Parallel Algorithms for Channel Routing in the Knock-Knee Model | Zendy

Joseph F. JáJá | Zendy; Shing-Chong Chang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Parallel Algorithms for Channel Routing in the Knock-Knee Model

Author(s) -

Joseph F. JáJá,

Shing-Chong Chang

Publication year - 1991

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0220014

Subject(s) - routing (electronic design automation) , channel (broadcasting) , computer science , algorithm , set (abstract data type) , range (aeronautics) , routing algorithm , parallel computing , computer network , routing protocol , engineering , programming language , aerospace engineering

The channel routing problem of a set of two-terminal nets in the knock-knee model is considered. A new approach to route all the nets within d tracks, where d is the density, such that the corresponding layout can be realized with three layers is developed. The routing and the layer assignment algorithms run in $O(\log n)$ time with $n / \log n$ processors on the CREW PRAM model under the reasonable assumption that all terminals lie in the range $[1,N]$, where $N = O(n)$.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research