Case Study 3: Managing Contention for Shared Resources on Multicore Processors
By
Ja’Kedrick L. Pearson
Professor Hossein Besharatian

CIS 512

June 2, 2013

Memory contention Memory contention is a state an OS memory manager can reside in when to many memory requests are issued to it from an active application possibly leading to a DOS condition specific to that application. A test was run on a group of applications several times, on three different schedules, each with two different parings sharing a memory domain. The three pairing permutations afforded each application an opportunity to run with each of the other three applications with the same memory domain. The three applications being discussed in this paper are the Soplex, Sphinx, and the NAMD. The Soplex is a linear programming (LP) solver based on the revised simplex algorithm. It features preprocessing techniques, exploits sparsity, and offers primal and dual solving routines. It can be used as a standalone solver reading MPS or LP format files as well as embedded into other programs via a C++ class library. Sphinx is an open source full text search server, designed from the ground up with performance, relevance (aka search quality), and integration simplicity in mind. It's written in C++ and works on Linux (RedHat, Ubuntu, etc), Windows, MacOS, Solaris, FreeBSD, and a few other systems (Sphinx Technologies, 2013). NAMD is a parallel molecular dynamics code designed for high-performance simulation of large bimolecular systems. NAMD uses the popular molecular graphics program VMD for simulation setup and trajectory analysis, but is also file-compatible with AMBER, CHARMM, and X-PLOR. NAMD is distributed free of charge with source code (NIGMS, 2013).
Examine the authors’ findings
Soplex and Sphinx ran in a memory domain, while Gamess and Namd shared another memory domain. Sphinx was paired with Gamess, while Soplex shared a domain with Namd. Sphinx was paired with Namd, while Soplex ran in the same domain with Gamess. The performance levels are indicated in terms of the percentage of degradation from solo execution time, when the application ran alone on the system, meaning that the lower the numbers, the better the performance. There was a dramatic difference between the best and the worst schedules. The workload as a whole performed 20 percent better with the best schedule, while gains for the individual applications Soplex and Sphinx were as great as 50 percent. This indicates a clear incentive for assigning applications to cores according to the best possible schedule (Fedora, Blagodurov & Zhuravlev, 2010).
Distributed Architecture
Using distributed intensity online (DIO), the authors constructed eight-application workloads containing from two to six memory-intensive applications. They picked eight workloads in total, all consisting of SPEC CPU2006 applications, and then executed them under the DIO and the default Linux scheduler on an AMD Opteron system featuring eight cores, four per memory domain. The performance improvement relative to default has been computed as the average improvement for all applications in the workload. DIO renders workload-average performance improvements of up to 11 percent. Another potential use of DIO is as a way to ensure quality of service for critical applications since DIO essentially provides a means to make sure the worst scheduling assignment is never selected, while the default scheduler may occasionally suffer as a consequence of a bad thread placement.
Power DI works as follows: assuming a centralized scheduler has knowledge of the entire computing infrastructure and distributes incoming applications across all systems, Power DI clusters all incoming applications on as few machines as possible, except for those applications deemed to be memory intensive. To determine if an application is memory-intensive, Power DI uses an experimentally derived threshold of 1,000 misses per million instructions; an application whose LLC miss rate exceeds that amount is considered memory intensive. Power DI, on the other hand, is able to adjust to the properties of the workload and minimize EDP in all cases, beating both Spread and Cluster for every single workload.
The authors found that scheduling algorithms that use this heuristic to avoid contention have the potential to reduce the overall completion time for workloads, avoid poor performance for high-priority applications, and save power without sacrificing performance (Fedora, Blagodurov & Zhuravlev, 2010).
Cache contention
Cache contention occurs when two or more threads are assigned to run on the cores of the same memory domain. There are two schools of thought regarding the modeling of cache contention. The first suggests that considering the LLC miss rate of the threads is a good way to predict whether these threads are likely to compete for the cache. The reasoning is that if a thread issues lots of cache misses, it must have a large cache working set, since each miss results in the allocation of a new cache line. The second school of thought states if a thread hardly ever reuses its cached data, as would be the case with a video-streaming application that touches the data only once, it will not suffer from contention even if it brings lots of data into the cache. That is because such a thread needs very little space to keep in cache the data that it actively uses (Fedora, Blagodurov & Zhuravlev, 2010).
Contention avoidance methods
The impact of prefetching shows the combined effect of these three factors, and is only an upper-bound on the impact of contention for prefetching hardware itself. That is why the older memory-reuse model, which was designed to model cache contention only, was not effective in our experimental environment. Cache-miss rate turned out to be an excellent predictor for contention for the memory controller, prefetching hardware, and front-side bus. An application issuing many cache misses will occupy the memory controller and the front-side bus, so it will not only hurt other applications that use that hardware, but also end up suffering itself if this hardware is usurped by others. An application aggressively using prefetching hardware will also typically have a high LLC miss rate, because prefetch requests for data that is not in the cache are counted as cache misses. Therefore, a high miss rate is also an indicator of the heavy use of prefetching hardware (Fedora, Blagodurov & Zhuravlev, 2010).

References:

Fedora, A., Blagodurov, S. & Zhuravlev, S. (2010). Managing Contention for Shared Resources on Multicore Processors. Retrieved from http://queue.acm.org/detail.cfm?id=1709862

NIGMS. (2013). NAMD. Retrieved from http://www.ks.uiuc.edu/Research/namd/.

Sphinx Technologies. (2013). Sphinx Overview. Retrieved from http://sphinxsearch.com/about/sphinx/

ZIB. (2013). SoPlex. Retrieved from http://soplex.zib.de/.