UWEE Tech Report Series

Track Placement: Orchestrating Routing Structures to Maximize Routability


UWEETR-2002-0013

Author(s):
Katherine Compton, Scott Hauck

Keywords:
FPGAs,routing architecture,routing channel,segmented routing

Abstract

The design of a routing channel for an FPGA is a complex process, requiring the careful balance of flexibility with silicon efficiency. With the growing move towards embedding FPGAs into SoC designs, and the opportunity to automatically generate FPGA architectures, this problem becomes even more critical. The design of a routing channel requires determining the number of routing tracks, the length of the wires in those tracks, and the positioning of the breaks on the tracks. This paper focuses on the last of these problems, the placement of breaks in tracks to maximize overall flexibility. We have developed both an optimal algorithm and a number of heuristics to solve the track placement problem. The optimal algorithm finds a best solution provided the problem meets a number of restrictions. Most of the heuristics are without restrictions, and the most promising of these find solutions on average within 1.13% of optimal.

Download the PDF version

Download the Gzipped Postscript version