【手続補正書】
【提出日】平成15年6月17日(2003.6.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の名称】プリンタ及び集積回路
【特許請求の範囲】
【請求項１】ａ．圧縮形式のプログラムを記憶するメモリと、ｂ．コンピュータから入力データを受け取るためのバッファと、ｃ．前記メモリと前記バッファとに結合され、前記入力データに応答して画像を決定するフォーマッタと、ｄ．前記画像を印刷する印刷エンジンと、を備え
前記フォーマッタが（１）前記メモリから前記プログラムの少なくとも一部分を受け取り、この一部分を圧縮解除して命令を送出する圧縮解除機構と、（２）前記命令を受け取って記憶するキャッシュと、（３）前記キャッシュからの命令を受け取り、かつ、該命令を実行して画像を決定するプロセッサと、
を備えることを特徴とするプリンタ。
【請求項２】 前記一部分が、前記メモリの複数の読出サイクルを有し、前記メモリが、読み出しアクセス用のページ・モードを有し、ｇ．中断しないページ・モードのアクセス中に前記複数の読出サイクルを処理する請求項１に記載のプリンタ。
【請求項３】 前記フォーマッタが、前記圧縮解除機構と、前記キャッシュと、前記プロセッサとを有する集積回路を備える請求項１又は請求項２のいずれか一項に記載のプリンタ。
【請求項４】 前記キャッシュが、ダイナミック・ランダム・アクセス・メモリのアレイを備える請求項１〜請求項３のいずれか一項に記載のプリンタ。
【請求項５】前記メモリが、第１幅を有する第１バスによって前記フォーマッタに結合され、前記キャッシュが、第２幅を有する第２バスによって前記圧縮解除機構に結合され、前記第１幅が、前記第２幅よりも狭いことを特徴とする請求項１〜請求項４のいずれか一項に記載のプリンタ。
【請求項６】ａ．実行可能命令を取り出すためのアドレスを送出するプロセッサと、ｂ．前記アドレスに応答して前記実行可能命令を送出するキャッシュとを備え、
前記キャッシュが（１）第１メモリと、（２）メモリからテーブルと情報ブロックとを読み出す圧縮解除機構とを備え、
（ａ）前記テーブルが複数の行を有し、前記各行が一連のタグ値のそれぞれのタグ値にそれぞれ対応しかつそれぞれのコード・ブロック値を識別し、（ｂ）前記情報ブロックが、データ項目を有し、（ｃ）前記圧縮解除機構が、前記第１メモリに、前記テーブルの行の前記各コード・ブロック値のコピーを記憶するとともに、
１）前記行のそれぞれのタグ値が、前記データ項目に応じて識別され、２）前記コピーが、実行可能命令を有し、３）前記コード・ブロック値が、前記データ項目よりも多い数のビットを有する集積回路。
【請求項７】 前記第１メモリが、ダイナミック・ランダム・アクセス・メモリを備える請求項６に記載の集積回路。
【請求項８】 前記キャッシュが、更に第２メモリを備え、前記圧縮解除機構が、該第２メモリに前記テーブルを格納する請求項６又は請求項７のいずれかに記載の集積回路。
【請求項９】ａ．第３メモリと、ｂ．前記第１メモリから前記コピーを読み出し、前記プロセッサによってアクセスのために前記実行可能命令の第２コピーを前記第３メモリに記憶するキャッシュ・コントローラとをさらに備える請求項６〜請求項８のいずれか一項に記載の集積回路。
【請求項１０】 ｃ．前記第１メモリが、ダイナミック・ランダム・アクセス・メモリを備え、ｄ．前記キャッシュが更に、（１）スタティック・ランダム・アクセス・メモリを有する第２メモリ、（２）第３メモリと、（３）前記第１メモリからコピーを読み出し、前記プロセッサによるアクセスのために前記実行可能命令の第２コピーを前記第３メモリに記憶するためのキャッシュ・コントローラとを備え、ｅ．前記圧縮解除機構は、前記メモリからマップを読み出し、前記第２メモリにテーブルとマップとを記憶し、前記マップに対応したメモリから情報ブロックを読み出す請求項６に記載の集積回路
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、プリンタ内のメモリに記憶されたプログラムを実行するプロセッサを備えたプリンタに関する。
【０００２】
【従来の技術】従来、レーザ・プリンタは、一般的に印刷エンジンと、印刷されるデータを受け取るための入力インターフェースと、受け取った前記データ（以下、入力データという。）に応じて印刷エンジンにデータを送出するプロセッサとを備えている。入力データは、伝統的に、Ｈｅｗｌｅｔｔ  Ｐａｃｋａｒｄ社が販売しているＰＣＬプリンタコントロール言語やＡｄｏｂｅ  Ｓｙｓｔｅｍｓ社が販売しているＰｏｓｔｓｃｒｉｐｔのページ記述言語などのページ記述言語（ ＰＤＬ）に適合する命令を有している。ＰＤＬにおいて様々な命令を実行可能にするために、通常、ＰＤＬ命令を処理するように記述されたプログラム（ＰＤＬ通訳：  ＰＤＬ  インタープリター）は、例えば、２Ｍバイト程にもなる。このようなＰＤＬ通訳プログラムは、従来、プリンタ内の読み出し専用メモリ（ＲＯＭ）に格納されている。
【０００３】一般的に、従来のレーザ・プリンタには、二つのタイプのメモリが使用されている。例えば、プロセッサが実行する命令を有するプログラムはＲＯＭ又は読出／書込メモリに記憶され、（印刷するために受け取ったデータを含め）プログラムにより使用される変数は、読出／書込メモリに記憶されている。メモリ・システムは拡張可能であり、これによって、工場又はユーザは、別の事前にプログラミングされたＲＯＭモジュールを追加できるようになり、その「組み込み」機能を追加することが出来る。工場又はユーザが、読出／書込メモリ機能のためにＲＡＭモジュールを追加することによって、単一シートに印刷する大量のデータ量に対する処理を拡張できるようになる。
【０００４】
【発明が解決しようとする課題】一般的に、ＲＯＭのアクセス時間は、ＲＡＭのアクセス時間よりも長い。したがって、ＲＯＭから取り出されたプログラム命令（例えば、ＰＤＬ通訳プログラム）は、ＲＡＭから取り出されたプログラム命令よりも、その実行が遅くなる。なお、ＲＡＭはＲＯＭよりもコストが高い。ユーザは、例えば、複雑な画像を印刷したり、（実行速度が速いためにＲＡＭに格納された）ダウンロードしたＰＤＬ通訳プログラムを記憶したりするために、プリンタにＲＡＭを追加することが出来るが、この場合、ＰＤＬ通訳プログラムが大量のＲＡＭを使用することになり、複雑な画像を印刷する際の能力が低下することがある。
【０００５】本発明によらなければ、ユーザがプリンタの性能を拡張する能力が制限されてしまうだろう。ユーザは、プリンタが、より複雑な画像を印刷し、かつ、更に精密なＰＤＬを解釈（通訳）することを望んでいる。多数の要因があるが、特にコストとシステムの信頼性とにより、ＲＡＭを単に追加することによってそれらの要求を満たす方策が制限されてしまう。システムソフトウェアの拡張に応じてプリンタの性能を拡張する能力を備えていない場合、従来のプリンタは直ちに時代遅れとなる。
【０００６】本発明は、このような従来の技術における課題を解決するものであり、プリンタの性能を拡張することが制限されずに、プログラムを効率的に記憶して実行できるプロセッサを有するプリンタの提供を目的とする。
【０００７】
【課題を解決するための手段】上記課題を達成するために、本発明の一つの実施形態におけるプリンタは、メモリと、バッファと、フォーマッタとを備えている。メモリは、プログラムを圧縮形式で記憶する。バッファは、コンピュータから入力データを受け取る。フォーマッタは、メモリとバッファとに結合され、入力データに応じて画像を決定する。フォーマッタは、圧縮解除（解凍）機構と、キャッシュと、プロセッサとを備えている。フォーマッタは、メモリからプログラムの少なくとも一部分を受け取り、この一部分を圧縮解除して命令を実行する。キャッシュは、命令を受け取って記憶する。プロセッサは、キャッシュから命令を受け取って、命令を実行することによって画像を決定する。印刷エンジンは、フォーマッタの決定に従って画像を印刷する。
【０００８】このような実施形態の第１態様によれば、メモリ内のプログラムの記憶に必要なアドレス領域が少なくなる。その結果、プリンタを更に多い又は長いプログラムの場合を同一コストで実現することが出来る。また、メモリの記憶量が減少し、プリンタの製造コストが低下する。
【０００９】第２態様によれば、キャッシュから取り出されたプログラムの実行は、メモリから取り出された拡張プログラムの実行よりも高速である。キャッシュの取り出しアクセス時間が、メモリの取り出しアクセス時間よりも高速の場合に、圧縮解除に必要な時間が短縮され、実質的な実行時間を短縮できる。
【００１０】他の一つの態様によれば、プログラム命令をメモリから取り出さずに、キャッシュから取り出す場合、印刷する画像を構成する入力データを解釈するためのプログラムの実行が迅速化される。実行時間が短いと、同一解釈要件に対する印刷速度を高めることが出来る。あるいは印刷速度に悪影響を与えることなく、より高精度な解釈が可能になる。
【００１１】本発明の一つの実施形態における集積回路は、プロセッサとキャッシュとを備えている。プロセッサは、実行可能な命令（以下、実行可能命令と記載する）を取り出すアドレスを送出する。キャッシュは、アドレスに応じて実行可能命令を送出する。キャッシュは、メモリと圧縮解除機構とを有している。この圧縮解除機構は、用意されたシステム・メモリからテーブルと情報ブロックとを読み出す。このテーブルは複数の行を有している。各行は、一連のタグ値から得たそれぞれのタグ値に対応する。また、各行は、それぞれのコード・ブロック値を識別する。情報ブロックは、データ項目を有している。
【００１２】圧縮解除機構は、キャッシュのメモリに、テーブルの選択された行の各コード・ブロック値のコピーを記憶する。選択された行は、データ項目によって識別されたタグ値を有する。コード・ブロックは、実行可能命令を有し、データ項目よりも多数のビットを有する。最終的な圧縮解除は、データ項目のコード・ブロック値の置換によるものである。
【００１３】このような実施形態の第１態様によれば、メモリ内のプログラムの記憶に必要なアドレス領域が少なくなる。したがって、この集積回路を使用するシステムは、より多数の又は長いプログラムを同一コストで提供し、あるいはシステム・メモリの記憶量を低減して、そのシステムの製造コストを削減できる。
【００１４】第２態様によれば、キャッシュから取り出されるプログラムの実行は、システム・メモリから取り出される拡張プログラムよりも高速である。キャッシュの取出しアクセス時間が、システム・メモリの取り出しアクセス時間よりも高速の場合に、圧縮解除に必要な時間が短縮され、実質的な実行時間を短縮できる。
【００１５】本発明の他の実施形態は、キャッシュから一連の実行可能命令を記憶する方法を提供する。
【００１６】この方法は、パターン・サイズを決定するステップと、一連の命令を、各コード・ブロック値を有し且つパターン・サイズを有する各コード・ブロックからなる一連のコード・ブロックに分割するステップと、一連の命令に各コード・ブロック値が発生するごとに、各コード・ブロック値と関連した各カウントを増分するステップと、一連のタグ値を決定し、各タグ値の行を有するテーブルを構成し、行に対応しないタグ値を決定するステップと、最大非選択カウントを対話式に選択し、テーブルに各タグ値に関して全ての行が満たされるまで各コード・ブロック値を格納するステップと、一連のコード・ブロックから一つのコード・ブロックを連続して対話式で読み出すことによって一連の情報ブロックを決定し、テーブルの行に対応する各コード・ブロック値ごとに、情報ブロック内で対応する行のタグ値を識別し、テーブル内に対応する行が存在しない場合は、情報ブロック内で各コード・ブロック値に続く行と対応しないタグ値を識別するステップと、テーブルのコード・ブロック値と情報ブロックのコード・ブロック値とに応じて、キャッシュが実行可能命令を有するようにキャッシュに書き込む圧縮解除機構によるアクセスのために、テーブルと一連の情報ブロックとをメモリに記憶するステップとを有している。
【００１７】このような方法における第１態様によれば、得られた情報ブロックが一連の命令よりも少ない領域を占有する。正味の圧縮は、一連の命令を記憶するコストが効果的に低減されて達成される。
【００１８】他の一つの態様によれば、パターン・サイズにおけるビット数が、一つの命令におけるビット数と相違することがある。これによって、圧縮のために繰り返す一群の命令を認識できるようになる。また、圧縮のためにいくつかの命令における繰り返しのビットのサブセットを認識することが出来る。
【００１９】
【発明の実施の形態】次に、本発明のプリンタの好ましい例示的な実施形態を、以下の図面を参照して以下に説明する。
【００２０】図１および図２の各機能ブロック図において、太い矢印は、２進コードを共に表す１群の信号を象徴的に表している。例えば、２進アドレスを、同時に得られた信号によって表示しており、一群のアドレスラインが太い矢印で表される。機能ブロック間の矢印は、一つ又は複数の信号を表している。
【００２１】本発明の態様による装置は、圧縮形式で記憶されたプログラムを実行する。プログラムの大規模な圧縮解除又は部分的な圧縮解除の後で、その実行が順次行われる。したがって、データ処理タスクを実行するために制限された内部メモリを有するコンピュータ・システム又はコンピュータ周辺装置において、特定の相乗作用が得られる。例えば、メモリ容量が制限されている際、多数の周辺装置のデータ処理タスクは、例えば、動作が遅延し、その結果精度が低下し、処理の中断が発生して（メモリ不足状態の障害で）、所定時間内に示される一連のタスクの完全な処理に対応できなくなる。
【００２２】本発明の態様によって、コンピュータ・システムとコンピュータ周辺装置は、例えば、物理的な監視と測定、特殊なデータ解析、プロセス制御、印刷、作図、データ記録、表示及びネットワーク通信などの幅広いデータ処理機能が処理されるため、その処理の複雑さが変化する。このようなコンピュータ・システムとコンピュータ周辺装置とは、プロセッサ（例えば、ＣＰＵ）と、サイズが制限された読出／書込メモリ（例えば、ＲＡＭ）と、サイズが制限されたプログラム記憶メモリ（例えば、ＲＯＭ）と、命令キャッシュとを有する内部機能アーキテクチャを備えている。これらの機能要素は、従来のように結合され、ＲＯＭから情報を読み出し、この情報を圧縮解除して命令キャッシュにプログラム命令を与える。このプログラム命令をＣＰＵ内で実行してＲＡＭ内の変数の値を変更するか、又は、出力信号を生成する。
【００２３】図１はプリンタ１００の構成を示すブロック図である。この図１のプリンタ１００は、コンピュータ周辺装置の一例であり、コンピュータ（図示しない）は、周辺装置としてプリンタ１００を使用する。コンピュータは、ライン１０１上でＰＤＬ命令（ＤＡＴＡ；入力データ）を使用して印刷する画像を記録する。プリンタ１００は、主な装置として、バッファに該当するインタフェースコントローラ１０６と、バスライン１１３と、フォーマッタ１０２と，ＲＯＭ１０８，ＲＡＭ１１２と、印刷エンジンコントローラ１１６と、印刷エンジン１１８とを備えている。
【００２４】従来の任意のディジタル回路で構成されたインタフェースコントローラ１０６は、ライン１０１上の信号ＤＡＴＡ（  ＰＤＬ命令）をバッファで受け取り、従来のインタフェース・プロトコルを実行することによって、従来のライン１０５，１０３及びバスライン１１３を通じてフォーマッタ１０２に渡す情報を決定する。また、インタフェースコントローラ１０６は、フォーマッタ１０２からの（例えば、インターフェース・プロトコルに関連した）命令に応答して、ライン１０１に状態・制御信号（図示せず）を送出する。
【００２５】印刷エンジン１１８は、ディジタル信号に応答して印刷媒体（例えば、紙やフィルム）上に文字又は図形を印刷して記録（例えば、インクジェット装置やレーザ印刷装置を使用するタイプでの印刷による記録）する従来より用いられている任意の印刷装置を備えるようにしても良い。印刷エンジン１１８が、ラスタ印刷装置を備えた場合の走査線形式のデータは、フォーマッタ１０２によって決定され、従来のライン１０３，１１１，１１５、バスライン１１３及び印刷エンジンコントローラ１１６を通じて、印刷用の印刷エンジン１１８に渡される。
【００２６】印刷エンジンコントローラ１１６は、ライン１１５でデータと制御信号とを印刷エンジン１１８に送出し、ライン１１５で印刷エンジン１１８からの状態信号に応答する任意のディジタル及び／又はアナログ回路を備えることがある。状態情報は、従来の方法でフォーマッタ１０２に伝達される。代替印刷エンジンコントローラは、ＲＯＭ１０８及びＲＡＭ１１２から印刷されるデータを読み出し、フォーマッタ１０２を用いないでＲＡＭ１１２に状況を書き込むダイレクト・メモリ・アクセス（ＤＭＡ）回路を有している。代替フォーマッタは、このためのＤＭＡ回路を備えている。
【００２７】プリンタ１００に使用されるメモリは、従来の読出／書込メモリ回路とＲＯＭ回路との任意の組合せを有しており、変数と（固定されたデータ項目とプログラム命令とを含む）ソフトウェアのための記憶機能を提供する。例えば、プリンタ１００は、変数の記憶用の、ＲＡＭ１１４によって拡張可能なＲＡＭ１１２を有し、更に、ＲＯＭ１１０によって拡張可能なＲＯＭ１０８を備えている。ＲＯＭ１０８は、固定されたデータ項目（例えば、フォント）とプログラムとを格納しており、大量の組み込みソフトウェアのための低コストの記憶機能が提供される。
【００２８】組み込みソフトウェアの一部又は全てが、圧縮されていることがある。ＲＯＭ１０８及び１１２による実行を行うための一般的なタイプとして、スタティック・マスクＲＯＭと、ＥＥＰＲＯＭ装置と、バッテリ・バックアップ付きＤＲＡＭ装置とを備えた任意の汎用メモリ回路を挙げることが出来る。
【００２９】ＲＡＭ１１４は、データの記憶機能を処理するためのものであり、ソフトウェアの一部分を圧縮形式又は非圧縮形式で供給することがある。動作において、インタフェース・コントローラ１０６からダウンロードされたソフトウェアは、圧縮形式又は非圧縮形式でＲＡＭ１１４に記憶することが出来る。
【００３０】本発明の態様によるフォーマッタは、プリンタ動作を制御し、一部分が圧縮形式で記憶されたプログラムを実行する任意のディジタル・コンピュータ回路を備えることが出来る。例えば、フォーマッタ１０２は、プリンタ１００のほぼ全ての機能を制御し、かつ、調整し、信号ＤＡＴＡによって受け取ったデータを印刷エンジン１１８用の走査ラインにフォーマットする。フォーマッタ１０２は、ＲＯＭ１０８（又は１１０）又はＲＡＭ１１２（又は１１４）に圧縮形式で記憶されたプログラム命令を実行する。
【００３１】変形例において、計算の性能、プロセスの監視又は印刷エンジンの制御を追加又は改善するために、追加の特殊なディジタル・コンピュータ回路をバスライン１１３に結合することが出来る。記憶されたプログラムを実行する従来の計算回路は、印刷回路ボード上又は特定用途向け集積回路（ＡＳＩＣ）上に従来通りに実施されたタイプのマイクロプロセッサ・ベースの回路とマイクロコントローラ・ベースの回路とを備えている。マイクロプロセッサとマイクロコントローラとは、従来通り、それぞれ処理量が制限されたオンチップ・データ・キャッシュとオンチップ命令キャッシュとを備えている。これらの従来のオンチップ（レベル１）キャッシュは、圧縮形式のプログラム命令を有していない。
【００３２】図２は図１中のフォーマッタの一部分の機能を示すブロック図であり、ＡＳＩＣ２００として実施されたフォーマッタ１０２の一部分の例を示している。この図２に示すＡＳＩＣ２００は、従来の技術によって構成され、例えば、標準セル及び／又はカスタム集積回路技術を利用して設計される。ＡＳＩＣ２００は、主にプロセッサ２１０と特許請求の範囲においてキャッシュに該当する命令キャッシュ２２０とを備えている。プロセッサ２１０は、データ・キャッシュ、バスライン制御、入出力制御、データ・メモリ管理及び電力消費管理用の従来の回路（図示しない）を備えている。一つの変形例において、プロセッサ２１０は、Ｉｎｔｅｌ社から販売されているプロセッサｍａｇａｃｅｌｌ  ｉ９６０を利用できる。
【００３３】プロセッサ２１０は、メモリ２３０（又は２３２）に記憶された圧縮した命令に高速アクセスするために命令キャッシュと連動する。メモリ２３０は、前記した内容によって、ＲＯＭ１０８，１１０及び／又はＲＡＭ１１２，１１４を有している。従来のライン１０３，１１３，１０７及び１０９を、ライン２０５として集合的に示す。命令キャッシュは、プロセッサ及びメモリと連動して、プロセッサがメモリから各命令を直接獲得して処理する場合よりも短いアクセス時間で、対応する命令のストリームをプロセッサに供給することによって、メモリ・アドレスのストリームに応答するためのすべての回路を備えている。
【００３４】本発明の態様による命令キャッシュは、メモリに記憶された情報を更に圧縮解除して、対応する命令のストリームを決定する。例えば、命令キャッシュ２２０は、一次キャッシュ２１２と二次キャッシュ２１８とを有している。一次キャッシュ２１２は、第３メモリに該当する高速なＳＲＡＭ２１６とキャッシュ・コントローラ２１４とを備えている。二次キャッシュ２１８は、第１メモリに該当するＤＲＡＭ２２６と、第２メモリに該当するＳＲＡＭ２２４と、圧縮解除機構に該当するキャッシュ・コントローラ２２２と、バスライン２１１とを備えている。キャッシュ・コントローラ２２２は、後で説明する動作に適合する従来の状態機械アーキテクチャを有する圧縮解除機構を備えている。
【００３５】ライン２１３は、キャッシュ・コントローラ２１４とＳＲＡＭ２１６との間のデータ通信を実行する。バスライン２１１は、ライン２１５を通じてキャッシュ・コントローラ２２２との間のデータ通信を実行する。また、ライン２１７を通じてＳＲＡＭ２２４との間のデータ通信を実行する。更に、ライン２１９を通じてＤＲＡＭ２２６との間のデータ通信を実行する。また、ライン２０５を通じてメモリ２３０との間でデータ通信を実行する。
【００３６】バスライン２１１とライン２１５，２１７，２１９及び２０９とのそれぞれの幅（並列ビット数）は、ライン２０５の幅と必ずしも同一でもなく、また、類似していない。フォーマッタ２００の好ましい形態において、バスライン２１１とライン２０９，２１９，２１７，２１５とは、６４〜５１２ビット幅、好ましくは１２８ビット幅であり、これに対してライン２０９は、それよりも幅が狭く、例えば、３２ビット数の幅である。
【００３７】動作において、一次キャッシュ２１２は、従来のオンチップ・キャッシュとして動作し、以下のように動作する。
【００３８】（１）キャッシュ・コントローラ２１４が、ライン２０１上の信号ＡＤＤＲで供給されるアドレスが、ＳＲＡＭ２１６内で現在利用可能な対応する命令を要求することを決定する場合（キャッシュ・ヒット）、キャッシュ・コントローラ２１４は、ＳＲＡＭ２１６からの信号ＩＮＳＴによって、対応する命令を実行する。
【００３９】（２）キャッシュ・コントローラ２１４が、ＳＲＡＭ２１６からのアドレスに対応できない場合（キャッシュ・ミス）、ライン２０７上のキャッシュ・コントローラ２１４が、二次キャッシュ２１８に対する一群のアドレス中の先頭アドレスにおいて、対応する命令を有する命令要求を送出する。キャッシュ・コントローラ２１４は、ＳＲＡＭ２１６の使用状態を管理して、要求される（すなわち、取り出される）可能性がほとんどない命令が占める領域を開放し、キャッシュ・ミスが発生する可能性を最小にするために自由領域を埋める。本発明の態様によれば、ＳＲＡＭ２１６は、予想されるプロセッサ・アドレス・シーケンス、ＳＲＡＭ２１６のアクセス時間、及び、二次キャッシュ２１８の予想応答時間に基づいて、高いヒット率を保証できるだけの領域を有している。
【００４０】命令キャッシュ２２０の変形例において、一次キャッシュ２１２は省略され、この省略に対応してＡＳＩＣの表面積、電力消費及び複雑さが減少する。省略される場合は、信号ＡＤＤＲがライン２０７のキャッシュ・コントローラ２２２に示され、信号ＩＮＳＴが、ライン２０９でＤＲＡＭ２２６からプロセッサ２１０に供給される。
【００４１】本発明の態様による二次キャッシュは、従来のレベル２（  ｌｅｖｅｌ  ２）キャッシュ（通常、レベル１（  ｌｅｖｅｌ  １）キャッシュよりも大きな命令ブロックを有する）の機能を有し、メモリから圧縮形式で読み出した情報ブロックを圧縮解除する。例えば、二次キャッシュ２１８は、次のように動作する。
【００４２】（１）キャッシュ・コントローラ２２２は、ライン２０７からのアドレスが、ＤＲＡＭ２２６内で現在利用可能な対応する命令を要求していると決定した場合（キャッシュ・ヒット）、キャッシュ・コントローラ２２２はＤＲＡＭ２２６から対応する命令を受け取る。
【００４３】（２）キャッシュ・コントローラ２２２が、ＤＲＡＭ２２６からのアドレスに対応できない場合（キャッシュ・ミス）、キャッシュ・コントローラ２２２は、圧縮形式を有する命令の取り出しを実行する。
【００４４】この方法は、圧縮形式の情報から固有の命令形式、すなわち、プロセッサが直接実行するために必要な固有の命令形式での結果を示す任意の一連のステップを有することがある。一般的に、圧縮形式の情報は、これに対応する実行可能な形式の命令よりも少ない記憶アドレスの領域を占有する。それぞれのメモリ・アドレス（命令／情報）の量の比率は、圧縮比と呼ばれている。
【００４５】特定の情報ブロック又は命令に適用されるような従来の圧縮アルゴリズムでは、約２：１の圧縮比が実現可能である。キャッシュ・コントローラ２２２は、従来の任意の圧縮解除アルゴリズムを実行する圧縮解除機構を有している。例えば、一般的に、ハフマン・アルゴリズムとして知られるタイプの好ましいアルゴリズムは、ｉ９６０プロセッサ実行形式の２５６Ｋバイトの命令の標準ブロックに適用される場合に、圧縮と圧縮解除に使用されるテーブル内のエントリの数によって１．８：１〜３．６：１の圧縮比を有することがある。
【００４６】本発明の変形例において、既知のＧＺｉｐ又はＬｉｍｐｅｌ  Ｚｉｖ  Ｗｅｌｃｈ（ＬＺＷ）アルゴリズムのバージョンは、圧縮する特定の命令によって圧縮比が変化する圧縮解除機構に使用される。特定の用途のアルゴリズムの選択は、キャッシュ・コントローラ２２２の回路の複雑さと、キャッシュ・メモリ（２１６，２２４，２２６）とシステム・メモリ（２３０，２３２）の相対サイズとアクセス時間に依存することになる。
【００４７】圧縮解除機構は、ライン２０７上の要求とメモリ２３０内の対応する情報と対応したライン２０９に実行可能命令を実行するように、キャッシュ・メモリとシステム・メモリと連動して動作を実行する。図３は圧縮解除機構の動作方法の一部分の処理手順を示すフローチャートである。この図３の方法３００は、例えば、圧縮形式の情報から導出したｉ９６０固有の命令形式のコード・ブロック値によって、一次キャッシュ２１２のミス・イベントに応答する。このコード・ブロックは、必要に応じてライン２０９でＳＲＡＭ２１６に転送するために、ＤＲＡＭ２２６内に記憶される。キャッシュ・コントローラ２１４及び２２２は、方法３００の終了時に従来の方法で連動して、ライン２０３に信号ＩＮＳＴで提供される実行可能命令を送出する。
【００４８】ステップ３０４及び３１０において、キャッシュ・コントローラ２２２は、マップ（ＭＡＰ）を使用して、メモリ２３０内のいずれのアドレスが適切な情報を有しているかを決定する。次に、このアドレス中のメモリ２３０内の情報の形式、すなわち、圧縮解除されているか又は圧縮されているかを決定し、圧縮されている場合は、圧縮解除に必要なテーブル（ＴＡＢＬＥ）の情報（ある場合）の場所を決定する。マップおよびテーブルのデータは、キャッシュ・コントローラ２２２が迅速にアクセスできるように、ＳＲＡＭ２２４に従来の方法で記憶されることが好ましい。
【００４９】以上、説明したように、メモリ２３０は、非圧縮情報と圧縮情報とを有している。非圧縮情報は、マップの情報、テーブルの情報及び非圧縮コード・ブロックを有することがある。圧縮情報は、後で説明する簡単又は複合的な情報ブロックを有している。
【００５０】マップの情報がメモリ２３０からＳＲＡＭ２２４に転送される際に、マップを非圧縮形式でアレイとして記憶することが出来る。アレイの各行は、コード・ブロックを圧縮解除するアドレス範囲を識別する。ライン２０７上でキャッシュ・コントローラ２１４によって指定されたアドレスが、特定の行によって指定された範囲内にあることが判明した場合に、この行のアレイにおける様々な列は、圧縮解除に十分な情報を識別する。この列の情報は、例えば、形式を圧縮／非圧縮として示す１ビット・フラグと、現状のまま（非圧縮形式に対し）又は圧縮解除（圧縮形式に対し）入力として使用される情報ブロックを一緒に定義するメモリ２３０内の先頭アドレスに対するオフセットおよび長さ（又は終了アドレスに対するオフセット）と、テーブル（ＴＡＢＥＬ）の適切な内容を識別するメモリ２３０内の先頭アドレスに対するオフセットとを有している。
【００５１】変形例において、メモリ２３０内の情報は、ポインタ又は従来の連結リストを使用する連結形式で可変長構造に編成される。連結リストは、より少数の算術比較によってランダムなアドレスに対応する（可変長）情報を位置決めする階層編成を示している。
【００５２】キャッシュ・コントローラ２２２は、要求されたアドレスを、対応する圧縮解除コード・ブロック値の範囲内の情報ブロックの先頭アドレスとオフセット・アドレスとに変換する従来の変換索引バッファを備えることもある。
【００５３】ステップ３１４において、キャッシュ・コントローラ２２２は、ＳＲＡＭ２２４に記憶されたテーブルの内容が、現状のままで良いか、それともメモリ２３０からの非圧縮情報と交換すべきかどうかを決定する。ＳＲＡＭ２２４に記憶されたテーブルの内容の識別は、テーブルの適切な内容を定義するメモリ２３０内のアドレスとしてレジスタに保持されることがある。レジスタとマップとによって与えられるテーブルの識別が一致しない場合は、ステップ３１６に移行し、メモリ２３０から新しいテーブルを読み出す。識別が一致する場合は、テーブル内の値を変更せずステップ３１８に移行する。
【００５４】任意の数のテーブルのエントリを使用することが出来る。各エントリが通常のタグ値に対応する「２Ｎ  −１」のエントリを使用することが好ましい。圧縮解除が不要であることを示すために、特殊なタグ値が設定される。通常タグ値は圧縮解除プロセスにおいて、圧縮情報で置換される固有形式の命令のコード・ブロックを識別するために使用することが出来る。
【００５５】テーブルの情報が、メモリ２３０からＳＲＡＭ２２４に転送される場合、テーブルを非圧縮形式でアレイとして記憶することが出来る。テーブルの各エントリは行を構成し、第１データ項目（例えば、短いタグ）と第２データ項目（例えばとコード・ブロックとも呼ばれる非圧縮コード・ブロック値）とを識別する。変形例において、ＳＲＡＭ２２４内の一連のアドレスにおける各アドレスは、通常タグ値と一致し、ＳＲＡＭ２２４にタグ値を記憶しないようにする。他の一つの変形例において、ポインタを使用して、不均等な長さの第２データ項目に対する参照を可能にする。更に他の一つの変形例において、テーブルの構造をマップの構造と類似させて、圧縮解除機構の回路規模を縮小する。
【００５６】ステップ３１８において、キャッシュ・コントローラ２２２は、（信号ＡＤＤＲから）要求されたアドレスに対応するメモリ２３０内の情報を圧縮解除すべきか、又は、圧縮解除せずに転送すべきかを決定する。圧縮解除が必要でない場合、ステップ３２４に移行する。圧縮解除が必要な場合は、ステップ３２０に移行する。要求アドレスを有するコード・ブロックは、部分的な命令、完全な命令又は固有形式の任意の数の命令を有することがある。
【００５７】コード・ブロックのサイズは、ＳＲＡＭ２１６，ＤＲＡＭ２１９，ＳＲＡＭ２２４及びメモリ２３０の読出／書込サイクル・タイミング、及びこのメモリの容量とワード・サイズに基づいて、システム性能（例えば、プロセッサ２１０から見た命令取出しの待ち時間）を最適にするように決定される。ページ・モードの読み出し／書き込み動作は、このメモリの一部分又は全てによる動作の一部分又は全てのために、好ましい変形例の圧縮解除機構によって実行される。
【００５８】ステップ３２０および３２２において、簡単又は複合的な情報ブロックが、メモリ２３０から読み出される。簡単な情報ブロックは、単独の通常タグ値又は非圧縮コード・ブロック値が続く特殊タグ値のいずれかからなる。複合的な情報ブロックは、一連の簡単な情報ブロックからなる。それぞれの通常タグ値に関して、圧縮解除機構は、テーブル内の対応するコード・ブロック値を識別する。それぞれの特殊タグ値に関して、圧縮解除機構は、特殊タグ値に続くコード・ブロック値を識別する。
【００５９】ステップ３２４において、非圧縮形式の識別されたコード・ブロックが、ＤＲＡＭ２２６に記憶される。ステップ３１８からステップ３２４に移行する場合、メモリ２３０からのコード・ブロックがＤＲＡＭ２２６に直接転送される。ステップ３２２からステップ３２４に移行して圧縮解除機構の出力が、ＤＲＡＭ２２６に記憶される。
【００６０】好ましい変形例において、複合的な情報ブロックは、パイプライン方式で読み出され、圧縮解除されて記憶される。例えば、メモリ２３０のそれぞれの連続した読み出しサイクルにおいて、タグが識別され、対応するコード・ブロックが、メモリ又はテーブルからＤＲＡＭ２２６内の適切な場所に転送される。
【００６１】他の一つの変形例において、コード・ブロックは、メモリ２３０の読出／書込部に戻され、対応するＭＡＰエントリがアクセス転送を行うように更新される。更に、他の一つの変形例において、全ての圧縮コード・ブロックは、システムの初期化又は任意の最初の要求の際に圧縮解除され、メモリ２３０に記憶されて、かつ、圧縮解除されて固有形式の命令の実行が中断されないようになる。
【００６２】次に、ＤＲＡＭ２２６は、キャッシュ・コントローラ２１４によって要求された命令を有する固有形式の命令を格納している。この命令に関する次の要求は、キャッシュ・コントローラ２２２が、要求前に命令がほとんど使用される可能性がないことを決定し、他の非圧縮コード・ブロックのためにＤＲＡＭ２２６内の領域を再使用し始めるまで、二次キャッシュ・ミスを引き起こさない。ＤＲＡＭ２２６の一部分を再使用する場合、キャッシュ・コントローラ２２２は、ＳＲＡＭ２２４に記憶されたＭＡＰを更新して、それまで利用可能であったコード・ブロックがＤＲＡＭ２２６内にないことを示す。
【００６３】ステップ３３０において、キャッシュ・コントローラ２２２は、次に二次キャッシュ・ミスの発生に対する待ち状態となる。このための処理はステップ３０２から継続する。また、変形例において、メモリ２３０の読出／書込部分は、キャッシュ・コントローラ２２２によって設定され、特定アドレスの要求よりも前に圧縮解除の結果を記憶するために使用される。これによってメモリ２３０の他の使用との干渉を犠牲にして命令取出しの待ち時間が改善される。
【００６４】事前にプログラムされた拡張可能回路であるメモリ２３２にダウンロード又はインストールされた圧縮形式で記憶した情報として、メモリ２３０又は２３２にデータを格納する前に、このデータを解析して、望ましい圧縮比を決定することが出来る。所望の圧縮比を達成するために、データの任意の解析方法を使用することが出来る。解析の結果、（例えば、ステップ３１０のように）圧縮解除の必要条件を決定することが出来る。
【００６５】図４は二次キャッシュ内のＳＲＡＭ２２４に記憶されたテーブルの値を決定する方法である。この図４の方法４００は、たとえば、前記した好ましいハフマン圧縮／圧縮解除方法の必要条件として圧縮比を解析して、ＳＲＡＭ２２４に記憶されたテーブルの値を決定する方法である。ステップ４１２において、アドレス範囲内の全ての命令を調べる。この調べ中に、パターンがアドレス範囲内で２度以上発生することが判明した場合、このパターンは、前記したテーブルと類似した一時的アレイにおいてタグ値と非圧縮コード・ブロック値との両方で識別される。調べの効率を高めるために、最小パターン長を設定する（例えば、１６ワード）。任意の一連のビット、バイト又はワードは、パターン（すなわち、コード・ブロック）を有することがある。
【００６６】ステップ４１４において、繰り返しのコード・ブロックごとに発生回数をカウントする。各カウントは、一時的にアレイに記憶される。
【００６７】ステップ４１６において、アドレス範囲内のコード・ブロックを全てカウントする。このカウントにコード・ブロック内のビットの数を乗じると、その積は、圧縮比の分子の値となる。
【００６８】ステップ４１８において、ループ変数「Ｎ」は、例えば、４の初期値に設定される。この初期値は、二次キャッシュ２１８のサイズと動作速度とを最適化するように選択される。初期値は、例えば、１〜２０における適合する任意の最小の数で良い。
【００６９】ステップ４２０，４３０，４４０及び４４４はループルーチンとなる。ステップ４２０において、「２Ｎ  −１」の繰り返しのコード・ブロックの有効範囲を解析する。すなわち、受入れ可能な圧縮比が、「２Ｎ  −１」の行を有するテーブルと一致するという仮説が立つ。最高の発生カウントを有する「２Ｎ  −１」の行の選択が検討され、圧縮比が計算される。ビット・カウントに基づく圧縮比は、以下の通りである。
【００７０】
【数１】
2000135821.tif 000001
【００７１】ここで、Ｘは選択された行内で発生したカウントの全ての発生カウントの合計であり、Ｙは非選択行内の全ての発生カウントの合計である。また、パターンサイズは、パターン（すなわち、コード・ブロック）内のビットの量、タグサイズは、タグ値におけるビットの量であり、全てのタグ値（特殊な値を有する）が同一サイズであると仮定する。
【００７２】ステップ４３０において、ステップ４２０で得た圧縮比を最小値と比較する。望ましい圧縮比（最小値と一致するか、それよりも大きい値）が得られた場合、ステップ４３２に移行してテーブルの行を定義する。望ましい圧縮比が得られない場合は、ステップ４４０に移行する。
【００７３】ステップ４４０において、ループ変数が上限、例えば、８に対する検査が行われる。この上限は、二次キャッシュ２１８のサイズと動作速度とを最適化するように選択される。上限は、例えば、４〜４０の適合する任意の最大数で良い。ループ変数が上限に達しない場合、ループ変数は、ステップ４４４において増分され、ループの一番上に移行する。ループ変数が上限に達した場合、ステップ４１２において解析用に提示されたアドレス範囲は、圧縮されていないものとして指定される。これは圧縮基準がシステム設計基準を満たさないことを意味する。
【００７４】圧縮基準は、例えば、アドレス範囲のサイズ、選択されていない圧縮アルゴリズム、パターン・サイズ、及び、圧縮解除のエントリのテーブルのサイズを有している。好ましい変形例において、ステップ４４２に移行する際に、他の１組の圧縮基準が決定され、望ましい圧縮比が得られるまで方法４００が繰り返される。例えば、タグ値の量が増加すると、テーブル内の行の数も同じように増加する。他の一つの変形例において、アドレス範囲内の命令を修正又は再編成して、特定のアドレス範囲内のコード・ブロック値の繰り返しを増加することが出来る。
【００７５】以上の説明では、本発明の範囲から逸脱することなく変更又は修正できる好ましい実施形態について説明している。例えば、一つの変形例において、圧縮解除は、連続した一連の命令を必ずしも発生させず、要求されると予想される命令のストリームを生成する。この連続した命令は、例えば、関数の所望の混合、共通に生じる入力データ、及び、予想される環境条件などのプログラムの実行の解析によって選択される。
【００７６】他の一つの変形例において、二次キャッシュ・ヒット率は、約９０％〜９５％である。
【００７７】その他の変形及び修正は、本発明の範囲に含まれる。本発明を明瞭かつ容易にするために、本発明の特定のいくつかの実施形態を説明したが、本発明の範囲は、併記した特許請求の範囲によって判断されるものである。
【００７８】以下に本発明の実施の形態を要約する。
【００７９】１．  ａ．圧縮形式のプログラムを記憶するメモリ（１０８，２３０）と、ｂ．コンピュータから入力データ（１０１）を受け取るためのバッファ（１０６）と、ｃ．前記メモリと前記バッファとに結合され、前記入力データに応答して画像を決定するフォーマッタ（１０２，２００）であって、（１）前記メモリ（２３０）から前記プログラムの少なくとも一部分を受け取り、この一部分を圧縮解除して命令を送出する圧縮解除機構（２２２）と、（２）前記命令を受け取って記憶するキャッシュ（２２６，２１６）と、（３）前記キャッシュからの命令を受け取り、かつ、該命令を実行して画像を決定するプロセッサ（２１０）とを備えるフォーマッタと、ｄ．前記画像を印刷する印刷エンジン（１１６，１１８）と、を備えるプリンタ（１００）。
【００８０】２．  ｅ．前記一部分が、前記メモリ（２３０）の複数の読出サイクルを有し、ｆ．前記メモリが、読み出しアクセス用のページ・モードを有し、ｇ．中断しないページ・モードのアクセス中に複数の読出サイクルを処理する上記１記載のプリンタ。
【００８１】３．  前記フォーマッタが、前記圧縮解除機構（２２２）と、前記キャッシュ（２２６，２１６）と、前記プロセッサ（２１０）とを有する集積回路（２００）を有する上記１又は２記載のプリンタ。
【００８２】４．  前記キャッシュが、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）のアレイ（２２６）を備える上記１，２，３いずれか一項に記載のプリンタ。
【００８３】５．  ａ．前記メモリ（２３０）が、第１幅を有する第１バス（２０５）によって前記フォーマッタに結合され、ｂ．前記キャッシュ（２２６）が、第２幅を有する第２バス（２１９，２１１，２１５）によって前記圧縮解除機構（２２２）に結合され、ｃ．前記第１幅が、前記第２幅よりも狭い上記１，２，３，４いずれか一項に記載のプリンタ。
【００８４】６．  ａ．実行可能命令（２０３）を取り出すためのアドレス（２０１）を送出するプロセッサ（２１０）と、ｂ．前記アドレスに応答して前記実行可能命令を送出するキャッシュ（２２０）であって、（１）第１メモリ（２２６）と、（２）メモリ（２３０）からテーブルと情報ブロックとを読み出す圧縮解除機構（２２２）とを備え、（ａ）前記テーブルが複数の行を有し、前記各行が一連のタグ値のそれぞれのタグ値に対応しかつそれぞれのコード・ブロック値を識別し、（ｂ）前記情報ブロックが、データ項目を有し、（ｃ）前記圧縮解除機構が、前記第１メモリに、前記テーブルの行の各コード・ブロック値のコピーを記憶するキャッシュとを備え、１）前記行のそれぞれのタグ値が、前記データ項目に応じて識別され、２）前記コピーが、実行可能命令を有し、３）前記コード・ブロック値が、前記データ項目よりも多い数のビットを有する集積回路（２００）。
【００８５】７．  前記第１メモリ（２２６）が、ダイナミック・ランダム・アクセス・メモリを備える上記６記載の集積回路。
【００８６】８．  前記キャッシュが、更に第２メモリ（２２４）を備え、前記圧縮解除機構が、該第２メモリに前記テーブルを格納する上記６又は７記載の集積回路。
【００８７】９．  ａ．第３メモリ（２１６）と、ｂ．前記第１メモリ（２２６）から前記コピーを読み出し、前記プロセッサ（２１０）によってアクセスのために前記実行可能命令の第２コピーを前記第３メモリ（２１６）に記憶するキャッシュ・コントローラ（２１４）と、を備える上記６，７，８いずれか一項に記載の集積回路。
【００８８】１０．  ｃ．前記第１メモリ（２２６）が、ダイナミック・ランダム・アクセス・メモリを備え、ｄ．前記キャッシュが更に、（１）スタティック・ランダム・アクセス・メモリを有する第２メモリ（２２４）と、（２）第３メモリ（２１６）と、（３）前記第１メモリ（２２６）からコピーを読み出し、前記プロセッサ（２１０）によるアクセスのために前記実行可能命令の第２コピーを前記第３メモリ（２１６）に記憶するためのキャッシュ・コントローラ（２１４）とを備え、ｅ．前記圧縮解除機構（２２２）は、前記メモリ（２３０）からマップを読み出し、前記第２メモリ（２２４）にテーブルとマップとを記憶し、前記マップに対応したメモリから情報ブロックを読み出す上記６記載の集積回路。
【００８９】
【発明の効果】以上の説明から明らかなように、本発明のプリンタによれば、命令キャッシュ及び圧縮プログラム記憶機能を備えたプロセッサにより、プリンタの性能の拡張を制限されずに、プログラムを効率的に記憶して実行できる。
【図面の簡単な説明】
【図１】プリンタの構成を示すブロック図である。
【図２】図１中のフォーマッタの一部分の機能を示すブロック図である。
【図３】圧縮解除機構の動作方法の一部分の処理手順を示すフローチャートである。
【図４】二次キャッシュ内のＳＲＡＭに記憶されたテーブルの値を決定する方法である。
【符号の説明】
１００  プリンタ
１０２，２００  フォーマッタ
１０６  インタフェースコントローラ
１０８，１１０  ＲＯＭ
１１２，１１４  ＲＡＭ
１１６  印刷エンジンコントローラ
１１８  印刷エンジン
２１０  プロセッサ
２１２  一次キャッシュ
２１４，２２２  キャッシュ・コントローラ
２１６，２２４  ＳＲＡＭ
２１８  二次キャッシュ
２２０  命令キャッシュ
２２６  ＤＲＡＭ
２３０，２３２  メモリ