title: Nested parallelism in Python
body: <p>I am trying out multiprocessor programming with Python. Take a divide and conquer algorithm like <code>Fibonacci</code> for example. The program flow of execution would branch out like a tree and execute in parallel. In other words, we have an example of <a href="http://www.google.com/search?q=%22nested%20parallelism%22%20filetype:pdf&amp;oq=%22nested%20parallelism%22%20filetype:pdf" rel="noreferrer">nested parallelism</a>.</p>
  
  <p>From Java, I have used a threadpool pattern to manage resources, since the program could branch out very quickly and create too many short-lived threads. A single static (shared) threadpool can be instantiated via   <code>ExecutorService</code>. </p>
  
  <p>I would expect the same for <strong><a href="http://docs.python.org/2/library/multiprocessing.html" rel="noreferrer">Pool</a></strong>, but it appears that <a href="https://stackoverflow.com/a/1748335/266457">Pool object is not to be globally shared</a>. For example, sharing the Pool using <code>multiprocessing.Manager.Namespace()</code> will lead to the error.</p>
  
  <blockquote>
    <p>pool objects cannot be passed between processes or pickled</p>
  </blockquote>
  
  <p>I have a 2-part question: </p>
  
  <ol>
  <li>What am I missing here; why shouldn't a Pool be shared between processes? </li>
  <li>What is a <strong>pattern for implementing nested parallelism in Python?</strong>  If possible, maintaining a recursive structure, and not trading it for iteration.</li>
  </ol>
  
  <hr>
  
  <pre><code>from concurrent.futures import ThreadPoolExecutor
  
  def fibonacci(n):
      if n &lt; 2:
          return n
      a = pool.submit(fibonacci, n - 1)
      b = pool.submit(fibonacci, n - 2)
      return a.result() + b.result()
  
  def main():
      global pool
  
      N = int(10)
      with ThreadPoolExecutor(2**N) as pool:
          print(fibonacci(N))
  
  main()
  </code></pre>
  
  <hr>
  
  <p>Java</p>
  
  <pre><code>public class FibTask implements Callable&lt;Integer&gt; {
  
      public static ExecutorService pool = Executors.newCachedThreadPool();
      int arg;
  
      public FibTask(int n) {
          this.arg= n;
      }
  
      @Override
      public Integer call() throws Exception {
          if (this.arg &gt; 2) { 
              Future&lt;Integer&gt; left = pool.submit(new FibTask(arg - 1));
              Future&lt;Integer&gt; right = pool.submit(new FibTask(arg - 2));
              return left.get() + right.get();
          } else {
              return 1;
          }
  
      } 
  
    public static void main(String[] args) throws Exception {
        Integer n = 14;
        Callable&lt;Integer&gt; task = new FibTask(n);
        Future&lt;Integer&gt; result =FibTask.pool.submit(task); 
        System.out.println(Integer.toString(result.get()));
        FibTask.pool.shutdown();            
    }    
  
  }
  </code></pre>
  
  <p>I'm not sure if it matters here, but I am ignoring the difference between "process" and "thread"; to me they both mean "virtualized processor". My understanding is, the purpose of a Pool is for sharing of a "pool" or resources. Running tasks can make a request to the Pool. As parallel tasks complete on other threads, those threads can be reclaimed and assigned to new tasks. It doesn't make sense to me to disallow sharing of the pool, so that each thread must instantiate its own new pool, since that would seem to defeat the purpose of a thread pool. </p>