题目描述

密歇根大学的 $Erik G. Hallnor$ 和 $Steven K. Reinhardt$在 $ISCA$（国际计算机体系结构研讨会）$2000$ 上提出了一种全相联软件管理缓存设计。他们的主要贡献有两个：一种全相联内存结构的实用设计——间接索引缓存（$IIC$），以及一种专门为 $IIC$ 设计的新型替换算法——世代替换算法。他们分析了采用世代替换算法的 $IIC$ 作为传统二级缓存的直接透明替代品的性能，与 $4$ 路组相联 $LRU$ 结构相比，其缺失率降低了 $8$ 到 $85$，性能接近或超过（实际上不可行的）全相联真 $LRU$ 缓存。将这些缺失率纳入基础时序模型表明，在当前 $DRAM$ 延迟下，$IIC/$世代替换缓存可能与传统缓存竞争，并且随着$CPU$ 相对延迟的增加，其性能将超过传统缓存。

间接索引缓存（$IIC$）通过间接映射的方式提供了全相联数据存储的实用实现，类似于基于页表的虚拟地址到物理地址的转换。与虚拟地址转换不同，$IIC$ 对操作系统透明。此外，与虚拟内存不同，$IIC$ 在硬件中启动缺失处理，使软件不参与主存访问的关键路径。

我们在此关注的世代替换算法在论文中的描述如下：

“尽管 $IIC$ 设计独立于用于管理它的替换算法，但其效用取决于是否存在一种实用算法，能够在不产生不合理开销的情况下提供有竞争力的性能。本节介绍我们开发的一种新型算法，称为世代替换……

如上所述，世代替换的动机是应对二级缓存引用位提供的信息不足的问题。具体来说，在世代替换中，如果一个块在特定时间间隔内未设置其引用位，并且在最近一段时间内被频繁引用，则不将其视为替换候选。不幸的是，基于引用位维护甚至近似的引用频率计数器非常耗时。相反，我们将块分组到少量优先池中。我们将频繁引用的块提升到更高优先级的池，将未引用的块降级到更低优先级的池。在缺失时，从最低优先级的非空池中选择要替换的块。我们将该算法称为“世代替换”，基于频繁访问的块被提升到高级世代的概念，类似于分代垃圾收集中长寿对象的提升。”

图中说明了该算法。在图中，有 $4$ 个优先池。每个池是一个可变长度的 $FIFO$ 队列。命中时，仅设置块的引用位。每次缺失时，在获取新块后，算法按优先级从高到低的顺序依次检查每个池 $FIFO$ 的头部。如果头部块的引用位被设置，则将其提升到下一个更高优先级的池（最高优先级池中的块将留在原池）；如果引用位未设置，则将其降级到下一个更低优先级的池（最低优先级池中的块将被替换出缓存）。无论哪种情况，引用位都会被清除，块被放置在新池 $FIFO$ 的尾部。新获取的块被放置在最高优先级池的尾部，其引用位未设置。

您需要读取一系列 $IIC$ 访问请求，实现世代替换算法，并描述最终各池的存储状态。

输入

输入包含多个测试用例。每个测试用例以整数 $N$（$1 \leq N \leq 10$）开头，表示优先池的数量。随后的行描述 $IIC$ 的访问序列，格式如下：

0x12345678 2

其中 $8$ 位十六进制数表示 $CPU$ 请求的块地址，后面的整数表示该块被连续请求的次数。

例如，块请求序列 0x11111111（$3$ 次）、0x22222222（$4$ 次）、0x33333333（$1$ 次）将表示为：

0x11111111 3
0x22222222 4
0x33333333 1

块序列以 # 结束，测试用例以 $N = 0$ 结束。

输出

对于每个测试用例，按优先级从高到低（池$0$ 到池 $n-1$）输出每个池中块的地址（从队头到队尾）。每个池占一行，格式为：

PoolNumber: BlockAdd1 BlockAdd2 ... BlockAddm

假设每个测试用例开始时所有池均为空。

测试用例之间需输出一个空行。

输入数据 1

4
0x11111111 1
0x22222222 1
0x33333333 1
0x44444444 1
0x55555555 1
#
0

输出数据 1

0: 0x22222222
1: 0x33333333
2: 0x44444444
3: 0x55555555

来源

POJ 月赛 -- 2004.07.18