Multihreading unter Windows und Linux

[[Moepi]1]

Ich weiß nicht so recht, ob das hier reinpasst oder doch eher ins Programmierforum gehört. Aber da ich eher mit Linux auf Kriegsfuß stehe, denke ich passt es ganz gut hier mit rein. Es geht um folgendes:

Für die Uni hab ich ein kleines Benchmark programmiert, das ne schnelle Fourier Transformation ausführt. Geschrieben hab ichs in C++ mit Inline Assembler. Es gibt 2 Varianten:

1) Single-Thread Lösung (simple iterative Schleife)
2) Dual-Thread Lösung (Datenfluss aufgebrochen, eine Barriere, die einmal durchlaufen wird, zur Threadsynchronisation)

Das Proggie läuft unter Windows und Linux. Jetzt kommt das eigentlich faszinierende, was mir Kopfschmerzen macht. Auf Dualcore Prozessoren liefert die Dual-Thread Lösung unter Linux keine besseren Ergebnisse als die Single-Thread Lösung. Um hier was zu messen, müssen die Transformationen schon verdammt lang werden und da werden die Messwerte wieder durch andere Faktoren beeinträchtigt.
Unter Windows hingegen zeigen sich mit der Dual-Thread Lösung Leistungssteigerungen schon bei relativ kleinen Transformationen mit nur wenigen KB Testdaten Performancesteigerungen um bis zu 40%. Das Leistungsdelte wird bei größeren Datenmengen geringer, was aber wohl daran liegt, dass ich die Prozessorkerne gegenseitig ums Speicherinterface kloppen. So gesehen nicht verwunderlich.

Aber woher kommts nun, dass ich unter Windows Leistungsverbesserungen habe und unter Linux eher noch Verschlechterungen? Die Codes sind praktisch identisch. Klar, unter Linux is die pthread gefragt, unter Windows die AFX. Aber der Code an sich is identisch und ob ich jetzt unter Windows oder unter Linux ne Barriere mit Semaphoren und Mutexes programmiere sollte ja egal sein - noch dazu ist es nur eine Barriere pro Transformation.
Es kann ja eigentlich fast nur noch am Scheduling der Betriebssysteme liegen...


Kennt jemand von Euch ähnliche Probleme oder weiß jemand ne gute Seite, wo die Scheduler von Windows und Linux verglichen werden? So kann ich den Code ja nicht an die Öffentlichkeit lassen...


/Edit: Ja, der Kernel is SMP fähig!

 

[scsi]

Kernel auch richtig gebaut?SMP und multithreat compiliert?

 

[gehacktesmacher]

Stimmt, guter Einfall. Mit nem DualCore System unter Linux bringts nicht wirklich was wenn man kein SMP in den Kernel integriert hat

 

[scsi]

Ja das sollte man schon reinpacken sonnst gibts keine 2 prozessoren und smt auch mit rein machen dann denke ich wirds auch klappen mit deinem programm mfg scsi

 

[[Moepi]1]

Ja das hätte ich vielleicht dazuschreiben sollen. Die Linuxtestumgebung ist Gentoo 2600.1 Live. Der 2.6er Kernel ist selbstverständlich ein SMP Kernel...

 

[Siberian..Husky]

also eigentlich hat linux einen ganz hervorragenden cpu scheduler und skalliert mit mehreren cpus deutlich besser als die meisten anderen unixen, und vermutlich auch als windows. allerdings bin ich mir nicht sicher inwieweit der cpu scheduler bei linux überhaupt für threads zustädig ist. früher konnte der zumindest nur prozesse. allerdings gibt es mitlerweile einige thread basierte server anwendungen für linux, das müsste sich also eigentlich geändert haben.

ein paar mehr informationen wären aber schon sinnvoll:
läuft dein gentoo wirklich von cd? eine livecd ist auf kompatibilität und wenig platz ausgelegt - da kann man eigentlich keine höchstleistungen erwarten.

welcher kernel wird genau verwendet? was den scheduler angeht hat sich seit dem ersten 2.6ern einiges getan. man sollte generell immer den neusten stabilen kernel verwenden wenn man die beste performance haben will .

welche glibc version? und is nptl aktiviert? am besten die neuste stable glibc von gentoo mit nptlonly useflag, um ganz sicher zu gehen .


wenn das geklärt ist könntest du ja mal das hier probieren. vielleicht lässt sich damit was rauskriegen.

wenn das alles nichts hilft guck mal hier. da gibts einige interessante links, unteranderem auch zu einer newsgroup wo du sicher jemanden finden wirst der dir helfen kann.

 

[boarder-winterman]

Gentoo 2006.1 Live dürfte Kernel 2.6.17-r7 dabei haben, also "recht" neu

 

[[Moepi]1]

Ich vermute den Fehler nach wie vor nicht direkt bei Linux. Ein Kommilitone macht dasselbe mit Matrixmultiplikationen und der bekommt bis zu 96% Performancezuwachs durch Threading. Obs an meinem Algorithmus liegt, also ein Programmierfehler ist? Weiß nicht so recht. Zumindest liefert die Transformation korrekte Ergebnisse und bei sehr großen Transformationen mit mehreren MB Testdaten kommt ja auch ein zu erwartender Performancegewinn (auch wenn die Messergebnisse dort stark schwanken - ich tendiere dazu, das auf das Speicherinterface als Flaschenhals zu schieben, da ich ne kranke Anzahl verteilter Speicherzugriffe hab).

Ich hab das ganze im Anhang mal visualisiert. Denselben Test unter Windows und Linux. Wie man sehen kann, profitiert Linux in einem Bereich von 192KB bis 3MB Testdaten praktisch garnicht vom Threading und bleibt mit der Singlethreadimplementierung gleich auf. Erst ab 6MB Testdaten passiert dann endlich das, was man erwarten würde! Da das eben so plötzlich nach oben schnellt, vermute ich, dass der Scheduler von Linux da seine Finger im Spiel hat und bei kleinen Transformationen beide Threads auf nur einen Kern schiebt.

Zu beachten sind die Ausführungszeiten, in denen wir uns bewegen. Das rangiert von 7µs (ka Mikrosekunden, nicht ms) bei den kleinsten Transformationen und steigt so Pi mal Daumen pro Arrayvergrößerung um den Faktor ~2,2 an. Bei 12MB Testdaten sind wir dann bei knapp 1s pro Transformation im Singlethreadalgorithmus und bei ca. 600ms beim Multithreading. Da ja auch nicht die komplette FFT parallelsiert wird, sondern nur deren Kernel, ist ein Performancezuwachs von 50% ordentlich - ne Barriere is ja auch noch drinnen.

Bei den ganz kleinen Transformationen kommen die negativen Werte einfach dadurch zustande, dass es bei ner Ausführungszeit von wenigen µs einfach länger dauert 2 Threads zu erstellen und zu synchronisieren, als es einfach mit einem Thread zu machen. Dafür können weder Windows noch Linux noch ich was. Die FFT hat halt nunmal nur ne asymptotische Komplexität von n*log(n)...


Meine Theroie geht wie schon erwähnt eben in die Richtung, dass der Linuxkernel nur alle x ms Threads auf Prozessoren verteilt. Terminieren Threads zu schnell, werden sie nur auf einem Kern ausgeführt. Allerdings hätte ich das gern irgendwo in nem technischen Dokument schwarz auf weiß stehen... :/
Bei diesen riesigen Testdatenmengen kann ich keine Vergleiche mehr zwischen verschiedenen CPUs durchführen, da hier einfach zuviele andere Faktoren ne Rolle spielen.

 

[FreddyMercury]

Du solltest in der make.conf auch angeben, das du mehrere CPU's hast. Obwohl das eher nur fürs Kompilieren genutzt wird.
Hast du auch die glibc in geeigneter Version dafür?

 

[Siberian..Husky]

du könntest ja einfach mal probieren die threads vor der eigentlichen berechnung einfach mal idlen zu lassen. vielleicht reicht das um den scheduler zu überlisten .

ansonsten würde ich einfach mal davon ausgehen das der scheduler abhängig vom kernel timer ist, und so je nach einstellung nur 100 - 1000 mal pro sekunde zu werke geht.


allerdings würde ich an deiner stelle lieber jemanden fragen der sich mit sowas auskennt . da wirst du in diesem forum wohl niemanden finden. wiegesagt, weiter oben gibts einen link zu einer threading-newsgroup....

 

[[Moepi]1]

du könntest ja einfach mal probieren die threads vor der eigentlichen berechnung einfach mal idlen zu lassen. vielleicht reicht das um den scheduler zu überlisten .

ansonsten würde ich einfach mal davon ausgehen das der scheduler abhängig vom kernel timer ist, und so je nach einstellung nur 100 - 1000 mal pro sekunde zu werke geht.


allerdings würde ich an deiner stelle lieber jemanden fragen der sich mit sowas auskennt . da wirst du in diesem forum wohl niemanden finden. wiegesagt, weiter oben gibts einen link zu einer threading-newsgroup....

Danke Dir auf jeden Fall. Ich glaub auch dass das irgendwo am Scheduling der Betriebssysteme hängen bleibt. Nen Programmierfehler schließ ich einfach mal selbstbewust aus - immerhin läuft der Mist ohne Absturz und bringt auch richtige Ergebnisse...



\Edit:
Ich glaube hier eine Erklärung gefunden zu haben:

Die Begründung für den späteren Performancegewinn unter Linux findet sich in der Art, wie Linux eine Verteilung der Systemlast auf mehrere Prozessoren realisiert. Anders als Windows implementiert Linux für jeden Prozessor einen Prozessqueue. Ein Loadbalancer prüft in einem Intervall von 1ms, unter Last alle 200ms, ob die Prozesse gleichmäßig auf alle Prozessoren verteilt ist. Und eben hier liegt das Problem. Da das System auch vor der Threaderstellung bereits unter Last steht, prüft der Load Balancer nur alle 200ms. Vor der Threaderstellung kann der Load Balancer nichts auf einen zweiten Prozessor verlagern. Werden nun zwei Threads erstellt, so laufen zunächst beide auf derselben physikalischen CPU wie der Prozess, aus dem die Threads erstellt wurden. Im Worst Case dauert es nun 200ms, bevor der Load Balancer reagieren kann. Unter 262144 Datenpunkten liegt die Ausführungszeit auf dem Testsystem unter 200ms für Hin- und Rücktransformation. Da die Threads für jede Transformation neu erstellt werden, existieren unter Linux für weit weniger als 100ms zwei Threads, welche auf zwei Prozessoren verteilt werden könnten. Ab 262144 Datenpunkten leigt die Ausführungszeit schließlich hoch genug, so dass der Load Balancer in Aktion treten kann. Je größer die Zeit wird, in der zwei Threads exisiteren, desto besser funktioniert schließlich die Verteilung auf meherere Prozessoren.