Chris@42: @node Multi-threaded FFTW, Distributed-memory FFTW with MPI, FFTW Reference, Top Chris@42: @chapter Multi-threaded FFTW Chris@42: Chris@42: @cindex parallel transform Chris@42: In this chapter we document the parallel FFTW routines for Chris@42: shared-memory parallel hardware. These routines, which support Chris@42: parallel one- and multi-dimensional transforms of both real and Chris@42: complex data, are the easiest way to take advantage of multiple Chris@42: processors with FFTW. They work just like the corresponding Chris@42: uniprocessor transform routines, except that you have an extra Chris@42: initialization routine to call, and there is a routine to set the Chris@42: number of threads to employ. Any program that uses the uniprocessor Chris@42: FFTW can therefore be trivially modified to use the multi-threaded Chris@42: FFTW. Chris@42: Chris@42: A shared-memory machine is one in which all CPUs can directly access Chris@42: the same main memory, and such machines are now common due to the Chris@42: ubiquity of multi-core CPUs. FFTW's multi-threading support allows Chris@42: you to utilize these additional CPUs transparently from a single Chris@42: program. However, this does not necessarily translate into Chris@42: performance gains---when multiple threads/CPUs are employed, there is Chris@42: an overhead required for synchronization that may outweigh the Chris@42: computatational parallelism. Therefore, you can only benefit from Chris@42: threads if your problem is sufficiently large. Chris@42: @cindex shared-memory Chris@42: @cindex threads Chris@42: Chris@42: @menu Chris@42: * Installation and Supported Hardware/Software:: Chris@42: * Usage of Multi-threaded FFTW:: Chris@42: * How Many Threads to Use?:: Chris@42: * Thread safety:: Chris@42: @end menu Chris@42: Chris@42: @c ------------------------------------------------------------ Chris@42: @node Installation and Supported Hardware/Software, Usage of Multi-threaded FFTW, Multi-threaded FFTW, Multi-threaded FFTW Chris@42: @section Installation and Supported Hardware/Software Chris@42: Chris@42: All of the FFTW threads code is located in the @code{threads} Chris@42: subdirectory of the FFTW package. On Unix systems, the FFTW threads Chris@42: libraries and header files can be automatically configured, compiled, Chris@42: and installed along with the uniprocessor FFTW libraries simply by Chris@42: including @code{--enable-threads} in the flags to the @code{configure} Chris@42: script (@pxref{Installation on Unix}), or @code{--enable-openmp} to use Chris@42: @uref{http://www.openmp.org,OpenMP} threads. Chris@42: @fpindex configure Chris@42: Chris@42: Chris@42: @cindex portability Chris@42: @cindex OpenMP Chris@42: The threads routines require your operating system to have some sort Chris@42: of shared-memory threads support. Specifically, the FFTW threads Chris@42: package works with POSIX threads (available on most Unix variants, Chris@42: from GNU/Linux to MacOS X) and Win32 threads. OpenMP threads, which Chris@42: are supported in many common compilers (e.g. gcc) are also supported, Chris@42: and may give better performance on some systems. (OpenMP threads are Chris@42: also useful if you are employing OpenMP in your own code, in order to Chris@42: minimize conflicts between threading models.) If you have a Chris@42: shared-memory machine that uses a different threads API, it should be Chris@42: a simple matter of programming to include support for it; see the file Chris@42: @code{threads/threads.c} for more detail. Chris@42: Chris@42: You can compile FFTW with @emph{both} @code{--enable-threads} and Chris@42: @code{--enable-openmp} at the same time, since they install libraries Chris@42: with different names (@samp{fftw3_threads} and @samp{fftw3_omp}, as Chris@42: described below). However, your programs may only link to @emph{one} Chris@42: of these two libraries at a time. Chris@42: Chris@42: Ideally, of course, you should also have multiple processors in order to Chris@42: get any benefit from the threaded transforms. Chris@42: Chris@42: @c ------------------------------------------------------------ Chris@42: @node Usage of Multi-threaded FFTW, How Many Threads to Use?, Installation and Supported Hardware/Software, Multi-threaded FFTW Chris@42: @section Usage of Multi-threaded FFTW Chris@42: Chris@42: Here, it is assumed that the reader is already familiar with the usage Chris@42: of the uniprocessor FFTW routines, described elsewhere in this manual. Chris@42: We only describe what one has to change in order to use the Chris@42: multi-threaded routines. Chris@42: Chris@42: @cindex OpenMP Chris@42: First, programs using the parallel complex transforms should be linked Chris@42: with @code{-lfftw3_threads -lfftw3 -lm} on Unix, or @code{-lfftw3_omp Chris@42: -lfftw3 -lm} if you compiled with OpenMP. You will also need to link Chris@42: with whatever library is responsible for threads on your system Chris@42: (e.g. @code{-lpthread} on GNU/Linux) or include whatever compiler flag Chris@42: enables OpenMP (e.g. @code{-fopenmp} with gcc). Chris@42: @cindex linking on Unix Chris@42: Chris@42: Chris@42: Second, before calling @emph{any} FFTW routines, you should call the Chris@42: function: Chris@42: Chris@42: @example Chris@42: int fftw_init_threads(void); Chris@42: @end example Chris@42: @findex fftw_init_threads Chris@42: Chris@42: This function, which need only be called once, performs any one-time Chris@42: initialization required to use threads on your system. It returns zero Chris@42: if there was some error (which should not happen under normal Chris@42: circumstances) and a non-zero value otherwise. Chris@42: Chris@42: Third, before creating a plan that you want to parallelize, you should Chris@42: call: Chris@42: Chris@42: @example Chris@42: void fftw_plan_with_nthreads(int nthreads); Chris@42: @end example Chris@42: @findex fftw_plan_with_nthreads Chris@42: Chris@42: The @code{nthreads} argument indicates the number of threads you want Chris@42: FFTW to use (or actually, the maximum number). All plans subsequently Chris@42: created with any planner routine will use that many threads. You can Chris@42: call @code{fftw_plan_with_nthreads}, create some plans, call Chris@42: @code{fftw_plan_with_nthreads} again with a different argument, and Chris@42: create some more plans for a new number of threads. Plans already created Chris@42: before a call to @code{fftw_plan_with_nthreads} are unaffected. If you Chris@42: pass an @code{nthreads} argument of @code{1} (the default), threads are Chris@42: disabled for subsequent plans. Chris@42: Chris@42: @cindex OpenMP Chris@42: With OpenMP, to configure FFTW to use all of the currently running Chris@42: OpenMP threads (set by @code{omp_set_num_threads(nthreads)} or by the Chris@42: @code{OMP_NUM_THREADS} environment variable), you can do: Chris@42: @code{fftw_plan_with_nthreads(omp_get_max_threads())}. (The @samp{omp_} Chris@42: OpenMP functions are declared via @code{#include }.) Chris@42: Chris@42: @cindex thread safety Chris@42: Given a plan, you then execute it as usual with Chris@42: @code{fftw_execute(plan)}, and the execution will use the number of Chris@42: threads specified when the plan was created. When done, you destroy Chris@42: it as usual with @code{fftw_destroy_plan}. As described in Chris@42: @ref{Thread safety}, plan @emph{execution} is thread-safe, but plan Chris@42: creation and destruction are @emph{not}: you should create/destroy Chris@42: plans only from a single thread, but can safely execute multiple plans Chris@42: in parallel. Chris@42: Chris@42: There is one additional routine: if you want to get rid of all memory Chris@42: and other resources allocated internally by FFTW, you can call: Chris@42: Chris@42: @example Chris@42: void fftw_cleanup_threads(void); Chris@42: @end example Chris@42: @findex fftw_cleanup_threads Chris@42: Chris@42: which is much like the @code{fftw_cleanup()} function except that it Chris@42: also gets rid of threads-related data. You must @emph{not} execute any Chris@42: previously created plans after calling this function. Chris@42: Chris@42: We should also mention one other restriction: if you save wisdom from a Chris@42: program using the multi-threaded FFTW, that wisdom @emph{cannot be used} Chris@42: by a program using only the single-threaded FFTW (i.e. not calling Chris@42: @code{fftw_init_threads}). @xref{Words of Wisdom-Saving Plans}. Chris@42: Chris@42: @c ------------------------------------------------------------ Chris@42: @node How Many Threads to Use?, Thread safety, Usage of Multi-threaded FFTW, Multi-threaded FFTW Chris@42: @section How Many Threads to Use? Chris@42: Chris@42: @cindex number of threads Chris@42: There is a fair amount of overhead involved in synchronizing threads, Chris@42: so the optimal number of threads to use depends upon the size of the Chris@42: transform as well as on the number of processors you have. Chris@42: Chris@42: As a general rule, you don't want to use more threads than you have Chris@42: processors. (Using more threads will work, but there will be extra Chris@42: overhead with no benefit.) In fact, if the problem size is too small, Chris@42: you may want to use fewer threads than you have processors. Chris@42: Chris@42: You will have to experiment with your system to see what level of Chris@42: parallelization is best for your problem size. Typically, the problem Chris@42: will have to involve at least a few thousand data points before threads Chris@42: become beneficial. If you plan with @code{FFTW_PATIENT}, it will Chris@42: automatically disable threads for sizes that don't benefit from Chris@42: parallelization. Chris@42: @ctindex FFTW_PATIENT Chris@42: Chris@42: @c ------------------------------------------------------------ Chris@42: @node Thread safety, , How Many Threads to Use?, Multi-threaded FFTW Chris@42: @section Thread safety Chris@42: Chris@42: @cindex threads Chris@42: @cindex OpenMP Chris@42: @cindex thread safety Chris@42: Users writing multi-threaded programs (including OpenMP) must concern Chris@42: themselves with the @dfn{thread safety} of the libraries they Chris@42: use---that is, whether it is safe to call routines in parallel from Chris@42: multiple threads. FFTW can be used in such an environment, but some Chris@42: care must be taken because the planner routines share data Chris@42: (e.g. wisdom and trigonometric tables) between calls and plans. Chris@42: Chris@42: The upshot is that the only thread-safe (re-entrant) routine in FFTW is Chris@42: @code{fftw_execute} (and the new-array variants thereof). All other routines Chris@42: (e.g. the planner) should only be called from one thread at a time. So, Chris@42: for example, you can wrap a semaphore lock around any calls to the Chris@42: planner; even more simply, you can just create all of your plans from Chris@42: one thread. We do not think this should be an important restriction Chris@42: (FFTW is designed for the situation where the only performance-sensitive Chris@42: code is the actual execution of the transform), and the benefits of Chris@42: shared data between plans are great. Chris@42: Chris@42: Note also that, since the plan is not modified by @code{fftw_execute}, Chris@42: it is safe to execute the @emph{same plan} in parallel by multiple Chris@42: threads. However, since a given plan operates by default on a fixed Chris@42: array, you need to use one of the new-array execute functions (@pxref{New-array Execute Functions}) so that different threads compute the transform of different data. Chris@42: Chris@42: (Users should note that these comments only apply to programs using Chris@42: shared-memory threads or OpenMP. Parallelism using MPI or forked processes Chris@42: involves a separate address-space and global variables for each process, Chris@42: and is not susceptible to problems of this sort.) Chris@42: Chris@42: If you are configured FFTW with the @code{--enable-debug} or Chris@42: @code{--enable-debug-malloc} flags (@pxref{Installation on Unix}), Chris@42: then @code{fftw_execute} is not thread-safe. These flags are not Chris@42: documented because they are intended only for developing Chris@42: and debugging FFTW, but if you must use @code{--enable-debug} then you Chris@42: should also specifically pass @code{--disable-debug-malloc} for Chris@42: @code{fftw_execute} to be thread-safe. Chris@42: Chris@42: Starting from FFTW-3.3.5, FFTW supports a new API to make the Chris@42: planner thread-safe: Chris@42: @example Chris@42: void fftw_make_planner_thread_safe(void); Chris@42: @end example Chris@42: @findex fftw_make_planner_thread_safe Chris@42: Chris@42: This call installs a hook that wraps a lock around all planner calls. Chris@42: This API is meant for ``applications'' that use ``plugins'' in multiple Chris@42: threads, where each ``plugin'' calls single-threaded FFTW but is unaware Chris@42: of the other ``plugins'' doing the same thing at the same time. In this Chris@42: case, the ``application'' calls @code{fftw_make_planner_thread_safe()} Chris@42: at the beginning to protect ``plugins'' from each other.