можливості інтегрованого середовища розробки програм Qt Creator та основи паралельних обчислень мовою програмування С++

б значення 100, то виконання ітерацій 1-25 могло б бути доручено першому процесору, 26-50 - другу, 51-75 - третій, а 76-99 - четвертому. Це характерно для політики планування, званої статичною. Політики планування ми обговоримо пізніше. 

Слід зазначити, що наприкінці паралельного регіону виконується бар'єрна синхронізація (barrier synchronization). Інакше кажучи, досягнувши кінця регіону, всі потоки блокуються доти, поки останній потік не завершить свою роботу.

 

2.3 Сортування масиву злиттям.

 

Сортування злиттям — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

Час роботи алгоритму   по впорядкуванню   елементів задовільняє рекурентному співвідношенню:

де   — час на впорядкування половини масиву,

   — час на злиття цих половинок.

Враховуючи, що

 ,

розв'язком співвідношення є:

 .

Крім того, алгоритм потребує для своєї роботи   додаткової пам'яті.

Алгоритм не міняє порядок розташування однакових елементів, а отже він є стабільним.

 

2.4 Тестування програми сортування.

 

Було розроблену програму сортування злиттям масиву випадкових чисел, в якій реалізований розподіл операцій на окремі потоки. Програма написана мовою програмування С++ з використанням інтегрованого середовища розробки Qt Creator і бібліотеки Qt 5.3. Для роботи потрібно ввести кількість чисел які будуть визначатись за допомогою генератора випадкових чисел, а також кількість потоків.

Програму було тестовано на ноутбуці із процесором Intel Core i5-4200U. Кількість випадкових чисел збільшували від 100 до 5 млн., порівнювався час сортування масиву при одному потоці і при чотирьох потоках рис 1.

 

Рис. 1. Залежність часу сортування від кількості елементів і кількості потоків

 

При збільшені кількості елементів масиву і кількості потоків різниця часу сортування збільшується. Використовувати паралельні потоки вигідніше при великій кількості елементів масиву.

 

Висновок

 

Під час проходження навчально-ознайомчої практики було вивчено основні можливості інтегрованого середовища розробки програм Qt Creator та ознайомлено  з основами паралельних обчислень мовою програмування С++ в цьому середовищі. 

Було розглянуто переваги OpenMP  та сортування  масиву злиттям  та тестування програми сортування. 

Було написано тестову програму сортування масиву випадкових чисел та застосовано паралельні потоки для прискорення обчислень з використанням директив OpenMP.

 

Список використаної літератури

 

Заячук Д.М. – Нанотехнології і наноструктури: Навч. Посібник. – Львів: Видавництво Національного університету “Львівська політехніка”, 2009. – 580 с.

P. J. F. Harris - Carbon  nanotube composites -  International Materials Reviews 2004 VOL 49 NO 1

L. Berha,  A. M. Sastry - Modeling percolation in high-aspect-ratio fiber systems. I. Soft-core versus hard-core models -  PHYSICAL REVIEW E 75, 2007.

Z. Ounaiesa, C. Park, K.E. Wise, E.J. Siochi, J.S. Harrison – Electrical  properties of single wall carbon nanotube reinforced polyimide composites. Composites Science and Technology 63 (2003) 1637–1646

Шлее М. – Qt 4.5. Профессиональное программирование на C++. – СПб.: БХВ-Петербург, 2010 – 896 с.

Богачёв К. Ю. – Основы параллельного программирования. – М.: БИНОМ. Лаборатория знаний, 2003. – 342 с.

Земсков В.Ю., Программирование на C++ с использованием библиотеки Qt 4. – СПб.: БХВ-Петербург, 2007. – 272 с.

Додаток А «сортування злиттям»

main.cpp

#include <QCoreApplication>

#include <omp.h>

#include <stdio.h>

#include <stdlib.h>

#include <QVector>

 

QVector<double> merge(const QVector<double> &pLeft, const QVector<double> &pRight)

{

    QVector<double> lResult;

    int lLeftIt = 0;

    int lRightIt = 0;

    while (lLeftIt < pLeft.size() && lRightIt < pRight.size())

    {

        if(pLeft.at(lLeftIt) < pRight.at(lRightIt))

        {

            lResult.push_back(pLeft.at(lLeftIt));

            lLeftIt++;

        }

        else

        {

            lResult.push_back(pRight.at(lRightIt));

            lRightIt++;