对图5.28(b)所示冲突图施加图着色算法,其结果为: 红色: { 1,2,10,11 } 蓝色: { 3,5,6,9 } 黑色: {4,7,8 } 也就是说,只需要3种功能单元就可以实现所有操作。这3种功能单元所实现的操作类型集分别是: (1) { +, <, - }; -- 对应于红色 (2) { *, + }; -- 对应于蓝色 (3) { * }。 -- 对应于黑色 上述例子用图着色算法对操作进行功能单元分配,分配过程中没有考虑硬件资源的约束条件。试想,如果用户指定的硬件资源约束条件规定只允许1个乘法器,那么上述分配结果就不能成立。如果要实现硬件资源约束条件下的(即必须满足用户指定的功能单元和数目)分配算法,就必须对图着色算法加以改进。此时,用户指定的每个功能单元对应于一种颜色,仅当结点对应的操作可以由某个功能单元实现时,才可以对这个结点着以该种颜色。 例如,假定上述例子中的硬件资源约束条件为:2个乘法器,1个减法器和1个实现{+,<}的功能单元。其着色结果示于图5.29。
|