Параллельные вычисления
 Скачать 1.75 Mb.
|
|
я рные ЭВМ Т-340А и К-340А имели бы- стродействие 1,2 × 10 6 двойных (2,4 × 10 6 обычных) операций в секунду (в начале 60-х г.г. типов о е быстродействие ЭВМ измерялось десятками или сотнями тысяч операций в секунду). В начале 70-х г.г. работами в области модулярной арифметики заинтересова- лись западные разработчики компьютерной техники, но все предложения о легальной зак у пке результатов разработки были пресечен ы глубококомпетентными органами; с тех пор модулярной арифметикой в нашей стране занимаются только отдельные энту- зиасты-теоретики. Параллельные системы априори предназначены для решения задач боль- шой размерности, поэтому среди прочих источников погрешностей заметной становится погрешность округления. Известно, что (при разумных допущени- ях) среднеквадратичное значение погрешности округления ) ( e O β = σ , где β - значение младшего разряда мантиссы числа (для ‘плавающих’ чисел оди- нарной точности при 3-х байтовой мантиссе β =2 -24 ), e – число арифметико- логических операций в задаче [7]. Для компьютера с производительностью всего 1 Гфлопс за час работы величина е достигает 4 × 10 12 , а σ будет иметь порядок O(2 -24 × 10 6 ) ≈ O(10 -6 × 2 -4 × 10 6 )=O(2 -4 ) ≈ 6%; такая погрешность недо- пустима, поэтому для параллельных вычислений практически всегда исполь- зуется двойная точность. Эмпирически замечено, что до 90% обращений в ОП производится в огра- ниченную область адресов. Эта область называется рабочим множеством, которое медленно перемещается в памяти по мере выполнения программы. Для рабочего множества целесообразно реализовать промежуточную (ло- кальную для данного АЛУ и очень быстродействующую) память небольшого размера (кэш), использование кэш-памяти очень эффективно для ускорения обращения к ОП. Во многих случаях рациональные преобразования про- - 24 - граммы (напр., циклических участков) позволяют многократно (иногда в де- сятки раз!) повысить быстродействие даже последовательной программы за счет ‘оседания’ в кэше часто используемых переменных. 1.3 Понятие параллельного процесса и гранулы распараллеливания Наиболее общая схема выполнения последовательных и параллельных вычислений приведена на рис.3 (моменты времени S и E – начало и конец задания соответственно). Рисунок 3 — Диаграммы выполнения процессов при последовательном вычислении - а), при близком к идеальному распараллеливании - б) и в общем случае распа- раллеливания - в) Процессом называют определенные последовательности команд, наравне с другими процессами претендующие для своего выполнения на использова- ние процессора; команды (инструкции) внутри процесса выполняются после- довательно [2], внутренний (напр., конвейерный) параллелизм при этом не учитывают. На рис.3 тонкими линиями показаны действия по созданию процессов и обмена данными между ними, толстыми – непосредственно исполнение про- цессов (ось абсцисс - время). В случае последовательных вычислений созда- ется единственный процесс (рис.3a), осуществляющий необходимые дейст- вия; при параллельном выполнении алгоритма необходимы несколько (ино- гда десятки/сотни/тысячи) процессов (параллельных ветвей задания). В иде- альном случае (близкое к идеальному распараллеливание) все процессы соз- даются одновременно и одновременно завершаются (рис.3б), в общем случае диаграмма процессов значительно сложнее и представляет собой некоторый граф (рис.3в). Характерная длина последовательно выполняющейся группы команд в каждом из параллельных процессов называется размером гранулы (зерна). В любом случае целесообразно стремиться к ‘крупнозернистости’ (идеал – диа- грамма 3б). Обычно размер зерна (гранулы) составляет десятки-сотни тысяч машинных операций (что на порядки превышает типичный размер оператора - 25 - языков Fortran или C/C++, [3]). В зависимости от размеров гранул говорят о мелкозернистом и крупнозернистом параллелизме (fine-grained parallelism и coarse-grained parallelism). На размер гранулы влияет и удобство программи- рования – в виде гранулы часто оформляют некий логически законченный фрагмент программы. Целесообразно стремиться к равномерной загрузке процессоров (как по количеству вычислительных операций, так и по загрузке оперативной памяти) Разработка параллельных программ является непростой задачей в связи с трудностью выявления параллелизма (обычно скрытого) в программе (т.е. выявления частей алгоритма, могущих выполняться независимо друг от дру- га). Например, для задачи вычислений фрагмента программы (ZnN – вычисленные значения, OpN – операнды, FunN – вычислительные процедуры, DN – арифметико-логические выражения): Zn1 ← Fun1(Op1,Op2) D1 Fun2(Op3) D2 Fun3(Op3); // operator 1 (2) Zn2 ← Fun4(Op4,Zn1) D3 Fun5(Op3); // operator 2 выявить параллелизм 'вручную' неcложно. Даже на первый взгляд видно, что вычисление оператора Zn2 невозможно без предварительного вычисле- ния Zn1 (при этом говорят, что оператор ‘ Zn1 зависит от Zn2’, т.е. существует зависимость по данным; подробнее см. подраздел 3.2). В простейшем случае возможно распределить по процессам вычисления Fun1 ÷ Fun3 в соответствие со схемой рис.3б и далее ‘собрать’ вычисленные значения для определения Zn1, в дальнейшем подобным образом поступить с вычислением Zn2 (что вычисление Fun5 можно совместить с вычислением Fun1 ÷ Fun3 ); в этом гранулами параллелизма являются вычисления Fun1 ÷ Fun5 . Заметим, что автоматизация (столь легко проделанная ‘вручную’) выявления параллелизма в алгоритмах непроста и в полном объеме вряд ли может быть решена в ближайшее время. В то же время за десятилетия экс- плуатации вычислительной техники разработано такое количество (тщатель- но отлаженных и оптимизированных) последовательных алгоритмов, что не может быть и речи об их ручном распараллеливании. Построим простейшую математическую модель для оценки возможного повышения производительности при распараллеливании вычислений c уче- том времени обмена данными. Пусть t O - характерное время обмена (опера- ций пересылки данных между процессами), t З - время выполнения последо- вательности команд, составляющих гранулу, n – число гранул. Примем (уп- рощенно), что при раcпараллеливании каждая гранула выполняется на от- дельном процессоре, время вычисления последовательности команд каждой гранулы одинаково, каждый процесс требует при функционировании не бо- лее двух обменов (как показано на рис.3б). Тогда последовательный алго- ритм выполнится (в среднем) за время n t T з посл × = , - 26 - а время выполнения параллельного алгоритма t t T o з парр × + = 2 Выигрыш в производительности параллельного алгоритма по сравнению с последовательным (коэффициент ускорения вычислений) в этом случае: t t t T T o з з парр посл n k × + × = = 2 . (3) Расчет количества процессоров, необходимых для получения хотя бы k=1 в функции t t з o дан в табл.1 (значения n не всегда округлены до целого). Таблица 1 — Минимальное расчетное количество процессоров n k 1 = , необходимых для гарантированного ускорения при параллель- ном выполнении (расчет по выражению (3)) t t з o / 0,125 0,25 0,5 1,0 2,0 5,0 7,5 10,0 n k 1 = 1,25 1,5 2 3 5 11 15 21 1 < t t з o (время обмена дан- ными меньше времени вы- полнения гранулы) 1 > t t з o (время обмена данными превышает время выполнения грану- лы) Как видно из табл.1, только при малости времени обмена (по сравнению с временем выполнения процесса) эффективность распараллеливания высока (для достижения k=1 требуется мало процессов), при превышении времени обмена времени выполнения процесса достижение хотя бы k=1 требует большого количества процессов. Таблица 2 — Ускорение вычислений k в зависимости от числа процес- сов n и величины t t з o (расчет по (3)) n 2 3 5 7 10 15 20 t t з o / =0,1 1,67 2,5 4,17 5,83 8,33 12,5 16,7 t t з o / =1 0,667 1,0 1,67 2,33 3,33 5,0 6,67 t t з o / =10 0,095 0,143 0,238 0,333 0,476 0,714 0,952 - 27 - Как и следовало ожидать (табл.2), снижение отношения t t з o / в высшей степени благоприятно для повышения ускорения при параллелизации вычис- лений. Т.о. даже простейшая модель (не учитывающая реальной диаграммы рас- параллеливания, задержек на старт процессов, зависимость времени обменов от размера сообщения и множества других параметров) параллельных вы- числений позволила выявить важное обстоятельство – время обмена данны- ми должно быть как можно меньше времени выполнения последовательности команд, образующих гранулу. Если в (2) качестве Fun1 ÷ Fun5 выступают функции типа sin(), cos(), atan(), log(), pow() , характерное время t З выполнения которых единицы микросе- кунд, время t O обмена данными должно составлять десятые/сотые доли мксек (столь ‘быстрых’ технологий сетевого межпроцессорного обмена не существует); для гранул большего размера допустимо время обменов в де- сятки (в некоторых случаях – даже сотни) мксек. Для реальных задач (тради- ционно) характерный размер зерна распараллеливания на несколько поряд- ков превышает характерный размер оператора традиционного языка про- граммирования (C/C++ или Fortran). Соотношение t t з o определяется в значительной степени структурой и ап- паратными возможностями вычислительного комплекса (архитектурой мно- гопроцессорной системы), при этом рациональный размер зерна распаралле- ливания также зависит от используемой архитектуры. 1.4 Взаимодействие параллельных процессов, синхронизация процессов Выполнение команд программы образует вычислительный процесс, в слу- чае выполнения нескольких программ на общей или разделяемой памяти и обмене этих программ сообщениями принято говорить о системе совместно протекающих взаимодействующих процессов [4]. Порождение и уничтожение процессов UNIX-подобных операционных системах выполняются операторами (системными вызовами) fork, exec и exit Системный вызов fork при выполнении текущим (родительским, parent process) процессом запрашивает ядро операционной системы на создание дочернего (child process) процесса, являющегося почти (за исключение зна- чения идентификатора процесса pid ) точной копией текущего. Оба процесса при успешном выполнении fork выполняются одновременно с оператора, не- посредственно следующего после вызова fork. Вызовы операторов семейства exec загружают исполняемую программу на место вызывающей, произвед- ший этот вызов ( pid процесса и файловые дескрипторы сохраняют свои зна- чения для замещающего процесса), exec -вызовы позволяют передавать поро- жденному процессу параметры. Создание двух разных процессов реализуется - 28 - последовательностью вызовов fork родительским процессом (создаются два процесса с одинаковыми кодами и данными) и exec дочерним процессом (при этом он завершается и замещается ‘новым’ процессом). Корректность рабо- ты с процессами требует вызова родительским процессом wait после fork (да- бы приостановить работу до момента завершения дочернего процесс и заме- щения его ‘новым’). Системный вызов exit завершает выполнение процесса с возвратом задан- ного значения целочисленного статуса завершения (exit status), процесс- родитель имеет возможность анализировать эту величину (при условии вы- полнения им wait ). Параллелизм часто описывается в терминах макрооператоров FORK и JOIN , в параллельных языках запуск параллельных ветвей осуществляется с помо- щью оператора FORK M1, M2 , ...ML , где M1, M2, ...ML - имена независимых ветвей; каждая ветвь заканчивается оператором JOIN (R,K) , исполнение кото- рого вызывает вычитание единицы из ячейки памяти R . Предварительно в R записывается равное количеству ветвей число, при последнем срабатывании оператора JOIN (т.е. когда все ветви выполнены) в R оказывается нуль и управление передается оператору K (в некоторых случаях в JOIN описывается подмножество ветвей, при выполнении которого срабатывает этот оператор). В последовательных языках аналогов операторам FORK и JOIN не может быть и ветви выполняются последовательно друг за другом. В терминах FORK/JOIN итерационная параллельная программа может иметь следующий вид (функции F1 , F2 и F3 из-за различной алгоритмиче- ской реализации должны вычисляться отдельными программными сегмента- ми, которые логично оформить в виде ветвей параллельной программы), [7]: X1=X10; X2=X20; X3=X30; R=3; // инициализация переменных LL FORK M1, M2, M3 // запустить параллельно M1,M2,M3 M1 Z1 = F1 (X1, X2, X3) // вычислить Z1=F1(X1, X2, X3) JOIN (R, KK) // R=R-1 M2 Z2 = F2 (X1, X2, X3) // вычислить Z2=F2(X1, X2, X3) JOIN (R, KK) // R=R-1 M3 Z3 = F3 (X1, X2, X3) // вычислить Z3=F3(X1, X2, X3) JOIN (R, KK) // R=R-1 KK IF (ABS (Z1-X1) < ε ) AND (ABS (Z2-X2) < ε ) AND (ABS (Z3-X3) < ε ) // если абсолютная точность ε // вычислений достигнута… THEN вывод результатов; STOP // то вывести данные и закончить ELSE X1=Z1; X2=Z2; X3=Z3; GO TO LL // иначе переопределить X1,X2,X3 // и повторить цикл вычислений Для многопроцессорных вычислительных систем особое значение имеет обеспечение синхронизации процессов (вышеописанный оператор JOIN со- - 29 - вместно с ячейкой R как раз и осуществляет такую синхронизацию - состоя- ние R=0 свидетельствует об окончании процессов разной длительности). На- пример, момент времени наступления обмена данными между процессорами априори никак не согласован и не может быть определен точно (т.к. зависит от множества труднооцениваемых параметров функционирования МВС), при этом для обеспечения полноценного рандеву (встречи для обмена информа- цией) просто необходимо применять синхронизацию. В слабосвязанных МВС вообще нельзя надеяться на абсолютную синхронизацию машинных часов отдельных процессоров, можно говорить только об измерении проме- жутков времени во временной системе каждого процессора. Синхронизация является действенным способом предотвращения ситуаций дедлока (deadlock, клинч, тупик) – ситуации, когда каждый из взаимодейст- вующих процессов получил в распоряжение часть необходимых ему (разде- ляемых с другими процессами) ресурсов, но ни ему ни иным процессам это- го количества ресурсов недостаточно для завершения обработки (и после- дующего освобождения ресурсов), [4]. Одним из известных методов синхронизации является использование се- мафоров (E.Дейкстра, 1965). Семафор представляет собой доступный ис- полняющимся процессам целочисленный объект, для которого определены следующие элементарные (атомарные, неделимые) операции: • Инициализация семафора, в результате которой семафору присваивается неотрицательное значение. • Операция типа P (от датского слова proberen - проверять), уменьшающая значение семафора. Если значение семафора опускается ниже нулевой отметки, выполняющий операцию процесс приостанавливает свою рабо- ту. • Операция типа V (от verhogen - увеличивать), увеличивающая значение семафора. Если значение семафора в результате операции становится больше или равно 0, один из процессов, приостановленных во время вы- полнения операции P, выходит из состояния приостанова. • Условная операция типа P (сокращенно CP, conditional P), уменьшающая значение семафора и возвращающая логическое значение ‘истина’ в том случае, когда значение семафора остается положительным. Если в резуль- тате операции значение семафора должно стать отрицательным или нуле- вым, никаких действий над ним не производится и операция возвращает логическое значение ‘ложь’. В системах параллельного программирования используют существенно более высокоуровневые приемы синхронизации. В технологии параллельного программирования MPI (см. раздел 4.2) применена схема синхронизации об- мена информацией между процессами, основанная на использовании прими- - 30 - тивов send/receive (послать/принять сообщение). При этом send может быть вызван в любой момент, а receive задерживает выполнение программы до момента реального поступления сообщения (т.н. блокирующие функции). В MPI определен оператор Barrier , явным образом блокирующий выполнение данного процесса до момента, когда все (из заданного множества) процессы не вызовут Barrier . Функция синхронизации в T-системе (раздел 4.3.2) под- держивается механизмом неготовых переменных, в системе программирова- ния Linda (раздел 4.2) при отсутствии явной поддержки синхронизация про- цессов несложно моделируется язык |