广播通讯模式的阶层概念与碰撞

1廣播通訊模式的階層概念與碰撞蕭學宏1楊昌彪[e-mail]@math.nsysu.edu.tw中文摘要現今最常用的乙太網路(Ethernet)﹐其通訊模式就是一種廣播通訊模式。在此種廣播通訊模式下的演算法﹐如能運用階層觀念(layerconcept)﹐將可減少碰撞﹐有效加快演算速度。本文中﹐我們以廣播通訊模式下﹐搜尋最大值的問題為例子﹐提出未加入此種觀念的演算法﹐並分析其平均時間複雜度為(ln2n)。而有運用此觀念的演算法﹐其平均時間複雜度為(lnn)。因此﹐在廣播通訊模式下的演算法﹐若能運用階層的觀念﹐對於加快演算速度將有所幫助。關鍵詞﹕平行演算法﹑廣播通訊模式﹑階層觀念﹑搜尋最大值﹑碰撞1長榮管理學院圖書館資訊組組長﹐兼資管系講師2中山大學應用數學系副教授﹐兼電子計算機中心資料組組長2一﹑研究背景與目的在眾多平行計算模式(parallelcomputationmodels)中﹐有多種簡單的模式﹐而廣播通訊模式(broadcastcommunicationmode)﹐就是其中的一種[1-12]。在此模式下﹐全部的機器共享唯一的通道﹐並藉由此一通道﹐進行訊號的連通(如圖1所示)。當有一部機器廣播(Broadcast)訊號時﹐其他的機器可藉此通道接收訊號。當有二部以上的機器同時想要傳送消息時﹐就會發生廣播碰撞(broadcastconflict)﹐此時就有一個機制(resolutionscheme)來解決碰撞﹐使得只有一部機器可以傳播資料。圖1此種模式不僅是較簡單的模式﹐而且是較切合實際。現今最普遍的網路架構﹐以乙太網路(Ethernet)為主﹐其通訊模式就是一種廣播通訊模式。此種模式最大的特徵﹐就是必須解決碰撞問題。如果碰撞是無可避免的﹐那如何減少碰撞次數﹐將是關鍵性的問題。在此種模式下架構演算法﹐所需花費的時間共分三部分。第一部份是解決碰撞所需的時間﹐第二部分是資料傳輸所需的時間﹐最後一部份是進行運算所需的時間。若能減少此三部分時間之總和﹐就能增進此演算法的執行效率。而其最具關鍵性的步驟﹐是減少第一部份的時間﹐換言之﹐就是減少碰撞次數。目前所知大概有二種概念﹐可以減少碰撞次數。第一種是﹐調整廣播機率的大小﹐如此可期待大約有一個資料可廣播成功。第二種是﹐逐一建立邏輯性的階層﹐在建立階層的過程﹐將資料分佈在每一個邏輯性的階層之中﹐達到分散資料﹐以減少參加碰撞的資料個數。不論是第一或第二種概念﹐皆能有效減少碰撞次數。第一種概念是由Martel所提出的[6]﹐雖然﹐此概念應用在尋找最大值的問題上﹐能證出具有O(lnn)的效果﹐但是缺乏更嚴謹的上下界限﹐以供參考比較。第二種概念是由作者之一﹐楊昌彪教授所提出的[10]。在廣播通訊模式下﹐將此概念運用在尋找最大值的問題上﹐我們已證出[12]平均所需的時間槽縫(timeslots)﹐以Tn表示﹐則4*lnnTn5*lnn。而Grabner和Prodinger[14]﹐則利用艱深的數學﹐精準地證出Tn/lnn2/(3*ln2)=4.746276…。不論是何者﹐皆證明我們運用階層概念的演算法﹐其平均時間複雜度為(lnn)。現在我們不僅試圖將此概念推廣至其他的應用﹐也有興趣探討在尋找最大值的問題上﹐如沒有運用階層概念﹐或其他概念﹐而改以直覺方式進行﹐將會有何結果﹖兩者之間的差距﹐會有多大﹖經我們證明其結果是(ln2n)﹐確實比運用階層概念的演算法﹐差上一個級數。此一結果證實運用階層概念有其效果﹐因此﹐在廣播通訊模式下想要發展有效的演算法﹐階層概念是可考慮的方向。而直覺方式的結果﹐可為其他新的概念﹐提供一個比較的基石。123457683以下我們將先介紹在廣播通訊模式下﹐如何以扔銅板的方式﹐解決碰撞問題﹐並說明其時間複雜度為(lnn)。然後再介紹在廣播通訊模式下﹐如何以直覺方式尋找最大值﹐並分析其時間複雜度為(ln2n)。最後則介紹階層概念﹐如何應用在找尋最大值的問題上。我們已證出[12]其時間複雜度為(lnn)﹐至於詳細的說明及證明﹐在此省略。二﹑扔擲銅板解決廣播碰撞之時間複雜度在廣播通訊模式下﹐通道的狀況僅有三種。第一種是﹐僅有一部機器﹐想要在通道廣播﹐當然資料廣播成功。第二種是﹐有二部以上的機器﹐皆想在通道廣播﹐結果產生碰撞。第三種是﹐沒有機器想要在通道廣播﹐結果通道是安靜無聲。不論是哪一種狀況﹐都會花費一個’時間槽縫’(timeslot)。以下我們將詳細解說以扔擲銅板方式﹐作為為解決碰撞的機制。假設有n個資料均分在n部機器﹐換言之﹐每部機器各自擁有一個資料。每部機器皆想要利用唯一的通道﹐傳送資料。當然會在第一個時間槽縫到達時﹐產生碰撞現象。在下一個時間槽縫未到前﹐每一部機器各自扔一次銅板。銅板有二面﹐其一為’人頭’﹐另一為’數字’。扔出’人頭’的機器﹐在下一個時間槽縫到時﹐參與對通道的廣播﹐將資料傳送到唯一的通道。而扔出’數字’的人﹐則放棄對通道廣播﹐即被淘汰出局。此時﹐通道會出現三種狀況。第一種是安靜無聲﹐代表無任何機器扔得’人頭’﹐剛才那批機器﹐必須再各自扔銅板﹐以決定在下一個時間槽縫到達時﹐是否參與對通道的廣播。第二種是碰撞﹐表示有二部機器以上扔得’人頭’﹐此時只有扔得’人頭’的機器﹐繼續再各自扔銅板﹐以決定再下一個時間槽縫到達時的動作﹐是廣播或是放棄。第三種是廣播成功﹐很明顯地代表僅有一部機器扔得’人頭’﹐可對通道成功地廣播資料。令Dn代表平均花費的時間槽縫次數﹐利用類似我們在[12]所提的證法﹐可得到lnnDn2*lnn。而Prodinger[13]運用艱深的數學﹐準確地證明Dnlog2n+1/2-2(log2n)﹐其中2(x)=121102logkkkkixe;kkik22log,;s是Riemann’s-function;s是-function。此分析結果說明﹐以扔銅板方式﹐解決碰撞﹐平均大約需要花費log2n次的時間槽縫。以上所提lnn與log2n的基底互換﹐會造成以後分析式子的無謂膨脹﹐混淆證明的主線發展﹐又因為log2n=lnn*log2e=lnn*1.442695…﹐兩者之間僅差一個常數值﹐因此﹐我們將用lnn作為以後表達式的主體﹐以簡化我們的證明及說明。這樣的替換﹐不會影響最後的結論。三﹑以直覺方式尋找最大值4在廣播通訊模式下尋找最大值的問題﹐就如同在乙太網路(Ethernet)上﹐有n部機器各自擁有一個資料﹐要從中得知那部機器擁有最大值。若n=8﹐則如圖1所示。基本上﹐以直覺方式進行尋找最大值的方法[5]﹐就是利用在解決碰撞﹐而最後有機器廣播資料成功時﹐將小於此資料的機器淘汰出局﹐而其他的機器則再進行下一回合。其進行的方式﹐可視為有n個人在扔擲銅板﹐扔出’人頭’的人﹐他們再繼續扔銅板﹐而扔出’數字’的人則暫時無權再扔銅板﹐如此重複進行﹐一直到最後只有一人扔出人頭。此人將其手中的資料公佈後﹐所有小於此資料的人﹐則淘汰出局﹐而所有大於此資料的人﹐可再進行扔銅板﹐直到最大的資料出現。以圖2為例﹐一開始有8個資料碰撞﹐然後經過一連串的扔銅板(平均大約經過3=log28次的時間槽縫)﹐排除碰撞後﹐假設最後資料3成功地廣播。3廣播後﹐僅剩資料4﹑5﹑6﹑7及8﹐當然還是會發生碰撞﹐此時4﹑5﹑6﹑7及8﹐再度經過一連串的扔銅板﹐以排除碰撞﹐假設資料6成功地廣播。廣播後﹐僅剩資料7及8﹐還是會發生碰撞﹐此時7及8再度經過一連串的扔銅板﹐假設資料8是成功者。廣播後﹐就沒有任何資料可以出來廣播。此時﹐就可得知8是最大的資料。圖2四﹑以直覺方式尋找最大值的時間複雜度分析Levitan和Foster曾證明此演算法所需的成功廣播次數﹐平均約為lnn次[5]。以下則探討此演算法加入排除碰撞後﹐所需的時間槽縫次數。以直覺方式尋找最大值的問題﹐其平均花費的時間槽縫次數﹐以Tn代表﹐則TnnTTTTnnnln(...)10121。第一式若以n=8為例﹐TTTTTTTTT818012345678ln()﹐其中ln8代表經過一連串的扔銅板。換言之﹐平均經過ln8次扔銅板後﹐1,2,3,…,7,8中會有一個廣播成功﹐且每一個的機會均等。所以﹐18代表T0,T1,…T6,T7﹐每一種狀況均有機會出現。T0表示在最大值8﹐廣播成功的狀況下﹐接下來將沒有任何資料﹐可以7,84,5,6,7,8經過一連串的扔銅板經過一連串的扔銅板經過一連串的扔銅板1,2,3,4,5,6,7,88廣播成功6廣播成功3廣播成功5再進行扔銅板﹐換言之﹐所有資料皆因小於最大值8﹐而被淘汰出局。相反地﹐T7表示在最小值1﹐廣播成功的狀況下﹐任何資料都可以再進行扔銅板。T5表示在第三小的資料3﹐廣播成功的狀況下﹐尚有比它大的5個資料(4,5,6,7,8)﹐有權再進行扔銅板﹐換言之﹐只淘汰了最小及第二小等二個資料(1,2)。n-1代入第一式可得TnnTTTTTTTTTnnnnnnnn101320132111111ln......ln*將上式代入第一式﹐再整理得到TTnnnnnn1111lnlnln將上式由n逐一擴張至3﹐可列出以下各式子TTnnnnTTnnnnTTnnnn112321111211232132lnlnlnlnlnlnlnlnln將以上各列式子累加整理得到TTnnnnnn2211112132lnlnlnlnln將上式整理可得TTnkkTTnkkkkknknnknkn232332112111lnlnlnlnlnlnlnlnTTnkkkkknknkn2332111lnlnlnlnln若要分析Tn﹐則需要分析Tn式子中13kkknln及113kkkknlnln的上下界﹐如此才能知道Tn的全貌。以下我們將先證明它們二者的上下界限﹐然後再綜合討論Tn的上下界限﹐最後導出時間複雜度Tn=(ln2n)。Lemma1.61212311212222322lnlnlnlnlnnkknknProof.利用積分試驗法(IntegralTest)之類似觀念﹐可得1113132xxdxkkxxdxnknnlnlnln運用部分積分法﹐可導出1122xxdxxClnln12112311212222322lnlnlnlnlnnkknkn121231211232222lnlnlnlnnn1212311212222322lnlnlnlnlnnkknkn得證Lemma2.14411111111221111131lnlnlnlnlnnnkkknnknProof.因為lnkk是遞減函數﹐且111kk﹐所以﹐1111111313131kkkkkkkkkknknknlnlnln111143131kkkkkkkkkknknknlnlnln第二式利用積分試驗法(IntegralTest)之類似觀念﹐可得11414xxxdxkkknknlnln及113121kkkxxxdxknnlnln將上式代入第二式得1111413121xxxdxkkkxxxdxnknnlnlnln第三式運用部分積分法﹐可導出111xxxdxxxClnln11441111141xxxdxnnnlnlnln11221111121xxxdxnnn