uBLAS Overview

Boost , ,

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

uBLAS Overview

Rationale

Было бы неплохо, если бы каждый тип числового программного обеспечения мог быть написан на C++ без потери эффективности, но если бы не было найдено что-то, что достигает этого без ущерба для системы типа C++, было бы предпочтительно полагаться на Fortran, Collectr или архитектурные расширения (Bjarne Stroustrup).

Эта библиотека C++ ориентирована на научные вычисления на уровне базовых линейных алгебры конструкций с матрицами и векторами и их соответствующих абстрактных операций. Основными целями проектирования были:

математическая нотация
эффективность
функциональность
совместимость

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

Resources

Развитие этой библиотеки было обусловлено несколькими аналогичными усилиями:

БЛАСДжек Донгарра и др.
Блиц++Тодд Велдхойзен
POOMAСкотта Хейни и др.
МТЛДжереми Сик и др.

BLAS, по-видимому, является наиболее широко используемой библиотекой для основных линейных алгебр, поэтому ее можно назвать стандартом de-facto. Его интерфейс процедурный, отдельные функции несколько абстрагируются от простых линейных алгебр. Из-за того, что было реализовано с использованием Fortran и его оптимизации, это также, кажется, одна из самых быстрых библиотек. Поскольку мы решили проектировать и реализовывать нашу библиотеку объектно-ориентированным образом, технические подходы отличаются. Однако любой человек должен быть в состоянии выразить абстракции BLAS с точки зрения наших библиотечных операторов и сравнить эффективность реализации.

Blitz++ - впечатляющая библиотека, реализованная на C++. Его основной дизайн, похоже, ориентирован на многомерные массивы и связанные с ними операторы, включая тензоры. Автор Blitz++ утверждает, что библиотека достигает производительности на том же уровне или лучше, чем соответствующий Fortran-код, благодаря своей технике реализации с использованием шаблонов выражения и метапрограмм шаблонов. Однако мы видим некоторые причины, чтобы разработать собственный подход к проектированию и реализации. Мы не знаем, пытается ли кто-либо реализовать традиционную линейную алгебру и другие численные алгоритмы с использованием Blitz++. Мы также предполагаем, что даже сегодня Blitz++ нуждается в самой продвинутой технологии компилятора C++ из-за ее идиомов реализации. С другой стороны, Blitz++ убедил нас, что использование шаблонов выражения является обязательным для сокращения абстракционного наказания до приемлемого предела.

Цели дизайна POOMA, похоже, параллельны Blitz++ во многих частях. Он расширяет концепции Blitz++ с классами из областей частичных дифференциальных уравнений и теоретической физики. Реализация поддерживает даже параллельные архитектуры.

MTL - еще один подход, поддерживающий основные линейные алгебры операций на C++. Его дизайн в основном, кажется, находится под влиянием BLAS и C++ Standard Template Library. Мы разделяем понимание того, что линейная библиотека алгебры должна обеспечивать функциональность, сопоставимую с BLAS. С другой стороны, мы считаем, что концепции стандартной библиотеки C++ еще не доказаны, чтобы поддерживать численные вычисления по мере необходимости. Как еще одно отличие MTL в настоящее время не использует шаблоны выражения. Это может привести к одному из двух последствий: возможной потере выразительности или возможной потере производительности.

Concepts

Mathematical Notation

Использование математического обозначения может облегчить разработку научных алгоритмов. Таким образом, библиотека C++, реализующая основные концепции линейной алгебры, должна тщательно перегружать выбранных операторов C++ на матричные и векторные классы.

Мы решили использовать перегрузка оператора для следующих примитивов:

Description	Operator
Индексирование векторов и матриц	`vector::operator(size_t i); матрица::operator(size_t i, size_t j);`
Распределение векторов и матриц	`vector::operator = (const вектор_expression &); вектор::operator += (const вектор_expression &); вектор::operator -= (const вектор_expression &); вектор::operator *= (const scalar_expression &); матрица::operator = (const_expression & ); матрица и матрица > > матрица матрица`
Неарочные операции на векторах и матрицах	`vector_expression оператор - (const вектор_expression &); оператор матричной экспрессии - (const matrix_expression &);`
Бинарные операции на векторах и матрицах	`vector_expression оператор + (const вектор_expression & , const вектор_expression & ); вектор_expression оператор - (const вектор_expression & , const вектор_expression & ); матрица_expression + (const matrix_expression & , const matrix_expression &); матрица_expression оператор - (const matrix_expression & , матрица_ );`
Умножение векторов и матриц скаляром	`vector_expressionоператор * (const scalar_expression & , const вектор_expression & ); вектор_expressionоператор * (const вектор_expression & , const scalar_expression & ); матрица_expression * (const scalar_expression & , const matrix_expression & ); матрица_expression * (const matrix_expression & >`

Мы решили не использовать перегрузку оператора для следующих других примитивных:

Description	Function
Левое умножение векторов с матрицей	`vector_expression prod<vector_type` `> (const matrix_expression &, const вектор_expression &); вектор_expression prod (const matrix_expression &, const вектор_expression &);`
Правильное умножение векторов с матрицей	`vector_expression prod<vector_type` `> (const вектор_expression &, const matrix_expression &); вектор_expression prod (const вектор_expression &, const matrix_expression &);`
Умножение матриц	`matrix_expression prod<matrix_type` `> (const matrix_expression &, const matrix_expression &); matrix_expression prod (const matrix_expression &, const matrix_expression &);`
Внутренний продукт векторов	`scalar_expression internal_prod (const вектор_expression &, const вектор_expression &);`
Внешний продукт векторов	`matrix_expression outer_prod (const вектор_expression &, const вектор_expression &);`
Перевод матрицы	`matrix_expression trans (const matrix_expression &);`

Efficiency

Для достижения цели эффективности численных вычислений необходимо преодолеть две трудности в формулировании абстракций с C++, а именно временные и виртуальные функциональные вызовы. Шаблоны экспрессии решают эти проблемы, но, как правило, замедляют время компиляции.

Eliminating Temporaries

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

Два интересных и опасных результата:

Aliases

Можно получить серьезные побочные эффекты, используя элемент мудрой оценки на векторах или матрицах. Рассмотрим матрицу векторного продукта x = A x. Оценка A₁x и присвоение x₁ меняет правую сторону, так что оценка A₂xx возвращает неправильный результат. В этом случае есть aliases элементов x_n как на левой, так и на правой стороне задания.

Наше решение этой проблемы состоит в том, чтобы оценить правую сторону уступки во временной, а затем назначить эту временную на левую сторону. Чтобы позволить дальнейшую оптимизацию, мы обеспечиваем соответствующую функцию члена для каждого оператора уступки, а также noalias синтаксис. Используя этот синтаксис, программист может подтвердить, что левая и правая стороны задания независимы, так что элемент мудрой оценки и прямого назначения цели является безопасным.

Complexity

Вычисленная сложность может быть неожиданно большой при определенных сирумстанциях. Рассмотрим цепный векторный продукт A (B x). Обычная оценка A (B x) является квадратичной. Опущенная оценка B x_i линейна. Поскольку каждый элемент B x_i необходим линейно в зависимости от размера, полностью отложенная оценка цепного векторного продукта матрицы A (B x) является кубическим. В таких случаях нужно повторно вводить temporaries в выражение.

Eliminating Virtual Function Calls

Оценка ленивого выражения обычно приводит к определению классовой иерархии терминов. Это приводит к использованию динамического полиморфизма для доступа к отдельным элементам векторов и матриц, которые также известны как дорогие с точки зрения времени. Решение было найдено пару лет назад самостоятельно Дэвидом Вандервордом и Тоддом Велдхуйзеном и обычно называется шаблонами выражения. Шаблоны экспрессии содержат ленивую оценку и заменяют динамический полиморфизм статическим, т.е. компиляционным полиморфизмом во времени. Шаблоны экспрессии в значительной степени зависят от известного трюка Бартона-Нэкмана, также придуманного Джимом Коплином «критически определенных рекурсивных шаблонов».

Шаблоны выражения формируют основу нашей реализации.

Compilation times

Это также хорошо известный факт, что шаблоны выражения бросают вызов существующим компиляторам. Мы смогли значительно уменьшить количество необходимых шаблонов выражения, используя трюк Бартон-Накман.

Мы также решили поддержать двойное обычное осуществление (т.е. не используя шаблоны выражения) с обширными границами и проверкой типа операций вектора и матрицы для поддержки цикла разработки. Переход от режима отладки к режиму выпуска контролируется NDEBUG предпроцессорный символ .

Functionality

Каждая библиотека C++, поддерживающая линейную алгебру, будет измерена против давнего пакета Fortran BLAS. Теперь мы описываем, как звонки BLAS могут быть отображены на наших классах.

Страница Обзор операций Матрицы и Вектора дает краткое резюме наиболее используемых операций на векторах и матрицах.

Blas Level 1

BLAS Call	Mapped Library Expression	Mathematical Description	Comment
`сум` или `дасум`	`norm_1 (x)`	сум \|x_i\|	Вычисляет l₁ (сумма) норму реального вектора.
`scasum` ИЛИ `dzasum`	`реальный (сум (v)) + imag (сумма (v)))`	(x_i) + sum im(x_i)	Вычисляет сумму элементов сложного вектора.
`_nrm2`	`norm_2 (x)`	sqrt (сумма \|x_i\|² )	Вычисляет l₂ (евклидовая) норма вектора.
`i_amax`	`norm_inf (x) index_norm_inf (x)`	макс \|x_i\|	l_inf (максимальная) норма вектора. BLAS вычисляет индекс первого элемента, имеющего это значение.
`_dot _dotu _dotc`	`inner_prod (x, y)` или`internal_prod (conj (x), y)`	x^T y или x^H y	Вычисляет внутренний продукт двух векторов. BLAS реализует определенную петлю unrollment.
`dsdot sdsdot`	`a + prec_inner_prod (x, y)`	a + x^T y	Вычисляет внутренний продукт в двойной точности.
`_копия`	`x = y y.assign (x)`	x <- y	Копирует один вектор к другому. BLAS реализует определенную петлю unrollment.
`_swap`	`swap (x, y)`	x <-> y	Плавает два вектора. BLAS реализует определенную петлю unrollment.
`_scal cscal zdscal`	`x *= a`	x <- x	Масштабирует вектор. BLAS реализует определенную петлю unrollment.
`_axpy`	`y += a * x`	y <- x + y	Добавляет масштабированный вектор. BLAS реализует определенную петлю unrollment.
`_rot _rotm csrot zdrot`	`t.assign (a * x + b * y), y.assign (-b * x + a * y), x.assign (t)`	(x, y) <- (a x + b y, -b x + a y)	Применяет вращение самолета.
`_rotg _rotmg`		(a, b) <- (? a / sqrt (a² + b²), ? b/ sqrt (a² + b^>2>) или (1, 00)	Построит вращение самолета.

Blas Level 2

BLAS Call	Mapped Library Expression	Mathematical Description	Comment
`_t_mv`	`x = prod (A, x)` или`x = prod (trans (A), x)` или`x = prod (herm (A), x)`	x <- A x или x <- A^T x или x <- A^{^{H x}}	Вычисляет продукт матрицы с вектором.
`_t_sv`	`y = решать (A, x, тег)` или `inplace_solve (A, x, тег)` или `y = реферат (A), x, тег)` или `inplace_solve (A), x, тег)` или `y = решать (герм (A), x, тег)` или `inplace_solve (герм (A), x, тег)`	>^{>-11> > >> > > > >>> >>>> >>>>>> >>>> >>> >> >>> >>>>> >>>>> >>>>>>>> >>>>>>>>>>> >>>>>>> >>>>>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>>>>>}	Пополняет систему линейных уравнений с треугольной формой, т.е. A является треугольной.
`_g_mv _s_mv _h_mv`	`y = a * prod (A, x) + b * y` или`y = a * prod (A), x) + b * y` или`y = a * prod (herm (A), x) + b * y`	y <- a x + b y или y <- a^T x + b y y < - A^H x + b y	Добавляет масштабированный продукт матрицы с вектором.
`_g_r _g_ru _g_rc`	`A += a * External_prod (x, y)` или`A += a * external_prod (x, conj (y))`	A <- x y^T + A или A <- x y^H + A	Выполняет рейтинг 1 обновление.
`_s_r _h_r`	`A += a * External_prod (x, x)` или`A += a * external_prod (x, conj (x))`	A <- x x^T + A или A <- x^H + A	Выполняет симметричный или геммицианский ранг 1 обновление.
`_s_r2 _h_r2`	`A += a * External_prod (x, y) + a * External_prod (y, x))` или`A += a * external_prod (x, conj (y)) + conj (a) * external_prod (y, conj (x))))`	A <- x y^TT + a x^{T^T + A или A <- x y^H + a^- y xH} +	Выполняет симметричный или геммицианский ранг 2 обновление.

Blas Level 3

BLAS Call	Mapped Library Expression	Mathematical Description	Comment
`_t_mm`	`B = a * prod (A, B)` или `B = a * prod (trans (A), B)` или `B = a * prod (A, trans (B)` или `B = a * prod (trans (A), trans (B)` или b = a	B < - op (A) op (B) с op (X) = X или op (X) = X^T или op (X) = X^H	Вычисляет масштабированный продукт из двух матриц.
`_t_sm`	`С = решение (A, B, тег)` или `inplace_solve (A, B, тег)` или `C = решать (транс (A), B, тег)` или `inplace_solve (trans (A), B, tag)` или`C = решать (herm (A), B, tag)` или`inplace_solve (herm (A), B, tag)`	С <- A^{-1>-1>-11>1>> 1>> 1>> 1>> 2>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>}	Пополняет систему линейных уравнений с треугольной формой, т.е. A является треугольной.
`_g_mm _s_mm _h_mm`	`C = a * prod (A, B) + b * C` или `C = a * prod (A), B + b * C` или `C = a * b) + b * C` или `C = a`	C < - op (A) op (B) + b C с op (X) = X или op (X) = X^T или op (X) = X^H	Добавляет масштабированный продукт из двух матриц.
`_s_rk _h_rk`	`B = a * prod (A, trans (A)) + b * B` или `B = a * prod (trans (A), A) + b * B` или `B = a * prod (A, herm (A) + b * B` или `B = a * prod (herm (A), A) + b`	B <- a A^T + b или B <- a^T A + b или B <- a A^{^>H + b или B < - A^H b>}	Выполняет симметричный или геммицианский ранг k обновление.
`_s_r2k _h_r2k`	`C = a * prod (A, trans (B)) + a * prod (B, trans (A)) + b * C` или `C = a * prod (A), B) + a * prod (trans (B), A) + b * C` или `C = a * prod (A, herm (B) +nbsp; prod)`	> > > > > > >> ^{^{^{> > < > > > > <}}}	Выполняет симметричный или геммицианский ранг 2 k обновление.

Storage Layout

uBLAS поддерживает множество различных схем хранения. Полные детали можно найти на Обзор Типов. Большинство типов, таких как vector< double> и matrix< double>, по умолчанию совместимы с C-решениями, но также могут быть настроены на включение совместимых данных FORTAN.

Compatibility

По причинам совместимости мы предоставляем массив, такой как индексирование векторов и матриц. Для некоторых типов (гермитианский, скудный и т.д.) это может быть дорогим для матриц из-за необходимых временных прокси-объектов.

uBLAS использует совместимые с STL распределители для распределения хранилища, необходимого для его контейнеров.

Benchmark Results

Нижеследующие таблицы содержат результаты одного из наших критериев. Этот ориентир сравнивает аборигенную реализацию C ('C mass') и некоторые библиотечные реализации. Безопасные варианты на основе библиотеки предполагают псевдоним, быстрые варианты не используют temporaries и функционально эквивалентны местной реализации C. Помимо общих классов вектора и матрицы, эталон использует специальные классы c_vector и c_matrix, которые предназначены для того, чтобы избежать каждого накладного через генеричность.

Базовая программа bench1 была составлена с GCC 4.0 и запущена на Athlon 64 3000+. Времена - это шкалы для разумной точности при запуске bench1 100.

Сначала мы комментируем результаты для двойных векторов и матриц измерения 3 и 3 x 3 соответственно.

Comment
inner_prod	C-образец	0.61	782	Some abstraction penalty
	c_vector	0.86	554
	вектор	1.02	467
vector + vector	C-образец	0.51	1122	Abstraction penalty: factor 2
	c_vector	1.17	489
	вектор	1.32	433
	c_vector	2.02	283
	вектор безопасный	6.95	82
outer_prod	C-образец	0.59	872	Some abstraction penalty
	c_matrix, c_vector	0.88	585
	матрица, вектор	0.90	572
	c_matrix, c_vector safe	1.66	310
	matrix, вектор	2.95	175
prod (matrix, vector)	C-образец	0.64	671	No significant abstraction penalty
	c_matrix, c_vector	0.70	613
	матрица, вектор	0.79	543
	c_matrix, c_vector safe	0.95	452
	matrix, вектор	2.61	164
matrix + matrix	C-образец	0.75	686	No significant abstraction penalty
	c_matrix	0.99	520
	matrix	1.29	399
	c_matrix сейф	1.7	303
	matrix safe	3.14	164
prod (matrix, matrix)	C-образец	0.94	457	No significant abstraction penalty
	c_matrix	1.17	367
	matrix	1.34	320
	c_matrix сейф	1.56	275
	matrix safe	2.06	208

Мы замечаем двухкратную потерю производительности для небольших векторов и матриц: сначала общее наказание за абстракцию для использования классов, а затем небольшие потери при использовании общих векторных и матричных классов. Различия в псевдонимах также значительны.

Далее мы комментируем результаты для двойных векторов и матриц измерения 100 и 100 x 100 соответственно.

Operation	Implementation	Elapsed [s]	MFLOP/s	Comment
inner_prod	C-образец	0.64	889	No significant abstraction penalty
	c_vector	0.66	862
	вектор	0.66	862
vector + vector	C-образец	0.64	894	No significant abstraction penalty
	c_vector	0.66	867
	вектор	0.66	867
	c_vector	1.14	501
	вектор безопасный	1.23	465
outer_prod	C-образец	0.50	1144	No significant abstraction penalty
	c_matrix, c_vector	0.71	806
	матрица, вектор	0.57	1004
	c_matrix, c_vector safe	1.91	300
	matrix, вектор	0.89	643
prod (matrix, vector)	C-образец	0.65	876	No significant abstraction penalty
	c_matrix, c_vector	0.65	876
	матрица, вектор	0.66	863
	c_matrix, c_vector safe	0.66	863
	matrix, вектор	0.66	863
matrix + matrix	C-образец	0.96	596	No significant abstraction penalty
	c_matrix	1.21	473
	matrix	1.00	572
	c_matrix сейф	2.44	235
	matrix safe	1.30	440
prod (matrix, matrix)	C-образец	0.70	813	No significant abstraction penalty
	c_matrix	0.73	780
	matrix	0.76	749
	c_matrix сейф	0.75	759
	matrix safe	0.76	749

Для более крупных векторов и матриц общее наказание за абстракцию для использования классов, по-видимому, уменьшается, небольшие потери при использовании общих векторных и матричных классов, похоже, остаются. Различия в псевдонимах также остаются видимыми.

Copyright (©) 2000-2002 Joerg Walter, Mathias Koch
Использование, модификация и распространение подлежат лицензии Boost Software, Version 1.0. (См. сопроводительный файл LICENSE_1_0.txt или копия на http://www.boost.org/LICENSE_1_0.txt ).

Статья uBLAS Overview раздела может быть полезна для разработчиков на c++ и boost.

Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.

:: Главная :: ::

Время компиляции файла: 2024-08-30 11:47:00
2025-05-19 23:29:52/0.033875942230225/1