Skip to Main content Skip to Navigation

Adaptive Algorithms for Shared Cache on Multicore

Marc Tchiboukdjian 1 Vincent Danjean 1 Thierry Gautier 1 Fabien Le Mentec 1 Bruno Raffin 1
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG [2007-2015] - Laboratoire d'Informatique de Grenoble [2007-2015]
Abstract : Reordering instructions and data layout can bring significant performance improvement for memory bounded applications. Parallelizing such applications requires a careful design of the algorithm in order to keep the locality of the sequential execution. On one hand, parallel computation tends to create concurrent tasks that work on independent data sets to reduce communication and synchronization. On the other hand, a multicore architecture with shared cache can bring performance benefits due to high-speed communication between cores if concurrent tasks process data close in memory. In this paper, we aim at finding a good parallelization of memory bounded applications on multicore that preserves the advantage of a shared cache. We focus on sequential applications with iteration through a sequence of memory references. Our solution relies on an adaptive parallel algorithm with a dynamic sliding window that constrains cores sharing the same cache to process data close in memory. This parallel algorithm induces the same number of cache misses as the sequential algorithm at the expense of an increased number of synchronizations. We theoretically analyze the synchronization overhead for both static and dynamic load balancing. Experiments with a memory bounded isosurface extraction application confirm that core collaboration for shared cache access can bring significant performance improvements despite the incurred synchronization costs. On quad cores Nehalem processor, our algorithms are 10% to 30% faster than algorithms not optimized for shared cache thanks to a reduced number of last level cache misses.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
Contributor : Marc Tchiboukdjian <>
Submitted on : Thursday, April 15, 2010 - 9:48:06 PM
Last modification on : Friday, July 17, 2020 - 11:10:24 AM
Long-term archiving on: : Monday, October 22, 2012 - 3:01:33 PM


Files produced by the author(s)


  • HAL Id : inria-00473617, version 1


Marc Tchiboukdjian, Vincent Danjean, Thierry Gautier, Fabien Le Mentec, Bruno Raffin. Adaptive Algorithms for Shared Cache on Multicore. [Research Report] RR-7256, INRIA. 2010, pp.17. ⟨inria-00473617⟩



Record views


Files downloads