Go to  Advanced Search

CAD algorithms and performance of Malibu : an FPGA with time-multiplexed coarse-grained elements

Show full item record

Files in this item

Files Size Format Description   View
ubc_2011_fall_grant_david.pdf 2.777Mb Adobe Portable Document Format Thesis   View/Open
Title: CAD algorithms and performance of Malibu : an FPGA with time-multiplexed coarse-grained elements
Author: Grant, David
Degree: Doctor of Philosophy - PhD
Program: Electrical and Computer Engineering
Copyright Date: 2011
Issue Date: 2011-09-07
Publisher University of British Columbia
Abstract: Modern Field-Programmable Gate Arrays (FPGAs) are used to implement a wide range of ever-larger circuits, many of which have both coarse-grained and fine-grained components. Past research into coarse-grained FPGAs optimized for such circuits have only demonstrated a 10% density advantage. In contrast, time-multiplexing of fine-grained FPGAs has demonstrated a 14x density improvement. This leaves an open question whether a time-multiplexed, coarse-grained FPGA can provide a similar density advantage. Even more important is whether the coarse-grained circuit structure can be exploited by Computer-Aided Design (CAD) tools to significantly reduce compile times. This thesis investigates a new type of FPGA in which coarse-grained, time-multiplexed resources are added to a traditional FPGA. Through time-multiplexing, density and compile time are improved. By retaining fine-grained logic and routing resources, performance does not suffer as much as in past attempts. This thesis also presents two CAD flows, M-CAD and M-HOT, to compile Verilog for this new FPGA. Both flows speed up compile times by more than 10x, which has not been demonstrated with any other flow (even flows that sacrifice quality). They can also achieve a circuit density greater than modern FPGAs, and can trade density for performance, something most FPGA CAD flows cannot do. At maximum density, M-HOT flow achieves a 26.1x compile time speedup, 2.5x the density, and 0.5x the performance of a commercial FPGA and CAD tool. At maximum performance, M-HOT achieves 1.0x density, and 0.7x performance. In contrast, M-CAD is a bit faster than M-HOT but achieves a lower quality result. In M-CAD, there are situations where the placer needs temporal information from the scheduler to make good decisions. Instead, M-HOT divides the circuit into heights to keep the integrated placement, routing, and scheduling problem tractable, but compile time suffers if there are too few heights. Although we show there is at most a theoretical 1.6x or 2.0x clock frequency improvement still remaining in M-HOT or M-CAD, respectively, the amount achievable may be far less. Future work should focus on improving the front-end synthesis, the coarse/fine-grained interface, and the coarse/fine-grained partitioning to provide higher quality input to the back-end CAD flow.
Affiliation: Applied Science, Faculty of
URI: http://hdl.handle.net/2429/37150
Scholarly Level: Graduate

This item appears in the following Collection(s)

Show full item record

Attribution-NonCommercial 2.5 Canada Except where otherwise noted, this item's license is described as Attribution-NonCommercial 2.5 Canada

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893