Планирование на основе транспозиций

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

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

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

Для преодоления этого недостатка предложен подход, сочетающий собственно решение задачи и балансировку нагрузки. Сначала определяется функция, уникально отображающая каждую позицию на доске в некоторое значение. Каждому компьютеру в распределённой системе назначается диапазон позиций, за которые он отвечает. У каждого компьютера своя таблица транспозиций и собственная очередь заданий. Как только компьютер завершает очередное задание, он извлекает следующее из очереди, вычисляет все новые возможные позиции, которые можно получить за один ход из текущей. Всё это соответствует традиционному решению на основе транспозиций. Однако далее, в традиционной схеме, компьютер для каждой найденной позиции запрашивает у другого компьютера, ответственного за неё, есть ли уже решение. Если нет — вычисляет решение рекурсивно и передаёт результат тому, кто за него отвечает. Именно тут возникает избыточная коммуникация.

Планирование на основе транспозиций (TDS) вместо традиционного запроса решения работает иначе: оно просто добавляет задачу в очередь дел того компьютера, который отвечает за позицию. Иначе говоря, каждый раз, когда у компьютера появляется позиция для решения, он пересылает её по сети тому, кто отвечает за область этой позиции, и далее не занимается ею. Только если позиция попадает в зону ответственности самого компьютера, он ищет решение в своей таблице транспозиций. Если решения нет — помещает задачу в свою очередь. Если решение уже найдено — сразу переключается на следующее задание.

Принципиальное отличие между классическим подходом и TDS заключается в схеме взаимодействия: в первом случае запрос решения требует ответа (request-response), то есть отправивший ждёт ответа от другого компьютера. В TDS передача задачи не требует обратной связи: известно, что другой компьютер примет задание и попытается его решить. Благодаря этому задержки (главная причина замедлений в модели запрос-ответ) здесь не имеют значения — компьютер никогда не ждёт ответа. Доставку сообщения обеспечивает оборудование или операционная система, так что после отправки задачи программа может не беспокоиться — задача придёт адресату.

TDS обеспечивает впечатляющие результаты по сравнению с классическими алгоритмами, в ряде случаев достигая даже сверхлинейного ускорения (хотя лишь в определённом смысле). Такой эффект связан с тем, что объём памяти у каждого компьютера ограничен, и при больших задачах сохранить все транспозиции невозможно, некоторые состояния придётся пересчитывать заново. Однако если использовать, например, 16 компьютеров, то их суммарная память увеличивается в 16 раз (если они идентичны), а значит, можно хранить больше транспозиций и дублирующих вычислений становится меньше. Если же одному компьютеру дать столько же памяти, сколько есть у всей группы из 16 по отдельности, ускорение будет чуть менее, чем идеально линейным.

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