test/loops/TorusSpanningTree.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

//import jsr166y.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

/**
 * This is reworked version of one of the tests reported on in the
 * paper: Guojing Cong, Sreedhar Kodali, Sriram Krishnamoorty, Doug
 * Lea, Vijay Saraswat and Tong Wen, "Solving irregular graph problems
 * using adaptive work-stealing", ICPP, 2008.
 *
 * It runs the main batching algorithm discussed there for spanning
 * trees, for a simple regular torus graph, where each node is
 * connected to its left. right, up, and down neighbors.
 */
public class TorusSpanningTree {
    static final int NCPUS = Runtime.getRuntime().availableProcessors();

    // Dimensions for test runs.
    // graphs have side*side nodes, each with 4 neighbors
    static final int MIN_SIDE = 1000;
    static final int MAX_SIDE = 3000;
    static final int SIDE_STEP = 500;

    public static void main(String[] args) throws Exception {
        Random rng = new Random();
        int procs = NCPUS;
        try {
            if (args.length > 0)
                procs = Integer.parseInt(args[0]);
        }
        catch (Exception e) {
            System.out.println("Usage: java TorusSpanningTree <threads>");
            return;
        }
        System.out.println("Number of threads: " + procs);
        System.out.println("Printing nanosec per edge across replications");
        System.out.print("for Toruses with side lengths");
        System.out.printf(" from %5d to %5d step %5d\n",
                          MIN_SIDE, MAX_SIDE, SIDE_STEP);
        ForkJoinPool pool = new ForkJoinPool(procs);

        for (int side = MIN_SIDE; side <= MAX_SIDE; side += SIDE_STEP) {
            int n = side * side;
            Node[] graph = makeGraph(side);
            System.out.printf( "N:%9d", n);
            for (int j = 0; j < 8; ++j) {
                Node root = graph[rng.nextInt(n)];
                long start = System.nanoTime();
                pool.invoke(new Driver(root));
                long elapsed = System.nanoTime() - start;
                double nanosPerEdge = (double)elapsed / (4 * n);
                System.out.printf(" %7.2f", nanosPerEdge);
                if (j == 0)
                    checkSpanningTree(graph, root);
                resetAll(graph);
            }
            System.out.println();
        }
        pool.shutdown();
    }

    static final class Node extends ForkJoinTask<Void> {
        final Node[] neighbors;
        Node parent;
        Node next;
        volatile int mark;

        Node(Node[] nbrs) {
            neighbors = nbrs;
            parent = this;
        }

        static final AtomicIntegerFieldUpdater<Node> markUpdater =
            AtomicIntegerFieldUpdater.newUpdater(Node.class, "mark");

        boolean tryMark() {
            return mark == 0 && markUpdater.compareAndSet(this, 0, 1);
        }
        void setMark() { mark = 1; }

        /*
         * Traverse the list ("oldList") embedded across .next fields,
         * starting at this node, placing newly discovered neighboring
         * nodes in newList. If the oldList becomes exhausted, swap in
         * newList and continue. Otherwise, whenever the length of
         * newList exceeds current number of tasks in work-stealing
         * queue, push list onto queue.
         */

        static final int LOG_MAX_BATCH_SIZE = 7;

        /**
         * Since tasks are never joined, we bypass Recursive{Action,Task}
         * and just directly implement exec
         */
        public boolean exec() {
            int batchSize = 0; // computed lazily
            Node newList = null;
            int newLength = 0;
            Node oldList = this;
            Node par = parent;
            do {
                Node v = oldList;
                Node[] edges = v.neighbors;
                oldList = v.next;
                int nedges = edges.length;
                for (int k = 0; k < nedges; ++k) {
                    Node e = edges[k];
                    if (e != null && e.tryMark()) {
                        e.parent = par;
                        e.next = newList;
                        newList = e;
                        if (batchSize == 0) {
                            int s = getQueuedTaskCount();
                            batchSize = ((s >= LOG_MAX_BATCH_SIZE)?
                                         (1 << LOG_MAX_BATCH_SIZE) :
                                         (1 << s));
                        }
                        if (++newLength >= batchSize) {
                            newLength = 0;
                            batchSize = 0;
                            if (oldList == null)
                                oldList = newList;
                            else
                                newList.fork();
                            newList = null;
                        }
                    }
                }
                if (oldList == null) {
                    oldList = newList;
                    newList = null;
                    newLength = 0;
                }
            } while (oldList != null);
            return false;
        }

        // required abstract implementations for ForkJoinTask
        public final Void getRawResult() { return null; }
        protected final void setRawResult(Void mustBeNull) { }

        public void reset() {
            reinitialize();
            parent = this;
            next = null;
            mark = 0;
        }

    }

    static final class Driver extends RecursiveAction {
        final Node root;
        Driver(Node root) {
            this.root = root;
        }
        public void compute() {
            root.setMark();
            root.fork();
            helpQuiesce();
        }
    }

    static Node[] makeGraph(int sideLength) {
        int n = sideLength * sideLength;
        Node[] vs = new Node[n];
        for (int i = 0; i < n; ++i)
            vs[i] = new Node(new Node[4]);

        // connect each node to left, right, up, down neighbors
        int maxcol = n - sideLength;
        int col = 0;
        for(int i = 0; i < sideLength; ++i) {
            for(int j = 0; j < sideLength; ++j) {
                Node[] a = vs[col + j].neighbors;
                a[0] = vs[col + ((j < sideLength-1)? (j+1) : 0)];
                a[1] = vs[col + ((j != 0)? (j-1) : (sideLength-1))];
                a[2] = vs[j + ((i < sideLength-1)? (col + sideLength) : 0)];
                a[3] = vs[j + ((i != 0)? (col - sideLength) : maxcol)];
            }
            col += sideLength;
        }
        return vs;
    }

    static void resetAll(Node[] g) {
        for (int i = 0; i < g.length; ++i)
            g[i].reset();
    }

    // check that all nodes have parents, and no cycles
    static void checkSpanningTree(Node[] g, Node root) {
        int n = g.length;
        for (int i = 0; i < n; ++i) {
            Node v = g[i];
            Node p = v;
            int k = n;
            while (p != root) {
                if (p == null)
                    throw new RuntimeException("null parent");
                if (--k <= 0)
                    throw new RuntimeException("cycle");
                p = p.parent;
            }
            v.parent = root;
        }
    }

}
Revision:	1.2
Committed:	Mon Nov 2 20:23:53 2009 UTC (14 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.1:	+10 -11 lines
Log Message:	whitespace
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/licenses/publicdomain
5			*/
6
7			//import jsr166y.*;
8			import java.util.*;
9			import java.util.concurrent.*;
10			import java.util.concurrent.atomic.*;
11
12			/**
13			* This is reworked version of one of the tests reported on in the
14			* paper: Guojing Cong, Sreedhar Kodali, Sriram Krishnamoorty, Doug
15			* Lea, Vijay Saraswat and Tong Wen, "Solving irregular graph problems
16			* using adaptive work-stealing", ICPP, 2008.
17	jsr166	1.2	*
18	dl	1.1	* It runs the main batching algorithm discussed there for spanning
19			* trees, for a simple regular torus graph, where each node is
20			* connected to its left. right, up, and down neighbors.
21			*/
22			public class TorusSpanningTree {
23			static final int NCPUS = Runtime.getRuntime().availableProcessors();
24
25	jsr166	1.2	// Dimensions for test runs.
26	dl	1.1	// graphs have side*side nodes, each with 4 neighbors
27			static final int MIN_SIDE = 1000;
28			static final int MAX_SIDE = 3000;
29			static final int SIDE_STEP = 500;
30
31			public static void main(String[] args) throws Exception {
32			Random rng = new Random();
33			int procs = NCPUS;
34			try {
35			if (args.length > 0)
36			procs = Integer.parseInt(args[0]);
37			}
38			catch (Exception e) {
39			System.out.println("Usage: java TorusSpanningTree <threads>");
40			return;
41			}
42			System.out.println("Number of threads: " + procs);
43			System.out.println("Printing nanosec per edge across replications");
44			System.out.print("for Toruses with side lengths");
45	jsr166	1.2	System.out.printf(" from %5d to %5d step %5d\n",
46	dl	1.1	MIN_SIDE, MAX_SIDE, SIDE_STEP);
47			ForkJoinPool pool = new ForkJoinPool(procs);
48
49			for (int side = MIN_SIDE; side <= MAX_SIDE; side += SIDE_STEP) {
50			int n = side * side;
51			Node[] graph = makeGraph(side);
52			System.out.printf( "N:%9d", n);
53			for (int j = 0; j < 8; ++j) {
54			Node root = graph[rng.nextInt(n)];
55			long start = System.nanoTime();
56			pool.invoke(new Driver(root));
57			long elapsed = System.nanoTime() - start;
58			double nanosPerEdge = (double)elapsed / (4 * n);
59			System.out.printf(" %7.2f", nanosPerEdge);
60			if (j == 0)
61			checkSpanningTree(graph, root);
62			resetAll(graph);
63			}
64			System.out.println();
65	jsr166	1.2	}
66			pool.shutdown();
67	dl	1.1	}
68
69			static final class Node extends ForkJoinTask<Void> {
70	jsr166	1.2	final Node[] neighbors;
71	dl	1.1	Node parent;
72			Node next;
73			volatile int mark;
74	jsr166	1.2
75	dl	1.1	Node(Node[] nbrs) {
76			neighbors = nbrs;
77			parent = this;
78			}
79
80			static final AtomicIntegerFieldUpdater<Node> markUpdater =
81			AtomicIntegerFieldUpdater.newUpdater(Node.class, "mark");
82
83			boolean tryMark() {
84			return mark == 0 && markUpdater.compareAndSet(this, 0, 1);
85			}
86			void setMark() { mark = 1; }
87
88			/*
89			* Traverse the list ("oldList") embedded across .next fields,
90			* starting at this node, placing newly discovered neighboring
91			* nodes in newList. If the oldList becomes exhausted, swap in
92			* newList and continue. Otherwise, whenever the length of
93			* newList exceeds current number of tasks in work-stealing
94			* queue, push list onto queue.
95			*/
96
97			static final int LOG_MAX_BATCH_SIZE = 7;
98
99			/**
100			* Since tasks are never joined, we bypass Recursive{Action,Task}
101			* and just directly implement exec
102			*/
103			public boolean exec() {
104			int batchSize = 0; // computed lazily
105			Node newList = null;
106			int newLength = 0;
107			Node oldList = this;
108			Node par = parent;
109			do {
110			Node v = oldList;
111			Node[] edges = v.neighbors;
112			oldList = v.next;
113			int nedges = edges.length;
114			for (int k = 0; k < nedges; ++k) {
115			Node e = edges[k];
116			if (e != null && e.tryMark()) {
117			e.parent = par;
118			e.next = newList;
119			newList = e;
120			if (batchSize == 0) {
121			int s = getQueuedTaskCount();
122	jsr166	1.2	batchSize = ((s >= LOG_MAX_BATCH_SIZE)?
123	dl	1.1	(1 << LOG_MAX_BATCH_SIZE) :
124			(1 << s));
125			}
126			if (++newLength >= batchSize) {
127			newLength = 0;
128			batchSize = 0;
129			if (oldList == null)
130			oldList = newList;
131			else
132			newList.fork();
133			newList = null;
134			}
135			}
136			}
137			if (oldList == null) {
138			oldList = newList;
139			newList = null;
140			newLength = 0;
141			}
142			} while (oldList != null);
143			return false;
144			}
145
146			// required abstract implementations for ForkJoinTask
147			public final Void getRawResult() { return null; }
148			protected final void setRawResult(Void mustBeNull) { }
149
150			public void reset() {
151			reinitialize();
152			parent = this;
153			next = null;
154			mark = 0;
155			}
156
157			}
158
159			static final class Driver extends RecursiveAction {
160			final Node root;
161	jsr166	1.2	Driver(Node root) {
162	dl	1.1	this.root = root;
163			}
164			public void compute() {
165			root.setMark();
166			root.fork();
167			helpQuiesce();
168			}
169			}
170
171			static Node[] makeGraph(int sideLength) {
172			int n = sideLength * sideLength;
173			Node[] vs = new Node[n];
174			for (int i = 0; i < n; ++i)
175			vs[i] = new Node(new Node[4]);
176
177			// connect each node to left, right, up, down neighbors
178			int maxcol = n - sideLength;
179			int col = 0;
180			for(int i = 0; i < sideLength; ++i) {
181			for(int j = 0; j < sideLength; ++j) {
182			Node[] a = vs[col + j].neighbors;
183			a[0] = vs[col + ((j < sideLength-1)? (j+1) : 0)];
184			a[1] = vs[col + ((j != 0)? (j-1) : (sideLength-1))];
185			a[2] = vs[j + ((i < sideLength-1)? (col + sideLength) : 0)];
186			a[3] = vs[j + ((i != 0)? (col - sideLength) : maxcol)];
187			}
188			col += sideLength;
189			}
190			return vs;
191			}
192
193			static void resetAll(Node[] g) {
194			for (int i = 0; i < g.length; ++i)
195			g[i].reset();
196			}
197
198			// check that all nodes have parents, and no cycles
199			static void checkSpanningTree(Node[] g, Node root) {
200			int n = g.length;
201			for (int i = 0; i < n; ++i) {
202			Node v = g[i];
203			Node p = v;
204			int k = n;
205			while (p != root) {
206			if (p == null)
207			throw new RuntimeException("null parent");
208			if (--k <= 0)
209			throw new RuntimeException("cycle");
210			p = p.parent;
211			}
212			v.parent = root;
213			}
214			}
215	jsr166	1.2
216	dl	1.1	}