Distributed-Memory Parallel Algorithms for Matching and ColoringÜmit V. Çatalyürek∗ , Florin Dobrian† , Assefaw Gebremedhin‡ , Mahantesh Halappanavar§ , Alex Pothen‡∗ Depts. of Biomedial Informatics and Electrical & Computer Engineering, The Ohio State University
Email: umit@bmi.osu.edu† Conviva
Email: dobrian@conviva.com‡ Department of Computer Science, Purdue University
Email: {agebreme,apothen}@purdue.edu§ Pacific Northwest National Laboratory
Email: Mahantesh.Halappanavar@pnl.gov

Abstract
We discuss the design and implementation of new highlyscalable distributed-memory parallel algorithms for two
prototypical graph problems, edge-weighted matching anddistance-1 vertex coloring. Graph algorithms in general
have low concurrency, poor data locality, and high ratio ofdata access to computation costs, making it challenging toachieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques,
including speculation and iteration, optimized communication, and randomization. We present preliminary results on
weak and strong scalability studies conducted on an IBM
Blue Gene/P machine employing up to tens of thousands ofprocessors. The results show that the algorithms hold strong
potential for computing at petascale.
Key words: Combinatorial scientific computing; graphcoloring; graph matching; parallel algorithms; petascalecomputing; distributed-memory architectures; MPI

1. Introduction
We discuss on-going work on the design and implementation of new scalable distributed-memory parallel algorithms
for two prototypical combinatorial problems of central importance to scientific computing, edge-weighted matchingand distance-1 vertex coloring, and present preliminary
results from experiments conducted on an IBM Blue Gene/P
employing up to tens of thousands of processors.
Developing scalable parallel graph algorithms on terascale (and peta-scale) distributed-memory architectures ischallenging for several reasons [17]. Many graph algorithms are inherently serial in nature, and therefore require
nontrivial algorithmic techniques for creating concurrency.
Graph algorithms possess poor data locality making it
difficult to obtain good memory system performance on
distributed-memory architectures. Computation and communication schedules can be determined often only at runtime,

which makes compile-time prefetching techniques inapplicable. There is relatively low computation per communicatedword, causing loss of performance on distributed-memoryarchitectures where communicating a word typically costs
much more than computing with it.
We overcome many of these challenges for the two
problems we consider by employing a variety of techniques.
An optimal solution for the edge-weighted matchingproblem can be obtained in polynomial time on a serial
machine. However, such optimal algorithms are ill-suitedfor parallelization since they involve long augmenting paths.
We circumvent this difficulty by working with a suitable approximation algorithm instead. The approximation algorithm
we work with has a near linear-time complexity, guarantees
a solution that is at least half of the optimal weight, andis amenable for parallelization as it is based on the ideaof identifying locally dominant (heaviest) edges. Although
the algorithm guarantees a half-approximate solution, experimental evidence indicates that the algorithm often gives
higher than 90% of the optimal weight for graphs that arise
in practice. See Table 1.1 for sample results.
MatrixASIC 680k
Hamrle3
rajat31
cage14ldoor
audikw 1#Vertices1, 365, 724
2, 894, 720
9, 380, 004
3, 011, 570
1, 904, 406
1, 887, 390#Edges3, 871, 773
5, 514, 242
20, 316, 253
27, 130, 349
46, 522, 475
77, 651, 847

Quality
99.99%
99.36%
100.00%100.00%100.00%100.00%

Table 1.1: Quality of the solution computed by the halfapproximation matching algorithm. The data set consists of the bipartite graph representation of randomly chosen matrices from the
University of Florida Sparse Matrix Collection. The first column
identifies the matrices, the second and third columns provide thesize of the corresponding graphs, and the fourth column provides
the quality of the suboptimal solutions relative to optimal solutions(percentages).

The distance-1 vertex coloring problem is NP-hard tosolve optimally [6]. Yet, a greedy algorithm, which runs
in linear time in the number of edges and uses at most∆ + 1 colors, where ∆ is the maximum degree in thegraph, often yields near-optimal solution for graphs thatarise in practice when good vertex ordering techniques
are employed—the near optimality of the solutions can beverified by computing appropriate lower bounds [8]. Such a
greedy coloring algorithm is, however, sequential in nature.
We use speculation and iteration, where concurrency is maximized by tentatively allowing inconsistencies and resolving
them later (iteratively), as a technique for overcoming thisobstacle. This iterative approach is further enhanced byusing randomization in the conflict-resolution phase, wherebias and computational load imbalance among processors is
avoided by picking the vertex to be re-colored in the eventof a conflict (an edge whose endpoints have received thesame color) randomly rather than deterministically.
The input graph in both the matching and coloring algorithms is assumed to be already distributed among processors. In both algorithms, we exploit the parallelism created
due to the initial data distribution. Furthermore, the costassociated with unavoidable communication is optimized.
The optimization is achieved by aggregating frequent, small
messages into infrequent, large messages, and by doing as
much computation as possible in between communication
phases, even if the computation has to be performed withincomplete information.
Employing the ingredients outlined above, we implemented the parallel algorithms for the matching and coloring
problems using MPI. We show that the implementations
scale well to tens of thousands of processors for graphsthat are distributed on processors in such a way that thepercentage of boundary vertices is low.
Our work is motivated by the enabling role graph matching and coloring (in many variations) play in computational
science and engineering (CSE) and in high-performancecomputing. Examples of contexts in which some variantof graph matching is used to devise an effective solution strategy include: maximizing diagonal dominance insparse linear solvers—to improve numerical stability indirect solvers and convergence rate in iterative solvers[4], [5]; computation of block triangular decomposition ofsparse matrices [22]; computation of sparse bases for underdetermined matrices [21]; the coarsening phase of multilevel algorithms for graph partitioning [13]; discovery (orwhen specified, identification) of substructures in networks
arising in bioinformatics [1], [16] and web technology applications [19]; etc. Likewise, a few examples of scenarios inwhich some variant of graph coloring is used to make overall
computation efficient (or feasible) include: task schedulingand concurrency discovery in parallel computing [12], [24];efficient computation of sparse Jacobian and Hessian matrices in numerical optimization [7]; frequency assignment inwireless networks [15]; etc.
There is a large body of work in the literature on graphmatching and on coloring, but much of it is theoretical innature. Few studies are concerned with the development ofefficient implementations useful for CSE. And there does
not seem to exist prior work on parallel implementations
suitable for computing at the tera-scale and beyond. In
this regard, our work stands in contrast to other efforts.
Manne and Bisseling [18] had described, albeit briefly,
a variant of the parallel half-approximation algorithm foredge-weighted matching presented here and reported results
using up to 32 processors for two test cases. We achievemuch greater scalability primarily by paying careful attention to the communication cost involved. A significant
part of the improvement comes from aggressive message
bundling, where messages sent between the same pair ofprocessors are grouped as often as possible.
The parallel coloring algorithm presented here is derived from the framework for parallelizing greedy coloring(based on speculation and iteration) developed by Bozdag
et al. [3]. The work in [3] showed that algorithms basedon speculation and iteration outperform previously known
algorithms that rely on iterative computation of maximal
independent sets in parallel. The work also showed how
specialized algorithms—tailored to specific input structuresand computational scenarios—can be designed using theframework. Experiments in [3] showed that the best specialized algorithm scaled well up to a few hundred processors.
The algorithm presented here extends the scalability range
to several thousands of processors. The improvement, here
again, is due to the use of new techniques for reducing interprocessor communication cost.

2. Preliminaries
Graph matching and coloring problems come in many
variations depending on whether the problem is definedon a bipartite or a non-bipartite graph, on whether or notweights are associated with the vertices and/or edges of agraph, and on the specifics of the computational scenario
under consideration [7], [9]. We focus in this paper on
two specific variants, distance-1 vertex coloring and edgeweighted matching on non-bipartite graphs.
The goal of the distance-1 vertex coloring problem is
to assign colors to the vertices of a graph such that every
pair of adjacent vertices receives different colors and thenumber of colors used is minimized. In the edge-weighted
matching problem, the goal is to find a subset M of theedges in an edge-weighted graph such that every vertex in
the graph is incident on at most one edge in M and thesum of the weights of the edges in M is maximized. As
mentioned earlier, the distance-1 coloring problem in NPhard, whereas the edge-weighted matching problem is polynomial time solvable. We rely here on a linear-time greedy
heuristic for the coloring problem and near linear-time halfapproximation algorithm for the matching problem.

In the parallel versions of these algorithms that we describe in the next two sections, the input graph is assumed
to be partitioned and distributed among the available processors in some reasonable way. By partitioning is meant thatprocessors are assigned nearly the same number of vertices
and the number of cross edges—edges that connect vertices
assigned to different processors—is relatively small. The
partitioning classifies the vertices as interior and boundary.
An interior vertex is a vertex all of whose neighbors are
assigned to the same processor as itself whereas a boundary
vertex is a vertex that has at least one neighbor assigned to adifferent processor. We say that a processor owns the vertices
assigned to it, and assume that a processor is responsible forcoloring (or matching) the vertices it owns. We refer to anedge whose endpoints are assigned to the same processor asinterior.
Clearly, the subgraphs induced by interior vertices (consisting of only interior edges) are independent of each other.
Hence, a coloring in each can be computed independentlyof any other. In the coloring algorithm presented in thispaper, these sub-solutions are concurrently computed andare conceptually pieced-together to give a partial solution tothe original problem on the entire input graph. To obtain acomplete solution, a coloring of the remainder of the graph,the interface graph, needs to be computed in parallel—and
this is the phase in our algorithm where speculation is used
and techniques for minimizing inter-processor communication cost are employed.
In the parallel matching algorithm, the computation on thesubgraphs and the interface graph is not as cleanly delineatedas in the parallel coloring algorithm. Dependencies betweenedges make it necessary to interleave the processing ofinterior and cross edges. On each processor, the computation considers interior edges for matching at first. Then,processors exchange messages as cross edges are considered
for matching. This process is alternated in an asynchronous
manner until the algorithm terminates.

3. Parallel Matching
The approximation algorithm we use for the parallel
computation of a matching M in a graph G = (V, E)
is based on the concept of local dominance: edges thatare heavier than their neighbors are moved from E to M
(M is initially empty) and their neighbors (free edges) areremoved from E; the process continues until E becomes
empty. Preis [23] showed that such a procedure guarantees
a 1/2 approximation factor. Describing the parallel matchingalgorithm based on this procedure in full detail requires more
space than is available here. Hence we describe in adequate
detail (i) the sequential algorithm and (ii) the communication
involved in its parallel version within the simplified context
of one vertex per processor. Then, we only sketch the detailsof the parallel algorithm in the practical context when thenumber of vertices per processor is much larger than one.

3.1. The Sequential Algorithm
A matching based on local dominance can be computed inlinear (O(|E|)) time [23]. Unfortunately, such an implementation is not well suited for parallelization, since it requires
inspecting augmenting paths that can be arbitrarily long.
Hoepman [10] and later Manne and Bisseling [18] discuss
an implementation, based on maintaining candidate mates,that is better suited for parallelization. The complexityof a basic variant of this algorithm is O(|E|∆), where∆ is the maximum vertex degree. The run time can be
improved to O(|E| log ∆) by sorting the adjacency list ofeach vertex based on edge-weights. However, if the weights
are distributed uniformly at random then the expected run
time is O(|E|) [18].
In the candidate mate-based algorithm that we use,for every vertex v, a candidate mate, denoted as
candidateMate(v), is maintained. This becomes the true
mate, denoted as mate(v), if v gets matched to it (mate(v)is set to 0 otherwise). Initially, for every vertex v,
candidateMate(v) is set to be the other endpoint of aheaviest edge incident on v. If there is more than one suchedge then ties are broken by choosing the neighbor with thesmallest label. In addition to the candidate mate, for every
vertex v, a set S(v) that keeps track of all remaining edges
incident on v is maintained. Each set S(v) is initialized toadj (v ).
The algorithm then proceeds by identifying locallydominant edges, i.e., an edge (u, v) such thatcandidateMate(u) = v and candidateMate(v) = u.
Each such edge is moved from E to M and the remainingedges incident on vertices u and v are removed from E, atask accomplished by setting mate(u) = v, mate(v) = u,S(u) = ∅ and S(v) = ∅, and by removing u and v from
S(w), for every vertex w adjacent to u or v. Also, for eachsuch neighbor vertex w, if candidateMate(w) happens tobe equal to u or v, it is necessary to recompute its value,considering the endpoints of the remaining edges incident
on w, which are stored in S(w). When no edges remain in
S(w), candidateMate(w) becomes 0.
In a sequential computation this can be implemented
efficiently by processing the matched vertices through aqueue Q. The termination can be controlled either by thestatus of E or Q, since both become empty at the sametime. Each time an edge (u, v) is added to M , its two
endpoints u and v are added to Q. When a vertex is removed
from Q, for each one of its exposed neighbors w, S(w) andcandidateMate(w) are updated accordingly.

w

w

w

R

1

2

1

3
v

u

S
v

2
3

S
u

F

F

1

2
3

v

u

R
R
Figure 3.1: Visualization of the basic communication in the parallel matching algorithm, using a simple graph (three different stages of
the computation are illustrated).

3.2. A Simple Parallel Algorithm
We now consider how the candidate mate-based algorithm
just described can be parallelized in the simple case where
there is only one vertex mapped to a processor. (Theprocedure we describe is similar to the procedure presented
in [10] and [18]).
Three message types are used to communicate between
processors:• REQUEST—to signal a matching preference,• SUCCEEDED—to signal that a vertex has already beensuccessfully matched and is therefore no longer available for matching, and• FAILED—to signal that a vertex cannot be matched atall.
Each such message is sent across some edge (u, v), fromp(u), the processor that owns the vertex u, to p(v), theprocessor that owns the vertex v. Accordingly, each message
contains the identities of the endpoints of the correspondingedges. All communication is asynchronous and point-topoint.
The computation begins by initializing candidateMate(v)and S(v), for every vertex v, as before (the processor thatowns vertex v stores all the information about v, including
adj (v)), and by sending REQUEST(v, candidateMate(v))
messages. After that, incoming messages are processed:
processor p(v) listens as long as there still exist edges
incident on v (determined through the status of S(v)), andits further actions involve sending one of the three typesof messages. Message processing is guaranteed to remove
edges until every set S(v) becomes empty (thus E becomes
empty as well), therefore the computation is guaranteed toterminate.
For every vertex v an additional set R(v) is used in
the parallel implementation, in order to keep track of theincoming REQUEST messages. This set is initialized to ∅,can grow when REQUEST messages are received, and is
emptied when v gets matched.

We illustrate the basic communication involved in theparallel matching algorithm using the simple example shownin Fig. 3.1. In the figure, a complete graph on three vertices,u, v, w, with the weights of edges (u, v), (u, w) and(v, w) equal to 3, 2 and 1, respectively, is considered.
Initially, candidateMate(u) = v, candidateMate(v) = u,candidateMate(w) = u, and S(u) = {v, w}, S(v) ={u, w}, S(w) = {u, v}.
The graph is depicted three times, corresponding to threedifferent stages of the computation. During the first stage,
all edges are drawn with dashed lines, to indicate that they
are present and free. At this time, the initial messages
REQUEST(u, v), REQUEST(v, u) and REQUEST(w, u) aresent.
The former two REQUEST messages trigger the movement of edge (u, v) from E to M and the removal of edges(u, w) and (v, w) from E; this is indicated by drawing
the edges with solid and dotted lines, respectively, in thelast two stages of the computation. Every such handshake(two symmetric REQUEST messages) implies a locally dominant edge that must be added to M . Furthermore, S(u)becomes {w}, S(v) becomes {w}, and SUCCEEDED(u, w)
and SUCCEEDED(v, w) messages are sent during the second
stage of the computation, informing vertex w that vertices
u and v are no longer available for matching and that w
should look for some other candidate mate.
In this case w is left with no choice, S(w) becomes
empty and processor p(w) stops listening for further messages since no edge incident on w is left. However, rightbefore processor p(w) ends its part of the computation,
FAILED(w, u) and FAILED(w, v) messages are sent during
the third stage of the computation, indicating that vertex w
cannot be matched. This is required in order for S(u) andS(v) to be updated: they both become empty, which meansthat p(u) and p(v) stop listening as well.
Note that a slight variation of the computation is possible
in this example, depending on the timing of the communication. In the scenario discussed so far there is an implicit

Algorithm 3.1 Parallel Matchingprocedure PARALLEL M ATCHING(v)mate(v) ← 0
S(v) ← adj (v)R(v) ← ∅candidateMate(v) ← C OMPUTE C ANDIDATE M ATE(v)if candidateMate(v) 6= 0 thensend REQUEST to candidateMate(v)while S(v) 6= ∅ doreceive message from u ∈ S(v)if message = REQUEST then
P ROCESS R EQUEST M ESSAGE(u, v)
else if message = SUCCEEDED then
P ROCESS S UCCEEDED M ESSAGE(u, v)
else if message = FAILED thenS(v) ← S(v) \ {u}Algorithm 3.2 Process REQUEST Message
procedure P ROCESS R EQUEST M ESSAGE(u, v)
if mate(v) 6= 0 thenreturnif candidateMate(v) = u thenmate(v) ← candidateMate(v)S(v) ← S(v) \ {mate(v)}R(v) ← ∅for w ∈ adj (v) \ {mate(v)} dosend SUCCEEDED to w
else
R(v) ← R(v) ∪ {u}assumption that message SUCCEEDED(v, w) is received byprocessor p(w) before message SUCCEEDED(u, w), thus w
is really left with no choice for a candidate mate. However,if the two SUCCEEDED messages arrive in reverse order, an
opportunity is given to vertex w to consider vertex v as a
candidate mate, resulting in an additional REQUEST(w, v)
message. The final outcome of the computation is, however,the same.
This simple parallel algorithm is formalized by procedure
PARALLEL M ATCHING (Algorithm 3.1), which starts thecomputation for every vertex v and then keeps processing
incoming messages as long as S(v) is not empty. The
processing is performed by two procedures P ROCESS R E QUEST M ESSAGE and P ROCESS S UCCEEDED M ESSAGE (Algorithms 3.2 and 3.3 respectively).
Procedure C OMPUTE C ANDIDATE M ATE, omitted here,
simply computes candidateMate(v) out of S(v). Note thatat least two and at most three messages are sent across anyedge.

3.3. The General Parallel Algorithm
The general parallel algorithm (many vertices per processor), which is only briefly described here, is based on
the procedures presented so far. We refer the reader to [9]for a detailed discussion of this algorithm and its analysis.
In a similar work, Manne and Bisseling present a serial

Algorithm 3.3 Process SUCCEEDED Message
procedure P ROCESS S UCCEEDED M ESSAGE(u, v)
S(v) ← S(v) \ {u}if mate(v) 6= 0 thenreturnif candidateMate(v) = u thencandidateMate(v) ← C OMPUTE C ANDIDATE M ATE(v)if candidateMate(v) 6= 0 thensend REQUEST to candidateMate(v)if candidateMate(v) ∈ R(v) thenmate(v) ← candidateMate(v)S(v) ← S(v) \ {mate(v)}R(v) ← ∅for w ∈ adj (v) \ {mate(v)} dosend SUCCEEDED to w
else
for w ∈ adj (v) do
send FAILED to w

implementation of the Hoepman’s algorithm and discuss its
parallelization using the Bulk Synchronous Parallel (BSP)
model [18]. Our implementation is asynchronous and uses
message-aggregation to optimize communication. In addition, we provide important implementation details.
We assume that the input graph is pre-distributed ona set of processors that will be involved in computing amatching. Cross edges are represented using ghost vertices:
A boundary vertex u is stored on its corresponding processorp(u) as well as on every other processor p(v) such that (u, v)
is a cross edge. On processor p(v) vertex u represents aghost vertex.
As before, for every vertex v the algorithm maintains thevariable candidateMate(v), which becomes the true mateof v, if v gets matched, or is 0 otherwise; it also maintains
the set S(v) that keeps track of all remaining edges incident
on v. In this case, however, interior and cross edges aremaintained separately.
The parallel computation interleaves local processing forthe interior edges, with asynchronous point-to-point communication for the cross edges, handled with the same three
types of messages. As before, at least two and at most threemessages would be sent across any cross edge; however, in
our algorithm, this number of messages is reduced substantially by bundling together messages sent between the same
pair of processors, whenever possible. This is an importantfeature that distinguishes our algorithm from previous ones,
and it makes it possible for the algorithm to scale to tens of
thousands of processors.
The communication reduction is enabled by organizing
the interleaved computation as a double loop, where theinner loop corresponds to the processing of interior vertices
and the outer loop corresponds to the processing of theboundary vertices. The inner loop generates no messages
in the algorithm, although an interior vertex might haveto wait for a boundary vertex to be matched or become
available to be matched, before it can decide on its mate.

The inner loop employs a queue Q of matched vertices to beprocessed by each processor, terminating when Q becomes
empty. The outer loop seeks to match the boundary vertices,and might have to communicate with a processor owninga ghost vertex to find if a cross edge is available to bematched. In our implementation, the messages generated by
all currently unmatched boundary vertices on a processor
are sent in bundles to its neighboring processors. The
termination of the outer loop is controlled by the numberof cross edges remaining in the subgraph mapped to thecorresponding processor. The number of iterations of theouter loop required for the parallel algorithm to terminate
depends on the distribution of weights on the edges of thegraph.
In a recent related work, Patwary et al. present a parallel
greedy algorithm for the maximum (cardinality) matchingproblem [20]. We note that the maximum matching problem
is different from the maximum edge-weighted matchingproblem.

4. Parallel Coloring
The parallel coloring algorithm for which results arepresented in this paper is derived from the frameworkfor parallel greedy coloring developed in [3]. We begin
this section with a review of the essential features of theframework, and then point out aspects of the new, improved
algorithm.

4.1. The Framework
By a greedy coloring algorithm is meant an algorithm
that runs through the set of vertices in some order at eachstep assigning a vertex v the smallest color not used byany of the vertices adjacent to v (such a choice of color
is referred to as first-fit). There exist several degree-based
vertex ordering techniques that enable the greedy coloringalgorithm to use near optimal number of colors [8]. The
framework developed in [3] considered how the greedy
coloring could be efficiently parallelized on distributedmemory architectures.
Given a graph partitioned among the processors of a
distributed-memory machine, in the stated framework, eachprocessor speculatively colors the vertices assigned to it
in a series of rounds. Each round consists of a tentative
coloring and a conflict detection phase. The coloring phasein a round is further broken down into supersteps. In eachsuperstep, a processor first colors a pre-specified numbers  1 of its assigned vertices sequentially, using color
information available at the beginning of the superstep,and only thereafter exchanges recent color information withother, relevant processors. The rationale for using infrequent,coarse-grained communication (rather than communication

Algorithm 4.1 A Parallel Coloring Framework. Input: graph
G = (V, E) and superstep size s. Initial data distribution: V
is partitioned into p subsets V1 , . . . , Vp ; processor Pi owns
Vi , stores edges Ei incident on Vi , and stores the identityof processors hosting the other endpoints of Ei .
procedure PARALLEL C OLORING(G = (V, E), s)on each processor Pi , i ∈ I = {1, . . . , p}for each boundary v ∈ Vi0 = {u|(u, v) ∈ Ei } do
Assign v a random number r(v) generatedusing v’s ID as seedUi ← Vi . Ui is the current set of vertices to becoloredwhile ∃j ∈ I, Uj 6= ∅ do
if Ui 6= ∅ thenPartition Ui into `i subsets Ui,1 , . . . , Ui,`i ,each of size sfor k ← 1 to `i do . each k corresponds
to a superstep
for each v ∈ Ui,k do
assign v a “permissible” color c(v)Send colors of boundary vertices in
Ui,k to other processors
Receive color information from otherprocessors
Wait until all incoming messages are successfully received
Ri ← ∅. Ri is a set of vertices to be
re-coloredfor each boundary vertex v ∈ Ui do
if ∃ (v, w) ∈ Ei where c(v) = c(w)and r(v) < r(w) thenRi ← Ri ∪ {v}Ui ← Ri
end onafter a single vertex is colored) is to reduce the associatedcommunication cost.
If two adjacent vertices owned by two different processors
are colored in the same superstep, they may receive the samecolor and cause a conflict. In the conflict-detection phase,
therefore, each processor examines those of its boundary
vertices that are colored in the current round for consistency and identifies a set of vertices that needs to be recolored in the next round to resolve any detected conflicts.
For a given conflict-edge—a cross edge whose endpoints
have received the same color—it suffices to recolor either
one of the endpoints to resolve the conflict. In order toachieve a balanced workload distribution across processors,
the vertex to be re-colored is chosen randomly. For thispurpose a random function is defined over boundary vertices
at the beginning of the algorithm (this avoids the need forgenerating/communicating a random number each time itis needed). The conflict detection phase does not requirecommunication since by the end of the tentative coloring
phase every processor has gathered complete information
about the colors of the neighbors of its vertices. The scheme
terminates when no more conflicts to be resolved remain.
The framework is outlined more formally in Algorithm 4.1.
Several variant algorithms derived from this framework
had been implemented using MPI and experimentally analyzed in [3]. The objective of the analysis was to determine
the best way in which the various parameters of the framework need to be combined in order to reduce both runtime
and number of colors. Among the questions the analysis
attempted to answer are: How large should the superstep
size s be? Should the supersteps be run synchronously or
asynchronously? Should interior vertices be colored before,
after, or interleaved with boundary vertices? How shoulda processor choose a color for a vertex (options of strategies here include first-fit, staggered first-fit, least-used etc)?
Should inter-processor communication be customized or
broadcast-based?
Experiments were carried out on two different platforms(PC clusters) using large-size synthetic as well as real graphs
drawn from various application areas. The computational
results obtained show that, for large-size well-partitioned
graphs (have a small fraction of boundary vertices), a combination of parameters in which (i) a superstep size in the orderof a thousand is used, (ii) supersteps are run asynchronously,(iii) each processor colors its assigned vertices in an orderwhere interior vertices appear either strictly before or strictly
after boundary vertices, (iv) a processor chooses a color
for a vertex using a first-fit scheme (where the smallest
available color is chosen at each coloring step), and (v)inter-processor communication is customized gives overall
the best performance. This variant is called FIAC in [3].

4.2. The New Algorithm
The algorithm presented in this paper is an enhancementof the FIAC scheme for scalability. Like FIAC, interprocessor communication in the new algorithm is customized, but it is performed in a different way. We explain
next the difference between FIAC, the new algorithm and thebroadcast based variant FIAB. Let B be the set of boundary
vertices owned by a processor Pi , and let BS ⊆ B denote thevertices colored by Pi in a superstep S. We say a processor
Pj is neighbor to the processor Pi if processor Pj owns atleast one vertex that is adjacent to some vertex in B, andwe call Pj superstep-neighbor to Pi if Pj owns at least one
vertex that is adjacent to some vertex in BS .
• In algorithm FIAB, processor Pi sends the same message, the union of the colors of the vertices in BS , toevery other processor Pk in the system.
• In algorithm FIAC, processor Pi again sends messages to every other processor Pk in the system, buteach message (color information) is customized to theprocessor Pk . In the case where Pk does not own avertex adjacent to some vertex in BS , then the message
would be “empty”. Therefore, compared to FIAB, thisreduces the total message volume, but not the numberof messages.
• In the new algorithm, processor Pi sends customized
messages to every neighboring processor Pj . Clearly,
this reduces both the volume and the number of messages.
The implementation of the new algorithm is made available as part of the Zoltan parallel data management andload-balancing library [2].

5. Preliminary Experimental Results

For poorly-partitioned graphs (a majority of the vertices
are boundary), good performance was observed to be attainable by using a superstep size close to a hundred in item(i), a broadcast based communication mode in item (v), andby keeping the remaining parameters as in the case withwell-partitioned graphs. This variant is called FIAB in [3].

We present in this section a small set of experimental results on the improved parallel distance-1 coloring algorithm
just described and the parallel half-approximation algorithm
for edge-weighted matching discussed in Section 3.

For most of the test graphs used in the experiments in[3], algorithms FIAC and FIAB converged rapidly—within
at most six rounds—and yielded fairly good speedup when
up to a few hundred processors are used. These algorithms
were also compared with maximal independent set-based
parallel coloring algorithms of the kinds suggested by Jonesand Plassmann [11], and they were found to be consistently
superior in performance. The main reason for the better
performance is that the framework in Algorithm 4.1 uses
provably fewer or at most as many rounds as the maximal
independent set-based algorithm [3].

As inputs for this preliminary investigation on weak andstrong scalability, we use a set of synthetically generated
graphs and two real-world graphs derived from a circuit
simulation application.
The synthetic graphs are five-point grid graphs that aremodel problems for partial differential equations. In thesegraphs, a node in a two-dimensional grid is connected to its
neighbors to the east, west, north and south (except at theboundaries). These graphs are too simplistic to be reasonablechoices for experiments on either coloring or matching interms quality of solution (i.e. the number of colors used

5.1. Experimental Setup

FigureFig. 5.1

Problemmatching &coloring

Scaling
Weak

Fig. 5.2

matching &coloring

StrongFig. 5.3

matching

StrongFig. 5.4

coloring

StrongInput graphk × k grid graphs, various k
smallest: |V | ≈ 64M , |E| ≈ 128M
largest:|V | ≈ 1B, |E| ≈ 2B
32, 768 × 32, 768 grid graph
32, 000 × 32, 000 grid graph|V | ≈ 1B, |E| ≈ 2B
Circuit simulation graph1|V | ≈ 3.2M , |E| ≈ 7.7M
Circuit simulation graph2|V | ≈ 1.5M , |E| ≈ 3M
Max and Min degree: 6 and 2

Distribution
Uniform 2D

Max proc
16,384

Uniform 2D

16,384METIS(6% edge cut)
ParMETIS(40% edge cut)

4,096
4,096

Table 5.1: Overview of experimental setup and results.

and the weight of the matching obtained). For example,
exploiting the available structure, a five-point grid graph canbe colored using just two colors. Similarly, for the matchingcase, a solution close to optimal could be obtained fairly
easily, again exploiting the structure. We do not exploit thestructure of the grid graphs in our experiments. Rather, we
use the grid graphs to be able to conduct weak scalability
study, where input size needs to be increased in proportion
to the number of processors employed.
The grid graphs were generated in parallel, distributed
in a two-dimensional fashion among the available processors. Each processor owns a subgraph corresponding toan appropriate portion of the grid and is responsible forcomputational tasks on the subgraph, in coordination withneighboring processors. For instance, in an experiment withan input grid graph of size 8, 000 × 8, 000 run on 1, 024
processors (a 32 × 32 processor-grid ), each processor is
assigned a subgraph corresponding to a 250 × 250 grid. As
the input size is doubled, the number of processors is also
doubled. Hence, ideally, the runtime is expected to remain
constant. We considered k × k grid graphs for values ofk ranging from 8, 000 to 32, 000. For the experiments onmatching, the edges in the graphs were assigned random
weights. This ensured that the grid structure did not play asignificant role for the scalability study.
The two real-world test graphs, used in our experiments
on strong scalability, are generated out of a matrix obtained
from the University of Florida Sparse Matrix Collection.
The matrix (named G 3 circuit) originates from a circuit
simulation application. For the experiments on the matchingalgorithm, a bipartite graph representation of the matrix wasused, whereas for the experiments on coloring an adjacency
graph representation was used. For the experiments onmatching, the graph was distributed among the processors
using the serial partitioning software tool METIS [13].
For the experiments on the coloring algorithm, the graph
was distributed among the processors using the parallel
partitioning tool ParMETIS [14]. METIS generally gives
much superior partitioning quality compared to ParMETIS
on a large number of processors. We used these two different

partitioning tools in our experiments, instead of just theone that is more favorable to our algorithms, to show thatthe algorithms deliver good performance even for relatively
poorly distributed input data.
The coloring experiments were carried out using the
Zoltan Toolkit [2] as a base framework. The experiments
were performed on Intrepid, the IBM Blue Gene/P machineat Argonne’s Advanced Leadership Computing Facility.

5.2. Results
The scalability results we obtained are summarized in
Figure 5.1 through Figure 5.4. Table 5.1 gives a quick
overview of the experimental setup along with some of theinformation contained in the figures. The compute times
reported in Figures 5.1 to 5.4 concern total coloring or
matching time, excluding the time taken to partition the input
graph (in the case of the experiment on the circuit simulationgraphs, Figures 5.3 and 5.4) or to do I/O.
On the grid graphs, it can be seen that both the matching
and the coloring algorithm exhibited excellent scalability—
both in terms of weak (Figure 5.1) and strong (Figure 5.2)
scaling. The observed behavior is in part due to the nearideal manner in which the grid graphs are distributed acrossprocessors.
The observed scalability in the experiment on the circuit
simulation graphs (Figure 5.3 and Figure 5.4) is expectedly
less than ideal, but still highly impressive, since the graphdistribution across processors, attained here using the twograph partitioning tools METIS and ParMETIS, is far from
ideal. For example, when partitioned with METIS on 4, 096
processors (as is done in the experiment on the matchingalgorithm), nearly 6% of the edges of the circuit simulationgraph get cut (become cross edges). When partitioned using
ParMETIS on the same number of processors (as is donein the experiment on the coloring algorithm), nearly 40%of the edges of the graph get cut. The relative performancedegradation for large number of processors and the relative
performance difference on the results on matching andcoloring seen in Figures 5.3 and 5.4 reflect the impact crossedges have on overall performance.

2.00E+00

6.50E-02

ActualIdeal

6.00E-02
1.00E+00

5.00E-02
Actual

4.50E-02

Ideal
4.00E-02
3.50E-02
3.00E-02
2.50E-02
8,192 x 8,192

16,384 x 16,384

32,768 x 32,768

1,024

4,096

16,384Compute time in seconds

Compute time in seconds

5.50E-02
5.00E-01
2.50E-01
1.25E-01
6.25E-02
3.13E-02

512

1,024

2,048

4,096

8,192

16,384

Number of processors

1.06E-02

5.00E-01

9.10E-03

2.50E-01

ActualIdeal

7.60E-03
6.10E-03
Actual
4.60E-03

Ideal

3.10E-03
1.60E-03

1.00E-04
8,000 x 8,000

16,000 x 16,000

32,000 x 32,000

1,024

4,096

16,384Compute time in seconds

Compute time in seconds

Grid dimensions (top) and number of processors (bottom)

1.25E-01
6.25E-02
3.13E-02

1.56E-02
7.81E-03
512

1,024

2,048

4,096

8,192

16,384

Number of processors

Grid dimensions (top) and number of processors (bottom)

Figure 5.1: Weak scaling on various five-point grid graphs. Top,

Figure 5.2: Top: Strong scaling of the matching algorithm on amatching. Bottom, coloring.

five-point, 32, 768 × 32, 768 grid graph. Bottom: Strong scalingof the coloring algorithm on a five-point, 32, 000 × 32, 000 grid
graph. Both axes are in log scale.

6. Concluding Remarks and Outlook

2.00E+00

ActualIdeal

1.00E+00
5.00E-01
2.50E-01

Compute time in seconds

On both the grid graphs and the circuit simulation graph,the parallel matching algorithm yielded a solution in which
the sum of the weights of edges in the computed matchingremained the same, regardless of the number of processors
used. The number of colors the parallel coloring algorithm
uses varied slightly as the number of processors is varied,
but in general remained nearly the same as the number usedby the underlying serial algorithm.

1.25E-01
6.25E-02
3.13E-02
1.56E-02
7.81E-03
3.91E-03
1.95E-03
9.77E-04
4.88E-04

We plan to present in future work more comprehensive
experimental results and details that were omitted for spaceconsideration.
Emerging many-core computing platforms are likely to becomprised of cores that in turn support parallelism via multithreading. Implementations that harness the full potentialof such architectures will need to rely on the use of hybrid
distributed-memory and shared-memory programming, forexample, via the combined use of MPI and OpenMP. In
future work, we will investigate how the coloring andmatching algorithms developed here could be extended to
employ such bi-level, hybrid programming approaches.
Acknowledgments. This research was supported by the
U.S. Department of Energy through the CSCAPES Institute(grants DE-FC02-08ER25864 and DE-FC02-06ER2775),

2

4

8

16

32

64

128

256

512 1024 2048 4096

Number of processors

Figure 5.3: Strong scaling of the matching algorithm on a bipartite
graph of a circuit simulation application (roughly 3.2 million
vertices and 7.7 million edges; edge cut at 4096 processors: 6%.)
Both axes are in log scale.

and by the National Science Foundation through grants
CCF-0830645,CNS-0643969, OCI-0904809, OCI-0904802
and CNS-0403342. We are grateful to the National Energy
Research Supercomputer Center (NERSC), the Advanced
Leadership Computer Facility at Argonne National Lab,
Ohio Supercomputer Center and the Rosen Center for Advanced Computing at Purdue University for access to theterascale computers on which we have run experiments.

1.25E-01

ActualIdeal

6.25E-02

Compute time in seconds

3.13E-02
1.56E-02[10] J.-H. Hoepman. Simple distributed weighted matchings.
CoRR, cs.DC/0410047, 2004.
[11] M. Jones and P. Plassmann. A parallel graph coloringheuristic. SIAM J. Sci. Comput., 14(3):654–669, 1993.

7.81E-03

3.91E-03
1.95E-03[12] M. Jones and P. Plassmann. Scalable iterative solution ofsparse linear systems. Parallel Computing, 20(5):753–773,
1994.

9.77E-04
4.88E-04
2.44E-04
1.22E-04
6.10E-05

3.05E-05
2

4

8

16

32

64

128

256

512 1024 2048 4096

Number of processors

Figure 5.4: Strong scaling of the coloring algorithm on theadjacency graph of a circuit simulation application (roughly 1.5
million vertices and 3 million edges; edge cut at 4096 processors:40%). Both axes are in log scale.

References[1] B. Berger, R. Singh, and J. Xu. Graph algorithms forbiological systems analysis. In SODA ’08: Proceedings ofthe nineteenth annual ACM-SIAM symposium on Discretealgorithms, pages 142–151, Philadelphia, PA, USA, 2008.
[2] E. Boman, K. Devine, R. Heaphy, B. Hendrickson, V. Leung, L. A. Riesen, C. Vaughan, U. Catalyurek, D. Bozdag,
W. Mitchell, and J. Teresco. Zoltan 3.0: Parallel Partitioning,
Load Balancing, and Data-Management Services; User’s
Guide. Sandia National Laboratories, Albuquerque, NM,
2007. Tech. Report SAND2007-4748W http://www.cs.sandia.
gov/Zoltan/ug html/ug.html.
[3] D. Bozdağ, A. H. Gebremedhin, F. Manne, E. G. Boman, andU. V. Catalyurek. A framework for scalable greedy coloringon distributed-memory parallel computers. Journal of Paralleland Distributed Computing, 68(4):515–535, 2008.
[4] I. S. Duff and J. Koster. The design and use of algorithms
for permuting large entries to the diagonal of sparse matrices.
SIAM J. Matrix Anal. Appl., 20(4):889–901, 1999.
[5] I. S. Duff and J. Koster. On algorithms for permuting large
entries to the diagonal of a sparse matrix. SIAM J. Matrix
Anal. Appl., 22(4):973–996, 2000.

[13] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci.
Comput., 20(1), 1999.
[14] G. Karypis, K. Schloegel, and V. Kumar. ParMETIS: Parallelgraph partitioning and sparse matrix ordering library, version
3.1. Technical report, Dept. Computer Science, University of
Minnesota, 2003.
[15] V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, andA. Srinivasan. End-to-end packet-scheduling in wireless adhoc networks. In SODA 2004: Proceedings of the Fifteenth
Annual ACM-SIAM Symposium on Discrete Algorithms, pages
1021–1030, 2004.
[16] C. J. Langmead and B. R. Donald. High-throughput 3d
structural homology detection via nmr resonance assignment.
In CSB ’04: Proceedings of the 2004 IEEE Computational
Systems Bioinformatics Conference, pages 278–289, Washington, DC, USA, 2004. IEEE Computer Society.
[17] A. Lumsdaine, D. Gregor, B. Hendrickson, and J. W. Berry.
Challenges in parallel graph processing. Parallel Processing
Letters, 17(1):5–20, 2007.
[18] F. Manne and R. H. Bisseling. A parallel approximation
algorithm for the weighted maximum matching problem. In
The Seventh International Conference on Parallel Processing
and Applied Mathematics, pages 708–717, 2007.
[19] A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords
and generalized online matching. J. ACM, 54(5):22, 2007.
[20] M. M. A. Patwary, R. H. Bisseling, and F. Manne. Parallel
greedy graph matching using an edge partitioning approach.
In Proceedings of the fourth international workshop on Highlevel parallel programming and applications, HLPP ’10,
pages 45–54, New York, NY, USA, 2010. ACM.

[6] M. R. Garey and D. S. Johnson. Computers and Intractability.
Freeman, 1979.

[21] A. Pinar, E. Chow, and A. Pothen. Combinatorial algorithms
for computing column space bases that have sparse inverses.
Electronic Transactions on Numerical Analysis, 22:122–145,
2006.

[7] A. H. Gebremedhin, F. Manne, and A. Pothen. What color
is your Jacobian? Graph coloring for computing derivatives.
SIAM Review, 47(4):629–705, 2005.

[22] A. Pothen and C.-J. Fan. Computing the block triangular formof a sparse matrix. ACM Trans. Math. Softw., 16(4):303–324,
1990.

[8] A. H. Gebremedhin, D. Nguyen, M. M. A. Patwary, and
A. Pothen. ColPack: Graph coloring software for derivative
computation and beyond. Submitted to ACM Trans. on Math.
Softw., 2010.

[23] R. Preis. Linear time 12 -approximation algorithm for maximum weighted matching in general graphs. In 16th Ann.
Symp. on Theoretical Aspects of Computer Science (STACS),
pages 259–269, 1999.

[9] M. Halappanavar. Algorithms for vertex-weighted matchingin graphs. PhD thesis, Old Dominion University, Norfolk,
VA, 2009.

[24] Y. Saad. ILUM: A multi-elimination ILU preconditioner for
general sparse matrices. SIAM J. Sci. Comput., 17:830–847,
1996.