Leveraging HPC Power for Solving Abstract Mathematical Problems

Leveraging HPC Power for Solving Abstract Mathematical Problems

Abstract

With the advent of new HPC architectures and machines, there is a potential to exploit their computational power in scientific applications for which HPC was not widely used before. In this paper, we identify a new class of applications that deal with abstract mathematical problems (enumerative combinatorics) and can be solved completely or partially (to give a clue for complete analytical solutions) by HPC techniques. These applications are embarrassingly parallel so they are best suited for the emerging machines. However, there are some severe challenges imposed by their heavy compute-intensive nature. Thus, we show mechanics of efficient design and implementation of a class of algorithms for these problems that fully utilize the new involved HPC machines such as GPGPUs and Cell BE. Our algorithms will take the best advantage of all levels of parallelism down to the bit-level and other common features of new multi core processors such as multithreading, SIMD, software managed memory hierarchies and rich SIMD bitwise operations to highly utilize the capabilities of such systems. For example, we propose an approach to change the representation of objects into bit arrays and better exploit the above features. As a result, we succeed to perform operations using / operations where is the SIMD width in bits. Through our experimental and evaluation results we show that, the proposed algorithms achieve a speedup of up to two orders of magnitudes which is not possible without employing the rich machine capabilities. Our results are valid for the class of enumerative combinatorial problems and the experimental results for two well-known enumerative problems namely "Intersection Problem of Steiner Triple Systems of Order 15" and "Graph Coloring Enumeration" have been presented.

References