共查询到20条相似文献,搜索用时 31 毫秒
1.
In the past decade, the exponential growth in commodity CPU's speed has far outpaced advances in memory latency. A second trend is that CPU performance advances are not only brought by increased clock rates, but also by increasing parallelism inside the CPU. Current database systems have not yet adapted to these trends and show poor utilization of both CPU and memory resources on current hardware. In this paper, we show how these resources can be optimized for large joins and translate these insights into guidelines for future database architectures, encompassing data structures, algorithms, cost modeling and implementation. In particular, we discuss how vertically fragmented data structures optimize cache performance on sequential data access. On the algorithmic side, we refine the partitioned hash-join with a new partitioning algorithm called "radix-cluster", which is specifically designed to optimize memory access. The performance of this algorithm is quantified using a detailed analytical model that incorporates memory access costs in terms of a limited number of parameters, such as cache sizes and miss penalties. We also present a calibration tool that extracts such parameters automatically from any computer hardware. The accuracy of our models is proven by exhaustive experiments conducted with the Monet database system on three different hardware platforms. Finally, we investigate the effect of implementation techniques that optimize CPU resource usage. Our experiments show that large joins can be accelerated almost an order of magnitude on modern RISC hardware when both memory and CPU resources are optimized 相似文献
2.
随着存储系统的访问速度与处理器的运算速度的差距越来越显著,访存性能已成为提高计算机系统性能的瓶颈.通过对指令Cache和数据Cache失效行为的分析,提出一种预取策略--结合访存失效队列状态的预取策略.该预取策略保持了指令和数据访问的次序,有利于预取流的提取.并将指令流和数据流的预取相分离,避免相互替换.在预取发起时机的选择上,不但考虑当前总线是否空闲,而且结合访存失效队列的状态,减小对处理器正常访存请求的影响.通过流过滤机制提高预取准确性,降低预取对访存带宽的需求.结果表明,采用结合访存失效队列状态的预取策略,处理器的平均访存延时减少30%,SPEC CPU2000程序的IPC值平均提高8.3%. 相似文献
3.
随着处理器和存储器速度差距的不断拉大,访存指令尤其是频繁cache miss的指令成为影响性能的重要瓶颈。编译器由于无法得知访存指令动态执行的拍数,一般假定这些指令的延迟为cache命中或者cache miss的延迟,所以并不准确。我们引入cache profiling技术来收集访存指令运行时的cache miss或者命中的信息,利用这些信息来计算访存的延迟。乱序机器上硬件的指令调度对于发射窗口内的指令能进行很好的动态调度,编译器则对更长的范围内的指令调度更有优势。在reorder buffer中cache miss一旦发生,容易引起reorder buffer满,导致流水线阻塞。调度容易cache miss的指令。使其并行执行,从而隐藏cache miss的长延迟,就可以提高程序性能。因此,我们针对load指令,一方面修改频繁miss的指令的延迟,一方面修改调度策略,提高存储级并行度。实验证明,我们的调度对于bzip2有高达4.8%的提升,art有4%的提升,整体平均提高1.5%。 相似文献
4.
Recent results in the Rio project at the University of Michigan show that it is possible to create an area of main memory
that is as safe as disk from operating system crashes. This paper explores how to integrate the reliable memory provided by
the Rio file cache into a database system. Prior studies have analyzed the performance benefits of reliable memory; we focus
instead on how different designs affect reliability. We propose three designs for integrating reliable memory into databases:
non-persistent database buffer cache, persistent database buffer cache, and persistent database buffer cache with protection.
Non-persistent buffer caches use an I/O interface to reliable memory and require the fewest modifications to existing databases.
However, they waste memory capacity and bandwidth due to double buffering. Persistent buffer caches use a memory interface
to reliable memory by mapping it into the database address space. This places reliable memory under complete database control
and eliminates double buffering, but it may expose the buffer cache to database errors. Our third design reduces this exposure
by write protecting the buffer pages. Extensive fault tests show that mapping reliable memory into the database address space
does not significantly hurt reliability. This is because wild stores rarely touch dirty, committed pages written by previous
transactions. As a result, we believe that databases should use a memory interface to reliable memory.
Received January 1, 1998 / Accepted June 20, 1998 相似文献
5.
Conventional implementations of iterative numerical algorithms, especially multigrid methods, merely reach a disappointing
small percentage of the theoretically available CPU performance when applied to representative large problems. One of the
most important reasons for this phenomenon is that the need for data locality due to poor main memory latency and limited
bandwidth is entirely neglected by many developers designing numerical software. Only when most of the data to be accessed
during the computation are found in the system cache (or in one of the caches if the machine architecture comprises a cache
hierarchy) fast program execution can be expected. Otherwise, i.e. in case of a significant rate of cache misses, the processor
must stay idle until the necessary operands are fetched from main memory, whose cycle time is in general extremely large compared
to the time needed to execute a floating point instruction. In this paper, we describe program transformation techniques developed
to improve the cache performance of two-dimensional multigrid algorithms. Although we merely consider the solution of Poisson's
equation on the unit square using structured grids, our techniques provide valuable hints towards the efficient treatment
of more general problems.
Received January 31, 1999; revised October 17, 1999 相似文献
6.
The speed gap between processor and main memory is the major performance bottleneck of modern computer systems. As a result,
today's microprocessors suffer from frequent cache misses and lose many CPU cycles due to pipeline stalling. Although traditional
data prefetching methods considerably reduce the number of cache misses, most of them strongly rely on the predictability
for future accesses and often fail when memory accesses do not contain much locality.
To solve the long latency problem of current memory systems, this paper presents the design and evaluation of our high-performance
decoupled architecture, the HiDISC (Hierarchical Decoupled Instruction Stream Computer). The motivation for the design originated
from the traditional decoupled architecture concept and its limits. The HiDISC approach implements an additional prefetching
processor on top of a traditional access/execute architecture. Our design aims at providing low memory access latency by separating
and decoupling otherwise sequential pieces of code into three streams and executing each stream on three dedicated processors.
The three streams act in concert to mask the long access latencies by providing the necessary data to the upper level on time.
This is achieved by separating the access-related instructions from the main computation and running them early enough on
the two dedicated processors.
Detailed hardware design and performance evaluation are performed with development of an architectural simulator and compiling
tools. Our performance results show that the proposed HiDISC model reduces 19.7% of the cache misses and improves the overall
IPC (Instructions Per Cycle) by 15.8%. With a slower memory model assuming 200 CPU cycles as memory access latency, our HiDISC
improves the performance by 17.2%. 相似文献
7.
Smartcards are the most secure portable computing device today. They have been used successfully in applications involving
money, and proprietary and personal data (such as banking, healthcare, insurance, etc.). As smartcards get more powerful (with
32-bit CPU and more than 1 MB of stable memory in the next versions) and become multi-application, the need for database management
arises. However, smartcards have severe hardware limitations (very slow write, very little RAM, constrained stable memory,
no autonomy, etc.) which make traditional database technology irrelevant. The major problem is scaling down database techniques
so they perform well under these limitations. In this paper, we give an in-depth analysis of this problem and propose a PicoDBMS
solution based on highly compact data structures, query execution without RAM, and specific techniques for atomicity and durability.
We show the effectiveness of our techniques through performance evaluation.
Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 23 July 2001 相似文献
8.
Relational database systems have traditionally optimized for I/O performance and organized records sequentially on disk pages
using the N-ary Storage Model (NSM) (a.k.a., slotted pages). Recent research, however, indicates that cache utilization and
performance is becoming increasingly important on modern platforms. In this paper, we first demonstrate that in-page data
placement is the key to high cache performance and that NSM exhibits low cache utilization on modern platforms. Next, we propose
a new data organization model called PAX (Partition Attributes Across), that significantly improves cache performance by grouping
together all values of each attribute within each page. Because PAX only affects layout inside the pages, it incurs no storage
penalty and does not affect I/O behavior. According to our experimental results (which were obtained without using any indices
on the participating relations), when compared to NSM: (a) PAX exhibits superior cache and memory bandwidth utilization, saving
at least 75% of NSM's stall time due to data cache accesses; (b) range selection queries and updates on memory-resident relations
execute 17–25% faster; and (c) TPC-H queries involving I/O execute 11–48% faster. Finally, we show that PAX performs well
across different memory system designs.
Received: November 1, 2001 / Accepted: August 29, 2002 Published online: November 22, 2002 相似文献
9.
随着大数据应用的涌现,计算机系统需要更大容量的内存以满足大数据处理的高时效性需求.新型非易失性存储器(non-volatile memory,NVM)结合传统动态随机存储器(dynamic random access memory, DRAM)组成的混合内存系统具有内存容量大、功耗低的优势,因而得到了广泛关注.大数据应用同时也面临着旁路转换缓冲器(translation lookaside buffer, TLB)缺失率过高的性能瓶颈.大页可以有效降低TLB缺失率,然而,在混合内存中支持大页面临着大页迁移开销过大的问题.因此,设计了一种支持大页和大容量缓存的层次化混合内存系统:DRAM和NVM分别使用4KB和2MB粒度的页面分别进行管理,同时在DRAM和NVM之间实现直接映射.设计了基于访存频率的DRAM缓存数据过滤机制,减轻了带宽压力.提出了基于内存实时信息的动态热度阈值调整策略,灵活适应应用访存特征的变化.实验显示:与使用大页的全NVM内存系统和缓存热页(caching hot page, CHOP)系统相比平均有69.9%和15.2%的性能提升,而与使用大页的全DRAM内存系统相比平均只有8.8%的性能差距. 相似文献
10.
On-chip caches to reduce average memory access latency are commonplace in today's commercial microprocessors. These on-chip caches generally have low associativity and small cache sizes. Cache line conflicts are the main source of cache misses, which are critical for overall system performance. This paper introduces an innovative design for on-chip data caches of microprocessors, called one's complement cache. While binary complement numbers have been successfully used in designing arithmetic units, to the best of our knowledge, no one has ever considered using such complement numbers in cache memory designs. This paper will show that such complement numbers help greatly in reducing cache misses in a data cache, thereby improving data cache performance. By parallel computation of cache addresses and memory addresses, the new design does not increase the critical hit time of cache accesses. Cache misses caused by line interference are reduced by evenly distributing data items referenced by program loops across all sets in a cache. Even distribution of data in the cache is achieved by making the number of sets in the cache a prime or an odd number, so that the chance of related data being mapped to a same set is small. Trace-driven simulations are used to evaluate the performance of the new design. Performance results on benchmarks show that the new design improves cache performance significantly with negligible additional hardware cost. 相似文献
11.
Physical data independence is touted as a central feature of modern
database systems. It allows users to frame queries in terms of the logical
structure of the data, letting a query processor automatically translate
them into optimal plans that access physical storage structures. Both
relational and object-oriented systems, however, force users to frame their
queries in terms of a logical schema that is directly tied to physical
structures. We present an approach that eliminates this dependence. All
storage structures are defined in a declarative language based on
relational algebra as functions of a logical schema. We present an
algorithm, integrated with a conventional query optimizer, that translates
queries over this logical schema into plans that access the storage
structures. We also show how to compile update requests into plans that
update all relevant storage structures consistently and optimally.
Finally, we report on experiments with a prototype implementation of our
approach that demonstrate how it allows storage structures to be tuned to
the expected or observed workload to achieve significantly better
performance than is possible with conventional techniques.
Edited by
Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received
September 15, 1994 / Accepted September 1, 1995 相似文献
12.
随着主存速度和现代处理器速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈,Cache行为对主存数据库系统更加重要.索引技术是主存数据库系统设计的关键部分.在CST-树的基础上应用预取技术提高查找操作的性能,提出了一种Cache优化的索引结构预取T-树(pT-tree).pT-树使用预取技术有效地创建比正常数据传... 相似文献
13.
Finding the best data layout has been an ultimate goal of memory optimization. Even with data access profile, heuristic algorithms are needed to reorganize data layout for better locality. The best layout could be found by running the given application with all possible data layouts and selecting the best performing layout. This approach, however, can incur too much overhead, particulary when the number of possible layouts are too many. In this paper, we present a composition-based cache simulation for structure reorganization. Instead of running all possible layouts, we simulate only the primary subsets of layouts and compose the cache misses for all layouts by summing up the cache misses of component subsets. Our experiment with the composition-based cache simulation shows that the differences in the cache misses are within 10% of the full cache simulation for 4-way and 8-way set associative caches. In addition to the cache miss estimation, our heuristic algorithm takes account of the extra instruction overhead incurred by structure reorganization. Our experiment with several structure intensive benchmarks shows the 37% reduction in the L1D read misses and the 28% reduction in the L2 read misses. As a result, the execution times are also reduced by 19% on average. 相似文献
14.
Traditional algorithms for optimizing the execution order of joins are no more valid when selections and projections involve
methods and become very expensive operations. Selections and projections could be even more costly than joins such that they
are pulled above joins, rather than pushed down in a query tree. In this paper, we take a fundamental look at how to approach
query optimization from a top-down design perspective, rather than trying to force one model to fit into another. We present
a graph model which is designed to characterize execution plans. Each edge and each vertex of the graph is assigned a weight
to model execution plans. We also design algorithms that use these weights to optimize the execution order of operations.
A cost model of these algorithms is developed. Experiments are conducted on the basis of this cost model. The results show
that our algorithms are superior to similar work proposed in the literature.
Received 20 April 1999 / Accepted 9 August 2000 Published online 20 April 2001 相似文献
15.
Main memory cache performance continues to play an important role in determining the overall performance of object-oriented,
object-relational and XML databases. An effective method of improving main memory cache performance is to prefetch or pre-load
pages in advance to their usage, in anticipation of main memory cache misses. In this paper we describe a framework for creating
prefetching algorithms with the novel features of path and cache consciousness. Path consciousness refers to the use of short
sequences of object references at key points in the reference trace to identify paths of navigation. Cache consciousness refers
to the use of historical page access knowledge to guess which pages are likely to be main memory cache resident most of the
time and then assumes these pages do not exist in the context of prefetching. We have conducted a number of experiments comparing
our approach against four highly competitive prefetching algorithms. The results shows our approach outperforms existing prefetching
techniques in some situations while performing worse in others. We provide guidelines as to when our algorithm should be used
and when others maybe more desirable. 相似文献
16.
SDRAM,SSRAM对于平衡存储器和CPU的带宽,实现主存的猝发访问,提高系统性能价格比有重要意义,本文基于Pentium处理器,讨论了高速缓存和主存采用SSRAM,SDRAM的不同系统实现方法及相对性能,不同的系统实现就是在性能,价格和设计复杂性之间的取舍,此分析同样适用于任何嵌入式一级高速缓存的处
处理器。 相似文献
17.
In this paper, we revisit the problem of performance prediction on SMP machines, motivated by the need for selecting parallelization strategy for random write reductions. Such reductions frequently arise in data mining algorithms. In our previous work, we have developed a number of techniques for parallelizing this class of reductions. Our previous work has shown that each of the three techniques, full replication, optimized full locking, and cache-sensitive, can outperform others depending upon problem, dataset, and machine parameters. Therefore, an important question is, “Can we predict the performance of these techniques for a given problem, dataset, and machine?”. This paper addresses this question by developing an analytical performance model that captures a two-level cache, coherence cache misses, TLB misses, locking overheads, and contention for memory. Analytical model is combined with results from micro-benchmarking to predict performance on real machines. We have validated our model on two different SMP machines. Our results show that our model effectively captures the impact of memory hierarchy (two-level cache and TLB) as well as the factors that limit parallelism (contention for locks, memory contention, and coherence cache misses). The difference between predicted and measured performance is within 20% in almost all cases. Moreover, the model is quite accurate in predicting the relative performance of the three parallelization techniques. 相似文献
18.
The problem of answering queries using views is to find efficient methods of answering a query using a set of previously
materialized views over the database, rather than accessing the database relations. The problem has received significant attention
because of its relevance to a wide variety of data management problems, such as data integration, query optimization, and
the maintenance of physical data independence. To date, the performance of proposed algorithms has received very little attention,
and in particular, their scale up in the presence of a large number of views is unknown. We first analyze two previous algorithms,
the bucket algorithm and the inverse-rules, and show their deficiencies. We then describe the MiniCon, a novel algorithm for
finding the maximally-contained rewriting of a conjunctive query using a set of conjunctive views. We present the first experimental
study of algorithms for answering queries using views. The study shows that the MiniCon scales up well and significantly outperforms
the previous algorithms. We describe an extension of the MiniCon to handle comparison predicates, and show its performance
experimentally. Finally, we describe how the MiniCon can be extended to the context of query optimization.
Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001 相似文献
19.
Data transfers and storage are crucial cost factors in multimedia systems. Systematic methodologies are needed to obtain dramatic reductions in terms of power, area and cycle count. Upcoming multimedia processing applications will require high memory bandwidth. In this paper, we estimate that a software reference implementation of an MPEG-4 video encoder typically requires five Gtransfers/s to main memory for a simple profile level L2. This shows a clear need for optimization and the use of intermediate memory stages. By applying our ACROPOLIS methodology, developed mainly to relieve this data access bottleneck, we have arrived at an implementation which needs a factor 65 less background accesses. In addition, we also show that we can heavily improve on the memory transfers, without sacrificing speed (even gaining about 10% on cache misses and cycles for a DEC Alpha), by aggressive source code transformations 相似文献
20.
Recently, to relieve the performance degradation caused by the bottleneck between CPU and main memory, cache conscious multi-dimensional index structures have been proposed. The ultimate goal of them is to reduce the space for entries so as to widen index trees and minimize the number of cache misses. The existing index structures can be classified into two approaches according to their entry reduction methods. One approach is to compress MBR keys by quantizing coordinate values to the fixed number of bits. The other approach is to store only the sides of minimum bounding regions (MBRs) that are different from their parents partially. The second approach works well when the size of a node is small and the number of entries is small. In this paper, we investigate the existing multi-dimensional index structures for main memory database systems through experiments under the various work loads. Then, we propose a new index structure that exploits the properties of the both techniques. We implement existing multi-dimensional index structures and the proposed index structure. We perform various experiments to show that our approach outperforms others. 相似文献
|