Abstract
This paper addresses the problem of efficiently supporting parallelism within a managed runtime. A popular approach for exploiting software parallelism on parallel hardware is task parallelism, where the programmer explicitly identifies potential parallelism and the runtime then schedules the work. Work-stealing is a promising scheduling strategy that a runtime may use to keep otherwise idle hardware busy while relieving overloaded hardware of its burden. However, work-stealing comes with substantial overheads. Recent work identified sequential overheads of work-stealing, those that occur even when no stealing takes place, as a significant source of overhead. That work was able to reduce sequential overheads to just 15% [21]. In this work, we turn to dynamic overheads, those that occur each time a steal takes place. We show that the dynamic overhead is dominated by introspection of the victim's stack when a steal takes place. We exploit the idea of a low overhead return barrier to reduce the dynamic overhead by approximately half, resulting in total performance improvements of as much as 20%. Because, unlike prior work, we attack the overheads directly due to stealing and therefore attack the overheads that grow as parallelism grows, we improve the scalability of work-stealing applications. This result is complementary to recent work addressing the sequential overheads of work-stealing. This work therefore substantially relieves work-stealing of the increasing pressure due to increasing intra-node hardware parallelism.
Original language | English |
---|---|
Pages | 165-176 |
Number of pages | 12 |
DOIs | |
Publication status | Published - 2014 |
Event | 10th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE 2014 - Salt Lake City, UT, United States Duration: 1 Mar 2014 → 2 Mar 2014 |
Conference
Conference | 10th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE 2014 |
---|---|
Country/Territory | United States |
City | Salt Lake City, UT |
Period | 1/03/14 → 2/03/14 |