笔记来源《计算机体系结构 量化研究方法》
回答上一篇最后留下的问题
（1）如何有效向量化多维矩阵运算？
（2）向量处理器如何高效处理稀疏矩阵？
步幅
步幅指在内存中从一个数组元素移动到下一个元素时跨过的字节数。
矩阵乘法示例（理解步幅的含义）
内层循环对应矩阵B的某一行与矩阵D的某一列的逐元素乘法。由于C语言通常以行为主序存储多维数组，矩阵B和D的元素在内存中可能不是连续存放的。
在C语言中，矩阵的行存储是连续的，但列之间存在较大的步幅。以矩阵D为例，如果要连续访问其列中的元素（内层循环的目的），每次迭代需要跳过整个行的宽度。Fortran语言通常以列主序存储数组，意味着矩阵的列元素在内存中是连续的，意味着访问其连续行元素时需要跨过较多内存空间。
编译器在向量化代码时，需要识别并优化这些步幅问题，以便有效地利用向量处理器的并行能力。如果不对循环进行重新排序或调整访问模式，处理器可能无法有效加载连续的向量元素到寄存器中进行并行运算，这会影响性能。
编译器可以通过循环变换（如循环展开、循环交换等）来改善内存访问模式，以减小步幅或使其适应向量寄存器的宽度。例如，通过改变循环顺序，使内存访问变得更加连续，从而减少跨步读取的次数。
向量处理器处理非连续数据
向量处理器提供了特殊指令来 处理非连续内存访问，如带有步幅参数的加载（Load）和存储（Store）指令，允许一次性读取或写入间隔固定字节数的多个数据元素。这有助于编译器即使在面对较大步幅时，也能生成有效的向量代码。
一旦数据载入向量寄存器，无论原始数据在内存中的分布如何（连续或非连续），处理器都视之为逻辑上相邻的元素，从而允许高效地执行向量运算。
通过具备步幅功能的向量加载（LWS, Load Vector WithStride）和存储（SWS, Store Vector WithStride）指令，向量处理器能够直接处理非连续内存位置的数据。这些指令允许指定加载或存储数据时的间隔，即步幅，从而适应如矩阵运算中跨列或跨行访问的需要。
动态计算步幅：由于矩阵尺寸或向量长度可能在编译时未知或在运行时变化，向量处理器需要动态计算步幅值，并能够将此值存储在通用寄存器中，以便灵活地指导LWS和SWS指令的操作。
LWS（Load Vector WithStride）允许处理器从内存中加载数据到向量寄存器，但不同于普通的连续加载，它可以指定一个步幅参数。
步幅是指在内存中从一个元素移动到下一个元素时跳跃的字节数或元素数。例如，在处理矩阵时，如果想要加载矩阵的一列到向量寄存器，即使这些元素在内存中不是连续存放的，LWS指令可以通过指定正确的步幅来实现这一点。
SWS（Store Vector WithStride）与LWS类似，但作用方向相反。SWS指令用于将向量寄存器中的数据存储回内存，并且同样支持指定步幅。这在需要将计算结果按照特定间隔分布回非连续内存位置时非常有用。
组冲突与停顿
块大小与缓存效率：增大缓存块大小通常可以减少单位步幅访问（如线性遍历数组）时的缓存未命中率，但对于非单位步幅访问（如按列访问矩阵元素），可能反而因频繁跨越缓存行边界而导致缓存效率降低。这是因为非连续访问模式可能不匹配增大的块大小，导致数据未被有效利用或频繁替换。
如果多个内存访问请求指向的是包含在同一个缓存行中的不同数据，且这些请求之间存在一定的步幅关系（即它们访问的地址模式导致频繁访问同一缓存行），这就会导致组冲突（Cache Bank Conflict或Bank Conflict）。这是因为缓存行在同一时间只能服务一个访问请求，其他请求必须等待，直到当前请求完成。
当步幅与缓存行大小的最小公倍数较小，意味着数据访问模式频繁地“撞击”同一缓存行。例如，如果步幅为32字节，而缓存行大小也是32字节，那么每次访问都会命中相同的缓存行，造成连续的冲突。
处理一个缓存行访问请求所需要的时间。如果在这个时间窗口内，有新的访问请求指向同一个缓存行，这些请求就必须等待，直到当前请求处理完毕。如果步幅与缓存行大小的关系导致请求过于频繁地访问同一缓存行，那么这种等待（停顿）就会频繁发生，显著降低系统的整体性能。
向量处理器经常需要存储稀疏矩阵。稀疏矩阵是指大部分元素为零的矩阵，直接存储会浪费大量空间，因此通常采用压缩存储格式，仅存储非零元素及其对应的索引。
稀疏矩阵
【数据结构和算法笔记】：稀疏矩阵的存储结构详解_稀疏矩阵存储结构-CSDN博客
向量计算时的稀疏矩阵
for(i = 0; i < n; i = i + 1)
A[k[i]] += C[m[i]];稀疏矩阵是指大部分元素为零的矩阵，直接存储会浪费大量空间，因此通常采用压缩存储格式，仅存储非零元素及其对应的索引。
向量体系结构使用集中分散操作来处理稀疏矩阵。
集中分散
集中-分散操作是处理稀疏矩阵时的关键技术，特别是在向量处理器和图形处理单元（GPU）中，用于高效地处理非连续存储的数据。这项技术允许在稀疏数据表示与连续（密集）数据操作之间进行有效转换，从而优化计算性能。
集中（Gather）操作
集中操作是从非连续的内存位置加载数据到一个连续的内存区域或向量寄存器中，通常用于将稀疏矩阵的非零元素收集到一个密集向量中，它把分散在内存中的数据集中起来。
实现：通过索引向量（如上例中的Rk和Rm）来指定哪些元素需要被加载。例如，指令LV Yk,Rk ;载入K 和 LY Ym,Rm ;载入M 分别根据Rk和Rm中的索引，从A[]和C[]中集中加载数据到向量寄存器Yk和Ym。这里，索引向量中的每个元素值代表了在原数组中的偏移量。
分散（Scatter）操作
分散操作则是将一个连续的内存区域或向量寄存器中的数据分散写回到非连续的内存位置，即将经过计算的密集向量数据写回稀疏矩阵的相应位置。它将数据分散回其原始的非连续存储位置。
使用同样的索引向量来确定写入的位置。在上述代码中，SVI (Ra+Vk),Va;它将向量寄存器Va中的数据根据Vk中的索引分散回数组A[]的相应位置。
面临的挑战与优化
内存访问冲突与延迟：由于分散-集中操作涉及的内存地址不连续，可能导致内存访问模式较为随机，容易引起存储器组冲突和增加延迟。每个数据元素都需要独立寻址，难以利用缓存行的连续访问优势。
硬件支持与优化：现代向量处理器和GPU通常内置了对集中-分散操作的硬件支持，如VMIPS指令集中的LVI（载入索引向量）和SVI（存储索引向量）。尽管这些操作可能不如连续访问那样高效，但通过精心设计的硬件（如增强的内存控制器、更大的TLB、优化的缓存策略）和软件策略（如程序员手动优化索引访问模式，确保连续访问以利用单位步幅优势），可以显著提升性能。
GPU中的应用
在GPU中，所有的数据载入本质上是集中操作，而存储则为分散操作。为了优化性能，GPU程序员需要确保集中或分散操作中的地址尽可能连续，以利用单位步幅访问的优势。GPU硬件也会通过识别特定模式，自动将某些集中或分散操作转换为更高效的连续访问模式，进一步减少访问延迟和提高吞吐量。