Контрольные вопросы и задания

1. Что такое независимые подзадачи?

2. Сколько чисел складывается на третьем шаге в задаче сложения n чисел с помощью p процессоров? Как это количество зависит от значений n и p?

3. Сколько процессоров используется на третьем шаге в задаче сложения n чисел с помощью p процессоров? Как это количество зависит от значений n и p?

4. Какое количество слагаемых остается к началу четвертого шага в задаче сложения n чисел с помощью p процессоров? Как это количество зависит от значений n и p?

5. Как оценить долю  последовательных вычислений в задаче вычисления скалярного произведения векторов?

6. Что такое распределенная структура данных, чем отличаются логические связи от топологических?

7. Какими свойствами обладает алгоритм обхода?

8. В чем заключается метод поиска в ширину?

9. В чем заключается метод поиска в глубину?

10. Какова сложность алгоритма обхода, приведенного в параграфе 2.2?

11. Сколько связей имеется в архитектуре распределенной системы в виде гиперкуба?

12. В чем различие между алгоритмами обхода и алгоритмами выбора?

13. Какова сложность алгоритма выбора, приведенного в параграфе 2.2?

14. Почему в оценке сложности используется величина диаметра графа распределенной системы?

15. Что такое «остовное дерево»?

16. Чем характеризуется дисциплина FIFO?

Задачи для самостоятельного решения

1. Выведите формулу количества используемых процессоров в зависимости от номера шага в задаче суммирования n чисел с помощью p процессоров.

2. Оцените сложность перемножения квадратных матриц размером nn на многопроцессорной ЭВМ с p процессорами и общей памятью.

3. Оцените сложность решения системы линейных алгебраических уравнений методом Гаусса на многопроцессорной ЭВМ с p процессорами и общей памятью.

4. Оцените сложность решения системы линейных алгебраических уравнений методом простой итерации на многопроцессорной ЭВМ с p процессорами и общей памятью.

5. Разработайте параллельный алгоритм, проверяющий изоморфны ли два графа. Графы заданы матрицами смежностей вершин, располагающимися в общей памяти. Предполагается, что вычислительная система содержит p универсальных процессоров, работающих независимо. Проведите оценку сложности алгоритма.

6. Разработайте параллельный алгоритм, проверяющий изоморфны ли два графа. Графы заданы матрицами смежностей вершин, располагающимися в общей памяти. Вычисления производятся массивом GPU, т.е. одновременно выполняется одна и та же команда над разными наборами данных. Оцените сложность разработанного алгоритма.

7. Разработайте распределенный алгоритм, вычисляющий максимальную степень вершины графа – узла распределенной вычислительной системы. Этот алгоритм относится к классу self-aware, т.е. исследуется граф самой вычислительной системы. Результат вычисления должен быть сообщен всем узлам распределенной системы. Оцените сложность алгоритма в зависимости от количества узлов в системе.

8. Разработайте распределенный алгоритм, вычисляющий диаметр графа – максимальное из расстояний между парами вершин – узлов распределенной вычислительной системы. Граф изображает структуру этой системы.