Optimize Memory Usage for Connected Components Algorithm

#1

Hi guys, is there anyway to optimize memory usage for Connected Component algorithm?

I’m following this without the @@compSizes MapAccum but still hitting System Memory critical.

The graph has about 1B nodes and the machine has 160GB of Memory. Idle memory is around 90GB.

Thanks!

1 Like
#3

Which version of the algorithm are you using?
The latest version has 3 data structures, 2 of which have one item per vertex. This is to provide output in 2 ways:
MinAccum @cc_id = 0; //each vertex’s tentative component id
MapAccum<INT, ListAccum> @@compGroupBySize;

The first one is pretty necessary: a label per vertex. The second repeats the same info, but groups the vertices by their final community ids.

#4

I think our solutions team has said than in general, you can lower runtime dyanmic memory by trading off paralleling:

  • Instead of using GSQL’s ACCUM clause which is an implied “FOREACH IN PARALLEL” clause,
    manually use a FOREACH statement, which executes sequentially. It might be must slower, but should use less dynamic memory.
#5

Another thing you could consider is to increase the memory size.

Could you try it with 256 GB memory?

Thanks.

#6

Hi guys, thanks for the reply!

@Xinyu_Chang we are trying not to use so much memory as for cloud pricing, it’s based on memory usage.

I’m trying to split the query into batches as but would like to confirm the correctness of the algorithm

 CREATE QUERY connected_component (INT k) FOR GRAPH device {
        MinAccum<int> @cc_id = 0;       //each vertex's tentative component id
        SumAccum<int> @old_id = 0;
        OrAccum<bool> @active;
        DATETIME before;
  
        before = now();
        Start (ANY) = {ANY};

        # Initialize: Label each vertex with its own internal ID
        S = SELECT x 
            FROM Start:x
            POST-ACCUM x.@cc_id = getvid(x),
                       x.@old_id = getvid(x)        
            ;

        # Propagate smaller internal IDs until no more ID changes can be DOne
        WHILE (Start.size()>0) DO
          FOREACH i IN RANGE [0, k-1] DO
                S = SELECT t
                    FROM Start:s -(:e)-> :t WHERE getvid(s) % k == i
                    ACCUM s.@cc_id += t.@cc_id // If s has a smaller id than t, copy the id to t
                    POST-ACCUM
                      CASE WHEN s.@old_id != s.@cc_id THEN // If t's id has changed
                                s.@old_id = s.@cc_id,
                                s.@active = true
                      ELSE 
                                s.@active = false
                      END
                    ;
          END;
          Start = SELECT s FROM Start:s WHERE s.@active == true;
        END;

        PRINT("TOOK " + to_string(datetime_diff(now(), before)) + " seconds") AS timing;
}
#7

Update: We increased memory to 256GB as recommended and managed to run the algorithm. However it only used 160GB which was just a bit beyond our instance’s memory initially.