SIAM J. SCI. COMPUT.
Vol. 32, No. 4, pp. 2418–2446

c 2010 Society for Industrial and Applied Mathematics!

DISTRIBUTED-MEMORY PARALLEL ALGORITHMS FORDISTANCE-2 COLORING AND RELATED PROBLEMS IN
DERIVATIVE COMPUTATION∗DORUK BOZDAĞ† , ÜMİT V. ÇATALYÜREK‡ , ASSEFAW H. GEBREMEDHIN§ ,FREDRIK MANNE¶, ERIK G. BOMAN! , AND FÜSUN ÖZGÜNER∗∗
Abstract. The distance-2 graph coloring problem aims at partitioning the vertex set of a graphinto the fewest sets consisting of vertices pairwise at distance greater than 2 from each other. Itsapplications include derivative computation in numerical optimization and channel assignment inradio networks. We present efficient, distributed-memory, parallel heuristic algorithms for this NPhard problem as well as for two related problems used in the computation of Jacobians and Hessians.
Parallel speedup is achieved through graph partitioning, speculative (iterative) coloring, and a bulk
synchronous parallel–like organization of parallel computation. Results from experiments conducted
on a PC cluster employing up to 96 processors and using large-size real-world as well as syntheticallygenerated test graphs show that the algorithms are scalable. In terms of quality of solution, thealgorithms perform remarkably well—the numbers of colors used by the parallel algorithms areobserved to be very close to the numbers used by their sequential counterparts, which in turn arequite often near optimal. Moreover, the experimental results show that the parallel distance-2
coloring algorithm compares favorably with the alternative approach of solving the distance-2 coloring
problem on a graph G by first constructing the square graph G 2 and then applying a parallel distance1 coloring algorithm on G 2 . Implementations of the algorithms are made available via the Zoltan
toolkit.
Key words. distance-2 graph coloring, distributed-memory parallel algorithms, Jacobian computation, Hessian computation, sparsity exploitation, automatic differentiation, combinatorial scientific computing
AMS subject classifications. 05C15, 05C85, 68R10, 68W10
DOI. 10.1137/080732158

1. Introduction. A distance-k coloring of a graph is an assignment of colors tovertices such that any two vertices connected by a path consisting of at most k edges
receive different colors, and the goal of the associated problem is to use as few colors as
possible. Distance-2 coloring (of an appropriate graph) is an archetypal model in theefficient computation of sparse Jacobian and Hessian matrices, whether derivatives∗ Received by the editors August 4, 2008; accepted for publication (in revised form) May 17, 2010;
published electronically August 5, 2010. This work was supported by the U.S. Department of Energy’s Office of Science through the CSCAPES SciDAC Institute; by the U.S. National Science Foundation under grants CCF-0830645, CNS-0643969, OCI-0904809, OCI-0904802, and CNS-0403342; byOhio Supercomputing Center PAS0052; and by the Norwegian Research Council through the Evita
program.
http://www.siam.org/journals/sisc/32-4/73215.html† Department of Biomedical Informatics, The Ohio State University, Columbus, OH 43210(bozdag.1@osu.edu).
‡ Departments of Biomedical Informatics and Electrical & Computer Engineering, The Ohio State
University, Columbus, OH 43210 (catalyurek.1@osu.edu).
§ Department of Computer Science, Purdue University, West Lafayette, IN 47907 (agebreme@
purdue.edu).
¶ Department of Informatics, University of Bergen, Bergen, Norway (Fredrik.Manne@ii.uib.no).
! Scalable Algorithms Department, Sandia National Laboratories, Albuquerque, NM 87185(egboman@sandia.gov). 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.
∗∗ Department of Electrical & Computer Engineering, The Ohio State University, Columbus, OH
43210 (ozguner@ece.osu.edu).

2418

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION2419

are calculated using automatic differentiation or estimated using finite differencing[16]. Jacobian and Hessian matrices are needed in many algorithms in scientific computing, including algorithms for nonlinear optimization, differential equations, inverse
problems, and sensitivity analysis. Distance-2 coloring also finds applications in otherareas, such as in channel assignment problems in radio networks [21, 22]. Distance1 coloring is used in numerous applications, including in discovering concurrency inparallel scientific computing [18, 19, 27].
In parallel applications where a distance-k coloring is needed, the graph is either already partitioned and mapped or needs to be partitioned and mapped onto
the processors of a distributed-memory parallel machine. Under such circumstances,
gathering the graph on one processor to perform the coloring sequentially is prohibitively time-consuming or infeasible due to memory constraints. Hence the graphneeds to be colored in parallel. Finding a distance-k coloring using the fewest colors
is an NP-hard problem [23], but greedy heuristics are effective in practice, as theyrun fast and provide solutions of acceptable quality [8, 16, 17]. They are, however,inherently sequential and thus challenging to parallelize.
We report in this paper on the design, analysis, implementation, and experimental
evaluation of a variety of efficient greedy parallel algorithms that we have developed for
distance-2 coloring in distributed-memory environments. We also present appropriate
variants of the algorithms tailored for Jacobian and Hessian computation. The algorithms presented here are obtained by extending the parallelization framework that
we developed in a recent work in the context of distance-1 coloring [6]. The framework is an iterative, data-parallel, algorithmic scheme that proceeds in two-phasedrounds. In the first phase of each round, processors concurrently color the vertices
assigned to them in a speculative manner, communicating at a coarse granularity. In
the second phase, processors concurrently check the validity of the colors assigned totheir respective vertices and identify a set of vertices that needs to be recolored in
the next round to resolve any detected inconsistencies. The scheme terminates when
every vertex has been colored correctly.
One of the challenges involved in extending the framework outlined above tothe distance-2 coloring case is devising an efficient means of information exchange
between processors hosting a pair of vertices that are two edges away from each otherin the graph. For such pairs of vertices, relying on direct communication between thecorresponding processors would incur unduly high communication cost, and locallystoring duplicates of distance-2 neighborhoods would require unduly large memory
space. Instead, we employ a strategy in which information is relayed via a third
processor (the processor owning a mutual distance-1 neighbor of vertices two edges
away from each other) as needed. We show that the parallel algorithms designed
using this strategy yield good speedup with increasing number of processors while
using nearly the same number of colors as a serial greedy algorithm. We also showthat the algorithms outperform the alternative approach based on distance-1 coloringof a square graph.
A preliminary version of a small portion of the work presented here has appearedin an earlier conference paper [5]. Compared to [5], the current paper has several
new contributions. In terms of the basic distance-2 coloring algorithm for generalgraphs, the algorithm has been described much more rigorously, its complexity has
been analyzed, and possible variations of the algorithm have been outlined; moreover,the experimental performance evaluation of the algorithm is conducted much morethoroughly and is carried out on a larger set of test problems and on a larger number

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2420

BOZDAĞ ET AL.

of processors. In addition, new algorithms for distance-2 coloring of bipartite graphs(for Jacobian computation) and restricted star coloring of general graphs (for Hessiancomputation) have been presented and experimentally evaluated.
To the best of our knowledge, this paper is the first to present demonstrably efficient and scalable parallel algorithms for distance-2 coloring on distributed-memoryarchitectures. Gebremedhin, Manne, and Pothen [15] have developed shared-memory
parallel algorithms for distance-2 coloring. They have also provided a comprehensive
review of the role of graph coloring in derivative computation in [16], and designed
efficient serial algorithms for acyclic and star coloring (which are used in Hessian computation) in [17]. The advantage of using those star and acyclic coloring algorithms in
the context of computing Hessians using automatic differentiation was demonstrated
in [13]. The literature on algorithmic graph theory features some work related to the
distance-2 coloring problem [1, 2, 21, 22]. Readers are referred to section 11.4 of [16]and section 2.3 of [17] for more pointers to theoretical work on distance-k and relatedcoloring problems.
The remainder of this paper is organized as follows. Section 2 provides background: it includes a self-contained review of the coloring models for sparse derivative
matrix computation that are relevant for this paper, and a brief discussion of serial
greedy coloring algorithms, since they form the foundation for the parallel algorithms
presented here. Section 3 sets the stage for a detailed presentation of the parallel
distance-2 coloring algorithm for general graphs in section 4 by discussing several algorithm design issues. Section 5 shows how the algorithm described in section 4 can beadapted for restricted star coloring of general graphs (for Hessian computation) anddistance-2 coloring of bipartite graphs (for Jacobian computation). Section 6 contains
a detailed computational evaluation of the performance of the parallel algorithms, andsection 7 concludes the paper.
2. Background.
2.1. Preliminary concepts and notation. Two distinct vertices in a graphare distance-k neighbors if a shortest path connecting them consists of at most kedges. We denote the set of distance-k neighbors of a vertex v by Nk (v). The degreek of a vertex v, denoted by dk (v), is the number of distinct paths of length at mostk edges starting at v. Two paths! are distinct if they differ in at least one edge. Notethat d1 (v) = |N1 (v)|, d2 (v) = w∈N1 (v) d1 (w), and, in general, dk (v) ≥ |Nk (v)|. We
denote the average degree-k in a graph by dk .
A distance-k coloring of a graph G = (V, E) is a mapping φ : V → {1, 2, . . . , q} suchthat φ(v) #= φ(w) whenever vertices v and w are distance-k neighbors. A distancek coloring of a graph G = (V, E) is equivalent to a distance-1 coloring of the kth
power graph G k = (V, F ), where (v, w) ∈ F whenever vertices v and w are distance-k
neighbors in G. A distance-k coloring of a graph G = (V, E) can equivalently be viewed
as a partition of the vertex set V into q distance-k independent sets—sets of vertices
at a distance greater than k edges from each other. Variants of distance-k coloring areused in modeling partitioning problems in sparse Jacobian and Hessian computation.
We review these in the next subsection; for a more comprehensive discussion, see[16, 17].
2.2. Coloring models in derivative computation. The computation of asparse m×n derivative matrix A using automatic differentiation (or finite differencing)
can be made efficient by first partitioning the n columns into q disjoint groups, withq as small as possible, and then evaluating the columns in each group jointly (as aCopyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2421sum) rather than separately. More specifically, the values of the entries of the matrix
A are obtained by first evaluating a compressed matrix B ≡ AS, where S is an n × q
seed matrix whose (j, k) entry sjk is such that sjk equals one if and only if column aj
belongs to group k and zero otherwise, and then recovering the entries of A from B.
The specific criteria used to define a seed matrix S for a derivative matrix A depends on whether the matrix A is Jacobian (nonsymmetric) or Hessian (symmetric).
It also depends on whether the entries of A are to be recovered from the compressed
representation B directly (without any further arithmetic), via substitution (by implicitly solving a set of simple triangular systems of equations), or via elimination(by solving a rectangular system of equations). In this paper we focus on only direct
methods.
2.2.1. Structurally orthogonal partition. Curtis, Powell, and Reid [10]showed that a structurally orthogonal partition of a Jacobian matrix A—a partitionof the columns of A in which no two columns in a group share a nonzero at the samerow index—gives a seed matrix S where the entries of A can be directly recoveredfrom the compressed representation B ≡ AS. The structure of a Jacobian matrix A
can be represented by the bipartite graph Gb (A) = (V1 , V2 , E), where V1 is the row
vertex set, V2 is the column vertex set, and (ri , cj ) ∈ E whenever the matrix entry
aij is nonzero. A partitioning of the columns of the matrix A into groups consistingof structurally orthogonal columns is equivalent to a partial distance-2 coloring of
the bipartite graph Gb (A) on the vertex set V2 [16]. The coloring is called “partial”
because the row vertex set V1 is left uncolored.
A structurally orthogonal column partition could also be used in computing a
Hessian via a direct method, albeit that symmetry is not exploited. Specifically,
McCormick [23] showed that a structurally orthogonal partition of a Hessian is equivalent to a distance-2 coloring of its adjacency graph. The adjacency graph Ga (A) ofa Hessian A has a vertex for each column, and an edge joins column vertices ci andcj whenever the entry aij , i #= j, is nonzero; the diagonal entries in A are assumed
to be nonzero, and they are not explicitly represented by edges in the graph Ga (A).
Figure 2.1 illustrates how a structurally orthogonal column partition of a matrix ismodeled by a distance-2 coloring in the appropriate graph. The rightmost subfigures
show the equivalent distance-1 coloring formulations in the appropriate square graph.
2.2.2. Symmetry-exploiting partition. Powell and Toint [26] were the first
to introduce a symmetry-exploiting technique for computing a Hessian via a direct
method. When translated to a coloring φ of the adjacency graph, the partition Powell
and Toint suggested for a direct Hessian computation requires that (1) φ be a distance1 coloring, and (2) in every path v, w, x on three vertices, the terminal vertices v andx be allowed to have the same color, but only if the color of the middle vertex w
is lower in value. A coloring that satisfies these two requirements has been called a
restricted star coloring in [17].
Coleman and Moré [9] showed that a symmetrically orthogonal partition of a
Hessian is sufficient for a direct recovery, and established that such a partition isequivalent to a star coloring of the adjacency graph of the Hessian. A star coloring is
a distance-1 coloring where, in addition, every path on four vertices uses at least threecolors. The name is due to the fact that in a star-colored graph, a subgraph induced
by any two color classes is a collection of stars. Note that the three coloring models
for direct Hessian computation discussed here can be ranked in increasing order ofrestriction (decreasing order of accuracy) as star coloring, restricted star coloring,
distance-2 coloring.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2422

BOZDAĞ ET AL.
a11 0 0 0 a15
0 a22 a23 0 0
0 a32 a33 a34 a35
0 0 a43 a44 a45
a51 0 a53 a54 a55

c1

c5

A

c1

c3

c2

c5

c3

c4

A

a11 a12 0 0 a15
a21 a22 0 0 0
a31 0 0 a34 0
0 0 a43 a44 a45

c2

c4
Ga2

Ga
c1

r1

c1

c2

r2

c3

r3

c4

r4

c2

c5

c3

c5
Gb

c4
2

Gb [V ]
2

Fig. 2.1. Equivalence among structurally orthogonal column partition of a matrix A, distance-2
coloring of the graph G(A) of A, and distance-1 coloring of G 2 (A). Top: symmetric case. Bottom:
nonsymmetric case, where Gb2 [V2 ] denotes the subgraph of the square graph Gb2 induced by the vertex
set V2 .

2.3. Greedy coloring algorithms. An optimization problem associated with
distance-k, restricted star, or star coloring asks for an appropriate coloring with thefewest colors, and each is known to be NP-hard [9, 17, 23]. In practice, greedy algorithms have been found effective in delivering good suboptimal solutions for these
problems quickly [8, 17]. A greedy algorithm for each of these problems progressively
extends a partial coloring of a graph by processing one vertex at a time, in someorder; there exist a number of effective ordering techniques that are based on somevariation of vertex degree [8, 17]. In the step where a vertex v is colored, first, a
set F of forbidden colors for the vertex v is obtained by exploring the appropriate
neighborhood of v. Then, the smallest allowable color (not included in F ) is chosen
and assigned to v.
In the case of distance-1 coloring, such a greedy algorithm uses at most ∆ + 1
colors, where ∆ is the maximum degree-1 in the graph. The quantity ∆ + 1 is a lower
bound on the optimal number of colors needed in a distance-2 coloring. Furthermore,
the number of colors used by a greedy distance-2 coloring algorithm is bounded fromabove by min{∆2 + 1, n}, where n is the number of vertices in the input graph. Using
this bound,
McCormick [23] showed that the greedy distance-2 coloring algorithm is√an O( n)-approximation algorithm.
Greedy algorithms for distance-1 and distance-2 coloring can be implemented suchthat their respective complexities are O(nd1 ) and O(nd2 ). Gebremedhin et al. [17]have developed O(nd2 )-time greedy algorithms for star and restricted star coloring.
Their algorithm for star coloring takes advantage of the structure of the two-coloredinduced subgraphs—the collection of stars—and uses fairly complex data structures tomaintain them. In this paper we develop parallel versions of the greedy algorithms for
distance-2 and restricted star coloring. We considered the simpler variant, restricted
star coloring, instead of star coloring, since restricted star coloring can be derived via
a simple modification of the parallel algorithm for the distance-2 coloring problem,
which is the main focus of this paper.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2423

3. Design issues. The parallel distance-2 coloring algorithm proposed in thispaper will be presented in detail in section 4. Here we discuss the major issues thatarise in the design of the algorithm and the assumptions and decisions we made aroundthem.
3.1. Data distribution. The way in which the input graph is partitioned andmapped to processors has implications for both load balance and interprocessor communication. A graph could be partitioned among processors either by partitioning
the vertex set or by partitioning the edge set. Traditionally, vertex partitioning has
been the most commonly used strategy for mapping graphs (or matrices) to processors [4, 7, 12]. When a vertex partitioning is used, edges are implicitly mapped toprocessors, with every crossing edge essentially being duplicated on the two processors to which its endpoints are mapped. For matrices, this corresponds to mapping of
entire columns or rows to processors. To make our algorithm and its implementation
more readily usable in other parallel codes, we assume that a vertex partitioning isused in distributing the graph among processors. A vertex partitioning classifies thevertices of the graph into two categories: interior and boundary. An interior vertex
is a vertex all of whose distance-1 neighbors are mapped onto the same processor as
itself. A boundary vertex has at least one distance-1 neighbor mapped onto a different
processor.
3.2. Data duplication and communication mechanism. The next design
issue is data duplication and its impact on information exchange.
As stated earlier, when a vertex partitioning is used, every crossing edge is duplicated, and that was the approach used in our earlier work on distance-1 coloring [6].
In such a mapping strategy, it makes sense for each processor to store the colors of
the off-processor endpoints of its crossing edges, as this would require storing at mostone extra color per crossing edge. In terms of communication, such a storage scheme
necessitates that each processor send the colors of its boundary vertices to neighboring processors as soon as the colors become available. Each receiving processor could
then store the information and use it later while coloring its own vertices. In this way,
the color of a boundary vertex is sent at most once for each of its incident crossing
edges.
In the distance-2 coloring case, for each vertex, color information about vertices
that are two edges away is also needed. One way of acquiring this information would
be for each processor to keep a local copy of the subgraph induced by off-processor
vertices that are within a distance of two edges from its own boundary vertices. Then,each processor could store and have access to all the needed color information as soon
as the information was received from neighboring processors. Thus, as in the distance1 coloring case, color information could be sent as soon as it became available. This
would in turn allow for a flexible coloring order on each processor, since the orderin which vertices are colored can be freely determined as the algorithm proceeds.
However, this flexibility comes at the expense of extra storage. For relatively densegraphs, large portions of the input graph may need to be duplicated on each processor.
In fact, this could happen even if there were just one high degree boundary vertex.
For this reason, we chose to duplicate just the boundary vertices and their colors, andno more.
With this design decision in place, each processor will gain local access to distance1 color information just as in the distance-1 coloring algorithm, and the information
can be exchanged among the processors at the earliest possible time. But a mechanism
for exchanging color information among vertices that are two edges apart still needs to

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2424

BOZDAĞ ET AL.

be devised. Since such colors are not going to be stored permanently on the receiving
processor, each color will have to be resent every time it is needed. Here, there are
two basic ways in which the communication can be coordinated: one can use eithera request-based protocol or a precomputed schedule. In a request-based protocol, eachprocessor would send a message to its neighboring processors asking for specific color
information whenever it needs the information. It then receives the information, uses
it, and discards it. With a precomputed schedule, each processor would know the order(at least partially) in which its neighbor processors are going to color their vertices.
Thus a processor could itself determine what color information to send to its neighbors
and when to do so. A request-based protocol gives rise to more communication thana precomputed schedule, but, on the other hand, it is more flexible as it allows for acompletely independent coloring order on each processor. In our algorithm we chose
to use a precomputed schedule. Even with a precomputed schedule, there exists anopportunity for using ordering techniques at a local level on each processor, but weforego a detailed study of such ordering techniques to limit the scope of this paper.
4. Parallel distance-2 coloring of general graphs. We are now ready topresent the new parallel distance-2 coloring algorithm for a general graph G = (V, E).
We begin in section 4.1 by providing an overview of the algorithm, and then present its
details layer-by-layer in sections 4.2–4.4. The complexity of the algorithm is analyzed
in section 4.5, and a brief discussion of possible variations of the algorithm is given
in section 4.6. In section 5 we will show how the algorithm needs to be modified tosolve the restricted star coloring problem, again on a general graph G, and the partial
distance-2 coloring problem on a bipartite graph Gb = (V1 , V2 , E).

4.1. Overview of the algorithm. Initially, the input graph G = (V, E) isassumed to be vertex-partitioned and distributed among the p available processors.
The set Vi of vertices in the partition {V1 , . . . , Vp } of V is assigned to and coloredby processor Pi . We say Pi owns Vi . In addition, processor Pi stores the adjacency
lists of its vertices and the identities of the processors owning them. This initial
data distribution classifies each set Vi into sets of interior and boundary vertices(Vi = Ii ∪ Bi ). We call two processors Pi and Pj neighbors if at least one boundary
vertex owned by processor Pi has a distance-1 neighbor vertex owned by processor Pj .
Clearly, any two interior vertices owned by two different processors can safely becolored concurrently in a distance-2 coloring. In contrast, a concurrent coloring of apair of boundary vertices or a pair consisting of one boundary and one interior vertex
may not be safe, as the constituents of the pair, while being distance-2 neighbors,
may receive the same color and therefore result in a conflict. We avoid the latter
situation for a potential conflict (due to a pair consisting of one boundary and one
interior vertex) by requiring that interior vertices be colored strictly before or strictly
after boundary vertices have been colored. Then, a conflict can occur only for pairsof boundary vertices. Thus, the central part of the algorithm being presented isconcerned with how the coloring of the boundary vertices is performed in parallel.
The main idea is to perform the coloring of the boundary vertices concurrently ina speculative manner and then detect and rectify conflicts that may have arisen. The
algorithm (iteratively) proceeds in rounds, each consisting of a tentative coloring anda conflict detection phase. Both of these phases are performed in parallel. To reduce
the frequency of communication among processors, the tentative coloring phase isorganized in a sequence of supersteps, a term borrowed from the literature on thebulk synchronous parallel model [4] and used here in a loose sense. Specifically, ineach superstep, each processor colors a prespecified number s of the vertices that

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2425

Algorithm 1. Overview of the parallel distance-2 coloring algorithm.
1: procedure ParallelColoring(G = (V, E ), s)2:
Data distribution: G is divided into p subgraphs G1 = (V1 , E1 ), . . . , Gp = (Vp , Ep ),

3:
4:
5:
6:
7:
8:
9:
10:
11:

where V1 , . . . , Vp is a partition of the set V and Ei = {(v, w) : v ∈ Vi , (v, w) ∈ E}.
Processor Pi owns the vertex set Vi and stores the edge set Ei and the ID’s of
the processors owning the other endpoints of Ei .
on each processor Pi , i ∈ P = {1, . . . , p},Ii ← interior vertices in Vi
Bi ← boundary vertices in Vi! Vi = Ii ∪ Bi
Color the vertices in Ii .
Assign each vertex v ∈ Bi ∪ N1 (Bi ) a random number rand(v), generated using
v’s ID as seed.
Ui ← Bi! Ui is the current set of boundary vertices to be colored by Pi
while ∃j ∈ P, Uj %= ∅ do
TentativelyColor(Ui , s)Ui ← DetectConflicts()

it owns in a sequential manner, using forbidden color information available at the
beginning of the superstep, and only thereafter sends recent color information toneighboring processors. In this scenario, if two boundary vertices that are either
adjacent or at a distance of exactly two edges from each other are colored during
the same superstep, they may receive the same color and thus cause a conflict. The
purpose of the subsequent detection phase is to discover such conflicts in the current
round and accumulate a list of vertices on each processor that needs to be recoloredin the next round to resolve the conflicts.
Given a pair of vertices involved in a conflict, it suffices to recolor only one ofthem to resolve the conflict. The vertex to be recolored is determined by making useof a global random function defined over all boundary vertices. In particular, eachprocessor Pi assigns a random number to each vertex in the set"Bi ∪ N1 (Bi ), where
Bi is the set of boundary vertices owned by Pi and N1 (Bi ) = w∈Bi N1 (w). Eachrandom number rand(v) associated with the vertex v is computed by a pseudorandom
generator using the global ID of the vertex v as a seed. This avoids the potential needfor exchange of random values among processors, since the number rand(v) computedon one processor for a given vertex v would be the same as the number rand(v)computed on another processor for the same vertex. The algorithm terminates when
no more vertices are left to be recolored. A high-level structure of the algorithm isgiven in Algorithm 1. The routines TentativelyColor and DetectConflicts
called in Algorithm 1 will be discussed in detail in sections 4.3 and 4.4, respectively.
But first we discuss a few fundamental techniques employed in Algorithm 1.
4.2. Conflict detection and relaying distance-2 color information. In addition to the design issues on data distribution, data duplication, and communication
protocol discussed in section 3, the way in which conflicts are detected is a major issue
in the design of Algorithm 1. We employed a strategy in which, for every path v, w, x
on three vertices, the processor on which the vertex w resides is responsible for detecting not only conflicts that involve the vertex w and an adjacent vertex in N1 (w) but
also a conflict involving the vertices v and x. We call the former (involving adjacentvertices) type 1 conflicts, and the latter (involving vertices two edges apart) type 2
conflicts. A type 1 conflict is detected by both of the implied processors, whereas atype 2 conflict is detected by the processor owning the middle vertex. Clearly, thisCopyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2426

BOZDAĞ ET AL.

Pk
Pi
w2

x1
w1
x2

Pi

Pj
w

v

x3

x

Pi

v

v

w

x1

(i)

(ii)

Pj
x2

(iii)

Fig. 4.1. Scenarios depicting the distribution of the distance-2 neighbors of vertex v acrossprocessors.

way of detecting a type 2 conflict is more efficient than the alternative in which theconflict is detected by both of the processors owning the terminal vertices v and x.
As the termination condition of the while-loop in Algorithm 1 indicates, even if
a processor has no more vertices left to be recolored in a round, i.e., Ui = ∅, it could
still be active in that round, as the processor may need to provide color information
to other processors, participate in detecting conflicts on other processors, or both.
Another basic ingredient in the design of Algorithm 1 is the technique used to build
the list of forbidden colors for a given vertex v in a given superstep. The technique isdirectly related with the strategies on data duplication and communication protocol
employed in the design of the algorithm (these were discussed in section 3.2). The
next two paragraphs discuss elements of this technique.
Let Pi be the processor that owns the vertex v. The list of forbidden colors for thevertex v consists of colors assigned to adjacent vertices—those in the set N1 (v)—andcolors assigned to vertices exactly two edges away from v. These colors are assigned
either in a previous superstep (for boundary vertices) or prior to the iterative coloring(for interior vertices). We classify these colors as local or nonlocal relative to processor
Pi on the onset of the superstep. A color of a vertex u is local to processor Pi if Pi
owns either the vertex u or some distance-1 neighbor of u (in which case Pi would
store a copy of u’s color information, which is computed and sent by u’s owner).
In contrast, a color is nonlocal to Pi if the information is not locally stored and hence
needs to be relayed via an “intermediate” processor.
Figure 4.1 shows the three scenarios in which the vertices on a path v, w, x may
be distributed among processors. Case (i) corresponds to the situation where both ofthe vertices w and x (w1 and x1 or w2 and x2 in the figure) are owned by processor Pi .
Clearly, in this case, the colors of the vertices w and x are both local to Pi . Case (ii)shows the situation where vertex w is owned by processor Pi and vertex x is owned byprocessor Pj , j #= i. In this case, again, the colors of both vertices w and x are local
to Pi . Case (iii) shows the situation where vertex w is owned by processor Pj , andvertices v and x do not have a common distance-1 neighbor owned by processor Pi .
As depicted in the figure, vertex x may be owned by any one of the three processors
Pi , Pj , or Pk , i #= j #= k (shown as vertices x1 , x2 , and x3 , respectively). In thisthird case, if the vertex x is owned by either of the processors Pj or Pk (shown as x2
and x3 ), then the color of x is nonlocal to processor Pi and needs to be relayed to Pi
through processor Pj . On the other hand, if the vertex x is owned by processor Pi(shown as x1 ), then the color of x is, strictly speaking, local to Pi and needs not berelayed via Pj . However, in the algorithm being described, since processor Pj does

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2427

Algorithm 2. Tentative coloring phase of Algorithm 1 run on processor Pi .
1: procedure TentativelyColor(Ui , s)2:Partition Ui into ni subsets Ui,1 , Ui,2 , . . . , Ui,ni , each of size s ! ni = " |Usi | #. Vertices
in Ui,! will be colored in the !th superstep by processor Pi .
for each processor-superstep pair (j, ") ∈ {{1, . . . , p} × {1, . . . , ni }}, j %= i, do
3:
j
4:
Ui,!
← {v|v ∈ Ui,! and N1 (v) ∩ Vj %= ∅} ! processor Pj is neighbor to processor Pi
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

j
Send schedules Ui,!
to each neighbor processor Pj .
i
Receive schedules Uj,!
from each neighbor processor Pj .
!j=p i
Xi,! ← j=1 Uj,!
! Vertices in Xi,! will be colored in !th step by processors Pj , j $= i
! ifor each v ∈ Xi ∪ Ui , where Xi = !=n!=1 Xi,! , docolor(v) ← 0! (re)initialize colors
L ← max1≤j≤p {nj }! L is the max number of supersteps over all processors
for " ← 1 to L do
! each ! corresponds to a superstep
i
Build lists of forbidden colors for vertices in Uj,!
.
Send the lists to each neighboring processor Pj , where " ≤ nj .
if " ≤ ni , then
! Pi has not finished coloring Ui
jReceive lists of forbidden colors for vertices in Ui,!
from each neighboring Pj .
Merge the lists of forbidden colors.
Update the lists of forbidden colors with local color information.
for each v ∈ Ui,! docolor(v) ← c such that c > 0 is the smallest “permissible” color for v
j
Send updated colors of vertices in Ui,!
to each neighboring Pj .
i
Receive updated colors of vertices in Uj,! from each neighboring Pj .

not store the adjacency lists of the vertices owned by processor Pi , it would treat thecolor of x1 as if it were nonlocal to Pi and send the color information to Pi . In otherwords, for every edge (v, w) in which vertex v is owned by processor Pi and w is owned
by Pj , processor Pj takes the responsibility of building a list of colors used by vertices
two edges away from the vertex v (a partial list of forbidden colors to v) and sending
the list to processor Pi .
4.3. The tentative coloring phase. Algorithm 2 outlines in detail the routine
TentativelyColor run on each processor Pi . The routine starts off by processor
Pi determining a coloring-schedule—a breakdown of its current set Ui of vertices tobe colored into supersteps (line 2). Processor Pi then computes and sends schedule
information to each of its neighboring processors (lines 3–5). Similarly, processor Pi
receives analogous schedules from each of its neighboring processors (line 6). This
enables each processor to know the distance-2 color information that it needs to sendin each superstep. In particular, using the schedules, for each superstep ", processor
Pi constructs a list Xi,! of vertices that will be colored by some other processor Pj insuperstep " and for which it must supply forbidden color information (line 7). Thus
with the knowledge of each Xi,! , processor Pi can be “proactive” in building up listsof relevant forbidden color information and sending these to neighboring processors
in superstep ".
Before the coloring of the vertices in the set Ui by processor Pi commences,impermissible colors assigned in a previous superstep need to be cleared. These consistof colors assigned to vertices in Ui (by processor Pi ) and colors assigned to vertices in
Xi , which are to be colored by other processors in the current round (lines 8 and 9).
Since for different processors Pi the number of vertices |Ui | to be colored could
differ, the number of supersteps required to color these vertices, ni = * |Usi | +, would also

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2428

BOZDAĞ ET AL.

vary. Processor Pi needs ni supersteps to color its vertices, but it may need to supply
forbidden color information to a neighboring processor that has not finished coloring
its vertices. Therefore, the algorithm overall needs L = max1≤j≤p {nj } supersteps(see line 10).
In each superstep, before processor Pi begins to color the set of vertices it owns,
it proactively builds and sends relevant color information to neighboring processors(lines 12 and 13). Further, to perform the coloring of its own vertices in a superstep,a processor first gathers color information from other processors to build a partial
list of forbidden colors for each of its boundary vertices scheduled to be colored in
the current superstep. After the processor has received the partial lists of forbidden
colors from all of its neighboring processors, it merges these lists and augments themwith local color information to determine a complete list of forbidden colors for its
vertices scheduled to be colored in the current superstep. Using this information, theprocessor then speculatively colors the vertices of the current superstep. At the endof the superstep, the new color information is sent to neighboring processors. These
actions are performed in the piece of code in lines 14–20. Regardless of whether aprocessor has finished coloring all of its vertices or not, it needs to receive updated
color information from neighboring processors (see line 21). This information is needed
to enable the processor to compile forbidden color information to be sent to otherprocessors in the next superstep.
4.4. The conflict detection phase. Algorithm 3 outlines the conflict detection
routine DetectConflicts executed on each processor Pi . The routine has two majorparts. In the first part, the routine finds a subset Wi ⊂ Vi of vertices that processor
Pi needs to examine to detect both type 1 and type 2 conflicts. Whenever a conflictis detected, one of the involved vertices is selected to be recolored in the next roundto resolve the conflict. The selection makes use of the random values assigned toboundary vertices in Algorithm 1. In the second part, the routine determines andreturns a set of vertices to be recolored by processor Pi in the next round.
Two vertices would be involved in a conflict only if they are colored in the same
superstep. Thus the vertex set Wi needs consist only of (1) every vertex v ∈ Ui
that has at least one distance-1 neighbor on a processor Pj , j #= i, colored in thesame superstep as v, and (2) every vertex v ∈ Vi that has at least two distance-1
neighbors on different processors that are colored in the same superstep, since thesemight be assigned the same color. To obtain elements of the set Wi that satisfy one orboth of these two conditions in an efficient manner, in Algorithm 3 relevant vertices
on processor Pi are traversed a superstep at a time, using the schedule computedin Algorithm 2. In each superstep ", first each vertex in Ui,! and its neighboringboundary vertices are marked. Then, for each vertex v ∈ Xi,! the vertices in the set
N1 (v) owned by processor Pi are marked. If this causes some vertex to be marked
twice during the same superstep, then the vertex is added to Wi . The determinationof the set Wi is achieved by the piece of code in lines 3–7 of Algorithm 3; details areomitted for brevity.
Turning to the second part of Algorithm 3, processor Pi accumulates a list Ri,jof vertices to be recolored by each processor Pj in the next round. To detect conflicts
around a vertex w in the set Wi , we need to look for vertices in the set N̄1 (w) =N1 (w) ∪ {w} that have the same color. In a valid distance-2 coloring, every vertex in
the set N̄1 (w) needs to have a distinct color. If several vertices with the same color arefound, we let the vertex with the lowest random value keep its color and recolor the
rest. To perform these tasks efficiently, we use two color-indexed, one-dimensional,

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2429

Algorithm 3. Conflict detection phase of Algorithm 1 run on processor Pi .
1: function DetectConflicts2:
Wi ← ∅! Wi is the set of vertices Pi examines to detect conflicts
3:for " ← 1 to L do
! uses schedules computed in Algorithm 2
4:for each w ∈ Ui,! , where w has at least one neighbor in Xi,! , do
5:
Wi ← Wi ∪ {w}! w is used for detecting type 1 conflicts
6:
for each w ∈ Vi , where w has at least two neighbors in Xi,! ∪ Ui,! on different
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

processors, doWi ← Wi ∪ {w}! w is used for detecting type 2 conflicts
for each j ∈ P = {1, . . . , p} do
Ri,j ← ∅! Ri,j is a set of vertices Pi notifies Pj to recolor
for each w ∈ Wi do
encountered[color(w)] ← w
lowest[color(w)] ← w
for each x ∈ N1 (w) do
if encountered[color(x)] = w, thenv ← lowest[color(x)]if rand(v) ≤ rand(x), then! rand(u): random number assigned to u
if v %= w, thenRi,Id(x) ← Ri,Id(x) ∪ {x}! Id(u): ID of processor owning uelse
Ri,Id(v) ← Ri,Id(v) ∪ {v}lowest[color(x)] ← x
else
encountered[color(x)] ← w
lowest[color(x)] ← xfor each j ∈ P , j %= i do
Send Ri,j to processor Pj .
for each j ∈ P , j %= i do
Receive Rj,i from processor Pj .
Ri,i ← Ri,i ∪ Rj,ireturn Ri,iarrays—encountered and lowest—that store vertices. The values stored in the twoarrays encode information that is updated and used in a for-loop that iterates overeach vertex w ∈ Wi . The context in each iteration in turn is a visit through theneighborhood N1 (w) of the vertex w. For each vertex w, encountered[c] = w indicatesthat at least one vertex in the set N̄1 (w) having the color c has been encountered,and lowest[c] stores the vertex with the lowest random value among these. Initially,both encountered[color(w)] and lowest[color(w)] are set to be w. This ensures thatany conflict involving the vertex w and one of the vertices in the set N1 (w) would
be discovered. To detect conflicts involving the neighbors of w, the algorithm checks
whether a given color used by a vertex in N1 (w) has been encountered more thanonce, and, if so, the vertex to be recolored is determined using the random values
assigned to the vertices and the array lowest is updated accordingly. See the for-loop
in lines 10–24 for details.
In Algorithm 3, a type 1 conflict involving adjacent vertices is detected by bothof the implied processors. Thus the if-test in line 17 is included to avoid sending
unnecessary notification from one processor to the other. Note also that in line 13 it
would have been sufficient to check for conflicts using only vertices N1 % (w) ⊆ N1 (w)that belong to either Ui or Xi . However, since determining the subset N1 % (w) takes
more time than testing for a conflict, we use the larger set N1 (w) in line 13.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2430

BOZDAĞ ET AL.

When the lists Ri,j that processor Pi accumulates are complete, processor Pi
sends each list Ri,j to processor Pj , j #= i, to notify the latter to do the recoloring(lines 25–26). Processor Pi itself is responsible for recoloring the vertices in Ri,i andtherefore adds to Ri,i notifications Rj,i received from each neighboring processor Pj(lines 27–29).
4.5. Complexity analysis. In Algorithm 2, the overall sequential work carriedout by processor Pi and its neighboring processors in order to perform the coloring of
the vertices in Ui is O(Σv∈Ui d2 (v)). Summing over all processors, the total work (ex"cluding communication cost) involved in coloring the vertices in the set U = i=p
i=1 Uiis O(Σv∈U d2 (v)), which is equivalent to the complexity of a sequential algorithm forcoloring the vertex set U .
Turning to the communication cost involved in Algorithm 2, note that for eachvertex v ∈ Ui every neighboring processor sends to processor Pi the union of the colors
used by vertices at exactly two edges from the vertex v, while the color of the vertex
v is sent to every processor that owns a distance-1 neighbor of v. Thus the total sizeof data exchanged while coloring the vertex v is bounded by O(d2 (v)), which in turn"i=pgives the bound O(Σv∈U d2 (v)), where U = i=1 Ui , on the overall communication
cost of Algorithm 2.
In Algorithm 3, in determining the set Wi (in lines 3–7), at most |Vi | vertices areprocessed. The per-vertex work involved in this process is proportional to the degree1 of the vertex. Hence, the time needed to determine Wi is bounded by O(|Vi |d1 ),where d1 is the average degree-1 in the input graph G. Further, in each iteration of thefor-loop over the set Wi in lines 10–24, the set of vertices to be recolored is determinedin time O(d1 (w)), which gives a complexity of O(|Wi |d1 ) for the entire for-loop. Since|Wi | ≤ |Vi | clearly holds, the overall complexity of Algorithm 3 is O(|Vi |d1 ).
With the complexities of Algorithms 2 and 3 just established and assuming thatthe number of rounds required in Algorithm 1 is sufficiently small, the total work
carried out by all of the p processors in coloring the input graph G = (V, E) is O(|V|d2 ),which is the same as the complexity of the sequential algorithm.
The assumption that the number of rounds needed by Algorithm 1 is small isrealistic. It is supported empirically by the experimental results to be presented
in section 6, where the number of rounds for test graphs with millions of edges andrepresenting a wide variety of structures and processor count in the order of a hundred
is observed to be in the order of ten. It is hard to provide a reasonable analyticalestimate on the number of rounds needed, as such an analysis would involve several
complicated factors, including the size and structure of the input graph, the mannerin which vertices are partitioned among processors, the order in which vertices arecolored, and the random numbers assigned to vertices.
Meanwhile, a very loose upper bound on the number of rounds is s · p, where sis the superstep size and p is the number of processors. And here is why the boundholds. First, note that a total of s · p vertices are colored in one superstep, and recall
that conflicts occur only between vertices colored in the same superstep. At the endof a round, only vertices involved in conflicts (and in fact only some of those) aremarked to be recolored. If a vertex is not marked to be recolored at the end of around, it will never be involved in conflicts in subsequent rounds (since its color will
be forbidden to neighbors), and hence its color does not change. Algorithm 3 ensuresthat, among the vertices involved in conflicts, those vertices with the smallest random
numbers in their neighborhood retain their colors, i.e., are not marked for recoloring.
As a result, at the very least, one vertex among the s · p vertices colored in the same

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2431

superstep is guaranteed to receive its final color in a round. Therefore, the number ofrounds can never exceed s · p.
In practice, the number of vertices that get their final colors in a round is likely
to be much much greater than one, making the bound s · p extremely unlikely to everbe attained. In fact, as the experimental results in section 6 will show, typically, morethan 90% of the vertices of an input graph get their final colors in the first round. And
the remaining 10% of the vertices get their final colors in a small number of rounds
since the number of conflicts drops rapidly between successive rounds.
4.6. Variations. Algorithm 1 and its subroutines Algorithms 2 and 3 could bespecialized along several axes to result in a variety of derived algorithms. We discuss
three of these axes.
First, in Algorithm 1, interior vertices (Ii ) are colored before boundary vertices(Bi ), but the reverse order could also be considered.
Second, while coloring the vertices in a superstep on each processor (see line 18of Algorithm 2), the natural ordering of the vertices, a random ordering, or any other
degree-based ordering technique could be used [17].
Third, the choice of a color for a vertex in a superstep (see line 19 of Algorithm 2)
could be done in several different ways. For example, a first fit (FF), a staggered firstfit (SFF), or a randomized coloring strategy could be used [6]. In the FF strategy,
each processor chooses the smallest allowable color for a vertex, starting from color 1.
In the SFF strategy, each processor Pi chooses the smallest permissible color from theset {* iK
p +, . . . , K}, where the initial estimate K is set to be, for example, equal to
the lower bound ∆ + 1 on the distance-2 chromatic number. If no such color exists,then the smallest permissible color in {1, . . . , / iKp 0} is chosen. If there still is no suchcolor, the smallest permissible color greater than K is chosen. Since the search for acolor in SFF starts from different “base colors” for each processor, SFF is likely toresult in fewer conflicts than FF.
5. Parallel restricted star and partial distance-2 coloring. The algorithms
presented in the previous section need to be modified only slightly to solve the two
related problems of our concern, restricted star coloring on a general graph (for Hessian computation) and partial distance-2 coloring on a bipartite graph (for Jacobiancomputation). In this section we point out the specific changes that need to be madein Algorithms 1–3 to address these two problems.
5.1. Restricted star coloring. As the definition given in section 2.2 implies,
in a restricted star coloring of a graph, the color assigned to a vertex v needs to satisfy
conditions that concern the distance-2 neighbors N2 (v) of the vertex v. The exact
same neighborhood is consulted in assigning a color for the vertex v in a distance2 coloring of the graph. Therefore, the greedy algorithms for the two variants ofcoloring (as developed in [17]) differ only in the way the set of forbidden colors for thevertex v is determined. We describe this difference below in the sequential setting;the additional differences that arise in the parallel setting are fairly straightforward
to implement, and their discussion is omitted.
Consider the step of a greedy algorithm (distance-2 or restricted star coloring)in which the vertex v is to be colored, and let v, w, x be a path in the distance-2
neighborhood of the vertex v. In the distance-2 coloring algorithm, both color(w)and color(x) are forbidden to the vertex v, since the path needs to have three distinct
colors. In the restricted star coloring algorithm, on the other hand, color(w) would

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2432

BOZDAĞ ET AL.

always be forbidden to v, whereas color(x) may or may not be forbidden. The decisionin the latter case is made based on further tests:• If color(w) = 0 (i.e., vertex w is not yet colored), then color(x) is forbidden
to v. This ensures that any extension v, w, x, y of the path v, w, x would end
up using at least three colors, as desired, since in the step in which the vertex
w is colored the distance-1 coloring requirement guarantees that the vertex
w gets a color distinct from color(v) and color(x).
• If color(w) #= 0, then color(x) is forbidden to v only if color(w) > color(x).
5.2. Partial distance-2 coloring. Here, the input is a bipartite graph Gb =(V1 , V2 , E), and only the vertex set V2 needs to be colored satisfying the condition
that a pair of vertices from V2 sharing a common distance-1 neighbor in V1 receive
different colors. If not already distributed, the graph Gb needs to be partitioned
among the processors in a manner that minimizes boundary vertices (and hence thelikelihood of conflicts and the size of overall communication). Assuming that a vertex
partitioning is used, let V1,1 , . . . , V1,p denote the partitioning of the set V1 , and let
V2,1 , . . . , V2,p denote the partitioning of the set V2 . The subgraph assigned to processor
Pi would then be Gb,i = (V1,i , V2,i , Ei ), where Ei is the set of edges incident on
vertices in V1,i ∪ V2,i . In terms of the underlying matrix, such a partitioning meansthat each processor owns a subset of the rows as well as a subset of the columns;
this is in contrast with the case where either only the columns or only the rows are
partitioned. With such a partitioning in place, the only change that needs to be madein Algorithm 1 is to replace the two references to Vi (in lines 4 and 5) with V2,i .
The changes that need to be made in Algorithms 2 and 3 are minimal as well, andthey are consequences of the basic difference between distance-2 coloring in a generalgraph G = (V, E) and partial distance-2 coloring in a bipartite graph Gb = (V1 , V2 , E)
illustrated by the code fragment in Algorithm 4.
Algorithm 4. Basic difference between distance-2 and partial distance-2 coloring.
procedure D2Coloring(G = (V, E))for each v ∈ V dofor each w ∈ N1 (v) do
Forbid color(w) to v.
for each x ∈ N1 (w) do
Forbid color(x) to v.
Assign a color to vertex v.

procedure PD2Coloring(Gb = (V1 , V2 , E))for each v ∈ V2 dofor each w ∈ N1 (v) do" w ∈ V1 never receives a color
for each x ∈ N1 (w) do
Forbid color(x) to v. " x ∈ V2
Assign a color to vertex v.

6. Experiments. We have implemented the algorithms presented in the previous two sections in the programming language C and using the message-passing
interface (MPI) library. We report in this section on experimental evaluation of theperformance of the algorithms. In particular, we present in sections 6.4 and 6.5
detailed experimental results on the performance of the parallel distance-2 coloringalgorithm for general graphs, and in sections 6.6 and 6.7 results on restricted starcoloring of general graphs and partial distance-2 coloring of bipartite graphs, respectively. In section 6.8 we present results on the alternative approach of obtaining a
distance-2 coloring of a graph by a distance-1 coloring of the square graph. We begin
the section with a discussion of the test platform and test graphs used (largely forthe experiments on the parallel algorithm for distance-2 coloring of general graphs)
in section 6.1, a comment on the performance of the underlying sequential algorithms
in section 6.2, and a discussion of the choice of a superstep size for the parallel algorithms in section 6.3. Some of the experiments on the restricted star coloring and

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2433

Table 6.1
Structural properties of the application (top), and the synthetic (bottom) test graphs used inmany of the experiments. The last column shows the number of edges in G 2 = (V, F ) comparedto G = (V, E). (ST–structural engineering [11], SH–ship section [3], CA–linear car analysis [3],AU–automotive [11], CE–civil engineering [11].)
App/
class
ST

SH

CA

AU

CE
planarrandomrandoms. world
s. world

Namenasasrb
ct20stif
pwtk
shipsec8
shipsec1
shipsec5bmw7st1
bmw3 2
inline1hoodmsdoorldoor
pkustk10
pkustk11
pkustk13
plan-1
rand-1
rand-2
sw-1
sw-2

|V|

|E|

54,87052,329217,918
114,919
140,874
179,860
141,347
227,362
503,712220,542
415,863952,203
80,67687,804
94,893
4,072,937
400,000
400,000
400,000
400,000

1,311,227
1,323,067
5,708,253
3,269,240
3,836,265
4,966,618
3,599,160
5,530,634
18,156,315
5,273,947
9,912,536
22,785,136
2,114,154
2,565,054
3,260,967
12,218,805
2,002,202
4,004,480
1,998,542
3,993,994

DegreeMax Avg

Colorsd1
d2

Exec. time (s)
d1
d2

275
206
179
131
101
125
434
335
842
76
76
76
89
131
299
40
27
45
468
880

41
49
48
54
48
50
54
48
51
42
42
42
42
66
57
9
9
12
18
27

0.049
0.063
0.229
0.128
0.143
0.190
0.167
0.274
0.925
0.277
0.520
1.197
0.091
0.103
0.155
3.435
0.644
1.242
0.345
0.632

48
51
52
57
55
55
51
49
72
48
48
48
52
58
69
6
10
20
10
20

276
210
180
150
126
140
435
336
843
103
105
112
126
198
303
41
41
101
469
882

2.237
2.581
10.335
6.776
7.457
9.852
6.730
10.07755.2179.407
17.43840.180
3.904
6.041
9.302
18.8806.676
21.97713.90950.954

|F |
|E|

3.2
3.8
2.9
3.5
3.1
3.2
3.3
3.2
7.0
3.2
3.2
3.2
2.9
4.2
6.0
3.4
11
21
31
59

partial distance-2 coloring experiments are conducted on additional test graphs, andthese graphs will be presented in sections 6.6 and 6.7.
6.1. Experimental setup.
Test platform. The experiments are largely carried out on a 96-node PC cluster
equipped with dual 2.4 GHz Intel P4 Xeon CPUs and 4 GB memory. The nodes of
the cluster are interconnected via a switched 10 Gbps Infiniband network.
Test graphs. Our first test set consists of 15 real-world graphs obtained fromfive different application areas: structural engineering, ship section design, linear car
analysis, automotive design, and civil engineering [14, 28, 11, 3]. The top part ofTable 6.1 lists the number of vertices, number of edges, maximum degree-1, andaverage degree-1 in each of these test graphs. The graphs are classified according to
the application area from which they are drawn. Table 6.1 also lists the number ofcolors and the execution time in seconds used by greedy sequential distance-1 anddistance-2 coloring algorithms when each is run on a single node of our test platform.
The last column lists the ratio between the number of edges in the square graph G 2
and the number of edges in G. These computed quantities will be used to gauge theperformance of the proposed parallel coloring algorithms on the input graphs G.
To be able to study the scalability of the proposed algorithms on a wider rangeof graph structures, we have also run experiments on synthetically generated graphs,
which constitute our second test set. To represent extreme cases, we considered
synthetic graphs drawn from three different classes: random, planar, and small-worldgraphs. (Loosely speaking, a small-world graph is a graph in which the distance
between any pair of nonadjacent vertices is fairly small [25].) The random and smallworld graphs are generated using the GTgraph synthetic graph generator suite [30].

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2434

BOZDAĞ ET AL.

The planar graphs are maximally planar—the degree of every vertex is at least 5—andare generated using the expansion method described in [24]; the generator is a part of
the graph suite for the Second DIMACS Challenge [29]. The structural properties ofthese graphs as well as the number of colors and runtime used by sequential distance1 and distance-2 coloring algorithms run on them are listed in the bottom part ofTable 6.1.
In the runtimes reported in Table 6.1 as well as in later figures in this section,
each individual test is an average of five runs. In the timing of the parallel coloring
code, we assume that the graph is initially partitioned and distributed among thenodes of the parallel machine, and thus the times reported concern only coloring. In
all of the experiments, the input graph is partitioned using the tool MeTiS [20].
6.2. Performance of the sequential algorithms. Before presenting resultson the performance of the proposed parallel coloring algorithms, it is worth pointing
out that the underlying sequential greedy algorithms, in the distance-1 as well as
distance-2 coloring cases, performed remarkably well in terms of number of colors usedon both the application and synthetic test graphs. Specifically, as Table 6.1 shows,the number of colors used by the greedy sequential distance-1 coloring algorithm isin most cases slightly below the average degree and far below the maximum degree,which is an upper bound on the optimal solution (the distance-1 chromatic number).
Even more remarkably, the number of colors used by the greedy sequential distance-2
coloring algorithm in most cases is observed to be very close to the maximum degree,which is a lower bound on the optimal solution (the distance-2 chromatic number).
This implies that the solution obtained by the greedy distance-2 coloring algorithm
is in most cases either optimal or just a few colors more. In both the distance-1 anddistance-2 coloring greedy algorithms, vertices were colored in the natural order inwhich they appear in the input graphs; i.e., no reordering techniques were used.
6.3. Choice of superstep size. Our first set of experiments is conducted to
study the dependence of the performance of the parallel distance-2 coloring algorithm(Algorithm 1) on the choice of the superstep size s, the number of vertices coloredin a superstep before communication takes place, for a fixed number of processors.
The results of this set of experiments are given in Figure 6.1. The experiments are
conducted using the application test graphs, and the reported results are averages
over each class. The number of processors used in the experiments is 32; we obtained
similar results while experimenting with various other numbers of processors, but forspace considerations we report results only for 32 processors.
Figure 6.1(a) shows the number of conflicts, normalized relative to the total number of vertices in the graph, as a function of superstep size. Figure 6.1(b) shows asimilar plot of the number of rounds required by the algorithm. As one would expect,
the normalized number of conflicts and the number of rounds increased as the superstep size s increased, but the rate of increase remained fairly low once the value of spassed a few hundred. Furthermore, it can be seen that both of these quantities are
small in magnitude: the normalized number of conflicts was at most about 15%, andthe number of rounds was at most around 16. Figure 6.1(c) shows that, for values ofs above a few hundred, further increase in s does not significantly influence speedup.
Similarly, as shown in Figure 6.1(d), the number of colors does not vary significantlywith s and stays within 12% of the number of colors used by the sequential algorithm.
In general, an “optimal” value for s is likely to depend on both the properties of thegraph being colored (size and density) and the platform on which the algorithm is

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2435

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

0.14
0.12

14

0.1
0.08
0.06
0.04

12
10
8
6
4

0.02
0
0

AU
ST
SH
CA
CE

16

AU
ST
SH
CA
CE

Number of rounds

Number of conflicts / |v|

0.16

2
500

1000

1500

2000

Superstep size

2500

0

3000

500

1000

25

Speedup

20
15
10
AU
ST
SH
CA
CE

5

500

1000

1500

2000

Superstep size

(c)

2000

2500

3000

2000

2500

3000

(b)

2500

3000

Normalized number of colors

(a)

0
0

1500

Superstep size

1.15
1.1
1.05
1
0.95
0.9
0.85
0.8
0

AU
ST
SH
CA
CE
500

1000

1500

Superstep size(d)Fig. 6.1. Normalized number of conflicts (a), number of rounds (b), speedup (c), and normalized
number of colors (d) in the parallel distance-2 coloring algorithm while the superstep size s for theapplication test graphs listed in Table 6.1 is varied. In all cases, the number of processors was fixed
at p = 32.

executed. Based on observations from our parallel experiments, we used a superstep
size of s = 100 for the scalability studies we report on in the rest of this section.
6.4. Results on parallel distance-2 coloring of general graphs.
6.4.1. Strong scaling results. Our second set of experiments is concerned withthe strong scalability of the parallel distance-2 coloring algorithm as the number ofprocessors used is varied. This set of experiments was conducted on both the application and synthetic test graphs listed in Table 6.1. The results from the experimentson the application graphs are summarized in Figure 6.2, and those from the synthetic
graphs are summarized in Figure 6.3. In the results shown in Figure 6.2, for eachapplication category, the largest graph from the category was used. A more detailed
set of results on all of the application test graphs (for the distance-2 as well as the
restricted star coloring algorithm) is included in a table in the appendix.
Results on application test graphs. The results in Figures 6.2(a) and (b) show thatthe number of conflicts and the number of rounds increase with increasing numbers ofprocessors. However, the rate of growth as well as the actual values of both of thesequantities were observed to be fairly small. For the graphs pkustk13 and inline1, thedensest graphs in our test set, the numbers are relatively larger. The reason for the

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2436

BOZDAĞ ET AL.
20

0.08

18

Number of rounds

Number of conflicts / |v|

0.1

ldoor
pwtk
shipsec5
inline_1
pkustk13

0.06
0.04
0.02
0
0

16
14

ldoor
pwtk
shipsec5
inline_1
pkustk13

12
10
8
6
4
2

20

40

60

80

Number of processors

0

100

20

40

(a)

Speedup

50

ldoor
pwtk
shipsec5
inline_1
pkustk13

40
30
20
10
0
0

20

40

60

80

Number of processors

(c)

80

100

60

80

100

(b)

Normalized number of colors

60

60

Number of processors

100

1.15
1.1
1.05
1
0.95
0.9
0.85
0.8
0

ldoor
pwtk
shipsec5
inline_1
pkustk1320

40

Number of processors(d)Fig. 6.2. Normalized number of conflicts (a), number of rounds (b), speedup (c), and normalized
number of colors (d) in the parallel distance-2 coloring algorithm while the number of processors forthe application test graphs listed in Table 6.1 is varied. In all cases, superstep size s = 100 was used.

relatively large number of rounds required in coloring the graph inline1 is the existenceof vertices with very large degree-1 values. This phenomenon will be explained further
with the help of synthetic graphs.
The metrics number of conflicts and number of rounds are in some sense “intermediate” performance measures for our parallel coloring algorithms. They are included in
the reports to help explain results on the two ultimate performance metrics—speedup
and number of colors used. The lower row of Figure 6.2 shows results on the latter
two metrics. We will use a similar set of four metrics in several other experiments
reported in this section.
The speedup results in Figure 6.2(c) demonstrate that our algorithm in generalscales well with increasing numbers of processors. As expected, the obtained speedups
are relatively poorer in the cases where the number of conflicts and the number ofrounds are relatively higher. The proposed algorithm also performed well in termsof the number of colors used. The results in Figure 6.2(d) show that the number ofcolors used by our parallel distance-2 algorithm, when as many as 96 processors areused, is at most 12% more than that used by the sequential algorithm. Recall thatthe solution obtained by the sequential algorithm in most cases is very close to the
maximum degree in the graph—a lower bound on the optimal solution—and hence
nearly optimal.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2437

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

1160

plan−1
rand−1
rand−2
sw−1
sw−2

140

Number of rounds

Number of conflicts / |v|

1.2

0.8
0.6
0.4
0.2
0
0

120

plan−1
rand−1
rand−2
sw−1
sw−2

100
80
60
40
20

20

40

60

80

Number of processors

100

0

20

(a)
80
70

Speedup60

plan−1
rand−1
rand−2
sw−1
sw−2

50
40
30
20
10
0
0

20

40

60

80

Number of processors

(c)

60

80

100

60

80

100

(b)
Normalized number of colors

90

40

Number of processors

100

1.4
1.3
1.2
1.1
1
0.9
0.8
0

plan−1
rand−1
rand−2
sw−1
sw−2
20

40

Number of processors(d)Fig. 6.3. Normalized number of conflicts (a), number of rounds (b), speedup (c), and normalized
number of colors (d) in the parallel distance-2 coloring algorithm while the number of processors forthe synthetic test graphs in Table 6.1 is varied. In all cases, superstep size s = 100 was used.

Number of rounds. Notice that the number of rounds in Figure 6.2(b) is observed
to be at most 19 (achieved when 64 processors are used), which is very small comparedto the bound s · p (which is equal to 100 × 64 = 6,400) discussed in section 4.5. The
major reason for the huge difference between the bound s · p and the actual numberof rounds is the fact that a vast majority of the vertices colored in a round get their
final colors in the same round, and only a small fraction need to be recolored ina subsequent round. In other words, the number of conflicts detected in a roundis small, and out of that small number only a portion will necessitate recoloring ofvertices. To provide evidence for this fact, we present Figure 6.4, which shows resultson the five application test graphs used in the experiments of Figure 6.2. Figure 6.4(a)shows the fraction of boundary vertices that get their final colors in each round of the
distance-2 coloring algorithm until a valid coloring is achieved. For each test graph in
the figure, the leftmost bar corresponds to the first round, the next bar to the rightcorresponds to the second round, and so on. It can be seen that typically more than
90% of the boundary vertices get their final colors in the very first round, and theremaining vertices eventually get their final colors in a matter of just a few rounds.
Figure 6.4(b) shows how the number of vertices colored in a round translates into
execution time. The bottom portion of the bars in this figure shows time spent in
the tentative coloring phase, and the top portion shows the time spent in the conflict

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

BOZDAĞ ET AL.
1

1

0.9

0.9

Fraction of boundary vertices

Fraction of boundary vertices

2438

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1

ldoor

pwtk

shipsec5(a)inline1pkustk13

0

ldoor

pwtk

shipsec5

inline1pkustk13(b)

Fig. 6.4. Fraction of boundary vertices colored (a) and fraction of time spent (b) in each roundof the parallel distance-2 coloring algorithm. For each test graph, the leftmost bar corresponds tothe first round, the next bar to the right corresponds to the second round, and so on. Each bar in(b) is divided into time spent on coloring (black) and time spent on conflict detection (white). In
all cases, the number of processors was fixed at p = 32, and superstep size was s = 100.

detection phase of each round of the distance-2 coloring algorithm. The results showthat most of the time in a round is spent in the tentative coloring phase, and the total
time spent in a round is proportional to the number of vertices colored in that round.
Results on synthetic test graphs. We now turn our attention to results on thesynthetic graphs, which are designed to capture “extreme cases.” The planar graphplan-1 represents partitionable graphs extremely well—almost all of the vertices ofplan-1 became interior vertices in a partition obtained using the tool MeTiS [20].
For such graphs, parallel speedup in the context of Algorithm 1 comes largely fromgraph partitioning (data distribution) as opposed to the iterative coloring part. As
Figure 6.3 shows, this results in a very small number of conflicts and good speedup.
The random graphs rand-1 and rand-2 represent the opposite extreme—almost
all of the vertices in these graphs become boundary vertices regardless of how thegraph is partitioned. As expected, Figure 6.3 shows that the number of conflicts is
considerably larger for the random graphs. Nonetheless, our algorithm achieved some
speedup (a constant around 10) even under such an extreme case. Note that the
speedup in this case comes solely from the iterative coloring part.
As mentioned earlier, graphs having vertices with very large degrees comprisea particularly difficult set of instances for the proposed parallel distance-2 coloringalgorithm. Resolving conflicts involving the neighbors of such vertices requires alarge number of rounds, which in turn degrades speedup. The third category in our
synthetic graphs, the small-world graphs sw-1 and sw-2, is included to represent sucha class of pathological instances for our approach. As Figure 6.3 shows, even though
the number of conflicts for small-world graphs is not necessarily larger than that for
random graphs with similar sizes, coloring small-world graphs requires a significantly
larger number of rounds. Consequently, the speedup achieved was poorer—it wasaround 3 for all numbers of processors used in our experiments.
As can be seen from Figure 6.3(d), the normalized number of colors for all thesynthetic graphs except rand-2 is within 12% of the sequential algorithm. In the caseof the graph rand-2, the algorithm involved relatively many conflicts but few rounds,
implying that many processors had to recolor a fairly large number of vertices in each

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2439

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION
7

|V|

|E|

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

1,625,972
3,250,939
4,888,479
6,513,589
8,150,267
160,000
320,000
480,000
640,000
800,000

4,877,910
9,752,811
14,665,431
19,540,761
24,450,795
1,600,528
3,201,327
4,803,946
6,403,242
8,005,505

Degree
Max
Avg
37
6
43
6
43
6
38
6
39
6
45
20
46
20
43
20
44
20
45
20

6

Run time (seconds)

Name

randomplanar

5
4
3
2
1
0
0

20

40

60

Number of processors

80

Fig. 6.5. Properties of the synthetic test graphs used in weak scaling tests (left) and results forthe parallel distance-2 coloring algorithm (right).

round to resolve the conflicts. Over multiple rounds, this resulted in a significant
increase in the number of colors used. This phenomenon is in contrast to that insmall-world graphs, where many fewer vertices are recolored in many more rounds.
The latter resembles sequential coloring; hence the number of colors increases only
slightly.
6.4.2. Weak scaling. Our next set of experimental results is on weak scalability,
where problem size and number of processors are increased in proportion so as toresult in nearly constant runtime. The experiments were conducted on five instancesfrom each of the random and planar graph classes. The structural properties ofthese graphs and the experimental results obtained using them are summarized in
Figure 6.5. It can be seen that the algorithm behaved almost ideally for planargraphs—the runtime remained nearly constant as the problem size and the number ofprocessors were increased in proportion. For the random graphs, the runtime grew,
but it did so fairly slowly.
6.5. Variations of the algorithm. In the results presented thus far in this section, a variant of the proposed distance-2 coloring algorithm with the following combination of parameters was used: interior vertices were colored before boundary vertices;
the natural ordering of the vertices was used while coloring; and an FF color choicestrategy was employed. In addition to this “default” variant, we experimented withseven other variations obtained via various combinations in which interior vertices arecolored after boundary vertices, a random vertex ordering is used while coloring, andan SFF color choice strategy (as discussed in section 4.6) is used. The experiments
showed that the only variant that resulted in better performance in the majority ofthe test cases compared to the default variant was a variant that used the SFF coloring strategy. Figure 6.6 shows the performance of the SFF-coloring–based variant
on the synthetic test graphs. Results on the application graphs are omitted, as no
significant improvement over the FF-based variant was observed.
As Figure 6.6 shows, the performance improvement with SFF was especially significant for the random and small-world graphs. The number of conflicts and thenumber of rounds were much smaller for these graphs when SFF is used instead ofFF; hence better speedup was achieved. For small-world graphs, the SFF strategy
required significantly more colors than FF, whereas for random graphs SFF required

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2440

BOZDAĞ ET AL.

1160

plan−1
rand−1
rand−2
sw−1
sw−2

140

Number of rounds

Number of conflicts / |v|

1.2

0.8
0.6
0.4
0.2
0
0

120

plan−1
rand−1
rand−2
sw−1
sw−2

100
80
60
40
20

20

40

60

80

Number of processors

100

0

20

(a)
80
70

Speedup60

plan−1
rand−1
rand−2
sw−1
sw−2

50
40
30
20
10
0
0

20

40

60

80

Number of processors

(c)

60

80

100

60

80

100

(b)
Normalized number of colors

90

40

Number of processors

100

1.4
1.3
1.2
1.1
1
0.9
0.8
0

plan−1
rand−1
rand−2
sw−1
sw−2
20

40

Number of processors(d)Fig. 6.6. Normalized number of conflicts (a), number of rounds (b), speedup (c), and normalized
number of colors (d) in the parallel distance-2 coloring algorithm using an SFF color selection
strategy and while the number of processors for the synthetic graphs listed in Table 6.1 was varied.
In all cases, superstep size s = 100 was used.

about the same number of colors for the random graph rand-1 and fewer colors forthe denser random graph rand-2.
6.6. Results on parallel restricted star coloring. As discussed in section 5,
a parallel restricted star coloring of a graph can be obtained via a slight modification of
the parallel distance-2 coloring algorithm. We performed the necessary modifications
and carried out experiments on the scalability of the resulting restricted star coloringalgorithm. Figure 6.7(a) shows speedup results obtained when the restricted starcoloring algorithm was run on the largest graph from each of the application graphclasses listed in Table 6.1. As expected, these speedup results are very similar to thosefor distance-2 coloring (Figure 6.2(c)). The number of colors used by the parallel
restricted star coloring algorithm normalized by the respective numbers used by thesequential restricted star coloring algorithm are given in Figure 6.7(b), and it canbe seen that the increase in four of the five graphs is below 10%. As the table in
Figure 6.7(c) shows, restricted star coloring of a graph could use significantly fewer
colors than a distance-2 coloring, demonstrating the advantage of exploiting symmetryin Hessian computation. (For a more detailed listing of the number of colors and otherinformation concerning restricted star and distance-2 coloring of all of the applicationgraphs in Table 6.1, see Table A.1 in the appendix.)

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

Speedup

50

ldoor
pwtk
shipsec5
inline_1
pkustk13

Normalized number of colors

60

40
30
20
10
0
0

20

40

60

80

Number of processors

1.4
1.3

ldoor
pwtk
shipsec5
inline_1
pkustk13

1.2
1.1
1
0.9
0.8
0

100

2441

20

40

60

80

Number of processors

(a)

100

(b)

r.star (nr. colors)
distance-2 (nr. colors)

ldoor
91
112

pwtk
180
180
(c)

shipsec5
141140

inline1843
843

pkustk13279
303

Fig. 6.7. (a) and (b) Speedup and normalized number of colors of the parallel restricted star coloring algorithm on select application graphs from Table 6.1. (c) Number of colors used by sequential
versions of the restricted star and the distance-2 coloring algorithms.
Table 6.2
Top: Properties of additional test graphs [28, 17] used for experiments on restricted star coloring. Bottom: Results of the parallel restricted star coloring algorithm on the listed graphs.
Name

|V|

|E|

mol1-3mol1-4
apoa1-10
apoa1-12mol1-6

131,072
131,072
92,224
92,224
131,072

5,636,096
14,680,064
17,100,850
28,886,369
50,200,576

Name
mol1-3mol1-4
apoa1-10
apoa1-12mol1-6

p = 16
27.1
20.0
20.0
18.9
15.0

DegreeMax Avg
86
86
224
224
503
371
832
626
766
766
Speedupp = 32
24.5
32.5
30.1
24.9
23.8

Number of colors
d1r.star
d2
43
197
226
100
528
583
182
976 1055
303
1688 1767
301
1891 2009

p = 64
13.0
36.3
35.4
25.6
32.2

Execution time (s)d1r.star
d2
0.10
17.4
17.1
0.23
106.3
107.4
0.12
177.2
182.3
0.20
507.4
522.3
0.72 1226.7 1273.2

Normalized nr. of colors
p = 16
p = 32
p = 64
1.11
1.17
1.21
1.17
1.24
1.31
1.18
1.27
1.51
1.20
1.45
1.81
1.27
1.49
1.94

To further demonstrate the advantage of exploiting symmetry in Hessian computation via restricted star coloring, we tested the parallel restricted star coloringalgorithm on five additional graphs obtained from a molecular dynamics application [28, 17]. The top part of Table 6.2 lists the structural properties of these graphs
as well as the number of colors and the execution time in seconds used by the sequential greedy distance-1, distance-2, and restricted star coloring algorithms. The
bottom part of Table 6.2 shows the speedup and normalized number of colors used by
the parallel restricted star coloring algorithm on these graphs for various numbers ofprocessors. These experiments were conducted on a platform different from the oneused for the graphs listed in Table 6.1; the platform here is a cluster equipped with

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2442

BOZDAĞ ET AL.

Table 6.3
Top: Structural properties of the bipartite graphs [11] used for partial distance-2 coloring experiments. Bottom: Results of the partial distance-2 coloring algorithm on the listed graphs.
Name

|V1 |

|V2 |

|E|

lhr71cstormG2
cont11 l
cage13
cage1470,304
528,185
1,468,599
445,315
1,505,785

70,304
1,377,306
1,961,394
445,315
1,505,785

1,528,092
3,459,881
5,382,999
7,479,343
27,130,349

Name
lhr71cstormG2
cont11 l
cage13
cage14

p = 16
11.3
7.4
4.8
4.6
3.4

Speedupp = 32
13.4
8.6
7.2
4.9
5.2

p = 64
6.9
5.3
6.3
3.7
3.4

Degree in V1
Max
Avg
63
10.9
48
1.8
5
1.6
39
8.4
41
9.0

Colors
65
48
8
118
136

Execution
time (s)
1.43
0.85
0.52
2.27
8.86

Normalized nr. of colors
p = 16
p = 32
p = 64
1.02
1.02
1.02
1.00
1.00
1.00
1.50
1.50
1.62
0.97
0.96
0.96
0.95
0.99
0.98

2.4 GHz Quad-Core AMD Opteron CPUs and 32 GB of memory and is interconnected
via an Infiniband network. The results in Table 6.2 show that the parallel star coloring algorithm scales quite well (near linear speedup was observed up to 32 processors,
while the speedup thereafter was quite moderate due to the relatively small size of thegraphs). The results further show that the algorithm uses a number of colors close to
the numbers used by the sequential variant and exploits available symmetry at no or
only modest increase in runtime compared to distance-2 coloring.
6.7. Results on parallel partial distance-2 coloring of bipartite graphs.
We evaluated the performance of the parallel algorithm for partial distance-2 coloringof bipartite graphs using five nonsymmetric matrices obtained from the University of
Florida Sparse Matrix Collection [11]. The structural properties of these graphs as wellas the sequential coloring results are given in the top part of Table 6.3. The parallel
partial distance-2 coloring results obtained using them are presented in the bottom
part of Table 6.3. In each test case except for cont11 l, the number of colors used by
the parallel algorithm was observed to be within 2% of that used by the sequential
algorithm. For cont11 l, the number of colors increased from 8 up to 13 when using
the parallel algorithm. In general, the speedup observed in the experiments on partial
distance-2 coloring of bipartite graphs is poorer than those observed in the distance-2
coloring of general graphs. A partial reason for this lies in the graph partitioner usedin the experiments. Specifically, in both the distance-2 coloring of general graphs andthe partial distance-2 coloring of bipartite graphs, the same partitioner (MeTiS) wasused, whereas MeTiS is designed for general graphs and does not exploit the propertiesof bipartite graphs. In particular, the partitioner tries only to achieve balance in sizes(weights) of parts by considering total number (or weight) of vertices in each partand ignores the fact that there are two groups (types) of vertices. This may lead toan imbalance among the same group of vertices in different parts, causing the poorer
performance.
6.8. Results on parallel distance-1 coloring of G 2 . As discussed in section 2,
the distance-2 coloring problem on a graph G can be solved by constructing and thendistance-1 coloring the square graph G 2 . This alternative method has the same overall

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2443

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

80
70
60

40

SpeedupSpeedup

50

90

ldoor
pwtk
shipsec5
inline_1
pkustk13

30

plan−1
rand−1
rand−2
sw−1
sw−2

7
6

Run time (seconds)

60

50
40
30

20

20
10
0
0

40

60

80

Number of processors

(a)

100

0
0

5
4
3
2
1

10
20

randomplanar

20

40

60

80

Number of processors

(b)

100

0
0

20

40

60

Number of processors

80

(c)

Fig. 6.8. (a) and (b) Speedup for distance-1 coloring of G 2 on the application test graphs andthe synthetic test graphs listed in Table 6.1, respectively. (c) Weak scaling for distance-1 coloring of
G 2 on the synthetic graphs given in Figure 6.5.

asymptotic time complexity as a greedy distance-2 coloring on the graph G, but theactual runtimes of the two approaches can differ substantially.
We have done experiments on this alternative approach using the graphs listed
in Table 6.1. For these graphs, the ratio of the number of edges in G 2 to that in G
is listed in the last column of Table 6.1. As one can see from the table, the storage
requirement for G 2 could be up to 7 times larger than what is needed for G for theapplication graphs, and up to 59 times larger for the synthetic graphs.
To construct G 2 in parallel, each processor requires the adjacency lists of distance1 neighbors of its boundary vertices. This requires communication between processors
similar to the forbidden color communication in a single round of the proposed parallel
distance-2 coloring algorithm. However, instead of a union of colors, adjacency lists
are exchanged. Thus the communication cost is higher.
Figure 6.8 shows strong and weak scaling results of the approach based on distance1 coloring of G 2 . The timing for this method includes parallel construction of G 2 andparallel distance-1 coloring of G 2 using the algorithm presented in [6]. While computing speedup, the sequential greedy distance-2 coloring algorithm is used as thereference. Therefore, the results in Figures 6.8(a) and 6.8(b) are directly comparable
to those in Figures 6.2(c) and 6.3(c), respectively. The results show that the alternative approach discussed in this section is slower and scales worse than the proposedparallel distance-2 coloring algorithm.
7. Conclusion. We have presented efficient distributed-memory parallel algorithms for three closely related coloring problems: distance-2 coloring of generalgraphs, restricted star coloring of general graphs, and partial distance-2 coloring of
bipartite graphs. These problems arise in the efficient computation of sparse Jacobianand Hessian matrices using automatic differentiation or finite differencing. The scalability of the proposed algorithms has been demonstrated on a variety of applications
as well as synthetic test graphs. MPI implementations of the algorithms have been
made available to the public through Zoltan, a software library for parallel partitioning, load balancing, and data-management services [31].
As the experimental results in section 6.4 showed, the number of rounds requiredby the parallel distance-2 coloring algorithm in coloring graphs in which a small
fraction of the vertices are of relatively very large degree (e.g., small-world graphs)
could be relatively high (in the order of a hundred). A separate treatment of suchvertices could improve the performance of the proposed algorithm. We plan to explore
this in a future work.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2444

BOZDAĞ ET AL.

Appendix.
Table A.1
Results on the parallel distance-2 coloring and restricted star coloring algorithms for the application graphs listed in Table 6.1 using the superstep size s = 100. In columns 6 and 10, thenumber of colors used by the respective sequential greedy coloring algorithm is given in parentheses.
Abbreviations: normalized (norm), number (nr), conflicts (cflicts), rounds (rnds), speedup (spdup),
number of processors (p).

p

16

48

96

Graph
name
nasasrb
ct20stif
pwtk
shipsec8
shipsec1
shipsec5bmw7st 1
bmw3 2
inline 1hood
msdoorldoor
pkustk10
pkustk11
pkustk13
nasasrb
ct20stif
pwtk
shipsec8
shipsec1
shipsec5bmw7st 1
bmw3 2
inline 1hood
msdoorldoor
pkustk10
pkustk11
pkustk13
nasasrb
ct20stif
pwtk
shipsec8
shipsec1
shipsec5bmw7st 1
bmw3 2
inline 1hood
msdoorldoor
pkustk10
pkustk11
pkustk13

Norm.
cflicts
1.21%
1.59%
0.09%
0.87%
0.85%
0.35%
0.85%
0.54%
0.36%
0.69%
0.31%
0.14%
1.28%
1.49%
1.37%
6.00%
6.21%
0.66%
2.14%
2.09%
1.06%
2.44%
1.51%
1.31%
1.67%
0.85%
0.45%
3.78%
3.84%
4.53%
10.17%
14.00%
2.02%
4.43%
3.60%
2.33%
5.59%
3.10%
2.22%
2.65%
1.65%
0.78%
8.32%
8.55%
10.18%

Distance-2 coloring
Nr. ofNr. ofrnds Spdup
colors510.1 276 (276)6
8.8 210 (210)3
13.2 180 (180)5
10.2 158 (150)4
11.4 141 (126)5
11.6 156 (140)1211.5 435 (435)4
11.2 336 (336)7
10.6 843 (843)4
13.4 108 (103)414.0 112 (105)4
14.7 119 (112)5
11.0 127 (126)5
9.4 219 (198)4
9.1 302 (303)24
8.9 276 (276)9
12.9 210 (210)5
28.7 180 (180)4
21.4 161 (150)5
22.2 134 (126)6
22.4 150 (140)1220.2 435 (435)1224.3 336 (336)1422.2 843 (843)530.8 113 (103)529.0 116 (105)4
36.5 117 (112)5
17.4 133 (126)5
16.8 209 (198)6
16.1 306 (303)23
6.7 276 (276)15
9.2 210 (210)4
43.6 180 (180)5
28.4 166 (150)6
29.6 141 (126)4
34.5 154 (140)18
16.5 435 (435)1125.8 350 (336)1535.3 843 (843)639.4 115 (103)646.1 118 (105)4
60.6 121 (112)822.2 130 (126)6
20.7 198 (198)8
21.2 314 (303)

Restricted star coloring
Norm. Nr. of
Nr. ofcflictsrnds Spdup
colors
1.98%
4
9.8 276 (100)1.32%
4
9.3 177 (210)0.66%
4
11.3 180 (180)0.95%
410.8 158 (144)0.74%
411.0 126 (126)0.56%
4
11.2 141 (141)0.66%
311.8 432 (408)0.64%
412.0 336 (204)0.26%
4
9.8 843 (843)
0.67%
4
11.6
105 (79)
0.29%
4
12.5
105 (98)
0.14%
4
12.7
112 (91)0.81%
4
10.1 120 (114)0.75%
4
8.5 183 (174)0.95%
4
9.0 303 (279)
4.87%
10
13.8 189 (100)4.42%
5
15.7 146 (210)0.75%
427.7 180 (180)1.76%
4
20.9 140 (144)1.79%
4
23.2 126 (126)1.06%
4
23.1 144 (141)1.95%
4
23.7 435 (408)
1.17%
4
27.3 336 (204)0.63%
424.2 843 (843)
1.73%
5
27.8
112 (79)
0.89%
4
28.9
108 (98)
0.46%
4
33.5
111 (91)
3.02%
5
21.1 123 (114)
3.02%
4
18.4 182 (174)2.19%
517.8 282 (279)7.90%
912.2 131 (100)11.26%
6
15.8 156 (210)2.19%
538.4 180 (180)4.53%
528.1 138 (144)2.64%
5
31.7 133 (126)2.40%
435.0 132 (141)4.08%
528.8 399 (408)2.44%
633.0 330 (204)1.46%
5
34.1 789 (843)
2.84%
4
39.4
105 (79)
1.65%
4
46.2
130 (98)
0.79%
4
58.6
111 (91)6.19%
524.9 118 (114)
6.44%
5
24.4 189 (174)4.90%
6
24.6 275 (279)

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PARALLEL GRAPH COLORING FOR DERIVATIVE COMPUTATION

2445

Acknowledgment. We thank the anonymous referees for their valuable comments, which helped us improve the presentation of this paper.
REFERENCES[1] G. Agnarsson, R. Greenlaw, and M. M. Halldórsson, On powers of chordal graphs andtheir colorings, Congr. Numer., 100 (2000), pp. 41–65.
[2] G. Agnarsson and M. M. Halldórsson, Coloring powers of planar graphs, SIAM J. Discrete
Math., 16 (2003), pp. 651–662.
[3] P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent, and J. Koster, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23 (2001),
pp. 15–41.
[4] R. H. Bisseling, Parallel Scientific Computation: A Structured Approach Using BSP and
MPI, Oxford University Press, London, 2004.
[5] D. Bozdağ, U. Catalyurek, A. H. Gebremedhin, F. Manne, E. G. Boman, andF. Özgüner, A parallel distance-2 graph coloring algorithm for distributed memory computers, in Proceedings of HPCC 2005, Lecture Notes in Comput. Sci. 3726, Springer, New
York, 2005, pp. 796–806.
[6] D. Bozdağ, A. H. Gebremedhin, F. Manne, E. G. Boman, and U. V. Catalyurek, A
framework for scalable greedy coloring on distributed-memory parallel computers, J. Parallel Distrib. Comput., 68 (2008), pp. 515–535.
[7] U. V. Catalyurek and C. Aykanat, Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, IEEE Trans. Parallel Distrib. System, 10 (1999),
pp. 673–693.
[8] T. F. Coleman and J. J. Moré, Estimation of sparse Jacobian matrices and graph coloring
problems, SIAM J. Numer. Anal., 20 (1983), pp. 187–209.
[9] T. F. Coleman and J. J. Moré, Estimation of sparse Hessian matrices and graph coloring
problems, Math. Program., 28 (1984), pp. 243–270.
[10] A. R. Curtis, M. J. D. Powell, and J. K. Reid, On the estimation of sparse Jacobianmatrices, J. Inst. Math. Appl., 13 (1974), pp. 117–119.
[11] T. Davis and Y. Hu, maintainers, University of Florida Sparse Matrix Collection, available
at http://www.cise.ufl.edu/research/sparse/matrices/.
[12] K. Devine, E. Boman, R. Heaphy, B. Hendrickson, and C. Vaughan, Zoltan data management services for parallel dynamic applications, Comput. Sci. Engrg., 4 (2002), pp. 90–97.
[13] A. H. Gebremedhin, A. Pothen, A. Tarafdar, and A. Walther, Efficient computation ofsparse Hessians using coloring and automatic differentiation, INFORMS J. Comput., 21(2009), pp. 209–223.
[14] A. H. Gebremedhin and F. Manne, Scalable parallel graph coloring algorithms, Concurrency:
Practice and Experience, 12 (2000), pp. 1131–1146.
[15] A. H. Gebremedhin, F. Manne, and A. Pothen, Parallel distance-k coloring algorithms
for numerical optimization, in Proceedings of Euro-Par 2002, Lecture Notes in Comput.
Sci. 2400, Springer, New York, 2002, pp. 912–921.
[16] A. H. Gebremedhin, F. Manne, and A. Pothen, What color is your Jacobian? Graph
coloring for computing derivatives, SIAM Rev., 47 (2005), pp. 629–705.
[17] A. H. Gebremedhin, A. Tarafdar, F. Manne, and A. Pothen, New acyclic and star coloringalgorithms with application to computing Hessians, SIAM J. Sci. Comput., 29 (2007),
pp. 1042–1072.
[18] D. Hysom and A. Pothen, A scalable parallel algorithm for incomplete factor preconditioning,
SIAM J. Sci. Comput., 22 (2001), pp. 2194–2215.
[19] M. T. Jones and P. E. Plassmann, Scalable iterative solution of sparse linear systems, Parallel
Comput., 20 (1994), pp. 753–773.
[20] G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregulargraphs, SIAM J. Sci. Comput., 20 (1998), pp. 359–392.
[21] S. O. Krumke, M. V. Marathe, and S. S. Ravi, Models and approximation algorithms forchannel assignment in radio networks, Wireless Networks, 7 (2001), pp. 575–584.
[22] V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan, End-to-end packetscheduling in wireless ad-hoc networks, in Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, SIAM, Philadelphia,
pp. 1014–1023.
[23] S. T. McCormick, Optimal approximation of sparse Hessians and its equivalence to a graphcoloring problem, Math. Program., 26 (1983), pp. 153–171.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2446

BOZDAĞ ET AL.

[24] C. A. Morgenstern and H. D. Shapiro, Heuristics for rapidly four-coloring large planargraphs, Algorithmica, 6 (1991), pp. 869–891.
[25] M. E. J. Newman, The structure and function of complex networks, SIAM Rev., 45 (2003),
pp. 167–256.
[26] M. J. D. Powell and Ph. L. Toint, On the estimation of sparse Hessian matrices, SIAM J.
Numer. Anal., 16 (1979), pp. 1060–1074.
[27] Y. Saad, ILUM: A multi-elimination ILU preconditioner for general sparse matrices, SIAM
J. Sci. Comput., 17 (1996), pp. 830–847.
[28] M. M. Strout and P. D. Hovland, Metrics and models for reordering transformations, inProceedings of the Second ACM SIGPLAN Workshop on Memory System Performance,
2004, ACM, New York, pp. 23–34.
[29] The Second DIMACS Implementation Challenge: Maximum Clique, Graph Coloring, and Satisfiability, http://dimacs.rutgers.edu/Challenges.
[30] Georgia Tech College of Computing, GTgraph: A suite of synthetic graph generators,
available at http://www-static.cc.gatech.edu/∼kamesh/GTgraph/.
[31] The Zoltan Team, Zoltan: Parallel partitioning, load balancing and data-management services, software package available online at http://www.cs.sandia.gov/Zoltan/.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.