CyclicBarrier Wasting Time - PullRequest
       55

CyclicBarrier Wasting Time

0 голосов
/ 03 февраля 2020

Я реализую параллельный алгоритм. Без CyclicBarrier я могу выполнить работу вдвое быстрее. Использование CyclicBarrier делает его до 100 раз дольше. Я включу мои вызовы потока и функцию потока, чтобы вы могли видеть, что происходит, и попытаться помочь мне. CyclicBarrier используется повторно, и новые потоки создаются каждый раз. По какой-то причине бит TRY (барьер.await;) вращается в течение длительного времени.

//Threads use this ...
private class threadILoop implements Runnable {
    protected int start, end, j, k;
    public threadILoop(int start,int end,int j,int k){
        this.start = start;
        this.end = end;
        this.j = j;
        this.k = k;
    }
    public void run() {
        for (int z = start; z < end; z++) {

            int zxj = z ^ j;
            if(zxj > z){
                if((z&k) == 0 && (data[z] > data[zxj]))
                    swap(z, zxj);
                if((z&k) != 0 && (data[z] < data[zxj]))
                    swap(z, zxj);
            }

            try{barrier.await();}
            catch (InterruptedException ex) { return; }
            catch (BrokenBarrierException ex) {return; }
        }
    }
}
//Main Driver here, where the CyclicBarrier gets allocated and the threads //are spawned from. 
 private void loopSort() throws InterruptedException {
        //print(data);
        barrier = new CyclicBarrier(N_THREADS);
        int kMax = data.length;
        for(int k = 2; k<=kMax; k*=2){
            for (int j = k/2; j > 0; j/=2) {

                int piece = data.length/N_THREADS;

                if(j > N_THREADS) {
                    //DIVIDE UP DATA SPACE FOR THREADS -> do work faster
                    int start = 0;
                    for(int i = 0; i < N_THREADS; i++)
                        {
                            int end =  i == N_THREADS - 1 ? data.length : start + piece;
                            threads[i] = new Thread(new threadILoop(start, end, j, k));
                            //threads[i].start();
                            start = end;
                        }

                    for(int i = 0; i < N_THREADS; i++)
                        {
                            threads[i].start();
                        }




                    // print(data);

                    for(int i = 0; i < N_THREADS; i++)
                        {
                            threads[i].join();
                        }
                }





1 Ответ

0 голосов
/ 03 февраля 2020

У вас слишком большой барьер в l oop, сейчас каждый поток получает диапазон элементов для обработки, и все они обрабатывают один элемент, ожидают все шаги, обрабатывают следующий, ждут и так далее. В этом случае накладные расходы на ожидание и обмен данными между потоками становятся гораздо более трудоемкими, чем фактическая обработка.

Попробуйте обработать больше элементов, прежде чем выравнивать их с другими потоками, например обработать во всем диапазоне, а затем ждать.

//Threads use this ...
private class threadILoop implements Runnable {
    protected int start, end, j, k;
    public threadILoop(int start,int end,int j,int k){
        this.start = start;
        this.end = end;
        this.j = j;
        this.k = k;
    }
    public void run() {
        for (int z = start; z < end; z++) {    
            int zxj = z ^ j;
            if(zxj > z){
                if((z&k) == 0 && (data[z] > data[zxj]))
                    swap(z, zxj);
                if((z&k) != 0 && (data[z] < data[zxj]))
                    swap(z, zxj);
            }
            // Wait moved from here
        }
        // To here (outside the inner loop)
        try{barrier.await();}
        catch (InterruptedException ex) { return; }
        catch (BrokenBarrierException ex) {return; }
    }
}
...