(57)【特許請求の範囲】
【請求項１】
生産ラインで収集するデータに対して演算処理（５００）を行う複数の演算ノード（２００）とネットワークを介して接続され、かつ、複数の前記演算ノード（２００）へ前記演算処理（５００）を割り当てる分散配置装置であり、
複数の前記演算ノード（２００）間のネットワーク構成と、それぞれの前記演算ノード（２００）に割り当てられる演算処理（５００）の名称と、それぞれの前記演算処理（５００）が実行される実行周期（７００）と、複数の前記演算処理（５００）の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理（５００）間の実行順序を規定する先行制約（６００）と、複数の前記演算処理（５００）間のデータ通信量と、それぞれの前記演算処理（５００）の実行時間とが入力される入力部（１０１）と、
前記入力部（１０１）に入力されたそれぞれの情報に基づいて制約条件式を作成する作成部（１０２）と、
複数の前記演算ノード（２００）間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノード（２００）への前記演算処理（５００）の割り当ておよびスケジュールを導出する導出部（１０３）と、
前記演算処理（５００）の割り当ておよび前記スケジュールをそれぞれの前記演算ノード（２００）へ分配する分配部（１０４）とを備え、
前記作成部（１０２）は、複数の前記演算処理（５００）間の前記先行制約（６００）に基づいて、それぞれの前記演算処理（５００）を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理（５００）の前記実行時間および複数の前記演算処理（５００）間の前記データ通信量に基づいて、前記デッドラインを満たす前記制約条件式を作成し、
前記作成部（１０２）は、前記先行制約（６００）に基づいて順序づけられたそれぞれの前記演算処理（５００）の前記実行周期（７００）に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノード（２００）には、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理（５００）を割り当てない前記制約条件式を作成する、
分散配置装置。
【請求項２】
前記入力部（１０１）には、複数の前記演算ノード（２００）間の通信速度がさらに入力され、
前記作成部（１０２）は、複数の前記演算ノード（２００）間で同時に複数のデータ通信が発生する場合、複数の前記演算ノード（２００）間の前記通信速度を同時に発生する前記データ通信の数で等分して前記制約条件式を作成する、
請求項１に記載の分散配置装置。
【請求項３】
前記作成部（１０２）は、前記先行制約（６００）に基づいて順序づけられたそれぞれの前記演算処理（５００）の前記実行周期（７００）が異なる場合、複数の前記実行周期（７００）の最小公倍数を前記全体周期とし、当該全体周期内でそれぞれの前記演算処理（５００）をそれぞれの前記実行周期（７００）に対応して繰り返し実行させる制約条件式を作成する、
請求項１または請求項２に記載の分散配置装置。
【請求項４】
生産ラインで収集するデータに対して演算処理（５００）を行う複数の演算ノード（２００）とネットワークを介して接続され、かつ、複数の前記演算ノード（２００）へ前記演算処理（５００）を割り当てる分散配置装置（１００）と、
前記分散配置装置（１００）に接続されるネットワーク構成とを備え、
前記分散配置装置（１００）は、
複数の前記演算ノード（２００）間のネットワーク構成と、それぞれの前記演算ノード（２００）に割り当てられる演算処理（５００）の名称と、それぞれの前記演算処理（５００）が実行される実行周期（７００）と、複数の前記演算処理（５００）の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理（５００）間の実行順序を規定する先行制約（６００）と、複数の前記演算処理（５００）間のデータ通信量と、それぞれの前記演算処理（５００）の実行時間とが入力される入力部（１０１）と、
前記入力部（１０１）に入力されたそれぞれの情報に基づいて制約条件式を作成する作成部（１０２）と、
複数の前記演算ノード（２００）間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノード（２００）への前記演算処理（５００）の割り当ておよびスケジュールを導出する導出部（１０３）と、
前記演算処理（５００）の割り当ておよび前記スケジュールをそれぞれの前記演算ノード（２００）へ分配する分配部（１０４）とを備え、
前記作成部（１０２）は、複数の前記演算処理（５００）間の前記先行制約（６００）に基づいて、それぞれの前記演算処理（５００）を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理（５００）の前記実行時間および複数の前記演算処理（５００）間の前記データ通信量に基づいて、前記デッドラインを満たす前記制約条件式を作成し、
前記作成部（１０２）は、前記先行制約（６００）に基づいて順序づけられたそれぞれの前記演算処理（５００）の前記実行周期（７００）に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノード（２００）には、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理（５００）を割り当てない前記制約条件式を作成し、
前記ネットワーク構成は、
前記演算処理（５００）を行う複数の前記演算ノード（２００）と、
複数の前記演算ノード（２００）間を接続するネットワークスイッチ（３００）とを備える、
分散配置システム。
【請求項５】
ネットワークを介して接続され、生産ラインで収集するデータに対して演算処理（５００）を行う複数の演算ノード（２００）へ、前記演算処理（５００）を割り当てる分散配置方法であり、
複数の前記演算ノード（２００）間のネットワーク構成と、それぞれの前記演算ノード（２００）に割り当てられる演算処理（５００）の名称と、それぞれの前記演算処理（５００）が実行される実行周期（７００）と、複数の前記演算処理（５００）の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理（５００）間の実行順序を規定する先行制約（６００）と、複数の前記演算処理（５００）間のデータ通信量と、それぞれの前記演算処理（５００）の実行時間とを入力し、
入力されたそれぞれの情報に基づいて制約条件式を作成し、
複数の前記演算ノード（２００）間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノード（２００）への前記演算処理（５００）の割り当ておよびスケジュールを導出し、
前記演算処理（５００）の割り当ておよび前記スケジュールをそれぞれの前記演算ノード（２００）へ分配し、
前記制約条件式の作成は、複数の前記演算処理（５００）間の前記先行制約（６００）に基づいて、それぞれの前記演算処理（５００）を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理（５００）の前記実行時間および複数の前記演算処理（５００）間の前記データ通信量に基づいて、前記デッドラインを満たすようになされ、
前記制約条件式の作成は、前記先行制約（６００）に基づいて順序づけられたそれぞれの前記演算処理（５００）の前記実行周期（７００）に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノード（２００）には、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理（５００）を割り当てないようになされる、
分散配置方法。
【請求項６】
複数の前記演算ノード（２００）間の通信速度をさらに入力し、
前記制約条件式の作成は、複数の前記演算ノード（２００）間で同時に複数のデータ通信が発生する場合、複数の前記演算ノード（２００）間の前記通信速度を同時に発生する前記データ通信の数で等分してなされる、
請求項５に記載の分散配置方法。
【請求項７】
前記制約条件式の作成は、前記先行制約（６００）に基づいて順序づけられたそれぞれの前記演算処理（５００）の前記実行周期（７００）が異なる場合、複数の前記実行周期（７００）の最小公倍数を前記全体周期とし、当該全体周期内でそれぞれの前記演算処理（５００）をそれぞれの前記実行周期（７００）に対応して繰り返し実行させるようになされる、
請求項５または請求項６に記載の分散配置方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願明細書に開示される技術は、たとえば、複数の演算ノードへ演算処理を割り当てる技術に関するものである。
【背景技術】
【０００２】
近年、ｆａｃｔｏｒｙ  ａｕｔｏｍａｔｉｏｎ（ＦＡ）分野などにおいて、センシングデータまたは稼働ログなどのデータを周期的に取得し、クラウドサーバーなどに当該データを集約した後、当該データの加工および分析を行うことによって、制御機器の故障予知または生産性の向上を図ることが行われている。なお、このデータの収集周期はデータごとに異なる場合がある。【０００３】
このように、データを単一のサーバーに集約すると、サーバーの処理負荷が増大するとともに、サーバーのアクセス負荷が増大してサーバー周辺のネットワークが逼迫してしまう。サーバー周辺のネットワークの逼迫によって、データ分析が所望の時間、すなわち、デッドライン内に完了しないという問題が生じる場合がある。【０００４】
このため、データの加工および分析に関する演算処理を、ネットワークに含まれる複数の演算ノードに分散して割り当てる、すなわち、分散配置する場合がある。【０００５】
演算処理を演算ノードに割り当てる方法として、たとえば、事前に演算処理の開始から終了までの要求時間であるデッドライン、演算処理が実行される周期、演算量または通信量などを設定し、割り当て前にそれぞれの演算ノードへ問い合わせを行うことによって、デッドラインを満たす割り当てを実行する方法がある（たとえば、特許文献１を参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１０−２７０６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
複数の演算処理間では、ある演算処理によって加工されたデータに対して他の演算処理がデータ分析を行うなどの、先行制約の関係を有する場合がある。【０００８】
しかしながら、たとえば、特許文献１は、先行制約で関係づけられた演算処理群に対する考慮はなされていない。そのため、個々の演算処理に対して、適切なデッドラインをそれぞれ設定する必要がある。このデッドラインの設定は、先行制約、データ通信量および処理の実行時間を考慮しなければならず、人手で実施することは困難である。【０００９】
また、ＦＡ分野においては、周期的にデータを収集することによって、故障予知などのデータ分析を行うアプリケーションが用いられている。このような故障予知などのデータ分析結果の出力には、データ収集の周期よりも長い時間をかけてもよい場合が多い。【００１０】
しかしながら、たとえば、特許文献１は、演算処理ごとに周期またはデッドラインのいずれかのみを設定するため、デッドラインを周期以上の長さに設定することなどは想定することができない。そのため、上記の処理のようにデータ収集の周期よりも長い時間をかけて実行されてもよい演算処理に対して、必要以上のデッドラインを設けることとなってしまう場合があった。【００１１】
本願明細書に開示される技術は、以上に記載されたような問題を解決するためになされたものであり、演算処理の周期よりもデッドラインが長い場合であっても、複数の演算処理間の先行制約を考慮しつつ、複数の演算ノードへ演算処理をそれぞれ割り当てる技術を提供することを目的とするものである。
【課題を解決するための手段】
【００１２】
本願明細書に開示される技術の第１の態様は、生産ラインで収集するデータに対して演算処理を行う複数の演算ノードとネットワークを介して接続され、かつ、複数の前記演算ノードへ前記演算処理を割り当てる分散配置装置であり、複数の前記演算ノード間のネットワーク構成と、それぞれの前記演算ノードに割り当てられる演算処理の名称と、それぞれの前記演算処理が実行される実行周期と、複数の前記演算処理の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理間の実行順序を規定する先行制約と、複数の前記演算処理間のデータ通信量と、それぞれの前記演算処理の実行時間とが入力される入力部と、前記入力部に入力されたそれぞれの情報に基づいて制約条件式を作成する作成部と、複数の前記演算ノード間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノードへの前記演算処理の割り当ておよびスケジュールを導出する導出部と、前記演算処理の割り当ておよび前記スケジュールをそれぞれの前記演算ノードへ分配する分配部とを備え、前記作成部は、複数の前記演算処理間の前記先行制約に基づいて、それぞれの前記演算処理を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理の前記実行時間および複数の前記演算処理間の前記データ通信量に基づいて、前記デッドラインを満たす前記制約条件式を作成し、前記作成部は、前記先行制約に基づいて順序づけられたそれぞれの前記演算処理の前記実行周期に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノードには、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理を割り当てない前記制約条件式を作成する。【００１３】
また、本願明細書に開示される技術の第２の態様は、生産ラインで収集するデータに対して演算処理を行う複数の演算ノードとネットワークを介して接続され、かつ、複数の前記演算ノードへ前記演算処理を割り当てる分散配置装置と、前記分散配置装置に接続されるネットワーク構成とを備え、前記分散配置装置は、複数の前記演算ノード間のネットワーク構成と、それぞれの前記演算ノードに割り当てられる演算処理の名称と、それぞれの前記演算処理が実行される実行周期と、複数の前記演算処理の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理間の実行順序を規定する先行制約と、複数の前記演算処理間のデータ通信量と、それぞれの前記演算処理の実行時間とが入力される入力部と、前記入力部に入力されたそれぞれの情報に基づいて制約条件式を作成する作成部と、複数の前記演算ノード間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノードへの前記演算処理の割り当ておよびスケジュールを導出する導出部と、前記演算処理の割り当ておよび前記スケジュールをそれぞれの前記演算ノードへ分配する分配部とを備え、前記作成部は、複数の前記演算処理間の前記先行制約に基づいて、それぞれの前記演算処理を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理の前記実行時間および複数の前記演算処理間の前記データ通信量に基づいて、前記デッドラインを満たす前記制約条件式を作成し、前記作成部は、前記先行制約に基づいて順序づけられたそれぞれの前記演算処理の前記実行周期に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノードには、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理を割り当てない前記制約条件式を作成し、前記ネットワーク構成は、前記演算処理を行う複数の前記演算ノードと、複数の前記演算ノード間を接続するネットワークスイッチとを備える。【００１４】
また、本願明細書に開示される技術の第３の態様は、ネットワークを介して接続され、生産ラインで収集するデータに対して演算処理を行う複数の演算ノードへ、前記演算処理を割り当てる分散配置方法であり、複数の前記演算ノード間のネットワーク構成と、それぞれの前記演算ノードに割り当てられる演算処理の名称と、それぞれの前記演算処理が実行される実行周期と、複数の前記演算処理の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理間の実行順序を規定する先行制約と、複数の前記演算処理間のデータ通信量と、それぞれの前記演算処理の実行時間とを入力し、入力されたそれぞれの情報に基づいて制約条件式を作成し、複数の前記演算ノード間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノードへの前記演算処理の割り当ておよびスケジュールを導出し、前記演算処理の割り当ておよび前記スケジュールをそれぞれの前記演算ノードへ分配し、前記制約条件式の作成は、複数の前記演算処理間の前記先行制約に基づいて、それぞれの前記演算処理を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理の前記実行時間および複数の前記演算処理間の前記データ通信量に基づいて、前記デッドラインを満たすようになされ、前記制約条件式の作成は、前記先行制約に基づいて順序づけられたそれぞれの前記演算処理の前記実行周期に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノードには、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理を割り当てないようになされる。
【発明の効果】
【００１５】
本願明細書に開示される技術の第１の態様は、生産ラインで収集するデータに対して演算処理を行う複数の演算ノードとネットワークを介して接続され、かつ、複数の前記演算ノードへ前記演算処理を割り当てる分散配置装置であり、複数の前記演算ノード間のネットワーク構成と、それぞれの前記演算ノードに割り当てられる演算処理の名称と、それぞれの前記演算処理が実行される実行周期と、複数の前記演算処理の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理間の実行順序を規定する先行制約と、複数の前記演算処理間のデータ通信量と、それぞれの前記演算処理の実行時間とが入力される入力部と、前記入力部に入力されたそれぞれの情報に基づいて制約条件式を作成する作成部と、複数の前記演算ノード間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノードへの前記演算処理の割り当ておよびスケジュールを導出する導出部と、前記演算処理の割り当ておよび前記スケジュールをそれぞれの前記演算ノードへ分配する分配部とを備え、前記作成部は、複数の前記演算処理間の前記先行制約に基づいて、それぞれの前記演算処理を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理の前記実行時間および複数の前記演算処理間の前記データ通信量に基づいて、前記デッドラインを満たす前記制約条件式を作成し、前記作成部は、前記先行制約に基づいて順序づけられたそれぞれの前記演算処理の前記実行周期に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノードには、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理を割り当てない前記制約条件式を作成するものである。このような構成によれば、複数の演算処理間の先行制約に基づいて、それぞれの演算処理を行う順序を決定され、当該順序に基づいて実行される複数の演算処理が全体としてデッドラインを満たすように、制約条件式が作成される。したがって、それぞれの演算処理に対して適切なデッドラインをそれぞれ設定する必要がない。また、先行制約に基づいて順序づけられた複数の演算処理の全体周期よりもデッドラインが長い場合であっても、超過演算処理を割り当てられる演算ノードには、次の全体周期において、超過演算処理の実行中に他の演算処理を割り当てないように制約条件式が作成される。したがって、実行周期に関連して必要以上にデッドラインを短く設定することがない。【００１６】
また、本願明細書に開示される技術の第２の態様は、生産ラインで収集するデータに対して演算処理を行う複数の演算ノードとネットワークを介して接続され、かつ、複数の前記演算ノードへ前記演算処理を割り当てる分散配置装置と、前記分散配置装置に接続されるネットワーク構成とを備え、前記分散配置装置は、複数の前記演算ノード間のネットワーク構成と、それぞれの前記演算ノードに割り当てられる演算処理の名称と、それぞれの前記演算処理が実行される実行周期と、複数の前記演算処理の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理間の実行順序を規定する先行制約と、複数の前記演算処理間のデータ通信量と、それぞれの前記演算処理の実行時間とが入力される入力部と、前記入力部に入力されたそれぞれの情報に基づいて制約条件式を作成する作成部と、複数の前記演算ノード間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノードへの前記演算処理の割り当ておよびスケジュールを導出する導出部と、前記演算処理の割り当ておよび前記スケジュールをそれぞれの前記演算ノードへ分配する分配部とを備え、前記作成部は、複数の前記演算処理間の前記先行制約に基づいて、それぞれの前記演算処理を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理の前記実行時間および複数の前記演算処理間の前記データ通信量に基づいて、前記デッドラインを満たす前記制約条件式を作成し、前記作成部は、前記先行制約に基づいて順序づけられたそれぞれの前記演算処理の前記実行周期に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノードには、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理を割り当てない前記制約条件式を作成し、前記ネットワーク構成は、前記演算処理を行う複数の前記演算ノードと、複数の前記演算ノード間を接続するネットワークスイッチとを備えるものである。このような構成によれば、複数の演算処理間の先行制約に基づいて、それぞれの演算処理を行う順序を決定され、当該順序に基づいて実行される複数の演算処理が全体としてデッドラインを満たすように、制約条件式が作成される。したがって、それぞれの演算処理に対して適切なデッドラインをそれぞれ設定する必要がない。また、先行制約に基づいて順序づけられた複数の演算処理の全体周期よりもデッドラインが長い場合であっても、超過演算処理を割り当てられる演算ノードには、次の全体周期において、超過演算処理の実行中に他の演算処理を割り当てないように制約条件式が作成される。したがって、実行周期に関連して必要以上にデッドラインを短く設定することがない。【００１７】
また、本願明細書に開示される技術の第３の態様は、ネットワークを介して接続され、生産ラインで収集するデータに対して演算処理を行う複数の演算ノードへ、前記演算処理を割り当てる分散配置方法であり、複数の前記演算ノード間のネットワーク構成と、それぞれの前記演算ノードに割り当てられる演算処理の名称と、それぞれの前記演算処理が実行される実行周期と、複数の前記演算処理の開始から終了までの要求時間であるデッドラインと、複数の前記演算処理間の実行順序を規定する先行制約と、複数の前記演算処理間のデータ通信量と、それぞれの前記演算処理の実行時間とを入力し、入力されたそれぞれの情報に基づいて制約条件式を作成し、複数の前記演算ノード間の前記ネットワーク構成を参照しつつ、前記制約条件式を満たすそれぞれの前記演算ノードへの前記演算処理の割り当ておよびスケジュールを導出し、前記演算処理の割り当ておよび前記スケジュールをそれぞれの前記演算ノードへ分配し、前記制約条件式の作成は、複数の前記演算処理間の前記先行制約に基づいて、それぞれの前記演算処理を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの前記演算処理の前記実行時間および複数の前記演算処理間の前記データ通信量に基づいて、前記デッドラインを満たすようになされ、前記制約条件式の作成は、前記先行制約に基づいて順序づけられたそれぞれの前記演算処理の前記実行周期に基づく全体周期を算出し、前記全体周期よりも前記デッドラインが長い場合、前記全体周期を超過して実行される超過演算処理を割り当てられる前記演算ノードには、次の前記全体周期において、前記超過演算処理の実行中に他の前記演算処理を割り当てないようになされる。このような構成によれば、先行制約に基づいて実行される複数の演算処理が全体としてデッドラインを満たすように、制約条件式が作成される。また、複数の演算処理の全体周期よりもデッドラインが長い場合であっても、超過演算処理を割り当てられる演算ノードには、次の全体周期において、超過演算処理の実行中に他の演算処理を割り当てないように制約条件式が作成される。したがって、それぞれの演算処理に対して適切なデッドラインをそれぞれ設定する必要がなく、また、実行周期に関連して必要以上にデッドラインを短く設定することがない。【００１８】
本願明細書に開示される技術に関する目的と、特徴と、局面と、利点とは、以下に示される詳細な説明と添付図面とによって、さらに明白となる。
【図面の簡単な説明】
【００１９】
【図１】実施の形態に関する、分散配置システムの構成を機能的に例示する図である。
【図２】実施の形態に関する、分散配置装置の内部構成を概略的に例示する図である。
【図３】実施の形態に関する、演算ノードの内部構成を概略的に例示する図である。
【図４】実施の形態に関する、演算ノードと、ネットワークスイッチと、通信経路との関係を示すネットワーク構成を例示する図である。
【図５】実施の形態に関する、演算処理間の先行制約に関するモデル記述に例示する図である。
【図６】実施の形態に関する、複数の演算処理のデッドラインを概念的に例示する図である。
【図７】実施の形態に関する、演算処理間のデータ通信量を例示する図である。
【図８】実施の形態に関する、演算処理の実行時間を例示する図である。
【図９】実施の形態に関する、演算処理を演算ノードに割り当てた場合の、スケジュールを例示する図である。
【図１０】実施の形態に関する、演算ノードと、ネットワークスイッチと、通信経路との関係を示すネットワーク構成を例示する図である。
【図１１】図４に例示されたネットワーク構成に関する最短通信経路を例示する図である。
【図１２】実施の形態に関する、ネットワーク構成を例示する図である。
【図１３】図１２に例示されるネットワーク構成に対し、図５に例示された演算処理を割り当てた結果を例示する図である。
【図１４】図１３に例示された割り当て結果に、先行制約に基づいて、それぞれの演算処理間のデータ通信の開始時刻と終了時刻とが追記された図である。
【図１５】周期３０ｍｓｅｃで実行される演算処理、周期２０ｍｓｅｃで実行される演算処理および演算処理間の先行制約に関するモデル記述に例示する図である。
【図１６】図１５に例示されたモデル記述に対応する、演算処理のデッドラインを概念的に例示する図である。
【図１７】図１５に例示されたモデル記述に対応する、演算処理のデッドラインを概念的に例示する図である。
【発明を実施するための形態】
【００２０】
以下、添付される図面を参照しながら実施の形態について説明する。
【００２１】
なお、図面は概略的に示されるものであり、説明の便宜のため、適宜、構成の省略、または、構成の簡略化がなされるものである。また、異なる図面にそれぞれ示される構成などの大きさおよび位置の相互関係は、必ずしも正確に記載されるものではなく、適宜変更され得るものである。
【００２２】
また、以下に示される説明では、同様の構成要素には同じ符号を付して図示し、それらの名称と機能とについても同様のものとする。したがって、それらについての詳細な説明を、重複を避けるために省略する場合がある。
【００２３】
＜第１の実施の形態＞
以下、本実施の形態に関する分散配置装置、分散配置システム、および、分散配置方法について説明する。
【００２４】
＜分散配置装置の構成について＞
図１は、本実施の形態に関する分散配置システムの構成を機能的に例示する図である。図１に例示されるように、分散配置システムにおける分散配置装置１００は、通信経路４００を介して複数の演算ノード２００および複数のネットワークスイッチ３００と接続される。ここで、演算ノード２００は、主に生産ラインで収集するデータに対して演算処理を行うものである。また、分散配置装置１００は、モデル入力部１０１と、定式化部１０２と、解導出部１０３と、分配部１０４とを備える。
【００２５】
ネットワークスイッチ３００は、分散配置装置１００、演算ノード２００および他のネットワークスイッチ３００と、通信経路４００を介して接続される。また、ネットワークスイッチ３００は、データの中継およびデータの転送を行う手段を備える。
【００２６】
モデル入力部１０１は、演算ノード２００のネットワーク構成と、演算ノード２００で実行させる演算処理とを含むモデル記述を、ユーザーが入力する手段を備える。
【００２７】
定式化部１０２は、モデル入力部１０１に入力されたモデル記述から制約条件式へ定式化を行う、すなわち、制約条件式を作成する手段を備える。
【００２８】
解導出部１０３は、複数の演算ノード２００間のネットワーク構成を参照しつつ、制約条件式を満たすそれぞれの演算処理の演算ノード２００への割り当てと、それぞれの演算処理を行うタイミングを示すスケジュールとを解として導出する手段を備える。
【００２９】
解導出部１０３は、導出された複数の解の中から、ユーザーが指定する目的関数を用いて最適な解を選択する手段を備える。解導出部１０３は、導出された解が１つである場合には、当該解を最適な解として選択する。
【００３０】
分配部１０４は、解導出部１０３が導出した演算処理の割り当てとスケジュールとを演算ノード２００へ配信する手段を備える。
【００３１】
図２は、分散配置装置１００の内部構成を概略的に例示する図である。図２に例示されるように、分散配置装置１００は、出力部１１１と、入力部１１２と、中央演算処理装置（ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ、すなわち、ＣＰＵ）１１３と、メモリ１１４と、通信デバイス１１５とを備える。
【００３２】
出力部１１１は、ユーザーが入力したモデル記述に基づく制約条件式を満たす、演算処理の割り当ておよびスケジュール結果を表示する。入力部１１２は、ユーザーがモデル記述を入力する手段を備える。
【００３３】
ＣＰＵ１１３は、モデル記述から制約条件式への定式化の実行と、制約条件式を満たす演算処理の演算ノード２００への割り当ておよびスケジューリングの実行とを行う。さらに、ＣＰＵ１１３は、導出した解の中から、ユーザーが指定する目的関数を用いて最適な解を選択する。
【００３４】
メモリ１１４は、分散配置装置１００の実行プログラムを格納する。通信デバイス１１５は、演算ノード２００へ、演算処理の割り当てとスケジュールとを配信する。
【００３５】
図３は、演算ノード２００の内部構成を概略的に例示する図である。図３に例示されるように、演算ノード２００は、ＣＰＵ２１１と、メモリ２１２と、通信デバイス２１３とを備える。
【００３６】
ＣＰＵ２１１は、分散配置装置１００から配信された演算処理を実行する。メモリ２１２は、分散配置装置１００から配信された演算処理とスケジュールとを格納する。通信デバイス２１３は、ネットワークを介して接続された他の演算ノード２００に演算処理の結果として生成したデータを送信する。
【００３７】
次に、分散配置装置１００のそれぞれの機能部について詳細に説明する。
【００３８】
まず、モデル入力部１０１について説明する。
【００３９】
モデル入力部１０１は、演算ノード２００とネットワークスイッチ３００と通信経路４００との関係を示すネットワーク構成と、通信経路４００の通信速度ＴＳと、それぞれの演算ノード２００に割り当てられる演算処理の名称と、複数の演算処理間の実行順序を規定する先行制約と、それぞれの演算処理が実行される実行周期と、複数の演算処理の開始から終了までの要求時間であるデッドラインと、複数の演算処理間のデータ通信量と、それぞれの演算処理の実行時間とを入力する手段を備える。ここで、モデル入力部１０１には、演算処理の内容、たとえば、処理動作を記述するプログラムも入力されてもよい。
【００４０】
図４は、演算ノード２００と、ネットワークスイッチ３００と、通信経路４００との関係を示すネットワーク構成を例示する図である。図５は、演算処理５００および演算処理５００間の先行制約６００に関するモデル記述に例示する図である。
【００４１】
図６は、複数の演算処理５００のデッドラインを概念的に例示する図である。図７は、演算処理５００間のデータ通信量を例示する図である。図８は、演算処理５００の実行時間を例示する図である。
【００４２】
次に、モデル入力部１０１に入力するモデル記述の詳細を説明する。
【００４３】
図５では、たとえば、演算処理５００のうちの演算処理Ｊ１が３０ｍｓｅｃで周期的に実行することを、実行周期７００によって記述している。
【００４４】
また、演算処理５００のうちの演算処理Ｊ１と演算処理Ｊ２との間の先行制約６００は、演算処理Ｊ１の完了後に生成されるデータを演算処理Ｊ２が割り当てられる演算ノード２００が受信完了した後に、演算処理Ｊ２が開始されることを記述している。
【００４５】
また、図７では、演算処理Ｊ１が割り当てられる演算ノード２００から演算処理Ｊ２が割り当てられる演算ノード２００へ送信されるデータ量が、「Ｊ１→Ｊ２」の行に「５０Ｍｂｙｔｅ」と記述されている。
【００４６】
また、図８では、演算処理５００が割り当て可能な演算ノード２００の名称、および、当該演算ノード２００における演算処理の実行時間が記述されている。
【００４７】
図８においては、最上段に演算処理の名称を記述し、最左列に演算ノード名を記述する。そして、演算処理５００が割り当て不可能な演算ノード２００には「−」が、演算処理５００が割り当て可能な演算ノード２００には演算処理の実行時間がそれぞれ記述されている。この「演算処理の実行時間」は、分散配置装置が設定する最小単位で記述される。ただし、演算処理５００の実行時間が実際にはバラつきがある場合は、バラつく実行時間のうちの最長の実行時間が記述される。ここで、演算処理の名称とは、演算処理の内容を識別するための名称であり、たとえば、番号または記号などによって示されるものである。
【００４８】
演算処理５００の実行時間の指定は、分散配置装置１００へのモデル入力の前に、あらかじめそれぞれの演算ノード２００に演算処理５００を配置した上で実行時間を計測するか、演算処理プログラムから実行時間を推定するかによって行われてもよい。または、分散配置装置１００が自動的に演算処理５００の実行時間を計測してもよい。
【００４９】
次に、定式化部１０２について説明する。
【００５０】
定式化部１０２は、モデル入力部１０１に入力されたモデル記述から制約条件式を導出する。
【００５１】
制約条件式は、それぞれの演算処理５００が割り当てる演算ノード２００と、それぞれの演算処理５００の実行開始時刻とを入力パラメータとし、制約を満たすかどうかの真偽を判定する式である。
【００５２】
以降、制約条件式の入力パラメータを下記で表す。
【００５３】
【数１】
0006707198.tif 000002
【００５４】
【数２】
0006707198.tif 000003
【００５５】
制約条件式では、モデル記述と入力パラメータとから明らかとなるパラメータとして下記を用いる。
【００５６】
【数３】
0006707198.tif 000004
【００５７】
【数４】
0006707198.tif 000005
【００５８】
【数５】
0006707198.tif 000006
【００５９】
【数６】
0006707198.tif 000007
【００６０】
【数７】
0006707198.tif 000008
【００６１】
ここで、通信速度ＴＳは、モデル記述で直接記述するパラメータである。完了時刻Ｊｘ＿Ｅは、演算ノードＪｘ＿Ｎおよび開始時刻Ｊｘ＿Ｓの入力パラメータから、図８を用いて導出されるパラメータである。
【００６２】
また、データ送信開始時刻Ｊｘ＿ｔｏ＿Ｊｙ＿Ｓは完了時刻Ｊｘ＿Ｅと同時刻とする。また、データ送信完了時刻Ｊｘ＿ｔｏ＿Ｊｙ＿Ｅは開始時刻Ｊｙ＿Ｓ以前であればよいので、開始時刻Ｊｙ＿Ｓと同時刻とする。
【００６３】
全体周期Ｐは、周期的に実行される演算処理５００が１つである場合、または、周期が同一である複数の演算処理５００が周期的に実行される場合は、当該演算処理の実行周期を示している。周期的に実行される演算処理５００が２種類以上である場合については、後述の第２の実施の形態において記載する。
【００６４】
図５の演算処理５００のモデル記述では、周期的に実行される演算処理５００が演算処理Ｊ１の１つであるため、全体周期Ｐは３０ｍｓｅｃとなる。
【００６５】
制約条件式は、先行制約、割り当て可能な演算ノードおよびその実行時間に関する制約、演算ノードの資源制約、通信経路の資源制約、および、デッドラインによる制約のすべてを満たすかどうかを判定する式である。
【００６６】
以降、全制約から導出される制約条件式を全制約条件式と呼び、それぞれの制約から導出される制約条件式は単に、制約条件式と呼ぶ。
【００６７】
次に、先行制約６００から導出される制約条件式について説明する。
【００６８】
先行制約６００に関する制約条件式は、周期的に実行される演算処理５００の開始時刻を０とする制約条件式と、先行制約６００が記述された２つの演算処理５００の間の実行順序に関する制約条件式である。図５に例示される先行制約６００において、演算処理Ｊ１に先行する演算処理はないため、演算処理Ｊ１の開始時刻Ｊ１＿Ｓを０とする。このように、周期的に実行される演算処理Ｊｘの開始時刻Ｊｘ＿Ｓを０とする式を＜制約条件式１＞とする。
【００６９】
【数８】
0006707198.tif 000009
【００７０】
さらに、演算処理Ｊ１と演算処理Ｊ２との間には先行制約が記述されているため、２つの演算処理５００の間の制約条件式は下記となる。
【００７１】
【数９】
0006707198.tif 000010
【００７２】
【数１０】
0006707198.tif 000011
【００７３】
【数１１】
0006707198.tif 000012
【００７４】
【数１２】
0006707198.tif 000013
【００７５】
上記の（式２−１）、（式２−２）、（式２−３）および（式２−４）は、演算処理Ｊ１と演算処理Ｊ３、演算処理Ｊ２と演算処理Ｊ４、および、演算処理Ｊ３と演算処理Ｊ４に対しても同様に生成され、これらの式をすべて論理積ＡＮＤで接続したものを、先行制約の制約条件式とし、＜制約条件式２＞とする。
【００７６】
【数１３】
0006707198.tif 000014
【００７７】
次に、割り当て可能な演算ノード２００と実行時間に関する制約とから導出される制約条件式について説明する。
【００７８】
入力された演算処理５００が割り当てられる演算ノード２００に基づいて、演算処理５００の実行時間を確定させる制約条件式を導出する。
【００７９】
演算処理Ｊｘを演算ノードＮｙに割り当てた場合の実行時間をＴｘｙとすると下記が制約条件式となる。
【００８０】
【数１４】
0006707198.tif 000015
【００８１】
ここで、演算ノードＪｘ＿Ｎに対して割り当て可能な演算ノード２００を演算ノードＮ１、演算ノードＮ２および演算ノードＮ３とした場合、（式３−１）は演算ノードＮ１、演算ノードＮ２および演算ノードＮ３のいずれかとの制約条件式を満たせばよいため、論理和ＯＲでの接続とする。
【００８２】
演算処理Ｊｘを演算ノードＮ１に割り当てた場合の実行時間をＴｘ１、演算処理Ｊｘを演算ノードＮ２に割り当てた場合の実行時間をＴｘ２、演算処理Ｊｘを演算ノードＮ３に割り当てた場合の実行時間をＴｘ３とすると、下記の制約条件式となる。
【００８３】
【数１５】
0006707198.tif 000016
【００８４】
上記の制約条件式を複数の演算処理５００に対して導出し、論理積ＡＮＤで結合したものを、演算処理５００と割り当て可能な演算ノード２００の制約条件式とし、＜制約条件式３＞とする。
【００８５】
図８では、＜制約条件式３＞は下記となる。
【００８６】
【数１６】
0006707198.tif 000017
【００８７】
次に、演算ノード２００の資源制約から導出される制約条件式について説明する。
【００８８】
演算ノード２００の資源制約としては、２つの演算処理５００の間で、割り当てられる演算ノード２００が異なるか否かであり、同じ演算ノード２００に２つの演算処理５００が割り当てられる場合には、実行時間が重複しないことを制約とする。
【００８９】
演算処理Ｊｘおよび演算処理Ｊｙの間での演算ノード２００の資源制約は下記となる。
【００９０】
【数１７】
0006707198.tif 000018
【００９１】
上記の（式４−１）を演算処理５００のすべての組み合わせに対して導出し、論理積ＡＮＤで接続したものが、演算ノード２００の資源制約に対する制約条件式となる。
【００９２】
ここで、本実施の形態では、演算処理５００の実行が全体周期Ｐを超過する場合も含めた制約条件式を導出する。したがって、全体周期Ｐを超過した演算処理、すなわち、超過演算処理が、次の全体周期Ｐにおける演算処理と資源制約に違反しないことを判定する必要がある。
【００９３】
図９は、演算処理Ｊ１および演算処理Ｊ２を演算ノードＮ５に、演算処理Ｊ３および演算処理Ｊ４を演算ノードＮ１にそれぞれ割り当てた場合の、スケジュールを例示する図である。
【００９４】
演算処理Ｊ１は実行周期が３０ｍｓｅｃであり、かつ、周期的に実行される演算処理５００が演算処理Ｊ１の１つであるため、全体周期Ｐは３０ｍｓｅｃである。ここで、演算処理Ｊ１の開始から演算処理Ｊ４の完了までのデッドラインは、図６で例示されたように５０ｍｓｅｃである。
【００９５】
演算ノード２００の資源制約から、全体周期Ｐにおける、演算処理Ｊ４の開始時刻（Ｊ４＿Ｓ）と演算処理Ｊ４の終了時刻（Ｊ４＿Ｅ）との間の時間帯を１周期分前にずらした時間帯には、演算処理Ｊ３が演算ノードＮ１において実行されないものとする。すなわち、全体周期Ｐを超過して実行される超過演算処理である演算処理Ｊ４が割り当てられる演算ノードＮ１には、次の全体周期Ｐにおいて、演算処理Ｊ４の実行中に他の演算処理、たとえば、演算処理Ｊ３などが割り当てられることがない。
【００９６】
このような全体周期Ｐを超過する演算処理５００に対して、演算ノード２００の資源制約は下記となる。
【００９７】
【数１８】
0006707198.tif 000019
【００９８】
これら、（式４−１）および（式４−２）を論理積ＡＮＤで接続したものが演算ノードの資源制約に対する制約条件式とし、＜制約条件式４＞とする。
【００９９】
次に、通信経路４００の資源制約から導出される制約条件式について説明する。
【０１００】
通信経路４００は、１つの通信経路４００に対して同時に複数の演算処理５００からデータ送信を実行することが可能であり、通信経路４００の通信速度ＴＳは、同時にデータ送信を行う演算処理５００の数で等分されるものとする。また、送信元と送信先とが同じ演算ノード２００である場合には通信が発生しないため、通信経路４００の資源制約はない。
【０１０１】
１つの通信経路４００で同時に複数の演算処理５００がデータを送信することを、通信経路４００の競合と呼ぶ。通信経路４００の競合を判定するために、まず、２つの演算ノード２００間の最短通信経路を導出する。
【０１０２】
最短通信経路は、送信元の演算ノード２００から送信先の演算ノード２００までの通信経路４００の内、経由する演算ノード２００の数とネットワークスイッチ３００の数との和が最小となる経路である。
【０１０３】
図１０は、演算ノード２００と、ネットワークスイッチ３００と、通信経路４００との関係を示すネットワーク構成を例示する図である。図１０に例示されるネットワーク構成では、演算ノードＮ１１から演算ノードＮ１５までの経路の候補としては、下記に例示されるような複数の経路が存在する。
【０１０４】
【数１９】
0006707198.tif 000020
【０１０５】
【数２０】
0006707198.tif 000021
【０１０６】
【数２１】
0006707198.tif 000022
【０１０７】
上記では、経路１が最短通信経路となる。この最短通信経路をユーザーが入力したモデル記述から算出し、２つの演算ノード２００間の最短通信経路の表を生成する。
【０１０８】
図１１は、図４に例示されたネットワーク構成に関する最短通信経路を例示する図である。図１１において、送信元と送信先とが同じ演算ノード２００の場合、最短経路は「−」と記述されている。図１１を用いて、通信経路４００の競合を判定する。
【０１０９】
演算ノードＮｘ１から演算ノードＮｙ１へのデータ送信、および、演算ノードＮｘ２から演算ノードＮｙ２へのデータ送信に関しての通信経路４００の競合の判定について説明する。
【０１１０】
演算ノードＮｘ１から演算ノードＮｙ１への最短通信経路と、演算ノードＮｘ２から演算ノードＮｙ２への最短通信経路との間で、同じ通信経路４００が含まれていれば競合であると判定し、同じ通信経路４００が含まれていなければ競合していないと判定する。
【０１１１】
図１１において、演算ノードＮ１から演算ノードＮ１０への通信経路、および、演算ノードＮ２から演算ノードＮ１０への通信経路には、ともに（ＳＷ１→Ｎ４）、（Ｎ４→ＳＷ３）および（ＳＷ３→Ｎ１０）の通信経路が含まれている。そのため、これらの通信経路は競合すると判定することができる。
【０１１２】
次に、通信経路の競合が発生する場合の制約条件式について説明する。
【０１１３】
すべての演算処理５００の開始時刻と完了時刻とをそれぞれ抽出し、時刻の古い順にＴ１、Ｔ２、Ｔ３、…とする。Ｔ１からＴ２、Ｔ２からＴ３、Ｔ３からＴ４、…のそれぞれの時間間隔内で通信経路４００の競合を検出し、競合が発生したデータ通信の数で通信速度を等分とする。
【０１１４】
図１２は、ネットワーク構成を例示する図である。また、図１３は、図１２に例示されるネットワーク構成に対し、図５に例示された演算処理５００を割り当てた結果を例示する図である。
【０１１５】
図１３において、それぞれの演算処理５００の開始時刻および終了時刻はＴ１、Ｔ２、Ｔ３、…、Ｔ８で示される。
【０１１６】
図１４は、図１３に例示された割り当て結果に、先行制約６００に基づいて、それぞれの演算処理５００間のデータ通信の開始時刻と終了時刻とが追記された図である。図１４において、演算処理Ｊ１から演算処理Ｊ２へのデータ送信は、「Ｊ１→Ｊ２」の範囲内で完了しなければならない。この制約を通信経路の資源制約とする。
【０１１７】
演算処理Ｊｘから演算処理Ｊｙへのデータ送信が発生し、完了時刻Ｊｘ＿Ｅ＝Ｔｎ、開始時刻Ｊｙ＿Ｓ＝Ｔｍとすると、下記の制約条件式となる。
【０１１８】
【数２２】
0006707198.tif 000023
【０１１９】
上記式をすべてのデータ送信が発生する演算処理５００に対して生成し、論理積ＡＮＤで接続したものを、＜制約条件式５＞とする。
【０１２０】
＜制約条件式５＞は図１４において、下記式となる。
【０１２１】
【数２３】
0006707198.tif 000024
【０１２２】
次に、デッドラインから導出される制約条件式について説明する。
【０１２３】
演算処理Ｊｘの開始時刻Ｊｘ＿Ｓ、演算処理Ｊｙの完了時刻Ｊｙ＿Ｅに対して、開始時刻Ｊｘ＿Ｓから完了時刻Ｊｙ＿ＥまでがデッドラインＤＬ以下でなければならないという制約から、下記の＜制約条件式６＞を導出する。
【０１２４】
【数２４】
0006707198.tif 000025
【０１２５】
図６に例示されたデッドラインのモデル記述は、演算処理Ｊ１の開始時刻から演算処理Ｊ４の完了時刻までのデッドラインが、それぞれの演算処理５００の実行時間および演算処理５００間のデータ通信などを考慮した上で、５０ｍｓｅｃ以下でなければならないという制約を示している。
【０１２６】
この制約から、下記の制約条件式を導出する。
【０１２７】
【数２５】
0006707198.tif 000026
【０１２８】
これまでに説明した＜制約条件式１＞、＜制約条件式２＞、＜制約条件式３＞、＜制約条件式４＞、＜制約条件式５＞および＜制約条件式６＞はすべて満たす必要があるため、これらを論理積ＡＮＤで接続したものを、＜全制約条件式＞とする。
【０１２９】
【数２６】
0006707198.tif 000027
【０１３０】
次に、解導出部１０３の詳細を説明する。
【０１３１】
解導出部１０３では、定式化部１０２で導出された全制約条件式を用いて、制約条件を満たす入力パラメータを導出する。入力パラメータの内、演算処理Ｊｘが割り当てられる演算ノードＪｘ＿Ｎの取りうる範囲、すなわち、演算処理Ｊｘを割り当て可能な演算ノードＪｘ＿Ｎは、図８に例示されている。
【０１３２】
入力パラメータの内、開始時刻Ｊｘ＿Ｓの最小値は０、最大値は（全体周期Ｐ＋最大ＤＬ）である。ここで、最大ＤＬとは、モデル記述で入力されたデッドラインの内で最も値の大きいものである。開始時刻Ｊｘ＿Ｓの最小単位はモデル入力部１０１において設定しておく。
【０１３３】
解導出部１０３は、演算ノードＪｘ＿Ｎが取りうる値の範囲と、開始時刻Ｊｘ＿Ｓが取りうる値の範囲との組み合わせを入力パラメータとして全制約条件式に入力し、制約を満たすかどうかを判定する。制約を満たす入力パラメータを解と呼ぶ。
【０１３４】
この時、解導出部１０３は網羅的に探索して解を導出してもよいし、局所探索によって解を導出してもよい。
【０１３５】
そして、解が見つからない場合は、ユーザーに通知を行う。解が見つからないという通知によって、ユーザーは、演算ノード２００の数の追加または演算処理５００の削減などを行う必要があることが分かる。
【０１３６】
上記の解が複数存在する場合、解導出部１０３は、目的関数Ｏを用いて最適解を選択する。なお、解導出部１０３は、導出された解が１つである場合には、当該解を最適な解として選択する。
【０１３７】
ユーザーは図２における入力部１１２から目的関数Ｏを入力する。そして解導出部１０３は、目的関数Ｏを最大化または最小化する解のいずれを最適解とするかを選択する。たとえば、全体処理時間を最小とする目的関数Ｏは下記となる。
【０１３８】
【数２７】
0006707198.tif 000028
【０１３９】
上記の式において、ＭＡＸ関数は引数の中で最大の値を返す関数である。上記の式を用いた場合の目的関数Ｏは、全演算処理において最後に実行する演算処理の完了時刻となる。
【０１４０】
この目的関数Ｏが最小となる解が、全体処理完了時間を最小とする解となる。この目的関数Ｏには、特定の演算ノード間の通信量を最小とする目的関数を設定してもよい。
【０１４１】
次に、分配部１０４の詳細を説明する。
【０１４２】
分配部１０４では、解導出部１０３において導出された解である演算処理５００が割り当てられる演算ノード２００と、割り当てられた演算処理５００の開始時刻と、演算処理５００の実行プログラムとをそれぞれの演算ノード２００へ配信する。分配部１０４は、すべての演算ノード２００と時刻同期を行い、全体周期Ｐの先頭時刻をそれぞれの演算ノード２００に通知する。ここで、演算処理５００の内容である実行プログラムは、モデル入力部１０１に入力されたものを参照してもよいし、外部の記憶媒体に記憶されている対応する実行プログラムを参照してもよい。
【０１４３】
演算ノード２００は、配信された演算処理５００の開始時刻と演算処理５００の実行プログラムとをメモリ２１２に格納する。そして、演算ノード２００は、実際の時刻に基づいて、全体周期Ｐの先頭を時刻０とする全体周期Ｐ内の時刻を算出し、演算処理５００を実行する。
【０１４４】
全体周期Ｐ内の時刻は、下記式において算出する。
【０１４５】
【数２８】
0006707198.tif 000029
【０１４６】
ここで、上記の式における「％」は、左項を右項で除算した剰余の値を求める演算子である。
【０１４７】
＜第２の実施の形態＞
本実施の形態に関する分散配置装置、分散配置システム、および、分散配置方法について説明する。以下の説明においては、以上に記載された実施の形態で説明された構成と同様の構成については同じ符号を付して図示し、その詳細な説明については適宜省略するものとする。
【０１４８】
＜分散配置装置の構成について＞
第１の実施の形態に関する分散配置装置１００では、モデル入力部１０１へ入力される演算処理５００の実行周期は１種類であった。しかしながら、複数の演算処理５００に対して、異なる長さの実行周期が設定されてもよい。
【０１４９】
図１５は、周期３０ｍｓｅｃで実行される演算処理Ｊ１１、周期２０ｍｓｅｃで実行される演算処理Ｊ２１および演算処理５００間の先行制約６００に関するモデル記述に例示する図である。
【０１５０】
図１６および図１７は、図１５に例示されたモデル記述に対応する、演算処理５００のデッドラインを概念的に例示する図である。
【０１５１】
複数の異なる周期を持つ演算処理５００に対して、全体周期Ｐはそれぞれの周期の最小公倍数とする。図１５に対しては、３０ｍｓｅｃと２０ｍｓｅｃとの最小公倍数である６０ｍｓｅｃを全体周期Ｐとする。
【０１５２】
全体周期Ｐにおいて、演算処理Ｊ１１は２回、演算処理Ｊ２１は３回実行される。そして、全体周期Ｐにおいて、１回目に実行する演算処理Ｊ１１をＪ１１［１］、２回目に実行する演算処理Ｊ１１をＪ１１［２］と記述する。演算処理Ｊ２１についても同様である。演算処理Ｊ１１および演算処理Ｊ２１から先行制約６００で関係づけられた全演算処理についても同様に複数回を全体周期Ｐ内で実行し、同様に演算処理Ｊｘ［ｎ］とする。
【０１５３】
ここで、周期的に実行される演算処理Ｊｘの開始時刻の＜制約条件式１＞は下記となる。
【０１５４】
【数２９】
0006707198.tif 000030
【０１５５】
ここで、Ｊｘ［１］を０としているが、０から（演算処理Ｊｘの周期）未満の範囲で自由に設定してもよい。
【０１５６】
上記の制約条件式１は、図１５の場合には下記となる。
【０１５７】
【数３０】
0006707198.tif 000031
【０１５８】
このようにして導出された＜制約条件式１＞と、［ｎ］付きのすべての演算処理に対して＜制約条件式２＞、＜制約条件式３＞、＜制約条件式４＞、＜制約条件式５＞および＜制約条件式６＞を第１の実施の形態と同様に導出したものとによって、全制約条件式を導出する。解導出部１０３の動作および分配部１０４の動作は、第１の実施の形態と同様である。
【０１５９】
＜以上に記載された実施の形態によって生じる効果について＞
次に、以上に記載された実施の形態によって生じる効果を例示する。なお、以下の説明においては、以上に記載された実施の形態に例示された具体的な構成に基づいて当該効果が記載されるが、同様の効果が生じる範囲で、本願明細書に例示される他の具体的な構成と置き換えられてもよい。
【０１６０】
また、当該置き換えは、複数の実施の形態に跨ってなされてもよい。すなわち、異なる実施の形態において例示されたそれぞれの構成が組み合わされて、同様の効果が生じる場合であってもよい。
【０１６１】
以上に記載された実施の形態によれば、分散配置装置１００は、複数の演算ノード２００とネットワークを介して接続され、かつ、複数の演算ノード２００へ演算処理５００を割り当てる。ここで、演算ノード２００は、生産ラインで収集するデータに対して演算処理５００を行う。分散配置装置１００は、入力部と、作成部と、導出部と、分配部１０４とを備える。ここで、入力部は、たとえば、モデル入力部１０１に対応するものである。また、作成部は、たとえば、定式化部１０２に対応するものである。また、導出部は、たとえば、解導出部１０３に対応するものである。そして、モデル入力部１０１には、複数の演算ノード２００間のネットワーク構成と、それぞれの演算ノード２００に割り当てられる演算処理５００の名称と、それぞれの演算処理５００が実行される実行周期７００と、複数の演算処理５００の開始から終了までの要求時間であるデッドラインと、複数の演算処理５００間の実行順序を規定する先行制約６００と、複数の演算処理５００間のデータ通信量と、それぞれの演算処理５００の実行時間とが入力される。また、定式化部１０２は、モデル入力部１０１に入力されたそれぞれの情報に基づいて制約条件式を作成する。また、解導出部１０３は、複数の演算ノード２００間のネットワーク構成を参照しつつ、制約条件式を満たすそれぞれの演算ノード２００への演算処理５００の割り当ておよびスケジュールを導出する。また、分配部１０４は、演算処理５００の割り当ておよびスケジュールをそれぞれの演算ノード２００へ分配する。また、定式化部１０２は、複数の演算処理５００間の先行制約６００に基づいて、それぞれの演算処理５００を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの演算処理５００の実行時間および複数の演算処理５００間のデータ通信量に基づいて、デッドラインを満たす制約条件式を作成する。また、定式化部１０２は、先行制約６００に基づいて順序づけられたそれぞれの演算処理５００の実行周期７００に基づく全体周期を算出し、全体周期よりもデッドラインが長い場合、全体周期を超過して実行される超過演算処理を割り当てられる演算ノード２００には、次の全体周期において、超過演算処理の実行中に他の演算処理５００を割り当てない制約条件式を作成する。
【０１６２】
また、以上に記載された実施の形態によれば、分散配置装置１００は、出力部１１１と、入力部１１２とを備える。また、分散配置装置１００は、プログラムを実行する処理回路であるＣＰＵ１１３と、実行されるプログラムを記憶する記憶装置であるメモリ１１４とを備える。そして、ＣＰＵ１１３がプログラムを実行することによって、以下の動作が実現される。
【０１６３】
すなわち、入力部１１２に入力されたそれぞれの情報に基づいて制約条件式を作成する。そして、複数の演算ノード２００間のネットワーク構成を参照しつつ、制約条件式を満たすそれぞれの演算ノード２００への演算処理５００の割り当ておよびスケジュールを導出する。そして、演算処理５００の割り当ておよびスケジュールをそれぞれの演算ノード２００へ出力部１１１を介して分配する。制約条件式の作成は、複数の演算処理５００間の先行制約６００に基づいて、それぞれの演算処理５００を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの演算処理５００の実行時間および複数の演算処理５００間のデータ通信量に基づいて、デッドラインを満たすようになされる。また、制約条件式の作成は、先行制約６００に基づいて順序づけられたそれぞれの演算処理５００の実行周期７００に基づく全体周期を算出し、全体周期よりもデッドラインが長い場合、全体周期を超過して実行される超過演算処理を割り当てられる演算ノード２００には、次の全体周期において、超過演算処理の実行中に他の演算処理５００を割り当てないようになされる。
【０１６４】
このような構成によれば、複数の演算処理５００間の先行制約６００に基づいて、それぞれの演算処理５００を行う順序を決定され、当該順序に基づいて実行される複数の演算処理５００が全体としてデッドラインを満たすように、制約条件式が作成される。したがって、それぞれの演算処理５００に対して適切なデッドラインをそれぞれ設定する必要がない。また、先行制約６００に基づいて順序づけられた複数の演算処理５００の全体周期よりもデッドラインが長い場合であっても、超過演算処理を割り当てられる演算ノード２００には、次の全体周期において、超過演算処理の実行中に他の演算処理５００を割り当てないように制約条件式が作成される。したがって、実行周期に関連して必要以上にデッドラインを短く設定することがない。
【０１６５】
なお、これらの構成以外の本願明細書に例示される他の構成については適宜省略することができる。すなわち、少なくともこれらの構成を備えていれば、以上に記載された効果を生じさせることができる。
【０１６６】
しかしながら、本願明細書に例示される他の構成のうちの少なくとも１つを以上に記載された構成に適宜追加した場合、すなわち、以上に記載された構成としては記載されなかった本願明細書に例示される他の構成を以上に記載された構成に追加した場合でも、同様に以上に記載された効果を生じさせることができる。
【０１６７】
また、以上に記載された実施の形態によれば、モデル入力部１０１には、複数の演算ノード２００間の通信速度がさらに入力される。そして、定式化部１０２は、複数の演算ノード２００間で同時に複数のデータ通信が発生する場合、複数の演算ノード２００間の通信速度を同時に発生するデータ通信の数で等分して制約条件式を作成する。このような構成によれば、通信経路４００における資源制約も考慮して、制約条件式を作成することができる。
【０１６８】
また、以上に記載された実施の形態によれば、定式化部１０２は、先行制約６００に基づいて順序づけられたそれぞれの演算処理５００の実行周期７００が異なる場合、複数の実行周期７００の最小公倍数を全体周期とし、当該全体周期内でそれぞれの演算処理５００をそれぞれの実行周期７００に対応して繰り返し実行させる制約条件式を作成する。このような構成によれば、異なる長さの実行周期が設定されている場合であっても、それぞれの演算処理５００が全体周期内で繰り返し実行されるように、全体周期の長さを制約条件式において適切に設定することができる。
【０１６９】
また、以上に記載された実施の形態によれば、分散配置システムは、分散配置装置１００と、分散配置装置１００に接続されるネットワーク構成とを備える。ネットワーク構成は、演算処理５００を行う複数の演算ノード２００と、複数の演算ノード２００間を接続するネットワークスイッチ３００とを備える。
【０１７０】
このような構成によれば、先行制約６００に基づいて実行される複数の演算処理５００が全体としてデッドラインを満たすように、制約条件式が作成される。また、複数の演算処理５００の全体周期よりもデッドラインが長い場合であっても、超過演算処理を割り当てられる演算ノード２００には、次の全体周期において、超過演算処理の実行中に他の演算処理５００を割り当てないように制約条件式が作成される。したがって、複数の演算処理５００に対する適切なデッドラインを設定しつつ、複数の演算処理５００を、ネットワーク構成における複数の演算ノード２００に分散配置することができる。
【０１７１】
以上に記載された実施の形態によれば、分散配置方法において、複数の演算ノード２００間のネットワーク構成と、それぞれの演算ノード２００に割り当てられる演算処理５００の名称と、それぞれの演算処理５００が実行される実行周期７００と、複数の演算処理５００の開始から終了までの要求時間であるデッドラインと、複数の演算処理５００間の実行順序を規定する先行制約６００と、複数の演算処理５００間のデータ通信量と、それぞれの演算処理５００の実行時間とを入力する。そして、入力されたそれぞれの情報に基づいて制約条件式を作成する。そして、複数の演算ノード２００間のネットワーク構成を参照しつつ、制約条件式を満たすそれぞれの演算ノード２００への演算処理５００の割り当ておよびスケジュールを導出する。そして、演算処理５００の割り当ておよびスケジュールをそれぞれの演算ノード２００へ分配する。ここで、制約条件式の作成は、複数の演算処理５００間の先行制約６００に基づいて、それぞれの演算処理５００を行う順序を決定し、さらに、当該順序に基づいて実行されるそれぞれの演算処理５００の実行時間および複数の演算処理５００間のデータ通信量に基づいて、デッドラインを満たすようになされる。また、制約条件式の作成は、先行制約６００に基づいて順序づけられたそれぞれの演算処理５００の実行周期７００に基づく全体周期を算出し、全体周期よりもデッドラインが長い場合、全体周期を超過して実行される超過演算処理を割り当てられる演算ノード２００には、次の全体周期において、超過演算処理の実行中に他の演算処理５００を割り当てないようになされる。
【０１７２】
このような構成によれば、先行制約６００に基づいて実行される複数の演算処理５００が全体としてデッドラインを満たすように、制約条件式が作成される。また、複数の演算処理５００の全体周期よりもデッドラインが長い場合であっても、超過演算処理を割り当てられる演算ノード２００には、次の全体周期において、超過演算処理の実行中に他の演算処理５００を割り当てないように制約条件式が作成される。したがって、それぞれの演算処理５００に対して適切なデッドラインをそれぞれ設定する必要がなく、また、実行周期に関連して必要以上にデッドラインを短く設定することがない。
【０１７３】
なお、これらの構成以外の本願明細書に例示される他の構成については適宜省略することができる。すなわち、少なくともこれらの構成を備えていれば、以上に記載された効果を生じさせることができる。
【０１７４】
しかしながら、本願明細書に例示される他の構成のうちの少なくとも１つを以上に記載された構成に適宜追加した場合、すなわち、以上に記載された構成としては記載されなかった本願明細書に例示される他の構成を以上に記載された構成に追加した場合でも、同様に以上に記載された効果を生じさせることができる。
【０１７５】
また、特段の制限がない場合には、それぞれの処理が行われる順序は変更することができる。
【０１７６】
＜以上に記載された実施の形態における変形例について＞
以上に記載された実施の形態では、それぞれの構成要素の寸法、形状、相対的配置関係または実施の条件などについても記載する場合があるが、これらはすべての局面において例示であって、本願明細書に記載されたものに限られることはないものとする。
【０１７７】
したがって、例示されていない無数の変形例、および、均等物が、本願明細書に開示される技術の範囲内において想定される。たとえば、少なくとも１つの構成要素を変形する場合、追加する場合または省略する場合、さらには、少なくとも１つの実施の形態における少なくとも１つの構成要素を抽出し、他の実施の形態の構成要素と組み合わせる場合が含まれるものとする。
【０１７８】
また、矛盾が生じない限り、以上に記載された実施の形態において「１つ」備えられるものとして記載された構成要素は、「１つ以上」備えられていてもよいものとする。
【０１７９】
さらに、以上に記載された実施の形態におけるそれぞれの構成要素は概念的な単位であって、本願明細書に開示される技術の範囲内には、１つの構成要素が複数の構造物から成る場合と、１つの構成要素がある構造物の一部に対応する場合と、さらには、複数の構成要素が１つの構造物に備えられる場合とを含むものとする。
【０１８０】
また、以上に記載された実施の形態におけるそれぞれの構成要素には、同一の機能を発揮する限り、他の構造または形状を有する構造物が含まれるものとする。
【０１８１】
また、本願明細書における説明は、本技術に関するすべての目的のために参照され、いずれも、従来技術であると認めるものではない。
【０１８２】
また、以上に記載された実施の形態で記載されたそれぞれの構成要素は、ソフトウェアまたはファームウェアとしても、それと対応するハードウェアとしても想定され、その双方の概念において、それぞれの構成要素は「部」または「処理回路」などと称される。
【０１８３】
また、本願明細書に開示される技術は、それぞれの構成要素が複数の装置に分散して備えられる場合、すなわち、システムのような態様であってもよいものとする。
【０１８４】
たとえば、メモリ１１４は、図２においては分散配置装置内に搭載されるものとして示されたが、外部の機能部であってもよいものとする。その場合、分散配置装置内の他の機能部と外部の機能部とが互いに作用しあうことによって、全体として分散配置装置の機能を果たすものであればよい。
【符号の説明】
【０１８５】
１００  分散配置装置、１０１  モデル入力部、１０２  定式化部、１０３  解導出部、１０４  分配部、１１１  出力部、１１２  入力部、１１３，２１１  ＣＰＵ、１１４，２１２  メモリ、１１５，２１３  通信デバイス、２００  演算ノード、３００  ネットワークスイッチ、４００  通信経路、５００  演算処理、６００  先行制約、７００  実行周期。
【図１】
0006707198.tif 000032
【図２】
0006707198.tif 000033
【図３】
0006707198.tif 000034
【図４】
0006707198.tif 000035
【図５】
0006707198.tif 000036
【図６】
0006707198.tif 000037
【図７】
0006707198.tif 000038
【図８】
0006707198.tif 000039
【図９】
0006707198.tif 000040
【図１０】
0006707198.tif 000041
【図１１】
0006707198.tif 000042
【図１２】
0006707198.tif 000043
【図１３】
0006707198.tif 000044
【図１４】
0006707198.tif 000045
【図１５】
0006707198.tif 000046
【図１６】
0006707198.tif 000047
【図１７】
0006707198.tif 000048