研究領域

Fault-Tolerant Computing (容錯計算)

當一個互連網路發生處理器或是連結線損壞時,研究是否仍然可找到各種長度的無損壞(fault-free)迴圈,使其涵蓋無損壞的處理器和連結線,就是容錯泛迴圈問題(fault-tolerant pancycle problem)。此問題在網路模擬(network emulation)有很重要的應用:當互連網路處理器或連結線損壞時,即可使用容錯演算法找出各種長度的無損壞迴圈,藉以執行發展在迴圈的平行演算法,使整個系統可模擬迴圈,而不致喪失效能。而在現今的文獻中,多數論文都是針對不同的互連網路(interconnection networks),利用其網路架構本身的特性,來深入探討容錯嵌入的性質;然而,欲探討某一種互連網路架構時,就得先剖析其本身的特性,再從中抽絲剝繭研究相關容錯嵌入的性質。研究方向則是找出互連網路架構的共同特性,探討這些互連網路是否只要符合某些性質,則此互連網路架構就會有容錯嵌入的性質。如此一來,只要剖析互連網路架構擁有哪些特性,即可得知是否具有容錯嵌入性質,並計算出其容錯度的大小,不必再針對個別的互連網路加以探討。

在未來的研究計畫中,除了持續探討不同拓樸結構的容錯能力之外,也將進一步思考將拓樸結構運用於實務上的可能性,例如:在無線通訊的議題上,若是擺放位置依照拓樸結構來設計,是否可以增加其系統的穩定性。

  • 研究計畫
  • 條件錯誤下正則網路之漢彌爾頓性質之研究(The Hamiltonian Properties of Regular Graph under the Conditional Fault Model), MOST 103-2218-E-006-019-MY3, 2014.08.01~2017.07.31 (科技部研究學者專題研究計畫)
  • 條件錯誤下侷限類超立方體的泛連通問題(Panconnectivity of Restricted Hypercube-Like Networks under the Conditional Fault Model),行政院科技部,MOST 102-2221-E-006-127-,2013.08-2014.07
Top

System-Level Diagnosis (系統偵錯)

系統偵錯(system-level diagnosis)是根據系統中各個處理機相互測試的結果,推導出系統中錯誤處理程序。系統偵錯原本應用在多處理機系統,最近晶圓測試也開始使用系統偵錯的技術,可見此主題具前瞻性及應用價值。偵錯度(diagnosability)是系統在偵錯過程中所能容忍的最大錯誤量,不同結構的互連網路,因其結構上的不同而有不同的偵錯度(diagnosability),在過去所發表的研究論文當中,多數論文也是網路架構本身的特性來探討該網路的偵錯能力。然而,欲探討某一種互連網路架構時,就得先剖析其本身的特性,再從中抽絲剝繭研究其偵錯度。研究方向則是考慮在兩個不同偵錯模式下(PMC model、MM* model),致力於找出不同的互連網路之間的共同特性,討論只要符合某些性質,其偵錯度即可計算得出。

在未來的研究計畫中,除了持續探討各種拓樸結構的偵錯能力之外,也將進一步思考如何將系統偵錯議題應用至實務上,例如:在新建大樓佈置網路系統時,若是考慮拓樸結構來設計,是否可以增加整個系統的穩定性,並且可以快速找出毀損節點的位置。

  • 研究計畫
  • 於PMC模型下合成網路圖之條件式偵錯度研究 (The Conditional Diagnosability of Component-Composition Graphs under the PMC Model), MOST 108-2221-E-143-004-MY2, 2019.08.01~2021.07.31
  • 正則網路之限制連通度與g好鄰條件式偵錯度之研究 (The restricted connectivity and g-good-neighbor conditional diagnosability of regular networks), MOST 107-2221-E-143-004, 2018.08.01~2019.10.31
  • 合成網路圖之偵錯度研究(The Diagnosability of the Component-Composition Graphs),行政院科技部,NSC 101-2221-E-006-236-,2012.08-2013.07
Top

Design and Analysis of Algorithms (演算法設計與分析)

Steiner樹問題是一個傳統的難題,這個問題在Euclidean metric或 rectilinear metric都已經被證明是NP-complete的問題。Steiner樹問題及其相關問題有廣泛的應用,例如VLSI 的廣域或局部的繞徑(local or global routing)、網路的繞徑(network routing)、電信通訊(telecommunications)、無線通訊(wireless communications)及傳輸(transportation)等。我們研究發現在一些實際應用中,部份端末點(terminals)需被限制為Steiner樹的內部點(internal nodes)。舉例而言,在網路資源分配(resource allocation),一些被對應到Steiner點的伺服器被指定當作routers,而其他的伺服器則無此限制。另外,在VLSI的廣域繞徑的問題中,某些端末點代表針角(pins)和閘門(gates),它們不允許為Steiner點,以增加穩定性﹔而某些端末點卻被允許可視為Steiner點以減少總成本(total cost)。

Top

Connectivity (連通度)

在建構多處理器系統時,我們通常會利用連通度(connectivity)性質來衡量一個系統的可靠度(reliability)及容錯(fault-tolerance)的能力。傳統的連通度會被圖形的分支度(degree)所限制,而一個處理器的相鄰處理器同時發生錯誤的機率很小,所以傳統的連通度可能不是一個很好的衡量標準。因此,我們進一步考慮一種通用且典型的連通度性質:條件連通度(conditional connectivity)。其中超連通度(extra connectivity)及限制連通度(restricted connectivity)是兩種被廣為討論的條件連通度問題。g-超連通度問題是討論圖形在移除點集合後,會產生二個以上的連通圖,且每個連通圖中至少有g + 1個點。h-限制連通度問題是討論圖形在移除點集合後,會產生二個以上的連通圖,且每個連通圖的最小分支度至少為h。

對於現今常被討論的互聯網路拓樸結構,我們嘗試計算出這些圖形的超連通度及限制連通度。

Top

Coloring Problem (著色問題)

著色問題的研究已經發展許久,在文獻上可以查詢到許多相關的著色問題文獻,至今仍然是一項被廣為討論、研究的一項重要的研究主題。在無線通訊的基地台設置問題,或者是物流轉運站設置問題,都可以藉由著色問題來解決。圖形的點排序問題是給定圖形上的每一個點一個顏色,使得若有兩個點擁有相同的顏色,則以這兩點為端點的每一條路徑上,必定存在一個擁有更大顏色的點。以線上即時的觀點來看點排序問題,點v1, v2,…, vn 是一個點接著一個點以任意順序的方式進入圖形中。而圖形的邊,則是由目前在圖形內的點其在原本的圖上有邊的那些邊所組成。並且給定顏色後就不能再做更改。我們針對在樹狀結構下之點排序問題設計了循序及平行的演算法。

而點排序的問題在目前的文獻上有更進一步的研究問題—c-ranking,因此,在未來的研究發展中,將會進一步探討相關的著色問題。

Top

Bioinformatics (生物資訊)

演化樹重建是一個在計算分子生物學和生物化學中的基本問題。自從越來越多物種的基因序列被定序之後,快速而正確的重建演化樹也益發重要。過去有許多研究指出利用Maximum Likelihood (最大概率)條件所重建出的演化樹正確性會比其他方法來的高。但受限於計算複雜度,所以我們結合啟發式搜尋法來降低搜尋空間,採用登山搜尋法的概念,從初始的樹型開始不斷改變它topology以改進該樹的maximum likelihood。並且採用Tree bisection and reconnection (簡稱TBR)產生廣泛的tree space。再利用minimum evolution的方法來過濾掉不可能的topology以降低搜索的時間。由使用基準序列資料作為評估,當物種資料量小時,所有的方法除了執行時間上的差別外,皆可找到接近最佳ML值的tree。當物種資料量增加時,我們的方法比起其他的方法仍然能找到最正確的tree。因此可以顯示出我們的方法表現比早先已知的方法為佳。

而蛋白質分類問題在生醫資訊中是一個相當熱門的研究議題。我們利用簡單圖形來展示三維蛋白質結構,圖形裡的每一個點用來表示二十種蛋白質的氨基酸。我們利用原子移位參數有效降低圖形裡的點和邊的複雜程度並加快程式執行速度。鎖定特定蛋白質家族中特定之子圖型樣,並應用搜尋頻繁子圖中的策略去找尋測試蛋白質是否亦有相同之子圖型樣,進一步分類屬於特定型樣的蛋白質家族。在實驗的部分,使用實際的蛋白質資料庫作為實驗數據,我們的分類方法在準確度表現上優於早先已知的方法,而且我們的方法是一個簡單、和容易被實施的方法。

Top

Cloud Computing (雲端計算)

雲端運算是一種平行分散式的運算系統,在近幾年來越來越受歡迎。在雲端運算裡,MapReduce是一個很受歡迎的模組,同時MapReduce對於大規模的資料平行應用也是一個重要的程式設計模組。Hadoop則是一個將MapReduce模型實作出來的平台,他是屬於開放原始碼的軟體,並且Hadoop經常被使用於資料密集的應用上,像是資料探勘以及網路索引。Hadoop在運行時會假設在叢集裡所有的機器節點都擁有相同的計算能力,並且每台節點執行工作所需的資料都是在本機上的,不需要進行資料的傳輸。然而,在一些私人的叢集或是計算中心並不會符合同質性,而在這樣的異質環境底下則可能會增加額外的開銷並且降低MapReduce的效能。因此我們設計了一個資料放置的演算法,用來解決節點會有工作量不平衡的問題。我們所提出的方法可以動態的調整以平衡在每台節點上資料的儲存,而調整的方式則是根據在異質環境的Hadoop叢集裡每台節點各自的運算能力來調配,這樣可以減少時間花在資料傳輸上,來達成改善Hadoop的效能。在實驗的結果顯示出,使用我們的演算法 - 動態資料放置策略在異質環境底下可以降低執行時間並且提升Hadoop的效能。

Top

Information Technology Education (資訊教育)

Top