Newsgroup: it.comp.java
Titolo: Multithreading concorrente contro monothreading

Ci sono dei casi di algoritmi (di calcolo, ordinamento,ecc..) in cui l'uso
del multithread associato a sistemi monoprocessore puň dare migliori
prestazioni (in termini di millisecondi) rispetto alla corrispondente
versione monothread? Abbiamo provato diversi programmi in un sistema con
processore Athlon XP e Windows XP prelevati dal sito ufficiale del libro:
"High-Performance Java Platform Computing" (
www.toolsotfcomputing.com
) ma
abbiamo notato che le performances peggiorano in tutti i casi (come
naturalmente ci aspettavamo avendo letto qua e la) tranne che nel caso
dell'algoritmo ShellsortBarrier, di cui alleghiamo il sorgente. Perché
questa implementazione gira piů veloce (e non di poco provate! Il limite nel
nostro sistema č circa 200 thread!) aumentando il numero di thread? Vi prego
aiutateci, noi non siamo riusciti a capirlo!
Name: ShellsortBarrier.java
-------------------------------------------------------------
import jhpc.thread.*; //library developed by the autors of the book
class ShellsortBarrier {
  static int minDivisible=3;
  int numThreads;
 public ShellsortBarrier(int numThreads){
	this.numThreads=numThreads;
 }
 private class Sort implements Runnable {
   int[] a; int i, h; SimpleBarrier b;
   Sort(int[] a, int i, int h, SimpleBarrier b){
	this.a=a; this.i=i; this.h=h; this.b=b;
   }
   public void run() {
	try{
	  while (h>0) {
	    if (h==2) h=1;
	    for (int m=i; m<h; m+=numThreads) {
		isort(a,i,h);
	    }
	    h=(int)(h/2.2);
	    b.gather();
	  }
	}catch(Exception ex){}
   }
 }
 static void isort(int[] a,int m,int h) {
	int i,j;
	for (j=m+h; j<a.length; j+=h) {
	    for (i=j; i>m && a[i]>a[i-h]; i-=h) {
		int tmp=a[i];
		a[i]=a[i-h];
		a[i-h]=tmp;
	    }
	}
 }
 public void sort(int[] a) {
	if (a.length<minDivisible) {
		isort(a,0,1);
		return;
	}
	SimpleBarrier b=new SimpleBarrier(numThreads);
	for (int i=numThreads-1;i>0;i--)
		new Thread(new Sort(a,i,a.length/minDivisible,b)).start();
	new Sort(a,0,a.length/minDivisible,b).run();
 }
 public static class Test1{
    public static void main(String[] args) {
	int[] a=new int[20];
	int i;
	for (i=a.length-1;i>=0;i--) {
		a[i]=(int)(Math.random()*100);
	}
	for (i=a.length-1;i>=0;i--) {
		System.out.print(" "+a[i]);
	}
	System.out.println();
	ShellsortBarrier s=new ShellsortBarrier(3);
	s.sort(a);
	for (i=a.length-1;i>=0;i--) {
		System.out.print(" "+a[i]);
	}
	System.out.println();
    }
 }
 public static class TestTime1{
    public static void main(String[] args) {
	if (args.length<2) {
		System.out.println(
			"Usage: java ShellsortBarrier$TestTime1 N T");
		System.exit(0);
	}
	int N=Integer.parseInt(args[0]);
	int T=Integer.parseInt(args[1]);
	int[] a=new int[N];
	int i;
	long time;
	for (i=a.length-1;i>=0;i--) {
		a[i]=(int)(Math.random()*N);
	}
	//for (i=a.length-1;i>=0;i--) {
	// System.out.print(" "+a[i]);
	//}
	//System.out.println();
	ShellsortBarrier s=new ShellsortBarrier(T);
	time=System.currentTimeMillis();
	s.sort(a);
	time=System.currentTimeMillis()-time;
	//for (i=a.length-1;i>=0;i--) {
	// System.out.print(" "+a[i]);
	//}
	//System.out.println();
	System.out.println("ShellsortBarrier\t"+N+"\t"+T+"\t"+time);
    }
 }
}
-------------------------------------------------------------
-Below is the library recalled in ShellsortBarrier.java:
Name: SimpleBarrier.java
-------------------------------------------------------------
package jhpc.thread;
/** Allows multiple threads to gather at a point before proceeding.
@author Thomas W. Christopher (Tools of Computing LLC)
@version 0.2 Beta
*/
public class SimpleBarrier {
//Number of threads that still must gather.
protected int count;
//Total number of threads that must gather.
protected int initCount;
/*Creates a Barrier at which n threads may repeatedly gather.
@param n total number of threads that must gather.
*/
 public SimpleBarrier(int n) {
    if (n<=0) throw
	new IllegalArgumentException (
	  "Barrier initialization specified non-positive value "
		+ n);
    initCount = count = n;
 }
/**
Is called by a thread to wait for the rest of the n threads to gather
before the set of threads may continue executing.
@exception InterruptedException If interrupted while waiting.
*/
 public synchronized void gather()
		throws InterruptedException {
	if (--count > 0) wait();
	else {
		count = initCount;
		notifyAll();
	}
 }
----------------------------------------------------------------
Vi prego aiutateci (in qualsiasi modo), siamo due studenti di ing.
elettronica di Ancona e stiamo facendo uno studio su questo argomento per
l'esame di Sistemi di Elaborazione. Grazie per l'interessamento.
                  Saluti,
                         Henry e Andrea
--------------------------------
Inviato via 
http://usenet.libero.it

 l'esame di Sistemi di Elaborazione. Grazie per l'interessamento.
Il motivo per cui va + veloce la versione multithread
e' che e' sbagliato il vostro algoritmo.
Io infatti ho prso il vostro sorgente
e anche nella versione multithread
mi sono fatto stampare l'array prima e dopo.
Ecco un run tipico:
java ShellsortBarrier$TestTime1 20 5
  41 70 55 37 85 53 19 89 96 5 81 75 13 8 98 52 6 36 85 27
  41 70 55 37 85 53 19 89 96 5 81 75 13 8 98 52 6 36 85 27
ShellsortBarrier	20	5	10
Mentre un run tipico della versione monothread funzionante e':
java ShellsortBarrier$Test1
  56 24 42 65 99 7 87 7 73 16 73 14 39 81 91 21 47 97 58 19
  7 7 14 16 19 21 24 39 42 47 56 58 65 73 73 81 87 91 97 99
Semplice, no?
- Dario

 e' che e' sbagliato il vostro algoritmo.
Sorry:
   ==> Ho detto un'enorme ca..ata <==
Scusate ancora.
Il vostro programma e' corretto.
Sono io che sono fatto... di caldo!
In quanto alla domanda originaria:
e' meglio che ci pensi con + calma e con + fresco.
Non ho analizzato bene l'algoritmo (lo faro' appunto con + fresco)
ma potrebbero esistere, secondo me e secondo i miei vaghi ricordi
di computabilita', degli algoritmi tali che
   T(1..100) > T(1..10) + T(11..20) + ... + T(91..100) + Z
dove T(x..y) e' il tempo per calcolare sugli elementi da x ad y
e dove X e' il tempo di mettere insieme i risultati delle invocazioni
parziali T(1..10), ... T(91..100).
Non so se mi son spiegato bene.
Ci ripenso con + fresco a disposizione.
- Dario


Abbiamo scritto agli autori del libro da cui abbiamo preso l'algoritmo in
questione.
Uno di loro ci ha risposto che potrebbe essere una questione di cache, nel
senso che, mentre la versione monothread deve caricare tutto il vettore in
memoria, ciascun thread della versione multithread usa solo una parte di
tale vettore da gestire. E' dunque possibile che mentre il vettore originale
risiede in memoria centrale perché nella cache non ci sta (ovviamente sto
parlando di vettori con 100000 elementi), il pezzetto di vettore sul quale
agisce ciascun thread si trova in cache velocizzando tale versione. Per me
il discorso fila abbastanza, l'unica cosa che mi viene in mente a questo
punto è di provare a usare vettori di piccole dimensioni, avendo la certezza
che questi si trovino allocati completamente in cache, e vedere se il
comportamento rimane lo stesso. Il problema è come fare per sapere con
certezza se il mio vettore si trova tutto in cache o meno! Mi sembra che il
sistema operativo non ne è a conoscenza in quanto la cache è gestita a
livello hardware dal processore! Boh?


 ha scritto:

Abbiamo scritto agli autori del libro da cui abbiamo preso l'algoritmo in
questione.
Uno di loro ci ha risposto che potrebbe essere una questione di cache, nel
senso che, mentre la versione monothread deve caricare tutto il vettore in
memoria, ciascun thread della versione multithread usa solo una parte di
tale vettore da gestire. E' dunque possibile che mentre il vettore originale
risiede in memoria centrale perché nella cache non ci sta (ovviamente sto
parlando di vettori con 100000 elementi), il pezzetto di vettore sul quale
agisce ciascun thread si trova in cache velocizzando tale versione. Per me
il discorso fila abbastanza, l'unica cosa che mi viene in mente a questo
punto è di provare a usare vettori di piccole dimensioni, avendo la certezza
che questi si trovino allocati completamente in cache, e vedere se il
comportamento rimane lo stesso. Il problema è come fare per sapere con
certezza se il mio vettore si trova tutto in cache o meno! Mi sembra che il
sistema operativo non ne è a conoscenza in quanto la cache è gestita a
livello hardware dal processore! Boh?
Scusate, flyston sono sempre io
