并行与串行实现的解释说明

Question

我已经实现了串行和并行算法，使用Jacobi方法解决线性系统。两个实现都收敛并给出正确的解决方案。

我遇到的问题是：

1. 如何在较低的迭代次数后并行实现收敛（相对于串行实现），我是否面临未知的并发问题？
2. 并行实现中迭代次数如何随每次运行而变化 (6,7)?

谢谢！

程序输出：

Mathematica solution: {{-1.12756}, {4.70371}, {-1.89272}, {1.56218}}
Serial: iterations=7194 , error=false, solution=[-1.1270591, 4.7042074, -1.8922218, 1.5626835]
Parallel: iterations=6 , error=false, solution=[-1.1274619, 4.7035804, -1.8927546, 1.5621948]

代码:

主函数

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        Serial s = new Serial();
        Parallel p = new Parallel(2);

        s.solve();
        p.solve();

        System.out.println("Mathematica solution: {{-1.12756}, {4.70371}, {-1.89272}, {1.56218}}");
        System.out.println(String.format("Serial: iterations=%d , error=%s, solution=%s", s.iter, s.errorFlag, Arrays.toString(s.data.solution)));
        System.out.println(String.format("Parallel: iterations=%d , error=%s, solution=%s", p.iter, p.errorFlag, Arrays.toString(p.data.solution)));


    }

}

数据

public class Data {

    public float A[][] = {{2.886139567217389f, 0.9778259187352214f, 0.9432146432722157f, 0.9622157488990459f}
                        ,{0.3023479007910952f,0.7503803506938734f,0.06163831478699766f,0.3856445043958068f}
                        ,{0.4298384105199724f,  0.7787439716945019f,    1.838686110345417f, 0.6282668788698587f}
                        ,{0.27798718418255075f, 0.09021764079496353f,   0.8765867330141233f,    1.246036349549629f}};

    public float b[] = {1.0630309381779384f,3.674438173599066f,0.6796639099285651f,0.39831385324794155f};
    public int size = A.length;
    public float x[] = new float[size];
    public float solution[] = new float[size];


}

并行

import java.util.Arrays;

    public class Parallel {


        private final int workers;
        private float[] globalNorm;

        public int iter;
        public int maxIter = 1000000;
        public double epsilon = 1.0e-3;
        public boolean errorFlag = false;

        public Data data = new Data();

        public Parallel(int workers) {
            this.workers = workers;
            this.globalNorm = new float[workers];
            Arrays.fill(globalNorm, 0);
        }

        public void solve() {

            JacobiWorker[] threads = new JacobiWorker[workers];
            int batchSize = data.size / workers;

            float norm;

            do {


                for(int i=0;i<workers;i++) {
                    threads[i] = new JacobiWorker(i,batchSize);
                    threads[i].start();
                }

                for(int i=0;i<workers;i++)
                    try {

                        threads[i].join();

                    } catch (InterruptedException e) {

                        e.printStackTrace();
                    }

                // At this point all worker calculations are done!

                norm = 0;

                for (float d : globalNorm) if (d > norm) norm = d;

                if (norm < epsilon)
                    errorFlag = false; // Converged
                else
                    errorFlag = true; // No desired convergence

            } while (norm >= epsilon && ++iter <= maxIter);

        }

        class JacobiWorker extends Thread {

            private final int idx;
            private final int batchSize;

            JacobiWorker(int idx, int batchSize) {
                this.idx = idx;
                this.batchSize = batchSize;
            }

            @Override
            public void run() {

                int upper = idx == workers - 1 ? data.size : (idx + 1) * batchSize;

                float localNorm = 0, diff = 0;

                for (int j = idx * batchSize; j < upper; j++) { // For every
                                                                // equation in batch

                    float s = 0;
                    for (int i = 0; i < data.size; i++) { // For every variable in
                                                            // equation

                        if (i != j)
                            s += data.A[j][i] * data.x[i];

                        data.solution[j] = (data.b[j] - s) / data.A[j][j];

                    }


                    diff = Math.abs(data.solution[j] - data.x[j]);
                    if (diff > localNorm) localNorm = diff;
                    data.x[j] = data.solution[j];


                }


                globalNorm[idx] = localNorm;

            }

        }

    }

串行

public class Serial {

    public int iter;
    public int maxIter = 1000000;
    public double epsilon = 1.0e-3;
    public boolean errorFlag = false;

    public Data data = new Data();

    public void solve() {

        float norm,diff=0;

        do {


            for(int i=0;i<data.size;i++) {

                float s=0;  
                for (int j = 0; j < data.size; j++) {
                    if (i != j)
                        s += data.A[i][j] * data.x[j];
                    data.solution[i] = (data.b[i] - s) / data.A[i][i];
                }
            }


            norm = 0;

            for (int i=0;i<data.size;i++) {
                diff = Math.abs(data.solution[i]-data.x[i]); // Calculate convergence
                if (diff > norm) norm = diff;
                data.x[i] = data.solution[i];
            }


            if (norm < epsilon)
                errorFlag = false; // Converged
            else
                errorFlag = true; // No desired convergence


        } while (norm >= epsilon && ++iter <= maxIter);

    }
}

- 1osmi

---

一个工人会发生什么？（首先要做的是确保1个工人与单线程相同） - andrew cooke

使用1个工作线程时，迭代次数在每次运行中都不会改变 - 它始终为6。 - 1osmi

Answer 1

我认为这是实现的问题而不是并行化问题。看看使用Parallel p = new Parallel(1);会发生什么。

Mathematica solution: {{-1.12756}, {4.70371}, {-1.89272}, {1.56218}}
Serial: iterations=7194 , error=false, solution=[-1.1270591, 4.7042074, -1.8922218, 1.5626835]
Parallel: iterations=6 , error=false, solution=[-1.1274619, 4.7035804, -1.8927546, 1.5621948]

事实证明，你的第二个实现并没有完全和第一个实现做相同的事情。

我将其添加到你的并行版本中，它在相同数量的迭代中运行。

for (int i = idx * batchSize; i < upper; i++) {
    diff = Math.abs(data.solution[i] - data.x[i]); // Calculate
        // convergence
        if (diff > localNorm)
            localNorm = diff;
            data.x[i] = data.solution[i];
        }
}

- John Vint

---

我的推理是：在任何实现中，程序必须进行n次计算，然后才能评估解决方案错误并增加迭代次数。在并行实现中，这是并行完成的，因此需要更少的时间。但是，无论实现方式如何，迭代次数都应该增加相同的次数。 - 1osmi

@1osmi，我一开始的推理有误。但是这个操作会导致你的串行版本多运行7000次。将其放入（并替换现有的代码）你的并行版本中，你应该能看到正确的数字。 - John Vint