Elastic memory: Buddy systems interface

To implement single-ended flexible arrays (‘elastic memory’) a class of underlying dynamic storage allocation methods called buddy systems may be used to allocate fixed blocks of memory of restricted choices of size. Arrays are implemented in one approach as contiguous blocks of memory and in another as two-level structures. Each approach is combined with three buddy methods for allocating blocks of memory, making six methods in all. This paper illustrates the general ideas of implementing elastic memory mechanisms in terms of the buddy system interface.     

A top-down processor allocation scheme for hypercube computers

An efficient processor allocation policy is presented for hypercube computers. The allocation policy is called free list since it maintains a list of free subcubes available in the system. An incoming request of dimension k (2^k nodes) is allocated by finding a free subcube of dimension k or by decomposing an available subcube of dimension greater than k. This free list policy uses a top-down allocation rule in contrast to the bottom-up approach used by the previous bit-map allocation algorithms. This allocation scheme is compared to the buddy, gray code (GC), and modified buddy allocation policies reported for the hypercubes. It is shown that the free list policy is optimal in a static environment, as are the other policies, and it also gives better subcube recognition ability compared to the previous schemes in a dynamic environment. The performance of this policy, in terms of parameters such as average delay, system utilization, and time complexity, is compared to the other schemes to demonstrate its effectiveness. The extension of the algorithm for parallel implementation, noncubic allocation, and inclusion/exclusion allocation is also given     

μC/OSII内存管理技术的研究

在μC/OSII中，当应用任务在申请到的内存块中产生了非法指针，并且指针地址指向了空闲内存块头结构区时（前几个字节），空闲链表将会被破坏。为解决这一隐患，将控制信息与用户空间独立存放。该文通过扩展内存块定位字节至16位，得到一种能够区分1 024个不同内存块的一级内存管理算法。     

基于任务相关性的机务虚拟维修系统的场景管理

为解决机务虚拟维修训练系统中场景、模型一次性全部加载速度慢、内存占用量高的问题,基于任务的相关性提出一种场景管理方法。使用TF-IDF算法获取系统中包含的虚拟维修任务工卡的相似度并进行划分。工卡的相似度越高表示所描述的虚拟维修场景、维修工具、维修对象等虚拟资源相关性越强。当在场景资源加载、内存分配时,将相关性大于68%的任务工卡描述的虚拟资源利用伙伴系统进行加载分配,对于相关性小于42%的任务场景,则在伙伴系统中申请一块内存,并将这块内存划分为内存池进行加载分配。而任务相关性介于42%～68%的任务场景用双动态双链表的方法进行管理。解决了传统虚拟维修训练系统中加载资源时没有维修资源相关性分配管理的不足,分配方法没有任务针对性的局限,避免了单独划分内存块的系统分配时间。实验结果表明,改进后的分配方法减少了17%内存占用量,并提高了17.57的帧率。     

An on-chip cache compression technique to reduce decompression overhead and design complexity

This research explores a compressed memory hierarchy model which can increase both the effective memory space and bandwidth of each level of memory hierarchy. It is well known that decompression time causes a critical effect to the memory access time and variable-sized compressed blocks tend to increase the design complexity of the compressed memory systems. This paper proposes a selective compressed memory system (SCMS) incorporating the compressed cache architecture and its management method. To reduce or hide decompression overhead, this SCMS employs several effective techniques, including selective compression, parallel decompression and the use of a decompression buffer. In addition, fixed memory space allocation method is used to achieve efficient management of the compressed blocks. Trace-driven simulation shows that the SCMS approach can not only reduce the on-chip cache miss ratio and data traffic by about 35% and 53%, respectively, but also achieve a 20% reduction in average memory access time (AMAT) over conventional memory systems (CMS). Moreover, this approach can provide both lower memory traffic at a lower cost than CMS with some architectural enhancement. Most importantly, the SCMS is a more attractive approach for future computer systems because it offers high performance in cases of long DRAM latency and limited bus bandwidth.     

Linux内核伙伴系统分析

本文针对Linux内核实现的伙伴系统进行了抽象分析,并通过实例演示了算法的执行过程. 分析了用于物理地址空间管理的三级数据结构及其关系. 在此基础上,详细描述了用于分配和回收页框的伙伴算法. 对于待回收的内存块而言,计算其伙伴的索引及合并内存块的索引是回收操作的关键,讨论了相关计算方法的几条结论并予以证明.     

Efficient Management of Persistent Knowledge

Although computer speed has steadily increased and memory is getting cheaper, the need for storage managers to deal efficiently with applications that cannot be held into main memory is vital. Dealing with large quantities of clauses implies the use of persistent knowledge and thus, indexing methods are essential to access efficiently the subset of clauses relevant to answering a query. We introduce PerKMan, a storage manager that uses G-trees, and aims at efficient manipulation of large amounts of persistent knowledge. PerKMan may be connected to Prolog systems that offer an external C language interface. As well as the fact that the storage manager allows different arguments of a predicate to share a common index dimension in a novel manner, it indexes rules and facts in the same manner. PerKMan handles compound terms efficiently and its data structures adapt their shape to large dynamic volumes of clauses, no matter what the distribution. The storage manager achieves fast clause retrieval and reasonable use of disk space.     

内存管理算法优化及在游戏引擎中的实现

本文对C++动态内存管理算法进行了描述,对其中可能存在的问题进行了探讨并提出了解决方法。通过对原来内存管理链表的结构改进,提出了新的双向链式哈希结构并应用于插入式调试内存管理器来跟踪所有动态分配的内存。此内存管理器的特点在于搜索速度快,内存管理全面,接口是无缝的。该内存管理器算法在我们一个最新研发的一款游戏引擎中进行了应用并通过了测试,获得了良好的效果。     

一种多维并行报文分类算法

位并行、位向量和聚合位向量算法通过对多个域进行并行处理加快分类速度,但三者内存占用太大,不适用于大规则集。为此,提出一种压缩位并行算法,通过报文分类压缩每个域上的重复规则并重新组织规则集,从而缩短位图中位串的长度,减少内存空间的占用。实验结果证明,该压缩位并行算法在不影响运行速度的前提下,明显减少了空间占用。     

基于Event-B的航天器内存管理系统形式化验证

内存管理系统位于操作系统内核的最底层,为上层提供内存分配和回收机制.在航天器这类安全攸关的关键系统中,其可靠性和安全性至关重要,必须要考虑到强实时性、有限空间限制、高分配效率以及各种边界条件约束.因此,系统通常采用较为复杂的数据结构和算法来管理内存空间,同时需要采用非常严格的形式化方法来保证航天器这类安全攸关系统的高可信性.对复杂内存管理系统的形式化验证也会较之前的验证工作带来更多难题,主要体现在：内存管理模块中的复杂数据结构的形式化描述;操作的规范语义;行为的建模;内部函数的规范及断言定义与循环不变式的定义;实时性验证等方面.本文拟针对这些问题,深入分析实际的航天器操作系统内存管理系统的特性;探索基于分层迭代的语义描述与验证的一般性方法与理论,并应用这些理论方法,来验证一个具有实际应用的航天嵌入式操作系统的内存管理系统.本文研究成果有望被直接应用于我国新一代的航天器系统上.     

Memory access schedule minimization for embedded systems

The growing gap between microprocessor speed and DRAM speed is a major problem that computer designers are facing. In order to narrow the gap, it is necessary to improve DRAM’s speed and throughput. To achieve this goal, this paper proposes techniques to take advantage of the characteristics of the 3-stage access of contemporary DRAM chips by grouping the accesses of the same row together and interleaving the execution of memory accesses from different banks. A family of Bubble Filling Scheduling (BFS) algorithms are proposed in this paper to minimize memory access schedule length and improve memory access time for embedded systems.When the memory access trace is known in some application-specific embedded systems, this information can be fully utilized to generate efficient memory access schedules. The offline BFS algorithm can generate schedules which are 47.49% shorter than in-order scheduling and 8.51% shorter than existing burst scheduling on average. When memory accesses are received by the single memory controller in real time, the memory accesses have to be scheduled as they come. The online BFS algorithm in this paper serves this purpose and generates schedules which are 58.47% shorter than in-order scheduling and 4.73% shorter than burst scheduling on average. To improve the memory throughput and further reduce the memory access schedule, an architecture with dual memory controllers is proposed. According to the experimental results, the dual controller algorithm can generate schedules which are 62.89% shorter than in-order scheduling, 14.23% shorter than burst scheduling, and 10.07% shorter than single controller BFS algorithms on average.     

实时系统中的动态内存分配算法

针对实时系统中的内存分配问题,分析实时系统应用程序的行为特点,提出一种使用双级离散表和双级索引位图相结合的动态内存分配方法。对于较小的内存分配请求,使用位图索引来加快速度并且降低内存分割的次数。对于较大内存块,使用双级离散表的方法降低内存碎片。实验表明,该方法具有很低的内存碎片率和确定的响应时间,适合实时性要求较高的系统。     

Wait-free concurrent memory management by Create and Read until Deletion (CaRuD)

Summary. The acronym CaRuD represents an interface specification and an algorithm for the management of memory shared by concurrent processes. The memory cells form a directed acyclic graph. This graph is only modified by adding a new node with a list of reachable children, and by removing unreachable nodes. If memory is not full, the algorithm ensures wait-free redistribution of free nodes. It uses atomic counters for reference counting and consensus variables to ensure exclusive access. Performance is enhanced by using nondeterminacy guided by insecure knowledge. Experiments indicate that the algorithm is very suitable for multiprocessing. Received: July 1998 / Accepted: July 2000     

基于R-list的Top-K高效用项集挖掘算法

针对现有的一阶段Top-K高效用项集挖掘算法挖掘过程中阈值提升慢,迭代时生成大量候选项集造成内存占用过多等问题,提出一种基于重用链表(R-list)的Top-K高效用挖掘算法RHUM。使用一种新的数据结构R-list来存储并快速访问项集信息,无需第2次扫描数据库进行项集挖掘。该算法重用内存以保存候选集信息,结合改进的RSD阈值提升策略对数据进行预处理,期间采用更严格的剪枝参数在递归搜索的过程中同时计算多个项集的效用来缩小搜索空间。在不同类型数据集中的实验结果表明:RHUM算法在内存效率方面均优于其他一阶段算法,且在K值变化时能保持稳定。     

Worst case performance of weighted buddy systems

Summary In this paper we have studied the worst case performance of the weighted buddy system of memory management. Specifically we have derived lower bounds of two system parameters NETREQ and NETALLOC for a weighted buddy system in case of unrestricted request sequence and stated a few preliminary results for those parameters in case of allocation only request sequence. We have also given bounds for the same system parameters for exact-fit memory management algorithms to compare the results with those for buddy systems.     

基于强化学习方法的访存调度算法

在现代处理器中,存储控制器是处理器芯片对片外存储器进行访问的管理者和执行者,其中对访存过程的调度算法会对实际访存性能产生十分重要的影响。针对已有调度算法在不同负载特征下自适应性不足的问题,提出了一种基于强化学习方法的ALHS算法,通过对访存调度中页命中优先时的连续页命中上限次数进行自适应调整,习得最优策略。多种不同典型访存模式的模拟结果显示,相比传统的FR-FCFS,ALHS算法运行速度平均提升了10.98%,并且可以获得近似于最优策略的性能提升,表明该算法能够自主探索环境并自我优化。     

Program Behavior and the Page-Fault-Frequency Replacement Algorithm

Virtual memory is one of the major concepts that has evolved in computer architecture over the last decade. It has had a great impact on the design of new computer systems since it was first introduced by the designers of the Atlas computer in 1962. A virtual memory is usually divided into blocks of contiguous locations to allow an efficient mapping of the logical addresses into the physical address space. In this paper, we are concerned with paging systems, that is, systems for which the blocks of contiguous locations are of equal size. The memory system consists of two levels: main memory and auxiliary memory. The occurrence of a reference to a page that is currently not in main memory is called a page fault. A page fault results in the interruption of the program and the transfer of the referenced page from auxiliary to main memory.     

Fast neighbor lists for adaptive-resolution particle simulations

Particle methods provide a simple yet powerful framework for simulating both discrete and continuous systems either deterministically or stochastically. The inherent adaptivity of particle methods is particularly appealing when simulating multiscale models or systems that develop a wide spectrum of length scales. Evaluating particle–particle interactions using neighbor-finding algorithms such as cell lists or Verlet lists, however, quickly becomes inefficient in adaptive-resolution simulations where the interaction cutoff radius is a function of space. We present a novel adaptive-resolution cell list algorithm and the associated data structures that provide efficient access to the interaction partners of a particle, independent of the (potentially continuous) spectrum of cutoff radii present in a simulation. We characterize the computational cost of the proposed algorithm for a wide range of resolution spans and particle numbers, showing that the present algorithm outperforms conventional uniform-resolution cell lists in most adaptive-resolution settings.     

Outperforming LRU with an adaptive replacement cache algorithm

The self-tuning, low-overhead, scan-resistant adaptive replacement cache algorithm outperforms the least-recently-used algorithm by dynamically responding to changing access patterns and continually balancing between workload recency and frequency features. Caching, a fundamental metaphor in modern computing, finds wide application in storage systems, databases, Web servers, middleware, processors, file systems, disk drives, redundant array of independent disks controllers, operating systems, and other applications such as data compression and list updating. In a two-level memory hierarchy, a cache performs faster than auxiliary storage, but it is more expensive. Cost concerns thus usually limit cache size to a fraction of the auxiliary memory's size.