### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for COSC 4397 at UH

### View Full Document

## 15

## 0

## Popular in Course

## Popular in Department

This 29 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Houston taught by a professor in Fall. Since its upload, it has received 15 views.

## Reviews for Class Note for COSC 4397 at UH

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

0080 4397 Parallel Computation Algorithm structure ll Edgar Gabriel Spring 2006 0080 4397 Parallel Computation Edgar Gabriel C S Algorithm struc Organize by tasks Organize by data decomposition Task Parallelism Divide and Conquer Geometric decomposition Recursive data 2U re Organize by flow of data Pipeline Eventbased coordination Task parallelism Implemented by Task queues Task distribution vs work stealing Divide and Conquer for recursive problems Split problem into subproblems until a lower limit in the problem size has been reached Solve the subproblem Edgar Gabriel IIll 0080 4397 Parallel Computation 2 Merge the results of the subproblems into the final result Task Parallelism using MasterWorker framework Master Process Worker Process 1 Worker Process 2 Result queue Task queue Fl r1 Ul r1 a 0080 4397 Parallel Computation H l Edgar Gabriel 3 Lhu Ill Task Parallelism using work stealing 0080 4397 Parallel Computation Edgar Gabriel 4 CSUH Divide and Conquer algorithms split split split Base solve Base solve 0080 4397 Parallel Computation Edgar Gabriel 5 S Geometric decomposition For all applications relying on data decomposition All processes should apply the same operations on different data items Key elements Data decomposition Exchange and update operation Data distribution and task scheduling 0080 4397 Parallel Computation Edgar Gabriel 6 C J Numerical differentiation forward difference formula From the definition ofderivatives y fxhfx fx l11 3 h one can derive an approximation for the fst derivative x z fxhIfx The same formula can be obtained from the Taylor I I Ser39es e39g39 fxh fxhf ltxgt7f 5 0050 4397 P n lob tjfx fx 131 g Edgar Gabriel am e ompu a Iquot 0 Central Difference Formula A better formula is derived if looking at the following two y terms 2 3 fx h fx hf x f x f lt 1 fx h fx hf x h3f x f 2 Subtracting equation 52 from 51 leads to h2 EL L fx 2hfxh fx m h is quadratic in the error term 0080 4397 Parallel Computation Edgar Gabriel 8 Central Difference Formula for 2nd Derivatives Extend 51 and 52 by an additional term 114 4 we fxh fx hf x h7f ltxgt fquotx rec 11 fx hf x h f x h fquotx h flt4gtlt 2 3 4 Adding both equations leads to 1 tfltxh 2fx fx h f 21 0080 4397 Parallel Computation Edgar Gabriel 9 C J Numerical differentiation summary Forward difference formula f x Central difference formula for the 1St derivative x Zihtfltxhgt fxh Central difference formula for the 2ncl derivative 1 tfltxh 00 rec 1m 0080 4397 Parallel Computation Edgar Gabriel 10 C J Differential equations terminology Differential equations equations containing the derivative of a function as a variable An ordinary differential equation ODE only contains functions of one independent variable A partial differential equation PDE contains functions of multiple independent variables and their partial derivatives The order of a differential equation is that of the highest derivative that it contains The goal is to find a function yt whose derivatives fulfill the given differential equations eg y gtt ft y y y W 0080 4397 Parallel Computation Edgar Gabriel 1 1 C J Finite Differences Approach for Solving Differential Equations Idea replace the derivatives in the DE by an according approximation formula Typically central differences 1 y t 2 hyth yth 1 y t yt 10 MO W 11 Example Boundary value problem of an ordinary differential equation d2 d defxy y anSb dx ya a W m gi ilParallel Computa1ti n 0 Finite Differences Approach ll For simplicity lets assume the points are equally spaced b xiaih OSiSn1 h n6 A two point boundary value problem becomes then 3 0 05 1 1 Wltyi12yiyi 1fx9y9 yilyi l X1 yn1 Equation X1 leads to a system of equations Solving the system of linear equations gives the solution of the ODE at the distinct points x0x1xnxn1 0080 4397 Parallel Computation Edgar Gabriel 13 C J Example I Solve the following two point boundary value problem using the finite difference method with hO2 2 dZ2 10xO 039531 dx dx y0 1 W 2 Since hO2 the mesh points are x0 0c1 02c2 04c3 06c4 08c5 10 39 ThUS yo W60 1 ys W65 2 y1 y4 are unknown 0080 4397 Parallel Computation Edgar Gabriel 14 C O Example ll Discrete version of the ODE using central differences 1 1 0541 2 Yi 1 22 hyi1 yi 11Oxi O 1 1 0541 235 yi 12O 4yi1 yi 11Oxi O I 25yi12yiyi 15yi1yi 11Oxi 0 I 2Oyi1 50yi30yi1 1xi 0080 4397 Parallel Computation Edgar Gabriel 15 C J Example Ill i1 20320 50y1 302 2 1ch1 gt 20 50yl30y2 1039O2 i1 50yl30y2 2 22 i2 2Oy1 50y230y3 4 13 20322 503233Oy4 2 6 14 20323 50324 2 68 or 50 3O 21 22 2O 50 3O 22 4 20 50 30 323 6 20 50 324 68 W H4 A y b 0080 4397 Parallel Computation Edgar Gabriel 16 C I So Scalar product IIll 0080 4397 Edgar Gabrie Given Ab and an initial guess yo r0 b T Given fsuch that f0 r0 2 O 00 a 00 1 V0 2 P0 0 fori12 A1 p re 3 1 pi a piil wi71 Pi ri l Pi 1 wi 1Vi 1 a A re Vi s rl i a ITS i th yi yi 1api wis 7 S Uit 7 ving Ayb using BiCGSTAB Scalar product in paralle Process with rank0 Scalar product rank1 N1 a071 b01 71 alN 121N s Z ai bi i0 Parallel algorithm NZ l N l s 2aibi2aibi N531 FNZ NZ l Z alocal blocal Z alocal blocal i0 i0 rankO I rank1 requires communication between the processes 0080 4397 Parallel Computation Edgar Gabriel 18 C J Matrixvector product in parallel Process 0 IIll 50x1 3OX2 20x1 50x2 20x2 0080 4397 Parallel Computation Edgar Gabriel 19 Process 1 Matrix vector product in parallel ll Introduction of ghost cells Process zero Process one X1 X2 II Looking at the source code eg 17i ri l ltPi 1 wi lvi l Vi Apr since the vector used in the matrix vector multiplication changes every iteration you always have to update the ghost cells before doing the calculation 0080 4397 Parallel Computation Edgar Gabriel 20 C J Matrix vector product in parallel Ill so the parallel algorithm for the same area is Pi ri t ltPi 1 wi lvi l Update the ghostcells of p 99 Process 0 sends p2 to Process 1 Process 1 sends p3 to Process 0 Vi Apr 0080 4397 Parallel Computation Edgar Gabriel 21 C J 2D Example Laplace equation I 2D Laplace equation 2 2 a a QMX y WMX y 0 Central discretization leads to ui1j 2uij ui uij1 2uij ui j 1 1 39 hZ J hZ O o o 9 o o o I1 39 0 0 O o 11 1 11 0080 4397 Parallel Computation Edgar Gabriel 22 C J 2D Example Laplace equation ll Parallel domain decomposition Data exchange at process boundaries required Halo cells Ghost cells Copy of the last rowcolumn of data from the neighbor process a CS UH hnlhvll 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 000000000000000 000000000000000000 00000 00000 00000 0000 00000 00000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 0000000000000000 00000000000000000 00000000000000000 OOIOIODIOOOOBOOOOI 0000 00000 00000 00000 00000 00000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 000000000000000000 000000000000000000 QQ 23 0080 4397 Parallel Computation Edgar Gabriel IIll IIll Edgar Gabriel 0080 4397 Parallel Computation 24 CS UH il il 000 600000 00 Limits the number of concurrent messages Ordered communication to avoid deadlock Implementation using blocking SendRecv 2D example Laplace equation ll Recursive Data Typically applied in recursive data structures Lists trees graphs Data decomposition recursive data structure is completely decomposed into individual elements Example prefix scan operation Each process has an element of an overall structure eg a linked list eg an integer x Lets denote the value of the X on process i xi At the end of the prefix scan operation process k holds the sum of all elements of xi for i0k 0080 4397 Parallel Computation Edgar Gabriel 25 C J Recursive data ll Example for eight processes Process Process Process Process Process Process Process Process 0 1 2 3 4 5 6 7 Before X X X X X X X X prefiX scan 0 1 2 3 4 5 6 7 After prefiX scan X0 X0 X1 XO X1 XO X1 XO X1 XO X1 X2 X2 X3 X2 X3 X2 X3 X4 X4 X5 IIll Edgar Gabriel 0080 4397 Parallel Computation 26 Sequential implementation Each process forwards its sum to the next process 39 n messages time steps required for n processes Process Process Process Process Process Process Process Process met 0080 4397 Parallel Computation m Edgar Gabriel 27 C I UH Recursive da a approach X1 X2 X3 X4 X5 X6 2060 2 209 we 20 we 20 Ixj 2 x4 20 we 20 x6 w w w w w w w Zorn IXO 2060 I19 209 IXZ 206219 20 x4 2 XS 20 x6 I 2060 2 2060 2 IIll J 7 2060 we 20 we 2 Ixj J 7 202 we 20 x6 2061 x4 J j 2060 we 2 we 2060 Ixj 20 x4 20M 20 x6 0080 4397 Parallel Computation Edgar Gabriel 28 Recursive Data Ill Very fine grained concurrency Restructuring of the original algorithm often required Parallel algorithm requires substantially more work which can however be executed in less timesteps 0080 4397 Parallel Computation Edgar Gabriel 29 C J

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.