To RAM or no to RAM - вот в чём вопрос! Опции

[m0use]

Привет, ребят.

Стою перед дилемой просто. Нужна обработка матриц - перемножение, сложение элементов. У меня такие мысли.

С первого взгляда, достаточно удобно описывать матрицу как RAM, особенно когда нужно перемножать элементы (на аппаратных умножителях). Но в таком случае за один CLK можно работать только с одним элементом массива (считывать из памяти). Это большое но, потому что хочется максимально распараллелить обработку матрицы. То есть хочется одновременного доступа ко всем элементам - но (и опять же но) комбинаторной логике много, наверно, получается - скорость падает.

Есть ли компромисс? Использовать небольшие блоки памяти? Подскажите, уважаемые коллеги! И вообще верны ли мои рассуждения? .

[Maverick]

Привет, ребят.

Стою перед дилемой просто. Нужна обработка матриц - перемножение, сложение элементов. У меня такие мысли.

С первого взгляда, достаточно удобно описывать матрицу как RAM, особенно когда нужно перемножать элементы (на аппаратных умножителях). Но в таком случае за один CLK можно работать только с одним элементом массива (считывать из памяти). Это большое но, потому что хочется максимально распараллелить обработку матрицы. То есть хочется одновременного доступа ко всем элементам - но (и опять же но) комбинаторной логике много, наверно, получается - скорость падает.

Есть ли компромисс? Использовать небольшие блоки памяти? Подскажите, уважаемые коллеги! И вообще верны ли мои рассуждения? .

какого размера матрицы? и элементы в матрице (их разрядность)?

[rv3dll(lex)]

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

[D13]

ващето память имеет скорость больше чем остальная плис.

в смысле?

[m0use]

какого размера матрицы? и элементы в матрице (их разрядность)?

Неплохо было бы, чтобы матрица была размером не меньше, чем 64x48. Вообще надо обрабатывать изображение 640x480, но думаю, такой объём не эффективно обрабатывать - буду разбивать на блоки порядка 64x48. Элемент матрицы - байт.

rv3dll(lex), а могли бы Вы пояснить. Для того, чтобы такое провернуть, нужен отдельный CLK или можно преобразовать общий CLK и получить большую частоту?

[Koluchiy]

Маленькие блоки RAM - это распределенная RAM.
Если она, конечно, есть.

[m0use]

Маленькие блоки RAM - это распределенная RAM.

Кстати, об этом тоже хотел узнать. Вот у меня небольшой блок памяти описывается поведенчески. На RTL схеме изображается блок RAM, всё как надо. Так вот этот блок RAM - это распределённая память на LUT или блочная RAM?

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

[des00]

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

а ничего что латентность чтения у этих блоков памяти разная ?

[m0use]

а ничего что латентность чтения у этих блоков памяти разная ? smile.gif

Разная - это какая? У блочной памяти время отклика больше?

Сообщение отредактировал m0use - Oct 5 2010, 12:34

[rv3dll(lex)]

вообще про какую плис речь?

для памяти нужен свой быстрый клок.
сама память работать будет на частотах например 500 при том, что остальная схема, если она большая не получится и на 200.

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

[m0use]

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

ПЛИС - Spartan3E.

[Maverick]

Неплохо было бы, чтобы матрица была размером не меньше, чем 64x48. Вообще надо обрабатывать изображение 640x480, но думаю, такой объём не эффективно обрабатывать - буду разбивать на блоки порядка 64x48. Элемент матрицы - байт.

rv3dll(lex), а могли бы Вы пояснить. Для того, чтобы такое провернуть, нужен отдельный CLK или можно преобразовать общий CLK и получить большую частоту?

как по мне лучше распределенная память - на регистрах. Таким образом обеспечивается параллельный доступ ко всем элементам матрицы. Но возможно скорость обработки упадет из-за этого...
Если на RAM блоках тогда нужно придумать FSM, который будет последовательно считывать данные матрицы из RAM блоков и записывать результат обратно в RAM блоки или передавать дальше на обработку... В этом случае наверное нужна двухпортовая память, чтобы "развязать" по скорости поступающих данных на входе и обработанных данных на выходе. Это в том случае если не удастся реализовать обработку входящих данных на проходе (обработка в реалтайме)...
PS Почему бы не взять за основу матрицу 8х6? Как по мне ресурсоемкость меньше и т.д. ...

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

ПЛИС - Spartan3E.

Выход - двухпортовая память или фифо или синхронизаторы на основе двух регистров.

Можно по другому пути пойти (память (во внутреннюю или во во внешнюю пока не важно))
1. изображение 640x480 записывать в память, а потом уже производить его обработку.
2. Изображение поступает например на частоте 5 МГц, а Ваша схема работает на частоте 50 МГц. Тогда можно организовать автомат, который на каждом десятом такте производил запись входных данных ( изображения 640x480) в память, а остальные 9 тактов производил бы обработку данных.
3. Организовать конвейерное обработку "на проходе". Т.е. производить обработку изображения по мере поступления пикселей изображения. Изображение ж на ПЛИС поступает последовательно..., правильно? Таким образом, когда будет конец кадра изображения - обработанные данные при таком подходе также будут готовы (с некоторой задержкой)

[m0use]

Почему бы не взять за основу матрицу 8х6? Как по мне ресурсоемкость меньше и т.д. ...

Матрицу 8x6 использую пока для отладки. Но вообще думаю о больших размерах .

Просто изображение большое - 640x480 и блоков по 8x6 получится много - то есть чтобы всю матрицу обработать, нужно много проходов. Конечная цель - получить хорошую скорость обработки именно изображения в целом. Поэтому и хочу "элементарный" блок увеличить.

Почему пришлось использовать RAM. В самом начале (когдя я ещё ничего не понимал о внутренней структуре ПЛИС, и смотрел на него как на штуку, которая может много оперций делать за один такт) я всё сделал на регистрах. И всю обработку сделал параллельной. А так как из порядка 100 умножений кристалл аппаратно может сделать лишь 20 получилось много логики (под 100% ресурсов на матрице 8x6) и мало скорости (5 МГц ).

Теперь думаю умножение реализовать только на аппаратных, соответственно удобно RАМ использовать. Умножил, хорошо. Но теперь нужно сделать сумму по окрестности каждого элемента и теперь RАМ не удобна, так как даёт доступ только к одному элементу за такт (выше был предложен вариант разных клок доменов, но для меня это круто пока).

Так что буду пробовать. Умножу как RAM, а складывать буду как регистровую память. Посмотрим, насколько макс.такт упадёт. Пока 120МГц. Я бы просто не хотел ниже 100 опускаться. Просто основная операция - умножение по ресурсам. И если их хотя бы больше 10 использовать, но эквивалентная частота будет больше 1ГГц.

[Maverick]

для конкретности понимания Вас не могли бы поделиться алгоритмом обработки изображения , который необходимо реализовать и требованиями к реализации?

[Koluchiy]

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

И резко возрастет объем проекта...

[m0use]

поделиться алгоритмом обработки изображения

Из исходной матрицы I строим градиентные матрицы Ix и Iy. В простейшем случае это просто разность элементов по x и по y. Потом строим 3 матрицы из поэлементных произведений Ix * Ix, Ix * Iy и Iy * Iy. То есть элементы этих матриц равны произведению соответствующих элементов исходных матриц. А потом для каждого элемента полученных матриц строим сумму по окрестности. То есть к значению самого элемента прибавляем значения соседей. Получим матрицы A, B и С. Вот. Но это ещё не всё . Элементы окончательная матрица H = f( A, B, C ). Функция f - простое выражение с двумя умножениями, разностью и делением. На Cи можно написать 4мя вложенными циклами. Но такой подход в кристалле тучу места займёт.

[Maverick]

И резко возрастет объем проекта...

что делать? человек всегда становится перед выбором

Функция f - простое выражение с двумя умножениями, разностью и делением.

с операцией деления по подробнее... На константу или переменную?

[m0use]

На константу или переменную?

На переменную - тоже моя головная боль будущая. Думаю использовать тут Core Generator. Потому что самому писать реализацию деления... когда-нибудь в другой раз .

Ребят, скажите, пожалуйста, можно ли одновременно оба канала 2-port RAM использовать для чтения?

Сообщение отредактировал m0use - Oct 5 2010, 17:39

[Maverick]

На переменную - тоже моя головная боль будущая. Думаю использовать тут Core Generator. Потому что самому писать реализацию деления... когда-нибудь в другой раз .

На мой взгляд лучше реализация по предложенному мною 3 варианту. Т.е. через конвейерную обработку на проходе.
Поясню более подробно (мое видение):
Реализовывается задержка на требуемое кол-во строк и пикселей в строке (аналогичную как на рисунке во вложении, из-за этого и предложил уменьшить матрицу ). Таким образом организовываем окно которое будет "скользить" по изображению. Далее реализовываем конвейерную обработку в темпе считывания изображения (оно ж последовательно поступает на ПЛИС) для значений пикселей в окне - как пример архитектуры реализации конвейера представлен на втором рисунке.
PS На рисунках во вложении для примера представлена архитектура реализации медианного фильтра 3х3 для изображения.
PS PS На втором рисунке горизонтальные линии - делят обработку на такты для конвейера.
PS PS PS Но решение как лучше реализовывать, принимать Вам

Эскизы прикрепленных изображений

 

[m0use]

Офигеть! Maverick, спасибо, что поведал про такую красивую идею!

А это откуда картинки? Просто первоисточник хотел бы посмотреть! Наверно, хорошая книжка . И, может быть Вы в принципе можете что-то посоветовать по теме таких вот стандартных схемотехнических решений? Буду очень благодарен.

А кстати, FIFO в простейшем случае (который здесь как задержка выступает) - это просто нужное количество регистров?

[Koluchiy]

что делать? человек всегда становится перед выбором

Иногда очень легко стать или перед пределом максимально возможной емкости отдельно взятой микросхемы, или (чаще) отдельно выделенного количества денег...

Шустрые плисины - они того, дорогие очень.

[vadimuzzz]

Теперь думаю умножение реализовать только на аппаратных, соответственно удобно RАМ использовать. Умножил, хорошо. Но теперь нужно сделать сумму по окрестности каждого элемента и теперь RАМ не удобна, так как даёт доступ только к одному элементу за такт

есть еще такой вариант: использовать RAM с шириной шины данных N*(сколько_у_вас_там_бит), соответственно можно распараллелить вычисления

[rv3dll(lex)]

есть еще такой вариант: использовать RAM с шириной шины данных N*(сколько_у_вас_там_бит), соответственно можно распараллелить вычисления

чтобы считывать сразу несколько точек?

[vadimuzzz]

чтобы считывать сразу несколько точек?

ну да, блочная память FPGA такие фокусы позволяет. еще многопортовый доступ можно задействовать.

[Maverick]

Офигеть! Maverick, спасибо, что поведал про такую красивую идею!

Всегда пожалуйста!

А это откуда картинки? Просто первоисточник хотел бы посмотреть! Наверно, хорошая книжка . И, может быть Вы в принципе можете что-то посоветовать по теме таких вот стандартных схемотехнических решений? Буду очень благодарен.

Первоисточник - в личке. Это даже не книжка - магистерская работа студента из Америки кажется.
Но довольно не плохая, как по мне...

А кстати, FIFO в простейшем случае (который здесь как задержка выступает) - это просто нужное количество регистров?

Да

[CaPpuCcino]

Первоисточник - в личке.

а может всё-таки огласите весь список? хотя бы название.
спб

[Maverick]

а может всё-таки огласите весь список? хотя бы название.
спб

Не проблема...
Первоисточник (где-то на форуме уже выкладывал)

Размер архива 814.79 килобайт

Там как пример рассмотрена реализация медианного фильтра и в конце приведено описание на VHDL.

PS Как по мне там красиво и подробно расписана эта идея и приведен пример реализации.

Подумайте, может можно заменить операцию деления на операцию сдвига (деления на числа степени двойки). Будет проще реализация

[m0use]

есть еще такой вариант: использовать RAM с шириной шины данных N*(сколько_у_вас_там_бит), соответственно можно распараллелить вычисления

Я думал так делать, но пока нацелился на конвеерный подход, который Maverick подкинул.

еще многопортовый доступ можно задействовать.

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

У меня просто произведения элементов матриц между собой и самих на себя требут 3 умножителей. Двухпортовое считывание позволяет 6 умножителей использовать. А подход с размерностью памяти, скажем, в три байта позволит 18 умножений делать за так. Из 20 аппаратных умножителей ещё 2 останутся - там потом ещё надо будет умножения делать. В целом, наверно, тут уже предел будет для этой ПЛИС.

Первоисточник - в личке.

Спасибо, тема близка - думаю, мне это сильно поможет. Только вот там VHDL, который я пока не изучал .

Длинный P.S.

У меня с этим конвеерным подходом небольшой вопрос появился. Мне нужная сумма 9 элементов на конвеере (условно горизонтальном). Соответственно, чтобы частота не падала - нужен конвеер уже в вертикальном направлении - из 8 "складывателей" и промежуточными регистрами. Если это так, то тогда можете подсказать, как оптимально такой вопрос решать. Так как это матрица, то мне не все суммы нужны (граничные эффект - когда окно к краям матрицы подходит). Как мне следующему модулю передать только нужные суммы? Я тут три подхода вижу:

1. Передавать все, а обрабатывать только нужные.
2. Передавать только нужные каким-нибудь сигналом, что на выходе нужная сумма. Но тут такой момент возникает, что от того момента, когда на конвеере будет нужная последовательность до того, как их сумма попадёт на выход пройдёт 4 такта. То есть и сигнал нужно задерживать на столько же тактов. Это регистром сдвига делать?
3. Другой подход. Какой ?

[CaPpuCcino]

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

нет больше пока на одну RAMину нельзя, но можно дублировать контент (параллельная запись в несколько RAM никем не противопоказана)

Я думал так делать, но пока нацелился на конвеерный подход, который Maverick подкинул.

а скомбинировать?

3. Другой подход. Какой ?

сдвиговый регистр вполне хорош, т.к. прост как табуретка и ресурсов по минимуму

[m0use]

Подумайте, может можно заменить операцию деления на операцию сдвига (деления на числа степени двойки). Будет проще реализация wink.gif

Надо подумать. Как-то очевидное решение не приходит. Если с = 2^n + r, то a = b / с = b / ( 2^n + r ) = b >> n / ( 1 + r >> n ). А дальше ряд Тейлора и ещё про дробную часть не забывать?.. Надо почитать про алгоритмы деления быстрые будет, но я бы пока на IP остановился.

[vadimuzzz]

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

именно, можно читать по 2 разным адресам. можно и 3-портовый доступ, 2 на чтение, 1 на запись. короче, есть где развернуться.

[m0use]

можно дублировать контент (параллельная запись в несколько RAM никем не противопоказана)

Ага - хорошее дополнение. Я немного по-другому делал - разбивал одну RAM на две меньших (без дублирования) - но тут опять же предел в 20 умножителей. Вариантов по его достижению уже немало было рассмотрено. По быстродействию и ресурсам они, наверно, очень близки - надо просто выбрать один .

а скомбинировать?

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

[Maverick]

У меня с этим конвеерным подходом небольшой вопрос появился. Мне нужная сумма 9 элементов на конвеере (условно горизонтальном). Соответственно, чтобы частота не падала - нужен конвеер уже в вертикальном направлении - из 8 "складывателей" и промежуточными регистрами. Если это так, то тогда можете подсказать, как оптимально такой вопрос решать. Так как это матрица, то мне не все суммы нужны (граничные эффект - когда окно к краям матрицы подходит). Как мне следующему модулю передать только нужные суммы? Я тут три подхода вижу:

1. Передавать все, а обрабатывать только нужные.
2. Передавать только нужные каким-нибудь сигналом, что на выходе нужная сумма. Но тут такой момент возникает, что от того момента, когда на конвеере будет нужная последовательность до того, как их сумма попадёт на выход пройдёт 4 такта. То есть и сигнал нужно задерживать на столько же тактов. Это регистром сдвига делать?
3. Другой подход. Какой ?

поясните, плиз 2 пункт

[m0use]

поясните, плиз 2 пункт

Неясно выразился, возможно. Например, матрица 4x4. На конвеер она поступает последовательно:

...-13-[12-11-10]-9-[8-7-6]-5-[4-3-2]-1-...

Но оконная функция не все комбинации выбирает, а только:

*__*__*__4
*__*__*__8
*__*__*__12
13_14_15_16

1__*__*__*
5__*__*__*
9__*__*__*
13_14_15_16

и т.п.

То есть сумма 13+12+11+9+8+7+5+4+3, к примеру, нам не нужна. Но на выходе она есть. Поэтому нужна дополнительная информация. Которая должна быть синхронизирована с потоком основных данных.

Сообщение отредактировал m0use - Oct 7 2010, 14:50

[CaPpuCcino]

Поэтому нужна дополнительная информация. Которая должна быть синхронизирована с потоком основных данных.

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

[m0use]

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

Входная матрица - 8x6.

Речь прежде всего о скорости. И вот какие результаты:
конвеер - порядка 220 МГц,
RAM - порядка 120 МГц.

При этом в первом случае для полного прохода ещё и тактов меньше требуется.

Прикладываю RTL-схемы модулей для наглядности.

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

К чему я. Возникло предположение, что подход с конвеером здесь более эффективен. Получается, где поток данных "проходит" через кристалл, не задерживаясь, RAM не к месту? RAM оправдана там, где данные "задерживаются" для многократного вторичного использования? Или как ?

Эскизы прикрепленных изображений

 

[CaPpuCcino]

Получается, где поток данных "проходит" через кристалл, не задерживаясь, RAM не к месту?

не обощайте так уж совсем. иногда например RAM удобно использовать в качестве демультиплексора в потоке: 1 порт на вход 2 на выход и разрядность у портов не связана меж собой обычная логика может сожрать много ресурсов и получится медленнее (всё зависит от подробностей).