Grids with multiple batch systems for performance enhancement of multi-component and parameter sweep parallel applications

In this work, we evaluate the benefits of using Grids with multiple batch systems to improve the performance of multi-component and parameter sweep parallel applications by reduction in queue waiting times. Using different job traces of different loads, job distributions and queue waiting times corresponding to three different queuing policies(FCFS, conservative and EASY backfilling), we conducted a large number of experiments using simulators of two important classes of applications. The first simulator models Community Climate System Model (CCSM), a prominent multi-component application and the second simulator models parameter sweep applications. We compare the performance of the applications when executed on multiple batch systems and on a single batch system for different system and application configurations. We show that there are a large number of configurations for which application execution using multiple batch systems can give improved performance over execution on a single system.

A delphi study on health in future India

PIP: A delphi study was conducted to identify or envision health scenarios in India by the year 2000. Questionnaires consisting of 48 questions on 5 areas (diagnosis and therapy; family planning; pharmaceuticals and drugs; biochemical and biomedical research; health services) were mailed to 250 experts in India. 36 responded. Results were compiled and mailed back to the respondents for changes and comments. 17 people responded. Results of the delphi study shows that policy decisions with respect to compulsory family planning as well as health education at secondary school level will precede further breakthroughs in birth control technology. Non operation reversible sterilization procedures, immunological birth control, Ayurvedic medicines for contraception and abortion, and selection of baby's sex are all possible by 2000 thereafter. Complete eradication of infectious diseases, malnutrition and associated diseases is considered unlikely before 2000, as are advances in biomedical research. Changes in health services (e.g., significant increases in hospital beds and doctors, cheap bulk drugs), particularly in rural areas, are imminent, leading to prolonging of life expectancy to 70 years. Genetic engineering may provide significant breakthroughs in the prevention of malignancies and cardiac disorders. The India delphi study is patterned after a similar delphi study conducted in the U.S. by Smith, Kline and French (SKF) Laboratories in 1968. The SKF study was able to predict some breakthroughs with basic research which have been realized.

Effect of pulse profile variations on measurement of eccentricity in orbits of Cen X-3 and SMC X-1

It has long been argued that better timing precision allowed by satellites like Rossi X-ray Timing Explorer (RXTE) will allow us to measure the orbital eccentricity and the angle of periastron of some of the bright persistent high-mass X-ray binaries (HMXBs) and hence a possible measurement of apsidal motion in these system. Measuring the rate of apsidal motion allows one to estimate the apsidal motion constant of the mass losing companion star and hence allows for the direct testing of the stellar structure models for these giant stars present in the HMXBs. In the present paper, we use the archival RXTE data of two bright persistent sources, namely Cen X-3 and SMC X-1, to measure the very small orbital eccentricity and the angle of periastron. We find that the small variations in the pulse profiles of these sources, rather than the intrinsic time resolution provided by RXTE, limit the accuracy with which we can measure arrival time of the pulses from these sources. This influences the accuracy with which one can measure the orbital parameters, especially the very small eccentricity and the angle of periastron in these sources. The observations of SMC X-1 in the year 2000 were taken during the high-flux state of the source and we could determine the orbital eccentricity and omega using this data set.

High-Throughput Flexible Constraint Length Viterbi Decoders on De Bruijn, Shuffle-Exchange and Butterfly Connected Architectures

Flexible constraint length channel decoders are required for software defined radios. This paper presents a novel scalable scheme for realizing flexible constraint length Viterbi decoders on a de Bruijn interconnection network. Architectures for flexible decoders using the flattened butterfly and shuffle-exchange networks are also described. It is shown that these networks provide favourable substrates for realizing flexible convolutional decoders. Synthesis results for the three networks are provided and a comparison is performed. An architecture based on a 2D-mesh, which is a topology having a nominally lesser silicon area requirement, is also considered as a fourth point for comparison. It is found that of all the networks considered, the de Bruijn network offers the best tradeoff in terms of area versus throughput.

A real coded genetic algorithm for data partitioning and scheduling in networks with arbitrary processor release time

The problem of scheduling divisible loads in distributed computing systems, in presence of processor release time is considered. The objective is to find the optimal sequence of load distribution and the optimal load fractions assigned to each processor in the system such that the processing time of the entire processing load is a minimum. This is a difficult combinatorial optimization problem and hence genetic algorithms approach is presented for its solution.

Distributed nonlinear optimization algorithms for general network problems

There are a number of large networks which occur in many problems dealing with the flow of power, communication signals, water, gas, transportable goods, etc. Both design and planning of these networks involve optimization problems. The first part of this paper introduces the common characteristics of a nonlinear network (the network may be linear, the objective function may be non linear, or both may be nonlinear). The second part develops a mathematical model trying to put together some important constraints based on the abstraction for a general network. The third part deals with solution procedures; it converts the network to a matrix based system of equations, gives the characteristics of the matrix and suggests two solution procedures, one of them being a new one. The fourth part handles spatially distributed networks and evolves a number of decomposition techniques so that we can solve the problem with the help of a distributed computer system. Algorithms for parallel processors and spatially distributed systems have been described.There are a number of common features that pertain to networks. A network consists of a set of nodes and arcs. In addition at every node, there is a possibility of an input (like power, water, message, goods etc) or an output or none. Normally, the network equations describe the flows amoungst nodes through the arcs. These network equations couple variables associated with nodes. Invariably, variables pertaining to arcs are constants; the result required will be flows through the arcs. To solve the normal base problem, we are given input flows at nodes, output flows at nodes and certain physical constraints on other variables at nodes and we should find out the flows through the network (variables at nodes will be referred to as across variables).The optimization problem involves in selecting inputs at nodes so as to optimise an objective function; the objective may be a cost function based on the inputs to be minimised or a loss function or an efficiency function. The above mathematical model can be solved using Lagrange Multiplier technique since the equalities are strong compared to inequalities. The Lagrange multiplier technique divides the solution procedure into two stages per iteration. Stage one calculates the problem variables % and stage two the multipliers lambda. It is shown that the Jacobian matrix used in stage one (for solving a nonlinear system of necessary conditions) occurs in the stage two also.A second solution procedure has also been imbedded into the first one. This is called total residue approach. It changes the equality constraints so that we can get faster convergence of the iterations.Both solution procedures are found to coverge in 3 to 7 iterations for a sample network.The availability of distributed computer systems — both LAN and WAN — suggest the need for algorithms to solve the optimization problems. Two types of algorithms have been proposed — one based on the physics of the network and the other on the property of the Jacobian matrix. Three algorithms have been deviced, one of them for the local area case. These algorithms are called as regional distributed algorithm, hierarchical regional distributed algorithm (both using the physics properties of the network), and locally distributed algorithm (a multiprocessor based approach with a local area network configuration). The approach used was to define an algorithm that is faster and uses minimum communications. These algorithms are found to converge at the same rate as the non distributed (unitary) case.

Parallel min-cut placement on reduced hardware SIMD architecture.

Massively parallel SIMD computing is applied to obtain an order of magnitude improvement in the executional speed of an important algorithm in VLSI design automation. The physical design of a VLSI circuit involves logic module placement as a subtask. The paper is concerned with accelerating the well known Min-cut placement technique for logic cell placement. The inherent parallelism of the Min-cut algorithm is identified, and it is shown that a parallel machine based on the efficient execution of the placement procedure.

Fast algorithm for data exchange in reconfigurable tree structures

This paper presents a fast algorithm for data exchange in a network of processors organized as a reconfigurable tree structure. For a given data exchange table, the algorithm generates a sequence of tree configurations in which the data exchanges are to be executed. A significant feature of the algorithm is that each exchange is executed in a tree configuration in which the source and destination nodes are adjacent to each other. It has been proved in a theorem that for every pair of nodes in the reconfigurable tree structure, there always exists two and only two configurations in which these two nodes are adjacent to each other. The algorithm utilizes this fact and determines the solution so as to optimize both the number of configurations required and the time to perform the data exchanges. Analysis of the algorithm shows that it has linear time complexity, and provides a large reduction in run-time as compared to a previously proposed algorithm. This is well-confirmed from the experimental results obtained by executing a large number of randomly-generated data exchange tables. Another significant feature of the algorithm is that the bit-size of the routing information code is always two bits, irrespective of the number of nodes in the tree. This not only increases the speed of the algorithm but also results in simpler hardware inside each node.

Pipelined ring algorithm for matrix multiplication on transputer networks: performance analysis and estimation

A parallel matrix multiplication algorithm is presented, and studies of its performance and estimation are discussed. The algorithm is implemented on a network of transputers connected in a ring topology. An efficient scheme for partitioning the input matrices is introduced which enables overlapping computation with communication. This makes the algorithm achieve near-ideal speed-up for reasonably large matrices. Analytical expressions for the execution time of the algorithm have been derived by analysing its computation and communication characteristics. These expressions are validated by comparing the theoretical results of the performance with the experimental values obtained on a four-transputer network for both square and irregular matrices. The analytical model is also used to estimate the performance of the algorithm for a varying number of transputers and varying problem sizes. Although the algorithm is implemented on transputers, the methodology and the partitioning scheme presented in this paper are quite general and can be implemented on other processors which have the capability of overlapping computation with communication. The equations for performance prediction can also be extended to other multiprocessor systems.

Sustainable biomass production for energy in selected Asian countries

This paper presents a synthesis of assessment of sustainable biomass production potential in six Asian countries-China, India, Malaysia, Philippines, Sri Lanka and Thailand, and is based on the detailed studies carried out in these countries under the Asian Regional Research Programme in Energy, Environment and Climate (ARRPEEC). National level studies were undertaken to estimate land availability for biomass production, identify and evaluate the biomass production options in terms of yield per hectare and financial viability, estimate sustainable biomass production for energy, and estimate the energy potential of biomass production in the six Asian countries. Sustainable biomass production from plantation is estimated to be in the range of 182.5-210.5, 62-310, 0.4-1.7, 3.7-20.4, 2.0-9.9 and 11.6-106.6 Mt yr(-1) for China, India, Malaysia, Philippines, Sri Lanka and Thailand, respectively. The maximum annual electricity generation potential, using advanced technologies, from the sustainable biomass production is estimated to be about 27, 114, 4.5, 79, 254 and 195 percentage of the total electricity generation in year 2000 in China, India, Malaysia, Philippines, Sri Lanka and Thailand, respectively. Investment cost for bioenergy production varies from US$381 to 1842 ha(-1) in the countries considered in this study; investment cost for production of biomass varies from US$5.1 to 23 t(-1). (C) 2003 Elsevier Ltd. All rights reserved.

Automatic Compilation of MATLAB Programs for Synergistic Execution on Heterogeneous Processors

MATLAB is an array language, initially popular for rapid prototyping, but is now being increasingly used to develop production code for numerical and scientific applications. Typical MATLAB programs have abundant data parallelism. These programs also have control flow dominated scalar regions that have an impact on the program's execution time. Today's computer systems have tremendous computing power in the form of traditional CPU cores and throughput oriented accelerators such as graphics processing units(GPUs). Thus, an approach that maps the control flow dominated regions to the CPU and the data parallel regions to the GPU can significantly improve program performance. In this paper, we present the design and implementation of MEGHA, a compiler that automatically compiles MATLAB programs to enable synergistic execution on heterogeneous processors. Our solution is fully automated and does not require programmer input for identifying data parallel regions. We propose a set of compiler optimizations tailored for MATLAB. Our compiler identifies data parallel regions of the program and composes them into kernels. The problem of combining statements into kernels is formulated as a constrained graph clustering problem. Heuristics are presented to map identified kernels to either the CPU or GPU so that kernel execution on the CPU and the GPU happens synergistically and the amount of data transfer needed is minimized. In order to ensure required data movement for dependencies across basic blocks, we propose a data flow analysis and edge splitting strategy. Thus our compiler automatically handles composition of kernels, mapping of kernels to CPU and GPU, scheduling and insertion of required data transfer. The proposed compiler was implemented and experimental evaluation using a set of MATLAB benchmarks shows that our approach achieves a geometric mean speedup of 19.8X for data parallel benchmarks over native execution of MATLAB.

A decidable temporal logic with repeating values

Various logical formalisms with the freeze quantifier have been recently considered to model computer systems even though this is a powerful mechanism that often leads to undecidability. In this paper, we study a linear-time temporal logic with past-time operators such that the freeze operator is only used to express that some value from an infinite set is repeated in the future or in the past. Such a restriction has been inspired by a recent work on spatio-temporal logics. We show decidability of finitary and infinitary satisfiability by reduction into the verification of temporal properties in Petri nets. This is a surprising result since the logic is closed under negation, contains future-time and past-time temporal operators and can express the nonce property and its negation. These ingredients are known to lead to undecidability with a more liberal use of the freeze quantifier.