Мултипроцесорски системи/К1 2021

Први колоквијум 2021. године одржан је 2. новембра и трајао је 105 минута. Поставка рока је доступна са странице предмета.

1. задатак

Поставка

Описати пет типичних класа рачунара. Навести за које апликације се обично користе, као и најбитније пројектне циљеве.

Решење

• Лични мобилни уређаји (ПМД - Персонал мобиле девицес) су преносиви рачунари намењени за личну употребу. Најбитнији пројектни циљеви су ниска цена, ниска потрошња енергије и перформансе у репродукцији медија.
• Десктоп рачунари су рачунари опште употребе са широким опсегом апликација. Најбитнији циљеви су однос цене и перформанси, потрошња енергије и перформансе за графику.
• Сервер рачунари су рачунари за сервисе који имају велик број корисника и захтевају висок ниво поузданости. Најбитнији циљеви су пропусни опсег, доступност/издржљивост, потрошња енергије.
• Кластери или WСЦ (Wарехоусе Сцале Цомпутинг) су скупови више хиљада рачунара повезаних на ЛАН. Користе се за СааС (Софтwаре ас а Сервице). Најбитнији циљеви су доступност, однос цена и перформанси, потрошња енергије.
• ИоТ/уграђени рачунари се користе у уређајима широке употребе, најчешће дизајнирани за специфичне сврхе. Најбитнији циљеви су ниска цена, ниска потрошња енергије и перформансе специфичне за њихову примену.

2. задатак

Поставка

Описати историјске трендове у архитектури рачунара у погледу остваривања паралелизма обраде.

Решење

У ВЛСИ рачунарским системима присутан је тренд повећавања паралелизма.

Најпре се појавило повећавање бит паралелизма. Проширивањем стазе података и ширине регистара смањен је број инструкција, а самим тим и тактова неопходним за извршење послова. Овај тренд је трајао до позних 1980их, са кључним тренутком када цео микропроцесор и кеш меморија стају на један чип.

Након тога је наступио тренд паралелизма на нивоу инструкције (ИЛП). Циљ је био повећати број инструкција по такту, што је постигнуто проточном обрадом, извршавањем ван поретка итд. Процесори бивају знатно сложенији и потрошња ресурса је повећана.

Раних 2000их достигнут је врхунац побољшања перформанси са ИЛП и прелази се на паралелизам на нивоу нити (ТЛП).

3. задатак

Поставка

Нацртати УМА и НУМА архитектуре. Објаснити сличности и разлике између њих.

Решење

Преглед карактеристика

Карактеристика	УМА	НУМА
Начин приступа меморији	Директан приступ свакој меморијској локацији.	Меморија је дистрибуирана, локални и удаљени приступ.
Брзина приступа	Некеширан приступ има исту цену за сваку локацију.	Локални приступ је бржи (директан приступ), удаљени спорији (преко порука на ИЦН).
Пропусни опсег	Захтева већи јер сви приступи иду кроз ИЦН/магистралу.	Мања потреба за брзим ИЦН.
Скалабилност	Теже се скалира, уско грло је обично магистрала/интерцоннецт мрежа.	Много боље скалира.

4. задатак

Поставка

Објаснити програмски модел Дата параллел. Нацртати и објаснити типичну архитектуру која подржава овај модел.

Решење

Дата Параллел програмски модел се односи на извршавање исте операције над различитим подацима у паралели како би се брже обрадила цела структура података.

Постоје специјални процесори (арраy процессорс) који су, за разлику од класичних општенаменских процесора, оптимизовани управо за програмски модел Дата Параллел у којем је неопходна брза обрада велике количине података.

Дата Параллел програмски модел је нарочито примењив за разна научна истраживања у којима се масовно ради над низовима и матрицама.

Архитектура оваквих арраy процессор-а је СИМД (Сингле Инструцтион Мултипле Дата) јер нити извршавају исте инструкције над различитим подацима. Постоји један контролни процесор који је задужен за управљање и распоређивање података на остале процесоре чија је једина улога израчунавање на основу података који су им додељени и смештени у њиховим локалним меморијама.

5. задатак

Поставка

Коришћењем ОпенМП технологије, паралелизовати део кода у прилогу који проналази параметар алфа са задовољавајућом тачношћу у методу коњугованих градијената. Обратити пажњу на ефикасност и коректност паралелизације. Паралелизацију обавити ручним распоређивањем посла нитима. Сматрати да су све променљиве исправно декларисане.

bool alfaSet = false;
int alfaIter = 0;
int step = 1;
double localAlfa = alfa;
double *testX = (double *) malloc(dim * sizeof(double));

while (!alfaSet) {
    alfaIter += step;
    localAlfa = pow(gamma, alfaIter - 1);

    for (i = 0; i < dim; i++) {
        testX[i] = x[i] + localAlfa * d[i];
    }
    
    if (func(testX, dim) - delta * localAlfa * b <= oldFunc) {
        if (!alfaSet) {
            alfaSet = true;
            alfaIter = 0;
            alfa = localAlfa;
        }
    }
}
free(testX);

Решење

Уколико претпоставимо да се под ручним распоређивањем послова мисли на некоришћење wорксхаринг директива и ОпенМП послова, и такође да је потребно да нађемо једно алфа уместо првог алфа које задовољава услове, једна могућност је:

#include <omp.h>
bool alfaSet = false;
#pragma omp parallel
{
int alfaIter = 0;
int step = 1;
double localAlfa = alfa;
double *testX = (double *) malloc(dim * sizeof(double));
alfaIter = omp_get_thread_num();
step = omp_get_num_threads();

while (!alfaSet) {
    alfaIter += step;
    localAlfa = pow(gamma, alfaIter - 1);

    for (i = 0; i < dim; i++) {
        testX[i] = x[i] + localAlfa * d[i];
    }
    
    if (func(testX, dim) - delta * localAlfa * b <= oldFunc) {
        #pragma omp critical (alfa_set_sync)
        if (!alfaSet) {
            alfaSet = true;
            alfaIter = 0;
            alfa = localAlfa;
        }
    }
}
free(testX);
}

6. задатак

Поставка

На који начин се променљиве подразумевано прослеђују у оквиру ОпенМП task директиве? Због чега је то неопходно и да ли је увек неопходно? Образложити одговор.

Решење

Променљиве се подразумевано прослеђују као firstprivate, односно приватне копије променљивих добијају почетну вредност. Ово има смисла јер се послови могу извршавати у неодређеном, каснијем тренутку када прослеђена променљива може бити ван досега. Овакве дељење није увек неопходно јер као и у осталим директивама за поделу посла, понегде су неопходни дељени подаци.

7. задатак

Поставка

Нека се посматра једна нумеричка симулација. Апликација најпре учитава параметре симулације, затим решава сложене системе линеарних диференцијалних једначина и на крају уписује резултате свога рада. Након мерења перформанси секвенцијалне имплементације посматране апликације при уобичајеној употреби, добијени су следећи резултати: апликација 5% времена проводи обављајући улазно-излазне операције, а 95% времена проводи у обради података. Типично време обраде у оквиру симулације коришћењем једног језгра је 1000с.

1. Уколико се апликација паралелизује за извршавање на СМП систему са 4 језгара на 2ГХз са 32ГБ меморије, навести формулу за Амдалов закон и одредити максимално могуће убрзање које се може постићи за задату апликацију са датом конфигурацијом.
2. Шта представља особина скалабилности у контексту паралелног рачунарства и специфично паралелног хардвера? Да ли би додавање нових процесорских језгара у случају под а) допринело убрзавању описане паралелне апликације и у којим случајевима?

Решење

Формула за Амдалов закон гласи:

• $T_p = \alpha T_1 + (1 - \alpha) \frac{T_1}{p}$
• $S_p = \frac{T_1}{T_P} = \frac{1}{\alpha + \frac{1 - \alpha}{p}} = \frac{p}{\alpha p + 1 - \alpha}$

Како је нама овде $\alpha = 0.05$ и $p = 4$ максимално убрзање које можемо да постигнемо је $S_p = \frac{4}{0.05 \cdot 4 + 1 - 0.05} \approx 3.47$.

Скалабилност у паралелном рачунарству се односи на могућност паралелног система да пропорционално убрза свој рад са додавањем нових процесора (ресурса) у систем. Специфично, за паралелни хардвер мисли се на повећање броја језгара, повећање пропусног опсега и слично. У овом случају, додавање нових процесорских језгара би значајно допринело убрзању ове апликације, јер се у највећем делу може паралелизовати њен код. Услов да се апликација заиста и убрза је, наравно, да се тај код који може да се паралелизује заиста и паралелизује.