3

Suppose I have an algorithm that has N blocks of data, and an operation needs to be performed on all blocks such that it requires 2 blocks to be in memory at any given time to be done for all possible pairings of the N blocks.

When N is large such that not all the data will fit in the memory of the machine running it:

What are the optimal methods for ordering these operations to minimize the number of times the data has to be fetched from disk to complete the operations? The simplistic approach to compare block 1 with all others is clearly very sub-optimal.

3
  • After you have processed the pair (1,2), do you also have to process (2,1) separately? What number of blocks does fit in memory at the same time? Apr 25, 2019 at 11:54
  • 1
    You might find that the Computer Science stack ( cs.stackexchange.com ) gives better answers to this question? Apr 25, 2019 at 13:20
  • @BartvanIngenSchenau in this case no, but if it were the case then (1,2) and (2,1) should clearly be processed sequentially, so this doesn't affect generality. the number of blocks that do fit, is >2 but <N
    – camelccc
    Apr 25, 2019 at 16:10

1 Answer 1

1

Memory is fast at random access. Persistent storage is not. Persistent storage is faster as a stream. If those assumptions hold true for your situation I'd design a solution that accommodates them.

Whenever I deal with a combination problem like this it helps to have a multiplication table in front of me:

enter image description here

Your operation requires two blocks just like multiplication requires two numbers. Notice that you can fold this table diagonally and see the same numbers on the other side. We can save duplicating over half the work by not duplicating the work in one triangle, assuming, just like multiplication, your operation is commutative.

If you think I'm just headed for the simplistic approach here you're right, but bear with me and you'll see something neat.

Here are some loops that work fine for this on an array in memory:

int[] arr={1,2,3,4};
for (int i=0; i<arr.length; i++)
    for (int j=i+1; j<arr.length; j++)
        System.out.println("{"+arr[i]+","+arr[j]+"}");

Outputs:

{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}

Here's the neat thing I want you to notice: as much as they can, the numbers here keep going up. The only time they don't is when we're skipping work that's already done. This could be rewritten to pull these in with streams and skip the unneeded parts. It lets you hold the left value in memory as long as it's needed.

A possible improvement would be to ensure that you only ever change one value at a time. That would mean arranging the work into this order:

{1,2}
{1,3}
{1,4}
{3,4}
{2,4}
{2,3}

However this requires that access to persistent storage be more random than sequential. Depending on the size of your blocks that might be fine. I/O has it's own block size that could be anywhere from 512 bytes to 64 kilobytes. Depends on your format.

If your block size is smaller than your I/Os block size you could do some random access within the bounds of the I/O block size. Otherwise being as sequential as possible is the way to go.

5
  • In fact, more generally, you can look at "block" methods for handling matrices - its been studied quite extensively by people who work with very large (and multi dimensional) matrices (or tensors) in order to get every bit of performance out of their machines when there is a hierarchy of storage with a corresponding hierarchy of cost.
    – davidbak
    Jan 24, 2021 at 17:42
  • @davidbak sounds interesting. Are you talking about this? If so how about favoring us with an answer. I'd love to see how you apply this to the OPs problem that requires any 2 blocks. Jan 24, 2021 at 18:56
  • That comment has already told you all I know about the subject. I think your link provides the start of the theory behind the numerical block algorithms, but consider this search ...
    – davidbak
    Jan 24, 2021 at 19:07
  • Oh and consider this too, on "communication avoiding algorithms", a term I had never heard of until just now ...
    – davidbak
    Jan 24, 2021 at 19:16
  • Your multiplication table argument relies not just on commutativity, but that the data in both blocks is the same (i.e. the numbers 1-10). But if it's the same, then there's no point in loading both blocks into memory. So OP's situation doesn't quite fit with your answer.
    – Flater
    Jan 25, 2021 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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