CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Timing-anomaly free dynamic scheduling of task-based parallel applications

Petros Voudouris (Institutionen för data- och informationsteknik, Datorteknik (Chalmers)) ; Per Stenström (Institutionen för data- och informationsteknik, Datorteknik (Chalmers)) ; Risat Mahmud Pathan (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, (RTAS 2017). Pittsburgh, PA, APR 18-21, 2017 (1545-3421). p. 365-376. (2017)
[Konferensbidrag, refereegranskat]

Multicore architectures can provide high predictable performance through parallel processing. Unfortunately, computing the makespan of parallel applications is overly pessimistic either due to load imbalance issues plaguing static scheduling methods or due to timing anomalies plaguing dynamic scheduling methods. This paper contributes with an anomaly-free dynamic scheduling method, called Lazy, which is non-preemptive and non-greedy in the sense that some ready tasks may not be dispatched for execution even if some processors are idle. Assuming parallel applications using contemporary taskbased parallel programming models, such as OpenMP, the general idea of Lazy is to avoid timing anomalies by assigning fixed priorities to the tasks and then dispatch selective highestpriority ready tasks for execution at each scheduling point. We formally prove that Lazy is timing-anomaly free. Unlike all the commonly-used dynamic schedulers like breadth-first and depth-first schedulers (e.g., CilkPlus) that rely on analytical approaches to determine an upper bound on the makespan of parallel application, a safe makespan of a parallel application is computed by simulating Lazy. Our experimental results show that the makespan computed by simulating Lazy is much tighter and scales better as demonstrated by four parallel benchmarks from a task-parallel benchmark suite in comparison to the state-of-the-art.

Denna post skapades 2017-07-27. Senast ändrad 2017-10-11.
CPL Pubid: 250834


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datorteknik (Chalmers)


Data- och informationsvetenskap

Chalmers infrastruktur