The maximum flow problem is a combinatorial
problem of significant importance in a wide variety of research
and commercial applications. It has been extensively studied and
implemented over the past 40 years. The push-relabel method has
been shown to be superior to other methods, both in theoretical
bounds and in experimental implementations. Our study discusses
the implementation of the push-relabel network flow algorithm on
present-day symmetric multiprocessors (SMP's) with large shared
memories. The maximum flow problem is an irregular graph problem
and requires frequent fine-grained locking of edges and vertices.
Over a decade ago, Anderson and Setubal implemented Goldberg's
push-relabel algorithm for shared memory parallel computers;
however, modern systems differ significantly from those targeted
by their implementation in that SMP's today have deep memory
hierarchies and different performance costs for synchronization
and fine-grained locking. Besides our new cache-aware
implementation of Goldberg's parallel algorithm for modern
shared-memory parallel computers, our main new contribution
is the first parallel implementation and analysis of the gap
relabeling heuristic that runs from 2.1 to 4.3 times faster for
sparse graphs.
