A Revisit to YACRIT: Yet Another Channel Router with Interchangeable Terminals

Abstract

This paper presents new algorithms for routing two rows of interchangeable terminals across a two-layer channel. In this case, the number of horizontal tracks required for routing is reduced significantly by simply interchanging the terminals in each cell. It has been found that on the average approximately 40% channel area or often more is saved just by interchanging the terminals. In practice, actually, on the design table of forming the final net list from a net list just given in the form of rows of terminals necessary for routing, or partially constructed channel instances are given for rearranging their terminals so that area required for routing is minimized. The number of horizontal tracks per net is assumed to be one, i.e., no-dogleg routing is performed, and subsequently with the help of each of the algorithms developed in this paper at least one feasible solution is always computed without doglegging. A generalized study is also encountered considering existence of more than two cells on a side of the given channel where cells are fixed at their relative positions though the terminals within a cell are interchangeable; intercell interchanges of terminals are not allowed.