ＲＡＩＤ装置及びガロア体の積演算処理方法
【課題】ガロア体を用いてパリテイデータを生成する際に、高速にガロア体の積演算を実行する。
【解決手段】ｎ台のデータストレージユニット（１０−１〜１０−１６）の内、 (ｎ−１)／２より大きな最小の整数をｓとして、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行する。
【解決手段】ｎ台のデータストレージユニット（１０−１〜１０−１６）の内、 (ｎ−１)／２より大きな最小の整数をｓとして、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体演算により、データのパリテイを計算するＲＡＩＤ装置及びガロア体の積演算方法に関し、特に、ディスク群の２重故障を復元するのに好適なＲＡＩＤ装置及びガロア体の積演算方法に関する。
【背景技術】
【０００２】
ディスクの２重故障を復元できる方法として、ＲＡＩＤ（Redundant Array of Independent Disks）６が知られている。このＲＡＩＤ６の方式として、１次元冗長方式が提案されている（例えば、特許文献１参照）。
【０００３】
図１４のＲＡＩＤ６の構成で説明すると、ＲＡＩＤコントローラ１１０に、３台のデータディスク装置（ハードディスクドライブ）１０１，１０２，１０３と、２台のパリテイディスク装置（ハードディスクドライブ）１０４，１０５が、接続される。
【０００４】
１次元冗長方式は、データから２種類のパリテイを生成する。図１５に示すように、１つ目のパリティＰは、従来のＲＡＩＤ５と同じく、各データＤ１，Ｄ２，Ｄ３の足し算（ＸＯＲ）を行った結果を、パリティとする。そして、このパリテイＰは、第１のディスク装置１０４に保存する。尚、以下、「＋」の記号は、ＸＯＲ（排他的論理和）を示す。
【０００５】
２つ目のパリティＱは、各データＤ１，Ｄ２，Ｄ３に対し、ガロア体の積演算による重み付け行った後、それらを足し合わせた結果（ＸＯＲ）をパリティとする。そして、このパリテイＱは、第２のディスク装置１０５に保存される。
【０００６】
このガロア体は、各データディスク装置１０１，１０２，１０３に対して、１つ決定され、２重故障の復元のためには、各データディスク装置１０１，１０２，１０３で、異なっている必要がある。例えば、図１５に示すように、データビット数を１６ビットとすると、ガロア体ＧＦ（２＾１６）は、２の１６乗個の有限個の点を取りうる。又、ガロア体の四則演算が、所定の法則で可能である。１次元冗長方式は、パリテイの分散が可能となり、２重故障の検出、復元に有効である。
【０００７】
図１５に示したように、ガロア体を利用したパリテイ生成においては、ガロア体の積演算として、データとガロア体の２つの変数を用いて、演算を行う必要がある。このため、ＲＡＩＤ５のＸＯＲ演算（パリテイＰの演算）に対し、パリテイ生成に処理時間を要し、性能が劣化する。
【０００８】
このガロア体の積演算を簡略化するため、複数のデータをシフトやＡＮＤ，ＸＯＲを使用し、α倍の重み付け（積演算）のアルゴリズムが提案されている（例えば、非特許文献１参照）。この提案された論文では、その４頁から５頁に、データが８ビットの場合のパリテイ生成、データ復元の方程式を解説し、６頁の下欄から７頁に、α倍のアルゴリズムをＣ言語で開示している。
【０００９】
このＣ言語で記述されたアルゴリズムを、図１６及び図１７を用いて、各々８ビットの４シンボルのデータを対象として、説明する。図１６の「ｖ」は、８ビット、４シンボル（３２ビット）の対象データを示す。
【００１０】
先ず、ディスク装置の８ビットのデータを、４つ、３２ビットのレジスタにロードする（Ｓ１００）。この対象データｖ（３２ビット）全体を、１ビット左（上位方向）にシフトする（Ｓ１０１）。１ビット左にシフトされたデータｖ＜＜１は、３２ビット単位で、対象データｖの２倍の値となる。
【００１１】
次に、シフトされたデータｖ＜＜１において、このデータｖのシフトにより、他のシンボルへ影響したビットをマスクする。このため、マスク値「０ｘｆｅｆｅｆｅｆｅ」を用意し、シフトされたデータｖ＜＜１と、マスク値とのアンド（ＡＮＤ）演算を行い、マスクされたデータｖｖを得る（Ｓ１０２）。この操作により、８ビット間隔の右端（シフトにより影響されたビット）の値が、「０」に設定される。即ち、３２ビット全体をシフトしているので、対象シンボルの右隣のシンボルの最上位ビットにより、対象シンボルの右端ビットが影響されることを防止する。
【００１２】
次に、対象データｖからマスク（ｖ）関数を、図１７のように作成する（Ｓ１０３）。マスク（ｖ）関数は、図１７に示すように、３２ビットの対象データｖの８ビット間隔の左端が、「１」である場合には、８ビットの「１１１１１１１１」を、左端が、「０」である場合には、８ビットの「００００００００」を表す。即ち、シフトにより、桁上げされたシンボルには、８ビットのオール「１」を、桁上げされないシンボルには、８ビットのオール「０」を施すマスク（ｖ）関数を作成する。
【００１３】
このため、マスク値「０ｘ８０８０８０８０」と、即ち、８ビット間隔で、「１」が現れ、その他は、「０」の値と、対象データｖとの論理積（ＡＮＤ）をとる（Ｓ１１０）。このマスク値は、各シンボルの先頭ビットを抽出する。
【００１４】
次に、論理積値を、左に１ビットシフトした３２ビットデータｖ＜＜１（２倍データ）を演算し、且つ論理積値を、右に７ビットシフトした３２ビットデータｖ＞＞７（１／１２８倍データ）を演算し，左に１ビットシフトした３２ビットデータｖ＜＜１（２倍データ）から右に７ビットシフトした３２ビットデータｖ＞＞７を差し引き、マスク（ｖ）関数ＭＡＳＫ（ｖ）を得る（Ｓ１１２）。この関数は、先頭ビットが、「１」のシンボルと、それ以外を区別する役目を持つ。
【００１５】
図１６に戻り、８ビットのガロア体ＧＦ（２の８乗）の生成多項式（＝ｘ＾８＋ｘ＾２＋１）に対応する係数値「０ｘ１ｄ１ｄ１ｄ１ｄ」と、マスク（ｖ）関数ＭＡＳＫ（ｖ）との論理積（ＡＮＤ）を演算する（Ｓ１０４）。即ち、４シンボルの内、先頭ビットが、「１」のシンボルのみに、係数値「０ｘ１ｄ１ｄ１ｄ１ｄ」の「０００１１１０１」に置き換える。
【００１６】
この論理積結果と、ステップＳ１０２で、演算したマスクされた対象データｖｖとのＸＯＲを演算することにより、α倍された対象データα・ｖを得る（Ｓ１０５）。このα倍された対象データα・ｖに、これらのステップを再度繰り返すと、対象データｖのαの二乗倍のデータが得られる。同様にして、対象データｖのαの繰り返し倍のデータを演算できる。
【００１７】
このように、従来技術では、ステップＳ１００で、代入、シフト、ステップＳ１０１で、ＡＮＤ，ステップＳ１０３（図１７）で、ＡＮＤ，２回シフト、減算、ステップＳ１０４で、ＡＮＤ，ステップＳ１０５で、ＸＯＲの９回の操作で、数シンボル（ここでは、４シンボル）のガロア体積演算の並列処理を実現できる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】日本国特開２０００−２５９３５９号公報（図５、図６）
【非特許文献】
【００１９】
【非特許文献１】論文「The mathematics of ＲＡＩＤ−６」（著者 Ｈ．Ｐｅｔｅｒ Ａｎｖｉｎ、online paper, http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf、２００６年１０月２６日アクセス）
【発明の概要】
【発明が解決しようとする課題】
【００２０】
この従来のガロア体の積演算処理では、複数シンボル（上の例では、４シンボル）の並列処理を実現できるが、α倍するには、９ステップの演算が必要となる。従って、αのｎ乗倍を演算するには、９・ｎステップの演算回数が必要となる。
【００２１】
特に、近年の記憶容量の増大に伴い、対象データのシンボル数（データディスク装置の数）も増大する傾向にあり、例えば、２台のパリテイディスク装置に対し、１４台のデータディスク装置を設けてＲＡＩＤ６を構成する場合には、αの１３乗倍を演算する必要があり、９・１３＝１１７ステップの演算が必要となり、更なるステップ数の削減が望まれる。
【００２２】
又、繰り返しにより、演算する場合には、その繰り返し数又は反復回数（積演算アルゴリズムのループ回数）が少ないことが、高速化のため、望まれる。
【００２３】
更に、生成処理のみならず、復元処理においても、ガロア体の積演算処理に、反復回数が少ないことが、処理時間短縮の点で、望まれる。
【００２４】
従って、本発明の目的は、ガロア体積演算の処理時間を短縮するためのＲＡＩＤ装置及びガロア体の積演算処理方法を提供することにある。
【００２５】
又、本発明の他の目的は、ガロア体積演算の並列処理のステップ数を低減するためのＲＡＩＤ装置及びガロア体の積演算処理方法を提供することにある。
【００２６】
更に、本発明の他の目的は、ガロア体積演算の並列処理の繰り返し数を低減するためのＲＡＩＤ装置及びガロア体の積演算処理方法を提供することにある。
【課題を解決するための手段】
【００２７】
この目的の達成のため、本発明のＲＡＩＤ装置は、データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットと、前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、前記データをｎ分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、前記積演算を実行する。
【００２８】
更に、本発明のガロア体の積演算処理方法は、データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するステップと、前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有する。
【００２９】
更に、本発明では、好ましくは、前記制御ユニットは、前記ｎ分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのＸＯＲ演算を行い、α倍の積演算結果を演算する。
【００３０】
更に、本発明では、好ましくは、前記制御ユニットは、前記積演算を、ｍ回繰り返し、α＾ｍ倍の積演算結果を演算する。
【００３１】
更に、本発明では、好ましくは、前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第１のパリテイデータ及び第２のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元する。
【発明の効果】
【００３２】
ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するので、少ない繰り返し回数で、各データのガロア体の積演算が可能となる。
【図面の簡単な説明】
【００３３】
【図１】本発明の一実施形態のＲＡＩＤ装置の構成図である。
【図２】本発明の一実施形態のパリテイ生成方法の説明図である。
【図３】図１のパリテイＱのガロア体積演算処理フロー図である。
【図４】図２の詳細処理フロー図である、
【図５】図４の積演算処理の具体例の説明図である、
【図６】図５のマスク作成処理の説明図である。
【図７】本発明の他の実施の形態のガロア体積演算処理の説明図である。
【図８】図７の積演算処理の説明図である。
【図９】図７のパリテイＱのガロア体積演算処理フロー図である。
【図１０】図９の操作処理フロー図である、
【図１１】図９の詳細処理フロー図である、
【図１２】本発明の更に別の実施の形態のガロア体積演算処理フロー図である。
【図１３】図１２の積演算処理の説明図である。
【図１４】従来のＲＡＩＤ６の構成図である。
【図１５】従来のＲＡＩＤ６のパリテイデータの説明図である。
【図１６】従来のガロア体の積演算の説明図である、
【図１７】従来のマスク作成処理の説明図である、
【発明を実施するための形態】
【００３４】
以下、本発明の実施の形態を、ＲＡＩＤ装置、ガロア体積演算処理、他のガロア体積演算処理、更に他のガロア体積演算処理、他の実施の形態の順で説明するが、本発明は、この実施の形態に限られない。
【００３５】
（ＲＡＩＤ装置）
図１は、本発明の一実施の形態のＲＡＩＤ装置の構成図、図２は、そのガロア体を用いたパリテイ演算の説明図である。図１に示すように、ＲＡＩＤ装置は、ホストコンピュータ１６に接続されたＲＡＩＤコントローラ１２と、ＲＡＩＤコントローラ１２にＦＣ（Ｆｉｂｒｅ Ｃｈａｎｎｅｌ）ループ１４等により接続され、且つ制御される複数（ここでは、１４台）のデータディスク装置（ハードディスクドライブ）１０−１〜１０−１４と、２台のパリテイディスク装置（ハードディスクドライブ）１０−１５，１０−１６とからなる。即ち、２重パリテイを持つＲＡＩＤ６の構成である。
【００３６】
図２に示すように、第１のパリテイＰは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４のＸＯＲで生成され、第１のパリテイディスク装置１０−１５の対応アドレスに格納される。第２のパリテイＱは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４を、ガロア体の積演算による重み付け後に、ＸＯＲして生成され、第２のパリテイディスク装置１０−１６の対応アドレスに格納される。即ち、パリテイＱは、下記式（１）で演算される。
【００３７】
【数１】
【００３８】
尚、記号「＋」は、ＸＯＲ演算を示す。これらのパリテイ演算は、ＲＡＩＤコントローラ１２が、実行する。ここで、１シンボルを１６ビットとすると、ガロア体は、ＧＦ（２の１６乗）であり、その原始多項式（生成多項式）は、下記式（２）で表される。
【００３９】
【数２】
【００４０】
又、この実施例で、ガロア体積演算に使用されるマスク値は、「３２７６８」であり、１６ビットのデータの最上位ビットのみが、「１」のデータである。又、値「４１０７」は、式（２）の原始多項式のｘの１６乗を除き、ｘに「２」を代入して得た値である。
【００４１】
ＲＡＩＤコントローラ１２は、データをディスク装置１０−１〜１０−４にライト処理する際に、ＸＯＲ演算により、パリテイＰを計算し、第１のパリテイディスク装置１０−１５に格納し、以下で説明するガロア体の積演算処理とＸＯＲ演算を行い、パリテイＱを計算し、第２のパリテイディスク装置１０−１６に格納する。
【００４２】
（ガロア体積演算）
図３は、本発明の一実施の形態のガロア体積演算処理フロー図、図４は、図３の詳細処理フロー図、図５は、図３及び図４の具体例の説明図、図６は、桁上がりシンボルの積演算の説明図である。
【００４３】
図３以下では、１シンボルを１６ビットとして、８シンボルを並列処理する例で説明する。例えば、インテル社（登録商標）のＣＰＵでは、ＭＭＸ命令セットが備わっている。ＭＭＸ命令セットは、ｘｍｍレジスタを使用する。このｘｍｍレジスタを用いて、並列処理を行う。ｘｍｍレジスタ長は、１６Ｂｙｔｅであり、1度に、１シンボルが１６ビットの時、８シンボルのデータの重み付けの並列処理が行える。
【００４４】
図３により、ガロア体積演算の基本的処理を説明する。
【００４５】
（Ｓ１０）先ず、ｘｍｍ１レジスタに、８シンボルをロードする。
【００４６】
（Ｓ１２）次に、ｘｍｍ１レジスタの各シンボルを、左に１ビットシフトし、各シンボルの値を２倍とする。
【００４７】
（Ｓ１４）マスク値を用いて、シフトにより値が小さくなるシンボル（即ち、最上位ビットの桁上がりが生じるシンボル）を検出する。
【００４８】
（Ｓ１６）シフトしたシンボルの内、値が小さくなったシンボルに、予め定めた値（「４１０７」）をＸＯＲする。
【００４９】
次に、図４により、ＭＭＸを用いた重み付け処理を詳細に説明する。又、図５、図６を用いて、データディスク番号ｉ＝２のガロア体の重み付け（ガロア体の積演算）処理を例に、具体的に説明を行う。データディスク番号ｉ＝２の場合には、式（１）のパリテイＱの生成多項式から、データＤｉ＝２に、α倍の重みづけを行う。
【００５０】
（Ｓ２０）ｘｍｍレジスタに、データを代入し、処理すべき繰り返し回数ＭＡＸを設定する。例えば、ディスク番号ｉ＝２の場合には、ＭＡＸ＝１である。又、繰り返し回数ポインタｉを「０」に初期化する。更に、ＭＡＸ＝０の場合には、ｘｍｍレジスタの内容を出力し、以下のステップを実行しないこととする。例えば、図５に示すように、データディスク番号ｉ＝２のディスクから、重み付けを行う８シンボル（１シンボル、１６ビット）のデータ（Ｄｉ＝２データ）をピックアップし、これをｘｍｍ１レジスタに代入する（図５のｘｍｍ１）。
【００５１】
又、「３２７６８」と「４１０７」の値が入力された８シンボルのデータｖ３２７６８，ｖ４１０７を用意する。値「３２７６８」は、１６ビット目のみに「１」の値があることを示し、シフトにより桁上げが生じるシンボルを検出するためのデータである。値「４１０７」は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（x^16+x^12+x^3+x+1）の（x^12+x^3+x+1）に、ｘ＝２を代入した値である。即ち、４０９６＋８＋２＋１＝４１０７である。
【００５２】
（Ｓ２２）次に、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタに代入された値を、ｘｍｍ２レジスタに移動する。シフト命令（ＰＳＬＬＷ）に応じて、ｘｍｍ２レジスタの各シンボルを、左に（上位方向に）１ビットシフトする（図５のｘｍｍ２）。これにより、各シンボルは、２倍（＝α倍）されるが、１シンボルが、１６ビットのため、桁上げされたビット部分は、オーバーフローする。このため、図５のｘｍｍ２に示すように、値が２倍になる箇所（一重下線）と、シフト前よりも値が小さくなる箇所（二重下線）がある。シフト前よりも値が小さくなる箇所は、オーバーフローした箇所である。
【００５３】
（Ｓ２４）この値が小さくなる箇所（シンボル）のみに、値「４１０７」のＸＯＲを行う。このため、先ず、値が小さくなったシンボルを抽出し、その抽出したシンボルの値を、オール「１」（即ち、６５５３５）とする。図６も参照して、説明する。ＡＮＤ命令（ＰＡＮＤ）に応じて、図５のｘｍｍ１レジスタの各シンボルの値と、ｖ３２７６８の値「３２７６８」との論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。図４及び図５の（ｘｍｍ１＆ｖ３２７６８）に示すように、８シンボルの内、オーバーフローしたシンボル（値が小さくなったシンボル）のみが、値「３２７６８」に置き換えられ、オーバーフローしないシンボルは、値「０」に置き換えられる。
【００５４】
次に、８シンボルの値判定を行い、シンボルの値を、値「６５５３５」又は値「０」に置き換える。即ち、比較及び最大値設定命令（ＰＣＭＰＥＱＷ）に応じて、（ｘｍｍ１＆ｖ３２７６８）の各シンボルの値と、値「３２７６８」を比較して、両者が一致すると、そのシンボルの１６ビットを、オール「１」（＝６５５３５）に置き換え、両者が一致しないと、そのシンボルの１６ビットを、オール「０」（＝０）に置き換える。これにより、値「４１０７」のマスクを作成する。
【００５５】
（Ｓ２６）そして、ＡＮＤ命令（ＰＡＮＤ）に応じて、このｘｍｍ１レジスタの各シンボルの値と、ｖ４１０７の値「４１０７」の論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。これにより、８シンボルのｘｍｍ１レジスタの内、値が小さくなったシンボルのみが、値「４１０７」に置き換えられ、値が小さくならないシンボルは、値「０」に置き換えられる。
【００５６】
（Ｓ２８）ＸＯＲ命令（ＰＸＯＲ）に応じて、この更新されたｘｍｍ１レジスタの各シンボルの値と、ステップＳ２２で得たｘｍｍ２レジスタの各シンボルの値とのＸＯＲ（排他的論理輪）をとり、α倍の重みづけを行った結果を得る。
【００５７】
（Ｓ３０）「ｂｒｅａｋ」が、検出された時に、処理を停止し、ｘｍｍ１の値を確定する。それ以外は、ステップＳ２４に戻る。
【００５８】
（Ｓ３２）α倍計算処理開始にあたり、繰り返し回数ポインタｉを、「１」インクリメントする。そして、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上であるかを判定する。繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上でなければ、ステップＳ２４に進む。
【００５９】
（Ｓ３４）一方、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上である場合には、設定した繰り返し回数が終了したので、「ｂｒｅａｋ」を通知し、ｘｍｍ１を結果として、出力する。
【００６０】
例えば、図５において、第２番目のシンボルの値「３６９３４」を単純に２倍すると、「７３８６８」となるが、１シンボルが１６ビットに制限されるため、オーバーフローが生じ、そのシンボルの値は、１ビットオーバーフローしているため、１６ビット表示で、８３３２（＝７３８６８−６５５３６）となる。しかし、第２番目のシンボルの２倍値の有意ビットは、１７ビットから２ビット目の１６ビットである。この有意ビットを補正するため、補正値「４１０７」を使用し、値「１２４２３」に変換する。
【００６１】
ステップＳ２２〜Ｓ２８の処理は、どれもレイテンシが小さい（レイテンシ＝２）命令で実現でき、処理時間を短くすることができる。α^j倍の重みづけでは、ステップＳ２２〜Ｓ２８の処理をｊ回繰り返す。
【００６２】
ここで、この実施の形態のマスク処理を、図６で説明する。図６は、シフトにより値が小さくなったシンボルを抽出するマスク処理を示し、先ず、ｘｍｍ１レジスタの値と、ｖ３２７６８のアンドで、オーバーフローシンボルと、オーバーフローしないシンボルを識別する。次に、これらのシンボルと、値「３２７６８」を比較し、両者が一致するシンボルを、オール「１」（＝６５５３５）に置き換え、マスクを作成する。そして、値ｖ４１０７とのアンドをとり、求めるｘｍｍ１を得る。
【００６３】
一方、図１７に示すように、従来技術では、元のシンボルｖに、値「０ｘ８０８０８０８０」をアンドし、オーバーフローシンボルと、オーバーフローしないシンボルを識別する。次に、この結果から、マスクを作成するため、この結果を、左１ビットシフトしたものを作成し、且つ右に７ビットシフトしたものを作成し、これらのシフト結果を引き算する。
【００６４】
即ち、本実施の形態では、図６のマスク処理は、マスク作成に、ＡＮＤと、比較命令の２命令で行っているのに対し、従来は、ＡＮＤ，シフト２回、引き算命令の４命令で実行している。
【００６５】
更に、本実施の形態では、図５に示すように、左シフトは、シンボル単位に、独立で行っているのに対し、従来技術では、図１６に示すように、レジスタ全体、即ち、４シンボル単位で行っている。このため、従来技術では、シフト後、シンボルの右端が、右隣のシンボルの最上位ビットに影響されないように、シンボルの右端を、強制的に、「０」に置き換える処理が余分に必要である。
【００６６】
従って、従来は、９命令で実行していたものを、本実施の形態では、６命令で実行できる。即ち、α倍するのに、２／３の処理時間で済み、高速に、ガロア体の積演算を実行できる。例えば、αの１３乗の積演算では、従来は、９×１３＝１１７命令（ステップ）必要としたのに対し、本実施の形態は、６×１３＝７８命令（ステップ）で済む。更に、式（１）の積演算では、従来は、９×（１＋２＋３＋４＋５＋６＋７＋８＋９＋１０＋１１＋１２＋１３＝９１）＝８１９命令の実行を要するが、本実施の形態では、６×（１＋２＋３＋４＋５＋６＋７＋８＋９＋１０＋１１＋１２＋１３＝９１）＝５４６命令の実行で済み、高速に、ガロア体積演算を実行できる。
【００６７】
更に、本実施の形態では、８シンボルを並列処理できるため、従来の４シンボルの並列処理に比し、更に２倍の高速処理が可能となり、結果として、１／３の処理時間で、ガロア体積演算を実現できる。
【００６８】
（他のガロア体積演算処理）
図７は、本発明のガロア体積演算処理の他の実施の形態の処理フロー図、図８は、図７の重み付け処理の説明図、図９は、図７のα−１倍の積演算処理フロー図、図１０は、そのオペレーションの説明図、図１１は、図９の詳細処理フロー図である。
【００６９】
前述の実施の形態は、ガロア体の積演算処理の１回の処理時間を短縮するものであったが、この実施の形態は、積演算処理の並列処理アルゴリズムのループ回数が少なくなるように、ガロア体の元を決定し、ガロア体の積演算処理時間を短縮するものである。
【００７０】
図７に示すように、図１乃至図２と同様に、データディスク装置を１４台で構成した例とすると、データディスク番号 ｉ (＝１〜１４)に対し、ｉ＝１〜８の場合は、αｉ−１倍による重み付けを行い、図４乃至図６の重み付け演算処理を行い、ｉ＝９〜１４の場合は、α−ｉ＋８倍による重み付けを行い、図８以下で説明するα−１倍の重みづけアルゴリズムを使用する。
【００７１】
この重み付けの割り振りを一般化すると、データディスク装置をｎ台で構成した例とすると、(ｎ−１)／２より大きな最小の整数をｓとする時に、データディスク番号ｉ＝１〜ｓ＋１の場合は、α＾（ｉ−１）倍による重み付けを行い、図４乃至図６の重み付け演算処理を行い、ｉ＝ｓ＋２〜ｎの場合は、α−ｉ＋ｓ＋１倍による重み付けを行う。
【００７２】
α倍の重みづけ処理は、図４乃至図６で説明したので、ここでは、説明を省略し、α−１倍の重み付け処理を、図８乃至図１１で説明する。
【００７３】
図８に示すように、第１のパリテイＰは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４のＸＯＲで生成され、第１のパリテイディスク装置１０−１５の対応アドレスに格納される。第２のパリテイＱは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４を、ガロア体の積演算による重み付け後に、ＸＯＲして生成され、第２のパリテイディスク装置１０−１６の対応アドレスに格納される。即ち、パリテイＱは、下記式（３）で演算される。
【００７４】
【数３】
【００７５】
尚、記号「＋」は、ＸＯＲ演算を示す。これらのパリテイ演算は、ＲＡＩＤコントローラ１２が、実行する。ここで、１シンボルを１６ビットとすると、ガロア体は、ＧＦ（２の１６乗）であり、その原始多項式（生成多項式）は、前記式（２）で表される。
【００７６】
又、この実施例で、α−１倍のガロア体積演算に使用されるマスク値は、「１」であり、１６ビットのデータの最下位ビットのみが、「１」のデータである。又、値「３４８２１」は、式（２）の原始多項式をｘで割り、割った式のｘに「２」を代入して得た値である。
【００７７】
ＲＡＩＤコントローラ１２は、データをディスク装置１０−１〜１０−１４にライト処理する際に、ＸＯＲ演算により、パリテイＰを計算し、第１のパリテイディスク装置１０−１５に格納し、以下で説明するガロア体の積演算処理とＸＯＲ演算を行い、パリテイＱを計算し、第２のパリテイディスク装置１０−１６に格納する。
【００７８】
図９以下でも、１シンボルを１６ビットとして、８シンボルを並列処理する例で説明する。例えば、インテル社（登録商標）のＣＰＵでは、ＭＭＸ命令セットが備わっている。ＭＭＸ命令セットは、ｘｍｍレジスタを使用する。このｘｍｍレジスタを用いて、並列処理を行う。ｘｍｍレジスタ長は、１６Ｂｙｔｅであり、1度に、１シンボルが１６ビットの時は、８シンボルのデータの重み付けの並列処理が行える。
【００７９】
図９により、α−１倍のガロア体積演算の基本的処理を説明する。
【００８０】
（Ｓ４０）先ず、ｘｍｍ１レジスタに、８シンボルをロードする。
【００８１】
（Ｓ４２）次に、ｘｍｍ１レジスタの各シンボルを、右方向（最下位ビット方向）に１ビットシフトし、各シンボルの値を１／２倍とする。
【００８２】
（Ｓ４４）マスク値を用いて、シフトにより値の桁落ちが生じるシンボル（即ち、対象シンボルの最下位ビット「１」が、消失するシンボル）を検出する。
【００８３】
（Ｓ４６）シフトしたシンボルの内、桁落ちしたシンボルに、予め定めた値（「３４８２１」）をＸＯＲする。
【００８４】
次に、図１１により、ＭＭＸを用いた重み付け処理を詳細に説明する。又、図１０を用いて、データディスク番号ｉ＝９のα−１倍のガロア体の重み付け（ガロア体の積演算）処理を例に、具体的に説明を行う。データディスク番号ｉ＝９の場合には、式（３）のパリテイＱの生成多項式から、データＤｉ＝９に、α−１倍の重みづけを行う。
【００８５】
（Ｓ５０）ｘｍｍレジスタに、データを代入し、処理すべき繰り返し回数ＭＡＸを設定する。例えば、ディスク番号ｉ＝９場合には、ＭＡＸ＝１である。又、繰り返し回数ポインタｉを「０」に初期化する。例えば、図５と同様に、データディスク番号ｉ＝９のディスクから、重み付けを行う８シンボル（１シンボル、１６ビット）のデータ（Ｄｉ＝９データ）をピックアップし、これをｘｍｍ１レジスタに代入する（図１０の（１））。
【００８６】
又、「１」と「３４８２１」の値が入力された８シンボルのデータｖ１，ｖ３４８２１を用意する。値「１」は、最下位である１ビット目のみに「１」の値があることを示し、左シフトにより桁落ちが生じるシンボルを検出するためのデータである。
【００８７】
値「３４２８１」は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（x^16+x^12+x^3+x+1）から「１」を除き、且つこの結果をｘで割った多項式（x^15+x^11+x^2+1）に、ｘ＝２を代入した値である。この意味は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（α^16+α^12+α^3+α+1）＝０の原則により、（α^16+α^12+α^3+α）＝１が成立する。このαに「２」を代入すると、６９６４２＝１が得られる。両辺を右（最下位）方向に１ビットシフトすると、３４８２１＝値が消失、となる。１６ビットデータの右辺に、「１」が有る場合に、右シフトすると、右辺の「１」が消失するため、「３４８２１」をＸＯＲすることにより、値を補正するものである。
【００８８】
（Ｓ５２）次に、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタに代入された値を、ｘｍｍ２レジスタに移動する。シフト命令（ＰＳＲＬＷ）に応じて、ｘｍｍ２レジスタの各シンボルを、右に（下位方向に）１ビットシフトする（図１０の（２）のｘｍｍ２）。これにより、各シンボルは、１／２倍（＝α−１倍）されるが、１シンボルが、１６ビットのため、桁落ちされたビット部分は、アンダーフローする。このため、図５と同様に、値がそのまま２倍になる箇所と、桁落ちする箇所（アンダーフローした箇所）とが混在する。
【００８９】
（Ｓ５４）この桁落ちした箇所（シンボル）のみに、値「３４８２１」のＸＯＲを行う。このため、先ず、桁落ちしたシンボルを抽出し、その抽出したシンボルの値を、オール「１」（即ち、６５５３５）とする。即ち、ＡＮＤ命令（ＰＡＮＤ）に応じて、図１０のｘｍｍ１レジスタの各シンボルの値と、ｖ１の値「１」との論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。（ｘｍｍ１＆ｖ１）は、８シンボルの内、最下位桁が「１」であるシンボルのみが、値「１」に置き換えられ、それ以外は、値「０」に置き換えられる。
【００９０】
次に、８シンボルの値判定を行い、シンボルの値を、値「６５５３５」又は値「０」に置き換える。即ち、比較及び最大値設定命令（ＰＣＭＰＥＱＷ）に応じて、（ｘｍｍ１＆ｖ１）の各シンボルの値と、値「１」を比較して、両者が一致すると、そのシンボルの１６ビットを、オール「１」（＝６５５３５）に置き換え、両者が一致しないと、そのシンボルの１６ビットを、オール「０」（＝０）に置き換える。これにより、値「３４８２１」のマスクを作成する。
【００９１】
（Ｓ５６）そして、ＡＮＤ命令（ＰＡＮＤ）に応じて、このｘｍｍ１レジスタの各シンボルの値と、ｖ３４８２１の値「３４８２１」の論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。これにより、８シンボルのｘｍｍ１レジスタの内、最下位桁が「１」のシンボルのみが、値「３４８２１」に置き換えられ、それ以外のシンボルは、値「０」に置き換えられる。
【００９２】
（Ｓ５８）ＸＯＲ命令（ＰＸＯＲ）に応じて、この更新されたｘｍｍ１レジスタの各シンボルの値と、ステップＳ５２で得たｘｍｍ２レジスタの各シンボルの値とのＸＯＲ（排他的論理輪）をとり、α−１倍の重みづけを行った結果を得る。
【００９３】
（Ｓ６０）「ｂｒｅａｋ」が、検出された時に、処理を停止し、ｘｍｍ１の値を確定する。それ以外は、ステップＳ５４に戻る。
【００９４】
（Ｓ６２）α＾−１倍計算処理開始にあたり、繰り返し回数ポインタｉを、「１」インクリメントする。そして、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上であるかを判定する。繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上でなければ、ステップＳ５４に進む。
【００９５】
（Ｓ６４）一方、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上である場合には、設定した繰り返し回数が終了したので、「ｂｒｅａｋ」を通知し、ｘｍｍ１を結果として、出力する。
【００９６】
このように、このα−１倍の重み付けアルゴリズムの特徴は、ｘｍｍレジスタに代入された値を、右１ビットシフトする点であり、基本的な考え方はα倍の重みづけアルゴリズムと同じである。出力は、ディスク番号ｉ＝９〜１４に対し、α^-(i-8)倍の重みづけ結果が出力される。
【００９７】
このように、ガロア体の元は、各ディスクで異なれば良く、必ずしも、式（１）のように、ディスク番号ｉに比例する乗数を持つガロア体の元を使用しなくても良い。これを利用して、α倍と、α−１倍の重み付け処理を用い、且つ繰り返し数が最小となるディスク番号ｉで、使用するガロア体を、αｉ−１倍と、α−ｉ＋８倍の重みを割り振る。これにより、図７及び図８では、ループ回数が、最大７回となる。
【００９８】
もし、図４の方法のみで行うと、ループ回数は、最大１３回となり、この実施の形態による、ループ回数の削減の効果は、大きい。
【００９９】
又、この実施の形態では、α倍と、α−１倍の重み付け処理を、図４の例で説明したが、他の１回の繰り返しでα倍、ｎ回の繰り返しで、αｎ倍の積演算ができる他の方法も適用できる。
【０１００】
勿論、図４の実施の形態の積演算処理を使用すれば、本実施の形態でも、６命令で実行でき、α倍するのに、２／３の処理時間で済み、高速に、ガロア体の積演算を実行できる。同様に、８シンボルを並列処理できるため、従来の４シンボルの並列処理に比し、更に２倍の高速処理が可能となり、結果として、１／３の処理時間で、ガロア体積演算を実現できる。
【０１０１】
（更に別のガロア体積演算処理）
図１２は、本発明のガロア体積演算処理の更に別の実施の形態の処理フロー図、図１３は、図１２の処理の説明図である。この実施の形態は、図４乃至図６の実施の形態のα倍演算処理を使用した任意のガロア体の元α^k倍の重みづけ処理を示し、最大反復回数が１５回で済むというメリットがある。この積演算処理は、特に、ｋ倍のｋが大きい時に、有効であり、ディスクの２重故障を復元させる際に使用することが好適である。
【０１０２】
図１３に示すように、例えば、１６ビットのガロア体ＧＦ（２＾１６）の最大のガロア体の元α^33653倍（αの３３６５３乗）の重みづけを行う際に、図４のα倍の重みづけアルゴリズムを用いた場合では、反復回数が３３６５３回、図７のα^(-1)倍の重みづけアルゴリズムを用いた場合では、反復回数が３１８８２回必要となり、効率的とは言えない。
【０１０３】
そこで、このようなケースでは、任意のガロア体重みづけアルゴリズムを使用する。このアルゴリズムは、ガロア体のベクトル表現を使用するところに特徴がある。任意のガロア体の元は、下記（４）式の関係がある。
【０１０４】
【数４】
【０１０５】
但し、ｇｆｗ（ｉ）は、「０」又は「１」のいずれかである。即ち、任意のガロア体を、２進数のベクトル表現(gfw(0), gfw(1),・・・, gfw(15))で表すことができる。
【０１０６】
又、1シンボルＤのα^k倍の重み付けは、下記（５）式のように、分配法則が成立する。
【０１０７】
【数５】
【０１０８】
図１２及び図１３の重み付け処理は、この分配法則を用いて重み付けを行う。例えば、α^33653倍の重みづけを行う場合には、ガロア体の法則から、下記（６）式の関係がある。
【０１０９】
【数６】
【０１１０】
従って、前述のベクトル表現では、( gfw(0), gfw(1),・・・, gfw(15) ) = ( 1, 0, 1, 0, ・・・, 0 )となる。
【０１１１】
また、反復回数は、gfw(i)=1となる最大のiを設定値として使用するため、反復回数ＭＡＸ＝２と設定する。この理由は、α^3・D, α^4・D, ・・・ の重み付けを、必要としないため、反復回数ＭＡＸを「２」に指定することで、余分な反復回数を減らすことが可能となり、処理時間を短縮する効果がある。
【０１１２】
図１３は、８シンボルデータ（Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５，Ｄ６，Ｄ７，Ｄ８）のα^33653倍の重みづけの例を示す。ＭＡＸ＝２回反復を繰り返すとき、α^0=1倍, α^1倍, α^2倍の重みづけデータが作成される。このうち、gfw(i)＝１となるi回目のα^i倍重み付けデータを足し算（ＸＯＲ）する。この例の場合には、０回目と２回目の重み付けデータを足し算（ＸＯＲ）する。
【０１１３】
これにより、目的の重み付けデータα＾33653・Ｄｊ（ｊ＝１，２，・・、８）を、（α＾０・Ｄｊ＋α＾２・Ｄｊ）により、得ることができる。
【０１１４】
図１２により処理を説明する。
【０１１５】
（Ｓ７０）ｘｍｍ１レジスタに、データを代入し、処理すべき繰り返し回数ＭＡＸを設定する。ｘｍｍ２レジスタを、ｖ０（オール「０」）に初期化する。又、繰り返し回数ポインタｉを「０」に初期化する。更に、ＭＡＸ＝０の場合には、ｘｍｍレジスタ１の内容を出力し、以下のステップを実行しないこととする。そして、ベクトルｇｆｗを設定する。
【０１１６】
又、図４と同様に、「３２７６８」と「４１０７」の値が入力された８シンボルのデータｖ３２７６８，ｖ４１０７を用意する。値「３２７６８」は、１６ビット目のみに「１」の値があることを示し、シフトにより桁上げが生じるシンボルを検出するためのデータである。値「４１０７」は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（x^16+x^12+x^3+x+1）の（x^12+x^3+x+1）に、ｘ＝２を代入した値である。即ち、４０９６＋８＋２＋１＝４１０７である。
【０１１７】
（Ｓ７２）次に、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタに代入された値を、ｘｍｍ３レジスタに移動する。シフト命令（ＰＳＬＬＷ）に応じて、ｘｍｍ３レジスタの各シンボルを、左に（上位方向に）１ビットシフトする。これにより、各シンボルは、２倍（＝α倍）されるが、１シンボルが、１６ビットのため、桁上げされたビット部分は、オーバーフローする。このため、値が２倍になる箇所と、シフト前よりも値が小さくなる箇所がある。シフト前よりも値が小さくなる箇所は、オーバーフローした箇所である。
【０１１８】
（Ｓ７４）この値が小さくなる箇所（シンボル）のみに、値「４１０７」のＸＯＲを行う。このため、先ず、値が小さくなったシンボルを抽出し、その抽出したシンボルの値を、オール「１」（即ち、６５５３５）とする。即ち、ＡＮＤ命令（ＰＡＮＤ）に応じて、ｘｍｍ１レジスタの各シンボルの値と、ｖ３２７６８の値「３２７６８」との論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。８シンボルの内、オーバーフローしたシンボル（値が小さくなったシンボル）のみが、値「３２７６８」に置き換えられ、オーバーフローしないシンボルは、値「０」に置き換えられる。
【０１１９】
次に、８シンボルの値判定を行い、シンボルの値を、値「６５５３５」又は値「０」に置き換える。即ち、比較及び最大値設定命令（ＰＣＭＰＥＱＷ）に応じて、（ｘｍｍ１＆ｖ３２７６８）の各シンボルの値と、値「３２７６８」を比較して、両者が一致すると、そのシンボルの１６ビットを、オール「１」（＝６５５３５）に置き換え、両者が一致しないと、そのシンボルの１６ビットを、オール「０」（＝０）に置き換える。これにより、値「４１０７」のマスクを作成する。
【０１２０】
（Ｓ７６）そして、ＡＮＤ命令（ＰＡＮＤ）に応じて、このｘｍｍ１レジスタの各シンボルの値と、ｖ４１０７の値「４１０７」の論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。これにより、８シンボルのｘｍｍ１レジスタの内、値が小さくなったシンボルのみが、値「４１０７」に置き換えられ、値が小さくならないシンボルは、値「０」に置き換えられる。
【０１２１】
（Ｓ７８）ＸＯＲ命令（ＰＸＯＲ）に応じて、この更新されたｘｍｍ１レジスタの各シンボルの値と、ステップＳ７２で得たｘｍｍ３レジスタの各シンボルの値とのＸＯＲ（排他的論理輪）をとり、α倍の重みづけを行った結果を得る。
【０１２２】
（Ｓ８０）「ｂｒｅａｋ」が、検出された時に、処理を停止し、ｘｍｍ１の値を確定する。それ以外は、ステップＳ７４に戻る。
【０１２３】
（Ｓ８２）ＸＯＲ計算部では、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタの処理結果を、ｘｍｍ４レジスタに移動する。
【０１２４】
（Ｓ８４）その処理時のｇｆｗ（ｉ）が、「１」であるかを判定する。
【０１２５】
（Ｓ８６）ｇｆｗ（ｉ）が、「１」である場合には、前述のように、ＸＯＲの対象であるため、ｘｍｍ２レジスタの内容とｘｍｍ４レジスタの内容とのＸＯＲを演算し、演算結果で、ｘｍｍ２レジスタを更新する。
【０１２６】
（Ｓ８８）繰り返し回数ポインタｉを、「１」インクリメントする。
【０１２７】
（Ｓ９０）そして、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上であるかを判定する。繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上でなければ、ステップＳ７４に進む。
【０１２８】
（Ｓ９２）一方、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上である場合には、設定した繰り返し回数が終了したので、「ｂｒｅａｋ」を、α倍計算部のループに通知し、ｘｍｍ２を結果として、出力する。
【０１２９】
このように、α^k倍の重みづけ処理の最大反復回数を減少でき、ｋが大きい時に、有効であり、ディスクの２重故障を復元させる際に使用すると、高速に復元できる。
【０１３０】
（他の実施の形態）
前述の実施の形態では、１４台のデータディスク装置と２台のパリテイディスク装置とで構成されるＲＡＩＤ６のストレージ装置で、説明したが、他の台数の構成にも適用できる。
【０１３１】
又、パリテイＱの生成は、図４の実施の形態又は図１１の他の実施の形態のガロア体積演算処理を使用し、パリテイＰ、Ｑを使用した２重故障の復元には、図１２の更に別の実施の形態のガロア体積演算処理を使用することが、パリテイ生成と復元の両方を高速に実行できる。しかし、パリテイＱの生成は、図４の実施の形態又は図１１の他の実施の形態のガロア体積演算処理を使用し、パリテイＰ，Ｑによる二重故障の復元も、図４の実施の形態又は図１１の他の実施の形態のガロア体積演算処理を使用することもできる。又、パリテイＱの生成及びパリテイＰ，Ｑによる二重故障の復元とも、図４の実施の形態を含む図１２の更に別の実施の形態のガロア体積演算処理を使用することもできる。
【０１３２】
以上、本発明を、実施の形態で説明したが、本発明は、その趣旨の範囲内で種々の変形が可能であり、これを本発明の範囲から排除するものではない。
【０１３３】
（付記１）データを分割し、分割されたデータを各々格納する複数のデータストレージユニットと、前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成法定式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、前記データを分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記分割されたデータの各々をレジスタにロードし、且つレジスタの各データを上位桁方向にビットシフトし、前記ロードされたデータと前記シフトにより桁上がりビットを検出するための固定値との論理積をとり、且つ前記論理積の結果と前記固定値とを比較して、前記桁上がりビットを有するデータを、前記データの最大値に置き換え、マスクを作成し、前記マスクの最大値と前記桁上がりを補正する補正値との論理積を演算し、前記演算結果と前記シフトされたデータとの排他的論理和（ＸＯＲ）を演算して、前記データを前記ガロア体の元で積演算した結果を得ることを特徴とするＲＡＩＤ装置。
【０１３４】
（付記２）前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第１のパリテイデータ及び第２のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元することを特徴とする付記１のＲＡＩＤ装置。
【０１３５】
（付記３）前記制御ユニットは、最上位ビットのみが「１」である前記データのビット数と同一のビット数を有する前記固定値を使用することを特徴とする付記１のＲＡＩＤ装置。
【０１３６】
（付記４）前記制御ユニットは、複数のデータを前記レジスタにロードし、前記複数のデータに対し、前記積演算処理を並列に実行することを特徴とする付記１のＲＡＩＤ装置。
【０１３７】
（付記５）前記制御ユニットは、前記ガロア体の原始多項式から得た前記補正値を使用することを特徴とする付記１のＲＡＩＤ装置。
【０１３８】
（付記６）前記制御ユニットは、前記ガロア体の元の次数分、前記積演算を繰り返すことを特徴とする付記１のＲＡＩＤ装置。
【０１３９】
（付記７）前記制御ユニットは、前記ガロア体の元を、ベクトル表現し、且つ分配法則を用いて、重み付け値を分配して、前記ガロア体の元の積演算を実行することを特徴とする付記１のＲＡＩＤ装置。
【０１４０】
（付記８）前記制御ユニットは、前記分配した第１の重み付け値の積演算を第１の重み付け値の回数分実行した後、前記実行結果を用いて、前記積演算を第２の重み付け値の回数分実行し、前記第１の重み付け値の積演算結果と、前記第２の重み付け値の積演算結果の排他的論理和をとり、前記ガロア体の元の積演算結果を得ることを特徴とする付記７のＲＡＩＤ装置。
【０１４１】
（付記９）データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットと、前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、前記データをｎ分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、前記積演算を実行することを特徴とするＲＡＩＤ装置。
【０１４２】
（付記１０）前記制御ユニットは、前記ｎ分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのＸＯＲ演算を行い、α倍の積演算結果を演算することを特徴とする付記９のＲＡＩＤ装置。
【０１４３】
（付記１１）前記制御ユニットは、前記積演算を、ｍ回繰り返し、α＾ｍ倍の積演算結果を演算することを特徴とする付記１０のＲＡＩＤ装置。
【０１４４】
（付記１２）前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第１のパリテイデータ及び第２のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元することを特徴とする付記９のＲＡＩＤ装置。
【０１４５】
（付記１３）分散されたデータの各々をレジスタにロードするステップと、前記レジスタの各データを上位桁方向にビットシフトするステップと、前記ロードされたデータと前記シフトにより桁上がりビットを検出するための固定値との論理積をとるステップと、前記論理積の結果と前記固定値とを比較して、前記桁上がりビットを有するデータを、前記データの最大値に置き換え、マスクを作成するステップと、前記マスクの最大値と前記桁上がりを補正する補正値との論理積を演算するステップと、前記演算結果と前記シフトされたデータとの排他的論理和（ＸＯＲ）を演算して、前記データを前記ガロア体の元で積演算した結果を得るステップとからなることを特徴とするガロア体積演算処理方法。
【０１４６】
（付記１４）前記固定値との論理積ステップは、最上位ビットのみが「１」である前記データのビット数と同一のビット数を有する前記固定値を使用するステップからなることを特徴とする付記１３のガロア体積演算処理方法。
【０１４７】
（付記１５）前記ロードステップは、複数のデータを前記レジスタにロードするステップからなり、前記複数のデータに対し、前記シフトステップ、論理積ステップ、作成ステップ、論理積ステップ、排他的論理和ステップを並列に実行することを特徴とする付記１３のガロア体積演算処理方法。
【０１４８】
（付記１６）前記補正値との論理積ステップは、前記ガロア体の原始多項式から得た前記補正値を使用するステップからなることを特徴とする付記１３のガロア体積演算処理方法。
【０１４９】
（付記１７）前記ガロア体の元の次数分、前記積演算を繰り返すステップを、更に、有することを特徴とする付記１３のガロア体積演算処理方法。
【０１５０】
（付記１８）前記ガロア体の元を、ベクトル表現し、且つ分配法則を用いて、重み付け値を分配して、前記ガロア体の元の積演算を実行するステップを、更に、有することを特徴とする付記１３のガロア体積演算処理方法。
【０１５１】
（付記１９）前記実行ステップは、前記分配した第１の重み付け値の積演算を第１の重み付け値の回数分実行するステップと、前記実行結果を用いて、前記積演算を第２の重み付け値の回数分実行するステップと、前記第１の重み付け値の積演算結果と、前記第２の重み付け値の積演算結果の排他的論理和をとり、前記ガロア体の元の積演算結果を得るステップとからなることを特徴とする付記１８のガロア体積演算処理方法。
【０１５２】
（付記２０）データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するステップと、前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有することを特徴とするガロア体積演算処理方法。
【０１５３】
（付記２１）前記積演算ステップは、前記ｎ分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのＸＯＲ演算を行い、α倍の積演算結果を演算するステップからなることを特徴とする付記２０のガロア体積演算処理方法。
【０１５４】
（付記２２）前記積演算を、ｍ回繰り返し、α＾ｍ倍の積演算結果を演算するステップを、更に有することを特徴とする付記２１のガロア体積演算処理方法。
【産業上の利用可能性】
【０１５５】
ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するので、少ない繰り返し回数で、各データのガロア体の積演算が可能となる。
【符号の説明】
【０１５６】
１０−１〜１０−１４ データディスク装置
１０−１５〜１０−１６ パリテイディスク装置
１２ ＲＡＩＤコントローラ
１４ 接続バス
１６ ホスト
【技術分野】
【０００１】
本発明は、ガロア体演算により、データのパリテイを計算するＲＡＩＤ装置及びガロア体の積演算方法に関し、特に、ディスク群の２重故障を復元するのに好適なＲＡＩＤ装置及びガロア体の積演算方法に関する。
【背景技術】
【０００２】
ディスクの２重故障を復元できる方法として、ＲＡＩＤ（Redundant Array of Independent Disks）６が知られている。このＲＡＩＤ６の方式として、１次元冗長方式が提案されている（例えば、特許文献１参照）。
【０００３】
図１４のＲＡＩＤ６の構成で説明すると、ＲＡＩＤコントローラ１１０に、３台のデータディスク装置（ハードディスクドライブ）１０１，１０２，１０３と、２台のパリテイディスク装置（ハードディスクドライブ）１０４，１０５が、接続される。
【０００４】
１次元冗長方式は、データから２種類のパリテイを生成する。図１５に示すように、１つ目のパリティＰは、従来のＲＡＩＤ５と同じく、各データＤ１，Ｄ２，Ｄ３の足し算（ＸＯＲ）を行った結果を、パリティとする。そして、このパリテイＰは、第１のディスク装置１０４に保存する。尚、以下、「＋」の記号は、ＸＯＲ（排他的論理和）を示す。
【０００５】
２つ目のパリティＱは、各データＤ１，Ｄ２，Ｄ３に対し、ガロア体の積演算による重み付け行った後、それらを足し合わせた結果（ＸＯＲ）をパリティとする。そして、このパリテイＱは、第２のディスク装置１０５に保存される。
【０００６】
このガロア体は、各データディスク装置１０１，１０２，１０３に対して、１つ決定され、２重故障の復元のためには、各データディスク装置１０１，１０２，１０３で、異なっている必要がある。例えば、図１５に示すように、データビット数を１６ビットとすると、ガロア体ＧＦ（２＾１６）は、２の１６乗個の有限個の点を取りうる。又、ガロア体の四則演算が、所定の法則で可能である。１次元冗長方式は、パリテイの分散が可能となり、２重故障の検出、復元に有効である。
【０００７】
図１５に示したように、ガロア体を利用したパリテイ生成においては、ガロア体の積演算として、データとガロア体の２つの変数を用いて、演算を行う必要がある。このため、ＲＡＩＤ５のＸＯＲ演算（パリテイＰの演算）に対し、パリテイ生成に処理時間を要し、性能が劣化する。
【０００８】
このガロア体の積演算を簡略化するため、複数のデータをシフトやＡＮＤ，ＸＯＲを使用し、α倍の重み付け（積演算）のアルゴリズムが提案されている（例えば、非特許文献１参照）。この提案された論文では、その４頁から５頁に、データが８ビットの場合のパリテイ生成、データ復元の方程式を解説し、６頁の下欄から７頁に、α倍のアルゴリズムをＣ言語で開示している。
【０００９】
このＣ言語で記述されたアルゴリズムを、図１６及び図１７を用いて、各々８ビットの４シンボルのデータを対象として、説明する。図１６の「ｖ」は、８ビット、４シンボル（３２ビット）の対象データを示す。
【００１０】
先ず、ディスク装置の８ビットのデータを、４つ、３２ビットのレジスタにロードする（Ｓ１００）。この対象データｖ（３２ビット）全体を、１ビット左（上位方向）にシフトする（Ｓ１０１）。１ビット左にシフトされたデータｖ＜＜１は、３２ビット単位で、対象データｖの２倍の値となる。
【００１１】
次に、シフトされたデータｖ＜＜１において、このデータｖのシフトにより、他のシンボルへ影響したビットをマスクする。このため、マスク値「０ｘｆｅｆｅｆｅｆｅ」を用意し、シフトされたデータｖ＜＜１と、マスク値とのアンド（ＡＮＤ）演算を行い、マスクされたデータｖｖを得る（Ｓ１０２）。この操作により、８ビット間隔の右端（シフトにより影響されたビット）の値が、「０」に設定される。即ち、３２ビット全体をシフトしているので、対象シンボルの右隣のシンボルの最上位ビットにより、対象シンボルの右端ビットが影響されることを防止する。
【００１２】
次に、対象データｖからマスク（ｖ）関数を、図１７のように作成する（Ｓ１０３）。マスク（ｖ）関数は、図１７に示すように、３２ビットの対象データｖの８ビット間隔の左端が、「１」である場合には、８ビットの「１１１１１１１１」を、左端が、「０」である場合には、８ビットの「００００００００」を表す。即ち、シフトにより、桁上げされたシンボルには、８ビットのオール「１」を、桁上げされないシンボルには、８ビットのオール「０」を施すマスク（ｖ）関数を作成する。
【００１３】
このため、マスク値「０ｘ８０８０８０８０」と、即ち、８ビット間隔で、「１」が現れ、その他は、「０」の値と、対象データｖとの論理積（ＡＮＤ）をとる（Ｓ１１０）。このマスク値は、各シンボルの先頭ビットを抽出する。
【００１４】
次に、論理積値を、左に１ビットシフトした３２ビットデータｖ＜＜１（２倍データ）を演算し、且つ論理積値を、右に７ビットシフトした３２ビットデータｖ＞＞７（１／１２８倍データ）を演算し，左に１ビットシフトした３２ビットデータｖ＜＜１（２倍データ）から右に７ビットシフトした３２ビットデータｖ＞＞７を差し引き、マスク（ｖ）関数ＭＡＳＫ（ｖ）を得る（Ｓ１１２）。この関数は、先頭ビットが、「１」のシンボルと、それ以外を区別する役目を持つ。
【００１５】
図１６に戻り、８ビットのガロア体ＧＦ（２の８乗）の生成多項式（＝ｘ＾８＋ｘ＾２＋１）に対応する係数値「０ｘ１ｄ１ｄ１ｄ１ｄ」と、マスク（ｖ）関数ＭＡＳＫ（ｖ）との論理積（ＡＮＤ）を演算する（Ｓ１０４）。即ち、４シンボルの内、先頭ビットが、「１」のシンボルのみに、係数値「０ｘ１ｄ１ｄ１ｄ１ｄ」の「０００１１１０１」に置き換える。
【００１６】
この論理積結果と、ステップＳ１０２で、演算したマスクされた対象データｖｖとのＸＯＲを演算することにより、α倍された対象データα・ｖを得る（Ｓ１０５）。このα倍された対象データα・ｖに、これらのステップを再度繰り返すと、対象データｖのαの二乗倍のデータが得られる。同様にして、対象データｖのαの繰り返し倍のデータを演算できる。
【００１７】
このように、従来技術では、ステップＳ１００で、代入、シフト、ステップＳ１０１で、ＡＮＤ，ステップＳ１０３（図１７）で、ＡＮＤ，２回シフト、減算、ステップＳ１０４で、ＡＮＤ，ステップＳ１０５で、ＸＯＲの９回の操作で、数シンボル（ここでは、４シンボル）のガロア体積演算の並列処理を実現できる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】日本国特開２０００−２５９３５９号公報（図５、図６）
【非特許文献】
【００１９】
【非特許文献１】論文「The mathematics of ＲＡＩＤ−６」（著者 Ｈ．Ｐｅｔｅｒ Ａｎｖｉｎ、online paper, http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf、２００６年１０月２６日アクセス）
【発明の概要】
【発明が解決しようとする課題】
【００２０】
この従来のガロア体の積演算処理では、複数シンボル（上の例では、４シンボル）の並列処理を実現できるが、α倍するには、９ステップの演算が必要となる。従って、αのｎ乗倍を演算するには、９・ｎステップの演算回数が必要となる。
【００２１】
特に、近年の記憶容量の増大に伴い、対象データのシンボル数（データディスク装置の数）も増大する傾向にあり、例えば、２台のパリテイディスク装置に対し、１４台のデータディスク装置を設けてＲＡＩＤ６を構成する場合には、αの１３乗倍を演算する必要があり、９・１３＝１１７ステップの演算が必要となり、更なるステップ数の削減が望まれる。
【００２２】
又、繰り返しにより、演算する場合には、その繰り返し数又は反復回数（積演算アルゴリズムのループ回数）が少ないことが、高速化のため、望まれる。
【００２３】
更に、生成処理のみならず、復元処理においても、ガロア体の積演算処理に、反復回数が少ないことが、処理時間短縮の点で、望まれる。
【００２４】
従って、本発明の目的は、ガロア体積演算の処理時間を短縮するためのＲＡＩＤ装置及びガロア体の積演算処理方法を提供することにある。
【００２５】
又、本発明の他の目的は、ガロア体積演算の並列処理のステップ数を低減するためのＲＡＩＤ装置及びガロア体の積演算処理方法を提供することにある。
【００２６】
更に、本発明の他の目的は、ガロア体積演算の並列処理の繰り返し数を低減するためのＲＡＩＤ装置及びガロア体の積演算処理方法を提供することにある。
【課題を解決するための手段】
【００２７】
この目的の達成のため、本発明のＲＡＩＤ装置は、データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットと、前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、前記データをｎ分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、前記積演算を実行する。
【００２８】
更に、本発明のガロア体の積演算処理方法は、データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するステップと、前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有する。
【００２９】
更に、本発明では、好ましくは、前記制御ユニットは、前記ｎ分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのＸＯＲ演算を行い、α倍の積演算結果を演算する。
【００３０】
更に、本発明では、好ましくは、前記制御ユニットは、前記積演算を、ｍ回繰り返し、α＾ｍ倍の積演算結果を演算する。
【００３１】
更に、本発明では、好ましくは、前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第１のパリテイデータ及び第２のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元する。
【発明の効果】
【００３２】
ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するので、少ない繰り返し回数で、各データのガロア体の積演算が可能となる。
【図面の簡単な説明】
【００３３】
【図１】本発明の一実施形態のＲＡＩＤ装置の構成図である。
【図２】本発明の一実施形態のパリテイ生成方法の説明図である。
【図３】図１のパリテイＱのガロア体積演算処理フロー図である。
【図４】図２の詳細処理フロー図である、
【図５】図４の積演算処理の具体例の説明図である、
【図６】図５のマスク作成処理の説明図である。
【図７】本発明の他の実施の形態のガロア体積演算処理の説明図である。
【図８】図７の積演算処理の説明図である。
【図９】図７のパリテイＱのガロア体積演算処理フロー図である。
【図１０】図９の操作処理フロー図である、
【図１１】図９の詳細処理フロー図である、
【図１２】本発明の更に別の実施の形態のガロア体積演算処理フロー図である。
【図１３】図１２の積演算処理の説明図である。
【図１４】従来のＲＡＩＤ６の構成図である。
【図１５】従来のＲＡＩＤ６のパリテイデータの説明図である。
【図１６】従来のガロア体の積演算の説明図である、
【図１７】従来のマスク作成処理の説明図である、
【発明を実施するための形態】
【００３４】
以下、本発明の実施の形態を、ＲＡＩＤ装置、ガロア体積演算処理、他のガロア体積演算処理、更に他のガロア体積演算処理、他の実施の形態の順で説明するが、本発明は、この実施の形態に限られない。
【００３５】
（ＲＡＩＤ装置）
図１は、本発明の一実施の形態のＲＡＩＤ装置の構成図、図２は、そのガロア体を用いたパリテイ演算の説明図である。図１に示すように、ＲＡＩＤ装置は、ホストコンピュータ１６に接続されたＲＡＩＤコントローラ１２と、ＲＡＩＤコントローラ１２にＦＣ（Ｆｉｂｒｅ Ｃｈａｎｎｅｌ）ループ１４等により接続され、且つ制御される複数（ここでは、１４台）のデータディスク装置（ハードディスクドライブ）１０−１〜１０−１４と、２台のパリテイディスク装置（ハードディスクドライブ）１０−１５，１０−１６とからなる。即ち、２重パリテイを持つＲＡＩＤ６の構成である。
【００３６】
図２に示すように、第１のパリテイＰは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４のＸＯＲで生成され、第１のパリテイディスク装置１０−１５の対応アドレスに格納される。第２のパリテイＱは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４を、ガロア体の積演算による重み付け後に、ＸＯＲして生成され、第２のパリテイディスク装置１０−１６の対応アドレスに格納される。即ち、パリテイＱは、下記式（１）で演算される。
【００３７】
【数１】
【００３８】
尚、記号「＋」は、ＸＯＲ演算を示す。これらのパリテイ演算は、ＲＡＩＤコントローラ１２が、実行する。ここで、１シンボルを１６ビットとすると、ガロア体は、ＧＦ（２の１６乗）であり、その原始多項式（生成多項式）は、下記式（２）で表される。
【００３９】
【数２】
【００４０】
又、この実施例で、ガロア体積演算に使用されるマスク値は、「３２７６８」であり、１６ビットのデータの最上位ビットのみが、「１」のデータである。又、値「４１０７」は、式（２）の原始多項式のｘの１６乗を除き、ｘに「２」を代入して得た値である。
【００４１】
ＲＡＩＤコントローラ１２は、データをディスク装置１０−１〜１０−４にライト処理する際に、ＸＯＲ演算により、パリテイＰを計算し、第１のパリテイディスク装置１０−１５に格納し、以下で説明するガロア体の積演算処理とＸＯＲ演算を行い、パリテイＱを計算し、第２のパリテイディスク装置１０−１６に格納する。
【００４２】
（ガロア体積演算）
図３は、本発明の一実施の形態のガロア体積演算処理フロー図、図４は、図３の詳細処理フロー図、図５は、図３及び図４の具体例の説明図、図６は、桁上がりシンボルの積演算の説明図である。
【００４３】
図３以下では、１シンボルを１６ビットとして、８シンボルを並列処理する例で説明する。例えば、インテル社（登録商標）のＣＰＵでは、ＭＭＸ命令セットが備わっている。ＭＭＸ命令セットは、ｘｍｍレジスタを使用する。このｘｍｍレジスタを用いて、並列処理を行う。ｘｍｍレジスタ長は、１６Ｂｙｔｅであり、1度に、１シンボルが１６ビットの時、８シンボルのデータの重み付けの並列処理が行える。
【００４４】
図３により、ガロア体積演算の基本的処理を説明する。
【００４５】
（Ｓ１０）先ず、ｘｍｍ１レジスタに、８シンボルをロードする。
【００４６】
（Ｓ１２）次に、ｘｍｍ１レジスタの各シンボルを、左に１ビットシフトし、各シンボルの値を２倍とする。
【００４７】
（Ｓ１４）マスク値を用いて、シフトにより値が小さくなるシンボル（即ち、最上位ビットの桁上がりが生じるシンボル）を検出する。
【００４８】
（Ｓ１６）シフトしたシンボルの内、値が小さくなったシンボルに、予め定めた値（「４１０７」）をＸＯＲする。
【００４９】
次に、図４により、ＭＭＸを用いた重み付け処理を詳細に説明する。又、図５、図６を用いて、データディスク番号ｉ＝２のガロア体の重み付け（ガロア体の積演算）処理を例に、具体的に説明を行う。データディスク番号ｉ＝２の場合には、式（１）のパリテイＱの生成多項式から、データＤｉ＝２に、α倍の重みづけを行う。
【００５０】
（Ｓ２０）ｘｍｍレジスタに、データを代入し、処理すべき繰り返し回数ＭＡＸを設定する。例えば、ディスク番号ｉ＝２の場合には、ＭＡＸ＝１である。又、繰り返し回数ポインタｉを「０」に初期化する。更に、ＭＡＸ＝０の場合には、ｘｍｍレジスタの内容を出力し、以下のステップを実行しないこととする。例えば、図５に示すように、データディスク番号ｉ＝２のディスクから、重み付けを行う８シンボル（１シンボル、１６ビット）のデータ（Ｄｉ＝２データ）をピックアップし、これをｘｍｍ１レジスタに代入する（図５のｘｍｍ１）。
【００５１】
又、「３２７６８」と「４１０７」の値が入力された８シンボルのデータｖ３２７６８，ｖ４１０７を用意する。値「３２７６８」は、１６ビット目のみに「１」の値があることを示し、シフトにより桁上げが生じるシンボルを検出するためのデータである。値「４１０７」は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（x^16+x^12+x^3+x+1）の（x^12+x^3+x+1）に、ｘ＝２を代入した値である。即ち、４０９６＋８＋２＋１＝４１０７である。
【００５２】
（Ｓ２２）次に、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタに代入された値を、ｘｍｍ２レジスタに移動する。シフト命令（ＰＳＬＬＷ）に応じて、ｘｍｍ２レジスタの各シンボルを、左に（上位方向に）１ビットシフトする（図５のｘｍｍ２）。これにより、各シンボルは、２倍（＝α倍）されるが、１シンボルが、１６ビットのため、桁上げされたビット部分は、オーバーフローする。このため、図５のｘｍｍ２に示すように、値が２倍になる箇所（一重下線）と、シフト前よりも値が小さくなる箇所（二重下線）がある。シフト前よりも値が小さくなる箇所は、オーバーフローした箇所である。
【００５３】
（Ｓ２４）この値が小さくなる箇所（シンボル）のみに、値「４１０７」のＸＯＲを行う。このため、先ず、値が小さくなったシンボルを抽出し、その抽出したシンボルの値を、オール「１」（即ち、６５５３５）とする。図６も参照して、説明する。ＡＮＤ命令（ＰＡＮＤ）に応じて、図５のｘｍｍ１レジスタの各シンボルの値と、ｖ３２７６８の値「３２７６８」との論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。図４及び図５の（ｘｍｍ１＆ｖ３２７６８）に示すように、８シンボルの内、オーバーフローしたシンボル（値が小さくなったシンボル）のみが、値「３２７６８」に置き換えられ、オーバーフローしないシンボルは、値「０」に置き換えられる。
【００５４】
次に、８シンボルの値判定を行い、シンボルの値を、値「６５５３５」又は値「０」に置き換える。即ち、比較及び最大値設定命令（ＰＣＭＰＥＱＷ）に応じて、（ｘｍｍ１＆ｖ３２７６８）の各シンボルの値と、値「３２７６８」を比較して、両者が一致すると、そのシンボルの１６ビットを、オール「１」（＝６５５３５）に置き換え、両者が一致しないと、そのシンボルの１６ビットを、オール「０」（＝０）に置き換える。これにより、値「４１０７」のマスクを作成する。
【００５５】
（Ｓ２６）そして、ＡＮＤ命令（ＰＡＮＤ）に応じて、このｘｍｍ１レジスタの各シンボルの値と、ｖ４１０７の値「４１０７」の論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。これにより、８シンボルのｘｍｍ１レジスタの内、値が小さくなったシンボルのみが、値「４１０７」に置き換えられ、値が小さくならないシンボルは、値「０」に置き換えられる。
【００５６】
（Ｓ２８）ＸＯＲ命令（ＰＸＯＲ）に応じて、この更新されたｘｍｍ１レジスタの各シンボルの値と、ステップＳ２２で得たｘｍｍ２レジスタの各シンボルの値とのＸＯＲ（排他的論理輪）をとり、α倍の重みづけを行った結果を得る。
【００５７】
（Ｓ３０）「ｂｒｅａｋ」が、検出された時に、処理を停止し、ｘｍｍ１の値を確定する。それ以外は、ステップＳ２４に戻る。
【００５８】
（Ｓ３２）α倍計算処理開始にあたり、繰り返し回数ポインタｉを、「１」インクリメントする。そして、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上であるかを判定する。繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上でなければ、ステップＳ２４に進む。
【００５９】
（Ｓ３４）一方、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上である場合には、設定した繰り返し回数が終了したので、「ｂｒｅａｋ」を通知し、ｘｍｍ１を結果として、出力する。
【００６０】
例えば、図５において、第２番目のシンボルの値「３６９３４」を単純に２倍すると、「７３８６８」となるが、１シンボルが１６ビットに制限されるため、オーバーフローが生じ、そのシンボルの値は、１ビットオーバーフローしているため、１６ビット表示で、８３３２（＝７３８６８−６５５３６）となる。しかし、第２番目のシンボルの２倍値の有意ビットは、１７ビットから２ビット目の１６ビットである。この有意ビットを補正するため、補正値「４１０７」を使用し、値「１２４２３」に変換する。
【００６１】
ステップＳ２２〜Ｓ２８の処理は、どれもレイテンシが小さい（レイテンシ＝２）命令で実現でき、処理時間を短くすることができる。α^j倍の重みづけでは、ステップＳ２２〜Ｓ２８の処理をｊ回繰り返す。
【００６２】
ここで、この実施の形態のマスク処理を、図６で説明する。図６は、シフトにより値が小さくなったシンボルを抽出するマスク処理を示し、先ず、ｘｍｍ１レジスタの値と、ｖ３２７６８のアンドで、オーバーフローシンボルと、オーバーフローしないシンボルを識別する。次に、これらのシンボルと、値「３２７６８」を比較し、両者が一致するシンボルを、オール「１」（＝６５５３５）に置き換え、マスクを作成する。そして、値ｖ４１０７とのアンドをとり、求めるｘｍｍ１を得る。
【００６３】
一方、図１７に示すように、従来技術では、元のシンボルｖに、値「０ｘ８０８０８０８０」をアンドし、オーバーフローシンボルと、オーバーフローしないシンボルを識別する。次に、この結果から、マスクを作成するため、この結果を、左１ビットシフトしたものを作成し、且つ右に７ビットシフトしたものを作成し、これらのシフト結果を引き算する。
【００６４】
即ち、本実施の形態では、図６のマスク処理は、マスク作成に、ＡＮＤと、比較命令の２命令で行っているのに対し、従来は、ＡＮＤ，シフト２回、引き算命令の４命令で実行している。
【００６５】
更に、本実施の形態では、図５に示すように、左シフトは、シンボル単位に、独立で行っているのに対し、従来技術では、図１６に示すように、レジスタ全体、即ち、４シンボル単位で行っている。このため、従来技術では、シフト後、シンボルの右端が、右隣のシンボルの最上位ビットに影響されないように、シンボルの右端を、強制的に、「０」に置き換える処理が余分に必要である。
【００６６】
従って、従来は、９命令で実行していたものを、本実施の形態では、６命令で実行できる。即ち、α倍するのに、２／３の処理時間で済み、高速に、ガロア体の積演算を実行できる。例えば、αの１３乗の積演算では、従来は、９×１３＝１１７命令（ステップ）必要としたのに対し、本実施の形態は、６×１３＝７８命令（ステップ）で済む。更に、式（１）の積演算では、従来は、９×（１＋２＋３＋４＋５＋６＋７＋８＋９＋１０＋１１＋１２＋１３＝９１）＝８１９命令の実行を要するが、本実施の形態では、６×（１＋２＋３＋４＋５＋６＋７＋８＋９＋１０＋１１＋１２＋１３＝９１）＝５４６命令の実行で済み、高速に、ガロア体積演算を実行できる。
【００６７】
更に、本実施の形態では、８シンボルを並列処理できるため、従来の４シンボルの並列処理に比し、更に２倍の高速処理が可能となり、結果として、１／３の処理時間で、ガロア体積演算を実現できる。
【００６８】
（他のガロア体積演算処理）
図７は、本発明のガロア体積演算処理の他の実施の形態の処理フロー図、図８は、図７の重み付け処理の説明図、図９は、図７のα−１倍の積演算処理フロー図、図１０は、そのオペレーションの説明図、図１１は、図９の詳細処理フロー図である。
【００６９】
前述の実施の形態は、ガロア体の積演算処理の１回の処理時間を短縮するものであったが、この実施の形態は、積演算処理の並列処理アルゴリズムのループ回数が少なくなるように、ガロア体の元を決定し、ガロア体の積演算処理時間を短縮するものである。
【００７０】
図７に示すように、図１乃至図２と同様に、データディスク装置を１４台で構成した例とすると、データディスク番号 ｉ (＝１〜１４)に対し、ｉ＝１〜８の場合は、αｉ−１倍による重み付けを行い、図４乃至図６の重み付け演算処理を行い、ｉ＝９〜１４の場合は、α−ｉ＋８倍による重み付けを行い、図８以下で説明するα−１倍の重みづけアルゴリズムを使用する。
【００７１】
この重み付けの割り振りを一般化すると、データディスク装置をｎ台で構成した例とすると、(ｎ−１)／２より大きな最小の整数をｓとする時に、データディスク番号ｉ＝１〜ｓ＋１の場合は、α＾（ｉ−１）倍による重み付けを行い、図４乃至図６の重み付け演算処理を行い、ｉ＝ｓ＋２〜ｎの場合は、α−ｉ＋ｓ＋１倍による重み付けを行う。
【００７２】
α倍の重みづけ処理は、図４乃至図６で説明したので、ここでは、説明を省略し、α−１倍の重み付け処理を、図８乃至図１１で説明する。
【００７３】
図８に示すように、第１のパリテイＰは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４のＸＯＲで生成され、第１のパリテイディスク装置１０−１５の対応アドレスに格納される。第２のパリテイＱは、データディスク装置１０−１〜１０−１４の列方向のデータＤ１〜Ｄ１４を、ガロア体の積演算による重み付け後に、ＸＯＲして生成され、第２のパリテイディスク装置１０−１６の対応アドレスに格納される。即ち、パリテイＱは、下記式（３）で演算される。
【００７４】
【数３】
【００７５】
尚、記号「＋」は、ＸＯＲ演算を示す。これらのパリテイ演算は、ＲＡＩＤコントローラ１２が、実行する。ここで、１シンボルを１６ビットとすると、ガロア体は、ＧＦ（２の１６乗）であり、その原始多項式（生成多項式）は、前記式（２）で表される。
【００７６】
又、この実施例で、α−１倍のガロア体積演算に使用されるマスク値は、「１」であり、１６ビットのデータの最下位ビットのみが、「１」のデータである。又、値「３４８２１」は、式（２）の原始多項式をｘで割り、割った式のｘに「２」を代入して得た値である。
【００７７】
ＲＡＩＤコントローラ１２は、データをディスク装置１０−１〜１０−１４にライト処理する際に、ＸＯＲ演算により、パリテイＰを計算し、第１のパリテイディスク装置１０−１５に格納し、以下で説明するガロア体の積演算処理とＸＯＲ演算を行い、パリテイＱを計算し、第２のパリテイディスク装置１０−１６に格納する。
【００７８】
図９以下でも、１シンボルを１６ビットとして、８シンボルを並列処理する例で説明する。例えば、インテル社（登録商標）のＣＰＵでは、ＭＭＸ命令セットが備わっている。ＭＭＸ命令セットは、ｘｍｍレジスタを使用する。このｘｍｍレジスタを用いて、並列処理を行う。ｘｍｍレジスタ長は、１６Ｂｙｔｅであり、1度に、１シンボルが１６ビットの時は、８シンボルのデータの重み付けの並列処理が行える。
【００７９】
図９により、α−１倍のガロア体積演算の基本的処理を説明する。
【００８０】
（Ｓ４０）先ず、ｘｍｍ１レジスタに、８シンボルをロードする。
【００８１】
（Ｓ４２）次に、ｘｍｍ１レジスタの各シンボルを、右方向（最下位ビット方向）に１ビットシフトし、各シンボルの値を１／２倍とする。
【００８２】
（Ｓ４４）マスク値を用いて、シフトにより値の桁落ちが生じるシンボル（即ち、対象シンボルの最下位ビット「１」が、消失するシンボル）を検出する。
【００８３】
（Ｓ４６）シフトしたシンボルの内、桁落ちしたシンボルに、予め定めた値（「３４８２１」）をＸＯＲする。
【００８４】
次に、図１１により、ＭＭＸを用いた重み付け処理を詳細に説明する。又、図１０を用いて、データディスク番号ｉ＝９のα−１倍のガロア体の重み付け（ガロア体の積演算）処理を例に、具体的に説明を行う。データディスク番号ｉ＝９の場合には、式（３）のパリテイＱの生成多項式から、データＤｉ＝９に、α−１倍の重みづけを行う。
【００８５】
（Ｓ５０）ｘｍｍレジスタに、データを代入し、処理すべき繰り返し回数ＭＡＸを設定する。例えば、ディスク番号ｉ＝９場合には、ＭＡＸ＝１である。又、繰り返し回数ポインタｉを「０」に初期化する。例えば、図５と同様に、データディスク番号ｉ＝９のディスクから、重み付けを行う８シンボル（１シンボル、１６ビット）のデータ（Ｄｉ＝９データ）をピックアップし、これをｘｍｍ１レジスタに代入する（図１０の（１））。
【００８６】
又、「１」と「３４８２１」の値が入力された８シンボルのデータｖ１，ｖ３４８２１を用意する。値「１」は、最下位である１ビット目のみに「１」の値があることを示し、左シフトにより桁落ちが生じるシンボルを検出するためのデータである。
【００８７】
値「３４２８１」は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（x^16+x^12+x^3+x+1）から「１」を除き、且つこの結果をｘで割った多項式（x^15+x^11+x^2+1）に、ｘ＝２を代入した値である。この意味は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（α^16+α^12+α^3+α+1）＝０の原則により、（α^16+α^12+α^3+α）＝１が成立する。このαに「２」を代入すると、６９６４２＝１が得られる。両辺を右（最下位）方向に１ビットシフトすると、３４８２１＝値が消失、となる。１６ビットデータの右辺に、「１」が有る場合に、右シフトすると、右辺の「１」が消失するため、「３４８２１」をＸＯＲすることにより、値を補正するものである。
【００８８】
（Ｓ５２）次に、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタに代入された値を、ｘｍｍ２レジスタに移動する。シフト命令（ＰＳＲＬＷ）に応じて、ｘｍｍ２レジスタの各シンボルを、右に（下位方向に）１ビットシフトする（図１０の（２）のｘｍｍ２）。これにより、各シンボルは、１／２倍（＝α−１倍）されるが、１シンボルが、１６ビットのため、桁落ちされたビット部分は、アンダーフローする。このため、図５と同様に、値がそのまま２倍になる箇所と、桁落ちする箇所（アンダーフローした箇所）とが混在する。
【００８９】
（Ｓ５４）この桁落ちした箇所（シンボル）のみに、値「３４８２１」のＸＯＲを行う。このため、先ず、桁落ちしたシンボルを抽出し、その抽出したシンボルの値を、オール「１」（即ち、６５５３５）とする。即ち、ＡＮＤ命令（ＰＡＮＤ）に応じて、図１０のｘｍｍ１レジスタの各シンボルの値と、ｖ１の値「１」との論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。（ｘｍｍ１＆ｖ１）は、８シンボルの内、最下位桁が「１」であるシンボルのみが、値「１」に置き換えられ、それ以外は、値「０」に置き換えられる。
【００９０】
次に、８シンボルの値判定を行い、シンボルの値を、値「６５５３５」又は値「０」に置き換える。即ち、比較及び最大値設定命令（ＰＣＭＰＥＱＷ）に応じて、（ｘｍｍ１＆ｖ１）の各シンボルの値と、値「１」を比較して、両者が一致すると、そのシンボルの１６ビットを、オール「１」（＝６５５３５）に置き換え、両者が一致しないと、そのシンボルの１６ビットを、オール「０」（＝０）に置き換える。これにより、値「３４８２１」のマスクを作成する。
【００９１】
（Ｓ５６）そして、ＡＮＤ命令（ＰＡＮＤ）に応じて、このｘｍｍ１レジスタの各シンボルの値と、ｖ３４８２１の値「３４８２１」の論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。これにより、８シンボルのｘｍｍ１レジスタの内、最下位桁が「１」のシンボルのみが、値「３４８２１」に置き換えられ、それ以外のシンボルは、値「０」に置き換えられる。
【００９２】
（Ｓ５８）ＸＯＲ命令（ＰＸＯＲ）に応じて、この更新されたｘｍｍ１レジスタの各シンボルの値と、ステップＳ５２で得たｘｍｍ２レジスタの各シンボルの値とのＸＯＲ（排他的論理輪）をとり、α−１倍の重みづけを行った結果を得る。
【００９３】
（Ｓ６０）「ｂｒｅａｋ」が、検出された時に、処理を停止し、ｘｍｍ１の値を確定する。それ以外は、ステップＳ５４に戻る。
【００９４】
（Ｓ６２）α＾−１倍計算処理開始にあたり、繰り返し回数ポインタｉを、「１」インクリメントする。そして、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上であるかを判定する。繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上でなければ、ステップＳ５４に進む。
【００９５】
（Ｓ６４）一方、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上である場合には、設定した繰り返し回数が終了したので、「ｂｒｅａｋ」を通知し、ｘｍｍ１を結果として、出力する。
【００９６】
このように、このα−１倍の重み付けアルゴリズムの特徴は、ｘｍｍレジスタに代入された値を、右１ビットシフトする点であり、基本的な考え方はα倍の重みづけアルゴリズムと同じである。出力は、ディスク番号ｉ＝９〜１４に対し、α^-(i-8)倍の重みづけ結果が出力される。
【００９７】
このように、ガロア体の元は、各ディスクで異なれば良く、必ずしも、式（１）のように、ディスク番号ｉに比例する乗数を持つガロア体の元を使用しなくても良い。これを利用して、α倍と、α−１倍の重み付け処理を用い、且つ繰り返し数が最小となるディスク番号ｉで、使用するガロア体を、αｉ−１倍と、α−ｉ＋８倍の重みを割り振る。これにより、図７及び図８では、ループ回数が、最大７回となる。
【００９８】
もし、図４の方法のみで行うと、ループ回数は、最大１３回となり、この実施の形態による、ループ回数の削減の効果は、大きい。
【００９９】
又、この実施の形態では、α倍と、α−１倍の重み付け処理を、図４の例で説明したが、他の１回の繰り返しでα倍、ｎ回の繰り返しで、αｎ倍の積演算ができる他の方法も適用できる。
【０１００】
勿論、図４の実施の形態の積演算処理を使用すれば、本実施の形態でも、６命令で実行でき、α倍するのに、２／３の処理時間で済み、高速に、ガロア体の積演算を実行できる。同様に、８シンボルを並列処理できるため、従来の４シンボルの並列処理に比し、更に２倍の高速処理が可能となり、結果として、１／３の処理時間で、ガロア体積演算を実現できる。
【０１０１】
（更に別のガロア体積演算処理）
図１２は、本発明のガロア体積演算処理の更に別の実施の形態の処理フロー図、図１３は、図１２の処理の説明図である。この実施の形態は、図４乃至図６の実施の形態のα倍演算処理を使用した任意のガロア体の元α^k倍の重みづけ処理を示し、最大反復回数が１５回で済むというメリットがある。この積演算処理は、特に、ｋ倍のｋが大きい時に、有効であり、ディスクの２重故障を復元させる際に使用することが好適である。
【０１０２】
図１３に示すように、例えば、１６ビットのガロア体ＧＦ（２＾１６）の最大のガロア体の元α^33653倍（αの３３６５３乗）の重みづけを行う際に、図４のα倍の重みづけアルゴリズムを用いた場合では、反復回数が３３６５３回、図７のα^(-1)倍の重みづけアルゴリズムを用いた場合では、反復回数が３１８８２回必要となり、効率的とは言えない。
【０１０３】
そこで、このようなケースでは、任意のガロア体重みづけアルゴリズムを使用する。このアルゴリズムは、ガロア体のベクトル表現を使用するところに特徴がある。任意のガロア体の元は、下記（４）式の関係がある。
【０１０４】
【数４】
【０１０５】
但し、ｇｆｗ（ｉ）は、「０」又は「１」のいずれかである。即ち、任意のガロア体を、２進数のベクトル表現(gfw(0), gfw(1),・・・, gfw(15))で表すことができる。
【０１０６】
又、1シンボルＤのα^k倍の重み付けは、下記（５）式のように、分配法則が成立する。
【０１０７】
【数５】
【０１０８】
図１２及び図１３の重み付け処理は、この分配法則を用いて重み付けを行う。例えば、α^33653倍の重みづけを行う場合には、ガロア体の法則から、下記（６）式の関係がある。
【０１０９】
【数６】
【０１１０】
従って、前述のベクトル表現では、( gfw(0), gfw(1),・・・, gfw(15) ) = ( 1, 0, 1, 0, ・・・, 0 )となる。
【０１１１】
また、反復回数は、gfw(i)=1となる最大のiを設定値として使用するため、反復回数ＭＡＸ＝２と設定する。この理由は、α^3・D, α^4・D, ・・・ の重み付けを、必要としないため、反復回数ＭＡＸを「２」に指定することで、余分な反復回数を減らすことが可能となり、処理時間を短縮する効果がある。
【０１１２】
図１３は、８シンボルデータ（Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５，Ｄ６，Ｄ７，Ｄ８）のα^33653倍の重みづけの例を示す。ＭＡＸ＝２回反復を繰り返すとき、α^0=1倍, α^1倍, α^2倍の重みづけデータが作成される。このうち、gfw(i)＝１となるi回目のα^i倍重み付けデータを足し算（ＸＯＲ）する。この例の場合には、０回目と２回目の重み付けデータを足し算（ＸＯＲ）する。
【０１１３】
これにより、目的の重み付けデータα＾33653・Ｄｊ（ｊ＝１，２，・・、８）を、（α＾０・Ｄｊ＋α＾２・Ｄｊ）により、得ることができる。
【０１１４】
図１２により処理を説明する。
【０１１５】
（Ｓ７０）ｘｍｍ１レジスタに、データを代入し、処理すべき繰り返し回数ＭＡＸを設定する。ｘｍｍ２レジスタを、ｖ０（オール「０」）に初期化する。又、繰り返し回数ポインタｉを「０」に初期化する。更に、ＭＡＸ＝０の場合には、ｘｍｍレジスタ１の内容を出力し、以下のステップを実行しないこととする。そして、ベクトルｇｆｗを設定する。
【０１１６】
又、図４と同様に、「３２７６８」と「４１０７」の値が入力された８シンボルのデータｖ３２７６８，ｖ４１０７を用意する。値「３２７６８」は、１６ビット目のみに「１」の値があることを示し、シフトにより桁上げが生じるシンボルを検出するためのデータである。値「４１０７」は、１６ビットのガロア体ＧＦ（２＾１６)の原始多項式（x^16+x^12+x^3+x+1）の（x^12+x^3+x+1）に、ｘ＝２を代入した値である。即ち、４０９６＋８＋２＋１＝４１０７である。
【０１１７】
（Ｓ７２）次に、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタに代入された値を、ｘｍｍ３レジスタに移動する。シフト命令（ＰＳＬＬＷ）に応じて、ｘｍｍ３レジスタの各シンボルを、左に（上位方向に）１ビットシフトする。これにより、各シンボルは、２倍（＝α倍）されるが、１シンボルが、１６ビットのため、桁上げされたビット部分は、オーバーフローする。このため、値が２倍になる箇所と、シフト前よりも値が小さくなる箇所がある。シフト前よりも値が小さくなる箇所は、オーバーフローした箇所である。
【０１１８】
（Ｓ７４）この値が小さくなる箇所（シンボル）のみに、値「４１０７」のＸＯＲを行う。このため、先ず、値が小さくなったシンボルを抽出し、その抽出したシンボルの値を、オール「１」（即ち、６５５３５）とする。即ち、ＡＮＤ命令（ＰＡＮＤ）に応じて、ｘｍｍ１レジスタの各シンボルの値と、ｖ３２７６８の値「３２７６８」との論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。８シンボルの内、オーバーフローしたシンボル（値が小さくなったシンボル）のみが、値「３２７６８」に置き換えられ、オーバーフローしないシンボルは、値「０」に置き換えられる。
【０１１９】
次に、８シンボルの値判定を行い、シンボルの値を、値「６５５３５」又は値「０」に置き換える。即ち、比較及び最大値設定命令（ＰＣＭＰＥＱＷ）に応じて、（ｘｍｍ１＆ｖ３２７６８）の各シンボルの値と、値「３２７６８」を比較して、両者が一致すると、そのシンボルの１６ビットを、オール「１」（＝６５５３５）に置き換え、両者が一致しないと、そのシンボルの１６ビットを、オール「０」（＝０）に置き換える。これにより、値「４１０７」のマスクを作成する。
【０１２０】
（Ｓ７６）そして、ＡＮＤ命令（ＰＡＮＤ）に応じて、このｘｍｍ１レジスタの各シンボルの値と、ｖ４１０７の値「４１０７」の論理積（ＡＮＤ）をとり、ｘｍｍ１レジスタを更新する。これにより、８シンボルのｘｍｍ１レジスタの内、値が小さくなったシンボルのみが、値「４１０７」に置き換えられ、値が小さくならないシンボルは、値「０」に置き換えられる。
【０１２１】
（Ｓ７８）ＸＯＲ命令（ＰＸＯＲ）に応じて、この更新されたｘｍｍ１レジスタの各シンボルの値と、ステップＳ７２で得たｘｍｍ３レジスタの各シンボルの値とのＸＯＲ（排他的論理輪）をとり、α倍の重みづけを行った結果を得る。
【０１２２】
（Ｓ８０）「ｂｒｅａｋ」が、検出された時に、処理を停止し、ｘｍｍ１の値を確定する。それ以外は、ステップＳ７４に戻る。
【０１２３】
（Ｓ８２）ＸＯＲ計算部では、移動命令（ＭＯＶＱ）に応じて、ｘｍｍ１レジスタの処理結果を、ｘｍｍ４レジスタに移動する。
【０１２４】
（Ｓ８４）その処理時のｇｆｗ（ｉ）が、「１」であるかを判定する。
【０１２５】
（Ｓ８６）ｇｆｗ（ｉ）が、「１」である場合には、前述のように、ＸＯＲの対象であるため、ｘｍｍ２レジスタの内容とｘｍｍ４レジスタの内容とのＸＯＲを演算し、演算結果で、ｘｍｍ２レジスタを更新する。
【０１２６】
（Ｓ８８）繰り返し回数ポインタｉを、「１」インクリメントする。
【０１２７】
（Ｓ９０）そして、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上であるかを判定する。繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上でなければ、ステップＳ７４に進む。
【０１２８】
（Ｓ９２）一方、繰り返し回数ポインタｉが、設定繰り返し回数ＭＡＸ以上である場合には、設定した繰り返し回数が終了したので、「ｂｒｅａｋ」を、α倍計算部のループに通知し、ｘｍｍ２を結果として、出力する。
【０１２９】
このように、α^k倍の重みづけ処理の最大反復回数を減少でき、ｋが大きい時に、有効であり、ディスクの２重故障を復元させる際に使用すると、高速に復元できる。
【０１３０】
（他の実施の形態）
前述の実施の形態では、１４台のデータディスク装置と２台のパリテイディスク装置とで構成されるＲＡＩＤ６のストレージ装置で、説明したが、他の台数の構成にも適用できる。
【０１３１】
又、パリテイＱの生成は、図４の実施の形態又は図１１の他の実施の形態のガロア体積演算処理を使用し、パリテイＰ、Ｑを使用した２重故障の復元には、図１２の更に別の実施の形態のガロア体積演算処理を使用することが、パリテイ生成と復元の両方を高速に実行できる。しかし、パリテイＱの生成は、図４の実施の形態又は図１１の他の実施の形態のガロア体積演算処理を使用し、パリテイＰ，Ｑによる二重故障の復元も、図４の実施の形態又は図１１の他の実施の形態のガロア体積演算処理を使用することもできる。又、パリテイＱの生成及びパリテイＰ，Ｑによる二重故障の復元とも、図４の実施の形態を含む図１２の更に別の実施の形態のガロア体積演算処理を使用することもできる。
【０１３２】
以上、本発明を、実施の形態で説明したが、本発明は、その趣旨の範囲内で種々の変形が可能であり、これを本発明の範囲から排除するものではない。
【０１３３】
（付記１）データを分割し、分割されたデータを各々格納する複数のデータストレージユニットと、前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成法定式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、前記データを分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記分割されたデータの各々をレジスタにロードし、且つレジスタの各データを上位桁方向にビットシフトし、前記ロードされたデータと前記シフトにより桁上がりビットを検出するための固定値との論理積をとり、且つ前記論理積の結果と前記固定値とを比較して、前記桁上がりビットを有するデータを、前記データの最大値に置き換え、マスクを作成し、前記マスクの最大値と前記桁上がりを補正する補正値との論理積を演算し、前記演算結果と前記シフトされたデータとの排他的論理和（ＸＯＲ）を演算して、前記データを前記ガロア体の元で積演算した結果を得ることを特徴とするＲＡＩＤ装置。
【０１３４】
（付記２）前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第１のパリテイデータ及び第２のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元することを特徴とする付記１のＲＡＩＤ装置。
【０１３５】
（付記３）前記制御ユニットは、最上位ビットのみが「１」である前記データのビット数と同一のビット数を有する前記固定値を使用することを特徴とする付記１のＲＡＩＤ装置。
【０１３６】
（付記４）前記制御ユニットは、複数のデータを前記レジスタにロードし、前記複数のデータに対し、前記積演算処理を並列に実行することを特徴とする付記１のＲＡＩＤ装置。
【０１３７】
（付記５）前記制御ユニットは、前記ガロア体の原始多項式から得た前記補正値を使用することを特徴とする付記１のＲＡＩＤ装置。
【０１３８】
（付記６）前記制御ユニットは、前記ガロア体の元の次数分、前記積演算を繰り返すことを特徴とする付記１のＲＡＩＤ装置。
【０１３９】
（付記７）前記制御ユニットは、前記ガロア体の元を、ベクトル表現し、且つ分配法則を用いて、重み付け値を分配して、前記ガロア体の元の積演算を実行することを特徴とする付記１のＲＡＩＤ装置。
【０１４０】
（付記８）前記制御ユニットは、前記分配した第１の重み付け値の積演算を第１の重み付け値の回数分実行した後、前記実行結果を用いて、前記積演算を第２の重み付け値の回数分実行し、前記第１の重み付け値の積演算結果と、前記第２の重み付け値の積演算結果の排他的論理和をとり、前記ガロア体の元の積演算結果を得ることを特徴とする付記７のＲＡＩＤ装置。
【０１４１】
（付記９）データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットと、前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、前記データをｎ分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、前記積演算を実行することを特徴とするＲＡＩＤ装置。
【０１４２】
（付記１０）前記制御ユニットは、前記ｎ分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのＸＯＲ演算を行い、α倍の積演算結果を演算することを特徴とする付記９のＲＡＩＤ装置。
【０１４３】
（付記１１）前記制御ユニットは、前記積演算を、ｍ回繰り返し、α＾ｍ倍の積演算結果を演算することを特徴とする付記１０のＲＡＩＤ装置。
【０１４４】
（付記１２）前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第１のパリテイデータ及び第２のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元することを特徴とする付記９のＲＡＩＤ装置。
【０１４５】
（付記１３）分散されたデータの各々をレジスタにロードするステップと、前記レジスタの各データを上位桁方向にビットシフトするステップと、前記ロードされたデータと前記シフトにより桁上がりビットを検出するための固定値との論理積をとるステップと、前記論理積の結果と前記固定値とを比較して、前記桁上がりビットを有するデータを、前記データの最大値に置き換え、マスクを作成するステップと、前記マスクの最大値と前記桁上がりを補正する補正値との論理積を演算するステップと、前記演算結果と前記シフトされたデータとの排他的論理和（ＸＯＲ）を演算して、前記データを前記ガロア体の元で積演算した結果を得るステップとからなることを特徴とするガロア体積演算処理方法。
【０１４６】
（付記１４）前記固定値との論理積ステップは、最上位ビットのみが「１」である前記データのビット数と同一のビット数を有する前記固定値を使用するステップからなることを特徴とする付記１３のガロア体積演算処理方法。
【０１４７】
（付記１５）前記ロードステップは、複数のデータを前記レジスタにロードするステップからなり、前記複数のデータに対し、前記シフトステップ、論理積ステップ、作成ステップ、論理積ステップ、排他的論理和ステップを並列に実行することを特徴とする付記１３のガロア体積演算処理方法。
【０１４８】
（付記１６）前記補正値との論理積ステップは、前記ガロア体の原始多項式から得た前記補正値を使用するステップからなることを特徴とする付記１３のガロア体積演算処理方法。
【０１４９】
（付記１７）前記ガロア体の元の次数分、前記積演算を繰り返すステップを、更に、有することを特徴とする付記１３のガロア体積演算処理方法。
【０１５０】
（付記１８）前記ガロア体の元を、ベクトル表現し、且つ分配法則を用いて、重み付け値を分配して、前記ガロア体の元の積演算を実行するステップを、更に、有することを特徴とする付記１３のガロア体積演算処理方法。
【０１５１】
（付記１９）前記実行ステップは、前記分配した第１の重み付け値の積演算を第１の重み付け値の回数分実行するステップと、前記実行結果を用いて、前記積演算を第２の重み付け値の回数分実行するステップと、前記第１の重み付け値の積演算結果と、前記第２の重み付け値の積演算結果の排他的論理和をとり、前記ガロア体の元の積演算結果を得るステップとからなることを特徴とする付記１８のガロア体積演算処理方法。
【０１５２】
（付記２０）データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するステップと、前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有することを特徴とするガロア体積演算処理方法。
【０１５３】
（付記２１）前記積演算ステップは、前記ｎ分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのＸＯＲ演算を行い、α倍の積演算結果を演算するステップからなることを特徴とする付記２０のガロア体積演算処理方法。
【０１５４】
（付記２２）前記積演算を、ｍ回繰り返し、α＾ｍ倍の積演算結果を演算するステップを、更に有することを特徴とする付記２１のガロア体積演算処理方法。
【産業上の利用可能性】
【０１５５】
ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するので、少ない繰り返し回数で、各データのガロア体の積演算が可能となる。
【符号の説明】
【０１５６】
１０−１〜１０−１４ データディスク装置
１０−１５〜１０−１６ パリテイディスク装置
１２ ＲＡＩＤコントローラ
１４ 接続バス
１６ ホスト
【特許請求の範囲】
【請求項１】
データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットと、
前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、
前記データをｎ分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、
前記制御ユニットは、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、前記積演算を実行する
ことを特徴とするＲＡＩＤ装置。
【請求項２】
データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、
前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するステップと、
前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有する
ことを特徴とするガロア体積演算処理方法。
【請求項１】
データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットと、
前記分割されたデータの組み合わせから得た第１のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第２のパリテイデータとを格納するパリテイストレージユニットと、
前記データをｎ分割し、前記第１のパリテイデータと第２のパリテイデータとを演算し、前記第１のパリテイデータと第２のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、
前記制御ユニットは、前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、前記積演算を実行する
ことを特徴とするＲＡＩＤ装置。
【請求項２】
データをｎ分割し、分割されたデータを各々格納するｎ台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、
前記ｎ台のデータストレージユニットの内、(ｎ−１)／２より大きな最小の整数をｓとする時に、ｉ＝１〜ｓ＋１番目のデータストレージユニットのデータのガロア体の元として、α＾（ｉ−１）を、ｉ＝ｓ＋２〜ｎ番目のデータストレージユニットのデータのガロア体の元を、α＾（−ｉ＋ｓ＋１）を、重み付けとして、積演算を実行するステップと、
前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有する
ことを特徴とするガロア体積演算処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１２−７０４３４（Ｐ２０１２−７０４３４Ａ）
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願番号】特願２０１１−２６９７７６（Ｐ２０１１−２６９７７６）
【出願日】平成２３年１２月９日（２０１１．１２．９）
【分割の表示】特願２００７−１０２０４（Ｐ２００７−１０２０４）の分割
【原出願日】平成１９年１月１９日（２００７．１．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願日】平成２３年１２月９日（２０１１．１２．９）
【分割の表示】特願２００７−１０２０４（Ｐ２００７−１０２０４）の分割
【原出願日】平成１９年１月１９日（２００７．１．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]