УПРАВЛЕНИЕ ПО ЗАПРОСУ

8.1 Ключевые (основные) вопросы (моменты)

— механизм управления по запросу;

— механизм передачи данных;

8.2 Текст лекции

8.2.1 Механизм управления по запросу

Контролировать число параллельных процессов можно, используя управление потоком запросов, когда при возникновении потребности в операндах формируется запрос к соответствующим операторам, которые поставляют требуемые данные либо порождают новые запросы к другим операторам.

При использовании механизма вызова по запросу система управления вычислительным процессом опреде­ляет порядок выполнения команд и инициирует запрос на вы­числение аргументов при возникновении потребности в них у одной из команд. В данном случае обработка вершин информационного графа происходит в обратном порядке: от узла, вычисляющего конечный результат R, к вышележащим операторным вершинам, поставляющим ему требуемые операнды. При этом в вычислительном процессе существует два потока: первый соответствует рассылке запросов на аргументы, а второй (встречный) - потоку вычисленных результатов.

Пусть требуется вычислить выражение R = (a + b)/ (a x c – d x e) (рис.5.4). Для получения результата R необходимо осуществить запрос к операторам сложения и деления, которые должны предоставить требуемые операнды R₁ и R₂ оператору деления. Значение R₁ передается сразу после вычисления суммы a + b, а для выполнения оператора вычитания необходимо сформировать новые запросы к операторам умножения, вычисляющим значения R₃ и R₄.

Как и в случае управления потоком данных, процесс порождения запросов сопровождается ростом числа параллельных процессов, однако этот рост легко контролируем, а порожденные в результате запросов процессы имеют непосредственное отношение к получению конечного результата.

Особенность данной модели вычислений состоит также в том, что результаты выполнения каждого оператора могут быть сохранены с заменой ими спецификации выполненной операции и при последующих запросах к этим операторам не потребуется их повторного выполнения. Замена операторов и подграфов вычисленными значениями приводит к сокращению информационного графа, в силу чего такие методы управления называют редукционными.

Подобные вычисления описываются редукционными программа­ми, которые представляют собой вложенные выражения. В отличие от машин, управляемых потоком данных, процесс вычисления (редуцирования) по таким программам осуществляется, начиная не с внутреннего, а с внешнего уровня, и представляет собой процесс сокраще­ния выражений путем подстановки вместо подвыражений их значе­ний. С формальной точки зрения процесс вычисления заключается в последовательной замене правой части выражений на левую.

Выделяют два типа моделей редукционных систем: строчную и графовую, которые отличаются тем, что в функцию передаются либо скопированные значения данных, либо указатели на структуры данных. В строчной редукционной модели каждый запросивший узел получает для оценки отдельную копию выражения, которое постепенно редуцируется до единственного значения. В графовой редукционной модели выражение представляется в виде ориентированного графа, сокращаемого по результатам оценки ветвей и подграфов. Управляющему ссылками на граф узлу при запросе возвращается указатель на результат редукции. Обход графа с изменением ссылок продолжаются до получения значения результата, значение которого возвращается осуществившему запрос узлу.

Редукционные вычисления согласуются с концепцией функционального программирования, в основе которого лежит лямбда-исчисление Чёрча. Общепринятым методом реализации функциональных языков типа Lisp являлось использование четырехстековой машины, за которой закрепилось наименование SECD-машины. Процесс оценивая символического выражения в такой машине является реализацией базовой операции приложения функции, как это определено в лямбда-исчислении.

Дата добавления: 2014-11-24; просмотров: 266; Нарушение авторских прав

Мы поможем в написании ваших работ!