Insertion parallèles & # 8220; & # 8221; dans un trie binaire à Haskell

Question

J'ai une liste de "mots" à n bits.

type BitWord = [Bool]

et un trie qui stocke le mot de haut en bas:

data Tree = Bs Tree Tree  -- Bs (zero_bit) (one_bit)
          | X -- incomplete word
          | B -- final bit of word

J'ai une fonction:

seenPreviously :: BitWord -> Tree -> (Tree,Bool)

La fonction fait défiler les bits du BitWord , tout en descendant dans l'arborescence de l'arbre en partant de gauche à zéro, et inversement. Nous renvoyons une nouvelle arborescence avec ce BitWord "fusionné dans", avec True si nous devions ajouter des sous-arbres à un moment donné (le BitWord n'était pas déjà dans le fichier ) et False sinon.

Je mappe cette fonction sur un [BitWord] en transmettant l’arbre en tant qu’état.

Ma question est la suivante : le parallélisme proposé par Control.Parallel pourrait-il tirer parti de cela? Et si oui, comment puis-je raisonner à propos de la paresse et de l’évaluation de la tête à la forme normale, etc.?

Mon instinct est que je peux insérer (en construisant un sous-arbre) une branche gauche tout en faisant la même chose dans la branche droite, sous la forme de deux threads indépendants. Quelque chose comme:

parallelMapSt :: [ BitWords ] -> Tree -> [Bool]
parallelMapSt [] _ = []
parallelMapSt (w:ws) t = let (b,t') = seenPreviously w t
                             bs     = parralelMapSt ws t'
                          in t' `par` bs `pseq` (b:bs)

Le thread qui évalue b dépend de certains threads précédemment déclenchés (ceux appartenant au BitWords qui partagent un préfixe commun avec w ). , mais pas tous, alors il semblerait qu’il soit possible de travailler en parallèle ici, mais je ne suis vraiment pas sûr.

Answer 1

Cela ressemble à un excellent candidat pour l'utilisation de par lors du parcours dans l'arbre ... Tout comme le point de repère des arbres binaires. Essayez d’écrire des programmes sur ce type et de mesurer l’effet de par .

Answer 2

Renvoyer si un mot était dans le tri séquencera inutilement votre programme. Si vous avez vraiment besoin de ces informations, il sera probablement difficile de les mettre en parallèle efficacement.

Cependant, si nous pouvons reformuler le problème de telle sorte que l'ordre et la disposition des insertions importent peu, le problème est assez simple:

import Control.Parallel

data Tree = Bs Bool         -- ^ is an empty word inserted here?
               (Maybe Tree) -- ^ '0' subtree
               (Maybe Tree) -- ^ '1' subtree
     deriving Show

insertMany :: [[Bool]] -> Maybe Tree
insertMany []  = Nothing
insertMany xss = hasEnd `par` fs `par` ts `pseq` Just (Bs hasEnd fs ts)
 where
    hasEnd = any null xss
    fs = insertMany [ xs | False : xs <- xss]
    ts = insertMany [ xs | True  : xs <- xss]

Je n'ai pas plusieurs cœurs pour le moment, je ne peux donc pas tester cela, mais cela devrait bien évoluer. Nous avons essentiellement une sorte de radix parallèle en quelques lignes seulement - pas trop mal!

Answer 3

Pourquoi ne pas simplement essayer et voir? Chronométrez l'exécution du programme avec 1 thread et plusieurs, et voyez s'il y a une différence. Les étincelles de Haskell sont vraiment très bon marché, alors ne vous inquiétez pas si vous en créez beaucoup.