Scalable Computing and Communications: Theory and Practice

21

–––––––––––––––––––––––

Implementing Pointer Jumping for Exact Inference on Many-Core Systems

Yinglong Xia, Nam Ma, and Viktor K. Prasanna

21.1 INTRODUCTION

Many recent parallel computing platforms install many-core processors or multiple multicore processors to deliver high performance. Such platforms are known as many-core systems, for example, the 24-core AMD Magny-Cours system, 32-core Intel Nehalem-EX system, 64-hardware-thread UltraSPARC T2 (Niagara 2) Sun Fire T2000 [1], and 80-core IBM Cyclops64 [2]. To accelerate the execution of applications in a many-core system, we must keep the cores busy. However, as the number of cores increases, a fundamental challenge in parallel computing is how to keep many cores busy, especially for applications with inherently sequential computation.

Pointer jumping is a parallel computing technique for exploring parallel activities from applications [3]. In this chapter, we especially consider applications offering limited parallelism. Such applications typically consist of a few long chains in their structures, where the computation along a chain must be performed sequentially. However, we can leverage pointer jumping to find more parallelism so that we can keep more cores busy simultaneously and therefore improve the overall performance.

We use a sample application called exact inference in junction trees to discuss the implementation of pointer jumping in many-core systems [4]. A junction tree is a probabilistic graphical model that ...