4 ms·

It really seems like Intel is designing this chip to support a very specific workload, when it would have been a better use of everyone's time and money to just

It really seems like Intel is designing this chip to support a very specific workload, when it would have been a better use of everyone's time and money to just rewrite the workload to work well on normal chips...

wmf 3y ago
That graph workload fundamentally cannot work well on normal chips.
- londons_explore 3y ago
  Citation needed. Huge sparse graphs can be processed fairly efficiently on both CPU's and GPU's, but the code has to be written with the architecture in mind.
  - yvdriess 3y ago
    Their inefficiency at large-scale graph problems is the entire reason DARPA wrote out the program that funded this chip.
    - danbruc 3y ago
      I have no expertise in this area, but I think the presentation explains the issue quite well. The workloads they consider have a large number of indirection and poor memory locality, so a lot of memory operations have to wait for cache misses, but you have to do the same thing a lot of times independently with different data. Normal multithreading is not a solution because it is not granular enough, you can not context switch in the middle of each memory access to run a different thread while waiting for the memory access to complete. You could manually unroll loops and instead of only following one path through the graph you could follow several paths at the same time by interleaving their operations. While this will be able to hide the waiting times because you can continue working on other paths, it will make your code more complex and increase register pressure as you still have the same number of registers but are operating on multiple independent paths. Letting the hardware interleave many parallel paths will keep your code simpler and as each thread has its own registers also not increase register pressure.
      - londons_explore 3y ago
        The solution is SIMD with a queue of 'to be processed' nodes, and a SIMD program that grabs 32 nodes at once from the queue, processes them all in parallel, and adds any new nodes to process to the end of the queue. There is then plenty of parallelism, great branch predictor behaviour, and the length of the queue ensures that blocking on memory reads pretty much never happens. Downside: Your business logic of what to do with every node needs to be written in SIMD intrinsics. But that has to be cheaper to do than asking Intel to design a new CPU for you.
        danbruc 3y ago
        Does this actually help? I don't know much about microarchitectural details, so I may be completely wrong. Let's take a simple example, I have some nodes and want to load a field and then do some calculations with the value. I load the pointers of 32 nodes into a SIMD register and issue a gather instruction, I get 32 cache misses. Now it seems to me there is nothing I can do but wait. I can not put this work item back into the queue in the middle of a memory access but even if I could, the overhead seems completely prohibitive to get things out and put them back into queues every other instruction or so. But with hundreds of hardware threads I could just continue executing some other thread that already got his pointer dereferenced. SIMD is great when you can issue loads and they all get satisfied with the same cache line, but if you have to gather data, then values will arrive one after another and you can not do any dependent work until the last one arrived. I guess the whole point is that all the threads can be at slightly different execution points, while some are waiting for reads to complete others can continue working after their read completed without having to wait for an entire group of reads to complete.
        yvdriess 3y ago
        Correct. This is also why hyperthreading yields a benefit for sparse/graph workloads. I was getting good results on the KNL Xeon Phi with its four hyperthreads. But you easily hit the 'outstanding loads' limit if your hyperthreads all do gather instructions every 4-8 instructions. The architecture needs to balanced around it.
- jandrewrogers 3y ago
  Graph workloads can work well on normal chips but you really have to know what you are doing. Clever algorithms that demonstrated graphs workloads could be efficiently run on CPUs was a major contributor to the demise of barrel processing research, since a lot of the interest in those architectures was for the purposes of efficient graph analysis. Given the option, economics heavily favors commodity silicon.

wmf 3y ago

That graph workload fundamentally cannot work well on normal chips.

londons_explore 3y ago
Citation needed. Huge sparse graphs can be processed fairly efficiently on both CPU's and GPU's, but the code has to be written with the architecture in mind.
- yvdriess 3y ago
  Their inefficiency at large-scale graph problems is the entire reason DARPA wrote out the program that funded this chip.
  - danbruc 3y ago
    I have no expertise in this area, but I think the presentation explains the issue quite well. The workloads they consider have a large number of indirection and poor memory locality, so a lot of memory operations have to wait for cache misses, but you have to do the same thing a lot of times independently with different data. Normal multithreading is not a solution because it is not granular enough, you can not context switch in the middle of each memory access to run a different thread while waiting for the memory access to complete. You could manually unroll loops and instead of only following one path through the graph you could follow several paths at the same time by interleaving their operations. While this will be able to hide the waiting times because you can continue working on other paths, it will make your code more complex and increase register pressure as you still have the same number of registers but are operating on multiple independent paths. Letting the hardware interleave many parallel paths will keep your code simpler and as each thread has its own registers also not increase register pressure.
    - londons_explore 3y ago
      The solution is SIMD with a queue of 'to be processed' nodes, and a SIMD program that grabs 32 nodes at once from the queue, processes them all in parallel, and adds any new nodes to process to the end of the queue. There is then plenty of parallelism, great branch predictor behaviour, and the length of the queue ensures that blocking on memory reads pretty much never happens. Downside: Your business logic of what to do with every node needs to be written in SIMD intrinsics. But that has to be cheaper to do than asking Intel to design a new CPU for you.
      - danbruc 3y ago
        Does this actually help? I don't know much about microarchitectural details, so I may be completely wrong. Let's take a simple example, I have some nodes and want to load a field and then do some calculations with the value. I load the pointers of 32 nodes into a SIMD register and issue a gather instruction, I get 32 cache misses. Now it seems to me there is nothing I can do but wait. I can not put this work item back into the queue in the middle of a memory access but even if I could, the overhead seems completely prohibitive to get things out and put them back into queues every other instruction or so. But with hundreds of hardware threads I could just continue executing some other thread that already got his pointer dereferenced. SIMD is great when you can issue loads and they all get satisfied with the same cache line, but if you have to gather data, then values will arrive one after another and you can not do any dependent work until the last one arrived. I guess the whole point is that all the threads can be at slightly different execution points, while some are waiting for reads to complete others can continue working after their read completed without having to wait for an entire group of reads to complete.
        yvdriess 3y ago
        Correct. This is also why hyperthreading yields a benefit for sparse/graph workloads. I was getting good results on the KNL Xeon Phi with its four hyperthreads. But you easily hit the 'outstanding loads' limit if your hyperthreads all do gather instructions every 4-8 instructions. The architecture needs to balanced around it.
jandrewrogers 3y ago
Graph workloads can work well on normal chips but you really have to know what you are doing. Clever algorithms that demonstrated graphs workloads could be efficiently run on CPUs was a major contributor to the demise of barrel processing research, since a lot of the interest in those architectures was for the purposes of efficient graph analysis. Given the option, economics heavily favors commodity silicon.