Data mapping of linear programming on fixed-size hypercubes

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

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)235-243
Number of pages9
JournalParallel Computing
Volume13
Issue number2
DOIs
Publication statusPublished - 1990 Jan 1

Fingerprint

Broadcasting
Hypercube
Linear programming
Partitioning
Simplex Method
Sufficient Conditions
Communication
Simplicity
Speedup
Partition
Minimise

Keywords

  • Linear programming
  • data mapping
  • hypercubes
  • simplex method

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture
  • Control and Systems Engineering

Cite this

Data mapping of linear programming on fixed-size hypercubes. / Chen, Gen Huey; Ho, Hong-Fa; Lin, Shieu Hong; Sheu, Jang Ping.

In: Parallel Computing, Vol. 13, No. 2, 01.01.1990, p. 235-243.

Research output: Contribution to journalArticle

Chen, Gen Huey ; Ho, Hong-Fa ; Lin, Shieu Hong ; Sheu, Jang Ping. / Data mapping of linear programming on fixed-size hypercubes. In: Parallel Computing. 1990 ; Vol. 13, No. 2. pp. 235-243.
@article{cacbe8c39074435082d131655f919389,
title = "Data mapping of linear programming on fixed-size hypercubes",
abstract = "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.",
keywords = "Linear programming, data mapping, hypercubes, simplex method",
author = "Chen, {Gen Huey} and Hong-Fa Ho and Lin, {Shieu Hong} and Sheu, {Jang Ping}",
year = "1990",
month = "1",
day = "1",
doi = "10.1016/0167-8191(90)90150-8",
language = "English",
volume = "13",
pages = "235--243",
journal = "Parallel Computing",
issn = "0167-8191",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Data mapping of linear programming on fixed-size hypercubes

AU - Chen, Gen Huey

AU - Ho, Hong-Fa

AU - Lin, Shieu Hong

AU - Sheu, Jang Ping

PY - 1990/1/1

Y1 - 1990/1/1

N2 - 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.

AB - 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.

KW - Linear programming

KW - data mapping

KW - hypercubes

KW - simplex method

UR - http://www.scopus.com/inward/record.url?scp=0025384428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025384428&partnerID=8YFLogxK

U2 - 10.1016/0167-8191(90)90150-8

DO - 10.1016/0167-8191(90)90150-8

M3 - Article

AN - SCOPUS:0025384428

VL - 13

SP - 235

EP - 243

JO - Parallel Computing

JF - Parallel Computing

SN - 0167-8191

IS - 2

ER -