Quotient Networks

Abstract

A large-network algorithm solves a problem of size N on a network of N processors. We present a method for transforming certain large networks into quotient networks that emulate those large networks with fewer processors. Large-network algorithms are easily modified to execute on the quotient network. The emulations result in no loss in execution efficiency. Quotient networks allow algorithms to be designed assuming any number of processors and executed efficiently at a great savings in hardware cost.