Ankündigung

Einklappen
Keine Ankündigung bisher.

Vishkin-Algorithmus 1 Summation

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Vishkin-Algorithmus 1 Summation

    Ich habe ein Problem mit einem Algorithmus, um Werte parallel aufzuaddieren.
    PHP-Code:
    for Pi<= <= n pardo
       B
    (0,i) := A(i)
       for 
    := 1 to log(n) do
          if 
    <= n/(2^h)
             
    then B(h,i) := B(h-1,2*i-1) + B(h-1,2*i)
             else 
    stay idle // mache nichts 
    pardo heißt, dass das folgende nicht in einer Schleife abläuft, sondern in unterschiedlichen Prozessen (in diesem Fall Threads). Pi steht für den i-ten Prozess. Die Ausgangsdaten liegen im A-Array.

    Der Ablauf schaut folgendermaßen aus (von links nach rechts und von unten nach oben):
    Code:
                                                                         B(3,1)
                                                         /                                 \
                                   B(2,1)                                                                   B(2,2)
                            /                    \                                                   /                 \
                 B(1,1)                               B(1,2)                             B(1,3)                           B(1,4)
                /     \                              /    \                              /    \                            /    \
    B(0,1)=A(1)   B(0,2)=A(2)  B(0,3)=A(3)  B(0,4)=A(4)  B(0,5)=A(5)  B(0,6)=A(6)  B(0,8)=A(7)  B(0,8)=A(8)
    Das Problem ist, dass sich die Threads in die Quere kommen können. Dass es B(2,1) vielleicht schon gibt, B(1,2) jedoch noch nicht. Irgendwie muss ich vielleicht mit join arbeiten. Dass B(2,1) und B(2,2) erst dann berechnet werden dürfen, wenn B(1,x) berechnet wurden. D. h. man muss das immer schichtweise von unten nach oben berechnen.

    Aber ich habe keine Ahnung, wie ich hier mit join arbeiten könnte. Denn z B der Prozess 1 ist erst dann fertig, wenn er bei B(3,1) angekommen ist. Er müsste aber auf dem Weg dorthin schon mehrmals auf andere Prozesse warten.


  • #2
    Das Stichwort ist Synchronisation, vllt. würden sich hier eine Art Semaphore anbieten, so dass erst mir der nächsten Ebene angefangen werden darf, wenn die Semaphore der Ebene darunter gleich der Anzahl der Elemente ist.
    mysql ist veraltet Mails senden: Ohne Probleme und ohne mail()
    PHP-Code:
    echo 'PS: <b>Meine Antwort ist keine Lösung, sondern nur eine Hilfe zur Lösung.</b>'

    Kommentar


    • #3
      Und wiedermal sehe ich den PHP-Bezug dieses Threads nicht.

      [MOD: Verschoben]
      --

      „Emoticons machen einen Beitrag etwas freundlicher. Deine wirken zwar fachlich richtig sein, aber meist ziemlich uninteressant.
      Wenn man nur Text sieht, haben viele junge Entwickler keine interesse, diese stumpfen Texte zu lesen.“


      --

      Kommentar


      • #4
        Das Stichwort ist Synchronisation, vllt. würden sich hier eine Art Semaphore anbieten, so dass erst mir der nächsten Ebene angefangen werden darf, wenn die Semaphore der Ebene darunter gleich der Anzahl der Elemente ist.
        Also mir wäre heute folgendes eingefallen:

        Ich definiere noch eine zusätzliche Klasse. Diese Klasse hat die Aufgabe, einen Zähler zu verwalten. Zu Beginn ist dieser Zähler 0. Den Zähler kann man inkrementieren, auf 0 zurücksetzen und auslesen.

        Von dieser Klasse erzeuge ich 1 Instanz. Diese Instanz übergeben ich allen Threads. Diese Instanz wäre eine Resource, die von allen Threads genutzt werden würde.

        Jeder Thread würde am Ende eines Schleifendurchlaufs den Zähler inkrementieren. Danach würde der Thread aktiv darauf warten, dass der Zähler der Anzahl der Threads entspricht. Dann weiß man, dass eine Ebene des Baums vollständig abgearbeitet wurde. Danach resette ich den Zähler und in allen Threads kann der nächste Schleifendurchlauf beginnen.

        Was mir daran nicht gefällt, ist dieses aktive Warten. Im Gegensatz zu einem join gehen bei einem aktiven Warten Systemresourcen drauf.

        Ich werd mich in der nächsten Zeit mal mit dem Thema Semaphore beschäftigen. Spätestens sobald ich das erledigt habe, mach ich wieder einen Eintrag hier.

        Kommentar


        • #5
          Semaphore steht unter Windows leider nicht zur Verfügung. Könnte ich nur nachbauen. http://php.net/manual/en/intro.sem.php

          Kommentar


          • #6
            Oder mittels einer VM ein Linux installieren...
            GitHub.com - ChrisAndChris - RowMapper und QueryBuilder für MySQL-Datenbanken

            Kommentar


            • #7
              Oder du benutzt eine Programmiersprache, die wirklich für parallele Programmierung geeignet ist. PHPThreads sind in der Praxis einfach unbenutzbar. Dinge, die in Java oder sogar C++ total einfach sind, kann man nur umständlich in PHP umsetzen.
              Crashkurs zum Thema Rechtschreibung: normalerweise (normaler weise oder normaler weiße), Standard (Standart), eben (ebend)

              Kommentar


              • #8
                Nachdem es in Java mehr Literatur zur parallelen Programmierung gibt als in PHP, lerne ich das aktuell in Java. Sobald ich mich dort durchblicke, schwenke ich wieder zurück zu PHP.
                PHPThreads sind in der Praxis einfach unbenutzbar. Dinge, die in Java oder sogar C++ total einfach sind, kann man nur umständlich in PHP umsetzen.
                Hast du ein Beispiel dafür, das du in PHP und Java implementiert hast, das zeigt, dass es in PHP schwieriger ist?

                So wie ich das verstanden habe, soll es in den objektorientierten Programmiersprachen generell schwierig sein, Threads zu programmieren. Erlangen hat angeblich ein viel besseres Konzept.

                Kommentar


                • #9
                  In Java ist es meiner Meinung nach am besten umgesetzt und total intuitiv. Aber in PHP kann man nur sehr umständlich möglich, die einzelnen Threads miteinander kommunizieren zu lassen und Daten austauschen.
                  Crashkurs zum Thema Rechtschreibung: normalerweise (normaler weise oder normaler weiße), Standard (Standart), eben (ebend)

                  Kommentar


                  • #10
                    Aber in PHP kann man nur sehr umständlich möglich, die einzelnen Threads miteinander kommunizieren zu lassen und Daten austauschen.
                    Was genau stört dich denn? Dass in PHP wait und notify Methoden von Thread(ed) sind?

                    Welches Package meinst du eigentlich? pthreads oder ev?

                    Kommentar


                    • #11
                      Erlangen hat angeblich ein viel besseres Konzept.
                      --

                      „Emoticons machen einen Beitrag etwas freundlicher. Deine wirken zwar fachlich richtig sein, aber meist ziemlich uninteressant.
                      Wenn man nur Text sieht, haben viele junge Entwickler keine interesse, diese stumpfen Texte zu lesen.“


                      --

                      Kommentar


                      • #12
                        Zitat von veryhot Beitrag anzeigen
                        Was genau stört dich denn? Dass in PHP wait und notify Methoden von Thread(ed) sind?

                        Welches Package meinst du eigentlich? pthreads oder ev?
                        Habe ich dir schon in deinem anderen Thread vor Wochen gesagt.
                        Crashkurs zum Thema Rechtschreibung: normalerweise (normaler weise oder normaler weiße), Standard (Standart), eben (ebend)

                        Kommentar


                        • #13
                          Ich habe deine Einträge gefunden. Du warst der, der mir den Tipp gegeben hatte, Java zu lernen. Mache ich grad. Danke. Deine restlichen Einträge in dem anderen Thema sind mir noch zu hoch. Dafür fehlt mir momentan noch das Wissen. Das wird noch ein paar Wochen dauern, bis ich das verstehe.

                          Kommentar

                          Lädt...
                          X