×

### Let's log you in.

or

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

×

or

15

0

19

# Class Note for COSC 4397 with Professor Gabriel at UH

Marketplace > University of Houston > Class Note for COSC 4397 with Professor Gabriel at UH

No professor available

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.
No professor available
TYPE
Class Notes
PAGES
19
WORDS
KARMA
25 ?

## Popular in Department

This 19 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 with Professor Gabriel at UH

×

×

### 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: 02/06/15
0080 4397 Parallel Computation Graph Algorithms ll Edgar Gabriel Spring 2006 0080 4397 Parallel Computation Edgar Gabriel C S Minimum Spawning Tree Minimum Spawning Tree Spawning tree undirected Graph G being a subgraph of G containing all vertices Minimum spawning tree spawning tree with minimum weight 0080 4397 Parallel Computation Edgar Gabriel 2 C J Prim s Algorithm Given GVEw and an arbitrary vertex r vT r drl O for all v V V do dv wrV while V5 V do find vertex u such that dulmindvlv V V VT VTUU for all v V V5 do dv min dv wluv end while 0080 4397 Parallel Computation Edgar Gabriel 3 C J Prim s Algorithm ll VT vector containing the vertices already added to the spawning tree V VT set of vertices which have not yet been added to the spawning tree d distance vector eg dii contains the minimum weight of vertex i to any vertex in the spawning tree 0080 4397 Parallel Computation Edgar Gabriel 4 C J Example I O 1 3 oo oo 3 1 O 5 1 oo oo 3 5 O 2 1 oo oo 1 2 O 4 oo oo oo 1 4 O 5 2 oo oo oo 5 O VT1 1 1 1 1 1 d1 0 5 1 oo oo 1 undefined node considered in the following search since Vertex is already in the spawning tree 0080 4397 Parallel Computation Edgar Gabriel 5 C J Example II 39 VT13 1 1 1 1 d10 214 00 0080 4397 Parallel Computation Edgar Gabriel 6 C J Example Ill VT13 0 2 1 1 dl10 2113 VT13 0 2 4 1 dl10 2113 0080 4397 Parallel Computation Edgar Gabriel 7 C Example IV VT130245 dl102113l 0080 4397 Parallel Computation Edgar Gabriel 8 C S Sequential implementation I Given ANN N u l Vtivtcount u for i0 iltN i di MU i l for i1 iltN i u findu vt vtcount d vtivtcount u updated d vt vtcount N u a 0080 4397 Parallel Computation Edgar Gabriel 9 Sequential implementation ll int findu int vtN int vtcount int dN int i j found int currentminMYINF currentminloc l for i0 iltN i for found O jO jltvtcount j if ivtj foundl if found continue if di lt currentmin currentminloc i currentmin dii return currentminloc Edgar Gabriel 10 Sequential implementation Ill void updated int diN int vtN int vtcount int N int u int aiNN int i j found for i0 iltN i l for foundO jO jltvtcount j if ivtj foundl if found continue dti min dtii atuitiil return 0080 4397 Parallel Computation Edgar Gabriel 1 1 Parallel Algorithm 1 l Each process owns one column of the adjacency matrix Each process owns the according part of the distance vector d vT is replicated on each process Only findu and updated need to be modified d III IIIE 0080 4397 Parallel Computation III III Edgar Gabriel 12 T L l l l r l L CS UH Parallel Algorithm 1 ll int findu int vtN int vtcount int d int mian gmian 1 rank MPICommrank MPICOMMWORLD amprank min0 d minl rank for i0 i lt vtcount i if vtli rank minlO MYINF break MPIAllreduce min gmin l MPI21NT MPIMINLOC MPICOMMWORLD 39 return gminll MPIMNLOC and MPIMAXLOC I Operators for reduction operations returning the minimummaximum value and the process owning the minimum and maximum value Special MPI data types have to be used MPI2 INT array of two integers Element zero contains minmax value Element one contains the rank of the process owning minimalmaximal value MP IFLOATINT structure consisting of a float and an int struct float val int rank 0080 4397 Parallel Computation m Edgar Gabriel 14 C J MPIMNLOC and MPIMAXLOC II Similarly MP IDOUBLEINT MP ISHORTINT MPILONGINT Note the rank in the second element has to be set by each process for the inputvalues MPI guarantees that each process will have the same rank in the resultvector for the location of the minimummaximum even it several processes have the same minimalmaximal value 0080 4397 Parallel Computation Edgar Gabriel 15 C J Parallel Algorithm 1 III void updated int d int Vt int vtcount int u int alN int 1 rank MPICommrank MPICOMMWORLD amprank for i0 i lt vtcount i if vtli rank return d min d alu return 0080 4397 Parallel Computation Edgar Gabriel 16 1 Parallel Algorithm 2 l Each process owns a certain number of columns of the adjacency matrix Each process owns the according elements of the distance vector vT is replicated on each process d 0080 4397 Parallel Computation Edgar Gabriel 17 C Parallel Algorithm 2 ll for i0 iltnx i l for found0 jO jltvtcount j if cxnxivtj foundl if found continue if dli lt currentmin currentminloc cxnxi currentmin di minlO currentmin minll rank MPIAllreduce min gmin l MPIZINT MP IMINLOC MP ICOMMWORLD MPIBcast ampcurrentminloc 1 MPIINT gmin1 MPICOMMWORLD return currentminloc Parallel Algorithm 2 III void updated int d int Vt int vtcount int u int alN int i j rank found for i0 iltnx i for foundO jO jltvtcount j if cxnxivtj foundl if found continue dli mymin dlil alullill return 0080 4397 Parallel Computation Edgar Gabriel 1g 1

×

×

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

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

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

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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