WebSVN - shark - Blame - Rev 1618 - /shark/branches/xen/ports/fftw/doc/fftw

Rev	Author	Line No.	Line
2	pj	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
		2	<HTML>
		3	<HEAD>
		4	<!-- This HTML file has been created by texi2html 1.52
		5	from fftw.texi on 18 May 1999 -->
		6
		7	<TITLE>FFTW - Introduction</TITLE>
		8	</HEAD>
		9	<BODY TEXT="#000000" BGCOLOR="#FFFFFF">
		10	Go to the first, previous, <A HREF="fftw_2.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.
		11	<P><HR><P>
		12
		13
		14	<H1><A NAME="SEC1">Introduction</A></H1>
		15	<P>
		16	This manual documents version 2.1.2 of FFTW, the <EM>Fastest
		17	Fourier Transform in the West</EM>. FFTW is a comprehensive collection of
		18	fast C routines for computing the discrete Fourier transform (DFT) in
		19	one or more dimensions, of both real and complex data, and of arbitrary
		20	input size. FFTW also includes parallel transforms for both shared- and
		21	distributed-memory systems. We assume herein that the reader is already
		22	familiar with the properties and uses of the DFT that are relevant to
		23	her application. Otherwise, see e.g. <CITE>The Fast Fourier Transform</CITE>
		24	by E. O. Brigham (Prentice-Hall, Englewood Cliffs, NJ, 1974).
		25	<A HREF="http://theory.lcs.mit.edu/~fftw">Our web page</A> also has links to
		26	FFT-related information online.
		27	<A NAME="IDX1"></A>
		28
		29
		30	<P>
		31	FFTW is usually faster (and sometimes much faster) than all other
		32	freely-available Fourier transform programs found on the Net. For
		33	transforms whose size is a power of two, it compares favorably with the
		34	FFT codes in Sun's Performance Library and IBM's ESSL library, which are
		35	targeted at specific machines. Moreover, FFTW's performance is
		36	<EM>portable</EM>. Indeed, FFTW is unique in that it automatically adapts
		37	itself to your machine, your cache, the size of your memory, the number
		38	of registers, and all the other factors that normally make it impossible
		39	to optimize a program for more than one machine. An extensive
		40	comparison of FFTW's performance with that of other Fourier transform
		41	codes has been made. The results are available on the Web at
		42	<A HREF="http://theory.lcs.mit.edu/~benchfft">the benchFFT home page</A>.
		43	<A NAME="IDX2"></A>
		44	<A NAME="IDX3"></A>
		45
		46
		47	<P>
		48	In order to use FFTW effectively, you need to understand one basic
		49	concept of FFTW's internal structure. FFTW does not used a fixed
		50	algorithm for computing the transform, but it can adapt the DFT
		51	algorithm to details of the underlying hardware in order to achieve best
		52	performance. Hence, the computation of the transform is split into two
		53	phases. First, FFTW's <EM>planner</EM> is called, which "learns" the
		54	<A NAME="IDX4"></A>
		55	fastest way to compute the transform on your machine. The planner
		56	<A NAME="IDX5"></A>
		57	produces a data structure called a <EM>plan</EM> that contains this
		58	information. Subsequently, the plan is passed to FFTW's <EM>executor</EM>,
		59	<A NAME="IDX6"></A>
		60	along with an array of input data. The executor computes the actual
		61	transform, as dictated by the plan. The plan can be reused as many
		62	times as needed. In typical high-performance applications, many
		63	transforms of the same size are computed, and consequently a
		64	relatively-expensive initialization of this sort is acceptable. On the
		65	other hand, if you need a single transform of a given size, the one-time
		66	cost of the planner becomes significant. For this case, FFTW provides
		67	fast planners based on heuristics or on previously computed plans.
		68
		69
		70	<P>
		71	The pattern of planning/execution applies to all four operation modes of
		72	FFTW, that is, I) one-dimensional complex transforms (FFTW), II)
		73	multi-dimensional complex transforms (FFTWND), III) one-dimensional
		74	transforms of real data (RFFTW), IV) multi-dimensional transforms of
		75	real data (RFFTWND). Each mode comes with its own planner and executor.
		76
		77
		78	<P>
		79	Besides the automatic performance adaptation performed by the planner,
		80	it is also possible for advanced users to customize FFTW for their
		81	special needs. As distributed, FFTW works most efficiently for arrays
		82	whose size can be factored into small primes (2, 3,
		83	5, and 7), and uses a slower general-purpose routine for
		84	other factors. FFTW, however, comes with a code generator that can
		85	produce fast C programs for any particular array size you may care
		86	about.
		87	<A NAME="IDX7"></A>
		88	For example, if you need transforms of size
		89	513 = 19*3<sup>3</sup>,
		90	you can customize FFTW to support the factor 19 efficiently.
		91
		92
		93	<P>
		94	FFTW can exploit multiple processors if you have them. FFTW comes with
		95	a shared-memory implementation on top of POSIX (and similar) threads, as
		96	well as a distributed-memory implementation based on MPI.
		97	<A NAME="IDX8"></A>
		98	<A NAME="IDX9"></A>
		99	<A NAME="IDX10"></A>
		100	We also provide an experimental parallel implementation written in Cilk,
		101	<EM>the superior programming tool of choice for discriminating
		102	hackers</EM> (Olin Shivers). (See <A HREF="http://supertech.lcs.mit.edu/cilk">the Cilk home page</A>.)
		103	<A NAME="IDX11"></A>
		104
		105
		106	<P>
		107	For more information regarding FFTW, see the paper, "The Fastest
		108	Fourier Transform in the West," by M. Frigo and S. G. Johnson, which is
		109	the technical report MIT-LCS-TR-728 (Sep. '97). See also, "FFTW: An
		110	Adaptive Software Architecture for the FFT," by M. Frigo and
		111	S. G. Johnson, which appeared in the 23rd International Conference on
		112	Acoustics, Speech, and Signal Processing (<CITE>Proc. ICASSP 1998</CITE>
		113	<B>3</B>, p. 1381). The code generator is described in the paper "A Fast
		114	Fourier Transform Compiler",
		115	<A NAME="IDX12"></A>
		116	by M. Frigo, to appear in the <CITE>Proceedings of the 1999 ACM SIGPLAN
		117	Conference on Programming Language Design and Implementation (PLDI),
		118	Atlanta, Georgia, May 1999</CITE>. These papers, along with the latest
		119	version of FFTW, the FAQ, benchmarks, and other links, are available at
		120	<A HREF="http://theory.lcs.mit.edu/~fftw">the FFTW home page</A>. The current
		121	version of FFTW incorporates many good ideas from the past thirty years
		122	of FFT literature. In one way or another, FFTW uses the Cooley-Tukey
		123	algorithm, the Prime Factor algorithm, Rader's algorithm for prime
		124	sizes, and the split-radix algorithm (with a variation due to Dan
		125	Bernstein). Our code generator also produces new algorithms that we do
		126	not yet completely understand.
		127	<A NAME="IDX13"></A>
		128	The reader is referred to the cited papers for the appropriate
		129	references.
		130
		131
		132	<P>
		133	The rest of this manual is organized as follows. We first discuss the
		134	sequential (one-processor) implementation. We start by describing the
		135	basic features of FFTW in Section <A HREF="fftw_2.html#SEC2">Tutorial</A>. This discussion includes the
		136	storage scheme of multi-dimensional arrays (Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>) and FFTW's mechanisms for storing plans on disk (Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>). Next, Section <A HREF="fftw_3.html#SEC16">FFTW Reference</A> provides comprehensive
		137	documentation of all FFTW's features. Parallel transforms are discussed
		138	in their own chapter Section <A HREF="fftw_4.html#SEC47">Parallel FFTW</A>. Fortran programmers can also
		139	use FFTW, as described in Section <A HREF="fftw_5.html#SEC62">Calling FFTW from Fortran</A>.
		140	Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A> explains how to install FFTW in
		141	your computer system and how to adapt FFTW to your needs. License and
		142	copyright information is given in Section <A HREF="fftw_8.html#SEC74">License and Copyright</A>. Finally,
		143	we thank all the people who helped us in Section <A HREF="fftw_7.html#SEC73">Acknowledgments</A>.
		144
		145
		146	<P><HR><P>
		147	Go to the first, previous, <A HREF="fftw_2.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.
		148	</BODY>
		149	</HTML>

Subversion Repositories shark

(root)/shark/branches/xen/ports/fftw/doc/fftw_1.htm - Rev 1618