Request for expansion in user guide

[kyleboyle]

In the user guide http://www.i3s.unice.fr/~hogie/software/grph/doc/manuals/grph-user-manual.pdf you have written the following. I'm wondering if you could point to an example that finishes your thought at the end?

5.6.5 Parallelism Modern computers embed a multi-core processor, enabling threads and processes to run in parallel. In order to take advantage of this parallelism, whenever possible split the computation in a number of independant jobs that are executed in parallel, within distinct threads, on the local computer. Depending on the algorithms, the speed off varies from near-to-zero to n,nbeing the number of processors/cores available on the computer. Grph comes with a basic parallelization framework for the execution of a certain class of algorithms: if an algorithm can be decomposed in routines called independently on every vertex, it may be invoked by the following code pattern:

[lhogie]

Dear Kyle,

Grph is somehow discontinued today. In order to achieve better performance we had to drastically change the data structure. The new data structure could not been made compatible with the old one, so we preferred starting a new project. It is called JMaxGraph and it's there:

http://www.i3s.unice.fr/~hogie/software/?name=jmaxgraph

It's still a young project but if you are interested in using it, I'll do my best to help you.

Best, Luc

-- Luc Hogie COMRED Research Unit (I3S(CNRS-UNS) Inria) I3S Laboratory, University of Nice Sophia Antipolis

http://www.i3s.unice.fr/~hogie/ luc.hogie@cnrs.fr +33 4 89 73 24 25 (office) +33 6 80 91 40 71 (mobile)

De: "Kyle Boyle" notifications@github.com À: "lhogie" grph@noreply.github.com Cc: "Subscribed" subscribed@noreply.github.com Envoyé: Vendredi 21 Septembre 2018 21:47:42 Objet: [lhogie/grph] Request for expansion in user guide (#4)

In the user guide you have written this, I'm wondering if you could point to an example that finishes your thought at the end?

5.6.5 Parallelism Modern computers embed a multi-core processor, enabling threads and processes to run in parallel. In order to take advantage of this parallelism, whenever possible split the computation in a number of independant jobs that are executed in parallel, within distinct threads, on the local computer. Depending on the algorithms, the speed off varies from near-to-zero to n,nbeing the number of processors/cores available on the computer. Grph comes with a basic parallelization framework for the execution of a certain class of algorithms: if an algorithm can be decomposed in routines called independently on every vertex, it may be invoked by the following code pattern: — You are receiving this because you are subscribed to this thread. Reply to this email directly, [ https://github.com/lhogie/grph/issues/4 | view it on GitHub ] , or [ https://github.com/notifications/unsubscribe-auth/APyjqEeheCjSySVbC7ztO4TZ0SFf8Xweks5udUJegaJpZM4W0xM4 | mute the thread ] .

[kyleboyle]

Luc, thanks for the response. In your new project, could you explain the page rank snippet:

public static int[] f(Graph g, Random r, int walkLength, int nbThreads)
    {
        g.out.ensureLoaded(nbThreads);
        int nbVertices = g.getNbVertices();
        final int[] ranks = new int[nbVertices];
        LongProcess lp = new LongProcess("page ranking", " iteration", walkLength);
        final int end = walkLength / nbThreads;

        new MultiThreadProcessing(nbThreads, lp)
        {
            @Override
            protected void runInParallel(ThreadSpecifics s, List<Thread> threads)
                    throws Throwable
            {
                int u = r.nextInt();
                int[] adj;

                for (int l = 0; l < end; ++l)
                {
                    s.progressStatus = l;

                    while ((adj = g.out.mem.b[u]).length == 0)
                    {
                        u = r.nextInt(nbVertices);
                    }

                    ++ranks[u = adj[r.nextInt(adj.length)]];
                }
            }
        };

        Cout.debug(walkLength * nbThreads, MathsUtilities.sum(ranks));
        return ranks;
    }

Does this code ensure that each vertex gets its rank assigned? I see that you are splitting up the work by thread count and number of graph vertices, but each thread is still selecting a random node from the entire graph.

while ((adj = g.out.mem.b[u]).length == 0) what is this doing? I'm not sure what your data structures contain.