Модель - вычисление
Cтраница 3
Автор считает предложенную в языке Ада модель вычислений с параллельной обработкой в высшей степени элегантной. Сторонники языка Ада доказали, что различные, ставшие уже классическими проблемы, связанные с использованием параллельной обработки могут быть решены с помощью языка Ада эффективно и естественно. [31]
В этом разделе будет построена такая модель вычисления, в которой каждый шаг процесса будет разделен на три: запись, вычисление, сдвиг. В этом случае можно распорядиться вычислениями так, что системы, состояния которых определяют, какие следует применить операторы перехода, не будут совпадать с теми системами, в которых содержатся конфигурации, подлежащие изменению. Грубо говоря, требуется, чтобы на каждом шаге вычисления проверяющие системы были бы отделены от систем, чьи состояния изменяются. [32]
Выполнение компилированной программы G-машины основано на модели вычислений, описанной в гл. Она использует стек указателей для спуска и подъема по гребню графа и дамп для вычисления применений функций. Единственной дополнительной особенностью здесь является применение функций, определенных пользователем, для которых графы тела функции должны быть означены подстановкой графов аргументов. [33]
Описанная при этом модель получила название модели вычисления оценок. [34]
Чтобы обсуждать понятие сложности, необходимо иметь модель вычислений. Наша модель включает в себя набор простейших операций и понятия допустимого информационного оператора и допустимого алгоритма. [35]
Таким образом, рассмотренная в этом параграфе модель вычислений применима в широком спектре приложений, связанных с распределенными системами и средами. [36]
В общем случае потоковый граф G соответствует недетерминированной модели вычислений: любой паре, состоящей из входного и выходного сообщений процесса, может соответствовать более одной его истории, и допускаются различные последовательности формирования компонентов сообщений. [37]
Характер меток входных и выходных позиций определяется семантикой модели вычислений. Напомним, что сообщение есть вектор, в котором каждый компонент в свою очередь представляет собой набор атомарных объектов ( значений данных), или токенов. Число входных и выходных позиций вершины графа G совпадает с числом компонентов входного и выходного сообщений соответствующего процесса. [38]
 |
Пример иерархии наследования типов данных. [39] |
Такая семантика меток позволяет ставить вопрос о реализуемости модели вычислений на заданной иерархии классов токенов. Подобная система типов может рассматриваться как основа для реализации концепции полиморфизма при компонентном проектировании программного обеспечения. [40]
В § 3.1 и § 3.2 проблема реализуемости недетерминированной модели потоковых вычислений сводится к поиску стационарной и неизбыточной разметки М - сети на верхней полуструктуре ее свойств, не убывающих в процессе решения задачи разметки. Стационарной разметки может и не существовать. Достигнутая стационарная разметка охватывает все допустимые истории процессов, обусловленные информационной структурой программы. [41]
В § 6 предложен метод распараллеливания алгоритма Ланцоша для модели вычислений с множественным потоком команд и данных. Получена оценка эффективности распараллеливания, зависящая от распределения ненулевых элементов в матрице системы. Параллельный алгоритм Ланцоша был запрограммирован и апробировался на вычислительной системе с 3 процессорами. При решении систем разреженных уравнений, построенных методом линейного решета, была достигнута эффективность распараллеливания, близкая к максимально возможной. [42]
Поскольку наиболее естественная реализация основана на редукции графов, модель вычислений является ленивой, а так как отсутствуют переменные, то нет необходимости рассматривать вопрос об их именах и контексте. К сожалению, даже очень простое Х - выражение имеет сложный эквивалент в КЛ и, хотя отсутствуют переменные, уменьшение накладных расходов из-за отсутствия контекста эффективно компенсируется необходимостью передавать выражения аргументов в качестве параметров. Таким образом, этот сырой подход не применим на практике без оптимизации с целью повышения эффективности. [43]
Замечание 2.1. В пункте ( i) нашего описания модели вычислений мы предполагаем, что каждый линейный функционал допустим. [44]
С одной стороны, поддержка недетерминизма является ценным свойством моделей вычислений и систем программирования. [45]
Страницы: 1 2 3 4