Embedded Systems Design - June 2008 - (Page 47)

20 years ago for example, a rare procedure that occurs during the processing of a block of contiguous data. One cache set is flushed and filled with the page-table directory; another cache set is flushed and filled with the indexed page table. If there’s yet another available cache set holding current data, it will be the next to go (rather than the set holding the directory or page THE THRASHING table) because it was PROBLEM the least recently used. Let’s consider a 32-entry, fulThis phenomenon, called page-table And all this dataly associative LRU TLB. thrashing, essentially negates the cache performance When 33 accesses occur to deterioration occurs different pages, the 33rd acperformance improvement that the TLB even if the procedure cess will cause the ﬁrst acshould yield. doesn’t access any cessed page to be discarded data! from the buffer. This may The impact of seem like a low TLB miss frehardware architecture quency, but consider a timeon code performance cannot be igdrop in performance is enough to warsliced multitasking system running six nored, especially with paged virtual processes, each using different pages for rant real concern. memory systems. The sizes and types instructions and data (an advisable of instruction caches, data caches, and DATA-CACHE COMPLICATIONS programming practice). In this situaTLBs can have vastly disparate effects Thrashing can deteriorate performance tion, at least 12 pages are active at any given time. If each process uses double- even more if there’s a data cache. This is on the performance of what might because the data-cache mechanism sees seem to be a simple application, espenested procedures (or jumps between cially in multitasking environments. three pages) in each time slice, there are no difference between page tables and Thankfully, following some simple 36 active pages—four more active pages any other type of data. As a result, page rules can help prevent undue thrashtables are loaded into the data cache than are available in the TLB. ing. For example, it’s possible to miniwhenever they’re placed in the TLB. As Now consider what happens as the mize data-cache performance deteriooperating system cycles through each of each page table and page-table directoration with TLB misses, even if the ry is encountered, the old contents of the six time slices sequentially. When page-table lookup failure occurs when the data cache are ﬂushed and the the processor reaches the sixth time there isn’t a context switch. Macros lookup tables loaded up instead. Since slice, there will have been 30 sequential should be expanded; long-unused data caches customarily use an LRU alaccesses to different pages. By the end variables should be declared absolutely gorithm, shared page tables aren’t of the sixth time slice, the operating rather than relatively. maintained in the data cache unless the system will have accessed 36 pages and Other ways to prevent thrashing: cache is set-associative and there are the cache manager will have discarded avoid nesting procedure calls wherever sufﬁcient sets to maintain the pagefrom the TLB the ﬁrst four page-table possible, minimize the number of table directory in the data cache (as entries accessed in the cycle. These four page-table entries were the least recent- well as the page table itself and the pro- concurrent tasks, and don’t use jumps larger than the page size unless abgram data). This situation is rare inly used (they’re in the ﬁrst of the six deed, since most data-cache systems are solutely necessary. time slices). Next month we’ll look at some two-way set-associative. As the operating system cycles special techniques to streamline inOn the other hand, data-cache back to the first time slice, the TLB struction and data flow to avoid ﬂushing isn’t always a problem with needs to resurrect those same pagethrashing. We’ll also examine how page tables. If the TLB miss occurs table entries in itself. In so doing, it interleaved memory banks can result discards the next six page-table entries. when the operating system switches to in varying performance with different a new task, the items discarded from The discarded entries are—you data and code structures. ■ the data cache belong to the last task guessed it—those used by the second anyway and the cache ﬂush doesn’t imtime slice. As the processor continues Back in 1989, Ernest Meyer was a pact performance. on its merry way, it continues to discontributing editor for Embedded Page-table thrashing can cause card exactly those page-table entries Systems Programming, now Embedded data-cache thrashing as well. Consider, Systems Design. from the TLB that it will need next. Unfortunately, LFU algorithms are very expensive to build in hardware. All memory systems below the mini supercomputer grade currently use the LRU replacement algorithm for instruction caches, data caches, and TLBs, placing some stringent limits on the capacity of the memory system. This phenomenon, called pagetable thrashing, essentially negates the performance improvement that the TLB should yield. With continual thrashing, overall program speed is at least three times slower than the optimum because the processor needs to look up three memory locations in every cycle instead of just one. A 300% www.embedded.com | embedded systems design | JUNE 2008 47 http://www.embedded.com

Table of Contents Feed for the Digital Edition of Embedded Systems Design - June 2008

Embedded Systems Design - June 2008 Contents #Include Party Bit Programmer's Toolbox Cover Feature: Virtual Hardware Platforms for Embedded Software Validation Allocating Memory in MATLAB-to-C Code MDD and IDEs: Making the Twain Meet in Embedded Systems Design Avoid a Thrashing Guest Editor Advertising Index Break Points Marketplace

Embedded Systems Design - June 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.