Как узнать, какие задания в дереве зависимостей можно запускать параллельно?

Question

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

#!/usr/bin/perl

use strict;
use warnings;

use Graph;

#FIXME: naive implementation, there may be a much better way to do this
sub run_in_parallel {
       my $g = shift->copy;

       while (my @v = $g->vertices) {
               my @run = grep { $g->is_successorless_vertex($_) } @v;
               print "running ", join(", ", @run), " in parallel\n";
               for my $compenent (@run) {
                       $g->delete_vertex($compenent);
               };
       }
}

my $g = Graph->new;
while (<DATA>) {
       my ($component, @dependencies) = split;
       unless ($g->has_vertex($component)) {
               $g->add_vertex($component);
       }
       for my $dependency (@dependencies) {
               unless ($g->has_vertex($dependency)) {
                       $g->add_vertex($dependency);
               }
               $g->add_edge($component, $dependency);
       }
}

run_in_parallel($g);

#component  dependency list
__DATA__
a           b c d
b           e
c           f g
d
e
f
g

Answer 1

Другая идея состоит в том, чтобы использовать сеть Петри . Узлы на вашем графике - это мест , действия - его переходов . Каждое место должно иметь ровно один разрешающий переход, даже если у него нет зависимостей. Таким образом, вам даже не нужно помещать никакие начальные токены.

Это также включает предложение Карла Билефельда.

Answer 2

Вы можете параллельно запускать любые задачи без незавершенных зависимостей. Например, в показанном наборе данных вы можете запустить d, e, f и g параллельно в начале. Когда f и g завершены, вы можете запускать c параллельно, даже если d и e все еще работают, и т. Д. Вашему алгоритму просто нужно каждый раз, когда задача завершается, отмечать его как выполненное и переоценивать, если какие-либо задачи теперь доступны для запуска.

Answer 3

Просто так случилось, что я недавно думал об этом, отвечая на чужой вопрос.

Ваш алгоритм в целом выглядит правильно, хотя я не уверен, есть ли более эффективный способ сделать это. Одна вещь: вы не должны предварительно вычислять то, что вы делаете в своем примере кода. который идет в ногу; так что если A B C можно запустить в начале, он запустит все три и дождется завершения всех трех, прежде чем заглядывать дальше в список. Но что, если D зависит только от A, а A является первым заданием, завершенным до B и C? Вы потратили бы впустую емкость, чтобы не запускать D сразу, поэтому вы действительно хотите сохранять график при запуске заданий и повторно опрашивать выполняемые задания каждый раз, когда задание завершается, если у вас уже нет полной очереди. *

На самом деле я начал писать ответ, используя Algorithm :: Dependency :: Ordered , что во многом соответствует духу ответа Эфира. Работать с памятью проще и легче, чем Graph, но я только что понял, что отчасти страдает от той же проблемы недостаточного использования. Я думаю, что это может быть поправимо, но в этом случае я буду обновлять здесь, когда смогу. :)

Answer 4

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

Вы поддерживаете зависимости вне порядка, но пока не поддерживает циклы.

Это очень четко описывает то, что вам нужно сделать, в некотором родеэто позволяет очень легко проверить, что все сделано правильно.

Я мог бы также создать обратный граф и использовать его для обхода, например, с Graph :: Traversal :: BFS.

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

Answer 5

Мне кажется, что вы можете избавиться от большей части поиска вершин, отслеживая конечные узлы, когда добавляете их в граф и обрабатываете список узлов.

if( @dependencies ) {
    for my $dependency (@dependencies) {
           unless ($g->has_vertex($dependency)) {
                   $g->add_vertex($dependency);
           }
           $g->add_edge($component, $dependency);
   }
}
else {
    push @end_components, $component;
}

Затем, когда вы обрабатываете свой набор данных, запускаете один поток выполнения (однако вы реализуете свой параллелизм) для каждого конечного узла. Когда поток завершается, любые родительские узлы без других преемников добавляются в список конечных узлов. Продолжайте обрабатывать список конечных узлов, пока график и список узлов не станут пустыми.

sub run_in_parallel {
   my $g = shift->copy;
   my $end_vertices = shift;

   my @queue;

   while( $g->vertices ) {

      print "running ", join(", ", @queue), " in parallel\n";

      for my $compenent (@queue) {
          # When process finished.

          $g->delete_vertex($component);
          push @queue, grep { $g->is_successorless_vertex($_) } $g->predecessors($v);
      }

      # Add some error check for non-empty graph + empty queue + no processes waiting to finish.
   }
}

Это изменение добавляет немного ведения записей и немного более хрупко, чем ваше первоначальное представление. Попробуйте инкапсулировать эти поведения в объекте, который содержит или наследует от Graph.

Наибольшим выигрышем в производительности будут большие графы с глубокими зависимостями. Минимальное улучшение будет наблюдаться с небольшими графиками (где затраты на поиск незначительны по сравнению со стоимостью управления процессами), или где графики очень мелкие.

Этот код полностью не проверен.

Answer 6

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

На самом деле вам не нужно много рассчитывать, какие задания можно запускать параллельно, так как этот список будет постоянно меняться по мере выполнения заданий.Вместо этого просто запускайте все, что можете, сразу же, и когда у вас есть доступные ресурсы, динамически ищите следующего лучшего кандидата.

# pseudocode:
use List::MoreUtils 'any';
while (my $job = get_next_job_that_I_would_ideally_run_now())
{
     # any { not } is subtly different than not all {} -- see how empty lists are handled!
     next if any { not $_->finished() } $job->get_dependent_jobs();

     # job has no dependencies or they are all complete: safe to run.
     # This probably involves forking or spawning a subthread to perform this
     # execution, and when it is done, the finished() state will be set so its
     # upstream dependencies can then run.
     $job->execute;

     # if no more resources are available for starting more jobs, wait here until
     # something is freed up; then we can continue on with our loop and look for the
     # next best job to start.
}