检索结果-内蒙古大学图书馆

code placement techniques for cache miss rate reduction

ACM Transactions on Design Automation of Electronic Systems 1997年第4期2卷 410-429页

作者： Tomiyama, Hiroyuki Yasuura, Hiroto Kyushu University Japan Department of Computer Science and Communication Engineering Graduate School of Information Science and Electrical Engineering Kyushu University Fukuoka 816 6-1 Kasuga-koen Kasuga Japan

In the design of embedded systems with cache memories, it is important to minimize the cache miss rates to reduce power consumption of the systems as well as improve the performance. In this article, we propose two code placement methods (a simplified method and a refined one) to reduce miss rates of instruction caches. We first define a simplified code placement problem without an attempt to minimize the code size. The problem is formulated as an integer linear programming (ILP) problem, by which an optimal placement can be found. Experimental results show that the simplified method reduces cache misses by an average of 30% (max. 77%). However, the code size obtained by the simplified method tends to be large, which inevitably leads to a larger memory size. In order to overcome this limitation, we further propose a refined code placement method in which the code size provided by the system designers must be satisfied. The effectiveness of the refined method is also demonstrated. © 1997 ACM.

关键词： code placement Design Instruction cache Integer linear programming Performance

来源：评论

学校读者我要写书评

暂无评论

Graph model for optimal OVSF code placement strategies

引用

INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING 2012年第3期9卷 133-141页

作者： Ouyang, Wen Yu, Chang Wu Liu, Meng-Ti Chang, Yu-Wei Chung Hua Univ Dept Comp Sci & Informat Engn Hsinchu 30012 Taiwan

The code utilisation of OVSF-CDMA systems are significantly impacted by the code placement and replacement schemes which have been studied by many researchers as independent problems. We formally define the placement optimality and present a novel graph model, CIDP, which is proved to be NP-complete for general graphs where the CIDP graphs reduced from the OVSF code placement problem are trivial perfect graphs. A unified algorithm UCMS-1, provided to firstly address both OVSF code placement and replacement jointly, achieves placement optimality in linear time complexity. It shows that OVSF code placement optimality problem is in P.

关键词： graph algorithm OVSF-CDMA code blocking code placement constrained independent dominating set

来源：评论

学校读者我要写书评

暂无评论

Frequency-based code placement for embedded multiprocessors

Frequency-based code placement for embedded multiprocessors

引用

42nd Design Automation Conference

作者： Goldfeder, C Columbia Univ New York NY 10027 USA

Multiprocessor embedded systems often have processor-local caches and a shared memory. If the system's code is available at design time we can maximize cache hits by rearranging code in memory so that frequently e... 详细信息

ISBN: (纸本)1595930582

关键词： embedded systems multiprocessors caching memory code placement frequent code

来源：评论

学校读者我要写书评

暂无评论

code motion and code placement:: Just synonyms? 7th

Code motion and code placement:: Just synonyms?

引用

7th European Symposium on Programming (ESOP'98) at the Joint European Conferences on Theory and Practice of Software (ETAPS'98)

作者： Knoop, J Rüthing, O Steffen, B Univ Passau D-94030 Passau Germany Univ Dortmund D-44221 Dortmund Germany

ISBN: (纸本)3540643028

We prow that there is no difference between code motion (CM) and code placement (CP) in the traditional syntactic setting, however, a dramatic difference in the semantic setting. We demonstrate this by re-investigating semantic CM under the perspective of the recent development of syntactic CM. Besides clarifying and highlighting the analogies and essential differences between the syntactic and the semantic approach, this leads as a side-effect to a drastical reduction of the conceptual complexity of the value-flow based procedure for semantic CM of [20], as the original bidirectional analysis is decomposed into purely unidirectional components. On the theoretical side, this establishes a natural semantical understanding in terms of the Herbrand interpretation (transparent equivalence), and thus eases the proof of correctness;moreover, it shows the frontier of semantic CM, and gives reason for the lack of algorithms going beyond. On the practical side, it simplifies the implementation and increases the efficiency, which, hire for its syntactic counterpart, can be the catalyst for its migration from academia into industrial practice.

关键词： program optimization data-flow analysis code motion code placement partial redundancy elimination transparent equivalence Herbrand interpretation

来源：评论

学校读者我要写书评

暂无评论

code and Data placement for Embedded Processors with Scratchpad and Cache Memories

引用

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY 2010年第2期60卷 211-224页

作者： Ishitobi, Yuriko Ishihara, Tohru Yasuura, Hiroto Kyushu Univ Grad Sch Informat Sci & Elect Engn Nishi Ku Fukuoka 8190395 Japan Kyushu Univ Syst LSI Res Ctr Sawara Ku Fukuoka 8140001 Japan Kyushu Univ Fac Informat Sci & Elect Engn Nishi Ku Fukuoka 8190395 Japan

This paper proposes a code placement problem, its ILP formulation, and a heuristic algorithm for reducing the total energy consumption of embedded processor systems including a CPU core, on-chip and off-chip memories. Our approach exploits a non-cacheable memory region for an effective use of a cache memory and as a result, reduces the number of off-chip accesses. Our algorithm simultaneously finds a code layout for a cacheable region, a scratchpad region, and the other non-cacheable region of the address space so as to minimize the total energy consumption of the processor system. Experiments using a commercial embedded processor and an off-chip SDRAM demonstrate that our algorithm reduces the energy consumption of the processor system by 23% without any performance degradation compared to the best result achieved by the conventional approach.

关键词： code placement Energy reduction Embedded processor

来源：评论

学校读者我要写书评

暂无评论

Procedure placement using temporal-ordering information: Dealing with code size expansion

引用

Journal of Embedded Computing 2005年第4期1卷 437-459页

作者： Guillon, Christophe Rastello, Fabrice Bidault, Thierry Bouchez, Florent STMicroelectronics in France École Normale Supérieure de Lyon in France

In a direct-mapped instruction cache, all instructions that have the same memory address modulo the cache size share a common and unique cache slot. Instruction cache conflicts can be partially handled at linked time by procedure placement. Pettis and Hansen give in [1] an algorithm that reorders procedures in memory by aggregating them in a greedy fashion. The Gloy and Smith algorithm [2] greatly decreases the number of conflict-misses but increases the code size by allowing gaps between procedures. The latter contains two main stages: the cache-placement phase assigns modulo addresses to minimizes cache-conflicts; the memory-placement phase assigns final memory addresses under the modulo placement constraints, and minimizes the code size expansion. In this paper: (1) we prove the NP-completeness of the cache-placement problem; (2) we provide an optimal algorithm to the memory-placement problem with complexity O(nmin(n,L)ack(n)) (n is the number of procedures, L the cache size, α is the inverse Ackermann's function that is lower than 4 in practice); (3) we take final program size into consideration during the cache-placement phase. Our modifications to the Gloy and Smith algorithm gives on average a code size expansion of 8% over the original program size, while the initial algorithm gave an expansion of 177%. The cache miss reduction is nearly the same as the Gloy and Smith solution with 35% cache miss reduction.

关键词： Instruction cache code placement code size cache miss min-matching Hamiltonian-path profiling

来源：评论

学校读者我要写书评

暂无评论

Scratchpad Memory Management Techniques for code in Embedded Systems without an MMU

引用

IEEE TRANSACTIONS ON COMPUTERS 2010年第8期59卷 1047-1062页

作者： Egger, Bernhard Kim, Seungkyun Jang, Choonki Lee, Jaejin Min, Sang Lyul Shin, Heonshik Samsung Adv Inst Technol Giheung Gu Yongin Si 446712 Gyeonggi Do South Korea Seoul Natl Univ Sch Comp Sci & Engn Seoul 151742 South Korea

We propose a code scratchpad memory (SPM) management technique with demand paging for embedded systems that have no memory management unit. Based on profiling information, a postpass optimizer analyzes and optimizes application binaries in a fully automated process. It classifies the code of the application including libraries into three classes based on a mixed integer linear programming formulation: External code is executed directly from the external memory. Pinned code is loaded into the SPM when the application starts and stays in the SPM. Paged code is loaded into/unloaded from the SPM on demand. We evaluate the proposed technique by running 14 embedded applications both on a cycle-accurate ARM processor simulator and an ARM1136JF-S core. On the simulator, the reference case, a four-way set-associative cache, is compared to a direct-mapped cache and an SPM of comparable die area. On average, we observe an improvement of 12 percent in runtime performance and a 21 percent reduction in energy consumption. On the ARM11 board, the reference case run on the 16-KB four-way set-associative cache is compared to the demand paging solution on the 16-KB SPM, optionally supported by the cache. The measured results show both a runtime performance improvement and a reduction of the energy consumption by 23 percent, on average.

关键词： Compilers postpass optimization code placement demand paging scratchpad memory embedded systems

来源：评论

学校读者我要写书评

暂无评论

Procedure placement using temporal-ordering information

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1999年第5期21卷 977-1027页

作者： Gloy, N Smith, MD Appliant Inc Seattle WA 98105 USA Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

Instruction cache performance is important to instruction fetch efficiency and overall processor performance. The layout of an executable has a substantial effect on the cache miss rate and the instruction working set size during execution. This means that the performance of an executable can be improved by applying a code-placement algorithm that minimizes instruction cache conflicts and improves spatial locality. We describe an algorithm for procedure placement, one type of code placement, that significantly differs from previous approaches in the type of information used to drive the placement algorithm. In particular, we gather temporal-ordering information that summarizes the interleaving of procedures in a program trace. Our algorithm uses this information along with cache configuration and procedure size information to better estimate the conflict cost of a potential procedure ordering. It optimizes the procedure placement for single level and multilevel caches. In addition to reducing instruction cache conflicts, the algorithm simultaneously minimizes the instruction working set size of the program. We compare the performance of our algorithm with a particularly successful procedure-placement algorithm and show noticeable improvements in the instruction cache behavior, while maintaining the same instruction working set size.

关键词： algorithms performance code placement conflict misses temporal profiling working-set optimization

来源：评论

学校读者我要写书评

暂无评论

A COMPOSITE HOISTING-STRENGTH REDUCTION TRANSFORMATION FOR GLOBAL PROGRAM OPTIMIZATION .2.

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1982年第2期11卷 111-126页

作者： JOSHI, SM DHAMDHERE, DM INDIAN INST TECHNOL CTR COMPBOMBAY 400076INDIA

In part I of this paper [9], an algorithm to perform hoisting and strength reduction in a unified manner (CHSA) was presented. This algorithm was shown to eliminate control flow analysis costs and to widen the scope of conventional strength reduction. Part II of this paper discusses various refinements of CHSA to improve its effectiveness.

关键词： Global program optimization code hoisting strength reduction induction variable program flow graph data flow analysis code placement 4.12 5.32

来源：评论

学校读者我要写书评

暂无评论

A NEW ALGORITHM FOR COMPOSITE HOISTING AND STRENGTH REDUCTION OPTIMIZATION

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1989年第1期27卷 1-14页

作者： DHAMDHERE, DM Computer Science & Engineering Indian Institute of Technology Bombay 400076 India

Unifications of optimising transformations are motivated by the desire to reduce the cost of optimisation. Two unifications using code placement techniques based on the suppression of partial redundancies have been reported in the literature [5, 8]. A common drawback of these unifications has been their failure to provide sufficient guarantees regarding improvement in execution efficiency of programs. This has tended to limit their effectiveness from a practical *** paper proposes a new algorithm to unify the optimising transformations of hoisting, loop optimisation and strength reduction. The algorithm uses a refined framework for code placement that provides guarantees of improvement in execution efficiency of programs. The properties of this algorithm are formally proved.

关键词： Compilers global program optimisation code movement code placement strength reduction data flow analysis 4.12 5.32

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：