Плохо ли создавать большое количество задач только для нескольких доступных ядер?

Question

Я новичок в параллельном программировании с TPL и только что закончил слушать курс TPL. Я только что написал небольшую демонстрационную программу, чтобы проверить мое понимание.

Позвольте мне объяснить контекст моего распараллеленного кода, прежде чем задавать общие вопросы: (если вам скучно, перейдите непосредственно к вопросам;-)

Контекст:

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

В игровом дереве узлы представляют игровые позиции. Корневой узел, являющийся текущей игровой позицией, и его n дочерних узлов (на 2-м уровне дерева) - игровые позиции, которые могут быть достигнуты путем применения n допустимых ходов для игрока A в корневой позиции. Узлы 3-го уровня представляют достижимые позиции, применяя законные ходы игрока B на каждой позиции / узлах 2-го уровня и так далее, пока не будет достигнута максимальная глубина поиска.

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

Наилучшее значение всех дочерних узлов сообщается их общему родительскому узлу (Конечно, если родительский узел представляет позицию, сыгранную игроком A, лучшим дочерним узлом является дочерний узел с наибольшим значением, и если он воспроизводится игрок B, лучший дочерний узел - тот, который имеет наименьшее значение).

Наконец, наилучшие дочерние значения сообщаются корневому узлу с индексом дочернего узла 2-го уровня, который сообщил о своем наилучшем значении корневому узлу. Конечно, этот индекс представляет "лучший" ход для игрока А. Это означает ход, который гарантирует игроку А, что сообщаемое значение (или лучшее) может быть достигнуто на исследуемой глубине ("конечная позиция") независимо от ходы, сыгранные игроком B.

Хорошо, это хорошо известный минимаксный алгоритм для игр с участием двух игроков.

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

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

Работа выполнена успешно, параллельный поиск выполняется быстрее, чем последовательный, и распределяет работу по всем доступным ядрам, работающим почти всегда на 100% (согласно диспетчеру задач). Я не хочу утомлять вас своим исходным кодом. Я просто хочу уточнить, что я также применил шаблон асинхронного ожидания.Net 4.5 к моему рекурсивному распараллеленному методу и реализовал шаблон "ожидания все по одному" (на самом деле ожидаем Task.WhenAll()) для создания подзадач, исследующих поддеревья, генерируемые каждым дочерним узлом. (Примечание. Чтобы разрешить отмену обхода поддерева, мне пришлось передать список токенов отмены в метод рекурсивного исследования асинхронного поддерева, каждый уровень повторного исследования добавляет новый список CancellationToken в список).

Теперь, когда вы понимаете контекст, вот мои вопросы:

1. Запуск поиска быстро создаст миллионы задач, оценивающих миллионы поддеревьев, генерируемых каждым узлом дерева, но на самом деле доступно только несколько процессорных ядер для выполнения этих задач с несколькими потоками (по одному на ядро?). Так что это хорошая идея, чтобы не принимать это во внимание и создавать задачи для каждого дочернего узла / поддерева, которые должны быть оценены / пройдены? Нет ли накладных расходов, вызванных созданием большего количества задач, чем необходимо, чтобы раскрыть максимум параллелизма? Не лучше ли ограничить количество запускаемых задач (например, запуская задачи только для узлов самого высокого уровня и используя чисто последовательный метод обхода для узлов самого низкого уровня?) Или мы можем не заботиться об этом, создав миллион задачи, даже если мы знаем, что некоторые из них (запущенные на самых глубоких узлах дерева) выполняют очень небольшую работу?

2. Я не предотвращал проблему "передачи переменной индекса цикла в запущенную задачу путем закрытия", используя аргумент лямбда-выражения (как предложено в курсе), но копировал переменную индекса цикла в локальную переменную копирования перед запуском задачи и обращался к ней. копировать по замыканию, вместо переменной цикла индекса из лямбда-выражения. Что вы думаете об этом обходном пути? Это так же безопасно, как передача аргумента лямбда-выражения?

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

Answer 1

Вопрос о том, "сколько задач" действительно обусловлен двумя причинами:

• организация концептуальной программы
• накладные расходы

Назначение одной задачи на узел в дереве концептуально чисто и легко. Это преимущество.

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

Причина, по которой вы выбрали задачи на уровне узлов, заключается в том, что легко увидеть (возможно) множество узлов. [В своем комментарии вы отметили, что для глубокого поиска было меньше единиц работы, чем вы ожидали!]. Другая причина в том, что вы не знаете точно, сколько работы занимает узел, поэтому наличие большого количества задач означает, что процессор может выполнить одно, поработать над ним до конца, а затем перейти к другому. Если все они имеют некоторое среднее время, процессоры будут выполняться и находить другую работу, не тратя много времени на ожидание появления другой работы.

Ключевая проблема - накладные расходы. Чтобы "иметь" задачу, есть куча накладных расходов: что-то должно ее создать, заполнить работой, поместить в рабочую очередь, где ее может получить другой процессор; этот другой процессор должен вытащить его из очереди, взять его содержимое, [не накладные расходы: выполнить его] и, наконец, удалить его. Каждый из этих битов издержек требует некоторых компьютерных инструкций, некоторого доступа к памяти (если вам повезло, что они обращаются к кешу) и, как правило, дорогостоящей синхронизации между процессорами (вы не можете иметь все процессоры, которые помещают новые задачи в доступную рабочую очередь на тот же момент).

Я не знаю, что такое служебная нагрузка для C# TPL. Вероятно, вы можете измерить его, написав простой цикл, который имитирует тело задачи и измеряет его; а затем измерить, сколько времени занимает этот цикл при сбросе в задачу. Я знаю, что вы хотите минимизировать накладные расходы (я разработал язык параллельного программирования PARLANSE для этой идеи) и максимизировать работу, которую вы вкладываете в задачу.

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

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

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

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

Альфа-бета может спасти вас ("только 1000 задач") от нехватки виртуальной машины из-за "больших стеков" и множества задач. Хорошие новости о создании большого количества работы - у вас есть много, чтобы дать процессорам. Плохая новость заключается в том, что они могут занимать много места в виртуальной машине, пока они сидят без дела; Модель MS с большим стеком усугубляет это. Даже если она не запускает вас из виртуальной машины, это может привести к тому, что ваша программа коснется огромных объемов памяти, что сведет на нет значение кеша процессора. Я бы беспокоился об этом, но у меня нет хороших советов по C#; Я построил PARLANSE, чтобы избежать этих проблем; оно автоматически ограничивает генерацию задач, когда у нее "достаточно" работы. У MS есть несколько умных куки, хотя.