Не будет преувеличением сказать, что эра многоядерных процессоров для персональных компьютеров наступила. Конечно, все уже давно привыкли к тому, что с помощью ПК можно путешествовать по Интернету и одновременно слушать музыку, поэтому для рядового пользователя переход на двухъядерный процессор означает только увеличение производительности, а вот для индустрии ПО — это целая революция. Уже существующие программы в большинстве своем не могут воспользоваться теми преимуществами, которые дает второе ядро в системе. Разработка новых версий продуктов, где исправлен этот недостаток, требует принципиально иных подходов. Так как же быть?
На самом деле все не так страшно. В этой статье рассказывается о том, как можно оптимизировать уже имеющееся приложение так, чтобы получить максимум производительности для многоядерной архитектуры.
В качестве примера рассмотрим программу, которая является классической задачей для любого программиста, — умножение двух матриц (см. одноименную врезку). Сама программа приведена в листинге 1. Она написана на языке С++ в среде программирования MS Visual Studio 2005.
В приведенном примере мы устанавливаем размер матрицы как константу и с помощью функции FillMatrix задаем значения паре исходных матриц. После этого функция MatrixMultiply вычисляет матричное произведение. На самом деле нам не так важно, как организованы вычисления с точки зрения математики, лишь бы изменения, вносимые в код, не влияли на полученный результат. Откомпилируем программу и запустим ее. После окончания работы будет выдан результат — время, затраченное на умножение двух матриц. Это наш стартовый ориентир, посмотрим, как его можно улучшить.
Профилирование
Процесс сбора характеристик работы программы, среди которых есть как простые вроде времени выполнения всей программы или ее отдельных модулей, так и более сложные, например данные о работе кэш-памяти процессора, называется профилированием, а программа, осуществляющая сбор подобных характеристик о приложении, — профилировщиком. Она работает так: исследуемое приложение запускается на выполнение и одновременно средствами профилировщика собирается информация о запуске подпрограмм, времени их работы, системных событиях (например, об обращениях к памяти и внешним устройствам, об ошибках алгоритмов предсказания ветвлений процессора для выборки данных в кэш) и т.д. Подобные инструментальные средства анализа программы помогают понять ее поведение, найти в ней узкие места — те фрагменты кода, скорость выполнения которых можно повысить, чтобы увеличить производительность всего приложения. Профилировщиков существует великое множество, они различаются прежде всего поддерживаемыми языками программирования и возможностями. Одни из наиболее функциональных разработаны как раз производителями процессоров, компаниями Intel и AMD — Intel VTune Performance Analyzer и AMD CodeAnalyst соответственно. Кроме того, и в компилятор GCC также входит программа-профилировщик — gprof. Сравнивать эти решения между собой напрямую нельзя, уж больно они разные, но здесь мы рассмотрим, что же у них общего.
Профилировщик AMD CodeAnalyst можно бесплатно загрузить с сайта компании-разработчика, предварительно зарегистрировавшись. Приложение Intel VTune — коммерческое. Оно гораздо более функциональное, однако ориентированное исключительно на процессоры Intel. И это понятно, ведь разработка такого приложения требует знания архитектуры процессора.
Сначала нам нужно собрать информацию о работе программы. В CodeAnalyst это делается так: после запуска профилировщика появится окно с названием Welcome to CodeAnalyst, в котором следует нажать на кнопку Express Profile!. Затем нам надо указать путь (Launch) к исследуемой программе (имеется в виду откомпилированный exe-файл, по умолчанию MS Visual Studio 2005 создает его в папке Debug). В раскрывающемся списке, в группе с названием Profile configuration (Конфигурация профилировщика), перечислено, что именно будет исследованно в работе приложения: Current event-based profile (подсчет количества системных вызовов во время выполнения исследуемого приложения) и Investigate L2 cache access (обращения к кэш-памяти процессора второго уровня и работа с памятью). Конечно, есть и другие характеристики, однако мы рассмотрим именно эти. Выполним их по порядку. После нажатия кнопки OK через некоторое время перед нами появятся результаты: таблица, в первой колонке которой будут названия модулей (Module Name), а во второй — условное время их работы (CPU Cycles). Дважды щелкнем мышью на исследуемом приложении (первый пункт в списке), и в новом окне появится таблица со временем работы функций нашей программы. Здесь уже наглядно видно, сколько работала каждая из них, и понятно, какие именно участки кода следует оптимизировать.
При повторном выборе первой по счету функции, MatrixMultiply, возникнет окно с программным кодом и временной характеристикой конкретных строк программы. Аналогично проведем выборку данных и для конфигурации Investigate L2 cache access. Проведя все те же манипуляции до появления окна с функцией MatrixMultiply, увидим результаты, изображенные на рис. 2.
Выделим строку “result[i][j] = ...“ и посмотрим на диаграмму на рис. 2. Столбец красного цвета — это общее количество обращений к памяти, а черного — промахи, т.е. результат ситуации, когда необходимых данных в кэше процессора не оказывалось и возникала вынужденная задержка в его работе из-за ожидания необходимых значений из оперативной памяти. Как известно, транзакция процессора с ОЗУ занимает больше времени, чем транзакция с его собственной кэш-памятью, и потому, если нам удастся снизить этот показатель, мы сможем существенно повысить производительность рассматриваемой программы.
Итак, еще раз вернемся к нашему примеру. Чтобы понять, почему же в цикле, где умножаются матрицы, так неэффективно используется память, нужно вспомнить, как работа с ней реализована в языках Си/C++ (см. врезку «Эффективная работа с памятью»).
Исправить это просто — достаточно поменять местами в функции MatrixMultiply два оператора for, как показано в листинге 2.
Результат налицо: время работы программы уменьшилось почти вдвое. Если запустить Investigate L2 cache access еще раз, то значительные изменения нас ждут и там: количество ошибок выборки данных в кэш существенно уменьшится, чем и объясняется рост быстродействия.
Теперь рассмотрим, какие возможности нам предоставляет Intel VTune Performance Analyzer. Для изучения базовой функциональности необходимо воспользоваться мастером Quick Performance Analysis Wizard (окно Easy Start или меню File • New Project), а затем указать путь к exe-файлу в поле Application To Launch.
Стандарт OpenMP
Итак, программа умножения матриц оптимизирована. Но остается вопрос: возрастет ли производительность при переходе к двухъядерным процессорам? А к четырехъядерным? Ответ — нет, поскольку реализованная программа выполняется в рамках одного потока команд, и значит, несколько процессоров не смогут разделить эту работу между собой. Все вычисления придется выполнять одному процессорному ядру, в то время как остальные доступные ядра будут простаивать. Налицо неэффективное использование вычислительных ресурсов! Выход из ситуации очевиден: необходимо каким-либо корректным способом разделить работу между процессорными ядрами, т.е. сделать так, чтобы потоки команд на различных ядрах не конфликтовали между собой.
Параллельное программирование как отдельная ветвь в разработке программного обеспечения начало развиваться еще в 60-х годах прошлого века. Разработка параллельных, иными словами допускающих одновременное выполнение на нескольких вычислителях, программ обычно более сложна по сравнению с разработкой последовательных. Однако за прошедшие годы было создано множество самых разнообразных средств, призванных помочь программисту преодолеть сложности, возникающие при написании подобных приложений. Одной из наиболее популярных технологий создания программ для многопроцессорных/многоядерных компьютеров (а с точки зрения прикладного программиста это одно и то же, здесь основной признак — общая оперативная память) является OpenMP.
Суть ее состоит в том, что в текст готовой последовательной программы нужно вставлять указания компилятору — прагмы, чтобы сообщить ему, как разделить работу между вычислительными ядрами. Прагмы в OpenMP — это директивы компилятору вида #pragma omp <директива> [раздел, ...]. Если подать код с такими директивами на вход компилятору, не поддерживающему стандарт OpenMP, то он просто проигнорирует их и создаст последовательный код. Кроме того, стандарт OpenMP предоставляет программисту механизмы параллельных секций и переменных окружения. Реализации стандарта доступны для языков Си, С++, Фортран на платформах Windows/Linux.
Как же работает OpenMP? Вся программа делится на последовательные и параллельные участки. В момент запуска порождается основной поток (его иногда еще называют «мастер-поток» и присваивают ему номер нуль), в рамках которого будут выполнены все последовательные участки кода. Когда работа программы доходит до параллельной области, основной поток порождает необходимое количество дополнительных, которые запускаются параллельно на различных процессорах. По окончании параллельной секции основной поток ожидает завершения остальных, и дальнейшие действия выполняет только он. Конечно, такая организация работы требует сложной логики синхронизации потоков выполнения и разграничения доступа к переменным, но здесь мы рассмотрим только базовые функции.
Возможность работы с OpenMP появилась в инструментальных средствах компании Microsoft только в выпуске 2005: Visual Studio 2005, версии Professional и Team System, поддерживает OpenMP 2.0. Полностью удовлетворяют этому стандарту, а также содержат отдельные расширения компиляторы языков С++ и Фортран компании Intel. Кроме того, последние версии компилятора GCC поддерживают OpenMP.
Проведем оптимизацию нашего приложения в среде MS Visual C++ 2005. Прежде всего следует указать компилятору, что необходимо включить поддержку OpenMP, иначе все прагмы будут просто проигнорированы. Для этого в меню Project • Properties нужно выбрать Configuration Properties • C/C++ • Language и для пункта OpenMP Support (поддержка OpenMP) указать Yes (/openmp). В начало текста программы добавим директиву #include
Директива #pragma omp parallel for указывает, что это инструкция OpenMP, задающая параллельную секцию, а именно параллельный оператор for. Итак, программа для многоядерной системы готова. Просто, не правда ли? Когда выполнение программы дойдет до данного места, то создадутся дополнительные потоки. Это справедливо для многоядерной системы, а на компьютере с одним процессором программа будет выполняться в один поток, так же как и прежде. Теоретически быстродействие на данном участке должно возрасти вдвое для двухъядерного процессора, однако на практике такой прирост недостижим из-за различных факторов, в частности из-за издержек на порождение потоков и повышенной нагрузки на шину памяти. Кроме того, нужно учитывать, что мы оптимизировали только один цикл во всей программе, поэтому можно говорить о приросте быстродействия всего приложения только тогда, когда оценивается доля времени работы этого цикла в общем времени выполнения.
В случае использования компилятора Intel C++ Compiler 9 есть два варианта: командная строка и интеграция в MS Visual Studio. Если выбрать первый, то команда будет выглядеть, например, так:
icl.exe /Qopenmp optimization_sample.cpp.
Для случая с Visual Studio сначала нужно выполнить команду Project • Convert to use Intel (R) C++ Project System (Конвертировать для использования системы проектов Intel), a затем в меню Project • Properties в пункте Configuration Properties • C/C++ • Command Line нужно добавить поддержку OpenMP, дописав /Qopenmp. В результате компилятор выведет информацию об успешном распараллеливании кода.
Рассмотрим, как еще можно использовать OpenMP, а именно механизм параллельных секций (листинг 4).
Здесь директива #pragma omp parallel sections указывает компилятору, что следующие секции следует выполнять параллельно, причем каждая из них начинается с #pragma omp section. Конечно, для нашей задачи этот вариант кажется несколько надуманным, однако очевидно, что такой подход к организации многопоточных вычислений является более общим, поскольку в секциях можно производить совершенно не связанные между собой вычисления.
Конечно, возможности OpenMP гораздо шире. В настоящее время уже принят стандарт OpenMP 2.5, познакомиться с которым можно по адресу www.openmp.org.
Умножение двух матриц
Матрица — это двумерный массив чисел. Мы будем рассматривать квадратные матрицы, т.е. такие, в которых количество чисел по горизонтали и вертикали совпадает. Если у нас есть две матрицы A и B одинакового размера, то, умножив одну на другую, мы получим матрицу C того же размера. Любой элемент матрицы С, стоящий на пересечении строки с номером i и столбца с номером j, вычисляется как сумма всех произведений элементов строки i матрицы A на элементы столбца j матрицы B. Другими словами, С[i][j] = A[i][0].B[0][j] + A[i][1].B[1][j] + A[i][2].B[2][j] + ... и т.д.
Эффективная работа с памятью
Вся память компьютера линейна, т.е. ее можно представить в виде списка последовательно пронумерованных элементов. Чтобы получить значение из какой-либо ячейки памяти, надо знать ее номер. Матрица — двумерный массив, и значит, ее нельзя записать в память компьютера в том виде, в каком она изображена на бумаге. Однако матрицу можно «разрезать» по строкам и поставить эти «полоски» одну за другой, чтобы получить линейное представление. В таком случае говорят, что матрицы, реализованные средствами языков Си/С++, размещаются в памяти по строкам. Но так бывает не всегда, например, в языке Фортран массивы размещаются по столбцам.
А теперь представим, как работать с такой структурой. Пусть программа обращается к элементу с номером (i,j), т.е. к тому, что находится на пересечении строки i со столбцом j. Прочитать следующий элемент из этой же строки (i+1,j) можно достаточно быстро, ведь в памяти они соседи. А вот если мы обратимся к следующему элементу из столбца j (i,j+1), то придется потратить гораздо больше времени, ведь данный элемент удален от исходного, он находится в следующей «полоске». А алгоритмы выборки данных в кэш процессора как раз и настроены на чтение последовательных значений, поэтому доступ к «дальнему» элементу приведет к тому, что нужных данных в кэше не окажется и процессор вынужден будет простаивать, ожидая их из оперативной памяти.