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

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

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

1. задатак

Поставка

Описати и објаснити датафлоw паралелни програмски модел. Који су недостаци примене овог модела.

Решење

Датафлоw програмски модел представља програм као граф блокова инструкција које се могу извршавати чим су њихови подаци доступни. Нажалост, овај програмски модел није заживео у данашње време због неколико недостатака:

  • Не води се рачуна о локалности података, и тиме много умањује ефекат кеш меморије.
  • Ради се много непотребних израчунавања док се чека на податке који нпр. одређују да ли ће се извршити један или други блок.
  • Пошто не постоји програмски бројач, дохватање инструкција из ове меморије је много сложеније.

2. задатак

Поставка

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

Решење

Паралелни систем са заједничком кеш меморијом има кеш меморију као слој испред обичне меморије, тако да процесори када приступају неком податку из меморије прво дођу до кеша а затим се приступа меморији уколико податак није у кешу. Предности оваквог приступа су што избегавамо проблем кохеренције кеша, уводимо позитивну интерференцију и избегавамо лажну дељивост.

3. задатак

Поставка

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

Решење

  • Власништво: један процесор код себе чува ажурну копију податка, може да је мења како хоће али је његова одговорност да ту копију на крају упише у меморију (wрите-бацк).
  • Ексклузивност: само један процесор код себе чува један податак, па зна да не мора да излази на магистралу да јавља осталима своје операције над њим.
  • Валидност: процесор има ажурну верзију податка код себе у кешу.
МЕСИ
Стање валидно власник екслузивно
M + + +
Е + - +
С + - -
I - - -
Драгон
Стање валидно власник екслузивно
M + + +
Е + - +
Сц + - -
См + + -


4. задатак

Поставка

Објаснити појаве правог дељења (труе схаринг) и лажног дељења (фалсе схаринг). Како повећање величине блока утиче на ове појаве.

Решење

Право дељење је када два процесора раде над истим податком, и зато избацују један другом тај податак из кеш меморије током одржавање кохеренције. Лажно дељење је када два процесора раде над подацима који се налазе у истом блоку кеша, и ефекат је исти, али далеко мање користан од праве дељивости. Повећање величине блока не утиче на праву дељивост[?] али може да повећа лажну дељивост, јер са више података у једном блоку може да дође до чешћих конфликата над тим подацима него кад је података мање.

5. задатак

Поставка

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

int index, n = width * height;
float mean = 0.0, var = 0.0, svar, std;
for (index = 0; index < n; index++) mean += (float)(inputImage[index]);
mean /= (float)n;
for (index = 0; index < n; index++) {
    svar = (float)(inputImage[index]) - mean;
    var += svar * svar;
}
var /= (float)n;
std = sqrtf(var);
for (index = 0; index < n; index++)
    outputImage[index] = (inputImage[index] - mean)/std;

Решење

int rank;
int size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
if (rank == MASTER) {
    // Input width, height, inputImage.
}
int index, n = width * height / size;
MPI_Bcast(&n, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
MPI_Scatter(inputImage, n, MPI_INT, inputImageRecv, n, MPI_INT, MASTER, MPI_COMM_WORLD);
float sum = 0.0, varSum = 0.0, var, svar, std, mean;
for (index = 0; index < n; index++) sum += (float)(inputImageRecv[index]);
MPI_Allreduce(&sum, &mean, 1, MPI_FLOAT, MPI_SUM, MPI_COMM_WORLD);
mean /= (float)(n * size);
for (index = 0; index < n; index++) {
    svar = (float)(inputImageRecv[index]) - mean;
    varSum += svar * svar;
}
MPI_Allreduce(&varSum, &var, 1, MPI_FLOAT, MPI_SUM, MPI_COMM_WORLD);
var /= (float)(n * size);
std = sqrtf(var);
for (index = 0; index < n; index++)
    outputImage[index] = (inputImage[index] - mean)/std;

MPI_Gather(outputImage, n, MPI_INT, outputImageRecv, n, MPI_INT, MASTER, MPI_COMM_WORLD);

6. задатак

Поставка

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

...
if (rank == MASTER) {
    for (i = 1; i < size; i++)
        MPI_Send(arr + i * chunk, chunk, MPI_INT, i, 1000, MPI_COMM_WORLD);
} else {
    MPI_Status status;
    MPI_Recv(buff, chunk, MPI_INT, MASTER, 1000, MPI_COMM_WORLD, &status);
}

Решење

Предности колективне комуникације су што може да значајно олакша посао програмеру, који уместо да ручно пише сенд/рецеиве команде може да то остави МПИ да одради, и коришћењем метода колективне комуникације такође јасније МПИ дајемо до знања шта желимо да урадимо, па он може да оптимизује комуникацију на начин који је специфичан за наш проблем. Горњи блок кода може се заменити MPI_Scatter позивом: 

MPI_Scatter(arr, chunk, MPI_INT, buff, chunk, MPI_INT, MASTER, MPI_COMM_WORLD);

7. задатак

Поставка

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

  1. П1,Р,А0
  2. П0,W,А0
  3. П2,Р,А0
  4. П0,W,А2
  5. П1,W,А2
  6. П2,W,А1
  7. П0,Р,А1
  8. П0,Р,А0
  • Написати стања кохеренције у свим процесорима и стање меморије после сваке промене и скицирати описани систем у тренутку 8.
  • Колико пута који од процесора приступа меморији? За сваки приступ навести разлог.
  • Колики је Хит Рате за сваки од процесора (бројати и читање и упис, приказати збирно)?

Решење

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

Тренутак 1

Садржај кешева
П0 П1 П2 П3
А0 С 0
Садржај меморије
А0 0
А1 0
А2 0
А3 0

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

Тренутак 2

Садржај кешева
П0 П1 П2 П3
А0 M 1 А0 I 0
Садржај меморије
А0 0
А1 0
А2 0
А3 0

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

Тренутак 3

Садржај кешева
П0 П1 П2 П3
А0 С 1 А0 I 0 А0 С 1
Садржај меморије
А0 1
А1 0
А2 0
А3 0

П0 је приступао меморији како би уписао свој податак (флусх) а затим је П2 приступио како би тај податак прочитао (РМ).

Тренутак 4

Садржај кешева
П0 П1 П2 П3
А2 M 1 А0 I 0 А0 С 1
Садржај меморије
А0 1
А1 0
А2 0
А3 0

П0 је приступао меморији како би прочитао податак А2 ради уписа (WМ).

Тренутак 5

Садржај кешева
П0 П1 П2 П3
А2 I 1 А2 M 2 А0 С 1
Садржај меморије
А0 1
А1 0
А2 1
А3 0

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

Тренутак 6

Садржај кешева
П0 П1 П2 П3
А2 I 1 А2 M 2 А0 С 1
А1 M 1
Садржај меморије
А0 1
А1 0
А2 1
А3 0

П2 је приступао меморији како би прочитао податак А1 ради уписа (WМ).

Тренутак 7

Садржај кешева
П0 П1 П2 П3
А2 I 1 А2 M 2 А0 С 1
А1 С 1 А1 С 1
Садржај меморије
А0 1
А1 1
А2 1
А3 0

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

Тренутак 8

Садржај кешева
П0 П1 П2 П3
А0 С 1 А2 M 2 А0 С 1
А1 С 1 А1 С 1
Садржај меморије
А0 1
А1 1
А2 1
А3 0

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

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