4 ms·

Googling "dependency cutting" does not find me any informative pages about this. Is there another term? Or do you have a link to a page where I can read about

• dragontamer 6y ago
  https://en.wikipedia.org/wiki/Dependency_graph https://en.wikipedia.org/wiki/Dependency_graph https://www.threadingbuildingblocks.org/docs/help/tbb_userguide/Parallelizing_Flow_Graph.html https://www.threadingbuildingblocks.org/docs/help/tbb_usergu... If you can imagine: there is a dependency graph of operations. Lets take a simple example: 1: mov rax, [someValueInMemory] 2: mov rbx, [OtherValue] 3: add rax, rbx 4: add rax, 5 5: add rax, 10 The above has the following dependency graph: 5 -> 4 -> 3 -> 2 -> 1 No instruction level parallelism is available at all. No modern CPU can parallelize it, if an 8-way decoder read all 5 instructions, it'd have to all go into the reorder buffer (but ultimately still execute sequentially). Now lets cut some dependencies, and execute the following instead: 1: mov rax, [someValueInMemory] 2: mov rbx, [OtherValue] 3: add rax, 5 4: add rbx, 10 5: add rax, rbx The graph is now the following: 5 -> 4 -> 2 5 -> 3 -> 1 A modern CPU will decode all of the instructions rather quickly, and come up with the following plan: ClockTick1: Execute 1 and 2 ClockTick2: Execute 3 and 4 ClockTick3: Execute 5 The dependency chain has been cut to only length 3, which means the 5-instructions can now execute in 3 clock cycles (instead of 5-cycles, like the original instructions).