Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 21
Текст из файла (страница 21)
Определены следующие типы базовых блоков: вычислительныйблок, вызов пользовательской функции, вызов внешней функции, вызов коммуникационной функции и редуцированный блок. Вычислительный базовый блок состоит из байт-кода выражений, входящих вего состав.Одним из атрибутов вершины модели (внутренней, или базовогоблока) является время ее выполнения (интерпретации), оценка которого является задачей интерпретации модели. Следует отметить, что интерпретация модели позволяет оценить не только время, но и многиедругие динамические атрибуты программы (объем требуемой памяти,степень локальности данных и др.).3.
Моделирование коммуникационных функцийМодель базового блока типа коммуникационная функция представляет собой описание соответствующей коммуникационной функции через базовые операции обмена. Определены следующие базовыеоперации обмена: Init (Free) – выделение (освобождение) ресурtype)сов под служебные структуры данных; Pack(n,(Unpack(n, type)) – упаковка (распаковка) объектов, передаваемых в данной коммуникации; Post(n) (Get(n)) – отправка (прием)буфера памяти длиной n байт другому процессу; Process(serv_msg) – обработка служебного сообщения; Copy(n) –копирование буфера размерности n байт в памяти вычислительногоузла; MakeThread – создание потока выполнения в программе;103Wait(событие) – ожидание события (под событием понимаетсяприбытие сообщения на вычислительный узел).
Например, операцияMPI_SSEND(n, type) (блокирующая синхронная посылка), где n– размер передаваемого сообщения, type – тип пересылаемых данных,в соответствии со стандартом MPI выражается через базовые операцииследующим образом:{Init; Post(запрос); [Pack(n, type)];Wait(разрешение); Post(n); Free;}Операция Pack заключена в квадратные скобки, так как она выполняется только при использовании MPI в неоднородной сети.Можно показать, что перечисленных операций достаточно дляспецификации работы всех функций библиотеки MPI.4.
Интерпретация модели для оценки времени выполненияИнтерпретация модели параллельной Java-программы состоит винтерпретации модели метода main(), одного из классов, входящих всостав программы (указывается пользователем). Интерпретация модели функции (метода) состоит в интерпретации ее корня.Интерпретация внутренней вершины зависит от типа этой вершины (последовательность, ветвление, цикл). Интерпретация вершинытипа последовательность состоит в последовательной интерпретациивершин, входящих в последовательность. Интерпретация вершин типаветвление состоит в интерпретации управляющего выражения, значение которого позволяет выбрать нужную ветвь, и последующей интерпретации выбранной ветви. Интерпретация вершины типа цикл состоит в интерпретации управляющего выражения, значение которого определяет момент выхода из цикла, и многократной интерпретации телацикла до тех пор, пока выход из цикла не произошел.
При интерпретации каждой внутренней вершины значение атрибута время вершин,подчиненных этой вершине, используются для вычисления атрибутавремя этой вершины.Интерпретация базового блока типа вычислительный блок состоитв выполнении инструкций, составляющих этот блок, с целью определения значений переменных, вычисляемых в этом блоке и через управляющее выражение влияющих на работу одной из вершин типа ветвление или цикл. Время работы вычислительного блока определяется заранее, во время предварительного анализа программы.Интерпретация базовых блоков типа вызов пользовательскойфункции и вызов внешней (библиотечной) функции состоит в интер104претации выражений, определяющих значения фактических параметров соответствующего вызова, и последующей интерпретации корневого узла модели тела этой функции.
В результате интерпретации вычисляется время работы корневого узла рассматриваемой функции,которое определяет атрибут время рассматриваемого базового блока.Интерпретация базового блока типа «вызов коммуникационнойфункции» заключается в определении времени работы блока согласновыбранной модели коммуникаций. Поскольку длительность работыкоммуникационной функции может зависеть от момента ее вызова, атакже от момента вызова ответной коммуникационной функции, вводится понятие модельного времени. Параллельная программа, выполняемая на n узлах, состоит из n независимых логических процессов,каждый из которых имеет свои модельные часы.
Начальные показаниявсех модельных часов равны 0. Показания модельных часов логического процесса обновляются после интерпретации в этом процессе каждого базового блока путем добавления значения атрибута время этогобазового блока к текущему значению модельного времени.
Интерпретация работы коммуникационных функций использует показания модельных часов различных процессов для выбора сценария выполнениякоммуникации и для определения продолжительности коммуникации.Логические процессы, участвующие в коммуникации определяютсяинтерпретатором. При интерпретации внутренних вершин показаниямодельных часов не меняются, так как интерпретация внутренней вершины сводится к выбору очередного базового блока, который необходимо интерпретировать.Из 10 базовых операций, используемых для моделирования функций MPI, только операции Post(n) и Get(n) зависят от свойствкоммуникационной системы. Для моделирования этих операций использована модель LogGP [4].
Согласно этой модели время выполнения операций Post(n) и Get(n) определяется по формулам:Time(Post(n)) = b*n + dP(n),Time(Get(n)) = b*n + dG(n),где b – пропускная способность сети, а d(n) – функция накладных расходов на передачу (прием), определяемая экспериментально с помощью бенчмарков.Для вычисления длительности ожидания (операция Wait (событие)) достаточно иметь показания модельных часов в момент началаоперации и в момент ее завершения.1055. Частичная интерпретацияПри интерпретации модели параллельной программы выполняетсяменьший объем вычислений, чем при выполнении самой программы,однако и интерпретация может занимать значительное время. Частичная интерпретация, позволяет при определенных условиях выполнитьинтерпретацию части программы. Результаты интерпретации частипрограммы могут использоваться для упрощения модели параллельнойпрограммы, что делает возможным интерпретировать программу «почастям»: определять время работы только интересующих фрагментовпрограммы, один раз интерпретировать многократно использующиесячасти программы, а также использовать результаты интерпретациичастей программы при интерпретации всей программы, сокращая время одного сеанса интерпретации.Для определения частичной интерпретации вводится операция редукции, которая определена только для вершин модели, интерпретациякоторых закончена и, следовательно, время ее выполнения определено.По определению, результатом редукции базового блока являетсяредуцированный базовый блок, время выполнения которого являетсяконстантой, а байт-код исключен.
Результатом редукции внутреннейвершины является редуцированный базовый блок, время выполнениякоторого является константой. Таким образом, для применения операции редукции время выполнения редуцируемого фрагмента программыдолжно быть известно. Операция редукции внутренней вершины позволяет осуществлять интерпретацию отдельных поддеревьев моделипрограммы, заменяя проинтерпретированные поддеревья редуцированными базовыми блоками. Следует отметить, что редукция отдельной вершины типа «вызов коммуникационной функции» может привести к некорректной модели программы, так как может нарушитьсясоответствие между посылками сообщений и их приемами в разныхпроцессах программы. Поэтому операция редукции для вершин такоготипа допустима только в составе операции редукции внутренней вершины.
При этом редуцируемая вершина должна быть замкнута покоммуникациям, то есть при ее интерпретации не должно оставаться непринятых сообщений, и все операции приема должны завершаться.Операция редукции позволяет интерпретировать программу почастям, заменяя проинтерпретированные фрагменты редуцированнымиблоками. В результате частичной интерпретации количество вершинмодели сокращается, что позволяет сократить длительность интерпретации.
При этом сохраняются оценки времени выполнения как для106программы в целом, так и для остальных единиц интерпретации, присутствующих в модели.6. РеализацияРеализация включает средства построения модели параллельнойпрограммы и средства интерпретации модели. Из описания моделивидно, что построение модели не является сложной задачей.
Рассмотрим реализацию интерпретатора (рис. 1).Интерпретатор осуществляет обход модели текущего метода согласно правилам, изложенным в п. 4 и 5. Во время интерпретации поописанию целевой вычислительной системы порождается набор логических процессов, каждый из которых строит оценку времени работысоответствующего процесса параллельной программы на целевой вычислительной системе. Максимальная оценка принимается в качествеоценки времени работы редуцируемой вершины. Если в качестве редуцируемой вершины выбрать корень одного из методов main, то будетинтерпретирована вся программа.Рис. 1. Схема выполнения интерпретациимодели параллельной программыИнтерпретатор при своей работе использует различные параметрыцелевой системы: мощность вычислительных узлов, латентность ипропускную способность каналов передачи данных, длительность базовых операций MPI.
Таким образом, располагая моделью программыи описанием целевой вычислительной системы, пользователь получаетдинамический профиль программы, используя только инструменталь107ный компьютер.Проверка точности интерпретации производилась на несколькихмодельных примерах. Сравнение результатов прогноза времени выполнения с временем фактического выполнения для одного из такихпримеров приведены на рис. 2. Рассматривается программа решениязадачи теплопереноса в стержне с использованием явной разностнойсхемы.
Размер матрицы увеличивался пропорционально количествузадействованных процессоров. Размер данных на одном вычислительном узле занимал приблизительно 80% памяти.Рис. 2. Сравнение прогноза времени выполнения (серая кривая) с временемфактического выполнения (черная кривая).Вычисления выполнялись на высокопроизводительном кластереМСЦ (PowerPC64 2.2GHz, Myrinet). Для прогнозирования времени работы программы использовалась рабочая станция с процессором IntelPentium IV 2,6 GHz с 512 Mb оперативной памяти. Время, требуемоедля получения прогноза, не превышало 60 сек. Относительная погрешность прогноза порядка 5%.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
