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

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

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

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

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

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

или матлаб

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

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

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

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


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

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

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

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

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

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

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

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

Успехов! Rob.

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

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

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

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

Немного не понял - если у Вас в 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.

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

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

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

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

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

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

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

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

Сейчас работаю с матрицей 765х201. Хочется сделать архитектуру универсальной, с масштабируемостью и неким запасом по размерам (оттого и 1000х500). Делаю обучение он-лайн, а не сборками. Я в курсе что batch training лучше, но хочется получить обучаемую систему, которой можно просто показывать один образец за другим. Матрица весов полная, т.е. нулей там ничтожно мало. Вектор же напротив, обычно имеет от 30% до 50% единиц только.
Почему я это делаю на FPGA: хочется получить универсальный нейроаккселератор, пригодный для встраеваемых систем, с низким энергопотреблением и работой в реальном времени. Кстати, моя реализация RBM далеко не первая на плисах. Обычно систему обучают на компьютере и в плисину уже загоняют тренированную сеть. Меня же интересует обучение.

count_enable
Всё верно.
Идея в том, что если у Вас активными (используемыми в вычислениях) будут хотя бы 25% отсчётов, то проще сделать суммирование "влоб" зануляя неиспользуемые.
Для процесса сложения возможно распараллеливание: на один DSP48 отсчёты с нескольких BRAM (например, с трёх одновременно). Тогда можно использовать объединение выходов BRAM через конвейер мультиплексоров.
Это хорошо повлияет на максимальную тактовую частоту, и машина состояний получится достаточно простой.

Спасибо, уже начал потихоньку строчить код. Практичный вопрос по ISE 14.1: есть ли смысл использовать примитив RAMB18 и писать обёртку к нему или же писать свою RAM размером с BRAM, а синтезатор сам догадается, что с ней сделать? По документации BRAM и DSP очень быстрые, 550 МГц. Хотелось бы хотя бы половину из этой частоты получить.

count_enable

теперь конечно проще советовать, но все еще есть вопросы:



однозначно все как полный вектор и полная матрица, 30% - погоды не сделают. (Выше ASN уже верно подметил!)


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

Если предположить, что матрица у Вас 500х1000, обучается за 1к итераций, то используя хорошо оптимизированные blas2 на Mali ядрах у A20 одна итерация (то есть одно суммирование по матрице) будет вычисляться примерно за 50 мкс, а все обучение будет длиться около 50мс если Вам для этого надобно 1к итераций и не более 1 секунды, если Вам надобно 20к итераций.

Удобство А20 - дешевизна, наличие почти в каждом планшетнике, наличие кучи удобных тулсов, купил, установил софт, и все работает. При желании можно проставить на нем под линуксом октав, чтобы сразу все переносить с матлаба, только немного помучиться оптимальные библиотеки к октаву прикрутить, иначе будет раз так в 10 медленнее.

Теперь о плиске. Конечно на ней можно, нужно, вроде бы правильно, но!

Какая скорость доступа на один брам? В Альтере с одного М9К вы получите примерно 0.8ГБайт/с, и, чтобы сравнится в теоретическом пике с Мали ядром, придется задействовать 60 таких блоков, а чтобы серьезно обогнать - пользовать под 500 таких блоков.

Сразу возникает вопросы:
1. а столько блоков в Вашем виртексе есть?
2. а если смотреть на задачи 500, Вы упираетесь уже в предел параллелизма, то есть алгоритм будет супер-супер плохо параллелиться. То есть Вам надобно будет больше памяти, а она в блочном виде в плисках ну совсем не масштабируема. И задачи Вам нужны побольше, для лучшего параллелизма...

ИМХО (совсем не настаиваю, но настойка бы получилась бы крепкая) пользуйте планшетник с А20 или Exinos 5 или A80 или любым другим процессором, в котором есть мали ядро 4, а лучше 6-ой версии, будет и потребление 2-3Ватта, и работать все из коробки, и все интернеты, блутусы, мультитачи на халяву... А вот если ну очень хочется плиску, я бы брал бы минимум 5-ый и очень жирный стратикс, и поднимал бы размерность задачи до 5к хотя бы.

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

Теоретически TC мог бы впихнуть в его чип (Virtex5LX110 ) одну копию матрицы 1000x500 - 250 блоков BRAM18 (а можно и 223 обойтись если не забывать что память 18 бит!)
Опят же теоретически один BRAM18 может выдать на гора ~550*4.5 >2.4 GByte/s (в конфигурации 2 порта по 18 бит)

Но практически для начала я бы ориентировался на частоту 330-400 MНz.
При таком раскладе для одного цикла суммирования надо будет ~530 тактов ~1.6 us

Но дешевым и мало потребляющем конечно такое решение не будет.

Успехов! Rob.

Лиха беда начало... Существующие реализации RBM имеют ускорение от х25 до х100 при сравнении с процессорами класса Intel Core. ( http://web.stanford.edu/~pmcmahon/fpl09_dbn.pdf "A Fully Pipelined FPGA Architecture of a Factored Restricted
Boltzmann Machine Artificial Neural Network" http://delivery.acm.org/10.1145/2540000/25...759a6160147408e ). Вполне возможно, что перейду на Zynq, с обучением на процессоре если будет выгоднее. Пока что Zynq не впечатляет меня своей плис-частью. Еще лежит под столом Virtex 7, но существующие корки, используемые нами созданы под V5/ PLB. В общем, работы непочатый край. Всем большое спасибо за дельные советы, я еще не одну тему здесь создам в процессе творения.

Сразу практический вопрос: необходим ли RAMB18 примитив, или можно как-то без него убедить синтезатор в использовании BRAM? Пока что мне синтезирует однопортовую память в LUT.

UPD: Сам себе отвечаю: включить принудительное использование BRAM и DSP в опциях синтеза, ну и полностью синхронный дизайн памяти.

Есть в описаниях XST шаблоны, которые приводятся к Block RAM и шаблоны которые приводятся синтезатором к Distrubuted RAM. Их синтезатор находит в коде, и генерирует именно те блоки, которые в них описаны.
Плюс такого подхода - быстрая симуляция без лишних библиотек.

Еще раз акцентирую Ваше внимание: RBM фактически требует максимально быстрого доступа к памяти, и у Вас есть два пути: использовать специальные процессоры а ля ГПУ, или блочную память плиски. Если сравнить современное отношение скорости доступа к внутренней памяти графических карт и обычных процессоров, то это отношение как раз и соответствует 100 раз, то есть в графической карте есть 6 гигабайт памяти, к которой Вы сможете в 100 раз быстрее достучаться, чем к обычной оперативной на обычном процессоре. Чтобы обогнать плиской 250 ГБайт в секунду стационарных, и 50ГБайт в секунду на портаберльных графических карт, Вам надобно очень сильно постараться и иметь достаточно жирные виртексы

В то же время, я одобряю Вашу идею использования плисок, так как это более эффективное расходование транзисторов, чем на графических картах для Вашей задачи, но, поймите, для РБМа Вы столько подводных камней на плиске получите, что, я бы, на Вашем месте, вначале на Опен-Це-еЛе это все обкатал бы, а только потом бы на плиску двинулся бы, благо какой-нибудь олинуксино за 65 евро берется, в котором все есть и пользуй-проверяй сколько хочешь.

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

Я бы ещё добавил:
1. Идея использования двух портов одновременно весьма здравая.
2. Если важна задержки доступа к памяти (latency) то FPGA должны серьезно обогнать и CPU и GPU.

Но ведь я-то не в отпуске . Лучше Вы к нам, здесь значительно дешевле, а выпивка и море отличные.

Почему всё же FPGA? Ну, во-первых это предмет моего PhD и он уже пересмотру не подлежит. Во-вторых, так же как безалкогольное пиво это первый шаг к резиновой женщине, так и FPGA это дорожка ведущая к ASICu. Существует несколько очень обещающих аналоговых и гибридных нейрочипов, я же думаю о чисто цифровом.

Очень рад слышать, что кто-то еще здесь работал с RBM. Если не секрет, то какая область? Распознавание образов, системы управления? А строили свёрточные сети и автоэнкодеры? Они сейчас реально рулят, просто магия какая-то.

так тем более - за знаниями в статистической области в командировку в Монтекарловку - к светиле в области статистики (у меня Нейчер есть) я Вам бы командировку-бы и подписал бы


ну так бы и сказали бы - "шашечки", правда, в Вашем случае, довольно интересные.


Распознавание пустышки от реальной боеголовки по интерференционной картине от ударной волны при высоких скоростях полета очень хорошо на факторизованной многомерной Больцманн машине получается, опорные вектора по скорости и рядом не стояли, хотя все-таки лучше.

А по-существу, позвольте дать Вам несколько советов:

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

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

3. Не ленитесь хотя бы на уровне статей сравнивать то, что получается на плиске у Вас или Ваших коллег/конкурентов с результатами на графических картах - часто помогает быстро упасть (или уронить шефа) с пьедестала.

Успехов!

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

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