Suche durch CPU-limitierten Algorithmus

[Eruphus]

Ich will von mir geschriebene Software (Basis für Multiprozessorfähiger SW) testen und suche deswegen einen Algorithmus denn man in einzelne Teile trennen (auf versch. CPUs verteilen) und dann abarbeiten kann.

MFG Ruph

[Simon]

Wie wärs mit Ray Tracing?

[del_4901]

Parallele Algorithmen unterscheiden sich erheblich von ihren sequenziellen Kameraden. Du musst schon etwas spezifischer werden, denn eine allgemeine Lösung gibt es für dieses Problem nicht.


Am besten du sucht dir irgenwas einfaches, wie z.B den parallelen Kruskal.

Aber was ich mich frage was macht deine von dir geschriebene SW? Threads etc. gibt es in Vollendung in BOOST
Das nicht zu nehmen währe ein Rückschritt.

[Eruphus]

Ich hab grad mal bei Wikipedia gelesen, was des is :)

Aber ich hab kein Bock extra SW bez. Raytracing zu entwickeln.
Interesant wäre es, weil man es auf die einzelnen Objekte aufteilen kann und Objekte hintereinander abhängigkeiten abbilden.

Hast du zufällig Source zum Thema RTracing?
wenn ja, auch mit dem notwendig Overhead?




Aber was ich mich frage was macht deine von dir geschriebene SW? Threads etc. gibt es in Vollendung in BOOST
Das nicht zu nehmen währe ein Rückschritt.

Nein, nicht nur Threads. sondern n-Threads die prioritätsgesteuert einzele Teile des gesuchten Algorithmus parallel abarbeiten sollen und voneinander abhängige nacheinander. Das natürlich Verklemmungsfrei.

Ich suche nur i-einen (am besten einfach zu implementierenden) Algo, den ich "zerteilen" und mein Paket damit füttern kann.



Danke für die schnelle Antwort!




Alexander

[del_4901]

bei parallelem RT gibt es sogut wie keinen Overhead.

Ich hab ein gutes Buch dazu:

http://www.amazon.com/Realistic-Tracing-Second-Peter-Shirley/dp/1568811985

[Simon]

Ich hab grad mal bei Wikipedia gelesen, was des is :)

Aber ich hab kein Bock extra SW bez. Raytracing zu entwickeln.
Das dauert vielleicht 2h (für den Anfang :D )...

Interesant wäre es, weil man es auf die einzelnen Objekte aufteilen kann und Objekte hintereinander abhängigkeiten abbilden.

Hast du zufällig Source zum Thema RTracing?
wenn ja, auch mit dem notwendig Overhead?
Raytracing: Theory & Implementation Part 1, Introduction (http://www.devmaster.net/articles/raytracing_series/part1.php) - 7 Artikel mit Source über Raytracing.

@AlphaTier: "Physically Based Rendering" find ich besser als das von dir genannte Buch ;)

[Eruphus]

Also ich hab mich dort mal einglesen und das example source ausgführt.
An dieser Stelle gefällt mir nicht, dass die berechnung pixel für pixel durchgeht.

Ich hätt da eher an einen Algorithmus im stiele eines Alignments gedacht.


Sonnst noch i-welche vorschläge?

[pajofego]

War nicht in der c't eine Reihe über paralleles Programmieren? Wenn ich mich nicht ganz täusche ist da eine Menge gewesen über verteiltes Rechnen inkl. source code und etc.

Gruß

pajofego

[Eruphus]

Um mich noch mal klar auszudrücken :

Es geht hier nicht um "paralleles Programieren" das ist bereits gemacht :rolleyes:

Ich will dieses Stück SW testen und suche deswegen ein stück code...

[pajofego]

Um mich noch mal klar auszudrücken :

Es geht hier nicht um "paralleles Programieren" das ist bereits gemacht :rolleyes:

Ich will dieses Stück SW testen und suche deswegen ein stück code...

Aber doch um verteiltes rechnen oder nicht...? Sowas wie der Algorithmus zum Berechnen von Fraktalen!

[del_4901]

Um mich noch mal klar auszudrücken :

Es geht hier nicht um "paralleles Programieren" das ist bereits gemacht :rolleyes:

Ich will dieses Stück SW testen und suche deswegen ein stück code...
Weist du was, eigendlich solltest du dir selber was aus den Fingern saugen können, wenn du schon soweit bist ...

[ScottManDeath]

Pete Shirleys Raytracing Buch ist knapp geschrieben, wenn man weiß um was es geht, ist es ok, es werden die Grundlagen erklärt und dann recht fix auf den Code verwiesen. Dies muss nicht jedermanns Sache sein.

Naja, seine Vorlesungen waren auch irgendwie unstrukturiert ;(

Code für einen Raytracer findest Du hier: http://www.cs.utah.edu/classes/cs6620/s05/public_html/

[Eruphus]

Weist du was, eigendlich solltest du dir selber was aus den Fingern saugen können, wenn du schon soweit bist ...

Ja, du hast recht :)

War gestern bei Freunden und beim nach Hause gehn is mir eingefallen, dass ich doch einfach QSort nutzen könnte.

Nah dem Teilen der menge durch das pivot kann man leicht die teilbereiche auslagern und unaghängig voneinander berechnen...

Werd das heute mal machen :)

Danke für die Hilfe 3D-Center!

Ruph

[SimonX]

Wie wäre es mit Mandelbrot? Das kann man zu 100% parallel laufen lassen.

Deine Software wird wohl ein Scheduler für parallele Tasks sein, richtig?

[Trap]

Wie wärs mit Rucksackproblem mit DP lösen? Das kann man parallelisieren, hat aber genügend Abhängigkeiten um den Teil des Framework ordentlich zu testen.

[bulla]

Öhm, per bruteforce Passwörter knacken?

[Chris Lux]

Aber was ich mich frage was macht deine von dir geschriebene SW? Threads etc. gibt es in Vollendung in BOOST
Das nicht zu nehmen währe ein Rückschritt.
sorry für ot. aber vollendung würde ich die boost threads nicht nennen. mir fehlt da einfach ein wenig was, bspw. zum modifizieren von thread prioritäten.

[Gast]

Wie wäre es denn mit dem c't-puzzle ?

Es gab da einen Programmierwettbewerb:
http://www.heise.de/ct/puzzle/programme/

Die Lösungsprogramme sind im Quelltext erhältlich und
die schnellen sind für Multithreading ausgelegt.

Gruß,
Gast