Введение 5
Глава 1. Технология параллельных вычислений Nvidia CUDA 9
1.1. Предварительные сведения о технологии CUDA 9
1.2. Преимущества и ограничения CUDA 10
1.3. Состав CUDA 11
1.4. Модель программирования CUDA 13
1.5. Модель памяти CUDA 14
1.5.1. Банк конфликты разделяемой памяти 17
1.6. Компиляция и оптимизация программ на CUDA 20
Глава 2. Разработка и исследование параллельных алгоритмов тестирования ПСП с помощью технологий Nvidia Cuda 21
2.1. Тестирование ПСП 21
2.2. Графический тест «Битовая автокорреляционная функция(АКФ)» 22
2.2.1. Описание теста 22
2.2.2. Последовательная реализация алгоритма 24
2.2.3. Параллельная реализация алгоритма 25
2.2.4. Сравнительный анализ 27
2.3. Графический спектральный тест 29
2.3.1. Описание теста 29
2.3.2. Последовательная реализация алгоритма 31
2.3.3. CUFFT 32
2.3.4. Параллельная реализация алгоритма 34
2.3.5. Сравнительный анализ 35
2.4. Редукция 36
2.5. Редукция на CUDA в статистических тестах 44
2.5.1. Частотный тест 45
2.5.2. Последовательная реализация алгоритма 46
2.5.3. Параллельная реализация алгоритма 47
2.5.4. Сравнительный анализ 47
2.6. Проверка корреляции 49
2.6.1. Описание теста 49
2.6.2. Последовательная реализация теста 50
2.6.3. Параллельная реализация теста 51
2.6.4. Сравнительный анализ 52
Глава 3. Доработка программного комплекса оценки качества генераторов ПСП 54
3.1. Инструменты и функционал разработки 54
3.2. Архитектура доработки 56
3.2.1. ManagedCuda 56
3.2.2. Основные интерфейсы и классы приложения 59
3.3. Сравнение с аналогами 61
Глава 4. «Золотой» генератор ПСП 63
4.1. Основные предпосылки 63
4.2. Идея генератора 63
4.3. Алгоритм 65
4.4. Тестирование в системе оценки качества генераторов ПСП 67
4.4.1. Результаты графических тестов 69
4.4.2. Результаты статистических тестов 78
4.4.3. Выводы 80
Заключение 81
Список литературы 83
Приложение 85
В настоящее время множество применений находят числа, которые выбираются случайным образом, так называемые последовательности случайных чисел (ПСЧ). Они используются при моделировании различных явлений для повышения адекватности моделей, при решении сложных задач численного анализа, в компьютерной графике, а также являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов.
Особую роль ПСЧ играют в криптографии. Например, они могут применяться в качестве ключевых последовательностей. Корректная реализация асимметричных криптоалгоритмов требует добавления к каждой порции открытого текста нескольких случайных байт. Случайные числа используются также при блочном шифровании и хешировании.
В наше время разработано достаточно большое количество различных генераторов ПСЧ. Все они в общем случае должны удовлетворять следующим основным требованиям:
• эффективность;
• невозможность повторной генерации выработанной ПСЧ;
• мультиплатформенность;
• простота программной реализации.
Однако практика показывает, что реализовать генератор ПСЧ, удовлетворяющий всем вышеперечисленным критериям, достаточно сложно.
В настоящее время широкое распространение получили программные генераторы, вырабатывающие ПСП с помощью детерминированных рекуррентных формул. Псевдослучайными эти последовательности называют потому, что фактически они остаются полностью детерминированными, даже пройдя все тесты на независимость и равномерность распределения.
Можно выделить следующие задачи, для решения которых используются генераторы ПСП:
• техническое диагностирование компонентов компьютерных систем (КС).
• контроль хода выполнения программ с использованием сторожевых процессоров.
• помехоустойчивое кодирование.
• защита информации.
Во всех вышеперечисленных случаях генераторы ПСП используются либо непосредственно, либо в составе генераторов случайных последовательностей, либо на их основе строятся алгоритмы хеширования информации. Именно от свойств генераторов ПСП, особенно в тех случаях, когда необходимо обеспечить устойчивую работу КС при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки, хранения и передачи информации.
Подобные генераторы ПСП должны удовлетворять нескольким дополнительным требованиям:
• числа в генерируемой последовательности должны быть равномерно распределены и независимы, т. е. должны быть некоррелированы;
• период последовательности должен иметь возможно большую длину. Непредсказуемость генераторов ПСП основывается на недоказуемом предположении, что аналитику не хватит ресурсов (вычислительных, временных или стоимостных), для того чтобы инвертировать функцию обратной связи или функцию выхода. Теория сложности вычислений, к сожалению, пока не в состоянии дать нижнюю границу сложности анализируемого алгоритма инвертирования. Иначе говоря, никогда нет гарантии, что алгоритм, сложность которого анализируется, самый эффективный из всех возможных.
То есть, чтобы оценить качество генератора ПСП достаточно провести исследование статистических свойств формируемых генератором последовательностей.
Для оценки статистических свойств псевдослучайных последовательностей используются следующие наборы тестов
В последнее время достигнуты определенные успехи в части тестирования псевдослучайных последовательностей. Этот процесс особенно интенсифицировался с развитием компьютерной техники и криптографии. Повышенные требования к защите информации и шифровальным процедурам потребовали формирования числовых последовательностей с очень большими периодами и очень большой длины. Современные системы тестирования ПСП зачастую используют алгоритмы тестирования, которые:
1) Не эффективны с точки зрения использования оперативной памяти компьютера.
2) Выполняются долго по времени.
Целью данной работы является уменьшение времени тестирования ПСП за счет распараллеливания алгоритмов тестирования с помощью технологии параллельных вычислений Nvidia Cuda.
Основными задачами дипломной работы являются:
1. Изучение и анализ существующих методов тестирования псевдослучайных последовательностей.
2. Разработка параллельных алгоритмов тестирования ПСП с помощью технологии Nvidia Cuda и сравнение с последовательными алгоритмами тестирования.
3. Программная реализация параллельных алгоритмов тестирования ПСП и доработка архитектуры программного комплекса по оценке качества генераторов ПСП.
4. Реализация «золотого» генератора ПСП, основанного на иррациональности, и его тестирование в системе оценки качества генераторов ПСП.
В современном мире защита информации будет продолжать играть ключевую роль, потому что общество стоит на пути нарастающей информатизации. Появляются новые методы шифрования данных, необходимо генерировать ключевые последовательности большой длины и периода. Поэтому в настоящее время основной задачей является не только создание новых генераторов ПСП, но и проверка их на качественность. Не всегда удается за разумное время протестировать ПСП. Поэтому целью выпускной квалификационной работы стало ускорение тестирования последовательностей, сформированных генераторами.
Можно с большой долей уверенности считать, что цель данной работы была достигнута. В процессе работы было разработано множество параллельный алгоритмов для тестирования ПСП. Использовалась программно-аппаратная вычислительная архитектура CUDA от компании Nvidia. Сейчас CUDA - быстро развивающаяся платформа, которая помогает перенести вычисления с CPU на GPU, в разы ускоряя вычисления. Также в CUDA имеется множество полезных библиотек для математических вычислений (CUFFT, CURAND, CUBLAS и др.).
Безусловно, более важным этапом являлся этап изучения предметной области. Были проанализированы основные концепции написания программ на CUDA, а также анализ последовательных алгоритмов с целью их оптимизации. Была изучена библиотека CUFFT, а также разработан метод редукции. Полученные знания были применены непосредственно в реализации параллельных алгоритмов.
Также важно отметить, что был реализован «золотой» генератор псевдослучайных последовательностей. Золотым он называется потому, что основывается на иррациональном числе, называемым еще числом золотого
сечения. Этот генератор имеет длинный период последовательности, что является хорошим показателем при оценке качества генераторов ПСП.
Используя созданный генератор, были сформированы последовательности разной длины и протестированы в программном комплексе оценки качества генераторов ПСП. Использовались разные виды тестов, как и графические, так и оценочные. Результаты тестирования были отображены в текстовой форме, а также в виде диаграмм. В целом, генератор прошел большинство тестов, что говорит о его хорошей статистической независимости.
Разработанный программный комплекс является законченным продуктом с достаточным набором функций. Реализованы как последовательные, так и параллельные тесты ПСП. Также существует автоматическая и ручная настройка параметров тестирования и отображение результатов в удобном для пользователя виде. Все результаты тестирования можно выгрузить в Microsoft Excel. Стоит отметить, что полученная система и параллельные алгоритмы тестирования ПСП могут быть использованы в криптографических системах, при создании новый генераторов ПСП и других отраслях.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
