Zx. Shen et Cc. Jong, Functional area lower bound and upper bound on multicomponent selection for interval scheduling, IEEE COMP A, 19(7), 2000, pp. 745-759
Citations number
21
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
In a realistic register-transfer-level component library, there usually exi
st several different hardware implementations for one generic function. Thi
s gives rise to a large design space of component selection which is interl
eaved with the scheduling of operations. Previous methods ignored the prese
nce of multicomponent selection in the process of lower/upper bound estimat
ion of scheduling, and produced the local lower/upper bounds which would ca
use the suboptimum designs,
Opposite to the previous methods, we compute, in this paper, the lower/uppe
r bounds which consider scheduling and component selection simultaneously.
A new problem of multicomponent selection integrated with interval scheduli
ng is studied, We present a very interesting and important result that both
the lower bound and upper bound of multicomponent selection are obtained o
n the most cost-effective components which have the minimum area-delay prod
ucts. This property leads to that the lower bound and upper bound of multic
omponent selection can be calculated efficiently. An integer linear program
ming model and a surrogate relaxation technique are proposed to derive an o
ptimum surrogate lower bound which has the asymptotic performance ratio les
s than two for a single type of function. An upper bound with the same asym
ptotic performance ratio is also obtained which turns out to be the optimum
solution value of the traditional unicomponent selection with the most cos
t-effective components. Both the theoretical analysis and the experimental
results show that the performance of our bounds are very promising.