University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2024
Views:

353

Pages:

18
Author:

Haiden Dudley

Introduction to Parallel Computing Outline       Parallel Examples Parallel Strategies Hardware Processes and threads Libraries & your own code Parallelization pitfalls Introduction  Many programs can perform simultaneous operations, given multiple processors to perform the work.  Generally speaking the burden of managing this lies on the programmer.  Either directly by implementing parallel code  Or indirectly by using libraries that perform parallel calculations.  First, let’s look at an example of some problems that could be solved with parallel computations. Limits (“bounds”) on Program Speed  Input/Output (I/O): The rate at which data can be read from a disk, a network file server, a remote server, a sensor, a user’s physical inputs, etc. limits the performance of the program.  Memory: The quantity of memory on the system limits performance.  Example: computer has 16 GB of RAM, data file is 64 GB in size.  CPU (or compute): The speed of the processor is the limit on performance. Why Parallelize? Example 1: Buoy data  Each row is the water temperature in Celcius at a depth of 2m from different ocean buoys off of the coast of New England.  We want to find the average daily temperature across all the buoys.  i.e. sum them all vertically and divide by 5.  How can we parallelize this? time Example 2: Buoy data  Now consider the temperatures from 1 buoy. This is daily data. How can we smooth the data by 30 days?  Smoothing:  Pick 30 days worth of data points starting at day 0. Average them and assign that value to a new array at day 0.  Pick another 30 days of data starting from day 1. Assign that average value to day 1.  Etc.  How can we parallelize this? Example 3: k-mer counting  k-mers are repeated sets of nucleotides in genomic sequences. k is the length of the set.  AGTCCC  Split into k-mers of length 3: AGT, GTC, TCC, CCC  A common problem in genomics is creating a histogram of all possible kmers from a data file. AGTCCCCGTCTTGCCGCGCGGGGGCGGGCGCGGGAAAAAAGCCGCGCGGGGGCGC CCGCGGGAAGGCAGCCCCGCGGCGCGCGGGGGGAGGGGCGGCGCCCGCGGGGGAG CGGCCGGCTCCGGGGGAGGGACGGGGAAGGGGGCGCGCGGGGCTGCCCTGCCGCC CGCCCGCCGCCGCCGCCCGCCTTCGCGCCCCCCCCCAAAAAACACCCCCCCCGGA …imagine this in a file a few dozen GB in size… Example 3: k-mer counting How can we split this up into parallel computations?  Tasks:      Read each line from the file. The file is compressed to save disk space. In each line, find all possible k-mers for a fixed value k. Store all k-mers that are found and how often they occurred. Repeat for the next line. The output is the histogram for the whole file: 3-mer Occurrences AGT 203 GTC 123 TCC 583 CCC 875 …etc… Which steps can happen concurrently? Outline       Parallel Examples Parallel Strategies Hardware Processes and threads Libraries & your own code Parallelization pitfalls Basics of Parallelization  Certain patterns of program execution lend them selves to specific parallelization solutions.  Recognizing these patterns in your code will help you choose which Python parallelization approach to use.  The solutions are strategies – it’s up to you to adapt them to your specific program.  Here’s a few examples. There are lots more than we have time for here! Embarrassingly Parallel  Take a list of numbers: 1 2 3 4 5 6 7 8 9 10  And calculate its sum: 1+2+3+4+5+6+7+8+9+10  This can easily be computed in parallel. Break into 2 chunks, sum them, and sum the chunks:  Or break it down into even smaller computaitons. 1+2+3+4+5 + 6+7+8+9+10 Embarassingly Parallel  Completely independent steps.  Ex.: multiple runs of a simulation, processing multiple data files with the same script, calling 1 function over every element of an array. python script.py Output file 1 Input file 2 python script.py Output file 1 Input file 3 python script.py Output file 1 Input file 1 Many files python script.py Output files Run simultaneously on separate cores Embarassingly Parallel  Each iteration of a for loop might be completely independent of each other. x = [1,2,3,4,5] % Each loop iteration has no dependence % on any other loop iteration. for i = 1:5 x(i) = some_func(x(i)) Divide & Conquer  A problem can be broken into sub-problems that are solved independently. Sub-problems 1 and 2 can be executed in parallel. Problem split Sub-problem 1 Sub-problem 2 Or both 3’s with 2. split Sub-problem 3 Sub-problem 3 Merge/reduce Solution Pipeline  Steps in a pipeline must run sequentially.  These stages could be internal functions in a program. Time Input data stage 1 stage 1 stage 2 stage 2 stage 3 stage 3 stage 4 stage 4 output data Each stage executes in parallel. Chunks of input data Geometric  The problem can be broken up into predictable patterns.  Example: blurring an image – the image can be broken into overlapping tiles processed in parallel.  Different parts of a program may use different parallel strategies during execution.