Abbas Eslami Kiasari
Axel Jantsch
Skip Abstract Section
Abstract
This article reviews four popular mathematical formalisms—queueing theory, network calculus, schedulability analysis, and dataflow analysis—and how they have been applied to the analysis of on-chip communication performance in Systems-on-Chip. The article discusses the basic concepts and results of each formalism and provides examples of how they have been used in Networks-on-Chip (NoCs) performance analysis. Also, the respective strengths and weaknesses of each technique and its suitability for a specific purpose are investigated. An open research issue is a unified analytical model for a comprehensive performance evaluation of NoCs. To this end, this article reviews the attempts that have been made to bridge these formalisms.
- Abdelzaher, T. F., Sharma, V., and Lu, C. 2004. A utilization bound for aperiodic tasks and priority driven scheduling. IEEE Trans. Comput. 53, 3, 334--350. Google Scholar
Digital Library
- Andersson, B. and Jonsson, J. 2000. Fixed-priority preemptive multiprocessor scheduling: To partition or not to partition. In Proceedings of the 7th International Conference on Real-Time Systems and Applications (RTCSA'00). IEEE Computer Society, 337--346. Google ScholarDigital Library
- Andersson, B., Baruah, S., and Jonsson, J. 2001. Static-priority scheduling on multiprocessors. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01). IEEE Computer Society, 193--202. Google ScholarDigital Library
- Audsley, N. C., Burns, A., Tindell, K., and Wellings, A. 1993. Applying new scheduling theory to static priority preemptive scheduling. Softw. Eng. J. 8, 5, 284--292.Google ScholarCross Ref
- Altisen, K., Liu, Y., and Moy, M. 2010. Performance evaluation of components using a granularity-based interface between real-time calculus and timed automata. In Proceedings of the 8th Workshop on Quantitative Aspects of Programming Languages (QAPL'10). 16--23.Google Scholar
- Baker, T. P. 2003. Multiprocessor EDF and deadline monotonic schedulability analysis. In Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS'03). IEEE Computer Society, 120--129. Google ScholarDigital Library
- Bakhouya, M., Suboh, S., Gaber, J., El-Ghazawi, T. A., and Niar, S. 2011. Performance evaluation and design tradeoffs of on-chip interconnect architectures. Simul. Model. Practice Theory 19, 6, 1496--1505.Google ScholarCross Ref
- Balakrishnan, S. and Ozguner, F. 1998. A priority-driven flow control mechanism for real-time traffic in multiprocessor networks. IEEE Trans. Parallel Distrib. Syst. 9, 7, 664--678. Google ScholarDigital Library
- Bekooij, M. J. G., Moriera, O., Poplavko, P., Mesman, B., Pastrnak, M., and Meerbergen, J. 2004. Predictable embedded multiprocessor system design. In Proceedings of the International Workshop on Software and Compilers for Embedded Systems, Lecture Notes in Computer Science, vol. 3199, Springer, 77--91.Google Scholar
- Bekooij, M. J. G., Hoes, R., Moreira, O., Poplavko, P., Pastrnak, M., Mesman, B., Mol, J. D., Stuijk, S., Gheorghita V., and van Meerbergen J. 2005. Dataflow analysis for real-time embedded multiprocessor system design. In Dynamic and Robust Streaming in and between Connected Consumer-Elecronic Devices, Chapter 15. Kluwer Academic Publishers, Norwell, MA.Google Scholar
- Bertsimas, D. and Mourtzinou, G. 1997. Transient laws of non-stationary queueing systems and their applications. Queu. Syst. 25, 1--4, 115--155. Google ScholarDigital Library
- Bhattacharya, B. and Bhattacharyya, S. S. 2001. Parameterized dataflow modeling for DSP systems. IEEE Trans. Signal Process. 49, 10, 2408--2421. Google ScholarDigital Library
- Bilsen, G., Engels, M., Lauwereins, R., and Peperstraete, J. 1996. Cyclo-static dataflow. IEEE Trans. Signal Process. 44, 2, 397--408. Google ScholarDigital Library
- Bini, E., Buttazzo, G. C., and Buttazzo, G. M. 2003. Rate monotonic scheduling: The hyperbolic bound. IEEE Trans. Comp. 52, 7, 933--942. Google ScholarDigital Library
- Bini, E. and Buttazzo, G. C. 2004. Schedulability analysis of periodic fixed priority systems. IEEE Trans. Comput. 53, 11, 1462--1473. Google ScholarDigital Library
- Bogdan, P. and Marculescu, R. 2007. Quantum-like effects in network-on-chip buffers behavior. In Proceedings of the 44th Annual Design Automation Conference (DAC'07). ACM Press, 266--267. Google ScholarDigital Library
- Bogdan, P. and Marculescu, R. 2009. Statistical physics approaches for network-on-chip traffic characterization. In Proceedings of the 7th IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'09). ACM Press, 461--470. Google ScholarDigital Library
- Bogdan, P. and Marculescu, R. 2010. Workload characterization and its impact on multicore platform design. In Proceedings of the 8th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'10). ACM Press, 231--240. Google ScholarDigital Library
- Bogdan, P. and Marculescu, R. 2011. Non-stationary traffic analysis and its implications on multicore platform design. IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 30, 4, 508--519. Google ScholarDigital Library
- Bolch, G., Greiner, S., de Meer, H., and Trivedi, K. S. 2006. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. 2nd Ed. John Wiley & Sons, Hoboken, NJ. Google ScholarDigital Library
- Buck, J. T. 1993. Scheduling dynamic dataflow graphs with bounded memory using the token flow model. Ph.D. dissertation, Dept. of EECS, UC Berkeley, Berkeley, CA. Google ScholarDigital Library
- Buck, J. T. and Lee, E. A. 1993. Scheduling dynamic dataflow graphs with bounded memory using the token flow model. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing: Plenary, Special, Audio, Underwater Acoustics, VLSI, Neural Networks (ICASSP'93), vol. I. IEEE Computer Society, 429--432. Google ScholarDigital Library
- Buck, J. T. 1994. A dynamic dataflow model suitable for efficient mixed hardware and software implementations of DSP applications. In Proceedings of the 3rd International Workshop on Hardware/Software Co-design (CODES'94). IEEE Computer Society, 165--172. Google ScholarDigital Library
- Buttazzo, G. C. 2005. Rate monotonic vs. EDF: Judgement day. Real Time Syst. 29, 1, 5--26. Google ScholarDigital Library
- Chakraborty, S., Kunzli, S., and Thiele, L. 2003. A general framework for analysing system properties in platform-based embedded system designs. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'03). IEEE Computer Society, 10190--10195. Google ScholarDigital Library
- Chang, C.-S. 2000. Performance Guarantees in Communication Networks. Springer-Verlag, London, U.K. Google ScholarDigital Library
- Cheng, A.-L., Pan, Y., Yan, X.-L., and Huan, R.-H. 2011. A general communication performance evaluation model based on routing path decomposition. J. Zhejiang Univ. - Sci. C (Comput. & Electron.) 12, 7, 561--573.Google ScholarCross Ref
- Cruz, R. L. 1991a. A calculus for network delay, part I: Network elements in isolation. IEEE Trans. Inf. Theory 37, 1, 114--131. Google ScholarDigital Library
- Cruz, R. L. 1991b. A calculus for network delay, part II: Network analysis. IEEE Trans. Inf. Theory 37, 1, 132--141. Google ScholarDigital Library
- Dasdan, A. 2004. Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Trans. Des. Autom. Electron. Syst. 9, 4, 385--418. Google ScholarDigital Library
- Dasdan, A. and Gupta, R. 1998. Faster maximum and minimum mean cycle algorithms for system performance analysis. IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 17, 10, 889--899. Google ScholarDigital Library
- Davis, R. I. and Burns, A. 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43, 4, article 35. Google ScholarDigital Library
- Dennis, J. B. 1980. Data flow supercomputers. Computer 13, 11, 48--56. Google ScholarDigital Library
- Foroutan, S., Thonnart, Y., Hersemeule, R., and Jerraya, A. 2009. Analytical computation of packet latency in a 2D-mesh NoC. In Proceedings of the Joint IEEE North-East Workshop on Circuits and Systems and TAISA Conference. 1--4.Google Scholar
- Foroutan, S., Thonnart, Y., Hersemeule, R., and Jerraya, A. 2010. An analytical method for evaluating network-on-chip performance. In Proceedings of the 13th Conference on Design, Automation and Test in Europe (DATE'10). 1629--1632. Google ScholarDigital Library
- Funk, S., Goossens, J., and Baruah, S. 2001. On-line scheduling on uniform multiprocessors. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01). IEEE Computer Society, 183--192. Google ScholarDigital Library
- Ghamarian, A. H., Geilen, M. C. W., Stuijk, S., Basten, T. Theelen, B. D., Mousavi, M. R., Moonen, A. J. M., and Bekooij, M. J. G. 2006. Throughput analysis of synchronous data flow graphs. In Proceedings of the 6th International Conference on Application of Concurrency to System Design (ACSD'06). IEEE Computer Society, 25--36. Google ScholarDigital Library
- Ghamarian, A. H., Stuijk, S., Basten, T., Geilen, M. C. W., and Theelen, B. D. 2007. Latency minimization for synchronous data flow graphs. In Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools (DSD'07). IEEE Computer Society, 189--196. Google ScholarDigital Library
- Guan, W., Tsai, W., and Blough, D. 1993. An analytical model for wormhole routing in multicomputer interconnection networks. In Proceedings of the International Parallel Processing Symposium. 650--654. Google ScholarDigital Library
- Guz, Z., Walter, I., Bolotin, E., Cidon, I., Ginosar, R., and Kolodny, A. 2007. Network delays and link capacities in application-specific wormhole NoCs. J. VLSI Design, article 90941.Google Scholar
- Hamann, A., Jersak, M., Richter, K., and Ernst, R. 2004. Design space exploration and system optimization with SymTA/S - symbolic timing analysis for systems. In Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04). IEEE Computer Society, 469--478. Google ScholarDigital Library
- Hansson, A., Wiggers, M., Moonen, A., Goossens, K., and Bekooij, M. J. G. 2009. Enabling application-level performance guarantees in network-based systems on chip by applying dataflow analysis. IET Comput. Digital Tech. 3, 5, 398--412.Google ScholarCross Ref
- Hansson, A. and Goossens, K. 2010. On-chip Interconnect with Aelite: Composable and Predictable Systems, Springer.Google Scholar
- Hary, S. L. and Ozguner, F. 1997. Feasibility test for real-time communication using wormhole routing. IEE Proc. Comput. Digital Tech. 144, 5, 273--278.Google ScholarCross Ref
- Horstmannshoff, J., Grotker, T., and Meyr, H. 1997. Mapping multirate dataflow to complex RT level hardware models. In Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'97). 283--292. Google ScholarDigital Library
- Hu, P.-C. and Kleinrock, L. 1997. An analytical model for wormhole routing with finite size input buffers. In Proceedings of the 15th International Teletraffic Congress. 549--560.Google Scholar
- Hu, J., Ogras, U. Y., and Marculescu, R. 2006. System-level buffer allocation for application-specific networks-on-chip router design. IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 25, 12, 2919--2933. Google ScholarDigital Library
- Hur, J. Y., Goossens, K., and Mhamdi, L. 2008. Performance analysis of soft and hard single-hop and multi-hop circuit-switched interconnects for FPGAs. In Proceedings of the IFIP International Conference on Very Large Scale Integration. 224--229.Google Scholar
- Jackson, J. R. 1957. Networks of waiting lines. Oper. Res. 5, 518--521.Google ScholarDigital Library
- Jafari, F., Lu, Z., Jantsch, A., and Yaghmaee, M. H. 2010. Buffer optimization in network-on-chip through flow regulation. IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 29, 12, 1973--1986. Google ScholarDigital Library
- Jantsch, A., and Sander, I. 2005. Models of computation and languages for embedded system design. IEE Proc. Comput. Digital Tech. 152, 2, 114--129.Google ScholarCross Ref
- Jiang, Y. and Liu, Y. 2008. Stochastic Network Calculus, Springer-Verlag, Berlin. Google ScholarDigital Library
- Jiang, Y. 2009. Network calculus and queueing theory: Two sides of one coin. In Proceedings of the 4th International Conference on Performance Evaluation Methodologies and Tools. Article 37. Google ScholarDigital Library
- Joseph, M. and Pandya, P. 1986. Finding response times in a real-time system. Brit. Comput. Soc. Comp. J. 29, 5, 390--395.Google ScholarCross Ref
- Kandlur, D. D., Shin, K. G., and Ferrari, D. 1994. Real-time communication in multihop networks. IEEE Trans. Parallel Distrib. Syst. 5, 10, 1044--1056. Google ScholarDigital Library
- Kiasari, A. E., Sarbazi-Azad, H., and Ould-Khaoua, M. 2008a. An accurate mathematical performance model of adaptive routing in the star graph. Future Gen. Comput. Syst. 24, 6, 461--474. Google ScholarDigital Library
- Kiasari, A. E., Rahmati, D., Sarbazi-Azad, H., and Hessabi, S. 2008b. A Markovian performance model for networks-on-chip. In Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP'08). 157--164. Google ScholarDigital Library
- Kiasari, A. E., Sarbazi-Azad, H., and Hessabi, S. 2008c. Caspian: A tunable performance model for multi-core systems. In Proceedings of the 14th European Conference on Parallel and Distributed Computing (Euro-Par'08), Lecture Notes in Computer Science, vol. 5168, Springer, 100--109. Google ScholarDigital Library
- Kiasari, A. E., Hessabi, S., and Sarbazi-Azad, H. 2008d. PERMAP: A performance-aware mapping for application-specific SoCs. In Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors (ASAP'08). IEEE Computer Society, 73--78. Google ScholarDigital Library
- Kiasari, A. E., Jantsch, A., and Lu, Z. 2010. A framework for designing congestion-aware deterministic routing. In Proceedings of the 3rd International Workshop on Network-on-Chip Architectures (NoCArc'10). ACM Press, 45--50. Google ScholarDigital Library
- Kiasari, A. E., Lu, Z., and Jantsch, A. 2012. An analytical latency model for networks-on-chip. IEEE Trans. Very Large Scale Integ. (VLSI) Syst. Doi: 10.1109/TVLSI.2011.2178620. To appear. Google ScholarDigital Library
- Kim, J. and Das, C. R. 1994. Hypercube communication delay with wormhole routing. IEEE Trans. Comput. 43, 7, 806--814. Google ScholarDigital Library
- Kim, B., Kim, J., Hong, S. J., and Lee, S. 1998. A real-time communication method for wormhole switching networks. In Proceedings of the International Conference on Parallel Processing (ICPP'98). IEEE Computer Society, 527--534. Google ScholarDigital Library
- Kim, J., Park, D., Nicopoulos, C., Vijaykrishnan, N., and Das, C. R. 2005. Design and analysis of an NoC architecture from performance, reliability and energy perspective. In Proceedings of the ACM Symposium on Architecture for Networking and Communications Systems (ANCS'05). ACM Press, 173--182. Google ScholarDigital Library
- Kim, H. and Hou, J. C. 2009. Enabling network calculus-based simulation for TCP congestion control. Comput. Netw. 53, 11--24. Google ScholarDigital Library
- Kleinrock, L. 1975. Queueing Systems, vol. 1., John Wiley, Hoboken, NJ. Google ScholarDigital Library
- Krimer, E., Keslassy, I., Kolodny, A., Walter, I., and Erez, M. 2011. Static timing analysis for modeling QoS in networks-on-chip. J. Parallel Distrib. Comput. 71, 5, 687--699. Google ScholarDigital Library
- Kumar, A., Mesman, B., Theelen, B. D., Corporaal, H., and Ha, Y. 2008. Analyzing composability of applications on MPSoC platforms. J. Syst. Architec. Embed. Syst. Design 54, 3--4, 369--383. Google ScholarDigital Library
- Lauwereins, R., Wauters, P., Ade, M., and Peperstraete, J. A. 1994. Geometric parallelism and cyclo-static data flow in GRAPE-II. In Proceedings of the International Workshop on Rapid System Prototyping. 90--107.Google Scholar
- Le Boudec J.-Y. and Thiran, P. 2001. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Springer-Verlag, Berlin. Google ScholarCross Ref
- Lee, E. A. and Messerschmitt, D. G. 1987a. Synchronous data flow. Proc. IEEE 75, 9, 1235--1245.Google ScholarCross Ref
- Lee, E. A. and Messerschmitt, D. G. 1987b. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. Comput. 36, 1, 24--35. Google ScholarDigital Library
- Lee, E. A. 1991. Consistency in dataflow graphs. IEEE Trans. Parallel Distrib. Syst. 2, 2, 223--235. Google ScholarDigital Library
- Lee, E. A. and Parks, T. M. 1995. Dataflow process networks. Proc. IEEE 83, 5, 773--799.Google ScholarCross Ref
- Lehoczky, J. P., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the IEEE Real-Time Systems Symposium. 166--171.Google Scholar
- Lehoczky, J. P. 1990. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of the IEEE Real Time Systems Symposium. 201--209.Google ScholarCross Ref
- Leung, J. Y. T. and Whitehead, J. 1982. On the complexity of fixed priority scheduling of periodic, real-time tasks. Perf. Eval. 2, 4, 237--250.Google ScholarCross Ref
- Li, J.-P. and Mutka, M. W. 1994. Priority based real-time communication for large scale wormhole networks. In Proceedings of the 8th International Symposium on Parallel Processing. IEEE Computer Society, 433--438. Google ScholarDigital Library
- Li, J.-P. and Mutka, M. W. 1996. Real-time virtual channel flow control. J. Parallel Distrib. Comput. 32, 1, 49--65. Google ScholarDigital Library
- Lindley, D. V. 1952. The theory of queues with a single server. Proc. Cambridge Philoso. Soci. 48, 2, 277--289.Google ScholarCross Ref
- Liu C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61. Google ScholarDigital Library
- Liu, J. W. S. 2000. Real-Time Systems 1st Ed. Prentice Hall, Upper Saddle River, NJ.Google Scholar
- Lu, Z., Jantsch, A., and Sander, I. 2005. Feasibility analysis of messages for on-chip networks using wormhole routing. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'05). ACM Press, 960--964. Google ScholarDigital Library
- Lu, Z., Millberg, M., Jantsch, A., Bruce, A., van der Wolf, P., and Henriksson, T. 2009. Flow regulation for on-chip communication. In Proceedings of the Design, Automation and Test in Europe Conference (DATE'09). 578--581. Google ScholarDigital Library
- Lu, Z. 2011. Cross clock-domain TDM virtual circuits for networks on chips. In Proceedings of the 5th ACM/IEEE International Symposium on Networks-on-Chip (NoCS'11). ACM Press, 209--216. Google ScholarDigital Library
- Manabe, Y. and Aoyagi, S. 1995. A feasibility decision algorithm for rate monotonic scheduling of periodic real-time tasks. In Proceedings of the Real-Time Technology and Applications Symposium (RTAS'95). IEEE Computer Society, 212--218. Google ScholarDigital Library
- Min, G. and Ould-Khaoua, M. 2004. A performance model for wormhole-switched interconnection networks under self-similar traffic. IEEE Trans. Comput. 53, 5, 601--613. Google ScholarDigital Library
- Moreira, O. M. and Bekooij, M. J. G. 2007. Self-timed scheduling analysis for real-time applications. EURASIP J. Adv. Signal Proces. Article Id: 083710.Google Scholar
- Nelson, A., Hansson, A., Corporaal, H., and Goossens, K. 2010. Conservative application-level performance analysis through simulation of MPSoCs. In Proceedings of the 8th IEEE Workshop on Embedded Systems for Real-Time Multimedia. 51--60.Google Scholar
- Odoni, A. and Roth, E. 1983. An empirical investigation of the transient behavior of stationary queueing systems. Oper. Res. 31, 432--455.Google ScholarCross Ref
- Ogras, U. Y., Bogdan, P., and Marculescu, R. 2010. An analytical approach for network-on-chip performance analysis. IEEE Trans. Comp.-Aided Des. Integ. Cir. Syst. 29, 12, 2001--2013. Google ScholarDigital Library
- Oh, D. and Bakker, T. P. 1998. Utilization bounds for n-processor rate monotone scheduling with static processor assignment. Real Time Syst. J. 15, 1, 183-193. Google ScholarDigital Library
- Oh, Y. and Son, S. H. 1995. Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Syst. 9, 3, 207--239. Google ScholarDigital Library
- Pandit, K., Schmitt, J., and Steinmetz, R. 2004. Network calculus meets queueing theory - a simulation based approach to bounded queues. In Proceedings of the IEEE International Workshop on Quality of Service. 114--120.Google Scholar
- Parhi, K. K. 1989. Algorithm transformation techniques for concurrent processors. Proc. IEEE 77, 12, 1879--1895.Google ScholarCross Ref
- Peng, D.-T. and Shin, K. G. 1993. A new performance measure for scheduling independent real-time tasks. J. Parallel Distrib. Comput. 19, 1, 11--26. Google ScholarDigital Library
- Pop, P., Eles, P., and Peng, Z. 2000. Schedulability analysis for systems with data and control dependencies. In Proceedings of the 12th Euromicro Conference on Real-Time Systems (RTS'00). IEEE Computer Society, 201--208. Google ScholarDigital Library
- Qian, Y., Lu, Z., and Dou, W. 2009a. Applying network calculus for performance analysis of self-similar traffic in on-chip networks. In Proceedings of the 7th IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'09). ACM Press, 453--460. Google ScholarDigital Library
- Qian, Y., Lu, Z., and Dou, W. 2009b. Analysis of worst-case delay bounds for best-effort communication in wormhole networks on chip. In Proceedings of the 3rd ACM/IEEE International Symposium on Networks-on-Chip (NOCS'09). IEEE Computer Society, 44--53. Google ScholarDigital Library
- Qian, Y., Lu, Z., and Dou, W. 2009c. Worst case flit and packet delay bounds in wormhole networks on chip. IEICE Trans. Fundamentals Electron. Commun. Comput. Sci. Special Section on VLSI Design and CAD Algorithms E92-A, 12, 3211--3220.Google Scholar
- Qian, Y., Lu, Z., and Dou, W. 2010a. Analysis of worst-case delay bounds for on-chip packet-switching networks. IEEE Trans. Comp.-Aided Des. Integ. Cir. Sys. 29, 5, 802--815. Google ScholarDigital Library
- Qian, Y., Lu, Z., and Dou, W. 2010b. QoS scheduling for NoCs: Strict priority queueing versus weighted round robin. In Proceedings of the 28th International Conference on Computer Design (ICCD'10). 52--59.Google Scholar
- Rumbaugh, J. 1977. A data flow multiprocessor. IEEE Trans. Comput. 26, 2, 138--146. Google ScholarDigital Library
- Sathaye, S. S. and Strosnider, J. K. 1994. A real-time scheduling framework for packet-switched networks. In Proceedings of the IEEE International Conference on Distributed Computing. IEEE Computer Society, 182--191.Google Scholar
- Scherrer, A., Fraboulet, A., and Risset, T. 2009. Long-range dependence and on-chip processor traffic. Microprocess. Microsyst. 33, 1, 72--80. Google ScholarDigital Library
- Schmitt, J. B. and Roedig, U. 2005. Sensor network calculus: A framework for worst case analysis. In Distributed Computing in Sensor Systems, Lecture Notes in Computer Science, vol. 3560, Springer, 141--154. Google ScholarDigital Library
- Schmitt, J. 2003. On average and worst case behaviour in non-preemptive priority queueing. In Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems. 197--204.Google Scholar
- Sha, L., Lehoczky, J. P., and Rajkumar, R. 1986. Solutions for some practical problems in prioritized preemptive scheduling. In Proceedings of the IEEE Real-Time Systems Symposium.181--191.Google Scholar
- She, H., Lu, Z., Jantsch, A., Zhou, D., and Zheng, L. 2009. Analytical evaluation of retransmission schemes in wireless sensor networks. In Proceedings of the 69th IEEE Vehicular Technology Conference (VTC'09).Google Scholar
- Shi, Z. and Burns, A. 2008. Real-time communication analysis for on-chip networks with wormhole switching. In Proceedings of the 2nd ACM/IEEE International Symposium on Networks-on-Chip (NOCS'08). IEEE Computer Society, 161--170. Google ScholarDigital Library
- Shi, Z. and Burns, A. 2009. Real-time communication analysis with a priority share policy in on-chip networks. In Proceedings of the 21st Euromicro Conference on Real-Time Systems (ECRTS). IEEE Computer Society, 3--12. Google ScholarDigital Library
- Shi, Z. and Burns, A. 2010. Schedulability analysis and task mapping for real-time on-chip communication. Real-Time Syst. 46, 3, 360--385. Google ScholarDigital Library
- Sjodin, M. and Hansson, H. 1998. Improved response-time analysis calculations. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS'98). IEEE Computer Society, 399--409. Google ScholarDigital Library
- Song, H., Kwon, B., and Yoon, H. 1997. Throttle and preempt: A new flow control for real-time communications in wormhole networks. In Proceedings of the International Conference on Parallel Processing (ICPP'97). IEEE Computer Society, 198--202. Google ScholarDigital Library
- Soteriou, V., Wang, H., and Peh, L.-S. 2006. A statistical traffic model for on-chip interconnection networks. In Proceedings of the 14th IEEE International Symposium on Modeling, Analysis, and Simulation (MASCOTS'06). IEEE Computer Society, 104--116. Google ScholarDigital Library
- Sriram, S., and Bhattacharyya, S. S. 2009. Embedded Multiprocessors: Scheduling and Synchronization 2nd Ed. CRC Press, Boca Raton, FL. Google ScholarDigital Library
- Stiliadis, D. and Varma, A. 1998. Latency-rate servers: A general model for analysis of traffic scheduling algorithms. IEEE/ACM Trans. Netw. 6, 5, 611--624. Google ScholarDigital Library
- Stuijk, S., Geilen, M. C. W., and Basten, T. 2006. Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. In Proceedings of the 43rd Annual Design Automation Conference (DAC'06). ACM Press, 899--904. Google ScholarDigital Library
- Stuijk, S., Geilen, M. C. W., Theelen, B. D., and Basten, T. 2011. Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications. In Proceedings of the International Conference on Embedded Computer Systems. 404--411.Google Scholar
- Theelen, B. D., Geilen, M. C. W., Basten, T., Voeten, J. P. M., Gheorghita, S. V., and Stuijk, S. 2006. A scenario-aware data flow model for combined long-run average and worst-case performance analysis. In Proceedings of the International Conference on Formal Methods and Models for Co-Design. 185--194.Google Scholar
- van As, H. R. 1986. Transient analysis of Markovian queueing systems and its application to congestion-control modeling. IEEE J. Select. Areas Commun. 4, 6, 891--904. Google ScholarDigital Library
- Varatkar, G. V. and Marculescu, R. 2004. On-chip traffic modeling and synthesis for MPEG-2 video applications. IEEE Trans. Very Large Scale Integr. Syst. 12, 1, 108--119. Google ScholarDigital Library
- Wang, J., Li, Y., and Peng, Q. 2011. A novel analytical model for network-on-chip using semi-Markov process. Adv. Elect. Comput. Eng. 11, 1, 111--118.Google ScholarCross Ref
- Wiggers, M. H., Bekooij, M. J. G., and Smit, G. J. M. 2007a. Modeling run-time arbitration by latency-rate servers in dataflow graphs. In Proceedings of the International Workshop on Software and Compilers for Embedded Systems. 11--22. Google ScholarDigital Library
- Wiggers, M. H., Bekooij, M. J. G., and Smit, G. J. M. 2007b. Efficient computation of buffer capacities for cyclo-static dataflow graphs. In Proceedings of the 44th Annual Design Automation Conference (DAC'07). ACM Press, 658--663. Google ScholarDigital Library
- Wiggers, M. H., Bekooij, M. J. G., and Smit, G. J. M. 2008. Buffer capacity computation for throughput constrained streaming applications with data-dependent inter-task communication. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'08). IEEE Computer Society, 183--194. Google ScholarDigital Library
- Wiggers, M. H., Bekooij, M. J. G., and Smit, G. J. M. 2011. Buffer capacity computation for throughput-constrained modal task graphs. ACM Trans. Embed. Comput. Syst. 10, 2, article 17. Google ScholarDigital Library
- Wu, J., Liu, J.-C., and Zhao, W. 2010. A general framework for parameterized schedulability bound analysis of real-time systems. IEEE Trans. Comput. 59, 6, 776--783. Google ScholarDigital Library
- Xuan, D., Bettati, R., Chen, J., Zhao, W., and Li, C. 2000. Utilization-based admission control for real-time applications. In Proceedings of the International Conference on Parallel Processing (ICPP'00). IEEE Computer Society, 251--262. Google ScholarDigital Library
- Yang, F. and Liu, J. 2010. Transient analysis of general queueing systems via simulation-based transfer function modeling, In Proceedings of the Winter Simulation Conference (WSC). IEEE Computer Society, 1110--1122. Google ScholarDigital Library
- Zhang, H. 1995. Service disciplines for guaranteed performance service in packet-switching networks. Proc. IEEE 83, 10, 1374--1396.Google ScholarCross Ref
Index Terms
- Mathematical formalisms for performance evaluation of networks-on-chip
Recommendations
Mesh-of-tree deterministic routing for network-on-chip architecture
GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSINetwork-on-Chip (NoC) is a new paradigm for designing future SoCs. It supports high degree of reusability, scalability, and parallelism in communication. Here, we present Mesh-of-Tree (MoT) based deterministic routing for NoC architecture. MoT ...
An Analysis of Reducing Communication Delay in Network-on-Chip Interconnect Architecture
This paper presents an Enhanced Clustered Mesh (EnMesh) topology for a Network-on-Chip architecture in order to reduce the communication delay between remote regions by considering the physical positions of remote nodes. EnMesh topology includes short ...
Low-power network-on-chip for high-performance SoC design
An energy-efficient network-on-chip (NoC) is presented for possible application to high-performance system-on-chip (SoC) design. It incorporates heterogeneous intellectual properties (IPs) such as multiple RISCs and SRAMs, a reconfigurable logic array, ...
Comments