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

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

1. задатак

Веома слично питање нашло се на првом колоквијуму 2021. године

Поставка

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

Решење

Видети овде.

2. задатак

Поставка

Објаснити шта је ИЛП и навести типичне примере. Објаснити и образложити трендове искоришћења ИЛП за повећање перформанси некада и сада.

Решење

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

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

3. задатак

Поставка

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

Решење

Предности:

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

Мане:

• Сложенији хардвер
• Теже скалира повећањем броја процесора
• Захтева посебне атомске операције за синхронизацију
• Програмер одговоран за правилан приступ дељеним подацима
• Теже оптимизовати имплицитну комуникацију

4. задатак

Поставка

Нацртати и објаснити типичну структуру система који подржава модел преноса порука. По чему се она разликује од НУМА архитектуре?

Решење

(Слика: П02 - ППМ, слајд 42)

Градивни елемент у моделу преноса порука је комплетан рачунар. Рачунарима су одвојени адресни простори и комуницирају експлицитним I/О операцијама преко мреже.

Организација је слична НУМА архитектурама, али постоје разлике:

• Комуникација у НУМА системима се односи на приступ меморији, не на размену порука.
• Јача је спрега између процесора и мреже код преноса порука.

5. задатак

Поставка

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

queue<node*> q;
q.push(head);
while (!q.empty()) {
    qSize = q.size();
    for (int i = 0; i < qSize; i++) {
        node* currNode = q.front();
        q.pop();
        doStuff(currNode);
        q.push(currNode);
    }
}

Решење

Овај код за обраду чворова БФС методом није исправан, јер све време циркулише исти чвор у реду, а и нема никаквог смисла враћати чвор који је већ био у реду назад у тај ред. Уколико занемаримо те проблеме, и претпоставимо да се у doStuff ради само обрада а не и неко гурање чворова у ред, овај задатак се може паралелизовати ОпенМП пословима, слично коду за обилажење уланчане листе:

queue<node*> q;
q.push(head);
#pragma omp parallel
{
#pragma omp single
{
while (!q.empty()) {
    qSize = q.size();
    for (int i = 0; i < qSize; i++) {
        node* currNode = q.front();
        q.pop();
        #pragma omp task
        doStuff(currNode);
        q.push(currNode);
    }
}
}
}

6. задатак

Поставка

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

Решење

ОпенМП подржава модел релаксиране конзистенције, тако да не морају све нити да виде исти садржај меморије. Уколико је нитима неопходно, могу да користе flush директиву која синхронизује поглед нити на меморију. Ова директива је имплицитна приликом наиласка на разне синхронизационе директиве и при уласку и изласку из паралелног региона. Није добро користити flush директиву кад није апсолутно неопходно.

7. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

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

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