Full Text:   <1977>

CLC number: TP302.7

On-line Access: 2011-07-04

Received: 2010-08-09

Revision Accepted: 2011-03-28

Crosschecked: 2011-05-31

Cited: 2

Clicked: 4116

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2011 Vol.12 No.7 P.561-573

http://doi.org/10.1631/jzus.C1000281


A general communication performance evaluation model based on routing path decomposition


Author(s):  Ai-lian Cheng, Yun Pan, Xiao-lang Yan, Ruo-hong Huan

Affiliation(s):  Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China, Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China, College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China

Corresponding email(s):   chengal@vlsi.zju.edu.cn, panyun@vlsi.zju.edu.cn

Key Words:  Analytical model, Communication performance, Network-on-chip (NoC), Queuing system, Routing path decomposition, Virtual channel


Ai-lian Cheng, Yun Pan, Xiao-lang Yan, Ruo-hong Huan. A general communication performance evaluation model based on routing path decomposition[J]. Journal of Zhejiang University Science C, 2011, 12(7): 561-573.

@article{title="A general communication performance evaluation model based on routing path decomposition",
author="Ai-lian Cheng, Yun Pan, Xiao-lang Yan, Ruo-hong Huan",
journal="Journal of Zhejiang University Science C",
volume="12",
number="7",
pages="561-573",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1000281"
}

%0 Journal Article
%T A general communication performance evaluation model based on routing path decomposition
%A Ai-lian Cheng
%A Yun Pan
%A Xiao-lang Yan
%A Ruo-hong Huan
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 7
%P 561-573
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1000281

TY - JOUR
T1 - A general communication performance evaluation model based on routing path decomposition
A1 - Ai-lian Cheng
A1 - Yun Pan
A1 - Xiao-lang Yan
A1 - Ruo-hong Huan
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 7
SP - 561
EP - 573
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1000281


Abstract: 
The network-on-chip (NoC) architecture is a main factor affecting the system performance of complicated multiprocessor 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 estimate 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 105 times faster than the cycle-accurate NoC simulator. Practical applications of the model including bottleneck detection and virtual channel allocation are also presented.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Arjomand, M., Sarbazi-Azad, H., 2009. A Comprehensive Power-Performance Model for NoCs with Multi-flit Channel Buffers. Proc. 23rd Int. Conf. on Supercomputing, p.470-478.

[2]Bahn, J.H., Bagherzadeh, N., 2008. Design of simulation and analytical models for a 2D-meshed asymmetric adaptive router. IET Comput. Digit. Techn., 2(1):63-73.

[3]Ciciani, B., Colajanni, M., Paolucci, C., 1997. An Accurate Model for the Performance Analysis of Deterministic Wormhole Routing. Proc. 11th Int. Parallel Processing Symp., p.353-359.

[4]Dally, W.J., 1992. Virtual-channel flow control. IEEE Trans. Parall. Distr. Syst., 3(2):194-205.

[5]Draper, J.T., Ghosh, J., 1994. A comprehensive analytical model for wormhole routing in multicomputer systems. J. Parall. Distr. Comput., 23(2):202-214.

[6]Guz, Z., Walter, I., Bolotin, E., Cidon, I., Ginosar, R., Kolodny, A., 2006. Efficient Link Capacity and QoS Design for Network-on-Chip. Proc. Design, Automation and Test in Europe, p.1-6.

[7]Hu, J.C., Ogras, U.Y., Marculescu, R., 2006. System-level buffer allocation for application-specific networks-on-chip router design. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 25(12):2919-2933.

[8]Hu, P.C., Kleinrock, L., 1997. An Analytical Model for Wormhole Routing with Finite Size Input Buffers. Proc. 15th Int. Teletraffic Congress, p.549-560.

[9]Keutzer, K., Newton, A.R., Rabaey, J.M., Sangiovanni-Vincentelli, A., 2000. System-level design: orthogonalization of concerns and platform-based design. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 19(12):1523-1543.

[10]Krimer, E., Erez, M., Keslassy, I., Kolodny, A., Walter, I., 2009. Packet-Level Static Timing Analysis for NoCs. Proc. 3rd ACM/IEEE Int. Symp. on Networks-on-Chip, p.88.

[11]Li, S., Peh, L.S., Jha, N.K., 2003. Dynamic Voltage Scaling with Links for Power Optimization of Interconnection Networks. Proc. 9th Int. Symp. on High-Performance Computer Architecture, p.91-102.

[12]Lu, C.L., 2009. Queuing Theory (2nd Ed.). Beijing University of Posts and Telecommunications Press, Beijing, China, p.32-41 (in Chinese).

[13]Marculescu, R., Bogdan, P., 2009. The chip is the network: toward a science of network-on-chip design. Found. Trends Electron. Des. Automat., 2(4):371-461.

[14]Marculescu, R., Ogras, U.Y., Peh, L.S., Jerger, N.E., Hoskote, Y., 2009. Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 28(1):3-21.

[15]Moadeli, M., Shahrabi, A., Vanderbauwhede, W., 2007a. Analytical Modelling of Communication in the Rectangular Mesh NoC. Int. Conf. on Parallel and Distributed Systems, p.1-8.

[16]Moadeli, M., Shahrabi, A., Vanderbauwhede, W., Ould-Khaoua, M., 2007b. An Analytical Performance Model for the Spidergon NoC. IEEE 21st Int. Conf. on Advanced Information Networking and Applications, p.1014-1021.

[17]Moraveji, R., Moinzadeh, P., Sarbazi-Azad, H., 2008. A General Approach for Analytical Modeling of Irregular NoCs. IEEE Int. Symp. on Parallel and Distributed Processing with Applications, p.327-334.

[18]Moraveji, R., Moinzadeh, P., Sarbazi-Azad, H., 2009. A general mathematical performance model for wormhole-switched irregular networks. Clust. Comput., 12(3):285-297.

[19]Ni, L.M., McKinley, P.K., 1993. A survey of wormhole routing techniques in direct networks. Computer, 26(2):62-76.

[20]Ogras, U.Y., Marculescu, R., 2007. Analytical Router Modeling for Networks-on-Chip Performance Analysis. Proc. Design, Automation and Test in Europe, p.1096-1101.

[21]Ould-Khaoua, M., Sarbazi-Azad, H., 2001. An analytical model of adaptive wormhole routing in hypercubes in the presence of hot spot traffic. IEEE Trans. Parall. Distr. Syst., 12(3):283-292.

[22]Sarbazi-Azad, H., 2003. A mathematical model of deterministic wormhole routing in hypercube multicomputers using virtual channels. Appl. Math. Model., 27(12):943-953.

[23]Sarbazi-Azad, H., Ould-Khaoua, M., Mackenzie, L.M., 2001. An accurate analytical model of adaptive wormhole routing in k-ary n-cubes interconnection networks. Perform. Eval., 43(2-3):165-179.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE