PRAM’s towards realistic parallelism: BRAM’s

Abstract. Due to its many idealizing assumptions, the well-known par-allel random access machine (PRAM) is not a very practical model of parallel computation. As a more realistic model we suggest the BRAM. Here each of the p processors gets a piece of length n of the input, which thus has size pn in total. Access to global memory has to be data-independent, block-wise, and has to obey the owner restriction. Assuming dierent global mem-ory sizes, BRAM's are suitable for modeling various parallel computers ranging from bounded degree networks to completely connected parallel machines, while abstracting from architectural details. We present optimal BRAM algorithms requiring dierent global mem-ory sizes and dierent numbers of block communications for the longest common subsequence and the sorting problem.