Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/91566
Title: Functional area lower bound and upper bound on multicomponent selection for interval scheduling
Authors: Shen, Zhao Xuan
Jong, Ching Chuen
Keywords: DRNTU::Engineering::Electrical and electronic engineering::Computer hardware, software and systems
Issue Date: 2000
Source: 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.
Series/Report no.: IEEE transactions on computer aided design of integrated circuits and systems
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.
URI: https://hdl.handle.net/10356/91566
http://hdl.handle.net/10220/6314
ISSN: 0278-0070
DOI: 10.1109/43.851990
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.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:EEE Journal Articles

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.