{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T20:08:00Z","timestamp":1762459680631,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,10,31]],"date-time":"2018-10-31T00:00:00Z","timestamp":1540944000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SIRIUS Centre for Scalable Data Access"},{"name":"Spanish MINECO Project","award":["TIN2015-69175-C4-2-R"],"award-info":[{"award-number":["TIN2015-69175-C4-2-R"]}]},{"name":"CM Project","award":["S2013\/ICE-3006"],"award-info":[{"award-number":["S2013\/ICE-3006"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            This article presents\n            <jats:italic>parallel cost analysis<\/jats:italic>\n            , a static cost analysis targeting to over-approximate the cost of parallel execution in distributed systems. In contrast to the standard notion of\n            <jats:italic>serial cost<\/jats:italic>\n            , parallel cost captures the cost of synchronized tasks executing in parallel by exploiting the true concurrency available in the execution model of distributed processing. True concurrency is challenging for static cost analysis, because the parallelism between tasks needs to be soundly inferred, and the waiting and idle processor times at the different locations need to be accounted for. Parallel cost analysis works in three phases: (1) it performs a\n            <jats:italic>block-level<\/jats:italic>\n            analysis to estimate the serial costs of the blocks between synchronization points in the program; (2) it then constructs a\n            <jats:italic>distributed flow graph<\/jats:italic>\n            (DFG) to capture the parallelism, the waiting, and idle times at the locations of the distributed system; and (3) the parallel cost can finally be obtained as the\n            <jats:italic>path of maximal cost<\/jats:italic>\n            in the DFG. We prove the correctness of the proposed parallel cost analysis, and provide a prototype implementation to perform an experimental evaluation of the accuracy and feasibility of the proposed analysis.\n          <\/jats:p>","DOI":"10.1145\/3274278","type":"journal-article","created":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T14:19:23Z","timestamp":1542723563000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Parallel Cost Analysis"],"prefix":"10.1145","volume":"19","author":[{"given":"Elvira","family":"Albert","sequence":"first","affiliation":[{"name":"Complutense University of Madrid, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jes\u00fas","family":"Correas","sequence":"additional","affiliation":[{"name":"Complutense University of Madrid, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Einar Broch","family":"Johnsen","sequence":"additional","affiliation":[{"name":"University of Oslo, Blindern, Oslo, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ka I.","family":"Pun","sequence":"additional","affiliation":[{"name":"Western Norway University of Applied Sciences and University of Oslo, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5299-0016","authenticated-orcid":false,"given":"Guillermo","family":"Rom\u00e1n-D\u00edez","sequence":"additional","affiliation":[{"name":"Universidad Polit\u00e9cnica de Madrid, Boadilla del Monte, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved on","author":"WCET","year":"2018","unstructured":"WCET tools. 2012. Retrieved on 1 May , 2018 from http:\/\/www.rapitasystems.com\/WCET-Tools. WCET tools. 2012. Retrieved on 1 May, 2018 from http:\/\/www.rapitasystems.com\/WCET-Tools."},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1229428.1229471"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.5555\/7929"},{"key":"e_1_2_1_4_1","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho A. V.","year":"2006","unstructured":"A. V. Aho , M. S. Lam , R. Sethi , and J. D. Ullman . 2006 . Compilers: Principles, Techniques, and Tools ( 2 nd ed.). Addison-Wesley Longman Publishing Co., Inc. , Boston . A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., Boston.","edition":"2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1002\/stvr.1569"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/978-3-642-54862-8_46"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/s10817-010-9174-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1016\/j.tcs.2011.07.009"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/2491411.2494590"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1007\/978-3-662-48288-9_16"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1007\/978-3-319-10936-7_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1007\/978-3-662-46681-0_6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1007\/978-3-642-30793-5_3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/2824255"},{"key":"e_1_2_1_15_1","volume-title":"Programming Erlang: Software for a Concurrent World. Pragmatic Bookshelf.","author":"Armstrong J.","year":"2007","unstructured":"J. Armstrong . 2007 . Programming Erlang: Software for a Concurrent World. Pragmatic Bookshelf. J. Armstrong. 2007. Programming Erlang: Software for a Concurrent World. Pragmatic Bookshelf."},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/800228.806932"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/72551.72552"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/978-3-540-69330-7_11"},{"doi-asserted-by":"crossref","unstructured":"S.\n      Brandauer E.\n      Castegren D.\n      Clarke K.\n      Fernandez-Reyes E. B.\n      Johnsen K. I.\n      Pun S. L.\n      Tapia Tarifa T.\n      Wrigstad and \n      A. M.\n      Yang\n  . \n  2015\n  . Parallel objects for multicores: A glimpse at the parallel language encore. In Formal Methods for Multicore Programming Lecture Notes in Computer Science Vol. \n  9104 Springer 1--56.  S. Brandauer E. Castegren D. Clarke K. Fernandez-Reyes E. B. Johnsen K. I. Pun S. L. Tapia Tarifa T. Wrigstad and A. M. Yang. 2015. Parallel objects for multicores: A glimpse at the parallel language encore. In Formal Methods for Multicore Programming Lecture Notes in Computer Science Vol. 9104 Springer 1--56.","key":"e_1_2_1_19_1","DOI":"10.1007\/978-3-319-18941-3_1"},{"unstructured":"D. Caromel and L. Henrio. 2005. A Theory of Distributed Object. Springer.   D. Caromel and L. Henrio. 2005. A Theory of Distributed Object. Springer.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Object-Based Parallel and Distributed Computation (OBPDC\u201995)","volume":"1107","author":"Caromel D.","unstructured":"D. Caromel and Y. Roudier . 1996. Reactive programming in Eiffel\/\/ . In Proceedings of the Conference on Object-Based Parallel and Distributed Computation (OBPDC\u201995) , J. Briot, J. Geib, and A. Yonezawa (Eds.). Lecture Notes in Computer Science , Vol. 1107 . Springer, 125--147. D. Caromel and Y. Roudier. 1996. Reactive programming in Eiffel\/\/. In Proceedings of the Conference on Object-Based Parallel and Distributed Computation (OBPDC\u201995), J. Briot, J. Geib, and A. Yonezawa (Eds.). Lecture Notes in Computer Science, Vol. 1107. Springer, 125--147."},{"volume-title":"Proceedings of the 4th International Conference on Object Oriented Information Systems (OOIS\u201997)","author":"Cugola G.","unstructured":"G. Cugola and C. Ghezzi . 1997. CJava: Introducing concurrent objects in Java . In Proceedings of the 4th International Conference on Object Oriented Information Systems (OOIS\u201997) , M. E. Orlowska and R. Zicari (Eds.). Springer, 504--514. G. Cugola and C. Ghezzi. 1997. CJava: Introducing concurrent objects in Java. In Proceedings of the 4th International Conference on Object Oriented Information Systems (OOIS\u201997), M. E. Orlowska and R. Zicari (Eds.). Springer, 504--514.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/2815400.2815409"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/3122848"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1109\/ICPP.2015.98"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/2429069.2429086"},{"volume-title":"20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979--1999","author":"Graham S. L.","unstructured":"S. L. Graham , P. B. Kessler , and M. K. McKusick . 1982. gprof: A call graph execution profiler (with retrospective) . In 20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979--1999 , A Selection, K. S. McKinley (Ed.). ACM, 49--57. S. L. Graham, P. B. Kessler, and M. K. McKusick. 1982. gprof: A call graph execution profiler (with retrospective). In 20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979--1999, A Selection, K. S. McKinley (Ed.). ACM, 49--57.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1480881.1480898"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1016\/j.tcs.2008.09.019"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/4472.4478"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/1926385.1926427"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1007\/978-3-662-46669-8_6"},{"key":"e_1_2_1_33_1","volume-title":"Slack: A New Performance Metric for Parallel Programs. Technical report","author":"Hollingsworth J. K.","year":"1994","unstructured":"J. K. Hollingsworth and B. P. Miller . 1994 . Slack: A New Performance Metric for Parallel Programs. Technical report , University of Maryland and University of Wisconsin-Madison , 1994. J. K. Hollingsworth and B. P. Miller. 1994. Slack: A New Performance Metric for Parallel Programs. Technical report, University of Maryland and University of Wisconsin-Madison, 1994."},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1007\/978-3-642-25271-6_8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1007\/s10270-006-0011-2"},{"volume-title":"Proceedings of the Norwegian Informatics Conference (NIK\u201903)","author":"Johnsen E. B.","unstructured":"E. B. Johnsen , O. Owe , and M. Arnestad . 2003. Combining active and reactive behavior in concurrent objects . In Proceedings of the Norwegian Informatics Conference (NIK\u201903) , D. Langmyhr (Ed.). Tapir Academic Publisher, 193--204. E. B. Johnsen, O. Owe, and M. Arnestad. 2003. Combining active and reactive behavior in concurrent objects. In Proceedings of the Norwegian Informatics Conference (NIK\u201903), D. Langmyhr (Ed.). Tapir Academic Publisher, 193--204.","key":"e_1_2_1_36_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1287\/opre.9.3.296"},{"unstructured":"J. K. Lee J. Palsberg and R. Majumdar. 2010. Complexity results for may-happen-in-parallel analysis. Retrieved on 1 May 2018 from web.cs.ucla.edu\/&sim;palsberg\/draft\/lpm10.pdf.  J. K. Lee J. Palsberg and R. Majumdar. 2010. Complexity results for may-happen-in-parallel analysis. Retrieved on 1 May 2018 from web.cs.ucla.edu\/&sim;palsberg\/draft\/lpm10.pdf.","key":"e_1_2_1_38_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/53990.54016"},{"doi-asserted-by":"crossref","unstructured":"M. McCool J. Reinders and A. Robison. 2012. Structured Parallel Programming: Patterns for Efficient Computation. Morgan Kaufmann Publishers Inc.   M. McCool J. Reinders and A. Robison. 2012. Structured Parallel Programming: Patterns for Efficient Computation. Morgan Kaufmann Publishers Inc.","key":"e_1_2_1_40_1","DOI":"10.1016\/B978-0-12-415993-8.00003-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1145\/1044834.1044835"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1109\/71.80132"},{"volume-title":"Proceedings of the 7th International Conference on Distributed Computing Systems. IEEE Computer Society, 482--489","author":"Miller B. P.","unstructured":"B. P. Miller and C. Yang . 1987. IPS: An interactive and automatic performance measurement tool for parallel and distributed programs . In Proceedings of the 7th International Conference on Distributed Computing Systems. IEEE Computer Society, 482--489 . B. P. Miller and C. Yang. 1987. IPS: An interactive and automatic performance measurement tool for parallel and distributed programs. In Proceedings of the 7th International Conference on Distributed Computing Systems. IEEE Computer Society, 482--489.","key":"e_1_2_1_43_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1145\/263699.263703"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/1926385.1926390"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1145\/1133981.1134027"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1145\/1095408.1095421"},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1145\/322261.322273"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1145\/361002.361016"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1145\/996841.996859"},{"unstructured":"D. Wyatt. 2013. Akka Concurrency. Artima.   D. Wyatt. 2013. Akka Concurrency. Artima.","key":"e_1_2_1_51_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_52_1","DOI":"10.1007\/978-3-642-29860-8_25"},{"doi-asserted-by":"publisher","key":"e_1_2_1_53_1","DOI":"10.1145\/3106237.3106254"},{"unstructured":"Y. Yokote and M. Tokoro. 1987. Concurrent programming in concurrentsmalltalk. In Object-Oriented Concurrent Programming A. Yonezawa and M. Tokoro (Eds.). MIT Press 129--158.   Y. Yokote and M. Tokoro. 1987. Concurrent programming in concurrentsmalltalk. In Object-Oriented Concurrent Programming A. Yonezawa and M. Tokoro (Eds.). MIT Press 129--158.","key":"e_1_2_1_54_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_55_1","DOI":"10.1145\/28697.28722"},{"doi-asserted-by":"crossref","unstructured":"F.\n      Zuleger S.\n      Gulwani M.\n      Sinn and \n      H.\n      Veith\n  . \n  2011\n  . Bound analysis of imperative programs with the size-change abstraction. In Proceedings of the 18th International Conference on Static Analysis (SAS\u201911) Lecture Notes in Computer Science Vol. \n  6887 Springer 280--297.   F. Zuleger S. Gulwani M. Sinn and H. Veith. 2011. Bound analysis of imperative programs with the size-change abstraction. In Proceedings of the 18th International Conference on Static Analysis (SAS\u201911) Lecture Notes in Computer Science Vol. 6887 Springer 280--297.","key":"e_1_2_1_56_1","DOI":"10.1007\/978-3-642-23702-7_22"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274278","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274278","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:06Z","timestamp":1750207446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274278"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,31]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3274278"],"URL":"https:\/\/doi.org\/10.1145\/3274278","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2018,10,31]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}