1/*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 */
22
23/*
24 * This file is available under and governed by the GNU General Public
25 * License version 2 only, as published by the Free Software Foundation.
26 * However, the following notice accompanied the original version of this
27 * file:
28 *
29 * Written by Doug Lea with assistance from members of JCP JSR-166
30 * Expert Group and released to the public domain, as explained at
31 * http://creativecommons.org/publicdomain/zero/1.0/
32 */
33
34/*
35 * @test
36 * @bug 6865571
37 * @summary Numerical Integration using fork/join
38 * @run main Integrate reps=1 forkPolicy=dynamic
39 * @run main Integrate reps=1 forkPolicy=serial
40 * @run main Integrate reps=1 forkPolicy=fork
41 */
42
43import java.util.concurrent.ForkJoinPool;
44import java.util.concurrent.RecursiveAction;
45
46/**
47 * Sample program using Gaussian Quadrature for numerical integration.
48 * This version uses a simplified hardwired function.  Inspired by a
49 * <A href="http://www.cs.uga.edu/~dkl/filaments/dist.html">
50 * Filaments</A> demo program.
51 */
52public final class Integrate {
53
54    static final double errorTolerance = 1.0e-11;
55    /** for time conversion */
56    static final long NPS = (1000L * 1000 * 1000);
57
58    static final int SERIAL = -1;
59    static final int DYNAMIC = 0;
60    static final int FORK = 1;
61
62    /** the function to integrate */
63    static double computeFunction(double x) {
64        return (x * x + 1.0) * x;
65    }
66
67    static final double start = 0.0;
68    static final double end = 1536.0;
69
70    /**
71     * The number of recursive calls for
72     * integrate from start to end.
73     * (Empirically determined)
74     */
75    static final int calls = 263479047;
76
77    static String keywordValue(String[] args, String keyword) {
78        for (String arg : args)
79            if (arg.startsWith(keyword))
80                return arg.substring(keyword.length() + 1);
81        return null;
82    }
83
84    static int intArg(String[] args, String keyword, int defaultValue) {
85        String val = keywordValue(args, keyword);
86        return (val == null) ? defaultValue : Integer.parseInt(val);
87    }
88
89    static int policyArg(String[] args, String keyword, int defaultPolicy) {
90        String val = keywordValue(args, keyword);
91        if (val == null) return defaultPolicy;
92        if (val.equals("dynamic")) return DYNAMIC;
93        if (val.equals("serial")) return SERIAL;
94        if (val.equals("fork")) return FORK;
95        throw new Error();
96    }
97
98    /**
99     * Usage: Integrate [procs=N] [reps=N] forkPolicy=serial|dynamic|fork
100     */
101    public static void main(String[] args) throws Exception {
102        final int procs = intArg(args, "procs",
103                                 Runtime.getRuntime().availableProcessors());
104        final int forkPolicy = policyArg(args, "forkPolicy", DYNAMIC);
105
106        ForkJoinPool g = new ForkJoinPool(procs);
107        System.out.println("Integrating from " + start + " to " + end +
108                           " forkPolicy = " + forkPolicy);
109        long lastTime = System.nanoTime();
110
111        for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {
112            double a;
113            if (forkPolicy == SERIAL)
114                a = SQuad.computeArea(g, start, end);
115            else if (forkPolicy == FORK)
116                a = FQuad.computeArea(g, start, end);
117            else
118                a = DQuad.computeArea(g, start, end);
119            long now = System.nanoTime();
120            double s = (double) (now - lastTime) / NPS;
121            lastTime = now;
122            System.out.printf("Calls/sec: %12d", (long) (calls / s));
123            System.out.printf(" Time: %7.3f", s);
124            System.out.printf(" Area: %12.1f", a);
125            System.out.println();
126        }
127        System.out.println(g);
128        g.shutdown();
129    }
130
131    // Sequential version
132    static final class SQuad extends RecursiveAction {
133        static double computeArea(ForkJoinPool pool, double l, double r) {
134            SQuad q = new SQuad(l, r, 0);
135            pool.invoke(q);
136            return q.area;
137        }
138
139        final double left;       // lower bound
140        final double right;      // upper bound
141        double area;
142
143        SQuad(double l, double r, double a) {
144            this.left = l; this.right = r; this.area = a;
145        }
146
147        public final void compute() {
148            double l = left;
149            double r = right;
150            area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
151        }
152
153        static final double recEval(double l, double r, double fl,
154                                    double fr, double a) {
155            double h = (r - l) * 0.5;
156            double c = l + h;
157            double fc = (c * c + 1.0) * c;
158            double hh = h * 0.5;
159            double al = (fl + fc) * hh;
160            double ar = (fr + fc) * hh;
161            double alr = al + ar;
162            if (Math.abs(alr - a) <= errorTolerance)
163                return alr;
164            else
165                return recEval(c, r, fc, fr, ar) + recEval(l, c, fl, fc, al);
166        }
167
168    }
169
170    //....................................
171
172    // ForkJoin version
173    static final class FQuad extends RecursiveAction {
174        static double computeArea(ForkJoinPool pool, double l, double r) {
175            FQuad q = new FQuad(l, r, 0);
176            pool.invoke(q);
177            return q.area;
178        }
179
180        final double left;       // lower bound
181        final double right;      // upper bound
182        double area;
183
184        FQuad(double l, double r, double a) {
185            this.left = l; this.right = r; this.area = a;
186        }
187
188        public final void compute() {
189            double l = left;
190            double r = right;
191            area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
192        }
193
194        static final double recEval(double l, double r, double fl,
195                                    double fr, double a) {
196            double h = (r - l) * 0.5;
197            double c = l + h;
198            double fc = (c * c + 1.0) * c;
199            double hh = h * 0.5;
200            double al = (fl + fc) * hh;
201            double ar = (fr + fc) * hh;
202            double alr = al + ar;
203            if (Math.abs(alr - a) <= errorTolerance)
204                return alr;
205            FQuad q = new FQuad(l, c, al);
206            q.fork();
207            ar = recEval(c, r, fc, fr, ar);
208            if (!q.tryUnfork()) {
209                q.quietlyJoin();
210                return ar + q.area;
211            }
212            return ar + recEval(l, c, fl, fc, al);
213        }
214
215    }
216
217    // ...........................
218
219    // Version using on-demand Fork
220    static final class DQuad extends RecursiveAction {
221        static double computeArea(ForkJoinPool pool, double l, double r) {
222            DQuad q = new DQuad(l, r, 0);
223            pool.invoke(q);
224            return q.area;
225        }
226
227        final double left;       // lower bound
228        final double right;      // upper bound
229        double area;
230
231        DQuad(double l, double r, double a) {
232            this.left = l; this.right = r; this.area = a;
233        }
234
235        public final void compute() {
236            double l = left;
237            double r = right;
238            area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
239        }
240
241        static final double recEval(double l, double r, double fl,
242                                    double fr, double a) {
243            double h = (r - l) * 0.5;
244            double c = l + h;
245            double fc = (c * c + 1.0) * c;
246            double hh = h * 0.5;
247            double al = (fl + fc) * hh;
248            double ar = (fr + fc) * hh;
249            double alr = al + ar;
250            if (Math.abs(alr - a) <= errorTolerance)
251                return alr;
252            DQuad q = null;
253            if (getSurplusQueuedTaskCount() <= 3)
254                (q = new DQuad(l, c, al)).fork();
255            ar = recEval(c, r, fc, fr, ar);
256            if (q != null && !q.tryUnfork()) {
257                q.quietlyJoin();
258                return ar + q.area;
259            }
260            return ar + recEval(l, c, fl, fc, al);
261        }
262
263    }
264
265}
266