2000 · 200 citations · 34 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel AlgorithmsSchedulingCache Behavior AnalysisData LocalityData Locality OptimizationMemory HierarchyShared-memory MultiprocessingShared-memory ParallelismCache LocalityExperimental ValidationLocality-aware SchedulingMemory Access LocalityMemory LocalityUpper BoundsWork StealingWork-stealing Scheduling
This paper studies the data locality of the work-stealing scheduling algorithm on hardware-controlled shared-memory machines. We present lower and upper bounds on the number of cache misses using work stealing, and introduce a locality-guided work-stealing algorithm along with experimental validation.
34