NDLI: High performance lattice reduction on heterogeneous computing platform

Content Provider	Springer Nature Link
Author	Józsa, Csaba M. Domene, Fernando Vidal, Antonio M. Piñero, Gema González, Alberto
Copyright Year	2014
Abstract	The lattice reduction (LR) technique has become very important in many engineering fields. However, its high complexity makes difficult its use in real-time applications, especially in applications that deal with large matrices. As a solution, the modified block LLL (MB-LLL) algorithm was introduced, where several levels of parallelism were exploited: (a) fine-grained parallelism was achieved through the cost-reduced all-swap LLL (CR-AS-LLL) algorithm introduced together with the MB-LLL by Józsa et al. (Proceedings of the tenth international symposium on wireless communication systems, 2013) and (b) coarse-grained parallelism was achieved by applying the block-reduction concept presented by Wetzel (Algorithmic number theory. Springer, New York, pp 323–337, 1998). In this paper, we present the cost-reduced MB-LLL (CR-MB-LLL) algorithm, which allows to significantly reduce the computational complexity of the MB-LLL by allowing the relaxation of the first LLL condition while executing the LR of submatrices, resulting in the delay of the Gram–Schmidt coefficients update and by using less costly procedures during the boundary checks. The effects of complexity reduction and implementation details are analyzed and discussed for several architectures. A mapping of the CR-MB-LLL on a heterogeneous platform is proposed and it is compared with implementations running on a dynamic parallelism enabled GPU and a multi-core CPU. The mapping on the architecture proposed allows a dynamic scheduling of kernels where the overhead introduced is hidden by the use of several CUDA streams. Results show that the execution time of the CR-MB-LLL algorithm on the heterogeneous platform outperforms the multi-core CPU and it is more efficient than the CR-AS-LLL algorithm in case of large matrices.
Starting Page	772
Ending Page	785
Page Count	14
File Format	PDF
ISSN	09208542
Journal	The Journal of Supercomputing
Volume Number	70
Issue Number	2
e-ISSN	15730484
Language	English
Publisher	Springer US
Publisher Date	2014-05-16
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Lattice reduction LLL GPU CUDA OpenMP Programming Languages, Compilers, Interpreters Processor Architectures Computer Science
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Information Systems Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Automatic code generation for GPUs in llc

An efficient scheduling scheme using estimated execution time for heterogeneous computing systems

An efficient parallel collaborative filtering algorithm on multi-GPU platform

MIMOPack: a high-performance computing library for MIMO communication systems

Accelerating 2D orthogonal matching pursuit algorithm on GPU

High Performance Air Pollution Simulation Using OpenMP

Accelerating HEVC using heterogeneous platforms

A compound OpenMP/MPI program development toolkit for hybrid CPU/GPU clusters

Comparative evaluation of platforms for parallel Ant Colony Optimization

High performance lattice reduction on heterogeneous computing platform

Similar Documents

Automatic code generation for GPUs in llc

An efficient scheduling scheme using estimated execution time for heterogeneous computing systems

An efficient parallel collaborative filtering algorithm on multi-GPU platform

MIMOPack: a high-performance computing library for MIMO communication systems

Accelerating 2D orthogonal matching pursuit algorithm on GPU

High Performance Air Pollution Simulation Using OpenMP

Accelerating HEVC using heterogeneous platforms

A compound OpenMP/MPI program development toolkit for hybrid CPU/GPU clusters

Comparative evaluation of platforms for parallel Ant Colony Optimization

High performance lattice reduction on heterogeneous computing platform