NDLI: How to unleash array optimizations on code using recursive data structures

Please wait, while we are loading the content...

Exascale science: the next frontier in high performance computing

Overlapping communication and computation by using a hybrid MPI/SMPSs approach

The auction: optimizing banks usage in Non-Uniform Cache Architectures

Fast and accurate NCBI BLASTP: acceleration with multiphase FPGA-based prefiltering

Streamlining GPU applications on the fly: thread divergence elimination through runtime thread-data remapping

Decomposable and responsive power models for multicore processors using performance counters

An approach to resource-aware co-scheduling for CMPs

Indemics: an interactive data intensive framework for high performance epidemic simulation

Handling task dependencies under strided and aliased references

An empirically tuned 2D and 3D FFT library on CUDA GPU

Throughput computing

Quantifying performance benefits of overlap using MPI-2 in a seismic modeling application

Cache oblivious parallelograms in iterative stencil computations

ParaLearn: a massively parallel, scalable system for learning interaction networks on FPGAs

An experimental approach to performance measurement of heterogeneous parallel applications using CUDA

Enigma: architectural and operating system support for reducing the impact of address translation

A query language for understanding component interactions in production systems

Clustering performance data efficiently at massive scales

How to unleash array optimizations on code using recursive data structures

Large-scale FFT on GPU clusters

The next-generation supercomputer project and a plan for the advanced institute for computational science

Optimal bucket algorithms for large MPI collectives on torus interconnects

Making nested parallel transactions practical using lightweight hardware support

High-throughput Bayesian network learning using heterogeneous multicore computers

Compiler and runtime support for enabling generalized reduction computations on heterogeneous parallel configurations

Timing local streams: improving timeliness in data prefetching

Adaptive multi-level cache allocation in distributed storage architectures

Speeding up Nek5000 with autotuning and specialization

A compiler-automated array compression scheme for optimizing memory intensive programs

FPGA accelerating double/quad-double high precision floating-point applications for ExaScale computing

Evaluation of parallel H.264 decoding strategies for the Cell Broadband Engine

SAMS multi-layout memory: providing multiple views of data to boost SIMD performance

InterferenceRemoval: removing interference of disk access for MPI programs through data replication

Static reuse distances for locality-based optimizations in MATLAB

Small-ruleset regular expression matching on GPGPUs: quantitative performance analysis and optimization

How to unleash array optimizations on code using recursive data structures

Content Provider	ACM Digital Library
Author	van der Spek, Harmen L. A. Holm, C. W. Mattias Wijshoff, Harry A. G.
Abstract	Loop optimization and parallelization have been most successful on code using arrays exclusively. Preferably, such code does not contain indirect access and has only simple, counted loops. The use of recursive data structures makes matters even worse, and optimization of such code has been less successful. Traversal of such data structures is often done using loops with data-dependent loop conditions. In this paper, we present a compiler transformation chain that transforms pointer traversal loops into counted loops operating on arrays that are indirectly accessed. We also show that this indirect access can in some cases be eliminated if the traversed data structure is reordered in memory. This results in a representation on which many existing techniques can be applied. Our system requires monitoring of actual arguments and heap data on which loop conditions depend so that preconditions for the optimized functions can be checked. Our experiments show that this overhead is small, considering the optimization opportunities the representation of the transformed code provides, and well worth the price.
Starting Page	275
Ending Page	284
Page Count	10
File Format	PDF
ISBN	9781450300186
DOI	10.1145/1810085.1810123
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-02
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Control flow optimization Restructuring compilers Recursive data structures Pointer optimization
Content Type	Text
Resource Type	Article

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

A general compiler framework for speculative optimizations using data speculative code motion

An introduction to compilers (2000).

Heap Analysis And Optimizations For Threaded Programs

Classical compiler optimizations on multithreaded code.

Detecting Coarse - Grain Parallelism Using an Interprocedural Parallelizing Compiler

A Cost Model for Integrated Restructuring Optimizations

Generic control flow reconstruction from assembly code

Transparent pointer compression for linked data structures

Predicting the impact of optimizations for embedded systems

How to unleash array optimizations on code using recursive data structures

Similar Documents

A general compiler framework for speculative optimizations using data speculative code motion

An introduction to compilers (2000).

Heap Analysis And Optimizations For Threaded Programs

Classical compiler optimizations on multithreaded code.

Detecting Coarse - Grain Parallelism Using an Interprocedural Parallelizing Compiler

A Cost Model for Integrated Restructuring Optimizations

Generic control flow reconstruction from assembly code

Transparent pointer compression for linked data structures

Predicting the impact of optimizations for embedded systems

How to unleash array optimizations on code using recursive data structures