多核动态任务调度的进一步探索(3)

如果使用动态任务调度来实现上面的Strassen矩阵乘法,通常的做法是将7次矩阵乘法变成7个任务来执行,但是,由于计算C0C1C2C3时,必须先将M1,M2,M3,M4,M5,M6,M7计算好,因此生成了7个矩阵乘法任务后,必须在计算C0前,等待这7个任务全部完成。


下面给出动态任务调度实现Strassen矩阵相乘的伪代码。


 


Parallel_StrassenMultiply(A, B, C) 


{


    T1 = A0 + A3;


    T2 = B0 + B3;


    SpawnTaks(M1 = T1* T2);


    T1 = A2 + A3;


    SpawnTask(M2 = T1* B0);


    T1 = (B1 - B3);


    SpawnTask (M3 = A0 * T1);


 


    T1 = B2 - B0;


    SpawnTask(M4 = A3 * T1);


 


    T1 = A0 + A1;


    StrassenMultiply(M5 = T1 * B3);       


   


    T1 = A2 – A0;


    T2 = B0 + B1;


    SpawnTask(M6 = T1 * T2);


    T1 = A1 – A3;


    T2 = B2 + B3;


StrassenMultiply(M7 = T1 * T2);


 


Wait 上面7个任务完成


    C0 = M1 + M4 - M5 + M7


    C1 = M3 + M5


    C2 = M2 + M4


    C3 = M1 - M2 + M3 + M6


}


 


要实现上面伪代码中的等待7个任务完成的功能是非常简单的,只要实现一个栅障(barrier)一样的功能就可以了,不过简单地使用栅障功能会带来许多副作用,因为它可能会使某些线程陷入等待的空闲状态,我们必须做到某个线程对应的7个任务未完成时,它不能空等,而需要去偷取属于其他线程的任务来执行,这样才能保证所有的线程都处于忙状态,使得CPU核得到充分利用。


所以,我们的有依赖关系的任务调度不会使用简单的栅障来实现任务等待,而会采用更高效的方式来实现等待功能,最高效的等待方式是什么?最高效的等待方式就是“不等待”。有没有搞错啊?不是说要实现等待功能吗,怎么能用“不等待”来实现等待呢?


或许有人看到这里要头晕了,其实我自己也头都晕了,因为实在找不到好的方式来解释用“不等待”实现等待的问题,只好把老子的道德经里的“有中生无,无中生有”搬出来一下,简单地说就是用“不等待”来生成“等待”


闲话少叙,还是看看具体的实现思想。

For more complete information about compiler optimizations, see our Optimization Notice.