図面 (/)

技術 高速変更計画システム、高速変更計画方法および高速変更計画プログラム

出願人 日本電気株式会社バンダービルト・ユニバーシティ
発明者 黒田貴之アニルダスレッシュゴカリェ
出願日 2015年4月24日 (5年0ヶ月経過) 出願番号 2015-089589
公開日 2015年12月3日 (4年4ヶ月経過) 公開番号 2015-215886
状態 特許登録済
技術分野 ストアードプログラム
主要キーワード 暫定結果 角丸四角形 計算不能 変更計画 遷移順序 導出結果 グループ群 適切な作業
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2015年12月3日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

規模なシステム変更計画作成における計算量を削減できる高速変更計画システムを提供する。

解決手段

高速変更計画システム10は、1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部11と、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序統合する状態マシン群統合部12とを含む。状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、当該状態マシン以外の状態マシンに関連し、状態マシン群分割部11は、複数の状態マシンに含まれる1つの状態マシンから、複数の状態マシン間の遷移条件が関連する状態マシンを、遷移条件の数だけ順に辿った時に1つの状態マシンに戻る場合、複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割してもよい。

概要

背景

変更管理の目的は、あるシステムを変更する際に生じる、変更するシステムの管理者および変更作業者の手間と、変更するシステムの利用者への影響を少なくすることである。変更するシステムが、例えば、複数の部品から構成されるような複雑なシステムである場合、変更作業は複雑になる。変更作業が複雑になると、作業者の手間や、作業者の作業を監督する管理者の手間は増大する。その結果、システム利用者への影響も増大する。

特に、システムを構成する部品間に依存性が存在する場合、各部品に対する変更作業の順序が問題になるため、作業が複雑になりやすい。部品間の依存性は、例えば、部品Aと部品Bがある場合、部品Aが正しく機能するためには部品Bが正しく機能することが必要であるというような、2つの要素間の関係性である。

上記の例の場合、部品Aは部品Bに依存するという。このような部品Aと部品Bから構成されるシステムを構築する作業では、最初に部品Bを構築し、次に部品Aを構築するというように、実施する作業に順序性が求められる。

このような依存性を考慮しつつ、システムの変更に必要な作業の計画を自動的に作成するシステムを変更計画システムと呼ぶ。ただし、本発明における変更計画システムは、各部品の現在の状態(現在状態)と、変更後の要求される状態(要求状態)とを入力データとして、必要な作業と適切な作業手順を導出するシステムである。変更計画システムでは、予め部品間の依存性に関する情報、および部品に対する作業に関する情報が定義されている。

上記の変更計画システムを用いることで、管理者は、複雑な変更作業の実施に効果的な作業手順を効率的に作成できる。また、作業者も、作成された効果的な作業手順に基づいて、効率的に作業を実施できる。その結果、変更されるシステムの利用者への影響も少なくなることが期待される。

このような変更計画システムに関して、既に多数の関連研究や関連製品が知られている。非特許文献1には、管理対象のシステムを複数の状態マシン群として定義する方法が記載されている。非特許文献1に記載された方法では、各状態マシン群が持つ遷移遷移条件は、遷移が含まれる状態マシン以外の状態マシン内の状態を用いて記述される。

状態マシンは、システムを構成する部品を表す。状態マシンの状態は、部品がとり得る状態を表す。また、遷移には、部品の状態を変更する際の作業の情報が含まれる。遷移条件は、遷移に含まれる情報に対応する作業が持つ依存性を表す。

以上のようなシステムの定義方法に基づく変更計画は、計画可能な状況が広範である点や、定義の再利用可能な点において、他の手法を用いた変更計画よりも有効であると期待される。本発明において、上記の定義方法に基づくシステムが対象のシステムになる。以下、対象になるシステムを単に変更計画システムと呼ぶ。

状態マシン群として記述されたシステムの変更計画は、全ての状態マシンが現在状態を持ち、少なくとも1つの状態マシンが要求状態を持つとき、遷移条件を満たしつつ要求状態が指定された全ての状態マシンを現在状態から要求状態に遷移させる遷移順序を求めることによって作成される。非特許文献1には、このような変更計画の作成方法が記載されている。

概要

規模なシステムの変更計画作成における計算量を削減できる高速変更計画システムを提供する。高速変更計画システム10は、1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部11と、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する状態マシン群統合部12とを含む。状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、当該状態マシン以外の状態マシンに関連し、状態マシン群分割部11は、複数の状態マシンに含まれる1つの状態マシンから、複数の状態マシン間の遷移条件が関連する状態マシンを、遷移条件の数だけ順に辿った時に1つの状態マシンに戻る場合、複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割してもよい。

目的

変更管理の目的は、あるシステムを変更する際に生じる、変更するシステムの管理者および変更作業者の手間と、変更するシステムの利用者への影響を少なくすることである

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部と、分割された前記状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序統合する状態マシン群統合部とを含むことを特徴とする高速変更計画ステム

請求項2

状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、前記状態マシン以外の状態マシンに関連し、状態マシン群分割部は、複数の状態マシンに含まれる1つの状態マシンから、前記複数の状態マシン間の遷移条件が関連する状態マシンを、前記遷移条件の数だけ順に辿った時に前記1つの状態マシンに戻る場合、前記複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割する請求項1記載の高速変更計画システム。

請求項3

状態マシン群分割部は、状態マシングループ内の状態マシンに関連する遷移条件に従って遷移する状態を含む仮状態マシンを前記状態マシングループに追加し、状態マシン群統合部は、前記仮状態マシンの元である状態マシングループから導出された遷移順序と、前記仮状態マシンが追加された状態マシングループから導出された遷移順序とを統合する請求項1記載の高速変更計画システム。

請求項4

状態マシン群統合部は、所定の条件に従う状態マシングループが複数ある場合、複数の前記状態マシングループから遷移順序をそれぞれ導出する処理を並列的に行う指示を外部装置に出力する請求項1記載の高速変更計画システム。

請求項5

所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されており、かつ前記他の状態マシングループから既に遷移順序が導出されていることである請求項4記載の高速変更計画システム。

請求項6

所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されていないことである請求項4記載の高速変更計画システム。

請求項7

1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、分割された前記状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合することを特徴とする高速変更計画方法。

請求項8

状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、前記状態マシン以外の状態マシンに関連し、複数の状態マシンに含まれる1つの状態マシンから、前記複数の状態マシン間の遷移条件が関連する状態マシンを、前記遷移条件の数だけ順に辿った時に前記1つの状態マシンに戻る場合、前記複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割する請求項7記載の高速変更計画方法。

請求項9

コンピュータで実行されるときに、1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、分割された前記状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する高速変更計画プログラムを記録した非一時的なコンピュータ読み取り可能な記録媒体

請求項10

コンピュータで実行されるときに、状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、前記状態マシン以外の状態マシンに関連し、複数の状態マシンに含まれる1つの状態マシンから、前記複数の状態マシン間の遷移条件が関連する状態マシンを、前記遷移条件の数だけ順に辿った時に前記1つの状態マシンに戻る場合、前記複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割する請求項9記載の記録媒体。

技術分野

0001

本発明は、高速変更計画ステム、高速変更計画方法および高速変更計画プログラムに関する。

背景技術

0002

変更管理の目的は、あるシステムを変更する際に生じる、変更するシステムの管理者および変更作業者の手間と、変更するシステムの利用者への影響を少なくすることである。変更するシステムが、例えば、複数の部品から構成されるような複雑なシステムである場合、変更作業は複雑になる。変更作業が複雑になると、作業者の手間や、作業者の作業を監督する管理者の手間は増大する。その結果、システム利用者への影響も増大する。

0003

特に、システムを構成する部品間に依存性が存在する場合、各部品に対する変更作業の順序が問題になるため、作業が複雑になりやすい。部品間の依存性は、例えば、部品Aと部品Bがある場合、部品Aが正しく機能するためには部品Bが正しく機能することが必要であるというような、2つの要素間の関係性である。

0004

上記の例の場合、部品Aは部品Bに依存するという。このような部品Aと部品Bから構成されるシステムを構築する作業では、最初に部品Bを構築し、次に部品Aを構築するというように、実施する作業に順序性が求められる。

0005

このような依存性を考慮しつつ、システムの変更に必要な作業の計画を自動的に作成するシステムを変更計画システムと呼ぶ。ただし、本発明における変更計画システムは、各部品の現在の状態(現在状態)と、変更後の要求される状態(要求状態)とを入力データとして、必要な作業と適切な作業手順を導出するシステムである。変更計画システムでは、予め部品間の依存性に関する情報、および部品に対する作業に関する情報が定義されている。

0006

上記の変更計画システムを用いることで、管理者は、複雑な変更作業の実施に効果的な作業手順を効率的に作成できる。また、作業者も、作成された効果的な作業手順に基づいて、効率的に作業を実施できる。その結果、変更されるシステムの利用者への影響も少なくなることが期待される。

0007

このような変更計画システムに関して、既に多数の関連研究や関連製品が知られている。非特許文献1には、管理対象のシステムを複数の状態マシン群として定義する方法が記載されている。非特許文献1に記載された方法では、各状態マシン群が持つ遷移遷移条件は、遷移が含まれる状態マシン以外の状態マシン内の状態を用いて記述される。

0008

状態マシンは、システムを構成する部品を表す。状態マシンの状態は、部品がとり得る状態を表す。また、遷移には、部品の状態を変更する際の作業の情報が含まれる。遷移条件は、遷移に含まれる情報に対応する作業が持つ依存性を表す。

0009

以上のようなシステムの定義方法に基づく変更計画は、計画可能な状況が広範である点や、定義の再利用可能な点において、他の手法を用いた変更計画よりも有効であると期待される。本発明において、上記の定義方法に基づくシステムが対象のシステムになる。以下、対象になるシステムを単に変更計画システムと呼ぶ。

0010

状態マシン群として記述されたシステムの変更計画は、全ての状態マシンが現在状態を持ち、少なくとも1つの状態マシンが要求状態を持つとき、遷移条件を満たしつつ要求状態が指定された全ての状態マシンを現在状態から要求状態に遷移させる遷移順序を求めることによって作成される。非特許文献1には、このような変更計画の作成方法が記載されている。

先行技術

0011

S. Hagen and A. Kemper, “Model-based planning for state-relatedchanges to infrastructure and software as a service instances in largedata centers,” in Cloud Computing (CLOUD), 2010IEEE 3rd InternationalConference on, July 2010, pp. 11-18.

発明が解決しようとする課題

0012

非特許文献1に記載されている変更計画システムでは、変更計画の作成に必要な計算量が、対象にする状態マシンの数が増えると指数関数的に増大する点が問題になる。すなわち、大規模なシステムの変更計画を作成するコンピュータは、膨大な計算量が原因で、計算不能になる。非特許文献1に記載されている方法がそのまま用いられた場合、大規模なシステムの変更計画の作成は困難である。

0013

特に、併せて計算することが求められる状態マシンの数を削減することによって変更計画の作成における計算量を削減する、特定の計画手段に適用が限定されない、一般的な計算の効率化手法を明らかにすることが課題である。

0014

そこで、本発明は、大規模なシステムの変更計画作成における計算量を削減できる高速変更計画システム、高速変更計画方法および高速変更計画プログラムを提供することを目的とする。

課題を解決するための手段

0015

本発明による高速変更計画システムは、1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部と、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する状態マシン群統合部とを含むことを特徴とする。

0016

本発明による高速変更計画方法は、1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合することを特徴とする。

0017

本発明による高速変更計画プログラムを記録した非一時的なコンピュータ読み取り可能な記録媒体は、コンピュータで実行されるときに、1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する高速変更計画プログラムを記憶する。

発明の効果

0018

本発明によれば、大規模なシステムの変更計画作成における計算量を削減できる。

図面の簡単な説明

0019

本発明による高速変更計画システムの第1の実施形態の構成例を示すブロック図である。
状態マシン群の概念を示す説明図である。
状態マシン群のテキストによる定義の一例を示す説明図である。
遷移順序の導出結果の一例を示す説明図である。
状態マシン群の分割により生成された状態マシングループ群の一例を示す説明図である。
統合された遷移順序を含む状態マシングループ群の一例を示す説明図である。
生成された仮状態マシンを含む状態マシングループの一例を示す説明図である。
状態マシングループごとの遷移順序の統合結果の一例を示す説明図である。
遷移順序の統合結果の単一の遷移順序への変換結果の一例を示す説明図である。
統合された遷移順序を含む状態マシングループ群の他の一例を示す説明図である。
生成された仮状態マシンを含む状態マシングループの他の一例を示す説明図である。
状態マシングループごとの遷移順序の統合結果の他の一例を示す説明図である。
遷移順序の統合結果の単一の遷移順序への変換結果の他の一例を示す説明図である。
高速変更計画システム100による状態マシン群の変更計画処理の動作を示すフローチャートである。
高速変更計画システム100による状態マシン群の分割処理の動作を示すフローチャートである。
高速変更計画システム100による状態マシンの状態マシングループ割り当て処理の動作を示すフローチャートである。
状態マシンの状態マシングループへの割り当て時に使用されるスタックの一例を示す説明図である。
高速変更計画システム100による遷移順序の導出処理統合処理の動作を示すフローチャートである。
本発明による高速変更計画システムの第2の実施形態の構成例を示すブロック図である。
遷移順序を並列計算可能な状態マシングループ群の一例を示す説明図である。
本発明による高速変更計画システムの概要を示すブロック図である。

実施例

0020

実施形態1.
[構成の説明]
以下、本発明の第1の実施形態を、図面を参照して説明する。図1は、本発明による高速変更計画システムの第1の実施形態の構成例を示すブロック図である。図1に示す高速変更計画システム100は、状態マシン群分割部101と、状態マシン群統合部102とを含む。

0021

状態マシン群分割部101は、状態マシン群を状態マシングループ群に分割する機能を有する。

0022

状態マシン群統合部102は、状態マシングループごとに導出された遷移順序を統合する機能を有する。

0023

状態マシン群統合部102は、状態マシン群分割部101と通信ネットワークなどを介して通信可能に接続されている。また、状態マシン群統合部102は、高速変更計画システム100の外部に存在する入出力部201および遷移順序導出部202とも、通信ネットワークなどを介して通信可能に接続されている。

0024

遷移順序導出部202は、状態マシン間の遷移条件を満たしつつ、要求状態が指定された全ての状態マシンを要求状態に遷移させる遷移順序を導出する機能を有する。

0025

状態マシン群統合部102は、入出力部201を介して入力された状態マシン群を受信する。状態マシン群統合部102は、受信した状態マシン群を、状態マシン群分割部101に出力する。

0026

状態マシン群分割部101は、入力された状態マシン群を、複数の状態マシンを含む状態マシングループにそれぞれ分割する。状態マシン群分割部101は、生成した状態マシングループ群を状態マシン群統合部102に返す。

0027

次いで、状態マシン群統合部102は、入力された状態マシングループ群から状態マシングループを一つずつ順に取り出す。状態マシン群統合部102は、取り出した状態マシングループを遷移順序導出部202に送信する。

0028

遷移順序導出部202は、受信した状態マシングループに基づいて遷移順序を導出する。遷移順序導出部202は、導出した遷移順序を状態マシン群統合部102に返す。

0029

次いで、状態マシン群統合部102は、遷移順序導出部202から受信した複数の遷移順序を統合する。状態マシン群統合部102は、統合した遷移順序を単一の遷移順序に変換する。統合と変換を繰り返した後、状態マシン群統合部102は、最終的に得られた単一の遷移順序を入出力部201に送信する。入出力部201は、受信した遷移順序を出力する。

0030

本実施形態における状態マシン群は、管理対象になるシステム、および管理対象になるシステムに対する変更要求に対応する。状態マシン群は、1または複数の状態マシンから構成される。状態マシンは、システムを構成する部品を示す。

0031

状態マシンは、複数の状態をとりうる。状態は、同一状態マシン内の他の状態に遷移可能である。状態マシンには、必ず1つの現在状態があり、状態マシンは、任意個(0でもよい。)の要求状態に遷移可能である。すなわち、状態マシンは、複数の状態を含むといえる。ただし、要求状態が複数指定された場合、要求状態は、指定されたいずれかの状態であればよい。要求状態が指定されない場合、要求状態は、どの状態でもよい。また、遷移の遷移条件は、遷移が含まれる状態マシン以外の状態マシン内の状態によって指定される。

0032

図2は、状態マシン群の概念を示す説明図である。図2において、状態マシンを長方形で表す。また、状態を楕円形で表す。また、遷移を実線の矢印で表す。また、遷移条件を点線の矢印で表す。また、現在状態を破線の楕円形で表す。また、要求状態を黒塗りの楕円形で表す。また、遷移を示す矢印の途中に存在する丸印は、遷移条件の矢印の始点を示す。他の図においても、図2と同じ方法で状態マシンなどが示される。

0033

図2は、"e1"と"e2"の2つの状態マシンから構成される状態マシン群を示す。"e1"と"e2"は、共に"s1"と"s2"の2つの状態を含む。

0034

図2に示すように、"e1"における"s1"は、"s2"への遷移を含む。また、"e2"における"s1"と"s2"は、互いの状態への遷移を含む。また、"e2"の"s1"から"s2"への遷移は、"e1"の状態"s2"を遷移条件にする。また、"e1"は、"s1"を現在状態にする。また、"e2"は、"s1"を現在状態にし、"s2"を要求状態にする。

0035

以下、便宜的に、例えば、状態マシン"e1"の状態"s1"のことを"e1(s1)"と記載する。また、状態マシン"e1"の状態"s1"から状態"s2"への遷移を、"e1(s1,s2)"と記載する。

0036

図3は、状態マシン群のテキストによる定義の一例を示す説明図である。図3は、XML(Extensible Markup Language)形式を用いた表現の一例として、図2に示す状態マシン群の定義例を示す。

0037

図3に示すように、例えば、状態マシンは、"stateMachine"タグによって表される。また、状態マシンのIDは、"stateMachine"の"id"属性によって表される。また、状態マシンが持つ状態は、"stateMachine"タグの子要素としての"state"タグによって表される。また、状態のIDは、"state"の"id"属性によって表される。

0038

また、図3に示すように、状態が持つ遷移は、"state"タグの子要素としての"transition"タグによって表される。また、遷移先の状態を示すIDは、"transition"の"to"属性によって表される。

0039

また、図3に示すように、遷移が持つ遷移条件は、"transition"タグの子要素としての"conditions"タグによって表される。遷移が状態マシン"e1"の状態"s2"を遷移条件にする場合、遷移条件は、"conditions"タグの子要素として"depends"タグを記述し、"depends"の"on"属性に"e1(s2)"を記述することによって表される。1つの遷移が複数の遷移条件を持つ場合、複数の遷移条件を記述するには、"conditions"タグの子要素として複数の"depends"タグを記述すればよい。

0040

本実施形態における状態マシン群に基づくシステムの変更計画の作成は、常に全ての遷移条件を満たしつつ、要求状態が指定された全ての状態マシンの状態を現在状態から要求状態へ遷移させるような遷移順序を発見することによって達成される。図2に示す状態マシン群の例であれば、"(e1(s1,s2), e2(s1,s2))"という遷移順序が、最も単純な唯一の解になる。

0041

図4は、遷移順序の導出結果の一例を示す説明図である。図4において、角丸四角形は遷移を示す。また、遷移間の矢印は、遷移間の依存性を表す。すなわち、遷移間の矢印は、"e1(s1,s2)"が実施された後にのみ"e2(s1,s2)"が実施されるという関係性を示す。

0042

図5は、状態マシン群の分割により生成された状態マシングループ群の一例を示す説明図である。図5は、"e1"と"e2"と"e3"と"e4"の4つの状態マシンから構成される状態マシン群が、"G1"と"G2"と"G3"の3つの状態マシングループに分割された様子を示す。なお、図5図2と異なり、状態マシン自体から他の状態マシン内の状態に関連する遷移条件に対応する矢印を示す。矢印は、状態マシン内の全ての遷移が、矢印に対応する遷移条件と同様の遷移条件を持つことを示す。

0043

本実施形態における遷移条件は、遷移条件として状態が指定される状態マシンに対して、指定された状態への遷移を誘発する。誘発する側の状態マシンと誘発される側の状態マシンの関係が一方的である場合、誘発する側の状態マシンの遷移順序を決定した後に、誘発される側の状態マシンの遷移順序を決定しても、最終的に得られる遷移順序に影響はない。しかし、互いに遷移を誘発する複数の状態マシンを含む状態マシン群の場合、状態マシン間の全ての関係を考慮しつつ遷移順序を決定することが求められる。

0044

そこで、本実施形態における状態マシン群の分割は、状態マシン間の複数の遷移条件が循環を構成しているか否かが考慮された上で実施される。複数の遷移条件が循環を構成する全ての状態マシンが同一の状態マシングループに属するように、状態マシン群は分割される。

0045

図5に示す例では、例えば、"e1"は"e2"への遷移条件を持つが、"e2"から派生する遷移条件を辿って"e1"へ至ることはない。よって、"e1"と"e2"との間に遷移条件の循環は構成されていないため、"e1"と"e2"は、異なる状態マシングループに分割される。

0046

また、図5に示す"e2"は"e3"への遷移条件を持ち、"e3"は"e2"への遷移条件を持つ。よって、"e2"と"e3"との間に遷移条件の循環が構成されているため、"e2"と"e3"は同一の状態マシングループに組み込まれる。

0047

なお、図5に示すような"e2"から"e4"に対する遷移条件ではなく、"e4"から"e2"に対する遷移条件がもし定義されていれば、"e2"と"e3"と"e4"との間に遷移条件の循環が成立する。よって、"e4"から"e2"に対する遷移条件が定義された場合、"e2"と"e3"と"e4"の3つの状態マシンが、同一の状態マシングループに組み込まれる。

0048

状態マシン群統合部102は、遷移順序導出部202を用いて、生成された状態マシングループにおける遷移順序を計算する。また、状態マシン群統合部102は、計算された遷移順序を統合する。

0049

図6は、統合された遷移順序を含む状態マシングループ群の一例を示す説明図である。遷移順序は、遷移を誘発する側の状態マシンを含む状態マシングループの方が先に決定される必要がある。よって、遷移順序は、遷移条件を指定する側の状態マシンである状態マシン"e1"を含む状態マシングループ"G1"に関して最初に計算される。

0050

状態マシングループ"G1"における遷移順序が計算された後、次に状態マシングループ"G2"、最後に状態マシングループ"G3"の順で遷移順序が計算される。計算された状態マシングループ"G1"における遷移順序は、単に1つの遷移"e1(s1,s2)"になる。

0051

"e1(s1,s2)"は、状態マシングループ"G2"内の状態マシンである"e2"に対する遷移条件を含む。よって、状態マシングループ"G2"における遷移順序の計算時には、遷移"e1(s1,s2)"が考慮される必要がある。

0052

そこで、状態マシン群統合部102は、遷移順序を計算する状態マシングループ内の状態マシンに遷移条件を持つ遷移を、暫定結果の遷移順序から抽出する。状態マシン群統合部102は、抽出した遷移に仮の状態をつなげることで仮状態マシンを構成する。状態マシン群統合部102は、計算対象の状態マシングループに仮状態マシンも加えて、遷移順序を計算する。

0053

図7は、生成された仮状態マシンを含む状態マシングループの一例を示す説明図である。図7は、図6に示す遷移"e1(s1,s2)"に基づいて、仮の状態"p1"と"p2"がつなげられた仮状態マシン"pseud"が構成され、"pseud"が状態マシングループ"G2"に追加された様子を示す。図7に示す吹き出しは、遷移"e1(s1,s2)"に基づいて、仮の状態"p1"と"p2"がつなげられていることを意味する。

0054

図7に示すような状態マシングループを元に遷移順序を計算すると、仮の遷移を含む遷移順序が得られる。図8は、状態マシングループごとの遷移順序の統合結果の一例を示す説明図である。

0055

図8に示す、状態マシングループ"G2"内の遷移順序は、図7に示す状態マシングループ"G2"から生成された、仮の遷移を含む遷移順序である。状態マシングループ"G2"内の点線の長方形が、仮の遷移に対応する。図8は、状態マシングループ"G2"内の仮の遷移が、状態マシングループ"G1"内の"e1(s1,s2)"であることを示す。

0056

状態マシン群統合部102は、仮の遷移が持つ他の遷移との依存関係を元の遷移に移行することによって、各状態マシングループから得られる遷移順序を統合する。図9は、遷移順序の統合結果の単一の遷移順序への変換結果の一例を示す説明図である。図9は、図8に示す2つの状態マシングループ"G1"と"G2"の遷移順序が、単一の遷移順序に変換された結果を示す。

0057

図10は、統合された遷移順序を含む状態マシングループ群の他の一例を示す説明図である。図10は、各遷移順序が統合された状態マシングループ"G1"、"G2"と、状態マシングループ"G3"との関係性を示す。

0058

図10に示す遷移順序を構成する遷移には、状態マシングループ"G3"内の状態マシンに対して遷移条件を持つ2つの遷移が含まれる。状態マシン群統合部102は、状態マシングループ"G3"における遷移順序の計算時に、遷移条件を持つ2つの遷移を仮の遷移として持つ仮状態マシンを構成する。

0059

図11は、生成された仮状態マシンを含む状態マシングループの他の一例を示す説明図である。図11は、状態マシングループ"G3"における遷移順序の計算時に用いられる、仮状態マシンを含む状態マシングループ"G3"の様子を示す。

0060

図11は、仮状態マシン"pseud"が状態マシングループ"G3"に追加された様子を示す。図11に示す仮状態マシン"pseud"は、図10に示す遷移"e2(s1,s2)"に基づいて仮の状態"p3"と"p4"がつなげられ、図10に示す遷移"e3(s1,s2)"に基づいて仮の状態"p4"と"p5"がつなげられることによって構成される。図11に示す各吹き出しは、遷移"e2(s1,s2)"に基づいて仮の状態"p3"と"p4"がつなげられていること、遷移"e3(s1,s2)"に基づいて仮の状態"p4"と"p5"がつなげられていることをそれぞれ意味する。

0061

図12は、状態マシングループごとの遷移順序の統合結果の他の一例を示す説明図である。図12は、計算結果として得られた状態マシングループ"G3"における遷移順序と、状態マシングループ"G1"と"G2"から得られた遷移順序との関係性を示す。

0062

図12に示す状態マシングループ"G3"内の遷移順序は、図11に示す状態マシングループ"G3"から生成された、仮の遷移を含む遷移順序である。図12は、状態マシングループ"G3"内の2つの仮の遷移がそれぞれ、状態マシングループ"G1&G2"内の"e2(s1,s2)"、"e3(s1,s2)"であることを示す。

0063

図13は、遷移順序の統合結果の単一の遷移順序への変換結果の他の一例を示す説明図である。図13は、図12に示す統合された2つの状態マシングループ"G1&G2"と"G3"の遷移順序が変換された単一の遷移順序を示す。図13に示す遷移順序が、状態マシングループ"G1"、"G2"、"G3"から得られる全ての遷移順序が統合された最終的な結果である。

0064

上記の分割処理と統合処理によって、4つの状態マシンに基づく遷移順序の計算が、状態マシングループ"G1"における遷移順序の計算と、状態マシングループ"G2"における遷移順序の計算と、状態マシングループ"G3"における遷移順序の計算とに分割される。

0065

状態マシングループ"G1"における遷移順序の計算は、1つの状態マシンに基づく。状態マシングループ"G2"における遷移順序の計算は、仮状態マシンも含めると、3つの状態マシンに基づく。状態マシングループ"G3"における遷移順序の計算は、仮状態マシンも含めると、2つの状態マシンに基づく。すなわち、遷移順序の計算において、併せて計算される状態マシンの数が減少する。

0066

なお、本実施形態の状態マシン群分割部101および状態マシン群統合部102は、例えば、非一時的なコンピュータ読み取り可能な記録媒体に記憶されたプログラムの制御に従って処理を実行するCPU(Central Processing Unit)によって実現される。

0067

[動作の説明]
以下、本実施形態の高速変更計画システム100の動作を図14を参照して説明する。図14は、高速変更計画システム100による状態マシン群の変更計画処理の動作を示すフローチャートである。

0068

状態マシン群統合部102は、入出力部201から状態マシン群の情報を受信する。状態マシン群統合部102は、受信した状態マシン群の情報を状態マシン群分割部101に出力する。

0069

状態マシン群分割部101は、入力された状態マシン群を、複数の状態マシングループに分割する。状態マシン群分割部101は、生成した状態マシングループ群を状態マシン群統合部102に返す(ステップS101)。

0070

次いで、状態マシン群統合部102は、入力された状態マシングループ群から、遷移順序を計算可能な状態マシングループを一つずつ取得する。遷移順序を計算可能な状態マシングループは、状態マシングループ内の状態マシンに遷移条件を持ち、かつ遷移順序が未計算の状態マシングループとの間に依存性がない状態マシングループである。

0071

上記の状態マシングループ間の依存性は、例えば、所定の状態マシングループと、所定の状態マシングループにおける遷移順序を計算するために事前に遷移順序を計算することが求められる状態マシングループとの関係に相当する。

0072

状態マシン群統合部102は、状態マシングループにおける遷移順序の計算処理と、計算された遷移順序の統合処理を、全ての状態マシングループに対して繰り返し行う。

0073

状態マシン群統合部102は、全ての状態マシングループにおける遷移順序が統合済みであるか否かを判断する(ステップS102)。全ての状態マシングループにおける遷移順序が統合済みである場合(ステップS102におけるYES)、状態マシン群統合部102は、得られた遷移順序の統合結果を最終的な結果として、処理を終了する。

0074

全ての状態マシングループにおける遷移順序が統合済みではない場合(ステップS102におけるNO)、状態マシン群統合部102は、遷移順序を計算可能な任意の未計算の状態マシングループを一つ取得する。状態マシン群統合部102は、取得した状態マシングループにおける遷移順序を計算し、計算された遷移順序を暫定結果に統合する(ステップS103)。統合した後、状態マシン群統合部102は、再度ステップS102における処理を行う。

0075

次に、ステップS101における処理を図15を参照して具体的に説明する。図15は、高速変更計画システム100による状態マシン群の分割処理の動作を示すフローチャートである。

0076

状態マシン群分割部101は、入力された状態マシン群から状態マシンを一つずつ取得する。状態マシン群分割部101は、取得した状態マシンを、適切な状態マシングループに割り当てる。状態マシン群分割部101は、割り当て処理を全ての状態マシンに対して繰り返し行う。

0077

状態マシン群分割部101は、入力された状態マシン群に含まれる全ての状態マシンを状態マシングループに割り当て済みであるか否かを判断する(ステップS111)。全ての状態マシンを状態マシングループに割り当て済みである場合(ステップS111におけるYES)、状態マシン群分割部101は、状態マシンを割り当てた結果を最終結果として、処理を終了する。

0078

全ての状態マシンを状態マシングループに割り当て済みではない場合(ステップS111におけるNO)、状態マシン群分割部101は、任意の未割り当ての状態マシンを一つ取得する。状態マシン群分割部101は、取得した状態マシンを状態マシングループに割り当てる(ステップS112)。

0079

ステップS112における状態マシンを状態マシングループに割り当てるプロセスは、プロセス内で割り当てる状態マシンに関連する他の状態マシンを状態マシングループに割り当てるプロセスを呼び出すという、プロセスの再起呼び出し構造をとる。

0080

すなわち、プロセスの呼び出しのループが発生する場合、ループにおける再起呼び出しの停止が求められる。呼び出しがループしていることを判断するために、状態マシン群分割部101は、プロセスの呼び出し時に、処理中の状態マシンの連鎖の情報を含むスタック型のデータを渡す。

0081

最初のステップS112における処理において、状態マシン群分割部101は、状態マシンを状態マシングループに割り当てるプロセスを最初に呼び出す。すなわち、状態マシン群分割部101は、空のスタック型のデータと共にプロセスを呼び出す。状態マシンを状態マシングループに割り当てた後、状態マシン群分割部101は、再度ステップS111における処理を行う。

0082

次に、ステップS112における処理を図16を参照して具体的に説明する。図16は、高速変更計画システム100による状態マシンの状態マシングループ割り当て処理の動作を示すフローチャートである。

0083

状態マシン群分割部101は、処理対象の状態マシンがスタックに含まれているか否かを判断する(ステップS121)。処理対象の状態マシンがスタックに含まれている場合(ステップS121におけるYES)、状態マシン群分割部101は、処理対象の状態マシンが、状態マシングループへの割り当て処理中であって遷移条件の循環を構成する状態マシンの一つであると判断する。

0084

状態マシン群分割部101は、遷移条件の循環を構成する全ての状態マシンを、処理対象の状態マシンと同一の状態マシングループに再度割り当てる(ステップS122)。状態マシンを同一の状態マシングループに割り当てた後、状態マシン群分割部101は、処理を終了する。

0085

図17は、状態マシンの状態マシングループへの割り当て時に使用されるスタックの一例を示す説明図である。図17に示す上側のスタックは、状態マシン"e1"の割り当て処理中に状態マシン"e2"の割り当て処理が呼ばれ、さらに、状態マシン"e2"の割り当て処理中に状態マシン"e3"の割り当て処理が呼ばれた場合のスタックの様子を示す。

0086

図17に示す下側のスタックは、上側のスタックが示す状況からさらに、状態マシン"e3"の割り当て処理中に状態マシン"e2"の割り当て処理が呼ばれた場合のスタックの様子を示す。

0087

状態マシン群分割部101は、例えば、図17に示す下側のスタック型のデータから、新たな割り当て処理の対象である状態マシン"e2"がスタックに含まれていると判断する。判断した後、状態マシン群分割部101は、スタックの一番上に詰まれた状態マシンから、新たな割り当て処理の対象である状態マシン"e2"までの間にある全ての状態マシンを、状態マシン"e2"と同一の状態マシングループに再度割り当てる。

0088

全ての状態マシンを同一の状態マシングループに再度割り当てる際に、再度割り当てられる状態マシンが属していた状態マシングループに別の状態マシンが含まれている場合、状態マシン群分割部101は、含まれている別の状態マシンも新たな状態マシングループに再度割り当てる。

0089

処理対象の状態マシンがスタックに含まれていない場合(ステップS121におけるNO)、状態マシン群分割部101は、処理対象の状態マシンを、処理対象の状態マシンのみが含まれる新たな状態マシングループに割り当てる(ステップS123)。

0090

次いで、状態マシン群分割部101は、処理対象の状態マシン内の状態が遷移する際に従う遷移条件が指定する他の状態マシンを一つずつ取得する。取得される他の状態マシンは、遷移が依存する状態マシンである。

0091

状態マシン群分割部101は、取得した他の状態マシンをステップS123で割り当てた新たな状態マシングループに割り当てる。状態マシン群分割部101は、割り当て処理を、処理対象の状態マシン内の遷移が依存する全ての状態マシンに対して繰り返し行う。

0092

すなわち、状態マシン群分割部101は、処理対象の状態マシン内の遷移が依存する全ての状態マシンに対して、割り当て処理を実施済みであるか否かを判断する(ステップS124)。遷移が依存する全ての状態マシンに対して、割り当て処理を実施済みである場合(ステップS124におけるYES)、状態マシン群分割部101は、処理を終了する。

0093

遷移が依存する全ての状態マシンに対して、割り当て処理を実施済みではない場合(ステップS124におけるNO)、状態マシン群分割部101は、遷移が依存する実施済みではない状態マシンに対して割り当て処理を実施する(ステップS125)。割り当て処理を実施した後、状態マシン群分割部101は、再度ステップS124における処理を実施する。

0094

次に、ステップS103における処理を図18を参照して具体的に説明する。図18は、高速変更計画システム100による遷移順序の導出処理と統合処理の動作を示すフローチャートである。

0095

状態マシン群統合部102は、処理対象の状態マシングループ内の状態マシンに対して遷移条件を指定する、暫定結果の遷移順序内の全ての遷移を、遷移順序通りに取得する。状態マシン群統合部102は、取得した遷移が任意の状態ではさまれるように、仮の状態を生成し、遷移と仮の状態とを関連付けることによって仮状態マシンを生成する(ステップS131)。

0096

次いで、状態マシン群統合部102は、仮状態マシンを含む処理対象の状態マシングループを、遷移順序導出部202に送信する。状態マシン群統合部102は、遷移順序導出部202から、送信した状態マシングループにおける遷移順序を取得する(ステップS132)。

0097

次いで、状態マシン群統合部102は、取得した遷移順序内の、全ての仮状態マシン由来の遷移に関連する依存性を元の遷移に付け替えることによって、取得した遷移順序を暫定結果に統合する(ステップS133)。暫定結果に統合した後、状態マシン群統合部102は、処理を終了する。

0098

[効果の説明]
本実施形態における高速変更計画システムは、状態マシン群の遷移順序を計算する際、併せて計算することが求められる状態マシンの数を削減できる。併せて計算することが求められる状態マシンの数が削減されることによって、全ての状態マシンを対象にした変更計画作成に求められる計算量が減少し、変更計画の作成が効率化される。

0099

実施形態2.
[構成の説明]
以下、本発明の第2の実施形態を、図面を参照して説明する。図19は、本発明による高速変更計画システムの第2の実施形態の構成例を示すブロック図である。図19において、第1の実施形態と同様の構成要素には同一の符号を付し、説明を省略する。

0100

図19に示すように、本実施形態における高速変更計画システム100の構成は、第1の実施形態における高速変更計画システム100の構成と同様である。しかし、本実施形態において、遷移順序導出部202が高速変更計画システム100外部の計算機プール203と接続されている点が、第1の実施形態と異なる。

0101

遷移順序導出部202は、計算機プール203と通信ネットワークなどを介して通信可能に接続されている。接続されている場合、遷移順序導出部202は、計算機プール203を用いて、遷移順序を計算する。計算機プール203の処理能力が高い場合、遷移順序導出部202は、例えば、並列的に複数の状態マシングループにおける遷移順序を計算できる。

0102

本実施形態における状態マシン群統合部102は、同時に遷移順序を計算できる複数の状態マシングループにおける各遷移順序の計算処理を、同時実行的に実施するように遷移順序導出部202に依頼する。

0103

図20は、遷移順序を並列計算可能な状態マシングループ群の一例を示す説明図である。第1の実施形態で説明したように、状態マシングループにおける遷移順序は、状態マシングループ内の状態マシンに遷移条件を持ち、遷移順序が未計算の状態マシングループとの間に依存性を持たない場合に、計算される。

0104

図20に示す例では、状態マシングループ"G1"のみが、他の状態マシングループとの間に依存性を持たない状態マシングループである。よって、分割直後の状態において、遷移順序導出部202は、状態マシングループ"G1"に対してのみ遷移順序を計算できる。

0105

状態マシングループ"G1"における遷移順序の計算を終了した後、遷移順序導出部202は、状態マシングループ"G1"に対してのみ依存性を持つ状態マシングループ"G2"および"G3"における遷移順序を計算できる。

0106

図20に示す状態マシングループ"G2"と"G3"との間には依存性が存在しないため、遷移順序導出部202は、状態マシングループ"G2"と"G3"における遷移順序を同時に計算できる。

0107

また、状態マシングループ"G2"と"G3"における遷移順序の計算が終了した後、遷移順序導出部202は、状態マシングループ"G4"と"G5"における遷移順序を同時に計算できる。

0108

また、状態マシングループ"G4"と"G5"における遷移順序の計算が終了した後、遷移順序導出部202は、状態マシングループ"G6"と"G7"における遷移順序を同時に計算できる。

0109

状態マシン群統合部102は、遷移順序を計算可能な状態マシングループが複数発生した場合、発生した状態マシングループを連続して遷移順序導出部202に送信する。また、状態マシン群統合部102は、遷移順序導出部202から受信した遷移順序の計算結果を、逐次暫定結果の遷移順序に統合する。

0110

[動作の説明]
以下、本実施形態の高速変更計画システム100の動作を図14図18を参照して説明する。本実施形態における高速変更計画システム100による変更計画処理は、基本的に第1の実施形態における変更計画処理と同様である。

0111

しかし、遷移順序の導出と遷移順序の統合を行うステップS103における処理が、第1の実施形態のステップS103における処理と異なる。以下、本実施形態のステップS103における処理を説明する。第1の実施形態における処理と同様の処理が行われるステップには、第1の実施形態と同様の符号を付し、説明を省略する。

0112

本実施形態における状態マシン群統合部102は、入力された状態マシングループ群の内、遷移順序を計算可能な状態マシングループを、所定の限度数まで取得する。所定の限度数は、遷移順序導出部202が計算機プール203を用いて並列的に計算できる状態マシングループの最大数である。状態マシン群統合部102は、遷移順序導出部202を用いた複数の状態マシングループにおける遷移順序の計算処理と、計算された遷移順序の統合処理を、全ての状態マシングループに対する計算が完了するまで繰り返し行う。

0113

すなわち、全ての状態マシングループにおける遷移順序が統合済みではない場合(ステップS102におけるNO)、状態マシン群統合部102は、遷移順序を計算可能な未計算の状態マシングループを、所定の限度数まで取得する。

0114

取得された複数の状態マシングループに対して、仮状態マシンの生成(ステップS131)と、遷移順序の計算(ステップS132)が連続的に実施される。状態マシン群統合部102は、遷移順序導出部202から特定の状態マシングループに関する遷移順序を受信すると、直ちに受信した遷移順序を暫定結果の遷移順序に統合する(ステップS133)。統合した後、状態マシン群統合部102は、再度ステップS102における処理を実施する。

0115

[効果の説明]
本実施形態の高速変更計画システムは、同時に遷移順序を計算できる複数の状態マシングループが存在し、かつ複数の状態マシングループにおける各遷移順序を並列的に計算できる計算機プールが存在する場合、結果を導出するための全ての計算を高速化できる。

0116

次に、本発明の概要を説明する。図21は、本発明による高速変更計画システムの概要を示すブロック図である。本発明による高速変更計画システム10は、1または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部11(例えば、状態マシン群分割部101)と、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する状態マシン群統合部12(例えば、状態マシン群統合部102)とを含む。

0117

そのような構成により、高速変更計画システムは、大規模なシステムの変更計画作成における計算量を削減できる。

0118

また、状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、当該状態マシン以外の状態マシンに関連し、状態マシン群分割部11は、複数の状態マシンに含まれる1つの状態マシンから、複数の状態マシン間の遷移条件が関連する状態マシンを、遷移条件の数だけ順に辿った時に1つの状態マシンに戻る場合、複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割してもよい。

0119

そのような構成により、高速変更計画システムは、状態マシン群に含まれる状態マシン間の複数の遷移条件の循環に基づいて、併せて計算することが求められる状態マシン同士のみから構成される小グループに、状態マシン群を分割できる。

0120

また、状態マシン群分割部11は、状態マシングループ内の状態マシンに関連する遷移条件に従って遷移する状態を含む仮状態マシンを状態マシングループに追加し、状態マシン群統合部12は、仮状態マシンの元である状態マシングループから導出された遷移順序と、仮状態マシンが追加された状態マシングループから導出された遷移順序とを統合してもよい。

0121

そのような構成により、高速変更計画システムは、状態マシングループ間の遷移条件を考慮した上で、遷移順序を統合できる。

0122

また、状態マシン群統合部12は、所定の条件に従う状態マシングループが複数ある場合、複数の状態マシングループから遷移順序をそれぞれ導出する処理を並列的に行う指示を外部装置に出力してもよい。

0123

そのような構成により、高速変更計画システムは、所定の条件に従う複数の状態マシングループを並列的に処理できる。

0124

また、所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されており、かつ他の状態マシングループから既に遷移順序が導出されていることでもよい。

0125

また、所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されていないことでもよい。

0126

そのような構成により、高速変更計画システムは、状態マシングループ間の依存性を考慮した上で、並列処理を実施できる。

0127

10、100高速変更計画システム
11、101状態マシン群分割部
12、102 状態マシン群統合部
201入出力部
202遷移順序導出部
203 計算機プール

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 富士通株式会社の「 情報処理装置、ブート方法及びブートプログラム」が 公開されました。( 2020/02/13)

    【課題】レガシーブートにおいてMMIO−Lが割り当てられるPCIデバイスの数を減らし、MMIO−L不足の発生を抑えること。【解決手段】前処理部47が、MMIO−Lを割り当てるルートポートを特定し、特定... 詳細

  • 富士通株式会社の「 分析支援方法および分析支援プログラム」が 公開されました。( 2020/02/13)

    【課題】システムのロジック変更箇所の特定を可能にする分析支援方法および分析支援プログラムを提供する。【解決手段】処理部12は、業務システム20を使用するユーザ60により指示されたロジックL1の業務シス... 詳細

  • トヨタ自動車株式会社の「 車載装置」が 公開されました。( 2020/02/13)

    【課題】プログラム更新のための通信量および所要時間を短縮できる車載装置を提供する。【解決手段】車載装置は、取得した更新データに基づいてプログラム更新を行う。車載装置は、プログラムを記憶する記憶部と、更... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ