Chapter 26: Parallel Algorithms: Fork-Join, Matrix Multiplication, and Merge Sort

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

All right, welcome back for another deep dive.

We're all about taking those really complex subjects, the ones you'd love to fully grasp, but just don't have the time to dig through endless research for and giving you those key insights you need.

Today, we're going to be looking at parallel algorithms and task scheduling, how they operate on multi -core computers, which, let's be real, are pretty much in everything we use these days.

Consider this your fast track to understanding how we get so much done so quickly with the computers we all rely on.

Exactly.

We're diving into a pretty comprehensive chapter today, all about parallel algorithms.

No need to wade through massive textbooks.

We'll handle that for you.

We're going to pull out those core ideas, really get at the heart of how computers manage to do multiple things all at the same time.

We'll make parallel computing crystal clear, maybe even spark some excitement about what's happening behind the scenes every time you use a device.

So parallel algorithms, that sounds like we're moving away from the one thing at a time way of thinking.

We're talking about doing lots of things all at once.

When did this shift from serial processing really become not just useful,

but essential?

Great question.

For quite a while, the focus was on making single processors faster.

It was like the driving force in computing, just keep pushing that speed limit.

But we ran into a wall, a physical limit.

When you get down to those tiny transistors, making them smaller and dealing with all the heat they generate, well, it just became a huge obstacle.

It wasn't feasible to making single processors exponentially faster anymore.

The real game changer, the way forward to get big performance gains was to have many processors working together.

And that's really the driving force behind the whole move to parallel algorithms.

And that's where multi -core architecture comes in, right?

We hear that term all the time.

So inside our devices, what does that look like?

Multi -core is everywhere these days.

Smartphones, laptops, those giant servers running the internet, they all have chips with multiple cores.

And these cores, they can all share the memory within that chip.

Now, you also have these bigger, more complex systems.

We call them distributed memory systems.

They've got multiple multi -core chips.

And each chip, it has its own separate memory.

So to get them talking to each other, it's a bit more involved, lots of message passing going on.

But for our deep dive today, we're going to stick with multi -core architectures.

They're the most common.

And honestly, they're just simpler to program for.

Simple always sounds good to me.

So parallel processing, doing these at the same time, sounds amazing for speed.

But I'm guessing there's a whole new level of complexity that comes with it.

You talked about thread parallelism earlier.

Can you remind us what that is and what makes it so tricky?

Right.

So thread parallelism is essentially a way to have multiple virtual processors, we call these threads.

And they're all working within that shared memory space we talked about.

Each thread's off doing its own thing, has its own little counter, keeping track where it is in the instructions.

The challenge is how do you split up the big task between all these threads?

You need to figure out how they'll communicate, coordinate, and most importantly, how to make sure they're sharing the workload evenly.

You don't want one thread overwhelmed while others are just sitting there.

Programming directly with threads, it can get messy, fast, lots of potential for errors.

Okay, so directly managing threads sounds a little bit like trying to conduct an orchestra of like 100 musicians all improvising at the same time.

So what's the solution?

You mentioned task parallel platforms.

How do they bring some order to this potential chaos?

Task parallel platforms, they provide a software layer above all those raw threads.

So instead of the programmer having to micromanage everything, creating threads, scheduling them, making sure they're talking to each other properly, you just focus on identifying bigger chunks of work.

These are your tasks and they can be executed in parallel.

The platform scheduler takes over, automatically assigning those tasks to the available processors.

It's what we call processor oblivious programming.

Processor oblivious.

Sounds pretty nice, to be honest.

So as a programmer, I just point out the parts of the problem that can be worked on simultaneously and the system takes care of the rest.

Exactly.

You concentrate on finding the inherent parallelism in the problem you're trying to solve.

The scheduler, that's the unsung hero handling all the low level details, making sure the work is distributed properly, running efficiently on the hardware.

This makes parallel programming much more manageable and it even allows us to use some fancy math like work and span analysis to kind of predict how well our parallel programs will do.

Work and span.

Those sound like pretty important concepts.

Definitely need to understand those better.

But first, let's really nail down this idea of task parallelism, specifically the fork joint model.

You said it's fundamental.

Can you explain why?

It absolutely is.

The fork joint model, it's kind of the bedrock for a lot of parallel programming systems.

It's all built around two key mechanisms,

spawning and parallel loops.

Spawning sounds kind of like creating something new, branching out.

What gets spawned exactly when we talk about parallel algorithms?

So when your program spawns a subroutine, it's like saying to the system, hey, this piece of code, it can run on its own.

It doesn't need to hold up everything else.

The main part of the program did the spawning, it just keeps going with its own instructions.

It doesn't have to wait for that spawn subroutine to wrap up.

Ah, okay.

So it's like delegating a task, right?

You've got a helper working on something while you keep moving forward.

What about those parallel loops?

We all know the regular for loops that go through each step one by one.

How do parallel loops work differently?

A parallel loop, it looks a lot like a standard for loop, but the big difference is that every iteration, each time that code inside the loop runs, they can all happen concurrently.

Like at the same time, maybe even on different processors.

So say I've got this loop that needs to do something a thousand times.

A parallel loop could, in theory, have many of those thousand operations going on simultaneously.

That could really speed things up.

Now, you mentioned programmers specify potential parallelism, not mandatory.

Why is that distinction important?

Really important point.

The programmer, they're pointing out where parallelism could happen.

Then it's up to the runtime system, the one managing all the threads, to actually make the it decides how and when to run those parallel parts based on the available processors and how busy things are at that moment.

This dynamic allocation, that's what allows for good load balancing.

The system can adapt to different hardware and workloads.

Got it.

So it's about flexibility.

The system can adjust on the fly.

This fork join model seems like a pretty elegant way to bring in parallelism.

What are some of the big advantages aside from, you know, running things faster?

Well, there are quite a few.

First, it's not a huge leap from traditional programming.

You don't need to completely rewire your brain to write these programs.

You often just add a few special keywords like parallel, spawn, sync, just little flags to tell the system where the parallelism is possible.

And what's really neat, you can often just take those keywords out and boom, you're back to the standard serial code.

It still solves the same problem.

It's called the serial projection of the parallel algorithm.

That's pretty cool, like a built -in backup plan.

Any other perks to using fork join?

Oh, definitely.

From a theoretical standpoint, it's very clean.

We can use some formal methods like that work and span analysis we'll talk about later to really measure how much parallelism is actually there in an algorithm.

Fork join also fits really well with those divide and conquer algorithms, you know, where you break a problem into smaller independent pieces, solve them all at the same time, and then put the results back together.

Think about things like sorting a list recursively or matrix multiplication.

And lastly, fork join is supported by a bunch of different programming environments and languages, Cilk, Habanero Java, the Java fork join framework, OpenMP, there are tons of them.

Okay, so we've got this model where tasks can be forked off and rejoined.

But how do we actually visualize or analyze the whole sequence of operations in a parallel program?

I imagine things can get pretty complicated to follow.

Right.

And that's where the idea of a parallel trace comes in.

It's often represented as a computation DAGI, which stands for directed acyclic graph.

Think of it like a flow chart for your parallel program's execution.

Each point in the graph that represents a bunch of instructions that run one after the other, no parallel stuff happening there, we call those sequences strands.

And the arrows between those points, the edges, those show how the strands depend on each other.

Strands.

Can you break that down a little more?

What makes up a strand exactly?

Picture an assembly line.

Each worker does a specific set of tasks without stopping to coordinate with others right then.

That uninterrupted sequence for one worker, that's like a strand.

It's a chunk of serial execution within the whole parallel program.

No spawning new tasks, no waiting for other tasks to finish syncing, no jumping to other parts of the code with function calls or returns.

Right.

So the strands are like the basic building blocks and those edges show how they all fit together.

What kinds of dependencies are those edges representing?

The edges are showing us control flow dependencies.

For instance, if a task calls a subroutine, there's a dependency edge from a strand in the calling task to the first strand of that subroutine.

And then another one going back from the last strand of the subroutine to the strand in the calling task that comes right after that call.

With spawn operations, there's an edge from the spawning strand to the first strand of the new child task so the child knows it can start.

At the same time, there's a continuation edge in the parent showing that it can also keep going.

Later, when the parent hits a sync point waiting for the child to finish up, there'll be an edge from the last strand of the child back to the strand in the parent that follows the sync.

Okay.

So those edges are kind of mapping out the flow of execution, right?

The order things need to happen in.

How does this graph tell us what parts of the program can really run in parallel?

Good question.

If you can follow a path between two strands in the DAG, that means they've got a dependency.

They have to happen in a specific order, either one right after the other or maybe with some overlap, depending on what kind of dependency it is.

Those strands are in series, but if there's no direct path between two strands, then they're independent.

They could run at the same time.

Those are in parallel.

The DAG, it's like a visual guide to the structure and the for parallelism in a program.

So when we analyze these parallel programs, what's the computer model we typically use?

For theoretical analysis, we often use what's called the ideal parallel computer.

It's a theoretical concept.

It has a certain number of processors, let's say dollars, and this thing called sequentially consistent shared memory.

Sequentially consistent.

That sounds important, but also a little bit technical.

What does that mean in simpler terms?

Sure.

Sequential consistency means that even though you've got multiple processors all trying to access the shared memory at the same time, the final result will be the same as if all those memory operations happened in a single global linear order, like everyone's politely taking turns.

Importantly, this global order has to respect the order each individual processor executed its own instructions.

So it's like there's an invisible traffic cop making sure all those memory requests are happening in a way that looks like everyone lined up, even though they all try to jump in at once.

Exactly.

That's a great way to put it.

And for our task parallel computations, that idea of a global order, it lines up with a topological sort of our day.

It's basically a valid way to arrange all the strands so that if strand A needs to happen before strand B, then A comes before B in the order.

Now, it's worth mentioning that lots of these analyses make some simplifying assumptions.

For example, they assume all processors have the same power and that scheduling tasks doesn't take any time.

Of course, the real world is a bit messier, but this ideal model, it gives us a solid starting point to understand the basics of performance.

Right.

So we've got this model in mind.

How do we actually measure how well a parallel algorithm is doing?

You mentioned work and span earlier.

Let's dig into those.

Okay.

So work, we represent that with TdalaWinner.

It's the total amount of computation the algorithm has to do.

It's basically the sum of the time it takes to run every single strand in our parallel trace.

Think of it like the time it would take to run the whole thing on a single processor, no parallelism.

That makes sense.

It's the total effort needed.

And then there's span, TdalaWinner.

That infinity symbol makes me think it's got something to do with having a ton of processors.

You got it.

Span, TdalaWinner, is the absolute fastest we could possibly run this algorithm if we had an unlimited number of processors.

It's all about the critical path and our diggy.

The critical path is the longest path through that graph from start to finish.

The span, that's the sum of the execution times for all the strands along that critical path.

It's the ultimate bottleneck, the sequential part of the algorithm.

We just can't escape no matter how many processors we have.

Okay.

So work is about the total computation and span is like the theoretical best case scenario, assuming unlimited resources.

But how do these two relate to performance in the real world where we have a limited number of processors, let's say $10?

That leads us to two really important principles in parallel computing,

the work law and the span law.

The work law says that the time it takes to run a parallel algorithm on Parbrice processors, we'll call that TP to a week, it has to be at least the total work divided by the number of processors, TPP, T1P or FI.

It's pretty intuitive.

If you have a certain amount of work to do, you can't finish it faster than if you perfectly divided it among all your processors.

Makes sense.

If a task needs 100 hours of computation, even with 10 processors working in perfect harmony, it'll take at least 10 hours.

Exactly.

Now, the span law, that one tells us the running time on parallel processors, 2PR shea, that also has to be at least as long as the span TPD, TFEP.

That's because even with a ton of processors, you still have to execute those operations on the critical path in order.

The length of that path, it sets a lower limit on So those two laws give us like a baseline, right?

A minimum time for our parallel algorithm, given a certain number of processors.

How do we actually measure the benefit of using multiple processors?

How much faster are things actually getting?

That's where we use speed up.

The speed up from using petal processors is basically the ratio of the work, the time on a single processor to the time on P dollar processors, TD dollar TPT.

It's a measure of how much faster things are running with multiple processors I also hear people talk about linear speed up and perfect linear speed up.

What's the difference?

Linear speed up?

That means the speed up is proportional to the number of processors we use.

In math terms, T dollar TP equals theta.

Perfect linear speed up.

That's the dream scenario.

The speed up is exactly equal to the number of processors.

T naught TP equals PT.

Great.

Meaning if you double the processors, you cut the execution time in half.

Perfectly.

That perfect scenario sounds great, but I'm guessing it's pretty rare in real world applications.

You're right.

It's tough to achieve.

There's almost always some overhead when you parallelize things like processors need to communicate, tasks need to be managed and scheduled.

That's where the concept of parallelism comes in.

Parallelism is defined as the ratio of work to span.

$200 today.

It's basically the average amount of work that can happen in parallel for every step along that critical path.

It also tells us the maximum possible speed up theoretically.

You'll never get a speed up higher than the parallelism of the algorithm, even with tons of processors.

If an algorithm has a parallelism of 10, you can't get a speed up of 12, even with a hundred processors.

So perfect linear speed up.

Generally, it's not going to happen if you have more processors than the parallelism of the algorithm.

Right.

There's a limit to how much faster we can make things by parallelizing.

Right.

You also mentioned parallel slackness.

What does that tell us?

Parallel slackness.

It's essentially a measure of how much potential we have compared to the number of processors we're actually using.

It's calculated as the parallelism divided by the number of processors.

T D and all T S P jot or two Donald T dollars.

If the slackness is a lot greater than one, it means we've got way more potential for parallel execution than we have processors to utilize.

And in these cases, a good scheduler can keep all those processors busy and we can get pretty close to that ideal linear speed up.

Okay.

So high parallel slackness.

That's a good thing.

It gives the system more room to work with, distribute tasks effectively.

Speaking of schedulers, you said they're pretty important.

What exactly are they doing and what makes a good scheduler?

The scheduler, that's the brain of the operation.

It takes the parallel tasks, those strands that are ready to go and assigns them to the available processors.

A really good scheduler is essential to actually see those performance gains that are promised by the algorithms work and span.

Now a common and effective type of scheduler is called a greedy scheduler.

They operate online, making decisions in real time as the computation is happening.

Their goal is pretty simple.

Keep as many processors busy as possible, working on those strands that are ready to execute, meaning all their dependencies have been met.

So maximizing processor utilization.

What are the different scenarios the scheduler might encounter in terms of ready tasks?

We have complete steps and incomplete steps.

A complete step.

That's when there are at least pottle dollar strands ready to go where the number of processors.

A greedy scheduler will just grab any dollars of those strands and assign them.

An incomplete step happens when there are fewer than Apollo ready strands.

In that case, the greedy scheduler assigns all the available strands, but some processors might end up idle for that step.

Sounds pretty straightforward, efficient.

Are there any guarantees about performance with this greedy strategy?

Absolutely.

There's a key result, often called theorem 26 .1, which states that for a task parallel computation with a total work of t tittle lullers and a span of team of five, a greedy scheduler running on pay processors will finish the whole thing in a time t pitter that is guaranteed to be no more than t teller p plus t town allure.

Okay, that seems like a pretty solid upper bound on the execution time.

What does it mean in practical terms?

It tells us that a greedy scheduler, it's not going to perform terribly compared to the theoretical best possible time, which we know is at least max t one p team five.

In fact, another result, sometimes called corollary 26 .2, proves that a greedy scheduler will always be within a factor of two of the optimal time, even compared to a perfect scheduler that knows the entire computation in advance.

And maybe the most interesting bit, corollary 26 .3, states that if we have a lot of parallel slackness, meaning the number of processors parallels is much smaller than the algorithm's parallelism t d dollar team 50, then the time t p t achieved by a greedy scheduler is going to be very close to ton of dollar, which is that near perfect linear speed up we were talking about earlier.

Wow.

So if the algorithm has a ton of potential for parallelism, and we use a smart, greedy scheduler, we can get really close to ideal speed up.

That's pretty powerful.

So how do we actually analyze a particular parallel algorithm to figure out its work and span?

Analyzing the work, it's usually pretty similar to analyzing the runtime of the regular serial version, you're basically just counting up all the operations.

Analyzing the span, that's where you have to think about the dependencies, usually by looking at the critical path in the DAG.

You need to understand how the spans of different parts of the algorithm combine.

Right.

How do they combine?

Are there like rules for calculating the work and span of operations that happen one after the other and operations that happen in parallel?

Yep, there are.

If you have two sub computations running sequentially, the total work is just the sum of work of each part.

The total span, same thing, you add the spans.

But if you've got two sub computations running in parallel, the total work is still the sum of the individual works, because you're doing both.

But the total span, that's the maximum of the two spans, which makes sense, right?

The whole parallel thing can't finish until the longest of those parallel parts is done.

Makes sense.

Those composition rules, they're essential for breaking down and analyzing those more complex parallel algorithms.

Can you give us a concrete example of how this work and span analysis plays out?

Sure.

A classic example is calculating the not Fibonacci number.

A basic recursive approach, it does a lot of redundant calculations.

The parallel version, we often call it PFIB, that uses the fork -join model.

It allows those two recursive calls in the Fibonacci calculation to happen in parallel.

When we analyze PFIB, the total work, tan as it being theta, where theta is the golden ratio, roughly 1 .618, it's the same work as the basic serial Fibonacci algorithm.

But the span of PFFI is much better, it's only the theta.

So even though the total computation is the same, the parallel version has a much faster best -case scenario with infinite processors.

What does that say about the potential speedup?

The parallelism of PFIB, that's its work divided by its span, TFIV and FFI.

And that ratio, it grows really fast as the Adels gets bigger, which means for larger values of one dollar, PFIB has a ton of potential for speedup, assuming we have enough processors.

It really shows how parallelization can make a huge difference for certain types of algorithms.

What about those parallel loops?

How do we analyze their work in span?

So parallel loops, they let the individual iterations run concurrently.

Compilers and runtime systems, they often implement parallel loops using something called recursive spawning.

It's like dividing the loop in half, and then each half is divided again and again.

It creates a sort of tree structure of parallel execution.

This recursive spawning, it does add some overhead, but it usually doesn't significantly change the total work of the loop.

The span of a parallel loop with null iterations, where each iteration of the algorithm has a span of either end of part, that often ends up being infida plus max one end part, that often comes from the depth of this recursive spawning tree.

So the span of a parallel loop depends on both the number of iterations and span of the slowest iteration.

Makes sense.

Now, with all this parallel programming, are there any common pitfalls to watch out for?

Definitely.

One of the big ones is race conditions and the whole issue of determinacy.

A deterministic parallel algorithm, that's one that always gives you the same output for the same input, no matter how the tasks are scheduled on the processors.

And what exactly is a determinacy race?

Sounds like something we want to avoid.

A determinacy race happens when two or more parallel instructions try to access the same spot in memory, and at least one of them is trying to write data there, trying to change the value.

Because the exact timing of those parallel instructions can vary, depending on the scheduler, the number of processors and other factors, a race condition can make your program behave unpredictably.

It might give you different results every time you run it, even with the same input.

This makes debugging a nightmare, because those errors, they come and go, making them super hard to track down.

Debugging already sounds like fun.

I can't imagine trying to track down an intermittent error like that.

How does sequential consistency play into these race conditions?

Sequential consistency gives us a nice, simple model of how shared memory should work in a parallel system.

But it doesn't stop race conditions from happening.

You see, sequential consistency allows for any valid order of instructions from different processors, as long as each processor's own instructions stay in the

memory location.

Some of those interleavings, they might work out fine, but others could lead to unexpected results.

That's how we get that unpredictable, non -deterministic behavior.

So how do we avoid these race conditions?

How do we make sure our parallel algorithms are deterministic and behave consistently?

The key is to make sure those parallel strands of execution don't interfere with each other.

This means either they work on completely separate parts of the memory, or if they do access the same locations, they're only reading, not writing.

No parallel strand should be trying to write to a memory location that another one is using at the same time.

With parallel loops, a common way to avoid races is to use index variables that are private to each iteration.

That way, different iterations are working on different chunks of data, no conflicts.

Keep those parallel parts isolated, working on their own stuff.

Good strategy.

Let's look at some specific algorithms.

You mentioned parallel matrix multiplication.

How do we approach parallelizing that?

There are a few ways to do it.

A pretty straightforward approach, often called P -matrix X -multiply, that directly parallelizes the outer two loops of the standard matrix multiplication algorithm, the one that takes theta and 3.

It has the same work as the serial version, theta and 3, but the span becomes theta and 3.

That gives us a parallelism of theta and 3, meaning there's a good chance for some speed up.

So just by parallelizing those outer loops, we could potentially see a quadratic speed up.

Are there even more advanced ways to parallelize matrix multiplication?

There are.

Another important one is P -matrix X -recursive.

It uses a divide and conquer strategy, recursively breaking down the matrices into smaller submatrices, and then using spawn to parallelize the multiplication of those subproblems.

This one often uses a temporary matrix to help avoid those race conditions.

While it still has total work of $1, n, 3, and 3, its span gets a lot better.

That leads to higher parallelism, theta, n, 3, and 3.

And even fancier serial algorithms, like Strassen's method, which takes theta times serially, those can also be parallelized using similar spawning techniques.

You end up with work of theta n and a span of the theta n giving a parallelism of thetas.

So we can apply parallelization at different levels of the algorithm, and it really impacts the work and span.

Let's move on to another classic algorithm, merge sort.

How does parallelization affect that?

Well, if you naively try to parallelize merge sort, let's call it P -N -A -E merge sort, you might just parallelize the two recursive calls that split the list in half, but you'd still use the regular serial merge to combine the sorted sublists.

The work would stay the same as the serial version, T2 on n, but the span would be pretty high.

That gives us low parallelism.

Only theta, that serial merge step, it becomes a bottleneck.

So if the combine step is still sequential, just parallelizing the divide step isn't enough.

How do we improve the parallel performance of merge sort?

The key is to parallelize the merging, too.

That's what a more sophisticated parallel merge sort does.

We usually call it P -merge sort.

The P -merge algorithm itself usually uses a recursive helper procedure, maybe called P -merge O -U -X, which merges two sorted subarrays in parallel.

It works by finding a pivot element in one subarray, then finding where it belongs in the other subarray using a binary search.

Then it breaks the merge down into two smaller parallel merge subproblems.

P -merge O -U -X, it has a work of theta and a span of theta lg n, so the whole P -merge sort algorithm ends up with work theta n2 n and a much better span.

That gives us much higher parallelism theta n2 3.

That's a big jump in parallelism just by parallelizing the merge step.

Really shows how important it is to find those bottlenecks.

I saw at the end of this chapter summary there's a glossary of terms.

Seems like it covers a lot of what we talked about today.

Yes, that glossary has definitions for a lot of the terms we've covered.

Things like critical path, determinacy race,

fork -join parallelism, greedy scheduler, span, work, and many others.

If anything we've talked about today felt a bit overwhelming or you just want to revisit a definition, definitely take a look at that glossary.

It's a great resource to really solidify these ideas.

Always helpful they have a good reference.

Well, we've covered a lot in this deep dive into parallel algorithms and task scheduling.

Before we wrap up, let's recap the main takeaways.

To sum it up, we saw how parallel algorithms use task parallelism to harness the power of those multi -core architectures.

The fork -join model, that's a really important and common approach.

We learned about work, T -Login 1 -1, and span.

Those are essential metrics for analyzing how well a parallel algorithm might perform, understanding its potential for parallelism, and the theoretical limits on speedup.

We also learned that good scheduling, often using greedy schedulers, that's crucial to actually get those performance benefits.

And finally, we touched on those race conditions and how important it is to ensure determinacy in parallel programs so they produce correct and reliable results.

And for you, our listener, I hope this deep dive gave you a good foundation to understand the core principles behind parallel algorithms.

You should have a much better grasp on how modern computing gets so much done so quickly, all thanks to the power of parallel processing.

One last thought to ponder.

We've been talking about how fork -join parallelism and task scheduling are used in computer science to break down computational problems.

But could we apply these same ideas to other complex systems in the real world?

Think about large organizations coordinating on a project, or even biological systems, with lots of processes happening at the same time.

What would be the spawns and sinks in those situations?

Could we analyze their work and span to figure out how efficiently they're working and maybe identify any bottlenecks?

That's a fascinating question, something to really think about.

If this has sparked your curiosity, definitely explore those specific parallel algorithms, learn more about parallel programming techniques, or even delve into the world of task scheduling.

There's a ton to discover.

Thanks for joining us on this deep dive.