比如一个kernel如下:

// N = rows*cols
for(int i=0; i<N;++i)
{
    int r=i//rows;
    int c=i%cols;
    out+=mat0[r][c]*mat1[c][r]
}

分析它的数据流图为:

image-20250710231038989

n4:循环+1

n1:判断 i

n2:i // rows

n3:i % cols

n5:接收n2,n3的值并从mat0 load

n6:接收n2,n3的值并从mat1 load

n7:相乘

n8:加法

n9:累加,由n4控制,表示如果满足“i > bound”,则无需进行实际的累加

如果是cpu的话,9个节点,需要9次计算,如果是gpu的话,也要9次计算,但是gpu可以接收向量化计算,就是一次可以计算多个值。

接下来我们看怎么靠一个2x2的cgra来加速计算:

cycle0: tile0计算n1拿到 i,留存在自己mem并输出给tile2

cycle1:tile0用cycle0的 i 算 n2,就是 i//rows,结果存自己mem同时发给tile2,同时tile2用 cycle0的i算n3,就是i%cols,结果存自己mem同时发给tile0,同时tile1可以开始算n4,就是循环+1

cycle2:tile0算n6,即用cycle1的结果加载 `mat1[c][r]`并发给tile2,tile2算n5,即加载`mat0[r][c]`并放在自己mem里

cycle3:tile2算n7,即相乘,然后输出到tile3,同时tile0又可以开始算n1了

cycle4:除了做和cycle1一样的操作,tile3还计算n8,即加法

cycle5:除了做和cycle2一样的操作,tile1还计算n9,out+=累加,并把结果放到tile3供下一次n8使用

这看似需要5个cycle才能完成一整个计算,但是可以发现从cycle3已经开始流水线了,就是不用完全等到一整个计算结束才开始计算n1,所以等循环跑起来之后,比如下边cycle6 -> cycle8就可以完成n1到n9的所有操作,那么在3个cycle就可以完成一整个操作,II 就是 3。

而cpu/gpu需要9个cycle才能完成,speedup = 9/3 = 3。CGRA加速器实现了cpu/gpu三倍的计算速度。

image-20250710235944730

image-20250711001111971