Abstract
在多重處理機系統裡面, 一個演算法的執行時間, 不僅要考量計算時間, 通訊時間亦應一併合算! 通訊時間又可分為本地通訊和整體通訊 (Local and Global Communic-ations) 。本論文中模版匹配 (Template Matching)需用到本地通訊。我們用格雷映射 (Gray Code Mapping)來解決本地通訊的問題。並且把處理器間的通訊時間降至最低，從而使得我們所提出的模版匹配演算法達到最佳速度比!當問題的本身若比處理器的數目還大時，我們需對問題做分割，俾使每一個小問題皆可以同時在處理器內執行!本論文中，我們用了切片和方塊分割法 ( Stripping andSquare Partitions)於找尋所有配對間的最短路徑問題。而且還利用了擴散二項樹 (Spanning Binomial Tree) 和多重擴散二項樹(Multiple Spanning Binomial Trees)的廣播通訊技巧來傳遞資料，使得我們的演算法在 d-cube 裡比 Jenq 和 Sahni 所提的演算法快了O(d )倍!為了平衡計算時間和通訊時間, 本論文亦提出“盡可能用最少的處理器”的策略。我們發現一些在圖形裡做路徑抽尋的演算法，當它們在只有n/logn個處理器時也能達到和用 n個處理器相同的效率!通訊時間是多重處理機的一大缺點, 本論文所提的格雷映射對本地通訊改進很多! 同時“盡可能用最少的處理器”亦是相當不錯的策略，它能平衡處理器的負載和處理器間的通訊! 對於為了追求平行性而盲目增加處理器數目的研究者，提供了一條新的研究方法!