1 00:00:03,220 --> 00:00:05,832 Okay. So, we're, today, we're talking about 2 00:00:05,832 --> 00:00:10,208 parallelism and synchronization. from a parallel, parallelization 3 00:00:10,208 --> 00:00:15,106 perspective, we're worried here about parallel programming and how to build 4 00:00:15,106 --> 00:00:19,808 computer architectures that can run simultaneously multiple programs or 5 00:00:19,808 --> 00:00:25,367 multiple threads within one program. And today, we're going to talk about some 6 00:00:25,367 --> 00:00:30,687 models of that synchronization, and some primitives to help you solve it like 7 00:00:30,687 --> 00:00:33,680 synchronization primitives and memory fences. 8 00:00:36,040 --> 00:00:42,624 This is a little bit of background or motivation for nowadays why we're going 9 00:00:42,624 --> 00:00:47,664 to multiple processors. So, we're, show here Moore's Law plotted 10 00:00:47,664 --> 00:00:51,321 on a log plot. A number of transistors going up 11 00:00:51,321 --> 00:00:55,943 exponentially. Our sequential performance has sort of 12 00:00:55,943 --> 00:00:59,222 gone up, and then sort of stopped at this point. 13 00:00:59,222 --> 00:01:03,618 If you go look at the new core I7 or something like that, 14 00:01:03,618 --> 00:01:07,874 it's kind of flattened out here. It isn't continuing to go up. 15 00:01:07,874 --> 00:01:13,036 and in fact, the numbers that they actually publish for sequential SpecINT 16 00:01:13,036 --> 00:01:18,757 to our actually parallel numbers these days because they're using multiple cores 17 00:01:18,757 --> 00:01:22,525 to make SpecINT and SpecFP go a little bit faster. 18 00:01:22,525 --> 00:01:28,340 and, clock frequency has also found out we didn't get to our 10GHz processor. 19 00:01:29,580 --> 00:01:34,343 And largely, that it is due to us hitting some power challenges here. 20 00:01:34,343 --> 00:01:38,914 But it's also just incredibly hard to build and design these very high 21 00:01:38,914 --> 00:01:42,841 frequency processors. So, instead, we started to use these more 22 00:01:42,841 --> 00:01:45,996 and more transistors to implement multiple cores. 23 00:01:45,996 --> 00:01:50,631 So, we started off with two cores and then four cores and, you know, we've, 24 00:01:50,631 --> 00:01:52,433 we've gone up from there. Intel, 25 00:01:52,433 --> 00:01:57,742 I think, he is now selling an eight core part and a ten core part is coming out 26 00:01:57,742 --> 00:02:00,763 soon. AMD has a sixteen core part, but it is 27 00:02:00,763 --> 00:02:05,558 not a true sixteen core part. I think it is two eight cores that are 28 00:02:05,558 --> 00:02:10,262 glued together on a chip. and there's some other weirder stuff up 29 00:02:10,262 --> 00:02:12,969 here. Some actual many cores, multicore 30 00:02:12,969 --> 00:02:18,880 processors with more, more cores. But people did multiprocessor built 31 00:02:18,880 --> 00:02:22,655 multiprocessors before the multicore revolution here. 32 00:02:22,655 --> 00:02:26,430 Back in these days, there were multiprocessor systems. 33 00:02:26,430 --> 00:02:31,597 You could take multiple chips and put them together somehow into small systems 34 00:02:31,597 --> 00:02:36,026 or large systems. And for the rest, rest of class between 35 00:02:36,026 --> 00:02:40,456 now and the end of the term, we're going to be talking about parallel 36 00:02:40,456 --> 00:02:44,415 computing systems. Both systems that have multiple cores on 37 00:02:44,415 --> 00:02:50,245 one chip and multiple chips in a system. And for, there's some subtle differences 38 00:02:50,245 --> 00:02:53,360 between the two of those things, but a lot of commonality. 39 00:02:56,540 --> 00:03:06,867 In today's lecture, we're going to focus on symmetric multiprocessors and memory 40 00:03:06,867 --> 00:03:12,538 systems for sharing of data and using shared memory to share data. 41 00:03:12,538 --> 00:03:17,138 But there are other ways to share data and we're already touching on that in two 42 00:03:17,138 --> 00:03:20,390 lectures when we talk about messaging in more detail. 43 00:03:20,390 --> 00:03:25,481 The, I bring up symmetric multiprocessors because it's the simplest model to reason 44 00:03:25,481 --> 00:03:28,527 about. All processors are up here, and memory is 45 00:03:28,527 --> 00:03:31,923 down here. And let's assume there's no caches in the 46 00:03:31,923 --> 00:03:35,907 system to begin with. And everyone is equidistant from memory, 47 00:03:35,907 --> 00:03:39,891 and it's one big memory. And you've multiple processors, which 48 00:03:39,891 --> 00:03:45,431 could either be running multiple threads in one program or multiple programs. 49 00:03:45,431 --> 00:03:52,500 A couple other interesting things is, you know, 50 00:03:52,500 --> 00:03:57,728 these concurrency challenges don't come up just from having multiple processors. 51 00:03:57,728 --> 00:04:02,826 There are other things that can go and communicate with memory or communicate 52 00:04:02,826 --> 00:04:05,572 via memory. We have all these different IO 53 00:04:05,572 --> 00:04:10,604 controllers down here, network cards, disc controllers, graphics cards and they 54 00:04:10,604 --> 00:04:15,180 also want to read and write memory. So, in your memory system, even on a 55 00:04:15,180 --> 00:04:20,539 uniprocessor system, there are multiple agents that want to read and write memory 56 00:04:20,539 --> 00:04:24,942 simultaneously. [COUGH] Okay. So, let's talk about 57 00:04:24,942 --> 00:04:29,952 synchronization. The dining philosopher problem is an 58 00:04:29,952 --> 00:04:37,633 example of a synchronization challenge and we're going to talk about two major 59 00:04:37,633 --> 00:04:43,121 synchronization ideas but there are more than, are shown on the slide. 60 00:04:43,121 --> 00:04:49,274 mainly they're sort of broadcast models and, and other things like that. 61 00:04:49,274 --> 00:04:54,870 But for right now, when I say synchronization, it's some way to 62 00:04:54,870 --> 00:05:00,773 synchronize communication or arbitrate communication in a restricted fashion. 63 00:05:00,773 --> 00:05:06,523 So, we're going to have two here, we're going to talk about producer-consumer, 64 00:05:06,523 --> 00:05:12,886 that's the, the figure on the right here. A producer, as the name implies, produces 65 00:05:12,886 --> 00:05:16,490 some values. And a consumer, consumes the values. 66 00:05:16,490 --> 00:05:20,657 This is the most basic form here, one producer, one consumer. 67 00:05:20,657 --> 00:05:25,814 You could think about having one producer, multiple consumers or multiple 68 00:05:25,814 --> 00:05:30,335 producers, multiple consumers or multiple producers, one consumer. 69 00:05:30,335 --> 00:05:36,098 a lot of this same ideas hold here. So, that's, that's one model that people 70 00:05:36,098 --> 00:05:39,628 like to use. Another model that people like to use is 71 00:05:39,628 --> 00:05:44,891 there's some shared resource and you want to make sure that not more, let's say, 72 00:05:44,891 --> 00:05:48,888 then one processor is trying to access that shared resource. 73 00:05:48,888 --> 00:05:55,474 And this resource could either be a disk, a graphics card, or it could actually be 74 00:05:55,474 --> 00:06:00,272 a location in memory. And we're going to call this mutual 75 00:06:00,272 --> 00:06:04,182 exclusion. And the reason it's called mutual 76 00:06:04,182 --> 00:06:09,697 exclusion is it's exclusive, who can access the resource at one time. 77 00:06:09,697 --> 00:06:15,753 Now, the generalized form of this, that, that's the most basic form is only one 78 00:06:15,753 --> 00:06:20,673 processor or one entity can go and access the resource at a time. 79 00:06:20,673 --> 00:06:26,879 A more general form of it is some number of processors or resources can go access 80 00:06:26,879 --> 00:06:31,345 that at one time. And this is the more general semaphore 81 00:06:31,345 --> 00:06:35,660 question which we'll be talking about a little bit later. 82 00:06:36,700 --> 00:06:41,122 So, what I mean by that is, you could have P processors or let's say, P is 83 00:06:41,122 --> 00:06:43,887 twenty. And you could have a resource that no 84 00:06:43,887 --> 00:06:47,327 more than two processors can go access at the same time. 85 00:06:47,327 --> 00:06:50,337 You might say, well, why would you want to do that? 86 00:06:50,337 --> 00:06:54,944 Well, a good example is something like a network card that has two outbound 87 00:06:54,944 --> 00:06:58,077 queues, we'll say. So, you can actually have multiple 88 00:06:58,077 --> 00:07:01,087 processors using it, but if you try to have three processors 89 00:07:01,087 --> 00:07:04,404 use that one network card at the same time, 90 00:07:04,404 --> 00:07:09,011 well, there's only two outbound queues. It has to decide, somehow, to, to share 91 00:07:09,011 --> 00:07:12,060 those. so that's the example of a, of a true 92 00:07:12,060 --> 00:07:15,287 [UNKNOWN] versus just a mutex. Okay. 93 00:07:15,287 --> 00:07:19,945 So, let's go through some code examples here because these are going to be 94 00:07:19,945 --> 00:07:25,440 instructive and let's look at actually, before I do that 95 00:07:26,860 --> 00:07:32,920 you can even have on a uniprocessor system, synchronization challenges. 96 00:07:32,920 --> 00:07:36,792 And how is that possible? Well, as I said, even in the uniprocessor 97 00:07:36,792 --> 00:07:40,068 system, you sometimes have multiple concurrent entities. 98 00:07:40,068 --> 00:07:44,179 So, it's either your disk drive, doing DMA into memory at the same time as a 99 00:07:44,179 --> 00:07:47,455 process is trying to read from that block, for instance. 100 00:07:47,455 --> 00:07:52,400 And you need to guarantee, for instance, that this block is completely read before 101 00:07:52,400 --> 00:07:55,480 the processor goes and tries to read the block. 102 00:07:55,480 --> 00:07:59,239 That's one way that is going to happen in uniprocessor system. 103 00:07:59,239 --> 00:08:03,459 Another way that happen in a uniprocessor system, is uniprocessor systems can many 104 00:08:03,459 --> 00:08:07,295 times be multiprogrammed. So, the operating system would actually 105 00:08:07,295 --> 00:08:11,242 time slice between different programs. And you'll get interleaving of 106 00:08:11,242 --> 00:08:15,817 instructions in a preemptive environment at least of different processes at the 107 00:08:15,817 --> 00:08:18,448 same time. So, you might be running one process, 108 00:08:18,448 --> 00:08:21,079 the timer tick goes off. You stop that process. 109 00:08:21,079 --> 00:08:24,797 You switch to another process and start executing code from that. 110 00:08:24,797 --> 00:08:29,315 At some point, the timer tick goes off, and you switch back to the first process. 111 00:08:29,315 --> 00:08:34,700 So, even on the uniprocessor system, you can have synchronization challenges. 112 00:08:34,700 --> 00:08:37,496 Okay. So, let's, let's look at a 113 00:08:37,496 --> 00:08:46,616 producer-consumer example. Let's look at the abstract first. 114 00:08:46,616 --> 00:08:50,894 So, you have a producer here, a consumer there. 115 00:08:50,894 --> 00:08:58,896 We're going to use memory and one big symmetric block of memory for all of the 116 00:08:58,896 --> 00:09:05,267 communication at this point. We have a queue between the producer and 117 00:09:05,267 --> 00:09:09,851 the consumer shown here. And then, we have a head and a tail 118 00:09:09,851 --> 00:09:12,080 pointer. So, it's a FIFO says, where the, our 119 00:09:12,080 --> 00:09:13,429 first in, first out queue. 120 00:09:13,429 --> 00:09:17,769 I was going to say, where the head is, where the tail is, they can sort of move 121 00:09:17,769 --> 00:09:22,168 after each other and they'll say. it's circular so they wrap around at some 122 00:09:22,168 --> 00:09:28,959 point. [COUGH] You have a register value here on 123 00:09:28,959 --> 00:09:35,500 the producer and you can move the tail pointer into this register. 124 00:09:35,500 --> 00:09:38,760 And then, we have three registers over here. 125 00:09:38,760 --> 00:09:44,319 The tail pointer register, the head pointer register, and a register for the 126 00:09:44,319 --> 00:09:48,274 value we receive. And the reason I point out these 127 00:09:48,274 --> 00:09:52,335 different registers is just to show that the producer owns this register, and the 128 00:09:52,335 --> 00:09:55,845 consumer owns these three registers. And, as you can see here, this says, R 129 00:09:55,845 --> 00:09:58,854 tail and that says, R tail. So, they're going to have different 130 00:09:58,854 --> 00:10:02,113 copies of R tail and they could potentially get out of sync here. 131 00:10:02,113 --> 00:10:05,240 We're going see some, some fun hijinks happening. 132 00:10:05,240 --> 00:10:10,966 Okay. So, let's, let's look at the basic sequence of code here where the producer 133 00:10:10,966 --> 00:10:17,461 wants to put an item x into the cube for a consumer to read sometime in the 134 00:10:17,461 --> 00:10:22,401 future. First thing, it wants to do is it's going 135 00:10:22,401 --> 00:10:25,780 to read the tail pointer into its register. 136 00:10:26,880 --> 00:10:31,081 It's going to then, this is a, a load store architecture here. 137 00:10:31,081 --> 00:10:36,263 It's going to do a store of value x into the tail, which is going to put it here. 138 00:10:36,263 --> 00:10:38,924 Now, we're going to have to bump the tail. 139 00:10:38,924 --> 00:10:43,966 We can't do this atomically so we actually have to add one to it in our 140 00:10:43,966 --> 00:10:48,098 register space so we just increment it in our own register. 141 00:10:48,098 --> 00:10:52,580 And then, we're going to store this back into the pointer in memory. 142 00:10:54,120 --> 00:11:00,785 Seems simple enough. Let's look at what the consumer does. The 143 00:11:00,785 --> 00:11:08,415 consumer loads the head. And the first thing it's really going to 144 00:11:08,415 --> 00:11:11,560 do here is it's going to try to figure out if the head equals the tail. 145 00:11:11,560 --> 00:11:14,660 because that will mean that the queue is empty and it just needs to block. 146 00:11:15,980 --> 00:11:19,158 Loads the tail pointer. So, it's the head pointer in this 147 00:11:19,158 --> 00:11:23,560 register, a tail pointer in that register, and sees that they're equal. 148 00:11:23,560 --> 00:11:28,624 If they are equal, it's going to jump up here, reload the 149 00:11:28,624 --> 00:11:36,416 tail pointer into the tab to see if it's got updated by this thread and just spin 150 00:11:36,416 --> 00:11:42,661 here for forever until the tail pointer is not equal to head pointer, which means 151 00:11:42,661 --> 00:11:46,357 there's some data available. And then, we can fall through. 152 00:11:46,357 --> 00:11:50,962 And in the fall through case, we are going to load from the head into R, so 153 00:11:50,962 --> 00:11:55,120 into this register, this is, so we, we did the read. 154 00:11:55,120 --> 00:11:59,840 And we're going to update the head pointer to the next location. 155 00:11:59,840 --> 00:12:05,686 Save it off and then, do something on this value we got. 156 00:12:05,686 --> 00:12:15,809 So, processes just do, do something. So, this program is a little naive 157 00:12:15,809 --> 00:12:19,963 because we've been talking about out of order processors, 158 00:12:19,963 --> 00:12:23,514 we've been talking about out of order memory systems. 159 00:12:23,514 --> 00:12:27,669 And in a perfect world, this is assuming that instructions are 160 00:12:27,669 --> 00:12:33,029 executed in order and that there's no interleaving between the consumer and the 161 00:12:33,029 --> 00:12:36,800 producer here, and vice versa, in the memory system. 162 00:12:36,800 --> 00:12:39,960 So, anyone think there's any problems with this? 163 00:12:55,780 --> 00:13:00,582 does this work fine? Yup. Okay. So, you're, you're saying if 164 00:13:00,582 --> 00:13:07,013 the consumer runs before the producer does anything, you might just try to take 165 00:13:07,013 --> 00:13:11,104 values off the queue. Well, so let's guard against that and 166 00:13:11,104 --> 00:13:15,000 say, the, the start case is head pointer equals tail pointer. 167 00:13:15,000 --> 00:13:18,240 So, that won't happen, you'll sit spinning here. 168 00:13:20,020 --> 00:13:25,620 Now, because no one's like jumping up and screaming up and down at this point, 169 00:13:25,620 --> 00:13:29,629 you're sort of all assuming that these operations happen in order. 170 00:13:29,629 --> 00:13:34,308 But we've talked about out of order machines which reorder loads relative to 171 00:13:34,308 --> 00:13:37,103 stores. We've talked about very interesting 172 00:13:37,103 --> 00:13:40,262 interleaving. We've talked about out of order memory 173 00:13:40,262 --> 00:13:43,057 systems. So, so much for me jumping up and down 174 00:13:43,057 --> 00:13:47,492 here, and saying, what do we guarantee about loads and stores to different 175 00:13:47,492 --> 00:13:53,928 addresses? So, we said, all we know is that a load 176 00:13:53,928 --> 00:14:00,431 and a store or excuse me, a store and a load that are serialized in that order, 177 00:14:00,431 --> 00:14:04,861 on the same processor, to the same address, will happen in order. 178 00:14:04,861 --> 00:14:11,401 Our out of order super scale and our out of order memory systems, we've talked 179 00:14:11,401 --> 00:14:14,354 about, have defined nothing about ordering 180 00:14:14,354 --> 00:14:19,206 between processors or even memory operations inside of one processor. 181 00:14:19,206 --> 00:14:25,401 So, that's what we're really going to be talking about today, how to reorder those 182 00:14:25,401 --> 00:14:31,017 instructions and how to prevent that from causing havoc. 183 00:14:31,017 --> 00:14:38,306 Okay. So, let's, let's look at this and let's 184 00:14:38,306 --> 00:14:45,526 number these purple instructions. So, we're going to number store, store in 185 00:14:45,526 --> 00:14:48,293 these two loads. The reason we, we look at those, in 186 00:14:48,293 --> 00:14:52,720 particular, is this is basically updating state that this thread is reading from, 187 00:14:52,720 --> 00:14:57,203 and these are the two instructions that update that thread, and these are the two 188 00:14:57,203 --> 00:15:00,580 instructions that read that thread, or read that state rather. 189 00:15:03,660 --> 00:15:11,580 So, the programmer assumes that there's some level of causality, here. 190 00:15:11,580 --> 00:15:17,727 Incorrectly, producer is assuming, if you look at this 191 00:15:17,727 --> 00:15:27,460 code, that if three, this load happens after this store here, 192 00:15:27,460 --> 00:15:31,340 that there's some relation between one and four. 193 00:15:31,340 --> 00:15:36,280 Namely, that one has happened by the time four happens. 194 00:15:37,580 --> 00:15:40,729 Not a good assumption in our memory systems. 195 00:15:40,729 --> 00:15:44,236 And that's especially in our out-of-order memory system. 196 00:15:44,236 --> 00:15:48,953 Because, if we recall, out out of order memory system said 197 00:15:48,953 --> 00:15:55,832 nothing about store ordering. We talked about, the only thing we talked 198 00:15:55,832 --> 00:16:00,135 about was having a load at the same address as a store and not moving that 199 00:16:00,135 --> 00:16:04,190 load past that store. But otherwise, these two stores are out 200 00:16:04,190 --> 00:16:08,654 of order processor that can very easily reorder or an out of order memory system 201 00:16:08,654 --> 00:16:11,520 can very easily reorder. Likewise, over here, 202 00:16:11,520 --> 00:16:15,532 these are just two loads. These loads can happen completely out of 203 00:16:15,532 --> 00:16:20,297 order in an out of order computer, and out of our memory system. 204 00:16:20,297 --> 00:16:26,701 No guarantees there. So, this assumption is bad in a 205 00:16:26,701 --> 00:16:30,619 multiprocessor system. Uniprocessor system might make sense, 206 00:16:30,619 --> 00:16:37,634 multiprocessor system, bad assumption. So, let's look at some sequences that are 207 00:16:37,634 --> 00:16:42,077 problematic. Name, namely, let's say, two and then, 208 00:16:42,077 --> 00:16:46,611 three happens. And then, four and then one happens. 209 00:16:46,611 --> 00:16:51,887 So, what, what happens when that? Well, two updated the tail. 210 00:16:51,887 --> 00:16:56,700 Three says, raise the value of that new tail pointer. 211 00:16:57,820 --> 00:17:03,750 But at this point, we haven't actually stored the value into the cube because 212 00:17:03,750 --> 00:17:08,063 one never happened. We go x cubed four and it just reads 213 00:17:08,063 --> 00:17:13,066 garbage from memory. And then finally, the value gets updated. 214 00:17:13,066 --> 00:17:17,465 Totally valid in out of order, out of our memory systems that we talked about up to 215 00:17:17,465 --> 00:17:19,280 this point. Nothing wrong here. 216 00:17:19,280 --> 00:17:23,700 Okay, let's say, four and then one happen. 217 00:17:24,820 --> 00:17:26,887 So, goes the load. Load the head. 218 00:17:26,887 --> 00:17:31,090 Then, the value gets written. And then, two and then three happen. 219 00:17:31,090 --> 00:17:35,626 This is just completely out of order, kind of no good semantics here. 220 00:17:35,626 --> 00:17:40,629 So, this piece of code which looks like it should have, the programmer would 221 00:17:40,629 --> 00:17:45,098 assume to have good semantics. Basically, it has no, no useful semantics 222 00:17:45,098 --> 00:17:47,900 unless we define what those semantics are.