Memory access is O(N^[1/3])
3 days ago
- #computer-science
- #memory-access
- #algorithm-optimization
- Memory access time is argued to be O(N^(1/3)), meaning larger memory leads to slower access times.
- Theoretical argument: Processor-memory communication delay is proportional to distance, fitting 8x memory within 2x distance in 3D space.
- Empirical evidence shows memory access time roughly follows the cube root of memory size, though bandwidth fits less accurately.
- Practical impact: Optimal precomputation table size in cryptography balances memory access time and computation efficiency, favoring intermediate sizes.
- Future computing models need to account for memory access complexities, especially with ASICs and GPUs optimizing for locality.