Диссертация (1150810), страница 2
Текст из файла (страница 2)
Время выполнения вычислений на каждомпроцессоре в рамках одного этапа в общем случае не зависит от времени аналогичных вычислений на других процессорах. Этап заканчивается в моментзавершения необходимых вычислений на каждом процессоре, после чего процессоры обмениваются информацией, и выполняется переход к следующемуэтапу.
Если бы у процессоров имелся доступ к глобальному времени, то длявсех процессоров все этапы начинались и заканчивались одновременно. Приотсутствии в вычислительной системе глобального времени необходимо прибегать к помощи синхронизирующих алгоритмов, работа которых основанана глобальной синхронизации или локальной синхронизации.При использовании глобальной синхронизации каждый процессор переходит к следующему этапу вычислений только после того, как все процессоры закончат вычисления, и все отправленные сообщения будут полученыадресатами. Возможные методы реализации такого подхода можно найти,например, в [16–18].При локальной синхронизации процессор переходит к следующему этапупосле того, как закончит вычисления и получит те сообщения с данными,9которые необходимы ему для перехода к следующему этапу. В этом случаене тратится время на ожидание того, когда все сообщения будут доставленывсем процессорам.Для асинхронных алгоритмов нет такого разделения на этапы, после выполнения вычислений процессоры приступают к новым, не следя за доставкой сообщений, и используют данные от других процессоров, имеющиеся наданный момент, пусть даже они будут и не самыми актуальными.
При такомподходе нет необходимости использовать глобальное время, глобальную илилокальную синхронизации и время простаивания процессоров сводится к минимуму. Важные вопросы, на которые требуется ответить при использованииасинхронных методов – приведет ли такой подход к нахождению решения задачи и, если да, то будет ли выигрыш в общем времени решения задачи посравнению с синхронным аналогом алгоритма.Рассмотрим вычислительную систему с ∈ N процессорами и задачу нахождения неподвижной точки, в которой ищется вектор = (1 , 2 , .
. . , ),удовлетворяющий равенству = (1 , 2 , . . . , ), = 1, . . . , ,где – заданные функции зависящие от переменных. Естественно в даннойситуации распределить вычисления по процессорам таким образом, чтобы-ый процессор обновлял переменную согласно формуле := (1 , 2 , . . . , ), = 1, .
. . , ,предполагая что вычисления начинаются с некоторых исходных значений.При использовании синхронного алгоритма процессор не приступит к -ому обновлению пока не получит результаты ( − 1)-ого обновления отпроцессоров, чьи переменные используются при расчете . У такого подхода есть несколько недостатков. Во-первых, процессор после обновления 10вынужден ожидать прихода результатов вычислений от других процессоров(рисунок 1.1). В частности, медленный канал обмена данными замедляет решения всей задачи (рисунок 1.2 a). Во-вторых, те процессоры, которые выполняют свои вычисления быстрее других по причине меньшей нагрузки врамках одной итерации или же в силу большей вычислительной мощности,вынуждены ждать пока более медленные процессоры завершат вычисления.Поэтому скорость всего алгоритма будет напрямую зависеть от скорости самого медленного процессора (рисунок 1.2 b).
Простой процессоров относитсяк так называемому штрафу за синхронизацию.1-ая итерация2-ая итерация3-я итерация123123Простой процессораВремя напроцессоре 1Время напроцессоре 2Рис. 1.1. Синхронный методИспользование асинхронного алгоритма (рисунок 1.3) позволяет в значительной степени ослабить условия перехода для процессора от -ого к( + 1)-ому обновлению. На рисунке 1.3 представлена ситуация, когда за время обмена данными между процессорами каждый из них может успеть выполнить три итерации. Чтобы перейти к (+1)-ому обновлению -ому процессорудостаточно знать некоторые прошлые результаты обновлений других процес11Время напроцессоре 11212343545Время напроцессоре 2(а)Время напроцессоре 11213243(b)54Время напроцессоре 2Рис. 1.2. Синхронный метод.
Задержки.соров пусть даже не самые актуальные. При таком подходе удаётся свестик минимуму штраф за синхронизацию, правда есть опасность, что использование в вычислениях устаревшей информации приведет к неэффективномуалгоритму. Обсуждение этого вопроса будет приведено в последующих разделах.Рассмотрим ещё один важный пример (см.
[19]), демонстрирующий преимущество асинхронных алгоритмов. Как отмечалось выше, время вычислений в рамках одной итерации может отличаться от процессора к процессору.Представляется разумным предположить, что время вычислений на процес121234567891012345678910Рис. 1.3. Асинхронный методсоре является случайной величиной. Для примера предположим, что времявычислений на любом из процессоров распределено по показательному распределению с параметром > 0. При синхронной реализации алгоритма переход к следующему этапу происходит после завершения вычислений всемипроцессорами, то есть время этапа – это максимум из случайных величин,если в системе процессоров. Среднее время этапа, как нетрудно проверить,имеет выражение /, где = 1 +11+ ··· + .2В данном случае характеризует штраф за синхронизацию.
Среднее времяпростоя процессора равно ( − 1)/ и будет неограниченно расти при стремлении к бесконечности. Такой итог побуждает к исследованию асинхронныхалгоритмов на неоднородных системах, то есть тех системах, на которых вычислительное время или время передачи может существенно отличаться дляразных процессоров.Когда речь заходит о решении задач большой размерности, нередко возникающих при дискретизации задач математической физики, то наряду сдетерминированными методами решения рассматривают и стохастические, а13именно метод Монте-Карло.
Чаще всего в таких ситуациях при его использовании строится стохастическая оценка, математическое ожидание которойесть искомое решение. Далее производится моделирование большого числаслучайных величин, распределенных так же, как построенная оценка. Послеполучения достаточного количества реализаций случайной величины беретсясреднее смоделированных величин, что в результате и является приближением искомой величины. Привлекательность такого метода состоит в том, чтомоделирование делается независимо и может быть поручена разным процессорам, представляя тем самым эффективный алгоритм загрузки многопроцессорной системы произвольной архитектуры.Далее будет рассматриваться задача нахождения неподвижной точки(1.1) = (),где=(1 , 2 , .
. . , )–вектор-столбецнеизвестных, = (1 (), 2 (), . . . , ()) – оператор из R в R . Так как в дальнейшем будет рассматриваться последовательность векторов наряду с элементами этихвекторов, введем следующие обозначения: компоненты вектора из R будемобозначать , = 1, . . . , , а последовательность векторов из R будем обозначать (), = 0, 1, . .
.. Метод простых итераций, который лежит в основерассматриваемых методов, запишется в предложенных обозначениях в виде( + 1) = (()), = 0, 1, . . . ,(1.2)для некоторого начального (0).Условия, при которых процесс (1.2) сходится к неподвижной точке оператора , можно найти, например, в [20]. Среди всевозможных условий особовыделим следующий класс операторов и связанную с этим классом теорему.Определение 1.Отображение : ⊂ R → R называется сжимающим14на 0 ⊂ , если существует такое < 1, что ‖ () − ()‖ < ‖ − ‖при всех , ∈ 0 .Теорема 1.Пусть отображение : ⊂ R → R сжимающее на замкнутом множестве 0 ⊂ и (0 ) ⊂ 0 . Тогда имеет единственнуюнеподвижную точку * ∈ 0 и для любого начального (0) ∈ 0 последовательность {()}, определяемая (1.2), сходится к * .1.1.
Асинхронные итерацииВпервые асинхронные варианты методов итераций для решения системы(1.1), в которой оператор являлся линейным оператором вида + , былипредложены в [1] и носили название "схема хаотических релаксаций"(chaoticrelaxation scheme). Там же было показано, что предложенная схема сходитсяк решению задачи (1.1) тогда и только тогда, когда 1 (||) < 1, где || –матрица, составленная из модулей элементов матрицы , а 1 (||) – первоесобственное число матрицы ||.Затем в [21] и [22] Миллоу обобщил схему хаотических релаксация на случай нелинейного оператора и доказал сходимость обобщенного метода длясжимающих операторов.
В [2] Боде ввел определение асинхронных итераций,которые обобщали понятие хаотических релаксаций, для решения систем (втом числе и нелинейных) уравнений и получил достаточные условия сходимости метода к решению системы (1.1).Ещё более общее определение асинхронных итераций было приведено в[16], поэтому в дальнейшем будем следовать постановке из этого источника.Пусть 1 , 2 , .
. . – заданные множества, а – их декартово произведение = 1 × 2 × · · · × .15Элемент ∈ соответственно имеет структуру = (1 , 2 , . . . , ),где принадлежат , = 1, . . . , . Пусть заданы функции : → , афункция : → представляется в виде () = (1 (), 2 (), . . . , ()), ∀ ∈ .Задача состоит в нахождении неподвижной точки оператора , то есть такой* ∈ , что * = (* ) или в покомпонентной записи* = (* ), = 1, .
. . , .Далее определим асинхронную версию метода простых итераций, которуювпоследствии будем называть асинхронными итерациями.Предположим, что множество = {0, 1, 2, . . . } – это множество моментов времени, в которые одна или несколько компонент вектора обновляется некоторым процессором распределенной вычислительной системы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
