A practical hierarchical model of parallel computation

Abstract

A model of parallel computation is introduced which employs the PRAM as a sub-model, while simultaneously being more reflective of realistic parallel architectures by accounting for and providing abstract control over communication and synchronization costs. Cost control is achieved via the representation of general degrees of locality ('neighborhoods' of activity). The model organizes 'control asynchrony' via an implicit hierarchy relation, and restricts 'communication asynchrony' in order to obtain determinate algorithms.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>