接触到了一种新的依赖解决算法问题，英文叫做wavefront algorithm，中文好像叫波前算法吧。大体思路是，对于一个X*Y数组结构的数据，当运算依赖关系是从西北角开始运算，直到覆盖所有的表项，得到最终结果的时候。每一个运算单元，都必须依赖其西，西北和北边相邻的数据才能开始运算时，其运算方式如同水波一样，逐层前进。
如下图模拟，数字增长，表示随着时间推移，运算的顺序：从1-》2-》3-》 -》7结束，完成整个数据的运算。
| 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 5 |
| 3 | 4 | 5 | 6 |
| 4 | 5 | 6 | 7 |
通过论文的阅读，有人在CELL BE上对他作出了如下改进：
根据SPE的数量，将原数组划分成高度为SPE数的BLOCK ROW，然后每一行用一个SPE进行运算，同样按照波前算法，得到如下图：这样，在每一个BLOCK ROW的最后计算时候，会和下一个BLOCK ROW有部分重叠，这样就提高了并行度。同时，从存储结构上来看。同一行之间传输数据，是不需要的，因为是在同一个SPE中，这样可以大大减少数据传输的时间。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 |
| 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 | 3 |
| 5 | 6 | 7 | 8 | 9 | 1 | 2 | 3 | 4 |
| 6 | 7 | 8 | 9 | 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 |
总计算时间为：20单位，SPE数量6个。
然后我们经过分析和思考，可以继续做如下改进：
将处理的数据，根据SPE的数量，划分成N/2高度的列和行，然后分别从列和行进行计算，再次加大并行程度，同时，在每做完一次行列计算之后，将原有数据量变小一个等级，解释如下图：
设我们有6个SPE,数据量为9*9
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 |
| 4 | 5 | 6 | 1 | 2 | 3 | 4 | 5 | 6 |
| 5 | 6 | 7 | 2 | 3 | 4 | 5 | 6 | 7 |
| 6 | 7 | 8 | 3 | 4 | 5 | 6 | 7 | 8 |
| 7 | 8 | 9 | 4 | 5 | 6 | 7 | 8 | 9 |
| 8 | 9 | 1 | 5 | 6 | 7 | 8 | 9 | 1 |
| 9 | 1 | 2 | 6 | 7 | 8 | 9 | 1 | 2 |
总计算时间为：20单位。SPE数量6个。
可以看出，在这种情况下，SPE数量相等时，总计算时间是相等的，但是从更细节上来看，我们改进的方法，SPE利用率更高，当系统总资源一定时，速度更快。
利用数学方式来看，方法一的总时间
T = (Ttile + Tdma) * (XY / Tsize~2 * Nspe + S(Nspe)) + Tserial
方法二总时间
T = (Ttile + Tdma) * (X(2XY – 2TsizeY – X~2 + XTsize) / Tsize~2 * Nspe + S`(Nspe)) + T`serial
其中S`(Nspe) < S(Nspe), 因为spe利用率更高。
可以证明，当X Y Tsize取一定值的时候，T2 《 T1.
这个取值还需要继续讨论和设计实验证明。
未完待续。。。