JPH04348452A - 制約条件満足化探索の多重プロセッサの実行のためのプロセッサ割当ての方法 - Google Patents
制約条件満足化探索の多重プロセッサの実行のためのプロセッサ割当ての方法Info
- Publication number
- JPH04348452A JPH04348452A JP3021531A JP2153191A JPH04348452A JP H04348452 A JPH04348452 A JP H04348452A JP 3021531 A JP3021531 A JP 3021531A JP 2153191 A JP2153191 A JP 2153191A JP H04348452 A JPH04348452 A JP H04348452A
- Authority
- JP
- Japan
- Prior art keywords
- search
- processors
- subtree
- size
- search tree
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5061—Partitioning or combining of resources
- G06F9/5066—Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N5/00—Computing arrangements using knowledge-based models
- G06N5/01—Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- General Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Computing Systems (AREA)
- Evolutionary Computation (AREA)
- Data Mining & Analysis (AREA)
- Mathematical Physics (AREA)
- Computational Linguistics (AREA)
- Artificial Intelligence (AREA)
- Multi Processors (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】この発明は、多重プロセッサデー
タ処理システム、特に、多重プロセッサシステムにおけ
る各データプロセッサ間で処理タスクを割当てるための
装置および方法に関する。
タ処理システム、特に、多重プロセッサシステムにおけ
る各データプロセッサ間で処理タスクを割当てるための
装置および方法に関する。
【０００２】
【従来技術】人工知能および順列組合せ論的探索適用業
務に関する多くの問題は、制約条件満足化問題として定
式化されている。簡単に言えば、制約条件満足化問題は
、通常、制約条件の任意の集合が満足させられることを
求める。その問題に対するすべての制約条件を同時に満
足させるすべての解決を列挙するために、探索法が用い
られる。
務に関する多くの問題は、制約条件満足化問題として定
式化されている。簡単に言えば、制約条件満足化問題は
、通常、制約条件の任意の集合が満足させられることを
求める。その問題に対するすべての制約条件を同時に満
足させるすべての解決を列挙するために、探索法が用い
られる。
【０００３】この種の問題のために開発された解決技法
に、後戻り探索アルゴリズムがある。その例は、Ｓ．Ｇ
ｏｌｏｍｂらによる“Ｂａｃｋｔｒａｃｋ Ｐｒｏｇ
ｒａｍｍｉｎｇ”（Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ
ＡＣＭ， Ｖｏｌ．１２， １９６５， ｐ
ｐ．５１６−５２４）と題する論文に見られる。
に、後戻り探索アルゴリズムがある。その例は、Ｓ．Ｇ
ｏｌｏｍｂらによる“Ｂａｃｋｔｒａｃｋ Ｐｒｏｇ
ｒａｍｍｉｎｇ”（Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ
ＡＣＭ， Ｖｏｌ．１２， １９６５， ｐ
ｐ．５１６−５２４）と題する論文に見られる。
【０００４】この後戻り探索アルゴリズムのさらに効率
的に修正された例は、以下の論文に見られる。
的に修正された例は、以下の論文に見られる。
【０００５】Ａ．Ｋ． Ｍａｃｋｗｏｒｔｈによる“Ｃ
ｏｎｓｉｓｔｅｎｃｙ ｉｎ Ｎｅｔｗｏｒｋｓ ｏｆ
Ｒｅｌａｔｉｏｎｓ”（Ａｒｔｉｆｉｃｉａｌ Ｉｎ
ｔｅｌｌｉｇｅｎｃｅ， Ｖｏｌ．８，ｐｐ． ９９−
１１８， １９７７）， Ｒ．Ｍ． Ｈａｒａｌｉｃｋ
およびＬ．Ｇ． Ｓｈａｐｉｒｏによる”Ｔｈｅ Ｃｏ
ｎｓｉｓｔｅｎｔ Ｌａｂｅｌｉｎｇ Ｐｒｏｂｌｅｍ
： Ｐａｒｔ Ｉ”（ＩＥＥＥ Ｔｒａｎｓ． ｏｎ
ＰａｔｔｅｒｎＡｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉ
ｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， Ｖｏｌ． １，Ａ
ｐｌ． １９７９， ｐｐ． １７３−１８４）， Ｒ
．Ｍ．Ｈａｒａｌｉｃ およびＧ．Ｌ． Ｅｌｌｉｏｔ
ｔによる“Ｉｍｐｒｏｖｉｎｇ Ｔｒｅｅ Ｓｅａｒｃ
ｈ Ｅｆｆｉｃｉｅｎｃｙ ｆｏｒ Ｃｏｎｓｔｒａｉ
ｎｔ Ｓａｔｉｓｆａｃｔｉｏｎ Ｐｒｏｂｌｅｍｓ
”（Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ
ｐｐ． ２６３−３１３，１９８０）並びにＪ．Ｒ．
Ｂｉｔｎｅｒ およびＥ．Ｍ． Ｒｅｉｎｇｏｌｄに
よる“Ｂａｃｋｔｒａｃｋ Ｐｒｏｇｒａｍｍｉｎ
ｇ Ｔｅｃｈｎｉｑｕｅｓ ”（Ｃｏｍｍ． ｏｆ
ｔｈｅ ＡＣＭ， Ｖｏｌ．１８， ｐｐ． ６５１−
６５６，１９７５）。
ｏｎｓｉｓｔｅｎｃｙ ｉｎ Ｎｅｔｗｏｒｋｓ ｏｆ
Ｒｅｌａｔｉｏｎｓ”（Ａｒｔｉｆｉｃｉａｌ Ｉｎ
ｔｅｌｌｉｇｅｎｃｅ， Ｖｏｌ．８，ｐｐ． ９９−
１１８， １９７７）， Ｒ．Ｍ． Ｈａｒａｌｉｃｋ
およびＬ．Ｇ． Ｓｈａｐｉｒｏによる”Ｔｈｅ Ｃｏ
ｎｓｉｓｔｅｎｔ Ｌａｂｅｌｉｎｇ Ｐｒｏｂｌｅｍ
： Ｐａｒｔ Ｉ”（ＩＥＥＥ Ｔｒａｎｓ． ｏｎ
ＰａｔｔｅｒｎＡｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉ
ｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， Ｖｏｌ． １，Ａ
ｐｌ． １９７９， ｐｐ． １７３−１８４）， Ｒ
．Ｍ．Ｈａｒａｌｉｃ およびＧ．Ｌ． Ｅｌｌｉｏｔ
ｔによる“Ｉｍｐｒｏｖｉｎｇ Ｔｒｅｅ Ｓｅａｒｃ
ｈ Ｅｆｆｉｃｉｅｎｃｙ ｆｏｒ Ｃｏｎｓｔｒａｉ
ｎｔ Ｓａｔｉｓｆａｃｔｉｏｎ Ｐｒｏｂｌｅｍｓ
”（Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ
ｐｐ． ２６３−３１３，１９８０）並びにＪ．Ｒ．
Ｂｉｔｎｅｒ およびＥ．Ｍ． Ｒｅｉｎｇｏｌｄに
よる“Ｂａｃｋｔｒａｃｋ Ｐｒｏｇｒａｍｍｉｎ
ｇ Ｔｅｃｈｎｉｑｕｅｓ ”（Ｃｏｍｍ． ｏｆ
ｔｈｅ ＡＣＭ， Ｖｏｌ．１８， ｐｐ． ６５１−
６５６，１９７５）。
【０００６】
【発明が解決しようとする問題点】従来の多重プロセッ
サ探索アルゴリズムは、通常、探索空間を、多数のプロ
セッサによって並行して探索される部分空間に分割しよ
うとするものである。公知の従来の多重プロセッサ探索
アルゴリズムに固有の欠点の一つは、処理の高速化が線
形からはずれる、つまり、プロセッサの数が増えるにつ
れて飽和する傾向がある点である。この飽和の第１の理
由は、最長実行探索タスクの長さに関係している。タス
ク実行時間の大きな分散は、各プロセッサにかけられる
処理負荷に著しい不均衡を生じ得る。このことが結果的
に、最長の探索タスクを実行しているプロセッサが終了
するのを待つ間、一部のプロセッサが相当の時間を浪費
することにつながる。
サ探索アルゴリズムは、通常、探索空間を、多数のプロ
セッサによって並行して探索される部分空間に分割しよ
うとするものである。公知の従来の多重プロセッサ探索
アルゴリズムに固有の欠点の一つは、処理の高速化が線
形からはずれる、つまり、プロセッサの数が増えるにつ
れて飽和する傾向がある点である。この飽和の第１の理
由は、最長実行探索タスクの長さに関係している。タス
ク実行時間の大きな分散は、各プロセッサにかけられる
処理負荷に著しい不均衡を生じ得る。このことが結果的
に、最長の探索タスクを実行しているプロセッサが終了
するのを待つ間、一部のプロセッサが相当の時間を浪費
することにつながる。
【０００７】希望の水準の処理効率を得るためには、全
プロセッサがほぼ同時に終了するように各プロセッサ間
で処理タスクが割当てられるようにすることが重要であ
る。処理負荷がうまく均衡がとれていれば、いずれのプ
ロセッサも、他のプロセッサが作業を終了するのを待つ
間、不当に長い時間、遊休状態とはならない。その結果
、負荷が不均衡なシステムに優る処理の高速化および効
率の向上が実現される。
プロセッサがほぼ同時に終了するように各プロセッサ間
で処理タスクが割当てられるようにすることが重要であ
る。処理負荷がうまく均衡がとれていれば、いずれのプ
ロセッサも、他のプロセッサが作業を終了するのを待つ
間、不当に長い時間、遊休状態とはならない。その結果
、負荷が不均衡なシステムに優る処理の高速化および効
率の向上が実現される。
【０００８】従って、この発明の第１の目的は、飽和作
用を明示的に考慮し克服する、処理タスクを割当てるた
めの装置および方法を提供することである。
用を明示的に考慮し克服する、処理タスクを割当てるた
めの装置および方法を提供することである。
【０００９】この発明の第２の目的は、探索樹の各部分
樹での探索労力量に比例してプロセッサを割当てること
により飽和を克服する装置および方法を提供することで
ある。
樹での探索労力量に比例してプロセッサを割当てること
により飽和を克服する装置および方法を提供することで
ある。
【００１０】さらに、この発明の第３の目的は、多重プ
ロセッサシステムにおいて、制約条件満足化問題の事例
を解決するために利用される後戻り探索樹の各部分樹に
沿った探索労力の分散を、全プロセッサがほぼ同時に各
自の処理タスクを終了するようにして、最小にすること
である。
ロセッサシステムにおいて、制約条件満足化問題の事例
を解決するために利用される後戻り探索樹の各部分樹に
沿った探索労力の分散を、全プロセッサがほぼ同時に各
自の処理タスクを終了するようにして、最小にすること
である。
【００１１】
【問題点を解決するための手段】制約条件満足化問題の
事例を後戻り探索樹によって解決するために多重プロセ
ッサシステムにおいて用いられる装置および方法によっ
て、前述の課題は克服され、発明の目的は達せられる。 この発明の一面に従えば、この方法は、ａ）探索樹の各
部分樹に必要な探索労力量を評価する段階と、ｂ）評価
探索労力量にもとづいて探索樹の各部分樹に適切な数の
プロセッサを割当て、その際、各部分樹に割当てられた
プロセッサの数は各部分樹に沿った探索処理時間の分散
を最小にするように選択される段階と、ｃ）割当てられ
たプロセッサにより探索樹の各部分樹に沿って並行して
探索を実行する段階とを含む。
事例を後戻り探索樹によって解決するために多重プロセ
ッサシステムにおいて用いられる装置および方法によっ
て、前述の課題は克服され、発明の目的は達せられる。 この発明の一面に従えば、この方法は、ａ）探索樹の各
部分樹に必要な探索労力量を評価する段階と、ｂ）評価
探索労力量にもとづいて探索樹の各部分樹に適切な数の
プロセッサを割当て、その際、各部分樹に割当てられた
プロセッサの数は各部分樹に沿った探索処理時間の分散
を最小にするように選択される段階と、ｃ）割当てられ
たプロセッサにより探索樹の各部分樹に沿って並行して
探索を実行する段階とを含む。
【００１２】適切な数のプロセッサを割当てる段階は、
さらに、ａ）探索を実施するために使用できるプロセッ
サの総数をＭ、部分空間の評価された大きさをそれぞれ
、サイズ（Ｔ１）、サイズ（Ｔ２）、…、サイズ（ＴＮ
）とした時に、探索樹をＴ１、Ｔ２、…、ＴＮとして示
されるＮ（＜Ｍ）の部分空間に分割する段階と、ｂ）そ
の部分空間の探索に関係する評価労力に比例して部分空
間にＭのプロセッサを割当てる段階とを含む。
さらに、ａ）探索を実施するために使用できるプロセッ
サの総数をＭ、部分空間の評価された大きさをそれぞれ
、サイズ（Ｔ１）、サイズ（Ｔ２）、…、サイズ（ＴＮ
）とした時に、探索樹をＴ１、Ｔ２、…、ＴＮとして示
されるＮ（＜Ｍ）の部分空間に分割する段階と、ｂ）そ
の部分空間の探索に関係する評価労力に比例して部分空
間にＭのプロセッサを割当てる段階とを含む。
【００１３】プロセッサを割当てる段階は、ａ）
【００
１４】
１４】
【式９】
を行う段階と、ｂ）ｃｉ＝サイズ（Ｔｉ）／Ｓを行う段
階と、ｃ）部分空間Ｔｉを探索するために割当てられる
べきプロセッサの数をａｉで示す段階とを含むものと開
示されている。プロセッサを割当てる段階はさらに、ｄ
）１≦ｉ≦Ｎの場合にａｉを丸めた値Ｍｃｉとする段階
と、ｅ）ａｉ＜１の場合にａｉ＝１とする段階と、ｆ）
階と、ｃ）部分空間Ｔｉを探索するために割当てられる
べきプロセッサの数をａｉで示す段階とを含むものと開
示されている。プロセッサを割当てる段階はさらに、ｄ
）１≦ｉ≦Ｎの場合にａｉを丸めた値Ｍｃｉとする段階
と、ｅ）ａｉ＜１の場合にａｉ＝１とする段階と、ｆ）
【００１５】
【式１０】
の場合にＭのプロセッサ全部が割当てられるまで、列Ｔ
１、Ｔ２…の各部分空間に追加のプロセッサを割当てる
段階とを含む。
１、Ｔ２…の各部分空間に追加のプロセッサを割当てる
段階とを含む。
【００１６】
【式１１】
の場合は、列Ｔ１、Ｔ２…の各部分空間について、
【０
０１７】
０１７】
【式１２】
になるまでａｉを１ずつ減らす段階が含まれる。
【００１８】
【実施例】この発明の教授するところから益する適用業
務は、しばしば、１以上の離散的データプロセッサによ
って、以下の総称形の制約条件満足化問題を解決する。
務は、しばしば、１以上の離散的データプロセッサによ
って、以下の総称形の制約条件満足化問題を解決する。
【００１９】
Ｇ（ｓ）＝Ｐ１（Ｓ１）＆Ｐ２（
Ｓ２）＆…ＰＭ（ＳＭ）式中、Ｇ（Ｓ）は解決すべき問
題、Ｓ＝｛Ｘ１、Ｘ２、．．．、ＸＮ｝はＮ個の引数の
変数の集合である。 １≦ｉ≦Ｍにおいて、Ｐｉ（Ｓｉ）は、引数Ｓｉを持つ
ｉ番目の副次問題である。ここで、
Ｓ２）＆…ＰＭ（ＳＭ）式中、Ｇ（Ｓ）は解決すべき問
題、Ｓ＝｛Ｘ１、Ｘ２、．．．、ＸＮ｝はＮ個の引数の
変数の集合である。 １≦ｉ≦Ｍにおいて、Ｐｉ（Ｓｉ）は、引数Ｓｉを持つ
ｉ番目の副次問題である。ここで、
【００２０】
【式１３】
である。問題Ｇの解決は、ａ）各副次問題Ｐｉが解決さ
れる、ｂ）２以上の副次問題に共通である各引数が整合
的に１定数に結ばれるような形で、Ｐ１、Ｐ２、．．．
、ＰＭの各引数に定数を結ぶことである。両者の解決は
、結びが異なる場合、すなわち、１以上の引数が２の結
びで異なる２の値に結ばれた場合、まったく異なる。
れる、ｂ）２以上の副次問題に共通である各引数が整合
的に１定数に結ばれるような形で、Ｐ１、Ｐ２、．．．
、ＰＭの各引数に定数を結ぶことである。両者の解決は
、結びが異なる場合、すなわち、１以上の引数が２の結
びで異なる２の値に結ばれた場合、まったく異なる。
【００２１】例えば、制約条件満足化問題の場合、Ｓの
部分集合の結びが与えられた場合、コンピュータ実施探
索手順は、Ｓの残りについて整合的な結びの全部を列挙
することを求められる。図１に示した形式の探索樹１０
は、そうした探索手順で利用される。探索樹１０は根ノ
ード１２を持っている。その葉ノードに向かう探索樹１
０に沿った動きを順方向探索と呼び、根ノード１２に向
かう動きを後戻り探索と呼ぶ。探索樹１０は、１４、１
６、１８ａおよび１８ｂで指示されている多数の部分樹
から成っている。図からわかるように、部分樹１６はさ
らに小さい部分樹１８ａおよび１８ｂを含んでいる。一
般に、探索樹１０は、多数の部分樹から成っており、素
の部分空間に分割される。各部分樹は部分空間に一致す
る。
部分集合の結びが与えられた場合、コンピュータ実施探
索手順は、Ｓの残りについて整合的な結びの全部を列挙
することを求められる。図１に示した形式の探索樹１０
は、そうした探索手順で利用される。探索樹１０は根ノ
ード１２を持っている。その葉ノードに向かう探索樹１
０に沿った動きを順方向探索と呼び、根ノード１２に向
かう動きを後戻り探索と呼ぶ。探索樹１０は、１４、１
６、１８ａおよび１８ｂで指示されている多数の部分樹
から成っている。図からわかるように、部分樹１６はさ
らに小さい部分樹１８ａおよび１８ｂを含んでいる。一
般に、探索樹１０は、多数の部分樹から成っており、素
の部分空間に分割される。各部分樹は部分空間に一致す
る。
【００２２】図２は、多数の（Ｐ１〜ＰＭ）個別の離散
的データプロセッサ２２を有する例示的な多重プロセッ
サデータ処理システム２０の略ブロック図を示す。デー
タ処理システム２０は、プロセッサ２２の間でタスク割
当てを管理し、また、システム２０のユーザとプロセッ
サ２２間のインタフェースとして働く、制御プロセッサ
（ＣＰ）２４を含む。ＣＰ２４は、下記の探索タスク評
価プログラムおよび離散的プロセッサ割当てプログラム
を含む、蓄積制御プログラムを実行するための記憶・命
令実行回路を含んでいる。データ信号線および制御信号
線を有する制御バス２４ａは、ＣＰ ２４とプロセッ
サ２２を結合しており、プロセッサ２２に対する、処理
タスクの割当ておよび探索樹の部分樹を表すデータなど
のデータの供給に使用される。図示されたシステムにお
いて、プロセッサ２２はそれぞれ、ローカル記憶装置バ
ス２６ａを介して共通記憶装置２６に結合されている。 共通記憶装置２６は、共用記憶域を通じて相互に通信す
るためにプロセッサ２２によって使用される。各プロセ
ッサ２２も、通常、命令およびデータの記憶のためのロ
ーカル記憶装置を含んでいる。図２がこの発明の方法を
実施する適切な実施例の一例にすぎず、分散型記憶装置
などの他のアーキテクチャを有する多数の適切な多重プ
ロセッサシステムが利用できることを理解しなければな
らない。
的データプロセッサ２２を有する例示的な多重プロセッ
サデータ処理システム２０の略ブロック図を示す。デー
タ処理システム２０は、プロセッサ２２の間でタスク割
当てを管理し、また、システム２０のユーザとプロセッ
サ２２間のインタフェースとして働く、制御プロセッサ
（ＣＰ）２４を含む。ＣＰ２４は、下記の探索タスク評
価プログラムおよび離散的プロセッサ割当てプログラム
を含む、蓄積制御プログラムを実行するための記憶・命
令実行回路を含んでいる。データ信号線および制御信号
線を有する制御バス２４ａは、ＣＰ ２４とプロセッ
サ２２を結合しており、プロセッサ２２に対する、処理
タスクの割当ておよび探索樹の部分樹を表すデータなど
のデータの供給に使用される。図示されたシステムにお
いて、プロセッサ２２はそれぞれ、ローカル記憶装置バ
ス２６ａを介して共通記憶装置２６に結合されている。 共通記憶装置２６は、共用記憶域を通じて相互に通信す
るためにプロセッサ２２によって使用される。各プロセ
ッサ２２も、通常、命令およびデータの記憶のためのロ
ーカル記憶装置を含んでいる。図２がこの発明の方法を
実施する適切な実施例の一例にすぎず、分散型記憶装置
などの他のアーキテクチャを有する多数の適切な多重プ
ロセッサシステムが利用できることを理解しなければな
らない。
【００２３】この発明に従えば、図３のフローチャート
に示すように、プロセッサ２２間で制約条件満足化問題
の後戻り樹木探索を割当てるために、以下の３段階が達
成される。ここで、Ｍは、樹木探索を実施するために使
用できる多重プロセッサシステム２０におけるプロセッ
サ２２の総数である。
に示すように、プロセッサ２２間で制約条件満足化問題
の後戻り樹木探索を割当てるために、以下の３段階が達
成される。ここで、Ｍは、樹木探索を実施するために使
用できる多重プロセッサシステム２０におけるプロセッ
サ２２の総数である。
【００２４】ブロック３０で、ＣＰ ２４またはその
他の適切なプロセッサは、探索樹１０の各部分樹で必要
な探索労力量を評価する。ブロック３２で、ＣＰ ２
４は、探索樹１０の各部分樹に割当てるためにプロセッ
サ２２の適切な数を計算または決定する。ブロック３４
で、探索樹１０の各部分樹に沿って、選択されたプロセ
ッサ２２によって並行して樹木探索が実施される。
他の適切なプロセッサは、探索樹１０の各部分樹で必要
な探索労力量を評価する。ブロック３２で、ＣＰ ２
４は、探索樹１０の各部分樹に割当てるためにプロセッ
サ２２の適切な数を計算または決定する。ブロック３４
で、探索樹１０の各部分樹に沿って、選択されたプロセ
ッサ２２によって並行して樹木探索が実施される。
【００２５】図３のブロック３０に示す最初の段階、す
なわち、探索樹１０の各部分樹で必要な探索労力量を評
価する段階は、公知の技法によって実施できる。特に、
Ｄ．Ｅ．Ｋｎｕｔｈによる論文“Ｅｓｔｉｍａｔｉｎｇ
ｔｈｅ Ｅｆｆｉｃｉｅｎｃｙ ｏｆ Ｂａ
ｃｋｔｒａｃｋ Ｐｒｏｇｒａｍａ”（Ｍａｔｈｅｍ
ａｔｉｃｓ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎ，
Ｖｏｌ．２９， １９７５，ｐｐ．１２１−１３６）
に述べられたサンプリング法または、論文“Ｅｓｔｉｍ
ａｔｉｎｇ Ｔｈｅ Ｓｉｚｅ Ｏｆ Ａ
Ｂａｃｋｔｒａｃｋ ＳｅａｒｃｈＤｕｒｉｎｇ
Ｔｈｅ Ｓｅａｒｃｈ Ｏｐｅｒａｔｉｏｎ”（Ｉ
ＢＭ Ｔｅｃｈｎｉｃａｌ Ｄｉｓｃｌｏｓｕｒｅ
Ｂｕｌｌｅｔｉｎ， Ｖｏｌ．３０， Ｎｏ．
８， Ｊａｎｕａｒｙ １９８８）に述べられた確
定的評価法がブロック３０の段階を実施するために使用
できる。
なわち、探索樹１０の各部分樹で必要な探索労力量を評
価する段階は、公知の技法によって実施できる。特に、
Ｄ．Ｅ．Ｋｎｕｔｈによる論文“Ｅｓｔｉｍａｔｉｎｇ
ｔｈｅ Ｅｆｆｉｃｉｅｎｃｙ ｏｆ Ｂａ
ｃｋｔｒａｃｋ Ｐｒｏｇｒａｍａ”（Ｍａｔｈｅｍ
ａｔｉｃｓ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎ，
Ｖｏｌ．２９， １９７５，ｐｐ．１２１−１３６）
に述べられたサンプリング法または、論文“Ｅｓｔｉｍ
ａｔｉｎｇ Ｔｈｅ Ｓｉｚｅ Ｏｆ Ａ
Ｂａｃｋｔｒａｃｋ ＳｅａｒｃｈＤｕｒｉｎｇ
Ｔｈｅ Ｓｅａｒｃｈ Ｏｐｅｒａｔｉｏｎ”（Ｉ
ＢＭ Ｔｅｃｈｎｉｃａｌ Ｄｉｓｃｌｏｓｕｒｅ
Ｂｕｌｌｅｔｉｎ， Ｖｏｌ．３０， Ｎｏ．
８， Ｊａｎｕａｒｙ １９８８）に述べられた確
定的評価法がブロック３０の段階を実施するために使用
できる。
【００２６】図３に示す方法の最後の段階、すなわち、
探索樹の各部分樹に沿って、選択されたプロセッサによ
って並行して探索が実施されるブロック３４もまた、論
文“Ｐａｒａｌｌｅｌ Ｌｏｏｋａｈｅａｄ Ｔｅ
ｃｈｎｉｑｕｅ Ｆｏｒ Ｃｏｎｓｔｒａｉｎｔ
Ｓａｔｉｓｆａｃｔｉｏｎ”（ＩＢＭ Ｔｅｃｈｎ
ｉｃａｌＤｉｓｃｌｏｓｕｒｅ Ｂｕｌｌｅｔｉｎ，
Ｖｏｌ．３１， Ｎｏ．１０，Ｍａｒｃｈ １
９８９）に述べられたような公知の技法によって実施で
きる。
探索樹の各部分樹に沿って、選択されたプロセッサによ
って並行して探索が実施されるブロック３４もまた、論
文“Ｐａｒａｌｌｅｌ Ｌｏｏｋａｈｅａｄ Ｔｅ
ｃｈｎｉｑｕｅ Ｆｏｒ Ｃｏｎｓｔｒａｉｎｔ
Ｓａｔｉｓｆａｃｔｉｏｎ”（ＩＢＭ Ｔｅｃｈｎ
ｉｃａｌＤｉｓｃｌｏｓｕｒｅ Ｂｕｌｌｅｔｉｎ，
Ｖｏｌ．３１， Ｎｏ．１０，Ｍａｒｃｈ １
９８９）に述べられたような公知の技法によって実施で
きる。
【００２７】図４のブロック図に示す、この発明の好ま
しい方法に従って、ここで、探索樹１０の各部分樹に割
当てるためにプロセッサ２２の適切な数を計算または決
定するブロック３２の段階を詳細に説明する。
しい方法に従って、ここで、探索樹１０の各部分樹に割
当てるためにプロセッサ２２の適切な数を計算または決
定するブロック３２の段階を詳細に説明する。
【００２８】図４について説明する。探索樹はＴ１、Ｔ
２、…、ＴＮとして示されるＮ（＜Ｍ）の部分空間に分
割される。これらの部分空間の評価された大きさは、そ
れぞれ、サイズ（Ｔ１）、サイズ（Ｔ２）、…、サイズ
（ＴＮ）として表される。普遍性を失わなければ、サイ
ズ（Ｔ１）≧サイズ（Ｔ２）≧…≧サイズ（ＴＮ）と仮
定する。
２、…、ＴＮとして示されるＮ（＜Ｍ）の部分空間に分
割される。これらの部分空間の評価された大きさは、そ
れぞれ、サイズ（Ｔ１）、サイズ（Ｔ２）、…、サイズ
（ＴＮ）として表される。普遍性を失わなければ、サイ
ズ（Ｔ１）≧サイズ（Ｔ２）≧…≧サイズ（ＴＮ）と仮
定する。
【００２９】この発明に従えば、各部分空間で探索を行
うためのプロセッサ２２の適切な数は、個別の部分空間
の完了時間の分散を最小にするように決定される。この
決定は、
うためのプロセッサ２２の適切な数は、個別の部分空間
の完了時間の分散を最小にするように決定される。この
決定は、
【００３０】
【式１４】
を行う（ブロック４０）、ｃｉ＝サイズ（Ｔｉ）／Ｓを
行う（ブロック４２）、部分空間Ｔｉを探索するために
割当てられるべきプロセッサの数をａｉで示す（ブロッ
ク４４）を含む。１≦ｉ≦Ｎの場合、ａｉを丸めた値Ｍ
ｃｉとされる（ブロック４６）。ａｉ＜１の場合、ａｉ
はブロック４８で１に設定される。
行う（ブロック４２）、部分空間Ｔｉを探索するために
割当てられるべきプロセッサの数をａｉで示す（ブロッ
ク４４）を含む。１≦ｉ≦Ｎの場合、ａｉを丸めた値Ｍ
ｃｉとされる（ブロック４６）。ａｉ＜１の場合、ａｉ
はブロック４８で１に設定される。
【００３１】
【式１５】
の場合（ブロック５０）、Ｍのプロセッサ全部が割当て
られるまで、列Ｔ１、Ｔ２…の各部分空間に追加のプロ
セッサ２２が割当てられる（ブロック５２）。
られるまで、列Ｔ１、Ｔ２…の各部分空間に追加のプロ
セッサ２２が割当てられる（ブロック５２）。
【００３２】
【式１６】
であれば、列Ｔ１、Ｔ２…の各部分空間について、
【０
０３３】
０３３】
【式１７】
になるまでａｉが１ずつ減らされる（ブロック５４）。
この発明に従えば、上述の段階は、部分空間を探索する
際に関係する評価労力量に比例して部分空間にＭのプロ
セッサを割当てる操作である。
際に関係する評価労力量に比例して部分空間にＭのプロ
セッサを割当てる操作である。
【００３４】ａｉ＜１である多数の探索タスクがある場
合、そのようなタスクのある数が好適に組合せられ、プ
ロセッサ２２のうちのいずれか一つに割当てられる。一
般に、多重プロセッサシステムのプロセッサ間で評価探
索労力の関数として評価探索労力を均等に配分するよう
にする、いずれかのプロセッサ割当て法を利用すること
ができる。
合、そのようなタスクのある数が好適に組合せられ、プ
ロセッサ２２のうちのいずれか一つに割当てられる。一
般に、多重プロセッサシステムのプロセッサ間で評価探
索労力の関数として評価探索労力を均等に配分するよう
にする、いずれかのプロセッサ割当て法を利用すること
ができる。
【００３５】上述のように、この発明を好ましい実施例
によって詳細に示し説明したが、この発明の範囲および
精神を逸脱することなく形式および細部の変更が行える
ことは、当業者によって理解されるであろう。
によって詳細に示し説明したが、この発明の範囲および
精神を逸脱することなく形式および細部の変更が行える
ことは、当業者によって理解されるであろう。
【図１】典型的な後戻り探索樹を例示する図。
【図２】この発明の教授を実施するために適した多重プ
ロセッサシステムの１実施例のブロック図。
ロセッサシステムの１実施例のブロック図。
【図３】探索樹の部分樹を探索するためにプロセッサを
割当てる際に関係する段階を示すフローチャート。
割当てる際に関係する段階を示すフローチャート。
【図４】探索樹の各部分樹に割当てられるプロセッサの
数を決定するためのこの発明の方法を示す詳細フローチ
ャート。
数を決定するためのこの発明の方法を示す詳細フローチ
ャート。
２０ 多重プロセッサデータ処理システム２２ 離
散的データプロセッサ ２４ 制御プロセッサ ２４ａ 制御バス ２６ａ ローカル記憶装置バス ２６ 共通記憶装置 ３０ 探索量評価段階 ３２ プロセッサ割当て段階 ３４ 並行探索実行段階
散的データプロセッサ ２４ 制御プロセッサ ２４ａ 制御バス ２６ａ ローカル記憶装置バス ２６ 共通記憶装置 ３０ 探索量評価段階 ３２ プロセッサ割当て段階 ３４ 並行探索実行段階
Claims (11)
- 【請求項１】多重プロセッサシステムにおいて、制約条
件満足化問題の事例を後戻り探索樹によって解決する方
法であって、探索樹の各部分樹に必要な探索労力量を評
価する段階と、評価探索労力量にもとづいて探索樹の各
部分樹に適切な数のプロセッサを割当て、その際、各部
分樹に割当てられるプロセッサの数は各部分樹に沿った
探索処理時間の分散を最小にするように選択される段階
と、割当てられたプロセッサにより探索樹の各部分樹に
沿って並行して探索を実行する段階とを含む方法。 - 【請求項２】請求項１記載の方法であって、適切な数の
プロセッサを割当てる段階が、探索を実施するために使
用できるプロセッサの総数をＭ、部分空間の評価された
大きさをそれぞれ、サイズ（Ｔ１）、サイズ（Ｔ２）、
…、サイズ（ＴＮ）とした時に、探索樹をＴ１、Ｔ２、
…、ＴＮとして示されるＮ（＜Ｍ）の部分空間に分割す
る段階と、その部分空間の探索に関係する評価労力に比
例して部分空間にＭのプロセッサを割当てる段階とを含
む方法。 - 【請求項３】請求項２記載の方法であって、プロセッサ
を割当てる段階が、 【式１】 を行う段階と、ｃｉ＝サイズ（Ｔｉ）／Ｓを行う段階と
、部分空間Ｔｉを探索するために割当てられるべきプロ
セッサの数をａｉで示す段階と、１≦ｉ≦Ｎの場合、ａ
ｉを丸めた値Ｍｃｉとする段階と、ａｉ＜１の場合、ａ
ｉ＝１とする段階と、 【式２】 の場合、Ｍのプロセッサ全部が割当てられるまで、列Ｔ
１、Ｔ２…の各部分空間に追加のプロセッサを割当てる
段階と、または、 【式３】 の場合、列Ｔ１、Ｔ２…の各部分空間について、【式４
】 になるまでａｉを１ずつ減らす段階とを含む方法。 - 【請求項４】請求項３記載の方法であって、ａｉ＜１の
条件について、プロセッサを割当てる段階が探索タスク
を組合わせ、その組合わされた探索タスクを単一のプロ
セッサに割当てる段階を含む方法。 - 【請求項５】多重プロセッサデータ処理システムにおい
て、制約条件満足化問題の事例を後戻り探索樹によって
解決するために使用される後戻り探索樹の各部分樹に沿
った探索の分散を最小にするためのプロセッサ割当て装
置であって、探索樹の各部分樹に必要な探索労力量を評
価するための手段と、評価探索労力量に応答する、探索
樹の各部分樹に適切な数のプロセッサを割当てる手段と
を含み、この割当て手段は、探索を実施するために使用
できるプロセッサの総数をＭ、部分空間の評価された大
きさをそれぞれ、サイズ（Ｔ１）、サイズ（Ｔ２）、…
、サイズ（ＴＮ）とした時に、探索樹をＴ１、Ｔ２、…
、ＴＮとして示されるＮ（＜Ｍ）の部分空間に分割する
手段および、その部分空間の探索に関係する評価労力に
比例して部分空間にＭのプロセッサを割当てる手段とを
含んでいる装置。 - 【請求項６】請求項５記載の多重プロセッサデータ処理
システムであって、Ｍのプロセッサがそれぞれ共通のデ
ータ記憶装置に結合されている多重プロセッサデータ処
理システム。 - 【請求項７】請求項５記載の多重プロセッサデータ処理
システムであって、Ｍのプロセッサがそれぞれ探索樹の
各部分樹に沿って並行して探索を実行するための手段を
含んでいる多重プロセッサデータ処理システム。 - 【請求項８】請求項５記載の多重プロセッサデータ処理
システムであって、探索労力量を評価するための手段お
よびプロセッサを割当てるための手段が、Ｍのプロセッ
サのそれぞれに共通に結合された制御データプロセッサ
を含んでいる多重プロセッサデータ処理システム。 - 【請求項９】多数の離散的データ処理装置を含む多重プ
ロセッサデータ処理システムにおいて、制約条件満足化
問題の事例を後戻り探索樹によって解決する方法であっ
て、探索樹の各部分樹に必要な探索労力量を制御データ
プロセッサによって評価する段階と、制御データプロセ
ッサによって、評価探索労力量の関数として各部分樹に
沿った探索処理時間の分散を最小にするように選択され
る数の１以上の離散的データ処理装置を探索樹の各部分
樹のそれぞれに割当てる段階と、割当てられた処理装置
によって探索樹の各部分樹に沿って並行して探索を実行
する段階であって、この段階が、探索を実施するために
使用できる処理装置の総数をＭ、部分空間の評価された
大きさをそれぞれ、サイズ（Ｔ１）、サイズ（Ｔ２）、
…、サイズ（ＴＮ）とした時に、探索樹をＴ１、Ｔ２、
…、ＴＮとして示されるＮ（＜Ｍ）の部分空間に分割す
る段階および、その部分空間の探索に関係する評価労力
量に比例して部分空間にＭの処理装置を割当てる段階と
を含んでいる方法。 - 【請求項１０】請求項９記載の方法であって、処理装置
を割当てる段階が、 【式５】 を行う段階と、ｃｉ＝サイズ（Ｔｉ）／Ｓを行う段階と
、部分空間Ｔｉを探索するために割当てられるべき処理
装置の数をａｉで示す段階と、１≦ｉ≦Ｎの場合、ａｉ
を丸めた値Ｍｃｉとする段階と、ａｉ＜１の場合、ａｉ
＝１とする段階と、 【式６】 の場合、Ｍのプロセッサ全部が割当てられるまで、列Ｔ
１、Ｔ２…の各部分空間に追加の処理装置を割当てる段
階と、または、 【式７】 の場合、列Ｔ１、Ｔ２…の各部分空間について、【式８
】 になるまでａｉを１ずつ減らす段階とを含む方法。 - 【請求項１１】請求項１０記載の方法であって、ａｉ＜
１の条件について、処理装置を割当てる段階が探索タス
クを組合わせ、その組合わされた探索タスクを単一の処
理装置に割当てる段階を含む方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US48403490A | 1990-02-22 | 1990-02-22 | |
| US484034 | 1990-02-22 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04348452A true JPH04348452A (ja) | 1992-12-03 |
| JP2677713B2 JP2677713B2 (ja) | 1997-11-17 |
Family
ID=23922464
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3021531A Expired - Lifetime JP2677713B2 (ja) | 1990-02-22 | 1991-01-22 | 制約条件満足化探索の多重プロセッサの実行のためのプロセッサ割当ての方法 |
Country Status (2)
| Country | Link |
|---|---|
| EP (1) | EP0443130A3 (ja) |
| JP (1) | JP2677713B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6285977B1 (en) | 1993-04-20 | 2001-09-04 | Mitsubishi Denki Kabushiki Kaisha | Multi-agents cooperating method and system |
| JP2017517082A (ja) * | 2014-03-17 | 2017-06-22 | マイクロソフト テクノロジー ライセンシング，エルエルシー | 並列ディシジョン・ツリー・プロセッサー・アーキテクチャ |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2504738A (en) * | 2012-08-08 | 2014-02-12 | Basis Technologies Internat Ltd | SAP (RTM) system with partitioning of data in SAP memory into data intervals |
-
1990
- 1990-12-10 EP EP19900123740 patent/EP0443130A3/en not_active Ceased
-
1991
- 1991-01-22 JP JP3021531A patent/JP2677713B2/ja not_active Expired - Lifetime
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6285977B1 (en) | 1993-04-20 | 2001-09-04 | Mitsubishi Denki Kabushiki Kaisha | Multi-agents cooperating method and system |
| JP2017517082A (ja) * | 2014-03-17 | 2017-06-22 | マイクロソフト テクノロジー ライセンシング，エルエルシー | 並列ディシジョン・ツリー・プロセッサー・アーキテクチャ |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2677713B2 (ja) | 1997-11-17 |
| EP0443130A2 (en) | 1991-08-28 |
| EP0443130A3 (en) | 1992-12-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Weingartner et al. | Methods for the solution of the multidimensional 0/1 knapsack problem | |
| JP2825611B2 (ja) | 割当依存型製造資源割当方法 | |
| Thomasian et al. | A decomposition solution to the queueing network model of the centralized DBMS with static locking | |
| CN109376151A (zh) | 数据分库处理方法、系统、装置和存储介质 | |
| US5146540A (en) | Processor allocation method and apparatus for multiprocessor execution of a constraint satisfaction search | |
| CN113157421A (zh) | 一种基于用户作业流程的分布式集群资源调度方法 | |
| CN111724037A (zh) | 运营资源分配方法、装置、计算机设备及可读存储介质 | |
| Artigues et al. | A new exact solution algorithm for the job shop problem with sequence-dependent setup times | |
| JPH04348452A (ja) | 制約条件満足化探索の多重プロセッサの実行のためのプロセッサ割当ての方法 | |
| JP4021287B2 (ja) | データベース検索プログラム、データベース検索方法及びデータベース検索装置 | |
| CN115934728A (zh) | 文件导入方法、装置及电子设备 | |
| CN118277087B (zh) | 一种资源调度策略确定方法、介质、电子设备和程序产品 | |
| CN119781979A (zh) | 一种内存分配方法、系统、终端及存储介质 | |
| US20100049747A1 (en) | Apparatus and method for storing log in a thread oriented logging system | |
| Ismaeel et al. | A systematic cloud workload clustering technique in large scale data centers | |
| Bohlouli et al. | Grid-HPA: Predicting resource requirements of a job in the grid computing environment | |
| CN118964495B (zh) | 一种线上办公信息的同步共享方法 | |
| CN113742052B (zh) | 批量任务处理方法和装置 | |
| CN115129481A (zh) | 一种计算资源分配方法、装置及电子设备 | |
| US20020099716A1 (en) | Technique and apparatus to process data | |
| US10929388B1 (en) | Distributed multi-version partitioned mapreduce for a data fabric | |
| Cousins et al. | The embedded genetic allocator-a system to automatically optimize the use of memory resources in high performance, scalable computing systems | |
| JPH09172453A (ja) | 回覧業務管理方法および回覧業務管理装置 | |
| Liu et al. | Comprehensive evaluation of large-scale parallel matrix factorization algorithms | |
| JPH09198441A (ja) | 見積装置及び見積方法 |