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

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.