Optimal and Heuristic Algorithms for Solving the Binding Problem

Minjoong Rim; Ashutosh Mujumdar; Rajiv Jain; Renato DeLeone

doi:10.1109/92.285747

Optimal and Heuristic Algorithms for Solving the Binding Problem

Minjoong Rim, Ashutosh Mujumdar, Rajiv Jain, Renato DeLeone

Department of Information and Communication Engineering

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

In this paper we present an optimal and a heuristic approach to solve the binding problem which occurs in high-level synthesis of digital systems. The optimal approach is based on an integer linear programming formulation. Given that such an approach is not practical for large problems, we then derive a heuristic from the ILP formulation which produces very good solutions in order of seconds. The heuristic is based on a network flow model and also considers floorplanning during the design process to minimize the interconnection area.

Original language	English
Pages (from-to)	211-225
Number of pages	15
Journal	IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume	2
Issue number	2
DOIs	https://doi.org/10.1109/92.285747
State	Published - Jun 1994

Access to Document

10.1109/92.285747

Cite this

@article{252fa09c91bc43a08222d0935451a5b5,

title = "Optimal and Heuristic Algorithms for Solving the Binding Problem",

abstract = "In this paper we present an optimal and a heuristic approach to solve the binding problem which occurs in high-level synthesis of digital systems. The optimal approach is based on an integer linear programming formulation. Given that such an approach is not practical for large problems, we then derive a heuristic from the ILP formulation which produces very good solutions in order of seconds. The heuristic is based on a network flow model and also considers floorplanning during the design process to minimize the interconnection area.",

author = "Minjoong Rim and Ashutosh Mujumdar and Rajiv Jain and Renato DeLeone",

year = "1994",

month = jun,

doi = "10.1109/92.285747",

language = "English",

volume = "2",

pages = "211--225",

journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",

issn = "1063-8210",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - Optimal and Heuristic Algorithms for Solving the Binding Problem

AU - Rim, Minjoong

AU - Mujumdar, Ashutosh

AU - Jain, Rajiv

AU - DeLeone, Renato

PY - 1994/6

Y1 - 1994/6

N2 - In this paper we present an optimal and a heuristic approach to solve the binding problem which occurs in high-level synthesis of digital systems. The optimal approach is based on an integer linear programming formulation. Given that such an approach is not practical for large problems, we then derive a heuristic from the ILP formulation which produces very good solutions in order of seconds. The heuristic is based on a network flow model and also considers floorplanning during the design process to minimize the interconnection area.

AB - In this paper we present an optimal and a heuristic approach to solve the binding problem which occurs in high-level synthesis of digital systems. The optimal approach is based on an integer linear programming formulation. Given that such an approach is not practical for large problems, we then derive a heuristic from the ILP formulation which produces very good solutions in order of seconds. The heuristic is based on a network flow model and also considers floorplanning during the design process to minimize the interconnection area.

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

U2 - 10.1109/92.285747

DO - 10.1109/92.285747

M3 - Article

AN - SCOPUS:0028452826

SN - 1063-8210

VL - 2

SP - 211

EP - 225

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IS - 2

ER -

Optimal and Heuristic Algorithms for Solving the Binding Problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this