Time versus Processors

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: The example of scheduling courses in terms is really a special case of a general problem that you can probably see of scheduling a bunch of tasks or jobs under constraints of which ones have to be done before other ones, which is a topic that comes up actually in lots of applications. But you can see applications in computer science where you might have a complex calculation, pieces of which could be done in parallel and other parts had to be done in order because later results depended on the results of an earlier computation.

It leads us to the general discussion of parallel scheduling.

And we've already worked out some theory of that really just from the example. Namely, if we look at the minimum number of terms to graduate, this corresponds to the minimum amount of number of stages or the minimum amount of time that it takes to process a bunch of tasks, assuming that you can do tasks in parallel and as many in parallel as you need to-- that there's no limit on the amount of parallelism allowed.

In that case, what we can say is that the minimum parallel time for a bunch of constrained tasks is simply the maximum chain size in the constraint graph.

We saw that example with the course prerequisites where we had five. And in general, this is the theorem. Minimum parallel time is exactly equal to maximum change size for chains in the graph that constrains the order in which tasks can be completed.

Now what about the maximum term load? Well, that corresponds to the number of processors you need to be doing tasks in parallel.

So for the course scheduling example, it means how many subjects can you take in one term? But if you were, say, doing computations, how many separate CPUs would you need in order to be able to fully utilize the parallelism to as much in parallel as you possibly could and abound on the number of processors that are needed for minimum time is simply the maximum antichain size, which in the example from the previous segment on course scheduling, it turns out there were five courses you could take in one term, the second term. And that was, in fact, the maximum antichain size.

So that's an upper bound on the number of processors that you need to achieve minimum time. But in fact, it's a course upper bound because although the number of processors needed to achieve minimum parallel time is at most the maximum antichain size. In fact, in the previous example, it turns out you could get away with three processors. It was possible to schedule the subjects so you only took three courses a term and still finished in minimum time.

So can you do better than three subjects? Well, there's a trivial argument that says, no, you can't. Because in that previous example, we had 13 subjects to schedule. The maximum chain size was 5. So it was going to take at least five terms.

So that means you have to distribute these 13 subjects among five terms. There has to be some term that has at least the average number of subjects, namely 13 divided by 5.

So that means there has to be a term in which you're taking 13 divided by 5 subjects. Of course, you round up because it has to be an integer.

So the minimum number of terms to finish and graduate-- finishing these 13 subjects in five terms-- is 3 because 13 divided by 5 rounded up is 3.

And this is a general phenomenon that applies. And what we can say is that if you have a DAG with n vertices and the maximum chain size is c-- so that's how deep it can be at most-- and the maximum antichain size is a-- that's the largest number of things that you could ever possibly do in parallel-- then clearly, the total number of vertices is c times a, at most.

So the total number of tasks that you can do where you are going to finish in c steps using at most a processors is bounded by c times a.

So what that tells you is that you can't both have the antichain size and the chain size be too small because their product has to be at least n.

That can be rephrased as a lemma that is credited to a guy named Dilworth. Dilworth is actually famous for Dilworth's theorem of which this Dilworth's lemma is a special case, but we don't need the general theorem.

Dilworth's lemma says that if you have an n-vertex DAG, then for any number t, it either has a chain of size bigger than t, or it has an antichain of size greater than or equal to n over t. And we proved this on the previous slide.

The product of these two things has to be at least n, and the general case is t times n over t is greater than or equal to n. And this holds for all t between 1 and n.

Well, let's think of a simple application of that. If I choose the t that balances antichain size from chain size, then I choose t to be the square root of n.

So over here, I have square root of n, and here I have n divided by the square root of n, which is also square root of n.

And what we can conclude is that every end vertex DAG has either a chain of size at least the square root of n or an anti chain of size at least square root of n.

This turns out to actually have a few applications, but we're just going to look at a fun application of this remark that you have to have a chain or an antichain of size at least square root of n.

You might have only one of these. You might have both. But one or the other has to be at least as big as square root of n.

Let's think of a new DAG that I'm going to construct as follows. I'm going to draw an edge between students in the class, and I'm going to think of one student as having a direct edge to another student if the first student is both shorter and younger-- actually meaning no taller than and no older than the other. Let's just say shorter-- meaning shorter or possibly the same height-- younger or possibly the same age.

And so the rule is if I think of a student as being represented by their shortness s and their age a, then a student with a height s 1 and age a 1 has a direct arrow to another student with height s 2 and age a 2, providing that the first pair is less than or equal to the second pair in both coordinates. S 1 is less than or equal to s 2. And A 1 is less than or equal to A 2.

Now, we don't want ties here because that would break the DAG property if I have two students with exactly the same age and height. So let's assume that we're measuring age in microseconds and the height in micrometers. And with that kind of a fineness, the likelihood of a tie is pretty low. So then it becomes a DAG again.

So this is the definition of taking a DAG built out of pairs-- there's a pure DAG for height, and there's a pure DAG for age. And I combine them into pairs, and I get a new DAG by looking at how the coordinates behave together.

This is called the product graph. It's a general construction that comes up, and we will talk a little bit more about when we reexamined DAGs in the context of the language of relations and partial orders.

Anyway, this is the product graph.

According to Dilworth's lemma, in a class like ours of 141 students, it means that we're going to have a chain or an antichain in this product DAG of size square root of 141 rounded up, or 12.

According to Dilworth's lemma, in this particular age-height graph, what does it mean for this to be an antichain? Suppose I take a bunch of students and I line them up in order of size with the tallest on the left and the shortest on the right.

If this is going to be an antichain, it means that they have to be getting older as they get shorter. Because if I ever had a case where somebody to the right was both shorter and younger than somebody to the left, it wouldn't be an antichain because they'd be comparable.

So an antichain-- according to Dilworth's lemma-- if you'd sort the students by height, they have to be getting older and as they get shorter. If it was a chain, they would be getting younger as they got shorter. But the more interesting one is the antichain in this height-birthday example.

So we should be looking at-- we'll either have a chain or an antichain in this class according to this product DAG.

As a matter of fact, we really had an antichain. Here's a quick list of a dozen students. And indeed, if you look at the birthdays, there's somebody who's 6'1 was born in August '94 and then somebody who was born in April '94 and is 6'0 all the way down to somebody who was born in 1991 and who's five feet tall.

So we lucked out. We could have only had to chain, but we actually had the antichain in this case.

Free Downloads

Video


Caption

  • English-US (SRT)