Особливість методів сортування лінійних масивів й можливі способи їх розпаралелювання. Порівняльна реалізація калібрування Шелла. Програма паралельного розрахунку визначеного інтеграла. Розробка уподібненої системи множення квадратної матриці на вектор.
Створення багатопроцесорних (паралельних) обчислювальних систем (ПОС) є стратегічною лінією розвитку компютерної техніки, що обумовлюється існуванням в теперішній момент часу актуальних завдань фундаментальної і прикладної науки, для аналізу і дослідження яких продуктивності існуючих засобів обчислювальної техніки виявляється недостатньо. Подолання першого стримуючого чинника по широкому використанню паралельних обчислень (висока вартість ПОС) може бути отримано шляхом побудови кластерних обчислювальних систем (clusters). Застосування кластерів може також в деякій мірі зменшити проблеми, повязані з розробкою паралельних алгоритмів і програм, оскільки підвищення обчислювальної потужності окремих процесорів дозволяє будувати кластери з порівняно невеликої кількості (декілька десятків) окремих компютерів.Алгоритм вважається навчальним і практично не застосовується поза навчальної літератури, замість нього на практиці застосовуються більш ефективні алгоритми сортування. У той же час метод сортування обмінами лежить в основі деяких більш досконалих алгоритмів, таких як шейкерні сортування, пірамідальна сортування і швидке сортування. Алгоритм складається з повторюваних проходів по масиву. Проходи по масиву повторюються N-1 раз або до тих пір, поки на черговому проході не буде зрозуміло, що обміни більше не потрібні, що означає - масив відсортований. Перший прохід: (5 1 4 2 8) (1 5 4 2 8), тут алгоритм порівнює два перших елемента і змінює їх місцями.У найпростішомувипадку, сортування полягає в чергуванні двох етапів. На першому етапі масив розбивається на пари (а0, а1), (а2, а3), (а4, а5),. . На другому етапі аналогічна обробка виконується в парах (а1, а2), (а3, а4), (а5, а6),. . Така реалізація може бути використана в многопроцессорном компютері, але для кластера робочих станцій вона не годиться, тому що витрати на пересилання сусідніх елементів будуть перевищувати час на виконання операцій з сортування. Щоб пристосувати метод до реалізації в розподіленої обчислювальної системі з p процесорів, всі п сортируємих елементів діляться на частини, що містять по п / p елементів.Ідея методу Шелла полягає в порівнянні елементів, що стоять не тільки поруч, але і на певній відстані один від одного. Аналогічний метод удосконалення бульбашкового сортування називається сортування гребінцем. Під час сортування Шелла спочатку порівнюються і сортуються між собою значення, віддалені один від одного на деякій відстані (про вибір значення див. нижче). Після цього процедура повторюється для деяких менших значень, а завершується сортування Шелла упорядкуванням елементів при (тобто звичайної сортуванням вставками). Ефективність сортування Шелла в певних випадках забезпечується тим, що елементи «швидше» встають на свої місця (в простих методах сортування, наприклад, бульбашкової, кожна перестановка двох елементів зменшує кількість інверсій у списку максимум на 1, а при сортуванні Шелла це число може бути більше).Щоб отримати паралельну реалізацію методу Шелла, необхідно обєднати процесори комунікаційної мережі в топологію N-мірного гіперкуба. Тоді максимальна відстань між елементами буде дорівнює N (2N вузлів, повязаних послідовно, мали б найбільшу відстань 2N - 1). 1.4.1 представлений приклад 3-мірного гіперкуба (має вигляд звичайного куба), у якого послідовність нумерації вершин (вузлів мережі) дозволяє використовувати код Грея при обході в порядку 0-1-3-2-6-7-5-4. На попередньому етапі виконується поділ вихідного масиву на 2N частин і розсилка кожної з них відповідного вузла кластера. На першому етапі послідовної реалізації методу Шелла обмін повинен виконуватися між віддаленими один від одного парами вузлів з номерами: 0 - 4, 1 - 5, 2-6, 3 - 7.Один з швидких відомих універсальних алгоритмів сортування масивів (в середньому O (n log n) обмінів при упорядкуванні n елементів), хоча і має ряд недоліків. Кроки алгоритму такі: - вибираємо в масиві певний елемент, який будемо називати опорним елементом. Відомі стратегії: вибирати постійно один і той же елемент, наприклад, середній або останній за положенням; вибирати елемент з випадково вибраним індексом; операція поділу масиву: реорганізуємо масив таким чином, щоб всі елементи зі значенням меншим або рівним опорному елементу, виявилися ліворуч від нього, а всі елементи, що перевищують за значенням опорний - праворуч від нього. індекс l послідовно збільшується до тих пір, поки l-й елемент не виявиться більше або дорівнює опорному;Для паралельної реалізації методу швидкого сортування (розширення Брюса Вагара - т. зв. гіпербистре сортування) так само, як і у випадку методу Шелла, створюється комунікаційна топологія у вигляді N-мірного гіперкуба для кластера, що містить 2N процесорів. Потім N раз виконується наступна послідовність дій: - вибирається провідний елемент з розсилкою його значення всім процесорам гіперкуба; виконується взаємний обмін частинами всередині кожної пари процесорів так, щоб у процесорів, що містять 0 в двійковому представленні свого номера, залишилося по дві частини з
План
ЗМІСТ
ВСТУП
1. ТЕОРЕТИЧНА ЧАСТИНА. ВАРІАНТ 10. МЕТОДИ СОРТУВАННЯ ЛІНІЙНИХ МАСИВІВ Й МОЖЛИВІ СПОСОБИ ЇХ РОЗПАРАЛЕЛЮВАННЯ. ЇХНІ ПЕРЕВАГИ, НЕДОЛІКИ
