В данном отчете по практикуму рассматриваются программы с различными методами распараллеливания: MPICH2, OpenMP.

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

1. ПРАКТИЧЕСКАЯ РАБОТА №1

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

Задача данной практической работы - произвести установку, настройку и проверку интегрированной инструментальной среды программирования MicrosoftVisual Studio в части C++ и OpenMP.

1. 2. Загрузка и настройка

      1. Системные требования

Поддерживаемые операционные системы

• Windows 8.1 (x86 и x64)
• Windows 8 (x86 и x64)
• Windows 7 SP1 (x86 и x64)
• Windows Server 2012 R2 (x64)
• Windows Server 2012 (x64)
• Windows Server 2008 R2 SP1 (x64)

Требования к оборудованию

• Процессор с частотой 1,6 ГГц или более мощный
• 1 ГБ ОЗУ (1,5 ГБ при использовании виртуальной машины)
• 20 ГБ свободного дискового пространства
• Жесткий диск со скоростью вращения 5400 об/мин
• Видеоадаптер с поддержкой DirectX 9; минимально допустимое разрешение экрана — 1024 x 768

Дополнительные требования:

• Internet Explorer 10
• Обязательна установка KB2883200 (доступно через Центр обновления Windows)
• Для разработки под Windows Phone:
  • Разработка для Windows Phone 8.0 требует наличия Windows 8.1 (64-разрядной версии) или более новой версии
  • Разработка для Windows Phone 8.1 требует наличия Windows 8.1 (32-разрядной версии) или более новой версии
  • Для эмуляторов Windows Phone требуется выпуск Windows 8.1 Профессиональная (64-разрядная версия) или выше, а также процессор с поддержкой Client Hyper-V и преобразования адресов второго уровня (SLAT)

Если ваш компьютер отвечает требованиям к операционной системе, но не соответствует требованиям к оборудованию для работы с эмуляторами Windows Phone, вы сможете установить и запустить средства разработки для Windows Phone. Однако эмуляторы Windows Phone 8.0 и 8.1 не будут функционировать, и вам понадобится устройство для развертывания и тестирования приложений Windows Phone.

1. 2. 2. Загрузка

Для загрузки интегрированной инструментальной среды необходимо выбрать на официальном сайте Microsoft версию Microsoft Visual Studio (http://www.microsoft.com/ru-ru/download/details.aspx?id=30678). Из возможных предложений (см. Приложение 1) выбираем MicrosoftVisual Studio Ultimate 2012.

Из предложенных вариантов загрузки выбираем веб-установщик (vs_ultimate.exe).

В загруженной версии MicrosoftVisualStudioиспользуются  VisualC++ 2012 и OpenMP 2.0.

1. 2. 3. Инсталляция

Запускаем загруженный дистрибутив, предварительно указав директорию или оставив предложенный по умолчанию каталог, нажимаем кнопку «Далее» (рис. 1).

рис.

В следующем пункте предоставляется возможность выбора необязательно устанавливаемых компонентов (оставляем выбор по умолчанию - все) и нажимаем кнопку «Далее». В процессе установки компьютер должен иметь доступ в Интернет. Ход установки отображается в прогресс баре.

1. 2. 4. Запуск

После появления окна с сообщением о завершении установки нужно кликнуть на кнопку «Запустить» (рис. 2Ошибка! Источник ссылки не найден.).

рис.

Далее появится окно с информацией о периоде бесплатного использования (30 дней). Нажимаем «Отмена».

В следующем окне нужно выбрать параметры среды для использования по умолчанию, я выбрала «Параметры разработки VisualC++». Происходит запуск приложения и появляется окно «Диспетчер содержимого справки» (рис. 3). Выбираем «Да».

рис.

1. 2. 5. Настройка

Установимпараметр компилятора OpenMP в среде разработки Visual Studio:

1. Откроем диалоговое окно Страницы свойств проекта (Меню проект, «Название проекта», рис. 4Ошибка! Источник ссылки не найден.).
2. Развернем узел Свойства конфигурации.
3. Развернем узел C/C++.
4. Выберем страницу свойств Язык.
5. Изменим значение свойства Поддержка OpenMP.
6. По завершении произведенного выбора нажмем «ОК».

рис.

1. 3. Создание приложения

      1. Создание проекта

Для создания проекта можно использовать сочетание клавиш: CTRL + SHIFT + N или выбрать соответствующий пункт в строке меню (рис. 5).

рис.

1. 3. 2. Выбор шаблона приложения

Выбираем шаблон и добавляем новый проект кода в управление версиями. Рекомендуется поместить новый проект в папку c:\Users\YourName\Source\Repos\. Выбираемконсольное приложение (рис. 6). Также на этом шаге есть возможность выбрать директорию для сохранения проекта и его название.

рис.

Появляется мастер приложений Win32 (рис. 7Ошибка! Источник ссылки не найден.). Нажимаем «Готово». Появляется «скелет» будущей программы (рис. 8).

рис.

рис.

1. 4. Написание кода программы

Используя предложенный «скелет», записываем исходный код на С++ с использованием OpenMP.

1. 4. 1. Программа“Hello, World”

#include "stdafx.h"

#include

int main()

{

#pragma omp parallel

printf("Hello, World!");

}

1. 4. 2. Программа “Hello, World” с выводом номеров потоков

#include "stdafx.h"

#include "omp.h"

void main()

{

#pragma omp parallel

{

int ID=omp_get_thread_num();

printf("Hello,World!(%d)\n", ID);

}

}

1. 5. Запуск приложения

Для компиляции кода нужно запустить локальный отладчик Windows или нажать на клавиатуре Ctrl+F5.

В поле вывода информации появляются записи о ходе выполнения программы (рис. 9) или открывается окно с результатом работы программы (рис. 10, рис. 11).

рис.

1. 5. 1. Программа “Hello, World”

рис.

1. 5. 2. Программа “Hello, World” с выводом номеров потоков

рис.

1. 6. Выводы

Итогом проведения практической работы №1 стали установленная интегрированная инструментальная среда программирования MicrosoftVisual Studio Ultimate 2012, созданный в ней с использованием OpenMP проекты «Hallo, World!».

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

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

2. ПРАКТИЧЕСКАЯ РАБОТА №2

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

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

На первом этапе использовать две матрицы размером 10*10, заполнить их числами двоичной системы счисления.

На втором этапе выполнять вычисления для матриц размером 1000*1000.

Каждый из этапов выполнять без распараллеливания и с распараллеливанием по строкам (столбцам), сравнить оба метода.

Цели данной работы:

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

2. 2. Используемое оборудование

2. 3. Написание программы

2.3.1. Умножение матриц размером 10*10

2.3.1.1. Без распараллеливания процессов

Код программы:

#include "stdafx.h"

#include

#include //для работы с файлами

usingnamespacestd; //для cout

#include

#include

#include //длятаймера

#include

int _tmain(int argc, _TCHAR* argv[])

{

cout << "Отчет находится в файле log.txt" << endl;

cout << "Идет процесс вычисления. Пожалуйста, не закрывайте программу." <

std::fstream logFile;

logFile.open("log.txt", std::ios_base::out);

std::cout.rdbuf(logFile.rdbuf());// меняембуфер cout длявыводавфайл

//умножение матриц

int n = 10, i, l, j, s;

int **a = new int*[n];

int **b = new int*[n];

int **c = new int*[n];

//заполнение матриц

srand(time(NULL));//для лучшего распределения рандома

cout<< "Матрица 1:" << endl;

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

{

a[i] = new int[n];

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

{

a[i][j] = rand() % 2 + 0;

cout<< a[i][j] << " ";

}

cout<< endl;

}

cout<< "Матрица 2:" << endl;

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

{

b[i] = new int[n];

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

{

b[i][j] = rand() % 2 + 0;

cout<< b[i][j] << " ";

}

cout<< endl;

}

//процессумножения

LARGE_INTEGER freq;

LARGE_INTEGER t1;

LARGE_INTEGER t2;

if (QueryPerformanceFrequency(&freq))

{

QueryPerformanceCounter(&t1);

for (i = 0; i < n; i++)//строки

{

c[i] = new int[n];

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

{

s = 0;

for (j = 0; j < n; j++)// столбцы

{

s += a[i][j] * b[j][l];

}

c[i][l] = s;

}

}

QueryPerformanceCounter(&t2);

}

else

cout<< "ОШИБКА!!! Счетчик монитора производительности не поддерживается системой..." << endl;

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

cout<< "Результирующаяматрица:" <

for (i = 0; i

{

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

{

cout<< c[i][j] << " ";

}

cout<< endl;

}

double dt = t2.QuadPart - t1.QuadPart;

double elapsed_time = 1000 * dt / freq.QuadPart; // времявыполнения

cout<< "Времявычисления:" << endl;

cout<< elapsed_time << " миллисекунды." << endl;

return 0;

}

Результат в файле 10.txt

2.3.1.2. С использованием распараллеливания

a)По строкам

• Без указания числа потоков

Кодпрограммы:

#include "stdafx.h"

#include

#include //для работы с файлами

using namespace std; //для cout

#include

#include

#include //длятаймера

#include

int _tmain(int argc, _TCHAR* argv[])

{

cout << "Отчет находится в файле log.txt" << endl;

cout << "Идет процесс вычисления. Пожалуйста, не закрывайте программу." <

std::fstream logFile;

logFile.open("log.txt", std::ios_base::out);

std::cout.rdbuf(logFile.rdbuf());// меняембуфер cout длявыводавфайл

//умножение матриц

int n = 10, i, l, j, s;

int **a = new int*[n];

int **b = new int*[n];

int **c = new int*[n];

//заполнение матриц

srand(time(NULL));//для лучшего распределения рандома

cout<< "Матрица 1:" << endl;

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

{

a[i] = new int[n];

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

{

a[i][j] = rand() % 2 + 0;

cout<< a[i][j] << " ";

}

cout<< endl;

}

cout<< "Матрица 2:" << endl;

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

{

b[i] = new int[n];

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

{

b[i][j] = rand() % 2 + 0;

cout<< b[i][j] << " ";

}

cout<< endl;

}

//процессумножения

LARGE_INTEGER freq;

LARGE_INTEGER t1;

LARGE_INTEGER t2;

if (QueryPerformanceFrequency(&freq))

{

QueryPerformanceCounter(&t1);

#pragma omp parallel for

for (i = 0; i < n; i++)//строки

{

c[i] = new int[n];

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

{

s = 0;

for (j = 0; j < n; j++)// столбцы

{

s += a[i][j] * b[j][l];

}

c[i][l] = s;

}

}

QueryPerformanceCounter(&t2);

}

else

cout<< "ОШИБКА!!! Счетчик монитора производительности не поддерживается системой..." << endl;

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

cout<< "Результирующаяматрица:" <

for (i = 0; i

{

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

{

cout<< c[i][j] << " ";

}

cout<< endl;

}

double dt = t2.QuadPart - t1.QuadPart;

double elapsed_time = 1000 * dt / freq.QuadPart; // времявыполнения

cout<< "Времявычисления:" << endl;

cout<< elapsed_time << " миллисекунды." <

return 0;

}

Результатвфайле 10pstr.txt

• 8 потоков. Добавление строки omp_set_num_threads(8);
• 16 потоков. Добавление строки omp_set_num_threads(16);
• 32 потока. Добавление строки omp_set_num_threads(32);

б) По столбцам

Код программы:

#include "stdafx.h"

#include

#include //для работы с файлами

using namespace std; //для cout

#include

#include

#include //длятаймера

#include

int _tmain(int argc, _TCHAR* argv[])

{

cout << "Отчет находится в файле log.txt" << endl;

cout << "Идет процесс вычисления. Пожалуйста, не закрывайте программу." <

std::fstream logFile;

logFile.open("log.txt", std::ios_base::out);

std::cout.rdbuf(logFile.rdbuf());// меняембуфер cout длявыводавфайл

//умножение матриц

int n = 10, i, l, j, s;

int **a = new int*[n];

int **b = new int*[n];

int **c = new int*[n];

//заполнение матриц

srand(time(NULL));//для лучшего распределения рандома

cout<< "Матрица 1:" << endl;

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

{

a[i] = new int[n];

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

{

a[i][j] = rand() % 2 + 0;

cout<< a[i][j] << " ";

}

cout<< endl;

}

cout<< "Матрица 2:" << endl;

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

{

b[i] = new int[n];

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

{

b[i][j] = rand() % 2 + 0;

cout<< b[i][j] << " ";

}

cout<< endl;

}

//процессумножения

LARGE_INTEGER freq;

LARGE_INTEGER t1;

LARGE_INTEGER t2;

if (QueryPerformanceFrequency(&freq))

{

QueryPerformanceCounter(&t1);

for (i = 0; i < n; i++)//строки

{

c[i] = new int[n];

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

{

s = 0;

#pragma omp parallel for

for (j = 0; j < n; j++)// столбцы

{

s += a[i][j] * b[j][l];

}

c[i][l] = s;

}

}

QueryPerformanceCounter(&t2);

}

else

cout<< "ОШИБКА!!! Счетчик монитора производительности не поддерживается системой..." << endl;

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

cout<< "Результирующаяматрица:" <

for (i = 0; i

{

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

{

cout<< c[i][j] << " ";

}

cout<< endl;

}

double dt = t2.QuadPart - t1.QuadPart;

double elapsed_time = 1000 * dt / freq.QuadPart; // времявыполнения

cout<< "Времявычисления:" << endl;

cout<< elapsed_time << " миллисекунды." <

return 0;

}

Результатвфайле10pstolb.txt

2.3.2. Умножение матриц размером 100*100

2.3.2.1. Без распараллеливания процессов

Код программы аналогичный, n=100;

Результат в файле 100.txt

2.3.2.2. С использованием распараллеливания

a) По строкам

• Без указания числа потоков

Код программы аналогичный, n=100;

Результат в файле 100pstr.txt

• 8 потоков
• 16 потоков
• 32 потока

б) По столбцам

Код программы аналогичный, n=100;

Результат в файле 100pstolb.txt

2.3.3. Умножение матриц размером 100*100

2.3.3.1. Без распараллеливания процессов

Код программы аналогичный, n=1000;

2.3.3.2. С использованием распараллеливания

a) По строкам

• Без указания числа потоков

Код программы аналогичный, n=100;

Результат в файле 1000pstr.txt

• 8 потоков
• 16 потоков
• 32 потока

б) По столбцам

Код программы аналогичный, n=1000;

Результат в файле 1000pstolb.txt

2.4. Результаты

1) Время вычисления с условием фиксированного (по умолчанию) количества потоков(мс).

Коэффициент ускорения (tпар/tпосл)

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

Коэффициент ускорения (tпар/tпосл)

1. 5. Выводы

а) без указания количества потоков

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

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

Для матриц размерности 1000*1000 и более эффективен любой метод распараллеливания (но по строкам предпочтительнее).

б) с заданным количеством потоков

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

3. ПРАКТИЧЕСКАЯ РАБОТА №3

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

Задачами данной практической работы являются установка и настройка интегрированной среды распределенного программирования C++ и MPICH.

Для проверки правильности установки необходимо установить 10 процессов и вывести на печать сообщение “Привет, мир!”.

3. 2. Используемое оборудование

Мной использовался один компьютер:

1. ПланшетAcerAspireSwitch 10набазеWindows 8.1 (32-х разрядной)

3. 3. Установка

Вначале нужно скачать последнюю версию MPICH2 с этой страницы: http://www.mpich.org/downloads/.

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

Если у вас WindowsVistaили Windows 8 (8.1), то выполните следующие действия:

• Запустите командную строку от имени администратора

или

• Откройте файл в командной строке

Запустится процесс установки.

Во время установки вам нужно будет ввести пароль для доступа к менеджеру процессов SMPD. Вы должны ввести одинаковый пароль на всех компьютерах:

Если Windows спросит, разрешить ли доступ в сеть программе smpd.exe, то нажмите «Разрешить».

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

Нажмите Пуск → Настройка → Панель управления → Администрирование → Службы. Вы должны увидеть «MPICH2 Process Manager» в списке служб. Эта служба должна работать. Если служба в списке отсутствует, то вы, видимо, не запустили инсталлятор от имени администратора.

Теперь проверим, разрешён ли доступ в сеть для MPICH. Зайдите в Пуск → Настройка → Панель управления → Брандмауэр Windows. Там нажмите «Разрешение обмена данными с приложениями в брандмауэре Windows». Вы должны увидеть в списке разрешённых программ «Process launcher for MPICH2 applications» и «Process manager service for MPICH2 applications».

Если какая-то из перечисленных программ отсутствует в списке разрешённых программ, то вы можете добавить её вручную. Для этого нажмите кнопку «Разрешить другое приложение...», и добавьте C:\​program files\​mpich2\​bin\​mpiexec.exe, если отсутствует «Process launcher for MPICH2 applications», и C:\​program files\​mpich2\​bin\​smpd.exe, если отсутствует «Process manager service for MPICH2 applications».

3. 4. Настройка

Рассмотрим настройку MPICH на примере работы с одним компьютером.

Запустите Wmpiregister на том компьютере, с которого вы собираетесь запускать MPI-программы. Окно программы выглядит следующим образом:

Введите имя пользователя и пароль в окне программы и нажмите кнопку «Register». Должна появиться надпись «Password encrypted into the Registry», после чего можно закрыть окно кнопкой «OK». Если ваш компьютер подключен к учетной записи Microsoft, то для начала перейдите на локальную учетную запись.

После этого окно программы больше не будет появляться при выполнении каких либо действий MPICH. Если вы захотите впоследствии удалить имя пользователя и пароль из реестра, то вам нужно будет снова запустить эту программу, и нажать кнопку «Remove».

Чтобы настроить менеджеры процессов MPICH можно использовать программу Wmpiconfig.Нам это не требуется, т.к. мы работаем с одним компьютером.

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

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

Для запуска MPI-программ в комплект MPICH2 входит программа с графическим интерфейсом Wmpiexec, которая представляет собой оболочку вокруг соответствующей утилиты командной строки Mpiexec. Окно программы Wmpiexec показано на рисунке (обратите внимание, что включён флажок «more options»).

3. 5. Создание MPI-программы в Visual Studio

В строке меню выбрать «Проект-Свойства проекта – свойства конфигурации – каталоги VC++ - каталоги включения» и нажать «изменить».

Выбратьдиректорию C:\Program Files\MPICH2\include.

Нажать «ОК».

В строке меню выбрать «Проект-Свойства проекта – свойства конфигурации – каталоги VC++ - каталоги библиотек – изменить».

Директория C:\Program Files\MPICH2\lib. В итоге окно должно выглядеть следующим образом:

Нажать «Применить».

В строке меню выбрать «Проект - Свойства проекта – свойства конфигурации – компоновщик – ввод – дополнительные зависимости».

Добавить«mpi.lib cxx.lib» (с переходом на новую строку).

Нажать«Применить», «ОК».

3. 6. Написание программы

3.6.1. Используя приложение wmpiexec

Сначала необходимо написать программу в среде VisualStudio.

Кодпрограммы:

#include "stdafx.h"

#include

#include

using namespace std;

int main(int argc, char **argv)

{

MPI_Init(&argc, &argv);

int rank, size;

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

MPI_Comm_size(MPI_COMM_WORLD, &size);

if (rank)

{

char buf[] = "Привет, мир!";

MPI_Send(buf, sizeof(buf), MPI_CHAR, 0, 0, MPI_COMM_WORLD);

}

else {

cout<< "Процесс №0 запущен" << endl;

for (int i(1); i

{

MPI_Status s;

MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &s);

int count;

MPI_Get_count(&s, MPI_CHAR, &count);

char *buf = new char[count];

MPI_Recv(buf, count, MPI_CHAR,

MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &s);

cout<< "Процесс № " << s.MPI_SOURCE << ": "

<

delete[] buf;

}

cout<< "Завершено." <

}

MPI_Finalize();

return 0;

}

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

Нужно разрешить доступ к сети.

Теперь открываем программу wmpiexec. В окне выбираем путь к полученному исполняемому файлу.

В задании нужно выбрать 10 процессов, указываем это число в окне и нажимаем кнопку «Execute». Результат видим в основном поле окна.

3. 7. Выводы

Итогом проведения практической работы №3стали установленная интегрированная среда распределенного программирования MPICH2 и созданный с ее помощью проект «Привет, мир!» с указанием числа процессов (10).

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

4. ПРАКТИЧЕСКАЯ РАБОТА №4

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

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

На первом этапе использовать две матрицы размером 10*10, заполнить их числами двоичной системы счисления.

На втором этапе выполнять вычисления для матриц размером 100*100.

На третьем этапе выполнять вычисления для матриц размером 1000*1000.

Каждый из этапов выполнять без распараллеливания и с распараллеливанием по строкам (столбцам), сравнить оба метода.

Цели данной работы:

• Вычислить отношение времени вычисления (коэффициент ускорения) с параллельным и последовательным методом – меньше или больше 1.
• Создать таблицы сравнения результатов измерений.
• Выполнить сравнение результатов с ПР№2.

4. 2. Написание программы

#include "stdafx.h"

#include

#include

#include

#include

#include

#include

#include

using namespace std; //для cout

int ProcNum;

int ProcRank;

int flag = 0;

int Size;

double *A;  double *B; double *C;

//------------------------------------------------------------

void PrintMatrix(double* pMatrix, int Size) {

for (int i = 0; i

cout<< endl;

for (int j = 0; j

printf("%7.2f ", pMatrix[i*Size + j]);

}

}

//------------------------------------------------------------

void RandInit(double* pMatrix, int Size) {

srand(0);

for (int i = 0; i

for (int j = 0; j

}

}

//-------------------------------------------------

void InitProcess(double* &A, double* &B, double* &C, int &Size) {

MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);

MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);

if (ProcRank == 0) {

do {

cout << "Введите размер массива (соответствует количеству процессов)." << endl;

cin >> Size;

if (Size == 0) cout << "Не указано количество процессов." << endl;

if (Size < ProcNum) cout << "Размер матрицы меньше количества процессов! " << endl;

if (Size%ProcNum != 0) cout << "Matrix size should be dividable by the number of processes!" <

} while ((Size< ProcNum) || (Size%ProcNum != 0));

}

if (Size<=20) flag = 1;

MPI_Bcast(&Size, 1, MPI_INT, 0, MPI_COMM_WORLD);

if (ProcRank == 0) {

A = new double[Size*Size];

B = new double[Size*Size];

C = new double[Size*Size];

RandInit(A, Size); RandInit(B, Size);

}

}

//-------------------------------------------------

void Flip(double *&B, int dim) {

double temp = 0.0;

for (int i = 0; i

for (int j = i + 1; j

temp = B[i*dim + j]; B[i*dim + j] = B[j*dim + i]; B[j*dim + i] = temp;

}

}

}

//-------------------------------------------------

void MatrixMultiplicationMPI(double *&A, double *&B, double *&C, int &Size) {

int dim = Size;

int i, j, k, p, ind;

double temp;

MPI_Status Status;

int ProcPartSize = dim / ProcNum;

int ProcPartElem = ProcPartSize*dim;

double* bufA = new double[dim*ProcPartSize];

double* bufB = new double[dim*ProcPartSize];

double* bufC = new double[dim*ProcPartSize];

int ProcPart = dim / ProcNum, part = ProcPart*dim;

if (ProcRank == 0) {

Flip(B, Size);

}

MPI_Scatter(A, part, MPI_DOUBLE, bufA, part, MPI_DOUBLE, 0, MPI_COMM_WORLD);

MPI_Scatter(B, part, MPI_DOUBLE, bufB, part, MPI_DOUBLE, 0, MPI_COMM_WORLD);

temp = 0.0;

for (i = 0; i

for (j = 0; j

for (k = 0; k

bufC[i*dim + j + ProcPartSize*ProcRank] = temp; temp = 0.0;

}

}

int NextProc; int PrevProc;

for (p = 1; p

NextProc = ProcRank + 1;

if (ProcRank == ProcNum - 1) NextProc = 0;

PrevProc = ProcRank - 1;

if (ProcRank == 0) PrevProc = ProcNum - 1;

MPI_Sendrecv_replace(bufB, part, MPI_DOUBLE, NextProc, 0, PrevProc, 0, MPI_COMM_WORLD, &Status);

temp = 0.0;

for (i = 0; i

for (j = 0; j

for (k = 0; k

temp += bufA[i*dim + k] * bufB[j*dim + k];

}

if (ProcRank - p >= 0)

ind = ProcRank - p;

else ind = (ProcNum - p + ProcRank);

bufC[i*dim + j + ind*ProcPartSize] = temp;

temp = 0.0;

}

}

}

MPI_Gather(bufC, ProcPartElem, MPI_DOUBLE, C, ProcPartElem, MPI_DOUBLE, 0, MPI_COMM_WORLD);

delete[]bufA;

delete[]bufB;

delete[]bufC;

}

//--------------------------------------------------------

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

double beg, end, serial, parallel = 0;

MPI_Init(&argc, &argv);

InitProcess(A, B, C, Size);

beg = MPI_Wtime();

MatrixMultiplicationMPI(A, B, C, Size);

end = MPI_Wtime(); parallel = end - beg;

if (ProcRank == 0) {

cout<< endl;

cout<< "Времявычислениясоставило: ";

printf("%7.4f", parallel);

cout<< " секунд"<

if (flag) {

cout << "Результирующая матрица" << endl;

PrintMatrix(C, Size);

}

}

MPI_Finalize();

delete[] A; delete[] B; delete[] C;

_getch();

}

4. 3. Результаты

      1. Без распараллеливания

Результаты последовательных вычислений указаны в пункте 2.4.

4. 3. 2. С распараллеливанием

Размер матрицы 10*10 (10 процессов)

Размер матрицы 100*100 (100 процессов)

Размер матрицы 1000*1000 (1000 процессов)

4. 4. Сравнение результатов использования MPICH2 и OpenMP

Для сравнения результатов возьмем лучшее время в использовании OpenMP, т.е. распараллеливание по строкам. Время указано в секудах.

Коэффициенты ускорения (tпар/tпосл):

Соответственно, метод эффективен, если коэффициент ускорения меньше единицы.

4. 5. Выводы

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

OpenMP

Данный метод эффективен только для матриц размером, превышающим миллион элементов. Также он оказался более эффективным, чем MPICH2 в матрице размером 100*100.

MPICH2

Данный метод показал себя как наиболее эффективный. Для размера матриц 10*10 и 1000*1000 время вычислений намного меньше, чем последовательным методом и параллельным с использованием OpenMP.

5. ПРАКТИЧЕСКАЯ РАБОТА№5

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

Задача данной практической работы – решение проблемы синхронизации при разработке параллельных алгоритмов - «Проблема обедающих философов».

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

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

Каждый философ может взять ближайшую вилку (если она доступна), или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

Задача сформулирована таким образом, чтобы иллюстрировать проблему избежания взаимной блокировки (англ. deadlock) — состояния системы, при котором прогресс невозможен. Также нельзя допустить состояния «голодной смерти» - ситуации, когда два соседних философа одновременно проголодаются и попытаются взять одну вилку.

5. 2. Написание программы

#include"stdafx.h"

#include"Philosophers_Win32API.h"

#include

#defineMAX_LOADSTRING  100

#defineIDB_START    101

#defineIDB_PAUSE    102

#defineLISTBOX_    1030

#defineLISTBOX_Info  1080

#defineN 5                // Количествофилософов

#defineLEFT(n) (n + 4) % N

#defineRIGHT(n) (n + 1) % N

int state[N];

HANDLE Semaphore;

int forks[N] = { 0, 0, 0, 0, 0 };

int fil_hungry[N] = { 0, 0, 0, 0, 0 };

bool stop = false;

char MainLV[N][14] = { "Конфуций", "Цицерон", "Плутарх", "Кант", "Ницше" };

int iMLV[N] = { 105, 105, 105, 105, 105 };

LVCOLUMN lvc = { 0 };

LVITEM LvItem;

HWND hListInfo, hListView;

// Глобальные переменные:

HINSTANCEhInst;                // текущий экземпляр

TCHAR szTitle[MAX_LOADSTRING];          // Текст строки заголовка

TCHAR szWindowClass[MAX_LOADSTRING];      // имя класса главного окна

// Отправить объявления функций, включенных в этот модуль кода:

ATOM        MyRegisterClass(HINSTANCE hInstance);

BOOL        InitInstance(HINSTANCE, int);

LRESULTCALLBACK  WndProc(HWND, UINT, WPARAM, LPARAM);

INT_PTRCALLBACK  About(HWND, UINT, WPARAM, LPARAM);

intAPIENTRY_tWinMain(HINSTANCEhInstance, HINSTANCEhPrevInstance, LPTSTRlpCmdLine, intnCmdShow)

{

UNREFERENCED_PARAMETER(hPrevInstance);

UNREFERENCED_PARAMETER(lpCmdLine);

// TODO: разместите код здесь.

MSG msg;

HACCEL hAccelTable;

// Инициализацияглобальныхстрок

LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);

LoadString(hInstance, IDC_PHILOSOPHERS_WIN32API, szWindowClass, MAX_LOADSTRING);

MyRegisterClass(hInstance);

// Выполнить инициализацию приложения:

if (!InitInstance(hInstance, nCmdShow))

{

returnFALSE;

}

hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_PHILOSOPHERS_WIN32API));

// Цикл основного сообщения:

while (GetMessage(&msg, NULL, 0, 0))

{

if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))

{

TranslateMessage(&msg);

DispatchMessage(&msg);

}

}

return (int)msg.wParam;

}

ATOMMyRegisterClass(HINSTANCEhInstance)

{

WNDCLASSEX wcex;

wcex.cbSize = sizeof(WNDCLASSEX);

wcex.style = CS_HREDRAW | CS_VREDRAW;

wcex.lpfnWndProc = WndProc;

wcex.cbClsExtra = 0;

wcex.cbWndExtra = 0;

wcex.hInstance = hInstance;

wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_PHILOSOPHERS_WIN32API));

wcex.hCursor = LoadCursor(NULL, IDC_ARROW);

wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW);

wcex.lpszMenuName = MAKEINTRESOURCE(IDC_PHILOSOPHERS_WIN32API);

wcex.lpszClassName = szWindowClass;

wcex.hIconSm = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

returnRegisterClassEx(&wcex);

}

BOOLInitInstance(HINSTANCEhInstance, intnCmdShow)

{

HWND hWnd;

hInst = hInstance; // Сохранить дескриптор экземпляра в глобальной переменной

constint w = 790, h = 420;

int x = (GetSystemMetrics(SM_CXSCREEN) - w) / 2;

int y = (GetSystemMetrics(SM_CYSCREEN) - h) / 2;

hWnd = CreateWindow(szWindowClass, "Проблемаобедающихфилософов", WS_OVERLAPPEDWINDOW,

x, y, w, h, NULL, NULL, hInstance, NULL);

if (!hWnd)

{

returnFALSE;

}

ShowWindow(hWnd, nCmdShow);

UpdateWindow(hWnd);

CreateWindowEx(0, "BUTTON", "Начать", BS_PUSHBUTTON | WS_VISIBLE | WS_CHILD,

300, 10, 200, 30, hWnd, (HMENU)IDB_START, NULL, NULL);

CreateWindow("static", "  Информация", WS_CHILD | WS_VISIBLE | WS_TABSTOP,

560, 45, 100, 15, hWnd, NULL, NULL, NULL);

hListView = CreateWindow(WC_LISTVIEW, NULL, WS_CHILD | WS_VISIBLE | WS_CLIPSIBLINGS | LVS_REPORT,

10, 45, 525, 313, hWnd, NULL, hInst, NULL);

ListView_SetExtendedListViewStyle(hListView, LVS_EX_FULLROWSELECT | LVS_EX_HEADERDRAGDROP | LVS_EX_GRIDLINES);

lvc.mask = LVCF_TEXT | LVCF_SUBITEM | LVCF_WIDTH | LVCF_FMT;

lvc.fmt = LVCFMT_LEFT;

for (int i = 0; i

{

lvc.iSubItem = i;

lvc.cx = iMLV[i];

lvc.pszText = MainLV[i];

ListView_InsertColumn(hListView, i, &lvc);

}

hListInfo = CreateWindow("LISTBOX", NULL, WS_CHILD | LBS_EXTENDEDSEL | WS_VSCROLL | WS_VISIBLE,

535, 70, 280, 300, hWnd, (HMENU)LISTBOX_Info, NULL, NULL);

returnTRUE;

}

void SET_State(intfil_num, intc)    // 1 - Голодный, 0 - Думает, 2 - Eст

{

state[fil_num] = c;

Sleep(1000);

char FS[N][9];

for (int i = 0; i

{

if (state[i] == 0)

{

strcpy(FS[i], "Думает");

}

elseif (state[i] == 1)

{

strcpy(FS[i], "Голодает");

}

elseif (state[i] == 2)

{

strcpy(FS[i], "Ест");

}

else

{

strcpy(FS[i], "Ошибка!!!");

}

}

int count = SendMessage(hListView, LVM_GETITEMCOUNT, 0, 0);

LvItem.mask = LVIF_TEXT | LVIF_COLUMNS | LVIF_COLFMT;

LvItem.pszText = FS[0];

LvItem.iItem = count;

ListView_InsertItem(hListView, &LvItem);

ListView_SetItemText(hListView, count, 1, FS[1]);

ListView_SetItemText(hListView, count, 2, FS[2]);

ListView_SetItemText(hListView, count, 3, FS[3]);

ListView_SetItemText(hListView, count, 4, FS[4]);

}

void Test(intfil_num)

{

if ((state[fil_num] == 1) && fil_hungry[fil_num] >= 3)  // если философ ждет больше 3 проходов - дать ему доступ покушать

{

if (fil_num == 4)

{

if (forks[0] == 1) //вилка 0 занята

{

SET_State(0, 0); //думает

forks[0] = 0;

forks[0] = 1;

}

else

{

forks[0] = 1; //взять

}

if (forks[4] == 1)

{

SET_State(3, 0);

forks[4] = 0;

forks[4] = 1;

}

else

{

forks[4] = 1;

}

SET_State(4, 2);

fil_hungry[4] = 0;

}

else

{

if (forks[fil_num] == 1)

{

SET_State(fil_num - 1, 0);

forks[fil_num] = 0;

forks[fil_num] = 1;

}

else

{

forks[fil_num] = 1;

}

if (forks[fil_num + 1] == 1)

{

SET_State(fil_num + 1, 0);

forks[fil_num + 1] = 0;

forks[fil_num + 1] = 1;

}

else

{

forks[fil_num + 1] = 1;

}

SET_State(fil_num, 2);

fil_hungry[fil_num] = 0;

}

}

elseif ((fil_num == 4) && (state[4] == 1) && (forks[4] == 0) && (forks[0] == 0) && (state[0] != 2))//если 4 философ голодает, обе вилки свободны, и он не ест

{

forks[4] = 1;

forks[0] = 1;//дать ему вилки

SET_State(4, 2);// четвертый ест

}

elseif ((state[fil_num] == 1) && (state[LEFT(fil_num)] != 1) && (state[RIGHT(fil_num)] != 1))//дляостальныхфилософов

{

if ((forks[fil_num] == 0) && (forks[fil_num + 1] == 0)) //если свободны две вилки перед философом, то

{

forks[fil_num] = 1; //берем одну вилку

forks[fil_num + 1] = 1; //берем вторую вилку

SET_State(fil_num, 2);//присваиваемстатус "ест"

}

}

else

{

fil_hungry[fil_num]++;

if (forks[fil_num] != 1 && forks[fil_num + 1] != 1) //если правая и левая вилки заняты

{

char buf[100] = { 0 };

if (fil_num == 0)

{

wsprintf(buf, "Конфуцийнеможетвзятьвилку!!!", fil_num);

}

elseif (fil_num == 1)

{

wsprintf(buf, "Цицероннеможетвзятьвилку!!!", fil_num);

}

elseif (fil_num == 2)

{

wsprintf(buf, "Плутархнеможетвзятьвилку!!!", fil_num);

}

elseif (fil_num == 3)

{

wsprintf(buf, "Кантнеможетвзятьвилку!!!", fil_num);

}

elseif (fil_num == 4)

{

wsprintf(buf, "Ницшенеможетвзятьвилку!!!", fil_num);

}

SendMessage(hListInfo, LB_ADDSTRING, 0, (LPARAM)buf);

}

}

}

void PutForks(intfil_num)

{

WaitForSingleObject(Semaphore, INFINITE);  // Захватываемдоступккритическимданным

if (fil_num == 4)

{

forks[4] = 0;

forks[0] = 0;

}

else

{

forks[fil_num] = 0;

forks[fil_num + 1] = 0;

}

SET_State(fil_num, 0);            // Изменяем свое состояние

Test(LEFT(fil_num));            // Пытаемся накормить соседа слева

Test(RIGHT(fil_num));            // Пытаемся накормить соседа справа

ReleaseSemaphore(Semaphore, 1, NULL);    // Освобождаем доступ к критическим данным

}

void TakeForks(intfil_num)

{

WaitForSingleObject(Semaphore, INFINITE);  // Захватываемдоступккритическимданным

SET_State(fil_num, 1);            // Изменяем свое состояние

Test(fil_num);                // Пытаемся взять две вилки

ReleaseSemaphore(Semaphore, 1, NULL);    // Освобождаем доступ к критическим данным

}

unsignedlongCALLBACK philosopher(void *num)

{

int fil_num = (int)num;

char buf[100] = { 0 };

if (fil_num == 0)

{

wsprintf(buf, "Конфуций сидит за столом", fil_num);

}

elseif (fil_num == 1)

{

wsprintf(buf, "Цицерон сидит за столом", fil_num);

}

elseif (fil_num == 2)

{

wsprintf(buf, "Плутарх сидит за столом", fil_num);

}

elseif (fil_num == 3)

{

wsprintf(buf, "Кант сидит за столом", fil_num);

}

elseif (fil_num == 4)

{

wsprintf(buf, "Ницше сидит за столом", fil_num);

}

SendMessage(hListInfo, LB_ADDSTRING, 0, (LPARAM)buf);

while (true)

{

if (stop == true)

{

while (true)

{

if (stop == false)

{

break;

}

}

}

else

{

Sleep(rand() % 1000);          //думает

TakeForks(fil_num);

PutForks(fil_num);

}

}

}

LRESULTCALLBACKWndProc(HWNDhWnd, UINTmessage, WPARAMwParam, LPARAMlParam)

{

int wmId, wmEvent;

PAINTSTRUCT ps;

HDC hdc;

switch (message)

{

caseWM_COMMAND:

wmId = LOWORD(wParam);

wmEvent = HIWORD(wParam);

// Разобрать выбор в меню:

switch (wmId)

{

caseIDB_START:

{

stop = false;

SendMessage(hListView, LVM_DELETEALLITEMS, 0, 0);

SendMessage(hListInfo, LB_RESETCONTENT, 0, 0);

unsignedlong id;

Semaphore = CreateSemaphore(NULL, 1, 1, NULL);

for (int i = 0; i

{

CreateThread(NULL, 0, philosopher, (void*)i, 0, &id);

}

}

break;

caseIDB_PAUSE:

stop = !stop;

break;

caseIDM_ABOUT:

DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);

break;

caseIDM_ZAD:

DialogBox(hInst, MAKEINTRESOURCE(IDD_ZADBOX), hWnd, About);

break;

caseIDM_EXIT:

DestroyWindow(hWnd);

break;

default:

returnDefWindowProc(hWnd, message, wParam, lParam);

}

break;

caseWM_PAINT:

hdc = BeginPaint(hWnd, &ps);

// TODO: добавьте любой код отрисовки...

EndPaint(hWnd, &ps);

break;

caseWM_DESTROY:

PostQuitMessage(0);

break;

default:

returnDefWindowProc(hWnd, message, wParam, lParam);

}

return 0;

}

// Обработчик сообщений для окна "О программе".

INT_PTRCALLBACKAbout(HWNDhDlg, UINTmessage, WPARAMwParam, LPARAMlParam)

{

UNREFERENCED_PARAMETER(lParam);

switch (message)

{

caseWM_INITDIALOG:

return (INT_PTR)TRUE;

caseWM_COMMAND:

if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)

{

EndDialog(hDlg, LOWORD(wParam));

return (INT_PTR)TRUE;

}

break;

}

return (INT_PTR)FALSE;

}

5. 3. Результаты

Главное окно программы

Процесс работы

Окно «Об авторе»

Окно «Условие»

5. 4. Вывод

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

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

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

В созданной программе на возникает блокировок, что подтверждает ее правильную работу.
ПРИЛОЖЕНИЯ

Приложение 1

СПИСОК ИСПОЛЬЗУЕМЫХ ИНФОРМАЦИОННЫХ ИСТОЧНИКОВ

• Курс лекций по предмету «Распределенные вычисления и приложения». Сыромятников В.П.
• https://msdn.microsoft.com/ - официальный сайт Microsoft;http://www.visualstudio.com/ - официальный сайт проекта «VisualStudio»;
• Антонов А.С. «Параллельное программирование с использованием технологии OpenMP».Учебное пособие". Изд-во МГУ, 2009;
• http://iproc.ru/
• http://www.mpich.org/
• http://www.hpcc.unn.ru/