Варианты распараллеливания функций в дереве F # - PullRequest
Новая
       21

Варианты распараллеливания функций в дереве F #

3 голосов
/ 16 марта 2011

В моем проекте структура данных представлена ​​следующим образом: 

type 'a Tree =
| Leaf of 'a
| Node of 'a Tree array

Из-за стоимости обхода больших деревьев я должен распараллелить некоторые следующие функции в этой структуре данных:

  • карта
  • * 1009 раза *
  • существует (существует узел, удовлетворяющий сказуемое)
  • уменьшить / преобразовать (необязательно)

Из-за характера проблемы, над которой я работаю, количество ветвей на каждом узле варьируется, а рабочие нагрузки на уровне листьев довольно малы. Первый вопрос: какие варианты следует рассмотреть для параллельного выполнения на дереве. Я пытаюсь использовать функции из модуля Array.Parallel на каждом узле, однако, поскольку накладные расходы параллелизма слишком велики, параллельная версия даже медленнее, чем последовательная версия. Я могу изменить представление массива на List или PSeq, если это необходимо.

Второй вопрос - как контролировать степень параллелизма в этих функциях. Я думаю об управлении по глубине дерева, количеству ветвей в каждом узле, сложности рабочей нагрузки на уровне листьев и количестве листья на дереве, однако, объединяя их вместе, кажется сложным и непредсказуемым.

Ответы [ 2 ]

4 голосов
/ 16 марта 2011

Как насчет отделения обхода от любой другой обработки? Возможно, создайте рабочую очередь (MailboxProcessor - хорошая отправная точка) и, по мере обхода дерева, поставьте в очередь дополнительную работу для фоновой обработки. Это не решает проблему параллельного обхода (которая кажется сложной для всех случаев), но с дополнительной обработкой, отводимой на задний план, она должна пройти довольно быстро. Вы можете экспериментировать с количеством фоновых работников, пока не найдете хорошую степень параллелизма. Все это предполагает, что объем работы, выполняемой для каждого узла, нетривиален.

EDIT

Вот код. Я уверен, что это может быть улучшено. Я должен был выковырять это довольно быстро. Но это показывает основную концепцию. У него только один «фоновый работник», то есть MailboxProcessor. Я оставлю обновление, чтобы использовать несколько рабочих для воображения. 

type Msg<'a, 'b> =
    | Work of 'a
    | Done of 'b

type MapTransformer(f) =
    let results = ResizeArray()
    let m = MailboxProcessor.Start(fun payload ->
        let rec loop() =
            async {
                let! msg = payload.Receive()
                match msg with
                | Work work -> 
                    results.Add(f work)
                    return! loop()                
                | Done (channel : AsyncReplyChannel<_>) -> 
                    channel.Reply(results :> seq<_>)
            }
        loop())
    member this.Enqueue(item) = m.Post(Work item)
    member this.Results = m.PostAndReply(fun c -> Done c)

let uberMap tree =
    let m = MapTransformer(fun x -> x + 1)
    tree |> List.iter (fun x -> m.Enqueue(x))
    m.Results

uberMap [1; 2; 3]
//outputs [2; 3; 4]
3 голосов
/ 16 марта 2011

Array.Parallel использует System.Threading.Parallel.For. Когда вы вызываете эту функцию, она пытается найти оптимальное расписание для данной задачи. Однако, с типичным алгоритмом рекурсивного дерева, это означает много вызовов Parallel.For, и вы, вероятно, получите слишком много потоков. (Если Parallel.For не оптимизирован для этого варианта использования, который я не знаю.)
Поэтому я думаю, что предложение Дэниела является хорошей идеей, если нагрузка на узел не слишком мала. Альтернативная идея состоит в том, чтобы ввести пороговое значение относительно оставшейся глубины дерева, как описано Стивеном Таубом в конце этой записи в блоге .

...