47233

Предсказание коммуникационных расходов параллельных программ

Дипломная

Информатика, кибернетика и программирование

Параллельное программирование На сегодняшний день параллельные вычислительные системы дают наибольшую производительность в решении задач требующих большого количества вычислений часто на больших объемах данных. MPI. Самая распространенная реализация модели передачи сообщений – это стандарт MPI Messge Pssing Interfce описывающий ряд функций для обмена данными между отдельными процессами или внутри...

Русский

2013-11-26

205 KB

2 чел.

Московский государственный университет имени М.В.Ломоносова, факультет Вычислительной математики и кибернетики,

кафедра системного программирования

ДИПЛОМНАЯ РАБОТА

Тема: “Предсказание коммуникационных расходов параллельных программ”

Выполнил:

Попов Д. В.

группа 527

Научный руководитель:

профессор д.ф.-м.н.

Крюков Виктор Алексеевич

Москва, 2004 г.


Содержание

[1]
Введение

[1.1] Параллельное программирование

[1.2] Предсказание

[2]
Постановка задачи

[3] Моделирование работы MPI

[4]
Новая схема работы Предиктора

[5]
Заключение

[6]
Литература


Введение

Параллельное программирование

На сегодняшний день параллельные вычислительные системы дают наибольшую производительность в решении задач, требующих большого количества вычислений, часто на больших объемах данных. Это достигается за счет распределения вычислений по большому числу одновременно работающих процессоров, каждый из которых решает свою часть задачи. По архитектуре параллельные вычислительные системы делятся на многопроцессорные системы с общей памятью и системы с распределенной памятью.

 Системы с общей памятью обычно выглядят как многопроцессорный вычислительный комплекс, в котором все процессоры обращаются к одному единому для всех блоку оперативной памяти. Такой подход минимизирует время обменов данными между процессорами, но, из-за сложности организации бесконфликтного доступа к общей памяти, ограничивает количество процессоров. Практика показывает, что фактически  количество процессоров в такой системе ограничено 32-мя. При большем числе процессоров накладные расходы обеспечения корректной работы с общей памятью сводят на нет увеличение производительности.

Успешной альтернативой такому подходу являются многопроцессорные системы с распределенной памятью, где у каждого процессора есть в распоряжении своя оперативная память, а обмены данными между процессорами осуществляются при помощи коммуникационной системы – обычно специально организованной высокопроизводительной локальной сети. Такой подход позволяет использовать в качестве узлов распределенной системы обычные персональные компьютеры (т.е. не создавать специальную техническую базу), а также легко наращивать число задействованных процессоров. В настоящее время существуют распределенные вычислительные системы с числом процессоров, превышающим 10000.

Программа, решающая задачу на параллельной вычислительной системе, называется параллельной программой. Работа параллельной программы представляет собой одновременную работу копий программы на всех процессорах вычислительной системы (или на заданном подмножестве процессоров). В зависимости от логики работы параллельной программы, их делят на несколько классов:

-SIMD (Single Instruction, Multiple Data) – каждый процессор обрабатывает свою часть данных, но все они действуют по одному алгоритму (один поток выполнения).

-MIMD (Multiple Instruction, Multiple Data) – каждый процессор обрабатывает свою часть данных, но действия могут быть разными для разных процессоров (несколько потоков выполнения).

-MISD (Multiple Instruction, Single Data) – разные потоки выполнения над одними данными. Фактически, никогда не реализовывался.

Существует несколько подходов к созданию параллельных программ. Они различаются используемыми инструментами, а главное -  принципами распараллеливания программы, или моделью параллельного программирования.

Модель передачи сообщений. MPI.

В этой модели копии параллельной программы, запускаемые на разных процессорах вычислительной системы, взаимодействуют друг с другом посредством передачи сообщений. При этом определение всей логики работы каждого процесса (т.е. какие данные и как обрабатывать, с какими процессами связываться и какие сообщения посылать) лежит целиком на плечах программиста. Самая распространенная реализация модели передачи сообщений – это стандарт MPI (Message Passing Interface), описывающий ряд функций для обмена данными между отдельными процессами или внутри группы процессов (коллективные операции). Стандарт MPI описывает набор функций, их синтаксис для языков Си и Фортран и общую семантику их работы. В настоящее время существует несколько реализаций этого стандарта в виде библиотек функций для указанных языков на различных платформах. Внутренние алгоритмы их работы (например, способ организации коллективных обменов) могут отличаться. Основные достоинства MPI перед другими коммуникационными библиотеками:

  •  Общий интерфейс для разных языков (Фортран, Си, Си++);
  •  Предоставление возможностей для асинхронных обменов (совмещения по времени обменов сообщениями  и вычислений);
  •  Наличие различных режимов передачи сообщений, позволяющих избежать лишнего копирования информации для буферизации. Как следствие – высокая производительность.
  •  Широкий набор коллективных операций (например, широковещательная рассылка информации, сбор информации с разных процессоров), допускающих гораздо более эффективную реализацию, чем использование соответствующей последовательности пересылок точка-точка;
  •  Удобная адресация: каждый процесс имеет свой номер (целое число от 0 до N-1, где N -  число процессоров). Это делает программу переносимой и независимой от способа адресации в сети.
  •  Возможность задания типа передаваемой информации, что позволяет обеспечить ее автоматическое преобразование в случае различий в представлении данных на разных узлах системы.

Модель параллелизма по данным. HPF.

В этой модели программист лишь указывает то, каким образом данные должны быть распределены по процессорам, а компилятор, используя эту информацию, преобразует последовательную программу в параллельную либо в модели передачи сообщений, либо в модели с общей памятью. При этом работа распределяется по правилу собственных вычислений: каждый процессор выполняет только те вычисления, которые относятся к данным, распределенным на этот процессор.

Модель параллелизма по данным  имеет следующие достоинства.

  •  Поскольку большинство вычислительных задач характеризуется однотипными вычислениями на больших объемах данных, такие задачи легко распараллеливаются в рамках данной модели.
  •  Программисту не надо думать об организации взаимодействий и обменов между процессами, он пишет обычную последовательную программу с небольшими пометками для компилятора, который берет всю низкоуровневую работу на себя.
  •  Улучшение локальности программы – т.к. с ростом числа процессоров на каждый процессор приходится все меньший объем данных, а сами данные расположены компактно, то увеличивается эффективность кэша процессора, что еще больше улучшает производительность.

Пример реализации данной модели – язык HPF (High Performance Fortran).

Модель параллелизма по управлению. OpenMP.

Данная модель представляет собой некоторую автоматизацию создания параллельной программы для систем с общей памятью. Программист не пишет код для отдельных нитей, а лишь указывает компилятору на циклы и секции программы, которые можно распараллелить. Компилятор берет на себя работу по организации параллельных нитей и распределению между ними витков цикла.

Пример реализации такой модели – язык OpenMP. Это интерфейс прикладной программы, расширяющий последовательный язык программирования (Си, Фортран)  набором директив компилятора, вызовов функций библиотеки поддержки выполнения и переменных среды.

Модель параллелизма по данным и управлению. DVM.

В данной модели программист также пишет обычную последовательную программу, но теперь он может указать компилятору, какие данные и какие вычисления распределены по процессорам. В рамках данной модели в Институте прикладной математики им М.В. Келдыша РАН была создана система разработки параллельных программ DVM (Distributed Virtual Machine или Distributed Virtual Memory). Она включает в себя расширения языков Си и Фортран C-DVM и Fortran-DVM, где специальные директивы компилятору оформлены в виде макросов, прозрачных для обычных компиляторов. Т.е. программа на языке C-DVM или Fortran-DVM продолжает компилироваться обычным компилятором и работать как простая последовательная программа. Но будучи пропущенной через специальный транслятор, программа с DVM-директивами превращается в программу, использующую функции библиотеки поддержки Lib-DVM, которые  используют MPI для обменов данными между процессами. Причем распределение данных и вычислений по процессорам производится функциями runtime-системы  динамически. Поэтому скомпилированная DVM-программа может без перекомпиляции работать на произвольном числе процессоров.

Предсказание

Важной задачей в области параллельного программирования является задача предсказания времени выполнения параллельной программы. Имея возможность такого предсказания, можно исследовать характеристики еще не созданных параллельных  вычислительных систем и определять их слабые места, оценивать необходимость приобретения той или иной вычислительной системы, изучать поведение и характеристики выполнения задачи на разных конфигурациях (в частности, определить оптимальное число процессоров для данной задачи и т.д.), предсказать эффективность параллельной программы без запуска на реальной параллельной машине и т.д. Однако, не каждая система параллельного программирования, не каждая модель параллельного программирования позволяет осуществить такое предсказание.

Допустим, мы имеем трассу работы параллельной программы на рабочей станции (одном процессоре) или на некоторой параллельной системе и хотим предсказать время выполнения нашей программы на некоторой другой системе.

Модель передачи сообщений. MPI.

В этой модели поведение каждого процесса существенно зависит от общего числа процессов и ранга (номера) данного процесса. Поэтому, не имея информации о внутренней логике программы, предсказать ее поведение не представляется возможным. Подход, который может быть использован – запуск программы на некоторой эмуляции нужной системы – плох тем, что требует произведения вычислений самой программы, т.е. время, необходимое для получения предсказания, будет сопоставимо (или даже больше), чем время выполнения программы на одном процессоре. Если задача достаточно большая (а именно с такими обычно и приходится работать), то это время становится неприемлемо большим.

Модель параллелизма по данным. HPF.

В данной модели поведение каждого процесса зависит от системы поддержки, принимающей решения на основе числа процессов и номера текущего. Поскольку на другом числе процессоров система поддержки HPF примет другие решения, неизвестные заранее, предсказать поведение программы не получится.

Модель параллелизма по управлению. OpenMP.

Поскольку OpenMP применяется на системах с общей памятью, где существуют сложные алгоритмы работы с кэшем и обеспечения консистентности, скорость работы сильно зависит от числа процессоров. Предсказание таких эффектов – слишком сложная и малоизученная задача, поэтому предсказание времени выполнения OpenMP программ также представляется затрудненным.

Модель параллелизма по данным и управлению. DVM.

В отличие от предыдущих моделей, система DVM специально была создана таким образом, чтобы DVM-программы легко могли быть запущены на разных количествах процессоров. Всю работу по распределению данных и вычислений выполняют функции системы поддержки, поэтому обычно в DVM-программе нет разветвлений в зависимости от числа процессоров. Это означает, что в трассе выполнения последовательность вызовов функций системы поддержки не меняется при изменении числа процессоров. Т.к. исходные тексты функций системы поддержки доступны и алгоритмы их работы известны, работу DVM-программы можно промоделировать (не выполняя вычислений, а лишь предсказывая требуемое на них время). Это сделало возможным появление в DVM системе инструмента под названием Предиктор.

Предиктор

Предиктор предназначен для анализа и отладки эффективности выполнения DVM-программ без использования реальной параллельной машины. Имея на входе трассу выполнения программы и характеристики параллельной машины, Предиктор предсказывает время выполнения этой программы на заданной машине и выдает подробные характеристики выполнения. Главные характеристики – это:

  •  время выполнения; 
  •  коэффициент эффективности; 
  •  потерянное время.

Время выполнения - это максимальное из времен выполнения программы на каждом процессоре.

Для вычисления главной характеристики параллельного выполнения – коэффициента эффективности следует вычислить два времени. Во-первых, полезное время, это время, которое потребуется для выполнения программы на однопроцессорной ЭВМ. Во-вторых, общее время использования процессоров, которое вычисляется как произведение времени выполнения на число процессоров. Коэффициент эффективности равен отношению полезного времени к общему времени использования процессоров.

Разница между общим временем использования процессоров и полезным временем представляет собой потерянное время. Если программист не удовлетворен коэффициентом эффективности выполнения своей программы, то он должен проанализировать составляющие части потерянного времени и причины их возникновения.

Существуют следующие составляющие потерянного времени:

  •  потери из-за недостатка параллелизма, приводящего к дублированию вычислений на нескольких процессорах (недостаточный параллелизм);
  •  потери из-за выполнения межпроцессорных обменов (коммуникации);
  •  потери из-за простоев тех процессоров, на которых выполнение программы завершилось раньше, чем на остальных (простои).

Для оценки суммарных потенциальных потерь, которые могут возникнуть из-за неодновременного запуска коллективных операций на разных процессорах, должна вычисляться и выдаваться пользователю специальная характеристика – синхронизация. Основная причина этих потерь, на устранение которой должен быть нацелен программист – разбалансировка загрузки процессоров при выполнении параллельных циклов. Для оценки возможных потерь из-за разбалансировки программисту выдается обобщенная характеристика – разбалансировка.

Важной характеристикой, отражающей степень совмещения межпроцессорных обменов с вычислениями, является время перекрытия обменов вычислениями.

Недостатки Предиктора

Точность предсказания определяется следующими реализационными ограничениями.

Во-первых, предиктор исходит из того, что соотношение времен выполнения любых фрагментов данной программы на целевой машине и той, на которой была получена трасса, является константой – отношением их производительностей. Во-вторых, при прогнозировании времен коммуникации, вызываемой выполнением любой коммуникационной операции (редукция, обновление теневых граней, загрузка буферов удаленного доступа, и т.п.), учитываются только характеристики коммуникационной сети, количество передаваемых сообщений и их объем. Взаимное влияние коммуникаций, вызванных разными операциями, а также их порядок при этом не учитываются. Кроме того, программа может состоять из нескольких независимых ветвей, выполняющихся одновременно. На многих типах сетей коммуникации одной ветви будут влиять на время прохождения коммуникаций других ветвей, что старая версия Предиктора никак не учитывает.

Еще одним важным недостатком является очень грубый подход к предсказанию коллективных операций: считается, что все процессоры должны начать коллективную операцию одновременно. Если какой-то процессор пришел к данной коллективной операции раньше других, считается, что он ждет остальных. Аналогично, если он закончил коллективную операцию раньше, он не выполняет никаких действий до тех пор, пока остальные процессоры не закончат ее. Такой подход вызван принципиальным недостатком старого Предиктора – он эмулирует не работу разных процессоров по отдельности, а работу всей системы в целом. Он читает трассу выполнения программы, и для каждого вызова функций Lib-DVM предсказывает время его выполнения сразу всей распределенной системой, а не отдельными процессорами. Такой подход создает существенное отличие между поведением реальной системы и эмулируемой Предиктором. Это приводит к заметным ошибкам в предсказании времен выполнения программ, активно использующих коллективные операции обмена.


Постановка задачи

Учитывая недостатки существующего Предиктора, было предложено создать схему более точного предсказания времен коммуникаций. Так как коммуникационные функции системы поддержки DVM опираются на вызовы библиотеки MPI, было решено промоделировать поведение MPI и работу сети, т.е. создать библиотеку функций, соответствующих функциям MPI, которые позволили бы предсказать время выполнения MPI функций. Имея информацию о времени работы функций MPI, можно вычислить и время работы коммуникационных функций системы поддержки DVM, т.е. более точно предсказать коммуникационные расходы параллельной программы. И, хотя изначальная цель была в том, чтобы повысить точность работы Предиктора, библиотеку предсказания времени выполнения MPI функций можно использовать и в отрыве от Предиктора, саму по себе.

Так как порядок и время выполнения функций MPI, вызванных DVM-программой, могут различаться на разных процессорах, а существующий Предиктор не учитывает такую вариацию времен на разных процессорах, вычисляя времена выполнения функций системы поддержки сразу для всей параллельной машины, необходимо было начать создание нового Предиктора, работающего по другой схеме. Новый Предиктор должен моделировать работу каждого в отдельности процессора целевой машины. Такой подход позволит приблизить модель к реальной системе, а также позволит моделировать такие эффекты, которые невозможно было предсказать в старой модели, например, влияние коммуникаций разных процессоров или ветвей программы друг на друга. В новом Предикторе трасса читается каждым эмулируемым процессором по отдельности, и для него вычисляется время выполнения каждого шага.

Моделирование работы MPI

Стандарт MPI включает в себя очень большое число функций, многие из которых используются крайне редко. Поэтому для моделирования были выбраны те, которые используются чаще всего и которые могут понадобиться для моделирования коммуникационных операций системы поддержки DVM. Для этого исходные тексты runtime системы DVM версии 3.93 (последней доступной на официальном сайте системы DVM) были проанализированы, и было выявлено около 30 функций MPI, вызовы которых встречаются в системе поддержки DVM. К этому списку были добавлены еще некоторые функции, которые либо часто используются в MPI-программах, либо используются при реализации других MPI-функций. В итоге, список моделируемых функций получился следующий (аргументы опущены):

  MPI_Init();

 MPI_Finalize();

 MPI_Wtime();

 MPI_Send();

 MPI_Recv();

 MPI_Isend();

 MPI_Issend();

 MPI_Irecv();

 MPI_Wait();

 MPI_Test();

 MPI_Waitall();

 MPI_Sendrecv();

 MPI_Bsend();

 MPI_Barrier();

 MPI_Bcast();

 MPI_Gather();

 MPI_Allgather();

 MPI_Allgatherv();

 MPI_Allreduce();

 MPI_Alltoallv();

 MPI_Group_incl();

 MPI_Group_free();

 MPI_Comm_size();

 MPI_Comm_rank();

 MPI_Comm_dup();

 MPI_Comm_create();

 MPI_Comm_split();

 MPI_Comm_free();

 MPI_Comm_group();

 MPI_Get_count();

 MPI_Get_processor_name();

Интерфейс

Библиотека функций, предсказывающих время работы перечисленных функций MPI была оформлена как класс на языке C++  “CComSys”, содержащий одноименные функции (без префикса MPI_). Для некоторых функций (типа MPI_Get_count , MPI_Comm_rank и т.п.) время выполнения не важно (его можно считать нулевым, т.к. они выполняются локально и очень просты по сути), зато важны результаты работы (конкретные значения). Для некоторых (типа MPI_Recv и т.п.)– наоборот, некоторые конкретные значения (скажем, пришедшие данные) не важны, зато важно время выполнения. Поэтому список аргументов функций не соответствует стандарту MPI – ненужные переменные были убраны из списков аргументов, зато были добавлены дополнительные аргументы. В частности, для тех функций, для которых важно время их выполнения, были добавлены аргументы double time – момент времени, когда эта функция была вызвана, и double *rettime – ссылка на переменную, в которую будет записано время выполнения соответствующей функции MPI.

Низкоуровневые пересылки данных.

Стандарт MPI не указывает на то, какой тип сети должен использоваться, каковы ее параметры и особенности. Однако, от типа сети, ее параметров в большой степени зависит время, необходимое для передачи сообщений. Библиотека MPI просто использует имеющуюся в наличии сеть для передачи своих сообщений. По аналогии, был создан абстрактный класс CNetwork предоставляющий метод для получения времени пересылки одного сообщения заданной длины от такого-то процессора к такому-то, при условии, что вызов произошел в такое-то время. Соответственно, при моделировании пересылок данных вызывается этот метод. В зависимости от того, какую сеть необходимо промоделировать, при инициализации библиотеки ей передается указатель на класс, наследный от CNetwork (т.е. содержащий нужный метод), реализующий тот или иной тип сети. На данный момент поддерживаются два основных типа (наиболее распространенных в реальных параллельных машинах): Ethernet и Myrinet.

Реальные кластеры (параллельные машины) часто строятся из двухпроцессорных узлов. С точки зрения сети это означает, что между двумя процессорами, находящимися на одном узле,  обмен данными происходит посредством копирования память-память, а не передачи по сети. Эта особенность тоже учтена и может быть задана отдельным параметром.

Моделирование сети Ethernet с шинной архитектурой отличается тем, что в один момент может происходить только одна пересылка. Если происходит запрос на пересылку в тот момент, когда сеть занята другой, происходит ожидание пока сеть не освободится, и лишь затем происходит «передача». Время передачи данных определяется по формуле

T  =  Tstart + Nbytes * Tbyte,

где Tstart – время подготовки к передачи, Tbyte – время передачи одного байта (эти два значения являются параметрами сети и задаются в файле параметров),

а Nbytes – размер передаваемого сообщения в байтах.

Моделирование сети Myrinet отличается тем, что она имеет несколько каналов, по каждому из которых может происходить передача данных в обе стороны одновременно. Количество каналов является параметром сети. При запросе на пересылку сообщения проверяется наличие свободного канала. Если все каналы заняты, то происходит «ожидание» пока не освободится хотя бы один из каналов. После этого сообщение «посылается» по той же схеме.

Источник алгоритмов

Для того, чтобы правильно промоделировать функции MPI, были взяты алгоритмы, почерпнутые из исходных текстов одной из реализаций MPIMPICH версии 1.2.5. Эта реализация MPI действительно часто применяется на реальных параллельных машинах.

Пересылки точка-точка

К числу операций типа точка-точка относятся функции

MPI_Send(),   MPI_Recv(),  MPI_Isend(),  MPI_Issend(),  MPI_Irecv(),  MPI_Wait(), MPI_Test(),  MPI_Waitall(),  MPI_Sendrecv(),  MPI_Bsend().

Важно заметить, что в реализации MPICH есть два основных режима передачи сообщений типа точка-точка: eager и rendezvous.

В режиме eager  сообщение отправляется как только вызвана функция отправки, независимо от того, была ли на принимающем узле вызвана функция приема сообщения. На принимающем узле сообщение сохраняется в буфер, где хранится пока не будет извлечено оттуда функцией приема. Этот режим может вызывать проблемы в случае переполнения принимающего буфера, но зато обеспечивает максимальную производительность, т.к. не требует лишних обменов (см. ниже).

В режиме rendezvous сообщение отправляется только тогда, когда его готовы принять. Это происходит по следующей схеме: при вызове операции посылки на принимающий узел отправляется сообщение о том, что заявлена такая-то пересылка. Когда на принимающем узле вызывается функция приема, на посылающий узел отправляется сообщение о готовности приема. Только после этого само сообщение с данными посылается. Этот режим позволяет избежать переполнения принимающего буфера, но требует больших накладных расходов.

Выбор режима в MPICH осуществляется в зависимости от размера пересылаемых данных. Для относительно небольших сообщений (меньше некоторого порога) используется режим eager, а для больших - rendezvous. Значение порога является параметром системы и задается в качестве одного из параметров всей модели (наряду со значениями Tstart, Tend, числа каналов и т.д.).

Особенности реализации

Объект класса CComSys, моделирующего поведение MPI, отвечает за всю коммуникационную систему и существует в одном экземпляре. Т.е. все процессоры для получения времен выполнения вызовов MPI обращаются к одному объекту. При этом, согласно стандарту MPI и алгоритмам работы MPICH, некоторые функции должны быть блокирующими. Например, функция MPI_Recv должна возвращаться только тогда, когда сообщение получено. Т.к. библиотека рассчитана на один поток выполнения, такое поведение могло бы привести к зависанию в случае, если команда приема сообщения вызвана раньше, чем соответствующая команда отправки (функция не возвращается, пока сообщение не будет отправлено, но сообщение не может быть отправлено, пока эта функция не вернется). Поэтому была принята следующая схема работы: если время возврата пока не может быть определено (в приведенном примере: функция посылки еще не вызвана), то в переменную, которая должна содержать время работы функции, записывается -1. Когда же ситуация прояснится (в примере: будет вызвана функция посылки), в этой переменной окажется нужное значение времени. Это можно проиллюстрировать на следующем примере:

double tsend, trecv;

CComSys cs;

cs.Recv(10, &trecv, …); // в момент времени 10 вызывается блокирующий Recv, но Senda еще не было

// trecv сейчас равна -1

cs.Send(11, &tsend,…); // в момент времени 11 вызывается соответствующий Send

// допустим, пересылка заняла 3 сек, режим rendezvous, пересылка закончена в момент 14

// теперь trecv=4, tsend=3

Т.е. функции имеют побочный эффект.

Алгоритм моделирования операций точка-точка

Объект коммуникационной системы (класса CComSys) содержит в себе очередь так называемых заявок на передачу и функции работы с этой очередью. Операции точка-точка отличаются тем, что для осуществления каждой такой операции должно быть вызвано 2 функции (одна на прием, другая на передачу) с соответствующими друг другу аргументами. Когда вызывается одна из таких функций, производится поиск в очереди заявок заявки от встречной функции с соответствующими аргументами. Если такая заявка находится, значит соответствующая парная функция уже была вызвана ранее и вся необходимая информация имеется. Тогда происходит моделирование передачи в соответствии с режимом посылки сообщения (eager/rendezvous), запись по указанным адресам времен выполнения обоих функций (отправки и приема), а заявка из очереди удаляется. Если же заявка найдена не была, то информации пока недостаточно, вместо времени выполнения записывается -1, и в очередь добавляется заявка с описанием операции и ее аргументов.

Алгоритм моделирования неблокирующих операций точка-точка

Порядок действий похож на случай блокирующих операций с той лишь разницей, что каждой паре вызовов отправка-прием может соответствовать пара вызовов MPI_Wait, а время работы операций отправки и приема всегда считается нулевым (т.е. подразумевается, что обмен происходит в фоновом режиме). Когда пересылка совершается (т.е. когда вызваны обе встречные функции), производится поиск заявок на Wait. Если они находятся, то они удовлетворяются (по нужному адресу записывается время) и уничтожаются. Если не находятся (т.е. Wait еще не вызывали), то соответствующие заявки добавляются в очередь.

При вызове операции Waitall (ожидание целого ряда неблокирующих операций) в очередь добавляется ряд заявок, похожих на Wait, но ссылающихся на одну переменную, где должно быть время работы. При удовлетворении заявок определяется максимум из временных интервалов между вызовом Waitall и завершением обменов.

Алгоритм моделирования операции MPI_Sendrecv

Полностью соответствует реализации MPICH и состоит из одного ISend, одного IRecv и следующего за ними Waitall.

Коллективные операции

В MPICH коллективные операции реализованы через операции точка-точка. Это было сделано для переносимости, т.к. не каждый тип сети позволяет делать широковещательные пересылки. Все коллективные операции осуществляются в рамках заданного коммуникатора, определяющего некоторое  подмножество процессов. У каждого процесса в коммуникаторе есть свой ранг – порядковый номер от 0 до N-1, где N – число процессов в коммуникаторе.

Для каждой коллективной операции библиотека предсказания старается повторить ту последовательность обменов точка-точка, которая происходит при работе соответствующей функции коллективной операции MPICH.

MPI_Barrier:

Алгоритм работы следующий:

Коммуникатор делится логически на две части: первые N2 процессов (ранги 0..N2-1) и остальные (N2..N-1), где N2 – максимальная степень двойки, не превышающая число процессов в коммуникаторе. Например, если число процессов 10, то N2 будет равно 8, В первую группу войдут процессы 0..7, а во вторую – 8..9. Каждый процесс с номером Р из второй группы обменивается (MPI_Sendrecv) коротким пакетом с процессом P-N2 (8-й с 0-ым, 9-й с 1-м). Работа этого процесса продолжится только тогда, когда он получит пакет от процесса P-N2. Работа процессов из первой группы происходит следующим образом: сначала ожидается прибытие пакета от процесса из второй группы (если P+N2<N, в нашем примере Р=0,1), затем происходит обмен с процессами из первой группы. Каждый процесс Р обменивается пакетами с теми процессами, номера которых в двоичной записи отличаются от Р в одном бите. Если представить процессы в углах двоичного куба, то ребра этого куба будут показывать на то, какие процессы обмениваются. После завершения взаимных обменов между процессами первой группы, посылаются пакеты процессам второй группы (для таких Р, что Р+N2<N).

MPI_Bcast:

Алгоритм работы:

Для каждого процесса в коммуникаторе вычисляется его относительный ранг:

rel_rank = P – P0, для P >= P0, и

rel_rank = P – P0 + N, для P < P0,

где Р – ранг (номер) процесса, Р0 – номер рассылающего процесса.

Далее, пересылка данных происходит по двоичному дереву:

Для каждого процесса определяется относительный ранг процесса, от которого он должен принять данные, и относительные ранги процессов, которым он должен данные послать. Пусть m - число нулей в конце двоичной записи относительного ранга процесса (например, для 4=100b m=2, для 2=10b m=1, для 3=11b m=0), тогда на (m+1)-м месте справа стоит 1 (если относительный ранг не равен 0, конечно). Относительный ранг процесса, от которого должны прийти  данные, получается из относительного ранга текущего процесса заменой 1 на (m+1)-м месте справа на 0 (т.е для 4=100b и 2=10b это 0, для 3=11b это 2=10b). Процесс с нулевым относительным рангом ни от кого данные не получает, т.к. он по определению является рассылающим. Относительные ранги процессов, которым текущий процесс должен послать данные, получаются из относительного ранга текущего процесса заменой на 1 одного из m последних нулей (т.е. для 4=100b это 5=101b и 6=110b, для 2=10b это 3=11b, а для 1 или 3 – никого). Зная эти относительные ранги, каждый процесс ждет получения данных того, кто должен ему прислать, а затем посылает данные тем, кому должен послать в соответствии с этим алгоритмом. Моделирование обменов между процессами происходит по той же схеме, что и моделирование операций точка-точка.

MPI_Gather:

При вызове данной функции корневой (принимающий) процессор готовится принимать данные от остальных (используя IRecv и Waitall), а остальные посылают ему свои данные.

Функция элементарно выражается через операции точка-точка ISend, IRecv, Wait и Waitall также, как это сделано в реализации MPICH.

MPI_Allgather и MPI_Allgatherv:

При вызове данной функции каждый процессор должен послать другим свою порцию данных и получить от остальных их порции данных. В MPICH использован децентрализованный алгоритм, когда данные перемещаются по кругу: каждый процессор получает порции данных от соседа слева и, когда получит, передает их соседу справа. Соседями считаются процессы, ранги которых отличаются на 1, а также 0 и (N-1)-й процессы. Первоначально у каждого процесса есть собственная порция данных, которую он сразу готов послать соседу справа. После такой пересылки у соседа справа есть уже две порции – своя и только что полученная от соседа слева. Она посылает их и т.д. В результате такого циклического процесса происходит N*(N-1) пересылок типа точка-точка (N порций, каждая из которых передается N-1 раз). При моделировании работы этой функции создается двухмерный массив, в котором для каждого процесса i помечено, есть ли у него порция данных j. При каждом вызове функции пробегается цикл по всему массиву и определяется, какие пересылки можно сделать. Они производятся. Этот процесс повторяется до тех пор, пока ни одна пересылка не будет более возможна (т.е. либо уже все процессы получили свои данные, либо какие-то из них еще не поделились своими, т.е. вызов Allgather с этих процессов пока не производился).

MPI_Allreduce:

Алгоритм работы:

Согласно тому алгоритму, который реализован в MPICH, данная операция производится в два этапа. Сначала данные собираются на процесс с нулевым рангом со всех остальных по двоичному дереву. Алгоритм сбора в точности повторяет алгоритм функции Bcast, но пересылки идут в обратную сторону: каждый процесс может получать данные от нескольких процессов, а посылает только одному. Каждый раз, когда процессу приходят от кого-то данные, сразу же производится редукция между двумя порциями данных – только что пришедшей и той, что уже хранилась у этого процесса. В результате, на нулевой процесс приходят уже результаты редукционной операции в рамках каждого из двоичных поддеревьев. На нулевом процессе делается то же самое, в результате чего получается окончательное значение редуцированных данных. После этого запускается второй этап – распространение редуцированных данных всем остальным процессам. Это происходит путем вызова уже известного MPI_Bcast. Моделирование функции MPI_Allreduce полностью воспроизводит этот алгоритм, совершая операции обмена точка-точка в том же порядке.

MPI_Alltoallv:

Данная операция легко сводится к набору IRecv, ISend и Waitall для каждого процесса, точно также, как это сделано в реализации MPICH.


Новая схема работы Предиктора

В связи с тем, что разработанная библиотека предсказания времен выполнения функций MPI вычисляет время для каждого процесса по отдельности, потребовалось изменить схему работы Предиктора – инструмента предсказания времен выполнения DVM-программ. К тому же, как уже упоминалось, новая схема позволила избавиться от некоторых важных проблем старого Предиктора, влияющих на точность предсказания.

Основное отличие новой схемы состоит в том, что теперь работа каждого процессора целевой параллельной машины моделируется отдельно. Если раньше Предиктор читал трассу выполнения DVM-программы и сразу рассчитывал время выполнения каждого из вызовов системы поддержки и вычислений между ними  на всей параллельной машине, то теперь трасса читается и интерпретируется каждым моделируемым процессором по отдельности.

Множество процессоров целевой машины представлено в виде массива объектов типа CProc. Каждый из этих объектов описывает состояние своего процессора и содержит методы для интерпретации функциональных вызовов трассы. На каждом из моделируемых процессоров существует свое локальное время. Главный цикл моделирования выглядит следующим образом: до тех пор, пока не есть еще не завершившие работу процессоры, выбрать процессор с минимальным локальным временем и на этом процессоре сделать один шаг. Один шаг процессора заключается в том, чтобы промоделировать либо время вычислений между двумя вызовами системы поддержки DVM, либо время работы системы поддержки и саму работу, если требуется.

Трасса выполнения DVM программы состоит из последовательности текстовых записей о вызовах функций системы поддержки. Для каждого вызова дано время, прошедшее с последнего вызова системы поддержки (т.е. время вычислений программы на этом отрезке), время отработки самой функции системы поддержки, ее название и параметры. На каждую такую запись в трассе при моделировании приходится два шага. Один шаг – вычисления между двумя вызовами. Другой шаг – вызов функции системы поддержки. Каждый процессор сам определяет какой шаг он должен сделать и надо ли считать следующую запись из трассы.

Архитектура нового Предиктора

Так как на целевой машине может быть несколько сотен и даже тысяч процессоров, хранить разнообразные служебные данные и читать один файл всеми моделируемыми процессорами слишком расточительно с точки зрения требуемой памяти. Для решения этой проблемы был создан класс «Сервер данных» (CDataServer), который хранит все необходимые данные в одном экземпляре, а моделируемые процессоры обращаются  за нужными данными к нему. В частности, именно сервер данных читает файл трассы. Когда какому-то процессору нужна следующая запись из трассы, он обращается к серверу данных, а тот смотрит, не сохранена ли эта запись у него в памяти, и либо выдает сохраненную (если есть), либо производит чтение из файла и сохраняет запись для других процессоров. Когда все процессоры запросили эту запись, ее присутствие в памяти больше не считается необходимым, и она удаляется. Идентификация записей трассы производится по ее порядковому номеру. Каждые процессор хранит у текущий порядковый номер записи трассы, увеличивая его при получении очередной записи. Кроме того, именно сервер данных содержит в себе объект класса CComSys (библиотека предсказания времен выполнения функций MPI), и именно через него процессоры обращаются к коммуникационной системе. Общая архитектура нового Предиктора выглядит так:

Разбиение на интервалы

Параллельная программа в DVM представляется в виде дерева вложенных интервалов, которые могут быть 4-х типов. Выполнение всей программы целиком рассматривается как интервал самого высокого (нулевого) уровня, и является отдельным типом интервала. Этот интервал может включать в себя несколько интервалов следующего (первого) уровня. Такими интервалами могут быть параллельные циклы, называемые параллельными интервалами (PAR), последовательные циклы, называемые последовательными интервалами (SEQ), а также любые отмеченные программистом последовательности операторов, называемые пользовательскими интервалами (USER). Интервалы первого уровня могут в свою очередь включать в себя интервалы второго уровня, и т.д. Каждый параллельный цикл рассматривается как отдельный  интервал.

Каждый интервал определяется именем файла с исходным текстом DVM-программы, номером строки, в которой расположен первый оператор интервала, типом и количеством входов в интервал (EXE_count).

Для каждого интервала и каждого процессора, на котором выполнялся данный интервал, в процессе моделирования вычисляются следующие характеристики выполнения программы:

  •  Execution_time – время выполнения интервала, то есть сумма отрезков времени, когда этот интервал был текущим интервалом
  •  I/O_time – сумма времен выполнения выданных в интервале операций ввода-вывода, без учета затрат на коммуникации
  •  CPU_time – сумма характеристик CPU_time_Par и CPU_time_Seq
  •  CPU_time_Par – время параллельных вычислений в интервале; для последовательных интервалов равно 0
  •  CPU_time_Seq – время последовательных вычислений в интервале; для параллельных интервалов равно 0
  •  Lost_time – суммарное потерянное время на интервале
  •  Communication – общее время коммуникаций, то есть сумма времен коммуникаций всех коллективных операций
  •  Wait_reduction – время коммуникаций при ожидании завершения редукции
  •  Wait_shadow – время коммуникаций при ожидании завершения обновления теневых граней
  •  Remote_access – время коммуникаций при удаленном доступе к данным
  •  Redistribution – время коммуникаций при перераспределении
  •  I/O_comm – время коммуникаций при выполнении операций ввода-вывода
  •  Insufficient_parallelism – общее время потерь из-за недостаточного параллелизма
  •  Insufficient_parallelism_Par – время потерь из-за недостаточного параллелизма при параллельных вычислениях
  •  Insufficient_parallelism_Seq – время потерь из-за недостаточного параллелизма при последовательных вычислениях
  •  Synchronization – время потерь из-за рассинхронизации.
  •  Idle – время простоя процессора
  •  Load_Imbalance – неравномерность загрузки процессоров при параллельных вычислениях
  •  Overlap – общее время перекрытия обменов вычислениями
  •  Reduction_overlap – время перекрытия редукции вычислениями
  •  Shadow_overlap – время перекрытия обновления теневых граней вычислениями

По окончании моделирования для каждого интервала вычисляются интегральные характеристики выполнения программы на данном интервале. Многие из них совпадают по названию и по значению с характеристиками выполнения интервала на каждом процессоре, и определяются путем суммирования значений одноименной характеристики на всех процессорах. Для таких характеристик объяснение их значения опускается. Ниже приведен список характеристик:

  •  Total_time – общее время использования процессоров, то есть произведение Execution_time на число процессоров
  •  Efficiency – коэффициент эффективности, равный отношению Productive_time к Total_time
  •  Execution_time – время выполнения, равное максимальному значению среди времен выполнения данного интервала на каждом процессоре
  •  Productive_timeполезное время, равное сумме Productive_CPU_time и I/O_time
  •  Productive_CPU_timeполезное процессорное время, равное разности CPU_time и Insufficient_parallelism
  •  I/O_time
  •  CPU_time
  •  CPU_time_Par
  •  CPU_time_Seq
  •  Lost_time
  •  Communication
  •  Wait_reduction
  •  Wait_shadow
  •  Remote_access
  •  Redistribution
  •  I/O_comm
  •  Insufficient_parallelism
  •  Insufficient_parallelism_Par
  •  Insufficient_parallelism_Seq
  •  Synchronization
  •  Idle
  •  Load_Imbalance
  •  Overlap
  •  Reduction_overlap
  •  Shadow_overlap

Изменение какой-либо характеристики интервала влечет за собой изменение аналогичной характеристики во всех интервалах, охватывающих данный интервал, на ту же величину.

В старом Предикторе создавалось глобальное дерево интервалов, каждый из которых содержал массив структур, содержащих информацию об указанных выше временных характеристиках для каждого процессора. Поскольку в старой версии трасса интерпретировалась сразу для всех процессоров единовременно, в каждый момент времени существовал только один текущий интервал, текущий параллельный цикл и т.д. В новой схеме, где в один момент времени разные процессоры могут интерпретировать разные места трассы (одни могут обгонять других), понятие «текущий интервал» перестает быть глобальным и должно быть свое для каждого процессора. В связи с этим, архитектура хранения временных характеристик была изменена. Теперь на каждом процессоре создается свое дерево интервалов, каждый из которых содержит информацию только об этом процессоре (а не обо всех, как раньше). Количественно объем данных не изменился, изменилась лишь структура и логика хранения. Теперь, для каждого процессора есть свой указатель на текущий интервал, куда и записываются времена выполнения текущих функций трассы. Алгоритм работы интегрирования информации с разных процессоров и интервалов был изменен в соответствии с новой логической структурой хранения данных.

Моделирование вызовов функций системы поддержки

Для того, чтобы определить роль каждого процессора, его часть распределенных данных, часть вычислений и поведение вообще, необходимо при моделировании проделать те же действия, что делает система поддержки на реальной машине. Это позволит получить информацию о распределенных на данный процессор данных и витках цикла, которая столь необходима для предсказания времени работы. Практически каждой функции системы поддержки, которую можно встретить в трассе выполнения DVM-программы, соответствует своя функция в Предикторе. В старой версии это были методы класса FuncCall, описывавшего запись из трассы о функциональном вызове системы поддержки. В новом Предикторе эти функции являются методами класса CProc, описывающего поведение одного процессора. В старой схеме каждая запись трассы приводила к одному вызову соответствующей функции. При необходимости создавались или изменялись нужные объекты. В новой схеме каждый процессор считывает данную запись из трассы и вызывает соответствующую функцию. В результате, например, функция создания какого-либо объекта вызывается N раз, где N – число процессоров. Поскольку параметры создаваемых объектов одни и те же (т.к. все процессоры читают одну и ту же трассу), то и объект можно создавать в единственном экземпляре, что позволяет существенно экономить память. Для этих целей в классе сервера данных был разработан специальный механизм, позволяющий корректно обращаться с объектами данных.

Все функции системы поддержки с точки зрения их моделирования можно условно разделить на следующие классы:

  •  обычные функции
  •  функции начала/конца интервала
  •  функции ввода/вывода данных
  •  функции, связанные с передачей данных
  •  функции создания/уничтожения объектов
  •  функции распределения ресурсов и данных
  •  функции инициализации коллективных операций
  •  функции выполнения коллективных операций
  •  функции параллельного цикла
  •  неизвестные функции

Обычные функции

Моделирование: время выполнения функции прибавляется к Execution_time и CPU_time_Seq текущего процессора (на котором происходит вызов). Кроме того, к Insufficient_parallelism_Seq процессора прибавляется время, рассчитанное по формуле:

T = Texec / (Nproc - 1)

Данный алгоритм моделирования времени является основным. Далее будем предполагать, что время выполнения  моделируется по этому алгоритму, за исключением тех случаев, когда при описании моделирования функции явно указан отличный от этого алгоритм.

Неизвестные функции

Предиктор может встретить в трассе вызов функции, которая ему не известна. Такие функции считаются обычными и просто вызывается функция моделирования времени обычной функции.

Функции начала/конца интервала

Для функций начала интервала в текущем для данного процессора интервале ищется подинтервал, с параметрами, совпадающими с указанными в трассе (т.е. возможно, акой интервал уже создан). Если такого не находится, то он создается. Если находится, увеличивается его счетчик вхождений (EXE_count). Обновляется указатель на текущий интервал для данного процессора.

Для функций конца интервала указатель на текущий интервал меняется на внешний интервал по отношению к текущему (родительский).

Функции создания объектов

Для большинства объектов, которые должны быть сохранены в памяти, в Предикторе созданы специальные структуры, хранящие ссылку на сам объект и информацию о нем (как минимум, идентификатор). В новом Предикторе все эти структуры являются наследными классами по отношению к структуре CInfo, содержащей самую общую информацию об объекте: идентификатор, и индекс функционального вызова создания объекта. Под индексом подразумевается порядковый номер записи в трассе, содержащей вызов функции системы поддержки на создание данного объекта. Таким образом, объекты, хранящиеся в памяти, характеризуются их идентификатором и порядковым номером функционального вызова из трассы, когда они были созданы. Это вызвано тем, что идентификатор объекта не является уникальным для всей трассы. После того, как объект с таким идентификатором уничтожается, может быть создан другой объект с таким же идентификатором. А поскольку разные процессоры могут в один момент интерпретировать разные фрагменты трассы, это может привести к нежелательной путанице. Когда необходимо создать некоторый объект, происходит обращение к серверу данных на создание структуры, содержащей информацию о данном объекте. Сервер данных ищет в своих таблицах такую структуру, у которой и идентификатор и индекс совпадают с указанными данным процессором (он передает серверу данных не только идентификатор создаваемого объекта, но и текущий индекс –  порядковый номер обрабатываемой записи из трассы). Если такая структура находится, то значит объект уже создан (другим процессором) и ничего делать не надо. В найденной структуре информации об объекте сервер данных увеличивает refcount - число использующих этот объект процессоров. Если же искомая структура не найдена, то она создается (с переданными параметрами), число использующих инициализируется единицей. Моделируемая функция создания объекта в любом случае получает указатель на информационную структуру. Если она была только что создана, то refcount у нее равен 1. иначе – он больше. Если он равен 1, то в памяти создается нужный объект, и в структуру записывается указатель на него. Таким образом, объект создается только один раз. Если какой-то процессор обогнал остальных в интерпретации трассы и создает новый объект с таким же идентификатором, то, поскольку индекс (порядковый номер записи в трассе) будет другой, будет создан другой объект, в результате чего конфликта не возникнет.

Функции изменения объектов

Некоторые функции по ходу своей работы должны изменить хранящийся в памяти объект. Но так как разные процессоры могут находиться на разной стадии интерпретации трассы, то некоторые из них должны видеть объект измененным, а другие – неизмененным.

Предположим, некоторый объект с идентификатором 22 был создан функциональным вызовом с индексом 123. А функциональный вызов трассы с индексом 145 изменяет объект. Пусть  процессор 1 успел проинтерпретировать 150 записей трассы (его текущий индекс трассы = 150), а процессор 2 – только 130. Тогда, обращаясь к серверу данных за объектом с идентификатором 22, первый процессор должен получить измененный объект, а второй – первоначальный. Достигается это за счет применения в сервере данных специального алгоритма поиска: при запросе некоторого объекта передается его идентификатор и текущий индекс трассы (в нашем примере: 150 или 130), в таблицах ищется структура нужного типа с запрашиваемым идентификатором и таким индексом трассы, который был бы максимальным из всех найденных, но не превышал бы текущего индекса (параметра). Тогда для первого процессора с текущим индексом 150 найдется обновленный объект, а для второго – старый. Для этого, функции изменения объектов не просто меняют их, а сначала создают новую копию объекта с текущим индексом трассы, и ее уже меняют. Т.е. в нашем примере при  интерпретации 145-го вызова будет вызвана функция изменения объекта, она найдет объект с индексом 123, создаст его копию с индексом 145 и ее изменит.

Функции удаления объектов

Аналогичным образом, так просто удалять объекты из памяти нельзя, т.к. каким-то процессорам они еще могут понадобиться. Функции удаления объектов обращаются к серверу данных с командой на удаление. Сервер по приведенному выше алгоритму находит нужный объект и уменьшает его refcount – число использующих. Если refcount опускается до нуля, значит данный объект был удален всеми процессорами и его можно действительно удалить из памяти.

Моделирование параллельных циклов

Вычисляется и запоминается общее количество витков цикла (Nвитков) и количество витков цикла на данном процессоре (Ni). Вычисляется величина Тфунк*(Ni/Nвитков) и прибавляется к Execution_time и CPU_time данного процессора. Кроме того, область вычислений процессора сравнивается с областями вычислений других процессоров, вычисляется число процессоров, выполнявших одинаковые витки цикла (Nпроц), потом для каждого процессора, выполнявшего данную часть цикла, вычисляется величина (Тфунк/Ni)*((Nпроц-1)/Nпроц) и прибавляется к Insufficient_parallelism_Par.

Коллективные операции

В старом Предикторе уже были реализованы функции, определяющие для коллективных операций объем пересылок для каждой пары процессоров. При создании объектов, описывающих коллективные операции (например, обмен теневыми гранями массивов), для этих объектов создавалась матрица transfer[i][j] размера N*N, где N – число процессоров, содержащая количество байт, которое должно быть передано с процессора i на процессор j. Вычисление же времени выполнения обменов происходило по довольно грубой схеме. Новый предиктор также создает необходимые объекты и заполняет матрицу transfer, но для определения времени, которое потратит данный процессор на данную коллективную операцию, используется библиотека предсказания времен выполнения функций MPI. Функции коллективных операций в системе поддержки обычно делятся на две группы: запуска коллективной операции и ожидания ее заверения. Моделирование запуска операции сводится к серии вызовов методов IRecv и ISend коммуникационной системы в соответствии с матрицей transfer[i][j]. Моделирование ожидания коллективной операции сводится к вызову функции Waitall. Так как данная функция не записывает нужного значения времени выполнения до тех пор, пока не будут выполнены все ожидаемые обмены, время выполнения ожидания завершения коллективной операции не может быть определено до тех пор, пока все участвующие процессоры не выполнят соответствующей операции запуска коллективного обмена. В случае, когда время выполнения еще не определено, в указанную в параметрах Waitall принимающую переменную записывается -1. В этом случае данный процессор не переходит к следующему шагу, а остается на этом. В результате, главный цикл моделирования обращается к другим процессорам делать их шаги, они выполняют запуск коллективной операции, и в определенный момент данный процессор получает искомое значение времени выполнения и переходит к следующему шагу.


Заключение

В результате проведенной работы была создана библиотека функций предсказания времен выполнения вызовов MPI, моделирующая работу более 30 часто используемых функций стандарта MPI, повторяющая поведение реализации MPI MPICH на нескольких типах сетей (одно- и двухпроцессорные узлы с сетью типа Ethernet или Myrinet).

Библиотека была выполнена в виде класса на языке С++ с объемом кода около 1300 строк.

Кроме этого, была создана новая версия Предиктора, использующая вышеуказанную библиотеку, и работающая по совершенно новой схеме. Новая версия создавалась с нуля как новая программа, сначала был создан скелет, реализующий новую логику работы, а затем постепенно он заполнялся за счет переработанных текстов старого Предиктора. Суммарный объем кода старого Предиктора – 14530 строк. Объем кода нового предиктора – 13982 строк, включая 4618 строк совершенно нового либо значительно переделанного  кода.


Литература

  1.  DVM-система. http://www.keldysh.ru/dvm/
  2.  Н.А.Коновалов, В.А.Крюков, А.А.Погребцов, Ю.Л.Сазанов.  “С-DVM - язык разработки мобильных параллельных программ”. Препринт ИПМ им. М.В.Келдыша РАН №86, 1997.
  3.  В.Е.Денисов, В.Н.Ильяков, Н.В.Ковалева, В.А.Крюков. "Отладка эффективности DVM-программ". Препринт ИПМ им. М.В.Келдыша РАН №74, 1998.
  4.  “MPI: A Message-Passing Interface Standard version 1.1”. 1995, University of Tennessee.
  5.  William Gropp, Ewing Lusk et al. “A High-Performance, Portable Implementation of the MPI Message Passing Interface Standard”, Argonne National Laboratory, Mississippi State University, 1996.
  6.  “Myrinet-on-VME Protocol Specification Draft Standard VITA 26-199x Draft 1.1 31 August 1998“.


   MPI

Ethernet

yrinet

CComSys

CNetwork

CNetworkEthernet

CNetworkMyrinet

Другие данные

Коммуникационная система

(CComSys)

Трасса

Сервер данных (CDataServer)

… Процессоры

(CProc)

П4

П3

П2

П1

П0

Главный цикл (Run())


 

А также другие работы, которые могут Вас заинтересовать

78912. Специфика объекта СГП 21.5 KB
  Вовторых в структуру и содержание объекта социальногуманитарного познания с необходимостью входит субъект познания. Объективация предмета познания оказывается в этом случае неполной и сопряжена с большими методологическим трудностями. Втретьих исследование объекта осуществляется в социальногуманитарном знании с ценностных позиций поскольку субъект познания будучи сам частью социальной системы оказывается нагруженным идеологическими предпосылками предрассудками некритически воспринятыми установками и т.
78913. Социокультурная обусловленность дисциплинарной структуры социально-гуманитарного знания 25 KB
  Прежде всего речь идет о различении социальных наук как наук об обществе и гуманитарных наук как наук в фокусе которых находится человек индивидуальная и социальная психология этика и т. Разделение наук по предмету о чем речь уже шла выше. Разделение наук по методу: в социальных науках используется метод объяснения тогда как в гуманитарных базовой методологической процедурой выступает понимание сразу же заметим что такое разделение грешит противопоставлением понимания объяснению. Разделение наук одновременно по предмету и методу...
78914. Конвергенция естественно-научного и СГН в современой науке 24 KB
  Логику развития методологии гуманитарного познания можно представить следующим образом: сначала проблематика методологии гуманитарных наук развивалась в направлении выявления и обоснования их специфики по сравнению с науками о природе. Главной на этом этапе является проблема идентификации социальногуманитарных наук и их демаркации от наук естественных. Обоснованию специфики социальногуманитарного познания посвящены работы Дильтея Описательная психология Гадамера Истина и метод Фуко Слова и вещи Рикера Герменевтика и...
78915. Специфика научной картины мира в СГН 31.5 KB
  Специфика научной картины мира в СГН Научная картина мира исторична она опирается на достижения науки конкретной эпохи в пределах тех знаний которыми располагает человечество. Научная картина мира представляет собой синтез научных знаний соответствующих конкретноисторическому периоду развития человечества. Поэтому она более строгое понятие чем образ мира или видение мира. В научную картину мира входят знания отвечающие критериям научности.
78916. Специфика субъекта СГП 34 KB
  В сфере познания субъект определяет предмет исследования выделяя его как некий срез противостоящего ему объекта а также выстраивает концептуальную и эмпирическую модели познаваемого предмета. В современном познании субъект проектирует ряд условий познания данного предмета проходит основные этапы процесса познания опираясь на те методы которые в наибольшей степени соответствуют характеристикам и самой природе познаваемого объекта. Субъектами социального и гуманитарного познания могут быть как индивиды отдельные исследователи...
78917. Кантовские представления о диалектике теоретического и практического разума 27 KB
  Правда на сами эти предпосылки Кант не покушается: более того он увековечивает их как прирожденные свойства разума. Резкий метафизический разрыв теоретического и практического разума опытных и априорных суждений анализа и синтеза общего и единичного целого и части – весь комплекс противоречий к которым неизбежно приходит метафизическое мышление Кант выставил перед философией как решающую проблему. Их можно только мыслить как условия возможности и науки и нравственности как гарантии теоретического и...
78918. Принципы логики социальных наук Поппера 47.5 KB
  Именно поразительный прогресс естественных наук о котором идет речь в моем первом тезисе постоянно напоминает нам о нашем незнании даже в области естественных наук...
78919. Социокультурное и гуманитарное содержание понятие жизни 26.5 KB
  Все его творения происходят из неспособности создать привычными средствами жизни и на основе ее эволюционных законов живое существо которое превосходило бы человека. Шелер называет странной пессимистичной ложной оказывается однако логически строго последовательной если по объяснению автора разделять дух соответственно разум и жизнь как два метафизических начала но при этом отождествлять дух с техническим интеллектом интеллектом лишенным мудрости а ценности жизни делать высшими ценностями. Фазы...
78920. История как одна из форм проявления жизни 28.5 KB
  История как одна из форм проявления жизни. Фазы развития этой болезни жизни которая зовется человеком в структурном отношении те же самые какие проходят все стареющие и умирающие существа: прогрессирующее преодоление жизненной силы посредством автономизации механизмов которые сам организм высвобождает из себя по мере старения. История общества по Зиммелю есть история нарастающей интеллектуализации рационализации социальной жизни и углубления влияния принципов денежных отношений. Анализу этих форм Зиммель посветил книгу Философия...