автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Аппаратно-программные средства работы с динамически формируемым контекстом вычислений в системе с автоматическим распределением ресурсов

На правах рукописи

Левченко Николай Николаевич

АППАРАТНО-ПРОГРАММНЫЕ СРЕДСТВА РАБОТЫ С ДИНАМИЧЕСКИ ФОРМИРУЕМЫМ КОНТЕКСТОМ ВЫЧИСЛЕНИЙ В СИСТЕМЕ С АВТОМАТИЧЕСКИМ РАСПРЕДЕЛЕНИЕМ РЕСУРСОВ

Специальность: 05.13.15 - «Вычислительные машины и системы»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

Работа выполнена в Институте проблем информатики РАН.

Научный руководитель: доктор технических наук, профессор,

Владимир Павлович Торчигин

Официальные оппоненты: доктор технических наук, профессор,

Светлана Александровна Пескова

кандидат технических наук, старший научный сотрудник Вычислительного центра РАН им. А.А. Дородницына Сергей Алексеевич Щербаков

Ведущая организация: Институт электронных управляющих

машин ОАО (ИНЭУМ)

Защита диссертации состоится «2/» 2005 года в ^ часов на

заседании диссертационного совета Д 002.073.01 при Институте проблем информатики РАН по адресу: 119333, Москва, ул. Вавилова, д. 44, корп. 2.

С диссертацией можно ознакомиться в библиотеке Института проблем информатики РАН.

Автореферат разослан мая 2005 г.

Отзыв, заверенный печатью, просим отправлять в одном экземпляре по адресу: 119333, Москва, ул. Вавилова, д. 44, корп. 2.

Ученый секретарь диссертационного совета Д 002.073.01 доктор технических наук,

профессор С.Н. Гринченко

г

Общая характеристика работы

Актуальность темы

Современная ситуация в области развития науки и техники такова, что существует большое количество современных фундаментальных задач, от решения которых зависит развитие целого направления исследования и которые имеют большое практическое значение. Для решения этих задач требуются многопроцессорные суперЭВМ с реальной производительностью 1012-1016 операций в секунду. Перечислим некоторые из них: задачи гидро- и газодинамики, изучение свойств веществ в интересах ядерной энергетики, моделирование ядерных процессов, структурное исследование человеческих генов, молекулярное конструирование лекарств, прогноз экологических изменений и природных геофизических явлений, таких как климат, загрязнение среды, сейсмическая обстановка, проектирование сверхсложных радиоэлектронных комплексов, в том числе микропроцессоров и другие.

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

Основным методом увеличения производительности вычислительных средств становится метод распараллеливания вычислительных процессов. На математическом уровне задача распараллеливания вычислительного процесса успешно решается.

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

- необходимость синхронизации вычислительных процессов по данным;

- потеря времени на обмен данными между процессорами.

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

В вычислительных системах, построенных на традиционных фон-неймановских принципах, данные задачи на текущий момент не решены.

В настоящее время в отделе «Построения информационно-вычислительных систем высокого параллелизма» Института проблем информатики Российской Академии Наук разработаны новые принципы организации вычислительного процесса и на их основе разработана^выаддоодадкщздшетема, использующая

| БИБЛИОТЕКА I

! ¿п*те*в»г кол

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

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

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

Настоящая диссертационная работа посвящена созданию аппаратно-программных средств работы с динамически формируемым контекстом вычислений в системе с автоматическим распределением ресурсов, разработке принципов функционирования и структуры, отвечающих за это блоков системы, методов их аппаратной реализации, разработке программной поддержки конструкций, обеспечивающих работу с динамически формируемым контекстом и их программной реализации. Для достижения поставленной цели в работе поставлены и решаются следующие основные задачи:

1. Анализ состояния и развития существующих потоковых моделей вычислений и их аппаратных реализаций.

2. Анализ потоковой модели вычислений с динамически формируемым контекстом и исследование ее аппаратной реализации - вычислительной системы с автоматическим распределением ресурсов.

3. Разработка команд, обеспечивающих работу с динамически формируемым контекстом вычислений, которые входят в систему команд.

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

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

6. Создание программ, имеющих практическую ценность, а также их исследование с целью выявления максимального параллелизма и эффективности их выполнения.

7. Осуществление практической реализации предложенных методов на макете исполнительного устройства.

Объект и предмет исследования

Объектом исследования является вычислительная система новой нетрадиционной архитектуры - вычислительная система с автоматическим распределением ресурсов (ВСАРР). Предметом исследования являются созданные

аппаратно-программные средства работы с динамически формируемым контекстом вычислений, что позволяет значительно повысить эффективность организации параллельных процессов и производительность в ВСАРР; разработанные алгоритмы и программы, их исследование на программной модели ВСАРР - инструментальном комплексе, и на аппаратной модели ВСАРР - макете; решение задач на инструментальном комплексе с целью проверки эффективности разработанных методов. Методы исследования

Исследования проводились с использованием теории параллельных вычислений, теории высокопроизводительных вычислений, теории построения трансляторов, теории инструментальных комплексов, теории проектирования ЭВМ и методик проектирования сложных вычислительных комплексов с применением систем автоматизированного проектирования. Аппаратная реализация макета исполнительных устройств велась в соответствии с принципами нисходящего проектирования с использованием объектно-ориентированного подхода. Научная новизна

Впервые разработаны аппаратно-программные средства работы с динамически формируемым контекстом вычислений в вычислительной системе нетрадиционной архитектуры - системе с автоматическим распределением ресурсов.

Основные научные результаты работы состоят в следующем:

• разработана часть системы команд, отвечающая за работу с динамически формируемым контекстом, и разработаны эффективные алгоритмы выполнения команд;

• аппаратно реализован блок исполнительного устройства вычислительной системы с автоматическим распределением ресурсов, осуществляющий выполнение системы команд работы с динамически формируемым контекстом;

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

• систематизированы способы организации работы со структурами данных (такими как деревья, вектора, многомерные массивы) в вычислительной системе с автоматическим распределением ресурсов;

• исследовано прохождение ряда программ на инструментальном комплексе и на макете, подтвердившее правильность самой концепции вычислительной модели и реализуемой на ее основе архитектуры, а также выявившее предельный параллелизм и эффективность выполнения программ;

• предложен новый метод реализации условных конструкций в вычислительной системе с автоматическим распределением ресурсов, позволяющий оптимизировать выполнение задачи;

• предложен новый метод реализации многовходовых узлов в ВСАРР. Практическая значимость

Практическая значимость работы заключается в следующем:

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

2. Разработанные алгоритмы трансляции конструкций параллельного машинно-ориентированного языка высокого уровня, обеспечивающих работу с динамически формируемым контекстом (ДФК) вычислений, позволяют повысить эффективность программирования и могут быть использованы при создании трансляторов со стандартных языков высокого уровня. Реализованные алгоритмы трансляции конструкций, обеспечивающих работы с ДФК вычислений вошли в состав созданного транслятора с параллельного машинно-ориентированного языка высокого уровня.

3. На примере созданной программы «Синтез топологии сетей» показана эффективность работы предлагаемой архитектуры при решении задач, представляющих практический интерес, что позволяет судить о правильности, принятых аппаратно-программных решений, обеспечивающих поддержку работы с динамически формируемым контекстом вычислений.

4. Предложены новые методы аппаратной реализации условных конструкций и многовходовых узлов.

Положения, выносимые на защиту:

1. Анализ архитектуры вычислительной системы с автоматическим распределением ресурсов, позволил выявить возможности повышения производительности системы.

2. Разработанная система команд и алгоритмы выполнения команд, позволяют обеспечить работу с динамически формируемым контекстом вычислений.

3. Разработанный блок, входящий в состав исполнительного устройства вычислительной системы с автоматическим распределением ресурсов, осуществляет работу с динамически формируемым контекстом вычислений.

4. Разработанные программные средства трансляции конструкций параллельного машинно-ориентированного языка высокого уровня, обеспечивают работу с динамически формируемым контекстом.

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

6. Создана программа "Синтез топологии сетей", которая представляет практический интерес, проведена оценка ее максимального распараллеливания и эффективности выполнения на инструментальном комплексе.

7. Предложены новые алгоритмы аппаратной поддержки выполнения условных конструкций и многовходовых узлов.

Реализация результатов работы

Разработанные теоретические положения и новые технические решения опробованы экспериментально на инструментальном комплексе и на макете вычислительной системы с автоматическим распределением ресурсов. Результаты работы реализованы в Институте проблем информатики РАН (ИЛИ РАН) в отделе Проблем построения информационно-вычислительных систем высокого параллелизма при исследовании и разработке нетрадиционной архитектуры вычислительных систем с автоматическим распределением ресурсов, а также при реализации проекта по созданию макета вычислительной машины данной архитектуры. Апробация работы

Основные положения и результаты работы докладывались и обсуждались на научных семинарах в ИЛИ РАН 2001-2005 гг., а также на ряде международных и всероссийских конференций в период с 2000 года по 2005 года: на международных молодежных научных конференциях "XXVI Гагаринские чтения" (Москва, 2000) и "XXVII Гагаринские чтения" (Москва, 2001); на международной научной конференции "С.А. Лебедев и развитие отечественной вычислительной техники" (Москва, 2002); на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС'2003» (пос. Дивноморское, 2003), на международной научно-практической конференции «Искусственный интеллект - 2004. Интеллектуальные и многопроцессорные системы - 2004» (пос. Кацивели, Крым, 2004), на «II Научной сессии Института проблем информатики Российской академии наук: Проблемы и методы информатики» (Москва, 2005).

Исследование разработанных методов аппаратной и программной поддержки работы с динамически формируемым контекстом проводилось в Институте проблем информатики РАН на инструментальном комплексе и при отладке макета ВСАРР. Публикации

По материалам диссертационной работы опубликовано 12 печатных работ, список которых приводится в конце автореферата. Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, списка литературы из 80 наименований и одного приложения.

Работа изложена на 175 с границах машинописного текста, включая 73 рисунка и 6 таблиц. Содержание работы

Во введении обоснована актуальность темы диссертации, определены научная новизна и практическая ценность работы, сформулированы цель и основные задачи исследований, приведено краткое описание структуры диссертации.

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

Рассмотрен принцип потока данных, который обеспечивает высокую параллельность вычислительных процессов, и исключает конфликтные ситуации

по данным, которые могут возникать из-за ошибок синхронизации вычислительного процесса.

Выполнен анализ преимуществ и недостатков вычислительных моделей, управляемых потоком данных. Можно выделить два основных принципа потоковых моделей:

- асинхронность выполнения - любая операция выполняется тогда и только тогда, когда появились все ее операнды;

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

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

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

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

• аппаратная реализация на существующей в то время элементной базе была слишком сложной и неэффективной;

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

• не был решен целый ряд принципиальных ограничений (проблема создания «бесконечной» ассоциативной памяти, обезличенные ресурсы, медленное выполнение одиночных операций из-за больших задержек в кольце, отсутствие средств регулирования прохождения вычислительного процесса и другие).

Во второй главе автором исследована вычислительная модель, управляемая потоком данных с динамическим формированием контекста. Проанализированы методы организации вычислительных процессов в рассматриваемой вычислительной системе. Проведен анализ особенностей аппаратной реализации вычислительной модели - как архитектуры, так и функционирования вычислительной системы нетрадиционной архитектуры - ВСАРР.

Особенности вычислительной модели управляемой потоком данных с динамически формируемым контекстом

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

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

Пример графа вычислительного процесса приведен на рис. 1.

("V»), «6»|в

1-ОагТ1 Т2.1Э т4

тз та. г?

Рис 1 Граф выполнения вычислительного процесса Основными структурными единицами потоковой программы являются узлы, именно на уровне узлов можно говорить о параллелизме в вычислительной модели. С каждым узлом связана программа, которая называется программой узла.

Между узлами происходит обмен информацией. Сообщение, передаваемое из узла в узел, называется токеном. Токен представляет собой структуру, в состав которой входят поле данных с той информацией, которую токен поставляет в узел, контекст и адрес узла, в который этот токен послан. Запуск программы узла происходит при поступлении соответствующих данных на вход виртуального узла и называется активацией узла Поскольку контекст токенов, поступающих на вход виртуального узла, независим от контекстов токенов, поступающих на другие виртуальные узлы, то все программ узлов могут выполняться в параллель на любом свободном исполнительном устройстве. Результатом выполнения

программы узла может быть посылка одного или многих токенов в другие узлы или посылка токенов-результатов на «хост-машину».

В число особенностей рассматриваемой модели входят следующие:

1. Динамически формируемый контекст.

2. Возможность аппаратно-программного изменения хода выполнения вычислительного процесса с помощью изменения контекста, а также -использование специального токена - косвенность.

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

4. Маскирование.

5. Возможность многократного считывания данных с автоматическим их последующим удалением.

6. Эффективное освобождение ассоциативной памяти при помощи специальных команд ассоциативной памяти (токен стирание и другие).

7. Обезличенные исполнительные устройства.

Динамически формируемый контекст (ДФК) вычислений, как и контекст предыдущих моделей вычислений, управляемых потоком данных, однозначно идентифицирует данное в виртуальном пространстве задачи. В системе формирование (изменение) ДФК, в частности, его отдельных полей, происходит в динамике - по ходу выполнения программы. Одновременно или по отдельности с формированием ДФК, осуществляется работа с ДФК, как со структурой, формат обращения к которой, может быть переопределен в ходе вычислений (в частности, без изменения самого данного). Подобный принцип работы с ДФК предъявляет определенные требования к аппаратно-программным средствам и обеспечивает значительное повышение эффективности системы.

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

В общем случае виртуальный экземпляр узла однозначно идентифицируется тем ключом, в контексте которого он работает. Контекст, в свою очередь, однозначно определяется одной или несколькими известными в процессе вычислений величинами. Токены, поступающие на входы узла, могут относиться к различным виртуальным экземплярам (другими словами, к различным его активациям) этого узла.

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

Активация узла производится по готовности обоих операндов, то есть сразу после того, как оба токена, посланные в узел, пришли на этот узел. Аппаратная

реализация данного основного принципа потоковой модели вычислений лучше всего получается при использовании ассоциативной памяти (АП).

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

Исследование организации и принципов функционирования вычислительной системы с автоматическим распределением ресурсов

Единицами информации, циркулирующими (обрабатываемыми) в вычислительной системе, являются токен и пара токенов (рис. 2). Токены представляют собой структуру, которая содержит передаваемое данное, ключ, а также служебные признаки и атрибуты. На вход программы узла графа для обработки поступает пара токенов, содержащая до двух данных.

Рис 2 Общая структура данных ВСАРР

В поле признаков записываются код первой операции, выполняемой над данными в программе узла графа, тип токена, а также другая служебная информация.

Динамически формируемый контекст (в дальнейшем под контекстом понимаем ключ, состоящий из контекста и адреса узла) вычислений предоставляет следующие преимущества:

• Максимально эффективное распараллеливание вычислений;

• Возможность изменения хода выполнения вычислительного процесса в динамике при помощи операций, выполняемых над ключом токена;

• Экономия системных ресурсов (в частности, более эффективное использование АП);

• Более эффективное формирование запросов к элементам структуры;

• Осуществление возможности выборки элементов матриц и других многомерных массивов по любому измерению или их комбинации (за одно обращение);

• Возможность использования полей контекста для передачи переменных или констант на обработку в узел;

• Параллельность работы с контекстом и данными;

• Возможность параллельной обработки полей контекста (структур)[спецкоманды ИУ];

• Эффективный контроль выхода за пределы массива или цикла при помощи

Токен

Дмиим

Пара токенов

Данное |

специальных команд АП;

• Эффективное освобождение ассоциативной памяти путем использования ключа с маской.

Структурная схема представляемой вычислительной системы с автоматическим распределением ресурсов приведена на рис. 3.

Работа данной структуры состоит в следующем:

- выходящие из исполнительных устройств данные (токены) содержат адрес узла, в который они должны поступить и где над ними должна выполниться соответствующая программа;

- АП объединяет данные, относящиеся к одной и той же программе узла (узлу графа), с соответствующим контекстом. Если парное данное на момент прихода токена в АП отсутствует, то происходит запись токена на свободное место в АП. Если же парное данное есть, происходит считывание этого данного и формирование пары данных в соответствии с правилами формирования пары, которая выдается на любое свободное ИУ. В случае множественного совпадения пришедшего токена с токенами, лежащими в АП, происходит формирование пар в соответствии с правилом использования кратности;

- выполнение задачи начинается с поступления токенов на входы ассоциативной памяти.

Рис 3 Структурная блок схема ВСАРР

В ВСАРР АП фактически берет на себя функции аппаратного управления вычислительным процессом.

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

АП работает с ключом токенов, который формируется в ИУ.

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

Особенностью ассоциативной памяти, используемой в данной вычислительной системе, является наличие как внешней (приходящей с токеном), так и внутренней (хранящейся вместе с токеном в АП) маски.

Ассоциативная память фактически выполняет многократные операции сравнения и условия.

Исполнительное устройство (ИУ) данной системы представляет собой функциональное устройство, предназначенное для выполнения программы узла над данными, поступающими на его вход.

Поскольку между сформированными парами токенов нет никакой «зависимости», в ИУ системы может происходить одновременная многопоточная параллельная обработка нескольких пар токенов (направлений) при наличии достаточного количества ресурсов. Вычислительные же блоки исполнительного устройства (арифметические и блоки специальных операций) используются коллективно всеми активными потоками команд, что позволяет повысить загруженность и эффективность работы ИУ в целом.

В результате рассмотренных преимуществ была выбрана многопоточная схема организации ИУ, разрабатываемой ВСАРР. На рис. 4. изображена общая структурная схема многопоточного исполнительного устройства (МИУ).

В МИУ обеспечивается параллельное независимое выполнение четырех пар токенов - потоков команд. Функциональные модули ИУ находятся в совместном использовании всех четырех направлений.

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

В набор функциональных устройств ИУ ВСАРР входят следующие:

- блок целочисленных операций;

- блок вещественных операций;

- блок специальных операций, выполняющий эффективную работу по формированию контекста.

Рис 4 Общая структурная схема многопоточного исполнительного устройства

Коммутатор токенов занимается распределением токенов по модулям ассоциативной памяти при помощи ХЭШ функции.

Коммутатор пар необходим для распределения готовых пар между свободными ИУ.

Программная поддержка модели вычислений

Для вычислительной системы с автоматическим распределением ресурсов был создан параллельный машинно-ориентированный язык высокого уровня, который предоставляет программисту удобные варианты работы с динамически формируемым контекстом.

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

Описание контекста является структурой, описанной вне узла, которая состоит из полей, возможно, в свою очередь, составных.

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

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

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

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

Блок аппаратной поддержки работы с динамически формируемым контекстом (специальных операций)

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

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

Точно так же как и контекст, данные могут представлять собой структуры. Вследствие этого блок специальных операций (БСО) предоставляет возможность работы не только с динамически формируемым контекстом, но и с данными.

С целью оптимизации работы с данными, представляемыми в виде структуры (контекст, разбитый на поля) было введено понятие «формат». Формат с одной стороны позволяет обращаться сразу ко многим полям и работать с ними в параллель, а с другой стороны позволяет указывать конкретный номер поля, с которым необходимо произвести действие. В вычислительной системе один и тот же контекст или данное может работать сразу в нескольких форматах, т.е. само данное не меняется, а структура обращения к нему претерпевает изменения. Алгоритм функционирования блока специальных операций

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

Структурная схема блока специальных операций приведена на рис. 5.

Рис. 5 Структурная схема блока специальных операций

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

Программная поддержка работы с динамически формируемым контекстом

В параллельном машинно-ориентированном языке высокого уровня ВСАРР непосредственная работа с динамически формируемым контекстом обеспечивается за счет операций с полями, работы с форматами и маскированием, конструкций, обеспечивающих формирование токена.

На рис. 6 приведен алгоритм работы транслятора при обработке динамически формируемого контекста в операциях посылки токена (наиболее часто используемый случай). В процессе трансляции происходит оптимизация программного кода, в частности используются команды, эффективно работающие с несколькими полями контекста.

формирование контекста

результируииций контекст

Рис 6 Алгоритм работы транслятора при обработке контекста

Аналогично осуществляется работа и с полями данных.

На рис. 7 приведен пример трансляции конструкций языка ВСАРР в ассемблерный код. Контекст разбит на 3 поля (к, Д в приведенном фрагменте программы осуществляется в первом случае одновременная работа по обнулению поля к, прибавлению единицы к а во втором - к присваивается 1, 1 прибавляется 1, а из 3 - вычитается I.

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

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

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

й (пЬб ап<164) Деп

вепс! О Ю ЬебВДи 1{0,1+1, еке

*етИ О ю ЬейЯ^Ь! г{ 1,1+1, },

Ю1 = 02 АШ64; К 1.279,

БСОМВ РО, г(Р_К], +(р_1),

_ЬЕРТЯЮНТ, М=0Ь 100000,

ДМР 1.296,

1.279 ЯСОМВ РО, +(Р_К, Р_1), ЧК^),

ЯЕАЕ>_ЬЕРТЯЮНТ, М=ОЫООООО,

Ь296,

а) б)

Рис 7 Пример трансляции конструкций на языке ВСАРР (а) в ассемблерный код (б), где команда ЯСОМВ - комбинированное формирование выходного состояния, которая параллельно работает с полями контекста Алгоритм функционирования многовходовых узлов

Предложена аппаратная поддержка и алгоритм функционирования многовходовых узлов в ВСАРР, которая предоставляет ряд преимуществ, как с точки зрения оптимизации работы системы в целом, так и с точки зрения разработки транслятора со стандартных языков высокого уровня. В частности можно ожидать:

- увеличения быстродействие определенных программ, в первую очередь высокопараллельных за счет сокращения количества обращений в АП;

- может быть уменьшен объем заполнения АП и возможность использования стандартных ОЗУ (более дешевых) для хранения данных «многовходовой пары»;

- повышение эффективность трансляции с языков высокого уровня (ЯВУ).

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

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

Макет вычислительной системы с автоматическим распределением ресурсов

Макет реализован на ПЛИС фирмы Altera с использованием САПР фирмы Altera MAX+PLUS II и Quartus, поскольку в первую очередь необходимо было не прибегая к чрезмерным затратам оценить новую архитектуру системы в кратчайшие сроки, проверить ее работоспособность. Разработка макета велась в соответствии с принципами нисходящего проектирования.

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

Конструктивно каадое из устройств располагалось на своей материнской плате. В свою очередь, на материнской плате находятся типовые элементы замены (ТЭЗ), который представляет из себя плату, на которой смонтирована микросхема ПЛИС и соответствующие интерфейсы, через которые осуществляется передача данных на следующих уровнях иерархии макета.

Исполнительное устройство разбито на следующие ТЭЗ: устройство управления операциями, буфер команд, блок специальных операций (работа с контекстом), устройство целочисленной арифметики и устройство вещественной арифметики.

В рамках создания макета, автором данной диссертационной работы, были разработаны и реализованы: буферная память ИУ, целочисленная арифметика ИУ, блок специальных операций ИУ макета ВСАРР.

Транслятор с машинно-ориентированного параллельного языка вычислительной системы с автоматическим распределением ресурсов

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

Общая схема трансляции с (ЯВУ) в машинные команды в настоящее время включает в себя промежуточный этап трансляции в ассемблерный код. Трансляция происходит в два этапа: сначала текст на ЯВУ при помощи транслятора ЯВУ транслируется в текст на языке Ассемблера, а затем компилятор с Ассемблера транслирует его в машинные.

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

Эффективность трансляции конструкций была подтверждена на задачах на инструментальном комплексе.

Программа «Синтез топологии сети»

Для подтверждения эффективности решения задач на архитектуре ВСАРР был решен ряд задач различных классов (сеточные, задачи линейной алгебры, комбинаторные и ряд других). Программы создавались на параллельном машинно-ориентированном ЯВУ ВСАРР, которые затем транслировались и запускались на поведенческой модели системы, а часть из них - и на макете.

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

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

Одной из задач, в создании которой автор принимал непосредственное участие, является задача «Синтез топологии сети».

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

Известно, что если количество узлов в сети больше либо равно 24, то топология такой сети ведет себя следующим образом, образуются две тройки (треугольника) из узлов, все остальные узлы связаны с обеими тройками. Узлы, которые могут образовать такие тройки, назовем узлами-кандидатами.

Имеются узлы сети количеством (п). Из этого количества выбирается заказчиком по определенным критериям некоторое количество узлов-кандидатов (т) и им же задается таблица стоимостей каналов между узлами размерностью п*ш, поскольку по условию задачи невозможно создание канала между двумя узлами, ни один из которых не является узлом-кандидатом. В результате необходимо получить топологию сети, а именно - координаты связи узлов друг с другом.

После того, как задача была написана на ЯВУ ВСАРР, она была оттранслирована и откомпилирована в машинные команды. Для запуска задачи на интерпретаторе была создана программа-клиент - для наглядного ввода данных, запуска задачи и вывода полученных результатов.

На финальной стадии отладки программы были получены реальные данные стоимости аренды каналов и соответственно список 45 узлов.

При запуске программы были получены следующие результаты:

- программа выполнялась в течении 52535 тактов;

- максимальное количество токенов в ассоциативной памяти составило порядка 175000;

- максимальная параллельность программы составила 480000;

- загрузка исполнительных устройств - близка к 100%. Тройки городов составили следующие города (рис. 8):

первая тройка - Санкт-Петербург, Ростов, Самара; вторая тройка - Екатеринбург, Новосибирск, Иркутск.

Полученные результаты свидетельствуют о высокой параллельности разработанного алгоритма и о высокой эффективности работы предлагаемой вычислительной системы.

Рис. 8. Результат работы задачи «Синтез топологии сети»

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

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

Дальнейшее развитие и исследование целесообразно вести в следующих направлениях:

- совершенствование транслятора и поведенческой модели системы;

- на основе результатов диссертационной работы провести модификацию команд, обеспечивающих работу с ДФК вычислений;

- аппаратная поддержка условных конструкций;

- внедрение многовходовых узлов в аппаратуру.

Основные результаты диссертационной работы

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

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

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

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

5. Введение данного блока в структуру исполнительных устройств повышает эффективность их работы, и всей системы в целом за счет эффективности разработанных алгоритмов и возможности параллельной работы с контекстом и данными.

6. Разработаны принципы аппаратной реализации блока, осуществляющего работу с динамически формируемым контекстом вычислений, на основе исследования возможностей современной элементной базы.

7. Для практической реализации предложенных аппаратных методов создан на ПЛИС макет блока, осуществляющего работу с ДФК вычислений.

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

9. Разработанные алгоритмы трансляции конструкций, отвечающих за работу с ДФК вычислений, вошли в созданный транслятор с параллельного машинно-ориентированного языка высокого уровня.

10. Для практической проверки созданных аппаратно-программных решений была реализована задача «Синтез топологии сетей», представляющая большой практический интерес.

11. Исследовано прохождение задачи «Синтез топологии сетей» на инструментальном комплексе системы, с целью выявления максимально достигнутого уровня параллелизма, динамики и эффективности ее прохождения.

12. Полученные результаты подтвердили эффективность созданных аппаратно-программных средств работы с динамически формируемым контекстом вычислений.

13.Предложен новый метод аппаратной реализации условных конструкций.

14. Предложен новый метод аппаратной поддержки работы с многовходовыми узлами.

Основные публикации по теме диссертации

1 Н Н. Левченко Динамическая обработка рекурсивных операций // "XXVI Гагаринские чтения". Тезисы докладов Всероссийской молодежной научной конференции. Том 2., - М.. Латмэс, 2000, с. 472.

2. НН Левченко Реализация цифровых устройств на ПЛИС // "XXVII Гагаринские чтения" Тезисы докладов Всероссийской молодежной научной конференции Том 5 , - М: Латмэс, 2001, с 65-66.

3 НН Левченко Блок работы с байтовыми структурами // "XXVII Гагаринские чтения" Тезисы докладов Всероссийской молодежной научной конференции Том 5 , -М." Латмэс, 2001, с. 66-67.

4 Н Н Левченко Реализация трансляции многовходовых узлов языка высокого уровня • ВМ нетрадиционной архитектуры потокового типа // С А. Лебедев и развитие отечественной вычислительной техники. - М МАИК, 2002 С 159-171.

5. H.H. Левченко. Особенности обработки узлов языка высокого уровня

вычислительной системы с автоматическим распределением ресурсов // ~

Интеллектуальные и многопроцессорные системы 2003. Материалы Международной научной конференции T 2. - Таганрог изд-во ТРТУ, 2003 С 58-60

6 Н Н Левченко Транслятор с машинно-ориентированного параллельного языка вычислительной системы с автоматическим распределением ресурсов // Системы и средства информатики Специальный выпуск Методы и средства разработки информационно-вычислительных систем и сетей Москва, ИЛИ РАН, 2004, стр 58

7 НН Левченко. Организация работ с циклами и массивами на вычислительной системе с автоматическим распределением ресурсов II Международная научно-практическая конференция «Искусственный интеллект - 2004 Интеллектуальные и многопроцессорные системы - 2004 пос Кацивели, Крым, 2004» // Материалы Международной научно-практической конференции, том 1, Таганрог - Донецк, 2004, стр 149.

8 Н Н Левченко, А С Окунев Аппаратно-программная реализация условных конструкций в вычислительной системе с автоматическим распределением ресурсов // Международная научно-практическая конференция «Искусственный интеллект -2004. Интеллектуальные и многопроцессорные системы — 2004 пос Кацивели, Крым, 2004» // Материалы Международной науч -практ. конф., т. I, Таганрог - Донецк, 2004, стр. 153

9 АС Окунев, НН Левченко Методы аппаратной реализации многовходовых узлов вычислительной системы с автоматическим распределением ресурсов // Научно-теоретический журнал «Искусственный интеллект» 3, 2004 1Ш111 «Наука i осв!та»,

2004, стр 149

10 НН Левченко Представление структур данных в вычислительной системе, управляемой потоком данных // Проблемы и методы информатики П научная сессия Института проблем информатики Российской академии наук, Москва, ИЛИ РАН, \

2005, стр. 201. <

11. НН Левченко, А.С Окунев Вопросы аппаратно-программной реализации условных

конструкций в вычислительной системе, управляемой потоком данных // Проблемы и

методы информатики П научная сессия Института проблем информатики Российской tf

академии наук, Москва, ИЛИ РАН, 2005, стр 203

12 НН Левченко, АС Окунев, ГО Чумаченко, И К Хайлов Варианты аппаратной поддержки многовходовых узлов в вычислительной системе с автоматическим распределением ресурсов // Проблемы и методы информатики II научная сессия Института проблем информатики Российской академии наук, Москва, ИЛИ РАН, 2005, стр. 206

Подписано к печати 25.05.2005. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Тираж 100 экз. Заказ № 112 Отпечатано в типографии ЦНИИатоминформа 127434, Москва, Дмитровское шоссе, 2

»1229

РНБ Русский фонд

2006-4 7519

Введение

Глава 1. Анализ вычислительных моделей управляемых потоком данных и их аппаратных реализаций

1.1. Статическая модель потока данных 13 1.1.1. MIT Static Dataflow Architecture

1.2. Динамическая модель потока данных

1.2.1. Манчестерская потоковая машина

1.2.2. Проект MIT Tagged-Token Dataflow Architecture

1.2.3. SIGMA

1.3. Модель вычислений потока данных с явным хранением токенов 24 1.3.1. Проект Monsoon

1.4. Гибридная модель вычислений потока данных

1.4.1. Threaded dataflow архитектура

1.4.1.1. Проект Epsilon

1.4.1.2. Проекты ЕМ-4 и ЕМ-Х

1.4.2. Крупно-зернистая архитектура потока данных (Large-grain dataflow) 32 1.4.2.1. Проект StarT

Выводы по первой главе

Глава 2. Исследование функционирования модели вычислений в вычислительной системе с автоматическим распределением ресурсов

2.1. Модель вычислений, управляемая потоком данных с произвольно изменяемым контекстом

2.2. Исследование организации и принципов функционирования предлагаемой вычислительной системы с автоматическим распределением ресурсов

2.2.1. Особенности, накладываемые аппаратной реализацией потоковой модели вычислений с произвольно изменяемым контекстом

2.2.2. Ассоциативная память

2.2.3. Исполнительное устройство

2.2.4. Коммутатор токенов

2.2.5. Коммутатор пар

2.3. Программная поддержка модели вычислений

2.4. Организация вычислений в вычислительной системе с автоматическим распределением ресурсов 2.4.1. Маскирование полей ключа токена

2.4.2. Реализация групповых операций над узлами

2.4.3. Преимущества использования произвольно изменяемого контекста при ^ реализации циклов и массивов на В САРР

2.5. Методика использования особенностей ВСАРР при программировании

2.5.1. «Пузырьковая сортировка»

Выводы по второй главе

Глава 3. Разработка алгоритмов функционирования аппаратно-программных средств работы с динамически формируемым контекстом вычислений

3.1. Блок специальных операций (аппаратной поддержки работы с динамически формируемым контекстом)

3.1.1. Алгоритм функционирования блока специальных операций

3.2. Программная поддержка работы с произвольно изменяемым контекстом

3.3. Алгоритм функционирования токенов, обеспечивающих аппаратную ^ ^ поддержку выполнения условных конструкций

3.4. Алгоритм функционирования многовходовых узлов 114 Выводы по третье главе

Глава 4. Создание макета исполнительного устройства системы с автоматическим распределением ресурсов. Практическая реализация программной поддержки работы с произвольно изменяемым контекстом. Создание параллельной программы для ВСАРР

4.1. Обоснование выбора ПЛИС в качестве элементной базы макета

4.2. Макет вычислительной системы с автоматическим распределением ресурсов

4.3. Разработка макета ВСАРР 125 4.3.1. Краткая характеристика языков проектирования электронных средств

4.4. Разработка блока специальных операций исполнительного устройства

4.5. Программная поддержка работы с произвольно изменяемым контекстом (транслятор с машинно-ориентированного параллельного языка вычислительной 141 системы с автоматическим распределением ресурсов)

4.6. Программа «Синтез топологии сети» 147 Выводы по четвертой главе 158 Заключение 159 Литература 161 Перечень сокращений 167 Приложение

Актуальность темы

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

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

Основным методом увеличения производительности вычислительных средств становится метод распараллеливания вычислительных процессов. На математическом уровне задача распараллеливания вычислительного процесса успешно решается.

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

- необходимость синхронизации вычислительных процессов по данным;

- потеря времени на обмен данными между процессорами.

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

В вычислительных системах, построенных на традиционных фон-неймановских принципах, данные задачи на текущий момент не решены.

В настоящее время в отделе «Построения информационно-вычислительных систем высокого параллелизма» Института проблем информатики Российской Академии Наук разработаны новые принципы организации вычислительного процесса и на их основе разработана вычислительная система, использующая модель вычислений, управляемую потоком данных с динамически формируемым контекстом вычислений. Создан инструментальный комплекс и макет системы.

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

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

Цель и задачи работы

Настоящая диссертационная работа посвящена созданию аппаратно-программных средств работы с динамически формируемым контекстом вычислений в системе с автоматическим распределением ресурсов, разработке принципов функционирования и структуры, отвечающих за это блоков системы, методов их аппаратной реализации, разработке программной поддержки конструкций, обеспечивающих работу с динамически формируемым контекстом и их программной реализации. Для достижения поставленной цели в работе поставлены и решаются следующие основные задачи:

1. Анализ состояния и развития существующих потоковых моделей вычислений и их аппаратных реализаций.

2. Анализ потоковой модели вычислений с динамически формируемым контекстом и исследование ее аппаратной реализации - вычислительной системы с автоматическим распределением ресурсов.

3. Разработка команд, обеспечивающих работу с динамически формируемым контекстом вычислений, которые входят в систему команд.

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

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

6. Создание программ, имеющих практическую ценность, а также их исследование с целью выявления максимального параллелизма и эффективности их выполнения.

7. Осуществление практической реализации предложенных методов на макете исполнительного устройства.

Объект и предмет исследования

Объектом исследования является вычислительная система новой нетрадиционной архитектуры - вычислительная система с автоматическим распределением ресурсов (ВСАРР). Предметом исследования являются созданные аппаратно-программные средства работы с динамически формируемым контекстом вычислений, что позволяет значительно повысить эффективность организации параллельных процессов и производительность в ВСАРР; разработанные алгоритмы и программы, их исследование на программной модели ВСАРР - инструментальном комплексе, и на аппаратной модели ВСАРР - макете; решение задач на инструментальном комплексе с целью проверки эффективности разработанных методов.

Методы исследования

Исследования проводились с использованием теории параллельных вычислений, теории высокопроизводительных вычислений, теории построения трансляторов, теории инструментальных комплексов, теории проектирования ЭВМ и методик проектирования сложных вычислительных комплексов с применением систем автоматизированного проектирования. Аппаратная реализация макета исполнительных устройств велась в соответствии с принципами нисходящего проектирования с использованием объектно-ориентированного подхода.

Научная новизна

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

1. разработана часть системы команд, отвечающая за работу с динамически формируемым контекстом, и разработаны эффективные алгоритмы выполнения команд;

2. аппаратно реализован блок исполнительного устройства вычислительной системы с автоматическим распределением ресурсов, осуществляющий выполнение системы команд работы с динамически формируемым контекстом;

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

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

5. исследовано прохождение ряда программ на инструментальном комплексе и на макете, подтвердившее правильность самой концепции вычислительной модели и реализуемой на ее основе архитектуры, а также выявившее предельный параллелизм и эффективность выполнения программ;

6. предложен новый метод реализации условных конструкций в вычислительной системе с автоматическим распределением ресурсов, позволяющий оптимизировать выполнение задачи;

7. предложен новый метод реализации многовходовых узлов в ВСАРР.

Практическая значимость

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

2. Разработанные алгоритмы трансляции конструкций параллельного машинно-ориентированного языка высокого уровня, обеспечивающих работу с динамически формируемым контекстом (ДФК) вычислений, позволяют повысить эффективность программирования и могут быть использованы при создании трансляторов со стандартных языков высокого уровня. Реализованные алгоритмы трансляции конструкций, обеспечивающих работы с ДФК вычислений вошли в состав созданного транслятора с параллельного машинно-ориентированного языка высокого уровня.

3. На примере созданной программы «Синтез топологии сетей» показана эффективность работы предлагаемой архитектуры при решении задач, представляющих практический интерес, что позволяет судить о правильности, принятых аппаратно-программных решений, обеспечивающих поддержку работы с динамически формируемым контекстом вычислений.

4. Предложены новые методы аппаратной реализации условных конструкций и многовходовых узлов.

Основные положения, которые выносятся на защиту:

1. Анализ архитектуры вычислительной системы с автоматическим распределением ресурсов, позволил выявить возможности повышения производительности системы.

2. Разработанная система команд и алгоритмы выполнения команд, позволяют обеспечить работу с динамически формируемым контекстом вычислений.

3. Разработанный блок, входящий в состав исполнительного устройства вычислительной системы с автоматическим распределением ресурсов, осуществляет работу с динамически формируемым контекстом вычислений.

4. Разработанные программные средства трансляции конструкций параллельного машинно-ориентированного языка высокого уровня, обеспечивают работу с динамически формируемым контекстом.

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

6. Создана программа "Синтез топологии сетей", которая представляет практический интерес, проведена оценка ее максимального распараллеливания и эффективности выполнения на инструментальном комплексе.

7. Предложены новые алгоритмы аппаратной поддержки выполнения условных конструкций и многовходовых узлов.

Реализация результатов работы

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

Апробация результатов

Основные положения и результаты работы докладывались и обсуждались на научных семинарах в ИПИ РАН 2001-2005 гг., а также на ряде международных и всероссийских конференций в период с 2000 года по 2005 года: на международных молодежных научных конференциях "XXVI Гагаринские чтения" (Москва, 2000) и "XXVII Гагаринские чтения" (Москва, 2001); на международной научной конференции "С.А. Лебедев и развитие отечественной вычислительной техники" (Москва, 2002); на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС'2003» (пос. Дивноморское, 2003), на международной научно-практической конференции «Искусственный интеллект - 2004. Интеллектуальные и многопроцессорные системы - 2004» (пос. Кацивели, Крым, 2004), на «II Научной сессии Института проблем информатики Российской академии наук: Проблемы и методы информатики» (Москва, 2005).

Исследование разработанных методов аппаратной и программной поддержки работы с динамически формируемым контекстом проводилось в Институте проблем информатики РАН на инструментальном комплексе и при отладке макета ВСАРР.

Структура диссертации.

Диссертационная работа состоит из введения, четырех глав, списка литературы из 84 наименований и одного приложения. Работа изложена на 181 странице машинописного текста, из них основного текста 168 страниц и 13 страниц приложения, работа включает 70 рисунков и 6 таблиц в основной части, приложения содержат 16 рисунков.

Основные результаты диссертационной работы.

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

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

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

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

5. Введение данного блока в структуру исполнительных устройств повышает эффективность их работы, и всей системы в целом за счет эффективности разработанных алгоритмов и возможности параллельной работы с контекстом и данными.

6. Разработаны принципы аппаратной реализации блока, осуществляющего работу с динамически формируемым контекстом вычислений, на основе исследования возможностей современной элементной базы.

7. Для практической реализации предложенных аппаратных методов создан на ПЛИС макет блока, осуществляющего работу с ДФК вычислений.

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

9. Разработанные алгоритмы трансляции конструкций, отвечающих за работу с ДФК вычислений, вошли в созданный транслятор с параллельного машинно-ориентированного языка высокого уровня.

10. Для практической проверки созданных аппаратно-программных решений была реализована задача «Синтез топологии сетей», представляющая большой практический интерес.

11. Исследовано прохождение задачи «Синтез топологии сетей» на инструментальном комплексе системы, с целью выявления максимально достигнутого уровня параллелизма, динамики и эффективности ее прохождения.

12. Полученные результаты подтвердили эффективность созданных аппаратно-программных средств работы с динамически формируемым контекстом вычислений.

13. Предложен новый метод аппаратной реализации условных конструкций.

14. Предложен новый метод аппаратной поддержки работы с многовходовыми узлами.

Заключение

1. Бурцев B.C. Новые принципы организации вычислительных процессов высокого параллелизма // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы — 2003». Т.1. Таганрог: Изд-во ТРТУ, 2003.

2. Митрофанов В., Слуцкин А., Ларионов К., Эйсымонт Л. Направления развития отечественных высокопроизводительных систем//Открытые системы. 2003. № 5.

3. Saphir W., Woo A., Yaroww М. The NAS Parallel Benchmark 2.1 Results//Report NAS-96-010, August 1996.

4. Michael L. Dertouzos. The Future of Computing//Scientific American. 1999. August 19.

5. Бурцев B.C. Перспективы развития вычислительной техники//Сб. статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. МВК Эльбрус». М., 1998.

6. Silc J., Robic В. Did Processor Architecture Make the Best of Dataflow?//PDPTA'2000.

7. Березко A.M. Новые концепции в архитектуре потоковых машин с тегированием данных. Отчет отдела системного программирования ВЦКП РАН. М., 1991.

8. Dennis J., Misunas D. A preliminary Architecture for Basic Data-Flow Processor//Project MAC, MIT, Houston, TX. 1975. Jan. P. 126-132.

9. Dennis J.B. The Evolution of «Static» Data-Flow Architecture//Advanced Topics in Dataflow Computing, ed. Bic L. and Gaudiot J.-L., Prentice Hall, 1991.

10. Gravlen 0. «The Evolution of Dataflow Computers Project Paper for 45214 Computer Architecture». University of Trondheim, 1994.

11. Arvind, Dahbura A.T., Caro A. Computer Architecture Research and the Real World//Computation Structures Group Memo 397, MIT Laboratory for Computer Science, Cambridge, MA, 1997, April 23.

12. Silc J., Robic В., Ungerer T. Asynchrony in parallel computing: From dataflow to multithreading//Parallel and Distributed Computing Practices. 1998. 1(1): 3-30.

13. Watson I., Gurd J.R. A prototype data flow computer with token labeling//Proc. National Сотр. Conf., Jun. 1979. P. 623-628.

14. Arvind, Nikhil R.S. Executing a program on the MIT tagged-token dataflow architecture//Lect. Notes Comput. Sc. 259 (1987). P. 1-29.

15. Barrington D.A., Culler D.E. DATAFLOW ARCHITECTURES//MIT Laboratory for Computer Science, 1986, February 2.

16. Gurd J. R., Kirkham С. C., Watson I. The Manchester Prototype Dataflow Computer//In S. S. Thakkar, editor, Selected Reprints on Dataflow and Reduction Architectures. IEEE Computer Society Press, Los Alamitos, CA, 1987. P. 111-129.

17. Березко A.M. Принципы действия и архитектура манчестерской потоковой машины//Отчет по теме «Анализ современного состояния архитектур вычислительных машин потока данных». М., 1988.

18. Gurd J.R. The Manchester dataflow machine//Future Generations Computer Systems 1. 1985. P. 201-212.

19. Feo J.T., Cann D.C., Oldehoeft R.R. A Report on the SISAL Language Project//Journal of Parallel and Distributed Computing, 10:349-366. 1990. Dec.

20. Patnaik L.M., Govindaraian R., Ramadoss N.S. Design and performance evaluation of EXMAN: Extended MANchester data flow computer/ЛЕЕЕ Trans. Computers C-35. 1986.P. 229 -244.

21. Arvind, Thomas R.E. I-structures: An efficient data type for parallel machines//Tech. Rep. TM 178, Computat. Structures Group, MIT Lab. for Comput. Sci., 545, Technology Square, Cambrige, MA 02139. 1980. Sept.

22. Arvind, Rishiyur S. Nikhil, Keshav K. Pingali. I-structures: data structures for parallel computing//ACM Transaction on Programming Language and Systems. 1989. October. V. 11, no. 4.

23. Arvind, Nikhil R.S., Executing a program on the MIT Tagged-Token Dataflow Architecture//IEEE Transactions of computers. 1990. March. V. 39, no. 3.

24. Arvind, Gostelow K.P., Plouffe W. An Asynchronous Programming Language and Computing Machine//Department of Information and Computer Science Technical Report 114a, University of California, Irvine. 1978. Dec.

25. Null L., Lobur J. The essentials of computer organization and architecture//Jones and Bartlett Publishers, Inc. 2003.

26. Shimada Т., Hiraki K., Sekiguchi S. A Dataflow Supercomputer for Scientific Computations: The SIGMA-1 System//Translated into English by Eoyang C, and published in The Institute for Supercomputing Research Vector Register, 11.15.1988. P. 3-9.

27. Culler D., Papadopoulos G. The Explicit Token Store//Journal of parallel and distributed computing. 1990. № 10. P. 289-308.

28. Papadopoulos M., Culler D. Monsoon: an Explicit Token-Store Architecture//Proc. of 17th Intl. Symposium on Computer Architecture (ISCA-17), May 1990. P. 82-91.

29. Robic В., Silc J., Ungerer T. Beyond dataflow//J. Computing and Information Technology, 8(2):89-101. 2000.

30. Papadopoulos G.M., Traub K.R. Multithreading: A revisionist view of dataflow architectures/An Proceedings of the 18th Annual International Symposium on Computer

31. Architecture//1EEE Computer Society. 1991. P. 342-351.

32. Iannucci R. Toward a Dataflow/von Neumann Hybrid Architecture/Лп 15th Annual International Symposium on Computer architecture. 1988. P. 131-140.

33. Traub K.R., Popadopoulos G.M., Beckerle M.J., Hicks J.E., Young J. Overview of the Monsoon Project//Proceedings of the 1991 IEEE International Conference on Computer Design, Cambridge, MA. 1991. Oct.

34. David E. Culler, Klaus E. Schauser, and Thorsten von Eicken. Two Fundamental Limits on Dataflow Multiprocessing// IFIP WG 10-3 Parallel Architectures and Compilation Techniques, Jan 1992.

35. Grafe V.G., Hoch J.E. The Epsilon-2 Multiprocessor System//Journal of Parallel and Distributed Computing, 10:309-318.1990. Dec.

36. Boon Seong Ang. Efficient Implementation of Sequential Loops in Dataflow Computation//Appeared in the Proceedings of the 1993 FPCA, Copenhagen, Denmark. P. 169-178.

37. Finkel R.A. ADVANCED PROGRAMMING LANGUAGE DESIGN. Addison-Wesley Publishing Company, 1996.

38. Culler D.E. Resource Management for the Tagged Token Dataflow Architecture//MIT. 1980. Jan.

39. Nikhil R.S. Dataflow Programming Languages//The 13th IMACS World Congress on Computation and Applied Mathematics, Trinity College, Dublin, Ireland, July 22-26, 1991.

40. Toshitsugu Yuba, Toshio Shimada, Yoshinori Yamaguchi, Kei Hiraki, Shuichi Sakai. Dataflow computer development in Japan//4th International Conference on Supercomputing, Amsterdam, The Netherlands, 1990.

41. Hiroshi Nagase, Masakuni Kameya, Takashi Kawanami, Tomoki Shiono. Dataflow Computer which Accelerates Execution of Sequential Programs by Firing Instruction Precedently//System and Computers in Japan. 2002. V. 33, no. 9. P. 68-77.

42. Yuba Toshitsugu. Research and Development Efforts on Dataflow Computer Architecture in Japan//Journal of Information Processing Abstract. 2002. V. 09, no. 02.

43. Yamaguchi,Y. SakaiS. An Architectural Design of a Highly Parallel Dataflow Machine//To appear in IFIP'89. 1989.

44. Sakai Shuichi, Yamaguchi Yoshinori, Hiraki Kei, Kodama Yuetsu, Yuba Toshitsugu. Design of the Dataflow Single-Chip Processor EMC-R//Journal of Information Processing Abstract. V. 13, no. 02-008.

45. Kahaner D.K. Parallel processing research in Japan//Supplement. 1991. May.

46. Herath J., Yamaguchi Y., Saito N., Yuba T. Dataflow Computing Models, Languages, and Machines for Intelligence Computations/ЛЕЕЕ Transactions on Software Engineering. 1988. Dec. V. 14, no. 12.

47. Arvind, Stephen Brobst. The evolution of dataflow architectures: from static dataflow to P-RISC//International Journal of High Speed Computing. 1993. V. 5, no. 2. P. 125-153.

48. Корнеев В., Киселев А. Современные микропроцессоры/^ изд. С-Пб.: БХВ-Петербург, 2003.

49. Beckerle M.J. Overview of the START (*T) multithreaded computer//Proc. COMPCON'93, 1993. P. 148-156.

50. Veen A.H. Dataflow machine architecture//ACM Computing Surveys (CSUR). 1986. Dec. V. 18, Issue 4.

51. Dennis J.B. Data Flow Supercomputers//Computer. 1980. Nov. V. 13, no. 11. P. 48-56.

52. Jagannathan R., Dataflow Models//Parallei and Distributed Computing Handbook: Editor Zomaya E.Y., McGraw-Hill, 1996.

53. Silc J., Robic В., Ungerer T. Processor Architecture: From Dataflow to Superscalar and Beyond. Springer-Verlag, Berlin, New York, 1999.

54. Ben Lee, Hurson A. R. Dataflow Architectures and Multithreading//Computer. 1994. Aug. V. 27, no. 8. P. 27-39.

55. Wesley M. Johnston, J.R. Paul Hanna, Richard J. Millar. Advances in dataflow programming languages//ACM Computing Surveys (CSUR). 2004. March. V. 36, Issue 1.

56. Herath J., Yamaguchi Y., Saito N., Yuba T. Dataflow Computing Models, Languages, and Machines for Intelligence Computations/ЛЕЕЕ Transactions on Software Engineering. 1988. Dec. V. 14, no. 12.

57. Бурцев B.C. О необходимости создания суперЭВМ в России//Сб. статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ», М., 1997.

58. Kaufmann М. Computer Architecture. A Quantitative Approach, 3rd Edition, 2002.

59. W. Ackerman. Data flow languages. IEEE Comput. 15,2,15—25,1982.

60. Бурцев B.C., «Перспективы развития вычислительной техники», в сб.статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. МВК Эльбрус», Москва, 1998.

61. Бурцев B.C., «Тенденции развития высокопроизводительных систем имногопроцессорные вычислительные комплексы», в сб.статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. МВК Эльбрус», Москва, 1998.

62. Левченко Н.Н. Динамическая обработка рекурсивных операций/ZXXVI Гагаринские чтения. Тезисы докладов Всероссийской молодежной научной конференции. Том 2. Секция «Микропроцессорные системы в авиационной и космической технике». М.: Латмэс, 2000. С. 472.

63. Левченко Н.Н. Реализация цифровых устройств на ПЛИС//ХХУН Гагаринские чтения. Тезисы докладов Всероссийской молодежной научной конференции. Том 5. Секция «Микропроцессорные системы в авиационной и космической технике». М.: Латмэс, 2001. С. 65-66.

64. Левченко Н.Н. Блок работы с байтовыми структурами //XXVII Гагаринские чтения. Тезисы докладов Всероссийской молодежной научной конференции. Там же. С. 66-67.

65. Левченко Н.Н. Реализация трансляции многовходовых узлов языка высокого уровня ВМ нетрадиционной архитектуры потокового типа//С.А. Лебедев и развитие отечественной вычислительной техники. М.: МАИК, 2002. С. 159-171.

66. Левченко Н.Н., Окунев А.С. Аппаратно-программная реализация условных конструкций в вычислительной системе с автоматическим распределением ресурсов. Там же. С. 153.

67. Окунев А.С., Левченко Н.Н. Методы аппаратной реализации многовходовых узлов вычислительной системы с автоматическим распределением ресурсов//Научно-теоретический журнал «Искусственный интеллект» 1ПШ1 «Наука i освгга». 2004. № 3. С. 149.

68. Левченко Н.Н. Представление структур данных в вычислительной системе, управляемой потоком данных//Проблемы и методы информатики: II научная сессия Института проблем информатики Российской академии наук. Тезисы докладов. М., ИПИ РАН, 2005. С. 201.

69. Кнут Д.Е. Искусство программирования. Т. 3. Сортировка и поиск. 2-е изд. Вильяме, Addison Wesley Longman, 2000.

70. Тексейра С., Пачеко К. Borland Delphi 6. Руководство разработчика. Вильяме, Москва, 2002.

71. Угрюмов Е.П. Цифровая схемотехника. 2-е изд., перераб. и доп., BHV, 2004.

72. Комолов Д.А. и др. САПР фирмы Altera МАХ + Plus II и Quartus 11//РадиоСофт. 2002.

73. Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Вильяме, 2003.

74. Вишневский В.М. Теоретические основы проектирования компьютерных сетей//Техносфера. 2003.

75. Стешенко В.Б. «ПЛИС фирмы ALTERA: проектирование устройств обработки сигналов.», М.: Додэка, 2000.

76. Altera Corporation. APEX 20К Programmable Logic Device Family. Data Sheet. August 1999. ver.2.02.

77. Шабанов Б.М., Яицков А.С. VHDL — язык описания аппаратуры. Учебное пособие. Москва, МИЭТ, 2003.

78. Антонов А.П. «Язык описания цифровых устройств AlteraHDL. Практический курс», -М.: ИП РадиоСофт, 2001.1671. Перечень сокращений1. AHDL Altera HDL

79. ANSI American National Standards Institute

80. CPLD Complex Programmable Logic Device

81. EDIF Electronic Design Interchange Format

82. EXMAN Extended Manchester Dataflow Computer

83. FPGA Field Programmable Gate Array1. GDF Graphic Design File

84. HDL Hardware Description Language

85. HTMT Hybrid Technology Multithreaded Architecture гибриднотехнологическая многопоточная архитектура IEEE Institute of Electrical and Electronic Engineers

86. M Library of Parameterized Modules Библиотеки параметризированныхмодулей

87. MAX+PLUS Multiple Array MatriX Programmable Logic User System — «пользовательекая система программирования логики упорядоченных структур» MDFM Manchester Data-Flow Machine

88. MIT Массачусетский Технологический Институт

89. MIT TTDA MIT Tagged-Token Dataflow Machine

90. MPP Massively Parallel Processor — процессоры с массовым параллелизмом

91. МТА MultiThreading Architecture многопоточная архитектура

92. RAM (ОЗУ) Оперативное запоминающее устройство RISC Reduced Instruction Set Computing (technology) вычисления ссокращённым набором команд ROM (ПЗУ) постоянное запоминающее устройство SDF Signal Design File1. TDF Text Design File

93. TPU Thread Processor Unit однонитевой процессор

94. Арасш Адрес памяти расширения

95. Асл Адрес следующей команды1. АФ Ассоциативный Формат

96. БВО Блок Вещественных Операций (операций над с плавающей точкой)1. БГП Буфер Готовых Пар1. БД База Данных1. БЗНЦ Без знаковое Целое

97. БИС Большие Интегральные Схемы1. БК Буфер Команд

98. БРГП Буфер Распределитель Готовых Пар

99. БСО Блок Специальных Операций

100. БЦО Блок Целочисленных Операций1. ВМ Вычислительная Машина

101. ВСАРР Вычислительная Система с Автоматическим Распределением Ресурсов1. ВТ Вычислительная Техника1. ДК Дешифратор Команд

102. ДФК Динамически Формируемый Контекст1. ЗНЦ Знаковое Целое1. ИС Интегральная Схема

103. ИУ Исполнительное Устройство

104. КМАП Коммутатор Модулей Ассоциативной Памяти1. КОП Код Операции1. КУ Код Условиялэ Логический Элемент

105. МАП Модуль Ассоциативной Памяти

106. МИУ Многопоточное Исполнительное Устройство

107. МПМ Манчестерская Потоковая Машина

108. ОЗУ Оперативное Запоминающее Устройство1. ОП Оперативная Память1. ОС Операционная Система1. ПК Память Команд1. ПКон Память Констант

109. ПЛИС Программируемые Логические Интегральные Схемы

110. ПО Программное Обеспечение1. Прасш Память расширения1. ПЭ Процессорный Элемент1. РК Регистр Команд

111. РОН Регистр Общего Назначения

112. САПР Система Автоматизированного Проектирования

113. СБИС Сверхбольшие Интегральные Схемы

114. ТЭЗ Типовой Элемент Замены1. УП Указатель Полей1. УУ Устройство Управления

115. УУОП Устройство Управления Операциями

116. ФУ Функциональное Устройство1. ЦП Центральный Процессор1. ЦУ Цифровые Устройства1. ЯВУ язык высокого уровня