(57)【要約】【課題】キャッシュメモリ上に非ゼロデータのみを保持することで、メモリ使用量及びバンド幅を抑えることができる情報処理装置を提供する。【解決手段】実施の形態の情報処理装置は、入力部と、記憶部と、リード制御部と、ライト制御部とを有する。入力部には、リード要求およびライト要求が入力される。記憶部には、管理情報が記憶されている。リード制御部は、リード要求が入力されると、管理情報を含むリードデータを記憶部から読み出し、管理情報を参照し、ブロック行の所定の範囲に含まれる非ゼロデータのみを出力する。ライト制御部は、非ゼロデータのみを記憶部に書き込み、かつ、所定の範囲より小さい位置から開始される連続する非ゼロデータの中で、最も大きい位置から開始される連続する非ゼロデータの開始位置から１つ前の管理情報と、所定の範囲に格納されていた最後の管理情報と、所定の範囲の最後の管理情報とを更新する。【選択図】図１
2015176245.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上の要素で構成されるブロックを少なくとも１つ以上備えるブロック行の所定の範囲に対する、リード要求およびライト要求が入力される入力部と、
１つのブロック中の全ての要素がゼロのゼロデータの領域に、１つのブロック中に非ゼロ要素が１つ以上ある連続する非ゼロデータの数、及び、次の非ゼロデータまでの距離を示す情報が格納された管理情報が記憶された記憶部と、
前記リード要求が入力されると、前記管理情報を含むリードデータを前記記憶部から読み出し、前記管理情報を参照し、前記ブロック行の所定の範囲に含まれる前記非ゼロデータのみを出力するリード制御部と、
前記ライト要求が入力されると、前記データのうち１つのブロック中に非ゼロ要素が１つ以上ある非ゼロデータのみを記憶部に書き込み、かつ、前記所定の範囲より小さい位置から開始される連続する非ゼロデータの中で、最も大きい位置から開始される前記連続する非ゼロデータの開始位置から１つ前の管理情報と、前記所定の範囲に格納されていた最後の管理情報と、前記所定の範囲の最後の管理情報とを更新するライト制御部と、
を有することを特徴とする情報処理装置。
【請求項２】
前記ブロック行とは別に前記管理情報を格納する管理領域を設け、
前記管理領域には、前記ブロック行の行頭からのデータについての管理情報が格納されることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記管理情報は、前記連続する非ゼロデータの１つ前の前記ゼロデータの領域に格納されることを特徴とする請求項１に記載の情報処理装置。
【請求項４】
１つ以上の要素で構成されるブロックを少なくとも１つ以上備えるブロック行のデータ構造であって、
１つのブロック中の全ての要素がゼロのゼロデータの領域に、１つのブロック中に非ゼロ要素が１つ以上ある連続する非ゼロデータの数、及び、次の非ゼロデータまでの距離を示す情報を格納したことを特徴とするデータ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、情報処理装置及びデータ構造に関する。
【背景技術】
【０００２】
従来、行列要素の大部分が０である疎行列において、非ゼロ成分のみメモリに保持することでメモリの使用量及びバンド幅を抑えたいという要望がある。現在は、ソフトウエアの疎行列管理ライブラリを使用することで、非ゼロ成分の値と、その位置情報のみを管理し、メモリの使用量及びバンド幅を抑えるという要望を実現している。
【０００３】
しかしながら、これらの処理はソフトウエアによるため、非ゼロ成分にアクセスする際に大きなオーバーヘッドが存在する。また、疎行列にアクセスする際には、それぞれのライブラリのデータ管理方法に則ったアクセスを行わないと多大な時間がかかってしまうため、通常の２次元配列で構成された行列と同様にはアクセスできず不便である。従来では、ＤＲＡＭ上に非ゼロ成分のみ保持できるように管理するハードウエアが存在するが、書き換え時の処理が複雑でオーバーヘッドが大きいという問題がある。
【０００４】
一方、一般に、プロセッサやハードウエアエンジンの処理速度は、ＤＲＡＭ等のメインメモリのデータ供給能力よりも高いため、その性能差を埋めるキャッシュメモリが用いられる場合がある。キャッシュメモリは、メインメモリよりも高速なＳＲＡＭ等のメモリであり、データアレイ上にデータを一時的に記憶する。プロセッサは、キャッシュメモリ上のデータにアクセスすることにより、高速に処理ができる。
【０００５】
データアレイ上にデータが無い場合には、キャッシュメモリは、アクセスするデータサイズよりも大きいキャッシュラインサイズ（例えば２５６バイト）単位でメインメモリからデータを取得する。大きな単位でメインメモリにアクセスすることで、メインメモリへのアクセスが効率化される。一方、データアレイ上にデータがある場合には、キャッシュメモリは、メインメモリからデータを取得せずに、データアレイからデータを返すことができるため、プロセッサやハードウエアエンジンは、高速にデータにアクセスすることができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−１８１３８６号公報
【特許文献２】特開昭５３−６４４３９号公報
【非特許文献】
【０００７】
【非特許文献１】Computer Organization and Design, John L. Hennessy and David A. Patterson, pp.545-579
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施の形態の課題は、キャッシュメモリ上に非ゼロデータのみを保持・管理することで、メモリ使用量及びバンド幅を抑えることができる情報処理装置を提供することである。
【課題を解決するための手段】
【０００９】
実施の形態の情報処理装置は、入力部と、記憶部と、リード制御部と、ライト制御部とを有する。入力部には、１つ以上の要素で構成されるブロックを少なくとも１つ以上備えるブロック行の所定の範囲に対する、リード要求およびライト要求が入力される。記憶部には、１つのブロック中の全ての要素がゼロのゼロデータの領域に、１つのブロック中に非ゼロ要素が１つ以上ある連続する非ゼロデータの数、及び、次の非ゼロデータまでの距離を示す情報が格納された管理情報が記憶されている。リード制御部は、リード要求が入力されると、管理情報を含むリードデータを記憶部から読み出し、管理情報を参照し、ブロック行の所定の範囲に含まれる非ゼロデータのみを出力する。ライト制御部は、データのうち１つのブロック中に非ゼロ要素が１つ以上ある非ゼロデータのみを記憶部に書き込み、かつ、所定の範囲より小さい位置から開始される連続する非ゼロデータの中で、最も大きい位置から開始される連続する非ゼロデータの開始位置から１つ前の管理情報と、所定の範囲に格納されていた最後の管理情報と、所定の範囲の最後の管理情報とを更新する。
【図面の簡単な説明】
【００１０】
【図１】本実施の形態に係る情報処理装置を備える計算機システムの構成を示す図である。
【図２】本実施の形態で処理を行う行列を説明するための図である。
【図３】行列の処理単位を説明するための図である。
【図４】ブロック行の管理方法を説明するための図である。
【図５】使用するメモリ空間の例を説明するための図である。
【図６】行列アドレス中のbit配置の例を説明するための図である。
【図７】行列管理エンジン４の詳細な構成を説明するための図である。
【図８】アドレス変換の処理について説明するための図である。
【図９】ライト要求の例を説明するための図である。
【図１０】Read Ctrl２３ａの詳細な構成を説明するための図である。
【図１１】Ｓ[ｍ] [ｎ０]〜Ｓ[ｍ] [ｎ１]のデータを読み出す処理の流れの例を説明するためのフローチャートである。
【図１２】Ｓ[ｍ] [ｎ０]〜Ｓ[ｍ] [ｎ１]のデータを読み出す処理の流れの例を説明するためのフローチャートである。
【図１３】Write Ctrl２４ａの詳細な構成を説明するための図である。
【図１４】m行目のブロック行のn0ブロック列〜n1ブロック列に対してデータを書き込む処理の流れの例を説明するためのフローチャートである。
【図１５】非ゼロデータ列Ｂ及びＡの探索の処理の流れの例を説明するためのフローチャートである。
【図１６】非ゼロデータ列Ｂの開始位置−１の位置の非ゼロ管理情報の更新、及び、ライトデータの書き込み処理の流れの例を説明するためのフローチャートである。
【図１７】非ゼロデータ列Ｂの開始位置−１の位置の非ゼロ管理情報の更新、及び、ライトデータの書き込み処理の流れの例を説明するためのフローチャートである。
【図１８】最後の非ゼロ管理情報の更新、及び、n1列の非ゼロ管理情報の更新処理の流れの例を説明するためのフローチャートである。
【図１９】Write Ctrl２４ａによるライト動作について説明するための図である。
【図２０】Write Ctrl２４ａによるライト動作について説明するための図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。  
本実施の形態に係る情報処理装置を備える計算機システムについて説明する。図１は、本実施の形態に係る情報処理装置を備える計算機システムの構成図である。計算機システム１は、中央処理装置（以下、ＣＰＵという）２と、ハードウエアエンジン（以下、ＨＷＥという）３と、行列管理エンジン４と、キャッシュ５と、アドレス変換部６と、インターコネクト７と、メインメモリ８と、入出力装置（以下、Ｉ／Ｏという）９と、で構成されている。
【００１２】
情報処理装置としての行列管理エンジン４は、ＣＰＵ２、ＨＷＥ３及びキャッシュ５に接続されている。キャッシュ５は、アドレス変換部６を介してインターコネクト７に接続されている。このインターコネクト７は、さらにメインメモリ８及びＩ／Ｏ９に接続されている。メインメモリ８は、例えばＤＲＡＭである。
【００１３】
計算機システム１への入力データは、Ｉ／Ｏ９、インターコネクト７を介してメインメモリ８に転送される。転送された入力データは、ＣＰＵ２やＨＷＥ３に転送され処理される。ＣＰＵ２やＨＷＥ３で処理された出力データは、メインメモリ８、インターコネクト７、Ｉ／Ｏ９を介して出力される。
【００１４】
計算機システム１は、行列以外のデータにアクセスする場合、行列管理エンジン４を経由せず、ＣＰＵ２やＨＷＥ３から直接メインメモリ８（あるいはキャッシュ５）にアクセスする。一方、行列にアクセスする場合、行列管理エンジン４が処理を行う。
【００１５】
本実施の形態で処理を行う行列の一例について説明する。図２は、本実施の形態で処理を行う行列を説明するための図であり、図３は、行列の処理単位を説明するための図である。
【００１６】
図２の行列は、１６行×５２列の８３２要素からなる２次元の疎行列Ｓである。そして、本実施の形態では、疎行列Ｓの所定サイズでゼロ／非ゼロを管理する。所定サイズは１要素以上であり、例えば図３に示すように、４×４の１６要素単位である。この単位をブロックと呼ぶ。疎行列Ｓ中の４×４のブロックについては、Ｓ[ｙ][ｘ]（ｘ＝１〜１３、ｙ＝１〜４）で表す。ｘは、横（列）方向のブロック番号であり、１〜疎行列Ｓの列数／４（端数切り上げ）の範囲を取る。ｙは、縦（行）方向のブロック番号であり、１〜疎行列Ｓの行数／４（端数切り上げ）の範囲を取る。
【００１７】
ここで、ブロック単位のゼロ／非ゼロの定義として、１ブロック全ての要素が０の場合をゼロとし、１ブロックに１つでも０でない要素がある場合を非ゼロとする。例えば、Ｓ[１][１]及びＳ[１][４]は、１６要素が全て０のため、ゼロとなる。一方、Ｓ[１][２]のように、１６要素のうち１つでも０でない場合や、Ｓ[１][３]のように、１６要素の全てが０でない場合は、非ゼロとなる。
【００１８】
本実施の形態では、非ゼロの管理をブロック行単位で行う。なお、疎行列Ｓが３次元以上の行列であっても、１次元のブロック行単位で管理することで、同様に管理可能である。本実施の形態では、図３に示すように、Ｓ[１][１]〜Ｓ[１][１３]を１つのブロック行Ｂ１として非ゼロの管理を行う。他のブロック行Ｂ２、Ｂ３及びＢ４のそれぞれについても同様に非ゼロの管理を行う。
【００１９】
図４は、ブロック行の管理方法を説明するための図である。ブロック行の非ゼロ管理には、行列データとは別に１ブロック分のメモリ領域（以下、非ゼロ管理領域という）を使用し、ブロック行の先頭に配置する。以降、非ゼロ管理におけるブロック位置をＲ[ｙ][ｘ]で表す。ｘは横（列）方向のブロック番号であり、ｙは縦（行）方向のブロック番号である。図４においては、Ｒ[ｙ][ｘ]（ｘ＝０〜１３、ｙ＝１〜４）である。ブロック行Ｂ１は、Ｒ[１][０]〜Ｒ[１][１３]を用いる。
【００２０】
非ゼロデータについては、疎行列Ｓ上の位置と、ブロック位置Ｒ上の位置とが同じになるように配置される。例えば、疎行列Ｓ上の非ゼロデータであるＳ[１][２]については、Ｒ[１][２]に配置され、Ｓ[１][６]については、Ｒ[１][６]に配置される。
【００２１】
そして、非ゼロデータの位置情報（以下、非ゼロ管理情報という）は、ゼロデータの位置に配置する。より具体的には、１つ以上の連続する非ゼロデータの１つ前のゼロデータの位置に、非ゼロ管理情報を配置する。なお、本実施の形態では、連続する非ゼロデータの１つ前のゼロデータの位置に非ゼロ管理情報を１つ記録するが、１つのゼロデータの位置に複数の非ゼロデータの位置情報を配置するようにしてもよい。
【００２２】
非ゼロ管理情報は、パラメータ（Num，Next）から構成される。Numは、連続する非ゼロデータのブロック数を示し、Nextは、次の非ゼロデータまでの距離（ブロック数）を示す。但し、Nextが０の場合には、次の連続する非ゼロデータがブロック行中に存在しないことを示す。なお、図４では、非ゼロ管理情報は相対距離を用いているが、絶対座標（ブロック位置ｘ）を用いてもよい。
【００２３】
例えば、図４のＳ[１][２]から始まる非ゼロデータの列の非ゼロ管理情報は、ゼロデータであるＲ[１][１]に配置される。Numは、Ｒ[１][２]及びＲ[１][３]が非ゼロなので２となる。また、次の非ゼロデータの列はＲ[１][６]から開始されるため、Nextは４（＝６−２）となる。これにより、Ｒ[１][１]に格納される非ゼロ管理情報は、（２，４）となる。
【００２４】
1ブロック列余分に確保された非ゼロ管理領域Ｒ[１][０]には、行頭Ｒ[１][１]からのデータについての非ゼロ管理情報が記録される。例えば、ブロック行Ｂ１は、行先頭Ｒ[１][１]がゼロデータのため、Ｒ[１][０]のNumは０となり、NextはＲ[１][２]から始まる非ゼロデータまでの距離１（＝２−１）となる。
【００２５】
一方、ブロック行Ｂ２は、Ｒ[２][１]が非ゼロデータのため、Ｒ[２][０]のNumはＲ[２][１]からの非ゼロデータ数となる。すなわち、ブロック行Ｂ２の非ゼロ管理領域Ｒ[２][０]のNumは１、Nextは次の非ゼロデータまでの距離２（＝３−１）となる。
【００２６】
また、ブロック行Ｂ３のように、ブロック行全てが非ゼロの場合、非ゼロ管理領域Ｒ[３][０]のデータは（１３，０）となる。一方、ブロック行Ｂ４のように、ブロック行全てがゼロの場合、非ゼロ管理領域Ｒ[４][０]のデータは（０，０）となる。
【００２７】
行列管理エンジン４は、管理する行列毎に行列管理情報を有している。この行列管理情報は、行列先頭アドレス(base)、行列の行数(width)、及び、行列の列数(height)であり、外部（ＣＰＵ２等）から設定される。ここで、アドレス空間をバイトアドレスで３２bit幅、疎行列Ｓの１要素を８byteデータ、その先頭アドレスを0x48000000とする。このとき、パラメータの設定値は、行列先頭アドレス(base)が0x48000000、行列の行数(width)が５２、及び、行列の列数(height)が１６となる。行列管理エンジン４は、これらパラメータを用い、メモリ空間を使用する。
【００２８】
図５は、使用するメモリ空間の例を説明するための図である。１ラインの要素数は、非ゼロ管理領域および行列の行データを含む２ｎ（ｎは１以上の整数）である。行列データはライン方向に１行ずつ、順に配置される。１行目のデータはBase Address(0x48000000)から、非ゼロ管理領域Ｑ１１(４要素分)、行列の行データＱ１２(５２要素分)が配置される。非ゼロ管理領域Ｑ１１の幅は、ゼロ／非ゼロ管理単位である１ブロックの列の幅に相当する。
【００２９】
なお、８要素分は使用しないデータ領域Ｑ１３である。使用しないデータ領域Ｑ１３の幅Ｚは、次の式を満たす最小値となる。
【００３０】
(Ｚ＋[管理領域Ｑ１１の幅]＋[行データＱ１２の要素数] )=２ｎ(ｎは正の整数、ｎ＞＝１)、かつ、Ｚ>=０
図５では、Ｚの値は８となり、１ラインのサイズは６４要素分となる。１ラインのメモリ量が５１２byte（６４要素×８byte）であるため、２行目のデータは0x48000200のアドレスから配置される。
【００３１】
図６は、行列アドレス（変換前アドレス）のbit配置の例を説明するための図である。行列アドレスは、Base Address、Ｙ座標、Ｘ座標及び1要素のデータ(8byte)をByte単位でアクセスする際に使用するOffsetを含む。疎行列Ｓのある要素をｓ（ｙ，ｘ）（ｘ＝１〜５２、ｙ＝１〜１６）とすると、その要素が配置されるアドレスは、Ｘ＝ｘ＋３、Ｙ＝ｙ−１となる。例えば、Ｓ（１，１）の場合は、Ｘ＝４、Ｙ＝０のため、アドレスは0x48000020となり、Ｓ（５，２５）の場合は、Ｘ＝２８、Ｙ＝４のため、アドレスは0x480008e0となる。
【００３２】
次に、行列管理エンジン４について説明する。図７は、行列管理エンジン４の構成図である。図７の行列管理エンジン４は、Packet Distributer２１と、Packet I/F２２ａ〜２２ｄと、Read Ctrl２３ａ〜２３ｄと、Write Ctrl２４ａ〜２４ｄとを備えている。なお、図７の行列管理エンジン４は、４つのPacket I/F２２ａ〜２２ｄを有するが、数は任意であり、それに対応してRead Ctrl２３およびWrite Ctrl２４を有する。また、キャッシュ５は、Ｌ２キャッシュ２５ａ〜２５ｄにより構成されている。さらに、アドレス変換部６は、Ｌ２キャッシュ２５ａ〜２５ｄのそれぞれに対応したAddress Translator２６ａ〜２６ｄにより構成されている。なお、Ｌ２キャッシュ２５は一般的なキャッシュでよい。
【００３３】
マスタモジュール（ＣＰＵ２またはＨＷＥ３）からの入力は、Packet Distributer２１へと入力される。行列管理エンジン４とマスタモジュールとの入出力の関係は次の通りである。マスタモジュールからの要求はブロック単位で行う。
【００３４】
ＨＷＥ３からのリード要求の場合、アクセス対象行列の開始アドレス、アクセス開始Ｘ座標およびＹ座標、転送列数、及び、転送行数が行列管理エンジン４に入力される。なお、このパラメータは一例であり、例えば１行内へのアクセスの場合、アクセス開始要素アドレス、及び、転送数のようなパラメータでもよい。この場合、アクセス開始要素アドレスから行列管理エンジン４内部で残りのパラメータを算出する。
【００３５】
ＨＷＥ３からのリード要求に対し、行列管理エンジン４は対象リード領域内に非ゼロデータがある場合、連続する非ゼロデータ列を、次のようなリードデータとして出力する。リードデータは、非ゼロデータの開始Ｘ座標およびＹ座標、連続非ゼロデータ列、及び、非ゼロデータフラグ（ＯＮ）を含む。なお、非ゼロデータ列がなく、全てゼロの場合は、非ゼロデータフラグがＯＦＦとなり、リード非ゼロデータの開始Ｘ座標、Ｙ座標、非ゼロデータ列には何も出力されない。
【００３６】
また、ＨＷＥ３からのライト要求の場合、アクセス対象行列の開始アドレス、アクセス開始Ｘ座標およびＹ座標、転送列数、転送行数、及び、非ゼロデータフラグが行列管理エンジン４に入力される。
【００３７】
非ゼロデータを書き込む場合、非ゼロデータフラグはＯＮになる。非ゼロデータを書き込む場合に入力されるデータは、連続する非ゼロデータ列毎に、非ゼロデータの開始Ｘ座標およびＹ座標、連続非ゼロデータ列、連続非ゼロデータ列の終端フラグとなる。そして、末尾にライトリクエストの最後の非ゼロデータフラグが付される。
【００３８】
ＨＷＥ３からのライト要求は、ライト要求範囲内で非ゼロデータ列が指定されていない箇所にゼロデータを書き込む。要求範囲内を全てゼロデータで書き込む場合は、非ゼロデータフラグがＯＦＦとなり、ＨＷＥ３から行列データは行列管理エンジン４に入力されない。
【００３９】
一方、ＣＰＵ２からのリード要求は、通常のＣＰＵからメモリへのリード要求と同じである。リードアクセス対象のアドレス、及び、リードサイズが行列管理エンジン４に入力される。
【００４０】
ＣＰＵ２からのリード要求に対し、行列管理エンジン４は要求されたリードサイズのリードデータをＣＰＵ２に返す。行列管理エンジン４は、要求されたリードサイズがブロックサイズより小さい場合やブロックサイズの整数倍ではない場合には、要求されたリードサイズより大きく、整数倍のブロックサイズの中で最小サイズのリード要求として処理する。そして、行列管理エンジン４は、得られたリードデータから実際に要求されたリードサイズのみＣＰＵ２に返す。また、行列管理エンジン４は、リードデータに０が含まれる場合には、ＣＰＵ２に０を返す。
【００４１】
また、ＣＰＵ２からのライト要求は、通常のＣＰＵからメモリへのライト要求と同じである。ライトアクセス対象のアドレス、ライトサイズ、及び、ライトデータが行列管理エンジン４に入力される。
【００４２】
ＣＰＵ２からのライト要求に対し、行列管理エンジン４は、要求されたライトサイズのライトデータを記憶する。行列管理エンジン４は、ライトサイズがブロックサイズより小さい場合やブロックサイズの整数倍ではない場合には、ライトサイズより大きく、整数倍のブロックサイズの中で最小サイズのライト要求として、与えられたライトデータ以外のデータは０とみなして処理する。
【００４３】
行列管理エンジン４は、行列情報を内部に持ち、アクセスが入力されると管理行列へのアクセスか否かを判定し、管理行列へのアクセスでないと判定した場合、通常のアクセスとしてＬ２キャッシュ２５等へアクセスする。
【００４４】
Read Ctrl２３は、非ゼロデータのみを要求元に出力する場合、Ｌ２キャッシュ２５から読み出した非ゼロデータとその位置情報を要求元に出力する。一方、Read Ctrl２３は、通常の行列データとして要求元に出力する場合、Ｌ２キャッシュ２５から読み出した非ゼロデータとその位置情報に基づいて、ゼロデータを挿入した通常の行列データを要求元に出力する。
【００４５】
Write Ctrl２４は、非ゼロデータと位置情報のみを入力する場合、あるいは、通常の行列データを入力する場合のいずれも、アクセスを次の２つの要求に変換してＬ２キャッシュ２５に出力する。具体的には、Write Ctrl２４は、アクセスを非ゼロデータの書き込みと位置情報の更新とを行うための要求と、非ゼロからゼロへの変換による位置情報の更新（データの書き込みは行われない）を行うための要求とに変換する。
【００４６】
マスタモジュールからの要求に対して、Packet Distributer２１はリード／ライト要求されたアドレスが管理している行列へのアクセスかどうかをチェックする。そして、Packet Distributer２１は、管理している行列へのアクセスの場合は、アドレス変換を行い、キャッシュ５へのアクセスかを判断し、行毎に要求をPacket I/F２２ａ〜２２ｄに分配する。管理している行列へのアクセスではない場合は、マスタモジュールにエラーを返す。
【００４７】
Packet Distributer２１は、管理している行列へのアクセスかどうかをチェックするために、行列管理パラメータ(base,width,height)を使用し、メモリのアドレス空間に要求されたアドレスが含まれるか否かをチェックする。
【００４８】
Packet Distributer２１は、管理している行列へのアクセスと判断した場合、アドレス変換し、非ゼロ管理されるブロックが元のアドレス空間では１行ごとに離れたアドレスに配置されていたものを、連続するアドレス空間に配置させる。
【００４９】
ここで、図８は、アドレス変換の処理について説明するための図である。管理単位が４×４のブロックの場合、ＸとＹの下位２bitとがブロック内の位置を示しているため、Packet Distributer２１は、変換前アドレスのＹの下位２bitを、変換後アドレスのＸの下位側に挿入する。なお、行列が３次元以上の場合も、Ｘ以外のブロック内の位置を示すbitをＸの下位側に移動させる。ＸやＹのbit位置は入力パラメータのwidthから算出が可能である。また、Packet Distributer２１は、管理しているどの行列かを示すMatrixIDを変換後アドレスに付加する。
【００５０】
また、Packet Distributer２１は、変換前アドレスのＬ２バンク番号を確認する。本実施の形態では、非ゼロ管理行列を１ブロック行毎にバンク、すなわち、Ｌ２キャッシュ２５ａ〜２５ｄを切り替える。そのため、変換前アドレスのＹの塗り潰しで示した位置の２bitがＬ２バンク番号を示す。Packet Distributer２１は、この２bitの値が指すＬ２キャッシュ２５ａ〜２５ｄのいずれかへ要求を出力する。なお、このＬ２バンク番号を示す２bitは、変換後アドレスに含まれない。出力パラメータは、入力パラメータから変換を行い、アクセス対象行の先頭アドレス、アクセス開始X座標、アクセス個数を含む。なお、ライト要求の場合のみ全て０書き込みを示すフラグを含む。
【００５１】
ライト要求の場合、ライトデータが別途入力されるが、Packet Distributer２１は、この入力ライトデータからライト非ゼロデータの開始Ｘ座標、連続非ゼロデータ列、連続非ゼロデータ列の終端フラグ(Flag-tail)、及び、ライトリクエストの最後の非ゼロデータフラグ(Flag-end)を変換して出力する。
【００５２】
図９は、ライト要求の例を説明するための図である。ライト対象３５は、開始アドレスｇからｋブロック分であるが、実際にライトデータが転送されるのは、非ゼロ領域３６、３７及び３８だけである。それ以外の領域３９は０を書き込む要求として扱われる。非ゼロ領域３６、３７及び３８の最後の非ゼロデータでは、連続非ゼロデータ列の終端フラグ(Flag-tail)が１となり、非ゼロ領域３８の最後の非ゼロデータでは、ライトリクエストの最後の非ゼロデータフラグ(Flag-end)が１となる。
【００５３】
Packet Distributer２１からのリード／ライト要求に基づき、Packet I/F２２ａ〜２２ｄは、Read Ctrl２３ａ〜２３ｄ／Write Ctrl２４ａ〜２４ｄに入力データを振り分ける。  
Read Ctrl２３ａ〜２３ｄはそれぞれ、リード要求に従って、Ｌ２キャッシュ２５ａ〜２５ｄ上のＬ２データ管理構造にアクセスし、アクセス範囲に含まれる非ゼロデータをPacketI/F２２ａ〜２２ｄに出力する。また、Read Ctrl２３ａ〜２３ｄは、Ｌ２キャッシュ２５ａ〜２５ｄを用いず、直接メインメモリ８上から非ゼロデータおよび非ゼロ管理情報を取得してもよい。
【００５４】
出力データは、リード非ゼロデータの開始Ｘ座標、連続非ゼロデータ列、連続非ゼロデータ列の終端フラグ(Flag-tail)、リードリクエストの最後の非ゼロデータフラグ(Flag-end)、及び、非ゼロデータフラグを含む。
【００５５】
Read Ctrl２３ａ〜２３ｄは、非ゼロ領域の非ゼロデータのみを出力する。すなわち、ゼロデータのデータ列は出力しない。Read Ctrl２３は、非ゼロデータが１つでもある場合、非ゼロデータフラグを１とする。一方、非ゼロデータが１つもリード要求範囲に含まれない場合、Read Ctrl２３は０の非ゼロデータフラグのみを返す。
【００５６】
Read Ctrl２３ａ〜２３ｄから出力されたデータはPacket I/F２２ａ〜２２ｄを介してPacket Distributor２１に入力される。Packet Distributor２１は、マスタモジュールとのリードデータI/Fに合わせてデータを出力する。
【００５７】
一方、Write Ctrl２４ａ〜２４ｄはそれぞれ、ライト要求に従って、Ｌ２キャッシュ２５ａ〜２５ｄ上のＬ２データ管理構造にアクセスし、非ゼロデータおよび非ゼロ管理情報を更新する。また、Write Ctrl２４ａ〜２４ｄは、Ｌ２キャッシュ２５ａ〜２５ｄを用いず、直接メインメモリ８上に非ゼロデータおよび非ゼロ管理情報を保存してもよい。
【００５８】
Address Translator２６ａ〜２６ｄは、Ｌ２キャッシュ２５あるいはRead Ctrl２３あるいはWrite Ctrl２４がメインメモリ８にアクセスする際に、行列管理情報を参照しアドレス変換を行う。このアドレス変換は、Packet Distributor２１が行う変換の逆変換を行う。
【００５９】
Address Translator２６ａ〜２６ｄのアドレス変換により、Ｌ２キャッシュ２５ａ〜２５ｄ上で1つの連続領域に配置されていた１ブロックのデータは、メインメモリ８上では行ごとの連続領域に分割されアクセスされる。なお、Ｌ２キャッシュ２５あるいはRead Ctrl２３あるいはWrite Ctrl２４は、Address Translator２６によるアドレス変換を用いず、直接メインメモリ８へアクセスしてもよい。
【００６０】
ここで、Read Ctrl２３における読み出し動作について説明する。なお、Read Ctrl２３ａ〜２３ｄは同様の構成のため、Read Ctrl２３ａについてのみ説明する。図１０は、Read Ctrl２３ａの構成図である。Read Ctrl２３ａは、Info Checker４１と、Read Requestor４２と、 Data Requestor４３と、Data Output４４と、Read Data Receiver４５とを有している。
【００６１】
Info Checker４１は、Packet I/F２２ａからリード要求が入力されると、非ゼロ管理情報の読み出しと、内容のチェックとを行う。  
Info Checker４１は、非ゼロ管理情報のリード要求をRead Requestor４２へ出力する。Read Requestor４２は、非ゼロ管理情報のリード要求に従って、Ｌ２キャッシュ２５ａへ非ゼロ管理情報を含むブロックのリード要求を出力する。ブロックのリード要求に従って、リードデータがＬ２キャッシュ２５ａから読み出され、Read Data Receiver４５へ入力される。Read Data Receiver４５は、リードデータから非ゼロ管理情報を読み出し、Info Checker４１に出力する。
【００６２】
Info Checker４１は、非ゼロ管理情報に従って、読み出す対象の非ゼロ列を検出すると、Data Requestor４３へ該非ゼロ列の座標と読み出し開始要求とを出力する。また、Info Checker４１は、非ゼロ管理情報に従って、非ゼロデータの開始位置をData Output４４へ出力する。
【００６３】
Data Requestor４３は、非ゼロ列の読み出し開始座標をData Output４４に出力し、読み出し領域に含まれる非ゼロブロックのリード要求をRead Requestor４２に出力する。そして、Read Requestor４２は、非ゼロブロックのリード要求に従って、Ｌ２キャッシュ２５ａへリード要求を出力する。非ゼロブロックのリード要求に従って、リードデータがＬ２キャッシュ２５ａから読み出され、Read Data Receiver４５を介してData Output４４に入力される。
【００６４】
Data Output４４は、Info Checker４１からの非ゼロデータの開始位置を用いて、ヘッダを出力する。また、Data Output４４は、Read Data Receiver４５から入力されたリードデータをPacket I/F２２ａに出力する。
【００６５】
Data Requestor４３は、連続する非ゼロブロックのリード要求が終了すると、Data Output４４に終了フラグを出力する。Data Output４４は、終了フラグが入力されると、連続非ゼロデータ列の終端フラグ(Flag-tail)を出力する。連続する非ゼロブロックが複数ある場合、Info Checker４１が非ゼロ管理情報のリード要求を再度Read Requestor４２へ出力し、上述した動作を行う。
【００６６】
また、Info Checker４１は、対象リード領域内での読み出しが終了すると、終了信号をData Output４４に出力する。Data Output４４は、終了信号が入力されると、リードリクエストの最後の非ゼロデータフラグ(Flag-end)を出力し、読み出し動作が終了となる。
【００６７】
次に、このように構成された行列管理エンジン４の動作について説明する。  
リード要求された場合の処理の例を図１１及び図１２を用いて説明する。図１１及び図１２は、Ｓ[ｍ][ｎ０]〜Ｓ[ｍ][ｎ１]のデータを読み出す処理を説明するためのフローチャートである。
【００６８】
まず、Read Ctrl２３ａは、ｍ行目のｎ０〜ｎ１ブロック列へのリード要求が入力されると（Ｓ１）、Ｙ＝ｍ、Ｘ＝１を設定する（Ｓ２）。次に、Read Ctrl２３ａは、Ｒ[Ｙ][Ｘ−１]の非ゼロ管理情報を読み出す（Ｓ３）。すなわち、このＳ３では、Ｘ、Ｙが示すブロックの１つ前の位置の非ゼロ管理情報が読み出される。次に、読み出された非ゼロ管理情報の値をNum（連続する非ゼロの個数）、Next（次の非ゼロ管理情報までの距離）とし、現在のＸの値をPosに退避する（Ｓ４）。
【００６９】
次に、Read Ctrl２３ａは、非ゼロデータ列が存在するか否かを判定する（Ｓ５）。非ゼロデータ列が存在しないと判定した場合（Ｓ５−ＮＯ）、すなわち、Num＝０の場合、Read Ctrl２３ａは、次の非ゼロデータ列が存在するか否かを判定する（Ｓ６）。後続に非ゼロデータ列が存在すると判定した場合（Ｓ６−ＹＥＳ）、Ｘ=Pos＋Nextに更新する（Ｓ７）。更新されたＸは、次の非ゼロデータ列の先頭の非ゼロブロックのＸ座標を示す。
【００７０】
次に、Read Ctrl２３ａは、Ｘが読み出し範囲よりも大きいか否かを判定する（Ｓ８）。ｎ１＜Ｘが非成立の場合（Ｓ８−ＮＯ）、次の非ゼロ列は読み出し範囲内に含まれる可能性があり、Ｓ３に戻る。
【００７１】
一方、非ゼロデータ列が存在すると判定した場合（Ｓ５−ＹＥＳ）、Read Ctrl２３ａは、非ゼロデータ列の中に読み出し範囲が含まれるか否か(((X<=n1)&&(X+Num>n0)))を判定する（Ｓ９）。読み出し範囲でない場合（Ｓ９−ＮＯ）は、Ｓ６に進み、読み出し範囲に含まれる場合（Ｓ９−ＹＥＳ）は、Ｓ１０に進む。
【００７２】
読み出し範囲に含まれると判定した場合（Ｓ９−ＹＥＳ）、Read Ctrl２３ａは、Ｘが読み出し範囲内（ｎ０≦Ｘ≦ｎ１）か否かを判定する（Ｓ１０）。Ｘが読み出し範囲内でない場合（Ｓ１０−ＮＯ）、Ｘ＝Ｘ＋１、Num＝Num−１に更新し（Ｓ１１）、Ｓ１０に戻る。一方、Ｘが読み出し範囲内であると判定される（Ｓ１０−ＹＥＳ）と、図１２のＳ１２に進む。
【００７３】
Read Ctrl２３ａは、ヘッダを出力する（Ｓ１２）。このヘッダは、非ゼロデータ列の開始位置情報であり、Ｘの値がヘッダとして出力される。次に、Ｓ[Ｙ][Ｘ]の非ゼロブロックがリードされ（Ｓ１３）、リードされたブロックがリード要求元へ出力される（Ｓ１４）。そして、Ｘ＝Ｘ＋１、Num＝Num−１に更新する（Ｓ１５）。
【００７４】
次に、Read Ctrl２３ａは、非ゼロデータ列の読み出しが終了したか否かを判定する（Ｓ１６）。まだ読み出す非ゼロデータが残っていると判定された場合（Ｓ１６−ＮＯ）、すなわち、Num＞０の場合、Read Ctrl２３ａは、Ｘが読み出し範囲内（ｎ０≦Ｘ≦ｎ１）か否かを判定する（Ｓ１７）。ｎ０≦Ｘ≦ｎ１が成立した場合（Ｓ１７−ＹＥＳ）、Ｓ１３に戻る。
【００７５】
一方、読み出す非ゼロデータが残っていないと判定された場合（Ｓ１６−ＮＯ）、すなわち、Num＝０の場合、連続する非ゼロデータ列が一旦終了するため、Ｓ１８に進む。また、Ｘが読み出し範囲内（ｎ０≦Ｘ≦ｎ１）でないと判定された場合（Ｓ１７−ＮＯ）も、Ｓ１８に進む。そして、Flag-tailを出力し（Ｓ１８）、図１１のＳ６に進む。
【００７６】
次の非ゼロデータ列が存在しない場合（Ｓ６−ＮＯ）、および、Ｘが読み出し範囲よりも大きい場合（Ｓ８−ＹＥＳ）、Ｓ１９に進む。そして、Flag-endを出力して（Ｓ１９）、リード処理を終了する。
【００７７】
ここで、Read Ctrl２３ａが、図３のブロック行Ｂ１の４〜８ブロック列（Ｓ[１][４]〜Ｓ[１][８]）を読み出す場合について説明する。ブロック列Ｓ[１][４]〜Ｓ[１][８]を読み出す場合、図４の行列データＲ[１][４]〜Ｒ[１][８]を参照することになる。ｍ＝１、ｎ０＝４、及び、ｎ１＝８となる。  
まず、Read Ctrl２３ａは、１行目の４〜８ブロック列へのリード要求が入力されると（Ｓ１）、Ｙ＝１、Ｘ＝１を設定する（Ｓ２）。
【００７８】
Read Ctrl２３ａは、非ゼロ管理領域の非ゼロ管理情報Ｒ[１][０]を読み出し（Ｓ３）、Num＝０、Next＝１、Pos＝１となる（Ｓ４）。非ゼロ管理領域Ｒ[１][０]の場合、非ゼロデータが存在しない（Num＝０）ので、Ｓ６に進む。Next＝１であるため、Read Ctrl２３ａは、次の非ゼロデータ列が存在すると判定し（Ｓ６−ＹＥＳ）、Ｘ＝１＋１とする（Ｓ７）。Ｘ＝２＜ｎ１＝８（Ｓ８−ＮＯ）なので、Ｓ３に戻る。
【００７９】
次に、Read Ctrl２３ａは、Ｒ[１][１]の非ゼロ管理情報を読み出す（Ｓ３）。Num＝２、Next＝４、Pos＝２となる（Ｓ４）。この場合、非ゼロデータが存在する（Ｓ５−ＹＥＳ）が、非ゼロデータが存在する範囲（Ｒ[１][２]〜Ｒ[１][３]）は読み出し範囲に入っていない（Ｓ９−ＮＯ）ため、Ｓ６に進む。Next＝４であるため、Read Ctrl２３ａは、次の非ゼロデータ列が存在する（Ｓ６−ＹＥＳ）と判定し、Ｘ＝２＋４とする（Ｓ７）。Ｘ＝６＜ｎ１＝８（Ｓ８−ＮＯ）なので、Ｓ３に戻る。
【００８０】
次に、Read Ctrl２３ａは、Ｒ[１][５]の非ゼロ管理情報を読み出す（Ｓ３）。Num＝２、Next＝５、Pos＝６となる（Ｓ４）。この場合、非ゼロデータが存在し（Ｓ５−ＹＥＳ）、かつ、非ゼロデータが存在する範囲（Ｒ[１][６]〜Ｒ[１][７]）が読み出し範囲に含まれる（Ｓ９−ＹＥＳかつＳ１０−ＹＥＳ）ので、Ｓ１２に進む。
【００８１】
Read Ctrl２３ａは、ヘッダを出力し（Ｓ１２）、キャッシュからＳ[１][６]のデータを読み出す（Ｓ１３）。そして、Read Ctrl２３ａは、Ｓ[１][６]のデータをリード要求元へ出力し（Ｓ１４）、Ｘ＝６＋１、Num＝２−１とする（Ｓ１５）。Num＝１なので、まだ読み出す非ゼロデータが残っていると判定される（Ｓ１６−ＮＯ）。また、Ｘ＝７なので、Ｘが読み出し範囲内に存在するため（Ｓ１７−ＹＥＳ）、Ｓ１３に戻る。
【００８２】
Read Ctrl２３ａは、Ｓ[１][７]のデータを読み出してリード要求元へ出力し（Ｓ１３、Ｓ１４）、Ｘ＝７＋１、Num＝１−１とする（Ｓ１５）。Num＝０なので、読み出す非ゼロデータが残っていないと判定され（Ｓ１６−ＹＥＳ）、Read Ctrl２３ａはFlag-tailを出力し（Ｓ１８）、Ｓ６に戻る。
【００８３】
Next＝５であるため、後続に非ゼロデータ列が存在すると判定され（Ｓ６−ＹＥＳ）、Ｘ＝６＋５とする（Ｓ７）。Ｘ＝１１＞ｎ１＝８となるため（Ｓ８−ＹＥＳ）、Read Ctrl２３ａはFlag-endを出力し（Ｓ１９）、リード処理を終了する。
【００８４】
次に、Write Ctrl２４における書き込み動作について説明する。なお、Write Ctrl２４ａ〜２４ｄは同様の構成のため、Write Ctrl２４ａについてのみ説明する。図１３は、Write Ctrl２４ａの構成図である。Write Ctrl２４ａは、B-Searcher５１と、Read Requestor５２と、A-Searcher５３と、Read Data Receiver５４と、Write Data Receiver５５と、B-Updater５６と、Write Requestor５７と、Data Writer５８と、Last-Info Updater５９とを有している。
【００８５】
B-Searcher５１は、Packet I/F２２ａからライト要求が入力されると、非ゼロデータ列Ｂの探索を行う。  
まず、B-Searcher５１は、非ゼロ管理情報のリード要求をRead Requestor５２へ出力する。Read Requestor５２は、非ゼロ管理情報へのリード要求に従って、Ｌ２キャッシュ２５ａへ非ゼロ管理情報を含むブロックのリード要求を出力する。ブロックのリード要求に従って、リードデータがＬ２キャッシュ２５ａから読み出され、Read Data Receiver５４へ入力される。Read Data Receiver５４は、リードデータから非ゼロ管理情報を読み出し、B-Searcher５１に出力する。
【００８６】
B-Searcher５１は、読み出された非ゼロ管理情報を用いた非ゼロデータ列Ｂの探索を終了すると、A-Searcher５３に対して非ゼロデータ列Ｂの情報と共に、動作開始要求を出力する。
【００８７】
A-Searcher５３は、非ゼロデータ列Ｂの情報及び動作開始要求が入力されると、非ゼロデータ列Ａの探索を行う。なお、非ゼロデータ列Ａの探索については、後述する。A-Searcher５３は、B-Searcher５１と同様に、非ゼロ管理情報のリード要求をRead Requestor５２に行い、Read Data Receiver５４から非ゼロ管理情報を読み出す。
【００８８】
A-Searcher５３は、読み出された非ゼロ管理情報を用いた非ゼロデータ列Ａの探索を終了すると、B-Updater５６へ非ゼロデータ列Ａ及びＢの情報と共に、ライト要求を出力する。
【００８９】
B-Updater５６は、入力された非ゼロデータ列Ａ及びＢの情報と、ライト要求とに従って、非ゼロデータ列Ｂの開始位置−１の非ゼロ管理情報の更新を行う。このとき、非ゼロデータ列開始位置は、Write Data Receiver５５から入力される。非ゼロ管理情報の更新は、B-Updater５６がWrite Requestor５７に対しライト要求を出力し、Write Requestor５７がＬ２キャッシュ２５ａに対して該当のブロックのライト要求を出力する。
【００９０】
Write Data Receiver５５には、非ゼロデータブロックのライトデータ、及び、非ゼロデータ列の開始位置がPacket I/F２３ａから入力される。Write Data Receiver５５は、入力された非ゼロデータブロックのライトデータ、及び、非ゼロデータ列の開始位置を、B-Updater５６及びData Writer５８へ出力する。
【００９１】
B-Updater５６は、非ゼロデータ列Ｂの開始位置−１の非ゼロ管理情報の更新終了後、Data Write５８へ動作開始要求を出力する。
【００９２】
Data Writer５８は、動作開始要求が入力されると、ライトデータの書き込みを行う。Data Writer５８は、非ゼロデータの書き込みと非ゼロ管理情報の書き込みについて、B-Updater５６と同様、Write Requestor５７に対しライト要求を出力し、Write Requestor５７がＬ２キャッシュ２５ａに対して該当のブロックのライト要求を出力する。Data Writer５８は、ライトデータの書き込み終了後、Last-Info Updater５９へ動作開始要求を出力する。
【００９３】
Last-Info Updater５９は、最後の非ゼロ管理情報の書き込みと、ｎ１位置（後述するライトデータの最終列）のライトデータの書き込みとを行う。Last-Info Updater５９は、非ゼロ管理情報の書き込みについて、B-Updater５６と同様、Write Requestor５７に対しライト要求を出力し、Write RequestorがＬ２キャッシュ２５ａに対して該当のブロックのライト要求を出力する。
【００９４】
ここで、ライト要求された場合の処理の例を図１４を用いて説明する。図１４は、ｍ行目のブロック行のn0ブロック列〜n1ブロック列に対してデータを書き込む処理を説明するためのフローチャートである。
【００９５】
まず、Write Ctrl２４ａは、m行目n0列〜n1列へのライト要求が入力されると（Ｓ２１）、非ゼロデータ列Ｂ及びＡを探索する（Ｓ２２）。ここで、非ゼロデータ列Ｂは、n0列〜n1列の領域より小さい位置から開始される連続非ゼロデータ列の中で、先頭にある非ゼロデータ列である。非ゼロデータ列Ａは、n0列〜n1列の領域より大きい位置にあるデータを含む連続非ゼロデータ列の中で、末尾にある非ゼロデータ列である。非ゼロデータ列Ｂの条件を満たす非ゼロデータ列が存在しない場合、非ゼロデータ列Ｂの開始位置は１とし、非ゼロデータ列Ａの条件を満たす非ゼロデータ列が存在しない場合、非ゼロデータ列Ａは存在しないとする。
【００９６】
次に、Write Ctrl２４ａは、非ゼロデータ列Ｂの開始位置−１の位置の非ゼロ管理情報の更新、及び、ライトデータの書き込みを行う（Ｓ２３）。
【００９７】
そして、Write Ctrl２４ａは、n0列〜n1列の最後の非ゼロ管理情報、及び、n1列の非ゼロ管理情報の更新を行い（Ｓ２４）、処理を終了する。
【００９８】
次に、Ｓ２２の具体的な処理を図１５を用いて説明する。図１５は、非ゼロデータ列Ｂ及びＡの探索の処理を説明するためのフローチャートである。
【００９９】
まず、Write Ctrl２４ａは、m行目n0列〜n1列へのライト要求が入力されると（Ｓ３１）、Ｙ＝ｍ、Ｘ＝１を設定する（Ｓ３２）。次に、Write Ctrl２４ａは、Ｒ[Ｙ][Ｘ−１]の非ゼロ管理情報を読み出す（Ｓ３３）。このＳ３３の処理では、Ｘ、Ｙが示すブロックの１つ前の位置の非ゼロ管理情報が読み出される。次に、読み出された非ゼロ管理情報の値をNum（連続する非ゼロの個数）、Next（次の非ゼロ管理情報までの距離）とする（Ｓ３４）。
【０１００】
Write Ctrl２４ａは、次の非ゼロデータ列が存在するか否かを判定する（Ｓ３５）。次の非ゼロデータ列が存在すると判定した場合（Ｓ３５−ＹＥＳ）、すなわち、Nextが０でない場合、Write Ctrl２４ａは、次の非ゼロデータ列がn0列以降になるか否かを判定する（Ｓ３６）。次の非ゼロデータ列の先頭非ゼロブロックもn0列未満の位置にあると判定した場合（Ｓ３６−ＮＯ）、Write Ctrl２４ａは、ＸをＸ＋Nextで更新し（Ｓ３７）、Ｓ３３に戻る。
【０１０１】
一方、次の非ゼロデータ列が存在しないと判定した場合（Ｓ３５−ＮＯ）、または、次の非ゼロデータ列の先頭非ゼロブロックがn0列以降にあると判定した場合（Ｓ３６−ＹＥＳ）、Write Ctrl２４ａは、Ｘから始まる非ゼロ列を非ゼロデータ列Ｂとして検出し、Ｂ＝Ｘ、Num＝Num、Next＝Nextを設定する（Ｓ３８）。このＳ３８の処理により、非ゼロデータ列Ｂと、非ゼロデータ列Ｂを示す非ゼロ管理情報が検出される。
【０１０２】
次に、Write Ctrl２４ａは、非ゼロデータ列が存在するか否かを判定する（Ｓ３９）。次の非ゼロデータ列が存在すると判定した場合（Ｓ３９−ＹＥＳ）、Write Ctrl２４ａは、非ゼロデータ列の末端がn1列より後か否かを判定する（Ｓ４０）。非ゼロデータ列の末端がn1列より後でないと判定した場合（Ｓ４０−ＮＯ）、Write Ctrl２４ａは、次の非ゼロデータ列が存在するか否かを判定する（Ｓ４１）。次の非ゼロデータ列が存在すると判定した場合（Ｓ４１−ＹＥＳ）、Write Ctrl２４ａは、ＸをＸ＋Nextに更新する（Ｓ４２）。  
次に、Write Ctrl２４ａは、Ｒ[Ｙ][Ｘ−１]の非ゼロ管理情報を読み出し（Ｓ４３）、読み出した非ゼロ管理情報の値をNum、Nextとする（Ｓ４４）。そして、Ｓ３９に戻る。
【０１０３】
一方、非ゼロデータ列の末端がn1列より後であると判定した場合（Ｓ４０−ＹＥＳ）、Write Ctrl２４ａは、Ｘから始まる非ゼロデータ列を非ゼロデータ列Ａとして検出し、Ａ＝Ｘ、Num＝Num、Next＝Nextを設定し（Ｓ４５）、処理を終了する。このＳ４５の処理により、非ゼロデータ列Ａと、非ゼロデータ列Ａを示す管理情報が検出される。
【０１０４】
なお、Ｓ３９で次の非ゼロデータ列が存在しない判定した場合（Ｓ３９−ＮＯ）、Write Ctrl２４ａは、非ゼロデータ列Ａは存在しない（Ｓ４６）として、処理終了する。同様に、Ｓ４１で次の非ゼロデータ列が存在しない判定した場合（Ｓ４１−ＮＯ）、Write Ctrl２４ａは、非ゼロデータ列Ａは存在しない（Ｓ４７）として、処理終了する。以上の処理により、非ゼロデータ列Ｂの開始位置、及び、非ゼロデータ列Ａの開始位置が探索される。
【０１０５】
次に、Ｓ２３の具体的な処理を説明する。図１６は、非ゼロデータ列Ｂの非ゼロ管理情報の更新を説明するためのフローチャートである。図１７は、ライトデータの書き込み処理を説明するためのフローチャートである。
【０１０６】
Write Ctrl２４ａは、範囲内の書き込みデータが全て０であるか、すなわち、書き込みデータに非ゼロデータが含まれているか否かを判定する（Ｓ５１）。書き込みデータに非ゼロデータが含まれていると判定した場合（Ｓ５１−ＮＯ）、Write Ctrl２４ａは、非ゼロデータ列の開始位置（ｑ）を入力する（Ｓ５２）。
【０１０７】
次に、Write Ctrl２４ａは、非ゼロデータ列の書き込みがn0列から開始か否かを判定する（Ｓ５３）。非ゼロデータ列の書き込みがn0列からでないと判定した場合（Ｓ５３−ＮＯ）、Write Ctrl２４ａは、非ゼロデータ列Ｂがn0〜n1列に含まれるか否かを判定する（Ｓ５４）。すなわち、このＳ５４の処理では、ゼロデータ書き込みで非ゼロデータ列Ｂの長さが変わるかがチェックされる。非ゼロデータ列Ｂがn0〜n1列に含まれると判定した（ゼロデータ書き込みで非ゼロデータ列Ｂの長さが変わる）場合（Ｓ５４−ＹＥＳ）、Write Ctrl２４ａは、非ゼロデータ列ＢのNumをn0〜n1列に重なる分だけ減少し（Ｓ５５）、非ゼロデータ列ＢのNextを非ゼロデータ列の開始位置ｑを指すように変更する（Ｓ５６）。
【０１０８】
次に、Write Ctrl２４ａは、非ゼロデータ列の開始位置ｑを非ゼロデータ列W0の開始位置として設定する（Ｓ５７）。ここでは、Write Ctrl２４ａは、Pos＝ｑ、Cnt＝０、Start＝ｑを設定し、図１７の処理に進む。
【０１０９】
一方、非ゼロデータ列の書き込みがn0列から開始と判定された場合（Ｓ５３−ＹＥＳ）、Write Ctrl２４ａは、非ゼロデータ列Ｂと非ゼロデータ列W0が接するか又は重なるかを判定する（Ｓ５８）。非ゼロデータ列Ｂと非ゼロデータ列W0が接しない、かつ、重ならないと判定した場合（Ｓ５８−ＮＯ）、Ｓ５６に進む。一方、非ゼロデータ列Ｂと非ゼロデータ列W0が接するか又は重なると判定された場合（Ｓ５８−ＹＥＳ）、Write Ctrl２４ａは、非ゼロデータ列Ｂの開始位置を非ゼロデータ列W0の開始位置として設定する（Ｓ５９）。ここでは、Write Ctrl２４ａは、Pos＝ｑ、Cnt＝n0−Ｂの開始位置、Start＝Ｂの開始位置を設定し、図１７の処理に進む。
【０１１０】
Ｓ５７またはＳ５９の処理が実行されると、図１７に移り、Write Ctrl２４ａは、非ゼロデータブロックを入力し（Ｓ６０）、入力した非ゼロデータブロックをＳ[m][Pos]の位置に書き込む（Ｓ６１）。次に、Write Ctrl２４ａは、Pos及びCntのカウントアップ（Pos＝Pos＋１、Cnt＝Cnt＋１）を行い（Ｓ６２）、非ゼロデータ列W0の書き込みが終了したか否かを判定する（Ｓ６３）。非ゼロデータ列W0の書き込みが終了していないと判定した場合（Ｓ６３−ＮＯ）、Ｓ６０に戻る。一方、非ゼロデータ列W0の書き込みが終了したと判定した場合（Ｓ６３−ＹＥＳ）、Write Ctrl２４ａは、次の書き込み非ゼロデータ列(W1とする)が存在するか否かを判定する（Ｓ６４）。次の書き込み非ゼロデータ列W1が存在すると判定した場合（Ｓ６４−ＹＥＳ）、Write Ctrl２４ａは、次の非ゼロデータ列W1の開始位置（ここでは、ｐとする）を入力する（Ｓ６５）。
【０１１１】
次に、Write Ctrl２４ａは、非ゼロデータ列W0のNum、Nextを更新する（Ｓ６６）。ここでは、Write Ctrl２４ａは、Num＝Cnt、Next＝ｐ−Startを設定する。そして、Write Ctrl２４ａは、非ゼロデータ列W1を次の非ゼロデータ列W0に設定し（Ｓ６７）、Ｓ６０に戻る。ここでは、Write Ctrl２４ａは、Pos＝ｐ、Cnt＝０、Start＝ｐを設定する。一方、次の書き込み非ゼロデータ列W1が存在しないと判定された場合（Ｓ６４−ＮＯ）、図１６のエンドに戻る。
【０１１２】
また、書き込みデータに非ゼロデータが含まれていない（範囲内の書き込みデータが全て０）と判定した場合（Ｓ５１−ＹＥＳ）、Write Ctrl２４ａは、非ゼロデータ列Ｂの要素がn0〜n1列に含まれるか否かを判定する（Ｓ６８）。非ゼロデータ列Ｂがn0〜n1列に含まれていないと判定した場合（Ｓ６８−ＮＯ）、Ｓ７０に進む。一方、非ゼロデータ列Ｂがn0〜n1列に含まれていると判定した場合、Write Ctrl２４ａは、非ゼロデータ列ＢのNumをn0〜n1列に重なる分だけ減少する（Ｓ６９）。
【０１１３】
次に、Write Ctrl２４ａは、非ゼロデータ列Ａが存在するか否かを判定する（Ｓ７０）。非ゼロデータ列Ａが存在しないと判定した場合（Ｓ７０−ＮＯ）、Write Ctrl２４ａは、非ゼロデータ列ＢのNextを０に変更し（Ｓ７１）、処理を終了する。一方、非ゼロデータ列Ａが存在すると判定した場合（Ｓ７０−ＹＥＳ）、Write Ctrl２４ａは、書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所があるか否かを判定する（Ｓ７２）。書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所がないと判定した場合（Ｓ７２−ＮＯ）、Write Ctrl２４ａは、非ゼロデータ列ＢのNextを非ゼロデータ列Ａを指すように変更し（Ｓ７３）、処理を終了する。一方、書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所があると判定した場合（Ｓ７２−ＹＥＳ）、Write Ctrl２４ａは、非ゼロデータ列ＢのNextをn1＋１を指すように変更し（Ｓ７４）、処理を終了する。
【０１１４】
図１８は、最後の非ゼロ管理情報の更新、及び、n1列の非ゼロ管理情報の更新処理を説明するためのフローチャートである。  
まず、Write Ctrl２４ａは、ライト範囲内全て０の書き込みか否かを判定する（Ｓ８１）。ライト範囲内全て０の書き込みでないと判定した場合（Ｓ８１−ＮＯ）、Write Ctrl２４ａは、非ゼロデータ列Ａが存在するか否かを判定する（Ｓ８２）。非ゼロデータ列Ａが存在すると判定した場合（Ｓ８２−ＹＥＳ）、Write Ctrl２４ａは、書き込みの最終ブロックが０か否かを判定する（Ｓ８３）。
【０１１５】
書き込みの最終ブロックが０と判定した場合（Ｓ８３−ＹＥＳ）、Write Ctrl２４ａは、書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所があるか否かを判定する（Ｓ８４）。書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所があると判定した場合（Ｓ８４−ＹＥＳ）、Write Ctrl２４ａは、最後の非ゼロ管理情報を更新する（Ｓ８５）。ここでは、Write Ctrl２４ａは、Next＝n1＋１−Start、Num＝Cntに設定する。最後に、Write Ctrl２４ａは、n1列の非ゼロ管理情報を更新し（Ｓ８６）、処理を終了する。ここでは、Write Ctrl２４ａは、Next ＝Ａ_Next、Num＝Ａ_Num−（n1＋１−Ａの開始位置）に設定する。
【０１１６】
一方書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所がないと判定された場合（Ｓ８４−ＮＯ）、Write Ctrl２４ａは、最後の非ゼロ管理情報をNext=Ａの開始位置−Start、Num＝Cntに更新し（Ｓ８７）、処理を終了する。
【０１１７】
また、書き込みの最終ブロックが０でないと判定された場合（Ｓ８３−ＮＯ）、Write Ctrl２４ａは、書き込みの最終ブロックが非ゼロデータ列Ａと接続又は重なるか否かを判定する（Ｓ８８）。書き込みの最終ブロックが非ゼロデータ列Ａと接続又は重なると判定した場合（Ｓ８８−ＹＥＳ）、Write Ctrl２４ａは、最後の非ゼロ管理情報をNext =Ａ_Next、Num＝Cntに更新し（Ｓ８９）、処理を終了する。一方、書き込みの最終ブロックが非ゼロデータ列Ａと接続しないかつ重ならないと判定した場合（Ｓ８８−ＮＯ）、Write Ctrl２４ａは、最後の非ゼロ管理情報をNext=Ａの開始位置−Start、Num＝Cntに更新し（Ｓ９０）、処理を終了する。
【０１１８】
また、非ゼロデータ列Ａが存在しないと判定された場合（Ｓ８２−ＮＯ）、Write Ctrl２４ａは、最後の非ゼロ管理情報をNext=０、Num＝Cntに更新し（Ｓ９１）、処理を終了する。
【０１１９】
また、ライト範囲内全て０の書き込みと判定された場合（Ｓ８１−ＹＥＳ）、Write Ctrl２４ａは、非ゼロデータ列Ａが存在するか否かを判定する（Ｓ９２）。非ゼロデータ列Ａが存在しないと判定した場合（Ｓ９２−ＮＯ）、処理を終了する。一方、非ゼロデータ列Ａが存在すると判定した場合（Ｓ９２−ＹＥＳ）、Write Ctrl２４ａは、書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所があるか否かを判定する（Ｓ９３）。書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所がないと判定した場合（Ｓ９３−ＮＯ）、処理を終了する。一方、書き込みで非ゼロデータ列Ａの非ゼロ列が０に変わる箇所があると判定した場合（Ｓ９３−ＹＥＳ）、Write Ctrl２４ａは、n1列の非ゼロ管理情報が、Next＝Ａ_Next、Num＝Ａ_Num−（n1＋１−Ａの開始位置）に更新し（Ｓ９４）、処理を終了する。
【０１２０】
次に、図３に示す疎行列Ｓの２行目（ｍ＝２）のブロック行Ｂ２に対してデータを書き込む例を図１９及び図２０を用いて説明する。図１９及び図２０は、書き込むデータ列と２行目の非ゼロ管理情報を示した図である。
【０１２１】
図１９において、符号７０は、データが書き込まれる前の疎行列Ｓの２行目のブロック行Ｂ２のデータである。符号７１ａ〜７１ｈにおいて、ハッチングが付加された四角は非ゼロデータを示し、灰色の四角はゼロデータを示し、白い四角は書き込みを行わないことを示している。符号７２ａ〜７２ｈはそれぞれ、例１〜例８の書き込みデータ（符号７１ａ〜７１ｈ）が書き込まれた後のブロック行Ｂ２のデータを示している。  まず、Ｓ２２の非ゼロデータ列Ｂ及びＡの探索処理について図１９の例１を用いて説明する。例１は、４〜１１列（n0＝４、n1＝１１）までデータの書き込みを行い、５、６、９及び１０列に非ゼロデータを書き込み、４、７、８及び１１列にゼロデータを書き込む。
【０１２２】
非ゼロデータ列Ｂの探索では、まず、Write Ctrl２４ａは、先頭の非ゼロ管理情報Ｒ[２][０]を読み出す。Write Ctrl２４ａは、読み出した値(Next)から、次の非ゼロ列の開始位置を求める。例１の場合、Ｒ[２][３]となる。
【０１２３】
次に、Write Ctrl２４ａは、求めた非ゼロ列の開始位置が書き込みデータの範囲内（Ｒ[２][４]〜Ｒ[２][１１]）に入っているか否かをチェックする。求めた非ゼロ列の開始位置が書き込みデータの範囲内に入っていた場合は、読み出した非ゼロ管理情報の位置＋１が非ゼロデータ列Ｂの開始位置となる。入っていなかった場合は、次の非ゼロ管理情報を読み出す。例１の場合、Ｒ[２][３]は、書き込みデータの範囲に入っていないため、次の非ゼロ管理情報Ｒ[２][２]を読み出す。
【０１２４】
Write Ctrl２４ａは、以降、非ゼロデータ列Ｂが検出されるまで同様の処理を行う。例１の場合、次の非ゼロ列の開始位置がＲ[２][７]となった際に、非ゼロデータ列Ｂの開始位置は、非ゼロ管理情報Ｒ[２][２]の位置＋１、すなわち、３となる。
【０１２５】
一方、非ゼロデータ列Ａの探索では、まず、Write Ctrl２４ａは、非ゼロ管理情報の位置を非ゼロデータ列Ｂの開始位置−１の位置に初期化する。そして、現在の非ゼロ管理情報の位置から非ゼロ管理情報を読み出し、非ゼロデータ列の最後の位置を、現在の非ゼロ管理情報の位置＋Numから求める。例１の場合、２＋２＝４より、Ｒ[２][４]となる。
【０１２６】
次に、Write Ctrl２４ａは、求めた非ゼロデータ列の最後の位置が書き込みデータ（Ｒ[２][４]〜Ｒ[２][１１]）の範囲に入っているか否かをチェックする。求めた非ゼロデータ列の最後の位置が書き込みデータの範囲に入っていない場合、現在の非ゼロ管理情報の位置＋１が非ゼロデータ列Ａの開始位置となる。この場合、Ｒ[２][４]は、書き込みデータの範囲に入っているため、Write Ctrl２４ａは、非ゼロ管理情報の位置を、次の非ゼロ管理情報Ｒ[２][６]の位置（６）に更新する。
【０１２７】
Write Ctrl２４ａは、以降、非ゼロデータ列Ａが検出されるまで同様の処理を行う。ここで、次の非ゼロ管理情報がない場合、非ゼロデータ列Ａが存在しないとなる。例１の場合、非ゼロ管理情報Ｒ[２][１０]の非ゼロデータ列の最後の位置がＲ[２][１２]の時、書き込みデータの範囲外になるため、非ゼロデータ列Ａの開始位置は、非ゼロ管理情報Ｒ[２][１０]の位置＋１、すなわち、１１となる。図２０の例７及び例８の場合、Ｒ[２][１２]が書き込みデータの範囲内となり、その次の非ゼロデータ列が存在しないため、非ゼロデータ列Ａが存在しないとなる。
【０１２８】
次に、Write Ctrl２４ａが、図１９の例１のデータを書き込む場合の、非ゼロデータ列Ｂ及びＡを探索する処理について、図１５を用いて説明する。  
まず、Write Ctrl２４ａは、２行目４列〜１１列へのライト要求が入力されると（Ｓ３１）、Ｙ＝２、Ｘ＝１を代入し（Ｓ３２）、Ｒ[２][０]の非ゼロ管理情報を読み出す（Ｓ３３）。そして、Write Ctrl２４ａは、読み出した非ゼロ管理情報の値をNum＝１、Next＝２とする（Ｓ３４）。
【０１２９】
次に、Write Ctrl２４ａは、Nextが０でないため次の非ゼロデータ列があると判定し（Ｓ３５−ＹＥＳ）、さらに、Ｘ＋Next＝３のため（（Ｘ＋Next）≧４）が非成立となり、次の非ゼロデータ列の先頭非ゼロブロックも４列未満の位置にあると判定する（Ｓ３６−ＮＯ）。Write Ctrl２４ａは、Ｘを３（＝１＋２）に更新し（Ｓ３７）、Ｓ３３に戻る。この更新されたＸ（＝３）が、次の非ゼロデータ列の先頭非ゼロブロックのＸ座標を示す。
【０１３０】
Write Ctrl２４ａは、Ｒ[２][２]の非ゼロ管理情報を読み出し（Ｓ３３）、Num＝２、Next＝４とする（Ｓ３４）。Write Ctrl２４ａは、Nextが０でないため次の非ゼロデータ列があると判定し（Ｓ３５−ＹＥＳ）、さらに、（（Ｘ＋Next）≧４）が成立するため、次の非ゼロデータ列の先頭非ゼロブロックが４列以上の列にある（Ｓ３６−ＹＥＳ）と判定する。これにより、Write Ctrl２４ａは、Ｘ＝３から始まる非ゼロデータ列を非ゼロデータ列Ｂとし、Ｂ＝Ｘ＝３、Num＝２、Next＝４を設定する（Ｓ３８）。
【０１３１】
次に、Write Ctrl２４ａは、Num＝２のため、次の非ゼロデータ列が存在すると判定し（Ｓ３９−ＹＥＳ）、さらに、 Ｘ＋Num−１＝４のため((Ｘ＋Num−１)＞１１)が非成立となり、末尾の非ゼロデータ列が１１列より前と判定する（Ｓ４０−ＮＯ）。
【０１３２】
次に、Write Ctrl２４ａは、Nextが４のため、次の非ゼロデータ列が存在すると判定し（Ｓ４１−ＹＥＳ）、Ｘを７（＝３＋４）に更新する（Ｓ４２）。この更新されたＸ（＝７）が、次の非ゼロデータ列の先頭非ゼロブロックのＸ座標を示す。
【０１３３】
次に、Write Ctrl２４ａは、Ｒ[２][６]の非ゼロ管理情報を読み出し（Ｓ４３）、Num＝２、Next＝４とし（Ｓ４４）、Ｓ３９に戻る。
【０１３４】
Write Ctrl２４ａは、Num＝２のため、次の非ゼロデータ列が存在すると判定し（Ｓ３９−ＹＥＳ）、Ｘ＋Num−１＝８のため、((Ｘ＋Num−１)＞１１)が非成立となり、末尾の非ゼロデータ列が１１列より前と判定する（Ｓ４０−ＮＯ）。また、Nextが４のため、Write Ctrl２４ａは、次の非ゼロデータ列が存在すると判定し（Ｓ４１−ＹＥＳ）、Ｘを１１（＝７＋４）に更新する（Ｓ４２）。次に、Write Ctrl２４ａは、Ｒ[２][１０]の非ゼロ管理情報を読み出し（Ｓ４３）、Num＝２、Next＝０とし（Ｓ４４）、Ｓ３９に戻る。
【０１３５】
この場合、Write Ctrl２４ａは、Num＝２のため、次の非ゼロデータ列が存在すると判定し（Ｓ３９−ＹＥＳ）、Ｘ＋Num−１＝１２のため、((Ｘ＋Num−１)＞１１)が成立と判定する（Ｓ４０−ＹＥＳ）。Write Ctrl２４ａは、Ｘ＝１１から始まる非ゼロデータ列を非ゼロデータ列Ａとする。以上の処理により、非ゼロデータ列Ｂの開始位置が３、非ゼロデータ列Ａの開始位置が１１と探索される。
【０１３６】
次に、非ゼロデータ列Ｂの開始位置−１の位置の非ゼロ管理情報の更新について、図１９及び図２０の例１〜例８を用いて説明する。８つの例は、いずれもＲ[２][３]が非ゼロデータ列Ｂの開始位置である。また、書き込み範囲は、n0列からn1列までであり、書き込みデータ内の先頭にある非ゼロデータ列をＣとし、Ｃの開始位置をｑとしている。
【０１３７】
図１９の例１及び図２０の例７では、書き込みはゼロデータから開始しており（Ｒ[２][n0]が０、n0≠ｑ）、ゼロデータの書き込みの結果、非ゼロデータ列の長さが減少する。そのため、非ゼロ管理情報Ｒ[２][２]のNumは２から１になる（n0−Ｂとする）。また、非ゼロ管理情報Ｒ[２][２]のNextは非ゼロデータ列Ｃの開始位置ｑを指すように変更（４→２へ）となる。
【０１３８】
また、図１９の例２では、書き込みはゼロデータから開始している（Ｒ[２][n0]が０、n0≠ｑ）が、ゼロデータの書き込みの結果、非ゼロデータ列の長さは変わらない。そのため、非ゼロ管理情報Ｒ[２][２]のNextのみＣの非ゼロデータ列の開始位置のｑを指すように変更（４→５へ）する。
【０１３９】
また、図１９の例３では、書き込みは非ゼロデータから開始しており（Ｒ[２][n0]が０、n0＝ｑ）、非ゼロ書き込みの結果、非ゼロデータ列の長さが変わる。そのため、非ゼロ管理情報Ｒ[２][２]のNumを２から５に変更する（Ｃの非ゼロデータの数＋ｑ−Ｂの開始位置）。また、非ゼロ管理情報Ｒ[２][２]のNextをＣの更に次の非ゼロデータ列の開始位置を指すように変更（４→６へ）する。
【０１４０】
また、図１９の例４では、書き込みは非ゼロデータから開始している（Ｒ[２][n0]が０、n0＝ｑ）が、非ゼロデータの書き込みの結果、非ゼロデータ列の長さが変わらない。そのため、非ゼロ管理情報Ｒ[２][２]のNextのみＣの非ゼロデータ列の開始位置のｑを指すように変更（４→３へ）する。
【０１４１】
また、図１９の例５では、書き込みは全てゼロデータであり、ゼロデータの書き込みの結果、非ゼロデータ列の長さが減少する。そのため、非ゼロ管理情報Ｒ[２][２]のNumを２から１に減少させる（n0−Ｂの開始位置とする）。さらに、ゼロデータの書き込みの結果、非ゼロデータ列Ａのデータ列の長さが減る。そのため、非ゼロ管理情報Ｒ[２][２]のNextをn1＋１を指すように変更（４→１１へ）する。
【０１４２】
また、図２０の例６では、書き込みは全てゼロデータであるが、ゼロデータの書き込みの結果、非ゼロデータ列の長さは変わらない。そのため、非ゼロ管理情報Ｒ[２][２]のNumを変更しない。さらに、ゼロデータの書き込みの結果、非ゼロデータ列Ａのデータ列の長さは変わらない。そのため、非ゼロ管理情報Ｒ[２][２]のNextを非ゼロデータ列Ａの開始位置を指すように変更（４→８へ）する。
【０１４３】
また、図２０の例８では、書き込みは全てゼロデータであり、ゼロデータの書き込みの結果、非ゼロデータ列の長さが減少する。これにより、非ゼロ管理情報Ｒ[２][２]のNumを２から１に減少させる（n0−Ｂの開始位置とする）。さらに、非ゼロデータ列Ａが存在しないため、非ゼロ管理情報Ｒ[２][２]のNextを０に変更する。
【０１４４】
次に、ライトデータの書き込み処理について、図１９の例１を用いて説明する。このライトデータの書き込みは、書き込みデータに非ゼロデータが含まれる場合に行う。  
まず、図１９の例１では、書き込み非ゼロデータの開始位置（Ｘ＝５）が入力され、非ゼロデータブロックが２つ入力され、Ｘ＝５、６（Ｓ[２][５]、Ｓ[２][６]）に非ゼロデータが書き込まれる。次に、書き込み非ゼロデータの開始位置（Ｘ＝９）が入力される。これにより、Ｘ＝４（Ｒ[２][４]）の位置の非ゼロ管理情報が確定するため、Num＝２、Next＝９−５＝４がＸ＝４（Ｓ[２][４]）の位置に書き込まれる。次に、非ゼロデータブロックが２つ入力され、Ｓ[２][９]、Ｓ[２][１０]に非ゼロデータが書き込まれ、書き込みが終了する。Ｘ＝８の位置の非ゼロ管理情報の更新は、次のＳ２４で行われる。このように、非ゼロデータ列の書き込みと非ゼロ管理情報の書き込みを繰り返し行う。動作途中に非ゼロ管理情報を読み出すことはない。
【０１４５】
図１９の例２〜例４についても同様である。ただし、例３の場合、最初に更新する非ゼロ管理情報は、非ゼロデータ列Ｂの開始位置−１の位置（Ｒ[２][２]）になる。
【０１４６】
ここで、Write Ctrl２４ａが、図１９の例１のデータを書き込む場合の、非ゼロデータ列Ｂの開始位置−１の位置の非ゼロ管理情報の更新、及び、ライトデータの書き込み処理について、図１６及び図１７を用いて説明する。  
まず、Write Ctrl２４ａは、書き込みデータに非ゼロデータが含まれているため（Ｓ５１−ＮＯ）、非ゼロデータ列の開始位置（ｑ＝５）を入力する（Ｓ５２）。次に、ｑ＝５、n0＝４のため、ｑ≠n0となり（Ｓ５３−ＮＯ）、ゼロデータから開始となる。そして、非ゼロデータ列Ｂの開始位置＝３、Ｂ_Num＝２より、（Ｂの開始位置＋Ｂ_Num−１）≧n0が成立し、非ゼロデータ列Ｂの要素がn0〜n1列に含まれる（Ｓ５４−ＹＥＳ）。
【０１４７】
次に、Write Ctrl２４ａは、非ゼロデータ列Ｂの開始位置−１の位置の非ゼロ管理情報Ｒ[２][２]を、Num＝１、Next＝２に更新する（Ｓ５５、Ｓ５６）。
【０１４８】
次に、Write Ctrl２４ａは、非ゼロデータ列の開始位置ｑを非ゼロデータ列W0の開始位置として設定し、Pos＝ｑ＝５、Cnt＝０、Start＝ｑ＝５に設定する（Ｓ５７）。
【０１４９】
次に、Write Ctrl２４ａは、非ゼロデータブロックが入力され（Ｓ６０）、入力された非ゼロデータブロックをＳ[２][５]に書き込む（Ｓ６１）。次に、Write Ctrl２４ａは、Pos及びCntのカウントアップ（Pos＝Pos＋１＝６、Cnt＝Cnt＋１＝１）を行う（Ｓ６２）。非ゼロデータ列W0の書き込みが終了していないため（Ｓ６３−ＮＯ）、Ｓ６０に戻る。
【０１５０】
次に、Write Ctrl２４ａは、非ゼロデータブロックを入力し（Ｓ６０）、入力した非ゼロデータブロックをＳ[２][６]に書き込む（Ｓ６１）。そして、Write Ctrl２４ａは、Pos＝７、Cnt＝２にカウントアップし（Ｓ６２）、非ゼロデータ列W0の書き込みが終了したと判定する（Ｓ６３−ＹＥＳ）。
【０１５１】
次に、次の書き込み非ゼロデータ列W1が存在するため（Ｓ６４−ＹＥＳ）、Write Ctrl２４ａは、次の非ゼロデータ列の開始位置（ｐ＝９）を入力する（Ｓ６５）。
【０１５２】
次に、Write Ctrl２４ａは、Num＝Cnt＝２、Next＝ｐ−Start＝９−５＝４とする（Ｓ６６）。そして、Write Ctrl２４ａは、非ゼロデータ列W1を次の非ゼロデータ列W0に設定し（Ｓ６７）、Ｓ６０に戻る。この場合、Pos＝ｐ＝９、Cnt＝０、Start＝ｐ＝９が設定される。
【０１５３】
次に、Write Ctrl２４ａは、非ゼロデータブロックを入力し（Ｓ６０）、入力した非ゼロデータブロックを Ｓ[２][９]に書き込む（Ｓ６１）。そして、Write Ctrl２４ａは、Pos＝１０、Cnt＝１にカウントアップし（Ｓ６２）、非ゼロデータ列W0の書き込みが終了していないため（Ｓ６３−ＮＯ）、Ｓ６０に戻る。
【０１５４】
次に、Write Ctrl２４ａは、非ゼロデータブロックを入力し（Ｓ６０）、入力した非ゼロデータブロックを Ｓ[２][１０]に書き込む（Ｓ６１）。そして、Write Ctrl２４ａは、Pos＝１１、Cnt＝２にカウントアップする（Ｓ６２）。Write Ctrl２４ａは、非ゼロデータ列W0の書き込みが終了し（Ｓ６３−ＹＥＳ）、次の書き込み非ゼロデータ列W1が存在しないため（Ｓ６４−ＮＯ）、図１６のエンドに返る。
【０１５５】
次に、ライトデータ中の最後の非ゼロ管理情報の更新、及び、n1列の非ゼロ管理情報の更新処理について説明する。図１９及び図２０の例１〜例６は、いずれもＲ[２][１１]が非ゼロデータ列Ａの開始位置となり、例７及び例８は、非ゼロデータ列Ａが存在しない。書き込み範囲は、n0〜n1列までで、書き込みデータ内の非ゼロデータの内で最も大きい位置にあるものの列数をeとする。
【０１５６】
図１９の例１では、e＝１０、書き込みはゼロデータで終了しており（Ｒ[２][n1]＝０、n1≠e）、ゼロデータの書き込みの結果、非ゼロデータ列Ａのデータ列の長さが減少する。そのため、最後の非ゼロ管理情報Ｒ[２][８]を、Numは２（ライトしたデータ列の個数のまま）、Nextはn1＋１−Startを指す（１１＋１−９＝３）ように変更する。また、n1列の非ゼロ管理情報Ｒ[２][１１]を、Numは非ゼロデータ列ＡのNum（２）からゼロ書き込みで減少した分を減少し(２→１へ)、Nextは非ゼロデータ列ＡのNextと同じになるように変更する。
【０１５７】
また、図１９の例２では、e＝９、書き込みはゼロデータで終了しており（Ｒ[２][n1]＝０、n1≠e）、ゼロデータの書き込みの結果、非ゼロデータ列Ａのデータ列の長さが減少しない。そのため、最後の非ゼロ管理情報Ｒ[２][７]を、Numは２(ライトしたデータ列の個数のまま)、Nextは非ゼロデータ列Ａの開始位置−Startを指す（１１−８＝３）ように変更する。
【０１５８】
また、図１９の例３では、e＝１１、書き込みは非ゼロデータで終了しており（Ｒ[２][n1]≠０、n1＝e）、非ゼロデータの書き込みの結果、最後の非ゼロデータ列と非ゼロデータ列Ａとが接続又は重なる。そのため、最後の非ゼロ管理情報Ｒ[２][８]を、Numは４（ライトしたデータ列の個数（３）＋非ゼロデータ列Ａの内でライト範囲外にあるブロック個数（１））、Nextは非ゼロデータ列ＡのNext（０）を指すように変更する。
【０１５９】
また、図１９の例４では、e＝９、書き込みは非ゼロデータで終了しており（Ｒ[２][n1]≠０、n1＝e）、非ゼロデータの書き込みの結果、非ゼロデータ列Ａのデータ列の長さが変わらない。そのため、最後の非ゼロ管理情報Ｒ[２][８]を、Numは１（ライトしたデータ列の個数のまま）、Nextは、非ゼロデータ列Ａの開始位置−Startを指す（１１−９＝２）ように変更する。もし、Ａが存在しない場合、Nextは０と変更する。
【０１６０】
また、図１９の例５では、非ゼロデータ書き込みは存在しないので、書き込みはゼロデータで終了しており（Ｒ[２][n1]＝０)、ゼロデータの書き込みの結果、非ゼロデータ列Ａのデータ列の長さが減少する。そのため、n1列の非ゼロ管理情報Ｒ[２][１１]を、Numは非ゼロデータ列ＡのNum（２）からゼロデータの書き込みで減った分を減少し（２→１へ）、Nextは非ゼロデータ列ＡのNextと同じに変更する。
【０１６１】
また、図２０の例６では、非ゼロデータ書き込みは存在しないので、書き込みはゼロデータで終了しており（Ｒ[２][n1]＝０)、ゼロデータの書き込みの結果、非ゼロデータ列Ａのデータ列の長さが減少しない。そのため、最後の非ゼロ管理情報、及び、n1列の非ゼロ管理情報を変更しない。
【０１６２】
また、図２０の例７では、e＝１０、n1＝１２、書き込みはゼロデータで終了しており（Ｒ[２][n1]が０、n1≠e）、非ゼロデータ列Ａは存在しない。そのため、Numは２（ライトしたデータ列の個数のまま）、Nextは０と変更する。
【０１６３】
また、図２０の例８では、非ゼロデータ書き込みは存在しないので、書き込みはゼロデータで終了しており(Ｒ[２][n1]＝0)、非ゼロデータ列Ａは存在しない。そのため、最後の非ゼロ管理情報、及び、n1列の非ゼロ管理情報を変更しない。
【０１６４】
次に、Write Ctrl２４ａが、図１９の例１のデータを書き込む場合の、最後の非ゼロ管理情報の更新、及び、n1列の非ゼロ管理情報の更新処理について、図１８を用いて説明する。  
図１６及び図１７の処理により、Pos＝１１、Cnt＝２、Start＝９に設定されているとする。まず、Write Ctrl２４ａは、ライト範囲内全て０の書き込みでなく（Ｓ８１−ＮＯ）、非ゼロデータ列Ａが存在し（Ｓ８２−ＹＥＳ）、Pos＝１１であり、Pos−１≠n1が成立するため、最後の書き込みデータが０であると判定する（Ｓ８３−ＹＥＳ）。
【０１６５】
次に、Write Ctrl２４ａは、非ゼロデータ列Ａの開始位置＝１１より、Ａ≦n1が成立し（Ｓ８４−ＹＥＳ）、最後の非ゼロ管理情報を更新し、Next＝n1＋１−Start＝１１＋１−９＝３、Num＝Cnt＝２に設定する（Ｓ８５）。
【０１６６】
最後に、Write Ctrl２４ａは、n1列の非ゼロ管理情報を更新し（Ｓ８６）、処理を終了する。この場合、Next ＝Ａ_Next＝０、Num＝Ａ_Num−（n1＋１−Ａの開始位置）＝２−（１１＋１−１１）＝１となる。以上の処理により、n1列の非ゼロ管理情報R[２][１１]は、Num＝１、Next＝０に更新される。
【０１６７】
以上のように、行列管理エンジン４は、Ｌ２キャッシュ２５ａ〜２５ｄに非ゼロデータのみを保持し、ゼロデータの領域に連続する非ゼロデータの数、及び、次の非ゼロデータまでの距離を示す非ゼロ管理情報を格納するようにした。そして、行列管理エンジン４は、リード要求が入力された際に非ゼロ管理情報を参照し、非ゼロデータのみを要求元に返すようにした。これにより、非ゼロデータのみを保持することでＬ２キャッシュ２５ａ〜２５ｄの使用量を削減し、非ゼロデータのみを転送することでバンド幅を削減するようにしている。
【０１６８】
よって、本実施の形態の情報処理装置としての行列管理エンジンによれば、キャッシュメモリ上に非ゼロデータのみを保持・管理することで、メモリ使用量及びバンド幅を抑えることができる。
【０１６９】
なお、本明細書におけるフローチャート中の各処理は、その性質に反しない限り、実行順序を変更し、複数同時に実行し、あるいは実行毎に異なった順序で実行してもよい。
【０１７０】
本発明のいくつかの実施の形態を説明したが、これらの実施の形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施の形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施の形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１７１】
１…計算機システム、２…ＣＰＵ、３…ＨＷE、４…行列管理エンジン、５…キャッシュ、６…アドレス変換部、７…インターコネクト、８…メインメモリ、９…Ｉ／Ｏ、２１…Packet Distributer、２２ａ〜２２ｄ…Packet I/F、２３ａ〜２３ｄ…Read Ctrl、２４ａ〜２４ｄ…Write Ctrl、２５ａ〜２５ｄ…Ｌ２キャッシュ、２６ａ〜２６ｄ…Address Translator、４１…Info Checker、４２…Read Requestor、４３…Data Requestor、４４…Data Output、４５…Read Data Receiver、５１…B−Searcher、５２…Read Requestor、５３…A−Searcher、５４…Read Data Receiver、５５…Write Data Receiver、５６…B−Updater、５７…Write Requestor、５８…Data Writer、５９…Last−Info Updater。
【図１】
2015176245.tif 000003
【図２】
2015176245.tif 000004
【図３】
2015176245.tif 000005
【図４】
2015176245.tif 000006
【図５】
2015176245.tif 000007
【図６】
2015176245.tif 000008
【図７】
2015176245.tif 000009
【図８】
2015176245.tif 000010
【図９】
2015176245.tif 000011
【図１０】
2015176245.tif 000012
【図１１】
2015176245.tif 000013
【図１２】
2015176245.tif 000014
【図１３】
2015176245.tif 000015
【図１４】
2015176245.tif 000016
【図１５】
2015176245.tif 000017
【図１６】
2015176245.tif 000018
【図１７】
2015176245.tif 000019
【図１８】
2015176245.tif 000020
【図１９】
2015176245.tif 000021
【図２０】
2015176245.tif 000022