A cost-efficient algorithm for arbitrary CRCW PRAM simulation

The arbitrary concurrent read concurrent write (CRCW) parallel random access machine (PRAM) is a very strong model of parallel computing. Direct realization of the model is not feasible with current silicon technologies but there exists a well-known indirect realization on a top of a physically distributed memory machine via simulation known as Ranade’s algorithm. Unfortunately it requires expensive sorting networks prior to a combining network and takes at least two steps per reference. In this paper we propose a novel single step algorithm for arbitrary CRCW PRAM simulation based on processor-level filtering and combining. We apply the algorithm to our scalable MP-SOC framework and give early simulation results