Placeholder Image

字幕列表 影片播放

  • The following content is provided under a Creative

  • Commons license.

  • Your support will help MIT OpenCourseWare

  • continue to offer high-quality educational resources for free.

  • To make a donation or to view additional materials

  • from hundreds of MIT courses, visit MIT OpenCourseWare

  • at ocw.mit.edu.

  • JULIAN SHUN: Good afternoon, everyone.

  • So let's get started.

  • So today, we're going to be talking

  • about races and parallelism.

  • And you'll be doing a lot of parallel programming

  • for the next homework assignment and project.

  • One thing I want to point out is that it's important

  • to meet with your MITPOSSE as soon as possible,

  • if you haven't done so already, since that's

  • going to be part of the evaluation for the Project 1

  • grade.

  • And if you have trouble reaching your MITPOSSE members,

  • please contact your TA and also make a post on Piazza

  • as soon as possible.

  • So as a reminder, let's look at the basics of Cilk.

  • So we have cilk_spawn and cilk_sync statements.

  • In Cilk, this was the code that we

  • saw in last lecture, which computes the nth Fibonacci

  • number.

  • So when we say cilk_spawn, it means

  • that the named child function, the function right

  • after the cilk_spawn keyword, can execute in parallel

  • with the parent caller.

  • So it says that fib of n minus 1 can

  • execute in parallel with the fib function that called it.

  • And then cilk_sync says that control cannot pass this point

  • until all of this spawned children have returned.

  • So this is going to wait for fib of n minus 1

  • to finish before it goes on and returns the sum of x and y.

  • And recall that the Cilk keywords grant permission

  • for parallel execution, but they don't actually

  • force parallel execution.

  • So this code here says that we can execute fib of n minus 1

  • in parallel with this parent caller,

  • but it doesn't say that we necessarily have

  • to execute them in parallel.

  • And it's up to the runtime system

  • to decide whether these different functions will

  • be executed in parallel.

  • We'll talk more about the runtime system today.

  • And also, we talked about this example,

  • where we wanted to do an in-place matrix transpose.

  • And this used the cilk_for keyword.

  • And this says that we can execute

  • the iterations of this cilk_for loop in parallel.

  • And again, this says that the runtime system

  • is allowed to schedule these iterations in parallel,

  • but doesn't necessarily say that they

  • have to execute in parallel.

  • And under the hood, cilk_for statements

  • are translated into nested cilk_spawn and cilk_sync calls.

  • So the compiler is going to divide the iteration

  • space in half, do a cilk_spawn on one of the two halves,

  • call the other half, and then this

  • is done recursively until we reach

  • a certain size for the number of iterations

  • in a loop, at which point it just

  • creates a single task for that.

  • So any questions on the Cilk constructs?

  • Yes?

  • AUDIENCE: Is Cilk smart enough to recognize issues

  • with reading and writing for matrix transpose?

  • JULIAN SHUN: So it's actually not

  • going to figure out whether the iterations are

  • independent for you.

  • The programmer actually has to reason about that.

  • But Cilk does have a nice tool, which we'll talk about,

  • that will tell you which places your code might possibly

  • be reading and writing the same memory location,

  • and that allows you to localize any possible race

  • bugs in your code.

  • So we'll actually talk about races.

  • But if you just compile this code,

  • Cilk isn't going to know whether the iterations are independent.

  • So determinacy races-- so race conditions

  • are the bane of concurrency.

  • So you don't want to have race conditions in your code.

  • And there are these two famous race bugs that cause disaster.

  • So there is this Therac-25 radiation therapy machine,

  • and there was a race condition in the software.

  • And this led to three people being killed

  • and many more being seriously injured.

  • The North American blackout of 2003

  • was also caused by a race bug in the software,

  • and this left 50 million people without power.

  • So these are very bad.

  • And they're notoriously difficult to discover

  • by conventional testing.

  • So race bugs aren't going to appear every time

  • you execute your program.

  • And in fact, the hardest ones to find, which cause these events,

  • are actually very rare events.

  • So most of the times when you run your program,

  • you're not going to see the race bug.

  • Only very rarely will you see it.

  • So this makes it very hard to find these race bugs.

  • And furthermore, when you see a race bug,

  • it doesn't necessarily always happen

  • in the same place in your code.

  • So that makes it even harder.

  • So what is a race?

  • So a determinacy race is one of the most basic forms of races.

  • And a determinacy race occurs when

  • two logically parallel instructions

  • access the same memory location, and at least one

  • of these instructions performs a write to that location.

  • So let's look at a simple example.

  • So in this code here, I'm first setting x equal to 0.

  • And then I have a cilk_for loop with two iterations,

  • and each of the two iterations are

  • incrementing this variable x.

  • And then at the end, I'm going to assert that x is equal to 2.

  • So there's actually a race in this program here.

  • So in order to understand where the race occurs,

  • let's look at the execution graph here.

  • So I'm going to label each of these statements with a letter.

  • The first statement, a, is just setting x equal to 0.

  • And then after that, we're actually

  • going to have two parallel paths, because we

  • have two iterations of this cilk_for loop, which

  • can execute in parallel.

  • And each of these paths are going to increment x by 1.

  • And then finally, we're going to assert that x is equal to 2

  • at the end.

  • And this sort of graph is known as a dependency graph.

  • It tells you what instructions have

  • to finish before you execute the next instruction.

  • So here it says that B and C must

  • wait for A to execute before they proceed,

  • but B and C can actually happen in parallel, because there

  • is no dependency among them.

  • And then D has to happen after B and C finish.

  • So to understand why there's a race bug here,

  • we actually need to take a closer look

  • at this dependency graph.

  • So let's take a closer look.

  • So when you run this code, x plus plus

  • is actually going to be translated into three steps.

  • So first, we're going to load the value

  • of x into some processor's register, r1.

  • And then we're going to increment r1,

  • and then we're going to set x equal to the result of r1.

  • And the same thing for r2.

  • We're going to load x into register r2, increment r2,

  • and then set x equal to r2.

  • So here, we have a race, because both of these stores,

  • x1 equal to r1 and x2 equal to r2,

  • are actually writing to the same memory location.

  • So let's look at one possible execution of this computation

  • graph.

  • And we're going to keep track of the values of x, r1 and r2.

  • So the first instruction we're going to execute

  • is x equal to 0.

  • So we just set x equal to 0, and everything's good so far.

  • And then next, we can actually pick one of two instructions

  • to execute, because both of these two instructions

  • have their predecessors satisfied already.

  • Their predecessors have already executed.

  • So let's say I pick r1 equal to x to execute.

  • And this is going to place the value 0 into register r1.

  • Now I'm going to increment r1, so this

  • changes the value in r1 to 1.

  • Then now, let's say I execute r2 equal to x.

  • So that's going to read x, which has a value of 0.