test/loops/FibTask.java

import java.util.concurrent.*;

/**
 * Recursive task-based version of Fibonacci. Computes:
 * <pre>
 * Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);  for n> 1
 *          fibonacci(0) = 0; 
 *          fibonacci(1) = 1.       
 * </pre>
 **/

public final class FibTask extends RecursiveTask<Integer> {

    // Performance-tuning constant:
    static int sequentialThreshold;

    static long lastStealCount;
  
    public static void main(String[] args) throws Exception {
        int procs = 0;
        int num = 45;
        sequentialThreshold = 2;
        try {
            if (args.length > 0)
                procs = Integer.parseInt(args[0]);
            if (args.length > 1)
                num = Integer.parseInt(args[1]);
            if (args.length > 2) 
                sequentialThreshold = Integer.parseInt(args[2]);
        }
        catch (Exception e) {
            System.out.println("Usage: java Fib <threads> <number> [<sequentialThreshold>]");
            return;
        }

        for (int reps = 0; reps < 2; ++reps) {
            ForkJoinPool g = procs == 0? new ForkJoinPool() : 
                new ForkJoinPool(procs);
            lastStealCount = g.getStealCount();
            for (int i = 0; i < 20; ++i) {
                test(g, num);
                //            Thread.sleep(1000);
            }
            System.out.println(g);
            g.shutdown();
        }
    }


    /** for time conversion */
    static final long NPS = (1000L * 1000 * 1000);

    static void test(ForkJoinPool g, int num) throws Exception {
        int ps = g.getParallelism();
        long start = System.nanoTime();
        int result = g.invoke(new FibTask(num));
        long time = System.nanoTime() - start;
        double secs = ((double)time) / NPS;
        System.out.print("FibTask " + num + " = " + result);
        System.out.printf("\tTime: %7.3f", secs);
       
        long sc = g.getStealCount();
        long ns = sc - lastStealCount;
        lastStealCount = sc;
        System.out.printf(" Steals/t: %5d", ns/ps);
        System.out.printf(" Workers: %5d", g.getPoolSize());
        System.out.println();
    }


    // Initialized with argument; replaced with result
    int number;

    FibTask(int n) { number = n; }

    public Integer compute() {
        int n = number;

        // Handle base cases:
        if (n <= 1) {
            return n;
        }
        // Use sequential code for small problems:
        else if (n <= sequentialThreshold) {
            return seqFib(n);
        }
        // Otherwise use recursive parallel decomposition:
        else {
            FibTask f1 = new FibTask(n - 1);
            f1.fork();
            FibTask f2 = new FibTask(n - 2);
            return f2.compute() + f1.join(); 
        }
    }

    // Sequential version for arguments less than threshold
    static final int seqFib(int n) { // unroll left only
        int r = 1;
        do {
            int m = n - 2;
            r += m <= 1 ? m : seqFib(m);
        } while (--n > 1);
        return r;
    }
}

Revision:	1.1
Committed:	Sun Sep 19 12:55:37 2010 UTC (13 years, 8 months ago) by dl
Branch:	MAIN
Log Message:	Add and update FJ and Queue tests
#	User	Rev	Content
1	dl	1.1	import java.util.concurrent.*;
2
3			/**
4			* Recursive task-based version of Fibonacci. Computes:
5			* <pre>
6			* Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2); for n> 1
7			* fibonacci(0) = 0;
8			* fibonacci(1) = 1.
9			* </pre>
10			**/
11
12			public final class FibTask extends RecursiveTask<Integer> {
13
14			// Performance-tuning constant:
15			static int sequentialThreshold;
16
17			static long lastStealCount;
18
19			public static void main(String[] args) throws Exception {
20			int procs = 0;
21			int num = 45;
22			sequentialThreshold = 2;
23			try {
24			if (args.length > 0)
25			procs = Integer.parseInt(args[0]);
26			if (args.length > 1)
27			num = Integer.parseInt(args[1]);
28			if (args.length > 2)
29			sequentialThreshold = Integer.parseInt(args[2]);
30			}
31			catch (Exception e) {
32			System.out.println("Usage: java Fib <threads> <number> [<sequentialThreshold>]");
33			return;
34			}
35
36			for (int reps = 0; reps < 2; ++reps) {
37			ForkJoinPool g = procs == 0? new ForkJoinPool() :
38			new ForkJoinPool(procs);
39			lastStealCount = g.getStealCount();
40			for (int i = 0; i < 20; ++i) {
41			test(g, num);
42			// Thread.sleep(1000);
43			}
44			System.out.println(g);
45			g.shutdown();
46			}
47			}
48
49
50			/** for time conversion */
51			static final long NPS = (1000L * 1000 * 1000);
52
53			static void test(ForkJoinPool g, int num) throws Exception {
54			int ps = g.getParallelism();
55			long start = System.nanoTime();
56			int result = g.invoke(new FibTask(num));
57			long time = System.nanoTime() - start;
58			double secs = ((double)time) / NPS;
59			System.out.print("FibTask " + num + " = " + result);
60			System.out.printf("\tTime: %7.3f", secs);
61
62			long sc = g.getStealCount();
63			long ns = sc - lastStealCount;
64			lastStealCount = sc;
65			System.out.printf(" Steals/t: %5d", ns/ps);
66			System.out.printf(" Workers: %5d", g.getPoolSize());
67			System.out.println();
68			}
69
70
71			// Initialized with argument; replaced with result
72			int number;
73
74			FibTask(int n) { number = n; }
75
76			public Integer compute() {
77			int n = number;
78
79			// Handle base cases:
80			if (n <= 1) {
81			return n;
82			}
83			// Use sequential code for small problems:
84			else if (n <= sequentialThreshold) {
85			return seqFib(n);
86			}
87			// Otherwise use recursive parallel decomposition:
88			else {
89			FibTask f1 = new FibTask(n - 1);
90			f1.fork();
91			FibTask f2 = new FibTask(n - 2);
92			return f2.compute() + f1.join();
93			}
94			}
95
96			// Sequential version for arguments less than threshold
97			static final int seqFib(int n) { // unroll left only
98			int r = 1;
99			do {
100			int m = n - 2;
101			r += m <= 1 ? m : seqFib(m);
102			} while (--n > 1);
103			return r;
104			}
105			}
106