Модель потоков для обработки данных в ориентированном графе

Question

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

Как мне многопоточность обработки в этом ориентированном графе, чтобы я мог получить результат из графа самым быстрым и эффективным способом? Память не является проблемой здесь, и также не является временем, которое требуется для инициализации этой задачи.

Я подумал о нескольких разных методах многопоточности работы:

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

• Создать поток для каждого узла и создать буфер данных на каждом ребре графа. Рабочий поток на узле будет постоянно проверять наличие данных в том случае, если один поток занимает больше времени с данными. Проблема этого подхода заключается в собственном «опросе» буфера за наличие достаточного количества данных, чтобы начать его обработку - возможно, небольшая цена за упрощение потока данных для любой конфигурации графа.

Кто-нибудь может придумать лучший способ или какой вы порекомендуете? Я ищу наименьшую задержку в системе и возможность постоянно обрабатывать поток входящих данных.

Спасибо! Brett

Answer 1

Прежде всего, не рекомендуется создавать неограниченное количество потоков (например, поток на узел). Обычно вы хотите иметь максимум в 1,5-3 раза больше потоков, чем у ядер вашего процессора (например, 6-12 потоков для четырехъядерного процессора).

Я бы порекомендовал использовать thread-pool и задачи . В таком случае вашу проблему можно перефразировать как размер ваших задач.

Оба упомянутых вами метода действительны, и у каждого есть свои плюсы и минусы.

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

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

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

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

Более сложная проблема - когда в узле есть два входящих ребра. При обработке задачи узлу придется ждать, пока станут доступны данные для обоих ребер.

Вывод: Я бы лично начал с первого варианта (одно задание на ввод данных) и посмотрел, как далеко вы сможете с ним справиться.