Processor-time tradeoffs in PRAM simulations

摘要

Different models of concurrent-read, concurrent-write parallel random access machine (CRCW PRAM) are distinguished by their method of write-conflict resolution, which can affect the power of the model. We consider the situation where a weaker model with kn processors wishes to simulate a stronger model with n processors (k may be a function of n). In the case of COMMON simulating ARBITRARY or PRIORITY, we show that one step of the stronger model can be simulated by T steps of the weaker model, where T satisfies the tradeoff kT log T = O(log n). In the case of ARBITRARY simulating PRIORITY, we can achieve the tradeoff Tlog(k + 1) = O(log n). This improves the number of processors necessary to achieve constant time to n(log n)ϵ (for fixed ϵe > 0). These tradeoffs unify and extend many previous results in this area. Corresponding lower bounds are proved for the class of simulations in which k processors of the weaker model are assigned to simulate one processor in the stronger model. Two different methods are used to prove the lower bounds; both have a strong combinatorial flavor.