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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

219
2) необходимо определить во входных последовательностях любую из
трех цепочек, и поэтому при обнаружении какой либо цепочки в любой
последовательности алгоритм завершается.
Определим необходимые коммуникации при разбиении алгоритма по
данным (рис.7.8). При разбиении входной последовательности на блоки
коммуникации будут аналогичными (при отсутствии итераций).
…
П о с л е д о в а т е л ь н о с т ь 1
П о с л е д о в а т е л ь н о с т ь 1 0
П о и с к
П о и с к
Р е з у л ь т а т 1
Р е з у л ь т а т 1 0
Рис.7.8. Коммуникации при разбиении алгоритма по данным
Определим необходимые коммуникации при разбиении алгоритма по
функциям. При разбиении алгоритма по функциям поиска каждой цепочки
коммуникации приведены на рис.7.9:
"есть/нет" 1 раз
"есть"1 раз
Последовательность
Ц1
Результат
Ц2
Ц3
Рис.7.9. Коммуникации при разбиении по функциям поиска цепочки
На рис.7.9, из-за недостатка места, показана только пересылка
сообщений («цепочка есть») от задачи, обнаруживающей первую цепочку к
двум другим. Аналогичные сообщения пересылает каждая задача каждой.
Теперь рассмотрим коммуникации при комбинировании разбиения по
данным и разбиения по функциям. Результат установления необходимых
коммуникаций представлен на рис.7.10. Для максимального же разбиения по
данным, и максимального разбиения по функциям необходимые
коммуникации, представлены на рис.7.11.
" е с т ь "
. . .
" е с т ь / н е т
"
П о с л е д - c т ь 1
Р е з у л ь т а т 1
Ц 1
Ц 2
Ц 3
" е с т ь / н е т
"
П о с л е д - c т ь 1 0
Р е з у л ь т а т 1 0
Ц 1
Ц 2
Ц 3
     2) необходимо определить во входных последовательностях любую из
трех цепочек, и поэтому при обнаружении какой либо цепочки в любой
последовательности алгоритм завершается.
     Определим необходимые коммуникации при разбиении алгоритма по
данным (рис.7.8). При разбиении входной последовательности на блоки
коммуникации будут аналогичными (при отсутствии итераций).

     П о с лед о в атель н о с ть 1           Поиск        Р ез уль тат 1
                                              …
    П о с лед о в атель н о с ть 10           Поиск       Р ез уль тат 10

        Рис.7.8. Коммуникации при разбиении алгоритма по данным
     Определим необходимые коммуникации при разбиении алгоритма по
функциям. При разбиении алгоритма по функциям поиска каждой цепочки
коммуникации приведены на рис.7.9:
                                       Ц1                      "есть"1 раз

     Последовательность                Ц2                         Результат

                                       Ц3                  "есть/нет" 1 раз

    Рис.7.9. Коммуникации при разбиении по функциям поиска цепочки
     На рис.7.9, из-за недостатка места, показана только пересылка
сообщений («цепочка есть») от задачи, обнаруживающей первую цепочку к
двум другим. Аналогичные сообщения пересылает каждая задача каждой.
     Теперь рассмотрим коммуникации при комбинировании разбиения по
данным и разбиения по функциям. Результат установления необходимых
коммуникаций представлен на рис.7.10. Для максимального же разбиения по
данным, и максимального разбиения по функциям необходимые
коммуникации, представлены на рис.7.11.
                                      Ц 1             " е с т ь /н е т
                                                              "
     П о с л е д -c т ь    1          Ц 2         Р е з у л ь т а т 1
                                      Ц 3
                                                          " е с т ь "
                                      . . .
                                      Ц 1                " е с т ь /н е т
                                                                 "
    П о с л е д -c т ь    1 0         Ц 2             Р е з у л ь т а т 1 0
                                      Ц 3



                                                                              219

Страницы