Shlomit S. Pinter, Ron Y. Pinter
ACM Transactions on Programming Languages and Systems (TOPLAS)
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.
Shlomit S. Pinter, Ron Y. Pinter
ACM Transactions on Programming Languages and Systems (TOPLAS)
Shiomit S. Pinter, Ron Y. Pinter
POPL 1991
Nissim Francez, Shalom Goldenberg, et al.
ACM SIGPLAN Notices
Reuven Bar-Yehuda, Jack A. Feldman, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems