Введение в параллельные алгоритмы

Ускорение, достигаемое при использовании метода коллективного решения, ограничена:

• числом доступных процессоров
• латентностью каналов межпроцессорной связи
• (Правильный ответ) отношением времени решения элементарного задания к суммарному времени обмена связанными с ним данными между процессором-мастером и обрабатывающим процессором

Укажите наиболее точную оценку числа тактов необходимых для упорядочивания 1 000 000 элементов массива методом пирамидальной сортировки, если операция сравнения и перестановки двух элементов занимает 1 такт:

• (Правильный ответ) 6 000 000
• 1 000 000 000 000
• 1 000 000

Верно ли что:

• (Правильный ответ) блоки данных, размещенные на каждом из процессоров при упорядочивании сетью сортировки со слиянием Бэтчера должны быть одинакового размера
• сети сортировки на системах с общей памятью выполняются эффективнее, чем на системах с распределенной памятью
• для построения сети сортировки Бетчера необходима многопроцессорная система

Вычислительные системы с распределенной памятью:

• обеспечивают линейное ускорение при увеличении числа используемых для расчета узлов
• позволяют эффективно решать задачи, требующие интенсивного взаимодействия между вычислительными узлами
• (Правильный ответ) могут состоять из вычислительных узлов, являющихся системами с общей памятью

Максимальное число процессоров, эффективное использование которых возможно при построении стены Фокса методом конвейерного параллелизма, не превышает:

• высоты стены
• общего числа кирпичей в стене
• (Правильный ответ) ширины стены (числа кирпичей в её основании)

За какое время можно вычислить значение любого { xi mod G(x) }, где G(x) – полином степени k?

• (Правильный ответ) за время, пропорциональное log(i)
• (Правильный ответ) за время, пропорциональное i
• за время, равное времени вычисления x100 mod G(x)

Какое минимальное количество параллельных шагов необходимо для сортировки с помощью сети (0-1), (1-2), (2-3), (0-1), (1-2), (0-1):

• 6
• (Правильный ответ) 5
• 3

Применение метода встречной прогонки на p процессорах при числе уравнений равном p2 обеспечивает эффективность:

• (Правильный ответ) порядка 33%
• порядка 99%
• порядка 66 %

Алгоритм глобального стека предполагает:

• наличие управляющего процессора
• наличие возможности передачи сообщений в асинхронном режиме
• (Правильный ответ) наличие одного ресурса, в котором хранится часть заданий на интегрирование

Верно ли, что для многопроцессорных систем важны следующие свойства генераторов псевдослучайных чисел:

• (Правильный ответ) одна и та же последовательность может быть сформирована с помощью каждого из трех методов: 1) M-последовательностей, 2) генератора на сдвиговом регистре, 3) генератора на основе примитивных полиномов
• успешное прохождение батареи тестов Diehard гарантирует применимость последовательности для решения прикладных задач
• для тестирования последовательности с помощью батареи тестов Diehard необходима многопроцессорная система

Чему равен период генератора xk mod (x2+x+1):

• 4
• (Правильный ответ) 3
• 2

Чему равен период генератора u[i+1]=(5* u[i]+7) mod 16, i>0:

• (Правильный ответ) 16
• 7
• зависит от значения u[0]

Общее время сортировки n элементов методом нечетно-четного слияния Бэтчера на p процессорах оценивается как:

• (n/p)*( log2(n/p) + log2(p) )
• (n/p)*log2(n/p) + p*log2(p)
• (Правильный ответ) (n/p)*( log2(n/p) + 0.5*(log2(p))2 )

Чему равен период генератора u[i+1]=(3* u[i]+2) mod 8, i>0:

• (Правильный ответ) зависит от значения u[0]
• 8
• 7

число операций при решении трехдиагональной системы из N линейных уравнений методом прогонки пропорционально:

• N2
• (Правильный ответ) N
• log(N)

Чему равен период генератора xk mod (x2+1), x>1?

• 3
• 2
• 5
• 1
• (Правильный ответ) 4

Чему равно x32 mod (x4+x+1):

• 1
• x
• (Правильный ответ) x2

Эффективность параллельного алгоритма сортировки n элементов на p процессорах с помощью сетей нечетно-четного слияния Бэтчера в предположении нулевой латентности и нулевого времени на передачу данных равна:

• близка к 100%
• (Правильный ответ) оценивается как log n/(log p)2
• оценивается как 1/(log p)

Какое минимальное количество параллельных шагов необходимо для сортировки с помощью сети (0-1), (2-3), (0-2), (1-3), (1-2):

• 5
• (Правильный ответ) 3
• 4

Что такое упорядоченная пирамида:

• пирамида называется упорядоченной, если для любого корня вес левого потомка не меньше веса правого потомка
• (Правильный ответ) пирамида называется упорядоченной, если вес любого корня не меньше веса его потомков
• пирамида называется упорядоченной, если вес любой вершины на уровне k не меньше веса любой вершины на уровне k-1

При упорядочивании массива из N элементов с помощью пирамидальной сортировки:

• (Правильный ответ) число операций в худшем случае пропорционально N*log(N)
• при сортировке уже упорядоченного массива число операций пропорционально N
• необходимо использование дополнительной памяти для хранения N элементов

Использование упреждающей рассылки элементов ведущей строки на p процессоров:

• позволяет сократить общее число вычислительных операций
• (Правильный ответ) следует выполнять в асинхронном режиме
• (Правильный ответ) позволяет сократить время вычислений

Использование локальных стеков:

• необходимо для сокращения суммарного объема хранимых в каждый момент времени данных
• (Правильный ответ) позволяет сократить накладные расходы на взаимодействие между процессорами
• обеспечивает взаимодействие между процессами

Метод коллективного решения:

• является методом статической балансировки загрузки
• используется при совместной работе над проектом нескольких программистов
• (Правильный ответ) может обеспечить эффективное решение множества независимых друг от друга задач, каждая из которых требует для своей обработки разного времени

Метод глобального стека является:

• (Правильный ответ) основан на принципах централизованного управления вычислительным процессом
• (Правильный ответ) методом динамической балансировки загрузки процессоров
• основан на методе геометрического параллелизма

Буферизация при асинхронной передаче данных необходима для:

• уменьшения объемов используемой памяти
• (Правильный ответ) сокращения общего времени взаимных ожиданий
• сокращения времени передачи сообщений

Укрупнение заданий, единовременно передаваемых на обработку в методе коллективного решения:

• (Правильный ответ) приводит к сокращению затрат на взаимодействие между процессорами
• приводит к увеличению общего объема передаваемых между процессорами данных
• (Правильный ответ) может приводить к увеличению дисбаланса распределения по процессорам вычислительной нагрузки