Why is the layout on the right considered 4D? If the block is the third dimension, what's the fourth?

This comment was marked helpful 0 times.

Each block is two dimensions, not one. You could declare an array like on the right as so: Array[num_blocks_y][num_blocks_x][block_size_y][block_size_x]. A 3D array would only have one 'row' per block whereas this array has multiple introducing a 4th dimension.

This comment was marked helpful 5 times.

in the 4D array layout, the cache line (in pink) is shown to span 2 rows. Is there a way to actually implement a data structure such that the processor loads a cache line in such a manner?

This comment was marked helpful 0 times.

@sss I think you would represent the 4D array using a single 1D array such that the contiguous addresses follow the direction of the arrows shown in the picture. This would be similar to the same manner that you often represent 2D images in a 1D format.

Say that we have an array that is 2-blocks wide, 1 block high, and each block has 2 elements along the x axis and 2 along the y. Let B(a,b) be the block at index (a,b) and E(x,y) be the element in a block with coordinates (x,y) (where I'm indexing y to go from top to bottom, x from left to right, and same with a and b).

Then, in memory, we can lay it out as follows:

------------------|-----------------|-----------------|-----------------|
| B(0,0) | B(0,0) | B(0,0) | B(0,0) | B(1,0) | B(1,0) | B(1,0) | B(1,0) |
| E(0,0) | E(1,0) | E(0,1) | E(1,1) | E(0,0) | E(1,0) | E(0,1) | E(1,1) |
------------------|-----------------|-----------------|-----------------|

So, visually, the cache line would span 2 rows, but in actual memory, it wouldn't.

As you can imagine, indexing into this array is lots of fun, so let me know if I made a mistake :)

Specifically, if element at the start of the cacheline is at index block_idx_x, block_idx_y, x, y (where block_idx_x, block_idx_y are the x and y indices of the block, x, y are the coordinates of the element within the block, where y is really the row), then you can access it as

Array[((block_idx_y * num_blocks_x + block_idx_x) * (block_size_x * block_size_y)) + (y*block_size_x + x)]

Let's break this down....

When I index into this array, I like to think of starting at the upper left of the array and counting the number of elements I have to go through as I follow the arrows (from the picture).

First I want to know the number of blocks that I skip over to get to my block. This should be the number of rows I go through * number of blocks/row + the horizontal index of my block:

(block_idx_y * num_blocks_x + block_idx_x)

Then if I multiply this by the number of elements in a block, I get the number of elements I skip through: (block_idx_y * num_blocks_x + block_idx_x - 1) * (block_size_x * block_size_y)

This should put me at the start of my block. Finally I just need to find the element within the block:

(y*block_size_x + x)

This comment was marked helpful 0 times.