''Relating the Power of the Multiple Associative Computing (MASC) Model to That of Reconfigurable Bus-Based Models''

Jerry L. Trahan

Mingxian Jin

Wittaya Chantamas

Johnnie W. Baker

Journal of Parallel and Distributed Computing vol. 70, no. 5, pp. 458-466, 2010


The MASC (Multiple ASsociative Computing) model is a multi-SIMD model that uses control parallelism to coordinate the interaction of data parallel threads and supports associative SIMD computing on each of its threads. There have been a wide range of algorithms developed for this model. To better understand the power of this model, we present simulations between MASC and reconfigurable bus-based models, e.g., various versions of the Reconfigurable Multiple Bus Machine (RMBM). Constant time simulations of the basic RMBM and the segmenting RMBM by MASC and vice versa are obtained. Simulating the fusing RMBM and the extended RMBM by MASC take O(ceiling(m/v) log m) time, where v is the word size for constant-time associative operations on the MASC and m is the number of buses on the RMBM. By taking advantage of previously established relationships between RMBM and two other popular parallel computational models, namely the Reconfigurable Mesh (RM) and the Parallel Random Access Machine (PRAM), we extend our simulation results to further evaluate the power of the MASC model in terms of its relationship to PRAM and RM.

This work was supported in part by the National Science Foundation under grant number CCR-0310916.