計畫成員 : 鄭湘筠、蔡孟宗
在電腦計算的過程中，計算的瓶頸不全都來自於中央處理器的實際運算。前人根據計算瓶頸的不同，約略地將計算問題分成兩大類，第一類的瓶頸在於需要花費大量時間進行實際運算，而第二類的瓶頸在於等待資料從記憶體端搬遷至中央處理器或是等待資料從中央處理器寫出至記憶體。為了突破第二類問題的計算瓶頸，文獻上有許多方法，設法改善資料搬遷的速度。但這類的許多研究往往限制在以下框架，給定一個計算問題，假設務必使用某種已知的計算方法完成計算。這樣一來，改善資料搬遷壅塞狀況的重擔，往往都落在於硬體端的重新設計與改良。在這樣的框架下，人們忽略了在硬體端重新設計後，計算方法亦可以有非常大的改變。
近日有許多文獻在探討在記憶體端加入簡單的運算單元，從而將需要大量資料讀取的計算過程，分配至記憶體端運算，這類的方式往往變成類分散式計算的過程，會較不經濟地使用計算資源和能量。我們的實驗室研究方向其中之一在於探討：若計算架構改變時，如何重新設計計算方法來輕鬆完成等價的計算，我們的手段包含在演算法設計領域中被稱為資料概括的技術。
我們近期針對了許多基礎的圖論計算問題，設計了資料概括的技術，包含了廣度優先生成樹、深度優先生成樹、少葉節點生成樹、稀疏生成尤拉子圖、拆解成少量的無環子圖、拆解成等大小的連通子圖。在這些計算問題中，我們提出計算方法，僅在中央處理器及記憶體之間使用極少的資料傳輸便完成計算，從而緩解計算所帶來的資料傳輸壅塞。我們亦證明了我們的方法所需的資料傳輸量並不會遠多於任何其他方法。
雖然借重硬體架構的改變，許多資料傳輸壅塞的狀況可以被大幅改善，我們亦探討若在現有的硬體架構下，我們是否可以改變計算的方式來緩解計算所帶來的資料傳輸壅塞？我們從幾個基礎運算加法、減法 （已足以實現某些相當耗時的科學運算）來進行深度的討論，簡單地說，我們想要將雙向的資料傳輸改變成單向的資料傳輸。這樣的改變有一個重要的好處，亦即中央處理器在和存取裝置溝通時，交付完任務後便可以結束，無需等待存取裝置方面傳遞任何訊息。這樣的方式雖未減少傳輸的資料量，但卻大幅減少了不必要的等待，可以提升平均資料的傳輸速度，也能緩解計算所帶來的資料傳輸壅塞。這聽起來不大可行，但在許多基礎運算卻是可行的，包含上面列舉的加法和減法。
我們的實驗室綜合了軟硬體的設計，試圖解決計算所帶來的資料傳輸壅塞，在許多基礎圖論問題以及他們的延伸應用，都得到相當正面的結果。
