test/loops/FJJacobi.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/licenses/publicdomain
 */

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

import java.util.concurrent.*;
//import jsr166y.*;

public class FJJacobi {

    static final int DEFAULT_GRANULARITY = 4096; // 1024;

    /**
     * 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 = new ForkJoinPool();

        // 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 = 1.0/dim;
        for (int i = 1; i < dim-1; ++i) {
            for (int j = 1; j < dim-1; ++j)
                a[i][j] = smallVal;
        }

        int nreps = 3;
        for (int rep = 0; rep < nreps; ++rep) {
            // 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;
            }
            Driver driver = new Driver(a, b, 1, n, 1, n, steps, granularity);

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

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

            System.out.println("Compute Time: " + secs);
            System.out.println("Workers: " + fjp.getPoolSize());
            System.out.println(fjp);
        }
    }


    abstract static class MatrixTree extends RecursiveAction {
        // maximum difference between old and new values
        double maxDiff;
        public final double directCompute() {
            compute();
            return maxDiff;
        }
        public final double joinAndReinitialize(double md) {
            if (tryUnfork())
                compute();
            else {
                //                quietlyJoin();
                quietlyHelpJoin();
                reinitialize();
            }
            double m = maxDiff;
            return (md > m)? md : m;
        }

    }


    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(double[][] A, double[][] B,
                 int loRow, int hiRow,
                 int loCol, int hiCol) {
            this.A = A;   this.B = B;
            this.loRow = loRow; this.hiRow = hiRow;
            this.loCol = loCol; this.hiCol = hiCol;
        }

        public 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 diff = v - a[i][j];
                    if (diff < 0) diff = -diff;
                    if (diff > md) md = diff;
                }
            }

            maxDiff = md;
        }
    }

    static final class FourNode extends MatrixTree {
        final MatrixTree q1;
        final MatrixTree q2;
        final MatrixTree q3;
        final MatrixTree q4;
        FourNode(MatrixTree q1, MatrixTree q2,
                 MatrixTree q3, MatrixTree q4) {
            this.q1 = q1; this.q2 = q2; this.q3 = q3; this.q4 = q4;
        }

        public void compute() {
            q4.fork();
            q3.fork();
            q2.fork();
            double md = q1.directCompute();
            md = q2.joinAndReinitialize(md);
            md = q3.joinAndReinitialize(md);
            md = q4.joinAndReinitialize(md);
            maxDiff = md;
        }
    }


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

        TwoNode(MatrixTree q1, MatrixTree q2) {
            this.q1 = q1; this.q2 = q2;
        }

        public void compute() {
            q2.fork();
            maxDiff = q2.joinAndReinitialize(q1.directCompute());
        }

    }


    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(A, B, firstRow, lastRow, firstCol, lastCol, leafs);
            System.out.println("Using " + nleaf + " segments");

        }

        MatrixTree build(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(a, b, lr, hr, lc, hc);
            }
            else if (hrows * hcols >= leafs) {
                return new FourNode(build(a, b, lr,   mr, lc,   mc, leafs),
                                    build(a, b, lr,   mr, mc+1, hc, leafs),
                                    build(a, b, mr+1, hr, lc,   mc, leafs),
                                    build(a, b, mr+1, hr, mc+1, hc, leafs));
            }
            else if (cols >= rows) {
                return new TwoNode(build(a, b, lr, hr, lc,   mc, leafs),
                                   build(a, b, lr, hr, mc+1, hc, leafs));
            }
            else {
                return new TwoNode(build(a, b, lr,   mr, lc, hc, leafs),
                                   build(a, b, mr+1, hr, lc, hc, leafs));

            }
        }

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