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

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

1. задатак

Поставка

Објаснити промену принципа пројектовања процесора који фаворизују паралелно процесирање.

Решење

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

2. задатак

Поставка

Шта је претпоставка Густафсон-овог закона? Извести и прецизно објаснити овај закон.

Решење

Густафсон-ов закон претпоставља да паралелни део програма расте са бројем процесора. То значи да ако за процесор са $p$ језгара узмемо да се програм извршава $T_p = \alpha T + \left(1 - \alpha\right) T$ где је $\alpha$ проценат секвенцијалног кода у апликацији, онда се за процесор са једним језгром тај исти програм извршава $T_1 = \alpha T + \left(1 - \alpha\right) pT$. Убрзање је онда $S_p = \frac{T_1}{T_p} = \frac{\alpha T + \left(1 - \alpha\right) pT}{\alpha T + \left(1 - \alpha\right) T} = \frac{\alpha T + \left(1 - \alpha\right) pT}{T} = \alpha + \left(1 - \alpha\right) p$. Ово значи да $\lim_{p \to +\infty} S_p = +\infty$, али ова претпоставка важи само за скалабилне апликације.

3. задатак

Поставка

Описати технолошке трендове у процесорској технологији и њихове последице.

Решење

• Тренд у процесорској технологији је био смањење величине транзистора. Смањењем величине транзистора можемо да спакујемо више транзистора на исту количину места и на тај начин правимо јаче процесоре. Нажалост, смањењем транзистора они мењају своје електронске карактеристике, кола у којима се они користе постају нестабилнија и постоји ограничење до којег се величина транзистора може смањивати.
• Тренд је такође био повећање такта процесора, повећавајући број извршених инструкција по секунди. Нажалост, како су процесори расли тако је расло и кашњење између логичких кола, и то представља проблем за повећање такта процесора, које је последње деценије успорило. Такође се дешава са повећавањем такта да се већа енергија дисипира на тако малој површини, па је процесору потребно много боље хлађење, и ту такође наилазимо на поwер wалл.

4. задатак

Поставка

Дати упоредни преглед карактеристика програмских модела заједничке меморије и преноса порука. У чему се разликују архитектуре и организације система који директно подржавау^[сиц] ове моделе.

Решење

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

Карактеристика	Заједничка меморија	Пренос порука
Приступ меморији	Директан приступ истој меморији	Директан приступ својој меморији, посредством порука приступ туђим меморијама
Синхронизација	Морају се користити одвојене структуре (капацитети оперативног система и хардвера) како би се приступ меморији синхронизовао	Имплицитна, јер размењују поруке
Копирање података	Није потребно, други имају приступ истој меморији као ми	Потребно, јер једино тако други могу да добију садржај наше приватне меморије
Идентитет	Процеси не (морају да) знају један за другог	Процеси знају један за другог
Архитектура и организација	Сложенија, постоје УМА и НУМА варијанте како би процесори делили меморију између себе и потребно је одржавати кохеренцију кеш меморија	Мање сложена, пошто процесори експлицитно захтевају једни од других меморију која им је потребна, али је зато софтвер који то ради сложенији

5. задатак

Поставка

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

float simpsons(float ll, float ul, int n) {
    float h = (ul - ll) / n, x[10], fx[10];
    for (int i = 0; i <= n; i++) {
        x[i] = ll + i * h; fx[i] = func(x[i]);
    }
    float res = 0;
    for (int i = 0; i <= n; i++) {
        if (i == 0 || i == n) res += fx[i];
        else if (i % 2 != 0) res += 4 * fx[i];
        else res += 2 * fx[i];
    }
    res = res * (h / 3);
    return res;
}

Решење

Следеће решење је писано под условом да су декларације x и fx као низове од 10 бројева симболичне и да n заправо сме да буде веће 10, јер иначе паралелизација овог програма не би имала никаквог смисла.

float simpsons(float ll, float ul, int n) {
    float h = (ul - ll) / n, x[10], fx[10];
    #pragma omp parallel for default(none) shared(x, fx, ll, ul, n, h)
    for (int i = 0; i <= n; i++) {
        x[i] = ll + i * h; fx[i] = func(x[i]);
    }
    float res = 0;
    #pragma omp parallel for default(none) shared(fx) reduction(+:res)
    for (int i = 0; i <= n; i++) {
        if (i == 0 || i == n) res += fx[i];
        else if (i % 2 != 0) res += 4 * fx[i];
        else res += 2 * fx[i];
    }
    res = res * (h / 3);
    return res;
}

6. задатак

Поставка

Да ли и на који начин ОпенМП подржава угнеждени паралелизам? Да ли је могуће у оквиру паралелног региона покренути нови паралелни регион и под којим условима?

Решење

ОпенМП подржава угнеждени паралелизам, у смислу да је могуће угнездити паралелни регион унутар другог паралелног региона. При угнеждавању ће се створити тим нити са једном нити у њему, осим уколико угнеждавање није омогућено коришћењем omp_set_nested(true) функције, или OMP_NESTED променљиве окружења. Неке имплементације не подржавају ове методе угнеждавања, и у њима ће угнеждени тим нити увек имати једну нит.

7. задатак

Поставка

Нека се посматра једна апликација за прикупљање и агрегацију података са интернета. Апликација се састоји од веб трагача (wеб цраwлер) који прикупља одређене информације на интернету, а затим се ради обрада. Након мерења перформанси секвенцијалне имплементације посматране апликације при уобичајеној употреби, добијени су следећи резултати: апликација 45% времена проводи обављајући улазно-излазне операције (секвенцијално прикупљање података из једног извора), а 55% времена проводи у обради података. Типично време обраде једног пакета података коришћењем једног језгра је 1с.

1. Уколико се апликација паралелизује за извршавање на СМП систему са 8 језгара на 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.45$ и $p = 8$ максимално убрзање које можемо да постигнемо је $S_p = \frac{8}{0.45 \cdot 8 + 1 - 0.45} \approx 1.93$.

Апликација може да одржава осам нити, од којих једна нит ради примање података преко интернета и како пристижу пакети убацује их у неку дељену структуру и неком синхронизационом примитивом сигнализира да има пакета за обраду (слично баг оф таскс приступу коришћењем програмског модела дељене меморије). Осталих седам нити могу да из ове вреће задатака преузимају пакете за обраду и обрађују их паралелно. Без обзира на то што пакети имају неуједначено време обраде, нити не морају да чекају једна на другу тако да док једна нит обрађује захтевнији пакет остале нити не зависе од ње (не постоји боттленецк). Више од осам нити вероватно неће убрзати апликацију јер ће свести на класичан тиме-схаринг уместо паралелне обраде.