The implementation of the parallel orthogonalization algorithms in the shortest integer lattices basis problem.pdf Целью работы является демонстрация увеличения производительности алгоритмовприведения базиса целочисленных решёток за счёт замены рекуррентного алгоритмаГрама - Шмидта параллельными алгоритмами ортогонализации.Для приведения базиса решётки с экспоненциальной точностью 7 = 2( n_i ) / 2 доста-точно привести базис к ($ - LLL)-редуцированному базису, применив полиномиальныйпо временной сложности алгоритм Ленстра - Ленстра - Ловаса (LLL) [1]. Для приве-дения базиса решётки с точностью 7 Е [2(ra_i)/2 - е, 1] достаточно привести подмно-жество базиса решётки, состоящее из в ^ n векторов, к базису Коркина - Золотарева,применив блочный алгоритм Коркина - Золотарева (BKZ), чья временная сложностьзависит от размера блока, изменяясь от полиномиальной до экспоненциальной [1].Ключевой частью алгоритмов приведения базиса решёток является этап ортого-нализации, осуществляемый при помощи алгоритмов, вычисляющих QR-разложениематрицы базисных векторов. Традиционно, в силу своей геометрической наглядно-сти и простоты, для ортогонализации используется рекуррентный алгоритм Грама -Шмидта или его вычислительно устойчивый аналог - модифицированный алгоритмГрама - Шмидта [2]. Однако рекуррентная природа данного алгоритма препятствуетего распараллеливанию и делает его «узким местом» процедуры приведения бази-са решётки. Алгоритм Грама - Шмидта может быть заменён другими алгоритмами,осуществляющими QR-разложение, а именно алгоритмом отражения Хаусхолдера илиалгоритмом вращения Гивенса [3]. Их применение теоретически позволяет ускоритьпроцесс ортогонализации (n х ^-матрицы базиса решётки в n раз.В основе метода Гивенса лежит идея поворота векторов матрицы базиса с цельюпоследовательного обнуления координат векторов ортогонализуемого базиса. Однойиз ключевых особенностей алгоритма Гивенса является необходимость вычисленияквадратного корня и в два раза большее число операций по сравнению с алгорит-мом Хаусхолдера. Однако этот недостаток компенсируется отсутствием ветвления,что приводит к высокой эффективности исполнения данного алгоритма на векторныхвычислительных устройствах, в частности на видеокартах. Последнее обстоятельствопривело к реализации именно этого алгоритма в библиотеке CUBLAS [4].Алгоритм Хаусхолдера основан на использовании линейного преобразования орто-гонализуемой матрицы, которое осуществляет «отражение» векторов относительно ги-перплоскости, проходящей через начало координат. Каждое преобразование обнуляетчасть строки и столбца ортогонализуемого базиса. При распараллеливании алгорит-ма Хаусхолдера возникает необходимость взаимодействия процессов, осуществляющихортогонализацию, что в целом накладывает ограничения на реализацию данного ме-тода на устройствах с SIMD-архитектурой.В настоящей работе представлена библиотека, содержащая реализацию модифици-рованного алгоритма Грама - Шмидта, а также алгоритмов Хаусхолдера и Гивенса ипредназначенная специально для решения задач приведения базисов целочисленныхрешёток в рамках созданного ранее приложения LRT [5]. В процессе создания библио-теки реализован специальный менеджер памяти, обеспечивающий устойчивую работуприложения в целом. Полученное приложение апробировано на конкурсных задачахиз тестовых библиотек для алгоритмов приведения базиса решёток [6]. На рис. 1 при-ведено сравнение времени выполнения различных алгоритмов ортогонализации прирешении задачи приведения базиса решётки размера п. Последовательная реализа-ция метода Грама -Шмидта (S MGS) выполнялась на одном ядре CPU Phenom IIX4 965, метод Гивенса -на GPU GeForce Ti 550 1GB (NVIDIA CUDA), алгоритм Ха-усхолдера-на четырёх ядрах CPU Phenom II X4 965 (Intel Math Kernel Library).Из представленного графика видно, что применение параллельных методов ортого-нализации обеспечило 300-кратный прирост (устойчиво растущий с ростом размерарешётки) производительности по сравнению с последовательной реализацией методаГрама - Шмидта. В классе параллельных методов ортогонализации метод Гивенса,исполняемый на GPU, продемонстрировал незначительное преимущество перед мето-дом Хаусхолдера.1000,0000S MGS100,0000 - j - - f - |10.0000 id h * 1 1MKLси.§- 1,00000.1000Г 1 1 !0,0100Размер 1000 1500 zooo 2500 3000 3500 4000 4500CUDA 0,0400 0,0800 0,1700 0,2600 0,3300 0,5600 0,6700 0,9300MKL 0,0500 0,1600 0,2900 0,4700 0,8100 1,2100 1,7300 * 2/4600 |Serial MGS 3,7464 12,4582 29,8511 58,1017 99,5647 1623610237,3449342,4431Рис. 1. Зависимость времени (в секундах) выполнения алгорит-мов ортогонализации базиса решётки от её размера (од-нократная точность вычислений)

Скачать электронную версию публикации