Single jog minimum area joining of compacted cells (Q689614)

A popular VLSI design style involves tiling a two-dimensional area with compacted basic cells such that all needed inter cell connections are between pairs of adjacent cells. Furthermore, adjacent cells have the same number of pins on their common boundary and the \(i\)th pins of the two cells are to be connected for all \(i\). This connecting of pin pairs is referred to as cell joining. Adjacent cells may be joined by stretching the cells so that the pairs line up but this will increase the height of the cells. Alternatively, river routing can be used but then the number of tracks used will be increased. The total area occupied by the stretched cells as well as the inter cell routing is defined to be the product of the height and the number of tracks. The connection of a pin pair may contain several jogs which are defined to be the vertical segments of a connection. Jogs decrease the manufacturing yield and reduce the reliability of the circuit and so single jog connection is sometimes preferred. An \(O(n^ 2)\) time algorithm is proposed that computes a single jog joining of a pair of cells using the smallest possible area.