Threads auf Arbeitsspeicher auslagern

[Waller66]

Hallo wollte mal Fragen ob Threads in C++ zwangsläufig die CPU benutzen müssen, will große Datenmengen verarbeiten und es wäre nett wenn man das irgendwie beschleunigen könnte

wie bekomme ich die schnellste bearbeitung hin ? (außer weglassen von redundanten aktionen)


Danke im vorraus :*

[warfley]

Originally Posted by Waller66

Hallo wollte mal Fragen ob Threads in C++ zwangsläufig die CPU benutzen müssen, will große Datenmengen verarbeiten und es wäre nett wenn man das irgendwie beschleunigen könnte

Nein du kannst z.B. mit Nvidia CUDA auch die GPU verwenden die deutlich besser parallelisieren kann

Originally Posted by Waller66

wie bekomme ich die schnellste bearbeitung hin ? (außer weglassen von redundanten Aktionen)

Kommt drauf an, du könntest einen Algorithmus mit besserer asymptotischer Laufzeit verwenden, du kannst deinen Code auch natürlich optimieren durch effizientere Funktionen, und das weglassen von aufwendigen mitteln (Komfort Einbußen, z.B. c statt C++), für konstante laufzeitverbesserung. Du kannst mehr parallelisieren (siehe oben mit z.B. GPU), du könntest eine andere Programmiersprache nehmen (z.B. Fortran). Aber ohne code kann ich dir hier viel erzählen

[Shadow992]

Originally Posted by warfley

Nein du kannst z.B. mit Nvidia CUDA auch die GPU verwenden die deutlich besser parallelisieren kann


Kommt drauf an, du könntest einen Algorithmus mit besserer asymptotischer Laufzeit verwenden, du kannst deinen Code auch natürlich optimieren durch effizientere Funktionen, und das weglassen von aufwendigen mitteln (Komfort Einbußen, z.B. c statt C++), für konstante laufzeitverbesserung. Du kannst mehr parallelisieren (siehe oben mit z.B. GPU), du könntest eine andere Programmiersprache nehmen (z.B. Fortran). Aber ohne code kann ich dir hier viel erzählen

Wichtig zu erwähnen:
Wenn du keine NVIDIA-GPU hast, ist OpenCl das Mittel deiner Wahl. Allgemein empfehle ich dir eher OpenCl, das ist zwar in Details schwieriger, aber läuft nicht nur für GPUs sondern auch CPUs und ähnliches. Außerdem ist es ein (mittlerweile) gut etablierter Standard für etliche Systeme (selbst Smartphone-GPUs unterstützen fast unveränderten OpenCl-Code).

Nichts desto trotz wage ich doch sehr an deinem Algorithmus zur Konvertierung zu zweifeln. Wenn man bedenkt, dass ganze Compiler einen Eingabe-Code (von manchml einigen MBs) in optimierten Maschinencode übersetzen können und zwar in wenigen Sekunden bis einigen Hundert Millisekunden, dann muss deine Methode irgendetwas falsch machen und damit meine ich nicht "nur" unnötige (de-)allokationen oder kein Funktionsinlining bzw If-Kaskaden anstatt von Switch/Case. Hier scheint mir dass du mit solchen kleinen Optimierungen sicher nicht genug rausholst, um die Zeit akzeptabel zu machen.

Aber auch OpenCl erscheint mir wie mit Panzern auf Ameisen zu schießen. Abgesehen davon sind GPUs miserabel beim Sprungbefehl ausführen, das heißt eine Zerteilung von Strings auf der GPU, was sehr oftmit vielen ifs verbunden ist, dürfte ebenso langsam (vielleicht sogar langsamer) sein wie die CPU-Version.

Daher solltest du lieber deinen Code teilen, damit wir dir einen besseren/anderen Algorithmus vorschlagen können und vor allem bleibt die Frage: Wie groß sind die Datenmengen? Und begrenzt wirklich die CPU? In vielen Fällen begrenzt nicht die CPU sondern die Bus-Geschwindigkeit bzw. die Ram-Lese/Schreib-Geschwindigkeit.

[Waller66]

danke für die infos ne ich würde den split und das füllen der felder per cpu machen wollen und dann das größere rechnen per gpu. vielen dank für den ganzen input

Originally Posted by Shadow992

Daher solltest du lieber deinen Code teilen, damit wir dir einen besseren/anderen Algorithmus vorschlagen können und vor allem bleibt die Frage: Wie groß sind die Datenmengen? Und begrenzt wirklich die CPU? In vielen Fällen begrenzt nicht die CPU sondern die Bus-Geschwindigkeit bzw. die Ram-Lese/Schreib-Geschwindigkeit.

Multi Threading Analysis, so 1.5 gb zum lesen. Ich würde das so machen der soll n threads aufmachen die analysieren und einen der liest und die anderen greifen nur auf die ergebnisse von dem lese thread zu, sodass die anderen threads solang wie möglich kombinationen durch gehen bis weitere array felder zum verarbeiten der infos da sind.

macht if oder switch case nen unterschied beim speed, sry habe noch nie auf der ebene gearbeitet.

[Shadow992]

Originally Posted by Waller66

danke für die infos ne ich würde den split und das füllen der felder per cpu machen wollen und dann das größere rechnen per gpu. vielen dank für den ganzen input



Multi Threading Analysis, so 1.5 gb zum lesen. Ich würde das so machen der soll n threads aufmachen die analysieren und einen der liest und die anderen greifen nur auf die ergebnisse von dem lese thread zu, sodass die anderen threads solang wie möglich kombinationen durch gehen bis weitere array felder zum verarbeiten der infos da sind.

macht if oder switch case nen unterschied beim speed, sry habe noch nie auf der ebene gearbeitet.

Wenn "Analysis" wirklich für Mathematik Analysis steht und du mit vektoren/matrizen und sehr wenigen ifs/whiles/etc. arbeiten musst, dann dürfte OpenCl/CUDA doch einen enormen boost bringen.

Wenn Analysis für "analysieren von Texten" o.ä. steht, dann kannste die GPU entgültig vergessen. Denn darin ist die GPU wirklich mehr als miserabel.

Also was genau ist Analysis bei dir bzw. was willst du konkret machen? Texte aufsplitten? Formeln berechnen? ...

Prinzipiell gibt es zwei sinnvolle Aufteilungen für die Parallelisierung:
Single Data Multiple Instruction: Jeder Thread bekommt nur einen kleinen Teil der Eingabedaten, muss darauf aber lange/aufwendige Berechnungen ausführen.
Multiple Data Single Instruktion: Ein Thread macht genau eine Aufgabe (vergleichbar mit Fließbandarbeit).

Alles in allem is ohne große Optimierung meistens SDMI schneller, denn ein Datenset lässt sich normalerweise easy in 4-16 Teile splitten (je nach CPU) mit der dann jeder Kern machen kann was er will. Damit erreicht man dann auch fast 400%-1600% (je nach CPU) SpeedUp, obwohl es ja immer Overhead bei Kommunikation o.ä. gibt.

Das heißt lass lieber von der Idee ab das Ganze als Fließband zu machen und teile deine Texte in 4-16 gleich große Teile, wobei jeder Thread sein eigens Süppchen kocht.

Aber alles in allem wäre es praktisch Details zu wissen, damit wir dir konkrete Ideen/Pseudocode liefern können.

Ifs vs Switch
Switch ist in manchen Umständen nichts anderes als viele Ifs, manchmal lässt sich das aber auch (vom Compiler) in eine Sprungtabelle oder binäre Suche umwandeln, dann ist es schneller als der naive If-Ansatz.

[Waller66]

Alles klar, ne mit analysis meinte ich einfach nur rechnen mit arrayfeldern, geht aber auch durch einige switch case bedingungen. weil das rechnen immer bedingt wird, aber einige davon könnte ich an den lese prozess hängen.

pro durchgang müsste der thread trotzdem noch so min 5- max 20 cases durchlaufen, dann doch lieber cpu lassen ?

will irgendwie die gpu mit nutzen können sonst ist mein ansatz zwar gut bringt aber mir vtl zu wenig sodas sich der aufwand nicht lohnt.

ist es den leicht alle cpu kerne arbeiten zulassen, gibt es da irgendwie mittel und wege das leicht zu gestalten, bin noch recht neu in c++

[Shadow992]

Originally Posted by Waller66

Alles klar, ne mit analysis meinte ich einfach nur rechnen mit arrayfeldern, geht aber auch durch einige switch case bedingungen. weil das rechnen immer bedingt wird, aber einige davon könnte ich an den lese prozess hängen.

pro durchgang müsste der thread trotzdem noch so min 5- max 20 cases durchlaufen, dann doch lieber cpu lassen ?

will irgendwie die gpu mit nutzen können sonst ist mein ansatz zwar gut bringt aber mir vtl zu wenig sodas sich der aufwand nicht lohnt.

ist es den leicht alle cpu kerne arbeiten zulassen, gibt es da irgendwie mittel und wege das leicht zu gestalten, bin noch recht neu in c++

Poste doch mal deinen Code/Details oder wenn du den Code nich teilen willst, umschreibe es mit Pseudo-Code, sonst können wir da viel philosophieren und raten...

[Waller66]

wie mache ich die kommunikation zwischen den threads, Pseudo-Code mäßig ist es doch beschrieben. geht in dem nicht lese sondern rechne prozess noch 5-20 if bedingungen durch bevor der rechnet. das soll 80% oder mehr der leistung ausmachen und dann die file nach und nach laden. sodass die rechne threads immer beschäftigt sind und nur darauf warten wenn sie fertig sind (weil sie etwas schneller sind) ob der lese thread neue daten bereit gestellt hat in den arrays.

[Shadow992]

Originally Posted by Waller66

wie mache ich die kommunikation zwischen den threads, Pseudo-Code mäßig ist es doch beschrieben. geht in dem nicht lese sondern rechne prozess noch 5-20 if bedingungen durch bevor der rechnet. das soll 80% oder mehr der leistung ausmachen und dann die file nach und nach laden. sodass die rechne threads immer beschäftigt sind und nur darauf warten wenn sie fertig sind (weil sie etwas schneller sind) ob der lese thread neue daten bereit gestellt hat in den arrays.

Naja es wäre wichtig zu wissen was genau deine Eingabe-Daten sind und was genau du als Ausgabe erwartest.
Wenn du es nicht "irgendeinem bekannten" Verfahren zuordnen kannst, wäre eine Umschreibung ala

Func calculatePart1(int* array)
   if ...
    // Add always 3 array-entries up to one entry and push it to newArray
  EndIf

  int someValue=calculataPart2(newArray)
  return someValue
EndFunc

Func calculatePart2(int* array)
   // calculate StandardDeviation
   // ...
   return standardDevArray
EndFunc

Sehr hilfreich, denn "5-20 Ifs" kann viel sein. Es könnte etwas sein wie

std::string str= ... // some big string
if ( str.length>1000 && str[0]!='A')
{

}

Dieses If wäre praktisch unmöglich "sinnvoll" auf die GPU zu bringen (mit sinnvoll meine ich einen entsprechenden SpeedUp zu generieren).

Dagegen diese if ist perfekt geeignet für die GPU:

float* array;
if ( Mean(array)<10 )
{

}

da sie super parallelisierbar ist mit OpenCl:

__kernel void main(__global const float *src, __global float* mean, __local srcSize)
{
   int globalSize=get_global_size(0);
   float count=0;
   float localMean=0.0;
   int tidOrig = get_global_id(0)

   for(int tid = tidOrig;tid<srcSize;tid+=globalSize)
   {
       localMean+=src[tid];
       count++;
   }
   mean[tidOrig]=localMean/count;
}

Anschließend muss die CPU nur noch über rund 200-1000 Werte iterieren und aufsummieren. Aber es muss angemerkt werden, dass sich nur ein SpeedUp bei entsprechend vielen Werten ergibt (mehreren Millionen Werten), sonst limitiert der Bus/der Overhead und man kommt praktisch bei 0 oder einem sehr kleinen SpedUp raus.

MultiThreading in C++11 ist relativ einfach. Kommunizieren können die Threads "einfach" über gemeinsame Speicherbereiche/globale variablen.

[Waller66]

3,12 mio und vielen vielen dank genau das beantwortet was ich wissen wollte, wie immer top Shadow992.op=true

aber eine frage habe ich noch, ist es redundant wenn man in funktionen immer variablen neu erzeugt oder sollten einmal fix global erzeugt werden, in dem bereich geschwindigkeit kenne ich mich überhaupt nicht aus :/ bislang hatte ich noch nicht so große projekte.

oder zb sowas :
double blub = numericUpDown1.value; // die variable ist doch schon durch die form drin , ist quasi nichts an speicher aber unnötig das dann noch in eine weitere variable zu schreiben oder ?

und ich stocke irgendwie noch in der überlegung wie ich den lese thread angleiche an die rechnen threads. sollte der immer fix eine gewisse menge laden, rechnen,laden rechnen oder durch gehend lesen und das array in der laufzeit der thread mit daten füllen, aber ich glaub das gibt irgendwie probleme

[Shadow992]

Originally Posted by Waller66

3,12 mio und vielen vielen dank genau das beantwortet was ich wissen wollte, wie immer top Shadow992.op=true

aber eine frage habe ich noch, ist es redundant wenn man in funktionen immer variablen neu erzeugt oder sollten einmal fix global erzeugt werden, in dem bereich geschwindigkeit kenne ich mich überhaupt nicht aus :/ bislang hatte ich noch nicht so große projekte.

oder zb sowas :
double blub = numericUpDown1.value; // die variable ist doch schon durch die form drin , ist quasi nichts an speicher aber unnötig das dann noch in eine weitere variable zu schreiben oder ?

Das sind Mikro-Optimierungen, die dir praktisch jeder Compiler abnimmt. So viel wie ich mitbekommen habe macht dir GNU z.B. automatisch (ab o1 glaub ich sogar schon) aus dem:

for (int i=0;i<100;i++)
{
  double d=0;
  // mache was mit d
}

Das hier:

double d;
for (int i=0;i<100;i++) 
{
  d=0;
  // mache was mit d
}

Also an solchen Sachen solltest du echt sparen. Schreib den Code so wie er für dich am verständlichsten ist und der Compiler wird dir jedemenge "verzeihen" und trotzdem das Schnellste draus machen.

Wenn es um Speed geht und man Algorithmen nicht verändern/beschleunigen kann, dann sollte man hauptsächlich nur in 3 Richtungen optimieren (wenn überhaupt...):

1. Einen eigenen Allokation-Helper machen, der new/delete ersetzt. Dieser Helper holt sich immer gleich einige MB an Speicher und zerteilt diesen Speicher dann bei jedem "new" in das entsprechende Objekt bzw. bei "delete" markiert es einen Bereich wieder als "verwendbar".
Dadurch spart man sich die endlosen Wege übers Betriebssystem (bei new/delete) und kann so schon deutlich Geschwindigkeit gut machen.

2. std::string durch char* ersetzen (das lohnt sich vor allem wenn man den String eh Zeichenweise durchgehen muss und kaum std::string-Methoden verwendet)

3. Cache-optimiert auf den Speicher zugreifen. Das heißt alle Werte, die nahe beieinander liegen(vor allem in großen Arrays) sollen auch nahe beieinander verwendet werden.
Gut:

char* str = new char[100001];
for(i = 0; i<100000; i++)
{
  if (str[i] == 'A' && str[i+1]=='B')
  {
    // ...
  }
}

Schlecht:

char* str = new char[100001];
for(i = 0; i<50000; i++)
{
  if (str[i] == 'A' && str[i*2]=='B')
  {
    // ...
  }
}

Die restlichen Optimierungen, die es noch so gibt, bringen nur selten genug SpeedUp als dass es sich lohnen würde, groß Zeit in das unleserlich machen von Code zuinvestieren.
Vorausgesetzt natürlich, dass man die " Standard-Optimierungen" wie Doppelte-Berechnungen, map statt vector (wenn man oft Werte suchen muss), usw. schon angewendet hat.

Edit:
Der Lese-Thread sollte entweder durchgehend auch lesen (dann braucht es aber eine Art von Synchronidation z.B. über Mutex oder ein entsprechendes "Finished"-Bit o.ä.) oder einmal komplett alles lesen wobei ich zu komplett lesen tendiere, denn 1,5GB sind extrem schnell in den RAM geladen. Ansonsten, wenn der Speicher wirklich knapp wird, kannst du es natürlich auch stückweise einlesen, wobei die Stücke dann schon ziemlich groß sein sollten.

[Waller66]

ist es möglich über eine form eine c++ datei oder code zu laden und den dann aus zu führen wenn ja wie , ich hasse c++ für den komplexeren syntax aber liebe die einsatz möglichkeiten :P

ist sowas per gpu auslagerbar ?
ist nur rechnen mit zahlen werten

 void blav(int s,int *pa,double *p) // vtl anderer datentyp als string
	  {
		 switch(s)
		 {
		 case 1: //
			 if(TTCOunter==0)  TT[TTCOunter] = TT[sizeof(TT)] + (p- TT[sizeof(TT)])/pa;
			 else TT[TTCOunter] = TT[TTCOunter-1] + (p-TT[TTCOunter-1])/pa;
			 break;
		 // 4 cases
		 }

soll ich solche ifs einfach in mehre switches dann verschachteln

[Shadow992]

Originally Posted by Waller66

ist es möglich über eine form eine c++ datei oder code zu laden und den dann aus zu führen wenn ja wie , ich hasse c++ für den komplexeren syntax aber liebe die einsatz möglichkeiten :P

ist sowas per gpu auslagerbar ?
ist nur rechnen mit zahlen werten

 void blav(int s,int *pa,double *p) // vtl anderer datentyp als string
	  {
		 switch(s)
		 {
		 case 1: //
			 if(TTCOunter==0)  TT[TTCOunter] = TT[sizeof(TT)] + (p- TT[sizeof(TT)])/pa;
			 else TT[TTCOunter] = TT[TTCOunter-1] + (p-TT[TTCOunter-1])/pa;
			 break;
		 // 4 cases
		 }

soll ich solche ifs einfach in mehre switches dann verschachteln

Form in C++:
Ist gar nicht so schwer, aber du kannst natürlich auch eine DLL erstellen oder eine Exe-File, die du dann aufrufst.

Code auf GPU:
Theoretisch schon vorallem weil mir die if nicht unbedingt nötig aussieht.

Code allgemein:
Bist du sicher dass dein Code wirklich zu 100% richtig ist und das macht was du willst?
Die Verwendung von SizeOf in Kombination mit dem Array-Zugriff sieht mir äuserst suspekt aus. Auch dass du p als Pointer deklarierst, aber "nur" mit ihm rechnest als wäre es ein normaler int sieht komisch aus (dasselbe gilt für pa).

If vs Switch:
Bei wenigen Cases in Switch wird der Compiler dir wahrscheinlich eh ne If-Kaskade erstellen, daher ist das relativ witzlos für ifs mit weniger als 3 Elses (bzw. Else ifs).

[Waller66]

zu dem bsp code danke bin noch nicht so im syntax drin, hatte nen array pointer use als vergleich genommen und cool danke für die ganzen infos

sizeof wird benutzt weil er das array von links nach rechts füllt und dann vorne wieder überschreibt wenn der counter für die position des aktuellen werts kleiner ist muss der den halt zurück setzen und er benutzt dann wenn auf 0 der
aktuelle wert ist , ist bei sizeof(ar) der vorherige wert auf den er zugreifen muss, normal beim aktueller position -1

und ich meine c++ code aus einer datei lesen und den dann auf die daten anwenden. also der soll den code die funktion ausführen, oder meinst du das ich nur die c++ datei zu ner dll irgendwie per befehl kompelieren lasse und dann die dll immer aufrufe.

[Shadow992]

Originally Posted by Waller66

zu dem bsp code danke bin noch nicht so im syntax drin, hatte nen array pointer use als vergleich genommen und cool danke für die ganzen infos

sizeof wird benutzt weil er das array von links nach rechts füllt und dann vorne wieder überschreibt wenn der counter für die position des aktuellen werts kleiner ist muss der den halt zurück setzen und er benutzt dann wenn auf 0 der
aktuelle wert ist , ist bei sizeof(ar) der vorherige wert auf den er zugreifen muss, normal beim aktueller position -1

und ich meine c++ code aus einer datei lesen und den dann auf die daten anwenden. also der soll den code die funktion ausführen, oder meinst du das ich nur die c++ datei zu ner dll irgendwie per befehl kompelieren lasse und dann die dll immer aufrufe.

Die C++ Datei/Funktionen zu ner DLL kompilieren und dann von C#/AutoIt/Python/whatever aus aufrufen.