Лекция по "Архитектуре ЭВМ"

В то время широкое распространение  получил синтетический тест Dhrystone, который позволял оценивать эффективность процессоров и компиляторов с языка C для программ нечисловой обработки. Он представлял собой тестовую смесь, 53% которой составляли операторы присваивания, 32% - операторы управления и 15% - вызовы функций. Это был очень короткий тест: общее число команд равнялось 100. Скорость выполнения программы из этих 100 команд измерялась в Dhrystone в секунду. Быстродействие VAX 11/780 на этом синтетическом тесте составляло 1757Dhrystone в секунду. Таким образом 1MIPS равен 1757 Dhrystone в секунду.

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

Третье определение MIPS связано  с IBM RS/6000 MIPS. Дело в том, что ряд  производителей и пользователей (последователей фирмы IBM) предпочитают сравнивать производительность своих компьютеров с производительностью  современных компьютеров IBM, а не со старой машиной компании DEC. Соотношение  между VAX MIPS и RS/6000 MIPS никогда широко не публиковались, но 1 RS/6000 MIPS примерно равен 1.6 VAX 11/780 MIPS.

MFLOPS

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

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

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

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

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

Решение обеих проблем  заключается в том, чтобы взять "каноническое" или "нормализованное" число операций с плавающей точкой из исходного текста программы и  затем поделить его на время выполнения. На рисунке 2.1 показано, каким образом  авторы тестового пакета "Ливерморские циклы", о котором речь пойдет ниже, вычисляют для программы количество нормализованных операций с плавающей точкой в соответствии с операциями, действительно находящимися в ее исходном тексте. Таким образом, рейтинг реальных MFLOPS отличается от рейтинга нормализованных MFLOPS, который часто приводится в литературе по суперкомпьютерам.

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

Наиболее часто MFLOPS, как  единица измерения производительности, используется при проведении контрольных  испытаний на тестовых пакетах "Ливерморские циклы" и LINPACK.

Ливерморские циклы - это набор фрагментов фортран-программ, каждый из которых взят из реальных программных систем, эксплуатируемых в Ливерморской национальной лаборатории им.Лоуренса (США). Обычно при проведении испытаний используется либо малый набор из 14 циклов, либо большой набор из 24 циклов.

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

На векторной машине производительность зависит не только от элементной базы, но и от характера самого алгоритма, т.е. коэффициента векторизуемости. Среди Ливерморских циклов коэффициент векторизуемости колеблется от 0 до 100%, что еще раз подтверждает их ценность для оценки производительности векторных архитектур. Кроме характера алгоритма, на коэффициент векторизуемости влияет и качество векторизатора, встроенного в компилятор.

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

LINPACK - это пакет фортран-программ для решения систем линейных алгебраических уравнений. Целью создания LINPACK отнюдь не было измерение производительности. Алгоритмы линейной алгебры весьма широко используются в самых разных задачах, и поэтому измерение производительности на LINPACK представляют интерес для многих пользователей. Сведения о производительности различных машин на пакете LINPACK публикуются сотрудником Аргоннской национальной лаборатории (США) Дж. Донгаррой и периодически обновляются.

В основе алгоритмов действующего варианта LINPACK лежит метод декомпозиции. Исходная матрица размером 100х100 элементов (в последнем варианте размером 1000х1000) сначала представляется в виде произведения двух матриц стандартной структуры, над которыми затем выполняется  собственно алгоритм нахождения решения. Подпрограммы, входящие в LINPACK, структурированы. В стандартном варианте LINPACK выделен  внутренний уровень базовых подпрограмм, каждая из которых выполняет элементарную операцию над векторами. Набор базовых  подпрограмм называется BLAS (Basic Linear Algebra Subprograms). Например, в BLAS входят две простые подпрограммы SAXPY (умножение вектора на скаляр и сложение векторов) и SDOT (скалярное произведение векторов). Все операции выполняются над числами с плавающей точкой, представленными с двойной точностью. Результат измеряется в MFLOPS.

Использование результатов  работы тестового пакета LINPACK с двойной  точностью как основы для демонстрации рейтинга MFLOPS стало общепринятой практикой  в компьютерной промышленности. При  этом следует помнить, что при  использовании исходной матрицы  размером 100х100, она полностью может  размещаться в кэш-памяти емкостью, например, 1 Мбайт. Если при проведении испытаний используется матрица  размером 1000х1000, то емкости такого кэша уже недостаточно и некоторые обращения к памяти будут ускоряться благодаря наличию такого кэша, другие же будут приводить к промахам и потребуют большего времени на обработку обращений к памяти. Для многопроцессорных систем также имеются параллельные версии LINPACK и такие системы часто показывают линейное увеличение производительности с ростом числа процессоров.

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

10. Законы Амдала и Густафсона. Теоретический и реальный рост производительности при распараллеливании вычислений. Тесты оценки производительности.

Законы Амдала и Густафсона ориентированы на крупнозернистый параллелизм.  Допустим,  имеется в наличии вычислительная система с неограниченными вычислительными ресурсами  (в которой количество процессоров неограниченно).  Как поведут себя программы в этой системе?  Ускорятся ли они в неограниченное количество раз?  Разумеется,  нет!  Скорость работы простейшей однопоточной программы не изменится,  так как она не использует параллелизм высокого уровня.  Её вычислительная нагрузка ляжет исключительно на один из процессоров.  В отличие от микроуровневого параллелизма,  который обеспечивается самим процессором, или в отличие от параллелизма уровня инструкций, где участия программиста не требуется (за исключением SIMD),  привлечение к вычислениям нескольких процессоров требует существенной модификации алгоритма.  Фактически требование дальнейшего повышения производительности вычислений вынуждает применять новые методики программирования, такие как векторное процессирование  (например, SSE),  многопоточное программирование (например, MPI)  и т.д.  Отметим,  что классические языки программирования высокого уровня (такие, как C++) ориентированы исключительно на класс SISD.

Итак, программист изменил  алгоритм и создал многопоточный  код (например, при помощи потоков POSIX). Приведёт ли это к неограниченному  росту производительности? Введём в  рассмотрение степень параллелизма программы – D(t) – число процессоров, участвующих в исполнении программы в момент времени t. При старте программы D(0)=1. Далее программа

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

Введём в рассмотрение T(n) – время исполнения программы на n  процессорах. T(n)<T(1), если параллельная версия алгоритма эффективна. T(n)>T(1),  если накладные расходы (издержки) реализации параллельной версии алгоритма чрезмерно велики. Внимание: за T(1)  взято не время выполнения многопоточной программы на одном процессоре,  а время выполнения однопоточной программы. Тогда ускорение за счёт параллельного выполнения составит S(n) = T(1) / T(n).

С экономической точки  зрения интерес представляет ускорение  в пересчёте на один процессор  – эффективность системы из n процессоров E(n) = S(n) / n.

В идеальном случае ускорение  линейно от n.  Такой алгоритм обладает свойством масштабируемости  (возможностью ускорения вычислений пропорционально числу процессоров).  Но на практике масштабируемый алгоритм имеет несколько худшие показатели из-за накладных расходов на поддержку многопроцессорных вычислений. Кроме того,  параметр n  масштабируемого алгоритма должен быть согласован с количеством процессоров в вычислительной системе.  Необходимо также учитывать и текущую загруженность процессоров другими задачами. Особое внимание заслуживает случай S(n) > n. Изначально может показаться, что такого не может быть. Однако примеры такого успешного распараллеливания есть! Вопрос лишь в том,  как квалифицированно разбить исходную задачу на подзадачи. Требования исходной задачи могут превосходить возможности эксплуатируемого процессора по любому из его ресурсов (чаще всего это кеши различных уровней, буфер BTB, буфер TLB). После разбиения на один процессор попадает задача меньшего объёма,  и,  соответственно,  требования к объёму ресурсов процессора сокращаются.  При преодолении таких порогов возникает суперлинейное ускорение.  Внимание:  организация кода/данных должна обеспечивать максимальную степень локальности кода/данных  (иначе ни линейного,  ни тем более суперлинейного ускорения достичь не удастся).

Закон Амдала: Любая многопоточная программа содержит последовательную часть. Это ввод/вывод, менеджмент потоков,  точки синхронизации и т.п. Обозначим долю последовательной части за f. Тогда доля параллельной части будет 1-f. Амдал в 1967  году рассмотрел ускорение такой программы на n  процессорах,  исходя из предположения линейного ускорения параллельной части,  и получил n/(1+(n–1)×f).  При неограниченном числе процессоров ускорение составит всего лишь 1/f.

Если,  например,  доля последовательной части 20%,  то теоретически невозможно получить ускорение вычислений более чем в пять раз! Таким  образом, превалирующую роль играет доля f, а вовсе не число процессоров!

Оптимистичный взгляд на закон  Амдала даёт закон Густафсона-Барсиса. Вместо вопроса об ускорении на n процессорах рассмотрим вопрос о замедлении вычислений при переходе на один процессор. Аналогично за f  примем долю последовательной части программы. Тогда получим закон масштабируемого ускорения, и S(n)=n+(1–n)×f.

Теперь графики S(f)  демонстрируют совершенно иную картину:  линейное ускорение в зависимости от числа процессоров. Т.е. законы Амдала и Густафсона в идентичных условиях дают различные значения ускорения.  Где же ошибка?  Каковы области применения этих законов?