36. Оценка коммуникационной трудоемкости параллельных алгоритмов. Характеристики топологии сети передачи данных
37. Общая характеристика механизмов передачи данных. Алгоритмы маршрутизации. Методы передачи данных!
38. Анализ трудоемкости основных операций передачи данных.
Передача данных между двумя процессорами сети.
Передача данных от одного процессора всем остальным процессорам сети
Передача данных от всех процессоров всем процессорам
Обобщенная передача данных от одного процессора всем остальным процессорам сети
Обобщенная передача данных от всех процессоров всем процессорам сети
Циклический сдвиг
39. Методы логического представления топологии коммуникационной среды. Представление кольцевой топологии в виде гиперкуба. Отображение топологии решетки на гиперкуб
40. Оценка трудоемкости операций передачи данных для кластерных систем
41. Параллельные численные алгоритмы для решения типовых задач вычислительной математики. Вычисление частных сумм последовательности числовых значений
Последовательный алгоритм суммирования
Каскадная схема суммирования
Модифицированная каскадная схема
Вычисление всех частных сумм
42. Умножение матрицы на вектор
Достижение максимально возможного быстродействия
Использование параллелизма среднего уровня
Организация параллельных вычислений при p = n
Использование ограниченного набора процессоров
43. Матричное умножение
Макрооперационный анализ алгоритмов решения задач
Организация параллелизма на основе разделения данных
44. Сортировка. Параллельное обобщение базовой операции сортировки
45. Обработка графов. Нахождение минимально охватывающего дерева. Поиск кратчайших путей
46. Модели функционирования параллельных программ. Концепция процесса. Понятие ресурса!
47. Организация программ как системы процессов. Взаимодействие и взаимоисключение процессов
48. Учебно-практическая задача: Решение дифференциальных уравнений в частных производных. Последовательные методы решения задачи Дирихле
49. Организация параллельных вычислений для систем с общей памятью
Использование OpenMP для организации параллелизма
Проблема синхронизации параллельных вычислений
Возможность неоднозначности вычислений в параллельных программах
Проблема взаимоблокировки
Исключение неоднозначности вычислений
Волновые схемы параллельных вычислений
Балансировка вычислительной нагрузки процессоров
50. Организация параллельных вычислений для систем с распределенной памятью. Разделение данных
Обмен информацией между процессорами
Коллективные операции обмена информацией
Организация волны вычислений
Блочная схема разделения данных
Оценка трудоемкости операций передачи данных
Ответы
..Закон Амдала Перед началом проекта по параллелизации разработчику может быть интересно оценить ускорение, которое он теоретически сможет достичь. Если процент последовательного кода, который можно исполнять параллельно, известен (или оценен), то он может использовать закон Амдала для расчёта верхней границы ускорения приложения без необходимости предварительного написания какого-либо параллельного кода. В литературе присутствуют несколько вариантов формулы закона Амдала. В каждой из них используется процент (предполагаемого) времени параллельного выполнения (pctPar), последовательного выполнения (1 – pctPar), и количество потоков/ядер (p). Ниже приведена простая формулировка закона Амдала для расчёта ускорения параллельного приложения на pядрах:
Данная формула представляет собой время последовательного выполнения, нормализованное до 1 и деленное на расчётное время параллельного выполнения с использованием процента нормализованного времени последовательного выполнения. Время параллельного выполнения рассчитывается как процент последовательного выполнения (1 – pctPar) и процент параллельного выполнения, деленные на количество используемых ядер (pctPar/p). Например, если 95% времени последовательного выполнения может выполняться параллельно на 8 ядрах, то оценочное ускорение, согласно закону Амдала, составит около 6x (1 / (0.05 + 0.95/8) = 5.925). В дополнение к отношению меньше или равно (≤) в формуле, формулировка закона Амдала подразумевает, что вычисления, которые можно выполнять параллельно, будут делиться на бесконечное количество ядер. Такое предположение удаляет второй член знаменателя, что означает, что наивысшее возможное ускорение просто равно инверсии остаточного последовательного выполнения. Закон Амдала часто критикуют за игнорирование издержек при коммуникацию, синхронизацию и других действий по управлению потоками, а также за предположение о бесконечном количестве процессоров. В дополнение к игнорированию издержек, присущих параллельным алгоритмам, одним из самых сильных замечаний является то, что при увеличении количества ядер количество обрабатываемых данных также обычно увеличивается. Закон Амдала подразумевает использование фиксированного набора данных при любом количестве ядер, и что процент времени последовательного выполнения останется одним и тем же.
Общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных.Была предложена в 70-е годы Майклом Флинном (Michael Flynn). Все разнообразие архитектур ЭВМ в этойтаксономии Флинна сводится к четырем классам:
· ОКОД — Вычислительная система с одиночным потоком команд и одиночным потоком данных (SISD, Single Instruction stream over a Single Data stream).
· ОКМД — Вычислительная система с одиночным потоком команд и множественным потоком данных (SIMD, Single Instruction, Multiple Data).
· МКОД — Вычислительная система со множественным потоком команд и одиночным потоком данных (MISD, Multiple Instruction Single Data).
· МКМД — Вычислительная система со множественным потоком команд и множественным потоком данных (MIMD, Multiple Instruction Multiple Data).
Типичными представителями SIMD являются векторные архитектуры. К классу MISD ряд исследователейотносит конвейерные ЭВМ, однако это не нашло окончательного признания, поэтому можно считать, чтореальных систем — представителей данного класса не существует. Класс MIMD включает в себямногопроцессорные системы, где процессоры обрабатывают множественные потоки данных.
Отношение конкретных машин к конкретному классу сильно зависит от точки зрения исследователя. Так,конвейерные машины могут быть отнесены и к классу SISD (конвейер — единый процессор), и к классу SIMD(векторный поток данных с конвейерным процессором) и к классу MISD (множество процессоров конвейераобрабатывают один поток данных последовательно), и к классу MIMD — как выполнение последовательностиразличных команд (операций ступеней конвейера) на множественным скалярным потоком данных (вектором).
