Accélérer List.fold avec des threads et des canaux

Question

Ce que j'essaie de réaliser est, ma propre version de List.fold_right ou List.fold_left avec Event Module et Thread Module afin d'accélérer le processus.

(Je suis conscient que Ocaml ne prend pas en charge le multithreading parallèle, mais je suis ici pour le concept)

Mon essai: (bien que je ne suis pas sûr gagné du temps supplémentaire)

open Thread 
open Event 
let rec tapply f start = function 
    | [] -> start 
    | h::t -> let c = new_channel() in 
      let _ = create (fun _ -> sync (send c (f h (tapply f start t))))() 
      in sync (receive c) 

appel tapply:

#tapply (*) 1 [1;2;3;4];; - : int = 24

Answer 1

Il est impossible de paralléliser fonctions pli dans le cas général, comme tous les Intermediat La valeur dépend de toutes les précédentes. Voir Cipher Block Chaining, par exemple. La parallélisation est possible si certaines conditions supplémentaires sont remplies. Exemple 1: S'il est possible de traiter chaque élément de liste comme une fonction (exemple: actions de groupe), vous pouvez exploiter l'associativité des fonctions à l'aide d'une approche de division et de conquête, où vous calculez d'abord la fonction puis l'appliquer à l'élément initial.

Exemple 2: Si la fonction est commutative et que vous utilisez à réduire au lieu d'une opération fois, vous pouvez diviser la liste en sous-listes et de distribution de travail pour les sous-listes, telles que:

open Batteries 

let par_reduce n f l = 
    (* worker thread *) 
    let worker (ch, l) = 
    List.reduce f l |> Event.(sync % send ch) in 
    (* split [l] in [n] sublists *) 
    let k = max (List.length l/n) 1 in 
    let sublists = List.ntake k l in 
    (* create [n] worker threads *) 
    List.map (fun sublist -> 
    let ch = Event.new_channel() in 
    let _ = Thread.create worker (ch, sublist) in 
    ch) sublists 
    (* collect results *) 
    |> List.map Event.(sync % receive) 
    (* and combine those into the final result *) 
    |> List.reduce f 

let factorial n = 
    par_reduce 4 Num.mult_num (List.init n (fun k -> Num.of_int (k+1))) 

let() = 
    Printf.printf "%s\n" Num.(to_string @@ factorial 1000) 

Remarque 1: Ceci utilise la bibliothèque "piles incluses" pour certaines fonctions de confort.

Note 2: Il existe des moyens plus rapides de calculer de grands factoriels - en fait, le code ne divise pas même le travail uniformément -, c'est juste un exemple qui utilise réellement du temps CPU.