Application of network coding for VLSI routing

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.