Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 27 стр.

следующих уравнений: sк1=s1z1; s1=s2z2∨s1z2; s2=s0z1 и соответствующее разбиение при-
ведено на рис.3.6.
            У равнение            У равнение              У равнение
              д л я sк1              дл я s1                 дл я s2
                 Рис. 3.6. Разбиение по функциям вычисления уравнений
     Далее, на следующем уровне иерархии, возможно разбиение вычислений правых
частей уравнений. Например, уравнение для s1 можно разбить на функции: конъюнкции,
дизъюнкции и присвоения (рис. 3.7).
                                            s1=

                                            ∨

                                    z2&s3         z2&s1
                           Рис. 3.7. Разбиение правой части для s1
      В конечном итоге полное функциональное разбиение будет представлять собой де-
рево (рис 3.8), корнем которого будет определение вхождения какой-либо цепочки во
входную последовательность, а далее соответственно по ярусам – нахождение конкрет-
ной цепочки, затем вычисление уравнений НДСКУ для этой цепочки и затем вычисление
их правых частей. На рисунке не приведено разбиение по функциям при вычислении
уравнения sf, т.к. при практической реализации алгоритма достаточно проверять входной
сигнал на равенство "bottom", и в случае обнаружения конца последовательности завер-
шать алгоритм поиска. Из рассмотрения этого дерева хорошо видно, что на нижнем уров-
не выполняется операция конъюнкции, затем дизъюнкции и затем присвоения. Таким об-
разом, в результате разбиения алгоритма по функциям получаются следующие элемен-
тарные задачи:
   1) конъюнкция si&zj, где si- одно из событий НДСКУ, а zj - входной сигнал;

  2) дизъюнкция полученных конъюнкций;

  3) присвоение.

  Так как эти операции являются элементарными (неделимыми), то дальнейшее функ-
циональное разбиение невозможно и декомпозицию алгоритма как по данным так и по
функциям можно считать завершенной.
  Анализируя полученные ЭЗ можно утверждать что:
  1) число Э3 достаточно велико, и это позволит в дальнейшем оптимально распреде-
   лять ЭЗ между процессорами;

  2) возможны слишком большие затраты памяти с ростом числа одновременно обраба-
   тываемых последовательностей (первый уровень декомпозиции данных), и это может
   привести к ограничению числа разбиений;

  3) размеры ЭЗ практически равны, и это позволит в дальнейшем равномерно загрузить
   процессоры;


                                            27