Due to the advancements in fabrication technology, the devices and interconnection wires are placed in closer proximity, and the circuits operate at higher frequencies. This results in crosstalk between wire segments. Work on routing channels with reduced crosstalk is a very important area of current research (Gao and Liu, 1993; and Pal, 2000). We know that the crosstalk minimization problem in the reserved two-layer Manhattan routing model is NP-complete, even for the channels without any vertical constraints (Pal et al., 2007). Since minimizing crosstalk is NP-complete, several polynomial time heuristic algorithms for reducing crosstalk have been developed (Pal et al., 2002, 2004 and 2006; and Singha et al., 2002). All the ideas that are introduced as heuristics are basically sequential in nature. This paper, develops two efficient parallel heuristic algorithms for computing reduced crosstalk routing solutions. The heuristics proposed in this paper are much better in computational complexity than the existing sequential versions of the algorithms developed previously (Pal et al., 2002 and 2006; and Singha et al., 2002).
Channel routing problem, Crosstalk minimization, NP-hardness, Simplest channel instance, High performance routing, Parallel heuristic algorithm
In Very Large Scale Integration (VLSI) layout design, it is required to realize a specified interconnection among different modules, using minimum possible area. This is known as the routing problem. There exist several routing strategies for efficient interconnection among different modules. One of the most important types of routing strategies is `channel routing' (Yoshimura and Kuh, 1982; and Pal, 2000). A channel is a rectangular region that has two open ends on the two opposite sides, and the other two sides have two rows of fixed terminals. A set of terminals that need to be electrically connected together is called a `net'. The terminals of the same net are assigned the same number. The unconnected terminals are assigned the number zero. |
