NDLI: Locality-aware task management for unstructured parallelism: a quantitative limit study

Please wait, while we are loading the content...

Fast greedy algorithms in mapreduce and streaming

Storage and search in dynamic peer-to-peer networks

Brief announcement: truly parallel burrows-wheeler compression and decompression

IRIS: a robust information system against insider dos-attacks

Coalescing-branching random walks on graphs

Work-efficient matrix inversion in polylogarithmic time

Profitable scheduling on multiple speed-scalable processors

Cloud scheduling with setup cost

Reduced hardware transactions: a new approach to hybrid transactional memory

Broadcasting in logarithmic time for ad hoc network nodes on a line using mimo

Brief announcement: locality in wireless scheduling

SybilCast: broadcast on the open airwaves (extended abstract)

Parallel rotor walks on finite graphs and applications in discrete load balancing

Communication optimal parallel multiplication of sparse random matrices

Nonclairvoyant sleep management and flow-time scheduling on multiple processors

Efficient online scheduling for deadline-sensitive jobs: extended abstract

Recursive design of hardware priority queues

Expected sum and maximum of displacement of random sensors for coverage of a domain: extended abstract

Brief announcement: universally truthful secondary spectrum auctions

On-the-fly pipeline parallelism

Parallel graph decompositions using random shifts

Communication efficient gaussian elimination with partial pivoting using a shape morphing data layout

Reallocation problems in scheduling

Locality-aware task management for unstructured parallelism: a quantitative limit study

Drop the anchor: lightweight memory management for non-blocking data structures

On dynamics in selfish network creation

Brief announcement: online batch scheduling for flow objectives

Reducing contention through priority updates

A constant factor approximation algorithm for the storage allocation problem: extended abstract

Optimal patrolling of fragmented boundaries

Efficient scheduling to minimize calibrations

Balls-into-bins with nearly optimal load distribution

Scalable statistics counters

Brief announcement: set it and forget it - approximating the set once strip cover problem

HEX: scaling honeycombs is easier than scaling clock trees

Non-monetary fair scheduling: a cooperative game theory approach

Brief announcement: between all and nothing - versatile aborts in hardware transactional memory

Brief announcement: towards a fully-articulated pessimistic distributed transactional memory

Brief announcement: a game-theoretic model motivated by the darpa network challenge

Locality-aware task management for unstructured parallelism: a quantitative limit study

Content Provider	ACM Digital Library
Author	Kim, Changkyu Hughes, Christopher J. Yoo, Richard M. Kozyrakis, Christos Chen, Yen-Kuang
Abstract	As we increase the number of cores on a processor die, the on-chip cache hierarchies that support these cores are getting larger, deeper, and more complex. As a result, non-uniform memory access effects are now prevalent even on a single chip. To reduce execution time and energy consumption, data access locality should be exploited. This is especially important for task-based programming systems, where a scheduler decides when and where on the chip the code segments, i.e., tasks, should execute. Capturing locality for structured task parallelism has been done effectively, but the more difficult case, unstructured parallelism, remains largely unsolved - little quantitative analysis exists to demonstrate the potential of locality-aware scheduling, and to guide future scheduler implementations in the most fruitful direction. This paper quantifies the potential of locality-aware scheduling for unstructured parallelism on three different many-core processors. Our simulation results of 32-core systems show that locality-aware scheduling can bring up to 2.39x speedup over a randomized schedule, and 2.05x speedup over a state-of-the-art baseline scheduling scheme. At the same time, a locality-aware schedule reduces average energy consumption by 55% and 47%, relative to the random and the baseline schedule, respectively. In addition, our 1024-core simulation results project that these benefits will only increase: Compared to 32-core executions, we see up to 1.83x additional locality benefits. To capture such potentials in a practical setting, we also perform a detailed scheduler design space exploration to quantify the impact of different scheduling decisions. We also highlight the importance of locality-aware stealing, and demonstrate that a stealing scheme can exploit significant locality while performing load balancing. Over randomized stealing, our proposed scheme shows up to 2.0x speedup for stolen tasks.
Starting Page	315
Ending Page	325
Page Count	11
File Format	PDF
ISBN	9781450315722
DOI	10.1145/2486159.2486175
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Energy Locality Task scheduling Task stealing Performance
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

SLAW: A scalable locality-aware adaptive work-stealing scheduler

A scalable locality-aware adaptive work-stealing scheduler for multi-core task parallelism

Yen-Kuang Chen†

A work-stealing scheduler for X10's task parallelism with suspension

Energy-Aware Task Scheduling of MapReduce Cluster

Optimizing load balancing and data-locality with data-aware scheduling

SLAW: A scalable localityaware adaptive work-stealing scheduler (2010)

Work-stealing without the baggage

Work-Stealing, Locality-Aware Actor Scheduling

Locality-aware task management for unstructured parallelism: a quantitative limit study

Similar Documents

SLAW: A scalable locality-aware adaptive work-stealing scheduler

A scalable locality-aware adaptive work-stealing scheduler for multi-core task parallelism

Yen-Kuang Chen†

A work-stealing scheduler for X10's task parallelism with suspension

Energy-Aware Task Scheduling of MapReduce Cluster

Optimizing load balancing and data-locality with data-aware scheduling

SLAW: A scalable localityaware adaptive work-stealing scheduler (2010)

Work-stealing without the baggage

Work-Stealing, Locality-Aware Actor Scheduling

Locality-aware task management for unstructured parallelism: a quantitative limit study