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

Актуальность темы

В настоящее время лидирующим продуктом микроэлектроники являются микропроцессоры с RISC-ядром [1, 3, 16, 32], которые используются в качестве элементной базы современных систем обработки данных, включая параллельную обработку. RISC-ядро предполагает выполнение любых операций над данными, которые могут содержаться только в регистрах, а обращение к памяти происходит только при выполнении операций записи и чтения данных, причем за существенно большее время [1, 3, 32, 41, 39, 43, 42].

Как правило, RISC-ядро присутствует во всех современных суперскалярных процессорах, причем в последнее время интенсивно разрабатываются процессоры, использующие программное управление параллелизмом выполняемых операций. Примерами таких процессоров могут служить отечественные разработки группы инженеров под руководством профессора Б. Бабаяна — процессор суперЭВМ «Эльбрус-3» [15, 10], проект процессора «Эльбрус Е2К» [44], известная модель i860 фирмы Intel [31, 14], а также новый совместный проект фирм Intel и Hewlett-Packard — процессор Itanium (изначально Merced) [35].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность работы. Теоретические результаты и программные средства, полученные при выполнении диссертационной работы, использованы при выполнении Рязанской государственной радиотехнической академией госбюджетных научно-исследовательских работ по темам «Рабочая станция разработчика мобильного программного обеспечения для параллельных вычислительных систем на основе современной элементной базы» (гос. per. № 1 200 001 955) и «Создание теории автоматизированного проектирования мобильного программного обеспечения и оптимизирующих средств трансляции для параллельных систем на базе процессоров с суперскалярной архитектурой» (гос. per. № 1 200 001 955), проводимых по заданию Министерства образования РФ, а также по теме «Модели, методы, инструментальные средства и научно-методическое обеспечение процесса проектирования параллельных систем с использованием CASE-технологий» (гос. per. № 12 001 105 108), проводимой в рамках научно-технической программы Минобразования РФ «Научное, научно-методическое, материально-техническое и информационное обеспечение системы образования» .

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

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

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

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

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

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

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

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

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

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

— Рязанская государственная радиотехническая академия (в учебном процессе для студентов специальностей 220 300 «Системы автоматизированного проектирования» и 220 500 «Конструирование и технология электронно-вычислительных средств» при изучении архитектур современных микропроцессоров и систем параллельной обработки данных, построенных на их базе, а также методов оптимизации программ, реализуемых в составе компиляторов).

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

Апробация работы. Основные положения диссертации представлены и обсуждены на следующих конференциях: 4-я Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (г. Рязань, 1999), 5-я Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании (НИТ-2000)» (г. Рязань, 2000), 9-я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2000), 6-я Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (г. Рязань, 2001), 10-я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2001), 7-я Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании (НИТ-2002)» (г. Рязань, 2002), а также на 31-й и 32-й научно-методических конференциях Военного автомобильного института (г. Рязань, 2001, 2002).

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

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех разделов, заключения и списка литературы, изложенных на 164 е., а также приложений на 57 с.

Список литературы

включает 102 наименования. Текст диссертации содержит 25 таблиц и 35 рисунков.

Выводы.

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные положения диссертации опубликованы в работах автора [47−58, 75, 76].