5
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ Memory is two-dimensional. If a memory address is $N$ bits long and $N = N_1+N_2$, you can think of it as having two dimensions, one $N_1$ bits long, and the other $N_2$ bits long. Similarly, it is three-dimensional. $\endgroup$ Apr 3 '20 at 17:26
  • 2
    $\begingroup$ Physically speaking, memory is arranged in several dimensions, of fixed size. However, this depends on the particular hardware. Complicating things, you could be mixing different hardware, some of your memory is virtual, and so on. You wouldn't want the programmer to handle all of this, and also it wouldn't really help representing matrices, unless they happen to have exactly the right dimensions. $\endgroup$ Apr 3 '20 at 17:28
  • $\begingroup$ @YuvalFilmus Okay it makes sense that you would want to avoid having the programmer deal with different hardware, but even if the matrix does not fit, you could maybe still provide high level abstractions for matrices, which are cut into blockmatrices for storage. This would probably still allow for SIMD. But I can see why this could easily become a big headache, thanks! $\endgroup$
    – Felix B.
    Apr 3 '20 at 18:42
  • $\begingroup$ I turn a 2nd part to my answer into the following comment: Why do programming languages not allow for true two dimensional storage of data? They don't? Please define True two dimensional storage of data. $\endgroup$
    – greybeard
    Mar 17 at 17:21
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ "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." Could you provide an argument for that? In particular in times where memory access is becoming the primary bottleneck. It seems like the additional physical space this capability would take is not really an issue. I mean RAM is already physically separate from the CPU and virtually arbitrarily sized. $\endgroup$
    – Felix B.
    Apr 4 '20 at 9:09
  • $\begingroup$ @FelixB. D.W. is talking about the majority situations, apparently. You are right to the point that memory architecture is so important or critical in many cases such as in large-scale computing for artificial intelligence (which is becoming (one of) the new major situations) specialized structures have been developed. $\endgroup$
    – John L.
    Apr 9 '20 at 17:26
  • $\begingroup$ Why is it different in the majority of situations? Why is it not worth the additional space? I mean the border of quadratic memory only increases with sqrt(n) in memory size n. Seems like a small sacrifice. And since the memory is physically separate I also do not find it convincing that there is not enough space $\endgroup$
    – Felix B.
    Apr 10 '20 at 10:04
  • 1
    $\begingroup$ @FelixB., My experience is that usually architectural changes that involve a small sacrifice for every workload and a large improvement for one workload turn out to be not worth it overall, in general-purpose CPUs. Of course special-purpose hardware is a different matter. So, saying "it's only a small sacrifice" isn't really a convincing argument. To make a convincing argument, you'd need to quantify the costs and benefits and the proportion of workload spent on tasks that benefit vs those that are harmed. $\endgroup$
    – D.W.
    Apr 10 '20 at 17:41
  • $\begingroup$ What about graphics cards? They are special purpose. They basically only do linear algebra. And the sacrifice is not really performance. It is just the cost of adding another read-out I guess? But sure I do not know the specifics. Which is why I asked the question. But answering the question of: "Why is this not done?" With: "It is not worth it." Is not really an answer in my opinion. Because: duh. $\endgroup$
    – Felix B.
    Apr 10 '20 at 20:06
0
$\begingroup$

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:

  1. invest extras in one place, e.g., separate data in&out vs. shared.
  2. 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".
  3. 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.

$\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.