Synchronization and memory costs are becoming humongous bottlenecks in today's architectures. However, algorithm complexities assume these operations as constant, which are done in O(1) time. What are your opinions in this regard? Are these good assumptions in today's world? Which algorithm complexity models assume higher costs for synchronization and memory operations?
The algorithm complexity measure makes the assumption that it is independent of the implementation. It is a way to abstract the problem into the mathematical domain. That is why benchmarking is necessary, in it you can take into account things such as UMA vs. NUMA architectures and other implementation details
Computational costs produced by the physical design of the architecture (such as memory accesses, data synchronization, multi-threading, instruction decoding, etc) are hardware and platform-specific. If your only concern is to study the algorithm that runs above the hardware, I guess it makes sense to omit the latency produced by the platform.
Of course, it also depends if your algorithm is closely related to the hardware. In such case, you obviously factor-in bottlenecks produced by the physical implementation.
Masab Ahmad Do you have a specific algorithm or problem or hardward that you are concerned? In terms of complexities, the costs of aforementioned factors are constants, though in reality the constant can be large, but it's still O(1).
Quan Hoang Nguyen I was asking about all machines in general. In reality, the time it takes to access to access O(N) elements from memory randomly or synchronizing on O(N) elements is higher than computational time taken on a O(N) function. As no machine exists that has very low memory access or synchronization costs, it may not be a good thing to assume O(1) costs for such operations. I'm just saying it may be wise to rethink these assumptions in the context of these bottlenecks.
Just adding to what was previously said. In specific purpose computers (embedded systems) it is posible to have hardware-based operations that are not necessarily O(1) (or any other complexity order for that matter) like their general purpose counterparts. Such is the case in certain devices designed for cryptology applications.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms