1
\$\begingroup\$

I've created a program - it's an implementation of the cellular automata described in this paper (can't find a free PDF, sorry - anyway it's not really relevant to this question). The CA is implemented as a 3D array of integers of size int[length][20][20], 'length' being an arbitrary value determined by the user.

The tl;dr is: I've parallelized the program and not only does it not speed up, it slows down sometimes. Here's the code for the sequential and concurrent versions of the program, as well as a main benchmarking program (this and this).

The way it's parallelized is that the array is distributed between threads - say if length = 200 and we use 4 threads, thread 0 would process (we will call the lattice itself 'duct' from now on) duct[0][0][0] through duct[49][19][19], thread 1 would process duct[50][0][0] through duct[99][19][19], and so on. While processing a cell, a thread might have to access a different thread domain, so ReentrantLocks are used on the boundaries between sections to preserve integrity. Synchronization is achieved with a CyclicBarrier.

Anyway, the program is not speeding up at all. I suspect it's due to a memory bottleneck; while processing a given cell the program accesses its 26 neighbors, which might be the reason for the slow results. Otherwise, I've no idea where to start optimizing this program so parallelization yields results, or even if parallelization will ever yield results with this particular program.

Since I've to post some code here besides pastebin, here's how parallelization is implemented. This is done on the constructor:

int step = length/n_threads;
for(int i=0 ; i<n_threads ; i++)
{
    int begin =     i*step;
    int end   = (i+1)*step-1;
    if ((i+1) == n_threads)
        end = length-1;

    threadArray[i] = new Duct(begin, end, i);
    if (i < n_threads-1)
        thread_locks[i]  = new ReentrantLock();
    }
}

Here's the thread object constructor:

public Duct(int begin, int end, int index)
{
    thread_index = index;
    index_array = new Integer[end-begin+1];
    // Aquí Coordinate se usa como un par de números, no como una coordenada
    boundaries = new Coordinate(begin, end, 0);
    // [begin, end] ambos inclusive
    for(int z=begin, i=0 ; z<=end ; z++, i++) 
    {
        index_array[i] = z;
    }
}

and the function that controls synchronization

protected void execute(int nGens)
{
    if(generation_number == 0)
    {
        init_routine_stem(); // Hacemos la primera generación (colocación de stem cells) secuencialmente
    }

    total_generations = nGens;

    try {
    threadPool = Executors.newFixedThreadPool(n_threads);
    for (int i=0; i<threadArray.length; i++)
        threadPool.execute(threadArray[i]);
    } catch(Exception e){System.out.println(e);}

    for (int i=0; i<total_generations; i++)
    {
        try
        {  
            threadBarrier.await();
            generation_number++;

            if(!initialized)
            {
                initialized = threadArray[0].get_local_initialized();
                for (int t=1; t<threadArray.length; t++)
                    initialized = initialized && threadArray[t].get_local_initialized();
            }
        }      
        catch (BrokenBarrierException | InterruptedException e){}
    }
    threadPool.shutdown();
    while(!threadPool.isTerminated()){}
}
\$\endgroup\$
  • 2
    \$\begingroup\$ If you're accessing "26 neighbors" then there's probably a problem with threads spending too much time blocked on a lock and not enough time executing independantly. You program is probably essentially serial because there isn't enough parallelism inherent in the problem to make adding threads useful. This isn't a memory bottleneck. C.f. Amdahl's Law en.wikipedia.org/wiki/Amdahl%27s_law \$\endgroup\$ – markspace Jan 20 '18 at 17:24
  • \$\begingroup\$ @markspace at most, only 4 iterations per section length of the outermost loop will engage in locking and unlocking, so it most likely isnt that. Also, CAs are very much parallelizable, at least 2D ones. Maybe 3D ones like mine arent, due to memory accesses. \$\endgroup\$ – Kovalainen Jan 20 '18 at 18:00
  • \$\begingroup\$ Which bit is the code you're trying to parallelize? I have a feeling your answer will be in there. \$\endgroup\$ – Joe C Jan 21 '18 at 17:52
  • \$\begingroup\$ @Joe-C I am now realizing maybe posting two 1k-lines programs wasn't the best of ideas - I'm parallelizing the whole program, basically. \$\endgroup\$ – Kovalainen Jan 21 '18 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.