3 ms·
https://en.wikipedia.org/wiki/Dependency_graph https://en.wikipedia.org/wiki/Dependency_graph https://www.threadingbuildingblocks.org/docs/help/tbb_userguide/P
by 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).