Computing network flow on a multiple processor pipeline

Author

Agrawal, Prathima ; Ng, Antony

Author_Institution

AT&T Bell Labs., Murray Hill, NJ, USA

Volume

5

Issue

6

fYear

1994

fDate

6/1/1994 12:00:00 AM

Firstpage

653

Lastpage

658

Abstract

We demonstrate the feasibility of a distributed implementation of the Goldberg-Tarjan algorithm for finding the maximum flow in a network. Unlike other parallel implementations of this algorithm, where the network graph is partitioned among many processors, we partition the algorithm among processors arranged in a pipeline. The network graph data are distributed among the processors according to local requirements. The partitioned algorithm is implemented on six processors within a 15-processor pipelined message-passing multicomputer operating at 5 MHz. We used randomly generated networks with integer capacities as examples. Performance estimates based upon a six-processor pipelined implementation indicated a speedup between 3.8 and 5.9 over a single processor

Keywords

distributed algorithms; graph theory; pipeline processing; Goldberg-Tarjan algorithm; maximum flow; message-passing multicomputer; multiple processor pipeline; network flow; network graph; parallel implementations; partitioned algorithm; performance estimates; six processors; Computer networks; Equations; Fault tolerance; Fault tolerant systems; Linear code; Operations research; Partitioning algorithms; Pipelines; Signal processing; Signal processing algorithms;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.285611

Filename

285611