The Sequential Task Flow(STF)model guides task parallelism by dynamically analyzing data dependencies at runtime,making it well-suited to handle dynamic and irregular parallelism.However,it introduces additional depen...The Sequential Task Flow(STF)model guides task parallelism by dynamically analyzing data dependencies at runtime,making it well-suited to handle dynamic and irregular parallelism.However,it introduces additional dependency tracking overhead.As task granularity becomes increasingly fine-grained or hardware parallelism increases,the traditional Centralized TDG Building(CB)algorithm progressively becomes a performance bottleneck.The Parallel TDG Building algorithm with Helpers(PBH),which leverages hardware message-passing mechanisms,has achieved significant speedups on the SW26010 platform,but its intensive sub-microsecond irregular synchronizations make it difficult to scale on cache-coherent multicore platforms.This paper proposes Cache-friendly PBH(CPBH),a parallel dependency tracking algorithm optimized for cache-coherent architectures.CPBH introduces a locality-aware lock-free batch synchronization mechanism that reduces the overhead of atomic operation contention and improves data access locality.Additionally,it employs an asynchronous execution strategy to overlap dependency tracking and task graph execution using dynamic reference counting.Experiments on three cache-coherent multicore platforms using 10 HPC benchmarks demonstrate that CPBH achieves an average speedup exceeding 1.4×compared to CB and over 1.2×speedup compared to DDAST under fine-grained scenarios.展开更多
基金supported in part by the National Key Research and Development Program of China(2024YFB4505701)National Natural Science Foundation of China(62090024)。
文摘The Sequential Task Flow(STF)model guides task parallelism by dynamically analyzing data dependencies at runtime,making it well-suited to handle dynamic and irregular parallelism.However,it introduces additional dependency tracking overhead.As task granularity becomes increasingly fine-grained or hardware parallelism increases,the traditional Centralized TDG Building(CB)algorithm progressively becomes a performance bottleneck.The Parallel TDG Building algorithm with Helpers(PBH),which leverages hardware message-passing mechanisms,has achieved significant speedups on the SW26010 platform,but its intensive sub-microsecond irregular synchronizations make it difficult to scale on cache-coherent multicore platforms.This paper proposes Cache-friendly PBH(CPBH),a parallel dependency tracking algorithm optimized for cache-coherent architectures.CPBH introduces a locality-aware lock-free batch synchronization mechanism that reduces the overhead of atomic operation contention and improves data access locality.Additionally,it employs an asynchronous execution strategy to overlap dependency tracking and task graph execution using dynamic reference counting.Experiments on three cache-coherent multicore platforms using 10 HPC benchmarks demonstrate that CPBH achieves an average speedup exceeding 1.4×compared to CB and over 1.2×speedup compared to DDAST under fine-grained scenarios.
