Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
Practical Algorithms For Selection On Coarse-Grained Parallel Computers, Ibraheem Al-Furaih, Srinivas Aluru, Sanjay Goil, Sanjay Ranka
Practical Algorithms For Selection On Coarse-Grained Parallel Computers, Ibraheem Al-Furaih, Srinivas Aluru, Sanjay Goil, Sanjay Ranka
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
In this paper, we consider the problem of selection on coarse-grained distributed memory parallel computers. We discuss several deterministic and randomized algorithms for parallel selection. We also consider several algorithms for load balancing needed to keep a balanced distribution of data across processors during the execution of the selection algorithms. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on the experimental results. We demonstrate that the randomized algorithms are superior to their deterministic counterparts.
Parallel Domain Decomposition And Load Balancing Using Space-Filling Curves, Srinivas Aluru, Faith E. Sevilgen
Parallel Domain Decomposition And Load Balancing Using Space-Filling Curves, Srinivas Aluru, Faith E. Sevilgen
Electrical Engineering and Computer Science - All Scholarship
Partitioning techniques based on space-filling curves have received much recent attention due to their low running time and good load balance characteristics. The basic idea underlying these methods is to order the multidimensional data according to a space-filling curve and partition the resulting one-dimensional order. However, space-filling curves are defined for points that lie on a uniform grid of a particular resolution. It is typically assumed that the coordinates of the points are representable using a fixed number of bits, and the run-times of the algorithms depend upon the number of bits used. In this paper, we present a simple …
Performance Modeling Of Load Balancing Algorithms Using Neural Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Performance Modeling Of Load Balancing Algorithms Using Neural Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
This paper presents a new approach that uses neural networks to predict the performance of a number of dynamic decentralized load balancing strategies. A distributed multicomputer system using any distributed load balancing strategy is represented by a unified analytical queuing model. A large simulation data set is used to train a neural network using the back–propagation learning algorithm based on gradient descent. The performance model using the predicted data from the neural network produces the average response time of various load balancing algorithms under various system parameters. The validation and comparison with simulation data show that the neural network is …
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.
Software Issues And Performance Of A Parallel Model For Stock Option Pricing, Kim Mills, Gang Cheng, Michael Vinson, Sanjay Ranka
Software Issues And Performance Of A Parallel Model For Stock Option Pricing, Kim Mills, Gang Cheng, Michael Vinson, Sanjay Ranka
Northeast Parallel Architecture Center
The finance industry is beginning to adopt parallel computing for numerical computation, and will soon be in a position to use parallel supercomputers. This paper examines software issues and performance of a stock option pricing model running on the Connection Machine-2 and DECmpp-12000. Pricing models incorporating stochastic volatility with American call (early exercise) are computationally intensive and require substantial communication. Three parallel versions of a stock option pricing model were developed which varied in data distribution, load balancing, and communication. The performance of this set of increasingly refined models ranged over no improvement, 10 times, and 100 times faster than …
A Comparison Of Load Balancing Algorithms For Parallel Computations, N. Mansouri, Geoffrey C. Fox
A Comparison Of Load Balancing Algorithms For Parallel Computations, N. Mansouri, Geoffrey C. Fox
Electrical Engineering and Computer Science - Technical Reports
Three physical optimization methods are considered in this paper for load balancing parallel computations. These are simulated annealing, genetic algorithms, and neural networks. Some design choices and the inclusion of additional steps lead to new versions of the algorithms with different solution qualities and execution times. The performances of these versions are critically evaluated and compared for test cases with different topologies and sizes. Orthogonal recursive coordinate bisection is also included in the comparison as a typical simple deterministic method. Simulation results show that the algorithms have diverse properties. Hence, different algorithms can be applied to different problems and requirements. …
Parallel Genetic Algorithms With Application To Load Balancing For Parallel Computing, N. Mansouri, Geoffrey C. Fox
Parallel Genetic Algorithms With Application To Load Balancing For Parallel Computing, N. Mansouri, Geoffrey C. Fox
Electrical Engineering and Computer Science - Technical Reports
A new coarse grain parallel genetic algorithm (PGA) and a new implementation of a data-parallel GA are presented in this paper. They are based on models of natural evolution in which the population is formed of discontinuous or continuous subpopulations. In addition to simulating natural evolution, the intrinsic parallelism in the two PGA's minimizes the possibility of premature convergence that the implementation of classic GA's often encounters. Intrinsic parallelism also allows the evolution of fit genotypes in a smaller number of generations in the PGA's than in sequential GA's, leading to superlinear speed-ups. The PGA's have been implemented on a …
A Decentralized Task Scheduling Algorithm And Its Performance Modeling For Computer Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra
A Decentralized Task Scheduling Algorithm And Its Performance Modeling For Computer Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
A dynamic task scheduling algorithm, that is stable, de-centralized, and adaptive to network topology, is presented. The proposed algorithm is an extension of nearest neighbor load balancing strategy with an enhanced degree of efficiency and it is intended for multicomputers connected by a store and forward communication network. The proposed algorithm is modeled by a central server open queuing network. It is shown that the response time of a task consists of two parts. The first part comprises a task‘s settling time which consists of scheduling time, communication time, and waiting time in scheduling and communication queues. The second part …