Первый вопрос, на который следует дать ответ, - какие вычисления программы на компьютере следует называть параллельными. Но это не единственный вопрос, на который хотелось бы получить ответ. Не менее важно понять, зачем вообще переходить из простого, хорошо знакомого, понятного мира последовательных вычислений к сложному для понимания миру параллельных вычислений. Какие преимущества есть у параллельных вычислений, и какие проблемы ждут программиста при создании программ, ориентированных на параллельные вычисления. Чтобы ответить на эти вопросы, давайте совершим небольшой экскурс в историю развития компьютеров.
Первые компьютеры были построены в соответствии с принципами, сформулированными Фон-Нейманом. Они имели три главных компонента - память, процессор и некоторый набор внешних устройств, обеспечивающих ввод и вывод информации.
Память была многоуровневой и для первых компьютеров содержала внешнюю память и внутреннюю память - оперативную и регистровую. Внешняя память (на магнитных лентах, перфокартах, дисках) позволяла сохранять программы и данные вне зависимости от того, включен компьютер или нет. Внутренняя память хранила информацию только на период сеанса работы с компьютером. При отключении компьютера содержимое внутренней памяти исчезало.
Для того чтобы программа могла быть выполнена на компьютере, она должна была быть загружена в оперативную память. Хранилась она там точно также как и данные, обрабатываемые этой программой. Принцип хранимой в памяти программы - один из главных принципов Фон-Неймановских компьютеров.
Регистровая память использовалась в момент выполнения вычислений. Прежде, чем выполнить некоторую операцию над данными, данные должны быть размещены на регистрах. Этот самый быстрый вид памяти обеспечивал необходимое быстродействие при выполнении операций над данными.
Выполнение всех операций - операций над данными и операций по управлению процессом вычислений - осуществлял процессор. Процессор компьютера обладал определенным набором команд. Этот набор был достаточно универсальным, чтобы вычислить любую потенциально вычислимую функцию. С другой стороны этот набор обеспечивал относительную простоту написания программ человеком.
Программы для первых компьютеров представляли последовательность команд, входящих в допустимый набор команд процессора. Выполнение программы на компьютере осуществлялось достаточно просто. В каждый момент времени на компьютере выполнялась одна программа. Процессор, в соответствии с программой, последовательно выполнял одну команду за другой. Все ресурсы компьютера - память, время процессора, все устройства - были в полном распоряжении программы, и ничто не могло вмешаться в ее работу (не считая конечно человека). Параллелизма не было и в помине.
Такая идиллия продолжалась недолго по причине неэффективного использования ресурсов крайне дорогих в те времена компьютеров. Компьютеры тогда не выключались, - одна программа сменяла другую.
Достаточно скоро у компьютера наряду с процессором, который стал называться центральным процессором, появились дополнительные процессоры, в первую очередь специализированные процессоры устройств ввода-вывода информации, отвечающие за выполнение наиболее медленных команд. Это дало возможность организации пакетного режима выполнения программ, когда на компьютере одновременно выполнялись несколько программ - одна программа могла печатать результаты работы, другая - выполняться, третья - вводить необходимые ей данные, например с магнитной ленты или другого внешнего носителя.
Революционным шагом было появление в 1964 году операционной системы фирмы IBM - OS 360. Появившаяся у компьютера операционная система стала его полновластным хозяином - распорядителем всех его ресурсов. Теперь программа пользователя могла быть выполнена только под управлением операционной системы. Операционная система позволяла решить две важные задачи - с одной стороны обеспечить необходимый сервис всем программам, одновременно выполняемым на компьютере, с другой - эффективно использовать и распределять существующие ресурсы между программами, претендующими на эти ресурсы. Появление операционных систем привело к переходу от однопрограммного режима работы к мультипрограммному, когда на одном компьютере одновременно выполняются несколько программ. Мультипрограммирование это еще не параллельное программирование, но это шаг в направлении параллельных вычислений.
Заметим, что наличие у компьютера нескольких процессоров является необходимым условием для мультипрограммирования. Существование операционной системы, организующей взаимную работу процессоров, достаточно для реализации мультипрограммирования. Для параллельных вычислений накладывается дополнительное требование - это требование к самой программе, - программа должна допускать возможность распараллеливания вычислений.
Появление операционной системы означало, что компьютер нельзя рассматривать только как "железо" (память, процессоры, другие устройства). Теперь у него две составляющие - хард (hard) и софт (soft) - аппаратная и программная составляющие, взаимно дополняющие друг друга. За полвека существования компьютеров оба компонента стремительно развивались.
Для аппаратуры характерен экспоненциальный рост, что нашло отражение в известном эмпирическом законе Мура, - экспоненциально росли все важнейшие характеристики - объем памяти на всех уровнях, уменьшение времени доступа к памяти, быстродействие процессоров. Согласно закону Мура (Гордон Мур - один из основателей фирмы Intel) каждые полтора года значения характеристик увеличивались вдвое. Росло и число процессоров, включаемых в состав компьютера. Изменялась и архитектура компьютера. Эти изменения во многом были шагами в сторону распараллеливания вычислений. Вот лишь некоторые изменения в архитектуре процессоров, связанные непосредственно с процессом распараллеливания:
В научных исследованиях и в новых технологиях всегда есть задачи, которым требуется вся мощь существующих вычислительных комплексов. Научный потенциал страны во многом определяется существованием у нее суперкомпьютеров. Понятие суперкомпьютера это относительное понятие. Характеристики суперкомпьютера десятилетней давности сегодня соответствуют характеристикам рядового компьютера. Сегодняшние суперкомпьютеры имеют производительность, измеряемую в петафлопсах (1015 операций с плавающей точкой в секунду). К 2020 году ожидается, что производительность суперкомпьютеров повысится в 1000 раз и будет измеряться в экзафлопсах.
Мир компьютеров многообразен, начиная от миниатюрных встроенных компьютеров до многотонных суперкомпьютеров, занимающих отдельные здания. Классифицировать их можно по-разному. Рассмотрим одну из первых и простейших классификаций - классификацию Флинна, основанную на том, как устроена в компьютере обработка данных. Согласно этой классификации все компьютеры (вычислительные комплексы) можно разделить на четыре класса - компьютеры с архитектурой:
Мы не будем рассматривать подробную классификацию компьютеров класса MIMD. Остановимся только на другом способе разделения компьютеров на три класса:
Мы говорили об архитектуре вычислительных комплексов, способных обеспечить параллельное выполнение программ. Но архитектура комплекса - это лишь одно из требований, необходимых для реализации подлинного параллелизма. Другие два требования связаны с требованиями к операционной системе и к самой программе. Не всякую программу можно распараллелить независимо о того, на каком суперкомпьютерном комплексе она будет выполняться. В следующих главах мы подробнее поговорим о средствах операционной системы, обеспечивающих параллелизм вычислений, и о параллельных алгоритмах. Сейчас же рассмотрим некоторую модель параллельного выполнения, где главным действующим лицом будет программа.
Параллельные вычисления становятся одним из магистральных направлений развития информационных технологий. Можно указать на две причины, определяющие важность этого направления. Первая состоит в том, что стратегически важные для развития государства задачи могут быть решены только с применением суперкомпьютеров, обладающих сотнями тысяч процессоров, которые нужно заставить работать одновременно. Вторая причина связана с другим полюсом компьютерной техники, на котором находятся обычные компьютеры, ориентированные на массового пользователя. И эта техника становится многоядерной, и ее требуется эффективно использовать, так что параллельные вычисления требуются и здесь.
Для поддержки параллельных вычислений сделано достаточно много, начиная от архитектуры вычислительных систем, операционных систем, языков программирования до разработки специальных параллельных алгоритмов. Тем не менее, для программиста, решающего сложную задачу, построение и отладка эффективной параллельной программы все еще остается не простым занятием.
Рассмотрим одну из моделей параллельного вычисления. Для этой модели мы хотим получить оценки времени выполнения программы одним процессором - $$T_1$$, конечным числом процессоров - $$Т_p$$, и для идеализированного случая, когда число процессоров не ограничивается - $$T \mathcal {1}$$.
Рассмотрим программу P, состоящую из n модулей:
Будем предполагать, что программа P выполняется на компьютере, обладающим некоторым числом процессоров, работающих на общей памяти. Выходные данные, полученные в результате работы модуля $$M_i$$, могут являться входными данными для модуля $$M_j$$. Так естественным образом возникает зависимость между модулями, определяющая возможный порядок их выполнения.
Множество модулей разобьём на k уровней. К уровню i отнесем те модули, для начала работы которых требуется завершение работы модулей верхних уровней, из которых хотя бы один принадлежит уровню i - 1. Модуль уровня i с номером k будем обозначать как $$M_k^i$$.
Модули, принадлежащие уровню 1, имеют все необходимые данные, полученные от внешних источников. Они не требуют завершения работы других модулей и в принципе могут выполняться параллельно, будучи запущенными в начальный момент выполнения программы.
Свяжем с программой P ориентированный граф зависимостей модулей. Граф не содержит циклов и отражает разбиение модулей на уровни. Модули являются вершинами графа, а дуги отражают зависимости между модулями. Дуга ведет от модуля $$M_k^i$$ к модулю $$M_1^j$$, если для начала выполнения модуля $$M_k^i$$ требуется завершение работы модуля $$M_1^j$$. В узлах графа содержится информация об ожидаемом времени выполнения модуля, где время измеряется в некоторых условных единицах. На Рис. 1.1 показан пример графа зависимостей:
(рис 1.1) Пример графа зависимостей
Обозначим через $$T_1$$ - время, требуемое для выполнения программы P одним процессором, $$T_p$$ - p процессорами, $$T_{\mathcal {1}}$$ - время, требуемое в случае, когда число процессоров неограниченно. В последнем случае достаточно n процессоров, по числу модулей нашей программы.
Предполагается, что все эти характеристики рассчитываются при соблюдении двух условий:
В случае одного процессора достаточно выполнение только первого условия. Обычно предполагается естественный порядок выполнения модулей, - последовательное выполнение модулей одного уровня, затем переход к выполнению модулей следующего уровня.
Для случая неограниченного числа процессоров оптимальным является такое расписание, когда каждый модуль начинает выполняться, как только завершены все модули, необходимые для его работы.
Для случая p процессоров можно распределить модули по процессорам, задав для каждого процессора $$P_i$$ множество модулей, выполняемых этим процессором:
$$D(P_i)=\{M_{i,1},M_{i,2},… M_{i,r}\}$$Распределение модулей по процессорам совместно с графом зависимостей однозначно определяет расписание работ и время выполнения программы при данном расписании. Предполагается, что каждый процессор выполняет модули из распределения $$D(P_i)$$. После завершения очередного модуля он сразу же переходит к выполнению следующего модуля, если для этого модуля выполнены все зависимости, заданные графом зависимостей. В противном случае процессор ждет окончания работы требуемых модулей. Время завершения последнего модуля в распределении $$D(P_i)$$ задает время работы данного процессора. Тот процессор, который последним заканчивает работу и определяет общее время решения задачи $$T_p^D$$ для данного расписания. Введенная ранее характеристика $$T_p$$ предполагает оптимальное расписание:
$$T_p=min_D T_p^D$$Задача составления оптимального расписания относится к сложным задачам. На практике для программ большого размера не удается явно вычислить значение $$T_p$$. По этой причине несомненный интерес представляет получение оценок для $$T_p$$.
Для введенных характеристик выполняется естественное соотношение:
$$T_{\mathcal {1}}\le T_p\le T_1$$Нас будет интересовать получение более точных оценок для $$T_p$$.
Рассмотрим вначале упрощенную ситуацию, предположив, что время выполнения всех модулей одинаково и равно t. Нетрудно видеть, что
Действительно, один процессор должен выполнить все модули программы, проходя, например, последовательно один уровень за другим.
Нетрудно посчитать и время $$T_{\mathcal {1}}$$
$$T_{\mathcal {1}}=k\cdot t$$Действительно, пусть на первом уровне $$n_1$$ модулей. У них есть все необходимые данные, и они могут выполняться параллельно. Поскольку число процессоров неограниченно, то запустив каждый модуль на одном из $$n_1$$ имеющихся процессоров, за время t завершим выполнение модулей первого уровня. Пусть за время $$i \cdot t$$ завершено выполнение всех модулей всех уровней от первого до i-го. Тогда возможно параллельно выполнять модули следующего i + 1-го уровня, число которых равно $$n_{i+1}$$. Процессоров у нас хватает, поэтому на завершение всех модулей этого уровня потребуется t времени, и общее время выполнения равно $$(i + 1) \cdot t$$, что по индукции доказывает справедливость формулы (3).
Для времени $$T_p$$ получим оценки сверху и снизу. Понятно, что p процессоров, начав одновременно работать, могут выполнить вычисление $$n_i$$ модулей уровня i за время $$\left \lceil \frac{n_i}{p}\right \rceil \cdot t$$, где $$\left \lceil x\right \rceil$$ обозначает минимальное целое, большее или равное x. Два процессора смогут выполнить пять модулей уровня 1 за время $$3 \cdot t$$. Отсюда следует, что общее время работы $$T_p$$ дается формулой:
Поскольку $$\left \lceil x\right \rceil \ge x$$, то
$$T_p\ge \sum_{i=1}^k \frac{n_i}{p} \cdot t=\frac{t}{p}\cdot \sum_{i=1}^k n_i=\frac{n \cdot t}{p}=\frac{T_1}{p}$$Формула (5) дает нижнюю оценку времени выполнения работы p процессорами.
Если на каждом уровне число модулей $$n_i$$ кратно p, то оценка достижима. В лучшем случае p процессоров могут сократить время выполнения программы в p раз в сравнении со временем, требуемом для выполнения этой работы одним процессором.
Получим теперь оценку сверху. Поскольку $$\left \lceil x\right \rceil \le x+1$$, то
$$T_p\le \sum_{i=1}^k \left ( \frac{n_i}{p}+1\right) \cdot t=\frac{t}{p}\cdot \sum_{i=1}^k n_i+\sum_{i=1}^k t=\frac{n \cdot t}{p}+k \cdot t=\frac{T_1}{p}+T_{\mathcal {1}}$$Объединяя (6) и (7), получим
$$\frac{T_1}{p}\le T_p\le \frac{T_1}{p}+T_{\mathcal {1}}$$Оценки (8) для случая, когда время выполнения всех модулей одинаково, известны [5].
Рассмотрим теперь более интересный для практики случай, когда модули программы для своего выполнения требуют разного времени. Пусть $$M^i$$ - множество модулей уровня i:
Для каждого из этих модулей известно время, требуемое на его выполнение - $$t_{i, j}$$.
И в этом случае нетрудно рассчитать время $$T_1$$ - время, требуемое на выполнение всей работы одним процессором:
$$T_1= \sum_{i=1}^k \sum_{j=1}^{k_i} t_{i, j}$$Как рассчитать время $$T_{\mathcal {1}}$$ в этой ситуации, когда мы располагаем неограниченным числом процессоров? Введем для каждого модуля время окончания его работы - $$t_j^i$$. Это время будем рассчитывать по следующей формуле:
$$t_j^i= t_{i, j}+t_{jmax}^{i-1}$$Здесь $$t_{jmax}^{i-1}$$ - время окончания работы того модуля уровня i-1, который:
Тогда время $$T_{\mathcal {1}}$$ можно рассчитать следующим образом:
$$T_{\mathcal {1}}= max_j \{ t_j^k \}$$Формула (12) говорит, что время завершения последнего модуля уровня k и является временем $$T_{\mathcal {1}}$$ при оптимальном расписании работ. Справедлива следующая теорема:
Время $$T_{\mathcal {1}}$$ задается максимально нагруженным путем в графе зависимостей.
Прежде всего, докажем, что при неограниченном числе процессоров оптимальное расписание каждого процессора содержит не более одного модуля на каждом уровне. Доказательство дается индукцией по числу уровней. Для уровня 1 утверждение справедливо, поскольку на этом уровне число процессоров совпадает с числом модулей этого уровня для оптимального расписания. Пусть утверждение справедливо на уровне j. Покажем, что оно остается справедливым и для модулей следующего уровня j + 1. Действительно, рассмотрим процессор Pr, выполняющий i-й модуль уровня j - $$M_i^j$$. Когда этот процессор завершит работу, то может оказаться, что появятся готовые к выполнению m модулей уровня j +1, ожидавших завершения работы $$M_i^j$$. Только один из этих модулей включается в оптимальное расписание процессора Pr, а остальные будут включены в расписание свободных процессоров, участвующих в работе. Если таковых не окажется, то
всегда можно добавить новые процессоры, так что все модули, ожидавшие завершения работы модуля $$M_i^j$$, начнут выполняться одновременно. Отсюда по индукции следует справедливость утверждения для всех уровней. Отсюда же следует, что $$T_{\mathcal {1}}$$ не может быть больше времени, задаваемого критическим путем.
Покажем теперь, что оптимальное расписание может быть составлено таким образом, чтобы критический путь был назначен одному процессору. Пусть процессор Ps - тот процессор, которому назначен $$M_i^1$$ первого уровня, лежащий на критическом пути. Спускаясь по уровням, этому процессору будем назначать модуль, лежащий на критическом пути. Так построенное расписание сохраняет свойство оптимальности, поскольку процессор Ps не простаивает, и ни какой другой процессор не может начать выполнять модули, лежащие на критическом пути, раньше процессора Ps. Заметьте, критический путь, вообще говоря, может быть не единственным.
Сложнее получить формулу для вычисления $$T_p$$. Проблема составления оптимального расписания в этих условиях относится к NP - полным проблемам, что означает, отсутствие алгоритма полиномиальной сложности, и для решения задачи необходимы переборные алгоритмы. Этим мы не будем заниматься.
Займемся тем, что покажем справедливость ранее полученных оценок (8) для $$T_p$$ в случае, когда время выполнения модулей различно и в графе зависимостей для каждого модуля задано время его работы:
$$\frac{T_1}{p}\le T_p\le \frac{T_1}{p}+T_{\mathcal {1}}$$Дадим вначале графическую интерпретацию. Задание нижней и верхней оценки для $$T_p(p)$$ означает, что эта функция ограничена двумя гиперболами. Функция убывающая. В начальной точке при p=1 по определению $$T_p(1) = T_1$$, так что функция находится в заданном коридоре. Это же справедливо и для конечных точек, для всех p, больших некоторого значения p*, при котором $$T_p = T_{\mathcal {1}}$$. Остается показать, что утверждение верно и для остальных значений $$1 < p < p*$$. Рис. 1.2 иллюстрирует поведение $$T_p$$.
(рис 1.2) Поведение функции Tp(p)
Приведем пример. Рассмотрим двух уровневую систему модулей, граф зависимостей которых показан на Рис. 1.1.
Нетрудно посчитать, что в этом случае:
$$T_1 = 30; T_{\mathcal {1}} = 13;$$Для случая двух процессоров для этого конкретного примера несложно задать оптимальное расписание. Для первого процессора последовательность выполняемых им модулей может быть следующей:
$$P1 = M_1^1, M_2^1, M_1^2, M_3^2\}$$Для второго процессора последовательность следующая:
$$P2 = \{M_3^1, M_4^1, M_2^2\}$$Время работы первого процессора равно 15, второго - 15. Следовательно, $$T_2$$ равно 15. Критический путь входит в расписание второго процессора. Подключение второго процессора в этой задаче позволяет вдвое уменьшить время выполнения в сравнении со случаем использования только одного процессора. Подключение третьего процессора, хотя и не столь эффективно, но позволит свести время выполнения до минимально возможного результата - $$T_{\mathcal {1}}$$. Добавление других процессоров не имеет смысла, поскольку не позволяет сократить время решения задачи.
После рассмотрения примера, перейдем к получению оценок.
Для $$T_p$$ справедлива оценка
$$T_p\ge \frac{T_1}{p}$$Докажем справедливость оценки. Пусть p процессоров выполняют работу согласно оптимальному расписанию, и ни один из процессоров не простаивает до окончания всей работы. Поскольку в результате все модули будут выполнены, и ни один модуль не будет выполняться дважды, то суммарное время работы всех процессоров равно $$T_1$$:
$$T_1=\sum^p_{i=1} T(P_i)$$Поскольку $$T_p$$ - это максимальное значение, затраченное одним из процессоров, на выполнение своей работы:
$$T_p=max_iT(P_i)$$Справедливость нижней оценки
$$T_p\ge \frac{T_1}{p}$$следует из общих свойств суммы компонентов. Максимальный компонент всегда больше или равен среднего арифметического значения суммы.
Если некоторые процессоры могут простаивать, то время $$T_p$$ может только увеличиваться, что гарантирует выполнения условия (16).
Равенство достигается в единственном случае, когда все компоненты суммы имеют одно и то же значение. Содержательно это означает, что все процессоры одновременно начинают свою работу и одновременно ее заканчивают. В этом случае общее время выполнения работы сокращается в p раз.
Пусть работу выполняют p процессоров. Составление расписания означает, что граф зависимостей разбивается на p непересекающихся подграфов. Все модули каждого из подграфов выполняются одним процессором. Подграф с максимальным временем выполнения для данного разбиения будем называть максимально нагруженным подграфом. Оптимальное расписание предполагает такое разбиение, при котором максимально нагруженный подграф выполняется за минимально возможное время. Итак, будем предполагать, что граф зависимостей G разбит на непересекающиеся подграфы $$G_i$$:
Не снижая общности, будем полагать, что максимально нагруженным подграфом является подграф $$G_1$$.
Для $$T_p$$ справедлива оценка
$$T_p\le \frac{T_1}{p}+T_{\mathcal {1}}$$Доказательство от противного. Покажем, что в этом случае разбиение не является оптимальным и может быть улучшено, что приведет к уменьшению времени $$T_p$$.
Итак, предположим, что
$$T_p=T(G_1)> \frac{\sum^p_{i=1}}{p}+T_{\mathcal {1}}$$Отсюда следует:
$$p \cdot T(G_1)> \sum^p_{i=1}T(G_I)+p \cdot T_{\mathcal {1}} \Rightarrow T(G_1)> \frac{\sum_{i=2…p}T(G_i)}{p-1}+\frac{p}{p-1}T_{\mathcal {1}}$$Пусть $$G_0$$ - минимально нагруженный подграф, тогда время его выполнения не больше среднего времени выполнения, так что имеем:
$$T(G_1)>T(G_0)+\frac{p}{p-1}T_{\mathcal {1}}$$Подграфу $$G_0$$ можно передать часть работ подграфа $$G_1$$, уменьшив суммарное время работы. Действительно, подграф $$G_1$$ можно представить в виде:
$$G_1= Path \bigcup G_1^'$$Здесь Path это часть пути или некоторый путь, начинающийся на первом уровне, который заведомо меньше критического пути. При передаче его подграфу $$G_0$$ время выполнения этого подграфа останется меньше времени выполнения подграфа $$G_1$$. Общее время выполнения работ при этом уменьшится. Следовательно, пришли к противоречию с утверждением об оптимальности расписания, что доказывает справедливость соотношения:
$$T_p=T(G_1)\le \frac{\sum^p_{i=1}T(G_I)}{p}+T_{\mathcal {1}}\le \frac{T_1}{p}+T_{\mathcal {1}}$$В заключение дадим некоторые практические рекомендации, следующие из полученных оценок. Выигрыш, который можно получить, используя дополнительные процессоры, зависит от разницы между общим временем выполнения всех модулей программы - $$T_1$$ и временем выполнения критического пути в графе зависимостей - $$T_{\mathcal {1}}$$.
Эта разница максимальна для крайнего случая, когда все модули могут выполняться независимо, и в графе зависимостей все модули находятся на одном первом уровне. Критический путь в этом случае состоит из одного модуля, требующего максимального времени своего выполнения. Так что $$T_1$$ - это время выполнения всех модулей, а $$T_{\mathcal {1}}$$ - это время выполнения одного модуля. Привлечение p процессоров может дать существенный эффект, уменьшая время выполнения практически до среднего времени выполнения одного модуля $$\frac{T_1}{p}$$.
Эта разница минимальна для другого крайнего случая - строго последовательной программы, когда N модулей программы расположены на N уровнях, и критический путь задает выполнение всех модулей. В этом случае $$T_1$$ и $$T_{\mathcal {1}}$$ совпадают и, как следствие, $$T_p$$ равно $$T_1$$ при любом числе процессоров, так что привлекать дополнительные процессоры в этом случае бессмысленно.
Для строго последовательной программы, когда i-й модуль зависит от модуля i-1, все три характеристики будут совпадать. Для строго последовательной программы дополнительные процессоры не позволяют уменьшить время выполнения программы в сравнении со временем выполнения этой же программы одним процессором. Так, например, задача о "Ханойской башне" на суперкомпьютере с сотнями тысяч процессоров будет решаться столь же долго, как и на компьютере с одним процессором. Это вытекает из сути задачи, - перенос следующего кольца требует завершение переноса предыдущего кольца, - параллельно эту работу выполнять нельзя.
В предыдущем разделе введены три параметра, характеризующие модель параллельных вычислений, - $$T_1$$, $$T_p$$, $$T_{\mathcal {1}}$$ - и заданы некоторые соотношения между ними. Продолжим эту тему и введем еще ряд характеристик. Все вводимые характеристики рассматриваются как функции параметра n, характеризующего сложность решаемой задачи. Обычно n понимается как объем входных данных.
Ускорение $$S_p(n)$$ определяют как отношение:
$$S_p(n)=\frac{T_1(n)}{T_p(n)}$$Важно правильно интерпретировать это отношение. Числитель и знаменатель, вообще говоря, рассчитываются для двух разных алгоритмов. Когда задача ориентирована на выполнение одним процессором, то можно построить алгоритм, оптимальный для последовательного выполнения. Использование нескольких процессоров, одновременно ведущих вычисления, требует другого алгоритма, предусматривающего распараллеливание. Построение хороших параллельных алгоритмов - это не простая задача. Чаще всего, хороший последовательный алгоритм не является таковым для параллельного выполнения.
Если у нас есть некоторая задача, и речь идет о том, какого ускорения можно добиться при распараллеливании, то в формуле (24) следует сравнивать время наилучшего последовательного алгоритма, для которого достаточно одного процессора, и время наилучшего параллельного алгоритма, который может использовать p имеющихся процессоров.
Какое ускорение является оптимальным? Ответ на этот вопрос дают оценки для $$T_p$$, полученные в предыдущем разделе. Из нижней оценки следует, что ускорение не может превосходить числа процессоров:
$$S_p(n) \le p$$Иногда эта оценка нарушается, и ускорение реально может быть больше p. В этом случае говорят о гиперускорении. Гиперускорение может возникнуть, если добавление процессоров влияет не только на вычисления. Например, появляется дополнительная память, возможно, другие устройства, способствующие ускорению решения задачи.
Максимальное ускорение для задачи задается соотношением:
$$S_{\mathcal {1}}(n)=\frac{T_1(n)}{T_{\mathcal {1}}(n)}$$Эффективность $$E_p(n)$$ определяют как отношение:
$$E_p(n)=\frac{S_p(n)}{p}$$Добиваться высокого ускорения следует, но не любой ценой. При оптимальном ускорении эффективность равна 1. Если же эффективность существенно ниже 1, то часто число процессоров целесообразно уменьшить, используя их более эффективно. Поясним ситуацию примером. Рассмотрим классическую задачу вычисления суммы элементов массива. Последовательный алгоритм, используя один процессор, вычисляет сумму за время порядка O(n). Схема вычисления показана на Рис. 1.3
(рис 1.3) Последовательное суммирование
Вычисление суммы можно распараллелить, построив пирамидальный алгоритм, который будет вычислять сумму за время O(log n), но для него на первом шаге потребуется n/2 процессоров, которые будут вычислять суммы пар элементов массива. На следующем шаге, число процессоров сократится вдвое, когда вычисляются суммы четверок. Для получения окончательного результата на последнем шаге потребуется всего один процессор. Схема вычисления показана на Рис. 1.4
(рис 1.4) Схема пирамидального параллельного алгоритма вычисления суммы элементов
Ускорение для этого алгоритма при вычислении суммы большого числа элементов прекрасное:
$$S_p(n)=\frac{n}{log_2n}$$При n, равном 220, например, ускорение более 215, составляет десятки тысяч раз. Но и процессоров требуется такого же порядка. Посчитаем эффективность для этого случая:
Для нашего примера эффективность будет равна 0,1. Возможно, более разумно в этой ситуации использовать конечное число процессоров. Например, имея 16 процессоров, можно разделить массив на 16 частей, для каждой из них процессоры вычислят частные суммы, а потом останется сложить эти частные суммы. В этом случае ускорение будет равно 16, но эффективность практически равна 1.
На проблему эффективности можно смотреть и с другой точки зрения. Пусть в нашем распоряжении есть многоядерный компьютер. Возникает естественный вопрос, насколько эффективно используются его возможности?
Введем в рассмотрение меру неиспользованных возможностей - упущенной выгоды - U(n), определив ее следующим образом:
Полагая, что оптимальное время, которое можно достичь, используя p процессоров, дается нижней оценкой для $$T_p$$, получим:
$$U_p(n)=p \frac{T_p(n)}{T_1}-1$$Если для компьютера с p ядрами время решения задачи оптимально и сокращается в p раз в сравнении с решением задачи на одноядерном компьютере, то наши потери равны нулю, возможности компьютера полностью используются. Если же задача решается за время $$T_1$$ - столь же долго, как на одноядерном компьютере, то потери пропорциональны числу неиспользованных ядер.
Ранее получены оценки для времени решения задачи при использовании p процессоров. При этом предполагалось, что задачу можно разделить на модули, задав граф зависимостей, определяющий возможный порядок вызова модулей. Представляет интерес рассмотрения случая, когда задачу можно разделить на две части, из которых одна часть требует последовательного выполнения, а вторая может быть полностью распараллелена. Законы Амдаля и Густавсона - Барсиса позволяют получить оценки для ускорения в зависимости от доли последовательных вычислений в общем времени решения задачи. Законы отличаются лишь тем, как определяется доля последовательных вычислений.
Пусть время решения задачи одним процессором можно представить как сумму времен решения последовательной части и части, допускающей распараллеливание:
$$T_1=T_{1succ}+T_{1par}$$Разделив обе части уравнения на $$T1$$, перейдем к долям времени:
$$ q= \frac{T_{1succ}}{T_1}; 1-q= \frac{T_{1par}}{T_1}$$Время решения задачи p процессорами также представим двумя частями:
$$T_p=T_{psucc}+T_{ppar}$$Последовательную долю нельзя уменьшить увеличением числа процессоров, поэтому $$T_{psucc} = T_{1succ}$$. Для параллельной части существует оценка, так что имеет место соотношение:
$$T_p \ge T_{1succ}+\frac {T_{1par}}{p}$$Переходя к ускорению, получим:
$$S_p =\frac {T_1}{T_p}\le \frac {T_1}{{T_{1succ}}+\frac {T_{1par}}{p}}}=\frac {1}{{\frac {T_{1succ}}{T_1}+\frac {T_{1par}}{T_1 \cdot p}}}=\frac {1}{q+\frac {1-q}{p}}\le \frac {1}{q}$$Соотношение (30) называется законом Амдаля. Оно говорит, что ускорение ограничено сверху величиной, зависящей от доли последовательных вычислений. Если, например, последовательные вычисления занимают 10% от общего времени вычисления, то за счет распараллеливания нельзя добиться более чем десятикратного ускорения времени работы, сколь много процессоров бы не привлекалось.
Пессимистический характер закона Амдаля может быть сглажен, если вспомнить, что все характеристики следует рассматривать, как функции от n - параметра характеризующего объем используемых данных. В этом случае закон Амдаля выглядит так:
На практике часто бывает, что последовательная часть задачи постоянна и не зависит от объема данных. В этом случае q(n) - убывающая функция, тогда для больших n можно добиться хорошего ускорения, не вступая в противоречие с законом Амдаля.
Запишем оптимальное время работы при использовании p процессоров в виде суммы времен двух частей - параллельной и последовательной:
$$T_{popt}= T_{popt\_succ}+T_{popt\_par}$$С учетом того, что последовательная часть выполняется p процессорами столь же долго, как одним процессором, а время параллельной части в оптимальном случае можно уменьшить в p раз, получим:
$$T_{popt}= T_{1succ}+\frac{T_{1par}}{p}$$Разделив обе части уравнения на $$T_{popt}$$, перейдем к долям времени:
$$g= \frac{T_{1succ}}{T_{popt}}; 1-g= \frac{T_{1par}}{p \cdot T_{popt}}$$Рассмотрим теперь отношение:
$$\frac{T_1}{T_{popt}}=\frac{T_{1succ}+T_{1par}}{T_{popt}}=g+p \cdot (1-g)$$Переходя к ускорению, получим
$$ S_p=\frac{T_1}{T_p}\le \frac{T_1}{T_{popt}}=g+p \cdot (1-g)$$Соотношение (32) выражает закон Густавсона-Барсиса, задавая оценку сверху для ускорения. Когда доля g стремится к единице, то и ускорения нет, оно ограничено единицей. Если же доля стремится к нулю, то ускорение, как и положено, ограничено числом используемых процессоров p.
Как и в законе Амдаля, характеристики следует рассматривать как функции параметра n:
Говоря о распараллеливании, различают два основных способа, позволяющих проводить параллельные вычисления, - распараллеливание по задачам и распараллеливание по данным.
Модель, рассмотренная выше, соответствовала случаю распараллеливания по задачам. В этой модели разные модули одной программы могли выполняться параллельно.
Рассмотрим теперь альтернативную ситуацию, когда выполняется распараллеливание по данным. В этом случае некоторое множество данных необходимо обработать одним модулем.
Пусть необходимо решить задачу D на некотором конечном множестве данных $$X = \{ x_1, x_2, …x_n\}$$. Зачастую, эффективный последовательный алгоритм решения этой задачи можно получить, если удается свести решение исходной задачи к решению k подзадач - $$D(X_i) ( i = 1, 2 …k)$$, где каждая подзадача означает решение исходной задачи D, но на подмножестве данных $$X_i$$. Наиболее эффективно, когда все подзадачи имеют один и тот же размер.
Справедлива простая, но крайне важная в теории алгоритмов
Если задачу D(X) можно свести к решению k подзадач одинаковой размерности и за линейное время из решений k подзадач можно получить общее решение исходной задачи, то временная сложность решения исходной задачи T(n) дается формулой:
Здесь с - некоторая константа.
Для простоты будем полагать, что $$n = k^m$$. Тогда с учетом сделанных предположений
$$T(n) = T(k^m) = k \cdot T( k^{m-1}) + c \cdot k^m = k \cdot (k \cdot T(k^{m-2}) + c \cdot k^{m-1}) + c \cdot k^m = k^2 \cdot T(k^{m-2}) + 2\cdot c \cdot k^m$$Продолжая разворачивать этот процесс, дойдем до времени T(1), которое можно считать без ограничения общности константой, равной c. Таким образом, получим:
Эффективный последовательный алгоритм предполагает рекурсивное определение. За счет сведения исходной задачи к решению нескольких задач меньшей размерности удается существенно снизить временную оценку сложности решения задачи в сравнении со случаем, когда задача решается для полного набора данных.
Классическим примером являются алгоритмы сортировки. В сортировке слиянием исходное множество разделяется на два подмножества практически одинаковой мощности (размер может отличаться на единицу). Слияние двух отсортированных подмножеств можно выполнить за линейное время. Поэтому временная сложность этой сортировки в соответствии с соотношением (35) задается формулой $$O(n \cdot log_2 n)$$. В то же время сложность таких простых алгоритмов сортировки как, например, пузырьковая сортировка задается соотношением $$O(n \cdot n)$$. При больших n, например при $$n = 2^20$$, время сортировки слиянием может быть в тысячи раз меньше времени пузырьковой сортировки.
Этот пример показывает, что и последовательные алгоритмы могут эффективно использовать распараллеливание по данным. А что могут дать в этой ситуации параллельные алгоритмы, использующие наличие k процессоров.
Пусть у нас есть компьютер, имеющий k ядер, и нужно решить задачу на множестве данных размерности $$k^m$$. Самое простое решение состоит в том, чтобы разбить исходное множество на k подмножеств одинаковой размерности $$k^{m-1}$$. Затем применять эффективный рекурсивный последовательный алгоритм, решая параллельно на всех ядрах исходную задачу для соответствующего подмножества. После этого за линейное время объединить полученные решения. Учитывая ранее полученные соотношения, временная сложность такого алгоритма дается соотношением:
Сравнивая соотношения (35) и (36), можно видеть, что за счет использования k ядер можно в k раз уменьшить сложность алгоритма. Заметьте, рассматриваемая версия алгоритма использует рекурсию только в последовательной версии, запускаемой на каждом ядре. Использование рекурсии в параллельных алгоритмах не всегда приводит к повышению эффективности.
В заключение первой главы кратко рассмотрим некоторые проблемы, возникающие при организации параллельных вычислений.
Когда несколько модулей одной и той же программы запускаются на разных процессорах, то возникает необходимость в синхронизации их действий.
Модулю А могут быть необходимы результаты работы модулей В и С, поэтому начать свое выполнение модуль А может лишь по завершении работы как модуля В, так и модуля С, которые могут выполняться параллельно, но не известно, какой из них первым закончит работу. В любом случае запуск модуля А на выполнение должен быть синхронизирован с окончанием работ модулей В и С.
При распараллеливании по данным один и тот же модуль F может быть запущен на k процессорах и параллельно выполняться, обрабатывая разные подмножества данных $$(X_1, X_2, …X_k)$$. Результаты работы k процессоров затем объединяются в процессе работы модуля G. Понятно, что запуск на выполнение модуля G должен быть синхронизирован с окончанием работы модуля F на всех параллельно работающих k процессорах.
Параллельные вычисления требуют тщательной синхронизации работы модулей программы, выполняемых разными процессорами.
Так называемая проблема "гонки данных" возникает для мультипроцессорных компьютеров с общей памятью. Поскольку процессоры работают параллельно, то в одни и те же моменты времени они могут получать доступ к одним и тем же данным, хранимым в общей памяти, как для чтения, так и для записи.
Если совместное чтение данных представляется возможным и допустимым, то одновременная запись двух разных значений в одну и ту же ячейку памяти не допустима. Запись всегда будет идти по очереди. Конкурирование процессоров за запись в одно и то же слово памяти и называется "гонкой данных". Интересно, что в этой гонке выигрывает не тот, кто пришел первый, а тот, кто пришел последний, поскольку именно его результаты будут сохранены в памяти. Это соответствует пословице: "хорошо смеется тот, кто смеется последним".
Чтобы справиться с проблемой "гонки данных", существуют разные механизмы закрытия памяти - одного из видов совместно используемого ресурса. Тот, кто выигрывает гонку и приходит первым, закрывает ресурс для доступа. Проигравшие гонку прерывают выполнение и становятся в очередь за обладание ресурсом. Обладатель ресурса спокойно выполняет свою работу, а по ее окончании открывает ресурс, с которым теперь начинает работать тот, кто первым стоит в очереди.
Гонка данных - это одна из самых серьезных проблем параллельного программирования, поскольку при некорректно организованной блокировке ресурса программа может завершаться с некорректными результатами без возникновения исключительных ситуаций.
Плохо, когда в процессе работы программы происходит отказ и нужные нам результаты не могут быть получены. Но еще хуже, когда программа завершается, выдает результаты, но эти результаты ошибочны. Плохо, когда студент на экзамене говорит: "не знаю", но хуже, когда он говорит "глупости".
Чтобы справиться с гонкой данных, приходится включать блокировку, закрывая ресурс для других конкурентов, которые должны прервать свою работу и томиться в очереди, ожидая момента освобождения ресурса. Блокировка - полезный механизм, обойтись без которого в ряде ситуаций просто невозможно. Но блокировка - это и опасный механизм, порождающий прерывание работы всей программы, когда возникает ситуация, называемая тупиком, клинчем или смертельным объятием.
Рассмотрим простейшую ситуацию, приводящую к возникновению клинча. Пусть есть два конкурента А и В, претендующие на два ресурса f и g. Пусть гонку за ресурс f выиграл А и соответственно закрыл этот ресурс для В. Гонку за ресурс g выиграл В и закрыл ресурс для А. Но А, чтобы закончить свою работу нужен ресурс g, поэтому он стал в очередь, ожидая освобождения ресурса g. Симметрично, В томится в очереди, ожидая освобождения ресурса f. Возникает ситуация клинча, когда ни А, ни В не могут продолжить свою работу.
В боксе, когда два боксера входят в клинч, сцепившись друг с другом, нужен судья, дающий команду "break", чтобы боксеры могли разойтись и продолжить бой. Так и в параллельных вычислениях при возникновении клинча, только внешнее воздействие может разрешить ситуацию.
Для мультикомпьютерных комплексов, где каждый компьютер комплекса имеет собственную память, проблемы гонки данных и клинча не столь актуальны. Здесь возникает своя не менее серьезная проблема. Хотя каждый компьютер комплекса работает со своими данными, но все параллельно работающие компьютеры решают одну и ту же задачу, поэтому без обмена информацией обойтись невозможно. В процессе работы компьютеры должны обмениваться данными, посылая друг другу сообщения. В кластерах (типичном виде мультикомпьютерного комплекса) компьютеры объединены высокоскоростными линиями связи. Тем не менее, передача данных является медленной операцией, и время на передачу данных может "съесть" весь выигрыш, полученный за счет распараллеливания вычислений. Поэтому при анализе эффективности работы программы, работающей на кластере или другом мультикомпьютерном комплексе, где параллельно работающие процессоры обмениваются сообщениями по линиям связи, не имея доступа к общей памяти, важную роль играют операции п осылки и получения сообщений (send - receive, map - reduce).
Пусть на кластере, содержащем k компьютеров, нужно решить некоторую задачу D на множестве данных X.
Алгоритм решения может быть задан следующей схемой:
Map(X); //Исходное множество X разбивается на k подмножеств, каждое из которых
//пересылается на соответствующий компьютер кластера.
Parallel_D(Xi); //Задача D параллельно запускается на каждом компьютере,
//обрабатывая подмножество данных Xi, и получая результат Yi.
Reduce(Y); //Результаты работы каждого компьютера Yi объединяются, создавая общее
//решение Y.
Для последовательного алгоритма время решения исходной задачи может быть записано в виде:
$$T_{sec}(D) = T(D(X(n)))$$Для параллельного алгоритма время решения исходной задачи может быть записано в виде:
$$T_{par}(D) = T(Map(n, k)) + T(D(X(n/k))) + T(Reduce(n, k))$$Как правило, Map и Reduce имеют линейную сложность. Полагая, что архитектура кластера позволяет одновременно пересылать данные всем компьютерам кластера, можно записать следующие соотношения для времени выполнения этих операций:
Аналогично
$$T(Reduce(n, k)) = c_r \cdot n/k$$Какой же алгоритм предпочтительнее по времени выполнения - последовательный или параллельный? В этих условиях все зависит от сложности задачи D. Если это простая задача с линейной временной сложностью
то вероятнее всего последовательный алгоритм будет эффективнее, поскольку обычно константы $$c_m$$ и $$c_r$$ много больше константы $$c_d$$. Так что будет выполняться соотношение:
$$c_d \cdot n < (c_m + c_r + c_d) \cdot n/k$$Для этого достаточно выполнения условия:
$$ c_d < (c_m + c_r )/k$$Для сложной в вычислительном отношении задачи D параллельный алгоритм, скорее всего, окажется эффективнее. Так, для задачи D, имеющей кубическую сложность, выполнение условия:
гарантирует эффективность параллельного алгоритма.
На этом завершим первую главу. В последующих главах появятся конкретные примеры, иллюстрирующие положения, рассмотренные в этой главе.
Первый вопрос, на который следует дать ответ, - какие вычисления программы на компьютере следует называть параллельными. Но это не единственный вопрос, на который хотелось бы получить ответ. Не менее важно понять, зачем вообще переходить из простого, хорошо знакомого, понятного мира последовательных вычислений к сложному для понимания миру параллельных вычислений. Какие преимущества есть у параллельных вычислений, и какие проблемы ждут программиста при создании программ, ориентированных на параллельные вычисления. Чтобы ответить на эти вопросы, давайте совершим небольшой экскурс в историю развития компьютеров.
Первые компьютеры были построены в соответствии с принципами, сформулированными Фон-Нейманом. Они имели три главных компонента - память, процессор и некоторый набор внешних устройств, обеспечивающих ввод и вывод информации.
Память была многоуровневой и для первых компьютеров содержала внешнюю память и внутреннюю память - оперативную и регистровую. Внешняя память (на магнитных лентах, перфокартах, дисках) позволяла сохранять программы и данные вне зависимости от того, включен компьютер или нет. Внутренняя память хранила информацию только на период сеанса работы с компьютером. При отключении компьютера содержимое внутренней памяти исчезало.
Для того чтобы программа могла быть выполнена на компьютере, она должна была быть загружена в оперативную память. Хранилась она там точно также как и данные, обрабатываемые этой программой. Принцип хранимой в памяти программы - один из главных принципов Фон-Неймановских компьютеров.
Регистровая память использовалась в момент выполнения вычислений. Прежде, чем выполнить некоторую операцию над данными, данные должны быть размещены на регистрах. Этот самый быстрый вид памяти обеспечивал необходимое быстродействие при выполнении операций над данными.
Выполнение всех операций - операций над данными и операций по управлению процессом вычислений - осуществлял процессор. Процессор компьютера обладал определенным набором команд. Этот набор был достаточно универсальным, чтобы вычислить любую потенциально вычислимую функцию. С другой стороны этот набор обеспечивал относительную простоту написания программ человеком.
Программы для первых компьютеров представляли последовательность команд, входящих в допустимый набор команд процессора. Выполнение программы на компьютере осуществлялось достаточно просто. В каждый момент времени на компьютере выполнялась одна программа. Процессор, в соответствии с программой, последовательно выполнял одну команду за другой. Все ресурсы компьютера - память, время процессора, все устройства - были в полном распоряжении программы, и ничто не могло вмешаться в ее работу (не считая конечно человека). Параллелизма не было и в помине.
Такая идиллия продолжалась недолго по причине неэффективного использования ресурсов крайне дорогих в те времена компьютеров. Компьютеры тогда не выключались, - одна программа сменяла другую.
Достаточно скоро у компьютера наряду с процессором, который стал называться центральным процессором, появились дополнительные процессоры, в первую очередь специализированные процессоры устройств ввода-вывода информации, отвечающие за выполнение наиболее медленных команд. Это дало возможность организации пакетного режима выполнения программ, когда на компьютере одновременно выполнялись несколько программ - одна программа могла печатать результаты работы, другая - выполняться, третья - вводить необходимые ей данные, например с магнитной ленты или другого внешнего носителя.
Революционным шагом было появление в 1964 году операционной системы фирмы IBM - OS 360. Появившаяся у компьютера операционная система стала его полновластным хозяином - распорядителем всех его ресурсов. Теперь программа пользователя могла быть выполнена только под управлением операционной системы. Операционная система позволяла решить две важные задачи - с одной стороны обеспечить необходимый сервис всем программам, одновременно выполняемым на компьютере, с другой - эффективно использовать и распределять существующие ресурсы между программами, претендующими на эти ресурсы. Появление операционных систем привело к переходу от однопрограммного режима работы к мультипрограммному, когда на одном компьютере одновременно выполняются несколько программ. Мультипрограммирование это еще не параллельное программирование, но это шаг в направлении параллельных вычислений.
Заметим, что наличие у компьютера нескольких процессоров является необходимым условием для мультипрограммирования. Существование операционной системы, организующей взаимную работу процессоров, достаточно для реализации мультипрограммирования. Для параллельных вычислений накладывается дополнительное требование - это требование к самой программе, - программа должна допускать возможность распараллеливания вычислений.
Появление операционной системы означало, что компьютер нельзя рассматривать только как "железо" (память, процессоры, другие устройства). Теперь у него две составляющие - хард (hard) и софт (soft) - аппаратная и программная составляющие, взаимно дополняющие друг друга. За полвека существования компьютеров оба компонента стремительно развивались.
Для аппаратуры характерен экспоненциальный рост, что нашло отражение в известном эмпирическом законе Мура, - экспоненциально росли все важнейшие характеристики - объем памяти на всех уровнях, уменьшение времени доступа к памяти, быстродействие процессоров. Согласно закону Мура (Гордон Мур - один из основателей фирмы Intel) каждые полтора года значения характеристик увеличивались вдвое. Росло и число процессоров, включаемых в состав компьютера. Изменялась и архитектура компьютера. Эти изменения во многом были шагами в сторону распараллеливания вычислений. Вот лишь некоторые изменения в архитектуре процессоров, связанные непосредственно с процессом распараллеливания:
В научных исследованиях и в новых технологиях всегда есть задачи, которым требуется вся мощь существующих вычислительных комплексов. Научный потенциал страны во многом определяется существованием у нее суперкомпьютеров. Понятие суперкомпьютера это относительное понятие. Характеристики суперкомпьютера десятилетней давности сегодня соответствуют характеристикам рядового компьютера. Сегодняшние суперкомпьютеры имеют производительность, измеряемую в петафлопсах (1015 операций с плавающей точкой в секунду). К 2020 году ожидается, что производительность суперкомпьютеров повысится в 1000 раз и будет измеряться в экзафлопсах.
Мир компьютеров многообразен, начиная от миниатюрных встроенных компьютеров до многотонных суперкомпьютеров, занимающих отдельные здания. Классифицировать их можно по-разному. Рассмотрим одну из первых и простейших классификаций - классификацию Флинна, основанную на том, как устроена в компьютере обработка данных. Согласно этой классификации все компьютеры (вычислительные комплексы) можно разделить на четыре класса - компьютеры с архитектурой:
Мы не будем рассматривать подробную классификацию компьютеров класса MIMD. Остановимся только на другом способе разделения компьютеров на три класса:
Мы говорили об архитектуре вычислительных комплексов, способных обеспечить параллельное выполнение программ. Но архитектура комплекса - это лишь одно из требований, необходимых для реализации подлинного параллелизма. Другие два требования связаны с требованиями к операционной системе и к самой программе. Не всякую программу можно распараллелить независимо о того, на каком суперкомпьютерном комплексе она будет выполняться. В следующих главах мы подробнее поговорим о средствах операционной системы, обеспечивающих параллелизм вычислений, и о параллельных алгоритмах. Сейчас же рассмотрим некоторую модель параллельного выполнения, где главным действующим лицом будет программа.
Параллельные вычисления становятся одним из магистральных направлений развития информационных технологий. Можно указать на две причины, определяющие важность этого направления. Первая состоит в том, что стратегически важные для развития государства задачи могут быть решены только с применением суперкомпьютеров, обладающих сотнями тысяч процессоров, которые нужно заставить работать одновременно. Вторая причина связана с другим полюсом компьютерной техники, на котором находятся обычные компьютеры, ориентированные на массового пользователя. И эта техника становится многоядерной, и ее требуется эффективно использовать, так что параллельные вычисления требуются и здесь.
Для поддержки параллельных вычислений сделано достаточно много, начиная от архитектуры вычислительных систем, операционных систем, языков программирования до разработки специальных параллельных алгоритмов. Тем не менее, для программиста, решающего сложную задачу, построение и отладка эффективной параллельной программы все еще остается не простым занятием.
Рассмотрим одну из моделей параллельного вычисления. Для этой модели мы хотим получить оценки времени выполнения программы одним процессором - $$T_1$$, конечным числом процессоров - $$Т_p$$, и для идеализированного случая, когда число процессоров не ограничивается - $$T \mathcal {1}$$.
Рассмотрим программу P, состоящую из n модулей:
Будем предполагать, что программа P выполняется на компьютере, обладающим некоторым числом процессоров, работающих на общей памяти. Выходные данные, полученные в результате работы модуля $$M_i$$, могут являться входными данными для модуля $$M_j$$. Так естественным образом возникает зависимость между модулями, определяющая возможный порядок их выполнения.
Множество модулей разобьём на k уровней. К уровню i отнесем те модули, для начала работы которых требуется завершение работы модулей верхних уровней, из которых хотя бы один принадлежит уровню i - 1. Модуль уровня i с номером k будем обозначать как $$M_k^i$$.
Модули, принадлежащие уровню 1, имеют все необходимые данные, полученные от внешних источников. Они не требуют завершения работы других модулей и в принципе могут выполняться параллельно, будучи запущенными в начальный момент выполнения программы.
Свяжем с программой P ориентированный граф зависимостей модулей. Граф не содержит циклов и отражает разбиение модулей на уровни. Модули являются вершинами графа, а дуги отражают зависимости между модулями. Дуга ведет от модуля $$M_k^i$$ к модулю $$M_1^j$$, если для начала выполнения модуля $$M_k^i$$ требуется завершение работы модуля $$M_1^j$$. В узлах графа содержится информация об ожидаемом времени выполнения модуля, где время измеряется в некоторых условных единицах. На Рис. 1.1 показан пример графа зависимостей:
(рис 1.1) Пример графа зависимостей
Обозначим через $$T_1$$ - время, требуемое для выполнения программы P одним процессором, $$T_p$$ - p процессорами, $$T_{\mathcal {1}}$$ - время, требуемое в случае, когда число процессоров неограниченно. В последнем случае достаточно n процессоров, по числу модулей нашей программы.
Предполагается, что все эти характеристики рассчитываются при соблюдении двух условий:
В случае одного процессора достаточно выполнение только первого условия. Обычно предполагается естественный порядок выполнения модулей, - последовательное выполнение модулей одного уровня, затем переход к выполнению модулей следующего уровня.
Для случая неограниченного числа процессоров оптимальным является такое расписание, когда каждый модуль начинает выполняться, как только завершены все модули, необходимые для его работы.
Для случая p процессоров можно распределить модули по процессорам, задав для каждого процессора $$P_i$$ множество модулей, выполняемых этим процессором:
$$D(P_i)=\{M_{i,1},M_{i,2},… M_{i,r}\}$$Распределение модулей по процессорам совместно с графом зависимостей однозначно определяет расписание работ и время выполнения программы при данном расписании. Предполагается, что каждый процессор выполняет модули из распределения $$D(P_i)$$. После завершения очередного модуля он сразу же переходит к выполнению следующего модуля, если для этого модуля выполнены все зависимости, заданные графом зависимостей. В противном случае процессор ждет окончания работы требуемых модулей. Время завершения последнего модуля в распределении $$D(P_i)$$ задает время работы данного процессора. Тот процессор, который последним заканчивает работу и определяет общее время решения задачи $$T_p^D$$ для данного расписания. Введенная ранее характеристика $$T_p$$ предполагает оптимальное расписание:
$$T_p=min_D T_p^D$$Задача составления оптимального расписания относится к сложным задачам. На практике для программ большого размера не удается явно вычислить значение $$T_p$$. По этой причине несомненный интерес представляет получение оценок для $$T_p$$.
Для введенных характеристик выполняется естественное соотношение:
$$T_{\mathcal {1}}\le T_p\le T_1$$Нас будет интересовать получение более точных оценок для $$T_p$$.
Рассмотрим вначале упрощенную ситуацию, предположив, что время выполнения всех модулей одинаково и равно t. Нетрудно видеть, что
Действительно, один процессор должен выполнить все модули программы, проходя, например, последовательно один уровень за другим.
Нетрудно посчитать и время $$T_{\mathcal {1}}$$
$$T_{\mathcal {1}}=k\cdot t$$Действительно, пусть на первом уровне $$n_1$$ модулей. У них есть все необходимые данные, и они могут выполняться параллельно. Поскольку число процессоров неограниченно, то запустив каждый модуль на одном из $$n_1$$ имеющихся процессоров, за время t завершим выполнение модулей первого уровня. Пусть за время $$i \cdot t$$ завершено выполнение всех модулей всех уровней от первого до i-го. Тогда возможно параллельно выполнять модули следующего i + 1-го уровня, число которых равно $$n_{i+1}$$. Процессоров у нас хватает, поэтому на завершение всех модулей этого уровня потребуется t времени, и общее время выполнения равно $$(i + 1) \cdot t$$, что по индукции доказывает справедливость формулы (3).
Для времени $$T_p$$ получим оценки сверху и снизу. Понятно, что p процессоров, начав одновременно работать, могут выполнить вычисление $$n_i$$ модулей уровня i за время $$\left \lceil \frac{n_i}{p}\right \rceil \cdot t$$, где $$\left \lceil x\right \rceil$$ обозначает минимальное целое, большее или равное x. Два процессора смогут выполнить пять модулей уровня 1 за время $$3 \cdot t$$. Отсюда следует, что общее время работы $$T_p$$ дается формулой:
Поскольку $$\left \lceil x\right \rceil \ge x$$, то
$$T_p\ge \sum_{i=1}^k \frac{n_i}{p} \cdot t=\frac{t}{p}\cdot \sum_{i=1}^k n_i=\frac{n \cdot t}{p}=\frac{T_1}{p}$$Формула (5) дает нижнюю оценку времени выполнения работы p процессорами.
Если на каждом уровне число модулей $$n_i$$ кратно p, то оценка достижима. В лучшем случае p процессоров могут сократить время выполнения программы в p раз в сравнении со временем, требуемом для выполнения этой работы одним процессором.
Получим теперь оценку сверху. Поскольку $$\left \lceil x\right \rceil \le x+1$$, то
$$T_p\le \sum_{i=1}^k \left ( \frac{n_i}{p}+1\right) \cdot t=\frac{t}{p}\cdot \sum_{i=1}^k n_i+\sum_{i=1}^k t=\frac{n \cdot t}{p}+k \cdot t=\frac{T_1}{p}+T_{\mathcal {1}}$$Объединяя (6) и (7), получим
$$\frac{T_1}{p}\le T_p\le \frac{T_1}{p}+T_{\mathcal {1}}$$Оценки (8) для случая, когда время выполнения всех модулей одинаково, известны [5].
Рассмотрим теперь более интересный для практики случай, когда модули программы для своего выполнения требуют разного времени. Пусть $$M^i$$ - множество модулей уровня i:
Для каждого из этих модулей известно время, требуемое на его выполнение - $$t_{i, j}$$.
И в этом случае нетрудно рассчитать время $$T_1$$ - время, требуемое на выполнение всей работы одним процессором:
$$T_1= \sum_{i=1}^k \sum_{j=1}^{k_i} t_{i, j}$$Как рассчитать время $$T_{\mathcal {1}}$$ в этой ситуации, когда мы располагаем неограниченным числом процессоров? Введем для каждого модуля время окончания его работы - $$t_j^i$$. Это время будем рассчитывать по следующей формуле:
$$t_j^i= t_{i, j}+t_{jmax}^{i-1}$$Здесь $$t_{jmax}^{i-1}$$ - время окончания работы того модуля уровня i-1, который:
Тогда время $$T_{\mathcal {1}}$$ можно рассчитать следующим образом:
$$T_{\mathcal {1}}= max_j \{ t_j^k \}$$Формула (12) говорит, что время завершения последнего модуля уровня k и является временем $$T_{\mathcal {1}}$$ при оптимальном расписании работ. Справедлива следующая теорема:
Время $$T_{\mathcal {1}}$$ задается максимально нагруженным путем в графе зависимостей.
Прежде всего, докажем, что при неограниченном числе процессоров оптимальное расписание каждого процессора содержит не более одного модуля на каждом уровне. Доказательство дается индукцией по числу уровней. Для уровня 1 утверждение справедливо, поскольку на этом уровне число процессоров совпадает с числом модулей этого уровня для оптимального расписания. Пусть утверждение справедливо на уровне j. Покажем, что оно остается справедливым и для модулей следующего уровня j + 1. Действительно, рассмотрим процессор Pr, выполняющий i-й модуль уровня j - $$M_i^j$$. Когда этот процессор завершит работу, то может оказаться, что появятся готовые к выполнению m модулей уровня j +1, ожидавших завершения работы $$M_i^j$$. Только один из этих модулей включается в оптимальное расписание процессора Pr, а остальные будут включены в расписание свободных процессоров, участвующих в работе. Если таковых не окажется, то
всегда можно добавить новые процессоры, так что все модули, ожидавшие завершения работы модуля $$M_i^j$$, начнут выполняться одновременно. Отсюда по индукции следует справедливость утверждения для всех уровней. Отсюда же следует, что $$T_{\mathcal {1}}$$ не может быть больше времени, задаваемого критическим путем.
Покажем теперь, что оптимальное расписание может быть составлено таким образом, чтобы критический путь был назначен одному процессору. Пусть процессор Ps - тот процессор, которому назначен $$M_i^1$$ первого уровня, лежащий на критическом пути. Спускаясь по уровням, этому процессору будем назначать модуль, лежащий на критическом пути. Так построенное расписание сохраняет свойство оптимальности, поскольку процессор Ps не простаивает, и ни какой другой процессор не может начать выполнять модули, лежащие на критическом пути, раньше процессора Ps. Заметьте, критический путь, вообще говоря, может быть не единственным.
Сложнее получить формулу для вычисления $$T_p$$. Проблема составления оптимального расписания в этих условиях относится к NP - полным проблемам, что означает, отсутствие алгоритма полиномиальной сложности, и для решения задачи необходимы переборные алгоритмы. Этим мы не будем заниматься.
Займемся тем, что покажем справедливость ранее полученных оценок (8) для $$T_p$$ в случае, когда время выполнения модулей различно и в графе зависимостей для каждого модуля задано время его работы:
$$\frac{T_1}{p}\le T_p\le \frac{T_1}{p}+T_{\mathcal {1}}$$Дадим вначале графическую интерпретацию. Задание нижней и верхней оценки для $$T_p(p)$$ означает, что эта функция ограничена двумя гиперболами. Функция убывающая. В начальной точке при p=1 по определению $$T_p(1) = T_1$$, так что функция находится в заданном коридоре. Это же справедливо и для конечных точек, для всех p, больших некоторого значения p*, при котором $$T_p = T_{\mathcal {1}}$$. Остается показать, что утверждение верно и для остальных значений $$1 < p < p*$$. Рис. 1.2 иллюстрирует поведение $$T_p$$.
(рис 1.2) Поведение функции Tp(p)
Приведем пример. Рассмотрим двух уровневую систему модулей, граф зависимостей которых показан на Рис. 1.1.
Нетрудно посчитать, что в этом случае:
$$T_1 = 30; T_{\mathcal {1}} = 13;$$Для случая двух процессоров для этого конкретного примера несложно задать оптимальное расписание. Для первого процессора последовательность выполняемых им модулей может быть следующей:
$$P1 = M_1^1, M_2^1, M_1^2, M_3^2\}$$Для второго процессора последовательность следующая:
$$P2 = \{M_3^1, M_4^1, M_2^2\}$$Время работы первого процессора равно 15, второго - 15. Следовательно, $$T_2$$ равно 15. Критический путь входит в расписание второго процессора. Подключение второго процессора в этой задаче позволяет вдвое уменьшить время выполнения в сравнении со случаем использования только одного процессора. Подключение третьего процессора, хотя и не столь эффективно, но позволит свести время выполнения до минимально возможного результата - $$T_{\mathcal {1}}$$. Добавление других процессоров не имеет смысла, поскольку не позволяет сократить время решения задачи.
После рассмотрения примера, перейдем к получению оценок.
Для $$T_p$$ справедлива оценка
$$T_p\ge \frac{T_1}{p}$$Докажем справедливость оценки. Пусть p процессоров выполняют работу согласно оптимальному расписанию, и ни один из процессоров не простаивает до окончания всей работы. Поскольку в результате все модули будут выполнены, и ни один модуль не будет выполняться дважды, то суммарное время работы всех процессоров равно $$T_1$$:
$$T_1=\sum^p_{i=1} T(P_i)$$Поскольку $$T_p$$ - это максимальное значение, затраченное одним из процессоров, на выполнение своей работы:
$$T_p=max_iT(P_i)$$Справедливость нижней оценки
$$T_p\ge \frac{T_1}{p}$$следует из общих свойств суммы компонентов. Максимальный компонент всегда больше или равен среднего арифметического значения суммы.
Если некоторые процессоры могут простаивать, то время $$T_p$$ может только увеличиваться, что гарантирует выполнения условия (16).
Равенство достигается в единственном случае, когда все компоненты суммы имеют одно и то же значение. Содержательно это означает, что все процессоры одновременно начинают свою работу и одновременно ее заканчивают. В этом случае общее время выполнения работы сокращается в p раз.
Пусть работу выполняют p процессоров. Составление расписания означает, что граф зависимостей разбивается на p непересекающихся подграфов. Все модули каждого из подграфов выполняются одним процессором. Подграф с максимальным временем выполнения для данного разбиения будем называть максимально нагруженным подграфом. Оптимальное расписание предполагает такое разбиение, при котором максимально нагруженный подграф выполняется за минимально возможное время. Итак, будем предполагать, что граф зависимостей G разбит на непересекающиеся подграфы $$G_i$$:
Не снижая общности, будем полагать, что максимально нагруженным подграфом является подграф $$G_1$$.
Для $$T_p$$ справедлива оценка
$$T_p\le \frac{T_1}{p}+T_{\mathcal {1}}$$Доказательство от противного. Покажем, что в этом случае разбиение не является оптимальным и может быть улучшено, что приведет к уменьшению времени $$T_p$$.
Итак, предположим, что
$$T_p=T(G_1)> \frac{\sum^p_{i=1}}{p}+T_{\mathcal {1}}$$Отсюда следует:
$$p \cdot T(G_1)> \sum^p_{i=1}T(G_I)+p \cdot T_{\mathcal {1}} \Rightarrow T(G_1)> \frac{\sum_{i=2…p}T(G_i)}{p-1}+\frac{p}{p-1}T_{\mathcal {1}}$$Пусть $$G_0$$ - минимально нагруженный подграф, тогда время его выполнения не больше среднего времени выполнения, так что имеем:
$$T(G_1)>T(G_0)+\frac{p}{p-1}T_{\mathcal {1}}$$Подграфу $$G_0$$ можно передать часть работ подграфа $$G_1$$, уменьшив суммарное время работы. Действительно, подграф $$G_1$$ можно представить в виде:
$$G_1= Path \bigcup G_1^'$$Здесь Path это часть пути или некоторый путь, начинающийся на первом уровне, который заведомо меньше критического пути. При передаче его подграфу $$G_0$$ время выполнения этого подграфа останется меньше времени выполнения подграфа $$G_1$$. Общее время выполнения работ при этом уменьшится. Следовательно, пришли к противоречию с утверждением об оптимальности расписания, что доказывает справедливость соотношения:
$$T_p=T(G_1)\le \frac{\sum^p_{i=1}T(G_I)}{p}+T_{\mathcal {1}}\le \frac{T_1}{p}+T_{\mathcal {1}}$$В заключение дадим некоторые практические рекомендации, следующие из полученных оценок. Выигрыш, который можно получить, используя дополнительные процессоры, зависит от разницы между общим временем выполнения всех модулей программы - $$T_1$$ и временем выполнения критического пути в графе зависимостей - $$T_{\mathcal {1}}$$.
Эта разница максимальна для крайнего случая, когда все модули могут выполняться независимо, и в графе зависимостей все модули находятся на одном первом уровне. Критический путь в этом случае состоит из одного модуля, требующего максимального времени своего выполнения. Так что $$T_1$$ - это время выполнения всех модулей, а $$T_{\mathcal {1}}$$ - это время выполнения одного модуля. Привлечение p процессоров может дать существенный эффект, уменьшая время выполнения практически до среднего времени выполнения одного модуля $$\frac{T_1}{p}$$.
Эта разница минимальна для другого крайнего случая - строго последовательной программы, когда N модулей программы расположены на N уровнях, и критический путь задает выполнение всех модулей. В этом случае $$T_1$$ и $$T_{\mathcal {1}}$$ совпадают и, как следствие, $$T_p$$ равно $$T_1$$ при любом числе процессоров, так что привлекать дополнительные процессоры в этом случае бессмысленно.
Для строго последовательной программы, когда i-й модуль зависит от модуля i-1, все три характеристики будут совпадать. Для строго последовательной программы дополнительные процессоры не позволяют уменьшить время выполнения программы в сравнении со временем выполнения этой же программы одним процессором. Так, например, задача о "Ханойской башне" на суперкомпьютере с сотнями тысяч процессоров будет решаться столь же долго, как и на компьютере с одним процессором. Это вытекает из сути задачи, - перенос следующего кольца требует завершение переноса предыдущего кольца, - параллельно эту работу выполнять нельзя.
В предыдущем разделе введены три параметра, характеризующие модель параллельных вычислений, - $$T_1$$, $$T_p$$, $$T_{\mathcal {1}}$$ - и заданы некоторые соотношения между ними. Продолжим эту тему и введем еще ряд характеристик. Все вводимые характеристики рассматриваются как функции параметра n, характеризующего сложность решаемой задачи. Обычно n понимается как объем входных данных.
Ускорение $$S_p(n)$$ определяют как отношение:
$$S_p(n)=\frac{T_1(n)}{T_p(n)}$$Важно правильно интерпретировать это отношение. Числитель и знаменатель, вообще говоря, рассчитываются для двух разных алгоритмов. Когда задача ориентирована на выполнение одним процессором, то можно построить алгоритм, оптимальный для последовательного выполнения. Использование нескольких процессоров, одновременно ведущих вычисления, требует другого алгоритма, предусматривающего распараллеливание. Построение хороших параллельных алгоритмов - это не простая задача. Чаще всего, хороший последовательный алгоритм не является таковым для параллельного выполнения.
Если у нас есть некоторая задача, и речь идет о том, какого ускорения можно добиться при распараллеливании, то в формуле (24) следует сравнивать время наилучшего последовательного алгоритма, для которого достаточно одного процессора, и время наилучшего параллельного алгоритма, который может использовать p имеющихся процессоров.
Какое ускорение является оптимальным? Ответ на этот вопрос дают оценки для $$T_p$$, полученные в предыдущем разделе. Из нижней оценки следует, что ускорение не может превосходить числа процессоров:
$$S_p(n) \le p$$Иногда эта оценка нарушается, и ускорение реально может быть больше p. В этом случае говорят о гиперускорении. Гиперускорение может возникнуть, если добавление процессоров влияет не только на вычисления. Например, появляется дополнительная память, возможно, другие устройства, способствующие ускорению решения задачи.
Максимальное ускорение для задачи задается соотношением:
$$S_{\mathcal {1}}(n)=\frac{T_1(n)}{T_{\mathcal {1}}(n)}$$Эффективность $$E_p(n)$$ определяют как отношение:
$$E_p(n)=\frac{S_p(n)}{p}$$Добиваться высокого ускорения следует, но не любой ценой. При оптимальном ускорении эффективность равна 1. Если же эффективность существенно ниже 1, то часто число процессоров целесообразно уменьшить, используя их более эффективно. Поясним ситуацию примером. Рассмотрим классическую задачу вычисления суммы элементов массива. Последовательный алгоритм, используя один процессор, вычисляет сумму за время порядка O(n). Схема вычисления показана на Рис. 1.3
(рис 1.3) Последовательное суммирование
Вычисление суммы можно распараллелить, построив пирамидальный алгоритм, который будет вычислять сумму за время O(log n), но для него на первом шаге потребуется n/2 процессоров, которые будут вычислять суммы пар элементов массива. На следующем шаге, число процессоров сократится вдвое, когда вычисляются суммы четверок. Для получения окончательного результата на последнем шаге потребуется всего один процессор. Схема вычисления показана на Рис. 1.4
(рис 1.4) Схема пирамидального параллельного алгоритма вычисления суммы элементов
Ускорение для этого алгоритма при вычислении суммы большого числа элементов прекрасное:
$$S_p(n)=\frac{n}{log_2n}$$При n, равном 220, например, ускорение более 215, составляет десятки тысяч раз. Но и процессоров требуется такого же порядка. Посчитаем эффективность для этого случая:
Для нашего примера эффективность будет равна 0,1. Возможно, более разумно в этой ситуации использовать конечное число процессоров. Например, имея 16 процессоров, можно разделить массив на 16 частей, для каждой из них процессоры вычислят частные суммы, а потом останется сложить эти частные суммы. В этом случае ускорение будет равно 16, но эффективность практически равна 1.
На проблему эффективности можно смотреть и с другой точки зрения. Пусть в нашем распоряжении есть многоядерный компьютер. Возникает естественный вопрос, насколько эффективно используются его возможности?
Введем в рассмотрение меру неиспользованных возможностей - упущенной выгоды - U(n), определив ее следующим образом:
Полагая, что оптимальное время, которое можно достичь, используя p процессоров, дается нижней оценкой для $$T_p$$, получим:
$$U_p(n)=p \frac{T_p(n)}{T_1}-1$$Если для компьютера с p ядрами время решения задачи оптимально и сокращается в p раз в сравнении с решением задачи на одноядерном компьютере, то наши потери равны нулю, возможности компьютера полностью используются. Если же задача решается за время $$T_1$$ - столь же долго, как на одноядерном компьютере, то потери пропорциональны числу неиспользованных ядер.
Ранее получены оценки для времени решения задачи при использовании p процессоров. При этом предполагалось, что задачу можно разделить на модули, задав граф зависимостей, определяющий возможный порядок вызова модулей. Представляет интерес рассмотрения случая, когда задачу можно разделить на две части, из которых одна часть требует последовательного выполнения, а вторая может быть полностью распараллелена. Законы Амдаля и Густавсона - Барсиса позволяют получить оценки для ускорения в зависимости от доли последовательных вычислений в общем времени решения задачи. Законы отличаются лишь тем, как определяется доля последовательных вычислений.
Пусть время решения задачи одним процессором можно представить как сумму времен решения последовательной части и части, допускающей распараллеливание:
$$T_1=T_{1succ}+T_{1par}$$Разделив обе части уравнения на $$T1$$, перейдем к долям времени:
$$ q= \frac{T_{1succ}}{T_1}; 1-q= \frac{T_{1par}}{T_1}$$Время решения задачи p процессорами также представим двумя частями:
$$T_p=T_{psucc}+T_{ppar}$$Последовательную долю нельзя уменьшить увеличением числа процессоров, поэтому $$T_{psucc} = T_{1succ}$$. Для параллельной части существует оценка, так что имеет место соотношение:
$$T_p \ge T_{1succ}+\frac {T_{1par}}{p}$$Переходя к ускорению, получим:
$$S_p =\frac {T_1}{T_p}\le \frac {T_1}{{T_{1succ}}+\frac {T_{1par}}{p}}}=\frac {1}{{\frac {T_{1succ}}{T_1}+\frac {T_{1par}}{T_1 \cdot p}}}=\frac {1}{q+\frac {1-q}{p}}\le \frac {1}{q}$$Соотношение (30) называется законом Амдаля. Оно говорит, что ускорение ограничено сверху величиной, зависящей от доли последовательных вычислений. Если, например, последовательные вычисления занимают 10% от общего времени вычисления, то за счет распараллеливания нельзя добиться более чем десятикратного ускорения времени работы, сколь много процессоров бы не привлекалось.
Пессимистический характер закона Амдаля может быть сглажен, если вспомнить, что все характеристики следует рассматривать, как функции от n - параметра характеризующего объем используемых данных. В этом случае закон Амдаля выглядит так:
На практике часто бывает, что последовательная часть задачи постоянна и не зависит от объема данных. В этом случае q(n) - убывающая функция, тогда для больших n можно добиться хорошего ускорения, не вступая в противоречие с законом Амдаля.
Запишем оптимальное время работы при использовании p процессоров в виде суммы времен двух частей - параллельной и последовательной:
$$T_{popt}= T_{popt\_succ}+T_{popt\_par}$$С учетом того, что последовательная часть выполняется p процессорами столь же долго, как одним процессором, а время параллельной части в оптимальном случае можно уменьшить в p раз, получим:
$$T_{popt}= T_{1succ}+\frac{T_{1par}}{p}$$Разделив обе части уравнения на $$T_{popt}$$, перейдем к долям времени:
$$g= \frac{T_{1succ}}{T_{popt}}; 1-g= \frac{T_{1par}}{p \cdot T_{popt}}$$Рассмотрим теперь отношение:
$$\frac{T_1}{T_{popt}}=\frac{T_{1succ}+T_{1par}}{T_{popt}}=g+p \cdot (1-g)$$Переходя к ускорению, получим
$$ S_p=\frac{T_1}{T_p}\le \frac{T_1}{T_{popt}}=g+p \cdot (1-g)$$Соотношение (32) выражает закон Густавсона-Барсиса, задавая оценку сверху для ускорения. Когда доля g стремится к единице, то и ускорения нет, оно ограничено единицей. Если же доля стремится к нулю, то ускорение, как и положено, ограничено числом используемых процессоров p.
Как и в законе Амдаля, характеристики следует рассматривать как функции параметра n:
Говоря о распараллеливании, различают два основных способа, позволяющих проводить параллельные вычисления, - распараллеливание по задачам и распараллеливание по данным.
Модель, рассмотренная выше, соответствовала случаю распараллеливания по задачам. В этой модели разные модули одной программы могли выполняться параллельно.
Рассмотрим теперь альтернативную ситуацию, когда выполняется распараллеливание по данным. В этом случае некоторое множество данных необходимо обработать одним модулем.
Пусть необходимо решить задачу D на некотором конечном множестве данных $$X = \{ x_1, x_2, …x_n\}$$. Зачастую, эффективный последовательный алгоритм решения этой задачи можно получить, если удается свести решение исходной задачи к решению k подзадач - $$D(X_i) ( i = 1, 2 …k)$$, где каждая подзадача означает решение исходной задачи D, но на подмножестве данных $$X_i$$. Наиболее эффективно, когда все подзадачи имеют один и тот же размер.
Справедлива простая, но крайне важная в теории алгоритмов
Если задачу D(X) можно свести к решению k подзадач одинаковой размерности и за линейное время из решений k подзадач можно получить общее решение исходной задачи, то временная сложность решения исходной задачи T(n) дается формулой:
Здесь с - некоторая константа.
Для простоты будем полагать, что $$n = k^m$$. Тогда с учетом сделанных предположений
$$T(n) = T(k^m) = k \cdot T( k^{m-1}) + c \cdot k^m = k \cdot (k \cdot T(k^{m-2}) + c \cdot k^{m-1}) + c \cdot k^m = k^2 \cdot T(k^{m-2}) + 2\cdot c \cdot k^m$$Продолжая разворачивать этот процесс, дойдем до времени T(1), которое можно считать без ограничения общности константой, равной c. Таким образом, получим:
Эффективный последовательный алгоритм предполагает рекурсивное определение. За счет сведения исходной задачи к решению нескольких задач меньшей размерности удается существенно снизить временную оценку сложности решения задачи в сравнении со случаем, когда задача решается для полного набора данных.
Классическим примером являются алгоритмы сортировки. В сортировке слиянием исходное множество разделяется на два подмножества практически одинаковой мощности (размер может отличаться на единицу). Слияние двух отсортированных подмножеств можно выполнить за линейное время. Поэтому временная сложность этой сортировки в соответствии с соотношением (35) задается формулой $$O(n \cdot log_2 n)$$. В то же время сложность таких простых алгоритмов сортировки как, например, пузырьковая сортировка задается соотношением $$O(n \cdot n)$$. При больших n, например при $$n = 2^20$$, время сортировки слиянием может быть в тысячи раз меньше времени пузырьковой сортировки.
Этот пример показывает, что и последовательные алгоритмы могут эффективно использовать распараллеливание по данным. А что могут дать в этой ситуации параллельные алгоритмы, использующие наличие k процессоров.
Пусть у нас есть компьютер, имеющий k ядер, и нужно решить задачу на множестве данных размерности $$k^m$$. Самое простое решение состоит в том, чтобы разбить исходное множество на k подмножеств одинаковой размерности $$k^{m-1}$$. Затем применять эффективный рекурсивный последовательный алгоритм, решая параллельно на всех ядрах исходную задачу для соответствующего подмножества. После этого за линейное время объединить полученные решения. Учитывая ранее полученные соотношения, временная сложность такого алгоритма дается соотношением:
Сравнивая соотношения (35) и (36), можно видеть, что за счет использования k ядер можно в k раз уменьшить сложность алгоритма. Заметьте, рассматриваемая версия алгоритма использует рекурсию только в последовательной версии, запускаемой на каждом ядре. Использование рекурсии в параллельных алгоритмах не всегда приводит к повышению эффективности.
В заключение первой главы кратко рассмотрим некоторые проблемы, возникающие при организации параллельных вычислений.
Когда несколько модулей одной и той же программы запускаются на разных процессорах, то возникает необходимость в синхронизации их действий.
Модулю А могут быть необходимы результаты работы модулей В и С, поэтому начать свое выполнение модуль А может лишь по завершении работы как модуля В, так и модуля С, которые могут выполняться параллельно, но не известно, какой из них первым закончит работу. В любом случае запуск модуля А на выполнение должен быть синхронизирован с окончанием работ модулей В и С.
При распараллеливании по данным один и тот же модуль F может быть запущен на k процессорах и параллельно выполняться, обрабатывая разные подмножества данных $$(X_1, X_2, …X_k)$$. Результаты работы k процессоров затем объединяются в процессе работы модуля G. Понятно, что запуск на выполнение модуля G должен быть синхронизирован с окончанием работы модуля F на всех параллельно работающих k процессорах.
Параллельные вычисления требуют тщательной синхронизации работы модулей программы, выполняемых разными процессорами.
Так называемая проблема "гонки данных" возникает для мультипроцессорных компьютеров с общей памятью. Поскольку процессоры работают параллельно, то в одни и те же моменты времени они могут получать доступ к одним и тем же данным, хранимым в общей памяти, как для чтения, так и для записи.
Если совместное чтение данных представляется возможным и допустимым, то одновременная запись двух разных значений в одну и ту же ячейку памяти не допустима. Запись всегда будет идти по очереди. Конкурирование процессоров за запись в одно и то же слово памяти и называется "гонкой данных". Интересно, что в этой гонке выигрывает не тот, кто пришел первый, а тот, кто пришел последний, поскольку именно его результаты будут сохранены в памяти. Это соответствует пословице: "хорошо смеется тот, кто смеется последним".
Чтобы справиться с проблемой "гонки данных", существуют разные механизмы закрытия памяти - одного из видов совместно используемого ресурса. Тот, кто выигрывает гонку и приходит первым, закрывает ресурс для доступа. Проигравшие гонку прерывают выполнение и становятся в очередь за обладание ресурсом. Обладатель ресурса спокойно выполняет свою работу, а по ее окончании открывает ресурс, с которым теперь начинает работать тот, кто первым стоит в очереди.
Гонка данных - это одна из самых серьезных проблем параллельного программирования, поскольку при некорректно организованной блокировке ресурса программа может завершаться с некорректными результатами без возникновения исключительных ситуаций.
Плохо, когда в процессе работы программы происходит отказ и нужные нам результаты не могут быть получены. Но еще хуже, когда программа завершается, выдает результаты, но эти результаты ошибочны. Плохо, когда студент на экзамене говорит: "не знаю", но хуже, когда он говорит "глупости".
Чтобы справиться с гонкой данных, приходится включать блокировку, закрывая ресурс для других конкурентов, которые должны прервать свою работу и томиться в очереди, ожидая момента освобождения ресурса. Блокировка - полезный механизм, обойтись без которого в ряде ситуаций просто невозможно. Но блокировка - это и опасный механизм, порождающий прерывание работы всей программы, когда возникает ситуация, называемая тупиком, клинчем или смертельным объятием.
Рассмотрим простейшую ситуацию, приводящую к возникновению клинча. Пусть есть два конкурента А и В, претендующие на два ресурса f и g. Пусть гонку за ресурс f выиграл А и соответственно закрыл этот ресурс для В. Гонку за ресурс g выиграл В и закрыл ресурс для А. Но А, чтобы закончить свою работу нужен ресурс g, поэтому он стал в очередь, ожидая освобождения ресурса g. Симметрично, В томится в очереди, ожидая освобождения ресурса f. Возникает ситуация клинча, когда ни А, ни В не могут продолжить свою работу.
В боксе, когда два боксера входят в клинч, сцепившись друг с другом, нужен судья, дающий команду "break", чтобы боксеры могли разойтись и продолжить бой. Так и в параллельных вычислениях при возникновении клинча, только внешнее воздействие может разрешить ситуацию.
Для мультикомпьютерных комплексов, где каждый компьютер комплекса имеет собственную память, проблемы гонки данных и клинча не столь актуальны. Здесь возникает своя не менее серьезная проблема. Хотя каждый компьютер комплекса работает со своими данными, но все параллельно работающие компьютеры решают одну и ту же задачу, поэтому без обмена информацией обойтись невозможно. В процессе работы компьютеры должны обмениваться данными, посылая друг другу сообщения. В кластерах (типичном виде мультикомпьютерного комплекса) компьютеры объединены высокоскоростными линиями связи. Тем не менее, передача данных является медленной операцией, и время на передачу данных может "съесть" весь выигрыш, полученный за счет распараллеливания вычислений. Поэтому при анализе эффективности работы программы, работающей на кластере или другом мультикомпьютерном комплексе, где параллельно работающие процессоры обмениваются сообщениями по линиям связи, не имея доступа к общей памяти, важную роль играют операции п осылки и получения сообщений (send - receive, map - reduce).
Пусть на кластере, содержащем k компьютеров, нужно решить некоторую задачу D на множестве данных X.
Алгоритм решения может быть задан следующей схемой:
Map(X); //Исходное множество X разбивается на k подмножеств, каждое из которых
//пересылается на соответствующий компьютер кластера.
Parallel_D(Xi); //Задача D параллельно запускается на каждом компьютере,
//обрабатывая подмножество данных Xi, и получая результат Yi.
Reduce(Y); //Результаты работы каждого компьютера Yi объединяются, создавая общее
//решение Y.
Для последовательного алгоритма время решения исходной задачи может быть записано в виде:
$$T_{sec}(D) = T(D(X(n)))$$Для параллельного алгоритма время решения исходной задачи может быть записано в виде:
$$T_{par}(D) = T(Map(n, k)) + T(D(X(n/k))) + T(Reduce(n, k))$$Как правило, Map и Reduce имеют линейную сложность. Полагая, что архитектура кластера позволяет одновременно пересылать данные всем компьютерам кластера, можно записать следующие соотношения для времени выполнения этих операций:
Аналогично
$$T(Reduce(n, k)) = c_r \cdot n/k$$Какой же алгоритм предпочтительнее по времени выполнения - последовательный или параллельный? В этих условиях все зависит от сложности задачи D. Если это простая задача с линейной временной сложностью
то вероятнее всего последовательный алгоритм будет эффективнее, поскольку обычно константы $$c_m$$ и $$c_r$$ много больше константы $$c_d$$. Так что будет выполняться соотношение:
$$c_d \cdot n < (c_m + c_r + c_d) \cdot n/k$$Для этого достаточно выполнения условия:
$$ c_d < (c_m + c_r )/k$$Для сложной в вычислительном отношении задачи D параллельный алгоритм, скорее всего, окажется эффективнее. Так, для задачи D, имеющей кубическую сложность, выполнение условия:
гарантирует эффективность параллельного алгоритма.
На этом завершим первую главу. В последующих главах появятся конкретные примеры, иллюстрирующие положения, рассмотренные в этой главе.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.