ВС SPMD-архитектуры, содержащей n= 2 процессоров, найдите ссылку на последний элемент списка N элементов. Воспользуйтесь методом параллельной подстановки ссылок, дающим решение за lg2N шагов. Непосредственный поиск "нулевой" ссылки производится за ]N/n[ шагов, что может быть значительно дольше. N=12
(Отметьте один правильный вариант ответа.)
Варианты ответа
Процессор 0 | Процессор 1 | |
---|---|---|
Цикл 1 | 1→4 | 2→5 |
Цикл 2 | 3→2 | 4→6 |
Цикл 3 | 5→7 | 6→8 |
Цикл 4 | 7→9 | 8→10, "пустая ссылка" |
Процессор 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, нет ссылки |
непосредственный поиск "пустой" ссылки производится за столько же циклов