Associative nets: a graph-based parallel computing model

摘要

This paper presents a new parallel computing model called Associative Nets. This model relies on basic primitives called associations that consist of applying an associative operator over connected components of a subgraph of the physical interprocessor connection graph. Associations can be very efficiently implemented (in terms of hardware cost or processing time) thanks to asynchronous computation. This model is quite effective for image analysis and several other fields; as an example, graph processing algorithms are presented. While relying on a much simpler architecture, these algorithms have, in general, a complexity equivalent to the one obtained by more expensive computing models, like the PRAM model.