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.