Введение к работе
Актуальность темы. Параллельные вычисления являются од-тим из основных средств повышения производительности современ-тых процессоров. Для увеличения эффективности использования по-генциального параллелизма, присутствующего в программах, в по-;леднее время широкое распространегше получили процессоры, ис-тользующие статический или программный параллелизм. Примерами эешений, использующих такой подход, могут служить суперкомпью-геры Intel Paragon, созданные на базе процессоров i860, или расширения систем команд процессоров для современных персональных ком-тьютеров и рабочих станций (ММХ, 3Dnow, VIS). При такой органи-5ации работы распределение инструкций по функциональным устройствам (ФУ) процессора производится на этапе трансляции программы, гто с одной стороны, позволяет более полно использовать ресурсы, тредоставляемые процессором, а с другой - накладывает повышенные гребования на эффективность алгоритмов трансляции и оптимизации трограмм.
Процессоры со статическим управлением параллелизмом на уфовне ФУ имеют следующие характерные особенности: » фиксированное время исполнения большинства команд; » сокращенный набор команд (RISC); » наличие большого числа ФУ; увеличение числа доступных регистров; » простая внутренняя структура.
Следует также отметить, такие черты, присущие этим процессорам, как «плавающий» формат командного слова (КС) и мультипорто-вый регистровый файл. Наличие командного слова «плавающего» формата означает, что командное слово имеет несколько вариантов разбиения на поля (форматов). Каждый из форматов обеспечивает цоступ к определеішой части ресурсов процессора. При этом время смены форматов, как правило, отлично от нуля.
Простота вігутренней организации подобных архитектур позво-пяет сократить цикл разработки новых процессоров, уменьшить площадь кристалла, увеличить рабочую тактовую частоту, а также сократить процент брака при их производстве.
Таким образом, процессоры с программным управлением параллелизмом на уровне ФУ являются перспективным направлением в
2 современной микрозлектроішке и применяются в системах обработки данных, требующих обеспечение повышенной производительности.
В связи с этим актуальность приобретает задача создания комплекса методов, позволяющих максимально эффективно использовать возможности, предоставляемые такими процессорами.
Целью работы является разработка методов и алгоритмов организации параллельных вычислений, обеспечивающих повышение производительности вычислительных систем, построенных на базе процессоров с программным управлением ФУ.
Учитывая, что управление ФУ и формирование КС происходит на уровне объектного кода программы, основные задачи формулируются следующим образом:
-
Выполнить анализ существующих программных систем и методов, применяемых при трансляции и оптимизации программ и оценить возможности их использования для систем с программным управлением ФУ процессора.
-
Разработать методы и алгоритмы для формирования и оптимизации объектного кода, учитывающие специфику таких процессоров, в частности, плавающий формат КС и мультипортовый регистровый файл.
-
Разработать программные средства для проверки корректности и получения характеристик указанных методов и алгоритмов.
Методы исследования. При решении поставленных задач в диссертационной работе использован аппарат теории графов, теории множеств и теории расписаний.
Научная новизна работы заключается в следующем:
-
Разработана модель процессора, учитывающая такие особенности процессоров с программным управлением на уровне ФУ, как «плавающий» формат КС с ненулевым временем смены формата и мультипортовый регистровый файл.
-
Разработан метод совместного планирования загрузки функциональных устройств и регистровой памяти целевой вычислительной системы, учитывающий возможность наличия командного слова «плавающего» формата и мультипортового регистрового файла, что позволяет более эффективно использовать ресурсы целевой вычислительной системы по сравнению с методами раздельного планирования вычислений и загрузки регистров.
-
Разработан эффективный метод построения дерева разбора арифметических выражений, учитывающий типичный набор операций]
процессоров с программным управлением параллелизмом на уровне ФУ и позволяющий формировать дерево разбора минимальной высоты.
-
Предложен новый подход статического предсказания ветвлений, ориентированный на достижение максимального параллелизма в объектной программе и позволяющий выявлять ветви, оптимизация которых не дает выигрыша во времени исполнения.
-
Предложена модель программы (диаграмма циклов и ветвлений), сочетающая детализацию на уровне инструкций с отображением управляющих структур. Это дает возможность эффективного применения методов, расширяющих область локальной оптимизации объектного кода.
-
Разработан метод преобразования графа зависимости по данным к виду дерева с минимальным числом дополнительно используемых регистров, в том числе, и в случае мультипортового регистрового файла. Метод позволяет применять известные алгоритмы укладки деревьев для оптимизации объектного кода по критерию времени.
Достоверность основных положений и полученных результатов диссертационной работы подтверждается моделированием на ЭВМ, разработкой действующих программных средств, а также свидетельствами об официальной регистрации разработанных программ и внедрением результатов в разработках ряда организаций и предприятий.
Практическая ценность работы. Теоретические результаты и программные средства, полученные при выполнении диссертационной работы, использованы в процессе проведения в Рязанской государственной радиотехнической академии госбюджетной научно-исследовательской работы по теме "Рабочая станция разработчика мобильного программного обеспечения для параллельных вычислительных систем на основе современной элементной базы" (г.р. N 01200001955).
Разработаны методы и алгоритмы, позволяющие эффективно использовать потенциальные возможности параллелизма уровня инструкций, которые во многом определяют эффективность оптимизации программ для ВС с управлением на уровне ФУ.
Разработан программный пакет, включающий в себя средства для трансляции программ с языка высокого уровня в промежуточный код и подсистему построения моделей микро- и макроуровня, необходимых для исследования полученного кода, которые могут использо-
4 ваться как в исследовательских, так и в учебных целях. Пакет имее открытую модульную структуру, что позволяет использовать компо ненты пакета, как самостоятельные утилиты, а также в комплексе < другими программными пакетами.
Проведен вычислительный эксперимент, подтвердивший кор ректность предложенного алгоритма разбора выражений и позволив ший получить его количественные характеристики, показавшие целе сообразность его применения при разработке трансляторов для про цессоров с программным управлением ФУ.
Разработан настраиваемый программный модуль построени; списочных расписаний загрузки регистров и функциональных уст ройств, обеспечивающий возможность интеграции (включения) в су шествующие системы генерации кода.
Основные модели и методы организации параллельных вы числений на микро- и макроуровнях параллелизма, предложенные j диссертационной работе, реализованы в программных комплексах официально зарегистрированных в Российском агентстве по правової охране программ для ЭВМ, баз данных и топологий интегральны; микросхем (РОСАПО) и Российском агентстве по патентам и товар ным знакам (РОСПАТЕНТ).
Реализация и внедрение. Теоретические и практические ре зультаты, полученные автором диссертации, использованы при проек тарований и создании ряда программных комплексов организациі вычислительных процессов для процессоров с программным управле нием параллелизмом на уровне функциональных устройств, а такжі при разработке и оптимизации программного обеспечения, предна значенного для систем обработки данных на базе процессоров с воз можностью управления ФУ.
В частности, научные и практические результаты диссертаци онной работы использованы в разработках следующих организаций і предприятий:
Федеральное агентство правительственной связи и информаци] при Президенте российской федерации, НТЦ "АТЛАС" (реализа ция криптографического алгоритма CAST-128 в рамках проект создания системы передачи данных по открытым каналам связи);
ГУП ОКБ «Спектр» при Рязанской государственной радиотехни ческой академии (выбор технических решений программны: средств обработки высокоинформативных потоков телеметриче ской информации для системы РОКС).
Апробация работы. Основные положения и результаты диссертационной работы представлены и обсуждены на следующих конференциях и семинарах: Всероссийская конференция "Новые информационные технологии в радиоэлектронике" (Рязань, 1997); 2-я Всероссийская конференция "Современные информационные системы в образовании" (Рязань, 1998); Всероссийская конференция "Новые информационные технологии в радиоэлектронике" (Рязань, 1998); XXIX научно-методическая конференция Военного автомобильного института (Рязань, 1999); 4-я Всероссийская конференция "Новые информационные технологии в научных исследованиях и в образовании" (Рязань, 1999); Международный научно-технический семинар "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций" (Рязань, 1999); 3-я Московская Международная телекоммуникационная конференция "Молодежь и наука" в научной сессии МИФИ (Москва, 2000); 9-я Международная конференция "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций" (Рязань 2000); конференции профессорско-преподавательского состава Рязанской государственной радиотехнической академии (1998 -2000 г.г.)
Публикации. По результатам исследований автором опубликовано 18 работ, среди которых 1 статья в центральной печати, 2 свидетельства об официальной регистрации программ для ЭВМ в РОСАПО и РОСПАТЕНТ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения и списка литературы, изложенных на 114 стр., а также приложений на 51 стр. Список литературы содержит 94 наименования.
