CAREER: Compiler and Runtime Support for Irregular Applications on Many-core Processors

North Carolina State University, Raleigh NC

Investigators

Abstract

Many-core processors (such as GPUs) have been used to accelerate a wide variety of applications: molecular dynamics, image processing, data mining, option pricing and linear algebra, among others. Despite their widespread adoption, these devices are still considered relatively difficult to use, in that they require the programmer to be familiar both with parallel programming and with the operation of the hardware. In particular, the effective deployment of irregular applications on many-core devices is still far from understood. However, many established and emerging applications (from social and computer networking, electrical circuit modeling, discrete event simulation, compilers, and computational sciences) are irregular in nature, being based on data structures such as graphs and trees. This research proposes compiler and runtime techniques to support the deployment of graph and other irregular applications on many-core processors, while hiding from the programmer the complexity and heterogeneity of the underlying hardware and software stack. Since the degree of parallelism within irregular applications is heavily data dependent, the proposed compiler techniques aim to generate multiple platform-specific code variants starting from high-level platform-agnostic algorithmic descriptions. The runtime techniques focus on the selection of the most appropriate code variant and its tuning to the hardware and the input datasets. More specifically, this research covers three important issues related to irregular applications: (i) the effective handling of nested parallelism (in the form of parallelizable nested loops and recursive functions) within irregular applications; (ii) the design of a dynamic memory allocation library that can scale to the degree of multithreading offered by many-core devices, and of graph encoding schemes suitable for applications operating on dynamic datasets; and (iii) the effective handling of synchronization on many-core devices.