A distributed algorithm for maximum flow on processor‐arrays
Kenji Onaga, Satoshi Marumoto · Systems and Computers in Japan · 1986
Abstract This paper considers the maximum flow computation of a network N = (V, E, C), and presents a design of its hardware algorithm which executes the computation in a distributed and MIMD way by a processor array of the same structure as N. The node of N corresponds to a node processor and the edge to a communication link carrying the computational information. The computation of the flow is performed on the flow table FTABLE established on each node. Each node processor performs distributed and MIMD instructions indicated by tokens which are generated in particular nodes (host, input and output nodes) modified and transferred through adjacent nodes. The proposed algorithm can be readily utilized in hardware simulation of traffic and communication networks.