Name
Title | ||
|---|---|---|
Position Paper: Locality-Driven Scheduling of Tasks for Data-Dependent Multithreading |
Abstract | ||
|---|---|---|
Implementing locality-aware scheduling algorithms using fine-programming models may generate scheduling overheads due to the potential elevated number of tasks. In order to reduce such overhead, while increasing at the same time data locality in multithreaded applications, this paper proposes a new technique named Locality-Driven Code Scheduling (LDCS). LDCS uses the data dependency graph of an application to identify the tasks writing to a common chunk of data and groups them into a single coarse-grain construct called super-task. LDCS uses fine-grain synchronization to start the execution of a super-task, but relaxes the constraints of classical macro-dataflow models by signaling a super-task in the middle of its execution to fire each of its internal phases. Since all the phases of a super-task process the same block of data and the scheduling of work to hardware threads is made in terms of super-tasks, long latency operations are significantly reduced. Preliminary results show that LDCS can improve the performance of a linear algebra kernel by 72% on average for weak scaling in comparison with a dynamic scheduling version of the kernel when using an architecture with software-managed memory hierarchy. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/IPDPSW.2014.153 | Parallel & Distributed Processing Symposium Workshops |
Keywords | Field | DocType |
data flow analysis,graph theory,multi-threading,processor scheduling,LDCS,data dependency graph,data-dependent multithreading,dynamic scheduling kernel version,fine-grain synchronization,fine-programming models,internal phases,locality-driven code scheduling,locality-driven task scheduling,macro-dataflow models,multithreaded applications,single coarse-grain construct,software-managed memory hierarchy,super-task,Dynamic Scheduling,Locality-Aware Scheduling,Many-core Architecture,Multithreading,Super-tasks | Fixed-priority pre-emptive scheduling,Fair-share scheduling,Computer science,Parallel computing,Gang scheduling,Two-level scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Round-robin scheduling,Distributed computing | Conference |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jaime Arteaga | 1 | 0 | 0.34 |
| Stéphane Zuckerman | 2 | 42 | 8.16 |
| Elkin Garcia | 3 | 82 | 7.90 |
| Guang R. Gao | 4 | 2661 | 265.87 |