Многопоточный менеджер очередей заданий - PullRequest
32 голосов
/ 19 февраля 2009

Мне нужно управлять многозадачными заданиями с высокой нагрузкой на процессор в интерактивном приложении. Как фон, мое конкретное приложение - это интерфейс инженерного проектирования. Когда пользователь настраивает различные параметры и параметры модели, в фоновом режиме запускается несколько симуляций, и результаты отображаются по мере их завершения, вероятно, даже когда пользователь все еще редактирует значения. Поскольку многократное моделирование занимает переменное время (некоторые - миллисекунды, некоторые - 5 секунд, некоторые - 10 минут), в основном это вопрос отображения обратной связи как можно быстрее, но часто прерывая задания, которые были запущены ранее, но теперь больше не нужны, потому что из изменений пользователя уже сделали их недействительными. Различные изменения пользователя могут сделать недействительными разные вычисления, поэтому в любое время я могу запустить 10 разных симуляций. У некоторых симуляций есть несколько частей, которые имеют зависимости (симуляции A и B могут быть вычислены отдельно, но мне нужны их результаты для заполнения симуляции C, поэтому мне нужно дождаться, пока A и B закончат сначала, прежде чем запускать C).

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

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

Первая мысль - запустить OpenMP , но я не уверен, что это то, что я хочу. OpenMP отлично подходит для распараллеливания на хорошем уровне, автоматического развертывания циклов и тому подобного. Будучи мультиплатформенным, он также вторгается в ваш код с помощью #pragmas. Но в основном он не предназначен для управления большими задачами .. особенно для отмены ожидающих заданий или определения зависимостей. Возможно, да, но это не элегантно.

Я заметил, что Google Chrome использует такой менеджер заданий даже для самых тривиальных задач. Кажется, цель разработки - сделать поток взаимодействия с пользователем как можно более легким и проворным, чтобы все, что можно было получить, порождается асинхронно, должно быть. Судя по исходным текстам Chrome, эта библиотека, похоже, не является общей, но все же интересно посмотреть, как дизайн использует асинхронные запуски для обеспечения быстрого взаимодействия. Это похоже на то, что я делаю.

Есть еще другие варианты:

Surge.Act: Boost-подобная библиотека для определения заданий. Он основан на OpenMP, но позволяет создавать цепочки зависимостей, что приятно. Кажется, не похоже, что у него есть менеджер, которого можно опрашивать, отменить работу и т. Д. Это устаревший проект, поэтому от него страшно зависеть.

Job Queue довольно близко к тому, о чем я думаю, но это 5-летняя статья, а не поддерживаемая библиотека.

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

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

Мое сообщение здесь, чтобы спросить вас обо всех существующих инструментах, которые я пропустил, и / или как вы создали собственную такую ​​многопоточную очередь заданий.

Ответы [ 10 ]

17 голосов
/ 20 февраля 2009

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

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

  • Мы запускаем один поток на ядро ​​в начале программы. Каждый тянет работу из глобальной очереди заданий. Задания состоят из функционального объекта и глобуса связанных данных (на самом деле разработка func_ptr и void *). Поток 0, быстрый цикл клиента, не может работать на заданиях, но остальные берутся как могут.
  • Сама очередь заданий должна представлять собой структуру данных без блокировки, такую ​​как список без привязок, односвязный (Visual Studio поставляется с одним ). Избегайте использования мьютекса; конкуренция за очередь удивительно высока, а захват мьютексов обходится дорого.
  • Упакуйте все необходимые данные для задания в сам объект задания - избегайте попадания указателя из задания обратно в основную кучу, где вам придется иметь дело с конфликтами между заданиями и блокировками и всем этим другие медленные, раздражающие вещи. Например, все параметры моделирования должны быть помещены в локальный блок данных задания. Очевидно, что структура результатов должна быть чем-то, что переживает задание: вы можете справиться с этим либо: а) зависая на объектах задания даже после того, как они закончат работу (так что вы можете использовать их содержимое из основного потока), либо б) выделение структуры результатов специально для каждого задания и вставка указателя в объект данных задания. Даже если сами результаты не будут работать, это фактически дает работе эксклюзивный доступ к ее выходной памяти, поэтому вам не нужно будет путаться с блокировками.

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

5 голосов
/ 19 февраля 2009

Я свернул свой, основываясь на Boost.threads. Я был очень удивлен тем, как много я получил от написания такого маленького кода. Если вы не нашли что-то готовое, не бойтесь свернуть свое. Между Boost.threads и вашим опытом с момента написания собственного, это может быть проще, чем вы помните.

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

4 голосов
/ 20 февраля 2009

Microsoft работает над набором технологий для следующей версии Visual Studio 2010, называемой средой параллелизма, библиотекой параллельных шаблонов и библиотекой асинхронных агентов, которая, вероятно, поможет. Среда выполнения с параллелизмом предложит планирование на основе политик, т.е. позволит вам управлять и создавать несколько экземпляров планировщика (аналогично пулам потоков, но с аффинитизацией и балансировкой нагрузки между экземплярами), библиотека параллельных шаблонов будет предлагать программирование на основе задач и параллельные циклы с STL, как модель программирования. Библиотека агентов предлагает модель программирования на основе акторов и поддерживает построение параллельных конвейеров потока данных, то есть управление этими зависимостями, описанными выше. К сожалению, это еще не выпущено, так что вы можете прочитать об этом в нашем блоге команды или посмотреть некоторые видео на канале 9 , также есть очень большой CTP, который доступен для скачивания. а также.

Если вы ищете решение сегодня, то Intel Building Building Blocks и библиотека потоков Boost являются хорошими библиотеками и доступны уже сейчас. JustSoftwareSolutions выпустил реализацию std :: thread, которая соответствует черновому варианту C ++ 0x, и, конечно, OpenMP широко доступен, если вы смотрите на мелкозернистый параллелизм на основе циклов.

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

-Rick

3 голосов
/ 19 февраля 2009

Было бы что-то вроде threadpool быть полезным для вас? Он основан на boost :: threads и в основном реализует простую очередь задач потока, которая передает рабочие функции в объединенные потоки.

2 голосов
/ 20 февраля 2009

Возможно, вы захотите взглянуть на Поточное программирование - оно основано на потоковой передаче фрагментов данных между асинхронными компонентами. Существуют версии драйвера для Java и C #, а также ряд предварительно закодированных компонентов. Он по сути многопоточный - на самом деле единственный однопоточный код находится внутри компонентов, хотя вы можете добавить временные ограничения в стандартные правила планирования. Хотя это может быть на слишком мелком уровне для того, что вам нужно, здесь могут быть вещи, которые вы можете использовать.

1 голос
/ 20 февраля 2009

Существует множество распределенных менеджеров ресурсов. Программное обеспечение, которое удовлетворяет почти всем вашим требованиям - Sun Grid Engine . SGE используется на некоторых из крупнейших в мире суперкомпьютеров и находится в активной разработке.

Есть также похожие решения в крутящий момент , платформа LSF и Condor .

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

1 голос
/ 20 февраля 2009

Вы можете посмотреть на Intel Thread Building Blocks . Я полагаю, что он делает то, что вы хотите, а с версией 2 это Open Source.

1 голос
/ 19 февраля 2009

Взгляните на boost :: future (но см. Также обсуждение и предложение ), которое выглядит как действительно хорошая основа для параллелизма (в частности, кажется, что он предлагает отличную поддержку для ситуаций типа C-зависит от A-и-B).

Я немного посмотрел на OpenMP, но (как и вы) не был уверен, что он будет работать хорошо для всего, кроме числового кода на Fortran / C. Intel Threading Building Blocks выглядела мне более интересной.

Если дело доходит до этого, не так уж трудно бросить свой собственный поверх boost :: thread. [Объяснение: поток ферма (большинство людей назвали бы это пулом) извлекает работу из поточно-ориентированной очереди функторов (задач или заданий). См. тесты и тест для примеров использования. У меня есть некоторые дополнительные сложности для (необязательно) поддержки задач с приоритетами, и случай, когда выполнение задач может порождать больше задач в рабочую очередь (это делает знание, когда вся работа фактически завершена, немного более проблематично; ссылки на «ожидающие решения») те, которые могут иметь дело с делом). В любом случае, это может дать вам некоторые идеи.]

0 голосов
/ 08 августа 2009

Возможно, немного поздно, но взгляните также на ThreadWeaver: http://en.wikipedia.org/wiki/ThreadWeaver

0 голосов
/ 20 февраля 2009

Я не знаю, ищете ли вы библиотеку C ++ (что, я думаю, у вас есть), но фреймворк Doug Lea Fork / Join для Java 7 довольно изящен и делает именно то, что вы хотите. Вы, вероятно, сможете реализовать его на C ++ или найти предварительно реализованную библиотеку.

Больше информации здесь: http://artisans -serverintellect-com.si-eioswww6.com / default.asp? W1

...