2019科創講堂

動態優化技術

講者/台灣大學資訊工程學系教授兼副系主任 徐慰中

撰文/整理/科學人
2019/06/04

2019科創講堂

動態優化技術

講者/台灣大學資訊工程學系教授兼副系主任 徐慰中

撰文/整理/科學人
2019/06/04


計算機科學不管哪個領域都需要做優化,優化處理器設計、優化網路頻寬的使用、優化應用程式的效率等等。以往是靜態優化居多,現在動態優化也慢慢崛起。


靜態優化 vs. 動態優化


台大資訊工程學系教授兼副主任徐慰中,首先為我們介紹靜態與動態優化的區別。靜態是先優化再散佈,譬如程式碼在編譯時期就把優化做好了,然後再將程式碼散佈給使用者, 而動態優化則是在機器執行時仍可以進行程式碼的優化。


徐慰中巧妙地以新聞為例,傳統報紙都是內容已經印好了再散佈,這就像是靜態優化;而網路新聞是先拿到內容,再根據使用者習性決定要呈現哪些內容,或是根據裝置決定如何呈現,網路新聞內容可以臨時修改,甚至可以刪除,這就像是動態優化。


有時軟體優化耗時甚久,因此靜態優化的好處是,程式執行時就不必再加上優化時間, 所以可說是優化一時, 享用萬次。相反的,動態優化的優化時間包含在執行時間內。但動態優化可以做到一些靜態優化做不到的事,它可以針對不同的底層機器、工作環境、執行路徑做不同的優化,或是針對效能真正出問題的地方做優化,還可以根據個人使用變得客製化。


其實,靜態與動態各有所長,動態優化不是用來取代靜態優化,而是用來輔助靜態優化。


動態優化崛起


以往很少人做動態優化,直到2000年後才慢慢受到注重。最主要的原因是微架構的進展使得處理器效能大幅增加,也提供很多機會讓編譯器發揮優化的能力。


舉例來說,假設微處理器一個指令週期能執行六個指令,但編譯器在這週期內卻只排入了一個指令,因為程式區塊內指令都是相關的,不能獨立執行,如此就浪費其他五個指令位置。這時編譯器就會想去用投機性優化(speculative optimization),把下面有可能執行到區塊內的指令預先移過來執行,如果猜對了, 執行的確是所預測的路徑, 優化就成功了,如果猜錯, 這優化恐怕反成了劣化。


所以該如何確保「預測」做得準確而提昇投機性優化的效率?徐慰中介紹了三個方法。


第一個方法是,編譯器可以收集程式過去的行為(profile)來協助預測。你可以用以前執行完成的結果來靜態產生profile,或是在程式執行時候,透過觀察來動態產生profile,動態收集的profile通常比靜態準。收集profile有兩種方式,一種是侵入式的做法,在程式裡插入探針,就可以在程式執行時收集各種資訊;另一種是用處理器的硬體觀測(hardware monitoring)在程式執行時觀察各種發生的事件,把事件收集起來當作預測的參考。


第二個方法是用機器學習來做預測,前提是要有足夠的大數據,目前尚在積極研究階段。但大家仍對機器學習寄予厚望,因為它常能夠發現一些人類沒注意到的事,預測也比較準確。


以上兩者是用過去發生的事情來預測末來,而第三個方法是往前看,程式執行時抽取一個執行緒專門做預測,就像大軍出發會先派出斥候偵查一樣,稱為偵測執行緒(scout thread)。舉例而言,偵測執行緒可跑在主程式之前, 提前算出陣列運算所需要的記憶體位址, 就可以預先暖化快取記憶(Warm-up Cache), 減少快取迷失(Cache Miss) 造成的效能損失。


徐慰中笑著說:「我有一個夢,希望有一天所有的系統都能自我優化,發揮系統最佳的效能。希望未來的動態優化可以帶我們到這個境界。」