YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 34.3 - Thread-Level Parallelism II: Computing Pi

[CS61C FA20] Lecture 34.3 - Thread-Level Parallelism II: Computing Pi — Transcript

by CS 61C Departmental · 3,111 words · 489 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back now let's see a really
0:02nice example
0:04in which we try to compute pi first
0:06we'll try it in cereal and then we'll
0:08try it in parallel and see we can do
0:09this
0:09we like this problem because we call it
0:11embarrassingly parallel
0:13it slices up really neatly into
0:15different slices of problems
0:16that can be farmed out to workers and
0:18they come back and each of the workers
0:19doesn't need the neighbor's
0:20value there's not a lot of communication
0:22between them i'll just do my job and
0:23then give it back and then you kind of
0:24put it all together at the end
0:26it's a nice four conjoined model
0:29there are two ways to do this this is
0:31the traditional way the
0:33if you were look at x squared plus y
0:35squared equals one
0:36that's a circle of area one and if you
0:39looked at a quarter of that
0:41so the top right corner if you just
0:43solve that for y you get y equals
0:451 uh minus x squared square root of 1
0:48minus x squared that's the
0:49that's the upper right value that's the
0:51upper right value here if i do this
0:52and look at this this is an area one
0:54this is sorry area pi
0:56radius 1 and the area equals pi
1:02this is simply y equals square root of
1:061 minus x squared from and if i
1:08integrate this from 0 to pi i'm going to
1:10get a quarter because i'm
1:12going to get a quarter of pi 0 to 1 i'm
1:14going to get a quarter pi if i multiply
1:15that by 4
1:16i get pi so this is just integrating
1:19this equation just from here just this
1:21curve just this curve
1:22and i say what's this area in here and
1:25this is 1
1:26and i integrate this and this is height
1:281 also this is
1:29square root of 1 minus 1 minus x squared
1:32but i multiply that by 4
1:34and i integrate between 0 and 1 i get pi
1:36so this is mathematically telling me i
1:38have just pi there's nothing it doesn't
1:39tie today it just
1:40says pi is a number and there there's
1:42another analogy which
1:43this curve this is beautiful this is
1:46also if you integrate this from zero to
1:47one
1:48pi which is a nice curve it looks like
1:50that picture on the right you see
1:52what we like about this over the top one
1:54is that
1:56square root can be slow from a floating
1:58point calculation point of view
1:59but squaring is really easy so we can we
2:02can do multiplication really fast much
2:03better than square root so we're gonna
2:04try this one
2:05and we see we can integrate this again
2:06from zero to one and do this so remember
2:07it's 4 over
2:091 plus x squared and here's a piece of
2:11code
2:12that does this serially here's what
2:14we're trying to get to at the top
2:20three 3.14159.26535.897932 uh three
2:22eight four et cetera
2:24so let's look at what this code does i
2:26have only ten steps i'm going to ten
2:28different rectangles to approximate my
2:30area
2:31and the step size is one over the number
2:33of steps that's the width of each of
2:34those rectangles as if i remember look
2:36at this
2:37what's the width of that rectangles that
2:39step
2:41okay what's the height well remember
2:43this before the height is 4 over 1 plus
2:45x squared
2:46and so this is 4 over 1 plus x
2:49squared wherever the value of x is x is
2:51a value from 0 to 1.
2:53so i initialize my accumulator sum as
2:56zero and then i'm going to go through
3:00you always want to iterate on integer
3:02values you want to be you don't want to
3:03be iterating on floating point values so
3:05i'm going to count how many steps
3:07because you always have a very clean cut
3:08line
3:09floating point has this noise right
3:11rounding noise so you don't want to have
3:12well sometimes i
3:13i ended up having some number of
3:15iterations another some other number if
3:17based on the noise i want to have a
3:18clean number of iterations now i have
3:19exactly here numsteps
3:21iterations x is going to continue to
3:25move to the right
3:26so here's the value oops here's the
3:27value of x as it continues to move to
3:29the right
3:29whoops as i continue to move to the
3:31right here
3:33sum starts at zero starts at zero and is
3:36going to be
3:37the area of that rectangle this is the
3:40width
3:41and this is the height okay so none of
3:44that none of that's
3:45none of that's magic and i'm doing that
3:47here and when i'm all done
3:48i print out the value of pi let's see
3:50what i get
3:51well i'm trying to get three point four
3:53one five nine two six five three five
3:55well i got to the two well it's supposed
3:58to be a one three one three one four one
3:59i didn't even get there so i got two
4:01significant figures if i increase num
4:04steps i'd do very well
4:05i would you know increase some steps to
4:07the biggest number i possibly can handle
4:09i would do really well take a long time
4:11but i do very well not very accurate
4:14so let's increase the numb steps and
4:16let's paralyze let's actually play with
4:17this and see how close we can get
4:19parallelization version boy i wish there
4:21were a way i wish certainly our way to
4:23just
4:24have a one-line change and make this
4:26work
4:27we do that pragma we talked about before
4:29that pragma parallel 4
4:31and i'm now done so i'm not going to
4:32paralyze that for loop openmp does all
4:35the hard work i obviously have to add
4:36the include file but that's all i'm
4:37going to add i love this isn't it nice
4:40two lines i add and this thing is now
4:41paralyzed
4:43num steps is still 10. and we can see
4:46what happens
4:47here we go here's my parallel four i'm
4:49going to sum plus equals let's see what
4:51happens here all right it looks pretty
4:52good
4:53and uh oh i've got a problem
4:57why is there a problem let me see what
4:58the problem is here
5:01each thread needs access to this shared
5:04element
5:05the whole idea of parallelization one of
5:06the core ideas of paralyzing
5:08anything just in life anything is
5:12what are any shared resources if i've
5:14got a shared resource i really have to
5:15be very careful about the shared
5:17resource
5:17if i have multiple workers all working
5:20on and reading and writing to a shared
5:21resource
5:22imagine you know imagine a google doc
5:24and they're all reading and writing and
5:25copying and grabbing a thing and
5:27grabbing their own version
5:28which is in their cache and then putting
5:29it back it could really be ugly google
5:31doc is nice because it's not really
5:32their own copy of this
5:33but if i had a folder and i'm copying a
5:35version of paper and i'm putting it back
5:36and then you're grabbing copy
5:37when i'm writing in parallel but there
5:39are issues like that
5:40so this shared value sum is a problem we
5:43don't like that
5:44the code's going to run sequentially
5:46that sum it knows that some is is
5:48sequentially
5:49so we got to think about how to do this
5:50in a way that i don't have this single
5:52this single sum that's that's going to
5:54be shared across across these guys
5:57so let's do this what if i did the same
6:00thing i did with my for loop and just
6:01slice it up and say sum
6:03zero first thread you're going to deal
6:05with the left side of this
6:06and you're going to do with the right
6:07side of this and then i compute
6:10independently sum of zero and sum of one
6:12so i'm going to have the sum array
6:13that i independently compute and it'll
6:15independently contribute to so
6:17you know here's just two accumulated one
6:19accumulator i'm gonna have
6:21multiple accumulators in parallel and
6:23then
6:24when i'm all done i then add them up and
6:26the join is
6:27a sequential thing where i go through
6:29each of the sum all right what was yours
6:30you know
6:31it's like all these workers went out and
6:32it worked for me how much you make
6:34okay how much you make how much you make
6:35and i write them all down at the end of
6:36the day but they all were doing their
6:37thing in parallel working their job at
6:39the end of the day
6:39the boss asked you how much did you make
6:41and here it's saying how much did you
6:42accumulate how much area how much
6:44average you calculate how much average
6:45did you calculate
6:46done so that seems like the way we do
6:48this so let's do a trial run here
6:50so now what do we change well i have to
6:53have
6:54i'm going to hard code the number of
6:56threads to four we talked before about
6:57how to ask the total number of threads
6:59are
6:59or i can set that somewhere and by the
7:01way here's the way i'm setting it so num
7:03threads is this
7:04constant i'm just saying it to 4 so i
7:05did that before
7:07and i'm going to do my parallel loop i
7:09have to here i go is my sum and i'm
7:11going to initialize my sum to zero so it
7:13wasn't as easy as before before i had a
7:14one-liner sum is zero now i have to have
7:16a little loop
7:16to initialize all my sum increment
7:18accumulators to be zero
7:21i do the same thing everything's the
7:22same except that what am i doing
7:24differently here
7:26here's this idea each of them is giving
7:28up a different piece of that array just
7:30like i was doing my for loop before
7:32each of them is going to be contributing
7:33to a different sum of sum of id where id
7:36is my
7:37get thread number aha we did this before
7:39we did this printout we kind of showed
7:41what that was
7:42here i'm also printing out this piece of
7:44it and the id number same as before all
7:46that's the same code as before
7:48i am accumulating all to the various
7:49values of the sum and at the end
7:51i initialize pi the return value to be
7:53zero i
7:54at i keep in sequentially not in
7:57parallel
7:58contributing sums contribution into pi
8:01and then i print what pi is how's my
8:03number 3.142425 we did pretty well
8:07i've parallelized this at least into
8:08four different ways and hopefully this
8:10is pretty close to being four times as
8:11fast it's not going to be perfect
8:12there is some overhead i still have to
8:14do this adding up everything
8:16of the sums in sequential order but i'm
8:18getting close to a four time improvement
8:20in speed love this did pretty well let's
8:23increment this to now
8:24just change one line to say rather than
8:26uh number steps is ten
8:27number steps is now with a million and
8:30how am i doing
8:31three point one four one five nine two
8:33six five three five
8:34eight nine seven not bad
8:38not bad so we're actually doing fairly
8:40well this is a pretty good job
8:42i'm feeling very confident about this i
8:44love this
8:46now i gotta take a second back
8:49how do i paralyze computing sum
8:52you remember that sum at the end i had
8:54to stop and remember look
8:56that was fine when i did this this is
8:58i'm stalling
9:00for four threads it's not too bad it's
9:03only four threads
9:04um this has nothing to do with its
9:06number of steps number threads could i
9:08paralyze
9:09that threads what if i had a lot of
9:11threads what if i had
9:12could i paralyze that parallelize the
9:15computing the sum
9:16in some way that would be interesting
9:19well let's try this one
9:20let's bring that pi and that pi plus
9:22equals sum of id
9:23let's bring that into the loop somehow
9:25so now i put this bracket around
9:26parallel omp pair
9:28parallel pragmatic parallel so here's
9:29this bracket around that
9:31and i brought the pi computation into
9:34that loop
9:36let's try it i'm so excited now be a
9:37little bit more efficient just that last
9:39group of four
9:40let's bring that in there what do i get
9:41okay so the summation is now inside the
9:43parallel section
9:44so there's not much speed up here right
9:46you're only speeding up for these four
9:47guys but what happens when i run this
9:533.1415926535897932
9:56uh oh 3.13 wait
10:00look i've got number of steps is a
10:01million wait wait i got a million
10:04i got a thousand threads here look a
10:05thousand threads so i added more threads
10:07here a lot more software threads that's
10:09different so i cranked that up
10:10i still got my million steps that's
10:12that's doing fine except do i do that a
10:14million
10:15then yeah that's like a hundred thousand
10:16steps it's a hundred thousand steps it's
10:18still pretty good
10:19but look at it behind what happened to
10:20pi
10:22that's that's crazy something went wrong
10:25here and what's even worse
10:27is the value changes between runs if i
10:30were to run this
10:3110 times like you saw before the value
10:33is going to change between runs
10:35what is the problem here well the
10:37problem somehow
10:38all the other thing i did differently
10:40was i added more threads that shouldn't
10:42be the problem
10:43change of steps down by factor 10 that
10:44shouldn't be the problem i brought the
10:46sum
10:47into the parallel part can you see why
10:49that's an issue
10:51what's going on
10:55this my friends is called a race
10:58condition
10:59and this is a big idea when you run in
11:01parallel where you run with the when you
11:03run with the parallel people
11:04having race conditions is something you
11:06have to really work hard to avoid
11:08because it's a way to have
11:10garbage values you're going to it's a
11:12way to have not just garbage value i
11:13mean this pie calculator is almost
11:14useless anymore right i was trying to do
11:16this so i can get a nice
11:17very very high resolution value of pi
11:20i'm not getting that at all and it's
11:22going to change between runs that you
11:24can't have that we can't have this is
11:25again
11:25pruning that non-determinism and one of
11:27the things is this race condition is the
11:29reason for that
11:31what if more than one thread grabs that
11:33so more than one thread grabs
11:35watches pi equals ply plus my sum of id
11:39so far so good that's so that's no
11:40problem so what's happening
11:42and this is at the end by the way that
11:43look all that main loop here's the main
11:45loop for for a hundred thousand here's
11:46the main loop on a thousand
11:47this is just a little bit here at the
11:50end where i have to now do this
11:51calculation
11:52uh at the end this
11:55this is problem because what happens at
11:57the end of all this is
11:58the day this is the work day this is the
12:00workday and now i'm at the point where
12:01all thousand people have to contribute
12:03their
12:04computation into the value of pi
12:08okay
12:11plus equals plus equal says pi equals pi
12:14plus
12:15there which means each what happens if
12:17two parallel threads
12:19grab the old value of pi
12:23they read they read they both grab the
12:25let's say the pi is pi is three let's
12:26just say pi
12:28now it's three okay i'm going to add my
12:30little fraction to that
12:33maybe both of us calculated point one
12:35right 0.05
12:37so 0.05.05.5 should be 3.1 at the end of
12:40the day right
12:40if here's pi at 3 and i calculate 0.05
12:43and you got 0.05 and we both calculate
12:45our piece to it
12:46so that should pi should be 3 plus 0.05
12:48plus 0.05
12:49is 3.1 okay and then there's more to get
12:52the four block etc
12:54so stay with me we both read three
12:58you can see this race can you see it
12:59happening i'm going to slow motion
13:01we both take r3 we both internally add
13:04our
13:05and we both now you write first that now
13:08three becomes 3.05
13:10and i write mine pi becomes now
13:133.05 we both wrote our 3.05 and it's not
13:16like we able to
13:17one of them was thrown away the first
13:18one was thrown away because this one
13:20was this could have been 3.06 right
13:22there and then 505 up it wrote over
13:24there
13:25trouble trouble trouble trouble trouble
13:27trouble
13:31the only way to deal with this is we got
13:32gotta we gotta figure out so that's the
13:34problem this is called a race condition
13:36this is a non-deterministic by the way
13:37this is through this this is when they
13:39were both the same what if one is
13:40bigger than smaller what if this is 0.06
13:42from 0.05
13:44here and here whoever writes last is
13:45going to be able to own that number and
13:47the other one is lost
13:48so it's not deterministic and i've lost
13:50values so this is really trouble
13:55we've got to figure out how to how to
13:56prune this so we're going to look at how
13:58to kind of
13:59lock the other people out of code that
14:01really should be sequential now we had a
14:03sequential at the end
14:04but we want to be able to do this in a
14:06clever way
14:07that we still get a little bit of
14:08parallelism but we gotta
14:10have a lock there's got to be a way to
14:11lock people out of this to be able to do
14:13this in a clever way
14:14okay so let's see if we can do this
14:18i still want to be able to imagine so i
14:19have a thousand threads i still want to
14:21be able to paralyze my
14:23contribution to pi but i want to do it
14:25in a way that
14:26makes sure that not two people aren't
14:28both trying to write to pi at the same
14:29time
14:30because if they're independent if a
14:31thousand people never happen to run it
14:33and override at the same time i'd be
14:34fine it'd be great and it'd be parallel
14:36each one is contributing their pi rather
14:37than having one serial guy at the end
14:39so i like that i want to get to that
14:40place but i need some help from software
14:42to support and prune that that race
14:44condition okay
14:45we'll see the next video

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 34.3 - Thread-Level Parallelism II: Computing Pi by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 3,111 words across 489 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.