Размещено на http://www.allbest.ru/

Зміст

• Вступ
• 1. Інтегроване середовище розробки програмних додатків Qt Creator
• 1.1 Інструментарій Qt
• 1.2 Компоненти Qt
• 2. OpenMP
• 2.1 Переваги OpenMP
• 2.2 Конструкції OpenMP
• 2.3 Сортування масиву злиттям
• 2.4 Тестування програми сортування
• Висновок
• Список використаної літератури
• Додаток

Вступ

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

Qt Creator -- інтегроване середовище розробки, призначене для створення крос-платформових застосунків з використанням бібліотеки Qt. Підтримується розробка як класичних програм мовою C++, так і використання мови QML, для визначення сценаріїв в якій використовується JavaScript, а структура і параметри елементів інтерфейсу задаються CSS-подібними блоками. Qt Creator може використовувати GCC або Microsoft VC++ в якості компілятора.

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

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



1. Інтегроване середовище розробки програмних додатків Qt Creator

Qt Creator -- інтегроване середовище розробки, призначене для створення крос-платформових застосунків з використанням бібліотеки Qt. Підтримується розробка як класичних програм мовою C++, так і використання мови QML, для визначення сценаріїв в якій використовується JavaScript, а структура і параметри елементів інтерфейсу задаються CSS-подібними блоками. Qt Creator може використовувати GCC або Microsoft VC++ в якості компілятора. Для Windows версій бібліотека комплектується компілятором, заголовними і об'єктними файлами MinGW.

1.1 Інструментарій Qt

Qt -- кросплатформовий інструментарій розробки ПЗ мовою програмування C++. Дозволяє запускати написане за його допомогою ПЗ на більшості сучасних операційних систем шляхом простої компіляції тексту програми для кожної ОС без зміни початкового коду. Включає всі основні класи, які можуть бути потрібні при розробці прикладного програмного забезпечення, починаючи з елементів графічного інтерфейсу і закінчуючи класами для роботи з мережею, базами даних, OpenGL, SVG і XML. Бібліотека дозволяє керувати потоками, працювати з мережею, і забезпечує кросплатформовий доступ до файлів.

Qt також може бути використаним в багатьох інших мовах програмування: Ada (QtAda), C# (Qyoto/Kimono), Java(Qt Jambi), Qt Jambi, Pascal, Perl, PHP (PHP-Qt), Ruby (QtRuby), та Python (PyQt,PySide).

Відмінна особливість Qt від інших бібліотек -- використання Meta Object Compiller -- попередньої системи обробки початкового коду (загалом, Qt, це бібліотека не для чистого C++, а для його особливого діалекту, з якого і "перекладає" MOC для подальший компіляції будь-яким стандартним C++ компілятором). MOC дозволяє у багато разів збільшити потужність бібліотек, вводячи такі поняття як слоти (slots) і сигнали (signals). Qt комплектується графічним середовищем розробки графічного інтерфейсу QTDesigner, що дозволяє створювати діалоги і форми "мишею". Ідеологія створення форм в Qt базується на використанні менеджерів розташування, котрі створюють "гумовий" дизайн, при якому розмір і розташування елементів форм визначаються автоматично, що значно прискорює розробку графічного інтерфейсу. В поставці Qt є "Qt Linguist" -- могутня графічна утиліта, що дозволяє спростити локалізацію і переклад вашої програми багатьма мовами; і "Qt Assistant" -- довідкова система Qt, що спрощує роботу з документацією по бібліотеці, а також дозволяє створювати кросплатформову довідку для розробленого на основі Qt ПЗ.

1.2 Компоненти Qt

Бібліотека розділена на декілька модулів, для четвертої версії це:

· QtCore -- класи ядра бібліотеки використовувані іншими модулями;

· QtGui -- компоненти графічного інтерфейсу;

· QtNetwork -- набір класів для мережевого програмування. Підтримка різних високорівневих протоколів може мінятися від версії до версії. У версії 4.2.x присутні класи для роботи з протоколами FTP і HTTP. Для роботи з протоколами TCP/IP і UDP призначені такі класи як: QTcpServer, QTcpSocket для TPC/IP і QUdpSocket для UDP;

· QtOpenGL -- набір класів для роботи з OpenGL;

· QtSql -- набір класів для роботи з базами даних мовою структурованих запитів SQL. Основні класи цього модуля у версії 4.2.х: QSqlDatabase -- клас для надання з'єднання з базою, для роботи з якоюсь конкретною базою даних, вимагає об'єкт успадкований від класу QSqlDriver -- абстрактного класу, який реалізується для конкретної бази даних і може вимагати для компіляції SDK бази даних. Наприклад, для збірки драйвера під базу даних FireBird/InterBase вимагає .h файли і бібліотеки статичної лінковки, що входять в комплект постачання даної БД;

· QtScript -- класи для роботи з Qt Scripts;

· QtSvg -- класи для відображення і роботи зі Scalable Vector Graphics (SVG) даними;

· QtXml -- модуль для роботи з XML, підтримується SAX і DOM моделі роботи;

· QtDesigner -- класи створення розширень QtDesigner'а для своїх власних віджетів;

· QtUiTools -- класи для обробки в застосунку форм Qt Designer;

· QtAssistant -- довідкова система;

· Qt3Support -- модуль з класами, необхідними для сумісності з бібліотекою Qt версії 3.х.х;

· QtTest -- модуль для роботи з UNIT тестами;

· QtWebKit -- модуль WebKit інтегрований в Qt і доступний через її класи;

· QtXmlPatterns -- модуль для підтримки XQuery 1.0 і XPath 2.0;

· Phonon -- модуль для підтримки відтворення і запису відео і аудіо, як локально, так і з пристроїв і з мережі;

· QtCLucene -- модуль для підтримки повнотекстового пошуку, застосовується в новій версії Assistant в Qt 4.4;

· ActiveQt -- модуль для роботи з ActiveX і COM технологіями для Qt-розробників під Windows. Модуль доступний тільки в комерційній редакції Qt.

Також реалізована технологія WOC -- widgets on canvas, за допомогою якої буде реалізована Plasma в KDE 4.1, Буде можливим використовувати віджети бібліотеки Qt прямо в аплетах. Забезпечує розташування віджетів на QGraphicsView з можливістю масштабування і різних графічних ефектів.

Бібліотека використовує власний формат проекту, що іменується .pro файлом, в якому зібрана інформація про те, які файли будуть скомпільовані, за якими шляхами шукати заголовні файли і багато іншої інформації. Згодом за допомогою утиліти qmake з них виходять makefile для make-утиліти компілятора. Також є можливість роботи за допомогою інтеграторів з такими середовищами програмування як Microsoft Visual Studio 2003/2005 і зовсім недавно стала доступна інтеграція в Eclipse, для версії бібліотеки 4.х.х.



2. OpenMP

OpenMP (Open Multi-Processing) -- це набір директив компілятора, бібліотечних процедур та змінних середовища, які призначені для програмування багатопотокових застосунків на багатопроцесорних системах із спільною пам'яттю на мовах C, C++ та Fortran.

Розробку специфікації OpenMP ведуть кілька великих виробників обчислювальної техніки та програмного забезпечення, робота яких регулюється некомерційною організацією, названою OpenMP Architecture Review Board (ARB). Специфікації для мов Fortran і C/C++ з'явилися відповідно в жовтні 1997 року і жовтні 1998 року.

2.1 Переваги OpenMP

За рахунок ідеї "інкрементального розпаралелювання" OpenMP ідеально підходить для розробників, що прагнуть швидко розпаралелювати свої обчислювальні програми з великими паралельними циклами. Розробник не створює нову паралельну програму, а просто послідовно додає в текст програми OpenMP-директиви.

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

Передбачається, що OpenMP-програма на однопроцесорній платформі може бути використана як послідовна програма, тобто немає необхідності підтримувати послідовну та паралельну версії. Директиви OpenMP просто ігноруються послідовним компілятором, а для виклику процедур OpenMP можуть бути підставлені заглушки (stubs), текст яких приведений в специфікаціях.

Однією з переваг OpenMP розробники вважають підтримку так званих "orphan" (відірваних) директив, тобто директиви синхронізації і розподілу роботи можуть не входити безпосередньо в лексичний контекст паралельної області.

2.2 Конструкції OpenMP

OpenMP простий у використанні і включає лише два базові типи конструкцій: директиви pragma і функції виконуючого середовища OpenMP. Директиви pragma, як правило, вказують компілятору реалізувати паралельне виконання блоків коду. Всі ці директиви починаються з # pragma omp. Як і будь-які інші директиви pragma, вони ігноруються компілятором, що не підтримують конкретну технологію - в даному випадку OpenMP.

Функції OpenMP служать в основному для зміни і отримання параметрів середовища. Крім того, OpenMP включає API-функції для підтримки деяких типів синхронізації. Щоб задіяти ці функції бібліотеки OpenMP періоду виконання (виконуючого середовища), в програму потрібно включити заголовний файл omp.h. Якщо ви використовуєте в додатку тільки OpenMP-директиви pragma, включати цей файл не потрібно.

Для реалізації паралельного виконання блоків додатки потрібно просто додати в код директиви pragma і, якщо потрібно, скористатися функціями бібліотеки OpenMP періоду виконання. Директиви pragma мають наступний формат:

#pragma omp <директива> [розділ [ [,] розділ]...]

OpenMP підтримує директиви parallel, for, parallel for, section, sections, single, master, critical, flush, ordered і atomic, які визначають або механізми поділу роботи або конструкції синхронізації. У цій статті ми обговоримо більшість директив.

Розділ (clause) - це необов'язковий модифікатор директиви, що впливає на її поведінку. Списки розділів, підтримувані кожної директивою, розрізняються, а п'ять директив (master, critical, flush, ordered і atomic) взагалі не підтримують розділи.

Хоча директив OpenMP багато, всі вони відразу нам не знадобляться. Найважливіша і поширена директива - parallel. Вона створює паралельний регіон для наступного за нею структурованого блоку, наприклад:

#pragma omp parallel [розділ[ [,] розділ]...]

Розглянемо приклад, який визначає середні значення двох сусідніх елементів масиву і записує результати в інший масив. У цьому прикладі використовується нова для вас OpenMP-конструкція # pragma omp for, яка відноситься до директив поділу роботи (work-sharing directive). Такі директиви застосовуються не для паралельного виконання коду, а для логічного розподілу групи потоків, щоб реалізувати зазначені конструкції керуючої логіки. Директива # pragma omp for повідомляє, що при виконанні циклу for в паралельному регіоні ітерації циклу повинні бути розподілені між потоками групи:

#pragma omp parallel

{

#pragma omp for

for(int i = 1; i < size; ++i)

x[i] = (y[i-1] + y[i+1])/2;

}

Якби цей код виконувався на чотирьох процесорному комп'ютері, а у змінної size було б значення 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.



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

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

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

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

4. 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

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

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

7. Земсков В.Ю., Программирование на 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++;

}

}

while(lLeftIt < pLeft.size())

{

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

lLeftIt++;

}

while(lRightIt < pRight.size())

{

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

lRightIt++;

}

return lResult;

}

QVector<double> mergesort(QVector<double> &pVec, int threads)

{

if(pVec.size() == 1)

{

return pVec;

}

int mid = pVec.size() / 2;

QVector<double> lLeft;

for(int i = 0; i < mid; i++)

{

lLeft.append(pVec.at(i));

}

QVector<double> lRight;

for(int i = mid; i < pVec.size(); i++)

{

lRight.append(pVec.at(i));

}

if (threads > 1)

{

#pragma omp parallel sections

{

#pragma omp section

{

lLeft = mergesort(lLeft, threads / 2);

}

#pragma omp section

{

lRight = mergesort(lRight, threads - threads / 2);

}

}

}

else

{

lLeft = mergesort(lLeft, 1);

lRight = mergesort(lRight, 1);

}

return merge(lLeft, lRight);

}

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

{

QCoreApplication a(argc, argv);

int n = 0;

int high = 10000;

int low = 0;

int threads = 1;

printf("N = ");

scanf("%d", &n);

printf("Threads count = ");

scanf("%d", &threads);

QVector<double> vec;

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

{

vec.append(qrand() % ((high + 1) - low) + low);

}

double t_start = omp_get_wtime();

vec = mergesort(vec, threads);

double t_end = omp_get_wtime();

printf("Time = %lf\n", t_end - t_start);

return a.exec();

}

openmp_example.pro

QT += core

QT -= gui

TARGET = openmp_example

CONFIG += console

CONFIG -= app_bundle

TEMPLATE = app

QMAKE_CXXFLAGS += -fopenmp

LIBS += -fopenmp

SOURCES += main.cpp



Додаток Б

програма масив злиття сортування

"Клас CEngine"

#include "cengine.h"

CEngine::CEngine()

{

}

void CEngine::set_numgroups(int num)

{

this->numgroups = num;

this->groups = new CObject[num];

}

void CEngine::set_numteachers(int num)

{

this->numteachers = num;

this->teachers = new CObject[num];

}

void CEngine::set_numclassrooms(int num)

{

this->numclassrooms = num;

this->classrooms = new CObject[num];

}

void CEngine::set_numsubjects(int num)

{

this->numsubjects = num;

this->subjects = new CObject[num];

}

void CEngine::Start_Sort()

{

int teach = -1;

int aud = -1;

bool set = false;

for(int i = 0; i < numgroups; i++)

{

for(int j = 0; j < groups[i].task_num; j++)

{

if(groups[i].task[j] > 0)

{

teach = -1;

aud = -1;

set = false;

for(int l = 0; l < 6; l++)

{

for(int k = 0; k < 5; k++)

{

if(groups[i].time[k][l] == false)

{

for(int v = 0; v < numteachers; v++)

{

for(int w = 0; w < teachers[v].type_num; w++)

{ if((teachers[v].time[k][l] == false)&&(teachers[v].type[w] == groups[i].type[j]))

{

teach = v;

qDebug() << teachers[v].time[k][l];

qDebug() << teachers[v].type[w];

qDebug() << groups[i].type[j];

break;

}

qDebug() << teachers[v].time[k][l];

qDebug() << teachers[v].type[w];

qDebug() << groups[i].type[j];

}

if(teach != -1)

{

break;

}

}

if(teach == -1)

{

continue;

}

for(int v = 0; v < numclassrooms; v++)

{

for(int w = 0; w < classrooms[v].type_num; w++)

{if((classrooms[v].time[k][l] == false)&&(classrooms[v].type[w] == find_subject(groups[i].type[j])))

{

aud = v;

break;

}

}

if(aud != -1)

{

break;

}

}

if(aud == -1)

{

continue;

}

groups[i].time[k][l] = true;

teachers[teach].time[k][l] = true;

classrooms[aud].time[k][l] = true;

groups[i].scedule_classroom[k][l] = aud;

groups[i].scedule_subj[k][l] = find_subj_id(groups[i].type[j]);

groups[i].scedule_teacher[k][l] = teach;

groups[i].task[j]--;

set = true;

qDebug() << "[" << k << "][" << l << "]\t" << groups[i].name << "\t" << groups[i].type[j] << "\t" << teachers[teach].name << "\t" << classrooms[aud].name;

if(groups[i].task[j] != 0)

{

j--;

}

break;

}

}

if(set)

{ break; } } } } }}

QString CEngine::find_subject(QString name)

{

for(int i = 0; i < this->numsubjects; i++)

{

if(this->subjects[i].name == name)

{

return this->subjects[i].type[0];

}

}

return "";

}

int CEngine::find_subj_id(QString name)

{

for(int i = 0; i < this->numsubjects; i++)

{

if(this->subjects[i].name == name)

{

return i;

}

}

return -1;

}

void CEngine::write_debug(int id)

{

for(int i = 0; i < 5; i++)

{

for(int j = 0; j < 6; j++)

{

QString txt[4];

txt[0] = groups[id].name;

if(groups[id].scedule_classroom[i][j] == -1)

{

txt[1] = "--";

}

else

{

txt[1] = classrooms[groups[id].scedule_classroom[i][j]].name;

}

if(groups[id].scedule_subj[i][j] == -1)

{

txt[2] = "--";

}

else

{

txt[2] = subjects[groups[id].scedule_subj[i][j]].name;

}

if(groups[id].scedule_teacher[i][j] == -1 )

{

txt[3] = "--";

}

else

{

txt[3] = teachers[groups[id].scedule_teacher[i][j]].name;

}

qDebug() << "[" << i << "][" << j << "]\t" << txt[0] << "\t" << txt[1] << "\t" << txt[2] << "\t" << txt[3];

} }}

int CEngine::Get_numgroups()

{

return this->numgroups;

}

Размещено на Allbest.ru