{"created":"2025-01-19T01:12:15.395490+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00211063","sets":["934:935:10452:10555"]},"path":["10555"],"owner":"44499","recid":"211063","title":["An Extensionally Equivalence-ensured Language for Task Parallel Processing with Backtracking-based Load Balancing"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-05-12"},"_buckets":{"deposit":"eb9e847b-cf81-44eb-850e-dea1bbe2515e"},"_deposit":{"id":"211063","pid":{"type":"depid","value":"211063","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"An Extensionally Equivalence-ensured Language for Task Parallel Processing with Backtracking-based Load Balancing","author_link":["535673","535671","535672","535670"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"An Extensionally Equivalence-ensured Language for Task Parallel Processing with Backtracking-based Load Balancing"},{"subitem_title":"An Extensionally Equivalence-ensured Language for Task Parallel Processing with Backtracking-based Load Balancing","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[通常論文] abstract rewriting theory, backtracking, Church-Rosser modulo equivalence, domain-specific language, extensional equivalence, load balancing, reversible computation, search problem, Tascell, task parallel processing, work stealing","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2021-05-12","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"STAIR Lab, Chiba Institute of Technology"},{"subitem_text_value":"Academic Center for Computing and Media Studies, Kyoto University"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"STAIR Lab, Chiba Institute of Technology","subitem_text_language":"en"},{"subitem_text_value":"Academic Center for Computing and Media Studies, Kyoto University","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/211063/files/IPSJ-TPRO1402004.pdf","label":"IPSJ-TPRO1402004.pdf"},"date":[{"dateType":"Available","dateValue":"2023-05-12"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO1402004.pdf","filesize":[{"value":"1.4 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"0fb7ca2e-2192-4228-847c-b47083fc3195","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2021 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tatsuya, Abe"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tasuku, Hiraishi"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tatsuya, Abe","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tasuku, Hiraishi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464814","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-7802","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Backtracking-based load balancing is a promising method for task parallel processing with work stealing. Tascell is a framework for developing applications with backtracking-based load balancing. Users are responsible for ensuring the consistent behavior of Tascell programs when backtracking is triggered in the Tascell runtimes. Nevertheless, the operational semantics for Tascell programs have not been formally studied. Moreover, no extensional equivalence between Tascell programs is provided. In this paper, we formally specify operational semantics for Tascell programs and define extensional equivalence between Tascell programs using the Church-Rosser modulo equivalence notion in abstract rewriting theory. We propose left invertibility and well-formedness properties for Tascell programs, which ensure extensional equivalence between sequential and concurrent behaviors of Tascell programs. We also propose a domain-specific language based on reversible computation, which allows only symmetric pre/post-processing to update states. Tascell programs written in our language have left invertibility and well-formedness properties by construction. Finally, we confirm that Tascell programs to solve typical search problems such as pentomino puzzles, N-queens, and traveling salesman problems can be written in our language.\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.29(2021) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Backtracking-based load balancing is a promising method for task parallel processing with work stealing. Tascell is a framework for developing applications with backtracking-based load balancing. Users are responsible for ensuring the consistent behavior of Tascell programs when backtracking is triggered in the Tascell runtimes. Nevertheless, the operational semantics for Tascell programs have not been formally studied. Moreover, no extensional equivalence between Tascell programs is provided. In this paper, we formally specify operational semantics for Tascell programs and define extensional equivalence between Tascell programs using the Church-Rosser modulo equivalence notion in abstract rewriting theory. We propose left invertibility and well-formedness properties for Tascell programs, which ensure extensional equivalence between sequential and concurrent behaviors of Tascell programs. We also propose a domain-specific language based on reversible computation, which allows only symmetric pre/post-processing to update states. Tascell programs written in our language have left invertibility and well-formedness properties by construction. Finally, we confirm that Tascell programs to solve typical search problems such as pentomino puzzles, N-queens, and traveling salesman problems can be written in our language.\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.29(2021) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2021-05-12","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicVolumeNumber":"14"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":211063,"updated":"2025-01-19T17:55:26.154404+00:00","links":{}}