01背景介紹

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

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

02COLAB方案概覽

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

03總結(jié)

本期報(bào)告著重介紹了COLAB運(yùn)行時(shí)優(yōu)化框架，該框架針對(duì)非對(duì)稱多核處理器(AMP)上的多線程多道程序工作負(fù)載。AMP在當(dāng)今處理器市場(chǎng)尤其是嵌入式系統(tǒng)中占據(jù)重要部分。COLAB是第一個(gè)通用調(diào)度程序，通過(guò)對(duì)核心敏感性、線程關(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é)能。

審核編輯 ：李倩