(57)【特許請求の範囲】
【請求項１】
入力データストリームをセグメント化するためのシステムであって、
プロセッサを備え、前記プロセッサは、
入力データストリームを複数のデータサブストリームへ分割し、これにより、前記複数のデータサブストリームの各々は、少なくとも、先頭に前記複数のデータサブストリームのうち連続する先行のデータサブストリームの末尾との重複部分を有する、又は、末尾に前記複数のデータサブストリームのうち連続する後続のデータサブストリームの先頭との重複部分を有し、
前記プロセッサの複数の処理パイプラインの１つにおいて、前記複数のデータサブストリームを各々、同一のセグメント化技法を使用して並行してセグメント化することにより、複数のセグメント化データサブストリームを並行して生成し、
前記複数のデータサブストリームのうち、各２つの連続するデータサブストリームの前記重複部分における少なくとも１つの同一のセグメントを識別し、識別された前記同一のセグメントに従って前記複数のセグメント化データサブストリームの各々のシーケンシングを同期することによって、前記複数のセグメント化データサブストリームを結合して、セグメント化データストリームを生成するよう適合される、
システム。
【請求項２】
前記プロセッサは、単一命令多重データ（ＳＩＭＤ）プロセッサである、請求項１に記載のシステム。
【請求項３】
前記プロセッサは、前記複数のデータサブストリームの各々の連続するデータ項目の複数のシーケンスの各々にわたって適用されるローリングシーケンスのためのローリングハッシュ値を計算すること、及び、前記ローリングハッシュ値が少なくとも１つのセグメント化基準に準拠するとき、前記複数のシーケンスの各々を可変サイズセグメントとして指定することによって、前記複数のデータサブストリームの各々をセグメント化するよう適合され、前記ローリングシーケンスは、それぞれのシーケンスの連続するデータ項目のサブセットを含む、請求項１又は２に記載のシステム。
【請求項４】
前記複数のシーケンスの各々は、予め定められた最小数の前記連続するデータ項目を含む、請求項３に記載のシステム。
【請求項５】
前記プロセッサは、前記ローリングハッシュ値が前記少なくとも１つのセグメント化基準に準拠していることを検出する前に、少なくとも１つの大きいシーケンスの前記連続するデータ項目の数が、予め定められた最大値を超える場合に、前記複数のシーケンスのうち前記少なくとも１つの大きいシーケンスを前記可変サイズセグメントとして指定するよう適合される、請求項３または４に記載のシステム。
【請求項６】
前記プロセッサは、前記同期が失敗した場合に、前記入力データストリームを順次にセグメント化するよう適合される、請求項１から５のいずれか一項にに記載のシステム。
【請求項７】
入力データストリームをセグメント化するための方法であって、
プロセッサにより、入力データストリームを複数のデータサブストリームへ分割する段階であって、これにより、前記複数のデータサブストリームの各々は、少なくとも、先頭に前記複数のデータサブストリームのうち連続する先行のデータサブストリームの末尾との重複部分を有する、又は、末尾に前記複数のデータサブストリームのうち連続する後続のデータサブストリームの先頭との重複部分を有する、段階と、
前記プロセッサの複数の処理パイプラインの１つにおいて、前記複数のデータサブストリームを各々、同一のセグメント化技法を使用して並行してセグメント化することにより、複数のセグメント化データサブストリームを並行して生成する段階と、
前記プロセッサにより、前記複数のデータサブストリームのうち、各２つの連続するデータサブストリームの前記重複部分における少なくとも１つの同一のセグメントを識別し、識別された前記同一のセグメントに従って前記複数のセグメント化データサブストリームの各々のシーケンシングを同期することによって、前記複数のセグメント化データサブストリームを結合して、セグメント化データストリームを生成する段階と
を備える、
方法。
【請求項８】
前記プロセッサが、前記複数のデータサブストリームの各々の連続するデータ項目の複数のシーケンスの各々にわたって適用されるローリングシーケンスのためのローリングハッシュ値を計算すること、及び、前記ローリングハッシュ値が少なくとも１つのセグメント化基準に準拠するとき、前記プロセッサが、前記複数のシーケンスの各々を可変サイズセグメントとして指定することによって、複数のデータサブストリームの各々がセグメント化され、前記ローリングシーケンスは、それぞれのシーケンスの連続するデータ項目のサブセットを含む、請求項７に記載の方法。
【請求項９】
前記複数のシーケンスの各々は、予め定められた最小数の前記連続するデータ項目を含む、請求項８に記載の方法。
【請求項１０】
前記ローリングハッシュ値が前記少なくとも１つのセグメント化基準に準拠していることを検出する前に前記少なくとも１つの大きいシーケンスの前記連続するデータ項目の数が、予め定められた最大値を超える場合に、前記プロセッサが、前記複数のシーケンスのうち少なくとも１つの大きいシーケンスを前記可変サイズセグメントとして指定する、請求項８または９に記載の方法。
【請求項１１】
前記同期が失敗する場合に、前記プロセッサが、前記入力データストリームを順次にセグメント化する、請求項７から１０のいずれか一項に記載の方法。
【請求項１２】
請求項７から１１のいずれか一項に記載の方法をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【背景技術】
【０００１】
本発明は、そのいくつかの実施形態において、入力データストリームのセグメント化に関し、より具体的には、これに限定されないが、ベクトル処理を使用して並列にセグメント化される複数のデータサブストリームへ入力データストリームを分割することによる、入力データストリームのセグメント化に関する。
【０００２】
情報時代である現代において、保存される、及び／又は、複数の場所の間で伝送される必要のあるデータの量は、急速に増加している。膨大な量のデータにより、データを保存するためのストレージ領域、及び／又は、それを伝送するためのネットワーク帯域幅に関して、費用及び／又は複雑性の大きな課題が発生し得る。
【０００３】
保存される、及び／又は、伝送されるデータの量を低減するべく一般的に使用される１つの解決策は、冗長データを除去することによってデータ量を低減する方法である、データ重複排除（「インテリジェント圧縮」又は「単一インスタンスストレージ」と呼ばれることも多い）である。ファイル重複排除のための方法は複数あるが、ブロック重複排除は、データ圧縮に関して、より良い結果をもたらし得る。ブロック重複排除では、データストリームのデータセグメント（ブロック）のうち、１つの一意のインスタンスのみが実際に保持され、一方で、既に保持されているデータセグメントと同一である冗長なデータセグメントは、保持されているデータセグメントのコピーに対するポインタで置き換えられる。ブロック重複排除は、１又は複数のデータセグメント（ブロック）の一意のインスタンスを識別するべく、例えば、データファイル、メディアファイル、ストリームデータなど複数のデータタイプを含み得るデータストリームを処理する。例えば、ラビン‐カープ法ローリングハッシュ及び／又はＢｕｚｈａｓｈなどのハッシュアルゴリズムを使用して、各セグメントについて、一意の数値（ハッシュ値）が生成される。各セグメントについて生成されたハッシュ値は、以前のセグメントについて生成された既存のハッシュ値と比較され、ハッシュ値が既存のハッシュ値に等しい場合、セグメントは保持されず、むしろ既存のセグメントのコピーに対するポインタで置き換えられる。更に、セグメントが更新された場合、変更されたデータのみが保持され得て、一方で、大量のセグメントを含み得る、残りの未変更のデータは、保持されない。
【０００４】
主要な課題の１つは、セグメントのデータコンテンツに対する変更によってセグメントが受ける影響をできるだけ小さくするように、データストリームを効果的にセグメント化することである。ローリングハッシュ技術は、業界で知られているように、データストリームのセグメント化に使用され得る。ローリングハッシュを使用して、データストリーム内のデータのシーケンスをシフトするためのハッシュ値が計算される（各ローリングシーケンスにおいて、最後のデータ項目は省略され、新しいデータ項目が挿入される）。計算されたハッシュ値は、予め定められた１又は複数のセグメント化基準に準拠しているかどうかチェックされる。準拠していることが確認された場合、それぞれのローリングシーケンスの始点は、セグメントの境界、又は、カット点として指定される。
【発明の概要】
【０００５】
本発明の第１態様によれば、入力データストリームをセグメント化するためのシステムであって、プロセッサを備え、プロセッサは、入力データストリームを複数のデータサブストリームへ分割し、これにより、複数のデータサブストリームの各々は、複数のデータサブストリームのうち連続するデータサブストリームとの重複部分を有し、プロセッサの複数の処理パイプラインの１つにおいて、複数のデータサブストリームの各々を並行してセグメント化することにより、複数のセグメント化データサブストリームを並行して生成し、複数のデータサブストリームのうち、各２つの連続するデータサブストリームの重複部分における少なくとも１つの重複するセグメントに従って、複数のセグメント化データサブストリームの各々のシーケンシングを同期することによって、複数のセグメント化データサブストリームを結合してセグメント化データストリームを生成するように適合される、システムが提供されている。
【０００６】
並行という用語は、それにより、期間の重複という意味を有し、また、同時（例えば、同一の時間に発生する）の意味も含む。
【０００７】
本発明の第１態様の第１実装形態自体によると、プロセッサは、単一命令多重データ（ＳＩＭＤ）プロセッサである。
【０００８】
第１態様の第２実装形態自体によると、又は、第１態様の第１実装形態によると、プロセッサは、複数のデータサブストリームの各々の連続するデータ項目の複数のシーケンスの各々にわたって適用されるローリングシーケンスのローリングハッシュ値を計算し、ローリングハッシュ値が少なくとも１つのセグメント化基準に準拠するときに、複数のシーケンスの各々を可変サイズセグメントとして指定することにより、複数のデータサブストリームの各々をセグメント化するよう適合され、ローリングシーケンスは、それぞれのシーケンスの連続するデータ項目のサブセットを含む。
【０００９】
第１態様の第３実装形態自体によると、又は、第１態様の第１又は第２実装形態のいずれかによると、複数のシーケンスの各々は、予め定められた最小数の連続するデータ項目を含む。
【００１０】
第１態様の第４実装形態自体によると、又は、第１態様の第１‐第３実装形態のいずれかによると、プロセッサは、ローリングハッシュ値が少なくとも１つのセグメント化基準に準拠していることを検出する前に少なくとも１つの大きいシーケンスの連続するデータ項目の数が予め定められた最大値を超える場合に、複数のシーケンスのうち少なくとも１つの大きいシーケンスを、可変サイズセグメントとして指定するよう適合される。
【００１１】
第１態様の第５実装形態自体によると、又は、第１‐第４実装形態のいずれかによると、プロセッサは、同期が失敗した場合、入力データストリームを順次にセグメント化するよう適合される。
【００１２】
本発明の第２態様によると、入力データストリームを複数のデータサブストリームへ分割する段階であって、これにより、複数のデータサブストリームの各々は、複数のデータサブストリームのうち連続するデータサブストリームとの重複部分を有する、段階と、プロセッサの複数の処理パイプラインの１つにおいて、複数のデータサブストリームを各々、並行してセグメント化することにより、複数のセグメント化データサブストリームを並行して生成する段階と、複数のデータサブストリームのうち、各２つの連続するデータサブストリームの重複部分における、少なくとも１つの重複するセグメントに従って、複数のセグメント化データサブストリームの各々のシーケンシングを同期することによって、複数のセグメント化データサブストリームを結合してセグメント化データストリームを生成する段階とを備える、入力データストリームをセグメント化するための方法が提供されている。
【００１３】
本発明の第２態様の第１実装形態自体によると、複数のデータサブストリームの各々は、複数のデータサブストリームの各々の連続するデータ項目の複数のシーケンスの各々にわたって適用されるローリングシーケンスのためのローリングハッシュ値を計算すること、及び、ローリングハッシュ値が少なくとも１つのセグメント化基準に準拠するとき、複数のシーケンスの各々を可変サイズセグメントとして指定することによってセグメント化され、ローリングシーケンスは、それぞれのシーケンスの連続するデータ項目のサブセットを含む。
【００１４】
第２態様の第２実装形態自体によると、又は、第２態様の第１実装形態によると、複数のシーケンスの各々は、予め定められた最小数の連続するデータ項目を含む。
【００１５】
第２態様の第３実装形態自体によると、又は、第２態様の第１又は第２実装形態のいずれかによると、ローリングハッシュ値が少なくとも１つのセグメント化基準に準拠していることを検出する前に、少なくとも１つの大きいシーケンスの連続するデータ項目の数が、予め定められた最大値を超える場合に、複数のシーケンスのうち少なくとも１つの大きいシーケンスは、可変サイズセグメントとして指定される。
【００１６】
第２態様の第４実装形態自体によると、又は、第２態様の第１実装形態から第３実装形態のいずれかによると、同期が失敗した場合、入力データストリームは、順次セグメント化される。
【図面の簡単な説明】
【００１７】
本発明のいくつかの実施形態は、本明細書において、単に例示として、添付の図面を参照しながら説明される。ここで、図面を詳しく具体的に参照するが、示されている具体的事項は、例であり、本発明の実施形態を例示的に説明することを目的としていることに留意されたい。これに関して、当業者であれば、図面に関する説明から、本発明の実施形態がどのように実施され得るか明らかとなるであろう。図面には以下の図が含まれる。
【００１８】
【図１】本発明のいくつかの実施形態に係る、ベクトル処理を使用して並列にセグメント化される複数のデータサブストリームへ入力データストリームを分割することによって入力データストリームをセグメント化する例示的なシステムの概略図である。
【００１９】
【図２】本発明のいくつかの実施形態に係る、ベクトル処理を使用して並列にセグメント化される複数のデータサブストリームへ入力データストリームを分割することによって入力データストリームをセグメント化する例示的な処理のフローチャートである。
【００２０】
【図３】本発明のいくつかの実施形態に係る、入力データストリームを複数のサブストリームへ分割する例示的な処理の概略図である。
【００２１】
【図４】本発明のいくつかの実施形態に係る、複数のセグメント化データサブストリームを結合して、セグメント化データストリームを生成する例示的な処理の概略図である。
【００２２】
【図５】ローリングハッシュセグメント化を使用して入力データストリームをセグメント化する例示的な処理の概略図である。
【００２３】
【図６】本発明のいくつかの実施形態に係る、ローリングハッシュセグメント化を使用して、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００２４】
【図７Ａ】本発明のいくつかの実施形態に係る、第１時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００２５】
【図７Ｂ】本発明のいくつかの実施形態に係る、第２時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００２６】
【図７Ｃ】本発明のいくつかの実施形態に係る、第３時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００２７】
【図７Ｄ】本発明のいくつかの実施形態に係る、第４時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００２８】
【図７Ｅ】本発明のいくつかの実施形態に係る、第５時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００２９】
【図７Ｆ】本発明のいくつかの実施形態に係る、第６時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００３０】
【図７Ｇ】本発明のいくつかの実施形態に係る、第７時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００３１】
【図７Ｈ】本発明のいくつかの実施形態に係る、第８時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００３２】
【図７Ｉ】本発明のいくつかの実施形態に係る、第９時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００３３】
【図７Ｊ】本発明のいくつかの実施形態に係る、第１０時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００３４】
【図７Ｋ】本発明のいくつかの実施形態に係る、第１１時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００３５】
【図７Ｌ】本発明のいくつかの実施形態に係る、第１２時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【００３６】
【図７Ｍ】本発明のいくつかの実施形態に係る、第１３時点における、並行して複数のデータサブストリームを並列にセグメント化する例示的な処理の概略図である。
【発明を実施するための形態】
【００３７】
本発明は、そのいくつかの実施形態において、入力データストリームのセグメント化に関し、より具体的には、ベクトル処理を使用して並列にセグメント化される複数のデータサブストリームへ入力データストリームを分割することによる、入力データストリームのセグメント化に関するが、これに限定されない。
【００３８】
本発明は、冗長な（重複した）データセグメントを除去することにより、例えば、データファイル、メディアファイル、ストリーミングデータなどの入力データストリームのデータ量を低減するべく、入力データストリームに適用される重複排除処理の一部として、ベクトル処理を使用して入力データストリームをセグメント化するためのシステム及び方法を提示する。入力データストリームのデータ量を低減するための重複排除処理は、入力データストリームの保存及び／又は伝送に必要なストレージ領域及び／又はネットワーク帯域幅を低減するべく実行される。セグメント化は、入力データストリームを複数のデータサブストリームへ分割することと、例えば単一命令多重データ（ＳＩＭＤ）プロセッサなどのベクトルプロセッサの複数の処理パイプラインの１つによって、データサブストリームを各々、並列にセグメント化することと、セグメント化データサブストリームを結合して、セグメント化データストリームを形成することとによって行われる。各データサブストリームが後続のデータサブストリームとのデータの重複部分を有するように、入力データストリームは、複数のデータサブストリームへ分割される。全てのデータサブストリームのセグメント化が完了した後で、あらゆる２つのデータサブストリーム間の重複部分におけるデータセグメント（ブロック）を同期することで、データサブストリームは互いに結合される。処理パイプラインによって、同一のセグメント化技法及び／又はセグメント化基準がデータサブストリームへ適用されるので、重複部分におけるセグメント化は同一であり、従って、データサブストリームを互いに同期させるのに使用され得ることが予想される。データサブストリームの各々のセグメント化は、例えば、データサブストリームに沿ってシフトされるローリングシーケンスのための一意のハッシュ値の計算、及び、ハッシュ値と１又は複数のセグメント化基準との比較など、複数のセグメント化技法のうち１又は複数を使用して実行され得る。ハッシュ値は、例えば、ラビン‐カープローリングハッシュ又はＢｕｚｈａｓｈなどの複数のハッシュアルゴリズムのうち１又は複数によって計算され得る。
【００３９】
任意で、データサブストリームのうち１つ又は複数の同期が失敗した場合、入力データストリームは、順次にセグメント化される。
【００４０】
ベクトル処理アーキテクチャの複数の処理パイプラインを使用する並行セグメント化は、既存の順次セグメント化方法と比較して、大きな利点をもたらし得る。ベクトル処理技術は、例えば、現代のプロセッサで利用可能な処理パイプラインの数、並列に処理され得るデータ項目の数、及び／又は、プロセッサの処理能力など、多くの側面において、急速に発展している。入力データストリームの効率的なセグメント化は、重複排除処理全体の有効性に大きく貢献し得るが、長い時間がかかる、及び／又は、プロセッサに負荷がかかる、重複排除処理の動作のうちの１つであり得る。入力シーケンスのデータ項目は、互いに独立していると見なされ得るので、入力データストリームは、例えば、ＳＩＭＤプロセッサ、及び／又は、エンジンなどのベクトル処理技術の利点を十分に活用して、分割及び並列に処理され得る。ベクトルプロセッサを使用することによる入力データストリームの処理は、現在のセグメント化方法によって利用されている順次セグメント化と比較して、セグメント化時間を大幅に低減し得る。セグメント化時間が大幅に低減すると、重複排除処理全体は大幅に短縮され得て、おそらく、データ伝送及び／又はデータ保存動作におけるボトルネックを除去し得る。
【００４１】
更に、ベクトル処理アーキテクチャの複数の処理パイプラインを使用する並行セグメント化は、既存の順次セグメント化方法によって使用されている標準のセグメント化技法を適用する。これにより、セグメント化処理における後方互換性を可能にし得て、従って、重複排除処理中に適用される他の動作及び／又はアルゴリズムに対して、いかなる影響も発生しない。更に、本発明に示される、並行セグメント化処理によって使用されるセグメント化技法の後方互換性は、並行セグメント化処理を順次セグメント化処理と組み合わせることを可能にし得て、それにより、入力データストリームのいくつかの部分が並行して処理される一方、他の部分が順次に処理され得る。
【００４２】
本発明の少なくとも１つの実施形態を詳細に説明する前に、本発明は必ずしも、その適用において、以下の記載に説明されている、並びに／又は、図面及び／若しくは例に示されている、構造の詳細、及び、コンポーネント及び／又は方法の構成に限定されるものではないことを理解されたい。本発明では、他の実施形態も、様々な手段で実施又は実行されることが可能である。
【００４３】
本発明は、システム、方法、及び／又は、コンピュータプログラムプロダクトであり得る。コンピュータプログラムプロダクトは、プロセッサに本発明の態様を実施させるためのコンピュータ可読プログラム命令を自身に含む１又は複数のコンピュータ可読記憶媒体を含み得る。
【００４４】
コンピュータ可読記憶媒体は、命令実行デバイスによって使用される命令を保持及び保存できる有形のデバイスであり得る。コンピュータ可読記憶媒体は、例えば、電子ストレージデバイス、磁気ストレージデバイス、光学ストレージデバイス、電磁ストレージデバイス、半導体ストレージデバイス、又は、上に挙げたものの好適な任意の組み合わせであり得るが、これらに限定されない。
【００４５】
本明細書に記載されたコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体から、それぞれのコンピューティング／処理デバイスへダウンロードでき、又は、例えば、インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、及び／又は、無線ネットワークなどのネットワークを介して、外部コンピュータ又は外部ストレージデバイスへダウンロードできる。 
【００４６】
コンピュータ可読プログラム命令は、ユーザのコンピュータ上で全て実行され得るか、スタンドアロンのソフトウェアパッケージとして部分的にユーザのコンピュータ上で実行され得るか、部分的にユーザのコンピュータ上で、部分的にリモートコンピュータ上で実行され得るか、又は、リモートコンピュータ又はサーバ上で全て実行され得る。後者のシナリオにおいて、リモートコンピュータは、ローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを介してユーザのコンピュータに接続されてもよく、又は接続は、外部コンピュータ（例えば、インターネットサービスプロバイダを使用するインターネットを介して）に対して行われてもよい。いくつかの実施形態において、例えば、プログラマブル論理回路、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、又は、プログラマブルロジックアレイ（ＰＬＡ）を含む電子回路は、本発明の態様を実行するべく、コンピュータ可読プログラム命令の状態情報を利用して電子回路を個人設定することにより、コンピュータ可読プログラム命令を実行し得る。
【００４７】
本発明の態様は、本明細書において、発明の実施形態に係る方法、機器（システム）、及び、コンピュータプログラムプロダクトのフローチャート及び／又はブロック図を参照して説明されている。フローチャート及び／又はブロック図の各ブロック、並びに、フローチャート及び／又はブロック図のブロックの組み合わせは、コンピュータ可読プログラム命令によって実装され得ることを理解すべきである。
【００４８】
図面内のフローチャート及びブロック図は、本発明の様々な実施形態に係る、システム、方法、及び、コンピュータプログラムプロダクトのあり得る実装のアーキテクチャ、機能、及び、動作を示す。これに関して、フローチャート又はブロック図における各ブロックは、指定された論理機能を実装するための１又は複数の実行可能命令を含む、命令のモジュール、セグメント、又は、部分を表し得る。いくつかの代替的な実装において、ブロック内に示されている機能は、図に示されている順序とは異なる順序で発生し得る。例えば、連続して示される２つのブロックは、実際には、実質的に並行して実行されてもよく、又は、それらのブロックは時折、関連する機能に応じて、逆の順番で実行されることがあってもよい。また、ブロック図及び／又はフローチャートの各ブロック、並びに、ブロック図及び／又はフローチャートのブロックの組み合わせは、指定された機能若しくは動作を実行する、又は、特定用途向けハードウェア及びコンピュータ命令の組み合わせを実施する、特定用途向けハードウェアベースシステムによって実装され得ることに留意すべきである。
【００４９】
ここで、図１を参照する。図１は、本発明のいくつかの実施形態に係る、ベクトル処理を使用して並列にセグメント化される複数のデータサブストリームへ入力データストリームを分割することにより、入力データストリームをセグメント化する例示的なシステムの概略図である。システム１００は、入力データストリーム１２０を受信及び／又は指定するための、及び／又は、セグメント化データストリーム１３０を出力するための、入力／出力（Ｉ／Ｏ）インタフェース１０２と、入力データストリーム１２０をセグメント化してセグメント化データストリーム１３０を生成するための複数の処理パイプライン１０６を有するプロセッサ１０４と、プログラム記憶部１０８とを備える。入力データストリーム１２０は、例えば、データファイル、メディアファイル、ストリーミングデータなど、１又は複数の形式で受信され得る。入力データストリーム１２０は、例えば、バイト、ワード、ダブルワード、及び／又は、ピクセルなど、ストリームとして順番に並べられ得る複数のデータ項目を含む。Ｉ／Ｏインタフェース１０２は、例えば、ネットワークインタフェース、メモリインタフェース、及び／又は、ストレージインタフェースなど、１又は複数のインタフェースを有し得る。Ｉ／Ｏインタフェース１０２は、例えば、メモリデバイス及び／又はストレージデバイスなどへデータストリーム１２０及び／又は１３０を取得及び／又は保存するべく、ネットワークを介して、データストリーム１２０及び／又は１３０を受信及び／又は送信するのに使用され得る。プロセッサ１０４は、各々が１又は複数のコアを含む１又は複数のプロセッサを有し得る。プロセッサ１０４は更に、複数の処理パイプライン１０６などのベクトル処理機能を有する。処理パイプライン１０６は、例えば、マルチプロセッサ、マルチコア、ベクトルプロセッサ、並びに／又は、ＳＩＭＤプロセッサ及び／若しくはＳＩＭＤエンジンなど、各々がデータを処理できる、複数の独立した実行パイプラインに対応する。ＳＩＭＤエンジンは、プロセッサ１０４の単一の命令で、複数のデータ項目を並行して処理できる複数の処理パイプライン１０６を含む。プログラム記憶部１０８は、例えば、ハードドライブ、フラッシュアレイなど、１又は複数の不揮発性永続的ストレージデバイスを有し得る。
【００５０】
また、ここで図２を参照する。図２は、本発明のいくつかの実施形態に係る、ベクトル処理を使用して並列にセグメント化される複数のデータサブストリームへ入力データストリームを分割することにより、入力データストリームをセグメント化するための例示的な処理のフローチャートである。セグメント化処理２００は、システム１００などのシステムによって実行され得る。処理２００は、並行して複数の処理パイプライン１０６によって並列にセグメント化され、結合されてセグメント化データストリーム１３０などのセグメント化データストリームを生成する、複数のデータサブストリームへ入力データストリーム１２０を分割することによる、入力データストリーム１２０のセグメント化に適用される。
【００５１】
セグメント化処理２００は、プロセッサ１０４及び／又は処理パイプライン１０６によって実行される複数のプログラム命令を含む、例えば、コーディネータ１１０及び／又はワーカ１１２などの、プログラム記憶部１０８からの１又は複数のソフトウェアモジュールによって実行され得る。任意で、ワーカ１１２は、処理パイプライン１０６に組み込まれた１又は複数のマイクロコードモジュールを含み得て、マイクロコードモジュールは、処理パイプライン１０６によって実行されるプログラム命令を含む。コーディネータ１１０は、例えば、プロセッサ１０４の処理ユニットによって実行され得る。コーディネータ１１０は、例えば、複数の処理パイプライン１０６の間でデータを分配すること、複数の処理パイプライン１０６からデータを収集すること、データを同期すること、タスクを同期すること、ワーカ１１２を調整することなど、セグメント化処理を管理及び／又は調整し得る。プロセッサ１０４及び／又は各処理パイプライン１０６は、入力データストリーム１２０のデータサブストリームを並行して処理するべく、ワーカ１１２のインスタンスを実行し得る。プロセッサ１０４が、複数の独立した処理ユニットである処理パイプライン１０６を含むベクトルプロセッサである場合、各処理パイプライン１０６は、ワーカ１１２インスタンスを独立に実行し得る。しかしながら、プロセッサ１０４がＳＩＭＤエンジンを内蔵している場合、ワーカ１１２は、ＳＩＭＤエンジンの処理パイプライン１０６の各々へデータを割り当てるプロセッサ１０４によって実行され得る。プロセッサ１０４は、次に、同一の動作（命令）を並行して実行するようにＳＩＭＤエンジンの全ての処理パイプライン１０６に指示するべく、単一の命令を開始し得て、各処理パイプライン１０６は、それぞれに割り当てられたそれ自体のデータを処理する。
【００５２】
２０２に示されているように、処理２００は、コーディネータ１１０が入力データストリーム１２０を受信することで開始する。
【００５３】
２０４に示されているように、コーディネータ１１０は、入力データストリーム１２０を複数のデータサブストリームへ分割し、それらを、処理パイプライン１０６のそれぞれによって各々が実行される複数のワーカ１１２へ分配する。データサブストリームの数は、処理パイプライン１０６などの利用可能な処理パイプラインの数に従って選択され得る。処理２００が、ＳＩＭＤエンジンを有するプロセッサ１０４によって実行される場合、ワーカ１１２は、それぞれのデータサブストリームのデータをＳＩＭＤエンジンの処理パイプライン１０６の各々へ割り当てるプロセッサ１０４によって実行される。コーディネータ１１０は、連続するデータサブストリームの各対が隣接するデータサブストリーム（すなわち、先行するデータサブストリーム、及び／又は、後続するデータサブストリーム）との重複部分を有するように、入力データストリーム１２０を分割する。コーディネータ１１０は、本明細書に後述されている複数のデータサブストリームの各々をセグメント化するべくワーカ１１２によって使用される１又は複数のセグメント化技法にもっとも良く対応できるように、重複部分のサイズを設定し得る。
【００５４】
ここで、図３を参照する。図３は、本発明のいくつかの実施形態に係る、入力データストリームを複数のサブストリームへ分割する例示的な処理の概略図である。コーディネータ１１０などのコーディネータは、ワーカ１１２などの複数のワーカによって処理される、入力データストリーム１２０などの例示的な入力データストリームを受信する。コーディネータ１１０は、例えば、４つのデータサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄへ入力データストリーム１２０を分割する。本明細書に記載されているデータサブストリームの数は、任意に選択される。データサブストリームの数は、処理パイプライン１０６などの利用可能な処理パイプラインの数（例えば、４、８、１６、６４、１２８、２５６、及び／又は２５６など）に従って選択され得る。更に、プロセッサ技術の発展に伴い、並列処理が可能な処理パイプライン１０６の数は、常に増加しているので、データサブストリームの数も、それに応じて増加し得る。殆どの場合において（すなわち、入力データストリーム１２０が十分に大きい場合）、処理パイプラインの増加に伴って、セグメント化のパフォーマンスが向上すると予想されている。コーディネータ１１０は、入力データストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄの各々が、隣接する先行の、及び／又は、後続のデータサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び／又は３００Ｄとの重複部分を有するように、入力データストリーム１２０を分割する。例えば、データサブストリーム３００Ａは、データサブストリーム３００Ｂとの重複部分３０２Ａを有し、データサブストリーム３００Ｂは、データサブストリーム３００Ｃとの重複部分３０２Ｂを有し、データサブストリーム３００Ｃは、データサブストリーム３００Ｄとの重複部分３０２Ｃを有する。明らかなように、例えば、データサブストリーム３００Ｂ及び３００Ｃなど、中央のデータサブストリームは各々、２つの重複部分、すなわち、３００Ａ及び３００Ｂなど、先行するデータサブストリームのそれぞれとの第１重複部分（それぞれ、３０２Ａ及び３０２Ｂ）、並びに、３００Ｃ及び３００Ｄなど、後続するデータサブストリームのそれぞれとの第２重複部分（それぞれ、３０２Ｂ及び３０２Ｃ）を有する。コーディネータ１１０は、データサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄをセグメント化するのに使用されるセグメント化技法に最適に対応するように、重複部分のサイズを選択及び／又は適合し得る。通常、重複部分である３０２Ａ、３０２Ｂ、及び／又は３０２Ｃなどの重複部分のサイズは、例えば、４、８、及び／又は１６セグメントなど、複数のデータセグメント（ブロック）を含むように選択される。セグメント化技法の大部分は、可変サイズセグメントを生成し得るが、セグメントは、平均セグメントサイズ（例えば、４キロバイト（ＫＢ））を維持し得る。このサイズは、予め定められた最小セグメントサイズ、及び、予め定められた最大セグメントサイズの間で変動し得る。
【００５５】
再度、図２を参照する。２０６で示されているように、ワーカ１１２は、並行してデータサブストリーム３００Ａ−３００Ｄをセグメント化する。処理パイプライン１０６が各々、ワーカ１１２を独立に実行している場合、ワーカ１１２の各々は、１つより多くのセグメント化データサブストリームのそれぞれを生成するべく、データサブストリーム３００Ａ−３００Ｄのうち１つより多くのそれぞれをセグメント化する。処理パイプライン１０６がＳＩＭＤ処理パイプラインである場合、プロセッサ１０４は、単一の命令を開始するワーカ１１２を実行する。この命令により、ＳＩＭＤエンジンの処理パイプライン１０６は、それ自体のそれぞれのデータサブストリーム３００Ａ−３００Ｄを並行してセグメント化する。ワーカ１１２は、それぞれのデータサブストリームをセグメント化するべく、複数のセグメント化技法のうち１又は複数（例えば、データサブストリームの各々にわたってシフトされるローリングシーケンスのためのローリングハッシュ値を計算する、及び、ローリングハッシュ値が１又は複数のセグメント化基準に準拠するかどうかチェックする）を使用し得る。任意の適切なセグメント化技法が処理２００に適用され得るので、ワーカ１１２は、当技術分野において知られている、及び／又は、まだ知られていない、他のセグメント化方法を使用し得る。ＳＩＭＤエンジンを有するプロセッサ１０４については、プロセッサ１０４によって実行されるワーカ１１２は、ＳＩＭＤエンジン処理パイプライン１０６の各々に、データサブストリーム３００Ａ−３００Ｄのそれぞれのデータを割り当てる。ＳＩＭＤエンジン処理パイプライン１０６は、ワーカ１１２（プロセッサ１０４）によって、単一の命令で、データサブストリーム３００Ａ−３００Ｄを並行してセグメント化する。
【００５６】
任意で、ワーカ１１２は、予め定められた最小サイズで、データセグメント（ブロック）の各々のセグメント化を開始する。ワーカ１１２の各々がローリングハッシュセグメント化技法を適用するとき、ワーカ１１２は、予め定められた最小サイズに従ってデータ項目のハッシュ値の計算を開始する。通常、データ重複排除については、データセグメントのサイズは、例えば、現在の処理、ストレージ、及び／又は、ネットワーキングのスループット及びパフォーマンスにもっとも良く適合し得る、４ＫＢ、６ＫＢ、及び／又は８ＫＢであり得て、それにより、データセグメントの処理のオーバーヘッドは、セグメントの数に関して最適化される。予め定められた最小サイズは、通常のセグメントサイズに基づいて、例えば、２ＫＢであり得る。
【００５７】
任意で、ワーカ１１２は、セグメント化データサブストリームにおけるデータセグメント（ブロック）の各々に対し、予め定められた最大サイズを適用する。ワーカ１１２の各々がローリングハッシュセグメント化技法を適用するとき、ローリングハッシュ値が１又は複数のセグメント化基準に準拠することをワーカ１１２が検出する前に、データ項目の予め定められた最大サイズに到達した場合に、ワーカ１１２は、データセグメントを「カット」、すなわち、指定し得る。予め定められた最大サイズは、通常のセグメントサイズに基づいて、例えば、１６ＫＢであり得る。
【００５８】
２０８に示されているように、ワーカ１１２がそれぞれのデータサブストリーム３００Ａ−３００Ｄのセグメント化を完了した後で、コーディネータ１１０は、元の入力データストリーム１２０の元のシーケンシング及び順序を復元するべく、データサブストリーム３００Ａ−３００Ｄを同期する。コーディネータ１１０はデータサブストリーム３００Ａ−３００Ｄの連続するデータサブストリームの各対によって共有されるセグメント化された重複部分３０２Ａ−３０２Ｃを解析することで、データサブストリーム３００Ａ−３００Ｄを同期する。全てのワーカ１１２は、データサブストリーム３００Ａ−３００Ｄをセグメント化するべく、同一のセグメント化技法、及び、同一のセグメント化基準を使用するので、各２つの隣接するセグメント化データサブストリーム３００Ａ−３００Ｄのそれぞれの重複部分３０２Ａ−３０２Ｃは、同様にセグメント化されることが予想される。コーディネータ１１０は、データサブストリーム３００Ａ−３００Ｄのセグメント化を適切に同期するべく、連続するデータサブストリーム３００Ａ−３００Ｄの間の同一のセグメント化領域を識別し得る。
【００５９】
２１０に示されているように、コーディネータ１１０がセグメント化データサブストリーム３００Ａ−３００Ｄを同期した後で、コーディネータ１１０は、セグメント化データサブストリームを共に結合して、元の受信した入力データストリーム１２０に対応する、完全なセグメント化データストリーム１３０を生成する。
【００６０】
任意で、コーディネータ１１０がセグメント化データサブストリーム３００Ａ−３００Ｄの同期に失敗した場合、コーディネータ１１０は、入力データストリーム１２０をセグメント化する。すなわち、入力データストリーム１２０を分割することと、ワーカ１１２ｃを利用して並行してデータサブストリーム３００Ａ−３００Ｄをセグメント化することとを行わない。
【００６１】
ここで、図４を参照する。図４は、本発明のいくつかの実施形態に係る、複数のセグメント化データサブストリームを結合して、セグメント化データストリームを生成する、例示的な処理の概略図である。プロセッサ１０４などのプロセッサが複数の独立した処理パイプラインを含む場合、各処理パイプラインは、ワーカ１１２などのワーカのインスタンスを実行する。ワーカ１１２のような複数のワーカは、対応するセグメント化データサブストリーム４００Ａ、４００Ｂ、４００Ｃ及び４００Ｄを生成するべく、データサブストリーム３００Ａ−３００Ｄなど、それらのそれぞれのデータサブストリームをセグメント化する。プロセッサ１０４がＳＩＭＤエンジンを有する場合、ワーカ１１２は、ＳＩＭＤエンジンの処理パイプライン１０６の各々にデータサブストリーム３００Ａ−３００Ｄのそれぞれのデータを割り当てるプロセッサ１０４によって実行される。ＳＩＭＤエンジン処理パイプライン１０６は、（プロセッサ１０４によって実行される）ワーカ１１２の命令で、データサブストリーム３００Ａ−３００Ｄを並行してセグメント化し得る。全てのワーカ１１２がデータサブストリーム３００Ａ−３００Ｄのセグメント化を完了し、それぞれセグメント化データサブストリーム４００Ａ−４００Ｄを提供した後で、コーディネータ１１０などのコーディネータは、セグメント化データストリーム４００Ａ−４００Ｄを結合して、入力データストリーム１２０に対応するセグメント化データストリーム１３０を生成する。コーディネータ１１０は、重複部分３０２Ａ、３０２Ｂ及び３０２Ｃなどの元の重複部分にそれぞれ対応するセグメント化された重複部分４０２Ａ、４０２Ｂ及び４０２Ｃのデータ項目のシーケンシングを同期することによって、セグメント化データサブストリーム４００Ａ−４００Ｄを結合して、元の入力データストリーム１２０の順序を維持する。セグメント化データサブストリーム４００Ａ−４００Ｄの隣接する各対は、セグメント化された重複部分４０２Ａ−４０２Ｃのそれぞれのセグメント化された重複部分を含む。ワーカ１１２の各々は、同一のセグメント化技法及び同一のセグメント化基準を使用するので、重複部分である３０２Ａ‐３０２Ｃは、同様にセグメント化される。例えば、セグメント化された重複部分４０２Ａは、セグメント化データサブストリーム４００Ａをセグメント化する処理パイプライン１０６、及び、セグメント化データサブストリーム４００Ｂをセグメント化する処理パイプライン１０６の両方によって、同様にセグメント化される。同様に、セグメント化された重複部分４０２Ｂは、セグメント化データサブストリーム４００Ｂをセグメント化する処理パイプライン１０６、及び、セグメント化データサブストリーム４００Ｃをセグメント化する処理パイプライン１０６の両方によって、同様にセグメント化される。同じように、セグメント化された重複部分４０２Ｃは、セグメント化データサブストリーム４００Ｃをセグメント化する処理パイプライン１０６、及び、セグメント化データサブストリーム４００Ｄをセグメント化する処理パイプライン１０６の両方によって、同様にセグメント化される。 
【００６２】
コーディネータ１１０は、重複部分４０２Ａ−４０２Ｃの各々において識別されたデータセグメントに基づいて、セグメント化データサブストリーム４００Ａ−４００Ｄのシーケンシングを同期することで、セグメント化データサブストリーム４００Ａ−４００Ｄを結合して、セグメント化データストリーム１３０を生成する。
【００６３】
本発明のいくつかの実施形態において、データサブストリームの各々のセグメント化は、データサブストリームの各々にわたってローリングシーケンスをシフトすること、及び、ローリングハッシュ値を計算することによって実行される。データセグメントを識別するべく、ローリングハッシュ値は、１又は複数のセグメント化基準に準拠しているかチェックされる。
【００６４】
ローリングハッシュセグメント化を利用する実施形態を更に示す前に、まず、ローリングシーケンス及びローリングハッシュを使用するセグメント化処理を説明する。
【００６５】
ここで、図５を参照する。図５は、ローリングハッシュセグメント化を使用する、入力データストリームのセグメント化の例示的な処理の概略図である。セグメント化データストリーム１３０などのセグメント化データストリームを生成するべく、入力データストリーム１２０などの入力データストリームがセグメント化され、入力データストリーム１２０内の複数のデータセグメント（ブロック）を指定する。セグメントの各々の検出には、３つの主要な段階、すなわち、スキップ５１０、初期化５１２、ロール５１４、及び、カット５１６が含まれる。スキップ５１０は、セグメントの各々が最小サイズを有するように、入力データストリーム１２０内のデータ項目の予め定められた最小数だけスキップすることを含む。初期化５１２は、ローリングハッシュ値を計算するための最小データサイズを設定するのに必要な予め定められた数のデータ項目（例えば、１６、６４、及び／又は１２８のデータ項目）だけシフトすることを含む。ロール５１４は、セグメントを検出するべく、入力データストリーム上でシフトされるローリングシーケンスのローリングハッシュ値を計算すること、及び、計算されたハッシュ値を１又は複数のセグメント化基準と比較することを含む。ハッシュ値がセグメント化基準に準拠する（満たす）とき、カット５１６が行われ、カット５１６の箇所までのデータ項目を含むデータセグメントがセグメントに指定される。セグメント化処理は、入力データストリーム１２０の始点から開始して、各カット点（すなわち、前のデータセグメントの端）から、スキップ５１０、初期化５１２、ロール５１４、及び、カット５１６を再度開始して、次のデータセグメントを検出及び指定する。セグメント化データストリーム１３０を生成するべく、セグメント５２０_１、５２０_２及び５２０_３など複数のデータセグメントが入力データストリーム１２０内で指定されるように、セグメント化処理は、入力データストリーム１２０全体で繰り返される。
【００６６】
ここで、図６を参照する。図６は、本発明のいくつかの実施形態に係る、ローリングハッシュセグメント化を使用して、並行して複数のデータサブストリームを並列にセグメント化するための例示的な処理の概略図である。コーディネータ１１０のようなコーディネータは、入力データストリーム１２０のような入力データストリームを、例えば４つの、複数のデータサブストリーム（データサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄなど）へ分割する。プロセッサ１０４のようなプロセッサが複数の独立した処理パイプラインを有する場合、各処理パイプラインは、ワーカ１１２のようなワーカのインスタンスを実行する。ワーカ１１２など、例えば４つの、複数のワーカは、セグメント化データサブストリーム４００Ａ、４００Ｂ、４００Ｃ及び４００Ｄなど、セグメント化データサブストリームを生成するべく、ローリングハッシュセグメント化を使用して、並行してそれぞれデータサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄを並列にセグメント化する。ワーカ１１２の各々は、データサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄのうち１つ又は複数をそれぞれ処理（セグメント化）する。ワーカ１１２の各々は、スキップ５１０のようなスキップ、初期化５１２のような初期化、ロール５１４のようなロール、及び、カット５１６のようなカットを含む、（本明細書で上述した）ローリングハッシュセグメント化技法を適用する。ローリングハッシュセグメント化技法は、可変サイズセグメント化を利用しているので、ワーカ１１２の各々は、例えば、５２０Ａ＿１、５２０Ｂ＿１、５２０Ｃ＿１、及び／又は、５２０Ｄ＿１など、それぞれのデータセグメントのためなど、異なるサイズのデータセグメントを検出し得る。
ワーカ１１２の１つがデータセグメント（ローリングハッシュ値がセグメント化基準に準拠していること）を検出し、セグメントを指定した後、ワーカ１１２は、データサブストリーム３００Ａ−３００Ｄそれぞれの全体について、その処理を繰り返す。ワーカ１１２は、セグメント化処理を互いから独立して実行するので、消費する処理時間が異なり得る。従って、複数のワーカ１１２によって実行されるセグメント化処理は、セグメント化データサブストリーム４００Ａ−４００Ｄの各々について、異なる時間に完了し得る。処理パイプライン１０６が、ＳＩＭＤエンジン処理パイプライン１０６である場合、ＳＩＭＤエンジンの処理パイプライン１０６の各々にデータサブストリーム３００Ａ−３００Ｄのそれぞれのデータを割り当てるプロセッサ１０４によってワーカ１１２が実行される。ＳＩＭＤエンジン処理パイプライン１０６は、（プロセッサ１０４によって実行される）ワーカ１１２の命令で、データサブストリーム３００Ａ−３００Ｄを並行してセグメント化し得る。ＳＩＭＤエンジン処理パイプライン１０６の１つがカット５１６を検出するまで、ＳＩＭＤエンジン処理パイプライン１０６は、それらのそれぞれのデータを並行して処理する。その時点で、（プロセッサ１０４によって実行される）ワーカ１１２は、全てのＳＩＭＤエンジン処理パイプライン１０６を停止し得る。なぜなら、全てのＳＩＭＤエンジン処理パイプライン１０６は、ワーカ１１２の同一命令を実行する必要があるからである。ワーカ１１２は、ロール５１４を再開するように全てのＳＩＭＤエンジン処理パイプライン１０６へ指示する前に、スキップ５１０及び初期化５１２を完了することによって、カット５１６を検出したＳＩＭＤエンジン処理パイプライン１０６のそれぞれのデータサブストリームを順次に処理し得る。
【００６７】
ここで、図７Ａ、図７Ｂ、図７Ｃ、図７Ｄ、図７Ｅ、図７Ｆ、図７Ｇ、図７Ｈ、図７Ｉ、図７Ｊ、図７Ｋ、図７Ｌ、及び、図７Ｍを参照する。これらは、本発明のいくつかの実施形態に係る、様々な時点において、複数のデータサブストリームを並行して並列にセグメント化するための例示的な処理の概略図である。コーディネータ１１０などのコーディネータは、最初に、入力データストリーム１２０などの入力データストリームを、例えば４つの、複数のデータサブストリーム（データサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄなど）へ分割する。ワーカ１１２など、例えば４つの、複数の処理パイプラインは、セグメント化データサブストリーム４００Ａ、４００Ｂ、４００Ｃ及び４００Ｄなど、セグメント化データサブストリームを生成するべく、ローリングハッシュセグメント化技法を使用して、並行してデータサブストリーム３００Ａ、３００Ｂ、３００Ｃ及び３００Ｄのそれぞれを並列にセグメント化する。本明細書に上述されているように、処理パイプライン１０６は、独立した処理パイプライン、並びに／又は、ＳＩＭＤプロセッサ及び／若しくはエンジンの処理パイプラインであり得る。処理パイプライン１０６の各々は、データサブストリーム３００Ａ−３００Ｄのそれぞれをセグメント化（処理）する。処理パイプライン１０６の各々は、スキップ５１０のようなスキップ、初期化５１２のような初期化、ロール５１４のようなロール、カット５１６のようなカットを含む、ローリングハッシュセグメント化をデータサブストリーム３００Ａ−３００Ｄのそれぞれに適用する。
【００６８】
図７Ａ‐図７Ｍは、４つの処理パイプライン１０６の１つによって各々実行される４つのワーカ１１２によって行われる、並行セグメント化の進行を示す。ワーカ１１２は、セグメント化データサブストリーム４００Ａ−４００Ｄを生成するべく、ストリーム内のデータサブストリーム３００Ａ−３００Ｄを並行して、独立にセグメント化する。 
【００６９】
図７Ａから分かるように、４つのデータサブストリーム３００Ａ−３００Ｄは、スキップ５１０、初期化５１２、及び、ローリング計算５１４によって、同時にセグメント化される。セグメント化データサブストリーム４００Ｂをセグメント化する処理パイプライン１０６が最初にデータセグメントを検出し、シーケンスをカット５１６してセグメント５２０を指定する。カット５１６に続き、セグメント化データサブストリーム４００Ｂをセグメント化する処理パイプライン１０６は、指定されたデータセグメントの端で開始する、次のデータセグメントのためのスキップ５１０及び初期化５１２を実行することに移行する。図７Ｂから分かるように、セグメント化データサブストリーム４００Ａ、４００Ｃ及び４００Ｄを処理する処理パイプライン１０６がまだロール５１４を実行している間、セグメント化データサブストリーム４００Ｂをセグメント化する処理パイプラインは、第２データセグメントを検出し、シーケンスをカット５１６してセグメント５２０を指定する。図７Ｃから分かるように、セグメント化データサブストリーム４００Ａ及び４００Ｄを処理している処理パイプラインがまだロール５１４を実行している間、セグメント化データサブストリーム４００Ｂ及び４００Ｃをセグメント化する２つの処理パイプライン１０６は、第３のデータセグメント及び第１のデータセグメントをそれぞれ検出し、シーケンスをカット５１６してセグメント５２０を指定する。処理パイプライン１０６は、セグメント化データサブストリーム４００Ａ−４００Ｄを生成するべく、図７Ｄ‐図７Ｍに示されているようなセグメント化処理に進む。図７Ｈから分かるように、セグメント化データサブストリーム４００Ｂを処理する処理パイプライン１０６は、セグメント化データサブストリーム４００Ｂの端に到達し、セグメント化処理を完了する。シーケンスのセグメント化を完了すると、セグメント化データサブストリーム４００Ｂを生成した処理パイプライン１０６は停止し、他の処理パイプライン１０６が他のセグメント化データサブストリーム４００Ａ、４００Ｃ及び４００Ｄのセグメント化を完了するまで待機する。
【００７０】
本明細書に上述されているように、ＳＩＭＤエンジンの処理パイプライン１０６については、処理パイプライン１０６の１つがカット５１６を検出し、セグメント５２０を指定するとき、カット５１６を行った処理パイプライン１０６がスキップ５１０及び初期化５１２を完了するまで、全ての他の処理パイプライン１０６におけるロール５１４は停止される。カット５１６を行った、検出している処理パイプライン１０６が、スキップ５１０及び初期化５１２を完了した後、（プロセッサ１０４によって実行される）ワーカ１１２は、ロール５１４を再開するようＳＩＭＤエンジンの処理パイプライン１０６全てに指示し得る。図７Ｌから分かるように、セグメント化データサブストリーム４００Ｃ及び４００Ｄを処理しているワーカ１１２はまた、セグメント化処理を完了して停止する。図７Ｍから分かるように、セグメント化データサブストリーム４００Ａを処理している処理パイプライン１０６が最後にセグメント化処理を完了して停止する。全ての処理パイプライン１０６が、セグメント化データサブストリーム４００Ａ−４００Ｄのセグメント化をそれぞれ完了すると、コーディネータ１１０は、セグメント化データサブストリーム１３０を生成するべく、セグメント化重複部分４０２Ａ−４０２Ｃなどのセグメント化重複部分を同期することによって、４００Ａ‐４００Ｄを結合し得る。
【００７１】
本発明の様々な実施形態の記載は、包括的、又は、開示された実施形態に限定することを意図するものではなく、例示を目的として示されている。記載された実施形態の範囲及び思想を逸脱することなく、多くの修正及び変形が、当業者にとって明らかとなるであろう。本明細書で使用される用語は、実施形態の原理、実際の適用、又は、業界で見られる技術に対する技術的改善点をもっとも良く説明するように、又は、当業者が本明細書に開示された実施形態を理解できるように選択された。
【００７２】
本出願から特許権満了までの存続期間の間、ＳＩＭＤなど、多くの関連するベクトル処理技術が開発されることが予想される。ＳＩＭＤという用語の範囲は、そのような新しい技術全てを先験的に含むことが意図されている。本明細書において使用される「約」という用語は、±１０％を意味する。
【００７３】
「備える」、「備え」、「有する」、「有し」「含む」という用語、及び、それらの活用形は、「以下を含むがそれらに限定されない」ことを意味する。この用語は、「から成る」、及び、「から主に成る」という用語を包含する。 
【００７４】
「から主に成る」という語句は、組成又は方法が、追加的な構成要素、及び／又は、段階を含み得るが、その追加的な構成要素、及び／又は、段階が、請求される組成又は方法の基本的な新しい特性を実質的に変化させない場合のみに限られることを意味する。
【００７５】
本明細書において使用される単数形は、文脈上別の明確な指示が無い限り、複数形を含む。例えば、「複合物」、又は、「少なくとも１つの複合物」という用語は、複数の複合物を含み、それらの混合物も含み得る。
【００７６】
本明細書において使用される「例示的」という単語は、「例、事例、例示としての役割を果たす」ことを意味する。「例示的」と記載されている任意の実施形態は、他の実施形態より望ましい、又は、優れている、及び／又は、他の実施形態からの機能を組み込むことを排除するものと、必ずしも解されるものではない。
【００７７】
本明細書において使用される、「任意で」という単語は、「いくつかの実施形態において提供され、他の実施形態では提供されない」ことを意味する。本発明の特定の実施形態のいずれも、機能が競合しない限り、複数の「任意の」機能を含み得る。
【００７８】
分かり易くするべく別個の実施形態の文脈で説明されている、本発明の特定の機能は、単一の実施形態において組み合わせて提供されることもあり得ることを認識すべきである。逆に、簡潔にするべく単一の実施形態の文脈で説明されている、本発明の様々な機能はまた、別個に、若しくは、いずれかの好適なサブコンビネーションで、又は、本発明で説明されているいずれかの他の実施形態において好適に提供され得る。様々な実施形態の文脈上で説明されている特定の機能は、それらの実施形態の本質的な機能として見なされるべきでない。ただし、それらの要素が無ければ実施形態が動作不能である場合を除く。
【図１】
0006537202.tif 000002
【図２】
0006537202.tif 000003
【図３】
0006537202.tif 000004
【図４】
0006537202.tif 000005
【図５】
0006537202.tif 000006
【図６】
0006537202.tif 000007
【図７Ａ−７Ｃ】
0006537202.tif 000008
【図７Ｄ−７Ｆ】
0006537202.tif 000009
【図７Ｇ−７Ｉ】
0006537202.tif 000010
【図７Ｊ−７Ｌ】
0006537202.tif 000011
【図７Ｍ】
0006537202.tif 000012