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

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