Parallel simplex algorithms and loop spreading Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/8336h4418

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Parallel solutions for two classes of linear programs are presented. First we parallelized the two-phase revised simplex algorithm and showed that it is possible to get linear improvement in performance. The simplex algorithm is the best known algorithm for solving linear programs, and we claim our result is the best one which can be achieved. Next we study the parallelization of the decomposed simplex algorithm. One of our new parallel algorithms has achieved 2*P time of performance improvement over the decomposed simplex algorithm using P processors. Meanwhile, we discovered a particular variation of the decomposed simplex algorithm which can run 2 times faster than the original one. The new parallel algorithm linearly speedups the fast sequential algorithm. As in any parallel program, unbalanced processor load causes the performance of the parallel decomposed simplex algorithm to drop significantly when the size of the input data is not a multiple of the number of available processors. To remove this limitation, we invented a load balance technique called Loop Spreading that evenly distributes parallel tasks on multiple processors without a drop in performance even when the size of the input data is not a multiple of the number of processors. Loop Spreading is a general technique that can be used automatically by a compiler to balance processor load in any language that supports parallel loop constructs.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6770A in PDF format. CVista PdfCompressor 5.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-05-29T16:06:49Z (GMT) No. of bitstreams: 1 WuYoufeng1989.pdf: 1808516 bytes, checksum: 744923f86ff39aae1e9c827b342296b0 (MD5)
  • description.provenance : Made available in DSpace on 2013-07-22T19:31:38Z (GMT). No. of bitstreams: 1 WuYoufeng1989.pdf: 1808516 bytes, checksum: 744923f86ff39aae1e9c827b342296b0 (MD5) Previous issue date: 1988-11-10
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-07-22T19:31:38Z (GMT) No. of bitstreams: 1 WuYoufeng1989.pdf: 1808516 bytes, checksum: 744923f86ff39aae1e9c827b342296b0 (MD5)
  • description.provenance : Submitted by Kaylee Patterson (kdpscanner@gmail.com) on 2013-05-17T20:56:21Z No. of bitstreams: 1 WuYoufeng1989.pdf: 1808516 bytes, checksum: 744923f86ff39aae1e9c827b342296b0 (MD5)

Relationships

In Administrative Set:
Last modified: 08/07/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items