NDLI: Parallel VLSI-routing models for polymorphic processors array

Content Provider	IEEE Xplore Digital Library
Author	Mazumder, P.
Copyright Year	1997
Description	Author affiliation: Dept. of Electr. Eng. & Comput. Sci., Michigan Univ., Ann Arbor, MI, USA (Mazumder, P.)
Abstract	This paper explores various parallel processing methods for concurrent multi-layer VLSI-routing. One approach is based on efficient execution of the maze routing algorithm on custom processing elements arranged in the form of a hexagonal array. The key features here are the mapping policy and the acceleration of three-dimensional search operations. Subsequently, parallel algorithms over a reconfigurable SIMD array is discussed to handle a wider range of routing applications. A routing framework is discussed that consolidates many of the existing specialized algorithms such as channel, switch-box and maze routers into one muting system. The concept of a total grid-graph is used to capture the state of the routing region and propose new and efficient parallel algorithms for cycle detection cycle elimination, and tree reduction on such graphs. The proposed algorithms scale well with increased problem sizes since they require only O (log(N)) time given a N/sup 2/-node grid-graph. Based on these algorithms, the paper develops two types of generalized detailed routers, each capable of finding paths concurrently spanning multiple layers. The first, called a parallel chord router, has the ability to compute various "useful" route patterns in close to constant time; the second is an adaptation of maze routing capable of simultaneously expanding from multiple pins. In addition, a parallel hill-climbing algorithm is discussed that can be used to improve a given route, if possible, by iteratively identifying and rewiring bends in the route.
Starting Page	10
Ending Page	14
File Size	656868
Page Count	5
File Format	PDF
ISBN	0818677554
ISSN	10639667
DOI	10.1109/ICVD.1997.567953
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1997-01-04
Publisher Place	India
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Very large scale integration Wiring Parallel processing Acceleration Parallel algorithms Tree graphs Concurrent computing Pins Iterative algorithms
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Hardware and Architecture

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