Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В.. Программирование для многопроцессорных систем в стандарте MPI -. Организация вычислений в многопроцессорных системах
 Скачать 1.61 Mb.
|
|
Глава 12. ЭФФЕКТИВНОСТЬ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ 12.1. АНАЛИТИЧЕСКАЯ ОЦЕНКА ЭФФЕКТИВНОСТИ ВЫЧИСЛЕНИЙ Время выполнения параллельной программы зависит от многих факторов: от параллелизма математического алгоритма, от его про- граммного представления, от возможностей и качества реализации языка параллельного программирования, количества процессоров, объема памяти, размещения данных по процессорам, быстродействия коммуникационного оборудования и от множества других обстоя- тельств. При некоторых упрощениях ускорение вычислений характе- ризуется сетевым законом Амдала (глава 1): C n a a c R + − + = 1 1 , (12.1) где Т А С С t W c t c W С ⋅ = ⋅ ⋅ = , (12.2) есть коэффициент сетевой деградации. При этом C А =Wс/W определя- ет алгоритмическую составляющую коэффициента деградации, обу- словленную свойствами алгоритма, а C Т – техническую составляю- щую, которая зависит от соотношения технического быстродействия процессора и аппаратуры сети. Таким образом, для повышения скоро- 237 сти вычислений следует воздействовать на обе составляющие коэф- фициента деградации. Как правило, обе составляющие коэффициента деградации С известны заранее для многих алгоритмов[14] и аппарат- ных средств, или их можно при некоторых упрощениях относительно легко вычислить. В качестве примера рассмотрим сетевую эффектив- ность вычислений умножения матрицы на вектор и умножение мат- рицы на матрицу [4]. Умножение матрицы на вектор. Предположим, что матрица А квадратная, размера m m ∗ . Тогда для каждого элемента результи- рующего вектора С , получаемого от перемножения матрицы А на век- тор b , нужно выполнить m умножений, и m- 1 сложений. Имеется m элементов вектора C , поэтому общее количество операций с плаваю- щей точкой будет m * (m + (m – 1 )) = 2 m 2 -m. (12.3) Для простоты предполагаем, что на сложение и умножение затра- чивается одинаковое количество времени, равное T выч . Далее предпо- лагаем, что полное время вычисления в основном зависит от операций с плавающей точкой. Таким образом, грубая оценка времени на вы- числения равна (2m 2 -m) * T выч . Оценим затраты на коммуникацию. Не будем учитывать затраты на посылку b каждому подчиненному процессу, предположим, что он прибывает туда другим способом (например, может быть там вычис- лен). Тогда количество чисел с плавающей запятой, которые должны быть переданы, равно m (чтобы послать строку матрицы A ), + 1 (что- бы послать ответ назад) для каждого из m элементов C , что дает в ре- зультате m х (m + 1 ) =m 2 + m. (12.4) Если предположить, что время, требуемое на сообщение числа с плавающей запятой равняется T КОМ , то полное время связи примерно равно (m 2 + m) * Т КОМ . Поэтому отношение коммуникации к вычисле- нию равно ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ × ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − + = × = выч ком T A Т T m 2 2m m 2 m C C C (12.5) Предположим, что: 1. Для больших m (именно для таких задач нужны параллельные ЭВМ) можно пренебречь m по сравнению с m 2 . 238 2. В качестве коммуникационной сети используется сеть Fast Ethernet с пропускной способность V = 10 Мбайт/сек. 3. Объединенное время t ОП плавающей операции (умножение, сложе- ние, 2 обращения в память) требует 20 нс при частоте процессора 500 Мгц. 4. Длина слова с плавающей запятой может составлять 10 байтов. Тогда согласно выражению (12.5) получаем: 25 10 20 10 10 2 1 10 2 1 2 1 9 7 = ∗ ∗ ∗ = ∗ ∗ = ∗ = ∗ = − оп выч ком Т А t V T T C C C (12.6) Следовательно, даже при идеальном распараллеливании ( а =0) 25 1 1 + = /n R c , (12.7) матрично-векторное умножение всегда будет выполняться в много- процессорной системе с замедлением по отношению к однопроцес- сорному варианту. Это же верно и для самопланирующего алгоритма умножения матриц, так как здесь основной операцией также является пересылка одной строки и умножение этой строки на один столбец. Необходимы другие алгоритмы матрично-векторного умножения, обеспечивающие ускорение. Умножение матрицы на матрицу. Для матрично-матричного ум- ножения вектор b становится матрицей B , которая копируется в каж- дом процессе, и после вычислений каждый процесс посылает обратно целую строку конечной матрицы С Пусть A и B – квадратные матрицы. Тогда число операций для ка- ждого элемента матрицы С будет (как и прежде) равно m умножений и m- 1 сложений, но теперь вычисляется m 2 элементов, а не m . Поэтому число операций с плавающей запятой равно m 2 × ( 2 m- 1 ) = 2 m 3 - m 2 . (12.8) Количество чисел с плавающей запятой, передаваемых каждой строке, равно m (чтобы послать строку матрицы A плюс m , чтобы послать строку матрицы С назад), и имеются m строк, отсюда ответом являет- ся m * 2 m . Тогда отношение коммуникации к вычислению можно вы- числить по формуле 12.9, результат стремится к 1 /m при увеличении m . Поэтому для этой задачи мы должны ожидать, что коммуникаци- онные перерасходы будут играть все меньшую роль при увеличении размера задачи. 239 Тогда с помощью рассуждений, которые проводились выше для векторно-матричного умножения, учитывая формулу (12.9) и необхо- димость посылки равного объема данных туда и обратно, получаем: 9 10 20 10 1 10 1 − ∗ ∗ ∗ = ∗ ∗ = ∗ = V m t V m С С С оп Т А (12.10) Поскольку для коммуникационной системы SCI (Scalable Coherent Interface) V = 80 Мбайт/сек, то для сетей Fast Ethernet (FE) и SCI полу- чаем: m n R FE c 100 1 + = 1 , (12.11) m n R SCI c 5 12 1 1 + = . (12.12) Ниже для операции умножения матрицы на матрицу приводятся два графика (рис. 12.1, 12.2), построенные по выражениям (12.11) и (12.12). Справа на графиках указано число процессоров в порядке расположения графиков (для n = 32 график и значение n расположены вверху). Приведенные графики позволяют сделать следующие выводы: Ускорение существенно зависит от объема вычислений, вызванного однократной передачей данных. Согласно (12.7) для самоплани- рующего алгоритма это соотношение неудовлетворительное, по- этому при любом числе процессоров происходит замедление, а не ускорение вычислений. В алгоритме с дублированием матрицы В объем вычислений при однократной передаче данных велик и по- вышается при увеличении размера матриц. Это видно из обоих графиков. Сравнение графиков для Fast Ethernet и SCI также показывает силь- ную зависимость ускорения от пропускной способности коммуни- кационной сети, причем для SCI высокое ускорение достигается при меньших размерах матриц. Реальные данные по производительности 36-процессорного кластера SCI и 40-процессорного кластера SKY, установленных в НИВЦ МГУ, приведены в [27]. ) 9 12 ( ) T T ( ) m m m ( выч ком 2 3 2 × − 2 2 240 Рис. 12.1. Зависимость ускорения от размера матриц и числа процессоров для Fast Ethernet Рис. 12.2. Зависимость ускорения от размера матриц и числа процессоров SCI 12.2. СПОСОБЫ ИЗМЕРЕНИЯ ЭФФЕКТИВНОСТИ ВЫЧИСЛЕНИЙ Последовательные программы тестируют, чтобы убедиться, дают ли они правильный результат. Для параллельных программ этого не- достаточно – для них необходимо определять ускорение, а следова- тельно, необходимо измерять время выполнения параллельной про- Ускорение для SCI 0 5 10 15 20 25 30 35 1 2 3 4 5 6 7 8 Размер матрицы m*1000 Ус коре ние 32 24 16 8 4 Ускорения для сети Fast Ethernet 0 5 10 15 20 25 1 2 3 4 5 6 7 8 Размер матрицы m*1000 Ус ко ре н и е 32 24 16 8 4 241 граммы. MPI имеет простые функции для измерения времени выпол- нения программы или ее частей. Функция MPI_Wtime возвращает число с плавающей запятой, ко- торое является текущим отсчетом времени в секундах. Следовательно, чтобы узнать время выполнения отрезка программы, нужно выпол- нить MPI_Wtime в начале и в конце отрезка, а затем вычесть отсчеты. Для получения отсчетов используются таймеры высокого разрешения. Если их нет в конкретном процессоре, то и измерения невозможны. Программа для вычисления значения π для языка Си, использующая функцию MPI_Wtime, представлена в параграфе 1.5. Функция MPI_Wtick не имеет никаких аргументов. Она возвра- щает число с плавающей точкой, которое указывает время между двумя последовательными тактами (период) тактового генератора. В MPI используются и более мощные средства измерения и анали- за эффективности параллельных вычислений. Они связаны с создани- ем логфайлов, в которых регистрируются заранее заданные пользова- телем события. Затем производится анализ и визуализация результа- тов регистрации. Все эти средства реализованы в основном в библио- теке MPE и представлены в параграфах 2.3 и 2.4 12.3. ИНТЕРФЕЙС ПРОФИЛИРОВАНИЯ Профилем некоторого процесса или объекта называют совокуп- ность его основных параметров. Профилирование – это процесс сбора этих параметров. В главе 2 и предыдущем параграфе были представ- лены некоторые фиксированные для MPICH и MPE методы профили- рования. Однако получаемый с помощью этих методов набор резуль- татов не всегда удовлетворяет пользователей. Поэтому разработчики MPI предоставили непосредственно пользователю вариант профили- рующего механизма, с помощью которого он сам сможет запрограм- мировать сбор любой нужной ему информации. Чтобы обеспечить это, реализация MPI должна: 1. Обеспечить механизм, с помощью которого ко всем определенным в MPI функциям можно обращаться по смещенному имени. Таким образом все функции MPI, которые начинаются с префиксом “MPI_“, должны быть также доступны с префиксом “PMPI_”. 2. Гарантировать, что не измененные функции также можно включать в исполнительный файл без конфликтов в отношении имен. 3. Обеспечивать подпрограмму MPI_PCONTROL холостой коман- дой. 242 Если реализация MPI отвечает вышеупомянутым требованиям, система профилирования в состоянии перехватить все запросы MPI, сделанные в соответствии с программой пользователя. Затем можно собрать любую требуемую информацию перед обращением к основ- ной реализации MPI (по ее имени, смещенному по отношению к входной точке) для достижения желаемого результата. Программа пользователя должна иметь возможность управлять профилированием во время своего исполнения. Обычно это необхо- димо для достижения следующих целей: для активизации профилиро- вания и его прекращения в зависимости от состояния вычислений; для очистки буферов трассировки в некритических точках вычисления и для добавления пользовательских событий в файл трассировки. Эти требования удовлетворяются при использовании функции MPI_PCONTROL MPI_PCONTROL (level, ...) IN level уровень профилирования int MPI_Pcontrol(const int level, ...) MPI_PCONTROL(LEVEL) INTEGER LEVEL, ... void Pcontrol(const int level, ...) MPI библиотеки непосредственно не используют эту подпрограм- му, они просто возвращаются немедленно к коду пользователя. Одна- ко возможность обращения к этой процедуре позволяет пользователю явно вызвать блок профилирования. Поскольку MPI не контролирует реализацию профилирующего кода, нельзя точно определить семантику, которая будет обеспечивать вызовы MPI_PCONTROL. Эта неопределенность распространяется на число аргументов функции и на их тип. Однако чтобы обеспечить некоторый уровень переносимости кода пользователя относительно различных библиотек профилирования, необходимо, чтобы определенные значения уровня имели следующий смысл: • level==0 Профилирование не используется. • level==1 Профилирование установлено для нормального по умол- чанию уровня детализации. 243 • level==2 Буфера профилирования очищены (в некоторых системах профилирования это может быть холостая команда). • Все другие значения level имеют эффекты, определенные библио- текой профилирования и дополнительными аргументами. Также требуется, чтобы после выполнения MPI_INIT по умолча- ниюбыло установлено профилирование (как если бы была выполнена операция MPI_PCONTROL с аргументом 1). Это позволяет пользо- вателю связаться с библиотекой профилирования и получить резуль- тат профилирования без модификации их исходного текста. Рассмотрим пример автоматического создания логфайлов для из- мерения времени выполнения всех операций MPI_ Bcast в программе вычисления числа π (параграф 2.3). Int MPI_Bcast(void*buf, int count, MPI_Datatype, int root, MPI_Comm comm) { int result; MPE_log_event (S_BCAST_EVENT, Bcast_ncalls, (char*)0); result = PMPI_Bcast(buf, count, datatype, root, comm); MPE_Log_event(E_BCAST_EVENT, Bcast_ncalls, (char*)0); return result; } Идея состоит в том, чтобы выполнить перехват вызовов на этапе компановки , а не на этапе компиляции. Стандарт MPI требует, чтобы каждая процедура MPI могла быть вызвана по альтернативному име- ни. В частности, каждая процедура вида MPI_xxx должна также вызы- ваться по имени xxx. Более того, пользователю должно быть позволе- но использовать свою собственную версию MPI_xxx. Эта схема позволяет пользователю написать некоторое число обо- лочек для процедур MPI и выполнить некоторые действия внутри этих оболочек. Чтобы вызвать реальную процедуру MPI, следует обозна- чить ее префиксом РMPI_. Необходимо только гарантировать, что эта версия MPI_Bcast является единственной, которая используется ком- пановщиком для обращения к ней из прикладного кода. Эта процеду- ра вызывает PMPI_Bcast, чтобы выполнить нормальную работу. По- следовательность библиотек, используемых компановщиком, показа- на на рис.12.3. Механизм профилирования MPI позволил создать ряд библиотек, предназначенных для анализа эффективности вычислений. Библиоте- ки эти входят в состав MPE и частично описаны в параграфе 2.3. 244 Рис. 12.3. Выполнение процедур с использованием библиотек Для каждой из этих библиотек процессы построения подобны. Сначала должны быть написаны профилирующие версии MPI_Init и MPI_Finalize. Профилирующие версии других процедур MPI подобны по стилю. Код каждой из них выглядит как: int MPI_Xxx (...) { сделать что-либо для профилирующей библиотеки retcode = PMPI_Xxx ( . . . ); сделать что-либо еще для профилирующей библиотеки return retcode; } Эти процедуры создаются только написанием частей “сделать что- либо”, а затем обрамляются автоматически вызовами PMPI_. Поэтому генерация профилирующих библиотек очень проста. Детали генера- ции находятся в MPICH в подкаталоге `mpe/profiling/lib'. КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 12 Контрольные вопросы к 12.1 1. Что такое сетевой закон Амдала? 2. Объясните смысл составляющих с А и с Т коэффициента сетевой деградации. 3. Почему при умножении матрицы на вектор имеет место замедление? 4. В чем состоят характерные различия графиков 12.1 и 12.2? Контрольные вопросы к 12.2 1. Для чего предназнaчена функция MPI_Wtime? 2. На примере программы вычисления числа π расскажите о способе использо- вания функции MPI_Wtime. 3. Дайте перечень средств измерения эффективности? 4. Что такое библиотека MPE? MPI_Bcast MPIBcast MPI_Bcast PMPIBCast Программы пользователя Библиотека профилирования Библиотека MPI 245 Контрольные вопросы к 12.3 1. Что такое профилирование? 2. Какие предопределенные средства профилирования Вы знаете? 3. Зачем нужен пользовательский интерфейс профилирования? 4. Определите назначение функции MPI_PCONTROL(level, ...). 5. Объясните пример профилирования, представленный программой и рис.12.3. 6. Какие библиотеки используются в этом примере? 7. Объясните способ автоматической генерация профилирующих библиотек. Глава 13. ПАРАЛЛЕЛЬНЫЕ БИБЛИОТЕКИ Существует достаточно большое количество библиотек, содержа- щих оптимизированные наборы программ различного назначения, предназначенных для систем с распределенной памятью. Среди них выделяются две библиотеки, связанные с MPI: • ScaLAPACK (Scalable LAPACK) – для параллельного решения разнообразных задач линейной алгебры, • PETSc (Portable Extensible Toolkit for Scientific Computation) – для параллельного решения линейных и нелинейных систем уравне- ний, возникающих при дискретизации уравнений в частных про- изводных. |