This thesis studies the applications of the network coding technique for intercon-
nect optimization and improving the routability of Very-large-scale integration (VLSI)
designs. The goal of the routing process is to connect the required sets of sources
and sinks while minimizing the total wirelength and reducing congestion. Typically,
chip interconnects include multiple sinks and are routed through intermediate nodes.
The main idea of the network coding technique is to enable the intermediate nodes
to generate new signals by combining the signals received over their incoming wires.
This is in contrast to the traditional approaches, in which an intermediate node can
only forward the incoming signals. This thesis attempts to explore the possible ben-
efits of the network coding technique for reducing the total wirelengh and mitigating
congestion in VLSI designs.
The contribution of the thesis is three-fold. First, we extend the Hanan’s theo-
rem for multi-net rectilinear coding networks. Second, we propose several exact and
heuristic solutions for finding near-optimal routing topologies that utilize network
coding techniques. Next, we perform extensive simulation study to evaluate the ad-
vantage of network coding over the traditional approaches. The simulations help to
identify routing instances where the network coding techniques are expected to be
beneficial. Finally, we evaluate the potential benefits from network coding in practical
settings by analyzing its performance on the International Symposium on Physical
Design (ISPD) benchmarks. Our results show that while network coding shows upto 2.43% improvement on
unconstrained rectilinear grids, it shows upto 4.34% improvement in cases with con-
straints along the grid. In addition, it shows an improvement upto 8.4% in cases
involving congestion reduction and also improves routing performance on ISPD rout-
ing benchmarks.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2670 |
| Date | 15 May 2009 |
| Creators | Nemade, Nikhil Pandit |
| Contributors | Sprintson, Alex |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0025 seconds