Parallel Lattice Basis Reduction - The Road to Many-Core

Werner Backes; Susanne Wetzel

doi:10.1109/HPCC.2011.61

Parallel Lattice Basis Reduction - The Road to Many-Core

Source

2011 IEEE International Conference on High Performance Computing and Communications > 417 - 424

Abstract

This paper introduces a new parallel algorithm that allows for an efficient LLL reduction using today's emerging many-core systems. This work develops suitable methods that efficiently implement the idea of splitting a lattice basis into smaller sub problems, LLL reducing the sub problems, and recombining the sub problems afterwards to obtain an overall LLL reduced basis. The new many-core algorithm outperforms any current parallel LLL algorithm. Experiments on a 48-core test system show a speed-up of approximately 10 for SVP challenge type lattice bases and a remarkable speed-up of approximately 50 for knapsack type lattice bases.