Research on the speculative Processing of computer systems based on the information theory approach

本研究考察了信息论领域中讨论的各种通用数据预测技术在计算机系统中的推测处理中的应用。两个研究小组，信息理论小组和计算机体系结构小组共同开展了这项研究，并建立了适合计算机系统中推测处理的数据结构。此外，我们设计了使用该数据结构的推测执行体系结构，并对其性能进行了评估。本研究的主要成果如下：1.研究成果。适合推测处理的反字典数据结构研究了一种称为反字典的压缩方法，该压缩方法使用对于数据序列不出现的最小序列的集合。我们提出了一种使用后缀树构造二进制串的反词典的快速且节省内存的算法。证明了该算法的时间和空间复杂度是线性的，并通过仿真实验验证了该算法的有效性。针对微处理器的分支预测，提出了一种结合分支历史和指令地址的模式匹配分支预测方案，并对其预测精度进行了测试。在不受计算复杂度或硬件资源数量限制的情况下，验证了该方案与传统的只利用分支历史进行分支预测相比具有较好的预测精度。为了实现高效运行的预测交换路由器，我们提出了减少预测错误报文的技术，以及检测和消除预测错误报文的技术。在考虑动态通信冲突的情况下，我们通过仿真对预测切换的效果进行了评估，并验证了该技术的高性能。

This research examined the various universal data prediction techniques argued in the field of information theory as application to the speculative processing in computer systems. Two research groups, the information theory group and the computer architecture group, jointly carried out the research and build the data structure suitable for the speculative processing in computer systems. Moreover, we designed the speculation execution architecture which uses the proposed data structure, and evaluated its performance. The main results of this research are as follows.1. Antidictionary data structure suitable for speculative processingThe compressing method called the anti-dictionary using the set of the minimum series which does not appear for a data series was examined. We present a fast and memory-efficient algorithm to construct an antidictionary for a binary string using a suffix tree. It is proved that the complexity of the algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results.2. Branch prediction for microprocessorsThe branch prediction scheme using the pattern matching with a branch history and an instruction address was proposed, and its prediction accuracy was examined. We verified the good prediction accuracy of the scheme compared with the conventional branch prediction only using a branch history when there was no restriction of computational complexity or the amount of hardw are resources.3. Switching router with predictionsIn order to realize the predictive switching router which operates efficiently, we proposed the technique of reducing prediction mistake packets, and the technology of detecting and canceling a prediction mistake packet. We performed the evaluation by a simulation about the effect of predictive switching in consideration of a dynamic communication collision and verified the high performance of the proposed technique.