Due to fundamental physical limitations and power
constraints, we are witnessing a radical change in commodity
microprocessor architectures to multicore designs.
Continued performance on multicore processors now requires
the exploitation of concurrency at the algorithmic
level. In this paper, we identify key issues in algorithm
design for multicore processors and propose a computational
model for these systems. We introduce SWARM
(SoftWare and Algorithms for Running on Multi-core),
a portable open-source parallel library of basic primitives
that fully exploit multicore processors. Using this
framework, we have implemented efficient parallel algorithms
for important primitive operations such as prefixsums,
pointer-jumping, symmetry breaking, and list ranking;
for combinatorial problems such as sorting and selection;
for parallel graph theoretic algorithms such as spanning
tree, minimum spanning tree, graph decomposition,
and tree contraction; and for computational genomics applications
such as maximum parsimony. The main contributions
of this paper are the design of the SWARM
multicore framework, the presentation of a multicore algorithmic
model, and validation results for this model.
SWARM is freely available as open-source from http://multicore-swarm.sourceforge.net/.
