Databases
StackOverflow2013
Postsdbo
POSolving embarassingly parallel problems using Python multiprocessing
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSolving embarassingly parallel problems using Python multiprocessing
    primarykey
    data
    text
    <p>How does one use <a href="http://docs.python.org/library/multiprocessing.html" rel="noreferrer">multiprocessing</a> to tackle <a href="http://en.wikipedia.org/wiki/Embarrassingly_parallel" rel="noreferrer">embarrassingly parallel problems</a>?</p> <p>Embarassingly parallel problems typically consist of three basic parts:</p> <ol> <li><strong>Read</strong> input data (from a file, database, tcp connection, etc.).</li> <li><strong>Run</strong> calculations on the input data, where each calculation is <em>independent of any other calculation</em>.</li> <li><strong>Write</strong> results of calculations (to a file, database, tcp connection, etc.).</li> </ol> <p>We can parallelize the program in two dimensions:</p> <ul> <li>Part 2 can run on multiple cores, since each calculation is independent; order of processing doesn't matter.</li> <li>Each part can run independently. Part 1 can place data on an input queue, part 2 can pull data off the input queue and put results onto an output queue, and part 3 can pull results off the output queue and write them out.</li> </ul> <p>This seems a most basic pattern in concurrent programming, but I am still lost in trying to solve it, so <strong>let's write a canonical example to illustrate how this is done using multiprocessing</strong>.</p> <p>Here is the example problem: Given a <a href="http://en.wikipedia.org/wiki/Comma-separated_values" rel="noreferrer">CSV file</a> with rows of integers as input, compute their sums. Separate the problem into three parts, which can all run in parallel:</p> <ol> <li>Process the input file into raw data (lists/iterables of integers)</li> <li>Calculate the sums of the data, in parallel</li> <li>Output the sums</li> </ol> <p>Below is traditional, single-process bound Python program which solves these three tasks:</p> <pre><code>#!/usr/bin/env python # -*- coding: UTF-8 -*- # basicsums.py """A program that reads integer values from a CSV file and writes out their sums to another CSV file. """ import csv import optparse import sys def make_cli_parser(): """Make the command line interface parser.""" usage = "\n\n".join(["python %prog INPUT_CSV OUTPUT_CSV", __doc__, """ ARGUMENTS: INPUT_CSV: an input CSV file with rows of numbers OUTPUT_CSV: an output file that will contain the sums\ """]) cli_parser = optparse.OptionParser(usage) return cli_parser def parse_input_csv(csvfile): """Parses the input CSV and yields tuples with the index of the row as the first element, and the integers of the row as the second element. The index is zero-index based. :Parameters: - `csvfile`: a `csv.reader` instance """ for i, row in enumerate(csvfile): row = [int(entry) for entry in row] yield i, row def sum_rows(rows): """Yields a tuple with the index of each input list of integers as the first element, and the sum of the list of integers as the second element. The index is zero-index based. :Parameters: - `rows`: an iterable of tuples, with the index of the original row as the first element, and a list of integers as the second element """ for i, row in rows: yield i, sum(row) def write_results(csvfile, results): """Writes a series of results to an outfile, where the first column is the index of the original row of data, and the second column is the result of the calculation. The index is zero-index based. :Parameters: - `csvfile`: a `csv.writer` instance to which to write results - `results`: an iterable of tuples, with the index (zero-based) of the original row as the first element, and the calculated result from that row as the second element """ for result_row in results: csvfile.writerow(result_row) def main(argv): cli_parser = make_cli_parser() opts, args = cli_parser.parse_args(argv) if len(args) != 2: cli_parser.error("Please provide an input file and output file.") infile = open(args[0]) in_csvfile = csv.reader(infile) outfile = open(args[1], 'w') out_csvfile = csv.writer(outfile) # gets an iterable of rows that's not yet evaluated input_rows = parse_input_csv(in_csvfile) # sends the rows iterable to sum_rows() for results iterable, but # still not evaluated result_rows = sum_rows(input_rows) # finally evaluation takes place as a chain in write_results() write_results(out_csvfile, result_rows) infile.close() outfile.close() if __name__ == '__main__': main(sys.argv[1:]) </code></pre> <p>Let's take this program and rewrite it to use multiprocessing to parallelize the three parts outlined above. Below is a skeleton of this new, parallelized program, that needs to be fleshed out to address the parts in the comments:</p> <pre><code>#!/usr/bin/env python # -*- coding: UTF-8 -*- # multiproc_sums.py """A program that reads integer values from a CSV file and writes out their sums to another CSV file, using multiple processes if desired. """ import csv import multiprocessing import optparse import sys NUM_PROCS = multiprocessing.cpu_count() def make_cli_parser(): """Make the command line interface parser.""" usage = "\n\n".join(["python %prog INPUT_CSV OUTPUT_CSV", __doc__, """ ARGUMENTS: INPUT_CSV: an input CSV file with rows of numbers OUTPUT_CSV: an output file that will contain the sums\ """]) cli_parser = optparse.OptionParser(usage) cli_parser.add_option('-n', '--numprocs', type='int', default=NUM_PROCS, help="Number of processes to launch [DEFAULT: %default]") return cli_parser def main(argv): cli_parser = make_cli_parser() opts, args = cli_parser.parse_args(argv) if len(args) != 2: cli_parser.error("Please provide an input file and output file.") infile = open(args[0]) in_csvfile = csv.reader(infile) outfile = open(args[1], 'w') out_csvfile = csv.writer(outfile) # Parse the input file and add the parsed data to a queue for # processing, possibly chunking to decrease communication between # processes. # Process the parsed data as soon as any (chunks) appear on the # queue, using as many processes as allotted by the user # (opts.numprocs); place results on a queue for output. # # Terminate processes when the parser stops putting data in the # input queue. # Write the results to disk as soon as they appear on the output # queue. # Ensure all child processes have terminated. # Clean up files. infile.close() outfile.close() if __name__ == '__main__': main(sys.argv[1:]) </code></pre> <p>These pieces of code, as well as <a href="http://github.com/gotgenes/multiprocessing_examples/blob/master/generate_random_ints.py" rel="noreferrer">another piece of code that can generate example CSV files</a> for testing purposes, can be <a href="http://github.com/gotgenes/multiprocessing_examples" rel="noreferrer">found on github</a>.</p> <p>I would appreciate any insight here as to how you concurrency gurus would approach this problem.</p> <hr /> <p><strong>Here are some questions I had when thinking about this problem.</strong> Bonus points for addressing any/all:</p> <ul> <li>Should I have child processes for reading in the data and placing it into the queue, or can the main process do this without blocking until all input is read?</li> <li>Likewise, should I have a child process for writing the results out from the processed queue, or can the main process do this without having to wait for all the results?</li> <li>Should I use a <a href="http://docs.python.org/library/multiprocessing.html#module-multiprocessing.pool" rel="noreferrer">processes pool</a> for the sum operations? <ul> <li>If yes, what method do I call on the pool to get it to start processing the results coming into the input queue, without blocking the input and output processes, too? <a href="http://docs.python.org/library/multiprocessing.html#multiprocessing.pool.multiprocessing.Pool.apply_async" rel="noreferrer">apply_async()</a>? <a href="http://docs.python.org/library/multiprocessing.html#multiprocessing.pool.multiprocessing.Pool.map_async" rel="noreferrer">map_async()</a>? <a href="http://docs.python.org/library/multiprocessing.html#multiprocessing.pool.multiprocessing.Pool.imap" rel="noreferrer">imap()</a>? <a href="http://docs.python.org/library/multiprocessing.html#multiprocessing.pool.multiprocessing.Pool.imap_unordered" rel="noreferrer">imap_unordered()</a>?</li> </ul></li> <li>Suppose we didn't need to siphon off the input and output queues as data entered them, but could wait until all input was parsed and all results were calculated (e.g., because we know all the input and output will fit in system memory). Should we change the algorithm in any way (e.g., not run any processes concurrently with I/O)?</li> </ul>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTom Neyland
    1. USgotgenes
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSolving embarassingly parallel problems using Python multiprocessing
      1. USunutbu
      1. VTFavorite
    2. VO
      singulars
      1. POSolving embarassingly parallel problems using Python multiprocessing
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POSolving embarassingly parallel problems using Python multiprocessing
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHaha, I Love the term embarrassingly-parallel. I am surprised that this is the first time I have heard the term, its a great way to refer to that concept.
      singulars
      1. POSolving embarassingly parallel problems using Python multiprocessing
      1. USTom Neyland
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload