MARCO GSRC Calibrating Achievable Design: Bookshelf

[3D-ADOpt] TPR: Three-dimensional Place and Route for 3D FPGAs

Cristinel Ababei, Hushrav Mogal, Pongstorn Maidee, Kia Bazargan

Last updated: Sun June 20, 2004

Introduction

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.

Source code and executables

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).

Command-line options

See the manual, which is included in the gzip file above.

Data formats and benchmarks

Data formats are very similar to those used with VPR; some very intuitive changes were made to "accommodate" the third dimension, z. Benchmarks are the same, which come with VPR package. The architecture file, also needed as an input file to TPR , follows the format of VPR, and has additional changes for the vertical dimension.

Features and limitations

The placement algorithm is partitioning-based, and hence scalable with the design size. We use the state-of-the-art partitioner hMetis. We also extended to 3D the simulated annealing placement algorithm of VPR to achieve better solution quality at the expense of longer run-times.
Various techniques for path-based timing optimization are integrated.
The placement engine is fast and can be used for quick architectural evaluations without going through the time-consuming routing process because it shows good fidelity between placement estimations and actual values after detailed routing.
The 3D detailed routing engine is breadth-first-search (PathFinder) based.

Currently TPR does not have a GUI. It's pending.
The routing algorithm is wire-length (WL) driven rather than timing driven.

Performance results

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.

Documentation and support

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:

C. Ababei, H. Mogal, and K. Bazargan, "Three-dimensional Place and Route for FPGAs", Asia South-Pacific Design Automation Conference (ASPDAC), 2005.
C. Ababei, P. Maidee, and K. Bazargan, "Exploring Potential Benefits for 3D FPGA Integration", Field Programmable Logic and its Applications (FPL), 2004.

Technical Report at UMN, Electrical and Computer Engineering Department:

Documentation and support

This work is supported in part by a DARPA grant as part of our 3D-ADOpt project.

Related Tools from Kia Bazargan's Group

Check Kia Bazargan's downloads page.

Link to the Bookshelf FPGA Layout Slot

kia@ece.umn.edu