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

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

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

1. задатак

Поставка

Скицирати и објаснити генеричку паралелну архитектуру и њене делове. Како се ова општа архитектура може прилагодити да ефикасно подржава поједине програмске моделе?

Решење

Генеричка паралелна архитектура се састоји од више процесора, сваки са својим кешом, заједничке меморије и комуникационог асистента, где сви комуницирају преко магистрале. Комуникациони асистент је компонента за комуникацију преко мреже, која може бити адаптирана у зависности од потреба конкретних програмских модела:

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

2. задатак

Поставка

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

Решење

Исто као први задатак са другог колоквијума 2021. године.

3. задатак

Поставка

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

Решење

При упису у податак, процесор који је уписао прелази у стање M а сви остали процесори када то детектују прелазе у стање I. Уколико је процесор био у стању M пре детекције уписа, он ради операцију флусх, а у супротном преноси вредност податка/блока процесору који уписује (ако није у стању I). Уколико више процесора у стању С жели да пренесе процесору који уписује вредност податка/блока, МЕСИ не дефинише начин на који се то ради. Овај проблем је решен каснијим протоколима (МЕСИФ, МОЕСИ).

4. задатак

Поставка

Шта је процесорска локалност? Дефинисати параметар који је индикатор процесорске локалности. У односу на вредност овог параметра коментарисати када боље перформансе има стратегија инвалидације, а када стратегија ажурирања.

Решење

Процесорска локалност је особина податка да се користи на само једном процесору. Индикатор процесорске локалности податка јесте дужина wрите рун, односно колико пута је процесор успео да упише у податак у свом кешу пре него што му је неки други процесор преотео тај податак. Дужи уписни низ показује да је тај податак више локалан за одређен процесор, док краћи уписни низ показује да је више дељен а мање локалан. У односу на ово, стратегија инвалидације је кориснија код дужих уписних низова, јер поништава застареле копије, док код краћих уписних низова изазива много поновних приступа меморији након инвалидације, где је стратегија ажурирања кориснија.

5. задатак

Поставка

Коришћењем МПИ технологије написати део кода који рачуна број ПИ коришћењем Лајбницове формуле:

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

Решење

#define MASTER 0

int main(void) {
    // ...
    int rank;
    int size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    int maxIter;
    if (rank == MASTER) {
        scanf("%d", &maxIter);
    }
    MPI_Bcast(&maxIter, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
    double pi;
    for (int i = rank; i < maxIter; i += size) {
        pi += ((i & 1) ? -1. : 1.)/(2. * i + 1.);
    }
    double totalPi;
    MPI_Allreduce(&pi, &totalPi, 1, MPI_DOUBLE, MPI_SUM, MPI_COMM_WORLD);
    printf("%lf\n", totalPi);
    // ...
    return 0;
}

6. задатак

Поставка

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

Решење

Предност коришћења група и комуникатора је у томе што можемо да ограничимо на који начин могу процеси да комуницирају, и да комуникацију вршимо у мањим групама. 

#define MASTER 0

int main(void) {
    // ...
    int n;
    int rank;
    MPI_Comm_size(MPI_COMM_WORLD, &n);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    int x;
    if (rank == MASTER) {
        // Input x
    }
    MPI_Group globalGroup;
    MPI_Comm_group(MPI_COMM_WORLD, &globalGroup);
    MPI_Comm newComm;
    MPI_Group newGroup;
    int ranges[][3] = {{0, n/2, 1}};
    MPI_Group_range_incl(globalGroup, 1, ranges, &newGroup);
    MPI_Comm_create(MPI_COMM_WORLD, newGroup, &newComm);
    if (rank < n/2) {
        MPI_Bcast(&x, 1, MPI_INT, MASTER, newComm);
    }
    // ...
}

7. задатак

Поставка

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

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

Решење

ЦПУ Број погодака Укупан број приступа Хит рате Приступи меморији
П0 1 7 14.3% WМ, флусх, WМ, флусх, РМ, РМ, РХ
П1 0 2 0% РМ, РМ
П2 0 1 0% РМ
П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 С 0 А0 С 0
Садржај меморије
А0 0
А1 0
А2 0
А3 0

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

Тренутак 3

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

П0 чита податак А0 са намером уписа (WМ), такође инвалидирајући остале податке том приликом.

Тренутак 4

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

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

Тренутак 5

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

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

Тренутак 6

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

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

Тренутак 7

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

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

Тренутак 8

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

П0 чита податак А0 из свог кеша (РХ).

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