Abstract
An implementation of the simplex method for solving the linear programming problem on fixed-size hypercubes is presented. A partitioning technique and a mapping technique are also presented to fit large problems into relatively small hypercubes. Two cases, pipelined broadcastings allowed and not allowed, are considered. It is shown that the proposed implementation achieves the optimal speedup asymptotically for both cases. Sufficient conditions for optimal partitionings when the problem sizes are considered finite are derived. These conditions will be useful in obtaining better partitionings. Optimal partitionings are found for some special cases.