Comments 38
Крутая статья!
Задача конвейеризации стандартных операций (сложения, умножения, сравнения и тд) может послужить прекрасной темой для бакалаврской, дипломной или магистерской работы.
Добавлю, что разработка и анализ реализаций таких стандартных математических операций в заданном контексте (производительность/задержка/компактность и т.д.) -- это важная часть реализации криптографических алгоритмов на FPGA.
Зачем вообще нужно задерживать данные на входе сумматоров, если время до появления устойчивого результата на выходах ограничено временем распространения сигнала по самой длинной логической цепи?
Имеете в виду почему бы не снести все регистры на выход os, а входы оставить без задержек?
Именно, в самом сложном случае, когда приходится учитывать перенос из каждого разряда, у нас будет наибольшее время до устойчивого состояния выходов. По истечении этого времени, результат можно записать в регистры. Может так получиться, что состояние наступит раньше, чем завершится один такт. Я правильно рассуждаю?
Если мы уберем задержки с входов, то из-за задержек на цепях переноса мы не сможем корректно складывать разряды каждый такт
Но если мы прикинем с реальными задержками, например, задержка формирования логического уровня на выходе переноса - 10 нс с момента поступления сигналов на входы сумматора по фронту такта, а такт - 200 нс. То 8 битный сумматор должен успеть сформировать корректный результат до завершения такта. Это верно? Т.к. сам однобитный сумматор не имеет памяти, то он переключается на столько быстро, на сколько позволяют его логические элементы.
Это прикол xD? что за такт в 200нс? это калькулятор на лампах или на рассыпухе? Тут такт задан в 2нс, ну если быть +/- в реальности то 5-3нс, но ни как ни 200нс.
Хорошо, такт 5 нс, перенос формируется за 0.4 нс. За такт 8 бит устаканятся?
так речь та не идет о 8 битах, 8 бит это не интересно. Интересно, когда числа многоразрядные, больше 32 хотя бы
Хорошо, при тех же вводных 64 битный сумматор из простых однобитных сумматоров покажет результат за 8 тактов?
результат будет зависеть от длины конвейера, его латентность будет равна разрядности сумматора (кажется), а интервал инициализации 1 такт - для случая разобранного в статье
shift_reg <= {shift_reg[C_CLOCK_CYCLES-1:0], data_in};
здесь все верно?
всего с 1 уровнем логики
Хотел не читая ответить что это невозможно, так как нижняя теоретическая оценка O(log n), но всё такие промотал статью до места где сказали что просто выполнили конвейеризацию.
Умеете за O(log n) уровней комбинационной логики? По мне так интересная задача, жалко что на практике почти не используется.
Умеете за O(log n) уровней комбинационной логики?
Позвольте процитировать один известный мем:
" если бы мы знали, что это такое, но мы не знаем, что это такое "
Ради интереса соорудил подобного "монстра-сумматора" на Cyclone IV. Если мне не изменяет память... Это был 32 битный сумматор с fmax равный fmax чипа (250МГц), +350LUT. (может не то запомнил)
Собственно я тогда и понял почему никто не хочет делать его "супербыстрым", и обычно делают какой-то не сильно замороченный.
Эх, я даже было начал смотреть видео, потом стал тыкать на прогрессбар -- вдруг что-то новое скажут, потом закрыл. До начала просмотра думал, что расскажут о схемах ускоренного переноса, деревьях сумматоров, каких-нибудь 3-2 adders и т.д. А оказалось, 3 часа делали конвеер, складывающий 1 бит за стадию.
При этом, исходный модуль не сложно переделать таким образом, чтобы конвейер был не на каждом разряде, а, например, на каждые 5 разрядов.
Меня удивляет бедность средств автоматической конвейеризации на сегодня. Перспективный HDL мог бы убедительно продемонстрировать свою полезность демонстрацией такого функционала. По-идее например в Chisel есть достаточные средства и для описания интерфейсов модулей, параметризованных глубиной конвейера, и для описания алгоритмов преобразования комбинационной логики в такие модули. Это же мега фишка, - описываем схему регулярным образом, а алгоритм расставляет регистры минимизируя длиннейший путь, вероятно нерегулярно, пересчитываясь после каждой правки исходника.
ну как сказать, ставим лишних регистров и врубаем ретайминг. Иногда помогает. Но мы не ищем легкий путей, только луты и триггеры, только хардкор xD
Автоматический ретайминг для генерации конвейера есть, правда мне известен только для ASIC, не для FPGA. Я его использую, он работает, хотя и медленее синтезирует, и не все его любят так как он снижает предсказуемость. Но он позволяет написать чисто комбинационный дизайн, потом сказать тулу: вот тебе 5 стадий конвейера, разложи в них как можешь.
См. https://picture.iczhiku.com/resource/eetop/shkedggoGHzkAmNC.pdf
ну в плис можно просто понатыкать на выходе регистров, запретить упаковку в аппаратный срл, включить ретайминг и иногда получается магия и он работает ) так-то это стандартная опция.
для сумматора , описанного как а+b оно естественно работать не будет
Так там собственно описывается способ@KeisN13 ! Если есть такая функция тулчейна, то здорово, но это во-первых, не переносимо, во-вторых, отчуждено от основного языка, условно в git-е схема отдельно, опции отдельно.
В-третьих, это специальный случай, который можно было бы расширять, будь описание интегрировано в язык... ну, я не знаю, конвейеризировать только часть схемы, если мы знаем, что часть входов меняться не будет. Или координировать выбор количества ступеней конвейера со сложным контекстом.
Почему нельзя поставить регистры на входы и на выходы суммматора? импульс записывает данные во входной регистр, задерживается на несколько тактов (когда данные на всех выходах разрядов будут стабильны) и записывает в выходной регистр.
Такая схема - это рассматриваемый случай поведенческого описания a+b . Кроме латентности, просто вставка регистров на вх и вых ни чего не даст.
Задержка (латентность) будет как минимум та же самая, но её можно будет значительно уменьшить как пытался подсказать Nansch.
Исходная и конвейеризированная конечная схема дают на выходе новый результат каждый такт. Конвейеризация позволила существенно уменьшить время такта ценой дополнительной latency и ресурсов. Ваша схема будет давать новый результат один раз в несколько тактов (т.е. будет некорректна), она будет иметь примерно такие же проблемы с delay, как исходная, при этом иметь бОльшую latency чем исходная, но в добавок она будет гораздо сложнее для анализа из-за multicycle констрейнтов.
Исходная и конвейеризированная конечная схема дают на выходе новый результат каждый такт
Именно так, с первым тактом появляется младший бит результата (суммы), и зачем он нужен? В статье не идёт речь о каком-то спецвычислителе где нужно как можно быстрее получить младший бит суммы, обычный сумматор, в котором нужны все биты суммы, напр. для АЛУ контроллера. Но даже и в случае спецвычислителя входной "конвеер" не нужен, все его биты, кроме одного, забиты "мусором", почему нельзя записать один входной бит разряда в регистр и всё. Выходной "конвеер" тоже ничего не даёт, кроме потребления, там тоже нужен только один бит. Если нужны младшие биты как можно раньше, то выходной регистр нужно разбить на секции и тактировать их с соответствующей задержкой. Автор предлагает секции из 5 бит, из этого можно предположить, что полный результат суммы можно получить в 5 раз быстрее приведенного автором решения.
Схема автора эффективна если данные поступают на вход в каждом такте конвеера, но об этом в статье ничего не сказано.
вот поставленная цель
И в этой заметке предлагаю вам погрузиться в небольшое исследование c реализацией конвейеризованного многоразрядного сумматора всего с 1 уровнем логики
...
...
В рамках статьи нам предстоит:
1. разработать схему многоразрядного сумматора с одним уровнем логики, т.е. максимально конвейеризированную версию.
Цель достигнута, задачи выполнены, все что кроме, ваши хотелки )
Именно так, с первым тактом появляется младший бит результата (суммы), и зачем он нужен?
А вот затем там и стоит столько регистров на входе и выходе, чтобы все биты появились одновременно, а не сначала младший.
наверное я не до конца понял, что хотел реализовать @Nansch
Рисунок бы сильно помог
На самом деле, кажется, что в простейшем сумматоре должно всё быстро переключиться и он посчитает чуть ли не со скоростью распространения сигнала по самому длинному пути. Так как нет памяти состояния и просто надо подождать устойчивого результата... Но нифига, оказывается оптимизировать надо, чтоб еще скорость поднять.
del
не туда
Выжимаем максимум из логики — сверхбыстрый, но прожорливый сумматор