NDLI: Hierarchical Channel Router

Content Provider	IEEE Xplore Digital Library
Author	Burstein, M. Pelavin, R.
Copyright Year	1983
Description	Author affiliation: IBM T. J. Watson Research Center, Yorktown Heights, NY (Burstein, M.)
Abstract	The channel routing problem is a special care of the wire routing problem when interconnections have to be performed within a rectangular strip having no obstructions, between terminals located on opposite sides of the rectangle. We present here a new channel routing algorithm, based on reduction of the problem to the case of a (2 x n) grid and on consistent utilization of a "divide and conquer" approach. For the current implementation of the algorithm, the running time is proportional to N x n x log (m), where N is the number of nets, n is the length of the channel (number of columns) and m is the width of the channel (number of tracks). Traditional technological restrictions are assumed, i.e. net terminals are located on vertical grid lines, two wiring layers are available for interconnections - one layer is used exclusively for vertical segments, another for horizontal and vias are introduced for each layer change. This algorithm consistently outperforms several known routers in quality of wiring. We tested the algorithm on several benchmark problems. One of them - Deutsch's "difficult example" - was routed with only 19 horizontal wiring tracks (the absolute minimum for this case), whereas all other known routers required 20 or more tracks.
Starting Page	591
Ending Page	597
File Size	590121
Page Count	7
File Format	PDF
ISBN	0818600268
ISSN	0738100X
DOI	10.1109/DAC.1983.1585714
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1983-06-27
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Wiring Wire Strips Benchmark testing Mercury (metals)
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Hierarchical Dynamic Router

New style for three-layer channel routing

Wire synthesizable global routing for timing closure

A multi-layer router utilizing over-cell areas

BOB-router: A new buffering-aware global router with over-the-block routing resources optimization

Area-optimal three-layer channel routing

MulCh: a multi-layer channel router using one, two, and three layer partitions

An improved bus line channel router

A Generalized Channel Router

Hierarchical Channel Router

Similar Documents

Hierarchical Dynamic Router

New style for three-layer channel routing

Wire synthesizable global routing for timing closure

A multi-layer router utilizing over-cell areas

BOB-router: A new buffering-aware global router with over-the-block routing resources optimization

Area-optimal three-layer channel routing

MulCh: a multi-layer channel router using one, two, and three layer partitions

An improved bus line channel router

A Generalized Channel Router

Hierarchical Channel Router