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

                                    1.4 Выводы
     Следует отметить, что хотя разработка алгоритмов решения задач поиска велась для
однопроцессорной системы ( последовательная реализация алгоритма ), полученные ал-
горитмы внутри являются параллельными.
    Но если задача поиска имеет большую размерность ( длинные цепочки и много фай-
лов большой длины, внутри которых их надо искать ), и есть возможность реализации ал-
горитма на мультипроцессорной системе, то имеет смысл с точки зрения повышения бы-
стродействия произвести разработку параллельного алгоритма.
               2 Методика проектирования параллельных алгоритмов
    Одна из важных тенденций развития современной вычислительной техники состоит в
расширенном внедрении мультипроцессорных архитектур. Микропроцессоры позволили
получить процессорное время по номинальной цене, а их малые габариты делают вполне
обоснованной постановку вопроса об их комплексировании в единой системе в количест-
ве десятков, сотен и более. Одним из ключевых факторов способствующих использова-
нию таких систем будет наличие параллельных алгоритмов.
    Один из возможных подходов к разработке параллельного алгоритма для решения
какой-либо задачи, в том числе задач идентификации базируется на методике, приведен-
ной в [5] и состоит из следующих этапов проектирования: - декомпозиция ( разбиение )
исходной задачи на элементарные задачи; - определение всех необходимых взаимодейст-
вий ( коммуникаций ) между элементарными задачами; - объединение элементарных за-
дач ( агломерация ) в соответствие с определенной стратегией, учитывающей в том числе
число процессоров в системе; - распределение полученных при агломерации задач на за-
данное число процессоров; - оценка полученного алгоритма (или алгоритмов, если их по-
лучено несколько) на масштабируемость (при увеличении объема исходных данных и/или
изменении числа процессоров в мультипроцессорной системе).
                2.1 Декомпозиция задачи на элементарные подзадачи
      На первом этапе проектирования данные, используемые в задаче и операции над
ними, разбиваются на элементарные задачи ( не допускающие дальнейшего разбиения )
без учета числа процессоров в мультипроцессорной системе. То есть внимание фокусиру-
ется на достижении максимального параллелизма как при разбиении данных, исходных
и/или промежуточных ( "декомпозиция данных" ), так и при разбиении выполняемых
операций в задаче( "функциональная декомпозиция" ).
      При декомпозиции данных входные и промежуточные данные, используемые в за-
даче разбиваются на элементарные части приблизительно одинакового размера, а затем
по этим частям разбиваются операции, выполняемые над ними. Эти данные и операции
над ними назовем элементарными задачами (ЭЗ). Нужно учитывать при этом, что если
какие-то операции в ЭЗ требуют данных из нескольких полученных при разбиении ЭЗ, то
в дальнейшем это потребует организации взаимосвязей (коммуникаций) между ЭЗ на что
потребуется время мультипроцессорной системы (это время может занимать существен-
ный процент от общего времени выполнения алгоритма). Идеальным можно считать слу-
чай когда коммуникации между ЭЗ отсутствуют. Существует хорошее правило при де-
композиции данных - начинать разбиение с больших структур данных или с тех, которые
используются наиболее часто в задаче.
      При функциональной декомпозиции разбиение операций, выполняемых над данны-
ми, рассматривается раньше чем разбиение самих данных. Задача также разбивается на
элементарные задачи - функции в идеальном случае не зависящие друг от друга.


                                         11