01背景介紹

性能和能耗之間的平衡是設(shè)計(jì)新處理器的核心問題之一，因?yàn)槌^90%的處理器最終用于嵌入式能源受限設(shè)備，例如智能手機(jī)和物聯(lián)網(wǎng)傳感器。異構(gòu)系統(tǒng)，結(jié)合不同的處理器類型，為不同類型的工作負(fù)載提供高能效處理。第一個(gè)異構(gòu)系統(tǒng)將處理器與不同的指令集架構(gòu)(ISA)相結(jié)合。最近，單ISA非對稱多核處理器(AMP)開始流行。它們的優(yōu)勢是顯而易見的——因?yàn)樘幚砥鞴蚕硐嗤募軜?gòu)，操作系統(tǒng)線程調(diào)度程序可以在運(yùn)行時(shí)做出關(guān)于將哪個(gè)任務(wù)/線程映射到哪個(gè)處理器/內(nèi)核的決定，這不僅取決于工作負(fù)載的特征，還取決于通過單個(gè)處理器/內(nèi)核的運(yùn)行時(shí)負(fù)載。另一方面，這為調(diào)度問題引入了額外的自由度，使其更加復(fù)雜。

非對稱多核處理器上的多線程多道程序工作負(fù)載，具有一個(gè)大核和一個(gè)小核。僅控制CPU核心親和性會導(dǎo)致次優(yōu)運(yùn)行時(shí)優(yōu)化決策。工作負(fù)載，這些應(yīng)用程序具有潛在的不平衡線程，并且線程總數(shù)可能高于內(nèi)核數(shù)。雖然向前邁出了重要一步，但WASH僅控制核心親和力，并且以有限的方式這樣做。前者意味著我們無法以整體方式處理核心分配和線程調(diào)度來加速最關(guān)鍵的線程。后者意味著WASH只真正控制每個(gè)線程的調(diào)度域，即允許線程使用的內(nèi)核組。每個(gè)線程的實(shí)際核心由底層LinuxCFS調(diào)度程序選擇，其啟發(fā)式忽略異構(gòu)性和線程關(guān)鍵性。

02COLAB方案概覽

COLAB是一種用于非對稱多核處理器的運(yùn)行時(shí)優(yōu)化策略，它能夠針對線程調(diào)度中的所有三個(gè)主要因素-核心敏感度、線程關(guān)鍵性和公平性做出協(xié)調(diào)決策。

1.核心敏感度：每種類型的核心都旨在處理不同類型的工作負(fù)載。例如，在ARM big.LITTLE系統(tǒng)中，大內(nèi)核主要用于性能關(guān)鍵型工作負(fù)載或具有指令級并行(ILP)的工作負(fù)載。在它們上執(zhí)行其他類型的工作負(fù)載不會顯著提高性能，但會顯著增加能耗。為了構(gòu)建高效的AMP調(diào)度程序，我們需要預(yù)測哪些線程適合哪種內(nèi)核。

2.線程關(guān)鍵性:更快地執(zhí)行工作負(fù)載的單個(gè)線程并不總是轉(zhuǎn)化為整個(gè)工作負(fù)載的更好性能。如果應(yīng)用程序的線程不平衡或以不同的速度執(zhí)行，例如因?yàn)椴煌木€程在不同類型的內(nèi)核上運(yùn)行，則應(yīng)用程序?qū)H以其最慢或最關(guān)鍵的線程（阻塞大部分其他線程的線程）運(yùn)行線程）。一個(gè)好的AMP調(diào)度程序會盡可能地加速這些線程，而不管核心敏感度如何。

3.負(fù)載均衡:在多道程序工作負(fù)載中，單獨(dú)加速單個(gè)應(yīng)用程序是不夠的，如果它會懲罰其他應(yīng)用程序。理想情況下，我們需要負(fù)載均衡來平衡所有應(yīng)用程序中資源共享的負(fù)面影響。在同構(gòu)系統(tǒng)中，這很容易通過以循環(huán)方式在CPU上為每個(gè)應(yīng)用程序提供固定大小的時(shí)間片來實(shí)現(xiàn)。AMP使這個(gè)簡單的解決方案變得不可行。由于每個(gè)內(nèi)核的性能不同，不同內(nèi)核類型上相同的CPU時(shí)間會導(dǎo)致執(zhí)行的工作量完全不同。

系統(tǒng)分為運(yùn)行時(shí)調(diào)度過程和離線建模過程。運(yùn)行時(shí)調(diào)度器內(nèi)置在OS內(nèi)核中，由

i)一個(gè)核心分配器組成，用于處理公平性和核心敏感性；

ii)實(shí)現(xiàn)瓶頸加速的線程選擇器；

iii)基于機(jī)器學(xué)習(xí)的運(yùn)行時(shí)模型，它預(yù)測異構(gòu)內(nèi)核上線程的加速和功耗。離線建模處理用于通過離線訓(xùn)練構(gòu)建運(yùn)行時(shí)模型。

COLAB調(diào)度程序的主要新穎之處在于它可以以協(xié)作的方式處理多個(gè)運(yùn)行時(shí)因素（核心敏感性、瓶頸加速和公平性），以實(shí)現(xiàn)高系統(tǒng)性能和能源效率。

運(yùn)行時(shí)分析

核心分配器：支持AMP的核心分配器主要受線程的核心敏感度因素指導(dǎo)，它量化了將線程從小核心遷移到大核心帶來的性能優(yōu)勢。將high-speedupthread（在大核心上享有較大的加速）從小核心遷移到大核心通常比遷移low-speedupthread 提供更多好處。然而，考慮到瓶頸因素，它量化了線程阻塞其他線程的程度，揭示了這種啟發(fā)式在多道程序工作負(fù)載上的問題。以前的方法只是將預(yù)測的瓶頸加速和加速結(jié)合在一起。這可能會導(dǎo)致次優(yōu)的調(diào)度決策，其中瓶頸線程和高速加速線程都累積在大核心的運(yùn)行隊(duì)列中，更好的核心分配策略將避免瓶頸加速和加速的簡單組合，而是專注于協(xié)作環(huán)境，其中大核心專注于高速瓶頸線程，小核心處理低加速瓶頸線程而無需額外遷移。此外，核心分配器試圖通過有效地共享異構(gòu)硬件并盡可能避免讓資源閑置來實(shí)現(xiàn)AMP的相對公平。簡單地將就緒線程均勻地映射到不同類型的內(nèi)核上并不能實(shí)現(xiàn)真正的公平性，因?yàn)椴煌愋偷膬?nèi)核最終具有不同數(shù)量的線程優(yōu)先級。因此，應(yīng)采用分層分配來保證整體公平性，從而避免頻繁將線程遷移到空運(yùn)行隊(duì)列的需要。

線程選擇器：線程選擇器決定接下來將執(zhí)行每個(gè)內(nèi)核的運(yùn)行隊(duì)列中的哪個(gè)線程。線程選擇器通常會優(yōu)先考慮瓶頸線程，以避免線程被阻塞太久而導(dǎo)致性能損失。在多線程多程序環(huán)境中，可能需要同時(shí)加速來自不同程序的多個(gè)瓶頸線程。不像之前的瓶頸加速調(diào)度程序那樣簡單地檢測瓶頸線程并將它們?nèi)糠峙浣o大核，線程選擇器需要做出協(xié)作決策——理想情況下，大核和小核核心將同時(shí)運(yùn)行瓶頸線程。核心敏感性通常對線程選擇器并不重要，它做出的決定完全由瓶頸加速來指導(dǎo)。一個(gè)例外是大核心的運(yùn)行隊(duì)列為空并且調(diào)用線程選擇器時(shí)。只有在這種情況下，才應(yīng)考慮就緒線程的核心敏感性的加速因素。必要時(shí)，大核甚至可以搶占小核上的線程執(zhí)行。最后，線程選擇器還關(guān)注公平性。通過更新線程選擇器的時(shí)間間隔來縮放線程的時(shí)間片已被證明可以保證線程的相等進(jìn)度并實(shí)現(xiàn)多線程單程序工作負(fù)載的公平性。然而，僅僅確保所有線程的平等進(jìn)程是不夠的，不足以保證跨程序的公平性。線程選擇器應(yīng)確保每個(gè)單獨(dú)的程序都能平等地進(jìn)行使用大核和小核來加速瓶頸為此提供了機(jī)會。線程選擇器試圖通過盡快加速所有程序的瓶頸線程來確保程序之間的公平性。

運(yùn)行時(shí)協(xié)作

核心分配器和線程選擇器協(xié)作以實(shí)現(xiàn)性能和能耗之間的良好折衷，同時(shí)確保公平。模型的流程圖如下圖所示。

基于加速預(yù)測和瓶頸識別的運(yùn)行時(shí)模型，通過定期將就緒線程分類（使用標(biāo)簽）分為兩個(gè)不同的類別來促進(jìn)協(xié)作。

核心分配標(biāo)簽：在大核心上具有高預(yù)測加速的線程將被標(biāo)記為大核心上的高優(yōu)先級。具有低預(yù)測加速和阻塞級別的線程，即非關(guān)鍵線程，將在小核心上獲得高優(yōu)先級（在大核心上獲得低優(yōu)先級）。剩余線程在大核或小核上獲得相同的優(yōu)先級——然后可以自由分配這些線程以平衡核的負(fù)載。

線程選擇標(biāo)簽：具有高阻塞級別的線程將被標(biāo)記為本地線程選擇的高優(yōu)先級。無論它們是在大核還是小核上執(zhí)行，都將給予這些線程相同的優(yōu)先級。該標(biāo)簽仍然記錄了當(dāng)前核心的類型——如果存在具有空運(yùn)行隊(duì)列的相同類型的核心，線程總是優(yōu)先被相同類型的核心選擇。在小核心上運(yùn)行的線程也被標(biāo)記，因?yàn)樗鼈兛赡軙诤线m的時(shí)候被搶占在大核心上遷移和執(zhí)行，但運(yùn)行線程永遠(yuǎn)不會優(yōu)先于等待就緒線程。

標(biāo)簽后處理：在標(biāo)記過程之后，公平性、核心敏感性和瓶頸加速由線程上的標(biāo)簽表示，并且可以由核心分配器、線程選擇器或兩者一起處理。基于這種協(xié)調(diào)模型，核心分配器和線程選擇器從就緒線程集中處理不同的優(yōu)先級隊(duì)列——它們的決策不會像WASH這樣的混合多因素直接排名。相反，他們提供了一個(gè)基于時(shí)間片的協(xié)作方案。

協(xié)同多因素模型處理的另一個(gè)重要問題是確保線程的平等進(jìn)展，我們不會干擾線程選擇的優(yōu)先級和決策，而是根據(jù)在大內(nèi)核上運(yùn)行的線程的預(yù)測加速值，通過按比例縮放的時(shí)間片方法在線程中實(shí)現(xiàn)相等的進(jìn)展。大核上的線程片比小核上的相對短。線程選擇功能更頻繁地被觸發(fā)以交換大核上的執(zhí)行線程，這保證了在所有核上執(zhí)行的線程的相對等進(jìn)度。運(yùn)行時(shí)模型會定期提取性能計(jì)數(shù)器，該計(jì)數(shù)器代表AMP上多線程多程序工作負(fù)載的當(dāng)前執(zhí)行環(huán)境。模型計(jì)算更新的運(yùn)行時(shí)因素包括預(yù)測的加速值和阻塞計(jì)數(shù)。此信息附加到線程并報(bào)告回多因素貼標(biāo)機(jī)以供下一輪使用。

03總結(jié)

本期報(bào)告著重介紹了COLAB運(yùn)行時(shí)優(yōu)化框架，該框架針對非對稱多核處理器(AMP)上的多線程多道程序工作負(fù)載。AMP在當(dāng)今處理器市場尤其是嵌入式系統(tǒng)中占據(jù)重要部分。COLAB是第一個(gè)通用調(diào)度程序，通過對核心敏感性、線程關(guān)鍵性和調(diào)度公平性做出協(xié)作決策，優(yōu)化了影響AMP調(diào)度的所有這三個(gè)因素-核心親和力、線程關(guān)鍵性和調(diào)度公平性。COLAB調(diào)度程序在性能方面分別比最先進(jìn)的WASH、ARMGTS 和LinuxCFS調(diào)度程序高出21%、20%和25%，平均系統(tǒng)吞吐量高了6%、2%和15%，與WASH和ARMGTS相比，COLAB實(shí)現(xiàn)了平均5%的節(jié)能。

審核編輯 ：李倩