Алгоритм сортування злиттям та його паралельна реалізація мовою С#
Автор: lentez • Декабрь 10, 2022 • Курсовая работа • 5,160 Слов (21 Страниц) • 203 Просмотры
[pic 1]
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
«КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО»
ФАКУЛЬТЕТ ІНФОРМАТИКИ ТА ОБЧИСЛЮВАЛЬНОЇ ТЕХНІКИ
КАФЕДРА ІНФОРМАТИКИ ТА ПРОГРАМНОЇ ІНЖЕНЕРІЇ
Курсова робота
з дисципліни «Технології паралельних обчислень»
Тема: Алгоритм сортування злиттям та його паралельна реалізація мовою С#
Керівник: д.т.н., проф. Стеценко І.В. «Допущено до захисту» _____________________ «___» __________ 2022 р. Захищено з оцінкою _____________________ Члени комісії: _____________________ _____________________ | Виконавець: Залізчук Данило Дмитрович студент групи ІП-92 залікова книжка №10 _____________________ «5» червня 2022 р. Інна СТЕЦЕНКО Олександра ДИФУЧИНА |
Київ – 2022
АНОТАЦІЯ
Структура та обсяг роботи. Пояснювальна записка курсової роботи складається з 5 розділів, містить 24 рисунки, 3 таблиці, 1 додаток, 6 джерел.
Мета. Курсова робота ставить перед собою досягнення наступних цілей:
- дослідити можливі методи паралельної реалізації алгоритму сортування злиттям;
- розробити паралельний алгоритм сортування злиттям для прискорення роботи;
- після перевірки коректності реалізованого алгоритму, провести дослідження його ефективності у порівнянні з послідовним алгоритмом.
У розділі розробки послідовного алгоритму та аналізу його швидкодії було по кроках описано роботу алгоритму сортування злиттям, проведено тестування на масивах різних розмірів. У розділі вибору програмного забезпечення було аргументовано вибір мови програмування C#.
У розділі розробки паралельного алгоритму сортування злиттям було по кроках спроектовано його роботу, реалізовано програму мовою C#, виконано тестування коректності роботи.
У розділі дослідження ефективності паралельних обчислень було виконано порівняння часу виконання паралельного алгоритму з часом виконання послідовного алгоритму на масивах різних розмірів з однаковими даними. Результати було записано у таблицю, візуалізовано на графіку та аргументовано.
КЛЮЧОВІ СЛОВА: АЛГОРИТМ, СОРТУВАННЯ ЗЛИТТЯМ, MERGE SORT, ПАРАЛЕЛЬНІ ОБЧИСЛЕННЯ, ПОТОК
ЗМІСТ
ВСТУП 4
РОЗДІЛ 1. ОПИС ПОСЛІДОВНОГО АЛГОРИТМУ ТА ЙОГО ВІДОМИХ ПАРАЛЕЛЬНИХ РЕАЛІЗАЦІЙ 5
1.1 Опис послідовного алгоритму 5
1.2 Опис паралельних реалізацій алгоритму 5
РОЗДІЛ 2. РОЗРОБКА ПОСЛІДОВНОГО АЛГОРИТМУ ТА АНАЛІЗ ЙОГО ШВИДКОДІЇ 7
РОЗДІЛ 3. ВИБІР ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ ДЛЯ РОЗРОБКИ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ ТА ЙОГО КОРОТКИЙ ОПИС. 12
РОЗДІЛ 4. РОЗРОБКА ПАРАЛЕЛЬНОГО АЛГОРИТМУ З ВИКОРИСТАННЯМ ОБРАНОГО ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ: ПРОЕКТУВАННЯ, РЕАЛІЗАЦІЯ, ТЕСТУВАННЯ 13
4.1 Проектування алгоритму 13
4.2 Реалізація алгоритму 13
4.3 Тестування алгоритму 14
РОЗДІЛ 5. ДОСЛІДЖЕННЯ ЕФЕКТИВНОСТІ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ АЛГОРИТМУ 19
ВИСНОВКИ 22
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 23
ДОДАТКИ 24
Додаток А. Лістинг коду програмного забезпечення 24
ВСТУП
З появою перших комп’ютерів, виконувані задачі мали невеликий об’єм та незначний рівень складності. З часом, комп’ютери покращувались, технології розвивались, а також з’являлись більш складні та комплексні задачі, на виконання яких комп’ютери почали витрачати більше часу. Зараз ми живемо у той час, коли перехід на нанометровий процес, поява більшої кількості ядер у процесорі, або перехід на зовсім іншу архітектуру не є чимось новим. Дуже складні і комплексні програми можуть працювати дуже швидко, і одна з причин – паралельні обчислення.
...