A Novel Integrated Parallel Accelerator for an Irregular Killer App

With severe challenges facing computer technology scaling, hardware accelerators have become increasingly attractive solutions to continue expected generational scaling of performance, as demonstrated by the outstanding commercial success of GPUs for regular parallelism applications such as computer graphics and machine learning.However, parallelism scaling is yet to have a similar impact on irregular algorithms and applications, where distributions of work and data are input-dependent and therefore defy compiletime characterization; e.g., (i) characterizing complex, pointer-based data structures in graph algorithms for locality or load balancing, and (ii) characterizing the transient embedding of heavily nested, input-dependent, fine-grained threads on parallel hardware.Furthermore, when parallelism in such algorithms and applications is limited, overheads in hardware and software exploitation techniques tend to dominate performance, leading even to slow downs, rather than speedups, over standard serial CPUs.Taking the bull by its horns, this paper advances a powerful idea for drastically speeding up irregular parallelism applications.Our goal is to develop a commercially viable parallel software-hardware framework that is especially geared for speeding up irregular applications.To that end, we select a commercially valuable application ("killer app"), whose irregular parallelism requires overcoming extremely challenging aspects of irregular algorithms, such as: (i) recursive spawning of short threads, and (ii) focusing on the most problematic end where parallelism is limited.The application we have selected is SAT solver, a core routine that does the heavy computational lifting in a vast majority of automated reasoning applications.We first develop parallelism models that involve nested spawning of threads.Then, we introduce NPA (Nested Parallel Accelerator), an integrated hardware accelerator that efficiently implements these nested parallelism models with low overhead.We have limited modifications to current CPU core to a few "hooks" to improve the chances for adoption by industry.Experimental results using a detailed microarchitectural simulator show speedups of up to 17.5X when using 10 execution units (and 50 "reservation stations").Increasing the number of execution units to 50, the maximum speedup goes up to 36X.Due to its diminishing scaling, our NPA should best be used in conjunction with prior techniques for workloads that have more parallelism.