Ответы

1. Архитектура вычислительной машины фон-Неймана

Аннотация

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

Основной текст

Компьютеры потока данных представляют собой альтернативу традиционной архитектуре вычислительной машины фон Неймана. Как хорошо известно, основные принципы построения практически всех современных компьютеров были заложены в трудах по теории алгоритмов, активно развивавшейся в первой трети XX века. Работы американского математика фон Неймана составляли значительную часть этого процесса, который привел в феврале 1946 года к их технической реализации: Джон Вильям Моучли разработал, а Джон Преспер Эккерт спроектировал и построил первую универсальную цифровую вычислительную машину ENIAC (Electronic Numerical Integrator And Computer). Несмотря на то, что она была электронным гигантом весом в 30 тонн и площадью 400 кв. метров (в ENIAC'е использовалось 18000 электронных ламп), это был гигантский качественный скачок: скорость вычислений увеличилась в тысячи раз. ENIAC выполнял пять операций сложения или вычитания в секунду, а одну операцию умножения за 2,6 секунды. Эта машина была разработана и построена в школе Электротехники Мура Пенсильванского университета в 1943-1946 годах, около десяти лет эксплуатировалась на военном полигоне в Абердине, а сейчас находится в музее Смитсонианского института.

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

Появление концепции машин потока данных следует отнести, видимо, примерно к 1967 году, когда соответствующие исследования начали проводить Дж. Родригес в Массачусетском Технологическом Институте и Д. Адамс в Станфордском университете. Примерно пятнадцать лет спустя интерес к данной проблеме был уже очень велик (как, впрочем, и вообще к любым разработкам нетрадиционных архитектур компьютеров), в работу было вовлечено достаточно много видных специалистов США, Англии, Франции, Финляндии. К тому моменту было опубликовано достаточное количество работ по проблематике машин потока данных, и в 1982 году американский журнал "Компьютер" посвятил ей специальный выпуск, в котором были помещены статьи крупнейших специалистов из ряда американских университетов и научных центров, и в котором проблема была освещена достаточно полно и основательно. Редакторами выпуска стали Т. Агервала из Исследовательского Центра Т.Дж.Ватсона корпорации ИБМ и Арвинд из Массачусетского Технологического института. Основная часть материала в данном реферате опирается именно на этот источник, статьи [1-6] взяты оттуда.

Интерес к нетрадиционным архитектурам вообще, и к концепции машин потока данных в частности, обусловлен в основном обстоятельствами, которые в настоящий момент сдерживают производительность вычислительных систем [2, 3, 5]. Дело в том, что именно основные особенности компьютеров фон Неймана - наличие единственного счетчика команд, единственного устройства управления, единой глобальной памяти, образуют узкое место, "бутылочное горлышко", которое сдерживает производительность компьютера. Многочисленные попытки строить мультипроцессорные системы из отдельных процессоров с архитектурой фон Неймана, или подобной, пока к значительным успехам не привели, поскольку наталкиваются на трудности синхронизации работы отдельных процессоров, и значительная часть суммарной вычислительной мощности подобных систем растрачивается на процесс организации совместной работы компьютеров, а не на полезные вычисления. Разумеется, пока еще не исчерпаны возможности микроэлектронной технологии, появляются новые технологии, и есть возможности повышения производительности компьютеров просто путем совершенствования быстродействия отдельных компонент. Однако, качественный скачок в производительности вычислительных машин по мнению большинства специалистов все-таки следует ожидать в области архитектурных новаций.

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

Основные концепции организации вычислений в машинах потока данных приводятся в [1, 2]. Компьютер потока данных не имеет ни глобальной памяти, ни счетчика инструкций. Устройство управления машины потока данных может быть единственным, если количество операционных устройств невелико, или нет - это не играет существенной роли в силу некоторого свойства локальности, заложенного в сам принцип организации вычислений. Машина потока данных вообще не имеет дела с адресами ячеек памяти в которых лежат некоторые величины, равно как языки высокого уровн потока данных не имеют дела с именами переменных, которые могут принимать разные значения. Машина потока данных имеет дело только с величинами (или значениями), каждое из которых представляет самостоятельный объект. Для обозначения такого объекта часто используется термин "токен". Вторым фундаментальным понятием концепции машины потока данных является понятие оператора или "актора". Вычисления в машине потока данных организуются следующим образом: значения (токены) передаются между операторами (акторами), когда актор получает все необходимые значения для выполнения операции, он активизируется, поглощает входные токены, а после завершения операции порождает токен результата, пересылаемый к другому актору для которого он становится входным. Имеются очень сильные аналогии между принципом работы машины потока данных, и принципом так называемого функционального или аппликативного программирования [3]. В функциональных языках программирования также отсутствует понятие глобальной памяти, они построены на примерно таком же, как и в машине потока данных понятии величины и понятии функции, которая может быть применена к величине или набору величин, а в качестве результата выдает опять же величину.

Программой компьютера потока данных является граф потока данных [2]. Граф потока данных - это ориентированный граф, узлами которого являются акторы, или операторы, выполняемые над данными, а ориентированные дуги указывают пути, по которым между акторами перетекают значения, или токены. Операция сложения двух чисел в таком графе, например, должна быть представлена узлом с двумя входными дугами, по которым поступают слагаемые, и одной выходной, по которой сумма передается дальше. Понятно, что количество входных и выходных дуг актора зависит от характера выполняемой им операции. Компьютеры потока данных можно классифицировать как хранящие программу, в этих компьютерах должна присутствовать память, в которой хранится программа в виде графа потока данных.

В компьютерах архитектуры фон Неймана последовательность выполняемых инструкций образует поток управления, который создается с помощью счетчика инструкций и глобальной памяти, откуда инструкции извлекаются [1]. В этих компьютерах инструкция выполняется когда на нее указывает счетчик инструкций. В компьютерах потока данных никаких указателей на инструкции нет, и принцип активизации операций (акторов) совсем другой: операция объявляется готовой к исполнению операционным устройством как только на ее входные дуги поступит полный набор величин (токенов), например, инструкция сложения будет готовой к исполнению как только на ее входные две дуги поступят и первое и второе слагаемое. Пока набор входных токенов не содержит полного набора операндов для данной операции, она будет ожидать поступления остальных. Правило активизации операции в компьютерах потока данных предельно локализовано, операция запускается просто когда откуда-то извне, вообще говоря, даже неважно откуда, поступают все необходимые данные. Это обстоятельство способствует децентрализации вычислительных мощностей в таких компьютерах, и построению мультипроцессорных систем. Архитектурной проблемой, как и для обычных компьютеров фон Неймана, остается построение межпроцессорного интерфейса (сети) достаточной пропускной способности и быстродействия.

В рамках изложенной концепции машины потока возможно очень большое количество вариантов архитектуры. Например, машины потока данных могут различаться по количеству входных токенов, которые могут ожидать на одной из дуг актора своих "напарников", которые могут поступить по другой дуге того же актора, а также дисциплиной подбора пар. Практически, было предложено три варианта [4]: на каждой дуге между любыми двумя акторами может находиться только один токен (схема с квитированием); может находиться любое количество токенов, причем они выстроены в очередь, так что при очередной активизации данного актора будет извлечен первый токен (схема с очередями на дугах); и, наконец, на дуге может находиться любое количество токенов, причем каждый токен снабжен ярлыком, а при активизации актора токены на наборе входных дуг актора подбираются с совпадающими ярлыками (ассоциативная схема). В [4] предлагается теоретическая модель архитектуры процессора потока данных, называемая U-интерпретатором, реализующая ассоциативную схему подбора входных токенов актора. Проблема заключается в том, что при реализации циклов, подпрограмм и условных операций возникают графы потока данных с петлями, условными ветвями и некоторыми другими неоднозначными конструкциями, и на входные дуги одного актора могут поступать данные, относящиеся, например, к разным итерациям цикла, либо к разным актам вызова подпрограммы, то есть "непарные" наборы токенов. Для того, чтобы правильно формировать наборы токенов при активизации актора, необходимо помечать все токены одного набора одним и тем же уникальным ярлыком, а затем отбирать их по этому признаку. U-интерпретатор реализует такие ярлыки и позволяет использовать итеративные конструкции и подпрограммы в программах для компьютера потока данных. Схемы с квитированием и с очередями на дугах, вообще говоря, позволяют реализовывать только программы "линейной структуры" (графы потока данных без петель), и, с некоторыми ограничениями условные ветвления в графах. Вторым достоинством модели U-интерпретатора являетс то, что он обеспечивает очень высокую степень параллельности работы операционных устройств в мультипроцессорных архитектурах потока данных, и потому способствует повышению реальной производительности системы. Недостатком этой модели является ее высокая сложность, не очень ясно, возможна ли вообще ее аппаратная реализация.

Работа [3] посвящена подробному разбору влияния архитектуры компьютеров потока данных на языки высокого уровня. Подобно другим типам параллельных компьютеров машины потока данных лучше программируются на специальных языках: большинство разработок потока данных было бы невероятно неэффективно при попытке программировать на обычных языках, таких как Фортран или PL/I. Языки, пригодные для машин потока данных, могут быть очень элегантны. Свойства языка, которых требует компьютер потока данных полезны сами по себе, и подобны некоторым свойствам (правильные управляющие структуры, упорядоченные межмодульные связи), которые, как известно, способствуют разработке простого для понимания и сопровождения программного обеспечения. Языки со многими из этих свойств существовали задолго до появления машин потока данных. Обсуждая языки потока данных следует принять во внимание следующие их свойства:

(1) Отсутствие побочных эффектов. Это свойство всегда важно. Чистый Lisp, возможно, является лучшим примером языка без побочных эффектов. "Функциональные" языки, такие как FP также относятся к этой категории. Связь между отсутствием побочных эффектов и эффективностью параллельных вычислений известна уже давно;

(2) Локальность действия. Языки потока данных вообще предоставляют желательную локальность;

(3) Эквивалентность ограничений планирования инструкций и зависимостей между данными. Это означает, что вся требуемая для выполнения программы информация содержится в ее "графе потока данных". Поскольку граф потока данных есть, в действительности, машинный код для компьютеров потока данных, то это свойство делает язык пригодным для такого компьютера;

(4) Правило "однократного присваивания", языки определений. Переменная может появиться в левой части оператора присваивания только однажды внутри области программы, в которой она активна;

(5) Особенности итеративных конструкций;