CODEWITHSUNDEEP
javamultithreadingconcurrencysynchronization
whd
whd

Reputation: 1861

Terribly slow synchronization

I'm trying to write game of life on many threads, 1 cell = 1 thread, it requires synchronization between threads, so no thread will start calculating it new state before other thread does not finish reading previous state. here is my code

        public class Cell extends Processor{
            private static int count = 0;
            private static Semaphore waitForAll = new Semaphore(0);
            private static Semaphore waiter = new Semaphore(0);
            private IntField isDead;
            public Cell(int n)
            {
                super(n);
                count ++;
            }
            public void initialize()
            {
                this.algorithmName = Cell.class.getSimpleName();
                isDead = new IntField(0);
                this.addField(isDead, "state");
            }
            public synchronized void step()
            {
                int size = neighbours.size();
                IntField[] states = new IntField[size];
                int readElementValue = 0;
                IntField readElement;
                sendAll(new IntField(isDead.getDist()));
                Cell.waitForAll.release();
    //here wait untill all other threads  finish reading
                    while (Cell.waitForAll.availablePermits() != Cell.count) {
                    }
    //here release semaphore neader lower 
                Cell.waiter.release();
                for (int i = 0; i < neighbours.size(); i++) {
                    readElement = (IntField) reciveMessage(neighbours.get(i));
                    states[i] = (IntField) reciveMessage(neighbours.get(i));
                }
                int alive = 0;
                int dead = 0;
                for(IntField ii: states)
                {
                    if(ii.getDist() == 1)
                        alive++;
                    else
                        dead++;
                }
                if(isDead.getDist() == 0)
                {
                    if(alive == 3)
                        isDead.setValue(1);
                    else
                        ;
                }
                else
                {
                    if(alive == 3 || alive == 2)
                        ;
                    else
                        isDead.setValue(0);
                }
                try {
                    while(Cell.waiter.availablePermits() != Cell.count)
                    {
                        ;
                      //if every thread finished reading we can acquire this semaphore
                    }
                    Cell.waitForAll.acquire();
                    while(Cell.waitForAll.availablePermits() != 0)
                        ;
//here we make sure every thread ends step in same moment
                    Cell.waiter.acquire();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }

processor class extends thread and in run method if i turn switch on it calls step() method. well it works nice for small amount of cells but when i run abou 36 cells it start to be very slow, how can repair my synchronization so it woudl be faster?

Upvotes: 0

Views: 416

Answers (1)

John Bollinger
John Bollinger

Reputation: 180968

Using large numbers of threads tends not to be very efficient, but 36 is not so many that I would expect that in itself to produce a difference that you would characterize as "very slow". I think more likely the problem is inherent in your strategy. In particular, I suspect this busy-wait is problematic:

Cell.waitForAll.release();
//here wait untill all other threads  finish reading
while (Cell.waitForAll.availablePermits() != Cell.count) {
}

Busy-waiting is always a performance problem because you are tying up the CPU with testing the condition over and over again. This busy-wait is worse than most, because it involves testing the state of a synchronization object, and this not only has extra overhead, but also introduces extra interference among threads.

Instead of busy-waiting, you want to use one of the various methods for making threads suspend execution until a condition is satisfied. It looks like what you've actually done is created a poor-man's version of a CyclicBarrier, so you might consider instead using CyclicBarrier itself. Alternatively, since this is a learning exercise you might benefit from learning how to use Object.wait(), Object.notify(), and Object.notifyAll() -- Java's built-in condition variable implementation.

If you insist on using semaphores, then I think you could do it without the busy-wait. The key to using semaphores is that it is being able to acquire the semaphore (at all) that indicates that the thread can proceed, not the number of available permits. If you maintain a separate variable with which to track how many threads are waiting on a given semaphore at a given point, then each thread reaching that point can determine whether to release all the other threads (and proceed itself) or whether to block by attempting to acquire the semaphore.

Upvotes: 1

Related Questions