図面 (/)

技術 RAID装置及びガロア体の積演算処理方法

出願人 富士通株式会社
発明者 伊東利雄
出願日 2011年12月9日 (9年0ヶ月経過) 出願番号 2011-269776
公開日 2012年4月5日 (8年8ヶ月経過) 公開番号 2012-070434
状態 特許登録済
技術分野 エラーの検出訂正 外部記憶装置との入出力 符号誤り検出・訂正
主要キーワード 積演算処理 重み付け演算処理 二重故障 次数分 重み付けアルゴリズム C言語 最大反復回数 論理積結果
関連する未来課題
重要な関連分野

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

図面 (18)

課題

ガロア体を用いてパリテイデータを生成する際に、高速にガロア体の積演算を実行する。

解決手段

n台のデータストレージユニット(10−1〜10−16)の内、 (n−1)/2より大きな最小の整数をsとして、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、積演算を実行する。

概要

背景

ディスクの2重故障復元できる方法として、RAID(Redundant Array of Independent Disks)6が知られている。このRAID6の方式として、1次元冗長方式が提案されている(例えば、特許文献1参照)。

図14のRAID6の構成で説明すると、RAIDコントローラ110に、3台のデータディスク装置(ハードディスクドライブ)101,102,103と、2台のパリテイディスク装置(ハードディスクドライブ)104,105が、接続される。

1次元冗長方式は、データから2種類のパリテイを生成する。図15に示すように、1つ目のパリティPは、従来のRAID5と同じく、各データD1,D2,D3の足し算(XOR)を行った結果を、パリティとする。そして、このパリテイPは、第1のディスク装置104に保存する。尚、以下、「+」の記号は、XOR(排他的論理和)を示す。

2つ目のパリティQは、各データD1,D2,D3に対し、ガロア体積演算による重み付け行った後、それらを足し合わせた結果(XOR)をパリティとする。そして、このパリテイQは、第2のディスク装置105に保存される。

このガロア体は、各データディスク装置101,102,103に対して、1つ決定され、2重故障の復元のためには、各データディスク装置101,102,103で、異なっている必要がある。例えば、図15に示すように、データビット数を16ビットとすると、ガロア体GF(2^16)は、2の16乗個有限個の点を取りうる。又、ガロア体の四則演算が、所定の法則で可能である。1次元冗長方式は、パリテイの分散が可能となり、2重故障の検出、復元に有効である。

図15に示したように、ガロア体を利用したパリテイ生成においては、ガロア体の積演算として、データとガロア体の2つの変数を用いて、演算を行う必要がある。このため、RAID5のXOR演算(パリテイPの演算)に対し、パリテイ生成に処理時間を要し、性能が劣化する。

このガロア体の積演算を簡略化するため、複数のデータをシフトやAND,XORを使用し、α倍の重み付け(積演算)のアルゴリズムが提案されている(例えば、非特許文献1参照)。この提案された論文では、その4頁から5頁に、データが8ビットの場合のパリテイ生成、データ復元方程式解説し、6頁の下欄から7頁に、α倍のアルゴリズムをC言語で開示している。

このC言語で記述されたアルゴリズムを、図16及び図17を用いて、各々8ビットの4シンボルのデータを対象として、説明する。図16の「v」は、8ビット、4シンボル(32ビット)の対象データを示す。

先ず、ディスク装置の8ビットのデータを、4つ、32ビットのレジスタにロードする(S100)。この対象データv(32ビット)全体を、1ビット左(上位方向)にシフトする(S101)。1ビット左にシフトされたデータv<<1は、32ビット単位で、対象データvの2倍の値となる。

次に、シフトされたデータv<<1において、このデータvのシフトにより、他のシンボルへ影響したビットをマスクする。このため、マスク値「0xfefefefe」を用意し、シフトされたデータv<<1と、マスク値とのアンド(AND)演算を行い、マスクされたデータvvを得る(S102)。この操作により、8ビット間隔の右端(シフトにより影響されたビット)の値が、「0」に設定される。即ち、32ビット全体をシフトしているので、対象シンボルの右隣のシンボルの最上位ビットにより、対象シンボルの右端ビットが影響されることを防止する。

次に、対象データvからマスク(v)関数を、図17のように作成する(S103)。マスク(v)関数は、図17に示すように、32ビットの対象データvの8ビット間隔の左端が、「1」である場合には、8ビットの「11111111」を、左端が、「0」である場合には、8ビットの「00000000」を表す。即ち、シフトにより、桁上げされたシンボルには、8ビットのオール「1」を、桁上げされないシンボルには、8ビットのオール「0」を施すマスク(v)関数を作成する。

このため、マスク値「0x80808080」と、即ち、8ビット間隔で、「1」が現れ、その他は、「0」の値と、対象データvとの論理積(AND)をとる(S110)。このマスク値は、各シンボルの先頭ビットを抽出する。

次に、論理積値を、左に1ビットシフトした32ビットデータv<<1(2倍データ)を演算し、且つ論理積値を、右に7ビットシフトした32ビットデータv>>7(1/128倍データ)を演算し,左に1ビットシフトした32ビットデータv<<1(2倍データ)から右に7ビットシフトした32ビットデータv>>7を差し引き、マスク(v)関数MASK(v)を得る(S112)。この関数は、先頭ビットが、「1」のシンボルと、それ以外を区別する役目を持つ。

図16に戻り、8ビットのガロア体GF(2の8乗)の生成多項式(=x^8+x^2+1)に対応する係数値「0x1d1d1d1d」と、マスク(v)関数MASK(v)との論理積(AND)を演算する(S104)。即ち、4シンボルの内、先頭ビットが、「1」のシンボルのみに、係数値「0x1d1d1d1d」の「00011101」に置き換える。

この論理積結果と、ステップS102で、演算したマスクされた対象データvvとのXORを演算することにより、α倍された対象データα・vを得る(S105)。このα倍された対象データα・vに、これらのステップを再度繰り返すと、対象データvのαの二乗倍のデータが得られる。同様にして、対象データvのαの繰り返し倍のデータを演算できる。

このように、従来技術では、ステップS100で、代入、シフト、ステップS101で、AND,ステップS103(図17)で、AND,2回シフト、減算、ステップS104で、AND,ステップS105で、XORの9回の操作で、数シンボル(ここでは、4シンボル)のガロア体積演算の並列処理を実現できる。

概要

ガロア体を用いてパリテイデータを生成する際に、高速にガロア体の積演算を実行する。n台のデータストレージユニット(10−1〜10−16)の内、 (n−1)/2より大きな最小の整数をsとして、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、積演算を実行する。

目的

本発明の目的は、ガロア体積演算の処理時間を短縮するためのRAID装置及びガロア体の積演算処理方法を提供する

効果

実績

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

この技術が所属する分野

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

請求項1

データをn分割し、分割されたデータを各々格納するn台のデータストレージユニットと、前記分割されたデータの組み合わせから得た第1のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第2のパリテイデータとを格納するパリテイストレージユニットと、前記データをn分割し、前記第1のパリテイデータと第2のパリテイデータとを演算し、前記第1のパリテイデータと第2のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、前記積演算を実行することを特徴とするRAID装置

請求項2

データをn分割し、分割されたデータを各々格納するn台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、前記n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、積演算を実行するステップと、前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有することを特徴とするガロア体積演算処理方法。

技術分野

0001

本発明は、ガロア体演算により、データのパリテイを計算するRAID装置及びガロア体積演算方法に関し、特に、ディスク群の2重故障復元するのに好適なRAID装置及びガロア体の積演算方法に関する。

背景技術

0002

ディスクの2重故障を復元できる方法として、RAID(Redundant Array of Independent Disks)6が知られている。このRAID6の方式として、1次元冗長方式が提案されている(例えば、特許文献1参照)。

0003

図14のRAID6の構成で説明すると、RAIDコントローラ110に、3台のデータディスク装置(ハードディスクドライブ)101,102,103と、2台のパリテイディスク装置(ハードディスクドライブ)104,105が、接続される。

0004

1次元冗長方式は、データから2種類のパリテイを生成する。図15に示すように、1つ目のパリティPは、従来のRAID5と同じく、各データD1,D2,D3の足し算(XOR)を行った結果を、パリティとする。そして、このパリテイPは、第1のディスク装置104に保存する。尚、以下、「+」の記号は、XOR(排他的論理和)を示す。

0005

2つ目のパリティQは、各データD1,D2,D3に対し、ガロア体の積演算による重み付け行った後、それらを足し合わせた結果(XOR)をパリティとする。そして、このパリテイQは、第2のディスク装置105に保存される。

0006

このガロア体は、各データディスク装置101,102,103に対して、1つ決定され、2重故障の復元のためには、各データディスク装置101,102,103で、異なっている必要がある。例えば、図15に示すように、データビット数を16ビットとすると、ガロア体GF(2^16)は、2の16乗個有限個の点を取りうる。又、ガロア体の四則演算が、所定の法則で可能である。1次元冗長方式は、パリテイの分散が可能となり、2重故障の検出、復元に有効である。

0007

図15に示したように、ガロア体を利用したパリテイ生成においては、ガロア体の積演算として、データとガロア体の2つの変数を用いて、演算を行う必要がある。このため、RAID5のXOR演算(パリテイPの演算)に対し、パリテイ生成に処理時間を要し、性能が劣化する。

0008

このガロア体の積演算を簡略化するため、複数のデータをシフトやAND,XORを使用し、α倍の重み付け(積演算)のアルゴリズムが提案されている(例えば、非特許文献1参照)。この提案された論文では、その4頁から5頁に、データが8ビットの場合のパリテイ生成、データ復元方程式解説し、6頁の下欄から7頁に、α倍のアルゴリズムをC言語で開示している。

0009

このC言語で記述されたアルゴリズムを、図16及び図17を用いて、各々8ビットの4シンボルのデータを対象として、説明する。図16の「v」は、8ビット、4シンボル(32ビット)の対象データを示す。

0010

先ず、ディスク装置の8ビットのデータを、4つ、32ビットのレジスタにロードする(S100)。この対象データv(32ビット)全体を、1ビット左(上位方向)にシフトする(S101)。1ビット左にシフトされたデータv<<1は、32ビット単位で、対象データvの2倍の値となる。

0011

次に、シフトされたデータv<<1において、このデータvのシフトにより、他のシンボルへ影響したビットをマスクする。このため、マスク値「0xfefefefe」を用意し、シフトされたデータv<<1と、マスク値とのアンド(AND)演算を行い、マスクされたデータvvを得る(S102)。この操作により、8ビット間隔の右端(シフトにより影響されたビット)の値が、「0」に設定される。即ち、32ビット全体をシフトしているので、対象シンボルの右隣のシンボルの最上位ビットにより、対象シンボルの右端ビットが影響されることを防止する。

0012

次に、対象データvからマスク(v)関数を、図17のように作成する(S103)。マスク(v)関数は、図17に示すように、32ビットの対象データvの8ビット間隔の左端が、「1」である場合には、8ビットの「11111111」を、左端が、「0」である場合には、8ビットの「00000000」を表す。即ち、シフトにより、桁上げされたシンボルには、8ビットのオール「1」を、桁上げされないシンボルには、8ビットのオール「0」を施すマスク(v)関数を作成する。

0013

このため、マスク値「0x80808080」と、即ち、8ビット間隔で、「1」が現れ、その他は、「0」の値と、対象データvとの論理積(AND)をとる(S110)。このマスク値は、各シンボルの先頭ビットを抽出する。

0014

次に、論理積値を、左に1ビットシフトした32ビットデータv<<1(2倍データ)を演算し、且つ論理積値を、右に7ビットシフトした32ビットデータv>>7(1/128倍データ)を演算し,左に1ビットシフトした32ビットデータv<<1(2倍データ)から右に7ビットシフトした32ビットデータv>>7を差し引き、マスク(v)関数MASK(v)を得る(S112)。この関数は、先頭ビットが、「1」のシンボルと、それ以外を区別する役目を持つ。

0015

図16戻り、8ビットのガロア体GF(2の8乗)の生成多項式(=x^8+x^2+1)に対応する係数値「0x1d1d1d1d」と、マスク(v)関数MASK(v)との論理積(AND)を演算する(S104)。即ち、4シンボルの内、先頭ビットが、「1」のシンボルのみに、係数値「0x1d1d1d1d」の「00011101」に置き換える。

0016

この論理積結果と、ステップS102で、演算したマスクされた対象データvvとのXORを演算することにより、α倍された対象データα・vを得る(S105)。このα倍された対象データα・vに、これらのステップを再度繰り返すと、対象データvのαの二乗倍のデータが得られる。同様にして、対象データvのαの繰り返し倍のデータを演算できる。

0017

このように、従来技術では、ステップS100で、代入、シフト、ステップS101で、AND,ステップS103(図17)で、AND,2回シフト、減算、ステップS104で、AND,ステップS105で、XORの9回の操作で、数シンボル(ここでは、4シンボル)のガロア体積演算の並列処理を実現できる。

0018

日本国特開2000−259359号公報(図5図6

先行技術

0019

論文「The mathematics of RAID−6」(著者H.Peter Anvin、online paper, http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf、2006年10月26日アクセス

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

0020

この従来のガロア体の積演算処理では、複数シンボル(上の例では、4シンボル)の並列処理を実現できるが、α倍するには、9ステップの演算が必要となる。従って、αのn乗倍を演算するには、9・nステップの演算回数が必要となる。

0021

特に、近年の記憶容量の増大に伴い、対象データのシンボル数(データディスク装置の数)も増大する傾向にあり、例えば、2台のパリテイディスク装置に対し、14台のデータディスク装置を設けてRAID6を構成する場合には、αの13乗倍を演算する必要があり、9・13=117ステップの演算が必要となり、更なるステップ数の削減が望まれる。

0022

又、繰り返しにより、演算する場合には、その繰り返し数又は反復回数(積演算アルゴリズムのループ回数)が少ないことが、高速化のため、望まれる。

0023

更に、生成処理のみならず、復元処理においても、ガロア体の積演算処理に、反復回数が少ないことが、処理時間短縮の点で、望まれる。

0024

従って、本発明の目的は、ガロア体積演算の処理時間を短縮するためのRAID装置及びガロア体の積演算処理方法を提供することにある。

0025

又、本発明の他の目的は、ガロア体積演算の並列処理のステップ数を低減するためのRAID装置及びガロア体の積演算処理方法を提供することにある。

0026

更に、本発明の他の目的は、ガロア体積演算の並列処理の繰り返し数を低減するためのRAID装置及びガロア体の積演算処理方法を提供することにある。

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

0027

この目的の達成のため、本発明のRAID装置は、データをn分割し、分割されたデータを各々格納するn台のデータストレージユニットと、前記分割されたデータの組み合わせから得た第1のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第2のパリテイデータとを格納するパリテイストレージユニットと、前記データをn分割し、前記第1のパリテイデータと第2のパリテイデータとを演算し、前記第1のパリテイデータと第2のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、前記積演算を実行する。

0028

更に、本発明のガロア体の積演算処理方法は、データをn分割し、分割されたデータを各々格納するn台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、前記n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、積演算を実行するステップと、前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有する。

0029

更に、本発明では、好ましくは、前記制御ユニットは、前記n分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのXOR演算を行い、α倍の積演算結果を演算する。

0030

更に、本発明では、好ましくは、前記制御ユニットは、前記積演算を、m回繰り返し、α^m倍の積演算結果を演算する。

0031

更に、本発明では、好ましくは、前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第1のパリテイデータ及び第2のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元する。

発明の効果

0032

n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、積演算を実行するので、少ない繰り返し回数で、各データのガロア体の積演算が可能となる。

図面の簡単な説明

0033

本発明の一実施形態のRAID装置の構成図である。
本発明の一実施形態のパリテイ生成方法の説明図である。
図1のパリテイQのガロア体積演算処理フロー図である。
図2の詳細処理フロー図である、
図4の積演算処理の具体例の説明図である、
図5のマスク作成処理の説明図である。
本発明の他の実施の形態のガロア体積演算処理の説明図である。
図7の積演算処理の説明図である。
図7のパリテイQのガロア体積演算処理フロー図である。
図9操作処理フロー図である、
図9の詳細処理フロー図である、
本発明の更に別の実施の形態のガロア体積演算処理フロー図である。
図12の積演算処理の説明図である。
従来のRAID6の構成図である。
従来のRAID6のパリテイデータの説明図である。
従来のガロア体の積演算の説明図である、
従来のマスク作成処理の説明図である、

実施例

0034

以下、本発明の実施の形態を、RAID装置、ガロア体積演算処理、他のガロア体積演算処理、更に他のガロア体積演算処理、他の実施の形態の順で説明するが、本発明は、この実施の形態に限られない。

0035

(RAID装置)
図1は、本発明の一実施の形態のRAID装置の構成図、図2は、そのガロア体を用いたパリテイ演算の説明図である。図1に示すように、RAID装置は、ホストコンピュータ16に接続されたRAIDコントローラ12と、RAIDコントローラ12にFC(Fibre Channel)ループ14等により接続され、且つ制御される複数(ここでは、14台)のデータディスク装置(ハードディスクドライブ)10−1〜10−14と、2台のパリテイディスク装置(ハードディスクドライブ)10−15,10−16とからなる。即ち、2重パリテイを持つRAID6の構成である。

0036

図2に示すように、第1のパリテイPは、データディスク装置10−1〜10−14の列方向のデータD1〜D14のXORで生成され、第1のパリテイディスク装置10−15の対応アドレスに格納される。第2のパリテイQは、データディスク装置10−1〜10−14の列方向のデータD1〜D14を、ガロア体の積演算による重み付け後に、XORして生成され、第2のパリテイディスク装置10−16の対応アドレスに格納される。即ち、パリテイQは、下記式(1)で演算される。

0037

0038

尚、記号「+」は、XOR演算を示す。これらのパリテイ演算は、RAIDコントローラ12が、実行する。ここで、1シンボルを16ビットとすると、ガロア体は、GF(2の16乗)であり、その原始多項式(生成多項式)は、下記式(2)で表される。

0039

0040

又、この実施例で、ガロア体積演算に使用されるマスク値は、「32768」であり、16ビットのデータの最上位ビットのみが、「1」のデータである。又、値「4107」は、式(2)の原始多項式のxの16乗を除き、xに「2」を代入して得た値である。

0041

RAIDコントローラ12は、データをディスク装置10−1〜10−4にライト処理する際に、XOR演算により、パリテイPを計算し、第1のパリテイディスク装置10−15に格納し、以下で説明するガロア体の積演算処理とXOR演算を行い、パリテイQを計算し、第2のパリテイディスク装置10−16に格納する。

0042

(ガロア体積演算)
図3は、本発明の一実施の形態のガロア体積演算処理フロー図、図4は、図3の詳細処理フロー図、図5は、図3及び図4の具体例の説明図、図6は、桁上がりシンボルの積演算の説明図である。

0043

図3以下では、1シンボルを16ビットとして、8シンボルを並列処理する例で説明する。例えば、インテル社登録商標)のCPUでは、MMX命令セットが備わっている。MMX命令セットは、xmmレジスタを使用する。このxmmレジスタを用いて、並列処理を行う。xmmレジスタ長は、16Byteであり、1度に、1シンボルが16ビットの時、8シンボルのデータの重み付けの並列処理が行える。

0044

図3により、ガロア体積演算の基本的処理を説明する。

0045

(S10)先ず、xmm1レジスタに、8シンボルをロードする。

0046

(S12)次に、xmm1レジスタの各シンボルを、左に1ビットシフトし、各シンボルの値を2倍とする。

0047

(S14)マスク値を用いて、シフトにより値が小さくなるシンボル(即ち、最上位ビットの桁上がりが生じるシンボル)を検出する。

0048

(S16)シフトしたシンボルの内、値が小さくなったシンボルに、予め定めた値(「4107」)をXORする。

0049

次に、図4により、MMXを用いた重み付け処理を詳細に説明する。又、図5図6を用いて、データディスク番号i=2のガロア体の重み付け(ガロア体の積演算)処理を例に、具体的に説明を行う。データディスク番号i=2の場合には、式(1)のパリテイQの生成多項式から、データDi=2に、α倍の重みづけを行う。

0050

(S20)xmmレジスタに、データを代入し、処理すべき繰り返し回数MAXを設定する。例えば、ディスク番号i=2の場合には、MAX=1である。又、繰り返し回数ポインタiを「0」に初期化する。更に、MAX=0の場合には、xmmレジスタの内容を出力し、以下のステップを実行しないこととする。例えば、図5に示すように、データディスク番号i=2のディスクから、重み付けを行う8シンボル(1シンボル、16ビット)のデータ(Di=2データ)をピックアップし、これをxmm1レジスタに代入する(図5のxmm1)。

0051

又、「32768」と「4107」の値が入力された8シンボルのデータv32768,v4107を用意する。値「32768」は、16ビット目のみに「1」の値があることを示し、シフトにより桁上げが生じるシンボルを検出するためのデータである。値「4107」は、16ビットのガロア体GF(2^16)の原始多項式(x^16+x^12+x^3+x+1)の(x^12+x^3+x+1)に、x=2を代入した値である。即ち、4096+8+2+1=4107である。

0052

(S22)次に、移動命令(MOVQ)に応じて、xmm1レジスタに代入された値を、xmm2レジスタに移動する。シフト命令(PSLLW)に応じて、xmm2レジスタの各シンボルを、左に(上位方向に)1ビットシフトする(図5のxmm2)。これにより、各シンボルは、2倍(=α倍)されるが、1シンボルが、16ビットのため、桁上げされたビット部分は、オーバーフローする。このため、図5のxmm2に示すように、値が2倍になる箇所(一重下線)と、シフト前よりも値が小さくなる箇所(二重下線)がある。シフト前よりも値が小さくなる箇所は、オーバーフローした箇所である。

0053

(S24)この値が小さくなる箇所(シンボル)のみに、値「4107」のXORを行う。このため、先ず、値が小さくなったシンボルを抽出し、その抽出したシンボルの値を、オール「1」(即ち、65535)とする。図6も参照して、説明する。AND命令(PAND)に応じて、図5のxmm1レジスタの各シンボルの値と、v32768の値「32768」との論理積(AND)をとり、xmm1レジスタを更新する。図4及び図5の(xmm1&v32768)に示すように、8シンボルの内、オーバーフローしたシンボル(値が小さくなったシンボル)のみが、値「32768」に置き換えられ、オーバーフローしないシンボルは、値「0」に置き換えられる。

0054

次に、8シンボルの値判定を行い、シンボルの値を、値「65535」又は値「0」に置き換える。即ち、比較及び最大値設定命令PCMEQW)に応じて、(xmm1&v32768)の各シンボルの値と、値「32768」を比較して、両者が一致すると、そのシンボルの16ビットを、オール「1」(=65535)に置き換え、両者が一致しないと、そのシンボルの16ビットを、オール「0」(=0)に置き換える。これにより、値「4107」のマスクを作成する。

0055

(S26)そして、AND命令(PAND)に応じて、このxmm1レジスタの各シンボルの値と、v4107の値「4107」の論理積(AND)をとり、xmm1レジスタを更新する。これにより、8シンボルのxmm1レジスタの内、値が小さくなったシンボルのみが、値「4107」に置き換えられ、値が小さくならないシンボルは、値「0」に置き換えられる。

0056

(S28)XOR命令(PXOR)に応じて、この更新されたxmm1レジスタの各シンボルの値と、ステップS22で得たxmm2レジスタの各シンボルの値とのXOR(排他論理輪)をとり、α倍の重みづけを行った結果を得る。

0057

(S30)「break」が、検出された時に、処理を停止し、xmm1の値を確定する。それ以外は、ステップS24に戻る。

0058

(S32)α倍計算処理開始にあたり、繰り返し回数ポインタiを、「1」インクリメントする。そして、繰り返し回数ポインタiが、設定繰り返し回数MAX以上であるかを判定する。繰り返し回数ポインタiが、設定繰り返し回数MAX以上でなければ、ステップS24に進む。

0059

(S34)一方、繰り返し回数ポインタiが、設定繰り返し回数MAX以上である場合には、設定した繰り返し回数が終了したので、「break」を通知し、xmm1を結果として、出力する。

0060

例えば、図5において、第2番目のシンボルの値「36934」を単純に2倍すると、「73868」となるが、1シンボルが16ビットに制限されるため、オーバーフローが生じ、そのシンボルの値は、1ビットオーバーフローしているため、16ビット表示で、8332(=73868−65536)となる。しかし、第2番目のシンボルの2倍値の有意ビットは、17ビットから2ビット目の16ビットである。この有意ビットを補正するため、補正値「4107」を使用し、値「12423」に変換する。

0061

ステップS22〜S28の処理は、どれもレイテンシが小さい(レイテンシ=2)命令で実現でき、処理時間を短くすることができる。α^j倍の重みづけでは、ステップS22〜S28の処理をj回繰り返す。

0062

ここで、この実施の形態のマスク処理を、図6で説明する。図6は、シフトにより値が小さくなったシンボルを抽出するマスク処理を示し、先ず、xmm1レジスタの値と、v32768のアンドで、オーバーフローシンボルと、オーバーフローしないシンボルを識別する。次に、これらのシンボルと、値「32768」を比較し、両者が一致するシンボルを、オール「1」(=65535)に置き換え、マスクを作成する。そして、値v4107とのアンドをとり、求めるxmm1を得る。

0063

一方、図17に示すように、従来技術では、元のシンボルvに、値「0x80808080」をアンドし、オーバーフローシンボルと、オーバーフローしないシンボルを識別する。次に、この結果から、マスクを作成するため、この結果を、左1ビットシフトしたものを作成し、且つ右に7ビットシフトしたものを作成し、これらのシフト結果引き算する。

0064

即ち、本実施の形態では、図6のマスク処理は、マスク作成に、ANDと、比較命令の2命令で行っているのに対し、従来は、AND,シフト2回、引き算命令の4命令で実行している。

0065

更に、本実施の形態では、図5に示すように、左シフトは、シンボル単位に、独立で行っているのに対し、従来技術では、図16に示すように、レジスタ全体、即ち、4シンボル単位で行っている。このため、従来技術では、シフト後、シンボルの右端が、右隣のシンボルの最上位ビットに影響されないように、シンボルの右端を、強制的に、「0」に置き換える処理が余分に必要である。

0066

従って、従来は、9命令で実行していたものを、本実施の形態では、6命令で実行できる。即ち、α倍するのに、2/3の処理時間で済み、高速に、ガロア体の積演算を実行できる。例えば、αの13乗の積演算では、従来は、9×13=117命令(ステップ)必要としたのに対し、本実施の形態は、6×13=78命令(ステップ)で済む。更に、式(1)の積演算では、従来は、9×(1+2+3+4+5+6+7+8+9+10+11+12+13=91)=819命令の実行を要するが、本実施の形態では、6×(1+2+3+4+5+6+7+8+9+10+11+12+13=91)=546命令の実行で済み、高速に、ガロア体積演算を実行できる。

0067

更に、本実施の形態では、8シンボルを並列処理できるため、従来の4シンボルの並列処理に比し、更に2倍の高速処理が可能となり、結果として、1/3の処理時間で、ガロア体積演算を実現できる。

0068

(他のガロア体積演算処理)
図7は、本発明のガロア体積演算処理の他の実施の形態の処理フロー図、図8は、図7の重み付け処理の説明図、図9は、図7のα−1倍の積演算処理フロー図、図10は、そのオペレーションの説明図、図11は、図9の詳細処理フロー図である。

0069

前述の実施の形態は、ガロア体の積演算処理の1回の処理時間を短縮するものであったが、この実施の形態は、積演算処理の並列処理アルゴリズムのループ回数が少なくなるように、ガロア体の元を決定し、ガロア体の積演算処理時間を短縮するものである。

0070

図7に示すように、図1乃至図2と同様に、データディスク装置を14台で構成した例とすると、データディスク番号 i (=1〜14)に対し、i=1〜8の場合は、αi−1倍による重み付けを行い、図4乃至図6重み付け演算処理を行い、i=9〜14の場合は、α−i+8倍による重み付けを行い、図8以下で説明するα−1倍の重みづけアルゴリズムを使用する。

0071

この重み付けの割り振り一般化すると、データディスク装置をn台で構成した例とすると、(n−1)/2より大きな最小の整数をsとする時に、データディスク番号i=1〜s+1の場合は、α^(i−1)倍による重み付けを行い、図4乃至図6の重み付け演算処理を行い、i=s+2〜nの場合は、α−i+s+1倍による重み付けを行う。

0072

α倍の重みづけ処理は、図4乃至図6で説明したので、ここでは、説明を省略し、α−1倍の重み付け処理を、図8乃至図11で説明する。

0073

図8に示すように、第1のパリテイPは、データディスク装置10−1〜10−14の列方向のデータD1〜D14のXORで生成され、第1のパリテイディスク装置10−15の対応アドレスに格納される。第2のパリテイQは、データディスク装置10−1〜10−14の列方向のデータD1〜D14を、ガロア体の積演算による重み付け後に、XORして生成され、第2のパリテイディスク装置10−16の対応アドレスに格納される。即ち、パリテイQは、下記式(3)で演算される。

0074

0075

尚、記号「+」は、XOR演算を示す。これらのパリテイ演算は、RAIDコントローラ12が、実行する。ここで、1シンボルを16ビットとすると、ガロア体は、GF(2の16乗)であり、その原始多項式(生成多項式)は、前記式(2)で表される。

0076

又、この実施例で、α−1倍のガロア体積演算に使用されるマスク値は、「1」であり、16ビットのデータの最下位ビットのみが、「1」のデータである。又、値「34821」は、式(2)の原始多項式をxで割り、割った式のxに「2」を代入して得た値である。

0077

RAIDコントローラ12は、データをディスク装置10−1〜10−14にライト処理する際に、XOR演算により、パリテイPを計算し、第1のパリテイディスク装置10−15に格納し、以下で説明するガロア体の積演算処理とXOR演算を行い、パリテイQを計算し、第2のパリテイディスク装置10−16に格納する。

0078

図9以下でも、1シンボルを16ビットとして、8シンボルを並列処理する例で説明する。例えば、インテル社(登録商標)のCPUでは、MMX命令セットが備わっている。MMX命令セットは、xmmレジスタを使用する。このxmmレジスタを用いて、並列処理を行う。xmmレジスタ長は、16Byteであり、1度に、1シンボルが16ビットの時は、8シンボルのデータの重み付けの並列処理が行える。

0079

図9により、α−1倍のガロア体積演算の基本的処理を説明する。

0080

(S40)先ず、xmm1レジスタに、8シンボルをロードする。

0081

(S42)次に、xmm1レジスタの各シンボルを、右方向(最下位ビット方向)に1ビットシフトし、各シンボルの値を1/2倍とする。

0082

(S44)マスク値を用いて、シフトにより値の桁落ちが生じるシンボル(即ち、対象シンボルの最下位ビット「1」が、消失するシンボル)を検出する。

0083

(S46)シフトしたシンボルの内、桁落ちしたシンボルに、予め定めた値(「34821」)をXORする。

0084

次に、図11により、MMXを用いた重み付け処理を詳細に説明する。又、図10を用いて、データディスク番号i=9のα−1倍のガロア体の重み付け(ガロア体の積演算)処理を例に、具体的に説明を行う。データディスク番号i=9の場合には、式(3)のパリテイQの生成多項式から、データDi=9に、α−1倍の重みづけを行う。

0085

(S50)xmmレジスタに、データを代入し、処理すべき繰り返し回数MAXを設定する。例えば、ディスク番号i=9場合には、MAX=1である。又、繰り返し回数ポインタiを「0」に初期化する。例えば、図5と同様に、データディスク番号i=9のディスクから、重み付けを行う8シンボル(1シンボル、16ビット)のデータ(Di=9データ)をピックアップし、これをxmm1レジスタに代入する(図10の(1))。

0086

又、「1」と「34821」の値が入力された8シンボルのデータv1,v34821を用意する。値「1」は、最下位である1ビット目のみに「1」の値があることを示し、左シフトにより桁落ちが生じるシンボルを検出するためのデータである。

0087

値「34281」は、16ビットのガロア体GF(2^16)の原始多項式(x^16+x^12+x^3+x+1)から「1」を除き、且つこの結果をxで割った多項式(x^15+x^11+x^2+1)に、x=2を代入した値である。この意味は、16ビットのガロア体GF(2^16)の原始多項式(α^16+α^12+α^3+α+1)=0の原則により、(α^16+α^12+α^3+α)=1が成立する。このαに「2」を代入すると、69642=1が得られる。両辺を右(最下位)方向に1ビットシフトすると、34821=値が消失、となる。16ビットデータの右辺に、「1」が有る場合に、右シフトすると、右辺の「1」が消失するため、「34821」をXORすることにより、値を補正するものである。

0088

(S52)次に、移動命令(MOVQ)に応じて、xmm1レジスタに代入された値を、xmm2レジスタに移動する。シフト命令(PSRLW)に応じて、xmm2レジスタの各シンボルを、右に(下位方向に)1ビットシフトする(図10の(2)のxmm2)。これにより、各シンボルは、1/2倍(=α−1倍)されるが、1シンボルが、16ビットのため、桁落ちされたビット部分は、アンダーフローする。このため、図5と同様に、値がそのまま2倍になる箇所と、桁落ちする箇所(アンダーフローした箇所)とが混在する。

0089

(S54)この桁落ちした箇所(シンボル)のみに、値「34821」のXORを行う。このため、先ず、桁落ちしたシンボルを抽出し、その抽出したシンボルの値を、オール「1」(即ち、65535)とする。即ち、AND命令(PAND)に応じて、図10のxmm1レジスタの各シンボルの値と、v1の値「1」との論理積(AND)をとり、xmm1レジスタを更新する。(xmm1&v1)は、8シンボルの内、最下位桁が「1」であるシンボルのみが、値「1」に置き換えられ、それ以外は、値「0」に置き換えられる。

0090

次に、8シンボルの値判定を行い、シンボルの値を、値「65535」又は値「0」に置き換える。即ち、比較及び最大値設定命令(PCMPEQW)に応じて、(xmm1&v1)の各シンボルの値と、値「1」を比較して、両者が一致すると、そのシンボルの16ビットを、オール「1」(=65535)に置き換え、両者が一致しないと、そのシンボルの16ビットを、オール「0」(=0)に置き換える。これにより、値「34821」のマスクを作成する。

0091

(S56)そして、AND命令(PAND)に応じて、このxmm1レジスタの各シンボルの値と、v34821の値「34821」の論理積(AND)をとり、xmm1レジスタを更新する。これにより、8シンボルのxmm1レジスタの内、最下位桁が「1」のシンボルのみが、値「34821」に置き換えられ、それ以外のシンボルは、値「0」に置き換えられる。

0092

(S58)XOR命令(PXOR)に応じて、この更新されたxmm1レジスタの各シンボルの値と、ステップS52で得たxmm2レジスタの各シンボルの値とのXOR(排他的論理輪)をとり、α−1倍の重みづけを行った結果を得る。

0093

(S60)「break」が、検出された時に、処理を停止し、xmm1の値を確定する。それ以外は、ステップS54に戻る。

0094

(S62)α^−1倍計算処理開始にあたり、繰り返し回数ポインタiを、「1」インクリメントする。そして、繰り返し回数ポインタiが、設定繰り返し回数MAX以上であるかを判定する。繰り返し回数ポインタiが、設定繰り返し回数MAX以上でなければ、ステップS54に進む。

0095

(S64)一方、繰り返し回数ポインタiが、設定繰り返し回数MAX以上である場合には、設定した繰り返し回数が終了したので、「break」を通知し、xmm1を結果として、出力する。

0096

このように、このα−1倍の重み付けアルゴリズムの特徴は、xmmレジスタに代入された値を、右1ビットシフトする点であり、基本的な考え方はα倍の重みづけアルゴリズムと同じである。出力は、ディスク番号i=9〜14に対し、α^-(i-8)倍の重みづけ結果が出力される。

0097

このように、ガロア体の元は、各ディスクで異なれば良く、必ずしも、式(1)のように、ディスク番号iに比例する乗数を持つガロア体の元を使用しなくても良い。これを利用して、α倍と、α−1倍の重み付け処理を用い、且つ繰り返し数が最小となるディスク番号iで、使用するガロア体を、αi−1倍と、α−i+8倍の重みを割り振る。これにより、図7及び図8では、ループ回数が、最大7回となる。

0098

もし、図4の方法のみで行うと、ループ回数は、最大13回となり、この実施の形態による、ループ回数の削減の効果は、大きい。

0099

又、この実施の形態では、α倍と、α−1倍の重み付け処理を、図4の例で説明したが、他の1回の繰り返しでα倍、n回の繰り返しで、αn倍の積演算ができる他の方法も適用できる。

0100

勿論、図4の実施の形態の積演算処理を使用すれば、本実施の形態でも、6命令で実行でき、α倍するのに、2/3の処理時間で済み、高速に、ガロア体の積演算を実行できる。同様に、8シンボルを並列処理できるため、従来の4シンボルの並列処理に比し、更に2倍の高速処理が可能となり、結果として、1/3の処理時間で、ガロア体積演算を実現できる。

0101

(更に別のガロア体積演算処理)
図12は、本発明のガロア体積演算処理の更に別の実施の形態の処理フロー図、図13は、図12の処理の説明図である。この実施の形態は、図4乃至図6の実施の形態のα倍演算処理を使用した任意のガロア体の元α^k倍の重みづけ処理を示し、最大反復回数が15回で済むというメリットがある。この積演算処理は、特に、k倍のkが大きい時に、有効であり、ディスクの2重故障を復元させる際に使用することが好適である。

0102

図13に示すように、例えば、16ビットのガロア体GF(2^16)の最大のガロア体の元α^33653倍(αの33653乗)の重みづけを行う際に、図4のα倍の重みづけアルゴリズムを用いた場合では、反復回数が33653回、図7のα^(-1)倍の重みづけアルゴリズムを用いた場合では、反復回数が31882回必要となり、効率的とは言えない。

0103

そこで、このようなケースでは、任意のガロア体重みづけアルゴリズムを使用する。このアルゴリズムは、ガロア体のベクトル表現を使用するところに特徴がある。任意のガロア体の元は、下記(4)式の関係がある。

0104

0105

但し、gfw(i)は、「0」又は「1」のいずれかである。即ち、任意のガロア体を、2進数のベクトル表現(gfw(0), gfw(1),・・・, gfw(15))で表すことができる。

0106

又、1シンボルDのα^k倍の重み付けは、下記(5)式のように、分配法則が成立する。

0107

0108

図12及び図13の重み付け処理は、この分配法則を用いて重み付けを行う。例えば、α^33653倍の重みづけを行う場合には、ガロア体の法則から、下記(6)式の関係がある。

0109

0110

従って、前述のベクトル表現では、( gfw(0), gfw(1),・・・, gfw(15) ) = ( 1, 0, 1, 0, ・・・, 0 )となる。

0111

また、反復回数は、gfw(i)=1となる最大のiを設定値として使用するため、反復回数MAX=2と設定する。この理由は、α^3・D, α^4・D, ・・・ の重み付けを、必要としないため、反復回数MAXを「2」に指定することで、余分な反復回数を減らすことが可能となり、処理時間を短縮する効果がある。

0112

図13は、8シンボルデータ(D1,D2,D3,D4,D5,D6,D7,D8)のα^33653倍の重みづけの例を示す。MAX=2回反復を繰り返すとき、α^0=1倍, α^1倍, α^2倍の重みづけデータが作成される。このうち、gfw(i)=1となるi回目のα^i倍重み付けデータを足し算(XOR)する。この例の場合には、0回目と2回目の重み付けデータを足し算(XOR)する。

0113

これにより、目的の重み付けデータα^33653・Dj(j=1,2,・・、8)を、(α^0・Dj+α^2・Dj)により、得ることができる。

0114

図12により処理を説明する。

0115

(S70)xmm1レジスタに、データを代入し、処理すべき繰り返し回数MAXを設定する。xmm2レジスタを、v0(オール「0」)に初期化する。又、繰り返し回数ポインタiを「0」に初期化する。更に、MAX=0の場合には、xmmレジスタ1の内容を出力し、以下のステップを実行しないこととする。そして、ベクトルgfwを設定する。

0116

又、図4と同様に、「32768」と「4107」の値が入力された8シンボルのデータv32768,v4107を用意する。値「32768」は、16ビット目のみに「1」の値があることを示し、シフトにより桁上げが生じるシンボルを検出するためのデータである。値「4107」は、16ビットのガロア体GF(2^16)の原始多項式(x^16+x^12+x^3+x+1)の(x^12+x^3+x+1)に、x=2を代入した値である。即ち、4096+8+2+1=4107である。

0117

(S72)次に、移動命令(MOVQ)に応じて、xmm1レジスタに代入された値を、xmm3レジスタに移動する。シフト命令(PSLLW)に応じて、xmm3レジスタの各シンボルを、左に(上位方向に)1ビットシフトする。これにより、各シンボルは、2倍(=α倍)されるが、1シンボルが、16ビットのため、桁上げされたビット部分は、オーバーフローする。このため、値が2倍になる箇所と、シフト前よりも値が小さくなる箇所がある。シフト前よりも値が小さくなる箇所は、オーバーフローした箇所である。

0118

(S74)この値が小さくなる箇所(シンボル)のみに、値「4107」のXORを行う。このため、先ず、値が小さくなったシンボルを抽出し、その抽出したシンボルの値を、オール「1」(即ち、65535)とする。即ち、AND命令(PAND)に応じて、xmm1レジスタの各シンボルの値と、v32768の値「32768」との論理積(AND)をとり、xmm1レジスタを更新する。8シンボルの内、オーバーフローしたシンボル(値が小さくなったシンボル)のみが、値「32768」に置き換えられ、オーバーフローしないシンボルは、値「0」に置き換えられる。

0119

次に、8シンボルの値判定を行い、シンボルの値を、値「65535」又は値「0」に置き換える。即ち、比較及び最大値設定命令(PCMPEQW)に応じて、(xmm1&v32768)の各シンボルの値と、値「32768」を比較して、両者が一致すると、そのシンボルの16ビットを、オール「1」(=65535)に置き換え、両者が一致しないと、そのシンボルの16ビットを、オール「0」(=0)に置き換える。これにより、値「4107」のマスクを作成する。

0120

(S76)そして、AND命令(PAND)に応じて、このxmm1レジスタの各シンボルの値と、v4107の値「4107」の論理積(AND)をとり、xmm1レジスタを更新する。これにより、8シンボルのxmm1レジスタの内、値が小さくなったシンボルのみが、値「4107」に置き換えられ、値が小さくならないシンボルは、値「0」に置き換えられる。

0121

(S78)XOR命令(PXOR)に応じて、この更新されたxmm1レジスタの各シンボルの値と、ステップS72で得たxmm3レジスタの各シンボルの値とのXOR(排他的論理輪)をとり、α倍の重みづけを行った結果を得る。

0122

(S80)「break」が、検出された時に、処理を停止し、xmm1の値を確定する。それ以外は、ステップS74に戻る。

0123

(S82)XOR計算部では、移動命令(MOVQ)に応じて、xmm1レジスタの処理結果を、xmm4レジスタに移動する。

0124

(S84)その処理時のgfw(i)が、「1」であるかを判定する。

0125

(S86)gfw(i)が、「1」である場合には、前述のように、XORの対象であるため、xmm2レジスタの内容とxmm4レジスタの内容とのXORを演算し、演算結果で、xmm2レジスタを更新する。

0126

(S88)繰り返し回数ポインタiを、「1」インクリメントする。

0127

(S90)そして、繰り返し回数ポインタiが、設定繰り返し回数MAX以上であるかを判定する。繰り返し回数ポインタiが、設定繰り返し回数MAX以上でなければ、ステップS74に進む。

0128

(S92)一方、繰り返し回数ポインタiが、設定繰り返し回数MAX以上である場合には、設定した繰り返し回数が終了したので、「break」を、α倍計算部のループに通知し、xmm2を結果として、出力する。

0129

このように、α^k倍の重みづけ処理の最大反復回数を減少でき、kが大きい時に、有効であり、ディスクの2重故障を復元させる際に使用すると、高速に復元できる。

0130

(他の実施の形態)
前述の実施の形態では、14台のデータディスク装置と2台のパリテイディスク装置とで構成されるRAID6のストレージ装置で、説明したが、他の台数の構成にも適用できる。

0131

又、パリテイQの生成は、図4の実施の形態又は図11の他の実施の形態のガロア体積演算処理を使用し、パリテイP、Qを使用した2重故障の復元には、図12の更に別の実施の形態のガロア体積演算処理を使用することが、パリテイ生成と復元の両方を高速に実行できる。しかし、パリテイQの生成は、図4の実施の形態又は図11の他の実施の形態のガロア体積演算処理を使用し、パリテイP,Qによる二重故障の復元も、図4の実施の形態又は図11の他の実施の形態のガロア体積演算処理を使用することもできる。又、パリテイQの生成及びパリテイP,Qによる二重故障の復元とも、図4の実施の形態を含む図12の更に別の実施の形態のガロア体積演算処理を使用することもできる。

0132

以上、本発明を、実施の形態で説明したが、本発明は、その趣旨の範囲内で種々の変形が可能であり、これを本発明の範囲から排除するものではない。

0133

(付記1)データを分割し、分割されたデータを各々格納する複数のデータストレージユニットと、前記分割されたデータの組み合わせから得た第1のパリテイデータと、パリテイの生成法定式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第2のパリテイデータとを格納するパリテイストレージユニットと、前記データを分割し、前記第1のパリテイデータと第2のパリテイデータとを演算し、前記第1のパリテイデータと第2のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記分割されたデータの各々をレジスタにロードし、且つレジスタの各データを上位桁方向にビットシフトし、前記ロードされたデータと前記シフトにより桁上がりビットを検出するための固定値との論理積をとり、且つ前記論理積の結果と前記固定値とを比較して、前記桁上がりビットを有するデータを、前記データの最大値に置き換え、マスクを作成し、前記マスクの最大値と前記桁上がりを補正する補正値との論理積を演算し、前記演算結果と前記シフトされたデータとの排他的論理和(XOR)を演算して、前記データを前記ガロア体の元で積演算した結果を得ることを特徴とするRAID装置。

0134

(付記2)前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第1のパリテイデータ及び第2のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元することを特徴とする付記1のRAID装置。

0135

(付記3)前記制御ユニットは、最上位ビットのみが「1」である前記データのビット数と同一のビット数を有する前記固定値を使用することを特徴とする付記1のRAID装置。

0136

(付記4)前記制御ユニットは、複数のデータを前記レジスタにロードし、前記複数のデータに対し、前記積演算処理を並列に実行することを特徴とする付記1のRAID装置。

0137

(付記5)前記制御ユニットは、前記ガロア体の原始多項式から得た前記補正値を使用することを特徴とする付記1のRAID装置。

0138

(付記6)前記制御ユニットは、前記ガロア体の元の次数分、前記積演算を繰り返すことを特徴とする付記1のRAID装置。

0139

(付記7)前記制御ユニットは、前記ガロア体の元を、ベクトル表現し、且つ分配法則を用いて、重み付け値分配して、前記ガロア体の元の積演算を実行することを特徴とする付記1のRAID装置。

0140

(付記8)前記制御ユニットは、前記分配した第1の重み付け値の積演算を第1の重み付け値の回数分実行した後、前記実行結果を用いて、前記積演算を第2の重み付け値の回数分実行し、前記第1の重み付け値の積演算結果と、前記第2の重み付け値の積演算結果の排他的論理和をとり、前記ガロア体の元の積演算結果を得ることを特徴とする付記7のRAID装置。

0141

(付記9)データをn分割し、分割されたデータを各々格納するn台のデータストレージユニットと、前記分割されたデータの組み合わせから得た第1のパリテイデータと、パリテイの生成方程式におけるガロア体の元を前記分割されたデータに積演算し、且つ積演算結果を用いて前記生成方程式を演算して得た第2のパリテイデータとを格納するパリテイストレージユニットと、前記データをn分割し、前記第1のパリテイデータと第2のパリテイデータとを演算し、前記第1のパリテイデータと第2のパリテイデータとを前記パリテイストレージユニットに格納する制御ユニットとを有し、前記制御ユニットは、前記n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、前記積演算を実行することを特徴とするRAID装置。

0142

(付記10)前記制御ユニットは、前記n分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのXOR演算を行い、α倍の積演算結果を演算することを特徴とする付記9のRAID装置。

0143

(付記11)前記制御ユニットは、前記積演算を、m回繰り返し、α^m倍の積演算結果を演算することを特徴とする付記10のRAID装置。

0144

(付記12)前記制御ユニットは、前記データストレージユニットの任意のデータストレージユニットの障害時に、前記障害発生したデータストレージユニットのデータを未知データとし、前記第1のパリテイデータ及び第2のパリテイデータと、前記障害発生したデータストレージユニット以外の前記データストレージユニットのデータとを用いて、前記ガロア体の連立方程式から、前記未知データを復元することを特徴とする付記9のRAID装置。

0145

(付記13)分散されたデータの各々をレジスタにロードするステップと、前記レジスタの各データを上位桁方向にビットシフトするステップと、前記ロードされたデータと前記シフトにより桁上がりビットを検出するための固定値との論理積をとるステップと、前記論理積の結果と前記固定値とを比較して、前記桁上がりビットを有するデータを、前記データの最大値に置き換え、マスクを作成するステップと、前記マスクの最大値と前記桁上がりを補正する補正値との論理積を演算するステップと、前記演算結果と前記シフトされたデータとの排他的論理和(XOR)を演算して、前記データを前記ガロア体の元で積演算した結果を得るステップとからなることを特徴とするガロア体積演算処理方法。

0146

(付記14)前記固定値との論理積ステップは、最上位ビットのみが「1」である前記データのビット数と同一のビット数を有する前記固定値を使用するステップからなることを特徴とする付記13のガロア体積演算処理方法。

0147

(付記15)前記ロードステップは、複数のデータを前記レジスタにロードするステップからなり、前記複数のデータに対し、前記シフトステップ、論理積ステップ、作成ステップ、論理積ステップ、排他的論理和ステップを並列に実行することを特徴とする付記13のガロア体積演算処理方法。

0148

(付記16)前記補正値との論理積ステップは、前記ガロア体の原始多項式から得た前記補正値を使用するステップからなることを特徴とする付記13のガロア体積演算処理方法。

0149

(付記17)前記ガロア体の元の次数分、前記積演算を繰り返すステップを、更に、有することを特徴とする付記13のガロア体積演算処理方法。

0150

(付記18)前記ガロア体の元を、ベクトル表現し、且つ分配法則を用いて、重み付け値を分配して、前記ガロア体の元の積演算を実行するステップを、更に、有することを特徴とする付記13のガロア体積演算処理方法。

0151

(付記19)前記実行ステップは、前記分配した第1の重み付け値の積演算を第1の重み付け値の回数分実行するステップと、前記実行結果を用いて、前記積演算を第2の重み付け値の回数分実行するステップと、前記第1の重み付け値の積演算結果と、前記第2の重み付け値の積演算結果の排他的論理和をとり、前記ガロア体の元の積演算結果を得るステップとからなることを特徴とする付記18のガロア体積演算処理方法。

0152

(付記20)データをn分割し、分割されたデータを各々格納するn台のデータストレージユニットのデータのパリテイデータをガロア体を用いて生成するためのガロア体積演算処理方法において、n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、積演算を実行するステップと、前記積演算結果で、前記パリテイのガロア体を用いた生成方程式を演算するステップを有することを特徴とするガロア体積演算処理方法。

0153

(付記21)前記積演算ステップは、前記n分割されたデータのシフト、シフトによる桁上がりデータの抽出、桁上がりデータのマスク作成、前記マスクを使用して、前記シフトされたデータと補正値とのXOR演算を行い、α倍の積演算結果を演算するステップからなることを特徴とする付記20のガロア体積演算処理方法。

0154

(付記22)前記積演算を、m回繰り返し、α^m倍の積演算結果を演算するステップを、更に有することを特徴とする付記21のガロア体積演算処理方法。

0155

n台のデータストレージユニットの内、(n−1)/2より大きな最小の整数をsとする時に、i=1〜s+1番目のデータストレージユニットのデータのガロア体の元として、α^(i−1)を、i=s+2〜n番目のデータストレージユニットのデータのガロア体の元を、α^(−i+s+1)を、重み付けとして、積演算を実行するので、少ない繰り返し回数で、各データのガロア体の積演算が可能となる。

0156

10−1〜10−14データディスク装置
10−15〜10−16パリテイディスク装置
12RAIDコントローラ
14接続バス
16 ホスト

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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