NDLI: Compact data structure and scalable algorithms for the sparse grid technique

Content Provider	ACM Digital Library
Author	Butnaru, Daniel Pflüger, Dirk Buse, Gerrit Murarasu, Alin Weidendorfer, Josef
Abstract	The sparse grid discretization technique enables a compressed representation of higher-dimensional functions. In its original form, it relies heavily on recursion and complex data structures, thus being far from well-suited for GPUs. In this paper, we describe optimizations that enable us to implement compression and decompression, the crucial sparse grid algorithms for our application, on Nvidia GPUs. The main idea consists of a bijective mapping between the set of points in a multi-dimensional sparse grid and a set of consecutive natural numbers. The resulting data structure consumes a minimum amount of memory. For a 10-dimensional sparse grid with approximately 127 million points, it consumes up to 30 times less memory than trees or hash tables which are typically used. Compared to a sequential CPU implementation, the speedups achieved on GPU are up to 17 for compression and up to 70 for decompression, respectively. We show that the optimizations are also applicable to multicore CPUs.
Starting Page	25
Ending Page	34
Page Count	10
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/2038037.1941559
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	46
Issue Number	8
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Sparse grids Performance optimization Gpu
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design 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

Compact data structure and scalable algorithms for the sparse grid technique

Scalable GPU graph traversal

Robust Parallel Preconditioned Power Grid Simulation on GPU With Adaptive Runtime Performance Modeling and Optimization

Scalable communication protocols for dynamic sparse data exchange

Compact data structure and scalable algorithms for the sparse grid technique (2011)

Scalable framework for mapping streaming applications onto multi-GPU systems

SPGrid: a sparse paged grid structure applied to adaptive smoke simulation

Scalable parallel minimum spanning forest computation

Automatic CPU-GPU communication management and optimization

Compact data structure and scalable algorithms for the sparse grid technique

Similar Documents

Compact data structure and scalable algorithms for the sparse grid technique

Scalable GPU graph traversal

Robust Parallel Preconditioned Power Grid Simulation on GPU With Adaptive Runtime Performance Modeling and Optimization

Scalable communication protocols for dynamic sparse data exchange

Compact data structure and scalable algorithms for the sparse grid technique (2011)

Scalable framework for mapping streaming applications onto multi-GPU systems

SPGrid: a sparse paged grid structure applied to adaptive smoke simulation

Scalable parallel minimum spanning forest computation

Automatic CPU-GPU communication management and optimization

Compact data structure and scalable algorithms for the sparse grid technique