J. Parallel Distrib. Comput. 68 (2008) 515 – 535
www.elsevier.com/locate/jpdc

A framework for scalable greedy coloring on distributed-memory
parallel computers!
Doruk Bozdağ a , Assefaw H. Gebremedhin b , Fredrik Manne c , Erik G. Boman d,1 ,Umit V. Catalyurek a,e,∗a Department of Electrical and Computer Engineering, The Ohio State University, USAb Department of Computer Science, Old Dominion University, USAc Department of Informatics, University of Bergen, Norwayd Department of Discrete Algorithms and Math, Sandia National Laboratories, USAe Department of Biomedical Informatics, The Ohio State University, USA

Received 23 September 2006; received in revised form 26 May 2007; accepted 6 August 2007
Available online 4 September 2007

Abstract
We present a scalable framework for parallelizing greedy graph coloring algorithms on distributed-memory computers. The framework unifies
several existing algorithms and blends a variety of techniques for creating or facilitating concurrency. The latter techniques include exploiting
features of the initial data distribution, the use of speculative coloring and randomization, and a BSP-style organization of computation andcommunication. We experimentally study the performance of several specialized algorithms designed using the framework and implemented
using MPI. The experiments are conducted on two different platforms and the test cases include large-size synthetic graphs as well as realgraphs drawn from various application areas. Computational results show that implementations that yield good speedup while at the same timeusing about the same number of colors as a sequential greedy algorithm can be achieved by setting parameters of the framework in accordancewith the size and structure of the graph being colored. Our implementation is freely available as part of the Zoltan parallel data management
and load-balancing library.
© 2007 Elsevier Inc. All rights reserved.
Keywords: Graph coloring; Parallel algorithms; Distributed-memory computers; Scientific computing; Experimental algorithmics

1. Introduction
In parallel scientific computing applications, computational dependency is often modeled using a graph. A vertex! The research was supported in part by the National Science Foundation under Grants #CNS-0643969, #CCF-0342615, #CNS-0426241, #CNS0403342, NIH NIBIB BISTI #P20EB000591, Ohio Supercomputing Center#PAS0052, and by the Department of Energy’s Office of Science through the
CSCAPES SciDAC Institute.
∗ Corresponding author. Department of Biomedical Informatics, The Ohio
State University, USA. Fax: +1 614 688 6600.
E-mail addresses: bozdagd@ece.osu.edu (D. Bozdağ),assefaw@cs.odu.edu (A.H. Gebremedhin), Fredrik.Manne@ii.uib.no(F. Manne), egboman@sandia.gov (E.G. Boman), umit@bmi.osu.edu(U.V. Catalyurek).
1 Sandia is a multiprogram laboratory operated by Sandia Corporation, a
Lockheed Martin company, for the U.S. Department of Energy’s National
Nuclear Security Administration under contract DE-AC04-94AL85000.

0743-7315/$ - see front matter © 2007 Elsevier Inc. All rights reserved.
doi:10.1016/j.jpdc.2007.08.002

coloring of the graph is then used as a routine to identify independent subtasks that can be performed concurrently. Examples of cases where coloring is used for such a purpose include
iterative solution of sparse linear systems [20], preconditioners[26], sparse tiling [27], and eigenvalue computation [24]. The
computational (model) graph in such contexts is often already
distributed among processors and therefore the coloring needs
to be performed in parallel. The alternative approach of gathering the graph on one processor for a subsequent sequential
coloring (by the same processor) is prohibitively time consuming or even infeasible due to memory constraints.
Theoretical results on graph coloring do not offer much good
news: even approximating the chromatic number of a graph isknown to be NP-hard [2]. For the computational graphs mentioned earlier as well as many other graphs that arise in practice,
however, greedy, linear-time, serial coloring heuristics give solutions of acceptable quality and are often preferable to slower,

516

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

iterative heuristics that may use fewer colors. An example ofan application in which greedy graph coloring algorithms provide satisfactory solutions is the efficient computation of sparse
derivative matrices [14].
This paper is concerned with the design and implementation of efficient, parallel, greedy coloring heuristics suitablefor distributed-memory computers. The focus is on the realistic setting where the number of available processors is several
orders of magnitude less than the number of vertices in the input graph. The goal is to develop parallel algorithms that satisfy the following two requirements simultaneously. First, theexecution time of an implementation decreases with increasing
number of processors. Second, the number of colors used by aparallel heuristic is fairly close to the number used by a serial
heuristic.
Since greedy coloring heuristics are inherently sequential,
the task at hand is difficult. A similar task had been the subject of several other studies, including the works of Gjertsen
et al. [17,21]; Allwright et al. [1]; Finocchi et al. [9]; andJohansson [19]. Some of these studies reported discouraging
speedup results [1,17,21], while others relied on only simulations without providing actual parallel implementations[9,19]. In contrast, Gebremedhin, Manne, Pothen, and Woods
reported encouraging speedup results on shared-memory implementations of algorithms they developed in a series of interrelated works [12,13,15]. Gebremedhin et al. [11] extended
one of these algorithms to the Coarse Grained Multicomputermodel.
Building upon experiences from earlier efforts and introducing several new ideas, in this paper, we present a comprehensive description and evaluation of an efficient framework forparallelizing greedy coloring algorithms (preliminary results ofthis work have been presented in [4]). The basic features ofthe framework could be summarized as follows. Given a graphpartitioned among the processors of a distributed-memory machine, each processor 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 phase ina round is further broken down into supersteps in which a processor first colors a pre-specified number s?1 of its assigned
vertices sequentially and then exchanges recent color information with other, relevant processors. In the conflict-detection
phase, each processor examines those of its vertices that arecolored in the current round for consistency and identifies a setof vertices that needs to be recolored in the next round to resolve any detected conflicts. The scheme terminates when no
more conflicts remain to be resolved.
We implemented (using the message-passing library MPI)
several variant algorithms derived from this framework. The
various implementations are experimentally analyzed so as todetermine the best way in which various parameters of theframework need to be combined in order to reduce both runtime
and number of colors. With this objective in mind, we attempt
to answer the following questions. How large should the superstep size s be? Should the supersteps be run synchronouslyor asynchronously? Should interior vertices be colored before,
after, or interleaved with boundary vertices? How should aprocessor choose a color for a vertex? Should inter-processor
communication be customized or broadcast-based?
The experiments are carried out on two different PC Linuxclusters. The testbed consists of large-size synthetic graphs aswell as real graphs drawn from various application areas. The
computational results we obtained suggest that, for large-size,
structured graphs (i.e., graphs where the percentage of boundary vertices in a given partition is fairly low), a combination ofparameters in which(1) a superstep size in the order of a thousand is used,(2) supersteps are run asynchronously,(3) each processor colors its assigned vertices in an order whereinterior vertices appear either strictly before or strictly after
boundary vertices,(4) a processor chooses a color for a vertex using a First-Fit(FF) scheme, and(5) inter-processor communication is customized,
gives an overall best performance. Furthermore, the choice ofthe coloring order in (3) offers a trade-off between numberof colors and execution time: coloring interior vertices first
gives a faster and slightly more scalable algorithm whereas
an algorithm in which boundary vertices are colored first uses
fewer colors. The number of colors used even when interiorvertices are colored first is fairly close to the number used bya sequential greedy algorithm. For unstructured graphs (i.e.,graphs where the vast majority of the vertices are boundary),
good performance is observed by using a superstep size close
to a hundred in item (1), a broadcast-based communication
mode in item (5), and by keeping the remaining parameters as
in the structured case. For almost all of the test graphs usedin our experiments, the variants of our framework with theaforementioned combination of parameters converged rapidly(within at most six rounds) and yielded fairly good speedup
with increasing number of processors.
The remainder of this paper is organized as follows. In
Section 2 we discuss relevant previous work on parallel (anddistributed) coloring. In Section 3 we present the unifying parallelization framework proposed in this paper and discuss theseveral directions in which it can be specialized. In Section 4
we present extensive experimental results on our implementations of various specialized algorithms designed using theframework. We conclude in Section 5.
2. Background2.1. Sequential coloring
A coloring of a graph is an assignment of positive integers(colors) to vertices such that every pair of adjacent vertices
receives different colors. The graph coloring problem, whose
objective is to minimize the number of colors used, is known to
be NP-hard [10]. The current best known approximation ratio
log n)2
for the problem is O(n (log), where n is the number of(log n)3
vertices in the graph. Moreover, the problem is known to be
not approximable within n1/7−! for any ! > 0 [2].

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

Despite these rather pessimistic results, greedy sequential
coloring heuristics are quite effective in practice [6]. A greedy
coloring heuristic iterates over the set of vertices in some order,
at each step assigning a vertex the smallest permissible color(a FF strategy). Vertex ordering techniques that have provento be effective in practice include Largest Degree First, Smallest Degree Last, Incidence Degree, and Saturation Degree ordering; see [14] for a review of these techniques. Any greedy
heuristic that employs a FF coloring strategy uses no more (butoften many fewer) than ! + 1 colors, where ! is the maximum
degree in the graph.
2.2. Related previous work on parallel coloring
A number of the existing parallel algorithms for greedy graphcoloring rely on Luby’s algorithm for computing a maximal independent set in parallel [23]. In Luby’s algorithm, each vertex
v in the input graph is assigned a random number r(v), and an
initially empty independent set I is successively populated in
the following manner. In each iteration, if a vertex v dominates
its neighborhood N (v), i.e., if r(v) > r(w) for all w ∈ N (v),then the vertex v is added to the set I and v as well as thevertices in N (v) are deleted from the graph. This procedure isthen recursively applied on the graph induced by the remaining
vertices, and the process terminates when the graph becomes
empty, at which point I is a maximal independent set.
Luby’s parallel algorithm for computing a maximal independent set can easily be turned into a parallel (or a distributed)
coloring algorithm: Instead of removing a dominating vertex v(a vertex whose random value is larger than the value of anyof its uncolored neighbors) and its neighbors N (v) from thecurrent (reduced) graph, assign the vertex v the smallest colorthat is not used by any of its already colored neighbors. If one
proceeds in this manner, then a pair of adjacent vertices surely
gets different colors, and once assigned, the color of a vertex
remains unchanged during the course of the algorithm.
Each of the works of Jones and Plassmann [21], Gjertsen
et al. [17], and Allwright et al. [1] is essentially a variation ofthis general scheme. In each algorithm, the input graph is assumed to be partitioned among the available processors, andeach processor is responsible for coloring the vertices assigned
to it. The interior vertices on each processor are trivially colored in parallel (using a sequential algorithm on each processor), and a variant of Luby’s coloring algorithm is applied on
the interface graph, the subgraph induced by the boundary vertices. A related algorithm that could be considered here is one
in which the interface graph is built on and colored by one
processor. In Section 3.4 we discuss this variation as well as
a variant of the Jones–Plassmann algorithm [21] that we have
implemented for the purposes of experimental comparison.
In the algorithms discussed in the previous paragraph, a pairof adjacent vertices is necessarily colored at different computational steps. Thus, once the random function that is used
for determining dominating vertices has been set, the longest
monotone path in the graph gives an upper bound on the parallel runtime of the algorithm. As the work of Johansson [19]517shows, this inherent sequentiality can be overcome by using
randomization in the selection of a color for a vertex. In particular, Johansson analyzed a distributed coloring algorithm where
each processor is assigned exactly one vertex and the vertices
are colored simultaneously by randomly choosing a color fromthe set {1, . . . , ! + 1}, where ! is the maximum degree in thegraph. Since this may lead to an inconsistent coloring, the process is repeated recursively on the vertices that did not receive
permissible colors.
More recently, Finocchi et al. [9] have performed extensive(sequential) simulations on a set of inter-related algorithms thateach resemble Johansson’s algorithm. In the basic variant of
their algorithms, the upper bound on the range of permissible
colors is initially set to be smaller than ! + 1 and is increased
later only when needed. Another feature of their algorithm isthat in a post-processing step at the end of each round, Luby’salgorithm is applied on each subgraph induced by a color class.
Specifically, the post-processing step is used to find a maximal
independent set of vertices whose colors can be declared final.
2.3. Precursory work on parallel coloring
Each of the works surveyed in Section 2.2 has one or more of
the following weaknesses: (i) no actual parallel implementation
is given, (ii) the number of colors used, although bounded by! + 1, is far from the number used by a sequential greedy algorithm, or (iii) an implementation yields poor parallel speedup on
unstructured graphs. Overcoming these weaknesses had been
the subject of several previous efforts in which at least a subsetof the authors of the current paper have been involved.
Gebremedhin and Manne [12] developed a simple, sharedmemory parallel coloring algorithm that gave fairly good
speedup in practice. In their algorithm, the vertex set is equipartitioned among the available processors and each processor
colors its assigned set of vertices in a sequential fashion, at
each step assigning a vertex the smallest color not used by anyof its on- or off-processor neighbors; the assigned color information is immediately made available to other processors by
writing to shared memory. Inconsistencies—which arise only
when a pair of adjacent vertices residing on different processors
is colored simultaneously—are then detected in a subsequentparallel phase and resolved in a final sequential phase.
Gebremedhin et al. [13] extended the algorithms in [12] tothe distance-2 and star coloring problems, models that occur
in the computation of Jacobian and Hessian matrices. The algorithms in [13] also used randomized techniques in selecting
a color for a vertex to reduce the likelihood of conflicts. Gebremedhin et al. [15] enhanced these algorithms by employing
graph partitioning tools to obtain more effective assignment ofvertices to processors and by using vertex orderings to minimize cache misses in a shared-memory implementation.
In a different direction, Gebremedhin et al. [11] extended
the algorithm in [12] to the Coarse Grained Multicomputer(CGM) model of parallel computation, thus making the algorithm feasible for distributed-memory architectures as well. The
CGM model is a simplified version of the Bulk Synchronous

518

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

Parallel (BSP) model introduced by Valiant [3,32]. Besides paying attention to cost associated with non-local data access, therandomized as well as deterministic CGM-coloring algorithms
proposed in [11] differed from the shared-memory algorithm in[12] in two ways. First, in the CGM-algorithms processors exchange information only after a group of vertices (rather thana single vertex) have been colored. Second, in the CGM algorithms potential conflicts are identified a priori and dealt within a recursive fashion. The algorithms in [11] were not implemented, but we believe the first item would certainly translate
into practical gain while the second item may not, since a recursive implementation is likely to be inefficient in practice.
3. A unifying framework
Building upon ideas and experiences gained from the efforts
mentioned in Section 2.3, we have developed a framework forscalable parallel graph coloring on distributed-memory computers. In this section, we describe the framework in detail andshow how it helps unify several existing algorithms.
3.1. The basic scheme
We assume that the input graph is partitioned among the pavailable processors in some reasonable way. Typically, this isachieved by employing a graph partitioning tool such as Metis[22]. The partitioning used (regardless of how it is achieved)classifies the vertices into two categories: interior and boundary.
An interior vertex is a vertex all of whose neighbors are locatedon the same processor as itself whereas a boundary vertex has atleast one neighbor located on a different processor. Clearly, thesubgraphs induced by interior vertices are independent of eachother and hence can be colored concurrently trivially. Parallel
coloring of the remainder of graph, however, requires interprocessor communication and coordination, and is a major issue
in the scheme being described.
At the highest level, our scheme proceeds in rounds. Eachround consists of a tentative coloring and a conflict-detection
phase. In the spirit of the BSP model, the coloring phase of around is organized as a sequence of supersteps, 2 where eachsuperstep has distinct computation and communication subphases. Since the conflict-detection phase does not involve communication, it does not need to be organized in supersteps.
In every superstep, each processor colors a pre-specified
number s of vertices in a sequential fashion, using color information available at the beginning of the superstep, and thenexchanges recent color information with other processors. In
particular, in the communication phase of a superstep, a processor sends the colors of its recently colored boundary vertices toother processors and receives relevant color information fromother processors. In this scenario, if two adjacent vertices located on two different processors are colored in the same superstep, they may receive the same color and cause a conflict.
2 We use the word superstep in a looser sense than its usage in the BSP
model.

Algorithm 1. A Scalable 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 .
1: procedure SPCFramework(G = (V , E), s)2:
on each processor Pi , i ∈ I = {1, . . . , p}3:
for each bound. vtx v ∈ Vi$ = {u|(u, v) ∈ Ei } do
4:
Assign v a random number r(v) generated using
v’s ID as seed5:
Ui ← Vi ! Ui : current set of vtxs to be colored6:
while ∃j ∈ I, Uj ' = ∅ do7:
if Ui ' = ∅ then8:
Partition Ui into !i subsets
Ui,1 , Ui,2 , . . . , Ui,!i , each of size s
9:for k ← 1 to !i do10:
for each v ∈ Ui,k do
11:
assign v a “permissible” color c(v)12:Send colors of boundary vertices in Ui,kto other processors
13:
Receive color information from otherprocessors
14:
Wait until all incoming messages are successfully received
15:
Ri ← ∅ ! Ri is a set of vtxs to be recolored16:
for each boundary vertex v ∈ Ui do
17:
if ∃ (v, w) ∈ Ei where c(v) = c(w) andr(v) < r(w) then18:
Ri ← Ri ∪ {v}
19:
U i ← Ri
20:
end on21: end procedure

The purpose of the second phase of a round is to detect conflicts and accumulate on each processor a list of vertices to berecolored in the next round. Given a conflict-edge, only one ofits two endpoints needs to be recolored to resolve the conflict.
The vertex to be recolored is determined in a random fashion sothat the workload in the next round is distributed more or lessevenly among the processors; we shall shortly discuss how therandom selection is done. 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 every processor is left with an empty list ofvertices to be recolored. Algorithm 1 outlines this scheme withsome more details. The scheme is hereafter referred to as Scalable Parallel Coloring Framework (SPCFRAMEWORK).
In each round of SPCFRAMEWORK, the vertices to be recolored in the subsequent round are determined by making use of a
uniformly distributed random function over boundary vertices,
defined at the beginning of the scheme; interior vertices neednot be considered since they do not cause conflicts. For eachconflict-edge detected in a round, the vertex with the lower

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

random value is selected to be recolored while the othervertex retains its color (see the for-loop in Line 16 of
SPCFRAMEWORK). Notice that the set of vertices that retain
their colors in a round in this manner is exactly the set thatwould be obtained by running one step of Luby’s algorithm(discussed in Section 2.2) on the set of vertices involved inconflicts.
In a distributed setting such as ours, the random numbers
assigned to boundary vertices need to be computed in a careful way in order to avoid the need for communication between
processors to exchange these values. The for-loop in Line 3 of
SPCFRAMEWORK is needed for that purpose. There, notice thateach processor Pi generates random values not only for boundary vertices in its own set Vi but also for adjacent boundary
vertices residing on other processors. Since the (global) unique
ID of a vertex is used in the random number generation, therandom value computed for a vertex on one processor is thesame as the value computed for the same vertex on another processor. Thus processors avoid inquiring each other of random
values.
The coloring phase of a round is divided into supersteps(rather than communicating after a single vertex is colored) to
reduce communication frequency and thereby the associatedcost. However, the number of supersteps used (or, equivalently,
the number of vertices colored in a superstep) is also closely
related to the likelihood of conflicts and consequently the number of rounds. The lower the number of supersteps the higher
the likelihood of conflicts and hence the higher the number ofrounds required. Choosing a value for the parameter s that minimizes the overall runtime is therefore a compromise between
these two contradicting requirements. An optimal value for s
would depend on such factors as the size and density of the input graph, the number of processors available, and the machinearchitecture and network.
3.2. Variations of the scheme
SPCFRAMEWORK has been deliberately presented in a general form. Here we discuss several ways in which it can be
specialized.
3.2.1. Color selection strategies
In Line 11 of SPCFRAMEWORK, the choice of a color, permissible relative to the currently available color information,
can be made in different ways. The strategy employed affects
the number of colors used by the algorithm and the likelihoodof conflicts (and thus the number of rounds required by the algorithm). Both of these quantities are desired to be as small
as possible. A coloring strategy typically reduces one of thesequantities at the expense of the other. Here, we present two
strategies, dubbed FF and Staggered First Fit (SFF).
In the FF strategy each processor Pi chooses the smallest
permissible color from the set {1, . . . , Ci }, where Ci , initially
set to be one, is the current largest (local) color used. If no suchcolor exists, Ci is incremented by one and the new value of Ci
is chosen as a color. In contrast, the SFF strategy relies on an

519

initial estimate K of the number of colors needed for the input
graph, and each processor Pi chooses the smallest permissible
color from the set {* iK
p +, . . . , K}. If no such color exists, thenthe smallest permissible color in {1, . . . , , iK
p -} is chosen. If
there still is no such color, the smallest permissible color greaterthan K is chosen. Notice that, unlike FF, the search for a color
in SFF starts from different “base colors” for each processor.
Therefore SFF is likely to result in fewer conflicts than FF. On
a negative side, the fact that the search for a color starts froma base larger than one makes SFF likely to require more colors
than FF.
The SFF strategy is similar to the strategy used in the algorithms of Finocchi et al. [9], specifically, to the variants
they refer to as Brooks–Vizing coloring algorithms. The essential difference between their color choice strategy and SFF
is that in their approach the color for a vertex is randomly
picked out of an appropriate range, whereas in SFF the smallest available color in a similar range is searched for and chosen. Taking the comparison further, note that the formulationof SPCFRAMEWORK is general enough to encompass the (entire) algorithms of Finocchi et al. as well as the algorithm ofJohansson [19]. Specifically, one arrives at the latter algorithms
by letting the number of processors be equal to the number ofvertices in the graph (which implies a superstep size s = 1)
and by choosing the color of a vertex in Line 11 appropriately.
Other color selection strategies that can be used in
SPCFRAMEWORK include: the Least Used strategy where the(locally) least used color so far is picked so that a more evencolor distribution is achieved, and the randomized methods ofGebremedhin et al. [13].
3.2.2. Coloring order
As mentioned earlier, the subgraphs induced by interior vertices are independent of each other and can therefore be colored concurrently without any communication. As a result,in the context of SPCFRAMEWORK, interior vertices can becolored before, after or interleaved with boundary vertices.
SPCFRAMEWORK is presented assuming an interleaved order,
wherein computational load is likely to be evenly balanced andcommunication is expected to be more evenly spaced out in
time, avoiding congestion as a result. On the other hand, an interleaved order may involve communication of a higher numberof messages of smaller size, which in turn degrades execution
speed and scalability. Overall, a non-interleaved order, whereininterior vertices are colored strictly before or after boundary
vertices, is likely to yield better performance. Furthermore, coloring interior vertices first is likely to produce fewer conflicts
when used in combination with a FF coloring scheme, since thesubsequent coloring of boundary vertices is performed with alarger spectrum of available colors. Coloring boundary vertices
first might be advantageous when used together with the SFF
color selection strategy.
3.2.3. Vertex ordering strategies
Regardless of whether interior and boundary vertices arecolored in separate or interleaved order, SPCFRAMEWORK520

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

provides another degree of freedom in the choice of the orderin which vertices on each processor are colored in each round.
Specifically, in Line 10 of SPCFRAMEWORK, the given orderin which the vertices appear in the input graph, or any one of
the effective (re)ordering techniques discussed in Section 2.1
could be used.
3.2.4. Synchronous vs. asynchronous supersteps
In SPCFRAMEWORK, the supersteps can be made to run ina synchronous fashion by introducing explicit synchronization
barriers at the end of each superstep. An advantage of this modeis that in the conflict-detection phase, the color of a boundary
vertex needs to be checked only against off-processor neighbors
colored during the same superstep. The obvious disadvantage
is that the barriers, in addition to the associated overhead, causesome processors to be idle while others are busy completing
their supersteps.
Alternatively, the supersteps can be made to run asynchronously, without explicit barriers at the end of each superstep. Each processor would then only process and use thecolor information that has been completely received when it ischecking for incoming messages. Any color information thathas not reached a processor at this stage would be deferred toa later superstep. Due to this, in the conflict-detection phase,the color of a boundary vertex needs to be checked against allof its off-processor neighbors.
3.2.5. Inter-processor communication
Sending color information in Line 12 of SPCFRAMEWORK
can be done in one of two ways. First, a processor may send
the color of a boundary vertex v to another processor only if
the latter owns at least one neighbor of the vertex v. Although
this helps avoid unnecessary communication, the customization of messages incurs computational overhead. An alternative approach is for a processor to send the color informationof all of its boundary vertices to every other processor without
customizing the messages (broadcast). This approach might bemore efficient when most of the boundary vertices have neighbors on a considerable portion of the processors in the system.
3.3. How then should all these various options be combined?
As we have been discussing in Section 3.2, there are as many
as five axes along which SPCFRAMEWORK could be specialized. Each axis in turn offers at least two alternatives eachhaving its own advantages and disadvantages. The final determination of how various options need to be put together to ultimately reduce both runtime and number of colors used is boundto rely on experimentation since it involves a complex set offactors, including the size and density of the input graph, thenumber of processors employed and the quality of the initial
partitioning among the processors, and the specific characteristics of the platform on which the implementations are run. We
have therefore experimentally studied the performance of several specialized implementations of SPCFRAMEWORK on two
different platforms. The results will be presented in Section 4.

3.4. Related algorithms
For the purposes of comparison in our experiments, wehave in addition implemented three other algorithms related to
SPCFRAMEWORK. We briefly describe these algorithms in thesequel; in each case, the input graph is assumed to be alreadypartitioned among the available processors.
3.4.1. Sequential Boundary Coloring Algorithm (SBC)
In this algorithm parallel processing is applied only on interior vertices, whereas the graph induced by boundary vertices
is constructed on one dedicated processor and then colored sequentially by the same processor.
3.4.2. Sequential Conflict Resolution Algorithm (SCR)
This is a variant in which SPCFRAMEWORK is restricted to
one round, and the conflicts detected at the end of the round areresolved sequentially on one processor. Here, only the graph induced by boundary vertices involved in conflicts is constructed
on one dedicated processor and then colored sequentially by
the same processor. Note that the algorithm of Gebremedhinand Manne [12] is a special case of SCR where the superstep
size s is equal to identity.
3.4.3. Modified Jones and Plassmann Algorithm (JP)This is a synchronous variant of the Jones–Plassmann (JP)algorithm first mentioned in Section 2.2. Given a graph partitioned among the available processors, we describe the steps
applied on only boundary vertices; interior vertices are trivially colored in parallel in a final phase. In each round j of thealgorithm, each processor Pi maintains a list Di of dominating vertices—vertices that are assigned larger random numbers
than their uncolored neighbors. The vertices in the list Di arecolored sequentially (by processor Pi ) in the round j. Then,processor Pi sends the recent color information to processors
who own vertices adjacent to elements of the list Di , and receives corresponding information from other processors. For
each off-processor vertex v whose color is received, the list Di
is updated in the following manner. If the coloring of the vertex
v has made any uncolored on-processor neighbor vertex w of
the vertex v dominate the uncolored neighbors of w, then thevertex w is included in the list Di . In this way only vertices
that are dominated by off-processor neighbors will be left uncolored at the end of the round j. The procedure is repeated insubsequent rounds until all boundary vertices are colored.
We claim that SPCFRAMEWORK uses fewer or at most as
many rounds as the JP algorithm just described. Here is the argument. Suppose the two algorithms begin a particular round kwith identical sets of uncolored vertices and random values. In
SPCFRAMEWORK any vertex that needs to be recolored after theround k must have had an off-processor neighbor with the samecolor and with a larger random value. Clearly, in the JP algorithm, such a vertex would not have been colored in the roundk. Thus the JP algorithm would require at least as many rounds
as SPCFRAMEWORK. To see that SPCFRAMEWORK could use
fewer rounds than the JP algorithm, consider a vertex v where

521

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

each off-processor neighbor with a larger random value (thanthat of v) receives a different color (from that of v). Then v cankeep its color as final in SPCFRAMEWORK, whereas v would
not have been colored in the JP algorithm.
4. Experiments
This section presents results from an experimental study ofthe various algorithms discussed in the previous section. The algorithms are implemented in C using the MPI message-passing
library.

4.1. Experimental setup
Our experiments are conducted on two different platforms,
each of which is a PC cluster running Linux. Table 1 gives theessential features of the platforms.
The testbed consists of very large-size real as well as synthetic graphs. The real graphs (21 in total) are obtained fromvarious application areas, including molecular dynamics, finite
element, structural engineering, civil engineering, and automotive and ship industry [12,29,28,31]. The first four columns
in Table 2 display data concerning structural properties ofTable 1
The two platforms used in the experiments
Name

CPU

MemoryCache size

Network

Bandwidth

Latency

I2
P4

900 MHz Itanium 2
2.4 GHz Pentium 4

4 GB
4 GB

512 KB
1.5 MB

Myrinet 2000
Infiniband

240 MB/s
888 MB/s

11 "s
7 "s

Table 2
Structural properties of the real test graphs used in the experiments, classified
according to their application area and source
Name

|V |

DegreeSequential FF

Max

Avg

ColorsTI 2 (ms)Molecular dynamics [28]popc-br-4
er-gre-4
apoa1-4

24,91636,57392,224

43
42
43

20
25
25

21
19
20

28
48
120

Finite elements [12]
144
598a
auto

144,649
110,971448,695

26
26
37

15
13
15

12
11
13

137
98
462

Linear car analysis [29]bmw3_2
bmw7st1
inline1

227,362
141,347
503,712

335
434
842

49
51
72

48
54
51

561
364
1818

Structural engineering [31]pwtk
nasasrb
ct20stif

217,918
54,87052,329

179
275
206

52
48
51

48
41
49

564
130
132

Automotive [31]hoodmsdoorldoor

220,542
415,863952,203

76
76
76

48
48
48

42
42
42

541
1020
2362

Civil engineering [31]pkustk10
pkustk11
pkustk13

80,67687,804
94,893

89
131
299

52
58
69

42
66
57

213
258
317

Ship section [29]shipsec1
shipsec5
shipsec8

140,874
179,860
114,919

101
125
131

54
55
57

48
50
54

382
491
322

Also shown is the number of colors used by and the runtime of a sequential First Fit algorithm run on a single node of the Itanium 2 cluster.

522

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

Table 3Structural properties of the synthetic test graphs used in the experiments
Name

|V |

DegreeSequential FF

Max

Avg

ColorsTI 2 (ms)TP 4 (ms)40,00040,00040,000

44
61
81

40
47
59

41
42
43

127
103
87

33
40
47

Planar [25]plan-1

4,072,937

40

6

9

4780

3725

Random [18]rand-1
rand-2
rand-3rand-4400,000
400,000
400,000
400,000

27
61
84
112

10
30
50
70

9
15
20
25

461
1189
1865
2972

626
1750
2857
4074

Clique based [16]cliq-1cliq-2cliq-3

Also shown is the number of colors used by and the runtime of a sequential First Fit algorithm run on a single node of each of the two test platforms.

Table 4
Configurations of SPCFRAMEWORK used in the experiments
Name

Color choice

Coloring orderSupersteps

Communication

FIAC
FBAC
FUAC
FISC
SIAC
SBAC
FIAB
FBAB
FIAC-blockFirst Fit
First Fit
First Fit
First Fit
Staggered FF
Staggered FF
First Fit
First Fit
First Fit

Interior first
Boundary firstUn-orderedInterior first
Interior first
Boundary first
Interior first
Boundary first
Interior first

Asynchronous
Asynchronous
Asynchronous
Synchronous
Asynchronous
Asynchronous
Asynchronous
Asynchronous
Asynchronous

Customized
Customized
Customized
Customized
Customized
Customized
Broadcast
Broadcast
Customized

In each algorithm, vertices on each processor are colored in their natural order; “-block” indicates the initial data distribution is obtained via simple block
partitioning, in all other cases graph partitioning is used.

these graphs and the source application areas. The last twocolumns show certain computed values—the number of colors
used by and the runtime in milliseconds of a serial FF algorithm
run on a single node of the Itanium 2 cluster; these values will
be used as normalizing quantities in the presentation of relevant
experimental results later in this section.
The synthetic graphs used in our experiment include instances drawn from three different classes: random, planar andclique-based. The random graphs belong to the Erdös–Renyi
class and are generated using the GTgraph Synthetic Graph
Generator Suite [18]. The planar graphs are maximally planar—
the degree of every vertex is at least five—and are generatedusing the expansion method described in [25]; the generator
is a part of the graph suite for the Second DIMACS Challenge [30]. Finally, the clique-based graphs are obtained using
P. Ross’s graph-coloring generator, which is a part of the Test
Problem Generators for Evolutionary Algorithms [16]. Each of
the clique-based graphs we generated consists of 1000 cliquesof size 40 each, and the cliques are in turn interconnected byadding edges according to a probabilistic function. Table 3 displays structural information about the synthetic test graphs ina manner analogous to Table 2.

4.2. Algorithms compared
As discussed in Section 3.2, there are five orthogonal axes of
specializations for SPCFRAMEWORK. Further, there are multiple options to be considered along each axis, making the possible combinations (configurations) exponentially many. We
describe below the configurations we have considered in our
experiments either for their potential performance worth or forbenchmarking purposes.
For the initial data distribution, we consider two scenarios.
In the first scenario, the input graph is partitioned among theprocessors using the software tool Metis [22] and its VMetis
option. This option aims at minimizing both the number ofboundary vertices and the communication volume. In the second scenario, the input graph is block partitioned, a case wherethe vertex set is simply equi-partitioned among the processors
without any effort to minimize cross-edges.
For vertex ordering, we use the natural order in which vertices appear in the input graph. We forgo considering other vertex orderings, since our primary objective is to study issues thathave relevance to parallel performance. In terms of coloring order, we consider three options: coloring interior vertices first,

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

coloring boundary vertices first or coloring in an un-ordered(interleaved) fashion. Each of the remaining three axes—themanner in which a color is chosen for a vertex, supersteps
are run, and inter-processor communication is handled—offers
two options. Table 4 summarizes the configurations we haveconsidered in our experiments and the acronyms we use in referring to each.
In addition to the nine algorithms listed in Table 4, wehave implemented and tested the three algorithms—Sequential
Boundary Coloring (SBC), Sequential Conflict Resolution(SCR), and Modified Jones–Plassmann (JP)—discussed in
Section 3.4.
Another configurable parameter of SPCFRAMEWORK is thesize s of a superstep, the number of vertices sequentially colored by a processor before communication takes place. Afterseveral preliminary tests, we determined that a value of s close
to a thousand is a good choice for cases where customized communication is preferable. Similarly, for cases where broadcast
is a better choice, a value of s close to a hundred was foundto be a good choice. For the results reported in the rest of thissection, we use s = 800 for the former case and s = 125 forthe latter.
4.3. Performance profiles
For much of our experimental analysis in this section, we use
performance profiles, a generic tool introduced by Dolan andMoré [8] for comparing a set of methods over a large set of test
cases with regard to a specific performance metric. The essential idea behind performance profiles (which we review below)
is to use a cumulative distribution function for a performance
metric, instead of, for example, taking averages or sum-totals
over all the test cases.
Let S denote the set of methods (solvers) being compared, P
denote the set of test cases (problems) used, and t denote themetric of interest, which is desired to be as small as possible.
For a specific method s ∈ S and a specific problem p ∈ P ,let tp,s denote the quantity with regard to metric t used by∗ correspondmethod s in solving problem p. Similarly, let tp,Sto the best performance by any solver in S on the problem p.
For example, if the performance metric of interest is runtime ofalgorithms, then tp,s is the time used by algorithm s in solving∗ is the time used by the fastest algorithm inproblem p, and tp,S
∗ is known as the
S in solving the problem p. The ratio tp,s /tp,S
performance ratio of method s on problem p and is denoted byrp,s . The lower the value of rp,s , the closer method s is to thebest method in S for solving problem p. In particular, rp,s = 1
means that method s is the best solver in S for problem p. Now
define a function " as follows:"s (#) = |P $ |/|P | where P $ = {p ∈ P : rp,s "#}.
The value "s (#) is then the probability for solver s ∈ S thatthe performance ratio rp,s is within a factor of # of the best
possible ratio, and the function "s is the cumulative distributionfunction for the performance ratio. In the performance profileplots presented in this section we label the axis corresponding523

to "s (#) as “Fraction of wins”, to indicate that this quantity
corresponds to the fraction of the test cases for which method s
is a winner (among its competitors in S) considering a solution
within a factor of # of the best possible as the criterion forcomparison.
4.4. Results and discussion: identifying the “best” algorithms
4.4.1. Fix color choice strategy and communication mode,vary other parameters
In our first set of experiments, we compare the performance(in terms of runtime and number of colors) of configurations of
SPCFRAMEWORK obtained by fixing the color selection strategy
to be FF and the communication mode to be Customized andby varying the remaining three parameters listed in Table 4.
Fig. 1 shows runtime performance profile plots (for various
number of processors) of the resulting five algorithms, FIAC,FISC, FBAC, FUAC, and FIAC-block. Fig. 2 shows similarplots for number of colors, where, in addition to these fiveparallel algorithms, a sequential FF algorithm is included as abaseline. The test set in both figures is the set of applicationgraphs listed in Table 2 and the experiments are conducted on
the Itanium 2 cluster.
We illustrate how performance profiles are to be “read” using
Fig. 1(c) as an example. In that example, one can see that fornearly every testcase, FIAC has the least runtime among the fivealgorithms being compared (see the values on the vertical line
# = 1). In almost 90% of the cases, FISC is nearly equally fast.
Suppose we are interested in identifying methods that would
solve every testcase within a factor of 1.2 of the best time. ThenFBAC would clearly join the company of FIAC and FISC. In
general, Fig. 1 clearly shows that Algorithms FIAC and FISC
are the fastest among the five for every value of p and are almost
indistinguishable from each other. The two algorithms are very
closely followed by FBAC.
In terms of number of colors, Fig. 2 shows that FBAC isthe best candidate. Its performance is almost as good as thesequential algorithm. A major reason for this rather impressive
performance is that algorithm FBAC has the flavor of a Largest
Degree First sequential algorithm, since vertices of large degree
are in general likely to be boundary vertices in a partition,and these are colored first in the FBAC configuration. In thesequential baseline algorithm, on the other hand, vertices arecolored in their natural order. Further in Fig. 2, we observe thatalgorithms FUAC, FIAC, and FISC have fairly similar behavior
with each other, and in general use 5–15% more colors than thatused by the sequential algorithm. This in itself is a rather “good”
performance considering the facts that the number of colors
used by a sequential algorithm is very close to the average
degree in the test graphs (see Table 2) and that existing parallel(distributed) coloring algorithms commonly try to only boundthe number by maximum degree.
Based on observations made from Figs. 1 and 2, we pickthe two algorithms FIAC and FBAC as the most preferredchoices, which in turn offer a runtime-quality tradeoff. We use
these algorithms in the rest of the experiments described in thissection.

524

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

0.6
0.5
0.4
0.3

0.6
0.5
0.4
0.3

FIAC
FISC
FBAC
FUAC
FIAC−block

0.2
0.1

FIAC
FISC
FBAC
FUAC
FIAC−block

0.2
0.1

0

0
1

2

3

4

5

6

1

2

3

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6
0.5
0.4
0.3

5

6

0.6
0.5
0.4
0.3

FIAC
FISC
FBAC
FUAC
FIAC−block

0.2
0.1

FIAC
FISC
FBAC
FUAC
FIAC−block

0.2
0.1

0

0
1

2

3

4

5

6

1

2

3

τ

4

5

6

τ

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

4τFraction of wins

Fraction of wins

τ

0.6
0.5
0.4
0.3

0.6
0.5
0.4
0.3

FIAC
FISC
FBAC
FUAC
FIAC−block

0.2
0.1

FIAC
FISC
FBAC
FUAC
FIAC−block

0.2
0.1

0

0
1

2

3

4
τ

5

6

1

2

3

4

5

6

τ

Fig. 1. Algorithms compared: five variants of SPCFRAMEWORK. Plots: performance profiles. Metric: runtime. Test set: (a) through (e), application graphs
listed in Table 2; (f), set of all processor–graph pairs (p, G), for p ∈ {8, 16, 24, 32, 40} and G drawn from Table 2. Platform: Itanium 2. s = 800. (a) p = 8,(b) p = 16, (c) p = 24, (d) p = 32, (e) p = 40, (f) p ∈ {8, 16, 24, 32, 40}.

525

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

0.6
0.5
0.4
0.3

0.1

0.5
0.4
0.3

FIAC
FISC
FBAC
FUAC
FIAC−block
Sequential

0.2

0.6

FIAC
FISC
FBAC
FUAC
FIAC−block
Sequential

0.2
0.1

0

0
1

1.05

1.1

1.15

1.2

1.25

1

1.05

1.1

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6
0.5
0.4
0.3

1.2

1.25

0.1

0.6
0.5
0.4
0.3

FIAC
FISC
FBAC
FUAC
FIAC−block
Sequential

0.2

FIAC
FISC
FBAC
FUAC
FIAC−block
Sequential

0.2
0.1
0

0
1

1.05

1.1

1.15

1.2

1.25

1

1.05

1.1

τ

1.15

1.2

1.25

τ

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

1.15
τFraction of wins

Fraction of wins

τ

0.6
0.5
0.4
0.3

FIAC
FISC
FBAC
FUAC
FIAC−block
Sequential

0.2
0.1

0.6
0.5
0.4
0.3

FIAC
FISC
FBAC
FUAC
FIAC−block
Sequential

0.2
0.1
0

0
1

1.05

1.1

1.15
τ

1.2

1.25

1

1.05

1.1

1.15

1.2

1.25

τ

Fig. 2. Algorithms compared: five variants of SPCFRAMEWORK. Plots: performance profiles. Metric: number of colors. Test set: (a) through (e), applicationgraphs listed in Table 2; (f), set of all processor–graph pairs (p, G), for p ∈ {8, 16, 24, 32, 40} and G drawn from Table 2. Platform: Itanium 2. s = 800.
(a) p = 8, (b) p = 16, (c) p = 24, (d) p = 32, (e) p = 40, (f) p ∈ {8, 16, 24, 32, 40}.

526

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

0.6
0.5
0.4
0.3

0.1

0.4

FIAC
FBAC
JP
SCR
SBC

0.2
0.1

0

0
1

2

3

4

5
τ

6

7

8

9

1

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

0.5

0.3
FIAC
FBAC
JP
SCR
SBC

0.2

0.6
0.5
0.4

2

3

4

5
τ

6

7

8

9

0.6
0.5
0.4
0.3

0.3
FIAC
FBAC
JP
SCR
SBC

0.2
0.1

FIAC
FBAC
JP
SCR
SBC

0.2
0.1
0

0
1

2

3

4

5
τ

6

7

8

9

1

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

0.6

0.6
0.5
0.4

2

3

4

5
τ

6

7

8

9

0.6
0.5
0.4
0.3

0.3
FIAC
FBAC
JP
SCR
SBC

0.2
0.1

FIAC
FBAC
JP
SCR
SBC

0.2
0.1

0

0
1

2

3

4

5
τ

6

7

8

9

1

2

3

4

5
τ

6

7

8

9

Fig. 3. Algorithms compared: two variants of SPCFRAMEWORK (FIAC and FBAC) and algorithms SCR, SBC and JP. Plots: performance profiles. Metric:
runtime. Test set: (a) through (e), graphs listed in Table 2; (f), set of all processor–graph pairs (p, G), for p ∈ {8, 16, 24, 32, 40} and G drawn from Table 2.
Platform: Itanium 2. s = 800. (a) p = 8, (b) p = 16, (c) p = 24, (d) p = 32, (e) p = 40, (f) p ∈ {8, 16, 24, 32, 40}.

527

1

1

0.9

0.9

0.8

0.8

0.7

0.7

Fraction of wins

Fraction of wins

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

0.6
0.5
0.4
0.3

0.1

0.4
FIAC
FBAC
JP
SCR
Sequential

0.2
0.1

0

0
1

1.05

1.1

1.15
τ

1.2

1.25

1

1

1

0.9

0.9

0.8

0.8

0.7

0.7

Fraction of wins

Fraction of wins

0.5

0.3
FIAC
FBAC
JP
SCR
Sequential

0.2

0.6
0.5
0.4
0.3

1.05

1.1

1.15
τ

1.2

1.25

0.6
0.5
0.4
0.3

FIAC
FBAC
JP
SCR
Sequential

0.2
0.1

FIAC
FBAC
JP
SCR
Sequential

0.2
0.1

0

0
1

1.05

1.1

1.15
τ

1.2

1.25

1

1

1

0.9

0.9

0.8

0.8

0.7

0.7

Fraction of wins

Fraction of wins

0.6

0.6
0.5
0.4

1.05

1.1

1.15
τ

1.2

1.25

0.6
0.5
0.4
0.3

0.3
FIAC
FBAC
JP
SCR
Sequential

0.2
0.1

FIAC
FBAC
JP
SCR
Sequential

0.2
0.1
0

0
1

1.05

1.1

1.15
τ

1.2

1.25

1

1.05

1.1

1.15
τ

1.2

1.25

Fig. 4. Algorithms compared: two variants of SPCFRAMEWORK (FIAC and FBAC) and algorithms SCR, JP and Sequential. Plots: performance profiles.
Metric: number of colors. Test set: (a) through (e), graphs listed in Table 2; (f), set of all processor–graph pairs (p, G), for p ∈ {8, 16, 24, 32, 40} and G
drawn from Table 2. Platform: Itanium 2. s = 800. (a) p = 8, (b) p = 16, (c) p = 24, (d) p = 32, (e) p = 40, (f) p ∈ {8, 16, 24, 32, 40}.

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Fraction of wins

Fraction of wins

528

0.6
0.5
0.4

0.6
0.5
0.4
0.3

0.3
0.2
0.1

SIAC
FIAC
SBAC
FBAC
Sequential

0.2

SIAC
FIAC
SBAC
FBAC

0.1
0

0
1

1.05

1.1

1.15

1.2
τ

1.25

1.3

1.35

1.4

1

1.05

1.1

1.15
τ

1.2

1.25

Fig. 5. Algorithms compared: variants xIAC and xBAC of SPCFRAMEWORK where the color selection strategy x is either F (First Fit) or S (Staggered FF).
Plots: performance profiles. Test set: application graphs listed in Table 2. Platform: Itanium 2, p = 40, s = 800. (a) Runtime, (b) number of colors.

30

30
FIAC ldoor
FIAB ldoor
FIAC rand−1
FIAB rand−1
FIAC rand−4
FIAB rand−4

25

20

20
SpeedupSpeedup

25

FIAC ldoor
FIAB ldoor
FIAC rand−1
FIAB rand−1
FIAC rand−4
FIAB rand−4

15

15

10

10

5

5

0

0
0

5

10

15
20
25
30
Number of processors

35

40

0

5

10

15
20
25
30
Number of processors

35

40

Fig. 6. Algorithms compared: variant FIAx of SPCFRAMEWORK where the communication mode x is either Customized (C) or Broadcast-based (B). Plots:
standard. Metric: speedup. For FIAC, s = 800; for FIAB, s = 125. (a) Itanium 2, (b) Pentium 4.

4.4.2. Comparison with related algorithms
In our second set of experiments, whose results are summarized in the performance profile plots shown in Figs. 3 and4, we compare FIAC and FBAC with the three other algorithms in our study: JP, SCR, and SBC. A more elaborate setof experimental data comparing these algorithms is available in
Tables A1–A5 in the Appendix.
The conclusion to be drawn from the runtime plots in
Fig. 3 is straightforward: algorithms FIAC and FBAC significantly outperform their competitors, which could further beranked in a decreasing order of execution speed as SCR, JP,
and SBC. The underlying reasons for this phenomenon are
obvious, but it is worth pointing out that the relative slownessof the JP algorithm is due to the many rounds it requires.
In terms of number of colors, Fig. 4 shows that, in general,
algorithms JP and SCR use (slightly) fewer colors than both
FBAC and FIAC. Notice that the difference in the quality ofthe solution obtained by the various algorithms here is fairly
marginal: the # values for more than 90% of the test cases range
between 1 and 1.15, indicating that the worst algorithm (FIAC)

529

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

30

30
ldoor
inline1
pwtk
shipsec5
apoa1− 4

15
10
5

5

10

10 15 20 25 30 35 40
Number of processors

0

15
10
5

20
15
10

1.2
1.1
1
0.9
ldoor
inline1
pwtk
shipsec5
apoa1− 4

0.8
0.7
0

5

10 15 20 25 30 35 40
Number of processors

15
10

0
0

5

10 15 20 25 30 35 40
Number of processors

1.2
1.1
1
0.9
ldoor
inline1
pwtk
shipsec5
apoa1− 4

0.8
0.7
0

5

0

Normalized number of colors

10 15 20 25 30 35 40
Number of processors

Normalized number of colors

5

20

5

0
0

10 15 20 25 30 35 40
Number of processors

ldoor
inline1
pwtk
shipsec5
apoa1− 4

25

5

0

5

30
ldoor
inline1
pwtk
shipsec5
apoa1− 425
Speedup20

10

10 15 20 25 30 35 40
Number of processors

Speedup

25

15

0
5

30
ldoor
inline1
pwtk
shipsec5
apoa1− 4

20

5

0

30

Speedup15

00Normalized number of colors

20

5

0

ldoor
inline1
pwtk
shipsec5
apoa1− 425
Speedup20

25
SpeedupSpeedup

25

30
ldoor
inline1
pwtk
shipsec5
apoa1− 4

10 15 20 25 30 35 40
Number of processors

5

10 15 20 25 30 35 40
Number of processors

1.2
1.1
1
0.9
ldoor
inline1
pwtk
shipsec5
apoa1− 4

0.8
0.7
0

5

10 15 20 25 30 35 40
Number of processors

Fig. 7. Performance on select application graphs using s = 800. (a) FIAC on I2, (b) FBAC on I2, (c) JP on I2, (d) FIAC on P4, (e) FBAC on P4, (f) JP on
P4, (g) FIAC, (h) FBAC, (i) JP.

uses in the worst case, only 15% more colors than that used by
the best algorithm (JP).
4.4.3. Effects of color selection
The purpose of our third set of experiments is to compare
the FF and SFF color selection strategies while using the xIAC
and xBAC configuration, i.e., algorithms FIAC, SIAC, FBAC
and SBAC. For SFF, we used the number of colors obtainedby running the sequential FF algorithm as our estimate for K.
Fig. 5 shows performance profile plots corresponding to theseexperiments.

As can be seen in Fig. 5(a), there is little difference in runtime
between FF and SFF when used in combination with an interiorfirst coloring order (xIAC), but with boundary-first ordering(xBAC), SFF is slightly faster. This is expected since SFF islikely to involve fewer conflicts than FF. Fig. 5(b) shows, again
as expected, that SFF uses more colors than FF in both cases.
4.4.4. Effects of communication mode
In the fourth set of experiments we consider the FIAC and
FIAB configurations in order to compare the two communication modes, Customized and Broadcast. We consider threeD. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

5

10

15

20

25

30

35

40

0

5

0

5

10

15

20

25

30

35

40

0

Normalized number of colors

Normalized number of colors

25

30

35

40

1.1
1.05
1
0.95
plan −1
rand−1
rand−4cliq− 1cliq−3

0.8
5

10

15

20

25

30

Number of processors

5

5

10

15

20

25

30

10

35

35

40

25

30

35

40

0

5

10

15

20

25

30

35 40

Number of processors

1.1
1.05
1
0.95
plan −1
rand−1
rand−4cliq− 1cliq−30.85

20plan −1
rand−1
rand−4cliq−1cliq−3

50
45
40
35
30
25
20
15
10
5
0

40

1.15

0.9

15

Number of processors

0.8
0

0

Number of processors

1.15

0.85

20

plan −1
rand−1
rand−4cliq−1cliq−3

50
45
40
35
30
25
20
15
10
5
0

Number of processors

0.9

15

Speedupplan −1
rand−1
rand−4cliq− 1cliq−3

50
45
40
35
30
25
20
15
10
5
0

10

plan −1
rand−1
rand−4cliq−1cliq−3

50
45
40
35
30
25
20
15
10
5
0

Number of processors

SpeedupSpeedup

Number of processors

Normalized number of colors

0plan −1
rand−1
rand−4cliq− 1cliq−3

50
45
40
35
30
25
20
15
10
5
0

Speedupplan −1
rand−1
rand−4cliq−1cliq−3

50
45
40
35
30
25
20
15
10
5
0

SpeedupSpeedup

530

1.15
1.1
1.05
1
0.95
plan −1
rand−1
rand−4cliq−1cliq−3

0.9
0.85
0.8

0

5

10

15

20

25

30

Number of processors

35

40

0

5

10

15

20

25

30

35

40

Number of processors

Fig. 8. Performance on select synthetic graphs using s = 125. (a) FIAB on I2, (b) FBAB on I2, (c) JP on I2, (d) FIAB on P4, (e) FBAB on P4, (f) JP on
P4, (g) FIAB, (h) FBAB, (i) JP.

graphs: the largest application graph ldoor from Table 2 andthe two random graphs rand-1 and rand-4 (which are of varying density) from Table 3. These examples are chosen to be
representatives of well partitionable (requiring low communication) and poorly partitionable (requiring high communication) graphs. As can be seen in the tables in the Appendix, theratio of boundary vertices to total vertices for p = 24 (say) is
only 4% for ldoor whereas it is nearly 100% for the randomgraphs.
Fig. 6 shows speedup plots for algorithms FIAC and FIAB
on the two test platforms Itanium 2 and Pentium 4. One cansee that the difference in performance between FIAB and FIAC
is negligible for the well-partitionable graph ldoor, whereas

FIAB is in general better than FIAC for the random graphs, thedifference being more pronounced for the denser graph rand-4.
4.5. Results and discussion: scalability
From the four set of experiments we have discussed thus far,
we can fairly conclude that algorithms FIAC and FBAC are
the best choices (offering runtime-quality tradeoff) for wellpartitionable graphs, while the corresponding choices for poorly
partitionable graphs are FIAB and FBAB. The results we presented so far showed how the various algorithms comparedagainst each other, but not the performance of each considered separately. We now present results where the latter aspect531

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

110

110
JP−random
FIAB−random
JP−planar
FIAB−planar

100

90

80

Normalized run time

Normalized run time90

JP−random
FIAB−random
JP−planar
FIAB−planar

100

70
60
50
40
30

80
70
60
50
40
30

20

20

10

10

0

0
0

5

10

15
20
25
30
Number of processors

35

40

0

5

10

15
20
25
30
Number of processors

35

40

Fig. 9. Weak scaling of algorithms FIAB and JP on select synthetic graphs, s = 125. (a) Itanium 2, (b) Pentium 4.

is addressed for the configurations FIAC, FBAC, FIAB and
FBAB.
4.5.1. Strong scalability
Application graphs: Figs. 7(a) through (c) show strong scalability results regarding algorithms FIAC, FBAC, and JP on
five test graphs drawn from Table 2. The test graphs are selected from five different application areas, and each graph isthe largest in its group. The test platform used is Itanium 2. A
similar set of results for the Pentium 4 platform is shown in
Figs. 7(d)–(f). Figs. 7(g)–(i) show the number of colors usedby the three algorithms, each normalized with respect to thenumber obtained using a sequential FF algorithm.
The results in Fig. 7 show that both FIAC and FBAC scale
well for these graphs in both platforms. In general we observe higher speedup for sparser graphs. The JP algorithm
showed some speedup, albeit small, largely due to the wellpartitionability of the graphs. We also observe that the numberof colors used by the three algorithms is fairly close the number
used by a sequential algorithm.
Synthetic graphs: Fig. 8 shows a set of figures similar to
those shown in Fig. 7, except now that the algorithms considered are FIAB, FBAB and JP and the test graphs are fivesynthetic graphs drawn from Table 3. One of the five graphs,
planar-1, is extremely well partitionable (almost all of its vertices are interior in a given partition, see Table A4). The opposite is true for the other four graphs, rand-1, rand-4, cliq-1 andcliq-3.
The strong scalability results in Figs. 8(a) through (f) agree
well with one’s expectation: good speedup on well-partitionablegraphs and poor speedup on poorly partitionable graphs. The
fact that both FIAB and FBAB actually yielded some reason-

able speedup (especially on the P4 platform) for the random
and clique-based graphs, however, is worth emphasizing: forsuch graphs the speedup stems solely from the “core” algorithm in SPCFRAMEWORK, without any contribution from parallelization due to partitioning.
The speedup results in Figs. 7 and 8 also show how thenature of a platform affects the performance of the algorithms.
For poorly partitionable graphs, where relatively high interprocessor communication is needed due to the large number ofboundary vertices, the Pentium 4 cluster with its lower latency
and higher network bandwidth, gave better scalability. For wellpartitionable graphs, on the other hand, although linear or evensuper-linear speedup can be achieved on both platforms, theItanium 2 cluster was observed to be a better environment,
primarily due to its larger cache.
4.5.2. Weak scalability
Our final experimental result is on weak scalability, where
both problem size and number of processors are increased inproportion so as to result in nearly constant runtime. Fig. 9shows weak scaling result on random and planar graphs. (Thecomplete experimental data are available in Table A5.)
From Fig. 9 we observe that runtime grows slowly with increasing number of processors for both JP and FIAB on planargraphs, but there is a dramatic difference for random graphs.
While FIAB takes only slightly more than a constant time onplanar graphs, the runtime for JP grows almost linearly withnumber of processors. This demonstrates that our framework(FIAB in particular) is clearly more scalable than JP on random graphs. This is due to the large number of boundary vertices, where JP performs poorly due to the many rounds it
requires.

532

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

5. Conclusion

algorithm whereas an algorithm in which boundary vertices arecolored first uses fewer colors.
Our implementation has been incorporated into Zoltan, afreely available parallel data management and load-balancing
library [7]. We plan to extend our work to other coloring problems such as the distance-2 graph coloring and the hypergraphcoloring problems, which arise in the efficient computation ofderivative matrices. A preliminary work we have done on parallel distance-2 coloring is available in [5].

We have developed an efficient and scalable parallel graphcoloring algorithmic framework suitable for distributedmemory computers. The framework is tunable to suit thestructure of the graph being colored and the specifics of the
hardware being used.
The scalability of several algorithms developed using theframework has been experimentally demonstrated on platformsof modest size processors. For almost all graphs tested in our
experiments, the variants of our framework yielded fairly good
speedup with increasing number of processors and the numberof colors used was close to the number used by a sequential
greedy algorithm. Furthermore, we observed that customizing
inter-processor communication and using a superstep size inthe order of a thousand improved the scalability of the algorithms for structured graphs. For unstructured graphs, good performance was observed by using a broadcast-based communication mode and using a superstep size close to a hundred. The
computational results we obtained also suggest that, coloring
interior vertices first gives a faster and slightly more scalable

Acknowledgments
We thank the anonymous reviewers for their valuable comments that helped us improve the paper significantly.
Appendix A.
A set of experimental data comparing FIAC and FBAC withthe three other algorithms in our study: JP, SCR, and SBC isshown in Tables A1–A5.

Table A1
Comparison of algorithms for the application graphs on the Itanium 2 cluster
using s = 800 and p = 8
Name

SpeedupColorsRounds

FIAC

FBAC

JP

SCR

SBC

FIAC

FBAC

JP

SCR

FIAC

FBAC

JP

popc-br-4
er-gre-4
apoa1-4

4.5
4.7
5.3

3.7
4.4
5.0

2.5
3.3
4.0

4.6
4.7
5.0

2.6
2.2
2.9

21
22
21

20
19
20

19
19
20

20
19
20

4
4
5

4
5
5

22
21
22

144
598a
auto

5.8
6.2
6.4

5.6
5.9
6.3

5.1
5.2
5.2

6.0
6.1
7.0

4.3
4.6
5.6

13
12
13

12
12
13

12
11
13

12
11
13

4
4
4

4
4
5

bmw3_2
bmw7st1
inline1

6.6
6.5
6.9

6.3
6.1
6.3

5.6
5.4
5.0

6.6
6.6
6.8

4.9
4.7
5.6

51
54
58

48
53
52

48
52
51

48
54
51

5
5
5

pwtk
nasasrb
ct20stif

6.8
6.0
5.4

6.7
5.6
4.3

6.0
4.5
3.8

6.8
6.1
5.4

5.8
4.0
3.1

45
38
49

43
40
50

42
40
48

45
40
49

hood
msdoor
ldoor

6.9
7.1
7.3

6.8
6.8
7.1

5.8
6.0
6.1

7.0
7.2
7.3

6.0
6.3
6.8

45
42
47

42
42
43

42
42
43

pkutsk10
pkutsk11
pkutsk13

6.1
6.0
5.8

5.6
5.7
5.2

4.6
4.5
4.2

6.0
5.9
5.6

3.6
3.3
2.9

50
66
57

46
66
57

shipsec1
shipsec5
shipsec8

6.2
6.1
6.0

6.1
5.8
5.7

5.1
5.2
4.8

6.1
6.1
6.0

4.0
3.9
3.7

53
54
54

50
48
50

|VB | denotes the total number of boundary vertices after partitioning.

|VB |
(%)
|V |

time on VB(%)
total time
FIAC

FBAC

JP

22
27
18

56
56
43

56
56
43

67
66
53

14
13
14

10
9
6

34
30
28

33
30
27

39
38
39

5
6
5

30
31
45

6
6
4

20
21
16

20
23
19

26
31
25

5
5
5

6
5
5

30
30
39

3
10
15

15
29
43

12
29
50

22
43
55

42
42
42

5
5
5

5
5
5

29
29
29

3
2
2

14
11
8

12
12
8

23
16
21

45
66
57

46
66
57

5
5
4

7
5
5

39
43
46

12
13
16

30
35
38

33
35
41

45
48
52

48
49
48

50
51
50

6
5
5

6
5
6

36
36
39

10
10
13

28
29
33

27
28
32

39
36
44

533

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535
Table A2
Comparison of algorithms for the application graphs on the Itanium 2 cluster using s = 800 and p = 24
Name

SpeedupColorsRounds

FIAC

FBAC

JP

SCR

SBC

FIAC

FBAC

JP

SCR

FIAC

FBAC

JP

popc-br-4
er-gre-4
apoa1-4

6.1
7.4
9.8

4.8
6.1
9.0

1.5
3.2
4.8

4.3
4.9
6.8

1.9
1.6
2.2

20
20
21

20
20
20

20
21
21

19
20
20

4
4
5

5
5
5

22
20
25

144
598a
auto

12.3
11.8
15.2

10.4
9.7
13.4

7.2
6.8
9.3

8.5
8.2
11.9

3.9
3.9
5.6

13
12
14

13
12
13

13
11
13

12
12
13

4
4
4

5
5
5

bmw3_2
bmw7st1
inline1

16.1
14.9
17.0

14.4
12.9
15.2

9.6
3.6
8.7

13.3
12.8
14.8

5.3
4.6
5.4

49
49
57

49
52
52

48
48
51

48
54
52

5
5
6

pwtk
nasasrb
ct20stif

16.6
11.8
10.4

14.8
10.1
8.4

10.4
5.0
3.7

12.6
8.2
7.7

5.4
2.7
2.3

45
45
54

43
41
51

41
39
47

44
38
48

hood
msdoor
ldoor

17.2
18.0
19.0

15.6
16.8
18.3

10.0
11.2
12.2

15.3
17.1
18.3

6.5
9.2
11.0

43
46
49

42
42
42

42
42
42

pkutsk10
pkutsk11
pkutsk13

13.0
12.5
12.3

11.1
10.7
9.9

6.3
7.0
7.5

9.6
9.3
9.2

2.9
2.2
2.3

48
66
57

45
65
57

shipsec1
shipsec5
shipsec8

13.8
14.5
13.2

11.8
12.7
11.3

7.7
8.3
6.2

9.4
10.2
9.0

3.1
3.5
2.8

50
53
55

48
52
53

|VB |
(%)
|V |

time on VB(%)
total time
FIAC

FBAC

JP

37
43
32

82
81
71

81
83
68

81
91
83

15
13
15

18
17
13

58
61
49

61
64
51

73
76
65

5
6
6

31
34
58

11
13
10

38
44
35

38
47
36

59
48
64

5
5
5

6
5
6

32
32
43

11
25
27

36
63
69

38
63
66

58
83
84

42
42
42

5
5
6

6
5
6

31
30
32

8
5
4

32
27
22

34
28
21

58
52
48

44
62
57

47
61
57

5
5
5

5
5
6

33
48
49

23
26
29

58
64
64

58
64
65

76
83
82

47
49
47

47
48
49

5
5
5

6
6
5

36
37
40

21
18
24

53
49
57

54
51
58

71
67
90

|VB |
(%)
|V |

time on VB(%)
total time

|VB | denotes the total number of boundary vertices after partitioning.

Table A3
Comparison of algorithms for the application graphs on the Itanium 2 cluster using s = 800 and p = 40
Name

SpeedupColorsRounds

FIAC

FBAC

JP

SCR

SBC

FIAC

FBAC

JP

SCR

FIAC

FBAC

JP

popc-br-4
er-gre-4
apoa1-4

5.4
6.8
11.2

4.5
6.5
10.3

1.2
2.1
4.5

3.0
3.9
5.9

1.5
1.3
1.8

22
21
21

21
20
20

19
20
20

20
18
20

4
5
5

5
5
5

24
24
22

144
598a
auto

13.1
11.6
19.6

12.0
10.5
16.5

6.2
5.4
14.4

7.8
7.1
12.2

3.3
3.3
4.8

13
13
14

12
12
13

12
11
13

12
11
13

5
5
4

5
5
5

bmw3_2
bmw7st1
inline1

21.8
19.2
24.1

18.6
15.2
19.9

9.2
7.5
9.9

14.5
12.6
16.7

4.3
3.6
4.5

48
54
57

48
48
55

48
49
51

48
53
51

5
5
5

pwtk
nasasrb
ct20stif

21.1
13.2
11.8

19.4
10.9
10.3

10.4
4.6
3.6

12.6
7.2
7.2

4.1
2.1
1.8

47
43
52

44
40
51

42
38
48

44
39
48

hood
msdoor
ldoor

23.6
26.1
27.8

20.2
23.9
27.3

10.8
10.9
15.2

17.1
21.3
24.3

5.5
8.4
10.1

45
47
47

42
42
42

42
42
42

pkutsk10
pkutsk11
pkutsk13

14.7
14.8
15.9

14.6
13.7
13.8

5.0
4.3
4.9

9.4
8.8
9.3

2.5
1.8
1.8

48
64
58

47
60
57

shipsec1
shipsec5
shipsec8

17.9
19.7
16.6

15.2
16.6
14.7

6.5
8.4
6.0

9.7
10.7
9.2

2.6
2.9
2.2

53
54
54

50
53
52

|VB | denotes the total number of boundary vertices after partitioning.

FIAC

FBAC

JP

46
51
38

91
90
81

90
89
78

97
97
91

17
15
16

22
22
16

75
78
62

74
78
64

87
88
76

6
7
6

34
35
57

14
19
14

52
59
48

51
63
51

76
81
77

6
5
5

6
6
5

34
33
43

16
32
36

54
77
81

55
77
77

78
94
94

42
42
42

5
5
6

6
5
5

30
40
31

11
7
5

46
37
32

49
38
31

74
72
61

44
58
57

48
62
57

6
6
5

5
5
5

39
55
54

28
33
37

73
77
75

68
72
72

89
91
90

45
49
50

49
50
51

5
5
6

6
6
5

44
38
42

26
23
29

66
61
70

66
62
68

85
81
87

534

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535

Table A4
Comparison of algorithms for the synthetic graphs using s = 125
p

Name

|VB |
(%)
|V |

Colors
FIAC

FBAC

JP

FIAC

FBAC

JP

FIAC

FBAC

JP

Speedup on Itanium 2

Speedup on Pentium 4

8rand-1
rand-2
rand-3rand-4plan-1cliq-1cliq-2cliq-3

99.5
100.0
100.0
100.0
0.0
64.8
100.0
100.0

9
16
21
27
9
41
42
43

9
16
21
26
9
41
42
43

9
15
21
26
9
41
42
42

2.8
3.1
3.2
3.4
11.4
4.9
2.4
2.5

2.8
3.1
3.1
3.8
11.9
4.9
2.4
2.6

0.8
0.5
0.5
0.6
12.8
3.0
1.0
0.8

5.1
5.7
5.8
6.0
11.2
4.1
2.1
2.3

5.1
5.6
5.8
6.0
11.1
4.0
2.0
2.2

1.6
1.3
1.3
1.3
9.0
2.3
0.6
0.5

24

rand-1
rand-2
rand-3rand-4plan-1cliq-1cliq-2cliq-3

99.8
100.0
100.0
100.0
0.1
60.3
100.0
100.0

9
16
22
27
9
42
42
43

10
16
22
27
9
41
42
43

9
15
21
25
9
41
42
43

4.6
6.2
6.3
7.5
37.0
8.7
2.9
2.9

4.7
6.2
6.4
7.3
33.3
7.6
2.9
2.9

1.7
1.1
1.4
1.5
27.9
4.1
1.3
1.0

9.4
12.5
12.5
14.4
36.3
5.1
2.1
2.1

9.3
12.2
13.0
14.5
31.9
5.0
2.0
2.0

3.5
2.5
2.2
2.0
20.2
2.4
0.7
0.5

40

rand-1
rand-2
rand-3rand-4plan-1cliq-1cliq-2cliq-3

99.8
100.0
100.0
100.0
0.2
63.3
100.0
100.0

10
17
23
28
9
41
42
43

9
17
23
28
8
41
42
43

9
15
20
26
9
41
42
43

5.2
7.2
8.2
10.0
53.4
7.3
2.9
3.0

5.2
6.7
8.0
9.1
52.6
6.8
2.9
3.0

2.4
1.4
1.1
1.1
34.5
3.5
1.1
0.9

10.7
16.5
18.4
20.4
50.6
4.1
1.8
1.9

10.7
16.3
18.5
19.7
43.1
4.4
1.8
1.8

4.8
3.3
2.8
2.6
24.1
2.0
0.6
0.5

|VB | denotes the total number of boundary vertices after partitioning.

Table A5
Weak scaling on synthetic graphs using s = 125
Name

DegreeSeq. colors

p

|VI |

Max

Avg

rand-5rand-6
rand-7
rand-8rand-9rand-10
rand-11

80
79
82
91
86
86
84

50
50
50
50
50
50
50

20
20
20
21
21
20
20

1
2
8
16
24
32
40

10,000000000

plan-2plan-3plan-4plan-5plan-6plan-7plan-8

35
29
32
37
40
43
40

6
6
6
6
6
6
6

8
8
9
8
9
9
9

1
2
8
16
24
32
40

102,093
101,988
102,248
101,448
101,522
101,394
101,655|VB |Colors

Runtime on Itanium 2

Runtime on Pentium 4

FIAC

FBAC

JP

FIAC

FBAC

JP

FIAC

FBAC

JP

0
20,00080,000160,000
240,000
320,000
400,000

20
20
22
22
22
23
23

20
20
22
22
22
22
23

20
20
21
20
21
21
20

26
29
48
106
178
196
227

26
29
80
110
142
193
232

26
86
375
742
1146
1469
1695

10
18
40
85
120
140
156

10
17
46
88
121
140
155

10
64
284
544
759
889
1007

0
74
1,521
2,811
4,539
6,347
6,750

8
8
9
8
9
9
9

8
8
9
8
9
9
8

8
8
9
8
9
9
9

49
38
43
69
72
83
90

49
38
62
69
76
83
91

49
39
50
87
102
116
139

28
29
37
45
51
60
77

28
31
39
51
61
71
86

28
33
51
79
103
123
155

|VI | is the average number of internal vertices on each processor, and |VB | is the total number of boundary vertices after partitioning.

References[1] J. Allwright, R. Bordawekar, P.D. Coddington, K. Dincer, C. Martin,
A comparison of parallel graph coloring algorithms, Technical Report,
NPAC Technical Report, SCCS-666, Northeast Parallel Architectures
Center at Syracuse University, 1994.
[2] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. MarchettiSpaccamela, M. Protasi, Complexity and Approximation, Springer,
Berlin, 1999.

[3] R.H. Bisseling, Parallel Scientific Computation: A Structured Approach
Using BSP and MPI, Oxford, 2004.
[4] E.G. Boman, D. Bozdağ, U. Catalyurek, A.H. Gebremedhin, F. Manne,
A scalable parallel graph coloring algorithm for distributed memorycomputers, in: Proceedings of Euro-Par 2005, Lecture Notes in Computer
Science, vol. 3648, Springer, Berlin, 2005, pp. 241–251.
[5] D. Bozdağ, U. Catalyurek, A.H. Gebremedhin, F. Manne, E.G. Boman,
F. Özgüner, A parallel distance-2 graph coloring algorithm for distributed
memory computers, in: Proceedings of HPCC 2005, Lecture Notes in
Computer Science, vol. 3726, Springer, Berlin, 2005, pp. 796–806.

D. Bozdağ et al. / J. Parallel Distrib. Comput. 68 (2008) 515 – 535[6] T.F. Coleman, J.J. More, Estimation of sparse Jacobian matrices andgraph coloring problems, SIAM J. Numer. Anal. 1 (20) (1983) 187–209.
[7] K. Devine, E. Boman, R. Heaphy, B. Hendrickson, C. Vaughan, Zoltan
data management services for parallel dynamic applications, Comput.
Sci. Eng. 4 (2) (2002) 90–97.
[8] E.D. Dolan, J.J. Moré, Benchmarking optimization software withperformance profiles, Math. Programming 91 (2) (2002) 201–213.
[9] I. Finocchi, A. Panconesi, R. Silvestri, Experimental analysis of simple,
distributed vertex coloring algorithms, Algorithmica 41 (1) (2004) 1–23.
[10] M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, New
York, 1979.
[11] A.H. Gebremedhin, I. Guérin-Lassous, J. Gustedt, J.A. Telle, Graph
coloring on coarse grained multicomputers, Discrete Appl. Math. 131(1) (2003) 179–198.
[12] A.H. Gebremedhin, F. Manne, Scalable parallel graph coloringalgorithms, Concurrency: Practice and Experience 12 (2000) 1131–1146.
[13] A.H. Gebremedhin, F. Manne, A. Pothen, Parallel distance-k coloringalgorithms for numerical optimization, in: Proceedings of Euro-Par 2002,
Lecture Notes in Computer Science, vol. 2400, Springer, Berlin, 2002,
pp. 912–921.
[14] A.H. Gebremedhin, F. Manne, A. Pothen, What color is your jacobian?
Graph coloring for computing derivatives, SIAM Rev. 47 (4) (2005)
629–705.
[15] A.H. Gebremedhin, F. Manne, T. Woods, Speeding up parallel graphcoloring, in: Proceedings of Para 2004, Lecture Notes in Computer
Science, vol. 3732, Springer, Berlin, 2005, pp. 1079–1088.
[16] Genetic algorithms (evolutionary algorithms): repository of test problem
generators .http://www.cs.uwyo.edu/∼ wspears/generators.html0.
[17] R.K. Gjertsen Jr., M.T. Jones, P. Plassmann, Parallel heuristics for
improved, balanced graph colorings, J. Par. and Dist. Comput. 37 (1996)
171–186.
[18] Gtgraph: a suite of synthetic graph generators .http://www-static.cc.
gatech.edu/∼kamesh/GTgraph/0.
[19] Ö. Johansson, Simple distributed $ + 1-coloring of graphs, Inform.
Process. Lett. 70 (1999) 229–232.
[20] M. Jones, P. Plassmann, Scalable iterative solution of sparse linear
systems, Parallel Comput. 20 (5) (1994) 753–773.
[21] M.T. Jones, P. Plassmann, A parallel graph coloring heuristic, SIAM J.
Sci. Comput. 14 (3) (1993) 654–669.
[22] G. Karypis, V. Kumar, A fast and high quality multilevel scheme forpartitioning irregular graphs, SIAM J. Sci. Comput. 20(1).
[23] M. Luby, A simple parallel algorithm for the maximal independent set
problem, SIAM J. Comput. 15 (4) (1986) 1036–1053.
[24] F. Manne, A parallel algorithm for computing the extremal eigenvaluesof very large sparse matrices, in: Proceedings of Para 1998, Lecture
Notes in Computer Science, vol. 1541, Springer, Berlin, 1998,
pp. 332–336.
[25] C.A. Morgenstern, H.D. Shapiro, Heuristics for rapidly four-coloringlarge planar graphs, Algorithmica 6 (6) (1991) 869–891.
[26] Y. Saad, ILUM: a multi-elimination ILU preconditioner for general sparse
matrices, SIAM J. Sci. Comput. 17 (1996) 830–847.
[27] M.M. Strout, L. Carter, J. Ferrante, J. Freeman, B. Kreaseck, Combining
performance aspects of irregular Gauss–Seidel via sparse tiling, in:W. Pugh, C.-W. Tseng (Eds.), LCPC, Lecture Notes in Computer Science,
vol. 2481, Springer, Berlin, 2002, pp. 90–110.
[28] M.M. Strout, P.D. Hovland, Metrics and models for reorderingtransformations, in: Proceedings of the Second ACM SIGPLAN
Workshop on Memory System Performance (MSP), 2004, pp. 23–34.
[29] Test data from the Parasol project .http://www.parallab.uib.no/projects/
parasol/data/0.
[30] The
SecondDIMACS
Challenge.http://mat.gsia.cmu.edu/
challenge.html0.
[31] University of Florida matrix collection .http://www.cise.ufl.edu/research/sparse/matrices/0.
[32] L. Valiant, A bridging model for parallel computation, Comm. ACM 33(8) (1990) 103–111 bSP.

535

Doruk Bozdağ is a graduate student in the Department of Electrical and Computer Engineering at The Ohio State University. His researchinterests include scheduling algorithms for multiprocessor systems, parallel graph algorithms
and high-performance computing. He received
his MS in Electrical and Computer Engineeringfrom The Ohio State University in 2005 and BS
in Electrical and Electronic Engineering and BS
in Physics from Boğaziçi University, Turkey, in
2002.

Assefaw H. Gebremedhin is a research scientist at the Department of Computer Science
and Center for Computational Sciences at Old
Dominion University, VA, USA. He is a member of the Combinatorial Scientific Computing
and Petascale Simulations (CSCAPES) Institute,which is sponsored by the US Department ofEnergy through its Scientific Discovery throughAdvanced Computing (SciDAC) program. Assefaw received his PhD in Computer Sciencefrom the University of Bergen, Norway, in 2003.
His academic background also includes a BSc
degree in Electrical Engineering. His research interests are in the areas of algorithmics, parallel computing, combinatorial scientific computing, automaticdifferentiation, and software development.
Fredrik Manne is a full professor at the Department of Informatics, University of Bergen,
Norway. He also received his PhD from thesame university in 1993. Previous to joining the
University of Bergen as a faculty member heworked in the oil industry as well as at Parallab, the supercomputing centre of the Universityof Bergen. His main research area is in parallel and distributed computing with a particularemphasis on problems arising in combinatorial
scientific computing.
Erik G. Boman is a scientist at Sandia National Laboratories, NM, USA.
He received a PhD in Scientific Computing and Computational Mathematics
from Stanford University (1999) and also holds a Cand.Scient. (MS) degree
in Informatics from the University of Bergen, Norway, (1992). His current
research interests are in combinatorial scientific computing and algorithms forparallel computing. He has extensive experience in algorithms for partitioning
and load balancing, and is a co-author of the Zoltan software toolkit. He
has also published several journal papers in numerical linear algebra andpreconditioning methods.
Umit V. Catalyurek is an associate professor
in the Department of Biomedical Informatics at
The Ohio State University, and has a joint faculty appointment in the Department of Electricaland Computer Engineering. His research interests include combinatorial scientific computing,grid computing, and runtime systems and algorithms for high-performance and data-intensive
computing. He received his PhD, MS and BS
in Computer Engineering and Information Science from Bilkent University, Turkey, in 2000,
1994 and 1992, respectively.