Java Concurrent - 没有 speedUp 获得 LU 算法 - 虚假共享？

Question

我有一个关于 java 并发软件的问题要问你。

我的应用程序的主要算法必须将 A 矩阵分解为 LU 矩阵:A = LU。此处粘贴的分解方法进行了高斯-若尔当归约。该软件设计用于处理位置为 A[0][0] != 0 的方阵。

不幸的是，为了算法的正确工作，我必须等待每一行都实现值。

我尝试使用障碍使该算法并行(等待每一行的实现并增加 "rigaCorrente" 值)但即使在并行中我也没有获得真正的加速版本我的处理器(2.4 GHz Core 2 Duo P8600)以总功率的 80%(而不是串行处理器的 40-50%)工作。

我担心的是我遇到了虚假分享的情况。问题与虚假分享有关，还是与其他事情有关？我知道 JVM 执行了很好的优化，但它仍然使用处理器的一半功率。我不认为改进算法是不可能的!

我的序列号代码:

    public void decompose(){
    int n = A.length;
    for(int k=0; k<n-1;k++) {
        for(int i=k+1; i<n; i++) {
            A[i][k] = A[i][k]/A[k][k];
            for(int j=k+1; j<n; j++) {
                A[i][j] = A[i][j] - A[i][k] * A[k][j];
            }
        }
    }
    decomposed = true;
}

我的并行代码:

    public class Manager {
private double [][] A;

private Semaphore main = new Semaphore(0);
private CyclicBarrier barriera;

private AtomicInteger index;
private int rigaCorrente = 0;
private boolean stop = false;

public Manager(final double A[][], final int numThr){
    this.A = A;
    this.index = new AtomicInteger(1);

    barriera = new CyclicBarrier(numThr, new Runnable(){

        @Override
        public void run() {

        rigaCorrente++;
        index = new AtomicInteger(rigaCorrente+1);

    if(rigaCorrente == A.length - 1){
            setStop(true);
            main.release();
        }
    }

    });
}

线程类:

    public class Deco implements Runnable {

private Manager manager;

public Deco(Manager manager){
    this.manager = manager;
}

@Override
public void run() {
    double [][] A = manager.getA();

while(manager.getStop() == false){
    int i;
    while((i = (manager.getIndex().getAndIncrement())) < (A.length)){
    double pivot = A[i][manager.getRigaCorrente()]/A[manager.getRigaCorrente()]                        [manager.getRigaCorrente()];

        for(int k = manager.getRigaCorrente(); k<A.length; k++)
            A[i][k] = A[i][k] - (pivot*A[manager.getRigaCorrente()][k]);

        A[i][manager.getRigaCorrente()] = pivot;
 }

        manager.acquireBarriera();

    }// Stop

}

   }

主要用于并行代码:

    package luConcurrent.test;
    import java.util.Arrays;
    import java.util.Scanner;

    import lu.DecompositionLU;
    import lu.IO;

    public class Starter {
private static IO io;
private static DecompositionLU dec;
public static void main(String[] args) throws Exception {
    io = new IO("//Users//black//Desktop//serie//2500.txt");
    int numThr = 2;

    double [][] A = io.readMatrixFromInputFile();
    double [] b = io.readArrayFromInputFile();
    double [] x;

    dec = new DecompositionLU(A);

    System.out.println("A.length: "+A.length);

    Manager manager = new Manager(A,numThr);
    Thread[] pool = new Thread[numThr];

    for(int i=0; i<pool.length; i++){
        pool[i] = new Thread(new Deco(manager));
    }

    long inizio = System.nanoTime();

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

    manager.getMain().acquire();

    dec.ProgresiveSustitution(b);
    x = dec.RegresiveSustitution(b);

    long fine = System.nanoTime()-inizio;

    System.out.println("Solution is: "+Arrays.toString(x));
    Scanner sc = new Scanner(System.in);
    sc.nextLine();
    System.out.println("Tempo: "+fine);
    sc.close();

}
    }

结果:

    1000x1000 Serial: 1154679000 nanoSec
    1000x1000 Parallel 2 Threads: 1135663000 nanoSec

    1750x1750 Serial: 7502559000 nanoSec
    1750x1750 Parallel 2 Threads: 6667129000 nanoSec

    4000x4000 Serial: 89851311000 nanoSec
    4000x4000 Parallel 2 Threads: 84348616000 nanoSec

Answer 1

我不会仓促得出错误共享正在发生的结论。该算法的并行版本增加了大量开销，这可能是导致其性能低于您预期的原因。

串行版本只有三个嵌套循环:k 上的外循环、i 上的中间循环和 j 上的内循环>。它所做的只是数组访问和算术运算，所以这应该非常快。

并行版本在每次迭代时使用 CyclicBarrier 在 rigaCorrente(当前行，如果我没记错的话)上运行其外循环。这增加了开销。循环屏障导致早到的线程等待，直到最后一个到达。好吧，你只有两个线程，所以第一个到达的线程必须等待第二个。那是一些死时间。即使线程大约同时完成，执行屏障同步也会产生开销。然后一个线程必须等待，而另一个线程运行屏障操作。

中间循环结束于 index，它是 getIndex 方法调用获取的 AtomicInteger。方法调用增加了开销，getAndIncrement 在线程之间增加了一些争用。

内部循环(令人困惑的是 k 而不是串行版本中的 j )在其中调用了 getRigaCorrente 方法。有时——但只是有时——JVM 可以内联方法调用。我在这里没有看到 getRigaCorrente 的实现，但是由于 rigaCorrente 是 manager 的私有(private)实例变量，它不是易变的，而且它是多线程读写，也许这个方法是同步的。这会增加更多开销。

这里的问题是线程在运行期间必须与共享状态交互很多。这增加了开销和争用。我建议尝试找到一种方法来提前在线程之间划分工作，然后告诉每个线程它需要做什么工作，然后让它们都独立运行。