Принципы разработки параллельных методов

“Young Scientist”
. 
#3 (137)
. 
January 2017
31
Computer Science
так и параллельные), однако если дело касается ка-
кой-либо новой задачи, то этот процесс занимает суще-
ственную часть выполняемых работ [1]. Данная процедура 
является фундаментом для разработки параллельного ме-
тода, но, тем не менее, к самой разработке имеет лишь 
косвенное отношением. Именно поэтому данный вопрос 
в данной работе далее рассматриваться не будет.
В общем, разработку параллельного алгоритма можно 
разделить на следующие этапы [1]:
1) Дифференциация вычислений на самостоятельные 
компоненты;
2) Определение связей между компонентами вычис-
лений;
3) Объединение компонентов в наборы или их детали-
зация;
4) Распределение наборов компонентов между про-
цессорами.
Для дифференциации вычислений на самостоятельные 
компоненты необходимо провести анализ вычислительной 
схемы решения задачи. Основным требованием при вы-
полнение данного этапа является то, что компоненты об-
ладают одинаковой вычислительной нагрузкой, а также 
имеют минимальные зависимости друг перед другом. Если 
компоненты будут независимы друг от друга в плане ин-
формации, то их можно будет выполнять одновременно 
в несколько потоков (поток — это некоторая последова-
тельность команд, логически выделенная и выполняемая 
на некотором вычислительном элементе). Одинаковая же 
вычислительная нагрузка позволяет равномерно и пра-
вильно распределить процесс решения.
При дифференциации может быть выбран один из двух 
возможных подходов: на основе параллелизма по данным 
или на основе функционального параллелизма. При па-
раллелизме по данным различные компоненты работают 
с различными наборами данных. Эти набору могут выде-
ляться либо согласно ленточной схемы разделения, либо 
согласно блочной схемы разделения данных. В свою оче-
редь, при функциональном параллелизме декомпозиция 
производится согласно выполняемым функциям метода, 
причем компоненты могут работать над одними и теми же 
данными.
Также необходимо отметить и различные подходы 
к проведению самой дифференциации. Можно либо про-
вести разбиение на максимально возможное количество 
компонентов, либо на довольно большие компоненты, 
когда становится довольно понятной сама схема вычис-
ления. Преимуществом первого подхода является эффек-
тивность вычислений, а преимуществом второго — ясная 
схема работы. Возможен также и третий вариант, при 
котором компоненты являются довольно простыми, но 
схема вычисления все еще является понятной.
Вопрос понятности вычислительной схемы решения 
является крайне важным, так как именно на основе нее 
производится второй этап разработки параллельного ал-
горитма — определение связей между компонентами 
вычислений. Данный этап, фактически, выполняется 
одновременно с первым, но, тем не менее, выделяется ло-
гически в отдельный. Происходит это потому, что диффе-
ренциация должна производится на основе анализа того, 
какие компоненты и как обмениваются информацией. То 
есть производится дифференциация, анализируются ин-
формационные зависимости, вновь проводится диффе-
ренциация и так далее.
При проведении процедуры анализа информационных 
зависимостей очень важно понять, какой является схема 
информационного взаимодействия (локальной, когда 
между собой зависимо небольшое число компонентов, 
или глобальной, когда все или почти все компоненты так 
или иначе зависимы друг от друга), каковы способы вза-
имодействия (структурные, когда взаимодействие по-
нятно, типично и однородно, или произвольные, когда от-
сутствует какая-либо структура взаимодействия), а также 
какова схема информационной зависимости (статическая, 
когда все понятно на этапе разработки, или динамическая, 
когда зависимость определяется при выполнении вычис-
лений). Все это помогает принять правильное решение 
о дифференциации вычислении на самостоятельные ком-
поненты.
Третий этап, на котором производится объединение 
компонентов в наборы или их детализация, проводится 
для адаптации параллельного метода к числу вычисли-
тельных элементов. Объединение компонентов в наборы 
производится при недостатке вычислительных мощно-
стей, причем полученные наборы, как и сами компоненты, 
должны обладать одинаковой вычислительной нагрузкой, 
а также иметь минимальные зависимости друг перед 
другом. Детализация же компонентов производится при 
избыточном числе вычислительных элементов.
Четвертый этап, а именно распределение наборов 
компонентов между процессорами, является необяза-
тельным и выполняется для управления нагрузкой в вы-
числительных системах с распределенной памятью при 
условии недостатка или избыточности вычислительных 
элементов. При успешном выполнении работ на данном 
этапе можно максимально эффективно использовать вы-
числительные элементы.
Разработанный параллельный алгоритм после под-
лежит программной реализации. Программный код де-
лится по вычислительным элементам компьютерной си-
стемы в соответствии с выбранной схемой. После отладки 
остается лишь запустить программу на исполнение и про-
вести вычисления. Помимо самих вычислительных эле-
ментов система должна поддерживать передачу инфор-
мацию между ними в силу информационной зависимости.
Важным моментом является то, что применение парал-
лельных методов возможно и в системах с общей памятью, 
где задача передачи информации будет заменена на задачу 
доступа к общим данным, которые рассматривается пото-
ками как единый общий ресурс. Решается вопроса доступа 
к общим данным, например, с помощью механизма блоки-
ровок. Например, если один поток читает некоторый набор 
данных, то прочитать эти данные может любой поток, но 

«Молодой учёный»

жүктеу/скачать 9,13 Mb.

Достарыңызбен бөлісу: