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

Учреждение Российской академии наук Научно-исследовательский институт системных исследований РАН

00349 1665

Широков Илья Андреевич

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

05.13.11 - "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей"

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

уЧо

"¿Л* **0

На правах рукописи УДК 004.414.2

Москва 2010

1 1 ФЕВ 2010

003491665

Работа выполнена в учреждении Российской академии наук научно-исследовательском институте системных исследований РАН.

Научный руководитель: кандидат физико-математических наук Кушниренко Анатолий Георгиевич

Официальные оппоненты: доктор физико-математических наук Петренко Александр Константинович, кандидат физико-математических наук Иванов Денис Владимирович

Ведущая организация: Российский федеральный ядерный центр -Всероссийский научно-исследовательский институт экспериментальной физики (РФЯЦ-ВНИИЭФ)

Защита диссертации состоится 17 февраля 2010 г. в 16 часов на заседании диссертационного совета Д 002.265.01 при НИИСИ РАН по адресу 117218, Москва, Нахимовский пр-т, д. 36, корп.1, конференц-зал.

С диссертацией можно ознакомиться в библиотеке НИИСИ (комн. 13-12). Автореферат разослан 16 января 2010 г.

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

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

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

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

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

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

3

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

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

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

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

Методы исследования. Исследования имели как теоретическую, так и практическую направленность. Большая часть работы прошла в рамках программы № 15 фундаментальных исследований Президиума РАН "Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий GRID".

Все исследования проводились только для алгоритмов с регулярными потоками данных в рамках подхода под названием «встречная оптимизация»: параметры и частично архитектура ЭВМ, узла, микропроцессора

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

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

Направления:

• суперЭВМ, мультипроцессорные ЭВМ, вычислительные узлы;

• расширения универсальных процессоров;

• сопроцессоры и спецпроцессоры.

Конкретные разработки:

• проекты СуперЭВМ-1 и СуперЭВМ-6; вычислительные узлы СЭВМ-1 и СЭВМ-6;

• проект вычислительного узла на базе 4-х ЦПОС-02;

• «сигнальное расширение» универсального процессора Комдив-64-СМП; модернизация арифметического сопроцессора СЭВМ-6; разработка Б [МО-сопроцессора в составе спецпроцессора К128.

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

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

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

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

• Показана применимость подхода «встречной оптимизации» к задачам трехмерного моделирования и обработки сигналов на процессорах и сопроцессорах СуперЭВМ с распределенной памятью.

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

Практическая ценность. Автором выделена теоретическая конструкция «схемы Потокового Программирования», которая в настоящий момент активно используется в НИИСИ РАН при разработке новых процессоров.

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

Автором разработана программная модель расширения для обработки сигналов для универсального процессора Комдив-64-СМП.

В рамках проекта СуперЭВМ СЭВМ-6 автором проведена оптимизация архитектуры сопроцессора вещественной арифметики под практические задачи обработки сигналов, в том числе под реальную задачу обработки данных радара с синтезированной антенной решеткой (Synthetic Aperture Radar, SAR).

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

Публикации. По теме диссертационной работы опубликовано 8 работ; из них 1 в изданиях по перечню ВАК.

Объем и структура работы. Диссертация состоит из введения, 4-х глав и заключения. Список использованной литературы содержит 52 наименования. Текст диссертации содержит 132 страницы машинописного текста.

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

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

В первой главе описывается «схема потокового программирования» (ПП) процессоров. Первоначально, схема потокового программирования была построена для программирования разрабатываемой в НИИСИ РАН суперЭВМ с вычислительными узлами на основе сопроцессора вещественной арифметики - СЭВМ-6. В дальнейшем схема потокового программирования активно использовалась при проектировании различных специализированных и универсальных микропроцессоров, разрабатываемых в НИИСИ РАН.

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

третий - пк+2 и т.д. Таким образом, мевду двумя последовательными командами одного потока проходит ровно п тактов, за это время завершится выполнение предыдущей команды и будет доступен ее результат.

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

Схема ПП применима и в случае, когда несколько вычислительных узлов разделяют общеий ресурс: пусть к ВУ с конвейером длины п конкурируют за общий ресурс, к которому можно обращаться каждый такт. Тогда, чтобы не возникало конфликтов между различными потоками на различных ВУ, схему ПП для нескольких ВУ необходимо подправить следующим образом. Во-первых, время использования общего ресурса делится между потоками: 1й ВУ обращается к общему ресурсу только на тактах с номерами пк1,...,пк1+п-1, 2й ВУ - на тактах с номерами пк1+п,...,пк1+2п-1, Зй ВУ - на тактах пк1+2п,...,пк1+Зп-1 и т.д. Во-вторых, так как на различных ВУ выполняются одинаковые программы, а время использования общего ресурса разделено указанным образом, то программы на различных ВУ запускаются не одновременно, а с задержкой в п тактов: 2й ВУ начинает работу через п тактов после 1го, Зй - через п тактов после 2го и т.д. Наконец, программа для одного потока, команды которой затем будут повторены по п раз для разных потоков на одном ВУ, пишется таким образом, чтобы обращение к общему ресурсу происходило только в командах с номерами к1+1. Тогда после повторения каждой команды п раз для различных потоков ВУ будет обращаться к общему ресурсу только в отведенное ему время.

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

В настоящее время схема Потокового Программирования широко используется в НЙИСИ РАН для параллельного вычисления различных алгоритмов. Например, это подход применялся для проекта СуперЭВМ СЭВМ-6 на задачах бРРМ, Ми1пСпс1, 8\уеерЗО и задачах обработки сигналов.

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

При помощи теоретического анализа Быстрого Преобразования Фурье и прикладных алгоритмов получены оценки производительности для проекта СуперЭВМ СЭВМ-6.

Численные результаты для вектора из N=2'° комплексных 64-разрядных (32 + 32) отсчетов

К Общее время, 10"3 сек. Среднее время на одно БПФ, 10"3 сек. Эффективность, %

4 0,15041 0,037603 42,55

20 0,58822 0,029411 54,40

100 2,77727 0,027773 57,61

500 13,7225 0,027445 58,30

1000 27,4041 0,027404 58,39

■00 0,027363 58,47

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

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

Для оценки производительности СуперЭВМ в целом показано, как вкладывается трехмерная решетка размером 2fx2gy-2h в гиперкуб размерности (f+g+h) (решение строится по индукции), и приведен алгоритм транспонирования матриц, снабженный оценкой времени транспонирования в зависимости от параметров СуперЭВМ'.

Т„ (2", AB) = 32(а + 4 АВ, -) + 4(п - 4)(« +

V 16*16 2 ß I ß

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

Оценивается производительность ЭВМ с арифметическим сопроцессором на одной из реальных задач обработки сигналов - на задаче обработки данных радара с синтезированной антенной решеткой (Synthetic Aperture Radar, SAR). Отметим, что особенностью этой задачи является необходимость обработки данных "на лету", в реальном времени. Программный эмулятор вычислительного узла СЭВМ-6, разработанный с участием автора, полностью подтвердил теоретические результаты, полученные в настоящем разделе.

Проведены оценки производительности вычислительного модуля на основе 4-х процессоров ЦГЮС-02. Для этого рассмотрена одна из возможных модификаций классического алгоритма быстрого преобразования Фурье: переход к основанию 4.

JV/4-l n¡ =0

+ (-1)4' 4N /2 + п2] + iklx[3/4N + n2

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

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

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

3 + 6fc + 3(l + k)log2(N/k) обработки фильтра: v комплексных операций в секунду,

2N/k

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

Третья глава посвящена разработке расширения цифровой обработки сигналов для универсального 64-разрядного процессора КОМДИВ 64 - СМП. Были проанализированы возможные усовершенствования традиционной архитектуры и при помощи методов оценки производительности, описанных в предыдущей главе, была выбрана модернизация архитектуры, которая позволяет увеличить производительность микропроцессора на задачах обработки сигналов до 3 раз.

С точки зрения задач обработки сигналов, вычислительный блок процессора КОМДИВ 64 - СМП построенный по традиционной архитектуре позволяет параллельно выполнять операции:

S умножения с накоплением 64-битных чисел (а*Ь+с); S уагрузки/выгрузки 64-битного слова.

Усовершенствование №1: одновременная обработка PS (Paired Single) команд. В этом случае вычислительный блок процессора К0МДИВ 64 -С МП в дополнение к раннее описанным возможностям позволит параллельно выполнять операции:

•S одновременного умножения с накоплением двух 32-битных чисел в

соседних ps-секциях 64-битного слова(al*bl+cl; а2*Ь2+с2); S загрузки/выгрузки 64-битного слова.

Усовершенствование №2: одновременная загрузка/выгрузка двух соседних 64-битных слов. В этом случае вычислительный блок процессора КОМДИВ 64 - СМИ в дополнение к раннее описанным возможностям позволит параллельно выполнять операции:

S одновременного умножения с накоплением двух 32-битных чисел в

соседних ps-секциях 64-битного слова (al*bl+cl; а2*Ь2+с2); ■S загрузки/выгрузки двух соседних 64-битных слов в/из соседних регистров процессора.

Усовершенствование №3: одновременное вычисление операций вида а+Ь и а-Ь, при этом вычислительный блок процессора КОМДИВ 64 - СМП будет позволять параллельно выполнять (при некоторых ограничениях, описанных ниже) операции:

J двух умножений с накоплением 64-битных чисел (a*b+c; а*Ь-с) или четырех умножений с накоплением двух 32-битных чисел в соседних ps-секциях 64-битного слова (al*bl+cl; al*bl-cl; а2*Ь2+с2; а2*Ь2-с2); •S загрузки/выгрузки двух соседних 64-битных слов в/из соседних регистров процессора.

Производительность процессора на преобразовании «бабочка Фурье»

Время вычисления 4-х бабочек Фурье (тактов) Поддерживаемая производительность (МФлопс) Пиковая производительность (МФлопс)

Исходный вариант 36 444 800

Усовершенствование 1 18 888 1600

Усовершенствование 2 16 1000 1600

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

По результатам теоретических оценок производительности была спроектирована программная модель расширения обработки сигналов. Для повышения производительности микропроцессора КОМДИВ 64 - СМП при решении задач цифровой обработки сигналов в архитектуру микропроцессора были внесены следующие дополнения:

• добавлены специальные DSP команды;

• добавлен режим работы, позволяющий выполнять 4 команды за такт;

• добавлен накристальный кэш 2-го уровня.

Данное расширение позволило повысить производительность процессора на задачах обработки сигналов в 3 раза.

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

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

1 В скобках приведена пиковая производительность без учёта параллельной обработки команд а+Ь и а-Ь.

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

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

1) параллельный запуск тестовых программ на ЯТЬ-модели процессора и его эталонной модели и сравнение содержимого регистров и памяти в обеих моделях после каждого такта или после завершения каждой инструкции;

2) сравнение поведения отдельных блоков ШЪ-модели (сравнение выходных сигналов) с некоторыми эталонными моделями этих блоков на определенных тестовых последовательностях входных сигналов.

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

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

Программный эмулятор проектируемого процессора покомандного уровня (ПКЭМ) необходимо создавать на самой ранней стадии разработки

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

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

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

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

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

Под руководством автора был разработан эмулятор ПКЭМ для разрабатываемого в НИИСИ РАН универсального 64-битного микропроцессора, который удовлетворяет всем описанным выше требованиям.

В заключении приводятся основные результаты работы.

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

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

Для обеспечения оценки производительности был сформулирован в общем виде подход к оценке производительности вычислительной системы. Введена схема потокового программирования, которая широко используется в НИИСИ РАН для разработки процессоров, процессорных модулей, ЭВМ и систем обработки сигналов. Описана ее реализация для различных типов вычислительных систем и сс применение в рамках подхода «встречной оптимизации»: структура алгоритма и архитектура вычислительной системы оптимизируются одновременно для достижения максимальной производительности.

Получены оценки производительности для проекта СуперЭВМ СЭВМ-6 и вычислительного модуля на основе 4-х процессоров ЦПОС-02. Для вычислительного модуля на процессорах ЩЮС-02 оценки производительности позволили выделить ключевые параметры, влияющие на производительность модуля. Для СуперЭВМ СЭВМ-6 эти оценки позволили оптимизировать архитектуру вычислительного узла и выбрать оптимальные параметры коммуникационной среды для повышения эффективности СуперЭВМ. Для оценки производительности СуперЭВМ в целом приводится схема распределения вычислительных узлов по вершинам гиперкуба и

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

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

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

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Лесных A.A., Широков И.А. "Проектирование расширения обработки сигналов для универсального микропроцессора" - М.: ФПМ, том 12, выпуск 8,2006 - С. 159-180.

2. Лесных A.A., Широков И.А. "Оценки производительности суперЭВМ на основе сопроцессора вещественной арифметики на задачах обработки сигналов" - М.: НИИСИ РАН, 2005 - С. 20-49.

3. Лесных А.А, Широков И.А., "Методы Оптимизации Алгоритмов: Схема потокового программирования" - М.: НИИСИ РАН, 2005 - С. 7-19.

4. Широков И.А. "Проектирование DSP-расширения для универсального 64-разрядного микропроцессора" - М.: НИИСИ РАН, 2005 - С. 71-86.

5. Широков И.А. "Быстрое преобразование Фурье на модуле с четырьмя процессорами ЦПОС-2"- М.: НИИСИ РАН, 2005 - С. 50-70.

6. Аряшев С.И., Широков И.А. "Оценки производительности DSP-расширения для процессора КОМДИВ 64 - СМП" - М.: НИИСИ РАН, 2005-С. 87-95.

7. Лесных АЛ., Широков И.А. "Покомандная модель проектируемого 64 битного процессора" - М.: НИИСИ РАН, 2005 - С. 96-116.

8. Лесных A.A., Широков И.А. "Обзор современных методов фильтрации данных М.: НИИСИ РАН, 2005 - С. 117-130.

Подписано в печать:

13.01.2010

Заказ Ла 3238 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.

Цель работы (исследования).

Методы исследования.

Научная новизна работы.

Результаты работы, выносимые на защиту.

Практическая ценность.

Апробация.

Публикации.

Структура и объем работы.

1 СХЕМА ПОТОКОВОГО ПРОГРАММИРОВАНИЯ.

1.1 Подход к проведению оценки производительности вычислительной системы

1.1.1 Оптимизация алгоритма.

1.1.2 Производительность на уровне процессора.

1.1.3 Производительность на уровне вычислительного узла.

1.1.4 Производительность системы в целом.161.2 Схема потокового программирования.

1.2.1 Реализация для одного конвейеризованного вычислительного узла.

1.2.2 Реализация для нескольких арифметических узлов.

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

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

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

2.1 Быстрое преобразование Фурье.

2.1.1 Дискретное преобразование Фурье.

2.1.2 Быстрое преобразование Фурье.

2.1.3 Общая схема вычислений и хранения данных.

2.1.4 «Бабочка Фурье» на сопроцессоре.

2.1.5 Реализация БПФ на одном вычислительном узле.

2.2 Оптимальное распределение процессов по вершинам гиперкуба.

2.3 Оценки времени транспонирования матриц на СЭВМ-6.

2.3.1 Общая схема алгоритма.

2.3.2 База индукции.

2.3.3 Шаг индукции.

2.3.4 Основное соотношение.

2.3.5 Некоторые замечания.

2.3.6 Численные результаты.

2.3.7 Оценки для малого количества ВУ.

2.4 Задача обработки данных радара с синтезированной антенной решеткой (ЭАЯ)

2.4.1 Введение.

2.4.2 Модельная задача.

2.4.3 Реальная задача.

2.5 Быстрое преобразование Фурье на макетном модуле с четырьмя процессорами ЦПОС

2.5.1 Быстрое Преобразование Фурье по основанию 4.

2.5.2 Архитектура макетного модуля с четырьмя процессорами ЦПОС-2.

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

2.6 Обзор современных методов фильтрации данных.

2.6.1 Прямое вычисление фильтра.

2.6.2 Фильтрация в области частот.

2.6.3 Схема блочного использования FFT при вычислении фильтра.

2.7 Выводы.

3 ПРОЕКТИРОВАНИЕ РАСШИРЕНИЯ ОБРАБОТКИ СИГНАЛОВ ДЛЯ УНИВЕРСАЛЬНОГО МИКРОПРОЦЕССОРА.

3.1 Описание усовершенствований.

3.1.1 Усовершенствование №1.

3.1.2 Усовершенствование №2.

3.1.3 Усовершенствование №3.

3.1.4 У совершен ство вание №4.

3.2 Оценка производительности предлагаемых архитектур.

3.2.1 Исходная архитектура.

3.2.2 Усовершенствование №1.

3.2.3 Усовершенствование №2.

3.2.4 Усовершенствование №3.

3.3 Другие альтернатив ы.

3.4 Теоретические результаты.

3.5 Архитектура DSP-расширения.

3.5.1 Описание DSP команд.

3.5.2 Режимы работы микропроцессора.

3.5.3 Кэш 2-го уровня.

3.5.4 Пиковая производительность микропроцессора.

3.6 Оценка производительности: данные в памяти.

3.7 Выводы.

4 МЕТОДИКА ИСПОЛЬЗОВАНИЯ ПРОГРАММНЫХ ЭМУЛЯТОРОВ ДЛЯ ОЦЕНОК ПРОИЗВОДИТЕЛЬНОСТИ И ВЕРИФИКАЦИИ ПРОЦЕССОРОВ.

4.1 Работа с долго выполняющимися программами.

4.2 Портирование ОС Linux.

4.3 Подключение виртуальной машины к локальной сети.

4.4 Потактовая модель.

4.5 Выводы.

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

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

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

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

Цель работы (исследования)

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

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

Методы исследования

Исследования имели как теоретическую, так и практическую направленность. Большая часть работы прошла в рамках программы № 15 фундаментальных исследований Президиума РАН "Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий ОЛЮ".

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

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

Направления:

• суперЭВМ, мультипроцессорные ЭВМ, вычислительные узлы;

• расширения универсальных процессоров;

• сопроцессоры и спецпроцессоры.

Конкретные разработки:

• проекты СуперЭВМ-1 и СуперЭВМ-6; вычислительные узлы СЭВМ-1 и СЭВМ-6;

• проект вычислительного узла на базе 4-х ЦГЮС-02;

• «сигнальное расширение» универсального процессора Комдив-64-СМП; модернизация арифметического сопроцессора СЭВМ-6; разработка БШХ)-сопроцессора в составе спецпроцессора К128.

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

Научная новизна работы

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

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

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

• Показана применимость подхода «встречной оптимизации» к задачам трехмерного моделирования и обработки сигналов на процессорах и сопроцессорах СуперЭВМ с распределенной памятью. 7

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

Результаты работы, выносимые на защиту

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

Практически, доказана применимость подхода «встречной оптимизации» для задач трехмерного моделирования и обработки сигналов на процессорах, сопроцессорах СуперЭВМ с распределенной памятью; спроектированы и реализованы с участием автора или под руководством автора программные эмуляторы исследуемых микропроцессоров и сопроцессоров, а также эмулятор вычислительного узла СЭВМ-6. На начальном этапе разработки микропроцессора, сопроцессора или вычислительного узла эмуляторы использовались для проведения оптимизации архитектуры под конкретный класс; для проведения процесса «встречной оптимизации» архитектуры и используемых алгоритмов. На втором этапе, по завершении процесса «встречной оптимизации», архитектура фиксировалась, и проводился анализ выбранных алгоритмов решения данного класса задач. Результаты этого анализа подтверждались прямыми измерениями производительности алгоритмов, путем непосредственно исполнения алгоритмов на эмуляторе.

Наконец, в соответствии с подходом «встречной оптимизации» оценки производительности не проводятся изолированно, а сочетаются с детализацией архитектуры.

Для сопроцессора вещественной арифметики в проекте СЭВМ-6 результатами работы автора на втором этапа были:

• Выбор окончательной архитектуры сопроцессора вещественной арифметики;

• Создание эмулятора сопроцессора вещественной арифметики;

Для расширения универсального процессора Комдив-64-СМП результатами работы автора на втором этапа были:

• Разработка архитектуры расширения обработки сигналов;

• Оценки производительности с подтверждением на эмуляторе для Быстрого Преобразования Фурье и модельных задач.

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

Для МП ЦПОС-02 автором был проведен анализ возможных вариантов архитектуры многопроцессорного вычислительного узла с целью его использования для задач обработки сигналов.

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

Практическая ценность

Автором выделена теоретическая конструкция «схемы Потокового Программирования», которая в настоящий момент активно используется в НИИСИ РАН при разработке новых процессоров.

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

Автором разработана программная модель расширения для обработки сигналов для универсального процессора Комдив-64-СМП.

В рамках проекта СуперЭВМ СЭВМ-6 автором проведена оптимизация архитектуры сопроцессора вещественной арифметики под практические задачи обработки сигналов, в том числе под реальную задачу обработки данных радара с синтезированной антенной решеткой (Synthetic Aperture Radar, SAR).

Апробация

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

Публикации

По теме диссертационной работы опубликовано 8 работ; из них 1 в изданиях по перечню ВАК.

Структура и объем работы

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

В первой главе описывается «схема потокового программирования» процессоров. Первоначально, схема потокового программирования была построена для программирования разрабатываемой в НИИСИ РАН суперЭВМ с вычислительными узлами на основе сопроцессора вещественной арифметики - СЭВМ-6. В дальнейшем схема потокового программирования активно, использовалась при проектировании различных специализированных и универсальных микропроцессоров, разрабатываемых в НИИСИ РАН.

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

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

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

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

Третья глава посвящена разработке расширения цифровой обработки сигналов для универсального 64-разрядного процессора КОМДИВ 64 - СМП. При помощи методов оценки производительности, описанных в предыдущей главе,' удалось увеличить производительность микропроцессора на задачах обработки сигналов до 3 раз.

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

Автор выражает глубокую признательность научному руководителю А.Г.Кушниренко за постановку задач, их полезное обсуждение и внимание к работе. Автор также благодарит команду инженеров и математиков, совместно с которыми проходили работы по созданию сопроцессоров, процессоров, вычислительных модулей и СуперЭВМ в НИИСИ РАН.

4.5 Выводы

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

ЗАКЛЮЧЕНИЕ

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

Для обеспечения оценки производительности был сформулирован в общем виде подход к оценке производительности вычислительной системы. Введена схема потокового программирования, которая широко используется в НИИСИ РАН для разработки процессоров, процессорных модулей, ЭВМ и систем обработки сигналов. Описана ее реализация для различных типов вычислительных систем и ее применение в рамках подхода «встречной оптимизации»: структура алгоритма и архитектура вычислительной системы оптимизируются одновременно для достижения максимальной производительности.

Получены оценки производительности для проекта СуперЭВМ СЭВМ-6 и вычислительного модуля на основе 4-х процессоров ЦПОС-02. Для вычислительного модуля на процессорах ЦПОС-02 оценки производительности позволили выделить ключевые параметры, влияющие на производительность модуля. Для СуперЭВМ СЭВМ-6 эти оценки позволили оптимизировать архитектуру вычислительного узла и выбрать оптимальные параметры коммуникационной среды для- повышения эффективности СуперЭВМ. Для оценки производительности СуперЭВМ в целом приводится, схема распределения вычислительных узлов по вершинам гиперкуба и алгоритм транспонирования матриц с оценки времени транспонирования в зависимости от параметров СуперЭВМ. Разработан эмулятор вычислительного узла СЭВМ-6, который позволил верифицировать.теоретические результаты.

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

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

1. В.Б. Бетелин, С.Г. Бобков, С.А. Зендрикова, А.А. Кравченко, А.Г. Кушниренко, В.К. Николаев "Теоретические оценки эффективности суперЭВМ с распределенной памятью" - М.: "НИИСИ РАН", 2003

2. Лесных А.А., Широков И.А. "Оценки производительности суперЭВМ на основе сопроцессора вещественной арифметики на задачах обработки сигналов" М.: НИИСИ РАН, 2005

3. Кушниренко А.Г., Лебедев Г.В. "Программирование для математиков"1. М.: Наука, 1988

4. Вьюкова В.В., Галатенко В.А., Самборский С.В., Шумаков С.М. "О проблеме оптимизации кода для процессорных архитектур с явным параллелизмом" М.: ИПУ РАН, 2001.

5. Корнеев В.В. "Параллельные вычислительные системы" М.: "Нолидж", 1999.

6. Dongarra J.J., Duff I.S., Sorensen D.C., van der Vorst H.A. "Numerical linear algebra for high-performance computers" Society for Industrial and Applied Mathematics Philadelphia (SIAM), 1998.

7. Kai Hwang, Zhiwei Xu "Scalable parallel computing" McGraw-Hill, 1998.

8. Бахвалов H.C., "Численные методы" M.: Наука, 1973

9. М. R. Schroeder and В. F. Logan, "Colorless Artificial Reverberation", J. Audio Eng. Soc., vol. 9, no. 3, pp. 192-197, July 1961.

10. M. R. Schroeder, "Natural Sounding Artificial Reverberation", J. Audio Eng. Soc., vol. 10, no. 3, pp. 219-223, July 1962.

11. Wen-Chieh Lee, Chung-Han Yang, Chi-Min Liu, Jiun-In Guo "Perceptual Convolution for Reverberation" Convention Paper of Audio Engineering Society, 2003

12. W.G. Gardner, "The virtual acoustic room", MS paper, MIT Media Lab, 1992 (http://alindsay.www.media.mit.edu/papers.html, по состоянию на 01.07.2007).

13. J. Dattorro, "Effect Design Part 1: Reverberator and Other Filters", J. Audio Eng. Soc., vol. 45, pp. 660-684, September 1997.

14. Egelmeers, K.D., Sommen, P.C.W. "A new method for efficient convolution in frequency domain by non-uniform partitioning". In Proceeding EUSIPCO, volume 2, pp 1030-1033, Edinburgh, September 1994.

15. Gardner, W.G. (1995). "Efficient convolution without input-output delay". J. Audio Eng. Soc. 43 (3), 127-136.

16. Steven W. Smith, "The Scientist and Engineer's Guide to Digital Signal Processing", Second Edition, California Technical Publishing (полный текст учебника доступен на сайте http://www.DSPguide.com, по состоянию на 01.07.2007)

17. A.V. Oppenheim and R. W. Schafer, "Digital Signal Processing", Prentice-Hall, Englewood Cliffs, NJ, 1975

18. Christian Muller-Tomfelde, "Time-Varying Filter in non-uniform Block Convolution", Proceedings of the COST G-6 Conference on Digital Audio Effects (DAFX-01), Limerick, Ireland, December 6-8, 2001

19. E. Ferrara, "Fast implementation of LMS adaptive filters", IEEE Trans. On ASSP, vol 28, No. 4, August 1980.

20. Guillermo Garcia, "Optimal Filter Partition for Efficient Convolution with Short Input/Output Delay". AES Convention Paper 5660. Presented at the 113th Convention 2002 October 5-8.

21. McGraph, Lake DSP Pty Ltd., "Method and apparatus for filtering an electronic environment with improved accuracy and efficiency and short flow-through delay". U.S. Patent #5, 502,747, 1996

22. MIPS64™ Architecture For Programmers (http://www.mips.com/ content/Documentation/MIPSDocumentation/ProcessorArchitecture/doclibrary, по состоянию на 01.07.2007)

23. J Hennessy, D. Patterson "Computer Architecture. A Quantitative Approuch" -Third edition, 2003

24. K. Hwang, Z. Xu "Scalable Parallel Computing", 1997

25. H. Cragon "Memory Systems and Pipelined Processors", 1995

26. Лесных A.A., Широков И.А. "Проектирование расширения обработки сигналов для универсального микропроцессора" М.: ФПМ, том 12, выпуск 8, 2006

27. Безруков B.JL, Годунов А.Н., Назаров П.Е., Солдатов В.А. Хоменков И.И. "Введение в ос2000" // сб. статей "Вопросы кибернетики" под ред. чл.-корр. РАН В.Б. Бетелина., Москва 1999

28. Подобаев В.Н. "Разработка поведенческой С-модели 64-х разрядного RISC-микропроцессора КЗ" // Информационная безопасность. Микропроцессоры. Отладка сложных систем под ред. академика РАН В.Б. Бетелина. М.: НИИСИ РАН, 2004.

29. Подобаев В.Н. "Методы отладки RTL-модели процессора КЗ с помощью потактовой поведенческой С-модели" // Автоматика, электроника, микроэлектроника. Сборник научных трудов. М: МИФИ, 2005. С.111-112.

30. Широков И.А. "Быстрое преобразование Фурье на модуле с четырьмя процессорами ЦПОС" М.: НИИСИ РАН, 2005

31. Аряшев С.И., Широков И.А. "Оценки производительности DSP-расширения для процессора КОМДИВ 64 СМП" - М.: НИИСИ РАН, 2005

32. Лесных A.A., Широков И.А. "Покомандная модель проектируемого 64 битного процессора" М.: НИИСИ РАН, 2005

33. Широков И.А. "Обзор современных методов фильтрации данных " М.: НИИСИ РАН, 2005