Comments 49
Интересно. И какая получается максимальная частота выполнения 1 шага сортировки массивов скажем размеров 4, 16 и 256 элементов на DE0/D2-115?
У меня частота от размера массива не зависит, только от размера сравниваемого числа в битах: критический путь проходит через один компаратор(модуль сравнения чисел) для реализации цепочкой и через два компаратора для дерева. Я рассчитываю, что для упомянутых плат на частоте 100mhz (1280x1024 vga) можно сравнивать 64-битные слова для реализации цепочкой. Сейчас попробую переделать тестовый стенд чтобы проверить.
Не удалось заставить схему сбоить. Даже со 128-битными данными порядок у обоих реализаций, 256-битные Quartus отказывается компилировать, а повышать частоту сложно, и за железо немного боязно.
Интересно сравнение скорости выполнения сортировки «аппаратной» и «софтварной»
Мне кажется для сортировки чисел можно использовать и обычный процессор, но для поиска строк или применения regex'ов — вот тут как раз FPGA очень даже полезны.
Ну, программная сортировка ограничена алгоритмической сложностью. Что касается regex'ов, то это смотря какие regex-ы. Если нужен широкий канал наружу и простой обработчик (проверить на равенство чему-то, посчитать хэш), то обычный FPGA подход вероятно сработает. Но я ищу задачу где требуется нелинейный алгоритм с большим количеством переходов(проверить выполнимость булевой формулы), который не ложится на обычный обработчик сигналов.
<оффтоп, да не совсем>
Интересно, когда появится оперативная память, стандартизированная под >90% десктоп и серверные архитектуры, способная самостоятельно выполнять различные операции над своими ячейками, поиск, копирование, сортировку,… произвольный код (по типу FPGA, даже и сильно ограниченный), к тому же многозадачно, параллельно и конечно же сверхэффективно как по энергопотреблению так и по скорости.
</...>
Интересно, когда появится оперативная память, стандартизированная под >90% десктоп и серверные архитектуры, способная самостоятельно выполнять различные операции над своими ячейками, поиск, копирование, сортировку,… произвольный код (по типу FPGA, даже и сильно ограниченный), к тому же многозадачно, параллельно и конечно же сверхэффективно как по энергопотреблению так и по скорости.
</...>
Интеллектуальная память, реконфигурируемые вычисления получат развитие не раньше, чем появится адекватная модель их программирования. Я вот как раз хочу попробовать комбинаторную логику в такой роли.
Стоп, что значит «адекватная модель»? Просто нужен 4GL, вроде матлаба, проблема мне кажется не в этом.
Кстати сказать, MATLAB Simulink умеет генерить HDL. Но это всё compile time. А для run time нужен язык с естественными средствами метапрограммирования который мог бы, так сказать, себя на лету перекомпилировать. Тут по-моему у функциональных языков нет конкурентов.
Стоп, не понял, зачем на лету перекомпилировать? Вы предлагаете перепрошивать FPGA на разные задачи? Но ведь это ненулевое время, а для больших программ могут быть вообще секунды.
Не на разные задачи, а на разные варианты базовой задачи. У вас в карточной игре, я не знаю, вышла некоторая масть. Вы можете построить более совершенный расчётный алгоритм использующий этот факт. См. Суперкомпиляция.
Секунды это специфика ПЛИС. Были бы алгоритмы, подразумевающие перестройку на лету, появились бы и средства переконфигурации.
Секунды это специфика ПЛИС. Были бы алгоритмы, подразумевающие перестройку на лету, появились бы и средства переконфигурации.
Ну, если поменялась например козырная масть, это не сложно инкорпорировать в схему, а вот если поменялась сама игра — другое дело, придется перепрошивать все и вся.
Я думаю, если не решать задачу 'в лоб', делая полностью программируемой всю логику. Память внутри чипа делится на домены (сотни и тысячи), в каждом — свой, даже не процессор, а блок FPGA, имеющий прямой доступ к ячейкам памяти домена, этот блок минимальный, сотни ячеек (ну тысяча), достаточный чтобы описать просто логику работы с памятью и работу со структурами данных (та же сортировка, например, может быть определена на основе одного поля в структуре данных, которая в свою очередь может быть двусвязанным списком или деревом).
в FPGA логика прошивается в свою собственную память, где конфигурация определяется той же побитовой матрицей (я верно понимаю что это почти та же флеш-память, где ячейки определяют связи между логическими элементами?), в нашем случае эти данные можно хранить в самой оперативной памяти, на этом можно неплохо сэкономить, ведь не полностью же все ячейки FPGA блоков нужны всегда, не нужные можно использовать как память общего назначения.
в FPGA логика прошивается в свою собственную память, где конфигурация определяется той же побитовой матрицей (я верно понимаю что это почти та же флеш-память, где ячейки определяют связи между логическими элементами?), в нашем случае эти данные можно хранить в самой оперативной памяти, на этом можно неплохо сэкономить, ведь не полностью же все ячейки FPGA блоков нужны всегда, не нужные можно использовать как память общего назначения.
Так, а чем это отличается от просто FPGA? И кстати, конфигурация FPGA во время работы хранится в ячейках статического ОЗУ, которые можно использовать альтернативно как дополнительную память. Флеш память непосредственно используется в другом типе ПЛИС — CPLD.
Значит я рад что ошибался (я думал что сам метод создания ячеек FPGA подразумевает технологию по типу FLASH памяти, со всеми вытекающими минусами), получается сам процесс прошивки FPGA модулей может не требовать какого-либо неприятно большого времени, а значит динамическая перепрошивка в процессе выполнения — вполне реальна. Вопросы компиляции 'на лету' можно отложить, это инженерные вопросы и решаемы так или иначе.
Просто FPGA от RAM отличаться будет тем что строение оперативной памяти уже давно не набор тригеров на базе логических элементов (так делают только что для кеш памяти процессора), а с целью плотности размещения на чипе и уменьшения энергопотребления используются технологии которые врят ли совместимы с технологиями FPGA матрицы. Т.е. на чипе придется совмещать их обе. Грубо говоря чем больше площади чипа мы отдадим FPGA тем меньше будет юзабельной памяти. А памяти мы хотим по прежнему много и подешевле.
Просто FPGA от RAM отличаться будет тем что строение оперативной памяти уже давно не набор тригеров на базе логических элементов (так делают только что для кеш памяти процессора), а с целью плотности размещения на чипе и уменьшения энергопотребления используются технологии которые врят ли совместимы с технологиями FPGA матрицы. Т.е. на чипе придется совмещать их обе. Грубо говоря чем больше площади чипа мы отдадим FPGA тем меньше будет юзабельной памяти. А памяти мы хотим по прежнему много и подешевле.
… динамическая перепрошивка в процессе выполнения — вполне реальна. Вопросы компиляции 'на лету' можно отложить, это инженерные вопросы и решаемы так или иначе.
Так что прошивать то? Если у вас несколько готовых прошивок, которые надо менять время от времени, — такая технология уже есть. Для чего-то сложнее нужна перекомпиляция.
Ну полная универсальность пока наверное не актуальна… да елки палки, просто оперативная память с единственной распаралеливаемой инструкцией — копирование/перемещение, может дать такой мощный прирост, особенно с прямой поддержкой процессором, что тут эта область развиваться начнет.
Механизм копирования блока памяти без участия процессора давно существует — ПДП(DMA). А если копировать не блоком, то кто будет управлять процессом, ставить саму задачу?
Там речь о взаимодействии памяти и устройства без участия процессора. С работой внутри оперативной памяти оно справляется?
DMA конечно процессор освобождает, но продолжает занимать шину данных, уже давно это бутылочное горлышко между процессором и памятью, и простая операция копирования занимает шину на 100%.
А что мешает расширять это горло? Можно ставить много независимых банков, можно использовать многопортовую память. Проблема в поддержании целостности системы в условиях массовой параллельной работы с памятью. Параллелизм надо поддерживать ещё на уровне парадигмы программирования, я ставлю на функциональный подход.
А вы уверены, что это o(n)? n-то предполагается любого размера, а не фиксированного. Если мы говорим, что у нас размер фиксирован, то это вообще o(1).
Если нам надо будет отсортировать M*n массив посредством этой штуки, где n — ёмкость этой штуки, то какой сложность будет относительно M?
Подозреваю, что едва ли не o(M2).
Если нам надо будет отсортировать 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 элементов.
Таким образом, алгоритмически ничего не поменялось. На практике поменялись константы — и это очень важно, на практике. Но с точки зрения чистой 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 = 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 элементов всё равно 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 тактов, при неизменном 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) существует. Например, в книге Кормена она есть, причём крайне простая. Вопрос лишь в выделении соответствующего массива памяти
Цитата из Кормена:
Мой модуль использует только попарные сравнения. Например, какие-нибудь double-ы сортировками семейства radix sort сортировать плохо.
… Разумеется, они улучшают оценку о(n log(n)) за счёт того, что используют не только попарные сравнения, но и внутреннюю структуру сортируемых объектов.
Мой модуль использует только попарные сравнения. Например, какие-нибудь double-ы сортировками семейства radix sort сортировать плохо.
Раз уж вы говорите, что за счет аппаратной реализации создали быстрый алгоритм, то стоило бы и сказать, сколько потратили ресурсов на эту реализацию.
Я не автор, но примерно скажу что время разработки на FPGA в 10-100 раз для простых проблем и 10-1000 для проблем промышленного масштаба. Более того, использование в реале несет нехилые косты в плане производства, и взаимодействие с классическими x86 системами это отдельная песня.
Поэтому FPGA как механизм ускорения (а не контроля за LED-дисплеем на вокзале) окупается только в узком спектре дисциплин, например в финансовой инженерии.
Поэтому FPGA как механизм ускорения (а не контроля за LED-дисплеем на вокзале) окупается только в узком спектре дисциплин, например в финансовой инженерии.
Это тоже, безусловно, важно, но я имел в виду более приземленную вещь: аппаратные затраты (логика, триггеры и т.д.)
FPGA как механизм ускорения (а не контроля за LED-дисплеем на вокзале)
Добавлю, что есть и другие важные области применения (такие как прототипирование ASIC и цифровая обработка сигналов в телекомуникационной отрасли), в которых использование FPGA не просто окупается, но ещё и едва ли не единственный применимый вариант.
А по поводу времени разработки замечу, что вендоры на месте не сидят, а работают над решниями (OpenCL на FPGA, HDL coder для MATLAB).
По трудозатратам я согласен с оценкой 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:
n_max=64, bits=32:
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-битных».
А то ализаровщина какая-то получается.
Например — «целых положительных 8-битных».
А то ализаровщина какая-то получается.
В данном случае, целых положительных с параметризованной разрядностью, но поскольку всё, кроме компаратора от типа данных не зависит, сравнивать можно что угодно, подобрав соответствующий компаратор. Можно числа с плавающей точкой, можно пары ключ-значение сортировать по ключу. Кстати, сортировка стабильная.
Sign up to leave a comment.
Аппаратный сортировщик чисел на verilog-е