TPR: Three-dimensional Place and Route for 3D FPGAs
| Cristinel Ababei, Hushrav Mogal, Pongstorn Maidee, Kia Bazargan|
Last updated: Sun June 20, 2004
TPR is a fast placement and detailed routing tool for array-based 3D FPGAs. A circuit is first partitioned for min-cut minimization into a number of blocks equal to the number of layers for the 3D integration. Then, timing-driven partitioning-based placement is performed on every layer starting with the top layer and proceeding towards the bottom layer. The allowable bounding box for nets on a particular layer is decided by the layers above it, in order to minimize the 3D bounding-boxes of the most critical nets. Constraints for any given layer are set by the placement on layers above. The philosophy of our tool closely follows that of its 2D counterpart, the leading academic placement and routing tool for 2D architectures, VPR. In fact, most of the code related to parsing the input files as well as the 2D FPGA architecture and routing definitions is imported and adapted from VPR. The routing algorithm was imported and adapted for the 3D architecture as well.
Purpose of TPR is to serve the research community in predicting and exploring potential gains that 3D technologies for FPGAs can offer (similar to the role VPR played in the development of FPGA physical design algorithms). It shall be used as a platform, which can be used for further development and implementation of new ideas in placement and routing for 3D FPGAs.
Make sure that you read and agree to the terms outlined here before you download.
Complete source code for TPR along with a preliminary Java GUI is availabe. TPR's code was written in C++ (though, it still preserves much of the VPR's C flavor), Red Hat Linux 9.0.
Source and executables are provided for Linux. Download tpr5_pargui.tar.gz (executable, manual, benchmark-circuits, architecture-files).
See the manual, which is included in the gzip file above.
On average, total decrease of 25% in wire-length and 30% (35%) in delay respectively, can be achieved over traditional 2D chips, when using an FPGA architecture with single-length vertical vias (multiple-length vertical vias) and using nine layers in 3D integration. Horizontal channel width decreases with the number of layers up to 33% when using nine layers, whereas the total routing area stays between 0.96÷1.1 of the total routing area corresponding to 2D case. Run-times of 3D SA-based placement are about twice the run-times of detailed routing and about an order of magnitude longer than run-times of 3D partitioning-based placement.
See paper(s) and technical report for more details and discussions.
Downloadable executables and code come with a short manual (also, good familiarity with VPR is assumed). There is no known problem with the installation and use of TPR. If you encounter any difficulty please let us know by e-mail.
Algorithms used in TPR are described in the following publications:
Technical Report at UMN, Electrical and Computer Engineering Department:
Check Kia Bazargan's downloads page.