Parallel arithmetic with concurrent writes
Alon Itai · 1985
A WRAM is a parallel computer with shared memory into which many processors may write concurrently.To study the bit-complexity of arithmetic operations the computing ability of each of the processors is restricted to bit operations and execution-time address calculation are prohibited.The model differs from unbounded fan-in boolean circuits since computing the cumulative-and, in constant time is shown to require super-linear number of processors in this model, but only 2u gates of an unbounded fan-in boolean circuit.This lower bound implies that adding two n-bit integers in constant time also requires a super-linear number of processors.However, two such integers may be compared in constant time with a linear number of processors.Thus implying the equivalence of two models of resolving write conflicts: that in which concurrent write occurs only when the same number is being written and that in which the processor with the highest index succeeds writing.Finally, several algorithms for arithmetic operations are investigated with the aim of decreasing the number of processors.