Data mapping of linear programming on fixed-size hypercubes

Although many solution methods are available for the linear programming problem, the simplex method is undoubtedly the most widely used one for its simplicity. In this paper, we propose an implementation of the simplex method on fixed-size hypercubes. A partitioning technique and a mapping technique are presented to fit large-size problem instances into relatively small-size hypercubes. Two cases, pipelined broadcasting allowed and pipelined broadcasting not allowed, are considered. We show that the proposed implementation achieves the linear speedup asymptotically for both cases. Also, under the given mapping method, we discuss how to partition data so as to minimize the total run time and the communication time. We derive sufficient conditions for optimal partitionings. These sufficient conditions are helpful to obtain better partitionings. The optimal partitioning is obtained for a special case.