PRAM's Towards Realistic Parallelism: BRAM's

Due to its many idealizing assumptions, the well-known parallel 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 different global memory 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 different global memory sizes and different numbers of block communications for the longest common subsequence and the sorting problem