Optimization of dynamic hardware reconfigurations

Recent generations of Field Programmable Gate Arrays (FPGA) allow the dynam ic reconfiguration of cells on the chip during run-time. For a given proble m consisting of a set of tasks with computation requirements modeled by rec tangles of cells, several optimization problems such as finding the array o f minimal size to accomplish the tasks within a given time limit are consid ered. Existing approaches based on ILP formulations to solve these problems as multi-dimensional packing problems turn out not to be applicable for pr oblem sizes of interest. Here, a breakthrough is achieved in solving these problems to optimality by using the new notion of packing classes. It allow s a significant reduction of the search space such that problems of the abo ve type may be solved exactly using a special branch-and-bound technique. W e validate the usefulness of our method by providing computational results.