微信服务号

微信订阅号

2025-4-9- 9
Home > Archive>Volume 27, Issue 9, 2016 >2426-2442. DOI:10.13328/j.cnki.jos.004859
PDF HTML XML Export Cite reminder
Basic-Block Based Instruction Prefetching Technology for Real-Time System
Author:
Affiliation:

Fund Project:

National High-Tech R&D Program of China (863) (2013AA011701)

  • Article
    • | |
  • Metrics
    • |
  • Reference [19]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Instruction prefetching technologies proposed for general purpose computer systems cannot meet the requirements of real- time systems. One of the most important issues is that cache content pollution caused by useless prefetching loses real-time tasks' WCET estimates. And a loose on WCET analysis degrades the schedulability of the system and in turn brings down its efficiency. A basic-block based instruction prefetching method is proposed in this paper. The method performs instruction prefetching at the basic block level, avoids useless prefetching, simplifies the instruction hit/miss classifications in the worst-case execution, and reduces the WCET estimates of real-time tasks. Real-time benchmark tests show that, the method can reduce real-time tasks' WCET estimates by 20% and also improve instruction cache access performance by 10% on average.

    Reference
    [1] Clifton C,Leavens GT,Chambers C,Millstein T.MultiJava:Modular open classes and symmetric multiple dispatch for Java.In:Rosson MB,Lea D,eds.Proc.of the 2000 ACM SIGPLAN Conf.on Object-Oriented Programming Systems,Languages&Applications.SIGPLAN Notices,2000,35(10):130-145.[doi:10.1145/353171.353181]
    [2] Smith AJ.Sequential program prefetching in memory hierarchies.Computer,1978,11(12):7-21.[doi:10.1109/C-M.1978.218016]
    [3] Smith AJ.Cache memories.ACM Computing Surveys (CSUR),1982,14(3):473-530.[doi:10.1145/356887.356892]
    [4] Smith JE,Hsu WC.Prefetching in supercomputer instruction caches.In:Werner R,ed.Proc.of the 1992 ACM/IEEE Conf.on Supercomputing.IEEE Computer Society Press,1992.588-597.[doi:10.1109/SUPERC.1992.236645]
    [5] Pierce J,Mudge T.Wrong-Path instruction prefetching.In:Beaty S,Melvin S,eds.Proc.of the 29th Annual IEEE/ACM Int'l Symp.on Microarchitecture (MICRO-29).IEEE,1996.165-175.[doi:10.1109/MICRO.1996.566459]
    [6] Joseph D,Grunwald D.Prefetching using Markov predictors.In:Pleszkun AR,Mudge T,eds.Proc.of the 24th Annual Int'l Symp.on Computer architecture.ACM Press,1997,25(2):252-263.[doi:10.1145/264107.264207]
    [7] Luk CK,Mowry TC.Cooperative prefetching:Compiler and hardware support for effective instruction prefetching in modern processors.In:Bondi J,Smith J,eds.Proc.of the 31st Annual ACM/IEEE Int'l Symp.on Microarchitecture (MICRO-31).IEEE Computer Society Press,1998.182-194.[doi:10.1109/MICRO.1998.742780]
    [8] Xia C,Torrellas J.Instruction prefetching of systems codes with layout optimized for reduced cache misses.In:Baer JL,ed.Proc.of the 23rd Annual Int'l Symp.on Computer Architecture.1996,24(2):271-282.[doi:10.1109/ISCA.1996.10019]
    [9] Reinman G,Calder B,Austin T.Fetch directed instruction prefetching.In:Ronen R,Farrens M,Spillinger I,eds.Proc.of the 32nd Annual Int'l Symp.on Microarchitecture (MICRO-32).IEEE,1999.16-27.[doi:10.1109/MICRO.1999.809439]
    [10] Zhang Y,Haga S,Barua R.Execution history guided instruction prefetching.In:Ebcioglu K,Pingali K,Nicolau A,eds.Proc.of the 16th Int'l Conf.on Supercomputing.ACM Press,2002.199-208.[doi:10.1145/514191.514220]
    [11] Aamodt TM,Chow P,Hammarlund P,Wang H,Shen JP.Hardware support for prescient instruction prefetch.In:Tirado F,Zapata EL,eds.Proc.of the IEEE Int'l Symp.on High Performance Computer Architecture.IEEE Computer Society,2004.84.[doi:10.1109/HPCA.2004.10028]
    [12] Yan J,Zhang W.WCET analysis of instruction caches with prefetching.In:Pande S,Li ZY,eds.Proc.of the 2007 ACM SIGPLAN/SIGBED Conf.on Languages,Compilers,and Tools for Embedded Systems.ACM SIGPLAN Notices,2007,42(7):175-184.[doi:10.1145/1254766.1254801]
    [13] Ding Y,Yan J,Zhang W.Optimizing instruction prefetching to improve worst-case performance for real-time applications.Journal of Computing Science and Engineering,2009,3(1):59-71.[doi:10.5626/JCSE.2009.3.1.059]
    [14] Lee M,Min SL,Kim CS.A worst case timing analysis technique for instruction prefetch buffers.Microprocessing and Microprogramming,1994,40(10):681-684.[doi:10.1016/0165-6074(94)90017-5]
    [15] Schoeberl M.A time predictable instruction cache for a Java processor.In:Zahir T,Angelo C,eds.Proc.of the Move to Meaningful Internet Systems 2004:OTM 2004 Workshops.Berlin,Heidelberg:Springer-Verlag,2004.371-382.[doi:10.1007/978-3-540-30470-8_52]
    [16] Li XF,Roychoudhury A,Mitra T.Modeling out-of-order processors for WCET analysis.Journal of Real-time Systems,2006,34(3):195-227.[doi:10.1007/s11241-006-9205-5]
    [17] Austin T,Larson E,Ernst D.SimpleScalar:An infrastructure for computer system modeling.Computer,2002,35(2):59-67.[doi:10.1109/2.982917]
    [18] Arnold R,Mueller F,Whalley D,Harmon M.Bounding worst-case instruction cache performance.In:Juan S,Rico P,eds.Proc.of the IEEE Real-Time Systems Symp.1994.172-181.[doi:10.1109/REAL.1994.342718]
    [19] Homepage of SNU real-time benchmark suite.2007.http://archi.snu.ac.kr/realtime/benchmark/
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

王恩东,倪璠,陈继承,王洪伟,唐士斌.一种面向实时系统的程序基本块指令预取技术.软件学报,2016,27(9):2426-2442

Copy
Share
Article Metrics
  • Abstract:2141
  • PDF: 4660
  • HTML: 1291
  • Cited by: 0
History
  • Received:September 03,2014
  • Revised:December 31,2014
  • Online: September 02,2016
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2034060Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063