COMPUTING NETWORK FLOW ON A MULTIPLE PROCESSOR PIPELINE

We demonstrate the feasibility of a distributed implementation of the Goldberg-Tarjan algorithm for finding the maximum flow in a network. U nlike other parallel implementations of this algorithm, where the netw ork graph is partitioned among many processors, we partition the algor ithm among processors arranged in a pipeline. The network graph data a re distributed among the processors according to local requirements. T he 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 example s. Performance estimates based upon a six-processor pipelined implemen tation indicated a speedup between 4.8 and 5.9 over a single processor .