Главная / Программирование /
Параллельное программирование / Тест 1
Номер 3
Ответ:
Параллельное программирование - тест 1
Упражнение 1:
Номер 1
Ответ:
Номер 1
Для ВС SPMD-архитектуры, содержащей 4 процессора, составьте таблицу параллельного логического вывода на основе языка ПРОЛОГ по сложной цели, исключающего перебор и backtracking. Мать (марья, Y)
Ответ:
(1)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| мать (марья, Y) | 1 | X=марья, Y=? | |
| 0 | родитель (марья, Y) | 7 | |
| 0 | родитель (марья, иван) | 1 | X=марья, Y=иван |
| 1 | не проходит унификация | 1 | |
| 2 | родитель (марья, василий) | 1 | X=марья, Y=василий |
| 3 | не проходит унификация | 1 | |
| 0 | не проходит унификация | 1 | |
| 1 | не проходит унификация | 1 | |
| 2 | не проходит унификация | 1 |
(2)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| мать (марья, Y) | 1 | X=марья, Y=? | |
| 0 | родитель (марья, Y) | 7 | |
| 0 | родитель (марья, иван) | 1 | X=марья, Y=иван |
| 1 | родитель (марья, василий) | 1 | X=марья, Y=василий |
(3)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| мать (марья, Y) | 1 | X=марья, Y=? | |
| 0 | родитель (марья, Y) | 7 | |
| 1 | родитель (марья, иван) | 1 | X=марья, Y=иван |
| 0 | родитель (марья, василий) | 1 | X=марья, Y=василий |
Номер 2
Ответ:
Для ВС SPMD-архитектуры, содержащей 4 процессора, составьте таблицу параллельного логического вывода на основе языка ПРОЛОГ по сложной цели, исключающего перебор и backtracking. Отец (Х, иван)
Ответ:
(1)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| отец (Х,иван) | 1 | X=?, Y=иван | |
| 0 | мужчина (Х), родитель (Х, иван) | 5 | |
| 0 | не проходит унификация | 1 | |
| 1 | не проходит унификация | 1 | |
| 2 | родитель (петр, иван) | 1 | X=петр, Y=иван |
| 3 | не проходит унификация | 1 | |
| 0 | не проходит унификация | 1 | |
| 0 | не проходит унификация | 1 |
(2)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| отец (Х,иван) | 1 | X=?, Y=иван | |
| 0 | мужчина (Х),родитель (Х, иван) | 5 | |
| 1 | родитель (петр, иван) | 1 | X=петр, Y=иван |
(3)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| отец (Х,иван) | 1 | X=?, Y=иван | |
| 0 | мужчина (Х),родитель (Х, иван) | 5 | |
| 0 | родитель (петр, иван) | 1 | X=петр, Y=иван |
Для ВС SPMD-архитектуры, содержащей 4 процессора, составьте таблицу параллельного логического вывода на основе языка ПРОЛОГ по сложной цели, исключающего перебор и backtracking. Отец (иван, Y)
Ответ:
(1)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| отец (иван, Y) | 1 | X= иван, Y=? | |
| 0 | родитель (иван, Y) | 7 | |
| 0 | не проходит унификация | 1 | |
| 1 | родитель (иван, елена) | 1 | X= иван, Y= елена |
| 2 | не проходит унификация | 1 | |
| 3 | не проходит унификация | 1 | |
| 0 | не проходит унификация | 1 | |
| 1 | не проходит унификация | 1 | |
| 2 | не проходит унификация | 1 |
(2)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| отец (иван, Y) | 1 | X= иван, Y=? | |
| 0 | родитель (иван, Y) | 7 | |
| 1 | родитель (иван, елена) | 1 | X= иван, Y= елена |
(3)
| Обрабатывающий процессор | Фрейм | Счетчик | Связывание переменных |
| отец (иван, Y) | 1 | X= иван, Y=? | |
| 0 | родитель (иван, Y) | 7 | |
| 0 | родитель (иван, елена) | 1 | X= иван, Y= елена |
Упражнение 3:
Номер 1
Ответ:
Номер 1
ВС SPMD-архитектуры, содержащей n= 2 процессоров, найдите ссылку на последний элемент списка N элементов. Воспользуйтесь методом параллельной подстановки ссылок, дающим решение заlg2Nшагов. Непосредственный поиск "нулевой" ссылки производится за]N/n[шагов, что может быть значительно дольше. N=8
Ответ:
(1)
| Процессор 0 | Процессор 1 | |
|---|---|---|
| Цикл 1 | 1→4 | 2→3 |
| Цикл 2 | 3→7 | 4→5 |
| Цикл 3 | 5→8 | 6 нет ссылки |
(2) непосредственный поиск "пустой" ссылки производится за столько же циклов
(3)
| Процессор 0 | Процессор 1 | |
|---|---|---|
| Цикл 1 | 1→3 | 2→4 |
| Цикл 2 | 3→5 | 4→6 |
| Цикл 3 | 5→7 | 6 нет ссылки |
Номер 2
Ответ:
ВС SPMD-архитектуры, содержащей n= 2 процессоров, найдите ссылку на последний элемент списка N элементов. Воспользуйтесь методом параллельной подстановки ссылок, дающим решение заlg2Nшагов. Непосредственный поиск "нулевой" ссылки производится за]N/n[шагов, что может быть значительно дольше. N=10
Ответ:
(1)
| Процессор 0 | Процессор 1 | |
|---|---|---|
| Цикл 1 | 1→2 | 2→5 |
| Цикл 2 | 3→4 | 4→6 |
| Цикл 3 | 5→8 | 6→7 |
| Цикл 4 | 7→10, нет ссылки | 8→9 |
(2) непосредственный поиск "пустой" ссылки, хоть и требует дополнительный цикл, зато менее трудоемок
(3)
| Процессор 0 | Процессор 1 | |
|---|---|---|
| Цикл 1 | 1→2 | 2→4 |
| Цикл 2 | 3→5 | 4→6 |
| Цикл 3 | 5→8 | 6→7 |
| Цикл 4 | 7→10, нет ссылки | 8→9 |
Номер 3
Ответ:
ВС SPMD-архитектуры, содержащей n= 2 процессоров, найдите ссылку на последний элемент списка N элементов. Воспользуйтесь методом параллельной подстановки ссылок, дающим решение заlg2Nшагов. Непосредственный поиск "нулевой" ссылки производится за]N/n[шагов, что может быть значительно дольше. N=12
Ответ:
(1)
| Процессор 0 | Процессор 1 | |
|---|---|---|
| Цикл 1 | 1→4 | 2→5 |
| Цикл 2 | 3→2 | 4→6 |
| Цикл 3 | 5→7 | 6→8 |
| Цикл 4 | 7→9 | 8→11 |
| Цикл 5 | 9→12 | 10, нет ссылки |
(2) непосредственный поиск "пустой" ссылки производится за столько же циклов
(3)
| Процессор 0 | Процессор 1 | |
|---|---|---|
| Цикл 1 | 1→4 | 2→5 |
| Цикл 2 | 3→2 | 4→6 |
| Цикл 3 | 5→7 | 6→8 |
| Цикл 4 | 7→9 | 8→10, "пустая ссылка" |
Упражнение 4:
Номер 1
Ответ:
Номер 1
ВС SPMD-архитектура содержит 4 процессора. Изобразите схему параллельного поиска и исключения из списка элемента с номером k. Список содержит 6 элементов, k = 3
Ответ:
(1)
| Процессоры | Комментарий | ||||||
| Цикл 1 | 0 | 1 | 2 | 3 | процессор 2 находит ссылку элемента 3 | ||
|---|---|---|---|---|---|---|---|
| Цикл 2 | 0 | 1 | процессор 1 находит ссылку на элемент 3 | ||||
| Цикл 3 | 2 | 3 | 0 | 1 | |||
| Цикл 4 | 2 | 3 | процессор3 меняет ссылку на 3 ссылкой на 5 | ||||
(2)
| Процессоры | Комментарий | ||||||
| Цикл 1 | 0 | 1 | 2 | 3 | процессор 2 находит ссылку элемента 3 | ||
|---|---|---|---|---|---|---|---|
| Цикл 2 | 0 | 1 | процессор 1 находит ссылку на элемент 3 | ||||
| Цикл 3 | 2 | 3 | 0 | 1 | 2 | 3 | процессор3 меняет ссылку на 3 ссылкой на 5 |
(3)
| Процессоры | Комментарий | ||||||
| Цикл 1 | 0 | 1 | 2 | 3 | процессор 2 находит ссылку элемента 3 и ссылку на элемент 3 | ||
|---|---|---|---|---|---|---|---|
| Цикл 2 | 0 | 1 | процессор 1 меняет ссылку на 3 ссылкой на 5 | ||||
Номер 2
Ответ:
ВС SPMD-архитектура содержит 4 процессора. Изобразите схему параллельного поиска и исключения из списка элемента с номером k. Список содержит 7 элементов, k = 6
Ответ:
(1)
| Процессоры | Комментарий | |||||||
| Цикл 1 | 0 | 1 | 2 | 3 | процессор 3 находит ссылку на элемент 6 | |||
|---|---|---|---|---|---|---|---|---|
| Цикл 2 | 0 | 1 | 2 | процессор 1 находит ссылку элемента 6 | ||||
| Цикл 3 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | процессор 2 находит ссылку на 6 ссылкой на 5 |
(2)
| Процессоры | Комментарий | |||||||
| Цикл 1 | 0 | 1 | 2 | 3 | процессор 3 находит ссылку на элемент 6 | |||
|---|---|---|---|---|---|---|---|---|
| Цикл 2 | 0 | 1 | 2 | процессор 1 находит ссылку элемента 6 и меняет ссылку на 6 ссылкой на 5 | ||||
(3)
| Процессоры | Комментарий | |||||||
| Цикл 1 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | процессор 3 находит ссылку на элемент 6, процессор 1 находит ссылку элемента 6 |
|---|---|---|---|---|---|---|---|---|
| Цикл 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | процессор 2 меняет ссылку на 6 ссылкой на 5 |
Номер 3
Ответ:
ВС SPMD-архитектура содержит 4 процессора. Изобразите схему параллельного поиска и исключения из списка элемента с номером k. Список содержит 5 элементов, k = 2
Ответ:
(1)
| Процессоры | Комментарий | |||||
| Цикл 1 | 0 | 1 | 2 | 3 | процессор 1 находит ссылку элемента 2 | |
|---|---|---|---|---|---|---|
| Цикл 2 | 0 | не найдена ссылка на элемент 2 | ||||
| Цикл 3 | 1 | 2 | 3 | 0 | 0 | процессор 2 ликвидирует ссылку элемента 2 |
(2)
| Процессоры | Комментарий | |||||
| Цикл 1 | 0 | 1 | 2 | 3 | 0 | процессор 1 находит ссылку элемента 2 |
|---|---|---|---|---|---|---|
| Цикл 2 | 1 | 2 | 3 | процессор 2 ликвидирует ссылку элемента 2 | ||
(3)
| Процессоры | Комментарий | |||||
| Цикл 1 | 0 | 1 | 2 | 3 | процессор 1 находит ссылку элемента 2, но, не найдя ссылку на элемент 2, ликвидирует ссылку этого элемента | |
|---|---|---|---|---|---|---|
Упражнение 5:
Номер 1
Ответ:
Номер 1
Исследуйте приемы параллельной обработки списков. Каким образом список можно интерпретировать как массив?
Ответ:
(1) создается массив – образ списка дополнением каждого его элемента "ссылкой на ссылку". Анализ таких ссылок обеспечивает возможность явного отображения связей между элементами массива. Этот массив становится опорным в процессе параллельной обработки по SPMD-технологии
(2) по числу процессоров выбирается несколько элементов списка, и каждый процессор последовательно ищет ссылку на искомый (в том числе последний) элемент. Процессор, нашедший эту ссылку, исключает элемент из списка
(3) на основе выделения массивов данных из элементов списка создается отдельный массив. Оставшаяся структура ссылок может рассматриваться как образ списка и самостоятельно оперативно обрабатываться
Номер 2
Ответ:
Исследуйте приемы параллельной обработки списков. Как обработка образа списка сокращает время решения задачи поиска в списке?
Ответ:
(1) за счет параллельных транзитивных преобразований ссылок, подобно реализации "пирамиды", поиск в списке длины N вместо максимального значения N производится за
log2N шагов
(2) образ списка обеспечивает полную и равную загрузку процессоров, но суммарное время поиска увеличивается
(3) время поиска сокращается незначительно
Номер 3
Ответ:
Исследуйте приемы параллельной обработки списков. Применимо ли формирование образа списка для обработки других структур – деревьев или графов? (Требует творческих размышлений)
Ответ:
(1) не применимо, т.к. эти структуры требуют последовательной обработки с ветвлением
(2) применимо, т.к. ссылка на более чем один элемент принципиально не влияет на возможность ее отображения по принципу "ссылка на ссылку" и легко учитывается обрабатывающим процессором
(3) такие структуры представляют альтернативные виды массивов – образов списка и требуют отображения несколькими дескрипторами