ПЛИС для вычислений с длинной арифметикой Опции

[planetzeus]

Помогите пожалуйста с выбором.
Нужно делать вычисления с длинной арифметикой - до 8 тысяч бит. Т.е нужно простое АЛУ, но числа очень длинные.
Вычисления относительно простые - сложение, вычитание (сложение с отрицательным в обратном коде), сдвиг на бит и пара таких же длинных счетчиков.
Никаких умножений или делений. Т.е задаем начальные значения и и девайс должен складывать (вычитать) числа в зависимости от знакового бита, пока не дойдет до конечного или не найдет совпадения с заданным длинным числом.
На компьютере такие вычисления крайне медленные. На GPU тоже, так как в любом случае сложение вычисляется группами по 64 бита.
Поэтому подумал, что идеальный вариант - собственное АЛУ, которое делает одну операцию со всеми битами за такт. Насколько я понимаю, самый правильный вариант - ПЛИС.
Желательно делать перебор с максимальной скоростью - к примеру если есть возможность 1 или 2 Ггц, то именно это и нужно.
Почитал про ПЛИС и есть желание разобраться, но не понятно с какого девайса начинать искать. Не хотелось бы покупать плату, которая в итоге не подойдет для этой задачи.
Мне не нужны разные интерфейсы, USB и может быть микроконтроллер на плате пригодится, но остальное по большому счету не очень важно.
Посоветуйте пожалуйста с чего начинать и какую плату для разработки выбрать. Самый главный критерий - максимальная производительность и возможность "зашить" свою логическую схему.

[x736C]

8000 тыс за такт на частоте 1 гиг — забудьте.

Можно подумать о комактных последовательных сумматорах, разместив их в ПЛИС максимальное количество. Имхо это будет наиболее быстро с т.з. скорости счета. Числа перемещать из блока в блок памяти.

Это в том случае, если все время необходимо параллельно считать, а не единовременно посчитать одно единственное выражение.

[planetzeus]

8000 тыс за такт на частоте 1 гиг — забудьте.

Я немного неправильно выразился, под тактом имел в виду минимальное время, т.е не последовательную работу с битами, а одновременно со всеми. В ПЛИС я даже не новичок, пытаюсь стать хотя бы новичком, поэтому немного колхозно объясняю.
Вот есть процессоры Intel, на борту у них есть регистры EAX, EBX и тд. Я хотел бы сделать на ПЛИС такую же схему - регистры, но только очень длинные. С внешней памятью работать нет необходимости. Т.е только последовательную загрузку 4 таких регистров, последовательную выгрузку, флаговый бит результата и все. Все остальные операции перебора значений автономные. Запустил и он работает только с этими регистрами, пока не сойдется условие равенства с конечным регистром. Точнее 0 как результат сложения.

[x736C]

Ошибся. Имелось в виду 8 тыс., а не 8000 тыс.

ПЛИС в силу своей универсальности работает существенно медленнее жестких полупроводниковых структур, выполненных по одной технологической норме. Есть оценки, что в 5-6 раз медленнее. Современные процессоры и GPU существенно обгоняют ПЛИС по технологии изготовления. Плюс они имеют значительно более высокие частоты работы в силу узкой специализации. Банальные вещи.
ПЛИС позволяет избавиться от накладных расходов и распараллелить вычисления. Максимальная частота работы вычислительной структуры на ПЛИС может быть не более ~500 МГц. А дальше она будет сильно зависеть от задержек сигналов. Попытка взаимозависимо переключить 8000 тыс триггеров одновременно уронит максимальную частоту очень сильно. Поэтому резонно было бы сделать компактный последовательный сумматор, выжав максимальную частоту работы. Далее получившийся сумматор скопировать максимально возможное количество раз. Блоки памяти встроены в ПЛИС, их большое количество и они имеют хорошее время доступа.

Такой подход используется при поиске чисел Мерсенна. Умножение огромных чисел на полиномиальном умножителе с помощью БПФ. В ПЛИС хорошо распараллеливается.

Сообщение отредактировал x736C - Nov 27 2017, 16:43

[RobFPGA]

..
Желательно делать перебор с максимальной скоростью - к примеру если есть возможность 1 или 2 Ггц, то именно это и нужно.
Почитал про ПЛИС и есть желание разобраться, но не понятно с какого девайса начинать искать. Не хотелось бы покупать плату, которая в итоге не подойдет для этой задачи.
..

Максимум что может получится выжать для такого рода задач это ~100 MHz и то не просто так.
Для сумматора критичным является задержки переноса. Чем длиннее аккумулятор тем задержка больше. Типичные скорости работы для 32-64 бит сумматора на логике - 200-400 МHz в зависимости от крутизны FPGA. В Вашем же случае (обратная связь от результата предыдущего цикла) придется разбивать сумматор на блоки, вставлять pipeline регистры и городить схемы обработки группового переноса. Так что 3-4 такта на цикл суммирования как минимум.
Так что GHz тут и близко не лежали. Такую грустную картину может сгладит только то что таких сумматоров в приличную FPGA можно напихать много так что в эквиваленте может и получите ускорение.

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


Удачи! Rob.

[_pv]

а вот это вот вычитание/сложение одного и того же числа пока не дойдёт до конечного не заменяется разве умножением/делением?
взяв первую попавшуюся ссылку на aribtrary precision: https://possiblywrong.wordpress.com/2015/10...rithmetic-in-c/
на ПК сложение двух рандомных чисел с 2500 десятичными знаками получилось 1000000 раз за секунду, а умножение в 250 раз медленнее.
то есть если складывать более 250 раз, то умножать будет быстрее?
в какой-нибудь нормальной библиотеке хотя бы малость оптимизированной под конкретные современные процессоры оно ещё в несколько раз быстрее получится, а если ещё каким-нибудь openMP распараллелить на 4-8 ядер, то ещё на порядок.
плюс есть ещё более быстрые алгоритмы умножения длинных чисел, а не O(N^2).
реализация в лоб сумматора на 8000бит на ПЛИС сильно быстрее работать не будет.
у амазона процессорные мощности арендуйте сколько надо и считайте.
https://aws.amazon.com/ru/ec2/pricing/on-demand/

[planetzeus]

Спасибо всем за ответы.
Согласен, что сумматор - самая тормозная часть и разбивать 8000 бит на части в любом случае придется.
Думаю, что можно оптимизировать маленькие блоки по несколько бит таблицей истинности или что-то типа этого.
Я пробовал реализовать этот алгоритм на CPU. Маленькие числа по 64 бит считаются к примеру чуть меньше секунды. Но то же самое число в виде длинного (т.е реально число маленькое, но операции выполняем над всеми битами блоками по 64 бит) считается примерно в 1000 раз медленнее. Пробовал сугубо для проверки арифметики с битами.
Сначала хотел попробовать на GPU, у меня 1080Ti, но потом подумал, что в любом случае это операции над блоками. Ну и процессор есть процессор - обработка команд, работа с памятью. Поэтому подумал, что ПЛИС возможно будет в данном случае намного быстрее. Например сдвиг вправо на бит и установка нулевого бита в 1 (умножение на 2 и +1) это вообще можно сделать за один реальный такт. Т.е один регистр содержит все биты числа, а второй регистр будет сразу содержать это число * 2 + 1. Проблема скорости только в сумматоре.
Поглядывал вот на этот девайс
www.amazon.com/dp/B00N3LHRYU?m=A2D3CNDMUB3UW1&ref_=v_sp_detail_page
www2.hdl.co.jp/en/plink/xcm-111.html
но не уверен, что подходит для этих целей.

[_pv]

тогда уж
https://www.aliexpress.com/item/Xilinx-FPGA...2799960711.html

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

[ViKo]

Это что, майнеры криптовалюты ищут черный ход?

[Shivers]

Согласен, что сумматор - самая тормозная часть и разбивать 8000 бит на части в любом случае придется.

Погуглите про систему остаточных классов (СОК). Специально придумано для распараллеливания арифметики с разрядностью в сотни и тысячи бит. Придумано кстати уже давно, лет 50 назад, и используется столько же - в спец. задачах. Главный недостаток СОК - хорошо работает только умножение и сложение, с делением проблемы. Но Вам то как раз сложение и нужно, я так понял.

[_Ivan_33]

А что мешает написать это все на opencl под видеокарту, протестировать, а затем переписать код под ПЛИС, протестировать на хостинге, не покупая дорогие ПЛИС и карты и сравнить результаты.
Получится и быстрее, и денег меньше и.т.д. Если профит в ПЛИС будет виден - заморочиться с реализацией на HDL языках.

[AVR]

Не увидел, чтобы кто-то спросил автора темы: зачем это всё? Может реально решить поставленную задачу иными способами.

[planetzeus]

А что мешает написать это все на opencl под видеокарту, протестировать, а затем переписать код под ПЛИС, протестировать на хостинге, не покупая дорогие ПЛИС и карты и сравнить результаты.

Всё, что мне нужно - это операция (2x+1), инкремент и сумма двух чисел.
Я уже сказал, операция 2x + 1 на логике в любом случае будет быстрее, так как это можно сделать за единицу времни. Т.е есть на входе схемы число X из 8000 бит, на выходе X*2+1, простая логическая схема.
Ни CUDA, ни OpenCL API не позволяют такого. Как можно другим способом сделать сдвиг 8000 бит за одну операцию? На CUDA (или OpenCL) можно распараллелить на блоки вычисления, но не разбить длинное число на биты и вычислять куски отдельными блоками/потоками, так как синхронизировать потом все это совсем нетривиальная задача.
Суммирование можно попробовать оптимизировать логикой. По моему это в любом случае будет быстрее, чем вычислять суммы на GPU блоками. Например разбить все биты на группы по 8 бит и складывать байтами.
Я не спец в электронике, вот например схема:

после такого сумматора первого уровня получаем два числа, которые затем складываем как в обычном сумматоре с итерациями и переносами...
если A = 2543 , а B = 1052, два блока по 8 бит
A = (9)(239)
B = (4)(28)
то после первого уровня получаем два числа
C1 = (13)(11)
C2 = (1)(0) (здесь всегда будут только 1 или 0)
Складываем сумматором второго уровня (с циклом если нужно)
Получаем (14)(11) = 3595
Первый уровень сумматора сразу выдает результат без необходимости переносов в пределах 8 битного блока. Второй уровень содержит меньше логики.
В общем, есть надежда, что с помощью внутрисхемной логики можно ускорить решение задачи во много раз.

Не увидел, чтобы кто-то спросил автора темы: зачем это всё? Может реально решить поставленную задачу иными способами.

Иного способа не нашел, к сожалению. Просто исследования, хочу попробовать решить эту задачу на ПЛИС. Компьютер решает задачу, но очень медленно.

[AVR]

Иного способа не нашел, к сожалению. Просто исследования, хочу попробовать решить эту задачу на ПЛИС. Компьютер решает задачу, но очень медленно.

Не, не то хотел спросить. Во имя чего такая задача решается в принципе? Дичь невиданная
Или нет возможности раскрыть конечное предназначение?

[ViKo]

Инкрементировать 8000-разрядное число (т.е. + 1) ничуть не проще, чем сложить два 8000-разрядных числа.
В отличие от умножения на 2. Там и сдвигать не надо. Выдавайте биты со сдвигом, и все.

[blackfin]

Я не спец в электронике, вот например схема:
...
после такого сумматора первого уровня получаем два числа, которые затем складываем как в обычном сумматоре с итерациями и переносами...

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

[planetzeus]

Не, не то хотел спросить. Во имя чего такая задача решается в принципе? Дичь невиданная
Или нет возможности раскрыть конечное предназначение?

Почему дичь? например в RSA тоже используется длинная арифметика. У меня задача связана с другой темой, но также немного имеет отношение к криптографии.
Мне нужно быстрое АЛУ для длинных чисел, что тут дикого?) Микропроцессоры, на мой взгляд, в любом случае медленнее, чем быстрая логика

[Alex77]

Всё, что мне нужно - это операция (2x+1), инкремент и сумма двух чисел.
Я уже сказал, операция 2x + 1 на логике в любом случае будет быстрее, так как это можно сделать за единицу времни. Т.е есть на входе схемы число X из 8000 бит, на выходе X*2+1, простая логическая схема.

Почему-то мне кажется что некорректно описано задание.
"X*2+1" - сиё означает умножение на 2 те сдвиг и пририсовывание бита 1.
Всё это реализуется "статическим сдвигом (т.е. реального сдвига нет)" и добавления вечной 1-цы.
Таким образом схема будет работать на максимальной скорости в 500МГц.

А на словах задание звучит как "А+Б+1".
Что Автору требуется ?

[blackfin]

Мне нужно быстрое АЛУ для длинных чисел, что тут дикого?

Вы не сказали, что нужно делать с полученной суммой двух длинных чисел. Если это однократная операция, то вполне вероятно, что запись/чтение в/из ПЛИС как раз и будут определять скорость всего алгоритма в целом. Как вы собираетесь загружать в ПЛИС 8000-разрядные числа?

[planetzeus]

"X*2+1" - сиё означает умножение на 2 те сдвиг и пририсовывание бита 1.
Всё это реализуется "статическим сдвигом (т.е. реального сдвига нет)" и добавления вечной 1-цы.
Таким образом схема будет работать на максимальной скорости в 500МГц.

А на словах задание звучит как "А+Б+1".
Что Автору требуется ?

Именно! Нужна максимальная скорость - все операции, которые можно реализовать схемой вход->[схема]->выход (с нужным значением). Операций нужно несколько, я ж написал. (2х+1) - одна операция. А+Б - другая операция. Сравнение с 0 - третья операция, которая тоже решается логической схемой.

Мне требуется только грамотный совет) Какой девайс выбрать чтобы все это пробовать? Т.е чтобы хватило логических элементов, чтобы была максимальная скорость. Девайсы недешевые, не хотелось бы потратить деньги и понять, что полностью реализовать не получится потому что мало элементов, или другие ограничения.

Как вы собираетесь загружать в ПЛИС 8000-разрядные числа?

Я думаю последовательно. Т.е если будут например 4 регистра по 8000 бит, то 2 внешних пина на выбор регистра, один пин для data, один на синхронизацию. Еще раз говорю, я не спец в электронике. Максимум, что я делал - это RPi и на уровне "помигать светодиодом". Вот хочу освоить ПЛИС, спрашиваю у людей с опытом совета.

[blackfin]

Мне требуется только грамотный совет. Какой девайс выбрать чтобы все это пробовать? Т.е чтобы хватило логических элементов, чтобы была максимальная скорость.

Выбирайте Stratix 10. Его скорости вам точно хватит..

[jojo]

Выбирайте Stratix 10. Его скорости вам точно хватит..

Или Xilinx Kintex-7, Virtex-7 и более новые Ultrascale. Я бы взял что-то из середины семейства примерно на 400...500 тыс. триггеров. Потому что больше не потянет система охлаждения и питания отладочной платы.

[blackfin]

Или Xilinx Kintex-7, Virtex-7 и более новые Ultrascale. Я бы взял что-то из середины семейства примерно на 400...500 тыс. триггеров. Потому что больше не потянет система охлаждения и питания отладочной платы.

Да всё потянет! Не болтайте ерундой!!! DK-U1-VCU1525-A-G.....

[jojo]

Да всё потянет! Не болтайте ерундой!!! DK-U1-VCU1525-A-G.....

Кстати, да, это тоже вариант для больших чисел.. Да что там, для любых чисел! Ток по VCCINT под 80А, если я правильно понял, и активное охлаждение. Надо брать.

[_Ivan_33]

И все-таки по поводу девайса, посмотрите на решения серверные, отработайте там - https://aws.amazon.com/ru/ec2/instance-types/f1/
Это сэкономит деньги, ибо если не понравится плис, то уйдете на что-то другое, заплатив пару баксов за час.

[Realking]

Вот хочу освоить ПЛИС, спрашиваю у людей с опытом совета.

Отличная задача для освоения ПЛИС )

[RobFPGA]

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

Именно! Нужна максимальная скорость - все операции, которые можно реализовать схемой вход->[схема]->выход (с нужным значением). Операций нужно несколько, я ж написал. (2х+1) - одна операция. А+Б - другая операция. Сравнение с 0 - третья операция, которая тоже решается логической схемой.

Было бы интересно увидеть алгоритм вычисления.
А так я уже выше писал по грубой прикидке для 8K бит надо будет 3-4 такта (200-300 MHz) на одну операцию -
получить цикл на операцию 10нc еще надо будет попотеть. Для начала значения в 100-20 нс на цикл более реалистично

Мне требуется только грамотный совет) Какой девайс выбрать чтобы все это пробовать? Т.е чтобы хватило логических элементов, чтобы была максимальная скорость. Девайсы недешевые, не хотелось бы потратить деньги и понять, что полностью реализовать не получится потому что мало элементов, или другие ограничения.

Берите ... ModelSim, Vivado, Quartus большего Вам в ближайший месяц-два-три и не понадобится.
А затем уж Вы и сами сможете ответить на этот вопрос на какой FPGA Вам будет выгодно реализовать Ваш алгоритм.

Конечно если очень хочется то можно сразу брать плату на Virtex UltarScale+ или Aria10 -не ошибетесь - к тому же мигание светодиода на плате в 10-15K $ особенно завораживающе выглядит.

Удачи! Rob.

[AVR]

Почему дичь? например в RSA тоже используется длинная арифметика. У меня задача связана с другой темой, но также немного имеет отношение к криптографии.
Мне нужно быстрое АЛУ для длинных чисел, что тут дикого?) Микропроцессоры, на мой взгляд, в любом случае медленнее, чем быстрая логика

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

Я бы пошел дальше и посоветовал тут для начала набросать алгоритм, чтобы он работал в матлабе/питоне/что_там_еще, чтобы было видно что всё успешно разбилось на много тактов, и результат такой же как и у "медленной версии на процессоре". И вот когда всё будет разбито на маленькие стадии, вот тогда можно пытаться это сделать на языке Verilog HDL.

[Fat Robot]

Использовать CLA.

Если есть ограничения на pipeline delay, то нужно балансировать между разрядностью элементарного сумматора и длиной цепочки переносов для достижения максимальной Fclk. Например, использование DSP-блоков позволит сделать быстрый элементарный сумматор для CLA, скажем, разрядностью 48х8 и, как следствие, цепь переносов длиной ceil{8000/(48х8)} ~= 20.

Если ограничений на pipeline delay в сумматоре не накладывается, то всё становится совсем просто, и работать будет на околопредельных частотах ПЛИС при любом внятном описании конвеера.

В одно действие задачка в общем-то. Вполне подойдет для собеседований на конкурс "творчество юных".

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

[krux]

planetzeus
Перенос в FPGA "только АЛУ", как вы это описали - не даст сколько-либо ценного результата.
При переносе в FPGA необходимо вынести в него определенный блок, довольно большой, который осуществляет определенную обработку (заведомо более 10...20 операций) по заранее известному алгоритму. В этим случае можно будет ставить в качестве целей, например, "производительность блока на гарантированном уровне не менее стольких-то обработанных бит на такт" и выстраивать подобные вещи.
Если вы прямо сейчас обладаете только навыками программиста - то для начала вам необходимо зачеркнуть всё, что вы ранее знали про обработку данных при помощи микросхем, и сменить парадигму с "у меня есть жесткий набор инструкций для ЦПУ или АЛУ" на "я могу сделать столько нужных мне действий за такт, сколько мне нужно". Крамольный смысл здесь в чем: матерого программиста сложно переучить на сколь-нибудь годного HDL-щика, в силу того, что программиста с рождения учили что на ЦПУ может выполняться только одна инструкция одновременно. А в HDL можно сделать одновременным выполнение стольких инструкций, сколько нужно. Следующий момент связан с тем, что "матерый программист со стажем" не понимает, что язык описания архитектуры HDL - это не язык программирования. Приходится долго и упорно объяснять, что единственно правильным решением для HDL - является реализация конечного автомата. Что для этого автомата необходимо заранее наметить условия изменения состояния, действия, выполняемые при изменении состояния. Ибо программистам как правило пофиг, потому что они считают что "ежели я не менял значение переменной, то оно должно сохранять свое состояние" по умолчанию, однако в HDL умолчания ведут к провалу; ну и про то, что в результате перехода конечного автомата через несколько состояний что-то где-то может измениться - им тоже плевать. Поначалу. Потом они просто сдаются.
Поэтому.
При переходе от языков программирования высокого уровня необходимо обязательно "слезть с дерева", и перестать считать, что все что ты пишешь на языке HDL - это примерно то же самое что и на C-ях, к примеру.
Это не так, от слова "совсем".
Поэтому у вас два пути - либо найти человека, который в ладах с HDL, и сможет внятно сформулировать какой же вычислительный блок вам сможет помочь, и что для этого нужно, либо "встрять надолго" начав изучение с азов.

Я думаю последовательно. Т.е если будут например 4 регистра по 8000 бит, то 2 внешних пина на выбор регистра, один пин для data, один на синхронизацию.

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

зы. полагаю, что если ваш изначальный алгоритм полностью "развернуть", или "по-программистски сделать unroll & inline", то биты конечного результата всегда будут выражаться через биты входных данных. Тогда в "блоке обработки", который планируется к переносу на FPGA нужно эту матрицу (либо несколько матриц) описать, После чего уже пытаться оптимизировать сложность этих действий в раскладках по тактам, и т.д. о чем вам опять-таки сможет объяснить найденный вами человек, который в ладах с HDL

ззы. если у вас есть выход на ИПМ Келдыша РАН, (и если это будет для вас достаточно), то там есть гибридные варианты суперкомпьютеров с интегрированными мульти-модулями ПЛИС, на очень специфическом языке программирования, из семейства C. При этом не придется изучать HDL, но думать конкуррентно-параллельно при создании алгоритма всё равно придется.

[planetzeus]

в FPGA нельзя думать последовательно.
нужно думать конкуррентно-параллельно.

Спасибо за развернутый комментарий.

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

На ЯП простая операция N == 0 превращается в очень непростую (по времени), если наше N состоит из 8000 бит, а в терминах логики - это большая куча элементов OR, которая практически сразу (с небольшой задержкой в переключениях логики) может выдать либо 1 или 0. Может колхозно рассуждаю, но примерно так)

По моему мнению ни программистами, ни электронщиками не рождаются. Ими ведь как-то становятся)
Есть задача, есть немного времени на эксперименты/самообразование. Почему бы не попробовать? Тем более тема мне интересна и задача обучения работе с ПЛИС не сводится только к этой конкретной задаче. Возможно потом появятся новые задачи. Просто хотелось в начале пути элементарно спросить - а в какую сторону ходить? Попытался максимально как мог описать задачу.

И все-таки по поводу девайса, посмотрите на решения серверные, отработайте там - https://aws.amazon.com/ru/ec2/instance-types/f1/

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

[iiv]

Помогите пожалуйста с выбором.
Нужно делать вычисления с длинной арифметикой - до 8 тысяч бит. Т.е нужно простое АЛУ, но числа очень длинные.

Вы писали, что у вас есть 1080TI. Она в пике дает на сложениях или вычитаниях с 32 битными числами около 5е12 операций в секунду. Если у вас по сути вашей задачи есть возможность выполнять несколько операций над вашими длинными 8кбитными числами полностью не зависимо и параллельно, то как раз 16 тредов в параллель позволит вам выполнить 16 таких операций на регистрах, то есть у вас есть шанс приблизиться к пиковой производительности карты. То есть одно такое сложение у вас будет выполняться за время около 0.1нс.

Если взять стратикс по стоимости соизмеримый с 1080ti, то в него вы сможете положить около 100 таких сумматоров, если делать в лоб и работать они будут в лучшем случае с 100, а то и с 50МГц частотой. То есть в общем примерно те же яйца, только в профиль.

То есть пользовать или не пользовать GPU или ПЛИС будет зависеть только от того, как у вас идут сами эти вычисления. Если вы решите по USB в плиску или с PCIe на графическую карту скармливать эти операции, то скорость будет определяться не скоростью плиски или графической карты, а дыркой, через которую вы это все будете протаскивать и будет как минимум на пару порядков медленнее. Вероятность того, что ваш алгоритм со всеми промежуточными данными поместится в 11GB, которые есть на халяву на борту вашей графической карты и нескольких десятков мегабайт под код программы несравненно выше, чем если вы будете заморачиваться с плиской.

ЗЫ: плиску для быстрых вычислений имеет смысл использовать только если на борту графической карты нет аппаратно реализованных операций, а в вашем случае, 32 битные сложения в графических картах наличествуют, и заморачиваться с плиской ИМХО нет смысла.

[krux]

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

На ЯП простая операция N == 0 превращается в очень непростую (по времени), если наше N состоит из 8000 бит, а в терминах логики - это большая куча элементов OR, которая практически сразу (с небольшой задержкой в переключениях логики) может выдать либо 1 или 0. Может колхозно рассуждаю, но примерно так)

Нет столько пинов - и не нужно, эти 8000 бит быстрее будут введены через какой-нибудь PCIe или Ethernet.
тем более.
при адаптации алгоритма с ЯП на HDL - если есть возможность определить в общем виде чему будет равен каждый из 8000 выходных бит после 2000 операций из входных данных - это и будет самым правильным подходом "в лоб", т.е. нулевым приближением: описать 8000 уравнений, с определением каждого выходного бита через множество действий с входными.

ещё добавлю, бывает случается, при попытке уложить "классический" алгоритм решения задачи на ЦПУ -> при попытке адаптации его на ПЛИС даёт совершенно непредсказуемый результат.
К примеру, с алгоритмами-кандидатами на хэш SHA3 случилось, что перебор при помощи FPGA выполняется на 6 порядков быстрее, чем на ЦПУ, из-за чего их на втором этапе забраковали, и к последнему этапу остался фактически один алгоритм-губка Кeccak.

[planetzeus]

То есть пользовать или не пользовать GPU или ПЛИС будет зависеть только от того, как у вас идут сами эти вычисления. Если вы решите по USB в плиску или с PCIe на графическую карту скармливать эти операции, то скорость будет определяться не скоростью плиски или графической карты, а дыркой, через которую вы это все будете протаскивать и будет как минимум на пару порядков медленнее. Вероятность того, что ваш алгоритм со всеми промежуточными данными поместится в 11GB, которые есть на халяву на борту вашей графической карты и нескольких десятков мегабайт под код программы несравненно выше, чем если вы будете заморачиваться с плиской.

Вот тут спорить даже не буду. Очень возможно что я не прав и на моей GPU будет та же скорость или даже больше. Попробую все-таки написать алгоритм на CUDA и проверить, но сравнить не с чем. С ПЛИС решил заморочиться из-за чисто интуитивного взгляда. Операция типа *2 (для 8 тыс. бит) на GPU нужно эмулировать. 8000 бит/32 ~ 250 операций. Все прочие операции такие же, почти везде нужен цикл и обход всех 250 32-битных чисел. Тогда как логикой это практически сразу.

Нет столько пинов - и не нужно, эти 8000 бит быстрее будут введены через какой-нибудь PCIe или Ethernet.

Говорю ж, обмен данными совсем не главная операция. Загрузили числа, перебираем. Можно загрузить такой диапазон, что перебирать в поисках подходящих значений будет сутками. Поэтому главная цель - скорость перебора в поиске, а не обмен. Ради загрузки 4 значений по 8 тыс. бит раз в сутки - нет необходимости в высокоскоростных интерфейсах.

[AVR]

С ПЛИС решил заморочиться из-за чисто интуитивного взгляда. Операция типа *2 (для 8 тыс. бит) на GPU нужно эмулировать. 8000 бит/32 ~ 250 операций. Все прочие операции такие же, почти везде нужен цикл и обход всех 250 32-битных чисел. Тогда как логикой это практически сразу.

А GPU разве не "логика"? Такая же самая логика, только фиксированная, пользователь лишь задает программу этой фиксированной логике.
Только вот если в ПЛИС задействуются цепи переноса, то откуда же там возникнет "практически сразу"? Ну можно засунуть в рот 5 бутербродов. Только ПЛИС это когда сто ртов независимо едят сто бутеров.
Я вот кое что делал на Spartan-6, ресурсов куча, а ячеек с переносом не осталось. Переделал на встроенных умножителях - влезло. Может для суммирования и сдвига тоже можно нечто подобное провернуть, но не факт что оно таки не сожрет "все" с переносом. Я с ПЛИС давно работаю, но некоторые моменты у меня остаются откровенно слабыми, пробелы.

ЗЫ: плиску для быстрых вычислений имеет смысл использовать только если на борту графической карты нет аппаратно реализованных операций, а в вашем случае, 32 битные сложения в графических картах наличествуют, и заморачиваться с плиской ИМХО нет смысла

Вот тут согласен, если все равно большое число придется разлохматить на кусочки, то сомневаюсь что ПЛИС даст выигрыш. Если конвейеризовать это на те же 32/64-битные части, то даже если задержка не критична (а это вроде так), то будет ли выигрыш относительно GPU?

[planetzeus]

Только вот если в ПЛИС задействуются цепи переноса, то откуда же там возникнет "практически сразу"?

Для суммы - да есть переносы, но для 2x+1, к примеру, нет.
Повторюсь, я не утверждаю ничего, допускаю что Вы правы. Но даже если скорость будет сравнима с GPU, я бы предпочел находить нужный мне ряд чисел на FPGA.
Мне сложно сравнивать. Процессор, который интерпретирует команды и в цикле работает с массивом 32-битных чисел или логическая схема внутри FPGA, оптимизированная под конкретную задачу.
На GPU я могу распараллелить задачу на разные диапазоны, но вот как распараллелить суммирование или сдвиг нескольких тысяч бит на разные блоки/потоки не представляю.

Я вот кое что делал на Spartan-6, ресурсов куча, а ячеек с переносом не осталось. Переделал на встроенных умножителях - влезло.

Именно для этого я и создал эту тему. Чтобы хотя бы определиться в какую сторону копать. Поскольку опыта у меня 0, то оценить сколько нужно логических элементов чтобы сделать сумматор для двух 8000-битовых чиел - загадка.

В общем-то я уже сделал первые выводы. Попробую для начала написать на Verilog схему в эмуляторе. Ну и присмотрюсь к облакам вместо реальной железки.

[jojo]

Именно для этого я и создал эту тему. Чтобы хотя бы определиться в какую сторону копать. Поскольку опыта у меня 0, то оценить сколько нужно логических элементов чтобы сделать сумматор для двух 8000-битовых чиел - загадка.

На вдаваясь в зависимости данных вокруг обсуждаемого алгоритма,

На примере Xilinx 1 слайс вычисляет 4 бита суммы, всего битов 8000, значит, слайсов 2000 на ядро.
Например, в Kintex 325T 50950 слайсов, т.е. 25 ядер.
25*500МГц = 12500 млн оп/c.
25*2*8000 = 400000 триггеров, впритык, значит, ядер меньше
Конвейер 250 этапов.

Если в GPU 3000 ядер на 2000 МГц суммируют по 32 бита, то будет
3000*2000*32/8000 = 24000 млн операций /с, и это без учёта влияния архитектуры.

Таким образом, порядок величин один и тот же.

[blackfin]

На вдаваясь в зависимости данных вокруг обсуждаемого алгоритма, ...

При тех же самых условиях:

Arria 10 - 10АХ115H1F34I1SG:

Total ALMs = 16250
Total registers = 24250
Fmax = 518 MHz

Хотя для Arria 10 лучше, КМК, суммировать не по 8*4, а по 6*6 бит..

[x736C]

Кстати, да, это тоже вариант для больших чисел.. Да что там, для любых чисел! Ток по VCCINT под 80А, если я правильно понял, и активное охлаждение. Надо брать.

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

[Plain]

Поскольку опыта у меня 0, то оценить сколько нужно логических элементов чтобы сделать сумматор для двух 8000-битовых чиел - загадка.

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

[blackfin]

25*2*8000 = 400000 триггеров, впритык, значит, ядер меньше
Конвейер 250 этапов.

Результат суммирования нужно тоже где-то хранить, плюс на каждую ступень конвейера нужен один бит переноса.

Итого:

25*(3*8000+250) = 25*24250 = 606250 триггеров.

[Shivers]

Я там выше уже писал про систему остаточных классов (СОК). Все что нужно - сконвертировать 8000 битные числа в СОК, а потом уже умножение и сложение будет представлять из себя кучу параллельных схемок с длинной переноса не более 10. И в конце результат еще надо сконвертировать обратно из СОК в бинарный код. Сравните - длинна переноса 8000 и длинна переноса 10, есть разница? Для этого СОК и был придуман.

[jojo]

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

Касательно той платы выше речь скорее про Vivado.
Vivado вытянет, он вообще молодец сейчас стал.

А питания стало маловато. Что такое 80 А по VCCINT, это только на логические ресурсы без BRAM и DSP. Как делал Xilinx отладочные платы - балалайки маломощные, так и продолжает.

[blackfin]

Все что нужно - сконвертировать 8000 битные числа в СОК, а потом уже умножение и сложение будет представлять из себя кучу параллельных схемок с длинной переноса не более 10. И в конце результат еще надо сконвертировать обратно из СОК в бинарный код. Сравните - длинна переноса 8000 и длинна переноса 10, есть разница?

Это если операций суммирования и умножения много. Но ТС не сказал сколько их должно быть? А если ему для каждой пары чисел нужно одно-два суммирования и одно-два умножения, то операции конвертирования окажутся более затратными, КМК.

[jojo]

Результат суммирования нужно тоже где-то хранить, плюс на каждую ступень конвейера нужен один бит переноса.

Итого:

25*(3*8000+250) = 25*24250 = 606250 триггеров.

Да, я даже не спорю. И подробностей этих миллион.
Ещё в моей схеме маячат затраты на сдвиговые регистры на SRL или BRAM. Тем не менее, дело интересное и оно вроде бы в общем может получиться.

[blackfin]

Тем не менее, дело интересное и оно вроде бы в общем может получиться.

Так я привел уже результаты P&R..

[vladec]

И все таки, почему как предлагает Shivers не хотите использовать арифметику в остаточных классах, для данной задачи, вроде как по прямому назначению?

[Александр С.]

Когда-то Mentor Graphics агитировал всем делать ASIC, вместо FPGA, дескать достаточно крупный техпроцесс окажется не сильно дорогим.
Может и вам взять корку RISC-V процессора, приладить к нему паровозик из нужного количества сумматоров и заказать или в Новосибирске на НЗПП по 3 мкм техпроцессу или вЗеленограде/наТайване по субмикронному процессу если цена устроит.

Кстати, интересно какой тактовой частоты можно достичь при 3 мкм или при Зеленоградском техпроцессе?

Кстати, нашел по ATMega тех процесс и частоты:
1997-2001 первое поколение AVR 0,5мкм (8Мгц)
2002-2014 второе поколение AVR 0,35 мкм (16Мгц@5В)
2015 - новое поколение tinyAVR по технологии 130нм, 16МГц, при сохранении 5В питания, 1,8-5,5В
2015 новое поколение megaAVR с суффиксом "B" по технологии 130нм, 20МГц, при сохранении 5В питания, 1,8-5,5В

Насколько у меня выходило Altera FPGA длинные сложные операции делали на частоте до 60 МГц (Stratix3, CycloneV). Не знаю почему именно эта магическая цифра у меня вечно фигурировала, но как то так... Но на Stratix3 была по факту ассинхроная логика без конвейера, на на CycloneV синхронная но алгоритм был чужой, возможно не оптимальный

За океаном ПЛИСы сильно дешевле, если все таки решитесь последнюю Arria/Stratix использовать - может проще ее купить уже на плате(отладочной) из-за океана

Кстати, есть же еще ПЛИС Achronix - с дико большой емкостью(1Милион LUT): https://www.achronix.com/product/speedster22i/ - на хабре есть статья - можете списаться с автором, может согласится вашу прошивку на плате запустить...

Сообщение отредактировал Александр С. - Dec 14 2017, 08:01

[jojo]

Насколько у меня выходило Altera FPGA длинные сложные операции делали на частоте до 60 МГц (Stratix3, CycloneV). Не знаю почему именно эта магическая цифра у меня вечно фигурировала, но как то так...

Почему 60, мало.
С конвейером 400-500 выходит, смотря что.

[iosifk]

Кстати, интересно какой тактовой частоты можно достичь при 3 мкм или при Зеленоградском техпроцессе?

Кстати, нашел по ATMega тех процесс и частоты:
1997-2001 первое поколение AVR 0,5мкм (8Мгц)
2002-2014 второе поколение AVR 0,35 мкм (16Мгц@5В)
2015 - новое поколение tinyAVR по технологии 130нм, 16МГц, при сохранении 5В питания, 1,8-5,5В
2015 новое поколение megaAVR с суффиксом "B" по технологии 130нм, 20МГц, при сохранении 5В питания, 1,8-5,5В

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