THREADED PREFETCHING - A NEW INSTRUCTION MEMORY-HIERARCHY FOR REAL-TIME SYSTEMS

Cache memories have been extensively used to bridge the speed gap betw een high speed processors and relatively slow main memory. However, th ey are not widely used in real-time systems due to their unpredictable performance. This paper proposes an instruction prefetching scheme ca lled threaded prefetching as an alternative to instruction caching in real-time systems. In the proposed threaded prefetching, an instructio n block pointer called a thread is assigned to each instruction memory block and is made to point to the next block on the worst case execut ion path that is determined by a compile-time analysis. Also, the thre ad is not updated throughout the entire program execution to guarantee predictability. This paper also compares the worst case performances of various previous instruction prefetching schemes with that of the p roposed threaded prefetching. By analyzing several benchmark programs, we show that the worst case performance of the proposed scheme is sig nificantly better than those of previous instruction prefetching schem es. The results also show that when the block size is large enough the worst case performance of the proposed threaded prefetching scheme is almost as good as that of an instruction cache with 100% hit ratio.