An Efficient and Fast Algorithm for Routing Over the Cells | Zendy

Kuo-En Chang | Zendy; Sei-Wang Chen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Efficient and Fast Algorithm for Routing Over the Cells

Author(s) -

Kuo-En Chang,

Sei-Wang Chen

Publication year - 1994

Publication title -

vlsi design

Language(s) - English

Resource type - Journals

eISSN - 1065-514X

pISSN - 1026-7123

DOI - 10.1155/1996/96136

Subject(s) - intersection (aeronautics) , computer science , algorithm , routing (electronic design automation) , scheme (mathematics) , destination sequenced distance vector routing , graph , set (abstract data type) , channel (broadcasting) , routing algorithm , representation (politics) , theoretical computer science , link state routing protocol , mathematics , routing protocol , computer network , engineering , mathematical analysis , programming language , politics , law , political science , aerospace engineering

A linear time algorithm for routing over the cells is presented. The algorithm tries to reducemaximum channel density by routing some connections over the cells. The algorithm firstdefines a new scheme for channel representation and formulates the problem based on anintersection graph derived from the new scheme. Then, a feasible independent set of theintersection graph is found for routing some subnets over the cells. The algorithm is implementedand evaluated with several well known benchmarks. In comparison with previousresearch, our results are satisfactory, and the algorithm takes substantially less CPU timethan those of previous works. For Deutsch's difficult example, the previous algorithms takeabout 29.25 seconds on an average but our new algorithm needs only 5.6 seconds

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