''Relating the Power of the Multiple Associative Computing (MASC) Model
to That of Reconfigurable Bus-Based Models''
Jerry L. Trahan
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.