Параллельные вычисления. Баканов В.М. - 25 стр.

                                      - 25 -


языков Fortran или C/C++, [3]). В зависимости от размеров гранул говорят о
мелкозернистом и крупнозернистом параллелизме (fine-grained parallelism и
coarse-grained parallelism). На размер гранулы влияет и удобство программи-
рования – в виде гранулы часто оформляют некий логически законченный
фрагмент программы. Целесообразно стремиться к равномерной загрузке
процессоров (как по количеству вычислительных операций, так и по загрузке
оперативной памяти)
  Разработка параллельных программ является непростой задачей в связи с
трудностью выявления параллелизма (обычно скрытого) в программе (т.е.
выявления частей алгоритма, могущих выполняться независимо друг от дру-
га). Например, для задачи вычислений фрагмента программы (ZnN –
вычисленные значения, OpN – операнды, FunN – вычислительные
процедуры, DN – арифметико-логические выражения):

  Zn1 ← Fun1(Op1,Op2) D1 Fun2(Op3) D2 Fun3(Op3); // operator 1          (2)
  Zn2 ← Fun4(Op4,Zn1) D3 Fun5(Op3); // operator 2

   выявить параллелизм 'вручную' неcложно. Даже на первый взгляд видно,
что вычисление оператора Zn2 невозможно без предварительного вычисле-
ния Zn1 (при этом говорят, что оператор ‘Zn1 зависит от Zn2’, т.е. существует
зависимость по данным; подробнее см. подраздел 3.2).
    В простейшем случае возможно распределить по процессам вычисления
Fun1 ÷ Fun3 в соответствие со схемой рис.3б и далее ‘собрать’ вычисленные
значения для определения Zn1, в дальнейшем подобным образом поступить
с вычислением Zn2 (что вычисление Fun5 можно совместить с вычислением
Fun1 ÷ Fun3); в этом гранулами параллелизма являются вычисления
Fun1 ÷ Fun5. Заметим, что автоматизация (столь легко проделанная ‘вручную’)
выявления параллелизма в алгоритмах непроста и в полном объеме вряд ли
может быть решена в ближайшее время. В то же время за десятилетия экс-
плуатации вычислительной техники разработано такое количество (тщатель-
но отлаженных и оптимизированных) последовательных алгоритмов, что не
может быть и речи об их ручном распараллеливании.
   Построим простейшую математическую модель для оценки возможного
повышения производительности при распараллеливании вычислений c уче-
том времени обмена данными. Пусть t O - характерное время обмена (опера-
ций пересылки данных между процессами), t З - время выполнения последо-
вательности команд, составляющих гранулу, n – число гранул. Примем (уп-
рощенно), что при раcпараллеливании каждая гранула выполняется на от-
дельном процессоре, время вычисления последовательности команд каждой
гранулы одинаково, каждый процесс требует при функционировании не бо-
лее двух обменов (как показано на рис.3б). Тогда последовательный алго-
ритм выполнится (в среднем) за время

  T посл = t з × n ,