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

Упражнение 1:

Номер 1

Верно ли что:

Ответ:

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

(2) в общем случае сети сортировки эффективны при выполнении на одном процессоре

(3) из того, что оценки времен выполнения двух алгоритмов A1 и A2 находятся в отношении O(A1)< O(A2) следует, что время выполнения первого алгоритма будет меньше, чем время выполнения второго алгоритма

Номер 2

Верно ли что:

Ответ:

(1) сети сортировки обеспечивают возможность построения эффективных параллельных алгоритмов сортировки

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

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

Номер 3

Верно ли что:

Ответ:

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

(2) для построения сети сортировки Бетчера необходима многопроцессорная система

(3) сети сортировки на системах с общей памятью выполняются эффективнее, чем на системах с распределенной памятью

Упражнение 2:

Номер 1

Число шагов выполнения компараторов сортировки-слияния при использовании нечетно-четного слияния Бэтчера на p процессорах оценивается как:

Ответ:

(1) 0.5*(log2(p))²

(2) p*log2(p)

(3) log2(p)

Номер 2

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

Ответ:

(1) (n/p)*( log2(n/p) + 0.5*(log2(p))² )

(2) (n/p)*( log2(n/p) + log2(p) )

(3) (n/p)*log2(n/p) + p*log2(p)

Номер 3

Число операций выполняемых одним компаратором сортировки-слияния на одном процессоре оценивается как:

Ответ:

(1) (n/p)

(2) 2*(n/p)

(3) (n/p)*log2(n/p)

Упражнение 3:

Номер 1

Принцип нулей и единиц применим для доказательства правильности алгоритмов сортировки:

Ответ:

(1) основанных на сравнениях-перестановках, в том числе на сетях

(2) поразрядных сортировок

(3) любых сортировок

Номер 2

Во сколько раз в среднем сократится объем передаваемых данных при использовании алгоритма предварительного анализа числа элементов, передать которые необходимо для выполнения одной операции компаратора слияния:

Ответ:

(1) в 4 раза

(2) в 2 раза

(3) не сократится

Номер 3

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

Ответ:

(1) близка к 100%

(2) оценивается как log n/(log p)²

(3) оценивается как 1/(log p)

Упражнение 4:

Номер 1

Отметьте сети, правильно сортирующие любой массив из 4-х элементов с помощью компараторов слияния (a,b) выполняющих сравнение-перестановку элементов с номерами a и b:

Ответ:

(1) (0-1), (0-2), (1-2), (1-3), (2-3)

(2) (0-1), (2-3), (1-3), (1-2), (0-2)

(3) (0-1), (2-3), (0-2), (1-3), (1-2)

Номер 2

Отметьте сети, правильно сортирующие любой массив из 4-х элементов с помощью компараторов слияния (a,b) выполняющих сравнение-перестановку элементов с номерами a и b:

Ответ:

(1) (0-1), (1-3), (2-3), (0-1), (1-3), (2-3)

(2) (0-1), (2-3), (1-2), (0-1), (2-3), (1-2)

(3) (1-2), (0-2), (1-3), (1-2), (0-2), (1-3)

Номер 3

Отметьте сети, правильно сортирующие любой массив из 4-х элементов с помощью компараторов слияния (a,b) выполняющих сравнение-перестановку элементов с номерами a и b:

Ответ:

(1) (1-2), (0-2), (1-3), (0-2), (1-3) , (1-2)

(2) (0-1), (1-2), (2-3), (0-1), (1-2), (0-1)

(3) (0-1),(1-2),(2-3),(0-3),(0-1),(1-2)

Упражнение 5:

Номер 1

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

Ответ:

(1) 3

(2) 4

(3) 6

Номер 2

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

Ответ:

(1) 3

(2) 5

(3) 6

Номер 3

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

Ответ:

(1) 3

(2) 4

(3) 5

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