2024 · 18 citations · 7 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureParallel ComputingData ParallelismData-flow AnalysisHardware AccelerationStatic AnalysisTiming AnalysisWorst-case Execution Time AnalysisGpu Parallel AlgorithmsGpu ProfilingParallel Partitioning StrategiesProcessor-accelerator PartitioningStatic Timing Analysis
Recent static timing analysis (STA) engines have leveraged task dependency graph (TDG) parallelism to accelerate various STA algorithms, including graph-based analysis and path-based analysis. Despite the promising speedup via task parallelism, the scheduling cost of a TDG has become dominant when handling large TDGs. To overcome this challenge, we propose G-PASTA, a simple and fast TDG partitioning algorithm to reduce the scheduling cost of large task-parallel STA algorithms. By harnessing the power of GPU computing, G-PASTA incurs minimal cost of partitioning while bringing significant runtime improvement to task-parallel STA algorithms. Compared to a state-of-the-art CPU-based TDG partitioner, G-PASTA is up to 41.8× faster in partitioning runtime and can improve the overall STA performance by 43% on large designs.
7
George Karypis, Vipin Kumar · University of Minnesota Digital Conservancy (University of Minnesota) · 1997 · 1.2K citations · Full text
Partitioning parallel programs for macro-dataflow
Vivek Sarkar, John L. Hennessy · 1986 · 107 citations
High-Quality Hypergraph Partitioning
Sebastian Schlag, Lars Gottesbüren, Yaroslav Akhremtsev et al. · ACM Journal of Experimental Algorithmics · 2022 · 107 citations
Cpp-Taskflow: Fast Task-Based Parallel Programming Using Modern C++
Tsung‐Wei Huang, Chun-Xun Lin, Guannan Guo et al. · 2019 · 89 citations