A linear systolic algorithm and architecture for convex bipartite matching

This paper describes the design of a linear systolic array algorithm and a VLSI architecture for finding the maximum matching in a convex bipartite graph. The design is based on a systolic architecture that fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput. The architecture is scalable and the algorithm is partitionable, i.e., large size problems can be partitioned and executed on a fixed sized array. The PE organization is simple and the architecture does not require any local or global memory. The proposed hardware could be used in various applications such as logic synthesis and channel routing in VLSI CAD, collision avoidance in robotics etc. The proposed chip is estimated to operate at a frequency of 100 MHz based on 1-micron SCMOS technology