Why is memory one dimensional?

Question

Addresses in system programming languages like C are one dimensional (i.e. one number). This forces the programmer to make a decision whether matrices are stored "row major" or "column major" causing the opposite access to be slower.

This is somewhat surprising, since I think I remember that physical RAM is actually a 2 dimensional structure. And looking at the free part of this article. It seems like there exists a burst mode for accessing multiple elements from the same row.

Why does this burst mode not exist for columns, and why do programming languages not allow for true two dimensional storage of data? This would allow for "row major"/"column major" agnostic designs, which would probably speed up a lot of linear algebra libraries. Which would then trickle down to statistics and machine learning.

(Crosspost from StackOverflow)

Answer 1

Conventional RAM is organized in rows and columns. The CPU selects one row, then the RAM hardware gathers all cells in columns within that row and delivers them to the CPU.

If you were able to also select a column and gather all cells within that column, you would get a different set of bits. No guarantee that they are ordered in any useful way for you. No guarantee that for example a 64 bit integer would come out in sequential bits, no guarantee even for a byte. And the hardware needed is at least doubled, which likely means half the memory for the same price. And I can’t see how this would help you with a 100x100 array.

Where I have seen something similar is in graphics cards. Much drawing is done in a small rectangular area, so you want a cache line not to contain a long stripe, but a rectangular area of pixels. You start with x and y coordinates, then the lower 4 bit of x and y address bytes within a 256 byte cache line, and the other bits address cache lines. As a result, a 16 pixel long line in any direction can fit into a cache line, unlike normal arrangement where for a vertical line each pixel would be in its own cache line.

Answer 2

You're asking multiple questions.

Why are instruction set architectures designed to use a one-dimensional address space for memory? Memory isn't actually one-dimensional, but providing a one-dimensional abstraction is very convenient. It makes programmer's lives simpler, it makes the CPU architecture easier to specify in a comprehensible way, and it provides a single flexible abstraction that isn't tied to a particular technology of the moment or a particular device or platform.

It's not the CPU's abstraction for memory that forces you to choose between row-major vs column-major storage, and cause the opposite way of accessing a matrix to be slower; it's the way DRAM works that forces this decision.

Why don't RAM chips provide both a row-burst and column-burst? Our current DRAM technology is highly optimized for cost, density, and power. Supporting additional features like that would be more expensive and more complex. It's likely that the potential performance gains you're hoping for are not worth the additional expense, and would be modest for most applications, hence not worth it.

Answer 3

Why does [burst mode (fast access to multiple elements from the same row)] not exist for columns?`

There are different "dimensions" involved with varying the basic rectangular semiconductor memory:

0. invest extras in one place, e.g., separate data in&out vs. shared.
1. invest extras in one line along one of the dimensions of the cell array.
   This is where most of the differentiation in DRAM specs has taken place.
   Not too much variance in driving the "word"-/row lines. (Or the write part of the "bit" circuitry.)
   A lot of it following the "sense amplifiers".
2. invest extras in the cell (array).
   This is where extra area would really hurt.
   Consider exchanging the roles of row and column:
   "Easy" with two extra routing layers - "just" add "word" and "bit" circuitry to the other dimension.
   (Not quite as easy, but potentially not as prohibitive in cost choosing the same layer for word lines in one and bit lines in the other dimension, and vice versa.) At the cost of doubled capacity, even if area did not increase.
   Or you invest a second transistor for the second dimension (the part needing an area not too small being the capacitor) - and hope that doesn't blow up cell area.
   (For pretty much the same additional logic - and routing closer to standard -, you could implement a true dual ported DRAM.)

At the benefit side, this allows for other dimension bursts in multiples of the one direction array size, only, else you'd need compiler awareness of RAM chip array size.
For full effect, you need a different (2D?) addressing model throughout more likely than not.

---

Dual (like-)ported memory is usually built from commodity memory parts:
for one thing, that keeps component cost capped at about three times single ported, and investment cost way down instead of up.
I think the same approach and argument to apply here.