chapter  10
22 Pages

Combinatorial Algorithm Design on the Cell/B.E. Processor

ByDavid A. Bader, Virat Agarwal, Kamesh Madduri, Fabrizio Petrini

Combinatorial algorithms play a subtle, yet important, role in traditional scientific computing. Perhaps the most well-known example is the graph partitioning formulation for load-balanced parallelization of scientific simulations. Partitioning algorithms are typically composed of several combinatorial kernels such as graph coloring, matching, sorting, and permutations. Combinatorial algorithms also appear in auxiliary roles for efficient parallelization of linear algebra, computational physics, and numerical optimization computa-

tions. In the last decade or so, the paradigm of data-intensive scientific discovery has significantly altered the landscape of computing. Combinatorial approaches are now at the heart of massive data analysis routines, systems biology, and in general, the study of natural phenomena involving networks and complex interactions.