Автоматически настраиваемое программное обеспечение линейной алгебры - Automatically Tuned Linear Algebra Software

АТЛАС

Репозиторий
Тип	Программная библиотека
Лицензия	Лицензия BSD
Интернет сайт	математический атлас .sourceforge .net

Автоматически настраиваемое программное обеспечение линейной алгебры ( ATLAS ) - это программная библиотека для линейной алгебры . Он предоставляет зрелую реализацию API-интерфейсов BLAS с открытым исходным кодом для C и Fortran77 .

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

ATLAS работает в большинстве Unix- подобных операционных систем и в Microsoft Windows (с использованием Cygwin ). Он выпущен под лицензией в стиле BSD без оговорок о рекламе , и его могут использовать многие известные математические приложения, включая MATLAB , Mathematica , Scilab , SageMath и некоторые сборки GNU Octave .

Функциональность

ATLAS предоставляет полную реализацию API-интерфейсов BLAS, а также некоторые дополнительные функции из LAPACK , библиотеки более высокого уровня, построенной на основе BLAS. В BLAS функциональность разделена на три группы, называемые уровнями 1, 2 и 3.

• Уровень 1 содержит векторные операции вида

${\ Displaystyle \ mathbf {y} \ leftarrow \ alpha \ mathbf {x} + \ mathbf {y} \!}$

а также скалярные скалярные произведения и векторные нормы , среди прочего.

• Уровень 2 содержит матрично-векторные операции вида

${\ displaystyle \ mathbf {y} \ leftarrow \ alpha A \ mathbf {x} + \ beta \ mathbf {y} \!}$

а также решения для с будучи треугольной формы, между прочим.${\ Displaystyle Т \ mathbf {x} = \ mathbf {y}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle T}$

• Уровень 3 содержит матрично-матричные операции, такие как широко используемая операция общего матричного умножения (GEMM).

${\ Displaystyle C \ leftarrow \ альфа AB + \ бета C \!}$

а также решение для треугольных матриц , среди прочего.${\ displaystyle B \ leftarrow \ alpha T ^ {- 1} B}$${\ displaystyle T}$

Оптимизационный подход

Оптимизация подход называется Автоматизированная Эмпирические Оптимизация программного обеспечения (AEOS), в котором определены четыре основных подхода к компьютерной вспомогательной оптимизации которой ATLAS использует три:

1. Параметризация - поиск в пространстве параметров функции, используемом для определения коэффициента блокировки, границы кеша и т. Д.
2. Множественная реализация - поиск различных подходов к реализации одной и той же функции, например, поддержки SSE до того, как встроенные функции сделали их доступными в коде C
3. Генерация кода - программы, которые пишут программы с учетом имеющихся у них знаний о том, что обеспечит наилучшую производительность системы.

• Оптимизация BLAS уровня 1 использует параметризацию и множественную реализацию

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

• Оптимизация уровня 2 BLAS использует параметризацию и множественную реализацию

С данными и операциями для выполнения функция обычно ограничена полосой пропускания для памяти, и, таким образом, нет особых возможностей для оптимизации.${\ displaystyle N ^ {2}}$${\ displaystyle N ^ {2}}$

Все подпрограммы в BLAS уровня 2 ATLAS построены из двух ядер BLAS уровня 2:

• • GEMV - обновление матрицы на вектор умножения:

${\ displaystyle \ mathbf {y} \ leftarrow \ alpha A \ mathbf {x} + \ beta \ mathbf {y} \!}$

• • GER - общее обновление ранга 1 из внешнего продукта:

${\ displaystyle A \ leftarrow \ alpha \ mathbf {x} \ mathbf {y} ^ {T} + A \!}$

• Оптимизация уровня 3 BLAS использует генерацию кода и два других метода.

Поскольку у нас есть операции только с данными, есть много возможностей для оптимизации${\ displaystyle N ^ {3}}$${\ displaystyle N ^ {2}}$

Уровень 3 BLAS

Большая часть BLAS уровня 3 является производной от GEMM , поэтому это основная цель оптимизации.

${\ Displaystyle О (п ^ {3})}$операции против данных${\ Displaystyle О (п ^ {2})}$

Интуиция о том, что операции будут преобладать над доступом к данным, работает только для примерно квадратных матриц. Реальной мерой должно быть отношение площади поверхности к объему. Разница становится важной для очень неквадратных матриц. ${\ Displaystyle п ^ {3}}$${\ Displaystyle п ^ {2}}$

Может ли копировать?

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

Итак, первый вопрос, с которым сталкивается GEMM, - может ли он позволить себе копирование входных данных?

Если так,

• Поместите в основной формат блока с хорошим выравниванием
• Воспользуйтесь преимуществами пользовательских ядер и очистки
• Обработка случаев транспонирования с копией: преобразование всего в TN (транспонирование - без транспонирования)
• Разберитесь с α в копии

Если не,

• Используйте версию без копирования
• Не делайте предположений о скорости матрицы A и B в памяти
• Явная обработка всех случаев транспонирования
• Нет гарантии согласования данных
• Поддержка конкретного кода α
• Есть риск проблем с TLB , плохих успехов и т. Д.

Фактическое решение принимается с помощью простой эвристики, которая проверяет наличие «скудных случаев».

Край кеша

Для блокировки кэша 2-го уровня используется единственный параметр края кэша. На высоком уровне выберите порядок прохождения блоков: ijk, jik, ikj, jki, kij, kji . Это не обязательно должен быть тот же порядок, что и продукт в пределах блока.

Обычно выбираются заказы ijk или jik . Для JIK идеальной ситуация будет скопировать A и NB широкой панель B . Для IJK поменять роль A и B .

Выбор большего из M или N для внешнего цикла уменьшает занимаемый копией размер. Но для больших K ATLAS даже не выделяет такой большой объем памяти. Вместо этого он определяет параметр Kp , чтобы наилучшим образом использовать кэш L2. Панели ограничены длиной Kp . Сначала он пытается выделить (в случае jik ) . Если это не удается, он пытается . (Если это не удается, используется версия GEMM без копирования, но этот случай маловероятен для разумного выбора края кеша.) Kp является функцией края кеша и NB . ${\ Displaystyle M \ cdot p + NB \ cdot Kp + NB \ cdot NB}$${\ Displaystyle 2 \ cdot Kp \ cdot NB + NB \ cdot NB}$

ЛАПАК

При интеграции ATLAS BLAS с LAPACK важным фактором является выбор коэффициента блокировки для LAPACK. Если коэффициент блокировки ATLAS достаточно мал, коэффициент блокировки LAPACK может быть установлен в соответствии с коэффициентом блокировки ATLAS.

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

Необходимость установки

Установка ATLAS на конкретную платформу - сложный процесс, который обычно выполняется поставщиком системы или местным экспертом и делается доступным для более широкой аудитории.

Для многих систем доступны архитектурные параметры по умолчанию; по сути, это сохраненные поиски плюс результаты ручной настройки. Если параметры по умолчанию работают, они, вероятно, получат на 10-15% большую производительность, чем поиск установки. В таких системах процесс установки значительно упрощается.

Ссылки

внешняя ссылка

• Автоматически настраиваемое программное обеспечение линейной алгебры на SourceForge.net
• Вклад пользователей в ATLAS
• Совместное руководство по разработке ATLAS
• В FAQ есть ссылки на Краткое справочное руководство по BLAS и Краткое справочное руководство по ATLAS LAPACK API.
• Microsoft Visual C ++ Howto для ATLAS