Datapath Scheduling for Behavioral Description with Conditional Branches

Akihisa YAMADA; Toshiki YAMAZAKI; Nagisa ISHIURA; Isao SHIRAKAWA; Takashi KAMBE

Datapath Scheduling for Behavioral Description with Conditional Branches

Akihisa YAMADA, Toshiki YAMAZAKI, Nagisa ISHIURA, Isao SHIRAKAWA, Takashi KAMBE

Full Text Views

0

Share
Cite this

Summary :

A new approach is described for the datapath scheduling of behavioral descriptions containing nested conditional branches of arbitrary structures. This paper first investigates such a complex scheduling mechanism, and formulates an optimal scheduling problem as a 0-1 integer programming problem such that given a prescribed number of control steps, the total cost of functional units can be minimized. In this formulation, each constraint is expressed in the form of a Boolean function, which is set equal to 1 or 0 according as the constraint is satisfied or not, respectively, and a satisfiability problem is defined by the product of the Boolean functions. A procedure is then described, which intends to seek an optimal solution by means of a branch-and-bound method on a binary decision diagram representing the satisfiability problem. Experimental results are also shown, which demonstrate that our approach is of more practical use than the existing methods.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.12 pp.1999-2009

Publication Date: 1994/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category

Cite this

Copy

Akihisa YAMADA, Toshiki YAMAZAKI, Nagisa ISHIURA, Isao SHIRAKAWA, Takashi KAMBE, "Datapath Scheduling for Behavioral Description with Conditional Branches" in IEICE TRANSACTIONS on Fundamentals, vol. E77-A, no. 12, pp. 1999-2009, December 1994, doi: .
Abstract: A new approach is described for the datapath scheduling of behavioral descriptions containing nested conditional branches of arbitrary structures. This paper first investigates such a complex scheduling mechanism, and formulates an optimal scheduling problem as a 0-1 integer programming problem such that given a prescribed number of control steps, the total cost of functional units can be minimized. In this formulation, each constraint is expressed in the form of a Boolean function, which is set equal to 1 or 0 according as the constraint is satisfied or not, respectively, and a satisfiability problem is defined by the product of the Boolean functions. A procedure is then described, which intends to seek an optimal solution by means of a branch-and-bound method on a binary decision diagram representing the satisfiability problem. Experimental results are also shown, which demonstrate that our approach is of more practical use than the existing methods.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e77-a_12_1999/_p

Copy

@ARTICLE{e77-a_12_1999,
author={Akihisa YAMADA, Toshiki YAMAZAKI, Nagisa ISHIURA, Isao SHIRAKAWA, Takashi KAMBE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Datapath Scheduling for Behavioral Description with Conditional Branches},
year={1994},
volume={E77-A},
number={12},
pages={1999-2009},
abstract={A new approach is described for the datapath scheduling of behavioral descriptions containing nested conditional branches of arbitrary structures. This paper first investigates such a complex scheduling mechanism, and formulates an optimal scheduling problem as a 0-1 integer programming problem such that given a prescribed number of control steps, the total cost of functional units can be minimized. In this formulation, each constraint is expressed in the form of a Boolean function, which is set equal to 1 or 0 according as the constraint is satisfied or not, respectively, and a satisfiability problem is defined by the product of the Boolean functions. A procedure is then described, which intends to seek an optimal solution by means of a branch-and-bound method on a binary decision diagram representing the satisfiability problem. Experimental results are also shown, which demonstrate that our approach is of more practical use than the existing methods.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Datapath Scheduling for Behavioral Description with Conditional Branches
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1999
EP - 2009
AU - Akihisa YAMADA
AU - Toshiki YAMAZAKI
AU - Nagisa ISHIURA
AU - Isao SHIRAKAWA
AU - Takashi KAMBE
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1994
AB - A new approach is described for the datapath scheduling of behavioral descriptions containing nested conditional branches of arbitrary structures. This paper first investigates such a complex scheduling mechanism, and formulates an optimal scheduling problem as a 0-1 integer programming problem such that given a prescribed number of control steps, the total cost of functional units can be minimized. In this formulation, each constraint is expressed in the form of a Boolean function, which is set equal to 1 or 0 according as the constraint is satisfied or not, respectively, and a satisfiability problem is defined by the product of the Boolean functions. A procedure is then described, which intends to seek an optimal solution by means of a branch-and-bound method on a binary decision diagram representing the satisfiability problem. Experimental results are also shown, which demonstrate that our approach is of more practical use than the existing methods.
ER -