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

РГВ од

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

СКВОРЦОВ Сергей Владимирович

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

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

системы и сети 05.13.11 - Математическое и программное

обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Рязань - 1999

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

Научный консультант - Заслуженный деятель науки и техники РФ,

доктор технических наук, профессор В.П. Корячко

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

Д.В. Гаскаров

доктор технических наук, профессор В.В. Игнатущенко

доктор технических наук, профессор И.Ю. Кашнрин

Ведущая организация -

НИИ "Аргон", г. Москва

Защита состоится 22 марта 2000 г. в 12 часов на заседании диссертационного совета Д 063.92.03 в Рязанской государственной радиотехнической академии по адресу: 391000, г. Рязань, ГСП, ул. Гагарина, 59/1.

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

Автореферат разослан

- /г -

января 2000 г.

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

} т.ш. г -0/6,3с не, о

И.А. Телков

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

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

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

В целом суперскалярный микропроцессор может одновременно выполнять несколько операций в разных ФУ или совмещать их выполнение в одном ФУ до тех пор, пока эти операции независимы по данным. В частности, к процессорам с суперскалярной архитектурой относят известную модель i860 фирмы Intel , процессор отечественной суперЭВМ "Эльбрус-3", а также другие универсальные и специализированные процессоры отечественных и зарубежных производителей.

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

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

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

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

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

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

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

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

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

Основные задачи работы формулируются следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- учитывается режим работы процессора (скалярный или конвейерный);

- допускаются разные критерии оптимизации (время исполнения, длина объектного кода, длина кода при ограничении на время исполнения).

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

- имеется один РгФ, доступный для всех ФУ процессора;

- процессор содержит несколько РгФ, каждый из которых является доступным для некоторого подмножества ФУ;

- каждое ФУ процессора имеет отдельный набор регистров (для суперскалярных процессоров на основе микропрограммируемых БИС).

4. Для организации диагностических процессов на макроуровне параллельных вычислений в магистрально-модульных многопроцессорных системах обоснован выбор симметричной диагностической модели (ДМ), применение которой позволяет существенно уменьшить число взаимных проверок вычислительных модулей для определения их технического состояния по сравнению с классическими моделями РМС (Preparata, Metze, Chien) и BGM (Barsi, Grandoni, Maestrini). Для выбранной ДМ впервые получено:

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

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

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

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

Практическая ценность работы. С использованием представленных в диссертации теоретических результатов и инструментальных программных средств с 1983 года проведено 19 НИР и ОКР. Эти работы выполнялись в рамках важнейшей хоздоговорной и госбюджетной тематики в соответствии со следующими руководящими документами: межведомственные программы фундаментальных и поисковых исследований на 1981-1985 г.г. и на 19861990 г.г.; решение ВПК № 328 от 05.10.85; приказ Минвуза РСФСР № 136 от 02.12.85 г.; приказ Комитета по высшей школе Миннауки России № 473 от 22.07.92; комплексные научно-технические программы Минвуза СССР "Микропроцессоры и микроЭВМ" и Минвуза РСФСР "Океанотехника"; межвузовские научно-технические программы "Охрана интеллектуальной собственности" и "Интеллектуальная собственность высшей школы".

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

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

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

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

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

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

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

- ГП ОКБ "Спектр" при Рязанской государственной радиотехнической академии (г. Рязань) - в процессе разработки и оптимизации программного обеспечения протоколов канального уровня специализированной сети передачи данных (в рамках ОКР "Резеда"), а также при разработке программного обеспечения автоматизированной системы проведения натурных испытаний сложных технических комплексов (ОКР "Экспресс");

- ЦНИИ 4 Министерства обороны России (в/ч 25840) - при разработке и оптимизации объектного кода специализированного программного обеспечения для информационно-расчетной системы "Ярус-М" в рамках НИР "Передовик -122-9";

- НИИИ 21 Министерства обороны России - для повышения эффективности комплекса программ по моделированию процессов функционирования системы восстановления автомобильной техники путем оптимизации объектного кода ряда программ этого комплекса;

- Научно-производственный центр ОАО "Рязанский радиозавод" (г. Рязань) - в процессе разработки пакета программ по подготовке данных и управлению технологическим оборудованием;

- ЗАО "Композит" (Рязанская область) - при проектировании отказоустойчивой распределенной многопроцессорной системы управления технологическим оборудованием, предназначенным для работы в условиях химически агрессивной внешней среды.

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

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

аппаратуры" (Владимир, 1983); Всесоюзная школа-семинар ЕС ЭВМ - 85 "Разработка и применение в народном хозяйстве ЕС ЭВМ" (Кишинев, 1985); Всесоюзная школа-семинар "Разработка и внедрение в народное хозяйство систем автоматизированного проектирования ЭВМ и БИС" (Ереван, 1986); IX Всесоюзный симпозиум "Логическое управление в промышленности" (Ташкент, 1986); X Всесоюзный симпозиум "Логическое управление с использованием ЭВМ" (Ижевск, 1987); Всесоюзная школа-семинар ЕС ЭВМ -87 "Разработка и внедрение в народное хозяйство ЕС ЭВМ" (Тбилиси, 1987); III Всесоюзное совещание "Высокопроизводительные вычислительные системы" (Таллин, 1988); школа-семинар "Организационно-экономические вопросы создания вычислительных комплексов и систем" (Москва, ВДНХ, 1989); Всесоюзная школа-семинар ЕС ЭВМ - 89 "Разработка и внедрение в народное хозяйство ЕС ЭВМ" (Киев, 1989); 2-я Всесоюзная конференция "Повышение эффективности средств обработки информации на базе математического и машинного моделирования" (Тамбов, 1991); Международный форум информатизации МФИ-92 (Москва, 1992); Международная конференция "Технологии и системы сбора, обработки и представления информации" (Рязань, 1993); Всероссийская конференция "Новые информационные технологии в научных исследованиях радиоэлектроники" (Рязань, 1997); 3-я Международная конференция "Теория и техника передачи, приема и обработки информации" (Туапсе, 1997); 7-й Международный семинар "Проблемы передачи и обработки информации в информационно-вычислительных сетях" (Рязань, 1997); 2-я Всероссийская конференция "Современные информационные технологии в образовании" (Рязань, 1998); Всероссийская конференция "Новые информационные технологии в радиоэлектронике" (Рязань, 1998); Международная конференция "Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем" (Пенза, 1998); 2-я Московская Международная телекоммуникационная конференция "Молодежь и наука" в научной сессии МИФИ (Москва, 1999); 4-я Всероссийская конференция "Новые информационные технологии в научных исследованиях и в образовании" (Рязань, 1999); 8-й Международный семинар "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций" (Рязань, 1999); конференции профессорско-преподавательского состава Рязанской государственной радиотехнической академии (Рязань, 1986, 1988, 1996 - 1999).

Публикации. Результаты диссертационной работы нашли отражение в 82 опубликованных научных работах, среди которых 1 монография, 20 статей в научно-технических журналах, 2 учебных пособия, 5 свидетельств об официальной регистрации программ для ЭВМ в РосАПО и РОСПАТЕНТ.

Структура и объем диссертации. Диссертационная работа состоит из введения, 6 разделов, заключения, списка литературы (318 наименований), изложенных на 425 страницах, и содержит 28 таблиц и 76 рисунков. Приложения на 43 страницах дополнительно включают 11 таблиц и 3 рисунка. Общий объем диссертации 468 страниц.

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

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

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

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

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

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

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

- все КС имеют одинаковую длину. В каждом слове выделяются группы разрядов (поля), связанные с одним или несколькими ФУ. При этом невозможно одновременно инициировать операции в различных ФУ, сопоставленных одному или разным, но пересекающимся полям командного слова;

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

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

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

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

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

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

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

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

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

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

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

Для решения задач организации вычислений на микроуровне параллелизма предложена новая модель - дизъюнктивный граф информационно-структурных зависимостей С* = (А, V, Е), которая строится на основе ГЗД б = (А, V) добавлением множества неориентированных Е ребер, связывающих каждую пару вершин, соответствующих неупорядоченным конфликтным операциям, не допускающим параллельное выполнение из-за ограничений, обусловленных архитектурой реального процессора (для суперскалярных процессоров эти ограничения проявляются в виде конфликтов доступа к ФУ и кодирования инструкций в КС). Такая модель строится на основе множества операций Л = {аь а2, ■■., а„} программы, каждая из которых реализуется инструкцией а1 = (С,, /ь 01, ыь /ь Г,), где С, - код операции, I, - множество регистров с данными (операндов), О, - множество регистров для результатов, и, - необходимое ФУ, /, - множество разрядов (поле) КС для кодирования инструкции а, и Г, - время выполнения (в тактах).

Граф б* задается множествами дуг Vи ребер Е = Е1 и Е2, где подмножество Е{ описывает конфликты доступа к ФУ, а Е2 - конфликты кодирования: V = {(а„ а,): / <у, (О, п 1,) и (/, п О,) и (О, пО^0}. £, = {[я„ а,-]: = = и,};

Ег = {[а/, а;]: ¿¡у = </,-, = 0,и1 * и,; /, п/} * 0}, где с1ц - элемент матрицы достижимости В = исходного ГЗД С?.

Дизъюнктивный граф в* = (А, V, Е) информационно-структурных зависимостей, в отличие от известных моделей, отражает не только алгоритмические, но и архитектурные ограничения на параллельное выполнение инструкций программы и может использоваться для решения задач как локальной оптимизации объектного кода в пределах линейных участков (ЛУ) программы (подобно ГЗД и его модификациям), так и глобального анализа и оптимизации программы с циклами и ветвлениями (где обычно используется управляющий или б алогический граф).

Определены основные критерии оптимизации, используемые при генерации последовательности КС П¥ = (И¥и ..., Ь\УЫ) объектной программы: минимальное время исполнения; минимальное число непустых КС. Показано использование дизъюнктивного графа О* для решения задачи локальной оптимизации объектного кода. Пусть множество бесконтурных орграфов, порождаемых заменой каждого ребра [а„ а/\ е Е дугой (а„ а;) или (а,, а,), обозначено как М0* = {б) = (А, К,), й2 = (А, У2),..., = (А, Ур)}. Каждый бесконтурный орграф С, е Ма» определяет вариант расписания параллельного выполнения инструкций исходного ЛУ программы. Такое расписание фиксирует значения моментов (/ = 1, п) времени инициирования инструкций а, е А в ФУ суперскалярного процессора и, тем самым, однозначно определяет состав каждого КС НУ] = {а, е А: = 7} объектной программы Ь\У. Для решения задачи по критерию времени требуется определить орграф О,. = (А, V,*) с

минимальной длиной критического пути. Количество непустых КС программы определяется числом слоев вершин этого графа.

Выделены два частных случая задачи локального синтеза последовательности LWпо критерию времени, обусловленные различиями в архитектурных характеристиках целевого процессора. В первом случае предполагается, что разные ФУ процессора не позволяют реализовать операции одного типа, и для выполнения любой операции программы может быть использован только один вариант инструкции. Для каждой пары упорядоченных операций а, и aj, такой, что (а,, е F должно выполняться неравенство

tj-U^T,. (1)

Каждая конфликтная пара инструкций [а, , е Е определяет условия

¡M'Q-yrf+tj-t.ZR,;

\ M*yiJ+ti-tj>Rj, ^

гдеy,j = 1, если a,eLJVt и üjgLWi, где к < /, иуи = 0, если к> I, М* - большое число, константы Rj и Rj задают число тактов между началом выполнения конфликтных операций ah aj и определяются видом конфликта (доступа к ФУ или кодирования), а также режимом работы процессора (скалярный или конвейерный). Для конвейерного режима всегда R,= Rj - 1. В скалярном режиме Rk= Tk для [а,, а,\ е£,и Rk-1 для [а,, ау] е Е2, где к е {i,j}.

Задача синтеза оптимальной по быстродействию параллельной объектной программы LW состоит в нахождении значений целочисленных переменных t, иyij (i,j = 1 ,п), которые удовлетворяют неравенствам (1), (2) и обеспечивают минимум целевой функции min F = шах (/, + Г,), а, е А.

Второй случай допускает выполнение операций с выбором необходимых инструкций из нескольких вариантов, соответствующих различным ФУ процессора или управляющим полям КС. Такое неоднозначное представление операций имеет вид а, = (С,, /,, О,, £/,, F,, ©,), где t/,c£/ - подмножество ФУ, которые могут использоваться для выполнения операции типа С,, F, и 0, - соответствующие множества полей КС и интервалов времени реализации. Если подмножество U, включает /И; < \ U | ФУ, то неоднозначное представление операции о, 6 А порождает /и, вариантов интструкций

ар>=(С„/„0(,«<4>, /f\7f>), _

отличающихся характеристиками е Ft и е ©,, где к = 1, ml .

Здесь для каждой пары (ah а,) е К должно быть справедливо неравенство

т,

tj-t,> Ъх1кТ<к), (3)

к=\

где xlk= 1, если для реализации а, используется ФУ , и х,к~ 0 п остальных

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

т,

Ъх1к=\. (4)

Определим множества пар Е™ и Е^ инструкций, параллельное выполнение или инициирование которых невозможно из-за конфликтов доступа к ФУ или конфликтов кодирования соответственно:

Е? = {[ , 4') ]: с1и = с111 = 0, и\р) = и<'>};

= {[ . ]: ¿у= =о. * > п *0 >;

Тогда для конфликтных пар инструкций должны выполняться условия: (М*(1-уи) + 1;-11>А1-М**[(1-х,р НО-*,,)];

где Д,= Т\р), Ау= Г7(/) для [ а<р), ] е Е? и А, = Д, =1 для [ а\р), ] е £2И',

Л/** - большое число, такое, что М** » М*.

Задача синтеза оптимальной по критерию времени последовательности КС с учетом неоднозначного представления операций заключается в нахождении значений переменных хц, которые удовлетворяют условиям (3), (4), (5) и обеспечивают минимальное значение целевой функции

т,

тах(г, + I х1кТ$к)).

а,еА 1

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

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

- для второго случая на его основе строится дизъюнктивный граф

= (Л* , У" ,Е") вариантов информационно-структурных зависимостей,

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

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

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

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

В третьем разделе представлены разработанные методы локальной оптимизации параллельных объектных программ в пределах ЛУ кода.

Минимизация времени исполнения ЛУ объектной программы выполняется с использованием комбинаторного метода ветвей и границ на основе дизъюнктивного графа G* = (А, V, Е) со скалярными весами Т, вершин а, е А, который имеет одну входную ай и одну выходную а„+1 вершины.

Соответствующий искомому орграфу G,. = (А, F,») критический путь (V[<70, a„+i] обозначим как цкр(Сг*) и будем называть минимальным критическим путем дизъюнктивного графа G*, так как его длина Z,(pKp(G*)) удовлетворяет условию Z(|aKp(G*)) = LKp(G,.) = min £Kp(G,), G/€ MG*.

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

порождаемых дизъюнктивными графами G, = (А, v\ ,е}) иGl2 = (А, v\, Е\), которые получаются заменой ребра [ах, ау] е Е дугами (ах, ау) е F,' для G{ и (ау, ах) е v\ для G\. Пусть на некотором .v-м шаге (5 > 2) имеются множества М\ , М\ ,..., М/(у), еще не подвергавшиеся разбиению и порождаемые графами G/ = (А, V-, Е-), / = 1, l(s). Среди них выбирается множество А/у(» с минимальной оценкой целевой функции, задаваемое графом G*(v) = (А, Esv{s)), и вновь разбивается на два подмножества М^ , и Мф) 2 • Затем все соответствующие неразветвленным вершинам дерева поиска подмножества заново обозначаются как Ml*1, Mj+1,...,

В качестве нижней границы целевой функции на множестве М- вариантов решения, порождаемых дизъюнктивным графом Gf =(А, К/, Е-), используется оценка r|(M/) = IKp(G/ ), где G,1 = (А, У/). Правомерность

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

Теорема 1. Если для дизъюнктивных графов Н* = (А, V, Eh) и G* = (А, V, Е) множества ребер Eh и Е удовлетворяют соотношению Eh с Е, то справедливо неравенство ¿(цкр(#*)) < I((jKp(G*)).

Следствие. Орграф G = (А, V), полученный из любого дизъюнктивного графа G* = (А, V, Е) исключением всех ребер, имеет критический путь величины IKp(G) < I(pKp(G*)).

Для ветвления дерева поиска на очередном шаге рекомендуется выбирать такое ребро е, = [ах, ау], которое удовлетворяет условию тах | Л(<?7) I, где

С целью сокращения перебора при поиске оптимального решения доказана теорема 2. Пусть задан дизъюнктивный граф в* = (А, V, Е), и для орграфа С7 = (А, V) известны пометки Х(а,) вершин, определяющие величины максимальных путей Я/], причем длина любой дуги (а„ о,) е К соответствует значению Г/. Упорядочим ребра е = аД по убыванию показателя 5(е;) = шах {^(с^,) - Х(ах) - 1ху, Х(ах) - - 1ух), где 1ху = Кх,

1ух= Яу- длины дуг (ах, ау) и (ау, ах) соответственно. В итоге получим последовательность еь е2, ■■■, еу, ..., еь, в которой Ь = \Е\ и е* - первое по порядку ребро, удовлетворяющее условию 5(е*) < 0.

Теорема 2. Дизъюнктивные графы С* - (А, V, Е) и Н*= (А, V, Ен) имеют равные значения ¿(цкр(0*)) = ¿(цк„(Я*)) минимальных критических путей, если выполняется условие ЕИ = Е \ {еь е2,..., е^}.

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

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

Для второго частного случая задачи синтеза последовательности КС с учетом неоднозначно представленных операций разработан метод решения, основанный на использовании итерационной процедуры построения дизъюнктивного графа вариантов С™ на базе исходного ГЗД в = (А, V) с векторными весами ©¡ = Гр^,..., т{т,г>) вершин а, е А. Граф С" описывает не более т\т2...т„ вариантов графовых моделей вида С* со скалярными весами и при. замене ребер дугами порождает орграф вариантов, построение которого на каждой итерации позволяет исключить из дальнейшего рассмотрения "наихудшие" варианты реализации инструкций программы. Итоговый выбор по одному элементу из каждого вектора ©, называется С-выборкой и задает один вариант исполнения каждой операции. Предложенный метод обеспечивает поиск на орграфе вариантов б-выборки с минимальной длиной критического пути, определяющей искомый вариант объектной программы, и использует для этого алгоритмы синтеза КС на основе модели вида С*.

Задача синтеза параллельной объектной программы по критерию минимального объема занимаемой памяти сведена к построению последовательности Ь\У, содержащей минимальное число непустых КС Ь\У1 ф 0. Разрабо-

таны методы решения, которые используют алгоритмы синтеза КС по критерию времени для дизъюнктивного графа б* и обеспечивают получение:

- глобального минимума числа непустых КС объектной программы;

- наименьшего числа непустых КС при ограничении на время исполнения. Предложен алгоритм последовательного сокращения числа непустых КС в

заданной графом С,. = (А, V,*) программе ¿IV = (ЬШ1, ЬЖ2, ..., основанный на объединении соседних непустых КС ЫУ1 и ЬIV, (/ < у), инициирующих независимые по данным операции. Приращение

= шах тах {/(¿Ж) + 1кр - *_},

а„еЩ арчТ'\ак)

общего времени исполнения, где 1кр - длина дуги (ак, ар) е К/, и = Ц

для аI е ЫУр определяет возможность преобразования программы на каждой итерации алгоритма. Его трудоемкость оценивается как 0{п ) действий.

Решение задачи размещения временных переменных, минимизирующее число одновременно занимаемых регистров, выполняется на основе графа потока данных С = (А, V), где V = {(а„ а/): /' <у, (О, п /у) Ф 0}, и последовательности Ы¥, фиксирующей значения для а, е А. При этом общее число необходимых регистров определяется как

М

V)/* = £ { шах Ч?¡ОиЬ,...,(„, х)}

/= 1 *е[1,ЛЧ

с использованием функции загрузки регистрового файла RFt е Ш7 вида

п

^/('ь Н, »., х) = Хд/,(р(е/,х) > /=1

1, если* е[г+ 7], шах {?,}]; г, _ _„

' ' о.ег(в,) 7 1, если 0/ п RF¡ Ф 0;

ф(/„ х):

я;ЕГ (О,) ^

О при х < tj + Tj или х > max {i }; 10 при Ot n RFt = 0,

где RF - множество регистровых файлов процессора.

Задача заключается в определении разбиения А - А, и Аг и ... и такого, что результаты г(а¡) операций я, е Aj можно поочередно хранить в одном регистре Rj, и сводится к решению задачи Дилворта построения множества непересекающихся путей D = {ць ц2, —, Щ«}, V* —> min, содержащих в совокупности все вершины некоторого графа G* - (А, V*). При этом каждый путь \i.j е D определяет расписание загрузки одного регистра Rj. Распределение занимаемых регистров по РгФ процессора производится окрашиванием вершин графа G* в соответствующие цвета.

Разработан метод размещения временных переменных в регистрах, минимизирующий общее число обращений к оперативной памяти и имеющий полиномиальную оценку трудоемкости 0(п2). Его применение допускается как для последовательных, так и для параллельных вычислений в суперскалярном процессоре с различной организацией регистровой памяти. Число

доступных РгФ и способы пересылок данных между ними учитываются при формировании графа (3 * на основе графа О и последовательности КС 1Л¥.

Основная доля скалярных операций ЛУ программ выполняется при вычислениях арифметических выражений, для эффективного распараллеливания которых требуется формирование ГЗД (дерева операторов) минимальной высоты. Показано, что известные алгоритмы микрораспараллеливания выражений обеспечивают получение хороших результатов только для частных случаев, когда не используются скобки, некоммутативные операции, или требуется преобразование выражения в польскую запись и др. В связи с этим разработан алгоритм генерации тетрадной формы арифметических выражений с полиномиальной оценкой трудоемкости 0(к2), где к - число операндов, который минимизирует высоту порождаемого дерева операторов, увеличивая тем самым потенциальные возможности распараллеливания выражения при формировании объектного кода. Предложенный алгоритм сочетает преимущества наиболее известных методов и распространяет их на выражения, которые могут быть составлены с использованием полного набора арифметических операций реального ШБС-процессора с суперскалярной архитектурой без каких-либо дополнительных ограничений.

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

Машинно-независимое представление программы с циклами и ветвлениями в виде последовательности яь а2> ..., а„ операций в тетрадной форме

а, = (С„ /}]), , О,), определяющей тип С,, операнды /,-1), 1\2> и результат

содержит операции безусловного перехода (.¡т, , , а*) к выполнению операции условных переходов к операции по нулевому (¡тг, X, , положительному Отр, X, , а к), отрицательному (.¡тп, X, , а к) и другим значениям операнда^, где к > / или к < /.

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

процедур анализа информационной зависимости операций а1 (/ = 1, п) с учетом выделенных фрагментов разработан метод построения билогического графа программы вида = (А, Vб), вершины которого соответствуют множеству А = {аь а2, ..., а„] операций, а дуги задают связи по данным и управлению. С каждой вершиной сопоставляется одна из пар вида (&, &), (&, ®), (©, &) или (Ф, ©), задающая условия входа и выхода с помощью логических функций И ("&") и ИСКЛ. ИЛИ ("Ф"), что определяет разбиение А - А&& и А&© и и А®©.

Показано, что билогический граф адекватно описывает структуру объектной программы на микроуровне параллелизма (но не учитывает ограничений на параллелизм операций из-за конфликтов по ресурсам) и используется для построения иерархической дизъюнктивной модели Н** =(А*, V*, Е*),

которая формируется на основе р > 1 множеств Мр = {} вложенных

дизъюнктивных графов ~(А^Р\ У^р\ информационно-структурных зависимостей, отражающих возможные варианты конфликтов инструкций на каждом р-м уровне иерархии (р = 1, р*), где р* - максимальный уровень. Число элементов Мр определяется количеством циклических, условных и альтернативных ветвей равного уровня вложенности, а множество

Мр = - (А\р*\ У\Р'\ е\р всегда содержит один элемент

#(/>•) = где А+ = А{р') > у* = у(Р') пЕ* =Е(Р>) _

Построение модели Я** производится с низшего (нулевого) уровня иерархии р = 0, для которого считаем, что С б = . Переход на следующий

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

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

множество А&& с корректировкой А&&, ЛФ&, А®® и далее рассматривается как макрооперация, блокирующая доступ к любым ресурсам процессора на период Т( или Т( р^'), величина которого определяется в результате синтеза последовательности КС 11У( или Ы¥( Р^)) временем ее исполнения. Любая макрооперация считается конфликтной для любых других операций и макроопераций.

Таким образом, к моменту окончательного формирования иерархической модели #** для каждой макрооперации известно время исполнения и соответствующий список КС. Итоговая последовательность ¿IV формируется на основе дизъюнктивного графа Н** с последующей заменой входящих макроопераций а[р) и р^ списками КС I \У{ а[р)) и Н¥($[р)).

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

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

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

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

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

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

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

Результат ЭП, в которой участвует пара модулей {и,, иД с и обозначается как лу е {0,1}, где = 0 при совпадении полученных результатов и = 1 - в

противном случае. Множество ЭП, выполняемых за цикл контроля системы и необходимых для определения технического состояния всех ВМ, задается диагностическим графом вида H=(U,L), где вершинам U = {щ, щ, ..., и„.i} сопоставлено множество ВМ, а каждая дуга (м„ и,) е L задает одну ЭП, где г/, - контролирующий ВМ, м, - контролируемый, и взвешивается ее результатом s,, е {0, 1}. Совокупность всех значений stj, полученных за очередной цикл контроля, образует текущий синдром S системы.

Если дешифрация синдрома S позволяет правильно определить все неисправные ВМ, число которых не превышает t, то система называется t-диагностируемой. Могут выявляться все неисправные модули одновременно (при параллельном /-диагностировании) или хотя бы некоторые из них (при последовательном /-диагностировании). Далее рассматривается параллельное /-диагностирование, где / - мера диагностируемости.

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

Диагностическая модель задается четверкой переменных (srr, sr{, s{r, ¿уД где первый индекс указывает состояние контролирующего, а второй - контролируемого ВМ (г - работоспособен, /- отказал), причем с учетом свойства полноты ЭП всегда srr - 0 и sri = 1, а переменные и Sff могут принимать любое из значений {0, 1, х}, где х означает непредсказуемый результат ЭП (О или 1). Наиболее известными являются модели РМС и BGM, которые описываются как (0,1, х, х) и (0,1, х, 1) соответственно.

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

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

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

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

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

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

ДМ вида (0,1,1,1) называют симметричной, так как результат эу е {0, 1} любой ЭП сохраняется при взаимном изменении функций ВМ (контролирующий - контролируемый). При ее использовании ДГ может быть представлен как неориентированный граф С7 = (£/, £>), где ребро [«,, иу] е О задает одну ЭП, в которой оба ВМ являются взаимоконтролирующшш (без жесткой фиксации функций).

Для ДМ (0,1,1,1) получено решение задачи характеризации, которое расширяет и обобщает известные результаты. Оно устанавливает необходимые и достаточные условия, сформулированные на основе принципов харак-теризационного анализа и определяющие структуру проверочных связей, которые описываются неориентированным ДГ и гарантируют получение заданной меры параллельной диагностируемое™ многопроцессорной системы.

Пусть граф й = (и, й) описывает систему с заданным значением / < п - 2. Если структура проверочных связей обеспечивает параллельную /-диагности-румость в рамках модели (0,1,1,1), то будем считать, что граф й е М обладает свойством /(0,1,1,1), где М - множество всех возможных ДГ, некоторые из которых могут и не иметь указанного свойства. Характеризационная проблема сводится к поиску множества Мг = { в? } запрещенных фигур вида

О^ = (и?, Ц2), отсутствие которых вбе М^, где Ма с М - подмножество допустимых ДГ, является необходимым и достаточным условием того, что й обладает свойством /(0,1,1,1), и при этом никакая из моделей й,2 е М2 не присутствует в другой запрещенной фигуре е М2.

Теорема 3. Диагностический граф (3 = (С/, й) с числом вершин и > / + 2 обладает свойством /(0,1,1,1), если и только если в й отсутствуют запрещенные фигуры следующих видов:

1) вершина и, е и, для которой с!е§(ы,) < / (фигура вида );

2) симметричный полный двудольный граф Ку „ = 0\ = (/У2г, ), такой, что каждая доля содержит 1 < V < / вершин и выполняются условия:

с!евСи|) = г, ы/е£/|; Т{Щ) = IV, \¥с и\Щ, | IV I = /-у; ¿(Щ, и \ IV) = 0, где с!(Хи Хг) = {[к,, «,] е В: и,еХъ и, еХъ Х1 с £/,Хг с и}.

На основе известного множества Мг запрещенных фигур предложено решение проблемы синтеза оптимальных неориентированных ДГ с минимальным числом ребер для симметричной ДМ вида (0,1,1,1).

Теорема 4. Диагностический граф G = (С/, D) с числом вершин п = t + 2 обладает свойством /'(0,1,1,1), если истинно условие \D„ \ Z)| < 1, где £>„ -множество ребер полного графа К„ = (JJ, D„).

Таким образом, при t = п - 2 ДГ с минимальным числом связей представляется как полный граф на п вершинах без одного любого ребра, что доказывается теоремой 4. Для значений 1 < t< п-2 разработаны и обоснованы эффективные процедуры малой трудоемкости, обеспечивающие построение ДГ с минимальным числом ребер.

Введено понятие абсолютно диагностируемого графа, под которым будем понимать неориентированный граф G, обладающий свойством /(0,1,1,1) для 1 <t<n- 2, если соответствующий ему дополнительный граф G обладает свойством F(0,1,1,1), где t = n-t- 1. При этом G также является абсолютно диагностируемым графом. В соответствии с теоремой 3 абсолютно диагностируемым может быть только такой граф G - (U, D), для которого deg(i/,) = t, и, е U.

Рассмотрим итерационную процедуру Р\ циклического построения графа G = (U, D) для четных значений /, таких, что 2 < t < п-Ъ. Процедура Р, начинает работу с пустого графа G(0) = {U, D(0)), где = 0. На очередной £-й итерации вводится п ребер, связывающих все вершины в один или несколько простых циклов, что увеличивает степень каждой вершины на два. В результате образуется граф G(k} = (U, £>w) с множеством ребер

£>(*> = £,(*-') u {[м. „.].j = + mod i = о, л-1}, для всех вершин и, s U которого имеем deg(z/,) = 2k. Окончательно получаем граф G = G(r), где г = t/2.

Теорема 5. Процедура Р\ порождает абсолютно диагностируемый граф G для четных значений t, удовлетворяющих условию t < п-Ъ.

В соответствии с теоремой 5 и свойствами абсолютно диагностируемого графа процедура Р\ обеспечивает построение оптимальных ДГ, обладающих свойством /(0,1,1,1), для следующих случаев: 1) п - четное число, 2 <t < п -3; 2) п - нечетное число, / - четное число из диапазона 2 < / < я-З.В первом случае для нечетных значений / с помощью процедуры Pt строится граф G , обладающий свойством 7(0,1,1,1), где / = (п - t - 1) - четное число, а в качестве искомого ДГ выбирается дополнительный к G граф G.

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

для

к = (/ + 1) /2, а затем процедура Рг удаляет из него г = (и -1) /2 ребер по следующему правилу: _

£>=DW\ {[и/, Uj] : / ~ 2т - 1, j — 2т, т=\,г}, где D - множество ребер искомого графа G=(U, D).

Теорема 6. Процедура Рг порождает ДГ 0={и,П), обладающий свойством /(0,1,1.1) Для нечетных значений п и /, таких, что 3 </< п - 4.

Предложенные процедуры обеспечивают решение проблемы синтеза оптимальных ДГ с минимальным числом ребер для симметричной ДМ вида (0,1,1,1). Процедура Р\ позволяет строить графы, в которых число ребер определяется как |£)| = п1 /2. Последовательное применение Р\ и Р2 для случая, когда п и / - нечетные числа, гарантирует получение минимальных ДГ с числом ребер \о\ = (п( + 1)/2. Малая трудоемкость процедур, которая оценивается как <5(0,5/л) для Р\ и 0(0,5«) - для Р2, позволяет использовать их для оперативного синтеза ДГ с минимальным числом проверочных связей при реконфигурациях отказоустойчивых многопроцессорных систем в режиме реального времени.

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

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

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

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

ность (98 % решений совпали с оптимальными, причем для числа операций более 40 отклонений от оптимальных результатов не наблюдалось).

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

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

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

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

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

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

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

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

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

Разработана и официально зарегистрирована в РосАПО программа анализа потоков команд в цифровых системах, построенных на базе микропроцессоров класса Intel 80x86, которая выполняет функции дизассемблирования стандартного исполняемого файла, определение структуры управляющего графа программы с вычислением длины (в байтах) и времени исполнения (в тактах синхронизации) отдельных команд и ЛУ. Для построения управляющего графа использованы предложенные алгоритмы анализа глобальной структуры программы, результаты работы которых, включающие списки ЛУ и составляющих их команд с оценками времени и длины, позволяют автоматизировать процесс выделения фрагментов кода с заданным временем исполнения, необходимых для выполнения ЭП (путем реализации параллельных вычислений) при организации активной отказоустойчивости многопроцессорных систем с магистральной организацией.

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

В приложениях приводятся результаты экспериментов по исследованию алгоритмов оптимизации параллельного объектного кода и генерации тетрад-

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

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

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

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

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

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

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

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

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

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

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

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

- для диагностической модели (0,1,1,1) получено новое решение задачи характеризации, которое расширяет и обобщает известные результаты, а также впервые предложено решение проблемы синтеза оптимальных неориентированных ДГ с минимальным числом ребер для заданной меры параллельной диагностируемое™ многопроцессорной системы;

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

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

5. Основные результаты диссертационной работы внедрены:

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

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

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

- в виде монографии, 2 учебных пособий, ряда методических и научных изданий, а также разделов лекционных курсов, изучаемых студентами специальностей 220300 "Системы автоматизированного проектирования" и 220500 "Конструирование и технология электронных вычислительных средств" в Рязанской государственной радиотехнической академии.

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

1. Корячко В.П., Скворцов C.B., Телков И.А. Архитектуры многопроцессорных систем и параллельные вычисления. М.: Высш. шк., 1999. 235 с.

2. Корячко В.П., Скворцов C.B. Планирование загрузки регистровой памяти при микропрограммировании микропроцессорных систем // Автоматика и вычислительная техника. 1987. №4. С. 75-80.

3. Гершанов В.И., Скворцов C.B. Синтез микропрограмм и оценка качества структуры микропроцессорных систем управления процессами реального времени // Вопросы радиоэлектроники. Серия Электрон, вычисл. техн. 1987. Вып. 5. С. 90-97.

4. Корячко В.П., Скворцов C.B., Шувиков В.И. Формирование микропрограммных управляющих слов для микропроцессорных систем // Электронное моделирование. 1987. № 6. С. 19-22.

5. Корячко В.П., Скворцов C.B., Телков И.А. Построение микропрограмм с циклами и ветвлениями для специализированных микропроцессорных систем // Электронное моделирование. 1988. № 1. С. 17-22.

6. Гершанов В.И., Скворцов C.B., Телков И.А. Синтез параллельных форм алгоритмов функционирования специализированных вычислительных систем // Вопросы специальной радиоэлектроники. Серия Электрон, вычисл. техн. 1989. Вып. 1. С. 37-46.

7. Скворцов C.B. Средства синтеза микропрограмм для магистрально-модульных микропроцессорных систем // Автоматика и вычислительная техника. 1990. № 2. С. 88-93.

8. Гершанов В.И., Скворцов C.B. Рациональное использование управляющей памяти при параллельном микропрограммировании // Вопросы радиоэлектроники. Серия Электрон, вычисл. техн. 1990. Вып. 7. С. 44-51.

9. Гершанов В.И., Скворцов C.B., Телков И.А. Методы повышения отказоустойчивости вычислительных систем, основанных на принципе ассоциативной селекции потоков данных // Вопросы радиоэлектроники. Серия Электрон, вычисл. техн. 1992. Вып. 7. С. 50-58.

10. Скворцов C.B. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов // Программирование. 1996. № 2. С. 41-52.

11. Скворцов C.B. Организация отказоустойчивых вычислений в маги-стрально-модульных многопроцессорных системах // Вестник Рязан. гос. радиотехн. акад. Рязань, 1996. Вып. 1. С. 27-32.

12. Корячко В.П., Скворцов C.B., Телков И.А. Модель планирования параллельных процессов в суперскалярных процессорах // Информационные технологии. 1997. № 1. С. 8-12.

13. Скворцов C.B. Применение метода ветвей и границ к задаче оптимизации кода для суперскалярных процессоров // Вестник Рязан. гос. радиотехн. акад. Рязань, 1997. Вып. 2. С. 65-70.

14. Скворцов C.B. Целочисленные модели оптимизации кода по критерию времени // Информационные технологии. 1997. № 10. С. 2-7.

15. Корячко В.П., Скворцов C.B. Иерархическая модель глобальной оптимизации параллельных объектных программ // Информационные технологии. 1998. №9. С. 34-40.

16. Скворцов C.B. Применение симметричной диагностической модели при организации активной отказоустойчивости многопроцессорных систем // Вестник Рязан. гос. радиотехн. акад. Рязань, 1998. Вып. 4. С. 57-64.

17. Корячко В.П., Скворцов C.B., Телков И.А. Математическая модель мобильных вычислений // Информационные технологии. 1998. № 11. С. 27-32.

18. Скворцов C.B. Решение задачи характеризации для одной симметричной диагностической модели // Вестник Рязан. гос. радиотехн. акад. Рязань, 1998. Вып. 5. С. 23-26.

19. Корячко В.П., Скворцов C.B., Шувиков C.B. Генерация машинно-независимого кода для параллельного вычисления арифметических выражений // Информационные технологии. 1999. № 3. С. 2-7.

20. Корячко В.П., Скворцов C.B., Шувиков В.И. Характеризация диагностических графов для симметричной модели дешифрации синдрома // Информационные технологии. 1999. № 6. С. 18-22.

21. Корячко В.П., Скворцов C.B., Шувиков В.И. Синтез оптимальных диагностических графов для симметричной модели дешифрации синдрома // Информационные технологии. 1999. № 12. С. 32-37.

22. Скворцов C.B., Телков И.А.. Программа анализа потоков команд (АНАЛИЗ) / Свидетельство об официальной регистрации программы для ЭВМ в РосАПО, № 940304 от 25.07.94.

23. Буслов A.B., Скворцов C.B. Программа анализа и выбора диагностических моделей модульных систем / Свидетельство об официальной регистрации программы для ЭВМ в РосАПО, № 980507 от 20.08.98.

24. Скворцов C.B., Шувиков C.B. Программа генерации графовых моделей (ГенГраф) / Свидетельство об официальной регистрации программы для ЭВМ в РосАПО, № 980385 от 23.06.98.

26. Буслов A.B., Скворцов C.B. Программный комплекс для исследования, синтеза и оптимизации диагностических графовых моделей модульных систем / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ, № 990662 от 13.09.99.

25. Горюнов М.Е., Скворцов C.B., Шувиков C.B. Учебно-исследовательский кросс-транслятор, ориентированный на генерацию параллельного объектного кода / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ, № 990663 от 13.09.99.

27. Скворцов C.B. Проектирование языков САПР: Учеб. пособие. Рязань: РРТИ, 1991.64 с.

28. Скворцов C.B., Телков И.А. Языки моделирования в САПР вычислительных систем: Учеб. пособие. Рязань: РРТИ, 1992.48 с.

29. Скворцов C.B. Распределение ресурсов специализированной вычислительной системы при автоматизированном проектировании микропрограмм / Деп. в ЦНИИТЭИ Приборостроения 30.05.85, № 2895пр-85. 1985. 11 с.

30. Скворцов C.B. Построение оптимальной последовательности управляющих микрокоманд для специализированных микропроцессорных систем / Деп. в ЦНИИТЭИ Приборостроения 24.10.86, № 3536-пр. 1986. 15 с.

31. Скворцов C.B. Исследование алгоритмов составления расписаний для многопроцессорных систем с использованием смешанных графов / Деп. в Информприбор 20.03.89, № 4556-пр89. 1989. 17 с.

32. Скворцов C.B. Синтез параллельных объектных программ с неоднозначно заданными операциями / Деп. в ВИМИ 16.01.98, № ДО-8728. 1997. 27 с.

33. Скворцов C.B. Оптимизация скалярных вычислений в параллельных процессах: необходимость и современные средства / Деп. в ВИМИ 20.03.98, № ДО-8717. 1998.20 с.

34. Скворцов C.B. Глобальная оптимизация параллельных объектных программ / Деп. в ВИМИ 16.04.98, № ДО-8729. 1998. 30 с.

35. Скворцов C.B. Оптимизация распределения регистров в процессорах с :уперскалярной архитектурой/Деп. в ВИМИ 21.09.98, № ДО-8741.1998.30 с.

36. Скворцов C.B., Шувиков В.И. Формализованный синтез микропрограмм // Микроминиатюризация радиоэлектронных устройств: Межвуз. сб. 'язань: РРТИ, 1983. С. 17-21.

37. Скворцов C.B. Применение списочных расписаний при микропрограммировании микропроцессорных систем // Микропроцессорные устройства и автоматизация проектирования: Межвуз. сб. Рязань: РРТИ, 1986. С. 41-45.

38. Скворцов C.B. Автоматизированное проектирование символических микропрограмм для специализированных микропроцессорных систем // Проектирование вычислительных машин и систем: Межвуз. сб. Рязань: РРТИ, 1987. С. 51-54.

39. Скворцов C.B. Планирование загрузки управляющей памяти при микропрограммировании микропроцессорных систем // Автоматизация проектирования и микроминиатюризация ЭВМ: Межвуз. сб. Рязань: РРТИ, 1988. С. 37-42.

40. Скворцов C.B. Итерационный метод синтеза микропрограмм с заданными характеристиками // Автоматизация проектирования микроэлектронных вычислительных средств: Межвуз. сб. Рязань: РРТИ, 1990. С. 35-39.

41. Скворцов C.B. Модель организации параллельных вычислений в суперскалярных процессорах // Вычислительные машины, комплексы и сети: Межвуз. сб. Рязань: РРТИ, 1996. С. 41-52.

42. Скворцов C.B. Распараллеливание кода с циклами и ветвлениями на основе дизъюнктивных графов // Новые информационные технологии: Межвуз. сб. Рязань: РГРТА, 1997. С. 48-55.

43. Скворцов C.B., Скворцов Н.В. Выбор диагностических моделей для организации активной отказоустойчивости многопроцессорных систем // Новые информационные технологии: Межвуз. сб. Рязань: РГТРА, 1997. С. 55-61.

44. Скворцов C.B., Скворцов Н.В. Синтез диагностических графов с экстремальными характеристиками // Новые информационные технологии: Межвуз. сб. Рязань: РГРТА, 1997. С. 118-123.

45. Буслов A.B., Скворцов C.B. Программные средства экспериментальной оценки диагностических моделей отказоустойчивых систем // Новые информационные технологии: Межвуз. сб. Рязань: РГРТА, 1998. С. 23-31.

46. Скворцов C.B., Шувиков C.B. Синтаксический разбор выражений для параллельного вычисления // Новые информационные технологии: Межвуз. сб. Рязань: РГРТА, 1998. С. 69-74.

47. Скворцов C.B. Анализ логической структуры программы в процессе синтеза параллельного объектного кода // Новые информационные технологии: Межвуз. сб. Рязань: РГТРА, 1998. С. 75-82.

48. Буслов A.B., Скворцов C.B. Аналитический метод дешифрации результатов диагностирования многопроцессорных систем П Вычислительные машины, комплексы и сети: Межвуз. сб. Рязань: РГТРА, 1999. С. 64-68.

49. Скворцов C.B. Модель размещения временных данных в регистровых файлах суперскалярного процессора // Вычислительные машины, комплексы и сети: Межвуз. сб. Рязань: РГТРА, 1999. С. 85-89.

50. Захаров A.B., Корячко В.П., Скворцов C.B., Телков И.А. Использование метода активной защиты для повышения отказоустойчивости маги-стрально-модульных вычислительных систем // Труды Международн. форума информатизации (МФИ-92). Москва, ноябрь 1992. М., 1992. С. 217-224.

51. Скворцов C.B., Телков И.А. Средства анализа потоков команд для планирования параллельных вычислений // Технологии и системы сбора, обработки и представления информации: Тез. докл. Международн. конф. Рязань, сентябрь 1993. Рязань: Русское слово, 1993. С. 99-100.

52. Корячко В.П., Скворцов C.B. Синтез параллельных объектных программ для систем обработки данных на основе суперскалярных процессоров // Теория и техника передачи, приема и обработки информации: Тез. докл. 3-й Международн. конф., Туапсе. Харьков-Туапсе: ХТУРЭ, 1997. С. 18-19.

53. Скворцов C.B., Телков И.А. Математическая модель мобильного программного обеспечения // Проблемы передачи и обработки информации в информационно-вычислительных сетях: Тез. докл. 7-го Международн. сем. Рязань, сентябрь-октябрь 1997. М.: НИЦПрИС, 1997. С. 106-107.

54. Буслов А.В., Скворцов C.B. Имитационное моделирование диагностических процессов в модульных вычислительных системах // Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем: Сб. докл. Международн. конф. Пенза: ПГТУ, 1998. С. 83-84.

55. Скворцов C.B., Шувиков В.И. Формализованный синтез микрокоманд // Автоматизация проектирования микроэлектронной аппаратуры: Тез. докл. Всесоюзн. совещ. Владимир, ноябрь 1983. М., 1983. Ч. 1. С. 32-33.

56. Скворцов C.B. Формирование микропрограммных управляющих слов при автоматизированном проектировании микропрограмм // Разработка и применение в народном хозяйстве ЕС ЭВМ (ЕС ЭВМ - 85): Тез. докл. Всесоюзн. шк.-сем.. Кишинев, сентябрь 1985. М., 1985. Ч. 2. С. 290-292.

57. Скворцов C.B. Планирование загрузки ресурсов микропроцессорных систем на этапе синтеза микропрограммм // Разработка и внедрение в народное хозяйство систем автоматизированного проектирования ЭВМ и БИС: Тез. докл. Всесоюзн. шк.-сем. Ереван, 1986. М., 1986. С. 301-303.

58. Корячко В.П., Скворцов C.B. Метод построения микропрограмм для управляющих микропроцессорных систем // Логическое управление в промышленности: Тез. докл. IX Всесоюзн. симп., Ташкент. М., 1986. С. 57-59.

59. Корячко В.П., Скворцов C.B. Оптимизация загрузки регистров общего назначения в управляющих микропроцессорных системах // Логическое управление с использованием ЭВМ: Тез. докл. X Всесоюзн. симп. Ижевск, 1987. М., 1987. С. 98-100.

60. Корячко В.П., Скворцов C.B. Планирование параллельных вычислений в специализированных микропрограммируемых структурах // Разработка и внедрение в народное хозяйство ЕС ЭВМ (ЕС ЭВМ - 87): Тез. докл. Всесоюзн. шк.-сем. Тбилиси, 1987. М., 1987. Ч. 2. С. 73-76.

61. Корячко В.П., Скворцов C.B. Автоматизированное проектирование микропрограмм для высокопроизводительных микропроцессорных систем // Высокопроизводительные вычислительные системы: Тез. докл. III Всесоюзн. :овещ. Таллин, 1988. М., 1988. С. 181-182.

62. Корячко В.П., Скворцов C.B., Телков И.А. Синтез архитектуры шрапнельных специализированных систем обработки данных // Разработка и внедрение в народное хозяйство ЕС ЭВМ (ЕС ЭВМ - 89): Тез. докл. Всесоюзн. лк.-сем. Киев, сентябрь 1989. Киев, 1989. С. 17-20.

63. Скворцов C.B., Хрюкин В.И. Разработка параллельных алгоритмов для цифровых систем управления // Повышение эффективности средств обработки информации на базе математического и машинного моделирования: Матер. 2-й Всесоюзн. конф. Тамбов, январь 1991. Тамбов, 1991. С. 58-59.

64. Скворцов C.B., Шувиков C.B. Учебно-исследовательский компилятор, ориентированный на генерацию параллельного кода // Современные информационные технологии в образовании: Тез. докл. 2-й Всероссийск. конф. Рязань: Ряз. ин-т развития образования, 1998. С. 114-116.

65. Горюнов М.Е., Скворцов C.B. Шувиков C.B. Графовые модели генерации параллельного кода // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Матер. 8-го Международн. сем. Рязань, сентябрь 1999. Рязань: РГРТА, 1999. С. 27-29.

66. Скворцов C.B. Шувиков C.B. Статическое предсказание переходов для компиляторов параллельного кода // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Матер. 8-го Международн. сем. Рязань, сентябрь 1999. Рязань: РГРТА, 1999. С. 32-34.

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

Подписано в печать 29.12.99. Формат бумаги 60 х 84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 2,0. Уч.-изд. л. 2,0. Тираж 100 экз. Заказ Бесплатно.

Рязанская государственная радиотехническая академия. 391000, г. Рязань, ул. Гагарина, 59/1. Отдел оперативной полиграфии Рязанского областного комитета статистики. 390013, г. Рязань, ул. Типанова, 4.

Скворцов Сергей Владимирович

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

ВВЕДЕНИЕ И ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

ВЫЧИСЛЕНИЙ.

1Л. Характеристики реальных задач обработки данных и требования к современным вычислительным средствам.

1.2. Необходимость оптимизации скалярных вычислений в параллельных процессах.

1.2.1. Модели оценки эффективности параллельных вычислений.

1.2.2. Параллелизм векторных и скалярных вычислений.

1.2.3. Анализ состава операций и операндов реальных программ.

1.3. Анализ известных архитектурных решений проблемы распараллеливания скалярных вычислений.

1.3.1. Аппаратно-программные средства оптимизации скалярных вычислений.

1.3.2. Архитектурные особенности суперскалярных процессоров, влияющие на эффективность объектного кода.

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

Выводы.

2. МОДЕЛИ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В ПРОЦЕССОРАХ С

СУПЕРСКАЛЯРНОЙ АРХИТЕКТУРОЙ.

2.1. Дизъюнктивная теоретико-графовая модель организации параллельных процессов.

2.1.1. Зависимости по данным.

2.1.2. Теоретико-графовые модели параллельных программ.

2.1.3. Влияние архитектурных ограничений на параллелизм операций программы.

2.2. Теоретико-графовая модель синтеза параллельного объектного кода со скалярными весами вершин.

2.2.1. Целочисленная модель задачи оптимизации объектного кода по критерию времени.

2.2.2. Задачи локальной оптимизации объектного кода на основе дизъюнктивной теоретико-графовой модели.

2.3. Теоретико-графовая модель синтеза параллельного объектного кода с векторными весами вершин.

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

2.3.2. Локальная оптимизация параллельного объектного кода на основе теоретико-графовой модели с векторными весами вершин.

2.4. Модель глобальной оптимизации параллельных объектных программ.

2.4.1. Краткий анализ известных решений.

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

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

2.5. Сравнение с известными моделями и методами.

Выводы.

3. МЕТОДЫ ЛОКАЛЬНОЙ ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНЫХ

ОБЪЕКТНЫХ ПРОГРАММ В ПРЕДЕЛАХ ЛИНЕЙНЫХ

ФРАГМЕНТОВ КОДА.

3.1. Минимизация времени исполнения для дизъюнктивной графовой модели синтеза объектного кода.

3.1.1. Поиск оптимального состава командных слов.

3.1.2. Эвристический алгоритм синтеза командных слов

3.2. Минимизация времени исполнения объектного кода для графовой модели синтеза с векторными весами вершин.

3.3. Минимизация количества командных слов параллельной объектной программы.

3.3.1. Последовательное сокращение непустых командных слов.

3.3.2. Итерационный синтез объектных программ с заданными характеристиками.

3.4. Оптимизация загрузки регистровой памяти.

3.4.1. Аппаратная и программная модификация регистров.

3.4.2. Программные методы распределения регистров.

3.4.3. Задача размещения временных скалярных переменных в регистровых файлах суперскалярного процессора

3.5. Оптимизация скалярных вычислений в пределах арифметических выражений.

3.5.1. Краткий анализ известных методов микрораспараллеливания выражений.

3.5.2. Генерация тетрадной формы представления арифметических выражений.

Выводы.

4. МЕТОДЫ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

ПАРАЛЛЕЛЬНЫХ ОБЪЕКТНЫХ ПРОГРАММ.

4.1. Анализ логической структуры объектной программы.

4.1.1. Выделение линейных, циклических и альтернативных фрагментов кода.

4.1.2. Генерация билогической модели объектной программы.

4.2. Использование макроопределений при построении графовых моделей объектных программ.

4.3. Генерации параллельного объектного кода для структурированной программы с циклами и ветвлениями на основе дизъюнктивной графовой модели.

4.4. Генерации параллельного объектного кода для структурированной программы с циклами и ветвлениями на основе списочных расписаний.

Выводы.

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

5.1. Модель отказоустойчивой системы параллельной обработки данных с магистрально-модульной структурой.

5.1.1. Организация активной отказоустойчивости.

5.1.2. Основные предположения и понятия.

5.2. Диагностические модели в процедурах активной отказоустойчивости.

5.2.1. Классические (асимметричные) диагностические модели.

5.2.2. Симметричные модели дешифрации синдрома.

5.2.3. Общая постановка задачи синтеза диагностических графов.

5.3. Дешифрация результатов диагностирования.

5.4. Синтез диагностических графов с экстремальными характеристиками.

5.4.1. Характеризация диагностических графов для симметричной модели дешифрации синдрома.

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

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

Выводы.

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

И АЛГОРИТМОВ.

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

6.1.1. Программные средства и результаты исследования алгоритмов синтеза параллельного объектного кода.

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

6.2 Инструментальные средства генерации и оптимизации параллельного объектного кода.

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

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

6.3. Исследование диагностических графовых моделей.

6.3.1. Краткое описание использованных программных средств.

6.3.2. Результаты вычислительного эксперимента.

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

6.4.1. Программные средства синтеза и оптимизации диагностических графовых моделей отказоустойчивых многопроцессорных систем.

6.4.2. Подготовка прикладных программ для параллельных диагностических вычислений.

Выводы.

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

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

Анализ научно-технических задач 80-90-х годов позволяет сделать вывод о том, что наиболее крупные вычислительные ресурсы требуются для решения задач ядерной и термоядерной энергетики, аэро- и гидродинамики, управления и планирования в больших экономических системах, управления в реальном времени многопараметрическими объектами и т. д. Кроме того, существенных ресурсов, превышающих возможности современных ЭВМ, требуют расчеты по оптимальному распределению материально-технических средств, составлению расписаний движения транспорта, оперативному управлению оптимальной загрузкой технологического оборудования [9, 55].

Актуальность темы. Большинство перечисленных научно-технических проблем сводится к решению стандартных классов математических задач, требующих для решения значительных объемов арифметических операций. В частности [9], при постановке ряда задач существует необходимость решения систем линейных алгебраических уравнений с матрицами, порядок которых достигает 105 , и даже 106 в случае разреженных симметричных матриц. При решении нелинейных дифференциальных уравнений методом конечных элементов возникают системы нелинейных алгебраических уравнений, число которых достигает тысячи, а при использовании метода конечных разностей - нескольких тысяч.

Необходимость решения указанных и подобных задач большой размерности обусловила развитие ВС параллельной обработки с большим числом процессоров. Современный уровень развития микроэлектроники позволяет создавать системы, которые содержат десятки, сотни, и даже тысячи процессоров, для реализации которых все шире используются серийные микропроцессоры как общего назначения, так и ориентированные на применение в составе подобных систем, например, транспьютеры, RISC- и суперскалярные микропроцессоры [58, 96].

При этом организация параллельных процессов является одной из важнейших проблем, возникающих при разработке новых архитектурных решений в области современной вычислительной техники. Значительные успехи в этом направлении достигнуты в области создания больших мультипроцессорных суперЭВМ с матричной и векторно-конвейерной архитектурой [39, 56, 58, 158, 170, 242, 245, 259], которые ориентированы на макроуровень параллелизма программ, где основное внимание уделяется вопросам параллельного выполнения независимых программ и подпрограмм, а также больших программных фрагментов, таких, как независимые ветви, циклы и их отдельные итерации.

Однако в настоящее время лидирующим продуктом микроэлектроники являются [96] микропроцессоры с суперскалярной архитектурой, которые ориентированы на микроуровень параллелизма и обеспечивают достижение пиковой производительности, сопоставимой с характеристиками ВС класса суперЭВМ. Отличительной особенностью [96, 255] таких процессоров является возможность параллельного выполнения операций программы, что в итоге обеспечивает формирование нескольких результатов за каждый такт синхронизации. Это достигается благодаря наличию в составе микропроцессора нескольких функциональных устройств (ФУ) конвейерного типа. Устройство управления выполняет дешифрацию командных слов (КС) программы и инициирует (запускает на исполнение) операции в соответствующих ФУ процессора. Время выполнения операции может занимать несколько тактов, что определяется длиной конвейера ФУ.

В целом суперскалярный микропроцессор может одновременно выполнять несколько операций в разных ФУ или совмещать их выполнение в одном ФУ до тех пор, пока эти операции независимы по данным. В частности, к процессорам с суперскалярной архитектурой относят известную модель i860 фирмы Intel [58, 297, 302], процессор отечественной суперЭВМ "Эльбрус-3" [144, 150], процессор на кристалле iWarp [299] и другие современные проекты [96].

Таким образом, основным преимуществом использования микропроцессоров с суперскалярной архитектурой при построении многопроцессорных ВС является существенное расширение области применения методов параллельных вычислений (от управления параллелизмом операций программы в пределах процессора до одновременного решения множества независимых задач процессорами системы) при разработке прикладного программного обеспечения, ориентированного на решение различных классов задач обработки информации. При этом, если методы организации параллельных процессов на макроуровне вычислений исследованы в достаточном для инженерной практики объеме [6, 17,18, 38, 39, 47, 57, 130, 141, 158, 159, 170, 271], то при реализации микропараллелизма в программах для суперскалярных процессоров возникает ряд научно-технических задач принципиального характера, связанных с генерацией эффективного объектного кода.

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

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

- количество и типы ФУ могут варьироваться в широких пределах;

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

- распределение регистров для хранения временных данных может выполняться аппаратно или программно;

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

Таким образом, при создании прикладного программного обеспечения для процессоров с суперскалярной архитектурой основной проблемой является генерация эффективного параллельного объектного кода, учитывающего особенности конкретной модели процессора. Необходимость исключения или существенного сокращения практики программирования на уровне языка ассемблера [43, 96, 144] делает актуальной проблему разработки формальных моделей, методов и алгоритмов организации параллельных процессов на микроуровне вычислений, что, в свою очередь, позволяет решить проблему создания оптимизирующего кросс-компилятора для суперскалярных процессоров с программным управлением параллелизмом, обеспечивающего настройку на архитектурные особенности конкретной модели процессора.

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

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

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

В соответствии с целью основные задачи формулируются следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

- отражает не только алгоритмические, но и структурные (архитектурные) ограничения на параллельное выполнение операций программы;

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

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

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

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

- учитывается режим работы суперскалярного процессора (скалярный или конвейерный);

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

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

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

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

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

4. Обоснован выбор симметричной диагностической модели для организации процедур активной отказоустойчивости на макроуровне параллельных вычислений в магистрально-модульных многопроцессорных системах, применение которой требует существенно меньшего числа взаимных элементарных проверок вычислительных модулей для определения их технического состояния по сравнению с классическими моделями РМС (Preparata, Metze, Chien [307]) и В GM (Barsi, Grandoni, Maestrini [278]).

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

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

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

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

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

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

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

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

- "Автоматизация проектирования процессов в вычислительных структурах, реализованных на СБИС" (НИР 21-83);

- "Разработка методов и средств реализации навигационных задач на микропроцессорных системах и микроЭВМ" (НИР 48-83);

- "Разработка методов и средств исследования эффективности микропрограммируемых вычислительных структур" (НИР 65-83);

- "Разработка пакета прикладных программ для автоматизации проектирования специализированных процессоров в устройствах отображения графической информации" (НИР 64-84);

- "Разработка структуры САПР морской электронной геологоразведочной аппаратуры" (НИР 40-85);

- "Разработка методов и средств автоматизации управления для специализированных вычислительных структур" (НИР 27-86, шифр "Левада");

- "Разработка теории проектирования высокопроизводительных вычислительных структур, систем и сетей" (НИР 2-87г);

- "Разработка системных программных средств управления реконфигурацией вычислительной системы" (НИР 8/91);

- "Разработка и исследование модели канального процессора для вычислительных сетей" (ОКР 47-91);

- "Средства автоматизированного проектирования и аппаратно-программная реализация системы управления распределенными базами данных" (НИР 49-92г);

- "Разработка методов и алгоритмов автоматизированного проектирования систем управления распределенными базами данных" (НИР 12-93г);

- "Создание инструментальных средств автоматизированного проектирования систем управления распределенными базами данных (СУРБД) и разработка структуры СУРБД испытаний сложных технических объектов" (НИР 21-94г);

- "Исследование и анализ информационных моделей распределенных систем обработки и контроля сложных технических комплексов" (ОКР 31-94);

- "Разработка математических моделей и методов синтеза и анализа цифровых систем управления и контроля в реальном времени" (НИР 44-92г, НИР 16-93г, НИР 32-94г, НИР 18-95г);

- "Рабочая станция разработчика мобильного программного обеспечения для параллельных вычислительных систем на основе современной элементной базы" ( НИР 7-97г, НИР 7-98г).

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

- межведомственная программа фундаментальных и поисковых исследований на 1981-1985 г.г. (НИР 21-83, НИР 65-83);

- межведомственная программа фундаментальных и поисковых исследований на 1986-1990 г.г., решение ВПК № 328 от 05.10.85 и приказ Минвуза РСФСР № 136 от 02.12.85 г. (НИР 27-86, шифр "Левада");

- приказ Комитета по высшей школе Миннауки России № 473 от 22.07.92 (НИР 44-92г, НИР 16-93г, НИР 32-94г, НИР 18-95г);

- комплексная научно-техническая программа Минвуза СССР "Микропроцессоры и микроЭВМ" (НИР 65-83);

- комплексная научно-техническая программа Минвуза РСФСР "Океанотехника" (НИР 48-83, НИР 40-85);

- межвузовские научно-технические программы "Охрана интеллектуальной собственности" (НИР 42-92г) и "Интеллектуальная собственность высшей школы" (НИР 12-93г, НИР № 21-94г).

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

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

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

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

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

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

- государственное предприятие ОКБ "Спектр" при Рязанской государственной радиотехнической академии (г. Рязань) - в процессе разработки и оптимизации программного обеспечения протоколов канального уровня специализированной сети передачи данных (в рамках ОКР "Резеда"), а также при разработке программного обеспечения автоматизированной системы проведения натурных испытаний сложных технических комплексов (ОКР "Экспресс");

- ЦНИИ 4 Министерства обороны России (в/ч 25840) - при разработке и оптимизации объектного кода специализированного программного обеспечения для информационно-расчетной системы "Ярус-М" в рамках НИР "Передовик -122-9";

- НИИИ 21 Министерства обороны России - для повышения эффективности комплекса программ по моделированию процессов функционирования системы восстановления автомобильной техники путем оптимизации объектного кода ряда программ этого комплекса;

- Научно-производственный центр ОАО "Рязанский радиозавод" (г. Рязань) - в процессе разработки пакета программ по подготовке данных и управлению технологическим оборудованием;

- ЗАО "Композит" (п. Лесной, Рязанская область) - при проектировании отказоустойчивой распределенной многопроцессорной системы управления технологическим оборудованием, предназначенным для работы в условиях химически агрессивной внешней среды.

Кроме того, основные положения диссертации используются в учебном процессе Рязанской государственной радиотехнической академии (г. Рязань) для студентов специальностей 220300 "Системы автоматизированного проектирования" и 220500 "Конструирование и технология электронно-вычислительных средств" при изучении дисциплин "Лингвистическое обеспечение САПР", "Системное программирование", "Дискретная математика", "Микропроцессорные устройства и системы", "Микропроцессоры и микроЭВМ в конструировании ЭВС", что подтверждается соответствующими актами о внедрении и практическом использовании научных результатов диссертационной работы.

Апробация работы. Основные положения и результаты диссертационной работы представлены на следующих конференциях, семинарах и совещаниях: Всесоюзное совещание "Автоматизация проектирования микроэлектронной аппаратуры" (Владимир, 1983); Всесоюзная школа-семинар ЕС ЭВМ - 85 "Разработка и применение в народном хозяйстве ЕС ЭВМ" (Кишинев, 1985); Всесоюзная школа-семинар "Разработка и внедрение в народное хозяйство систем автоматизированного проектирования ЭВМ и БИС" (Ереван, 1986); IX Всесоюзный симпозиум "Логическое управление в промышленности" (Ташкент, 1986); X Всесоюзный симпозиум "Логическое управление с использованием ЭВМ" (Ижевск, 1987); Всесоюзная школа-семинар ЕС ЭВМ - 87 "Разработка и внедрение в народное хозяйство ЕС ЭВМ" (Тбилиси, 1987); III Всесоюзное совещание "Высокопроизводительные вычислительные системы" (Таллин, 1988); Региональная школа-семинар " Организационно-экономические вопросы создания вычислительных комплексов и систем" (Москва, 1989); Всесоюзная школа-семинар ЕС ЭВМ - 89 "Разработка и внедрение в народное хозяйство ЕС ЭВМ" (Киев, 1989); 2-я Всесоюзная конференция "Повышение эффективности средств обработки информации на базе математического и машинного моделирования" (Тамбов, 1991); Международный форум информатизации МФИ-92 (Москва, 1992); Международная конференция "Технологии и системы сбора, обработки и представления информации" (Рязань, 1993); Всероссийская научно-техническая конференция "Новые информационные технологии в научных исследованиях радиоэлектроники" (Рязань, 1997); 3-я Международная конференция "Теория и техника передачи, приема и обработки информации" (Туапсе, 1997); 7-й Международный научно-технический семинар "Проблемы передачи и обработки информации в информационно-вычислительных сетях" (Рязань, 1997); 2-й Всероссийской научно-практической конференции "Современные информационные технологии в образовании" (Рязань, 1998); Всероссийская научно-техническая конференция "Новые информационные технологии в радиоэлектронике" (Рязань, 1998); Международная конференция "Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем" (Пенза, 1998); 2-я Московская Международная телекоммуникационная конференция "Молодежь и наука" в научной сессии МИФИ (Москва, 1999); 4-я Всероссийская научно-техническая конференция "Новые информационные технологии в научных исследованиях и в образовании" (Рязань, 1999); 8-й Международный научно-технический семинар "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций" (Рязань, 1999); конференции профессорско-преподавательского состава Рязанской государственной радиотехнической академии (Рязань, 1986, 1988, 1996 - 1999).

24

Публикации. Результаты диссертационной работы нашли отражение в 82 опубликованных научных работах, среди которых 1 монография, 2 учебных пособия, 20 статей в научно-технических журналах, 5 свидетельств об официальной регистрации программ для ЭВМ в РосАПО и РОСПАТЕНТ.

Структура и объем диссертации. Диссертационная работа состоит из введения, 6 разделов, заключения, списка литературы (318 наименований), изложенных на 425 страницах, и содержит 28 таблиц и 76 рисунков. Приложения на 43 страницах дополнительно включают 11 таблиц и 3 рисунка. Общий объем диссертации 468 страниц.

6. Основные результаты диссертационной работы использованы при проведении 19 НИР и ОКР, выполненных в 1983-1999 годах в Рязанской государственной радиотехнической академии при непосредственном участии автора диссертации в качестве исполнителя, ответственного исполнителя и заместителя научного руководителя, и внедрены в разработках ряда организаций и предприятий:

- в виде формальных моделей, методов и алгоритмов локальной и глобальной оптимизации параллельного объектного кода, включая решение задачи автоматического распределения регистровой памяти, применение которых существенно повышает эффективность машинных программ с точки зрения сокращения времени исполнения (до 20%) и уменьшение их объема (до 14%) по сравнению с результатами генерации объектного кода без использования предложенных средств оптимизации скалярных вычислений на микроуровне параллелизма (НИИ "Аргон", г.

Москва, ЦНИИ 4 и НИИИ 21 Минобороны России, ГП ОКБ "Спектр" при Рязанской государственной радиотехнической академии, Научно-производственный центр ОАО "Рязанский радиозавод", г. Рязань);

- в виде инструментальных программных средств генерации и оптимизации параллельного объектного кода, созданных на базе предложенных в диссертационной работе методов организации параллельных процессов на микроуровне вычислений и обеспечивающих сокращение сроков разработки машинных программ для конкретных моделей вычислительных систем примерно в 2-3 раза при повышении их эффективности в указанных выше пределах (НИИ "Аргон", г. Москва, ЦНИИ 4 и НИИИ 21 Минобороны России, ГП ОКБ "Спектр" при Рязанской государственной радиотехнической академии);

- в виде алгоритмов и системных программных средств организации вычислительных процессов на макроуровне параллелизма в отказоустойчивых многопроцессорных системах, применение которых обеспечивает работоспособность системных программ диагностирования отказов вычислительных модулей в режиме реального времени при существенном сокращении длительности цикла контроля (общее число взаимных проверок модулей уменьшается на 30-40%) за счет обоснованного выбора модели дешифрации синдрома системы и синтеза оптимальных диагностических графовых моделей системы (НИИ "Аргон", г. Москва, ЗАО "Композит", Рязанская область);

- в виде монографии, 2 учебных пособий, методических и научных изданий, а также разделов лекционных курсов, изучаемых студентами специальностей 220300 "Системы автоматизированного проектирования" и 220500 "Конструирование и технология электронных вычислительных средств" (Рязанская государственная радиотехническая академия).

Копии актов о внедрении научных результатов диссертации приведены в приложении 8.

Основные положения диссертационной работы опубликованы в отчетах о НИР [3, 174-179] и работах автора [28-36, 51-54, 62, 77, 97, 104-119, 142, 143, 183, 187-191, 195-238-, 270].

1. Аваков В. Микропроцессор MIPS R10000 // Открытые системы. 1995. № 6. С. 62-69.

2. Авижиенис A.A. Отказоустойчивость свойство, обеспечивающее постоянную работоспособность цифровых систем // ТИИЭР. 1978. Т. 66. № 10. С. 5-25.

3. Автоматизация проектирования процессов в вычислительных структурах, реализуемых на СБИС: Отчет о НИР / Рязан. радиотехн. ин-т; Руководитель В.П.Корячко. № гос. per. 01830041129; инв. № 0284.0 062068. Рязань, 1984. 99 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. 319 с.

5. Алагич С., Арбиб М. Проектирование корректных структурированных программ. М.: Радио и связь, 1984. 264 с.

6. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем // Под ред. А.П.Ершова. М.: Наука, 1982. 336 с.

7. Аллен Р., Кеннеди К. Автоматическая трансляция Фортран-программ в векторную форму // Векторизация программ: теория, методы, реализация. Сб. статей. М.: Мир, 1991. С. 77-140.

8. Арапов Д. Можно ли превратить сеть в суперкомпьютер? // Открытые системы. 1997. № 4. С. 6-10.

9. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. М.: Радио и связь, 1991. 248 с.

10. Атстопас Ф.Ф., Плукас К.И. Метод минимизации микропрограмм ЭЦВМ // Автоматика и вычислительная техника. 1971. № 4. С. 10-16.

11. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ. М.: Мир, 1978. 616 с.

12. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 2. Компиляция. М.: Мир, 1978. 448 с.

13. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ алгоритмов для ЭВМ. М.: Мир, 1979. 536 с.

14. А. с. 1679505 СССР, МКИ G 06 F 15/46. Способ контроля правильности функционирования дискретных устройств / М.А.Терещенко, И.Б.Шубинский, В.И.Николаев, Ф.С.Власов, А.М.Заяц. № 4641959/00-24; Заявлено 25.01.89; Опубл. 23.09.91, Бюл. № 35.

15. Баранов С.И., Баркалов A.A. Микропрограммирование: принципы, методы, применения // Зарубежная радиоэлектроника. 1984. № 5. С. 3-29.

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

17. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. 256 с.

18. Бахаревский А.Д., Игнатущенко В.В. Новый подход к организации опережающей выборки данных для однопроцессорных и параллельных компьютеров: формальные модели и доказательства // Автоматика и телемеханика. 1995. № 8. С. 158-181.

19. Бек JI. Введение в системное программирование. М.: Мир, 1988.448 с.

20. Бердышев Е.М. Технология ММХ. Новые возможности процессоров Р5 и Р6. М.: ДИАЛОГ-МИФИ, 1998. 234 с.

21. Борзенко А.Е., Корячко В.П. Синтез оптимальной структуры операционной части микропроцессорного модуля // Микропроцессорные устройства и автоматизация проектирования: Межвуз. сб. / Рязан. радиотехн. ин-т. Рязань, 1986. С. 5-10.

22. Бортовые ЦВМ с архитектурой ПОИСК для истребительной авиации / А.А.Соловьев, В.Н.Геништа, Б.Ю. Курбатов и др. // Проблемы информатизации. 1998. Вып. 3-4. С. 15-27.

23. Брамм П., Брамм Д. Микропроцессор 80386 и его программирование. М.: Мир, 1990. 448 с.

24. Бройтман Д. Микропроцессор PowerPC 601 // Монитор. № 4. 1994. С. 56-61.

25. Бруно Бабэ. Просто и ясно о Borland С++: Пер. с англ. М.: БИНОМ. 400 с.

26. Буслов A.B., Скворцов C.B. Программные средства экспериментальной оценки диагностических моделей отказоустойчивых систем // Новые информационные технологии: Межвуз. сб. / Рязан. гос. радио-техн. акад. Рязань, 1998. С. 23-31.

27. Буслов A.B., Скворцов C.B. Метод обнаружения неисправных модулей в отказоустойчивых системах // Новые информационные технологии в радиоэлектронике: Тез. докл. Всероссийской научно-технич. конф. Рязань, май 1998. Рязань: РГРТА, 1998. С. 41-42.

28. Буслов A.B., Скворцов C.B. Аналитический метод дешифрации результатов диагностирования многопроцессорных систем // Вычислительные машины, комплексы и сети: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1999. С. 64-68.

29. Вайнгартен Ф. Трансляция языков программирования. М.: Мир, 1977. 190 с.

30. Вайрадян A.C., Коровин A.B., Удалов В.Н. Эффективное функционирование управляющих мультипроцессорных систем. М.: Радио и связь, 1984. 328 с.

31. Валях Е. Последовательно-параллельные вычисления. М.: Мир, 1985. 456 с.

32. Василюк В.Р., Шувиков В.И., Юсим Г.В. Распределение общих ресурсов микропрограммируемой вычислительной системы // Проектирование вычислительных машин и систем: Межвуз. сб. / Рязан. радио-техн. ин-т. Рязань, 1984. С. 87-92.

33. Ведешенков В.А. Об организации самодиагностируемых цифровых систем // Автоматика и телемеханика. 1983. № 7. С. 133-144.

34. Ведешенков В.А., Нестеров A.M. О двух методах дешифрации результатов диагностирования цифровых систем // Электронное моделирование. 1981. № 2. С. 53-58.

35. Векторизация программ: теория, методы, реализация. Сб. статей / Под ред. Г.Д.Чинина. М.: Мир, 1991. 275 с.

36. Власов Ф.С., Гершанов В.И., Черников О. И. Решение задачи унификации при создании МВС "Циклоп" // Тез. докл. Всесоюзного совещания "Проблемы построения перспективных бортовых управляющих вычислительных комплексов". Владивосток, 1991. С. 7.

37. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.

38. Воеводин Вл.В. Теория и практика исследования параллелизма последовательных программ // Программирование, 1992. № 3. С. 38-53.

39. Гаскаров Д.В., Истомин Е.П., Кутузов О.И. Автоматизированные системы управления распределенными сетями. Спб.: Энергоатомиз-дат. Санкт-Петербургское отд-ние, 1998. 351 с.

40. Гершанов В.И., Корячко В.П. Оптимизация загрузки СОЗУ промежуточными результатами // Вопросы радиоэлектроники. Серия Электрон, вычисл. техн. 1986. Вып. 7. С. 27-33.

41. Гершанов В.И., Скворцов C.B. Синтез микропрограмм и оценка качества структуры микропроцессорных систем управления процессами реального времени // Вопросы радиоэлектроники. Серия Электрон, вычисл. техн. 1987. Вып. 7. С. 90-97.

42. Гершанов В.И., Скворцов C.B. Рациональное использование управляющей памяти при параллельном микропрограммировании // Вопросы радиоэлетроники. Серия Электрон, вычисл. техн. 1990. Вып. 7. С. 44-51.

43. Гершанов В.И., Скворцов C.B., Телков И.А. Синтез параллельных форм алгоритмов функционирования специализированных вычислительных систем // Вопросы специальной радиоэлектроники. Серия Электрон, вычисл. техн. 1989. Вып. 1. С. 37-46.

44. Гершанов В.И., Скворцов C.B., Телков И.А. Методы повышения отказоустойчивости вычислительных систем, основанных на принципе ассоциативной селекции потоков данных // Вопросы радиоэлектроники. Серия Электрон, вычисл. техн. 1992. Вып. 7. С. 50-58.

45. Глушков В.М., Молчанов И.Н. О некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений // Кибернетика. 1981. № 1. С.82-88.

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

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

48. Головкин Б.А. Вычислительные системы с болыцим числом процессоров. М.: Радио и связь, 1995. 320 с.

49. Горбатов В.А. Основы дискретной математики. М.: Высшая школа, 1986. 311 с.

50. Горелов О.И., Плотников Е.В. Представление открытых вычислительных сетей моделью самодиагностируемой системы с распределенным диагностическим ядром // Автоматика и вычислительная техника. 1983. № 4. С. 64-70.

51. Горелов О.И., Плотников Е.В. Об одном методе анализа вычислительных сетей // Автоматика и вычислительная техника. 1986. № 1. С. 30-35.

52. Григорьев B.JI. Программирование однокристальных микропроцессоров. М.: Энергоатомиздат, 1987. 287 с.

53. Грис Д. Конструирование компиляторов дж цифровых вычислительных машин. М.: Мир, 1975. 544 с.

54. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. 368 с.

55. Гуткин M. Intel и новая технология ММХ // PC Week. Russian Edition. 1996. № 14. С. 47-50.

56. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975. 248 с.

57. Данциг Д.Б., Гофман А.Дж. Теорема Дилворта о частично-упорядоченных множествах // Линейные неравенства и смежные вопросы. М.: Изд-во иностранной литературы, 1959. С. 311-317.

58. Димитриев Ю.К., Хорошевский В.Г. Вычислительные системы из миниЭВМ / Под ред. Э.В. Евреинова. М.: Радио и связь, 1982. 304 с.

59. Дубова Н. РА 7200 новый процессор семейства HP РА-RI S С // Открытые системы. 1995. № 1. С. 62-66.

60. Евсиков М. Новое семейство процессоров Analog Devices // КомпьютерПресс. 1996. № 8. С. 64-67.

61. Евстигнеев В.А. Применение теории графов в программирова-ниии. М.: Наука, 1985. 352 с.

62. Евстигнеев В.А. Некоторые особенности программного обеспечения ЭВМ с длинным командным словом // Программирование. 1991. № 2. С. 69-80.

63. Евстигнеев В.А., Касьянов В.Н. Оптимизирующие преобразования в распараллеливающих компиляторах // Программирование. 1996. № 6. С. 12-26.

64. Ершов А.П. Математическое обеспечение четвертого поколения // Кибернетика. 1973. № 1. С. 9-21.

65. Жинтелис Г.Б., Карчяускас Э.К., Мачикенас Э.К. Автоматизация проектирования микропрограммируемых структур. Л.: Машиностроение, 1985. 216 с.

66. Золотовский В.Е. Микропроцессорные вычислительные структуры для решения уравнений в частных производных // Автоматика и вычислительная техника. 1984. № 3. С. 62-68.

67. Игнатущенко В.В. Организация структур управляющих многопроцессорных вычислительных систем. М.: Энергоатомиздат, 1984. 184 с.

68. Игнатущенко В.В., Скугарев В.В. Новая технология групповой выборки данных для однопроцессорных и параллельных ЭВМ: характерные особенности и возможности // Автоматика и телемеханика. 1993. № 3. С. 165-177.

69. Игнатущенко В.В. Новая организация опережающей выборки данных для конвейерных однопроцессорных и параллельных компьютеров // Автоматика и телемеханика. 1997. № 8. С. 196-209.

70. Игнатущенко В.В., Подшивалова И.Ю. Динамическое управление параллельными вычислительными процессами на основе статического прогнозирования их выполнения // Автоматика и телемеханика. 1997. № 5. С. 160-173.

71. Игнатущенко В.В., Подшивалова И.Ю. Динамическое управление надежным выполнением параллельных вычислительных процессов для систем реального времени // Автоматика и телемеханика. 1999. № 6. С. 142-157.

72. Иыуду К.А. Надежность, контроль и диагностика вычислительных машин и систем. М.: Высшая школа, 1989. 216 с.

73. Иыуду К.А., Кривощеков С.А. Математические модели отказоустойчивых вычислительных систем. М.: Изд-во МАИ, 1989. 144 с.

74. Каширин И.Ю. Унификация на множестве термов формальной структуры программ // Вестник Рязанской государственной радиотехнической академии. 1997. Вып. 2. С. 53-60.

75. Каширин И.Ю., Коричнев Л.П. Формальное исследование интеллектуальных программных систем. М.: Радио и связь, 1997. 160 с.

76. Квиттнер П. Задачи, программы, вычисления, результаты. М.: Мир, 1980. 424 с.

77. Клембо B.C. Автоматизированное проектирование микропрограмм // Электронная техника. Сер. 11. 1976. Вып. 3. С. 77-83.

78. Клингман Э. Проектирование специализированных микропроцессорных систем. М.: Мир, 1985. 363 с.

79. Кожевникова Г.П., Синицкий А.Л. О задаче перестройки деревьев в алгоритмах микрораспараллеливания // Кибернетика. 1983. № 5. С. 14-21.

80. Комплект БИС К1804 в процессорах и контроллерах / В.М.Мещеряков, И.Е. Лобов, С.С.Глебов и др.; Под ред. В.Б.Смолова. М.: Радио и связь, 1990. 255 с.

81. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975. 360 с.

82. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368 с.

83. Корнеев В.В., Киселев A.B. Современные микропроцесоры. М.: НОЛИДЖ, 1998. 240 с.

84. Коршунов Ю.М. Математические основы кибернетики. М.: Энергоатомиздат, 1987. 469 с.

85. Корячко В.П. Конструирование микропроцессорных систем контроля радиоэлектронной аппаратуры. М.: Радио и связь, 1987.160 с.

86. Корячко В.П. Микропроцессоры и микроЭВМ в радиоэлектронных средствах. М.: Высшая школа, 1990. 407 с.

87. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. М.: Энергоатомиздат, 1987. 386 с.

88. Корячко В.П., Курчидис В.А. Оптимизация организации внутренней памяти цифровой управляющей машины // Управляющие системы и машины 1975. № 3. С. 87-91.

89. Корячко В.П., Курчидис В.А. Об укладке графов программ // Изв. АН СССР. Техническая кибернетика. 1979. № 6. С. 129 136.

90. Корячко В.П., Скворцов C.B. Планирование загрузки регистровой памяти при микропрограммировании микропроцессорных систем // Автоматика и вычислительная техника. 1987. № 4. С. 75-80.

91. Корячко В.П., Скворцов C.B. Оптимизация загрузки регистров общего назначения в управляющих микропроцессорных системах //

92. Логическое управление с использованием ЭВМ: Тез. докл. X Всесоюзн. симпозиума. Ижевск, 1987. М.: Научный совет АН СССР по комплексной проблеме "Кибернетика", 1987. С. 98-100.

93. Корячко В.П., Скворцов C.B. Иерархическая модель глобальной оптимизации параллельных объектных программ // Информационные технологии. 1998. № 9. С. 34-40.

94. Корячко В.П., Скворцов C.B., Телков И.А. Построение микропрограмм с циклами и ветвлениями для специализированных микропроцессорных систем//Электронное моделирование. 1988. № 1. С. 17-22.

95. Корячко В.П., Скворцов C.B., Телков И.А. Модель планирования параллельных процессов в суперскалярных процессорах // Информационные технологии. 1997. № 1. С. 8-12.

96. Корячко В.П., Скворцов C.B., Телков И.А. Математическая модель мобильных вычислений // Информационные технологии. 1998. № 11. С. 27-32.

97. Корячко В.П., Скворцов C.B., Телков И.А. Архитектуры многопроцессорных систем и параллельные вычисления. М.: Высшая школа, 1999. 235 с.

98. Корячко В.П., Скворцов C.B., Шувиков В.И. Формирование микропрограммных управляющих слов для микропроцессорных систем // Электронное моделирование. 1987. № 6. С. 19-22.

99. Корячко В.П., Скворцов C.B., Шувиков В.И. Характеризация диагностических графов для симметричной модели дешифрации синдрома // Информационные технологии. 1999. № 6. С. 18-22

100. Корячко В.П., Скворцов C.B., Шувиков В.И. Синтез оптимальных диагностических графов для симметричной модели дешифрации синдрома // Информационные технологии. 1999. № 12. С. 32-37.

101. Корячко В.П., Скворцов C.B., Шувиков C.B. Генерация машинно-независимого кода для параллельного вычисления арифметических выражений // Информационные технологии. 1999. № 3. С. 2-7.

102. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. 480 с.

103. Кофман А., Дебазей Г. Сетевые методы планирования. М.: Прогресс, 1968. 182 с.

104. Кравцов Л.Я., Черницкий Г.И. Проектирование микропрограммных устройств управления. Д.: Энергия, 1976. 152 с.

105. Крамаренко М.Б. Модели диагностирования отказов параллельной вычислительной системы // Электронное моделирование. 1989. № 3. С. 60-65.

106. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

107. Кручинин С. RISC-архитектура: общие принципы и перспективы развития // ComputerWeek-Moscow. 1995. № 32, 33.

108. Кручинин С. Процессоры//Hard and Soft. 1995. № 11. С. 41-49.

109. Кузьминский М. Микропроцессор PA-RISC 8000 // Открытые системы. 1995. № 5. С. 15-18.

110. Кузьминский М. Микроархитектура DEC Alpha 21264 // Открытые системы. 1998. № 1. С. 7-11.

111. Кузюрин H.H., Фрумкин М.А. Параллельные вычисления: теория и алгоритмы (обзор) // Программирование, 1991. № 2. С. 6-19.

112. Кузюрин H.H., Фрумкин М.А. Параллельные вычисления: теория и алгоритмы // Итоги науки и техники. Серия Вычислительные науки, т. 8. М.: ВИНИТИ АН СССР, 1991. С. 1-211.

113. Лазарев В.Г., Пийль Е.И., Турута E.H. Построение программируемых управляющих устройств. М.: Энергоатомиздат, 1984. 192 с.

114. Лингер Р., Миллс X., Уитт Б. Теория и практика структурного программирования. М.: Мир, 1982. 406 с.

115. Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика, 1979. 248 с.

116. Липкин И. RISC-поворот или сосуществование двух направлений // КомпьютерПресс. 1990. № 5. С. 70-75.

117. Липкин И. Еще раз о RISC // КомпьютерПресс. 1991. № 6. С. 43-47. № 7. С. 15-19.

118. Липский В. Комбинаторика для программистов. М.: Мир, 1988. 213 с.

119. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1979. 654 с.

120. Микеладзе М.А. Развитие основных моделей самодиагностирования сложных технических систем // Автоматика и телемеханика. 1995. № 5. С. 3-18.

121. Микропроцессоры PowerPC 603, 604, 620 // Монитор. № 4. 1995. С. 6-9.

122. Микропроцессорные комплекты БИС на основе интегральной инжекционной логики / В.С.Борисов, Ф.С.Власов, Э.П.Калошкин и др.; Под ред. Э.П. Калошкина. М.: Радио и связь, 1984. 248 с.

123. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989. 320 с.

124. Многопроцессорные ЭВМ и методы их проектирования / Б.А.Бабаян, А.В.Бочаров, В.С.Волин и др. М.: Высшая школа, 1990.143 с.

125. Мозгалевский A.B., Гаскаров Д.В. Техническая диагностика. М.: Высшая школа, 1974. 207 с.

126. МП-3?.i860?.Неизвестные?! Незнакомые! / А.Лякишев, Е.Монахова, В.Новичихин, С.Степаненко // PC Week. Russian Edition. 1996. № 1,2

127. Мы впереди ! // Мир связи, 1998. № 12 1999. № 1. С. 9.

128. Мюллер Д.Е., Препарата Ф.П. Перестроение арифметических выражений для параллельного вычисления // Кибернетический сборник. Новая серия. Вып. 16. М.: Мир, 1979. С. 5-22.

129. Набор команд процессоров Alpha пополняется новыми мультимедиа-инструкциями // ComputerWeek-Moscow. 1996. № 30.

130. Назаров Л.Н. Многопроцессорные вычислительные комплексы "Эльбрус" // Проблемы информатизации. 1997. Вып. 1-2. С. 33-37.

131. Настраиваемый инструментальный комплекс для разработки систем на секционированных микропроцессорах / О.И. Семенков. Л.А.Гриншпан, Е.М.Злотник и др. // Управляющие системы и машины. 1984. № 2. С. 36-39.

132. Ope О. Теория графов. М.: Наука, 1980. 336 с.

133. Основы технической диагностики. В 2-х книгах. Кн. 1. Модели объектов, методы и алгоритмы диагноза / Под ред. П.П.Пархоменко. М.: Энергия, 1976. 464 с.

134. Падуа Д., Вольф М. Оптимизация в компиляторах для суперкомпьютеров // Векторизация программ: теория, методы, реализация. Сб. статей. М.: Мир, 1991. С. 7-47.

135. Палагин A.B., Денисенко E.JL, Юсифов С.И. О формализации проектирования микропроцессоров с несколькими операционными блоками: Препринт / АН УССР, Ин-т кибернетики им. В.М.Глушкова; 85-32. Киев, 1985. 19 с.

136. Палагин A.B., Слободянюк Т.Ф., Юсифов С.И. Проектирование мультиоперационных микропроцессоров на базе набора БИС со "слайсовой" структурой // Кибернетика. 1987. № 5. С. 73-78.

137. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 512 с.

138. Параллельные вычисления / Под ред. Г.Родрига. М.: Наука, 1986. 376 с.

139. Параллельная обработка информации: В 5 томах. Том 1. Распараллеливание алгоритмов обработки информации / A.B. Бабичев, В.А.Вальковский, В.В.Грицык и др.; Под ред. А.Н.Свенсона. Киев: Наук, думка, 1985. 280 с.

140. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. М.: Энергия, 1981. 320 с.

141. Перминов О.Н. Программирование на языке Паскаль. М.: Радио и связь, 1988. 224 с.

142. Петрова Ю. RISC-процессоры третьего поколения // ComputerWeek-Moscow. 1995. № 22, 23.

143. Плотников Е.В. Метод функционального диагностирования вычислительных сетей на макроуровне // Электронное моделирование. 1986. № 3. С. 41-44.

144. Погребной В.К. Об автоматизации распределения памяти на графовых моделях алгоритмов // Управляющие системы и машины. 1980. № 5. С. 37-42.

145. Подсистема автоматизированного проектирования микропрограмм / В.Н.Голубкин, В.В.Тимофеев, Э.Т.Емелеев, И.М.Якимов // Вопросы радиоэлектроники. Серия Электрон, вычисл. техн. 1982. Вып. 7. С. 49-54.

146. Подсистема автоматизированного проектирования микропрограмм АВТПРОМ / Л.В.Арсентьева, Г.В.Поляков, Д.А.Скиндер, Ю.А.Татарников // Обмен производственно-техническим опытом. 1986. № 9. С. 34-37.

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

148. Применение булевых матриц в решении задач контроля технического состояния дискретных устройств и систем / Н.Н.Новиков, В.Н.Козлов, Н.М.Емелин, Ю.В.Астапенко // Надежность и контроль качества. 1998. № 3. С. 33-41.

149. Проектирование цифровых систем на комплектах микропро-граммируемых БИС / С.С.Булгаков, В.М.Мещеряков, В.В.Новоселов, Л.А.Шумилов; Под ред. В.Г. Колесникова. М.: Радио и связь, 1984.240 с.

150. Программирование на параллельных вычислительных системах / Р.Бэбб, Дж.Мак-Гроу, Т.Акселрод и др.; Под ред. Р.Бэбба И. М.: Мир, 1991. 376 с.

151. Процессоры ТпМесНа с архитектурой У1Л\¥ // СотрШ:ег\¥еек-Моэсоху. 1996. № 25.

152. Радойчевски В.Ц., Шалаев А.Я. Параллельная диагностируе-мость модульных систем при централизованной дешифрации синдрома // Электронное моделирование. 1992. № 1. С. 57-63.

153. Разработка и отладка микропрограммного обеспечения цифровых систем на основе секционированных микропроцессоров / А.Г.Алексенко, А.Г.Гапоненко, А.Д.Иванников, И.Д.Курилов // Микропроцессорные средства и системы. 1986. № 1. С. 37-43.

154. Разработка методов и средств автоматизации управления для специализированных вычислительных структур: Отчет о НИР / Рязан. радиотехн. ин-т; Руководитель В.П.Корячко. № гос. per. 01860119417; инв. № 0287.0 066576. Рязань, 1987. 118 с.

155. Разработка методов и средств автоматизации управления для специализированных вычислительных структур: Отчет о НИР / Рязан. радиотехн. ин-т; Руководитель В.П.Корячко. № гос. per. 01860119417; инв. № 0288.0 078232. Рязань, 1988. 142 с.

156. Разработка методов и средств исследования эффективности микропрограммируемых вычислительных структур: Отчет о НИР / Рязан. радиотехн. ин-т; Руководитель В.П.Корячко. № гос. per. 01840040820; инв. № 0286.0 052805. Рязань, 1985. 201 с.

157. Разработка методов и средств реализации навигационных задач на микропроцессорных системах и микроЭВМ: Отчет о НИР / Рязан. радиотехн. ин-т; Руководитель В.П.Корячко. № гос. per. 01830066876; инв. № 0287.0 063880. Рязань, 1985. 158 с.

158. Разработка структуры САПР морской электронной геологоразведочной аппаратуры: Отчет о НИР / Рязан. радиотехн. ин-т; Руководитель В.П.Корячко. № гос. per. 01860004815; инв. № 0287.0 034003. Рязань, 1987. 258 с.

159. Реджеевски P.P. Об арифметических выражениях и деревьях // Кибернетический сборник. Новая серия. Вып. 7. М.: Мир, 1970. С. 99-107.

160. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

161. Рейуорд-Смит Д.Дж. Теория формальных языков. Вводный курс. М.: Радио и связь, 1988. 128 с.

162. Ручкин В.H., Скворцов C.B., Телков И.А. Анализ и оптимизация структуры автоматизированной системы обработки телеметрической информации / Рязан. радиотехн. ин-т. Рязань, 1982. 17 с. Деп. в ЦНИИТЭИ Приборостроения, № 1766пр-Д82.

163. Рыбаков А. Процессоры семейства PowerPC // КомпьютерПресс. 1996. № 2. С. 86-93.

164. Рыжков А.П. Правильная билотическая граф-модель параллельного вычислительного процесса и ее свойства // Известия АН СССР. Техническая кибернетика. 1976. № 2. С. 96-104.

165. Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высшая шкода, 1987. 272 с.

166. Свидетельство об официальной регистрации программы для ЭВМ № 940304, Россия. Программа анализа потоков команд (АНАЛИЗ) / С.В.Скворцов, И.А.Телков. Зарегистрировано в РосАПО 25.07.94, заявка № 940216.

167. Свидетельство об официальной регистрации программы для ЭВМ № 980507, Россия. Программа анализа и выбора диагностических моделей модульных систем / А.В.Буслов, С.В.Скворцов. Зарегистрировано в РосАПО 20.08.98, заявка № 980376.

168. Свидетельство об официальной регистрации программы для ЭВМ № 980385, Россия. Программа генерации графовых моделей (ГенГраф) / С.В.Скворцов, С.В.Шувиков. Зарегистрировано в РосАПО2306.98, заявка № 980253.

169. Свидетельство об официальной регистрации программы для ЭВМ № 990663, Россия. Учебно-исследовательский кросс-транслятор, ориентированный на генерацию параллельного объектного кода /

170. M.Е.Горюнов, С. В. Скворцов, С.В.Шувиков. Зарегистрировано в РОСПАТЕНТ 13.09.99, заявка № 990545.

171. Сир Ж.К. Метод потока операндов в многопроцессорных системах типа MIMD // Системы параллельной обработки / Под ред. Д.Ивенса. М.: Мир, 1985. С. 240-276.

172. Системы команд процессоров пополняются мультимедиа-инструкциями // ComputerWeek-Moscow. 1996. № 32.

173. Системы параллельной обработки / Под ред. Д.Ивенса. М.: Мир, 1985. 416 с.

174. Скворцов C.B. Распределение ресурсов специализированной вычислительной системы при автоматизированном проектировании микропрограмм / Рязан. радиотехн. ин-т. Рязань, 1985. 11 с. Деп. в ЦНИИТЭИ Приборостроения 30.05.85, № 2895пр-85.

175. Скворцов C.B. Построение оптимальной последовательности управляющих микрокоманд для специализированных микропроцессорных систем / Рязан. радиотехн. ин-т. Рязань, 1986. 15 с. Деп. в ЦНИИТЭИ Приборостроения 24.10.86, № 3536-пр.

176. Скворцов C.B. Применение списочных расписаний при микропрограммировании микропроцессорных систем // Микропроцессорные устройства и автоматизация проектирования: Межвуз. сб. / Рязан. радиотехн. ин-т. Рязань, 1986. С. 41-45.

177. Скворцов C.B. Автоматизированное проектирование символических микропрограмм для специализированных микропроцессорных систем // Проектирование вычислительных машин и систем: Межвуз. сб. / Рязан. радиотехн. ин-т. Рязань, 1987. С. 51-54.

178. Скворцов C.B. Планирование загрузки управляющей памяти при микропрограммировании микропроцессорных систем // Автоматизация проектирования и микроминиатюризация ЭВМ: Межвуз. сб. / Рязан. радиотехн. ин-т. Рязань, 1988. С. 37-42.

179. Скворцов C.B. Исследование алгоритмов составления расписаний для многопроцессорных систем с использованием смешанных графов / Рязан. радиотехн. ин-т. Рязань, 1989. 17 с. Деп. в Информприбор 20.03.89, № 4556-пр89.

180. Скворцов C.B. Средства синтеза микропрограмм для маги-стрально-модульных микропроцессорных систем // Автоматика и вычислительная техника. 1990. № 2. С. 88-93.

181. Скворцов C.B. Итерационный метод синтеза микропрограмм с заданными характеристиками // Автоматизация проектирования микроэлектронных вычислительных средств: Межвуз. сб. / Рязан. радиотехн. ин-т. Рязань, 1990. С. 35-39.

182. Скворцов C.B. Лингвистическое обеспечение САПР: Методические указания к лабораторным работам / Рязан. радиотехн. ин-т. Рязань, 1990. 40 с.

183. Скворцов C.B. Проектирование языков САПР: Учебное пособие / Рязан. радиотехн. ин-т. Рязань, 1991. 64 с.

184. Скворцов C.B. Организация отказоустойчивых вычислений в магистрально-модульных многопроцессорных системах // Вестник Рязанской государственной радиотехнической академии. 1996. Вып. 1. С. 27-32.

185. Скворцов C.B. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов // Программирование. 1996. № 2. С. 41-52.

186. Скворцов C.B. Модель организации параллельных вычислений в суперскалярных процессорах // Вычислительные машины, комплексы и сети: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1996. С. 41-52.

187. Скворцов C.B. Применение метода ветвей и границ к задаче оптимизации кода для суперскалярных процессоров // Вестник Рязанской государственной радиотехнической академии. 1997. Вып. 2. С. 65-70.

188. Скворцов C.B. Целочисленные модели оптимизации кода по критерию времени // Информационные технологии. 1997. № 10. С. 2-7.

189. Скворцов C.B. Распараллеливание кода с циклами и ветвлениями на основе дизъюнктивных графов // Новые информационные технологии: Межвуз. сб./Рязан. гос. радиотехн. акад. Рязань, 1997. С. 48-55.

190. Скворцов C.B. Синтез параллельных объектных программ с неоднозначно заданными операциями / Рязан. гос. радиотехн. акад. Рязань, 1997. 27 с. Деп. в ВИМИ 16.01.98, № ДО-8728.

191. Скворцов C.B. Применение симметричной диагностической модели при организации активной отказоустойчивости многопроцессорных систем // Вестник Рязанской государственной радиотехнической академии. 1998. Вып. 4. С. 57-64.

192. Скворцов C.B. Оптимизация скалярных вычислений в параллельных процессах: необходимость и современные средства / Рязан. гос. радиотехн. акад. Рязань, 1998. 20 с. Деп. в ВИМИ 20.03.98, № ДО-8717.

193. Скворцов C.B. Глобальная оптимизация параллельных объектных программ / Рязан. гос. радиотехн. акад. Рязань, 1998. 30 с. Деп. в ВИМИ 16.04.98, № ДО-8729.

194. Скворцов C.B. Оптимизация распределения регистров в процессорах с суперскалярной архитектурой / Рязан. гос. радиотехн. акад. Рязань, 1998. 30 с. Деп. в ВИМИ 21.09.98, № ДО-8741.

195. Скворцов C.B. Анализ логической структуры программы в процессе синтеза параллельного объектного кода // Новые информационные технологии: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань,1998. С. 75-82.

196. Скворцов C.B. Решение задачи характеризации для одной симметричной диагностической модели // Вестник Рязанской государственной радиотехнической академии. 1999. Вып. 5. С. 23-26.

197. Скворцов C.B. Модель размещения временных данных в регистровых файлах суперскалярного процессора // Вычислительные машины, комплексы и сети: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань,1999. С. 85-89.

198. Скворцов C.B., Новиков М.А. Расширение описания графа микропрограммы // Конструирование специализированной электронно-вычислительной аппаратуры: Межвуз. сб. / Рязан. радиотехн. ин-т. Рязань, 1984. С. 110-114.

199. Скворцов C.B., Скворцов Н.В. Реализация отказоустойчивых вычислений в магистрально-модульной многопроцессорной системе // Проблемы автоматизированного проектирования: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1996. С. 52-58.

200. Скворцов C.B., Скворцов Н.В. Выбор диагностических моделей для организации активной отказоустойчивости многопроцессорных систем // Новые информационные технологии: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1997. С. 55-61.

201. Скворцов C.B., Скворцов Н.В. Синтез диагностических графов с экстремальными характеристиками // Новые информационные технологии: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1997. С. 118-123.

202. Скворцов C.B., Телков И.А. Языки моделирования в САПР вычислительных систем: Учебное пособие / Рязан. радиотехн. ин-т. Рязань, 1992. 48 с.

203. Скворцов C.B., Телков И.А. Оценка временных характеристик потоков команд для организации параллельных вычислений // Проблемы обработки информации: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1995. С. 56-61.

204. Скворцов C.B., Хрюкин В.И. Экстремальные пути на графах: Методические указания к практическим занятиям / Рязан. гос. радиотехн. акад. Рязань, 1995. 32 с.

205. Скворцов C.B., Хрюкин В.И. Эмулятор микропроцессорного тренажера МТ1804: Методические указания к лабораторным работам / Рязан. гос. радиотехн. акад. Рязань, 1995. 32 с.

206. Скворцов C.B., Шувиков В.И. Формализованный синтез микропрограмм // Микроминиатюризация радиоэлектронных устройств: Межвуз. сб. / Рязан. радиотехн. ин-т. Рязань, 1983. С. 17-21.

207. Скворцов C.B., Шувиков В.И. Формализованный синтез микрокоманд // Автоматизация проектирования микроэлектронной аппаратуры: Тез. докл. Всесоюзного совещания. Владимир, ноябрь 1983. М., 1983. Ч. 1. С. 32-33.

208. Скворцов C.B., Шувиков C.B. Синтаксический разбор выражений для параллельного вычисления // Новые информационные технологии: Межвуз. сб./Рязан. гос. радиотехн. акад. Рязань, 1998. С. 69-74.

209. Скворцов C.B. Шувиков C.B. Разбор выражений для VLIW-процессоров // Новые информационные технологии в радиоэлектронике: Тез. докл. Всероссийской научно-технич. конф. Рязань, май 1998. Рязань: РГРТА, 1998. С. 54-57.

210. Скэнлон JI. Персональные ЭВМ IBM PC и XT. Программирование на языке ассемблера. М.: Радио и связь, 1989. 336 с.

211. Сточный A.A., Кондратьев А.И. Теоретико-игровое информационное моделирование в системах принятия решений. Киев: Наукова думка, 1986. 279 с.

212. СуперЭВМ. Аппаратная и программная организация / Под ред. С.Фернбаха. М.: Радио и связь, 1991. 320 с.

213. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975. 256 с.

214. Теория и методы автоматизации проектирования вычислительных систем / Под ред. М.Брейера. М.: Мир, 1977. 284 с.

215. Тербер К. Дж. Архитектура высокопроизводительных вычислительных систем. М.: Наука, 1985. 272 с.

216. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981. 254 с.

217. Трахтенгерц Э.А. Влияние архитектуры и структуры многопроцессорных вычислительных машин на языки программирования и методы трансляции // Автоматика и телемеханика. 1986. № 3. С. 5-47.

218. Трахтенгерц Э.А. Программное обеспечение параллельных процессов. М.: Наука, 1987. 272 с.

219. Трусов С.С. Об эффективности простых диспетчеров // Изв. АН СССР. Техническая кибернетика. 1973. № 4. С. 150-160.

220. Управление и оптимизация производственно-технологических процессов / Н.М.Вихров, Д.В.Гаскаров, А.А.Грищенков, А.А.Шнуренко; Под ред. Д.В.Гаскарова. СПб.: Энергоатомиздат. Санкт-Петербургское отд-ние, 1995. 301 с.

221. Ферранте Дж., Оттенштейн К., Уоррен Дж. Граф программных зависимостей и его применение в оптимизации // Векторизация программ: теория, методы, реализация. Сб. статей. М.: Мир, 1991. С. 141-182.

222. ФордЛ.Р., ФалкерсонД.Р. Потоки в сетях. М.: Мир, 1966.276 с.

223. Французов Ю.А. Реорганизация кода по графу зависимости данных для ЭВМ векторно-конвейерного типа // Программирование. 1989. № 3. С. 25-49.

224. Французов Ю.А. Планирование потока команд с отложенным распределением регистров // Программирование. 1991. № 1. С. 58-66.

225. Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации// Программирование. 1992. № 3. С. 16-37.

226. Фрир Дж. Построение вычислительных систем на базе перспективных микропроцессоров. М.: Мир, 1990. 413 с.

227. Хантер Р. Проектирование и конструирование компиляторов. М.: Финансы и статистика. 1984. 232 с.

228. Хетагуров Я. А., Древе Ю.Г. Проектирование информационно-вычислительных комплексов. М.: Высшая школа, 1987. 279 с.

229. Хокни Р., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М.: Радио и связь, 1986. 392 с.

230. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 519 с.

231. Цой С., Цхай С.М. Прикладная теория графов. Алма-Ата: Наука, 1971. 500 с.

232. Чернобровцев A. Hewlett-Packard выпускает рабочие станции и серверы с процессорами РА-8000 // ComputerWeek-Moscow. 1996. № 27.

233. Чу Я. Организация ЭВМ и микропрограммирование. М.: Мир, 1975. 592 с.

234. Шадский А. Семейство DEC Alpha АХР // Открытые системы. 1994. № 3. С. 12-16.

235. Шейдвассер М.А. О длине и ширине размещений графов в решетках // Проблемы кибернетики: Сб. статей. Вып. 29. М.: Наука, 1974. С. 63-102.

236. Шнитман В. Архитектура процессоров UltraSPARC // Открытые системы. 1996. № 2. С. 5-13.

237. Шнитман В. Отказоустойчивые компьютеры компании Stratus // Открытые системы. 1998. № 1. С. 12-22.

238. Шубинский И.Б. Об одном подходе к обеспечению надежности модульных систем обработки информации // Надежность и контроль качества. 1984. № 9. С. 10-15.

239. Шубинский И.Б. Активная защита от отказов. М.: Знание, 1987. 61 с.

240. Элементы параллельного программирования / В.А. Вальков-ский, В.Е.Котов, А.Г.Марчук, Н.Н.Миренков; Под ред. В.Е.Котова. М.: Радио и связь, 1983. 240 с.

241. Электроника СБИС. Проектирование микроструктур / Под ред. Н.Айнспрука. М.: Мир, 1989. 256 с.

242. HP 9000 что внутри?//Системы и решения. 1996. № 3. С. 4-5.

243. Р7 процессор с архитектурой нового типа // ComputerWeek-Moscow. 1996. № 25.

244. RISC-технологии и вопросы разработки современных БЦВМ / В.И.Штейнберг, И.Б.Григорьева, В.А.Белов, В.Ф.Мишин // Проблемы информатизации. 1998. Вып. 3-4. С. 28-37.

245. Anderson J.P. A note on compiling algorithms // Communications of the ACM. 1964. № 7. P. 145-150.

246. Baer J.L., Bovet D.P. Compilation of arithmetic expressions for parallel computations // Proc. IFIP Congr., 1968. Amsterdam: North-Holland Publ. Co. 1968. P. 340-346

247. Barsi F., Grandoni F., Maestrini P. A Theory of Diagnosability of Digital Systems // IEEE Trans. Comput. 1976. V. C-25. № 6. P. 585-593.

248. Beatty J.C. An axiomatic approach to code optimization for expressions // Journal of ACM. 1972. V. 19. № 4. P. 613-640.

249. Belady L.A. A study of replacement algorithms for a virtual-storage computer // IBM Systems Journal. 1966. № 5. P. 78-82.

250. Colwell R.P., Nix R.P., O'Donnel J J., et. al. A VLIW architecture for a trace scheduling compiler // IEEE Trans. Comput. 1988. V. C-37. № 8. P. 967-979.

251. Dasgupta S., Tartar J. The identification of maximal parallelism in straight-line microprograms // IEEE Trans. Comput. 1976. V. C-25. № 10. P. 986-991.

252. Dasgupta S. Parallelism in loop-free microprograms // Proc. IFIP Congr. 1977. P. 745-750.

253. Eppstein D., Galil Z. Parallel algorithms techniques for combinatorial optimization // Ann. Rev. Comput. Sei. 1988. V. 3. P. 233-283.

254. Fischer C.N., LeBlanc R.J. Crafting a compilers with C. The Benjamin / Cummings Publishing Company, Inc., 1991. 812 p.

255. Fisher J.A. Trace scheduling: A technique for global microcode compaction // IEEE Trans. Comput. 1981. V. C-30. № 7. P. 478-490.

256. Fisher J.A., Landscov D., Shriver B. Microcode compaction: Looking backward and looking forward // Proc. of the 1981 AFIPS National Computer Conf. 1981. V. 50. P. 95-102.

257. Fisher J.A. A Very Long Instruction Word architectures and ELI-512 // Proc. of the 10th Symp. on Compiler Architectures, IEEE. June 1983. P. 140-150.

258. Fisher J.A. The VLIW machine: a multiprocessor for compiling scientific cod // IEEE Computer. 1984. V. 17. № 7. P. 45-53.

259. Fisher J.A., O'Donnel J.J. VLIW machines: multiprocessors we can actually program // COMPCON 84, IEEE, Feb. 1984. P. 299-305.

260. Fisher J.A., Ellis J.A., Ruttenberg J.C., Nicolau A. Parallel processing: a smart compiler and dump machine // SIGPLAN Notices. 1984. V. 19. № 6. P. 37-47.

261. Fisher J.A. The VLIW architecture: supercomputing via overlapped execution // The Second Intern. Conf. on Supercomputing. Santa Clara, California. May 3-8. 1987.

262. Fortune S., Wile J. Parallelizm in random access machines // Proc. of 10th ACM STOC 1978. P. 114-118.

263. Foster C.C., Riseman E.M. Percolation of code to enhance parallel dispatching and execution // IEEE Trans. Comput. 1972. V. C-21. № 12. P. 1411-1415.

264. Hakimi S.L., Amin A.T. Characterization of the connection assignment of diagnosable systems // IEEE Trans. Comput. 1974. V. C-23. № 1. P. 86-88.

265. Kavianpour A., Friedman A.D. Different Diagnostic Models for Multiprocessor Systems // Information Processing 80: Proc. IFIP Congr. Tokyo-Melburn, 1980. P. 157-162.

266. Lam M.S. Instruction scheduling for superscalar architectures // Annu. Rev. Comput. Sei. 1990. V. 4. P. 173-201.

267. Local microcode compaction techniques / D.Landscov, S.Davidson, B.Shriver, P.W.Mallett // ACM Comput. Surveys. 1980. V. 12. № 3. P. 261-294.

268. Margulis N. The Intel 80860//Byte. 1989. December. P. 333-339.

269. Margulis N. i860 Microprocessor Internal Architecture // Microprocessors and Microsystems. 1990. V. 14. № 2. P. 89-96.

270. Nakata I. A note on compiling algoritms for arithmetic expressions // Communications of the ACM. 1967. V. 10. № 10. P. 492-494.

271. Nicolau A., Fisher J.A. Measuring the parallelism available for Very Long Instruction Word architectures // IEEE Trans. Comput. 1984. V. C-33. № 11. P. 968-976.

272. Nicolau A. Uniform parallelism exploitation in ordinary programs // Proc. of the 1985 Intern. Conf. on Parallel Processing, Aug. 1985. P. 614-618.

273. Polychronopoulos C.D., Kuck D.J., Padua D.A. Execution of parallel loops on parallel processor systems // Int. Conf. Parallel Process., Aug. 19-22, 1986. Washington, D. C., 1986. P. 519-527.

274. Preparata F.P., Metze G., Chien R.T. On the Connection Assignment Problem of Diagnosable Systems // IEEE Trans. Electron. Comput. 1967. V. EC-16. № 6. P. 848-854.

275. Ramamoorthy S.V., Gonzalez M.J. A survey of techniques for recognizing parallel programs//Proc. FICC AFIPS, USA. 1969. V. 35. P. 1-15.

276. Ramamoorthy S.V., Park J.H., Li H.F. Compilation techniques for recognition of parallel processable tasks in arithmetic expressions // IEEE Trans. Comput. 1973. V. C-22. № 11. P. 986-998.

277. Ramamoorthy C.V., Tsuchiya M. A high-level language for horizontal microprogramming // IEEE Trans. Comput. 1974. V. C-23. № 8. P. 791-802.

278. Riseman E.M., Foster C.C. The inhibition of potential parallelism by conditional jumps // IEEE Trans. Comput. 1972. V. C-21. № 12. P. 1405-1411.425

279. Siewiorec D.P. Architecture of Fault-Tolerant Computers // Computer. 1984. V. 17. № 8. P. 9-18.

280. Squir I.S. A translation algorithm for multiple processor computer // Proc. 18 th ACM Nat. Conf. Colorado: Denver, 1963. P. 174-191.

281. Some experiments in local microcode compaction for horizontal machines / S.Davidson, D.Landscov, B.Shriver, P.W.Mallett // IEEE Trans. Comput. 1981. V. C-30. № 7. P. 460-477.

282. Stone H.S. One-pass compilation of arithmetic expressions for a parallel processor // Communications of the ACM. 1967. V. 10. № 4. P. 220-223.

283. Tokoro M., Tamura E., Takizuka T. Optimization of microprograms // IEEE Trans. Comput. 1982. V. C-30. № 7. P. 491-504.

284. Tsuchiya M., Gonzalez M.J. Toward optimization of horizontal microprograms // IEEE Trans. Comput. 1976. V. C-25. № 10. P. 992-999.

285. Tjaden C.S., Flynn M.J. Detection and parallel execution of independent instructions // IEEE Trans. Comput. 1970. V. C-19. № 10. P. 889-895.

286. Список использованных сокращений

287. АЛУ арифметико-логическое устройство

288. БИС большая интегральная схема

289. БНФ форма Бэкуса-Наура (нормальная форма Бэкуса)

290. БМУ блок микропрограммного управления1. ВМ вычислительный модуль1. ВС вычислительная система

291. ГЗД граф зависимости по данным1. ДГ диагностический граф1. ДМ диагностическая модель

292. ИМ -информационная магистраль1. КС командное слово1. ЛБ линейный блок1. ЛУ линейный участок1. МКС микрокомандное слово1. МО микрооперация1. РгФ регистровый файл

293. РОН регистр общего назначения

294. СБИС- сверхбольшая интегральная схема1. УМ управляющий модуль1. УП управляющая память1. ФМ функциональный модуль

295. ФУ функциональное устройство1. ЭК элементарная команда1. ЭП элементарная проверка

296. BSP Burroughs Scientific Processor1. MMX MultiMedia extensions

297. PRAM Parallel Random Access Machine1. RAM Random Access Machine

298. SIMD Single Instruction - Multiple Data

299. VIS Visual Instruction Set

300. VLIW Very Long Instruction Word

301. Результаты исследования алгоритмов оптимизации объектного кода