Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.5/doc/html/MPI-Data-Distribution.html @ 42:2cd0e3b3e1fd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Current fftw source
author Chris Cannam
date Tue, 18 Oct 2016 13:40:26 +0100
parents
children
comparison
equal deleted inserted replaced
41:481f5f8c5634 42:2cd0e3b3e1fd
1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2 <html>
3 <!-- This manual is for FFTW
4 (version 3.3.5, 30 July 2016).
5
6 Copyright (C) 2003 Matteo Frigo.
7
8 Copyright (C) 2003 Massachusetts Institute of Technology.
9
10 Permission is granted to make and distribute verbatim copies of this
11 manual provided the copyright notice and this permission notice are
12 preserved on all copies.
13
14 Permission is granted to copy and distribute modified versions of this
15 manual under the conditions for verbatim copying, provided that the
16 entire resulting derived work is distributed under the terms of a
17 permission notice identical to this one.
18
19 Permission is granted to copy and distribute translations of this manual
20 into another language, under the above conditions for modified versions,
21 except that this permission notice may be stated in a translation
22 approved by the Free Software Foundation. -->
23 <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
24 <head>
25 <title>FFTW 3.3.5: MPI Data Distribution</title>
26
27 <meta name="description" content="FFTW 3.3.5: MPI Data Distribution">
28 <meta name="keywords" content="FFTW 3.3.5: MPI Data Distribution">
29 <meta name="resource-type" content="document">
30 <meta name="distribution" content="global">
31 <meta name="Generator" content="makeinfo">
32 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
33 <link href="index.html#Top" rel="start" title="Top">
34 <link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
35 <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
36 <link href="Distributed_002dmemory-FFTW-with-MPI.html#Distributed_002dmemory-FFTW-with-MPI" rel="up" title="Distributed-memory FFTW with MPI">
37 <link href="Basic-and-advanced-distribution-interfaces.html#Basic-and-advanced-distribution-interfaces" rel="next" title="Basic and advanced distribution interfaces">
38 <link href="2d-MPI-example.html#g_t2d-MPI-example" rel="prev" title="2d MPI example">
39 <style type="text/css">
40 <!--
41 a.summary-letter {text-decoration: none}
42 blockquote.smallquotation {font-size: smaller}
43 div.display {margin-left: 3.2em}
44 div.example {margin-left: 3.2em}
45 div.indentedblock {margin-left: 3.2em}
46 div.lisp {margin-left: 3.2em}
47 div.smalldisplay {margin-left: 3.2em}
48 div.smallexample {margin-left: 3.2em}
49 div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
50 div.smalllisp {margin-left: 3.2em}
51 kbd {font-style:oblique}
52 pre.display {font-family: inherit}
53 pre.format {font-family: inherit}
54 pre.menu-comment {font-family: serif}
55 pre.menu-preformatted {font-family: serif}
56 pre.smalldisplay {font-family: inherit; font-size: smaller}
57 pre.smallexample {font-size: smaller}
58 pre.smallformat {font-family: inherit; font-size: smaller}
59 pre.smalllisp {font-size: smaller}
60 span.nocodebreak {white-space:nowrap}
61 span.nolinebreak {white-space:nowrap}
62 span.roman {font-family:serif; font-weight:normal}
63 span.sansserif {font-family:sans-serif; font-weight:normal}
64 ul.no-bullet {list-style: none}
65 -->
66 </style>
67
68
69 </head>
70
71 <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
72 <a name="MPI-Data-Distribution"></a>
73 <div class="header">
74 <p>
75 Next: <a href="Multi_002ddimensional-MPI-DFTs-of-Real-Data.html#Multi_002ddimensional-MPI-DFTs-of-Real-Data" accesskey="n" rel="next">Multi-dimensional MPI DFTs of Real Data</a>, Previous: <a href="2d-MPI-example.html#g_t2d-MPI-example" accesskey="p" rel="prev">2d MPI example</a>, Up: <a href="Distributed_002dmemory-FFTW-with-MPI.html#Distributed_002dmemory-FFTW-with-MPI" accesskey="u" rel="up">Distributed-memory FFTW with MPI</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
76 </div>
77 <hr>
78 <a name="MPI-Data-Distribution-1"></a>
79 <h3 class="section">6.4 MPI Data Distribution</h3>
80 <a name="index-data-distribution-2"></a>
81
82 <p>The most important concept to understand in using FFTW&rsquo;s MPI interface
83 is the data distribution. With a serial or multithreaded FFT, all of
84 the inputs and outputs are stored as a single contiguous chunk of
85 memory. With a distributed-memory FFT, the inputs and outputs are
86 broken into disjoint blocks, one per process.
87 </p>
88 <p>In particular, FFTW uses a <em>1d block distribution</em> of the data,
89 distributed along the <em>first dimension</em>. For example, if you
90 want to perform a 100&nbsp;&times;&nbsp;200 complex DFT, distributed over 4
91 processes, each process will get a 25&nbsp;&times;&nbsp;200 slice of the data.
92 That is, process 0 will get rows 0 through 24, process 1 will get rows
93 25 through 49, process 2 will get rows 50 through 74, and process 3
94 will get rows 75 through 99. If you take the same array but
95 distribute it over 3 processes, then it is not evenly divisible so the
96 different processes will have unequal chunks. FFTW&rsquo;s default choice
97 in this case is to assign 34 rows to processes 0 and 1, and 32 rows to
98 process 2.
99 <a name="index-block-distribution"></a>
100 </p>
101
102 <p>FFTW provides several &lsquo;<samp>fftw_mpi_local_size</samp>&rsquo; routines that you can
103 call to find out what portion of an array is stored on the current
104 process. In most cases, you should use the default block sizes picked
105 by FFTW, but it is also possible to specify your own block size. For
106 example, with a 100&nbsp;&times;&nbsp;200 array on three processes, you can
107 tell FFTW to use a block size of 40, which would assign 40 rows to
108 processes 0 and 1, and 20 rows to process 2. FFTW&rsquo;s default is to
109 divide the data equally among the processes if possible, and as best
110 it can otherwise. The rows are always assigned in &ldquo;rank order,&rdquo;
111 i.e. process 0 gets the first block of rows, then process 1, and so
112 on. (You can change this by using <code>MPI_Comm_split</code> to create a
113 new communicator with re-ordered processes.) However, you should
114 always call the &lsquo;<samp>fftw_mpi_local_size</samp>&rsquo; routines, if possible,
115 rather than trying to predict FFTW&rsquo;s distribution choices.
116 </p>
117 <p>In particular, it is critical that you allocate the storage size that
118 is returned by &lsquo;<samp>fftw_mpi_local_size</samp>&rsquo;, which is <em>not</em>
119 necessarily the size of the local slice of the array. The reason is
120 that intermediate steps of FFTW&rsquo;s algorithms involve transposing the
121 array and redistributing the data, so at these intermediate steps FFTW
122 may require more local storage space (albeit always proportional to
123 the total size divided by the number of processes). The
124 &lsquo;<samp>fftw_mpi_local_size</samp>&rsquo; functions know how much storage is required
125 for these intermediate steps and tell you the correct amount to
126 allocate.
127 </p>
128 <table class="menu" border="0" cellspacing="0">
129 <tr><td align="left" valign="top">&bull; <a href="Basic-and-advanced-distribution-interfaces.html#Basic-and-advanced-distribution-interfaces" accesskey="1">Basic and advanced distribution interfaces</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
130 </td></tr>
131 <tr><td align="left" valign="top">&bull; <a href="Load-balancing.html#Load-balancing" accesskey="2">Load balancing</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
132 </td></tr>
133 <tr><td align="left" valign="top">&bull; <a href="Transposed-distributions.html#Transposed-distributions" accesskey="3">Transposed distributions</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
134 </td></tr>
135 <tr><td align="left" valign="top">&bull; <a href="One_002ddimensional-distributions.html#One_002ddimensional-distributions" accesskey="4">One-dimensional distributions</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
136 </td></tr>
137 </table>
138
139 <hr>
140 <div class="header">
141 <p>
142 Next: <a href="Multi_002ddimensional-MPI-DFTs-of-Real-Data.html#Multi_002ddimensional-MPI-DFTs-of-Real-Data" accesskey="n" rel="next">Multi-dimensional MPI DFTs of Real Data</a>, Previous: <a href="2d-MPI-example.html#g_t2d-MPI-example" accesskey="p" rel="prev">2d MPI example</a>, Up: <a href="Distributed_002dmemory-FFTW-with-MPI.html#Distributed_002dmemory-FFTW-with-MPI" accesskey="u" rel="up">Distributed-memory FFTW with MPI</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
143 </div>
144
145
146
147 </body>
148 </html>