CyclicBarrier浪费时间

Question

我正在实现一个并行算法。没有CyclicBarrier，我可以在一半的时间内完成这项工作。使用CyclicBarrier需要花费100倍的时间。我将包括我的线程调用和线程函数，这样您就可以看到正在发生的事情，并尝试帮助我解决问题。CyclicBarrier被重用，每次都生成新线程。由于某种原因，TRY(barrier.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();
                        }
                }

Answer 1

循环的障碍太大了，现在每个线程都要处理一系列的元素，它们都处理一个元素，等待所有的步骤，下一个进程，等待等等。在这种情况下，线程之间等待和通信的开销比实际处理的工作量要大得多。

在与其他线程(例如，在整个范围内的process)对齐之前，尝试处理更多的元素，然后等待。

//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; }
    }
}