×

Optimization of dynamic hardware reconfigurations. (English) Zbl 0988.68022

Summary: Recent generations of field programmable gate arrays allow the dynamic reconfiguration of cells on the chip during run-time. For a given problems consisting of a set of tasks with computation requirements modeled by rectangles of cells, several optimization problems such as finding the array of minimal size to accomplish the tasks within a given time limit are considered. Existing approaches based on ILP formulations to solve these problems as multidimensional packing problems turn out not to be applicable for problem sizes of interest. Here, a breakthrough is achieved in solving these problems to optimality by using the new notion of packing classes. It allows a significant reduction of the search space such that problems of the above type may be solved exactly using a special branch-and-bound technique. We validate the usefulness of our method by providing computational results.

MSC:

68M99 Computer system organization
PDFBibTeX XMLCite
Full Text: DOI