Содержание к диссертации
Введение
1. Принципы организации и методы проектирования контроллеров и специализированных процессоров подсистем ВЗУ ЦЦ 12
1.1. Структура подсистем ВЗУ ЦЦ и методы повышения её эффективности 12
1.2. Структурная реализация некоторых методов повышения эффективности подсистем ВЗУ ЦЦ 17
1.3. Особенности подсистем управления ВЗУ ЦЦ. Анализ методов проектирования контроллеров и спецпроцессоров подсистем ВЗУ ЦЦ 45
1.4. Основные выводы по главе 51
2. Структурный подход к проектированию контроллеров и специализированных процессоров подсистем ВЗУ ЦЦ 53
2.1. Сети Петри 56
2.2. Формализация представления структуры проектируемого устройства 69
2.3. Анализ исследуемой структуры 89
2.4. Основные выводы по главе 102
3. Средства структурного проектирования контроллеров и спецпроцессоров подсистем ВЗУ ЦЦ 103
3.1. Комплекс программ для исследования управляющих устройств подсистем ВЗУ ЦЦ на архитектурном уровне 104
3.2. Специализированная система проектирования на микропрограммном уровне 129
3.3. Основные выводы по главе 145
4. Использование средств структурного проектирования на архитектурном уровне при разработке спецпроцессора реляционной базы данных 148
4.1. Назначение спецпроцессора 150
4.2. Разработка алгоритмов выполнения операций реляционной алгебры в спецпроцессоре РБД 166
4.3. Разработка и верификация множества структур спецпроцессоров, реализующих отдельные операции реляционной алгебры 187
4.4. Разработка структуры спецпроцессора РБД 234
4.5. Основные выводы по главе 245
Заключение 247
Литература 250
Приложение I. Акты внедрения результатов работы 263
Приложение 2. Результаты исследования процессора оптимизации плана обращений к ВЗУ ПД 273
Приложение 3. Классификация сетей Петри 281
Приложение 4. Определение операций алгебры регулярных сетей Петри 284
Приложение 5. Доказательство свойств операций алгебры
сетей Петри 287
Приложение 6. Примеры входных и выходных данных подсистемы документированного представления и кодирования диаграмм микропрограммной логики 296
Приложение 7. Подсистема моделирования 302
Приложение 8. Описание операций реляционной алгебры 315
Приложение 9. Назначение элементов сетей Петри, интерпретирующих спецпроцессоры операций реляционной алгебры 319
- Структура подсистем ВЗУ ЦЦ и методы повышения её эффективности
- Сети Петри
- Комплекс программ для исследования управляющих устройств подсистем ВЗУ ЦЦ на архитектурном уровне
- Назначение спецпроцессора
Введение к работе
Современные ЭВМ общего назначения и вычислительные системы (ВС) характеризуются высоким отношением производительности к стоимости, простотой адаптаиии к сфере применения и высокой се-рийнопригодностью. Эффективным средством обеспечения указанных свойств является применение в этих ЭВМ и ВС развитой системы ввода-вывода (СВВ). Эффективная работа СВВ в значительной мере определяет потребительские свойства и стоимость ЭВМ. Доля стоимости СВВ от общей стоимости ЭВМ в настоящее время составляет более 75$ для универсальных ЭВМ и более 80$ для мини- и микро-ЭВМ [59] . Кроме того, по мере совершенствования структуры ЭВМ и ВС к СВВ предъявляют все более высокие требования пропускной способности, надежности, гибкости и живучести в работе. Задача повышения производительности СВВ ЭВМ и ВС во многом определяется дальнейшим повышением эффективности работы накопителей внешних запоминающих устройств прямого доступа (ВЗУ ЦЦ) при обращении к ним со стороны центрального процессора (Щ) через соответствующие каналы и устройства управления.
Одним из подходов к повышению производительности работы подсистем ВЗУ ЦЦ является перемещение логической обработки данных на устройства управления, роль которых выполняют контроллеры и спе-пиализированные процессоры ввода-вывода.
Специализированные процессоры и контроллеры подсистем ВЗУ ПД с расширенными функциями представляют собой иерархию трех уровней [3, 5, 59, 80].'микропрограммный уровень, традиционный машинный уровень, уровень операционной системы. На основе данных уровней определяются функции спецпроцессоров и контроллеров и их разделение на множества, реализуемые аппаратным и программным путем; определяется состав устройств и способы их взаимодействия. Данные задачи решаются в пропессе проектирования указанных устройств на функциональном и алгоритмическом уровнях [62].
При разработке контроллеров и спепиализированных процессоров подсистем ввода-вывода особенно ярко проявляется взаимосвязь архитектурного и микропрограммного уровней проектирования. Это объясняется, во-первых, тем, что указанные управляющие устройства входят в сложные иерархические системы, при описании которых необходимо учитывать разносторонние внешние взаимодействия. Кроме того, спеппропессоры и контроллеры представляют собой сложные управляющие устройства, выполняющие разнообразные специальные функпии по логической обработке больших объемов информации. Указанные свойства требуют использования специальных методов и средств формального описания и исследования как структур, включающих контроллеры и спеппропессоры ввода-вывода, так и внутренней архитектуры данных устройств. Во-вторых, из-за высокой сложности в большинстве контроллеров и спецпроцессоров реализован микропрограммный принцип управления. Это, в свою очередь, требует использования микропрограммного подхода к проектированию данных управляющих устройств. Использование микропрограммирования подразумевает необходимость разработки спепиализированных систем инженерного проектирования, которые должны обеспечивать этапы формирования и проверки корректности микропрограмм, выпуска документации для специалистов, а также файловую систему для хранения и обновления наборов данных о проектируемом устройстве в пропессе его изготовления и последующей эксплуатации.
Разработанные к настоящему времени методы проектирования и способы построения СВВ не решают всех вопросов, связанных с проектированием высокоэффективных спецпроцессоров и контроллеров с расширенными функциями. Далеки от завершения исследования, связанные с согласованным распределением ресурсов подсистем и их взаимодействием с нейтральной частью ВС; отсутствуют общепринятая методология и формальные методы проектирования, нет простых и быстрых способов опенки результатов проектирования, анализа подсистем на возможность возникновения тупиковых ситуапий; используемые правила выбора варианта проекта, выделения уровней иерархии и состава функций отдельных модулей базируются в основном на интуитивном подходе, что значительно снижает эффективность процесса разработки подсистем ВЗУ ІЩ. Указанные обстоятельства приводят к необходимости дальнейшего совершенствования теоретических и практических методов, а также средств проектирования развитых устройств управления подсистем ВЗУ ЦД.
Целью работы является разработка методов и средств структурного проектирования специализированных процессоров и контроллеров с расширенными функциями подсистем ВЗУ ЦД на архитектурном и микропрограммном уровнях.
Указанная цель достигается решением следующих задач: исследование структур и определение подхода к проектированию контроллеров и спецпроцессоров подсистем ВЗУ ПД; разработка элементов формального аппарата синтеза и анализа проектируемых устройств на архитектурном уровне, разработка эффективной методики проектирования и верификации структуры устройства; разработка средств структурного проектирования специализированных процессоров и контроллеров на архитектурном и микропрограммном уровнях;
4) практическая проверка возможности применения результатов исследования для проектирования указанных устройств подсистем
ВЗУ БД.
Методы исследования основаны на использовании положений теории сетей Петри, матричного анализа, теории множеств, теории формальных грамматик и строятся на сочетании формальных и содержательных методов. Решение поставленных задач предусматривало использование основ структурного программирования и имитационного моделирования.
Научная новизна состоит в развитии методов и средств разработки спепиализированных пропессоров и контроллеров подсистем ВЗУ ГІД в рамках структурного подхода, связанных с дальнейшим совершенствованием процедур анализа и синтеза сложных вычислительных структур, а также разработкой спепиализированных средств для их реализации.
В результате проведенного исследования достигнуто следующее:
1. На основе теории сетей Петри разработаны элементы формаль ного аппарата исследования устройств управления ВЗУ ЦД на архи тектурном уровне, которые заключаются в расширении средств опи сания и анализа иерархических систем, в разработке методов деком позиции систем и их оптимизации на различных уровнях представ ления;
На основе иерархических сетей разработана методика проектирования спецпроцессоров и контроллеров подсистем ВЗУ ПД на архитектурном уровне, которая содержит эффективные методы верификации структур с точки зрения возможности возникновения тупиковой ситуации и сочетает формальные методы исследования с наглядностью и простотой представления;
Разработаны программные средства, позволяющие проектиро- вать многоуровневые подсистемы управления ВЗУ ЇЇД на архитектурном и микропрограммном уровнях. В рамках разработанных средств предложены: подход к реализации макро- и микроархитектуры многоуровневых подсистем; спектр интерфейсов пользователя, основанных на различном представлении данных и позволяющих обеспечить возможность выбора наиболее удобного способа доступа к системе; реализация механизма отображения моделей смежных уровней и методы манипулирования соответствующими данными;
4. Предложены методы повышения эффективности работы подсистем ВЗУ с накопителями на магнитных дисках: разработаны варианты структурной реализации специализированного процессора оптимизации плана обращений к ВЗУ; выработаны рекомендации по использованию методов коммутации информационных трактов к зонам одного накопителя или к накопителям многомодульной системы ВЗУ при страничном обмене данными.
Достоверность полученных результатов подтверждается экспериментально при разработке на архитектурном уровне специализированного процессора реляционной базы данных. При этом обоснован вариант архитектурного решения в виде многопроцессорной ВС, показана корректность полученной структуры.
Практическая ценность. Работа является составной частью программы проводимых на кафедре вычислительной техники ШШ научно-исследовательских работ по исследованию и разработке структур контура управления и средств файловой обработки в подсистемах ВЗУ БД, которые входят в план важнейших НИР Минвуза СССР в области вычислительной техники на 1981-85 г.г. (приказ J$ 1238 от 29.12.81, тема 2.2.3 "Разработка программ для моделирования и автоматизации проектирования ЭВМ"), важнейших НИР Минвуза РСФСР по проблеме САПР (приказ В ЗІ от 15.02.83). Данная работа являет- ся также частью научно-исследовательских работ "Разработка методики обучения автоматизированному проектированию архитектуры вычислительных комплексов и сетей с использованием дисплейных станций", которая определяется Координационным планом Минвуза РСФСР "Исследование эффективного комплексного применения технических средств обучения в условиях проблеммного обучения".
Практическими результатами работы являются: I) разработка и внедрение спецпроцессоров ВЗУ оптимизации доступа к накопителям на магнитных дисках; 2) разработка и внедрение специализированной системы моделирования, кодирования и документирования микропрограммного обеспечения устройств управления ВЗУ; проведено обучение операторов ЭВМ по использованию данной системы, внедрение которой ускорило процесс проектирования интеллектуальных контроллеров и оформления документации в соответствии с требованиями ЕСКЦ; 3) разработка комплекса программ для исследования управляющих устройств подсистем ВЗУ ІЩ на архитектурном уровне, который сдан в ФАЛ НИВЦ МГУ; 4) на основе предложенных программных средств разработана структура специализированного процессора реляционной базы данных, которая положена в основу технического проекта устройства управления файловой обработкой в подсис--темах ввода-вывода вычислительных комплексов.
Реализация в промышленности. Результаты диссертационной работы внедрены на промышленном предприятии г.Пензы при выполнении автором четырех научно-исследовательских работ (что подтверждается соответствующими актами), а также использовались при выполнении хоздоговорных и госбюджетных работ на кафедре ВТ ППИ.
Апробация работы. Материалы диссертационной работы докладывались ж обсуждались на: - Всесоюзной конференции "Автоматизация проектных и конструкторских работ" (Москва, 1979 г.); - Всесоюзной научно-технической конференции "Автоматизапия науч ных исследований, эргономического проектирования и испытаний сложных человеко-машинных систем" (Ленинград, 1983 г.);
Всесоюзной научно-технической конференнии "Развитие теории и техники хранения информации" (Пенза, 1983 г.);
Всесоюзной научно-технической конференнии "Проблемы теоретической кибернетики" (Саратов, 1983 г.);
Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем" (Ереван, 1983 г.);
Ш Всесоюзном симпозиуме "Вероятностные автоматы и их приложения" (Казань, 1983 г.);
Всесоюзном семинаре "Оптимизация сложных систем" (Винница, 1983 г.);
Всесоюзной конференции молодых ученых и специалистов приборостроительной промышленности (Москва, 1983 г.); семинаре "Автоматизация проектирования в радиоэлектронике и вычислительной технике" (Москва, Мд"НТП, 1984 г.);
ХП Всесоюзном совещании-семинаре "Автоматизация проектирования микропроцессоров, микропроцессорных систем и СБИС" (Крымская область, 1984 г.); научно-технических конференциях профессорско-преподавательского состава щи в 1977-83 гг.
Публикации. По результатам выполненных исследований опубликовано 17 печатных работ, написаны разделы в четырех отчетах по НИР.
Работа.состоит из введения, четырех глав и заключения. ^первой главе- рассмотрены принципы организации и анализ методов проектирования устройств управления подсистем ВЗУ ПД. При этом рассмотрены методы повышения эффективности структур подсистем ВЗУ и - II - структурная реализация некоторых из указанных методов; дан анализ особенностей управляющих устройств подсистем ВЗУ ПД; обоснован выбор структурного подхода к проектированию и соответствующего математического аппарата. J3o второй глазе разрабатывается методика структурного проектирования управляющих устройств подсистеїл ЗЗУ ИД на основе аппарата сетей Петри. В третьей главе дано описание средств структурного проектирования спецпроцессоров и контроллеров подсистем ІЗЗУ ПД, которые основаны на разработанной выше методике. В четвёртой главе описан процесс проектирования специализированного процессора реляциоішои базы данных на архитектурном уровне. Показаны возможности математического аппарата и разработанных методов и средств проектирования управляющих устройств подсистем ВЗУ ПД. На защиту выносятся следующие научные результаты: методика разработки контроллеров и спецпроцессоров подсистем ВЗУ ПД на алгоритмическом уровне, основанная на структурном подходе к проектированию, математическим аппаратом которой служит теория иерархических сетей Петри.
Методы анализа и разрешения конфликтных ситуаций в системах:, для которых характерны динамическое распределение ресурсов и параллельные взаимодействующие процессы.
Метод декомпозиции иерархических уровней системы и определение функционального назначения отдельных модулей.
Средства структурного проектирования контроллеров и спецпроцессоров на архитектурном и микропрограммном уровнях.
Структура подсистем ВЗУ ЦЦ и методы повышения её эффективности
Под подсистемой ВЗУ ЦЦ понимается группа обрабатывающих компонентов, предназначенных для хранения данных и их передачи между ВЗУ ЦЦ (магнитный диск с перемещающимися либо фиксированными головками записи-чтения или магнитный барабан) и каналом ввода-вывода. Подсистемы ВЗУ ЦД характеризуются независимостью от структуры ядра ЭВМ и ВС и функциональным разделением управления вводом-выводом по следующим уровням иерархии: канал - контроллер - управляющий модуль - ВЗУ ЦД. Многоуровневая организация подсистем ВЗУ ЦД обеспечивает следующие основные преимущества в организации работы ЭВМ: параллельную работу центрального процессора (ЦП) ЭВМ и подсистемы, организацию параллельной работы многих ВЗУ на основе разделения времени и ресурсов, асинхронный принцип работы ЦП и подсистемы, возможность построения сложных подсистем путём организации нескольких направлений доступа к ВЗУ [59].
Известно, что производительность ВС часто ограничивается производительностью средств ввода-вывода и. внешней памяти [27,37,59]. Современные ВЗУ ЦД практически достигли предела быстродействия, определяемого электромеханическим принципом их действия. Поэтому повышение быстродействия подсистем ВЗУ ЦД, а следовательно и всей ВС в целом, может быть достигнуто структурными методами, которые основаны на сокращении времени связи ВЗУ с центральной частью ВС. Анализ отечественных и зарубежных высокопроизводительных ЭВМ даёт возможность определить ряд методов, влияющих на повышение эффективности ВС [7,20,37,40,58,68,69,85,86,87,122]. К наиболее эффективным способам следует отнести совмещение операций ЦП и подсистемы ВЗУ ЦД, которые порождают ряд приёмов по достижению заданной цели: предварительная обработка данных [65,86,99], буферизация информационных потоков .[58,88], осуществление страничного обмена информацией [58,65,100].
Сети Петри
В качестве примера демонстрации возможностей сетей Петри опишем с их помощью варианты реализации механизма извещения ЦП об окончании процесса передачи данных в подсистеме ВЗУ ЦЦ.
Самым простым способом, позволяющим задать механизм изве- щения ЦП об окончании процесса передачи данных, является разряд состояния, устанавливаемый ЦП перед началом ввода-вывода и сбрасываемый подсистемой после завершения передачи информации. Для формального описания работы подсистемы с подобным механизмом извещения может быть использован фрагмент безопасной сети Петри, представленный на рис. 2.4 . Переходы ,$// и ## описывают работу ЦП, переход Q - работу подсистемы ВЗУ ПД. Разметка позиций Р/ и Рд соответствует готовности ЦП к работе и наличию исходных данных. Выполнение данных условий приводит к началу работы ЦП (срабатывание перехода t/ ). Если исходных данных достаточно для выполнения некоторой последовательности действий, ЦП обрабатывает данную последовательность в течение времени Т (срабатывание перехода Qfi ) и переходит к анализу следующей информации. Если для продолжения работы ЦП необходимо осуществить операцию ввода-вывода, то ЦП формирует соответствующую команду для подсистемы ВЗУ ПД (срабатывание перехода Qfi ).
Комплекс программ для исследования управляющих устройств подсистем ВЗУ ЦЦ на архитектурном уровне
В процессе проектирования сложных вычислительных устройств на архитектурном уровне разработчику необходимо решать ряд задач, среда которых можно выделить: выбор архитектуры устройства; определение состава блоков устройства и способов их взаимодействия,определение требований к выходным параметрам блоков [62]
. Если проектируемое устройство относится к классу систем, характеризующемуся протеканием асинхронных параллельных процессов (многопроцессорные ВС, системы управления распределенными базами данных и .др.),то среди указанных вопросов проектирования можно выделить такие подзадачи, как разбиение структуры сложного устройства на уровни иерархии, анализ структуры и ее отдельных уровней на возможность возникновения тупиковых ситуаций, определение функционального назначения блоков устройства определенного уровня В качестве средства для решения указанных подзадач предлагается комплекс программ,основанный на аппарате иерархических сетей Петри. Комплекс является дальнейшим развитием системы моделирования на основе сетей Петри [28] . в качестве входного языка, служащего .для описания проектируемых устройств, используется метаязык, в основу которого положена алгебра сетей Петри. Основой идеологии комплекса программ является создание последовательно преобразуемых структурных моделей, выраженных средствами метаязыка. Если модель проектируемой структуры удовлетворяет заданным требованиям, то разрабатываются новые,более детальные модели .другого уровня. В противном случае модель разрабатывается заново и процесс проектирования возобновляется. Алгоритмы анализа и преобразования сетей Петри, реализованные программами комплекса, ориентированы на матричное представление сетей Петри.С другой стороны, формульное представление сетей Петри (фразы входного языка) позволяет оперативно вводить информацию о структуре и связях проектируемого устройства. Поэтому в качестве одного из требований, предъявляемых при разработке комплекса, являлось выполнение однозначности перехода от формульного представления сетей Петри к матричному и наоборот.
Назначение спецпроцессора
В основе реляционной модели лежит математическое понятие теоретико-множественного отношения, которое представляет собой подмножество декартова произведения списка доменов [55]. В работе [8і] дано следующее определение декартова произведения: декартовым произведением доменов Dj, Ъ , і.. ,21 к (їїі хд&. х называется множество всех кортежей #$,«$,..., j длины К таких, чт . и т.д. Здесь под доменами понимается некоторое множество элементов. Некоторое подмножество декартова произведения одного или нескольких доменов называется отношением. Отношение обычно представляется в виде таблиш, в которой строки соответствуют кортежам, а столбцы - доменам.
Если доменам отношений присвоить имена, то их порядок станет несущественным. Выражение R (Л/, ,...,/ ) при этом называется схемой отношения, R - именем отношения, п. - степенью отношения, (/#/,..., /7/j) - некоторая совокупность атрибутов. При этом каждый домен Лі отношения является областью определения атрибута А І . Примеры отношений приведены на рис.4.1.
Для описания подобных отношений и операпий над ними существуют точные математические обозначения, основанные на реляционной алгебре (РА) или реляционном исчислении (РИ). Операндами РА являются отношения фиксированной размерности. При определении РА используют операции: объединение, пересечение, разность, декартово произведение, проекция, соединение, деление, ограничение -математическое описание которых приведено в [45].
В РИ путем использования предикатов, кванторов и переменных удается описать отношения и операции над ними в виде аналитических выражений. Кратко изложим основы данного исчисления на основе терминологии работы [82] .
Пусть Г является именем переменной. Тогда совокупность значений списка атрибутов А(ґ[А] ) называется срезом. Формула вида &ІГІ называется термом значения, где р - предикат. Формулы вида AQf/ , Л@А , где Л и J4 - срезы, о- константа, - 6 один из двуместных предикатов (х ,ф , , , , ), называются термами соединения. Между конечным множеством /?/,..., Rn одноместных предикатных переменных и множеством Ri ,..., Rn схем связей некоторой БД существует однозначное соответствие: терм указывает, что переменная fj- в некоторый момент времени последовательно принимает значения связи fy ; срез iTAJ отмечает О. -й компонент переменной ґ . на основе определений среза, термов значения и соединения вводятся понятия правильно построенной формулы (ППФ), свободных и связанных переменных, ППФ с областью определения, оС -выражения [82]. Совокупность - -выражений, с помощью которых пользователь описывает результаты, которые он желает получить при манипулировании с РБД, называется языком запросов к РБД, или реляционным исчислением [55,133].
