test/loops/ThreadPhaserJacobi.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
 */

// Barrier version of Jacobi iteration

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

public class ThreadPhaserJacobi {

    static final int nprocs = Runtime.getRuntime().availableProcessors();

    /**
     * The maximum submatrix length (both row-wise and column-wise)
     * for any Segment
     **/

    static final double EPSILON = 0.0001;  // convergence criterion

    static int dimGran;

    public static void main(String[] args) throws Exception {
        int n = 2048;
        int steps = 1000;
        try {
            if (args.length > 0)
                n = Integer.parseInt(args[0]);
            if (args.length > 1)
                steps = Integer.parseInt(args[1]);
        }

        catch (Exception e) {
            System.out.println("Usage: java ThreadPhaserJacobi <matrix size> <max steps>");
            return;
        }

        int granularity = n * n / nprocs;
        dimGran = (int)(Math.sqrt(granularity));

        // allocate enough space for edges
        int dim = n+2;
        int ncells = dim * dim;
        double[][] a = new double[dim][dim];
        double[][] b = new double[dim][dim];
        // Initialize interiors to small value
        double smallVal = 1.0/dim;
        for (int i = 1; i < dim-1; ++i) {
            for (int j = 1; j < dim-1; ++j)
                a[i][j] = smallVal;
        }

        int nreps = 3;
        for (int rep = 0; rep < nreps; ++rep) {
            // Fill all edges with 1's.
            for (int k = 0; k < dim; ++k) {
                a[k][0] += 1.0;
                a[k][n+1] += 1.0;
                a[0][k] += 1.0;
                a[n+1][k] += 1.0;
            }
            Driver driver = new Driver(a, b, 1, n, 1, n, steps);
            long startTime = System.currentTimeMillis();
            driver.compute();

            long time = System.currentTimeMillis() - startTime;
            double secs = ((double)time) / 1000.0;

            System.out.println("Compute Time: " + secs);
        }
    }

    static class Segment implements Runnable {

        double[][] A; // matrix to get old values from
        double[][] B; // matrix to put new values into

        // indices of current submatrix
        final int loRow;
        final int hiRow;
        final int loCol;
        final int hiCol;
        final int steps;
        final Phaser barrier;
        double maxDiff; // maximum difference between old and new values

        Segment(double[][] A, double[][] B,
                int loRow, int hiRow,
                int loCol, int hiCol,
                int steps,
                Phaser barrier) {
            this.A = A;   this.B = B;
            this.loRow = loRow; this.hiRow = hiRow;
            this.loCol = loCol; this.hiCol = hiCol;
            this.steps = steps;
            this.barrier = barrier;
            barrier.register();
        }


        public void run() {
            try {
                double[][] a = A;
                double[][] b = B;

                for (int i = 0; i < steps; ++i) {
                    maxDiff = update(a, b);
                    if (barrier.awaitAdvance(barrier.arrive()) < 0)
                        break;
                    double[][] tmp = a; a = b; b = tmp;
                }
            }
            catch(Exception ex) {
                ex.printStackTrace();
                return;
            }
        }

        double update(double[][] a, double[][] b) {
            double md = 0.0; // local for computing max diff

            for (int i = loRow; i <= hiRow; ++i) {
                for (int j = loCol; j <= hiCol; ++j) {
                    double v = 0.25 * (a[i-1][j] + a[i][j-1] +
                                       a[i+1][j] + a[i][j+1]);
                    b[i][j] = v;

                    double diff = v - a[i][j];
                    if (diff < 0) diff = -diff;
                    if (diff > md) md = diff;
                }
            }

            return md;
        }

    }


    static class Driver {
        double[][] A; // matrix to get old values from
        double[][] B; // matrix to put new values into

        final int loRow;   // indices of current submatrix
        final int hiRow;
        final int loCol;
        final int hiCol;
        final int steps;
        Segment[] allSegments;

        Driver(double[][] mat1, double[][] mat2,
               int firstRow, int lastRow,
               int firstCol, int lastCol,
               int steps) {

            this.A = mat1;   this.B = mat2;
            this.loRow = firstRow; this.hiRow = lastRow;
            this.loCol = firstCol; this.hiCol = lastCol;
            this.steps = steps;

            int rows = hiRow - loRow + 1;
            int cols = hiCol - loCol + 1;
            int rblocks = (int)(Math.round((float)rows / dimGran));
            int cblocks = (int)(Math.round((float)cols / dimGran));

            int n = rblocks * cblocks;

            Segment[] segs = new Segment[n];
            Phaser barrier = new Phaser();
            int k = 0;
            for (int i = 0; i < rblocks; ++i) {
                int lr = loRow + i * dimGran;
                int hr = lr + dimGran;
                if (i == rblocks-1) hr = hiRow;

                for (int j = 0; j < cblocks; ++j) {
                    int lc = loCol + j * dimGran;
                    int hc = lc + dimGran;
                    if (j == cblocks-1) hc = hiCol;

                    segs[k] = new Segment(A, B, lr, hr, lc, hc, steps, barrier);
                    ++k;
                }
            }
            System.out.println("Using " + n + " segments (threads)");
            allSegments = segs;
        }

        public void compute() throws InterruptedException {
            Segment[] segs = allSegments;
            int n = segs.length;
            Thread[] threads = new Thread[n];

            for (int k = 0; k < n; ++k) threads[k] = new Thread(segs[k]);
            for (int k = 0; k < n; ++k) threads[k].start();
            for (int k = 0; k < n; ++k) threads[k].join();

            double maxd = 0;
            for (int k = 0; k < n; ++k) {
                double md = segs[k].maxDiff;
                if (md > maxd) maxd = md;
            }

            System.out.println("Max diff after " + steps + " steps = " + maxd);
        }
    }


}
Revision:	1.3
Committed:	Fri Oct 30 14:15:04 2009 UTC (14 years, 6 months ago) by dl
Branch:	MAIN
Changes since 1.2:	+6 -0 lines
Log Message:	Missing file headers
#	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/licenses/publicdomain
5	*/
6
7	// Barrier version of Jacobi iteration
8
9	import java.util.*;
10	import java.util.concurrent.*;
11	//import jsr166y.*;
12
13	public class ThreadPhaserJacobi {
14
15	static final int nprocs = Runtime.getRuntime().availableProcessors();
16
17	/**
18	* The maximum submatrix length (both row-wise and column-wise)
19	* for any Segment
20	**/
21
22	static final double EPSILON = 0.0001; // convergence criterion
23
24	static int dimGran;
25
26	public static void main(String[] args) throws Exception {
27	int n = 2048;
28	int steps = 1000;
29	try {
30	if (args.length > 0)
31	n = Integer.parseInt(args[0]);
32	if (args.length > 1)
33	steps = Integer.parseInt(args[1]);
34	}
35
36	catch (Exception e) {
37	System.out.println("Usage: java ThreadPhaserJacobi <matrix size> <max steps>");
38	return;
39	}
40
41	int granularity = n * n / nprocs;
42	dimGran = (int)(Math.sqrt(granularity));
43
44	// allocate enough space for edges
45	int dim = n+2;
46	int ncells = dim * dim;
47	double[][] a = new double[dim][dim];
48	double[][] b = new double[dim][dim];
49	// Initialize interiors to small value
50	double smallVal = 1.0/dim;
51	for (int i = 1; i < dim-1; ++i) {
52	for (int j = 1; j < dim-1; ++j)
53	a[i][j] = smallVal;
54	}
55
56	int nreps = 3;
57	for (int rep = 0; rep < nreps; ++rep) {
58	// Fill all edges with 1's.
59	for (int k = 0; k < dim; ++k) {
60	a[k][0] += 1.0;
61	a[k][n+1] += 1.0;
62	a[0][k] += 1.0;
63	a[n+1][k] += 1.0;
64	}
65	Driver driver = new Driver(a, b, 1, n, 1, n, steps);
66	long startTime = System.currentTimeMillis();
67	driver.compute();
68
69	long time = System.currentTimeMillis() - startTime;
70	double secs = ((double)time) / 1000.0;
71
72	System.out.println("Compute Time: " + secs);
73	}
74	}
75
76	static class Segment implements Runnable {
77
78	double[][] A; // matrix to get old values from
79	double[][] B; // matrix to put new values into
80
81	// indices of current submatrix
82	final int loRow;
83	final int hiRow;
84	final int loCol;
85	final int hiCol;
86	final int steps;
87	final Phaser barrier;
88	double maxDiff; // maximum difference between old and new values
89
90	Segment(double[][] A, double[][] B,
91	int loRow, int hiRow,
92	int loCol, int hiCol,
93	int steps,
94	Phaser barrier) {
95	this.A = A; this.B = B;
96	this.loRow = loRow; this.hiRow = hiRow;
97	this.loCol = loCol; this.hiCol = hiCol;
98	this.steps = steps;
99	this.barrier = barrier;
100	barrier.register();
101	}
102
103
104	public void run() {
105	try {
106	double[][] a = A;
107	double[][] b = B;
108
109	for (int i = 0; i < steps; ++i) {
110	maxDiff = update(a, b);
111	if (barrier.awaitAdvance(barrier.arrive()) < 0)
112	break;
113	double[][] tmp = a; a = b; b = tmp;
114	}
115	}
116	catch(Exception ex) {
117	ex.printStackTrace();
118	return;
119	}
120	}
121
122	double update(double[][] a, double[][] b) {
123	double md = 0.0; // local for computing max diff
124
125	for (int i = loRow; i <= hiRow; ++i) {
126	for (int j = loCol; j <= hiCol; ++j) {
127	double v = 0.25 * (a[i-1][j] + a[i][j-1] +
128	a[i+1][j] + a[i][j+1]);
129	b[i][j] = v;
130
131	double diff = v - a[i][j];
132	if (diff < 0) diff = -diff;
133	if (diff > md) md = diff;
134	}
135	}
136
137	return md;
138	}
139
140	}
141
142
143	static class Driver {
144	double[][] A; // matrix to get old values from
145	double[][] B; // matrix to put new values into
146
147	final int loRow; // indices of current submatrix
148	final int hiRow;
149	final int loCol;
150	final int hiCol;
151	final int steps;
152	Segment[] allSegments;
153
154	Driver(double[][] mat1, double[][] mat2,
155	int firstRow, int lastRow,
156	int firstCol, int lastCol,
157	int steps) {
158
159	this.A = mat1; this.B = mat2;
160	this.loRow = firstRow; this.hiRow = lastRow;
161	this.loCol = firstCol; this.hiCol = lastCol;
162	this.steps = steps;
163
164	int rows = hiRow - loRow + 1;
165	int cols = hiCol - loCol + 1;
166	int rblocks = (int)(Math.round((float)rows / dimGran));
167	int cblocks = (int)(Math.round((float)cols / dimGran));
168
169	int n = rblocks * cblocks;
170
171	Segment[] segs = new Segment[n];
172	Phaser barrier = new Phaser();
173	int k = 0;
174	for (int i = 0; i < rblocks; ++i) {
175	int lr = loRow + i * dimGran;
176	int hr = lr + dimGran;
177	if (i == rblocks-1) hr = hiRow;
178
179	for (int j = 0; j < cblocks; ++j) {
180	int lc = loCol + j * dimGran;
181	int hc = lc + dimGran;
182	if (j == cblocks-1) hc = hiCol;
183
184	segs[k] = new Segment(A, B, lr, hr, lc, hc, steps, barrier);
185	++k;
186	}
187	}
188	System.out.println("Using " + n + " segments (threads)");
189	allSegments = segs;
190	}
191
192	public void compute() throws InterruptedException {
193	Segment[] segs = allSegments;
194	int n = segs.length;
195	Thread[] threads = new Thread[n];
196
197	for (int k = 0; k < n; ++k) threads[k] = new Thread(segs[k]);
198	for (int k = 0; k < n; ++k) threads[k].start();
199	for (int k = 0; k < n; ++k) threads[k].join();
200
201	double maxd = 0;
202	for (int k = 0; k < n; ++k) {
203	double md = segs[k].maxDiff;
204	if (md > maxd) maxd = md;
205	}
206
207	System.out.println("Max diff after " + steps + " steps = " + maxd);
208	}
209	}
210
211
212	}