Перейти к содержанию

    

planetzeus

Участник
  • Публикаций

    9
  • Зарегистрирован

  • Посещение

Репутация

0 Обычный
  1. Цитата(AVR @ Nov 28 2017, 23:23) Только вот если в ПЛИС задействуются цепи переноса, то откуда же там возникнет "практически сразу"? Для суммы - да есть переносы, но для 2x+1, к примеру, нет. Повторюсь, я не утверждаю ничего, допускаю что Вы правы. Но даже если скорость будет сравнима с GPU, я бы предпочел находить нужный мне ряд чисел на FPGA. Мне сложно сравнивать. Процессор, который интерпретирует команды и в цикле работает с массивом 32-битных чисел или логическая схема внутри FPGA, оптимизированная под конкретную задачу. На GPU я могу распараллелить задачу на разные диапазоны, но вот как распараллелить суммирование или сдвиг нескольких тысяч бит на разные блоки/потоки не представляю. Цитата(AVR @ Nov 28 2017, 23:23) Я вот кое что делал на Spartan-6, ресурсов куча, а ячеек с переносом не осталось. Переделал на встроенных умножителях - влезло. Именно для этого я и создал эту тему. Чтобы хотя бы определиться в какую сторону копать. Поскольку опыта у меня 0, то оценить сколько нужно логических элементов чтобы сделать сумматор для двух 8000-битовых чиел - загадка. В общем-то я уже сделал первые выводы. Попробую для начала написать на Verilog схему в эмуляторе. Ну и присмотрюсь к облакам вместо реальной железки.
  2. Цитата(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 тыс. бит раз в сутки - нет необходимости в высокоскоростных интерфейсах.
  3. Цитата(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, чтобы можно было экспериментировать не только на этой задаче, но и возможно на других.
  4. Цитата(Alex77 @ Nov 28 2017, 15:21) "X*2+1" - сиё означает умножение на 2 те сдвиг и пририсовывание бита 1. Всё это реализуется "статическим сдвигом (т.е. реального сдвига нет)" и добавления вечной 1-цы. Таким образом схема будет работать на максимальной скорости в 500МГц. А на словах задание звучит как "А+Б+1". Что Автору требуется ? Именно! Нужна максимальная скорость - все операции, которые можно реализовать схемой вход->[схема]->выход (с нужным значением). Операций нужно несколько, я ж написал. (2х+1) - одна операция. А+Б - другая операция. Сравнение с 0 - третья операция, которая тоже решается логической схемой. Мне требуется только грамотный совет) Какой девайс выбрать чтобы все это пробовать? Т.е чтобы хватило логических элементов, чтобы была максимальная скорость. Девайсы недешевые, не хотелось бы потратить деньги и понять, что полностью реализовать не получится потому что мало элементов, или другие ограничения. Цитата(blackfin @ Nov 28 2017, 15:21) Как вы собираетесь загружать в ПЛИС 8000-разрядные числа? Я думаю последовательно. Т.е если будут например 4 регистра по 8000 бит, то 2 внешних пина на выбор регистра, один пин для data, один на синхронизацию. Еще раз говорю, я не спец в электронике. Максимум, что я делал - это RPi и на уровне "помигать светодиодом". Вот хочу освоить ПЛИС, спрашиваю у людей с опытом совета.
  5. Цитата(AVR @ Nov 28 2017, 14:54) Не, не то хотел спросить. Во имя чего такая задача решается в принципе? Дичь невиданная Или нет возможности раскрыть конечное предназначение? Почему дичь? например в RSA тоже используется длинная арифметика. У меня задача связана с другой темой, но также немного имеет отношение к криптографии. Мне нужно быстрое АЛУ для длинных чисел, что тут дикого?) Микропроцессоры, на мой взгляд, в любом случае медленнее, чем быстрая логика
  6. Цитата(_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) Не увидел, чтобы кто-то спросил автора темы: зачем это всё? Может реально решить поставленную задачу иными способами. Иного способа не нашел, к сожалению. Просто исследования, хочу попробовать решить эту задачу на ПЛИС. Компьютер решает задачу, но очень медленно.
  7. Спасибо всем за ответы. Согласен, что сумматор - самая тормозная часть и разбивать 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 но не уверен, что подходит для этих целей.
  8. Цитата(x736C @ Nov 27 2017, 19:54) 8000 тыс за такт на частоте 1 гиг — забудьте. Я немного неправильно выразился, под тактом имел в виду минимальное время, т.е не последовательную работу с битами, а одновременно со всеми. В ПЛИС я даже не новичок, пытаюсь стать хотя бы новичком, поэтому немного колхозно объясняю. Вот есть процессоры Intel, на борту у них есть регистры EAX, EBX и тд. Я хотел бы сделать на ПЛИС такую же схему - регистры, но только очень длинные. С внешней памятью работать нет необходимости. Т.е только последовательную загрузку 4 таких регистров, последовательную выгрузку, флаговый бит результата и все. Все остальные операции перебора значений автономные. Запустил и он работает только с этими регистрами, пока не сойдется условие равенства с конечным регистром. Точнее 0 как результат сложения.
  9. Помогите пожалуйста с выбором. Нужно делать вычисления с длинной арифметикой - до 8 тысяч бит. Т.е нужно простое АЛУ, но числа очень длинные. Вычисления относительно простые - сложение, вычитание (сложение с отрицательным в обратном коде), сдвиг на бит и пара таких же длинных счетчиков. Никаких умножений или делений. Т.е задаем начальные значения и и девайс должен складывать (вычитать) числа в зависимости от знакового бита, пока не дойдет до конечного или не найдет совпадения с заданным длинным числом. На компьютере такие вычисления крайне медленные. На GPU тоже, так как в любом случае сложение вычисляется группами по 64 бита. Поэтому подумал, что идеальный вариант - собственное АЛУ, которое делает одну операцию со всеми битами за такт. Насколько я понимаю, самый правильный вариант - ПЛИС. Желательно делать перебор с максимальной скоростью - к примеру если есть возможность 1 или 2 Ггц, то именно это и нужно. Почитал про ПЛИС и есть желание разобраться, но не понятно с какого девайса начинать искать. Не хотелось бы покупать плату, которая в итоге не подойдет для этой задачи. Мне не нужны разные интерфейсы, USB и может быть микроконтроллер на плате пригодится, но остальное по большому счету не очень важно. Посоветуйте пожалуйста с чего начинать и какую плату для разработки выбрать. Самый главный критерий - максимальная производительность и возможность "зашить" свою логическую схему.