Temporal floorplanning using the three-dimensional transitive closure subGraph
Journal
ACM Transactions on Design Automation of Electronic Systems
Journal Volume
12
Journal Issue
4
Date Issued
2007
Author(s)
Abstract
Improving logic capacity by time-sharing, dynamically reconfigurable Field Gate Programmable Arrays (FPGAs) are employed to handle designs of high complexity and functionality. In this paper, we use a novel graph-based topological floorplan representation, named 3D-subTCG (3-Dimensional Transitive Closure subGraph), to deal with the 3-dimensional (temporal) floorplanning/placement problem, arising from dynamically reconfigurable FPGAs. The 3D-subTCG uses three transitive closure graphs to model the temporal and spatial relations between modules. We derive the feasibility conditions for the precedence constraints induced by the execution of the dynamically reconfigurable FPGAs. Because the geometric relationship is transparent to the 3D-subTCG and its induced operations (i.e., we can directly detect the relationship between any two tasks from the representation), we can easily detect any violation of the temporal precedence constraints on 3D-subTCG. We also derive important properties of the 3D-subTCG to reduce the solution space and shorten the running time for 3D (temporal) foorplanning/placement. Experimental results show that our 3D-subTCG-based algorithm is very effective and efficient. © 2007 ACM.
Subjects
Partially dynamical reconfiguration; Reconfigurable computing; Temporal floorplanning
Other Subjects
Partially dynamical reconfiguration; Reconfigurable computing; Temporal floorplanning; Array processing; Constraint theory; Gateways (computer networks); Problem solving; Temporal logic; Time sharing systems; Graph theory
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
04.pdf
Size
1.49 MB
Format
Adobe PDF
Checksum
(MD5):a60f500e3e8c51cee0f6d48360bb3385