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

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

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

1. задатак

Поставка

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

Решење

Два могућа начина:

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

2. задатак

Поставка

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

Решење

Када би се појавио нови процесор који жели да чита неки податак, који је други процесор већ изменио у свом кешу, МЕСИ протокол би морао да уради упис тог податка у меморију пре него што пређе у С стање. Додавање новог стања које означава само власништво а не и екслузивност над тим податком би одложило овај упис. Тако је настало стање O:

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

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=6950”