direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 696-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Optimal FPGA Module Placement with Temporal Precedence Constraints
Submitted for publication
primary: 68M07 Mathematical problems of computer architecture
secondary: 68R10 Graph theory
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe