Новосибирский государственный университетФакультет информационных технологий |
Потоковые вычислительные системы - системы, использующие механизм управления вычислениями, при котором команды выполняются, когда становятся доступными их операнды. В потоковых архитектурах для описания вычислений используется ориентированный граф, иногда называемый графом потоков данных (dataflow graph). Этот граф состоит из вершин (узлов), отображающих операции, и ребер или дуг, показывающих потоки данных между теми вершинами графа, которые они соединяют.
Идеология вычислений, управляемых потоком данных (потоковой обработки), была разработана в 60-х годах Карпом и Миллером. В начале 70-х годов Деннис, а позже и другие начали разрабатывать компьютерные архитектуры, основанные на вычислительной модели с управлением от потока данных в противовес программному управлению (Control Flow). Графическую модель управляемых данными вычислений предложил в диссертационной работе сотрудник Стэнфордского университета Дуайн Адамс.
Основополагающим понятием потоковых вычислений является принцип готовности к выполнению операции по условию готовности всех необходимых для выполнения этой операции операндов. Операнд считается «готовым», если соответствующим этому операнду ячейкам памяти присвоено значение (вычислено ранее или константо-присвоено).
В потоковой архитектуре отсутствует понятие «последовательность инструкций» и нет счетчика команд. Программа в потоковой системе - это не набор команд, а вычислительный граф. Каждый узел графа представляют собой оператор или набор операторов, а ветви отражают зависимости узлов по данным. Очередной узел начинает выполняется как только доступны все его входные данные. В этом состоит один из основных принципов архитектуры: исполнение инструкций по готовности данных. В потоковых машинах данные передаются и хранятся в виде токенов. Токен - это структура, содержащая собственно передаваемое значение и метку - указатель узла назначения.
Потоковый граф, определяющий программу вычислений, хранится в памяти системы в виде таблицы. Каждая запись в таблице представляет одну вершину потокового графа. Порядок размещения записей в памяти несущественен, поскольку момент активации вершины определяется лишь наличием данных на всех ее входах.
Одним из основных достоинств потоковой архитектуры является ее масштабируемость. Устройства могут объединяться простейшим коммутатором, а для адресации токенов служат их метки. Весь диапазон номеров узлов просто распределяется равномерно между устройствами. Никаких дополнительных мер для синхронизации вычислительного процесса, в отличие от многопроцессорной Control Flow архитектуры, не требуется.
Все известные потоковые вычислительные системы могут быть отнесены к двум основным типам: статическим и динамическим. В свою очередь, динамические потоковые ВС обычно реализуются по одной из двух схем: архитектуре с помеченными токенами и архитектуре с явно адресуемыми токенами.
Ключевые термины: вычислительная модель потоковой обработки; control flow; статические потоковые вычислительные системы; динамические потоковые вычислительные системы; мультипотоковые вычислительные системы;
Федотова Ольга |
НГУ ФИТ НГУ ИВТ СО РАН |