Browse Prior Art Database

Lower bounds on communication complexity in VLSI

IP.com Disclosure Number: IPCOM000128200D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 17 page(s) / 46K

Publishing Venue

Software Patent Institute

Related People

Richard Colet: AUTHOR [+4]

Abstract

We analyze a family of problems governing the VLSI complexity of broadcasting B bits of information in time T (sB) to each of N processors located along the perimeter of a two dimensional broadcast network. Among other results, we show: [Equation ommitted] for such network, when the output ports are [Equation ommitted] unit distance apart. This bound seems to be the first ATZ tradeoff which is not based on the number of bits that must cross a cut of boundary of some subcircuit. The above ATZ bound scales linearly in the distance between adjacent ports, for ports distributed along the circuit perimeter with an approximately uniform spacing. Any vertex degree 3 graph, which has N vertices and breadth first search depth T, contains a complete binary tree of depth [Equation ommitted] These problems are of importance in the design and analysis of optimal VLSI circuits, such as sorters that have their input ports located along the circuit perimeter. Moreover, some of the proof techniques are of interest in their own right..

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

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Lower bounds on communication complexity in VLSI

by

Richard Colet Alan Siegel*

Technical Report #192 Ultracomputer Note #90 December, 1985 New York University Dept. of Computer Science Courant Institute of Mathematical Sciences 251 Mercer Street New York, New York 10012 i

This work was supported in part by NSF Grant DCR-84-OI633, and by an IBM Faculty Development Award. $ This work was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U. S. Department of Energy, under contract number DE-AC0276ER03077, and in part by ONR contract number ONR-N0014-85-K-0046.

ABSTRACT

We analyze a family of problems governing the VLSI complexity of broadcasting B bits of information in time T (sB) to each of N processors located along the perimeter of a two dimensional broadcast network. Among other results, we show:

(Equation Omitted)

for such network, when the output ports are

(Equation Omitted)

unit distance apart. This bound seems to be the first ATZ tradeoff which is not based on the number of bits that must cross a cut of boundary of some subcircuit. The above ATZ bound scales linearly in the distance between adjacent ports, for ports distributed along the circuit perimeter with an approximately uniform spacing.

Any vertex degree 3 graph, which has N vertices and breadth first search

depth T, contains a complete binary tree of depth

(Equation Omitted)

These problems are of importance in the design and analysis of optimal VLSI circuits, such as sorters that have their input ports located along the circuit perimeter. Moreover, some of the proof techniques are of interest in their own right..

1. Introduction

This work analyzes the VLSI complexity of a basic function: the broadcast. Evidently, a broadcast circuit must, in general, contain a tree linking the output ports to the input port. Thus it is to be anticipated that the complexity of laying out a tree plays a central role in our results. It is

New York University Page 1 Dec 31, 1985

Page 2 of 17

Lower bounds on communication complexity in VLSI

well known that an N node; complete binary tree can be laid out in linear area (the H-tree layout). Most of the leaves of an H-tree, however, are located in the interior of the circuit, and not along the perimeter. In many applications - such as when the leaves represent output ports - the leaf nodes must be located exclusively along the perimeter of the circuit. More specifically, we consider the following problem. Give a tight lower bound on the VLSI complexity of broadcasting B bits in time T to N sets of consecutive output ports, that is, for each bit b, there is a port in each set of output ports that receives bit b. It should be emphasized that the intervals spanned by sets of output ports must be disjoint. This restriction prevents the problem from being solved, for instance, by BIT disjoint broadcast tregs, each of minimal size. Our...