test/loops/CCJacobi.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

// Jacobi iteration on a mesh. Based loosely on a Filaments demo

import java.util.concurrent.*;

public class CCJacobi {

    //    static final int DEFAULT_GRANULARITY = 4096;
    static final int DEFAULT_GRANULARITY = 256;

    /**
     * The maximum number of matrix cells
     * at which to stop recursing down and instead directly update.
     */
    static final double EPSILON = 0.0001;  // convergence criterion

    public static void main(String[] args) throws Exception {
        int n = 2048;
        int steps = 1000;
        int granularity = DEFAULT_GRANULARITY;

        try {
            if (args.length > 0)
                n = Integer.parseInt(args[0]);
            if (args.length > 1)
                steps = Integer.parseInt(args[1]);
            if (args.length > 2)
                granularity = Integer.parseInt(args[2]);
        }

        catch (Exception e) {
            System.out.println("Usage: java FJJacobi <matrix size> <max steps> [<leafcells>]");
            return;
        }

        ForkJoinPool fjp = ForkJoinPool.commonPool();

        // allocate enough space for edges
        int dim = n+2;
        int ncells = dim * dim;
        double[][] a = new double[dim][dim];
        double[][] b = new double[dim][dim];
        // Initialize interiors to small value
        double smallVal = EPSILON; // 1.0/dim;
        for (int i = 1; i < dim-1; ++i) {
            for (int j = 1; j < dim-1; ++j)
                a[i][j] = smallVal;
        }
        // Fill all edges with 1's.
        for (int k = 0; k < dim; ++k) {
            a[k][0] = 1.0;
            a[k][n+1] = 1.0;
            a[0][k] = 1.0;
            a[n+1][k] = 1.0;
            b[k][0] = 1.0;
            b[k][n+1] = 1.0;
            b[0][k] = 1.0;
            b[n+1][k] = 1.0;
        }
        int nreps = 10;
        for (int rep = 0; rep < nreps; ++rep) {
            Driver driver = new Driver(a, b, 1, n, 1, n, steps, granularity);

            long startTime = System.currentTimeMillis();
            driver.invoke();

            long time = System.currentTimeMillis() - startTime;
            double secs = ((double)time) / 1000.0;

            System.out.println("Compute Time: " + secs);
            System.out.println(fjp);
            Thread.sleep(1000);
        }
    }

    abstract static class MatrixTree extends CountedCompleter<Void> {
        // maximum difference between old and new values
        double maxDiff;
        MatrixTree(CountedCompleter<?> p, int c) { super(p, c); }
    }

    static final class LeafNode extends MatrixTree {
        final double[][] A; // matrix to get old values from
        final double[][] B; // matrix to put new values into

        // indices of current submatrix
        final int loRow;    final int hiRow;
        final int loCol;    final int hiCol;

        int steps = 0; // track even/odd steps

        LeafNode(CountedCompleter<?> p,
                 double[][] A, double[][] B,
                 int loRow, int hiRow,
                 int loCol, int hiCol) {
            super(p, 0);
            this.A = A;   this.B = B;
            this.loRow = loRow; this.hiRow = hiRow;
            this.loCol = loCol; this.hiCol = hiCol;
        }

        public final void compute() {
            boolean AtoB = (steps++ & 1) == 0;
            double[][] a = AtoB ? A : B;
            double[][] b = AtoB ? B : A;

            double md = 0.0; // local for computing max diff
            for (int i = loRow; i <= hiRow; ++i) {
                for (int j = loCol; j <= hiCol; ++j) {
                    double v = 0.25 * (a[i-1][j] + a[i][j-1] +
                                       a[i+1][j] + a[i][j+1]);
                    b[i][j] = v;
                    double prev = a[i][j];
                    double diff = v - prev;
                    if (diff < 0) diff = -diff;
                    if (diff > md) md = diff;
                }
            }

            maxDiff = md;
            tryComplete();
        }
    }

    static final class FourNode extends MatrixTree {
        MatrixTree q1;
        MatrixTree q2;
        MatrixTree q3;
        MatrixTree q4;
        FourNode(CountedCompleter<?> p) {
            super(p, 3);
        }

        public void onCompletion(CountedCompleter<?> caller) {
            double md = q1.maxDiff, m;
            if ((m = q2.maxDiff) > md)
                md = m;
            if ((m = q3.maxDiff) > md)
                md = m;
            if ((m = q4.maxDiff) > md)
                md = m;
            maxDiff = md;
            setPendingCount(3);
        }

        public final void compute() {
            q4.fork();
            q3.fork();
            q2.fork();
            q1.compute();
        }
    }

    static final class TwoNode extends MatrixTree {
        MatrixTree q1;
        MatrixTree q2;

        TwoNode(CountedCompleter<?> p) {
            super(p, 1);
        }

        public void onCompletion(CountedCompleter<?> caller) {
            double md = q1.maxDiff, m;
            if ((m = q2.maxDiff) > md)
                md = m;
            maxDiff = md;
            setPendingCount(1);
        }

        public final void compute() {
            q2.fork();
            q1.compute();
        }
    }

    static final class Driver extends RecursiveAction {
        MatrixTree mat;
        double[][] A; double[][] B;
        int firstRow; int lastRow;
        int firstCol; int lastCol;
        final int steps;
        final int leafs;
        int nleaf;

        Driver(double[][] A, double[][] B,
               int firstRow, int lastRow,
               int firstCol, int lastCol,
               int steps, int leafs) {
            this.A = A;
            this.B = B;
            this.firstRow = firstRow;
            this.firstCol = firstCol;
            this.lastRow = lastRow;
            this.lastCol = lastCol;
            this.steps = steps;
            this.leafs = leafs;
            mat = build(null, A, B, firstRow, lastRow, firstCol, lastCol, leafs);
            System.out.println("Using " + nleaf + " segments");
        }

        MatrixTree build(MatrixTree p,
                         double[][] a, double[][] b,
                         int lr, int hr, int lc, int hc, int leafs) {
            int rows = (hr - lr + 1);
            int cols = (hc - lc + 1);

            int mr = (lr + hr) >>> 1; // midpoints
            int mc = (lc + hc) >>> 1;

            int hrows = (mr - lr + 1);
            int hcols = (mc - lc + 1);

            if (rows * cols <= leafs) {
                ++nleaf;
                return new LeafNode(p, a, b, lr, hr, lc, hc);
            }
            else if (hrows * hcols >= leafs) {
                FourNode q = new FourNode(p);
                q.q1 = build(q, a, b, lr,   mr, lc,   mc, leafs);
                q.q2 = build(q, a, b, lr,   mr, mc+1, hc, leafs);
                q.q3 = build(q, a, b, mr+1, hr, lc,   mc, leafs);
                q.q4 = build(q, a, b, mr+1, hr, mc+1, hc, leafs);
                return q;
            }
            else if (cols >= rows) {
                TwoNode q = new TwoNode(p);
                q.q1 = build(q, a, b, lr, hr, lc,   mc, leafs);
                q.q2 = build(q, a, b, lr, hr, mc+1, hc, leafs);
                return q;
            }
            else {
                TwoNode q = new TwoNode(p);
                q.q1 = build(q, a, b, lr,   mr, lc, hc, leafs);
                q.q2 = build(q, a, b, mr+1, hr, lc, hc, leafs);
                return q;
            }
        }

        static void doCompute(MatrixTree m, int s) {
            for (int i = 0; i < s; ++i) {
                m.setPendingCount(3);
                m.invoke();
                m.reinitialize();
            }
        }

        public void compute() {
            doCompute(mat, steps);
            double md = mat.maxDiff;
            System.out.println("max diff after " + steps + " steps = " + md);
        }
    }
}
Revision:	1.7
Committed:	Sat Sep 12 18:16:45 2015 UTC (8 years, 7 months ago) by dl
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.6:	+1 -1 lines
Log Message:	No explicit gc()
#	Content
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/publicdomain/zero/1.0/
5	*/
6
7	// Jacobi iteration on a mesh. Based loosely on a Filaments demo
8
9	import java.util.concurrent.*;
10
11	public class CCJacobi {
12
13	// static final int DEFAULT_GRANULARITY = 4096;
14	static final int DEFAULT_GRANULARITY = 256;
15
16	/**
17	* The maximum number of matrix cells
18	* at which to stop recursing down and instead directly update.
19	*/
20	static final double EPSILON = 0.0001; // convergence criterion
21
22	public static void main(String[] args) throws Exception {
23	int n = 2048;
24	int steps = 1000;
25	int granularity = DEFAULT_GRANULARITY;
26
27	try {
28	if (args.length > 0)
29	n = Integer.parseInt(args[0]);
30	if (args.length > 1)
31	steps = Integer.parseInt(args[1]);
32	if (args.length > 2)
33	granularity = Integer.parseInt(args[2]);
34	}
35
36	catch (Exception e) {
37	System.out.println("Usage: java FJJacobi <matrix size> <max steps> [<leafcells>]");
38	return;
39	}
40
41	ForkJoinPool fjp = ForkJoinPool.commonPool();
42
43	// allocate enough space for edges
44	int dim = n+2;
45	int ncells = dim * dim;
46	double[][] a = new double[dim][dim];
47	double[][] b = new double[dim][dim];
48	// Initialize interiors to small value
49	double smallVal = EPSILON; // 1.0/dim;
50	for (int i = 1; i < dim-1; ++i) {
51	for (int j = 1; j < dim-1; ++j)
52	a[i][j] = smallVal;
53	}
54	// Fill all edges with 1's.
55	for (int k = 0; k < dim; ++k) {
56	a[k][0] = 1.0;
57	a[k][n+1] = 1.0;
58	a[0][k] = 1.0;
59	a[n+1][k] = 1.0;
60	b[k][0] = 1.0;
61	b[k][n+1] = 1.0;
62	b[0][k] = 1.0;
63	b[n+1][k] = 1.0;
64	}
65	int nreps = 10;
66	for (int rep = 0; rep < nreps; ++rep) {
67	Driver driver = new Driver(a, b, 1, n, 1, n, steps, granularity);
68
69	long startTime = System.currentTimeMillis();
70	driver.invoke();
71
72	long time = System.currentTimeMillis() - startTime;
73	double secs = ((double)time) / 1000.0;
74
75	System.out.println("Compute Time: " + secs);
76	System.out.println(fjp);
77	Thread.sleep(1000);
78	}
79	}
80
81	abstract static class MatrixTree extends CountedCompleter<Void> {
82	// maximum difference between old and new values
83	double maxDiff;
84	MatrixTree(CountedCompleter<?> p, int c) { super(p, c); }
85	}
86
87	static final class LeafNode extends MatrixTree {
88	final double[][] A; // matrix to get old values from
89	final double[][] B; // matrix to put new values into
90
91	// indices of current submatrix
92	final int loRow; final int hiRow;
93	final int loCol; final int hiCol;
94
95	int steps = 0; // track even/odd steps
96
97	LeafNode(CountedCompleter<?> p,
98	double[][] A, double[][] B,
99	int loRow, int hiRow,
100	int loCol, int hiCol) {
101	super(p, 0);
102	this.A = A; this.B = B;
103	this.loRow = loRow; this.hiRow = hiRow;
104	this.loCol = loCol; this.hiCol = hiCol;
105	}
106
107	public final void compute() {
108	boolean AtoB = (steps++ & 1) == 0;
109	double[][] a = AtoB ? A : B;
110	double[][] b = AtoB ? B : A;
111
112	double md = 0.0; // local for computing max diff
113	for (int i = loRow; i <= hiRow; ++i) {
114	for (int j = loCol; j <= hiCol; ++j) {
115	double v = 0.25 * (a[i-1][j] + a[i][j-1] +
116	a[i+1][j] + a[i][j+1]);
117	b[i][j] = v;
118	double prev = a[i][j];
119	double diff = v - prev;
120	if (diff < 0) diff = -diff;
121	if (diff > md) md = diff;
122	}
123	}
124
125	maxDiff = md;
126	tryComplete();
127	}
128	}
129
130	static final class FourNode extends MatrixTree {
131	MatrixTree q1;
132	MatrixTree q2;
133	MatrixTree q3;
134	MatrixTree q4;
135	FourNode(CountedCompleter<?> p) {
136	super(p, 3);
137	}
138
139	public void onCompletion(CountedCompleter<?> caller) {
140	double md = q1.maxDiff, m;
141	if ((m = q2.maxDiff) > md)
142	md = m;
143	if ((m = q3.maxDiff) > md)
144	md = m;
145	if ((m = q4.maxDiff) > md)
146	md = m;
147	maxDiff = md;
148	setPendingCount(3);
149	}
150
151	public final void compute() {
152	q4.fork();
153	q3.fork();
154	q2.fork();
155	q1.compute();
156	}
157	}
158
159	static final class TwoNode extends MatrixTree {
160	MatrixTree q1;
161	MatrixTree q2;
162
163	TwoNode(CountedCompleter<?> p) {
164	super(p, 1);
165	}
166
167	public void onCompletion(CountedCompleter<?> caller) {
168	double md = q1.maxDiff, m;
169	if ((m = q2.maxDiff) > md)
170	md = m;
171	maxDiff = md;
172	setPendingCount(1);
173	}
174
175	public final void compute() {
176	q2.fork();
177	q1.compute();
178	}
179	}
180
181	static final class Driver extends RecursiveAction {
182	MatrixTree mat;
183	double[][] A; double[][] B;
184	int firstRow; int lastRow;
185	int firstCol; int lastCol;
186	final int steps;
187	final int leafs;
188	int nleaf;
189
190	Driver(double[][] A, double[][] B,
191	int firstRow, int lastRow,
192	int firstCol, int lastCol,
193	int steps, int leafs) {
194	this.A = A;
195	this.B = B;
196	this.firstRow = firstRow;
197	this.firstCol = firstCol;
198	this.lastRow = lastRow;
199	this.lastCol = lastCol;
200	this.steps = steps;
201	this.leafs = leafs;
202	mat = build(null, A, B, firstRow, lastRow, firstCol, lastCol, leafs);
203	System.out.println("Using " + nleaf + " segments");
204	}
205
206	MatrixTree build(MatrixTree p,
207	double[][] a, double[][] b,
208	int lr, int hr, int lc, int hc, int leafs) {
209	int rows = (hr - lr + 1);
210	int cols = (hc - lc + 1);
211
212	int mr = (lr + hr) >>> 1; // midpoints
213	int mc = (lc + hc) >>> 1;
214
215	int hrows = (mr - lr + 1);
216	int hcols = (mc - lc + 1);
217
218	if (rows * cols <= leafs) {
219	++nleaf;
220	return new LeafNode(p, a, b, lr, hr, lc, hc);
221	}
222	else if (hrows * hcols >= leafs) {
223	FourNode q = new FourNode(p);
224	q.q1 = build(q, a, b, lr, mr, lc, mc, leafs);
225	q.q2 = build(q, a, b, lr, mr, mc+1, hc, leafs);
226	q.q3 = build(q, a, b, mr+1, hr, lc, mc, leafs);
227	q.q4 = build(q, a, b, mr+1, hr, mc+1, hc, leafs);
228	return q;
229	}
230	else if (cols >= rows) {
231	TwoNode q = new TwoNode(p);
232	q.q1 = build(q, a, b, lr, hr, lc, mc, leafs);
233	q.q2 = build(q, a, b, lr, hr, mc+1, hc, leafs);
234	return q;
235	}
236	else {
237	TwoNode q = new TwoNode(p);
238	q.q1 = build(q, a, b, lr, mr, lc, hc, leafs);
239	q.q2 = build(q, a, b, mr+1, hr, lc, hc, leafs);
240	return q;
241	}
242	}
243
244	static void doCompute(MatrixTree m, int s) {
245	for (int i = 0; i < s; ++i) {
246	m.setPendingCount(3);
247	m.invoke();
248	m.reinitialize();
249	}
250	}
251
252	public void compute() {
253	doCompute(mat, steps);
254	double md = mat.maxDiff;
255	System.out.println("max diff after " + steps + " steps = " + md);
256	}
257	}
258	}