WEBVTT 1 00:00:00.200 --> 00:00:04.080 Welcome to this deep dive learner. Today we are well, 2 00:00:04.400 --> 00:00:07.960 we're entirely focused on a crisis that honestly almost broke 3 00:00:08.000 --> 00:00:08.720 the tech world. 4 00:00:08.839 --> 00:00:09.439 It really did. 5 00:00:09.679 --> 00:00:13.000 Yeah, because you know, when we think about human progress, 6 00:00:13.000 --> 00:00:17.440 we're usually talking about these like slow, steady increments. But 7 00:00:17.519 --> 00:00:20.280 for the first sixty years of the electronic computer era, 8 00:00:21.039 --> 00:00:25.679 computing performance per dollar didn't just crawl, it sprinted. We 9 00:00:25.719 --> 00:00:30.399 are talking about a fifty five percent increase every single year, which. 10 00:00:30.199 --> 00:00:33.880 Is just I mean over those decades, that compounded into 11 00:00:33.920 --> 00:00:37.399 a one hundred billion fold increase in performance. 12 00:00:37.479 --> 00:00:38.840 One hundred billion fold. 13 00:00:38.920 --> 00:00:41.679 Yeah, it is a staggering trajectory. Yeah, and the industry, 14 00:00:41.759 --> 00:00:43.600 you know, they just kind of assumed that line would 15 00:00:43.679 --> 00:00:46.280 keep going up forever just by making single processors run 16 00:00:46.320 --> 00:00:47.520 faster and faster, right. 17 00:00:47.399 --> 00:00:49.920 Like going from a slow walk to literal warp drive. 18 00:00:50.159 --> 00:00:52.880 But then right around the mid two thousands, this unstoppable 19 00:00:52.920 --> 00:00:56.600 bullet train violently hit what engineers call a power wall. 20 00:00:56.679 --> 00:00:57.799 Yeah, the power wall. 21 00:00:57.600 --> 00:01:00.000 Because the processors they literally could not dissipate the heat 22 00:01:00.000 --> 00:01:00.679 they were generating. 23 00:01:00.799 --> 00:01:04.319 I exactly, the physics simply wouldn't allow it. As engineers 24 00:01:04.359 --> 00:01:07.120 packed more and more transistors into these tighter spaces and 25 00:01:07.359 --> 00:01:11.799 cranked up the clock speed. The electrical resistance generated massive 26 00:01:11.799 --> 00:01:15.120 amounts of heat just burning up oh completely. If they 27 00:01:15.120 --> 00:01:18.200 pumped any more speed into those single chips, the silicon 28 00:01:18.280 --> 00:01:21.599 would quite literally melt. We were hitting the hard thermal 29 00:01:21.640 --> 00:01:23.400 limits of the materials we were using. 30 00:01:23.480 --> 00:01:27.159 Okay, let's unpack this, because how do you keep making 31 00:01:27.239 --> 00:01:31.079 computers faster? If you know, making the engine any faster 32 00:01:31.200 --> 00:01:34.640 turns it into a tiny, incredibly expensive space heater. 33 00:01:34.799 --> 00:01:36.120 Right, that's the big question. 34 00:01:35.920 --> 00:01:38.519 And that is our mission today. We are using Eric 35 00:01:38.560 --> 00:01:42.359 Abenell's really fascinating book Elements of Parallel Computing as our 36 00:01:42.680 --> 00:01:43.280 guide here. 37 00:01:43.400 --> 00:01:44.959 It's a great foundational text. 38 00:01:44.799 --> 00:01:46.280 It really is. So we are going to be your 39 00:01:46.280 --> 00:01:49.840 shortcut to understanding how the tech world by pass this 40 00:01:49.959 --> 00:01:53.799 melting point, the mental gymnastics required to program these new 41 00:01:53.840 --> 00:01:57.560 machines and the algorithms that quietly power everything from your 42 00:01:57.599 --> 00:02:00.599 social media feeds to global weathers emulations. 43 00:02:00.640 --> 00:02:00.840 Yeah. 44 00:02:01.159 --> 00:02:03.760 So, faced with this power wall, how did the hardware 45 00:02:03.799 --> 00:02:04.959 industry actually pivot? 46 00:02:05.200 --> 00:02:09.240 Well, their solution was deceptively simple. Really, Instead of trying 47 00:02:09.280 --> 00:02:13.280 to build one incredibly fast processor that would overheat, they 48 00:02:13.360 --> 00:02:17.319 fundamentally change the architecture Okay, they lowered the individual clock 49 00:02:17.360 --> 00:02:20.520 speeds to manage the heat. But they started putting multiple 50 00:02:20.520 --> 00:02:24.840 processors or cores onto a single chip. They basically multiply 51 00:02:24.960 --> 00:02:25.560 the number. 52 00:02:25.360 --> 00:02:28.479 Of workers, which means moving away from that classic model 53 00:02:28.520 --> 00:02:30.439 that the source calls the von Neumann. 54 00:02:30.120 --> 00:02:31.400 Architecture, right, exactly. 55 00:02:31.520 --> 00:02:35.800 Yeah, for anyone who isn't like a computer historian, what 56 00:02:35.879 --> 00:02:37.719 does that old model actually look like? 57 00:02:38.280 --> 00:02:41.520 So the vond Nomen architecture is essentially a sequential bottleneck. 58 00:02:41.879 --> 00:02:45.159 In this model, the computer memory and the processor take turns, 59 00:02:45.319 --> 00:02:48.560 just one by one. Right. The processor fetches one instruction, 60 00:02:48.840 --> 00:02:52.240 processes one piece of data, and writes it back. Albano 61 00:02:52.360 --> 00:02:57.000 refers to this as SISD, which stands for single instruction, single. 62 00:02:56.800 --> 00:02:58.520 Data, Single instruction, single data. 63 00:02:58.599 --> 00:03:01.479 Yeah. It executes one single stream of instructions on one 64 00:03:01.520 --> 00:03:04.879 single stream of data, step by painstaking step. 65 00:03:04.960 --> 00:03:08.039 Okay, I think an analogy might help visualize this. If 66 00:03:08.039 --> 00:03:13.039 we think of SSD, that single instruction single data model, 67 00:03:13.599 --> 00:03:17.080 it's like having one hypercaffeinated chef in a kitchen trying 68 00:03:17.120 --> 00:03:20.000 to cook a massive, I don't know, one hundred course 69 00:03:20.039 --> 00:03:22.400 meal entirely by themselves. 70 00:03:22.479 --> 00:03:23.919 That's a very stressful kitchen. 71 00:03:23.919 --> 00:03:26.840 Oh, absolutely, they chop one carrot, and they stir one pot, 72 00:03:26.919 --> 00:03:30.159 then they plate one dish. It doesn't matter how unbelievably 73 00:03:30.319 --> 00:03:33.680 fast their hands move. They are a bottleneck. 74 00:03:33.800 --> 00:03:36.680 They are. And this is where parallel formats stepped in 75 00:03:36.759 --> 00:03:40.039 to replace it as the dominant paradigm. The hardware industry 76 00:03:40.039 --> 00:03:43.879 moved to architectures like SIMD that single instruction, multiple data 77 00:03:43.919 --> 00:03:46.800 and MIMD multiple instruction multiple data. 78 00:03:46.879 --> 00:03:49.960 So in our pitchin analogy, a SIMD single instruction multiple 79 00:03:50.039 --> 00:03:52.840 data is like well, expanding the kitchen and hiring one 80 00:03:52.919 --> 00:03:53.639 hundred chefs. 81 00:03:53.719 --> 00:03:56.280 Yes, but they don't just cook whatever they want. Far 82 00:03:56.319 --> 00:03:59.319 from it. In a SIMD architecture, they all execute the 83 00:03:59.400 --> 00:04:02.240 exact same command at the exact same fraction of a 84 00:04:02.240 --> 00:04:05.639 second in perfect locksdawn like in armies. Exactly, the head 85 00:04:05.680 --> 00:04:10.080 chef yells chop and one hundred knives hit one hundred 86 00:04:10.080 --> 00:04:13.520 cutting boards simultaneously. They're all doing the same instruction, but 87 00:04:13.639 --> 00:04:16.160 on their own multiple pieces of data. 88 00:04:16.199 --> 00:04:19.680 That sounds incredibly efficient and maybe slightly terrifying. 89 00:04:19.279 --> 00:04:20.920 To watch, honestly a little bit. Yeah. 90 00:04:21.000 --> 00:04:24.600 The source actually highlights a historical machine that proved this 91 00:04:24.759 --> 00:04:27.800 wasn't just theoretical, right, A computer from the nineteen eighties 92 00:04:27.839 --> 00:04:29.680 that took this to the absolute extreme. 93 00:04:29.800 --> 00:04:33.160 Oh, the Connection Machine or CM one built by thinking machines. 94 00:04:33.560 --> 00:04:36.439 It wasn't just a technological marvel. It was designed as 95 00:04:36.639 --> 00:04:38.160 a literal work of art. 96 00:04:38.319 --> 00:04:38.560 Yeah. 97 00:04:38.639 --> 00:04:43.680 It was this massive SIMDI computer housing and unbelievable sixty 98 00:04:43.720 --> 00:04:46.279 five hundred and thirty six individual processors. 99 00:04:46.360 --> 00:04:48.000 Wait, sixty five thousand. 100 00:04:47.759 --> 00:04:50.279 Over sixty five thousand, that is wild. 101 00:04:50.439 --> 00:04:53.639 The text mentions that the artist Tommic Oo'tell actually designed 102 00:04:53.639 --> 00:04:55.199 its physical enclosure, right he did. 103 00:04:55.319 --> 00:04:55.600 Yeah. 104 00:04:55.759 --> 00:04:59.480 She collaborated with the legendary physicist Richard Feynman to build 105 00:04:59.560 --> 00:05:03.920 this trans parent cubic case with blinking red LEDs. It 106 00:05:03.959 --> 00:05:06.600 allowed you to physically see the data flowing and the 107 00:05:06.639 --> 00:05:08.480 processors thinking in real time. 108 00:05:08.959 --> 00:05:13.160 It was stunning, and Feineman's involvement was crucial there. He 109 00:05:13.319 --> 00:05:17.040 used the CM one to write a program solving quantum 110 00:05:17.160 --> 00:05:18.560 chromodynamics problems. 111 00:05:18.600 --> 00:05:20.879 Okay, let's define that really quickly for the listener. That's 112 00:05:20.920 --> 00:05:24.480 the physics of how fundamental particles like quarks and gluons 113 00:05:24.480 --> 00:05:26.399 interact to hold the universe together. 114 00:05:26.199 --> 00:05:30.240 Right, exactly that it is insanely complex math, right, And 115 00:05:30.240 --> 00:05:33.639 by running those physics simulations on the CM one. Fineman 116 00:05:33.800 --> 00:05:37.360 proved that this massive parallel architecture wasn't just you know, 117 00:05:37.800 --> 00:05:41.040 a toy for early artificial intelligence research. It was a 118 00:05:41.120 --> 00:05:43.680 powerhouse for hard scientific computation. 119 00:05:43.920 --> 00:05:47.199 But having a beautifully designed kitchen with sixty five thousand 120 00:05:47.279 --> 00:05:50.120 chefs all chopping in the lockstep brings up a massive problem. 121 00:05:50.439 --> 00:05:53.199 The hardware was clearly ready to handle the heat, but 122 00:05:53.360 --> 00:05:55.600 human programmers were completely unprepared for this. 123 00:05:55.800 --> 00:05:57.800 Oh, entirely unprepared. 124 00:05:57.360 --> 00:05:59.680 Because if your recipe is only written for one person, 125 00:06:00.120 --> 00:06:02.600 having all those extra shifts does absolutely nothing. 126 00:06:02.720 --> 00:06:05.360 That's exactly it. The hardware shift was really only half 127 00:06:05.360 --> 00:06:09.480 the battle. Parallel computing requires a fundamental shift in how 128 00:06:09.519 --> 00:06:13.680 we approach problem solving, and this is notoriously difficult for 129 00:06:13.720 --> 00:06:16.959 programmers because as humans, we are taught from day one 130 00:06:17.079 --> 00:06:20.399 to program sequentially. We write a line of code, tell 131 00:06:20.399 --> 00:06:22.439 the computer to finish it, and then move to the 132 00:06:22.439 --> 00:06:23.439 next line, which is. 133 00:06:23.399 --> 00:06:27.120 Deeply ironic because our own human brains are parallel processors, 134 00:06:27.120 --> 00:06:30.800 absolutely are. I mean, we are breathing pumping blood, processing 135 00:06:30.959 --> 00:06:34.160 visual data from the room around us, and interpreting audio 136 00:06:34.279 --> 00:06:36.480 from this deep dive, all at the exact same time. 137 00:06:36.959 --> 00:06:38.800 But the second we sit at a keyboard, we get 138 00:06:38.839 --> 00:06:39.519 tunnel vision. 139 00:06:39.639 --> 00:06:41.959 We do. And to break out of that tunnel vision, 140 00:06:42.319 --> 00:06:46.759 programmers have to adopt what educators call a threshold concept. 141 00:06:47.000 --> 00:06:47.959 That's threshold. 142 00:06:48.160 --> 00:06:52.240 Come yeah, It's a transformative, almost painful, new mental model 143 00:06:52.519 --> 00:06:56.759 of how instructions execute. You have to stop visualizing a single, 144 00:06:56.920 --> 00:06:59.959 top down list of commands and start visualizing a net 145 00:07:00.120 --> 00:07:04.240 work of interconnected events. Aubnell introduces this as the task 146 00:07:04.279 --> 00:07:04.879 graph model. 147 00:07:04.959 --> 00:07:07.360 Let's break down this task graph model. Because it sounds 148 00:07:07.399 --> 00:07:08.680 like drawing a massive blueprint. 149 00:07:08.720 --> 00:07:10.879 Think of it as a web. The points on the web, 150 00:07:11.240 --> 00:07:14.480 or the vertices are individual tasks like chop the carrot 151 00:07:14.720 --> 00:07:18.639 or boil the water. The lines connecting those points the edges, 152 00:07:19.079 --> 00:07:24.079 represent data dependencies. A data dependency means one task absolutely 153 00:07:24.120 --> 00:07:27.319 cannot start until another one finishes and hands over its result. 154 00:07:27.600 --> 00:07:30.240 So boiling water before you put the pasta in exactly. 155 00:07:30.399 --> 00:07:33.160 But the source makes a really specific distinction here though, 156 00:07:33.439 --> 00:07:37.600 it separates real data dependencies from false dependencies. Why does 157 00:07:37.639 --> 00:07:38.160 that matter? 158 00:07:38.480 --> 00:07:42.639 Well, a real data dependency is a physical reality. Task 159 00:07:42.759 --> 00:07:46.399 B physically needs the answer from task A to start. 160 00:07:47.040 --> 00:07:49.920 Like your pasta example, you cannot bake the cake until 161 00:07:49.959 --> 00:07:50.199 you have. 162 00:07:50.199 --> 00:07:52.279 Mixed the batter right physically impossible. 163 00:07:52.560 --> 00:07:55.240 But a false dependency, which computer scientists sometimes call an 164 00:07:55.240 --> 00:07:59.480 antidependence or an output dependence, is essentially an illusion created 165 00:07:59.519 --> 00:08:00.839 by slot be human. 166 00:08:00.600 --> 00:08:02.759 Habits how so sloppy? 167 00:08:02.800 --> 00:08:05.680 How Well. In the early days of programming, computer memory 168 00:08:05.759 --> 00:08:09.240 was incredibly limited, so programmers would constantly reuse the same 169 00:08:09.319 --> 00:08:12.839 variable names, like calling a piece of data x just 170 00:08:12.879 --> 00:08:13.639 to save space. 171 00:08:13.879 --> 00:08:14.480 Ah. 172 00:08:14.519 --> 00:08:17.240 So, task A and task B might have absolutely nothing 173 00:08:17.240 --> 00:08:20.360 to do with each other mathematically, but because the programmer 174 00:08:20.800 --> 00:08:24.000 reuse the variable X for both of them, the computer 175 00:08:24.120 --> 00:08:26.560 thinks they are fighting over the same sticky note. 176 00:08:26.720 --> 00:08:30.399 Oh, so you just give them different sticky notes exactly. 177 00:08:30.480 --> 00:08:32.960 You rename the variables, give them unique labels, and suddenly 178 00:08:33.000 --> 00:08:35.440 you realize these tasks can actually run at the exact 179 00:08:35.440 --> 00:08:38.200 same time precisely. But wait, let me push back on 180 00:08:38.240 --> 00:08:41.039 this on behalf of you listening right now. Compilers the 181 00:08:41.080 --> 00:08:44.919 software that translates our human code into machine code. They 182 00:08:44.919 --> 00:08:46.759 are incredibly advanced today. 183 00:08:47.080 --> 00:08:48.279 Very true, So why do. 184 00:08:48.240 --> 00:08:51.039 We even need to learn to think in task graphs? 185 00:08:51.320 --> 00:08:54.440 Can't we just write normal sequential code and let a 186 00:08:54.559 --> 00:08:58.519 super smart compiler automatically map out the dependencies and translate 187 00:08:58.519 --> 00:08:59.559 it into parallel code. 188 00:08:59.600 --> 00:09:02.600 For us, this raises an important question, and honestly, it's 189 00:09:02.639 --> 00:09:03.919 a very common misconception. 190 00:09:04.279 --> 00:09:04.639 Really. 191 00:09:04.840 --> 00:09:08.480 Yeah, compilers are brilliant at finding small efficiencies. They can 192 00:09:08.519 --> 00:09:11.039 look at a few lines of code and maybe execute 193 00:09:11.039 --> 00:09:16.759 a few independent mathematical operations simultaneously. But a compiler cannot 194 00:09:16.799 --> 00:09:20.200 fundamentally rewrite a sequential algorithm into a parallel one. 195 00:09:20.320 --> 00:09:23.240 So it can optimize, but it can't invent exactly. 196 00:09:23.440 --> 00:09:26.120 It cannot look at your step by step recipe and 197 00:09:26.200 --> 00:09:29.720 magically invent a completely new workflow for one hundred chefs 198 00:09:29.759 --> 00:09:33.080 to cook it simultaneously. If the underlying logical structure you 199 00:09:33.120 --> 00:09:36.879 designed a sequential, the execution will be sequential. The compiler 200 00:09:36.919 --> 00:09:38.279 can't save you. Wow. 201 00:09:38.399 --> 00:09:41.159 Okay, So if the compiler can't write the recipe for 202 00:09:41.200 --> 00:09:44.080 our hundred chefs, we have to look at the master 203 00:09:44.159 --> 00:09:47.519 blueprints ourselves. We have to learn how to design the 204 00:09:47.600 --> 00:09:48.960 kitchen workflow from scratch. 205 00:09:49.240 --> 00:09:53.159 We do, and that process begins with the art of decomposition. 206 00:09:53.240 --> 00:09:54.840 Decomposition, Yeah, how do you. 207 00:09:54.799 --> 00:09:58.600 Take a massive computational problem and shatter it into smaller pieces? 208 00:09:59.159 --> 00:10:02.399 Ibitil outline two golden rules for parallel algorithm design. 209 00:10:02.480 --> 00:10:03.519 Here, Okay, lay them on me. 210 00:10:03.639 --> 00:10:07.080 Rule number one postpone thinking about the physical hardware until 211 00:10:07.120 --> 00:10:08.559 after the decomposition phase. 212 00:10:08.639 --> 00:10:08.919 Okay. 213 00:10:09.159 --> 00:10:11.519 When you are mapping the workflow, do not worry about 214 00:10:11.559 --> 00:10:14.039 whether you have four cores or four thousand cores. 215 00:10:13.759 --> 00:10:16.360 Because you just want to design the most logically perfect 216 00:10:16.440 --> 00:10:19.559 workflow independent of the physical machine exactly. 217 00:10:20.039 --> 00:10:24.200 And rule number two follows that logic create many independent 218 00:10:24.279 --> 00:10:27.720 tasks that scale up with the problem size. You want 219 00:10:27.720 --> 00:10:31.399 to design as many tasks as possible that absolutely do 220 00:10:31.480 --> 00:10:32.840 not need to communicate with each. 221 00:10:32.720 --> 00:10:35.440 Other, which brings us to perhaps the most delightful term 222 00:10:35.480 --> 00:10:39.120 in all of computer science. Embarrassingly parallel. 223 00:10:39.240 --> 00:10:40.519 It's a great term, or. 224 00:10:40.759 --> 00:10:45.080 As it's sometimes more politely called in textbooks, obviously parallel. Right. 225 00:10:45.240 --> 00:10:49.519 It's an elegant structural pattern. In an embarrassingly parallel problem, 226 00:10:49.759 --> 00:10:52.519 the tasks require zero communication none. 227 00:10:52.639 --> 00:10:53.000 Okay. 228 00:10:53.240 --> 00:10:56.519 A classic example Abenell uses is the Monte Carlo estimation 229 00:10:56.600 --> 00:10:56.919 of pi. 230 00:10:57.240 --> 00:11:00.639 Oh. Let's visualize this. Imagine you have a square target 231 00:11:00.679 --> 00:11:03.960 on a wall and a circle drawn perfectly inside that square. 232 00:11:04.120 --> 00:11:06.279 You stand back and throw thousands of darts at it, 233 00:11:06.279 --> 00:11:07.840 completely randomly, right, and. 234 00:11:07.799 --> 00:11:09.759 If you know the total number of darts thrown, and 235 00:11:09.799 --> 00:11:12.279 you count how many landed inside the circle versus outside. 236 00:11:12.279 --> 00:11:14.279 In the corners of the square, you can use the 237 00:11:14.360 --> 00:11:16.879 ratio of those areas to calculate the value of pie. 238 00:11:17.720 --> 00:11:21.799 In a computer simulation, every single dart throne is an independent. 239 00:11:21.320 --> 00:11:23.799 Task because dart A doesn't need to know where dart 240 00:11:23.799 --> 00:11:25.440 be landed precisely. 241 00:11:25.799 --> 00:11:28.840 You can have a million processors throw a million darts 242 00:11:29.120 --> 00:11:32.240 at the exact same millisecond and it scales perfectly without 243 00:11:32.279 --> 00:11:33.559 them ever needing to talk. 244 00:11:33.720 --> 00:11:37.039 That's so clean. The source also BOMs up those mind 245 00:11:37.080 --> 00:11:41.559 bending infinite images generalized fractals like the Mandelbrot set. Yes, 246 00:11:41.720 --> 00:11:44.480 every single pixel you see on the screen is calculated 247 00:11:44.480 --> 00:11:48.879 completely independently based on its specific coordinates, but the tax 248 00:11:48.960 --> 00:11:51.879 points out a really specific challenge with fractals, right, it. 249 00:11:51.840 --> 00:11:55.600 Does the challenge of load imbalance. With fractals, the computer 250 00:11:55.679 --> 00:11:58.679 is running a mathematical function over and over for each 251 00:11:58.759 --> 00:12:01.759 pixel to see if the mask diverges, meaning it escapes 252 00:12:01.799 --> 00:12:04.440 to infinity. Okay, for the dark pixels you see in 253 00:12:04.480 --> 00:12:08.480 the image, the math diverges very quickly. The processor finishes 254 00:12:08.519 --> 00:12:11.240 the math and a split second. But for the white pixels, 255 00:12:11.399 --> 00:12:13.840 the computer might have to run the calculation the maximum 256 00:12:13.919 --> 00:12:16.840 number of times, say two hundred and fifty five iterations, 257 00:12:17.159 --> 00:12:19.159 before it finally gives up in colors it white. 258 00:12:19.200 --> 00:12:22.279 Oh here's where it gets really interesting. Think about this 259 00:12:22.320 --> 00:12:25.960 as an analogy learner. It's like a teacher handing out 260 00:12:25.960 --> 00:12:28.480 one hundred pop quizzes to one hundred students. 261 00:12:28.519 --> 00:12:29.240 Okay, I like this. 262 00:12:29.559 --> 00:12:32.480 It's embarrassingly parallel because the students don't need to talk 263 00:12:32.480 --> 00:12:34.919 to each other to finish their own quiz. But the 264 00:12:34.960 --> 00:12:38.240 fractal problem is like some students getting a short five 265 00:12:38.320 --> 00:12:41.840 question quiz while others get a brutal fifty question quiz. 266 00:12:41.960 --> 00:12:44.679 Exactly the ones with five questions finish in two minutes, 267 00:12:44.720 --> 00:12:46.600 and then they just sit there staring at the clock 268 00:12:46.679 --> 00:12:49.519 twiddling their thumbs while the other students are sweating for 269 00:12:49.559 --> 00:12:49.960 an hour. 270 00:12:50.600 --> 00:12:54.720 That is the perfect illustration of load imbalance. Even if 271 00:12:54.759 --> 00:12:57.679 tasks are independent, if they take vastly different amounts of 272 00:12:57.679 --> 00:13:01.879 time to complete, your overall ex acution time is bottlenecked 273 00:13:01.879 --> 00:13:03.000 by the slowest task. 274 00:13:03.159 --> 00:13:04.240 So how do you fix it? 275 00:13:04.600 --> 00:13:08.240 To fix it, programmers have to implement dynamic load balancing. 276 00:13:08.919 --> 00:13:11.279 As soon as the fast students finish, you hand the 277 00:13:11.360 --> 00:13:13.440 more questions from the slow students' piles. 278 00:13:13.679 --> 00:13:16.799 Got it, But let's be real. Not all problems are 279 00:13:16.840 --> 00:13:20.639 isolated pop quizzes. Most real world problems require the shefs 280 00:13:20.639 --> 00:13:24.080 to pass ingredients to one another. We can't avoid communication forever, 281 00:13:24.360 --> 00:13:25.240 we can't. 282 00:13:25.120 --> 00:13:27.960 Know, and that is where we enter the realm of 283 00:13:28.000 --> 00:13:33.639 advanced choreography. This is where programmers use ingenious computational patterns 284 00:13:34.080 --> 00:13:37.679 to force parallel execution out of problems that look stubbornly 285 00:13:37.960 --> 00:13:39.200 fundamentally sequential. 286 00:13:39.639 --> 00:13:42.159 So let's look at one of the most famous patterns, reduction, 287 00:13:42.440 --> 00:13:45.159 which is the backbone of the map reduced algorithm. 288 00:13:45.240 --> 00:13:48.840 Yeah, reduction is a brilliant way to handle massive data 289 00:13:48.879 --> 00:13:52.639 sets when you need to combine everything into a single summary, 290 00:13:53.120 --> 00:13:56.159 like adding millions of numbers together or finding a single 291 00:13:56.240 --> 00:14:00.320 maximum value. Instead of having one core pains to makingly 292 00:14:00.360 --> 00:14:03.720 add a million numbers one by one, use a binary tree. 293 00:14:03.559 --> 00:14:06.480 Structure to make that visual. It's basically a tournament bracket. 294 00:14:06.519 --> 00:14:08.240 That's a great way to ground it. If you have 295 00:14:08.279 --> 00:14:10.360 eight numbers to add, you don't do it sequentially. You 296 00:14:10.399 --> 00:14:14.120 pair them off. Four cores add four pairs simultaneously. Okay, 297 00:14:14.159 --> 00:14:16.600 now you have four numbers. Then two cores add those 298 00:14:16.600 --> 00:14:19.639 into two numbers. Then one final core adds the last 299 00:14:19.639 --> 00:14:20.519 two for the total. 300 00:14:20.639 --> 00:14:23.720 So you reduce the data set logarithmically, meaning the workload 301 00:14:23.759 --> 00:14:26.360 gets chopped in half at every single step, just like 302 00:14:26.399 --> 00:14:27.679 teams getting eliminated in the. 303 00:14:27.679 --> 00:14:31.559 Sports bracket exactly. The book uses the classic map reduced 304 00:14:31.559 --> 00:14:34.080 word count example to show this. If you want to 305 00:14:34.120 --> 00:14:36.440 count how many times the word parallel appears in an 306 00:14:36.559 --> 00:14:39.840 entire library of books, you first map the task. Okay, 307 00:14:40.000 --> 00:14:42.960 each processor independently counts the word in a single chapter, 308 00:14:43.399 --> 00:14:45.960 Then you reduce you some those partial counts up the 309 00:14:45.960 --> 00:14:49.200 tournament bracket until you get the grand total. Makes total sense, 310 00:14:49.480 --> 00:14:53.240 and it's also the underlying logic for algorithms like amins clustering, 311 00:14:53.480 --> 00:14:56.440 which data scientists use to group millions of similar data 312 00:14:56.440 --> 00:14:58.000 points by finding common centers. 313 00:14:58.200 --> 00:15:02.879 Okay, reduction makes intuitive. You're collapsing a tree. But the 314 00:15:02.919 --> 00:15:07.039 next pattern obnel discusses the scan or the prefix sum 315 00:15:07.200 --> 00:15:08.600 is where my brain starts to hurt. 316 00:15:08.480 --> 00:15:10.799 A little bit. Is definitely a cognitive leap. I'll give 317 00:15:10.840 --> 00:15:11.080 you that. 318 00:15:11.240 --> 00:15:15.600 The source uses image compression, specifically run length decoding to 319 00:15:15.639 --> 00:15:18.600 explain this. If an image is compressed, a line of 320 00:15:18.600 --> 00:15:21.360 pixels might be encoded as four W three B, meaning 321 00:15:21.519 --> 00:15:25.799 four white pixels followed by three black pixels. Expanding four 322 00:15:26.000 --> 00:15:29.159 W and three B independently is easy, But to put 323 00:15:29.200 --> 00:15:32.840 them into the final computer memory array, the core expanding 324 00:15:32.879 --> 00:15:35.279 the three B needs to know exactly where to put them. 325 00:15:35.720 --> 00:15:38.080 It needs a prefix sum of everything that came before 326 00:15:38.120 --> 00:15:39.720 it to know its starting position. 327 00:15:40.039 --> 00:15:42.320 Yes, it needs to know that four items came before it, 328 00:15:42.360 --> 00:15:44.879 so it should start dropping its black pixels and index four. 329 00:15:45.039 --> 00:15:45.279 Right. 330 00:15:45.759 --> 00:15:49.480 But if you have millions of these compressed segments, how 331 00:15:49.480 --> 00:15:53.919 do you calculate the running total for every single item simultaneously? 332 00:15:54.080 --> 00:15:57.000 Yes, that's exactly my question. Okay, I get how you 333 00:15:57.039 --> 00:15:59.320 can expand them in parallel, But in the prefix sum. 334 00:15:59.639 --> 00:16:01.720 If lam at number four relies on the sum of 335 00:16:01.759 --> 00:16:03.919 elements one to two and three, how on earth do 336 00:16:03.960 --> 00:16:06.360 you calculate element four at the exact same time as 337 00:16:06.399 --> 00:16:09.360 element two. It feels like you need time travel to 338 00:16:09.399 --> 00:16:10.360 know the future sum. 339 00:16:10.519 --> 00:16:13.840 It really feels like magic, but it is actually solved 340 00:16:13.960 --> 00:16:17.440 by Blellock's algorithm. Guy Block figured out that you can 341 00:16:17.559 --> 00:16:20.559 use a binary tree just like our tournament bracket, but 342 00:16:20.639 --> 00:16:21.720 you sweep through it twice. 343 00:16:21.799 --> 00:16:24.000 Sweeping through it twice how does that actually work. 344 00:16:24.320 --> 00:16:27.320 So first you do enough sweep, just like the reduction 345 00:16:27.399 --> 00:16:30.320 we talked about, pairs of numbers are added together, moving 346 00:16:30.399 --> 00:16:32.000 up the tree until you have the grand total at 347 00:16:32.039 --> 00:16:35.559 the top. Okay, But then Bellock's algorithm does a downsweep. 348 00:16:35.879 --> 00:16:38.919 It takes those partial sums and passes them back down 349 00:16:38.960 --> 00:16:41.759 the branches of the tree, swapping and adding values along 350 00:16:41.759 --> 00:16:42.080 the way. 351 00:16:42.200 --> 00:16:42.759 Oh wow. 352 00:16:42.879 --> 00:16:44.799 By the time the data hits the bottom leaves of 353 00:16:44.840 --> 00:16:48.840 the tree again, every single element instantly knows the sum 354 00:16:48.879 --> 00:16:50.200 of everything that came before it. 355 00:16:50.360 --> 00:16:53.320 That is just brilliant. It avoids everyone standing in a 356 00:16:53.320 --> 00:16:55.399 single file line waiting for the person in front of 357 00:16:55.440 --> 00:16:56.399 them to finish adding. 358 00:16:56.600 --> 00:17:01.360 It is a beautiful algorithmic ballet. We see similar choreography 359 00:17:01.360 --> 00:17:05.200 in pipelines, where data moves through specialized stages like an 360 00:17:05.240 --> 00:17:06.079 assembly line. 361 00:17:06.240 --> 00:17:09.039 Right, the source mentions pipelines being used in two D 362 00:17:09.200 --> 00:17:11.119 fast Fourier transforms. 363 00:17:10.599 --> 00:17:12.960 Yes, which is a mathematical way of taking an image 364 00:17:13.000 --> 00:17:16.680 and breaking it down into its core frequencies used constantly 365 00:17:16.720 --> 00:17:17.640 in image processing. 366 00:17:17.839 --> 00:17:17.960 UH. 367 00:17:18.200 --> 00:17:21.480 With a pipeline, processors can calculate all the rows of 368 00:17:21.519 --> 00:17:24.680 an image simultaneously, past the entire block to the next 369 00:17:24.720 --> 00:17:27.200 stage of the assembly line and then calculate all the 370 00:17:27.200 --> 00:17:28.319 columns simultaneously. 371 00:17:28.400 --> 00:17:32.759 And Aubinell also brings up cellular automata like Conway's Game 372 00:17:32.799 --> 00:17:33.400 of Life. 373 00:17:33.640 --> 00:17:36.640 Yeah, the mechanism there is fascinating. It's a massive grid 374 00:17:37.039 --> 00:17:39.480 of cells that live or die based on how many 375 00:17:39.519 --> 00:17:42.480 neighbors they have. Instead of a processor checking roll one 376 00:17:42.519 --> 00:17:46.039 than row two, you assign processors to sections of the grid. Okay, 377 00:17:46.200 --> 00:17:49.480 every single cell checks its neighbors and calculates its life 378 00:17:49.559 --> 00:17:52.839 or death status simultaneously in the exact same tick of 379 00:17:52.880 --> 00:17:56.480 the clock. We also see this decomposition using a technique 380 00:17:56.519 --> 00:18:00.759 cold pointer jumping to parallelize searching through linkedless of data. 381 00:18:00.839 --> 00:18:02.839 You know, I am just marveling at how pristine this 382 00:18:02.920 --> 00:18:08.759 choreography is Blollock's algorithm cellular automoto. It's mathematically perfect on paper, 383 00:18:08.839 --> 00:18:09.359 it is. 384 00:18:09.480 --> 00:18:12.119 But having a perfect blueprint on paper is very different 385 00:18:12.119 --> 00:18:13.000 from building a house. 386 00:18:13.160 --> 00:18:13.519 True. 387 00:18:13.599 --> 00:18:16.359 The reality is when that pristine task graph collides with 388 00:18:16.400 --> 00:18:21.079 the messy physical architecture of actual computer hardware, things get complicated. 389 00:18:21.279 --> 00:18:25.359 Ah right. The kitchen isn't an abstract mathematical space. It 390 00:18:25.400 --> 00:18:28.920 has walls, limited counterspace, and physical chefs who bump into 391 00:18:28.960 --> 00:18:30.039 each other and drop. 392 00:18:29.799 --> 00:18:34.240 Things exactly In a real computer, this beautiful choreography is 393 00:18:34.480 --> 00:18:38.839 constantly on the verge of total chaotic collapse, and managing 394 00:18:38.880 --> 00:18:42.519 that physical chaos is the true art of parallel. 395 00:18:42.039 --> 00:18:45.039 Programming, which brings us to the messiest parts of the kitchen. 396 00:18:45.480 --> 00:18:49.000 You mentioned load balancing earlier. How execution time is bottlenecked 397 00:18:49.000 --> 00:18:52.240 by the slowest core, But the source details even more 398 00:18:52.240 --> 00:18:55.480 insidious physical constraints, like the dreaded data. 399 00:18:55.279 --> 00:18:58.720 RaSE, oh, data races. They are the absolute nightmare of 400 00:18:58.720 --> 00:19:01.799 shared memory systems. Imagine you have thread zero and thread one. 401 00:19:01.920 --> 00:19:04.079