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

• Широков, Илья Андреевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Широков, Илья Андреевич

ВВЕДЕНИЕ.

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

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

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

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

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

Апробация.

Публикации.

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

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 раза. Для верификации результатов теоретического анализа под руководством автора был создан программный эмулятор проектируемого процессора покомандного уровня. Для выбранного при разработке микропроцессора маршрута проектирования, использование эмулятора является основным инструментом отладки, тестирования и доводки процессора.

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

Список литературы диссертационного исследования кандидат физико-математических наук Широков, Илья Андреевич, 2010 год

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