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 
43 import java.util.concurrent.ForkJoinPool;
44 import 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  */
52 public 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 */
computeFunction(double x)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 
keywordValue(String[] args, String keyword)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 
intArg(String[] args, String keyword, int defaultValue)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 
policyArg(String[] args, String keyword, int defaultPolicy)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      */
main(String[] args)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 {
computeArea(ForkJoinPool pool, double l, double r)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 
SQuad(double l, double r, double a)143         SQuad(double l, double r, double a) {
144             this.left = l; this.right = r; this.area = a;
145         }
146 
compute()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 
recEval(double l, double r, double fl, double fr, double a)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 {
computeArea(ForkJoinPool pool, double l, double r)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 
FQuad(double l, double r, double a)184         FQuad(double l, double r, double a) {
185             this.left = l; this.right = r; this.area = a;
186         }
187 
compute()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 
recEval(double l, double r, double fl, double fr, double a)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 {
computeArea(ForkJoinPool pool, double l, double r)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 
DQuad(double l, double r, double a)231         DQuad(double l, double r, double a) {
232             this.left = l; this.right = r; this.area = a;
233         }
234 
compute()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 
recEval(double l, double r, double fl, double fr, double a)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