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/publicdomain/zero/1.0/
 */

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

import java.util.concurrent.*;

public class FJJacobi {

    //    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 = new ForkJoinPool(1);
        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();
            fjp.invoke(driver);

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