NDLI: Efficient VLSI layouts for homogeneous product networks

Content Provider	IEEE Xplore Digital Library
Author	Fernandez, A. Efe, K.
Copyright Year	1968
Abstract	In this paper, we develop generalized methods to layout homogeneous product networks with any number of dimensions, and analyze their VLSI complexity by deriving upper and lower bounds on the area and maximum wire length. In the literature, lower bounds are generally obtained by computing lower bounds on the bisection width or the crossing number of the network being laid out. In this paper, we define a new measure that we call "maximal congestion", that can be used to obtain both the bisection width and the crossing number, thereby unifying the two approaches. Upper bounds are traditionally obtained by constructing layouts based on separators or bifurcators. Both methods have the basic limitation that they are applicable only for graphs with bounded vertex degree. The separators approach generally yields good layouts when good separators can be found, but it is difficult to find a good separator for an arbitrary graph. The bifurcators approach is easier to apply, but it generally yields larger area and wire lengths. We show how to obtain "strong separators" as well as bifurcators for any homogeneous product network, as long as the factor graph has bounded vertex degree. We illustrate application of both methods to layout a number of interesting product networks. Furthermore, we introduce a new layout method for product networks based on the combination of collinear layouts. This method is more powerful than the two methods above because it is applicable even when the factor graph has unbounded vertex degree. It also yields smaller area than the earlier methods. In fact, our method has led to the optimal area for all of the homogeneous product networks we considered in this paper with one exception, which is very close to optimal. In regards to wire lengths, the results obtained by our method turned out to be the best of the three methods for all the examples we considered, again subject to one (and the same) exception. We give an extensive variety of such examples.
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	1070
Ending Page	1082
Page Count	13
File Size	337078
File Format	PDF
ISSN	00189340
Volume Number	46
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1997-10-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Very large scale integration Particle separators Bifurcation Wire Multiprocessor interconnection networks Routing Hypercubes Partitioning algorithms Computer networks Upper bound
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software 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

Generalized algorithm for parallel sorting on product networks

Area-efficient VLSI layouts for binary hypercubes

Tighter layouts of the cube-connected cycles

K-pairwise cluster fault tolerant routing in hypercubes

The extended cube connected cycles: an efficient interconnection for massively parallel systems

Unicast in hypercubes with large number of faulty nodes

Efficient network folding techniques for routing permutations in VLSI

VLSI considerations for TESH: a new hierarchical interconnection network for 3-D integration

Resource sharing interconnection networks in multiprocessors

Efficient VLSI layouts for homogeneous product networks

Similar Documents

Generalized algorithm for parallel sorting on product networks

Area-efficient VLSI layouts for binary hypercubes

Tighter layouts of the cube-connected cycles

K-pairwise cluster fault tolerant routing in hypercubes

The extended cube connected cycles: an efficient interconnection for massively parallel systems

Unicast in hypercubes with large number of faulty nodes

Efficient network folding techniques for routing permutations in VLSI

VLSI considerations for TESH: a new hierarchical interconnection network for 3-D integration

Resource sharing interconnection networks in multiprocessors

Efficient VLSI layouts for homogeneous product networks