Хранение и работа с большими матрицами в ПЛИС, Размера 1000х500 Опции

[count_enable]

Есть большая матрица, размера эдак 1000х500 8-битных целых. Требуемые операции (в порядке приоритета по скорости):
- Сумма выбранных элементов из столбца А, типа А1+А5+А100+А512.
- Сумма выбранных элементов из строки B, типа B1+B5+B100+B512.
- К выбранному элементу добавить или отнять 8-битное целое.
- Заполнение матрицы начальными значениями.

Операций умножения нет. Решение в лоб это декларация двумерного массива и работа как с однопортовой ОЗУ с чтением-записью поэлементно. Но так как по грубым прикидкам операция суммирования в столбце или в строке будет занимать около 3/4 всех вычислений, хочется чего-то более умного. Целевое железо это Virtex 5.

Думаю над тем чтобы разбить столбцы (число строк всегда больше числа столбцов) на отдельные BRAM, тогда можно будет выбрать все элементы строки в один цикл, но обратная задача - все элементы столбца тогда опять получается O(N). Есть ли решения получше? Можно использовать внешнюю DDR, но вряд ли она здесь поможет.

[Maverick]

Есть большая матрица, размера эдак 1000х500 8-битных целых. Требуемые операции (в порядке приоритета по скорости):
- Сумма выбранных элементов из столбца А, типа А1+А5+А100+А512.
- Сумма выбранных элементов из строки B, типа B1+B5+B100+B512.
- К выбранному элементу добавить или отнять 8-битное целое.
- Заполнение матрицы начальными значениями.

Операций умножения нет. Решение в лоб это декларация двумерного массива и работа как с однопортовой ОЗУ с чтением-записью поэлементно. Но так как по грубым прикидкам операция суммирования в столбце или в строке будет занимать около 3/4 всех вычислений, хочется чего-то более умного. Целевое железо это Virtex 5.

Думаю над тем чтобы разбить столбцы (число строк всегда больше числа столбцов) на отдельные BRAM, тогда можно будет выбрать все элементы строки в один цикл, но обратная задача - все элементы столбца тогда опять получается O(N). Есть ли решения получше? Можно использовать внешнюю DDR, но вряд ли она здесь поможет.

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

[SFx]

Начните с модели на языке С/С++

[Maverick]

добавлю к словам

Начните с модели на языке С/С++

или матлаб

[count_enable]

В матлабе уже давно всё работает, матлаб вообще превосходно заточен для матричных операций. Если точнее, то делаю алгоритм обучения Restricted Boltzmann Machine.

Вкратце алгоритм таков:
- Получаем на входе множество строк, которые надо выбрать из столбцов (А, В, Е, Х....)
- Для каждого столбца считаем сумму элементов в строках (А, В, Е, Х....). Данная операция равноценна умножению бинарного вектора Х [0,1] на матрицу. Обычно вектор довольно разряженный, т.е. количество единиц меньше половины но никаких закономерностей нет.

- Потом получаем множество столбцов и повторяем операцию, только суммируем элементы в строках. Данная операция равноценна умножению вектора на транспонированую матрицу.

Допустим у нас есть вектор и матрица:

Код

[ 0,          [ A B C
  1,            D E F
  1,            G H I
  0]            J K L ]      

Тогда результатом будет вектор [ D+G , E+H, F+I ]

Надеюсь, понятно обьяснил. Из этих двух операций и состоит 75% алгоритма. После чего следует поэлементное сложение чисел в матрице, т.е. к каждому элементу добавляется некое число, положительное или отрицательное.

[Timmy]

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

[count_enable]

А можно поподробнее, что значит диагонально? К тому же сумма всех строк или столбцов мне неинтересна, только избранные.

[Timmy]

А можно поподробнее, что значит диагонально? К тому же сумма всех строк или столбцов мне неинтересна, только избранные.

Например, Element[row,col] -> Element[row,(row+col) mod ncols].

[RobFPGA]

Приветствую!

Полет буйной фантазии - если у Вас чип жирный

500 блоков BRAM18 в формате 1Kx16 ну и ~(500 + 256) DSP в dual mode
фактически 2 копии матрицы
младшая половина доступна через порт А - доступ по столбцам
старшая половина доступна через порт B - доступ по строкам

при заполнении матрицы один или оба порта переключается на источник данных.

Успехов! Rob.

[count_enable]

RobFPGA, у меня XC5VLX110T, 64 DSP, 296 BRAM18. Насколько я понял, Вы предлагаете держать по сути две матрицы, прямую и транспонированую в блоках по 16 бит, где старший байт- прямая матрица, а младший-обратная? К сожалению, боюсь двойной размер я не потяну . И я не понял зачем там DSP - есть только сложение, без умножения.

Пока что мне нравится такой вариант:
Один BRAM держит один или 2 столбца (матрица до 1125х592). Два набора сумматоров: один делает сумму выбранных столбцов для заданной строки (все строки пробегаем за O(К), т.к. у нас одно чтение с каждого столбца), второй делает сумму выбранных строк для всех столбцов (т.е. у нас по одному сумматору на BRAM) и мы последовательно читаем все выбранные строки, пробегая их за О(М). Тревогу пока вызывает первый сумматор: он должен суммировать за O(1) все столбцы, т.е. иметь ~500 входов, что меня немного пугает и подталкивает до сложения в цикле (10х50, например).

[RobFPGA]

Приветствую!

Ну с таким маленьким (чипом конечно же) будет большой секс

Немного не понял - если у Вас в BRAM один - или 2 столбца - откуда появился 500 входной сумматор ???

Так как полная матрица внутрь не влезет то остается работать с внешней - а тут увы все упирается в полосу пропускания памяти.
Хорошо если это какая-нибудь *SRAM куда хочу туда и читаю, если же DRAM - то выборка на чтение только по одному направлению матрицы.

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

Я имел ввиду что 2 матрицы хранятся в разных половинах BRAM - старший бит адреса в порте A=0, а в B=1 поэтому как бы имеем 2 независимых блока 512х16 - но это уже не столь актуально.

На DSP удобно не только умножать - но и просто суммировать - один DSP48 может работать как один сумматор 48+48 или
как 2 24+24 или как 4 12+12

Успехов! Rob.

[Timmy]

При диагональном расположении матрицы в памяти можно за один такт выбирать либо всю строку, либо весь столбец(устанавливая нулевую или единичную разность адресов между соседними BRAM), и сразу складывать все элементы строки/столбца на дереве сумматоров. Правда, из-за того, что в из одного BRAM придётся выбирать сразу два элемента, на выборке либо строк, либо столбцов придётся добавить ещё один такт.

[ASN]

count_enable
Уважаемый RobFPGA Вам посоветовал хорошую идею использовать встроенные аппаратные блоки для выполнения арифметических операций.
IMHO, чем проще реализация - тем лучше.
У Вас 296 BRAM18 - это 592 блока (1024 отсчёта по 8 бит). Для хранения матрицы необходимо только 500.
Если суммировать все отсчёты на DSP48 (адреса задаются обычным счётчиком), то неиспользуемые в сумме текущие выбираемые отсчёты можно зануляются на входе сумматора через мультиплексор согласно правилу суммирования.
В таком случае, можно задавать вектор суммирования переменный, с помощью битовой маской. На неё 50 блоков и уйдёт.
Скорость обработки зависит от количество параллельно работающих DSP48 и тактовой частоты.
IMHO, при 10 нс внутреннем цикле суммирование на 50 сумматорах (работающих в режиме 16 + 16 + 16) позволят обработать пакет данных менее чем за 50 мкс.

[count_enable]

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

RobFPGA и ASN я так понял, что предлагаете хранить 1 столбец - 1 BRAM, верно? И держать 50 сумматоров 12+12+12+12 с мультиплексорами чтобы в цикле суммировать все выходы BRAM?

[iiv]

Есть большая матрица, размера эдак 1000х500 8-битных целых. Требуемые операции (в порядке приоритета по скорости):
...
Целевое железо это Virtex 5.

Давайте прежде чем что-то в железе имплементировать, изучим чуток Ваш алгоритм.

Во-первых, интересует диапазоны разреженности векторов и матрицы, целевые размеры матрицы, число итераций по сходимости РБМа.

Во-вторых, не проще ли сделать разреженное сингулярное разложение или адаптивнцю кросс-аппроксимацию Вашей матрице и применить РБМ уже на такую факторизованную матрицу. Если озвученные размеры в 1Кх1К верны, то влоб лапаком даже без разреженности Вы это быстрее чем за 0.1с на обычном компьютере получите.

В-третьих: что хочется, решить задачу, решить много задач, решать быстро и тратить мало электричества, решать еще быстрее, но наплевать на электричество, или все-тики есть "шашечки" в виде Витрекса?