前缀和算法.doc

多核并行实验报告题目：前缀和算法班级：物联网 姓名：XXX 学号：12345678 一 实验目的通过JAVA的多线程技术来模拟多核并行，并且实现求前缀和的算法。二 实验要求 以JAVA平台为编程基础，运用多线程技术，模拟多核并行，实现求前缀和的多核并行平衡树算法。三 实验内容 前缀和定义对于取值于集合S上的满足二元结合律运算的n个元素x1,.,xn的序列，所谓n个元素的前缀和是指如下定义的n个部分的和(或积)si =x1x2xi,1i n.本程序中多核组织成平衡树形式，每一个父节点即为一个核。设置三个级数A、B、C。A存放原始数据；B存放正向遍历的结果；C存放反向遍历的结果，也即所求的前缀和。本程序的伪代码如下：平衡树如下：3.1 程序源代码/AddTwo.javapackage .neu.chiewen.prefixSum;public class AddTwo implements Runnable private int i; private int j; public AddTwo(int i, int j) this.i = i; this.j = j; Override public void run() Main.B.get(i).set(j, Main.B.get(i - 1).get(2 * j) + Main.B.get(i - 1).get(2 * j + 1); Main.latch.countDown(); /CalcPrefix.javapackage .neu.chiewen.prefixSum;public class CalcPrefix implements Runnable private int i; private int j; public CalcPrefix(int i, int j) this.i = i; this.j = j; Override public void run() if (j % 2 = 1) Main.C.get(i).set(j, Main.C.get(i - 1).get(j - 1) / 2); else if (j = 0) Main.C.get(i).set(j, Main.B.get(Main.m - i).get(0); else Main.C.get(i).set(j, Main.C.get(i - 1).get(j / 2 - 1) + Main.B.get(Main.m - i).get(j); Main.latch.countDown(); /Main.javapackage .neu.chiewen.prefixSum;import java.util.ArrayList;import java.util.Random;import java.util.concurrent.CountDownLatch;public class Main public static final int m = 4; public static ArrayList values = prepareNumbers(); public static ArrayListArrayList B = new ArrayListArrayList(); public static ArrayListArrayList C = new ArrayListArrayList(); public static CountDownLatch latch; public static void main(String args) throws InterruptedException printNumbers(); B.add(new ArrayList(1 m); for (int i = 0; i values.size(); i+) B.get(0).add(values.get(i); for (int i = 1; i = m; i+) final int l = 1 (m - i); B.add(new ArrayList(l); for (int j = 0; j l; j+) B.get(i).add(0); latch = new CountDownLatch(l); for (int j = 0; j l; j+) new Thread(new AddTwo(i, j).start(); latch.await(); printResult(B, B:); for (int i = 0; i = m; i+) final int l = 1 i; C.add(new ArrayList(l); for (int j = 0; j l; j+) C.get(i).add(0); latch = new CountDownLatch(l); for (int j = 0; j l; j+) new Thread(new CalcPrefix(i, j).start(); latch.await(); printResult(C, C:); private static void printResult(ArrayListArrayList l, String name) System.out.println(name); for (int i = 0; i l.size(); i+) for (int j = 0; j l.get(i).size(); j+) System.out.print(l.get(i).get(j) + , ); System.out.println(); private static ArrayList prepareNumbers() ArrayList values = new ArrayList(); Random rand = new Random(); for (int i = 0; i 1 m; i+) values.add(rand.nextInt(100); return values; private static void printNumbers() System.out.print(Numbers: ); for (int i = 0; i values.size(); i+) System.out.print