{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:06:36Z","timestamp":1760241996974,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,12,3]],"date-time":"2018-12-03T00:00:00Z","timestamp":1543795200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>The paper presents a Non-Uniform Memory Access (NUMA)-aware compiler optimization for task-level parallel code. The optimization is based on Non-Uniform Memory Access\u2014Balanced Task and Loop Parallelism (NUMA-BTLP) algorithm \u015etirb, 2018. The algorithm gets the type of each thread in the source code based on a static analysis of the code. After assigning a type to each thread, NUMA-BTLP \u015etirb, 2018 calls NUMA-BTDM mapping algorithm \u015etirb, 2016 which uses PThreads routine pthread_setaffinity_np to set the CPU affinities of the threads (i.e., thread-to-core associations) based on their type. The algorithms perform an improve thread mapping for NUMA systems by mapping threads that share data on the same core(s), allowing fast access to L1 cache data. The paper proves that PThreads based task-level parallel code which is optimized by NUMA-BTLP \u015etirb, 2018 and NUMA-BTDM \u015etirb, 2016 at compile-time, is running time and energy efficiently on NUMA systems. The results show that the energy is optimized with up to 5% at the same execution time for one of the tested real benchmarks and up to 15% for another benchmark running in infinite loop. The algorithms can be used on real-time control systems such as client\/server based applications which require efficient access to shared resources. Most often, task parallelism is used in the implementation of the server and loop parallelism is used for the client.<\/jats:p>","DOI":"10.3390\/computers7040066","type":"journal-article","created":{"date-parts":[[2018,12,3]],"date-time":"2018-12-03T06:02:09Z","timestamp":1543816929000},"page":"66","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Extending NUMA-BTLP Algorithm with Thread Mapping Based on a Communication Tree"],"prefix":"10.3390","volume":"7","author":[{"given":"Iulia","family":"\u0218tirb","sequence":"first","affiliation":[{"name":"Department of Computers and Software Engineering, Politehnica University of Timi\u0219oara, 300006 Timi\u0219oara, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,12,3]]},"reference":[{"key":"ref_1","unstructured":"(2018, February 25). Introduction to Parallel Computing, Available online: https:\/\/computing.llnl.gov\/tutorials\/parallel_comp\/."},{"key":"ref_2","first-page":"816","article-title":"Towards efficient locality aware parallel data stream processing","volume":"21","author":"Falt","year":"2015","journal-title":"J. Univ. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1145\/3006385","article-title":"Affinity-Based Thread and Data Mapping in Shared Memory Systems","volume":"49","author":"Diener","year":"2017","journal-title":"ACM Comput. Surv."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tam, D., Azimi, R., and Stumm, M. (2007, January 21\u201323). Thread clustering: Sharing-aware scheduling on SMP-CMP-SMT multiprocessors. Proceedings of the ACM SIGOPS Operating Systems Review, Lisbon, Portugal.","DOI":"10.1145\/1272996.1273004"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"\u015etirb, I. (2018, January 10\u201313). NUMA-BTLP: A static algorithm for thread classification. Proceedings of the 2018 5th International Conference on Control, Decision and Information Technologies (CoDIT), Thessaloniki, Greece.","DOI":"10.1109\/CoDIT.2018.8394925"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"\u0218tirb, I. (2016, January 16\u201318). NUMA-BTDM: A thread mapping algorithm for balance data locality on NUMA systems. Proceedings of the 2016 17th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Guangzhou, China.","DOI":"10.1109\/PDCAT.2016.074"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Broquedis, F., Clet-Ortega, J., Moreaud, S., Furmento, N., Goglin, B., Mercier, G., Thibault, S., and Namyst, R. (2010, January 17\u201319). hwloc: A generic framework for managing hardware affinities in HPC applications. Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, Pisa, Italy.","DOI":"10.1109\/PDP.2010.67"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/1105734.1105745","article-title":"Performance implications of single thread migration on a chip multi-core","volume":"33","author":"Constantinou","year":"2005","journal-title":"ACM Sigarch Comput. Archit. News"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1109\/TPDS.2013.104","article-title":"Process placement in multicore clusters: Algorithmic issues and practical techniques","volume":"25","author":"Jeannot","year":"2014","journal-title":"IEEE Trans. Parallel Dist. Syst."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1400097.1400102","article-title":"Towards achieving fairness in the linux scheduler","volume":"42","author":"Wong","year":"2008","journal-title":"ACM Sigops Oper. Syst. Rev."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Li, T., Baumberger, D.P., and Hahn, S. (2009, January 14\u201318). Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin. Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Raleigh, NC, USA.","DOI":"10.1145\/1504176.1504188"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Das, R., Ausavarungnirun, R., Mutlu, O., Kumar, A., and Azimi, M. (2013, January 23\u201327). Application-to-core mapping policies to reduce memory system interference in multi-core systems. Proceedings of the 2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA), Shenzhen, China.","DOI":"10.1109\/HPCA.2013.6522311"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.peva.2015.03.001","article-title":"Characterizing communication and page usage of parallel applications for thread and data mapping","volume":"88","author":"Diener","year":"2015","journal-title":"Perform. Eval."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1145\/2654822.2541971","article-title":"Energy-efficient work-stealing language runtimes","volume":"42","author":"Ribic","year":"2014","journal-title":"ACM SIGARCH Comput. Archit. News"},{"key":"ref_15","unstructured":"Armstrong, R., Hensgen, D., and Kidd, T. (1988, January 30). The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions. Proceedings of the Seventh Heterogeneous Computing Workshop (HCW\u201998), Orlando, FL, USA."},{"key":"ref_16","first-page":"493","article-title":"Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs","volume":"Volume 1067","author":"Liddell","year":"1996","journal-title":"High-Performance Computing and Networking. HPCN-Europe 1996. Lecture Notes in Computer Science"},{"key":"ref_17","unstructured":"Karypis, G., and Kumar, V. (1996, January 15\u201319). Parallel multilevel graph partitioning. Proceedings of the International Conference on Parallel Processing, Honolulu, HI, USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1988","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Devine, K.D., Boman, E.G., Heaphy, R.T., Bisseling, R.H., and Catalyurek, U.V. (2006, January 25\u201329). Parallel hypergraph partitioning for scientific computing. Proceedings of the 20th IEEE International Parallel & Distributed Processing Symposium, Rhodes Island, Greece.","DOI":"10.1109\/IPDPS.2006.1639359"},{"key":"ref_20","first-page":"199","article-title":"Near-optimal placement of MPI processes on hierarchical NUMA architectures","volume":"Volume 6272","author":"Guarracino","year":"2010","journal-title":"Euro-Par 2010\u2014Parallel Processing. Euro-Par 2010. Lecture Notes in Computer Science"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Cruz, E.H., Diener, M., Pilla, L.L., and Navaux, P.O. (2015, January 4\u20136). An efficient algorithm for communication-based task mapping. Proceedings of the 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Turku, Finland.","DOI":"10.1109\/PDP.2015.25"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Traff, J.L. (2002, January 16\u201322). Implementing the MPI process topology mechanism. Proceedings of the 2002 ACM\/IEEE Conference on Supercomputing, Baltimore, MD, USA.","DOI":"10.1109\/SC.2002.10045"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1145\/3040222","article-title":"A library for portable and composable data locality optimizations for NUMA systems","volume":"3","author":"Majo","year":"2017","journal-title":"ACM Trans. Parallel Comput."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Wheeler, K.B., Murphy, R.C., and Thain, D. (2008, January 14\u201318). Qthreads: An API for programming with millions of lightweight threads. Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing, Miami, FL, USA.","DOI":"10.1109\/IPDPS.2008.4536359"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/324133.324234","article-title":"Scheduling multithreaded computations by work stealing","volume":"46","author":"Blumofe","year":"1999","journal-title":"J. ACM"},{"key":"ref_26","first-page":"196","article-title":"Locality and balance for communication-aware thread mapping in multicore systems","volume":"Volume 9233","author":"Hunold","year":"2015","journal-title":"Euro-Par 2015: Parallel Processing. Euro-Par 2015. Lecture Notes in Computer Science"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Xiao, Y., Xue, Y., Nazarian, S., and Bogdan, P. (2017, January 13\u201316). A load balancing inspired optimization framework for exascale multicore systems: A complex networks approach. Proceedings of the 36th International Conference on Computer-Aided Design, Irvine, CA, USA.","DOI":"10.1109\/ICCAD.2017.8203781"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Bogdan, P., Sauerwald, T., Stauffer, A., and Sun, H. (2013, January 6\u20138). Balls into bins via local search. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611973105.2"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Marongiu, A., Burgio, P., and Benini, L. (2010, January 24\u201329). Vertical stealing: Robust, locality-aware do-all workload distribution for 3D MPSoCs. Proceedings of the 2010 International Conference on Compilers, Architectures and Synthesis for Embedded Systems, Scottsdale, AZ, USA.","DOI":"10.1145\/1878921.1878952"}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/7\/4\/66\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:30:41Z","timestamp":1760196641000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/7\/4\/66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,3]]},"references-count":29,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["computers7040066"],"URL":"https:\/\/doi.org\/10.3390\/computers7040066","relation":{},"ISSN":["2073-431X"],"issn-type":[{"type":"electronic","value":"2073-431X"}],"subject":[],"published":{"date-parts":[[2018,12,3]]}}}