甲斐 宗徳

By adopting a search method in the scheduling algorithm taking account of communication overhead, algorithms are proposed that provide better scheduling results than heuristic algorithms in relatively short search time. In the proposed method, search area is limited to the portions that seem to include some better solutions that heuristic solutions.

A heuristic algorithm that saves the investment of redundant processors required for executing programs in parallel and reduces parallel processing time is proposed. Based on the critical path method, the conventional list scheduling algorithms keep the processor utilization low in the cases where the communication overhead is considered. The algorithm gives almost the same schedule length with half number of processors compared with conventional scheduling algorithm. The throughput of the system can be raised by executing other applications on the remaining half number of processors.

The authors describe a Prolog OR-parallel processing scheme. An OR-tree representing an execution process of a Prolog program, is searched from the right and left sides of each subtree in the whole tree by a plurality of processors. Each processor performs the depth-first search independently. The search allows coarse task granularity to be obtained, and reduces the frequency of the task assignment or the data transfers among the processors. Introducing a special pointer (selection pointer) which indicates a position of the processors in the OR-tree minimizes the data transfer caused by each task assignment. The depth-first searches from both sides of subtrees extract the acceleration anomaly efficiently and reduce parallel processing time in some cases. The effectiveness of the scheme is demonstrated on a multiprocessor minisupercomputer Alliant FX/80.

本論文では階層型挟み打ち探索法と呼ぶPROLCのOR並列処理手法を提案する.本手法では PROLOGの処理過程をAND逐次実行の条件下でOR木を用いて表現し そのOR木を複数のプロセッサが左右から階層的に挟み打ちをする形で並列かつ独立に深さ優先探索を行う.これによりプロセッサヘの負荷割当て単位(グラニュラリティ)を大きくとることができ 負荷の割当て制御(スケジューリン力の頻度を低減させ スケジューリングによるオーバヘッドおよび実行時のプロセッサ間データ転送のオー(へッドを低く抑えることが可能となるまた スケジューりングの効率化のために各プロセッサの探索状況を示す特殊なポインタ(セレクションポインタ)を導入する.これにより 負荷の割当て後 探索に必要な環境を各プロセッサがデータ転送を行わずに自己生成でき スケジューリング時のデータ転送オーバヘッドをさらに軽減することができる本手法ではOR木の左右から深さ優先探索を行うため m台のプロセッサを用いて1台の時の1/m以下の処理時間を得るという加速異常現象を有効に引き出すことができる.本手法の性能および有効性はソフトウェアシミュレーションにより確かめられる.

本稿では階層型挟み打ち探索法と呼ぶ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 of 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.

In most cases, the scheduling problem for the multiprocessor system is NP‐ or strong NP‐hard. For this problem, we have already proposed a practical optimization algorithm DF/IHS (Depth First/Implicit Heuristic Search), which combines the list‐scheduling algorithm and the depth‐first search, for the minimum parallel processing time multiprocessors scheduling problem. This paper presents a result of application of DF/IHS to the minimum total weighted flow time problem, which is used in the optimization of memory utilization. The problem of allocating tasks to m processors is considered with or without precedence constraints among the tasks. It was verified that the DF/IHS can be applied to this kind of problem very effectively, where the optimal or highly accurate approximate solution is obtained for the large‐scale problem with several hundreds of tasks. Copyright © 1988 Wiley Periodicals, Inc., A Wiley Company