DocumentCode :
3487372
Title :
Data partitioning schemes for the parallel implementation of the revised simplex algorithm for LP problems
Author :
Sridhar, Usha ; Basu, A.
Author_Institution :
Center for Dev. of Adv. Comput., Bangalore, India
fYear :
1993
fDate :
13-16 Apr 1993
Firstpage :
379
Lastpage :
383
Abstract :
The parallel implementation of the revised simplex algorithm (RSA) using eta-factorization holds the promise of significant improvement in the execution time by virtue of the existence of a high degree of parallelism in the computation within an iteration of the algorithm. However, the scheme employed to partition key data structures in a distributed memory parallel processor has a great impact on the achievable performance. The paper explores the trade-offs between block-row and block-column partitioning schemes for the matrix of constraint coefficients vis-a-vis the communication overheads and granularity of parallel computations. The results of an approximate analysis of the compute-communication balance are compared with measurements from practical implementation of the partitioning schemes on C-DAC´s PARAM 8000 distributed memory parallel processor
Keywords :
data structures; distributed memory systems; linear programming; parallel algorithms; C-DAC´s PARAM 8000; LP problems; approximate analysis; block-column; block-row; communication overheads; data partitioning schemes; data structures; distributed memory parallel processor; eta-factorization; granularity; linear programming; parallel implementation; revised simplex algorithm; Acceleration; Concurrent computing; Costs; Data structures; Distributed computing; Engineering management; Linear programming; Memory management; Parallel processing; Partitioning algorithms;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location :
Newport, CA
Print_ISBN :
0-8186-3442-1
Type :
conf
DOI :
10.1109/IPPS.1993.262910
Filename :
262910
Link To Document :
بازگشت