Special-Purpose Hardware Architecture for Large Scale Linear Programming

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. key words: parallel processing, systolic arrays, special-purpose hardware, linear programming, revised simplex method Shinhaeng Lee received the B.S. degree in Electrical Engineering from Hongik University, Korea, in 1995. He is currently an M.S. Candidate in Electric Communication Engineering, Tohoku University, Japan. His current research interests include the design of special-purpose hardware such as linear programming problems or fractal image compression. Shin'ichiro Omachi received the B.E., M.E. and Dr.Eng. degrees in Information Engineering from Tohoku University, Japan, in 1988, 1990 and 1993, respectively. He has worked as a research associate at Education Center for Information Processing, Tohoku University from 1993 to 1996. He is now a research associate at Graduate School of Engineering, Tohoku University. His research interests include pattern recognition, parallel pro-cessing, fuzzy system etc. Dr. Omachi is a member of IEEE, the Information Processing Society of Japan, and the Japanese Society of Artificial Intelligence. Hirotomo Aso received B.E., M.E., and Dr.Eng. degrees in Electrical Engineering from Tohoku University, Sendai, Japan, in 1968, 1970, and 1974, respectively. He was with the Department of Information Engineering, Tohoku University in 1973, and joined the Faculty of Engineering, Nagoya University from 1979 to 1986. He is now a Professor at Tohoku University. He is engaged in research on character pattern recognition, cellular au-tomata, concurrent program schema and parallel processing. Dr. Aso is a member of the Information Processing Society of Japan; the Japanese Society of Artificial Intelligence; IEEE; EATCS; and ACM.