Автоматически настраиваемое программное обеспечение для линейной алгебры

Автоматически настраиваемое программное обеспечение для линейной алгебры

Стабильная версия	3.10.3 / 28 июля 2016 г ( 28 июля 2016 )
Репозиторий	github .с /math-атлас /math-атлас
Написано в	С , ФОРТРАН 77
Тип	Библиотека программного обеспечения
Лицензия	Лицензия БСД
Веб-сайт	математический атлас .sourceforge .сеть

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

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 содержит векторные операции вида

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

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

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

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

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

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

$C\leftarrow \alpha AB+\beta C\!$

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

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

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

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

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

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

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

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

Все процедуры в BLAS ATLAS уровня 2 построены на основе двух ядер BLAS уровня 2:

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

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

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

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

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

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

Уровень 3 БЛАС

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

$O(n^{3})$ операции против. $O(n^{2})$ данные

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

Может ли он позволить себе копирование?

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

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

Если так,

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

Если не,

• Используйте версию nocopy
• Не делайте предположений о шаге матриц 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 ) $M\cdot p+NB\cdot Kp+NB\cdot NB$.Если это не удается, он пытается $2\cdot Kp\cdot NB+NB\cdot NB$.(Если это не удается, используется версия GEMM без копирования, но этот случай маловероятен при разумном выборе края кэша.) Kp является функцией края кэша и NB .

ЛАПАК

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

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

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

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

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

Внешние ссылки

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