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

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

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

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

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

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

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

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

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

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

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


Удачи! Rob.

а вот это вот вычитание/сложение одного и того же числа пока не дойдёт до конечного не заменяется разве умножением/делением?
взяв первую попавшуюся ссылку на 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/

Спасибо всем за ответы.
Согласен, что сумматор - самая тормозная часть и разбивать 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
но не уверен, что подходит для этих целей.

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

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

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

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

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

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

Всё, что мне нужно - это операция (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 битного блока. Второй уровень содержит меньше логики.
В общем, есть надежда, что с помощью внутрисхемной логики можно ускорить решение задачи во много раз.


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

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

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