Какие алгоритмы хеширования параллельны? Оптимизация хэширования больших файлов с использованием многоядерных процессоров

Я заинтересован в оптимизации хэширования некоторых больших файлов (оптимизация времени настенных часов). Уровень ввода-вывода уже достаточно оптимизирован, и устройство ввода-вывода (локальный SSD) используется только около 25% емкости, а один из ядер процессора полностью отключен.

У меня есть больше ядер, и в будущем, вероятно, будет еще больше ядер. До сих пор я мог использовать больше ядер, если мне понадобилось несколько хэшей одного и того же файла, скажем, MD5 и SHA256 в одно и то же время. Я могу использовать один и тот же поток ввода-вывода для подачи двух или более алгоритмов хэширования, и я получаю более быстрые алгоритмы, сделанные бесплатно (до настенных часов). Поскольку я понимаю большинство алгоритмов хэширования, каждый новый бит изменяет весь результат, и по своей сути это сложно или невозможно сделать параллельно.

Разрешены ли какие-либо из алгоритмов хеш-мейнстрима? Существуют ли какие-либо обычные хеши, которые являются параллелизуемыми (и которые имеют хотя бы выборочную реализацию)?

Как будущие процессоры будут ориентироваться на большее количество ядер и выравнивание в тактовой частоте, есть ли способ улучшить производительность хэширования файлов? (кроме разгонного охлаждения с жидким азотом?) или он по своей сути непараллелизуем?

Ответ 1

В этой области действительно много исследований. Национальный институт стандартов и технологий США в настоящее время проводит конкурс на разработку следующего поколения функций хеш-класса государственного уровня. Большинство предложений для этого являются параллелизуемыми.

Один пример: http://www.schneier.com/skein1.2.pdf

Википедия Описание текущего статуса конкурса: http://en.wikipedia.org/wiki/SHA-3

Ответ 2

Какой SSD у вас есть? Моя реализация MD5 работает со скоростью 400 МБ/с на одном ядре Intel Core2 (2,4 ГГц, а не на новейшем Intel). У вас действительно есть SSD, который поддерживает пропускную способность 1,6 ГБ/с? Я хочу то же самое!

Хеширование дерева может применяться к любой хэш-функции. Есть несколько тонкостей, и спецификация Skein пытается справиться с ними, интегрируя некоторые метаданные в самой функции (это не меняет многого для производительности), но "древовидный режим" Skein - это не "Skein", представленный SHA-3. Даже если Skein выбран как SHA-3, выход хеша с древовидным режимом не будет таким же, как вывод "plain Skein".

Надеюсь, в какой-то момент будет определен стандарт, чтобы описать хэш-процесс общего дерева. Прямо сейчас их нет. Тем не менее, некоторые протоколы были определены с поддержкой пользовательского хеширования дерева с помощью хэш-функции Tiger под названием "TTH" (Tiger Tree Hash) или "THEX" (формат обмена деревом Hash). Спецификация для TTH, по-видимому, немного неуловима; Я нахожу ссылки на проекты, которые либо переехали, либо исчезли навсегда.

Тем не менее, я немного сомневаюсь в этой концепции. Это довольно аккуратно, но обеспечивает повышение производительности только в том случае, если вы можете читать данные быстрее, чем то, что может обрабатывать одно ядро, и, учитывая правильную функцию и правильную реализацию, одно ядро может хешировать довольно много данных в секунду. Хеш дерева, распределенный по нескольким ядрам, требует наличия данных, отправленных в соответствующие ядра, а 1,6 ГБ/с - это не самая маленькая полоса пропускания.

SHA-256 и SHA-512 не очень быстры. Среди кандидатов SHA-3, предполагающих x86-процессор в 64-битном режиме, некоторые из них достигают высокой скорости (более 300 Мбайт/с на моем 2,4 ГГц Intel Core2 Q6600 с одним ядром - что я могу получить SHA-1 тоже), например BMW, SHABAL или Skein. Криптографически эти конструкции немного новы, но MD5 и SHA-1 уже криптографически "разбиты" (довольно эффективно в случае MD5, скорее теоретически для SHA-1), поэтому любой из кандидатов SHA-3 раунда-2 должно быть хорошо.

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

Ответ 3

Ты не сказал, зачем нужен хэш. Если вы не собираетесь обменивать его с внешним миром, а только для внутреннего использования, просто разделите каждый файл на куски, вычислите и сохраните все контрольные суммы. Затем вы можете использовать многие ядра, просто бросая кусок на каждый.

Два решения, которые приходят на ум, делят файлы на куски фиксированного размера (проще, но будут использовать меньше ядер для небольших файлов, где вам не нужна вся эта мощность) или в фиксированном количестве кусков (будет используйте все ядра для каждого файла). Действительно зависит от того, чего вы хотите достичь и как выглядит ваше распределение размера файла.

Если, с другой стороны, вам нужны хэши для внешнего мира, так как вы можете читать из других ответов, это невозможно с "стандартными" хэшами (например, если вы хотите отправить хэши SHA1 для других, чтобы проверить разные инструменты), поэтому вы должны искать где-то еще. Подобно вычислению хэша, когда вы храните файл, для последующего извлечения или вычисляете хэши в фоновом режиме с "свободными" ядрами и сохраняете для последующего поиска.

Лучшее решение зависит от того, каковы ваши ограничения и где вы можете инвестировать пространство, время или мощность процессора.