(57)【特許請求の範囲】
【請求項１】
それぞれ要素値を含む複数の要素からなる配列の一部であって所定数の要素の列からなるブロックを取得するブロック取得手段と、
前記取得されたブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するブロックパラメータ決定手段と、
前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値に基づいて、前記ブロックが連結されてなる前記配列における部分和の最大値を算出する最大部分和算出手段と、
を含み、
前記ブロックパラメータ決定手段は、
前記取得されたブロックが区切られた複数の副ブロックのそれぞれについて求められた要素値の総和が並んで配置されレジスタに格納される総和ブロックと、前記複数の副ブロックのそれぞれについて求められた部分和の最大値が並んで配置されレジスタに格納される最大ブロックと、前記複数の副ブロックのそれぞれについて求められた先頭要素からの部分和の最大値が並んで配置されレジスタに格納される先頭最大ブロックと、前記複数の副ブロックのそれぞれについて求められた末尾要素までの部分和の最大値が並んで配置されレジスタに格納される末尾最大ブロックとを生成する初期処理手段と、
レジスタに格納される複数の副ブロックの値を一括して操作する所定のプロセッサ命令により、前記複数の副ブロックについての前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックを操作することで、隣り合う２つの前記副ブロックが連結された新たな副ブロックを含む新たな複数の副ブロックについて、複数のレジスタにそれぞれ格納される新たな総和ブロック、新たな最大ブロック、新たな先頭最大ブロック、および新たな末尾最大ブロックを算出する処理を繰り返し実行する、繰返処理手段と、
前記処理が所定の回数実行された場合に、前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定する決定手段と、を含む、
情報処理装置。
【請求項２】
請求項１に記載の情報処理装置において、
前記繰返処理手段は、所定の複数のプロセッサ命令により、
前記隣り合う２つの前記副ブロックのうち先頭側にある前ブロックについての要素値の総和、および、前記隣り合う２つの前記副ブロックのうち末尾側にある後ブロックについての要素値の総和の和が、前記新たな副ブロックについての要素値の総和として配置される新たな総和ブロックを算出し、
前記前ブロックについての要素値の総和、および、前記後ブロックについての先頭要素からの部分和の最大値の和と、前記前ブロックについての先頭要素からの部分和の最大値と、のうち大きい方が、前記新たな副ブロックについての先頭要素からの部分和の最大値として配置される新たな先頭最大ブロックを算出し、
前記後ブロックについての総和、および、前記前ブロックについての末尾要素までの部分和の最大値の和と、前記後ブロックについての末尾要素までの部分和の最大値と、のうち大きい方が、前記新たな副ブロックについての末尾要素までの部分和の最大値として配置される新たな末尾最大ブロックを算出し、
前記前ブロックについての末尾要素までの部分和の最大値および前記後ブロックについての先頭要素からの部分和の最大値の和と、前記前ブロックについての部分和の最大値と、前記後ブロックについての部分和の最大値と、のうち一番大きいものが、前記新たな副ブロックについての部分和の最大値として配置される新たな最大ブロックを算出する、
情報処理装置。
【請求項３】
請求項１に記載の情報処理装置において、
前記ブロック取得手段は、前記決定手段が前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定した後に、次のブロックを今回のブロックとして取得し、
前記ブロックパラメータ決定手段は、前記今回のブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定し、
前記最大部分和算出手段は、前記決定手段が前記今回のブロックにおける、要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するごとに、配列の先頭要素から前回のブロックの末尾要素までの要素群における部分和の最大値と、前記要素群における最終要素までの部分和の最大値と、前記今回のブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値とに基づいて、配列の先頭要素値から前記今回のブロックの末尾要素までの新たな要素群についての部分和の最大値、および当該新たな要素群についての最終要素までの部分和の最大値を求める、
情報処理装置。
【請求項４】
それぞれ要素値を含む複数の要素からなる配列の一部であって所定数の要素の列からなるブロックを取得するステップと、
前記取得されたブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するブロックパラメータ決定ステップと、
前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値に基づいて、前記ブロックが連結されてなる前記配列における部分和の最大値を算出するステップと、
を含み、
前記ブロックパラメータ決定ステップでは、
前記取得されたブロックが区切られた複数の副ブロックのそれぞれについて求められた要素値の総和が並んで配置されレジスタに格納される総和ブロックと、前記複数の副ブロックのそれぞれについて求められた部分和の最大値が並んで配置されレジスタに格納される最大ブロックと、前記複数の副ブロックのそれぞれについて求められた先頭要素からの部分和の最大値が並んで配置されレジスタに格納される先頭最大ブロックと、前記複数の副ブロックのそれぞれについて求められた末尾要素までの部分和の最大値が並んで配置されレジスタに格納される末尾最大ブロックとを生成し、
レジスタに格納される複数の副ブロックの値を一括して操作する所定のプロセッサ命令により、前記複数の副ブロックについての前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックを操作することで、隣り合う２つの前記副ブロックが連結された新たな副ブロックを含む新たな複数の副ブロックについて、複数のレジスタにそれぞれ格納される新たな総和ブロック、新たな最大ブロック、新たな先頭最大ブロック、および新たな末尾最大ブロックを算出する処理を繰り返し実行し、
前記処理が所定の回数実行された場合に、前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定する、
情報処理方法。
【請求項５】
それぞれ要素値を含む複数の要素からなる配列の一部であって所定数の要素の列からなるブロックを取得するブロック取得手段と、
前記取得されたブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するブロックパラメータ決定手段と、
前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値に基づいて、前記ブロックが連結されてなる前記配列における部分和の最大値を算出する最大部分和算出手段と、
としてコンピュータを機能させ、
前記ブロックパラメータ決定手段は、
前記取得されたブロックが区切られた複数の副ブロックのそれぞれについて求められた要素値の総和が並んで配置されレジスタに格納される総和ブロックと、前記複数の副ブロックのそれぞれについて求められた部分和の最大値が並んで配置されレジスタに格納される最大ブロックと、前記複数の副ブロックのそれぞれについて求められた先頭要素からの部分和の最大値が並んで配置されレジスタに格納される先頭最大ブロックと、前記複数の副ブロックのそれぞれについて求められた末尾要素までの部分和の最大値が並んで配置されレジスタに格納される末尾最大ブロックとを生成する初期処理手段と、
レジスタに格納される複数の副ブロックの値を一括して操作する所定のプロセッサ命令により、前記複数の副ブロックについての前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックを操作することで、隣り合う２つの前記副ブロックが連結された新たな副ブロックを含む新たな複数の副ブロックについて、複数のレジスタにそれぞれ格納される新たな総和ブロック、新たな最大ブロック、新たな先頭最大ブロック、および新たな末尾最大ブロックを算出する処理を繰り返し実行する、繰返処理手段と、
前記処理が所定の回数実行された場合に、前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定する決定手段と、を含む、
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
温度の変動の検出や画像の解析などに用いられる汎用的な解析手法として、配列の最大部分和の計算が存在する。この配列（以下では、この配列の要素数をｎとする）の最大部分和を求めるアルゴリズムとして、Kadaneの方法が知られており、その計算量はO(n)である。また、連続する２つの配列のそれぞれの最大部分和等の値を用いて、その２つの配列が結合されてなる配列の最大部分和等の値を求める手法(Smith)も存在する。【０００３】
非特許文献１にはKadaneによる最大部分和の計算手法が、非特許文献２にはSmithによる最大部分和の計算手法が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Jon Bentley, “programming pearls”, Communications of the ACM volume 27  Number 9, pp. 865-871, September 1984.
【非特許文献２】Douglas R. Smith, “Applications of a strategy for designing divide-and-conquer algorithms”, Science of Computer Programming 8, pp. 213-229, 1987.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
Kadaneの方法は処理を繰返すことにより最大部分和を求めており、今回の処理の結果を算出するためには前回の処理の結果を必要とする。このため、並列処理により処理時間を短縮することができない。一方、Smithでは再帰処理を用いたプログラムによる実装と専用のハードウェアによる処理とが開示されているに過ぎず、汎用的なハードウェアによる並列処理を具体的かつ実用的に実装することは検討されていなかった。【０００６】
本発明は上記課題を鑑みてなされたものであって、その目的は、プログラムによる並列処理により配列の最大部分和を高速に求めることができる情報処理装置、情報処理方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明にかかる情報処理装置は、それぞれ要素値を含む複数の要素からなる配列の一部であって所定数の要素の列からなるブロックを取得するブロック取得手段と、前記取得されたブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するブロックパラメータ決定手段と、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値に基づいて、前記ブロックが連結されてなる前記配列における部分和の最大値を算出する最大部分和算出手段と、を含み、前記ブロックパラメータ決定手段は、前記取得されたブロックが区切られた複数の副ブロックのそれぞれについて求められた要素値の総和が並んで配置されレジスタに格納される総和ブロックと、前記複数の副ブロックのそれぞれについて求められた部分和の最大値が並んで配置されレジスタに格納される最大ブロックと、前記複数の副ブロックのそれぞれについて求められた先頭要素からの部分和の最大値が並んで配置されレジスタに格納される先頭最大ブロックと、前記複数の副ブロックのそれぞれについて求められた末尾要素までの部分和の最大値が並んで配置されレジスタに格納される末尾最大ブロックとを生成する初期処理手段と、レジスタに格納される複数の副ブロックの値を一括して操作する所定のプロセッサ命令により、前記複数の副ブロックについての前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックを操作することで、隣り合う２つの前記副ブロックが連結された新たな副ブロックを含む新たな複数の副ブロックについて、複数のレジスタにそれぞれ格納される新たな総和ブロック、新たな最大ブロック、新たな先頭最大ブロック、および新たな末尾最大ブロックを算出する処理を繰り返し実行する、繰返処理手段と、前記処理が所定の回数実行された場合に、前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定する決定手段と、を含む。【０００８】
また、本発明にかかる情報処理方法は、それぞれ要素値を含む複数の要素からなる配列の一部であって所定数の要素の列からなるブロックを取得するステップと、前記取得されたブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するブロックパラメータ決定ステップと、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値に基づいて、前記ブロックが連結されてなる前記配列における部分和の最大値を算出するステップと、を含み、前記ブロックパラメータ決定ステップでは、前記取得されたブロックが区切られた複数の副ブロックのそれぞれについて求められた要素値の総和が並んで配置されレジスタに格納される総和ブロックと、前記複数の副ブロックのそれぞれについて求められた部分和の最大値が並んで配置されレジスタに格納される最大ブロックと、前記複数の副ブロックのそれぞれについて求められた先頭要素からの部分和の最大値が並んで配置されレジスタに格納される先頭最大ブロックと、前記複数の副ブロックのそれぞれについて求められた末尾要素までの部分和の最大値が並んで配置されレジスタに格納される末尾最大ブロックとを生成し、レジスタに格納される複数の副ブロックの値を一括して操作する所定のプロセッサ命令により、前記複数の副ブロックについての前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックを操作することで、隣り合う２つの前記副ブロックが連結された新たな副ブロックを含む新たな複数の副ブロックについて、複数のレジスタにそれぞれ格納される新たな総和ブロック、新たな最大ブロック、新たな先頭最大ブロック、および新たな末尾最大ブロックを算出する処理を繰り返し実行し、前記処理が所定の回数実行された場合に、前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定する。【０００９】
また、本発明にかかるプログラムは、それぞれ要素値を含む複数の要素からなる配列の一部であって所定数の要素の列からなるブロックを取得するブロック取得手段と、前記取得されたブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するブロックパラメータ決定手段と、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値に基づいて、前記ブロックが連結されてなる前記配列における部分和の最大値を算出する最大部分和算出手段と、としてコンピュータを機能させるためのプログラムであって、前記ブロックパラメータ決定手段は、前記取得されたブロックが区切られた複数の副ブロックのそれぞれについて求められた要素値の総和が並んで配置されレジスタに格納される総和ブロックと、前記複数の副ブロックのそれぞれについて求められた部分和の最大値が並んで配置されレジスタに格納される最大ブロックと、前記複数の副ブロックのそれぞれについて求められた先頭要素からの部分和の最大値が並んで配置されレジスタに格納される先頭最大ブロックと、前記複数の副ブロックのそれぞれについて求められた末尾要素までの部分和の最大値が並んで配置されレジスタに格納される末尾最大ブロックとを生成する初期処理手段と、レジスタに格納される複数の副ブロックの値を一括して操作する所定のプロセッサ命令により、前記複数の副ブロックについての前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックを操作することで、隣り合う２つの前記副ブロックが連結された新たな副ブロックを含む新たな複数の副ブロックについて、複数のレジスタにそれぞれ格納される新たな総和ブロック、新たな最大ブロック、新たな先頭最大ブロック、および新たな末尾最大ブロックを算出する処理を繰り返し実行する、繰返処理手段と、前記処理が所定の回数実行された場合に、前記総和ブロック、前記最大ブロック、前記先頭最大ブロック、および前記末尾最大ブロックに基づいて、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定する決定手段と、を含む。【００１０】
本発明によれば、プログラムによる並列処理により配列の最大部分和を高速に求めることができる。【００１１】
本発明の一態様では、前記繰返処理手段は、所定の複数のプロセッサ命令により、前記隣り合う２つの前記副ブロックのうち先頭側にある前ブロックについての要素値の総和、および、前記隣り合う２つの前記副ブロックのうち末尾側にある後ブロックについての要素値の総和の和が、前記新たな副ブロックについての要素値の総和として配置される新たな総和ブロックを算出し、前記前ブロックについての要素値の総和、および、前記後ブロックについての先頭要素からの部分和の最大値の和と、前記前ブロックについての先頭要素からの部分和の最大値と、のうち大きい方が、前記新たな副ブロックについての先頭要素からの部分和の最大値として配置される新たな先頭最大ブロックを算出し、前記後ブロックについての総和、および、前記前ブロックについての末尾要素までの部分和の最大値の和と、前記後ブロックについての末尾要素までの部分和の最大値と、のうち大きい方が、前記新たな副ブロックについての末尾要素までの部分和の最大値として配置される新たな末尾最大ブロックを算出し、前記前ブロックについての末尾要素までの部分和の最大値および前記後ブロックについての先頭要素からの部分和の最大値の和と、前記前ブロックについての部分和の最大値と、前記後ブロックについての部分和の最大値と、のうち一番大きいものが、前記新たな副ブロックについての部分和の最大値として配置される新たな最大ブロックを算出してもよい。【００１２】
本発明の一態様では、前記ブロック取得手段は、前記決定手段が前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定した後に、次のブロックを今回のブロックとして取得し、前記ブロックパラメータ決定手段は、前記今回のブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定し、前記最大部分和算出手段は、前記決定手段が前記今回のブロックにおける、要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定するごとに、配列の先頭要素から前回のブロックの末尾要素までの要素群における部分和の最大値と、前記要素群における最終要素までの部分和の最大値と、前記今回のブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値とに基づいて、配列の先頭要素値から前記今回のブロックの末尾要素までの新たな要素群についての部分和の最大値、および当該新たな要素群についての最終要素までの部分和の最大値を求めてもよい。【００１３】
この態様によれば、例えばストリーミング的に配列が少しずつ出力されるような場合であっても、これまでに出力された配列の最大部分和を効率的に求めることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態にかかる情報処理装置のハードウェア構成の一例を示す図である。
【図２】情報処理装置が実現する機能を示すブロック図である。
【図３】最大部分和の計算対象となる入力配列の一例を示す図である。
【図４】要素ブロックの一例を示す図である。
【図５】情報処理装置の処理の概要の一例を示すフロー図である。
【図６】ブロックパラメータ算出部の処理の一例を示すフロー図である。
【図７】繰返処理部の繰返処理におけるデータの状態を示す図である。
【図８】ブロックから上位ブロックを生成する処理を説明する図である。
【図９】ブロックから下位ブロックを生成する処理を説明する図である。
【発明を実施するための形態】
【００１５】
以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。以下では情報処理装置の例として、それぞれが符号付き整数値を有する要素の列である入力配列を取得し、その入力配列についての最大部分和を出力する装置を説明する。この例では特に説明しない限り、この入力配列のそれぞれの要素は、温度センサにより計測された温度と前回計測された温度との差分値であるとする。
【００１６】
ここで、最大部分和はそれぞれが値を有する要素の列である配列の部分列の和のうち最大のものである。最大部分和は、配列の要素の数をｎとした場合に、１≦ｖ≦ｗ≦ｎを満たす整数ｖ，ｗの組のそれぞれについて求められるｖ番目からｗ番目の要素の値の合計と０とのうちの最大値である。最大部分和は、要素の値が全て負の値であるような特殊な場合に０になり、この場合は、どの要素も合計の計算に用いられないことに相当する。また、例えば、配列のそれぞれの要素が温度センサにより計測された温度の前回の計測からの差分を示す場合には、最大部分和は温度上昇の最大の幅に相当する。
【００１７】
図１は、本発明の実施形態にかかる情報処理装置のハードウェア構成の一例を示す図である。本発明の実施形態にかかる情報処理装置は、例えばサーバコンピュータやパーソナルコンピュータである。情報処理装置は、プロセッサ１１、記憶部１２、通信部１３、入出力部１４、バス１５を含む。
【００１８】
プロセッサ１１は、記憶部１２に格納されているプログラムに従って動作する。またプロセッサ１１は通信部１３、入出力部１４を制御する。プロセッサ１１は、複数のデータを並列的に演算するＳＩＭＤ演算機能を有していてもよい。なお、上記プログラムは、インターネット等を介して提供されるものであってもよいし、フラッシュメモリやＤＶＤ−ＲＯＭ等のコンピュータで読み取り可能な記憶媒体に格納されて提供されるものであってもよい。
【００１９】
記憶部１２は、ＲＡＭやフラッシュメモリ等のメモリ素子やハードディスクドライブによって構成されている。記憶部１２は、上記プログラムを格納する。また、記憶部１２は、各部から入力される情報や演算結果を格納する。
【００２０】
通信部１３は、他の装置と通信する機能を実現するものであり、例えば有線ＬＡＮの集積回路やコネクタ端子、無線ＬＡＮの集積回路やアンテナなどにより構成されている。通信部１３は、プロセッサ１１の制御に基づいて、他の装置から受信した情報をプロセッサ１１や記憶部１２に入力し、他の装置に情報を送信する。
【００２１】
入出力部１４は、表示出力手段をコントロールするビデオコントローラや、入力デバイスからのデータを取得するコントローラなどにより構成される。入力デバイスとしては、キーボード、マウス、タッチパネルなどがある。入出力部１４は、プロセッサ１１の制御に基づいて、表示出力デバイスに表示データを出力し、入力デバイスをユーザが操作することにより入力されるデータを取得する。表示出力デバイスは例えば、外部に接続されるディスプレイ装置または情報処理装置に内蔵されるディスプレイパネルである。
【００２２】
バス１５は、プロセッサ１１と記憶部１２と通信部１３と入出力部１４とを接続し、それらの間でデータを含む信号を伝送する。
【００２３】
図２は、情報処理装置が実現する機能を示すブロック図である。情報処理装置は、機能的に、要素ブロック取得部５１と、ブロックパラメータ算出部５２と、最大部分和算出部５３と、結果出力部５４とを含む。またブロックパラメータ算出部５２は、機能的に、初期処理部５５、繰返処理部５６、パラメータ決定部５７を含む。本実施形態では、要素ブロック取得部５１、ブロックパラメータ算出部５２、最大部分和算出部５３、結果出力部５４は、プロセッサ１１が記憶部１２に格納されるプログラムを実行し、通信部１３や入出力部１４を制御することで実現される。
【００２４】
要素ブロック取得部５１は、予め定められた数の要素の列からなる要素ブロックＡを取得する。この要素の列は、それぞれ要素値を含む複数の要素からなる入力配列の一部である。要素ブロック取得部５１は、記憶部１２に予め格納された入力配列からその入力配列の一部を要素ブロックＡとして取得してもよいし、通信部１３を介して他のコンピュータからストリーミング形式で送信される要素ブロックＡを取得してもよいし、入出力部１４を介して測定デバイスから取得された一定期間の計測値から要素ブロックＡを生成してもよい。例えば、この入力配列に含まれる複数の要素は計測された温度の変動を時系列で示す情報であり、複数の要素のそれぞれには、１つ前の要素が示す温度を基準とした場合の温度の相対値が格納されている。計測開始時の温度の値と、入力配列とがあれば、温度を時系列で把握することが可能となる。入力配列は、株価の時系列の値を示すものであってもよいし、レーダーの反射波の測定値の列を示すものであってもよいし、電子商取引のＷｅｂサイトにおける、価格の差分や売上の値であってよい。入力配列が価格の差分や売上の値の場合には、価格変動や売上動向の分析が可能になる。
【００２５】
また、要素ブロック取得部５１は、絶対値が格納される配列を取得して、その取得された配列から入力配列を生成してもよい。ここで、絶対値は例えば温度の値といった計測値そのものを示し、相対値は、その相対値が格納される要素に対応する計測値からその要素の前の要素に対応する計測値の値を引いた値である。例えば、温度センサが計測値の絶対値の配列をネットワークを介して出力し、要素ブロック取得部５１が通信部１３を介してその配列を受信し、その絶対値の配列から差分値の配列を入力配列として生成してもよい。
【００２６】
一方、温度センサが今回計測された温度と前回計測された温度との差分を出力するような場合には、要素ブロック取得部５１は相対値が格納される入力配列を直接取得してもよい。例えば、温度センサを有する他のコンピュータが前回の測定値との差分値の配列を生成して送信し、要素ブロック取得部５１が通信部１３を介してその差分値の配列を入力配列として受信してもよい。
【００２７】
図３は、最大部分和の計算対象となる入力配列の一例を示す図である。本図に記載されている要素の数は１５であるが、実際にはもっと多くの数の要素を含む。図３の例のグラフにおける縦軸は計測値、横軸は時間であり、入力配列の各要素は、時系列で並んでいる。要素の値は、あるタイミングの計測値からその１つ前の計測値を引いた相対値である。このような入力配列の場合、相対値の最大部分和は、例えば時間が経つにつれて計測値が増加する量の最大値に相当する。なお、入力配列に計測値ではなく相対値を格納することにより、データのサイズが小さくなることは言うまでもない。
【００２８】
入力配列が温度の計測値などの時系列の値を含む場合には、入力配列の対象となる期間を１日などの所定の期間としてよい。ある入力配列の期間を過ぎると、次の期間を対象とする入力配列の要素にその時点の値が格納されるように入力配列が切り替わってもよい。切り替わった後の過去の期間に対応する入力配列が累積的に保存されてもよいし、最大部分和が計算された入力配列が削除されてもよい。
【００２９】
任意の要素ブロックＡに含まれる複数の要素は入力配列において連続している。いずれかの要素ブロックＡにおける末尾の要素の次の要素は、その要素ブロックＡの次の要素ブロックＡにおける先頭の要素である。また先頭を除くいずれかの要素ブロックＡにおける先頭の要素の１つ前の要素は、その要素ブロックＡの前の要素ブロックＡにおける末尾の要素である。
【００３０】
ここで、１つの要素ブロックＡの大きさはプロセッサ１１のレジスタの有効なビット数であるワード長と同じである。以下では、ワード長をｗ、各要素のビット数をｍ（ｍはｗの半分以下とする）と表記する。１つの要素ブロックＡに含まれる要素の数αは（ｗ／ｍ）の小数点以下を切り捨てた値である。ワード長ｗおよび要素のビット数ｍが２のべき乗の場合は、αは単に（ｗ／ｍ）である。より具体的には、例えば、ワード長ｗが１２８ビット、要素が４ビットの符号付き整数であれば、要素の数αは３２となる。ｉ番目の要素ブロックＡには、入力配列における［（ｉ−１）×α＋１］番目から（ｉ×α）番目までの要素が上位ビットまたは下位ビットの側から並ぶように配置されている。
【００３１】
図４は、要素ブロックＡの一例を示す図である。１つの要素ブロックＡには複数の要素からなる列が配置されている。図４の例では、下段側に要素ブロックＡに格納されているビット列が記載され、上段にそのビット列が示す数値が記載されている。図４の例では列の要素が上位ビット側から順に配置されているが、列の要素が下位ビット側から順に配置されていてもよい。また説明の容易のため図４に示す要素ブロックＡのワード長ｗは１６ビットであり、要素ブロックＡ中の要素の数αは４であるが、実際にはこれらの値はより大きくてもよい。また要素のビット数ｍも異なっていてもよい。
【００３２】
ブロックパラメータ算出部５２は、取得された要素ブロックＡについて、要素値の総和ｂｓｕｍ、部分和の最大値ｂｍａｘ、先頭要素からの部分和の最大値ｂｍａｘｐｒｅ、および末尾要素までの部分和の最大値ｂｍａｘｓｕｆを算出する。
【００３３】
要素値の総和ｂｓｕｍは、要素ブロックＡに含まれる先頭から最終の要素の値の合計である。先頭要素からの部分和の最大値ｂｍａｘｐｒｅは、（１≦ｄ≦α）の条件を満たすそれぞれのｄについて求められる、要素ブロックＡに含まれる先頭からｄ番目までの要素の値の合計と０とのうち最大のものである。末尾要素までの部分和の最大値ｂｍａｘｓｕｆは、（１≦ｄ≦α）の条件を満たすそれぞれのｄについて求められる、要素ブロックＡに含まれるｄ番目から最終までの要素の値の合計と０とのうち最大のものである。部分和の最大値ｂｍａｘは、（１≦ｐ≦ｑ≦α）の条件を満たす整数ｐ，ｑの組のそれぞれについて求められる、要素ブロックＡに含まれるｐ番目からｑ番目の要素の値の合計と０とのうち最大のものである。以下では、要素ブロックＡについての部分和は、要素ブロックＡに含まれかつ連続する複数の要素の合計とする。同様に入力配列の部分和は入力配列に含まれかつ連続する複数の要素の合計とする。部分和で合計される複数の要素は、要素ブロックＡまたは入力配列に含まれる要素のうち一部または全部となる。部分和の最大値は、その要素の一部または全部がとりうる全てのパターンにおける部分和と、０とのうち最大値を示すものとする。
【００３４】
最大部分和算出部５３は、ブロックパラメータ算出部５２により算出された要素値の総和ｂｓｕｍ、部分和の最大値ｂｍａｘ、先頭要素からの部分和の最大値ｂｍａｘｐｒｅ、および末尾要素までの部分和の最大値ｂｍａｘｓｕｆに基づいて、入力配列における最大部分和（部分和の最大値）を算出する。
【００３５】
結果出力部５４は、最大部分和算出部５３により算出された最大部分和を示す情報を記憶部１２に記憶させ、またその情報を通信部１３を介して他のコンピュータへ、または入出力部１４を介してディスプレイへ出力する。例えば、結果出力部５４は、算出された最大部分和をディスプレイ装置が表示するように制御する。
【００３６】
次に、情報処理装置が実行する処理について説明する。図５は、情報処理装置の処理の概要を示すフロー図である。
【００３７】
はじめに、最大部分和算出部５３は変数を初期化する。より具体的には、最大部分和算出部５３は変数ｍａｘおよびｍａｘｓｕｆに０を、ループカウンタである変数ｉに１を代入する（ステップＳ１０１）。変数ｍａｘにはこれまでに処理された１または複数の要素ブロックＡを対象とした場合についての部分和の最大値が格納される。
【００３８】
次に、要素ブロック取得部５１は、入力配列に含まれる複数の要素ブロックＡのうちｉ番目の要素ブロックＡを取得する（ステップＳ１０２）。そして、ブロックパラメータ算出部５２は、取得された要素ブロックＡについて、要素値の総和ｂｓｕｍ、部分和の最大値ｂｍａｘ、先頭要素からの部分和の最大値ｂｍａｘｐｒｅ、および末尾要素までの部分和の最大値ｂｍａｘｓｕｆを算出する（ステップＳ１０３）。
【００３９】
ステップＳ１０３の処理についてさらに詳細に説明する。図６は、ブロックパラメータ算出部５２の処理の一例を示すフロー図である。
【００４０】
初期処理部５５は、ループカウンタとなる変数ｊに１を代入する（ステップＳ２０１）。ここで、ステップＳ２０３からＳ２０９のループ内処理の繰返し回数Ｌは、（ｌｏｇ２α）の小数点以下を切り上げた値である。
【００４１】
次に、初期処理部５５は、１回目のループ内処理に用いるための初期の、総和ブロックＳ、最大ブロックＭ、先頭最大ブロックＭＰ、末尾最大ブロックＭＳを求める（ステップＳ２０２）。総和ブロックＳは、要素ブロックＡが区切られた複数の副ブロックのそれぞれについて求められた要素値の総和が並んで配置されるデータである。ここで、本実施形態では初期処理部５５が出力するデータに含まれる副ブロックは単一の要素に対応し、後述の繰返処理部５６が算出するデータに含まれる副ブロックは複数の要素に対応する。最大ブロックＭは、複数の副ブロックのそれぞれについて求められた部分和の最大値が並んで配置されるデータである。先頭最大ブロックＭＰは、複数の副ブロックのそれぞれについて求められた先頭要素からの部分和の最大値が並んで配置されるデータである。末尾最大ブロックＭＳは、複数の副ブロックのそれぞれについて求められた末尾要素までの部分和の最大値が並んで配置されるデータである。ステップＳ２０２で求められた総和ブロックＳ、最大ブロックＭ、先頭最大ブロックＭＰ、末尾最大ブロックＭＳはプロセッサ１１のレジスタに格納される。
【００４２】
以下では総和ブロックＳ、最大ブロックＭ、先頭最大ブロックＭＰ、末尾最大ブロックＭＳなど、内部に複数の副ブロックの値が配置されるデータを、単に「ブロック」と表記する。ここで、ブロックのビット長はワード長ｗであり、１つのブロックに含まれる副ブロックの数は処理過程により変化する。本実施形態では、初期処理部５５の処理における副ブロックの数は要素の数と同じαであり、副ブロックのビット長は要素のビット長と同じである。副ブロックは、対応する１または複数の要素における総和や最大値などの値を含み、その値が格納される副ブロックのビット位置は、要素ブロックＡにおいて対応する要素が配置されるビット位置と同じである。副ブロックが複数ある場合には、先頭側の要素に対応する副ブロックから末尾側の要素に対応する副ブロックまでがブロック内を順に並ぶように配置される。なお、以下に記載する処理と異なる処理により、初期処理部５５が、副ブロックのそれぞれが連続する複数の要素に対応するようなブロックを生成してもよい。
【００４３】
ステップＳ２０２においては、複数の副ブロックのそれぞれは１つの要素に対応する。初期処理部５５は総和ブロックＳを要素ブロックＡのコピーにより生成する。また、初期処理部５５は要素ブロックＡの各要素の値と０とのうち大きい方の値（最大値）が対応する副ブロックに格納されたブロックを生成し、そのブロックのコピーにより最大ブロックＭ、先頭最大ブロックＭＰ、末尾最大ブロックＭＳを生成する。
【００４４】
ここで、以下の式に記載される、２つのブロックＰ１，Ｐ２のうち同じビット位置にある副ブロックの最大値が格納されたブロックＺを取得する処理について説明する。
【００４５】
【数１】
0005931311.tif 000002
【００４６】
ここで、ｋは、副ブロックのビット数である。この式の処理は、ビット演算や整数演算の組合せにより実現される。以下の式の記載では、「＆」、「｜」、「〜」、「＜＜」、「＞＞」、「＾」は、それぞれ論理積のビット演算、論理和のビット演算、ＮＯＴ演算、左シフト演算、右シフト演算、排他的論理和（ＸＯＲ）演算をすることを示す。プロセッサ１１はこれらのビット演算と加算、減算のそれぞれをプロセッサ命令に基づいて最小のクロックで実行する。またプロセッサ命令によるこれらの演算のそれぞれはレジスタに格納される複数の副ブロックの値を一括して操作するものである。
【００４７】
最大値が格納されたブロックＺは、以下の式に示す処理によって算出される。
【００４８】
【数２】
0005931311.tif 000003
【００４９】
ここで、「Ｈｋ」は、処理単位のビット数のデータに含まれるｋビットの副ブロックのそれぞれについて、最も上位のビットが１となり、他のビットが０となる処理単位のビット列を示している。また、後述の「Ｌｋ」は、処理単位のビット数のデータに含まれるｋビットの副ブロックのそれぞれについて、最も下位のビットが１となり、他のビットが０となる処理単位のビット列を示している。例えばＨ４は２進数で「１０００１０００・・・１０００１０００」であり、Ｌ４は２進数で「０００１０００１・・・０００１０００１」である。
【００５０】
ここで、０の値が副ブロックに配置されたブロックのデータをＮ０とすると、初期処理部５５は、最大ブロックＭ、先頭最大ブロックＭＰ、末尾最大ブロックＭＳのデータを、ｐｍａｘｋ（Ａ，Ｎ０）により求める。なお、初期処理部５５は、ｐｍａｘｋ（Ａ，Ｎ０）の出力を、Ｖ１を単に（Ａ＆Ｈｋ）により求め、上述の式でＶ２を求めた後に、（〜Ｖ２＆Ａ）を算出することで求めてもよい。なお、プロセッサ１１がＳＩＭＤ演算機能を有する場合には、ｐｍａｘｋ（Ａ，Ｎ０）や後述のブロック単位の並列演算が、これらのビット演算と加算、減算といった命令の組合せではなく、ＳＩＭＤ命令によって実装されてもよい。
【００５１】
繰返処理部５６は、ループ内処理を繰り返す。ループ内処理は、レジスタに格納される複数の副ブロックの値を一括して操作する複数のプロセッサ命令により、複数の副ブロックについての前記総和ブロックＳ、最大ブロックＭ、先頭最大ブロックＭＰ、および末尾最大ブロックＭＳを操作し、隣り合う２つの副ブロックが連結された新たな副ブロックを含む新たな複数の副ブロックについて、複数のレジスタにそれぞれ格納される新たな総和ブロックＳ、新たな最大ブロックＭ、新たな先頭最大ブロックＭＰ、および新たな末尾最大ブロックＭＳを算出する処理である。
【００５２】
ここで、ｊ回目のループ内処理の開始時点においてブロックに含まれる副ブロックの数をｔｊとすると、新たな副ブロックは、先頭から（２ｓ−１）番目と２ｓ番目の副ブロックが結合したものであり（１≦ｓ≦ｔｊ／２とする）、新たな副ブロックの数ｔｊ＋１はｔｊの半分（ただしｔｊが２の倍数の場合）となる。以下では、結合される２つの副ブロックを、「隣り合う２つの副ブロック」と記載し、その隣り合う２つの副ブロックのうち先頭の側にある（２ｓ−１）番目の副ブロックを「前ブロック」と記載し、末尾の側にある２ｓ番目の副ブロックを「後ブロック」と記載する。
【００５３】
繰返処理部５６のループ内処理についてさらに具体的に説明する。はじめに、繰返処理部５６は、副ブロックのビット数ｋを取得する（ステップＳ２０３）。そして、繰返処理部５６は、新たな副ブロックにおける新たな総和ブロックＳ、新たな先頭最大ブロックＭＰ、新たな末尾最大ブロックＭＳ、新たな最大ブロックＭを算出する（ステップＳ２０４からＳ２０７）。
【００５４】
ステップＳ２０４からステップＳ２０７の処理についてさらに説明する。図７は、繰返処理部５６の１回のループ内処理におけるデータの状態を示す図である。図７には、ループ内処理により、４つの副ブロックが配置されるブロックから、２つの新たな副ブロックが配置される新たなブロックが算出される場合の例が示されている。
【００５５】
ステップＳ２０４において、繰返処理部５６は、前ブロックについての要素値の総和と、後ブロックについての要素値の総和との和が、新たな副ブロックについての総和として配置される新たな総和ブロックＳを算出する。より具体的には、繰返処理部５６は、はじめに、総和ブロックＳのうち前ブロックの値が新たな副ブロックの位置に配置される上位総和ブロックＳＵと、総和ブロックＳのうち後ブロックの値が新たな副ブロックの位置に配置される下位総和ブロックＳＬとを生成する。先頭最大ブロックＭＰ、末尾最大ブロックＭＳ、最大ブロックＭについても同様の処理が行われる。以下では、前ブロックの値が新たな副ブロックに配置されるブロックを上位ブロックＢＵ、後ブロックの値が新たな副ブロックに配置されるブロックを下位ブロックＢＬと記載する。
【００５６】
図８は、ブロックＢＩから上位ブロックＢＵを生成する処理を説明する図である。図９は、ブロックＢＩから下位ブロックＢＬを生成する処理を説明する図である。
【００５７】
上位ブロックＢＵと下位ブロックＢＬとを生成する処理は、処理対象となるブロックＢＩをレジスタＲ１，Ｒ２に配置する第１操作と、レジスタＲ１に格納される前ブロックの位置とレジスタＲ２に格納される後ブロックの位置とが合うように第１および第２のレジスタＲ１，Ｒ２のうち一方のビットをシフトする第２操作（図８および９ではレジスタＲ１をシフトする）と、総和ブロックＳに含まれる前ブロックのみが配置されたブロックＷＢＵを得る第３操作と、ブロックＷＢＵに含まれる前ブロックをその前ブロックのビット領域を含む新たな副ブロックのビット領域に符号拡張し上位ブロックＢＵを得る第４操作と、総和ブロックＳに含まれる後ブロックのみが配置されたブロックＷＢＬを得る第５操作と、ブロックＷＢＬに含まれる後ブロックをその後ブロックのビット領域を含む新たな副ブロックのビット領域に符号拡張し下位ブロックＢＬを得る第６操作と、を含む。符号拡張は、元の副ブロックのビット領域が示す値を、新たな副ブロックのビット領域が示すように変換する操作である。副ブロックの値が負の値を含む２の補数で表現される場合には、符号拡張は、値が格納される元の副ブロックの最上位ビットを、その上位側にある副ブロックの全てのビットにコピーする操作である。なお、第２操作は第３操作または第５操作の後にブロックＷＢＵまたはブロックＷＢＬが格納されるレジスタに対して行われてもよい。
【００５８】
第３操作は、プロセッサ１１が前ブロックが配置されるビット領域の全てのビットに１がセットされたデータとＲ１との論理積を演算することにより実現される。第５操作は、プロセッサ１１がシフト後の後ブロックが配置されるビット領域の全てのビットに１がセットされたデータとＲ２との論理積を演算することにより実現される。この場合には、前ブロックが配置されるビット領域の全てのビットに１がセットされたデータやシフト後の後ブロックが配置されるビット領域の全てのビットに１がセットされたデータは、２進数の “００００１１１１００００１１１１”である。このデータはビット長ｋや繰返し回数の値に応じて取得できる配列に予め格納されていてもよい。
【００５９】
第４操作、第６操作は、以下の数式により表される演算により実現される。なお、プロセッサ１１は、符号拡張命令を用いて第４操作、第６操作を実現してもよい。ここでは、ｋの値は新たな副ブロックのビット長であるとする。
【００６０】
【数３】
0005931311.tif 000004
【００６１】
第４操作では、プロセッサ１１は、ブロックＷＢＵが格納されるレジスタとＨｋ／２との論理積を演算し、Ｈｋからその論理積の結果を減算し、減算の結果とＨｋとの排他的論理和を演算し、その排他的論理和の結果とＷＢＵとの論理和をとる。これにより上位ブロックＢＵが算出される。第６操作でも、ブロックＷＢＬについて同様の演算が行われる。なお、各種演算の結果はプロセッサ１１のレジスタに格納される。
【００６２】
繰返処理部５６は、上述の第１操作から第６操作を総和ブロックＳについて行うことにより、それぞれ互いに異なるレジスタに格納される上位総和ブロックＳＵと下位総和ブロックＳＬとを生成する。
【００６３】
上位総和ブロックＳＵと下位総和ブロックＳＬとが生成されると、繰返処理部５６は、上位総和ブロックＳＵと下位総和ブロックＳＬとに含まれる新たな副ブロックに相当する領域に格納される値の和が配置された新たな総和ブロックＳを算出する。
【００６４】
ここで、以下の式に示される、２つのブロックＰ３，Ｐ４のうち同じビット位置に含まれる副ブロックの値の和が配置されたブロックＺ２を取得する処理について説明する。
【００６５】
【数４】
0005931311.tif 000005
【００６６】
ｋはＰ３，Ｐ４に含まれる副ブロック（新たな副ブロックに相当）のビット長である。和が格納されたブロックＺ２は、以下の式に示す処理によって算出される。
【００６７】
【数５】
0005931311.tif 000006
【００６８】
繰返処理部５６は、ｐａｄｄｋ（ＳＵ，ＳＬ）の結果を新たな総和ブロックＳの値として取得する。
【００６９】
ステップＳ２０５において、繰返処理部５６は、前ブロックについての要素値の総和、および後ブロックについての先頭要素からの部分和の最大値の和と、前ブロックについての先頭要素からの部分和の最大値と、のうち大きい方が、新たな副ブロックについての先頭要素からの部分和の最大値として配置される新たな先頭最大ブロックＭＰを算出する。より具体的には、繰返処理部５６は上述の第１操作から第６操作を先頭最大ブロックＭＰについて行うことにより、上位先頭最大ブロックＭＰＵと下位先頭最大ブロックＭＰＬとを生成する。そして、繰返処理部５６はｐａｄｄｋ（ＳＵ，ＭＰＬ）を算出しブロックＷ１に配置する。ブロックＷ１には上位総和ブロックＳＵと下位先頭最大ブロックＭＰＬとに含まれる同じ位置にある２つの副ブロックの和が配置される。繰返処理部５６はｐｍａｘｋ（Ｗ１，ＭＰＵ）により、新たな先頭最大ブロックＭＰを算出する。ｐｍａｘｋ（Ｗ１，ＭＰＵ）は、ブロックＷ１と上位先頭最大ブロックＭＰＵとに含まれる同じ位置にある２つの副ブロックの最大値を算出する処理である。
【００７０】
ステップＳ２０６において、繰返処理部５６は、後ブロックについての総和、および前ブロックについての末尾要素までの部分和の最大値の和と、後ブロックについての末尾要素までの部分和の最大値と、のうち大きい方が、新たな副ブロックについての末尾要素までの部分和の最大値として配置される新たな末尾最大ブロックＭＳを算出する。より具体的には、繰返処理部５６は上述の第１操作から第６操作を末尾最大ブロックＭＳについて行うことにより、上位末尾最大ブロックＭＳＵと下位末尾最大ブロックＭＳＬとを生成する。そして、繰返処理部５６はｐａｄｄｋ（ＳＬ，ＭＳＵ）を算出しブロックＷ２に配置する。ブロックＷ２には下位総和ブロックＳＬと上位末尾最大ブロックＭＳＵとに含まれる同じ位置にある２つの副ブロックの和が配置される。繰返処理部５６はｐｍａｘｋ（Ｗ２，ＭＳＬ）により、新たな末尾最大ブロックＭＳを算出する。ｐｍａｘｋ（Ｗ２，ＭＳＬ）は、ブロックＷ２と下位末尾最大ブロックＭＳＬとに含まれる同じ位置にある２つの副ブロックの最大値を算出する処理である。
【００７１】
ステップＳ２０７において、繰返処理部５６は、前ブロックについての末尾要素までの部分和の最大値および後ブロックについての先頭要素からの部分和の最大値の和と、前ブロックについての部分和の最大値と、後ブロックについての部分和の最大値と、のうち一番大きいものが、新たな副ブロックについての部分和の最大値として配置される最大ブロックＭを算出する。より具体的には、繰返処理部５６は上述の第１操作から第６操作を最大ブロックＭについて行うことにより、上位最大ブロックＭＵと下位最大ブロックＭＬとを生成する。そして、繰返処理部５６はｐｍａｘｋ（ＭＵ，ＭＬ）を算出し、ブロックＷ３に配置する。また、繰返処理部５６はｐａｄｄｋ（ＭＳＵ，ＭＰＬ）を算出し、ブロックＷ４に配置する。最後に、繰返処理部５６はｐｍａｘｋ（Ｗ３，Ｗ４）により、新たな最大ブロックＭを算出する。
【００７２】
なお、処理の順序は上述の説明と異なっていてもよい。例えば、ステップＳ２０５およびステップＳ２０６の処理の順序が交換されてもよい。
【００７３】
新たな副ブロックにおける新たな総和ブロックＳ、新たな先頭最大ブロックＭＰ、新たな末尾最大ブロックＭＳ、新たな最大ブロックＭが算出されると、繰返処理部５６は変数ｊの値を１増加させ（ステップＳ２０８）、ｊの値が繰返し回数Ｌ以下の場合には（ステップＳ２０９のＹ）、ステップＳ２０３からループ内処理を繰返す。一方、ｊの値が繰返し回数Ｌを超えた場合には（ステップＳ２０９のＮ）、パラメータ決定部５７は、総和ブロックＳ、先頭最大ブロックＭＰ、末尾最大ブロックＭＳ、最大ブロックＭに含まれる１つの副ブロックに格納される値を、それぞれ総和ｂｓｕｍ、部分和の最大値ｂｍａｘ、先頭要素からの部分和の最大値ｂｍａｘｐｒｅ、および末尾要素までの部分和の最大値ｂｍａｘｓｕｆとして決定し、これらを最大部分和算出部５３に渡す（ステップＳ２１０）。
【００７４】
なお、ブロックのワード長や要素のビット長が変化しなければ、繰返処理部５６の処理の繰返し回数Ｌは一定であるので、ループによって同じプログラムを繰返し実行させなくてもよい。例えば、１回目のループ内処理のプログラム、２回目のループ内処理のプログラム・・・、Ｌ回目のループ内処理のプログラムを互いに別にしておき、繰返処理部５６はそれらのプログラムを順に実行してもよい。本実施形態では要素ブロックＡに含まれる要素の数などの処理に関わるパラメータを一定の値にすることが容易であり、処理の最適化により所要時間を短縮することも可能である。
【００７５】
総和ｂｓｕｍ、部分和の最大値ｂｍａｘ、先頭要素からの部分和の最大値ｂｍａｘｐｒｅ、および末尾要素までの部分和の最大値ｂｍａｘｓｕｆが算出されると、最大部分和算出部５３は、変数ｍａｘ、部分和の最大値ｂｍａｘ、（ｍａｘｓｕｆ＋ｂｍａｘｐｒｅ）のうち最大の値を変数ｍａｘに代入する（ステップＳ１０４）。この処理を行う前の変数ｍａｘには、配列の先頭要素から前回の要素ブロックＡの末尾要素までの部分配列における最大部分和の値が格納されている。最大部分和算出部５３はこの処理では、今回の処理までに取得された要素ブロックＡが連結された新たな部分配列における最大部分和を求め変数ｍａｘに代入している。新たな部分配列は、配列の先頭要素から今回の要素ブロックＡの末尾要素までを含む。
【００７６】
次に、最大部分和算出部５３は、（ｍａｘｓｕｆ＋ｂｓｕｍ）、ｂｍａｘｓｕｆのうち大きい方の値を変数ｍａｘｓｕｆに代入する（ステップＳ１０５）。この処理を行う前の変数ｍａｘｓｕｆには、配列の先頭要素から前回の要素ブロックＡの末尾要素までの部分配列における末尾要素までの部分和の最大値が格納されている。最大部分和算出部５３はこの処理では、次に取得される要素ブロックＡについての処理で必要になる、今回の処理までに取得された要素ブロックＡが連結された新たな部分配列における最終要素までの部分和の最大値を求め、変数ｍａｘｓｕｆに格納している。
【００７７】
そして、取得されていない次の要素ブロックＡが存在する場合には（ステップＳ１０６のＹ）、最大部分和算出部５３は変数ｉの値を１増加させ（ステップＳ１０７）、ステップＳ１０２の処理から繰り返させる。一方、次の要素ブロックＡが存在しない場合には（ステップＳ１０６のＮ）、結果出力部５４は、変数ｍａｘの値を、最大部分和算出部５３により算出された最大部分和として取得し、その最大部分和を含む情報を出力する（ステップＳ１０８）。
【００７８】
本実施形態では、ブロックパラメータ算出部５２および最大部分和算出部５３の計算量のオーダーは、O(n/α log α)となる。要素ブロックＡに含まれる要素の数αが多いほどKadaneの方法に対して計算量が少なくなる。
【００７９】
最大部分和算出部５３の処理では、これまでにブロックパラメータ算出部５２により処理された１または複数の要素ブロックＡによる部分配列と、今回の処理にかかる要素ブロックＡとの２つについてのパラメータを用いて最大部分和等を計算する。何番目の要素ブロックＡの取得後の処理であっても、部分配列の末尾側のみに新たな要素ブロックＡが存在することは変わらないため、要素ブロックＡ内の計算と異なり、部分配列における、先頭からの部分和の最大値や総和を用いる必要がない。これにより、並列処理が難しい最大部分和算出部５３の処理量を削減し、処理時間短縮の効果を全体としても得ることが可能になる。また、入力配列に含まれる要素の数が不定の場合でも処理を進めることができ、温度や株価の時系列データをストリーミング的に少しずつリアルタイムに受信して処理することも可能になる。
【００８０】
なお、入力配列に含まれる要素は必ずしも符号付き整数値でなくてもよい。例えば、プロセッサ１１が、複数の浮動小数点が配置されているレジスタを操作するＳＩＭＤ命令を含む場合には、要素が浮動小数点を含んでいてもよい。
【要約】
プログラムによる並列処理により配列の最大部分和を高速に求めること。
情報処理装置は、配列の一部であって所定数の要素の列からなるブロックを取得し、前記ブロックが区切られた複数の副ブロックのそれぞれについて総和ブロックと、最大ブロックと、先頭最大ブロックと、末尾最大ブロックとを生成し、レジスタに格納される複数の副ブロックの値を一括して操作する所定のプロセッサ命令により、前記副ブロックが連結された新たな副ブロックについて、新たに総和ブロック、最大ブロック、先頭最大ブロック、および末尾最大ブロックを算出する処理を繰り返し実行し、前記処理が所定の回数実行された場合に、前記ブロックにおける要素値の総和、部分和の最大値、先頭要素からの部分和の最大値、および末尾要素までの部分和の最大値を決定し、前記決定された値に基づいて、前記配列における部分和の最大値を算出する。【図１】
0005931311.tif 000007
【図２】
0005931311.tif 000008
【図３】
0005931311.tif 000009
【図４】
0005931311.tif 000010
【図５】
0005931311.tif 000011
【図６】
0005931311.tif 000012
【図７】
0005931311.tif 000013
【図８】
0005931311.tif 000014
【図９】
0005931311.tif 000015