Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ ЗАСОБАМИ MPI
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Лабораторна робота №3
з дисципліни "Паралельні та розподілені обчислення"
на тему: “ ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ ЗАСОБАМИ MPI”
Мета роботи: вивчити методи декомпозиції задач. Набути навиків розв'язування задач з функціональної декомпозиці.. Основики інструменти бібліотеки МРІ для реалізації декомпозиції задач.
ТЕОРЕТИЧНІ ВІДОМОСТІ.
1.Використання функціональної декомпозиції
Найважливішим та найважчим етапом при створенні програми є розробка алгоритму, особливо, якщо мова йде про паралельний алгоритм. Процес створення паралельного алгоритму можна розбити на чотири кроки.
1.1. Декомпозиція. На цьому етапі вихідна задача аналізується, оцінюється можливість її розпаралелювання. Іноді виграш від розпаралелення може бути незначним, а трудоємкість розробки паралельної програми велика. В цьому випадку перший крок розробки алгоритму виявляється і останнім. Якщо ж ситуація відмінна від описаної, то задача та пов’язані з нею дані розділяються на дрібніші частини – підзадачі і фрагменти структур даних. Особливості архітектури конкретної обчислювальної системи на цьому етапі можуть не враховуватися.
1.2. Проектування комунікацій(обміну даними) між задачами. На цьому етапі визначаються зв’язки, необхідні для пересилання вхідних даних, проміжних результатів виконання підзадач, а також комунікації, що необхідні для керування роботою під задач. Обираються методи та алгоритми комунікацій.
1.3.Укрупнення. Підзадачі можуть об’єднуватися у більші блоки, якщо це дозволяє підвищити ефективність алгоритму і знизити трудоємкість розробки. Основними критеріями на даному кроці є ефективність алгоритму (в першу чергу продуктивність) та трудоємкість його реалізації.
1.4. Планування обчислень. На цьому кроці виконується розподіл під задач між процесорами. Основний критерій вибору способу розміщення під задач – ефективне використання процесорів з мінімальними затратами часу на обмін даними.
Декомпозиція (сегментування).
На цьому етапі визначається степінь можливого розпаралелення задачі. Іноді декомпозиція поставленої задачі природним чином випливає з самої задачі тому є очевидною, іноді – ні. Чим менший розмір підзадач, отриманих в результаті декомпозиції, чим більша їх кількість, тим гнучкішим виявляється паралельний алгоритм і тим легше забезпечити рівномірне завантаження процесорів обчислювальної системи. Надалі, можливо доведеться укрупнити алгоритм, оскільки слід прийняти до уваги інтенсивність обміну даними та інші фактори. Сегментувати можна як обчислювальний алгоритм, так і дані. Застосовуються різні варіанти декомпозиції.
В методі декомпозиції даних спочатку сегментуються дані, а потім алгоритм їх обробки. Дані розбиваються на сегменти приблизно однакового розміру. З фрагментами даних пов’язуються операції їх обробки, з яких і формуються підзадачі. Визначаються необхідні правила обміну даними. Перекриття частин, на які розбивається задача, повинне бути мінімальним. Це дозволяє уникнути дублювання обчислень. Схема розбиття може в подальшому уточнюватися. Іноді, якщо це необхідно для зменшення кількості обмінів, допускається збільшення степені перекриття фрагментів задачі.
При декомпозиції даних спочатку аналізуються структури даних найбільшого розміру, або ті, до яких найчастіше відбувається звертання. На різних стадіях розрахунків можуть використовуватися різні структури даних, тому можуть бути необхідними динамічні, тобто такі, що міняються в часі схеми декомпозиції цих структур.
В методі функціональної декомпозиції спочатку сегментується обчислювальний алгоритм, а потім під цю схему підбирається схема декомпозиції даних. Успіх у цьому випадку не завжди гарантовано, оскільки схема може вимагати багатьох додаткових пересилань даних. Цей метод декомпозиції може виявитися корисним у випадку, якщо немає структур даних, які б могли бути розпаралелені очевидним чином. Функціональна декомпозиція відіграє важливу роль і як метод структурування програм. Вона може виявитися корисною при моделюванні складних систем, що складаються з множини простих підсистем, зв’язаних між собою набором інтерфейсів.
Розмір блоків, з яких складається паралельна програма, може бути різним. В залежності від розміру блоків, алгоритм може мати різну “зернистість”. Її виміром в найпростішому випадку є кількість операцій у блоці. Виділяють три степені зернистості: дрібнозернистий, середньоблоковий та великоблоковий. Зернистість пов’язана з рівнем паралелізму.
Паралелізм на рівні команд найбільш дрібнозернистий. Його масштаб менше ніж 20 команд на блок. Кількість підзадач, що паралельно виконуються – від однієї до кількох тисяч, при чому середній масштаб паралелізму складає біля п’яти команд на блок.
Наступний рівень - паралелізм на рівні циклів. Переважно, цикл містить не більше 500 команд. Якщо ітерації циклу незалежні, вони можуть виконуватися, наприклад за допомогою конвеєра або на векторному процесорі. Це також дрібнозернистий паралелізм.
Паралелізм на рівні підзадач – середньоблоковий. Розмір блоку – до 2000 команд. Виконання такого паралелізму реалізувати важче, оскільки слід враховувати можливі міжпроцедурні залежності. Вимоги до комунікацій менші, ніж у випадку паралелізму на рівні команд.
Паралелізм на рівні програм (задач) – великоблоковий. Він означає виконання незалежних програм на паралельному комп’ютері. Великоблоковий паралелізм повинен підтримуватися операційною системою.
Обмін даними через спільні/розподілені змінні використовується на рівнях дрібнозернистого і середньоблокового паралелізму, а на великоблоковому – засобами передачі повідомлень.
Досягнути ефективності роботи паралельної програми можна, якщо збалансувати зернистість алгоритму і затрати часу на обмін даними.
Частини програми можуть виконуватися паралельно, лише якщо вони незалежні.
Незалежність за даними полягає в тому, що дані, які обробляються однією частиною програми не модифікуються іншою її частиною.
Незалежність за керуванням полягає в тому, що послідовність виконання частин програми може бути визначена лише під час виконання програми(наявність залежності по виконанню наперед визначає порядок виконання).
Незалежність за ресурсами забезпечується достатньою кількістю комп’ютерних ресурсів(об’єм пам’яті, кількість функціональних вузлів та ін.).
Залежність за виводом виникає, якщо дві підзадачі виконують запис в одну і ту ж змінну. А залежність за вводом/виводом, якщо оператори вводу/виводу двох чи декількох під задач звертаються до одного файлу(чи змінної).
Дві підзадачі можуть виконуватися паралельно, якщо вони незалежні за даними, за керуванням і за операціями вводу виводу.
ЗАВДАННЯ.
1.Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат .
2. На основі створеного алгоритму написати програму використовуючи засоби яка дозволяє обчислити вираз та ілюструє проведену декомпозицію для кількості процесорів заданих у варіанті
Варіант: 8
/
Декомпозиція:
/
Результат роботи програми:
/
Додаток:
using System;
namespace laba1
{
public class ArythmeticOperations : IArythmeticOperations
{
public double Execute(double leftValue, double rightValue, Func<double, double, double> operation)
{
return operation(leftValue, rightValue);
}
public static double Add(double leftValue, double rightValue)
{
return leftValue + rightValue;
}
public static double Sub(double leftValue, double rightValue)
{
return leftValue - rightValue;
}
public static double Mul(double leftValue, double rightValue)
{
return leftValue * rightValue;
}
public static double Div(double leftValue, double rightValue)
{
return leftValue/rightValue;
}
public static double Pow(double leftValue, double power)
{
return Math.Pow(leftValue, power);
}
}
}
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
namespace laba1
{
public class DataImporter : IDataImporter
{
private StreamReader streamReader;
private FileStream fileStream;
private readonly List<string> exceptions;
public List<double> ImportData(string filePath)
{
try
{
using (fileStream = new FileStream(filePath + ".txt", FileMode.Open))
{
using (streamReader = new StreamReader(this.fileStream))
{
string dataFromFile = streamReader.ReadLine();
return string.IsNullOrEmpty(dataFromFile) ? null : new List<double>(dataFromFile.Split(',').Select(double.Parse));
}
}
}
catch (Exception exception)
{
Console.WriteLine("failed while importing data");
return null;
}
}
}
}
using System;
namespace laba1
{
public static class Extensions
{
public static void ShowMatrix(this Matrix matrix)
{
int dimension = matrix.Length;
for (int columnIndex = 0; columnIndex < dimension; columnIndex++)
{
for (int rowIndex = 0; rowIndex < dimension; rowIndex++)
{
Console.Write(matrix.MatrixValue[columnIndex, rowIndex] + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
public static void ShowVector(this Vector vector)
{
if(vector == null) return;
for (int index = 0; index < vector.Length; index++)
{
Console.Write(vector.VectorValue[index] + " ");
}
Console.WriteLine();
}
public static Matrix T(this Matrix matrix)
{
var size = matrix.Length;
var res = new Matrix(new double[size, size]);
for (int columnIndex = 0; columnIndex < size; columnIndex++)
{
for (int rowIndex = 0; rowIndex < size; rowIndex++)
{
res.MatrixValue[rowIndex, columnIndex] = matrix.MatrixValue[columnIndex, rowIndex];
}
}
return res;
}
}
}
using System;
namespace laba1
{
public interface IArythmeticOperations
{
double Execute(double leftValue, double rightValue, Func<double,double,double> operation);
}
}
using System.Collections.Generic;
namespace laba1
{
public interface IDataImporter
{
List<double> ImportData(string filePath);
}
}
using System;
namespace laba1
{
public class VectorScalarOperation : IVectorScalarOperations
{
private IArythmeticOperations operation;
public VectorScalarOperation()
{
operation = new ArythmeticOperations();
}
public Vector Mul(Vector vector, double scalar)
{
Vector resVector = new Vector(new double[vector.Length]);
for (int firstIndex = 0; firstIndex < vector.Length; firstIndex++)
{
var firstVector = vector.VectorValue[firstIndex];
resVector.VectorValue[firstIndex] = operation.Execute(firstVector, scalar, ArythmeticOperations.Mul);
}
return resVector;
}
public Vector Div(Vector vector, double scalar)
{
throw new NotImplementedException();
}
}
}
22.03.2018 19:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора