{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T05:55:03Z","timestamp":1719554103223},"reference-count":47,"publisher":"Wiley","issue":"18","license":[{"start":{"date-parts":[[2016,1,21]],"date-time":"2016-01-21T00:00:00Z","timestamp":1453334400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2016,12,25]]},"abstract":"Summary<\/jats:title>In this paper, the focus is put on multi\u2010core branch\u2010and\u2010bound algorithms for solving large\u2010scale permutation\u2010based optimization problems. We investigate five work stealing (WS) strategies with a new data structure called integer\u2013vector\u2013matrix (IVM). In these strategies, each thread has a private IVM allowing the local management of a set of subproblems enumerated using a factorial system. The WS strategies differ in the way the victim thread is selected and the granularity of stolen work units (intervals of factoradics). To assess the efficiency of the private IVM\u2010based WS approach, the five WS strategies have been extensively experimented on the flowshop scheduling permutation problem and compared with their conventional linked\u2010list\u2010based counterparts. The obtained results demonstrate that the IVM\u2010based WS outperforms the linked\u2010list\u2010based one in terms of CPU time, memory usage and number of performed WS operations. Copyright \u00a9 2016 John Wiley & Sons, Ltd.<\/jats:p>","DOI":"10.1002\/cpe.3771","type":"journal-article","created":{"date-parts":[[2016,1,22]],"date-time":"2016-01-22T13:53:45Z","timestamp":1453470825000},"page":"4463-4484","source":"Crossref","is-referenced-by-count":8,"title":["Work stealing with private integer\u2013vector\u2013matrix data structure for multi\u2010core branch\u2010and\u2010bound algorithms"],"prefix":"10.1002","volume":"28","author":[{"given":"Jan","family":"Gmys","sequence":"first","affiliation":[{"name":"Mathematics and Operational Research Department (MARO) University of Mons Mons Belgium"}]},{"given":"Rudi","family":"Leroy","sequence":"additional","affiliation":[{"name":"INRIA Lille Nord Europe Universit\u00e9 Lille 1, CNRS\/CRIStAL Cit\u00e9 scientifique \u2010 59655 Villeneuve d'Ascq cedex France"}]},{"given":"Mohand","family":"Mezmaz","sequence":"additional","affiliation":[{"name":"Mathematics and Operational Research Department (MARO) University of Mons Mons Belgium"}]},{"given":"Nouredine","family":"Melab","sequence":"additional","affiliation":[{"name":"INRIA Lille Nord Europe Universit\u00e9 Lille 1, CNRS\/CRIStAL Cit\u00e9 scientifique \u2010 59655 Villeneuve d'Ascq cedex France"}]},{"given":"Daniel","family":"Tuyttens","sequence":"additional","affiliation":[{"name":"Mathematics and Operational Research Department (MARO) University of Mons Mons Belgium"}]}],"member":"311","published-online":{"date-parts":[[2016,1,21]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/256\/1\/012018"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00450-009-0083-7"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09707-7_8"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-011-0594-4"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.6.1042"},{"key":"e_1_2_7_7_1","unstructured":"LeroyR MezmazM MelabN TuyttensD.Work stealing strategies for multi\u2010core parallel branch\u2010and\u2010bound algorithm using factorial number system. InProceedings of Programming Models and Applications on Multicores And Manycores PMAM'14.ACM:New York NY USA 2007;111:111\u2013111:119."},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(02)00190-9"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02578930"},{"key":"e_1_2_7_10_1","doi-asserted-by":"crossref","unstructured":"ClimerS ZhangW.Cut\u2010and\u2010solve: an iterative search strategy for combinatorial optimization problems Artificial Intelligence.2006;170(8\u20139):714\u2013738.","DOI":"10.1016\/j.artint.2006.02.005"},{"key":"e_1_2_7_11_1","unstructured":"MelabN.Contributions \u00e0 la r\u00e9solution de probl\u00e8mes d'optimisation combinatoire sur grilles de calcul LIFL USTL 2005. Th\u00e8se HDR."},{"key":"e_1_2_7_12_1","unstructured":"CungVD DowajiS Le CunB MautorT RoucairolC.Parallel and distributed branch\u2010and\u2010bound\/A* algorithms.Technical Report 94\/31 Laboratoire PRISM Universit\u00e9 de Versailles 1994."},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3155"},{"key":"e_1_2_7_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/209937.209958"},{"key":"e_1_2_7_16_1","doi-asserted-by":"crossref","unstructured":"FrigoM LeisersonCE RandallKH.The implementation of the Cilk\u20105 multithreaded language. InProceedings of the ACM Sigplan 1998 Conference on Programming Language Design and Implementation PLDI '98.ACM:New York NY USA 1998;212\u2013223.","DOI":"10.1145\/277650.277725"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011434065"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79561-2_9"},{"key":"e_1_2_7_19_1","volume-title":"Intel threading building blocks","author":"Reinders J","year":"2007"},{"key":"e_1_2_7_20_1","doi-asserted-by":"crossref","unstructured":"LeaD.A java fork\/join framework. InProceedings of the ACM 2000 Conference on Java Grande JAVA '00.ACM:New York NY USA 2000;36\u201343.","DOI":"10.1145\/337449.337465"},{"key":"e_1_2_7_21_1","unstructured":"WeilandM.Chapel fortress and x10: novel languages for HPC. In HPCxTR0706 EPCC The University of Edinburgh 2007."},{"key":"e_1_2_7_22_1","unstructured":"NelsonJ HoltB MyersB BriggsP CezeL KahanS OskinM.Grappa: a latency\u2010tolerant runtime for large\u2010scale irregular applications.Technical reportUW-CSE-14-02-01."},{"key":"e_1_2_7_23_1","doi-asserted-by":"crossref","unstructured":"KaiserH HellerT Adelstein\u2010LelbachB SerioA FeyD.Hpx: A task based programming model in a global address space. InProceedings of the 8th International Conference on Partitioned Global Address Space Programming ModelsACM Eugene OR2014;6.","DOI":"10.1145\/2676870.2676883"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536359"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1897852.1897873"},{"issue":"2","key":"e_1_2_7_26_1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s002240011004","article-title":"Thread scheduling for multiprogrammed multiprocessors","volume":"34","author":"Arora NS","year":"2001","journal-title":"Theory of Computing Systems"},{"key":"e_1_2_7_27_1","doi-asserted-by":"crossref","unstructured":"HendlerD LevY MoirM ShavitN.A dynamic\u2010sized nonblocking work stealing deque 2005.","DOI":"10.1007\/s00446-005-0144-5"},{"key":"e_1_2_7_28_1","doi-asserted-by":"crossref","unstructured":"ChaseD LevY.Dynamic circular work\u2010stealing deque. InProceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures.ACM Las Vegas NV2005;21\u201328.","DOI":"10.1145\/1073970.1073974"},{"key":"e_1_2_7_29_1","doi-asserted-by":"crossref","unstructured":"DinanJ LarkinsDB SadayappanP KrishnamoorthyS NieplochaJ.Scalable work stealing. InProceedings of the Conference on High Performance Computing Networking Storage And Analysis Article no. 53 SC '09.ACM:New York NY USA 2009.","DOI":"10.1145\/1654059.1654113"},{"key":"e_1_2_7_30_1","doi-asserted-by":"crossref","unstructured":"AcarUA ChargueraudA RaineyM.Scheduling parallel programs by work stealing with private deques. InProceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming PPoPP '13.ACM:New York NY USA 2013;219\u2013228.","DOI":"10.1145\/2442516.2442538"},{"key":"e_1_2_7_31_1","doi-asserted-by":"crossref","unstructured":"vanDijkT van\u00a0de PolJC.Lace: non\u2010blocking split deque for work\u2010stealing. InEuro\u2010par 2014: Parallel Processing Workshops.Springer Porto Portugal2014;206\u2013217.","DOI":"10.1007\/978-3-319-14313-2_18"},{"key":"e_1_2_7_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6130-6_7"},{"key":"e_1_2_7_33_1","unstructured":"WimmerM CedermanD Tr\u00e4ffJL TsigasP.Configurable strategies for work\u2010stealing.arXiv preprint arXiv:1305.6474 2013."},{"key":"e_1_2_7_34_1","doi-asserted-by":"crossref","unstructured":"PerarnauS SatoM.Victim selection and distributed work stealing performance: a case study. In2014 IEEE 28th International Parallel and Distributed Processing Symposium IEEE Phoenix AZ2014;659\u2013668.","DOI":"10.1109\/IPDPS.2014.74"},{"key":"e_1_2_7_35_1","volume-title":"Parallel depth first search on the ring architecture","author":"Kumar V","year":"1988"},{"key":"e_1_2_7_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04244-7_20"},{"key":"e_1_2_7_37_1","series-title":"OpenAccess Series in Informatics (OASIcs)","first-page":"3","volume-title":"2014 Imperial College Computing Student Workshop","author":"Belikov E","year":"2014"},{"key":"e_1_2_7_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-014-0309-6"},{"key":"e_1_2_7_39_1","unstructured":"CantorG.Zeitschrift f\u00fcr mathematik und physik 14 1869."},{"key":"e_1_2_7_40_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.378"},{"key":"e_1_2_7_41_1","first-page":"194","article-title":"The art of computer programming, volume 2:seminumerical algorithms","author":"Knuth DE","year":"1997","journal-title":"Reading, Ma"},{"key":"e_1_2_7_42_1","unstructured":"McCaffreyJ.Using permutations in .NET for improved systems security 2003."},{"key":"e_1_2_7_43_1","doi-asserted-by":"crossref","unstructured":"MezmazM MelabN Talbi.EG.A grid\u2010enabled branch and bound algorithm for solving challenging combinatorial optimization problems. InProceedings of 21th IEEE International Parallel and Distributed Processing Symp. (IPDPS):Long Beach California March2007.","DOI":"10.1109\/IPDPS.2007.370217"},{"key":"e_1_2_7_44_1","doi-asserted-by":"crossref","unstructured":"SaraswatVA KambadurP KodaliS GroveD KrishnamoorthyS.Lifeline\u2010based global load balancing. InProceedings of the 16th Symposium on Principles and Pratice of Parallel Programming PPoPP '11.ACM:New York NY USA 2011;201\u2013212.","DOI":"10.1145\/1941553.1941582"},{"key":"e_1_2_7_45_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.2.117"},{"key":"e_1_2_7_46_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.53"},{"key":"e_1_2_7_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800010110"},{"key":"e_1_2_7_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)90182-M"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.3771","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.3771","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.3771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T11:37:34Z","timestamp":1696592254000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.3771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,21]]},"references-count":47,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2016,12,25]]}},"alternative-id":["10.1002\/cpe.3771"],"URL":"https:\/\/doi.org\/10.1002\/cpe.3771","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"value":"1532-0626","type":"print"},{"value":"1532-0634","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,21]]}}}