We carry out some research on the OP2 domain specific language, which can generate automatically optimized parallel codes for unstructured mesh applications. In 2D these meshes are planar graphs.
These meshes contain numbered vertices and edges. We partition the graph into np number of subgraphs and we compute the task on every subgraph with independent compute processors. It is important to note, that during this partitioning process we duplicate edges that were cut on the borders, so if we cut through an edge, then there will be a copy of it in both subgraphs with the same index.
In our application we perform parallel algorithms within each subgraph where with an edge-centric approach: on each edge calculations increment values on the connected vertices. To be able to parallelize this, we need to color the edges so that no two edges with the same color share a vertex. This can easily be done with a greedy coloring algorithm, which usually provides a near-optimal coloring wrt number of colors. However we have an additional constraint: increments applied to any given vertex should happen in the same order regardless of partitioning (number, shape). This requires an ordering between colors, and for edges to be colored so this constraint is satisfied.
For this problem, we have a trivial solution: we choose the index of the edge as the color. With this we have as many colors as many edges in any given subgraph, but we do not have multiple edges with the same color, thus we can not parallelize the execution.
And this is the part, where I am stuck. I can not create an algorithm which produces such a coloring which is more effective than the above one in terms of number of colors. (Also I can not prove whether this is possible at all or not..). Do you have any suggestions on how to approach this problem?