III Международная студенческая научная конференция Студенческий научный форум - 2011

В результате продолжения исследований, предварительные результаты которых были описаны в статье [1] были получены результаты, позволяющие говорить о начале создания новой теоретической базы в области разработки и реализации алгоритмов хеширования. В частности, были найдены объяснения увеличения количества коллизий для мультипликативного метода:

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

Однако наибольшего внимания заслуживает особенность, присущая цифровым ЭВМ, и заставившая разработчика программного пакета OspGen (на момент написания данной статьи актуальной является версия 2.1, ведется работа по созданию версии 2.2) провести детальный анализ процесса обработки процессором операндов при вычислении результата - особенность заключается в том, что все цифровые ЭВМ имеют ограниченную точность вычислений с плавающей точкой, а главное, эта точность может варьироваться (и притом заметно) не только в зависимости от типа операций, но и от модели процессора, причем различия настолько заметны, что наблюдаются значительные расхождения в статистике результатов элементарных операций - умножения и деления.

Данная особенность начала проявлять себя еще на этапе определения количества необходимых вычислений при заданном диапазоне и шаге. Было установлено, что если, скажем, заданы границы диапазона от -10 до 10 с шагом 0.1, то некоторые процессоры (например, Intel Pentium IV 3200 MHz (540) на ядре Prescott с технологией Hyper Threading) производя вычисления для определения количества итераций цикла вычислений, получали корректный результат (вычисления проводились в режиме с плавающей точкой)

Другие же процессоры (в основном старых серий, таких, как Intel Celeron 433 MHz на ядре Mendocino, Intel Pentium 133 MHz, а также современные мобильные процессоры Intel Pentium M) получали иной результат, приводивший к тому, что итоговое значение было неверно:

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

И хотя данную проблему удалось устранить достаточно быстро, в дальнейшем указанная особенность стала решающим фактором при проведении вычислительного эксперимента по исследованию свойств хеш-функций. При использовании мультипликативного метода статистика количества наборов значений коэффициентов функции при заданном количестве коллизий, полученная на процессорах Intel Celeron 433 MHz на ядре Mendocino и Intel Pentium IV 3200 MHz (540) на ядре Prescott с технологией Hyper Threading расходятся кардинальным образом. Например, если у Celeron 35 коллизий было получено при 1024 наборах коэффициентов, то у Pentium 35 коллизий дали только 532 набора! Подобная картина наблюдается на подавляющем большинстве значений количества коллизий. Отсюда следует вывод, что, судя по всему, процессорные устройства по точности вычислений можно разделить на классы эквивалентности, хотя в официальной документации на оборудование фирмы Intel это не указано.

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

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

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

Литература

1. Е.Р. Абдулин, А.Л. Бескин. «Построение хеш-функций и анализ их свойств». Теоретические вопросы вычислительной техники, программного обеспечения и информационных технологий в муниципальном хозяйстве: Межвузовский сборник научных трудов / Государственное образовательное учреждение высшего профессионального образования «Московский госу­дарственный институт радиотехники электроники и автоматики (технический университет)» M., 2005 - .232-234 с.

Код для цитирования: Скопировать