Supernode transformation on GPGPUs

ABSTRACT

Supernode transformation, or tiling, is a technique that partitions algorithms to improve data locality and parallelism to achieve shortest running time. It groups multiple iterations of nested loops into supernodes to be assigned to processors for processing in parallel. A supernode transformation can be described by supernode size and shape. This paper focuses on supernode transformation on General Purpose Graphic Processing Units (GPGPUs), including supernode scheduling, supernode mapping to GPGPU blocks, and the finding of the optimal supernode size, for achieving the shortest total running time. The algorithms considered are two nested loops with regular data dependencies. The Longest Common Subsequence problem is used as an illustration. A novel mathematical model for the total running time is established as a function of the supernode size, algorithm parameters such as the problem size and the data dependence, the computation time of each loop iteration, architecture parameters such as the number of GPGPU blocks, and the communication cost. The optimal supernode size is derived from this closed form model. The model and the optimal supernode size provide better results than previous research and are verified by simulations on GPGPUs.

Iterations in a two-dimensional uniform dependence algorithm iteration space of $M\times N$, shown as the intersections in the picture, can be grouped into rectangles of $w\times h$ known as a tile or a supernode. This process is called supernode transformation or tiling. It reduces the inter-iteration communication cost thus improves the total execution time. The supernodes on the same wavefront may be scheduled on GPU to be processed at the same time, each by a GPU block. The size of the tile, $w\times h$, plays an important role in this transformation. The optimal size can lead to minimal total execution time.

Graphical Abstract

KEYWORDS:

• Supernode transformation
• tiling
• GPGPUs
• linear scheduling
• data locality
• parallel computing