Ph.D Thesis

Ph.D StudentArtishchev-Zapolotsk Maria
SubjectCompact Layouts for Some Interconnection Networks
DepartmentDepartment of Computer Science
Supervisors MR Yefim Dinitz
PROFESSOR EMERITUS Shimon Even (Deceased)
Full Thesis textFull thesis text - English Version


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 N outputs. In our layout, the input/output terminals are located inside the layout  area. The area is ½N2 + o(N2), which improves by factor of 2 on the previously best result. The layout is knock-knee free. We prove a matching lower bound for the rectangular area required for the Butterfly layout: ½N2 - o(N2).

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 ½N2 + o(N2), 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 ½N2 + o(N2).

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 3N2. The first one obtains the area of 2N2, but contains knock-knees. The second one eliminates knock-knees, suggesting the area of 2⅓N2.