Graph Coloring on a Coarse Grained Multiprocessor(extended abstract)
Assefaw Hadish Gebremedhin1, Isabelle Guérin Lassous2 ,Jens Gustedt3 , and Jan Arne Telle1
1

Univ. of Bergen, Norway. assefaw telle @ii.uib.no
INRIA Rocquencourt, France. Isabelle.Guerin-Lassous@inria.fr
3 LORIA & INRIA Lorraine, France. Jens.Gustedt@loria.fr2

Abstract. We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph G with a guarantee of at most ∆G 1 colors.


1 Introduction and Overview
The problem of graph coloring is crucial both for the applications of graph algorithms
to real world problems and for the domain of parallel graph algorithms itself. For thelatter, graph colorings using a bounded number of colors are often used in a theoreticalsetting to ensure the independence of tasks that are to be accomplished on the verticesof a graph, i.e. since the color classes form independent sets that don’t interact eachone of them can be treated in parallel. For a long time, no efficient parallel implementation of a graph coloring heuristic with good speedups was known, see Allwright et al.
(1995). However, in a recent result, Gebremedhin and Manne (1999a, 1999b) present
an algorithm and an implementation for a shared memory computer that proves to betheoretically and practically efficient with good speedups.
In this paper we make this successful approach feasible for a larger variety of architectures by extending it to the more general setting of coarse grained multiprocessors(CGM), see Dehne et al. (1996). This model of parallel computation makes an abstraction of the interconnection network between the processors of a parallel machine (ornetwork) and tries to capture the efficiency of a parallel algorithm using only a few
parameters. Several experiments show that the CGM model is of practical relevance:
implementations of algorithms formulated in the CGM model in general turn out to befeasible, portable, predictable and efficient, see Guérin Lassous et al. (2000).
This paper is organized as follows. In the next section we review the coarse grainedmodels of parallel computation and the basics of graph coloring heuristics. Then, we
present our algorithm together with an average case analysis of its time and work complexity. Finally, we show how to handle high degree vertices and how to alter the algorithm to achieve the same good time and work complexity also in the worst-case.
1.1 Coarse Grained Models of Parallel Computation.
In recent years several efforts have been made to define models of parallel (or distributed) computation that are more realistic than the classical PRAM models. In contrast to the PRAM, these new models are coarse grained, i.e. they assume that thenumber of processors p and the size of the input N of an algorithm are orders of magnitudes apart, p
N. By that assumption these models map much better on existingarchitectures where in general the number of processors is at most some thousands andthe size of the data that are to be handled goes into millions and billions.
This branch of research got its kick-off with Valiant (1990) introducing the socalled bulk synchronous parallel machine, BSP, and was refined in different directions
for example by Culler et al. (1993) to LogP, and by Dehne et al. (1996) to CGM.
We place ourselves in the context of CGM which seems to be well suited for a designof algorithms that are not too dependent on an individual architecture. We summarize
the assumptions of this model as follows:
All algorithms perform in so-called supersteps. A superstep consists of one phaseof interprocessor communication and one phase of local computation.
All processors have the same size M O N p of memory.
The communication network between the processors can be arbitrary.
The goal when designing an algorithm in this model is to keep the individual workload,time for communication and idle time of each processor within T s p where T is theruntime of the best sequential algorithm on the same data and s p , the speedup, is afunction that should be as close to p as possible. To be able to do so, it is considered
as good idea to keep the number of supersteps of such an algorithm as low as possible,
preferably o M .
The rationale for that is that for the communication time there are at least two invariants of the architecture that come into play: the latency, i.e. the minimal time a communication needs to startup before any data reach the other end, and the bandwidth, i.e.
the overall throughput per time unit of the communication network for large chunks ofdata. In any superstep there are at most O p communications for each processor and soa number of supersteps of o M ensures that the latency can be neglected for the performance analysis of such an algorithm. The bandwidth restriction of a specific platform
must still be observed, and here the best strategy is simply to reduce the communication
volume as much as possible. See Guérin Lassous et al. (2000) for an introduction andoverview on algorithms, code and experiments within the coarse grained setting.
As a legacy from the PRAM model it is usually assumed that the number of supersteps should be polylogarithmic in p, but there seems to be no real world rationale forthat. In fact, no relationship of the coarseness models to the complexity classes NC khave been found, and algorithms that simply ensure a number of supersteps that are afunction of p (and not of N) perform quite well in practice, see Goudreau et al. (1996).
To be able to organize the supersteps well it is natural to assume that each processor can keep a vector of p-sized data for each other processor and so the coarsenessrequirement translates into
p2 M N p(1)   



  
 

 

 

 

  

1.2 Graph Coloring.

 

A graph coloring is a labeling of the vertices of a graph G
V E with positive
integers, the colors, such that no two neighbors obtain the same color. An importantparameter of such a coloring C is the number of colors χ C that the coloring uses. Thiscan be viewed equivalently as searching for a partition of the vertex set of the graph into 

independent sets. Even though coloring a graph with the fewest number of colors is an
NP-hard problem, in many practical and theoretical settings a coloring using a bounded
number of colors, possibly far from the minimum, may suffice. Particularly in many
PRAM graph algorithms, a bounded coloring (resp. partition into independent sets) isneeded as a subroutine. However, up to recently no reasonable coloring had shown toperform well in practical parallel settings.
One of the simplest but quite efficient sequential heuristics for coloring is the socalled list coloring. It iterates over v V and colors v with the least color that has not
yet been assigned to one of its neighbors. It is  easy to see that this heuristic always
uses at most ∆G  1 colors, where ∆G maxv  V degree of v  . A parallelization of list
coloring has been shown by Gebremedhin and Manne (1999b) to perform well both intheory and by experiment on shared memory machines. They show that distributing thevertices evenly among the processors and running list coloring concurrently on the processors, while checking for color compatibility with already colored neighbors, createsvery few conflicts: the probability that two neighbors are colored at exactly the same
instance of the computation is quite small. Their algorithm was proven to behave wellon expectation and the conflicts could easily be resolved thereafter with very low cost.



1.3 The distribution of data on the processors
Even more than for sequential algorithms, a good organization of the data is crucial forthe efficiency of parallel code. We will organize the graphs that we handle as follows:
Every processor Pi is responsible for a specific subset Ui of the vertices. For a given
vertex v this processor is denoted by Pv .
Every edge v w  is represented as arcs v w , stored at Pv , and w v , stored at Pw .
For every arc v w processor Pv stores the identity of Pw and thus the location of
the arc w v . This is to avoid a logarithmic blow-up due to searching for Pw .
The arcs are sorted lexicographically and stored as a linked list per vertex.
For convenience, we will also assume that the input size N for any graph algorithm isin fact equal to the amount of edges  E  . Up to a constant which corresponds to theencoding size of an edge this will always be achieved in graphs that don’t have isolated
vertices. If the input that we receive is not of the desired form it can be efficiently
tranformed into one by the following steps:
Generate two arcs for each edge as described above,
Radix sort (see Guérin Lassous et al. (2000) for a CGM radix sort) the list of arcs
such that each processor receives the arcs v w if it is responsible for vertex w,
Let every processor note its identity on these sibling arcs,
Radix sort the list of arcs such that every processor receives its proper arcs (arcsv w if it is responsible for vertex v).
On a somewhat simplified level, the parallelization of list coloring for shared memory machines as given by Gebremedhin and Manne (1999b) worked by tackling the listof vertices numbered from 1 to n in a ‘round robin’ manner: at a given time 1  t  np
processor Pi colors vertex i  1  np  t. The shared memory assumptions ensure that Pi
may access the color information of any vertex at unit cost of time. The only problems
that can occur are with the neighbors that are in fact handled at exactly the same time.
Gebremedhin and Manne (1999b) show that the number of such conflicts is small on





 



 

 








 

 

 

 

P1
P2
P3
P4
P5
P6
t

 1

t

 2

t

 3

t

 4

Fig. 1. Graph on 72 vertices distributed onto 6 processors and 4 timeslots.

expectation, and that they can easily be handled a posteriori. In a coarse grained setting
we have to be more careful about the access to data that are situated on other processors.

2 The Algorithm
As the best sequential algorithm for an approximate graph coloring is linear in the sizeof the graph  G  , our aim is to design a parallel algorithm in CGM with a work (total
number of local computations) per processor in O  Gp and overall communication costs
in O  G  .
Algorithm 1 colors any graph G such that ∆G  M recursively. Section 3 shows how
to get rid of high degree vertices. The first type of high degree vertices are the vertices
v such that deg v  Np . The second type of high degree vertices are the vertices v suchNthat pk
deg v  Np . Note that the first call to Algorithm 1 is applied on the wholegraph G (G G).
In Algorithm 1, we group the vertices that are to be handled on each processor into
k different timeslots, see the figure and group vertices in the algorithm. The number
1 k  p of timeslots is a parameter of our algorithm. For each such timeslot wegroup the messages to the other processors together, see send to neighbors and receivefrom neighbors, and thus in general we produce few, even if possibly large, messages.
Figure 1 shows a graph on 72 vertices distributed onto 6 processors and 4 timeslots.
A naive parallel list coloring will respect adjacencies between timeslots, but may
violate adjacencies listed in bold, inside a timeslot. Our algorithm avoids this by coloring the bold subgraphs recursively until they are small enough to fit onto a single
processor. In the recursive call, a vertex will belong to the same processor but probably
to a different timeslot. Note that in general some processors may receive more vertices
than others.
By proceeding like this, we may generate more conflicts than in the shared memoryalgorithm; we may accidentally color two neighbors in the same timeslot with the same

 

 










Algorithm 1: List coloring on a CGM with p processors
Input: Subgraph G V  E  of a base graph G  V  E  with M edges per processor
such that ∆G M , M the initial input size per processor and lists Fv of forbidden
colors for the vertices.
Output: A valid coloring of G with at most ∆G

1 colors.

bottom if the size of G is less than N2 then solve the problem sequentially on processor P1 ;kpelsehigh degreegroup vertices

identify conflicts
resolve conflicts
color timeslot
send to neighbors

receive from neighbors

Get rid of high degree vertices of second type (see Section 3);
Each processor Pi groups its vertices Ui into k timeslots Ui t , t  1   k, such thatthe degree sum in all timeslots is about the same;
For each vertex v denote the index of its timeslot by tv ;for t  1 to k doforeach processor Pi do Consider all arcs e  v w  with v  Ui t and tv  tw  t;
Name this set Si and consider the vertices
VSi that have such an arc;
Recursively color the graph VSi  Si  ;foreach uncoloredvertex v with tv  t do color v with least possible color;
foreach arc v w  with v  Ui , tv  t and tw  t do collect the color of v forPw in a send buffer;send out the tuples (w,color);
receive the colors
from the other processors;
foreach arc v w  with w  Ui , tv  t and tw  t do add the color of v to Fw ;color. We find it convenient to resolve these conflicts beforehand, see identify conflicts
and resolve conflicts, by a recursive call to the same algorithm. We must ensure thatthese recursive calls do not produce a blow-up in computation and communication, andin fact the main part of the technical details in the paper are dedicated to ensure this.
In the recursive calls we must handle the restrictions that are imposed by previously
colored vertices. We extend the problem specification and assume that a vertex v also
has a list Fv of forbidden colors that is initially empty. An important issue for the complexity bounds will be that we will only add individual forbidden colors to Fv as theknowledge about them arrives on Pv . The list Fv as a whole will only be touched once,
namely when v is finally colored.
Observe also that the recursive calls in line resolve conflicts are not issued synchronized between the different processors: it is not necessary (nor desired) that theprocessors start recursion at exactly the same moment in time. When the calls reachthe communication parts of the algorithm during recursion, they will be synchronizedautomatically when waiting for the data of each other.1
Another issue that we have to face is the possible degree variation among the vertices. Whereas for the shared memory algorithm, different degrees of the vertices thatare handled in parallel just causes a slight asynchronicity of the execution of the algo1 In fact, when writing this the authors got more and more convinced of the importance ofasynchronicity between those of us working in Europe and the one visiting Australia.

rithm, in a CGM setting it might result in a severe imbalance of charge and even in amemory overflow of individual processors. We will see in Section 3 how to handle this.
2.1 An Average Case Analysis
To get a high level understanding of the algorithm, let us first assume that we deal withthe best of all worlds, that is:
we never have high degree vertices of first and second type (d is a high degree if
d  Mk ),the events of having an edge between a pair of vertices are all random and totally
independent of each other.
In Section 3, we show how to handle high degree vertices and in Section 4 we showwhat processing we have to add if we don’t assume randomness for the edges.

Lemma 1. Consider Algorithm 1. For any edge v w  , the probability that t v

 t is .
w

1k

Proof. The expected size of the degree sums of the timeslots Ui  t is the same. Since
there are k timeslots, when fixing the timeslot of v the probability that w is in the sametimeslot on its processor is 1k .

Lemma 2. The expected size of all subgraphs over all t
is N k.

 1

k in resolve conflicts



Proof. Every processor has M edges so each timeslot is expected to contain M k edges,
M k2 of which may create conflicts. So on each processor, considering all the timeslots,
we expect M k conflict edges and in total N k.



Lemma 3. For any value 1 k  p the expected number of supersteps is linear in p.


 



Proof. Each call can initiate k recursive calls. The maximal recursion depth of ouralgorithm
is the minimum value d such that N k d  M N p, i.e. kd  p, i.e. dlogk p . The total number of supersteps in each call is c  k, for some constant c, one
for each timeslot plus some to get rid of high degree vertices. Then, the total number ofsupersteps on recursion level i is given by c  k i and so the total number of supersteps is∑ c  ki  c  klogk p  c  plogk p

(2)

i 1



 

Lemma 4. Besides the cost for bottom and high degree, for any value of 1
expected work and communication per processor is O M .

 k  p the

Proof. First we show that the work and communication that any processor has to perform is a function in the number of its edges, i.e. M.
Inserting new forbidden colors into an unsorted list Fv can be done in constant time
per color. Any edge adds an item to the list of forbidden colors of one of its end-vertices
at most once, so the size of such a list is bounded by the degree of the vertex. Thus, thetotal size of these lists on any of the processors will never exceed the input size M.

Algorithm 2: Solve the problem sequentially on processor P1
Input: M the initial input size per processor, subgraph G  V  E  of a base graphG  V  E  with E
M and lists Fv of forbidden colors for the vertices.


collect colors

foreach processor Pi do
Let Ui  Ui V be the vertices that are stored on Pi ;For each v  Ui let d v  be the degree  of v in G ;Compute a sorted list Av of the least d v  1 allowed colors for v;
Communicate E and all lists Av to P1 ;solve sequentially for processor P1 do

Collect the graph G together with the lists Av ;Color G sequentially;
Send the resulting colors back to the corresponding processors;
retransmit colors foreach processor Pi do

Inform all neighbors of Ui of the colors that have been assigned;
Receive the colors from the other processors and update the lists Fv accordingly;

To find the least available color in color timeslot we then have to process the list
as a whole. This happens only once for each vertex v, and so one might hope to getaway with just sorting the list Fv . But sorting here can be too expensive, comparison
sort would impose a time of M logM whereas counting sort would lead to  Fv   M pervertex.
But nevertheless the work for this can be bound as follows. Each processor maintains a Boolean vector colors that is indexed with the colors and that will help to decide
for a vertex v on the least color to be taken. Since we got rid of high degree vertices
we know that no list Fv will be longer than M k and so a length of M k  1 suffices forcolors.
Later, when relaxing this condition in Section 3 we will need at most p colors forvertices of degree greater than N p and ensure to add no more than ∆   1 colors, where∆ is the maximum degree among the remaining vertices (∆   M).
In total this means that we have at most p  M  1 colors and so our vector colors
still fits on a processor. This vector is initialized once with all values “true”. Then whenprocessing a vertex v we run through its list of forbidden colors and set the corresponding items of colors to “false”. After that, we look for the first item in colors that stillis true and choose that color for v. Then, to revert the changes we run through the list
again and set all values to “true”. This then clearly needs at most a time of p  M  1plus the sizes of the list, so O M time in total.
As seen above, on any processor the total fraction of edges going into recursion is
expected to be M k, so the Main Theorem for divide and conquer algorithms shows that
the total costs are O M .









 

 

2.2 The bottom of recursion
At first one might be tempted to think that the bottom of the recursion should easily staywithin the required bounds and only communicates as much data as there are edges inAlgorithm 3: Compute the allowed colors Av of a vertex v.
Input: v together with its actual degree d v  and its (unordered) list Fv of forbidden
colors; A Boolean vector colors with all values set to true.
foreach c  Fv do Set colors c  f alse;for (c  1; Av  d v  ;c) do if colors c then Av  c Av ;foreach c  Fv do Set colors c  true;










the corresponding subgraph. But such an approach doesn’t count for the lists Fv offorbidden colors that the vertices might already have collected during higher levels ofrecursion. The size of these lists may actually be too large and their union might not
fit on a single processor. To take care of that situation we proceed in three steps, see
Algorithm 2.
In the first step collect colors, for each vertex v V we produce a short list ofallowed colors. In fact, the idea is that when we color the vertex later on we will notuse more than its degree  1 colors so a list of d v  1 allowed colors suffices to takeall restrictions of forbidden colors into account. With the same trick as in the previous
section, we can get away with a computation time of  Fv   d v to compute the list
Av , see Algorithm 3. It is also easy to see that we can use this trick again when wesequentially color the graph on P1 . We summarize:





 



V  E  with lists of forbidden
Lemma 5. The bottom of the recursion for graph G colors Fv can be done in a constant number of communication steps with overall workthat is proportional to  G  and the lists Fv and with a communication that is proportional to  G  .
Note that there will be k logk p calls to bottom, therefore P1 handles at most k logk p kpN2

edges and k logk p kpN2  k1  logk p kpN2  kp kpN2
of O M .

  M. That implies a total time for bottom

3 Getting Rid of High Degree Vertices
Line group vertices of Algorithm 1 groups the vertices into k  p timeslots of about
equal degree sum. Such a grouping would not be possible if the variation in the degreesof the vertices is too large. For example, if we have one vertex of very large degree, itwould always dominate the degree sum of its timeslot and we cannot achieve a balance.
So we will ensure that the degrees of all vertices is fairly small, namely smaller than
M k. Observe that this notion of ‘small’ depends on the input size M and thus theproperty of being of small degree may change during the course of the algorithm. This
is why we have to have the line high degree in every recursive call and not only for the
top level call. On the other hand this choice of M k will leave us enough freedom tochoose k in the range of 2  p as convenient.
We distinguish two different kinds of high degree vertices. The first type we have tohandle in a preprocessing step that is only done once on the top level of recursion. Theseare vertices for which the degree is greater than M N p. In fact, these vertices can’t
have all their arcs stored at one processor alone. Clearly, overall we can have at most





 

Algorithm 4: Get rid of high degree vertices of second type.
foreach processor Pi do
find all v  Ui with degree higher than M  k (Note: all degrees less than N p);
send the names and the degrees of these vertices to P1 ;for processor P1 do
Receive lists of high degree vertices;Group these vertices into kk timeslots W1   Wk of at most p vertices each andof a degree sum of at most 2N p for each timeslot;
Communicate the timeslots to the other processors;foreach processor Pi do
Receive the timeslots for the high degree vertices in Ui ;Communicate these values to all the neighbors of these vertices;
Receive the corresponding information from the other processors;
Compute Et i for t  1    k where one endpoint is in Ui ;for t  1 to k doforeach processor Pi do Communicate Et i to processor P1 ;for processor P1 do
Receive Et 
Wt  Et  the induced subgraph of
1  i  p Et i and denote by Gt high degree vertices of timeslot t;
Solve the problem for Gt sequentially, see Algorithm 2;

p such vertices, otherwise we would have more than N edges total. Thus the subgraphinduced by these vertices has at most p2 edges. Because of (1) this induced subgraphfits on processor P1 and a call to Algorithm 2 in a preprocessing step will color it.
The second type of high degree vertices, that we indeed have to treat in each recursive call, are those vertices v with N pk
M  k deg v  M 
N p, see Algorithm 4. Every processor holds at most k such vertices, otherwise it would hold morethan M  k  k M  edges. So in total there are at most p  k such vertices.
It is again easy to see that the probability for a vertex v to become a high degree
vertex of second type is small: even if it actually has M  k edges, with high probability
only M  k2 have their other endpoint in the same timeslot, and so v will not becomeof high degree on the next recursion level. So on expectation Algorithm 4 will only
contribute little to the total number of supersteps, workload and communication.

      



 





4 An add-on to achieve a good worst-case behavior
So far for a possible implementation of our algorithm we have a degree of freedom
in the number of timeslots k. If we are heading for just a guarantee on expectation asshown above we certainly would not like to bother with recursion and can choose k p.
This gives an algorithm that has 3p supersteps.
To give a deterministic algorithm with a worst case bound we choose the otherextreme, namely k 2. This enables us to bound the number of edges that go into therecursion. We have to distinguish two different types of edges: edges that have bothAlgorithm 5: Determine an ordering on the k 2 timeslots on each processor.

foreach processor  Pi do
foreach edge v w  do inform the processor of w about the timeslot of v;
for s  1 p do
for r r  0  1 do set mrr
is  0;

rr  , where P is the processor of w and r and r are
foreach edge v w  do add 1 to missthe timeslots of v and w;
rr  for s  1 
Broadcast all values mis
 p to all other processors;
inv 1  f alse;for s  2 to p do
A  0; A  0;
for s  s do
if inv s  then
A  A
m00
m11
ss ;
ss
01
10
A  A mss mss








else



A  A
m01
m10
ss
ss ;
00
11
A  A mss mss








if A  A then inv s  true;else inv s  f alse;

endpoints on the same processor, internal edges, and those that have them on different
processors, external edges.
Here we only describe how to handle external edges. In fact, the ideas for handlinginternal edges during the partition of the vertices into the two different timeslots arequite similar, but we omitted them for this short abstract.
To handle the external edges we add a call to Algorithm 5 after group vertices in
Algorithm 1. This algorithm counts the number mrr
is of edges between all possible pairsof timeslots on different processors, and broadcasts these values to all processors. Thena quick iterative algorithm is executed in parallel on all processors that decides on theprocessors for which the roles of the two timeslots are interchanged.
After having decided whether or not to interchange the roles of the timeslots onprocessors P1  Pi 1 we compute two values for processor Pi : A the number of edges
that would go into recursion if we would keep the role of the two timeslots, and A thesame number if we would interchange the role of the two timeslots.


References[Allwright et al., 1995] Allwright, J. R., Bordawekar, R., Coddington, P. D., Dincer, K., and Martin, C. L. (1995). A comparison of parallel graph coloring algorithms. Technical Report Tech.
Rep. SCCS-666, Northeast Parallel Architecture Center, Syracuse University.
[Culler et al., 1993] Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K., Santos, E., Subramonian, R., and von Eicken, T. (1993). LogP: Towards a Realistic Model of Parallel Com-putation. In Proceeding of 4-th ACM SIGPLAN Symp. on Principles and Practises of Parallel
Programming, pages 1–12.
[Dehne et al., 1996] Dehne, F., Fabri, A., and Rau-Chaplin, A. (1996). Scalable parallel computational geometry for coarse grained multicomputers. International Journal on Computational
Geometry, 6(3):379–400.
[Gebremedhin and Manne, 1999a] Gebremedhin, A. H. and Manne, F. (1999a). Parallel graphcoloring algorithms using OpenMP (extended abstract). In First European Workshop on
OpenMP, pages 10–18, Lund, Sweden.
[Gebremedhin and Manne, 1999b] Gebremedhin, A. H. and Manne, F. (1999b). Scalable, sharedmemory parallel graph coloring heuristics. Technical Report 181, Department of Informatics,
University of Bergen, 5020 Bergen, Norway.
[Goudreau et al., 1996] Goudreau, M., Lang, K., Rao, S., Suel, T., and Tsantilas, T. (1996). Towards efficiency and portability: Programming with the BSP model. In 8th Annual ACM symposium on Parallel Algorithms and Architectures (SPAA’96), pages 1–12.
[Gu´erin Lassous et al., 2000] Gu´erin Lassous, I., Gustedt, J., and Morvan, M. (2000). Feasability, portability, predictability and efficiency: Four ambitious goals for the design and implementation of parallel coarse grained graph algorithms. Technical report, INRIA.
[Valiant, 1990] Valiant, L. G. (1990). A bridging model for parallel computation. Communications of the ACM, 33(8):103–111.