5
$\begingroup$

Summary: Are there good algorithms for out-of-core dense matrix transpose if each row of the matrix is separately compressed?

Details: The matrix is about 1 TB uncompressed, and is roughly but not exactly square. An uncompressed row is less than 6 MB, so many of them fit in RAM at once. On disk, I would like to separately compress each row of the matrix (with a domain-specific, non-random access method), so I need a transpose algorithm that reads from compressed form, recompresses each column, and writes out the compressed columns as the new transposed matrix.

Are any existing out-of-core transpose algorithms compatible with this setup?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ How are you compressing the matrix? $\endgroup$ – Dan May 21 '12 at 6:30
  • $\begingroup$ Each row can be reinterpreted as a rank 6 bit tensor. I haven't implemented it yet, but the plan is to apply a filter/prediction step to increase the number of zeros, then run it through zlib (similar to png compression). $\endgroup$ – Geoffrey Irving May 21 '12 at 15:41
  • $\begingroup$ Why do you want to store individual (compressed) rows instead of compressed tiles? $\endgroup$ – Jed Brown May 21 '12 at 20:39
  • 1
    $\begingroup$ Okay, but you can hold several rows in memory while generating them, and maybe you even create them in parallel (threads or MPI). Putting it on disk in tiles gives up cheap single-row access, but it will make column access massively faster. $\endgroup$ – Jed Brown May 21 '12 at 22:06
  • 2
    $\begingroup$ Yeah, that's very true. I can hold something like 500-700 uncompressed rows in memory at a time, and square tiles of that size are plenty large enough to amortize disk access. And then no need to ever form the transpose on disk. Cool, I should be all set. $\endgroup$ – Geoffrey Irving May 21 '12 at 22:15
4
$\begingroup$

If you do not need fast random access to single rows, you can store tiles instead of storing rows. For example, generate $500$ rows at a time and store them in $500\times 500$ tiles (match to a disk block size for best possible performance). These tiles are big enough that reading them off the disk in a different order (e.g. by columns) will still perform well.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Matching to disk block size is hard due to the compression, but otherwise this is the way to go. $\endgroup$ – Geoffrey Irving May 24 '12 at 4:20
0
$\begingroup$

I'd implement it using blocks of rows. If the matrix is $A$, write it as a sum $A=\sum_{b=1}^B A_b$ where each block $A_b$ consists of only some of the rows of $A$. You choose each block to be so that it fits into memory.

Then $A^T=\sum_{b=1}^B A_b^T$: compute the transpose of $A_1$, store it to disk. Read $A_2$, compute its transpose and add the new columns you get from $A_2^T$ to the ones already computed for $A_1^T$, and so on and so forth. As long as you can store $A_b^T$ and the compressed form of the already treated transposes, it should work.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I'm not sure I follow you. You can't simply write $A_b^T$ to disk independently of the other $A_b^T$, since it needs to be woven into the compressed rows of the output transposed matrix. $\endgroup$ – Geoffrey Irving May 21 '12 at 17:59
  • $\begingroup$ Yes, but every row of $A^T$ is a compressed list of column indices and corresponding values, and you can of course write a partial list to disk, later load it again and merge it with another list. $\endgroup$ – Wolfgang Bangerth May 22 '12 at 8:19
  • $\begingroup$ Ah, that explains the mismatch: the matrix is dense. Doing the repeated load and merge on a dense matrix would result in a massive amount of extra I/O. $\endgroup$ – Geoffrey Irving May 22 '12 at 15:30
  • $\begingroup$ Oh, I misread your original statement then. I thought it was compressed, and I had imagined that you had sparsified it. $\endgroup$ – Wolfgang Bangerth May 23 '12 at 14:17

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.