2024-03-28T20:53:00Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000248092023-04-27T10:00:04Z01164:01579:01726:01736
Prolog OR並列処理手法 -階層型挟み打ち探索法-AN OR PARALLEL PROCESSING SCHEME OF PROLOG -HIERARCHICAL PINCERS ATTACK SEARCH-jpnhttp://id.nii.ac.jp/1001/00024809/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=24809&item_no=1&attribute_id=1&file_no=1Copyright (c) 1988 by the Information Processing Society of Japan早稲田大学理工学部電気工学科早稲田大学理工学部電気工学科早稲田大学理工学部電気工学科甲斐, 宗徳小林, 和男笠原, 博徳本稿では階層型狭み打ち探索法を呼ぶPROLOGのOR並列処理手法を提案する。本手法では、PROLOGの処理過程をAND逐次実行の条件下でOR木を用いて表現し、そのOR木を複数のプロセッサが左右から階層的に挟み打ちをする形で並列かつ独立に深さ優先探索を行なう。これによりプロセッサへの負荷割当て単位(グラニュラリティ)を大きくとることができ、負荷の割当て制御(スケジューリング)の頻度を低減させ、スケジューリングによるオーバヘッドおよび実行時のプロセッサ間データ転送のオーバヘッドを低く抑えることが可能となる。また、スケジューリングの効率化のために各プロセッサの探索状況を示す特殊なポインタ(セレクションポインタ)を導入する。これにより、負荷の割当て後、探索に必要な環境を各プロセッサがデータ転送を行なわずに自己生成でき、スケジューリング時のデータ転送オーバヘッドをさらに軽減することができる。本手法ではOR木の左右から深さ優先探索を行なうため、m台のプロセッサを用いて1台の時の1/m以下の処理時間を得るという加速異常現象を有効に引き出すことができる。本手法の性能及び有効性はソフトウェアシミュレーションにより確かめられる。We proposes an OR parallel processing scheme of Prolog named "Hierarchical Pincers Attack Search". In the scheme, an OR-tree, which represents an execution process of a Prolog program, is searched from right and left by a plurality of processors. Each processor does the depth first search independently. The pincers attack search allows us to get a coarse task granularity. That reduces the frequency of the task assignment or the task scheduling, and also the amount of the data transfers among the processors. Furthermore, the introduction of a special pointer which indicates the status of the processors, minimizes the data transfers caused by the task scheduling. In addition, the depth first searches from the both sides extract the acceleration anormaly efficiently. The effectiveness of the proposed scheme is confirmed by simulations of the parallel processing process.AN10096105情報処理学会研究報告計算機アーキテクチャ(ARC)19884(1987-ARC-069)171988-01-212009-06-30