#1 12. Dezember 2013 Zuletzt von einem Moderator bearbeitet: 14. April 2017 Moin moin! Ich soll den Quicksort algorithmus parallelisieren. Und zwar hab ich das so gedacht, dass ich erstmal ein Pivotelement bestimme und danach den zu sortierenden Array aufteile. Nun gehe ich die einzelnen teilarrays parallel durch und mache den ersten Schritt vom quicksort algorithmus nämlich alle Elemente, die kleinergleich dem Pivotelement sind in eine seperate Liste schreiben und alle die größer sind in eine andere Liste schreiben. Mein Problem ist, dass ich diese Listen ja nun für jeden Teilarray habe, sprich für jeden Prozess. Ich will aber diese Listen nun zwischen den Prozessen tauschen und zwar soll der Prozess, der den Anfang des sortierenden Arrays "sortiert", mit dem prozess, der das ende des zu sortierenden arrays durchgeht die Liste mit den kleineren Elementen bekommet und dafür aber die Liste mit den größeren Elementen abgibt Weiß nicht hoffe das ist verständlich, sonst hier: Nun ist mein Problem: Wir bekomme ich diese Listen durchgetauscht... Das Problem ist ja, das die Prozesse da irgendwie miteinander kommunizieren... :/ das ganze soll in C mit OpenMP implementiert werden... Hoffe ihr wisst da nen Weg und wenn es nicht geht dann vielleicht einen alternativen Lösungsweg :/ + Multi-Zitat Zitieren
#2 13. Dezember 2013 AW: Quicksort parallelisieren Am einfachsten wäre es wohl wenn du die Teillisten global anlegst sodass alle Prozesse darauf zugreifen können. Müsstest dann eben den Zugriff per Mutex synchronisieren. Ob das auch das effizienteste ist weiß ich nicht... + Multi-Zitat Zitieren
#3 13. Dezember 2013 AW: Quicksort parallelisieren Mit OpenMP musst du dir eigl. nicht mehr über die Zugriffe Gedanken machen. Du machst dir zwei Partitionen der Eingabe (mit ner parallelen schleife) und arbeitest diese dann mit sections ab. Wie es im dritten und vierten Ergebnis bei Google gezeigt wird + Multi-Zitat Zitieren
#4 15. Dezember 2013 AW: Quicksort parallelisieren am besten nimmst du den quicksort yaroslavski oder wie der chinese hiess ;-) der lässt sich glaube ich noch besser paralelisieren wegen der 2 pivot elemente. + Multi-Zitat Zitieren