Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I want to know whether it will work faster if stored in row major or column major order.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
The asymptotic complexity will not change with relation to how the matrices are laid out in memory, but the actual running time of the matrix multiplication will be very dependent upon the memory layout. There are two papers that I know of that go into detail about this, one by McKellar in 1969 and another by Prokop in 1999. Prokop's paper defines the concept of cache complexity which is related to the number of cache misses the algorithm will incur.
The two papers can be found here: http://supertech.csail.mit.edu/papers/Prokop99.pdf and here: http://dl.acm.org/citation.cfm?id=362879
The short version is, an $O(n^3)$ algorithm will still be an $O(n^3)$ algorithm (assuming you are using the straightforward matrix-multiply). However, by taking into account the memory hierarchy of the system, you can significantly speed up that $O(n^3)$ algorithm.
$\begingroup$
$\endgroup$
4
No, the complexity remains the same.
The main difference between row-major and column-major order is memory access patterns - for example if you iterate by column then row-major order would be jumping around memory, which is bad for CPUs because they cannot read-ahead/cache memory.
This is because transferring data from RAM to the CPU on modern processors is relatively very slow, compared with the speed of the processors. Thus most of the time would be spent on waiting for the memory to arrive.
To solve this problem, memory accesses are answered in in bunches, with a lot of extra data coming to the CPU's caches. This makes it important to use "good" memory access patterns, so that the machine can try and predict what you will use next, and therefore cache it, and thus eliminate the transfer-wait-times as much as possible. But if you jump around memory instead of going in order, the machine will potentially have to wait for each access.
The wait time is bounded by a constant however, so the complexity remains the same. And of course, doing it in the correct order does not decrease the complexity.
-
1$\begingroup$ Transposition of one matrix source has been used to accelerate matrix multiply, but matrix multiply is the classic use case for blocking to maximize reuse within a level of the memory hierarchy (registers, L1 Dcache, etc.). $\endgroup$– user4577Commented Nov 11, 2013 at 13:26
-
$\begingroup$ @PaulA.Clayton by accelerate, I assume you mean complexity-wise; that sounds interesting, can you give a reference? $\endgroup$ Commented Nov 11, 2013 at 14:51
-
2$\begingroup$ No, complexity ignores real-world effects like caching, burst memory accesses, and DRAM row/page hits. Transposition of one source allows the inner most loop to use sequential accesses for both matrices, which in some real world situations reduced the runtime of matrix multiply. Wikipedia indicates ATLAS still considers transposition (though that may be out-of-date). $\endgroup$– user4577Commented Nov 12, 2013 at 0:31
-
$\begingroup$ @PaulA.Clayton ah ok, that is still interesting. $\endgroup$ Commented Nov 12, 2013 at 0:33
$\begingroup$
$\endgroup$
It depends on the machine model you're using.
In the RAM model, which is probably the most commonly used one, the complexity is the same regardless of the layout being row-major or column-major.
In the IO model, where you're counting how many times the algorithm must read a block of size B into a cache of size M, it does matter. (For example, in the IO model sorting is not N lg N; it's N/B lg_M N/B.) For matrices that don't fit into the cache, iterating the entries in the wrong order costs n^2 instead of n^2/B.
Algorithms that perform well in the IO model, without relying on the specific values of B or M, are called cache oblivious.
