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

                                        - 17 -


скольку, во-первых, при этом сохраняется простота модели и, во-вторых, ло-
кальное (последовательное) время выполнения алгоритмов в процессорах не-
сложно установить и без этой модели.
  Моделировать схемы из функциональных элементов с помощью парал-
лельных машин с произвольным доступом (PRAM) позволяет теорема
Брента (*). В качестве функциональных элементов могут выступать как 4
основных (осуществляющих логические операции NOT, AND, OR, XOR – от-
рицание, логическое И, логическое ИЛИ и исключающее ИЛИ соответствен-
но), более сложные NAND и NOR (И-НЕ и ИЛИ-НЕ), так и любой сложности.
В дальнейшем предполагается, что задержка (propagation delay, т.е. время
срабатывания – время, через которое предусмотренные значения сигналов
появляются на выходе элемента после установления значений на входах)
                                                    одинакова     для    всех
                                                    функциональных       эле-
                                                    ментов.
                                                       Рассматривается схема
                                                    из функциональных эле-
                                                    ментов     (combinational
                                                    circuit), состоящая из
                                                    функциональных       эле-
                                                    ментов     (combinational
                                                    element),   соединенных
                                                    без образования циклов
                                                    (предполагаем,        что
                                                    функциональные       эле-
                                                    менты имеют любое ко-
                                                    личество входов, но ров-
                                                    но один выход - элемент
                                                    с несколькими выходами
                                                    можно заменить        не-
Рисунок 1 — Моделирование схемы размера 15, глубины
    5 с двумя процессорами с помощью параллельной сколькими элементами с
    машины с произвольным доступом (PRAM - машина)  единственным выходом),
                                                    см. рис.1. Число входов
                                                    определяет входную сте-
пень (fan-in) элемента, а число входов, к которым подключен выход элемента
- его выходной степенью (fan-out). Обычно предполагается, что входные
степени всех используемых элементов ограничены сверху, выходные же сте-
пени могут быть любыми. Под размером (size) схемы понимается количество
элементов в ней, наибольшее число элементов на путях от входов схемы к

*
    Кормен T., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. –М.: МЦНМО,
    2001, -960 с.