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

Эта статья слишком полагается на Рекомендации к основные источники. Пожалуйста, улучшите это, добавив вторичные или третичные источники. (Ноябрь 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

АТЛАС

Репозиторий	github.com/ математический атлас/ математический атлас
Тип	Библиотека программного обеспечения
Лицензия	Лицензия BSD
Интернет сайт	математический атлас.sourceforge.сеть

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

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

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

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

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

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

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

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

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

${displaystyle mathbf {y} leftarrow alpha Amathbf {x} + eta mathbf {y}!}$

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

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

${displaystyle Cleftarrow alpha AB + eta C!}$

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

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

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

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 Amathbf {x} + eta mathbf {y}!}$

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

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

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

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

Уровень 3 BLAS

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

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

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

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

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

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

Если так,

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

Если не,

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

Фактическое решение принимается с помощью простого эвристический который проверяет наличие "тонких футляров".

Край кеша

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

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

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

ЛАПАК

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

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

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

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

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

Рекомендации

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

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