929

Методы программирования

Конспект

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

Моделирование и анализ параллельных вычислений. Описание схемы выполнения параллельного алгоритма. Программирование параллельных алгоритмов. Структура параллельной программы с использованием MPI. Передача данных от одного процесса всем процессам программы. Организация неблокирующих обменов данными между процессами. Факторы, влияющие на производительность, и способы ее повышения. Режимы параллельных вычислений с общей памятью. Обзор средств параллельного и распределенного программирования.

Русский

2015-01-15

2.94 MB

314 чел.

Содержание.

Введение 4

Лекция 1 7

Моделирование и анализ параллельных вычислений 7

Модель вычислений в виде графа "операции – операнды 8

Описание схемы выполнения параллельного алгоритма 9

Определение времени выполнения параллельного алгоритма 10

Правила разработки алгоритмов 12

Лекция2 12

Программирование параллельных алгоритмов 12

Технология MPI 13

Введение в библиотеку MPICH 14

Структура параллельной программы с использованием MPI 15

Передача/прием сообщений между отдельными процессами 16

Лекция 3 20

Использование модульной структуры 21

Определение времени выполнения программ 21

Контроль выполнения программ 22

Передача данных от одного процесса всем процессам программы. 23

Пример использования широковещательной рассылки 24

Лекция 4 26

Передача данных от всех процессов одному процессу 26

Пример коллективного вызова (без обмена) 27

Аварийное завершение параллельной программы 28

Оценка коммуникационных затрат для  кластерных систем 28

Режимы передачи данных MPI 29

Лекция 5 31

Организация неблокирующих обменов данными между процессами 32

Одновременное выполнение передачи и приема 34

Группа процессоров и коммутаторов 35

Показатели эффективности в параллельных алгоритмах 40

Модельная задача – вычисление частных сумм 42

Последовательный алгоритм суммирования 42

Лекция 6 43

Каскадная схема суммирования 43

Каскадная схема с асимптотически ненулевой эффективность 45

Построение частичных сумм 46

Оценка максимального параллелизма 47

Анализ масштабируемости параллельных вычислений 50

Верхняя граница времени выполнения параллельного алгоритма 51

Факторы, влияющие на производительность, и способы ее повышения 52

Лекция 7 53

Принципы разработка параллельных алгоритмов 53

Моделирование при проектировании параллельных алгоритмов 55

Этапы разработки параллельных алгоритмов 58

Умножение матриц при ленточной схеме разделения данных 66

Лекция 8 69

Параллельное решение систем линейных уравнений 69

Построение параллельного алгоритма 73

Масштабирование и распределение подзадач по процессорам. 74

Анализ эффективности 75

Лекция 9 76

Параллельные методы сортировки 76

Принципы распараллеливания 77

Масштабирование параллельных вычислений 78

Пузырьковая сортировка 80

Алгоритм чет-нечетной перестановки 80

Определение подзадач и выделение информационных зависимостей 81

Масштабирование и распределение подзадач по процессорам 83

Анализ эффективности 83

Лекция 10 85

Параллельные вычисления при решении задач на графах 85

Программная реализация параллельного алгоритма Флойда 87

Определение подзадач 89

Анализ эффективности 89

Построение минимального остова. Выделение подзадач 90

Анализ информационных связей 91

Лекция 11 91

PVM (Параллельные виртуальные машины) 91

Работа PVM 94

Структура идентификатора TD 95

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

Настройка PVM 95

Пример простейшей программы 96

Лекция 12 97

Структура программы PVM 97

Выводы по PVM 98

Выводы по PVM: Классификация вычислительных систем 98

Алгоритмы предварительного распределения данных (графы) 99

Режимы параллельных вычислений с общей памятью 100

Основные обозначения псевдокода 101

Распределение данных в EREW 102

Лекция 13 103

Параллельное программирование с использованием общей памяти 103

Многопоточное программирование 103

Спецификация POSIX Threads 104

Пример программы с использованием POSIX Threads 104

Механизмы синхронизации потоков 106

Лекция 14 107

Среда Open MP 107

Основные компоненты 108

Модель выполнения программы 109

Модель памяти 110

Структура программы 110

Опции. Основные правила 111

Синхронизация 112

Лекция 15 113

Обзор средств параллельного и распределенного программирования 113

Литература 115

Введение

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

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

Можно выделить следующий ряд общих проблем, возникающих при использовании параллельных вычислительных систем:

  1.  Потери производительности для организации параллелизма - согласно гипотезе Минского, ускорение, достигаемое при использовании параллельной системы, пропорционально двоичному логарифму от числа процессоров (т.е. при 1000 процессорах возможное ускорение оказывается равным 10).

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

  1.  Существование последовательных вычислений - в соответствии с законом Амдаля ускорение процесса вычислений при использовании p процессоров ограничивается величиной:

S≤1/(f+(1-f)/p) ,

где f есть доля последовательных вычислений в применяемом алгоритме обработки данных (т.е., например, при наличии всего 10% последовательных команд в выполняемых вычислениях эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных).

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

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

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

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

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

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

Проблематика параллельных вычислений является чрезвычайно широкой областью теоретических исследований и практически выполняемых работ и обычно подразделяется на следующие направления деятельности:

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

Лекция 1

Моделирование и анализ параллельных вычислений.

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

Эффективность оценивается в нескольких терминах, главным из которых является «ускорение»:

- Ускорение по отношению к конкретному последовательному алгоритму (оценка эффективности распараллеливания конкретного алгоритма).

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

Модель вычислений в виде графа "операции – операнды"

Данная модель может использоваться для описания существующих

информационных зависимостей в выбираемых алгоритмах решения задач.

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

  •  Граф не имеет контуров.
  •  V- множество вершин (операции)
  •  U - множество ребер (информационные зависимости)
  •  Множество ориентированных дуг – зависимость операций от результатов предыдущих операций.
  •  Предполагается, что выполнение каждой операции =1, а передача данных осуществляется мгновенно.

Примеры:

S=(x2-x1)*(y2-y1)= x2 *y2 - x2 *y1 – x1 *y2 + x1 *y1

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

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

Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).

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

Пример: операции  (*) могут выполняться параллельно.

Пусть имеется p процессов, тогда для параллельного выполнения вычислений необходимо задать множество (расписание) :

Hp = {(i, pi, ti)} ,

в котором для каждой операции i Є V указывается номер используемого для выполнения операции процессора pi и время начала выполнения операции ti. Завершение операции происходит в момент ti+1.

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

  1.  Для i, j Є V если ti=tjpipj , т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент;
  2.  Для i, j Є V если дуга (i, j) Є Uti ti+1, т.е. к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены.

Определение времени выполнения параллельного алгоритма. 

Вычислительная схема алгоритма G совместно с расписанием Hp может рассматриваться как модель параллельного алгоритма Ap(G,Hp), исполняемого с использованием p процессоров.

  •  Время выполнения параллельного алгоритма определяется максимальным значением времени, применяемым в расписании

Tp(G, Hp) =

  •  Для выбранной схемы вычислений желательно использование расписания, обеспечивающего минимальное время исполнения алгоритма:

Tp(G) =  

  •  Уменьшение времени выполнения может быть обеспечено и путем подбора наилучшей вычислительной схемы:

  Tp =  

Все оценки могут быть получены для разного числа процессов.

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

T∞ = – минимально возможное время выполнения параллельного алгоритма при использовании неограниченного количества процессоров.

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

T1 = - при оптимальном выборе модели.

  •  Время решения различных задач на одном процессоре различается.

T1* = min T1 – наиболее быстрый из последних алгоритмов, где операция минимума берется по множеству всех возможных последовательных алгоритмов решения данной задачи.

Обозначим: d(G) — диаметр (длина максимального пути) графа.

Теорема 1.

Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма, т.е.

T∞ (G) = d (G)

Теорема 2. 

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

T∞ (G)≥

Где n -  число вершин ввода.

Теорема 3.

При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров:

q=cp , где c<1 (>0) ⟹ TpcTq

Теорема 4.

Для числа процессоров справедлива следующая оценка:

Tp < (T∞ + T1/p)

Теорема 5.

Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T∞, можно достичь при количестве процессоров порядка p  ~T1/T∞, а именно:

Если pT1/ T∞, то Tp2T∞.

При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в 2 раза наилучшее время вычислений при имеющемся числе процессоров:

Если p< T1/ T∞, то T1/p Tp ≤2 T1/p

Правила разработки алгоритмов.

  1.  Схема графа должна быть выбрана таким образом, чтобы его диаметр был бы минимальным.

d(G)  min

  1.  Целесообразно выбирать число процессоров следующим образом:

p  T1/T.

  1.  Для времени выполнения алгоритма с использованием p процессоров выполняются ограничения рассмотренных соотношений.

Лекция 2

Программирование параллельных алгоритмов.

  1.  Существуют подходы, основанные на специальных языках программирования
  2.  Расширение обычных языков программирования (последовательное программирование)
  3.  Использование специальных библиотек. Этот способ нашел наибольше распространение для программирования распределенных вычислений. Программы, реализующиеся для кластеров. Здесь используются уже существующие компоненты + дополнительные библиотеки.

Наибольшее распространение получили:

  1.  Технология MPI (Message Passing Interface – интерфейс передачи сообщений) . Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу.
  2.  Технология PVM (Parallel Virtual Machine - виртуальная параллельная машина)

      Главное отличие: PVM позволяет более гибко управлять параллельными процессами. MPI такой гибкости не достигла.

Технология MPI.

Разработана в середине 90-х годов. Основная идея: порождение нескольких процессов. Программа реализуется параллельно в виде вызова функции специальной библиотеки. Проблемы переносимости практически нет. Технология MPI снижает сложность разработки. Стандарт  MPI  фиксирует   интерфейс,   который   должен соблюдаться   как   системой   программирования   на   каждой   вычислительной платформе, так и пользователем при создании своих программ. Современные реализации, чаще всего, соответствуют стандарту MPI версии 1.1. В 1997—1998   годах   появился   стандарт   MPI-2.0,   значительно   расширивший функциональность предыдущей версии. Однако до сих пор этот вариант MPI не получил широкого распространения и в полном объеме не реализован ни на одной системе. MPI   поддерживает   работу   с   языками  Фортран   и  Си.

Все дополнительные объекты:  имена процедур,  константы,  предопределенные типы данных и т.п.,  используемые  в MPI,  имеют  префикс  MPI_.  Если пользователь не будет использовать в программе имен с таким префиксом, то конфликтов с объектами MPI заведомо не будет. В языке Си, кроме того, является существенным регистр символов в названиях функций. Обычно в названиях функций MPI первая буква после префикса MPI_ пишется в верхнем регистре, последующие буквы – в нижнем регистре, а названия констант MPI записываются целиком в верхнем регистре.  Все описания интерфейса  MPI собраны в файле  mpif.h  (mpi.h).

Наиболее практической библиотекой является MPICH (англ. «Message Passing Interface Chameleon») — это одна из самых первых разработанных библиотек MPI.

Введение в библиотеку MPICH.

Библиотека вызывается из программы и представляет собой набор функций. Достаточно использовать 6 функций. Основные:

  1.  MPI_INIT (INTEGER IERR) (init arg с, char *arg v[]) Инициализация параллельной части программы. Все другие процедуры MPI могут быть вызваны только после вызова  MPI_INIT.  Инициализация параллельной части для каждого приложения должна выполняться только один раз. В языке Си функции MPI_Init передаются указатели на аргументы командной строки программы argc и argv, из которых системой могут извлекаться и передаваться  в параллельные  процессы некоторые  параметры  запуска программы.
  2.  MPI_FINALIZE (INTEGER IERR).  Завершение параллельной части приложения. Все последующие обращения к любым процедурам MPI, в том числе к MPI_INIT, запрещены. К моменту вы-зова MPI_FINALIZE каждым процессом программы все действия, требующие его участия в обмене сообщениями, должны быть завершены.

Общая схема MPI-программы на языке Си выглядит примерно следующим образом:

#include “mpi.h”

main(int argc, char **argv)

{

MPI_Init(&argc, &argv);

MPI_Finalize();

}

  1.  MPI_INITIALIZED(FLAG, IERR)

LOGICAL FLAG

INTEGER IERR. Процедура возвращает в аргументе  FLAG  значение  .TRUE.,  если вызвана из параллельной части приложения, и значение .FALSE.  - в противном случае. Это   единственная   процедура   MPI,   которую   можно  вызвать   до   вызова MPI_INIT.

  1.  MPI_COMM_SIZE(COMM, SIZE, IERR)

INTEGER COMM, SIZE, IERR. В аргументе  SIZE  процедура возвращает число параллельных процессов в коммуникаторе COMM.

  1.  MPI_COMM_RANK(COMM, RANK, IERR)

INTEGER COMM, RANK, IERR. В аргументе  RANK  процедура возвращает номер процесса в коммуникаторе COMM.  Если   процедура  MPI_COMM_SIZE  для   того  же   коммуникатора  COMM вернула   значение  SIZE,   то   значение,   возвращаемое   процедурой MPI_COMM_RANK через переменную RANK, лежит в диапазоне от 0 до SIZE-1.

Структура параллельной программы с использованием MPI:

#include “mpi.h”

int main(int argc, char argv[])

 {

       int ProcNum, ProcRank;    //ProcRank-идентификатор данного процесса //

             <код без MPI>

MPI_Init(&argc, &argv);

     MPI_COMM_SIZE(MPI_COMM_WORLD, & ProcNum);  

 // MPI_COMM_WORLD – коммутатор по умолчанию, ProcNum- размер коммутатора //

     MPI_COMM_RANK(MPI_COMM_WORLD, & ProcRank);

// ProcRank хранит ранг процесса, который этот вызов произвел //

                <код с использованием MPI>

 MPI_Finalize();

<код без MPI>

return 0;

}

Передача/прием сообщений между отдельными процессами.

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

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

Передача/прием сообщений с блокировкой:

  •  MPI_SEND(void *BUF, int COUNT, MPI_DATATYPE type, int DEST, int TAG, MPI_COMM comm)

 Блокирующая посылка массива  BUF  с идентификатором MSGTAG,  состоящего из COUNT элементов типа DATATYPE, процессу с номером DEST в коммуникаторе COMM. Все элементы посылаемого сообщения должны быть расположены подряд в буфере BUF. Операция начинается независимо от того, была ли инициализирована   соответствующая   процедура   приема.  При   этом  сообщение может быть скопировано как непосредственно в буфер приема,  так и помещено в некоторый системный буфер (если это предусмотрено в MPI). Значение COUNT может быть нулем. Процессу разрешается передавать сообщение самому себе, однако это небезопасно и может привести к возникновению ту-пиковой ситуации. Параметр DATATYPE имеет в языке Фортран тип INTEGER (в языке Си – предопределенный тип MPI_Datatype).

Предопределенные типы данных:

Тип данных в MPI

Соответствие

MPI_BYTE

8 бит, используется для передачи

нетипизированных данных

MPI_CHAR

                                CHAR

MPI_DOUBLE

                    DOUBLE

MPI_FLOAT

  FLOAT

MPI_INT

                     INT

MPI_LONG

                                 LONG

           MPI_LONG_DOUBLE

                                 LONG DOUBLE

MPI_PACKED

тип для упакованных данных

MPI_SHORT

                                  SHORT

MPI_UNSIGNED

                                  UNSIGNED INT

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

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

Следует специально отметить, что возврат из процедуры MPI_SEND не означает ни того, что сообщение получено процессом DEST, ни того, что сообщение покинуло процессорный элемент, на котором выполняется процесс, выполнивший   данный   вызов.  Предоставляется   только   гарантия   безопасного изменения   переменных, использованных   в   вызове   данной   процедуры.

MPI предоставляет следующие модификации процедуры передачи данных с блокировкой MPI_SEND:

  •  MPI_BSEND  — передача   сообщения  с   буферизацией.  Если   прием  посылаемого   сообщения   еще   не   был   инициализирован   процессом-получателем,   то  сообщение  будет   записано в  специальный буфер,  и произойдет немедленный возврат из процедуры.  Выполнение данной процедуры никак не зависит от соответствующего вызова процедуры приема   сообщения.   Тем   не   менее,   процедура   может   вернуть   код ошибки, если места под буфер недостаточно. О выделении массива для буферизации должен заботиться пользователь.
  •  MPI_SSEND — передача сообщения с синхронизацией. Выход из данной процедуры   произойдет   только   тогда,   когда   прием   посылаемого сообщения   будет   инициализирован   процессом-получателем.   Таким образом,  завершение передачи с синхронизацией говорит не только о возможности   повторного   использования   буфера   посылки,   но   и   о гарантированном   достижении   процессом-получателем   точки   приема сообщения   в   программе.   Использование   передачи   сообщений   с синхронизацией   может   замедлить   выполнение   программы,   но позволяет   избежать   наличия   в   системе   большого   количества   не принятых буферизованных сообщений.
  •  MPI_RSEND — передача сообщения по готовности. Данной процедурой можно пользоваться только в том случае, если процесс-получатель уже инициировал прием сообщения. В противном случае вызов процедуры, вообще   говоря,   является   ошибочным и  результат   ее   выполнения  не определен.   Гарантировать   инициализацию  приема   сообщения   перед вызовом   процедуры  MPI_RSEND  можно   с   помощью   операций, осуществляющих   явную   или   неявную   синхронизацию   процессов (например,  MPI_BARRIER  или  MPI_SSEND).   Во   многих   реализациях процедура  MPI_RSEND  сокращает   протокол   взаимодействия   между отправителем   и   получателем,   уменьшая   накладные   расходы   на организацию передачи данных.
  •  MPI_SEND(void *BUF, int COUNT, MPI_DATATYPE type, int SOURCE, int TAG, MPI_COMM comm, MPI_ STATUS *status)

Блокирующий прием в буфер BUF не более COUNT элементов сообщения типа

DATATYPE с идентификатором MSGTAG от процесса с номером SOURCE в ком-

муникаторе COMM с заполнением массива атрибутов приходящего сообщения

STATUS. Если число реально принятых элементов меньше значения COUNT, то

гарантируется,   что   в   буфере  BUF  изменятся   только   элементы,

соответствующие   элементам   принятого   сообщения.   Если   количество

элементов в принимаемом сообщении больше значения COUNT, то возникает

ошибка   переполнения.  Типы данных должны совпадать с MPI_SEND и MPI_RECV.

При приеме сообщения вместо аргументов SOURCE и TAG можно использовать следующие предопределенные константы:

  •  MPI_ANY_SOURCE — признак того,  что подходит сообщение от любого

процесса;

  •  MPI_ANY_TAG — признак   того,   что   подходит   сообщение   с   любым

             идентификатором.

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

Реальные   атрибуты   принятого   сообщения   всегда   можно   определить   по соответствующим элементам массива  status. В Фортране параметр status является   целочисленным   массивом   размера  MPI_STATUS_SIZE.  Константы  MPI_SOURCE, MPI_TAG и MPI_ERROR являются индексами по данному массиву для доступа к значениям соответствующих полей:

status(MPI_SOURCE) — номер процесса-отправителя сообщения;

status(MPI_TAG) — идентификатор сообщения;

• status(MPI_ERROR) — код ошибки.

В языке Си параметр  status  является структурой предопределенного типа

MPI_Status с полями MPI_SOURCE, MPI_TAG и MPI_ERROR.

Программа:

int main (…)

 {

    int ProcNum; ProcRank; RecvRank;

      MPI_Status; MPI_Init (…);

           MPI_COMM_SIZE(MPI_COMM_WORLD, & ProcNum);

             MPI_COMM_RANK(MPI_COMM_WORLD, & ProcRank);

     if (ProcRank==0)  {print (“\n Выполняется процесс %3d”, ProcRank);

           for (i=1, i< ProcNum, i++)

                 {MPI_Recv (& RecvRank, 1, MPI_INT, MPI_ANY_SOURCE,         MPI_ANY_TAG, MPI_COMM_WORLD, & Status);

         print f  (“\n Получено сообщение от процесса % 3d “, RecvRank);  }}//

end if else MPI_Send (&ProcRank, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);

MPI_Finalize ();

return 0;

}

Лекция 3

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

MPI_Recv( &RecvRank, 1, MPI_INT i, MPI_ANY_TAG, MPI_COM_WORLD, &Status)

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

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

Использование модульной структуры.

Этот способ является традиционным способом борьбы со сложными структурами.

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

MPI_Comm_rank( MPI_COMM_WORLD, &ProcNum );

if (ProcNum==0) DoProc0();

elseif (ProcNum==1) DoProc1();

elseif (ProcNum==2) DoProc2();

Определение времени выполнения программ.

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

Получение текущего момента времени обеспечивается при помощи функции:

double MPI_Wtime(void),

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

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

double t1, t2, dt;

t1 = MPI_Wtime();

……………………

t2 = MPI_Wtime();

dt = t2 – t1;

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

double MPI_Wtick(void),

позволяющая определить время в секундах между двумя последовательными показателями времени аппаратного таймера примененной компьютерной системы.

Контроль выполнения программ.

Все вызовы библиотеки MPI возвращают код завершения, который может быть обработан. Wtime, Wtick – исключения.

Код завершения при успехеMPI_SUCCESS

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

  •  MPI_ERR_BUFFER – неверный указатель на буфер
  •  MPI_ERR_TRUNCATE – неверное по объему сообщение
  •  MPI_ERR_COMM – неверный компилятор
  •  MPI_ERR_RANK – неверный ранг процессора

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

Передача данных от одного процесса всем процессам программы.

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

MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);

for (int i = 1; i < ProcNum; i++)

MPI_Send(&x, n, MPI_DOUBLE, i, 0, MPI_COMM_WORLD);

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

Достижение эффективного выполнения операции передачи данных от одного процесса всем процессам программы ( широковещательная рассылка данных ) может быть обеспечено при помощи функции MPI:

int MPI_Bcast(void *buf, int count, MPI_Datatype type, int root,

 MPI_Comm comm),

где

buf, count, type — буфер памяти с отправляемым сообщением (для процесса с рангом 0 ) и для приема сообщений (для всех остальных процессов );

root — ранг процесса, выполняющего рассылку данных;

comm — коммуникатор, в рамках которого выполняется передача данных.

Функция MPI_Bcast осуществляет рассылку данных из буфера buf, содержащего count элементов типа type, с процесса, имеющего номер root, всем процессам, входящим в коммуникатор comm.

Следует отметить:

  •  функция MPI_Bcast определяет коллективную операцию, и, тем самым, при выполнении необходимых рассылок данных вызов функции MPI_Bcast должен быть осуществлен всеми процессами указываемого коммуникатора.
  •  указываемый в функции MPI_Bcast буфер памяти имеет различное назначение у разных процессов: для процесса с рангом root, которым осуществляется рассылка данных, в этом буфере должно находиться рассылаемое сообщение, а для всех остальных процессов указываемый буфер предназначен для приема передаваемых данных;
  •  все коллективные операции "несовместимы" с парными операциями — так, например, принять широковещательное сообщение, отосланное с помощью MPI_Bcast, функцией MPI_Recv нельзя, для этого можно задействовать только MPI_Bcast.

Как распознать кто получатель,  а кто отправитель?

  •  Если указан root – это ранг отправителя
  •  Если ранг совпадает с рангом root – отправитель
  •  Если нет – получатель.

Пример использования широковещательной рассылки:

Параллельная программа суммирования числовых значений.

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include "mpi.h"

int main(int argc, char* argv[]){

double x[100], TotalSum, ProcSum = 0.0;

int  ProcRank, ProcNum, N=100, k, i1, i2;

MPI_Status Status;

// Инициализация

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD,&ProcNum);

MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank);

// Подготовка данных

if ( ProcRank == 0 ) DataInitialization(x,N);

// Рассылка данных на все процессы

MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

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

// на каждом процессе суммируются элементы вектора x от i1 до i2

 k = N / ProcNum;

i1 = k *   ProcRank;

i2 = k * ( ProcRank + 1 );

if ( ProcRank == ProcNum-1 ) i2 = N;

for ( int i = i1; i < i2; i++ )

  ProcSum  = ProcSum + x[i];

// Сборка частичных сумм на процессе с рангом 0

 if ( ProcRank == 0 ) {

  TotalSum = ProcSum;

  for ( int i=1; i < ProcNum; i++ ) {

    MPI_Recv(&ProcSum,1,MPI_DOUBLE,MPI_ANY_SOURCE,0, MPI_COMM_WORLD, &Status);

    TotalSum = TotalSum + ProcSum;

  }

}

else // Все процессы отсылают свои частичные суммы

  MPI_Send(&ProcSum, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);

// Вывод результата

if ( ProcRank == 0 )

  printf("\nTotal Sum = %10.2f",TotalSum);

 MPI_Finalize();

return 0;

}

Лекция 4

Передача данных от всех процессов одному процессу. Операция редукции.

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

int MPI_Reduce (void *sendbuf, void *recvbuf, int count, MPI_Datatype  type,

MPI_Op op,  int root, MPI_Comm  comm);

где,

 recvbuf – буфер принимаемого сообщения;   

count- длина буфера

MPI_Op- операция при получении сообщения

Функция MPI_Reduce минимизирует затраты.

Основные операции при приеме сообщений при вызове Reduce:

MPI_SUM

MPI_PROD           для целых или вещественных int, float

MPI_MIN
MPI_MAX

Логические операции:

MPI_LAND – конъюнкция

MPI_LOR – дизъюнкция                            целые операнды int

MPI_LXOR – исключающее или

Побитовые операции (разрядные):

MPI_BAND

MPI_BOR             int, byte

MPI_BXOR

Операции выполняются над всеми элементами сообщения.

Если в сообщении два элемента, то отдельно суммируются первые элементы каждого сообщения и отдельно вторые элементы каждого сообщения.

MPI_Reduce (&ProcSum, &TotalSum, 1, MPI_DOUBLE, MPI_SUM, o, MPI_COMM_WORLD);

где о – ранг (root) получателя.

Чем больше процессов участвуют в обмене, тем больше разница между обменом точка-точка и коллективным вызовом Reduce.  Reduce – вызов коллективного обмена, поэтому все процессы, указанные в Reduce коммутатора, должны выполнить этот вызов.

Пример коллективного вызова (без обмена)- коллективная синхронизация.

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

 

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

Рекомендация: выполнять аварийные завершения.

Аварийное завершение параллельной программы

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

int MPI_Abort (MPI_COMM comm, int errcode)            или   

MPI_ERR_OTHER  - это корректное завершение программы

---------------------------------------------------------------------------------------

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

int MPI_Get_count (MPI_Status *status, MPI_Datatype, int * count);

Оценка коммуникационных затрат для  кластерных систем.

Независимые компоненты, подключение к локальной сети.  Модель этих затрат зависит от протокола. Все сообщения разбиваются на пакеты и передаются.

Для протоколов TCP/IP

Модель А.

А:  tng (m)=+ m * + ,

где :

 tng (m) – время передачи данных,

  - начальная подготовка const,

  – служебная информация const,

B:    =        + m* +(m+ )*,  n=1

                       + ( - )* +(m+ )* , n>1

где:

n –число передаваемых пакетов

(m+ ) )* – время передачи данных

  (708 байт) – число байт, служебных в пакете(одном)                                                                

(1500 байт) – максимальный размер пакета                                                                                

m* – (m-количество байтов) время подготовки и передачи данных.

Некоторые действия могут быть совмещены со временем. Время начальной подготовки не может быть больше 1.

С: Хокни  tng (m)=+ m *

 

если определить, то можно контролировать время передачи

β=R=  - пропускная способность,   α=

Время подготовки определяется с помощью передачи сообщения минимальной длины.

Для определения пропускной способности передается сообщение максимальной длины.

При пересылке сообщения в 2000 байт, время (его погрешность), при повторении этого опыта много раз. Погрешность в процентах.

Байт

А

В

С

2000

…..

2*

…..

5*

33,45

8,44

5,91

7,93

0,44

1,21

34,8

8,41

6,05

Режимы передачи данных MPI.

Реализуется в стандартном режиме, т.е. процесс –отправитель блокируется, после завершения можно использовать буфер опять, возможные состояния сообщения:

принадлежность процессу-отправителю;

состояние передачи;

принадлежность процессу-получателю;

принято, завершится после Recv;

Синхронный вызов:

MPI_Send   Стандартный(Standart):

–обеспечивается функциейMPI_Send,

–на время выполнения функции процесс-отправитель сообщения блокируется,

–после завершения функции буфер может быть использован повторно,

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

MPI_Ssend Синхронный (Synchronous) режим–завершение функции отправки сообщения происходит только при получении от процесса-получателя подтверждения о начале приема отправленного сообщения.

MPI_Rsend – самый быстрый вариант обмена, выполнится, если к моменту вызова инициирована   операция приема сообщения ( если Recv не вызван, то Rsend считается ошибкой)

MPI_Bsend – завершится во всех случаях, если неинициирована, в буфер помещает сообщение и завершается, если инициирована операция приема - просто завершится, так как сообщение передано. Для его использования нужно создать буфер:

int MPI_Buffer_attach (void*buf, int size)

выделить память

  int MPI_Buffer_detech (void*buf, int size)

 

                                  очистить память 

Режимы передачи данных

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

Лекция 5

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

  1.  int MPI_Pac_size(int count, MPI_Datatype type, MPI_Comm comm, int *size );  - функция возвращает размер буфера.

+ предопределенная константа (к длине буфера)

MPI_BSEND_OVERHEAD – служебная область сообщений.

Необходимо учесть: в буфере могут располагаться несколько сообщений.

  1.  Распределение памяти под буфер.

malloc, calloc.

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

int MPI_Buffer_attach(void *buf, int size),

где

buf — адрес буфера памяти;

size — размер буфера.

  1.  Перессылки (использование буфера).
  2.  После завершения работы с буфером он должен быть отключен от MPI при помощи функции:

int MPI_Buffer_detach(void *buf, int *size),

где

buf — адрес буфера памяти;

size — возвращаемый размер буфера.

  1.  Освобождение памяти.

free();

Используя соответствующие режимы Bsend, Rsend можно исключить задержки, блокировки процесса-отправителя не будет.

Если запрос на прием выполнен, а сообщение не передано, то процесс получателя блокируется – MPI_Recv.

Организация неблокирующих обменов данными между процессами

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

MPI обеспечивает возможность неблокированного выполнения операций передачи данных между двумя процессами. Наименование неблокирующих аналогов образуется из названий соответствующих функций путем добавления префикса I ( Immediate ). Список параметров неблокирующих функций содержит обычный набор параметров исходных функций и один дополнительный параметр request с типом MPI_Request (в функции MPI_Irecv отсутствует также параметр status ):

  •  int MPI_Isend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request),
  •  int MPI_Issend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request),
  •  int MPI_Ibsend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request),
  •  int MPI_Irsend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request),
  •  int MPI_Irecv(void *buf, int count, MPI_Datatype type, int source, int tag, MPI_Comm comm, MPI_Request *request).

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

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

int MPI_Test(MPI_Request *request, int *flag, MPI_status *status),

где

request — дескриптор операции, определенный при вызове неблокирующей функции;

flag — результат проверки ( true, если операция завершена);

status — результат выполнения операции обмена (только для завершенной операции).

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

MPI_Isend(buf, count, type, dest, tag, comm, &request);

………….

do {

………...

MPI_Test(&request, &flag, &status);

} while (!flag);

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

int MPI_Wait(MPI_Request *request, MPI_status *status),

где

request — дескриптор операции, определенный при вызове неблокирующей функции;

status — результат выполнения операции обмена (только для завершенной операции).

Кроме рассмотренных, MPI содержит ряд дополнительных функций проверки и ожидания неблокирующих операций обмена:

  •  MPI_Testall — проверка завершения всех перечисленных операций обмена;
  •  MPI_Waitall — ожидание завершения всех операций обмена;
  •  MPI_Testany — проверка завершения хотя бы одной из перечисленных операций обмена;
  •  MPI_Waitany — ожидание завершения любой из перечисленных операций обмена;
  •  MPI_Testsome — проверка завершения каждой из перечисленных операций обмена;
  •  MPI_Waitsome — ожидание завершения хотя бы одной из перечисленных операций обмена и оценка состояния по всем операциям.

Одновременное выполнение передачи и приема.

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

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

int MPI_Sendrecv(void *sbuf,int scount,MPI_Datatype stype,

 int dest, int stag, void *rbuf,int rcount,MPI_Datatype rtype,

 int source,int rtag, MPI_Comm comm, MPI_Status *status),

где

sbuf, scount, stype, dest, stag — параметры передаваемого сообщения;

rbuf, rcount, rtype, source, rtag — параметры принимаемого сообщения;

comm — коммуникатор, в рамках которого выполняется передача данных;

status — структура данных с информацией о результате выполнения операции.

Как следует из описания, функция MPI_Sendrecv передает сообщение, описываемое параметрами ( sbuf, scount, stype, dest, stag ), процессу с рангом dest и принимает сообщение в буфер, определяемый параметрами ( rbuf, rcount, rtype, source, rtag ), от процесса с рангом source.

Группа процессоров и коммутаторов.

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

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

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

Управление группами.

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

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

int MPI_Comm_group(MPI_Comm comm, MPI_Group *group),

где

comm — коммуникатор;

group — группа, связанная с коммуникатором.

Далее, на основе существующих групп, могут быть созданы новые группы:

  1.  создание новой группы newgroup из существующей группы oldgroup, которая будет включать в себя n процессов — их ранги перечисляются в массиве ranks:

int MPI_Group_incl(MPI_Group oldgroup, int n, int *ranks,

MPI_Group *newgroup),

где

oldgroup — существующая группа;

n — число элементов в массиве ranks;

ranks — массив рангов процессов, которые будут включены в новую группу;

newgroup — созданная группа;

  •  2)
  1.  создание новой группы newgroup из группы oldgroup, которая будет включать в себя n процессов, чьи ранги не совпадают с рангами, перечисленными в массиве ranks:

int MPI_Group_excl(MPI_Group oldgroup, int n, int *ranks,

MPI_Group *newgroup),

где

oldgroup — существующая группа;

n — число элементов в массиве ranks;

ranks — массив рангов процессов, которые будут исключены из новой группы;

newgroup — созданная группа.

Для получения новых групп над имеющимися группами процессов могут быть выполнены операции объединения, пересечения и разности:

  •  создание новой группы newgroup как объединения групп group1 и group2:

 int MPI_Group_union(MPI_Group group1, MPI_Group group2,

MPI_Group *newgroup),

где

group1 первая группа;

group2 — вторая группа;

newgroup — объединение групп;

  •  создание новой группы newgroup как пересечения групп group1 и group2:

 int MPI_Group_intersection(MPI_Group group1, MPI_Group group2,

MPI_Group *newgroup),

где

group1 первая группа;

group2 — вторая группа;

newgroup — пересечение групп;

  •  создание новой группы newgroup как разности групп group1 и group2:

 int MPI_Group_difference(MPI_Group group1, MPI_Group group2,

MPI_Group *newgroup),

где

group1 первая группа;

group2 — вторая группа;

newgroup — разность групп;

При конструировании групп может оказаться полезной специальная пустая группа MPI_COMM_EMPTY.

Ряд функций MPI обеспечивает получение информации о группе процессов:

  1.  получение количества процессов в группе:

int MPI_Group_size(MPI_Group group, int *size),

где

group — группа;

size — число процессов в группе;

  1.  получение ранга текущего процесса в группе:

int MPI_Group_rank(MPI_Group group, int *rank),

где

group — группа;

rank — ранг процесса в группе.

  1.  После завершения использования группа должна быть удалена:

int MPI_Group_free(MPI_Group *group),

где

group — группа, подлежащая удалению

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

Управление коммуникаторами.

Для создания новых коммуникаторов существуют два основных способа:

  1.  дублирование уже существующего коммуникатора:

int MPI_Comm_dup(MPI_Comm oldcom, MPI_comm *newcom),

где

oldcom — существующий коммуникатор, копия которого создается;

newcom — новый коммуникатор;

  1.  создание нового коммуникатора из подмножества процессов существующего коммуникатора:

int MPI_comm_create(MPI_Comm oldcom, MPI_Group group,

MPI_Comm *newcom),

где

oldcom — существующий коммуникатор;

group — подмножество процессов коммуникатора oldcom;

newcom — новый коммуникатор.

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

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

Быстрый и полезный способ одновременного создания нескольких коммуникаторов обеспечивает функция:

int MPI_Comm_split(MPI_Comm oldcomm, int split, int key,

 MPI_Comm *newcomm),

где

oldcomm — исходный коммуникатор;

split — номер коммуникатора, которому должен принадлежать процесс ;

key — порядок ранга процесса в создаваемом коммуникаторе;

newcomm — создаваемый коммуникатор.

Создание коммуникаторов относится к коллективным операциям, и поэтому вызов функции MPI_Comm_split должен быть выполнен в каждом процессе коммуникатора oldcomm. В результате выполнения функции процессы разделяются на непересекающиеся группы с одинаковыми значениями параметра split. На основе сформированных групп создается набор коммуникаторов. Для того чтобы указать, что процесс не должен входить ни в один из создаваемых коммуникаторов, необходимо воспользоваться константой MPI_UNDEFINED в качестве значения параметра split. При создании коммуникаторов для рангов процессов в новом коммуникаторе выбирается такой порядок нумерации, чтобы он соответствовал порядку значений параметров key ( процесс с большим значением параметра key получает больший ранг, процессы с одинаковым значением параметра key сохраняют свою относительную нумерацию).

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

int MPI_Comm_free(MPI_Comm *comm),

где

comm — коммуникатор, подлежащий удалению.

Показатели эффективности в параллельных алгоритмах.

Ускорение получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется величиной:

Sp(n)= T1(n)/Tp(n)

n- размерность задачи.

Эффективность использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:

Ep(n) = T1(n)/(p* Tp(n))= Sp(n)/p

Из приведенных соотношений можно показать, что в наилучшем случае Sp(n)=p и Ep(n)=1.

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

  1.  При определенных обстоятельствах ускорение может оказаться больше числа используемых процессоров Sp(n)>p - в этом случае говорят о существовании сверхлинейного ускорения. Несмотря на парадоксальность таких ситуаций (ускорение превышает число процессоров), на практике сверхлинейное ускорение может иметь место. Одной из причин такого явления может быть неодинаковость условий выполнения последовательной и параллельной программ. Например, при решении задачи на одном процессоре оказывается недостаточно оперативной памяти для хранения всех обрабатываемых данных и тогда становится необходимым использование более медленной внешней памяти (в случае же использования нескольких процессоров оперативной памяти может оказаться достаточно за счет разделения данных между процессорами). Еще одной причиной сверхлинейного ускорения может быть нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных. Так, например, известный алгоритм пузырьковой сортировки характеризуется квадратичной зависимостью количества необходимых операций от числа упорядочиваемых данных. Как результат, при распределении сортируемого массива между процессорами может быть получено ускорение, превышающее число процессоров Источником сверхлинейного ускорения может быть и различие вычислительных схем последовательного и параллельного методов,
  2.  При внимательном рассмотрении можно обратить внимание, что попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) могут привести к ухудшению ситуации по другому показателю, ибо показатели качества параллельных вычислений являются часто противоречивыми. Так, например, повышение ускорения обычно может быть обеспечено за счет увеличения числа процессоров, что приводит, как правило, к падению эффективности. И наоборот, повышение эффективности достигается во многих случаях при уменьшении числа процессоров (в предельном случае идеальная эффективность Ep(n)=1 легко обеспечивается при использовании одного процессора). Как результат, разработка методов параллельных вычислений часто предполагает выбор некоторого компромиссного варианта с учетом желаемых показателей ускорения и эффективности.

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

Cp(n) = p*Tp(n)

В связи с этим можно определить понятие стоимостно-оптимального параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма:

Ср’(n) ~ T1(n)

Ср’(n) = k*T1(n)

Модельная задача – вычисление частных сумм последовательности числовых значений.

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

Изучение возможных параллельных методов решения данной задачи начнем с еще более простого варианта ее постановки – с задачи вычисления общей суммы имеющегося набора значений:

Последовательный алгоритм суммирования

Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора:

S=0,

S=S+x1,...

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

Как можно заметить, данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен.

Лекция 6.

Каскадная схема суммирования.

Алгоритм  состоит в следующем:

– на первой итерации каскадной схемы все исходные данные разбиваются на пары, и для каждой пары вычисляется сумма их значений,

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

Эта вычислительная схема может быть определена как граф .

n- размерность задачи

Т – число операций

Характеристики каскадных моделей:

  1.  Количество операций ввода  n=
  2.  Количество выполняемых операций k=

Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется величиной:     =

Эффективность (efficiency)  использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:

= =

p= ;   =        при  ; n→∞

При увеличении n процессоры используются все менее эффективно.

 

Каскадная схема с асимптотически ненулевой эффективностью.

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

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

n= ;  k= ;  s=2 => n=16

                                             

Для  реализации каскадной схемы требуется:  ) ≤.

Для реализации каскадной схемы понадобится:/2.

Худший случай: 2;     ;   

   =

lim  = 0,5  при  n→∞

Построение частичных сумм

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

=  ;  1 ≤ k ≤ n;

  p=n;    = ;   

= =

 

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

Оценка максимального параллелизма.

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

  1.  Закон Амдаля

Достижению максимального ускорения может препятствовать существование в выполняемых вычислениях последовательных расчетов, которые не могут быть распараллелены.  Пусть  f есть доля последовательных вычислений  в применяемом алгоритме обработки данных; тогда в соответствии с законом Амдаля (Amdahl) ускорение процесса вычислений при использовании p процессоров ограничивается величиной:

Так, например, при наличии всего 10% последовательных команд в выполняемых вычислениях, эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных. Для рассмотренного примера вычисления суммы значений для каскадной схемы доля последовательных расчетов составляет и, как результат, величина возможного ускорения ограничена оценкой =

Закон Амдаля характеризует одну из самых серьезных проблем в области параллельного программирования (алгоритмов без определенной доли последовательных команд практически не существует). Однако часто доля последовательных действий характеризует не возможность параллельного решения задач, а последовательные свойства применяемых алгоритмов. Как результат, доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания методов. Следует отметить также, что рассмотрение закона Амдаля происходит при предположении, что доля последовательных расчетов  f  является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой  задачи. Однако для большого ряда задач доля f  =  f (n) является убывающей функцией от n,  и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за

счет увеличения вычислительной сложности решаемой задачи. Данное замечание может быть сформулировано как утверждение, что ускорение  = (n)  является возрастающей функцией от параметра n  (данное утверждение часто именуется как эффект Амдаля).

  1.  Закон Густавсона-Барсиса

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

где     есть времена последовательной и параллельной частей выполняемых вычислений соответственно, т. е. (n) = τ( n) + π( n) ;            С учетом введенной величины g можно получить:  τ( n)=g∙ ( τ( n) + );

π( n)=(1-g)p∙(τ( n)+; что позволяет построить оценку для ускорения:

= ; которая после упрощения приводится к виду  закона Густавсона–Барсиса (GustafsonBarsis's law):

За счет увеличения числа суммируемых значений величина  g может быть пренебрежимо малой, обеспечивая получение идеального возможного ускорения = p.                        При рассмотрении закона Густавсона–Барсиса следует учитывать еще один важный момент. При увеличении  числа используемых процессоров темп уменьшения времени параллельного решения задач может падать (после превышения определенного порога). Однако при этом за счет уменьшения времени вычислений сложность решаемых задач может быть увеличена. Оценку получаемого при этом ускорения можно определить при помощи сформулированных закономерностей. Такая аналитическая оценка тем более полезна, поскольку решение таких более сложных вариантов задач на одном процессоре может оказаться достаточно трудоемким и даже невозможным, например, в силу нехватки оперативной памяти. С учетом указанных обстоятельств оценку ускорения, получаемую в соответствии с законом Густавсона–Барсиса, еще называют ускорением масштабирования (scaled speedup), поскольку данная характеристика может показать, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.

Анализ масштабируемости параллельных вычислений.

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

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

Используя введенные обозначения, соотношения для времени параллельного решения задачи и соответствующего ускорения можно представить в виде:

,     

Соответственно эффективность использования s процессоров:

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

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

Пусть задан желаемый уровень эффективности выполняемых вычислений: =const.

Из выражения для эффективности можно записать так :       или

, где K=

Из последнего равенства видно, что эффективность характеризуется коэффициентом K. Следовательно, если построить функцию вида N = F(K, s) , то для заданного фиксированного уровня эффективности K каждому числу процессоров s можно поставить в соответствие требуемый уровень сложности –N и наоборот. При рассмотрении конкретных вычислительных алгоритмов построение функции изоэффективности позволяет выявить пути совершенствования параллельных алгоритмов.

Для построения этих функций удобно использовать закон Густавсона –Барсиса. Эффективность использования s процессоров в соответствии с этим законом выражается в виде :  .

При заданном фиксированном = const с использованием этого равенства можно построить аналитическое соотношение для функции изоэффективности в следующем виде: g = F(, s).  Такая форма может оказаться более удобной в случае, когда известна доля времени на проведение последовательных расчетов в выполняемых параллельных вычислениях.

Верхняя граница времени выполнения параллельного алгоритма

Для любого количества используемых процессоров – s справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма:  

Действительно, пусть  есть расписание для достижения минимально возможного времени выполнения . Для каждой итерации τ, 0<τ<T∞ выполнения расписания обозначим через количество операций, выполняемых в ходе итерации τ. Расписание  выполнения алгоритма с использованием s процессоров может быть построено следующим образом. Выполнение алгоритма разделим на шагов; на каждом шаге τ следует выполнить все  операций, которые выполнялись на итерации τ расписания . Эти операции могут быть выполнены не более чем за  ] /s[ итераций при использовании s процессоров. Как результат, время выполнения алгоритма Ts может быть оценено следующим образом: +,

где ]* [– означает операцию округления до целого числа в сторону увеличения.

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

Факторы, влияющие на производительность, и способы ее повышения.

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

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

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

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

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

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

Лекция 7

Принципы разработка параллельных алгоритмов.

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

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

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

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

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

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

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

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

Моделирование (использование моделей) при проектировании параллельных алгоритмов.

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

Использование двух моделей параллельных вычислений позволяет лучше разделить проблемы, которые проявляются при разработке параллельных методов:

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

Дадим дополнительные пояснения для используемых понятий в модели "процессы – каналы":

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

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

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

Этапы разработки параллельных алгоритмов.

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

  1.  Разделение вычислительной схемы на независимые части, на основе ее анализа.

Цель: выделить подзадачи, имеющие равные по объему вычисления, и минимизировать  информационные взаимодействия между ними.

  •  Крупные подзадачи обеспечивают более наглядное представление.
  •  Мелкие подзадачи обеспечивают более равномерную загрузку процессоров.

По возможности лучше реализовывать информационные взаимодействия  сообщениями большого объема.

Данные организуются в виде матриц. Разделение производится по строкам, по столбцам и по блокам:

  •  По строкам.

  •  По столбцам.

  •  По блокам.

Распараллеливание по данным.

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

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

Функциональное распараллеливание.

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

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

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

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

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

  1.  Определение информационных зависимостей.

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

При проведении анализа информационных зависимостей между подзадачами следует различать (предпочтительные формы информационного взаимодействия выделены подчеркиванием):

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

Критерии для проверки этого этапа:

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

  1.  Масштабирование набора подзадач.

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

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

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

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

Список контрольных вопросов для оценки правильности этапа масштабирования, выглядит следующим образом:

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

  1.  Распределение подзадач между процессорами.

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

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

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

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

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

В качестве примера дадим краткую характеристику широко используемого способа динамического управления распределением вычислительной нагрузки, обычно именуемого схемой "менеджер – исполнитель" ( the manager-worker scheme ). При использовании данного подхода предполагается, что подзадачи могут возникать и завершаться в ходе вычислений, при этом информационные взаимодействия между подзадачами либо полностью отсутствуют, либо минимальны. В соответствии с рассматриваемой схемой для управления распределением нагрузки в системе выделяется отдельный процессор-менеджер, которому доступна информация обо всех имеющихся подзадачах. Остальные процессоры системы являются исполнителями, которые для получения вычислительной нагрузки обращаются к процессору-менеджеру. Порождаемые в ходе вычислений новые подзадачи передаются обратно процессору-менеджеру и могут быть получены для решения при последующих обращениях процессоров- исполнителей. Завершение вычислений происходит в момент, когда процессоры-исполнители завершили решение всех переданных им подзадач, а процессор-менеджер не имеет каких-либо вычислительных работ для выполнения.

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

  •  Не приводит ли распределение нескольких задач на один процессор к росту дополнительных вычислительных затрат?
  •  Существует ли необходимость динамической балансировки вычислений?
  •  Не является ли процессор-менеджер "узким" местом при использовании схемы "менеджер – исполнитель"

Умножение матриц при ленточной схеме разделения данных.

Рассмотрим два параллельных алгоритма умножения матриц, в которых матрицы A и B разбиваются на непрерывные последовательности строк или столбцов (полосы).

Определение подзадач.

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

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

Выделение информационных зависимостей

Для вычисления одной строки матрицы С необходимо, чтобы в каждой подзадаче содержалась строка матрицы А и был обеспечен доступ ко всем столбцам матрицы B. Возможные способы организации параллельных вычислений состоят в следующем.

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

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

Масштабирование и распределение подзадач по процессорам

Выделенные базовые подзадачи характеризуются одинаковой вычислительной трудоемкостью и равным объемом передаваемых данных. Когда размер матриц n оказывается больше, чем число процессоров p, базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько соседних строк и столбцов перемножаемых матриц. В этом случае исходная матрица A разбивается на ряд горизонтальных полос, а матрица B представляется в виде набора вертикальных (для первого алгоритма) или горизонтальных (для второго алгоритма) полос. Размер полос при этом следует выбрать равным k=n/p (в предположении, что n кратно p ), что позволит по-прежнему обеспечить равномерность распределения вычислительной нагрузки по процессорам, составляющим многопроцессорную вычислительную систему.

Анализ эффективности

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

Общая трудоемкость последовательного алгоритма, как уже отмечалось ранее, является пропорциональной n3. Для параллельного алгоритма на каждой итерации каждый процессор выполняет умножение имеющихся на процессоре полос матрицы А и матрицы В(размер полос равен n/p, и, как результат, общее количество выполняемых при этом умножении операций равно n3/p2 ). Поскольку число итераций алгоритма совпадает с количеством процессоров, сложность параллельного алгоритма без учета затрат на передачу данных может быть определена при помощи выражения

(7.4)

С учетом этой оценки показатели ускорения и эффективности данного параллельного алгоритма матричного умножения принимают вид:

Лекция 8

Параллельное решение систем линейных уравнений

Алгоритм решения систем линейных уравнений методом Гаусса.

Системы линейных уравнений возникают при решении многих прикладных задач. Матрицы коэффициентов систем линейных уравнений могут иметь различные структуру и свойства. Мы будем полагать, что решаемая система имеет плотную матрицу высокого порядка. Линейная система n уравнений с n неизвестными , , …, может быть представлена в виде  Ax=b.  Здесь n×n-матрица A и n×1-вектор b составлены из вещественных чисел, а задача заключается в нахождении неизвестного вектора x.

                                              ………………

                                             

Метод Гаусса – широко используемый алгоритм решения систем линейных уравнений  с   невырожденной матрицей  A. Метод заключается в приведении матрицы А системы  к верхнему треугольному виду путем последовательных эквивалентных преобразований (прямой ход), с последующей последовательной подстановкой (обратный ход). К числу  эквивалентных преобразований относятся:

  •  умножение любого из уравнений на ненулевую константу;  
  •  перестановка уравнений;
  •  прибавление к уравнению любого другого уравнения системы.

Прямой ход метода Гаусса состоит в последовательном исключении неизвестных в уравнениях решаемой системы линейных уравнений. На итерации  i, 0 ≤ i<n–1 метода производится исключение неизвестной  i для всех уравнений с номерами k, большими  i (т.е.  i<kn–1). Для этого из этих уравнений осуществляется вычитание строки  i, умноженной на константу (/), с тем чтобы результирующий коэффициент при неизвестной xi в строках оказался нулевым. Вычисления, выполняемые над элементами матрицы A и вектора b, определяются следующими соотношениями:

0≤ i <n-1 ;  i< kn-1 ;   i≤ 0 ≤ n-1

          Выполнение прямого хода метода Гаусса покажем на примере системы:  

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

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

Итерация прямого хода алгоритма Гаусса

На рисунке представлена общая схема состояния данных на  i-й итерации прямого хода алгоритма Гаусса. Все коэффициенты при неизвестных, расположенные ниже главной диагонали и левее столбца i, уже являются нулевыми. На i-й итерации прямого хода метода Гаусса осуществляется обнуление коэффициентов столбца  i, расположенных ниже главной диагонали, путем вычитания строки i, умноженной на величину /, соответствующую k-й строке. После n-1–й итерации матрица приводится к верхнему треугольному виду.

Строка, которая используется для исключения неизвестных в прямом ходе метода Гаусса, называется ведущей, а диагональный элемент ведущей строки – ведущим элементом. Вычисление невозможно, если ведущий элемент равен нулю. Даже если ведущий элемент отличен от нуля, но имеет малое значение, деление на этот элемент может приводить к накоплению вычислительной погрешности и вычислительной неустойчивости алгоритма.

Для того чтобы избежать этой проблемы, на каждой итерации прямого хода в столбце, соответствующем исключаемой неизвестной, определяют коэффициент с максимальным значением по абсолютной величине:   y= max ||, ikn–1, а в качестве ведущей принимают строку, в которой располагается этот коэффициент (метод главных элементов).

Вычислительная сложность прямого хода алгоритма Гаусса с выбором ведущей строки имеет порядок O().

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

i=n-2, n-3,….,0

Продолжим рассмотрение приведенного выше примера. Из последнего уравнения нетрудно видеть, что неизвестная =9/3=3. Подставляя это значение во второе уравнение, определим значение неизвестной =16–3=13. На последней итерации обратного хода метода Гаусса определяется значение неизвестной = 1–3∙13–2∙3 = –44. Заметим, что в обратном ходе исключение переменной, после того как она определена, может выполняться одновременно, т.е. параллельно, во всех уравнениях системы.

Определим вычислительную сложность метода Гаусса. В прямом ходе алгоритма для выбора ведущей строки на каждой итерации должно быть определено максимальное значение в столбце с исключаемой неизвестной. По мере исключения неизвестных количество строк и элементов в строках сокращается. Текущее число элементов строки (включая правую часть), с которыми производятся действия сложения и вычитания (первый элемент без вычислений полагается равным нулю), равно  (n-i),  где  i, 0≤ i<n-2 – номер итерации прямого хода. Поскольку кроме выполнения двух операций (умножения и вычитания) с каждым элементом строки предварительно должен быть вычислен масштабирующий коэффициент /, общие затраты на выполнение действий в одной строке составят  2(n-i)+1  операций.

С учетом того, что на каждой i-й итерации, 0≤ i<n-2 (итерациям для удобства присваиваем номера от n-2 до 0) необходимо произвести n-i-1 умножений, столько же вычитаний, а также одно деление для определения очередной неизвестной. Следовательно, общая вычислительная сложность обратного хода составит:

Суммируя затраты на реализацию прямого и обратного хода, получаем:

В последнем равенстве пределы и порядок суммирования изменены с учетом замены j=n-i.

Используя элементарные формулы суммирования, в частности, известное равенство

,

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

T=

При большом n можно приближенно положить T≈

Вычислительная сложность обратного хода алгоритма Гаусса имеет порядок O(). Общая сложность всего алгоритма O().

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

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

  1.  нужно собрать ведущие элементы на первом процессоре и выбрать ведущую строку;
  2.  затем надо ведущую строку разослать всем процессорам, в которых есть к –ые строки;
  3.  получив ведущую строку, все процессоры выполняют вычитание строк и исключают из системы переменную .

В обратном ходе метода Гаусса, как только какая-либо, например  i–я подзадача,

0 ≤i<n-1, определила свою переменную., это значение рассылается всем подзадачам с номерами k, k<i. В каждой подзадаче полученное значение неизвестной умножается на соответствующий коэффициент и выполняется корректировка соответствующего элемента вектора b.

Масштабирование и распределение подзадач по процессорам.

В качестве подзадач могут быть взяты строки матрицы A, каждая из которых при этом закрепляется за одним процессором. Если число строк матрицы больше, чем число доступных процессоров (p<n), подзадачи можно укрупнить, объединив несколько строк матрицы. Если при  этом используется последовательная схема разделения данных, при которой в одной подзадаче оказываются соседние строки матрицы, по мере исключения (в прямом ходе) или определения (в обратном ходе) неизвестных, все большая часть процессоров, для которой вычисления завершены, окажется простаивающей.  

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

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

Анализ эффективности

Пусть n – порядок системы линейных уравнений, а p, p<n – число используемых процессоров, т.е. матрица А имеет размер n×n, а n/p – размер полосы на каждом процессоре (для простоты полагаем, что n/p – целое число). Определим сложность параллельного варианта метода Гаусса.  

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

Общие затраты на выполнение действий в одной строке на  i-й итерации,  0 ≤i<n-2  составляет  2(n-i)+1  операций. Если применена циклическая схема распределения данных между процессорами, то на  i-й итерации каждый процессор будет обрабатывать примерно  (n-i)/s  строк. С учетом этого, общее число операций параллельного варианта прямого хода метода Гаусса определяется выражением :

=

Обратный ход. После рассылки очередного сообщения:

Ускорение :    

Эффективность :    

                                     Затраты при обратном ходе:

Лекция 9

Параллельные методы сортировки

Сортировка является одной из типовых проблем обработки данных и обычно понимается как задача размещения элементов неупорядоченного набора значений в порядке монотонного возрастания или убывания (здесь и далее все пояснения для краткости будут даваться только на примере упорядочивания данных по возрастанию).

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

T n2

Для более эффективных алгоритмов (сортировка слиянием, сортировка Шелла, быстрая сортировка ) трудоемкость определяется величиной T  

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

Ускорение сортировки может быть обеспечено при использовании нескольких (p>1) процессоров. Исходный упорядочиваемый набор в этом случае разделяется между процессорами; в ходе сортировки данные пересылаются между процессорами и сравниваются между собой. Результирующий (упорядоченный) набор, как правило, также разделен между процессорами; при этом для систематизации такого разделения для процессоров вводится та или иная система последовательной нумерации и обычно требуется, чтобы при завершении сортировки значения, располагаемые на процессорах с меньшими номерами, не превышали значений процессоров с большими номерами.

Принципы распараллеливания

При внимательном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно заметить, что многие методы основаны на применении одной и той же базовой операции "сравнить и переставить" ( compare-exchange ), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановке этих значений, если их порядок не соответствует условиям сортировки.

// Базовая операция "сравнить и переставить"

if ( A[i] > A[j] ) {

 temp = A[i];

 A[i] = A[j];

 A[j] = temp;

}

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

Для параллельного обобщения выделенной базовой операции сортировки рассмотрим первоначально ситуацию, когда количество процессоров совпадает с числом сортируемых значений (т. е. p=n ) и на каждом из процессоров содержится только по одному значению исходного набора данных. Тогда сравнение значений ai и aj, располагаемых соответственно на процессорах Pi и Pj, можно организовать следующим образом (параллельное обобщение базовой операции сортировки ):

  1.  выполнить взаимообмен имеющихся на процессорах Pi и Pj значений (с сохранением на этих процессорах исходных элементов);
  2.  сравнить на каждом процессоре Pi и Pj получившиеся одинаковые пары значений ( ai, aj ); результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi ) остается меньший элемент, другой процессор (т. е. Pj ) запоминает для дальнейшей обработки большее значение пары

Масштабирование параллельных вычислений

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

Определим в качестве результата выполнения параллельного алгоритма сортировки такое состояние упорядочиваемого набора данных, при котором имеющиеся на процессорах данные упорядочены, а порядок распределения блоков по процессорам соответствует линейному порядку нумерации (т. е. значение последнего элемента на процессоре Pi меньше значения первого элемента на процессоре Pi+1, где 0i<p-1 или равно ему).

Блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (начальная стадия параллельной сортировки ). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров Pi и Pi+1 для совместного упорядочения содержимого блоков Ai и Ai+1 может быть осуществлено следующим образом:

  •  выполнить взаимообмен блоков между процессорами Pi и Pi+1 ;
  •  объединить блоки Ai и Ai+1 на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков Ai и Ai+1 процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);
  •  разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре Pi, а другую часть (с большими значениями, соответственно) – на процессоре Pi+1

Рассмотренная процедура обычно именуется в литературе операцией "сравнить и разделить" ( compare-split ). Следует отметить, что сформированные в результате такой процедуры блоки на процессорах Pi и Pi+1 совпадают по размеру с исходными блоками Ai и Ai+1 и все значения, расположенные на процессоре Pi, не превышают значений на процессоре Pi+1.

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

Пузырьковая сортировка

Последовательный алгоритм.

Последовательный алгоритм пузырьковой сортировки ( the bubble sort algorithm ) сравнивает и обменивает соседние элементы в последовательности, которую нужно отсортировать. Для последовательности

(a1, a2, ..., an)

алгоритм сначала выполняет n-1 базовых операций "сравнения-обмена" для последовательных пар элементов

(a1, a2), (a2, a3), ..., (an-1, an).

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

(a'1, a'2, ..., a'n-1).

Как можно увидеть, последовательность будет отсортирована после n-1 итерации. Эффективность пузырьковой сортировки может быть улучшена, если завершать алгоритм в случае отсутствия каких- либо изменений сортируемой последовательности данных в ходе какой-либо итерации сортировки.

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

Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная в литературе как метод чет-нечетной перестановки ( the odd-even transposition method ). Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода: в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Таким образом, на всех нечетных итерациях сравниваются пары

(a1, a2), (a3, a4), ..., (an-1,an) (при четном n),

а на четных итерациях обрабатываются элементы

(a2, a3), (a4, a5), ..., (an-2,an-1).

После n -кратного повторения итераций сортировки исходный набор данных оказывается упорядоченным.

Определение подзадач и выделение информационных зависимостей

Получение параллельного варианта для метода чет-нечетной перестановки уже не представляет каких-либо затруднений – сравнения пар значений на итерациях сортировки являются независимыми и могут быть выполнены параллельно. В случае p<n, когда количество процессоров меньше числа упорядочиваемых значений, процессоры содержат блоки данных размера n/p и в качестве базовой подзадачи может быть использована операция "сравнить и разделить”.

// Параллельный алгоритм чет-нечетной перестановки

ParallelOddEvenSort(double A[], int n) {

 int id = GetProcId();     // номер процесса

 int np = GetProcNum();    // количество процессов

 for (int i = 0; i < np; i++ ) {

   if (i % 2 == 1) {    // нечетная итерация

     if (id % 2 == 1) {    // нечетный номер процесса

       // Cравнение-обмен с процессом — соседом справа

       if (id < np - 1) compare_split_min(id + 1);

     }

     else

       // Cравнение-обмен с процессом — соседом слева

       if (id > 0) compare_split_max(id - 1);

   }

   else {    // четная итерация

     if(id % 2 == 0) {    // четный номер процесса

       // Cравнение-обмен с процессом — соседом справа

       if (id < np - 1) compare_split_min(id + 1);

     }

     else

       // Cравнение-обмен с процессом — соседом слева

       compare_split_max(id - 1);

   }

 }

}

Для пояснения такого параллельного способа сортировки в табл. 9.1 приведен пример упорядочения данных при n=16, p=4 (т.е. блок значений на каждом процессоре содержит n/p=4 элемента). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессов, для которых параллельно выполняются операции "сравнить и разделить". Взаимодействующие пары процессов выделены в таблице рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.

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

Таблица 9.1. Пример сортировки данных параллельным методом чет-нечетной перестановки

№ и тип итераци

Процессоры

1

2

3

4

Исходные данные

13 55 59 88

29 43 71 85

2 18 40 75

4 14 22 43

1 нечет (1, 2), (3, 4)

13 55 59 88

29 43 71 85

2 18 40 75

4 14 22 43

13 29 43 55

59 71 85 88

2 4 14 18

22 40 43 75

2 чет (2, 3)

13 29 43 55

59 71 85 88

2 4 14 18

22 40 43 75

13 29 43 55

2 4 14 18

59 71 85 88

22 40 43 75

3 нечет (1, 2), (3, 4)

13 29 43 55

2 4 14 18

59 71 85 88

22 40 43 75

2 4 13 14

18 29 43 55

22 40 43 59

71 75 85 88

4 чет (2, 3)

2 4 13 14

18 29 43 55

22 40 43 59

71 75 85 88

2 4 13 14

18 22 29 40

43 43 55 59

71 75 85 88

Масштабирование и распределение подзадач по процессорам

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

Анализ эффективности

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

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

(9.1)

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

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

(9.2)

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

(9.3)

С учетом полученных соотношений показатели эффективности и ускорения параллельного метода сортировки имеют вид:

(9.4)

Расширим приведенные выражения – учтем длительность выполняемых вычислительных операций и оценим трудоемкость операции передачи блоков между процессорами. При использовании модели Хокни общее время всех выполняемых в ходе сортировки операций передачи блоков можно оценить при помощи соотношения вида:

(9.5)

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

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

(9.6)

где  есть время выполнения базовой операции сортировки.

Лекция 10

Параллельные вычисления при решении задач на графах.

Модельный пример: алгоритм Флойда-Уоршелла.— алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования.

G (V,U)  |V|=n

Пример взвешенного ориентированного графа

Известны различные способы задания графов. При малом количестве дуг в графе (т.е. m<<) целесообразно использовать  для определения графов списки, перечисляющие имеющиеся в графах дуги. Представление достаточно плотных графов, ждля которых почти все вершины соединены между собой дугами, может быть эффективно обеспечено при помощи матрицы смежности. A=), 1≤I, jn, ненулевые значения элементов которой соответствуют дугам графа.

 

Матрица смежности для графа, рассмотренного выше  

Программная реализация параллельного алгоритма Флойда:

int ProcRank; // rank of current process

int ProcNum; // number of processes

// Maximum evaluation function

int Min(int A, int B)

int Result = (A < B) ? A : B;

if ((A < 0) && (B >= 0)) Result = B;

if ((B < 0) && (A >= 0)) Result = A;

if ((A < 0) && (B < 0))  Result = -1;

return Result;

}

// Main function

int main(int argc, char* argv[]) {

int *pMatrix; ; // adjacency matrix

int Size; // size of adjacency matrix

int *pProcRows;  // rows of adjacency matrix

int RowNum;  // number of rows on current process

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);

MPI_Comm_rank (MPI_COMM_WORLD, &ProcRank);

// Data initialization

ProcessInitialization (pMatrix, pProcRows, Size, RowNum);

// Data distribituon to all processes

DataDistribution (pMatrix, pProcRows, Size, RowNum);

// The Floyd parallel algorithm

ParallelFloyd (pProcRows, Size, RowNum);

// Result collection

ResultCollection (pMatrix, pProcRows, Size, RowNum);

// Computation Termination

ProcessTermination (pMatrix, pProcRows);

 

MPI_Finalize();

 return 0;

}

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

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

Функция DataDistribution распределяет данные между процессами. Каждый процесс получает горизонтальную полосу исходной матрицы.

Функция ProcessTermination выполняет необходимый вывод результатов решения  задачи и освобождает всю ранее выделенную память для хранения данных.

Матрица смежности вершин взвешена длинами дуг, идущими из вершины

i в j : A[i][j]

for (k=0; k<n; k++)

    for (i=0; i<n; i++)            Последовательный алгоритм

         for (j=0; j<n; j++)

            { A[i][j]=min (A[i][j], A[i][k]+ A[k][j]); }

Определение подзадач.

Матрица изменяется в ходе выполнения алгоритма, поэтому матрицу нельзя разделить между процессорами.

В качестве подзадач можно принять цикл по i и j. Всего получается k подзадач. Но сначала надо показать, что для заданного k не меняются A[i][k], A[k][j]:

i=k

A[k][j]= min (A[k][j], A[k,k]+ A[k][j]),

т.е.  A[i][j]= A[k,j] не меняется, т.к. петель нет

j=k

A[i][k]=min (A[i][k], A[k,k]+ A[i][k])

Для каждой подзадачи понадобятся: A[i][j], A[i][k],A[k][j]

0  0  0  0  0  0  

0  0  0  0  0  0  

0  0  0  0  0  0  

0  0  0  0  0  0  

0  0  0  0  0  0  

0  0  0  0  0  0  

p<<, поэтому за каждым процессором придется закреплять вычисление не одного элемента, а некоторая лента (горизонтальная или вертикальная). Тогда на каждой итерации придется передавать строку матрицы A.

Анализ эффективности

+

Результаты вычислительных экспериментов для параллельного алгоритма Флойда

Количество вершин

Последовательный алгоритм (Время)

Параллельный алгоритм (ускорение)

1000

8, 0370

1,9357

3, 8880

8,5439

2000

59, 8119

1, 9725

3, 8901

7, 4229

3000

197, 1114

1,9851

3, 9240

7, 6867

4000

461, 7849

1,9861

3, 9395

6, 6021

5000

884, 6221

1,9935

3,9414

6,9069

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

G (V,U)   
     n=|V|

Выделение подзадач

V=TᴗX, где T-вершины, принадлежащие минимальному остову;

X – все остальные вершины

На каждой итерации k для любой вершины x из множества X определяется – минимальная длина ребра, соединяющая эту вершину с одной из вершин множества X.

На каждой итерации можно параллельно выбирать минимальные длины ребер.

)

k=- число вершин на каждом процессоре

Анализ информационных связей

Итерация завершается выбором из всех минимального.

Лекция 11

PVM (Параллельные виртуальные машины).

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

PVM – это некоторая альтернатива MPI, но менее распространенная.

PVM можно использовать программируя на различных языках (например, C/C++, Fortran, Perl, Java, Matlab).

Гетерогенность  выражается разнородностью:

  1.  по формату данных на узлах.
  2.  по быстродействию узлов.
  3.  по архитектуре узлов.
  4.  по загрузке узлов.
  5.  по загрузке сети.

Преимущества PVM:

  •  Сравнительно низкая стоимость.
  •  Возможность повышения производительности за счет динамического распределения задач по узлам.
  •  Устойчивость в процессе решения задач (интерактивное управление).
  •  Наращивание и модификация программ.

Основные постулаты, взятые за основу для PVM:

  1.  Конфигурируемый пользователем пул хостов: вычислительные задачи приложения выполняются с привлечением набора машин, которые выбираются пользователем для данной программы PVM. Как однопроцессорные машины, так и аппаратное обеспечение мультипроцессоров (включая компьютеры с разделяемой и распределенной памятью) могут быть составной частью пула хостов. Пул хостов может изменяться добавлением и удалением машин в процессе работы (важная возможность для поддержания минимального уровня ошибок).
  2.  Прозрачность доступа к оборудованию: прикладные программы могут ``видеть'' аппаратную среду как группу виртуальных вычислительных элементов без атрибутов или эксплуатировать по выбору возможности специфических машин из пула хостов путем ``перемещения'' определенных счетных задач на наиболее подходящие для их решения компьютеры.
  3.  Вычисления, производимые с помощью процессов: единицей параллелизма в PVM является задача (часто, но не всегда совпадает с процессом в системе UNIX) - независимый последовательный поток управления, который может быть либо коммуникационным, либо вычислительным. PVM не содержит и не навязывает карты связей процессов; характерно, что составные задачи могут выполняться на одном процессоре.
  4.  Модель явного обмена сообщениями: группы вычислительных задач, каждая из которых выполняет часть ``нагрузки'' приложения - используется декомпозиция по данным, функциям или гибридная, - взаимодействуют, явно посылая сообщения друг другу и принимая их. Длина сообщения ограничена только размером доступной памяти.
  5.  Поддержка гетерогенности: система PVM поддерживает гетерогенность системы машин, сетей и приложений. В отношении механизма обмена сообщениями PVM допускает сообщения, содержащие данные более одного типа, для обмена между машинами с различным представлением данных.
  6.  Поддержка мультипроцессоров: PVM использует оригинальные возможности обмена сообщениями для мультипроцессоров с целью извлечения выгоды от использования базового оборудования. Производители часто поддерживают собственные, оптимизированные для своих систем PVM, которые становятся коммуникационными в их общей версии.

Работа PVM

  1.  Создание параллельной виртуальной машины. На каждом хосте при этом запускается демон (pvmd). Каждому процессу присваивается идентификатор TD (аналогично рангу в  MPI, но на системном уровне есть отличия).

Идентификатор – это ссылка на служебную информацию с описание процесса. TD  назначается локальным демоном. Доступ к TD осуществляется с помощью библиотечной функции.

  1.  Каждому компьютеру присваивается имя, связанное с его архитектурой. Каждый процесс может передавать сообщения другому процессу. Так же, можно создавать динамические группы (эквивалент коммуникаторам).
    1.  При запуске демона в каталоге /tmp (служебный каталог временного хранения) создается файл pvmd.UTD, расширение которого совпадает с числовым идентификатором пользователя. Этот файл является блокирующим – если демон не работает, то такой хост нельзя добавить в систему виртуальной машины. Чтобы удалить pvd.UID, необходимо с помощью консоли ввести команду halt (остановить всё).
    2.  Демон параллельной виртуальной машины – это гибкое средство, позволяющее на одном компьютере работать нескольким пользователям PVM. Причем, для каждого пользователя запускается свой демон, и они работают независимо.

Демон играет роль маршрутизатора сообщений. Он управляет процессами, обеспечивает продолжение работы при аварийном завершении. pvmd, запущенный вручную  - называется главным (master). Остальные называются исполнителями (slave). Главный демон запускает остальные slave.   

Демон принимает запросы на управление конфигурацией.

Структура идентификатора TD

31       30                                            18                                                        12                                                            0        

Н-хост

Идентификатор процесса

n – номер задачи

S      G

S, G, H – глобальные параметры интерпретируются всеми демонами одинаково.

При запуске N  хостов относительно виртуальной машины, каждый демон конфигурирует с собственным номером хоста.

На каждом хосте можно запустить (218 - 1) задач.

4095 – ограничение на номер хоста.

Взаимооднозначное соответствие между номерами и физическими хостами необязательно; устанавливается глобальной таблицей.

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

Сообщениями обмениваются задачи под управлением демонов. При обмене данные преобразуются в формат XDR,  т.о. преодолевается гетерогенность. При отправке сообщения отправитель не блокируется.

Сообщение передается в коммуникационную сеть, откуда попадает в буфер приема (адресата).

  •  Буферы обмены выделяются динамически.  
  •  Последовательность сообщений от одного отправителя сохраняются при приеме.

Настройка PVM

  1.  Для установки PVM не требуется быть администратором; установить можно в личный каталог.
  2.  Настраиваются переменные окружения:

PVM_ROOT – путь к каталогу, в котором размещается система PVM.

PVM_ARCH – сюда прописываются идентификаторы архитектуры.

Структура каталога PVM:

  1.  Исполнительные файлы – примера программ.
  2.  Конфигурационные файлы.
  3.  Исходные тексты консоли.
  4.  Документации.
  5.  Исходные тексты примеров.
  6.  Командные файлы.

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

Приглашение ввести команду PVM:  PVM>

Примеры команд:

PVM>   add do1

PVM>  delete do1

PVM>  conf – вывести конфигурацию.

Наиболее распространенные проблемы

  1.  Неправильное определение переменной окружения PVM_ROOT
  2.  Файл с описанием хоста .rhost
  3.  Неправильно зарегистрирован пользователь на данном хосте.

Пример простейшей программы

// программа для master

#include "pvm3.h"

main()

{

  int err, tid, msgtag;

  char buf[100];

  printf("master:tid t%i\n", pvm_mytid());

  err= pvm_spawn("f1", (char**)0, 0, "",1, &tid);

  if (err == 1) {

      msgtag = 1;

      pvm_recv(tid, msgtag);

      pvm_upkstr(buf);

      printf("Получено сообщение от tid= %i: %s\n", tid, buf);

else printf("Ошибка\n");

  pvm_exit();

}

Лекция 12

Структура программы PVM.

f1

#includepvm3.h

   main ()

{

     int ptid, msgtag;

    char buf [100];

        ptid=pvm-parent (); // определяется идентификатор базового процесса

           strcopy (buf,  “Задача f1”); // занесение в буфер

           msgtag=1;

                 pvm-initsend ();

                PvmDataDefault (); //режимы инициирования по умолчанию

                pvm_pkstr (buf);

            pvm_send (ptid, msgtag);

      pvm_exit ();

}

Выводы по PVM:

  1.  Если платформа в виде многопроцессорного компьютера, то рекомендуется использовать технологию MPI;
  2.  Если предполагается использовать различные по настройкам режимы обмена, то используем MPI;
  3.  Если используется гетерогенный кластер (разнородный), то используем PVM;
  4.  Динамическое распределение задач, то используем PVM.

Классификация вычислительных систем

Одним из наиболее распространенных способов классификации ЭВМ является систематика Флинна (Flynn), в рамках которой основное внимание при анализе архитектуры вычислительных систем уделяется способам взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных. При таком подходе различают следующие основные типы систем:

  1.  

I – поток инструкций

D – поток данных

  1.             

                                  

За одну операцию обрабатывается вектор данных

  1.  

                           

                          Много операций над одним и тем же числом.

  1.   

  

Алгоритмы предварительного распределения данных (графы)

Модель PRAM (параллельный произвольный доступ к памяти - parallel random acess memory)- вычислительная модель, состоящая из некоторого числа синхронизованных процессоров, имеющих доступ к общей памяти. В модели предусмотрены режимы Exclusive, когда одновременный доступ к ячейке памяти разрешается только одному процессору, и Concurrent, когда одновременный доступ к ячейке памяти разрешается нескольким процессорам. Процессоры сильно связаны и используют общий блок памяти. У каждого процессора есть индивидуальная регистровая память.

Все процессоры осуществляют стандартный цикл обработки.

  •   чтение данного
  •  обработка
  •  запись в память

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

  1.  Конкурентный доступ
  2.  Исключительный доступ

Коллизии чтения

  1.  Конкурентный режим доступа. К одной и той же ячейке могут обращаться несколько процессоров одновременно.
  2.  Исключительный доступ. Читать из поля памяти может в каждый момент времени только единственный процессор.

Коллизии записи

  1.  Конкурентный доступ к памяти. Коллизии разрешаются приоритетами, приоритет может совпадать с номером процессора, может вычисляться в процессе решения задачи, логическое управление конкурентным доступом. Запись допускается, если процессоры записывают одно и то же значение, записывается минимальное из значений, которые они записывают. Арифметические подходы: попытка записи нескольких значений, то записывается их сложение или умножение.
  2.  Исключительный подход. Любая коллизия при записи фиксируется как ошибка.

Режимы параллельных вычислений с общей памятью

  •   CRCWпроизвольно много процессоров могут одновременно читать содержимое одной и той же ячейки памяти и произвольно много процессоров могут обращаться для записи в одну и ту же ячейку памяти. Данная модель разделяется на следующие подвиды в зависимости от способа разрешения конфликтов записи:

1) COMMON(CRCW)PRAM, в которой должны быть идентичными все значения, записываемые одновременно;

2) ARBITRARY(CRCW)PRAM, в которой срабатывает любой один из конкурирующих в записи процессоров;

3) PRIORITY(CRCW)PRAM, в которой процессоры линейно упорядочены в соответствии с их приоритетами и выбирается тот из конфликтующих, который имеет наивысший приоритет;

4) COMBINING(CRCW)PRAM, в которой записывается линейная комбинация вычисленных значений, например их сумма. Значения могут комбинироваться с помощью любой ассоциативной и коммутативной операции, которая вычислима за константное время на РАМ.

  •  CREW –  произвольно много процессоров могут одновременно читать содержимое одной и той же ячейки памяти, но писать может только один.  
  •    ERCW - исключающее считывание/параллельная запись
  •  EREW - только один процессор может читать содержимое ячейки памяти и только один процессор может писать в эту ячейку.

Основные обозначения псевдокода

- i-ый процессор

N –число элементов во входном списке

- j-ое поле памяти

pstart  и PEnd – скобки, фрагмент алгоритма, все операции выполняются параллельно.

Пример.  Распределение данных в модели CREW

P[1]  M[1]; // записывает в первое поле памяти данные

 PStart

    for (k=z; k≤p; k++)

         P[k]←M[1]; // остальные прочитали

 PEnd

Распределение совершается в два этапа. На первом значение записывается в память, на втором – все процессоры читают его. Такая скорость возможна только благодаря конкурентному чтению.

Распределение данных в EREW

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

Однако если воспользоваться циклом чтение / обработка / запись на втором

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

P[1]  M[1];

i=1;

for (j=1; jlogP; j++)

{

  PStart

       for (k=i+1; k≤2*i; k++)

{

          P[k]←M[k-i];

          P[k] M[k];

}

  PEnd

i=i*2;

}

Лекция 13

Параллельное программирование с использованием общей памяти

T1, CRCW – наименее жесткий режим.

T2, EREW -  чтение и запись  невозможны из одного и того же поля (противоположность CRCW).

В CRCW  любой алгоритм выполняется в этой модели, при условии, что:

  1.   Алгоритм использует p процессоров.
  2.  Существует алгоритм, который буде выполняться в модели EREW, реализует ту же самую задачу, с тем же числом процессоров. Время его выполнения не превышает время выполнения одного алгоритма в

Людой алгоритм можно перевести в другой режим.

Многопоточное программирование

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

Взаимодействие между потомками реализуется с помощью сообщений.

Технология MPI также используется в системах с общей памятью, но работают медленнее.

К общим данным относятся:

  •  Глобальные переменные.
  •  Данные, объявленные в статической памяти.
  •  Данные, объявленные в динамической памяти.

Индивидуальные данные – те, которые доступны в одном потоке – локальные переменные.

Планирование потоков используется во всех современных системах. В результате потоки выполняются параллельно.

  •  Если одному потоку приложения соответствует  один поток ядра – одноуровневая схема.
  •  Если нескольким потокам приложения соответствует одни поток ядра – многоуровневая схема.

Спецификация POSIX Threads

  •  Разработана сообществом разработчиков программного обеспечения.
  •  Предназначена для управления потоками.

IEEE's POSIX Threads Model:

• Модель программирования потоков для UNIX platform

• pthreads включает международные стандарты  ISO/IEC9945-1

Программная модель pthreads определяет:

• Создание и завершение потоков

• Управление исполнением потоков

• Управление разделяемыми ресурсами процесса

Создание потока:

int pthread_ create( pthread_ t * thread, pthread_ attr_ t * attr,  void*(*thread_function)(void * ), void * arg ),

  •  thread –указатель на идентификатор созданного потока
  •  attr – атрибуты потока
  •  third argument – функция, которую поток будет исполнять
  •  arg – аргументы функции (обычно структура)
  •  Функция возвращает 0 при успехе.

Ожидание завершения потока:

int pthread_ join( pthread_ t thread, void * * thread_ return )

  •  Основной поток дожидается завершения потока с идентификатором  thread.
  •  Второй аргумент – значение возвращаемое потоком
  •  Функция возвращает 0 при успехе.
  •   Следует всегда дожидаться завершения потока.

Пример программы с использованием POSIX Threads

#include <pthread.h>

#include <stdio.h>

#include <string.h>

void *potok(void *arg)

{

printf(“Работает поток%s\n”, (char*)arg);

return 0;

}

main(int argc, char *argv[])

{

int r, rc;

pthread_t threads;

if (argc>1)

{

threads=(pthread_t *)malloc((argc-1)*sizeof(pthread_t));

for(i=1; i<argc; i++)

{

rc=pthread_create(&(threads[i-1]),NULL, potok, argv[i]);

if (rc!=0) exit(-1);

}

for(i=1; i<argc; i++)

{

rc=pthread_join(threads[i-1]),NULL);

if (rc!=0) exit(-2);

}

}

}

Механизмы синхронизации потоков

Выполнение потоков по одной и той же функции может занимать разное время.

mynumber = counter;

counter++;

Критические секции выполняются строго одним процессором.

Для POSIX – это любая последовательность операторов, которая должна выполняться, не прерываясь, на одном процессоре.

Взаимное иключение (mutex):

  1.  Ограничивает доступ множества потоков к одному ресурсу в разделяемой памяти
  2.  Обеспечивает locking/unlocking критического участка кода, где разделяемый ресурс модифицируется.

Каждый поток ждет пока mutex будет разблокирован (потоком, который его блокировал) прежде чем войти в критическую секцию.

Базовые функции:

int pthread_ mutex_ init(pthread_ mutex_ t * mutex, const pthread_ mutexattr_ t * mutexattr);

int pthread_ mutex_ lock(pthread_ mutex_ t * mutex);

int pthread_ mutex_ unlock(pthread_ mutex_ t * mutex);

int pthread_ mutex_ destroy(pthread_ mutex_ t * mutex);

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

Семафоры:

  1.  Ограничивает количество потоков, исполняющих блок кода.
  2.  Аналогичен mutex-ам

Основные функции:

  1.  Создание: int sem_ init(sem_ t * sem, int pshared, unsigned int value);

pshared  - значение 0 означает, что семафор локален для процесса

Начальное значение для семафора устанавливается в  value.

  1.  Уничтожение: int sem_ destroy(sem_ t * sem);

Результат действий с использованием уничтоженного семофора не определен.

Управление семафором:

  •  int sem_ post(sem_ t * sem) - а увеличивает значение семафора на  1 ;
  •  int sem_ wait(sem_ t * sem) - уменьшает значение семафора на 1; предварительно дождавшись пока значение не станет больше 0;

Условные переменные.

Лекция 14

Среда Open MP

OpenMP [omp] — это API-интерфейс, который является отраслевым стандартом для создания параллельных приложений для компьютеров с совместным использованием памяти. Главная задача OpenMP — облегчить написание программ, ориентированных на циклы. Такие программы часто создаются для высокопроизводительных вычислений. Кроме того, в OpenMP были включены компоненты для поддержки таких параллельных алгоритмов как SPMD, "главный и рабочий процесс", конвейерный и т.д.

OpenMP стал очень успешным языком параллельного программирования. Он имеется на каждом компьютере с совместным использованием памяти, выходящем на рынок. Кроме того, недавно в Intel был создан вариант OpenMP для поддержки кластеров. OpenMP поддерживает такой стиль программирования, при котором параллелизм добавляется постепенно, пока имеющаяся последовательная программа не превратится в параллельную. Впрочем, это преимущество является и самым слабым местом OpenMP. Если параллелизм добавляется постепенно, программист может не выполнить широкомасштабную перестройку программы, которая часто необходима для достижения максимальной производительности.

Текущую версию можно посмотреть на сайте www.openmp.org

Основные компоненты:

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

Модель выполнения программы

Возможны вложенные ветвления

Модель памяти

Данные:

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

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

Структура программы

#include <stdio.h>

#include <omp.h>

main ()

{

  # pragma omp parallel      

       print f (“Работает поток\n”);

}

Применяется к следующему оператору или блоку. Имеет единую точку входа и точку выхода.

Для создания потока в OpenMP используется конструкция "parallel".

#pragma omp parallel  

Если такая конструкция используется без уточняющих операторов, то число потоков, которые создает программа, определяется средой выполнения (обычно это число равно числу процессоров или ядер). Каждый поток будет выполнять блок инструкций, который следует за прагмой parallel. Это может быть почти любой набор разрешенных инструкций в C; единственным ограничением является запрет на переходы внутрь этого блока инструкций или из него. Если потоки выполняют весь набор инструкций, а результат работы программы должен быть осмысленным, то потоки не должны беспорядочно перемещаться внутрь конструкции в рамках параллельного участка или из нее. В OpenMP это - общее ограничение. Такой блок инструкций без переходов называется "структурированным блоком".

Опции:

num_threads (5) – 5 раз выведется, вместо 5 можно использовать переменную, 5 – число потоков.

Библиотечные функции – позволяют управлять вычислительным процессом:

  •  Возвращает число доступных процессоров

int omp_get_num.procs (void)  - возвращает значение (можно узнать сколько процессов)

  •  Возвращает число потоков в группе

int omp_get_num_threads(void)

  •  Эквивалент ранга процесса

int omp_get_threads_num(void)

Вид переменных устанавливается явно или по умолчанию.

Основные правила:

  1.  Переменные, объявленные вне блока параллельного выполнения, будут общие
  2.  Статические переменные тоже являются общими
  3.  Автоматические переменные, объявленные внутри параллельного блока – индивидуальны
  4.  Локальные переменные и формальные параметры функции, вызываемые внутри параллельного блока- индивидуальны.

Существуют опции директивы параллели:

  •  private – определяет список переменных, которые будут индивидуальны для потоков, выполненных параллельно
  •  firstprivate – инициализация индивидуальных переменных, которые получат значения, равные значению переменных в главном потоке, в момент вхождения в параллельный участок
  •  reduction (оператор: список)

reduction (+:t) – в конце параллельного блока (все значения индивидуальных переменных t будут суммироваться)

Синхронизация

Выполняется с помощью atomic.

Критические секции critical [] – секции с одним и тем же именем не могут выполняться одновременно.

Директива master выделяет действие, которое выполняется только главным потоком.

# pragma omp master

{<действие}

Параллельное выполнение циклов позволяет получить ускорение. В технологии Open MP пользователь сам выбирает циклические участки, которые надо выполнить параллельно. Компилятор это не отслеживает.

Псевдо-код:

#pragma omp parallel for

for (i=0; i<n; i++)

# pragma omp atomic

S+=a[i]*b[i];

return S;

Можно ускорить:

#pragma omp parallel for

reduction (+, S)

for (i=0; i<n; i++)

# pragma omp atomic

S+=a[i]*b[i];

return S;

Функция shedule позволяет задать несколько режимов:

  •  статическое распределение по данному количеству
  •  динамическое распределение (нагружать освободившиеся процессы)

Лекция 15.

Обзор средств параллельного и распределенного программирования.

Технология DVM (Digital Virtual Machine)-выполнена институтом Прикладной математики Академии Наук.

Принципы реализации этой системы:

  1.  Высокоуровневая модель выполнения программ;
  2.  Спецификация параллельного программирования невидимы для обычных трансляторов;
  3.  Модель языковых конструкций параллельного программирования близка к модели выполнения программы;
  4.  Основная работа по выполнению программы реализуется системой DVM;

Система DVM базируется на библиотеке MPI, следовательно, переносимость относительно платформы. Синтаксис и семантика директив DVM практически совпадает с синтаксисом и семантикой языка Си.

Структурные особенности модели DVM – программ:

  1.  Выполняется на виртуальной MPI – машине (но есть и реализации на PVM);
  2.  Виртуальная многопроцессорная система представляется как многомерная решетка процессоров;
  3.  При запуске выполнение программы начинается сразу на всех процессорах, при этом 1 процесс выполняет поток управления;
  4.  Допускается иерархия распараллеливания (на верхнем уровне выполняются  независимые по данным задачи, а на нижних- параллельные циклы. В конце ветвей или задач выполняется редукция);
  5.  При входе в параллельный блок поток управления разбивается на несколько потоков;
  6.  Все переменные репродуцируются  по процессам и являются при этом локальными переменными;
  7.  Оператор присваивания выполняется в режим собственных вычислений (результат выполнения этого оператора передается этому процессору, которому доступна переменная из левой части оператора);

Существует возможность отображения задач на секции решетки. Отображение может быть статическим или динамическим. Существуют различные режимы работы с данными. Доступно редуцирование.

Реализуется и используется система DVM на различных сетях: HP, IBM, SUN; OC: UNIX, Windows.

Документация: www.keldysh.ru/dvm

Язык mpC

Предназначен для организации вычислений на неоднородных сетях.

Характерные принципы:

  1.  При организации таких вычислений не указывается, сколько процессов используется и на каких процессорах. Вместо этих настроек используется понятие-сеть. После задания сети определяется отображение виртуальных процессоров на реальные процессы.
  2.  Синхронизация – основное средство.

Язык Occam

Минимальными средствами решена задача разработки системы программирования на транспьютерах.

Фирма INMOS – производитель транспьютеров. Базовые элементы: декларации и три процесса (присваивание, ввод, вывод) .Эти три процесса объединяются в реальные процессы с помощью конструкторов:

  •  Последовательный – создает участки с последовательным выполнением
  •  Параллельный
  •  Защищенного взаимодействия

Язык CSP

Моделирование приложений. Все взаимодействуется в результате событий. События:

  •  присоединение (последовательное выполнение программы)
  •  рекурсия участка программ
  •  защищенный выбор (моделирование недетерминированного участка)

Язык Linda

Язык разделяемых переменных и асинхронных сообщений. Любой последовательный язык можно дополнить примитивами Linda и получить параллельный язык.

Портфель задач. Задача – единица работы. Задача помещается в некий портфель, который разделяется процессами. Разделяется по следующей схеме:

  1.  получить задачу
  2.  проверить наличие задачи, если нет – завершить процесс

Нужно задать задачу, определить портфель, определить программу решения задачи, определить критерий окончания работы.

Для реализации: использование языка С с внедренным в него примитивами языка Linda.

Литература:

  •  В.П Гергель  «Теория и практика параллельных вычислений» , 2007


 

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

4077. Исследование теплового излучения абсолютно чёрного тела 113 KB
  Цель работы – исследование температурной зависимости энергетической светимости абсолютно черного тела. Приборы и принадлежности –лабораторная работа выполняется на установке ФПК-11, которая включает: - объект исследования – тер...
4078. Поляризация света. Закон Малюса 1.05 MB
  Цель работы: ознакомление с методами получения линейно поляризованного света, некоторыми его свойствами и опытная проверка закона изменения интенсивности света при прохождении поляризованным светом анализатора (закон Малюса). Приборы и принадлежност...
4079. Исследование качества полированной поверхности с помощью микроинтерферометра Линника 788.5 KB
  Цель работы – знакомство с явлением интерференции света и с его использованием в метрологии. Получение практических навыков работы с высокоточным измерительным оптическим прибором и определение качества полированной поверхности исследуемого обр...
4080. Исследование интерференции света и определение длины волны используемого излучения 247.5 KB
  Цель работы - изучение методов наблюдения интерференционной картины и измерения ее параметров, определение длины волны используемого излучения. Приборы и принадлежности Оптическая скамья. Лазер. Бипризма Френеля. Линзы. ...
4081. Обработка результатов физического эксперимента 391.5 KB
  Цель работы – ознакомление с методами оценки результатов измерений и расчета погрешностей. Приборы и принадлежности: исследуемые образцы штангенциркуль микрометр лабораторная установка FPM - 01 пакет компьютерных программ по моделированию...
4082. Изучение центрального абсолютно упругого и неупругого соударения шаров 749 KB
  Цель работы - изучение центрального абсолютно упругого и неупругого соударения шаров. Исследование упругого соударения шаров Физические закономерности, возникающие при ударе двух тел, широко используются в науке и технике, например, при ковке металл...
4083. Изучение равноускоренного движения на машине Атвудаи ее компьютерной модели 1.03 MB
  Дана методика и описаны эксперименты по проверке основных формул кинематики и динамики равноускоренного прямолинейного движения. Эксперименты могут быть проведены как на реальной лабораторной установке (машине Атвуда), так и на ее компьютерной модел...
4084. Изучение вращательного движения с помощью маятника Обербека и его компьютерного имитатора 183.5 KB
  Изложены основные положения кинематики и динамики твердого тела. Приведена методика и описан эксперимент по проверке основного закона динамики вращательного движения. Эксперимент может быть выполнен как на реальной лабораторной установке (маятнике ...
4085. Определение коэффициента трения с помощью установки ФПМ-02 и ее компьютерного имитатора 646 KB
  Цель работы: изучить свободные затухающие колебания наклонного маятника освоить методику определения коэффициента трения. Приборы: установка для определения коэффициента трения ФПМ-02, а также IBM-совместимый персональный компьютер и пакет компьют...