2 ms·

You can't always prefetch though. Look at linked lists and trees. You have to execute the code and wait the 100+ cycles at every node access because you can't p

by eloff 13y ago

You can't always prefetch though. Look at linked lists and trees. You have to execute the code and wait the 100+ cycles at every node access because you can't predict where the next node will be.

twoodfin 13y ago
"Doctor, it hurts when I do this!" If you're hoping to be able to service a request in a few hundred (dozen?) cycles, you'll find your choice of data structures severely limited. That being said, it would be interesting to see how much smarter a CPU could make prefetch. I know there has been a lot of research over the years into prefetch helper threads[1] that would speculatively execute code along both sides of branches to attempt to pull forward as many memory requests as possible. As I understand it, most attempts to implement this in practical systems have been failures. [1] http://cseweb.ucsd.edu/~swanson/papers/ASPLOS2011Prefetching.pdf http://cseweb.ucsd.edu/~swanson/papers/ASPLOS2011Prefetching...
- eloff 13y ago
  Well I'm going to try something like a prefetch thread soon with some common request types that just fetch/modify a single object. It will be interesting to see if that makes any difference to throughput. Something less speculative that helps a lot is just hoist the loads in your code as far away from where you use them as possible.
nkurz 13y ago
Yes, but this puts a lower limit on the latency of each individual request, not on the throughput. Consider having 4 3-level tree lookups that you need to perform. If the first level hits L1, the second L3, and the 3rd is in RAM, you'd have about 10 + 40 + 100 = ~150 cycles of minimum latency for each request. Serially, you'd have ~600 cycles cycles of total latency for the 4 lookups. But if you can do the lookups in batches of 4, you can overlap your latencies and increase your throughput. You can issue the 4 parallel first level lookups, then 4 second level, and then the 4 third level in very close to the same ~150 cycles that you require to do a single complete lookup.

by eloff 13y ago

You can't always prefetch though. Look at linked lists and trees. You have to execute the code and wait the 100+ cycles at every node access because you can't predict where the next node will be.

twoodfin 13y ago

"Doctor, it hurts when I do this!" If you're hoping to be able to service a request in a few hundred (dozen?) cycles, you'll find your choice of data structures severely limited. That being said, it would be interesting to see how much smarter a CPU could make prefetch. I know there has been a lot of research over the years into prefetch helper threads[1] that would speculatively execute code along both sides of branches to attempt to pull forward as many memory requests as possible. As I understand it, most attempts to implement this in practical systems have been failures. [1] http://cseweb.ucsd.edu/~swanson/papers/ASPLOS2011Prefetching.pdf http://cseweb.ucsd.edu/~swanson/papers/ASPLOS2011Prefetching...

eloff 13y ago
Well I'm going to try something like a prefetch thread soon with some common request types that just fetch/modify a single object. It will be interesting to see if that makes any difference to throughput. Something less speculative that helps a lot is just hoist the loads in your code as far away from where you use them as possible.

nkurz 13y ago

Yes, but this puts a lower limit on the latency of each individual request, not on the throughput. Consider having 4 3-level tree lookups that you need to perform. If the first level hits L1, the second L3, and the 3rd is in RAM, you'd have about 10 + 40 + 100 = ~150 cycles of minimum latency for each request. Serially, you'd have ~600 cycles cycles of total latency for the 4 lookups. But if you can do the lookups in batches of 4, you can overlap your latencies and increase your throughput. You can issue the 4 parallel first level lookups, then 4 second level, and then the 4 third level in very close to the same ~150 cycles that you require to do a single complete lookup.