Why are 513x513 matrix transpositions faster than 512x512 matrix transpositions?

Understanding Performance Differences in Matrix Transposition for Matrix Sizes of 512x512 and 513x513

Square matrices of varying sizes exhibit unique time differences when it comes to transposing them. Interestingly, matrices with dimensions of 2^n tend to have slower transposition times compared to those with dimensions of 2^n 1. While these differences may seem insignificant for small values of n, they become significant at larger dimensions, as evidenced by MATSIZE 512.

To understand the underlying reason for this performance disparity, we delve into the concept of caching.

Cache Organization and Set Mapping

Caches are organized into sets and lines. Each set contains multiple lines that can store data. To locate the set that a particular memory address belongs to, we use the following formula:

set = (address / lineSize) % numberOfsets

As a result, memory addresses map to sets in a somewhat uniform manner.

Cache Misses and Line Evictions

When accessing a memory location, the cache checks if the data is already present. If not, a cache miss occurs, and the corresponding line is read from memory and placed in the cache. However, when the cache is full, it evicts the Least Recently Used (LRU) line to accommodate the new data.

Critical Stride

The critical stride represents the spacing between variables that contend for the same cache lines. It is calculated as follows:

criticalStride = numberOfSets * lineSize

Variables spaced apart by the critical stride or its multiples are more likely to cause cache evictions.

Matrix Transposition and Critical Stride

Imagine a 64x64 matrix with an 8kB cache and four lines per set. Each line can hold eight 64-bit integers. The critical stride in this scenario is 2048 bytes, equivalent to four rows of the matrix.

When transposing the matrix, we swap rows and columns. As we process each row and swap it with its corresponding column, elements separated by the critical stride (four rows) encounter cache evictions. This results in a significant number of cache reloads, leading to slower transposition.

Conclusion

The disparity in transposition times between 512x512 and 513x513 matrices stems from the relationship between the matrix dimensions and the cache's critical stride. Matrices with dimensions that are not multiples of the critical stride experience reduced cache evictions and, consequently, faster transposition times.

The above is the detailed content of Why are 513x513 matrix transpositions faster than 512x512 matrix transpositions?. For more information, please follow other related articles on the PHP Chinese website!