Parallel algorithm for wiring two-terminal nets in the knock-knee mode

In this paper, the problem of stretching a layout in the knock-knee mode is represented while considering its wirability. The previous O(n×m) time serial algorithm for this problem which is bared on two layers needs (2m-1)×n layout area in the worst case, where m=number of rows and n number of columns. However, O(n log n) time serial algorithm that is able to wire all the two-terminal nets within (m×3n/2) layout area is given in the paper. This serial algorithm is applied to generate a parallel CREW PRAM algorithm that can wire all the nets in O(log n) time by using O(n) number of processors