Special-Purpose Hardware Architecture for Large Scale Linear Programming

Shinhaeng LEE  Shin'ichiro OMACHI  Hirotomo ASO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E80-D   No.9   pp.893-898
Publication Date: 1997/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)
Category: Computer Architecture
Keyword: 
parallel processing,  systolic arrays,  special-purpose hardware,  linear programming,  revised simplex method,  

Full Text: PDF>>
Buy this Article



Summary: 
Linear programming techniques are useful in many diverse applications such as: production planning, energy distribution etc. To find an optimal solution of the linear programming problem, we have to repeat computations and it takes a lot of processing time. For high speed computation of linear programming, special purpose hardware has been sought. This paper proposes a systolic array for solving linear programming problems using the revised simplex method which is a typical algorithm of linear programming. This paper also proposes a modified systolic array that can solve linear programming problems whose sizes are very large.