Threading langsam, warum ?

funcry · Verfasst: Do 12.02.09 15:49

Für ein kleines privates Projekt versuche ich Threading effizient einzusetzen.

Innerhalb des Projektes gibt es eine Routine die 60% der Rechenzeit beansprucht.

Alle meine Versuche diese Schleife parallel auszuführen scheitern an der Effizienz. Vermutlich ist der Block der parallel ausgeführt werden soll einfach zu kurz, so dass die gesamten Einsparungen durch den Mehraufwand durch Threading verloren gehen. Ist dem wirklich so, oder habe ich es einfach ineffizient programmiert ?

Hier ist die single Thread Routine (Verarbeitungszeit Programm 0,57 Sekunden 100000 Aufrufe):

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

for (int x = 0; x < this.Fn_hcs; x++)
            {
                double ds_hx = ds_h[x];

                for (int y = 0; y < this.Fn_ics; y++)
                {
                    this.Fws.ws_h[x][y] += this.Flf * this.Fws.w_i * ds_hx * vs_i[y] + this.Fmom * (this.Fws.ws_h[x][y] - this.Fws_old.ws_h[x][y]);
                }

                // + bias input:
                this.Fws.ws_h[x][this.Fn_ics] += this.Flf * this.Fws.w_i * ds_hx + this.Fmom * (this.Fws.ws_h[x][this.Fn_ics] - this.Fws_old.ws_h[x][this.Fn_ics]);

            }

Die folgenden Zeiten gemessen an einer dual-Core Maschine:

Hier das Gleiche mit ThreadPool (Verarbeitungszeit Programm 2,40 Sekunden 100000 Aufrufe):

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

AutoResetEvent done = new AutoResetEvent(false);
            int numToDo = this.Fn_hcs;

            for (int x = 0; x < this.Fn_hcs; x++)
            {                
                ThreadPool.QueueUserWorkItem(delegate (object cnt) 
                {
                    int _x = (int)cnt;
                    for (int y = 0; y < this.Fn_ics; y++)
                        this.Fws.ws_h[_x][y] += this.Flf * this.Fws.w_i * ds_h[_x] * vs_i[y] + this.Fmom * (this.Fws.ws_h[_x][y] - this.Fws_old.ws_h[_x][y]);

                    // + bias input:
                    this.Fws.ws_h[_x][this.Fn_ics] += this.Flf * this.Fws.w_i * ds_h[_x] + this.Fmom * (this.Fws.ws_h[_x][this.Fn_ics] - this.Fws_old.ws_h[_x][this.Fn_ics]);

                    if (Interlocked.Decrement(ref numToDo) == 0) done.Set();
                }, x);
            }

            done.WaitOne();

Und hier mit Parallel Extensions von Microsoft (Verarbeitungszeit Programm 4,4 Sekunden 100000 Aufrufe):

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

Parallel.For(0, this.Fn_hcs, x =>
            {
                double ds_hx = ds_h[x];

                for (int y = 0; y < this.Fn_ics; y++)
                {
                    this.Fws.ws_h[x][y] += this.Flf * this.Fws.w_i * ds_hx * vs_i[y] + this.Fmom * (this.Fws.ws_h[x][y] - this.Fws_old.ws_h[x][y]);
                }

                // + bias input:
                this.Fws.ws_h[x][this.Fn_ics] += this.Flf * this.Fws.w_i * ds_hx + this.Fmom * (this.Fws.ws_h[x][this.Fn_ics] - this.Fws_old.ws_h[x][this.Fn_ics]);

            });

Was ich bisher noch getestet habe:
* Umstellung des Programems von STAThread auf MTAthread und anstelle von WaitOne auf WaitAll (hat nichts gebracht)
* Anstelle des delegates eine eigene Methode geschrieben und die Parameter in einem Struct übergeben (hat bisschen was gebracht, insgesamt aber ein bisschen langsamer als single-Threaded).
* Anstelle des ThreadPools eingene Threads erstellt (5 Stck). (hat nichts gebracht).

Was mich stutzig macht ist, dass Microsoft selbst für sehr kurze Routinen Threading verwendet, ich dabei aber massive Nachteile messe:

Hier ein original-Beispiel aus der Parallel Extension Doku (abgesehen davon wären jagged Arrays erheblich schneller...):
As a real-world example of where Parallel.For is useful, consider the task of multiplying two matrices:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

void MultiplyMatrices(int size, double[,] m1, double[,] m2, double[,] result)
      {
          Parallel.For(0, size, i =>
          {
              for (int j = 0; j < size; j++)
              {
                  result[i, j] = 0;
                  for (int k = 0; k < size; k++)
                  {
                      result[i, j] += m1[i, k] * m2[k, j];
                  }
              }
          });
      }

Könnt Ihr mir bei dem Problem weiterhelfen, stehe da irgendwie auf dem Schlauch :/

Kha · Verfasst: Do 12.02.09 17:33

funcry hat folgendes geschrieben :

Hier ist die single Thread Routine (Verarbeitungszeit Programm 0,57 Sekunden 100000 Aufrufe):

Also ein paar Mikrosekunden Laufzeit? Dafür ist der Overhead wahrscheinlich doch zu groß

. Beim Matrix-Beispiel bekomme ich "schon" bei 100x100-Matrizen folgendes Ergebnis:

markieren

Quelltext

1:
2:

   1. Parallel.For                       2,49 ms
   2. for                                3,99 ms

Und bei 200x200 bin ich schon (eben O(n³)) bei einem Verhältnis von 1:3. Hab also keinen Dualcore :mrgreen:

.

_________________
>λ=

funcry · Verfasst: Sa 14.02.09 10:33

Ich kann das bestätigen:

Jeweils 100x100 Matrix 1000 Durchgänge (i7 System 8 Threads):

markieren

Quelltext

1:
2:
3:
4:
5:
6:

Parallel.for    1,55 Sekunden (ohne Debugging)
for:        3,0 Sekunden (ohne Debugging)

jagged Arrays:
Parallel.for    1,32 Sekunden (ohne Debugging)
for:      2,87 Sekunden (ohne Debuggind)

Müsste die Ergebnismatrix nicht als Ref-Parameter übergeben werden ?

Wers selbst probieren möchte hier der Quelltext:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:

namespace WindowsFormsApplication1
{

    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        Random myrandom = new Random();

        private void button1_Click(object sender, EventArgs e)
        {
            int size = 100;

            test mytest = new test();
            double[,] m1 = new double[size, size];
            double[,] m2 = new double[size, size];
            double[,] mx = new double[size, size];

            for (int x = 0; x < size; x++)
                for (int y = 0; y < size; y++)
                {
                    m1[x, y] = myrandom.NextDouble();
                    m2[x, y] = myrandom.NextDouble();
                }

            Stopwatch mystopwatch = new Stopwatch();
            mystopwatch.Start();

            for (int n = 0; n < 1000; n++)
              mytest.MultiplyMatrices(size, m1, m2, mx);

            this.label1.Text = mystopwatch.Elapsed.ToString();
        }
    }

    public class test
    {
        public void MultiplyMatrices(int size, double[,] m1, double[,] m2, double[,] result)
        {
            //Parallel.For(0, size, i =>
            for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        result[i, j] = 0;
                        for (int k = 0; k < size; k++)
                        {
                            result[i, j] += m1[i, k] * m2[k, j];
                        }
                    }
                }
        }
    }
}

Kha · Verfasst: Sa 14.02.09 13:24

funcry hat folgendes geschrieben :

Müsste die Ergebnismatrix nicht als Ref-Parameter übergeben werden ?

Wenn sich die Funktion darauf verlässt, dass die Größe schon stimmt: Nein, denn Arrays sind Reference Types.

_________________
>λ=

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,

Zitat:

result[i, j] += m1[i, k] * m2[k, j];

allein diese Zeile verdoppelt bei mir die Laufzeit...

edit: sry, die Antwort war etwas kurz...

Das Problem dabei ist halt, dass du immer auf das Array, also auf den Cache zugreifen musst, wenn man sich dafür eine zusätzliche Variable nimmt kann die immer in Registern gehalten werden...

Also so:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

double tmp;
for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        tmp = 0;
                        for (int k = 0; k < size; k++)
                        {
                            tmp += m1[i, k] * m2[k, j];
                        }
                        result[i, j] = tmp
                    }
                }

Was die ursprüngliche Frage angeht, da werden ja auch haufenweise invariante Werte neu berechnet, schneller wäre's auf jeden Fall so:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

for (int x = 0; x < this.Fn_hcs; x++)
            {
                double ds_hx = ds_h[x];
                double tmp = this.Flf * this.Fws.w_i * ds_hx;
                for (int y = 0; y < this.Fn_ics; y++)
                {
                    this.Fws.ws_h[x][y] +=  tmp * vs_i[y] + this.Fmom * (this.Fws.ws_h[x][y] - this.Fws_old.ws_h[x][y]);
                }

                // + bias input:
                this.Fws.ws_h[x][this.Fn_ics] += this.Flf * this.Fws.w_i * ds_hx + this.Fmom * (this.Fws.ws_h[x][this.Fn_ics] - this.Fws_old.ws_h[x][this.Fn_ics]);

            }

Moderiert von Christian S.: Code- durch C#-Tags ersetzt

funcry · Verfasst: Sa 14.02.09 16:17

Zitat:

da werden ja auch haufenweise invariante Werte neu berechnet

Danke für den Hinweis!

Die Ausführungsgeschwindigkeit verbessert sich dadurch von 0,74 Sekunden auf 0,68 Sekunden (100.000 Durchgänge).

Das verbessert die Situation, aber ich muss weiter nach einer parallelen Lösung suchen. Ich sehe das problem darin, dass die Berechnungen zu kurz für einen eigenen Thread sind - auch wenn diese sich sehr oft widerholen. Das Problem ist, jede Wiederholung greift auf das Ergebnis der vorherigen Berechnung zu.
Ein anderer Ansatz den ich getestet habe war die Berechnungen in z.B. 50 parallel instantiierten eigenen Objekten auszuführen, und danach die Ergebnisse zu synchrobnisieren. Dies ist möglich wenn ich die jeweiligen Veränderungen speichere, und am Schluss die gespeichernten Werte übernehme. Dadurch entsteht ein höherer Rechenaufwand welcher durch die zusätzlichen Thread gerade so aufgefangen wurde. Jedoch benötige ich für die gleichen Ergebnisse dann auch mehr Durchgänge.

Vermutlich gibt es eine Lösung für mein Problem, aber ich stehe noch auf dem Schlauch :/

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Was genau berechnest du da eigentlich?

Die Matrix ist bei den Zeiten wahrscheinlich relativ klein, oder?

Ansonsten würde ich das blockweise threaden, also in etwa so:

for(int i = 0 ; i<n ; i+=BLOCKSIZE)

ParallelFor(int ii=0 ; ii<BLOCKSIZE; ...

sry, kenn die Syntax vom ParallelFor nicht

funcry · Verfasst: Sa 14.02.09 17:05

Zitat:

Was genau berechnest du da eigentlich?

Ein einfaches Optimierungsverfahren.

Dank dem Forum bin ich jetzt sicher, dass Aufgrund der zu kurzen Berechnungen _momentan_ ein anderer Ansatz nötig ist. Diesen werde ich jetzt testen. Übertragen gesagt, die Schlacht ist erstmal verloren, aber für den Krieg sehe ich noch Chancen

Mehr Informationen gerne wenn ich mit meinem privaten Projekt einen besser entwickelten Stand erreicht habe.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme