Новосибирский государственный университет Факультет информационных технологий

А.М.Федотов

Словарь терминов в коллекции "Вычислительные системы"

Потоковые вычислительные системы

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

Идеология вычислений, управляемых потоком данных (потоковой обработки), была разработана в 60-х годах Карпом и Миллером. В начале 70-х годов Деннис, а позже и другие начали разрабатывать компьютерные архитектуры, основанные на вычислительной модели с управлением от потока данных в противовес программному управлению (Control Flow). Графическую модель управляемых данными вычислений предложил в диссертационной работе сотрудник Стэнфордского университета Дуайн Адамс.

Основополагающим понятием потоковых вычислений является принцип готовности к выполнению операции по условию готовности всех необходимых для выполнения этой операции операндов. Операнд считается «готовым», если соответствующим этому операнду ячейкам памяти присвоено значение (вычислено ранее или константо-присвоено).

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

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

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

Все известные потоковые вычислительные системы могут быть отнесены к двум основным типам: статическим и динамическим. В свою очередь, динамические потоковые ВС обычно реализуются по одной из двух схем: архитектуре с помеченными токенами и архитектуре с явно адресуемыми токенами.

Литература
• Brewer E. Clustering: Multiply and Conquer // Data Communications, July, 1997.
• Dennis J.B., Misunas D.P. A preliminary architecture for a basic data-flow processor // ISCA '75 Proceedings of the 2^nd Annual Symposium on Computer Architecture. - P. 126-132
• Dennis J.B. Dataflow Supercomputers // Computer. - 1980. - N 13. - P. 48-56.
• Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов / С.А. Орлов, Б.Я. Цилькер. - СПб.: Питер, 2011. - 688 с.

Ключевые термины, связанные с термином "Потоковые вычислительные системы":

1. Вычислительные системы волнового фронта
2. Динамические потоковые вычислительные системы
3. Мультипотоковые вычислительные системы
4. Статические потоковые вычислительные системы
5. Управление от потока данных

Литература

Основная:

1. Цилькер Б.Я. Организация ЭВМ и систем : Учебник для вузов / Б.Я. Цилькер, С.А. Орлов. - 2-е изд. - СПб.: Питер, 2011. - 688 с. - ISBN 978-5-49807-862-5.

Ключевые термины (головные):  Вычислительная модель потоковой обработки;   Control Flow;   Статические потоковые вычислительные системы;   Динамические потоковые вычислительные системы;   Мультипотоковые вычислительные системы;

Контекстный поиск: Задайте образец для поиска:

Федотов Анатолий Михайлович

НГУ ФИТ НГУ ИВТ СО РАН