{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T15:10:11Z","timestamp":1773414611231,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3s","license":[{"start":{"date-parts":[[2014,3,1]],"date-time":"2014-03-01T00:00:00Z","timestamp":1393632000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","award":["SFRH\/BD\/71169\/2010 and SFRH\/BD\/81087\/2011"],"award-info":[{"award-number":["SFRH\/BD\/71169\/2010 and SFRH\/BD\/81087\/2011"]}],"id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"name":"FCT and COMPETE"},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["SFRH\/BD\/71169\/2010 and SFRH\/BD\/81087\/2011"],"award-info":[{"award-number":["SFRH\/BD\/71169\/2010 and SFRH\/BD\/81087\/2011"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Funds through FCT and ERDF (European Regional Development Fund) through COMPETE"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2014,3]]},"abstract":"<jats:p>\n            \u201cMany-core\u201d systems based on a Network-on-Chip (NoC) architecture offer various opportunities in terms of performance and computing capabilities, but at the same time they pose many challenges for the deployment of real-time systems, which must fulfill specific timing requirements at runtime. It is therefore essential to identify, at design time, the parameters that have an impact on the execution time of the tasks deployed on these systems and the upper bounds on the other key parameters. The focus of this work is to determine an upper bound on the\n            <jats:italic>traversal time<\/jats:italic>\n            of a packet when it is transmitted over the NoC infrastructure. Towards this aim, we first identify and explore some limitations in the existing recursive-calculus-based approaches to compute the Worst-Case Traversal Time (WCTT) of a packet. Then, we extend the existing model by integrating the characteristics of the tasks that generate the packets. For this extended model, we propose an algorithm called \u201cBranch and Prune\u201d (BP). Our proposed method provides tighter and safe estimates than the existing recursive-calculus-based approaches. Finally, we introduce a more general approach, namely \u201cBranch, Prune and Collapse\u201d (BPC) which offers a configurable parameter that provides a flexible trade-off between the computational complexity and the tightness of the computed estimate. The recursive-calculus methods and BP present two special cases of BPC when a trade-off parameter is 1 or \u221e, respectively. Through simulations, we analyze this trade-off, reason about the implications of certain choices, and also provide some case studies to observe the impact of task parameters on the WCTT estimates.\n          <\/jats:p>","DOI":"10.1145\/2567937","type":"journal-article","created":{"date-parts":[[2014,3,25]],"date-time":"2014-03-25T13:34:12Z","timestamp":1395754452000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["NoC contention analysis using a branch-and-prune algorithm"],"prefix":"10.1145","volume":"13","author":[{"given":"Dakshina","family":"Dasari","sequence":"first","affiliation":[{"name":"CISTER\/INESC-TEC Research Center, Polytechnic Institute of Porto, Portugal"}]},{"given":"Borislav","family":"Nikoli'c","sequence":"additional","affiliation":[{"name":"CISTER\/INESC-TEC Research Center, Polytechnic Institute of Porto, Portugal"}]},{"given":"Vincent","family":"N'elis","sequence":"additional","affiliation":[{"name":"CISTER\/INESC-TEC Research Center, Polytechnic Institute of Porto, Portugal"}]},{"given":"Stefan M.","family":"Petters","sequence":"additional","affiliation":[{"name":"CISTER\/INESC-TEC Research Center, Polytechnic Institute of Porto, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2014,3,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.976921"},{"key":"e_1_2_1_2_1","unstructured":"J.-Y. L. Boudec. and P. Thiran. 2004. Network Calculus\u2014A Theory of Deterministic Queuing Systems for the Internet. Springer.  J.-Y. L. Boudec. and P. Thiran. 2004. Network Calculus\u2014A Theory of Deterministic Queuing Systems for the Internet. Springer."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.127260"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01660031"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TrustCom.2011.146"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOCS.2010.38"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1132"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES'09)","author":"Ferrandiz T.","unstructured":"T. Ferrandiz , F. Frances , and C. Fraboul . 2009. A method of computation for worst-case delay analysis on spacewire networks . In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES'09) . 19--27. T. Ferrandiz, F. Frances, and C. Fraboul. 2009. A method of computation for worst-case delay analysis on spacewire networks. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES'09). 19--27."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038617.2038627"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2012.35"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2005.99"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119772.1119818"},{"key":"e_1_2_1_13_1","unstructured":"INTEL. 2010. The single-chip-cloud computer. http:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/technology-briefs\/intel-labs-singlechip-cloud-article.pdf.  INTEL. 2010. The single-chip-cloud computer. http:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/technology-briefs\/intel-labs-singlechip-cloud-article.pdf."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 23rd Annual International Computer Software and Applications Conference (COMPSAC'99)","author":"Knauber K.","unstructured":"K. Knauber and B. Chen . 1999. Supporting preemption in wormhole networks . In Proceedings of the 23rd Annual International Computer Software and Applications Conference (COMPSAC'99) . 232--238. K. Knauber and B. Chen. 1999. Supporting preemption in wormhole networks. In Proceedings of the 23rd Annual International Computer Software and Applications Conference (COMPSAC'99). 232--238."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-7315(02)00055-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120767"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2008.18"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe. 741--746","author":"Pellizzoni R.","unstructured":"R. Pellizzoni , A. Schranzhofer , J.-J. Chen , M. Caccamo , and L. Thiele . 2010. Worst case delay analysis for memory interference in multicore systems . In Proceedings of the Conference on Design, Automation and Test in Europe. 741--746 . R. Pellizzoni, A. Schranzhofer, J.-J. Chen, M. Caccamo, and L. Thiele. 2010. Worst case delay analysis for memory interference in multicore systems. In Proceedings of the Conference on Design, Automation and Test in Europe. 741--746."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2043572"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687507"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"E. Salminen A. Kulmala and T. Hamalainen. 2008. Survey of network-on-chip proposals. www.ocpip.org.  E. Salminen A. Kulmala and T. Hamalainen. 2008. Survey of network-on-chip proposals. www.ocpip.org.","DOI":"10.1109\/DSD.2007.4341515"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe. 759--764","author":"Schliecker S.","unstructured":"S. Schliecker , M. Negrean , and R. Ernst . 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems . In Proceedings of the Conference on Design, Automation and Test in Europe. 759--764 . S. Schliecker, M. Negrean, and R. Ernst. 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems. In Proceedings of the Conference on Design, Automation and Test in Europe. 759--764."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2nd ACM\/IEEE International Symposium on Networks-on-Chip. 161--170","author":"Shi Z.","unstructured":"Z. Shi and A. Burns . 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. 161--170 . Z. Shi and A. Burns. 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. 161--170."},{"key":"e_1_2_1_24_1","unstructured":"Tilera. 2011. Tile processor: User architecture manual. www.tilera.com\/scm\/docs\/UG101-User-Architecture-Reference.pdf.  Tilera. 2011. Tile processor: User architecture manual. www.tilera.com\/scm\/docs\/UG101-User-Architecture-Reference.pdf."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2007.89"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2567937","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2567937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:40Z","timestamp":1750232080000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2567937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3]]},"references-count":25,"journal-issue":{"issue":"3s","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1145\/2567937"],"URL":"https:\/\/doi.org\/10.1145\/2567937","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}