Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 218 стр.

     1) конъюнкция Si&zj, где Si- одно из событий НД СКУ, а zj - входной
сигнал;
     2) дизъюнкция полученных конъюнкций;
     3) присвоение.
     Так как эти операции являются элементарными (неделимыми), то
дальнейшее функциональное разбиение невозможно и декомпозицию
алгоритма, как по данным, так и по функциям можно считать завершенной.
     Анализируя полученные ЭЗ можно утверждать что:
     1) число Э3 достаточно велико, и это позволит в дальнейшем
оптимально распределять ЭЗ между процессорами;
     2) с ростом числа одновременно обрабатываемых последовательностей
возможны слишком большие затраты памяти (первый уровень декомпозиции
данных), и это может привести к ограничению числа разбиений;
     3) размеры ЭЗ практически равны, и это позволит в дальнейшем
равномерно загрузить процессоры;
     4) при увеличении размерности входных данных возрастает число ЭЗ, а
размер Э3 остается неизменным, и это обеспечивает масштабируемость
алгоритма поиска.
                          Найдена любая цепочка
                               Sк1Sк2Sк3

                      Sк1=        Sк2=        Sк3=

                     S1&z1        S4&z2      S5&z1

                         S1=       S4=        S5=

                  S2&z2    S1&z2 S0&z3 S0&z3      S6&z3

                   S2=                               S6=

                  S0&z1                           S5&z2

                Рис.7.6. Полное функциональное разбиение
     На втором шаге проектирования параллельного алгоритма определим
необходимые коммуникации между ЭЗ, учитывая что:
     1) входные последовательности и результаты поиска в каждой из них
будут храниться в одном месте (оперативная память, файл на диске, и т.п.);



                                                                       218