Algebra-Dynamic Models for CPU- and GPU-Parallel Program Design and the Model of Auto-Tuning

Algebra-Dynamic Models for CPU- and GPU-Parallel Program Design and the Model of Auto-Tuning

DOI: 10.4018/978-1-5225-9384-3.ch004


This chapter considers algebra-dynamic models of parallel programs, which are based on concepts of transition systems theory and algebra of algorithms. The models of sequential and parallel multithreaded programs for multicore processors and program models for graphics processing units are constructed. The authors describe transformations of programs aimed at transition from sequential to parallel versions (parallelization) and improving performance of parallel programs in respect to execution time (optimization). The transformations are based on using rewriting rules technique. The formal model of program auto-tuning as an evolutional extension of transition systems is proposed, and some properties of programs are considered.
Chapter Preview


Development of multicore processors leads to increasing importance of parallel programming aimed at standard, widely accessible computers, and not just for specialized high-performance systems (Akhter & Roberts, 2006). However, there is one more direction of parallel programming which has received especial development recently, namely, the programming of general-purpose tasks for graphics processing units (GPUs) (“General-Purpose Computation on Graphics Hardware”, n.d.). Market requirements have led to rapid development of GPUs and, at present, their computing capacity considerably exceeds the capabilities of usual processors. Therefore, GPUs were applied for solving the problems not concerned directly with graphics processing. Research in these directions is supported by GPU developers: in particular, NVIDIA company provides CUDA platform for general-purpose computations on GPUs (“NVIDIA CUDA technology”, n.d.).

Despite the presence of specialized facilities for CUDA, development of GPU programs remains a labor-consuming work, which requires from a developer a knowledge about low-level details of hardware and software platform. Therefore, there is a need of research in the area of automation of software development process for GPUs. This chapter describes the development of formal design methods, based on concepts of transition systems theory, algebraic programming and algebra-dynamic models of programs (Andon, Doroshenko, Tseytlin, & Yatsenko, 2007; Doroshenko, Zhereb, & Yatsenko, 2010) with the use of rewriting rules technique (Doroshenko & Shevchenko, 2006; “TermWare”, n.d.) for automated development of efficient programs for GPUs. High-level models of programs and models of program execution are developed for central processing unit (CPU) and GPU. Application of rewriting rules and high-level models for automated parallelization and optimization of programs for GPUs is described. The method of automated transition between a high-level model of a program and a source code, which is based on the use of special rewriting rules is proposed. This chapter also considers the formal model of program auto-tuning constructed as an evolutional extension of transition systems and properties of programs.

Currently there is a significant amount of research in the area of automation of software development for graphics processors. Research community examines problems of transition from sequential to parallel programs as well as problems of optimization of existing parallel programs with the use of GPUs. Particularly, the paper (Lee, Min, & Eigenmann, 2009) considers the automatic transition from a multithreaded program implemented using OpenMP technology (“OpenMP Application Programming Interface”, 2015) to implementation of the same program on CUDA platform. Paper (Baskaran et al., 2008) describes a platform for loop optimization in GPU programs. Systems for automatic parallelization and optimization of programs from a specific subject domain, for example, data mining (Ma & Agrawal, 2009) or image processing (Allusse, Horain, Agarwal, & Saipriyadarshan, 2008), are developed. Paper (Lefohn, Sengupta, Kniss, Strzodka, & Owens, 2006) describes the library of high-level data structures for GPUs. Programming platforms for GPUs providing the facilities of a level higher than CUDA are also developed, such as hiCUDA (Han & Abdelrahman, 2009) and BSGP (Hou, Zhou, & Guo, 2008). The difference of the research presented in this chapter consists in the use of formal models and methods that allows combining brevity of description and efficiency of implementation of transformations.

Key Terms in this Chapter

Graphics Processing Unit (GPU): A specialized electronic circuit designed to rapidly manipulate and alter memory to accelerate the creation of images in a frame buffer intended for output to a display device. Modern GPUs are very efficient at manipulating computer graphics and image processing, and their highly parallel structure makes them more efficient than general-purpose CPUs for algorithms where the processing of large blocks of data is done in parallel.

Algebra-Dynamic Program Model: A model of a program which is based on the concept of a transition system. It consists of two parts: a model of program structure and a model of program execution.

Transition System: A concept used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition.

General-purpose computing on graphics processing units (GPGPU): The use of a graphics processing unit (GPU), which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the central processing unit (CPU).

CUDA: A parallel computing platform and application programming interface (API) model created by NVIDIA. It allows software developers and software engineers to use a CUDA-enabled graphics processing unit (GPU).

Evolutionary Model of an Auto-Tuner: The model constructed as an evolutional extension of transition systems which formally describes the auto-tuning system intended for adjusting (optimization) of programs.

Glushkov’s System of Algorithmic Algebras (SAA, Glushkov’s Algebra): The two-sorted algebra focused on analytical form of representation of algorithms and formalized transformation of these representations.

Complete Chapter List

Search this Book: