WEKO3
アイテム
An Extensionally Equivalence-ensured Language for Task Parallel Processing with Backtracking-based Load Balancing
https://ipsj.ixsq.nii.ac.jp/records/211063
https://ipsj.ixsq.nii.ac.jp/records/2110637618128e-7cac-4d86-961d-cd18446b8e37
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO1402004.pdf (1.4 MB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-05-12 | |||||||||
| タイトル | ||||||||||
| タイトル | An Extensionally Equivalence-ensured Language for Task Parallel Processing with Backtracking-based Load Balancing | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | An Extensionally Equivalence-ensured Language for Task Parallel Processing with Backtracking-based Load Balancing | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [通常論文] 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 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者所属 | ||||||||||
| STAIR Lab, Chiba Institute of Technology | ||||||||||
| 著者所属 | ||||||||||
| Academic Center for Computing and Media Studies, Kyoto University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| STAIR Lab, Chiba Institute of Technology | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Academic Center for Computing and Media Studies, Kyoto University | ||||||||||
| 著者名 |
Tatsuya, Abe
× Tatsuya, Abe
× Tasuku, Hiraishi
|
|||||||||
| 著者名(英) |
Tatsuya, Abe
× Tatsuya, Abe
× Tasuku, Hiraishi
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.29(2021) (online) ------------------------------ |
|||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.29(2021) (online) ------------------------------ |
|||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA11464814 | |||||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 14, 号 2, 発行日 2021-05-12 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7802 | |||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
