The parallel coloring algorithm in Zoltan is based on the work of
Boman et al. for distance-1
coloring and Bozdag et al. for
distance-2 coloring. It was implemented in Zoltan by Doruk Bozdag and
Umit V. Catalyurek, Department of Biomedical Informatics, the Ohio State
University. Distance-1 coloring algorithm is an iterative data
parallel algorithm that proceeds in two-phased rounds. In the first
phase, processors concurrently color the vertices assigned to
them. Adjacent vertices colored in the same parallel step of this
phase may result in inconsistencies. In the second phase, processors
concurrently check the validity of the colors assigned to their
respective vertices and identify a set of vertices that needs to be
re-colored in the next round to resolve the detected
inconsistencies. The algorithm terminates when every vertex has been
colored correctly. To reduce communication frequency, the coloring
phase is further decomposed into computation and communication
sub-phases. In a communication sub-phase processors exchange recent
color information. During a computation sub-phase, a number of
vertices determined by the SUPERSTEP_SIZE parameter, rather than a
single vertex, is colored based on currently available color
information. With an appropriate choice of a value for SUPERSTEP_SIZE,
the number of ensuing conflicts can be kept low while at the same time
preventing the runtime from being dominated by the sending of a large
number of small messages. The distance-2 graph coloring problem aims
at partitioning the vertex set of a graph into the fewest sets
consisting of vertices pairwise at distance greater than two from each
other. The algorithm is an extension of the parallel distance-1
coloring algorithm.
In distance-1 coloring, a
post-processing to coloring, named as recoloring, is also implemented
in Zoltan by Ahmet Erdem Sariyuce, Erik Saule and Umit V. Catalyurek,
Department of Biomedical Informatics, the Ohio State University. Its
details are presented in Sariyuce et
al.. Recoloring is an iterative improvement algorithm first
proposed in Culberson 92 for
sequential architecture. The algorithm uses an existing coloring of a
graph to produce an new coloring. The vertices of the graph are
sorted according to a given permutation of the colors so that vertices
with the same color are recolored concurrently. There are two modes
of the recoloring procedure that are controlled by
RECOLORING_TYPE parameter. In asynchronous recoloring, the vertices
are colored using the same algorithm used for the original coloring;
the only difference is the ordering of the vertices, which is expected
to present less conflicts (and therefore is faster and leads to fewer
colors). In synchronous recoloring, each processor waits for its
neighboors to finish coloring the vertices of a given color before
starting to color the vertices of the next color. Using a simple first
fit color allocation policy, the algorithm guarantees that no
conflicts will be generated and that the number of colors will not
increase. The order in which the colors are considers is given by the
RECOLORING_PERMUTATION parameter. The forward order processes the
colors in increasing value of the color identifier; while the reverse
order processes them in the opposite order. The non-decreasing order
processes the colors so that the most used color in the graph is
colored last; while the non-increasing order is the opposite
order. The number of times the recoloring procedure is applied is
controlled by the RECOLORING_NUM_OF_ITERATIONS parameter (setting it
to zero disables recoloring).