Как перевести вычисления в индексной нотации в последовательность операций SIMD в общем случае?

Question

UPD: вопрос в его первоначальной форме плохо сформулирован, потому что я сильно путаю терминологию (SIMD vs с векторизованными вычислениями) и даю слишком широкий пример, который точно не определяет, в чем проблема; Я голосовал, чтобы закрыть его с «неясно, что вы просите», я связать лучше сформулированный выше вопрос всякий раз, когда он появляется

---

В математике, один, как правило, описывают п-мерный тензор вычислений с использованием индекс обозначения, что будет выглядеть примерно так:

A[i,j,k] = B[k,j] + C[d[k],i,B[k,j]] + d[k]*f[j] // for 0<i<N, 0<j<M, 0<k<K 

, но если мы хотим использовать любую библиотеку SIMD эффективно распараллелить, что вычисление (и воспользоваться линейно-алгебраические магии), мы должны выразить его с помощью примитивов из BLAS, numpy, tensorflow, OpenCL, ..., что часто довольно сложно.

Выражения в [Эйнштейна обозначений] [1], как A_ijk*B_kj, как правило, решаются с помощью [np.einsum] [2] (с помощью tensordot, sum и transpose, я полагаю?). Суммирование и другие элементарные операции также хорошо, «умное» индексирование довольно сложно, хотя (особенно, если индекс появляется больше, чем один раз в выражении).

Интересно, существуют ли какие-либо языковые агностические библиотеки, которые принимают выражение в определенной форме (скажем, форму выше) и переводит его в некоторый Intermediate Representation, который может быть эффективно выполнен с использованием существующих библиотек линейных алгебр?

Есть библиотеки, которые пытаются распараллелить вычисление цикла (пользователь API обычно выглядит #pragma в C++ или @numba.jit в Python), но я спрашиваю о немногих другом деле: перевести abritary выражения в форме выше, в конечную последовательность SIMD команды, как поэлементного-OPS, matvecs, tensordots и т.д.

Если нет языка агностик решения еще, я лично заинтересован в Numpy вычислениях :)

Answer 1

Дальнейшие вопросы о коде:

• Я вижу B[k,j] используется индекс и как значение. Все ли целые числа? Если нет, то какие части FP и где происходит преобразование?
• Почему i не появляется в правой части экрана? Повторяются ли одни и те же данные N раз?

---

О Хлоп, поэтому у вас есть операции сбора, с индексами, поступающих от d[k] и B[k,j]. Только несколько наборов инструкций SIMD поддерживают это (например, AVX2).

Я в основном вручную процитирую материал в C, с Intel's x86 intrinsics, (или автоматически векторизовать и проверять выходной файл компилятора, чтобы убедиться, что он не сосал), поэтому IDK, если есть какой-либо независимый от платформы способ выразить это операция.

Я бы не ожидал, что многие межплатформенные языки SIMD предоставят сбор или что-нибудь, что построено на вершине собрания. Однако я не использовал numpy. Я не ожидаю, что вы найдете BLAS, LAPACK или другую библиотечную функцию, которая включает сборку, если вы не ищете реализации этой точной проблемы.

С эффективным собрать (например, Intel Skylake или Xeon Phi), это может векторизации нормально, если вы используете SIMD в петлю над j, поэтому вы загружаете целый вектор сразу от B[], и от f[], и использовать его с вектор, содержащий d[k], передается в каждую позицию. Вероятно, вы захотите сохранить транспонированную матрицу результатов, например A[i][k][j], поэтому окончательный магазин не должен быть разбросом. Вам определенно необходимо избегать обхода более k во внутреннем цикле, поскольку это делает нагрузки с B[] несмежными, и у вас есть d[k] вместо f[j], изменяющихся внутри внутреннего цикла.

---

Я не сделал много с GPGPU, но они делают SIMD по-разному. Вместо использования коротких векторов, таких как процессоры, они эффективно используют множество скалярных процессоров. OpenCL или CUDA или любые другие горячие новые технологии GPGPU могут работать с вашими сборами гораздо эффективнее.

---

SIMD команды, как поэлементного-OPS, matvecs, tensordots и т.д.

Когда я думаю о "SIMD команды", я думаю, инструкции по сборке x86 (или ARM NEON, или независимо) или, по крайней мере, C/C++ intrinsics, которые скомпилируются для отдельных инструкций. : P

Матрично-векторный продукт - это не одна «инструкция». Если вы использовали эту терминологию, каждая функция, обрабатывающая буфер, будет «инструкцией SIMD».

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

IDK, если есть что-то в этом роде, кроме обычного компилятора C, авто-векторизация петель над массивами.