Threads - summieren

[minzee]

Hi

Ich hab leider scheinbar echt Probleme mit Threads. Scheinbar schaff ich noch nicht mal die einfachsten Sachen

Ich wollte mal ein wenig mit http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf herumexperimentieren, aber scheiter leider gleich am Anfang beim ersten Algorithmus 1 (summation) auf Seite 10. Irgendwie ist das ziemlich frustrierend. Dabei dachte ich echt, ich hätte eine Möglichkeit gefunden:

class B 
{
   private int v;                 // Wert
   private boolean valid = false; // ob B schon einen Wert hat

   public void set(int v)
   {
      this.v = v;
      valid = true;
      
      notifyAll();
   }
   public int get(int h, int i)
   {
      while(!valid)
      {
         try
         {
            System.out.println("waiting h: " + h + ", i: " + i);
            wait();
         }
         catch(InterruptedException e)
         {
         }
      }
      return v;
   }
}
class T extends Thread
{
   private int i;
   private int[] a;
   private B[][] b;
   
   /**
    * @param int i Thread-ID >= 0
    * @param int[] a Daten
    * @param B[][] b Summen
    */
   public T(int i, int[] a, B[][] b)
   {
      this.i = i;
      this.a = a;
      this.b = b;
      
      start();
   }
   public void run()
   {
      System.out.println("i: " + i);
      
      int n = a.length;                            // Anzahl der Werte in a = 8
      int logN = (int)(Math.log(n) / Math.log(2)); // log2(n), bei n = 8 => 3
      
      b[0][i].set(a[i]);                           // unterste Reihe in der Baumstruktur (h = 0)
      for(int h = 1; h <= logN; ++h)               // Höhe. Bei n = 8 läuft jeder Thread von 0 bis 3.
      {
         if(i < n / Math.pow(2, h))                // Allerdings führt nich jeder Thread in jedem Durchlauf eine Addition durch.
         {
            int v = 
               b[h - 1][2 * i].get(h, i) +
               b[h - 1][2 * i + 1].get(h, i);
            b[h][i].set(v);

            System.out.println("h: " + h + ", i: " + i + ", B[" + h + "][" + i + "] = B[" + (h - 1) + "][" + (2 * i) + "] + B[" + (h - 1) + "][" + (2 * i + 1) + "] = " + v);
         }
      }
   }
}
class P0
{
   public static void main(String[] args) 
   {      
      int[] a = {1, 2, 3, 4, 5, 6, 7, 8};          // Werte

      int n = a.length;                            // Anzahl der Werte in a = 8
      int logN = (int)(Math.log(n) / Math.log(2)); // log2(n), bei n = 8 => 3
      B[][] b = new B[logN + 1][n];                // [0 ... 3][0 ... 7]
      for(int i = 0; i < logN + 1; ++i)
      {
         for(int j = 0; j < n; ++j)
         {
            b[i][j] = new B();
         }
      }
      // h
      // 3                                                                   T0: B[3][0]
      //                                                            /             +             \
      // 2                               T0: B[2][0]                                                             T1: B[2][1]
      //                               /      +      \                                                         /      +      \
      // 1             T0: B[1][0]                         T1: B[1][1]                         T2: B[1][2]                         T3: B[1][3]
      //                /   +   \                           /   +   \                           /   +   \                           /   +   \
      // 0  T0: B[0][0]=A[0]  T1: B[0][1]=A[1]  T2: B[0][2]=A[2]  T3: B[0][3]=A[3]  T4: B[0][4]=A[4]  T5: B[0][5]=A[5]  T6: B[0][6]=A[6]  T7: B[0][7]=A[7]
      //
      // Legende: Ti ... Thread i
      
      System.out.println("n: " + n);
      System.out.println("logN: " + logN);
      
      T[] threads = new T[n];
      for(int i = 0; i < n; ++i) // zu jedem Wert 1 Thread
      {
         threads[i] = new T(i, a, b);
      }

      // Ausgabe:
      //System.out.println("Summe: " + b[logN][0].get());
   }
}

Aber leider liefert mir das eine IllegalMonitorStateException. Ist also alles falsch, was ich gemacht habe. Total falsches Konzept. Jetzt weiß ich nicht mehr weiter.

Wie macht man denn das richtig?

 

[minzee]

Ups, das ist mir jetzt peinlich. Ich habe nur "synchronized" vergessen bei den Methoden "get" und "set".

Scheint also so zu funktionieren:

class B 
{
   private int v;                 // Wert
   private boolean valid = false; // ob B schon einen Wert hat

   synchronized public void set(int v)
   {
      this.v = v;
      valid = true;
      
      notifyAll();
   }
   synchronized public int get(int h, int i)
   {
      while(!valid)
      {
         try
         {
            System.out.println("waiting h: " + h + ", i: " + i);
            wait();
         }
         catch(InterruptedException e)
         {
         }
      }
      return v;
   }
}
class T extends Thread
{
   private int i;
   private int[] a;
   private B[][] b;
   
   /**
    * @param int i Thread-ID >= 0
    * @param int[] a Daten
    * @param B[][] b Summen
    */
   public T(int i, int[] a, B[][] b)
   {
      this.i = i;
      this.a = a;
      this.b = b;
      
      start();
   }
   public void run()
   {
      System.out.println("i: " + i);
      
      int n = a.length;                            // Anzahl der Werte in a = 8
      int logN = (int)(Math.log(n) / Math.log(2)); // log2(n), bei n = 8 => 3
      
      b[0][i].set(a[i]);                           // unterste Reihe in der Baumstruktur (h = 0)
      for(int h = 1; h <= logN; ++h)               // Höhe. Bei n = 8 läuft jeder Thread von 0 bis 3.
      {
         if(i < n / Math.pow(2, h))                // Allerdings führt nich jeder Thread in jedem Durchlauf eine Addition durch.
         {
            int v = 
               b[h - 1][2 * i].get(h, i) +
               b[h - 1][2 * i + 1].get(h, i);
            b[h][i].set(v);

            System.out.println("h: " + h + ", i: " + i + ", B[" + h + "][" + i + "] = B[" + (h - 1) + "][" + (2 * i) + "] + B[" + (h - 1) + "][" + (2 * i + 1) + "] = " + v);
         }
      }
   }
}
class P0
{
   public static void main(String[] args) 
   {      
      int[] a = {1, 2, 3, 4, 5, 6, 7, 8};          // Werte

      int n = a.length;                            // Anzahl der Werte in a = 8
      int logN = (int)(Math.log(n) / Math.log(2)); // log2(n), bei n = 8 => 3
      B[][] b = new B[logN + 1][n];                // [0 ... 3][0 ... 7]
      for(int i = 0; i < logN + 1; ++i)
      {
         for(int j = 0; j < n; ++j)
         {
            b[i][j] = new B();
         }
      }
      // h
      // 3                                                                   T0: B[3][0]
      //                                                            /             +             \
      // 2                               T0: B[2][0]                                                             T1: B[2][1]
      //                               /      +      \                                                         /      +      \
      // 1             T0: B[1][0]                         T1: B[1][1]                         T2: B[1][2]                         T3: B[1][3]
      //                /   +   \                           /   +   \                           /   +   \                           /   +   \
      // 0  T0: B[0][0]=A[0]  T1: B[0][1]=A[1]  T2: B[0][2]=A[2]  T3: B[0][3]=A[3]  T4: B[0][4]=A[4]  T5: B[0][5]=A[5]  T6: B[0][6]=A[6]  T7: B[0][7]=A[7]
      //
      // Legende: Ti ... Thread i
      
      System.out.println("n: " + n);
      System.out.println("logN: " + logN);
      
      T[] threads = new T[n];
      for(int i = 0; i < n; ++i) // zu jedem Wert 1 Thread
      {
         threads[i] = new T(i, a, b);
      }

      // Ausgabe:
      for(int i = 0; i < n; ++i) // zu jedem Wert 1 Thread
      {
         try
         {
            threads[i].join();
         }
         catch(InterruptedException e)
         {
         }
      }
      System.out.println("Summe: " + b[logN][0].get(0, 0));
   }
}

Geht das vielleicht noch irgendwie einfacher?

 

[minzee]

Ich glaube, ich habe noch 2 Optimierungsmöglichkeiten gefunden:

class B 
{
   private int v;                 // Wert
   private boolean valid = false; // ob B schon einen Wert hat

   void init(int v)
   {
      this.v = v;
      valid = true;
   }
   /**
    * @param int v
    */
   synchronized void set(int v)
   {
      this.v = v;
      valid = true;
      
      notifyAll();
   }
   /**
    * @return int
    */
   synchronized int get(/*int h, int i*/) // h und i nur zum Debuggen
   {
      while(!valid)
      {
         try
         {
            //System.out.println("waiting h: " + h + ", i: " + i);
            wait();
         }
         catch(InterruptedException e)
         {
         }
      }
      return v;
   }
}
class T extends Thread
{
   private int i;
   private int[] a;
   private B[][] b;
   
   /**
    * @param int i Thread-ID >= 0
    * @param int[] a Daten
    * @param B[][] b Summen
    */
   public T(int i, int[] a, B[][] b)
   {
      this.i = i;
      this.a = a;
      this.b = b;
      
      start();
   }
   public void run()
   {
      //System.out.println("i: " + i);
      
      int n = a.length;                            // Anzahl der Werte in a = 8
      int logN = (int)(Math.log(n) / Math.log(2)); // log2(n), bei n = 8 => 3
      
      for(int h = 1; h <= logN; ++h)               // Höhe. Bei n = 8 läuft jeder Thread von 0 bis 3.
      {
         if(i < n / Math.pow(2, h))                // Allerdings führt nich jeder Thread in jedem Durchlauf eine Addition durch.
         {
            int v = 
               b[h - 1][2 * i].get(/*h, i*/) +
               b[h - 1][2 * i + 1].get(/*h, i*/);
            b[h][i].set(v);

            //System.out.println("h: " + h + ", i: " + i + ", B[" + h + "][" + i + "] = B[" + (h - 1) + "][" + (2 * i) + "] + B[" + (h - 1) + "][" + (2 * i + 1) + "] = " + v);
         }
      }
   }
}
class P
{
   private static void initB(int[] a, B[][] b, int n, int logN)
   {
      for(int i = 0; i < n; ++i)
      {
         b[0][i] = new B();
         b[0][i].init(a[i]);
      }
      for(int h = 1; h < logN + 1; ++h) // 1, 2, 3
      {
         n /= 2;
         for(int i = 0; i < n; ++i) // 4, 2, 1
         {
            b[h][i] = new B();
         }
      }
   }
   public static void main(String[] args) 
   {      
      int[] a = {1, 2, 3, 4, 5, 6, 7, 8};          // 2^x Werte

      // Initialisierung:
      int n = a.length;                            // Anzahl der Werte in a = 8
      int logN = (int)(Math.log(n) / Math.log(2)); // log2(n), bei n = 8 => 3
      B[][] b = new B[logN + 1][n];                // [0 ... 3][0 ... 7]
      initB(a, b, n, logN);
      
      // h
      // 3                                                       T0: B[3][0]
      //                                                /             +             \
      // 2                         T0: B[2][0]                                                 T1: B[2][1]
      //                         /      +      \                                             /      +      \
      // 1          T0: B[1][0]                   T1: B[1][1]                   T2: B[1][2]                   T3: B[1][3]
      //             /   +   \                     /   +   \                     /   +   \                     /   +   \
      // 0  B[0][0]=A[0]   B[0][1]=A[1]   B[0][2]=A[2]   B[0][3]=A[3]   B[0][4]=A[4]   B[0][5]=A[5]   B[0][6]=A[6]   B[0][7]=A[7]
      //
      // Legende: Ti ... Thread i
      
      //System.out.println("n: " + n);
      //System.out.println("logN: " + logN);
      
      T[] threads = new T[logN + 1];
      for(int i = 0; i <= logN; ++i)
      {
         threads[i] = new T(i, a, b);
      }

      // Ausgabe:
      for(int i = 0; i <= logN; ++i)
      {
         try
         {
            threads[i].join();
         }
         catch(InterruptedException e)
         {
         }
      }
      System.out.println("Summe: " + b[logN][0].get(/*0, 0*/));      
   }
}

Allerdings schaut die Implementierung jetzt ein wenig anders aus als der Algorithmus. Die b[0]-Werte initialisiere ich jetzt nicht mehr im Thread, sondern schon vorher im Hauptprogramm. Dadurch kann ich die Anzahl der Threads reduzieren.

Ich hoffe, das verursacht keine Probleme.?.?

 

[minzee]

Ich glaube, diese Variante ist doch nicht gut. Das Wichtigste ist hier die Performance. Das Programm soll schneller sein als ein paar Additionen. Doch je mehr ich außerhalb der Threads mache, desto langsamer wird automatisch alles.

Vielleicht kann das Programm nur schneller werden als normale Additionen, wenn ich auch noch die b-Instanzierungen irgendwie in die Threads reinbekomme.

 

[arilou]

Doch je mehr ich außerhalb der Threads mache, desto langsamer wird automatisch alles.

Unsinn.

Dir ist schon klar, dass das eine akademische Programmierübung darstellt?

Du wirst extrem viele Additionen benötigen, um mit Threads eine Beschleunigung zu erreichen.
In der Zeit, die ein 'new' verbrät, um ein neues Thread-Objekt anzulegen, kannst du 1 Mio Additionen durchführen. Und da du ein Array aufsummieren willst... bei einer Datenmenge, die da noch deutlich darüber liegt, ist dein Problem weniger die Rechengeschwindigkeit der Prozessorkerne, sondern die Speicherbandbreite. Das Ram kann solche Datenmengen nicht schnell genug liefern, nicht mal für 1 Prozessorkern.

Ohne Datenlokalität (d.h. dass ein und dieselben Daten immer wieder verwendet werden, so dass dir ein Cache etwas bringt) kannst du Multithreading vergessen.

 

[minzee]

Kann man das irgendwie anders programmieren, damit das auch bei Arrays Sinn macht, die keine millionen Einträge hat?

Die ersten paar Algorithmen, die in der erwähnten pdf erklärt werden, funktionieren nämlich scheinbar alle irgendwie nach dem gleichen Prinzip.

 

[minzee]

Mir spukt da was im Kopf herum.

Ist das richtig, dass man dem Datentyp int kein null übergeben kann, dem Datentyp Integer aber schon? Könnte ich dann auf null prüfen, wenn ich kontrollieren will, ob ein b-Wert valide ist? Dann könnte ich mir nämlich die Eigenschaft valid sparen.

Und dieses ganze synchronize muss doch nicht unbedingt bei einer Methode angegeben werden, richtig? Man kann doch auch irgendwo mitten im Code einen synchronize-Block definieren, glaube ich irgendwo mal gelesen zu haben.

Aufgrund dieser 2 Punkte brächte ich dann keine B-Klasse und könnte ich mir doch die ganzen B-Instanzierungen ersparen, stimmt das?

 

[arilou]

'int' ist ein primitiver Datentyp, und selbige können alle nicht 'null' sein.
java.lang.Integer ist eine Klasse, und eine Variable diesen "Typs" ist eine Referenz (ein "Pointer") auf ein Integer-Objekt. Ein Pointer kann auf 'null' gesetzt werden.

Die 'null' -Idee, um die Variable "valid" zu sparen, funktioniert prinzipiell. Aber mit Objekten zu hantieren ist viel langsamer als mit primitiven Datentypen...

 

[minzee]

War leider sowieso eine dumme Idee von mir. Definiert man synchronized als Block, muss man ein Objekt übergeben. D. h. auch wenn ein b-Wert noch invalide ist, sollte er schon ein Integer sein.

Ich befürchte, jetzt bin ich mit meinem Latein am Ende. Das wurmt mich echt. Aber man muss auch mal verlieren können.

Falls ihr keine Ideen mehr habt, lasse ich das Thema ruhen. Vielleicht stoße ich irgendwann zufällig auf einen Code, der diesen ganzen parallelen Aufwand rechtfertigt.

 

[JavaMeister]

Java: NebenlÃ

Ich kenne die AUtoren und habe deren VOrlesung besucht. Die erklären das alles sehr einfach.

 

[minzee]

Ich bin ein großer Bücher-Fan! Danke für den Hinweis

Nebenläufige & verteilte Programmierung - terrashop.de

Für die Bearbeitung des Online-Kurses werden ca. 60 Stunden benötigt

Weißt du zufällig, von welchem Online-Kurs genau hier die Rede ist? Würde mir gerne eine wenig davon ansehen. Wenn es mir gefällt, kaufe ich mir das Buch und gehe dann den Online-Kurs komplett durch.

Ist der irgendwo auf F versteckt?

Registriert habe ich mich. Kurs habe ich gefunden auf W3L-B . Die tan 5185441337 habe ich eingelöst. Aber mir wird zum Kurs kein Inhaltsverzeichnis angelegt. Alles leer

Wie kann ich Wissensbausteine auswählen? Kann ich die nur auswählen, wenn ich vorher W3L-Online-Kurse: Java: Nebenl die 890 euro bezahlt habe?

 

[JavaMeister]

Hi,

Ich habe das w3l vor Jahren genutzt. Da wurden für die Studenten die Unterlagen bereitgestellt.

Wie dem auch sei. Ich gehe davon aus, dass die Inhalte sichtbar werden, wenn man sie bezahlt.

Außerdem würde ich mich in diesem fall an w3l direkt wenden.

 

[minzee]

Ich habe vielleicht eine Lösung gefunden:

class SumCounter
{
   private int n;
   private int i; // Zähler je Ebene
   
   /**
    * @param int n Anzahl der Knoten auf der Ebene über der untersten Ebene = Anzahl Werte / 2 = Anzahl Threads.
    */
   SumCounter(int n)
   {
      this.n = n;
      i = 0;
   }
   synchronized void inc()
   {
      try
      {
         if(i < n - 1)
         {
            ++i;
            wait(); // Thread, der inc aufgerufen hat, in Wartepool legen
         }
         else if(n > 1)
         {
            n /= 2;
            i = 0;
            notifyAll(); // alle Threads aus Wartepool holen
         }
      }
      catch( InterruptedException e)
      {
         System.out.println("FEHLER");
      }
   }
}
class SumThread extends Thread
{
   private int i;
   private int n;
   private int[][] sumValues;
   private SumCounter c;
   
   /**
    * @param int n Summations-Ebenen
    * @param int i Thread-ID
    * @param int[][] sumValues aufzusummierende Daten
    * @param SumCounter c
    */
   SumThread(int n, int i, int[][] sumValues, SumCounter c)
   {
      this.n = n;
      this.i = i;
      this.sumValues = sumValues;
      this.c = c;
      
      start();
   }
   public void run()
   {
      int left = i * 2;
      int right = left + 1;
      for(int j = n - 1; j >= 0; --j) // Zeilen
      {
         if(i < 1 << j)
         {
            sumValues[j][i] = sumValues[j + 1][left] + sumValues[j + 1][right];
            c.inc();
         }
      }
   }
}
class ThreadMath
{
   static int sum(int[] values)
   {
      // Daten in 2-dim. Array übernehmen:
      int n = (int)(Math.log(values.length) / Math.log(2.0)); // log2(n), bei n = 8 => 3
      int[][] sumValues = new int[n + 1][values.length]; // [Zeile][Spalte]
      sumValues[n] = values;

      // SumCounter zur Synchronisation der Additionen:
      int m = values.length / 2;
      SumCounter sumCounter = new SumCounter(m);

      // Threads:
      SumThread[] sumThreads = new SumThread[m];
      for(int i = m; i > 0; )
      {
         sumThreads[--i] = new SumThread(n, i, sumValues, sumCounter);
      }
      try
      {
         sumThreads[0].join(); // darauf warten, dass Thread 0 fertig ist
      }
      catch( InterruptedException e)
      {
         System.out.println("FEHLER");
      }
      
      // Debugging-Ausgabe:
      for(int row = 0; row <= n; ++row)
      {
         for(int col = 0; col < values.length; ++col)
            System.out.print(sumValues[row][col] + " ");
         System.out.println();
      }
      
      // Summe:
      return sumValues[0][0];
   }
}
class Main
{
   public static void main(String[] args)
   {
      int[] values = {1, 2, 3, 4, 5, 6, 7, 8}; // 2^x Werte    
      int sum = ThreadMath.sum(values);
      System.out.println(sum); // 36
   }
}

Ich habe jetzt ganz normale int-Werte. Mache also nicht für jeden Wert ein eigenes Objekt. Die Synchronisation übernimmt jetzt eine eigene Klasse, die immer je Baumebene zählt, wie viele Additionen schon durchgeführt wurden.

Ist das OK so?

 

[minzee]

Ich nehme das zurück. Das ist wohl auch keine Lösung. Da bei jeder Addition die synchronisierte Methode aufgerufen wird, und dabei der Thread fast immer in den Wartepool gelegt wird, wird hier wohl wieder serialisiert. Dadurch gehen die Vorteile der parallelen Programmierung verloren. Ist doch so, oder?