Please use this identifier to cite or link to this item:
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFekete, Sándor P.
dc.contributor.authorKöhler, Ekkehard
dc.contributor.authorTeich, Jürgen
dc.description.abstractWe 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.en
dc.subject.ddc510 Mathematiken
dc.subject.otherfield-programmable gate arraysen
dc.subject.othermore-dimensional packingen
dc.subject.otherprecedence constraintsen
dc.subject.otherexact algorithmsen
dc.subject.otherinterval graphsen
dc.subject.otherpartial ordersen
dc.titleOptimal FPGA Module Placement with Temporal Precedence Constraintsen
dc.typeResearch Paperen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2000, 696en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
tub.subject.msc200068M07 Mathematical problems of computer architectureen
tub.subject.msc200068R10 Graph theoryen
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.