Задачи параллелизма на процессах

Первая задача

Номер варианта	Задача
1	Сумма элементов вектора
2	Вычисление среднего значения элементов вектора
3	Максимальное значение элементов вектора
4	Минимальное значение элементов вектора
5	Нахождение числа чередований знаков значений соседних элементов вектора
6	Нахождение числа нарушений упорядоченности соседних элементов вектора
7	Нахождение наиболее близких соседних элементов вектора
8	Нахождение наиболее отличающихся по значению соседних элементов вектора
9	Скалярное произведение векторов
10	Сумма элементов матрицы
11	Сумма значений по строкам матрицы
12	Сумма значений по столбцам матрицы
13	Максимальное значение элементов матрицы
14	Минимальное значение элементов матрицы
15	Нахождение максимальных значений по строкам матрицы
16	Нахождение максимальных значений по столбцам матрицы
17	Нахождение минимальных значений по строкам матрицы
18	Нахождение минимальных значений по столбцам матрицы
19	Интегрирование – метод прямоугольников
20	Интегрирование – метод трапеций
21	Интегрирование – метод Монте-Карло
22	Подсчет числа буквенных символов в строке
23	Подсчет частоты символа в строке
24	Подсчет числа слов в строке
25	Подсчет числа предложений в строке
26	Проверка лексикографической упорядоченности двух строк
27	Подсчет числа несовпадающих символов двух строк

Вторая задача

Номер варианта	Задача
1	Передача от одного всем (broadcast)
2	Передача от всех одному (reduce)
3	Передача от всех одному и рассылка (allreduce)
4	Обобщенная передача от одного всем (scatter)
5	Обобщенная передача от всех одному (gather)
6	Линейка
7	Кольцо
8	Звезда
9	Решетка-тор
10	Гиперкуб
11	Ленточная горизонтальная схема - умножение матрицы на вектор
12	Ленточная вертикальная схема - умножение матрицы на вектор
13	Ленточная горизонтальная схема - разбиение только матрицы А - умножение матрицы на матрицу
14	Ленточная горизонтальная схема А, вертикальное В - умножение матрицы на матрицу
15	Метод Гаусса – ленточная горизонтальная схема
16	Метод Гаусса – ленточная вертикальная схема
17	Метод Гаусса-Жордана
18	Итеративные методы (Якоби)
19	Итеративные методы (Зейделя)
20	Метод простой итерации
21	Сортировка пузырьком (алгоритм чет-нечетной перестановки)
22	Сглаживание изображения
23	Повышение контраста

Третья задача

Номер варианта	Задача
1	Умножение плотных матриц. Элементы типа double. Блочная схема, алгоритм Кэннона.
2	Умножение плотных матриц. Элементы типа double. Блочная схема, алгоритм Фокса.
3	Умножение плотных матриц. Элементы типа double. Алгоритм Штрассена.
4	Умножение разреженных матриц. Элементы типа double. Формат хранения матрицы – строковый (CRS).
5	Умножение разреженных матриц. Элементы типа double. Формат хранения матрицы – столбцовый (CCS).
6	Решение систем линейных уравнений методом сопряженных градиентов.
7	Вычисление многомерных интегралов с использованием многошаговой схемы (метод прямоугольников).
8	Вычисление многомерных интегралов с использованием многошаговой схемы (метод трапеций).
9	Вычисление многомерных интегралов с использованием многошаговой схемы (метод Симпсона).
10	Вычисление многомерных интегралов методом Монте-Карло.
11	Алгоритм глобального поиска (Стронгина) для одномерных задач оптимизации. Распараллеливание по характеристикам.
12	Многошаговая схема решения двумерных задач глобальной оптимизации. Распараллеливание путем разделения области поиска.
13	Многошаговая схема решения двумерных задач глобальной оптимизации. Распараллеливание по характеристикам.
14	Быстрая сортировка с простым слиянием.
15	Быстрая сортировка с четно-нечетным слиянием Бэтчера.
16	Сортировка Шелла с простым слиянием.
17	Сортировка Шелла с четно-нечетным слиянием Бэтчера.
18	Поразрядная сортировка для целых чисел с простым слиянием.
19	Поразрядная сортировка для целых чисел с четно-нечетным слиянием Бэтчера.
20	Поразрядная сортировка для вещественных чисел (тип double) с простым слиянием.
21	Поразрядная сортировка для вещественных чисел (тип double) с четно-нечетным слиянием Бэтчера.
22	Поиск кратчайших путей из одной вершины (алгоритм Дейкстры). С CRS формой хранения графа.
23	Поиск кратчайших путей из одной вершины (алгоритм Беллмана-Форда). С CRS формой хранения графа.
24	Построение выпуклой оболочки – проход Грэхема.
25	Построение выпуклой оболочки – проход Джарвиса.
26	Линейная фильтрация изображений (горизонтальное разбиение). Ядро Гаусса 3x3.
27	Линейная фильтрация изображений (вертикальное разбиение). Ядро Гаусса 3x3.
28	Линейная фильтрация изображений (блочное разбиение). Ядро Гаусса 3x3.
29	Выделение ребер на изображении с использованием оператора Собеля.
30	Повышение контраста полутонового изображения посредством линейной растяжки гистограммы
31	Маркировка компонент на бинарном изображении (черные области соответствуют объектам, белые – фону).
32	Построение выпуклой оболочки для компонент бинарного изображения.

Комментарии для 2-ой и 3-й задач:

• МЕТОДЫ ПЕРЕДАЧИ СООБЩЕНИЙ. Нужно реализовать указанные методы, используя только функции Send и Recv. Реализованная функция должна иметь тот же прототип, что и соответствующая функция MPI. Тестовая программа должна позволять выбрать номер процесса root и выполнять пересылку (рассылку, сбор) массива как минимум следующих типов: MPI_INT, MPI_FLOAT, MPI_DOUBLE. Во всех операциях передача должна выполняться с использованием «дерева» процессов.

  Комментарии относятся к:

  Варинты для второй задачи	Варинты для третьей задачи
  1 - 5	x

• ТОПОЛОГИИ СЕТЕЙ ПЕРЕДАЧИ ДАННЫХ. Нужно реализовать указанную в задаче виртуальную топологию, используя возможности MPI по работе с коммуникаторами и топологиями и обеспечить возможность передачи данных от любого выбранного процесса любому другому процессу. (Не используя MPI_Cart_Create и MPI_Graph_Create)

  Комментарии относятся к:

  Варинты для второй задачи	Варинты для третьей задачи
  6 - 10	x

• МАТРИЧНЫЕ ВЫЧИСЛЕНИЯ. В горизонтальной схеме матрица делится между процессами по строкам. В вертикальной - по столбцам, вектор в этом случае также делится между процессами.

  Комментарии относятся к:

  Варинты для второй задачи	Варинты для третьей задачи
  11 - 14	1 - 5

• МАШИННАЯ ГРАФИКА И ОБРАБОТКА ИЗОБРАЖЕНИЙ. Считается, что изображение задано в цветном виде или оттенках серого, входные данные - одномерный массив. Загружать реальное изображение не требуется, но и не возбраняется.

  Комментарии относятся к:

  Варинты для второй задачи	Варинты для третьей задачи
  26 - 27	24 - 32

• РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

  Комментарии относятся к:

  Варинты для второй задачи	Варинты для третьей задачи
  15 - 20	6

• АЛГОРИТМЫ СОРТИРОВКИ

  Комментарии относятся к:

  Варинты для второй задачи	Варинты для третьей задачи
  21	14 - 21

• АЛГОРИТМЫ НА ГРАФАХ

  Комментарии относятся к:

  Варинты для второй задачи	Варинты для третьей задачи
  x	22 - 23