|
Published Articles >> Table of Contents >> Abstract
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers
p. 34a
Translating Submachine Locality into Locality of Reference
Carlo Fantozzi, University of Padova
Andrea Pietracaprina, University of Padova
Geppino Pucci, University of Padova
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1302947
Send link to a friend
| Abstract |
|
The design of algorithms exhibiting a high degree of temporal and spatial locality of reference is crucial to attain good performance on current and foreseeable computing systems featuring ever deeper memory hierarchies. Previous work has demonstrated that task parallelism can be efficiently transformed into locality of reference in two-level hierarchies. Recently, we moved a step forward and showed how the more structured type of parallelism exposed by submachine locality can be efficiently turned into temporal locality on arbitrarily deep hierarchies. In this work, we complete and extend the above result by encompassing also spatial locality. Specifically, we present a scheme to simulate parallel algorithms designed for the Decomposable BSP (a BSP variant which captures submachine locality) on the Hierarchical Memory Model with Block Transfer. The simulation yields good hierarchy-conscious sequential algorithms from parallel ones, and provides evidence of the strict relation between submachine locality in parallel computation and locality of reference (both temporal and spatial) in the hierarchical memory setting.
|
 Additional Information
|
Citation:
Carlo Fantozzi, Andrea Pietracaprina, Geppino Pucci,
"Translating Submachine Locality into Locality of Reference,"
ipdps,
p. 34a,
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers,
2004
|
|
