1 (10).
Операция реляционной алгебры R(A, B) ⊲⊳ B<C S(C, D)
возвращает все наборы (a, b, c, d) такие, что набор (a, b) находится в отношении R, набор (c, d) -- в отношении S и b < c. Напишите MapReduce-реализацию этой операции в предположении, что R и S -- множества.
[Оригинал:
The relational-algebra operation R(A, B) ⊲⊳ B<C S(C, D)
produces all tuples (a, b, c, d) such that tuple (a, b) is in relation R, tuple (c, d) is in S, and b < c. Give a MapReduce implementation of this operation, assuming R and S are sets.]
2 (10). Разреженной (sparse) матрицей называется матрица, состоящая преимущественно из нулей. Примером такой матрицы может служить матрица смежностей из алгоритма PageRank или матрица смежностей графа "друзей" социальной сети. На диске хранятся только ненулевые значения элементов разреженной матрицы, что позволяет существенно экономить место. Как изменятся двухшаговый и одношаговый MapReduce-алгоритмы умножения матриц для разреженных матриц?
3 (10). Опишите постановку задачи сортировки массива чисел во фреймворке MapReduce. Реализуема ли в MapReduce сортировка слиянием (merge sort)? битонная сортировка (bitonic sort)? Если да, то как именно? Если нет, то что препятствует реализации? Что еще следует отметить про сортировку в MapReduce? Дайте развернутый ответ.
4 (10). Возможно ли реализовать фреймворк MapReduce средствами MPI? Какой именно функционал для этого потребуется реализовать? Какие при этом будут сложности и ограничения? Что еще можно отметить про реализацию MapReduce в MPI? Дайте развернутый ответ.
К экзамену: Студенты, не набравшие желаемую суммарную оценку в течение семестра, должны выполнить задания 1--4, и пройти устное собеседование (+10) по этим заданиям и лекционному материалу. Для каждого из заданий 1--4 необходимо привести пример выполнения алгоритма (на бумаге). Вопросы к устному собеседованию: /parallel/questions.html.
parallel