Data mapping of linear programming on fixed-size hypercubes

Gen Huey Chen*, Hong Fa Ho, Shieu Hong Lin, Jang Ping Sheu


研究成果: 雜誌貢獻期刊論文同行評審

2 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)235-243
期刊Parallel Computing
出版狀態已發佈 - 1990 2月

ASJC Scopus subject areas

  • 軟體
  • 理論電腦科學
  • 硬體和架構
  • 電腦網路與通信
  • 電腦繪圖與電腦輔助設計
  • 人工智慧


深入研究「Data mapping of linear programming on fixed-size hypercubes」主題。共同形成了獨特的指紋。