Введение к работе
Актуальность темы. Организация параллельных процессов является одной из важнейших проблем, возникающих при разработке новых проектов в области современной вычислительной техники. Значительные успехи в этом направлении достигнуты в области создания больших мультипроцессорных суперЭВМ с матричной и векторно-конвейерной архитектурой, которые ориентированы на макроуровень параллелизма вычислений, где основное внимание уделяется вопросам параллельного выполнения независимых программ и подпрограмм, а также больших программных фрагментов, таких как независимые ветви, циклы и их отдельные итерации.
Однако в настоящее время лидирующим продуктом микроэлектроники являются микропроцессоры с суперскалярной архитектурой, которые ориентированы на микроуровень параллелизма и обеспечивают достижение пиковой производительности, сопоставимой с характеристиками вычислительных систем (ВС) класса суперЭВМ. Отличительной особенностью таких процессоров является возможность параллельного выполнения операций программы, что в итоге обеспечивает формирование нескольких результатов за каждый такт синхронизации. Это достигается благодаря наличию в составе микропроцессора нескольких функциональных устройств (ФУ) конвейерного типа. Устройство управления выполняет дешифрацию командных слов (КС) программы и инициирует (запускает на исполнение) операции в соответствующих ФУ процессора. Время выполнения операции может занимать несколько тактов, что определяется длиной конвейера ФУ.
В целом суперскалярный микропроцессор может одновременно выполнять несколько операций в разных ФУ или совмещать их выполнение в одном ФУ до тех пор, пока эти операции независимы по данным. В частности, к процессорам с суперскалярной архитектурой относят известную модель i860 фирмы Intel , процессор отечественной суперЭВМ "Эльбрус-3", а также другие универсальные и специализированные процессоры отечественных и зарубежных производителей.
Основным преимуществом использования микропроцессоров с суперскалярной архитектурой при построении многопроцессорных ВС является существенное расширение области применения методов параллельных вычислений (от управления параллелизмом операций программы в пределах процессора до одновременного решения множества задач процессорами системы) при разработке прикладного программного обеспечения, ориентированного на решение различных классов задач обработки информации.
При этом, если методы организации параллельных процессов на макроуровне вычислений исследованы в достаточном для инженерной практики объеме, то при реализации микропараллелизма в программах для суперскалярных процессоров возникает ряд научно-технических задач принципиального характера, связанных с генерацией эффективного объектного кода.
Суть зтігх задач определяется наличием существенных различий в архитектурных решениях современных суперскалярных процессоров, основные из которых заключаются в следующем: управление параллелизмом операций
может быть динамическим (аппаратным), статическим (программным) или аппаратно-программным; количество и типы ФУ могут варьироваться в широких пределах; КС могут иметь отличающиеся форматы для управления разными подмножествами ФУ и для операций разных типов; распределение регистров для хранения временных данных может выполняться аппаратно или программно; количество и типы регистровых файлов (РгФ) могут сильно отличаться в зависимости от модели процессора.
Основным препятствием для массового использования процессоров с суперскалярной архитектурой является сложность и трудоемкость получения эффективных объектных программ, учитывающих особенности конкретной модели процессора. Это обстоятельство делает актуальной проблему разработки формальных моделей, методов и алгоритмов организации параллельных процессов на микроуровне вычислений, применение которых в инженерной практике позволяет решить основные задачи создания инструментальных средств автоматизации программирования для суперскалярных процессоров с программным управлением параллелизмом, обеспечивающих настройку на архитектурные особенности конкретной модели процессора.
Кроме того следует отметить, что многопроцессорные ВС по сути своего построения являются отказоустойчивыми, поскольку в процессе их функционирования, как правило, часть процессоров периодически бездействует из-за алгоритмических особенностей решаемых задач, и эти свободные процессоры целесообразно использовать для диагностирования отказов посредством проведения взаимных проверок в режиме реального времени.
Поэтому актуальной также представляется проблема разработки математических моделей, методов и алгоритмов организации параллельных процессов и на макроуровне вычислений, направленных на повышение производительности и обеспечение отказоустойчивости многопроцессорных систем за счет сокращения времени идентификации отказавших процессоров и последующей реконфигурации системы в процессе решения прикладных задач в режиме реального времени. Полученные результаты также могут быть использованы при создании соответствующих средств автоматизации программирования для реализации функций подготовки объектного кода к вычислениям с взаимным контролем работоспособности процессоров системы.
Целью работы является разработка методов организации параллельных процессов на микро- и макроуровнях вычислений в специализированных системах обработки данных, построенных на базе суперскалярных процессоров с программным управлением параллелизмом операций.
Применение этих методов на микроуровне вычислений позволяет повысить производительность системы за счет генерации эффективного объектного кода, обеспечивающего параллельное выполнение скалярных операций программы, а на макроуровне позволяет организовать отказоустойчивую работу магистрально-модульных многопроцессорных систем путем автоматического обнаружения отказов с последующей реконфигурацией системы в процессе решения прикладных задач.
Основные задачи работы формулируются следующим образом:
разработать формальные модели организации параллельных процессов на микроуровне вычислений, учитывающие такие архитектурные особенности современных процессоров с суперскалярной архитектурой, которые влияют на эффективность объектного кода и позволяют использовать эти модели для целого класса суперскалярных процессоров с программным управлением параллелизмом операций;
разработать единые методы и алгоритмы, обеспечивающие решение задач генерации и статической оптимизации объектного кода как для отдельных линейных участков, так и для программ с циклами и ветвлениями;
разработать единые методы и алгоритмы, обеспечивающие решение задачи распределения регистров при генерации объектного кода для различных структурных вариантов организации регистровой памяти в суперскалярных процессорах, отличающихся числом доступных РгФ для ФУ процессора;
разработать формальные методы анализа и синтеза диагностических графовых моделей, дешифрации результатов диагностирования и планирования загрузки вычислительных модулей, комплексное применение которых обеспечивает существенное сокращение времени выявления устойчивых неисправностей при реализации процедур активной отказоустойчивости на макроуровне параллельных вычислений в магистрально-модульных многопроцессорных системах реального времени;
практически реализовать в составе программных инструментальных средств и экспериментально оценить эффективность предложенных моделей, методов и алгоритмов организации параллельных вычислений на макро- и микроуровнях параллелшма.
Методы исследования. Для решения поставленных задач использован аппарат теории множеств, теории графов, теории расписаний, теории дискретной оптимизации и математического программирования, теории ВС, параллельных вычислительных процессов и технической диагностики.
Научная новизна. В диссертационной работе предлагается систематизированное решение и теоретическое обобщение важной научно-технической проблемы организации параллельных процессов на микро- и макроуровнях вычислений в специализированных системах обработки данных, построенных на базе суперскалярных процессоров с программным управлением параллелизмом операций, с целью обеспечения повышенной производительности и отказоустойчивой работы таких систем в реальном времени.
Научная новизна диссертационной работы состоит в следующем.
1. Предложена новая теоретико-графовая модель организации параллельных скалярных вычислений на микроуровне параллелизма (дизъюнктивный граф информационно-структурных зависимостей), которая по сравнению с известными моделями, такими, как граф зависимости по данным (ГЗД) и его модификации, управляющий граф, билогический граф программы и др., имеет целый ряд преимуществ, основными из которых являются:
- отражает не только алгоритмические, но и архитектурные ограничения
на параллельное выполнение операций программы;
- может использоваться для решения задач как локальной оптимизации
объектного кода в пределах линейных фрагментов (подобно ГЗД), так и гло
бального анализа и оптимизации программы с циклами и ветвлениями
(традиционно применяются управляющий или билогический граф).
2. Разработан комплекс взаимосвязанных методов организации парал
лельных скалярных вычислений в суперскалярных процессорах с программ
ным управлением параллелизмом операций, который базируется на использо
вании дизъюнктивных графов информационно-структурных зависимостей и
позволяет использовать единые методы решения задачи генерации и стати
ческой оптимизации параллельного объектного кода для различных вариан
тов этой задачи, где:
- рассматривается отдельный линейный участок или программа с циклами
и ветвлениями в целом;
- учитываются разные архитектурные решения процессора (одно
кристальный микропроцессор или многокристальный процессор на базе мик-
ропрограммируемых БИС, переменное или фиксированное расположение
управляющих полей в командном слове, пересекаются или нет множества
выполняемых операций для разных ФУ и др.);
- учитывается режим работы процессора (скалярный или конвейерный);
- допускаются разные критерии оптимизации (время исполнения, длина
объектного кода, длина кода при ограничении на время исполнения).
3. Задача размещения временных скалярных данных в регистровой памяти
суперскалярного процессора по критерию минимального числа одновременно
занимаемых регистров сведена к задаче Дилворта (поиска минимального
множества непересекающихся путей на графе, содержащих в совокупности
все его вершины). Предложен метод решения, единый для последовательных
и параллельных процессов на микроуровне вычислений при различных вари
антах структурной организации регистровой памяти:
- имеется один РгФ, доступный для всех ФУ процессора;
- процессор содержит несколько РгФ, каждый из которых является до
ступным для некоторого подмножества ФУ;
- каждое ФУ процессора имеет отдельный набор регистров (для суперска
лярных процессоров на основе микропрограммируемых БИС).
4. Для организации диагностических процессов на макроуровне парал
лельных вычислений в магистрально-модульных многопроцессорных систе
мах обоснован выбор симметричной диагностической модели (ДМ), приме
нение которой позволяет существенно уменьшить число взаимных проверок
вычислительных модулей для определения их технического состояния по
сравнению с классическими моделями PMC (Preparata, Metze, Chien) и BGM
(Barsi, Grandoni, Maestrini). Для выбранной ДМ впервые получено:
- новое решение задачи характеризации, которое расширяет и обобщает
известные результаты. Оно устанавливает необходимые и достаточные усло
вия, определяющие структуру диагностического графа (ДГ), гарантирующего
получение заданной меры параллельной диагностируемое многопроцес
сорной системы;
- решение проблемы синтеза оптимальных ДГ с минимальным числом ребер, для чего разработаны и обоснованы эффективные процедуры малой трудоемкости, обеспечивающие построение таких графов для заданной меры параллельной диагностируемости многопроцессорной ВС.
Перечисленные теоретические результаты получены автором при выполнении диссертационной работы и выносятся на защиту.
Достоверность основных положений и полученных результатов диссертационной работы подтверждается математическими обоснованиями и доказательствами, моделированием на ЭВМ, разработкой действующих программных средств, а также свидетельствами об официальной регистрации разработанных программных комплексов и внедрением результатов в разработках ряда организаций и предприятий.
Практическая ценность работы. С использованием представленных в диссертации теоретических результатов и инструментальных программных средств с 1983 года проведено 19 НИР и ОКР. Эти работы выполнялись в рамках важнейшей хоздоговорной и госбюджетной тематики в соответствии со следующими руководящими документами: межведомственные программы фундаментальных и поисковых исследований на 1981-1985 г.г. и на 1986-1990 г.г.; решение ВПК № 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 страниц.
