Browse Prior Art Database

Finding Connected Components and Connected Ones On A Mesh-Connected Parallel Computer

IP.com Disclosure Number: IPCOM000128553D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 16 page(s) / 47K

Publishing Venue

Software Patent Institute

Related People

David Nassimi: AUTHOR [+4]

Abstract

Let [Equation ommitted] be an undirected graph in which no vertex has degree more than d. Let IVI= nq. In this paper we present an [Equation ommitted] algorithm to find the connected components of G on a q-dimensional [Equation ommitted] mesh-connected parallel computer. When d=2, the connected components can be found in [Equation ommitted] time. We also show that the connected ones problem can be solved in [Equation ommitted] time.

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

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Finding Connected Components and Connected Ones On A Mesh- Connected Parallel Computer

by David Nassimi and Sartaj Sahni Computer Science Department 136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical Report 79- 18 June 1979 Cover design courtest of Ruth and Jay Leavitt Finding Connected Components and Connected Ones On A Mesh-Connected Parallel Computer

David Nassimi and Sartaj Sahni University of Minnesota

Abstract:

Let

(Equation Omitted)

be an undirected graph in which no vertex has degree more than d. Let IVI= nq. In this paper we present an

(Equation Omitted)

algorithm to find the connected components of G on a q-dimensional

(Equation Omitted)

mesh-connected parallel computer. When d=2, the connected components can be found in

(Equation Omitted)

time. We also show that the connected ones problem can be solved in

(Equation Omitted)

time.

Keywords and phrases: Connected components, connected ones, mesh-connected computer, parallel algorithm, complexity. *This research was supported in part by NSF grant MCS 78- 15455.

1. Introduction

A mesh-connected parallel computer (MCC) is an SIMD (Single _In-struction Stream, Multiple Data Stream) computer. It consists of N=2p processing elements (PEs). In a q-dimensional

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1979

Page 2 of 16

Finding Connected Components and Connected Ones On A Mesh-Connected Parallel Computer

, the PEs may be thought of as logically arranged in a q-dimensional n x n x... x n array. The PE at location

(Equation Omitted)

of the array is connected to the PEs at locations

(Equation Omitted)

provided they exist. Two PEs are adjacent iff they are connected. APE may transmit data to an adjacent PE in a unit-route. In an MCC, each PE has some local memory. Each word and register of local memory has a storage capacity of log N bits (all logarithms in this paper are base 2). The PEs are synchronized and operate under the control of a single instruction stream which is determined by the control unit. An enable mask may be used to select a subset of PEs that will perform the instruction to be executed at any given time. All enabled PEs perform the same in-struction. Parallel algorithms for MCCs and closely related models (such as cellular automatas and parallel processing arrays) have been studied by several researchers. Efficient sorting algorithms can be found in [11] and [15]. Algorithms for certain graph and matrix problems appear in [1 to 4, 8 to 10, and 16]. General routing problems are considered in (12],
[13] and [14]. [6] and [7] cover. language recognition type problems. Several other references to work on MCCs exist. Most of these can be found by tracing through the references of the papers cited above. In this paper we shall address the following problems: (i) Let

(Equation Omitted)

be an undirected graph with

(Equation Omitted)

vertices. L...