A分項計畫：嵌入式繪圖處理器系統軟體研發（主持人李政崑教授）
子項計畫1：嵌入式繪圖處理器編譯器技術（清大李政崑教授、台科大黃元欣教授）
[1] 嵌入式編譯器基礎建設及最佳化
隨著嵌入式系統上的處理器數目增加，如何提供編譯器工具讓軟體開發者善用系統上的MPU、GPU及DSP的硬體特色及運算能力，成為一值得探討及極具挑戰的問題。OpenCL標準的提出解決了這大部分的問題，透過OpenCL所定義的C99語言擴充 (Language Extensions)、多種程式設計規範 (Programming Models)、平台函式庫 (Platform APIs)、執行期函式庫 (Runtime APIs)、編譯器及執行系統(Runtime)的支援，程式設計人員可運用多顆處理器核心來進行平行運算，並妥善利用到MPU、DSP及GPU上的SIMD指令來加速程式。OpenCL承自C99並擴充了C語言來支援底層平行運算單元的程式語法，OpenCL支援了向量的運算讓使用者可善用硬體SIMD指令，OpenCL亦提供了許多控制平台的 APIs，方便使用者控制底層運算單元來進行平行運算。在平行運算機制方面，OpenCL提供了基於Task分割和Data分割的並列運算機制，在撰寫平行程式時具有相當大的彈性。OpenCL編譯器的支援將分作底下幾項工作： 首先，需能編譯擴充的C99語法，如Kernel函式關鍵字及Vector向量資料型別。其次，需提供目標平台如GPU及SIMD的暫存器配置及指令排程。最後，編譯後的OpenCL程式需與平台函式庫以及執行期函式庫整合，以支援於裝置端運行OpenCL必要的內建函式。[2] 編譯器PPA基礎研究及規畫
在C-like語言中，如C, C++, C#及OpenCL，純量變數(Scalar Variables)的使用情況可以很容易地藉著編譯器（Compiler）的分析，知道之間的相依關係；但常被大量使用的指標（Pointers），卻不能夠容易的被分析相互之間的關係。其中問題是當用到此類語言中的Pointers時，Pointer可能是指到一個從C的原始碼看不出來的位置。利用Pointer Probalistic Analysis (PPA) 的資訊可以讓編譯器做更積極的優化如；幫助編譯器或程式設計者在嵌入式系統中更容易做資料上的分配，預期可以帶來更好的效能、耗電比；亦或將資訊使用在OpenCL 架構中Kernel的分析上，做Variance Analysis 及Divergence Analysis。本項目將延續之前團隊已經發表的論文，改採使用開放原始碼的Open Research Compiler (ORC)並且使用Single Static Assignment (SSA) Form來改進分析的效能與準確度。[3] 編譯器SIMD最佳化研究
長久以來SIMD (Single Instruction, Multiple Data)常被使用來當作加速資料及訊號處理的途徑，其運作原理為：執行一道指令可分別作用在多筆資料上，如以一道乘法指令完成多筆運算，以此減少程式花費在流程控制的時間。SIMD在硬體上已被廣泛實現，如現今在微處理機上的多媒體擴充指令集(MME)、數位訊號處理器(DSP)的Subword指令集、以及高階遊戲機(Game Console)及圖形處理器(GPU)上的SIMD指令。但如何有效率的使用底層硬體所提供的SIMD特色，在撰寫SIMD程式中一直是個議題。為此OpenCL規範了如下對於SIMD的支援：首先，OpenCL提供語法讓程式開發者可描寫運算核心(Kernel)，也就是個將在各個OpenCL處理單元(PE)上執行的函式，其中可能包含多道運算的敘述，透過OpenCL同時讓多個PE執行同一個運算核心，每個PE有著共同的PC值，執行相同的函式中的同筆指令，但作用在不同的資料上，以達到SIMD並行處理的目的。除此之外，OpenCL亦擴充了C99來提供向量資料型別，讓使用者可在運算核心中宣告向量資料，如char4, int4及float4等。這些向量的運算在OpenCL的編譯中可被對應到底層的硬體指令，讓每個PE可使用硬體的SIMD指令一次可進行多筆8-bit至64-bit的整數或浮點數運算。最後，透過編譯器對於運算核心進行自動向量化(Autovectorization)，在編譯的過程中除了將向量資料型別對應到硬體SIMD指令外，還可將運算核心中的純量資料運算轉換成向量運算，並讓一個PE同時處理多個運算核心的計算以增進SIMD的效果。[4] 繪圖處理器之Divergence最佳化
在GPU程式執行時，核心 (Kernel) 的平行執行緒 (Thread) 單位群被稱為Warp或Wavefront；然而同一個Warp 或Wavefront內的所有執行緒卻在同一個時間只能執行一個同樣的指令，因此當核心內存在有分歧 (Branch) 的程式時，在Warp或Wavefront內的執行緒就僅能作連續 (Serially) 的執行而非平行處理。如果沒有注意這個問題，核心內的程式效能會大幅的降低。因此希望透過資料的配置，達到同一個Warp或Wavefront內的執行緒都能夠在同一個時間執行同樣的指令的效果，如此一來可以避免效能的大幅降低。如圖 8所示，在相同的程式中，若核心內沒有發生Divergence的狀況所測得的執行時間我們將其標準化(Normalize)成1，相較於無divergence及有divergence成兩個pathes的程式，執行時間幾乎是呈倍數成長；而Divergence成三個pathes的程式，幾乎是呈三倍的時間成長。因此對於這樣的現象如果可以經過分析進而避免發生，可以使核心的效能成倍數的優化。[5] 裝置與雲端工作分配編譯器技術
隨著行動裝置(Device)的普及，使用者對於多媒體服務的執行需求增高，隨著多媒體技術的提升，單就裝置上的處理器可能無法負荷複雜的執行運算，抑或者需要有耗能、非同步運算等等不同的考量，經由卸載(Offload)運算至雲端(Cloud)執行來達到目的；而當雲端上的應用程式欲卸載到不同的裝置上運行，也需要一套雲端至裝置的運算模式，來幫助開發者縮短工作分配以及配置的時間。然而，如何整合不同平台上的設計模式(Design Pattern)以達到提升平行運算或是節能的效果，成為一個值得探討的問題。圖 9所示，我們可將工作切割成Programming Language、Parallel Algorithm、Compiler Support、Concurrent Execution、Embedded Hardware五層。應用程式中圖形處理器運算的程式由可由如OpenCL等高階語言來撰寫，搭配平行化語義(Ontology)以及不同的運算模式等支援。我們可以將不同的運算模式實作出函式庫或是直接提供模板給開發者，而透過語意的描述可以讓我們對應不同的應用平台來做動態的調整之後可利用及時編譯技術如LLVM等針對不同的雲端平台或是裝置來編譯成不同的版本，設計模式(Design Pattern)為根據不同問題的領域，提供一套整合的解決方案。
子項計畫2:可重定目標二元碼轉譯系統（交大楊武教授、清大許雅三教授）
[1] 靜態二元碼轉譯系統
本項目中將實作一個靜態的二元碼轉譯器(Static Binary Translator)，將二元碼轉譯至LLVM 的指令集(i.e., LLVM IR)，再透過LLVM 的靜態編譯器將轉譯出來的LLVM IR 編譯成不同平台的二元碼來執行，如此一來我們不需要實作不同平台的Code Generator 和Optimizer，便可輕易的實作出一個有效率且可重定目標(Retargetable)的二元碼轉譯系統，讓程式在沒有原始碼的情況下也能夠輕易地移植到不同的硬體平台。[2] 自動化驗證工具
由於我們的二元碼的轉譯是透過LLVM 來實作，雖然不需要根據不同的目標指令集實作出不同的Code Generator 及Optimizer，但是轉譯到目標平台的二元碼轉我們也很難知道是由原始二元碼的哪一個指令所轉譯過來的。除此之外，轉譯過後的二元碼在執行時，我們也沒辦法知道所模擬的原始指令集目前的Architectural State。這會對驗證和除錯轉譯過後的二元碼造成很大的困難。我們希望能夠結合LLVM 所提供的Metadata 的功能，在轉譯出來的LLVM IR中插入除錯的資訊，並結合現有的工具實作出容易除錯甚至能自動驗證的二元碼轉譯系統。[3] 動態二元碼轉譯系統
靜態的二元碼轉譯(SBT)系統雖然能夠對轉譯後產生的二元碼進行大量的優化並帶來程式執行效率的提升，但是因為缺乏Runtime的資訊，有些問題在靜態轉譯時並無法有效的解決，例如Code Discovery Problem、Code LocationProblem、及Self-modifying Code (SMC)。因此我們希望能夠將前一年度的研究成果(i.e.,靜態二元碼轉譯系統)結合LLVM的JIT編譯器，實作出一個可重定目標的動態二元碼轉譯(DBT)系統來彌補靜態轉譯的不足。[4] 結合靜態和動態的混合型二元碼轉譯系統
靜態轉譯系統所轉譯出的二元碼可以執行大量的優化，但卻無法完美的處理Code Discovery Problem 及Code Location Problem；動態轉譯系統在執行時期雖然會有額外的負擔，但卻可以有效的處理靜態轉譯無法處理的問題。我們希望結合這兩個系統的優點，建立出一個混和型的二元碼轉譯系統。
子項計畫3:繪圖處理器之自動化可擴充指令最佳化設計（交大 劉志尉教授）
[1] SW/HW co-design based on high-level hardware simulation library
由於進行軟硬體協同設計的一大瓶頸即在於軟硬體不同的programming model及開發環境，因此本項目將開發一套高抽象程度之擴充指令集硬體函式庫，讓使用者可在高階語言中置換欲加速之運算，並進行效能及成本評估。且利用native simulation大幅加速初期軟硬體協同模擬的速度。[2] 運算模型識別(computation pattern identificaiton)
本項目將開發一套利用圖學理論找出常見的基本運算模型，利用此基本運算模型進行平行式或串接式運算，建立基本擴充指令集，根據使用者需求最佳化資料路徑架構設計。[3] 自動化可擴充指令集最佳化設計合成
本項目將探討如何利用基本運算指令組合出更複雜之擴充指令集，且根據程式本身的平行度，硬體成本，探討最佳組態。同時進行各個不同資料路徑共用設計，一來可以降低reconfiguration的時間，同時也能提高資源的使用率。[4] FPGA-enabled GPU/Host interface design
本項目將研究軟硬體介面設計，許多文獻揭露不良的軟硬體介面設計將嚴重影響異質運算平台之效能，因此我們預期設計一低成本，高效率之軟硬體介面，負責FPGA-enabled GPU與host processor的溝通及組態設定。[5] Run-time resource management
本項目預計設計一硬體化控制器，能夠隨著應用程式執行動態的調整資料路徑，像是需要提高效能時，可以動態增加運算單元。或是改變資料路徑組態以達不同需求像是低功耗。
子項計畫4:LLVM編譯器軟體研發（清大 李政崑教授）
[1] LLVM編譯最佳化技術
由於各式各樣的 Google Android 產品，如: 智慧型手機、平板電腦、TV …等不斷的推陳出新，這些平台上具有不同的硬體架構，為了使開發出的應用軟體可以在不同的平台上執行，Google 採用了LLVM 編譯器來作on-device compilation 與 jit compilation。由於這些產品的系統資源是有限的，因此如何在有限的時間內編譯出具有高效能與code size 優勢的執行檔將是一個重大議題。本項目將發展 LLVM編譯最佳化技術，包含了 LLVM optimization with phase selection 、 LLVM optimization on code size reduction 與 LLVM Machine Code(MC)。[2] Renderscript編譯及最佳化技術
目前高階2維和3維繪圖技術已經大量的被應用在各式各樣的行動資訊裝置上(智慧型手機、平板電腦、GPS和車載資訊娛樂系統…等)而相關的應用需求也持續增加，為了兼顧效能以及功耗開發人員必須充分利用內嵌圖形處理器以及其他異質處理器的運算能力，目前Renderscript的技術可以達到上述的需求， 在Android的開發平台上Renderscript可以用來控制 3D Rendering以及其些其他異質處理器的運算工作，由於Renderscript是C99的Extension加上可以透過LLVM編譯轉換變成Bit code以及Java Code，增加開發上開發的便利性以及可攜性，因此可預期Renderscript未來將會成為行動資訊裝置上得重要技術，本分項將會研究Renderscript的編譯以及最佳化技術，包含了Offline Compilation Techniques、On-line JIT Compiler以及Runtime Library Support。