452
Глава 5. Вычисления на регистровых машинах
произвести замены, наша машина использует третий « временный» регистр, который мы
назовем t. (Сначала мы помещаем остаток в t, затем помещаем содержимое b в a, и
наконец переносим остаток, хранимый в t, в b.)
Можно изобразить регистры и операции, требуемые нашей машине, при помощи
диаграммы путей данных, показан ной на рисунке 5.1. Регистры (a, b и t) на этой
диаграмме изображаются в виде прямоугольников. Каждый способ присвоить регистру
значение обозначается стрелкой, указывающей из источника данных на регистр, со знач-
ком Х позади головки. Можно считать этот Х кнопкой, которая при нажатии позволяет
значению из источника «перетечь» в указанный регистр. Метка рядом — это имя для
кнопки. Имена эти произвольны, и их можно подбирать с мнемоническим значением
(например, a<-b обозначает нажатие кнопки, которая присваивает содержимое регистра
b регистру a). Источником данных для регистра может служить другой регистр (как в
случае присваивания a<-b), результат операции (как в случае присваивани я t<-r) или
константа (встроенное значение, которое нельзя изменять и которое представляется на
диаграмме путей данных в виде треугольника со значением внутри).
Операция, которая вычисляет значение на основе констант и содержимого регистров,
представляется на диаграмме путей данных в виде трапеции, содержащей имя опера-
ции. Например, фигура, обо значенная на рисунке 5.1 как rem, представляет операцию,
вычисля ющую остаток от деления содержимых регистров a и b, к которым она подсо-
единена. Стрелки (без кнопок) указывают из входных регистров и констант на фигуру, а
другие стрелк и связывают результат операции с регистрами. Сравнение изображается в
виде круга, содержащего имя теста. К примеру, в нашей машине НОД имеется операция,
которая проверяет, не равно ли содержимое регистра b нулю. У теста тоже есть входные
стрелки, ведущие из входных регистров и констант, но у него нет исходящих стрелок;
его значение используется контроллером, а не путями данных. В целом, диаграмма путей
дан ных показывает регистры и операции, которые нужны машине, и как они должны
быть связаны. Если мы рассматриваем стрелки как провода, а кнопки Х как переключ а-
тели, то диаграмма путей данных оказывается очень похожа на схему машины, которую
можно было бы построи ть из электронных деталей.
Для того, чтобы пути данных вычисляли НОД, нужно нажимать кнопки в правильной
последовательности. Мы будем описывать эту последовательность с помощью диаграм-
мы контроллера, показанной на рисунке 5.2. Элементы диаграммы контрол лера показы-
вают, как следует работать с компонентами путей данных. Прямоугольные блоки в такой
диаграмме указывают, на какие кнопки следует нажимать, а стрелки описывают после-
довательный переход от одного шага к другому. Ромб на диаграмме обозначает выбор.
Произойдет переход по одной из двух исходящих стрелок, в зависимости от значения
того теста в потоке данных, имя которого у казано в ромбе. Можно интерпретировать
контроллер с помощью физической аналогии: представьте себе, что диаграмма — это
лабиринт, в котором катается шарик. Когда шарик закатывается в прямоугольник, он на-
жимает на кнопку, имя ко торой в прямоугольнике написано. Когда шарик закатывается в
узел выбора (например, тест b = 0), он покидает этот узел по стрел ке, которую опреде-
ляет результат указанного теста. Взятые вместе, пути данных и контроллер полностью
определя ют машину для вычисления НОД . Мы запускаем контроллер (катящийся ша-
рик) в месте, обозначенном start, поместив предварительно числа в регистры a и b.
Когда контроллер достигает точки, помеченной done, в регистре a оказывается значение
НОД.