NDLI: MaizeRouter: Engineering an effective global router

Content Provider	IEEE Xplore Digital Library
Author	Moffitt, M.D.
Copyright Year	2008
Description	Author affiliation: IBM Austin Res. Lab., Austin (Moffitt, M.D.)
Abstract	In this paper, we present MaizeRouter, winner of the inaugural Global Routing Contest hosted at ISPD 2007. MaizeRouter reflects a significant leap in progress over existing publicly-available routing tools, and abandons popular algorithms such as multicommodity flow-based techniques, ILP formulations, and congestion-driven Steiner tree generation. Instead, the foundation of our algorithm draws upon simple yet powerful edge-based operations, including extreme edge shifting, a technique aimed primarily at the efficient reduction of routing congestion, and edge retraction, a counterpart to extreme edge shifting that serves to reduce unnecessary wirelength. These algorithmic contributions are built upon a framework of interdependent net decomposition, a representation that improves upon traditional two-pin net decomposition by preventing duplication of routing resources while enabling cheap and incremental topological reconstruction. A maintenance mechanism, named garbage collection, is introduced to eliminate leftover routing segments. Collectively, these operations permit a broad search space that previous algorithms have been unable to achieve, resulting in solutions of considerably higher quality than those of well-established routers.
Starting Page	226
Ending Page	231
File Size	204841
Page Count	6
File Format	PDF
ISBN	9781424419210
DOI	10.1109/ASPDAC.2008.4483946
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-03-21
Publisher Place	South Korea
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Engines Algorithm design and analysis Topology Runtime Costs Statistics Very large scale integration Electronic design automation and methodology Data structures
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

MaizeRouter: Engineering an Effective Global Router

An Industrial World Channel Router for Non-Rectangular Channels

Fast Congestion Aware Routing for Pin Assignment

PHIroute: A parallel hierarchical sea-of-gates router

A heuristic global router for polycell layout

Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement

A parallel router based on load-balanced region partition strategy

High-performance routing at the nanometer scale

MaizeRouter: engineering an effective global router

MaizeRouter: Engineering an effective global router

Similar Documents

MaizeRouter: Engineering an Effective Global Router

An Industrial World Channel Router for Non-Rectangular Channels

Fast Congestion Aware Routing for Pin Assignment

PHIroute: A parallel hierarchical sea-of-gates router

A heuristic global router for polycell layout

Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement

A parallel router based on load-balanced region partition strategy

High-performance routing at the nanometer scale

MaizeRouter: engineering an effective global router

MaizeRouter: Engineering an effective global router