Hierarchical Binary Set Partitioning in Cache Memories

In this paper, a new cache placement scheme is proposed to achieve higher hit ratios with respect to the two conventional schemes namely set-associative and direct mapping. Similar to set-associative, in this scheme, cache space is divided into sets of different sizes. Hence, the length of tag fields associated to each set is also variable and depends on the partition it is in. The proposed mapping function has been simulated with some standard trace files and statistics are gathered and analyzed for different cache configurations. The results reveal that the proposed scheme exhibits a higher hit ratio compared to the two well-known mapping schemes, namely set-associative and direct mapping, using LRU replacement policy.     

General method of testing the compatibility of interacting automata with finite memory

A method is proposed for compatibility analysis of two interacting partial nondeterministic automata A and B specified in a first-order language with monadic predicates. In contrast to a method proposed earlier, no restrictions are imposed on the form of specification of the automaton B. These investigations were partially supported by INTAS grant 96-0760. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 25–37, November–December, 1999.     

Performance Metrics and Models for Shared Cache

Performance metrics and models are prerequisites for scientific understanding and optimization. This paper introduces a new footprint-based theory and reviews the research in the past four decades leading to the new theory. The review groups the past work into metrics and their models in particular those of the reuse distance, metrics conversion, models of shared cache, performance and optimization, and other related techniques.     

拟（h,k）存贮有限自动机的可逆性

主要研究拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆性,以及它的弱逆,得到了拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k＋1步弱可逆拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱逆。     

关于二元延迟3步前馈逆有限自动机的结构

前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥3的前馈逆结构的刻划,则是一个长期的未解决问题.研究了二元延迟3步前馈逆有限自动机的结构.对于自治有限自动机M_a的状态图为圈的二元延迟3步弱可逆半输入存储有限自动机C(M_af ),给出了其长3极小输出权分别为1,2,8三种情形下结构的一种刻画.由于C(M_af )延迟3步弱可逆当且仅当它是延迟3步弱逆,因此,得到了二元延迟3步前馈逆有限自动机结构的一种部分刻画.     

拟(h,k)存贮有限自动机的可逆性

主要研究拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆性,以及它的弱逆,得到了拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k+1步弱可逆拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱逆.     

PCI协议对Cache的支持

论述了Ｃａｃｈｅ在高性能计算机系统中的作用和访问Ｃａｃｈｅ的过程,以及Ｃａｃｈｅ数据一致性问题和解决的方法,介绍和分析了ＰＣＩ协议对Ｃａｃｈｅ的支持。     

解决中央处理器运算速度与内存系统性能矛盾的一种方案

中央处理器-存储器集成是解决当前处理器运算速度与传统的存储器系统性能滞后的一种新思路。文章运用一个简单的评价模型和模拟运行,分析了几种处理器-存储器集成的方案。     

一类NFA 到DFA 的直接转化方法

NFA的确定化具有重要的理论和实际意义.迄今为止,普遍采用子集构造法将一个NFA(非确定性自动机)转化为DFA(确定性自动机),但这种方法需要引入空输入ε及状态子集I的ε-闭包,其计算过程相对繁琐.而且在确定化过程中对于NFA状态集存在ε-closure重复计算和由于对非ε转换的判断而引起的重复计算等问题.本文描述了一种将一类NFA直接转化为DFA的方法.在本方法中,不需要引入空输入ε,可根据原始的NFA状态图或状态转移表直接得出等价的DFA状态图或状态转移表,而且所有状态都是单一的状态而非集合状态,便于软硬件实现与测试.     

概率有限自动机的积和分解

给出几种概率有限自动机的积;讨论了他们之间的相互关系;并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解;证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。     

弱可逆拟(r,r)阶存贮线性有限自动机的分解

通过对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机输出权的研究,得出对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机的任意一个状态,它的长r的输出权都是1;任何一个n元拟(r,r)阶存贮线性有限自动机M延迟r步弱可逆的充分必要条件是M都可以分解为一个延迟0步弱可逆有限自动机M0和一个延迟r步弱可逆拟(0,r)阶存贮线性有限自动机M1。     

一种将NFA到最小化DFA的方法

词法分析是编译程序重要阶段,有效的词法分析可提高编译程序的效率。本文提出用子集方法完成NFA到DFA并使用树型分割法实现DFA到最小化DFA的化简。     

Enhancing MC68030 performance using the SN74ACT2155 cache

Texas Instruments highlights the important questions facing the system designer who needs to interface a cache to a fast microprocessor, giving an example solution using its cache chip     

On the design of on-chip instruction caches

Cache memories reduce memory latency and traffic in computing systems. Most existing caches are implemented as board-based systems. Advancing VLSI technology will soon permit significant caches to be integrated on chip with the processors they support. In designing on-chip caches, the constraints of VLSI become significant. The primary constraints are economic limitations on circuit area and off-chip communications. The paper explores the design of on-chip instruction-only caches in terms of these constraints. The primary contribution of this work is the development of a unified economic model of on-chip instruction-only cache design which integrates the points of view of the cache designer and of the floorplan architect. With suitable data, this model permits the rational allocation of constrained resources to the achievement of a desired cache performance. Specific conclusions are that random line replacement is superior to LRU replacement, due to an increased flexibility in VLSI floorplan design; that variable set associativity can be an effective tool in regulating a chip's floorplan; and that sectoring permits area efficient caches while avoiding high transfer widths. Results are reported on economic functionality, from chip area and transfer width to miss ratio. These results, or the underlying analysis, can be used by microprocessor architects to make intelligent decisions regarding appropriate cache organizations and resource allocations.     

存储系统模拟器SiMemSy的设计与实现

由于存储器间距日益扩大 ,存储系统对计算机系统整体性能的影响越来越严重 ,存储系统模拟器的研究与开发也日益重要 .传统的模拟器更多地将注意力集中于对 Cache的模拟 ,而对存储系统整体的模拟不够 .为了模拟并分析存储系统各部分的性能与其对存储系统整体性能的影响 ,本文设计并实现存储系统模拟器 Si Mem Sy(SImulator ofMEMory SYstem) .实验表明 ,Si Mem Sy可以准确、高效地对存储系统进行模拟并得到可信的结果