Ph.D Student | Artishchev-Zapolotsk Maria |
---|---|

Subject | Compact Layouts for Some Interconnection Networks |

Department | Department of Computer Science |

Supervisors | Mr. Yefim Dinitz |

Professor Emeritus Shimon Even (Deceased) | |

Professor Ami Litman | |

Full Thesis text |

We present some compact layouts of interconnection networks and their components to a grid. The main optimization parameter is the layout area. Besides, the number of the wire bends and component scalability are also studied and improved.

We use *Thompson*
layout model. We allow *knock-knees* (sharing a grid point by two bending
wires), but make a maximum effort to eliminate them.

We consider
first the *Butterfly* network with *N* * ^{ }*inputs and

In the above
layout, we use a wiring of *N* two-point nets in a *channel* of a
triangle shape, where the inputs lie on a triangle leg, and the outputs on the
second leg. Our layout uses a specific *permutation*: reordering of
outputs w.r.t. inputs. We further extend the study to wiring a *general*
permutation in a triangle area. We show two layouts in an optimal area of ½*N*^{2}
+ o(*N*^{2}), with O(*N*) bends each. We prove that the first
layout requires the absolutely minimum area and yields the irreducible number
of bends, while containing knock-knees. The second one eliminates knock-knees,
while keeping the above bounds. We prove a lower bound of 3N - o(*N*) for
the number of bends in the worst case, for any layout in an optimal area of ½*N*^{2}
+ o(*N*^{2}).

Another study of
channel routing is for a rectangle-shaped channel, where the inputs and outputs
lie on opposite sides of this rectangle. We study the algorithm of
Muthukrishnan *et al*. (with knock-knees). In their paper, the algorithm
had a substantial gap, and was analyzed not precisely. We complete the
algorithm and correct its analysis. Besides, we suggest another algorithm
solving the same problem, which modifies techniques of Pinter. It is simpler
and needs less bends.

Another interconnection network dealt
in this work is the *Odd-Even sorting* *network*. Its *N* input
and *N* output terminals lie on opposite sides of the encompassing
rectangle. We show two layouts improving the previously best result suggesting
area of 3*N*^{2}. The first one obtains the area of 2*N*^{2},
but contains knock-knees. The second one eliminates knock-knees, suggesting the
area of 2⅓*N*^{2}.