Параллельные вычисления с использованием библиотеки PVM

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования  
«Смоленский государственный университет»

 

 

Факультет экономики и управления

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

 

 

 

 

 

Курсовая работа

ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ С ИСПОЛЬЗОВАНИЕМ БИБЛИОТЕКИ PVM.

 

 

 

 

 

Выполнил

студент 3 курса очной формы обучения

направления подготовки

«Прикладная информатика»

МАРКЕЛОВ Владислав Сергеевич

 

 

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

ст. преподаватель

БЛАКУНОВ Игорь Олегович

 

 

 

 

 

 

 

 

Смоленск

2014

ОГЛАВЛЕНИЕ

 

 

ВВЕДЕНИЕ………………………………………………………………….3

ГЛАВА 1.ОПИСАНИЕ КЛАСТЕРНЫХ СИСТЕМ И ХАРАКТЕРИСТИКА БИБЛИОТЕК ПАРАЛЛЕЛИЗМ………………….4

1.1. ТИПЫ КЛАСТЕРНЫХ СИСТЕМ……………………………...……..4

1.2. ПОПУЛЯРНЫЕ БИБЛИОТЕКИ ПАРАЛЛЕЛИЗМА.

 АНАЛОГИ PVM…………………………………………………..……….7

1.3.  ОПИСАНИЕ СИСТЕМЫ PVM……………………………………...13

ГЛАВА 2. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ…….16

2.1. ОПИСАНИЕ ОБОРОДУВАНИЯ И ПРОГРАММНОГО

 ОБЕСПЕЧЕНИЯ………………………………………………………......16

2.2. УСТАНОВКА И НАСТРОЙКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ КЛАСТЕРА………………………………………………………………....17

2.3. ГИПОТЕЗА ГОЛЬДБАХА…………………………………………....21

2.4. ПРОЦЕСС КОМПИЛЯЦИИ СОБСТВЕННОЙ  ПРОГРАММЫ ДЛЯ РАБОТЫ С PVM…………………………………...……………………....22

2.5. ВЫПОЛНЕНИЕ ПРОГРАММЫ…………………………………......23

ЗАКЛЮЧЕНИЕ…………………………………………………………….26

СПИСОК ЛИТЕРАТУРЫ………………………………………………….27

ПРИЛОЖЕНИЕ А. ЛИСТИНГ ПРОГРАММЫ В С++…………………..28

 

 

ВВЕДЕНИЕ

Данная исследовательская работа посвящена ознакомлению с  программированием параллельных  вычислительных  процессов с использованием пакета программ PVM (Parallel  Virtual Machine).

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

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

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

Данное исследование ставит перед собой цель рассмотреть возможности PVM на примере конкретной задачи, разобраться из чего состоит PVM, каким образом работать в ней, какие преимущества и недостатки имеет эта библиотека?

 

ГЛАВА 1. ОПИСАНИЕ КЛАСТЕРНЫХ СИСТЕМ И ХАРКТЕРИСТИКА БИБЛИОТЕК ПАРАЛЛЕЛИЗМА.

 

1. . ТИПЫ КЛАСТЕРНЫХ СИСТЕМ.

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

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

Разберемся в типах кластерных систем. Они различаются по типу памяти — общая (shared) или распределенная (distributed), и по типу управления — один управляющий узел(SIMD) и несколько(MIMD). Получается, четыре вида кластерных систем.

 

Общая.

Рис. 1

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

 

Распределенная.

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

Рис. 2

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

 

 

SIMD.

SIMD — Singe Instruction stream, Multiple Data stream. Управляющий узел один, он отправляет инструкции всем остальным процессорам. Каждый процессор имеет свой набор данных для работы.

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

MIMD.

MIMD — Multiple Instruction stream, Multiple Data Stream. Каждый процессор имеет свой собственный управляющий модуль, каждый процессор может выполнять разные инструкции.

MIMD-машины обладают более  широким функционалом, поэтому в  наших пользовательских компьютерах  используются именно они. Любые  устройства, использующие хотя бы двухъядерный процессор - MIMD-машины с общей памятью. MIMD с  распределенной памятью это суперкомпьютеры вроде IBM Blue Gene или кластеры.

Чтобы заставить работать описанные типы кластеров по назначению используют программные инструменты параллелизма, например, PVM

1.2. ПОПУЛЯРНЫЕ БИБЛИОТЕКИ ПАРАЛЛЕЛИЗМА. АНАЛОГИ PVM.

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

 

Message Passing Interface.

В 1994 г. был принят стандарт механизма передачи сообщений MPI (Message Passing Interface) . Он готовился с 1992 по 1994 гг. группой Message Passing Interface Forum, в которую вошли представители более чем 40 организаций из Америки и Европы. Основная цель, которую ставили перед собой разработчики MPI - это обеспечение полной независимости приложений, написанных с использованием MPI, от архитектуры многопроцессорной системы, без какой-либо существенной потери производительности. По замыслу авторов это должно было стать мощным стимулом для разработки прикладного программного обеспечения и стандартизованных библиотек подпрограмм для многопроцессорных систем с распределенной памятью. Подтверждением того, что эта цель была достигнута, служит тот факт, что в настоящее время этот стандарт поддерживается практически всеми производителями многопроцессорных систем. Реализации MPI успешно работают не только на классических MPP системах, но также на SMP системах и на сетях рабочих станций (в том числе и неоднородных).

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

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

В первую очередь MPI ориентирован на системы с распределенной памятью, то есть когда затраты на передачу данных велики, в то время как OpenMP ориентирован на системы с общей памятью (многоядерные с общим кэшем). Обе технологии могут использоваться совместно, дабы оптимально использовать в кластере многоядерные системы. Самая последняя версия на сегодняшний день MPI 3.0 вышла 21 сентября 2012 года.

OpenMP.

OpenMP (Open Multi-Processing) — открытый стандарт для распараллеливания программ на языках Си, Си++ и Фортран.

Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB) .

Первая версия появилась в 1997 году, предназначалась для языка Fortran. Для С/С++ версия разработана в 1998 году. В 2008 году вышла версия OpenMP 3.0.

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

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

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

 

Linda.

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

Язык Linda позволяет писать параллельные программы на обычных языках: языке Си, языке Фортран, языке Лисп, дополняя их операциями организации межпроцессорного обмена данными. Важной характеристикой языка Linda является то, что он может использоваться для написания программ, выполняемых на суперкомпьютерах с различной архитектурой. Благодаря тому, что Linda позволяет большой прикладной процесс разбивать на много небольших, это упрощает и распараллеливает этот процесс. Между тем, нужно соблюдать и некоторую осторожность. Если процесс будет разделен на большое число мелких, то теряется много времени на обмен данными между процессами, результатами и получением новых заданий.

 

p4 Parallel Programming System.

p4 Parallel Programming System представляет  собой библиотеку макросов (макрос — программный алгоритм действий, записанный пользователем) и подпрограмм, разработанных в Аргоннской национальной лаборатории для программирования разнообразных параллельных машин в С++ и Fortran. Ее предшественницей была m4 - система, описанная Холтом, Райнхартом и Уинстоном в книге "Портативные программы для параллельных процессов”. Нынешняя система P4 поддерживает те же основные вычислительные модели, описанные там (мониторы для модели с разделяемой памятью, передачи сообщений для модели распределенной памяти, а также поддержку объединения двух моделей) при значительном увеличении легкость и гибкость использования.

Система р4 портативна. Она проста в установке и весьма эффективна в использовании. Система может быть применена для программирования сети рабочих станций с распределенной памятью, параллельных суперкомпьютеров, как в Intel Paragon, мыслящими машинами СМ-5, а также IBM SP-1, а также многопроцессорных разделяемой памятью, как Кендалл-сквер. Сейчас р4 установлена на многих суперкомпьютерах. Текущий релиз р4 – версия 1.3.

 

HPF(High Performance Fortran).

High Performance Fortran (HPF) – это  высокоуровневая система программирования  с распараллеливанием данных, основанная на языке Фортран.

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