×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## Parallel Computations II

by: Lisette Hodkiewicz

24

0

13

# Parallel Computations II CS 6260

Lisette Hodkiewicz
WMU
GPA 3.83

Elise Dedoncker

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Elise Dedoncker
TYPE
Class Notes
PAGES
13
WORDS
KARMA
25 ?

## Popular in ComputerScienence

This 13 page Class Notes was uploaded by Lisette Hodkiewicz on Wednesday September 30, 2015. The Class Notes belongs to CS 6260 at Western Michigan University taught by Elise Dedoncker in Fall. Since its upload, it has received 24 views. For similar materials see /class/216887/cs-6260-western-michigan-university in ComputerScienence at Western Michigan University.

×

## Reviews for Parallel Computations II

×

×

### What is Karma?

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

Date Created: 09/30/15
Solving Linear System using Parallel Gaussion Elimination Thap Panitanarak 086260 Spring 2009 K Linear System 0 Linear System or System of Linear Equations 0 n equations of n variables o aile is a coefficient of X in equation i a000 a01X1 a022 aOn1Xn1 b0 amx0 aux1 a1 12x2 a11xn1 b1 an10X0 an11X1 an12X2 an1n1Xn1 bn1 K 392009 392009 Linear System 0 Matrix representation a00 a01 a02 X0 b0 a1o a11 a12 X1 b1 an 1o an 11 an 12 Xn1 bn1 A X b j Linear System 0 Matrix representation Augmented matrix a00 a01 a02 aon 1 b0 a10 a11 a12 a1n 1 b1 an 1o an 1 1 an 12 an 1n 1 bn 1 J 392009 Linear System 0 Matrix representation Triangular matrix ao1 a02 ao n 1 33911 a3912 a391n1 o o o a3911 T J Solving Linear System AX b TX c X d Original By Gaussian By Back Linear System Elimination Substitution J Back Substitution Solve a linear system TX c where T is upper triangular 1X0 1x 1gtlt2 4gtlt8 8 2X1 3X2 1X8 5 2X2 3x8 0 2X8 4 Substitute X3 2 1X0 1X1 1X2 O 2x 3X2 2x2 2X8 4 Next X2 and X1 Back Substitution Substitute X2 3 1x0 3 2x1 12 Substitute X1 6 1X0 3 2X2 6 Wegetx03x1 6X23andx32 392009 392009 GaUSSIan Elimination 0 General Concept 0 WellKnownquot algorithm for solving the linear system AX 0 Reduce AX b to TX c where T is an upper triangular matrix o Back substitution TX c to solve for X Row Operations used 0 Multiply any row with a nonzero constant 0 Row swap 0 AddSubtract one row with another J GaUSSIan Elimination Consider the linear system BX 2X2 2X8 8 2X0 5X2 2X8 4 39 4X0 39 3X1 5X2 4X8 1 8X0 18X1 2X2 3X8 40 39 mm 319309 0395l m20 ago300 391 and map asp300 2 4X0 BX 2X2 2X8 8 4X2 1X8 O BX 3X2 2X8 9 BX 8X2 7X8 24 Lower elements of column 0 are eliminated H j Gaussian Elimination nth1 a2Y1a1y1 1 and may1 a3Y1a1y1 2 4X0 BX 3X1 39 mag a32322 2 4X0 BX 3x1 Wegethc 2X2 4 2X2 2X2 4X2 1X2 2gtlt8 8 1gtlt8 0 1X8 9 5gtlt8 24 2X8 8 1X8 0 1X8 9 3X8 6 Gaussian Elimination 0 There is a problem ll Consider the system 6X1 2x0 4x0 3X 8X0 18X1 We cannot compute rnL0 aiyoaoyo i 13 Divided by Zero 2X2 5X2 5X2 2X2 Solution Partial Pivoting 2X8 8 2X8 4 4X8 1 3x8 40 392009 Gaussian Elimination Partial Pivoting Use the rowthat has the biggest absolute value of a pivot column as a pivot row row swap needed BX 2X2 2X8 8 2X0 5X2 2X8 4 3X1 5X2 4X8 1 25x tax1 2x2 3x3 40 8x0 18X1 2x 3x 40 I 2X0 5X2 2X8 39 4X0 39 3X1 5X2 4X8 6x1 2x2 2x8 8 Also make the computation more accuracy Gaussian Elimination Sequential Algorithm fori from 0 to n1 do Back Substitution Find Pivot Row fori from n1 to 0 ax 0 xi ainaii for from i to n1 do for from 0 to i1 do if pmax lt la il then ain a nxi aii p ax l 39il end do prow j end do end if end do rswapiprow Note To make row swa more Gaussian Elimination efficientl wecan also useindirectv for fromi1 to n1 do IndexloclJiyhere physical row m anvilav JIS Indexed by Virtual row for k from i to n do a k a kaik m nd do 392009 Gaussian Elimination Indirect index for row swap o BX 2X2 2X8 8 1 2X0 5X2 2X8 4 2 3x1 5x2 4x8 1 3 3 iax 2x2 3x3 40 3 BX 2X2 2X8 8 1 2X0 5x2 2x8 4 2 4X0 3X1 5x2 4x8 1 0 8X0 18X1 2X2 3X8 4O Gaussian Elimination Sequential Algorithm Analysis 0 Gaussian elimination with partial pivoting In iteration k column k Finding pivot row step uses nk Elimination step uses nk1nk n iterations 0 to n 1 9 nn12 nn 1n13 On3 Back substitution In iteration k it takes n k 1 n iterations 9 nn 12 On2 o All in On3 392009 392009 K I I I I GaUSSIan Elimination Parallel Design Back Substitution 0 Consider 1X0 1x 1gtlt2 4gtlt8 2X1 3X2 1X8 5 2x2 3X8 2X8 4 c We can change to Gaussian Elimination Parallel Design 0 Back Substitution Processors asignment row wise Po 1X0 8 4X3 1X2 11 P 5 1gtlt8 3gtlt2 p2 0 3X3 4 P3 computes X3 and broadcast X3 to others Pm P1 and P update their values b s P co mputes x2 and broadcast X2 to others ED and P1 u date their values b s P1 computes X1 and broadcast X1 to others P0 updates its value and computes its X0 Gaussian Elimination Parallel Design Back Substitution Algorithm amp Analysis for i from n1 to 0 do Pi computes xi Pi boardcasts xi to others P s forj from 0 to H do in parallel Pj updates bj d do en end d o PO computes xO With n processors we can achieve Onlogzn Speedup S n2nlogzn nlogzn Example n 16 9 S 164 4 K Gaussian Elimination Parallel Design 0 Gaussian elimination with partial pivoting Processors asignment row wise P 0 4X0 Pl 2X0 P2 4X0 P8 8X0 6X1 BX 18X1 2X2 5X2 5X2 2X2 2X3 2X3 4X3 3X3 Communication needed to find a pivot row in each iteration 9 All reduce pmax prow Communication needed to zero off elimination all processors need to know all elements in pivot row Parallel elimination can be done after all processors have pivot row 392009 AllReduce Communication 0 Hypercube Find MAX A 4115 97o lt gtOQ7u79 2 5w 9 i 7 1 l 7 7 7 9 6H9 9 9 4 I 7 4lt gto7 x9 9 6 I 91 6 9 9 399 4 7 H7 9 9 K 1 v4 3 Gaussian Elimination Parallel Design Gaussian elimination with partial pivoting Algorithm for i from 0 to n1 do find pivot row find maxpmaxprow using allreduce P39 swaps its row or index with Pprow eimination Pi broadcasts its row to others forj from i1 to n1 do in parallel Pj computes mi for k from i to n do Pj computes aik end do end do end do 392009 Gaussian Elimination Parallel Design 0 Gaussian elimination with partial pivoting Anaysis 0 With n processors At iteration k Finding pivot row step takes logzn Elimination step takes n klogzn n k c Total time Tp nlogzn nn1logzn2 nn12 c Speedup S nn12 nn 1n13 nlogzn nn1logzn2 nn12 n12n133ogznnogznn1 0 Example n 16 9 822 Gaussian Elimination Parallel Design 0 Other issues 0 Another Data distributing Columnwise o PltnExampleP4n12 o P4 row 4 8 12 o Loadbalancing Efficiency amp Scalability 392009 Question 0 What is the purpose of allreduce communication Give an example o At the end of communication all processors have the same reduced value Min Max etc References 0 1 Seyed H Roosta Parallel Processing and Parallel Algorithms Theory and Computation SpringerVerlag 2000 o 2 Micheal J Quinn Parallel Programming in C with MPI and OpenMP Tata McGrawHill 2003 392009

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Bentley McCaw University of Florida

#### "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!"

Janice Dongeun University of Washington

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

Forbes

#### "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."

Become an Elite Notetaker and start selling your notes online!
×

### 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