We consider the optimal placement
of hardware modules in space and time for FPGA architectures
with reconfiguration capabilities, where modules are
three-dimensional boxes, with two dimensions corresponding to
spatial cell requirements on the array and the third one
describing execution time.
Thus, optimal module placement can be modeled as a
three-dimensional packing problem.
A novel graph-theoretic characterization (by so-called "packing classes")
of feasible packings and efficient families of lower bounds
allow a drastic reduction of the search space,
so that it is possible to solve the following problems for a given
set of module tasks to optimality:
(a) Find the minimal execution time of
the given problem on an FPGA of fixed size,
(b) Find the FPGA of minimal size to accomplish the
tasks within a fixed time limit.
Moreover, our approach
allows the treatment of precedence constraints for the sequence
of tasks, which are present in virtually all practical
instances. These additional constraints cause serious problems to
standard combinatorial algorithms.
We show the packing class approach
is perfectly suited for this type of problem.
Additional mathematical structures are developed
that lead to a powerful framework for computing optimal solutions.
The usefulness is validated by computational results.
