Feed-through river routing

Abstract

We propose a natural extension to river-routing in multiple, parallel channels which faithfully models connections among non-adjacent rows for routability and placement purposes. We devise an efficient algorithm for finding an optimal placement of the components (in the horizontal axis) that yields the minimal area in which routing of all nets is still possible with one layer when the channels' widths are given. Even though this algorithm has quadratic worst-case behaviour, its observed running time is linear. Finding the channels' widths that would achieve minimal area when only the sum of the widths is given has been previously proved to be an NP-complete problem (even for multiple channels without feed-throughs). Thus, we provide a heuristic for finding a"good" set of channels' widths for which the area would be reasonably close to optimal (which works well even when feed-throughs are allowed). We present experimental results. © 1989.