以取樣爲基礎之多執行緒程式行爲分類與預測

Abstract

程式執行行爲常有重複執行的現象，因此如果可以認出重複執行的部分，則可以最佳化程式執行。若可將程式執行區段準確分類到適當的類別裡，並且可以利用這些分類資訊來預測下一區段所屬的類別，則可及時啟用一個適當的最佳化方法於下一個區段執行。這樣的最佳化機會不僅出現在單一執行緒的程式裡，也會出現在多執行緒的程式裡。 在本篇論文裡，我們提出一個架構能夠蒐集每個執行緒所執行的每個區段的程式特徵，並且在程式執行時將每個區段分類到適當的類別裡。最後利用這些分類結果來預測下一區段的類別。爲了提高分類的效率，我們只儲存固定數目的代表資訊來做分類，因此分類的效率很高而且所需的記憶體空間小於三千個位元組。另外我們使用信心表格來提高預測準度。我們的架構能夠將區段分到適當類別裡使得同一類別裡的區段間行爲非常類似。且下一個區段所屬的類別的預測準度爲65%。若加入信心表格，則預測準度提高至80%。

Program executions are usually repetitive; hence, we can optimize program executions if we are able to identify the program’s repetition pattern. If we can accurately classify program execution intervals into phases, and use such information to accurately predict the next phase at runtime, we will be able to apply suitable optimization on the coming intervals. Such runtime optimization opportunity not only exists in single-threaded programs but also in multi-threaded programs (e.g. OpenMP codes, which exhibit repetitive behavior). In this paper, we propose a framework that collects code signature of each interval from individual threads of a multi-threaded parallel program, and classify them into phases at runtime. We then use the classification results to predict the next phase in an on-line fashion. In order to efficiently classify execution intervals on-line, we only keep a fixed number of representative data in a shared table for classification purpose. The classification is very efficient and uses less than 3K bytes of memory. We also propose a confidence table to improve the prediction rate. Our system can classify intervals into phases with high homogeneity, can predict the next phase with 65% accuracy without using confidence and with 80% accuracy when confidence table is used.