распараллеливание
синтез параллельного алгоритма
Распараллеливание - это нахождение параллельного алгоритма решения задачи и реализация этого алгоритма на параллельной вычислительной системе. Распараллеливание не обязательно предполагает получение параллельного алгоритма из последовательного алгоритма.
параллельная вычислительная математика
Разработка и обоснование параллельных алгоритмов является предметом новой и бурно развивающейся отрасли вычислительной математики — параллельной вычислительной математики. Результатами параллельной вычислительной математики являются как эффективные параллельные алгоритмы для решения конкретных задач, так и целые классы принципиально новых алгоритмов, ярким представителем которых являются нейросетевые алгоритмы. Одним из важных результатов параллельной вычислительной математики является установление того факта, что многие традиционные последовательные алгоритмы не имеют эффективных параллельных аналогов.
зернистость алгоритма
степень грануляции алгоритма
Наряду с понятием зернистости параллельной программы или гранулированности параллельной программы, как меры степени ее параллелизма. говорят о зернистости алгоритма или степени грануляции алгоритма, как мере степени его параллелизма.
мелкозернистый алгоритм
Мелкозернистый алгоритм позволяет выделить в нем параллельные ветви только малого объема.
крупнозернистый алгоритм
крупноблочный алгоритм
крупнозернистый алгоритм адекватен MIMD-системам и состоит из независимых или слабо связанных ветвей значительного объема, которые могут обрабатываться параллельно. Крупнозернистый алгоритм часто называют крупноблочным алгоритмом.
сильно связанная задача
Задача, для которой известны только мелкозернистые алгоритмы ее решения, называется сильно связанной задачей.
слабо связанная задача
Задача, для которой известен хотя бы один крупно крупнозернистый алгоритм ее решения, называется слабо связанной задачей.
параллелизм данных
Параллелизмом данных обладают задачи, которые включают в себя неоднократное выполнение одного и того же алгоритма с различными исходными данными. Такие вычисления могут, очевидно, производиться параллельно. Если задача обладает параллелизмом данных, то соответствующую параллельную программу (SPMD-программу) целесообразно организовать в виде совокупности одинаковых программ, каждая из которых выполняется на своем подчиненном процессоре, и из основной программы, которая выполняется на мастер-процессоре. Такая программа является, как правило, крупнозернистой.
декомпозиция по данным
Распараллеливание на основе параллелизма по данным называется декомпозицией по данным.
статическая декомпозиция по данным
Декомпозиция по данным может быть статической и динамической. При статической декомпозиции по данным каждому процессу заранее назначается его доля данных.
динамическая декомпозиция по данным
Декомпозиция по данным может быть статической и динамической. При динамической декомпозиции по данным мастер-процесс распределяет блоки данных по процессам в ходе решения задачи по мере появления данных и освобождения соответствующих процессоров.
функциональный параллелизм
Функциональный параллелизм – это параллелизм групп операций, объединенных по функциональному признаку.
функциональная декомпозиция
Распараллеливание на основе функционального параллелизма называется функциональной декомпозицией. Тривиальным примером функциональной декомпозиции является декомпозиция задачи на три следующих подзадачи: ввод исходных данных, обработка, вывод результатов, визуализация результатов. Параллелизм при этом достигается параллельным выполнением трех указанных подзадач и созданием «конвейера» (последовательного или последовательно параллельного) между ними. Менее очевидным примером функциональной декомпозиции является декомпозиция задачи математического моделирования самолета на подзадачи моделирования атмосферы, фюзеляжа самолета, его левого крыла, правого крыла и т.д.
геометрический параллелизм
Геометрическим параллелизмом обладают, например, многие физические задачи, которые описываются дифференциальными уравнениями в частных производных (задачи механики сплошной среды, теории поля и т.п.). Такие задачи обычно решаются конечно-разностными методами или методами конечных элементов. Дискретные аналоги этих задач имеют локально-ограниченные взаимодействия между узлами сетки, покрывающей область решения, что позволяет разбить область решения задачи на подобласти и вычисления в каждой из подобластей поручить отдельному процессору. Отличие геометрического параллелизма от параллелизма по данным состоит в том, что в первом случае подзадачи обработки каждой из подобластей взаимосвязаны (требуется обмен данными между этими подзадачами).
декомпозиция области решения
Распараллеливание на основе геометрического параллелизма называется декомпозиция области решения. Декомпозиция области решения – один из основных способов получения крупнозернистых алгоритмов и программ.
локальность алгоритма
Декомпозиция области решения эффективна при условии, что вычислительная сложность каждой из подзадач примерно одинакова (для однородной вычислительной системы). Кроме того, для эффективности декомпозиции области решения каждая из подзадач должна использовать лишь небольшой объем данных, обрабатываемых другими подзадачами. Такое свойство называется локальностью алгоритма.
статическая декомпозиция области решения
При статической декомпозиции области решения границы подобластей, на которые разбивается область решения задачи, в ходе вычислений не меняются. Статическая декомпозиция области решения может быть эффективной, если вычислительные сложности подзадачи обработки каждой из подобластей не меняются в ходе вычислений.
динамическая декомпозиция области решения
При динамической декомпозиции области решения границы подобластей, на которые разбивается область решения задачи, в ходе вычислений меняются. Динамическая декомпозиция области решения используется, когда вычислительные сложности подзадачи обработки каждой из подобластей меняются в ходе вычислений.
алгоритмический параллелизм
Алгоритмическим параллелизмом называется параллелизм, который выявляется путем выделения в данном алгоритме тех фрагментов, которые могут выполняться параллельно . Алгоритмический параллелизм редко порождает крупнозернистые параллельные алгоритмы и программы.
алгоритмическая декомпозиция
Синтез параллельных алгоритмов (распараллеливание) на основе алгоритмического параллелизма называется алгоритмической декомпозицией. При использовании алгоритмической декомпозиции следует стремиться к разбиению задачи на крупные и редко взаимодействующие ветви. Должно быть обеспечено, по возможности, однородное распределение массивов по ветвям параллельного алгоритма.
конвейерный параллелизм
Типичный пример конвейерного параллелизма представляет собой параллелизм систем обработки видеоинформации, в которых множество изображений должны проходить несколько этапов обработки.
конвейерная декомпозиция
Типичный пример конвейерного параллелизма представляет собой параллелизм систем обработки видеоинформации. В таких системах множество изображений должны проходить несколько этапов обработки. В данном случае естественно использовать конвейерную декомпозицию задачи, когда каждый этап обработки выполняется на отдельном процессоре.
«беспорядочный» параллелизм;
В некоторых классах алгоритмов возможное количество параллельных ветвей и их вычислительная сложность априори неизвестны, а определяются особенностями конкретной задачи. Примерами алгоритмов, обладающих «беспорядочным» параллелизмом, является алгоритм «ветвей и границ»», рекурсивные алгоритмы типа «разделяй и властвуй» и пр.
реструктуризация данных
Реструктуризация данных - это широко известным частным случаем алгоритмической декомпозиции. Реструктуризация данных может быть использована при выполнении любой ассоциативной операции, например, при вычислении произведения n вещественных чисел.