Pull to refresh

Comments 49

Интересно. И какая получается максимальная частота выполнения 1 шага сортировки массивов скажем размеров 4, 16 и 256 элементов на DE0/D2-115?
У меня частота от размера массива не зависит, только от размера сравниваемого числа в битах: критический путь проходит через один компаратор(модуль сравнения чисел) для реализации цепочкой и через два компаратора для дерева. Я рассчитываю, что для упомянутых плат на частоте 100mhz (1280x1024 vga) можно сравнивать 64-битные слова для реализации цепочкой. Сейчас попробую переделать тестовый стенд чтобы проверить.
Не удалось заставить схему сбоить. Даже со 128-битными данными порядок у обоих реализаций, 256-битные Quartus отказывается компилировать, а повышать частоту сложно, и за железо немного боязно.
Интересно сравнение скорости выполнения сортировки «аппаратной» и «софтварной»
Аппаратная в данном случае работает 2*n тактов для n чисел, хорошая софтварная имеет сложность n*log(n), если одно сравнение будут делаться за один такт, то для массива из 256 чисел получим 2048 тактов против 512 у аппаратной. Ну и чем больше n тем лучше.
Мне кажется для сортировки чисел можно использовать и обычный процессор, но для поиска строк или применения regex'ов — вот тут как раз FPGA очень даже полезны.
Ну, программная сортировка ограничена алгоритмической сложностью. Что касается regex'ов, то это смотря какие regex-ы. Если нужен широкий канал наружу и простой обработчик (проверить на равенство чему-то, посчитать хэш), то обычный FPGA подход вероятно сработает. Но я ищу задачу где требуется нелинейный алгоритм с большим количеством переходов(проверить выполнимость булевой формулы), который не ложится на обычный обработчик сигналов.
Монте-карло симуляция карточной игры кажется подпадает под это определение.
Это как, задаём игровую ситуацию, делаем ход, а потом перебираем случайные продолжения? Как тренировочная задача может быть подойдёт.
Именно так. И поскольку некоторые ходы могут означать конец игры, а другие ее продолжение, получается нелинейная структура которую к сожалению GPU не очень охотно берет ввиду дивергенции ветвей, а вот на FPGA можно даже несколько реализаций процесса делать одновременно, если место позволяет.
<оффтоп, да не совсем>
Интересно, когда появится оперативная память, стандартизированная под >90% десктоп и серверные архитектуры, способная самостоятельно выполнять различные операции над своими ячейками, поиск, копирование, сортировку,… произвольный код (по типу FPGA, даже и сильно ограниченный), к тому же многозадачно, параллельно и конечно же сверхэффективно как по энергопотреблению так и по скорости.
</...>
Стоп, что значит «адекватная модель»? Просто нужен 4GL, вроде матлаба, проблема мне кажется не в этом.
Кстати сказать, MATLAB Simulink умеет генерить HDL. Но это всё compile time. А для run time нужен язык с естественными средствами метапрограммирования который мог бы, так сказать, себя на лету перекомпилировать. Тут по-моему у функциональных языков нет конкурентов.
Стоп, не понял, зачем на лету перекомпилировать? Вы предлагаете перепрошивать FPGA на разные задачи? Но ведь это ненулевое время, а для больших программ могут быть вообще секунды.
Не на разные задачи, а на разные варианты базовой задачи. У вас в карточной игре, я не знаю, вышла некоторая масть. Вы можете построить более совершенный расчётный алгоритм использующий этот факт. См. Суперкомпиляция.
Секунды это специфика ПЛИС. Были бы алгоритмы, подразумевающие перестройку на лету, появились бы и средства переконфигурации.
Ну, если поменялась например козырная масть, это не сложно инкорпорировать в схему, а вот если поменялась сама игра — другое дело, придется перепрошивать все и вся.
Я думаю, если не решать задачу 'в лоб', делая полностью программируемой всю логику. Память внутри чипа делится на домены (сотни и тысячи), в каждом — свой, даже не процессор, а блок FPGA, имеющий прямой доступ к ячейкам памяти домена, этот блок минимальный, сотни ячеек (ну тысяча), достаточный чтобы описать просто логику работы с памятью и работу со структурами данных (та же сортировка, например, может быть определена на основе одного поля в структуре данных, которая в свою очередь может быть двусвязанным списком или деревом).

в FPGA логика прошивается в свою собственную память, где конфигурация определяется той же побитовой матрицей (я верно понимаю что это почти та же флеш-память, где ячейки определяют связи между логическими элементами?), в нашем случае эти данные можно хранить в самой оперативной памяти, на этом можно неплохо сэкономить, ведь не полностью же все ячейки FPGA блоков нужны всегда, не нужные можно использовать как память общего назначения.
Так, а чем это отличается от просто FPGA? И кстати, конфигурация FPGA во время работы хранится в ячейках статического ОЗУ, которые можно использовать альтернативно как дополнительную память. Флеш память непосредственно используется в другом типе ПЛИС — CPLD.
Значит я рад что ошибался (я думал что сам метод создания ячеек FPGA подразумевает технологию по типу FLASH памяти, со всеми вытекающими минусами), получается сам процесс прошивки FPGA модулей может не требовать какого-либо неприятно большого времени, а значит динамическая перепрошивка в процессе выполнения — вполне реальна. Вопросы компиляции 'на лету' можно отложить, это инженерные вопросы и решаемы так или иначе.

Просто FPGA от RAM отличаться будет тем что строение оперативной памяти уже давно не набор тригеров на базе логических элементов (так делают только что для кеш памяти процессора), а с целью плотности размещения на чипе и уменьшения энергопотребления используются технологии которые врят ли совместимы с технологиями FPGA матрицы. Т.е. на чипе придется совмещать их обе. Грубо говоря чем больше площади чипа мы отдадим FPGA тем меньше будет юзабельной памяти. А памяти мы хотим по прежнему много и подешевле.
… динамическая перепрошивка в процессе выполнения — вполне реальна. Вопросы компиляции 'на лету' можно отложить, это инженерные вопросы и решаемы так или иначе.

Так что прошивать то? Если у вас несколько готовых прошивок, которые надо менять время от времени, — такая технология уже есть. Для чего-то сложнее нужна перекомпиляция.
Да понятно, что все эти технологии есть… по отдельности, хотелось бы это уже в оперативной памяти, стандартной и для десктопа, с поддержкой процессоров и компиляторов :)

Дай возможность массам, а там и инструментарий наработается.
Ну полная универсальность пока наверное не актуальна… да елки палки, просто оперативная память с единственной распаралеливаемой инструкцией — копирование/перемещение, может дать такой мощный прирост, особенно с прямой поддержкой процессором, что тут эта область развиваться начнет.
Механизм копирования блока памяти без участия процессора давно существует — ПДП(DMA). А если копировать не блоком, то кто будет управлять процессом, ставить саму задачу?
Там речь о взаимодействии памяти и устройства без участия процессора. С работой внутри оперативной памяти оно справляется?
Да, канал ПДП из памяти в память тоже часто используется. Типичное применение — подкачка из объёмной внешней памяти в быструю внутреннюю.
DMA конечно процессор освобождает, но продолжает занимать шину данных, уже давно это бутылочное горлышко между процессором и памятью, и простая операция копирования занимает шину на 100%.
А что мешает расширять это горло? Можно ставить много независимых банков, можно использовать многопортовую память. Проблема в поддержании целостности системы в условиях массовой параллельной работы с памятью. Параллелизм надо поддерживать ещё на уровне парадигмы программирования, я ставлю на функциональный подход.
Ложкой черпать океан.
Мы не можем достаточно расширить каналы передачи данных, к тому же это усложняет общую архитектуру компьютера. Развитие, как мне кажется, должно быть в добавлении собственных мозгов каждому компоненту, в данном случае — оперативной памяти.
А вы уверены, что это o(n)? n-то предполагается любого размера, а не фиксированного. Если мы говорим, что у нас размер фиксирован, то это вообще o(1).

Если нам надо будет отсортировать M*n массив посредством этой штуки, где n — ёмкость этой штуки, то какой сложность будет относительно M?

Подозреваю, что едва ли не o(M2).
Ну конечно, o(n) будет для n<n_max. Для случаев массивов больших n, польза всё равно будет, сортируем по кусочкам, а потом применяем сортировку слиянием. Должно по идее получиться o(n*(log(n/n_max)))
Это как вы так изящно деление под логарифм засунули? Получится o(n*log(n-n_max)) для сортировки слиянием блоков, помноженный на o(n_max) для сортировки плиской. n_max константа, так что ей можно пренебречь, получаем o(n*log(n)) — никакой разницы, «сортировка слиянием».

Таким образом, алгоритмически ничего не поменялось. На практике поменялись константы — и это очень важно, на практике. Но с точки зрения чистой CS — тот же алгоритм, только переставляет за раз не 2, а const элементов.
Допустим n = 2*n_max. Отсортировали два куска n/2 аппаратно — n тактов (n/2+n/2). Слили два куска за n тактов. Итого 2*n
Допустим n = 4*n_max. Отсортировали четыре куска n/4 аппаратно — n. Слили первый раз за n, стало два куска, слили второй раз за n Итого 3*n тактов.
Допустим n = (2^k)*n_max. Отсортировали (2^k) куска n/(2^k) аппаратно — n. Слили первый раз за n, стало (2^(k-1)) куска, слили второй раз за n… Итого (k+1)*n тактов.
(k+1) это как раз log(n/n_max).
В тот момент, когда вы говорите, что n= Cont1 * Const2, то у вас n становится константой, и сложность алгоритма становится o(1).

Кстати, сортировка слиянием для n элементов всё равно o(n*log(n)), даже если куски отсортированы. Если у вас размер куска m, всего элементов n, то у вас n/m кусков, что есть o(n).
Вы прекрасный инженер, но плохо разбираетесь в теоретических основах компьютерных наук. О-нотация используется не для точной оценки количества операций, выполняемых в ходе алгоритма, а для оценки того, как хорошо алгоритм масштабируется.
В вашем случае, масштабируемость не предусмотрена и вы всегда можете отсортировать n элементов за n тактов, при неизменном n. Это даже не О(n), это О(1) — т.е. алгоритм, в рамках своей реализации, всегда выполняет константное количество операций, равное n.
О(1) означает, что ваш алгоритм пропорционален «f(x) = 1», с известным коэффициентом пропорциональности, равным n, вынесенным за О и отброшенным.
Как только вы вводите масштабируемость, сортируя k > n элементов, с помощью слияния блоков, ваше О(1) сводится к слиянию k/n блоков, т.е. O(k*log(k)).
Ну хорошо, убедили, сейчас напишу дополнение. Хотя мне хотелось бы иметь возможность подчеркнуть тот факт, что моя сортировка быстрее программной, причём чем больше n (<n_max) тем больше выигрыш.
ну, вообще говоря, учитывая условие n<nmax, то и программная реализация O(n) существует. Например, в книге Кормена она есть, причём крайне простая. Вопрос лишь в выделении соответствующего массива памяти
Цитата из Кормена:
… Разумеется, они улучшают оценку о(n log(n)) за счёт того, что используют не только попарные сравнения, но и внутреннюю структуру сортируемых объектов.

Мой модуль использует только попарные сравнения. Например, какие-нибудь double-ы сортировками семейства radix sort сортировать плохо.
Раз уж вы говорите, что за счет аппаратной реализации создали быстрый алгоритм, то стоило бы и сказать, сколько потратили ресурсов на эту реализацию.
Я не автор, но примерно скажу что время разработки на FPGA в 10-100 раз для простых проблем и 10-1000 для проблем промышленного масштаба. Более того, использование в реале несет нехилые косты в плане производства, и взаимодействие с классическими x86 системами это отдельная песня.

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

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

А по поводу времени разработки замечу, что вендоры на месте не сидят, а работают над решниями (OpenCL на FPGA, HDL coder для MATLAB).
Да вот как раз обработка сигналов это то узкое место где FPGA рулит. Например приходит к вам вагон данных с биржи, с которым x86 не справиться — делается FPGA feed handler который сам все распарсит и даже может назад что-то послать.
По трудозатратам я согласен с оценкой mezastel, а по ресурсам ПЛИС вот отчёт от Quartus для сортировщика с n_max=128, 16 битные числа:
+--------------------------------------------------------------------------------------+
; Flow Summary                                                                         ;
+------------------------------------+-------------------------------------------------+
; Flow Status                        ; Successful - Fri May 09 20:42:53 2014           ;
; Quartus II 32-bit Version          ; 13.0.1 Build 232 06/12/2013 SP 1 SJ Web Edition ;
; Revision Name                      ; DE0_VGA                                         ;
; Top-level Entity Name              ; DE0_VGA                                         ;
; Family                             ; Cyclone III                                     ;
; Device                             ; EP3C16F484C6                                    ;
; Timing Models                      ; Final                                           ;
; Total logic elements               ; 3,970 / 15,408 ( 26 % )                         ;
;     Total combinational functions  ; 3,732 / 15,408 ( 24 % )                         ;
;     Dedicated logic registers      ; 2,257 / 15,408 ( 15 % )                         ;
; Total registers                    ; 2257                                            ;
; Total pins                         ; 252 / 347 ( 73 % )                              ;
; Total virtual pins                 ; 0                                               ;
; Total memory bits                  ; 0 / 516,096 ( 0 % )                             ;
; Embedded Multiplier 9-bit elements ; 6 / 112 ( 5 % )                                 ;
; Total PLLs                         ; 1 / 4 ( 25 % )                                  ;
+------------------------------------+-------------------------------------------------+
А можно сравнение для другого n_max? Интересно, линейная зависимость или какая.
Практически линейная, и для n_max и для разрядности.
n_max=64, bits=16:
; Total logic elements               ; 2,317 / 15,408 ( 15 % )                         ;
;     Total combinational functions  ; 2,157 / 15,408 ( 14 % )                         ;
;     Dedicated logic registers      ; 1,233 / 15,408 ( 8 % )                          ;

n_max=64, bits=32:
; Total logic elements               ; 4,567 / 15,408 ( 30 % )                         ;
;     Total combinational functions  ; 3,993 / 15,408 ( 26 % )                         ;
;     Dedicated logic registers      ; 2,369 / 15,408 ( 15 % )                         ;

в общем случае требует время O(n*log(n))

Количество операций растёт с такой скоростью, а не время, тут вы лишь распараллеливаете.
Попробуйте прикинуть сложность числа операций с ростом n вашем варианте.
Хорошо бы автор написал — сортировщик _каких_ чисел в данном случае реализован.
Например — «целых положительных 8-битных».
А то ализаровщина какая-то получается.
В данном случае, целых положительных с параметризованной разрядностью, но поскольку всё, кроме компаратора от типа данных не зависит, сравнивать можно что угодно, подобрав соответствующий компаратор. Можно числа с плавающей точкой, можно пары ключ-значение сортировать по ключу. Кстати, сортировка стабильная.
Only those users with full accounts are able to leave comments. Log in, please.