Регистрация / Вход
Прислать материал

Универсальные методы решения линейных систем над конечными полями на экзафлопных вычислителях

Номер контракта: 14.604.21.0034

Руководитель: Тыртышников Евгений Евгеньевич

Должность руководителя: Директор

Докладчик: Замарашкин Николай Леонидович, с.н.с.

Организация: Федеральное государственное бюджетное учреждение науки Институт вычислительной математики Российской академии наук
Организация докладчика: Федеральное государственное бюджетное учреждение науки Институт вычислительной математики Российской академии наук

Аннотация скачать
Постер скачать
Ключевые слова:
линейные системы, конечные поля, метод монтгомери, метод видемана-коппресмита, аппроксимации паде, параллельные вычисления, параллельные алгоритмы, быстрые алгоритмы, специальные матрицы, специализированные ускорители, графические ускорители, плис, rsa шифр

Цель проекта:
1. Разработка научных и программно-технических решений в области разработки универсальных методов решения линейных систем над конечными полями на эксафлопсных вычислителях. 2. Разработка экспериментального образца программного обеспечения (далее - ЭО ПО) ориентированного на эффективное функционирование на вычислительных системах эксафлопсного уровня производительности для реализации универсальных методов решения линейных систем над конечными полями.

Основные планируемые результаты проекта:
1. Краткое описание основных результатов.

а) Универсальный численный метод решения линейных систем над конечными полями с большим числом элементов (числом элементов 10^150).
б) Универсальный численный метод решения линейных систем над конечными полями с двумя элементами (над полем GF(2)).
в) Массивно-параллельный метод для нахождения вычислительно трудоемких блочных операций, возникающих при решении линейных систем над конечными полями.
г)Оптимальные по сложности универсальные алгоритмы решения линейных систем, реализующие разработанные методы, на различных вычислительных системах с пиковой производительностью уровня 100 и более Tflops.

2. Основные характеристики планируемых результатов

a) Разрабатываемый универсальный численный метод решения линейных систем над конечными полями с числом элементов порядка 10^150 должен быть предназначен для решения линейных систем:
1) с разреженной матрицей системы размера не менее 10^7,
2) средним числом ненулевых элементов в строке не более 150 с допустимым отклонением 10%.

б)Разрабатываемый универсальный численный метод решения линейных систем над конечным полем GF(2) должен быть предназначен для решения линейных систем:
1) с разреженной матрицей системы размера не более 2·10^9,
2) средним числом ненулевых элементов в строке не более 1000 с допустимым отклонением 20%.

в) Разрабатываемый массивно-параллельный метод для нахождения вычислительно трудоемких блочных операций должен быть предназначен для работы с блоками
1) от 6 400 до 64 000 для конечного поля GF(2),
2) от 100 до 1000 для конечных полей с числом элементов порядка 10^150.

г) Разрабатываемый универсальный численный метод решения линейных систем над конечными полями с числом элементов порядка 10^150 должен обеспечивать:
1) масштабирование параллельных вычислений (не менее 50% производительности) на системах со 100 000 распределенных вычислительных узлов;
2) эффективную возможность масштабирования вычислений как для систем с быстрыми и надежными межпроцессорными связями, так и для систем с медленными межпроцессорными связями.

д) Разрабатываемый универсальный численный метод решения линейных систем над конечным полем GF(2) должен обеспечивать:
1) масштабирование параллельных вычислений (не менее 50% производительности) на системах со 100 000 распределенных вычислительных
2) эффективную возможность масштабирования вычислений как для систем с быстрыми и надежными межпроцессорными связями, так и для систем с медленными межпроцессорными связями.обеспечивать:

е) Разрабатываемые оптимальные по сложности универсальные алгоритмы решения линейных систем над конечным полем GF(2) должны предусматривать массивно параллельные вычисления для блоков-векторов и матриц над конечным полем GF(2) с блочным размером, изменяющимся в пределах от 6 400 до 64 000, эффективно реализуемые с помощью технологий многопоточных и/или многопроцессорных вычислений на специализированных вычислительных ускорителях

ж) Разрабатываемые оптимальные по сложности универсальные алгоритмы решения линейных систем над конечными полями с «большим» числом элементов должны предусматривать массивно параллельные вычисления для блоков-векторов и матриц над полем с числом элементов 10^150 с блочным размером, изменяющимся от 100 до 1000, эффективно реализуемые с помощью технологий многопоточных и/или многопроцессорных вычислений на специализированных вычислительных ускорителях

Краткая характеристика создаваемой/созданной научной (научно-технической, инновационной) продукции:
1. Конечным продуктом данного проекта является программная реализация оптимальных по сложности универсальных алгоритмов решения линейных систем над конечными полями (над полем GF(2) и над конечным полем с числом элементов порядка 10^150) в виде ЭО ПО. Экспериментальные образцы ПО должны эффективно функционировать на различных вычислительных системах с пиковой производительностью уровня 100 и более Tflops, что обеспечивается широким внедрением технологий многопоточных и многопроцессорных вычислений. ЭО ПО должны обеспечивать масштабирование (не менее 50% производительности) на системах со 100 000 распределенных вычислительных узлов. ЭО ПО должны одинаково эффективно масштабироваться как для систем с быстрыми межпроцессорными связями, так и для систем с медленными межпроцессорными связями.

2. В ходе работ по проекту были разработаны универсальные численные методы и оптимальные по сложности универсальные алгоритмы решения линейных систем над конечными полями, основанные на матричных аппроксимациях Паде. Предложенная оригинальная параметризация универсальных алгоритмов допускает баланс для времени, необходимого на алгоритмические вычисления, и для времени на обмен данными. В результате применения оптимальных параметризаций были получены оптимальные по сложности универсальные алгоритмы решения линейных систем над конечными полями, обладающие высокой масштабируемостью вычислений на вычислительных системах с различной параллельной архитектурой и с числом распределенных вычислительных узлов до 100 000. С целью повышения общей эффективности ЭО ПО, были разработаны параллельные алгоритмы линейной алгебры для нахождения вычислительно трудоемких блочных операций над конечными полями с большим числом элементов (порядка 10^150). Отличительной особенностью предложенных алгоритмов является использование оригинальных оптимизированных реализаций алгоритмов арифметики больших полей в применении к базовым операциям линейной алгебры с векторами и блоками. При написании отдельных модулей ЭО ПО были использованы оптимальные схемы хранения данных, использовались высокоэффективные технологии многопоточных (OpenMP) и многопроцессорных (MPI) вычислений.

3. На сегодняшний день для решения больших разреженных систем над конечными полями используются два подхода: блочные методы типа Ланцоша-Монтгомери и блочные методы типа Видемана-Копперсмита. Оба подхода имеют достоинства и недостатки. Простота методов типа Ланцоша нивелируется их ограниченным параллельным ресурсом. С другой стороны, использование большого параллельного ресурса блочных методов Видемана-Копперсмита невозможно без выполнения весьма жестких требований к используемым вычислительным системам, например к объему общей памяти. Разработанные в проекте универсальные алгоритмы, реализующие универсальный численный метод решения больших разреженных систем линейных уравнений над простыми конечными полями с большим числом элементов, а также универсальный численный метод решения больших разреженных систем линейных уравнений над конечным полем GF(2), лишены обоих недостатков. Проведенные численные эксперименты с ЭО ПО подтверждают хорошую масштабируемость вычислений для универсальных численных методов решения систем линейных уравнений над конечными полями.

4. Для достижения заявленных результатов в ходе проекта были:
а) разработаны универсальные численные методы решения линейных систем над конечными полями;
б) разработаны оптимальные по сложности универсальные алгоритмы решения линейных систем над конечными полями;
в) разработаны массивно-параллельные алгоритмы для вычислительно трудоемких операций с блоками;
г) разработаны быстрые реализации операций в больших конечных полях;
д) при создании ЭО ПО использовались высокоэффективные технологии многопоточных (Open MP) и многопроцессорных (MPI) вычислений, а также высокоэффективные "ассемблерные вставки" в критических местах алгоритма

Назначение и область применения, эффекты от внедрения результатов проекта:
1. Проблема решения больших систем линейных уравнений над конечными полями связана в первую очередь с задачей анализа криптостойкости существующих современных и будущих систем шифрования данных. К системам над большими полями приводит задача дискретного логарифмирования, на которой базируется криптография с открытым ключом. Классическими криптографическими схемами на основе задачи дискретного логарифмирования являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры. К системам линейных уравнений над полем GF(2) приводит задача факторизации составного числа на два простых множителя, сложность которой определяет криптостойкость системы шифрования RSA.

2. Результаты данного проекта могут быть использованы для анализа криптостойкости существующих и будущих систем шифрования.
Потенциальными потребителями научных результатов являются:
1. ФСБ РФ (установление новых параметров безопасности используемых в нашей стране схем защиты информации и криптоанализ схем, используемых зарубежными создателями программного обеспечения).
2. Научно-исследовательские коллективы, нуждающиеся в решении больших разреженных систем линейных уравнений над конечными полями.
3. Фирмы-производители пакетов программ компьютерной алгебры.
4. Крупные компьютерные фирмы-производители программного обеспечения, занимающиеся исследовательской работой в области защиты информации (IBM, Microsoft, RSA Labs, Oracle).

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

4. Результаты исследований показывают, что с технологической точки зрения существует подход к решению сверхбольших разреженных линейных систем над конечными полями, допускающий эффективную реализацию на высокопроизводительных вычислительных системах до 100 и более Tflops. Последнее, по-видимому, означает, что в ближайшее время при анализе современных параметров безопасности основные усилия будут сконцентрированы на построении более эффективных или усовершенствовании известных методов решета.

Текущие результаты проекта:
1. Разработан универсальный численный метод решения линейных систем над конечными полями с большим числом элементов (число элементов 10^150).
2. Разработан универсальный численный метод решения линейных систем над конечным полем с двумя элементами (над полем GF(2)).
3. Разработаны оптимальные по сложности алгоритмы решения линейных систем, реализующие разработанные методы на различных вычислительных системах.
4. Разработан массивно-параллельный метод для нахождения вычислительно трудоемких блочных операций.
5. Разработана версия ЭО ПО, предназначенная для решения сверхбольших разреженных линейных систем над конечными полями с большим числом элементов.
6. Разработана версия ЭО ПО, предназначенная для решения сверхбольших разреженных линейных систем над конечным полем с двумя элементами.
7. Разработаны программы и методики экспериментальных исследований разработанного ЭО ПО.
8. Проведены вычислительные эксперименты с разработанным ЭО ПО.