New Multithreaded Ordering and Coloring Algorithms for Multicore Architectures

We present new multithreaded vertex

ordering

and

distance-k graph coloring

algorithms that are well-suited for multicore platforms. The vertex ordering techniques rely on various notions of “degree”, are known to be effective in reducing the number of colors used by a

greedy

coloring algorithm, and are generic enough to be applicable to contexts other than coloring. We employ

approximate degree

computation in the ordering algorithms and

speculation

and

iteration

in the coloring algorithms as our primary tools for breaking sequentiality and achieving effective parallelization. The algorithms have been implemented using OpenMP, and experiments conducted on Intel Nehalem and other multi-core machines using various types of graphs attest that the algorithms provide scalable runtime performance. The number of colors the algorithms use is often close to optimal. The techniques used for computing the ordering and coloring in parallel are applicable to other problems where there is an inherent ordering to the computations that needs to be relaxed for increasing concurrency.