Умножение матриц: эффективная реализация шаг за шагом

Наверное не так выразился. Мысль которую я хотел донести: Не используются субкубические варианты типа алгоритма Штрассена.

Умножение матриц: эффективная реализация шаг за шагом

На сколько я видел в разных реализациях, нигде блочное перемножение не используется. Видимо потому, что это приводит к дополнительным копированиям памяти. А как следует из статьи выигрыш от локализации данных в кэше — до 10 раз. Выигрыш от подобных блочных алгоритмов будет проявляться только на матрицах циклопических размеров. А такие уже будет целесообразно считать на GPU.

Умножение матриц: эффективная реализация шаг за шагом

Цель статьи — не написать саму быструю реализацию, а показать внутренее устройство алгоритма. Понятно, что GPU будет быстрее. С этим никто не спорит.

Умножение матриц: эффективная реализация шаг за шагом

Основной принцип останется прежним: микроядра, максимальная локализация в кэше. Изменится только функции переупорядочивания.

Умножение матриц: эффективная реализация шаг за шагом

Я уже достаточно давно разработываю проект по оптимизации различных алгоритмов (в основном по компьютерному зрению) при помощи SIMD инструкций. В частности я всегда старался выравнивать данные и использовать варианты с выровненными инструкциями (например, _mm_load_ps вместо _mm_loadu_ps), где только можно. Однако в последних поколениях процессоров Интел скорость работы этих инструкций одинаковая (при условии обращения к выровненному адресу конечно). Более того компилятор часто вместо _mm_load_ps подставляет ассемблерную инструкцию соответсвующую _mm_loadu_ps.

Умножение матриц: эффективная реализация шаг за шагом

На больших матрицах думаю будет небольшой проигрыш в пределах 5-10% (для 1 — потока). На малых размерах проигрыш будет в разы (причины этого указаны в статье).

Линус Торвальдс не верит, что серверы на ARM-архитектуре заменят x86. «Продавать 64-битную модель — идиотизм»

Писать приходится 6 раз минимум: Scalar, SSE, AVX, AVX2|FMA, AVX-512 и NEON.

Линус Торвальдс не верит, что серверы на ARM-архитектуре заменят x86. «Продавать 64-битную модель — идиотизм»

Как раз сейчас у меня очередной этап портирования кода: x86(SSE, AVX) -> ARM (NEON). Могу только констатировать, что в данном вопросе Линукс полностью прав: Без нормальной девборды этот процесс весьма длительный и утомительный (с кросскомпиляцией и без дебагера).

P.S. А так на текущем этапе ARM явно не хватает широкого SIMD. NEON с его 128-bit на текущем этапе достаточно скромно выглядит по сравнению с AVX и уж тем более AVX-512.

Нейросеть для разработчиков C++

Перспективы библиотеки конечно довольно туманны, ввиду огромного количества весьма достойных альтернатив. Однако она тоже полезна — лучший способ разобраться в методах машинного обучения — самому написать библиотечку для машинного обучения (проверено на себе). Так что удачи автору!
P.S. Сам достаточно длительное время посвятил оптимизациям прямого распространения сигнала в неросетях на CPU (проекты Simd и Synet). Если потребуется помощь — обращайтесь.

Приватность в Китае: преступника поймали на концерте в 50 тыс. человек с помощью системы распознавания лиц

Да. Но камер то у нас тысячи… К стати будете детектирование и распознавание одной сетью делать? Просто полностью работу (получение видеоптока, декодирование, предварительная обработка, детектирование, распознавание, сопровождение, поиск по базе подозреваемых, выдача результата) выполнить на GPU врядли получиться. А если часть работы делать на СPU, то именно эта работы будет узким местом.

Приватность в Китае: преступника поймали на концерте в 50 тыс. человек с помощью системы распознавания лиц

Типичный пример ошибки, когда максимальную скорость обработкой ГПУ предварительно подготовленных батчей экстраполируют на видео потоки, которые еще нужно декодировать и т д и т п.

Приватность в Китае: преступника поймали на концерте в 50 тыс. человек с помощью системы распознавания лиц

Т.е. у вас домашний GPU может обрабатывать 60000 Full-HD кадров за 17секунд с работающими алгоритмами обнаружения и распознавания лиц? Дайте мне такой!
Или вы не это имеете в виду?

Приватность в Китае: преступника поймали на концерте в 50 тыс. человек с помощью системы распознавания лиц

У вас хороший домашний сервер. Анализировать видео с миллиона видео камер в режиме реального времени — это коллосальная по вычислительным требованиям задача. Современные алгоритмы основанные на DNN очень ресурсоемки.

Японцы оценили залежи редкоземельных элементов в океаническом иле возле острова Минамитори в 16 миллионов тонн

Теоретически можно увеличивать площадь острова за счет отвалов пустой породы (ила). Остров не очень большой, потому это может иметь практический смысл, если для размещения перерабатывающих заводов не будет хватать площади.

C++ велосипедостроение для профессионалов

Я не поленился и проверил скорость деления с применением закешированного значение и напрямую с использованием SSE:

#include <emmintrin.h>
#include <windows.h>
#include <inttypes.h>
#include <vector>
#include <iostream>

float fractions[256];

void Div1(const float * a, const int * b, size_t n, float * c)
{
	const int step = 4;
	for (size_t i = 0; i < n; i += step)
	{
		c[0] = a[0] * fractions[b[0]];
		c[1] = a[1] * fractions[b[1]];
		c[2] = a[2] * fractions[b[2]];
		c[3] = a[3] * fractions[b[3]];
		a += step;
		b += step;
		c += step;
	}
}

void Div2(const float * a, const int * b, size_t n, float * c)
{
	const int step = 4;
	for (size_t i = 0; i < n; i += step)
	{
		_mm_storeu_ps(c, _mm_div_ps(_mm_loadu_ps(a), _mm_cvtepi32_ps(_mm_loadu_si128((__m128i*)b))));
		a += step;
		b += step;
		c += step;
	}
}

double GetFrequency()
{
	LARGE_INTEGER frequency;
	QueryPerformanceFrequency(&frequency);
	return double(frequency.QuadPart);
}

double g_frequency = GetFrequency();
double Time()
{
	LARGE_INTEGER counter;
	QueryPerformanceCounter(&counter);
	return double(counter.QuadPart) / ::g_frequency;
}

int main()
{
	for (size_t i = 0; i < 256; ++i)
		fractions[i] = 1.0f / i;

	const size_t n = 1024 * 256, m = 256;
	std::vector<int> b(n);
	std::vector<float> a(n), c1(n), c2(n);
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = (float)::rand();
		b[i] = (::rand() * 256) / RAND_MAX;
	}

	double t1 = Time();
	for (size_t i = 0; i < m; i++)
		Div1(a.data(), b.data(), n, c1.data());
	t1 = Time() - t1;
	std::cout << "t1 = " << t1 * 1000 << " ms." << std::endl;

	double t2 = Time();
	for (size_t i = 0; i < m; i++)
		Div2(a.data(), b.data(), n, c2.data());
	t2 = Time() - t2;
	std::cout << "t2 = " << t2 * 1000 << " ms." << std::endl;

	return 0;
}

У меня получилось, что второй вариант более чем вдвое быстрее (35 ms и 15 ms).

C++ велосипедостроение для профессионалов

Да пример не самый удачный. Тем не менее даже с учетом конвертации туда и обратно, fp деление будет быстрее, потому как векторизуемо.

C++ велосипедостроение для профессионалов

Хотелось бы сделать небольшое замечание, касательно быстрого деления на число. На самом деле кеширование результата операции целесообразно только для деление на небольшое число. Кроме того доступ к закешированным данным плохо векторизуется. Если деление настолько массовая операция, то наиболее оптимально будет ее выполнять на лету при помощи векторных инструкций. Нашел пример с умножением по модулю:
stackoverflow.com/questions/46790237/vectorization-of-modulo-multiplication/46790553#46790553

Первый шаг к аппаратным ускорителям нейронных сетей для программистов лежит через изучение основ HDL, RTL и лаб на FPGA

Тем не менее алгоритм для всех точек одинаковый (ну может быть кроме краевых), хотя и использует разные данные. Потому тут SIMD самое место. Согласен про достижение 100% — это очень маловероятно, но 30-50% вполне себе достижимо. Значит вы занизили всего в 10-15 раз…

Первый шаг к аппаратным ускорителям нейронных сетей для программистов лежит через изучение основ HDL, RTL и лаб на FPGA

Всего-навсего FullHD 60fps видео камера и требуется простейшая обработка видеопотока реалтайм.
Давайте просто подсчитаем сколько у нас тактов на пиксель на том же ПК?
(3*10^9) / (1920*1080*60) = 24

Тут на лицо явная поддасовка фактов. Типичный своременный ПК с поддержкой AVX2 имеет производительность порядка 100 GFLOPs (32-bit float) на каждое ядро (2х2х8 операций за такт с использованием FMA). Т.е. вы занизили производительность ПК в 30 раз!

Ускоряем метод Виолы-Джонса (Viola-Jones)

Не везде есть возможность работать на GPU. Да и не все алгоритмы на GPU хорошо ложатся.