mirage

Functional area lower bound and upper bound on multicomponent selection for interval scheduling

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

Functional area lower bound and upper bound on multicomponent selection for interval scheduling

Show simple item record

dc.contributor.author Shen, Zhao Xuan
dc.contributor.author Jong, Ching Chuen
dc.date.accessioned 2010-08-17T08:01:24Z
dc.date.available 2010-08-17T08:01:24Z
dc.date.copyright 2000
dc.date.issued 2010-08-17T08:01:24Z
dc.identifier.citation Shen, Z. X., & Jong, C. C. (2000). Functional area lower bound and upper bound on multicomponent selection for interval scheduling. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems. 19(7), 745-759.
dc.identifier.issn 0278-0070
dc.identifier.uri http://hdl.handle.net/10220/6314
dc.description.abstract In a realistic register-transfer-level component library, there usually exist several different hardware implementations for one generic function. This gives rise to a large design space of component selection which is interleaved with the scheduling of operations. Previous methods ignored the presence of multicomponent selection in the process of lower/upper bound estimation of scheduling, and produced the local lower/upper bounds which would cause the suboptimum designs. Opposite to the previous methods, we compute, in this paper, the lower/upper bounds which consider scheduling and component selection simultaneously. A new problem of multicomponent selection integrated with interval scheduling is studied.We present a very interesting and important result that both the lower bound and upper bound of multicomponent selection are obtained on the most cost-effective components which have the minimum area-delay products. This property leads to that the lower bound and upper bound of multicomponent selection can be calculated efficiently. An integer linear programming model and a surrogate relaxation technique are proposed to derive an optimum surrogate lower bound which has the asymptotic performance ratio less than two for a single type of function. An upper bound with the same asymptotic performance ratio is also obtained which turns out to be the optimum solution value of the traditional unicomponent selection with the most cost-effective components. Both the theoretical analysis and the experimental results show that the performance of our bounds are very promising.
dc.format.extent 15 p.
dc.language.iso en
dc.relation.ispartofseries IEEE transactions on computer aided design of integrated circuits and systems
dc.rights © 2000 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. http://www.ieee.org/portal/site This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
dc.subject DRNTU::Engineering::Electrical and electronic engineering::Computer hardware, software and systems
dc.title Functional area lower bound and upper bound on multicomponent selection for interval scheduling
dc.type Journal Article
dc.contributor.school School of Electrical and Electronic Engineering
dc.identifier.doi http://dx.doi.org/10.1109/43.851990
dc.description.version Published version

Files in this item

Files Size Format View
Functional area ... or interval scheduling.pdf 490.5Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Statistics

Total views

All Items Views
Functional area lower bound and upper bound on multicomponent selection for interval scheduling 392

Total downloads

All Bitstreams Views
Functional area lower bound and upper bound on multicomponent selection for interval scheduling.pdf 186

Top country downloads

Country Code Views
Singapore 61
United States of America 52
China 34
Russian Federation 9
Unknown Country 4

Top city downloads

city Views
Singapore 61
Mountain View 43
Beijing 21
Southampton 2
Toronto 2