Re: Multithreading / Scalability

Philipp Kayser wrote:
Hi,

I wrote a small program to test scalability in a multiprocessor
environment (in my case an Athlon 64 X2). I included the source below.

To my surprise the calculation does not run faster if I use 2 threads
(which should be the case if I have 2 processors) but it runs 5 times
slower (e.g. 15s instead of 3s)! Everything else seems to be okay: If i
use 1 thread, I have a total CPU usage of 50%, if use two threads I get
100%.
The best thing is: if I limit the JVM to one processor by setting the
CPU affinity for the process, but again take 2 threads, the calculation
runs only 2 times slower (6s instead of 3s for one thread).

My current current diagnosis is that it may have something to do with
the CPU cache. I searched the Internet for similar problems and found
the terms "CPU Cache trashing" and "Ping-Pong-Effect": the processors
always switch between the two threads and by doing so their CPU cache
gets flushed every time.

Does anyone have an idea?

Best regards,
Philipp Kayser.

public class Test
{
private final int number_of_threads = 2;
private static int number_of_finished_threads;
private Thread threads[] = new Thread[number_of_threads];
double result[] = new double[number_of_threads];
private Thread main_thread;

private class CalculationThread extends Thread
{
int thread_number;

CalculationThread(int n)
{
super();
thread_number = n;
}

public void run()
{
try
{
synchronized (this)
{
while (true)
{
wait();

int n = 0;

for (n = 0; n < 600000000; n++)
if (n % number_of_threads == thread_number)
result[thread_number] += Math.sqrt(n);

synchronized (main_thread)
{
number_of_finished_threads++;
main_thread.notify();
}
}
}
}
catch (InterruptedException e)
{
}
}
}

private void multithreaded_calculation()
{
synchronized (main_thread)
{
number_of_finished_threads = 0;

int i;
for (i = 0; i < number_of_threads; i++)
{
synchronized (threads[i])
{
threads[i].notify();
}
}

do
{
try
{
main_thread.wait();
}
catch (InterruptedException e)
{
}
}
while (number_of_finished_threads < number_of_threads);

double total_result = 0;
for (i = 0; i < number_of_threads; i++)
total_result += result[i];

System.out.println(total_result);
}
}

private void test()
{
main_thread = Thread.currentThread();

int i;
for (i = 0; i < number_of_threads; i++)
{
threads[i] = new CalculationThread(i);
threads[i].setPriority(Thread.NORM_PRIORITY);
threads[i].setDaemon(true);
threads[i].start();
}

try
{
Thread.sleep(1000);
}
catch (InterruptedException e)
{
}

long t0 = new Date().getTime();

multithreaded_calculation();

long t1 = new Date().getTime();

System.out.println(((double)t1 - t0)/1000);
}

public static void main(String[] args) {
new Test().test();
}
}

Saw your post and thought it was interesting. I too duplicated your results but I don't have a clue as to what the problem is. I wrote a couple of tests of my own to try and got more predictable results. Although not quite.

The first program below times the calculations as yours did but I think it is still not optimum for this test.

The second program calculates the number of calculation cycles per ms which I think is more to the point. I got very similar results to the first test though and that is that one thread is definitely slower than two threads but more than that don't really improve performance. On my single processor machine, every increase in threads reduced the number of calculations that could be performed although again not as dramatically as I expected with the increase in number of threads.

I tested these on my 1.6Ghz P4 and on a dual Xeon 2.8Ghz. The Xeons are dual core and as I added threads I could see the additional cores being used. Another interesting thing, if I used one thread the processor usage showed 25%, two threads 50% and so on. The P4 is running Windows XP Home and the Xeon is running 32bit Windows XP Pro.

I do think that the comment about the floating point processor could be significant too.

Anyway a very interesting post.


public class test2 implements Runnable {
int numberOfThreads;
int calculations = 100000000;
Thread[] thread;

public test2(String[] args) {
numberOfThreads = Integer.parseInt(args[0]);
thread = new Thread[numberOfThreads];

long then = System.currentTimeMillis();

for (int i=0; i<numberOfThreads; i++) {
thread[i] = new Thread(this);
thread[i].start();
}

try {
for (int i=0; i<numberOfThreads; i++)
thread[i].join();
} catch (InterruptedException ie) {
ie.printStackTrace();
}

System.out.println(System.currentTimeMillis() - then);
}

public void run() {
double d;
int n = calculations / numberOfThreads;
for (int i=1; i<=n; i++) {
d = Math.sqrt(i*1.234);
double t = d / i;
}
}

public static void main(String[] args) {
new test2(args);
}
}

import java.util.concurrent.*;

public class test3 implements Runnable {
volatile long calculations;
volatile boolean runFlag = true;
Object o = new Object();
Semaphore sem;

public test3(String[] args) {
int numberOfThreads = Integer.parseInt(args[0]);
Thread[] thread = new Thread[numberOfThreads];
sem = new Semaphore(numberOfThreads);
try {
sem.acquire(numberOfThreads);

for (int i=0; i<numberOfThreads; i++) {
thread[i] = new Thread(this);
thread[i].start();
}
Thread.sleep(2000); // wait till all threads are created

long then = System.currentTimeMillis();
sem.release(numberOfThreads);
Thread.sleep(20000);
runFlag = false;
long now = System.currentTimeMillis();

System.out.println(calculations/(now-then));
} catch (InterruptedException ie) {
ie.printStackTrace();
}
}

public void run() {
try {
sem.acquire();
while (runFlag) {
double d = Math.sqrt(1234.56789);
double t = Math.tan(d);
++calculations;
}
} catch (InterruptedException ie) {
ie.printStackTrace();
}
}

public static void main(String[] args) {
new test3(args);
}
}

--

Knute Johnson
email s/nospam/knute/
.

Relevant Pages

  • Re: Need Help, Trying to learn WCF
    ... Right now I have a windows application that does some room calculations, ... is instead of use the roomrate class is send those 5 arguments to a ... [Operational Contract] ... int MyMethod ...
    (microsoft.public.dotnet.framework.webservices)
  • Re: Rounding error when converting from double to int
    ... the original double amount contains fractions of a cent (due to some ... interest calculations). ... then it converts to int. ...     else ...
    (comp.lang.c)
  • Re: A freshmans question
    ... public static void main{ ... int i =0; ... Do the assignment. ... terrible,I don't understand all of your meaning. ...
    (comp.lang.java.programmer)
  • Re: Using java.util.map
    ... public static void main{ ... The problem is not with the Map implemetations but with the handling of the ... In Java you used an imutable one. ... Is is partially the fault of the Java language in not making int a true ...
    (comp.lang.java.advocacy)
  • Re: uninitialized variable
    ... public static void main(String args) { ... int y = 10; ... But as far as the compiler ...
    (comp.lang.java.programmer)