AN OPTIMAL IMPLEMENTATION OF BROADCASTING WITH SELECTIVE REDUCTION

A new model of parallel computation called Broadcasting with Selective Reduction (BSR) can be viewed as a CRCW PRAM with one extension. An a dditional type of concurrent memory access is permitted in BSR, namely the BROADCAST instruction, by means of which all N processors may gai n access to all M memory locations simultaneously for the purpose of w riting. At each memory location, a subset of the incoming broadcast da ta is selected and reduced to one value finally stored in that locatio n. For several problems, BSR algorithms are known which require fewer steps than the corresponding best-known PRAM algorithms, using the sam e number of processors. In this paper, we introduce a circuit to imple ment the BSR model, and show that, in size and depth, the circuit we p resent is of the same order as an optimal circuit implementing the PRA M. Thus, we claim that, if it is reasonable to assume that CRCW PRAM i nstructions execute in constant time, the assumption of a constant tim e BROADCAST instruction is no less reasonable.