SHF: Small: A Novel Integrated Accelerator for a Challenging Irregular Critical Application

Parallel computing, with proper engineering, has the potential to become the dominant computing paradigm, as demonstrated by the success of graphics processing units (GPUs) in the gaming application domain and more recently in the artificial intelligence (AI) application domain. In order to expand the horizon of parallel computing to more general-purpose application domains, it is imperative to resolve the existing mismatch between current parallel hardware and the type of parallelism present in these applications, which is often referred to as “irregular”. The core idea behind this project is to develop and study a novel parallel architecture that is geared for harnessing the difficult, irregular parallelism present in many applications. Successful completion of this project will be a significant step towards prototyping a parallel hardware system that serves applications in such diverse fields as hardware/software verification, automated reasoning, and more generally, computer security. Parallel processing of an application that has irregular parallelism such as satisfiability (SAT) solvers (where distributions of work and data defy pre-runtime characterization) is an extremely challenging task. This project attacks this grand challenge on multiple fronts—algorithms and data structures, parallel programming, and hardware architecture. While the software development part will rewrite applications using irregular threads and nested spawns, the novel hardware framework will use two different components to target different types of parallelism: (1) a sophisticated general-purpose processor that exploits instruction-level parallelism and (2) an integrated parallel processing accelerator that exploits irregular parallelism by providing mechanisms for low-overhead thread spawning and nested thread spawning. While inherently serial portions of the application will run on the general-purpose processor, the parallel portions of the application will run on the accelerator. An integrated accelerator that supports low-overhead nested spawning of threads will be designed and evaluated. Specifically, microarchitectural modeling and cycle-accurate simulation will be used to evaluate performance scaling for SAT solvers, a core routine that does the computational heavy lifting in a vast majority of automated reasoning technologies. Preliminary assessments of system-level integration of the processor and the accelerator with a low-latency, high-bandwidth memory system will be conducted. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.