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
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;
Conference_Titel :
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location :
Newport, CA
Print_ISBN :
0-8186-3442-1
DOI :
10.1109/IPPS.1993.262910
