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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    19  * CA 95054 USA or visit www.sun.com if you need additional information or

    20  * have any 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/licenses/publicdomain

    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

    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      * The number of recursive calls for

    71      * integrate from start to end.

    72      * (Empirically determined)

    73      */

    74     static final int calls = 263479047;

    75 

    76     static String keywordValue(String[] args, String keyword) {

    77         for (String arg : args)

    78             if (arg.startsWith(keyword))

    79                 return arg.substring(keyword.length() + 1);

    80         return null;

    81     }

    82 

    83     static int intArg(String[] args, String keyword, int defaultValue) {

    84         String val = keywordValue(args, keyword);

    85         return (val == null) ? defaultValue : Integer.parseInt(val);

    86     }

    87 

    88     static int policyArg(String[] args, String keyword, int defaultPolicy) {

    89         String val = keywordValue(args, keyword);

    90         if (val == null) return defaultPolicy;

    91         if (val.equals("dynamic")) return DYNAMIC;

    92         if (val.equals("serial")) return SERIAL;

    93         if (val.equals("fork")) return FORK;

    94         throw new Error();

    95     }

    96 

    97     /**

    98      * Usage: Integrate [procs=N] [reps=N] forkPolicy=serial|dynamic|fork

    99      */

   100     public static void main(String[] args) throws Exception {

   101         final int procs = intArg(args, "procs",

   102                                  Runtime.getRuntime().availableProcessors());

   103         final int forkPolicy = policyArg(args, "forkPolicy", DYNAMIC);

   104 

   105         ForkJoinPool g = new ForkJoinPool(procs);

   106         System.out.println("Integrating from " + start + " to " + end +

   107                            " forkPolicy = " + forkPolicy);

   108         long lastTime = System.nanoTime();

   109 

   110         for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {

   111             double a;

   112             if (forkPolicy == SERIAL)

   113                 a = SQuad.computeArea(g, start, end);

   114             else if (forkPolicy == FORK)

   115                 a = FQuad.computeArea(g, start, end);

   116             else

   117                 a = DQuad.computeArea(g, start, end);

   118             long now = System.nanoTime();

   119             double s = (double) (now - lastTime) / NPS;

   120             lastTime = now;

   121             System.out.printf("Calls/sec: %12d", (long) (calls / s));

   122             System.out.printf(" Time: %7.3f", s);

   123             System.out.printf(" Area: %12.1f", a);

   124             System.out.println();

   125         }

   126         System.out.println(g);

   127         g.shutdown();

   128     }

   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.quietlyHelpJoin();

   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.quietlyHelpJoin();

   258                 return ar + q.area;

   259             }

   260             return ar + recEval(l, c, fl, fc, al);

   261         }

   262 

   263     }

   264 

   265 }