• 學位論文

高效能視訊編碼之適應性迴圈濾波器研究

本論文針對高效能視訊編碼中適應性迴圈濾波器進行研究，適應性迴圈濾波器 可去除重建畫面中量化後的雜訊，提升重建畫面的品質。高效能視訊編碼中 適應性迴圈濾波器是基於整體畫面資訊做濾波器優化，必須等待整張畫面編碼完畢之後暫存所有區塊的資訊以取得最佳濾波器係數，不僅需耗費額外記憶體空間儲存，同時也造成編碼延遲的上升。直接套用先前已重建畫面的濾波器係數於目前的編碼畫面，雖解決編碼延遲的問題，但此方式並非該編碼畫面的最佳濾波器係數設計。為每個區塊設計一組目前編碼畫面中最佳濾波器係數，雖有效解決上述問題，但濾波器係數數量可能因畫面大小而呈正比成長。在不考慮編碼延遲上升的情形下，本論文探討適應性迴圈濾波器對於畫面品質的改善極限，提出基於整體畫面資訊之濾波器優化演算法，利用階層式四分樹切割方式將畫面作分割後再以Bottom-up的方式進行不規則合併。 期望達成單一區塊編碼延遲並同時取得區塊之最佳濾波器係數。實驗結果顯示本論文提出的演算法在解析度1920x1080之視訊序列下平均達0.3%的壓縮效能提升，而雙區塊編碼延遲之設計則造成0.3%的壓縮效能下降，但兩種方法皆能有效地提升重建畫面的主觀品質。

• 學位論文

使用核關聯之非剛性形體對齊與對應

我們提出一個非剛性形體間之對齊與對應的方法。許多基於形變的方法改進迭代最近點法，並且將形體之對齊與對應的問題轉化為最佳化問題。然而，基於迭代最近點法的非線性能量系統必須在每次迭代時改變對應的最近點，並且移除當中被認為是不好的對應。此項行為造成最佳化的過程中改變了能量系統，因此最佳化處理時無法直截了當地求解。相反地，我們使用基於核關聯的方法來表示非線性能量系統，此法間接地給了動點一個方向，並且保證最佳化過程中擁有固定的數學表示式。我們的演算法不將每個形變物表上的取樣點對應到目標表物表上的另一個取樣點，而是將其對應到目標物表上的一個合理位置，因此獲得更合意的對齊與對應結果。此外，我們的演算法因擁有固定的數學表示式而能更有效率地求出最佳解。

• 學位論文

用於擺置繞線流程的可繞度和效能最佳化技術

近年來，隨著奈米技術的進步，晶片中的元件越來越多，同時繞線的難度也越來越高。晶片的可繞性(Routability)成為眾人所觀注的議題。在該議題上，全域繞線(Global Routing)扮演著重要的角色。在電路實體設計(Physical Design)的流程中，全域繞線上承元件擺放(Placement)，下啟細部繞線(Detailed Routing)。一個快速的全域繞線器能提供擁擠度(Congestion)的資訊給擺放器，讓擺放器擺出較容易繞線的布局。此外，若全域繞線器能有效的解決繞線擁擠度的問題，細部繞線的負擔和所需時間可以大幅降低。當全域繞線器和擺放器合作時，全域繞線器如何快速且準確的回報擁擠度資訊給擺放器是一個重要的議題。另一方面，當全域繞線器扮演細部繞線器的指導者角色時，全域繞線結果的品質就顯的格外重要。若細部繞線器能根據一個高品質的全域繞線結果進行細部繞線，將會提升細部繞線結果的品質，並大縮短細部繞線的時間。這篇論文提出了兩個全域繞線器: Grace是個快速的全域繞線器，適合擔任擁擠度預估器; NCTU-GR 2.0能產生高品質的繞線結果來指導細部繞線，其繞線結果較不擁擠且有較短的線長。此外，為了將Grace應用於業界，我們增加了許多功能於Grace中來滿足業界的需求。在擺放和繞線的中間階段，我們結合了擺放器和全域繞線器，提出了一個可繞性優化器(Routability Optimizer)。若給予一個布局結果，該優化器可以重新擺放其中的元件，讓該布局更容易被繞線，進而得到更好的繞線結果。最終，在進行細部繞線前，我們還提出了一個三維繞線改善器，將全域繞線的結果在做進一步的改善，此舉可以更進一步的降低細部繞線器的時間和負擔。

• 學位論文

適用於都會區車載網路的動態覆蓋式群播機制與基於道路之預測式多路徑繞徑協定

在車載網路中，多媒體串流及群組通訊為兩種重要且有潛力的服務，而一個高效能的繞徑協定將能顯著地提升來源端至接收端的多媒體串流效能。因此，在本論文中，在應用層我們提出一個動態覆蓋式群播機制來提供實況多媒體串流給群組節點；而在網路層我們提出一個新穎的服務品質感知之基於道路多路徑繞徑協定。我們所提出的這兩個方法都旨在都會區車載網路中提供流暢的多媒體串流服務。 在都會區車載網路的各種應用服務中，提供資訊娛樂服務(infotainment service)已經是可預見的趨勢，而多媒體串流是潛力極高的資訊娛樂服務。我們考慮的情境是在群組車輛間進行實況多媒體串流群播服務，為此我們使用動態應用層覆蓋(dynamic application-layer overlay)方式來達成。由於非群組中的車輛不一定願意合作來協助群播，因此以應用層覆蓋式群播的方式會比其他種類的群播方式，如基於網路編碼之群播以及網路層群播，更具彈性。因此，為了適應都會區車載網路高移動性及障礙物密集的特性，我們提出了一個稱作OMV (Overlay Multicast in VANETs)的高效能動態覆蓋式群播機制來提供多媒體串流。在這個OMV方法中，我們提出兩項策略來增強覆蓋(overlay)的穩定性：(1)滿足服務品質之動態覆蓋及(2)網狀結構之覆蓋。滿足服務品質之動態覆蓋的策略是按照封包遺失率及端到端延遲時間來挑選潛在的新父節點，以優化此覆蓋架構。而網狀結構之覆蓋的策略是允許子節點可擁有多個父節點。我們採用了兩個真實的影音短片來評估及驗證OMV在多障礙物的都會區車載網路中傳送影音的可行性。評估結果顯示，相較於目前在車載網路上最佳的方法—Qadri等人使用靜態網狀覆蓋的研究，平均來說OMV降低了27.1%的封包遺失率、11.7%的端到端延遲時間，但只增加2.1%的額外控制負荷。我們並將樹狀OMV與ALMA作比較，其中ALMA為另一個樹狀覆蓋式群播且是行動隨意網路(MANETs)中的最佳方法，OMV降低了7.1%的封包遺失率及13.1%的端到端延遲時間。此外，針對都會區車載網路中障礙物密集的問題，我們歸納出在不同的道路疏密度下可行之串流速度與群組大小。據我們所知，現有的車載網路文獻中尚未有如何動態地調整應用層群播覆蓋架構，以有效傳送多媒體串流的研究。總結來說，為處理都會區車載網路中高變動的拓樸，我們提出一個能滿足服務品質的策略，使群組節點可切換至能提供較佳服務品質的新父節點。我們所提出的OMV適用於實況多媒體串流，例如緊急實況影音傳輸及同一群組車輛的遊客們實況影音導遊。 至於在網路層中，穩定且效能高的繞徑是車載網路成功的關鍵。現有文獻已經證明基於道路的繞徑方式是非常適用於車載網路。此外，一旦使用中的路徑失敗時，多路徑繞徑方式可提供額外的路徑供切換。然而，現有的多路徑繞徑協定皆為基於節點的繞徑方法，因此並不適用於都會區之車載網路。在本論文中，我們也提出了一個適用於都會區車載網路之新穎的服務品質感知之基於道路多路徑繞徑協定(RMRV)。我們所提出的RMRV能找到多條路徑並且被有效地使用。我們提出了一個新穎的時空平面圖(space-time planar graph)的方法來預測一條路徑中各個路段的連通性，以得到此路徑未來的各個存活時段(life periods)。如此一來，源節點(source node)可動態地切換使用一條目前是連通且延遲時間較短的路徑，我們稱此為基於服務品質之路徑切換方法(QoS path switching)。採用此方法可預先避免封包遺失及可選用潛在延遲時間較短的路徑。模擬結果顯示，相較於另一個代表性的基於道路單路徑之繞徑協定，RBVT-R，我們所提出之RMRV（一次只使用一條路徑來傳送資料）提高了16.6%的封包送達率、降低了35.3%的端到端延遲時間，以及減少了45.8%的額外控制負荷。據我們所知，現有文獻中尚未有適用於車載網路的基於道路之多路徑繞徑協定。

• 學位論文

高效能快閃記憶體轉換層設計之研究

快閃記憶體在支援磁碟使用的檔案系統時，需要在快閃記憶體上增加一個快閃記憶體轉換層，提供區塊裝置式介面。因為快閃記憶體有寫入前需抹除的特性，快閃記憶體轉換層使用異地更新及清除流程去回收含廢棄資料的區塊。這些回收的成本是快閃記憶體轉換層效能的關鍵，因為清除流程使用的動作，例如複製頁、抹除區塊等等，都非常耗時。為達高效能的目的，快閃記憶體轉換層應該要最小化清除成本。 為了索引邏輯頁的實體頁位置，快閃記憶體轉換層負責維護兩者之間的對映表格。混合式位置轉換快閃記憶體轉換層將快閃記憶體區分為兩個區域，大的資料區域使用邏輯區塊對應實體區塊的管理；小的日誌區域使用邏輯頁對實體頁管理。藉此控制對映資訊的數量，並且達到良好的效能。 本論文提出了兩個混合式位置轉換快閃記憶體轉換層。第一個名為ROSE，其中包含了三項用來降低清除成本的新技術。首先，它透過避免連續寫入整個區塊的頁落入不同的區塊，藉此降低回收的成本；同時，不會將隨機寫入、不完全連續寫入，誤判為連續寫入，避免因誤判隨之而來的代價。其次，採用針對混合式位置轉換快閃記憶體轉換層來設計、同時考量區塊的新舊與合併成本的清除方針，藉此提高清除的效率。最後，藉由延遲抹除尚有空白頁的廢棄區塊，並回收使用這些空白頁。 第二個快閃記憶體轉換層名為 HybridLog。透過有效率的使用備用區域，HybridLog 在所有的區塊進行日誌式的寫入，有效率的支援新型的 NAND快閃記憶體。日誌式寫入能夠避免寫入無謂的空白資料進入頁，以及降低因為資料區域目標頁已經被寫過、而寫入日誌區域的機率。 我們透過模擬評估上述兩個我們所提出的快閃記憶體轉換層的效能。我們使用三個知名的混合式位置轉換快閃記憶體轉換層作為效能比較對象。評估結果顯示，我們所提出的快閃記憶體轉換層的表現優於比較對象。

• 學位論文

通用圖形處理器裝置之抽象化與資源管理研究

最近幾年在高效能運算(HPC)領域中，運用異質多核心加速原有應用程式，已成為平行運算之顯學。其中具有多繪圖處理器之平台，俗稱桌上型超級電腦，因具有便宜，高效能的優點而眾所採用。然而現今的異質多核心運算程式語言模型，例如OpenCL，並不具針對有多裝置平台的運算資源管理，當使用此種平台時，程式設計師必然需實作裝置資源管理，例如裝置排程，記憶體一致性維持等。又因排程所需的資訊(例如裝置忙碌程度)不為設計者所知，程式設計師所選之運算裝置不一定為最佳選擇。因此，本論文提出一OpenCL裝置抽象化及資源管理架構VirtCL，此架構分為兩部分：前端之OpenCL相容程式庫，目的在提供OpenCL應用程式與後端資源管理平台之抽象化裝置及介面。後端之資源管理平台，目的在滿足前端提出之通用計算之需求，以及實作記憶體管理和裝置管理排程。我們提出一個COST排程器，期根據kernel運算時間之歷史結果以及OpenCL指令在各裝置之所需等待時間，為使用者選出一最佳裝置。實驗結果顯示，VirtCL架構實作之抽象化界面具有相當小的成本(平均10.44 %)，我們所設計的排程器，能夠依裝置數量之不同，提供接近相應之效能。最後的排程模擬測試顯示，我們的排程器在系統負載高時，相較於最短等候列排程器，能夠提供2倍之效能。

• 學位論文

多重圖形處理系統上之OpenCL程式內核的自動平行化排程

隨著異質多核心架構的系統與 OpenCL 平行化的程式語言模型的日趨成熟，傳統處理器(CPU)與通用圖型處理器(GPGPU)的協同運算已廣泛運用在生物資訊、財務金融預測、大氣模擬等科學領域；而硬體製程工藝的進步與軟體設計的需要，大至雲端運算級的大型伺服器叢集系統，小至家用電腦甚至是手持裝置，具有多個GPGPU 或CPU 裝置的硬體系統已然普及。但現行的軟體系統並無法針對多個裝置的運算資源做最佳化的調控與配置；由於OpenCL 的程式語言模型設計，舊有的應用程式在多個裝置上也無法獲得更高的效能。 本研究主要目的為提供一個OpenCL 的抽象層，包含靜態分析與運行環境系統，前者可分析舊有應用程式中運算kernel 的相依性，後者根據靜態分析的資訊進行運算資源的分配，其中包括記憶體的同步與管理系統與運算kernel 的排程分配系統，使舊有的應用程式可以分配在多個裝置上計算，並以單一的裝置介面提供程式設計者進行API 的操作，簡化多個裝置間資源分配與同步的考量，進而減輕在撰寫時的負擔。我們將實作成果與原生具備單一裝置的 OpenCL runtime 做比較，在使用一個、兩個與四個裝置上執行的平均效率依序為 95%，92%與87%。總體的overhead 平均約為5%，主要來自於應用程式與runtime 系統的資料傳輸語同步。

• 學位論文

多模式無線通訊應用下 高速8平行512點具有可變訊號量化噪聲比之 可調整式快速傅立葉轉換處理器

這個論文實現了一個可調整式快速複利葉轉換器，支援802.15.3c以及802.11n兩種通訊規格。在802.15.3c規格下可最高支援到2.4 GS/s 取樣頻率，FFT點數可支援512、256、128 三種點數，而802.11n規格下可支援1、2、3、4 四種天線數，FFT點數可支援128、64 二種點數。 整體快速複利葉轉換器的架構是採用管線式並搭配Radix2、Radix22 演算法做再利用的規劃，來達到硬體利用率的上升以及硬體的節省。此外設計了可調整訊號量化噪聲比與動態控制電流搭配不同的通訊規格來節省功率上的消耗。

• 學位論文

利用群聚法分析網路記錄

本篇論文藉由觀察網路用戶的連線行為，結合殭屍網路的連線特徵尋找校園網路內潛在中電腦病毒的受害機器以及由Domain Generating Algorithm(DGA)產生的惡意網域，我們針對無法連接的網域(NXdomains)提出了一個分辨一般網域以及由DGA產生惡意網域的特徵叫做Popular 2gram(兩個連續的英文單字)，並且透過群聚法以及分類法找到受害的機器以及惡意的網域。我們另外觀察受害機器的連線目標並且計算每一個受害機器的連線相似程度去法絕這些機器在一起行動時的行為模式。為了加快分析的時間，我們使用Hadoop的技術去分析大量的網路紀錄。本論文提出的方法可以提供中毒機器的連線行為模式，惡意的網域以及IP的資訊給網路管理人員，使網路管理人員能做出相應的措施此殭屍網路所造成的傷害降低。 關鍵詞:殭屍網路、動態網域產生演算法、群聚法、機器學習、分散式阻斷攻擊、海量 資料、網域名稱系統。

• 學位論文

應用組合對局知識解決遊戲及改良搜尋效能

本篇論文，主要是應用組合對局知識解決遊戲及改良搜尋效能。組合對局理論已經成為許多益智遊戲分析的基本數學模型，其利用數學代數的特性來降低問題的複雜度。本論文主要研究三種組合對局遊戲，包括三角殺棋(Triangular Nim)、XT Domineering及NoGo。 首先，三角殺棋是一種Nim的變形，是流行台灣及中國的二人遊戲。本論文使用Retrograde方法，全解九層三角殺棋盤面，並運用旋轉及對稱方法，降低記憶空間需求達5.72倍，並增進運算速度達4.62倍。 第二、本論文介紹新的組合對局遊戲XT Domineering及其數學分析，XT Domineering其變化來自於Domineering。變化後的規則，在遊戲中所有盤面皆為微數字(Infinitesimal)，計算得出所有3×3盤面的遊戲值(Game values)，並得出每一盤面的遊戲值為8種基本微數字的線性組合，利用一個簡單代數和的式子，即可以迅速算出雙方勝敗，以取代搜尋全部遊戲樹(Game tree)。 第三、本論文分析2011年BIRS組合對局會議提出的一種新的組合對局遊戲NoGo，計算其許多4×4 NoGo盤面的遊戲值，發現其最高溫度（Temperature）為2，並在研究中推導出一些基本定理，以幫助我們瞭解NoGo遊戲特性。