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

Question

Меня интересует оптимизация хеширования некоторых больших файлов (оптимизация времени настенных часов). Ввод / вывод уже достаточно хорошо оптимизирован, и устройство ввода / вывода (локальный SSD) подключено только примерно на 25% емкости, а одно из ядер ЦП полностью заполнено.

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

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

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

Answer 1

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

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

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

Answer 2

Какой у вас SSD? Моя реализация C5 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» (Tree Hash Exchange Format). Спецификация для TTH кажется немного неуловимой; Я нахожу некоторые ссылки на черновики, которые переместились или исчезли навсегда.

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

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

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

Answer 3

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

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

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

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