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

Хеш-функция ГОСТ 34.11-2012 (Стрибог) оптимизация по утилизации

Если пойти тривиальным путём получается следующая картина:

  • S-функция. На один байт входного вектора расходуется одна ячейка BRAM. Двухпортовой памяти соответственно требуется в два раза меньше.
  • P-функция для FPGA бесплатно
  • L-функция - 2000 lut.

В процессорных реализациях используют таблицы предвычислений L и S функций:

https://github.com/drobotun/stribog_precalc/blob/master/gost_3411_2012_const.h

Но для финального вычисления требуется аж 64 обращения к таблицам, так что для FPGA этот метод выглядит бесполезным.

Есть ли другие пути оптимизации этого алгоритма или вся оптимизация возможна только за счет потери пропускной способности?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Какая требуется пропускная способность?

Какая ПЛИС используется?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

1 hour ago, negiin said:

Какая требуется пропускная способность?

Какая ПЛИС используется?

А с какой целью интересуетесь?

Четких требований пока нет, я хотел бы выяснить, есть ли еще возможность для оптимизации на уровне lps-функций.

Пробовал имплементацию под 325й кинтекс - целиком влезла одна E-функция. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Одно дело если 100 Мб, совсем другое дело если поток 100 Гб.

Одно дело если ПЛИС последних семейств, другое если старая.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Возможностей для оптимизации масса, всё зависит от того, что хотите получить.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

On 6/28/2019 at 10:05 AM, Lixlex said:

Но для финального вычисления требуется аж 64 обращения к таблицам, так что для FPGA этот метод выглядит бесполезным.

Почему? Современные FPGA имеют много быстрой памяти внутри.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

On 7/18/2019 at 4:22 PM, Koluchiy said:

Возможностей для оптимизации масса, всё зависит от того, что хотите получить.

Подскажите "массу", поскольку реализация стрибога "в лоб" гигантское число ресурсов, это притом, что Sboxes на BRAM (утилизация BRAM свыше 3000 шт).

Результат готов каждый такт (на вход тоже можно подавать каждый такт).

Критерий - максимизация T/A (Throughput/Area)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

On 7/19/2019 at 3:32 PM, count_enable said:

Почему? Современные FPGA имеют много быстрой памяти внутри. 

В этом случае мы лишь в 2 раза(и то не факт) выигрываем по утилизации, но в 64 раза проигрываем в пропускной способности.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

On 7/19/2019 at 7:44 PM, Doka said:

Подскажите "массу", поскольку реализация стрибога "в лоб" гигантское число ресурсов, это притом, что Sboxes на BRAM (утилизация BRAM свыше 3000 шт).

Результат готов каждый такт (на вход тоже можно подавать каждый такт).

Критерий - максимизация T/A (Throughput/Area)

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

Так что, начинать надо с определения, какая "средняя" скорость поступления данных, и из нее уже решать, каким образом оптимизировать расчет.

Естественно, всё это только в случае, если требования скорости расчета реально заданы, а не просто желание кинуть в логику известный пример на Си вообще без переделки под FPGA.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

1 minute ago, Koluchiy said:

Вы хотите каждый такт иметь что? Хэш-сумму для всего файла? А зачем? Файл может быть большой и подать его целиком на логику может быть физически невозможно.

ок.   условия:

  • у меня есть набор данных каждый длиной 512бит
  • от каждого набора надо считать хеш (наборы независимы)
  • темп поступления набора - раз в такт
  • темп снятия результата - раз в такт

 

вопрос тот же:

какую "массу возможностей для оптимизации" вы могли бы рекомендовать.

важен критерий - максимизация T/A (Throughput/Area)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Даже страшно подумать, чего Вы там обсчитываете, если на каждые 512 бит надо посчитать хэш в 512 бит, и всё это за 1 такт.

Для такой ширины шины 200Мгц - это уже 100Г.

Какая частота тактов?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

7 minutes ago, Koluchiy said:

Какая частота тактов?

As high as possible

Данные формируются внутри FPGA, так что ограничений нет никаких.

PS: Что за сфера применения догадаться не так сложно

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Не, я недогадливый. Расскажите, если не секретно. Если секретно - тогда не рассказывайте :).

Quote

As high as possible

Ой как я не люблю такие постановки задач... Гораздо лучше, когда люди знают, что они хотят.

 

Ладно, пара мыслей.

 

1. Стрибог - итерационный байт-ориентированный алгоритм, скармливать ему целиком строку и требовать сразу ответа - на мой взгляд, затея безнадежная.

 

2. Я бы пошел по пути распараллеливания с соответствующим увеличением латентности. Далее зависит от того, какая латентность устраивает.

 

1) Если латентность совсем не важна, наплодить ядер с последовательным расчетом (1 байт/такт, итерации последовательно). Каждое такое ядро занимает довольно небольшой объем, в большую микросхему их можно запихнуть много. Есть опыт реализации подобного ядра, если интересно - пишите в личку, поинтересуюсь у начальства по поводу возможности модернизации под Ваши нужды.

 

2) Если латентность не совсем не важна, хотя бы сделать расчет 1 итерации за 1 такт входных данных. Не знаю, во что это выльется, не пробовал.

 

3) Если с латентностью совсем никак, тогда только задирать рабочую частоту относительно частоты данных, и пытаться из этого как-то разбить расчет на итерации.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

у меня уже написанный и работающий стрибог, и конечно я, как и ТС после фразы о "массе возможностей для оптимизации" ожидали откровений именно для стрибог (и даже конкретно - для L-проеобразования), а не "Есть опыт реализации подобного ядра... поинтересуюсь у начальства..." :whistle3:

 

33 minutes ago, Koluchiy said:

Ой как я не люблю такие постановки задач... Гораздо лучше, когда люди знают, что они хотят.

а вам не кажется, что в случае ПЛИС этот кейс хорошо бьётся с намерением максимизации Т/А?

36 minutes ago, Koluchiy said:

1. Стрибог - итерационный байт-ориентированный алгоритм, скармливать ему целиком строку и требовать сразу ответа - на мой взгляд, затея безнадежная.

практика - критерий истины

36 minutes ago, Koluchiy said:

2. Я бы пошел по пути распараллеливания с соответствующим увеличением латентности.

как это вообще повлияет на Т/А? (никак)

37 minutes ago, Koluchiy said:

1) Если латентность совсем не важна, наплодить ядер с последовательным расчетом (1 байт/такт, итерации последовательно).

возьмите произвольный алгоритм хеширования/криптования - конвейеризованная реализация всегда раз выигрывает у итеративной/свёрнутой реализации, особенно это заметно у алгоритмов, параметры которых меняются от раунда к раунду (величина циклического сдвига, схема перемешивания, раундовые константы).

 

ЗЫЖ всёравно спасибо что не остались безучастным к проблеме.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Quote

и конечно я, как и ТС 

Вы и ТС - одно лицо? Или откуда знаете, чего он хотел? :)

Quote

ожидали откровений именно для стрибог (и даже конкретно - для L-проеобразования)

Очень жаль, что я Вас разочаровал... :( В следующий раз подробнее пишите, чего Вам надо - а то выспрашивать приходиццо :).

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

Quote

а вам не кажется, что в случае ПЛИС этот кейс хорошо бьётся с намерением максимизации Т/А?

Отсутствие задания реалистичных требований всегда плохо бьется со всем. В случае с ПЛИС, например, отсутствие задания частоты входных данных не позволяет понять, в сколько раз можно ускорить обработку за счет увеличения тактовой.

 

Quote

возьмите произвольный алгоритм хеширования/криптования - конвейеризованная реализация всегда раз выигрывает у итеративной/свёрнутой реализации

Это зависит от стоящих требований. В моем случае нужно было минимизировать объем при относительно небольшой скорости поступления данных. Конвейер был бы избыточен.

 

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...