{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00219082","sets":["934:1119:10960:10961"]},"path":["10961"],"owner":"44499","recid":"219082","title":["FPGA Acceleration of Swap-Based Tabu Search for Solving Maximum Clique Problems"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-07-28"},"_buckets":{"deposit":"20c52722-2527-49b1-a63b-68017eb1fa65"},"_deposit":{"id":"219082","pid":{"type":"depid","value":"219082","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"FPGA Acceleration of Swap-Based Tabu Search for Solving Maximum Clique Problems","author_link":["571090","571089"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"FPGA Acceleration of Swap-Based Tabu Search for Solving Maximum Clique Problems"},{"subitem_title":"FPGA Acceleration of Swap-Based Tabu Search for Solving Maximum Clique Problems","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"FPGA, maximum clique problems, tabu search","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2022-07-28","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Faculty of Engineering, Information and Systems, University of Tsukuba"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Faculty of Engineering, Information and Systems, University of Tsukuba","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/219082/files/IPSJ-TACS1501003.pdf","label":"IPSJ-TACS1501003.pdf"},"date":[{"dateType":"Available","dateValue":"2024-07-28"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TACS1501003.pdf","filesize":[{"value":"775.1 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"16"},{"tax":["include_tax"],"price":"0","billingrole":"11"},{"tax":["include_tax"],"price":"0","billingrole":"14"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"435f9944-48be-48fe-9dbc-e7bbccbf2bc9","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kenji, Kanazawa"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kenji, Kanazawa","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11833852","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7829","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"The Swap-Based Tabu Search (SBTS) is a heuristic algorithm for solving the maximum independent set problems and can solve the maximum clique problems as well because the maximum clique in a graph is equivalent to the maximum independent set in its complementary graph. Although SBTS is a powerful algorithm in solving the maximum clique problems and has abundant inherent parallelism, it is difficult to parallelize because of its solution searching heuristic involving indirect indexing on array components. In this paper, we show a variant of SBTS that does not require indirect indexing while maintaining the same accuracy as that of the original version of SBTS and describe its hardware acceleration using a Field-Programmable Gate Array (FPGA). Experimental results show that our proposed SBTS variant on FPGA can solve the maximum clique problems up to 51.1 times faster than the original SBTS algorithm on CPU and up to 5.40 times faster than our proposed SBTS variant on CPU, respectively.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"The Swap-Based Tabu Search (SBTS) is a heuristic algorithm for solving the maximum independent set problems and can solve the maximum clique problems as well because the maximum clique in a graph is equivalent to the maximum independent set in its complementary graph. Although SBTS is a powerful algorithm in solving the maximum clique problems and has abundant inherent parallelism, it is difficult to parallelize because of its solution searching heuristic involving indirect indexing on array components. In this paper, we show a variant of SBTS that does not require indirect indexing while maintaining the same accuracy as that of the original version of SBTS and describe its hardware acceleration using a Field-Programmable Gate Array (FPGA). Experimental results show that our proposed SBTS variant on FPGA can solve the maximum clique problems up to 51.1 times faster than the original SBTS algorithm on CPU and up to 5.40 times faster than our proposed SBTS variant on CPU, respectively.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌コンピューティングシステム（ACS）"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2022-07-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicVolumeNumber":"15"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":219082,"updated":"2025-01-19T14:55:55.669144+00:00","links":{},"created":"2025-01-19T01:19:25.018364+00:00"}