Predicting Interference-Free Performance with Linear Model Trees

Abstract

Moderne flerkjerne-prosessorer bruker ofte delte hardwarekomponenter for å forbedre utnyttelsen av hver enkelt komponent og en bedre ytelse fra systemet i sin helhet. Men, slike delte komponenter fører også til at en applikasjon kan tilføre interferens for en annen applikasjon. Slik blir ytelsen til hver enkelt applikasjon uforutsigbar fordi den avhenger av hvilke applikasjoner som kjører samtidig. Å beregne hva ytelsen per applikasjon ville ha vært uten denne interferensen er en svært nyttig metrikk med tanke på å tildele delte systemressurser effektivt. En rekke systemer for å predikere en slik interferensfri ytelse har blitt foreslått. De beste av dem klarer å predikere interferensfri ytelse forholdsvis nøyaktig, men har en kompleks modellering som gjør at hardware-kostnaden ved å implementere systemene øker. Dette gjør systemene mindre attraktive for kommersielle prosessorprodusenter.

Denne masteroppgaven foreslår en ny måte å predikere interferensfri ytelse på, med fokus på å redusere hvor mye lagringskapasitet som kreves for å implementere prediksjonssystemet. Istedet for å modellere enkeltverdier som skal representere nøkkelkomponenter i en ytelsesmodell for delte minneressurser, benyttes læring av regresjonsmodeller for å predikere den resulterende ytelsen. Mer konkret: lineære trær benyttes som regresjonsmodell. Et linærtre er et beslutningstre som inneholder lineær regresjon i hver løvnode. De klassifiserer observasjoner med lik minneoppførsel, og drar nytte av linearitet mellom observasjonene. Lineærtrærne benyttes enten til å predikere interferensfri ytelse direkte eller til å estimere nøkkelkomponenter i en ytelsesmodell. Hovedfokuset i denne oppgaven har vært å bevare så mye av nøyaktigheten i prediksjonene som mulig, mens lagringen som kreves for å implementere prediksjonssystemet reduseres.

Lineære trær kan konfigureres en rekke måter. For å vise hvilket kraftfullt verktøy lineære trær kan være, presenteres resultatene for to ulike lineærtre-konfigurasjoner. Begge konfigurasjonene benytter 10 løvnoder i treet, og predikerer antall instruksjoner per sykel. Forskjellen mellom konfigurasjonene er at ene ikke bruker en kostbar input-verdi som krever mye lagringskapasitet. Det første oppsettet reduserte feilen i prediksjonene med 1% sammenlignet med "state-of-the-art", mens lagringskapasiteten som kreves for systemet reduseres med 24%. Den andre konfigurasjonen med et redusert input-sett har en økt feil sammenlignet med "state-of-the-art" med 17%, men reduserer lagringskapasiteten som kreves med hele 85%.

Modern multicore processors improve hardware utilization and throughput with resource sharing between cores. However, resource sharing also leads to an unpredictable application performance because of inter-application interference in the shared resources. Quantifying the performance without this interference, called the interference-free performance is a key component to effectively manage shared system resources. Several performance accounting systems have been proposed, predicting interference-free performance. They are able to predict quite accurately, but have significant storage overhead making them less attractive to be implemented by commercial vendors.

This master thesis proposes a novel way of predicting interference-free performance in multicore processors, with a lower storage overhead. Instead of modeling some key performance aspect of the shared memory system to predict performance, the behavior is learned by a regression model. Specifically, linear model trees (LMTs) are used combining decision trees and linear regression. The LMTs classify observations in the memory system with similar behavior. Succeedingly, they exploit linearity within each classification. The LMT can either predict the interference-free performance directly, or provide low-cost predictions to be used in other performance accounting models. The main focus of the work is retaining prediction accuracy compared to state-of-the-art while reducing the storage overhead of predictions.

The LMTs can be configured numerous ways, however two specific configurations point out how they can reduce storage overhead for interference-free performance prediction. Both configurations predict IPC directly in a LMT with 10 leaf nodes. The only difference between them is that a set of costly input features are removed to reduce storage overhead in one of the configurations. First configuration improves the prediction error compared to state-of-the-art by 1%, while reducing the storage overhead by 24%. Secondly, the reduced feature set configuration increases the prediction error compared to state-of-the-art by 17%. However, the storage overhead is reduced by 85%.