Algorithms for Irregular Data Redistribution Problems

Abstract

不規則資料重新分配問題在平行處理的環 境下是一個基本且重要的問題。此問題之最佳化 排程可視為一種二分平面圖(biplanar graphs)之 新的邊塗色問題(the chromatic max-edge-coloring problem)。此圖論問題已經被 證明其為NP-complete。我們將為此問題提出一 個找出最佳解的演算法及設計一個快速的貪婪 演算法(greedy algorithm)。除此之外， 有些情況 會希望傳輸的步驟(次數)愈少愈好， 所以， 在最 少的傳輸次數下且成本最小的問題我們也會一 併討論。我們並且設計一個簡單有效的貪婪法並 與最佳解作比較。根據我們的實驗顯示此貪婪法 可以有6 成以上的機率找到最佳解及最差的狀況 其成本低於最佳解的1.64 倍。