中科大计算机科学导论 7.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 坏为n3 (缓存 连Y的一列数 据都不能驻留) 灰色表示在缓存中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 灰色表示在缓存中 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 坏为n3 (缓存 连Y的一列数 据都不能驻留) j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 灰色表示在缓存中 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 坏为n3 (缓存 连Y的一列数 据都不能驻留) 矩阵乘算法 继续对i =1, 2, …, n ?1逐步完成最外循环的过程中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法及其优化 完成Z所有 各行元素的计 算过程中，因 取Y而出现的 缓存未命中次 数最好是n2/c 次。该算法所 有缓存未命中 为n2/c +n2/c次 矩阵乘算法 继续对i =1, 2, …, n ?1逐步完成最外循环的过程中 j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法及其优化 完成Z所有 各行元素的计 算过程中，因 取Y而出现的 缓存未命中次 数最坏是n3次, 该算法所有缓 存未命中为 n2/c + n3次 j = 0, 1, … , n ?1 i = 0 X Y 并行矩阵乘算法 再考虑在p个处理器上并行计算 矩阵乘算法及其优化 把Z不同行的计算