Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Optimal FPGA Module Placement with Temporal Precedence Constraints
Author(s): Fekete, Sándor P.
Köhler, Ekkehard
Teich, Jürgen
Type: Research Paper
Abstract: 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.
Subject(s): field-programmable gate arrays
more-dimensional packing
precedence constraints
exact algorithms
interval graphs
partial orders
Issue Date: 2000
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 68M07 Mathematical problems of computer architecture
68R10 Graph theory
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2000, 696
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 488.21 kB
DownloadShow Preview
Format: Unknown | Size: 115.81 kB
Format: Postscript | Size: 2.56 MB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.