{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T22:23:43Z","timestamp":1743891823905,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T00:00:00Z","timestamp":1623283200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T00:00:00Z","timestamp":1623283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P020631\/1"],"award-info":[{"award-number":["EP\/P020631\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:italic>Parallel patterns<\/jats:italic> are a high-level programming paradigm that enables non-experts in parallelism to develop structured parallel programs that are maintainable, adaptive, and portable whilst achieving good performance on a variety of parallel systems. However, there still exists a large base of <jats:italic>legacy-parallel code<\/jats:italic> developed using ad-hoc methods and incorporating low-level parallel\/concurrency libraries such as <jats:italic>pthreads<\/jats:italic> without any parallel patterns in the fundamental design. This code would benefit from being restructured and rewritten into pattern-based code. However, the process of rewriting the code is laborious and error-prone, due to typical concurrency and pthreading code being closely intertwined throughout the business logic of the program. In this paper, we present a new software restoration methodology, to transform legacy-parallel programs implemented using <jats:italic>pthreads<\/jats:italic> into structured farm and pipeline patterned equivalents. We demonstrate our restoration technique on a number of benchmarks, allowing the introduction of patterned farm and pipeline parallelism in the resulting code; we record improvements in cyclomatic complexity and speedups on a number of representative benchmarks.<\/jats:p>","DOI":"10.1007\/s10766-021-00716-z","type":"journal-article","created":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T20:02:42Z","timestamp":1623355362000},"page":"886-910","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Restoration of Legacy Parallelism: Transforming Pthreads into Farm and Pipeline Patterns"],"prefix":"10.1007","volume":"49","author":[{"given":"Vladimir","family":"Janjic","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6030-2885","authenticated-orcid":false,"given":"Christopher","family":"Brown","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam D.","family":"Barwell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,10]]},"reference":[{"key":"716_CR1","unstructured":"Aldinucci, M., Danelutto, M.: Stream Parallel Skeleton Optimization. In: PDCS, pp. 955\u2013962 (1999)"},{"key":"716_CR2","doi-asserted-by":"crossref","unstructured":"Aldinucci, M., Danelutto, M., Kilpatrick, P., Torquati, M.: Fastflow: High-level and efficient streaming on multicore, chap.\u00a013, pp. 261\u2013280 (2017). 10.1002\/9781119332015.ch13","DOI":"10.1002\/9781119332015.ch13"},{"issue":"10","key":"716_CR3","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/1562764.1562783","volume":"52","author":"K Asanovic","year":"2009","unstructured":"Asanovic, K., Bod\u00edk, R., Demmel, J., Keaveny, T., Keutzer, K., Kubiatowicz, J., Morgan, N., Patterson, D.A., Sen, K., Wawrzynek, J., Wessel, D., Yelick, K.A.: A view of the parallel computing landscape. Commun. ACM 52(10), 56\u201367 (2009)","journal-title":"Commun. ACM"},{"key":"716_CR4","doi-asserted-by":"crossref","unstructured":"Axelsson, E., Claessen, K., Sheeran, M., Svenningsson, J., Engdal, D., Persson, A.: The design and implementation of feldspar\u2014an embedded language for digital signal processing. In: The 22nd International Symposium on Implementation and Application of Functional Languages, IFL 2010, Lecture Notes in Computer Science, vol. 6647, pp. 121\u2013136. Springer (2010)","DOI":"10.1007\/978-3-642-24276-2_8"},{"issue":"4","key":"716_CR5","first-page":"792","volume":"35","author":"AD Barwell","year":"2016","unstructured":"Barwell, A.D., Brown, C., Hammond, K., Turek, W., Byrski, A.: Using program shaping and algorithmic skeletons to parallelise an evolutionary multi-agent system in Erlang. J. Comput. Inform. 35(4), 792\u2013818 (2016)","journal-title":"J. Comput. Inform."},{"key":"716_CR6","unstructured":"Barwell, A.D., Brown, C., Sarkar, S.: Proof-carrying refactorings: sound refactoring for haskell via dependent types. In: International Conference on Functional Programming (ICFP), pp. 1\u201325. In Submission (2021)"},{"issue":"4","key":"716_CR7","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/s10766-013-0266-5","volume":"42","author":"C Brown","year":"2014","unstructured":"Brown, C., Danelutto, M., Hammond, K., Kilpatrick, P., Elliott, A.: Cost-directed refactoring for parallel Erlang programs. Int. J. Parallel Programm. 42(4), 564\u2013582 (2014)","journal-title":"Int. J. Parallel Programm."},{"issue":"4","key":"716_CR8","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/s10766-020-00667-x","volume":"48","author":"C Brown","year":"2020","unstructured":"Brown, C., Janjic, V., Barwell, A., Garc\u00eda, J.D., MacKenzie, K.: Refactoring GrPPI: generic refactoring for generic parallelism in C++. Int. J. Parallel Programm. 48(4), 603\u2013625 (2020). https:\/\/doi.org\/10.1007\/s10766-020-00667-x","journal-title":"Int. J. Parallel Programm."},{"key":"716_CR9","doi-asserted-by":"crossref","unstructured":"Brown, C., Janjic, V., Hammond, K., Sch\u00f6ner, H., Idrees, K., Glass, C.W.: Agricultural reform: more efficient farming using advanced parallel refactoring tools. In: Euromicro International Conference on Parallel, Distributed and Network-based Processing, PDP, pp. 36\u201343. IEEE Computer Society (2014)","DOI":"10.1109\/PDP.2014.94"},{"key":"716_CR10","doi-asserted-by":"crossref","unstructured":"Brown, C., Janjic, V., Barwell, A, Thomson, J, Lozano, R. C., Cole, M, Franke, B, Garcia-Sanchez, J.D., Astorga, D. D. R., MacKenzie, K.: A hybrid approach to parallel pattern discovery in C++. In: 2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), pp. 187\u2013191 (2020)","DOI":"10.1109\/PDP50117.2020.00035"},{"issue":"1","key":"716_CR11","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/321992.321996","volume":"24","author":"RM Burstall","year":"1977","unstructured":"Burstall, R.M., Darlington, J.: A transformation system for developing recursive programs. J. ACM 24(1), 44\u201367 (1977)","journal-title":"J. ACM"},{"key":"716_CR12","volume-title":"Programming with POSIX Threads","author":"DR Butenhof","year":"1997","unstructured":"Butenhof, D.R.: Programming with POSIX Threads. Addison-Wesley Longman Publishing Co. Inc., USA (1997)"},{"key":"716_CR13","unstructured":"Campbell, C., Miller, A.: A parallel programming with microsoft visual C++: design patterns for decomposition and coordination on multicore architectures, 1st edn. Microsoft Press (2011)"},{"issue":"3","key":"716_CR14","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/287000.287001","volume":"7","author":"JE Cook","year":"1998","unstructured":"Cook, J.E., Wolf, A.L.: Discovering models of software processes from event-based data. ACM Trans. Softw. Eng. Methodol. 7(3), 215\u2013249 (1998)","journal-title":"ACM Trans. Softw. Eng. Methodol."},{"key":"716_CR15","doi-asserted-by":"crossref","unstructured":"Corbett, J.C., Dwyer, M.B., Hatcliff, J., Laubach, S., Pasareanu, C.S., Robby, Zheng, H.: Bandera: extracting finite-state models from java source code. In: Proceedings of the 22nd International Conference on Software Engineering ICSE, pp. 439\u2013448. ACM (2000)","DOI":"10.1145\/337180.337234"},{"issue":"1","key":"716_CR16","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/99.660313","volume":"5","author":"L Dagum","year":"1998","unstructured":"Dagum, L., Menon, R.: Openmp: an industry-standard API for shared-memory programming. IEEE J. Comput. Sci. Eng. 5(1), 46\u201355 (1998)","journal-title":"IEEE J. Comput. Sci. Eng."},{"key":"716_CR17","doi-asserted-by":"publisher","DOI":"10.1145\/3132710","author":"D De Sensi","year":"2017","unstructured":"De Sensi, D., De Matteis, T., Torquati, M., Mencagli, G., Danelutto, M.: Bringing parallel patterns out of the corner: the P3ARSEC benchmark suite. ACM Trans. Architect. Code Optim. (2017). https:\/\/doi.org\/10.1145\/3132710","journal-title":"ACM Trans. Architect. Code Optim."},{"issue":"24","key":"716_CR18","doi-asserted-by":"publisher","first-page":"e4175","DOI":"10.1002\/cpe.4175","volume":"29","author":"D DelRio Astorga","year":"2017","unstructured":"del Rio Astorga, D., Dolz, M.F., Fern\u00e1ndez, J., Garc\u00eda, J.D.: A generic parallel pattern interface for stream and data processing. Concurr. Comput. Practice Exp. 29(24), e4175 (2017). https:\/\/doi.org\/10.1002\/cpe.4175","journal-title":"Concurr. Comput. Practice Exp."},{"issue":"6","key":"716_CR19","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1177\/1094342017695639","volume":"32","author":"D del Rio Astorga","year":"2018","unstructured":"del Rio Astorga, D., Dolz, M.F., S\u00e1nchez, L.M., Garc\u00eda, J.D., Danelutto, M., Torquati, M.: Finding parallel patterns through static analysis in C++ applications. Int. J. High-Performance Comput. (IJHPCA) 32(6), 779\u201388 (2018)","journal-title":"Int. J. High-Performance Comput. (IJHPCA)"},{"issue":"1","key":"716_CR20","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1109\/MS.2011.1","volume":"28","author":"D Dig","year":"2011","unstructured":"Dig, D.: A refactoring approach to parallelism. IEEE Softw. 28(1), 17\u201322 (2011)","journal-title":"IEEE Softw."},{"key":"716_CR21","series-title":"Addison Wesley Object Technology Series","volume-title":"Refactoring\u2014improving the design of existing code","author":"M Fowler","year":"1999","unstructured":"Fowler, M.: Refactoring\u2014improving the design of existing code. Addison Wesley Object Technology Series. Addison-Wesley, Boston (1999)"},{"issue":"12","key":"716_CR22","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1002\/spe.1026","volume":"40","author":"H Gonz\u00e1lez-V\u00e9lez","year":"2010","unstructured":"Gonz\u00e1lez-V\u00e9lez, H., Leyton, M.: A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers. Softw. Pract. Exp. 40(12), 1135\u20131160 (2010)","journal-title":"Softw. Pract. Exp."},{"key":"716_CR23","doi-asserted-by":"crossref","unstructured":"Gorlatch, S.: Domain-specific optimizations of composed parallel components. In: Domain-specific program generation, Lecture Notes in Computer Science, vol. 3016, pp. 274\u2013290. Springer (2003)","DOI":"10.1007\/978-3-540-25935-0_16"},{"key":"716_CR24","unstructured":"Gorlatch, S., Wedler, C., Lengauer, C.: Optimization rules for programming with collective operations. In: Proceedings of the 13th International Parallel Processing Symposium on Parallel and Distributed Computing IPPS\/SPDP, pp. 492\u2013499. IEEE Computer Society (1999)"},{"issue":"1","key":"716_CR25","doi-asserted-by":"publisher","first-page":"1740005:1","DOI":"10.1142\/S0129626417400059","volume":"27","author":"D Griebler","year":"2017","unstructured":"Griebler, D., Danelutto, M., Torquati, M., Fernandes, L.G.: Spar: A DSL for high-level and productive stream parallelism. Parallel Processing Letters 27(1), 1740005:1\u20131740005:20 (2017). https:\/\/doi.org\/10.1142\/S0129626417400059","journal-title":"Parallel Processing Letters"},{"key":"716_CR26","doi-asserted-by":"crossref","unstructured":"Hagedorn, B., Stoltzfus, L., Steuwer, M., Gorlatch, S., Dubach, C.: High performance stencil code generation with lift. In: Proceedings of the International Symposium on Code Generation and Optimization, CGO, pp. 100\u2013112. ACM (2018)","DOI":"10.1145\/3168824"},{"key":"716_CR27","doi-asserted-by":"crossref","unstructured":"Janjic, V., Brown, C., Mackenzie, K., Hammond, K., Danelutto, M., Aldinucci, M., Garc\u00eda, J.D.: RPL: A domain-specific language for designing and implementing parallel C++ applications. In: Proceedings of the 24th International Conference on Parallel, Distributed and Network-based Processing, PDP, pp. 288\u2013295. IEEE Computer Society (2016)","DOI":"10.1109\/PDP.2016.122"},{"key":"716_CR28","first-page":"5","volume-title":"Program Flow Analysis","author":"K Kennedy","year":"1981","unstructured":"Kennedy, K.: A survey of data flow analysis techniques. In: Muchnick, S.S., Jones, N.D. (eds.) Program Flow Analysis, pp. 5\u201354. Prentice-Hall, Englewood Cliffs (1981)"},{"key":"716_CR29","doi-asserted-by":"crossref","unstructured":"Li, H., Thompson, S.J.: Safe concurrency introduction through slicing. In: Proceedings of the Workshop on Partial Evaluation and Program Manipulation, PEPM, pp. 103\u2013113. ACM (2015)","DOI":"10.1145\/2678015.2682533"},{"key":"716_CR30","doi-asserted-by":"crossref","unstructured":"Matsuzaki, K., Kakehi, K., Iwasaki, H., Hu, Z., Akashi, Y.: A fusion-embedded skeleton library. In: Euro-Par, Lecture Notes in Computer Science, vol. 3149, pp. 644\u2013653. Springer (2004)","DOI":"10.1007\/978-3-540-27866-5_85"},{"issue":"4","key":"716_CR31","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1109\/TSE.1976.233837","volume":"2","author":"TJ McCabe","year":"1976","unstructured":"McCabe, T.J.: A complexity measure. IEEE Trans. Softw. Eng. 2(4), 308\u2013320 (1976)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"2","key":"716_CR32","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1109\/TSE.2004.1265817","volume":"30","author":"T Mens","year":"2004","unstructured":"Mens, T., Tourw\u00e9, T.: A survey of software refactoring. IEEE Trans. Softw. Eng. 30(2), 126\u2013139 (2004)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"716_CR33","unstructured":"Microsoft: Visual Studio IDE: https:\/\/visualstudio.microsoft.com\/vs\/. (2019)"},{"key":"716_CR34","unstructured":"Reyes, R., Lom\u00fcller, V.: SYCL: Single-source C++ accelerator programming. In: Proceedings of the International Conference on Parallel Computing (PARCO), Advances in Parallel Computing, vol.\u00a027, pp. 673\u2013682. IOS Press (2015)"},{"key":"716_CR35","doi-asserted-by":"crossref","unstructured":"TBB (Intel Threading Building Blocks). In: Encyclopedia of Parallel Computing, p. 2029. Springer (2011)","DOI":"10.1007\/978-0-387-09766-4_2080"},{"key":"716_CR36","unstructured":"The Eclipse Foundation.: Eclipse\u2014an open development platform (2009). http:\/\/www.eclipse.org"},{"key":"716_CR37","unstructured":"Yu, Y., Wang, Y., Mylopoulos, J., Liaskos, S., Lapouchnian, A., do\u00a0Prado\u00a0Leite, J.C.S.: Reverse engineering goal models from legacy code. In: 13th IEEE International Conference on Requirements Engineering (RE 2005), 29 August\u20132 September 2005, Paris, France, pp. 363\u2013372. IEEE Computer Society (2005)"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-021-00716-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-021-00716-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-021-00716-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T22:09:34Z","timestamp":1634854174000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-021-00716-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,10]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["716"],"URL":"https:\/\/doi.org\/10.1007\/s10766-021-00716-z","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"type":"print","value":"0885-7458"},{"type":"electronic","value":"1573-7640"}],"subject":[],"published":{"date-parts":[[2021,6,10]]},"assertion":[{"value":"20 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}