Thursday, February 01, 2007
Prefetching Data & Hardware Registers
Some older processors may not support prefetch.
Try the gcc __builtin_prefetch__ function first.
When that doesn't work, you need to write inline assembly. See my MIPS assembly post for a prefetch code for a MIPs processor.
Always instrument you code first to see where there are high cache misses. Once you identify which the offending data structures, see if it's possible to reduce the size. Some times, people write overly large structures thinking that they're trading size for performance. This is especially true for hash tables.
If you've done all higher level optimization first and it's still not fast enough, then it may be time to prefetch. Remember that prefetch does take cycles and system resource. If the code accesses a piece of data 1000 times and miss the cache once, it's probably not worth prefetching. You can tell if prefetching is worth while by carefully instructing the code first.
It's also possible to prefetch a hardware register, but it's a PITA and I've never found the trade-offs worth while for a production level code.
1. Reserved a GPR(general purpose register) to store the prefetch value
GCC has a compiler option xxx which allows you to do this.
You don't want to take away this register from everyone so I suggest you separate the code that's going to reserver this register into it's own file to only that file or directory reserves this register.
Make this register a non-clobber register if you intend to make subroutine calls between the time you prefetch until you use the prefetched value.
2. Write inline assembly to load from the hardware register to this GPR.
The CPU won't block waiting for this transfer to finish. However, the CPU will block if anyone attempts another operation using this GPR.
3. Write inline assembly to load from this GPR to whatever variable you want to use.
If the load operation is not finished, then the CPU will block, but you've still saved some valuable cycles.
Obviously, the hardware register that was prefetched is out of date by the time you use it.
Try the gcc __builtin_prefetch__ function first.
When that doesn't work, you need to write inline assembly. See my MIPS assembly post for a prefetch code for a MIPs processor.
Always instrument you code first to see where there are high cache misses. Once you identify which the offending data structures, see if it's possible to reduce the size. Some times, people write overly large structures thinking that they're trading size for performance. This is especially true for hash tables.
If you've done all higher level optimization first and it's still not fast enough, then it may be time to prefetch. Remember that prefetch does take cycles and system resource. If the code accesses a piece of data 1000 times and miss the cache once, it's probably not worth prefetching. You can tell if prefetching is worth while by carefully instructing the code first.
It's also possible to prefetch a hardware register, but it's a PITA and I've never found the trade-offs worth while for a production level code.
1. Reserved a GPR(general purpose register) to store the prefetch value
GCC has a compiler option xxx which allows you to do this.
You don't want to take away this register from everyone so I suggest you separate the code that's going to reserver this register into it's own file to only that file or directory reserves this register.
Make this register a non-clobber register if you intend to make subroutine calls between the time you prefetch until you use the prefetched value.
2. Write inline assembly to load from the hardware register to this GPR.
The CPU won't block waiting for this transfer to finish. However, the CPU will block if anyone attempts another operation using this GPR.
3. Write inline assembly to load from this GPR to whatever variable you want to use.
If the load operation is not finished, then the CPU will block, but you've still saved some valuable cycles.
Obviously, the hardware register that was prefetched is out of date by the time you use it.
# posted by Mack @ 3:37 PM 
