第1页共9页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共9页廣播通訊模式的階層概念與碰撞蕭學宏1楊昌彪2shiaush@mail.cju.edu.twcbyang@math.nsysu.edu.tw中文摘要現今最常用的乙太網路(Ethernet)﹐其通訊模式就是一種廣播通訊模式。在此種廣播通訊模式下的演算法﹐如能運用階層觀念(layerconcept)﹐將可減少碰撞﹐有效加快演算速度。本文中﹐我們以廣播通訊模式下﹐搜尋最大值的問題為例子﹐提出未加入此種觀念的演算法﹐並分析其平均時間複雜度為(ln2n)。而有運用此觀念的演算法﹐其平均時間複雜度為(lnn)。因此﹐在廣播通訊模式下的演算法﹐若能運用階層的觀念﹐對於加快演算速度將有所幫助。關鍵詞﹕平行演算法﹑廣播通訊模式﹑階層觀念﹑搜尋最大值﹑碰撞1長榮管理學院圖書館資訊組組長﹐兼資管系講師2中山大學應用數學系副教授﹐兼電子計算機中心資料組組長第2页共9页第1页共9页12345768编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共9页一﹑研究背景與目的在眾多平行計算模式(parallelcomputationmodels)中﹐有多種簡單的模式﹐而廣播通訊模式(broadcastcommunicationmode)﹐就是其中的一種[1-12]。在此模式下﹐全部的機器共享唯一的通道﹐並藉由此一通道﹐進行訊號的連通(如圖1所示)。當有一部機器廣播(Broadcast)訊號時﹐其他的機器可藉此通道接收訊號。當有二部以上的機器同時想要傳送消息時﹐就會發生廣播碰撞(broadcastconflict)﹐此時就有一個機制(resolutionscheme)來解決碰撞﹐使得只有一部機器可以傳播資料。圖1此種模式不僅是較簡單的模式﹐而且是較切合實際。現今最普遍的網路架構﹐以乙太網路(Ethernet)為主﹐其通訊模式就是一種廣播通訊模式。此種模式最大的特徵﹐就是必須解決碰撞問題。如果碰撞是無可避免的﹐那如何減少碰撞次數﹐將是關鍵性的問題。在此種模式下架構演算法﹐所需花費的時間共分三部分。第一部份是解決碰撞所需的時間﹐第二部分是資料傳輸所需的時間﹐最後一部份是進行運算所需的時間。若能減少此三部分時間之總和﹐就能增進此演算法的執行效率。而其最具關鍵性的步驟﹐是減少第一部份的時間﹐換言之﹐就是減少碰撞次數。目前所知大概有二種概念﹐可以減少碰撞次數。第一種是﹐調整廣播機率的大小﹐如此可期待大約有一個資料可廣播成功。第二種是﹐逐一建立邏輯性的階層﹐在建立階層的過程﹐將資料分佈在每一個邏輯性的階層之中﹐達到分散資料﹐以減少參加碰撞的資料個數。不論是第一或第二種概念﹐皆能有效減少碰撞次數。第一種概念是由Martel所提出的[6]﹐雖然﹐此概念應用在尋找最大值的問題上﹐能證出具有O(lnn)的效果﹐但是缺乏更嚴謹的上下界限﹐以供參考比較。第二種概念是由作者之一﹐楊昌彪教授所提出的[10]。在廣播通訊模式下﹐將此概念運用在尋找最大值的問題上﹐我們已證出[12]平均所需的時間槽縫(timeslots)﹐以Tn表示﹐則4*lnn
