NDLI: Dynamic data layouts for cache-conscious implementation of a class of signal transforms

Content Provider	IEEE Xplore Digital Library
Author	Neungsoo Park Prasanna, V.K.
Copyright Year	1991
Abstract	Effective utilization of cache memories is a key factor in achieving high performance for computing large signal transforms. Nonunit stride access in the computation of large signal transforms results in poor cache performance, leading to severe degradation in the overall performance. In this paper, we develop a cache-conscious technique, called a dynamic data layout, to improve the performance of large signal transforms. In our approach, data reorganization is performed between computation stages to reduce cache misses. We develop an efficient search algorithm to determine an optimal tree with the minimum execution time among possible factorization trees based on the size of the signal transform and the data access stride. Our approach is applied to compute the fast Fourier transform (FFT) and the Walsh-Hadamard transform (WHT). Experiments were performed on Alpha 21264, MIPS R10000, UltraSPARC III, and Pentium 4. Experimental results show that our FFT and WHT achieve performance improvement of up to 3.52 times over other state-of-the-art FFT and WHT packages. The proposed optimization is portable across various platforms.
Sponsorship	IEEE Signal Processing Society
Starting Page	2120
Ending Page	2134
Page Count	15
File Size	875019
File Format	PDF
ISSN	1053587X
Volume Number	52
Issue Number	7
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-07-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Degradation Packaging Fast Fourier transforms Computer architecture Cache memory High performance computing Subcontracting Computer science Software architecture Tree data structures
Content Type	Text
Resource Type	Article
Subject	Signal Processing Electrical and Electronic Engineering

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

Cache conscious Walsh-Hadamard transform

Dynamic data layouts for cache-conscious implementation of a class of signal transforms.

Dynamic data layouts for cache-conscious factorization of DFT

Implementation and performance of the fast Hartley transform

Memory usage reduction method for FFT implementations on DSP based embedded system

Conflict-Free Parallel Memory Accessing Techniques for FFT Architectures

Modular VLSI architectures for computing the arithmetic Fourier transform

A self-adapting distributed memory package for fast signal transforms

Computing discrete Fourier transform on a rectangular data array

Dynamic data layouts for cache-conscious implementation of a class of signal transforms

Similar Documents

Cache conscious Walsh-Hadamard transform

Dynamic data layouts for cache-conscious implementation of a class of signal transforms.

Dynamic data layouts for cache-conscious factorization of DFT

Implementation and performance of the fast Hartley transform

Memory usage reduction method for FFT implementations on DSP based embedded system

Conflict-Free Parallel Memory Accessing Techniques for FFT Architectures

Modular VLSI architectures for computing the arithmetic Fourier transform

A self-adapting distributed memory package for fast signal transforms

Computing discrete Fourier transform on a rectangular data array

Dynamic data layouts for cache-conscious implementation of a class of signal transforms