注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东南隅

wantnon的blog

 
 
 

日志

 
 
 
 

非线性流水线的无冲突调度算法的原理  

2010-05-15 11:57:58|  分类: 计算机 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

《体系结构》课本上只给出了算法过程,并没有结出证明,但通过对算法的分析,可以弄清背后的原理:

1, 重叠表:

设G为非线性流水线的预约表,s为G中画叉的格子形成的图形。

G(s1)表示由G与一个s无冲突叠加而成的表,称为一次重叠表。

同理定义二次重叠表G(s1,s2),三次重叠表G(s1,s2,s3),…,m次重叠表G(s1,…,sm)。

G可以看作是0次重叠表。

用sr表示G(s1,…,sm)中最后一个s。

如果需要表示出G(s1,..,sm)中相临s间的距离,则可以用记号G(d1,s1,…,di,si,….,dm,sm),其中di为si-1与si之间的距离。

2, 表的扩充:

设有m次重叠表G(d1,s1,..,dm,sm),现通过增加一个重叠使其变为表G(d1,s1,…,dm,sm,k,sm+1)的过程称为一次“扩充”。如果需要指明新增s与原sr的距离为k,则可以说成是一次“k-扩充”。

3, 冲突向量:

设有重叠表G(d1,s1,..,dm,sm),将其作k-扩充,显然,对于某些k值扩充结果将发生冲突,对于另一些k值则无冲突。将所有使G(d1,s1,..,dm,sm)的k-扩充冲突的k值所成集合称为重叠表G(d1,s1,..,dm,sm)的冲突向量。

简言之:某重叠表的冲突向量就是使其k-扩充发生冲突的k值集合。

另外注意这里集合是用二进制串来表示的,如101100表示集合{6,4,3}。

冲突向量的分量称为冲突分量。

4,状态图中转化过程的含义:

clip_image002(图1)

如图,其中状态101100是0次重叠表G的冲突向量,而其余状态均为G的扩充表,或扩充表的扩充表的冲突向量。

以其中的101111-(5)->101101为例,此过程的含义是:

将冲突向量为101111的重叠表5-扩充,所得新表冲突向量为101101。

5,下一状态冲突向量的计算:

仍以101111-(5)->101101为例。

书上是这样计算出101101的:

(*)首先将101111逻辑右移5位得000001,然后再与G的冲突向量101100按位或得到101101。

此算法为什么是对的?回答如下:

设冲突向量101111对应的表为G(d1,s1,…,dm,sm),现要对它进行扩充,这里作的是5-扩充,至于为什么是5?原因很简单:因为G(d1,s1,…,dm,sm)的冲突向量101111表明对其作1,2,3,4-扩充均有冲突,所以至少是5-扩充。扩充后得G(d1,s1,…,dm,sm,5,sm+1),下面求G(d1,s1,…,dm,sm,5,sm+1)的冲突向量。也就是要看G(d1,s1,…,dm,sm,5,sm+1)不能作几扩充。因为“对G(d1,s1,…,dm,sm)作k-扩充新增s的位置”=“对G(d1,s1,…,dm,sm,5,sm+1)作k-5扩充新增s的位置”,而由G(d1,s1,…,dm,sm)的冲突向量为101111知k不能取6、4、3、2、1,所以k-5不能取1、-1、-2、-3、-4,所以G(d1,s1,…,dm,sm,5,sm+1)不能作1、-1、-2、-3、-4扩充,由于扩充距离不可能是负数,所以“不能作-1,-2,-3,-4扩充”是废话,所以得到的有用信息仅是“G(d1,s1,…,dm,sm,5,sm+1)不能作1扩充”,所以000001是G(d1,s1,…,dm,sm,5,sm+1)的冲突向量的一个子集(注:以上计算过程用二进制表示出来就是:101111逻辑右移五位得000001)。不过000001并非完整的冲突向量,它只是说明G(d1,s1,…,dm,sm,5,sm+1)的哪些k-扩充会与s,s1,…,sm冲突。即000001只是“G(d1,s1,…,dm,sm,5,sm+1)对s,s1,…,sm的冲突向量”。下面还需要求“G(d1,s1,…,dm,sm,5,sm+1)对sm+1的冲突向量”:

因为“G(d1,s1,…,dm,sm,5,sm+1)的k-扩充与sm+1冲突”<=>“G的k扩充冲突”所以“G(d1,s1,…,dm,sm,5,sm+1)的对sm+1的冲突向量”=“G的冲突向量”=101100。

因此有:“G(d1,s1,…,dm,sm,5,sm+1)的冲突向量”=“G(d1,s1,…,dm,sm,5,sm+1)对s,s1,…,sm的冲突向量”∪“G(d1,s1,…,dm,sm,5,sm+1)对sm+1的冲突向量”=000001∪101100=101101。这就证明算法(*)的正确性(同时也说清了它是怎么想出来的)。

6,多个重叠预约表可能对应同一个冲突向量:

例如,状态图(图1)中G(5,s1)和G(2,s1,5,s2)两个重叠表都对应冲突向量101101。

7,右移次数>=7时必回到G的冲突向量101100:

这是因为右移7次或7次以上二进制串就成为全0了,然后与G的冲突向量101100按位或,当然还得101100。

  评论这张
 
阅读(99)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018