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

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.