cannam@95: @node Other Important Topics, FFTW Reference, Tutorial, Top cannam@95: @chapter Other Important Topics cannam@95: @menu cannam@95: * SIMD alignment and fftw_malloc:: cannam@95: * Multi-dimensional Array Format:: cannam@95: * Words of Wisdom-Saving Plans:: cannam@95: * Caveats in Using Wisdom:: cannam@95: @end menu cannam@95: cannam@95: @c ------------------------------------------------------------ cannam@95: @node SIMD alignment and fftw_malloc, Multi-dimensional Array Format, Other Important Topics, Other Important Topics cannam@95: @section SIMD alignment and fftw_malloc cannam@95: cannam@95: SIMD, which stands for ``Single Instruction Multiple Data,'' is a set of cannam@95: special operations supported by some processors to perform a single cannam@95: operation on several numbers (usually 2 or 4) simultaneously. SIMD cannam@95: floating-point instructions are available on several popular CPUs: cannam@95: SSE/SSE2/AVX on recent x86/x86-64 processors, AltiVec (single precision) cannam@95: on some PowerPCs (Apple G4 and higher), NEON on some ARM models, and MIPS Paired Single cannam@95: (currently only in FFTW 3.2.x). FFTW can be compiled to support the cannam@95: SIMD instructions on any of these systems. cannam@95: @cindex SIMD cannam@95: @cindex SSE cannam@95: @cindex SSE2 cannam@95: @cindex AVX cannam@95: @cindex AltiVec cannam@95: @cindex MIPS PS cannam@95: @cindex precision cannam@95: cannam@95: cannam@95: A program linking to an FFTW library compiled with SIMD support can cannam@95: obtain a nonnegligible speedup for most complex and r2c/c2r cannam@95: transforms. In order to obtain this speedup, however, the arrays of cannam@95: complex (or real) data passed to FFTW must be specially aligned in cannam@95: memory (typically 16-byte aligned), and often this alignment is more cannam@95: stringent than that provided by the usual @code{malloc} (etc.) cannam@95: allocation routines. cannam@95: cannam@95: @cindex portability cannam@95: In order to guarantee proper alignment for SIMD, therefore, in case cannam@95: your program is ever linked against a SIMD-using FFTW, we recommend cannam@95: allocating your transform data with @code{fftw_malloc} and cannam@95: de-allocating it with @code{fftw_free}. cannam@95: @findex fftw_malloc cannam@95: @findex fftw_free cannam@95: These have exactly the same interface and behavior as cannam@95: @code{malloc}/@code{free}, except that for a SIMD FFTW they ensure cannam@95: that the returned pointer has the necessary alignment (by calling cannam@95: @code{memalign} or its equivalent on your OS). cannam@95: cannam@95: You are not @emph{required} to use @code{fftw_malloc}. You can cannam@95: allocate your data in any way that you like, from @code{malloc} to cannam@95: @code{new} (in C++) to a fixed-size array declaration. If the array cannam@95: happens not to be properly aligned, FFTW will not use the SIMD cannam@95: extensions. cannam@95: @cindex C++ cannam@95: cannam@95: @findex fftw_alloc_real cannam@95: @findex fftw_alloc_complex cannam@95: Since @code{fftw_malloc} only ever needs to be used for real and cannam@95: complex arrays, we provide two convenient wrapper routines cannam@95: @code{fftw_alloc_real(N)} and @code{fftw_alloc_complex(N)} that are cannam@95: equivalent to @code{(double*)fftw_malloc(sizeof(double) * N)} and cannam@95: @code{(fftw_complex*)fftw_malloc(sizeof(fftw_complex) * N)}, cannam@95: respectively (or their equivalents in other precisions). cannam@95: cannam@95: @c ------------------------------------------------------------ cannam@95: @node Multi-dimensional Array Format, Words of Wisdom-Saving Plans, SIMD alignment and fftw_malloc, Other Important Topics cannam@95: @section Multi-dimensional Array Format cannam@95: cannam@95: This section describes the format in which multi-dimensional arrays cannam@95: are stored in FFTW. We felt that a detailed discussion of this topic cannam@95: was necessary. Since several different formats are common, this topic cannam@95: is often a source of confusion. cannam@95: cannam@95: @menu cannam@95: * Row-major Format:: cannam@95: * Column-major Format:: cannam@95: * Fixed-size Arrays in C:: cannam@95: * Dynamic Arrays in C:: cannam@95: * Dynamic Arrays in C-The Wrong Way:: cannam@95: @end menu cannam@95: cannam@95: @c =========> cannam@95: @node Row-major Format, Column-major Format, Multi-dimensional Array Format, Multi-dimensional Array Format cannam@95: @subsection Row-major Format cannam@95: @cindex row-major cannam@95: cannam@95: The multi-dimensional arrays passed to @code{fftw_plan_dft} etcetera cannam@95: are expected to be stored as a single contiguous block in cannam@95: @dfn{row-major} order (sometimes called ``C order''). Basically, this cannam@95: means that as you step through adjacent memory locations, the first cannam@95: dimension's index varies most slowly and the last dimension's index cannam@95: varies most quickly. cannam@95: cannam@95: To be more explicit, let us consider an array of rank @math{d} whose cannam@95: dimensions are @ndims{}. Now, we specify a location in the array by a cannam@95: sequence of @math{d} (zero-based) indices, one for each dimension: cannam@95: @tex cannam@95: $(i_0, i_1, i_2, \ldots, i_{d-1})$. cannam@95: @end tex cannam@95: @ifinfo cannam@95: (i[0], i[1], ..., i[d-1]). cannam@95: @end ifinfo cannam@95: @html cannam@95: (i0, i1, i2,..., id-1). cannam@95: @end html cannam@95: If the array is stored in row-major cannam@95: order, then this element is located at the position cannam@95: @tex cannam@95: $i_{d-1} + n_{d-1} (i_{d-2} + n_{d-2} (\ldots + n_1 i_0))$. cannam@95: @end tex cannam@95: @ifinfo cannam@95: i[d-1] + n[d-1] * (i[d-2] + n[d-2] * (... + n[1] * i[0])). cannam@95: @end ifinfo cannam@95: @html cannam@95: id-1 + nd-1 * (id-2 + nd-2 * (... + n1 * i0)). cannam@95: @end html cannam@95: cannam@95: Note that, for the ordinary complex DFT, each element of the array cannam@95: must be of type @code{fftw_complex}; i.e. a (real, imaginary) pair of cannam@95: (double-precision) numbers. cannam@95: cannam@95: In the advanced FFTW interface, the physical dimensions @math{n} from cannam@95: which the indices are computed can be different from (larger than) cannam@95: the logical dimensions of the transform to be computed, in order to cannam@95: transform a subset of a larger array. cannam@95: @cindex advanced interface cannam@95: Note also that, in the advanced interface, the expression above is cannam@95: multiplied by a @dfn{stride} to get the actual array index---this is cannam@95: useful in situations where each element of the multi-dimensional array cannam@95: is actually a data structure (or another array), and you just want to cannam@95: transform a single field. In the basic interface, however, the stride cannam@95: is 1. cannam@95: @cindex stride cannam@95: cannam@95: @c =========> cannam@95: @node Column-major Format, Fixed-size Arrays in C, Row-major Format, Multi-dimensional Array Format cannam@95: @subsection Column-major Format cannam@95: @cindex column-major cannam@95: cannam@95: Readers from the Fortran world are used to arrays stored in cannam@95: @dfn{column-major} order (sometimes called ``Fortran order''). This is cannam@95: essentially the exact opposite of row-major order in that, here, the cannam@95: @emph{first} dimension's index varies most quickly. cannam@95: cannam@95: If you have an array stored in column-major order and wish to cannam@95: transform it using FFTW, it is quite easy to do. When creating the cannam@95: plan, simply pass the dimensions of the array to the planner in cannam@95: @emph{reverse order}. For example, if your array is a rank three cannam@95: @code{N x M x L} matrix in column-major order, you should pass the cannam@95: dimensions of the array as if it were an @code{L x M x N} matrix cannam@95: (which it is, from the perspective of FFTW). This is done for you cannam@95: @emph{automatically} by the FFTW legacy-Fortran interface cannam@95: (@pxref{Calling FFTW from Legacy Fortran}), but you must do it cannam@95: manually with the modern Fortran interface (@pxref{Reversing array cannam@95: dimensions}). cannam@95: @cindex Fortran interface cannam@95: cannam@95: @c =========> cannam@95: @node Fixed-size Arrays in C, Dynamic Arrays in C, Column-major Format, Multi-dimensional Array Format cannam@95: @subsection Fixed-size Arrays in C cannam@95: @cindex C multi-dimensional arrays cannam@95: cannam@95: A multi-dimensional array whose size is declared at compile time in C cannam@95: is @emph{already} in row-major order. You don't have to do anything cannam@95: special to transform it. For example: cannam@95: cannam@95: @example cannam@95: @{ cannam@95: fftw_complex data[N0][N1][N2]; cannam@95: fftw_plan plan; cannam@95: ... cannam@95: plan = fftw_plan_dft_3d(N0, N1, N2, &data[0][0][0], &data[0][0][0], cannam@95: FFTW_FORWARD, FFTW_ESTIMATE); cannam@95: ... cannam@95: @} cannam@95: @end example cannam@95: cannam@95: This will plan a 3d in-place transform of size @code{N0 x N1 x N2}. cannam@95: Notice how we took the address of the zero-th element to pass to the cannam@95: planner (we could also have used a typecast). cannam@95: cannam@95: However, we tend to @emph{discourage} users from declaring their cannam@95: arrays in this way, for two reasons. First, this allocates the array cannam@95: on the stack (``automatic'' storage), which has a very limited size on cannam@95: most operating systems (declaring an array with more than a few cannam@95: thousand elements will often cause a crash). (You can get around this cannam@95: limitation on many systems by declaring the array as cannam@95: @code{static} and/or global, but that has its own drawbacks.) cannam@95: Second, it may not optimally align the array for use with a SIMD cannam@95: FFTW (@pxref{SIMD alignment and fftw_malloc}). Instead, we recommend cannam@95: using @code{fftw_malloc}, as described below. cannam@95: cannam@95: @c =========> cannam@95: @node Dynamic Arrays in C, Dynamic Arrays in C-The Wrong Way, Fixed-size Arrays in C, Multi-dimensional Array Format cannam@95: @subsection Dynamic Arrays in C cannam@95: cannam@95: We recommend allocating most arrays dynamically, with cannam@95: @code{fftw_malloc}. This isn't too hard to do, although it is not as cannam@95: straightforward for multi-dimensional arrays as it is for cannam@95: one-dimensional arrays. cannam@95: cannam@95: Creating the array is simple: using a dynamic-allocation routine like cannam@95: @code{fftw_malloc}, allocate an array big enough to store N cannam@95: @code{fftw_complex} values (for a complex DFT), where N is the product cannam@95: of the sizes of the array dimensions (i.e. the total number of complex cannam@95: values in the array). For example, here is code to allocate a cannam@95: @threedims{5,12,27} rank-3 array: cannam@95: @findex fftw_malloc cannam@95: cannam@95: @example cannam@95: fftw_complex *an_array; cannam@95: an_array = (fftw_complex*) fftw_malloc(5*12*27 * sizeof(fftw_complex)); cannam@95: @end example cannam@95: cannam@95: Accessing the array elements, however, is more tricky---you can't cannam@95: simply use multiple applications of the @samp{[]} operator like you cannam@95: could for fixed-size arrays. Instead, you have to explicitly compute cannam@95: the offset into the array using the formula given earlier for cannam@95: row-major arrays. For example, to reference the @math{(i,j,k)}-th cannam@95: element of the array allocated above, you would use the expression cannam@95: @code{an_array[k + 27 * (j + 12 * i)]}. cannam@95: cannam@95: This pain can be alleviated somewhat by defining appropriate macros, cannam@95: or, in C++, creating a class and overloading the @samp{()} operator. cannam@95: The recent C99 standard provides a way to reinterpret the dynamic cannam@95: array as a ``variable-length'' multi-dimensional array amenable to cannam@95: @samp{[]}, but this feature is not yet widely supported by compilers. cannam@95: @cindex C99 cannam@95: @cindex C++ cannam@95: cannam@95: @c =========> cannam@95: @node Dynamic Arrays in C-The Wrong Way, , Dynamic Arrays in C, Multi-dimensional Array Format cannam@95: @subsection Dynamic Arrays in C---The Wrong Way cannam@95: cannam@95: A different method for allocating multi-dimensional arrays in C is cannam@95: often suggested that is incompatible with FFTW: @emph{using it will cannam@95: cause FFTW to die a painful death}. We discuss the technique here, cannam@95: however, because it is so commonly known and used. This method is to cannam@95: create arrays of pointers of arrays of pointers of @dots{}etcetera. cannam@95: For example, the analogue in this method to the example above is: cannam@95: cannam@95: @example cannam@95: int i,j; cannam@95: fftw_complex ***a_bad_array; /* @r{another way to make a 5x12x27 array} */ cannam@95: cannam@95: a_bad_array = (fftw_complex ***) malloc(5 * sizeof(fftw_complex **)); cannam@95: for (i = 0; i < 5; ++i) @{ cannam@95: a_bad_array[i] = cannam@95: (fftw_complex **) malloc(12 * sizeof(fftw_complex *)); cannam@95: for (j = 0; j < 12; ++j) cannam@95: a_bad_array[i][j] = cannam@95: (fftw_complex *) malloc(27 * sizeof(fftw_complex)); cannam@95: @} cannam@95: @end example cannam@95: cannam@95: As you can see, this sort of array is inconvenient to allocate (and cannam@95: deallocate). On the other hand, it has the advantage that the cannam@95: @math{(i,j,k)}-th element can be referenced simply by cannam@95: @code{a_bad_array[i][j][k]}. cannam@95: cannam@95: If you like this technique and want to maximize convenience in accessing cannam@95: the array, but still want to pass the array to FFTW, you can use a cannam@95: hybrid method. Allocate the array as one contiguous block, but also cannam@95: declare an array of arrays of pointers that point to appropriate places cannam@95: in the block. That sort of trick is beyond the scope of this cannam@95: documentation; for more information on multi-dimensional arrays in C, cannam@95: see the @code{comp.lang.c} cannam@95: @uref{http://c-faq.com/aryptr/dynmuldimary.html, FAQ}. cannam@95: cannam@95: @c ------------------------------------------------------------ cannam@95: @node Words of Wisdom-Saving Plans, Caveats in Using Wisdom, Multi-dimensional Array Format, Other Important Topics cannam@95: @section Words of Wisdom---Saving Plans cannam@95: @cindex wisdom cannam@95: @cindex saving plans to disk cannam@95: cannam@95: FFTW implements a method for saving plans to disk and restoring them. cannam@95: In fact, what FFTW does is more general than just saving and loading cannam@95: plans. The mechanism is called @dfn{wisdom}. Here, we describe cannam@95: this feature at a high level. @xref{FFTW Reference}, for a less casual cannam@95: but more complete discussion of how to use wisdom in FFTW. cannam@95: cannam@95: Plans created with the @code{FFTW_MEASURE}, @code{FFTW_PATIENT}, or cannam@95: @code{FFTW_EXHAUSTIVE} options produce near-optimal FFT performance, cannam@95: but may require a long time to compute because FFTW must measure the cannam@95: runtime of many possible plans and select the best one. This setup is cannam@95: designed for the situations where so many transforms of the same size cannam@95: must be computed that the start-up time is irrelevant. For short cannam@95: initialization times, but slower transforms, we have provided cannam@95: @code{FFTW_ESTIMATE}. The @code{wisdom} mechanism is a way to get the cannam@95: best of both worlds: you compute a good plan once, save it to cannam@95: disk, and later reload it as many times as necessary. The wisdom cannam@95: mechanism can actually save and reload many plans at once, not just cannam@95: one. cannam@95: @ctindex FFTW_MEASURE cannam@95: @ctindex FFTW_PATIENT cannam@95: @ctindex FFTW_EXHAUSTIVE cannam@95: @ctindex FFTW_ESTIMATE cannam@95: cannam@95: cannam@95: Whenever you create a plan, the FFTW planner accumulates wisdom, which cannam@95: is information sufficient to reconstruct the plan. After planning, cannam@95: you can save this information to disk by means of the function: cannam@95: @example cannam@95: int fftw_export_wisdom_to_filename(const char *filename); cannam@95: @end example cannam@95: @findex fftw_export_wisdom_to_filename cannam@95: (This function returns non-zero on success.) cannam@95: cannam@95: The next time you run the program, you can restore the wisdom with cannam@95: @code{fftw_import_wisdom_from_filename} (which also returns non-zero on success), cannam@95: and then recreate the plan using the same flags as before. cannam@95: @example cannam@95: int fftw_import_wisdom_from_filename(const char *filename); cannam@95: @end example cannam@95: @findex fftw_import_wisdom_from_filename cannam@95: cannam@95: Wisdom is automatically used for any size to which it is applicable, as cannam@95: long as the planner flags are not more ``patient'' than those with which cannam@95: the wisdom was created. For example, wisdom created with cannam@95: @code{FFTW_MEASURE} can be used if you later plan with cannam@95: @code{FFTW_ESTIMATE} or @code{FFTW_MEASURE}, but not with cannam@95: @code{FFTW_PATIENT}. cannam@95: cannam@95: The @code{wisdom} is cumulative, and is stored in a global, private cannam@95: data structure managed internally by FFTW. The storage space required cannam@95: is minimal, proportional to the logarithm of the sizes the wisdom was cannam@95: generated from. If memory usage is a concern, however, the wisdom can cannam@95: be forgotten and its associated memory freed by calling: cannam@95: @example cannam@95: void fftw_forget_wisdom(void); cannam@95: @end example cannam@95: @findex fftw_forget_wisdom cannam@95: cannam@95: Wisdom can be exported to a file, a string, or any other medium. cannam@95: For details, see @ref{Wisdom}. cannam@95: cannam@95: @node Caveats in Using Wisdom, , Words of Wisdom-Saving Plans, Other Important Topics cannam@95: @section Caveats in Using Wisdom cannam@95: @cindex wisdom, problems with cannam@95: cannam@95: @quotation cannam@95: @html cannam@95: cannam@95: @end html cannam@95: For in much wisdom is much grief, and he that increaseth knowledge cannam@95: increaseth sorrow. cannam@95: @html cannam@95: cannam@95: @end html cannam@95: [Ecclesiastes 1:18] cannam@95: @cindex Ecclesiastes cannam@95: @end quotation cannam@95: @iftex cannam@95: @medskip cannam@95: @end iftex cannam@95: cannam@95: @cindex portability cannam@95: There are pitfalls to using wisdom, in that it can negate FFTW's cannam@95: ability to adapt to changing hardware and other conditions. For cannam@95: example, it would be perfectly possible to export wisdom from a cannam@95: program running on one processor and import it into a program running cannam@95: on another processor. Doing so, however, would mean that the second cannam@95: program would use plans optimized for the first processor, instead of cannam@95: the one it is running on. cannam@95: cannam@95: It should be safe to reuse wisdom as long as the hardware and program cannam@95: binaries remain unchanged. (Actually, the optimal plan may change even cannam@95: between runs of the same binary on identical hardware, due to cannam@95: differences in the virtual memory environment, etcetera. Users cannam@95: seriously interested in performance should worry about this problem, cannam@95: too.) It is likely that, if the same wisdom is used for two cannam@95: different program binaries, even running on the same machine, the cannam@95: plans may be sub-optimal because of differing code alignments. It is cannam@95: therefore wise to recreate wisdom every time an application is cannam@95: recompiled. The more the underlying hardware and software changes cannam@95: between the creation of wisdom and its use, the greater grows cannam@95: the risk of sub-optimal plans. cannam@95: cannam@95: Nevertheless, if the choice is between using @code{FFTW_ESTIMATE} or cannam@95: using possibly-suboptimal wisdom (created on the same machine, but for a cannam@95: different binary), the wisdom is likely to be better. For this reason, cannam@95: we provide a function to import wisdom from a standard system-wide cannam@95: location (@code{/etc/fftw/wisdom} on Unix): cannam@95: @cindex wisdom, system-wide cannam@95: cannam@95: @example cannam@95: int fftw_import_system_wisdom(void); cannam@95: @end example cannam@95: @findex fftw_import_system_wisdom cannam@95: cannam@95: FFTW also provides a standalone program, @code{fftw-wisdom} (described cannam@95: by its own @code{man} page on Unix) with which users can create wisdom, cannam@95: e.g. for a canonical set of sizes to store in the system wisdom file. cannam@95: @xref{Wisdom Utilities}. cannam@95: @cindex fftw-wisdom utility cannam@95: