Browse Prior Art Database

ON THE PARTITIONING OF REGULAR NE'TWORKS

IP.com Disclosure Number: IPCOM000128211D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 9 page(s) / 28K

Publishing Venue

Software Patent Institute

Related People

Marc Snir: AUTHOR [+3]

Abstract

Partitions of regular interconnection networks used for multiprocessing axe investigated. Bounds on the number of components as a function of the number of connections between components are given. The relation between the existence of partitions for networks and their ability to support efficiently data motions is examined. This work was supported by the National Science Foundation under Grant No. MCS-8203307

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE PARTITIONING OF REGULAR NE'TWORKS

by Marc Snir

July 1982

TECHNICAL REPORT 46 This work was supported by the National Science Foundation under Grant No. MCS-8203307.

ABSTRACT

Partitions of regular interconnection networks used for multiprocessing axe investigated. Bounds on the number of components as a function of the number of connections between components are given. The relation between the existence of partitions for networks and their ability to support efficiently data motions is examined.

This work was supported by the National Science Foundation under Grant No. MCS-8203307

1. INTRODUCTION

The fast advance in microelectronics has fostered interest in new architectures suited to this technology. In particular, much research has been devoted to the design of systems consisting of large, regular networks of identical computation nodes. The advance in VLSI has also motivated a large number of papers on the theoretical constraints of VLSI technology. In particular, the area required to realize different types of regular communication graphs have been investigated.

The silicon area required to realize a large computational system frequently exceeds the area of one chip. The network has to be packaged into several components. The cost of multichip systems is best reflected by the number of components rather than by the sum of their area. The "component number" complexity of a network is therefore no less important than its area complexity.

The number of components needed to realize a given network is affected by two constraints. The "area" of a component, i.e. number of nodes that can be packed on a component, is restricted by the physical size of the chip. The "perimeter" of a component, i.e. number of lines leaving that component, is restricted by the pin count of the chip. The last constraint becomes increasingly important with the advance in VLSI technology. The pin count of VLSI chips increase more slowly than the gate count since the size of external wires does not scale down at the same rate as the internal feature size. Also, there is an increasing disparity between the speed of internal lines and the speed of external lines. This Iimits,the use of time-multiplexing to overcome the pin count constraint. It is therefore important to study the effect of "perimeter" constraints on the partionability of interconnection graphs.

Such a study is undertaken in this paper. we characterize the "area" to "perimeter" relationship for families of common graphs such as grides, trees, and shuffle-exchange graphs. We proceed

New York University Page 1 Dec 31, 1982

Page 2 of 9

ON THE PARTITIONING OF REGULAR NE'TWORKS

next to relate the partitionability of graphs to their ability to support efficiently data motions, and show that networks which are efficient for routing do riot partition well.

2. DEFINITIONS

We represent a network by a triple

(Equation Omitted)

is an und...