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

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

1. задатак

Поставка

Објаснити како је настао поwер wалл и како то утиче на пројектовање процесора.

Решење

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

2. задатак

Поставка

Које две класе паралелизма преовладјују^[сиц] у апликацијама? Које врсте паралелизма се препознају при извршавању ну^[сиц] рачунарима?

Решење

Две класе паралелизма у апликацијама су паралелизам на нивоу података као и задатака, док се при извршавању на рачунарима препознају као паралелизам на нивоу инструкције, нити, захтева, као и векторске архитектуре.

3. задатак

Поставка

Објаснити шта је паралелни програмски модели.^[сиц] Објаснити шта су имплицитни, а шта експлицитни модели, шта су њихове предности и недостаци.

Решење

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

4. задатак

Поставка

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

Решење

Видети овде.

5. задатак

Поставка

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

int iter = 0;
while (error > tol && iter < iter_max) {
    error = 0.0;
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            Anew[j][i] = 0.25 * (A[j][i+1] + A[j][i-1] + A[j-1][i] + A[j+1][i]);
            double diff;
            if ((Anew[j][i] - A[j][i]) > 0.0) {
                diff = Anew[j][i] - A[j][i];
            } else {
                diff = A[j][i] - Anew[j][i];
            }
            if (diff > error) error = diff;
        }
    }
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            A[j][i] = Anew[j][i];
        }
    }
    iter++;
}

Решење

int iter = 0;
while (error > tol && iter < iter_max) {
    error = 0.0;
    #pragma omp parallel default(none) shared(A, Anew, n, m) reduction(max:error)
    {
    #pragma omp for collapse(2)
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            Anew[j][i] = 0.25 * (A[j][i+1] + A[j][i-1] + A[j-1][i] + A[j+1][i]);
            double diff;
            if ((Anew[j][i] - A[j][i]) > 0.0) {
                diff = Anew[j][i] - A[j][i];
            } else {
                diff = A[j][i] - Anew[j][i];
            }
            if (diff > error) error = diff;
        }
    }
    #pragma omp for collapse(2)
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            A[j][i] = Anew[j][i];
        }
    }
    }
    iter++;
}

6. задатак

Поставка

На који начин nowait одредба може утицати на директиве на које се односи? Навести када је ова одредба употребљива и образложити одговор.

Решење

nowait директива диктира да на крају одређеног региона ОпенМП кода не треба да се врши имплицитна синхронизација као што се иначе врши на крају for, sections и single региона. Ова директива је употребљива када нам оваква имплицитна синхронизација није потребна и можемо пустити више нити да прође тај регион како бисмо их онда касније негде експлицитно синхронизовали. На пример, можемо пустити нити да прођу кроз више блокова асоцираних са for директивама ако те петље не зависе једна од друге, а затим их синхронизовати на некој баријери испод.

7. задатак

Поставка

Нека се посматра једна апликација која врши обраду великих матрица које представљају одређену 2Д медицинску слику. Након мерења перформанси секвенцијалне имплементације посматране апликације при уобичајеној употреби, добијени су следећи резултати: апликација 15% времена проводи обављајући улазно-излазне операције, 85% времена проводи у обради података. Типично време обраде једног чвора коришћењем једног језгра је 1с.

1. Уколико се апликација паралелизује за извршавање на СМП систему са 64 језгара на 3ГХз са 32ГБ меморије, навести формулу за Амдалов закон и одредити максимално могуће убрзање које се може постићи за задату апликацију.
2. Објаснити различите начине за декомпозицију домена у контексту обраде 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.15$ и $p = 64$ максимално убрзање које можемо да постигнемо је $S_p = \frac{64}{0.15 \cdot 64 + 1 - 0.15} \approx 6.12$.

Дводимензионалне матрице могу да се поделе на различите начине: по редовима, по колонама, по блоковима, циклично... на перформансе апликације, додуше може да утиче начин кеширања података током њиховог дохватања. Елементи матрице су генерално подаци који се налазе близу један до другог уколико им се приступа на одређен начин (у C је то по редовима) и зато је за перформансе кеширања података најбоље делити тим редом. Уколико елементи матрице имају малу неуједначеност у потребном времену обраде, циклична подела може да помогне тако да свака нит има могућност да захвати и делове који захтевају мање и делове који захтевају више обраде.