Paper Info
Title
Near optimal algorithms for scheduling independent chains in BSP
Abstract
The aim of this work is to show that scheduling a set of independent chains on a parallel machine under the BSP model is a difficult optimization problem which can be easily approximated in practice. BSP is a machine independent computational model which is becoming more and more popular. Finding the optimal solution when the number of processors is fixed is shown to be hard. Efficient heuristics including communications are proposed and analyzed. We particularly focus on the influence of synchronization between consecutive supersteps. Simulations of a large number of instances have been carried out to complement the theoretical worst case analysis. They confirm the very good behaviour of the algorithm on average
Year
DOI
Venue
1998
10.1109/HIPC.1998.738003
Madras
Keywords
Field
DocType
distributed memory systems,heuristic programming,optimisation,parallel machines,scheduling,synchronisation,BSP model,Bulk Synchronous Parallel,heuristics,independent chain scheduling,machine independent computational model,near optimal algorithms,optimal solution,optimization problem,parallel machine,simulation,synchronization,worst case analysis
Synchronization,Algorithm design,Scheduling (computing),Computer science,Parallel computing,Algorithm,Heuristics,Bulk synchronous parallel,Optimization problem,Electrical capacitance tomography,Distributed computing,Case analysis
Conference
ISSN
ISBN
Citations 
1094-7256
0-8186-9194-8
1
PageRank 
References 
Authors
0.36
3
3
Name
Order
Citations
PageRank
Alfredo Goldman124824.76
Gregory Mounie213711.22
Denis Trystram31120160.57