Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

Parallel dynamic load-balancing for adaptive unstructured meshes

This chapter describes a parallel optimization technique that incorporates a distributed load-balancing algorithm and provides an extremely fast solution to the problem of load-balancing adaptive unstructured meshes. Moreover, a parallel graph contraction technique can be employed to enhance the partition quality and the resulting strategy outperforms or matches results from existing state-of-the-art static mesh partitioning algorithms. The strategy can also be applied to static partitioning problems. Dynamic procedures have been found to be much faster than static techniques, to provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data. The method employs a new iterative optimization technique that balances the workload and attempts to minimize the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more quickly. The dynamic evolution of load has three major influences on possible partitioning techniques; cost, reuse, and parallelism. The unstructured mesh may be modified every few time-steps and so the load-balancing must have a low cost relative to that of the solution algorithm in between remeshing.

Permanent Magnet Synchronous Machine for Parallel Hybrid Vehicle

The aim of this thesis is to describe hybrid drive design problems, the advantages and difficulties related to the drive. A review of possible hybrid constructions, benefits of parallel, series and series-parallel hybrids is done. In the thesis analytical and finite element calculations of permanent magnet synchronous machines with embedded magnets were done. The finite element calculations were done using Cedrat’s Flux 2D software. This machine is planned to be used as a motor-generator in a low power parallel hybrid vehicle. The boundary conditions for the design were found from Lucas-TVS Ltd., India. Design Requirements, briefly: • The system DC voltage level is 120 V, which implies Uphase = 49 V (RMS) in a three phase system. • The power output of 10 kW at base speed 1500 rpm (Torque of 65 Nm) is desired. • The maximum outer diameter should not be more than 250 mm, and the maximum core length should not exceed 40 mm. The main difficulties which the author met were the dimensional restrictions. After having designed and analyzed several possible constructions they were compared and the final design selected. Dimensioned and detailed design is performed. Effects of different parameters, such as the number of poles, number of turns and magnetic geometry are discussed. The best modification offers considerable reduction of volume.

Independent AND-parallel implementation of narrowing

We present a parallel graph narrowing machine, which is used to implement a functional logic language on a shared memory multiprocessor. It is an extensión of an abstract machine for a purely functional language. The result is a programmed graph reduction machine which integrates the mechanisms of unification, backtracking, and independent and-parallelism. In the machine, the subexpressions of an expression can run in parallel. In the case of backtracking, the structure of an expression is used to avoid the reevaluation of subexpressions as far as possible. Deterministic computations are detected. Their results are maintained and need not be reevaluated after backtracking.

Mesh partitioning and load balancing for distributed memory parallel systems

A method is outlined for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a relative gain iterative technique to both evenly balance the workload and minimise the number and volume of interprocessor communications. A parallel graph reduction technique is also briefly described and can be used to give a global perspective to the optimisation. The algorithms work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds. The algorithms can also be used for dynamic load-balancing, reusing existing partitions and in this case the procedures are much faster than static techniques, provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data.

Experimental and theoretical study of transport properties in uniaxially pressed (Bi, Pb)(2)Sr(2)Ca(2)Cu(3)O(10+delta) ceramic samples

Experimental and theoretical studies on the magnetic field dependence of the electrical resistance R(B(a)) and the transport noise (TN) in polycrystalline high-T(c) superconductors subjected to different uniaxial compacting pressures were conducted. X-ray diffraction rocking curves were performed in different surfaces of the samples in order to investigated the degree of texture The results indicated an improvement of the degree of texture with increasing the uniaxial compacting pressure In theoretical simulations of the data, the polycrystalline superconductors were described as a series-parallel array of Josephson devices The intergranular magnetic field is described within the framework of the intragranular flux-trapping model and the distribution of the grain-boundary angles is assumed to follow the Rayleigh statistical function The proposed model describes well the experimental magnetoresistance R(B(a)) data We have found that the behavior of the R(B(a)) curves changes appreciably when different uniaxially compacting pressures are applied to the sample and such a changes are reproduced by the model when different grain-boundary angles distributions are used In addition, changes in the R(B(a)) dependence have their counterparts in the experimental transport noise signals (C) 2009 Elsevier B.V. All rights reserved

An Improved Design Procedure for LCC Resonant Filter of Dimmable Electronic Ballasts for Fluorescent Lamps, Based on Lamp Model

This paper presents an improved design methodology for determining the parameters used in the classical Series-Parallel Loaded Resonant (SPLR) filter employed in the switching frequency controlled dimmable electronic ballasts. According to the analysis developed in this paper, it is possible to evaluate some characteristics of the resonant filter during the dimming process, such as: range of switching frequency, phase shift and rms value of the current drained by the resonant filter + fluorescent lamp set.

Dimmable electronic ballast with high power-factor SEPIC preregulator, for multiple tubular fluorescent lamps

An electronic ballast for multiple tubular fluorescent lamps is presented in this paper. The proposed structure features high power-factor, dimming capability, and soft-switching to the semiconductor devices operated in high frequencies. A Zero-Current-Switching - Pulse-Width-Modulated (ZCS-PWM) SEPIC converter composes the rectifying stage, controlled by the instantaneous average input current technique, performing soft-commutations and high input power factor. Regarding the inverting stage, it is composed by a classical resonant Half-Bridge converter, associated to Series Parallel-Loaded Resonant (SPLR) filters. The dimming control technique employed in this Half-Bridge inverter is based on the phase-shift in the current processed through the sets of filter + lamp. In addition, experimental results are shown in order to validate the developed analysis.

Algoritmos para geração de referências, inicialização e proteção de um condicionador unificado de qualidade de energia

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Reatores eletrônicos para sistemas de iluminação com múltiplas lâmpadas tubulares fluorescentes com controle de luminosidade, elevada eficiência e elevado fator de potência

Pós-graduação em Engenharia Elétrica - FEIS

Glucose-Insulin regulator for type 1 diabetes using high order neural networks

In this paper a Glucose-Insulin regulator for Type 1 Diabetes using artificial neural networks (ANN) is proposed. This is done using a discrete recurrent high order neural network in order to identify and control a nonlinear dynamical system which represents the pancreas? beta-cells behavior of a virtual patient. The ANN which reproduces and identifies the dynamical behavior system, is configured as series parallel and trained on line using the extended Kalman filter algorithm to achieve a quickly convergence identification in silico. The control objective is to regulate the glucose-insulin level under different glucose inputs and is based on a nonlinear neural block control law. A safety block is included between the control output signal and the virtual patient with type 1 diabetes mellitus. Simulations include a period of three days. Simulation results are compared during the overnight fasting period in Open-Loop (OL) versus Closed- Loop (CL). Tests in Semi-Closed-Loop (SCL) are made feedforward in order to give information to the control algorithm. We conclude the controller is able to drive the glucose to target in overnight periods and the feedforward is necessary to control the postprandial period.

A study in the application of domestic solar assisted heat pumps for heating and cooling

In the present work, the more important parameters of the heat pump system and of solar assisted heat pump systems were analysed in a quantitative way. Ideal and real Rankine cycles applied to the heat pump, with and without subcooling and superheating were studied using practical recommended values for their thermodynamics parameters. Comparative characteristics of refrigerants here analysed looking for their applicability in heat pumps for domestic heating and their effect in the performance of the system. Curves for the variation of the coefficient of performance as a function of condensing and evaporating temperatures were prepared for R12. Air, water and earth as low-grade heat sources and basic heat pump design factors for integrated heat pumps and thermal stores and for solar assisted heat pump-series, parallel and dual-systems were studied. The analysis of the relative performance of these systems demonstrated that the dual system presents advantages in domestic applications. An account of energy requirements for space and hater heating in the domestic sector in the O.K. is presented. The expected primary energy savings by using heat pumps to provide for the heating demand of the domestic sector was found to be of the order of 7%. The availability of solar energy in the U.K. climatic conditions and the characteristics of the solar radiation here studied. Tables and graphical representations in order to calculate the incident solar radiation over a tilted roof were prepared and are given in this study in section IV. In order to analyse and calculate the heating load for the system, new mathematical and graphical relations were developed in section V. A domestic space and water heating system is described and studied. It comprises three main components: a solar radiation absorber, the normal roof of a house, a split heat pump and a thermal store. A mathematical study of the heat exchange characteristics in the roof structure was done. This permits to evaluate the energy collected by the roof acting as a radiation absorber and its efficiency. An indication of the relative contributions from the three low-grade sources: ambient air, solar boost and heat loss from the house to the roof space during operation is given in section VI, together with the average seasonal performance and the energy saving for a prototype system tested at the University of Aston. The seasonal performance as found to be 2.6 and the energy savings by using the system studied 61%. A new store configuration to reduce wasted heat losses is also discussed in section VI.

Ferroelectric-like behaviour of melanin:humidity effect on current-voltage characteristics

The influence of low vacuum on quasistatic current-voltage (I–V) dependences and the impact of wet air pulse on dynamic bipolar I-V-loops and unipolar I-V-curves of fungal melanin thin layers have been studied for the first time. The threshold hysteresis voltages of I–V dependences are near to the standard electrode potentials of anodic water decomposition. Short wet air pulse impact leads to sharp increase of the current and appearance of “hump”-like and “knee”-like features of I-V-loops and I-V-curves, respectively. By treatment of I-V-loop allowing for I-V-curve shape the maxima of displacement current are revealed. The peculiarities of I-V-characteristics were modelled by series-parallel RC-circuit with Zener diodes as nonlinear elements. As a reason of appearance of temporal polar media with reversible ferroelectric-like polarization and ionic space charge transfer is considered the water-assisted dissociation of some ionic groups of melanin monomers that significantly influences electrophysical parameters of melanin nanostructures.

Scalable unstructured mesh decomposition

As the efficiency of parallel software increases it is becoming common to measure near linear speedup for many applications. For a problem size N on P processors then with software running at O(N=P ) the performance restrictions due to file i/o systems and mesh decomposition running at O(N) become increasingly apparent especially for large P . For distributed memory parallel systems an additional limit to scalability results from the finite memory size available for i/o scatter/gather operations. Simple strategies developed to address the scalability of scatter/gather operations for unstructured mesh based applications have been extended to provide scalable mesh decomposition through the development of a parallel graph partitioning code, JOSTLE [8]. The focus of this work is directed towards the development of generic strategies that can be incorporated into the Computer Aided Parallelisation Tools (CAPTools) project.