Jeffrey R. Spirn, Peter J. Denning · 1972
For many years, there has been interest in "program locality" as a phenomenon to be considered in storage allocation. This notion arises from the empirical observation that it is possible to run a program efficiently with only some fraction of its total instruction and data code in main storage at any given time. That virtual memory systems can be made to run at all demonstrates that program locality can be used to advantage; and though it is certainly possible to write a program which violates the principles of locality, it seems one must go out of one's way to do so.
Cited by 90Open access
Yutao Zhong, Wentao Chang · 2008
Reuse signature, or reuse distance pattern, is an accurate model for program memory accessing behaviors. It has been studied and shown to be effective in program analysis and optimizations by many recent works. However, the high overhead associated with reuse distance measurement restricts the scope of its application. This paper explores applying sampling in reuse signature collection to reduce the time overhead. We compare different sampling strategies and show that an enhanced systematic sampling with a uniform coverage of all distance ranges can be used to extrapolate the reuse distance distribution. Based on that analysis, we present a novel sampling method with a measurement accuracy of more than 99%. Our average speedup of reuse signature collection is 7.5 while the best improvement observed is 34. This is the first attempt to utilize sampling in measuring reuse signatures. Experiments with varied programs and instrumentation tools show that sampling has great potential in promoting the practical uses of reuse signatures and enabling more optimization opportunities.
Cited by 69
Huang, Xianglong, 1975- · Texas ScholarWorks (Texas Digital Library) · 2011
Cited by 0Open access
Kang Zhang, Narasimhaiah Gorla · Journal of Systems and Software · 2000
Cited by 1
Dong Chen · UR Research (University of Rochester) · 2019
Thesis (Ph. D.)-- University of Rochester. Department of Computer Science, 2019.
Cited by 0Open access
Chungmin Joo, Gunhee Kim · Korea Jouranl of Communication Studies · 2021
본 연구는 지역방송 종사자와 시청자를 대상으로 지역방송 뉴스의 지역성 구현 방안을 살펴보았다. 이를 위해 지역방송 뉴스 제작자와 지역 시청자를 대상으로 심층인터뷰를 실시하였다. 연구결과, 방송인과 시청자간에 지역방송 뉴스의 기능과 역할, 뉴스의 주제와 내용, 뉴스와 지역민의 이해관계, 뉴스의 보도대상에 대해 공통적인 의견도 있었지만, 차이점도 있었다. 그러나 지역방송의 여론 다양성 및 민주주의 활성화를 위한 역할에 대해서는 공통적인 의견은 없었고, 차이점만 있었다. 시청자들은 지역방송 뉴스가 지역성을 구현하기 위해서는 충분한 지역소식 전달, 지역 경제와 산업 활성화에 대한 관심, 지역현안에 대한 해결책 제시, 지역민의 언론접근권 보장, 지역의견 소통의 장 역할에 더 관심을 기울여야 한다고 응답하였다. 지역방송의 지역성 구현에 대한 구체적인 방안에 대해 방송인들은 이상적인 역할과 기능을 강조한데 비해, 시청자들은 지역사회의 현실을 고려한 역할과 기능을 강조하였다.
Cited by 0
Xianglong Huang, Stephen M Blackburn, Kathryn S Mckinley et al. · 2004
As improvements in processor speed continue to outpace improvements in cache and memory speed, poor locality increasingly degrades performance. Because copying garbage collectors move objects, they have an opportunity to improve locality. However, no static copying order is guaranteed to match program traversal orders. This paper introduces online object reordering (OOR) which includes a new dynamic, online class analysis for Java that detects program traversal patterns and exploits them in a copying collector. OOR uses runtime method sampling that drives just-in-time (JIT) compilation. For each hot (frequently executed) method, OOR analysis identifies the hot field accesses. At garbage collection time, the OOR collector then copies referents of hot fields together with their parent. Enhancements include static analysis to exclude accesses in cold basic blocks, heuristics that decay heat to respond to phase changes, and a separate space for hot objects. The overhead of OOR is on average negligible and always less than 2 % on Java benchmarks in Jikes RVM with MMTk. We compare program performance of OOR to static class-oblivious copying orders (e.g., breadth and depth first). Performance variation due to static orders is often low, but can be up to 25%. In contrast, OOR matches or improves upon the best static order since its historybased copying tunes memory layout to program traversal.
Cited by 0
Sriram Krishnamoorthy · OhioLink ETD Center (Ohio Library and Information Network) · 2008
Cited by 0Open access
Vera Rivera, Francisco Javier, Abella Ferrer, Jaume, González Colás, Antonio María et al. · RECERCAT (Consorci de Serveis Universitaris de Catalunya)
Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality. Performance of memory hierarchy can be improved by means of data and loop transformations. Tiling is a loop transformation that aims at reducing capacity misses by exploiting reuse at the lower levels of cache. Padding is a data transformation targeted to reduce conflict misses. We present an accurate cost model which makes use of the cache miss equations (CMEs) to guide tiling and padding transformations. It describes misses across different hierarchy levels and considers the effects of other hardware components such as branch predictors. We combine the cost model with a genetic algorithm (GA) to select the tile and pad factors that enhance the program. Our results show that this scheme is useful to optimize programs' performance. When compared to previous works, we observe that with a reasonable compile-time overhead, our approach obtains significant performance improvements for all studied kernels on a variety of architectures.
Cited by 0Open access
Moss, Eliot B. · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · 2004
Cited by 0
Thomas Rauber, Gudula Rünger · 2004
Numerical software for sequential or parallel machines with memory hierarchies can benefit from locality optimizations which are usually achieved by program restructuring or program transformations. In this paper we introduce and discuss program-based locality measures which can be used to guide the restructuring and transformation process at the program level. As an example we consider a popular solution method to solve ordinary differential equations provided in many scientific libraries.
Cited by 2
Roland Cheng, Chen Ding · 2015
Since a program may have an infinite number of inputs, it is difficult to measure the exact performance under all possible uses. In this paper, we use the notion of reuse distance and reuse signature to measure the variation of data locality across program inputs. We use two classes of programs. The first is integer programs from SPEC 2000 benchmark set, including Vpr, Mcf, Parser, Perl, Gzip, and Bzip. For this set we test the current version from their open-source web sites instead of (or in addition to) the ones in the benchmark set. The second class is commonly used interactive programs, including Latex, Ghostview, and Gnuplot. We compare the reuse signature of 126 inputs for these 9 programs and show different degrees of locality variation. For most programs, the reuse signature is mostly consistent across inputs, indicating that the reuse pattern can be exploited in system design and optimization. * The figures in this paper are generated by pdflatex and can be printed clearly on paper even though they may not display well on screen. 1
Cited by 0
Thomas Rauber, Gudula Rünger · International Journal of Foundations of Computer Science · 2004
Numerical software for sequential or parallel machines with memory hierarchies can benefit from locality optimizations which are usually achieved by program restructuring or program transformations. In this paper we introduce and discuss program-based locality measures which can be used to guide the restructuring and transformation process at program level. As example we consider a popular solution method to solve ordinary differential equations provided in many scientific libraries.
Cited by 1
(:Unav) · The Digital Archeological Record (tDAR) · 2018
Cited by 0Open access
Peter J. Denning, Kevin C. Kahn · 1975
A program model can be regarded as decomposible into two main parts. The macromodel captures the phase-transition behavior by specifying locality sets and their associated reference intervals (phases). The micromodel captures the reference patterns within phases. A semi-Markov model can be used at the macro level, while one of the simple early models (such as the random-reference or LRU stack) can be used at the micro level. This paper shows that, even in simplest form, this type of model is capable of reproducing known properties of empirical lifetime functions. A micromodel, alone without a macromodel, is incapable of doing so.
Cited by 29
Richard B. Bunt, Jennifer Murphy, Shikharesh Majumdar · ACM SIGMETRICS Performance Evaluation Review · 1984
Although the phenomenon of locality has long been recognized as the single most important characteristic of program behaviour, relatively little work has been done in attempting to measure it. Recent work has led to the development of an intrinsic measure of program locality based on the Bradford-Zipf distribution. Potential applications for such a measure are many, and include the evaluation of program restructuring methods (manual and automatic), the prediction of system performance, the validation of program behaviour models, and the enhanced understanding of the phenomena that characterize program behaviour. A consideration of each of these areas is given in connection with the proposed measure, both to increase confidence in the validity of the measure and to illustrate a methodology for dealing with such problems.
Cited by 19Open access
Albert Mingkun Yang, Erik Österlund, Tobias Wrigstad · 2020
The hierarchical memory system with increasingly small and increasingly fast memory closer to the CPU has for long been at the heart of hiding, or mitigating the performance gap between memories and processors. To utilise this hardware, programs must be written to exhibit good object locality. In languages like C/C++, programmers can carefully plan how objects should be laid out (albeit time consuming and error-prone); for managed languages, especially ones with moving garbage collectors, a manually created optimal layout may be destroyed in the process of object relocation. For managed languages that present an abstract view of memory, the solution lies in making the garbage collector aware of object locality, and strive to achieve and maintain good locality, even in the face of multi-phased programs that exhibit different behaviour across different phases.
Cited by 19
Peter J. Denning, Kevin C. Kahn · ACM SIGOPS Operating Systems Review · 1975
A program model can be regarded as decomposible into two main parts. The macromodel captures the phase-transition behavior by specifying locality sets and their associated reference intervals (phases). The micromodel captures the reference patterns within phases. A semi-Markov model can be used at the macro level, while one of the simple early models (such as the random-reference or LRU stack) can be used at the micro level. This paper shows that, even in simplest form, this type of model is capable of reproducing known properties of empirical lifetime functions. A micromodel, alone without a macromodel, is incapable of doing so.
Cited by 56Open access
Chen Ding, Yutao Zhong · ACM SIGPLAN Notices · 2003
Profiling can accurately analyze program behavior for select data inputs. We show that profiling can also predict program locality for inputs other than profiled ones. Here locality is defined by the distance of data reuse. Studying whole-program data reuse may reveal global patterns not apparent in short-distance reuses or local control flow. However, the analysis must meet two requirements to be useful. The first is efficiency. It needs to analyze all accesses to all data elements in full-size benchmarks and to measure distance of any length and in any required precision. The second is predication. Based on a few training runs, it needs to classify patterns as regular and irregular and, for regular ones, it should predict their (changing) behavior for other inputs. In this paper, we show that these goals are attainable through three techniques: approximate analysis of reuse distance (originally called LRU stack distance), pattern recognition, and distance-based sampling. When tested on 15 integer and floating-point programs from SPEC and other benchmark suites, our techniques predict with on average 94% accuracy for data inputs up to hundreds times larger than the training inputs. Based on these results, the paper discusses possible uses of this analysis.
Cited by 263
Mahmut Kandemir · ACM SIGPLAN Notices · 2001
Exploiting spatial and temporal locality is essential for obtaining high performance on modern computers. Writing programs that exhibit high locality of reference is difficult and error-prone. Compiler researchers have developed loop transformations that allow the conversion of programs to exploit locality. Recently, transformations that change the memory layouts of multi-dimensional arrays---called data transformations---have been proposed. Unfortunately, both data and loop transformations have some important draw-backs. In this work, we present an integrated framework that uses loop and data transformations in concert to exploit the benefits of both approaches while minimizing the impact of their disadvantages. Our approach works inter-procedurally on acyclic call graphs, uses profile data to eliminate layout conflicts, and is unique in its capability of resolving conflicting layout requirements of different references to the same array in the same nest and in different nests for regular array-based applications.The optimization technique presented in this paper has been implemented in a source-to-source translator. We evaluate its performance using standard benchmark suites and several math libraries (complete programs) with large input sizes. Experimental results show that our approach reduces the overall execution times of original codes by 17.5% on the average. This reduction comes from three important characteristics of the technique, namely, resolving layout conflicts between references to the same array in a loop nest, determining a suitable order to propagate layout modifications across loop nests, and propagating layouts between different procedures in the program --- all in a unified framework.
Cited by 4