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/publicdomain/zero/1.0/
 */

//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);

        boolean checked = false;
        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 (!checked) {
                    checked = true;
                    checkSpanningTree(graph, root);
                }
                pool.invoke(new Resetter(graph, 0, graph.length));
            }
            System.out.println();
        }
        System.out.println(pool);
        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;
        }
    }

    static final class Resetter extends RecursiveAction {
        final Node[] g;
        final int lo, hi;
        Resetter(Node[] g, int lo, int hi) {
            this.g = g; this.lo = lo; this.hi = hi;
        }
        public void compute() {
            int mid = (lo + hi) >>> 1;
            if (mid == lo || getSurplusQueuedTaskCount() > 3) {
                for (int i = lo; i < hi; ++i)
                    g[i].reset();
            }
            else
                invokeAll(new Resetter(g, lo, mid), new Resetter(g, mid, hi));
        }
    }
}
Revision:	1.8
Committed:	Tue Mar 15 19:47:06 2011 UTC (13 years, 2 months ago) by jsr166
Branch:	MAIN
CVS Tags:	release-1_7_0
Changes since 1.7:	+1 -1 lines
Log Message:	Update Creative Commons license URL in legal notices
#	Content
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/publicdomain/zero/1.0/
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	*
18	* 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	// Dimensions for test runs.
26	// 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	System.out.printf(" from %5d to %5d step %5d\n",
46	MIN_SIDE, MAX_SIDE, SIDE_STEP);
47	ForkJoinPool pool = new ForkJoinPool(procs);
48
49	boolean checked = false;
50	for (int side = MIN_SIDE; side <= MAX_SIDE; side += SIDE_STEP) {
51	int n = side * side;
52	Node[] graph = makeGraph(side);
53	System.out.printf( "N:%9d", n);
54	for (int j = 0; j < 8; ++j) {
55	Node root = graph[rng.nextInt(n)];
56	long start = System.nanoTime();
57	pool.invoke(new Driver(root));
58	long elapsed = System.nanoTime() - start;
59	double nanosPerEdge = (double) elapsed / (4 * n);
60	System.out.printf(" %7.2f", nanosPerEdge);
61	if (!checked) {
62	checked = true;
63	checkSpanningTree(graph, root);
64	}
65	pool.invoke(new Resetter(graph, 0, graph.length));
66	}
67	System.out.println();
68	}
69	System.out.println(pool);
70	pool.shutdown();
71	}
72
73	static final class Node extends ForkJoinTask<Void> {
74	final Node[] neighbors;
75	Node parent;
76	Node next;
77	volatile int mark;
78
79	Node(Node[] nbrs) {
80	neighbors = nbrs;
81	parent = this;
82	}
83
84	static final AtomicIntegerFieldUpdater<Node> markUpdater =
85	AtomicIntegerFieldUpdater.newUpdater(Node.class, "mark");
86
87	boolean tryMark() {
88	return mark == 0 && markUpdater.compareAndSet(this, 0, 1);
89	}
90	void setMark() { mark = 1; }
91
92	/*
93	* Traverse the list ("oldList") embedded across .next fields,
94	* starting at this node, placing newly discovered neighboring
95	* nodes in newList. If the oldList becomes exhausted, swap in
96	* newList and continue. Otherwise, whenever the length of
97	* newList exceeds current number of tasks in work-stealing
98	* queue, push list onto queue.
99	*/
100
101	static final int LOG_MAX_BATCH_SIZE = 7;
102
103	/**
104	* Since tasks are never joined, we bypass Recursive{Action,Task}
105	* and just directly implement exec
106	*/
107	public boolean exec() {
108	int batchSize = 0; // computed lazily
109	Node newList = null;
110	int newLength = 0;
111	Node oldList = this;
112	Node par = parent;
113	do {
114	Node v = oldList;
115	Node[] edges = v.neighbors;
116	oldList = v.next;
117	int nedges = edges.length;
118	for (int k = 0; k < nedges; ++k) {
119	Node e = edges[k];
120	if (e != null && e.tryMark()) {
121	e.parent = par;
122	e.next = newList;
123	newList = e;
124	if (batchSize == 0) {
125	int s = getQueuedTaskCount();
126	batchSize = ((s >= LOG_MAX_BATCH_SIZE) ?
127	(1 << LOG_MAX_BATCH_SIZE) :
128	(1 << s));
129	}
130	if (++newLength >= batchSize) {
131	newLength = 0;
132	batchSize = 0;
133	if (oldList == null)
134	oldList = newList;
135	else
136	newList.fork();
137	newList = null;
138	}
139	}
140	}
141	if (oldList == null) {
142	oldList = newList;
143	newList = null;
144	newLength = 0;
145	}
146	} while (oldList != null);
147	return false;
148	}
149
150	// required abstract implementations for ForkJoinTask
151	public final Void getRawResult() { return null; }
152	protected final void setRawResult(Void mustBeNull) { }
153
154	public void reset() {
155	reinitialize();
156	parent = this;
157	next = null;
158	mark = 0;
159	}
160
161	}
162
163	static final class Driver extends RecursiveAction {
164	final Node root;
165	Driver(Node root) {
166	this.root = root;
167	}
168	public void compute() {
169	root.setMark();
170	root.fork();
171	helpQuiesce();
172	}
173	}
174
175	static Node[] makeGraph(int sideLength) {
176	int n = sideLength * sideLength;
177	Node[] vs = new Node[n];
178	for (int i = 0; i < n; ++i)
179	vs[i] = new Node(new Node[4]);
180
181	// connect each node to left, right, up, down neighbors
182	int maxcol = n - sideLength;
183	int col = 0;
184	for (int i = 0; i < sideLength; ++i) {
185	for (int j = 0; j < sideLength; ++j) {
186	Node[] a = vs[col + j].neighbors;
187	a[0] = vs[col + ((j < sideLength-1) ? (j+1) : 0)];
188	a[1] = vs[col + ((j != 0) ? (j-1) : (sideLength-1))];
189	a[2] = vs[j + ((i < sideLength-1) ? (col + sideLength) : 0)];
190	a[3] = vs[j + ((i != 0) ? (col - sideLength) : maxcol)];
191	}
192	col += sideLength;
193	}
194	return vs;
195	}
196
197	static void resetAll(Node[] g) {
198	for (int i = 0; i < g.length; ++i)
199	g[i].reset();
200	}
201
202	// check that all nodes have parents, and no cycles
203	static void checkSpanningTree(Node[] g, Node root) {
204	int n = g.length;
205	for (int i = 0; i < n; ++i) {
206	Node v = g[i];
207	Node p = v;
208	int k = n;
209	while (p != root) {
210	if (p == null)
211	throw new RuntimeException("null parent");
212	if (--k <= 0)
213	throw new RuntimeException("cycle");
214	p = p.parent;
215	}
216	v.parent = root;
217	}
218	}
219
220	static final class Resetter extends RecursiveAction {
221	final Node[] g;
222	final int lo, hi;
223	Resetter(Node[] g, int lo, int hi) {
224	this.g = g; this.lo = lo; this.hi = hi;
225	}
226	public void compute() {
227	int mid = (lo + hi) >>> 1;
228	if (mid == lo \|\| getSurplusQueuedTaskCount() > 3) {
229	for (int i = lo; i < hi; ++i)
230	g[i].reset();
231	}
232	else
233	invokeAll(new Resetter(g, lo, mid), new Resetter(g, mid, hi));
234	}
235	}
236	}