(57)【要約】  本出願は、全体の圧縮構造体を読み出し解凍する必要なく、メモリ内の圧縮構造体にランダムにアクセスする方法を提供する。
2011511986.tif 000002
【特許請求の範囲】
【請求項１】
指示セットのアーキテクチャを有するプロセッサであって、
前記指示セットのアーキテクチャは、ランダムアクセスメモリに記憶された圧縮構造体からデータ値を読み出すための、少なくとも１つの読込指示を備え、
前記少なくとも１つの読込指示は、演算コード、および、非圧縮構造体において前記データ値の位置を特定する少なくとも１つの演算対象を備え、
前記プロセッサは、非圧縮構造体内の前記データ値の位置を、前記圧縮構造体における前記データ値のためのメモリ位置に変換するように適合され、さらに、前記データ値を前記メモリ位置から読み出すように適合される
ことを特徴とするプロセッサ。
【請求項２】
請求項１に記載のプロセッサであって、前記非圧縮構造体は、瑣末な値および瑣末でない値を備え、前記圧縮構造体は、瑣末でないデータ値のみを備えること、を特徴とするプロセッサ。
【請求項３】
請求項１または２に記載のプロセッサであって、前記圧縮データ構造体は、前記非圧縮構造体における瑣末でないデータ値の位置を表すマップを備えること、を特徴とするプロセッサ。
【請求項４】
請求項３に記載のプロセッサであって、前記プロセッサは、要求された前記値の転送に先だって、前記圧縮データ構造体の前記マップを得るように構成されること、を特徴とするプロセッサ。
【請求項５】
請求項３または４に記載のプロセッサであって、前記瑣末でないデータ値は非零値であること、を特徴とするプロセッサ。
【請求項６】
請求項３〜５のいずれか一項に記載のプロセッサであって、前記プロセッサは、前記マップから前記要求された値が瑣末な値か瑣末でない値かを決定すること、を特徴とするプロセッサ。
【請求項７】
請求項６に記載のプロセッサであって、前記少なくとも１つの演算対象は、前記圧縮構造体のためのベースアドレスを含むこと、を特徴とするプロセッサ。
【請求項８】
請求項７に記載のプロセッサであって、前記要求された値が瑣末でない値の場合、前記プロセッサは、前記マップから瑣末でない値の数をカウントし、それを前記ベースアドレスへのオフセットとして要求された値の前に加算し、ランダムアクセスメモリがそれに応じてアドレスにアクセスするようにセットするように構成されること、を特徴とするプロセッサ。
【請求項９】
請求項８に記載のプロセッサであって、前記カウントは、複数の加算器を用いて実行されること、を特徴とするプロセッサ。
【請求項１０】
請求項８に記載のプロセッサであって、前記要求された値が瑣末な値であるときは、前記プロセッサは、前記メモリにアクセスすることなく前記瑣末な値を返すように構成されること、を特徴とするプロセッサ。
【請求項１１】
請求項１〜１０のいずれか一項に記載のプロセッサであって、前記プロセッサは、前記指示に応答して複数のデータ値を読込むように適合されること、を特徴とするプロセッサ。
【請求項１２】
請求項１に記載のプロセッサであって、前記データ値は浮動小数点数であること、を特徴とするプロセッサ。
【請求項１３】
請求項１２に記載のプロセッサであって、前記データ値は単精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項１４】
請求項１２に記載のプロセッサであって、前記データ値は倍精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項１５】
請求項１２に記載のプロセッサであって、前記データ値は拡張精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項１６】
請求項１２に記載のプロセッサであって、前記データ値は１２８ビット精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項１７】
請求項１に記載のプロセッサであって、前記データ値は整数であること、を特徴とするプロセッサ。
【請求項１８】
請求項１に記載のプロセッサであって、前記データ値は、浮動小数点数、浮動小数点数行列、浮動小数点数ベクトル、および、固定小数点整数の組合せであること、を特徴とするプロセッサ。
【請求項１９】
データ構造体からプロセッサへ少なくとも１つのデータ値を読込む方法であって、
前記データ構造体は、瑣末でないデータ値のみが存在する圧縮形式でメモリに記憶され
前記圧縮形式は、さらに、非圧縮構造体における前記瑣末でないデータ値の位置を特定するマップを備え、
前記方法は、
前記非圧縮構造体に読込むための、前記少なくとも１つのデータ値のための少なくとも１つの位置を受け取るステップと、
前記マップを使用し、前記圧縮構造体における、前記少なくとも１つのデータ値の前記少なくとも１つの記憶された位置を特定するステップと、
前記少なくとも１つの記憶された位置を使用し、前記少なくとも１つのデータ値を、前記メモリから前記プロセッサに読込むステップと、
を含むことを特徴とする方法。
【請求項２０】
請求項１９に記載の方法であって、前記方法は、前記少なくとも１つの位置に特定されたデータ値のみを読込むこと、を特徴とする方法。
【請求項２１】
請求項２０に記載の方法であって、前記方法は、前記少なくとも１つのデータ値の読み出しに先立って、前記圧縮データ構造体の前記マップを得るステップを含むこと、を特徴とする方法。
【請求項２２】
請求項２１に記載の方法であって、前記マップを得るステップは前記メモリから前記マップを読み出すステップを含むこと、を特徴とする方法。
【請求項２３】
請求項２０〜２２のいずれか一項に記載の方法であって、前記瑣末でないデータ値は非零値であること、を特徴とする方法。
【請求項２４】
請求項２０〜２３のいずれか一項に記載の方法であって、前記要求されたデータ値が瑣末でない値の場合は、前記方法は、前記要求されたデータ値の前に、前記マップから瑣末でない値の数をカウントし、それに応じて前記ランダムアクセスメモリがアドレスにアクセスするようにセットするように構成されること、を特徴とする方法。
【請求項２５】
請求項２０〜２４のいずれか一項に記載の方法であって、前記方法は、複数のデータ値を前記プロセッサおよびメモリの間に同時に転送すること、を特徴とする方法。
【請求項２６】
請求項２０〜２３のいずれか一項に記載の方法であって、前記受け取った少なくとも１つの位置が、前記非圧縮構造体における瑣末な値の前記記憶位置に対応する場合は、前記方法は、前記瑣末な値を直接前記プロセッサに提供するように構成されること、を特徴とする方法。
【請求項２７】
請求項２０〜２６に記載の方法であって、前記データ値は、浮動小数点数であること、を特徴とする方法。
【請求項２８】
請求項２７に記載の方法であって、前記データ値は、単精度浮動小数点数であること、を特徴とする方法。
【請求項２９】
請求項２７に記載の方法であって、前記データ値は、倍精度浮動小数点数であること、を特徴とする方法。
【請求項３０】
請求項２７に記載の方法であって、前記データ値は、拡張精度浮動小数点数であること、を特徴とする方法。
【請求項３１】
請求項２７に記載の方法であって、前記データ値は、１２８ビット精度浮動小数点数であること、を特徴とする方法。
【請求項３２】
請求項２０〜２６のいずれか一項に記載の方法であって、前記データ値は整数であること、を特徴とする方法。
【請求項３３】
請求項２０に記載の方法であって、前記データ値は、浮動小数点数、浮動小数点数行列、浮動小数点数ベクトル、および、固定小数点整数の組合せであること、を特徴とする方法。
【請求項３４】
少なくとも１つのデータ値を、メモリ内の圧縮構造体から読込むデータ転送機能を有するデータ処理装置であって、
前記圧縮構造体は、瑣末でないデータ値のみが存在する複数のデータ値、および、対応する非圧縮構造体内に前記瑣末でないデータ値の位置を特定するマップを備え、
前記データ転送機能は、前記データ値を読込むための指示に応答し、
前記指示は、前記対応する非圧縮構造体内における前記データ値の位置を特定し、
前記データ転送の特徴は、前記特定された位置からメモリオフセットを生成し、前記オフセットを、前記データ値をメモリから転送するために使用することに適合される
ことを特徴とするデータ処理装置。
【請求項３５】
請求項３４に記載のデータ処理装置であって、前記データ処理装置はプロセッサであること、を特徴とするデータ処理装置。
【請求項３６】
請求項３４に記載のデータ処理装置であって、前記データ処理装置は状態エンジンであること、を特徴とするデータ処理装置。
【請求項３７】
指示セットアーキテクチャを有するプロセッサであって、
前記指示セットアーキテクチャは、ランダムアクセスメモリにおける、非圧縮データ構造体から対応する圧縮データ構造体の中に、少なくとも１つのデータ値を記憶するための少なくとも１つの記憶指示を備え、
前記少なくとも１つの記憶指示は、演算コード、および、前記非圧縮データ構造体における前記少なくとも１つのデータ値の位置を特定する少なくとも１つの演算対象を備え、
前記プロセッサは、非圧縮構造体内の前記少なくとも１つのデータ値の前記位置を、前記圧縮構造体における前記データ値のためのメモリ位置に、前記圧縮構造体内のデータ値の前記位置を示すマップを用いて変換することに適合され、さらに、前記少なくとも１つのデータ値をこのメモリ位置に記憶することに適合される
ことを特徴とするプロセッサ。
【請求項３８】
請求項３７に記載のプロセッサであって、前記非圧縮構造体は瑣末な値および瑣末でない値を備え、前記圧縮構造体は瑣末でないデータ値のみを備えること、を特徴とするプロセッサ。
【請求項３９】
請求項３７または３８に記載のプロセッサであって、前記マップは、前記圧縮データ構造体の一部であり、前記非圧縮データ構造体における瑣末でないデータ値の位置を表すこと、を特徴とするプロセッサ。
【請求項４０】
請求項３９に記載のプロセッサであって、前記プロセッサは、前記要求された値を記憶する前に、メモリから前記圧縮データ構造体の前記マップを得るように構成されること、を特徴とするプロセッサ。
【請求項４１】
請求項３９または４０に記載のプロセッサであって、前記瑣末でないデータ値は非零値であること、を特徴とするプロセッサ。
【請求項４２】
請求項３７〜４１のいずれか一項に記載のプロセッサであって、前記プロセッサは、前記データ値の前に、前記マップから瑣末でない値の数をカウントし、それに応じて前記ランダムアクセスメモリがアドレスにアクセスするようにセットするように構成されること、を特徴とするプロセッサ。
【請求項４３】
請求項４２に記載のプロセッサであって、前記カウントは一連の加算器を用いて実行されること、を特徴とするプロセッサ。
【請求項４４】
請求項３７から４３のいずれか一項に記載のプロセッサであって、前記プロセッサは、前記演算コードに応答し、複数のデータ値を同時に記憶すること、を特徴とするプロセッサ。
【請求項４５】
請求項３７〜４４のいずれか一項に記載のプロセッサであって、前記少なくとも１つの演算対象は、ＲＡＭにおける前記圧縮データ構造体の前記ベースアドレス含むこと、を特徴とするプロセッサ。
【請求項４６】
請求項３７〜４６のいずれか一項に記載のプロセッサであって、前記圧縮データ構造体内の複数のデータ値を一つの指示とともに記憶することができること、を特徴とするプロセッサ。
【請求項４７】
請求項３７に記載のプロセッサであって、前記データ値は、浮動小数点数であること、を特徴とするプロセッサ。
【請求項４８】
請求項４７に記載のプロセッサであって、前記データ値は、単精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項４９】
請求項４７に記載のプロセッサであって、前記データ値は、倍精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項５０】
請求項４７に記載のプロセッサであって、前記データ値は、拡張精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項５１】
請求項４７に記載のプロセッサであって、前記データ値は、１２８ビット精度浮動小数点数であること、を特徴とするプロセッサ。
【請求項５２】
請求項３７に記載のプロセッサであって、前記データ値は整数であること、を特徴とするプロセッサ。
【請求項５３】
請求項３７に記載のプロセッサであって、前記データ値は、浮動小数点数、浮動小数点数行列、浮動小数点数ベクトル、および、固定小数点整数の組合せであること、を特徴とするプロセッサ。
【請求項５４】
プロセッサから、瑣末でないデータ値のみが存在するメモリ内の圧縮構造体の中にデータ値を挿入する方法であって、
前記圧縮構造体は、対応する非圧縮構造体における、前記瑣末でないデータ値の位置を特定するマップを備え、
前記方法は、
挿入される前記データ値の前記非圧縮構造体内の位置を受け取るステップと、
前記マップを使用し、前記受け取った位置から、前記圧縮構造体における前記データ値の前記対応する位置を特定するステップと、
前記対応する位置を使用し、前記メモリ内の前記データ値を記憶するステップと、
を含むことを特徴とする方法。
【請求項５５】
請求項５４に記載の方法であって、前記方法は、前記データ値を記憶するステップに先立って、前記圧縮データ構造体の前記マップを得るステップ含むこと、を特徴とする方法。
【請求項５６】
請求項５５に記載の方法であって、前記マップを得る前記ステップは、前記マップを前記メモリから読み出すステップを含むこと、を特徴とする方法。
【請求項５７】
請求項５４〜５６のいずれか一項に記載の方法であって、前記瑣末でないデータ値は非零値であること、を特徴とする方法。
【請求項５８】
請求項５４〜５７のいずれか一項に記載の方法であって、要求されたデータ値が瑣末でない値の場合は、前記方法は、前記マップから、前記要求されたデータ値の前に瑣末でない値の数をカウントし、それに応じて、前記ランダムアクセスメモリがアドレスにアクセスするようにセットするように構成されること、を特徴とする方法。
【請求項５９】
請求項５４〜５８のいずれか一項に記載の方法であって、前記方法は、複数の２つのデータ値を前記プロセッサとメモリの間に同時に転送すること、を特徴とする方法。
【請求項６０】
請求項５４〜５９のいずれか一項に記載の方法であって、前記データ値は、浮動小数点数であること、を特徴とする方法。
【請求項６１】
請求項６０に記載の方法であって、前記データ値は、単精度浮動小数点数であること、を特徴とする方法。
【請求項６２】
請求項６０に記載の方法であって、前記データ値は、倍精度浮動小数点数であること、を特徴とする方法。
【請求項６３】
請求項６０に記載の方法であって、前記データ値は、拡張精度浮動小数点数であること、を特徴とする方法。
【請求項６４】
請求項６０に記載の方法であって、前記データ値は、１２８ビット精度浮動小数点数であること、を特徴とする方法。
【請求項６５】
請求項５４〜５９のいずれか一項に記載の方法であって、前記データ値は整数であること、を特徴とする方法。
【請求項６６】
請求項５４に記載の方法であって、前記データ値は、浮動小数点数、浮動小数点数行列、浮動小数点数ベクトル、および、固定小数点整数の組合せであること、を特徴とする方法。
【請求項６７】
データ値を直接メモリ内の圧縮構造体内に記憶するための、データ転送機能を有するデータ処理装置であって、
前記圧縮構造体は、瑣末でないデータ値のみが存在する複数のデータ値、および、対応する非圧縮構造体内の前記瑣末でないデータ値の位置を特定するマップを備え、
前記データ転送機能は、前記データ値を記憶するための指示に応答し、
前記指示は、前記対応する非圧縮構造体内の前記データ値の位置を特定し、
前記データ転送機能は、前記特定された位置からメモリオフセットを生成し、前記メモリにアクセスするための前記オフセットを使用し、前記データ値をメモリの中に記憶するように適合される
ことを特徴とするデータ処理装置。
【請求項６８】
請求項６７に記載のデータ処理装置であって、前記データ処理装置はプロセッサであること、を特徴とするデータ処理装置。
【請求項６９】
請求項６７に記載のデータ処理装置であって、前記データ処理装置は状態エンジンであること、を特徴とするデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、プロセッサの分野、およびメモリとプロセッサの間のデータ転送の方法に関する。特に、本出願は、メモリ内の圧縮データ構造体において、圧縮構造体の全体を読み出して解凍する必要なく、個別の値、または、隣接グループもしくは非隣接グループの値にアクセスする方法を対象にする。
【背景技術】
【０００２】
計算システムの設計においては基本的な問題がある。すなわち、メモリアクセスの時間コストを最小にすることである。
【０００３】
これは、計算をサポートするどんなメモリ技術を使用しても、メモリをプロセッサに接続するためにどんな技術を使用しても、コンピュータシステムを設計する上での基本的な制限である。最大の制限は、所要時間内にどれだけの量の情報をプロセッサとメモリ間で転送できるかによる。これは、利用できるメモリの帯域幅であり、利用できるメモリの帯域幅による計算パワーの制限は、しばしば、「メモリウォール」と称される。
【０００４】
本出願は、実効的なメモリの帯域幅を増やそうとし、データ圧縮の使用により「メモリウォール」の制限を最小化しようとする。
【０００５】
データ圧縮を使用し、「メモリウォール」の影響を減らすことは公知である。しかし、圧縮メモリサブシステムを使用するプログラマーにとっての問題点は、図１のシステムに示すように、データを処理する前に解凍しなければならないことである。これは、圧縮データをメモリ１０の一部からプロセッサ１６のレジスタファイルへ読み出すステップ、プログラムメモリ１８から読み出したプログラムコードを使用して読み出したデータを解凍するステップ、および、メモリ１２内の他の圧縮されていない部分に解凍したデータを記憶するステップを伴う。
【０００６】
しかし、この解決策は、圧縮データを読み出し、非圧縮の形態で記憶し、再びプロセッサに読み出して処理するために、追加のメモリ帯域幅を必要とするという不利な点がある。非圧縮データを保持するために追加のメモリ容量が必要となり、解凍プロセスはプロセッサのレジスタファイルへの圧力を増加させると考えられる。明らかに、これは次善の解決策である。このことは、なぜ、このような圧縮メモリのサブシステムは、マイクロプロセッサ産業の主流となるより、学術的好奇心の対象のままであるのかの説明を示唆する。
【０００７】
欧州特許出願公開第０２４００３２号明細書は、ベクトルデータを記憶し読み出すためのメモリを備えるベクトルプロセッサを開示する。ベクトルプロセッサは、各々が複数のｍ個のベクトル要素を並行して読み出しまたは書き込みができる複数のベクトルレジスタと、並行してｍ個のマスクビットに対応できる少なくとも１つのマスクベクトルレジスタと、前記メモリ、前記複数のベクトルレジスタおよび前記マスクベクトルレジスタに接続されており、メモリ内に一定の間隔で配置されたアドレスから、有効なマスクビットに対応する選択されたベクトルレジスタの選択された記憶位置へ、ベクトル要素を転送するための指示に応答する転送部とを備える。この方法は有用であるが、ベクトルデータの記憶／読み出しはレジスタ全体に制限される。
【０００８】
レジスタブロッキングは、行列代数（特に有限要素の場合）を加速するために有効な技術である。しかし、多くの行列（例えば、ＧＯＯＧＬＥ（登録商標）のようなサーチエンジンで使用されるもの）は零を埋める必要があり、有効なＦＬＯＰＳ（フロップス、Floating Point Operations Per Second）を減少させ、メモリに要求される帯域幅を増加させるという不利な点がある。これらは両方とも、現代の計算システムにおいて供給が不足しているものである。
【０００９】
実際は、処理能力およびメモリの帯域幅は、それぞれ、年率５０％および７％の全く異なる比率で向上しており、これにより増大している差は、上述のように「メモリウォール」と称される。メモリウォールを「突破」したとの主張が数多くある。これらは、たいていキャッシュを使用しチップ外で処理しなければならない確率を減らす構成、および／または、マルチスレッドを使用しチップ外の処理に伴う待ち時間および不利益を軽減する構成からなる。
【００１０】
これらの方法は、制限された外部メモリの帯域幅の問題を解決するよりは、むしろ、単に隠している。また、これらの方法は、一般的に、データセットが十分にデータの局所性を示していること、および／または、プログラムが十分なスレッドレベル並列性（ＴＬＰ： Thread-Level Parallelism）を示し効率的であること、に依存している。これは、全ての問題に当てはまるわけではなく、確実に先験的にいつも知られているわけではない。実際には、より大きく、かつ、より興味深い問題の多くは、十分なデータの局所性も十分なＴＬＰも示さない。システム全体のスループットは、外部メモリの帯域幅によって制限されるポイントまで悪化する。そして、チップ上に追加した追加ハードウェアは役に立たない。この理由により、大きな工学アプリケーションにおいて、プロセッサの性能を、製造業者が最大能力の仕様としている能力の１％、または、それ以下まで引き下ろしていることは、珍しいことではない。
【発明の概要】
【００１１】
本出願は、圧縮フォーマットでデータを記憶することにより、実効的なメモリの帯域幅を増やし、計算上の「メモリウォール」の制限を最小化しようとする。このことは、例えば、コンピュータグラフィクス、剛体の力学、有限要素解析、および、その他の科学および工学アプリケーションを含む、メモリに記憶する必要がある大きなデータを処理する多くのアプリケーションにおいて使用されるブロック構造に適した圧縮手段および解凍手段を提供することにより達成される。「メモリウォール」の影響をさらに減らすために、プロセッサのパイプラインも圧縮を利用するように変形させ、処理レートを、圧縮データのみを計算することにより達成できる処理レートよりも増加させる。
【００１２】
特に、本出願では、メモリに記憶されている圧縮構造体内の個別のデータに、値のマップ、および、指示の一部として特定された関連するフィールドビットを使用し、ランダムアクセスすることを許可している。
【００１３】
したがって、本出願の第１の実施形態は、請求項１および３８に記載されるプロセッサを提供する。本出願は、請求項２１および５６に記載される方法も提供する。本出願は、さらに、請求項３５および６９に記載されるデータ処理装置も提供する。有利な実施形態は、従属項において提供する。
【００１４】
本出願を、添付図面を参照して説明する。
【図面の簡単な説明】
【００１５】
【図１】当業で公知のプロセッサの配置図である。
【図２】本出願のプロセッサの処理に適している一連の変換である。
【図３】本出願の一実施形態に係るプロセッサの例である。
【図４】図３のプロセッサに使用することができる例示的な解凍方法を示す図である。
【図５】図３のプロセッサにより、どのようにメモリ構造を３２ビットＲＡＭに適合するように圧縮できるかを示す図である。
【図６】図３のプロセッサに使用することができる例示的な指示コードのフォーマットを示す図である。
【図７】図３のプロセッサにより、どのように図５と同じメモリ構造を６４ビットＲＡＭに適合するように圧縮できるかを示す図である。
【図８】図３のプロセッサに使用してもよいアドレスを生成する例示的な回路を示す図である。
【図９】例示的な値を用いて図８の演算を説明する図である。
【図１０】図３のプロセッサに使用してもよい、例示的な読込／記憶回路を説明する図である。
【図１１】図１０に使用するアドレスシーケンス生成を示す図である。
【図１２】図１０の回路の処理モードを示す例示的なタイミング図である。
【図１３】図３のプロセッサのより詳細なブロック図である。
【図１４】指示フォーマットである。
【図１５】例示的なプロセッサで利用できる、圧縮データの読込／記憶のための指示を含む様々な処理コードの指示を示す表である。
【図１６】非圧縮に基づく指示のアドレス生成のための回路を示す図である。
【図１７】プロセッサの圧縮方法によるビット生成回路である。
【図１８】図３の例示的なプロセッサにより提供される計算の低減量を、様々なタイプの行列構造に対して示す図である。
【図１９】圧縮データを読込／記憶する図２のプロセッサに適した回路を示す図である。
【図２０】メモリ構造上のポート幅の影響を示す図である。
【図２１】図２０に示すアドレスのためのアドレス生成へ、結果として生じる影響を示す図である。
【図２２】図２０の影響を示すタイミング図の例である。
【実施例】
【００１６】
圧縮の望ましい状況の典型的な例は、行列表示および線形代数演算を使用して、コンピュータグラフィクスおよび関連アプリケーションにおける２次元画面で現実性をシミュレーションするものである。もとの行列データへの演算は、しばしば、回転、その他の変換およびそれらのシーケンスからなる。図２に、それらのタイプを示す。図に示すように、これらの行列は多数の零を含み、多数の零は、読込／記憶するための多くのメモリの帯域幅を必要とする。しかし、多数の零は、行列全体を使用して実行された計算結果に貢献していない。すなわち、多数の零は、計算の観点からは瑣末な値である。
【００１７】
図３に示すように、本出願は、メモリ内の圧縮データを直接演算でき、解凍プロセスを必要としない変形したプロセッサを提供する。したがって、追加の非圧縮データ用のバッファ、および、圧縮データをバッファエリアに解凍し、さらに処理をすすめるための追加のプロセッサおよびメモリの帯域幅が不要となる。代わりに、圧縮および解凍プロセスは、プロセッサのメモリアクセス構造体に統合される。
【００１８】
本出願は、例えば、浮動小数点数の行列、浮動小数点数のベクトル、浮動小数点数のスカラー、符号付き整数、符号なし整数、文字列、および、アドレスポインタの任意の組み合わせからなる、任意のサイズおよび複雑さの圧縮構造体を可能とする。
【００１９】
好適には、圧縮および解凍ロジックは、プロセッサの読込／記憶ポート内に埋め込まれ、処理１件ごとに考慮する方式で、どのようにデータを圧縮メモリサブシステムから読み出し、および、圧縮メモリサブシステムへ書き込むかの詳細について気にする必要をなくすという点で、プログラマーの仕事を容易にする。
【００２０】
ここに記載する解決策は、値マップを使用し、図４に示す方法で、零および非零の入力を高密度なサブ行列に符合化する。このような値マップの使用は、先に関連出願において記載されている（２００７年４月１１日に出願の米国仮特許出願第６０／９１１，２７３号、２００７年４月１１日に出願の米国仮特許出願第６０／９１１，２７４号、英国特許出願第０７０４９９９９．２号、英国特許出願第０７０４９９７６．０号、および、優先権主張の基礎とした対応するＰＣＴ出願）。これらの全体の内容を、参照により本願に援用する。図示の例においては、３７．５％の圧縮を達成している。提案した解決策は、記憶される行列の各々の零入力は、３２ビットの単精度、６４ビットの倍精度等の数ではなく１ビットにより表されるという有利な点を有する。全体の圧縮は、３２ビットの単精度の入力をもつ疎行列を記憶する３２ビットのメモリシステムにおいて、１つの密行列あたり１つ以上の入力が零であれば達成される。
【００２１】
上述の基本的な圧縮は興味深いものであり有利な効果を提供するが、多くの実際のアプリケーションにおいては、プログラマーは単なる疎行列以上のものを記憶することを望み、しばしば、複雑なデータ構造体に記憶されているデータを記憶し読み出すことを必要とする。課題は、いかに圧縮技術を統合し、混在した圧縮／非圧縮のデータ構造体を取り扱う際に、プログラマーを過度に悩ませることなく、同等の性能およびメモリ圧縮の利点を上述のアプリケーションに提供できるかである。
【００２２】
本出願は、上述の方法により圧縮することができるが、非圧縮の浮動小数点数または整数を含んでいてもよい、大きな構造体内のデータにランダムにアクセスする手段を提供する。この技術によれば、基本構造は、３２ビットの整数により表される３２ビットの入力を３２個まで含むことができる（値マップ）。原則として、この技術は３２個に制限されない。しかし、３２個の入力の値または構造、値マップの大きさ、および、入力の個数を選択し、プロセッサ設計の要求を満たすようにすることができる。値マップ内の１ビットは、メモリ内のその位置に、圧縮前のように、瑣末でない浮動小数点数または整数値が存在することを示す。各値は１つのビットで表されるので、値マップはビットマップとして参照することができる。図５に、どのように混在（圧縮／非圧縮）構造体をメモリに記憶するかを示す。
【００２３】
提案する圧縮構造体の解凍ロジックにおける演算の基本的な原則は、値マップは、瑣末な値の存在を表すために使用されるということである。本出願の目的のためには、瑣末な値は単精度（３２ビット）の０．０である（Ｈｅｘでは、００００００００）が、同様の技術は、倍精度またはより精度の高い浮動小数点数に容易に拡張できる。あるいは、ある特定のデータセットにおいて０．０以外の数が多数ある場合は、ここに示した技術は、０．０でない数が値マップの０を表すように容易に拡張できる。例えば、１．０という値を多く含むデータセットもあり得る。
【００２４】
図５に示すデータ配列のＲＡＭアドレスの例からわかるように、３２ビットの値マップの各々の非零の入力（ｓｘ、ｓｙ、ｓｚ、ｘ０−ｘ３、ｙ０−ｙ３、ｚ０−ｚ３）に対して、オフセット「１」がベースアドレスに足される。実際には、メモリ内の値マップおよび次の構造のベースアドレスの両方が、現在の構造に埋め込まれ、プログラマーが読み出すことができる。
【００２５】
圧縮構造体を使用することは、プログラマーにとっては、圧縮構造体で記憶されたデータを記憶し読み出す際に、オーバーヘッドを減らすことに役立つ。本出願においては、プログラミングのオーバーヘッドは、プロセッサのＬＳＵ（Load-Store Unit）アドレス生成器内の圧縮データを記憶し読み出す際の複雑さを隠すことにより最小化される。プロセッサは、例えば、ＲＩＳＣプロセッサでもよい。アドレス生成器により、プログラマーは、どのデータ要素が圧縮構造体から読み出されるかを特定することができる。順々に、ＬＳＵは要求された要素をメモリ内の圧縮構造体から、全体の圧縮構造体を解凍することなく読み出すことができる。
【００２６】
したがって、ここに示す例示的な配列においては、アドレス生成器により、プログラマーは、３２入力の圧縮構造体から、どの８個の可能な４入力フィールド（ベクトル）を、単純な８ビットフィールドマスクを使って、読込み記憶するかを特定することができる。８ビットフィールドマスクは、図６に示す読込／記憶演算コードの中に含まれる。この例示的な配列においては、圧縮ベクトルを読込むための指示はＬＤＣＶであり、圧縮データを記憶するための指示はＳＴＣＶである。
【００２７】
この例示的な配列においては、プログラマーは、データがそこから読み出され、または、そこに記憶される、４入力のベクトルレジスタファイル（ＶＲＦ：Vector Register File）レジスタを特定することができる。アドレス生成器が圧縮構造体のオフセットおよび値マップを追加する整数レジスタファイル（ＩＲＦ：Integer Register File）内のベースレジスタもＩＲＦ内に登録する。演算コードは直近の８ビット値f[7:0]を含み、この８ビット値は、どの８個の４入力圧縮ベクトルが、実際にＶＲＦから読込まれ、ＶＲＦに記憶されるかを選択するために使用される。
【００２８】
ＬＳＵのポート幅は一般的に制限されているため、ＬＤＣＶおよびＳＴＣＶの指示は、複数のクロックサイクルを必要とすることを理解されたい。本出願の配列例では６４ビットに制限されている。結果として、値マップは、ｆビットの順に繰り返す方法で復号され、６４ビットの圧縮入力は、正しいＶＲＦレジスタへ書き込まれ、または、読み出され、また、ＬＳＵポートから見て正しいメモリ（ＲＡＭ）アドレスに記憶され、または、読み出される。図７に、６４ビットメモリサブシステムにおける典型的な圧縮構造体のＲＡＭ内でのレイアウトを示す。
【００２９】
この方法および配列は、３２ビットワードまたは６４ビット幅メモリに限定されるものではなく、類似のレイアウトが、９６または１２８ビット幅メモリなどを含む他のメモリ幅についても可能であることを理解されたい。しかし、説明を平易にするため、このような配列構成については、ここでは詳細に説明しない。
【００３０】
ＶＲＦは、完全な圧縮構造体のための段階領域として、圧縮読込みの場合は、その一部がプロセッサ内の他のレジスタファイルへ分散する前に使用することができる。または、その代わりに、ＶＲＦは、ＬＳＵポートに接続した外部ＲＡＭに圧縮構造体を記憶するための段階領域として使用することもできる。
【００３１】
図８を参照して、ＬＳＵのためのロジックの例を示す。この例は、所定のベースアドレス（base_addr）における圧縮構造体内部から値を読込むためのＬＳＵ圧縮構造体アドレス生成器のロジックである。加算器（圧縮器）の第１の行５０が提供され、８個の４ビット値マップフィールド（ｂｍ７〜ｂｍ０）に配列された３２ビットの値マップ構造体を、８個の３ビット数に圧縮する。各々の３ビット数は、与えられた４ビットの値マップ内の数を表す。加算器の第２の行５２は、圧縮器の行の結果を加算するために提供される。圧縮器は、各々の値マップの開始アドレスを生成し、これによって、各々の値マップフィールドは、圧縮した読込または記憶演算コードにおいて、適切なｆビットを適用して要求された場合に、独立してアドレスを指定することができる。ＡＮＤゲートの行５４が提供され、圧縮した読込／記憶演算コードにおいて、ｆ（フィールド）ビットセットの状態に応じて、要求されなかったフィールドをマスクする。これらのＡＮＤゲートの出力は、その後、さらなる加算器のセット５６により加算され、３２ビットワードの総数（word_cnt）を生成する。この総数は、演算コードのｆビットに基づいて、メモリから読込み、メモリへ記憶しなければならない。最後の［８：１］のマルチプレクサ段５８は、８フィールド実行信号により制御される。このフィールド実行信号により、選択され要求された値マップのアドレスを、要求されたＲＡＭアドレスを生成するために、最後の加算器６０に順に適用することができる。
【００３２】
図９に、圧縮データ構造体の例における様々な信号の値を示す。示したアドレスは、選択したＩＲＦ（整数レジスタファイル：Integer Register File）レジスタにおいて、値マップから静的に計算され、また、その後、圧縮した読込または記憶指示において特定されたｆビットの段階に応じて順に適用される。
【００３３】
図１０に、要求された制御信号を生成するためのカウンタおよび有限状態マシンを含む、圧縮した読込／記憶演算のための完全なアドレス生成ロジックを示す。
【００３４】
アドレス選択マルチプレクサに適用するアドレスの順番を選択するｆｅｎ［２：０］信号は、図１１に示す真理値表に従って動作する。
【００３５】
図１２に示すように、ソース／宛先アドレスは、ＬＳＵアドレス生成器によって生成された圧縮した読込／記憶演算のためにのみ要求されているのではなく、圧縮した読込／記憶演算において特定されたものに関連したソース／宛先ＶＲＦ行のためのソース／宛先アドレスも生成される。６４ビットＬＳＵバスの場合は、最大２行のＶＲＦ行に、圧縮した読込／記憶指示におけるアドレスを指定することができる。この配列の例においては、ＶＲＦは、圧縮した読込／記憶演算において、データを読込むソース、または、データを記憶する宛先として選択されたが、原則として、整数レジスタファイル（ＩＲＦ：Integer Register File）、または、スカラーレジスタファイル（ＳＲＦ：Scalar Register Rile）を、同じように選択することができる。
【００３６】
図１２の例示的なタイミング図は、明らかに、圧縮した読込／記憶演算は、実行に複数のサイクルを要することを示す。また、全ての必要な制御信号は、圧縮した読込／記憶制御ワードにおいて特定されたｆビットと結合して、圧縮構造体についてのＩＲＦの値マップ記述子の情報から生成されることを示す。制御信号のシーケンスは、アドレス生成器へのクロック入力により駆動されるカウンタとともに、ｆビットおよび値マップを用いて導かれる。
【００３７】
このタイミング図は、読込演算および記憶演算の両方についての動作を示す。２つの演算は、以下に示す点についてのみ異なる。
１．圧縮した読込の場合、読み出し信号が生成され、ＬＳＵポートに接続するＲＡＭから読み出される。書き込み信号は、ＲＡＭの内容への宛先として働く適切なＶＲＦ行のために生成される。実際には、一連のＲＡＭの読み出しおよびＶＲＦの書き込みは、ＩＲＦ内の値マップの状態、および、圧縮した読込演算コード内のｆビットセットに依存して生成される。
２．同様に、圧縮した記憶の場合、一連のＶＲＦの読み出しおよびＲＡＭの書き込みは、ＩＲＦ内の値マップの状態、および、圧縮した記憶演算コード内のｆビットセットに依存して生成される。
【００３８】
図１３に、ＳＶＵアーキテクチャのブロック図を示す。読込記憶部（ＬＳＵ:Load Store Unit）は圧縮した読込／記憶演算とともに、その一部を構成する。図に示すように、主要な外部とのインターフェースは、ＳＶＵ指示メモリへのものおよびＬＳＵポートであり、これらは、データメモリバンクとともにデバッグ制御部（ＤＣＵ：Debug Control Unit）に接続する。デバッグ制御部により、ＳＶＵレジスタおよび診断情報は、プロセッサバスを経由して読み出し、書き込むことができる。
【００３９】
指示ワードは、７個のスロットを有する。このスロットにより、指示ワードは、図１４に示すように、１サイクル中に９個の機能部のうち７個までを制御することができる。
【００４０】
本実施形態においては、１２８ビットの指示のうちの最も左のビットは、将来の機能のために予約されていて、残りの１２７ビットがフィールドに分割される。このフィールドのそれぞれは、プロセッサのアーキテクチャの好適な実施形態に含まれる９個の機能部のうちの１個の機能部を制御する。
１ｘ  基礎実行部（ＰＥＵ：Predicated Execution Unit）
１ｘ  分岐／繰り返し部（ＢＲＵ：Branch/Repeat Unit）
２ｘ  読込記憶部（ＬＳＵ：Load-Store Units）
１ｘ  ベクトル演算部（ＶＡＵ：Vector Arithmetic Unit）
１ｘ  スカラー演算部（ＳＡＵ：Scalar Arithmetic Unit）
２ｘ  整数演算部（ＩＡＵ：Integer Arithmetic Units）
１ｘ  比較／移動部（ＣＭＵ：Compare/Move Unit）
【００４１】
指示ワードの直接の制御下にない最後の機能部は、デバッグ制御部（ＤＣＵ：Debug Control-Unit）である。デバッグ制御部により、プロセッサは、特に例外的な条件、及び／又は、中断が発生した場合に、プログラムの実行を監視し制御することができる。
【００４２】
例示的なＬＳＵにより、プログラマーは、ベクトルデータをメモリからＶＲＦレジスタに読込むことができる。ＬＳＵは、２４ビットの演算コードにより制御され、８種類の演算のうちの１つの演算を実行することができる。
ＮＯＰ  メモリからデータを読込まない（省電力のためクロックがゲートによりオフされる）。
ＬＤＶＸ  メモリから４要素の非圧縮のベクトルを読込む。
ＳＴＶＸ  メモリに４要素の非圧縮のベクトルを記憶する。
ＬＤＣＶ  メモリから４要素の圧縮したベクトルを読込む。
ＳＴＣＶ  メモリに４要素の圧縮したベクトル要素を記憶する。
ＬＤＬＩ  特定したＩＲＦレジスタの直近の16ビットを下位１６ビットに読込む。
ＬＤＨＩ  特定したＩＲＦレジスタの直近の16ビットを上位１６ビットに読込む。
ＣＰＸＩ  ＩＲＦ値マップのフィールド１〜８のサイズ／アドレスをＩＲＦベースレジスタにコピーする。
【００４３】
図１５に、ＬＳＵのための演算コードテーブルの例を示す。
【００４４】
図１６に、非圧縮の読込／記憶モードにおけるＬＳＵのブロック図を示す。このモードにおいては、「bru_hold」信号は、読込／記憶演算が完了するまで、ＢＲＵ内のプログラムカウンタ（ＰＣ：Program-Counter）が前に進むことを妨げる。読込および記憶が、1回のサイクルでは完了しないということは重要である。４要素が１回のサイクルで転送される（１２８ビット）よりは、４個要素が１または２回のサイクルで転送されなければならないからである。
【００４５】
図１７に、非零の値マップ生成のための、値マップ生成ロジックおよびＶＲＦへの読込／記憶パスのブロック図を示す。非圧縮の４要素のベクトルがメモリからＶＲＦへ読込まれるときはいつも、追加の４入力非零値マップが、４個のコンパレータ（４個の３２入力ＮＯＲゲート）の行を用いて生成され、メモリから取り出されたデータとして対応するＶＲＦの行に挿入される。この４ビットの値マップの入力を後に用いて、データを圧縮フォーマットでメモリに記憶し、零値についての瑣末な演算を削除することによって、消費電力を最小にすることができる。
【００４６】
ここに記載するプロセッサアーキテクチャの比類のない能力は、全ての圧縮構造体を読み出す必要のない、ランダムアクセスの方法による、その圧縮データの読込および記憶へのサポートである。このサポートの理由は、多くの興味深いアプリケーションは、大量の疎データ、すなわち、メモリから取り出す必要がある多くの零を含むデータについて演算し、演算したときに零という結果を生成するからである。
【００４７】
このアーキテクチャの主要な前提は、プロセッサが取り扱う全てのデータは、４要素のベクトルにまとめられてメモリに記憶されるということである。これは、このデータが圧縮か非圧縮か、および、データが行列、ベクトル、まとまったスカラーまたは整数のいずれから構成されるかにかかわらない。この前提に基づいて、プログラマーは、行列／ベクトル／スカラー／整数データを、非零の入力のみが明確に記憶される３２入力の圧縮ブロックの中に構成してもよい。全ての零の値および非零の値は、非零の値マップにおいて１ビット入力により表わされる。この値マップは、３２入力をＲＡＭ内の３２または、それより少ない３２ビットワードに圧縮／解凍するために使用することができる。
【００４８】
図に示すような、３次元グラフィックスおよびゲームの物理(剛体力学)のアプリケーションに用いられる変換行列は良い例である。図２に、８個の行列に対応する３２ビットの値マップを示す。
【００４９】
図１８に示すように、グラフィック変換行列は、多くの割合の瑣末な値（零値）を含み、このことは、５０％以上のデータ圧縮を達成することを可能とする。
【００５０】
圧縮した値マップを用いることにより、プログラマーが定義した複雑なデータ構造体へのランダムアクセスは、図１９に示すハードウェアを用いて可能となる。圧縮した読込演算により、プログラマーは、ＩＲＦにおいて特定されたベースアドレスの最初のアドレスからの演算コードにおいて８ビットフィールドにより特定された一連の最大８個のＡ要素値を集めることができる。ハードウェアは、自動的に、必要なアドレスを生成し、信号を読み出し、また、複数のサイクルの読込を必要とする場合、例えば、４個以上の非零をメモリから読込まなければならない場合に、ＢＲＵをホールドするためのホールド信号も生成する。その一方、従来技術においては、このタイプの複雑なスキャッタ・ギャザー機能性は、典型的には、複雑なデータ構造体のインデックスを作成するために、複数のレジスタをベースアドレスおよびオフセットによりセットアップすることを必要とする、従来のプロセッサアーキテクチャで達成するのは複雑である。その上、このような従来のプロセッサのアーキテクチャは、瑣末なデータ値を圧縮するための準備をしない。
【００５１】
好適には、ＬＳＵのポート幅は、例えば、レジスタにおける入力として与えられたパラメータを用いて、独立して設定する。図２０に示すようにＳＶＵのＬＳＵポートに接続された１／２／４要素幅データバスにわたる複数のトランザクションにおいて、４要素のベクトルを読込／記憶できるようにすることによって、このポート幅のパラメータにより、最上位のＳｏＣの相互接続をＳＶＵのスループットと交換することができる。
【００５２】
ポート幅のパラメータ化を支えるための追加アドレスｌｓｂｓの生成は、カウンタを用いて実行される。このカウンタは、０個、１個または２個のアドレスのｌｓｂｓを、図２１に示すＬＳＵにより生成されたアドレスに付け加える。
【００５３】
図２２に、ＳＶＵのＲＡＭへの４要素の記憶へのポート幅パラメータの効果を示す。図に示すように、１２８ビットのベクトルを読込または記憶するために要するサイクル数は、ポート幅が１（３２ビット）のときは４サイクル、ポート幅が２（６４ビット）のときは２サイクル、および、ポート幅が４（１２８ビット）のときは１サイクルである。
【００５４】
本出願は、メモリとプロセッサ間のデータ転送を実行するための特定された演算コードを有する指示セットを備えるプロセッサについて記載してきたが、プログラム記憶装置に明示的な指示セットがない場合も機能を実行することができ、むしろ、読込および記憶は、ステートマシンまたは他の手段の制御の下に実行されることを理解されたい。重要な利点は、１つまたはそれ以上のデータ項目を、全体の圧縮構造体を読み出し解凍する必要なく、メモリ内の圧縮構造体から取り扱うことができるということである。同様に、データの１項目を、全体の圧縮構造体を読み出しまたは解凍する必要なく、メモリに記憶された圧縮構造体において更新することができる。
【００５５】
この明細書においては、「含む／備える（ｃｏｍｐｒｉｓｅｓ／ｃｏｍｐｒｉｓｉｎｇ）」の用語は、決まった特徴、整数、ステップまたは要素の存在を特定することものである。しかし、１つまたはそれ以上の特徴、整数、ステップ、要素またはこれらのグループの存在または追加を排除するものではない。
【図１】
2011511986.tif 000003
【図２】
2011511986.tif 000004
【図３】
2011511986.tif 000005
【図４】
2011511986.tif 000006
【図５】
2011511986.tif 000007
【図６】
2011511986.tif 000008
【図７】
2011511986.tif 000009
【図８】
2011511986.tif 000010
【図９】
2011511986.tif 000011
【図１０】
2011511986.tif 000012
【図１１】
2011511986.tif 000013
【図１２】
2011511986.tif 000014
【図１３】
2011511986.tif 000015
【図１４】
2011511986.tif 000016
【図１５】
2011511986.tif 000017
【図１６】
2011511986.tif 000018
【図１７】
2011511986.tif 000019
【図１８】
2011511986.tif 000020
【図１９】
2011511986.tif 000021
【図２０】
2011511986.tif 000022
【図２１】
2011511986.tif 000023
【図２２】
2011511986.tif 000024
【国際調査報告】
2011511986.tif 000025
2011511986.tif 000026