雙尤拉路徑,傳遞問題及投射環網路

Abstract

在本篇論文中，要討論三個問題：（一） 在串並聯網路中的雙尤拉路徑 問題，（二） 各個網路結構上的傳遞問題，（三） 投射環網路的各項性 質等三個題目。針對串並聯網路中雙尤拉路徑的問題而言，判斷串並聯網 路中是否存在雙尤拉路徑對 CMOS輸出是個很重要的問題，在 CMOS 輸出 中，如果存在有一雙尤拉路徑，那在輸出面積上是最少的，也就是最佳的 ，我們將發展出一個判斷是否在串並聯網路中具有雙尤拉路徑的演算法， 此演算法祇需線性時間；針對網路結構上的傳遞問題而言，在通訊網路上 ，針對單一主電腦有許多傳輸資料的方法及形式，而傳遞問題就是其中之 一，我們將討論在各個網路結構上的傳遞問題，及其傳遞方法與時間；最 後，我們將介紹一個新網路，稱為「投射環網路」，那是針對環網路上線 容錯而發展出來的新網路，我們將深入介紹其各項性質。 There are three problems, the recognition of double Euler trails in series-parallel networks, transmitting on various network topologies and projective torus networks, which are discussed in the thesis. Recognition of double Euler trails in series-parallel networks is an important problem in CMOS layout. Finding a double Euler trails in a network is essential for optimizing the layout area of a complementary CMOS functional cell. In interconnection networks, there are several different schemes to broadcast a message from the host computer. Transmitting scheme is one of these schemes. We will discuss the transmitting scheme on various network topologies. We also propose a topology for interconnection networks, called projective torus, arising edge fault tolerance concern for tori.