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.

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.

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.

Scheduling parallel batch processors with incompatible job families using ant colony optimization

The present work concerns with the static scheduling of jobs to parallel identical batch processors with incompatible job families for minimizing the total weighted tardiness. This scheduling problem is applicable in burn-in operations and wafer fabrication in semiconductor manufacturing. We decompose the problem into two stages: batch formation and batch scheduling, as in the literature. The Ant Colony Optimization (ACO) based algorithm called ATC-BACO algorithm is developed in which ACO is used to solve the batch scheduling problems. Our computational experimentation shows that the proposed ATC-BACO algorithm performs better than the available best traditional dispatching rule called ATC-BATC rule.

Effect of coordinated ions on structure and flexibility of parallel G-quadruplexes: A molecular dynamics study

ingle tract guanine residues can associate to form stable parallel quadruplex structures in the presence of certain cations. Nanosecond scale molecular dynamics simulations have been performed on fully solvated fibre model of parallel d(G(7)) quadruplex structures with Na+ or K+ ions coordinated in the cavity formed by the O6 atoms of the guanine bases. The AMBER 4.1 force field and Particle Mesh Ewald technique for electrostatic interactions have been used in all simulations. There quadruplex structures are stable during the simulation, with the middle four base tetrads showing root mean square deviation values between 0.5 to 0.8 Angstrom from the initial structure as well the high resolution crystal structure. Even in the absence of any coordinated ion in the initial structure, the G-quadruplex structure remains intact throughout the simulation. During the 1.1 ns MD simulation, one Nai counter ion from the solvent as well as several water molecules enter the central cavity to occupy the empty coordination sites within the parallel quadruplex and help stabilize the structure. Hydrogen bonding pattern depends on the nature of the coordinated ion, with the G-tetrad undergoing local structural variation to accommodate cations of different sizes. in the absence of any coordinated ion. due to strong mutual repulsion, O6 atoms within G-tetrad are forced farther apart from each other, which leads to a considerably different hydrogen bonding scheme within the G-tetrads and very favourable interaction energy between the guanine bases constituting a G-tetrad. However, a coordinated ion between G-tetrads provides extra stacking energy for the G-tetrads and makes the quadruplex structure more rigid. Na+ ions, within the quadruplex cavity, are more mobile than coordinated K+ ions. A number of hydrogen bonded water molecules are observed within the grooves of all quadruplex structures.

Parallel circuit partitioning on a reduced array architecture

The physical design of a VLSI circuit involves circuit partitioning as a subtask. Typically, it is necessary to partition a large electrical circuit into several smaller circuits such that the total cross-wiring is minimized. This problem is a variant of the more general graph partitioning problem, and it is known that there does not exist a polynomial time algorithm to obtain an optimal partition. The heuristic procedure proposed by Kernighan and Lin1,2 requires O(n2 log2n) time to obtain a near-optimal two-way partition of a circuit with n modules. In the VLSI context, due to the large problem size involved, this computational requirement is unacceptably high. This paper is concerned with the hardware acceleration of the Kernighan-Lin procedure on an SIMD architecture. The proposed parallel partitioning algorithm requires O(n) processors, and has a time complexity of O(n log2n). In the proposed scheme, the reduced array architecture is employed with due considerations towards cost effectiveness and VLSI realizability of the architecture.The authors are not aware of any earlier attempts to parallelize a circuit partitioning algorithm in general or the Kernighan-Lin algorithm in particular. The use of the reduced array architecture is novel and opens up the possibilities of using this computing structure for several other applications in electronic design automation.

Groove Binding Ligands for the Interaction with Parallel-Stranded ps-Duplex DNA and Triplex DNA

DNA adopts different conformations not only based on novel base pairs, but also with different chain polarities. Besides several duplex structures (A, B, Z, parallel stranded (ps)-DNA, etc.), DNA also forms higher-order structures like triplex, tetraplex, and i-motif. Each of these structures has its own biological significance. The ps-duplexes have been found to be resistant to certain nucleases and endonucleases. Molecules that promote triple-helix formation have significant potential. These investigations have many therapeutic advantages which may be useful in the regulation of the expression of genes responsible for certain diseases by locking either their transcription (antigene) or translation (antisense). Each DNA minor groove binding ligand (MGBL) interacts with DNA through helical minor groove recognition in a sequence-specific manner, and this interferes with several DNA-associated processes. Incidentally, these ligands interact with some non-B-DNA and with higher-order DNA structures including ps-DNA and triplexes. While the design and recognition of minor grooves of duplex DNA by specific MGBLs have been a topic of many reports, limited information is available on the binding behavior of MGBLs with nonduplex DNA. In this review, we summarize various attempts of the interaction of MGBLs with ps-DNA and DNA triplexes.