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

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





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



Помогите пожалуйста с выбором.
Нужно делать вычисления с длинной арифметикой - до 8 тысяч бит. Т.е нужно простое АЛУ, но числа очень длинные.
Вычисления относительно простые - сложение, вычитание (сложение с отрицательным в обратном коде), сдвиг на бит и пара таких же длинных счетчиков.
Никаких умножений или делений. Т.е задаем начальные значения и и девайс должен складывать (вычитать) числа в зависимости от знакового бита, пока не дойдет до конечного или не найдет совпадения с заданным длинным числом.
На компьютере такие вычисления крайне медленные. На GPU тоже, так как в любом случае сложение вычисляется группами по 64 бита.
Поэтому подумал, что идеальный вариант - собственное АЛУ, которое делает одну операцию со всеми битами за такт. Насколько я понимаю, самый правильный вариант - ПЛИС.
Желательно делать перебор с максимальной скоростью - к примеру если есть возможность 1 или 2 Ггц, то именно это и нужно.
Почитал про ПЛИС и есть желание разобраться, но не понятно с какого девайса начинать искать. Не хотелось бы покупать плату, которая в итоге не подойдет для этой задачи.
Мне не нужны разные интерфейсы, USB и может быть микроконтроллер на плате пригодится, но остальное по большому счету не очень важно.
Посоветуйте пожалуйста с чего начинать и какую плату для разработки выбрать. Самый главный критерий - максимальная производительность и возможность "зашить" свою логическую схему.
Go to the top of the page
 
+Quote Post
x736C
сообщение Nov 27 2017, 15:54
Сообщение #2


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

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



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

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

Это в том случае, если все время необходимо параллельно считать, а не единовременно посчитать одно единственное выражение.
Go to the top of the page
 
+Quote Post
planetzeus
сообщение Nov 27 2017, 16:11
Сообщение #3





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



Цитата(x736C @ Nov 27 2017, 19:54) *
8000 тыс за такт на частоте 1 гиг — забудьте.


Я немного неправильно выразился, под тактом имел в виду минимальное время, т.е не последовательную работу с битами, а одновременно со всеми. В ПЛИС я даже не новичок, пытаюсь стать хотя бы новичком, поэтому немного колхозно объясняю.
Вот есть процессоры Intel, на борту у них есть регистры EAX, EBX и тд. Я хотел бы сделать на ПЛИС такую же схему - регистры, но только очень длинные. С внешней памятью работать нет необходимости. Т.е только последовательную загрузку 4 таких регистров, последовательную выгрузку, флаговый бит результата и все. Все остальные операции перебора значений автономные. Запустил и он работает только с этими регистрами, пока не сойдется условие равенства с конечным регистром. Точнее 0 как результат сложения.
Go to the top of the page
 
+Quote Post
x736C
сообщение Nov 27 2017, 16:37
Сообщение #4


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

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



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

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

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

Сообщение отредактировал x736C - Nov 27 2017, 16:43
Go to the top of the page
 
+Quote Post
RobFPGA
сообщение Nov 27 2017, 16:51
Сообщение #5


Знающий
****

Группа: Свой
Сообщений: 934
Регистрация: 23-12-04
Пользователь №: 1 643



Цитата(planetzeus @ Nov 27 2017, 18:18) *
..
Желательно делать перебор с максимальной скоростью - к примеру если есть возможность 1 или 2 Ггц, то именно это и нужно.
Почитал про ПЛИС и есть желание разобраться, но не понятно с какого девайса начинать искать. Не хотелось бы покупать плату, которая в итоге не подойдет для этой задачи.
..


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

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


Удачи! Rob.
Go to the top of the page
 
+Quote Post
_pv
сообщение Nov 27 2017, 17:41
Сообщение #6


Гуру
******

Группа: Свой
Сообщений: 2 276
Регистрация: 8-04-05
Из: Nsk
Пользователь №: 3 954



а вот это вот вычитание/сложение одного и того же числа пока не дойдёт до конечного не заменяется разве умножением/делением?
взяв первую попавшуюся ссылку на 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/
Go to the top of the page
 
+Quote Post
planetzeus
сообщение Nov 27 2017, 17:56
Сообщение #7





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



Спасибо всем за ответы.
Согласен, что сумматор - самая тормозная часть и разбивать 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
но не уверен, что подходит для этих целей.
Go to the top of the page
 
+Quote Post
_pv
сообщение Nov 27 2017, 18:04
Сообщение #8


Гуру
******

Группа: Свой
Сообщений: 2 276
Регистрация: 8-04-05
Из: Nsk
Пользователь №: 3 954



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

а на сэкономленные деньги возьмите у амазона сколько надо EC2 и на нём всё посчитайте пока плата из китая ехать будет.
Go to the top of the page
 
+Quote Post
ViKo
сообщение Nov 27 2017, 20:00
Сообщение #9


Универсальный солдатик
******

Группа: Модераторы
Сообщений: 7 775
Регистрация: 1-11-05
Из: Минск
Пользователь №: 10 362



Это что, майнеры криптовалюты ищут черный ход?
Go to the top of the page
 
+Quote Post
Shivers
сообщение Nov 28 2017, 06:19
Сообщение #10


Знающий
****

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



Цитата(planetzeus @ Nov 27 2017, 20:56) *
Согласен, что сумматор - самая тормозная часть и разбивать 8000 бит на части в любом случае придется.

Погуглите про систему остаточных классов (СОК). Специально придумано для распараллеливания арифметики с разрядностью в сотни и тысячи бит. Придумано кстати уже давно, лет 50 назад, и используется столько же - в спец. задачах. Главный недостаток СОК - хорошо работает только умножение и сложение, с делением проблемы. Но Вам то как раз сложение и нужно, я так понял.
Go to the top of the page
 
+Quote Post
_Ivan_33
сообщение Nov 28 2017, 08:29
Сообщение #11


fpga designer
****

Группа: Свой
Сообщений: 575
Регистрация: 20-04-08
Из: Зеленоград
Пользователь №: 36 928



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


--------------------
Go to the top of the page
 
+Quote Post
AVR
сообщение Nov 28 2017, 10:08
Сообщение #12


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

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



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


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





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



Цитата(_Ivan_33 @ Nov 28 2017, 12:29) *
А что мешает написать это все на 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 @ Nov 28 2017, 14:08) *
Не увидел, чтобы кто-то спросил автора темы: зачем это всё? Может реально решить поставленную задачу иными способами.

Иного способа не нашел, к сожалению. Просто исследования, хочу попробовать решить эту задачу на ПЛИС. Компьютер решает задачу, но очень медленно.
Go to the top of the page
 
+Quote Post
AVR
сообщение Nov 28 2017, 10:54
Сообщение #14


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

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



Цитата(planetzeus @ Nov 28 2017, 13:37) *
Иного способа не нашел, к сожалению. Просто исследования, хочу попробовать решить эту задачу на ПЛИС. Компьютер решает задачу, но очень медленно.

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


--------------------
Go to the top of the page
 
+Quote Post
ViKo
сообщение Nov 28 2017, 10:57
Сообщение #15


Универсальный солдатик
******

Группа: Модераторы
Сообщений: 7 775
Регистрация: 1-11-05
Из: Минск
Пользователь №: 10 362



Инкрементировать 8000-разрядное число (т.е. + 1) ничуть не проще, чем сложить два 8000-разрядных числа.
В отличие от умножения на 2. Там и сдвигать не надо. Выдавайте биты со сдвигом, и все. rolleyes.gif
Go to the top of the page
 
+Quote Post

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

 


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


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