IEICE TRANSACTIONS on Fundamentals
Datapath Scheduling for Behavioral Description with Conditional Branches
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
