NDLI: Mechanical Derivation of Fused Multiply–Add Algorithms for Linear Transforms

Content Provider	IEEE Xplore Digital Library
Author	Voronenko, Y. Puschel, M.
Copyright Year	1991
Abstract	Several computer architectures offer fused multiply-add (FMA), also called multiply-and-accumulate (MAC) instructions, that are as fast as a single addition or multiplication. For the efficient implementation of linear transforms, such as the discrete Fourier transform or discrete cosine transforms, this poses a challenge to algorithm developers as standard transform algorithms have to be manipulated into FMA algorithms that make optimal use of FMA instructions. We present a general method to convert any transform algorithm into an FMA algorithm. The method works with both algorithms given as directed acyclic graphs (DAGs) and algorithms given as structured matrix factorizations. We prove bounds on the efficiency of the method. In particular, we show that it removes all single multiplications except at most as many as the transform has outputs. We implemented the DAG-based version of the method and show that we can generate many of the best-known hand-derived FMA algorithms from the literature as well as a few novel FMA algorithms.
Sponsorship	IEEE Signal Processing Society
Starting Page	4458
Ending Page	4473
Page Count	16
File Size	769090
File Format	PDF
ISSN	1053587X
Volume Number	55
Issue Number	9
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-09-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	Discrete Fourier transforms Discrete cosine transforms Discrete transforms Computer architecture Fourier transforms Costs Standards development Matrix converters Computer aided instruction Hardware multiply and accumulate (MAC) Automatic program generation discrete cosine transform (DCT) discrete Fourier transform (DFT) fast algorithm implementation multiply-and-accumulate (MAC) instruction
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

Bidirectional conversion between DCT coefficients of blocks and their subblocks

On the odd-DFT and its applications to DCT/IDCT computation

Transform Coefficient Histogram-Based Image Enhancement Algorithms Using Contrast Entropy

Hardware implementation of discrete cosine transform

A new texture generation method based on pseudo-DCT coefficients

Algebraic Signal Processing Theory: Cooley–Tukey Type Algorithms for DCTs and DSTs

Implementation of Efficient FFT Algorithms on Fused Multiply- Add Architectures

Fast DCT domain filtering using the DCT and the DST

A Fast Computational Algorithm for the Discrete Cosine Transform

Mechanical Derivation of Fused Multiply–Add Algorithms for Linear Transforms

Similar Documents

Bidirectional conversion between DCT coefficients of blocks and their subblocks

On the odd-DFT and its applications to DCT/IDCT computation

Transform Coefficient Histogram-Based Image Enhancement Algorithms Using Contrast Entropy

Hardware implementation of discrete cosine transform

A new texture generation method based on pseudo-DCT coefficients

Algebraic Signal Processing Theory: Cooley–Tukey Type Algorithms for DCTs and DSTs

Implementation of Efficient FFT Algorithms on Fused Multiply- Add Architectures

Fast DCT domain filtering using the DCT and the DST

A Fast Computational Algorithm for the Discrete Cosine Transform

Mechanical Derivation of Fused Multiply–Add Algorithms for Linear Transforms