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

ВВЕДЕНИЕ .5"

ГЛАВА I. ОРГАНИЗАЦИЯ УПРАВЛЕНИЯ РАСПРЕДЕЛЕНИЕМ РЕСУРСОВ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С ПЕРЕСТРАИВАЕМОЙ СТРУКТУРОЙ .'

1.1. Связь между структурой вычислительной системы и классами решаемых задач. Концепции вычислительных систем с перестраиваемой структурой . tl

1.2. Постановка задачи выбора структур распределяемого поля ресурсов МВСПС .2У

1.3. Принципы организации системы выбора структур РПР

ВЫВОДЫ.

ГЛАВА 2. ФОРМАЛИЗАЦИЯ ПРОЦЕССА ВЫБОРА СТРУКТУРЫ ОБЪЕКТА

В УСЛОВИЯХ НЕСТАЦИОНАРНОЙ ВНЕШНЕЙ СРЕДЫ

2.1. Исходные положения формализации процесса выбора структуры в условиях нестационарной внешней среды. so

2.2. Построение аппарата настройки ИЛС на внешнюю среду.57 2^3. Решение задачи сокращения объема перебора вариантов структур на ГК.W

2Л. Сокращение объема перебора при решении задачи дискретной оптимизации на ГК

2.5. Разработка методики установления оптимального соответствия между сегментом задачи и структурой РПР с использованием аппарата ИЛС

ВЫВОДЫ .W

ГЛАВА 3. ПОСТРОЕНИЕ МОДЕЛЕЙ ПОКАЗАТЕЛЕЙ КАЧЕСТВА ДЛЯ

РЕАЛИЗАЦИИ ПРОЦЕССА ВЫБОРА СТРУКТУР И ЗАГРУЗКИ

РЕСУРСОВ ВС .tot

3.1. Принципы построения моделей оценки качества структур РПР .Ш

3.2. Использование ИЛС в качестве аппарата оценки загрузки ресурсов РПР. Организация информационнологической системы планирования . и*

ВЫВОДЫ

ГЛАВА 4. РАЗРАБОТКА СИСТЕМЫ ВЫБОРА СТРУКТУР РПР МВСПС,. nt

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

4.2. Автоматическая система выбора структур РПР . i$

4.3. Информационно-логическая система планирования загрузки РПР

ВЫВОДЫ

ГЛАВА 5. ИСПОЛЬЗОВАНИЕ СИСТЕМ ВЫБОРА СТРУКТУР РПР И

ПЛАНИРОВАНИЯ ЗАГРУЗКИ РЕСУРСОВ РПР ПРИ РЕШЕНИИ ЗАДАЧ ПРОЕКТИРОВАНИЯ ВС

5.1. Решение задачи выбора структур для системы управления настройкой структуры ВС с перестраиваемыми групповыми процессорами.{

5.2. Решение задачи выбора структуры ВС пилотажно навигационного комплекса МИ-8М.

5.3. Решение задачи выбора оптимального соотношения ресурсов ВС автоматизированной системы управления полупроводниковыми преобразователями для сварки панелей.2/

ВЫВОДЫ

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

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

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

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

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

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

3. Разработать метод планирования загрузки ресурсов РПР;

4. Осуществить практическую программную реализацию разработанных методов и алгоритмов в системах автоматического вдбора структур РПР и планирования загрузки ресурсов РПР МВСПС.

В качестве основы для построения системы выбора структур РПР и планирования загрузки РПР использован аппарат информационно-логических систем (ИЛС), предложенный проф.Шигиным А.Г. в 1969 г. и развитый в работах /76,78,83/,

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

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

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

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

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

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

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

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

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

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

Рассмотрен вопрос сокращения объема перебора в процессе выбора оптимального варианта структуры на семантически упорядоченном ГК. Получен алгоритм поиска оптимума по обобщенному критерию качества вида: К~ Qt'Zi + Clz» где %2 «показатели качества структуры объекта.

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

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

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

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

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

На основе полученных результатов разработаны алгоритмы работы: а) системы выбора структур РПР; б) системы планирования загрузки ресурсов РПР.

Глава 4- посвящена практической реализации разработанных методов и алгоритмов в программные системы выбора структур РПР и планирования загрузки ресурсов РПР сегментами задач, описанными в системе команд ЕС ЭВМ.

Разработаны и программно реализованы следующие программные системы:

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

2. Информационно-логическая система планирования (ИЛСП),

- Si' осуществляющая формирование плана загрузки ресурсов PUP сегментами задач.

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

В главе 5 описываются примеры практического использования разработанных программных систем. Данные системы использованы при проектировании системы управления полупроводниковыми преобразователями для сварки панелей в Институте электродинамики АН УССР, при проработке структуры ВС пилотажно-навигационного комплекса МИ-8М в НИИ Авиационного Оборудования и при разработке системы управления ВС на базе перестраиваемых групповых процессоров ВСПГП в рамках НИР № У78518, проводимой в МЭИ совместно с НИЦЭВТ.

Также проведена оценка эффективности как отдельных алгоритмов, так и программных систем в целом при помощи машинных экспериментов на ЭВМ EC-I033.

В приложении I приводятся доказательства теорем, отдельные формальные преобразования.

В приложении 2 описаны решения некоторых вопросов организации РПР: вопрос построения коммутационной сети РПР на основе настраиваемых коммутационных элементов (НКЭ); вопрос организации режима разделения времени в службах РПР.

В приложении 3 даны листинги отдельных алгоритмов и программных систем АСВС и ИАСП в целом, описанных на языке ПЛ-1 ОС ЕС, а также распечатки результатов работы данных программных систем.

I. ОРГАНИЗАЦИЯ УПРАВЛЕНИЯ РАСПРЕДЕЛЕНИЕМ РЕСУРСОВ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С ПЕРЕСТРАИВАЕМОЙ СТРУКТУРОЙ

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

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

Появление вычислительных систем (ВС) различной структурной организации и их использование при решении разнообразных прикладных задач показало, что технико-экономические показатели (ТЭП) ВС в значительной степени зависят от особенностей

- /зклассов, решаемых задач. Как показало в ряде работ jl2?5/y соответствие структуры ВС классам решаемых задач является одним из наиболее существенных факторов влияющих на ТЭП ВС. В связи с этим, задача выбора структуры ВС, т.е. выбора состава компонент, способа организации связей между компонентами и алгоритмов функционирования, в значительной степени зависит от того на решение каких задач ориентирована ВС. Любая задача, решаемая на ВС характеризуется некоторой структурой алгоритма и структурой данных. Структуру алгоритма решения задачи можно, согласноISTfiU, представить в виде информационного графа (ИГ) (рис.1.1а), вершинами которого являются операторы преобразования данных (У), дуги же соответствуют путям передачи информации между соответствующими вершинами. Оператором может являться отдельная команда или группа команд, представляющая часть процедуры решения задачи (рис.1.16). Каждой команде соответствует совокупность исходных данных - операндов (рис.1.16). Данные имеют определенную структурную организацию в виде: скаляров, векторов или матриц. Очевидно, что решение задачи на ВС требует аппаратного обеспечения операторов задачи - вершин ИГ устройствами обработки и хранения данных, а дуг ИГ - каналами передачи информации. В случае, если структура ВС аппаратно отображает ИГ некоторой задачи, может быть достигнута максимально возможная производительность ВС, однако такая ВС будет узкоспециализированной, т.е. ориентированной на решение одной аппаратно запрограммированной задачи. Создание таких ВС целесообразно в тех случаях, когда ВС предназначена для многократного решения одной и той же задачи с различными исходными данными/^82!.

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

Г)

Рис. IЛ. Представление задач в виде информационного графа: а- общий вид информационного графа; б- представление оператора задачии и связанных с ним данных. обработки. Известны следующие способы организации ВП j6ij .

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

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

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

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

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

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

Способы организации ВП определяют структуры реализующих их ВС:

I. ВП последовательно-командной организации реализуется по существу любым многофункциональным устройством обработки данных - процессором (рис.1.2а). Совокупность устройства управления (УУ) памяти (П), канала передачи информации (К) и процессора (Пр) и определяет структурную организацию вычислительного устройства реализующего данный вид ВП. Примерами подобных ft nP T a) n

К— 0 m

2>

CUD H

S)

МП МП МП

73 П Э <3=J> п э

ТУ on

НС

0<РГ7 е)

Рис. 1.2. Структуры вычислительных систем: а- многофункциональные однопроцессорные вычислительные устройства; б- командо-магистральные ВС; в- арифметико-магист-ральные ВС; г- многопроцессорные ВС с независимым управлением; д- многопроцессорные ВС с общим управлением; е- ВС с управлением но потоку данных. устройств могут являться любые ЭВМ 1-го, 2-го и 3-го поколений. Главным достоинством последовательно-командной организации ВП на структуре ЭВМ является наибольшая гибкость управления, т.к. каждая пара скалярных операндов сопровождается управляющей командой. Однако в связи с последовательным характером обработки команд при подобной организации структуры невозможно обеспечить ускорение процесса обработки задачи за счет естественного параллелизма в структуре алгоритма, отображаемого ИГ. Невозможно ускорить и процесс обработки данных, т.к. в случае векторного или матричного характера представления данных необходимо циклически реализовать одну и ту же комннду алгоритма решения задачи для каждого элемента вектора или массива. Поэтому наиболее эффективно использовать вычислительные устройства рассматриваемого типа для решения задач, ИГ которых характеризуется возможно малым числом ветвлений, данные не имеют скалярную организацию.

2. ВП последовательно-потоковой организации реализуется командно-магистральными ВС (рисЛ.26). Характерной особенностью структурной организации ВС этого типа является наличие нескольких функционально-ориентированных устройств обработки данных (ФОД). Примерами таких ВС могут являться СДС 6600; СДС 6700; IBM 370/168 ! 12,17!. ВС с командно-магистральной организацией структуры обладают всеми достоинствами ЭВМ, реализующих последовательно-командный тип ВП. Более высокие показатели быстродействия и других ТЭП в командно-магистральных ВС обеспечиваются функциональной ориентацией устройств обработки данных, а также возможностью параллельной обработки нескольких команд, если они требуют различные ФОД. Использование командно-магистральных ВС для задач с векторной организацией данных крайне неэффективно, т.к. поэлементная обработка вектора на одном из

- /«

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

3. ВП последовательно-групповой организации реализуется арифметико-магистральными ВС (рис.1.2в). Особенностью организации структуры этих ВС является построение процессора в виде конвейера специализированных устройств преобразования данных (СПД), каждый из которых ориентирован на выполнение определенной фазы обработки команды. Примерами ВС такого типа являются системы: BTAR~(lDD, ASC /iZ,171 .

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

4-. ВП параллельно-командной организации реализуется многопроцессорными ВС (рис.1.2г). Структура этих ВС содержит, как правило, ряд многофункциональных процессоров, с независимым управлением (ПР), реализующих последовательно-командный тип ВП, модули оперативной памяти (МП) и комутатор связей (КС) типа "каждый с каждым". Примерами ВС такого типа являются ВС : В6700, Эльбрус-3/ /2/.

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

5. ВП параллельно-групповой организации реализуется ВС с общим управлением (рис.1.2д). К ВС этого типа относятся матрич ные и ассоциативные системы. Примерами подобных ВС являются системы TLLJA0-IV) В$Р; Pzopai-2; DAP ; IBM 3838/0// Особенностью структурной организации этих ВС является наличие в них многофункциональных процессорных элементов (ПЭ), работающих под управлением одного устройства управления (У) межпроцессорные связи в этих ВС выполнены по принципу близкодействия и носят регулярный характер. В связи с этим ВС с общим управлением эффективно решают задачи с высокой степенью естественного параллелизма/35,6f/% К задачам этого класса относятся: задачи обработки информации от множества датчиков, задачи моделирования в однородной среде, задачи распознавания образов;обработки геофизической информации и др. Характерной чертой ИГ этих задач является наличие ряда информационно несвязанных (или слабо связанных) ветвей, операторы которых осуществляют обработку независимых потоков данных по идентичной процедуре. Другим классом задач, эффективно решаемых на ВС с общим управлением ' являются задачи с параллелизмом ветвей !^,Bf/t отличаются наличием в ИГ перекрестных и главным образом регулярных связей между операторами параллельных ветвей. В числе задач подобного класса - задачи матричной алгебры, линейного программирования, спектральной обработки сигналов, прямого и обратного преобразования Фурье и Адамара и др. Структура данных этих классов задач носит ярко выраженный векторный и матричный характер. В случае, если вышеупомянутые условия, налагаемые на структуру алгоритма и данных, не выполняются, то использование матричных или ассоциативных ВС становится неэффективным, т.к. значительное число ПЭ окажется незагруженным и будет простаивать. б. ВП параллельно-потоковой организации реализуется ВС, построенными по принципу управления потоком данных "Data F£ow" (рис.1.2е). Структура этих ВС базируется на однофункциональных преобразователях (ОФП) связанных с общей памятью через коммутатор (КС). Примером подобной ВС может служить система АМД-290 /23,55/Эти ВС относятся к классу ВС со структурой, имеющей возможность настройки на решаемую задачу и более подробно будут рассмотрены ниже.

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

Следовательно, если ВС предназначается для решения задач различных классов, т.е. Зг^ const , то для того чтобы поддерживать значения ТЭП ВС на максимально возможном уровне, необходимо чтобы структура ВС - &1Ф const , т.е. имела бы возможность перестройки с целью отображения индивидуальных особенностей информационного графа и структуры данных решаемой задачи.

Концепция многопроцессорных ВС с переменной струкутрой (МВСПС) впервые была предложена в работе /30/ и известна как концепция машины Эстрина. Эта концепция была заложена в проект макромодульных машин. Структура подобной системы допускает изменения межмодульных связей в зависимости от характера решаемой задачи. Модулями в системе являются регистры, сумматоры, блоки памяти, блоки управления. Межмодульные связи осуществляются блоками связи. Изменения структуры, т.е. набора функциональных модулей системы связей осуществляется либо электромеханически при помощи переключателей, либо посредством электронных схем под управлением супервизорной системы. Пример подобной машины приведен в работе f 37/ .

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

В работах Евреинова Э.В., Косарева Ю.Г. и др. 128,29/.предложена концепция ВС с настраиваемой структурой, получившая название "однородной вычислительной среды". Основным принципом является использование в системе одинаковых устройств обработки данных (процессоров, мини-ЭВМ и т.д.) с программноуправля-емой системой межпроцессорных связей. Концепция "однородной среды" реализована в ряде отечественных ВС : СУММА /10 j , ММИНИМАКС ! 9/ и др.

Система СУММА (Система управляющая минимашинная) является модульной однородной системой с программируемой системой межпроцессорных связей. Управление настройкой связей осуществляется операционной системой на основе стандартного набора конфигураций межпроцессорных связей. Операционная система позволяет настраивать структуру ВС СУММА на режимы матричной, магистральной и мультипроцессорной работы. Выбор режима работы ВС путем программной настройки структуры является большим достоинством системы, однако такая настройка позволяет учитывать лишь наиболее общие черты класса решаемой задачи и не учитывает ее конкретных особенностей. Система МИНИМАКС (Минимашинная программно-коммутируемая система) также является модульной однородной ВС и имеет программно-перестраиваемые межпроцессорные связи. Структура ВС содержит элементарные машины (ЭМ), состоящие из ЭВМ на базе М-6000 и системного устройства, осуществляющего взаимодействия с 4—мя соседними ЭВМ путем программной коммутации связей. Управление настройкой в данной ВС организовано таким образом, что в системе может быть образовано несколько подсистем, включающих одну или несколько ЗМ и работающих независимо. Подсистемы из ЭМ создаются и уничтожаются в процессе функционирования ВС, т.е. настройка связей носит динамический характер. Операционная система МИНИМАКС обеспечивает параллельную обработку информации, автономную работу ЭМ, а также режим смешанного функционирования, когда одна подсистема осуществляет параллельную обработку, а другие ЭМ работают автономно. Динамическое управление настройкой связей, возможность разбиения структуры на ряд автономно работающих подсистем позволяют достаточно гибко использовать вычислительные ресурсы системы. Однако эффективность управления настройкой структуры в этом случае зависит от того, насколько часто в процессе решения возникает необходимость в параллельной обработке данных.

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

Еще одним подходом к построению ВС с настраиваемой на решаемые задачи структурой является подход получивший название " Data FEow " (поток данных). Основной принцип этого подхода - управление ходом вычислений потоком данных. Основными моделями структур подобных ВС являются $М - мащина {Search mode) и IM-машина (Inteiconnection mode ), предложенные Милером и Коком 1471 . Характерным свойством обоих моделей является возможность динамической реконфигурации их структуры. Перестройка осуществляется перекоммутацией процессоров, соответствующих операторам потоковой программы, согласно структуре этой программы. Благодаря возможности реконфигурации потоковая ВС потенциально способна достигнуть той же производительности, что и специализированные ВС, оставаясь достаточно универсальной. Однако как отмечено ъ1ВЗ,ВЧ1 производительность потоковой ВС зависит главным образом от пропускной способности устройства управления, которое существенно влияет на эффективность использования процессоров. Причиной этого влияния является тот факт, что устройство управления должно осуществлять формирование управляющих воздействий в темпе поступления операторов решаемых задач, т.к. реконфигурация структуры ВС должна осуществляться по мере готовности операторов задачи к обработке. Снижение частоты перестройки структуры ВС возможно, если осуществлять настройку структуры на более крупные части задачи, нежели отдельные операторы. Этот принцип используется в отечественных системах с перестраиваемой структурой, концепция которых развивается в Институте проблем управления под руководством акад. Прангишвили И.В. / 6D/, В ВС этого типа осуществляется выделение в программе решаемой задачи определенных конструкций (линейных участков, циклов и т.п.), далее в процессе трансляции осуществляется объединение выделенных программных конструкций в параллельные операторы, после чего формируется параллельные ветви программы. За каждой ветвью на время ее обработки закрепляются необходимые вычислительные устройства (блоки обработки команд, арифметико-логические модули и др.). Организация структуры в виде функционально-ориентированных модулей, образующих поля памяти, ввода-вывода, обработки команд, арифметико-логической обработки позволяет осуществлять гибкое рас

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

Построение системы управления перестройкой структуры ВС на основе формализованной системы выбора оптимальных структур заложено в основу концепции ВС с перестраиваемыми групповыми процессорами (ВСПГП). Эта концепция ВС с перестраиваемой структурой развивается в Московском энергетическом институте под руководством проф.Шигина А.Г.

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

- 2Qоптимальных структур РПР для сегментов, всвязи с большой мощностью множества возможных состояний структур РПР ВСПГП. Поэтому в работе /$б/ было предложено использовать специальную формализованную систему выбора структур, которая с учетом особенностей решаемых задач автоматически осуществляла бы выбор структур групповых процессоров ВСПГП, что позволило бы значительно повысить ТЭП всей вычислительной системы.

Всё вышесказанное позволяет сделать следующие выводы:

1. Структура ВС и реализуемый ею тип ВП определяет проблемную ориентацию ВС на те или иные классы задач;

2. Необходимость повышения ТЭП ВС при решении задач различных классов приводит к концепциям ВС с перестраиваемой структурой (МВСПС);

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

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

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

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

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

ВЫВОДЫ

В данной главе решены следующие задачи.

1. Разработана система выбора структур распределяемого поля ресурсов для ВС на базе перестраиваемых групповых процессоров (ВСПГП) на основе программных систем АСВС и ИЛСП. На основе машинных экспериментов (на ЭВМ ЕС-ЮЗЗ) показана эффективность использования данных программных систем в составе системы управления настройкой структуры ВСПГП на решаемые задачи.

2. Решена задача выбора структуры ВС пилотажно-навигацион-ного комплекса вертолета МИ-8М с использованием программных систем АСВС и ИЛСП. Полученные результаты позволили минимизировать аппаратные затраты на реализацию ВС данного комплекса.

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

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

ЗАКЛЮЧЕНИЕ

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

Совокупность разработанных алгоритмов, методов и средств преследует цель повышения ТЭП МВСПС путем компенсации изменения значений показателей качества МВСПС при изменении параметров внешней среды МВСПС (совокупности решаемых на ВС задач) целенаправленной перестройкой структуры ВС.

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

1. Разработаны теоретические положения, являющиеся основой построения ИЛС для объектов, функционирующих в нестационарной внешней среде.

2. Создан метод автоматического формирования аналитических оценочных функций показателей качества "время обработки сегмента задачи", основанный на интерпретации команд сегмента задачи во фрагменты оценочной функции. Данный метод реализован в программной системе конструирования оценочных функций (СКОФ).

3. Разработана методика установления соответствия между сегментом задачи, представленном на уровне команд и структурой РПР, основанная на использовании настраиваемой ИЛС в качестве аппарата соответствия.

- ггч

Разработан метод планирования загрузки ресурсов РПР, основанный на использовании настраиваемой ИЛС в качестве аппарата коррекции дисциплины загрузки сегментов задач в МБ СПС.

5. На основе разработанного комплекса алгоритмов, методов и средств построены и программно реализованы: автоматическая система выбора структур (АСВС); информационно-логическая система планирования загрузки ресурсов РПР (ИЛСП). Данные системы использованы при разработке системы управления перестройкой структуры ВС с перестраиваемыми групповыми процессорами (ВСПГП), которая осуществлялась в МЭИ совместно с НИЦЭВТ в рамках НИР № У78518, а также при проектировании системы управления полупроводниковыми преобразователями для сварки панелей в Институте электродинамики АН УССР и в НИИ авиационного оборудования (НИИАО) при проработке структуры ВС пилотажно-навига-ционного комплекса МИ-8М.

1. Арлазаров В.Л., Волков А.Ф., Лысиков В.Т., Фараджев И.А. Архитектуры многопроцессорной вычислительной системы.-В кн.: Многопроцессорные вычислительные системы.-М.: Наука,1975,с. 12-19.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир, 1979 536с.

3. JJdorn T.L.j Gh&ndy K.N.y Diskson J.R. rf comparison oj list stheo/и €es /ог рач&£€ев ргocessiно/

4. SCsiem . Com un /1СМt /9/4 , f. //, У* iBt p. ets- €30,

5. Барский А.Б. Планирование параллельных вычислительных процессов. -М.: Машиностроение, 1980 192с.

6. Барский А.Б., Бахарев В.М., Безденежных Н.П. и др.-Некоторые вопросы диспетчеризации вычислительных систем.- Вопросы радиоэлектроники. Сер. Электронная вычислительная техника, 1974, вып.8, с.27-42.

7. Батищев Д.И. Поисковые методы оптимального проектирования.-М.: Советское радио, 1975 215с.

8. Васильев Ф.П. Численные методы поиска экстремума.-М.:Наука, 1980 546с.

9. Виноград Т. Программа, понимающая естественный язык.-М.:Мир, 1976 294 с.

10. Винокуров В.Г., Дмитриев Ю.К., Евреинов Э.В., Костелянский

11. Woods Trot л si iicn /Veiu/схк GzG/m/n&7S /or jVatvt?a€ Language Ano/€tys(s . Cornmanieatt osts foz the Лssoci.aiierrs /or Computing Machinery, v. /J 76/ /9/0.

12. Головкин Б.А. Параллельные вычислительные системы.-М.:Наука, 1980 520 с.

13. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов.-М.: Радио и связь, 1983 272 с.

14. Головкин Б.А. Классификация методов диспетчеризации работы многопроцессорных и многомашинных вычислительных систем.-Управляющие системы и машины, 1982, № 3, с.3-11.

15. Глушков В.М. Основы безбумажной информатики.-М.: Наука, 1982 552 с.

16. Глушков В.М. Некоторые проблемы теории автоматов и искусственного интеллекта.- Управляющие системы и машины, Киев: Наукова Думка, 1970, № 2, с.3-13.

17. Gtaham Uff. The pexePPei апе/ ihe pipe^cfte compuieis-- Datamation f 1970f f£, p. П 71.

18. Горбатов В.А. Система управления, ЦВМ и графы.-М.:Энергия, 1971.

19. QontaUs M.I. ietetministlc piocessop schbdufcnfl Computing sur reus f /9 77, i/.9/ p. 173 20Ц.

20. Голубев Новожилов Ю.С. Многомашинные комплексы вычислительных средств.- М.:Советское радио, 1967 - 424 с.

21. Дерюгин А.А., Иванов В.Е. Методика проектирования ЗУ на фер-ритовых сердечниках с помощью ЦВМ. Труды МЭИ, 1976, Ш 303, с.57-60.

22. Дерюгин А.А., Хороманьска Ив. Вопросы автоматизированного проектирования ЗУ различных систем, с общей разрядной обмоткой, Труды МЭИ, 1978, № 380, с.12-17.

23. Dentins У,В., Nisuncts Z,P. A preCiminaty axchiieciaye fox a Basic data f€ou/ processor.- : . of theьесоиЫ Ann*. St//np. of the Ccmput. Architect./У.Ру J BEE / 197S/ p.{2€-f32.

24. Дешко А.И., Игнатенко Б.В., Костюк В.И. Информационная модель проблемной области в системах принятия решений. Кибернетика, 1983, № I, с.46-48.

25. Дзегелёнок И.И. Механизм активной адаптации.-Известия АН СССР: Техническая кибернетика, 1971, te I, с.142-153.

26. Дзегелёнок И.И. Принцип дискретной оптимизации с вариацией уровней нелокального поиска.- Тр/Моск.энерг.ин-т,1975,вып. 216, с.49-52.27. fiijkstra E.f A note сп two ptoBBem in Connection with Graphs, flunteiische tfc/tefn&tic f л*/y /0S$y p 2CS-27/.

27. Евреинов Э.В., Косарев Ю.Г. Однородные вычислительные системы высокой производительности.- Новосибирск: Наука, Сибирское отделение, 1966 308 с.

28. Евреинов Э.Б. Однородные вычислительные системы и среды.-В кн.: Вычислительные средства в технике и системах связи. Вып.З. М.:Связь, 1978, с.3-16.

29. EstxCri G. Organisation of computer system: the fuxed pCus i/axiaSte structure computet/!/at. Уос/it Compui Committee Conf. Ptoc.f i960 f k/estett? Joint Cotnput . Cohf. I/./?, p.33- f/O.

30. Ефимов Е.И. Решатели интеллектуальных задач.-M.:Наука, 1982 316 с.

31. Quzet У. ТгеЬагеп P.A. //ighCy pazefM computer aichL{ecture,TR.2)ept. Ccmput • Sci t/Ш Manthe^1976, Apr.

32. Каляев А.В. Многопроцессорные вычислительные системы с программируемой архитектурой.-М.: Радио и связь, 1984 329с.

33. Карп P.M., Миллер Р.Е. Параллельные схемы программ.-В кн.: Кибернетический сборник, М.: Мир,1975,вып.13, с.5-61.

34. Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика.-М.: Радио и связь, 1981.

35. Кирищян Л.Г., Шигин А.Г. Внешняя среда и семантическое упорядочение графа конструирования в информационно-логических системах проектирования.-Тр/Моск.энерг.ин-т,1983, вып.614, с.72-76.

36. Свагк U/.rf. Meczomocfafar compute* stysteM* /IF/PS Conf Ргос (96У/ sysC y i/. зоf p. 333 336.

37. Клыков Ю.й. Ситуационное управление большими системами.-М.: Энергия, 1974 134с.

38. Косарев Ю.Г., Миренков Н.Н. Математическое обеспечение однородных вычислительных систем.- В кн.: Вычислительные системы, Вып.58.Новосибирск: ММ СО АН СССР,1974, с.61-79.

39. Кузин Е.С., Фоминых Й.В., Хахалин Г.К. Системы принятия решений в интегральных работах /Обзор/.- В кн.: "Интегральные роботы", Вып.2, М.: Мир,1975, с.364-377.

40. Летичевский А.А. Функциональная эквивалентность дискретных преобразователей.-Кибернетика, 1969, N2 2, с.5-15; 1970, № 2, с.14-28.

41. Luckhctm А С. / Pavk D.M., Paiexsen M.S. бп formalized сcmpu-tex p^oft&MS.- У. Compat. Syst. See, 1970, р.2го-2«Э.

42. Методы автоматизированного анализа и синтеза перестраиваемого группового процессора: Отчет/МЭИ; руководитель работы А.Г.Ши-гин.- № ГР У78518, № Г 39757.- М., 1983 90с.

43. Методика и средства автоматизированного проектирования вариантов структур ВС на базе перестраиваемого группового процессора с динамическим микропрограммным управлением: Отчет/МЭИ; руководитель работы А.Г.Шигин.- № ГР У78518, № Г 39758.-М., 1984 90 с.

44. Мики Д. Формирование и выполнение планов вычислительной машиной.- В кн.: "Интегральные работы". М.: Мир,1975, с.378-405.

45. Миллер Р.Е., Кок Дж. ЭВМ с изменяемой конфигурацией: новый класс вычислительных машин. Пер.с англ.- В кн.: Теория программирования. Труды симпозиума. Новосибирск: ВЦ СО АН СССР, 1972, с.121-131.

46. Минский М. Психология машинного зрения.-М.: Мир,1978.

47. Минский М. Фреймы для представления знаний.-М.: Энергия,1979.

48. Мороховец Ю.Е. Проектирование структур многопроцессорных систем оперативной обработки данных с заданным уровнем производительности." Сб.Тр/Моск.энерг.ин-т, 1982, вып.544, 4с.

49. Мясников В.А., Игнатьев М.В., Торгашев В.А. Рекурсивные вычислительные машины.-М.: ИТМ и ВТ АН СССР, 1977, Препринт12 Збс.

50. Нильсон Н. Искусственный интеллект.-М.: Мир, 1973.

51. Ондаш И. Алгоритмы распределения ресурсов однородной многопроцессорной системы.-В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем.-М.: Наука, 1982, с.292-319.

52. Организация работы ВЦ "ОРГВЦ-Г1.-Калинин: Статистика /изд. Минприбор/, 1980.-2 ЪО

53. РСаз A. LAV system aicfiUtciure : A parage/ o(aia efti t/en ptccessfiz £а.$ес/ ей Sthyfe asscf/i-metit 7и : Ргос . of t£e ff7'c j-fitctn. Сон/.он paT&fCee Ptocebbtnj f p. 29$- Ъ<Э2.

54. Половинкин А.И. Автоматизированный синтез оптимальных структур технических систем.-Известия АН СССР. Техническая кибернетика, 1973, № 5, с.62-68.

55. Поспелов Д.А. Введение в теорию вычислительных систем.- M.s Советское радио, 1972 280 с.

56. Поспелов Д.А. Принципы ситуационного управления.-Известия АН СССР. Сер. Техническая кибернетика N2 2, 1971.

57. Потемкин И.С., Долматова Л.М., Иванова Н.А. Автоматическое проектирование функциональных схем сумматоров.-Труды МЭИ 1975, № 216, с.62-69.

58. Прангишвили И.В., Резанов В.В. Многопроцессорные управляющие вычислительные комплексы с перестраиваемой структурой.-М.: ИТМ и ВТ АН СССР, 1977, Препринт № 10, 25с.

59. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением.-М.: Энергоатом-издат, 1983 311с.

60. Рапопорт А. Математические аспекты абстрактного анализа систем." В кн.: Исследования по общей теории систем. Пер.с англ.-М.: Прогресс, 1969.

61. Ram&moozlhy CAetnJy Conz&fes MX, Ofo tСтав ichecft/tncr гпи&с-p toceSSO J* syslew . f£££ Ttans,1972, IS- С ?// /?. S3?

62. R им iauyh У.А. wuft eProcess** .1ЕЕ£ CotHfut., /ЭУУ / ^ Z

63. Слейгл Дж. Искусственный интеллект.-M.: Мир, 1973.

64. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации.-Киев: Наукова Думка, 1980 273с.

65. Таненбаум Э. Многуровневая организация ЭВМ.-М.: Мир,1979 -547 с.

66. Уинстон П. Искусственный интеллект.-М.: Мир, 1980 519с.

67. Файкс Р., Нильсон Н. Система новый подход к применению методов доказательства теорем при решении задач.

68. В кн.: "Интегральные роботы".-М.: Мир, 1973, с.382-403.

69. Флинн М. Сверхбыстродействующие вычислительные системы.-Труды ИИЭР, 1966, т.54, №> 12, с.311-320.

70. U66так У.2). Po^nom.iet£ compCttt iche.<?(a рГйв?ем$ . Rexkefeyl Unit/. Ca£cf. COMput. Set Яе/rt., TQ-*/«3i Мат., /9УЪ .

71. Нат.* P. / AfStiSOv //., Petf>Aae£ В., AasCc Jdt tAe f-Uu te'sf Cc S^e^e tfnina ticvi of Mс nih>7иf*t Cos t Pdifisrf £££ Ггшгз с/1 S</st.

72. S'ci, а Сс/бети., S SC ^ p. Ш-/07, /fee.

73. Хомский H. Логические основы лингвистической теории.- В кн.: "Новое в лингвистике", Вып.4, 1965, с.465-575.

74. Шахбазян К.В., Тушкина Т.А., Сахранская B.C. и др. Эксперимент по реализации алгоритмов диспетчеризации для многопроцессорных систем.- Управляющие системы и машины. Киев: Наукова Думка, 1975, № 3, с.103-105.

75. Шигин А.Г. Некоторые вопросы программного моделирования при проектировании ЦВМ.-Выч.сист.,АН СССР СО, Институт математики № 4, 1969, с.107-114.

76. Шигин А.Г., Кемельмахер Г.Л. Информационно-логическая система проектирования операционных частей ЦВМ.-Управляющие системы и машины. Киев: Наукова Думка, 1973, № I, с.52-58.

77. Шигин А.Г., Дерюгин А.А. Цифровые вычислительные машины.-М.: Энергия, 1975 536с.

78. Шигин А.Г., Мороховец Ю.Е., Федорова О.И. Модель информационного процесса для проблемно-ориентированных СООД.-Сб.Тр/Моск. энерг.ин-т, 1981, вып.496, 5с.

79. Шигин А.Г., Федин В.А. Модель процесса проектирования для автоматизированного проектирования информационно-логического типа.-Управляющие системы и машины. Киев: Наукова Думка,1977, № 2, с.84-88.

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

81. Эстрин Г. Микроэлементы в системах обработки информации.-Пер. с англ.-В кн.: Микроэлектроника и большие системы.-М.: Мир, 1967, с.30-41.

82. ПРИЛОШЕНИЕ I Доказательства теорем и некоторые теоретическиеположения

83. Теорема I. Нестационарная служба 1-го рода может быть декомпозирована единственным образом на две стационарные службы не связанные по показателю качества.

84. Если службы XirKXij не связаны по показателю качества, тоf ftфункция вклада службы Xij представляется как Fij = >

85. Тогда локальные приращения в группе с номером Z =т" \ , Г ft , , „' ff . -ft fffij)t = (Fit + Fij ) (FiZ +FijJ = Fij -Ft'j.fи в группе с номером (z+/)о" \ ' / ' " \ * "

86. Jtjh+i (F>л+1 4Ftj)-(Fiw + F-j4 J = F^j -Fij.tчто отвечает второму условию классификации.tf

87. Таким образом, если служба Xij стационарная и несвязанная поt показателю качества с , то локальное приращение службы Xitравно = ( Fir +Fij J {FiZ4 + Fij) = Fir

88. Если выполняется условие стационарности N2 3, т.е.

89. Г Fiji г Ь Fejlz-1 т-е- Ъг + Fij > Fiz4 + F-'j/ . д' / / и следовательно Fc't >, то У и ~ Fiz -/v?-/ Очто означает, что служба Xi7 также стационарна для всех

90. Таким образом нестационарная служба 1-го рода Xij может бытьдекомпозирована на две стационарные службы Xfa , ; Xij не связанные по показателю качества.

91. Теорема 2. Нестационарная служба 3-го рода может быть декомпозирована на две стационарные службы, параметрически связанные по показателю качества.

92. Доказательство. Пусть служба Xi i-i,P отвечает только условно классификации te I. Представим службу Xi эквивалентной композиf rfцией Xi и Xi .

93. Согласно условию классификации № I, тупиковые вершины графа 2>(Xi,£)= Gr(x'i ,£) * Н(Х;,£) могут быть разбиты на В групп по С вершин в каждой, причем в каждой группе локальное приращение положительно.к —

94. Fcj (Z;j ; Y) = F^ (ОС-г ; Y) * F-j х-; ; /(х'ь); Y.где * операция связи Р;г и .ч \ п

95. Упорядочим группы аг, 1-1,£ таким образом, чтобы FlC Jz+t > (Fu)zи соответственно пронумеруем вершины службы

96. Подбором вида функции / (Хсъ) и операции * можно добитьсячтобы выполнялось неравенство (f/)^>(f})zдля всех Z= , т.е. t / >,0 , а служба Xi% являлась бы стационарной.

97. Набор значений / (x'iz ) и * можно представить в виде системыпродукций вида:если Z-p $ то ¥(х'сг)= и т.д.

98. Таким образом, может быть осуществлена декомпозиция нестационарной службы 3-го рода.

99. Теорема 3. Нестационарная служба 4-го рода может быть декомпозирована на стационарные службы, связанные по показателю качества как параметрически, так и синтаксически.

100. Доказательство. Пусть Xij нестационарная служба 4-го рода.

101. Z- 1,(d*1) . Служба Xij может быть приведена к стационарному виду аналогично тому, как это сделано при доказательстве теоремы 3.

102. Если выполняется условие >а2-У(ц)тле ¥(Т), f(Q)локальные приращения функций Zz=W/Wb тупиковых

103. Рассмотрим двухярусный ГК, образованный службами

104. X2j еХ /г , TJnz Пусть в кустах функции качества Т и Q. линейно зависятот mi , причем У(т)»0; У(в)<0 (Рис.2.9а).

105. Если для всех Xti в кустах X^j выполняется условие af%(T)>cti-¥i(e)

106. Рис.2.9а), то для определения $оптнеобходимо вычислитьзначения Т и Q в тупиковых вершинах ГК $Хц ,Xn} — Kimihи определить Hmin = Win fК; min. •

107. Аналогично если для всех i-l^i Oi-%(т)>аг-%(4)Ееобходимознать величины 7 и Q в Sim2 , %itn2J и определить1. И min = min ^ win}

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

109. Пусть М- число элементов внешней среды в заданной системе элементов. Тогда £ число признаков-параметров идентификации У/>еУ,К~1,£ ,и число значений, принимаемых параметром идентификации у к определяется соотношением М ~ П 1к1. K-i

110. Вывод формулы оценки значений коэффициента компактности

111. Qcn iKz*' f!oqz ги) Тогда значения коэффициента компактности могут быть оценены отношением вида:£ T1U- Род, П гкy) 0нЛ м-е09гм jJi1. КОНГГ) Л — £ g1. Цср Z(7« ZlГк-Ь^г*)f к~t

112. ПРИЛОШЕНИЕ 2 Некоторые вопросы организадии вычислительного процесса в распределяемом поле ресурсов вычислительной системы с перестраиваемой структурой. Пример работы алгоритма планирования загрузки ресурсов служб РПР сегментами решаемых задач.

113. Некоторые вопросы организации распределяемого поля ресурсов МВСПС

114. Службу выборки команд (СВК) Xj

115. Службу обработки полей команды (СПК)

116. Службу подготовки адресов операндов (СПД) Х3

117. Службу выборки операндов (СВД) Х^

118. Службу обработки операндов (СОД) Х^

119. П2.УВ,г) величины Тк , поэтому ТСП.>^ 2ТК (Рис./7 2./).

120. Таким образом аппаратно-временное разделение ресурсов на1. Yi RR коп R1 R2 1. Yz RR коп R1 яг 1. Уз RX коп R1 Х2 82 7)21. Уч RR коп Ri R2 1