Speedup and scalability analysis of Master-Slave applications on large heterogeneous clusters

Although cluster environments have an enormous potential processing power, real applications that take advantage of this power remain an elusive goal. This is due, in part, to the lack of understanding about the characteristics of the applications best suited for these environments. This paper focuses on Master/Slave applications for large heterogeneous clusters. It defines application, cluster and execution models to derive an analytic expression for the execution time. It defines speedup and derives speedup bounds based on the inherent parallelism of the application and the aggregated computing power of the cluster. The paper derives an analytical expression for efficiency and uses it to define scalability of the algorithm-cluster combination based on the isoefficiency metric. Furthermore, the paper establishes necessary and sufficient conditions for an algorithm-cluster combination to be scalable which are easy to verify and use in practice. Finally, it covers the impact of network contention as the number of processors grow. (C) 2007 Elsevier B.V. All rights reserved.

Tabu search algorithm for network synthesis

Large scale combinatorial problems such as the network expansion problem present an amazingly high number of alternative configurations with practically the same investment, but with substantially different structures (configurations obtained with different sets of circuit/transformer additions). The proposed parallel tabu search algorithm has shown to be effective in exploring this type of optimization landscape. The algorithm is a third generation tabu search procedure with several advanced features. This is the most comprehensive combinatorial optimization technique available for treating difficult problems such as the transmission expansion planning. The method includes features of a variety of other approaches such as heuristic search, simulated annealing and genetic algorithms. In all test cases studied there are new generation, load sites which can be connected to an existing main network: such connections may require more than one line, transformer addition, which makes the problem harder in the sense that more combinations have to be considered.

Comparative studies on non-convex optimization methods for transmission network expansion planning

We have investigated and extensively tested three families of non-convex optimization approaches for solving the transmission network expansion planning problem: simulated annealing (SA), genetic algorithms (GA), and tabu search algorithms (TS). The paper compares the main features of the three approaches and presents an integrated view of these methodologies. A hybrid approach is then proposed which presents performances which are far better than the ones obtained with any of these approaches individually. Results obtained in tests performed with large scale real-life networks are summarized.

Parallel simulated annealing applied to long term transmission network expansion planning

The simulated annealing optimization technique has been successfully applied to a number of electrical engineering problems, including transmission system expansion planning. The method is general in the sense that it does not assume any particular property of the problem being solved, such as linearity or convexity. Moreover, it has the ability to provide solutions arbitrarily close to an optimum (i.e. it is asymptotically convergent) as the cooling process slows down. The drawback of the approach is the computational burden: finding optimal solutions may be extremely expensive in some cases. This paper presents a Parallel Simulated Annealing, PSA, algorithm for solving the long term transmission network expansion planning problem. A strategy that does not affect the basic convergence properties of the Sequential Simulated Annealing algorithm have been implementeded and tested. The paper investigates the conditions under which the parallel algorithm is most efficient. The parallel implementations have been tested on three example networks: a small 6-bus network, and two complex real-life networks. Excellent results are reported in the test section of the paper: in addition to reductions in computing times, the Parallel Simulated Annealing algorithm proposed in the paper has shown significant improvements in solution quality for the largest of the test networks.

Collagen type VI is a component of the extracellular matrix microfibril network of the prostatic stroma

Stroma-epithelium relationships are of great relevance in prostatic morphogenesis and physiology, However, little knowledge exists about either stromal cells or extracellular matrix composition and arrangement in this system, Ultrastructural analysis revealed the existence of a microfibrillar system which occupies large areas of the rat prostatic stroma, In this work, we have applied immunocytochemistry and an ATP treatment for the ultrastructural identification of collagen type VI microfibrils, aiming at examining its participation in the prostatic microfibrillar network. Immunocytochemistry was also extended to a human case of prostatic nodular hyperplasia, Both methods succeeded in identifying collagen type VI in the rat ventral prostate, Collagen type VI is evenly distributed throughout the stroma but mainly associated with the basal lamina, collagen fibrils, and around the stromal cells, the use of ATP treatment allowed for the discrimination between collagen type VI and elastin-associated microfibrils, and demonstrated that these two classes of microfibrils establish an extended, mixed, and open network. The same aspects of association with the basal lamina, with stromal cells (particularly with smooth muscle cells), and with fibrillar components of the stroma were observed in the human tissue, We suggest that the collagen type VI and elastin-associated microfibril system may be involved in the control of some aspects of cellular behavior and may also play a structural role, maintaining the organ integrity after the deformations occurring under smooth muscle contraction.

Test systems and mathematical models for transmission network expansion planning

The data of four networks that can be used in carrying out comparative studies with methods for transmission network expansion planning are given. These networks are of various types and different levels of complexity. The main mathematical formulations used in transmission expansion studies-transportation models, hybrid models, DC power flow models, and disjunctive models are also summarised and compared. The main algorithm families are reviewed-both analytical, combinatorial and heuristic approaches. Optimal solutions are not yet known for some of the four networks when more accurate models (e.g. The DC model) are used to represent the power flow equations-the state of the art with regard to this is also summarised. This should serve as a challenge to authors searching for new, more efficient methods.

Algorithms for network piecewise-linear programs: A comparative study

Piecewise-Linear Programming (PLP) is an important area of Mathematical Programming and concerns the minimisation of a convex separable piecewise-linear objective function, subject to linear constraints. In this paper a subarea of PLP called Network Piecewise-Linear Programming (NPLP) is explored. The paper presents four specialised algorithms for NPLP: (Strongly Feasible) Primal Simplex, Dual Method, Out-of-Kilter and (Strongly Polynomial) Cost-Scaling and their relative efficiency is studied. A statistically designed experiment is used to perform a computational comparison of the algorithms. The response variable observed in the experiment is the CPU time to solve randomly generated network piecewise-linear problems classified according to problem class (Transportation, Transshipment and Circulation), problem size, extent of capacitation, and number of breakpoints per arc. Results and conclusions on performance of the algorithms are reported.

Comparative studies on non-convex optimization methods for transmission network expansion planning

We have investigated and extensively tested three families of non-convex optimization approaches for solving the transmission network expansion planning problem: simulated annealing (SA), genetic algorithms (GA), and tabu search algorithms (TS). The paper compares the main features of the three approaches and presents an integrated view of these methodologies. A hybrid approach is then proposed which presents performances which are far better than the ones obtained with any of these approaches individually. Results obtained in tests performed with large scale real-life networks are summarized.

A constructive heuristic algorithm to Short Term Transmission Network Expansion Planning

In this paper a method for solving the Short Term Transmission Network Expansion Planning (STTNEP) problem is presented. The STTNEP is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In this work we present a constructive heuristic algorithm to find a solution of the STTNEP of excellent quality. In each step of the algorithm a sensitivity index is used to add a circuit (transmission line or transformer) to the system. This sensitivity index is obtained solving the STTNEP problem considering as a continuous variable the number of circuits to be added (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an interior points method that uses a combination of the multiple predictor corrector and multiple centrality corrections methods, both belonging to the family of higher order interior points method (HOIPM). Tests were carried out using a modified Carver system and the results presented show the good performance of both the constructive heuristic algorithm to solve the STTNEP problem and the HOIPM used in each step.

Managing large scale virtual environments using portals

This article describes a technique for Large Scale Virtual Environments (LSVEs) partitioning in hexagon cells and using portal in the cell interfaces to reduce the number of messages on the network and the complexity of the virtual world. These environments usually demand a high volume of data that must be sent only to those users who needs the information [Greenhalgh, Benford 1997].

GDP 4.0 transfer to SGP 3.0 for SCIAMACHY no2 column processing: Verification with SDOAS / GDOAS prototype algorithms and delta-validation with NDACC / UV-visible network data

Until mid 2006, SCIAMACHY data processors for the operational retrieval of nitrogen dioxide (NO2) column data were based on the historical version 2 of the GOME Data Processor (GDP). On top of known problems inherent to GDP 2, ground-based validations of SCIAMACHY NO2 data revealed issues specific to SCIAMACHY, like a large cloud-dependent offset occurring at Northern latitudes. In 2006, the GDOAS prototype algorithm of the improved GDP version 4 was transferred to the off-line SCIAMACHY Ground Processor (SGP) version 3.0. In parallel, the calibration of SCIAMACHY radiometric data was upgraded. Before operational switch-on of SGP 3.0 and public release of upgraded SCIAMACHY NO2 data, we have investigated the accuracy of the algorithm transfer: (a) by checking the consistency of SGP 3.0 with prototype algorithms; and (b) by comparing SGP 3.0 NO2 data with ground-based observations reported by the WMO/GAW NDACC network of UV-visible DOAS/SAOZ spectrometers. This delta-validation study concludes that SGP 3.0 is a significant improvement with respect to the previous processor IPF 5.04. For three particular SCIAMACHY states, the study reveals unexplained features in the slant columns and air mass factors, although the quantitative impact on SGP 3.0 vertical columns is not significant.

Urban sprawl and energy use for transportation in the largest Brazilian cities

A study of the relationships between the amount of energy consumed for transportation purposes and a few selected variables related to urban form and socioeconomic characteristics of some of the largest Brazilian cities is conducted in this work. The studied cities include all 27 state capitals regardless of their size and population and 184 urban areas each with more than 20,000 inhabitants located in the state of São Paulo. Two different techniques were applied for data analyses: a more traditional regression analysis approach and artificial neural networks. In general, the results found in the analyses conducted here support the assumption that urban sprawl increases the energy use for transportation. In the case of the 27 state capitals, the analysis indicated that two spatial variables have a strong impact on the energy consumed for urban transportation: urban density and the ratio between the longest distances in the east-west and north-south directions. In the case of the 184 urbanized areas we also reached a similar conclusion. In that case, however, income and employment level apparently have a stronger influence on the amount of energy consumed. The results of the present study stress the importance of physical planning in developing country cities in order to reduce energy use for transportation. © 2007 International Energy Initiative, Inc.

Heuristic algorithm to solve the short term transmission network expansion planning

In this paper, a method for solving the short term transmission network expansion planning problem is presented. This is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In order to And a solution of excellent quality for this problem, a constructive heuristic algorithm is presented in this paper. In each step of the algorithm, a sensitivity index is used to add a circuit (transmission line or transformer) or a capacitor bank (fixed or variable) to the system. This sensitivity index is obtained solving the problem considering the numbers of circuits and capacitors banks to be added (relaxed problem), as continuous variables. The relaxed problem is a large and complex nonlinear programming and was solved through a higher order interior point method. The paper shows results of several tests that were performed using three well-known electric energy systems in order to show the possibility and the advantages of using the AC model. ©2007 IEEE.

Distribution network planning using a constructive heuristic algorithm

An optimization technique to solve distribution network planning (DNP) problem is presented. This is a very complex mixed binary nonlinear programming problem. A constructive heuristic algorithm (CHA) aimed at obtaining an excellent quality solution for this problem is presented. In each step of the CHA, a sensitivity index is used to add a circuit or a substation to the distribution network. This sensitivity index is obtained solving the DNP problem considering the numbers of circuits and substations to be added as continuous variables (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an efficient nonlinear optimization solver. A local improvement phase and a branching technique were implemented in the CHA. Results of two tests using a distribution network are presented in the paper in order to show the ability of the proposed algorithm. ©2009 IEEE.

An efficient codification to solve distribution network reconfiguration for loss reduction problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)