5
$\begingroup$

If you are given a memory address $n$ bits long, then you need to at least process those bits. Hence, if you have $N$ memory available, addressed by $n$ bits, it would take $O(\mathbf{log}(N)) = O(n)$ time to access a given memory location, at best. I can see why it might be convenient to assume $O(1)$ memory access time because we don't go out of our way to abuse it in day-to-day arguments, and because $\mathbf{log}$ grows slowly. That said, what are some "easy" unreasonable implications of being able to access memory in $O(1)$?

$\endgroup$
  • $\begingroup$ Not a hardware expert, but I expect some micro-paralellism is going on, that yes, you need to see each of the $n$ bits, but the circuits can access them in parallel. $\endgroup$ – jmite May 10 '16 at 3:47
  • $\begingroup$ @jmite, but hardware is fixed, so as $n$ goes to infinity, you still need linear time with respect to the size of the address. $\endgroup$ – Yi Liu May 10 '16 at 5:41
  • $\begingroup$ Right, but if $n$ is tending to infinity, then we're working with a theoretical model, which means memory access time depends on what we choose as our model of computation. We can axiomatically define a system to have $O(1)$ memory access, and there's nothing inherently contradictory about that, just like we can define non-deterministic Turing Machines or oracles. The question is, which is most useful in practice, and the consensus seems to be that modelling memory access as $O(1)$ provides the best model of real-world computing. $\endgroup$ – jmite May 10 '16 at 5:46
  • $\begingroup$ stackoverflow.com/a/941340/5191731 $\endgroup$ – HopefullyHelpful May 10 '16 at 5:56
  • $\begingroup$ To some extent, you take this into account since it takes time for the program to write the address (if it's very long). However, once you've calculated one address, you can change only parts of it in $O(1)$. If you change higher order bits, then the resulting addresses are not adjacent, so this is somewhat unrealistic, as you mention. $\endgroup$ – Yuval Filmus May 10 '16 at 6:24
1
$\begingroup$

Memory access is assumed to be constant time, because normally you access memory that is close to each other, eg. from one hard drive or one given computer. Under that assumption there is a constant maximum amount of time to retrieve that data.

You are right. If I access data randomly accross very large amounts of data, then it's nowhere near constant, but normally you can arrange the data beforehand in a way that makes it O(1), because of it fitting onto one machine or very close machines. Another reason is that, harddrives all come with their hardware. That means normally you won't be switching hard drives in and out of one machine, and each drive comes with it's own reader. Also most machines are limited to a certain amount of drives. Those technical limitation give O(1) comlexity to most pratical applications and the software perspective of things.

One easy and unreasonable implication of O(1) time memory access is violating the assumptions above by scattering data randomly, across multiple machines in an unordered fashion or switching drives in and out of machines and expecting O(1) access times. Anything relying on wrong assumption is doomed to be wrong and thus unreasonable.

$\endgroup$
1
$\begingroup$

The fault in the logic here is that n bits are processed in parallel. Roughly speaking out of those n bits, m<n bits are used to select the chip, and on the chip m-n bits are used to select the memory cell.

The chip select can be envisaged as offering all chips in parallel the relevant m bits of the address. Each chip has a unique ID, so only one of them will match that part of the address and start decoding the next n-m bits.

On the chip, pretty much the same process repeats: the memory cells are arranged in rows and columns. The incoming n-m bits are split in two. Half of those select the correct row, half select the right column, and at the crosspoint of the two is the right memory cell.

In practice, chips are grouped in DIMM's, inside a chip there are individual pages, memory access isn't bit-by-bit but typically 64 to 256 bits at a time, but that's irrelevant for the big-O picture. All relevant address decoding happens in parallel.

$\endgroup$
1
$\begingroup$

The easiest unreasonable implication is that such ignores the impact of temporal and spatial locality of reference in conventional systems. Processor caches cause accesses to other addresses within a cache block to be faster (spatial locality) and repeated accesses to the same address (temporal locality) when accessed while still in cache. Conventional implementations of virtual memory also cache address translations at page granularity. Latency (and bandwidth) in accessing standard DRAM will vary based on whether the access is a row hit (this avoids the need for a row activate command) and whether the DRAM bank being accessed has an active row (this requires a precharge command before the row activate command). Conventional storage devices are high latency block devices and copy data to main memory (in some cases to last level cache), again introducing issues of spatial and temporal locality.

Random accesses may have approximately constant latency when the working set size is within the capacity of one level of the memory hierarchy but much larger than the next level closer to the processor. That is, when the vast majority of accesses are satisfied by one level of the memory hierarchy. (Even this ignores cold-start latencies.)

Even without caching (i.e., copying data into a faster memory), basic physics encourage non-uniform access delay: storage that is physically closer to the processing element can have lower latency. In addition, while the speed of light limit would imply O($\sqrt[3]{N}$) latency (not O(log(N))), something between O($\sqrt[3]{N}$) and O($\sqrt{N}$) is probably more realistic because of the way systems are biased toward two dimensional layout (not that a circular single processor system with a radius of tens of meters is especially realistic).

Another factor is that for larger memories, reducing cost per bit of "distant" storage at the cost of latency becomes attractive because the latency cost of a slower technology is effectively constant while the latency cost of communication is related to distance. Not only are caches requiring spatial and temporal locality effective, but programmers even have some bias toward such locality (e.g., data members of an object are typically allocated together and referenced with some temporal locality because they are conceptually related). This further encourages the use of memory hierarchies.

(Distributing work to multiple processing elements increases the complexity of memory latency considerations. Because physical distance is a factor in latency and large crossbar interconnects are expensive, local memory will be used and access latency will depend on which processing element is accessing the memory. Each processing element is likely to have its own memory hierarchy with levels of sharing. In addition to reducing local latency, distributing computation facilitates increased local bandwith.)

Another factor involves the ability to overlap latencies (memory level parallelism). An algorithm that can do other work while waiting for a slow access will hide some of the latency of that access. By introducing necessary slow accesses at a higher rate more of the latency can be hidden (the accesses are effectively pipelined). Unlimited memory level parallelism changes a latency bottleneck into a bandwidth bottleneck.

(Asymptotic notation also inherently ignores constant factors and lower order terms, but in actual systems these can be significant.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.