Тема 2_2010 Сложные задачи их хараетристики пути эффективного решения (Лекции (ещё одни)), страница 2

Если β =0, tдоп =0, тогда S=p (т.е. алгоритм полностью параллелен,отсутствует последовательная часть)1- Закон Амдаля1− β(β +)pT ( n)3. Если β – любое, tдоп >>0, тогда S = 1 < 1 ,t доп2. Если β <>0, tдоп =0, тогда S =Имеем большие затраты на обмен данными и синхронизацию, чтоможет привести к неэффективности параллельного алгоритма.Если 9/10 программы исполняется параллельно, а 1/10 по-прежнемупоследовательно, то ускорения более, чем в 10 раз получить в принципеневозможно вне зависимости от качества реализации параллельной частикода и числа используемых процессоров (ясно, что 10 получается только втом случае, когда время исполнения параллельной части равно 0).Посмотрим на проблему с другой стороны: а какую же часть кода надоускорить (а значит и предварительно исследовать), чтобы получить заданноеускорение?Ответ можно найти в следствии из закона Амдала: для того чтобыускорить выполнение программы в q раз необходимо ускорить не менее, чемв (1-1/q)-ю часть программы.

Следовательно, если есть желание ускоритьпрограмму в 100 раз по сравнению с ее последовательным вариантом, тонеобходимо получить ускорение не менее, чем на 99.99% кода, что почтивсегда составляет значительную часть программы!Отсюда первый вывод - прежде, чем основательно переделывать коддля перехода на параллельный компьютер или суперкомпьютер надоосновательно подумать.

Если, оценив заложенный в программе алгоритм,ясно, что доля последовательных операций велика, то на значительноеускорение рассчитывать явно не приходится и нужно думать о заменеотдельных компонент алгоритма.В ряде случаев последовательный характер алгоритма изменить не таксложно. Допустим, что в программе есть следующий фрагмент длявычисления суммы n чисел:s = 0Do i = 1, ns = s + a(i)EndDoПо своей природе он строго последователен, так как на i-й итерациицикла требуется результат с (i-1)-й и все итерации выполняются одна заодной. Имеем 100% последовательных операций, а значит и никакогоэффекта от использования параллельных компьютеров.Вместе с тем, выход очевиден. Поскольку в большинстве реальныхпрограмм нет существенной разницы, в каком порядке складывать числа,выберем иную схему сложения.

Сначала найдем сумму пар соседнихэлементов: a(1)+a(2), a(3)+a(4), a(5)+a(6) и т.д. Заметим, что при такой схемевсе пары можно складывать одновременно! На следующих шагах будемдействовать абсолютно аналогично, получив вариант параллельногоалгоритма.Казалось бы в данном случае все проблемы удалось разрешить. Нопредставьте, что доступные вам процессоры разнородны по своейпроизводительности. Значит будет такой момент, когда кто-то из них ещетрудится, а кто-то уже все сделал и бесполезно простаивает в ожидании.Если разброс в производительности компьютеров большой, то иэффективность всей системы при равномерной загрузке процессоров будеткрайне низкой.Но пойдем дальше и предположим, что все процессоры одинаковы.Проблемы кончились? Опять нет! Процессоры выполнили свою работу, норезультат-то надо передать другому для продолжения процессасуммирования, а на передачу уходит время и в это время процессоры опятьпростаивают.Словом, заставить параллельную вычислительную систему или суперЭВМ работать с максимальной эффективность на конкретной программе это,задача не из простых, поскольку необходимо тщательное согласованиеструктуры программ и алгоритмов с особенностями архитектурыпараллельных вычислительных систем.Замечание: Верно ли утверждение: чем мощнее компьютер, тем быстреена нем можно решить данную задачу?Нет, это не верно.

Можно пояснить простым бытовым примером. Еслиодин землекоп выкопает яму 1м*1м*1м за 1 час, то два таких же землекопаэто сделают за 30 мин - в это можно поверить. А за сколько времени этуработу сделают 60 землекопов? За 1 минуту? Конечно же нет! Начиная снекоторого момента они будут просто мешаться друг другу, не ускоряя, азамедляя процесс. Так же и в компьютерах: если задача слишком мала, томы будем дольше заниматься распределением работы, синхронизациейпроцессов, сборкой результатов и т.п., чем непосредственно полезнойработой..