Содержание к диссертации
Введение 4
Глава 1. Анализ вычислительных моделей управляемых потоком данных и их
аппаратных реализаций
Статическая модель потока данных 13 1.1.1. MIT Static Dataflow Architecture 14
Динамическая модель потока данных 17
Манчестерская потоковая машина 18
Проект MIT Tagged-Token Dataflow Architecture 21
SIGMA-1 23
Модель вычислений потока данных с явным хранением токенов 24 1.3.1. Проект Monsoon 25
Гибридная модель вычислений потока данных 28
1.4.1. Threaded dataflow архитектура 29
Проект Epsilon-2 29
Проекты ЕМ-4 и ЕМ-Х 30
1.4.2. Крупно-зернистая архитектура потока данных (Large-grain dataflow) 32
1.4.2.1. Проект StarT 32
Выводы по первой главе 36
Глава 2. Исследование функционирования модели вычислений в вычислительной
системе с автоматическим распределением ресурсов
2.1. Модель вычислений, управляемая потоком данных с произвольно
изменяемым контекстом
2.2. Исследование организации и принципов функционирования предлагаемой
вычислительной системы с автоматическим распределением ресурсов
Особенности, накладываемые аппаратной реализацией потоковой модели вычислений с произвольно изменяемым контекстом
Ассоциативная память 56
Исполнительное устройство 59
Коммутатор токенов 62
Коммутатор пар 63
2.3. Программная поддержка модели вычислений 63
2.4. Организация вычислений в вычислительной системе с автоматическим
69 распределением ресурсов
2.4.1. Маскирование полей ключа токена 69
Реализация групповых операций над узлами 70
Преимущества использования произвольно изменяемого контекста при реализации циклов и массивов на В САРР
2.5. Методика использования особенностей ВСАРР при программировании 77
2.5.1. «Пузырьковая сортировка» 78
Выводы по второй главе 87
Глава 3. Разработка алгоритмов функционирования аппаратно-программных средств
работы с динамически формируемым контекстом вычислений
3.1. Блок специальных операций (аппаратной поддержки работы с динамически
формируемым контекстом)
3.1.1. Алгоритм функционирования блока специальных операций 95
3.2. Программная поддержка работы с произвольно изменяемым контекстом 107
3.3. Алгоритм функционирования токенов, обеспечивающих аппаратную
поддержку выполнения условных конструкций
3.4. Алгоритм функционирования многовходовых узлов 114
Выводы по третье главе 117
Глава 4. Создание макета исполнительного устройства системы с автоматическим
распределением ресурсов. Практическая реализация программной поддержки
работы с произвольно изменяемым контекстом. Создание параллельной программы
для ВСАРР
Обоснование выбора ПЛИС в качестве элементной базы макета 118
Макет вычислительной системы с автоматическим распределением ресурсов 121
Разработка макета ВСАРР 125 4.3.1. Краткая характеристика языков проектирования электронных средств 127
Разработка блока специальных операций исполнительного устройства 136
Программная поддержка работы с произвольно изменяемым контекстом (транслятор с машинно-ориентированного параллельного языка вычислительной 141 системы с автоматическим распределением ресурсов)
4.6. Программа «Синтез топологии сети» 147
Выводы по четвертой главе 158
Заключение 159
Литература 161
Перечень сокращений 167
Приложение 1 170
Введение к работе
Актуальность темы
Современная ситуация в области развития науки и техники такова, что существует большое количество современных фундаментальных задач, от решения которых зависит развитие целого направления исследования и которые имеют большое практическое значение. Для решения этих задач требуются многопроцессорные суперЭВМ с реальной производительностью 1012-1016 операций в секунду. Перечислим некоторые из них: задачи гидро- и газодинамики, изучение свойств веществ в интересах ядерной энергетики, моделирование ядерных процессов, структурное исследование человеческих генов, молекулярное конструирование лекарств, прогноз экологических изменений и природных геофизических явлений, таких как климат, загрязнение среды, сейсмическая обстановка, проектирование сверхсложных радиоэлектронных комплексов, в том числе микропроцессоров и другие.
С каждым годом требования, предъявляемые к вычислительной технике, на которой будут решаться эти задачи, только возрастают.
Основным методом увеличения производительности вычислительных средств становится метод распараллеливания вычислительных процессов. На математическом уровне задача распараллеливания вычислительного процесса успешно решается.
На аппаратном уровне основным методом повышения производительности вычислительных комплексов в настоящее время является совершенствование технологии, а поскольку производительность одного процессора на используемой элементной базе близка к пределу, то увеличивают число процессоров в системе. Однако, увеличение числа процессоров в подобных системах, не всегда приносит значительную выгоду, ввиду того, что падает коэффициент загрузки каждого процессора в системе и соответственно реальная производительность всей системы в целом, что подтверждается результатами, полученными на тестовых пакетах. При решении практических задач реальная производительность микропроцессора системы может быть существенно меньше пиковой. В числе основных причин падения реальной производительности вычислительных комплексов, можно выделить следующие:
необходимость синхронизации вычислительных процессов по данным;
потеря времени на обмен данными между процессорами.
Таким образом, в настоящее время актуальна задача создания вычислительной системы, которая обеспечивала бы на аппаратном уровне предельное распараллеливание вычислительных процессов, синхронизацию по данным в динамике вычислений и
5 эффективность использования вычислительных средств.
В вычислительных системах, построенных на традиционных фон-неймановских принципах, данные задачи на текущий момент не решены.
В настоящее время в отделе «Построения информационно-вычислительных систем высокого параллелизма» Института проблем информатики Российской Академии Наук разработаны новые принципы организации вычислительного процесса и на их основе разработана вычислительная система, использующая модель вычислений, управляемую потоком данных с динамически формируемым контекстом вычислений. Создан инструментальный комплекс и макет системы.
Диссертационная работа посвящена созданию аппаратно-программных средств работы с динамически формируемым контекстом вычислений (возможна работа с контекстом, как со структурой, формат которой может переопределяться в ходе вычислений и значения полей контекста также формируются во время вычислений), который является одним из основных принципов построения рассматриваемой архитектуры, что и определяет актуальность данной работы.
Создание аппаратно-программных средств работы с динамически формируемым контекстом вычислений, отвечающих всем требованиям новой архитектуры и обеспечивающих поддержку основного класса базовых конструкций и алгоритмов, повышает эффективность работы всей системы.
Цель и задачи работы
Настоящая диссертационная работа посвящена созданию аппаратно-программных средств работы с динамически формируемым контекстом вычислений в системе с автоматическим распределением ресурсов, разработке принципов функционирования и структуры, отвечающих за это блоков системы, методов их аппаратной реализации, разработке программной поддержки конструкций, обеспечивающих работу с динамически формируемым контекстом и их программной реализации. Для достижения поставленной цели в работе поставлены и решаются следующие основные задачи:
Анализ состояния и развития существующих потоковых моделей вычислений и их аппаратных реализаций.
Анализ потоковой модели вычислений с динамически формируемым контекстом и исследование ее аппаратной реализации - вычислительной системы с автоматическим распределением ресурсов.
Разработка команд, обеспечивающих работу с динамически формируемым контекстом вычислений, которые входят в систему команд.
Создание алгоритмов работы команд, обеспечивающих эффективную работу с динамически формируемым контекстом выполняемой программы, а также разработка структуры и принципов аппаратной реализации блока исполнительного устройства на основе исследования возможностей современной элементной базы.
Разработка программной поддержки - трансляции конструкций параллельного машинно-орентированного языка вычислительной системы с автоматическим распределением ресурсов, обеспечивающих работу с динамически формируемым контекстом вычислений.
Создание программ, имеющих практическую ценность, а также их исследование с целью выявления максимального параллелизма и эффективности их выполнения.
Осуществление практической реализации предложенных методов на макете исполнительного устройства.
Объект и предмет исследования
Объектом исследования является вычислительная система новой нетрадиционной архитектуры - вычислительная система с автоматическим распределением ресурсов (ВСАРР). Предметом исследования являются созданные аппаратно-программные средства работы с динамически формируемым контекстом вычислений, что позволяет значительно повысить эффективность организации параллельных процессов и производительность в ВСАРР; разработанные алгоритмы и программы, их исследование на программной модели ВСАРР - инструментальном комплексе, и на аппаратной модели ВСАРР - макете; решение задач на инструментальном комплексе с целью проверки эффективности разработанных методов.
Методы исследования
Исследования проводились с использованием теории параллельных вычислений, теории высокопроизводительных вычислений, теории построения трансляторов, теории инструментальных комплексов, теории проектирования ЭВМ и методик проектирования сложных вычислительных комплексов с применением систем автоматизированного проектирования. Аппаратная реализация макета исполнительных устройств велась в соответствии с принципами нисходящего проектирования с использованием объектно-ориентированного подхода.
Научная новизна
Впервые разработаны аппаратно-программные средства работы с динамически
7 формируемым контекстом вычислений в вычислительной системе нетрадиционной архитектуры - системе с автоматическим распределением ресурсов. Основные научные результаты работы состоят в следующем:
разработана часть системы команд, отвечающая за работу с динамически формируемым контекстом, и разработаны эффективные алгоритмы выполнения команд;
аппаратно реализован блок исполнительного устройства вычислительной системы с автоматическим распределением ресурсов, осуществляющий выполнение системы команд работы с динамически формируемым контекстом;
в качестве программной поддержки работы с динамически формируемым контекстом операндов реализована трансляция конструкций параллельного машинно-ориентированного языка высокого уровня, отвечающих за работу с динамически формируемым контекстом вычислений;
систематизированы способы организации работы со структурами данных (такими как деревья, вектора, многомерные массивы) в вычислительной системе с автоматическим распределением ресурсов;
исследовано прохождение ряда программ на инструментальном комплексе и на макете, подтвердившее правильность самой концепции вычислительной модели и реализуемой на ее основе архитектуры, а также выявившее предельный параллелизм и эффективность выполнения программ;
предложен новый метод реализации условных конструкций в вычислительной системе с автоматическим распределением ресурсов, позволяющий оптимизировать выполнение задачи;
предложен новый метод реализации многовходовых узлов в ВСАРР.
Практическая значимость
Практическая значимость работы заключается в следующем: 1. Разработанные в диссертационной работе специальные команды для эффективной работы с динамически формируемым контекстом вычислений вошли в систему команд ВСАРР. Разработанные и реализованные автором алгоритмы работы данных команд эффективно применяются и для работы со структурами данных, а также могут быть использованы при последующих реализациях ВСАРР и в специализированных вычислительных системах. Аппаратная реализация блока специальных операций, который вошел в состав исполнительного устройства макета ВСАРР, позволяет оценить работоспособность и эффективность предложенных аппаратных решений.
Разработанные алгоритмы трансляции конструкций параллельного машинно-ориентированного языка высокого уровня, обеспечивающих работу с динамически формируемым контекстом (ДФК) вычислений, позволяют повысить эффективность программирования и могут быть использованы при создании трансляторов со стандартных языков высокого уровня. Реализованные алгоритмы трансляции конструкций, обеспечивающих работы с ДФК вычислений вошли в состав созданного транслятора с параллельного машинно-ориентированного языка высокого уровня.
На примере созданной программы «Синтез топологии сетей» показана эффективность работы предлагаемой архитектуры при решении задач, представляющих практический интерес, что позволяет судить о правильности, принятых аппаратно-программных решений, обеспечивающих поддержку работы с динамически формируемым контекстом вычислений.
Предложены новые методы аппаратной реализации условных конструкций и многовходовых узлов.
Основные положения, которые выносятся на защиту:
Анализ архитектуры вычислительной системы с автоматическим распределением ресурсов, позволил выявить возможности повышения производительности системы.
Разработанная система команд и алгоритмы выполнения команд, позволяют обеспечить работу с динамически формируемым контекстом вычислений.
Разработанный блок, входящий в состав исполнительного устройства вычислительной системы с автоматическим распределением ресурсов, осуществляет работу с динамически формируемым контекстом вычислений.
Разработанные программные средства трансляции конструкций параллельного машинно-ориентированного языка высокого уровня, обеспечивают работу с динамически формируемым контекстом.
Созданный на ПЛИС с целью апробации разработанных методов блок, входящий в состав исполнительного устройства макета системы с автоматическим распределением ресурсов, осуществляет работу с динамически формируемым контекстом вычислений.
Создана программа "Синтез топологии сетей", которая представляет практический интерес, проведена оценка ее максимального распараллеливания и эффективности выполнения на инструментальном комплексе.
Предложены новые алгоритмы аппаратной поддержки выполнения условных конструкций и многовходовых узлов.
Реализация результатов работы
Разработанные теоретические положения и новые технические решения опробованы экспериментально на инструментальном комплексе и на макете вычислительной системы с автоматическим распределением ресурсов. Результаты работы реализованы в Институте проблем информатики РАН (ИПИ РАН) в отделе Проблем построения информационно-вычислительных систем высокого параллелизма при исследовании и разработке нетрадиционной архитектуры вычислительных систем с автоматическим распределением ресурсов, а также при реализации проекта по созданию макета вычислительной машины данной архитектуры.
Апробация результатов
Основные положения и результаты работы докладывались и обсуждались на научных семинарах в ИПИ РАН 2001-2005 гг., а также на ряде международных и всероссийских конференций в период с 2000 года по 2005 года: на международных молодежных научных конференциях "XXVI Гагаринские чтения" (Москва, 2000) и "XXVII Гагаринские чтения" (Москва, 2001); на международной научной конференции "С.А. Лебедев и развитие отечественной вычислительной техники" (Москва, 2002); на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС'2003» (пос. Дивноморское, 2003), на международной научно-практической конференции «Искусственный интеллект - 2004. Интеллектуальные и многопроцессорные системы - 2004» (пос. Кацивели, Крым, 2004), на «II Научной сессии Института проблем информатики Российской академии наук: Проблемы и методы информатики» (Москва, 2005).
Исследование разработанных методов аппаратной и программной поддержки работы с динамически формируемым контекстом проводилось в Институте проблем информатики РАН на инструментальном комплексе и при отладке макета ВСАРР.
Структура диссертации.
Диссертационная работа состоит из введения, четырех глав, списка литературы из 84 наименований и одного приложения. Работа изложена на 181 странице машинописного текста, из них основного текста 168 страниц и 13 страниц приложения, работа включает 70 рисунков и 6 таблиц в основной части, приложения содержат 16 рисунков.
Аннотация диссертационной работы по главам
В первой главе диссертационной работы приведен обзор существующих вычислительных моделей, управляемых потоком данных, и их конкретных аппаратных
реализаций. Выполнен анализ преимуществ и недостатков каждой из вычислительных моделей.
Вторая глава посвящена анализу вычислительной модели, управляемой потоком данных с произвольно изменяемым контекстом. Исследованы особенности организации параллельных вычислительных процессов в вычислительной системе нетрадиционной архитектуры с автоматическим распределением ресурсов (ВСАРР), рассмотрена ее структура и выполняемые отдельными устройствами функции. Рассматривается программная поддержка работы с произвольно изменяемым контекстом операндов. Рассмотрены на примере программы принципы программирования, используемые в данной вычислительной системе.
Третья глава содержит описание разработанных алгоритмов работы блока спецопераций, который осуществляет аппаратную поддержку системы команд, обеспечивающей работу с произвольно изменяемым контекстом. Представлены разработанные алгоритмы трансляции конструкций языка, относящихся к произвольно изменяемому контексту. Предложены алгоритмы аппаратной работы с условными конструкциями в ВСАРР. Рассматривается возможность введения аппаратной поддержки выполнения многовходовых узлов в рассматриваемой вычислительной системе.
В четвертой главе приведены материалы по разработке исполнительного устройства макета ВСАРР. Обосновывается выбор используемой элементной базы. Рассматривается методология проектирования, использованная при проектировании макета ВСАРР. Рассматривается транслятор с параллельного машинно-ориентированного языка высокого уровня ВСАРР. Рассматривается алгоритм создания программы, использующей особенности предлагаемой архитектуры, и реализованная на его основе - сама программа. Исследовано ее прохождение на инструментальном комплексе системы с целью проверки уровня достигаемого параллелизма и загрузки исполнительных устройств системы.
В заключение работы приведена общая характеристика работы, обобщены основные результаты проведенных автором исследований и разработок, сформулированы основные выводы по работе в целом, намечены пути дальнейшего исследования методов организации параллельных вычислительных процессов в ВСАРР и аппаратно-программной поддержки работы с произвольно изменяемым контекстом операндов.
