A general communication performance evaluation model based on routing path decomposition

The network-on-chip (NoC) architecture is a main factor affecting the system performance of complicated multi-processor systems-on-chips (MPSoCs).To evaluate the effects of the NoC architectures on communication efficiency,several kinds of techniques have been developed,including various simulators and analytical models.The simulators are accurate but time consuming,especially in large space explorations of diverse network configurations;in contrast,the analytical models are fast and flexible,providing alternative methods for performance evaluation.In this paper,we propose a general analytical model to esti-mate the communication performance for arbitrary NoCs with wormhole routing and virtual channel flow control.To resolve the inherent dependency of successive links occupied by one packet in wormhole routing,we propose the routing path decomposition approach to generating a series of ordered link categories.Then we use the traditional queuing system to derive the fine-grained transmission latency for each network component.According to our experiments,the proposed analytical model provides a good approximation of the average packet latency to the simulation results,and estimates the network throughput precisely under various NoC configurations and workloads.Also,the analytical model runs about 10 5 times faster than the cycle-accurate NoC simulator.Practical applications of the model including bottleneck detection and virtual channel allocation are also presented.

X-Hamiltonian Surface Broadcast Algorithm

Broadcast is one of the most important approach in distributed memory parallel computers that is used to find a routing approach from one source to all nodes in the mesh. Broadcasting is a data communication task in which corresponds to one-to-all communication. Routing schema is the approach used to determine the road that is used to send a message from a source node to destination nodes. In this paper, we propose an efficient algorithm for broadcasting on an all-port wormhole-routed 3D mesh with arbitrary size. Wormhole routing is a fundamental routing mechanism in modern parallel computers which is characterized with low communication latency. We show how to apply this approach to 3-D meshes. In wormhole, routing large network packets are broken into small pieces called FLITs (flow control digits). The destination address is kept in the first flit which is called the header flit and sets up the routing behavior for all subsequent flits associated with the packet. In this paper, we introduce an efficient algorithm, X-Hamiltonian Surface Broadcast (X-HSB) which uses broadcast communication facility with deadlock-free wormhole routing in general three dimensional networks. In this paper, the behaviors of this algorithm are compared to the previous results using simulation;our paradigm reduces broadcast latency and is simpler. The results presented in this paper indicate the advantage of our proposed algorithm.