Notes on 2D Array Storage and Memory Access

2D Arrays and Memory Addressing

Overview of 2D Arrays

  • Definition: A 2D array is a matrix format for storing data, effectively organizing information in rows and columns.

  • Example of a 2D Array:

    • Let M represent the array, specifically a 25 x 25 matrix.

    • Each element in the matrix can be referred to using the notation M(i, j), where i is the row index and j is the column index.

Storage Details of the 2D Array M

  • Matrix Dimensions: M has dimensions of 25 rows and 25 columns (25 x 25).

  • Column Order Storage:

    • The elements are stored in a column-major order, meaning:

    • The first column is filled from the top to bottom, then the second column, and so on.

    • For example, the addresses for the first column elements are:

      • M(0,0) stored at address i

      • M(1,0) stored at address i + 4

      • M(2,0) stored at address i + 8

      • Continuing until M(24,0) which is stored at address i + 100

  • Address Calculation:

    • Each element occupies 4 bytes (word size). Thus, the formula for the address of M(m,n) given the starting address i as:

    • M(m,n): Address = i + (m * 100 + n * 4)

    • Example for the first row:

    • M(0,0) is at i

    • M(0,1) is at i + 100

    • M(0,2) is at i + 200

    • …

    • M(0,24) is at i + 2400

Memory Allocation

  • Block of Memory Example:

    • This matrix M results in a total of 1000 bytes allocated in memory, calculated as follows:

    • 1000 bytes = 25 rows * 25 columns * 4 bytes/word.

  • Memory Addresses of Elements:

    • The elements of the first row, M(0,j) for j=0 to 24, are stored consecutively:

    • Addresses will be as follows:

      • M(0,0) at address i

      • M(0,1) at address i + 100

      • M(0,2) at address i + 200

      • …

      • M(0,24) at address i + 2400

Accessing Elements in a 2D Array

  • Post-indexed Mode:

    • Elements can be accessed using post-indexed mode in assembly programming.

    • Example Load Instruction:

    • LDR R1, [R2], R10, LSL #2

    • This instruction loads a word from the address contained in R2 into R1 and then updates R2 with an offset based on R10 shifted left by 2 bits.

    • The sequential access pattern can utilize a loop to iterate through each column of the first row.

  • Looping Structure:

    • An iterative approach can be used in a programming language to access each element. Each loop iteration would increment the address according to the offset calculations.

Conclusion

  • Understanding the arrangement and access patterns of a 2D array in memory is crucial for efficient programming, especially in low-level languages where memory management is critical.