大量平行系統之近似同意問題

Abstract

本文提出了一個適切的方式──近鄰方式──在大量平行系統上 成近似 同意。此方式只需直接相鄰之處理機做資料交換, 而非以往方 所用之全 部對全部廣播, 因而處理機不必為資料定傳送路線, 亦不必嵽穭勾~站之 工作。此外, 此方式具有一些如等方性、自主性等分散式t統非常需要之 特性, 因此非常適合用於達成分散式系統之近似同意。為了實現鄰近方 式, 我們提出了一個簡單但有效之方法──近鄰平〞k──在高維立方體 及環繞網狀體上達成近似同意。依據此一方法之甈□ 我們導出了一組遞 迴關係, 並進而推導出此一方法在不同結構體W之收歛速率。求出之收歛 速率乃是以結構參數所表示, 因而我們可以e易地看出系統之結構如何影 響收歛速率, 而作為系統設計之參考。接著, 我們將近鄰平均法應用至上 述系統之時鐘同步, 並與三個具野N表性之全域性方法比較其效能。結果 顯示近鄰平均法除了具有通信弇s作的優點外, 其效能在實際應用時不僅 可接受, 而且在一些通信情p下其效能優於任何全域性方法。 An appropiate approach--neighborhood approach--is proposed forng an approximate agreement in massively prallel systems. Instead-to-all broadcasting that conventional approaches adopt, pproach requires only direct neighbor communication and e routing and redirection. Besides, the approach inherents ties such as isotropic and autonomy, which are very desirabledistributed systems.ealize neighborhood approach, we present a simple but effective m to achieve an approximate agreement on hypercube and wraparoundystems. A set of recurrence relations are derived for each ing to the behavior of neighboring average algorithm. Convergenceor each topology is then deducted through solving the recurrenceons. The evaluated convergence rate, expressed as a function ofure parameters, shows how it is affected by topology of the ch neighboring average algorithm is applied.neighboring average algorithm is then employed to synchronizeand its performance is compared to three representitive globalthms. The performance comparison shows that, besides the advant-n communication and implementation, neighboring average algori-es outperform any global algorithm in some communication