Mercurial > hg > sv-dependency-builds

diff src/fftw-3.3.3/doc/html/Load-balancing.html @ 10:37bf6b4a2645

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add FFTW3
author Chris Cannam
date Wed, 20 Mar 2013 15:35:50 +0000
parents
children
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/fftw-3.3.3/doc/html/Load-balancing.html	Wed Mar 20 15:35:50 2013 +0000
@@ -0,0 +1,89 @@
+<html lang="en">
+<head>
+<title>Load balancing - FFTW 3.3.3</title>
+<meta http-equiv="Content-Type" content="text/html">
+<meta name="description" content="FFTW 3.3.3">
+<meta name="generator" content="makeinfo 4.13">
+<link title="Top" rel="start" href="index.html#Top">
+<link rel="up" href="MPI-Data-Distribution.html#MPI-Data-Distribution" title="MPI Data Distribution">
+<link rel="prev" href="Basic-and-advanced-distribution-interfaces.html#Basic-and-advanced-distribution-interfaces" title="Basic and advanced distribution interfaces">
+<link rel="next" href="Transposed-distributions.html#Transposed-distributions" title="Transposed distributions">
+<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
+<!--
+This manual is for FFTW
+(version 3.3.3, 25 November 2012).
+
+Copyright (C) 2003 Matteo Frigo.
+
+Copyright (C) 2003 Massachusetts Institute of Technology.
+
+     Permission is granted to make and distribute verbatim copies of
+     this manual provided the copyright notice and this permission
+     notice are preserved on all copies.
+
+     Permission is granted to copy and distribute modified versions of
+     this manual under the conditions for verbatim copying, provided
+     that the entire resulting derived work is distributed under the
+     terms of a permission notice identical to this one.
+
+     Permission is granted to copy and distribute translations of this
+     manual into another language, under the above conditions for
+     modified versions, except that this permission notice may be
+     stated in a translation approved by the Free Software Foundation.
+   -->
+<meta http-equiv="Content-Style-Type" content="text/css">
+<style type="text/css"><!--
+  pre.display { font-family:inherit }
+  pre.format  { font-family:inherit }
+  pre.smalldisplay { font-family:inherit; font-size:smaller }
+  pre.smallformat  { font-family:inherit; font-size:smaller }
+  pre.smallexample { font-size:smaller }
+  pre.smalllisp    { font-size:smaller }
+  span.sc    { font-variant:small-caps }
+  span.roman { font-family:serif; font-weight:normal; } 
+  span.sansserif { font-family:sans-serif; font-weight:normal; } 
+--></style>
+</head>
+<body>
+<div class="node">
+<a name="Load-balancing"></a>
+<p>
+Next:&nbsp;<a rel="next" accesskey="n" href="Transposed-distributions.html#Transposed-distributions">Transposed distributions</a>,
+Previous:&nbsp;<a rel="previous" accesskey="p" href="Basic-and-advanced-distribution-interfaces.html#Basic-and-advanced-distribution-interfaces">Basic and advanced distribution interfaces</a>,
+Up:&nbsp;<a rel="up" accesskey="u" href="MPI-Data-Distribution.html#MPI-Data-Distribution">MPI Data Distribution</a>
+<hr>
+</div>
+
+<h4 class="subsection">6.4.2 Load balancing</h4>
+
+<p><a name="index-load-balancing-378"></a>
+Ideally, when you parallelize a transform over some P
+processes, each process should end up with work that takes equal time. 
+Otherwise, all of the processes end up waiting on whichever process is
+slowest.  This goal is known as &ldquo;load balancing.&rdquo;  In this section,
+we describe the circumstances under which FFTW is able to load-balance
+well, and in particular how you should choose your transform size in
+order to load balance.
+
+   <p>Load balancing is especially difficult when you are parallelizing over
+heterogeneous machines; for example, if one of your processors is a
+old 486 and another is a Pentium IV, obviously you should give the
+Pentium more work to do than the 486 since the latter is much slower. 
+FFTW does not deal with this problem, however&mdash;it assumes that your
+processes run on hardware of comparable speed, and that the goal is
+therefore to divide the problem as equally as possible.
+
+   <p>For a multi-dimensional complex DFT, FFTW can divide the problem
+equally among the processes if: (i) the <em>first</em> dimension
+<code>n0</code> is divisible by P; and (ii), the <em>product</em> of
+the subsequent dimensions is divisible by P.  (For the advanced
+interface, where you can specify multiple simultaneous transforms via
+some &ldquo;vector&rdquo; length <code>howmany</code>, a factor of <code>howmany</code> is
+included in the product of the subsequent dimensions.)
+
+   <p>For a one-dimensional complex DFT, the length <code>N</code> of the data
+should be divisible by P <em>squared</em> to be able to divide
+the problem equally among the processes.
+
+   </body></html>
+