EPIC: A framework to exploit parallelism in irregular codes

摘要

To harness the performance potential of current multicore processors, a multitude of algorithms, frameworks and libraries have been developed. Nevertheless, it is still extremely difficult to take advantage of the full potential of multicore processors. Moreover, when using third-party tools and/or in the presence of asymmetric sets of tasks, this problem would only aggravate. The EPIC framework was developed to ease the exploitation of task parallelism in irregular applications that use third-party tools and/or generate asymmetric sets of tasks. It is based on a software design and implements two algorithms that, together, allow, in a seamlessly way, the efficient exploitation of coarse-grained parallelism, fine-grained parallelism, and the combination of both of these types. Thus, it becomes possible to make a better and transparent usage of the performance potential of current multicore processors on shared-memory systems. In this paper, we present two refinements to the EPIC framework: one that refines the software design of the EPIC framework and another that refines the scheduling algorithm of the EPIC framework. Together, these refinements allow to cope with a special class of sets of tasks: sets of tasks where asymmetry is insignificant or can be neglected. Thus, these refinements broaden the applicability of the EPIC framework to a large class of irregular applications where task parallelism can be exploited. To assess the feasibility and the benefit of using this new version of the EPIC framework to exploit task parallelism, we used four real-world irregular applications-three from phylogenetics and another from astrophysics-and several input data sets with different characteristics. Our studies show groundbreaking results in terms of the achieved speedups and that scalability is not impaired, even when using third-party tools and/or in the presence of (a)symmetric sets of tasks.