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

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Други колоквијум 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). Приликом детекције сигнала BusUpgr се само прелази у стање I без икаквих бочних ефеката (BusUpgr/--).

3. задатак

Поставка

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

Решење

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

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

4. задатак

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

Поставка

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

Решење

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. На слици су приказана три процеса са одговарајућим алоцираним прозорима W0, W1 и W2, као и приватним просторима који садрже податке А, W2 и 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 приступио како би ту вредност прочитао (РМ).

Преузето из „https://siwiki.rs/w/index.php?title=Мултипроцесорски_системи/К2_2021&oldid=6967”