Parallel channel routing
18
Citation
13
Reference
20
Related Paper
Citation Trend
Abstract:
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.Keywords:
Routing algorithm
A tool for switch-box routing that can route regions with cyclic constraints and with terminals on three or four sides is presented. A divide-and-conquer algorithm is used to explore the greedy channel routing idea, using techniques such as routing area partitioning, dynamic routing strategies, and sweeping concurrent bidirectional columns. The routing area is decomposed into three parts by two special lines cut parallel, making routing easier. The algorithm completely routes Burstein's switch-box problem and with an extension also routes the Deutsch channel example in 19 tracks.< >
Routing algorithm
Equal-cost multi-path routing
Cite
Citations (2)
The problem of interchanging the terminals on the cells at the sides of a channel in order to obtain new channels that can be routed more efficiently is considered. A linear-time algorithm that detects whether there exists an interchange of the terminals that produces a river routable problem is given, and O(n/sup 2/) algorithm that finds a terminal permutation that guarantees that the density of the channel routing problem is minimal over all possible permutations is presented.< >
Routing algorithm
Cite
Citations (7)
Numerous solutions to the problem of detailed routing of wires on a chip have been proposed for two routing layers but few are general enough to also handle switchboxes, more than two layers, variable channel widths, or multiple-layer problems with stacked terminals (3-D routing) without extensive modifications. We propose a different routing approach that not only can solve the two layer problem but the other problems as well. The inherent parallelism of the approach lead to a coarse-grained parallel algorithm.
Multipath routing
Cite
Citations (19)
This paper presents a new parallel-processing architecture for hardware routers based on the Lee algorithm. Unlike the existing machines, which require N/sup 2/ processors to implement the Lee algorithm on an N x N grid plane, the proposed architecture requires only O(N) processors to find a path in O(N) time. A prototype machine with 64 processors has been developed to deal with a 128 x 128 grid plane. The architecture of the machine is discussed, together with its experimental performance data. Further, it is reported that the parallel-processed Lee algorithm is most useful and powerful when applied to interactive rip-up and reroute.
Forwarding plane
Cite
Citations (42)
A near-optimal algorithm for the channel pin assignment problem is presented. This algorithm, called the alternative packing algorithm, can always produce an assignment solution whose density is at most one more than the density of an optimal solution, i.e., d(S)>
Benchmark (surveying)
Routing algorithm
Cite
Citations (7)
Obtaining small chip size is always an important goal in the automatic layout design of VLSI circuits. The advantages of using the routing area over the cells for interconnections to further reduce the channel width for the layout with standard cell design style is discussed. An efficient iterative algorithm for over-the-cell channel routing is presented. The execution speed of the router is significantly greater than that of previously reported units.< >
Standard cell
Integrated circuit layout
Cite
Citations (0)
This paper presents an algorithm to route multiple nets for VLSI layout synthesis in the presence of irregular rectilinear obstacles. The proposed routing algorithms are to be used when layout is nearly finished. Any incremental routing for performance needs to be done by using the very limited space between existing layout cells or by routing directly over the cells. Each net has multiple pins, which are located either on the boundary or anywhere inside the layout region. The proposed algorithm is very systematic and easy to implement. It does not require any net sequencing, and through extensive experiments on real circuits has been shown to always produce near optimal solutions.< >
Net (polyhedron)
Integrated circuit layout
Cite
Citations (1)
In this paper, we study the over-the-cell channel routing problem for the cell model in which all the pins are positioned along a horizontal line inside the corresponding cell. We present an efficient approach to the problem under the assumption that two metal layers are available for routing in each of the two over-the-cell regions and three metal layers are available for routing in the channel. The idea of our approach is to treat the three routing regions as a two-layer expanded channel, and to generate a two-layer channel routing solution first. The solution is then transformed into the final over-the-cell channel routing solution with the objective of minimizing the resulting width of the original channel. The transformation problem is reduced to the constrained two-processor scheduling problem for which we develop a polynomial time optimal algorithm. Our approach has been implemented in C language, and experimental results are also provided to support it.
Equal-cost multi-path routing
Multipath routing
Cite
Citations (0)
Routing algorithm
Placement
Integrated circuit layout
Cite
Citations (4)
Routing is one of the time-consuming processes in LSI design to connect previously placed terminals. In this study, we propose a multithreaded parallel routing algorithm for LSI design. In the proposed method, first, threads are created and the nets of the target net list are equally distributed to the threads. Sharing the routing regions, each of the threads searches a candidate path of a net in parallel without synchronization. Then, each thread exclusively writes a candidate path to the routing regions as a determined path. Although the exclusive control is necessary when updating the routing regions, this asynchronous parallel routing reduces the wait time of the threads. If a candidate path of a net does not satisfy constraints due to the asynchronous parallel routing, the net is re-routed. We experimentally confirmed that our proposed method running on a PC with eight cores was 7.1 times faster than the sequential execution. In addition, we also confirmed that the routing quality was not degraded compared to the sequential execution.
Equal-cost multi-path routing
Multipath routing
Path vector protocol
Policy-based routing
Cite
Citations (6)