Стабильная версия | 3.8.0 / 12 ноября 2017 г.; 2 года назад (2017-11-12) |
---|---|
Написано на | в зависимости от реализации |
Платформа | Кросс-платформенность |
Тип | Библиотека |
Веб-сайт | www.netlib.org / blas / |
Подпрограммы базовой линейной алгебры (BLAS ) - это спецификация, которая предписывает набор подпрограммы уровня для выполнения общих операций линейной алгебры, таких как векторное сложение, скалярное умножение, скалярные произведения, линейные комбинации и умножение матриц. Это де-факто стандартные низкоуровневые процедуры для библиотек линейной алгебры; подпрограммы имеют привязки как для C («интерфейс CBLAS»), так и для Fortran («интерфейс BLAS»). Хотя спецификация BLAS является общей, реализации BLAS часто оптимизированы для скорости на конкретном компьютере, поэтому их использование может дать существенные преимущества в производительности. Реализации BLAS будут использовать преимущества специального оборудования с плавающей запятой, такого как векторные регистры или инструкции SIMD.
Она возникла как библиотека Fortran в 1979 году, а ее интерфейс был стандартизирован Форумом BLAS Technical (BLAST), последний отчет которого можно найти на веб-сайте netlib. Эта библиотека Fortran известна как эталонная реализация (иногда ошибочно называемая библиотекой BLAS) и не оптимизирована для скорости, но находится в общественном достоянии.
Большинство библиотек, которые предлагают процедуры линейной алгебры соответствуют интерфейсу BLAS, что позволяет пользователям библиотеки разрабатывать программы, не зависящие от используемой библиотеки BLAS. Примеры библиотек BLAS включают: AMD Core Math Library (ACML), Arm Performance Libraries, ATLAS, Intel Math Kernel Library (MKL) и OpenBLAS. ACML больше не поддерживается его производителем. ATLAS - это переносимая библиотека, которая автоматически оптимизируется для произвольной архитектуры. MKL - это бесплатная и проприетарная библиотека поставщика, оптимизированная для x86 и x86-64 с упором на производительность процессоров Intel. OpenBLAS - это библиотека с открытым исходным кодом, оптимизированная вручную для многих популярных архитектур. Тесты LINPACK в значительной степени полагаются на процедуру BLAS gemm
для измерения производительности.
Многие числовые программные приложения используют BLAS-совместимые библиотеки для выполнения вычислений линейной алгебры, включая Armadillo, LAPACK, LINPACK, GNU Octave, Mathematica, MATLAB, NumPy,R и Julia.
С появлением числового программирования, сложные библиотеки подпрограмм стали полезными. Эти библиотеки будут содержать подпрограммы для общих математических операций высокого уровня, таких как поиск корня, обращение матриц и решение систем уравнений. Выбранный язык был FORTRAN. Самой известной библиотекой численного программирования была IBM (SSP). Эти библиотеки подпрограмм позволили программистам сосредоточиться на своих конкретных проблемах и избежать повторной реализации хорошо известных алгоритмов. Библиотечные подпрограммы также были бы лучше, чем обычные реализации; матричные алгоритмы, например, могут использовать полное вращение для повышения числовой точности. Библиотечные подпрограммы также будут иметь более эффективные подпрограммы. Например, библиотека может включать программу для решения верхней треугольной матрицы. Библиотеки будут включать версии некоторых алгоритмов с одинарной и двойной точностью.
Первоначально эти подпрограммы использовали жестко запрограммированные циклы для своих низкоуровневых операций. Например, если подпрограмме необходимо выполнить матричное умножение, то подпрограмма будет иметь три вложенных цикла. В программах линейной алгебры есть много общих операций низкого уровня (так называемые операции «ядра», не относящиеся к операционным системам ). Между 1973 и 1977 годами было выявлено несколько из этих операций ядра. Эти операции ядра стали определенными подпрограммами, которые могли вызывать математические библиотеки. Вызовы ядра имели преимущества по сравнению с жестко запрограммированными циклами: подпрограмма библиотеки была бы более читаемой, было бы меньше шансов на появление ошибок, а реализацию ядра можно было бы оптимизировать по скорости. Спецификация для этих операций ядра с использованием скаляров и векторов, подпрограмм базовой линейной алгебры (BLAS) уровня 1, была опубликована в 1979 году. BLAS использовался для реализации библиотеки подпрограмм линейной алгебры. LINPACK.
Абстракция BLAS допускает настройку для достижения высокой производительности. Например, LINPACK - это библиотека общего назначения, которую можно использовать на многих разных машинах без изменений. LINPACK может использовать общую версию BLAS. Для повышения производительности разные машины могут использовать адаптированные версии BLAS. По мере того, как компьютерные архитектуры становились более сложными, появились векторные машины. BLAS для векторной машины может использовать быстрые векторные операции машины. (Хотя векторные процессоры в конечном итоге перестали пользоваться популярностью, векторные инструкции в современных процессорах необходимы для оптимальной производительности в процедурах BLAS.)
Другие машинные функции стали доступны и также могут быть использованы. Следовательно, BLAS был дополнен с 1984 по 1986 год операциями ядра второго уровня, которые касались векторно-матричных операций. Было также признано, что иерархия памяти может быть использована. Многие компьютеры имеют кэш-память, которая намного быстрее основной памяти; локализация операций с матрицей позволяет лучше использовать кеш. В 1987 и 1988 годах BLAS уровня 3 были определены для выполнения матрично-матричных операций. BLAS уровня 3 поощрял блочно-разделенные алгоритмы. Библиотека LAPACK использует BLAS уровня 3.
Исходный BLAS касался только плотно хранимых векторов и матриц. Были рассмотрены дальнейшие расширения BLAS, такие как для разреженных матриц.
Автоматически настраиваемое программное обеспечение линейной алгебры (ATLAS) пытается сделать реализацию BLAS с более высокой производительностью. ATLAS определяет многие операции BLAS в терминах некоторых основных подпрограмм, а затем пытается автоматически адаптировать основные подпрограммы для обеспечения хорошей производительности. Выполняется поиск для выбора подходящего размера блока. Размеры блоков могут зависеть от размера и архитектуры кэша компьютера. Также проводятся тесты, чтобы убедиться, что копирование массивов и векторов улучшает производительность. Например, может быть выгодно копировать аргументы, чтобы они были выровнены по строке кэша, чтобы пользовательские процедуры могли использовать инструкции SIMD.
Функциональные возможности BLAS подразделяются на три набора процедур, называемых «уровнями», которые соответствуют как хронологическому порядку определения и публикации, так и степени полинома в сложности. алгоритмов; Операции BLAS уровня 1 обычно занимают линейное время, O (n), операции уровня 2 - квадратичное время и операции уровня 3 - кубическое время. Современные реализации BLAS обычно предоставляют все три уровня.
Этот уровень состоит из всех подпрограмм, описанных в исходной презентации BLAS (1979), которая определяла только векторные операции над последовательными массивами : скалярные произведения, векторные нормы, обобщенное векторное сложение вида
(так называемый «axpy») и несколько других операций.
Этот уровень содержит операции матрица-вектор, включая, среди прочего, обобщенное умножение матрицы на вектор (gemv):
, а также решатель для x в линейном уравнении
с T быть треугольным. Разработка BLAS уровня 2 началась в 1984 году, а результаты были опубликованы в 1988 году. Подпрограммы уровня 2 специально предназначены для повышения производительности программ, использующих BLAS на векторных процессорах, где BLAS уровня 1 неоптимальны, "потому что они скрывают матрично-векторный характер операций компилятора. "
Этот уровень, официально опубликованный в 1990 году, содержит операции матрица-матрица, включая« общее умножение матриц "(драгоценный камень
) в форме
где A и B при желании могут быть транспонированы или эрмитово -сопряжен внутри процедуры, и все три матрицы могут быть разделены. Обычное матричное умножение A B может быть выполнено путем установки α равным единице и C равным нулю матрицы подходящего размера.
На уровень 3 также включены процедуры для решения
где T - это треугольная матрица, помимо других функций.
Из-за повсеместного распространения умножения матриц во многих научных приложениях, в том числе для реализации остальной части BLAS уровня 3, и поскольку существуют более быстрые алгоритмы помимо очевидного повторения умножения матрицы на вектор, gemm
является основной целью оптимизации для разработчиков BLAS. Например, разложив один или оба из A, Bна блочные матрицы, gemm
может быть реализован рекурсивно. Это одна из мотиваций для включения параметра β, поэтому результаты предыдущих блоков можно накапливать. Обратите внимание, что это разложение требует особого случая β = 1, который оптимизируют многие реализации, тем самым устраняя одно умножение для каждого значения C . Такая декомпозиция позволяет лучше локализовать ссылку как в пространстве, так и во времени данных, используемых в продукте. Это, в свою очередь, использует кэш в системе. Для систем с более чем одним уровнем кэш-памяти блокировку можно применить второй раз к порядку, в котором блоки используются в вычислениях. Оба этих уровня оптимизации используются в таких реализациях, как ATLAS. Совсем недавно реализации Казусигэ Гото показали, что блокировка только для кэша L2 в сочетании с осторожной амортизацией копирования в непрерывную память для уменьшения TLB промахивается, превосходит ATLAS. Тщательно настроенная реализация, основанная на этих идеях, является частью GotoBLAS, OpenBLAS и BLIS.
Распространенным вариантом gemm
является gemm3m
, который вычисляет комплексное произведение с использованием «трех умножений вещественных матриц и пяти сложений вещественных матриц вместо обычных четырех умножений вещественных матриц и двух сложений вещественных матриц», алгоритм, аналогичный алгоритму Штрассена сначала описан Питером Ангаром.
Несколько расширений BLAS для обработки разреженных матриц были предложены на протяжении истории библиотеки; небольшой набор подпрограмм ядра с разреженными матрицами был наконец стандартизован в 2002 году.