SHA1 производительность хеширования FPGA

Question

Я пытаюсь понять, насколько хорошо FPGA может выполнять хэширование SHA1.

Для справки, SHA1 включает в себя серию 32-битных целочисленных вычислений, сгруппированных в 80 «шагов»; Вот 4 репрезентативных шага от середины алгоритма, в C:

x0 = rol(x13 ^ x8 ^ x2 ^ x0, 1);
e += rol(a,5) + (b^c^d) + x0 + 0x6ED9EBA1L;
b = rol(b,30); 

x1 = rol(x14 ^ x9 ^ x3 ^ x1, 1);
c += rol(d,5) + (e^a^b) + x1 + 0x6ED9EBA1L;
e = rol(e,30); 

x2 = rol(x13 ^ x10 ^ x4 ^ x2, 1);
b += rol(c,5) + (d^e^a) + x2 + 0x6ED9EBA1L;
d = rol(d,30); 

x3 = rol(x13 ^ x11 ^ x5 ^ x3, 1)
a += rol(b,5) + (c^d^e) + x3 + 0x6ED9EBA1L;
c = rol(c,30); 

Всего имеется 21 внутренняя 32-битная переменная, и алгоритм продолжает подавать их друг в друга. «rol» - это сдвиг с вращением (перемещение битов с одного конца на другой.)

Теперь мне кажется, что для вычисления x13 ^ x11 ^ x5 ^ x3 требуется 32 LUT, c ^ d ^ e - еще 32 LUT, и я не совсем понимаю, как рассчитать ресурсы, необходимые для дополнений, но я предполагаю 96 или 128 LUT. Вращения и назначения выполняются через межсоединения. Итак, скажем, всего 192 LUT, раз 80 шагов, плюс некоторые накладные расходы. Полностью развернутый, я бы ожидал ~ 16 000 LUT, с пропускной способностью 1 входной блок за такт и задержкой 80 тактов. Xilinx Artix-7 XC7A50T содержит 8150 срезов с 4 LUT каждый, поэтому я буду иметь пропускную способность 2 блока на тактовый цикл или 600 МГц / с при 300 МГц (300 Гбит / с, поскольку каждый блок 512 бит.) Является ли это разумным оцените или я далеко?

Мне не удалось найти никаких ссылок на полностью развернутые реализации SHA1, но эти ребята https://www.heliontech.com/fast_hash.htm заявляют о реализации "очень высокой производительности" с 828 LUT и пропускной способностью 1 блок на 82 такта, поэтому ближе к 70 Гбит / с на XC7A50T. Неужели эта цифра намного ниже просто потому, что они не развернуты?

Answer 1

Хорошо, теперь я могу ответить на свой вопрос. Мне удалось собрать работающую реализацию SHA1 в Verilog.

https://github.com/ekuznetsov139/fpga

Это фактически генератор PMK WPA2, а не просто SHA1 (SHA1 выполняется в цикле 8192 раза для одних и тех же данных.)

Я бы не стал утверждать, что он идеально оптимизирован или даже особенно хорошо закодирован - я узнал все, что знаю о Verilog за последние две недели, в промежутке между другими проектами, и половина этого времени была потрачена на сбор данных и из нескольких экземпляров ядра через PCI-Express. Но я получил корректную работу в симуляторе и успешно запустил реальную ПЛИС, и показатели производительности близки к моим первоначальным прогнозам. С целью Cyclone V я последовательно вижу около 7000 ALM на ядро, причем каждое ядро ​​способно выполнять один хэш на такт. Один ALM - это, по сути, 2 LUT (1 большая или 2 маленьких) плюс некоторое оборудование для переноса сумматора Итак, 14 000 ЛУТ. Fmax, кажется, составляет около 300 МГц для быстрого кремния и ближе к 150 МГц для медленного кремния.

Одна вещь, которую я не учел в своих первоначальных оценках, - это потребность в большом количестве памяти для внутреннего состояния. 21 32-разрядные переменные, умноженные на 80 шагов, равны 53760 битам, и при 4 регистрах на ALM для этого потребуется больше ресурсов, чем для всех вычислений. Но компилятор может упаковать большую часть этого в ячейки памяти, даже если я не проинструктирую его делать это явно.

Маршрутизация / компоновка - довольно большая проблема. У меня есть чип с 113K ALM (301K LE). Максимум, что я смог вписать в него - 5 копий. Это менее 40% использования. И это заняло ~ 8 часов примерки. Попробую возиться с LogicLock, чтобы посмотреть, смогу ли я сделать лучше.

При одновременном запуске 5 копий на частоте 300 МГц пропускная способность будет равна 1,5 Гхаш / с SHA1 или 90 Кхаш / с WPA2. Что несколько меньше, чем я ожидал (около 1/3 пропускной способности GeForce 980 Ti). Но, по крайней мере, эффективность использования энергии намного лучше.

---

РЕДАКТИРОВАТЬ: Один взгляд на Планировщик разделов дизайна в стандартной версии Quartus выявил проблему. Компилятор, слишком умный для собственной пользы, объединял массивы внутренних хранилищ каждого ядра, создавая тонны ненужных соединений между ядрами.

Даже без полного LogicLock, просто с «Разрешить объединение регистров сдвига по иерархиям», установленным на «выкл», у меня есть успешное совпадение с 10 копиями. Посмотрим, смогу ли я сделать 12 ...

Answer 2

Теперь мне кажется, что для вычисления x13 ^ x11 ^ x5 ^ x3 требуется 32 LUT, c^d^e - еще 32 LUT, и я не совсем понимаю, как рассчитать ресурсы, необходимые для дополнений, но я 'Я предполагаю 96 или 128 LUT.

Все это было бы верно, если бы XOR и дополнение были независимыми, но это не так.Каждая LUT на FPGA серии 7 может занимать до 6 входов, поэтому синтезатор может поглощать некоторые из XOR в цепочку сложений.

При всем этом, маршрутизация и компоновка будут самыми большимипрепятствие.Чтобы использовать цепь переноса, все биты в широком сумматоре должны быть расположены "вертикально".Это приводит к естественному течению конвейера слева направо, но я сомневаюсь, что в XC7A50T достаточно столбцов, чтобы уместить весь конвейер в один ряд.Ограничивающим фактором будут не ресурсы маршрутизации, а LUT.