1240

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,

VOL. 28,

NO. 5, MAY 2017

Algorithms for Balanced Graph Colorings
with Applications in Parallel Computing
Hao Lu, Mahantesh Halappanavar, Daniel Chavarrıa-Miranda, Assefaw H. Gebremedhin,
Ajay Panyala, and Ananth Kalyanaraman, Member, IEEE
Abstract—Graph coloring—in a generic sense—is used to identify subsets of independent tasks in parallel scientific computing
applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number ofparallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources
becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees aperfect balance among color classes, and its practical relaxation is referred to here as balanced coloring. In this paper, we consider
balanced coloring models in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without
increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that
aim to achieve such a balanced coloring for two variants of coloring problem, distance-1 coloring (the standard coloring problem) andpartial distance-2 coloring (defined on a bipartite graph). We present parallelization approaches for multi-core and manycorearchitectures and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we
study the impact of the proposed balanced coloring heuristics on a concrete application-viz. parallel community detection, which is an
example of an irregular application. In addition, we propose several extensions to our basic balancing schemes and evaluate theirbalancing efficacy and performance characteristics. The thorough treatment of balanced coloring presented in this paper fromalgorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel
performance of their applications using coloring.
Index Terms—Balanced coloring, parallel graph coloring, distance-1 coloring, partial distance-2 coloring, Tilera manycore architecture,community detection, graph algorithms

Ç1

INTRODUCTIOND

ECOMPOSING a computational task into constituent
parts that can be executed simultaneously or identifying elements of composite data that can be safely updated
simultaneously is a pervasive primitive in parallel computing. An associated need is that of scheduling the identified
subtasks (or data update operations) onto the processing
units of a platform. In such a scenario, one would, for performance reasons, need to both maximize the amount ofparallel execution (or data update) attained in a given stepand minimize the total number of steps needed. In cases
where the computational or data dependency between entities can be abstracted using a graph, this dual objective canbe modeled and solved as a graph coloring problem.
In this paper, we consider two types of graph coloring
problems: distance-1 coloring, which is defined on a general(unipartite) graph, and, partial distance-2 coloring, which isdefined on a bipartite graph. A distance-1 coloring of a

H. Lu, A.H. Gebremedhi, and A. Kalyanaraman are with Washington
State University, Pullman, WA 99164. E-mail: luhowardmark@wsu.edu,{assefaw, ananth}@eecs.wsu.edu.
 M. Halappanavar, D. Chavarrıa-Miranda, and P. Panyala are with PacificNorthwest National Laboratory, Richland, WA 99354.
E-mail: {hala, daniel.chavarria, ajay.panyala}@pnnl.gov.
Manuscript received 29 Oct. 2015; revised 31 Aug. 2016; accepted 9 Sept.
2016. Date of publication 21 Oct. 2016; date of current version 12 Apr. 2017.
Recommended for acceptance by R. Vuduc.
For information on obtaining reprints of this article, please send e-mail to:
reprints@ieee.org, and reference the Digital Object Identifier below.
Digital Object Identifier no. 10.1109/TPDS.2016.2620142

general graph GðV; EÞ is an assignment of colors to vertices
such that any two adjacent vertices receive different colors.
A partial distance-2 coloring of a bipartite graph Gb ¼
ðV1 ; V2 ; EÞ is an assignment of colors to one of the vertex
sets, say V2 , such that any two vertices in V2 that are twoedges away from each other receive different colors. Moreformal definitions of these problems will be given in
Sections 2 and 5, but we remark at this point that distance-1
coloring is the “usual” graph coloring problem.
Standard formulations of the distance-1 and partial distance-2 coloring problems aim at minimizing the number ofcolors used (that is, the number of independent subsets
or color classes) without any requirement on the size of thecolor classes relative to each other. They therefore permit
cases where the color classes can be highly unbalanced. In
fact, by their nature, most practical algorithms for the standard formulations of these graph coloring problems produce highly skewed color classes. This will be undesirable
as the smaller color classes may not provide sufficient workload for parallel efficiency.
In this paper, we deal with the design, implementationand performance evaluation of algorithms for the distance-1
and partial distance-2 coloring problems that also requirethat color classes be balanced in their sizes.
There is a body of work in the graph theory literature on
equitable distance-1 colorings—a formulation in which color
classes are required to be perfectly balanced—but little work
exists on fast, practical, balanced coloring algorithms
and their parallelization on contemporary and emerging

1045-9219 ß 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

platforms. Further, to the best of our knowledge, there exists
no prior work on balanced partial distance-2 coloring. We
seek to address these deficiencies.
The scope and contributions of this paper are as follows:

Algorithms. We investigate a variety of techniques,grouped in two main categories, for achieving balanced coloring in both the distance-1 and partial distance-2 coloring cases. Algorithms in the first category
aim to obtain a balanced coloring in a single attempt(ab initio). Those in the second category begin with an
initial coloring oblivious to balance and use that information to produce a new coloring that is also balanced(guided). We propose three different types of guided
balanced coloring algorithms (each of which could further be specialized to tune for performance) and examine several variants of ab initio approaches.
 Parallelization. We parallelize all of the balanced coloring algorithms we explore targeting two different
architectures: conventional multicore x86 architectures and a specialized many-core platform, Tilera
TileGx36.
 Application and Evaluation. We demonstrate the impactof balanced distance-1 coloring on community detection—a widely used graph application. Our results
show that using balanced coloring for this application
could yield significant performance improvements
while preserving quality. In addition, we present athorough evaluation of the different heuristics basedon their balancing efficacy and performance.
A preliminary version of this paper that focused only on
distance-1 coloring has appeared in [1]. The remainder of thepaper is organized as follows. We provide background andmotivate our work in Section 2. We describe the sequential
versions of the various algorithms we explore for balanced
distance-1 coloring in Section 3 and discuss how they areparallelized in Section 4. We discuss how the algorithms
developed for distance-1 coloring are modified to handle thepartial distance-2 coloring case in Section 5. We review essential features of the platforms for which the implementations
are targeted in Section 6. We present and discuss experimental results in Section 7. We conclude in Section 8.

2

BACKGROUND

2.1 Basics of Balanced Distance-1 Coloring
Given a general graph G ¼ ðV; EÞ, a distance-1 coloring of G is
an assignment of colors to vertices such that any two adjacentvertices (which are at distance 1 from each other) are assigned
different colors. This is the “usual” coloring problem, andhenceforth, for brevity, we will drop the qualifier “distance1” unless we need to distinguish it from distance-2 coloring.
A coloring is said to be equitable if the sizes of any twocolor classes differ by at most one. The concept of equitable
coloring was introduced by Meyer in a 1973 paper [2]. Its
history, however, goes even further back to a conjecture by
Erd€os, a conjecture settled in 1970 by Hajnal and Szemeredi[3] forming their celebrated theorem: a graph with maximal
degree D is equitably k-colorable if k  D þ 1. This bound is
sharp. One of the directions of early theoretical research inthis field had been to obtain better upper bounds than D þ 1
for special graph classes [4].

1241

The equitable coloring problem asks for an equitable
k-coloring with the smallest possible k. This problem is NPhard, as the classical coloring problem can be triviallyreduced to it. Polynomial time equitable coloring algorithms
are known for various special classes of graphs, including
trees [5], r-partite graphs [6], line graphs [6], and planargraphs [7]. Furmanczyk [8] provides a survey of work onequitable colorings until the early 2000’s.
In equitable coloring, as stated earlier, the difference insize between any pair of color classes is required to be at
most one. This ideal can for some practical needs be unnecessarily stringent and too costly to attain. In the closely
related heuristic variant we refer to here as balanced coloring,
the restriction is relaxed; the difference in color class size
instead is allowed to be at most a “small” number greaterthan 1. One formal way to state this is to say that each color
class is bounded by some parameter l. Bodleander andFomin [10] study this problem and show that it, as well as
the equitable coloring problem itself, can be solved in polynomial time for graphs with bounded treewidth. In thiswork, we take a less formal route and think of balanced
coloring without fixing a parameter l. More specifically,
given a graph GðV; EÞ, the problem is to compute a distance-1 coloring such that each color class receives approximately jVC j vertices, where C is the number of colors used.
Equitable coloring and balanced coloring (in the sensejust mentioned) find important applications in various
areas. Examples include load-balanced partitioning fordomain decomposition methods [11], parallel sparse matrix
computations on irregular grids [12], and various types ofscheduling and timetabling problems [13]. Tucker in a 1973
paper [14] discusses how equitable coloring theory has beenused in helping out Operations Researchers at the Urban
Science Department at Stony Brook, who were faced with achallenging routing problem that sought to optimize scheduling of garbage collecting trucks in the city.
Balanced coloring in the context of parallel scientificcomputing was studied by Gjertsen, Jones and Plassmann[15], where they developed a balanced, distributed memory
parallel coloring heuristic building on their own earlier
work on parallel graph coloring that was unconcerned withbalancing color classes [16]. Their balancing heuristic draws
ideas from approximation algorithms for the bin packing
problem [17] and a coloring work in [18].
The work in [15] has connections to that in this paper, but it
differs both in terms context and approach. In particular, thecontext in [15] is a distributed memory setting in which thevertex set of a graph is already partitioned among processors.
Further, the authors assume that the partitioning is a good
one in the sense that each processor is assigned nearly thesame number of vertices. Based on an initial coloring of
the partitioned graph, the authors then run a balancing heuristic that respects the vertex partitioning (avoids relocation ofvertices to processors). In contrast, in this work, we do notassume any a priori partitioning of the vertex set. In fact, theassignment of vertices to processors (or threads) is expected
to be done after the balanced coloring is achieved, which is anadvantage. In terms of approach, the work in [15] focuses on
one class of algorithms: given an initial coloring, how can balancing be achieved without increasing the number of colors
used? In contrast, here we consider a wider variety of algorithms, provide implementations on modern day multi-core

1242IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,

VOL. 28,

NO. 5, MAY 2017

Fig. 1. a) The size distribution of the color classes obtained by the Greedy First Fit heuristic for distance-1 coloring on an input graph (uk-2002)
obtained through a web crawl of the .uk domain. b) The evolution of modularity gain across the iterations of a parallel implementation of the Louvain
method [19]. Four curves are depicted there. Two of the curves correspond to results obtained when coloring (skewed and balanced) is used in theparallel implementation, the third corresponds to results when coloring is not used, and the fourth corresponds to results on a serial implementation.

and manycore platforms, and experimentally evaluate theirperformance as well as the trade-offs they offer.

2.2 A Foundational Scheme
For the standard distance-1 graph coloring problem, despite
its NP-hardness, the greedy scheme outlined in Algorithm 1
is often found quite effective in practice, since the scheme
gives usable solutions and can be implemented to run in linear-time for graphs that arise in practice.
Algorithm 1. Greedy
Greedy (G ¼ ðV; EÞ)for each v 2 V in some order dofor each w adjacent to v do
Mark the color of w as forbidden to v
Assign v a color not marked as forbidden to v

The scheme Greedy can be specialized in a variety ofways depending on a) the technique used to determine theorder in which the vertices are processed and b) the strategy
used to pick a color (among a set of permissible colors) for a
vertex at a given step.
A common strategy with regards to (a) is to rank the vertices in a non-ascending order of “degree”, where degree
is suitably defined (e.g., as the number of neighbors, or thenumber of already colored neighbors, or the number of differently colored neighbors). The intuition is to treat vertices
that are likely to be harder to color, earlier in the process.
A common strategy used with regards to (b) is to pick thesmallest (we assume colors are positive integers) permissible
color for a vertex in each step. This strategy is sometimes
referred to as First Fit (FF), since, considering the analogy
to the bin packing problem mentioned earlier, it strives toplace the vertex in the first bin (color) it could be placed in.
The rationale behind choosing the smallest color is that one
can then guarantee that the number of colors used by thescheme is bounded from above by D þ 1 (where D is the maximum degree in the graph) regardless of the order in which
the vertices are processed and by K þ 1 (where K is the corenumber of the graph) if the degeneracy order of the vertices
is used. A degeneracy order, also known as Smallest Lastordering, can be obtained in linear-time.

The FF strategy is attractive for the bounds on the number of colors it assures. The color classes it produces, however, could be highly skewed, with a vast majority
containing significantly smaller number of vertices—anexpected result out of selecting the first available bin forevery vertex. The chart in Fig. 1a confirms this expectation
on a real world graph. Small-sized color classes can become
scalability bottlenecks in an end-application, where typically the color classes are processed in different steps (tohonor dependencies) and the smaller classes limit thedegree of parallelism during those steps.

2.3 Community Detection: A Motivating Application
Overcoming such scalability bottlenecks is in part what
motivated our current work. We sought to investigate algorithms for achieving balanced coloring and their effective
use in parallel computing applications. As a case-study, we
consider balanced coloring in the context of parallel community detection, based on an implementation called “Grappolo”
that we developed for multi-core and manycore architectures[19], [20]. The parallel implementation is based on the sequential Louvain heuristic [21]. The Louvain method, which is oneof the most widely used community detection algorithms,
uses the modularity function [22] as the objective function to
be maximized.
Grappolo consists of multiple phases, each in turn containing multiple iterations. Within each phase, the algorithm starts with every vertex placed in a community of its
own. A series of iterations is then performed until a convergence criterion is met. Within each iteration, all vertices arescanned in parallel. For each vertex, a greedy decision ismade as to whether the vertex should migrate to a different
community (selected from one of its neighbors) or should
stay in its current community, so as to maximize the net
modularity gain. This approach places multiple constraints
on concurrent processing of neighboring vertices. In previous work, we had extensively explored the use of graph coloring in effectively addressing the challenges associatedwith these constraints [19]. Our findings showed that theuse of coloring significantly accelerates convergence and,for many input cases, also improves the quality of communities output (as measured by the modularity function).

LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

1243

TABLE 1A Comprehensive List of Balancing Strategies for Distance-1 Coloring Presented and Studied in This Paper
Strategy

Category

Description

Greedy-LU
Greedy-Random
Shuffling-unscheduled

ab initio
ab initio
guidedShuffling-scheduled

guidedRecoloring

guidedRun Algorithm 1 with LU color choice among permissible colors.
Run Algorithm 1 with Random color choice among permissible colors.
Run Algorithm 1 with FF color choice strategy. Based on the obtained coloring identify
over-full and under-full bins. Move select vertices from over-full to under-full bins withoutchanging the number of color classes. Further specializations include Vertex-centric FF(VFF) and Color-centric LU (CLU).
Run Algorithm 1 with FF color choice strategy. Based on the obtained coloring identify overfull and under-full bins. Move select vertices from over-full to under-full bins in a scheduledmanner without changing the number of color classes.
Run Algorithm 1 with FF color choice strategy. Let the number of colors used be C. Let
g ¼ jV j=C. Construct an ordered set of vertices W ¼ fV ðCÞ; V ðC  1Þ; . . . ; V ð1Þg, where V ðiÞ
denotes the set of vertices having the color i. Re-color vertices in W in that order using
Algorithm 1 such that in each step, a vertex v is assigned the smallest permissible color ksuch that the size of bin k is less than g.

The input graph is denoted by G ¼ ðV; EÞ. The same set of strategies are also extended to obtain a balanced partial distance-2 coloring on bipartite graph inputs.

However, since the color classes are processed in parallel
one at a time, large skews in color class sizes (as shown in
Fig. 1a) can reduce overall scalability, particularly while
processing the smaller color classes. The purpose of balancing the color classes is thus to improve thread utilization for
those smaller color classes, while ensuring that the overall
output quality of the solution (modularity) is maintained.
The chart in Fig. 1b demonstrates this purpose. The chartshows that balanced coloring matches skewed coloring in
its impact on community detection both in terms of convergence rate (i.e., number of iterations taken to complete) andin terms of output quality (final modularity), while offering
the added advantage of improved thread utilization withinevery iteration, since the color classes are balanced.

3

ALGORITHMS FOR BALANCED DISTANCE-1
COLORING

In this section, we present multiple heuristics to compute abalanced distance-1 coloring of an input graph, as summarized in Table 1.
We explore two categories of approaches. Approaches in
the first category aim at obtaining a balanced coloring in asingle attempt. We refer to these as “ab initio” approaches.
Those in the second category follow a two-step procedure,
where an initial coloring obtained using a balance-oblivious
procedure, is subsequently balanced in the second step. We
refer to these approaches as “guided” (to signify that they
are guided by an initial coloring).

3.1 Ab initio Balancing Strategies
Within the ab initio category, we consider two well-known
variants of the Greedy scheme outlined in Algorithm 1 thatdiffer in how the choice of color to be assigned to a vertex ineach step is done. Both variants seek to achieve balanced
coloring by virtue of the color choice strategy:

Greedy-LU: A vertex is assigned the least used color
among all currently available permissible colors. If
no permissible color exists, then a new color is created and assigned to the vertex.
Greedy-Random: A vertex is assigned a color picked at
random from the set of permissible colors. The

particular Greedy-Random variant we consider
assumes the existence of a reasonable bound B on
the number of colors needed. One such easy-to-compute bound is B ¼ D þ 1. Then, a vertex v is assigned
a randomly chosen color from the set of permissible
colors P ðvÞ  f1; 2; . . . ; Bg.
Manne and Boman analyze balanced greedy coloring
using the strategies LU and Random in the context of sparse
random graphs [23].

3.2 Guided Balancing Strategies
In the guided category, we study different approaches for
obtaining a balanced coloring given an initial coloring. We
note here that all of the proposed guided approaches canbe applied to an initial coloring produced by an arbitrarycoloring method. However, a subset of these approaches isdesigned to exploit certain properties of an initial coloringproduced by the Greedy coloring scheme that uses the FFcolor choice strategy (henceforth abbreviated as Greedy-FF).
Given an input graph G ¼ ðV; EÞ, let the number of colors
used by the initial coloring step be C. In all our guided strategies, we make use of the quantity g ¼ jV j=C to guide ourmethods. Note that in a strictly balanced setting, the size ofeach color class would be roughly g. Consequently, we referto a color class of size greater than g as an over-full bin, and acolor class of size less than g as an under-full bin. (We use
the terms bin and color class interchangeably throughout the
paper.)
Broadly, we classify our guided strategies into two types.
In the first type, a subset of vertices from each over-full
bin is moved to under-full bins so that a better balance isattained. Since this is achieved without increasing the number of color classes, we refer to this type of methods Shuffling-based. In the second type, instead of enforcing that the
number of color classes remains unchanged, all vertices arecolored afresh, this time with a balance constraint imposed.
We call this strategy Recoloring.
The Shuffling methods in turn comprise two specializations: unscheduled and scheduled moves. The motivation forthis distinction comes from parallel performance needs thatwill be explained in Section 4.

1244IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,The Recoloring method takes advantage of an interesting
property of the Greedy-FF scheme. Suppose a coloring of agraph G ¼ ðV; EÞ is obtained using Greedy-FF in some vertex order. Let the number of colors used be C. Now suppose
the vertices of G are ordered such that vertices in the samecolor class are listed consecutively. Then re-applying
Greedy-FF using this new ordering will produce a new coloring of G using C or fewer colors. Culberson [24] applied
this idea iteratively in his method called Iterated Greedy(IG) to successively reduce the number of colors and draw
the number as close to the optimal as possible. There is adegree of freedom in how the color classes themselves could
be ordered for IG to be successful. One of the better strategies is to list the color classes in reverse order—i.e., beginning from the vertices of the highest color index.
We build on this property to devise our Recoloring
method for balancing. A key extension in our case is that we
maintain the sizes of bins during the new coloring and use
those to impose balance. In particular, in each step of the recoloring, a vertex is assigned the smallest permissible color
k such that the size of the bin k is less than g.

4

PARALLEL ALGORITHMS

We parallelized all of the guided balanced coloring algorithms presented in Section 3 for the shared memory model.
For each heuristic we developed two OpenMP-based implementations—one for conventional multicores and anotherfor the Tilera manycore platform. To obtain the initial coloring we used a parallel implementation available for GreedyFF from a previous effort [25]. In this section, we describe
the parallel algorithms underlying the implementations of
the balancing schemes.
To parallelize our shuffling-based approaches, we considered two ways of moving a vertex from an over-full bin
to an under-full bin. The first type of move is “unscheduled”.
Here, the choice of the target bin for a given vertex isdecided dynamically (using either the FF or LU strategy)
based on the state of the color bins—encompassing bothsize and composition. This approach strives to achieve agood balance, if possible; as a trade-off, however, it entails
the cost needed to keep each dynamic state up-to-date.
More specifically, concurrent updates to the sizes of thesame bin need to be synchronized.
To mitigate the cost of updates, we explored an alternative that we call “scheduled” moves, where the target bin fora vertex in an over-full bin is statically determined using aheuristic, and the check to verify if such a move is permissible is deferred until the move is actually attempted.
If a move attempt creates a “conflict”, which is possible if
a neighboring vertex is already in the same target bin, nofurther attempt is made and the vertex remains in its original
bin. The advantage of this approach is the expected
improvement in parallel performance, as no atomic operation or lock is needed to update bin sizes. However, thisapproach could potentially leave bins unbalanced.

4.1 Parallelization using Unscheduled Moves
For obtaining guided balanced coloring using unscheduled
moves, we considered two parallelization schemes. In thevertex-centric schemes, the loop-parallelization is around a
set of vertices, and vertices from different color classes are

VOL. 28,

NO. 5, MAY 2017

allowed to be processed concurrently. In the color-centric
schemes, vertices processed concurrently must belong to
the same color class. In both schemes, only vertices in overfull bins are considered for color reassignment. Furthermore, once an over-full bin i reaches balance (i.e., size
reaches g) at any point in the execution, then vertices fromthat bin are no longer considered for color reassignment.
Hence, these schemes represent partial recoloring methods
that proceed until either a balance is achieved or a balance
is no longer possible (i.e., there exist no more permissible
moves from any of the remaining over-full bins).
Vertex-Centric Parallelization Scheme. Processing vertices
from possibly different color classes exposes maximum concurrency. However, it could also cause conflicts. To handle
such conflicts in parallel we adopt the Speculation-and-Iteration framework described in [25]. The basic idea in thisframework is to maximize concurrency by temporarily tolerating inconsistencies. Consider a simple loop-parallelization over the set of vertices in the Greedy scheme (using FF
or LU) outlined in Algorithm 1. Such a parallelization will
not preclude the possibility of a pair of adjacent vertices
from receiving the same color. In our adoption of the speculation-and-iteration framework, once vertices are moved totheir target color classes, the idea is to detect conflicts (inparallel) in a separate phase in the same round and resolve
them in a subsequent round. The algorithm proceeds iteratively in this fashion until all conflicts are resolved.
A template for the vertex-centric parallelization scheme
is presented in Algorithm 2. This algorithm corresponds tothe Vertex-centric First Fit (VFF) balancing method. It shouldbe easy to see that the same algorithm can be easily adapted
to the Vertex-centric Least Used (VLU) balancing methodwith a change to the target bin (k) selection criterion.

Algorithm 2. Vertex-Centric Parallel Scheme for Balanced
Coloring (using FF)
VertexParallelGuidedBalancing(G ¼ ðV; EÞ)
Obtain an initial coloring of G
Let U be the set of vertices from over-full bins
while U 6¼ 0 do
for v 2 U do in parallel
Let k be the smallest index of an under-full bin that ispermissible"FF
if k exists thenLet jcolor½v
color½v
kUpdate size of bins k and j"synch. stepR;for v 2 U do in parallel"check for conflicts
for w 2 adjðvÞ do
if (color½w ¼ color½v and v > wÞ thenR
R [ fvg
Update size of bin color½v
"synch. stepU
R

Note that the maximum number of conflicts per a vertex
v in the above algorithm can be upper-bounded by
minfdðvÞ; bg, where dðvÞ is the number of vertices adjacent
to v and b is the number of under-full bins. This upperbound is rather weak. In practice, we observed that theclosely related quantity—the actual number of iterations
needed to clear all conflicts—is typically a small constant.

LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

Color-Centric Parallelization Scheme. In the color-centric
scheme for parallelization, we allow only vertices from thesame color class to be processed concurrently. This isachieved by processing one over-full bin at a time and performing the moves departing from that over-full bin in parallel until a balance is achieved or no more move is possible.
This scheme, therefore, avoids conflicts, and the balancing
procedure requires no more than a single pass of the overfull bins. However, the trade-off is in parallel performanceof the balancing procedure, which requires as many parallel
steps as there are number of over-full bins in the initial coloring. Depending on the strategy used to pick an under-fullbin (FF or LU), we refer to this Color-centric parallelization
scheme as either CFF or CLU. A template for the color-centric scheme is shown in Algorithm 3.

Algorithm 3. Color-Centric Parallel Balanced Coloring
ColorParallelGuidedBalancing(G ¼ ðV; EÞ)
Obtain an initial coloring of G
Let Q be the set of over-full bins
for each j 2 Q do
Let V ðjÞ denote the set of vertices with color j
for v 2 V ðjÞ do in parallel
Let k be the smallest index of an under-full bin thatis permissible to v
"FF
if k exists thencolor½v
kUpdate size of bin k; j"synch. step

Initial Coloring. We note here a special property emerging
from the use of Greedy-FF for generating the initial coloring.
Any initial coloring produced by Greedy-FF satisfies the following property: Assume a linear ordering of colors from
1; . . . ; C. If a vertex v is assigned color j, where j > 1, thenit implies that v contains at least one neighbor in each of theprevious colors 1; . . . ; j  1 (otherwise, v would have been
assigned a smaller color). Therefore, if we follow theGreedy-FF initial coloring by another FF-based strategy during the subsequent balancing step (e.g., VFF or CFF), then theclosest permissible bin, say k, we identify through that procedure would also correspond to a color that has a high incidence of edges on the source over-full color bin. Given thatk represents a permissible bin despite its high incidence
makes it intuitively an attractive target for this vertex. On
the other hand, an LU-based strategy (VLU or CLU) operates oblivious to the ordering of the initial colors, and istherefore better suited for scenarios where the initial coloring was generated by schemes other than Greedy-FF.
It is for these reasons that we use the Greedy-FF strategy
for computing an initial coloring in VFF and CFF, while for
VLU and CLU the use of any initial coloring scheme isreasonable.

4.2 Parallelization using Scheduled Moves
To parallelize guided balancing using scheduled moves wetake advantage of both the incidence property (observed
above) and another size-related property of the Greedy-FF
initial coloring: owing to its First Fit strategy, Greedy-FF is
expected to assign more vertices to smaller-indexed color
classes. In other words, color classes are expected to be in
non-increasing order of their sizes as one proceeds from1245

color 1 through color C. This expectation agrees with thesize distributions depicted in Fig. 1.
Our parallel algorithm with scheduled moves is outlinedin Algorithm 4. Intuitively, we identify an arbitrary subset
of surplus vertices from the sequence of over-full bins andmark each of them for assignment to a corresponding
under-full color.1 At this point, no explicit checks are madeto identify conflicts. In the next step, all vertices from theover-full bins that were scheduled for recoloring are processed in parallel to check if any of them conflicts with theassigned target bin. A move is completed only if it generates
no conflicts.

Algorithm 4. Parallel Shuffling using Scheduled Moves
ScheduledBalancing(G ¼ ðV; EÞ)
Obtain an initial coloring of G using Greedy-FF
Let C be the number of colors used, and let g ¼ jV j=C
Let QO be an ordered set of over-full bins in increasing orderof color index
Let QU be an ordered set of under-full bins in decreasingorder of color index
Let L (initially ;) maintain a list of moves from over-full tounder-full bins
for each j 2 QO do
Let V ðjÞ denote fu 2 V j color½u ¼ jg
Select V 0 ðjÞ  V ðjÞ such that jV 0 ðjÞj ¼ jV ðjÞj  g
for each k 2 QU AND V 0 ðjÞ 6¼ ; do
Let Vk0 ðjÞ  V 0 ðjÞ denote vertices that can be moved
to k such that jVk0 ðjÞj þ jV ðkÞj  g
LL [ Vk0 ðjÞ
V 0 ðjÞ
V 0 ðjÞ n Vk0 ðjÞ
for Vk0 ðjÞ 2 L dofor v 2 Vk0 ðjÞ do in parallel
if (k is a permissible color for v) thencolor½v
kThis simple approach requires no synchronization on thebin sizes. However it could leave the bins imbalanced. To
improve the chance of obtaining a better balance, we fill theunder-full bins (set QU in Algorithm 4) in the decreasing orderof color index (we refer to this approach as Scheduled Reverse,
or more simply, Sched-Rev). Attempting to fill the under-fullbins in decreasing order increases the likelihood of color coassignment of vertices—i.e., two vertices being moved fromthe same source over-full bin are likely to co-locate in thesame target under-full bin, thus minimizing the chance of
conflicts. This is a consequence of the aforementioned sizerelated property of the Greedy-FF initial coloring.

4.3 Parallel Recoloring
The parallelization we use for the balancing based on Recoloring is outlined in Algorithm 5. This is similar to the vertex-centric parallel scheme given in Algorithm 2 with themain difference being that we recolor all the vertices fromscratch and that balance is imposed as the recoloring proceeds. In particular, the recoloring approach colors vertices
roughly in the order of vertices as they appear from the
1. This step is performed serially in our current implementation
since it was very quick for most inputs; however, if required, this step
can also be parallelized using parallel prefix (details omitted).

1246

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,

VOL. 28,

NO. 5, MAY 2017

Fig. 2. Illustration of equivalence among structurally orthogonal partition of a matrix A (a), partial distance-2 coloring of the vertices in V2 in bipartite
graph Gb ¼ ðV1 ; V2 ; EÞ of A (b), and distance-1 coloring of the subgraph of the square graph induced by V2 , that is Gb 2 ½V2  (c).

largest color to the smallest color of the initial coloring. The
rationale for this ordering, as mentioned in Section 3.2, isthat the re-coloring procedure would have an opportunity
to use fewer colors, since now the vertices that were“difficult” to color initially are processed earlier. In the process of recoloring, we also strive for the size of each color
class to be as close as possible to the average size of a color
class g obtained from the initial coloring.

Algorithm 5. Parallel Recoloring for Balance
ParallelRecoloring(G ¼ ðV; EÞ)
Obtain an initial coloring of G using Greedy-FF
Let C be the number of colors used, and let g ¼ jV j=C
Let V ðjÞ denote fu 2 V j color½u ¼ jg
Construct an ordered set W ¼ fV ðCÞ; V ðC  1Þ; . . . ; V ð1Þg
Initialize bin½i ¼ 0, for i ¼ 1; . . . ; C
UWwhile U 6¼ ; do"perform a fresh coloringfor v 2 U do in parallel
color½v
smallest permissible color k such thatbin½k  gIncrement bin½k by 1
"synch. stepR;for v 2 U do in parallel
for w 2 adjðvÞ do
if (color½w ¼ color½v and v > wÞ thenR
R [ fvg
UR

4.4 Complexity
With careful choice of data structures, the sequential
Greedy scheme (Algorithm 1) that underlies all of our parallel algorithms, can be implemented such that its runtime isupper-bounded by OðjV j  DÞ, where D is the maximum
degree in the graph. In each of the templates outlined in
Algorithms 2 through 5, the total “additional” work
incurred due to parallelization is no more than the work
involved in Algorithm 1. Furthermore, the number ofrounds required by the iterative variants (Algorithms 2 and5), as argued earlier, is typically a small constant in practice.
Therefore, the net total work in any of our schemes can be
upper-bounded by OðjV j  DÞ.
The above complexity represents a worst-case, where for
instance, multiple vertices with relatively high degrees tend
to occupy the overfull bins in the initial coloring. But suchcases also require a relatively high number of such vertices
in the input, which is less likely to be observed in real world
networks with power-law like degree distributions.

5

PARTIAL DISTANCE-2 COLORING

5.1 Preliminaries
As mentioned in Section 1, besides distance-1 coloring, we
considered in the current work a balanced version ofanother coloring problem, partial distance-2 coloring, that isdefined on a bipartite graph Gb ¼ ðV1 ; V2 ; EÞ. The coloring“rule” here is to assign colors to vertices in one of the vertex
sets, say V2 , such that any pair of vertices vi ; vj from V2 thatshare a common neighbor vc in V1 (that is, ðvc ; vi Þ 2 E andðvc ; vj Þ 2 E) get different colors.2 The objective of the standard version of the problem, as in distance-1 coloring, is touse as few colors as possible. The balanced variant seeks to,in addition, balance the color classes.
The partial distance-2 coloring problem is an importantmodel in computations involving nonsymmetric matrices.
For example, a partitioning of the columns of a nonsymmetric matrix A into groups of structurally orthogonal columns—
a group in which no two columns share nonzero entries inthe same row position—can be modeled by a partial distance-2 coloring of the column vertices V2 of the bipartite
graph Gb ðAÞ ¼ ðV1 ; V2 ; EÞ representing the sparsity structure of the matrix A [26]. Such a model is useful, for example, in an efficient computation of a Jacobian matrix A using
automatic differentiation. Fig. 2 shows a small example that
illustrates how a structurally orthogonal column partitionof a matrix is modeled as as a partial distance-2 coloring of
the bipartite graph.
Fig. 2c illustrates yet another equivalence. In general, apartial distance-2 coloring on the vertex set V2 of a bipartite
graph Gb ¼ ðV1 ; V2 ; EÞ is equivalent to a distance-1 coloringof a certain derived graph—the subgraph of the square graphof Gb induced by the vertex set V2 , which we denote by
Gb 2 ½V2 . For a general graph G ¼ ðV; EÞ, the square graph
G2 ¼ ðV; F Þ is a graph defined on the same vertex set V andwhere the edge set F consists of pairs of vertices that are
distance less than or equal to two edges from each other. In
2. This variant is called “partial” since only one of the two vertex
sets in the bipartite graph is colored. It is called “distance-2” since, inthe vertex set to be colored, any two vertices that are two edges awayfrom each other are required to get different colors. The naming was
first used in [26].

LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

other words, F ¼ E [ E 0 , where E 0 corresponds to pairs ofvertices that are at distance exactly two edges from eachother in G. If the graph under consideration is a bipartite
graph Gb ¼ ðV1 ; V2 ; EÞ, then the square graph Gb 2 ¼ ðV1 ;V2 ; F Þ, which no longer is bipartite, is such that the edge set
can be viewed as having three parts: F ¼ E [ E1 [ E2 ,where E1 corresponds to the “new” edges that run among
vertices in V1 (those that are at distance 2 in Gb ) and E2 corresponds to the edges that run among vertices in V2 (thosethat are at distance 2 in Gb ). The subgraph of Gb 2 inducedby the vertex set V2 could then be written as Gc ¼ ðV2 ; E2 Þ.
In network science literature, the graph Gc is also sometimes
referred to as a “projection” on to the vertex set V2 , and in
the numerical optimization community Gc is also known as
the “column intersection graph” of the associated non symmetric matrix.
The discussion in the paragraph above focused on thecase where the vertex set in the bipartite graph to be coloredis V2 . Entirely analogous discussion and definitions apply if
the vertex set to be colored were V1 instead.
Now if partial distance-2 coloring on the vertex set V2 ofthe bipartite graph Gb ¼ ðV1 ; V2 ; EÞ is equivalent to distance-1 coloring of the intersection graph Gc Gb 2 ½V2 , why
don’t we then simply construct Gc and solve the distance-1
coloring problem on it using algorithms developed for distance-1 coloring, instead of developing algorithms tailoredfor partial distance-2 coloring? As has been argued in [26],there are several reasons for this. First, the partial distance-2
coloring formulation offers greater flexibility. In particular,
the intersection graph necessarily looses structural information contained in the original bipartite graph. For example,
considering the context of an underlying nonsymmetricmatrix, given two column vertices in V2 joined by an edge in
Gc , one cannot determine the row at which the two columns
share nonzero entries. Second, for some structures, theintersection graph Gb 2 ½V2  could turn out to be substantiallydenser (have more edges) than the original graph Gb andhence require more memory. Note that by construction,
each vertex u 2 V1 of GðV1 ; V2 ; EÞ would correspond to a
k-clique in G2b ½V2 , where k is the degree of u. Third, the partial distance-2 coloring formulation avoids the need forbuilding a different data structure than the one used to represent the input graph.

5.2 Algorithms
The greedy scheme for distance-1 coloring outlined in
Algorithm 1 can be easily modified to obtain a solution
for the partial distance-2 coloring problem. The needed
modifications are: (i) the input is a bipartite graph
Gb ¼ ðV1 ; V2 ; EÞ, (ii) the for-loop iterates over v 2 V2 , and(iii) the neighbors of a vertex v are those vertices x thatare connected to v by a path v; w; x of length two edges.
The algorithm modified in this manner is outlined in
Algorithm 6. Let dðV2 Þ denote the average degree of avertex in V2 , and DðV1 Þ denote the maximum degree of avertex in V1 . Consequently, the runtime complexity of
the algorithm is as follows [26]: OðjV2 jdðV2 ÞDðV1 ÞÞ, whichis same as OðjEjDðV1 ÞÞ.
We note here that it is possible to develop a faster
greedy algorithm by exploiting the bipartite structure of1247

the graph and by relaxing the constraint on the maximum number of colors used. One such approach is tolinearly scan the vertices in V1 and assign different colors
to all its neighbors in V2 , while using colors in a greedy
first-fit fashion. Such an approach, while improving theruntime (OðjEjÞ), could potentially use more colors relative to Algorithm 6. Furthermore, parallelization of suchan approach may necessitate multiple iterations toresolve potential conflicts introduced during the parallel
coloring procedure. For these reasons, we use Algorithm 6 as the basis for the balanced variants developed
and results presented in this paper.

Algorithm 6. Greedy Partial Distance-2 Coloring
GreedyPD2C(Gb ¼ ðV1 ; V2 ; EÞ)for each v 2 V2 in some order dofor each w adjacent to v dofor each x adjacent w do
Mark the color of x as forbidden to v
Assign v a color not marked as forbidden

The parallelization strategies discussed in Section 4
focused on distance-1 coloring. The corresponding algorithms for partial distance-2 coloring follow the same methodology, with the modifications outlined earlier in thisparagraph. We therefore omit detailed presentation of algorithms for partial distance-2 coloring.

5.3 Another Example of an Application
Parallel implementation of the coordinate descent algorithm isanother example of an application in which partial distance-2 coloring is useful. Let us review the coordinate
descent algorithm briefly to show how partial distance-2
coloring is relevant there. In the coordinate descent algorithm, the rows of matrix A correspond to samples and thecolumns correspond to features. The corresponding dimensions are often denoted by n (samples) and k (features). Formulated in a generic fashion, the coordinate descent (CD)algorithm consists of four steps that are performed iteratively until convergence is reached:
Step (1) Select a set of coordinates J
Step (2) Propose increment dj , j 2 J
Step (3) Accept some subset J 0  J of the proposals
Step (4) Update weight wj for all j 2 J 0 .
The approach taken in the Select step determines thetype of the CD Algorithm. For example in cyclic or stochastic CD the selection targets a singleton, whereas ingreedy CD one selects a set—and in the extreme case(fully greedy), the entire set of features is selected.
Clearly, greedy is better suited for parallel CD. In a parallel formulation of CD, the Propose and Update steps
need to be performed concurrently. In order to performthe Update step with maximal exploitation of parallelism, one needs to identify groups of structurally orthogonal columns (features), since then matrix entries in all
the columns in a group can be updated safely concurrently. This identification in turn is what is modeledusing partial distance-2 coloring (on the column-vertices)of the bipartite graph representing the sparsity structureof the matrix A.

1248

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,TABLE 2
Input Statistics for the Graphs used in
Our Distance-1 Coloring Study
Degree stats

Input

Num.

Num.

graph

vertices (n)edges (m)

max.

avg.

random2
CNR
coPapersDBLP
rgg11-22
ChannelMG2
NLPKKT200
uk-2002
Europe-osm

100,000
325,557
540,486
4,194,304
4,802,000
11,005,829
16,240,000
18,520,486
50,912,018

9,994,356
2,738,970
15,245,729
27,306,228
42,681,372
674,142,381
215,992,816
261,787,258
54,054,660

263
18,236
3,299
23
18
5,466
27
194,95513

199.89
16.28
56.41
13.02
17.77
122.50
26.60
28.27
2.12

6

IMPLEMENTATION ON THE TILERA PLATFORM

We have ported our parallel balanced coloring algorithms to
the Tilera manycore platform. The Tilera TileGX36 system
implements a manycore processor based on a two-dimensional mesh topology. Each core (called a “tile” in Tilera’s
terminology), consists of a three-way VLIW processing unit,a private 32 KB, two-way set associative L1 data cache, aprivate 32 KB, direct-mapped instruction cache and a 256
KB, eight-way set associative unified L2 cache. The cacheline granularity is 64 bytes across all three caches. Each tile
is connected via multiple links to several networks-on-chip(NOCs) in a 2D mesh configuration. (These NOCs include
one for coherence traffic, a user-programmable message
passing NOC, and a dedicated I/O NOC.)
Tilera’s caching policies are the salient features that we
exploit to optimize this application. For each individual
memory page, the system can set the home tile of its data inthe cache subsystem. There are two principal modes for setting the home tile of a memory page: homed (a particular tileis the home for the whole page) and hashed (individual
cache lines on the page are distributed in a round-robinmanner to the L2 caches of all tile).
For the balanced coloring algorithms and the community
detection application we use a heap manager with a backing
store of homed huge pages (16 MB/page) for all thread private data. The global shared data structures (Compressed
Sparse Row Representation of the graph, arrays of colors
and bin sizes) are allocated on default-sized pages (64 KB/

VOL. 28,

NO. 5, MAY 2017page) using the hashed policy. Previous experience withbasic coloring and community detection on Tilera [20] has
shown this configuration to be the most performant one forall input data sets. The OpenMP threads created by theapplication are pinned to contiguous sets of cores on the
manycore mesh architecture in order to avoid costly thread
migration and subsequent cache misses.

7

EXPERIMENTAL RESULTS

7.1 Experimental Setup
Test Platforms. We used two platforms for testing: the manycore Tilera TileGX36 presented in Section 6, and an x86
AMD Interlagos platform.
The TileGX36 platform is equipped with 32 GB of DDR3
memory separated into two 16 GB banks, with the coresrunning at 1.2 GHz. The TileGX36 runs a custom version ofLinux adapted for Tilera’s hardware. The compiler and runtime environment are adapted from GCC 4.8.2 and retargeted for the TileGX’s 64-bit VLIW cores. The community
detection code has been parallelized using OpenMP and
Tilera-specific extensions for memory management, synchronization and atomic operations.
The AMD multi-core platform consists of a dual-socket
Interlagos processor with 64 GB of memory. Each sockethas 16 cores running at 2.1 GHz. Each pair of cores isgrouped into a module sharing a single floating-point functional units and separate integer functional units. Each corecontains 16 KB of L1 cache, while each module shares 2 MBof L2 cache. Four modules share 8 MB of L3 cache. Eachsocket contains eight modules on our system.
Test Inputs. The test inputs used in the different experiments on distance-1 coloring are summarized in Table 2.
These inputs were all downloaded from the University of
Florida sparse matrix collection [27], with the following
exceptions: MG2 is a custom-built biological network
obtained from protein sequences of a metagenomics data
set [28]; rgg11  22 represents a random geometricgraph [29] that was generated using the generator describedin [30]; and random2 was generated using a simple randomfunction that applies a probability of edge between any pairof vertices. These inputs were chosen to encompass a variety in graph sizes and color class properties such as thenumber of colors and color size distribution (Table 3).

TABLE 3
Quality of Balance Obtained by the Different Heuristics on Different Inputs
Input
graph
random2
CNR
coPapersDBLP
rgg11-22
ChannelMG2
NLPKKT200
uk-2002
Europe-osm

Init. coloring
Greedy-FF
37.17%
587.73%342.41%129.03%128.99%1,272.31%
99.88%
1,885.15%
126.87%

(52)
(85)
(336)
(15)
(12)
(2,143)
(4)
(943)
(5)

Ab initio schemes

Guided schemes
VFF

CLU

Sched-Rev

0.08%
0.03%
0.69%
0.00%
0.00%
0.38%
0.00%
0.08%
0.00%

0.09%
0.04%
0.15%
0.00%
7.16%
0.21%
17.65%
0.01%
0.00%

26.21%
16.44%
12.01%
14.69%
7.55%
9.57%
7.95%
4.88%
6.70%

Recoloring
22.74%
13.81%
10.17%
26.66%
35.75%
25.34%
72.13%
3.53%
39.90%

(57)
(88)
(340)
(15)
(14)
(2335)
(6)
(945)
(6)

Greedy-LU
9.10%
12.03%
0.11%
4.29%
4.84%
18.09%
0.00%
2.94%
0.00%

(82)
(211)
(337)
(17)
(16)
(2169)(23)(1010)(7)

Greedy-Random
21.04%
24.29%
23.15%
38.93%
20.05%
94.37%
1.64%
28.34%
12.07%

(73)
(209)
(338)
(16)
(17)
(2172)(23)(1018)(6)

Entries in each cell show the Relative Standard Deviation (in percent) of color class sizes obtained by a given heuristic (the lower the values, the better the balance). The guided schemes VFF and CLU produce the same number of colors as the initial coloring scheme (Greedy-FF). The number of colors produced by
Greedy-FF, Recoloring and the two ab initio schemes is provided in parenthesis (next to their respective RSD values).

LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

1249

Fig. 3. Distance-1 coloring: Distribution of color class sizes produced by the different balanced coloring schemes (horizontal axis corresponds to colors (bins) and vertical axis to sizes of color classes). Recall that smaller color class sizes correspond to reduced parallelism in the end-application,
while higher number of colors corresponds to increased number of parallel steps within the application. For Channel and random2, color class sizes
from all balancing schemes are shown. For NLPKKT200 and CNR, color class sizes only from the balancing schemes that produce same or comparable number of colors to the Greedy-FF scheme are shown.

All results pertaining to distance-1 coloring are presented
in Section 7.2 through Section 7.4 The test inputs and resultson partial distance-2 coloring are presented in Section 7.5. The
extensions to balanced coloring are presented in Section 7.6.

7.2 Balance Quality Assessment
In this section, we compare the quality of balance in thecolor class sizes produced by the different balancing
schemes proposed in the paper. (Please refer to Table 1 foran overview of all the schemes.) To measure balance, we
use the Relative Standard Deviation of the color class sizes(expressed in percent), which is the ratio of the standard
deviation to the mean color size. The closer this value is tozero the better is the balance. For the schemes {Recoloring,
Greedy-LU and Greedy-Random} we also compared thenumber of colors they produce to the number of colors produced by the Greedy-FF scheme (initial coloring).
Table 3 shows the results of our quality assessment. First,
we observe the very large skews in the color sizes producedby the Greedy-FF scheme (which was the primary motivation behind this work). With respect to balancing, we
observe that schemes VFF and CLU generally outperform
all other schemes in either category (guided or ab initio). We
note here that if the initial coloring was generated by ascheme other than Greedy-FF, then CLU is expected to outperform VFF. The Sched-Rev scheme was also effective in
reducing the skew although the degree of balance achieved
was lower than VFF and CLU—as can be expected due toits scheduled strategy. One way to improve the performance of the scheduled strategy is to iterate the procedure a
constant number of times; however the tradeoff is that it
would increase run-time. In fact, we evaluate this tradeoff
in the context of partial distance-2 coloring (see Section 7.5).
Among the schemes that do not guarantee the same number of colors as Greedy-FF (viz. Recoloring, Greedy-LU and
Greedy-Random), we observed consistently that all those
three schemes produced more colors than the Greedy-FF
scheme. However, the number of colors produced by Recoloring was generally close to the number of colors produced by
Greedy-FF and other guided schemes (VFF, CLU), and thebalancing obtained was comparable to the Sched-Rev scheme.
On the other hand, Greedy-LU and Greedy-Random produced significantly higher number of colors making them lessdesirable from the end-application perspective.
As described in Section 4.3, the main advantage of the
Recoloring scheme is that it processes the vertices with larger
color indices earlier. Since these vertices have higher degreeand consequently harder to color, there is potential benefit inprocessing them earlier in the Recoloring scheme. However,the balancing constraint imposed during the recoloring process coupled with parallel execution which disturbs theintended order of vertex processing explains the less-thanoptimal performance displayed by this scheme.
Fig. 3 illustrates the effect of the different balancing
schemes—it shows the sizes of all the color classes produced by the different balancing schemes.

1250

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,

VOL. 28,

NO. 5, MAY 2017

Fig. 4. Recoloring: The figure illustrates the impact of different bounds on bin sizes for the recoloring scheme (Algorithm 5). The default recoloring
scheme which uses t ¼ 0:0 (identifed in the chart by the “0.0” label) fixes the average size for each bin based on the numbers from the initial (unbalanced) coloring scheme. The average size is then varied from 10, 20, and 30 percent (identified by labels “0.1”, “0.2” and “0.3” respectively), which
results in a smaller number of colors used and possibly a higher imbalance in bin sizes than the default recoloring scheme. The percentages inside
paranthesis against each t setting indicates the imbalance, measured by the Relative Standard Deviation of the resulting color class sizes.

Looking Further into the Recoloring Scheme. For the Recoloring scheme, by allowing some of the color classes to slightly
exceed the average color class size (g), it is possible toachieve a reduction in the number of colors used comparedto the baseline version of Recoloring (Algorithm 5). However, the balancing quality may not necessarily be maintained. We empirically investigated this tradeoff between
the number of colors and balancing quality. In particular,
we modified Algorithm 5 such that the line bin½k  g is
replaced by bin½k  g  ð1 þ tÞ, where t is a small fraction
indicating how much offset from g is “tolerated”. Fig. 4
shows results for four values of t (0, 0.1, 0.2 and 0.3) on two
test inputs. The results suggest that the nonzero values for t
help reduce the number of colors used. However, as
expected, the balancing quality degrades with increase in t.

7.3 Performance Evaluation
The balancing schemes were also compared against one
another for their parallel performance. We tested both our
Tilera and x86 implementations on a range of inputs andthread counts. Tables 4 and 5 show the run-times taken by
the VFF balancing scheme. (We select VFF because it was
one of the schemes that produced the best balancing results(as was discussed in Section 7.2).) The corresponding
speedup charts are shown in Fig. 5.
The results show that the scaling in Tilera manycore issignificantly superior to the scaling results in x86. For
instance, a top speedup of 13 was observed on 16 Tilera
cores. The improved scalability delivered by the Tilera
TABLE 4
Parallel Run-Time (in Seconds) of the VFF Scheme on Different
Number of Cores of the Tilera Platform

manycore platform can be largely attributed to a scalable
on-chip network interconnect, which reduces the costs ofsynchronization and latency for irregular memory accesses.
On the other hand, we found synchronization overhead tobe a significant factor impacting the parallel performanceon the x86 architecture. We confirmed this by comparing
the run-times between the VFF (that uses atomic operations
to update bin sizes) and Sched-Rev (that does not). On thex86 architecture, we consistently observed Sched-Rev to be
8 or more faster than VFF on all inputs tested (data notshown). The corresponding performance gain on the Tilera
platform was a more modest 2 (Table 6).
The speedup trends observed on both architectures also
show the impact of the number of initial colors on parallel
performance. As shown in Figs. 5a and 5b, the speedups
obtained on MG2 (2 K colors) and uk-2002 (943 colors) aresuperior than on other inputs. Intuitively, fewer colors
imply a higher probability for concurrent bin size updates.
From the parallel runtimes shown in Tables 4 and 5, it canbe observed that, on a per-core basis, the Tilera platform is generally slower than the x86 system. The main reason is the relatively modest frequency and instruction level parallelism(ILP) of the Tilera cores (3 packed operations per VLIW
instruction, statically scheduled by the compiler), in comparison to double the frequency on the x86 system and wider
superscalar instruction scheduling. However, at full systemscale, the runtimes on the Tilera platform begin to becomecomparable to the runtimes on the x86 platform. ThisTABLE 5
Parallel Run-Times (in Seconds) of the VFF Scheme on
Different Number of Cores of the AMD x86 Platform
Number of threads

Input
graph

1

2

4

8

16

32

Channel 7.55
4.57
3.37
2.59 2.23 2.06 2.13
uk-2002 163.22 84.68 45.59 26.32 16.87 12.11 11.66
MG2
460.22 254.66 154.16 85.97 54.56 34.95 33.29

CNR
Channeluk-2002
Europe
MG2

0.15
0.79
35.60
11.78
70.67

0.17
1.79
23.30
15.98
44.14

0.15
1.77
14.03
20.55
24.00

0.15
2.27
10.31
19.90
14.84

0.15
1.59
9.49
18.97
10.76

0.14
1.70
8.74
16.96
10.69

Times shown are only for the balancing procedure (i.e., initial coloring time is
not included).

Times shown are only for the balancing procedure (i.e., initial coloring time is
not included).

Input
graph

Number of threads
1

2

4

8

16

32

36

LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

1251

Fig. 5. (a, b) Speedup obtained by our Tilera manycore and x86 multi-core implementations of the VFF balancing scheme. Speedups are relative to
one thread executions on both systems. (c) Application study: Evolution of modularity values within the first phase of a parallel community detection
implementation (Grappolo) on uk-2002, performed with the use of VFF balanced coloring. The chart also shows the corresponding modularity curves
for the runs made without balanced coloring and the best performing serial implementation [21].

observation, coupled with the observation that the Tilera platform exhibited a better scalability than x86, (compare Figs. 5aversus 5b), indicates that the Tilera platform, on larger systemsizes, has the potential to make up for the difference withrespect to x86 and even surpass its absolute performance.
In Table 6, we compare the run-times of three of the mostcompetitive balancing schemes {VFF, Sched-Rev and Recoloring} on the Tilera manycore platform. As expected the
Sched-Rev scheme outperforms the other two schemes.
More specifically, we observed Sched-Rev to be 2 fasterthan VFF.3 Considering the fact that Sched-Rev also performed appreciably well in terms of balance quality (Section
7.2), we conclude that it provides a reasonable trade-off
between quality and performance among the different balancing schemes presented in this paper.
Table 7 compares the runtime performance between aguided scheme (VFF) and an ab initio scheme (Greedy-LU).
As was shown earlier in Table 3, the VFF and Greedy-LU
schemes represent one of the top balancing schemes in theirrespective categories (guided and ab initio). Since the guided
schemes require an initial coloring, we include that runtime
as well in the Table 7. The results confirm the runtime
advantage expected for ab initio schemes as they compute abalanced coloring directly, without requiring an initial coloring. However, in most cases, the total runtime for guided
schemes (initial coloring + VFF balancing) is comparable tothe ab initio runtimes, while in general delivering a betterbalancing quality (Table 3).

7.4 Impact on the Community Detection Application
To evaluate the effectiveness of the proposed balanced coloring schemes in a real world application, we studied theparallel community detection code, Grappolo, described in
Section 2.3. Since VFF was one of the leading schemes forbalance quality, we used VFF as our default balancing
scheme on the Tilera platform. We ran Grappolo in twomodes: i) using the original skewed coloring, and ii) using
the balanced coloring produced by VFF.
Table 8 shows the results of our evaluation in the context
of community detection using Grappolo. In this table, we
3. This performance improvement was even more pronounced in
x86 architecture as noted earlier.

compare both end-to-end performance (run-time) and output quality (modularity). We note here that the our current
implementation of Grappolo is configured to use coloring
only during the first phase of its algorithm. However, thealgorithm itself is multi-phase and configuring to use coloring in subsequent phases is one of our planned future extensions. However, for this paper, we used coloring only forthe first phase, and therefore, the benefits of balanced coloring observed in Table 8 are understated.
From the table, we can observe the following: The overhead introduced in balancing is compensated by the runtime gains achieved in the community detection. This istrue for three of the five inputs tested—for instance, in thecase of MG2, balancing yields a total end-to-end run-timesavings of 44.11 percent. Note that this is for a single execution of the community detection code. In practice, a user
may run multiple instances of community detection under
different parametric settings (while the coloring is a onetime preprocessing task). The CNR input is the smallest in
the number of vertices and edges that we processed and thegains from parallelism (with or without balancing) is insignificant. As for Europe-osm, the first phase only consumed
6 percent of the total run-time and therefore the benefits ofbalanced coloring are not directly evident from Table 8.
The results in Table 8 also demonstrate the ability of the VFF
balanced scheme to preserve quality of output (in terms ofmodularity). In fact, we observed that introducing balancing
has a positive impact on the progression of modularlity in thefirst phase, as illustrated in Fig. 5c—which is a consequence ofthe revised ordering of vertices due to balanced coloring.

7.5 Results on Partial Distance-2 Coloring
Our work on partial distance-2 coloring is partly motivatedby its application in the parallelization of the stochastic
TABLE 6
Parallel Run-Times (in Seconds) of the Three Balancing
Schemes {VFF, Sched-Rev and Recoloring} on 16 Tilera Cores
Input graph

VFF

Sched-Rev

Recoloring

Channeluk-2002
MG2

2.23
16.87
54.56

2.19
8.71
27.70

3.28
36.97
185.19

1252

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,TABLE 7
Runtime (in Seconds) Comparison for the Guided VFF Scheme
versus Ab initio (Greedy-LU) Balancing Scheme
GuidedInit. coloring

VFF

Ab initio(Greedy-LU)

0.15
1.29
5.74
8.69
27.75

0.14
1.70
8.74
16.96
10.69

0.19
3.21
10.1
21.85
36.88

Input graph
CNR
Channeluk-2002
EuropeMG2

VOL. 28,

NO. 5, MAY 2017

TABLE 9Statistics on Structure of the Bipartite Real-World
Graphs G ¼ ðV1 ; V2 ; EÞ Used in Our Study
Input

jV1 j

jV2 j

jEj

DðV1 Þ

DðV2 Þ

KDD-A
KDD-B

8.4
1.9

106 2.0
107 2.9

107 3.0
107 5.6

108
108

85
75

104
106

LPCRE-B
LPCRE-D

9.6
8.0

103 7.7
103 7.3

104 2.6
104 2.4

105
105

844
808

14
13

Gene-Drug
3.0
Host-Pathogen 8.9

103 1.4
103 6.3

104 2.9
103 2.2

104
104

283
166

144
1,631

6.7
3.0

All runs were performed on 32 threads of the AMD x86 platform.

Recall that D corresponds to maximum degree.

coordinate descent (SCD) algorithms [31]. We therefore
selected for our experiments two test instances (KDD-A andKDD-B) related to SCD and representing data from theKDD Cup 2010 Challenge on educational data mining [32].
Further, we selected two additional instances (LPCRE-B
and LPCRE-D) from the Florida Sparse Matrix Collection [27] that arise from linear programming problems. We
consider the bipartite graphs representation of the sparsity
structures of these matrices (instances), G ¼ ðV1 ; V2 ; EÞ,
where the set V1 corresponds to the rows and the set V2 corresponds to the columns, and the edge set E corresponds tothe nonzero entries. In partial distance-2 coloring, we color
only the vertex set V2 (please refer Section 5 for definitionand other details of partial distance-2 coloring).
As additional test cases from another application
domain, we experimented on two bipartite graph inputs
obtained from the biology domain—viz. gene-drug interactions [33] and host-pathogen network [34]. Balanced coloring can be used as a way to determine efficient partial
orderings of vertices for parallel processing of such networks in co-clustering applications [35]. The testsets used inour experiments are summarized in Table 9.
Table 10 shows the parallel runtimes for two balancing
schemes—VFF and Sched-Rev—on the AMD platform. We
note that these are bipartite graph implementations of thoseschemes. For Sched-Rev we provide results from running
the algorithm for one round and for three rounds (simply
iterated three times). We observed relatively better performance from three rounds than two rounds. The distributions of color class sizes while using the different schemes
are provided in Fig. 6. We observe that the quality of output
from Sched-Rev with three rounds is comparable to VFF,
but the execution time is relatively high. Sched-Rev (withone round) provides faster execution times with comparable

quality. The corresponding distributions of color class sizes
from the unbalanced coloring scheme (Greedy-FF) are also
provided in Fig. 6 (in red). Overall, the results demonstrate
the general effectiveness of our balancing schemes for partial distance-2 balanced coloring as well.

7.6 Extensions to Balanced Coloring
In this section, we present two extensions to balanced coloring, motivated by two different practical considerations.
7.6.1 Weighted Balancing
Color class sizes (the number of vertices having the samecolor) form the basis for the balancing schemes presented
thus far. This assumes that the work associated with eachvertex is uniform in the end application. However, in some
applications, the workload may vary from vertex to vertex.
For such scenarios, a weighted treatment of vertices may be
more appropriate. Following a similar approach as in [15],we implemented and evaluated a weighted extension forbalancing, by setting the weight of a vertex to its degree. We
implemented by modifying the VFF balancing scheme asfollows. Let vðuÞ denote the weight of vertex u. Then, thetarget size for each color C is given byP
u2C vðuÞ
:gv ¼
jCj
7.6.2 Lower Bound-Based Coloring
One purpose of balancing is to ensure a uniform distributionof parallel workload across color classes in the end application. An alternative, more pragmatic strategy would be to not
aim for a balancing across all color classes, but rather focus on
ensuring that the smaller color classes are filled to a thresholdsize, sufficient to utilize the threads efficiently. Such a scheme

TABLE 8
Evaluation of the Balancing Heuristics on a Parallel Community Detection application, Grappolo
Input

w/o balanced coloringgraph

Run-time

w/ balanced coloring

0.15
1.87
37.31
7.83
17.95

3.98
38.85
954.81406.81358.26Modularity

Init. coloring VFF balancing Community detection

Init. coloring Community detection
CNR
ChannelMG2
uk-2002
Europe-osm

Run-time

Modularity
0.91240.93480.99840.98950.9988

0.15
1.87
37.31
7.83
17.95

All timing results are in seconds and were obtained on 36 threads of the Tilera manycore platform.

0.15
2.13
33.29
11.66
20.98

4.16
20.94
483.80254.27369.190.91190.93280.99840.9894
0.9988LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

1253

Fig. 6. Partial distance-2 coloring: The distributions of color class sizes produced by the different balanced coloring schemes (horizontal axis corresponds to colors (bins) and vertical axis (in log 2 scale) to sizes of color classes).

1254

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,TABLE 10
Parallel Run-Times (in Seconds) of Unbalanced andBalanced {VFF, Sched-Rev} Partial Distance-2
Schemes on the AMD Platform
Input
graph
KDD-A
KDD-B
LPCRE-B
LPCRE-D
Gene-Drug
Host-Pathogen

Sched-Rev

Init.
coloring

VFF
balancing(1 round)(3 rounds)

213
606
0.08
0.08
0.008
0.005

130
354
0.1
0.09
0.02
0.01

117
154
0.12
0.11
0.04
0.03

305
424
0.29
0.24
0.07
0.04

Thirty-two cores were used for the KDD inputs, and 16 cores were used for theremaining inputs (due to smaller size). All runs were performed to color vertices in V2 .

could have an advantage in reducing the balancing cost—because fewer vertex migrations are needed. This motivatedour second extension. We modified the VFF scheme to take as
input a lower bound (threshold) size (denoted by g ‘ ) for eachcolor class. During the process of balancing, we consider only
bins (colors) that have less than the threshold as potential candidates for receiving vertices (from larger bins). Therefore,
the resulting color size distribution is expected to be less balanced compared to the other balancing schemes, whereas theoverhead for balancing is reduced. We denote this modified
scheme as “LB-based” coloring scheme.

7.6.3 Experimental Results
We compared the two extensions outlined above (weighted
and LB-based) against the “baseline” schemes of VFF balancing and the Greedy-FF (initial coloring). Fig. 7 andTable 11 show the results of our comparative evaluation.
Fig. 7 shows the balancing quality produced by the extension schemes and the baseline schemes. As can be expected,
the weighted scheme does not exhibit a good balance basedon the number of vertices per color bin. However, if one
were to take into account the sum of the weights of the vertices per bin, then the weighted scheme does indeed achieve abalance. The LB-based scheme also shows an expectedbehavior, where the color classes that contain less than g ‘vertices in the initial coloring are the only classes to receive
new vertices into their bins (until the lower bound is met).

VOL. 28,

NO. 5, MAY 2017

TABLE 11
Run-Time Evaluation of Our Extensions (Weighted and LBbased) in Comparison to the VFF Balancing Scheme and theGreedy-FF (Initial Coloring) Scheme
Input

Steps

BalancingComm. Det.
Balancing
MG2
Comm. Det.
Balancinguk-2002 Comm. Det.
CNR

Greedy-FF

VFF

0
1.30
0
204.72
0
50.91

0.15
1.18
10.33
122.67
9.42
41.25

Weighted LB-based(g ‘ ¼1024)
0.15
1.42
10.94
123.31
9.75
44.05

0.07
1.25
7.86
149.45
3.59
51.08

All executions were performed on 16 threads of our x86 platform.

This implies that the balancing quality achieved by the LBscheme is sub-optimal but the benefits are expected to lie in
its reduced balancing cost (which we evaluate next).
Table 11 shows the run-times for the balancing step andthe community detection step (application impact) corresponding to the extension schemes and the baseline
schemes. In the case of weighted scheme, the balancing cost
is comparable to that of VFF balancing. As for the community detection step, the benefits due to using vertex weights
during balancing are not readily realized. This is because
our parallel implementation of the community detection
step (Grappolo) currently uses a vertex-based parallelization instead of an edge-based parallelization. The latter ismore conducive to the weighted scheme. As part of our
future study, we plan to implement and evaluate such anedge-based scheme in Grappolo, to better exploit the benefits of the weighted scheme.
In the case of LB-based scheme, we observe that the balancing cost is significantly smaller than the VFF balancing
cost. This confirms our expectation of reduced work during
the balancing procedure through the use of a lower boundsize. Note that this may cause sub-optimal balancing (asshown in Fig. 7), which in turn may affect the end application parallel performance. Table 11 shows a marginalincrease in the run-times for community detection as per
this expectation. In fact, as the lower bound value (g ‘ ) is further reduced, the size distribution of the color classes would
tend closer to the skewed distribution of the initial coloring.

Fig. 7. Balanced coloring extensions: Distribution of color class sizes produced by the two distance-1 balanced coloring extensions (Weighted, LowerBound) compared to VFF balancing (without weights or lower-bounds) and and initial coloring (Greedy-FF). Horizontal axis corresponds to colors(bins) and vertical axis to sizes of color classes (measured in the number of vertices).

LU ET AL.: ALGORITHMS FOR BALANCED GRAPH COLORINGS WITH APPLICATIONS IN PARALLEL COMPUTING

8CONCLUSIONSIn this paper, we provided a thorough treatment of the
problem of generating balanced graph colorings, with ourcontributions spanning algorithm development, parallelization, and application. We considered two different coloring
variants—distance-1 coloring (the standard coloring problem) and partial distance-2 coloring (defined on a bipartite
graph). We presented multiple balancing schemes, developed parallel implementations on conventional multi-cores
and an emerging manycore platform (Tilera), and evaluatedtheir effectiveness in achieving a balanced coloring andhow such results translate to gains in an application’s performance. Coloring is used in a number of parallel computing applications to identify independent tasks, and we
expect the detailed study presented in this paper involving
a family of balancing heuristics and their implementations
on modern day multi-core and manycore architectures, toserve as a valuable reference to application developers whoseek to improve parallel performance of their applications
using coloring.

ACKNOWLEDGMENTS
We thank the anonymous reviewers for the insightful comments, especially on partial distance-2 coloring. This
research was support in parts by U.S. Department of Energy
grants DE-SC-0006516, DE-AC05-76RL01830, and DE-SC0010205, the U.S. Department of Defense under the Autotuning for Power, Energy & Resilience (ATPER) project,and by National Science Foundation award IIS-1553528.

REFERENCES
[1]

[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]

H. Lu, M. Halappanavar, D. Chavarria-Miranda, A. Gebremedhin, and A. Kalyanaraman, “Balanced coloring for parallel computing applications,” in Proc. IEEE Int. Parallel Distrib. Process.
Symp., 2015, pp. 7–16.
W. Meyer, “Equitable coloring,” Amer. Math. Monthly, vol. 80,
pp. 920–922, 1973.
A. Hajnal and E. Szemeredi, Proof of a Conjecture of P. Erd€os.
Amsterdam, The Netherlands: North-Holland, 1970, pp. 601–623.
P. Erd€os, A. Renyi, and V. S
os, Eds., Combinatorial Theory and Its
Application. Amsterdam, The Netherlands: North-Holland, 1970.
B. Chen and K. Lih, “Equitable coloring of trees,” J. Combinatorial
Theory Series B, vol. 61, pp. 83–87, 1994.
W. Wang and K. Zhang, “Equitable colorings of line graphs andcomplete r-partite graphs,” Syst. Sci. Math. Sci., vol. 13, no. 2,
pp. 190–194, 2000.
H. Yap and Y. Zhang, “Equitable colorings of planar graphs,” J.
Combinatorial Math. Combinatorial Comput., vol. 27, pp. 97–105,
1998.
H. Furma
nczyk, Equitable Coloring of Graphs. Providence, RI, USA:Amer. Math. Soc., 2004, pp. 35–53.
M. Kubale, Ed., Graph Colorings. Providence, RI, USA: Amer.
Math. Soc., 2004.
H. Bodleander and F. Fomin, “Equitable colorings of bounded
treewidth graphs,” Theoretical Comput. Sci., vol. 349, no. 1, pp. 22–
30, 2005.
B. Smith, P. Bjørstad, and W. Gropp, Domain Decomposition; Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambiridge, U.K.: Cambridge Univ. Press, 1996.
R. Melhem and V. Ramarao, “Multicolor reorderings of sparse
matrices resulting from irregular grids,” ACM Trans. Math. Softw.,
vol. 14, pp. 117–138, 1988.
J. Blazewick, K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Scheduling Computer and Manufacturing Processes, 2nd ed. Berlin, Germany: Springer, 2001.
A. Tucker, “Perfect graphs and an application to optimizing
municipal services,” SIAM Rev., vol. 15, pp. 585–590, 1973.

1255[15] J. Robert, K. Gjertsen, M. T. Jones, and P. Plassmann, “Parallel
heuristics for improved, balanced graph colorings,” J. Parallel Distrib. Comput., vol. 37, pp. 171–186, 1996.
[16] M. T. Jones and P. Plassmann, “A parallel graph coloring heuristic,” SIAM J. Sci. Comput., vol. 14, pp. 654–669, 1993.
[17] J. E. G. Coffman, M. Garey, and D. Johnson, Approximation Algorithms for Bin Packing: A Survey. Boston, MA, USA: PWS Publishing Company, 1997, pp. 46–86.
[18] C. Pommerell, M. Annaratone, and W. Fichtner, “A set of new
mapping and coloring heuristics for distributed-memory parallel
processors,” SIAM J. Sci. Statist. Comput., vol. 13, pp. 194–226,
1992.
[19] H. Lu, M. Halappanavar, and A. Kalyanaraman, “Parallel heuristics for scalable community detection,” Parallel Comput., vol. 47,
pp. 19–37, 2015. [Online]. Available: http://www.sciencedirect.
com/science/article/pii/S0167819115000472[20] D. Chavarrıa-Miranda, M. Halappanavar, and A. Kalyanaraman,“Scaling graph community detection on the Tilera Many-corearchitecture,” in Proc. IEEE Int. Conf. High Performance Comput.,
Dec. 2014, Art. no. 11.
[21] V. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fastunfolding of communities in large networks,” J. Statist. Mech.: Theory Experiment, vol. 2008, 2008, Art. no. P10008.
[22] M. E. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. E, vol. 69, no. 6, pp. 66–133, 2004.
[23] F. Manne and E. Boman, “Balanced greedy colorings of sparse
random graphs,” in Proc. Norwegian Informat. Conf., 2005, pp. 113–
124.
[24] J. Culberson and F. Luo, “Exploring the k-colorable landscapewith iterated greedy,” in Cliques Coloring and Satisfiability: Second
DIMACS Implementation Challenge, D. Johnson and M. Trick, Eds.
Providence, RI, USA: Amer. Math. Soc., 1996, pp. 245–284.
[25] U. Çataly€
urek, J. Feo, A. H. Gebremedhin, M. Halappanavar, and
A. Pothen, “Graph coloring algorithms for multi-core and massively multithreaded architectures,” Parallel Comput., vol. 38,
pp. 576–594, 2012.
[26] A. Gebremedhin, F. Manne, and A. Pothen, “What color is your
Jacobian? Graph coloring for computing derivatives,” SIAM Rev.,
vol. 47, no. 4, pp. 629–705, 2005.
[27] T. A. Davis and Y. Hu, “The university of Florida sparse matrix
collection,” ACM Trans. Math. Softw., vol. 38, no. 1, pp. 1–25, Dec.
2011.
[28] J. Daily, A. Kalyanaraman, S. Krishnamoorthy, and A. Vishnu, “Awork stealing based approach for enabling scalable optimal
sequence homology detection,” J. Parallel Distrib. Comput., vol. 79–
80, pp. 132–142, 2015. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0743731514001518[29] M. Penrose, Random Geometric Graphs. London, U.K.: Oxford Univ.
Press, 2003.
[30] M. Halappanavar, “Algorithms for vertex-weighted matching ingraphs,” Ph.D. dissertation, Dept. Comput. Sci., Old Dominion
Univ., Norfolk, VA, USA, 2009.
[31] C. Scherrer, A. Tewari, M. Halappanavar, and D. Haglin, “Featureclustering for accelerating parallel coordinate descent,” in Proc.
Advances Neural Inf. Process. Syst., 2012, pp. 28–36.
[32] H.-F. Yu, et al., “Feature engineering and classifier ensemble for
KDD Cup 2010, ” in Proc. JMLR Workshop Conf. Proc., 2011, pp. 1–
16.
[33] M. Griffith, et al., “DGIdb: Mining the druggable genome,” Nature
Methods, vol. 10, no. 12, pp. 1209–1210, 2013.
[34] M. Wardeh, C. Risley, M. K. McIntyre, C. Setzkorn, and M. Baylis,“Database of host-pathogen and related species interactions, andtheir global distribution,” Sci. Data, vol. 2, 2015, Art. no. 150049.
[35] D. Hanisch, A. Zien, R. Zimmer, and T. Lengauer, “Co-clusteringof biological networks and gene expression data,” Bioinformatics,
vol. 18, no. suppl 1, pp. S145–S154, 2002.

1256

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,

Hao Lu received the bachelor’s degree in computer science from Washington State University,
in 2011. Currently, he is working toward the PhD
degree in computer science at Washington State
University. His research interests include highperformance computing, graph algorithms, andcomputational biology. The focus of his dissertation is on developing parallel heuristics on community detection in graphs, and heuristics forcoloring and balanced coloring. He is a memberof the ACM Computer Society.
Mahantesh Halappanavar received the PhD
degree in computer science from the Old Dominion University, in 2009. He is a senior researchscientist and team lead in the Data Sciences
Group, Pacific Northwest National Laboratory.
His research focuses on developing efficient parallel graph algorithms and their applications toseveral domains including the analysis of electric
power grids, information analytics, sparse linear
algebra, and cyber security. He explores theinterplay of algorithm design, architectural features, and data characteristics targeting massively multithreaded architectures and emerging multicore and manycore platforms.
Daniel Chavarrıa-Miranda received the MS and
PhD degrees in computer science from Rice
University, in 2004. He is a senior scientist with
High-Performance Computing Group, PacificNorthwest National Laboratory. His expertise is inruntime systems, programming models, compilers,
and languages for high performance computing.
He has been a member of the ACM since 1997.

VOL. 28,

NO. 5, MAY 2017

Assefaw H. Gebremedhin received the BSc
degree in electrical engineering from Addis
Ababa University, Ethiopia, in 1992, and the MSc
and PhD degrees in computer science from the
University of Bergen, Norway, in 2003 and 1999,
respectively. He is currently an assistant professor in the School of Electrical Engineering andComputer Science, Washington State University(WSU), where he leads the Scalable Algorithms
for Data Science Lab. Prior to joining WSU, in fall2014, he was a research assistant professor with
Department of Computer Science, Purdue University. His researchinterests include high-performance computing, combinatorial scientificcomputing, network science, data mining and machine learning, bioinformatics, and health analytics. He received the National Science Foundation CAREER Award in 2016.
Ajay Panyala received the BTech degree in computer science from Jawaharlal Nehru Technological University, Hyderabad, India, in 2007, and the
PhD degree in computer science from Louisiana
State University, in 2014. He is currently a post
doctoral research associate with Pacific Northwest National Laboratory. His research interest
include compiler optimizations for high performance computing.

Ananth Kalyanaraman received the bachelor’s
degree from the Visvesvaraya National Instituteof Technology, Nagpur, India, in 1998, and the
MS and PhD degrees from Iowa State University,
Ames, in 2002 and 2006, respectively. Currently,
he is an associate professor in the School ofElectrical Engineering and Computer Science,
Washington State University, Pullman. His
research focuses on developing parallel algorithms and software for data-intensive problems
originating in the areas of computational biology
and graph-theoretic applications. He received the DOE Early CareerAward, an Early Career Impact Award and two best paper awards. He
serves on editorial boards of the IEEE Transactions on Parallel and Distributed Systems and the Journal of Parallel and Distributed Computing.
He is a member of the AAAS, the ACM, the IEEE, the ISCB, and the
SIAM.
" For more information on this or any other computing topic,
please visit our Digital Library at www.computer.org/publications/dlib.