University:
Boston University
Course:
ENG EC 410 | Introduction to Electronics
Academic year:

2022
Views:

71

Pages:

26
Author:

Naomi Whitehead

INTRODUCTION TO MATLAB PARALLEL COMPUTING TOOLBOX MATLAB Parallel Computing Toolbox Overview • Goals: Basic understanding of parallel computing concepts 2. Familiarity with MATLAB parallel computing tools 1. • Outline: • Parallelism, defined • Parallel “speedup” and its limits • Types of MATLAB parallelism • multi-threaded/implicit, distributed, explicit) • Tools: parpool, SPMD, parfor, gpuArray, etc 2 MATLAB Parallel Computing Toolbox 3 Parallel Computing Definition: The use of two or more processors in combination to solve a single problem. • Serial performance improvements have slowed, while parallel hardware has become ubiquitous • Parallel programs are typically harder to write and debug than serial programs. Select features of Intel CPUs over time, Sutter, H. (2005). The free lunch is over. Dr. Dobb’s Journal, 1–9. MATLAB Parallel Computing Toolbox 4 Parallel speedup, and its limits (1) • “Speedup” is a measure of performance improvement 𝑡𝑖𝑚𝑒𝑜𝑙𝑑 speedup = 𝑡𝑖𝑚𝑒𝑛𝑒𝑤 • For a parallel program, we can with an arbitrary number of cores, n. • Parallel speedup is a function of the number of cores 𝑡𝑖𝑚𝑒𝑜𝑙𝑑 speedup(p) = 𝑡𝑖𝑚𝑒𝑛𝑒𝑤 (𝑝) MATLAB Parallel Computing Toolbox Parallel speedup, its limits (2) • Amdahl’s law: Ideal speedup for a problem of fixed size • Let: p = number of processors/cores α = fraction of the program that is strictly serial T = execution time Then: 𝑇 𝑝 = 𝑇(1) α + 1 𝑝 (1 − α) And: 1 𝑇 1 𝑆 𝑝 = 𝑇 𝑝 = α + 1 (1 − α) 𝑝 • Think about the limiting cases: α = 0, α = 1, p = 1, p = ∞ 5 6 MATLAB Parallel Computing Toolbox Parallel speedup, and its limits (3) • Diminishing returns as more processors are added • Speedup is limited if α < 0 • “Linear speedup” is the best you can do (usually) * 7 MATLAB Parallel Computing Toolbox Parallel speedup, and its limits (3) • The program “chokes” if too many cores are added • Caused by communication cost and overhead, resource contention * 8 MATLAB Parallel Computing Toolbox Hardware: single core • No parallelism System memory Network • Good luck finding one… Processor 1 9 MATLAB Parallel Computing Toolbox Hardware: multi-core • Each processor core runs System memory independently Network • All cores can access system memory Processor 1 • Common in desktops, laptops, smartphones, probably toasters… 10 MATLAB Parallel Computing Toolbox Hardware: multi-core, multi-processor • Each processor core System memory runs independently Network • All cores can access system memory Processor 1 Processor 2 • Common in workstations and servers (including the SCC here at BU) MATLAB Parallel Computing Toolbox 11 Hardware: accelerators System memory Accelerator/ GPU memory Network Accelerator / GPU Processor 1 • Accelerator/GPU is an a separate chip with many simple cores. • GPU memory is separate from system memory Processor 2 • Not all GPUs are suitable for research computing tasks (need support for APIs, decent floatingpoint performance) MATLAB Parallel Computing Toolbox 12 Hardware: clusters System memory Accelerator/ GPU memory Network Accelerator / GPU Processor 1 Processor 2 System memory Accelerator/ GPU memory Network Accelerator / GPU Processor 1 Processor 2 • Several independent computers, linked via network • System memory is distributed (i.e. each core cannot access all cluster memory) • Bottlenecks: inter- processor and inter-node communications, contention for memory, disk, network bandwidth, etc. MATLAB Parallel Computing Toolbox 13 Three Types of Parallel Computing Parallel MATLAB: Multiple Processors and Multiple Cores, Cleve Moler, MathWorks GPU memory Network System memory GPU Processor 1 Processor 2 Multithreaded parallelism… one instance of MATLAB automatically generates multiple simultaneous instruction streams. Multiple processors or cores, sharing the memory of a single computer, execute these streams. An example is summing the elements of a matrix. GPU memory Network System memory Distributed computing. GPU Processor 1 Processor 2 Explicit parallelism. MATLAB Parallel Computing Toolbox 14 Three Types of Parallel Computing Parallel MATLAB: Multiple Processors and Multiple Cores, Cleve Moler, MathWorks GPU memory Network System memory Multithreaded parallelism. Distributed computing. GPU Processor 1 Processor 2 GPU memory Network System memory GPU Processor 1 Processor 2 multiple instances of MATLAB run multiple independent computations on separate computers, each with its own memory…In most cases, a single program is run many times with different parameters or different random number seeds. Explicit parallelism. MATLAB Parallel Computing Toolbox 15 Three Types of Parallel Computing Parallel MATLAB: Multiple Processors and Multiple Cores, Cleve Moler, MathWorks GPU memory Network System memory Multithreaded parallelism. Distributed computing. GPU Explicit parallelism… Processor 1 Processor 2 GPU memory Network System memory GPU Processor 1 Processor 2 several instances of MATLAB run on several processors or computers, often with separate memories, and simultaneously execute a single MATLAB command or M-function. New programming constructs, including parallel loops and distributed arrays, describe the parallelism. MATLAB Parallel Computing Toolbox 16 MATLAB parallel computing toolbox (PCT)  Supports multithreading (adds GPUs), distributed parallelism, and explicit parallelism  You need…  MATLAB and a PCT license  Note that licenses are limited at BU – 500 for MATLAB, 45 for PCT  Parallel hardware, as discussed above MATLAB Parallel Computing Toolbox Distributed Jobs • Define and run independent jobs • No need to parallelize code! • Expect linear speedup • Each task must be entirely independent • Approach: define jobs, submit to a scheduler, gather results • Using MATLAB scheduler – not recommended: c = parcluster; j = createJob(c); createTask(j, @sum, 1, {[1 1]}); createTask(j, @sum, 1, {[2 2]}); createTask(j, @sum, 1, {[3 3]}); submit(j); wait(j); out = fetchOutputs(j); define submit gather 17 MATLAB Parallel Computing Toolbox 18 Distributed Jobs on SCC • For task-parallel jobs on SCC, use the cluster scheduler (not the tools provided by PCT) • To define and submit one job: qsub matlab -nodisplay -singleCompThread -r “rand(5), exit” submit define • To define and submit many jobs, use a job array: qsub –N myjobs –t 1-10:2 matlab -nodisplay -singleCompThread –r \ “rand($SGE_TASK_ID), exit" • Results must be gathered manually, typically by a “cleanup” job that runs after the others have completed: qsub –hold_jid myjobs matlab -nodisplay -singleCompThread –r \ “my_cleanup_function, exit" MATLAB Parallel Computing Toolbox 19 Parallel Jobs • Split up the work for a single task • Must write parallel code • Your mileage may vary - some parallel algorithms may run efficiently and others may not • Programs may include both parallel and serial sections • Client: • The head MATLAB session – creates workers, distributes work, receives results • Workers/Labs: • independent, headless, MATLAB sessions • do not share memory • create before you need them, destroy them when you are done • Modes: • pmode: special interactive mode for learning the PCT and development • matlabpool/parpool: is the general-use mode for both interactive and batch processing. MATLAB Parallel Computing Toolbox 20 Parallel Jobs: matlabpool/parpool • matlabpool/parpool creates workers (a.k.a labs) to do parallel computations. • Usage: parpool(2) % . . . % perform parallel tasks % . . . delete(gcp) • No access to GUI or graphics (workers are “headless”) • Parallel method choices that use parpool workers: • parfor: parallel for-loop; can’t mix with spmd • spmd: single program multiple data parallel region MATLAB Parallel Computing Toolbox 21 parfor (1) • Simple: a parallel for-loop • Work load is distributed evenly and automatically according to loop index. Details are intentionally opaque to user. • Many additional restrictions as to what can and cannot be done in a parfor loop – this is the price of simplicity • Data starts on client (base workspace), automatically copied to workers’ workspaces. Output copied back to client when done. • Basic usage: parpool(2) x = zeros(1,10); parfor i=1:10 x(i) = sin(i); end delete(gcp) MATLAB Parallel Computing Toolbox 22 parfor (2) • For the parfor loop to work, variables inside the loop must all fall into one of these categories: Type Description Loop A loop index variable for arrays Sliced An array whose segments are manipulated on different loop iterations Broadcast A variable defined before the loop and is used inside the loop but never modified Reduction Accumulates a value across loop iterations, regardless of iteration order Temporary Variable created inside the loop, but not used outside the loop c = pi; s = 0; X = rand(1,100); parfor k = 1 : 100 a = k; % a - temporary variable; k - loop variable s = s + k; % s - reduction variable if i <= c % c - broadcast variable a = 3*a - 1; end Y(k) = X(k) + a; % Y - output sliced var; X - input sliced var end MATLAB Parallel Computing Toolbox parfor (3): what can’t you do? • Data dependency: loop iterations are must be independent a = zeros(1,100); parfor i = 2:100 a(i) = myfct(a(i-1)); end 23 MATLAB Parallel Computing Toolbox 24 parfor (4): what can’t you do? • Data dependency exceptions: “Reduction” operations that combine results from loop iterations in order-independent or entirely predictable ways % computing factorial using parfor x = 1; parfor idx = 2:100 x = x * idx; end % reduction assignment with insert operator d = []; parfor idx = -10 : 10 d = [d, idx*idx*idx]; end % reduction assignment of a row vector v = zeros(1,100); parfor idx = 1:n v = v + (1:100)*idx; end MATLAB Parallel Computing Toolbox 25 parfor (4): what can’t you do? • Data dependency exception: “Reduction” operations that combine results from loop iterations • Reduction operations must not depend on loop order • must satisfy x ◊ (y ◊ z) = (x ◊ y) ◊ z • Plus (+) and multiply (*) operators pass, subtract (-) and divide (/) may fail. s = 0; parfor i=1:10 s = i-s; end MATLAB Parallel Computing Toolbox 26 parfor (5): what can’t you do? • Loop index must be consecutive integers. parfor parfor parfor parfor A = [3 No i i i i 7 = 1 : 100 % OK = -20 : 20 % OK = 1 : 2 : 25 % No = -7.5 : 7.5 % No -2 6 4 -4 9 3 7]; parfor i = find(A > 0) % • …and more! See the documentation