ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/loops/MatrixMultiply.java

Comparing jsr166/src/test/loops/MatrixMultiply.java (file contents):
Revision 1.1 by dl, Sun Sep 19 12:55:37 2010 UTC vs.
Revision 1.8 by jsr166, Thu Jan 15 18:34:19 2015 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		//import jsr166y.*;
8		import java.util.concurrent.*;
9	–	import java.util.concurrent.TimeUnit;
10	–
9
10		/**
11		* Divide and Conquer matrix multiply demo
12	<	**/
15	<
12	>	*/
13		public class MatrixMultiply {
14
15		/** for time conversion */
#	Line 20 | Line 17 | public class MatrixMultiply {
17
18		static final int DEFAULT_GRANULARITY = 32;
19
20	<	/** The quadrant size at which to stop recursing down
20	>	/**
21	>	* The quadrant size at which to stop recursing down
22		* and instead directly multiply the matrices.
23		* Must be a power of two. Minimum value is 2.
24	<	**/
24	>	*/
25		static int granularity = DEFAULT_GRANULARITY;
26
27		public static void main(String[] args) throws Exception {
#	Line 38 | Line 36 | public class MatrixMultiply {
36		procs = Integer.parseInt(args[0]);
37		if (args.length > 1)
38		n = Integer.parseInt(args[1]);
39	<	if (args.length > 2)
39	>	if (args.length > 2)
40		granularity = Integer.parseInt(args[2]);
41	<	if (args.length > 3)
41	>	if (args.length > 3)
42		runs = Integer.parseInt(args[2]);
43		}
44	<
44	>
45		catch (Exception e) {
46		System.out.println(usage);
47		return;
48		}
49	<
50	<	if ( ((n & (n - 1)) != 0) ||
49	>
50	>	if ( ((n & (n - 1)) != 0) ||
51		((granularity & (granularity - 1)) != 0) ||
52		granularity < 2) {
53		System.out.println(usage);
54		return;
55		}
56	<
57	<	ForkJoinPool pool = procs == 0? new ForkJoinPool() :
56	>
57	>	ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() :
58		new ForkJoinPool(procs);
59	<	System.out.println("procs: " + pool.getParallelism() +
59	>	System.out.println("procs: " + pool.getParallelism() +
60		" n: " + n + " granularity: " + granularity +
61		" runs: " + runs);
62	<
62	>
63		float[][] a = new float[n][n];
64		float[][] b = new float[n][n];
65		float[][] c = new float[n][n];
66	<
66	>
67		for (int i = 0; i < runs; ++i) {
68		init(a, b, n);
69		long start = System.nanoTime();
#	Line 80 | Line 78 | public class MatrixMultiply {
78		pool.shutdown();
79		}
80
83	–
81		// To simplify checking, fill with all 1's. Answer should be all n's.
82		static void init(float[][] a, float[][] b, int n) {
83		for (int i = 0; i < n; ++i) {
#	Line 101 | Line 98 | public class MatrixMultiply {
98		}
99		}
100
101	<	/**
101	>	/**
102		* Multiply matrices AxB by dividing into quadrants, using algorithm:
103		* <pre>
104	<	*      A      x      B
104	>	*      A      x      B
105		*
106	<	*  A11 | A12     B11 | B12     A11*B11 | A11*B12     A12*B21 | A12*B22
106	>	*  A11 | A12     B11 | B12     A11*B11 | A11*B12     A12*B21 | A12*B22
107		* |----+----| x |----+----| = |--------+--------| + |---------+-------|
108	<	*  A21 | A22     B21 | B21     A21*B11 | A21*B21     A22*B21 | A22*B22
108	>	*  A21 | A22     B21 | B21     A21*B11 | A21*B21     A22*B21 | A22*B22
109		* </pre>
110		*/
114	–
115	–
111		static class Multiplier extends RecursiveAction {
112		final float[][] A;   // Matrix A
113		final int aRow;      // first row    of current quadrant of A
#	Line 127 | Line 122 | public class MatrixMultiply {
122		final int cCol;
123
124		final int size;      // number of elements in current quadrant
125	<
125	>
126		Multiplier(float[][] A, int aRow, int aCol,
127		float[][] B, int bRow, int bCol,
128		float[][] C, int cRow, int cCol,
#	Line 156 | Line 151 | public class MatrixMultiply {
151		B, bRow+h, bCol,    // B21
152		C, cRow,   cCol,    // C11
153		h)),
154	<
154	>
155		seq(new Multiplier(A, aRow,   aCol,    // A11
156		B, bRow,   bCol+h,  // B12
157		C, cRow,   cCol+h,  // C12
#	Line 165 | Line 160 | public class MatrixMultiply {
160		B, bRow+h, bCol+h,  // B22
161		C, cRow,   cCol+h,  // C12
162		h)),
163	<
163	>
164		seq(new Multiplier(A, aRow+h, aCol,    // A21
165		B, bRow,   bCol,    // B11
166		C, cRow+h, cCol,    // C21
#	Line 174 | Line 169 | public class MatrixMultiply {
169		B, bRow+h, bCol,    // B21
170		C, cRow+h, cCol,    // C21
171		h)),
172	<
172	>
173		seq(new Multiplier(A, aRow+h, aCol,    // A21
174		B, bRow,   bCol+h,  // B12
175		C, cRow+h, cCol+h,  // C22
#	Line 187 | Line 182 | public class MatrixMultiply {
182		}
183		}
184
185	<	/**
185	>	/**
186		* Version of matrix multiplication that steps 2 rows and columns
187		* at a time. Adapted from Cilk demos.
188		* Note that the results are added into C, not just set into C.
189		* This works well here because Java array elements
190		* are created with all zero values.
191	<	**/
197	<
191	>	*/
192		void multiplyStride2() {
193		for (int j = 0; j < size; j+=2) {
194		for (int i = 0; i < size; i +=2) {
195
196		float[] a0 = A[aRow+i];
197		float[] a1 = A[aRow+i+1];
198	<
199	<	float s00 = 0.0F;
200	<	float s01 = 0.0F;
201	<	float s10 = 0.0F;
202	<	float s11 = 0.0F;
198	>
199	>	float s00 = 0.0F;
200	>	float s01 = 0.0F;
201	>	float s10 = 0.0F;
202	>	float s11 = 0.0F;
203
204		for (int k = 0; k < size; k+=2) {
205
#	Line 234 | Line 228 | public class MatrixMultiply {
228
229		}
230
231	<	static Seq2 seq(RecursiveAction task1,
232	<	RecursiveAction task2) {
233	<	return new Seq2(task1, task2);
231	>	static Seq2 seq(RecursiveAction task1,
232	>	RecursiveAction task2) {
233	>	return new Seq2(task1, task2);
234		}
235
236		static final class Seq2 extends RecursiveAction {
#	Line 251 | Line 245 | public class MatrixMultiply {
245		snd.invoke();
246		}
247		}
254	–
255	–
248		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines