Compile-time Optimization of Dynamic Hardware Reconfigurations.
Jürgen Teich, Sándor P. Fekete, Jörg Schepers · 1999
Recent generations of Field Programmable Gate Arrays (FPGA) allow the dynamic reconfiguration of cells on the chip during run-time. For a given problem 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 being related to multi-dimensional 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 a new notion of packing classes that allows a significant reduction of the search space such that above problems may be solved exactly using a special branchand -bound technique. We validate the usefulness of our method by providing computational results. Keywords: reconfigurable hardware, multidimensional placement and packing 1 Introduction Field-...