How to speed up calculation using multiple threads?

Question

I'm trying to compute Pi, but what I really want to achieve is efficiency when using more than one thread. The algorithm is simple: I randomly generate points in the unit square and after that count how many of them are in the circle inscribed within the square. (more here: http://math.fullerton.edu/mathews/n2003/montecarlopimod.html) My idea is to split the square horizontally and to run a different thread for each part of it. But instead of speed up, all I get is a delay. Any ideas why? Here is the code:

public class TaskManager { public static void main(String[] args) { int threadsCount = 3; int size = 10000000; boolean isQuiet = false; PiCalculator pi = new PiCalculator(size); Thread tr[] = new Thread[threadsCount]; long time = -System.currentTimeMillis(); int i; double s = 1.0/threadsCount; int p = size/threadsCount; for(i = 0; i < threadsCount; i++) { PiRunnable r = new PiRunnable(pi, s*i, s*(1.0+i), p, isQuiet); tr[i] = new Thread(r); } for(i = 0; i < threadsCount; i++) { tr[i].start(); } for(i = 0; i < threadsCount; i++) { try { tr[i].join(); } catch (InterruptedException e) { e.printStackTrace(); } } double myPi = 4.0*pi.getPointsInCircle()/pi.getPointsInSquare(); System.out.println(myPi + " time = " + (System.currentTimeMillis()+time)); } } public class PiRunnable implements Runnable { PiCalculator pi; private double minX; private double maxX; private int pointsToSpread; public PiRunnable(PiCalculator pi, double minX, double maxX, int pointsToSpread, boolean isQuiet) { super(); this.pi = pi; this.minX = minX; this.maxX = maxX; this.pointsToSpread = pointsToSpread; } @Override public void run() { int n = countPointsInAreaInCircle(minX, maxX, pointsToSpread); pi.addToPointsInCircle(n); } public int countPointsInAreaInCircle (double minX, double maxX, int pointsCount) { double x; double y; int inCircle = 0; for (int i = 0; i < pointsCount; i++) { x = Math.random() * (maxX - minX) + minX; y = Math.random(); if (x*x + y*y <= 1) { inCircle++; } } return inCircle; } } public class PiCalculator { private int pointsInSquare; private int pointsInCircle; public PiCalculator(int pointsInSquare) { super(); this.pointsInSquare = pointsInSquare; } public synchronized void addToPointsInCircle (int pointsCount) { this.pointsInCircle += pointsCount; } public synchronized int getPointsInCircle () { return this.pointsInCircle; } public synchronized void setPointsInSquare (int pointsInSquare) { this.pointsInSquare = pointsInSquare; } public synchronized int getPointsInSquare () { return this.pointsInSquare; } }

Some results: -for 3 threads: "3.1424696 time = 2803" -for 1 thread: "3.1416192 time = 2337"

He's starting them all before joining so this is ok. If you only have 2 cores than there is no use in using more than 2 threads. Your application is purely CPU bound so more threads than cores will just slow things down due to the overhead of context switches. — ribram
– ribram, Commented Jun 7, 2011 at 19:54
I used the following in my version final int threadsCount = Runtime.getRuntime().availableProcessors(); — user177800
– user177800, Commented Jun 7, 2011 at 20:10

Saurabh Gokhale · Accepted Answer · 2011-06-07 19:42:09Z

Your threads could be fighting/waiting for Math.random() which is synchronized, you should create an instance of java.util.Random for each thread. Also in this case speedup with multiple threads will only happen if you have more than one core/cpu.

From the javadoc of Math.random():

This method is properly synchronized to allow correct use by more than one thread. However, if many threads need to generate pseudorandom numbers at a great rate, it may reduce contention for each thread to have its own pseudorandom-number generator.

I changed the Math.random() to a local instance of Random and get the following output 3.1411296 time = 253 Core i3 M350 2.27GHZ / 8GB RAM

user177800 · Accepted Answer · 2011-06-07 20:08:38Z

Here is an alternate main method that uses the java.util.concurrency package instead of manually managing the threads and waiting for them to finish.

public static void main(final String[] args) throws InterruptedException { final int threadsCount = Runtime.getRuntime().availableProcessors(); final int size = 10000000; boolean isQuiet = false; final PiCalculator pi = new PiCalculator(size); final ExecutorService es = Executors.newFixedThreadPool(threadsCount); long time = -System.currentTimeMillis(); int i; double s = 1.0 / threadsCount; int p = size / threadsCount; for (i = 0; i < threadsCount; i++) { es.submit(new PiRunnable(pi, s * i, s * (1.0 + i), p, isQuiet)); } es.shutdown(); while (!es.isTerminated()) { /* do nothing waiting for threads to complete */ } double myPi = 4.0 * pi.getPointsInCircle() / pi.getPointsInSquare(); System.out.println(myPi + " time = " + (System.currentTimeMillis() + time)); }

I also changed the Math.random() to use local instances of Random for each Runnable.

final private Random rnd; ... x = this.rnd.nextDouble() * (maxX - minX) + minX; y = this.rnd.nextDouble();

this is the new output I get ...

3.1419284 time = 235

I think you could probably drop the time some more using Futures and not having to synchronized so much on the PiCalculator.

Collectives™ on Stack Overflow

How to speed up calculation using multiple threads?

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related