M.Sc Thesis | |

M.Sc Student | Emanuel Ben |
---|---|

Subject | On VLSI Interconnects Sizing and Ordering Problems |

Department | Department of Applied Mathematics |

Supervisors | PROFESSOR EMERITUS Gershon Wolansky |

ASSOCIATE PROF. Shmuel Wimer |

This thesis considers some VLSI interconnects sizing and ordering problems occurring in VLSI chip design. The first topic discussing design implementation of interconnect in the VLSI design flow, a task known also as routing. We will present the interconnection problem in a generalized approach where the two aspects of routing, namely the wiring patterns and their widths are simultaneously optimized to yield minimum Power Delay Product interconnect. The simultaneous handling of routing pattern and sizing is obtained by employing recent network flow results using simulated annealing scheme.

The second topic
presents several optimization problems occurring in VLSI interconnect, Networks
on Chip (NoC) design and 3D VLSI integration, all possessing closed-form
solutions obtained by well-solvable Quadratic Assignment Problems (QAP). The
first type of problems deals with the optimal ordering of signals in a bus
bundle such that the switching power, delay and noise interference are
minimized. We extend a known solution of ordering the signals in a bus bundle
to minimize the impact of the 1^{st} order wire-to-wire parasitic
capacitance occurring between adjacent wires into a model accounting also
secondary components of wire-to-wire parasitic capacitances. The second type of
problems arises in the mapping of computation tasks into array of processors
sharing a common bus, such as those found in NoC. We show a QAP closed-form
solution to the optimal mapping problem which simultaneously minimizes the
switching power and the average delay of the bus. The third problem deals with
the optimization of 3D VLSI, vertically stacking ordinary ICs. Some of the
above problems involve -distance Traveling
Salesman Problem (TSP), where costs are evaluated for elements located at -distance apart along the tour.
We show a simple proof that these are well-solvable problems and obtain their
solution. This is then generalized to well-solvable QAPs obtained by
superposition of such TSPs. A simple proof shows that if -distance TSPs are well-solvable,
so is the QAP obtained by their sum, where the solution of -distance TSPs dominates all the
others.