(57)【要約】線形増分ランレングス値、不連続に対応する変位値、およびループ圧縮を使用する圧縮を提供する、高速プログラムトレーサ。プログラムカウントシーケンサは、プロセッサからプログラムカウント値を受け取り、種々のプログラムカウント値および信号を出力し、それによって、線形増分ランレングス、不連続検出、および反復命令ループの検出に基づいて圧縮計算を行うことが可能となる。圧縮は、種々の圧縮値を表す選択された数のワードを使用して達成することができる。
2005502123.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサ上で実行中のプログラムの実行順序を追跡するプログラムトレーサにおいて、前記プロセッサが、プログラム命令を実行中に、該プログラム命令に対するプログラム命令カウント値を維持する、プログラムカウンタを有する前記プログラムトレーサであって、
前記プログラムカウンタに動作可能に接続されて、前記プログラムカウンタから現行プログラムカウント値を受け取るとともに、プログラム命令フロー中の不連続の通知を受け取るプログラムカウントシーケンサであって、前記通知に応答して現行不連続行先カウント値を生成する、前記プログラムカウントシーケンサと、
前記プログラムカウントシーケンサに動作可能に結合されて前記現行プログラムカウント値および前記現行不連続行先カウント値を受け取り、線形増分ランレングスを計算して、プログラム中の不連続の通知に応答して前記線形増分ランレングス値を選択的に供給する、線形増分ジェネレータモジュールとを含む、前記プログラムトレーサ。
【請求項２】
プログラムカウントシーケンサに結合されて現行プログラムカウント値および先行プログラムカウント値を受け取るとともに、それに応答して変位値を計算する、変位ジェネレータモジュールをさらに含む、請求項１に記載のプログラムトレーサ。
【請求項３】
変位ジェネレータモジュールが、プログラム中の不連続の通知に応答して、変位値を選択的に供給する、請求項１に記載のプログラムトレーサ。
【請求項４】
プロセッサ上で実行中のプログラムの実行順序を追跡するプログラムトレーサにおいて、前記プロセッサが、プログラム命令を実行中に該プログラム命令に対するプログラム命令カウント値を維持する、プログラムカウンタを有する、前記プログラムトレーサであって、
前記プログラムカウンタから現行プログラムカウント値を受け取り、先行プログラムカウント値を維持するとともに、現行不連続発生カウント値および現行不連続行先カウント値を決定するプログラムカウントシーケンサと、
該プログラムカウントシーケンサに結合されて、前記現行不連続発生カウント値および現行不連続行先カウント値を受け取り、第１の先行不連続発生カウント値および第１の先行不連続行先カウント値を維持するとともに、前記現行不連続発生カウント値および前記現行不連続行先カウント値を、前記第１の先行不連続発生カウント値および前記第１の先行不連続発生カウント値と、それぞれ比較することによって、少なくとも第１のループのループ実行を計数する、ループカウントモジュールとを含む、前記プログラムトレーサ。
【請求項５】
プログラム命令を実行中に、該プログラム命令のプログラム命令カウント値を維持するプログラムカウンタを有するプロセッサ上で実行するプログラム実行順序を追跡する方法であって、
不連続の通知に応答して、現行不連続行先カウント値を生成するステップと、
前記現行不連続行先カウント値および現行プログラムカウント値に基づいて線形増分ランレングスを計算するステップとを含む、前記方法。
【請求項６】
プログラム中の不連続の通知に応答して、線形増分ランレングス値を選択的に供給するステップをさらに含む、請求項５に記載の追跡方法。
【請求項７】
プログラム命令の実行中に、該プログラム命令のプログラム命令カウント値を維持するプログラムカウンタを有するプロセッサ上で実行されているプログラムの実行順序を追跡する方法であって、
現行不連続発生カウント値および現行不連続行先カウント値を決定するステップと、
現行不連続発生カウント値および現行不連続行先カウント値を、第１の先行不連続発生カウント値および第１の先行不連続行先カウント値と比較することによって、少なくとも第１のループのループ実行を計数するステップとを含む、前記方法。
【発明の詳細な説明】
【詳細な説明】
【０００１】
関係する出願
本出願は、３５Ｕ．Ｓ．Ｃ．１１９（ｅ）に基づき、２００１年８月２９日出願のAllenらの「ディジタルベースバンドプロセッサ（"DIGITAL BASEBAND PROCESSOR," by Allen, et al.）」という名称の米国特許仮出願第６０／３１５，６５５号の利益を主張するものである。前記の仮出願の全文を本明細書に参照により組み入れる。
発明の分野
本発明は、一般的にはプログラム追跡に関し、より具体的には、高速プログラム追跡を容易化するためのデータ圧縮を提供する方法および装置に関する。
【０００２】
発明の背景
プログラムトレーサは、マイクロプロセッサ、ディジタル信号プロセッサ、有限状態機械またはその他のプロセッサ装置（本明細書では総括的に、「プロセッサ」と呼ぶ）上で実行されているプログラムの実行順序を追跡する能力を提供する。実行順序は、一般に、プログラムカウンタ（ＰＣ）からのプログラムカウント値のログ（すなわち、プログラムトレース）（例えば、アドレス、または実行されているプログラム命令に対応するアドレスの表現）を維持することによって追跡される。このログは、プログラムをデバッグしたり、その実行を分析したりする目的で、機械翻訳によって、テキストフォーマット、グラフィカルフォーマットまたはその他の、人が読み取り可能なフォーマットにすることができる。プログラム追跡は、プログラムの実行順序に対する動的な視点を提供する。このような視点は、プログラム、コンパイラの効率または速度の改善、プログラムロジックの研究や、プロセッサ装置のプログラムをコンパイルするコンパイラの効率または動作を研究する活動において有用である。
【０００３】
プログラムカウント値は、それぞれのプログラム命令に対して１６ビットまたは３２ビットのアドレスデータを含むことがあり、また新規命令は通常、プロセッサデバイスのクロックサイクル毎に利用可能であるので、単に純粋なプログラムカウント値を出力することによってプログラムを追跡することは、負荷が大きいとともに、大量の物理的資源を必要とすることになる。例えば、各ＰＣ値を、トレーサが実装される集積回路からの出力とすると、多数の（関連回路を伴う）専用ピンが必要となる可能性がある。また、プログラムカウンタ出力に加えて、プログラムトレーサが、プログラムカウント値をその他のデータ値（例えば、実行順序に対する洞察を提供するデータレジスタ値）と多重化することがあるので、さらなる需要が生じる可能性がある。物理的資源需要に加えて、大量のデータの出力によって、データを転送するために必要な信号を生成するための、過剰な電力需要が生じることになる。
【０００４】
したがって、合理的な量の物理資源を使用してプログラムトトレーサ機能を達成するためには、プログラムカウント値を直列化（すなわち、３２ビットプログラムカウント値がバッファされて、連続する８ビットセグメントとして出力）して、圧縮方式を実装することができる。例えば、そのような方式においては、最も一般的なプログラムフロー事象が命令の順次実行である（すなわち、プログラムカウント値は、それぞれの連続する命令と共に、プログラム「コード」の次のラインへ１だけ増分する）ので、プログラムトレーサは、プログラムカウント値全体を出力するのではなく、プログラムカウント値において単一の増分が発生したことを示す値を出力する。さらに、不連続の事象においては、プログラムトレーサは、変位値を出力する。すなわち、プログラムトレーサは、不連続の実行後の完全なプログラムカウント値ではなく、不連続を実行する前のプログラムカウンタ値（不連続発生プログラムカウンタ値（discontinuity source program counter value）とも呼ばれる）と不連続を実行後のプログラムカウンタ値（不連続行先プログラムカウンタ値（discontinuity destination program counter value）とも呼ばれる）との間の符号付き差分の表示を提供する。「不連続（discontinuity）」の用語は、本明細書においては、プログラム中における非連続のプログラムカウント値を有する命令の実行として定義され、例えば、不連続は、ジャンプ、呼出し、または分岐の実行によって生じる。
【０００５】
このようなプログラムトレーサ機能は、プログラムの実行を追跡するのに必要なデータの低減を可能にしたが、従来式の圧縮方式ではデータの損失が発生し、このためにプログラム追跡が不完全となった。データの損失は、プログラムトレーサによるデータ出力が過剰であることによって発生することがある。例えば、直列化バッファのような内部バッファが、データ量が理由で、オーバフローする可能性がある。したがって、追跡に割り当てる資源とデータ損失の許容レベルとの間で妥協を図る必要がある。
そこで必要とされるのは、データ損失の発生が少ない、改良型圧縮方式を有するプログラムトレーサである。さらに、必要とされるには、物理資源需要が低く、かつ電力需要が低いプログラムトレーサである。
【０００６】
発明の概要
本発明の態様によるプログラムトレーサは、比較的高い圧縮係数を提供する。本発明のいくつかの態様は、線形増分ランレングス、ループ圧縮を提供するプログラムトレーサを目的としている。
本発明の第１の態様は、プロセッサ上で実行中のプログラムの実行順序を追跡するプログラムトレーサにおいて、前記プロセッサが、プログラム命令を実行中に、該プログラム命令に対するプログラム命令カウント値を維持するプログラムカウンタを有する、前記プログラムトレーサであって、前記プログラムカウンタに動作可能に接続されて、前記プログラムカウンタから現行プログラムカウント値を受け取るとともに、プログラム中の不連続の通知を受け取るプログラムカウントシーケンサであって、前記通知に応答して現行不連続行先カウント値を生成する、前記プログラムカウントシーケンサと、前記プログラムカウントシーケンサに動作可能に結合されて前記現行プログラムカウント値および前記現行不連続行先カウント値を受け取り、線形増分ランレングスを計算して、プログラム中の不連続の通知に応答して前記線形増分ランレングス値を選択的に供給する、線形増分ジェネレータモジュールとを含む、前記プログラムトレーサである。
【０００７】
いくつかの実施態様においては、プログラムトレーサは、プログラムカウントシーケンサに結合されて現行プログラムカウント値および先行プログラムカウント値を受け取るとともに、応答して変位値を計算する、変位ジェネレータモジュールをさらに含む。任意選択で、変位ジェネレータモジュールは、プログラム中の不連続の通知に応答して、変位値を選択的に供給する。
本発明の第２の態様は、プロセッサ上で実行中のプログラムの実行順序を追跡するプログラムトレーサにおいて、前記プロセッサが、プログラム命令を実行中に該プログラム命令に対するプログラム命令カウント値を維持するプログラムカウンタを有する、前記プログラムトレーサであって、本発明の第２の態様は、前記プログラムカウンタから現行プログラムカウント値を受け取り、先行プログラムカウント値を維持するとともに、現行不連続発生カウント値および現行不連続行先カウント値を決定するプログラムカウントシーケンサと、該プログラムカウントシーケンサに結合されて、前記現行不連続発生カウント値および現行不連続行先カウント値を受け取り、第１の先行不連続発生カウント値および第１の先行不連続行先カウント値を維持するとともに、前記現行不連続発生カウント値および前記現行不連続行先カウント値を、前記第１の先行不連続発生カウント値および前記第１の先行不連続発生カウント値と、それぞれ比較することによって、少なくとも第１のループのループ実行を計数する、ループカウントモジュールとを含む、前記プログラムトレーサである。
【０００８】
本発明の第３の態様は、プログラム命令を実行中に、該プログラム命令のプログラム命令カウント値を維持するプログラムカウンタを有するプロセッサ上で実行するプログラム実行順序を追跡する方法であって、不連続の通知に応答して、現行不連続行先カウント値を生成するステップと、前記現行不連続行先値および現行プログラムカウント値に基づいて線形増分ランレングスを計算するステップとを含む、前記方法である。実行順序を追跡する方法は、プログラム中の不連続の通知に応答して、線形増分ランレングス値を選択的に供給するステップをさらに含む。
【０００９】
本発明の第４の態様は、プログラム命令の実行中に、該プログラム命令のプログラム命令カウント値を維持するプログラムカウンタを有するプロセッサ上で実行されているプログラムの実行順序を追跡する方法であって、現行不連続発生カウント値および現行不連続行先カウント値を決定するステップと、現行不連続発生カウント値および現行不連続行先カウント値を、第１の先行不連続発生カウント値および第１の先行不連続行先カウント値と比較することによって、少なくとも第１のループのループ実行を計数するステップとを含む、前記方法である。
【００１０】
詳細な説明
本発明の、説明のためであり非限定の実施態様を、添付の図面を参照して、例を挙げて説明するが、図面においては、異なる図における同一の部品は、同一の参照番号を使用して表している。
図１は、プログラムトレーサシステム１００と追跡すべきプログラムを実行するプロセッサ１５０の機能ブロック図である。プロセッサ１５０は、プログラム命令を実行することができ、かつ実行されているプログラム命令に対する、プログラムカウント値（例えば、アドレスまたは実行中のプログラム命令に対応するアドレスの表現）を維持するプログラムカウンタ（ＰＣ）１５２を有する、任意の装置とすることができる。例えば、プロセッサ１５０は、マイクロプロセッサ、ディジタル信号プロセッサ、または有限状態機械とすることができる。好ましくは、プロセッサ１５０は、不連続の通知１５６を生成して、プログラム実行における不連続を表示する。例えば、プログラム実行における不連続の通知は、割込み、分岐、呼出し、復帰の命令、またはゼロオーバヘッドのハードウエアループの実行時に生成することができる。代替方法として、プログラムトレーサ１１０またはその他の資源が、直前のＰＣ値を現行ＰＣ値と比較して、不連続を検出して合図することができる。
【００１１】
プログラム追跡システム１００は、プログラムカウンタ１５２からの現行プログラムカウント値１５４と、不連続の通知１５６とを受け取る、プログラムトレーサ１１０を含む。現行プログラムカウント値１５４は、任意の長さ（例えば、１６ビットまたは３２ビット）とすることができる。以下にさらに詳細を示すように、プログラムトレーサ１１０は、１つまたは２つ以上の変位値１１２、および１つまたは２つ以上の線型増分ランレングス値１１３を含む、プログラムトレースの圧縮出力１１１を生成する。
【００１２】
任意選択で、データコントローラ１２０を含めて、プログラムトレーサシステム１００が、圧縮出力１１１と多重化された出力補助データ１５３を出力できるようにすることができる。例えば、補助データ１５３には、タイミング情報または追跡されるプログラムの実行中にプロセッサ１５０によって生成されるデータ値を含めることができる。メモリデバイス１３０を設けて、出力１１４を記憶するとともに、出力デバイス１４０を含めて、出力１１４の分析を可能にすることができる。デコンプレッサ（decompressor）１４５を設けて、圧縮された出力１１４を復元して、実行された命令の順序を再構成することができる。提示デバイス１４０は、ＣＲＴや液晶ディスプレイなどのディスプレイ装置、プリンタ装置、またはその他の提示デバイスとすることができる。
【００１３】
出力１１４は、通常、長さｎ（例えば８ビット）を有し、その長さはプログラムカウント値１５４の長さｍ（例えば、３２ビット）よりも短い。長さの低減は、データ圧縮や、直列化によって生じることがある。
図２は、本発明の少なくともいくつかの態様による、プログラムトレーサ１１０の例示的実施態様の機能ブロック図である。プログラムトレーサ１１０は、プログラムカウントシーケンサ２１２、変位ジェネレータモジュール（displacement generator module）２２０、線型増分ジェネレータモジュール（linear increment generator module）２３０、およびループカウントモジュール２４０を含む。「プログラムカウント値」は、本明細書では、「カウント値」または「ＰＣ値」とも呼ぶ。
【００１４】
プログラムカウントシーケンサ２１２は、プログラムカウンタ１５２（図１に示す）からの現行ＰＣ値１５４、および不連続の通知１５６を受け取り、現行プログラムカウント値１５４、先行ＰＣ値２１４、現行不連続行先ＰＣ値２１６、および現行不連続発生ＰＣ値２１８を供給する。現行不連続行先ＰＣ値２１６および現行不連続発生ＰＣ値２１８は、最近の不連続の、不連続発生ＰＣ値および不連続行先ＰＣ値をそれぞれ参照する。
線型増分ジェネレータモジュール２３０は、動作可能にプログラムカウントシーケンサ２１２に結合されて、先行プログラムカウント値２１４および現行不連続行先プログラムカウント値２１６を受け取るとともに、線型増分ジェネレータ２３２を含み、線形増分ランレングス値２３８を計算する。「線形増分ランレングス」の用語は、本明細書においては、最近の不連続と、先行の不連続との間に実行されたプログラム命令数に等しいと定義する。既知のＰＣ値と線形増分ランレングス値を組み合わせると、プログラムトレースの部分の圧縮表現が形成されることを理解されたい。
【００１５】
線形増分コンプレッサ２３４を含めて、線形増分ランレングス値２３８を圧縮することができる。以下に記述するように、線形増分コンプレッサ２３４は、増分ランレングス値２３８の絶対値に応じて、線形増分ランレングス値を表す選択された数のデータワードを供給する。任意選択で、コンプレッサ２３４は、線形増分ランレングス値を直列化してもよい。さらに、線形増分コンプレッサ２３４は、線形増分ランレングス値の選択された数のデータワードに対応するワードカウント２６３を供給することができる。
任意選択で、バッファ２３６は線形増分ジェネレータモジュール２３０の出力に結合されて、一時的に線形増分ランレングス値２３８を記憶することができる。バッファ２３６は、例えば、先入れ先出し（ＦＩＦＯ）バッファとすることができる。線形増分ランレングス値２３８は、例えば、コンプレッサ２３４によるデータの直列化によるか、またはデータコントローラ１２０（図１に示す）がプログラムトレーサに含まれて、それによってデータコントローラ１２０を介して高優先順位のデータが出力されている間、線形増分ランレングス値２３８をバッファ２３６に蓄積することができるので、バッファ２３６内に蓄積することができる。
【００１６】
いくつかの実施態様においては、線形増分ジェネレータモジュール２３０は、線形増分ランレングス値を、プログラムカウントシーケンサ２１２から受け取るそれぞれの先行プログラムカウント値２１４に対する出力として計算する。すなわち、それぞれの現行プログラム値に対して、線形増分値は１だけ増加する。しかしながら、不連続の時刻に存在する、線形増分ランレングス値だけが、正確なプログラム追跡を維持するのに必要であるので、プログラムトレーサ１１０のいくつかの実施態様においては、「不連続の通知」１５６は、線形増分モジュール２３０に供給されて、線形増分モジュール２３０が、プログラム中の不連続の通知に応答して線形増分ランレングス値を選択的に供給することを可能にする。「不連続の通知」１５６を使用することによって、いくつかの方法で、線形増分モジュール２３０が、「不連続の通知」がない場合に、線形増分ランレングス値を供給するのを防止することができる。例えば、「不連続の通知」１５６を受け取るときだけにランレングス値を記憶するように、バッファ２３６を構成することによって、それ以外の線形増分ランレングス値を廃棄することができる。
【００１７】
変位ジェネレータモジュール２２０は、変位ジェネレータ２２２を含むとともに、プログラムカウントシーケンサ２１２に動作可能に結合されて、現行プログラムカウント値１５４および先行プログラムカウント値２１４を受け取る。変位ジェネレータ２２２は、現行プログラムカウント値１５４と先行プログラムカウント値２１４との差を計算することによって、プロセッサ１５０（図１に示す）によって実行されるプログラムの命令実行順序に対応する変位値２２８を計算する。
【００１８】
プログラムトレーサ１１０のいくつかの実施態様においては、変位ジェネレータモジュール２２０は、プログラムカウントシーケンス２１２から受け取る、それぞれの現行プログラムカウント値１５４に対する変位値を計算する。しかしながら、正確なプログラム追跡を維持するためには、不連続の時刻に存在する変位値のみが必要であるので、プログラムトレーサ１１０のいくつかの実施態様においては、プログラム中の不連続の通知に応答して変位値２２８を選択的に供給するために、「不連続の通知」信号１５４が、変位ジェネレータモジュール２２０に供給される。すなわち、不連続の通知を受け取っている場合には、変位値２２８は、変位ジェネレータモジュール２２０からだけ出力される。
【００１９】
「不連続の通知」１５４を使用して、いくつかの方法で、「不連続の通知」がない場合に、変位ジェネレータモジュール２２０が変位値を供給するのを防止することができる。例えば、バッファ２２６を「不連続の通知」２５６を受け取ったときのみに、変位値を記憶するように構成し、コンプレッサ２２４が出力を供給するのを防止することができる。代替方法として、マルチプレクサ２７０が変位値を転送するのを防止することができる。
変位コンプレッサ２２４を含めることによって、変位値２２８を圧縮することができる。下記のように、変位コンプレッサ２２４は、変位値２２８の絶対値に応じて、選択された数のデータワードを供給する。任意選択で、変位コンプレッサ２２４は、変位データを直列化してもよい。さらに、変位コンプレッサ２２４は、選択された数のデータワードに対応するワードカウント２６２を供給することができる。
【００２０】
任意選択で、バッファ２２６は、変位ジェネレータモジュール２２０に結合して、一時的に変位値２２８を記憶することができる。バッファ２２６は、例えば、先入り先出し（ＦＩＦＯ）とすることができる。例えば、コンプレッサ２２４によるデータの直列化によるか、またはデータコレクタ１２０（図１に示す）がプログラムトレーサに含まれ、それによって、高優先順位データがデータコントローラ１２０を介して出力される間に、変位値２２８がバッファ２２６に入れることを要求されるので、変位値２２８はバッファ２２６に蓄積することができる。
図５に参照して以下に述べるように、一般に、データコントローラ１２０（図１を参照）は、バッファ２２６および２３６の対から変位値２２８および線形増分ランレングス値２３８を読み取り、このバッファ対２２６，２３６は、１つの変位値とそれに対応する１つの線形増分ランレングス値を含む。
【００２１】
任意選択で、所与の不連続が、固定のプログラムカウンタ値を有する行先を有する命令（例えば、既知のプログラムカウンタ値を有する既知の行先を有するジャンプまたは呼出し）によって生成されたことを示す信号２２６を、変位ジェネレータモジュール２２０に供給し、信号２２６を受け取るときに、変位値を抑制して、コンプレッサ２２４によって（図２の３０２に示すような）空白値を出力２２８に供給してもよい。
いくつかの実施態様においては、空白値は、データコントローラ１２０に無視されて、その結果、空白値を処理するのに時間を消費されることがない。当業者であれば理解するであろうが、そのような抑制されたプログラム実行順序を再構成するには、プログラムを参照して、適当な変位値を決定しなくてはならない。
【００２２】
ループカウントモジュール２４０は、少なくとも１つの内部ループカウンタ２４２を含む。ループカウントモジュール２４０は、プログラムカウントシーケンサ２１２に結合されて、現行不連続発生カウント値２１８および現行不連続行先カウント値２１６を受け取る。さらに、ループカウントモジュール２４０は、第１の先行不連続発生カウント値２４５および第１の先行不連続行先カウント値２４６を維持する。ループカウンタ２４２は、少なくとも第１のループのループ実行を、現行不連続発生カウント値２１８および現行不連続行先カウント値２１６を、第１の先行不連続発生カウント地２４５および先行不連続行先カウント値２４６と比較することによって、計数する。
【００２３】
現行不連続発生カウント値２１８および現行不連続行先カウント値２１６が、第１の先行不連続発生カウント値２４５および先行不連続行先カウント値２４６にそれぞれ等しいと判定すると、カウンタレジスタ２４９が増分される。
任意選択で、ループカウントモジュール２４０には、外部ループカウンタ２４３を含めて、第２のループのループ実行を計数してもよい。外部ループカウンタを有する実施態様においては、ループカウンタモジュール２４０は、第２の先行不連続発生カウント値２４７および第２の先行不連続行先カウント値２４８を維持する。現行不連続発生カウント値２１８および現行不連続行先カウント値２１６が、第２の先行不連続発生カウント値２４７および第２の先行不連続行先カウント値２４７にそれぞれ等しいと判定すると、カウンタレジスタ２４１が増分される。内部ループカウンタおよび外部ループカウンタだけについて論述したが、３つ以上のループカウンタを有するプログラムトレーサは、本発明の範囲の入るものである。
【００２４】
内部ループカウントコンプレッサ２４４および／または外部ループコンプレッサ２５４を含めて、内部ループカウントおよび外部ループカウントをそれぞれ圧縮することができる。内部ループカウントコンプレッサ２４４および外部ループカウントコンプレッサ２５４は、ループカウント２４８の絶対値に応じて、選択された数のデータワードを供給することができる。さらに、ループカウントコンプレッサ２４４、２５４は、それぞれが内部ループカウントおよび外部ループカウント内のデータワード数に対応する、ワードカウント２５１および２４５を供給する。図４を参照して以下に記述するように、内部ループカウンタおよび外部ループカウンタは、マルチプレクサ２７０および２７２を使用して、それぞれバッファ２２６および２３６に記憶することができる。マルチプレクサ２７２を使用して、ワードカウント２６２、２６３、２４５および２５１のそれぞれをバッファ２６０に記憶することができる。
【００２５】
図３は、本発明によるプログラムトレーサに使用するのに好適な圧縮方式の一例に使用するコード化値の表である。コード化値３０４、３０８、３１０は、線形増分値をコード化するのに使用することができる。例示的な圧縮方式においては、選択された数のワードを、線形増分値の絶対値に基づいて、線形増分値を表すのに使用する。接頭語３０４ａ、３０８ａ、３１０ａは、それぞれのコード化値３０４、３０８、３１０に存在し、それぞれの接頭語が、線形増分値を表すワード数を表す。同様に、符号ビット３０８ｂ、３１０ｂが、それぞれのコード化値３０８、３１０に存在する。
【００２６】
符号化値３０６、３０８、３１０、３１２は、変位値をコード化するのに使用することができる。この例示的な圧縮方式においては、選択された数のワードを、変位値の絶対値に基づいて、変位値を表すのに使用する。接頭語３０６ａ、３０８ａ、３１０ａ、３１２ａは、それぞれのコード化値３０６、３０８、３１０、３１２内にある。これらの接頭語は、線形増分値を表すワード数を表す。符号ビット３０６ｂ、３０８ｂ、３１０ｂ、３１２ｂがそれぞれのコード化値３０６、３０８、３１０、３１２内にあり、不連続には、正または負の不連続の場合があるので、符号ビットを使用して、正または負の不連続方向性を示す。
【００２７】
コード化値３１８、３２０を使用して、内部ループカウント値および外部ループカウント値をそれぞれ表すことができる。図示した例示的な圧縮方式においては、固定ワードカウントを使用している（すなわち、圧縮を行わない）が、上記のループカウント圧縮を行うことができることを理解されたい。例えば、上記の圧縮方式と同様に、選択された数のワードを使用して、ループカウントの絶対値に基づいて、ループカウント値を表すことができる。
カウントがゼロである場合、または変位値が上述のように抑制される場合には、コード化値３０２（本明細書では空白値とも呼ぶ）を使用することができる。変位抑制の事象においては、以下に記述するように、いくつかの実施態様においては、変位値および線形増分値が、対になったデータコントローラ１２０（図１に示す）によって交互に出力されるので、コード化値３０２をコンプレッサ２２４によって出力することができる。したがって、コード化値３０２は、場所ホルダとして動作する。いくつかの実施態様においては、コード化値３０２は、データコントローラ１２０によって認識されて、それを伝送することなく廃棄される。
【００２８】
圧縮値に加えて、コンプレッサ２２４、２３４、２４４、２５４は、完全プログラムカウンタ値を供給する必要があることがある。例えば、変位値または線形増分ランレングス値が大きすぎる（例えば、変位ジェネレータモジュール２２０または線形増分ジェネレータモジュール２３０内のレジスタがオーバフローする）場合には、対応するコンプレッサ２２４、２３４が、完全ＰＣ値を含むコード化値３１４を出力する。また、バッファ２２６および２３６の１つがオーバフローする場合には、対応するコンプレッサ２２４、２３４が、完全ＰＣ値を含むコード化値３１４を出力する。また、図示したコード化値に加えて、それぞれが追加の発生源からの出力（すなわち、図１の信号１５３）に対応する、コード化値を設けることができる。そのような出力に対応するコード化値によって、提示デバイス１４０が、そのような値を認識して反応することを可能になる。
【００２９】
図４は、本発明の少なくともいつくかの態様による、プログラムトレーサ１１０の例示的な実施態様の概略図である。プログラムトレーサ１１０は、プログラムカウントシーケンサ２１２、変位ジェネレータモジュール２２０、線形増分ジェネレータモジュール２３０、およびループカウントモジュール２４０を含む。
プログラムカウントシーケンサ２１２は、プログラムカウンタ１５２（図１に示す）からの現行プログラムカウント値１５４および「不連続の通知」１５６受け取る。現行ＰＣ値１５４は、１クロックサイクル遅延されて、フリップフロップのような遅延デバイス４１４によって維持されて、先行プログラムカウント値１１４を供給する。現行ＰＣ値は、追跡されているプログラムを実行中のプロセッサによって実行されている現行プログラム命令に対応するＰＣ値４０２である必要はない。例えば、実行されている現行プログラム命令のＰＣ値４０２を、遅延デバイス４０５によって遅延させることができる。しかしながら、先行ＰＣ値１１４は、現行ＰＣ値１５４の以前に１クロックサイクル存在したＰＣ値でなくてはならない。また「不連続の通知」１５６は、現行ＰＣ値１５４がＰＣ値４０２に対して遅延された量と等しい量だけ遅延させなくてはならない。
【００３０】
プログラムカウントシーケンサ２１２は、現行プログラムカウント値１５４および不連続の通知１５６を、論理ＡＮＤデバイス４１６（例えば、ＡＮＤゲート）に入力することによって、現行不連続行先ＰＣ値１１８を生成する。プログラムカウントシーケンサ２１２は、先行プログラムカウント値１１４および「不連続の通知」２５６を論理ＡＮＤデバイス４１９に入力することによって、現行不連続発生カウント値１１６を生成する。論理ＡＮＤデバイス４１５および遅延デバイス４１８は、先行不連続行先値４１３を線形増分ジェネレータモジュール２３０に供給するように動作する。線形増分ジェネレータモジュール２３０は、先行プログラムカウント値１１４および先行不連続行先カウント値４１３を受け取るとともに、先行プログラムカウント値１１４と先行不連続行先カウント値４１３との差を計算することによって線形増分ランレングスを計算する、差分デバイス４３２を含む。
【００３１】
線形増分ジェネレータモジュール２３０は、コンプレッサ４３４を含むことができる。コンプレッサ４３４は、任意好適な圧縮方式（そのいくつかは当該技術において公知である）を使用して、線形増分ランレングス値４３８を供給するのに必要な、ビットの総数を低減することができる。例えば、コンプレッサ４３４は、図３を参照して上述した圧縮方式を使用することができる。差分デバイス４３２によって計算される、線形増分ランレングス値は、選択された圧縮方式に従って、任意の方法を使用して、コード化値３０４、３０８、３１０に変換することができる。例えば、ルックアップテーブルを使用して、コード化値を供給するか、あるいは、差分の絶対値に基づいて、適当なヘッダーを差分デバイス４３２の出力に添付してもよい。
【００３２】
いくつかの実施態様においては、最高３つのワードが可能であるが、ヘッダーおよび符号データビットのために、線形増分ランレングス値を示すのに、最大１９ビットが利用可能である（すなわち、最大線形増分ランレングス値は２１９である）。差分デバイスの出力の絶対値が２１９を超えると、コンプレッサ４３４は、絶対ＰＣ値に対応するコード化値３１４（図３に示す）を供給する。
上述のように、いくつかの実施態様においては、コンプレッサ４３４は、線形増分ランレングス値４３８におけるワード数に対応する、ワードカウント４３９を提供する。図５を参照して以下に記述するように、データコントローラ１２０がワードカウントを使用して、圧縮追跡順序（compressed trace sequence）の出力を調整することができる。
【００３３】
変位ジェネレータモジュール２２０は、先行プログラムカウント値１１４および現行プログラムカウント値２５４を受け取るとともに、先行プログラムカウント値１１４と現行プログラムカウント値１５４との間の差分を計算することによって変位値４２８を計算するために、差分デバイス１２２を含む。変位生成モジュール２２０には、コンプレッサ４２４を含めることができる。コンプレッサ４２４は、任意の圧縮方式を使用して、変位値４２８を供給するのに必要な合計ビット数を低減することができる。例えば、コンプレッサ４２４は、図３を参照して上述した圧縮方式を使用することができる。差分デバイス４２２によって計算された変位値は、任意公知の方法を使用して、図３に示す圧縮方式に従うコード化値３０６、３０８、３１０、３１２に変換することができる。例えば、ルックアップテーブルを使用して、コード化値を供給するか、または、差分の絶対値に基づいて、適当なヘッダーを差分デバイス４２２の出力に添付することができる。
【００３４】
いくつかの実施態様においては、最大４ワードが可能であるが、ヘッダーおよび符号データビットのせいで、差分を示すのに、最大２５ビットが使用可能である（すなわち、最大差分量は２２５である）。差分デバイスの出力の絶対値が２２５を超える場合には、コンプレッサ４２４は、絶対ＰＣ値に対応する、コード化値３１４（図３に示す）を生成する。上述のように、いくつかの実施態様において、コンプレッサ４２４は、出力４２８におけるワード数に対応する、ワードカウント４２９を供給する。図５を参照して以下に述べるように、データコントローラ１２０がワードカウントを使用して、圧縮追跡順序の出力を調整することができる。
【００３５】
ループカウントモジュールは、少なくとも第１の先行不連続発生カウント値４４４および第１の先行不連続行先カウント値４４５とを含む、メモリ４４２（例えば、２×ｎＦＩＦＯバッファ）を含む。図示した例示的な実施態様において、メモリ４４２は、２×２ＦＩＦＯバッファであり、したがってこのメモリは、第２の先行不連続発生カウント値４４６および第２の先行不連続行先カウント値４４７も含む。メモリ４４２は、任意の数の先行不連続発生カウント数と、第１の先行不連続行先カウント値とを含むメモリ（例えば、２×ｎＦＩＦＯバッファ）とすることができることを理解されたい。
ループカウンタ２４０は、図に示すコンパレータ４４８および４４９を使用して、プログラムカウントシーケンサ２１２によって生成される、それぞれの先行プログラムカウント値１１４および現行プログラムカウント値１５４を、第１の先行不連続発生カウント数値４４４および第１の先行不連続行先発生カウント値４４５と、それぞれ比較する。先行プログラムカウント値１１４が、第１の先行不連続発生カウント値４４４に等しく、かつ現行プログラムカウント値１５４が、第１の先行不連続行先カウント値４４５に等しいことをＡＮＤデバイス４５２が示す場合には、内部ループカウンタ４５４が増分される。
【００３６】
いくつかの実施態様において、内部ループカウンタ４５４は、マルチプレクサ４８０を介してバッファ２２６（図２に示す）に内部ループカウントを供給する。さらに、内部ループカウンタ４５４は、マルチプレクサ４８２を介してワードカウントをバッファ２６０（図２に示す）に供給する。いくつかの例においては、内部ループカウンタ４５４は、図３に示すコード化値３１８に従う接頭語を生成する。図３に示す圧縮方式において、内部ループカウンタ値は圧縮されず（例えば、内部ループカウントに対するコード化値のワードカウントは、内部ループ値の絶対値に依存しない）、したがって、図３に示す方式による内部ループカウンタ値は、ハードワイアリングによって生成して、接頭語がカウント値に添付されるようにすることができる。代替手法として、ルックアップテーブルまたはその他の任意好適な方法を使用して、図３に示す方式に従うコード化値を生成することができる。図３に示す方式はループカウント値を圧縮しないが、ループ値圧縮を含む圧縮方式は、本発明の範囲に含まれるものであり、コンプレッサ２２４または２３４（図２に示す）と類似のループコンプレッサを組み込むことができることを理解すべきである。
【００３７】
同様に、ループカウンタモジュール４４０は、コンパレータ４５１および４５２を使用して、プログラムカウントシーケンサ２１２によって生成される、各先行プログラムカウント値１１４および現行プログラムカウント値１５４を、第２の先行不連続発生カウント値４４６および第２の先行不連続行先カウント値４４７とそれぞれ比較する。先行プログラムカウント値１１４が第２の先行不連続発生カウント値４４６に等しく、かつ現行プログラムカウント値２５４が第２の先行不連続行先カウント値４４７と等しいことをＡＮＤデバイス４５３が表示する場合には、外部ループ実行が表示される。したがって、外部ループカウンタ４５５が増分される。
【００３８】
いくつかの実施態様において、外部ループカウンタ４５５が、マルチプレクサ４８１を介して、バッファ２３６（図２に示す）に外部ループカウントを供給する。さらに、外部ループカウンタ４５５は、マルチプレクサ４８２を介して、バッファ２２０（図２に示す）にワードカウントを供給する。いくつかの実施例においては、外部ループカウンタ２５５は、図３に示すコード化値３２０に従う接頭語を生成する。図３に示す圧縮方式において、ループカウンタ値は圧縮されず、したがって、図３に示す方式による外部ループカウンタ値は、ハードワイアリングによって生成して、接頭語がカウント値に添付されるようにすることができる。代替方法としては、ルックアップテーブルまたはその他の任意好適な方法を使用して、図３に示す方式に従うコード化値を生成することができる。
【００３９】
マルチプレクサ４８０は、変位ジェネレータモジュール２２０および内部ループカウンタ４５４の両方が、バッファ２２６（図２に示す）を充填することを可能にし、マルチプレクサ４８１は、線形増分ジェネレータモジュール４３０および外部ループカウンタ４５５の両方が、バッファ２３６（図２に示す）を満たすことを可能にする。マルチプレクサ４８２は、コンプレッサ４２４、圧縮４３４、内部ループカウンタ４５４、および外部ループカウンタ４５５のそれぞれからの、ワードカウントがバッファ２６０（図２に示す）を満たすことを可能にする。
ＮＯＲデバイス（ゲート）４５７は、内部ループ実行または外部ループ実行の１つが示されない限り、論理ハイを生成する。したがって、［不連続の通知」２５６は、ＡＮＤデバイス４５８によって阻止され、それによってＡＮＤデバイス４１９、４１６が、更新された不連続発生ＰＣ値４４４および更新された不連続行先ＰＣ値４４５を供給するのを防止する。しかし、ＮＯＲデバイス４５７が、内部ループ実行と外部ループ実行の両方を示さない場合には、新規の不連続が発生する度に、メモリデバイス４４２が更新される。さらに、信号４５９（ゲート４５８の出力）を、変位発生モジュール２２０および線形増分ジェネレータモジュール２３０に供給して、内部ループまたは外部ループが存在することが示される場合には、変位値４２８および線形増分ラン値４３８が、計算されるのを防止することができる。
【００４０】
図５Ａは、例示的な圧縮データ構造を含む、バッファ２２６、２６０、２３６の概略図である。この例示的な実施態様において、それぞれのバッファは、ＦＩＦＯバッファであり、バッファの上部ワード（すなわち、１番目の位置、またはアドレス）におけるデータは、データの１番目である。バッファ２２６は、両方とも第１の変位値に対応する２ワードの変位データ、５０２ａおよび５０２ａ’と、すべてが第１の内部ループカウント値に対応する３ワードの内部ループカウントデータ、５０４ａ、５０４ａ’、５０４ａ”と、第２の変位カウント値に対応する１ワードの変位データ、５０６ａ’とを含む。
バッファ２３６は、第１の変位カウント値に対応する（かつ変位値５０２ａ、５０２ａ’に対応する）１ワードの線形増分カウントデータ５０２ｂと、両方が第１の外部ループカウント値に対応する、２ワードの外部ループカウントデータ５０４ｂおよび５０４ｂ’と、第２の線形増分カウント値に対応する（かつ変位カウントデータ５０６ａに対応する）、１ワードの線形増分データ５０６ｂ’とを含む。ワードカウントバッファ２６０は、バッファ２２６および２３６のそれぞれにおけるデータに対応するワードカウント値を含む。
【００４１】
例えば、好適にプログラムされたデータコントローラ（例えば、データコントローラ１２０）を使用して、バッファ５２６およびバッファ５３６から、変位データ、線形増分データ、内部ループデータ、および外部ループデータを読み取り、それらによって、統合された、圧縮プログラムトレースを形成することができる。統合されて、圧縮されたプログラムトレースは、次いで、デコンプレッサ１４５（図１に示す）によって復元されて、復元プログラムトレースが形成される。データの統合は、ワードカウント５０２、５０２’、５０４、５０４’、５０６、５０６’を読み取り、かつバッファ２２６およびバッファ２３６から、交番するワードカウントを使用して、対応する数のワードを読むことによって行われる。例えば、図示された例示的なデータ構造によれば、結果として得られる統合圧縮プログラムトレースは、バッファからのワードカウント５０２に対応する、バッファ２２６から２ワードのデータ５０２ａおよび５０２ａ’を最初に読み取ることによって形成される。次に、１ワードのデータ５０２ｂが、バッファ２６０からのワードカウント５０２’に対応する、バッファ２３６から読み取られる。次いで、バッファ２６０からのワードカウント５０２に対応する、バッファ５２６から、データ５０２ａおよび５０２ａ’の２ワードの３ワードが読み取られる。結果として得られる統合データを含むメモリ５５０を、図５Ｂに示してある。メモリ５５０は、バッファ２２６および２３６から読み取られるデータによって下部から上方に充填される。結果として得られる統合データの圧縮復元は、デコンプレッサ１４５（図１に示す）を使用して達成することができる。
【００４２】
以上のように本発明の概念と、いくつかの例示的な実施態様を記述したが、当業者には、本発明は種々の方法によって実施することが可能であり、かつ当業者であれば修正および改善を容易に思いつくであろうことは明白であろう。したがって、提示した実施例は、それらに限定することを意図するものではない。本発明は、添付のクレイムとその等価物によって要求されることによってのみ限定されるものである。また、用語「含む」、「具備する」、または「有する」などの用語は、その後に列挙される項目、およびその等価物、ならびに列挙する項目の前後、中間の追加の項目をも包含するものである。
【図面の簡単な説明】
【００４３】
【図１】プログラムトレーサシステムおよび追跡すべきプログラムを実行するプロセッサの機能ブロック図である。
【図２】本発明の少なくともいくつかの態様によるプログラムトレーサの例示的な実施態様の機能ブロック図である。
【図３】本発明によるプログラムトレーサに使用するのに好適な圧縮方式の一例に使用するコード化値を示す表である。
【図４】本発明の少なくともいくつかの態様による、プログラムトレーサの例示的な実施態様の概略図である。
【図５Ａ】例示的な圧縮データ構造を含む、バッファの概略図である。
【図５Ｂ】統合データ構造を含むメモリを示す図である。
【図１】
2005502123.tif 000003
【図２】
2005502123.tif 000004
【図３】
2005502123.tif 000005
【図４】
2005502123.tif 000006
【図５Ａ】
2005502123.tif 000007
【図５Ｂ】
2005502123.tif 000008
【国際公開パンフレット】
2005502123.tif 000009
2005502123.tif 000010
2005502123.tif 000011
2005502123.tif 000012
2005502123.tif 000013
2005502123.tif 000014
2005502123.tif 000015
2005502123.tif 000016
2005502123.tif 000017
2005502123.tif 000018
2005502123.tif 000019
2005502123.tif 000020
2005502123.tif 000021
2005502123.tif 000022
2005502123.tif 000023
2005502123.tif 000024
2005502123.tif 000025
2005502123.tif 000026
2005502123.tif 000027
2005502123.tif 000028
2005502123.tif 000029
2005502123.tif 000030
2005502123.tif 000031
2005502123.tif 000032
【国際公開パンフレット（コレクトバージョン）】
2005502123.tif 000033
2005502123.tif 000034
【国際調査報告】
2005502123.tif 000035
2005502123.tif 000036