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

Планирование на основе транспозиции (TDS) — это алгоритм балансировки нагрузки для параллельных вычислений . Он был разработан в Vrije Universiteit в Амстердаме , Нидерланды, как алгоритм для решения головоломок . Алгоритм обеспечивает почти линейное ускорение с некоторыми проблемами и очень хорошо масштабируется. Он был опубликован о Джоне Ромейне , Аске Плате , Анри Бале и Джонатане Шеффере .

Решение головоломок на основе транспозиции

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

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

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

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

Традиционная установка

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

TDS-шаг

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

Разница

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

Результаты

Ускорение

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

Масштабируемость

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