Мултипроцесорски системи/К2 2020
Други колоквијум 2020. године одржан је 7. децембра. Трајао је 105 минута и поставка је доступна са странице предмета.
1. задатак
Поставка
Објаснити принцип паралелизације код датафлоw програмског модела. Нацртати структуру оваквог система и објаснити принцип функционисања.
Решење
Датафлоw програмски модел постиже паралелизацију представљањем програма као графа са блоковима инструкција као чворовима који могу да се изврше чим су им подаци спремни. Гране оваквог графа представљају зависности по подацима. Између чворова се прослеђује токен извршавања, и сви чворови који имају токен се извршавају у паралели.
2. задатак
Поставка
Објаснити предности и недостатке примене заједничке кеш меморије у мултипроцесорским системима.
Решење
Предности:
- Позитивна интерференција: податак који је довукао један процесор може служити и другом.
- Нема потребе водити рачуна о кохеренцији кеша.
- Избегава се лажна дељивост.
Мане:
- Негативна интерференција: податак који је довукао један процесор може бити избачен од стране другог.
- Што је кеш меморија већа то је и спорија.
- Сви процесори приступају истој кеш меморији, па им је пропусни опсег заједно ограничен
3. задатак
Поставка
Каква је мотивација за унапређење у протоколу МЕСИФ? Објаснити семантику додатног стања. Прецизно објаснити све акције које су везане за ове стање и нацртати само део дијаграма стања везан за ово стање.
Решење
У МЕСИ протоколу се у S стању није знало ко ће приликом операције Transfer, односно преношења податка из једне у другу кеш меморију, бити тај који преноси податак. Новоуведено стање F (форwард) је исто као S осим што служи да означи процесор који ће радити то прослеђивање податка преко магистрале. Додељује се процесору који је последњи прочитао податак, тако да се у ово стање улази чим се прочита податак са магистрале, а из њега излази чим се детектује читање или упис.
4. задатак
Поставка
Дискутовати како се реорганизацијом дељених структура података са могућностима уписа у мултипроцесорском систему могу побољшати перформансе у следећим случајевима: а) низ стуктура[сиц] са два поља којима приступају два различита процеса и б) низ чији елементи су мањи од величине блока којима приступају различити процеси.
Решење
Низ структура са по два поља се може претворити у два низа, тако да сваки процесор приступа другачијем делу меморије и неће избацивати један другог из респективних кеш меморија (изазивати лажну дељивост). Низ са елементима мањим од величине блока се може изменити тако да сваки елемент садржи довољно празног простора (паддинг) унутар себе да процесори не дохвате елементе осталих процесора приликом дохватања својих.
5. задатак
Поставка
Коришћењем МПИ технологије паралелизовати функцију у прилогу која врши проналажење свих индекса у стринг стр на којима се налази знак ц. Обратити пажњу на ефикасност паралелизације. Сматрати да је МПИ окружење већ иницијализовано и да сви процеси треба да учествују у обради. Процес са рангом 0 добија улазне податке, расподељује их осталим процесима, учествује у обради и сакупља резултате. Пронађени индекси у резултујућем низу треба да одговарају улазном низу. Сматрати да алокације меморије увек успевају.
int* find_all_occurences(char* str, char c) {
int* loc = malloc(sizeof(int) * strlen(str)), j = 0;
for (int i = 0; i < strlen(str); i++) {
if (str[i] == c) {
loc[j++] = i;
}
}
loc = realloc(loc, (j + 1) * sizeof(int));
loc[j] = -1;
return loc;
}
Решење
#define MASTER 0
int* find_all_occurences(char* str, char c, int length, int* locSize) {
int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
int* loc = malloc(sizeof(int) * length);
*locSize = 0;
for (int i = 0; i < length; i++) {
if (str[i] == c) {
loc[(*locSize)++] = i + rank * length;
}
}
return loc;
}
int main(void) {
// ...
MPI_Status status;
int size;
int rank;
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
char *str, c;
if (rank == MASTER) {
// Input str, c
}
int length = strlen(str);
int chunk = length / size;
MPI_Bcast(&chunk, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
MPI_Bcast(&c, 1, MPI_CHAR, MASTER, MPI_COMM_WORLD);
char* myStr;
if (rank == MASTER) {
myStr = str;
for (int i = 1; i < size; ++i) {
MPI_Send(str + i * chunk, chunk, MPI_CHAR, i, 0, MPI_COMM_WORLD);
}
} else {
myStr = malloc(chunk * sizeof(char));
MPI_Recv(myStr, chunk, MPI_CHAR, MASTER, 0, MPI_COMM_WORLD, &status);
}
int locSize = 0;
int* loc = find_all_occurences(myStr, c, chunk, &locSize);
if (rank == MASTER) {
int totalLocSize = locSize;
loc = realloc(loc, length * sizeof(int));
for (int i = 1; i < size; ++i) {
int otherLocSize;
MPI_Recv(&otherLocSize, 1, MPI_INT, i, 1, MPI_COMM_WORLD, &status);
MPI_Recv(loc + totalLocSize, otherLocSize, MPI_INT, i, 2, MPI_COMM_WORLD, &status);
totalLocSize += otherLocSize;
}
loc = realloc(loc, (totalLocSize + 1) * sizeof(char));
loc[totalLocSize] = -1;
} else {
MPI_Send(&locSize, 1, MPI_INT, MASTER, 1, MPI_COMM_WORLD);
MPI_Send(loc, locSize, MPI_INT, MASTER, 2, MPI_COMM_WORLD);
free(loc);
}
free(str);
// ...
}
6. задатак
Поставка
Каква је улога бафера приликом МПИ комуникације између тачно два процеса (поинт-то-поинт комуникације)? Какву врсту комуникације бафери омогућавају? Да ли програмер свестан постојања бафера? Одговор илустровати сликом.
Решење
Системски бафер у МПИ служи за асинхроно примање и слање података, али такође служе и за руковање ситуацијом када процесу стигну поруке које не може одмах да обради. Системски бафер је транспарентан за програмера.
7. задатак
Поставка
Дат је мултипроцесорски систем са 4 идентична процесора, који користи МОЕСИ протокол за одржавање кохеренције кеш меморије. Свака кеш меморија има по 2 улаза, који су величине једне речи. Пресликавање је директно. Почетне вредности података су 0. Сваки упис увећава вредност измењеног податка за 1. На почетку су све кеш меморије празне. Дата је следећа секвенца приступа меморији:
- П0,Р,А0
- П2,Р,А0
- П0,W,А0
- П1,Р,А0
- П0,W,А0
- П0,W,А2
- П0,Р,А1
- П2,W,А0
- Написати стања кохеренције у свим процесорима и стање меморије после сваке промене и скицирати описани систем у тренутку 8.
- Колико пута који од процесора приступа меморији? За сваки приступ навести разлог.
- Колики је Хит Рате за сваки од процесора (бројати и читање и упис, приказати збирно)?
Решење
| ЦПУ | Број погодака | Укупан број приступа | Хит рате | Приступи меморији |
|---|---|---|---|---|
| П0 | 2 | 6 | 33% | РМ, WХ, WХ, флусх, WМ, РМ |
| П1 | 0 | 1 | 0% | Трансфер |
| П2 | 0 | 2 | 0% | Трансфер, WМ |
| П3 | 0 | 0 | 0% |
Тренутак 1
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А0 | Е | 0 | |||||||||
| А0 | 0 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П0 је приступао меморији како би дохватио податак са А0 (РМ).
Тренутак 2
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А0 | С | 0 | А0 | С | 0 | ||||||
| А0 | 0 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П2 је покушао да приступи меморији како би дохватио податак са А0, али га је П0 кеш опслужио уместо меморије (Трансфер).
Тренутак 3
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А0 | M | 1 | А0 | I | 0 | ||||||
| А0 | 0 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П0 је у свој кеш уписао вредност А0 и није приступао меморији (WХ), већ само поништио остале копије на магистрали (БусУпгр).
Тренутак 4
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А0 | О | 1 | А0 | С | 1 | А0 | I | 0 | |||
| А0 | 0 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П1 је покушао да приступи меморији како би дохватио податак са А0, али га је П0 кеш опслужио уместо меморије (Трансфер).
Тренутак 5
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А0 | M | 2 | А0 | I | 1 | А0 | I | 0 | |||
| А0 | 0 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П0 је у свој кеш уписао вредност А0 и није приступао меморији (WХ), већ само поништио остале копије на магистрали (БусУпгр).
Тренутак 6
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А2 | M | 1 | А0 | I | 1 | А0 | I | 0 | |||
| А0 | 2 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П0 је прво одрадио упис свог локалног податка у меморију (флусх), а затим дохватио податак А2 из меморије ради уписа (WМ).
Тренутак 7
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А2 | M | 1 | А0 | I | 1 | А0 | I | 0 | |||
| А1 | Е | 0 | |||||||||
| А0 | 2 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П0 чита податак А1 из меморије (РМ).
Тренутак 8
| П0 | П1 | П2 | П3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| А2 | M | 1 | А0 | I | 1 | А0 | M | 3 | |||
| А1 | Е | 0 | |||||||||
| А0 | 2 |
|---|---|
| А1 | 0 |
| А2 | 0 |
| А3 | 0 |
П2 чита податак А0 из меморије ради уписа (WМ).