Учебное пособие Казань 018 удк

4. ПОСТРОЕНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ: ИНЖЕНЕРНЫЙ 
ПОДХОД 
4.1. Постановка задачи 
Известно, что перенос последовательной программы на параллельную 
ЭВМ без ее существенной переработки, как правило, не приводит к ускорению 
вычислений. Усилия, затрачиваемые на эту переработку, в значительной 
степени зависят от типа решаемой задачи. Для того чтобы построить 
эффективный параллельный алгоритм, строго говоря, следует провести анализ 
графа алгоритма и решить задачу отображения так, как это сформулировано в 
разделе 3.2. Решение такой задачи оптимизации на графах требует 
значительных усилий и высокой квалификации. 
На практике разработку параллельного алгоритма обычно осуществляет 
специалист, работающий в некоторой предметной области, не всегда 
владеющий методами дискретной оптимизации. С другой стороны, строгое 
решение этой задачи требуется далеко не всегда. Обычно ограничения, 
связанные с типовым набором доступных архитектур, все равно вынуждают 
исследователя находить некоторое приемлемое для него решение, 
руководствуясь не вполне строгими, но проверенными на практике приемами и 
правилами. 
В частности, если в конкретной задаче элементы некоторого массива 
исходных данных могут обрабатываться независимо друг от друга, то эти 
правила обычно очевидны и позволяют строить весьма эффективные 
параллельные алгоритмы. В этом случае задача переработки может свестись к 

---

40 
разбиению массива исходных данных на фрагменты, обработка которых 
ведется независимо на различных процессорах. Ясно, что при этом должна 
обеспечиваться равномерная загрузка процессоров, с учетом их, возможно, 
различной производительности. 
Эффективность программы в этом случае зависит от соотношения 
временных затрат на проведение вычислений на фрагментах исходных данных 
и пересылку данных (накладные расходы) [2,3]. По мере увеличения числа (а 
значит уменьшения размеров) фрагментов данных, объем вычислений на 
каждом фрагменте уменьшается. При этом накладные расходы могут 
оставаться почти прежними, например, вследствие большой латентности 
(связанной с потерями на передачу сообщения нулевой длины) 
коммуникационной среды. 
Иногда 
используется 
следующий 
простой 
способ 
построения 
эффективной параллельной программы, совмещенный с этапом ее отладки. 
Размеры фрагментов массива исходных данных уменьшают (соответственно 
увеличивают число параллельно работающих процессоров) до тех пор, пока 
имеет место почти линейное ускорение. Если же при очередном увеличении 
числа процессоров линейного ускорения не происходит, это означает, что 
накладные расходы стали заметными и дальнейшее распараллеливание по 
данным приведет к недостаточной загрузке процессоров. Этот подход 
обсуждался в работе [7]. 
Совокупность методов и приемов распараллеливания, не требующих 
строгого решения задачи отображения графа алгоритма на граф 
вычислительной системы, будем называть инженерным подходом. В настоящем