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

Для служебного пользования

Экз.№ £_

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

РУЧКИН Владимир Николаевич

УДК 681.32 681.621 519.4

ОПТИМИЗАЦИЯ СПЕЦИАЛИЗИРОВАННЫХ МУЛЬТИМИКРОПРОЦЕССОРНЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ

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

Автореферат

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

МОСКВА 1998

Работа выполнена на кафедре высшей и прикладной математики Рязанского института Московского государственного открытого университета

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

Левин В. К.

доктор технических наук, профессор, Смирнов Ю. М.

доктор технических наук, профессор, Петров О. М.

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

ЗгО

Зашита состоится ^" _ 1998г. в / ^ часов на

заседании диссертационного совета Д 053.18.02 при Московском государственном авиационном институте (технический университет) по адресу: 125871, г. Москва, Волоколамское шоссе, д. 4.

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

Отзыв на автореферат в одном экземпляре, заверенный печатью просим выслать по адресу: 125871, ГСП, г. Москва, Волоколамское шоссе, д. 4.

Автореферат разослан ' " ' 1998г.

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

Ю.В. Горбатов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Вопросам организации систем с параллельным принципом обработки. повышению живучести посредством диагностики и автоматизации проектирования с созданием интеллектуальных экспертных систем посвящены работы отечественных ученых И.В. Прангпшвили. B.C. Бурцева. Б. Бабаяна, В.Г. Лазарева, A.B. Каляева, Г.Т. Артамонова. В.И. Матова, К.А. Иыуду, В.Ю. Любатова, О.М. Брехова. Г.Н. Соловьева, В.Б. Смолова, И.П. Норенкова. Л.П. Коричнева. В.П. Корячко, Г.Г. Раннева, А.Н. Пылькпна. Ю.А. Маматова, В.А. Курчпдпса п др., а также зарубежных специалистов Б. Байцера. Э.А. Якубайтиса, М. Флинна, У.Р. Эшбн, Д. Данцига, П. Кортуа, Т. Ху, A.A. Саати, Л.А. Заде, Р. Галагера, Л. Клепнрока и др.

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

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

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

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

Задачи исследований.

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

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

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

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

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

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

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

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

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

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

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

4. Классификация структур мультимикропроцессорных (тМП) реализаций (тМПР) узла связи сети и получены аналитические соотношения для оценка производительности, простоя и затрат технических и программных средств.

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

6. Разработана экспертная система проектирования на основе предложенных методик расспараллеливания алгоритмов, классификации структур 111 МП систем и многокритериального выбора структуры

реализации узла связи сети первичной обработки информации в условиях неполной (нечеткой) априорной статистической информации.

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

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

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

Достоверность полученных в диссертации теоретических выводов подтверждена результатами:

- математического и имитационного моделирования полученных структур, методов, алгоритмов, диагностических тестов на ПЭВМ;

- апробации методик нечеткого выбора для рассматриваемых в работе тМП - систем обработки информации и диагностирующих тестов;

- эксплуатации программно - аппаратных средств в составе функционирующих систем УКС1 и УКС2[12,14];

- межведомственные и Государственные испытания аппаратуры передачи данных ПД - 440;

- войсковые испытания в реальных условиях эксплуатации Агрегативной многопроцессорной системы РАМС;

- создание сети передачи данных по ЦЗКС в ДВО, ПРИ ВО и СКВО РФ КЛО СВТ "Терминал" и АОЗТ 1СЬ;

- НИР и ОКР создания мультипроцессорных вычислительных систем с массовым параллелизмом в Институте проблем вычислительной техники РАН.

Научные положения выносимые автором па защиту:

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

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

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

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

- основы теории решения оптимизационных задач большой размерности посредством ее декомпозиции на ряд независимых подзадач меньше]'! размерности;

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

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

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

- Комплексная программа развития Единой системы научно - технических исследований на XII пятилетку (№ 223 от 9.07.85);

- Комплексная программа ГКНТ СССР 0.80.10 (№ 407/241 от 09.12.80);

- Межвузовская научно-техническая программа "Интеллектуальная собственность высшей школы(направлеши "Информатика" и "Микроэлектроника");

- Государственный заказ. Решение организации П/Я А-1572 ВП -8188 от 14.09.90г.;

- Государственный заказ. Решение организации П/Я А-1572 ВП -256 от 03.09.90г.

Выполненные НИР - ОКР(в которых соискатель был заместителем научного руководителя, ответственным исполнителем или руководителем раздела):

- НИР № 65-84 " Разработка декомпозиционных методов оптимизации конструкторских и проектных задач анализа и синтеза систем обработки измерительной информации" (гос.рег. № 81004968, 1984 г.);

- НИР № 69-85 "Создание САПР специализированной аппаратуры" (гос.рег. №01830056203,1985);

- НИР № 39-86 "Разработка устройства обработки сигналов датчиков

физических величин со стохастическими моделями" (гос. per.

№0186078716, 1987г.);

- НИР № 39-88 "Разработка устройства обработки сигналов датчиков физических вел1гшн со стохастическими моделями" (гос. per. № 0186078716, 1989 г.);

- НИР № 39-89 "Разработка системы управления электроприводами устройства УКП-3" (гос. per. № 01.88.0021147, 1989 г.);

- НИР № 41-89 " Разработка перспективного буквенно - цифрового жидко - кристаллического индикатора" (гос. per. № 01.89.0033475, 1990 г.);

- ОКР № 58-91 "Диагностирование аппаратных и программных средств универсальной комплексной системы (УКС 1)" (гос. per. № 01.9.10 048994

1991 г.);

- ОКР № 58-92 "Диагностирование аппаратных и программных средств универсальной комплексной системы (УКС 2)"(гос. per. № 01.9.10 048994

1992 г.);

- ОКР "Волан" по договору 65/104 от 04.02.93r.

- ОКР по договорам с П/Я А- 1572, В/Ч 11232 и ООО РязаньПрибор.

Результаты, полученные в диссертации, использованы и внедрены на

следующих предприятиях: ОКБ "СПЕКТР" при РГРТА в процессе выполнения работ по темам "Резеда" и "Сбор" Государственный заказ по решению организации П/Я А - 1572 № ВП - 256 от 03,09.90г., КБ

"Монитор", Восьмом Управлении ГШ ВС России в рамках ОКР " Волан" по договору 65/104 от 04.02.93г., Главном Управлении Командующего внутренних войск России в рамках договоров № 03/95 от 12.05.94 г. и № 09/95 от 4.7.96 г., КТО СВТ "Терминал" и АОЗТ ICL в рамках договора с В/Ч 11232, НИР и ОКР общей структуры интегрированной системы моделирования мультипроцессорных систем с массовым параллелизмом в Институте проблем вычислительной техники РАН.

Апробация работы. Результаты исследований, составляющих основное содержание работы, докладывались и обсуждались на международных конференциях: Г' International Conference and Exhibition DIGITAL SIGNAL PROCESSING AND ITS APPLICATIONS-DSPA'98(Moscow,1998); LOCAL-AREA NETWORKS (Riga, 1990, 1992), " Технологии и системы сбора, обработки и представления информации"(Рязань, 1993), " Проблемы передачи и обработки информации в информационно - вычислительных сетях (1997); на Всесоюзных конференциях, симпозиумах и школах - семинарах: "Вычислительные сети коммутации пакетов" (Рига, 1983, 1985, 1987, 1989), " Проблемы создания систем передачи дискретной информации и телеобработки данных в ИБС и АСУ " (Рязань, 1985), " Применение микропроцессоров, мнкро - и персональных ЭВМ" (Миасс, 1990), " Вычислительные сети" (Ереван, 1983, Винница, 1991), " Перспективы развития локальных информационно -вычислительных сетей на базе персональных ЭВМ" (Москва - Ивантеевка, 1989), " Структура и функционирование локальных вычислительных сетей и информационно - управляющих систем" ( Москва - Ивантеевка, 1988), И, III, IV, V Рязанские педагогические чтения (1995, 1996, 1997, 1998), "Современные телекоммуникационные среды обучения - ТЕЛЕМАТИКА - 96" (Санкт-Петербург, 1996), межведомственные и Государственные испытания аппаратуры передачи данных ПД - 440 и войсковые испытания в реальных условиях эксплуатации Агрегативной многопроцессорной системы РАМС, создание сети передачи данных по ЦЗКС в ДВО, ПРИ ВО и СКВО МО РФ в КТО СВТ "Терминал" и АОЗТ ICL, НИР и ОКР по созданию мультипроцессорных вычислительных систем с массовым параллелизмом в Институте проблем вычислительной техники РАН.

Объём и структура диссертации: введение, 7 глав, заключение, 10 приложений; 325 страниц, из которых 272 стр. составляют основное содержание, 16 стр. - рисунки (23 рис.), 9 стр. - таблицы, 18 стр. - литература (185 наименований), 36 стр. - приложения.

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

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

Глава 1. ПРИНЦИПЫ И МЕТОДЫ ОРГАНИЗАЦИИ СЕТИ ОБРАБОТКИ ДАННЫХ

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

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

Исследованы реализованные на практике варианты структур систем первичной обработки. На основании анализа существующих систем первичной обработки информации показывается целесообразность применения'БИС и СБИС на базе Intel Pentium, IBM 6x86 или Power PC, AMD Кб, Cyrix 6x86, DEC Alpha, NexGen Nx586 для создания мультимикропро-цессорных (шМП) систем, что позволяет обеспечить более высокую степень гибкости, модульности и мнкропрограммируемости при достаточно значительной производительности за счет высокой степени параллельности вычислений. Причем по мнению российских и ряда зарубежных специалистов с появлением шМП-систем вновь возникает реальность разумной специализации машинных комплексов, т.е.становится более гибкой граница между техническими и программными средствам, что заключает в себе потенциальную возможность повышения эффективности вычислительных систем.

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

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

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

Постановка задачи.

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

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

В результате проведенного анализа установлено, что для решения задач первичной обработки целесообразно использовать специализированные средства в виде мультимикропроцессорной системы ( тМП - системы ). Дальнейшее повышение производительности гпМП - системы возможно на основании анализа оптимальных соотношений между аппаратными и программными средствами и определения наиболее рациональной организации взаимодействия между микропроцессорными модулями (МИМ). В процессе выбора наиболее рациональной организации системы в качестве критериев используются технические характеристики: быстродействие(1/Тк), объём микропрограммной памяти (|МП|), число микропроцессорных модулей (И0), время простоя (Тщ.). Дополнительно в качестве критериев могут быть рассмотрены параметры системы: надёжность (Р), адаптация (А), готовность промышленности (К), патентная чисто-та(П) и стоимость (С)) и др. Упорядоченная последовательность приведенных критериев в виде кортежа определяется как стратегия проектирования.

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

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

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

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

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

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

Глава 2. ОБОБЩЕННАЯ МОДЕЛЬ ОПТИМИЗАЦИИ СРЕДСТВ ОБРАБОТКИ ИНФОРМАЦИИ

В развитии специализированных вычислительных средств(СВС) для натурного эксперимента сложных объектов, включая ЛА и ЛО наблюдаются следующие направления:

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

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

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

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

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

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

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

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

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

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

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

На основании используемого в работе теоретико-множественного подхода [ 4,9 ] введем следующие обозначения.

Подмножество технических характеристик M={Mi,M2,..,Mn,...,MN} включает в себя число процессорных модулей, объем командной и оперативной памяти, разрядность операций и порцессора, время выполнения команд, время обращения к памяти и др.

Подмножество требований G={GI,G2,...,Gk,...,GK} включает в себя: режимы обработки информации, временные ограничения на обработку и ее точность, достоверность решения задач обработки, надежность и др.

Подмножество ограничений Е = { Ei,E2,...,Ei,...,El} накладывается на основные технические характеристики и включает все допущения на функциональные зависимости вида Mi = f| (G, М, Е) и все ограничения на пределы изменения технических параметров.

F( M,G,E) - критериальный показатель оценки уровня работоспособности СВС.

В общем виде задача макросинтеза жизнеспособной СВС может быть сформулирована следующим образом: для заданных векторов М, G и Е требуется отыскать такой вектор М* значений: Mi* = Fi(M,G,E), М2* = F2(M,G,E), ,..., ML*= Fl(M,G,E), при которых величина критериального показателя F(M,G,E) принимает экстремальное значение. Другими словами оптимальным образом спроектированная система должна наилучшим образом удовлетворять предъявленным требованиям к уровню производительности, точности, надежности, живучести СВС, а их совокупность была оптимальной с точки зрения критериального показателя оценки уровня жизнеспособности СВС.

На основании обобщенной математической модели выбор оптимального состава технических и программных средств обработки информации сводится к решению задач: Z = Z( G,M,E ) => ext

при условиях F (М,Е) < = G, (1)

В работе автором показывается, что при введенных условиях функционал вида (1) является сепарабельным. Это позволяет в простейшем случае представить функцию Z = Z (G,M,E) в виде линейной формы

Z = Z(kj*G + k2*M + k3*E), где ki,k2,k3 - весовые коэффициенты. Для обеспечения равномерного вклада частных показателей в общий критерий значения коэффициентов ki нормируются в области от 0 до 1.

Глава 3. ОПТИМИЗАЦИЯ СРЕДСТВ ОБРАБОТКИ ИНФОРМАЦИИ В СЕТИ ПЕРЕДАЧИ ДАННЫХ

Проектируемая вычислительная структура функционирует по алгоритмам предварительной обработки A00, Vj = 1,N, каждый из которых представляет собой кортеж алгоритмов: отбраковки, сжатия, калибровки, автоконтроля и других.

Под алгоритмом понимается конечный кортеж операций Oj A(J) = < Oi, Oq,..„ 0L,02,0,,...,0r > длиной |A|.

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

О, => {МК,„}; Vm=l,Kra; V1=1,L, (2)

где под множеством команд МК = { МКьМК2,...,МКм } конкретного комплекта СБИС подразумевается внутренний язык ВС; Кт -минимальное количество команд, реализующее операцию 0|.

Выбор элементной базы - сложная математическая задача и в данной работе не рассматривается. Поэтому в работе в качестве исходных данных используется система команд Х86. Предложенный набор может быть дополнен командами ММХ (MultiMedia extensions).

В зависимости от решения задачи (2) на втором этапе проектирования каждому j - му алгоритму обработки ставится в соответствие программа обработки PR(j) посредством определяемого отображения

А0) ^ PRCi) vj= 1,N. (3)

Под программой обработки информации PR понимается кортеж команд PR(J) = < МК1,МКш,...,МК2,МК5,...,МКм >. Характеристиками рассматриваемой программы PR^' являются: длина программы PR0', определяемая как общее число команд, входящих в программу; время выполнения программы T=Em=itm, где!:т-время выполнения т-ой команды: PRy) ^{PR01 ,Т}. Причем выражение(З) определяет однопроцессорный вариант тМП реализации системы.

Далее вводится понятие структуры Swe S, под которой понимается отношение параллельности выполнения подпрограмм RO|, ROk двумя различными процессорными модулями: RO| Sw ROk; ROb ROk e PR.

Тогда на третьем этапе проектирования определяется множество всевозможных структур S,»eS, позволяющих некоторой j-ой программе обработки PR(3) поставить в соответствие множество подпрограмм RO i S„ e S : PR => { ROj }, V i = 1,1; V w = 1,W. (4 )

На четвертом этапе осуществляется оптимальный выбор структуры первичной обработки информации по заданной стратегии проектирования, включающей в себя минимум технических и программных средств и удовлетворяющей требованиям по производительности: минимизировать Х = (2*Х + 11*Х при условиях

V Хц + Хц * Х1} <= Т! £¡=1х^ + ^=1 vWj * х^ <= Т\,

и^* Хщ + 1]=1 Vwj * <= , ( 5 )

где ^ - время выполнения .¡-го алгоритма Аа) - ой структурой при его технической реализации; - время выполнения ] -го алгоритма А0) лу -ой структурой при его программной реализации; Х^ - двумерная переменная, обозначающая способ реализации .¡-го алгоритма в \v-oii структуре;

= 0.1,0.9; XVVj = 1-Х,ф где - характеризует программные

затраты при реализации .¡-го алгоритма обработки \v-oii структурой;

где QWj - затраты технических средств при реализации .¡-го алгоритма в н'-ой структуре. Система (5) имеет решение, если ^ <= Т0. Оптимальные соотношения существуют между техническими и программными средствами, если ^ >= Т0.

Для решения задачи ( 3 ) введем понятие равенства подпрограмм 1101 и ЯОи первичной обработки информации ЯО| = 1Юк, под которым далее понимается равенство длин указанных подпрограмм 1Ю| = ШЭк и совпадение их с точностью до команды МК/к) = МК/1' ,т.е.

I ИО, | = | ЯОк |

V 1,к = 1,Ы 110,= ЯОк ={

МК,(к) = МК,-(1), VI = 1,| 110, | (6 )

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

Введенное отношение структур Б* позволяет разбить всю программу обработки РГ^', определяемую согласно ( 3 ), на классы эквивалентности Я|, т.е. на классы неравных между собой подпрограмм с числом классов эквивалентности Ь и порядком каждого класса | а> |. Каждый класс эквивалентности а, имеет своего представителя в виде подпрограммы ЯО,, имеющей число команд равное порядку подпрограммы | ИД | .

Таким образом, структура первичной обработки информации ставит в соответствие некоторой j -011 программе обработки РЯ совокупность независимых и неравных подпрограмм 1Ю|, число которых равно числу классов эквивалентности Ь, а кратность ( 110|) определяется порядком класса эквивалентности ( Я|):

РЯШ => {(1Ю,)4 }, = 1,Я| ; VI = (7)

В результате решения задачи (7) возможны следующие варианты решения.

К л а с с н ф и к а ц и я тМП - структур.

1. Число классов эквивалентности равно Ь и порядок каждого класса равен единице а( = 1. Тогда j - ый алгоритм первичной информации представляет собой кортеж из Ь подпрограмм:

Аа)К" => {ЯО,} = <1^,110:,...ДО,,...ДОь>, (8)

каждая из которых является представителем своего класса эквивалентности и обеспечивает входной информацией последующую 1Ю|+1 подпрограмму. Взяв число процессорных модулей равное Ь и назначив каждому 1 -му модулю соответствующую ему подпрограмму, получим тМП реализацию конвейерного типа. Далее определяются основные параметры получаемого конвейера первичной обработки информации.

2. Число классов эквивалентности Ь равно единице и порядок класса | Я| | равен q. Тогда _|-му алгоритму обработки А0) информации соответствует набор q совершенно одинаковых программ А® => {(КО)4}.

Если выходная информация каждой подпрограммы ИД, '4 = 1,(] является входной для каждой последующей 1ЮнЬ тогда имеем уже известную конвейерную структуру с числом процессорных модулей равным q, каждый из которых функционирует по программе 110 .

Если входная информация требуется одновременно для всех подпрограмм, тогда, назначая q процессорных модулей на первичную обработку информации, получаем тМП реализацию матричного или параллельного типа Аа) ^ => (1101)=<1101><1Ю1>...<1101>, в которой все q процессорных модулей функционируют по одной и той же подпрограмме Я0(.

3. Число классов эквивалентности равно Ь и порядок каждого 1 -го класса равен | а, |. Этот случай является общим и предполагает отношения не только между подпрограммами внутри класса, но и между подпрограммами различных классов.

Пусть обмен информацией между представителями классов ШЭЬ У1=1,Ь осуществляется последовательно. Если подпрограммы внутри 1-го класса обмениваются последовательно, тогда, назначая число процессорных модулей N0 = Ь* Е|=1 | получим известную конвейерную структуру. Если для подпрограмм внутри 1 - го класса требуется информация одновременно, тогда, назначая число процессорных модулей равное N0 = Ь * шах | а! V 1=1,Ь, получим конвейерно-векторную структуру первичной обработки информации.

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

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

Результаты анализа по конвейерной(1,Г), векторной(2,2'), вектор-но-конвейерной(3,3'), конвейерно-векторной(4,4') структурам первичной обработки информации для 80 заданных алгоритмов приведены на Рис.3.6 и Рис.3.7

•о Л?

I

I

13 7

¿Мл-

4/

, .. л _ — _

_-Г ^ А

, ' / й, - - "

/

1

г

12

15

1В

21

24 па

Рис.3.6. Обобщенные характеристики производительности 1/Ти от количества Н, процессорных модулей для различных тМП структур.

■та

ш

3

ff :::t2::::::tS:::::t3

Рис.3.7. Обобщенные характеристики объема памяти |RO| от количества N0 процессорных модулей для различных шМП структур.

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

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

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

Глава 4. ДЕКОМПОЗИЦИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

ВЫБОРА СРЕДСТВ ОБРАБОТКИ ИНФОРМАЦИИ

Решение задачи выбора рациональной структуры узла связи сети первичной обработки информации большой размерности в работе предлагается произвести посредством декомпозиции условий (5) при введенных обозначениях С = (С-Я); Со = Я; А = ||(^||; ЬпТрЕ^, У0; Ь={Ы}.

В этом случае преобразованная задача ( 5 ) принимает вид: минимизировать линейную форму Ъ = С*Х + Со при условиях А * X < = В, где А = || ац || ( 9 )

I = { 1,2,3,...,1,...,М }- множество алгоритмов обработки;

.1 = { 1,2,3,..____N }- множество структур обработки.

Известно [2], что любая матрица А имеет структуру строк апр = { К',,К'2,...,К',,...,К'Т }, VI =1,Т'; 1 < =Т' < =М, К', = {Б,: qe М',}; и,=1 М'« =М ; Б, = { ачЬ ач2,...,а^ }, Vq = 1,М, и структуру столбцов

астл = {" К"1,К-'2,..,К".,...Д"т }, 1=1,Т"; 1< = Т" < = М,

К", = {5ч:ЧеМ'\}; и,=1М",=М; 5Ч= { а,„ а2,.....ак, }, УЧ= 1,14;

М = {1,2,...,Ы }.

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

1. Структуры строк и столбцов матрицы совпадают К'|=К",=КЬ 1еТ'=Т"=Т.

2. Внутри структуры симметрии существует цикличность перехода элементов: ачг=...=ач„ еК,. ( 10) Исследование симметрии матрицы ограничений А и определение всей группы в линейных преобразований, относительно которых система (4-6) будет инвариантна относительно группы и еСЦп, И.) унитарных линейных преобразований, производится согласно условшо коммутативности Ли

[АЩ = Аи - иА = 0 (11).

В работе доказано, что необходимым и достаточным условиями(П) являются наличие структуры симметрии (10). Так необходимое условие формулируется в виде утверждения: если матрица ограничений А задачи(9) удовлетворяет (11), тогда она должна иметь структуру симметрии (10).

Справедливость достаточного условия вытекает из следующего результата. Если матрица А обладает структурой симметрией (10), тог-

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

Доказанные соотношения справедливы для одного элемента группы и» е вЦп, К). Оставшиеся (т - 1) -н элемент класса Л| определяются согласно следующего предложения: если матрица ограничении удовлетворяет условиям (10), она коммутирует со всеми степенями Ц1, V 1=2,т-1; и^1 = Е, где Е - единичная матрица. (иг)(|)А=А(иг)(|), У1=2,1ь1.

Последовательно превращая цикл за циклом в единичный и комбинируя их, можно построить всевозможные классы смежности С!, \/1=1,г, из которых состоит группа СЦпД). Зная всю группу согласно теории матриц[5] можно путем преобразования подобия посредством матрицы Н исходную матрицу А привести к квазидиагональному виду НАН"1 = с11ай(А1(11),...,Аш(1,„), где \/]=1,т А^) - квадратная матрица порядка Р^ допускающая единственное собственное значение т.е. характеристический полином такой матрицы имеет вид ВД1)=(1-^)Р].

В каношгческом базисе приводимого представления и^) группы ЗД.(п, II) оператор - матрица затрат(4-6 ) записывается в блочно-диагональ-ном виде 111 п2 п,

А=с^[А1,...,А1,А2,...,А2,...,А1,...,А1], (12)

где Ау - блок-матрица порядка шу При этом порядок шу полученных матриц-блоков Ау и их кратность пу определяются следующими выражениями: пУ=х„(С0) (13)

шу=1/аЕг,=1Ь!Ху(С1)Х(С,), (14)

где Со-класс единичного элемента, С| - 1-ый класс сопряженных элементов в группе вЦпД), Ху - характер неприводимого представления группы порядка ч и X - составной характер. Таким образом первым результатом введения структуры симметрии является возможность оценки приведен™ матрицы ограничении по определяемой данной методикой группе йЦпД).

Необходимый для приведения оператор проектирования Р определяется согласно следующего выражения:

Ру=п,/ё (Хое сХу(йи8)=пу^(ЕГ|=1Ху(С!)иЕа, (15)

где иг -матричное представление элемента группы g, и£С| - сумма матричных представлений всех элементов класса С,.

Пусть 1,, 12,..., 1, - длины циклов, соответствующие структуре симметрии матрицы А (22) : 1,+12+...+1к+1„=п; Ь>1. Тогда вторым результатом является построение оператора проектирования Н со следующей

блочной структурой матрицами Нк и Вк,(к=1,2,..., s), определяемыми следующими выражениями

Н=

н,н2 Ни- Hs 0 0 .. . 0 -1 1 0 0 .. . 0 0

В, 0 0 .. . Ü 0 -1 1 0 .. . 0 0

0 В2 0 .. 0 и 0 .. . 0

; нк= 1 1.. . 1 ; вк= 0 0 0 -1.. . 0 0

0 0 Вк- . 0 0 0 .. . 0

0 0 0 0 1 0

0 0 0 .. . Bs 0 0 . . 0 0 0 0 0 .. . -1 1

(16)

Такую же блочную структуру имеет и оператор проектирования Н(-1) с прямоугольными матрицами Бк размером (1к х Б)(к- ый столбец которой состоит из элементов 1к-1) и Ск размером 1кх(1к-1) следующего вида

Н

Dl с, . ü . 0 0 0 . ik-i. . 0 a! a2 a3 . • 3|k-2 . • aik.i

0 0 . lk-i. . 0 bj a2 a3 . ■ aik-2 • ■ a,k.i

Dk 0 . . Ск. 0 ;Dk= ik-i. . 0 ;ck= bt b2 a3 . • 3|k.2 . • aik.i

0 0 . lk-i • . 0

Ds 0 . . 0 . Cs (17) а о. ik-i. . 0 (18) bi b2 bi . ■ biu-2 . • bin

В результате декомпозиция задач линейного программирования сводится к эквивалентному преобразованию исходной задачи (4-6) и представлению ее в виде совокупности подзадач меньшей размерности чем исходная: Z = {Zi.Z2,...,ZN} = { Z } Z = C| Х=> min (шах) С = { С,} при условиях А| X <= Bi V i= 1 ,N А = { Ai} ; В = { В,}

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

В данной работе дается оценка трудоемкости предлагаемого алгоритма. которая определяет границу применимости предложенного метода N\p= 2Nrp М + 3/2SN2rp

Глава 5. МЕТОД МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА СТРУКТУРЫ шМИ СИСТЕМЫ ПО ЗАДАННОЙ СТРАТЕГИИ ПРОЕКТИРОВАНИЯ

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

ропроцессорных структур Si е S лицо, принимающее решение (ЛПР), должно на основании обобщенной оценки каждой альтернативы Si выбрать наилучшую по совокупности противоречивых критериев: быстродействие (1/Тг);объем микропрограммной памяти (|МР|); число микропроцессорных модулей(Ыо), время простоя (Тт>). Дополнительно можно рассмотреть и другие критерии: надежность (Р); гибкость перестройки-адаптация (А); готовность промышленности (К); стоимость (Q); патентная чнстота(П) и т.д. В работе все вышеперечисленные критерии предлагается ранжировать в порядке важности технического проектирования и называть стратегией проектирования [6,11].

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

ЛПР оценивает структуры и критерии с помощью понятий нечеткой переменной или терма t е Т "высокая"(В), "довольно - высокая" (ДВ), "вроде - высокая"(ВВ), "чуть выше средней"(ВС), "средняя" (С), "чуть ниже средней "(НС), "вроде низкая"(ВН), "довольно низкая" (ДН), "низкая" (Н). Формализация такого описания производится с помощью лингвистической переменной <структура или критерий {В, ДВ, ВВ, ВС, С, НС, ВН,ДН, Н}. Каждая переменная имеет область определения в виде отрезка Е = [а,в] и функцию принадлежности mt (е), т.е. tj = { шн(е),е }.

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

- бнпарная лингвистическая переменная - "отношение значимости критерия" Rj/j+i или "отношение полезности структуры" Qj/j+l;

- унарная лингвистическая переменная -"качественная оценка значимости критерия" m2j (х) или "качественная оценка полезности структуры" mzj.Si (х,у).

Значения бинарных лингвистических переменных"отношение значимости" и "отношение полезности" строятся методом нечеткого алгоритма высказывания правил вида: "если А, то В". Два и более правил нечетких высказываний объединяются связкой "иначе": "если А, то В, иначе С"=[А][В] + [ А][С] или U (если А, то В, иначе C)={mA/V(B), 1- mA/V(C) }.

Оценка значимости каждого из предыдущих в списке критериев производится согласно стратегии проектирования по правилу композиции Zj = оЯ^и, ]=п-1,п-2,...,1. При этом функция принадлежности нечеткого множества Zj является результатом максминной операции: (х) = иуе V т )о т (у,х). Для получения весов значимости критериев нечеткие множества преобразуются в скаляры одним из известных способов, например, выбором такого значения бинарной переменной, при котором функция принадлежности достигает максимума. Затем скалярные оценки значимости критериев шкалируются и нормализуются. В результате каждый критерий получает вес \^=1,и; £¡=1 = 1.

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

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

Таким образом, алгоритм логического вывода состоит из следующих шагов.

1. Выбор носителей и получение начального распределения.

2. Определение стратегии проектирования, которое выражается в ранжировании заданных критериев.

3. Определение бинарных лингвистических переменных "отношение значимости критерия" Я^+ь которое производится по правилу композиции:

Ъ i=Z¡+lo с выбором критериев, начиная с последнего ^=N-1.....1.

4. Получение "качественной оценки значимости критерия" по формуле:

111ц (х) = иусУ шг]+1(у) г. тК№1(у,х).

5. Получение скалярных оценок Х^ , то есть определение номера тех носителей. при которых значения критериев достигают единицы.

6. Шкалирование оценок по формуле: HJ = 3(Х)* +1) + 1.

7. Получение нормализованных весов по формуле: = Н

8. Определение бинарных лингвистических переменных " отношение полезности структуры": Ъ j = Ъ о И с выбором структуры, начиная с первой.

9. Определение "качественной оценки полезности структур" по формуле:

(У,Х).

10. Получение скалярных оценок т.е. определение номера тех носителей, при которых значения структур достигают единицы.

11. Шкалирование оценок по формуле: Н ц = 3(Уу* +1) +1.

12. Получение нормализованных весов: Р ц = Н у /£¡=1 Н д.

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

14. Вычисление аддитивной функции полезности = ^Л*/ ] * И у альтернативных вариантов структур мультимикропроцессорных реализаций узла связи сети по совокупности всех критериев согласно стратегии проектирования, где Р д - нормализованные веса.

15. Вывод результата логического решения.

Глава 6. ЭКСПЕРТНАЯ СИСТЕМА ВЫБОРА СТРУКТУРЫ шМП СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ

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

Как известно [15], разработка экспертной системы включает в себя создание базы знаний на существующем множестве 51Ше Б шМП реализаций и описание процедуры логического вывода. В данной главе предлагается алгоритмы этих двух составляющих. В основе алгоритма описания базы знаний лежат уже известные соотношения:

УАШ е А Е 8„ : МРШ => { (РЛ,)4 } Уч = 1,| а, |; VI = 1,Ь. В процессе анализа используется информация обмена данными между фрагментами внутри класса согласно заданным алгоритмам А0).

Исходными данными для базы знаний являются характеристики алгоритмов: число классов эквивалентности Ь, порядок каждого класс| а1 | обмен данными между фрагментами классов, поступление входных, выдача выходных данных; множество микрокоманд выбранного микропроцессорного комплекта и множество критериев Ъ. Каждый из вышеперечисленных параметров является объектом и частью сцепленного списка (Таб.6.1).

Обмен данными между фрагментами классов эквивалентности может быть параллельный и последовательный.

Исходя из основных соотношений описание базы знаний сводится к следующей последовательности действий:

ОБЪЕКТ МП Микро- Кл. Пор. Характер Структуры Крите-

СПИСОК наб- програ- экв кла- Обмена рии

ЗНАЧЕНИЙ ор мма ив. сса

Начальный 1,Р,К, 41 Последова Конвейер.К Быст-

блок В 1 тельный Почти кон- родей-

вейернаяПК ствие.

Арифметич Е,Ь Е,С,Е, Яг Параллел Конвейерно Объем

еский блок Р,А В,Р, 2 Ный Векторн.КВ Памяти

Логический 3,М К, Е, Б, Яэ Последов. ВродеКонв. Число

блок к,р Е,С,Б, 3 Параллел. Вектор.ВКВ моду-

р В,Р,К, МатричнаяМ лей ,

Блок АР Е,Б,Е, . . Параллел. ВродеВект. Время

перехода С,Е,В, • 41 Последов. КонвейерВВ прост.

Циклическ- Р,К, Е, 1 ПочтиВект. Стои-

ий блок А, РР, . . . ПВ мость .

Конечный АР ВекторнаяВ Надеж-

блок ность

Таб. 6.1. Сцепленный список.

1. ЕСЛИ число классов эквивалентности равно Ь, порядок каждого класса Л| равен единице И

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

ТО "конвейерная структура";

- информация одновременно требуется всем фрагментам,

ТО "векторная структура";

2. ЕСЛИ число классов эквивалентности Ь равно единице, порядок каждого класса Л| равен q И

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

ТО "конвейерная структура";

- входная информация требуется одновременно всем фрагментам,

ТО "векторная структура";

3. ЕСЛИ число классов эквивалентности равно Ь, порядок каждого класса равен а! И

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

ТО "конвейерная структура";

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

ТО "почти конвейерная структура";

- обмен информацией между фрагментами классов, кроме 1-го, последовательный, а 1-му классу информация требуется одновременно,

ТО "конвейерно - векторная";

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

ТО "вроде конвейерно - векторная структура";

- если порядок каждого класса равен числу классов эквивалентности Ь,

ТО "матричная структура";

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

ТО "вроде векторно - конвейерная структура";

- информация требуется одновременно всем классам, но фрагменты 1-го класса обмениваются последовательно,

ТО "векторно - конвейерная структура";

- информация требуется одновременно фрагментам всех классов, кроме некоторых фрагментов 1-го класса,

ТО "почти векторная структура";

- информация требуется одновременно всем фрагментам классов,

ТО "векторная структура".

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

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

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

Глава 7. ЭКСПЕРИМЕНТАЛЬНЫЕ ХАРАКТЕРИСТИКИ СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ В ВЫЧИСЛИТЕЛЬНОЙ СЕТИ ПЕРЕДАЧИ ДАННЫХ ПД-440 И РАМС

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

На первом этапе, согласно предложенной методики, выбирается один из самых производительных комплектов СБИС 1486, эмулирующего универсальную систему команд Х86-базовую для большинства из перечисленных выше комплектов СБИС, включая и систему микрокоманд ММХ.

На втором этапе для заданных алгоритмов первичной обработки А1, V] = разработана методика формализации программ обработки однопроцессорного варианта тМП реализации системы.

На третьем этапе проектирования определяется множество Б возможных структур е Б. Для этого программа обработки, определенная выше, разбивается на множество независимых подпрограмм, т.е. классы эквивалентности по данным и по командам.

На четвертом этапе выбирается ММП структуры системы первичной обработки информации, реализующая заданный класс алгоритмов обработки в режиме реального времени и без потерь по заданной стратегии проектирована. Анализ микропрограммы протокола сжатия для СБИС 1486 со временем пересылки регистр - регистр 1= 16 не показывает, что в микропрограмме МР={1,Р,К,Р,5,Р,С,Р,В,Р,К,Р,5,Р,С,Р,В,Р,К,Р,8,Р,0,Р,В,-Р,К,Р,А,Р,К,Р,8,РР }имеет четыре класса эквивалентности: представителем первого класса является фрагмент РН.1={ Р,К,Р,8,Р,С,Р,В } и порядок П1= -3, представш-елем второго класса - РЯ2 = { Р,К,Р,А } и порядок а2= 1, представителем третьего класса - РЯ3 ={ Р.КДБ } и порядок = 1, представителем четвертого класса - Р!^ ={РР}и порядок а4 = 1.Причем обмен информацией между классами и внутри класса параллельно-последовательный.

Разбивая всю программу на четыре части МРО1 = МР02 = МРОз = = МРО4 ={РЛ2, РЛ3, ИЯ»} и назначая каждой из них микропроцессорный модуль, получаем конвейерную структуру Б] мультимикропроцессор-ной системы сети с временем цикла Тг = 6,2 мс и N0= 4.

Так как информационно фрагменты первого класса не зависят друг от друга,то, назначая число микропроцессорных модулей равным три,получаем векторную структуру S2 ММПР с микропрограммой протокола MPOi = МР02 = МРОз={ I,P,K,F,S,F,G,F,B,P,K,F,A or S,PP} и временем выполнения Тг=6,4 мс(А or S-дизъюнкция команд А и S) и N„ = 3.

Разбивая программу протокола MPOi на две равные части MP0i=MP02 и вводя еще три микропроцессорных модуля, получаем векторно - конвейерную структуру Бз мультимпкропроцессорного узла связи сети со следующими представителями: MPOi-з = = { I,P,K,F,S,F,G,F,B} п МРО4-6 = { I,P,K,F,B,P,K,F,A or S,PP } и временем выполнения Тг = 3,8 мен N„ = 6. Из перечисленных Si, Sî,S3 структур необходимо выбрать одну наиболее рациональную по заданной стратегии проектирования Z, состоящей из четырех ранжированных критериев: быстродействие ( 1 ЛГг), объем микропрограммной памяти (|МР|); число микропроцессорных модулей (No), время простоя (Тпр).

Для решения вышеупомянутой задачи используется предложенная в работе методика многокритериального нечеткого выбора, на основании которой первоначально на отрезке [0,1] выбираются конечные носители.

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

Таб. 7.1.

Носитель Линг. Терм. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

H 1 1 0.7 0.2 0.1 0 0 0 0 0 0

дн 0.5 1 1 0.4 0.2 0.1 0 0 0 0 0

ВН 0.2 0.3 0.8 1 0.8 0.3 0.1 0 0 0 0

НС 0 0 0.1 0.4 1 0.4 0.1 0 0 0 0

с 0 0 0 0.1 0.4 1 0.4 0.1 0 0 0

ВС 0 0 0 0 0.1 0.4 1 0.4 0.1 0 0

ВВ 0 0 0 0 0.1 0.3 0.8 1 0.8 0.3 0.2

дв 0 0 0 0 0 0.1 0.2 0.4 1 1 0.5

в 0 0 0 0 0 0 0.1 0.2 0.7 1 1

Далее определяем стратегию проектирования, выражающуюся в ранжировании критериев п назначении им лингвистических бинарных отношений значимости 11^+1. Результаты заносятся в таблицу 7.2., в которую также включены разделы качественной оценки значимости критериев скалярной оценки X) , шкалированных оценок

Hj=3(Xj +1) +1 и, наконец, нормированных весов Wj каждого критерия j=l,4; Wj=Hj/Zj,|H j. Причем качественная оценка простоя Тш> взята в качестве лингвистического терма "средняя", а все остальные Zi, Zz, Zj -по правилу композиции Zj = Zj+i Rj/j+i. Кроме того, принятие Zi за среднее позволяет обеспечить нормализованные веса факторов. При этом функции принадлежности качественных оценок достигают своих максимальных значении U4i=iZj=lnpH определенных значениях X . Эти значения и являются скалярными оценками.

Дальше строятся лингвистические бинарные отношения полезности вариантов по каждому критерию и производятся аналогичные вычисления скалярных Vij и шкалярных оценок Н ¡¡, нормализованных весов F ¡¡. Получаемые результаты сводятся в Таблицу 7.2.

На основании полученных данных вычисляется аддитивная функцияполезности Ui альтернативных вариантов мультимикропроцес-сорных структур реализации узла связи сети по совокупности всех критериев Ui = Z j=i Wj Fij = 0.3; Ua=E|=iWj F2j = 0.32; Uj =Zj=.iWj F3j=0.38.

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

Таблица 1.2.

Т а Б. С К т р, Р- Качественна я оценка значимост и Скал. Оцен, Знач. Шкал. Оцен. знач. Нор- мал. вес

1 1Л-„ 0 0 0 0 0.5 0.5 0.7 0.7 1 0.5 0.9 6.7 0.3

2 |МР| 0.5 0.7 1 0.5 0.5 0.3 0.1 0 0 0 0.2 5.6 0.2

3 No 0 0 0 0.1 0.4 0.5 0.7 1 0.5 0.4 0.8 6.4 0.28

4 TiD 0 0 0.1 0.4 1 0.4 0.1 0 0 0 0.4 5.2 0.22

1 Si 1 0.5 0.5 0.3 0 0 0 0 0 0 0 4 0.24

s2 0.2 0.5 0.7 0.7 1 1 0.5 0 0 0 0.5 5.5 0.32

s3 0 0 0 0 0 0 0.2 0.7 1 1 1 7 0.44

2 Si 1 1 0.5 0.5 0.5 0 0 0 0 0 0.1 4.3 0.26

s2 0.2 0.4 0.5 0.7 1 1 0.5 0.5 0 0 0.6 5.8 0.35

s3 0 0 0 0 0 0.2 0.4 1 1 0.5 0.8 6.4 0.39

3 Si 0 0 0 0.1 0.4 0.5 0.7 1 0.4 0.4 0.7 6.1 0.35

S2 0 0 0 0.1 0.4 1 0.4 0.1 0 0 0.5 5.5 0.325

s3 0 0 0 0.1 0.4 1 0.4 0.1 0 0 0.5 5.5 0.325

4 Si 0 0.2 0.4 0.5 0.5 0.7 1 1 0.5 0.5 0.6 5.8 0.34

S2 0.2 0.4 0.5 0.7 1 1 0.5 0.5 0 0 0.4 5.2 0.3

S3 0 0 0 0 0 0.2 0.4 .1 1 0.5 0.7 6.1 0.36

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработан метод распараллеливания заданных алгоритмов обработки информации на базе классов эквивалентности и представления исходной программы в виде множества независимых фрагментов. На основе метода произведена классификация получаемых в процессе проектирования известных и предлагаемых мультпмпкропроцессорных структур с возможностью варьировать в широких пределах 20 - 25 % затрат аппаратных и программных средств. Получены аналитические временные оценки производительности и простоя оборудования предложенных структур системы обработки данных, показывающие выигрыш по производительности за счет сложной организации обработки примерно на 20 % и сокращение времени обработки в среднем на 15 - 20 % по сравнению с известными.

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

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

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

получаемых классов тМП - структур по различным критериям, микропроцессорным комплектам, алгоритмам обработки и осуществления выбора наиболее рациональной структуры при существенном, примерно на 20 - 25%, сокращении в целом сроков проектирования рассматриваемых сетей обработки данных.

5. Предложена методика дополнительного тестирования протоколов физического и канального уровней, повышающая эффективную скорость передачи данных в условиях изменяющейся помеховой обстановки в каналах связи в среднем на 14-18% без ухудшения достоверности передаваемой информации. Результаты подтверждены межведомственными и Государственными испытаниями аппаратуры передачи данных ПД - 44 0 и Агрегативной мультипроцессорной системы РАМС.

6. Правильность и целесообразность разработанных методик и программного обеспечения подтверждена сокращением трудоемкости проектных работ по оптимизации аппаратных и программных средств Агрегативной мультпмпкропроцессорной системы РАМС и аппаратуры передачи данных ПД - 440 па 14 - 18% и увеличением производительности обработки информации на 15 - 17% за счет расспараллеливания алгоритмов обработки. Приводимые результаты подтверждены в ходе войсковых испытаний .аппаратуры РАМС, межведомственных и Государственных испытаний аппаратуры передачи данных ПД-440 и при выполнении плановых НИР по созданию мультипроцессорных вычислительных систем с массовым параллелизмом в Институте проблем вычислительной техники РАН.

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

1. Ручкнн В.Н. Проектирование и выбор специализированных средств обработки информации. М.: Московский государственный открытый университет, 1997. 120 е.: ил.

2.Ручкнн В.Н. Анализ аппаратных и программных средств специализированных систем телекомпыотеризации //Электросвязь. - 1998 - N 10. С.27-33

3. V.N. Ruchkin Designing of multimicroprocessor systems digital signais processing // Theses Of the Reports l51 International Conférence and Exhibition

DIGITAL SIGNAL PROCESSING AND ITS APPLICATIONS DSPA'98. M: ICSTI, 1998, v. IV, pp. 129 - 136.

4. Ручкнн B.H. Экспертная система проектирования пгМП систем обработки измерительной информации//ВЕСТНИК РГРТА, 1998, N4.C.127-130.

5.Ручкнн В.Н. Методы распараллеливания алгоритмов обработки измерительной информации//Электронное моделирование. 1989. N3. Т11 С.38- 41.

6.Ручкин В.Н. Выбор аппаратно-микропрограммной реализации протоколов // Микропроцессорные устройства и автоматизация проектирования: Межвуз. сб. Рязань: Рязан. раднотехн. ин-т., 1986. С. 64 - 69

7. Митюшин Ф.Ф., Курашин В.Н., Ручкин В.Н., Цыцаркин Ю.М. Об одном методе оптимизации технических ресурсов вычислительной сети // Электронное моделирование. 1987. N3.T.9 С. 32 - 35.

8. Воронин Ю.М., Ручкнн В.Н. Математические основы теории систем. М.: ВЗПИ, 1990. 102 с."

9. Ручкнн В.Н. Проектирование и выбор специализированных средств первичной обработки информации // Проектирование ЭВМ: Межвуз. сб. Рязань: Рязан. гос. раднотехн. акад., 1996. С. 64-69.

10. Ручкнн В.Н., Асаева Т.А. МАТЕМАТИКА. Линейное программирование. Декомпозиция задач линейного программирования. Рязань: Изд-во Рязан. Центра науч.-техн. инф., 1998. 45 с.

11. I.G. Pankov, V.N. Rnchkin Multicriterion Choice of Network Communication Node Implementation // Theses Of the Reports International Conference LOCAL - AREA NETWORKS. Riga: Institute of Electronics and Computer Science, Latvian Academy of Sciences, 1990. pp. 57 -62.

12. V.Grygorenko, V.Kurashin, I.Pankov, V.Ruchkin. Diagnostic of Universal Complex Hardware Network // Theses Of the Reports The Theses Of the Reports International Conference LOCAL-AREA NETWORKS.Riga:Institute of Electronics and Computer Science, Latvian Academy of Sciences, 1992, pp. 49 - 53.

13 I.G. Pankov, V.N. Ruchkin Regional Telecommunicational Space of Distance Learning // Theses of The reports. International Scientific-Technical Conferention. "TELEMATICS -96" StPetersburg., 1996. pp. 44 - 48.

И.Ручкин В.Н. Программная поддержка многокритериального нечеткого выбора//Автоматизация проектирования микроэлектронных вычислительных средств: Межвуз. сб. Рязань: Рязан. радиотехн. ин-т., 1990. С.65 - 68.

15. Митюшин Ф.Ф., Ручкнн В.Н. Классификация мультипроцессорных систем обработки телеметрической информации // Проблемы разработки и

эксплуатации специализированных вычислительных систем и сетей: Тематический сб. научных трудов. М.: МАИ, 1984 г. С.46 - 50.

16. Галкин Д.Ю., Панков И.Г., Ручкин В.Н. Телекоммуникационная среда дистанционного обучения// Проектирование ЭВМ: Межвуз. сб. Рязань: Рязан. гос. радиотсхн. акад., 1997. С. 64-69.

17. Ручкин В.Н., Хамидулин Ю.М. Выбор мультнмнкропроцессорной реализации узла связи сети // Проектирование ЭВМ: Межвуз. сб. Рязань: Рязан. радиотехн. ин-т., 1992. С.79 - 86.

18. Панков И.Г., Ручкин В.Н., Шибанов А.Н. Диагностирование протоколов каналов передачи данных // Обработка сложных сигналов с применением цифровых устройств и функциональной электроники: Межвуз. сб. Рязань: Рязан. радиотсхн. ин-т, 1993. С.73 -84.

19. Безгинов А.Н., Ручкин В.Н. Процедура экспертного анализа структур мультнмнкропроцессорной системы обработки информации //Автоматизация проектирования ЭВМ: Межвуз. сб.. Рязань: Рязан. радиотехн. ин-т, 1993. С.80 - 84.

20. Ручкин В.Н. Использование автоматизированных обучающих систем на базе локальных вычислительных сетей в процессе заочного обучения //Вопросы методики преподавания в заочном вузе: Межвуз. сб. Деп. в НИИВШ, 06.04.89, N 761-89. С.97 - 105.

21. Курашин В.Н., Ручкин В.Н. Представление протоколов на нечетких множествах // Информационно-измерительные управляющие системы: Межвуз. сб. /М.: Вс. заоч. политехи, ин-т, 1991. С. 120 - 122.

22. Рпкин В.Н. Многокритериальный нечеткий выбор // Тез. докл. Вс. науч.-техн. конф. "Применение микропроцессоров, микро- и персональных ЭВМ. Миасс, 1990. С.44 - 45.

23. Митюшин Ф.Ф., Ручкин В.Н., Цыцаркин Ю.М. Исследование структуры организации вычислительной системы коллективного пользования телеобработки данных // Тез. докл. Вс. науч.-техн. конф. "Техническое и программное обеспечение передачи и телеобработки данных в ИБС и АСУ". Рязань: Рязан. радиотехн. ин-т, 1985. С.83 - 87.

24. Панков И.Г., Ручкин В.Н. Аппаратно - микропрограммная реализация протоколов в локальных вычислительных сетях // Тез. докл. Пятой Вс. науч.-техн. конф. по вычислительным сетям КОМПАК-87. 4.2. Рига: ИЭиВТ. 1987. С. 153 - 157.

25. Курашин В.Н., Ручкин В.Н. Возможности представления протоколов на нечетких множествах // Тез. докл. Вс. науч.-техн. сов. "Перспективы