一套系統化的多核心系統加速機制

Abstract

在多核心系統上，使用多執行緒平行化的方式來加速應用程式的效能是一種相當常見的方法。然而，我們發現平行化不一定總是能帶來正向的加速效果，這是因為系統上存在著一些潛在的問題使得結果不如預期，像是執行緒間可觀的同步開銷及不合理的執行緒派發。研究人員常常會因為專注在平行化方法的設計上，而忽略了這些系統的問題。因此，我們提出一套系統化機制能在多核心系統上有效地加速應用程式。為了讓加速確實有效，整個機制的目標放在如何有系統地操作執行緒以妥善地使用這些多核心。我們將機制設計成三個階段來解決上述的系統問題，這包含了：如何將程式平行給執行緒執行、如何協調這些執行緒與系統核心、以及如何排程這些執行緒。為了讓機制更有彈性，每個階段採用獨立模組的設計，不僅能疊加在一起也可個別與其它既有的加速方法一同使用以達到更佳的加速效果。此外，我們也提供了相關的理論分析，包含了可行性及時間複雜度的分析，並在一台四核心的系統上做了一系列的實驗，以兩個不同類型的應用來驗證整個機制。實驗結果顯示我們的機制因為減少了系統上的開銷，與傳統的方法相比能達到更好的效能。

In multi-core environment, parallelizing with multi-hreading is a common approach to speed up application programs. However, we find that the parallelization efforts might not always lead to positive performance gain because of some potential system issues, such as the significant synchronization overhead among threads and the unreasonable dispatching of threads. Researches focusing on the parallelization of specific program components without consideration of the entire system might often overlook these system issues. Therefore, we propose to design a systematic mechanism to speed up application programs effectively on multi-core systems. To make the speed-up effective, the mechanism aims at how to manipulate threads to utilize multiple cores systematically. It includes three phases: parallelizing the program into threads, coordinating these threads with system kernel, and scheduling these threads, to solve the problem with consideration of the system issues. For the flexibility, each phase is developed as an independent module, and can be applied not only all together but also individually with other existing speed-up approaches to achieve higher performance. Furthermore, we also provide related theoretical analysis including feasibility and time complexity, and conduct a series of experiments with two different kinds of applications to verify the mechanism on a 4-core machine. The results show that it can deliver higher performance than traditional approaches because of the reduction of the system overhead.