реклама на сайте
подробности

 
 
4 страниц V  < 1 2 3 4 >  
Reply to this topicStart new topic
> ПЛИС для вычислений с длинной арифметикой
planetzeus
сообщение Nov 28 2017, 18:01
Сообщение #31





Группа: Участник
Сообщений: 9
Регистрация: 27-11-17
Пользователь №: 100 387



Цитата(krux @ Nov 28 2017, 21:09) *
в FPGA нельзя думать последовательно.
нужно думать конкуррентно-параллельно.

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

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

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

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

Цитата(_Ivan_33 @ Nov 28 2017, 16:55) *
И все-таки по поводу девайса, посмотрите на решения серверные, отработайте там - https://aws.amazon.com/ru/ec2/instance-types/f1/

В общем-то решение с облаком интересное и для оценки наверное очень даже подходящее. Буду курить в этом направлении. А насчет девайса - для экспериментов хотелось бы что-то в районе $500 - $1000, чтобы можно было экспериментировать не только на этой задаче, но и возможно на других.
Go to the top of the page
 
+Quote Post
iiv
сообщение Nov 28 2017, 18:23
Сообщение #32


вопрошающий
*****

Группа: Свой
Сообщений: 1 631
Регистрация: 24-01-11
Пользователь №: 62 436



Цитата(planetzeus @ Nov 27 2017, 20:18) *
Помогите пожалуйста с выбором.
Нужно делать вычисления с длинной арифметикой - до 8 тысяч бит. Т.е нужно простое АЛУ, но числа очень длинные.

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

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

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

ЗЫ: плиску для быстрых вычислений имеет смысл использовать только если на борту графической карты нет аппаратно реализованных операций, а в вашем случае, 32 битные сложения в графических картах наличествуют, и заморачиваться с плиской ИМХО нет смысла.
Go to the top of the page
 
+Quote Post
krux
сообщение Nov 28 2017, 18:25
Сообщение #33


Профессионал
*****

Группа: Свой
Сообщений: 1 579
Регистрация: 2-07-12
Из: дефолт-сити
Пользователь №: 72 596



Цитата(planetzeus @ Nov 28 2017, 21:01) *
Под последовательной загрузкой я имел в виду, что нет возможности сразу параллельно забить 8000 бит. Нет столько пинов, поэтому последовательно по биту - вполне подойдет для моих задач. Загрузка/считывание данных - это задача эпизодическая, а не основная. Загрузили регистры, запустили процесс, поймалось условие - выгрузили. Не поймалось условие на данном диапазоне - загрузили новые значения.

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

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

ещё добавлю, бывает случается, при попытке уложить "классический" алгоритм решения задачи на ЦПУ -> при попытке адаптации его на ПЛИС даёт совершенно непредсказуемый результат.
К примеру, с алгоритмами-кандидатами на хэш SHA3 случилось, что перебор при помощи FPGA выполняется на 6 порядков быстрее, чем на ЦПУ, из-за чего их на втором этапе забраковали, и к последнему этапу остался фактически один алгоритм-губка Кeccak.
Go to the top of the page
 
+Quote Post
planetzeus
сообщение Nov 28 2017, 18:42
Сообщение #34





Группа: Участник
Сообщений: 9
Регистрация: 27-11-17
Пользователь №: 100 387



Цитата(iiv @ Nov 28 2017, 22:23) *
То есть пользовать или не пользовать GPU или ПЛИС будет зависеть только от того, как у вас идут сами эти вычисления. Если вы решите по USB в плиску или с PCIe на графическую карту скармливать эти операции, то скорость будет определяться не скоростью плиски или графической карты, а дыркой, через которую вы это все будете протаскивать и будет как минимум на пару порядков медленнее. Вероятность того, что ваш алгоритм со всеми промежуточными данными поместится в 11GB, которые есть на халяву на борту вашей графической карты и нескольких десятков мегабайт под код программы несравненно выше, чем если вы будете заморачиваться с плиской.

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

Цитата(krux @ Nov 28 2017, 22:25) *
Нет столько пинов - и не нужно, эти 8000 бит быстрее будут введены через какой-нибудь PCIe или Ethernet.

Говорю ж, обмен данными совсем не главная операция. Загрузили числа, перебираем. Можно загрузить такой диапазон, что перебирать в поисках подходящих значений будет сутками. Поэтому главная цель - скорость перебора в поиске, а не обмен. Ради загрузки 4 значений по 8 тыс. бит раз в сутки - нет необходимости в высокоскоростных интерфейсах.
Go to the top of the page
 
+Quote Post
AVR
сообщение Nov 28 2017, 19:23
Сообщение #35


фанат Linux'а
*****

Группа: Свой
Сообщений: 1 123
Регистрация: 23-10-05
Из: SPB.RU
Пользователь №: 10 008



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

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

Цитата(iiv @ Nov 28 2017, 21:23) *
ЗЫ: плиску для быстрых вычислений имеет смысл использовать только если на борту графической карты нет аппаратно реализованных операций, а в вашем случае, 32 битные сложения в графических картах наличествуют, и заморачиваться с плиской ИМХО нет смысла

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


--------------------
Go to the top of the page
 
+Quote Post
planetzeus
сообщение Nov 28 2017, 20:05
Сообщение #36





Группа: Участник
Сообщений: 9
Регистрация: 27-11-17
Пользователь №: 100 387



Цитата(AVR @ Nov 28 2017, 23:23) *
Только вот если в ПЛИС задействуются цепи переноса, то откуда же там возникнет "практически сразу"?

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

Цитата(AVR @ Nov 28 2017, 23:23) *
Я вот кое что делал на Spartan-6, ресурсов куча, а ячеек с переносом не осталось. Переделал на встроенных умножителях - влезло.

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

В общем-то я уже сделал первые выводы. Попробую для начала написать на Verilog схему в эмуляторе. Ну и присмотрюсь к облакам вместо реальной железки.
Go to the top of the page
 
+Quote Post
jojo
сообщение Nov 28 2017, 20:45
Сообщение #37


Знающий
****

Группа: Свой
Сообщений: 517
Регистрация: 9-10-04
Из: СССР
Пользователь №: 827



Цитата(planetzeus @ Nov 28 2017, 23:05) *
Именно для этого я и создал эту тему. Чтобы хотя бы определиться в какую сторону копать. Поскольку опыта у меня 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 млн операций /с, и это без учёта влияния архитектуры.

Таким образом, порядок величин один и тот же.
Go to the top of the page
 
+Quote Post
blackfin
сообщение Nov 28 2017, 21:39
Сообщение #38


Гуру
******

Группа: Свой
Сообщений: 2 738
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(jojo @ Nov 28 2017, 23:45) *
На вдаваясь в зависимости данных вокруг обсуждаемого алгоритма, ...

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

Arria 10 - 10АХ115H1F34I1SG:

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

Хотя для Arria 10 лучше, КМК, суммировать не по 8*4, а по 6*6 бит..
Go to the top of the page
 
+Quote Post
x736C
сообщение Nov 28 2017, 22:30
Сообщение #39


Профессионал
*****

Группа: Участник
Сообщений: 1 182
Регистрация: 3-03-06
Пользователь №: 14 942



Цитата(jojo @ Nov 28 2017, 15:45) *
Кстати, да, это тоже вариант для больших чисел.. Да что там, для любых чисел! Ток по VCCINT под 80А, если я правильно понял, и активное охлаждение. Надо брать.

Я бы еще посмотрел, как это все будет собираться даже на неплохом компе. Не знаю, как сейчас, а пару лет назад квартус слетал при более скромных проектах.
Go to the top of the page
 
+Quote Post
Plain
сообщение Nov 28 2017, 23:24
Сообщение #40


Гуру
******

Группа: Участник
Сообщений: 5 927
Регистрация: 5-03-09
Из: Москва
Пользователь №: 45 710



Цитата(planetzeus @ Nov 28 2017, 23:05) *
Поскольку опыта у меня 0, то оценить сколько нужно логических элементов чтобы сделать сумматор для двух 8000-битовых чиел - загадка.

Ну так надо было с этого и начать, т.е. почитать про сумматоры вообще, и с ускоренным переносом, с переключением переноса и т.д. в частности.
Go to the top of the page
 
+Quote Post
blackfin
сообщение Nov 29 2017, 05:05
Сообщение #41


Гуру
******

Группа: Свой
Сообщений: 2 738
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(jojo @ Nov 28 2017, 23:45) *
25*2*8000 = 400000 триггеров, впритык, значит, ядер меньше
Конвейер 250 этапов.

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

Итого:

25*(3*8000+250) = 25*24250 = 606250 триггеров.
Go to the top of the page
 
+Quote Post
Shivers
сообщение Nov 29 2017, 05:15
Сообщение #42


Знающий
****

Группа: Свой
Сообщений: 624
Регистрация: 11-02-08
Из: Msk
Пользователь №: 34 950



Я там выше уже писал про систему остаточных классов (СОК). Все что нужно - сконвертировать 8000 битные числа в СОК, а потом уже умножение и сложение будет представлять из себя кучу параллельных схемок с длинной переноса не более 10. И в конце результат еще надо сконвертировать обратно из СОК в бинарный код. Сравните - длинна переноса 8000 и длинна переноса 10, есть разница? Для этого СОК и был придуман.
Go to the top of the page
 
+Quote Post
jojo
сообщение Nov 29 2017, 05:33
Сообщение #43


Знающий
****

Группа: Свой
Сообщений: 517
Регистрация: 9-10-04
Из: СССР
Пользователь №: 827



Цитата(x736C @ Nov 29 2017, 01:30) *
Я бы еще посмотрел, как это все будет собираться даже на неплохом компе. Не знаю, как сейчас, а пару лет назад квартус слетал при более скромных проектах.


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

А питания стало маловато. Что такое 80 А по VCCINT, это только на логические ресурсы без BRAM и DSP. Как делал Xilinx отладочные платы - балалайки маломощные, так и продолжает.
Go to the top of the page
 
+Quote Post
blackfin
сообщение Nov 29 2017, 05:36
Сообщение #44


Гуру
******

Группа: Свой
Сообщений: 2 738
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(Shivers @ Nov 29 2017, 08:15) *
Все что нужно - сконвертировать 8000 битные числа в СОК, а потом уже умножение и сложение будет представлять из себя кучу параллельных схемок с длинной переноса не более 10. И в конце результат еще надо сконвертировать обратно из СОК в бинарный код. Сравните - длинна переноса 8000 и длинна переноса 10, есть разница?

Это если операций суммирования и умножения много. Но ТС не сказал сколько их должно быть? А если ему для каждой пары чисел нужно одно-два суммирования и одно-два умножения, то операции конвертирования окажутся более затратными, КМК.
Go to the top of the page
 
+Quote Post
jojo
сообщение Nov 29 2017, 05:39
Сообщение #45


Знающий
****

Группа: Свой
Сообщений: 517
Регистрация: 9-10-04
Из: СССР
Пользователь №: 827



Цитата(blackfin @ Nov 29 2017, 08:05) *
Результат суммирования нужно тоже где-то хранить, плюс на каждую ступень конвейера нужен один бит переноса.

Итого:

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

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

4 страниц V  < 1 2 3 4 >
Reply to this topicStart new topic
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 12th December 2017 - 21:44
Рейтинг@Mail.ru


Страница сгенерированна за 0.01355 секунд с 7
ELECTRONIX ©2004-2016