Optimal FPGA Module Placement with Temporal Precedence Constraints

Sándor P. Fekete, Ekkehard Köhler, and Jürgen Teich

Submitted for publication

field-programmable gate arrays (FPGA's), scheduling, more-dimensional packing, precedence constraints, exact algorithms, interval graphs, partial orders.

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.

Download as [PDF] [ps.gz] [ps.Z] [ps]