全相联映射是指主存中任一块都可以映射到Cache 中任一块的方式,也就是说,当主存中的一块需调入Cache 时,可根据当时Cache 的块占用或分配情况,选择一个块给主存块存储,所选的Cache 块可以是Cache 中的任意一块。例如,设Cache 共有2C 块,主存共有2M 块,当主存的某一块j 需调进Cache 中时,它可以存入Cache 的块0、块1、…、块i 、… 或块2C -1的任意一块上。如图4-28所示。
图4-28全相联映射方式
在全相联映射方式下,CPU 的访主存地址为如下形式:
其中,M 为主存的块号,W 为块内的字号。而CPU 访Cache 的地址形式为:
其中,C 为Cache 的块号,W 为块内的字号。
主存地址到Cache 地址的转换是通过查找一个由相联存储器实现的块表来完成的,其形成过程如图4-29示。
图4-29全相联映射的地址转换
当一个主存块调入Cache 中时,会同时在一个存储主存块号和Cache 块号映射表的相联存储器中进行登记。CPU 访存时,首先,根据主存地址中的主存块号M 在相联存储器中查找Cache 块号,若找到,则本次访Cache 命中,于是将对应的Cache 块号取出,并送访Cache 地址的块号C 字段;紧接着将主存地址的块内字号W 直接送Cache 地址的块内字号W 字段,从而形成一个访Cache 的地址;最后根据该地址完成对Cache 单元的访问.
全相联映射方式的优点是Cache 的空间利用率高,但缺点是相联存储器庞大,比较电路复杂,因此只适合于小容量的Cache 之用。
2. 直接相联映射
直接相联映射方式是指主存的某块j 只能映射到满足如下特定关系的Cache 块i 中:
i =j mod 2C (4.2)
图4-30直接相联映射方式
上图中,主存的第0、2C 、2C +1、… 块只能映射到Cache 的第0块,主存的第1、2C +1、2C +1+1、… 块只能映射到Cache 的第1
块,… … ,主存的第2C -1、2C +1-1、…2M -1块只能映射到Cache 的第2C -1块。
在直接相联映射方式下,CPU 的访主存地址为如下形式:
其中,T 为标志号,C 为Cache 的块号,W 为块内的字号。在这里,原主存的块号M 实际上被分成了两个字段:T 和C ,其中C 用于指出主存的块可以映射的Cache 的块。一般来讲,主存的块数是Cache 的块数的整数倍,也就是说主存的块数2M 和Cache 的块数2C 满足关系式:2M =n·2C
在直接相联映射方式下,标志号T 是随Cache 的每个块一起存储的,其地址转换过程如图4-31所示。
图4-31直接相联映射的地址转换
当一个主存块调入Cache 中时,会同时将主存地址的T 标志存入Cache 块的标志字段中。当CPU 送来一个访存地址时,首先,根据该主存地址的C 字段找到Cache 的相应块,然后将该块标志字段中存放的标志与主存地址的T 标志进行比较,若相符,说明主存的块目前已调入该Cache 块中,则命中,于是使用主存地址的W 字段访问该Cache 块的相应字单元;若不相符,则未命中,于是使用主存地址直接访主存。
直接相联映射方式的优点是比较电路最简单,但缺点是Cache 块冲突率较高,从而降低了Cache 的利用率。由于主存的每一块只能映射到Cache 的一个特定块上,当主存的某块需调入Cache 时,如果对应的Cache 特定块已被占用,而Cache 中的其它块即使空闲,主存的块也只能通过替换的方式调入特定块的位置,不能放置到其它块的位置上。
3. 组相联映射
以上两种方式各有优缺点,而且非常有趣的是,它们的优缺点正
好相反,也就是说,对于全相联映射方式来说为优点的恰是直接相联映射方式的缺点,而对于全相联映射方式来说为缺点的恰是直接相联映射方式的优点。那么,可否找到一种能较好地兼顾这两种方式的优点的映射方式呢?下面我们就来看看组相联映射方式 在这种方式下,将Cache 分成2u 组,每组包含2v 块。主存的块与Cache 的组之间采用直接相联映射,而与组内的各块则采用全相联映射。也就是说,主存的某块只能映射到Cache 的特定组中的任意一块。主存的某块j 与Cache 的组k 之间满足如下关系:
k =j mod 2u (4.3)
设主存共有2s ×2u 块(即M =s+u),则它们的映射关系如下图4-32示。
图4-32组相联映射方式
图中,主存的块0、2u 、2u +1、…、(2s -1)2u 可以映射到Cache 的第0组的任意一块,主存的块1、2u +1、2u +1+1、…、(2s -1)2u +1可以映射到Cache 的第1组的任意一块,… … ,主存的块2u -1、2u +1-1、…、2M -1可以映
射到Cache 的第2u -1组的任意一块。
在组相联映射方式下,CPU 的访主存地址和访Cache 地址分别为如下形式:
其中,u 为Cache 的组号,v 为组内的块号。Cache 的块号C =u+v,而主存的块号M =s+u。也就是说,主存块地址的后u 位指出了主存的这一块所能映射的Cache 的组。
与全相联映射方式类似的是,在组相联映射方式下,主存地址到Cache 地址的转换也是通过查找一个由相联存储器实现的块表来完成的,其形成过程如图4-33所示。
图4-33组相联映射的地址转换
当一个主存块调入Cache 中时,会同时将其主存块地址的前s 位写入一个由相联存储器实现的快表的对应Cache 块项的s 字段中。例如,设主存的某块调入Cache 的第1组的第2块中,则在快表的组1第3项的s 字段会登记下该主存块地址的前s 位。
全相联映射是指主存中任一块都可以映射到Cache 中任一块的方式,也就是说,当主存中的一块需调入Cache 时,可根据当时Cache 的块占用或分配情况,选择一个块给主存块存储,所选的Cache 块可以是Cache 中的任意一块。例如,设Cache 共有2C 块,主存共有2M 块,当主存的某一块j 需调进Cache 中时,它可以存入Cache 的块0、块1、…、块i 、… 或块2C -1的任意一块上。如图4-28所示。
图4-28全相联映射方式
在全相联映射方式下,CPU 的访主存地址为如下形式:
其中,M 为主存的块号,W 为块内的字号。而CPU 访Cache 的地址形式为:
其中,C 为Cache 的块号,W 为块内的字号。
主存地址到Cache 地址的转换是通过查找一个由相联存储器实现的块表来完成的,其形成过程如图4-29示。
图4-29全相联映射的地址转换
当一个主存块调入Cache 中时,会同时在一个存储主存块号和Cache 块号映射表的相联存储器中进行登记。CPU 访存时,首先,根据主存地址中的主存块号M 在相联存储器中查找Cache 块号,若找到,则本次访Cache 命中,于是将对应的Cache 块号取出,并送访Cache 地址的块号C 字段;紧接着将主存地址的块内字号W 直接送Cache 地址的块内字号W 字段,从而形成一个访Cache 的地址;最后根据该地址完成对Cache 单元的访问.
全相联映射方式的优点是Cache 的空间利用率高,但缺点是相联存储器庞大,比较电路复杂,因此只适合于小容量的Cache 之用。
2. 直接相联映射
直接相联映射方式是指主存的某块j 只能映射到满足如下特定关系的Cache 块i 中:
i =j mod 2C (4.2)
图4-30直接相联映射方式
上图中,主存的第0、2C 、2C +1、… 块只能映射到Cache 的第0块,主存的第1、2C +1、2C +1+1、… 块只能映射到Cache 的第1
块,… … ,主存的第2C -1、2C +1-1、…2M -1块只能映射到Cache 的第2C -1块。
在直接相联映射方式下,CPU 的访主存地址为如下形式:
其中,T 为标志号,C 为Cache 的块号,W 为块内的字号。在这里,原主存的块号M 实际上被分成了两个字段:T 和C ,其中C 用于指出主存的块可以映射的Cache 的块。一般来讲,主存的块数是Cache 的块数的整数倍,也就是说主存的块数2M 和Cache 的块数2C 满足关系式:2M =n·2C
在直接相联映射方式下,标志号T 是随Cache 的每个块一起存储的,其地址转换过程如图4-31所示。
图4-31直接相联映射的地址转换
当一个主存块调入Cache 中时,会同时将主存地址的T 标志存入Cache 块的标志字段中。当CPU 送来一个访存地址时,首先,根据该主存地址的C 字段找到Cache 的相应块,然后将该块标志字段中存放的标志与主存地址的T 标志进行比较,若相符,说明主存的块目前已调入该Cache 块中,则命中,于是使用主存地址的W 字段访问该Cache 块的相应字单元;若不相符,则未命中,于是使用主存地址直接访主存。
直接相联映射方式的优点是比较电路最简单,但缺点是Cache 块冲突率较高,从而降低了Cache 的利用率。由于主存的每一块只能映射到Cache 的一个特定块上,当主存的某块需调入Cache 时,如果对应的Cache 特定块已被占用,而Cache 中的其它块即使空闲,主存的块也只能通过替换的方式调入特定块的位置,不能放置到其它块的位置上。
3. 组相联映射
以上两种方式各有优缺点,而且非常有趣的是,它们的优缺点正
好相反,也就是说,对于全相联映射方式来说为优点的恰是直接相联映射方式的缺点,而对于全相联映射方式来说为缺点的恰是直接相联映射方式的优点。那么,可否找到一种能较好地兼顾这两种方式的优点的映射方式呢?下面我们就来看看组相联映射方式 在这种方式下,将Cache 分成2u 组,每组包含2v 块。主存的块与Cache 的组之间采用直接相联映射,而与组内的各块则采用全相联映射。也就是说,主存的某块只能映射到Cache 的特定组中的任意一块。主存的某块j 与Cache 的组k 之间满足如下关系:
k =j mod 2u (4.3)
设主存共有2s ×2u 块(即M =s+u),则它们的映射关系如下图4-32示。
图4-32组相联映射方式
图中,主存的块0、2u 、2u +1、…、(2s -1)2u 可以映射到Cache 的第0组的任意一块,主存的块1、2u +1、2u +1+1、…、(2s -1)2u +1可以映射到Cache 的第1组的任意一块,… … ,主存的块2u -1、2u +1-1、…、2M -1可以映
射到Cache 的第2u -1组的任意一块。
在组相联映射方式下,CPU 的访主存地址和访Cache 地址分别为如下形式:
其中,u 为Cache 的组号,v 为组内的块号。Cache 的块号C =u+v,而主存的块号M =s+u。也就是说,主存块地址的后u 位指出了主存的这一块所能映射的Cache 的组。
与全相联映射方式类似的是,在组相联映射方式下,主存地址到Cache 地址的转换也是通过查找一个由相联存储器实现的块表来完成的,其形成过程如图4-33所示。
图4-33组相联映射的地址转换
当一个主存块调入Cache 中时,会同时将其主存块地址的前s 位写入一个由相联存储器实现的快表的对应Cache 块项的s 字段中。例如,设主存的某块调入Cache 的第1组的第2块中,则在快表的组1第3项的s 字段会登记下该主存块地址的前s 位。