A strategy for scheduling tightly coupled parallel applications on clusters

Although various strategies have been developed for scheduling parallel applications with independent tasks, very little work exists for scheduling tightly coupled parallel applications on cluster environments. In this paper, we compare four different strategies based on performance models of tightly coupled parallel applications for scheduling the applications on clusters. In addition to algorithms based on existing popular optimization techniques, we also propose a new algorithm called Box Elimination that searches the space of performance model parameters to determine the best schedule of machines. By means of real and simulation experiments, we evaluated the algorithms on single cluster and multi-cluster setups. We show that our Box Elimination algorithm generates up to 80% more efficient schedule than other algorithms. We also show that the execution times of the schedules produced by our algorithm are more robust against the performance modeling errors.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

DMT of Multi-hop Cooperative Networks-Part I: K-Parallel-Path Networks

We consider single-source, single-sink multi-hop relay networks, with slow-fading Rayleigh fading links and single-antenna relay nodes operating under the half-duplex constraint. While two hop relay networks have been studied in great detail in terms of the diversity-multiplexing tradeoff (DMT), few results are available for more general networks. In this two-part paper, we identify two families of networks that are multi-hop generalizations of the two hop network: K-Parallel-Path (KPP) networks and Layered networks. In the first part, we initially consider KPP networks, which can be viewed as the union of K node-disjoint parallel paths, each of length > 1. The results are then generalized to KPP(I) networks, which permit interference between paths and to KPP(D) networks, which possess a direct link from source to sink. We characterize the optimal DMT of KPP(D) networks with K >= 4, and KPP(I) networks with K >= 3. Along the way, we derive lower bounds for the DMT of triangular channel matrices, which are useful in DMT computation of various protocols. As a special case, the DMT of two-hop relay network without direct link is obtained. Two key implications of the results in the two-part paper are that the half-duplex constraint does not necessarily entail rate loss by a factor of two, as previously believed and that, simple AF protocols are often sufficient to attain the best possible DMT.

Multilevel Dodecagonal Space Vector Generation for Open-end Winding Induction Motor Drive Using Conventional Three Level Inverters

A novel dodecagonal space vector structure for induction motor drive is presented in this paper. It consists of two dodecagons, with the radius of the outer one twice the inner one. Compared to existing dodecagonal space vector structures, to achieve the same PWM output voltage quality, the proposed topology lowers the switching frequency of the inverters and reduces the device ratings to half. At the same time, other benefits obtained from existing dodecagonal space vector structure are retained here. This includes the extension of the linear modulation range and elimination of all 6+/-1 harmonics (n=odd) from the phase voltage. The proposed structure is realized by feeding an open-end winding induction motor with two conventional three level inverters. A detailed calculation of the PWM timings for switching the space vector points is also presented. Simulation and experimental results indicate the possible application of the proposed idea for high power drives.

Parallel implementation of AutoDock

Computational docking of ligands to protein structures is a key step in structure-based drug design. Currently, the time required for each docking run is high and thus limits the use of docking in a high-throughput manner, warranting parallelization of docking algorithms. AutoDock, a widely used tool, has been chosen for parallelization. Near-linear increases in speed were observed with 96 processors, reducing the time required for docking ligands to HIV-protease from 81 min, as an example, on a single IBM Power-5 processor ( 1.65 GHz), to about 1 min on an IBM cluster, with 96 such processors. This implementation would make it feasible to perform virtual ligand screening using AutoDock.

Monoclinic polymorph of Boc-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe(anhydrous). Parallel packing of 3(10)-/alpha-helices and a transition of helix type

The structures of two crystal forms of Boc-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe have been determined. The triclinic form (P1, Z = 1) from DMSO/H2O crystallizes as a dihydrate (Karle, Sukumar & Balaram (1986) Proc, Natl, Acad. Sci. USA 83, 9284-9288). The monoclinic form (P2(1), Z = 2) crystallized from dioxane is anhydrous. The conformation of the peptide is essentially the same in both crystal system, but small changes in conformational angles are associated with a shift of the helix from a predominantly alpha-type to a predominantly 3(10)-type. The r.m.s. deviation of 33 atoms in the backbone and C beta positions of residues 2-8 is only 0.29 A between molecules in the two polymorphs. In both space groups, the helical molecules pack in a parallel fashion, rather than antiparallel. The only intermolecular hydrogen bonding is head-to-tail between helices. There are no lateral hydrogen bonds. In the P2(1) cell, a = 9.422(2) A, b = 36.392(11) A, c = 10.548(2) A, beta = 111.31(2) degrees and V = 3369.3 A for 2 molecules of C60H97N11O13 per cell.

Parallel and antiparallel aggregation of alpha-helices. Crystal structures of two apolar decapeptides X-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe (X = Boc, Ac)

An apolar helical decapeptide with different end groups, Boc- or Ac-, crystallizes in a completely parallel fashion for the Boc-analog and in an antiparallel fashion for the Ac-analog. In both crystals, the packing motif consists of rows of parallel molecules. In the Boc-crystals, adjacent rows assemble with the helix axes pointed in the same direction. In the Ac-crystals, adjacent rows assemble with the helix axes pointed in opposite directions. The conformations of the molecules in both crystals are quite similar, predominantly alpha-helical, except for the tryptophanyl side chain where chi 1 congruent to 60 degrees in the Boc- analog and congruent to 180 degrees in the Ac-analog. As a result, there is one lateral hydrogen bond between helices, N(1 epsilon)...O(7), in the Ac-analog. The structures do not provide a ready rationalization of packing preference in terms of side-chain interactions and do not support a major role for helix dipole interactions in determining helix orientation in crystals. The crystal parameters are as follow. Boc-analog: C60H97N11O13.C3H7OH, space group Pl with a = 10.250(3) A, b = 12.451(4) A, c = 15.077(6) A, alpha = 96.55(3) degrees, beta = 92.31(3) degrees, gamma = 106.37(3) degrees, Z = 1, R = 5.5% for 5581 data ([F] greater than 3.0 sigma(F)), resolution 0.89 A. Ac-analog: C57H91N11O12, space group P2(1) with a = 9.965(1) A, b = 19.707(3) A, c = 16.648(3) A, beta = 94.08(1), Z = 2, R = 7.2% for 2530 data ([F] greater than 3.0 sigma(F)), resolution 1.00 A.

BER-optimized linear parallel interference cancellers for multicarrier DS-CDMA systems

In this paper, we consider the design and bit-error performance analysis of linear parallel interference cancellers (LPIC) for multicarrier (MC) direct-sequence code division multiple access (DS-CDMA) systems. We propose an LPIC scheme where we estimate and cancel the multiple access interference (MAT) based on the soft decision outputs on individual subcarriers, and the interference cancelled outputs on different subcarriers are combined to form the final decision statistic. We scale the MAI estimate on individual subcarriers by a weight before cancellation. In order to choose these weights optimally, we derive exact closed-form expressions for the bit-error rate (BER) at the output of different stages of the LPIC, which we minimize to obtain the optimum weights for the different stages. In addition, using an alternate approach involving the characteristic function of the decision variable, we derive BER expressions for the weighted LPIC scheme, matched filter (MF) detector, decorrelating detector, and minimum mean square error (MMSE) detector for the considered multicarrier DS-CDMA system. We show that the proposed BER-optimized weighted LPIC scheme performs better than the MF detector and the conventional LPIC scheme (where the weights are taken to be unity), and close to the decorrelating and MMSE detectors.

Free convection heat transfer between vertical parallel plates

A new mathematical model for the solution of the problem of free convection heat transfer between vertical parallel flat isothermal plates under isothermal boundary conditions, has been presented. The set of boundary layer equations used in the model are transformed to nonlinear coupled differential equations by similarity type variables as obtained by Ostrach for vertical flat plates in an infinite fluid medium. By utilising a parameter ηw* to represent the outer boundary, the governing differential equations are solved numerically for parametric values of Pr = 0.733. 2 and 3, and ηw* = 0.1, 0.5, 1, 2, 3, 4, ... and 8.0. The velocity and temperature profiles are presented. Results indicate that ηw* can effectively classify the system into (1) thin layers where conduction predominates, (2) intermediate layers and (3) thick layers whose results can be predicted by the solutions for vertical flat plates in infinite fluid medium. Heat transfer correlations are presented for the 3 categories. Several experimental and analytical results available in the literature agree with the present correlations.

A Survey on Cascaded Multilevel Inverters

Cascaded multilevel inverters synthesize a medium-voltage output based on a series connection of power cells which use standard low-voltage component configurations. This characteristic allows one to achieve high-quality output voltages and input currents and also outstanding availability due to their intrinsic component redundancy. Due to these features, the cascaded multilevel inverter has been recognized as an important alternative in the medium-voltage inverter market. This paper presents a survey of different topologies, control strategies and modulation techniques used by these inverters. Regenerative and advanced topologies are also discussed. Applications where the mentioned features play a key role are shown. Finally, future developments are addressed.

An Integrated Design Procedure for High Frequency AC Inductors for Inverters

Inductors are important energy storage elements that are used as filters in switching power converters. The operating efficiency of power inductors depend on the initial design choices and they remain as one of the most inefficient elements in a power converter. The focus of this paper is to explore the inductor design procedure from the point of efficiency and operating temperature. A modified form of the area product approach is used as starting point for the inductor design. The equations which estimate the power loss in core and copper winding are described. The surface temperature of the inductor is modelled using heat transfer equations for radiation and natural convection. All design assumptions are verified by actual experimental data and results show a good match with the analysis.

Singularity and controllability analysis of parallel manipulators and closed-loop mechanisms

This paper presents a study of kinematic and force singularities in parallel manipulators and closed-loop mechanisms and their relationship to accessibility and controllability of such manipulators and closed-loop mechanisms, Parallel manipulators and closed-loop mechanisms are classified according to their degrees of freedom, number of output Cartesian variables used to describe their motion and the number of actuated joint inputs. The singularities in the workspace are obtained by considering the force transformation matrix which maps the forces and torques in joint space to output forces and torques ill Cartesian space. The regions in the workspace which violate the small time local controllability (STLC) and small time local accessibility (STLA) condition are obtained by deriving the equations of motion in terms of Cartesian variables and by using techniques from Lie algebra.We show that for fully actuated manipulators when the number ofactuated joint inputs is equal to the number of output Cartesian variables, and the force transformation matrix loses rank, the parallel manipulator does not meet the STLC requirement. For the case where the number of joint inputs is less than the number of output Cartesian variables, if the constraint forces and torques (represented by the Lagrange multipliers) become infinite, the force transformation matrix loses rank. Finally, we show that the singular and non-STLC regions in the workspace of a parallel manipulator and closed-loop mechanism can be reduced by adding redundant joint actuators and links. The results are illustrated with the help of numerical examples where we plot the singular and non-STLC/non-STLA regions of parallel manipulators and closed-loop mechanisms belonging to the above mentioned classes. (C) 2000 Elsevier Science Ltd. All rights reserved.