(57)【特許請求の範囲】
【請求項１】
拡張マークアップ言語（XML）ドキュメントのリスト構造表現から、名前の要素及びタイプの要素のうち少なくとも１つを有する要素のセットを抽出し、
前記名前の要素及び前記タイプの要素を並列のレイアウトを有するプライマリリストに格納し、前記名前の要素は、第１のセットの連続したメモリ位置においてパック・ベクトルに格納され、前記タイプの要素は、第２のセットの連続したメモリ位置において前記パック・ベクトルに格納され、
前記プライマリリストに格納されない前記XMLドキュメントを記述する情報へのポインタをセカンダリリストに格納することを有する方法。
【請求項２】
前記プライマリリストの各要素が、前記セカンダリリストの３つのポインタに関連する、請求項１に記載の方法。
【請求項３】
前記プライマリリストに格納されない前記XMLドキュメントを記述する前記情報は、前記リスト構造において頻繁に使用されない要素を有する、請求項１に記載の方法。
【請求項４】
前記要素のセットは、少なくとも８個の要素を有する、請求項１に記載の方法。
【請求項５】
SIMD（Single  Instruction  Multiple  Data）命令を使用して前記第１及び第２のパック・ベクトルの検索を実行し、前記パック・ベクトルの前記要素のセットの各要素における合致について並列に検索することを更に有する、請求項１に記載の方法。
【請求項６】
前記SIMD命令は、並列に８バイトで動作する、請求項５に記載の方法。
【請求項７】
前記SIMD命令は、並列に１６バイトで動作する、請求項５に記載の方法。
【請求項８】
前記セカンダリリストは、可変サイズの要素を有する、請求項１に記載の方法。
【請求項９】
拡張マークアップ言語（XML）ドキュメントのリスト構造表現からタイプ及び名前の要素のセットを抽出するリスト−パック・ベクトル変換器と、
タイプの要素を第１のセットの連続したメモリ位置においてパック・ベクトルに格納し、名前の要素を第２のセットの連続したメモリ位置において前記パック・ベクトルに格納し、並列データ表現を生成するプライマリリストと、
前記プライマリリストを格納するメモリと
を有する装置。
【請求項１０】
前記要素のセットは、少なくとも８個の要素を有する、請求項９に記載の装置。
【請求項１１】
前記プライマリリストは、SIMD（Single  Instruction  Multiple  Data）命令により、前記パック・ベクトルの前記要素のセットの各要素における合致について並列に検索するために使用する並列レイアウトを有する、請求項９に記載の装置。
【請求項１２】
前記SIMD命令は、並列に８バイトで動作する、請求項１１に記載の装置。
【請求項１３】
前記SIMD命令は、並列に１６バイトで動作する、請求項１１に記載の装置。
【請求項１４】
前記名前の要素又は前記タイプの要素以外の可変サイズの要素を格納するセカンダリリストを更に有し、
前記可変サイズの要素は、前記リスト構造表現から抽出される、請求項９に記載の装置。
【請求項１５】
機械に、
XMLドキュメントのリスト構造表現から、名前の要素及びタイプの要素のうち少なくとも１つを有する要素のセットを抽出する手順と、
前記名前の要素を第１のセットの連続したメモリ位置においてパック・ベクトルに格納し、前記タイプの要素を第２のセットの連続したメモリ位置において前記パック・ベクトルに格納し、並列パック・ベクトル表現を生成する手順と
を実行させるためのプログラムを記録した機械読み取り可能な記憶媒体。
【請求項１６】
前記プログラムは、前記機械に、前記名前の要素又は前記タイプの要素以外の可変サイズの要素のセカンダリリストを前記パック・ベクトルに格納する手順を更に実行させ、
前記可変サイズの要素は、前記リスト構造表現から抽出される、請求項１５に記載の機械読み取り可能な記憶媒体。
【請求項１７】
前記プログラムは、前記機械に、前記パック・ベクトルの要素及び前記セカンダリリストの可変サイズの要素をインターリーブする手順を更に実行させる、請求項１６に記載の機械読み取り可能な記憶媒体。
【請求項１８】
前記プログラムは、前記機械に、SIMD（Single  Instruction  Multiple  Data）命令を使用して前記パック・ベクトルの検索を実行し、前記パック・ベクトルの前記要素のセットにおける合致について並列に検索する手順を更に実行させる、請求項１５に記載の機械読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、拡張マークアップ言語（XML：Extensible  Markup  Language）に関し、特にXMLドキュメントが検索される速度を改善することに関する。
【背景技術】
【０００２】
XMLは、ドキュメントをエンコードしてインターネットを介したデータの共有を容易にするために使用されるオープンスタンダードの汎用マークアップ言語である。XMLは、テキストとグラフィックスと音声とビデオとハイパーリンクとを組み込んだドキュメントをワールドワイドウェブ（World  Wide  Web）で生成するために使用されるHTMLと類似する。しかし、XMLは、符号化データの表示規格の代わりに論理構造を示すタグを使用することで、HTMLと異なる。
【０００３】
メモリ構造にXMLデータを表現する多くの異なる方法が存在する。例えば、XMLデータは、(1)W3C（World  Wide  Web  Consortium）により推奨される文字列、(2)アクセス速度を改善するためのセカンダリインデックスを備えた文字列、(3)リスト構造（各構造はXMLデータの何らかの側面を表す）又は(4)ツリー構造（各構造はXMLデータの何らかの側面を表す）として表され得る。
【０００４】
XMLデータの典型的な‘リスト構造（list  of  structures）’表現は、XMLデータの異なる特徴を表す構造タイプを使用し、ドキュメントの順序でこれらの構造をリストに接続する。典型的な構造タイプは、要素（element）、属性、文字データ、名前空間、処理命令及びコメントである。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
XMLデータの‘リスト構造’表現は、‘ツリー構造（trees
of structures）’表現に比べて比較的コンパクトであるという利点を有し、また、文字列より自動的に処理することが容易である。従って、遅い文字列処理と大きいメモリを必要とし得る‘ツリー構造’表現との間の良好な折衷案である。
【０００６】
XMLドキュメントの検索は、XMLデータにより公表された階層を使用して論理的に指定され得る。例えば、文字列での正規表現の使用と同様に、“//a/b/*”としてのW3C（World  Wide  Web  Consortium）のXPath（XML  Path  Language）シンタックスで表されるノード‘a’の子であるノード‘b’の子を見つける。しかし、リスト構造として格納されたデータでの階層検索モデルの使用は、構造間のポインタが検索空間を制限するために使用され得る“ツリー構造”として表されたデータの検索に比べて遅くなる可能性がある。従って、‘ツリー構造’表現は、XMLデータへのランダムアクセスを提供するが、‘リスト構造’は、順次アクセスのみを提供する。
【課題を解決するための手段】
【０００７】
本発明の方法は、
拡張マークアップ言語（XML）ドキュメントのリスト構造表現から要素のセットを抽出し、
前記要素のセットを連続したメモリ位置のパック・ベクトルに格納し、前記セットの要素が並列に検索されることを可能にすることを有することを特徴の１つとする。
【０００８】
また、本発明の装置は、
拡張マークアップ言語（XML）ドキュメントのリスト構造表現から要素のセットを抽出するリスト−パック・ベクトル変換器と、
前記要素のセットを連続したメモリ位置のパック・ベクトルに格納し、前記セットの要素が並列に検索されることを可能にするプライマリリストと
を有することを特徴の１つとする。
【０００９】
また、本発明の物は、
関連情報を有する機械アクセス可能媒体を含む物であって、
前記情報は、アクセスされたときに、機械に、
XMLドキュメントのリスト構造表現から要素のセットを抽出し、
前記要素のセットを連続したメモリ位置のパック・ベクトルに格納し、前記セットの要素が並列に検索されることを可能にすることを実行させることを特徴の１つとする。
【発明の効果】
【００１０】
本発明の実施例によれば、XMLドキュメントが検索される速度を改善することが可能になる。
【発明を実施するための最良の形態】
【００１１】
特許請求の範囲の対象の実施例の特徴は、図面を参照することで、以下の詳細な説明と共に明らかになる。図面において同様の参照符号は同様の部分を示す。
【００１２】
以下の詳細な説明は、特許請求の範囲の対象の例示的な実施例を参照して行われるが、その多くの代替、変更及び変形が当業者に明らかになる。従って、特許請求の範囲の対象は、広く見なされ、特許請求の範囲に記載のもののみにより規定されることを意図する。
【００１３】
図１Ａ及び１Ｂは、XMLドキュメントの例を示している。XMLドキュメントは、www.w3.orgで入手可能なW3C（World  Wide  Web  Consortium）の拡張マークアップ言語（XML：Extensible  Markup  Language）1.0で記述されるようにフォーマットされてもよい。図１Ａに示すように、XMLドキュメント100は、複数の要素102、104、106、108を含み、要素は、開始タグ‘<>’及び／又は終了タグ‘</>’を有する。要素102、104、106、108のタイプ（例えば‘a、b、c又はd’）は、開始タグと終了タグとの双方に含まれる。
【００１４】
図１Ａを参照すると、要素102は、名前（ns1）とURI（Uniform  Resource  Identifier）（uri）とを有する“xmlns”を使用して宣言された名前空間（namespace）を含む。すなわち、抽象的又は物理的リソースを特定するコンパクトな文字列を含む。要素102はまた、名前（a1）と値（attribute）とを有する属性を含む。
【００１５】
図１Ｂは、図１Ａに示すXMLドキュメント100を表すために使用され得るリスト構造150を示している。XMLデータの典型的な‘リスト構造’表現は、XMLデータの異なる特徴を表すために異なる構造タイプを使用し、ドキュメントの順序でこれらの構造をリストに接続する。典型的な構造タイプは、要素（例えば、開始要素、終了要素）、属性、名前空間、処理命令、コメント及び文字データ（例えばテキスト）である。
【００１６】
図１Ｂに示すように、図１Ａに示すXMLドキュメント100を表すリスト構造150は、要素タイプ（a、b、c及びd）と名前空間と属性とテキストとを含み、これらは、開始及び終了要素構造と名前空間構造と属性構造とテキスト構造とを含む構造152-1,...,150-15により表される。
【００１７】
従って、要素タイプ‘a’102（図１Ａ）（すなわち、<a  xmins:ns1=”namespace”  a1=”attribute”></a>は、開始要素構造152-1と名前空間構造152-2と属性構造152-3とテキスト構造152-4と終了要素構造152-15とにより表される。構造152-1は図１Ａに示すXMLドキュメント100の<a>に対応し、構造152-2はxmins:ns1=”namespace”に対応し、構造152-3はa1=”attribute”に対応し、構造152-4はnewline及びtabに対応し、構造152-15は”</a>”に対応する。
【００１８】
XMLドキュメントの“ツリー構造”表現の検索とXMLドキュメントの“リスト構造”表現の検索との間の性能差を低減するために、“ツリー構造”の構造は、構造間の直接のリンクを提供するオフセット又はポインタで拡張されてもよく、読み取られたメモリ量を低減するために２次記憶機構に頻繁にアクセスされないデータを移動することにより拡張されてもよい。階層検索はまた、複数の検索でアクセスコストが償却されるように併せて評価されてもよい。しかし、これらの技術が使用されたとしても、検索の性能は、XMLドキュメントの全てのデータを走査して特定のタイプの要素を見つけるのに要する時間により依然として制限される。
【００１９】
リスト構造の各構造の長さ（ビット数）が可変であるため、特定の要素タイプの検索は、合致を見つけるためにバイト毎にXMLドキュメントを通じた順次検索を必要とする。XMLドキュメントは、数千ものレコードを有し得るため、特定のレコードを求めてXMLドキュメントの開始から終了まで走査することは、非常に時間を消費する。
【００２０】
本発明の原理によれば、‘リスト構造’表現の走査速度は、SIMD（Single  Instruction  Multiple  Data）命令に適したフォーマットでXMLデータを格納することにより、検索処理を支援するように改善される。SIMD命令は、並列に複数の構造要素の検索を実行するために使用されてもよい。
【００２１】
SIMD（Single  Instruction  Multiple  Data）命令は、データセットの複数の要素で同じ動作を同時に実行する。単一のSIMD命令が複数の構造を検査することを可能にするために、データセットの要素は、典型的に“パック・ベクトル（packed  vector）”に格納される。すなわち、同じサイズの複数の要素を含むデータ構造である。バイト毎に各構造からデータをロードする代わりに、XMLデータは、SIMD命令により使用されるのに適したフォーマットで格納される。
【００２２】
実施例では、構造のセット（一式の構造）は、データがSIMD命令に容易にアクセス可能になるように、並列形式で配置される。図１Ａに示すXMLドキュメントの図１Ｂに示すリスト構造は、論理的に２つの部分：(1)並列のレイアウトでキー情報をグループ化するプライマリリスト及び(2)標準的な直列の形式での残りのデータのセカンダリリストに分割される。
【００２３】
図２は、SIMD命令実行モデルのブロック図である。SIMD命令は、１つの命令を使用して同時に複数のデータで動作することにより作動する。図２に示すように、第１のオペランド200はB[0]-B[7]のラベルの8バイトを有し、第２のオペランド202はA[0]-A[7]のラベルの8バイトを有する。同じ動作‘op’204が第１のオペランド200の１つのバイトと第２のオペランドの対応するバイトとで並列に実行され、R[0]-R[7]のラベルの８バイトを有する結果を作る。
【００２４】
図２は、本発明の原理に従って図１Ｂに示すリスト構造150から抽出されたプライマリリスト300の実施例を示している。構造タイプのセット（一式の構造タイプ）及び構造名のセット（一式の構造名）は、SIMD命令の長さに基づいて連続したメモリに格納される。このことにより、SIMD命令が図２に示すモデルと共に説明したように、プライマリリスト300で構造タイプのセット及び／又は構造名のセットを並列に検索するために使用されることが可能になる。
【００２５】
図３は、並列に64ビット（8バイト）で動作するSIMD命令により使用される8のエントリを有する各セットを仮定して、プライマリリスト200のレイアウトを示している。他の実施例では、セット毎に8のエントリより多く存在してもよく、少なく存在してもよい。図示の実施例では、プライマリリスト300はB[0]-B[31]のラベルの32バイトを有し、リスト構造表現150から抽出された構造名及びタイプを格納する。
【００２６】
プライマリリスト300は、XMLドキュメントでの検索を実行するAPI（Application  Programming  Interface）に応じて、リスト構造150として表されたXMLドキュメント100から抽出されてもよい。リスト構造表現150から要素を抽出してプライマリリスト300のパック・ベクトル表現を作るために、リスト−パック・ベクトル変換器（list  to  packed  vector  converter）が使用されてもよい。
【００２７】
プライマリリスト300に格納されたリスト構造表現150からの各要素は、構造のタイプ又は名前である。図示の実施例では、SIMD命令により使用されるオペランドのサイズは64ビット（すなわち、8バイト）である。従って、メモリの32（4×8バイト）の連続したバイトがプライマリリスト300に割り当てられ、図１Ｂのリスト構造表現150で示す15の構造に対応する構造タイプ及び構造名の全てを格納する。
【００２８】
最初の8バイトB[0]-B[7]（8の並列のエントリのセット）は、図１Ｂに示すリスト構造表現150の最初の8の構造152-1,...,152-8に対応する構造タイプを格納する。次の8バイトB[8]-B[15]は、図１Ｂに示すリスト構造表現150の最初の8の構造152-1,...,152-8に対応する構造名を格納する。バイトB[16]-B[23]は、図１Ｂに示すリスト構造表現150の構造152-9,...,152-15に対応する構造タイプを格納する。バイトB[24]-B[31]は、図１Ｂに示すリスト構造表現150の構造152-9,...,152-15に対応する構造名を格納する。
【００２９】
バイトB[0]-B[7]及びバイトB[16]-B[23]に格納された構造タイプは、開始要素（SE：start  element）タイプ構造、終了要素（EE：end  element）タイプ構造、名前空間（NS：namespace）タイプ構造、属性（A：attribute）タイプ構造、及びテキスト（T：Text）タイプ構造を含む。構造名は、a-b、ns1及びa1を含む。
【００３０】
構造タイプ及び構造名は、検索されるXMLドキュメント100で最も一般的なフィールドである。プライマリリスト300のキーデータ項目は、バイトB[0]-B[7]及びバイトB[16]-B[23]に格納された構造タイプであり、任意選択でバイトB[8]-B[15]及びバイトB[23]-B[31]に格納された構造名である。構造名について、表現は、XMLデータ表現に一般的な文字列を表す数による文字列の置換を可能にする。また、図示のように、各構造タイプ及び構造名は、バイトに符号化されてもよい。
【００３１】
プライマリリスト300は、SIMD命令を使用して特定の構造タイプ及び／又は構造名について検索されてもよい。例えば、特定のタイプの構造についてXMLドキュメント100を検索するために、プライマリリスト300のバイトB[0]-B[7]及びB[16]-B[23]で動作する２つのSIMD等価比較（equality  comparison）が使用されてもよい。
【００３２】
従って、図３に示すプライマリリスト300のパック・ベクトル表現は、並列に8バイトを検索することにより、論理的には8だけ走査コストを低減する。B[0]-B[7]及びB[24]-B[31]の範囲のバイトでSIMD等価演算を組み合わせることにより、より複雑な検索が実行されてもよい。
【００３３】
リスト構造表現150の全てのデータがプライマリリスト300に配置されてもよいが、頻繁に使用されない項目が存在し、特定の構造名又はタイプについてプライマリリスト200を検索する時間を増加させ得る。従って、実施例では、リスト構造表現150で頻繁に使用されない要素（例えばuri及び属性値）は、プライマリリスト300に含まれない。リスト構造表現150を通じて順次に検索する代わりに、XMLドキュメントはパック・ベクトル300のプライマリリスト及びセカンダリリストに格納される。
【００３４】
図３Ｂは、図１Ｂに示すリスト構造150から抽出されたセカンダリリスト302の実施例を示している。
【００３５】
通常の直列の方法で配置されたセカンダリリスト302は、プライマリリスト300の検索が合致を生じない場合に、頻繁に使用されない項目を検索するために、プライマリリストに加えて使用される。セカンダリリスト302は、データへのポインタ（DP）を格納する。図３Ｂに示す例では、23のポインタ（DP[0]-DP[23]）が示されている。各ポインタ（DP）は、システムのCPUが32ビット（4バイト）であるか64ビット（8バイト）であるかに応じて4又は8バイトを有してもよい。プライマリリスト300の各エントリ（B[0]-B[31]）は、セカンダリリスト（ストリーム）302の３つのエントリ（DP）に関連する。これらの３つのエントリは、プライマリリスト300に格納されていない頻繁にアクセスされないXMLデータを記述するために必要な更なる情報へのポインタを格納する。
【００３６】
第１のエントリは、レコード（構造）152-1,...,152-15のプレフィックス列（prefix  string）へのポインタを格納するためのものであり、第２のエントリは、名前列へのポインタ又はURI列へのポインタを格納するためのものであり、第３のエントリは、テキスト列へのポインタを格納するためのものである。全ての構造タイプが全ての３つのエントリを使用するとは限らないため、未使用のエントリは、図３Ｂに示すセカンダリリスト302で0として示されている。
【００３７】
図３Ｂに示す例では、Pnはレコード‘n’のプレフィックス列へのポインタを表し、Nnは‘n’の名前列へのポインタを表し、Unは‘n’のURI列へのポインタを表し、Tnはレコード‘n’のテキスト列へのポインタを表す。これらのフィールドは、プレフィックス、名前／URI及びテキストとして（すなわち、３つのエントリに）格納される。名前及びURIは、構造タイプが名前及びURIを必要としないため、第２のエントリを共有する。
【００３８】
セカンダリリスト302へのオフセットは、セカンダリリスト302のエントリのサイズ（例えば4又は8）の３倍だけプライマリリスト300の構造の位置を乗算することにより、特定の構造152-1,...,152-15について計算されてもよい。
【００３９】
他の実施例では、プライマリ及びセカンダリリストは、１つの構造にインターリーブされてもよく、及び／又は並列データ表現が他ではない入力の何らかの部分について選択的に使用されてもよい。いずれの場合でも、検索効率を改善するためのXMLデータの並列データレイアウトの原理が依然として当てはまる。
【００４０】
プライマリ及びセカンダリストリームをインターリーブするために、まず、固定数の構造がプライマリストリームフォーマットでエンコードされ、メモリに格納される。次に、同じ固定数の構造がセカンダリストリームフォーマットでエンコードされ、メモリの次の連続したメモリ位置に格納される。この処理は、全てのデータをエンコードするために必要な回数だけ繰り返される。図３Ｃは、プライマリリスト及びセカンダリリストがインターリーブされた図１Ｂに示すリスト構造150から抽出された構造310の実施例を示している。図３Ｃに示すように、プライマリリストは304及び308に格納され、セカンダリリストは306及び308に格納される。
【００４１】
図４は、図１Ｂに示すリスト構造表現150のリストから図２に示すプライマリリスト400を生成する方法の実施例を示すフローチャートである。
【００４２】
ブロック400において、リスト−パック・ベクトル変換器は、XMLドキュメント100を処理する要求を受信するのを待機する。XMLドキュメントを処理する要求は、XMLドキュメントを処理するAPI呼び出しから生じてもよい。JAXPは、JAVA（登録商標）でXMLドキュメントを処理するために使用されるAPI呼び出しの例である。要求が受信されると、処理はブロック402で継続する。受信されない場合、処理はブロック400で継続する。
【００４３】
ブロック402において、図１Ｂに示すリスト構造表現150として格納されているXMLドキュメント100は、Nの連続した構造から構造タイプを抽出するように解析される。例えば、図１Ｂを参照して、Nが8である場合、構造タイプは、第１の構造タイプが開始要素（SE）タイプであり第８の構造タイプが終了要素（EE）であるリスト構造表現の最初の8の構造152-1,...,152-8から抽出される。処理はブロック404で継続する。
【００４４】
ブロック404において、Nの構造タイプがリスト構造表現から抽出されると、構造タイプは、プライマリリスト300の連続したメモリ位置に格納される。処理はブロック406で継続する。
【００４５】
ブロック406において、構造タイプがNの要素のそれぞれから抽出された後に、リスト構造表現150は、構造タイプが抽出されたNの構造に対応して構造毎に１つずつ、Nの構造名について解析される。処理はブロック408で継続する。
【００４６】
ブロック408において、構造名がリスト構造表現から抽出されると、構造名は、第Nの構造タイプが格納された後のメモリ位置から始まり、プライマリリスト200の連続したメモリ位置に格納される。１つの位置は、構造に関連する構造名が存在するか否かに拘らず、Nの構造のそれぞれの構造タイプを格納するために確保される。例えば、図４に示すように、構造152-4が構造名を有さない場合であっても、バイトB[11]は、構造152-4に関連する構造名を格納するために確保される。処理はブロック410で継続する。
【００４７】
ブロック410において、リスト−パック・ベクトル変換器は、リスト構造表現150に処理すべき他の構造が存在するか否かを決定する。存在する場合、処理はブロック402で継続し、リスト構造表現150の残りの構造を処理する。存在しない場合、処理はブロック412で継続する。
【００４８】
ブロック412において、プライマリリスト300がリスト構造表現150から生成された後に、プライマリリスト400は、特定の構造タイプ及び／又は構造名について検索されてもよい。プライマリリストのパック・ベクトルの8バイトは、SIMD命令を使用した合致を検索するために、バイトで並列に比較されてもよい。例えば、PCMPEQB(compare  packed  bytes  for  equal)命令のようなx86  MMX比較命令は、目的オペランドと源オペランドとのパック・バイトの等価について比較を実行する。処理はブロック400で継続し、他の要求を待機する。
【００４９】
図５は、XMLドキュメント528のリスト構造表現からプライマリリスト542を生成するリスト−パック・ベクトル変換器（list  to  packed  vector  converter）の実施例を含むシステムのブロック図である。
【００５０】
システム500は、プロセッサ501と、メモリコントローラハブ（MCH：Memory  Controller  Hub）502と、入力／出力（I/O）コントローラハブ（ICH：Input/Output  Controller  Hub）504とを含む。MCH502は、プロセッサ501とメモリ504との間の通信を制御するメモリコントローラ506を含む。プロセッサ501及びMCH502はシステムバス516で通信する。
【００５１】
プロセッサ501は、シングルコアIntel  Pentium（登録商標）  IVプロセッサ、シングルコアIntel  Celeronプロセッサ、Intel  XScaleプロセッサ、若しくはマルチコアプロセッサ（Intel  Pentium（登録商標）  D、Intel  Xeonプロセッサ又はIntel  Core  Duoプロセッサ等）又は他の種類のプロセッサのようなSSE（Streaming  SIMD  Extensions）をサポートする複数のプロセッサのうち何れか１つでもよい。
【００５２】
メモリ503は、DRAM（Dynamic  Random  Access  Memory）、SRAM（Static  Random  Access  Memory）、SDRAM（Synchronized  Dynamic  Random  Access  Memory）、DDR2（Double  Data  Rate  2）RAM若しくはRDRAM（Rambus  Dynamic  Random  Access  Memory）又は他の種類のメモリでもよい。
【００５３】
ICH504は、DMI（Direct  Media  Interface）のような高速チップ間相互接続514を使用してMCH502に結合されてもよい。DMIは、２つの片方向レーンを介して2ギガビット／秒の同時転送レートをサポートする。
【００５４】
ICH504は、ICH504に結合された少なくとも１つの記憶装置512との通信を制御する記憶入力／出力（I/O）コントローラ510を含んでもよい。例えば、記憶装置は、ディスクドライブ、DVD（Digital  Video  Disk）ドライブ、CD（Compact  Disk）ドライブ、RAID（Redundant  Array  of  Independent  Disks）、テープドライブ又は他の記憶装置でもよい。ICH504は、SAS（Serial  Attached  Small  Computer  System  Interface）又はSATA（Serial  Advanced  Technology  Attachment）のようなシリアルストレージプロトコルを使用して、ストレージプロトコル相互接続518で記憶装置512と通信してもよい。
【００５５】
ICH504はまた、少なくとも１つの他のシステム536とのインターネット550での通信を制御するNIC（Network  Interface  Communications）コントローラ526を含んでもよい。メモリ508は、XMLドキュメント528のリスト構造表現からプライマリリスト532を生成するリスト−パック・ベクトル変換器530を格納してもよい。XMLドキュメント528は、RAIDアレイ512又はインターネット536を介してアクセス可能な他のシステム528に格納されてもよい。パック・ベクトル変換器530は、メモリ508に格納され得るXMLドキュメント528のリスト構造表現536で動作する。パック・ベクトル変換器530は、本発明の原理に従ってXMLドキュメント528のリスト構造表現からプライマリリスト534及びセカンダリリスト532を生成する。
【００５６】
本発明の実施例は64ビットのSIMD命令（すなわち、並列に64ビット（8バイト）で動作するSIMD命令）について説明した。しかし、本発明は、並列に64ビットで動作することに限定されない。本発明の実施例は、並列に64ビットより多くで（例えば並列に16バイトで動作するために128ビットのレジスタを使用して）動作するSIMD命令を使用してもよい。
【００５７】
本発明の実施例に関する方法は、コンピュータ使用可能媒体を含むコンピュータプログラムプロダクトに具現されてもよいことが、当業者に明らかである。例えば、このようなコンピュータ使用可能媒体は、CD-ROM（Compact  Disk  Read  Only  Memory）ディスク又は通常のROM装置のような読み取り専用メモリ装置で構成されてもよく、格納されたコンピュータ可読プログラムコードを有するコンピュータディスクで構成されてもよい。
【００５８】
本発明の実施例について特に実施例を参照して図示及び説明したが、特許請求の範囲に含まれる本発明の実施例の範囲を逸脱することなく、形式及び詳細で様々な変更が行われてもよいことが当業者にわかる。
【図面の簡単な説明】
【００５９】
【図１Ａ】XMLドキュメントの例
【図１Ｂ】XMLドキュメントの例
【図２】SIMD命令実行モデルのブロック図
【図３Ａ】本発明の原理に従って図１Ｂに示すリスト構造から抽出されたプライマリリストの実施例
【図３Ｂ】図１Ｂに示すリスト構造から抽出されたセカンダリリストの実施例
【図３Ｃ】プライマリ及びセカンダリリストがインターリーブされた図１Ｂに示すリスト構造から抽出された構造の実施例
【図４】図１Ｂに示すリスト構造から図３に示すプライマリリストを生成する方法の実施例を示すフローチャート
【図５】XMLドキュメントのリスト構造表現からプライマリリストを生成するリスト−パック・ベクトル変換器の実施例を含むシステムのブロック図
【符号の説明】
【００６０】
501  ホスト中央処理装置（CPU）
502  メモリコントローラハブ（MCH）
504  入力／出力コントローラハブ（ICH）
506  メモリコントローラ
508  メモリ
510  記憶入力／出力コントローラ
512  RAID配列
526  ネットワークインタフェースコントローラ
528  XMLドキュメント
530  変換器
532  セカンダリリスト
534  プライマリリスト
536  リスト構造
550  インターネット
558  XMLドキュメント
【図１Ａ】
0004896950.tif 000002
【図１Ｂ】
0004896950.tif 000003
【図２】
0004896950.tif 000004
【図３Ａ】
0004896950.tif 000005
【図３Ｂ】
0004896950.tif 000006
【図３Ｃ】
0004896950.tif 000007
【図４】
0004896950.tif 000008
【図５】
0004896950.tif 000009