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

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

1. задатак

Поставка

Објаснити како може доћи до проблема кеш кохеренције чак и када се ради о приватним подацима.

Решење

До проблема кеш кохеренције чак и када се ради о приватним подацима може доћи на следећа два начина:

• Миграција процеса: До проблема кеш кохеренције може доћи чак и када је реч о приватним подацима због миграције процеса са једног процесора на други - то се може догодити нпр. када распоређивач процеса покуша да побољша баланс оптерећења у систему. Нека постоји податак на адреси А0 у оперативној меморији са вредношћу 0 и нека га тренутно ниједан процесор нема у свом кешу. Нека се процес П0 налази на процесору Проц1 са кеш меморијом Ц0. Он може да довуче податак у кеш и измени му вредност на 1 само у свом кешу тако да податак у меморији сада није ажуран. Нека се сада догоди миграција процеса П0 са процесора Проц0 на процесор Проц1 са кеш меморијом Ц1. Ако процес П1 сада покуша да прочита податак, прво ће га потражити у кешу Ц1, па пошто га ту неће пронаћи прочитаће га из меморије, а пошто податак у меморији није ажуран, систем ће ући у неконзистентно стање и тиме управо настаје проблем кеш кохеренције.
• Лажно дељење: До проблема кеш кохеренције може доћи чак и када је реч о приватним подацима због појаве "лажне дељивости". Нека процес на процесору Проц0 уписује у податак који је у меморији на адреси А0 и нека га има у свом кешу. Нека процес на процесору Проц1 уписује у податак који је у меморији на адреси А1 и нека га има у свом кешу. Нека је величина једног блока који кешеви дохватају и смештају у једну кеш линију величине две суседне меморијске локације. То би значило да, иако процесор Проц0 мења само податак са адресе А0, а процесор Проц1 само податак са адресе А1 (дакле, различите податке) свака таква модификација биће детектована као проблем кеш кохеренције који треба разрешити иако тог проблема уопште нема, па онда долази до беспотребног поништавања или ажурирања података у зависности од протокола који се користи за обезбеђивање кеш кохеренције. Овог проблема не би било када би величина блока који дохватају кешеви била величине једне меморијске речи, али је онда питање колико би било корисно такво кеширање - зато је потребно добро размислити при пројектовању кеш меморије колика би требало да буде величина једне кеш линије како би се истовремено што боље искористило кеширање, али исто тако и смањила појава "лажног дељења".

2. задатак

Поставка

Објаснити мотивацију за стање О у протоколу МОЕСИ. Каква је семантика овог стања? Прецизно описати све прелазе из овог стања и прелазе у ово стање.

Решење

Код МЕСИ протокола имамо следећу ситуацију: уколико је нека кеш линија на неком процесору у стању M и неки други процесор затражи податак који се налази у тој кеш линији за читање, први процесор би (пре преласка у стање С) урадио операцију флусх којом би истовремено ажурирао меморију и доставио податак процесору који га је тражио за читање. Меморија мора да се ажурира код МЕСИ протокола у овој ситуацији, јер ако се то не би урадило било би могуће да систем уђе у неконзистентно стање у случају када су све кеш линије са тим податком у стању С јер тада ниједна кеш линија нема власништво над податком, тј. није одговорна за тај податак. Ако је то случај, и додатно податак се не налази у меморији, може да се догоди замена блокова у овим кеш линијама које су у стању С и онда бисмо трајно изгубили ажурну вредност податка.

Зато се код МОЕСИ протокола уводи стање О које има семантику власништва, тј. одговорности над податком, али не и ексклузивности. Због овог стања у описаној ситуацији није потребан упис у меморију јер се одговорност над податком додељује процесору код кога је кеш линија била у стању M и зато ће тај процесор тек кад заиста буде био неопходан упис у меморију то и урадити (дакле, одложено у односу на МЕСИ протокол) и зато гарантовано неће никад доћи до трајног губитка ажурног податка.

Прелази везани за стање O:

• У стање O се прелази из стања M када неки други процесор затражи податак за читање - тада процесор код кога је кеш линија била у стању M шаље податак процесору који га је тражио за читање (BusRd/Transfer). Преласком кеш линије из стања M у стање O процесор задржава власништво над податком али, логично, губи ексклузивност.
• Приликом читања у стању O, кеш линија остаје у истом стању и нема никаквих бочних ефеката (PrRd/--) јер кеш има ажуран податак.
• Приликом уписа у стању O, прелази се у стање M и шаље се сигнал BusUpgr на магистралу да би остали процесори инвалидирали своје копије податка (PrWr/BusUpgr).
• Приликом детекције читања у стању O, остаје се у истом стању и прослеђује се податак из кеша директно у кеш процесора који је затражио податак за читање (BusRd/Transfer).
• Приликом детекције писања у стању O, прелази се у стање I и ради се операција флусх (BusRdX/Flush) - ово је ситуација када неки процесор код кога је кеш линија са овим податком била у стању I затражи упис у дати податак (тада је потребан флусх јер кеш тог процесора нема ажуран податак). Приликом детекције сигнала BusUpgr се само прелази у стање I без икаквих бочних ефеката (BusUpgr/--) - ово је ситуација када неки процесор код кога је кеш линија са овим податком била у стању S затражи упис у дати податак (тада није потребан флусх јер кеш тог процесора већ има ажуран податак).

3. задатак

Поставка

Објаснити 4Ц модел промашаја у кеш меморијама. Објаснити сваку врсту промашаја као и начин да се број промашаја поједине врсте смањи.

Решење

4Ц модел промашаја у кеш меморијама се односи на 4 узрока промашаја у кеш меморијама:

1. Цомпулсорy: Ово је промашај који се догађа када се податак први пут довлачи у кеш меморију - овакав промашај је неизбежан. Ови промашаји се могу смањити повећањем величине блока који може да стане у једну кеш линију - логично, тако би се више података одједном довукло у кеш и то онда потенцијално може претворити вишеструке Цомпулсорy промашаје у један.
2. Цапацитy: Ово је промашај који се догађа због ограничене величине кеш меморије - уколико је радни скуп нашег програма (величина меморије коју он користи) већи од величине целе кеш меморије, могуће је да се догоди да се неки блок у кешу замени неким другим чак и када би кеш меморија била потпуно асоцијативна (што би значило да било који блок сме да се смести у било коју кеш линију) јер просто нема довољно места у кешу да се у њему у једном тренутку нађе наш читав радни скуп. Ови промашаји се могу смањити повећањем величине кеш меморије.
3. Цонфлицт: Ово је промашај који се догађа због ограничене сет-асоцијативности кеш меморије. Мапирање блокова у кеш линије може бити директно, сет-асоцијативно или потпуно асоцијативно. Код директног мапирања, сваки блок сме да се смести у тачно једну кеш линију и јасно је да тада имамо највише промашаја због конфликта јер ће тада максималан број блокова бити мапиран на једну кеш линију и они ће се сви међусобно избацивати из кеша (овде је величина сета 1). Код сет-асоцијативног мапирања један блок може да се смести на било коју од кеш линија које припадају истом сету (сет представља ништа друго него скуп кеш линија), па је јасно да ће тада за веће сетове бити све мање промашаја услед конфликта јер сваки блок има све више опција где може да се смести у кешу. Код потпуно асоцијативног мапирања сваки блок може да се смести у било коју кеш линију у оквиру кеша јер је ту величина сета максимална - једнака је величини целе кеш меморије. Код оваквог мапирања промашаји услед конфликта не могу уопште да се догоде, логично, јер ниједан блок није мапиран ни у једну конкретну кеш линију, већ сваки може да се смести у било коју слободну кеш линију. Међутим, због велике хардверске сложености потребне за имплементацију потпуно асоцијативног мапирања, углавном се користи сет-асоцијативно мапирање. Ови промашаји се очигледно смањују повећањем величине сета.
4. Цохеренце: Ово је промашај који се догађа због дељења податка између више процесора. Ово дељење може бити право или лажно. Код правог дељења заиста један исти податак активно мења више процесора. Промашаји настали услед правог дељења могу да се смање повећањем величине блока јер тако ако је нпр. дељен низ дужине 8 меморијских речи и један процесор измени сваку реч у низу, други процесор мора да дохвати читав низ, па ће то урадити са два промашаја уколико је величина блока 4 меморијске речи, а са једним промашајем ако је величина блока 8 меморијских речи. Промашаји услед правог дељења се могу смањити и софтверски тако што програмер смањи количину дељених података између процесора. Код лажног дељења процесори користе различите податке који припадају истом блоку, па се онда догађају инвалидације или ажурирања (у зависности од типа коришћеног протокола за одржавање кеш кохеренције) читавог блока увек иако процесори модификују различите податке. Промашаји услед лажног дељења се могу смањити смањењем величине блока. Лажно дељење би било у потпуности отклоњено ако би величина блока била једнака величини једне меморијске речи, али такво кеширање не би било исплативо, па се то не ради.

Цомпулсорy, Цапацитy и Цонфлицт промашаји постоје и код једнопроцесорских и код мултипроцесорских система, док Цохеренце промашаји постоје само код мултипроцесорских система.

4. задатак

Поставка

Објаснити мотивацију за адаптивне протоколе кеш кохеренције. Какав је њихов уобичајени начин рада? Објаснити како долази до инвалидације у протоколу ЕДWП.

Решење

• Мотивација: Не може се рећи да су генерално поништавајући протоколи за одржавање кеш кохеренције бољи од ажурирајућих или обратно, зато што директно зависи од карактеристика саме апликације који тип протокола је боље применити. Основни критеријум који се разматра при одабиру типа протокола јесте процесорска локалност, тј. колико се подаци користе од стране само једног процесора. Индикатор процесорске локалности је дужина уписног низа (wрите рун), тј. колико пута неки процесор успе да упише у дати податак пре него што га неки други процесор затражи за читање или упис. Поништавајући протоколи су ефикаснији за дуже уписне низове (нпр. ако је дужина уписног низа 20, једном бисмо јавили осталим процесорима на почетку да инвалидирају своје копије, па бисмо онда локалним, јефтиним уписима у нашу кеш меморију мењали податак и онда бисмо га доставили процесору који га затражи након наших 20 уписа; ово је доста ефикасније него када бисмо користили ажурирајући протокол јер би се тада беспотребно на сваки наш упис слала вредност податка свим процесорима иако ниједном не треба ништа друго осим вредности податка након нашег последњег, тј. 20. уписа). Ажурирајући протоколи су ефикаснији за краће уписне низове (нпр. ако је дужина уписног низа 1, након сваке измене податка у нашем кешу слали бисмо нову вредност свим процесорима који имају копију тог податка и у овом случају је то одлично јер ће свакако увек неки други процесор затражити тај податак након само једног нашег уписа, а овако ће га тада увек пронаћи у свом кешу; ово је доста ефикасније него када бисмо користили поништавајући протокол јер би онда вредност податка у осталим процесорима након сваког уписа нашег процесора била инвалидирана, што значи да би сви остали процесори наредни пут када им затреба тај податак увек промашили у својим кешевима). Сада када знамо шта тачно значи процесорска локалност, јасно је да она може бити променљива и у оквиру једне апликације, што значи да је могуће да неким деловима апликације више одговарају поништавајући протоколи, а другим ажурирајући, па се тако дошло до идеје о адаптивним протоколима који би требало да комбинују оба типа протокола како би потенцијално биле остварене боље перформансе.
• Уобичајени начин рада: Адаптивни протоколи кеш кохеренције обично прво претпоставе да је дужина уписног низа (wрите рун) мала и зато прво почну са применом ажурирајућег протокола. Уколико дужина уписног низа порасте преко неког унапред дефинисаног прага, онда се сматра да се тада више исплати поништавајући протокол и зато се онда прелази на његово коришћење. Пошто је ово обично реализовано хардверски, транспарентно је за програмера, али такође повећава хардверску сложеност система.
• Инвалидација у протоколу ЕДWП: Као претеча ЕДWП (Еффициент Дистрибутед Wритинг Протоцол) протоколу прво се појавио РWБ (Реад анд Wрите Броадцаст) протокол код ког се већ за дужину уписног низа од два уписа прелази са ажурирања на инвалидацију (та промена се догоди већ при другом упису). Закључено је да је то прерано (нпр. код синхронизације процеса прво се догоди упис вредности 0 у дељену променљиву мутеx, па онда упис вредности 1 од стране истог процеса на истом процесору - тада нпр. треба неки други процес на другом процесору да прочита ту вредност мутеx-а како би наставио свој рад, међутим она је инвалидирана јер је у њу писано два пута, па ће он промашити у свом кешу; када би се тек при трећем упису упису прешло са ажурирања на инвалидацију, други процес на другом процесору би пронашао податак у свом кешу). Као што је било и очекивано, на основу резултата симулација закључено је да је боље да се прелази са ажурирања на инвалидацију тек при трећем упису и то само када сви процесори који имају копију тог податка детектују уписни низ дужине три уписа (може се десити да су неки процесори детектовали уписни низ дужине три уписа, а да нпр. један процесор прекине тај уписни низ тако што ће да прочита тај податак, па је онда за њега уписни низ дужине нула уписа - у том случају ће се наставити са применом ажурирајућег протокола све док нису сви процесори (осим, наравно, оног који уписује у податак) детектовали уписни низ дужине три уписа, и тада ће се прећи на поништавајући протокол због чега ће се онда инвалидовати копије у њиховим кешевима).

5. задатак

Поставка

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

double* sin_trans_interpolation(int n, double a, double b, double fa, double fb, double s[], int nx, double x[]) {
    double angle, f1, f2, pi = 3.141592653589793, *value;
    int i, j;
    value = new double[nx];
    for (i = 0; i < nx; i++) {
        f1 = f1_calc(a, b, fa, fb, x[i]); f2 = 0.0;
        for (j = 0; j < n; j++) {
            angle = angle_calc(a, b, j, x[i], pi);
            f2 = f2 + s[j] * sin (angle);
        }
        value[i] = f1 + f2;
    }
    return value;
}

Решење

int main(void) {
    // ...
    int size;
    int rank;
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    int n, nx = 1;
    double a, b, fa, fb, s[...], x[...];
    if (rank == MASTER) {
        // Input n, a, b, fa, fb, n, nx, s, x
    }
    int ints[] = {n, nx};
    double doubles[] = {a, b, fa, fb};
    MPI_Bcast(ints, 2, MPI_INT, MASTER, MPI_COMM_WORLD);
    MPI_Bcast(doubles, 4, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    MPI_Bcast(s, n, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    int count = ints[1] / size;
    double* recvX = new double[count];
    MPI_Scatter(x, count, MPI_DOUBLE, recvX, count, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    double* value = sin_trans_interpolation(ints[0], doubles[0], doubles[1], doubles[2], doubles[3], s, count, recvX);
    double* recvVal = new double[nx];
    MPI_Gather(value, count, MPI_DOUBLE, recvVal, nx, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    delete[] value;
    delete[] recvX;
    // ...
}

6. задатак

Поставка

Једнострана комуникација

1. На слици су приказана три процеса са одговарајућим алоцираним прозорима W₀, W₁ и W₂, као и приватним просторима који садрже податке А, W₂ и C. Објаснити која акција заснована на ПУТ или ГЕТ операцији и од стране ког процеса је спроведена да би се добило стање описано сликом.
2. Да ли се приступ прозору једног процеса мора штити синхронизационим рутинама? На који начин би се могао заштити приступ прозору у случају приказаном под а)?

Решење

1. Извршена је ГЕТ операција од стране процеса 1.
2. Операције приступа не гаратују секвенцијалан приступ од стране више процеса, па је у том случају потребно синхронизовати их. За синхронизацију је могуће користити ЛОЦК/УНЛОЦК операције или фенце.

7. задатак

Поставка

Дат је мултипроцесорски систем са 4 идентична процесора, који користи МСИ протокол за одржавање кохеренције кеш меморије. Свака кеш меморија има по 2 улаза, који су величине једне речи. Пресликавање је директно. Почетне вредности података су 0. Сваки упис увећава вредност измењеног податка за 1. На почетку су све кеш меморије празне. Дата је следећа секвенца приступа меморији:

1. П1,Р,А1
2. П0,W,А1
3. П0,W,А1
4. П1,Р,А0
5. П0,Р,А0
6. П1,Р,А1
7. П1,W,А1
8. П0,Р,А1

• Написати стања кохеренције у свим процесорима и стање меморије после сваке промене и скицирати описани систем у тренутку 8.
• Колико пута који од процесора приступа меморији? За сваки приступ навести разлог.
• Колики је Хит Рате за сваки од процесора (бројати и читање и упис, приказати збирно)?

Решење

Напомена: Узели смо претпоставку да операција флусх само упише ажуран податак у меморију и уопште га не проследи другом кешу који га је тражио, већ ће он морати да приступи меморији да би прочитао ту вредност. Могућа је и другачија имплементација код које би процесор који уради флусх такође и проследио одмах процесору који је тражио податак ту вредност и онда тај други процесор уопште не би приступао меморији јер би имао тај податак у свом кешу - тада бисмо код њега имали РХ уместо РМ при приступу том податку. Ако испробате секвенце приступа из задатка у Вивио симулатору 5.1 видећете да флусх функционише овако.

ЦПУ	Број погодака	Укупан број приступа	Хит рате	Приступи меморији
П0	1	5	20%	WМ, WХ, РМ, флусх, РМ
П1	1	5	20%	РМ, РМ, РМ, WХ, флусх
П2	0	0	0%
П3	0	0	0%

Тренутак 1

Садржај кешева

П0			П1			П2			П3
			А1	С	0

Садржај меморије

А0	0
А1	0
А2	0
А3	0

П1 је приступао меморији како би дохватио податак са А1 (РМ).

Тренутак 2

Садржај кешева

П0			П1			П2			П3
А1	M	1	А1	I	0

Садржај меморије

А0	0
А1	0
А2	0
А3	0

П0 је приступио меморији како би дохватио податак у који је хтео да упише (WМ).

Тренутак 3

Садржај кешева

П0			П1			П2			П3
А1	M	2	А1	I	0

Садржај меморије

А0	0
А1	0
А2	0
А3	0

П0 је покушао да приступи меморији ради уписа у А1, али је тај податак већ био у његовом кешу (WХ).

Тренутак 4

Садржај кешева

П0			П1			П2			П3
			А0	С	0
А1			А1	I	0

Садржај меморије

А0	0
А1	0
А2	0
А3	0

П1 је приступио меморији ради читања А0 (РМ).

Тренутак 5

Садржај кешева

П0			П1			П2			П3
А0	С	0	А0	С	0
А1	M	2	А1	I	0

Садржај меморије

А0	0
А1	0
А2	0
А3	0

П0 је приступио меморији ради читања А0 (РМ).

Тренутак 6

Садржај кешева

П0			П1			П2			П3
А0	С	0	А0	С	0
А1	С	2	А1	С	2

Садржај меморије

А0	0
А1	2
А2	0
А3	0

П0 је приступио меморији како би уписао измењену вредност А1 (флусх), након чега је П1 приступио како би ту вредност прочитао (РМ).

Тренутак 7

Садржај кешева

П0			П1			П2			П3
А0	С	0	А0	С	0
А1	I	2	А1	M	3

Садржај меморије

А0	0
А1	2
А2	0
А3	0

П1 је изменио А1 који је био у његовој кеш меморији (WХ) а онда инвалидирао остале копије.

Тренутак 8

Садржај кешева

П0			П1			П2			П3
А0	С	0	А0	С	0
А1	С	3	А1	С	3

Садржај меморије

А0	0
А1	3
А2	0
А3	0

П1 је приступио меморији како би уписао измењену вредност А1 (флусх), након чега је П0 приступио како би ту вредност прочитао (РМ).