| Abstract |
Recent trends in modern CPU architectures lead to multi-core designs with ever increasing numbers of cores. Furthermore architectures have emerged with heterogeneity and explicit memory hierarchies. The CELL [1] processor is a prime example of a powerful heterogeneous processor with explicitly managed local memories. A major challenge for such multi-core systems is the extraction of adequate parallelism and its exploitation with low runtime overhead and reasonable programming effort.
A suitable programming model for such architectures is the task-based model [2] [3] [4]. Task-based programming provides a high abstraction for the programmer while maintaining a significant amount of useful information. However the task-based model in far from panacea, since it requires explicit synchronization, which can be a limiting factor.
The dynamic data-flow execution model can overcome the bottleneck of explicit synchronization in task-based parallel programming, while at the same time simplifying the requirements from the programmer. Earlier research, such as the CELLSS [2] programming framework, proves that it is possible to implement the dynamic dataflow model over a task-based model via runtime dependence analysis. CELLSS [2] however performs expensive dependence analysis on memory objects by maintaining a task-graph at runtime. We propose an alternative method of implementing the data-flow model of execution over task-based models, where instead of a task graph we use a data dependency graph, and a novel mechanism for identifying dependencies with O(1) complexity. Furthermore our mechanism has the ability to track dependences due to partially overlapping data regions accessed by different tasks.
We design and implement ADAM, a runtime system that employees our proposals. ADAM stands for “Accelerated Dependence Analysis for Multi-cores”. We evaluate the scalability of ADAM on the CELL [1] processor and compare its performance with the (i)TPC [3] runtime, the (ii) CELLSS [2] runtime and (iii) a runtime with manual dependence analysis. ADAMs performance compared to the CELLSS [2] runtime is 2,77 better for the Cholesky benchmark and 2,27 times better for the Jacobi benchmark. In comparison with the TPC [3] runtime ADAM manages to efficiently parallelize applications that the TPC [3] fails to.
|
Dynamic Dependence Analysis on Multi-core Processors
