JPH0281257A - タスク割当て装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は、並列処理システムで実行される複数のタスク
を最適に割当てるタスク割当て装置に係わり、特にニュ
ーラルネットを用いたタスク割当て装置に関する。

（従来の技術） 近年、並列処理技術の発展に伴って、並列処理システム
を構成する複数のプロセッシングエレメント（以下ＰＥ
と略称する）に複数のタスクを割当てる最適タスク割当
て問題が重要視されるようになってきた。

すなわち、一般に並列処理システムでは、単にＰＨの数
を増やしただけでは、期待する程の処理効率の向上は図
れない。その理由はタスク間で通信が存在し、これに時
間がかかることや、タスクが必ずしも並列には実行され
ないことから、タスクの割当てが悪いと、多くのＰＥが
待ち状態になってしまうからである。

そこで、タスクの時間的配置（スケジューリング）や負
荷分散を考慮したタスク割当ての最適解を求めるための
手法が必要となる。しかし、このような最適解を公知な
数理的手法で求めることは、計算量が膨大であることか
ら、一般には困難である。また、ヒユーリスティックス
を導入して最適解を求める方法も知られているが、局所
的に計算量を減じてい〈従来の手法では必ずしも良い解
が得られていない。

一方、ホップフィールド（Ｈｏｐｌ’１ｅｌｄ）がニュ
ーラルネットを用いて、最適化組合わせ問題の一つであ
る巡回セールスマン問題を解いた（　ＪｏｈｎＪ、Ｈｏ
ｐｆｉｅｌｄ　ａｎｄ　Ｄａｖｉｄ　Ｗ、Ｔａｎｋ、Ｂ
Ｉｏｌ、Ｃｙｂｅｒｎ、５２゜１４１−１５２（１９８
５））ことにより、上述した最適タスク割当て問題を解
決するに当り上記ニューラルネットを適用することが検
討されている。

第９図は上記ニューラルネットの構成を示す図である。

なお、この二二一うルネットは、米国特許４７１９５９
１号および同４７３１７４７号に開示されている。二二
一うルネット１０は、複数のニューロン素子Ｎ１　、　
Ｎ２　、　　Ｎ３−Ｎ　ｎと、伝達路１と、結合部２と
から構成されている。ニューロン素子Ｎｉ　　（ｉ＝１
．２．３・＝ｎ）の出力は、伝達路１を介して他のニュ
ーロン素子Ｎｊ（ｊ−１，２゜３、・・・ｎ：但しｊ≠
ｉ）の入力と結合部２において結合されている。各結合
の強さは結合係数Ｗ１ｊによって決定される。また、二
つのニューロン素子Ｎ間の結合は対象的（Ｗｉｊ＝Ｗｊ
ｉ）である。

第１０図はｊ番目のニューロン素子Ｎｊを取出して示し
た図である。ニューロン素子Ｎ１からの入力信号ｘ　ｉ
　ｓニューロン素子Ｎｊの出力をｙｊ、内部状態変数を
ｕｊとすると、ニューロン素子Ｎｊは、次式（１）に従
って動作する。

ｙｊ−ｆ（ｕｊ） ・・・　（２） 但し、τは定数である。

ここで変数ｆとしては、例えば第１１図に示すように、
Ｓ字形（ｓｉｇｍｏｌｄ）関数等の単調増加関数が用い
られている。この関数によれば、ニューロン素子Ｎｊは
内部状態ｕｊが大きくなると「１」に近い信号ｙｊを出
力し、内部状態ｕｊが負の方に大きくなると「０」に近
い信号ｙｊを出力する。

ここでニューラルネット１０のエネルギーの総和Ｅ　（
ｙ）は（３）式で定義される。

連想記憶モデルでは、ニューラルネット１０の結合係数
Ｗが決定されると、第１２図に示すように、（３）式の
エネルギー関数Ｅ　（ｙ）が決定する。

この状態で各ニューロン素子Ｎ１に任意の初期値が設定
されると、ニューラルネット１０のエネルギーＥが上記
エネルギー関数Ｅ　（ｙ）のどのエネルギーレベルであ
るかが決定し、各ニューロン素子Ｎｉが（１−）、（２
）式に示した動作を行なうことにより、ニューラルネッ
ト１０のエネルギーＥはエネルギー関数Ｅ　（ｙ）の勾
配に従って例えばＰｏ、Ｐｌと遷移し、初期値に対応し
たエネルギーの極小点Ｐ２に向けて収束する。したがっ
て、このエネルギー関数Ｅ　（ｙ）を最適化における評
価関数と対応させるべき結合係数を決定することにより
、上記収束点における各ニューロン素子の状態パターン
が最適化問題の解として求められる。

このようなニューラルネット１０を用いて最適タスク割
当て問題の解を求める場合、従来の方法では、ニューラ
ルネット１０としてタスクの数ｎ個とＰＨの数ｍ個との
積、すなわちｎｘｍ個のニューロン素子Ｎｉが必要とな
る。そして例えばタスク間の並列可能性と通信量とを結
合部２の伝達係数Ｗ、　ｉ　ｊに反映させて設定する。

そしてニューラルネットに任意の初期値を設定し、ニュ
ーラルネットを動作させると、二二一うルネット１０の
エネルギーＥが収束した時、すなわち一定になったとき
、最適化問題の解が第１３図のように求められる。例え
ば、タスクｉをどのＰＥに割当てるかはタスク１行の中
の１が出力されたニューロン素子Ｎに対応するＰＥ番号
により決定される。したがって、図に示す如く、例えば
タスク１はＰＥ２に割当てられ、タスク２はＰＥＩに割
当てられる。このようにして全タスクがＰＨに割当てら
れることになる。

しかしながら、このようなニューラルネットを用いた従
来の最適タスク割当て方法では、ニューロン素子の出力
値のとり得る範囲を（０，１）とし、出力値が１に近い
ときに割当て、０に近いときに割当てないという方法を
とっていたため、ＰＨの数とタスクの数との積に等しい
数のニューロン素子を必要とし、ＰＥやタスクの数に対
してニューラルネットの規模が大きくなりすぎるという
問題があった。

また、従来の方法では、最適化の解が成る種の制約条件
、例えば１つのＰＨに割当てられるタスクの数は必ず１
つである等の制約条件を満たさなければならない場合に
は、この制約条件を全ての結合係数に反映させる必要が
ある。しかしニューラルネットの規模が大きくなると、
全ての制約条件を結合係数Ｗに反映することが非常に難
しくなり、結局制約条件を満たさない不当な解が得られ
てしまうという問題があった。

（発明が解決しようとする課題） 上記の如く、ニューラルネットを用いた従来の最適タス
ク割当て方法では、ニューラルネットの規模が大きべな
り過ぎること、及びニューラルネットの結合係数を決め
るのが困難で制約条件を満足しない不当な解が求められ
てしまうという問題があった。

本発明はＰＨの数に拘りなく小規模なニューラルネット
で構成でき、しかも不当な解を出力することのないタス
ク割当て装置を提供することを目的とする。

（課題を解決するための手段） 第１の発明に係るタスク割当て装置は、２つのＰＥに対
して複数のタスクを割当てるものであって、各タスクと
１対１に対応し、出力値が正の所定値と負の所定値との
間で変化する複数のニューロン素子、および前記タスク
相互の関係から決定される結合係数に応じて前記各ニュ
ーロン素子の出力を自己を除く他の全てのニューロン素
子の入力に結合する結合手段を備えたニューラルネット
と、この二二一うルネットを起動する手段と、この手段
によって起動された前記ニューラルネットが平衡状態に
達したときに、正の値を出力しているニューロン素子に
対応するタスクを一方の前記プロセッシングエレメント
に割当て、負の値を出力しているニューロン素子に対応
するタスクを他方の前記プロセッシングエレメントに割
当てる手段とを具備したことを特徴としている。

また、第２の発明に係るタスク割当て装置は、３つ以上
のＰＨに対して複数のタスクが割当てるものであって、
上記ニューラルネットに加え、ニューラルネットを所定
の回数だけ起動する手段と、この手段によって起動され
た前記ニューラルネットが平衡状態に達する度に、正の
値を出力しているニューロン素子と負の値を出力してい
るニューロン素子とを分類し、各ニューロン素子に対応
するタスクを当該ニューロン素子の最終的な分類結果に
対応したプロセッシングエレメントに割当てる割当て手
段と、前記ニューラルネットが平衡状態に達する度に前
記分類結果に基づいて前記結合係数を変更する結合係数
変更手段とを備えるようにした。

（作用） 第１の発明によれば、各ニューロン素子からは（−ａ、
ｂ）、但しくａ、ｂ＞０）の範囲の出力が得られ、その
出力値の符号によって割当てるＰＥが決定されるので、
各ニューロン素子の出力は必ずいずれかのＰＥの割当て
を特定し、又必ず評価に反映される。このため、ニュー
ロン素子の数はタスクの数だけで足りることになり、小
規模のニューラルネットで構成できる。又、各ニューロ
ン素子は、各タスクと１対１で対応しているので、１つ
のタスクが複数のＰＥに割当てられるようなことがなく
、そのような制約条件を結合係数に反映させる必要がな
くなる。このため、結合係数の設定が容易になるうえ、
従来のような不当な解が出力されることがない。

又、第２の発明によれば、複数のタスクの２分割を繰返
しながら各ステージで上述した２つのＰＥへの割当て処
理を実行し、２つのグループを分類していくことにより
最終的な分類結果が割当てらるＰＨの番号として求めら
れる。このため、第１の発明と同様の作用効果が得られ
る。更に、この発明によれば、分類の過程で、分類結果
にもとづいて結合係数が適宜変更されるため、状況に応
じて最適性の解を柔軟に変更することができる。

（実施例） 以下、図面を参照しながら本発明の実施例について説明
する。

第１図は本発明の一実施例に係るタスク割当て装置の構
成を示す図である。このタスク割当て装置２０は、２台
のＰＥＯ，ＰＥＩにｎ個のタスクを割当てるものであり
、割当てるべきタスクと１対１で対応する複数のニュー
ロン素子Ｎ１．Ｎ２゜Ｎ３．・・・、Ｎｎからなるニュ
ーラルネットを主体に構成されている。各ニューロン素
子Ｎ１の出力は、伝達路２１を介して他の全てのニュー
ロン素子Ｎｊ　　（ｊ＃ｉ）の入力に結合されている。

この結合の強さ（シナプス荷重）は、後に述べる結合係
数Ｗｌｊによって決定される。この結合係数Ｗｌｊが設
定された結合部２２とニューロン素子Ｎ１〜Ｎｎとでニ
ューラルネットが構成される。各ニューロン素子Ｎｌに
は、ニューラルネットを起動するための手段として、各
素子Ｎｉの初期値を与えるランダムジェネレータ２３か
らの出力が与えられている。各ニューロン素子の出力は
、所定の閾値関数φ（ｘ）を持った割当て装置２４の各
セル２５に入力されている。そして、これら各セル２５
の出力により割当てるＰＥの番号が求められる。

このタスク割当て装置２０は、第２図（ａ）に示すよう
にタスクを割当てる並列プロセッサシステム３０と別個
の装置として構成することも可能であるし、又、同図（
ｂ）に示すように並列プロセッサシステム３０の一部の
ＰＥを用いて構成することも可能である。特に前者の場
合には、ニューラルネットを複数の増幅器や抵抗のネッ
トワークで構成できる。

第３図に上述したニューラルネットの基本要素であるニ
ューロン素子Ｎｊとその入出力信号を示す。ニューロン
素子Ｎｊにはｎ−１個の入力信号Ｘ１．ｘ２　、　・、
ｘｎ−１が結合係数Ｗｌｊ、　Ｗ２ｊ・・・、　Ｗｎ−
１ｊでそれぞれ重み付けされて入力されている。ニュー
ロン素子Ｎｊの内部状態変数をｕｊとすると、ニューロ
ン素子Ｎｊの動作を示す方程式は、旧式（１）、（２）
で示したように、ｙｊ　　−ｆ　　（ｕｊ） で表わされる。

本装置ではニューロン素子Ｎｊの内部状態変数ｕｊと出
力信号ｙｊとの関係を示す関数ｆとして第４図に示すよ
うなシグモイド関数を用いる。この曲線は（−１，１）
の範囲で出力ｙｊが変化する微分可能な単調増加関数で
あり、（４）式のように示される。

ｙｊ　＝ｔ　ａｎｈ　（ｕｊ　）　　　　　　　−（４
）割当て装置２４は、平衡状態に達したニューラルネッ
ト２０のニューロン素子Ｎｉの出力信号ｙ＋を入力し、
この信号ｙｌに対して（５）式に示すような閾値処理を
行ない信号ｚｉを出力する。

・・・　（５） 次に結合係数ＷＩｊの決定方法について説明する。

結合係数Ｗｌｊはタスク間の関係を考慮した種々のパラ
メータにより決定可能であるが、ここでは−例として結
合係数Ｗｌｊを次のように定義する。

Ｗｉｊ＝　−（Ｓ　Ｉｊ　−ｋ　Ｔ　ｉｊ）　　　　　
　・・・（６）ただし、ｋは正の定数 ここでＳｌｊはタスク２とタスクｔｊとの並列性を示す
指標である。例を第５図に示す。タスクｔｌからタスク
６まで６つのタスクがあったとする。様々な初期条件を
与えて実行させた結果のタスク間の関係を示したもので
ある。点線内は並列に実行されたもの、矢印はタスク間
の通信量を表わしている。例えば、タスクｔｉとｔ４．
　タスクｔ２とｔ、とｔ７及びタスクｔ３とｔ６のよう
に、並列実行可能性が高いものには大きな値が与えられ
、例えばタスクｔｌとｔ２のように逐次的にしか実行さ
れない場合にはＳ　ｉｊ＝　０となる。また、Ｔｌｊは
タスクｔｉとタスクｔｊとの間の通信量を示す指標で、
例えば第５図におけるタスクｔ１とタスクｔ４とのよう
にタスク間に通信が存在しなければＴｉｊ−０，タスク
ｔ１とｔ２のように通信が存在すれば所定の値が与えら
れ、タスクｔ２とｔ４のように通信量が大きい場合には
大きな値が与えられる。もし、１回の通信で送られる情
報が一定であれば、このＴｌｊはタスクｔ１とｔｊとの
間の通信開度になる。

これらを例示すれば、次のようになる。

Ｓ　１４−　Ｓ　４１−１００　、　　Ｓ　１２−　Ｓ
　２１−１５Ｓ　２４−　Ｓ　４２−８０ Ｔ１４−Ｔ４１−０．Ｔ１２−Ｔ２１−１０Ｔ２４−　
Ｔ４２−　１　０　０　０ なお、以上の性質から明らかなように、Ｓｉｊ≧Ｏ、Ｓ
　ｉｊ　−Ｓ　ｊｌ、　　Ｓ　１１−０Ｔｉｊ≧０．Ｔ
ｉｊ−Ｓｊｉ、　　Ｔｉｔ−０である。

次にタスク割当ての最適解を決定するための評価関数Ｆ
について説明する。評価関数Ｆは、様々な視点から適宜
設定できるが、ここでは、負荷分散コストと通信コスト
の２つのコストを評価の対象とする。評価関数Ｆは次の
ように定義できる。

・・・　（７） 但し、ｋは正の定数であり、 ここで、Ｒ１は、 割当てる場合） 評価関数Ｆの第１項は、ＰＥに対する負荷分散コストを
示している。タスクｔ１とタスクＢとが同一のＰＨに割
当てられた場合には、ＰＨに対して負荷の分散が達成さ
れていないため、ペナルティＳｌｊが課せられる。また
、タスクｔｌとタスクｔｊとが異なるＰＨに割当てられ
た場合には、ＰＨに対する負荷は分散されるのでコスト
増としてはカウントされない。

評価関数Ｆめ第２項は、ＰＥに対する通信コストを示し
ている。タスクｔｌとタスクｔｊとが異なるＰＨに割当
てられた場合には、異なるＰＥ間における通信に時間が
かかるため、ペナルティＴｉｊが課せられ、コスト増と
してカウントされる。

また、タスクｔ１とタスクｔｊとが同じＰＨに割当てら
れた場合には、通信に時間がかからないためペナルティ
は課されない。なお、ｋは２つのコストのバランスをと
るためのものである。

最適タスク割当て問題の解は、この評価関数Ｆを極小に
するような解として求められる。ところで、いまニュー
ロン素子Ｎｌの出力ｙｔが十分に１に近い時には、タス
クｔｔをＰＥＩに割当て、ｙ＋が十分に−１に近い時に
はタスクｔｉをＰＥＯに割当てるものとすると、 （タスクＪ１をＰＥＩに割当てる場合）ｙｌ　’ｉｌ　
　→　Ｒ１−１ （タスクＪｌをＰＥＯに割当てる場合）ｙｉ！＝ｉ−１
→　Ｒ１−０ である。すると近似的に、 ・・・　（８） と表わせるから、これを（７）式の評価関数Ｆに代入し
て となる。上式の第３項は定数なので省略し、Ｗｉｊ−−
（Ｓ　Ｉｊ　−ｋ　Ｔ　ｉｊ）　　　　　　　　・・・
　（１０）とおくと、 となる。この式は、前述したホップフィールドのエネル
ギー関数を示しているので、ニューラルネットは、結局
、このＦを極小にするような解に収束する（　Ｊ、Ｊ、
Ｈｏｐｆ’１ｅｌｄ、Ｐｒｏｃ、Ｎａｔｌ、＾ｃａｄ、
　Ｓｃｌ。

ＵＳＡ８１．３０８８−３０９２（１９８４））。ホッ
プフィールドが示した原理をそのまま利用すると、与え
られた最適タスク割当て問題に対して（６）式でＷｌｊ
を定めると、（１１）式のエネルギー関数が定義できる
。

以上の本装置によれば、割当てるタスクの性質に応じて
各結合係数Ｗ１ｊを適当に設定し、ランダムジェネレー
タ２３にて各ニューロン素子Ｎ１に初期状態ｕｉを設定
すると、ニューラルネットは（１１）式を極小にするよ
うな解ｙ１に収束する。

（１１）式は最適タスク割当て問題の評価関数に定数項
を除いて等しいから、この評価関数の意味でも極小にな
っている。従って、かなり良好な解が求められる。なお
、各ニューロン素子Ｎ１の出力は実際にはｙｔ−±１に
はならないので、最終割当て装置２４での閾値処理によ
りＹｉの符号で行なう。

第６図は本発明の第２の実施例を示す図で、第１図と重
複する部分には同一符号を付しである。

このタスク割当て装置４０はｍ台のＰＥにｎ個のタスク
を割当てるもので、割当て装置４１の構成が第１図のも
のとは異なると共に、新たに結合係数変更装置４２が付
加されている。

割当て装置４１は、第７図に示すように、ニューロン素
子Ｎｊの出力ｙｊを前述した関数φ（ｙ　Ｄで閾値処理
して１ビツトとのとットデータＢｊを出力する判定回路
４３と、この判定回路４３の出力Ｂｊを１ビツトずつシ
フトインして記憶するシフトレジスタ４４とにより構成
されている。また、結合係数変更装置４２はニューラル
ネットの複数回の起動の過程で結合係数Ｗｉｊを適応的
に変更する。

この装置では、ＰＥの台数ｍに対して、ランダムジェネ
レータ２３は、ニューラルネットを［Ｌｏｇ　２　ｍ］
　　（ただし［ｘ］はＸ以上の最小の整数）回起動する
。例えば、１０台のＰＨに割当てる時は４回処理が繰返
される。！　＝　［Ｌｏｇ　２　ｍ１回処理を繰返すと
、ニューロン素子Ｎｊに対応するシフトレジスタ４４に
は、ノビットのデータＺｊが求められる。このデータＺ
ｊがタスクｔｊを割当てるＰＥ番号（バイナリデータ）
Ｚ　ｊ−Ｂ　ＩＪＸ　２　　　＋　Ｂ　２ｊｘ　２’−
２＋、　　　Ｎ−１ ・・・＋Ｂ　　　ｊＸ２’＋Ｂｌ）ｊ Ｊ−１ となる。

この装置によれば、ノ回の起動の過程でニューラルネッ
トが平衡状態に達する度に、ｙｉ　！；１を出力してい
るニューロン素子Ｎｌと、ｙｌζ−１を出力しているニ
ューロン素子Ｎｌとを分類し、最終的な分類結果として
ＰＥ番号が求められる。

ところで、ノ回の繰返しの過程のある段階で、判定回路
４３の出力Ｂ１とＢｊとが異なる値となった場合、最終
的に得られるデータＺｉとＺｊとは必ず異るものとなり
、結局、タスク２とｔｊとは同一のＰＨに割当てられる
ことはない。従って、この段階でタスクｔ１とｔｊの負
荷分散は達成されたことになるので、この場合には、評
価関数Ｆから負荷分散コストを削除する必要がある。ま
た、これに伴って負荷分散に対する過小評価されてしま
うことがないようにするためにＲｉ−Ｒｊとなっている
結合係数Ｓｌｊを２倍しておく。従って、結合係数変更
装置４２は、ニューラルネットが平衡状態に達する度に
、結合係数Ｗｌｊを次のように変更する。

Ｗ！ｊ’　　−ｋＴｉｊ　　　　　　　（但し、Ｂ１　
≠Ｂｊ）Ｗｉｊ’　−一（ｇ　Ｓ　ｉｊ　−ｋ　Ｔｉｊ
）（但し、Ｂｉ　＝Ｂｊ　、ｇ＞１の定数）ここに示し
た方法は、多数のＰＥへの割当て問題を、幾つかの２組
のＰＥ群への割当て問題へ分解しながら、なおかつ通信
コストを残す形で全体の問題として評価をしながら解く
という方法である。

以上の処理の流れを第８図に示す。

各タスク間の並列性および通信量に基づき、結合係数Ｗ
を初期設定し、ニューラルネットの起動回数ノを１とす
る（Ｓｔ、１）。ニューラルネットを起動しくＳｔ、２
）、平衡状態に達したら、得られたビットデータＢｌを
シフトレジスタに格納する（Ｓｔ、３）。求められた結
果Ｂ１に基づき結合係数Ｗｉｊを変更する（Ｓｔ、７）
。これをノ＞Ｌｏｇ２ｍとなるまで繰返しくＳｔ、４゜
Ｓｔ、５）、最終的に求められたデータＺｊをＰＥ番号
として出力する（Ｓｔ、６）。

なお、ｍが２のべき乗でない場合には、２’　＞ｍとな
るので、ｍ≦Ｚｊ＜２’の範囲のデータＺｊを出力した
タスクは、適当に存在するＰＥに割当てるものとする。

この場合、例えばランダムに割当てる。最も割当てタス
クの少ないＰＥに割当てる等の方法が考えられる。

以上のように、従来の方法では、タスク数をｎ。

ＰＥの台数をｍとしたとき、ｎｘｍ個のニューロン素子
と（ｎＸｍ）２個の結合係数によってニューラルネット
を構成する必要があったが、本装置では、ＰＥの台数ｍ
に拘らず、ｎ個のニューロン素子とｎ２個の結合係数で
済み、ニューラルネットの規模を大幅に縮小できる。

なお、本発明は上述した実施例に限定されるものではな
い。例えば、上記実施例では、ニューロン素子の出力値
を（−１，１）としたが、この範囲は０を含む区間に設
定することが本質である。

従って、一般には出力値が（−ａ、ｂ）、（但し、ａ、
ｂ＞０）の範囲で変位するものであればよい。

結合係数は、全結合を前提に記載したが、問題によって
はもっと疎な結合であってもよい。この場合には、ニュ
ーロン素子の数は変化しないがニューラルネットの規模
は更に小さくなる。実際の応用では、多くのＳｉｊ、Ｔ
ｌｊが０になることが多いので、この可能性は十分ある
。但し、この場合には各ニューロン素子はどのニューロ
ン素子と結合しているのかの情報を付加しておく必要が
ある。

結合係数の変更方法には、他にも様々なものがある。例
えば、繰返し数が多くなるにつれて通信コストを重視し
たタスク割当てにしたければ、定数にの値を大きくする
方法がある。ｋは通信コストと負荷分散コストとのバラ
ンスをとるためのものであるから、この値を変更するだ
けで全体の割当て方法の性質を修正することができる。

ＰＥが処理できるタスク数に制限がある場合には、この
ｋの値を小さくするかあるいはタスクが集中しているグ
ループの間のｓｌｊを大きくスルコとによって、負荷分
散の評価を高め、制限内のタスクしか含まれないように
割当てることが可能である。このほか本発明の要旨を逸
脱しない範囲で種々変形実施可能であるのは勿論である
。

Ｅ発明の効果コ 以上に述べたように第１の発明によれば、各ニューロン
素子から正負の出力が得られ、それぞれがＰＨの割当て
を特定しているので、タスクの数に応じたニューロン素
子と結合係数とを設ければよく、ニューラルネットの規
模を縮小でき、不当な解が出力されることもない。

又、第２の発明によれば複数のＰＥを２つに分散しなが
ら繰返し、第１の発明の処理を適用するので、第１の発
明と同様の効果を複数のＰＥへの割当ての際にも得るこ
とができる。又、この発明によれば、分類結果に応じて
結合係数が変化するので極めて最適な解が得られるとい
う効果がある。

【図面の簡単な説明】

第１図〜第５図は本発明の第１の実施例を示す図で、第
１図はタスク割当て装置の構成を示す図、第２図はタス
ク割当て装置と並列プロセッサシステムとの関係を示す
図、第３図はニューロン素子の入出力を示す図、第４図
はニューロン素子の内部状態とニューロン素子の出力値
との関係を示す図、第５図はタスク間の関係を示す図、
第６図〜第８図は本発明の第２の実施例を示す図で、第
６図はタスク割当て装置の構成を示す図、第７図は割当
て装置の構成を示す図、第８図はタスク割当て装置の処
理手順を示すフロー図、第９図〜第１３図は従来のニュ
ーラルネットを説明するための図で、第９図はニューラ
ルネットの構成を示す図、第１０図はニューロン素子の
入出力を示す図、第１１図はニューロン素子の内部状態
とニューロン素子の出力値との関係を示す図、第１２図
はニューラルネットのエネルギー関数を示す図、第１３
図は最適タスク割当て問題を解いたときの各ニューロン
素子の出力値を示す図である。 １．２１・・・伝達路、２，２２・・・結合部、１０・
・・ニューラルネット、２０．４０・・・タスク割当て
装置、２３・・・ランダム・ジェネレータ、２４．４１
・・・割当て装置、４２・・・結合係数変更装置、４３
・・・判定回路、４４・・・シフトレジスタ、Ｎ１〜Ｎ
ｎ・・・ニューロン素子。 出願人代理人　弁理士　鈴江武彦 第４図 第１図 （ａ） （ｂ） 第２図 第５図 第１０図 一 第６ 図 第９ 図 ｊ 第１２図 第１３図

Claims (2)

【特許請求の範囲】
1. （１）並列処理システムを構成する２つのプロセッシン
   グエレメントに対して複数のタスクを割当てるタスク割
   当て装置において、 各タスクと１対１に対応し、出力値が正の所定値と負の
   所定値との間で変化する複数のニューロン素子、および
   前記タスク相互の関係から決定される結合係数に応じて
   前記各ニューロン素子の出力を自己を除く他の全てのニ
   ューロン素子の入力に結合する結合手段を備えたニュー
   ラルネットと、このニューラルネットを起動する手段と
   、 この手段によって起動された前記ニューラルネットが平
   衡状態に達したときに、正の値を出力しているニューロ
   ン素子に対応するタスクを一方の前記プロセッシングエ
   レメントに割当て、負の値を出力しているニューロン素
   子に対応するタスクを他方の前記プロセッシングエレメ
   ントに割当てる手段とを具備したことを特徴とするタス
   ク割当て装置。
2. （２）並列処理システムを構成する３つ以上のプロセッ
   シングエレメントに対して複数のタスクを割当てるタス
   ク割当て装置において、 各タスクと１対１に対応し、出力値が正の所定値と負の
   所定値との間で変化する複数のニューロン素子、および
   前記タスク相互の関係から決定される結合係数に応じて
   前記各ニューロン素子の出力を自己を除く他の全てのニ
   ューロン素子の入力に結合する結合手段を備えたニュー
   ラルネットと、このニューラルネットを所定の回数だけ
   起動する手段と、 この手段によって起動された前記ニューラルネットが平
   衡状態に達する度に、正の値を出力しているニューロン
   素子と負の値を出力しているニューロン素子とを分類し
   、各ニューロン素子に対応するタスクを当該ニューロン
   素子の最終的な分類結果に対応したプロセッシングエレ
   メントに割当てる割当て手段と、 前記ニューラルネットが平衡状態に達する度に前記分類
   結果に基づいて前記結合係数を変更する結合係数変更手
   段とを具備したことを特徴とするタスク割当て装置。