A confusion about the Co-Scheduling of Gemini

[jxyszzx]

Hi, I am trying to implement several graph algorithms for an experimental research and meet some problem.

Firstly, we define a concept named seperable.
A main computing function f is seperable iff f(A union B) = f(f(A),f(B)), e.g., sum, min, max are seperable, while min color, h-index are non-seperable.

In my understanding, the design of Co-Scheduling of Computation can well support the seperable type of algorithm, while it is not very suitable for non-seperable computing in just a process_edge.

Taking the graph coloring algorithm as an example, we have to maintain a temporal vertex_array to store the min color which have not been used in all neighbors for every vertex because a super step is divided into p mini-steps, and it will lead to a huge space overhead.

But if there's no mini-steps and the system just process vertices one by one, we only need to maintain such a temporal vertex_array for every machine rather than vertex, which may significantly reduce the space cost.

I am not sure whether my understanding is correct or have something overlooked. Looking forward to your views.

Thank you very much.

[coolerzxw]

Hi, the given concept looks a bit confusing to me. Do you mean algorithms that are associative and commutative?
While I agree that classical graph coloring is unsuitable/inefficient to be implemented in Gemini, the major obstacle seems to be the BSP model which makes coordination in coarse-grained super-steps.
Regarding co-scheduling, there are no explicit barriers between mini-steps like those between super-steps. So mini-steps (or co-scheduling) should not be the main issue.