Содержание к диссертации
Введение
ГЛАВА 1. Обзор вычислительных систем нетрадиционной архитектуры, вычислитешэныи процесс в которых управляется потоком данных 12
1.1. Проблемы повышения производительности в вычислительных системах массового параллелизма 12
1.2. Обзор архитектур, которые реализуют модель вычислений, управляемых потоком данных 14
1.3. Проблема переполнения памяти токенов в вычислительных системах, управляемых потоком данных и способы ее решения 23
1.3.1. Основные причины переполнения памяти совпадений 24
1.3.2. Методы преодоления проблемы переполнения памяти совпадений в предыдущих реализациях вычислительных систем, управляемых потоком данных...25
1.3.2.1. Принципы управления распределением ресурса памяти в проекте МГТ TTDA 25
1.3.2.2, Методы ограничения параллелизма программ в проекте MDFM 33
Выводы к первой главе 38
ГЛАВА 2. Разработка методов преодоления переполнения апвсарр и реализация виртуальной памяти токенов 40
2.1. Архитектура вычислительной системы с автоматическим распределением ресурсов 40
2.1.1. Представление информации в ВСАРР , 41
2.1.2. Общая структура ВСАРР , 45
2.1.3. Функционирование отдельных устройств ВСАРР 46
2.2. Исследование проблемы переполнения ассоциативной памяти ВСАРР и методы ее решения 49
2.2.1. Основные причины переполнения ассоциативной памяти 50
2.2.2, Методы решения проблемы переполнения ассоциативной памяти ВСАРР 51
2.3. Построение иерархии памяти ВСАРР 51
2.3.1. Использование буферов токснов и пар в ВСАРР 51
2.3.2. Блокировка вычислительного процесса в ВСАРР 52
2.3.2.1, Блокировка вычислительного процесса в результате переполнения буферов токенов и пар 52
2.3.2.2. Блокировка вычислительного процесса в результате переполнения модулей ассоциативной памяти , 55
2.3.3. Построение иерархии памяти ВСАРР 55
2.3.4. Статистика 57
2.4. Принципы организации виртуальной памяти токснов и аппаратная поддержка многозадачного режима работы системы 59
2.4.1. Механизм реализации виртуальной памяти токенов 60
2.4.2, Аппаратная поддержка многозадачного режима работы системы 63
2.4.2.1. Многозадачный режим работы без подзадач 67
2.4.2.2. Многозадачный режим работы с включением номера подзадачи в ключ 68
2.4.2.3. Многозадачный режим работы с использованием областей 69
2.4.2.4. Алгоритм работы ЦУУП по откачке и подкачке токенов 71
2.5. Аппаратно-программные методы регулирования параллелизма в ВСАРР 73
Выводы ко второй главе 76
ГЛАВА 3. Алгоритмы выполнения команд управления задачами и работы цууп, реализующих многозадачный режим работы системы и виртуальную память токенов 78
3.1. Специальные команды управления задачами 78
3.1.1. Описание команд управления задачами и их классификация 78
3.1.2. Алгоритмы выполнения команд управления задачами 81
3.1.3. Форматы дополнительных токенов, обеспечивающих выполнение команд управления 97
3.2. Структура и режимы функционирования ЦУУП 99
3.2.1. Основные функциональные блоки ЦУУП 102
3.2.2. Взаимодействие ЦУУП с адаптером ООЗУ и модулями АЛ ,...105
3.2.3. Основные режимы работы ЦУУП ...109
3.3. Методы аппаратной поддержки программных конструкций и специальных
режимов работы системы 116
3.3.1. Аппаратная поддержка механизма подсчета глобальной кратности 116
3.3.2. Аппаратная поддержка многовходовых узлов 118
3.3.3. Реализации механизма восстановления системы после сбоя или отказа 121
Выводы к третьей главе 125
ГЛАВА 4. Исследование функционирования вычислительной системы на инструментальном испытательном комплексе ВСАРР 126
4.1. Имитационная модель системы 126
4.2. Программная блочно-регистровая модель системы 127
4.3. Проведение экспериментов на инструментальном испытательном комплексе с использованием разработанных специальных команд управления 129
4.3.1. Описание задач, на которых проводились исследования .,..130
4.3.2. Результаты исследований прохождения задач в различных режимах запуска. 135
4.4. Макет вычислительной системы с автоматическим распределением ресурсов.139
4.4.1. Структура макета ВСАРР и конструктивные решения для него 140
4.4.2. Перспективы развития макета ВСАРР 143
Выводы к четвертой главе 145
Заключение 146
Литература
- Обзор архитектур, которые реализуют модель вычислений, управляемых потоком данных
- Исследование проблемы переполнения ассоциативной памяти ВСАРР и методы ее решения
- Форматы дополнительных токенов, обеспечивающих выполнение команд управления
- Проведение экспериментов на инструментальном испытательном комплексе с использованием разработанных специальных команд управления
Введение к работе
Актуальность темы диссертации
Существуют фундаментальные задачи, имеющие большое научное и практическое значение, от решения которых зависит развитие многих важных направлений науки и техники. К ним относятся: задачи ядерной физики, моделирование ядерных процессов; задачи гидродинамики и газодинамики; задачи генной инженерии; задачи прогноза природных геофизических явлений и экологических изменений в окружающей среде; задачи проектирования сверхсложных объектов и комплексов; задачи исследования космоса и другие.
Для решения этих задач требуются суперкомпьютеры с реальной производительностью 1012-1016 операпий в секунду. Причем с каждым годом требования, предъявляемые к вычислительной технике, на которой решаются подобные задачи, возрастают [8,12,16].
Одним из основных способов увеличения реальной производительности вычислительных систем является метод распараллеливания вычислений. Ведущие позиции в области параллельных вычислительных систем в настоящее время занимают компьютеры, построенные по фон-неймановской архитектуре. При решении современных фундаментальных задач такие параллельные вычислительные системы имеют низкий коэффициент загрузки процессоров [7]. Существует несколько причин, но которым процессоры данных вычислительных систем работают недостаточно эффективно, а именно:
- необходимость синхронизировать параллельные вычислительные процессы,
работающие с общими данными;
- временные потери, возникающие при обмене данными между процессорами.
В результате реальная производительность параллельных вычислительных
систем практически на порядок отличается от пиковой и, поэтому, в настоящее время актуальна задача создания системы, которая обеспечивала бы на аппаратном уровне предельное распараллеливание вычислительных процессов и высокую эффективность использования аппаратных средств. С этой целью исследуются различные модели вычислительных систем: реляционные, рекурсивные, асинхронные, функциональные, потоковые и другие [7,18].
В Англии, США и Японии проводились исследования архитектур, в которых вычислительный процесс управляется потоком данных [35,40,41,46,59]. Особенностью таких архитектур является возможность одновременного выполнения всех операций, для которых в данный момент готовы операнды, что обеспечивает предельную степень параллелизма, имеющегося у конкретной задачи. Однако, результаты данных исследований, не нашли широкого применения. Одной из причин являлось то, что не были решены вопросы создания виртуальной памяти и поддержки работы в многозадачном режиме [45].
В отделе «Проблем построения информационно-вычислительных систем высокого параллелизма» Института проблем информатики Российской академии
наук под руководством академика [B.C. Бурцева] разработаны новые принципы организации вычислительного процесса и па их основе спроектирована вычислительная система с автоматическим распределением ресурсов, использующая модель вычислений, управляемых потоком данных с динамически формируемым контекстом вычислений. В настоящее время работа над данным проектом продолжается [7].
Для этой системы решена задача максимального распараллеливания вычислительного процесса. Однако для нее актуальным является создание аппаратно-программных средств управления задачами и организация виртуальной памяти. В данной диссертационной работе решаются проблемы, связанные с необходимостью обеспечить возможность выполнения задач (работающих как в однозадачном, так и в многозадачном режимах), для которых требуется объем памяти совпадений (ассоциативной памяти), превышающий реальный объем этой памяти в системе. Цель и задачи работы
Настоящая диссертационная работа посвящена созданию аппаратно-программных средств управления задачами и организации виртуальной памяти в вычислительной системе с автоматическим распределением ресурсов (ВСАРР).
Для достижения поставленной цели в работе решаются следующие основные задачи:
1. Анализ состояния реализованных ранее проектов вычислительных систем с управлением потоком данных с точки зрения выполнения задач, требующих
объема памяти совпадений, превышающего реальный объем этой памяти в системе (проблема создания виртуальной памяти), и решения проблем управления параллелизмом задач.
Разработка и реализация аппаратно-программных средств управления задачами и метода организации виртуальной памяти в вычислительной системе с автоматическим распределением ресурсов.
Разработка системы специальных команд управления задачами, обеспечивающих эффективную загрузку ресурсов системы, осуществляющих контроль над прохождением задач, поддерживающих многозадачный режим и связь ВСАРР с операционной системой, и алгоритмов их выполнения.
Разработка структуры и принципов аппаратной реализации центрального устройства управления памятью, обеспечивающего выполнение специальных команд управления задачами и организацию виртуальной памяти.
Исследование предложенных методов управления задачами, методов регулирования параллелизма задач на инструментальном испытательном комплексе вычислительной системы с автоматическим распределением ресурсов (на различных классах задач) и анализ данных, полученных в результате исследования.
Объект и предмет исследования
Объектом исследования является вычислительная система новой нетрадиционной архитектуры - вычислительная система с автоматическим распределением ресурсов. Предметом исследования являются аппаратно-программные средства управления задачами и организация виртуальной памяти ВСАРР. Методы исследования
Исследования проводились с использованием основных положений теории проектирования компьютерных систем, теории параллельных вычислений, теории высокопроизводительных вычислений и методик проектирования сложных вычислительных комплексов с применением систем автоматизированного проектирования. Аппаратная реализация макета ВСАРР велась с применением
7 принципов нисходящего проектирования электронных систем с использованием объектно-ориентированного подхода. Научная новизна
Впервые разработаны аппаратно-программные средства управления задачами, создан метод организации и предложены принципы реализации виртуальной памяти в машине потоковой архитектуры - системе с автоматическим распределением ресурсов.
Основные научные результаты работы состоят в следующем:
На основе проведенного анализа архитектуры ВСАРР разработаны методы организации работы системы в многозадачном режиме.
Впервые разработана система специальных команд управления задачами, организующих виртуальную память, поддерживающих многозадачный режим работы и связь ВСАРР с операционной системой, и алгоритмы их выполнения.
Впервые разработаны подходы к созданию ВСАРР, работающей в реальном масштабе времени, обеспечивающие восстановление работоспособности системы с контрольных точек и обработку прерываний, возникающих при сбоях и отказах отдельных устройств.
Впервые разработана структура и принципы функционирования центрального устройства управления памятью (ІДУУП), обеспечивающего выполнение специальных команд управления задачами, организацига виртуальной памяти и взаимодействие ВСАРР с операционной системой.
Впервые разработаны механизмы функционирования аппаратуры по сбору статистики в ВСАРР, контролю прохождения задач и подзадач, применяемые при реализации ЦУУП и методов преодоления переполнения ассоциативной памяти.
Исследовано прохождение ряда задач на инструментальном испытательном комплексе, подтвердившее правильность разработанных решений с точки зрения управления задачами и организации виртуальной памяти системы.
Предложены новые методы аппаратной реализации многовходовых узлов, подсчета глобальной кратности и средств восстановления системы.
Практическая значимость
8 Практическая значимость работы заключается в следующем:
Разработанные в диссертационной работе аппаратно-программные средства управления задачами, связанные с одно- и многозадачным режимом работы и организацией виртуальной памяти, обеспечивают прохождение задач, для выполнения которых требуется объем ассоциативной памяти, превышающий реальный объем этой памяти в ВСАРР.
Разработанные в диссертационной работе специальные команды управления задачами, вошедшие в систему команд ВСАРР, реализуют новые возможности работы системы: организацию виртуальной памяти, обеспечение многозадачного режима работы и связи ВСАРР с операционной системой,
Разработана структура и принципы реализации ЦУУП, обеспечивающего выполнение специальных команд управления задачами, что позволяет повысить эффективность использования ресурсов системы при решении различных классов задач.
Разработаны подходы к созданшо ВСАРР, работающей в реальном масштабе времени, которые позволяют обрабатывать прерывания по сбоям и отказам отдельных устройств и обеспечивают продолжение решения задач с контрольных точек.
Разработаны и реализованы аппаратно-программные средства, предназначенные для: контроля прохождения задач и подзадач, регулирования параллелизма задач, сбора статистики, что делает возможным дальнейшее совершенствование архитектуры, а также реализацию предлагаемых методов в ВСАРР и в специализированных вычислительных системах подобной архитектуры.
Разработаны алгоритмы аппаратной реализации механизма подсчета глобальной кратности, многовходовых узлов, оптимизирующие выполнение задач, и которые позволят в будущем расширить возможности системы.
Проведено исследование прохождения ряда задач на инструментальном испытательном комплексе и продемонстрирована эффективность работы предлагаемой системы специальных команд управления задачами.
Положения, выносимые на защиту
Анализ новой архитектуры с точки зрения возможности создания аппаратно-программных средств управления задачами и организации виртуальной памяти в ВСАРР.
Разработанная система специальных команд управления задачами и алгоритмы их выполнения, позволяющих добиться эффективной загрузки ресурсов системы и поддерживать многозадачный режим работы.
Разработанные принципы и средства реализации механизма виртуальной памяти.
Разработанная структура и принципы аппаратной реализации центрального устройства управления памятью, реализующего систему специальных команд управления задачами и аппаратные средства преодоления переполнения АП в автоматическом режиме.
Исследование предложенных методов управления задачами па инструментальном испытательном комплексе вычислительной системы.
Реализация результатов работы
Новые теоретические положения и технические решения апробированы на инструментальном испытательном комплексе ВСАРР. Результаты работы реализованы в Институте проблем информатики РАН (ИПИ РАН) в отделе «Проблем построения информационно-вычислительных систем высокого параллелизма» при исследовании и разработке вычислительной системы с автоматическим распределением ресурсов и при реализации проекта по созданию макета вычислительной машины данной архитектуры. Апробация работы
Основные положения и результаты работы докладывались и обсуждались на научных семинарах в ИПИ РАН в 1999-2005 гг., а также на конференциях и научных форумах: на международной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» (г. Гурзуф, 2001), на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС2003» (нос. Дивноморское, 2003), на международной научно-практической конференции «Искусственный интеллект -
10 2004. Интеллектуальные и многопроцессорные системы - 2004» (пос. Кацивели, Крым, 2004), на «II Научной сессии Института проблем информатики Российской академии наук: Проблемы и методы информатики» (Москва, 2005), на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС2005» (пос. Дивпоморское, 2005), на второй Всероссийской научно-технической конференции «Методы и средства обработки информации МСО-2005» (Москва, 2005).
Некоторые решения, созданные в рамках диссертации в виде имитационной модели, демонстрировались на Всемирной выставке по информационным технологиям CeBIT-2003, Ганновер, Германия.
Исследование разработанных методик, алгоритмов и схемотехнических решений проводилось в Институте проблем информатики РАН на инструментальном испытательном комплексе. Структура и объем диссертации
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и одного приложения. Общий объем диссертации составляет 160 страниц. Аннотация работы по главам
Во введении обоснована актуальность темы диссертации, определены научная новизна и практическая значимость работы, сформулированы цель и основные задачи исследований, приведено краткое описание структуры диссертации.
В первой главе диссертационной работы приведен обзор проблем повышения производительности в традиционных вычислительных системах массового параллелизма и анализ причин переполнения памяти совпадений в вычислительных системах, управляемых потоком данных.
Во второй главе дано описание вычислительной системы с автоматическим распределением ресурсов (ВСАРР), описываются методы преодоления ситуации переполнения ассоциативной памяти (АП) ВСАРР и предлагается подход к реализации виртуальной памяти системы.
В третьей главе содержится описание алгоритмов выполнения команд управления задачами и работы центрального устройства управления памятью
(ЦУУП), реализующих многозадачный режим работы и поддерживающих организацию виртуальной памяти В САРР.
В четвертой главе приведены результаты исследования функционирования вычислительной системы на инструментальном испытательном комплексе ВСАРР.
В заключении обобщаются основные результаты проведенных автором исследований и разработок, сформулированы основные выводы по работе в пелом, намечены пути дальнейшего исследования методов организации средств управления задачами и виртуальной памяти.
Обзор архитектур, которые реализуют модель вычислений, управляемых потоком данных
Вычислительные системы потока данных (или потоковые вычислительные системы) - один из архитектурных путей достижения высокой производительности [20,68,70,74]. Граф вычислительного процесса
Компьютеры потока данных представляют собой подход к организации вычислений полностью отличный от традиционной вычислительной машины фон-Любой вычислительный процесс может быть представлен графом потока данных (рис. 1.1) - это ориентированный граф, узлами которого являются операторы, выполняемые над данными, а по дугам графа перемещаются данные. Вычислительные машины архитектуры потока данных реализуют непосредственное выполнение данного графа. Это обеспечивает параллельность вычислительных процессов, заданных программой, и исключает конфликтные ситуации по данным.
Данные, передаваемые по дугам графа, называются токенами. Токены представляют из себя сложную структуру, которая помимо самого данного содержит код операции, которая будет выполнена над данным, а также некий контекст, идентифицирующий это данное. Фундаментальным понятием концепции машины потока данных является понятие оператора (узла). Вычисления в машине потока данных организуются следующим образом: токены передаются между операторами (узлами) и когда узел получает все токены для выполнения операции, он активируется, выполняет операцию над входными токенами, а после завершения операции пересылает токен с результатом к другому узлу, для которого этоттокен становится входным [49].
В компьютерах фон-неймановской архитектуры последовательность выполняемых инструкций образует поток управления, который создается с помощью счетчика команд и памяти команд [18,31]. В этих компьютерах инструкция выполняется, когда на нее указывает счетчик инструкций. В компьютерах потока данных никаких указателей на инструкции нет, и принцип активации операторов (узлов) совсем другой: оператор считается готовым к исполнению, как только на его входные дуги поступит полный набор операндов (токенов). Например, инструкция сложения некоторого узла будет готова к исполнению, как только на его дуги поступят и первое, и второе слагаемое. Пока набор входных токенов не содержит полного набора операндов для данной операции, она будет ожидать поступления остальных операндов. Статическая модель вычислений, управляемых потоком данных
Для вычислительных систем потока данных, реализующих статический граф потока данных, па каждой дуге между любыми двумя узлами может находиться только один токен. Узлы графа соответствуют операциям, выполняемым над входными данными. Графы, в узлах которых выполняется только одна операция, называются мелкоструктурированными (мелкозернистыми) потоковыми графами. В статической модели токен характеризуется только адресом (номером) узла, при этом выполнение в параллель нескольких итераций цикла, или вызовов подпрограмм невозможно [48]. На уровне вычислительной системы граф потока данных представлен как набор шаблонов, каждый из которых содержит код операции, поля операндов и поле адреса назначения результата. Узел активируется, как только все необходимые токены появляются на его входных дугах, и нет токенов на его выходной дуге. Чтобы реализовать данное ограничение, вводится квитирование, то есть передача по дополнительным дугам подтверждения [50].
Статическая модель организации вычислительного процесса с управлением потоком данных базируется на следующем правиле - команда считается готовой к выполнению, когда на её входных дугах присутствуют токепы-операнды, и на выходной дуге отсутствует результат её предыдущего выполнения.
При выполнении команды узла его входные токены исчезают со входных дуг. Токеиы-подтверждения по дополнительным дугам выдаются командой предыдущим командам, чьи результаты являются входными операндами для команды текущего узла после того, как она начала выполняться.
В свою очередь, команда считается готовой к выполнению, если на ее входные дуги поступили все входные токены, а по дополнительной дуге поступил токен-подтверждение о том, что входная дуга команды-получателя результата свободна.
На основе статической модели было создано несколько вычислительных машин, среди которых MIT Static Dataflow Агс1ікесШге(Массачусетский Технологический Институт, США), LAU System(OpaHnrni), NEC Image Pipelined Ргосез5ог(Япония).
Преимущества и недостатки статической модели организации вычислительного процесса с управлением потоком данных
Основным преимуществом статической модели является то, что статическая модель потока данных дает увеличение производительности при выполнении программ с большим параллелизмом на уровне команд. Это достигается за счет выдачи команд на исполнение по готовности их входных операндов, а не по счетчику команд, как это делается в машинах традиционной архитектуры. При соответствующем уровне параллелизма программы это приводит к хорошей загрузке конвейера и отсутствию простоя исполнительных устройств.
Основными недостатками статической модели потока данных являются: - отсутствие возможности выполнять параллельно несколько итераций одного цикла и осуществлять выполнение нескольких параллельных активаций одной и той же функции; - недостаточная поддержка параллельного выполнения функций и итераций циклов сводит извлекаемый из программы параллелизм только к параллелизму на уровне команд; - техника обратных сигналов удваивает количество токенов, передаваемых между операторами программы; - статическая модель потоковой архитектуры малоэффективна при работе со структурными типами данных - массивами, списками, векторами. Динамическая модель вычислений, управляемых потоком данных
Исследование проблемы переполнения ассоциативной памяти ВСАРР и методы ее решения
Решение задачи построения иерархии памяти, разработка подходов к созданию механизма виртуальной памяти токенов и методов регулирования вычислительного процесса, в том числе в многозадачном режиме работы, стали одними из основных в исследовании и разработке новой вычислительной системы.
Для любых вычислительных систем всегда может быть написана такая программа, для выполнения которой имеющихся в наличии ресурсов физической оперативной памяти будет недостаточно, и ВСАРР - не исключение. Основные факторы, которые влияют на переполнение ассоциативной памяти ВСАРР: Модульность АП
Несмотря на все преимущества разделения ассоциативной памяти на модули, это разделение порождает ряд проблем. В частности, переполнение одного из модулей ассоциативной памяти (из-за неравномерного распределения токенов по модулям) для архитектуры ВСАРР по сути равнозначно переполнению всей АП, поскольку в этом случае выполнение программы может резко замедлиться, а в некоторых случаях - даже и не закончиться, если не предпринимать никаких действий для освобождения места в модуле АП. Несовершенная хэш-функция
Данный фактор неразрывно связан с модульностью АП, поскольку при неудачно выбранной хэш-функции может возникнуть ситуация, при которой значительное количество генерируемых токенов будет попадать в один модуль АП и в конце концов он может переполниться. Наличие проблемы «взрывного» параллелизма программ Данная проблема рассматривается в разделе 2.5. Использование принципа маскирования ключа токена и бесконечной кратности Взаимодействие токенов с маской (тем более, если один из токенов имеет бесконечную кратность) .может привести к «взрыву» параллелизма (раздел 2.5), поскольку в этом случае даже один токен способен вызвать генерацию многих пар. Использование глобальных токенов
Поскольку все глобальные токены имеют бесконечную кратность и принцип их работы таков, что экземпляры глобальных токенов для каждого вычислительного узла одновременно посылаются во все модули АП, что в итоге вызывает накапливание отработавших токенов (с бесконечной кратностью), сокращающих полезный объем ассоциативной памяти.
Возможность генерации программой узла «неограниченного» количества токенов В ВСАРР существует возможность генерации исполнительным устройством практически неограниченного количества токенов. В результате существует реальная угроза переполнения ЛП при занятости ИУ обработкой подобных узлов, поскольку ИУ не будут принимать готовые к исполнению пары, в то время как сами ИУ будут передавать токены в АП.
Методы решения проблемы переполнения ассоциативной памяти ВСАРР К основным методам можно отнести следующие: -построение иерархии памяти и создание механизма виртуальной памяти системы; -разработка аппаратно-программных методов регулирования параллелизма задач; -аппаратная поддержка некоторых программных конструкций таких, как механизм подсчета глобальной кратности, реализации многовходовых узлов. В следующих разделах подробно рассматриваются основные подходы к решению проблемы переполнения ассоциативной памяти и блокировки вычислений, реализованные в вычислительной системе. Построение иерархии памяти ВСАРР
В этом разделе рассматриваются проблемы блокировки вычислительного процесса в результате переполнения буферов кольца и самих модулей АП, а также возможности построения иерархической памяти.
Использование буферов токенов и пар в ВСАРР Коммутатор токенов (КМТ) имеет встроенный буфер небольшого объема для хранения токенов, что связано с необходимостью иметь высокую реактивность системы.
Коммутатор пар (КМП) с собственным буфером выполняет следующие функции: сглаживает неравномерность во временах выдачи пар из МАП и приема пар вИУ; обеспечивает равномерную загрузку исполнительных устройств за счет перемещения готовых пар из более заполненного буфера в менее заполненный; обеспечивает соединение всех МАП со всеми устройствами ИУ по принципу «каждый с каждым».
Основными причинами неравномерности прохождения токенов и пар по вычислительным узлам системы и необходимости использования буферов являются следующие факторы: а) резкое изменение параллелизма решаемой задачи; б) неравномерность режимов работы МАП (при поиске, обработке, записи); в) неравномерность обработки пар в ИУ, связанная с использованием программ узлов с произвольным количеством команд.
Необходимо отметить, что в каждом кольце достаточно установить по одному буферу токенов и пар. Буфера в кольце увеличивают объем памяти всего кольца и сглаживают неравномерность параллелизма задачи с целью наиболее полной загрузки ИУ.
Блокировка вычислительного процесса (deadlock) в ВСАРР - это такая ситуация, при которой алгоритм задачи и сама программа написаны верно, а задача при запуске се на выполнение в вычислительной системе, в зависимости от конкретной конфигурации и временных соотношений при ее выполнении, не проходит из-за недостатка физического ресурса. В ВСАРР недостающим ресурсом, как правило, бывает память вычислительного узла, представляющая собой память токенов модуля АП, а также буфера токенов и пар.
Форматы дополнительных токенов, обеспечивающих выполнение команд управления
Основными функциями ЦУУП являются: - установка начальных физических адресов в адаптере ООЗУ, причем для каждого вида откачиваемых токенов имеется своя область ячеек в ООЗУ; - распределение свободных страниц ООЗУ; - поддержка операционной системы с точки зрения распределение ресурсов ООЗУ и связи ООЗУ с дисковой памятью; - сбор статистики по выполняемым задачам (количество свободных ячеек в модулях АП; интенсивность формирования пар по каждой задаче; интенсивность прихода токенов на вход МАП; загрузка буфера готовых пар по каждому модулю;) - выполнение ротации задач и подзадач; - подсчет значения глобальной кратности для выполняющихся задач; - проверка активности задач, реализация функции останова задач;
Структура областей (буферов или сегментов) откачанных токенов и пар В ООЗУ могут быть записаны следующие данные: - токены задачи (подзадачи), которые впервые вводятся в работу; - откачанные записанные токены задачи (подзадачи), в том числе отложенные токены; - откачанные заглушкой токены задачи (подзадачи); - откачанные пары задачи (подзадачи); - токены для загрузки памяти ИУ; - токены для загрузки таблицы страниц памяти ИУ; - токены задачи (подзадачи), предназначенные для выдачи на хост-машину.
Каждая задача (подзадача) должна иметь в ООЗУ несколько типов областей (буферов - далее будем называть их сегментами) для вышеописанных типов токенов. Поэтому можно иерархически структурировать содержимое ООЗУ, например, для подзадач (рис, 3,3) - верхняя ступень структурирования - по номеру подзадачи, нижняя - по номеру модуля АП (на рисунке показаны не все области).
Токены задачи (подзадачи), предназначенные для ввода в ВСАРР загружаются в ООЗУ хост-машиной. Эти токены можно рассматривать как информацию, поступающую в систему извне (например в режиме реального времени), или как первоначально вводимые данные задачи в ВСАРР.
Откачанные записанные (или отложенные) токены задачи (подзадачи) направляются в ООЗУ в результате выполнения команды откачки задачи (подзадачи), либо в случае автономной работы ЦУУП при переполнении одного или нескольких модулей ЛП (рабочие названия - «откачанный записанный токен», «откачанный отложенный токен»).
Откачанные заглушкой токены задачи (подзадачи) направляются в ООЗУ в результате взаимодействия с установленными в АП токенами-заглушками (в ООЗУ направляются токены, которые передавались от ИУ на поиск в модули АП, рабочее название «токен, откачанный по заглушке»).
Откачанные пары задачи (подзадачи) могут направляться в ООЗУ для поддержания нужного темпа работы АП при возникновении занятости на прием в коммутатор пар или при занятости всех исполнительных устройств.
Токены задачи (подзадачи), предназначенные для выдачи на хост-машину это токены, которые могут содержать окончательные или промежуточные результаты выполнения задачи. К дополнительным видам токенов, которые инициируют выполнение различных действий и осуществляют аппаратную поддержку системы команд управления ВСАРР, относятся: - токены-команды разных типов (раздел 3.1.2.); - токен-команда «Подсчитать значение глобальной кратности для задачи»; - специальный токен, поддерживающий выполнение команды «Подсчитать значение глобальной кратности для задачи». Посылается из модуля АП в ЦУУП при достижении значения счетчика в модуле АП (подсчитывающего количество взаимодействий с глобальным токеном), равного 256; - специальный токен, периодически опрашивающий модуль АП (для подсчета глобальной кратности). Этот токен посылается из ЦУУП в МАП (период выдачи токена определяет ЦУУП); - специальный токен-сообщение «Глобальная кратность подсчитана» посылается из ЦУУП в МАП; - специальный токен «Стирание» для стирания в МАП токенов-счетчиков, подсчитывающих глобальную кратность; - специальный токен, удаляющий токен-заглушку конкретной задачи или подзадачи; - специальный токсн-запрос от пользователя, запрашивающий значение глобальной кратности; - специальный токен, содержащий статистическую информацию о задаче; - специальный токен, фиксирующий исключительную ситуацию и передающий ее код; - токены загрузки для работы с исполнительным устройством по командам «Загрузка памяти ИУ» и«3агрузка таблицы страниц ИУ»; 102 токены, передающие контрольный код от ИУ для каждой записанной страницы в ПК ИУ; токены-заглушки; специальный токсн-заглушка («фиктивная заглушка»), который фиксирует интенсивность прихода токепов задачи (подзадачи) и посылает подсчитанное значение в ЦУУП; токсны-фишки; токены-фиксаторы; токен-подтвержденис;
Проведение экспериментов на инструментальном испытательном комплексе с использованием разработанных специальных команд управления
С целью отработки и проверки работоспособности архитектуры ВСАРР был создан инструментальный испытательный комплекс системы. Он позволяет проанализировать работоспособность созданной архитектуры, оценить правильность алгоритмов работы и динамики загрузки отдельных устройств системы в ходе решения задач, а также накопить статистику с целью ее дальнейшей обработки для выявления достоинств и недостатков системы команд управления задачами и используемых аппаратных решений.
В состав инструментального испытательного комплекса (ИИК) входят: - имитационная модель ВСАРР (поведенческого уровня); - программная блочно-регистровая модель - ПЕРМ; - макет ВСАРР, выполненный на ПЛИС фирмы Altera. 4.1. Имитационная модель системы
Имитационная модель отражает особенности данной архитектуры и позволяет запускать программы, проводить оценку степени распараллеливания, загрузки устройств и эффективности некоторых способов распараллеливания алгоритмов, используя для этих целей средства визуализации и сбора статистики.
Имитационная модель обеспечивает: - корректное исполнение программ, диагностику ошибок; - возможность изменения конфигурации системы; - демонстрацию загрузки устройств системы.
Имитационная модель позволяет устанавливать различные варианты конфигураций системы. При этом предоставляется возможность изменения размера буферов на входе и выходе модулей АП. Эти параметры важны для исследования возможностей аппаратуры при решении различных классов задач.
В качестве результатов прохождения задачи могут быть получены следующие данные: - количество исполненных команд различного вида при решении задачи; - загрузка устройств на каждом такте решения задачи на данной конфигурации; - динамика загрузки устройств в процессе решения задачи и подсчет тактов работы системы от начала до окончания задачи;
Имитационная модель предоставляет также возможность остановки системы на любом такте ее работы и просмотр состояния ассоциативной памяти, в том числе данных, подаваемых в исполнительное устройство, а также тип исполняемой команды.
Программная блочно-регистровая модель (ПЕРМ) ВСАРР предназначена для более детальных исследований (по сравнению с имитационной моделью), поскольку многие блоки системы в этой модели описаны до регистрового уровня. При необходимости, возможно изменение степени детализации устройств, входящих в систему, так как для всех основных блоков, вплоть до буферов, имеется возможность изменения количества регистров, разрядности данных, управляющих воздействий и других параметров. На ПБРМ ВСАРР:
а) впервые отрабатывались алгоритмы работы команд управления, выполняющихся в привилегированном режиме;
б) впервые осуществлялись эксперименты по преодолению переполнения модулей ассоциативной памяти;
в) были получены результаты, связанные с возможностью регулирования параллелизма задач с поддержкой этих режимов на аппаратном уровне;
г) введены команды сбора статистики и контроля прохождения задач, исследовались возможности работы системы в многозадачном режиме.
Блочно-регистровая модель представляет собой интерактивную систему конструирования работы ВСАРР. Модель состоит из двух основных блоков: «ядра» - программы, моделирующей работу ВСАРР и «оболочки» - программы, позволяющей управлять работой ядра, то есть устанавливать конфигурацию, загружать команды, константы и другие данные, а также отлшкивать исполняемые в «ядре» программы.
Принцип работы «ядра» основан на взаимодействии объектов, описанных в конфигурации. Конфигурация модели состоит из объектов и связей между ними (рис. 4.1). Каждый из объектов имеет определенные входные и выходные интерфейсы, что позволяет реализовывать и отлаживать каждый из объектов отдельно независимо от других. Реализация каждого объекта заключатся в описании реакций на события, пришедшие от других объектов. Объектом поведенческой модели может быть как программная модель устройства, так и аппаратная реализация устройства. При этом полностью сохраняется интерфейс между устройствами.
Одной из основных задач моделирования является синхронизация между объектами (моделирование времени выполнения операций). Данная проблема решена методом «событийного моделирования»: каждый из объектов на своем выходе генерирует событие, в котором указывается объект, которому оно передается, время выполнения этого события в объекте-получателе, а также исходящие данные. Это событие помещается в глобальный «список событий», который работает по принципу буфера - очереди FIFO (из списка берется первое событие, выполняется в указанном в нем объекте и затем удаляется).
Пример конфигурации системы в ПЕРМ
Создание конфигурации осуществляется в «оболочке», каждый объект, реализованный в «ядре» или подключенный к нему с помощью технологий СОМ или DLL, имеет свое «графическое отображение». Конструирование конфигурации осуществляется путем установки этих «графических отображений» в рабочую область (рис. 4.1). Алгоритм работы сконфигурированной модели обеспечивается установкой связи между «отображениями», путем соединения выходов одних со входами других, при этом осуществляется контроль связей, то есть невозможно провести связи между входом и входом, выходом и выходом, а также выходом и входом с разными типами данных.
