アプリケーションが決定したスケジューリングによる効率的なキャッシュの再利用
【課題】マルチプロセッサコンピュータシステにおいて効率的なキャッシュの再利用を図る。
【解決手段】コンピュータシステム１００においてタスクを実行すべく複数のスレッドからスレッドを決定する方法が開示される。複数のスレッドは、コンピュータシステムのキャッシュメモリと関連付けられた少なくとも１つのサブセットにグループ化される。タスクは、命令の集合により決定された型を有する。方法は、複数のスレッドのサブセットの実行履歴を取得し、命令の集合及びデータの集合毎にタスク型に依存する重み付けを決定する。次に、実行履歴及び決定された重み付けに基づいてタスクを実行するスレッドのサブセットの適合性が決定される。決定されたスレッドのサブセットの適合性を条件として、スレッドのサブセットと関連付けられたキャッシュメモリの内容を使用してタスクを実行すべくスレッドのサブセットからスレッドを決定する方法が開示される。
【解決手段】コンピュータシステム１００においてタスクを実行すべく複数のスレッドからスレッドを決定する方法が開示される。複数のスレッドは、コンピュータシステムのキャッシュメモリと関連付けられた少なくとも１つのサブセットにグループ化される。タスクは、命令の集合により決定された型を有する。方法は、複数のスレッドのサブセットの実行履歴を取得し、命令の集合及びデータの集合毎にタスク型に依存する重み付けを決定する。次に、実行履歴及び決定された重み付けに基づいてタスクを実行するスレッドのサブセットの適合性が決定される。決定されたスレッドのサブセットの適合性を条件として、スレッドのサブセットと関連付けられたキャッシュメモリの内容を使用してタスクを実行すべくスレッドのサブセットからスレッドを決定する方法が開示される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータベースのシステムに関し、特にアプリケーションプログラム内の処理スケジューリングによりキャッシュヒット率の向上に関するものである。
【背景技術】
【０００２】
コンピュータシステムにおけるキャッシュメモリは、中央処理装置（ＣＰＵ）が容易に且つ高速にアクセスするために、主記憶場所からの命令又はオペランドであるデータ項目のコピーを格納するために使用される。キャッシュの再利用は、メモリアクセス時間を短縮することにより殆どのソフトウェアアプリケーションにとって大幅な実行時間の短縮につながるため、非常に望ましい。処理（又はマルチスレッドアプリケーションにおけるスレッド）内の効率的なキャッシュの再利用は、アプリケーションプログラムコードの品質に依存し、処理間及びスレッド間の効率的なキャッシュの再利用は、キャッシュに既にロードされているものを追跡すること、並びにキャッシュ内容の再利用を考慮して次に実行するための後続の処理／スレッドを選択することを含む。
【０００３】
キャッシュ内容を追跡することは、一般に、ハードウェア手段又はソフトウェア技術を採用することで当技術分野において実現される。多くの場合、収集されたキャッシュ内容情報の正確度とその処理専用の時間及びリソースの量との間にはトレードオフの関係がある。キャッシュの再利用方法は、一般化されることによりあらゆるプログラム又は処理に対して適用可能なものもあるが、より特化されるものもある。
【０００４】
また、データキャッシュ内容の再利用を目標とする方法もあるが、命令キャッシュ内容の再利用を目標とする方法もある。場合によっては、方法は、特にどちらかを目標とすることなく、データ及び命令の双方に対して適用可能である。
【０００５】
従来技術において既知であるデータキャッシュの再利用に対する１つの手法は以下の通りである。データを全く共有しない処理は、マルチプロセッサシステムにおいて可能であれば種々のプロセッサ上でスケジュールされる。また、依存関係のために同時に実行されないが、互いに共通データを共有する処理は、それらがキャッシュ内容を共有できるような方法でＣＰＵ上でスケジュールされる。方法は、特定のアプリケーションにおいて動作可能なアルゴリズムの詳細な知識を必要とし、データの再利用のみを考慮する。
【０００６】
他の従来技術は、同一のプロセッサ上で同一の処理をスケジュールすることで命令データの局所性を向上することを目的とする。命令の再利用のみを考慮する。
【０００７】
いくつかの従来技術の方法の主な欠点は、それらがデータの再利用又は命令の再利用を簡略化するように設計されるが、双方を考慮しないことである。
【０００８】
他には、より一般的な従来技術の手法は、所定の処理に対してキャッシュ内容の「キャッシュウォーム（cache warmth）」を測定することにより、ハードウェア手段又はソフトウェア技術を用いて命令の再利用及びデータの再利用の双方を簡略化することである。キャッシュウォームは、キャッシュにおいて見つけられた特定の処理のデータの古さを示すために使用される場合がある用語であり、処理毎に各プロセッサの要求の数をカウントする方法又はキャッシュのサブセクションに対するキャッシュミスを追跡する方法、あるいはライン毎のキャッシュの利用を追跡する方法等を含む従来技術における種々の方法で測定される。ＣＰＵがキャッシュにおいてデータ項目を見つけられない場合にキャッシュミスが発生する。これにより、関連付けられた性能ペナルティでより低いレベルのキャッシュ又は主記憶からデータ項目を取り出すことが必要になる。
【０００９】
キャッシュ内容の再利用に対するこれらのより一般的な従来技術の手法の主な欠点は、それらの複雑性及びその複雑性がプログラム実行に対して課すオーバヘッドにある。それらは、実現するために専用ハードウェアを更に必要とすることが多い。
【発明の概要】
【００１０】
本発明の目的は、従来技術の構成の１つ以上の欠点を実質的に克服するかあるいは少なくとも改善することである。
【００１１】
本発明によれば、アプリケーションの内部知識を有するスケジューラは、重い処理オーバヘッドを課さずにコンピュータシステムにおいてコンテキストを切り替える結果発生するキャッシュミスを減少することでキャッシュミス率を最小限にするように配置される。
【００１２】
多くのグループ内のスレッドの総合的な実行又は処理の履歴及び実行されるタスクの特徴の双方に基づいて、タスクを実行するスレッドのこれらのグループのうちの１つにプリファレンスが与えられる構成が開示される。
【００１３】
本発明の一態様によれば、マルチプロセッサのコンピュータシステムにおいて、タスクを実行すべく複数のスレッドから１つのスレッドを決定する方法であって、複数のスレッドはコンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化されており、タスクは命令の集合により決定される型を有しており、当該方法は、複数のスレッドのサブセットの実行履歴を取得するステップと、命令の集合及びデータの集合の各々に対し、タスクの型に依存している重み付けを決定するステップと、実行履歴と決定された重み付けとに基づいて、タスクを実行すべく複数のスレッドのサブセットの適合性を決定するステップと、複数のスレッドのサブセットの決定された適合性を条件として、複数のスレッドのサブセットに関連付けられたキャッシュメモリの内容を使用して、タスクを実行すべく複数のスレッドのサブセットから１つのスレッドを決定するステップと、を含む方法が提供される。
【００１４】
使用される複数のスレッドのサブセットの適合性を決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することが望ましい。複数のスレッドのサブセットの適合性を決定するステップは、命令に対する重み付けがデータに対する重み付けより大きい場合に、タスクを実行すべく複数のスレッドのサブセットの適合性を決定するために、データ履歴の前にタスク履歴を検査するサブステップと、データに対する重み付けが命令に対する重み付けより大きい場合に、タスクを実行すべく複数のスレッドのサブセットの適合性を決定するために、タスク履歴の前にデータ履歴を検査するサブステップと、を含むことが望ましい。
【００１５】
重み付けは、複数のスレッドのサブセットの実行履歴に基づいて決定されることが好適である。あるいは、重み付けは、ルックアップテーブルを使用して決定され得る。
【００１６】
一般に、キャッシュメモリのサイズに依存したサイズを有する。あるいは、実行履歴は、複数のスレッドにより実行されるタスクの集合に関連して最も多く実行された命令のサイズに依存したサイズを有する。更に別の方法において、実行履歴は、複数のスレッドにより実行されるタスクの集合により使用されたデータに依存したサイズを有する。
【００１７】
本発明の他の態様によれば、マルチプロセッサのコンピュータシステムにおいて、印刷タスクを処理するためのキャッシュメモリのキャッシュ再利用を管理する方法であって、キャッシュメモリは複数のスレッドのサブセットと関連付けられており、印刷タスクは該印刷タスクのための命令の集合により決定される型を有しており、当該方法は、複数のスレッドのサブセットの実行履歴を取得するステップと、命令の集合及びデータの集合の各々に対し、印刷タスクの型に依存している重み付けを決定するステップと、実行履歴と決定された重み付けとに基づいて、印刷タスクを実行すべく複数のスレッドのサブセットの適合性を決定するステップと、印刷タスクを処理するサブセットから１つのスレッドを決定することにより複数のスレッドのサブセットが適切であると決定される場合に、キャッシュメモリを再利用するステップと、を含む方法が提供される。
【００１８】
本発明の更に他の態様によれば、マルチプロセッサのコンピュータシステムにおいて、スレッドによる実行のために複数のタスクから１つのタスクを決定する方法であって、スレッドはコンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化される複数のスレッドの１つであり、タスクは命令の集合により決定される型を有しており、当該方法は、スレッドの実行履歴を取得し、対応するキャッシュメモリを識別するステップと、実行のために利用可能なタスクを識別し、命令の集合及びデータの集合の各々に対し、識別されたタスクの型に依存している重み付けを決定するステップと、実行履歴と決定された重み付けとに基づいて、スレッドで実行すべく識別されたタスクの適合性を決定するステップと、複数のスレッドのサブセットの決定された適合性を条件として、対応するキャッシュメモリの内容に基づいて、複数のタスクからスレッドで実行される１つの識別されたタスクを決定するステップと、を含む方法が提供される。
【００１９】
重み付けが、使用されるタスクを決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することが望ましい。スレッドによる実行のために複数のタスクから１つのタスクの適合性を決定するステップは、タスクの命令に対する重み付けがデータに対する重み付けより大きい場合に、スレッドにより実行されるタスクの適合性を決定するために、データ履歴の前にタスク履歴を検査するサブステップと、タスクのデータに対する重み付けが命令に対する重み付けより大きい場合に、スレッドにより実行されるタスクの適合性を決定するために、タスク履歴の前にデータ履歴を検査するサブステップと、を含むことが望ましい。
【００２０】
他の態様も更に開示する。
【００２１】
次に、以下の図面を参照して本発明の少なくとも１つの実施形態を説明する。
【図面の簡単な説明】
【００２２】
【図１】説明される構成が実現される例示的なコンピュータシステムの一部を示す概略ブロック図である。
【図２】図１のコンピュータシステムの処理装置及びメモリ装置の一例を示す概略ブロック図である。
【図３】図１の制御プログラム１３０に対する例示的なアーキテクチャを示す概略ブロック図である。
【図４】図３のＥＸＥＣＵＴＩＯＮ−ＲＥＧＩＳＴＥＲ３８０格納構成要素のメモリレイアウトを示す図である。
【図５】受信したＭＡＴＣＨ＿ＴＨＲＥＡＤメッセージ及びＭＡＴＣＨ＿ＴＡＳＫメッセージに応答してタスクをスレッドに一致させる処理を示すデータフローチャートである。
【図６】所定のスレッド上で実行するためにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥからタスクを選択する処理を示すデータフローチャートである。
【図７Ａ】所定のタスクを実行するためにＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴからスレッドを選択する処理を示すデータフローチャートである。
【図７Ｂ】データの再利用が重要である場合に所定のタスクを実行するためにＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴからスレッドを選択する処理を示すデータフローチャートである。
【図７Ｃ】命令の再利用が重要である場合に所定のタスクを実行するためにＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴからスレッドを選択する処理を示すデータフローチャートである。
【図８】マルチスレッドソフトウェアプログラムの実行の所定の時点におけるＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０データ構造（図４のメモリレイアウトに従う）のメモリ内容を示す図である。
【図９】所定のスレッド上で実行するためにタスクを選択する図６に示されたデータフローチャートに対する別の手法を示すデータフローチャートである。
【図１０Ａ】Ｌ２及びＬ３のキャッシュ最適化に対する例示的な構成を示す図である。
【図１０Ｂ】Ｌ２及びＬ３のキャッシュ最適化に対する例示的な構成を示す図である。
【図１１Ａ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【図１１Ｂ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【図１１Ｃ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【図１１Ｄ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【発明を実施するための形態】
【００２３】
コンピュータシステムにおいてマルチプロセッサアーキテクチャを使用することで性能速度の高速化を実現する傾向は、近年広範に使用されるようになってきている。マルチプロセッサアーキテクチャにより、１つ以上の処理に属する多くのスレッドが多くの中央処理装置（ＣＰＵ）を介して並列に実行できるため、実行時間全体が短縮される。
【００２４】
ＣＰＵの数及び速度と共に、コンピュータシステムのメモリ構成は、処理速度に大きく影響する。階層的記憶構造は、キャッシュと呼ばれるより小型で高速なメモリをＣＰＵにより近接させた近年のメモリシステムに対して一般に受け入れられたアーキテクチャである。記憶階層において同一の深度に配置されたキャッシュは、同一のキャッシュレベルであると言われる。キャッシュメモリは、容易でより高速なアクセスのためにＣＰＵにより近接する主記憶内容のサブセットを格納するために使用される。
【００２５】
レベル１（Ｌ１）キャッシュは、ＣＰＵに最近接し、同一のハードウェアチップ上に配置又は構成される。Ｌ１キャッシュは小型で非常に高速である。レベル２（Ｌ２）キャッシュはＬ１キャッシュより大きい。Ｌ２は、一般にＣＰＵチップ上の最後のキャッシュである。レベル３（Ｌ３）キャッシュは、存在する場合により大きいために上位レベルのキャッシュより低速であるが、依然として主記憶よりはるかに高速である。一般にＣＰＵのすぐ隣のコンピュータマザーボード上に配置されたＬ３キャッシュは、ＣＰＵと直接専用に相互接続していることが多い。一般にＬ３キャッシュは、単にサイズがより大きいためにＬ１キャッシュ及びＬ２キャッシュよりキャッシュミスの発生が少ない。
【００２６】
各レベルにおいて、キャッシュは、物理的に独立したデータキャッシュ及び命令キャッシュ又はデータ及び命令の双方に対するユニファイドキャッシュから形成される。双方の場合において、データ及び命令は個別に考えられる。本発明において開示される構成は、双方の場合に対して使用される。
【００２７】
項目（命令又はオペランド（データ））が初めてＣＰＵにより要求されると、項目が属する主記憶ブロックの内容は、キャッシュラインにおいてキャッシュにロードされる。同一の項目又は同一のブロックからの項目に対する後続の要求は、そのキャッシュラインにアクセスすることで満たされる。要求された項目がキャッシュにおいて見つけられる場合、当技術分野においてキャッシュヒットとして既知であるイベント、すなわち要求された項目へのアクセスは、キャッシュミス上で発生する要求された項目が主記憶から取り出されなければならない時よりはるかに高速である。キャッシュにロードされるものは全てあらゆる種類のデータであるが、プログラムコードが動作するプログラムコード（命令）とオペランド（データ）との間で区別されることが多い。この説明において、前者を「命令」と呼び、後者を単に「データ」と呼ぶ。アプリケーションを実行するために使用されているプロセッサは、キャッシュが命令又はデータを含むかを決定し、且つ万が一キャッシュミスの場合にキャッシュラインをロードする処理を実行する。本発明において開示される構成は、命令及びデータのキャッシュを管理する全ての一般的な方法に対して適用可能である。
【００２８】
マルチプロセッサシステムにおいて並列性を利用するために、一般に処理は、タスクとして既知である本明細書の目的で、並列に実行される動作の独立単位に大きく細分される。プログラムの実行には１つ以上のタスクを完了する必要がある。各タスクは、並列に実行される場合にスレッド上で実行される。
【００２９】
本発明において開示される構成の好適な実現例において、タスクとスレッドとの間で一対一対応が維持される。すなわち、タスクは一度に１つのスレッドのみにおいて実行される。タスクの例には、グラフィックイメージ作成プログラムにおけるレンダリング処理及びスプレッドシートアプリケーションにおいて数値データの列に帰された数学演算子が含まれる。従って、タスクのサイズ及び複雑性が変動し、これは、アプリケーションプログラムが符号化されるかあるいは実行されることが望まれる方法に従う。
【００３０】
スケジューリングの観点から、タスクは、動作の最小のスケジュール可能な単位であり、常に完了する。タスクは、その型（ＴＡＳＫ＿ＩＤ）及びタスクが処理するデータ（ＤＡＴＡＳＥＴ＿ＩＤ）により規定される。ＴＡＳＫ＿ＩＤは、関連付けられたタスクが実行される場合に実行されると予想される命令の集合を識別する。ＤＡＴＡＳＥＴ＿ＩＤは、タスクの実行中に読み出されるか又は書き込まれると予想されるか、あるいはそれら双方を予想される記憶場所の集合を識別する。タスク型は命令の集合により規定される。
【００３１】
種々のタスク型は種々の特徴を有する。その特徴のうちの１つは、命令及びデータの使用パターンである。従って、データ及び命令の再利用の相対的な重要度は種々のタスク毎に異なる。本発明において開示される構成において、２つの重み値は、各タスク型、すなわちｗi及びｗdと関連付けられる。重みｗiはそのタスクに対する命令の再利用の重要度を反映し、重みｗdはそのタスクに対するデータの再利用の重要度を反映する。ｗdより高いｗiを含むタスクは命令を再利用することからより多くの利益を得、ｗdより低いｗiを含むタスクはデータを再利用することからより多くの利益を得る。重みを比較することにより、考えられる最適なキャッシュの再利用のために、スレッドをタスクに一致させる方法又はタスクをスレッドに一致させる方法を決定することが可能である。例えば、タスクＴに対してｗi＝１０及びｗd＝５である場合、そのタスクＴに対して命令の再利用はデータの再利用より重要である。
【００３２】
これらの重み値は、静的又は動的に設定される。重み値の静的決定は演繹的に行われ、プログラムにおけるタスク型に対する重みの動的決定は、実行時に行われ、コンピューティングシステムの現在の状態を反映するように変化する。例えばより大きなデータセットは、命令の再利用が一般により重要なものとして考えられるタスクに対してデータの再利用の重み値ｗdの増加を保証する。
【００３３】
そのようなスレッド−タスクのペアリングがキャッシュの再利用につながる可能性が高い場合、スレッドは所定のタスクを実行するのに適していると仮定され、タスクは所定のスレッド上で実行されるのに適していると仮定される。
【００３４】
２つ以上のＣＰＵが同一のキャッシュユニットを共有する場合、これらのＣＰＵ上で実行されたスレッドを本明細書において計算グループ（ＣＧ）と呼ぶ。ＣＧにおける全てのスレッドは、対応するＣＰＵにより物理的に共有されたキャッシュへの同等のアクセスを有する。例示的な一実現例は、特に図１０Ａに示されるようにＬ２キャッシュに適用されるものとして説明される。しかし、本明細書において開示された手法は、図１０ＢのＬ３最適化等のあらゆるキャッシュレベルに適用されてよい。
【００３５】
一般に、１つ以上のスレッドがＣＰＵに割り当てられるが、好適な一実現例において、１つのスレッドだけがＣＰＵに割り当てられる。所定のスレッドが常に同一のＣＰＵ上で動作するため、このような割り当てにより、実行中にスレッドの親和性として当技術分野において既知である概念を変更しない。
【００３６】
本発明において開示される構成は、タスクレベルでタスクをスレッドにスケジュールすることで従来技術の主な欠点に対処する。タスクがスレッドに割り当てられる結果、その特定のタスクに対して最も重要な種類のキャッシュされた内容（命令又はデータ）を再利用する。このため、命令及びデータのタスクの潜在的な再利用を示すタスク型が重要である。逆に、従来技術は、多くの場合キャッシュラインの使用を厳密に監視することにより、機械語レベルでキャッシュされた内容を再利用する。従って、従来技術は、本明細書において開示される構成より多くのオーバヘッドをプログラム実行に対して課し、多くの場合専用のハードウェアを更に必要とする。
【００３７】
図１は、本発明において開示される構成が実現されるメモリの少なくとも１つのレベルを含むマルチプロセッサコンピュータシステム１００を示す概略ブロック図である。コンピュータシステム１００は、スタンドアロンコンピュータ、例えばＩＢＭ−ＰＣ及びその互換のコンピュータシステム、Ｓｕｎ社のＳＰＡＲＣ（商標）コンピュータシステム又はＡｐｐｌｅ社のＭａｃ（商標）コンピュータシステム等に類似する近年のデスクトップコンピュータである。あるいはコンピュータシステム１００は、例えばプリンタ、撮像システム又は制御システム等の特殊機能装置を部分的に又は完全に実現する。各処理デバイス又は各チップ上のＣＰＵの数、キャッシュ及びそれらの階層的組織の数、並びに他のコンピュータシステムの構成要素は、広範に変動する。コンピュータシステム１００は、多くの処理装置１５０、メモリ１２０、周辺装置インタフェース１９０、ハードディスクドライブシステム（ＨＤＤ）１９２及び読み出し専用メモリ（ＲＯＭ）１９４を有する。示されるように、それらは全てバス１４０、並びに関連付けられたそれぞれの接続１４１、１４２、１４３、１４４及び１４５を介して相互接続される。周辺装置インタフェース１９０により、コンピュータシステム１００は、オプションの接続１９５を介して通信ネットワークを含む他のシステム、他のコンピュータ、プリンタ及び表示装置等のデバイス、並びにキーボード及びマウスポインティングデバイス（不図示）等の制御デバイスと相互接続できる。処理装置１５０及びメモリ１２０は、バス１４０とは別の専用の接続１４５を有する。図１に示されたようなメモリ１２０は、一般的なコンピュータシステムにおいて使用された種々のメモリの構成要素と種類との混合物を示す。従って、メモリ１２０は、マイクロプロセッサデバイス／マイクロコントローラデバイスに組み込まれたＬ１キャッシュ及びＬ２キャッシュ、そのようなデバイスに直接結合されたＬ３キャッシュ、並びにいわゆる「主」記憶を含む。それらは全て、一般に、専用のランダムアクセスメモリ（ＲＡＭ）デバイスとして処理装置１５０と一体化されない半導体ベースのＲＡＭを使用して実現される。コンピュータシステム１００は、ＨＤＤシステム１９２、ＲＯＭメモリ１２０、並びに光ディスクドライブ、ＰＣＭＣＩＡドライブ及びＵＳＢドライブ等の他のデバイスにより示されている他のメモリを含む。それらは、明確にするために示されず、従来独占的にバス１４０に結合し、処理装置１５０に直接結合しない。
【００３８】
一般的なコンピュータシステムにおいて、ＲＯＭ１９４は、一般に処理装置１５０により実行されるためにＨＤＤ１９２の永久記憶装置からのオペレーティングシステム１２２をメモリ１２０にコピーすることにより、コンピュータ１００のオペレーティングシステム１２２をブートすることを含む基本動作処理をコンピュータ１００が開始及び実行できるようにする基本処理を格納する。オペレーティングシステム１２２は、キャッシュメモリ管理がその一部を形成するメモリ管理等の低レベルの動作機能を含むコンピュータの機能の基本制御を提供する。従って、コンピュータシステム上で実行する（高次レベルの）アプリケーションは、オペレーティングシステムにより与えられたデフォルトメモリ管理機能を利用する。しかし、一般に特定のアプリケーションに最適化された性能又は適した性能を実現するために、低レベルの動作よりも自身の制御の影響を行使することを好む（高次レベルの）アプリケーションもある。そのようなアプリケーションは、高次レベルのアプリケーションにより所望されるようにコンピュータシステム１００の低レベルの動作を変形するように構成された特定のソフトウェアアプリケーションをそのように提供するか、あるいはそれを伴う。
【００３９】
通常、図１に示されるように、一般に制御プログラム１３０は、ＨＤＤ１９２に格納されてＨＤＤ１９２からコピーされ、メモリ１２０に常住する。その結果、制御プログラム１３０は、処理装置１５０のＣＰＵ１７１、１７２、１８１及び１８２と関連付けられたスレッドのうちの１つ以上において実行可能である。本発明において、一般に制御プログラム１３０は、特定の目的のためにコンピュータシステム１００上で実行可能なアプリケーションプログラムであり、キャッシュミス率を低下させるためにコンピュータシステム１００のキャッシュメモリを管理し且つキャッシュの再利用を最適化するように別の手法を実現するために本発明に従って構成されたソフトウェアコンポーネントを含む。そのような実現例において、本発明において説明するキャッシュ管理処理は、オペレーティングシステム１２２内のデフォルト処理として組み込まれる。制御プログラム１３０の特定の目的は、広範に変動するが、レンダリング、ラスタリング及び合成等の画像処理アプリケーション、並びに印刷アプリケーションにより生成された印刷タスクを含む。他のアプリケーションは、特に、ワードプロセシングアプリケーション及びデスクトップパブリッシングアプリケーション、金融アプリケーション、ゲーム、通信、データ処理、モニタリング、制御システムを含む。
【００４０】
図１の例に示されるように、処理装置１５０のＣＰＵ１７１、１７２、１８１及び１８２は、２つの計算グループ（ＣＧ）、すなわちＣＧ１６０及びＣＧ１６５に分けられる。
【００４１】
図２は、図１の処理装置１５０及びメモリ１２０の階層的構成の例示的な構成２００を示す。この特定の構成２００において、ＣＧは、同一のＬ２キャッシュを使用するＣＰＵと関連付けられたスレッドから構成され、Ｌ１キャッシュが一般に同一の半導体デバイス上の対応するＣＰＵで構成される図１０Ａの構成によりミラーリングされる。従って、図２は、２つのＣＧ、すなわち、Ｌ２キャッシュ２１０を共有するＣＰＵ１７１及びＣＰＵ１８１のスレッドに対するＣＧ１６０、並びにＬ２キャッシュ２２０を共有するＣＰＵ１７２及びＣＰＵ１８２のスレッドに対するＣＧ１６５を示す。この構成において、説明される構成の実現例は、Ｌ２キャッシュの最適化を提供する。
【００４２】
図１に示された各ＣＰＵは、ユニファイドキャッシュであるか、あるいは専用のデータキャッシュ及び命令キャッシュの２つの独立した物理ユニットから構成される対応する専用Ｌ１キャッシュを有する。図２は、Ｌ１キャッシュ２３１を有するＣＰＵ１７１、Ｌ１キャッシュ２３２を有するＣＰＵ１８１、Ｌ１キャッシュ２３３を有するＣＰＵ１７２及びＬ１キャッシュ２３４を有するＣＰＵ１８２を示す。
【００４３】
同様に、Ｌ２キャッシュ２１０及びＬ２キャッシュ２２０は、統合されるか、あるいは専用のデータキャッシュ及び命令キャッシュの物理的に独立したハードウェアユニットを有する。本発明において説明する種々の実現例において、Ｌ２キャッシュ２１０及び２２０は、物理的配列に拘らず、各々が１つの論理キャッシュユニットとして見なされる。低位メモリレベル２３０構成要素は、この例示的なハードウェア構成においてＬ３キャッシュ及び主メモリである残りの記憶階層を示す。図２の構成の一般的な実現例において、各Ｌ１キャッシュは、対応するＣＰＵと同一の集積回路チップ上に物理的に配置され、各Ｌ２は、対応するＣＰＵデバイスに直接物理的に接続された専用のキャッシュメモリ素子であり、Ｌ３キャッシュは、コンピュータシステム１００の主半導体ランダムアクセスメモリ（ＲＡＭ）内で物理的に区分された仮想場所のグループである。
【００４４】
図３は、エグゼクティブスレッド３０５構成要素及びワーカースレッド３１０構成要素を含む制御プログラム１３０の一実現例を示す。エグゼクティブスレッド３０５構成要素は、制御プログラム１３０の実行を開始及び監督する。ワーカースレッド３１０構成要素は、複数のスレッド（スレッド０、スレッド１、スレッド２．．．）を含み、エグゼクティブスレッド３０５構成要素により指示されたようにこれらのスレッド上でタスクを実行する。例えば、制御プログラム１３０がレンダリング及び合成等の関連付けられた印刷タスクを有するプリンタドライバである場合、エグゼクティブスレッド３０５は、レンダリング等の特定のタスク、並びに／あるいは縁端の追跡及び合成等のそれらの重要な構成要素を実現するワーカースレッド３１０により実行される実際の印刷処理を実施するキャッシュ管理を含むプリンタドライバの管理動作を示す。
【００４５】
本発明において説明する構成は、全てが特定の計算グループ（ＣＧ）内で実行するように制限される特定のスレッドに特定のタスクを一致させることに基づく。これは、スレッドとタスクとの組合せが各通話に対して同一のキャッシュメモリと実質的に関連付けられることにより、キャッシュミス率を潜在的に減少させることを提供する。
【００４６】
エグゼクティブスレッド３０５は、処理を実行するためにタスクを作成すること及び実行するためにこれらのタスクをワーカースレッド３１０にディスパッチすることを担うタスク生成器及びディスパッチャ３３５を備える。作成の際、タスクは、他の属性のうち、実行される命令の集合を識別する型（ＴＡＳＫ＿ＩＤ）、タスクが処理しているデータを識別するＤＡＴＡＳＥＴ＿ＩＤ及びタスクスケジューリング優先順位を割り当てられる。
【００４７】
処理メッセージ３３０構成要素は、制御プログラム１３０内で渡された全てのメッセージを処理することを担い、スケジューラ３４５は、実行するためにタスクをスケジュールすることを担う。スケジューラ３４５は、詳細に後述される機能であるタスクをスレッドに一致させることを担うタスク−スレッド選択器３４０を有する。
【００４８】
エグゼクティブスレッド３０５は、以下の格納構成要素、すなわちＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５、ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０、ＭＥＳＳＡＧＥＳ３１５及びＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０を更に有する。次に、それらの各々の機能及び内容を順番に説明する。
【００４９】
ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５は、実行するためにディスパッチ可能な状態にある制御プログラム１３０において全てのタスクを含むキューデータ構造である。
【００５０】
ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０は、制御プログラム１３０に割り当てられたスレッドのアイデンティティ（ＩＤ）のリストを格納する。リスト３６０におけるスレッドは、現在アイドル状態である制御プログラム１３０と関連付けられた全てのワーカースレッド３１０のサブセットを示すため、タスクの実行に割り当てられない。このリスト３６０は、実行中のあらゆる所定の時間において制御プログラム１３０に対して使用可能な計算リソースを追跡するために保持される。
【００５１】
ＭＥＳＳＡＧＥＳ３１５記憶装置は、制御プログラム１３０の構成要素間で渡されたメッセージを格納する。各メッセージは、その目的を示すＭＡＴＣＨ＿ＴＨＲＥＡＤ、ＭＡＴＣＨ＿ＴＡＳＫ、ＳＴＡＲＴ＿ＴＡＳＫ及びＴＡＳＫ＿ＦＩＮＩＳＨＥＤ等のタイプを有する。ＭＥＳＳＡＧＥ記憶装置３１５は、ＭＡＴＣＨ＿ＴＨＲＥＡＤ又はＭＡＴＣＨ＿ＴＡＳＫのメッセージタイプである処理メッセージ３３０構成要素からタスク−スレッド選択器３４０に渡されるメッセージを提供する。
【００５２】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０は、ＣＧにおいてスレッドの総合的な実行履歴を追跡する。図４に示されるように、記憶装置３８０は３つの構造を有することが好ましい。構造ＣＧ＿ＴＯ＿ＴＨＲＥＡＤ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４１０は、多くのレコード４２５においてＣＧ ＩＤ及び各ＣＧにおけるスレッドのＩＤを含む。従って、テーブル４１０は、対応するＣＧ、すなわち対応するキャッシュメモリと関連付けられたスレッドのサブセットを示す。レコード４２５は、ＣＧ ＩＤを格納するフィールド４１２、そのＣＧにおけるスレッドの数を格納するフィールド４１４を有し、レコード４１６、４１８及び４２０における残りのフィールドは、スレッドをそのＣＧに格納することを示す。
【００５３】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０における第２の構造は、ＣＧ毎に個々のレコード４４５に記録されるＣＧ毎の実行履歴を格納するＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造である。
【００５４】
各レコード４４５は、対応するＣＧにおいてスレッド上で最後に実行されたタスクのタスクＩＤを含むキューデータ構造であるＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０を有するため、ＣＧのタスク履歴を示す。各レコード４４５は、ＣＧにおいてスレッド上で最後に実行されたタスクのデータセットＩＤを含むキューデータ構造であり、ＣＧのデータ履歴を示すＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５を更に有する。要約すれば、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造は、最後に使用された主記憶領域を識別する情報を格納する。
【００５５】
レコード４４５のフィールド４４２はＣＧ ＩＤを格納する。フィールド４４６、４４８及び４５０は、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０の符号化を示す。フィールド４５４、４５６及び４５８は、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５の符号化を示す。フィールド４４４及び４５２は、それぞれ、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５におけるエントリの数を格納する。総合的にスレッドの実行履歴を示すこれらのキューの深度は、最適化されるために使用されるキャッシュのサイズ及び制御プログラム１３０におけるタスクの特徴の双方に依存する。制御プログラム１３０におけるタスクの特徴の例は、タスクの平均コードサイズ及びタスクのコードにおいて最も頻繁に実行された命令の平均サイズである。制御プログラム１３０におけるタスクの特徴、例えばタスクのコードサイズは、キューの深度を事前に決定するため又は制御プログラム１３０の実行中にキュー深度を変更するために使用される。従って、一実現例において、実行履歴は、スレッドにより実行されたタスクと関連付けられた最も一般的に実行された命令のコードサイズに依存するサイズを有する。別の実現例において、実行履歴は、スレッドにより実行されたタスクにより使用されたデータのサイズに依存するサイズを有する。そのキュー深度値は、キュー及び／又はＣＧ毎に異なり、制御プログラム１３０を開始する前に設定されるかあるいは制御プログラム１３０の実行中に動的に変動される。ＣＧ＿ＴＯ＿ＴＨＲＥＡＤ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４１０構造及びＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造の双方は、ＣＧ毎に１つのレコードを含む。
【００５６】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０における第３の構造は、スレッドに対応するレコード４８５において、フィールド４８２におけるスレッドＩＤからフィールド４８４においてスレッドが属するＣＧにルックアップテーブルを格納するＴＨＲＥＡＤ＿ＴＯ＿ＣＧ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４８０構造である。構造４８０は、制御プログラム１３０のワーカースレッド３１０構成要素におけるスレッドの数であるＮ個のレコードを含む。構造４８０は、上述のテーブル４１０の基本的な態様を補完する。
【００５７】
スケジューラ３４５構成要素は、実行するためにタスクをスレッド上でスケジュールすることを担い、メッセージチャネル３９０を介してタスク生成器及びディスパッチャ３３５から生成されたタスクの規格を受信する。スケジューラ３４５は、採用されたスケジューリングアルゴリズムにより決定された順番でＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５を保持する。当技術分野において既知であるあらゆる適切なスケジューリングアルゴリズムは、スケジューラ３４５により採用される。好適な実現例によれば、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５におけるタスクは、降順のタスク優先順位で保持される。すなわち、高優先度タスクはキューの前方にあり、低優先度タスクはキューの後方にある。タスク優先順位は、タスク作成の際に割り当てられ、実行中に後で前後する。タスク−スレッド選択器３４０構成要素は、実行可能な状態にあるタスクをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０からのスレッドと一致させる。次に、図５を参照してタスク−スレッド選択器３４０の機能性を詳細に説明する。
【００５８】
図５は、それぞれ、所定のタスクが使用可能なスレッドと一致されるか又は所定のスレッドがタスクを実行可能な状態にあるかを決定するスケジューラ３４５により実行された処理５００を示す。最初に、ＭＥＳＳＡＧＥ３１５は、ディスパッチャ３３５からスケジューラ３４５に渡される。ＭＡＴＣＨ＿ＴＨＲＥＡＤタイプ又はＭＡＴＣＨ＿ＴＡＳＫタイプのみがディスパッチャ３３５の処理メッセージ３３０構成要素からスケジューラ３４５のタスク−スレッド選択器３４０構成要素に渡されるため、ＭＥＳＳＡＧＥ３１５はこれらの２つのメッセージタイプのいずれかである。ＭＥＳＳＡＧＥ３１５は、メッセージタイプ及び一致されなければならないスレッド又はタスクを含む。例えば、（ＭＡＴＣＨ＿ＴＨＲＥＡＤ、「０」）は、ＩＤ「０」を含むスレッドを実行可能な状態にある適切なタスクと一致させるメッセージ要求である。例えば、メッセージ要求（ＭＡＴＣＨ＿ＴＡＳＫ、［ＤＬ、７］）は、要求により示された型「ＤＬ」により規定されたタスク及びスレッドにより処理されるデータセット「７」を実行するのに適したスレッドを見つける要求である。
【００５９】
スケジューラ３４５は、判断ステップ５０５において、ＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプであるかを決定する。ＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプである場合、処理５００はステップ５１０を介して進み、ＭＥＳＳＡＧＥ３１５において渡されたスレッド上で実行するのに適したタスクを決定する。ＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプではない場合、すなわちＭＡＴＣＨ＿ＴＡＳＫタイプである場合、処理は、ＭＥＳＳＡＧＥ３１５において渡されたタスクを実行するのに適したスレッドを選択することにより、ステップ５２０を介して継続する。次に、これらの２つの例を順番に説明する。
【００６０】
スケジューラ３４５は、判断ステップ５０５においてＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプであると決定する場合、判断ステップ５１０に進む。ステップ５１０において、スケジューラ３４５は、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５が空であるかをチェックする。ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５が空である場合、スケジューラ３４５は、処理ステップ５１５に進み、ブールパラメータＭＡＴＣＨＥＤを「偽」に設定する。次にスケジューラ３４５は、ステップ５５５において、図３に示されるようにタスク又はスレッドの選択を要求したＭＥＳＳＡＧＥ３１５への応答としてエグゼクティブスレッド３０５の処理メッセージ３３０構成要素に送出されるメッセージＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５を作成する。
【００６１】
ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５は、ＭＥＳＳＡＧＥの値及び対（ＴＨＲＥＡＤ、ＴＡＳＫ）を含む。ステップ５１５が生じる場合、一致が不可能であるため、所定のＴＨＲＥＡＤに対するＴＡＳＫの値は、ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５においてヌルに設定される。処理５００はステップ５５５で終了する。
【００６２】
ステップ５１０においてテストされるようなＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５において少なくとも１つのタスクがある場合、ＴＨＲＥＡＤは、ステップ５２５においてＭＥＳＳＡＧＥ３１５から取り出される。次に、ＴＨＲＥＡＤ上で実行するためのタスクは、図６を参照して詳細に後述される処理５３５において選択される。処理はステップ５４５に進む。
【００６３】
ステップ５０５においてＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプではないと処理装置１５０におけるスレッド３０５のスケジューラ３４５が決定する場合、処理５００は、ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０が空であるかをスケジューラ３４５がチェックする判断ステップ５２０に継続する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０が空である場合、ブールパラメータＭＡＴＣＨＥＤは、ステップ５１５において「偽」に設定される。次にスケジューラ３４５は、ステップ５５５においてメッセージＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５を作成する。ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５は、タスク又はスレッドの選択を要求したＭＥＳＳＡＧＥ３１５への応答として処理メッセージ３３０構成要素に送出される。この場合、再度、一致が不可能であるため、所定のＴＡＳＫに対するＴＨＲＥＡＤの値はＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５においてヌルに設定され、処理５００はステップ５５５で終了する。
【００６４】
ステップ５２０に戻り、少なくとも１つの使用可能なスレッドがある場合、処理は、ステップ５３０においてＭＥＳＳＡＧＥ３１５からＴＡＳＫを取り出すことを継続する。次にスケジューラ３４５は、図７Ａ〜図７Ｃを参照して詳細に後述されるように、ＴＡＳＫを実行するためのスレッドを選択する処理５４０を実行する。
【００６５】
それぞれメッセージタイプＭＡＴＣＨ＿ＴＨＲＥＡＤ及びＭＡＴＣＨ＿ＴＡＳＫに対して実行された処理５３５及び５４０の双方は、常に結果として対（ＴＨＲＥＡＤ、ＴＡＳＫ）を取得する。従って、後続のステップ５４５において、ブールパラメータＭＡＴＣＨＥＤは「真」に設定され、次にステップ５５０において、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０は、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造においてＴＨＲＥＡＤのＣＧに対するＴＡＳＫのＴＡＳＫ＿ＩＤ及びＤＡＴＡＳＥＴ＿ＩＤを実行履歴キュー４９０及び４９５に追加することで更新される。ＴＡＳＫのＴＡＳＫ＿ＩＤ及びＤＡＴＡＳＥＴ＿ＩＤは、それぞれキュー４９０及び４９５の前方に追加され、他の全てのエントリは、各キューの最後のエントリ（最も古い）が削除された状態でキューの末尾へ移行される。
【００６６】
処理５００は、ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥがブールパラメータＭＡＴＣＨＥＤの値（ステップ５４５から後続する場合に値「真」を有する）及び対（ＴＨＲＥＡＤ、ＴＡＳＫ）で作成されるステップ５５５で終了する。
【００６７】
図６は、所定のスレッド、すなわちＴＨＲＥＡＤ６０５上で実行するためにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からタスクを選択する処理５３５を示す。処理５３５は、スケジューラ３４５がＴＨＲＥＡＤ６０５のＣＧの履歴を取得するステップ６１０から開始する。これは、ＴＨＲＥＡＤ＿ＴＯ＿ＣＧ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４８０からＴＨＲＥＡＤ６０５に対するレコードにアクセスし、ＴＨＲＥＡＤ６０５が属するＣＧＩＤを特定するフィールド４８４を取得することで実現される。次に、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造から、そのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０から読み出されたタスク履歴及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５から読み出されたデータ履歴を含む実行履歴は、ステップ６１０でアクセスされる。取得ステップ６１５において、スケジューラ３４５は、ＴＨＲＥＡＤ６０５上で実行するのに適したタスクが見つけられるまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてエントリを繰り返す処理を開始する。ステップ６１５において、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の先頭から開始し、タスクＴは、タスク生成器及びディスパッチャ３３５により取得される。ステップ６１７において、タスクＴに対して命令の集合の重み付けｗi及びデータの集合の重み付けｗdを決定する。重み付けは、タスクに対する命令の再利用又はデータの再利用の重要度を決定する。この重みは種々の方法で決定される。種々の方法のうちの１つは、メモリ１２０に格納された制御プログラム１３０において全てのタスク型に対するｗi及びｗdの所定の値のルックアップテーブルを使用することであるが、それに限定されない。次にスケジューラ３４５は、判断ステップ６２０においてｗiがｗdより大きいかをチェックする。ｗiがｗdより大きい場合、タスクＴに対して命令の再利用はデータの再利用より重要であり、処理５３５は、ＴＡＳＫのＴＡＳＫ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にあるかをチェックする判断ステップ６２５に継続する。ＴＡＳＫのＴＡＳＫ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にある場合、タスクＴは適している。ステップ６４５において、スケジューラ３４５はＴＡＳＫをＴに設定し、処理５３５が終了する。
【００６８】
ステップ６２０においてｗiがｗdより大きくないと決定する場合、タスクＴに対して命令の再利用はデータの再利用と同様に重要ではなく、タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５にあるかをチェックするステップ６３０に後続する。タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧのＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられる場合、タスクＴは適切なタスクであり、スケジューラ３４５がＴＡＳＫをＴに設定するステップ６４５に後続し、処理５３５が終了する。
【００６９】
図６においてＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からタスクＴを取得し、且つタスクＴのＴＡＳＫ＿ＩＤ又はＤＡＴＡＳＥＴ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧに対する実行履歴にあるかをチェックする処理は、ステップ６３５においてテストされたように、ＴＡＳＫ＿ＩＤ（ステップ６２５）又はＤＡＴＡＳＥＴ＿ＩＤ（ステップ６３０）を一致させるタスクが見つけられるまで、あるいはキューの後方に到達するまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてタスク毎に繰り返される。
【００７０】
ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてこれ以上タスクがない場合、ステップ６１５及び６３５により形成された処理ループは、ＴＡＳＫをＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５における最初のタスクに設定するステップ６４０に進む。キューの先頭のタスクは最も優先度の高いタスクであり、キャッシュ内容の再利用を実現できない場合、キューの先頭のタスクは実行するためにディスパッチされる。ステップ６４０の後、処理５３５は終了する。
【００７１】
図７Ａは、所定のタスク、すなわちＴＡＳＫ７１５を実行するためにスレッドを選択する処理５４０を示す。処理５４０は、ＣＧ ＩＤのリスト（ＣＧ＿ＩＤ）が実行履歴４４０から作成されることでＣＧを形成するスレッドのサブセットの実行履歴を示すステップ７０５から開始する。ＣＧ＿ＬＩＳＴにおける各エントリは、少なくとも１つの使用可能なスレッドを有する。ＣＧ＿ＬＩＳＴを繰り返す繰返し子は、ステップ７０５において更に設定される。ステップ７１０において、スケジューラ３４５は、ＴＡＳＫ７１５に対して命令の集合の重み付けｗi及びデータの集合の重み付けｗdを決定する。これは種々の方法で決定される。種々の方法のうちの１つは、制御プログラム１３０において全てのタスク型に対するｗi及びｗdの所定の値のルックアップテーブルを使用することであるが、それに限定されない。判断ステップ７２０は、ｗiがｗdより大きいかをチェックする。ｗiがｗdより大きい場合、図７Ｃを参照して詳細に後述するように、ＴＡＳＫ７１５に対して命令の再利用はデータの再利用より重要であり、処理は処理７３０に継続する。
【００７２】
次に図７Ｂを参照して詳細に説明されるように、スケジューラ３４５がステップ７２０においてｗiがｗdより大きくないと決定する場合、ＴＡＳＫ７１５に対して命令の再利用はデータの再利用と同様に重要でないため、処理は処理７２５に継続する。
【００７３】
図７Ｂ及び図７Ｃに示されたステップ７２５及び７３０の処理は、スレッドの実行履歴、並びにタスクと関連付けられた命令及びデータに対して決定された重み付け（ｗi、ｗd）に基づいてＴＡＳＫ７１５を実行するのに適した全てのアイドル（使用可能な）スレッドのサブセットから特定のスレッドを選択する。
【００７４】
図７Ｂは、ＴＡＳＫ７１５に対してデータの再利用が命令の再利用より重要である場合にＴＡＳＫ７１５を実行するのに適したスレッドを選択する処理７２５を示す。従って、処理７２５は、ＴＡＳＫ７１５と関連付けられたデータ履歴に依存し、双方がステップ７０５において前に作成された繰返し子を使用してスケジューラ３４５がＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得するステップ７５０から開始する。次にスケジューラ３４５は、ステップ７５２においてそのＣＧに対するデータ履歴を取得する。これは、そのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５にアクセスするためにＣＧ ＩＤを使用することで実現される。
【００７５】
処理７２５は、ＴＡＳＫ７１５と関連付けられたＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるかをスケジューラ３４５が決定する判断ステップ７５４に継続する。ＴＡＳＫ７１５と関連付けられたＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられる場合、次にステップ７６６において、ＴＡＳＫ７１５を実行するために使用されるＣＧから使用可能なスレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。
【００７６】
ＴＡＳＫ７１５に割り当てられたＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられなかったことがステップ７５４において決定された場合、処理は判断ステップ７５６に進む。ステップ７５６において、データ履歴がまだチェックされていないＣＧ＿ＬＩＳＴにより多くのＣＧがあるかを決定する。ＣＧ＿ＬＩＳＴにより多くのＣＧがある場合、ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるまで又はＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７５０、７５２及び７５４は繰り返される。
【００７７】
ステップ７５６において決定されたようにチェックすべきエントリがこれ以上ＣＧ＿ＬＩＳＴに残っていない場合、処理７２５は、現在使用可能なあらゆるスレッド上でＴＡＳＫ７１５に対してデータの再利用を実現できないため、ＣＧ＿ＬＩＳＴ繰返し子を再設定することでＣＧ＿ＬＩＳＴの繰り返しが最初から開始されるステップ７５８に進む。ＣＧ＿ＬＩＳＴのＣＧ ＩＤのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０におけるエントリは、命令の再利用を実現することを考慮してＴＡＳＫ７１５のＴＡＳＫ＿ＩＤに対してチェックされる。
【００７８】
ステップ７６０において、スケジューラ３４５はＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得する。ステップ７６１において、スケジューラ３４５は、そのグループのスレッドが実行した命令の集合に関するそのＣＧのタスク履歴を取得する。これは、そのＣＧに対するＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造においてＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にアクセスすることで実現される。
【００７９】
判断ステップ７６２において、スケジューラ３４５は、ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられるかをチェックする。ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられる場合を条件として、スケジューラ３４５は、ステップ７６６においてＴＡＳＫ７１５を実行するために使用されるＣＧに割り当てられたワーカースレッド３１０から使用可能なワーカースレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。
【００８０】
ステップ７６２においてＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられない場合、ＴＡＳＫ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられるまで又は判断ステップ７６４において決定されたようにＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７６４、７６０、７６１及び７６２は繰り返される。チェックすべきエントリがこれ以上残っていない場合、ＴＨＲＥＡＤは、ステップ７６８においてＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０で示されたサブセットにより識別されたワーカースレッド３１０からのあらゆるアイドルワーカースレッドに設定される。アイドルスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。処理７２５は、ステップ７６８で終了し、ＴＡＳＫ７１５に対してデータの再利用が命令の再利用より重要である場合にＴＡＳＫ７１５を処理するのに適したスレッドをリスト３６０のサブセットから選択することを実証する。上述したように、スレッドのサブセットの選択は、スレッドの実行履歴及びタスクと関連付けられた命令の再利用又はデータの再利用に対して決定された重み付けに基づく。
【００８１】
図７Ｃは、ＴＡＳＫ７１５に対して命令の再利用が重要である場合に図７Ａにおいて示されたようにＴＡＳＫ７１５を実行するのに適したスレッドを選択する処理７３０を示す。従って、処理７３０は、ＴＡＳＫ７１５と関連付けられた命令履歴に依存し、ステップ７０５において作成されたＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得するステップ７７０から開始する。ステップ７７２において、そのグループのスレッドが最近実行した命令に関するそのＣＧに対する履歴を取得する。これは、そのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にアクセスするためにＣＧ ＩＤを使用することにより実現される。
【００８２】
処理７３０は、ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥにおいて見つけられるかをスケジューラ３４５が決定する判断ステップ７７４に継続する。ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥにおいて見つけられる場合、スケジューラ３４５は、ステップ７８６においてＴＡＳＫ７１５を実行するために使用されるＣＧに割り当てられたワーカースレッド３１０から使用可能なワーカースレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。
【００８３】
ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられない場合、処理は、命令履歴がまだチェックされていないＣＧ＿ＬＩＳＴにより多くのＣＧがあるかをスケジューラ３４５が決定する判断ステップ７７６に到達する。ＣＧ＿ＬＩＳＴにより多くのＣＧがある場合、ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられるまで又はＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７７０、７７２及び７７４は繰り返される。
【００８４】
チェックすべきエントリがこれ以上ＣＧ＿ＬＩＳＴにない場合（判断ステップ７７６）、処理は、現在使用可能なあらゆるスレッド上でＴＡＳＫ７１５に対して命令の再利用を実現できないため、データを再利用しようとすることでＣＧ＿ＬＩＳＴの繰り返しが最初から開始されるステップ７７８に進む。再利用を実現するために、ＣＧ＿ＬＩＳＴにおけるＣＧのＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５は、ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤに対してチェックされる。ステップ７８０において、ＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得する。
【００８５】
ステップ７８１において、スケジューラ３４５はそのＣＧに対するデータ履歴を取得する。これは、データ実行履歴が格納されるＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５にアクセスするためにＣＧ ＩＤを使用することで実現される。
【００８６】
判断ステップ７８２において、スケジューラ３４５は、ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるかをチェックする。ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられる場合、スケジューラ３４５は、ステップ７８６においてＴＡＳＫ７１５を実行するために使用される計算グループＣＧから使用可能なワーカースレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。処理７３０はステップ７８６で終了する。
【００８７】
ＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられない場合、ＤＡＴＡＳＥＴ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるまで又は判断ステップ７８４により決定されたようにＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７８４、７８０、７８１及び７８２は繰り返される。チェックすべきエントリがこれ以上残っていない場合、ＴＨＲＥＡＤは、ステップ７８８においてＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０からのあらゆるスレッドに設定され、処理７３０は終了する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０からのアイドルスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。処理７３０は、ＴＡＳＫ７１５に対して命令の再利用が重要である場合にＴＡＳＫ７１５を処理するのに適したスレッドをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０から選択することを更に実証する。同様に、ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０におけるスレッドのサブセットの選択は、スレッドの実行履歴及びタスクと関連付けられた命令の再利用又はデータの再利用に対して決定された重み付けに基づく。
【００８８】
本発明において説明する処理構成は、同一の計算グループのＣＰＵ上で実行されたタスク間でキャッシュ内容を最大限再利用するためにスレッドをタスクに適切に一致させるようにメモリ１２０に格納された制御プログラム１３０により作成及び実行されたタスクの特徴の知識を使用する。行われなければならない判断の簡潔性及び保持された限られた実行履歴により、タスク−スレッド選択器３４０が招くオーバヘッドを最小限にできる。
【００８９】
次に、図４の構造に類似する構造を示す図８を参照して３つの例を説明する。印刷システムにおいて使用されたラスタイメージプロセッサ（ＲＩＰ）アプリケーションプログラムは、以下の例を説明するために使用される。ＲＩＰアプリケーションプログラムは、制御プログラム１３０の一部を形成する。一般にＲＩＰは、ページの高レベルな記述を印刷記述言語（ＰＤＬ）からラスタ表現に変換する必要がある。ページの高レベルＰＤＬ記述は、テキスト、ライン、フィル領域及び画像データ等のグラフィックオブジェクト、並びにこれらのグラフィックオブジェクトがラスタ表現にレンダリングされる順番を含む。この順番は、一般にｚオーダーとして当技術分野において既知である。ページのラスタ表現は色画素データから構成される。次にプリンタエンジンは、一般に、ページのラスタ表現を用紙等の印刷媒体上に印刷する。ラスタ表現を生成する前、ＲＩＰは、ページの中間ページ表現を生成する。ページの中間ページ表現は、一般にラスタ表現より小型であるが、迅速かつ容易にラスタ表現に変換される。
【００９０】
次に、図１１Ａ〜図１１Ｄを参照して、「フィルマップ」として既知である中間ページ表現の一例を説明する。図１１Ａはページ表現１１００を示す。ページ１１００は、白色の背景を有し、２つのグラフィックオブジェクト１１０１及び１１０２を含む。第１のグラフィックオブジェクト１１０１は、灰色の平坦なフィルを含む不透明な「Ｔ」形のオブジェクトである。第２のグラフィックオブジェクト１１０２は、陰影をつけられたフィルを含む透明な正方形である。他のフィルの例は、直線的に変動する色を表す混合、ビットマップ画像又はタイル型の（すなわち、繰り返された）画像である。第２のグラフィックオブジェクト１１０２は、部分的に第１のグラフィックオブジェクト１１０１に重複する。
【００９１】
図１１Ｂは、画素格子１１２０に従ってページ１１００のグラフィックオブジェクト１１０１及び１１０２を画素整列ラフィックオブジェクトの縁端、レベル、並びにフィルに分解することを示す。グラフィックオブジェクトは、２つ以上の画素整列オブジェクトの縁端、単一のレベル及び１つ以上のフィルに分解される。画素整列グラフィックオブジェクトの縁端は、ラスタ化中のレベルの起動又は停止を規定する。従って、画素整列グラフィックオブジェクトの縁端は、それらが導出されるオブジェクトのレベルを示す。第１のグラフィックオブジェクト１１０１は、２つの画素整列グラフィックオブジェクトの縁端１１２１及び１１２２、並びに灰色の平坦なフィルから構成されるレベル１１３２に分解される。画素整列グラフィックオブジェクトの縁端１１２１及び１１２２は、第１のグラフィックオブジェクト１１０１のレベル１１３２を示す。第２のグラフィックオブジェクト１１０２は、２つの画素整列グラフィックオブジェクトの縁端１１２３及び１１２４、並びに透明な陰影をつけられたフィルから構成されるレベル１１３３に分解される。画素整列グラフィックオブジェクトの縁端１１２３及び１１２４は、第２のグラフィックオブジェクト１１０２のレベル１１３３を示す。背景１１２５は、白色のフィルから構成されるレベル１１３１を有する。
【００９２】
図１１Ｃは、図１１Ａに示されたページ１１００のフィルマップ表現１１４０を示す。フィルマップ表現１１４０は、５つの画素整列フィルマップの縁端から構成される。画素整列フィルマップの縁端の各々は、その画素整列フィルマップの縁端により起動された各画素の色を決定するために使用されるフィルシーケンスを示す。画素整列フィルマップの縁端がアクティブである所定のあらゆる走査線上において、画素整列フィルマップの縁端は、次の画素整列フィルマップの縁端又はページ境界に遭遇するまで画素整列フィルマップの縁端のすぐ右にある画素を起動する。第１の画素整列フィルマップの縁端１１４１は、ページの左手の境界を追跡し、背景フィルを使用して充填される単一の不透明なレベルを含むフィルシーケンス１１５１を示す。第２の画素整列フィルマップの縁端１１４２は、第１のグラフィックオブジェクト１１０１の左手の境界を追跡し、不透明であり且つ灰色の平坦なフィルを使用して充填される単一のレベルを含むフィルシーケンス１１５２を示す。第３の画素整列フィルマップの縁端１１４３は、第１の画素整列フィルマップの縁端１１４１と同一のフィルシーケンス１１５１を示す。第４の画素整列フィルマップの縁端１１４４は、第２のオブジェクト１１０２が白色の背景に重複する領域の左手の境界を追跡する。第４の画素整列フィルマップの縁端１１４４は、２つのレベルを含むフィルシーケンス１１５４を示す。一番上のレベルは、透明であり、陰影をつけられたフィルを使用して充填される。一番下のレベルは、不透明であり、背景フィルを使用して充填される。第５の画素整列フィルマップの縁端１４５は、第２のグラフィックオブジェクト１１０２が第１のグラフィックオブジェクト１１０１に重複する領域の左手の境界を追跡する。第５の画素整列フィルマップの縁端１１４５は、２つのレベルを含むフィルシーケンス１１５３を示す。一番上のレベルは、透明であり、陰影をつけられたフィルを使用して充填される。一番下のレベルは、不透明であり、灰色の平坦なフィルを使用して充填される。
【００９３】
ページのフィルマップ表現１１４０に含まれた画素整列フィルマップの縁端により示されたフィルシーケンス１１５１、１１５２、１１５３及び１１５４を含むフィルシーケンスのテーブルは、ページのフィルマップ表現１１４０を伴う。
【００９４】
図１１Ｄは、図１１Ａに示されたページのタイル型のフィルマップ表現１１６０を示す。タイル型のフィルマップは、４つのタイル１１６５、１１７０、１１７５及び１１８０を含む。各タイルは、８個の画素の高さ及び幅を有する。ページのタイル型のフィルマップ表現１１６０を生成するために、元のフィルマップ表現１１４０の画素整列フィルマップの縁端は、フィルマップタイル境界にわたり分裂されている。例えば、図１１Ｃに示された非タイル型のフィルマップ表現１１４０においてページの左手の境界を追跡する画素整列フィルマップの縁端１１４１は、２つの画素整列フィルマップの縁端１１６６及び１１７６に分割されている。第１の画素整列フィルマップの縁端１１６６は、左上のタイル１１６５の画素を起動し、第２の画素整列フィルマップの縁端１１７６は、左下のタイル１１７５の画素を起動する。また、新しい画素整列フィルマップの縁端は、画素が常駐するタイルの左に対してタイルにおいて画素整列フィルマップの縁端により前に起動された各タイルの最も左の画素を起動するようにタイル境界上に挿入されている。例えば、右上のタイル１１７０において、新しい画素整列フィルマップの縁端１１７１は、図１１Ｃに示された元のフィルマップ表現１１４０において第１のグラフィックオブジェクト１１０１の左手の境界を追跡する画素整列フィルマップの縁端１１４２により起動された画素を起動するように挿入されている。
【００９５】
以下の例を説明するために使用されたＲＩＰアプリケーションは、４つの型のタスク、すなわち表示リスト生成（ＤＬ）、フィルマップ生成（ＦＧ）、フィルマップマージング（ＦＭ）及びフィルマップレンダリング（ＦＲ）から構成される。ＤＬタスクは、ＰＤＬ文書からｚオーダーのグラフィックオブジェクトのシーケンスを読み出し、表示リストを作成する。一般に表示リストは、グラフィックオブジェクトのｙソートリストから構成され、一般に当技術分野において既知である。印刷される所定のページに対して、いくつかのＤＬタスクは、ｚオーダーのグラフィックオブジェクトの種々のシーケンスを処理する必要がある。各シーケンスはｚ帯として既知であり、そのようなシーケンスに対してＤＬタスクにより生成された表示リストは、ｚ帯表示リストとして既知である。ｚ帯表示リスト毎に、ＦＧタスクは、ｚ帯フィルマップとして既知であるフィルマップ表現を生成する。図１１Ａ〜図１１Ｄを参照してフィルマップ表現を上述した。ＦＭタスクは、２つ以上のｚ帯フィルマップを受信し、それらを単一のフィルマップにマージする。より多くのｚ帯フィルマップがページに対して残っている場合、更なるＦＭタスクは、ｚ帯フィルマップをマージする必要がある。マージすべきｚ帯フィルマップがこれ以上残っていない場合、ＦＭタスクにより生成されたフィルマップは、ページ上に全てのグラフィックオブジェクトを示す。次にＦＲタスクは、フィルマップを印刷可能な状態にあるラスタ表現に変換するために使用される。
【００９６】
図８は、制御プログラム１３０の実行中の所定の時間におけるＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０の状態８００を示す。図８に示された例において、第１の構造８２０に示されたようにＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０のＣＧ＿ＴＯ＿ＴＨＲＥＡＤ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥの例を示す２つのＣＧ、すなわちＣＧ０（８２１）及びＣＧ１（８２２）がある。ＣＧ０８２１は２つのスレッド（フィールド８２３に示されたような）を含み、ＣＧ１は２つのスレッド（フィールド８２４に示されたような）を更に含む。フィールド８２５及び８２６にそれぞれ示されるように、ＣＧ０は、スレッド「０」及びスレッド「１」を含む。フィールド８２７及び８２８にそれぞれ示されるように、ＣＧ１は、スレッド「２」及びスレッド「３」を含む。
【００９７】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０の第２の構造８４０は、ＣＧ０及びＣＧ１のＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹテーブルの例を含む。ＣＧ０（８２１）に対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０は、フィールド８４２〜８４４に示された３つのエントリ（フィールド８４１において特定されたような）を有する。ＣＧ０（８２１）のＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１は、フィールド８４６〜８４８に示された３つのエントリ（フィールド８４５において特定されたような）を有する。ＣＧ１（８２２）に対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６２は、フィールド８５２〜８５４に示された３つのエントリ（フィールド８５１において特定されたような）を有する。ＣＧ１（８２２）に対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６３は、フィールド８５６〜８５８に示された３つのエントリ（フィールド８５５において特定されたような）を有する。
【００９８】
図４を参照して上述したように、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥは、各計算グループ上で実行されたタスク型の履歴を含む。従って、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０及び８６２は、ＲＩＰアプリケーションの例において４つのタスク型に対応するＤＬ、ＦＧ、ＦＭ又はＦＲ（ＦＲはこの例において示されない）である値を含む。これらの値は、潜在的に将来のタスクにより再利用されるキャッシュされた命令を示す。同様に、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥは、各計算グループ上で実行されたタスクにより使用されたデータの履歴を含む。ＲＩＰアプリケーションの例において、所定のタスクに対して処理されているページの数は、処理されているデータを示す。従って、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１及び８６３はページ数を含む。ページの数は、潜在的に将来のタスクにより再利用されるキャッシュされたデータを示す。
【００９９】
後続の例において、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０の一部を形成する重み行列８９０は、所定のタスクを処理する場合に命令及びデータの相対的な重要度を決定するために使用される。命令及びデータの相対的な重要度は、所定のタスクを実行するのに適したスレッド又は所定のスレッド上で実行されるのに適したタスクを選択するために使用される。以下の例において使用された重みを図８の重み行列８９０において示す。実行される４つの型のタスク、すなわちＤＬ（８９１）、ＦＧ（８９２）、ＦＭ（８９３）及びＦＲ（８９４）があり、ｗi及びｗdの値は、重み行列８９０においてタスク型毎に与えられたタスクに依存することが好ましい。重み行列８９０における重みは、制御プログラム１３０の前の実行において取得された履歴データを解析すること及びプログラムコードの複雑性の解析等の種々の方法で決定される。換言すると、重み付けは、スレッドのサブセットの実行履歴に基づいて決定される。別の実現例において、重み付けは、タスクの知識に基づいて事前に決定され、メモリ１２０のルックアップテーブルに格納される。
【０１００】
ＲＩＰアプリケーションの例において、ＤＬ（表示リスト生成）タスクは、命令の適切に規定されたシーケンスを実行し、各ＤＬタスクは、グラフィックオブジェクトの別個のシーケンスを処理する。従って、ＤＬタスクの場合、ｗiはｗdより高い値を与えられる。データの別個のｚ帯を更に処理するＦＧ（フィルマップ生成）タスクに対して、同一の推論が適用可能である。また、ＲＩＰアプリケーションの例において、ＦＧタスクは、通常ＤＬタスクに対して別個のスレッド上で実行されるため、ＤＬタスクにより生成された表示リストデータを利用できないことが多い。従って、ＦＧタスクの場合、ｗiはｗdより高い値を更に与えられる。ＦＭ（フィルマップマージング）タスクは、多数のＦＧタスクにより生成されたフィルマップデータを受信する。このフィルマップデータが大量のメモリを消費するため、可能な場合は常にキャッシュに格納されたフィルマップデータを再利用することが有益である。従って、ＦＭタスクの場合、ｗdはｗiより高い値を与えられる。各ＦＲ（フィルマップレンダリング）タスクは、印刷されている別個のページからのフィルマップを処理する。従って、ＦＲタスク間でのデータの再利用の機会は殆どない。従って、ＦＲタスクの場合、ｗiはｗdより高い値を与えられる。命令の再利用及びデータの再利用に対してタスク及びそれらの挙動のこのような知識を有することは、重み付けがタスク型に基づくことを意味する。
【０１０１】
例１
次に、所定のスレッドに対してタスクを選択する一例を説明する。タスク［ＤＬ、６］を処理した後にスレッド「０」が使用可能になったと仮定する。タスク［ＦＭ、２］は、降順の優先順位で配置されて実行可能な状態にある他のタスクが後続したＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の先頭にある。ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の状態は以下の通りである。
［ＦＭ、２］［ＤＬ、７］［ＤＬ、８］［ＦＧ、３］［ＦＧ、４］［ＦＧ、５］
【０１０２】
図３を参照して上述したように、ＭＥＳＳＡＧＥ３１５はタスク−スレッド選択器３４０に送出される。例１において、ＭＥＳＳＡＧＥ３１５は、ＭＡＴＣＨ＿ＴＨＲＥＡＤタイプであり、スレッドＩＤ「０」（８２５）を含む。従って、図６を参照して上述した処理５３５が実行されることにより、スレッド「０」上で実行するのに適したタスクをＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５から選択する。スレッド「０」のＣＧがＣＧ０（８２１）であるため、ＣＧ０の実行履歴は、スレッド「０」上で実行すべきタスクを決定するために使用される。
【０１０３】
スケジューラ３４５は、処理５３５において、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からこの例においてはタスク［ＦＭ、２］である第１のタスクを選択する。タスクのＦＭ型であるため、重み行列８９０に従って、タスク［ＦＭ、２］は、ｗi＝５及びｗd＝１０を有する。これは、タスク［ＦＭ、２］に対してデータの再利用が命令の再利用より重要であることを意味する。
【０１０４】
従って、処理５３５は、ＤＡＴＡＳＥＴ＿ＩＤ＝２がステップ６３０においてＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１にあるかを決定する。ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１は、ＤＡＴＡＳＥＴ＿ＩＤ＝２を含まない。従って、処理５３５は、例１においてはタスク［ＤＬ、７］であるＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５において次のタスクに進む。
【０１０５】
タスク［ＤＬ、７］は、ＤＬ型であり、重み行列８９０に従ってｗi＝１０及びｗd＝５を有する。これは、ＤＬタスク型に対して命令の再利用より重要であることを意味する。従って、処理５３５は、ステップ６２５においてＴＡＳＫ＿ＩＤ＝ＤＬがスレッド「０」のＣＧ０のＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０にあるかを決定する。スレッド「０」ＣＧ０のＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０は、ＴＡＳＫ＿ＩＤ＝ＤＬを含む。従って、処理５３５は、タスク［ＤＬ、７］がスレッド「０」により実行されるのに適していると決定する。処理５３５は終了し、ブールパラメータＭＡＴＣＨＥＤが「真」に設定されるステップ５４５、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０におけるＣＧ０の実行履歴が更新されるステップ５５０、並びにＭＡＴＣＨＥＤの値及びスレッド−タスク対（「０」、［ＤＬ、７］）を含むＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥが作成されるステップ５５５が実行される。
【０１０６】
例２
次に、所定のタスクに対するスレッドを選択する一例を説明する。実行されるタスク［ＦＭ、２］に対して要求されると仮定する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０の状態は以下の通りである。
｛「０」、「３」｝
【０１０７】
図３を参照して上述したように、ＭＥＳＳＡＧＥ３１５はタスク−スレッド選択器３４０に送出される。例２において、ＭＥＳＳＡＧＥ３１５は、タスク［ＦＭ、２］に対するＭＡＴＣＨ＿ＴＡＳＫタイプである。従って、図７Ａを参照して上述した処理５４０が実行されることにより、タスク［ＦＭ、２］を実行するのに適したスレッドをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０から選択する。双方のＣＧが少なくとも１つのアイドルスレッドを有するため、ステップ７０５において作成されたＣＧ＿ＬＩＳＴは、｛ＣＧ０、ＣＧ１｝である。
【０１０８】
タスク［ＦＭ、２］はＦＭ型であり、重み行列８９０に従って、ｗi＝５及びｗd＝１０を有する。これは、タスク［ＦＭ、２］に対してデータの再利用がより重要であることを意味する。従って、処理５４０はデータの再利用に対するスレッドを選択する。従って、図７Ｂを参照して上述した処理７２５が実行される。
【０１０９】
処理７２５は、使用可能なスレッドを含むＣＧのリスト、すなわちＣＧ＿ＬＩＳＴからこの例においてはＣＧ０である第１のＣＧを選択する。データの再利用が処理７２５の目的であるため、処理７２５は、タスク［ＦＭ、２］と関連付けられたＤＡＴＡＳＥＴ＿ＩＤ＝２がＣＧ０のＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１にあるかを決定する。ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０は「ＦＭ」を含むが、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１はＤＡＴＡＳＥＴ＿ＩＤ＝２を含まない。従って、処理７２５は、ＣＧ＿ＬＩＳＴにおいて使用可能なスレッドを含む例２においてはＣＧ１である次のＣＧに進む。
【０１１０】
ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６３は、ＤＡＴＡＳＥＴ＿ＩＤ＝２を含む。従って、スケジューラ３４５は、処理７２５においてＣＧ１から使用可能なスレッドがタスク［ＦＭ、２］を実行するのに適しているかを決定する。処理７２５は、ＣＧ１から使用可能なスレッド「３」を選択する。次に、ブールパラメータＭＡＴＣＨＥＤが「真」に設定されるステップ５４５、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０におけるＣＧ１の実行履歴が更新されるステップ５５０、並びにＭＡＴＣＨＥＤの値及びスレッド−タスク対（「３」、［ＦＭ、２］）を含むＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥが作成されるステップ５５５が実行される。
【０１１１】
例３
次に、所定のスレッドを選択する別の例を説明する。例３は、所定のタスクに対して命令の再利用が重要である場合の例を示すが、いずれの使用可能なスレッドによっても満たされない。タスク［ＦＲ、１］が実行されるのを待っていると仮定する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０の状態は以下の通りである。
｛「０」、「３」｝
【０１１２】
図３を参照して上述したように、ＭＥＳＳＡＧＥ３１５はタスク−スレッド選択器３４０に送出される。この例において、ＭＥＳＳＡＧＥ３１５は、タスク［ＦＲ、１］に対するＭＡＴＣＨ＿ＴＡＳＫタイプである。従って、図７Ａを参照して上述した処理５４０が実行されることにより、タスク［ＦＲ、１］を実行するのに適したスレッドをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０から選択する。双方のＣＧが少なくとも１つのアイドルスレッド、すなわち使用可能なスレッドを有するため、ステップ７０５において作成されたＣＧ＿ＬＩＳＴは｛ＣＧ０、ＣＧ１｝である。
【０１１３】
タスク［ＦＭ、１］はＦＭ型であり、重み行列８９０に従って、ｗi＝１０及びｗd＝５を有する。これは、［ＦＲ、１］に対して命令の再利用がより重要であることを意味する。従って、処理５４０は、命令の再利用に対するスレッドを選択することを判断する。従って、図７Ｃを参照して上述した処理７３０が実行される。
【０１１４】
スケジューラ３４５は、処理７３０において使用可能なスレッドを含むＣＧのリスト、すなわちＣＧ＿ＬＩＳＴからこの例においてはＣＧ０である第１のＣＧを選択する。命令の再利用が処理７３０の目的であるため、処理７３０は、タスク［ＦＲ、１］と関連付けられたＴＡＳＫ＿ＩＤ＝ＦＲがＣＧ０のＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０において見つけられるかを決定する。ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０はＴＡＳＫ＿ＩＤ＝ＦＲを含まない。従って、処理７３０は、ＣＧ＿ＬＩＳＴにおいて使用可能なスレッドを含む本発明の例においてはＣＧ１である次のＣＧに進む。処理７３０は、ＣＧ１と関連付けられたＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０がＴＡＳＫ＿ＩＤ＝ＦＲを含まないことを更に決定する。従って、処理７３０は、データの再利用に対して適切なスレッドを見つけることに進む。
【０１１５】
処理７３０は、タスク［ＦＲ、１］と関連付けられたＤＡＴＡＳＥＴ＿ＩＤ＝１がＣＧ０のＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１にあるかを決定する。ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１は、ＤＡＴＡＳＥＴ＿ＩＤ＝１を含む。従って、処理７３０は、ＣＧ０からの使用可能なスレッドがタスク［ＦＲ、１］を実行するのに適していると決定する。処理７３０は、ＣＧ０からスレッド「０」を選択する。その後、スレッド「０」はタスク［ＦＲ、１］の実行に進む。
【０１１６】
次に、ブールパラメータＭＡＴＣＨＥＤが「真」に設定されるステップ５４５、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０におけるＣＧ０の実行履歴が更新されるステップ５５０、並びにＭＡＴＣＨＥＤの値及びスレッド−タスク対（「０」、［ＦＲ、１］）を含むＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥが作成されるステップ５５５が実行される。
【０１１７】
次に、図９に示されるように所定のＴＨＲＥＡＤ上で実行するのに適したタスクを選択する処理９００を参照して、別の実現例を説明する。処理９００は、図６に示されたような処理５３５の代わりに使用されてもよい。この実現例において、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造に保持された命令及びデータの履歴は、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５の２つのキューにおけるより最近のものでない項目の前にチェックされたＴＨＲＥＡＤ９０５のＣＧに対するこれらの双方のキューにおけるより最近の項目と組み合わされる。
【０１１８】
処理９００は、ＴＨＲＥＡＤ９０５のＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５から作成されたリスト構造ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹを使用する。リスト構造は、一般にシーケンスのタプルをタプルのシーケンスにマッピングするコンボリューション（又はジップ）として当技術分野において既知である処理において形成される。この場合、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５のそれぞれの項目Ｈi及びＨdは、ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストに保持された対のシーケンスを形成する。履歴キューが他のキューより短い場合、他のキューからの相対物を有さないエントリは、値ヌルと対にされる。例えば、そのＣＧに対してＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０が３つのエントリを有し、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５が５つのエントリを有する場合、所定のＣＧに対するＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストは以下のように見える。
｛（ＤＬ、６）、（ＤＬ、５）、（ＤＬ、４）、（Ｎｕｌｌ、３）、（Ｎｕｌｌ、２）｝
【０１１９】
次に、処理９００を説明する。処理９００は、スケジューラ３４５がＴＨＲＥＡＤ９０５のＣＧの履歴を取得し、そのＣＧに対するＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストを作成したステップ９１０から開始する。これは、ＴＨＲＥＡＤ＿ＴＯ＿ＣＧ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４８０からＴＨＲＥＡＤ９０５に対するレコードにアクセスし、ＴＨＲＥＡＤ９０５が属し、その後格納されるＣＧ ＩＤフィールド４８４を取得することで実現される。次に、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造において、そのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５を含む実行履歴がアクセスされ、対のＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストが上述したように作成される。ステップ９１２において、履歴エントリの第１の対（Ｈi、Ｈd）を取得することでＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストのエントリを繰り返す処理が開始する。
【０１２０】
ステップ９１５において、スケジューラ３４５は、ＴＨＲＥＡＤ６０５上で実行するのに適したタスクが見つけられるまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてエントリを繰り返す処理を開始する。ステップ９１５において、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の先頭から開始し、タスクＴを取得する。ステップ９１７において、スケジューラ３４５は、タスクＴに対して重みｗi及びｗdを決定する。この重みは種々の方法で決定される。種々の方法のうちの１つは、制御プログラム１３０において全てのタスク型に対するｗi及びｗdの所定の値のルックアップテーブルを使用することであるが、それに限定されない。判断ステップ９２０において、スケジューラ３４５はｗiがｗdより大きいかをチェックする。ｗiがｗdより大きい場合、タスクＴに対して命令の再利用はデータの再利用より重要であり、処理は、ＴＡＳＫのＴＡＳＫ＿ＩＤがステップ９１２において取得した履歴エントリの対（Ｈi、Ｈd）からのタスク型Ｈiと同一であるかをチェックする判断ステップ９２５に継続する。ＴＡＳＫのＴＡＳＫ＿ＩＤがステップ９１２において取得された履歴エントリの対（Ｈi、Ｈd）からのタスク型Ｈiと同一である場合、タスクＴは適切であるため、ステップ９４５においてＴＡＳＫをＴに設定し、処理９００が終了する。
【０１２１】
ステップ９２０において、ｗiがｗdより大きくないとスケジューラ３４５が決定する場合、タスクＴに対して命令の再利用はデータの再利用と同様に重要ではなく、ステップ９３０において、タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがステップ９１２において取得された履歴エントリの対（Ｈi、Ｈd）からのＤＡＴＡＳＥＴ＿ＩＤ＝Ｈdと同一であるかをチェックする。タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがステップ９１２において取得された履歴エントリの対（Ｈi、Ｈd）からのＤＡＴＡＳＥＴ＿ＩＤ＝Ｈdと同一である場合、タスクＴは適切なタスクであるため、ステップ９４５においてＴＡＳＫをＴに設定し、処理９００が終了する。
【０１２２】
ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からタスクＴを取得し、且つＴＡＳＫ＿ＩＤ又はＤＡＴＡＳＥＴ＿ＩＤがＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにあるかをチェックする処理は、ステップ９３５においてテストされたように、Ｈi又はＨdを一致させるタスクが見つけられるまで、あるいはキューの後方に到達するまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてタスク毎に繰り返される。
【０１２３】
チェック、判断ステップ９３５において決定すべきタスクがこれ以上ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５にない場合、スケジューラ３４５がまだチェックされていないより多くのエントリがＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにあるかをチェックするステップ９３７に進む。まだチェックされていないより多くのエントリがＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにある場合、ステップ９３６において、ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにおける次のエントリに対する適合性に対して最初からＲＥＡＤ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５におけるタスクをチェックし始めるためにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５繰返し子を再設定する。その後処理は、履歴エントリの次の対がＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストから取得されるステップ９１２に戻る。
【０１２４】
判断ステップ９３７において、チェックすべきエントリがこれ以上ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにないとスケジューラ３４５が決定する場合、処理９００は、ＴＡＳＫをＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５における第１のタスクに設定するステップ９４０に進む。キューの先頭のタスクは最も優先度の高いタスクであり、キャッシュ内容の再利用を実現できない場合、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５における第１のタスクは、実行するためにディスパッチされたタスクである。処理９００はステップ９４０で終了する。
【０１２５】
実行履歴キューＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５、並びにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５において双方のエントリを繰り返す複雑性が増加したことによる何らかの余分なオーバヘッドを含むキャッシュ内容の再利用の機会を改善するために、処理９００は、図５の処理５３５の代わりに使用されてもよい。
【産業上の利用可能性】
【０１２６】
説明した構成は、コンピュータ産業及びデータ処理産業、並びに特にキャッシュの再利用を増進するキャッシュメモリに対して適用可能である。
【０１２７】
上記の記述は本発明のいくつかの実施形態のみを説明し、本発明の範囲及び趣旨から逸脱せずに、変形及び／又は変更がいくつかの実施形態に対して行なわれてもよい。実施形態は、限定するものではなく例示するものである。例えば、説明した好適な構成は、各計算グループを対応するＬ２キャッシュと関連付けることでＬ２キャッシュを最適化する計算グループの動的構成に注目したが、同一の原理は、図１０Ｂに示されたようなＬ３キャッシュ等の他のキャッシュレベルを最適化するために適用されてもよい。図１０Ｂにおいて、Ｌ３最適化のためのＬ３キャッシュに対応する計算グループＣＧが形成される。
【技術分野】
【０００１】
本発明は、コンピュータベースのシステムに関し、特にアプリケーションプログラム内の処理スケジューリングによりキャッシュヒット率の向上に関するものである。
【背景技術】
【０００２】
コンピュータシステムにおけるキャッシュメモリは、中央処理装置（ＣＰＵ）が容易に且つ高速にアクセスするために、主記憶場所からの命令又はオペランドであるデータ項目のコピーを格納するために使用される。キャッシュの再利用は、メモリアクセス時間を短縮することにより殆どのソフトウェアアプリケーションにとって大幅な実行時間の短縮につながるため、非常に望ましい。処理（又はマルチスレッドアプリケーションにおけるスレッド）内の効率的なキャッシュの再利用は、アプリケーションプログラムコードの品質に依存し、処理間及びスレッド間の効率的なキャッシュの再利用は、キャッシュに既にロードされているものを追跡すること、並びにキャッシュ内容の再利用を考慮して次に実行するための後続の処理／スレッドを選択することを含む。
【０００３】
キャッシュ内容を追跡することは、一般に、ハードウェア手段又はソフトウェア技術を採用することで当技術分野において実現される。多くの場合、収集されたキャッシュ内容情報の正確度とその処理専用の時間及びリソースの量との間にはトレードオフの関係がある。キャッシュの再利用方法は、一般化されることによりあらゆるプログラム又は処理に対して適用可能なものもあるが、より特化されるものもある。
【０００４】
また、データキャッシュ内容の再利用を目標とする方法もあるが、命令キャッシュ内容の再利用を目標とする方法もある。場合によっては、方法は、特にどちらかを目標とすることなく、データ及び命令の双方に対して適用可能である。
【０００５】
従来技術において既知であるデータキャッシュの再利用に対する１つの手法は以下の通りである。データを全く共有しない処理は、マルチプロセッサシステムにおいて可能であれば種々のプロセッサ上でスケジュールされる。また、依存関係のために同時に実行されないが、互いに共通データを共有する処理は、それらがキャッシュ内容を共有できるような方法でＣＰＵ上でスケジュールされる。方法は、特定のアプリケーションにおいて動作可能なアルゴリズムの詳細な知識を必要とし、データの再利用のみを考慮する。
【０００６】
他の従来技術は、同一のプロセッサ上で同一の処理をスケジュールすることで命令データの局所性を向上することを目的とする。命令の再利用のみを考慮する。
【０００７】
いくつかの従来技術の方法の主な欠点は、それらがデータの再利用又は命令の再利用を簡略化するように設計されるが、双方を考慮しないことである。
【０００８】
他には、より一般的な従来技術の手法は、所定の処理に対してキャッシュ内容の「キャッシュウォーム（cache warmth）」を測定することにより、ハードウェア手段又はソフトウェア技術を用いて命令の再利用及びデータの再利用の双方を簡略化することである。キャッシュウォームは、キャッシュにおいて見つけられた特定の処理のデータの古さを示すために使用される場合がある用語であり、処理毎に各プロセッサの要求の数をカウントする方法又はキャッシュのサブセクションに対するキャッシュミスを追跡する方法、あるいはライン毎のキャッシュの利用を追跡する方法等を含む従来技術における種々の方法で測定される。ＣＰＵがキャッシュにおいてデータ項目を見つけられない場合にキャッシュミスが発生する。これにより、関連付けられた性能ペナルティでより低いレベルのキャッシュ又は主記憶からデータ項目を取り出すことが必要になる。
【０００９】
キャッシュ内容の再利用に対するこれらのより一般的な従来技術の手法の主な欠点は、それらの複雑性及びその複雑性がプログラム実行に対して課すオーバヘッドにある。それらは、実現するために専用ハードウェアを更に必要とすることが多い。
【発明の概要】
【００１０】
本発明の目的は、従来技術の構成の１つ以上の欠点を実質的に克服するかあるいは少なくとも改善することである。
【００１１】
本発明によれば、アプリケーションの内部知識を有するスケジューラは、重い処理オーバヘッドを課さずにコンピュータシステムにおいてコンテキストを切り替える結果発生するキャッシュミスを減少することでキャッシュミス率を最小限にするように配置される。
【００１２】
多くのグループ内のスレッドの総合的な実行又は処理の履歴及び実行されるタスクの特徴の双方に基づいて、タスクを実行するスレッドのこれらのグループのうちの１つにプリファレンスが与えられる構成が開示される。
【００１３】
本発明の一態様によれば、マルチプロセッサのコンピュータシステムにおいて、タスクを実行すべく複数のスレッドから１つのスレッドを決定する方法であって、複数のスレッドはコンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化されており、タスクは命令の集合により決定される型を有しており、当該方法は、複数のスレッドのサブセットの実行履歴を取得するステップと、命令の集合及びデータの集合の各々に対し、タスクの型に依存している重み付けを決定するステップと、実行履歴と決定された重み付けとに基づいて、タスクを実行すべく複数のスレッドのサブセットの適合性を決定するステップと、複数のスレッドのサブセットの決定された適合性を条件として、複数のスレッドのサブセットに関連付けられたキャッシュメモリの内容を使用して、タスクを実行すべく複数のスレッドのサブセットから１つのスレッドを決定するステップと、を含む方法が提供される。
【００１４】
使用される複数のスレッドのサブセットの適合性を決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することが望ましい。複数のスレッドのサブセットの適合性を決定するステップは、命令に対する重み付けがデータに対する重み付けより大きい場合に、タスクを実行すべく複数のスレッドのサブセットの適合性を決定するために、データ履歴の前にタスク履歴を検査するサブステップと、データに対する重み付けが命令に対する重み付けより大きい場合に、タスクを実行すべく複数のスレッドのサブセットの適合性を決定するために、タスク履歴の前にデータ履歴を検査するサブステップと、を含むことが望ましい。
【００１５】
重み付けは、複数のスレッドのサブセットの実行履歴に基づいて決定されることが好適である。あるいは、重み付けは、ルックアップテーブルを使用して決定され得る。
【００１６】
一般に、キャッシュメモリのサイズに依存したサイズを有する。あるいは、実行履歴は、複数のスレッドにより実行されるタスクの集合に関連して最も多く実行された命令のサイズに依存したサイズを有する。更に別の方法において、実行履歴は、複数のスレッドにより実行されるタスクの集合により使用されたデータに依存したサイズを有する。
【００１７】
本発明の他の態様によれば、マルチプロセッサのコンピュータシステムにおいて、印刷タスクを処理するためのキャッシュメモリのキャッシュ再利用を管理する方法であって、キャッシュメモリは複数のスレッドのサブセットと関連付けられており、印刷タスクは該印刷タスクのための命令の集合により決定される型を有しており、当該方法は、複数のスレッドのサブセットの実行履歴を取得するステップと、命令の集合及びデータの集合の各々に対し、印刷タスクの型に依存している重み付けを決定するステップと、実行履歴と決定された重み付けとに基づいて、印刷タスクを実行すべく複数のスレッドのサブセットの適合性を決定するステップと、印刷タスクを処理するサブセットから１つのスレッドを決定することにより複数のスレッドのサブセットが適切であると決定される場合に、キャッシュメモリを再利用するステップと、を含む方法が提供される。
【００１８】
本発明の更に他の態様によれば、マルチプロセッサのコンピュータシステムにおいて、スレッドによる実行のために複数のタスクから１つのタスクを決定する方法であって、スレッドはコンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化される複数のスレッドの１つであり、タスクは命令の集合により決定される型を有しており、当該方法は、スレッドの実行履歴を取得し、対応するキャッシュメモリを識別するステップと、実行のために利用可能なタスクを識別し、命令の集合及びデータの集合の各々に対し、識別されたタスクの型に依存している重み付けを決定するステップと、実行履歴と決定された重み付けとに基づいて、スレッドで実行すべく識別されたタスクの適合性を決定するステップと、複数のスレッドのサブセットの決定された適合性を条件として、対応するキャッシュメモリの内容に基づいて、複数のタスクからスレッドで実行される１つの識別されたタスクを決定するステップと、を含む方法が提供される。
【００１９】
重み付けが、使用されるタスクを決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することが望ましい。スレッドによる実行のために複数のタスクから１つのタスクの適合性を決定するステップは、タスクの命令に対する重み付けがデータに対する重み付けより大きい場合に、スレッドにより実行されるタスクの適合性を決定するために、データ履歴の前にタスク履歴を検査するサブステップと、タスクのデータに対する重み付けが命令に対する重み付けより大きい場合に、スレッドにより実行されるタスクの適合性を決定するために、タスク履歴の前にデータ履歴を検査するサブステップと、を含むことが望ましい。
【００２０】
他の態様も更に開示する。
【００２１】
次に、以下の図面を参照して本発明の少なくとも１つの実施形態を説明する。
【図面の簡単な説明】
【００２２】
【図１】説明される構成が実現される例示的なコンピュータシステムの一部を示す概略ブロック図である。
【図２】図１のコンピュータシステムの処理装置及びメモリ装置の一例を示す概略ブロック図である。
【図３】図１の制御プログラム１３０に対する例示的なアーキテクチャを示す概略ブロック図である。
【図４】図３のＥＸＥＣＵＴＩＯＮ−ＲＥＧＩＳＴＥＲ３８０格納構成要素のメモリレイアウトを示す図である。
【図５】受信したＭＡＴＣＨ＿ＴＨＲＥＡＤメッセージ及びＭＡＴＣＨ＿ＴＡＳＫメッセージに応答してタスクをスレッドに一致させる処理を示すデータフローチャートである。
【図６】所定のスレッド上で実行するためにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥからタスクを選択する処理を示すデータフローチャートである。
【図７Ａ】所定のタスクを実行するためにＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴからスレッドを選択する処理を示すデータフローチャートである。
【図７Ｂ】データの再利用が重要である場合に所定のタスクを実行するためにＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴからスレッドを選択する処理を示すデータフローチャートである。
【図７Ｃ】命令の再利用が重要である場合に所定のタスクを実行するためにＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴからスレッドを選択する処理を示すデータフローチャートである。
【図８】マルチスレッドソフトウェアプログラムの実行の所定の時点におけるＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０データ構造（図４のメモリレイアウトに従う）のメモリ内容を示す図である。
【図９】所定のスレッド上で実行するためにタスクを選択する図６に示されたデータフローチャートに対する別の手法を示すデータフローチャートである。
【図１０Ａ】Ｌ２及びＬ３のキャッシュ最適化に対する例示的な構成を示す図である。
【図１０Ｂ】Ｌ２及びＬ３のキャッシュ最適化に対する例示的な構成を示す図である。
【図１１Ａ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【図１１Ｂ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【図１１Ｃ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【図１１Ｄ】印刷処理の一部であるフィルマップ表現の形成を示す図である。
【発明を実施するための形態】
【００２３】
コンピュータシステムにおいてマルチプロセッサアーキテクチャを使用することで性能速度の高速化を実現する傾向は、近年広範に使用されるようになってきている。マルチプロセッサアーキテクチャにより、１つ以上の処理に属する多くのスレッドが多くの中央処理装置（ＣＰＵ）を介して並列に実行できるため、実行時間全体が短縮される。
【００２４】
ＣＰＵの数及び速度と共に、コンピュータシステムのメモリ構成は、処理速度に大きく影響する。階層的記憶構造は、キャッシュと呼ばれるより小型で高速なメモリをＣＰＵにより近接させた近年のメモリシステムに対して一般に受け入れられたアーキテクチャである。記憶階層において同一の深度に配置されたキャッシュは、同一のキャッシュレベルであると言われる。キャッシュメモリは、容易でより高速なアクセスのためにＣＰＵにより近接する主記憶内容のサブセットを格納するために使用される。
【００２５】
レベル１（Ｌ１）キャッシュは、ＣＰＵに最近接し、同一のハードウェアチップ上に配置又は構成される。Ｌ１キャッシュは小型で非常に高速である。レベル２（Ｌ２）キャッシュはＬ１キャッシュより大きい。Ｌ２は、一般にＣＰＵチップ上の最後のキャッシュである。レベル３（Ｌ３）キャッシュは、存在する場合により大きいために上位レベルのキャッシュより低速であるが、依然として主記憶よりはるかに高速である。一般にＣＰＵのすぐ隣のコンピュータマザーボード上に配置されたＬ３キャッシュは、ＣＰＵと直接専用に相互接続していることが多い。一般にＬ３キャッシュは、単にサイズがより大きいためにＬ１キャッシュ及びＬ２キャッシュよりキャッシュミスの発生が少ない。
【００２６】
各レベルにおいて、キャッシュは、物理的に独立したデータキャッシュ及び命令キャッシュ又はデータ及び命令の双方に対するユニファイドキャッシュから形成される。双方の場合において、データ及び命令は個別に考えられる。本発明において開示される構成は、双方の場合に対して使用される。
【００２７】
項目（命令又はオペランド（データ））が初めてＣＰＵにより要求されると、項目が属する主記憶ブロックの内容は、キャッシュラインにおいてキャッシュにロードされる。同一の項目又は同一のブロックからの項目に対する後続の要求は、そのキャッシュラインにアクセスすることで満たされる。要求された項目がキャッシュにおいて見つけられる場合、当技術分野においてキャッシュヒットとして既知であるイベント、すなわち要求された項目へのアクセスは、キャッシュミス上で発生する要求された項目が主記憶から取り出されなければならない時よりはるかに高速である。キャッシュにロードされるものは全てあらゆる種類のデータであるが、プログラムコードが動作するプログラムコード（命令）とオペランド（データ）との間で区別されることが多い。この説明において、前者を「命令」と呼び、後者を単に「データ」と呼ぶ。アプリケーションを実行するために使用されているプロセッサは、キャッシュが命令又はデータを含むかを決定し、且つ万が一キャッシュミスの場合にキャッシュラインをロードする処理を実行する。本発明において開示される構成は、命令及びデータのキャッシュを管理する全ての一般的な方法に対して適用可能である。
【００２８】
マルチプロセッサシステムにおいて並列性を利用するために、一般に処理は、タスクとして既知である本明細書の目的で、並列に実行される動作の独立単位に大きく細分される。プログラムの実行には１つ以上のタスクを完了する必要がある。各タスクは、並列に実行される場合にスレッド上で実行される。
【００２９】
本発明において開示される構成の好適な実現例において、タスクとスレッドとの間で一対一対応が維持される。すなわち、タスクは一度に１つのスレッドのみにおいて実行される。タスクの例には、グラフィックイメージ作成プログラムにおけるレンダリング処理及びスプレッドシートアプリケーションにおいて数値データの列に帰された数学演算子が含まれる。従って、タスクのサイズ及び複雑性が変動し、これは、アプリケーションプログラムが符号化されるかあるいは実行されることが望まれる方法に従う。
【００３０】
スケジューリングの観点から、タスクは、動作の最小のスケジュール可能な単位であり、常に完了する。タスクは、その型（ＴＡＳＫ＿ＩＤ）及びタスクが処理するデータ（ＤＡＴＡＳＥＴ＿ＩＤ）により規定される。ＴＡＳＫ＿ＩＤは、関連付けられたタスクが実行される場合に実行されると予想される命令の集合を識別する。ＤＡＴＡＳＥＴ＿ＩＤは、タスクの実行中に読み出されるか又は書き込まれると予想されるか、あるいはそれら双方を予想される記憶場所の集合を識別する。タスク型は命令の集合により規定される。
【００３１】
種々のタスク型は種々の特徴を有する。その特徴のうちの１つは、命令及びデータの使用パターンである。従って、データ及び命令の再利用の相対的な重要度は種々のタスク毎に異なる。本発明において開示される構成において、２つの重み値は、各タスク型、すなわちｗi及びｗdと関連付けられる。重みｗiはそのタスクに対する命令の再利用の重要度を反映し、重みｗdはそのタスクに対するデータの再利用の重要度を反映する。ｗdより高いｗiを含むタスクは命令を再利用することからより多くの利益を得、ｗdより低いｗiを含むタスクはデータを再利用することからより多くの利益を得る。重みを比較することにより、考えられる最適なキャッシュの再利用のために、スレッドをタスクに一致させる方法又はタスクをスレッドに一致させる方法を決定することが可能である。例えば、タスクＴに対してｗi＝１０及びｗd＝５である場合、そのタスクＴに対して命令の再利用はデータの再利用より重要である。
【００３２】
これらの重み値は、静的又は動的に設定される。重み値の静的決定は演繹的に行われ、プログラムにおけるタスク型に対する重みの動的決定は、実行時に行われ、コンピューティングシステムの現在の状態を反映するように変化する。例えばより大きなデータセットは、命令の再利用が一般により重要なものとして考えられるタスクに対してデータの再利用の重み値ｗdの増加を保証する。
【００３３】
そのようなスレッド−タスクのペアリングがキャッシュの再利用につながる可能性が高い場合、スレッドは所定のタスクを実行するのに適していると仮定され、タスクは所定のスレッド上で実行されるのに適していると仮定される。
【００３４】
２つ以上のＣＰＵが同一のキャッシュユニットを共有する場合、これらのＣＰＵ上で実行されたスレッドを本明細書において計算グループ（ＣＧ）と呼ぶ。ＣＧにおける全てのスレッドは、対応するＣＰＵにより物理的に共有されたキャッシュへの同等のアクセスを有する。例示的な一実現例は、特に図１０Ａに示されるようにＬ２キャッシュに適用されるものとして説明される。しかし、本明細書において開示された手法は、図１０ＢのＬ３最適化等のあらゆるキャッシュレベルに適用されてよい。
【００３５】
一般に、１つ以上のスレッドがＣＰＵに割り当てられるが、好適な一実現例において、１つのスレッドだけがＣＰＵに割り当てられる。所定のスレッドが常に同一のＣＰＵ上で動作するため、このような割り当てにより、実行中にスレッドの親和性として当技術分野において既知である概念を変更しない。
【００３６】
本発明において開示される構成は、タスクレベルでタスクをスレッドにスケジュールすることで従来技術の主な欠点に対処する。タスクがスレッドに割り当てられる結果、その特定のタスクに対して最も重要な種類のキャッシュされた内容（命令又はデータ）を再利用する。このため、命令及びデータのタスクの潜在的な再利用を示すタスク型が重要である。逆に、従来技術は、多くの場合キャッシュラインの使用を厳密に監視することにより、機械語レベルでキャッシュされた内容を再利用する。従って、従来技術は、本明細書において開示される構成より多くのオーバヘッドをプログラム実行に対して課し、多くの場合専用のハードウェアを更に必要とする。
【００３７】
図１は、本発明において開示される構成が実現されるメモリの少なくとも１つのレベルを含むマルチプロセッサコンピュータシステム１００を示す概略ブロック図である。コンピュータシステム１００は、スタンドアロンコンピュータ、例えばＩＢＭ−ＰＣ及びその互換のコンピュータシステム、Ｓｕｎ社のＳＰＡＲＣ（商標）コンピュータシステム又はＡｐｐｌｅ社のＭａｃ（商標）コンピュータシステム等に類似する近年のデスクトップコンピュータである。あるいはコンピュータシステム１００は、例えばプリンタ、撮像システム又は制御システム等の特殊機能装置を部分的に又は完全に実現する。各処理デバイス又は各チップ上のＣＰＵの数、キャッシュ及びそれらの階層的組織の数、並びに他のコンピュータシステムの構成要素は、広範に変動する。コンピュータシステム１００は、多くの処理装置１５０、メモリ１２０、周辺装置インタフェース１９０、ハードディスクドライブシステム（ＨＤＤ）１９２及び読み出し専用メモリ（ＲＯＭ）１９４を有する。示されるように、それらは全てバス１４０、並びに関連付けられたそれぞれの接続１４１、１４２、１４３、１４４及び１４５を介して相互接続される。周辺装置インタフェース１９０により、コンピュータシステム１００は、オプションの接続１９５を介して通信ネットワークを含む他のシステム、他のコンピュータ、プリンタ及び表示装置等のデバイス、並びにキーボード及びマウスポインティングデバイス（不図示）等の制御デバイスと相互接続できる。処理装置１５０及びメモリ１２０は、バス１４０とは別の専用の接続１４５を有する。図１に示されたようなメモリ１２０は、一般的なコンピュータシステムにおいて使用された種々のメモリの構成要素と種類との混合物を示す。従って、メモリ１２０は、マイクロプロセッサデバイス／マイクロコントローラデバイスに組み込まれたＬ１キャッシュ及びＬ２キャッシュ、そのようなデバイスに直接結合されたＬ３キャッシュ、並びにいわゆる「主」記憶を含む。それらは全て、一般に、専用のランダムアクセスメモリ（ＲＡＭ）デバイスとして処理装置１５０と一体化されない半導体ベースのＲＡＭを使用して実現される。コンピュータシステム１００は、ＨＤＤシステム１９２、ＲＯＭメモリ１２０、並びに光ディスクドライブ、ＰＣＭＣＩＡドライブ及びＵＳＢドライブ等の他のデバイスにより示されている他のメモリを含む。それらは、明確にするために示されず、従来独占的にバス１４０に結合し、処理装置１５０に直接結合しない。
【００３８】
一般的なコンピュータシステムにおいて、ＲＯＭ１９４は、一般に処理装置１５０により実行されるためにＨＤＤ１９２の永久記憶装置からのオペレーティングシステム１２２をメモリ１２０にコピーすることにより、コンピュータ１００のオペレーティングシステム１２２をブートすることを含む基本動作処理をコンピュータ１００が開始及び実行できるようにする基本処理を格納する。オペレーティングシステム１２２は、キャッシュメモリ管理がその一部を形成するメモリ管理等の低レベルの動作機能を含むコンピュータの機能の基本制御を提供する。従って、コンピュータシステム上で実行する（高次レベルの）アプリケーションは、オペレーティングシステムにより与えられたデフォルトメモリ管理機能を利用する。しかし、一般に特定のアプリケーションに最適化された性能又は適した性能を実現するために、低レベルの動作よりも自身の制御の影響を行使することを好む（高次レベルの）アプリケーションもある。そのようなアプリケーションは、高次レベルのアプリケーションにより所望されるようにコンピュータシステム１００の低レベルの動作を変形するように構成された特定のソフトウェアアプリケーションをそのように提供するか、あるいはそれを伴う。
【００３９】
通常、図１に示されるように、一般に制御プログラム１３０は、ＨＤＤ１９２に格納されてＨＤＤ１９２からコピーされ、メモリ１２０に常住する。その結果、制御プログラム１３０は、処理装置１５０のＣＰＵ１７１、１７２、１８１及び１８２と関連付けられたスレッドのうちの１つ以上において実行可能である。本発明において、一般に制御プログラム１３０は、特定の目的のためにコンピュータシステム１００上で実行可能なアプリケーションプログラムであり、キャッシュミス率を低下させるためにコンピュータシステム１００のキャッシュメモリを管理し且つキャッシュの再利用を最適化するように別の手法を実現するために本発明に従って構成されたソフトウェアコンポーネントを含む。そのような実現例において、本発明において説明するキャッシュ管理処理は、オペレーティングシステム１２２内のデフォルト処理として組み込まれる。制御プログラム１３０の特定の目的は、広範に変動するが、レンダリング、ラスタリング及び合成等の画像処理アプリケーション、並びに印刷アプリケーションにより生成された印刷タスクを含む。他のアプリケーションは、特に、ワードプロセシングアプリケーション及びデスクトップパブリッシングアプリケーション、金融アプリケーション、ゲーム、通信、データ処理、モニタリング、制御システムを含む。
【００４０】
図１の例に示されるように、処理装置１５０のＣＰＵ１７１、１７２、１８１及び１８２は、２つの計算グループ（ＣＧ）、すなわちＣＧ１６０及びＣＧ１６５に分けられる。
【００４１】
図２は、図１の処理装置１５０及びメモリ１２０の階層的構成の例示的な構成２００を示す。この特定の構成２００において、ＣＧは、同一のＬ２キャッシュを使用するＣＰＵと関連付けられたスレッドから構成され、Ｌ１キャッシュが一般に同一の半導体デバイス上の対応するＣＰＵで構成される図１０Ａの構成によりミラーリングされる。従って、図２は、２つのＣＧ、すなわち、Ｌ２キャッシュ２１０を共有するＣＰＵ１７１及びＣＰＵ１８１のスレッドに対するＣＧ１６０、並びにＬ２キャッシュ２２０を共有するＣＰＵ１７２及びＣＰＵ１８２のスレッドに対するＣＧ１６５を示す。この構成において、説明される構成の実現例は、Ｌ２キャッシュの最適化を提供する。
【００４２】
図１に示された各ＣＰＵは、ユニファイドキャッシュであるか、あるいは専用のデータキャッシュ及び命令キャッシュの２つの独立した物理ユニットから構成される対応する専用Ｌ１キャッシュを有する。図２は、Ｌ１キャッシュ２３１を有するＣＰＵ１７１、Ｌ１キャッシュ２３２を有するＣＰＵ１８１、Ｌ１キャッシュ２３３を有するＣＰＵ１７２及びＬ１キャッシュ２３４を有するＣＰＵ１８２を示す。
【００４３】
同様に、Ｌ２キャッシュ２１０及びＬ２キャッシュ２２０は、統合されるか、あるいは専用のデータキャッシュ及び命令キャッシュの物理的に独立したハードウェアユニットを有する。本発明において説明する種々の実現例において、Ｌ２キャッシュ２１０及び２２０は、物理的配列に拘らず、各々が１つの論理キャッシュユニットとして見なされる。低位メモリレベル２３０構成要素は、この例示的なハードウェア構成においてＬ３キャッシュ及び主メモリである残りの記憶階層を示す。図２の構成の一般的な実現例において、各Ｌ１キャッシュは、対応するＣＰＵと同一の集積回路チップ上に物理的に配置され、各Ｌ２は、対応するＣＰＵデバイスに直接物理的に接続された専用のキャッシュメモリ素子であり、Ｌ３キャッシュは、コンピュータシステム１００の主半導体ランダムアクセスメモリ（ＲＡＭ）内で物理的に区分された仮想場所のグループである。
【００４４】
図３は、エグゼクティブスレッド３０５構成要素及びワーカースレッド３１０構成要素を含む制御プログラム１３０の一実現例を示す。エグゼクティブスレッド３０５構成要素は、制御プログラム１３０の実行を開始及び監督する。ワーカースレッド３１０構成要素は、複数のスレッド（スレッド０、スレッド１、スレッド２．．．）を含み、エグゼクティブスレッド３０５構成要素により指示されたようにこれらのスレッド上でタスクを実行する。例えば、制御プログラム１３０がレンダリング及び合成等の関連付けられた印刷タスクを有するプリンタドライバである場合、エグゼクティブスレッド３０５は、レンダリング等の特定のタスク、並びに／あるいは縁端の追跡及び合成等のそれらの重要な構成要素を実現するワーカースレッド３１０により実行される実際の印刷処理を実施するキャッシュ管理を含むプリンタドライバの管理動作を示す。
【００４５】
本発明において説明する構成は、全てが特定の計算グループ（ＣＧ）内で実行するように制限される特定のスレッドに特定のタスクを一致させることに基づく。これは、スレッドとタスクとの組合せが各通話に対して同一のキャッシュメモリと実質的に関連付けられることにより、キャッシュミス率を潜在的に減少させることを提供する。
【００４６】
エグゼクティブスレッド３０５は、処理を実行するためにタスクを作成すること及び実行するためにこれらのタスクをワーカースレッド３１０にディスパッチすることを担うタスク生成器及びディスパッチャ３３５を備える。作成の際、タスクは、他の属性のうち、実行される命令の集合を識別する型（ＴＡＳＫ＿ＩＤ）、タスクが処理しているデータを識別するＤＡＴＡＳＥＴ＿ＩＤ及びタスクスケジューリング優先順位を割り当てられる。
【００４７】
処理メッセージ３３０構成要素は、制御プログラム１３０内で渡された全てのメッセージを処理することを担い、スケジューラ３４５は、実行するためにタスクをスケジュールすることを担う。スケジューラ３４５は、詳細に後述される機能であるタスクをスレッドに一致させることを担うタスク−スレッド選択器３４０を有する。
【００４８】
エグゼクティブスレッド３０５は、以下の格納構成要素、すなわちＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５、ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０、ＭＥＳＳＡＧＥＳ３１５及びＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０を更に有する。次に、それらの各々の機能及び内容を順番に説明する。
【００４９】
ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５は、実行するためにディスパッチ可能な状態にある制御プログラム１３０において全てのタスクを含むキューデータ構造である。
【００５０】
ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０は、制御プログラム１３０に割り当てられたスレッドのアイデンティティ（ＩＤ）のリストを格納する。リスト３６０におけるスレッドは、現在アイドル状態である制御プログラム１３０と関連付けられた全てのワーカースレッド３１０のサブセットを示すため、タスクの実行に割り当てられない。このリスト３６０は、実行中のあらゆる所定の時間において制御プログラム１３０に対して使用可能な計算リソースを追跡するために保持される。
【００５１】
ＭＥＳＳＡＧＥＳ３１５記憶装置は、制御プログラム１３０の構成要素間で渡されたメッセージを格納する。各メッセージは、その目的を示すＭＡＴＣＨ＿ＴＨＲＥＡＤ、ＭＡＴＣＨ＿ＴＡＳＫ、ＳＴＡＲＴ＿ＴＡＳＫ及びＴＡＳＫ＿ＦＩＮＩＳＨＥＤ等のタイプを有する。ＭＥＳＳＡＧＥ記憶装置３１５は、ＭＡＴＣＨ＿ＴＨＲＥＡＤ又はＭＡＴＣＨ＿ＴＡＳＫのメッセージタイプである処理メッセージ３３０構成要素からタスク−スレッド選択器３４０に渡されるメッセージを提供する。
【００５２】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０は、ＣＧにおいてスレッドの総合的な実行履歴を追跡する。図４に示されるように、記憶装置３８０は３つの構造を有することが好ましい。構造ＣＧ＿ＴＯ＿ＴＨＲＥＡＤ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４１０は、多くのレコード４２５においてＣＧ ＩＤ及び各ＣＧにおけるスレッドのＩＤを含む。従って、テーブル４１０は、対応するＣＧ、すなわち対応するキャッシュメモリと関連付けられたスレッドのサブセットを示す。レコード４２５は、ＣＧ ＩＤを格納するフィールド４１２、そのＣＧにおけるスレッドの数を格納するフィールド４１４を有し、レコード４１６、４１８及び４２０における残りのフィールドは、スレッドをそのＣＧに格納することを示す。
【００５３】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０における第２の構造は、ＣＧ毎に個々のレコード４４５に記録されるＣＧ毎の実行履歴を格納するＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造である。
【００５４】
各レコード４４５は、対応するＣＧにおいてスレッド上で最後に実行されたタスクのタスクＩＤを含むキューデータ構造であるＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０を有するため、ＣＧのタスク履歴を示す。各レコード４４５は、ＣＧにおいてスレッド上で最後に実行されたタスクのデータセットＩＤを含むキューデータ構造であり、ＣＧのデータ履歴を示すＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５を更に有する。要約すれば、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造は、最後に使用された主記憶領域を識別する情報を格納する。
【００５５】
レコード４４５のフィールド４４２はＣＧ ＩＤを格納する。フィールド４４６、４４８及び４５０は、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０の符号化を示す。フィールド４５４、４５６及び４５８は、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５の符号化を示す。フィールド４４４及び４５２は、それぞれ、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５におけるエントリの数を格納する。総合的にスレッドの実行履歴を示すこれらのキューの深度は、最適化されるために使用されるキャッシュのサイズ及び制御プログラム１３０におけるタスクの特徴の双方に依存する。制御プログラム１３０におけるタスクの特徴の例は、タスクの平均コードサイズ及びタスクのコードにおいて最も頻繁に実行された命令の平均サイズである。制御プログラム１３０におけるタスクの特徴、例えばタスクのコードサイズは、キューの深度を事前に決定するため又は制御プログラム１３０の実行中にキュー深度を変更するために使用される。従って、一実現例において、実行履歴は、スレッドにより実行されたタスクと関連付けられた最も一般的に実行された命令のコードサイズに依存するサイズを有する。別の実現例において、実行履歴は、スレッドにより実行されたタスクにより使用されたデータのサイズに依存するサイズを有する。そのキュー深度値は、キュー及び／又はＣＧ毎に異なり、制御プログラム１３０を開始する前に設定されるかあるいは制御プログラム１３０の実行中に動的に変動される。ＣＧ＿ＴＯ＿ＴＨＲＥＡＤ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４１０構造及びＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造の双方は、ＣＧ毎に１つのレコードを含む。
【００５６】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０における第３の構造は、スレッドに対応するレコード４８５において、フィールド４８２におけるスレッドＩＤからフィールド４８４においてスレッドが属するＣＧにルックアップテーブルを格納するＴＨＲＥＡＤ＿ＴＯ＿ＣＧ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４８０構造である。構造４８０は、制御プログラム１３０のワーカースレッド３１０構成要素におけるスレッドの数であるＮ個のレコードを含む。構造４８０は、上述のテーブル４１０の基本的な態様を補完する。
【００５７】
スケジューラ３４５構成要素は、実行するためにタスクをスレッド上でスケジュールすることを担い、メッセージチャネル３９０を介してタスク生成器及びディスパッチャ３３５から生成されたタスクの規格を受信する。スケジューラ３４５は、採用されたスケジューリングアルゴリズムにより決定された順番でＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５を保持する。当技術分野において既知であるあらゆる適切なスケジューリングアルゴリズムは、スケジューラ３４５により採用される。好適な実現例によれば、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５におけるタスクは、降順のタスク優先順位で保持される。すなわち、高優先度タスクはキューの前方にあり、低優先度タスクはキューの後方にある。タスク優先順位は、タスク作成の際に割り当てられ、実行中に後で前後する。タスク−スレッド選択器３４０構成要素は、実行可能な状態にあるタスクをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０からのスレッドと一致させる。次に、図５を参照してタスク−スレッド選択器３４０の機能性を詳細に説明する。
【００５８】
図５は、それぞれ、所定のタスクが使用可能なスレッドと一致されるか又は所定のスレッドがタスクを実行可能な状態にあるかを決定するスケジューラ３４５により実行された処理５００を示す。最初に、ＭＥＳＳＡＧＥ３１５は、ディスパッチャ３３５からスケジューラ３４５に渡される。ＭＡＴＣＨ＿ＴＨＲＥＡＤタイプ又はＭＡＴＣＨ＿ＴＡＳＫタイプのみがディスパッチャ３３５の処理メッセージ３３０構成要素からスケジューラ３４５のタスク−スレッド選択器３４０構成要素に渡されるため、ＭＥＳＳＡＧＥ３１５はこれらの２つのメッセージタイプのいずれかである。ＭＥＳＳＡＧＥ３１５は、メッセージタイプ及び一致されなければならないスレッド又はタスクを含む。例えば、（ＭＡＴＣＨ＿ＴＨＲＥＡＤ、「０」）は、ＩＤ「０」を含むスレッドを実行可能な状態にある適切なタスクと一致させるメッセージ要求である。例えば、メッセージ要求（ＭＡＴＣＨ＿ＴＡＳＫ、［ＤＬ、７］）は、要求により示された型「ＤＬ」により規定されたタスク及びスレッドにより処理されるデータセット「７」を実行するのに適したスレッドを見つける要求である。
【００５９】
スケジューラ３４５は、判断ステップ５０５において、ＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプであるかを決定する。ＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプである場合、処理５００はステップ５１０を介して進み、ＭＥＳＳＡＧＥ３１５において渡されたスレッド上で実行するのに適したタスクを決定する。ＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプではない場合、すなわちＭＡＴＣＨ＿ＴＡＳＫタイプである場合、処理は、ＭＥＳＳＡＧＥ３１５において渡されたタスクを実行するのに適したスレッドを選択することにより、ステップ５２０を介して継続する。次に、これらの２つの例を順番に説明する。
【００６０】
スケジューラ３４５は、判断ステップ５０５においてＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプであると決定する場合、判断ステップ５１０に進む。ステップ５１０において、スケジューラ３４５は、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５が空であるかをチェックする。ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５が空である場合、スケジューラ３４５は、処理ステップ５１５に進み、ブールパラメータＭＡＴＣＨＥＤを「偽」に設定する。次にスケジューラ３４５は、ステップ５５５において、図３に示されるようにタスク又はスレッドの選択を要求したＭＥＳＳＡＧＥ３１５への応答としてエグゼクティブスレッド３０５の処理メッセージ３３０構成要素に送出されるメッセージＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５を作成する。
【００６１】
ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５は、ＭＥＳＳＡＧＥの値及び対（ＴＨＲＥＡＤ、ＴＡＳＫ）を含む。ステップ５１５が生じる場合、一致が不可能であるため、所定のＴＨＲＥＡＤに対するＴＡＳＫの値は、ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５においてヌルに設定される。処理５００はステップ５５５で終了する。
【００６２】
ステップ５１０においてテストされるようなＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５において少なくとも１つのタスクがある場合、ＴＨＲＥＡＤは、ステップ５２５においてＭＥＳＳＡＧＥ３１５から取り出される。次に、ＴＨＲＥＡＤ上で実行するためのタスクは、図６を参照して詳細に後述される処理５３５において選択される。処理はステップ５４５に進む。
【００６３】
ステップ５０５においてＭＥＳＳＡＧＥ３１５がＭＡＴＣＨ＿ＴＨＲＥＡＤタイプではないと処理装置１５０におけるスレッド３０５のスケジューラ３４５が決定する場合、処理５００は、ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０が空であるかをスケジューラ３４５がチェックする判断ステップ５２０に継続する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０が空である場合、ブールパラメータＭＡＴＣＨＥＤは、ステップ５１５において「偽」に設定される。次にスケジューラ３４５は、ステップ５５５においてメッセージＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５を作成する。ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５は、タスク又はスレッドの選択を要求したＭＥＳＳＡＧＥ３１５への応答として処理メッセージ３３０構成要素に送出される。この場合、再度、一致が不可能であるため、所定のＴＡＳＫに対するＴＨＲＥＡＤの値はＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥ３２５においてヌルに設定され、処理５００はステップ５５５で終了する。
【００６４】
ステップ５２０に戻り、少なくとも１つの使用可能なスレッドがある場合、処理は、ステップ５３０においてＭＥＳＳＡＧＥ３１５からＴＡＳＫを取り出すことを継続する。次にスケジューラ３４５は、図７Ａ〜図７Ｃを参照して詳細に後述されるように、ＴＡＳＫを実行するためのスレッドを選択する処理５４０を実行する。
【００６５】
それぞれメッセージタイプＭＡＴＣＨ＿ＴＨＲＥＡＤ及びＭＡＴＣＨ＿ＴＡＳＫに対して実行された処理５３５及び５４０の双方は、常に結果として対（ＴＨＲＥＡＤ、ＴＡＳＫ）を取得する。従って、後続のステップ５４５において、ブールパラメータＭＡＴＣＨＥＤは「真」に設定され、次にステップ５５０において、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０は、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造においてＴＨＲＥＡＤのＣＧに対するＴＡＳＫのＴＡＳＫ＿ＩＤ及びＤＡＴＡＳＥＴ＿ＩＤを実行履歴キュー４９０及び４９５に追加することで更新される。ＴＡＳＫのＴＡＳＫ＿ＩＤ及びＤＡＴＡＳＥＴ＿ＩＤは、それぞれキュー４９０及び４９５の前方に追加され、他の全てのエントリは、各キューの最後のエントリ（最も古い）が削除された状態でキューの末尾へ移行される。
【００６６】
処理５００は、ＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥがブールパラメータＭＡＴＣＨＥＤの値（ステップ５４５から後続する場合に値「真」を有する）及び対（ＴＨＲＥＡＤ、ＴＡＳＫ）で作成されるステップ５５５で終了する。
【００６７】
図６は、所定のスレッド、すなわちＴＨＲＥＡＤ６０５上で実行するためにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からタスクを選択する処理５３５を示す。処理５３５は、スケジューラ３４５がＴＨＲＥＡＤ６０５のＣＧの履歴を取得するステップ６１０から開始する。これは、ＴＨＲＥＡＤ＿ＴＯ＿ＣＧ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４８０からＴＨＲＥＡＤ６０５に対するレコードにアクセスし、ＴＨＲＥＡＤ６０５が属するＣＧＩＤを特定するフィールド４８４を取得することで実現される。次に、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造から、そのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０から読み出されたタスク履歴及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５から読み出されたデータ履歴を含む実行履歴は、ステップ６１０でアクセスされる。取得ステップ６１５において、スケジューラ３４５は、ＴＨＲＥＡＤ６０５上で実行するのに適したタスクが見つけられるまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてエントリを繰り返す処理を開始する。ステップ６１５において、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の先頭から開始し、タスクＴは、タスク生成器及びディスパッチャ３３５により取得される。ステップ６１７において、タスクＴに対して命令の集合の重み付けｗi及びデータの集合の重み付けｗdを決定する。重み付けは、タスクに対する命令の再利用又はデータの再利用の重要度を決定する。この重みは種々の方法で決定される。種々の方法のうちの１つは、メモリ１２０に格納された制御プログラム１３０において全てのタスク型に対するｗi及びｗdの所定の値のルックアップテーブルを使用することであるが、それに限定されない。次にスケジューラ３４５は、判断ステップ６２０においてｗiがｗdより大きいかをチェックする。ｗiがｗdより大きい場合、タスクＴに対して命令の再利用はデータの再利用より重要であり、処理５３５は、ＴＡＳＫのＴＡＳＫ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にあるかをチェックする判断ステップ６２５に継続する。ＴＡＳＫのＴＡＳＫ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にある場合、タスクＴは適している。ステップ６４５において、スケジューラ３４５はＴＡＳＫをＴに設定し、処理５３５が終了する。
【００６８】
ステップ６２０においてｗiがｗdより大きくないと決定する場合、タスクＴに対して命令の再利用はデータの再利用と同様に重要ではなく、タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５にあるかをチェックするステップ６３０に後続する。タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧのＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられる場合、タスクＴは適切なタスクであり、スケジューラ３４５がＴＡＳＫをＴに設定するステップ６４５に後続し、処理５３５が終了する。
【００６９】
図６においてＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からタスクＴを取得し、且つタスクＴのＴＡＳＫ＿ＩＤ又はＤＡＴＡＳＥＴ＿ＩＤがＴＨＲＥＡＤ６０５のＣＧに対する実行履歴にあるかをチェックする処理は、ステップ６３５においてテストされたように、ＴＡＳＫ＿ＩＤ（ステップ６２５）又はＤＡＴＡＳＥＴ＿ＩＤ（ステップ６３０）を一致させるタスクが見つけられるまで、あるいはキューの後方に到達するまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてタスク毎に繰り返される。
【００７０】
ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてこれ以上タスクがない場合、ステップ６１５及び６３５により形成された処理ループは、ＴＡＳＫをＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５における最初のタスクに設定するステップ６４０に進む。キューの先頭のタスクは最も優先度の高いタスクであり、キャッシュ内容の再利用を実現できない場合、キューの先頭のタスクは実行するためにディスパッチされる。ステップ６４０の後、処理５３５は終了する。
【００７１】
図７Ａは、所定のタスク、すなわちＴＡＳＫ７１５を実行するためにスレッドを選択する処理５４０を示す。処理５４０は、ＣＧ ＩＤのリスト（ＣＧ＿ＩＤ）が実行履歴４４０から作成されることでＣＧを形成するスレッドのサブセットの実行履歴を示すステップ７０５から開始する。ＣＧ＿ＬＩＳＴにおける各エントリは、少なくとも１つの使用可能なスレッドを有する。ＣＧ＿ＬＩＳＴを繰り返す繰返し子は、ステップ７０５において更に設定される。ステップ７１０において、スケジューラ３４５は、ＴＡＳＫ７１５に対して命令の集合の重み付けｗi及びデータの集合の重み付けｗdを決定する。これは種々の方法で決定される。種々の方法のうちの１つは、制御プログラム１３０において全てのタスク型に対するｗi及びｗdの所定の値のルックアップテーブルを使用することであるが、それに限定されない。判断ステップ７２０は、ｗiがｗdより大きいかをチェックする。ｗiがｗdより大きい場合、図７Ｃを参照して詳細に後述するように、ＴＡＳＫ７１５に対して命令の再利用はデータの再利用より重要であり、処理は処理７３０に継続する。
【００７２】
次に図７Ｂを参照して詳細に説明されるように、スケジューラ３４５がステップ７２０においてｗiがｗdより大きくないと決定する場合、ＴＡＳＫ７１５に対して命令の再利用はデータの再利用と同様に重要でないため、処理は処理７２５に継続する。
【００７３】
図７Ｂ及び図７Ｃに示されたステップ７２５及び７３０の処理は、スレッドの実行履歴、並びにタスクと関連付けられた命令及びデータに対して決定された重み付け（ｗi、ｗd）に基づいてＴＡＳＫ７１５を実行するのに適した全てのアイドル（使用可能な）スレッドのサブセットから特定のスレッドを選択する。
【００７４】
図７Ｂは、ＴＡＳＫ７１５に対してデータの再利用が命令の再利用より重要である場合にＴＡＳＫ７１５を実行するのに適したスレッドを選択する処理７２５を示す。従って、処理７２５は、ＴＡＳＫ７１５と関連付けられたデータ履歴に依存し、双方がステップ７０５において前に作成された繰返し子を使用してスケジューラ３４５がＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得するステップ７５０から開始する。次にスケジューラ３４５は、ステップ７５２においてそのＣＧに対するデータ履歴を取得する。これは、そのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５にアクセスするためにＣＧ ＩＤを使用することで実現される。
【００７５】
処理７２５は、ＴＡＳＫ７１５と関連付けられたＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるかをスケジューラ３４５が決定する判断ステップ７５４に継続する。ＴＡＳＫ７１５と関連付けられたＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられる場合、次にステップ７６６において、ＴＡＳＫ７１５を実行するために使用されるＣＧから使用可能なスレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。
【００７６】
ＴＡＳＫ７１５に割り当てられたＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられなかったことがステップ７５４において決定された場合、処理は判断ステップ７５６に進む。ステップ７５６において、データ履歴がまだチェックされていないＣＧ＿ＬＩＳＴにより多くのＣＧがあるかを決定する。ＣＧ＿ＬＩＳＴにより多くのＣＧがある場合、ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるまで又はＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７５０、７５２及び７５４は繰り返される。
【００７７】
ステップ７５６において決定されたようにチェックすべきエントリがこれ以上ＣＧ＿ＬＩＳＴに残っていない場合、処理７２５は、現在使用可能なあらゆるスレッド上でＴＡＳＫ７１５に対してデータの再利用を実現できないため、ＣＧ＿ＬＩＳＴ繰返し子を再設定することでＣＧ＿ＬＩＳＴの繰り返しが最初から開始されるステップ７５８に進む。ＣＧ＿ＬＩＳＴのＣＧ ＩＤのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０におけるエントリは、命令の再利用を実現することを考慮してＴＡＳＫ７１５のＴＡＳＫ＿ＩＤに対してチェックされる。
【００７８】
ステップ７６０において、スケジューラ３４５はＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得する。ステップ７６１において、スケジューラ３４５は、そのグループのスレッドが実行した命令の集合に関するそのＣＧのタスク履歴を取得する。これは、そのＣＧに対するＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造においてＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にアクセスすることで実現される。
【００７９】
判断ステップ７６２において、スケジューラ３４５は、ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられるかをチェックする。ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられる場合を条件として、スケジューラ３４５は、ステップ７６６においてＴＡＳＫ７１５を実行するために使用されるＣＧに割り当てられたワーカースレッド３１０から使用可能なワーカースレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。
【００８０】
ステップ７６２においてＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられない場合、ＴＡＳＫ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられるまで又は判断ステップ７６４において決定されたようにＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７６４、７６０、７６１及び７６２は繰り返される。チェックすべきエントリがこれ以上残っていない場合、ＴＨＲＥＡＤは、ステップ７６８においてＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０で示されたサブセットにより識別されたワーカースレッド３１０からのあらゆるアイドルワーカースレッドに設定される。アイドルスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。処理７２５は、ステップ７６８で終了し、ＴＡＳＫ７１５に対してデータの再利用が命令の再利用より重要である場合にＴＡＳＫ７１５を処理するのに適したスレッドをリスト３６０のサブセットから選択することを実証する。上述したように、スレッドのサブセットの選択は、スレッドの実行履歴及びタスクと関連付けられた命令の再利用又はデータの再利用に対して決定された重み付けに基づく。
【００８１】
図７Ｃは、ＴＡＳＫ７１５に対して命令の再利用が重要である場合に図７Ａにおいて示されたようにＴＡＳＫ７１５を実行するのに適したスレッドを選択する処理７３０を示す。従って、処理７３０は、ＴＡＳＫ７１５と関連付けられた命令履歴に依存し、ステップ７０５において作成されたＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得するステップ７７０から開始する。ステップ７７２において、そのグループのスレッドが最近実行した命令に関するそのＣＧに対する履歴を取得する。これは、そのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０にアクセスするためにＣＧ ＩＤを使用することにより実現される。
【００８２】
処理７３０は、ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥにおいて見つけられるかをスケジューラ３４５が決定する判断ステップ７７４に継続する。ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥにおいて見つけられる場合、スケジューラ３４５は、ステップ７８６においてＴＡＳＫ７１５を実行するために使用されるＣＧに割り当てられたワーカースレッド３１０から使用可能なワーカースレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。
【００８３】
ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがそのＣＧのＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられない場合、処理は、命令履歴がまだチェックされていないＣＧ＿ＬＩＳＴにより多くのＣＧがあるかをスケジューラ３４５が決定する判断ステップ７７６に到達する。ＣＧ＿ＬＩＳＴにより多くのＣＧがある場合、ＴＡＳＫ７１５のＴＡＳＫ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０において見つけられるまで又はＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７７０、７７２及び７７４は繰り返される。
【００８４】
チェックすべきエントリがこれ以上ＣＧ＿ＬＩＳＴにない場合（判断ステップ７７６）、処理は、現在使用可能なあらゆるスレッド上でＴＡＳＫ７１５に対して命令の再利用を実現できないため、データを再利用しようとすることでＣＧ＿ＬＩＳＴの繰り返しが最初から開始されるステップ７７８に進む。再利用を実現するために、ＣＧ＿ＬＩＳＴにおけるＣＧのＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５は、ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤに対してチェックされる。ステップ７８０において、ＣＧ＿ＬＩＳＴからＣＧ ＩＤを取得する。
【００８５】
ステップ７８１において、スケジューラ３４５はそのＣＧに対するデータ履歴を取得する。これは、データ実行履歴が格納されるＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５にアクセスするためにＣＧ ＩＤを使用することで実現される。
【００８６】
判断ステップ７８２において、スケジューラ３４５は、ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるかをチェックする。ＴＡＳＫ７１５のＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられる場合、スケジューラ３４５は、ステップ７８６においてＴＡＳＫ７１５を実行するために使用される計算グループＣＧから使用可能なワーカースレッドを選択する。現在アイドル状態であるあらゆるスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。処理７３０はステップ７８６で終了する。
【００８７】
ＤＡＴＡＳＥＴ＿ＩＤがそのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられない場合、ＤＡＴＡＳＥＴ＿ＩＤがＣＧ＿ＬＩＳＴのＣＧに対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５において見つけられるまで又は判断ステップ７８４により決定されたようにＣＧ＿ＬＩＳＴにおいてチェックすべきエントリがなくなるまでステップ７８４、７８０、７８１及び７８２は繰り返される。チェックすべきエントリがこれ以上残っていない場合、ＴＨＲＥＡＤは、ステップ７８８においてＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０からのあらゆるスレッドに設定され、処理７３０は終了する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０からのアイドルスレッドは、当技術分野において既知であるあらゆる負荷分散アルゴリズムを適用することを含むがそれに限定されない手段により選択される。処理７３０は、ＴＡＳＫ７１５に対して命令の再利用が重要である場合にＴＡＳＫ７１５を処理するのに適したスレッドをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０から選択することを更に実証する。同様に、ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０におけるスレッドのサブセットの選択は、スレッドの実行履歴及びタスクと関連付けられた命令の再利用又はデータの再利用に対して決定された重み付けに基づく。
【００８８】
本発明において説明する処理構成は、同一の計算グループのＣＰＵ上で実行されたタスク間でキャッシュ内容を最大限再利用するためにスレッドをタスクに適切に一致させるようにメモリ１２０に格納された制御プログラム１３０により作成及び実行されたタスクの特徴の知識を使用する。行われなければならない判断の簡潔性及び保持された限られた実行履歴により、タスク−スレッド選択器３４０が招くオーバヘッドを最小限にできる。
【００８９】
次に、図４の構造に類似する構造を示す図８を参照して３つの例を説明する。印刷システムにおいて使用されたラスタイメージプロセッサ（ＲＩＰ）アプリケーションプログラムは、以下の例を説明するために使用される。ＲＩＰアプリケーションプログラムは、制御プログラム１３０の一部を形成する。一般にＲＩＰは、ページの高レベルな記述を印刷記述言語（ＰＤＬ）からラスタ表現に変換する必要がある。ページの高レベルＰＤＬ記述は、テキスト、ライン、フィル領域及び画像データ等のグラフィックオブジェクト、並びにこれらのグラフィックオブジェクトがラスタ表現にレンダリングされる順番を含む。この順番は、一般にｚオーダーとして当技術分野において既知である。ページのラスタ表現は色画素データから構成される。次にプリンタエンジンは、一般に、ページのラスタ表現を用紙等の印刷媒体上に印刷する。ラスタ表現を生成する前、ＲＩＰは、ページの中間ページ表現を生成する。ページの中間ページ表現は、一般にラスタ表現より小型であるが、迅速かつ容易にラスタ表現に変換される。
【００９０】
次に、図１１Ａ〜図１１Ｄを参照して、「フィルマップ」として既知である中間ページ表現の一例を説明する。図１１Ａはページ表現１１００を示す。ページ１１００は、白色の背景を有し、２つのグラフィックオブジェクト１１０１及び１１０２を含む。第１のグラフィックオブジェクト１１０１は、灰色の平坦なフィルを含む不透明な「Ｔ」形のオブジェクトである。第２のグラフィックオブジェクト１１０２は、陰影をつけられたフィルを含む透明な正方形である。他のフィルの例は、直線的に変動する色を表す混合、ビットマップ画像又はタイル型の（すなわち、繰り返された）画像である。第２のグラフィックオブジェクト１１０２は、部分的に第１のグラフィックオブジェクト１１０１に重複する。
【００９１】
図１１Ｂは、画素格子１１２０に従ってページ１１００のグラフィックオブジェクト１１０１及び１１０２を画素整列ラフィックオブジェクトの縁端、レベル、並びにフィルに分解することを示す。グラフィックオブジェクトは、２つ以上の画素整列オブジェクトの縁端、単一のレベル及び１つ以上のフィルに分解される。画素整列グラフィックオブジェクトの縁端は、ラスタ化中のレベルの起動又は停止を規定する。従って、画素整列グラフィックオブジェクトの縁端は、それらが導出されるオブジェクトのレベルを示す。第１のグラフィックオブジェクト１１０１は、２つの画素整列グラフィックオブジェクトの縁端１１２１及び１１２２、並びに灰色の平坦なフィルから構成されるレベル１１３２に分解される。画素整列グラフィックオブジェクトの縁端１１２１及び１１２２は、第１のグラフィックオブジェクト１１０１のレベル１１３２を示す。第２のグラフィックオブジェクト１１０２は、２つの画素整列グラフィックオブジェクトの縁端１１２３及び１１２４、並びに透明な陰影をつけられたフィルから構成されるレベル１１３３に分解される。画素整列グラフィックオブジェクトの縁端１１２３及び１１２４は、第２のグラフィックオブジェクト１１０２のレベル１１３３を示す。背景１１２５は、白色のフィルから構成されるレベル１１３１を有する。
【００９２】
図１１Ｃは、図１１Ａに示されたページ１１００のフィルマップ表現１１４０を示す。フィルマップ表現１１４０は、５つの画素整列フィルマップの縁端から構成される。画素整列フィルマップの縁端の各々は、その画素整列フィルマップの縁端により起動された各画素の色を決定するために使用されるフィルシーケンスを示す。画素整列フィルマップの縁端がアクティブである所定のあらゆる走査線上において、画素整列フィルマップの縁端は、次の画素整列フィルマップの縁端又はページ境界に遭遇するまで画素整列フィルマップの縁端のすぐ右にある画素を起動する。第１の画素整列フィルマップの縁端１１４１は、ページの左手の境界を追跡し、背景フィルを使用して充填される単一の不透明なレベルを含むフィルシーケンス１１５１を示す。第２の画素整列フィルマップの縁端１１４２は、第１のグラフィックオブジェクト１１０１の左手の境界を追跡し、不透明であり且つ灰色の平坦なフィルを使用して充填される単一のレベルを含むフィルシーケンス１１５２を示す。第３の画素整列フィルマップの縁端１１４３は、第１の画素整列フィルマップの縁端１１４１と同一のフィルシーケンス１１５１を示す。第４の画素整列フィルマップの縁端１１４４は、第２のオブジェクト１１０２が白色の背景に重複する領域の左手の境界を追跡する。第４の画素整列フィルマップの縁端１１４４は、２つのレベルを含むフィルシーケンス１１５４を示す。一番上のレベルは、透明であり、陰影をつけられたフィルを使用して充填される。一番下のレベルは、不透明であり、背景フィルを使用して充填される。第５の画素整列フィルマップの縁端１４５は、第２のグラフィックオブジェクト１１０２が第１のグラフィックオブジェクト１１０１に重複する領域の左手の境界を追跡する。第５の画素整列フィルマップの縁端１１４５は、２つのレベルを含むフィルシーケンス１１５３を示す。一番上のレベルは、透明であり、陰影をつけられたフィルを使用して充填される。一番下のレベルは、不透明であり、灰色の平坦なフィルを使用して充填される。
【００９３】
ページのフィルマップ表現１１４０に含まれた画素整列フィルマップの縁端により示されたフィルシーケンス１１５１、１１５２、１１５３及び１１５４を含むフィルシーケンスのテーブルは、ページのフィルマップ表現１１４０を伴う。
【００９４】
図１１Ｄは、図１１Ａに示されたページのタイル型のフィルマップ表現１１６０を示す。タイル型のフィルマップは、４つのタイル１１６５、１１７０、１１７５及び１１８０を含む。各タイルは、８個の画素の高さ及び幅を有する。ページのタイル型のフィルマップ表現１１６０を生成するために、元のフィルマップ表現１１４０の画素整列フィルマップの縁端は、フィルマップタイル境界にわたり分裂されている。例えば、図１１Ｃに示された非タイル型のフィルマップ表現１１４０においてページの左手の境界を追跡する画素整列フィルマップの縁端１１４１は、２つの画素整列フィルマップの縁端１１６６及び１１７６に分割されている。第１の画素整列フィルマップの縁端１１６６は、左上のタイル１１６５の画素を起動し、第２の画素整列フィルマップの縁端１１７６は、左下のタイル１１７５の画素を起動する。また、新しい画素整列フィルマップの縁端は、画素が常駐するタイルの左に対してタイルにおいて画素整列フィルマップの縁端により前に起動された各タイルの最も左の画素を起動するようにタイル境界上に挿入されている。例えば、右上のタイル１１７０において、新しい画素整列フィルマップの縁端１１７１は、図１１Ｃに示された元のフィルマップ表現１１４０において第１のグラフィックオブジェクト１１０１の左手の境界を追跡する画素整列フィルマップの縁端１１４２により起動された画素を起動するように挿入されている。
【００９５】
以下の例を説明するために使用されたＲＩＰアプリケーションは、４つの型のタスク、すなわち表示リスト生成（ＤＬ）、フィルマップ生成（ＦＧ）、フィルマップマージング（ＦＭ）及びフィルマップレンダリング（ＦＲ）から構成される。ＤＬタスクは、ＰＤＬ文書からｚオーダーのグラフィックオブジェクトのシーケンスを読み出し、表示リストを作成する。一般に表示リストは、グラフィックオブジェクトのｙソートリストから構成され、一般に当技術分野において既知である。印刷される所定のページに対して、いくつかのＤＬタスクは、ｚオーダーのグラフィックオブジェクトの種々のシーケンスを処理する必要がある。各シーケンスはｚ帯として既知であり、そのようなシーケンスに対してＤＬタスクにより生成された表示リストは、ｚ帯表示リストとして既知である。ｚ帯表示リスト毎に、ＦＧタスクは、ｚ帯フィルマップとして既知であるフィルマップ表現を生成する。図１１Ａ〜図１１Ｄを参照してフィルマップ表現を上述した。ＦＭタスクは、２つ以上のｚ帯フィルマップを受信し、それらを単一のフィルマップにマージする。より多くのｚ帯フィルマップがページに対して残っている場合、更なるＦＭタスクは、ｚ帯フィルマップをマージする必要がある。マージすべきｚ帯フィルマップがこれ以上残っていない場合、ＦＭタスクにより生成されたフィルマップは、ページ上に全てのグラフィックオブジェクトを示す。次にＦＲタスクは、フィルマップを印刷可能な状態にあるラスタ表現に変換するために使用される。
【００９６】
図８は、制御プログラム１３０の実行中の所定の時間におけるＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０の状態８００を示す。図８に示された例において、第１の構造８２０に示されたようにＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０のＣＧ＿ＴＯ＿ＴＨＲＥＡＤ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥの例を示す２つのＣＧ、すなわちＣＧ０（８２１）及びＣＧ１（８２２）がある。ＣＧ０８２１は２つのスレッド（フィールド８２３に示されたような）を含み、ＣＧ１は２つのスレッド（フィールド８２４に示されたような）を更に含む。フィールド８２５及び８２６にそれぞれ示されるように、ＣＧ０は、スレッド「０」及びスレッド「１」を含む。フィールド８２７及び８２８にそれぞれ示されるように、ＣＧ１は、スレッド「２」及びスレッド「３」を含む。
【００９７】
ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０の第２の構造８４０は、ＣＧ０及びＣＧ１のＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹテーブルの例を含む。ＣＧ０（８２１）に対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０は、フィールド８４２〜８４４に示された３つのエントリ（フィールド８４１において特定されたような）を有する。ＣＧ０（８２１）のＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１は、フィールド８４６〜８４８に示された３つのエントリ（フィールド８４５において特定されたような）を有する。ＣＧ１（８２２）に対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６２は、フィールド８５２〜８５４に示された３つのエントリ（フィールド８５１において特定されたような）を有する。ＣＧ１（８２２）に対するＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６３は、フィールド８５６〜８５８に示された３つのエントリ（フィールド８５５において特定されたような）を有する。
【００９８】
図４を参照して上述したように、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥは、各計算グループ上で実行されたタスク型の履歴を含む。従って、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０及び８６２は、ＲＩＰアプリケーションの例において４つのタスク型に対応するＤＬ、ＦＧ、ＦＭ又はＦＲ（ＦＲはこの例において示されない）である値を含む。これらの値は、潜在的に将来のタスクにより再利用されるキャッシュされた命令を示す。同様に、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥは、各計算グループ上で実行されたタスクにより使用されたデータの履歴を含む。ＲＩＰアプリケーションの例において、所定のタスクに対して処理されているページの数は、処理されているデータを示す。従って、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１及び８６３はページ数を含む。ページの数は、潜在的に将来のタスクにより再利用されるキャッシュされたデータを示す。
【００９９】
後続の例において、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０の一部を形成する重み行列８９０は、所定のタスクを処理する場合に命令及びデータの相対的な重要度を決定するために使用される。命令及びデータの相対的な重要度は、所定のタスクを実行するのに適したスレッド又は所定のスレッド上で実行されるのに適したタスクを選択するために使用される。以下の例において使用された重みを図８の重み行列８９０において示す。実行される４つの型のタスク、すなわちＤＬ（８９１）、ＦＧ（８９２）、ＦＭ（８９３）及びＦＲ（８９４）があり、ｗi及びｗdの値は、重み行列８９０においてタスク型毎に与えられたタスクに依存することが好ましい。重み行列８９０における重みは、制御プログラム１３０の前の実行において取得された履歴データを解析すること及びプログラムコードの複雑性の解析等の種々の方法で決定される。換言すると、重み付けは、スレッドのサブセットの実行履歴に基づいて決定される。別の実現例において、重み付けは、タスクの知識に基づいて事前に決定され、メモリ１２０のルックアップテーブルに格納される。
【０１００】
ＲＩＰアプリケーションの例において、ＤＬ（表示リスト生成）タスクは、命令の適切に規定されたシーケンスを実行し、各ＤＬタスクは、グラフィックオブジェクトの別個のシーケンスを処理する。従って、ＤＬタスクの場合、ｗiはｗdより高い値を与えられる。データの別個のｚ帯を更に処理するＦＧ（フィルマップ生成）タスクに対して、同一の推論が適用可能である。また、ＲＩＰアプリケーションの例において、ＦＧタスクは、通常ＤＬタスクに対して別個のスレッド上で実行されるため、ＤＬタスクにより生成された表示リストデータを利用できないことが多い。従って、ＦＧタスクの場合、ｗiはｗdより高い値を更に与えられる。ＦＭ（フィルマップマージング）タスクは、多数のＦＧタスクにより生成されたフィルマップデータを受信する。このフィルマップデータが大量のメモリを消費するため、可能な場合は常にキャッシュに格納されたフィルマップデータを再利用することが有益である。従って、ＦＭタスクの場合、ｗdはｗiより高い値を与えられる。各ＦＲ（フィルマップレンダリング）タスクは、印刷されている別個のページからのフィルマップを処理する。従って、ＦＲタスク間でのデータの再利用の機会は殆どない。従って、ＦＲタスクの場合、ｗiはｗdより高い値を与えられる。命令の再利用及びデータの再利用に対してタスク及びそれらの挙動のこのような知識を有することは、重み付けがタスク型に基づくことを意味する。
【０１０１】
例１
次に、所定のスレッドに対してタスクを選択する一例を説明する。タスク［ＤＬ、６］を処理した後にスレッド「０」が使用可能になったと仮定する。タスク［ＦＭ、２］は、降順の優先順位で配置されて実行可能な状態にある他のタスクが後続したＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の先頭にある。ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の状態は以下の通りである。
［ＦＭ、２］［ＤＬ、７］［ＤＬ、８］［ＦＧ、３］［ＦＧ、４］［ＦＧ、５］
【０１０２】
図３を参照して上述したように、ＭＥＳＳＡＧＥ３１５はタスク−スレッド選択器３４０に送出される。例１において、ＭＥＳＳＡＧＥ３１５は、ＭＡＴＣＨ＿ＴＨＲＥＡＤタイプであり、スレッドＩＤ「０」（８２５）を含む。従って、図６を参照して上述した処理５３５が実行されることにより、スレッド「０」上で実行するのに適したタスクをＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５から選択する。スレッド「０」のＣＧがＣＧ０（８２１）であるため、ＣＧ０の実行履歴は、スレッド「０」上で実行すべきタスクを決定するために使用される。
【０１０３】
スケジューラ３４５は、処理５３５において、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からこの例においてはタスク［ＦＭ、２］である第１のタスクを選択する。タスクのＦＭ型であるため、重み行列８９０に従って、タスク［ＦＭ、２］は、ｗi＝５及びｗd＝１０を有する。これは、タスク［ＦＭ、２］に対してデータの再利用が命令の再利用より重要であることを意味する。
【０１０４】
従って、処理５３５は、ＤＡＴＡＳＥＴ＿ＩＤ＝２がステップ６３０においてＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１にあるかを決定する。ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１は、ＤＡＴＡＳＥＴ＿ＩＤ＝２を含まない。従って、処理５３５は、例１においてはタスク［ＤＬ、７］であるＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５において次のタスクに進む。
【０１０５】
タスク［ＤＬ、７］は、ＤＬ型であり、重み行列８９０に従ってｗi＝１０及びｗd＝５を有する。これは、ＤＬタスク型に対して命令の再利用より重要であることを意味する。従って、処理５３５は、ステップ６２５においてＴＡＳＫ＿ＩＤ＝ＤＬがスレッド「０」のＣＧ０のＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０にあるかを決定する。スレッド「０」ＣＧ０のＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０は、ＴＡＳＫ＿ＩＤ＝ＤＬを含む。従って、処理５３５は、タスク［ＤＬ、７］がスレッド「０」により実行されるのに適していると決定する。処理５３５は終了し、ブールパラメータＭＡＴＣＨＥＤが「真」に設定されるステップ５４５、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０におけるＣＧ０の実行履歴が更新されるステップ５５０、並びにＭＡＴＣＨＥＤの値及びスレッド−タスク対（「０」、［ＤＬ、７］）を含むＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥが作成されるステップ５５５が実行される。
【０１０６】
例２
次に、所定のタスクに対するスレッドを選択する一例を説明する。実行されるタスク［ＦＭ、２］に対して要求されると仮定する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０の状態は以下の通りである。
｛「０」、「３」｝
【０１０７】
図３を参照して上述したように、ＭＥＳＳＡＧＥ３１５はタスク−スレッド選択器３４０に送出される。例２において、ＭＥＳＳＡＧＥ３１５は、タスク［ＦＭ、２］に対するＭＡＴＣＨ＿ＴＡＳＫタイプである。従って、図７Ａを参照して上述した処理５４０が実行されることにより、タスク［ＦＭ、２］を実行するのに適したスレッドをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０から選択する。双方のＣＧが少なくとも１つのアイドルスレッドを有するため、ステップ７０５において作成されたＣＧ＿ＬＩＳＴは、｛ＣＧ０、ＣＧ１｝である。
【０１０８】
タスク［ＦＭ、２］はＦＭ型であり、重み行列８９０に従って、ｗi＝５及びｗd＝１０を有する。これは、タスク［ＦＭ、２］に対してデータの再利用がより重要であることを意味する。従って、処理５４０はデータの再利用に対するスレッドを選択する。従って、図７Ｂを参照して上述した処理７２５が実行される。
【０１０９】
処理７２５は、使用可能なスレッドを含むＣＧのリスト、すなわちＣＧ＿ＬＩＳＴからこの例においてはＣＧ０である第１のＣＧを選択する。データの再利用が処理７２５の目的であるため、処理７２５は、タスク［ＦＭ、２］と関連付けられたＤＡＴＡＳＥＴ＿ＩＤ＝２がＣＧ０のＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１にあるかを決定する。ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０は「ＦＭ」を含むが、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１はＤＡＴＡＳＥＴ＿ＩＤ＝２を含まない。従って、処理７２５は、ＣＧ＿ＬＩＳＴにおいて使用可能なスレッドを含む例２においてはＣＧ１である次のＣＧに進む。
【０１１０】
ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６３は、ＤＡＴＡＳＥＴ＿ＩＤ＝２を含む。従って、スケジューラ３４５は、処理７２５においてＣＧ１から使用可能なスレッドがタスク［ＦＭ、２］を実行するのに適しているかを決定する。処理７２５は、ＣＧ１から使用可能なスレッド「３」を選択する。次に、ブールパラメータＭＡＴＣＨＥＤが「真」に設定されるステップ５４５、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０におけるＣＧ１の実行履歴が更新されるステップ５５０、並びにＭＡＴＣＨＥＤの値及びスレッド−タスク対（「３」、［ＦＭ、２］）を含むＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥが作成されるステップ５５５が実行される。
【０１１１】
例３
次に、所定のスレッドを選択する別の例を説明する。例３は、所定のタスクに対して命令の再利用が重要である場合の例を示すが、いずれの使用可能なスレッドによっても満たされない。タスク［ＦＲ、１］が実行されるのを待っていると仮定する。ＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０の状態は以下の通りである。
｛「０」、「３」｝
【０１１２】
図３を参照して上述したように、ＭＥＳＳＡＧＥ３１５はタスク−スレッド選択器３４０に送出される。この例において、ＭＥＳＳＡＧＥ３１５は、タスク［ＦＲ、１］に対するＭＡＴＣＨ＿ＴＡＳＫタイプである。従って、図７Ａを参照して上述した処理５４０が実行されることにより、タスク［ＦＲ、１］を実行するのに適したスレッドをＡＶＡＩＬＡＢＬＥ＿ＴＨＲＥＡＤＳ＿ＬＩＳＴ３６０から選択する。双方のＣＧが少なくとも１つのアイドルスレッド、すなわち使用可能なスレッドを有するため、ステップ７０５において作成されたＣＧ＿ＬＩＳＴは｛ＣＧ０、ＣＧ１｝である。
【０１１３】
タスク［ＦＭ、１］はＦＭ型であり、重み行列８９０に従って、ｗi＝１０及びｗd＝５を有する。これは、［ＦＲ、１］に対して命令の再利用がより重要であることを意味する。従って、処理５４０は、命令の再利用に対するスレッドを選択することを判断する。従って、図７Ｃを参照して上述した処理７３０が実行される。
【０１１４】
スケジューラ３４５は、処理７３０において使用可能なスレッドを含むＣＧのリスト、すなわちＣＧ＿ＬＩＳＴからこの例においてはＣＧ０である第１のＣＧを選択する。命令の再利用が処理７３０の目的であるため、処理７３０は、タスク［ＦＲ、１］と関連付けられたＴＡＳＫ＿ＩＤ＝ＦＲがＣＧ０のＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０において見つけられるかを決定する。ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０はＴＡＳＫ＿ＩＤ＝ＦＲを含まない。従って、処理７３０は、ＣＧ＿ＬＩＳＴにおいて使用可能なスレッドを含む本発明の例においてはＣＧ１である次のＣＧに進む。処理７３０は、ＣＧ１と関連付けられたＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６０がＴＡＳＫ＿ＩＤ＝ＦＲを含まないことを更に決定する。従って、処理７３０は、データの再利用に対して適切なスレッドを見つけることに進む。
【０１１５】
処理７３０は、タスク［ＦＲ、１］と関連付けられたＤＡＴＡＳＥＴ＿ＩＤ＝１がＣＧ０のＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１にあるかを決定する。ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ８６１は、ＤＡＴＡＳＥＴ＿ＩＤ＝１を含む。従って、処理７３０は、ＣＧ０からの使用可能なスレッドがタスク［ＦＲ、１］を実行するのに適していると決定する。処理７３０は、ＣＧ０からスレッド「０」を選択する。その後、スレッド「０」はタスク［ＦＲ、１］の実行に進む。
【０１１６】
次に、ブールパラメータＭＡＴＣＨＥＤが「真」に設定されるステップ５４５、ＥＸＥＣＵＴＩＯＮ＿ＲＥＧＩＳＴＥＲ３８０におけるＣＧ０の実行履歴が更新されるステップ５５０、並びにＭＡＴＣＨＥＤの値及びスレッド−タスク対（「０」、［ＦＲ、１］）を含むＭＡＴＣＨＥＤ＿ＭＥＳＳＡＧＥが作成されるステップ５５５が実行される。
【０１１７】
次に、図９に示されるように所定のＴＨＲＥＡＤ上で実行するのに適したタスクを選択する処理９００を参照して、別の実現例を説明する。処理９００は、図６に示されたような処理５３５の代わりに使用されてもよい。この実現例において、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造に保持された命令及びデータの履歴は、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５の２つのキューにおけるより最近のものでない項目の前にチェックされたＴＨＲＥＡＤ９０５のＣＧに対するこれらの双方のキューにおけるより最近の項目と組み合わされる。
【０１１８】
処理９００は、ＴＨＲＥＡＤ９０５のＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５から作成されたリスト構造ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹを使用する。リスト構造は、一般にシーケンスのタプルをタプルのシーケンスにマッピングするコンボリューション（又はジップ）として当技術分野において既知である処理において形成される。この場合、ＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５のそれぞれの項目Ｈi及びＨdは、ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストに保持された対のシーケンスを形成する。履歴キューが他のキューより短い場合、他のキューからの相対物を有さないエントリは、値ヌルと対にされる。例えば、そのＣＧに対してＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０が３つのエントリを有し、ＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５が５つのエントリを有する場合、所定のＣＧに対するＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストは以下のように見える。
｛（ＤＬ、６）、（ＤＬ、５）、（ＤＬ、４）、（Ｎｕｌｌ、３）、（Ｎｕｌｌ、２）｝
【０１１９】
次に、処理９００を説明する。処理９００は、スケジューラ３４５がＴＨＲＥＡＤ９０５のＣＧの履歴を取得し、そのＣＧに対するＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストを作成したステップ９１０から開始する。これは、ＴＨＲＥＡＤ＿ＴＯ＿ＣＧ＿ＬＯＯＫＵＰ＿ＴＡＢＬＥ４８０からＴＨＲＥＡＤ９０５に対するレコードにアクセスし、ＴＨＲＥＡＤ９０５が属し、その後格納されるＣＧ ＩＤフィールド４８４を取得することで実現される。次に、ＥＸＥＣＵＴＩＯＮ＿ＨＩＳＴＯＲＹ４４０構造において、そのＣＧに対するＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５を含む実行履歴がアクセスされ、対のＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストが上述したように作成される。ステップ９１２において、履歴エントリの第１の対（Ｈi、Ｈd）を取得することでＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストのエントリを繰り返す処理が開始する。
【０１２０】
ステップ９１５において、スケジューラ３４５は、ＴＨＲＥＡＤ６０５上で実行するのに適したタスクが見つけられるまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてエントリを繰り返す処理を開始する。ステップ９１５において、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５の先頭から開始し、タスクＴを取得する。ステップ９１７において、スケジューラ３４５は、タスクＴに対して重みｗi及びｗdを決定する。この重みは種々の方法で決定される。種々の方法のうちの１つは、制御プログラム１３０において全てのタスク型に対するｗi及びｗdの所定の値のルックアップテーブルを使用することであるが、それに限定されない。判断ステップ９２０において、スケジューラ３４５はｗiがｗdより大きいかをチェックする。ｗiがｗdより大きい場合、タスクＴに対して命令の再利用はデータの再利用より重要であり、処理は、ＴＡＳＫのＴＡＳＫ＿ＩＤがステップ９１２において取得した履歴エントリの対（Ｈi、Ｈd）からのタスク型Ｈiと同一であるかをチェックする判断ステップ９２５に継続する。ＴＡＳＫのＴＡＳＫ＿ＩＤがステップ９１２において取得された履歴エントリの対（Ｈi、Ｈd）からのタスク型Ｈiと同一である場合、タスクＴは適切であるため、ステップ９４５においてＴＡＳＫをＴに設定し、処理９００が終了する。
【０１２１】
ステップ９２０において、ｗiがｗdより大きくないとスケジューラ３４５が決定する場合、タスクＴに対して命令の再利用はデータの再利用と同様に重要ではなく、ステップ９３０において、タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがステップ９１２において取得された履歴エントリの対（Ｈi、Ｈd）からのＤＡＴＡＳＥＴ＿ＩＤ＝Ｈdと同一であるかをチェックする。タスクＴと関連付けられたＤＡＴＡＳＥＴ＿ＩＤがステップ９１２において取得された履歴エントリの対（Ｈi、Ｈd）からのＤＡＴＡＳＥＴ＿ＩＤ＝Ｈdと同一である場合、タスクＴは適切なタスクであるため、ステップ９４５においてＴＡＳＫをＴに設定し、処理９００が終了する。
【０１２２】
ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５からタスクＴを取得し、且つＴＡＳＫ＿ＩＤ又はＤＡＴＡＳＥＴ＿ＩＤがＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにあるかをチェックする処理は、ステップ９３５においてテストされたように、Ｈi又はＨdを一致させるタスクが見つけられるまで、あるいはキューの後方に到達するまでＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５においてタスク毎に繰り返される。
【０１２３】
チェック、判断ステップ９３５において決定すべきタスクがこれ以上ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５にない場合、スケジューラ３４５がまだチェックされていないより多くのエントリがＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにあるかをチェックするステップ９３７に進む。まだチェックされていないより多くのエントリがＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにある場合、ステップ９３６において、ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにおける次のエントリに対する適合性に対して最初からＲＥＡＤ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５におけるタスクをチェックし始めるためにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５繰返し子を再設定する。その後処理は、履歴エントリの次の対がＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストから取得されるステップ９１２に戻る。
【０１２４】
判断ステップ９３７において、チェックすべきエントリがこれ以上ＣＯＭＢＩＮＥＤ＿ＨＩＳＴＯＲＹリストにないとスケジューラ３４５が決定する場合、処理９００は、ＴＡＳＫをＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５における第１のタスクに設定するステップ９４０に進む。キューの先頭のタスクは最も優先度の高いタスクであり、キャッシュ内容の再利用を実現できない場合、ＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５における第１のタスクは、実行するためにディスパッチされたタスクである。処理９００はステップ９４０で終了する。
【０１２５】
実行履歴キューＴＡＳＫ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９０及びＤＡＴＡ＿ＨＩＳＴＯＲＹ＿ＱＵＥＵＥ４９５、並びにＲＥＡＤＹ＿ＴＡＳＫ＿ＱＵＥＵＥ３５５において双方のエントリを繰り返す複雑性が増加したことによる何らかの余分なオーバヘッドを含むキャッシュ内容の再利用の機会を改善するために、処理９００は、図５の処理５３５の代わりに使用されてもよい。
【産業上の利用可能性】
【０１２６】
説明した構成は、コンピュータ産業及びデータ処理産業、並びに特にキャッシュの再利用を増進するキャッシュメモリに対して適用可能である。
【０１２７】
上記の記述は本発明のいくつかの実施形態のみを説明し、本発明の範囲及び趣旨から逸脱せずに、変形及び／又は変更がいくつかの実施形態に対して行なわれてもよい。実施形態は、限定するものではなく例示するものである。例えば、説明した好適な構成は、各計算グループを対応するＬ２キャッシュと関連付けることでＬ２キャッシュを最適化する計算グループの動的構成に注目したが、同一の原理は、図１０Ｂに示されたようなＬ３キャッシュ等の他のキャッシュレベルを最適化するために適用されてもよい。図１０Ｂにおいて、Ｌ３最適化のためのＬ３キャッシュに対応する計算グループＣＧが形成される。
【特許請求の範囲】
【請求項１】
マルチプロセッサのコンピュータシステムにおいて、タスクを実行すべく複数のスレッドから１つのスレッドを決定する方法であって、前記複数のスレッドは前記コンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化されており、前記タスクは命令の集合により決定される型を有しており、前記方法は、
複数のスレッドのサブセットの実行履歴を取得するステップと、
命令の集合及びデータの集合の各々に対し、前記タスクの型に依存している重み付けを決定するステップと、
前記実行履歴と前記決定された重み付けとに基づいて、前記タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するステップと、
前記複数のスレッドの前記サブセットの前記決定された適合性を条件として、前記複数のスレッドの前記サブセットに関連付けられた前記キャッシュメモリの内容を使用して、前記タスクを実行すべく前記複数のスレッドの前記サブセットから１つのスレッドを決定するステップと、
を含むことを特徴とする方法。
【請求項２】
前記重み付けは、使用される複数のスレッドのサブセットの適合性を決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することを特徴とする請求項１に記載の方法。
【請求項３】
前記複数のスレッドの前記サブセットの適合性を決定する前記ステップは、
命令に対する重み付けがデータに対する重み付けより大きい場合に、前記タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するために、前記データ履歴の前に前記タスク履歴を検査するサブステップと、
データに対する重み付けが命令に対する重み付けより大きい場合に、前記タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するために、前記タスク履歴の前に前記データ履歴を検査するサブステップと、
を含む
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記重み付けは、前記複数のスレッドの前記サブセットの実行履歴に基づいて決定されることを特徴とする請求項１に記載の方法。
【請求項５】
前記重み付けは、ルックアップテーブルを使用して決定されることを特徴とする請求項１に記載の方法。
【請求項６】
前記実行履歴は、前記キャッシュメモリのサイズに依存したサイズを有することを特徴とする請求項１に記載の方法。
【請求項７】
前記実行履歴は、前記複数のスレッドにより実行されるタスクの集合に関連して最も多く実行された命令のサイズに依存したサイズを有することを特徴とする請求項１に記載の方法。
【請求項８】
前記実行履歴は、前記複数のスレッドにより実行されるタスクの集合により使用されたデータに依存したサイズを有することを特徴とする請求項１に記載の方法。
【請求項９】
マルチプロセッサのコンピュータシステムにおいて、印刷タスクを処理するためのキャッシュメモリのキャッシュ再利用を管理する方法であって、前記キャッシュメモリは複数のスレッドのサブセットと関連付けられており、前記印刷タスクは該印刷タスクのための命令の集合により決定される型を有しており、前記方法は、
複数のスレッドのサブセットの実行履歴を取得するステップと、
命令の集合及びデータの集合の各々に対し、前記印刷タスクの型に依存している重み付けを決定するステップと、
前記実行履歴と前記決定された重み付けとに基づいて、前記印刷タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するステップと、
前記印刷タスクを処理する前記サブセットから１つのスレッドを決定することにより前記複数のスレッドの前記サブセットが適切であると決定される場合に、前記キャッシュメモリを再利用するステップと、
を含むことを特徴とする方法。
【請求項１０】
マルチプロセッサのコンピュータシステムにおいて、スレッドによる実行のために複数のタスクから１つのタスクを決定する方法であって、前記スレッドは前記コンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化される複数のスレッドの１つであり、前記タスクは命令の集合により決定される型を有しており、前記方法は、
前記スレッドの実行履歴を取得し、対応するキャッシュメモリを識別するステップと、
実行のために利用可能なタスクを識別し、命令の集合及びデータの集合の各々に対し、前記識別されたタスクの型に依存している重み付けを決定するステップと、
前記実行履歴と前記決定された重み付けとに基づいて、前記スレッドで実行すべく前記識別されたタスクの適合性を決定するステップと、
前記複数のスレッドのサブセットの前記決定された適合性を条件として、前記対応するキャッシュメモリの内容に基づいて、前記複数のタスクから前記スレッドで実行される１つの前記識別されたタスクを決定するステップと、
を含むことを特徴とする方法。
【請求項１１】
前記重み付けは、使用されるタスクを決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することを特徴とする請求項１０に記載の方法。
【請求項１２】
スレッドによる実行のために複数のタスクから１つのタスクの適合性を決定する前記ステップは、
前記タスクの命令に対する重み付けがデータに対する重み付けより大きい場合に、前記スレッドにより実行される前記タスクの適合性を決定するために、前記データ履歴の前に前記タスク履歴を検査するサブステップと、
前記タスクのデータに対する重み付けが命令に対する重み付けより大きい場合に、前記スレッドにより実行される前記タスクの適合性を決定するために、前記タスク履歴の前に前記データ履歴を検査するサブステップと、
を含む
ことを特徴とする請求項１０に記載の方法。
【請求項１３】
コンピュータシステムに請求項１に記載の方法を実行させるためのプログラムを格納したコンピュータ可読の記憶媒体。
【請求項１４】
コンピュータシステムに請求項９に記載の方法を実行させるためのプログラムを格納したコンピュータ可読の記憶媒体。
【請求項１５】
コンピュータシステムに請求項１０に記載の方法を実行させるためのプログラムを格納したコンピュータ可読の記憶媒体。
【請求項１６】
請求項１に記載の方法を実行するように構成されたコンピュータシステム。
【請求項１７】
請求項９に記載の方法を実行するように構成されたコンピュータシステム。
【請求項１８】
請求項１０に記載の方法を実行するように構成されたコンピュータシステム。
【請求項１９】
複数のプロセッサと該複数のプロセッサに関連付けられたキャッシュメモリとを有し、少なくとも該複数のプロセッサと該キャッシュメモリとの間の命令を用いてアプリケーション・プログラムを実行するように構成されたコンピュータシステムであって、該コンピュータシステムは、該コンピュータシステムにおいて、複数のスレッドから前記アプリケーション・プログラムのタスクを実行する１つのスレッドを決定するスケジューラを含み、前記複数のスレッドは前記キャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化されており、前記タスクは命令の集合により決定される型を有しており、前記スケジューラは、
複数のスレッドのサブセットの実行履歴を取得し、
命令の集合及びデータの集合の各々に対し、前記タスクの型に依存した重み付けを決定し、
前記実行履歴と前記決定された重み付けとに基づいて、前記タスクを実行する前記複数のスレッドの前記サブセットの適合性を決定し、
前記複数のスレッドの前記サブセットの前記決定された適合性を条件として、前記複数のスレッドの前記サブセットに関連付けられた前記キャッシュメモリの内容を使用して、前記複数のスレッドの前記サブセットから前記タスクを実行する１つのスレッドを決定する、
よう動作することを特徴とするコンピュータシステム。
【請求項１】
マルチプロセッサのコンピュータシステムにおいて、タスクを実行すべく複数のスレッドから１つのスレッドを決定する方法であって、前記複数のスレッドは前記コンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化されており、前記タスクは命令の集合により決定される型を有しており、前記方法は、
複数のスレッドのサブセットの実行履歴を取得するステップと、
命令の集合及びデータの集合の各々に対し、前記タスクの型に依存している重み付けを決定するステップと、
前記実行履歴と前記決定された重み付けとに基づいて、前記タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するステップと、
前記複数のスレッドの前記サブセットの前記決定された適合性を条件として、前記複数のスレッドの前記サブセットに関連付けられた前記キャッシュメモリの内容を使用して、前記タスクを実行すべく前記複数のスレッドの前記サブセットから１つのスレッドを決定するステップと、
を含むことを特徴とする方法。
【請求項２】
前記重み付けは、使用される複数のスレッドのサブセットの適合性を決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することを特徴とする請求項１に記載の方法。
【請求項３】
前記複数のスレッドの前記サブセットの適合性を決定する前記ステップは、
命令に対する重み付けがデータに対する重み付けより大きい場合に、前記タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するために、前記データ履歴の前に前記タスク履歴を検査するサブステップと、
データに対する重み付けが命令に対する重み付けより大きい場合に、前記タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するために、前記タスク履歴の前に前記データ履歴を検査するサブステップと、
を含む
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記重み付けは、前記複数のスレッドの前記サブセットの実行履歴に基づいて決定されることを特徴とする請求項１に記載の方法。
【請求項５】
前記重み付けは、ルックアップテーブルを使用して決定されることを特徴とする請求項１に記載の方法。
【請求項６】
前記実行履歴は、前記キャッシュメモリのサイズに依存したサイズを有することを特徴とする請求項１に記載の方法。
【請求項７】
前記実行履歴は、前記複数のスレッドにより実行されるタスクの集合に関連して最も多く実行された命令のサイズに依存したサイズを有することを特徴とする請求項１に記載の方法。
【請求項８】
前記実行履歴は、前記複数のスレッドにより実行されるタスクの集合により使用されたデータに依存したサイズを有することを特徴とする請求項１に記載の方法。
【請求項９】
マルチプロセッサのコンピュータシステムにおいて、印刷タスクを処理するためのキャッシュメモリのキャッシュ再利用を管理する方法であって、前記キャッシュメモリは複数のスレッドのサブセットと関連付けられており、前記印刷タスクは該印刷タスクのための命令の集合により決定される型を有しており、前記方法は、
複数のスレッドのサブセットの実行履歴を取得するステップと、
命令の集合及びデータの集合の各々に対し、前記印刷タスクの型に依存している重み付けを決定するステップと、
前記実行履歴と前記決定された重み付けとに基づいて、前記印刷タスクを実行すべく前記複数のスレッドの前記サブセットの適合性を決定するステップと、
前記印刷タスクを処理する前記サブセットから１つのスレッドを決定することにより前記複数のスレッドの前記サブセットが適切であると決定される場合に、前記キャッシュメモリを再利用するステップと、
を含むことを特徴とする方法。
【請求項１０】
マルチプロセッサのコンピュータシステムにおいて、スレッドによる実行のために複数のタスクから１つのタスクを決定する方法であって、前記スレッドは前記コンピュータシステムのキャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化される複数のスレッドの１つであり、前記タスクは命令の集合により決定される型を有しており、前記方法は、
前記スレッドの実行履歴を取得し、対応するキャッシュメモリを識別するステップと、
実行のために利用可能なタスクを識別し、命令の集合及びデータの集合の各々に対し、前記識別されたタスクの型に依存している重み付けを決定するステップと、
前記実行履歴と前記決定された重み付けとに基づいて、前記スレッドで実行すべく前記識別されたタスクの適合性を決定するステップと、
前記複数のスレッドのサブセットの前記決定された適合性を条件として、前記対応するキャッシュメモリの内容に基づいて、前記複数のタスクから前記スレッドで実行される１つの前記識別されたタスクを決定するステップと、
を含むことを特徴とする方法。
【請求項１１】
前記重み付けは、使用されるタスクを決定するために使用されるタスク履歴及びデータ履歴のうちの一方を決定することを特徴とする請求項１０に記載の方法。
【請求項１２】
スレッドによる実行のために複数のタスクから１つのタスクの適合性を決定する前記ステップは、
前記タスクの命令に対する重み付けがデータに対する重み付けより大きい場合に、前記スレッドにより実行される前記タスクの適合性を決定するために、前記データ履歴の前に前記タスク履歴を検査するサブステップと、
前記タスクのデータに対する重み付けが命令に対する重み付けより大きい場合に、前記スレッドにより実行される前記タスクの適合性を決定するために、前記タスク履歴の前に前記データ履歴を検査するサブステップと、
を含む
ことを特徴とする請求項１０に記載の方法。
【請求項１３】
コンピュータシステムに請求項１に記載の方法を実行させるためのプログラムを格納したコンピュータ可読の記憶媒体。
【請求項１４】
コンピュータシステムに請求項９に記載の方法を実行させるためのプログラムを格納したコンピュータ可読の記憶媒体。
【請求項１５】
コンピュータシステムに請求項１０に記載の方法を実行させるためのプログラムを格納したコンピュータ可読の記憶媒体。
【請求項１６】
請求項１に記載の方法を実行するように構成されたコンピュータシステム。
【請求項１７】
請求項９に記載の方法を実行するように構成されたコンピュータシステム。
【請求項１８】
請求項１０に記載の方法を実行するように構成されたコンピュータシステム。
【請求項１９】
複数のプロセッサと該複数のプロセッサに関連付けられたキャッシュメモリとを有し、少なくとも該複数のプロセッサと該キャッシュメモリとの間の命令を用いてアプリケーション・プログラムを実行するように構成されたコンピュータシステムであって、該コンピュータシステムは、該コンピュータシステムにおいて、複数のスレッドから前記アプリケーション・プログラムのタスクを実行する１つのスレッドを決定するスケジューラを含み、前記複数のスレッドは前記キャッシュメモリに関連付けられた少なくとも１つのサブセットにグループ化されており、前記タスクは命令の集合により決定される型を有しており、前記スケジューラは、
複数のスレッドのサブセットの実行履歴を取得し、
命令の集合及びデータの集合の各々に対し、前記タスクの型に依存した重み付けを決定し、
前記実行履歴と前記決定された重み付けとに基づいて、前記タスクを実行する前記複数のスレッドの前記サブセットの適合性を決定し、
前記複数のスレッドの前記サブセットの前記決定された適合性を条件として、前記複数のスレッドの前記サブセットに関連付けられた前記キャッシュメモリの内容を使用して、前記複数のスレッドの前記サブセットから前記タスクを実行する１つのスレッドを決定する、
よう動作することを特徴とするコンピュータシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１１Ａ】
【図１１Ｂ】
【図１１Ｃ】
【図１１Ｄ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１１Ａ】
【図１１Ｂ】
【図１１Ｃ】
【図１１Ｄ】
【公開番号】特開２０１３−４７９５０（Ｐ２０１３−４７９５０Ａ）
【公開日】平成２５年３月７日（２０１３．３．７）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−１８１１７２（Ｐ２０１２−１８１１７２）
【出願日】平成２４年８月１７日（２０１２．８．１７）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２５年３月７日（２０１３．３．７）
【国際特許分類】
【出願番号】特願２０１２−１８１１７２（Ｐ２０１２−１８１１７２）
【出願日】平成２４年８月１７日（２０１２．８．１７）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]