Cache-oblivious simulation of parallel programs

Author

Pietracaprina, Andrea ; Pucci, Geppino ; Silvestri, Francesco

Author_Institution

Dept. of Inf. Eng., Padova Univ.

fYear

2006

fDate

25-29 April 2006

Abstract

This paper explores the relation between the structured parallelism exposed by the decomposable BSP (D-BSP) model through submachine locality and locality of reference in multi-level cache hierarchies. Specifically, an efficient cache-oblivious algorithm is developed to simulate D-BSP programs on the ideal cache model (ICM). The effectiveness of the simulation is proved by showing that optimal cache-oblivious algorithms for prominent problems can be obtained from D-BSP algorithms. Finally, a tight relation between optimality in the D-BSP and ICM models is established

Keywords

cache storage; distributed shared memory systems; parallel programming; D-BSP program; cache-oblivious simulation; decomposable BSP; ideal cache model; multilevel cache hierarchy; optimal cache-oblivious algorithm; parallel program; structured parallelism; submachine locality; Algorithm design and analysis; Computational efficiency; Computational modeling; Cost function; Hidden Markov models; Memory management; Microprocessors; Parallel processing; Programming profession; User-generated content;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International

Conference_Location

Rhodes Island

Print_ISBN

1-4244-0054-6

Type

conf

DOI

10.1109/IPDPS.2006.1639555

Filename

1639555