Research On An Improved BFT Topology And Routing Algorithm For Network On Chip

To meet the demands of high bandwidth and low latency communication amongmodules on chip, Network on Chip technique grows up. Network on Chip is calledNoC for short. The basic properties of NoC are, it presents a moduler,component-based approach to hardware and software designs, using micro network tocommunicate among modules. NoC provides high bandwidth, low latency andscalability. The main idea of NoC is that the computer network technology is migratedinto the on-chip interconnect. Both NoC and computer network have routers. However,NoC is implemented on single chip, which has many limiting factors such as restrictedarea and power, and complex long link wire will result in lager cpu cycle time.Butterfly Fat-tree (BFT) can balance each factors very well. However, BFT has poornetwork performance in local traffic and its structure of router is complicated. Theaim of this thesis is to reduce the area cost and design a more suitable NoC structure,router and routing algorithm for a great local traffic.This thesis focuses the local traffic influence on NoC performance. To overcomethe shortage of BFT, we propose a novel NoC topology, XBFT, router and routingalgorithm. The proposed topology changes some edges of BFT topology to formXBFT which add some links between the first level routers. When the network size is64, as the theoretical analysis result showed, compared with BFT, the number ofrouter in XBFT topology is reduced14.3%compared with that in BFT topology. Thenumber of physical links in XBFT topology is also reduced10.7%compared with thatin BFT topology. When the network size is256, the number of router in XBFTtopology is reduced20.0%compared with that in BFT topology which the number ofphysical links in XBFT topology is reduced32.1%compared with that in BFTtopology.We conduct experiment using gpNoCsim for a64nodes NoC. In the experiment,the performances of XBFT and BFT topologies are compared for local traffic anduniform traffic patterns. Experimental results show that in the case of local trafficpattern, XBFT and BFT topologies have the same performance when the network haslow injection rate of package. With the increase of injection rate, XBFT has betterperformance compared with BFT topology. In the case of uniform traffic pattern,when the network has low injection rate of package, XBFT and BFT topologies havethe same performance. With the increase of injection rate, XBFT has poor performance compared with BFT. Because the big network diameter in XBFT leads toincrease the average latencies.