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

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

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

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