{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:40:36Z","timestamp":1753886436570,"version":"3.41.2"},"reference-count":25,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T00:00:00Z","timestamp":1328054400000},"content-version":"vor","delay-in-days":31,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Scatter Search is an effective and established population\u2010based metaheuristic that has been used to solve a variety of hard optimization problems. However, the time required to find high\u2010quality solutions can become prohibitive as problem sizes grow. In this paper, we present a hardware implementation of Scatter Search on a <jats:italic>field-programmable gate array (FPGA)<\/jats:italic>. Our objective is to improve the run time of Scatter Search by exploiting the potentially massive performance benefits that are available through the native parallelism in hardware. When implementing Scatter Search we employ two different <jats:italic>high-level languages (HLLs)<\/jats:italic>: Handel\u2010C and Impulse\u2010C. Our empirical results show that by effectively exploiting source\u2010code optimizations, data parallelism, and pipelining, a 28x speed up over software can be achieved.<\/jats:p>","DOI":"10.1155\/2012\/793196","type":"journal-article","created":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T21:01:23Z","timestamp":1328130083000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Empirical Investigation on System and Statement Level Parallelism Strategies for Accelerating Scatter Search Using Handel\u2010C and Impulse\u2010C"],"prefix":"10.1155","volume":"2012","author":[{"given":"M.","family":"Walton","sequence":"first","affiliation":[]},{"given":"O.","family":"Ahmed","sequence":"additional","affiliation":[]},{"given":"G.","family":"Grewal","sequence":"additional","affiliation":[]},{"given":"S.","family":"Areibi","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2012,2]]},"reference":[{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_7_1_2"},{"doi-asserted-by":"publisher","key":"e_1_2_7_2_2","DOI":"10.1007\/BFb0026589"},{"doi-asserted-by":"publisher","key":"e_1_2_7_3_2","DOI":"10.1007\/978-1-4615-0337-8"},{"doi-asserted-by":"publisher","key":"e_1_2_7_4_2","DOI":"10.1016\/S0167\u20108191(03)00043\u20107"},{"key":"e_1_2_7_5_2","first-page":"223","volume-title":"Parallel Metaheuristics: A New Class of Algorithms","author":"Garca-Lpez F.","year":"2005"},{"doi-asserted-by":"publisher","key":"e_1_2_7_6_2","DOI":"10.1016\/j.ejor.2004.08.011"},{"doi-asserted-by":"crossref","unstructured":"VavourasM. PapadimitriouK. andPapaefstathiouI. Implementation of a genetic algorithm on a Virtex-II pro FPGA Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays 2009.","key":"e_1_2_7_7_2","DOI":"10.1145\/1508128.1508206"},{"doi-asserted-by":"publisher","key":"e_1_2_7_8_2","DOI":"10.1016\/j.compeleceng.2007.02.003"},{"doi-asserted-by":"publisher","key":"e_1_2_7_9_2","DOI":"10.1016\/j.micpro.2004.08.012"},{"unstructured":"IEEE VASG: VHDL analysis and standardization group 2008 http:\/\/www.vhdl.org\/vasg\/.","key":"e_1_2_7_10_2"},{"volume-title":"The Verilog Hardware Description Language","year":"2008","author":"Thomas D.","key":"e_1_2_7_11_2"},{"unstructured":"Agility Handel-C reference manual 2009 http:\/\/www.mentor.com\/products\/fpga\/handel\u2010c\/upload\/handelc\u2010reference.pdf.","key":"e_1_2_7_12_2"},{"unstructured":"Impulse Accelerated Technologies Impluse c: Software tools for an accelerated world 2010 http:\/\/www.impulseaccelerated.com\/.","key":"e_1_2_7_13_2"},{"unstructured":"Mentor Graphics Catapult C 2010 http:\/\/www.mentor.com\/products\/esl\/high\u2010levelsynthesis\/catapult\u2010synthesis\/.","key":"e_1_2_7_14_2"},{"doi-asserted-by":"crossref","unstructured":"WaltonM. GrewalG. andDarlingtonG. Parallel FPGA-based implementation of scatter search Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference July 2010 New York NY USA ACM 1075\u20131082 2-s2.0-77955898814 https:\/\/doi.org\/10.1145\/1830483.1830683.","key":"e_1_2_7_15_2","DOI":"10.1145\/1830483.1830683"},{"doi-asserted-by":"crossref","unstructured":"WaltonM. GrewalG. andDarlingtonG. Hardware acceleration of scatter search Proceedings of the International Conference on High Performance Computing and Simulation (HPCS \u203210) July 2010 436\u2013443 2-s2.0-77956962773 https:\/\/doi.org\/10.1109\/HPCS.2010.5547101.","key":"e_1_2_7_16_2","DOI":"10.1109\/HPCS.2010.5547101"},{"doi-asserted-by":"publisher","key":"e_1_2_7_17_2","DOI":"10.1007\/978-3-540-24777-7"},{"volume-title":"Unleash the System On Chip Using FPGAs and Handel C","year":"2010","author":"Kamat R.","key":"e_1_2_7_18_2"},{"volume-title":"Practical FPGA Programming in C","year":"2005","author":"Pellerin D.","key":"e_1_2_7_19_2"},{"unstructured":"Mentor Graphics Handel-C synthesis methodology 2010 http:\/\/www.mentor.com\/products\/fpga\/handel\u2010c\/.","key":"e_1_2_7_20_2"},{"doi-asserted-by":"publisher","key":"e_1_2_7_21_2","DOI":"10.1007\/978-3-662-07418-3"},{"unstructured":"Xilinx ISE 11 2010 http:\/\/www.xilinx.com\/support\/documentation\/dt_ise11\u20101.htm.","key":"e_1_2_7_22_2"},{"doi-asserted-by":"publisher","key":"e_1_2_7_23_2","DOI":"10.1109\/95.296382"},{"doi-asserted-by":"publisher","key":"e_1_2_7_24_2","DOI":"10.1002\/0471739383"},{"volume-title":"Design of Experiments: Statistical Principles of Research Design and Analysis","year":"2000","author":"Kuehl R. O.","key":"e_1_2_7_25_2"}],"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/2012\/793196.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/archive\/2012\/793196.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2012\/793196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T13:34:35Z","timestamp":1718026475000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2012\/793196"}},"subtitle":[],"editor":[{"given":"Gregory","family":"Peterson","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1155\/2012\/793196"],"URL":"https:\/\/doi.org\/10.1155\/2012\/793196","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2011-03-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"793196"}}