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.2
Committed:	Mon Sep 20 20:42:37 2010 UTC (13 years, 7 months ago) by jsr166
Branch:	MAIN
Changes since 1.1:	+7 -7 lines
Log Message:	whitespace
#	Content
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