Parallel execution of the Simplex algorithm

Graduate Project

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/graduate_projects/79408534h

Descriptions

Attribute Name	Values
Creator	Choi, Sungwoon
Abstract	This project is concerned with the optimal distribution of the computation and the data in parallelized Simplex algorithms. Test cases were implemented on a 16-processor Transputer system from INMOS Corporation. By careful consideration of distribution of computations and data, a nearly linear speedup pattern was obtained. The most interesting thing in this study was that 1) the execution time is not dependant on communication delay, 2) overhead due to parallelization does not significantly increase as the number of processors increase and 3) the Simplex algorithm communication delay is not so significant if the problem size is big enough. Keywords and phrases : message-passing, two-phase Simplex, linear programming, distributed memory, multiprocessor system
Resource Type	Capstone Project
Date Issued	1988-04-30
Degree Level	Master's
Degree Name	Master of Science (M.S.)
Degree Field	Computer Science
Degree Grantor	Oregon State University
Commencement Year	1988
Advisor	Lewis, Ted G.
Academic Affiliation	Computer Science
Rights Statement	In Copyright
Publisher	Oregon State University
Peer Reviewed	No
Language	English [eng]
File Format	pdf

Thumbnail	Title	Date Uploaded	Visibility	Actions
	Choi_Sungwoon_1988_04_30.pdf	2022-11-23	Public	Download