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

кандидата технических наук
Хейфец, Владимир Иосифович
город
Москва
год
1991
специальность ВАК РФ
05.13.13
Автореферат по информатике, вычислительной технике и управлению на тему «Разработка и исследование методов управления и контроля решающего поля мультипроцессора ПС2100»

Автореферат диссертации по теме "Разработка и исследование методов управления и контроля решающего поля мультипроцессора ПС2100"

С}Ш

^ V) 1 АКАДЕМИЯ НАУК СССР 1 '* ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

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

ХЕЙФЕЦ ВЛАДИМИР ИОСИФОВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ УПРАВЛЕНИЯ И КОНТРОЛЯ РШАЩЕГО ЮЛЯ НУЛЬТИПРОЦЕКСОРА ПС2100

Специальность 05.13.13 - Вычислительные машины, комплексы,

системы и сети.

АВТОРЕФЕРАТ

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

Москва - 1991 г.

Работа выполнена в Научно-исследовательском институте управляющих вычислительных машин (НПО "ймцульс") и ордена Ленина Институте проблем управления.

Научный руководитель - д.т.н., с.н.с. Медведев И.Л.

Официальные оппоненты:

д.т.н., профессор Согомонян Е.С.

К.Г.Н.9 С • Н« С• Яблонский C.B.

Ведущее предприятие - Всесоюзный научно-исследовательский

институт геофизических методов разведки (ВНИИГеофизика)

заседании специализированного совета № а (,дии<:.68.01) Института проблем управления: Москва, ул.Профсоюзная,65. Телефон совета: 334-93-29.

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

Автореферат разослан: "_"_1991 г.

Ученый секретарь

специализированного совета

к.т.н. Е.В.Юркевич

Защита состоится

час на

/

f

' - 1 -

■ 0Б1ДАЯ ХАРАКТЕРИСТИКА РАБОТЫ

->■ Актуальность проблемы» В мировой и отечественной практике прошшленной высокопроизводительной обработки информации широкое распространение получили комплексы со спецпроцессорами, которые выгодно отличаются от аналогичных по характеристикам супер-ЭВМ простотой технической реализации, низкой стоимостью, достаточной толерантностью к условиям эксш^атации. Кроме того, они обладает естественной модульностью, что позволяет специфицировать их состав под конкретные задачи, максимизируя соотношение "производительность/стоимость" для каждого пользователя. К таким комплексам принадлежат вычислительные комплексы ПС-2000 и ПС-2100, совместно разработанные Институтом проблем управления (г.Москва) и НПО "Импульс" (г.Северодонецк) и базирующиеся на мультипроцессорах (МП) ПС-2000 и ПС2Ю0 соответственно.

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

1) синтез структуры решающего поля;

2) синтез средств и методов управления решающим полем ;

3) синтез системы контроля решающего поля.

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

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

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

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

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

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

- О -

вании широкого класса устройств, характеристики быстродействия, надежности и ремонтопригодности которых соотносятся в той же пропорции, что и для Ш ПС2100.

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

Апробация работы. Материалы диссертационной работы докладывались на Всесоюзной научно-технической конференции "Опыт разработки и внедрения технических и программных средств СМ ЭВМ и АСВГ-ПС" (Северодонецк, 1986 г.), 1-й Всесоюзной конференции "Однородные вычислительные среды и структуры" (Львов, 1990г.), Всесоюзной научно-технической конференции "Опыт разработки и внедрения средств серии ПС" (Северодонецк, 1991г.).

Публикации. Основные положения диссертационной работы изложены в 10 опубликованных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на ПО стр. машинописного текста, кроме того, содержит 35 стр. иллюстраций, список литературы из 140 наименование и приложения.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность и формируется цель диссертационной работа с учетом особенностей реализации и проблемной ориентации МП ПС2Ю0.

В первой главе рассматриваются основные архитектурные и структурные особенности вычислительного комплекса (ВК) ПС2Ю0, структура ЫП HC2I00, способы управления МП в комплексе. Приводится иерархическая структура системы управления Ш, на верхнем уровне которой программа и микропрбграмма пользователя, адекватше графу его задачи, на никнем - аппаратура обработки,'хранения и передачи данных; подчиненность компонентов системы распространяется вниз по вертикали. На основании анализа системы управления МП определяются компоненты системы, подлежащие исследованию:

микрокод МП, структура и характеристики управляющего интерфейса, <

система .прерывания микропрограммы.

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

Ъ „

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

чество блоков для реализации решающего поля, Лб - количество блоков для реализации памяти микропрограмм при варианте реализации

1 ^ ' 1 г'

микрокода, принятом за базовый; Тп ,<ал,Л^л« - те же параметры для варианта реализации микрокода, который требуется сравнить с базовым по принятому критерию.

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

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

Рассмотрено состояние исследований методов синтеза и оптимизации систем прерываний программ. Показано, что этот аспект применительно к мультипроцессорным система!.! практически не исследован. Имеется монография по системам прерывания управляющих ЭВМ, однако принятые в ней критерии эффективности не могут быть применены к МП ПС2Ю0 в силу различия в их функционировании. В качестве критерия эффективности предлагается минимум суммарного времени обслуживания запросов на прерывания при соблюдении ограничений на время ожидания обслуживания запроса в очереди.

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

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

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

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

- . о/ Ло 7

на помечаемом входе: Р^ = пл {/¿ч,"^ у . Очевидно; если вершина графа ЗСс отображает элемент памяти, то переключение состояния выхода происходит только при переключении сигналов на входах синхронизации, установки и сброса и не происходит при переключении сигналов на информационных и управляющих входах;' поэтому для такой

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

- на графе (Х,0) выделяется подграф ¿¿(Хс все вершины которого отображают те и только те схемные элзментч, которые переключаются при выполнении ;

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

¡Илх^мм [Т,Л)1 ма*СТв^-]1, где ^ - число входных вершин подграфа , а/ - число выходных вершин подграфа Ьс , I - число особых дуг подграфа d¿ , 74/ - длина критического пути от К-го входа до J -го выхода подграфа ^ , 7е></' - длина критического пути от К-го входа до J -й особой дуги, включая вес особой дуги.

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

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

следовательности _ТтСп. = X <и-Тс , где А/ - количество типов микрокоманд в последовательности, - количество микрокоманд с -го типа, - время выполнения С-й микрокоманды. При

любом выбранном времени машинного такта Т временные потери

на выполнение пс л Тс =. Т- Т; Эля 11 ^Т; д Тс Ть | ."]"

для Тс.^ Т (здесь подразумевается, что каждая микрокоманды с

преобразуется в п- микрокоманд, ^аким

зом, интегральная величина относительной потери времени на по-

• Т*

следовательности микрокоманд ^ = - ; относительное пре-

0,1 17 * /¡.у., » вышедае объема памяти над оптимальным У =. , где М - ко-

личество типов микрокоманд, для которых Т^'нз кратно Т. Полученные выражения для Г и \ дают возможность выбирать время машинного такта как по критерию минимума,-времени выполнения поеледова-

»

тельности микрокоманд, так и по критерию ЖСР, предложенному в первой главе.

Предложенный метод позволяет выбрать рациональное время машинного такта для заданного набора микрокоманд. Однако автором, предложен метод минимизации времени машинного такта, подразумевающий некоторую реконструкцию выбранного микрокода. Основная идея этого метода - метода упреждающего управления - заключается в уменьшении времени выполнения микрокоманд путем опережающего формирования управляющих сигналов в предадущей микрокоманде. Для реализации этого метода микрокод представляется в виде множества микрокоманд М^мс} > ^ ~ язык АЭР^ - в виде множества

операторов 0^ =1,У. Каждый оператор 0j транслируется в некоторое подмножество микрокоманд М0-Г с фиксированным порядком следования микрокоманд. Обозначим через

д/Г номер к -й микрокоманды в М0-*' ; составим матрицу 5* Сразмером I х I по следующему правилу:

-1 (Зо^ €-0 А/еМ° =г 4. V М^ = гло-х /!/■

АГУ

Выделим такие сочетания <--й строки и J -го столбца матрицы 5, что ='1; ^¡¿ф =0 для . Наличие такого сочетания

означает, что исхает быть в микропрограмме только непосредственно перед М] ; следовательно, попытка уменьшить Т^ за счет увеличения Т^ будет корректной. Собственно метод уменьшения Т ] эа счет увеличения Т^ заключается в следующем. На подграфах <¿1 и (э^ , отображающих участки схены, срабатывающие при выполнении и пу , выделим критические пути Ее и И] . Найдем подграф Я-1] с Р^ такой, что ^ С. <¿¿ . Наличие такого подграфа говорит о том, что в выполняется некая логическая функция Ф, которую модно перенести в Мс, "Нагрузим" м: выполнением функции Ф, т.е. образуем для тс новый подграф <5; = I/ Теперь время выполнения Р^с - критическая длина подграфа <э/ , а

время выполнения го; - критическая длина подграфа = <¿1 ^ ^ , *

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

Как правило, реконструирование микрокода и уменьшение времени машинного такта по предложенному методу сводится к реорганизации управляющего дешифратора, т.е. изменению программы прожига ПЗУ или топологии связей в БЖ и не требует дополнительных затрат аппаратуры.

Решение горизонтальной задачи синтеза микрокода начинается с определения потенциальной возможности разбиения микрокоманда на независимые поля. Для этого МП представляется в виде множества В -С^'1-}, 1 = функциональных устройств ; каждой микрокоманде

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

разбить на подмножества М^ , Мэа , ...,Мэк с соответствующим разбиением множества В на подмножества В,, В2, ...,Вк; разбиения должны удовлетворять условия!.!: для Vr<4 eM=¡j BmcC.6j ; для Ykic^-Мэс &miUt>\-ф при jФ£ . Наличие таких разбиений дает потенциальную возможность разбить микрокоманду на К полей, каждое из которых управляет работой функциональных устройств j =1 ,К, с =1, А/ь . Найденная потенциальная возможность разбиения микрокоманды на независимые поля может быть, сужена ограничениями, накладываемыми транслятором с ASPS. Ограничения состоят в том, что микрокоманды, изменяющие управляющий граф микропрограммы (например, входящие в операторы ASP5 с внутренними циклами, вызовами подпрограмм и т.д.) не могут совмещаться с другими микрокомандами. После исключения таких микрокоманд некоторые из подмножеств Mo¿ мопут оказаться пустыми; оставшиеся подмножества представляют собой реальное разбиение микрокоманда на Р независимых полей. Как известно, любое Р-элементное множество можно разбить на подмножества И£ способами, где Ир - число Белла, вы-

^ к-

числяемое по рекуррентной формуле Dn-н = C¿ 'di, . Следовательно, для получения оптимального решения горизонтальной задачи синтеза микрокода необходимо из Jp разбиений выбрать оптимальное по принятому критерию MÍCP.

Анализ применения предложенного метода на пользовательских микропрограммах, запрограммированных на ASK, дал следующие результаты:

- оптимальное время машинного такта без применения метода упреждающего управления для МП 1Б2100 было бы 180 не; предложенный метод позволил уменьшить это время до 140 не;

- оптимальное сочетание полей микрокоманда позволяет улучшить критерий MSCP на 26 % по сравнению с чисто вертикальным кодированием микрокоманда.

- J.JL -

Задача исследования эффективности управляющего интерфейса МП наиболее актуальна при загрузке в память микропрограмм и формулируется следующим образом. Пусть канал мониторной подсистемы (МПС) имеет пропускную способность Д , управляющий интерфейс МП - пропускную способность jm . Требуете:: найти оптимальный объем буфера К и оценить полученное решение с точки зрения уменьшения времени занятости мониторной подсистемы, работающей в многозадачном режиме, на обслуживание процессов связи с МП, а также с точки зрения уменьшения общего времени передачи массива из МПС в МП. При руХ задача вырождается, т.к. в случае, когда пропускная способность приемника выше пропускной способности источника, нет необходимости в: буферировании. Поэтому исследование проведено для случая . Максимальная пропускная способность

канала МПС достигается в блок-мультиплексном режиме, когда канал передает информацию блоками по 256 байтов; после передачи блока канал ожидает прерывания по готовности партнера. Через время Тп = =40 мне после появления прерывания начинается передача следующего блока. При подключения МП МПС без буфера блок передается с темпом J4, при этом ограничен снизу: при пауза между

словами воспринимается, как тайм-аут. При наличии на интерфейсной карте буфера глубиной к байт заполнение буфера идет с темпом % , одновременно идет разгрузка буфера с темпом ju (дисциплина FIFO). Поскольку , буфер постепенно заполняется. Он не должен

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

В случае отсутствия буфера время передачи массива из d ■ байтов составляет 77 й +Тп) • Показано, что оптимальным

является объем буфера К =25&( {- il ) ; при этом МПС затратна пе-

/

редачу массива из d байтов время TZM = • -t-Tn) . Показано,что общее время передачи массива при оптимальной емкости буфе-

- -

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

Система прерывания микропрограммы обрабатывает запросы от таймеров, схем контроля и внесших интерфейсов. Показано, что на типовых задачах пользователя можно пренебречь всеми прерываниями, кроме регенерации динамической памяти, канала данных и таймера периодического программного контроля. При этом время обработки зап роса на прерывание по регенерации ограничено жёстко: при Цр > Тр фиксируется аппаратная ошибка, и программа пользователя останавливается, т.к. возможно искажение информации в динамической памяти (здесь (2р - время пребывания в очереди запроса на прерывание по регенерации, Тр - период генерации запросов на прерывание). Вреда пребывания в очереди^запроса на прерывание от канала данных ограничено нежёстко: при 0.*>Тк будет происходить торможение внешних устройств, связанных с МП по каналу данных; произойдёт потеря эффективности МП, однако задача может выполняться (здесь Ох- время пребывания в очереди запросов на прерывание от канала, Тк - среднее время между запросами на прерывание). Время обработки запроса на прерывание от таймера периодического программного контроля ничем не ограничено.

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

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

Показано, что систему прерывания микропрограммы можно представить в виде системы массового обслуживания, при этом непрерываемые участки программы представляются потоком непрерываемости, характеристики которого получеш экспериментально на программах пользователя при различных наборах регистров, используемых только на непрерываемых участках. Характеристики потоков заявок и обслуживания для запросов прерывания по регенерации и периодическому программному контролю получеш на реальных резидентных программах МП ПС2Ю0; характеристики потока заявок канала данных взяты для самого худшего случая перспективных пользовательских задач; характеристики обслуживания заявок подучены для разных вариантов набора регистров, используешх только на непрерываемых участках микропрограмм, на реальных резидентных микропрограммах МП ПС2100. •

Исследования проводились для бесприоритетной и приоритетной дисциплин обработки запросов. При бесприоритетной дисциплине функция распределения времени пребывания запросов в очереди аппроксимируется приближенной формулой Н( г.) =1 - > ГДе И - общая загрузка системы прерывания, - ) - сред-

ьа-я)

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

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

Для системы с абсолютными приоритетами функци, распределения времени пребывания в очереди запросов К-го приоритета определяется посредством обратного преобразования Лалласа-Стилтьеса выражения

и*-, ч С*- £ ьъз сз+сь^-ак., -лА^Х]

Пк С"53 = -—-—---—--- )

2- ^^ ^ СС^ - ^ Ы}

где - преобразование Лапласа-Стилтьеса функции распре-

деления периода занятости системы прерывания, определяемое из соотношения

СУКЛ (в) = 2 Яг Ц С5 + с*., - а^ Т^С*)] - суммарная загрузка системы прерывания запросами с приоритетом не ниже -К:

^ £ & О*- = г. - .

* & //с

В общем случае определение функций распределения времени пребывания запросов в очереди с помощью преобразования Лапласа-Стилтьеса представляет значительные трудности; для инженерных расчетов рекомендуется метод аппроксимации, предполагающий расчет функции распределения времени ожидания по форлуле Нк(1)=,1-- СГк е ""к где И/к - среднее время ожидания в очереди запроса К-го приоритета, вычисляемое по формуле

WK » + .......й _

о^-, JLii-eXc.,)^-^)

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

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

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

{Зас ■*■ Х02) -гЛеЗ + Яоч) [Сич+Яог +

где - интенсивность отказов первого вида, - итенсивносп

запуска программного контроля, - интенсивность отказов

второго вида, - интенсивность отказов третьего вида, Я<ш -интенсивность восстановления, Я^о - интенсивность программного контроля. Полученное выражение связывает коэффициент пользовательской готовности с параметрами надежности МП и временными параметрами организации контроля. Продифференцировав Ро по и приравняв произведен) к нулю, получаем оптимальное значение периода запуска программных тестов Гок = <1 с и оптимальное значение Ро , где «£. - доля оборудования, охваченного аппаратным конт-

ролем, - доля оборудования, неохваченного аппаратным и охваченного программным контролем. Показано, что точно такой же коэффициент пользовательской готовности получится, если доля оборудования, охваченного аппаратным контролем составит (с£+р ), что для МП ПС2100 составляет 88 %. Очевидна большая сложность такого аппа ратного решения, устраняемая оптимизацией организации аппаратного контроля. Если при существующей доле оборудования, охваченного аппаратшм контролем, не вводить программного контроля, то Ро =о в 3,7 раз хуже Ро .

Работа МП в централизованном режше управления комплексом отличается тем, что пользовательская программа в Ж запускается центральной программой из МПС , и в ожидании запуска МП находится в простое. Когда МП в простое, система программного контроля продолжает работать, однако маска прерывания в МПС закрыта, и наличие ошибки запоминается на триггере, не приводя мгновенно к ремонту. Если в момент запуска программы в МП триггер ошибки равен нулю, МП переходит в состояние выполнения пользовательской программы на исправном оборудовании; если же триггер ошибки равен единице, то в момент запуска программы в МП начинается ремонт. В данной модели коэффициент пользовательской готовности зависит не только от параметров надёжности МП и временной организации программного контроля, но и от загрузки Е, определяемой как доля системного времени, в течение которой МЛ выполняет пользовательскую программу. Система уравнений Колмогорова для данного случая слишком громоздка для аналитического решения, поэтому она была решена методом Гаусса с использованием ПЭВМ. Получены зависимости Ро от отношения ^"'/Ток ( 'Сок- среднее время выполнения контролирующего теста, Ток - период запуска контролирующих тестов) при различных Е; при Е=1 решение совпадает с решением для децентрализованного режима. Для организации контроля важна зависимость Ток от Е; такая зависимость получена, показано, что в диапазоне Е, представляющем практический интерес (Е > ОД) Ток практически константен, что дает возможность планировать процесс периодического программного контроля статически, независимо от заранее неизвестной загрузки.

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

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

Для исследования и оптимизации временной организации периодического программного контроля разработана математическая модель, представляющая собой непериодическую неприводимую цепь Маркова. Система уравнений Колмогорова, описывающая систем, слишком громоздка для аналитического решения, поэтому решение проводится методом Гаусса с использованием ПЭВМ. Порчены зависимости Ро от Ток при различных Е. Определена зависимость оптимальных Ток и Ро от Е. Получена зависимость от Е отношения Рос/Роа, где Рос - оптимальный коэффициент пользовательской готовности для режима контроля с постоянной плотностью; Роа - оптимальный коэффициент пользовательской готовности для режима контроля с' переменной плотностью. При "слишком малых" и "слишком больших" значениях Е Рос = Роа ; это объясняется тем, что при "слишком малых" значениях Е время нахождения Ш в простое достаточно большое для того, чтобы возникшая неисправность была обнаружена и при ра-

- IS -

бочей плотности контроля, а при "слишком больших" значениях Е

за время простоя запускается достаточно мало контролирующих тесу

тов и при постоянном программном контроле. Отношение Рос/Роа достигает минимума при Е=0,4; при этом Рос/Роа = 0,92. Таким образом, предложенный метод повышает коэффициент пользовательской готовности МП в крайнем случае на 8 %.

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

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

- „о -

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

а схемы на мультиплексорах /V- -1-, ; для МП ПС2100

С-1 о

=450, Мг. =515. Следовательно, реализация схемы опроса на сдвиговых регистрах дает экономию оборудования =12,6 %.

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

- 21 -

ВЫВОДЫ, ТЕОРЕТИЧЕСКИЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ

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

1. На основе графовой модели и комбинаторных методов разработан метод синтеза микрокода, состоящий из решения вертикальной и горизонтальной задач и отличающийся от известных методов введением особых дуг в графовой модели, представлением N -выходных схем ti вершинами графа и использованием наличия в программе жестко связанных пар микрокоманд для уменьшения времени выполнения второй микрокоманды путем формирования управляющих сигналов для нее в первой микрокоманде. Показано, что применение упреждающего управления позволяет уменьшить время машинного такта для ПС2Ю0 со 180 не до 140 не, а предложенный метод решения горизонтальной задачи синтеза микрокода дает улучшение по комплексному критерию на 26 %.

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

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

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

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

статически; показано, что при оптимальной плотности контроля коэффициент пользовательской готовности в 3,5 раза больше, чем в системе без программного контроля.

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

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

6. Обоснован выбор структуры и схемотехники основных узлов устройства управления.

7. Разработан и освоен в серийном производстве мультипроцессор ПС2100.

Основное содержание диссертации отражено в следующих опубликованных работах:

1. Власенко Л.Я., Итенберг И.И., Набатов A.C., Хейфец В.И. Мультипроцессор ПС2Ю0. - Тезисы докладов Всесоюзной научно-технической конференции "Опыт'разработки и внедрения технических и программных средств СМ ЭВМ и АСВТ-ПС". Северодонецк, 1986

2. Набатова Т.Л., Хейфец В.И., Ященко В.И. Опыт разработки устройств с применением полузаказных БИС. - Тезисы докладов Всесоюзной научно-технической конференции "Опыт разработки и внедрения технических и программных средств СМ ЭВМ и АСВГ-ПС". Северодонецк, 1986.

3. Белилыцикова Н.В., Набатов A.C., Хейфец В.И. Общая организация средств локализации неисправностей в многопроцессорной вычислительной системе типа MIMB-SIMD . - УСиМ, 1988, № 4 - с.7-9.

4. Хейфец В.И. Исследование модели периодического программного контроля с переменной плотностью для мультипроцессора ПС2100. - Тезисы докладов 1-й Всесоюзной конференции "Однородные вычислительные среда и систолические структуры". Львов, 1990 .

5. Данильченко С.И., Итенберг И.И., Набатов A.C., Хейфец В.И., Ященко В.И. Мультипроцессор Ж2Ю0. - Тезисы докладов 1-й Всесоюзной конференции "Однородные вычислительные среда и структуры". Льэов, 1990.

г 24 - "

6. Данильченко С.И., Итенберг И.И., Набатов A.C., . Хейфец В.И., Ященко В.И. Мультипроцессор ПС2Ю0 - ПСиУ, 1990, №9.

7. Данильченко С.И., Итенберг И.И., Набатов A.C., Хейфец В.И., Ященко В.И, Модуль базовый ÜC2I00: архитектура, структура, особенности реализации. - Тезисы докладов Всесоюзной научно-технической конференции "Опыт разработки и внедрения средс: серии ПС", Северодонецк, 1991.

8. Хейфец В.И. Об одном • зтоде оптимизации микрокода параллельного мультипроцессора. - Т.зисы докладов Всесоюзной научно-технической конференции "Опыт разработки и внедрения средств серии ПС". Северодонецк, 1991,

9. Хейфец В.И., Власенко Л.Я. Архитектура УУ МБ ПС2Ю0. -Тезисы докладов Всесоюзной научно-технической конференции "Опыт разработки и внедрения средств серии Ш". Северодонецк, 1991.

10. Хейфец В.И., Данильченко С.И. Сопряжение МБ 1Ю2Ю0 с IBM PC. - Тезисы докладов Всесоюзной научно-технической коррекции "Опыт разработки и внедрения средств серии ПС". Северодонецк, 1991.

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

По работам, оцубликованным в соавторстве, личный вклад диссертанта состоит в следующем: в [I, 5"" 7} предложена структура устройства управления Ш, в [2] предложена схемотехника узлов обработки мантисс и порядков ПЭ ПС2Ю0, в [3] предложена структура и схемотехника узла управления диагностикой, в С93 предложена методика выбора структуры основных узлов устройства управления МП, в [IOj предложена организация сопряжения управляющего интерфейса Ml с интерфейсом ПЭВМ.