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