Modelling Inclusive Cache Hierarchies in Multi-core Systems

Abstract

Ytelsen til moderne datasystemer er ofte begrenset av hastigheten til minnet da hastigheten til prosessorer har økt mye mer enn hastigheten til minnesystemer over flere år. Dette har ført til at minnesystemer ofte blir en flaskehals for ytelsen til systemet da prosessoren må vente at minnet blir ferdig. Dette er særlig et problem for programmer med mange minneoperasjoner. En løsning for å redusere ventetiden på minner er å bruke hurtigbuffere, men disse er bare effektive hvis bufferne inneholder relevant data.

Hvis et hurtigbuffer blir fullt må noe kastes ut for å få plass til nye datablokker. Dette bestemmes av "erstatningspolicyer" ("cache replacement policies"), men disse kan fort bli avanserte siden det ofte ikke er enkelt å finne ut hva som er optimalt å kaste ut. I tillegg kan policyen påvirke (eller bli påvirket) av andre faktorer i systemet. Det er derfor vanlig å bruke simulatorer for å simulere prototyper av policyer med forskjellige parametere før de blir brukt i hardware.

Et interessant scenario det kan være verdt å se nærmere på er hvordan en inklusiv policy oppfører seg i et system med flere kjerner og nivåer med hurtigbuffere. Dette omfatter for eksempel graffik-prosessorer da disse ofte har noen private buffere med data og noen delte buffere mellom seg. Det finnes mange åpne akademiske simulatorer på nettet men virtuelt alle har begrensinger på som kan gjøres og hva som ikke kan gjøres. Ingen av de simulatorene som ble sett på i starten av dette prosjektet var i stand til å simulere minneoperasjoner per prosessorkjerne i et system med flere prosessorkjerner og nivåer med hurtigbuffere.

Denne masteroppgaven presenterer simulatoren COCOASIM – en "COncurrent Cache Operating Access SIMulator". Simulatoren er bygget helt fra bunnen av i C++, og er designet spesifikt for å simulere minnesystemer med flere prosessorkjerner og spesifiserte tråder til hver kjerne. Simulatoren tar filer med formatterte minneoperasjoner som input, og kjører disse gjennom et virtuelt system til alle operasjonene er ferdige. Siden simulatoren baserer seg eksklusivt på filer med minneoperasjoner er den helt uavhengig av dataarkitekturen som datamaskiner i den virkelige verden må forholde seg til. Eksperimentell testing viser at COCOASIM kan simulere mer enn 8000 instruksjoner i sekundet for små filer (med 8192 operasjoner) og mer enn 4000 instruksjoner i sekundet for store filer (med 2097152 operasjoner). Simulatoren har også flere nyttige funksjoner som f.eks. muligheten til å lage egendefinerte hurtigbuffere, policyer, eller systemer, og kan også logge alt som skjer i en simulasjon samt dumpe statistikk over tid under simuleringen.

The performance of modern conventional computers are often limited by the memory latency of a system as the increase in processor performance has massively outperformed the increase in memory latency throughout the years. This causes the slow memory to act as a bottleneck, and is especially problematic for memory-intense applications. One common solution for reducing the memory latency is the use of caches, but these are only effective if they retain relevant data.

Deciding what data should be kept in a cache is decided by cache replacement polices, but these can often become complex and have non-trivial effects on other components in a memory system. Cache simulators are often used to quickly test the performance of replacement policies with varying cache sizes and memory hierarchy designs.

One interesting area of study is how inclusive cache policies affect multi-core systems – like Graphic Processing Units (GPUs) – with multiple levels of caches. While several open-source simulators exists, a literature review revealed no simulator that can simulate individual cores in a multi-core system with inclusive caches.

This thesis presents COCOASIM – a COncurrent Cache Operating Access SIMulator. The simulator is able to simulate advanced user-defined systems with multiple cores and L1 caches. COCOASIM also uses "Instruction Set Architecture (ISA)" agnostic memory traces – making it possible to define and test architecture independent systems. Experimental testing show that COCOASIM can more than 8000 Instructions per Second (IPS) for small traces (8192 operations), and more than 4000 IPS for larger traces (2097152 operations). The simulator also provides multiple fully customizable components like systems, caches, cache replacement polices, and also supports logging and dumping of statistics at certain checkpoints.