Revisiting the cache miss analysis of multithreaded algorithms

Richard Cole, Vijaya Ramachandran

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper revisits the cache miss analysis of algorithms when scheduled using randomized work stealing (RWS) in a parallel environment where processors have private caches. We focus on the effect of task migration on cache miss costs, and in particular, the costs of accessing "hidden" data typically stored on execution stacks (such as the return location for a recursive call). Prior analyses, with the exception of [1], do not account for such costs, and it is not clear how to extend them to account for these costs. By means of a new analysis, we show that for a variety of basic algorithms these task migration costs are no larger than the costs for the remainder of the computation, and thereby recover existing bounds. We also analyze a number of algorithms implicitly analyzed by [1], namely Scans (including Prefix Sums and Matrix Transposition), Matrix Multiply (the depth n in-place algorithm, the standard 8-way divide and conquer algorithm, and Strassen's algorithm), I-GEP, finding a longest common subsequence, FFT, the SPMS sorting algorithm, list ranking and graph connected components; we obtain sharper bounds in many cases. While this paper focusses on the RWS scheduler, the bounds we obtain are a function of the number of steals, and thus would apply to any scheduler given bounds on the number of steals it induces.

Original languageEnglish (US)
Title of host publicationLATIN 2012
Subtitle of host publicationTheoretical Informatics - 10th Latin American Symposium, Proceedings
Number of pages12
StatePublished - 2012
Event10th Latin American Symposiumon Theoretical Informatics, LATIN 2012 - Arequipa, Peru
Duration: Apr 16 2012Apr 20 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7256 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other10th Latin American Symposiumon Theoretical Informatics, LATIN 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Revisiting the cache miss analysis of multithreaded algorithms'. Together they form a unique fingerprint.

Cite this