Теормин

1.Внутренний параллелизм, степень параллелизма(определение).Алгоритм обладает внутренним параллелизмом, если в нём присутствуютдействия, для которых допустимо одновременно выполнение.Степень параллелизма алгоритма - это число операций, выполнять которыеможно в любом порядке.2. Оценка времени передачи данных между двумяпроцессорами, непосредственно соединённых каналомпередачи данных.Скорость передачи n байт T (n) = n * T Байта + T Латентности , где T Байта - это времяпередачи одного байта, а T Латентности - это время, которое требуется, чтобы передачаданных начала осуществляться.3. Сверхлинейное ускорение (определение), возможныепричины.Ускорение, чьё значение превышает количество процессоров называетсясверхлинейным, т.е. приSp > p .Может быть вызвано:● Неудачным выбором последовательного алгоритма● особенностями вычислительных систем (например: при работена одном процессоре все обрабатываемые данные непомещаются в кэш)4.Ускорение, эффективность (определение).Ускорение параллельного алгоритма - это отношение времени выполненияпоследовательного алгоритма​TpT 1 ​ ко времени выполнения параллельного алгоритмаSp =на заданном числе процессоров p.​T1Tp​.Эффективность параллельного алгоритма - это отношения ускорения к числупроцессоров, на которых оно достигнуто5.Ep =Spp .​Закон Амдала.Пусть α - доля вычислений от общего объёма, которые могут быть выполненытолько последовательно.

​Тогда ускорение, которое может быть получено навычислительной системе из p процессоров, по сравнению с однопроцессорным решениемне будет превышать величины6.Sp =α+11−αpМетоды передачи данных (перечислить).●Синхронный метод (Send, Recv)●7.Асинхронный метод (ASend, ARecv, ASync): бывают асинхронныеметоды с буферизацией и без буферизации (это важно)Барьер (определение).Барьер – это функция, вызываемая всеми процессами, участвующими в актевзаимной синхронизации.

Ни один из вызвавших эту функцию процессов не завершитее выполнение до тех пор, пока пока все процессы не начнут выполнение этойфункции.8.Семафор (определение).Семафор - это целочисленная неотрицательная переменная, над которойможно выполнять только две ​атомарные​ операции P и V.● V - неблокирующая операция, которая увеличивает значение семафора на 1● Операция P:1) Если значение семафора было положительно, уменьшает значениесемафора на 12) Если значение семафора было равно нулю, то переходит в ожидание дотех пор, пока какой-нибудь другой процесс не вызовет операцию V ипосле этого переходит к шагу 19.

Виды балансировки загрузки процессоров (определение ихарактерные представители).Балансировка предполагает равномерную нагрузку вычислительных узлов. Принимаетрешение, на каком вычислительном узле следует выполнять вычисления, связанные сновым заданием.1. Статическая. Примеры: геометрический параллелизм, конвейерныйпараллелизм, метод сдваивания2. Динамическая. Примеры: диффузная балансировка, коллективное решение10.

Сети сортировки (определение).Сети сортировки - это вид алгоритмов сортировки, в которых порядоквыполнения операций сравнения и их количество не зависит от значения элементовсортируемого массива.11. Критерии декомпозиции расчетных сеток (перечислить).1. Равномерность распределения графа по доменам2. Минимальность максимального числа рёбер, соединяющих вершины каждогоиз доменов с вершинами других доменов3. Минимальность числа смежных доменов4. Связность множества размещённых в каждом из доменов элементов графа.