A New Global Routing Algorithm For FPGAs
4
Citation
6
Reference
10
Related Paper
Keywords:
Routing algorithm
Algorithm design
One area of particular importance is the design of an FPGA routing architecture, which houses the user-programmable switches and wires that are used to interconnect the FPGAs logic resources. Because the routing switches consume significant chip area and introduce propagation delays, the design of the routing architecture greatly influences both the area utilization and speed performance of an FPGA. FPGA routing architectures have already been studied using experimental techniques. This paper describes a stochastic model that facilitates exploration of a wide range of FPGA routing architectures using a theoretical approach. In the stochastic model an FPGA is represented as an N*N array of logic blocks separated by both horizontal and vertical routing channels, similar to a Xilinx FPGA. A circuit to be routed is represented by additional parameters that specify the total number of connections, and each connection's length and trajectory. The stochastic model gives an analytic expression for the routability of the circuit in the FPGA. Practically speaking, routability can be viewed as the likelihood that a circuit can be successfully routed in a given FPGA. The routability predictions from the model are validated by comparing them with the results of a previously published experimental study on FPGA routability.< >
Gate array
Cite
Citations (66)
Centralized control routing algorithm for optical banyan networks on vertical stacking scheme has time complexity O(Nlog 2 N) for rearrangebly nonblocking structure. A distributed algorithm with O(log 2 N) has been recently proposed in which authors have considered an N completely connected processors to take routing decision which practically would be very difficult to implement for large N. In this paper we have proposed a distributed routing algorithm with processors work in pipelined fashion and take the routing decision in linear time. Also they do not need to be completely connected which makes it more practical for implementation.
Banyan
Routing algorithm
Cite
Citations (0)
Channel routing is an important, time-consuming, and difficult problem in VLSI layout design, In this paper, we consider the two-terminal channel routing problem in the new routing model, called times square model (TSM); see, Lodj, Info. Proc. Lett., vol. 35, p. 41, 1990.; where the grid is composed of horizontal tracks, right tracks (with slope +60/spl deg/) and left tracks (with slope -60/spl deg/). We show a new lower bound [2d/3]-1 to the width of channel and present an optimal algorithm for two-terminal channel routing problems, which obtains [2d/3]+2 as an upper bound to the channel width where d is the channel density. The algorithm not only utilizes the horizontal tracks, but also the zig-zag connections, thus achieving the routing optimality.< >
Routing algorithm
Square (algebra)
Cite
Citations (6)
We devise an optimal deterministic algorithm for routing h-relations on-line on an N-input/output multibutterfly. The algorithm, which is obtained by generalizing the circuit-switching techniques of (Arora et al., 1996), routes any h-relation with messages of X bits in O (h(X+log N)) steps in the bit model, and in O(h[X/log N]+log N) communication steps in the word model. Unlike other recently developed algorithms, our algorithm does not need extra levels of expanders, hence minimizes the layout area. Moreover, the network topology does not depend on h.
Routing algorithm
Line (geometry)
Network routing
Cite
Citations (4)
Cite
Citations (0)
A parallel algorithm is proposed for solving the problem of channel and switchbox routing in the design of VLSI chips. The algorithm is suitable for implementation on a shared-memory multiprocessor environment. Our approach does not impose restrictions on the channel type (such as fix or variable channel widths) and the number of available layers. The algorithm contains three major phases: 1) dividing the channel into several regions by selecting some columns, 2) assigning tracks to nets of the selected columns, and 3) assigning tracks to nets of the columns in each region.
Routing algorithm
Cite
Citations (18)
In this paper we analyze the properties of the Xilinx-like regular segmentation schemes for 2-D Field Programmable Gate Arrays (FPGAs). We introduce a new notion of architectural level routing decaying effect caused by wiring segmentation. We discuss its routing properties and propose a relative prime number based segmentation scheme for 2-D FPGA architectures. A new FPGA design concept of applying architectural coupling to achieve better routability is also introduced and experimentally justified.
Cite
Citations (0)
A parallel algorithm for channel routing problems is presented. The problem is to route the given interconnections between two rows of terminals on a multilayer channel where the channel area must be minimized. The current advancement of VLSI chip technology allows one to use four layers composed of two metal layers and two polysilicon layers for routing in a chip. The goal of the proposed parallel algorithm is to find the near-optimum routing solution for the given interconnections in a short time. The algorithm is applied to four-layer channel routing problems requiring n*m*2 processing elements for the n-net-m-track problem. The algorithm has three advantages over the conventional algorithms: (1) it can be easily modified for accommodating more than four-layer problems; (2) it runs both on a sequential machine and on a parallel machine with maximally n*m*2 processors; and (3) the program size is very small. The algorithm is verified by solving seven bench-mark problems.< >
Routing algorithm
Cite
Citations (35)
A two-stage channel routing technique for CMOS gate arrays is proposed. In the first stage, certain nets are routed on two sides of the channel so that channel density is reduced. A single-side O(N) optimum algorithm is presented for this stage. The algorithm can choose one set with maximum weight from among the possible sets of routing nets. The second stage can be general channel routing. An efficient algorithm for one-and-a-half-layer routing model that is based on one metal mask and a fixed poly-crossunder layer is presented. This router scans the channel in a left-to-right, zone-by-zone manner, using a multilevel prediction to guide wiring and a greedy approach for nets to contend for limited crossunders. Implementation results are provided to indicate the efficiency of the technique.< >
Routing algorithm
Cite
Citations (3)
Unlike ASICs, FPGAs have routing fabrics that are pre-manufactured. And because of this prefabrication, FPGAs hardly can achieve high clock frequencies which offered by ASICs. Thus, there is a need for better FPGA timing performance. And design automation or computer-aided design (CAD) tools for field programmable gate arrays (FPGAs) have played a very critical role over the past decades for FPGA design. This mini survey presents the up-to-date overview of placement and routing algorithm for FPGA devices with an emphasis on the recent research from 2008.
Electronic design automation
Application-specific integrated circuit
FPGA prototype
Programmable Array Logic
Reconfigurable Computing
Prefabrication
Place and route
Cite
Citations (0)