Chapter_16 (1110568), страница 3
Текст из файла (страница 3)
ЭВМ, управляемые потоком данныхВсе рассматриваемые нами до сих пор ЭВМ базировались на изученных нами принципах ФонНеймана. Как уже говорилось, все современные ЭВМ в той или иной мере отказываются от большинства этих принципов для повышения своей производительности. Тем не менее, все рассмотренные досих пор архитектуры ЭВМ продолжают следовать одному основополагающему принципу Фон Неймана. Это принцип программного управления, который состоит в том, что ЭВМ автоматически обрабатывает данные, выполняя расположенную в своей памяти программу.
То, что именно программадолжна обрабатывает данные, представляется большинству программистов совершенно очевидным.Разберёмся, однако, с этим вопросом более подробно.Как Вы помните, ЭВМ является алгоритмической системой, в частности, она является исполнителем алгоритма на языке машины. В прошлом семестре Вам давали примерно следующее неформальное определение алгоритма. "Алгоритм – это чёткая система правил (шагов алгоритма). Обрабатывая входные данные, к которым алгоритм применим, исполнитель алгоритма за конечное числовыполнения своих шагов остановится и выдаст результат (выходные данные)".Как видим, по самому определению алгоритма он выполняет в нашей системе главную роль, аобрабатываемые данные – подчинённую.
В начале развития программистской науки такое положение вещей было очевидным, оно находило своё отражение и в "информативности" программы и данных. Например, изучая текст определённой программы (даже без комментариев), программист мог6выяснить, что она предназначена, например, для вычисления суммы элементов некоторого массива. Вто же время, сколько бы программист не рассматривал числа, составляющие входной массив данных,он, не видя программы, конечно, не может догадаться, для чего предназначены эти данные. Другимисловами, если принять во внимание, что программу в совокупности с её данными можно рассматривать как модель некоторого объекта, то большая часть сведений об этом объекте была сосредоточенаименно в программе, а не в обрабатываемых данных.
Например, исследуя программу решения системлинейных уравнений, мы сможем понять, для чего предназначена эта программа. В то же время, какбы тщательно мы не изучали вводимые этой программой данные (т.е. числовые матрицы), мы вряд липоймём, в чём заключается решаемая задача. Можно сказать, что в некотором смысле в этой задачепрограмма играет главную роль, а обрабатываемые данные – второстепенную.Такая ситуация сохранялась в программировании примерно до начала 80-х годов прошлого века.Далее, однако, обрабатываемые данные непрерывно усложнялись, пока, наконец, для некоторых задач не превзошли по сложности программы, которые обрабатывали эти данные.
Рассмотрим в качестве примера большую базу данных, которая хранит текущее состояние дел некоторого крупногопредприятия. Можно сказать, что база данных содержит сложно структурированную, изменяющуюсяво времени модель этого предприятия. Программы, обрабатывающие информацию из базы данных(БД) называются обычно системой управления базой данных (СУБД) [20].
СУБД позволяет вводить,удалять и модифицировать данные в БД, а также обрабатывать запросы на поиск и выдачу из БДнужных сведений. Так вот, сколько бы программист не исследовал программы, входящие в СУБД, онпрактически ничего не узнает о самом предприятии, ни что оно выпускает, ни сколько человек на нёмработает и т.д. Очевидно, что в нашей модели предприятия (БД+СУБД) данные играют основнуюроль, а обрабатывающие их программы – уже второстепенную.Как Вы можете догадаться, примерно в это же время появилась идея коренным образом изменитьархитектуру компьютера так, чтобы отказаться от принципа программного управления. Таким образом, если компьютеры традиционной архитектуры управляются потоком (или потоками) команд, токомпьютеры новой, нетрадиционной архитектуры должны управляться потоком данных. Можно сказать, что не команды должны определять, когда какие данные надо обрабатывать, а, наоборот, данные выбирают для себя действия (операторы), которые в определённый момент надо выполнить надэтими данными для получения нужного результата.
Компьютеры такой архитектуры принято называть потоковыми ЭВМ (по-английски DFC – Data Flow Computers) [1,16].Заметим, что сам по себе принцип потоковой обработки данных не представляет собой ничегозагадочного или экзотического. Например, отметим, что уже изученные Вами ранее такие алгоритмические системы, как машина Тьюринга и Нормальные алгоритмы Маркова были обработчикамиданных именно этого класса. Действительно, например, в машине Тьюринга именно данные (текущий символ, на который указывает головка), определял, какие именно операции необходимо быловыполнить на этом шаге работы!В то же время оказалось, что архитектура "настоящих" потоковых ЭВМ оказывается весьмавесьма сложной и сильно отличается от архитектуры традиционных ЭВМ.
Например, в устройствеуправления таких ЭВМ нет никакого счётчика адреса, а в их памяти нет программы (по крайней мере,в нашем традиционном понимании). Мы рассмотрим схему функционирование такой потоковойЭВМ на одном очень простом примере.Пусть нам необходимо вычислить такой оператор присваивания:x := (x+y)*p + (x+p)/z - p*y/zПредставим этот оператор в виде так называемого графа потока данных, показанного на рис.16.1. В этом ориентированном графе есть два вида узлов: это сами обрабатываемые данные, изображённые в виде квадратиков (в нашем примере – значения переменных x,y,z и p) и обрабатывающие элементы потоковой ЭВМ, которые мы обозначили просто знаками соответствующих арифметических операций в кружочках.1Основная идея потоковых вычислений состоит в следующем.
Все действия над данными производят обрабатывающие элементы (операторы), в нашем примере эти элемента обозначены арифметическими операциями сложения, вычитания умножения и деления. Можно сказать, что всё арифметико-логическое устройство потоковой ЭВМ – это набор таких обрабатывающих элементов. Каждыйобрабатывающий элемент начинает автоматически выполняться, когда есть в наличие (готовы к об1Заметка на будущее для продвинутых студентов: граф потока данных базируется на принципах построения так называемых сетей Петри.7работке) требуемые для него данные. Так, в нашем примере автоматически (и параллельно!) начинают выполняться обрабатывающие элемента для операторов + , + и * во второй строке нашего графа, затем, на втором шаге работы, параллельно выполняются операторы * , / и / втретьей строке и т.д.
Здесь просматривается большое сходство со способом работы электронныхсхем, составленных из вентилей. Действительно, если граф потока данных "положить на левый бок",то он будет весьма похож на электронную схему двоичного сумматора, как мы показывали её на рис.2.2а). При этом роль вентилей будут играть обрабатывающие элементы, а входных и выходных сигналов – обрабатываемые данные.xpzy++**//+-xРис.16.1. Граф потока данных для оператора присваивания.Заметим, что обрабатываемые данные в потоковом компьютере вовсе не являются пассивными,как в ЭВМ традиционной архитектуры, наоборот, они "громко заявляют" о своей готовности к обработке (можно сказать, требуют к себе "внимания" со стороны обрабатывающих элементов). Вообщеговоря, здесь есть все основания отказаться от принципа Фон Неймана, согласно которому памятьтолько хранит данные, но не обрабатывает их.
Другими словами, представляется естественным совместить функции хранения и обработки данных, и разместить обрабатывающие элементы не варифметико-логическом устройстве, а прямо в оперативной памяти.Вообще говоря, граф потока данных и является "программой" для потоковой ЭВМ, а программ внашем привычном понимании (запись алгоритма на языке машины) здесь не существует. Можно сказать, что здесь сами данные управляют процессом своей обработки. Отсюда можно сделать вывод,что обычные языки программирования плохо подходят для записи алгоритмов обработки данных впотоковых ЭВМ, так что приходится делать сложный специальный компилятор, преобразующийобычную последовательную программу на языке высокого уровня в граф потока данных. Неудивительно поэтому, что вместе с идеей потоковых ЭВМ появились и специальные языки потоков данных(Data Flow Languages),1 ориентированные на прямое описание графа потока данных [1].Из рассмотренной схемы обработки данных в потоковых ЭВМ можно сделать вывод, что в нихможет быть реализован принцип максимального параллелизма в обработке данных, так как любыеготовые данные тут же могут поступать на выполнение соответствующему обрабатывающему элементу потоковой ЭВМ.
Ясно, что быстрее решить данную задачу просто невозможно.Немного подумав, можно выделить две фундаментальные трудности, которые встают при реализации потоковой ЭВМ. Во-первых, для достаточно сложного алгоритма невозможно полностью построить граф потока данных до начала счёта. Действительно, алгоритм вводит свои входные данныеи содержит условные операторы, выполнение которых может, в частности, зависеть и от этих входных данных. Следовательно, компилятор с некоторого традиционного языка программирования может построить только некоторый первоначальный граф потока данных, а устройство управления по1Язык не поворачивается назвать эти языки языками программирования (это каламбур ☺).8токовой ЭВМ должно будет в процессе счёта динамически изменять этот граф. Ясно, что это весьмасложная задача для аппаратуры центрального процессора потоковой ЭВМ.Вторая проблема заключается в том, что арифметико-логическое устройство потоковой ЭВМдолжно содержать много одинаковых обрабатывающих элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
