Haskell Parallelberechnung mit einem STArray

Question

Ich versuche parallel Berechnung zu tun, und schreibe die Ergebnisse in ein STArray. Ich denke, dieser Code zeigt, was ich versuche zu tun. Ich erhalte jedoch Kompilierungsfehler.

import Control.Monad 
import Control.Monad.ST 
import Control.Parallel 
import Data.Array.ST 

main = do 
    arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int) 
    runSTArray $ do 
     par (writeArray arr (1,1) 17) (writeArray arr (2,2) 23) 
     return arr 
    print arr 

Wie soll ich das tun?

Answer 1

Sie verwenden newArray, die den Typ ST s (STArray s (Int, Int) Int) hat. Allerdings verwenden Sie es im Körper der main-Funktion, was bedeutet, dass alles, was Sie do müssen einen IO Typ haben. ST ist nicht IO, daher können die Typen nicht übereinstimmen.

Sie sollten zuerst die newArray in einen Kontext verschieben, in dem Sie Zugriff auf die ST Monade haben. Dieser Zusammenhang ist natürlich in den Körper runSTArray, so dass der Körper ändern:

runSTArray $ do 
     arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int) 
     par (writeArray arr (1,1) 17) (writeArray arr (2,2) 23) 
     return arr 

Dann müssen Sie wie par verhält sich zu überdenken. par ist zum Erstellen von parallelen reinen Berechnungen und kann nicht für monadische Aktionen verwendet werden; Monaden können überhaupt nicht parallelisiert werden. Insbesondere bietet die ST monad keine Alternativen für parallele Berechnungen; Da parallele Schreibvorgänge in einem Array zu Race-Bedingungen führen können (was passiert, wenn Sie die selbe Zelle überschreiben? Welcher Write zählt und welcher nicht?), ist es hier unsicher, Parallelität zuzulassen. Sie müssen das Array der Reihe nach ändern:

runSTArray $ do 
     arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int) 
     writeArray arr (1,1) 17 
     writeArray arr (2,2) 23 
     return arr 

Die Schreibvorgänge sind jedoch nicht teuer; Es sind die Berechnungen der Werte, die teuer sein können. Angenommen, Sie möchten 17 und 23 im laufenden Betrieb berechnen; Sie können dann wie folgt vor:

let a = someLongCalculation 12534 
    b = a `par` (someLongCalculation 24889) 
writeArray arr (1, 1) a 
writeArray arr (2, 2) b 

Schließlich müssen Sie erkennen, dass runSTArray das Ergebnis Array zurückgibt, so dass Sie es wie folgt speichern müssen:

import Control.Monad 
import Control.Monad.ST 
import Control.Parallel 
import Data.Array.ST 

main = 
    let pureArr = 
     runSTArray $ do 
      arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int) 
      writeArray arr (1,1) 17 
      writeArray arr (2,2) 23 
      return arr 
    in print pureArr 

Ich glaube nicht, dass STArray s die richtige Lösung hier. Sie sollten eine leistungsfähigere Array-Bibliothek wie repa in Situationen verwenden, in denen Sie parallele symmetrische Array-Berechnungen benötigen.

Answer 2

par ist für das Zusammensetzen von reinen Operationen parallel. Sie komponieren wirkungsvolle Operationen. Sie können Par nicht verwenden. Außerdem ist die Parallelität ein Effekt (zumindest wenn sie mit Mutation zusammengesetzt ist) und steht Ihnen in der ST-Monade nicht zur Verfügung. Ich kann Ihnen keinen Ratschlag geben, wie Sie Ihren Code richtig strukturieren können, weil die Dinge zu klein sind, um zu sehen, was Ihr eigentliches Problem ist. Mein allgemeiner Rat ist jedoch, explizite Concurrency-Konstrukte wie fork (in der IO-Monade) oder zu verwenden, um reine Operationen anstelle von Mutatey-Arrays zu verwenden.