  We explore the interplay between architectures and algorithm design in the
context of shared-memory platforms and a specific graph problem of central
importance in scientific and high-performance computing, distance-1 graph
coloring. We introduce two different kinds of multithreaded heuristic
algorithms for the stated, NP-hard, problem. The first algorithm relies on
speculation and iteration, and is suitable for any shared-memory system. The
second algorithm uses dataflow principles, and is targeted at the
non-conventional, massively multithreaded Cray XMT system. We study the
performance of the algorithms on the Cray XMT and two multi-core systems, Sun
Niagara 2 and Intel Nehalem. Together, the three systems represent a spectrum
of multithreading capabilities and memory structure. As testbed, we use
synthetically generated large-scale graphs carefully chosen to cover a wide
range of input types. The results show that the algorithms have scalable
runtime performance and use nearly the same number of colors as the underlying
serial algorithm, which in turn is effective in practice. The study provides
insight into the design of high performance algorithms for irregular problems
on many-core architectures.
