concurrent/forkjoin/Integrate.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/
 */

/*
 * @test
 * @bug 6865571
 * @summary Numerical Integration using fork/join
 * @run main Integrate reps=1 forkPolicy=dynamic
 * @run main Integrate reps=1 forkPolicy=serial
 * @run main Integrate reps=1 forkPolicy=fork
 */

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * Sample program using Gaussian Quadrature for numerical integration.
 * This version uses a simplified hardwired function.  Inspired by a
 * <A href="http://www.cs.uga.edu/~dkl/filaments/dist.html">
 * Filaments</A> demo program.
 */
public final class Integrate {

    static final double errorTolerance = 1.0e-11;
    /** for time conversion */
    static final long NPS = (1000L * 1000 * 1000);

    static final int SERIAL = -1;
    static final int DYNAMIC = 0;
    static final int FORK = 1;

    /** the function to integrate */
    static double computeFunction(double x) {
        return (x * x + 1.0) * x;
    }

    static final double start = 0.0;
    static final double end = 1536.0;

    /**
     * The number of recursive calls for
     * integrate from start to end.
     * (Empirically determined)
     */
    static final int calls = 263479047;

    static String keywordValue(String[] args, String keyword) {
        for (String arg : args)
            if (arg.startsWith(keyword))
                return arg.substring(keyword.length() + 1);
        return null;
    }

    static int intArg(String[] args, String keyword, int defaultValue) {
        String val = keywordValue(args, keyword);
        return (val == null) ? defaultValue : Integer.parseInt(val);
    }

    static int policyArg(String[] args, String keyword, int defaultPolicy) {
        String val = keywordValue(args, keyword);
        if (val == null) return defaultPolicy;
        if (val.equals("dynamic")) return DYNAMIC;
        if (val.equals("serial")) return SERIAL;
        if (val.equals("fork")) return FORK;
        throw new Error();
    }

    /**
     * Usage: Integrate [procs=N] [reps=N] forkPolicy=serial|dynamic|fork
     */
    public static void main(String[] args) throws Exception {
        final int procs = intArg(args, "procs",
                                 Runtime.getRuntime().availableProcessors());
        final int forkPolicy = policyArg(args, "forkPolicy", DYNAMIC);

        ForkJoinPool g = new ForkJoinPool(procs);
        System.out.println("Integrating from " + start + " to " + end +
                           " forkPolicy = " + forkPolicy);
        long lastTime = System.nanoTime();

        for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {
            double a;
            if (forkPolicy == SERIAL)
                a = SQuad.computeArea(g, start, end);
            else if (forkPolicy == FORK)
                a = FQuad.computeArea(g, start, end);
            else
                a = DQuad.computeArea(g, start, end);
            long now = System.nanoTime();
            double s = (double) (now - lastTime) / NPS;
            lastTime = now;
            System.out.printf("Calls/sec: %12d", (long) (calls / s));
            System.out.printf(" Time: %7.3f", s);
            System.out.printf(" Area: %12.1f", a);
            System.out.println();
        }
        System.out.println(g);
        g.shutdown();
    }

    // Sequential version
    static final class SQuad extends RecursiveAction {
        static double computeArea(ForkJoinPool pool, double l, double r) {
            SQuad q = new SQuad(l, r, 0);
            pool.invoke(q);
            return q.area;
        }

        final double left;       // lower bound
        final double right;      // upper bound
        double area;

        SQuad(double l, double r, double a) {
            this.left = l; this.right = r; this.area = a;
        }

        public final void compute() {
            double l = left;
            double r = right;
            area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
        }

        static final double recEval(double l, double r, double fl,
                                    double fr, double a) {
            double h = (r - l) * 0.5;
            double c = l + h;
            double fc = (c * c + 1.0) * c;
            double hh = h * 0.5;
            double al = (fl + fc) * hh;
            double ar = (fr + fc) * hh;
            double alr = al + ar;
            if (Math.abs(alr - a) <= errorTolerance)
                return alr;
            else
                return recEval(c, r, fc, fr, ar) + recEval(l, c, fl, fc, al);
        }

    }

    //....................................

    // ForkJoin version
    static final class FQuad extends RecursiveAction {
        static double computeArea(ForkJoinPool pool, double l, double r) {
            FQuad q = new FQuad(l, r, 0);
            pool.invoke(q);
            return q.area;
        }

        final double left;       // lower bound
        final double right;      // upper bound
        double area;

        FQuad(double l, double r, double a) {
            this.left = l; this.right = r; this.area = a;
        }

        public final void compute() {
            double l = left;
            double r = right;
            area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
        }

        static final double recEval(double l, double r, double fl,
                                    double fr, double a) {
            double h = (r - l) * 0.5;
            double c = l + h;
            double fc = (c * c + 1.0) * c;
            double hh = h * 0.5;
            double al = (fl + fc) * hh;
            double ar = (fr + fc) * hh;
            double alr = al + ar;
            if (Math.abs(alr - a) <= errorTolerance)
                return alr;
            FQuad q = new FQuad(l, c, al);
            q.fork();
            ar = recEval(c, r, fc, fr, ar);
            if (!q.tryUnfork()) {
                q.quietlyJoin();
                return ar + q.area;
            }
            return ar + recEval(l, c, fl, fc, al);
        }

    }

    // ...........................

    // Version using on-demand Fork
    static final class DQuad extends RecursiveAction {
        static double computeArea(ForkJoinPool pool, double l, double r) {
            DQuad q = new DQuad(l, r, 0);
            pool.invoke(q);
            return q.area;
        }

        final double left;       // lower bound
        final double right;      // upper bound
        double area;

        DQuad(double l, double r, double a) {
            this.left = l; this.right = r; this.area = a;
        }

        public final void compute() {
            double l = left;
            double r = right;
            area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
        }

        static final double recEval(double l, double r, double fl,
                                    double fr, double a) {
            double h = (r - l) * 0.5;
            double c = l + h;
            double fc = (c * c + 1.0) * c;
            double hh = h * 0.5;
            double al = (fl + fc) * hh;
            double ar = (fr + fc) * hh;
            double alr = al + ar;
            if (Math.abs(alr - a) <= errorTolerance)
                return alr;
            DQuad q = null;
            if (getSurplusQueuedTaskCount() <= 3)
                (q = new DQuad(l, c, al)).fork();
            ar = recEval(c, r, fc, fr, ar);
            if (q != null && !q.tryUnfork()) {
                q.quietlyJoin();
                return ar + q.area;
            }
            return ar + recEval(l, c, fl, fc, al);
        }

    }

}
Revision:	1.5
Committed:	Mon Sep 14 16:47:43 2015 UTC (8 years, 8 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.4:	+0 -1 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/publicdomain/zero/1.0/
5	*/
6
7	/*
8	* @test
9	* @bug 6865571
10	* @summary Numerical Integration using fork/join
11	* @run main Integrate reps=1 forkPolicy=dynamic
12	* @run main Integrate reps=1 forkPolicy=serial
13	* @run main Integrate reps=1 forkPolicy=fork
14	*/
15
16	import java.util.concurrent.ForkJoinPool;
17	import java.util.concurrent.RecursiveAction;
18
19	/**
20	* Sample program using Gaussian Quadrature for numerical integration.
21	* This version uses a simplified hardwired function. Inspired by a
22	* <A href="http://www.cs.uga.edu/~dkl/filaments/dist.html">
23	* Filaments</A> demo program.
24	*/
25	public final class Integrate {
26
27	static final double errorTolerance = 1.0e-11;
28	/** for time conversion */
29	static final long NPS = (1000L * 1000 * 1000);
30
31	static final int SERIAL = -1;
32	static final int DYNAMIC = 0;
33	static final int FORK = 1;
34
35	/** the function to integrate */
36	static double computeFunction(double x) {
37	return (x * x + 1.0) * x;
38	}
39
40	static final double start = 0.0;
41	static final double end = 1536.0;
42
43	/**
44	* The number of recursive calls for
45	* integrate from start to end.
46	* (Empirically determined)
47	*/
48	static final int calls = 263479047;
49
50	static String keywordValue(String[] args, String keyword) {
51	for (String arg : args)
52	if (arg.startsWith(keyword))
53	return arg.substring(keyword.length() + 1);
54	return null;
55	}
56
57	static int intArg(String[] args, String keyword, int defaultValue) {
58	String val = keywordValue(args, keyword);
59	return (val == null) ? defaultValue : Integer.parseInt(val);
60	}
61
62	static int policyArg(String[] args, String keyword, int defaultPolicy) {
63	String val = keywordValue(args, keyword);
64	if (val == null) return defaultPolicy;
65	if (val.equals("dynamic")) return DYNAMIC;
66	if (val.equals("serial")) return SERIAL;
67	if (val.equals("fork")) return FORK;
68	throw new Error();
69	}
70
71	/**
72	* Usage: Integrate [procs=N] [reps=N] forkPolicy=serial\|dynamic\|fork
73	*/
74	public static void main(String[] args) throws Exception {
75	final int procs = intArg(args, "procs",
76	Runtime.getRuntime().availableProcessors());
77	final int forkPolicy = policyArg(args, "forkPolicy", DYNAMIC);
78
79	ForkJoinPool g = new ForkJoinPool(procs);
80	System.out.println("Integrating from " + start + " to " + end +
81	" forkPolicy = " + forkPolicy);
82	long lastTime = System.nanoTime();
83
84	for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {
85	double a;
86	if (forkPolicy == SERIAL)
87	a = SQuad.computeArea(g, start, end);
88	else if (forkPolicy == FORK)
89	a = FQuad.computeArea(g, start, end);
90	else
91	a = DQuad.computeArea(g, start, end);
92	long now = System.nanoTime();
93	double s = (double) (now - lastTime) / NPS;
94	lastTime = now;
95	System.out.printf("Calls/sec: %12d", (long) (calls / s));
96	System.out.printf(" Time: %7.3f", s);
97	System.out.printf(" Area: %12.1f", a);
98	System.out.println();
99	}
100	System.out.println(g);
101	g.shutdown();
102	}
103
104	// Sequential version
105	static final class SQuad extends RecursiveAction {
106	static double computeArea(ForkJoinPool pool, double l, double r) {
107	SQuad q = new SQuad(l, r, 0);
108	pool.invoke(q);
109	return q.area;
110	}
111
112	final double left; // lower bound
113	final double right; // upper bound
114	double area;
115
116	SQuad(double l, double r, double a) {
117	this.left = l; this.right = r; this.area = a;
118	}
119
120	public final void compute() {
121	double l = left;
122	double r = right;
123	area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
124	}
125
126	static final double recEval(double l, double r, double fl,
127	double fr, double a) {
128	double h = (r - l) * 0.5;
129	double c = l + h;
130	double fc = (c * c + 1.0) * c;
131	double hh = h * 0.5;
132	double al = (fl + fc) * hh;
133	double ar = (fr + fc) * hh;
134	double alr = al + ar;
135	if (Math.abs(alr - a) <= errorTolerance)
136	return alr;
137	else
138	return recEval(c, r, fc, fr, ar) + recEval(l, c, fl, fc, al);
139	}
140
141	}
142
143	//....................................
144
145	// ForkJoin version
146	static final class FQuad extends RecursiveAction {
147	static double computeArea(ForkJoinPool pool, double l, double r) {
148	FQuad q = new FQuad(l, r, 0);
149	pool.invoke(q);
150	return q.area;
151	}
152
153	final double left; // lower bound
154	final double right; // upper bound
155	double area;
156
157	FQuad(double l, double r, double a) {
158	this.left = l; this.right = r; this.area = a;
159	}
160
161	public final void compute() {
162	double l = left;
163	double r = right;
164	area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
165	}
166
167	static final double recEval(double l, double r, double fl,
168	double fr, double a) {
169	double h = (r - l) * 0.5;
170	double c = l + h;
171	double fc = (c * c + 1.0) * c;
172	double hh = h * 0.5;
173	double al = (fl + fc) * hh;
174	double ar = (fr + fc) * hh;
175	double alr = al + ar;
176	if (Math.abs(alr - a) <= errorTolerance)
177	return alr;
178	FQuad q = new FQuad(l, c, al);
179	q.fork();
180	ar = recEval(c, r, fc, fr, ar);
181	if (!q.tryUnfork()) {
182	q.quietlyJoin();
183	return ar + q.area;
184	}
185	return ar + recEval(l, c, fl, fc, al);
186	}
187
188	}
189
190	// ...........................
191
192	// Version using on-demand Fork
193	static final class DQuad extends RecursiveAction {
194	static double computeArea(ForkJoinPool pool, double l, double r) {
195	DQuad q = new DQuad(l, r, 0);
196	pool.invoke(q);
197	return q.area;
198	}
199
200	final double left; // lower bound
201	final double right; // upper bound
202	double area;
203
204	DQuad(double l, double r, double a) {
205	this.left = l; this.right = r; this.area = a;
206	}
207
208	public final void compute() {
209	double l = left;
210	double r = right;
211	area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
212	}
213
214	static final double recEval(double l, double r, double fl,
215	double fr, double a) {
216	double h = (r - l) * 0.5;
217	double c = l + h;
218	double fc = (c * c + 1.0) * c;
219	double hh = h * 0.5;
220	double al = (fl + fc) * hh;
221	double ar = (fr + fc) * hh;
222	double alr = al + ar;
223	if (Math.abs(alr - a) <= errorTolerance)
224	return alr;
225	DQuad q = null;
226	if (getSurplusQueuedTaskCount() <= 3)
227	(q = new DQuad(l, c, al)).fork();
228	ar = recEval(c, r, fc, fr, ar);
229	if (q != null && !q.tryUnfork()) {
230	q.quietlyJoin();
231	return ar + q.area;
232	}
233	return ar + recEval(l, c, fl, fc, al);
234	}
235
236	}
237
238	}