Installation and Customization
******************************

This chapter describes the installation and customization of FFTW, the latest version of which may be downloaded from the FFTW home page (http://www.fftw.org).

In principle, FFTW should work on any system with an ANSI C compiler (gcc is fine).  However, planner time is drastically reduced if FFTW can exploit a hardware cycle counter; FFTW comes with cycle-counter support for all modern general-purpose CPUs, but you may need to add a couple of lines of code if your compiler is not yet supported (see Cycle Counters).  (On Unix, there will be a warning at the end of the configure output if no cycle counter is found.)

Installation of FFTW is simplest if you have a Unix or a GNU system, such as GNU/Linux, and we describe this case in the first section below, including the use of special configuration options to e.g. install different precisions or exploit optimizations for particular architectures (e.g. SIMD).  Compilation on non-Unix systems is a more manual process, but we outline the procedure in the second section.  It is also likely that pre-compiled binaries will be available for popular systems.

Finally, we describe how you can customize FFTW for particular needs by generating codelets for fast transforms of sizes not supported efficiently by the standard FFTW distribution.

Installation on Unix
====================

FFTW comes with a configure program in the GNU style. Installation can be as simple as:

     ./configure
     make
     make install

This will build the uniprocessor complex and real transform libraries along with the test programs.  (We recommend that you use GNU make if it is available; on some systems it is called gmake.)  The ``make install'' command installs the fftw and rfftw libraries in standard places, and typically requires root privileges (unless you specify a different install directory with the --prefix flag to configure).  You can also type ``make check'' to put the FFTW test programs through their paces. If you have problems during configuration or compilation, you may want to run ``make distclean'' before trying again; this ensures that you don't have any stale files left over from previous compilation attempts.

The configure script chooses the gcc compiler by default, if it is available; you can select some other compiler with:

     ./configure CC="<the name of your C compiler>"

The configure script knows good CFLAGS (C compiler flags) for a few systems.  If your system is not known, the configure script will print out a warning.  In this case, you should re-configure FFTW with the command

     ./configure CFLAGS="<write your CFLAGS here>"

and then compile as usual.  If you do find an optimal set of CFLAGS for your system, please let us know what they are (along with the output of config.guess) so that we can include them in future releases.

configure supports all the standard flags defined by the GNU Coding Standards; see the INSTALL file in FFTW or the GNU web page (http://www.gnu.org/prep/standards/html_node/index.html). Note especially --help to list all flags and --enable-shared to create shared, rather than static, libraries. configure also accepts a few FFTW-specific flags, particularly:

  * --enable-float: Produces a single-precision version of FFTW (float) instead of the default double-precision (double). See Precision.

  * --enable-long-double: Produces a long-double precision version of FFTW (long double) instead of the default double-precision (double).  The configure script will halt with an error message if long double is the same size as double on your machine/compiler.  See Precision.

  * --enable-quad-precision: Produces a quadruple-precision version of FFTW using the nonstandard __float128 type provided by gcc 4.6 or later on x86, x86-64, and Itanium architectures, instead of the default double-precision (double).  The configure script will halt with an error message if the compiler is not gcc version 4.6 or later or if gcc's libquadmath library is not installed.  See Precision.

  * --enable-threads: Enables compilation and installation of the FFTW threads library (see Multi-threaded FFTW), which provides a simple interface to parallel transforms for SMP systems.  By default, the threads routines are not compiled.

  * --enable-openmp: Like --enable-threads, but using OpenMP compiler directives in order to induce parallelism rather than spawning its own threads directly, and installing an fftw3_omp library rather than an fftw3_threads library (see Multi-threaded FFTW).  You can use both --enable-openmp and --enable-threads since they compile/install libraries with different names.  By default, the OpenMP routines are not compiled.

  * --with-combined-threads: By default, if --enable-threads is used, the threads support is compiled into a separate library that must be linked in addition to the main FFTW library.  This is so that users of the serial library do not need to link the system threads libraries.  If --with-combined-threads is specified, however, then no separate threads library is created, and threads are included in the main FFTW library.  This is mainly useful under Windows, where no system threads library is required and inter-library dependencies are problematic.

  * --enable-mpi: Enables compilation and installation of the FFTW MPI library (see Distributed-memory FFTW with MPI), which provides parallel transforms for distributed-memory systems with MPI.  (By default, the MPI routines are not compiled.)  See FFTW MPI Installation.

  * --disable-fortran: Disables inclusion of legacy-Fortran wrapper routines (see Calling FFTW from Legacy Fortran) in the standard FFTW libraries.  These wrapper routines increase the library size by only a negligible amount, so they are included by default as long as the configure script finds a Fortran compiler on your system. (To specify a particular Fortran compiler foo, pass F77=foo to configure.)

  * --with-g77-wrappers: By default, when Fortran wrappers are included, the wrappers employ the linking conventions of the Fortran compiler detected by the configure script.  If this compiler is GNU g77, however, then two versions of the wrappers are included: one with g77's idiosyncratic convention of appending two underscores to identifiers, and one with the more common convention of appending only a single underscore.  This way, the same FFTW library will work with both g77 and other Fortran compilers, such as GNU gfortran.  However, the converse is not true: if you configure with a different compiler, then the g77-compatible wrappers are not included.  By specifying --with-g77-wrappers, the g77-compatible wrappers are included in addition to wrappers for whatever Fortran compiler configure finds.

  * --with-slow-timer: Disables the use of hardware cycle counters, and falls back on gettimeofday or clock.  This greatly worsens performance, and should generally not be used (unless you don't have a cycle counter but still really want an optimized plan regardless of the time).  See Cycle Counters.

  * --enable-sse, --enable-sse2, --enable-avx, --enable-altivec: Enable the compilation of SIMD code for SSE (Pentium III+), SSE2 (Pentium IV+), AVX (Sandy Bridge, Interlagos), AltiVec (PowerPC G4+).  SSE and AltiVec only work with --enable-float (above).  SSE2 works in both single and double precision (and is simply SSE in single precision).  The resulting code will still work on earlier CPUs lacking the SIMD extensions (SIMD is automatically disabled, although the FFTW library is still larger).

       - These options require a compiler supporting SIMD extensions, and compiler support is always a bit flaky: see the FFTW FAQ for a list of compiler versions that have problems compiling FFTW.

       - With AltiVec and gcc, you may have to use the -mabi=altivec option when compiling any code that links to FFTW, in order to properly align the stack; otherwise, FFTW could crash when it tries to use an AltiVec feature.  (This is not necessary on MacOS X.)

       - With SSE/SSE2 and gcc, you should use a version of gcc that properly aligns the stack when compiling any code that links to FFTW. By default, gcc 2.95 and later versions align the stack as needed, but you should not compile FFTW with the -Os option or the -mpreferred-stack-boundary option with an argument less than 4.

To force configure to use a particular C compiler foo (instead of the default, usually gcc), pass CC=foo to the configure script; you may also need to set the flags via the variable CFLAGS as described above.

Installation on non-Unix systems
================================

It should be relatively straightforward to compile FFTW even on non-Unix systems lacking the niceties of a configure script.  Basically, you need to edit the config.h header (copy it from config.h.in) to #define the various options and compiler characteristics, and then compile all the .c files in the relevant directories.

The config.h header contains about 100 options to set, each one initially an #undef, each documented with a comment, and most of them fairly obvious.  For most of the options, you should simply #define them to 1 if they are applicable, although a few options require a particular value (e.g. SIZEOF_LONG_LONG should be defined to the size of the long long type, in bytes, or zero if it is not supported).  We will likely post some sample config.h files for various operating systems and compilers for you to use (at least as a starting point).  Please let us know if you have to hand-create a configuration file (and/or a pre-compiled binary) that you want to share.

To create the FFTW library, you will then need to compile all of the .c files in the kernel, dft, dft/scalar, dft/scalar/codelets, rdft, rdft/scalar, rdft/scalar/r2cf, rdft/scalar/r2cb, rdft/scalar/r2r, reodft, and api directories. If you are compiling with SIMD support (e.g. you defined HAVE_SSE2 in config.h), then you also need to compile the .c files in the simd-support, {dft,rdft}/simd, {dft,rdft}/simd/* directories.

Once these files are all compiled, link them into a library, or a shared library, or directly into your program.

To compile the FFTW test program, additionally compile the code in the libbench2/ directory, and link it into a library.  Then compile the code in the tests/ directory and link it to the libbench2 and FFTW libraries.  To compile the fftw-wisdom (command-line) tool (see Wisdom Utilities), compile tools/fftw-wisdom.c and link it to the libbench2 and FFTW libraries

Cycle Counters
==============

FFTW's planner actually executes and times different possible FFT algorithms in order to pick the fastest plan for a given n.  In order to do this in as short a time as possible, however, the timer must have a very high resolution, and to accomplish this we employ the hardware cycle counters that are available on most CPUs. Currently, FFTW supports the cycle counters on x86, PowerPC/POWER, Alpha, UltraSPARC (SPARC v9), IA64, PA-RISC, and MIPS processors.

Access to the cycle counters, unfortunately, is a compiler and/or operating-system dependent task, often requiring inline assembly language, and it may be that your compiler is not supported.  If you are not supported, FFTW will by default fall back on its estimator (effectively using FFTW_ESTIMATE for all plans).

You can add support by editing the file kernel/cycle.h; normally, this will involve adapting one of the examples already present in order to use the inline-assembler syntax for your C compiler, and will only require a couple of lines of code.  Anyone adding support for a new system to cycle.h is encouraged to email us at fftw@fftw.org.

If a cycle counter is not available on your system (e.g. some embedded processor), and you don't want to use estimated plans, as a last resort you can use the --with-slow-timer option to configure (on Unix) or #define WITH_SLOW_TIMER in config.h (elsewhere). This will use the much lower-resolution gettimeofday function, or even clock if the former is unavailable, and planning will be extremely slow.

Generating your own code
========================

The directory genfft contains the programs that were used to generate FFTW's ``codelets,'' which are hard-coded transforms of small sizes. We do not expect casual users to employ the generator, which is a rather sophisticated program that generates directed acyclic graphs of FFT algorithms and performs algebraic simplifications on them.  It was written in Objective Caml, a dialect of ML, which is available at http://caml.inria.fr/ocaml/index.en.html.

If you have Objective Caml installed (along with recent versions of GNU autoconf, automake, and libtool), then you can change the set of codelets that are generated or play with the generation options.  The set of generated codelets is specified by the {dft,rdft}/{codelets,simd}/*/Makefile.am files.  For example, you can add efficient REDFT codelets of small sizes by modifying rdft/codelets/r2r/Makefile.am. After you modify any Makefile.am files, you can type sh bootstrap.sh in the top-level directory followed by make to re-generate the files.

We do not provide more details about the code-generation process, since we do not expect that most users will need to generate their own code. However, feel free to contact us at fftw@fftw.org if you are interested in the subject.

You might find it interesting to learn Caml and/or some modern programming techniques that we used in the generator (including monadic programming), especially if you heard the rumor that Java and object-oriented programming are the latest advancement in the field. The internal operation of the codelet generator is described in the paper, ``A Fast Fourier Transform Compiler,'' by M. Frigo, which is available from the FFTW home page (http://www.fftw.org) and also appeared in the Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).