(57)【特許請求の範囲】
【請求項１】
コンピュータシステム内でスレッドを実行する方法であって、当該方法は、
複数のスレッドをそれぞれのスレッドのタイプに基づいて第１のスレッドタイプまたは第２のスレッドタイプに分離すること、
それぞれが第１のスレッドタイプの複数のスレッドを主に含む第１のバッチを形成すること、
プロセッサによって、それぞれの第１のバッチの複数のスレッドを実行することであって、第１のバッチの複数のスレッドの各々は、メモリバンク内の互いに異なるメモリからデータを抽出することを含む、実行することと、
それぞれが第２のスレッドタイプの複数のスレッドを主に含む第２のバッチを形成すること、
前記プロセッサによって、それぞれの第２のバッチの複数のスレッドを実行することを含み、それぞれの第１のバッチの複数のスレッドが、それぞれの第２のバッチの複数のスレッドが実行される前に実行される方法。
【請求項２】
それぞれの第１のバッチの複数のスレッドを実行することが、第２のバッチを形成する前に発生する、請求項１に記載の方法。
【請求項３】
それぞれの第１のバッチの複数のスレッドを実行することが、任意の他の第１のバッチのスレッドを実行する前に、選択された第１のバッチのすべてのスレッドを実行することを含む、請求項１に記載の方法。
【請求項４】
分離することが、第１のスレッドタイプの複数のスレッドを第１のグループにグループ化すること、第２のスレッドタイプの複数のスレッドを第２のグループにグループ化すること、第３のスレッドタイプの複数のスレッドを第３のグループにグループ化することを含む、請求項１に記載の方法。
【請求項５】
分離することが、これまでのスレッドを実行することから収集された過去の互換性データに基づいて分離することを含む、請求項１に記載の方法。
【請求項６】
分離することが、前記複数のスレッドが、並列プロセッサと共に使用するために、メモリバンクから並列してデータを抽出できるか否かに基づいて分離することを含む、請求項１に記載の方法。
【請求項７】
分離することが、前記スレッドがその他のスレッドと共働するために、異なるメモリバンクからデータを抽出できるか否かに基づいて分離することを含む、請求項１に記載の方法。
【請求項８】
分離することが、スレッドが発生したアプリケーションプログラムに基づいて分離することを含む、請求項１に記載の方法。
【請求項９】
分離することが、それぞれのスレッドが行うメモリ要求の相対数に基づいて分離することを含む、請求項１に記載の方法。
【請求項１０】
コンピュータシステム内でスレッドを実行するために、コンピュータ可読媒体内で符号化されたソフトウェアを有するコンピュータプログラム製品であって、前記ソフトウェアが実行されることに応答して動作可能な命令を含み、その命令は、
複数のスレッドをそれぞれのスレッドのタイプに基づいて第１のスレッドタイプまたは第２のスレッドタイプに分離することと、
それぞれが第１のスレッドタイプの複数のスレッドを主に含む第１のバッチを形成することと、
プロセッサによって、それぞれの第１のバッチの複数のスレッドを実行することであって、第1のバッチの複数のスレッドの各々は、メモリバンク内の互いに異なるメモリからデータを抽出することを含む、実行することと、
それぞれが第２のスレッドタイプの複数のスレッドを主に含む第２のバッチを形成することと、
前記プロセッサによって、それぞれの第２のバッチの複数のスレッドを実行することと含み、それぞれの第１のバッチの複数のスレッドが、それぞれの第２のバッチの複数のスレッドが実行される前に実行されるコンピュータプログラム。
【請求項１１】
前記命令が、それぞれの第１のバッチの複数のスレッドを実行し、次いで、第２のバッチを形成する、請求項１０に記載のコンピュータプログラム。
【請求項１２】
それぞれの第１のバッチの複数のスレッドを実行するための前記命令が、選択された第１のバッチのすべてのスレッドを実行し、次いで、任意の他の第１のバッチのスレッドを実行するための命令を含む、請求項１０に記載のコンピュータプログラム。
【請求項１３】
分離するための前記命令が、前記複数のスレッドを３つのグループにグループ化するための命令を含み、前記３つのグループのそれぞれは、第１のスレッドタイプ、第２のスレッドタイプ、または第３のスレッドタイプのうちのそれぞれ１つからのスレッドを含む、請求項１０に記載のコンピュータプログラム。
【請求項１４】
分離するための前記命令が、これまでのスレッドを実行することから収集された過去の互換性データに基づいて分離するための命令を含む、請求項１０に記載のコンピュータプログラム。
【請求項１５】
分離するための前記命令が、前記スレッドが、並列プロセッサと共に使用するために、メモリバンクから並列してデータを抽出できるか否かに基づいて分離するための命令を含む、請求項１０に記載のコンピュータプログラム。
【請求項１６】
コンピュータシステムにおいて、当該コンピュータシステムが、
複数のコアを含むプロセッサと、
前記複数のコアに動作可能に結合されたコンピュータ可読媒体であって、該コンピュータ可読媒体が、前記コンピュータシステムによって実行されることに応答して、前記コンピュータシステムが、以下のように構成されたコンピュータ実行可能な命令を含む、コンピュータ可読媒体と、を含み、前記コンピュータシステムが、
複数のスレッドをそれぞれのスレッドのタイプに基づいて第１のスレッドタイプまたは第２のスレッドタイプに分離するように構成され、
それぞれが第１のスレッドタイプの複数のスレッドを主に含む第１のバッチを形成するように構成され、
前記コンピュータシステムによって、それぞれの第１のバッチの複数のスレッドを実行するように構成され、第１のバッチの複数のスレッドの各々は、メモリバンク内の互いに異なるメモリからデータを抽出することを含み、
それぞれが第２のスレッドタイプの複数のスレッドを主に含む第２のバッチを形成するように構成され、
前記コンピュータシステムによって、それぞれの第２のバッチの複数のスレッドを実行するように構成され、それぞれの第１のバッチの複数のスレッドが、それぞれの第２のバッチの複数のスレッドが実行される前に実行されることを含む、
コンピュータシステム。
【請求項１７】
選択された第１のバッチのすべてのスレッドを実行し、次いで、任意の他の第１のバッチのスレッドを実行するようにさらに構成された、請求項１６に記載のコンピュータシステム。
【請求項１８】
これまでのスレッドを実行することから収集された過去の互換性データに基づいて前記スレッドを分離すようにさらに構成された、請求項１６に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、以下の同時継続出願、すなわち、２００９年７月２２日に出願された「Ｂａｔｃｈ  Ｓｃｈｅｄｕｌｉｎｇ  Ｗｉｔｈ  Ｓｅｇｒｅｇａｔｉｏｎ」という表題の出願第１２／５０７，６９６号、および２００９年７月２２日に出願された「Ａｐｐｌｉｃａｔｉｏｎ  Ｓｅｌｅｔｉｏｎ  ｏｆ  Ｍｅｍｏｒｙ  Ｒｅｑｕｅｓｔ  Ｓｃｈｅｄｕｌｉｎｇ」という表題の出願第１２／５０７，６７１号に関する。
【背景技術】
【０００２】
チップマルチプロセッサ（ＣＭＰ）システムでは、ＤＲＡＭシステムはコア間で共有される。共有されたＤＲＡＭシステムでは、スレッドからの要求は、バンク衝突、バス衝突、または低バッファ衝突を引き起こすことによって、他のスレッドからの要求を遅らせる可能性があるだけでなく、他のスレッドのＤＲＡＭバンクレベルの並列処理を破壊する可能性がある。普通なら並行化されているはずのレイテンシを伴う要求は、事実上シリアル化される可能性がある。結果として、公平性とシステムスループットの両方が劣化する可能性があり、一部のスレッドは長期間にわたって処理されない（ｓｔａｒｖｅ）可能性がある。
【０００３】
公平で高性能のメモリスケジューリングを実行するための一手法は、本出願に一致しない場合を除いて、そのすべてが参照により本明細書に組み込まれている、Ｏｎｕｒ  ＭｕｔｌｕおよびＴｈｏｍａｓ  Ｍｏｓｃｉｂｒｏｄａの「Ｐａｒａｌｌｅｌｉｓｍ−Ａｗａｒｅ  Ｂａｔｃｈ  Ｓｃｈｅｄｕｌｉｎｇ：Ｅｎｈａｎｃｉｎｇ  ｂｏｔｈ  Ｐｅｒｆｏｒｍａｎｃｅ  ａｎｄ  Ｆａｉｒｎｅｓｓ  ｏｆ  Ｓｈａｒｅｄ  ＤＲＡＭ  Ｓｙｓｔｅｍｓ」／ＳＣＡ、６３〜７４ページ、２００８（２００８  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ）に示されるような並列処理認識バッチスケジューリング（ｐａｒａｌｌｅｌｉｓｍ−ａｗａｒｅ  ｂａｔｃｈ  ｓｃｈｅｄｕｌｉｎｇ）（ＰＡＲ−ＢＳ）と呼ばれるスケジューリングアルゴリズムを使用している。ＰＡＲ−ＢＳ設計は、２つの構想に基づく。すなわち、（１）要求バッチ処理、および（２）並列処理認識メモリスケジューリングである。第１に、ＰＡＲ−ＢＳは、公平性を提供して、要求の未処理（ｓｔａｒｖａｔｉｏｎ）を回避するために、ＤＲＡＭ要求をバッチの形で処理する。第２に、システムスループットを最適化するために、ＰＡＲ−ＢＳは、ＤＲＡＭバンク内でスレッドからの要求を並列処理し、それによって、スレッドが経験するメモリ関連の失速時間を削減する目的で、並列処理認識ＤＲＡＭスケジューリングポリシーを用いる。ＰＡＲ−ＢＳは、システムレベルのスレッド優先順位に関するサポートを組み込み、異なる優先順位を有するスレッドに対して、純粋に便宜主義的なサービスを含めて、異なるサービスレベルを提供することが可能である。
【発明の概要】
【課題を解決するための手段】
【０００４】
第１の態様では、本開示は、一般に、スレッドを第１のスレッドタイプまたは第２のスレッドタイプに分離すること、それぞれが第１のスレッドタイプの第１のスレッドを主に含む第１のバッチを形成すること、それぞれの第１のバッチのスレッドを実行することを含む、コンピュータシステム内でスレッドを実行する方法を説明する。
【０００５】
第２の態様では、本開示は、一般に、コンピュータシステム内でスレッドを実行するために、コンピュータ可読媒体内で符号化されたソフトウェアを有するコンピュータプログラム製品を説明する。このソフトウェアは、実行されたとき、スレッドを第１のスレッドタイプまたは第２のスレッドタイプに分離して、それぞれが第１のスレッドタイプの第１のスレッドを主に含む第１のバッチを形成し、それぞれの第１のバッチのスレッドを実行するように動作可能な命令を含む。
【０００６】
第３の態様では、本開示は、一般に、複数のコアと、それらの複数のコアに動作可能に結合されたコンピュータ可読媒体とを有するコンピュータシステムを説明する。このコンピュータ可読媒体は、コンピュータシステムによって実行されたとき、スレッドを第１のスレッドタイプまたは第２のスレッドタイプに分離し、それぞれが第１のスレッドタイプのスレッドを主に含む第１のバッチを形成し、それぞれの第１のバッチのスレッドを実行するようにそのコンピュータシステムを構成するコンピュータ実行可能命令を含む。
【０００７】
前述の要約は、単に例示的であり、決して限定的であることが意図されない。上で説明された例示的な態様、実施形態、および特徴に加えて、さらなる態様、実施形態、および特徴は、図面および以下の発明を実施するための形態を参照することによって明らかになるであろう。
【０００８】
主題は、本明細書の結末部分で詳細に指摘され、明確に特許請求される。本開示の前述の特徴およびその他の特徴は、添付の図面と共に、以下の説明および添付の特許請求の範囲から十分明らかになるであろう。これらの図面は本開示によるいくつかの実施形態だけを示し、したがって、その範囲を限定すると見なされないことを理解し、本開示は、添付の図面の使用により、追加の特異性および詳細を用いて説明される。
【図面の簡単な説明】
【０００９】
【図１】コンピュータシステムを例示する図である。
【図２】オペレーティングシステムによって実行されているアプリケーションプログラムを例示する図である。
【図３】図３Ａのオペレーティングシステムまたはアプリケーションプログラムのスレッドスケジューラの詳細図を含む、メモリコントローラに送信される要求を発行するスレッドに分割されているアプリケーションプログラムの概略図である。
【図４】方法、装置（システム）、およびコンピュータプログラム製品を例示する流れ図である。
【図５】すべて本開示の少なくともいくつかの実施形態に従って構成された、バッチの形で構成されているスレッドの概略図である。
【発明を実施するための形態】
【００１０】
以下の説明は、特許請求される主題の十分な理解をもたらすために、特定の詳細と共に様々な例を記載する。しかし、特許請求される主題は、本明細書で開示される特定の詳細のうちのいくつかまたはより多くの当該詳細なしに実行可能である点を当業者は理解されよう。さらに、状況によっては、よく知られている方法、手順、システム、構成要素、および／または回路は、特許請求される主題を不必要にあいまいにすることを回避するために、詳しく説明されていない。以下の詳細な説明では、その説明の一部を形成する添付の図面が参照される。図面では、別段文脈によって示されない限り、類似の符号は、通常、類似の構成要素を識別する。発明を実施するための形態、図面、および特許請求の範囲において説明される例示的な実施形態は、限定的なものとしない。本明細書で提示される主題の趣旨または範囲から逸脱せずに、その他の実施形態を利用することが可能であり、ここに提示される主題の趣旨および範囲から逸脱せずに、その他の変更を行うことも可能である。本明細書で一般に説明され、図面において例示される本開示の態様は、そのすべてが明示的に企図され、本開示の一部である幅広い異なる構成で構成、置換、組合せ、および設計され得る点を容易に理解されよう。
【００１１】
以下の説明では、コンピュータ内および／もしくはコンピューティングシステムメモリ内など、コンピューティングシステム内に格納されたデータビットおよび／もしくは２値デジタル信号に関するアルゴリズムならびに／または動作の記号表現が提示される場合がある。アルゴリズムは、一般に、所望される結果をもたらす動作および／または類似処理の自己無撞着シーケンスと見なされ、この場合、これらの動作は、格納されること、転送されること、組み合わされること、比較されること、および／もしくは、他の方法で操作されることが可能な電気信号、磁気信号ならびに／または電磁信号の形をとり得る物理量の物理処理を必要とする場合がある。様々な状況において、かかる信号は、ビット、データ、値、要素、記号、文字、用語、番号、数字などと呼ばれる場合がある。しかし、当業者は、かかる用語は物理量を意味するために使用され得る点を認識されよう。したがって、本明細書において「格納する」、「処理する」、「取り出す」、「計算する」、「決定する」などの用語が使用されるとき、これらは、コンピューティングプラットフォームのプロセッサ内、メモリ内、レジスタ内などの電子量および／もしくは磁気量を含む物理量として表されるデータを操作ならびに／または変換する、コンピュータ、あるいはセルラ電話などの類似の電子コンピューティングデバイスなど、コンピューティングプラットフォームの動作を指す場合がある。
【００１２】
本開示は、とりわけ、バッチスケジューリングによるスレッドのスケジューリングに関する方法、装置、システム、およびコンピュータプログラム製品に関して描写される。本開示は、一定の基準に基づいて、スレッドのバッチへのグループ化の発見を使用する。（１）それらのスレッドが、並列プロセッサと共に使用するために、どのくらい良好に設計されているかに基づいて、良好な設計スレッドおよび不良な設計スレッド、（２）それらのスレッドがその他のスレッドとどのくらい効果的に共働するかに基づいて、協調スレッドおよび非協調スレッド、（３）そのスレッドが発生したアプリケーションプログラムに基づいて、第１のアプリケーションスレッド、第２のアプリケーションスレッド、および第３のアプリケーションスレッド、（４）それらのスレッドが行うメモリ内のデータに関する要求の相対数に基づいて、大規模要求スレッド、任意選択で、中規模要求スレッドおよび小規模要求スレッド、例えば、大規模要求スレッドは、平均数以上の要求を行うことが可能であり、小規模要求スレッドは、平均数未満のいくつかの要求を行うことが可能であるなど、様々な様式でこれらのスレッドをバッチにグループ化することが可能である。スレッドをバッチにグループ化するためのその他の基準は、それぞれのスレッドに重要度、例えば、高い重要度もしくは低い重要度を割り当てること、または重要度値を割り当てて、類似の重要度値もしくは同じ重要度値を有するスレッドを共にバッチ処理することを含むことが可能である。スレッドをバッチにグループ化するためのさらにその他の基準は、それぞれのスレッドに関連するゴーストページ（ｇｈｏｓｔ  ｐａｇｅ）内に格納されたデータを用いて、これまでそれらのスレッドを実行したときに収集された過去の互換性データに基づいてグループ化することを含むことが可能であり、または当該データは、そこからそのスレッドが発行されたアプリケーションプログラムの一部として提供されたフリーズドライゴーストページ（ｆｒｅｅｚｅ  ｄｒｉｅｄ  ｇｈｏｓｔ  ｐａｇｅ）内に格納可能であり、このフリーズドライゴーストページはそのアプリケーションプログラムを用いて提供されたスレッドの互換性データを含む。多くの他の改変形態が可能である。
【００１３】
いくつかの例では、コンピュータシステム内で実行しているスレッドを分離するための方法が説明される場合がある。このコンピュータシステムは、オペレーティングシステムを含むことが可能である。いくつかの説明される方法は、その効率性に基づいて、スレッドを良好なスレッドおよび不良なスレッドに分離することを含むことが可能である。いくつかの例では、メモリバンクから並列してデータを抽出できるスレッドは、良好なスレッドと見なすことができ、メモリバンクから並列してデータを抽出できないスレッドは、不良なスレッドと見なすことができる。これらの方法は、良好なスレッドを主に含むスレッドの第１のバッチを形成すること、不良なスレッドを主に含むスレッドの第２のバッチとを形成することを含むことも可能である。
【００１４】
いくつかの追加の例では、コンピュータシステム内で実行しているスレッドを分離するための方法が説明される場合がある。このコンピュータシステムは、オペレーティングシステムを含むことが可能である。例示的な方法は、どのスレッドが互いに効率的に動作し、どのスレッドが互いに効率的に動作しないかを決定することを含むことが可能である。互いに効率的に動作するスレッドは、異なるメモリバンクからデータを抽出することができ、互いに効率的に動作しないスレッドは、同じメモリバンクからデータを抽出することができる。例示的な方法は、互いに効率的に動作するスレッドを主に含むスレッドの第１のバッチを形成すること、互いに効率的に動作しないスレッドを主に含むスレッドの第２のバッチを形成することを含むことも可能である。
【００１５】
さらにその他の例では、コンピュータシステム内で実行しているスレッドを分離するための方法が説明される場合がある。このコンピュータシステムは、オペレーティングシステムを含むことが可能である。これらの例示的な方法は、基準に基づいて、それらのスレッドを第１のスレッドタイプと第２のスレッドタイプとに分離することを含むことが可能である。これらの例示的な方法は、主に第１のスレッドタイプのものであるスレッドを含む第１のバッチを形成すること、主に第２のスレッドタイプのものであるスレッドを含む第２のバッチを形成することを含むことも可能である。
【００１６】
図１は、本開示の少なくともいくつかの実施形態に従って構成されたコンピュータシステムを例示する。図１は、プロセッサ１１０と、メモリ１２０と、１つまたは複数のドライブ１３０とを含むコンピュータ１００を例示する。ドライブ１３０およびその関連するコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの記憶装置をコンピュータ１００に提供することが可能である。ドライブ１３０は、オペレーティングシステム１４０と、アプリケーションプログラム１５０と、プログラムモジュール１６０と、データベース１８０とを含むことが可能である。オペレーティングシステム１４０および／またはアプリケーションプログラム１５０は、例えば、コンピュータ１００に図４に指定される機能および／または動作、例えば、バッチスケジューリングアプリケーション１５４を実行させるためのプログラム命令を含むことが可能である。コンピュータ１００は、それを介してユーザがコマンドおよびデータを入力できるユーザ入力デバイス１９０を含むことが可能である。入力デバイスは、電子デジタイザと、マイクロフォンと、キーボードと、一般に、マウス、トラックボールまたはタッチパッドと呼ばれるポインティングデバイスとを含むことが可能である。その他の入力デバイスは、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナなどを含むことが可能である。
【００１７】
これらの入力デバイスおよびその他の入力デバイスは、システムバスに結合可能なユーザ入力インターフェースを介してプロセッサ１１０に結合可能であるか、あるいは当該入力デバイスは、パラレルポート、ゲームポート、もしくはユニバーサルシリアルバス（ＵＳＢ）など、その他のインターフェースまたはバス構造によって接続可能である。コンピュータ１００は、出力周辺インターフェース１９４などを介して接続可能なスピーカ、プリンタ、またはディスプレイ２０２など、周辺出力デバイスを含むことが可能である。
【００１８】
コンピュータ１００は、ネットワークインターフェース１９６に接続された遠隔コンピュータなど、１つまたは複数のコンピュータに対する論理接続を使用して、ネットワーキング環境で動作するように構成され得る。この遠隔コンピュータは、パーソナルコンピュータ（ＰＣ）、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、またはその他の共通ネットワークノードであってよく、コンピュータ１００に関連して上で説明された要素の多くまたはすべてを含むことが可能である。
【００１９】
ネットワーキング環境は、事務所、企業広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、イントラネット、およびインターネットを含むことが可能である。一例では、コンピュータ１００は、そこからデータが移動されている送信元機械であってよく、遠隔コンピュータは、宛先機械を備えてよく、またはその逆であってもよい。送信元ソース機械および宛先機械は、ネットワーク１０８または任意の他の手段によって接続できず、代わりに、データは、送信元プラットフォームによって書き込まれて、１つまたは複数の宛先プラットフォームによって読み取られることが可能な任意の媒体を経由して移動可能である。ＬＡＮまたはＷＬＡＮのネットワーキング環境では、コンピュータ１００は、ネットワークインターフェース１９６もしくはアダプタを介して、ＬＡＮまたはＷＡＮに接続可能である。ＷＡＮネットワーキング環境では、コンピュータ１００は、モデム、またはインターネットもしくはネットワーク１０８など、ＷＡＮ上で通信を確立するためのその他の手段を含むことが可能である。コンピュータ同士の間で通信リンクを確立するその他の手段を使用することも可能である。
【００２０】
コンピュータ周辺装置は、システムバスを介してコンピュータ１００のプロセッサ１１０およびメモリ１２０に結合された任意のデバイスを含むことが可能である。コンピュータ周辺装置は、ディスプレイ２０２、プリンタ、またはスピーカを含む出力周辺インターフェースと、ドライブ１３０と、キーボード、マウス、およびマイクロフォンなどのユーザ入力デバイス１９０と、ネットワークインターフェース１９６とに接続された任意のデバイスを含むことが可能である。コンピュータ周辺装置の構成要素は、電力を使用することが可能であり、スピーカ、発光ダイオードなどの照明要素、またはディスプレイに照明を提供するために使用されるバックライト、ＬＣＤ、ＬＥＤ、ＯＬＥＯ、ＣＲＴ、もしくはプラズマディスプレイなどのディスプレイ要素、または中央処理装置（ＣＰＵ）、グラフィック処理ユニット（ＧＰＵ）、メモリなどの半導体チップなど、任意のデバイスであってよい、コンピュータ周辺装置内の任意のデバイスを含むことが可能である。
【００２１】
図２は、本開示の少なくともいくつかの実施形態に従ってオペレーティングシステムによって実行されているアプリケーションプログラムを例示する。図２に示されるように、オペレーティングシステム１４０は、ドライブ１３０からアプリケーションプログラム１５０を実行することができる。オペレーティングシステム１４０および／またはアプリケーションプログラム１５０は、例えば、コンピュータ１００に図４に指定された機能および／または動作を実行させるためのプログラム命令を含むことが可能である。アプリケーションプログラム１５０は、マイクロプロセッサ１１１内のオペレーティングシステム１４０によって実行可能な任意のアプリケーション、プログラム、プログラムの部分、またはスレッドであってよい。アプリケーションプログラム１５０は、メモリコントローラ２１０を使用して、データ２３０をメモリ１２０内にロードすることが可能であり、メモリ１２０からデータ２３０にアクセスする。アプリケーションプログラム１５０は、１つまたは複数の要求２２６を使用して、メモリ１２０のメモリバンク１２２内にデータ２３０をロードし、メモリ１２０のメモリバンク１２２からデータ２３０にアクセスするなどのタスクを達成するために、スレッド２２０と呼ばれる複数のサブアプリケーションを実行することが可能である。スレッド２２０は、アプリケーションプログラム１５０によって実行可能である。アプリケーションプログラム１５０は、タスクの実行を、アプリケーションプログラムがそのタスクを達成するために必要と見なすだけの数のスレッド２２０に分割することが可能である。例えば、アプリケーションプログラム１５０が複数のページを有する文書を用いたワード処理プログラムであり、アプリケーションプログラム１５０がその文書のそれぞれのページのスペルチェックのタスクを達成するように構成され得る場合、アプリケーションプログラム１５０は、それぞれのスレッド２２０がその文書の一部をスペルチェックできるように、文書のスペルチェックのタスクを複数のスレッド２２０に分割することが可能である。それぞれのスレッド２２０は、実行のためにマルチプロセッサ１１１に送信可能である。マルチプロセッサ１１１内で実行されたとき、それぞれのスレッド２２０は、メモリ１２０内でデータ２３０に関する要求２２６を作成することが可能である。要求２２６は、効率的に動作するようにマルチプロセッサ１１１を構成することができるように要求２２６を組織できるメモリコントローラ２１０に送信可能である。
【００２２】
いくつかの実施形態では、図２に示されるように、マルチプロセッサ１１１は、２つ以上のスレッド２２０を同時に実行できるプロセッサを含むことが可能である。マルチプロセッサ１１１は、コア４１２および５１２として知られる複数のプロセッサを含むことが可能であり、またはマルチスレッドプロセッサとしても知られている、複数のスレッド２２０を同時に実行できる単一のプロセッサ（４１２もしくは５１２のうちの１つだけ）を含むことも可能である。図２は、２つのコア４１２および５１２を含む例示的なマルチプロセッサ１１１を示すが、任意の特定数のコアに限定されない。「コア」という用語は、本明細書において、単一のスレッドを処理することが可能であり、単一のスレッドを処理できるプロセッサまたはプロセッサ内の部分を指す場合がある任意のデバイスを指すために使用される場合がある。マルチスレッドプロセッサは、複数のコアを有するプロセッサと呼ばれる場合がある。複数のプロセッサを有するコンピュータ１００は、本明細書において、複数のコアを有するコンピュータ１００と呼ばれる場合がある。
【００２３】
図３は、本開示の少なくともいくつかの実施形態に従って、メモリコントローラに送信される要求を発行できるスレッドに分割されているアプリケーションプログラムの概略図を示す。図３に示されるように、アプリケーション１５０は、複数のスレッド２２０ａ〜２２０ｎに分割可能であり、この場合、ｎはスレッド２２０の数を表すことが可能であり、それぞれのスレッドは、アプリケーション１５０に関するタスクを実行することが可能であり、例えば、図２のマルチプロセッサ１１１上で実行可能である。このマルチプロセッサは、アプリケーションプログラム１５０から複数のスレッド２２０ａ〜２２０ｎを個々にまたは同時に受信および実行するように構成され得る。マルチプロセッサ上で実行されるそれぞれのスレッド２２０は、それぞれの他のスレッド２２０から独立して実行可能であり、メモリ１２０内に格納されたデータ２３０に関して複数の要求２２６ａ１〜２２６ｎｏ
を発行することが可能であり、この場合、第１の指数（ａ．．．ｎ）は、要求２２６に関連するスレッド２２０を表し、第２の指数（１．．．ｏ）は、特定のスレッド２２０に関連する要求２２６の数を表す。
【００２４】
それぞれのスレッド２２０は、メモリ１２０内に格納されたデータ２３０に関する要求２２６を発行することが可能であり、一例では、メモリ１２０内のメモリバンク１２２ａ〜１２２ｍ内に格納されたデータ２３０に関する要求２２６を発行することが可能であり、この場合、指数（ａ、ｂ．．．ｍ）は、メモリバンク１２２の数を表すことが可能である。メモリ１２０は、異なるメモリバンクからデータ２３０を追求する場合、複数の未解決のメモリ要求２２６が並列して処理されることを可能にし得る複数のメモリバンク１２２ａから１２２ｍを含むことが可能である。結果として、第１のメモリバンク１２２ａおよび第２のメモリバンク１２２ｂは、データ２３０に関する要求２２６の受信時に、メモリコントローラ２１０によって同時にアクセスされ得る。
【００２５】
それぞれのメモリバンク１２２は、指数（１．．．ｉ）が列の数を表すことが可能な列Ｃ１からＣｉと、指数（１．．．ｊ）が行の数を表すことが可能な行Ｒ１からＲｉとを含む二次元アレイであってよい。行は、連続的なメモリ位置内にデータを格納することが可能であり、例えば、およそ１〜２キロバイト（ＫＢ）のサイズであってよい。メモリバンク１２２内のデータ２３０は、最大で１行を含み得る行バッファＲＢからアクセス可能である。一例では、それぞれのメモリバンク１２２は、１つの行バッファＲＢを含むことが可能である。メモリバンク１２２がデータ２３０に関するそれぞれの要求２２６にサービス提供するためにかかる時間は、それぞれの行バッファＲＢの状態に依存する可能性があり、３つの範疇のうちの１つに該当し得る。第１の範疇は、行ヒット（ｒｏｗ−ｈｉｔ）であってよく、この場合、要求２２６は、それぞれの行バッファＲＢ内で現在開放され、メモリコントローラ２１０がそれぞれのメモリバンク１２２に対する読取りコマンドまたは書込みコマンドだけを発行することを可能にし、結果として、ｔＣＬのバンクアクセスレイテンシをもたらし得る行に対する可能性がある。
【００２６】
第２の範疇は、行閉鎖（ｒｏｗ  ｃｌｏｓｅｄ）であってよく、この場合、行バッファＲＢ内には開放された行が存在しない可能性があり、その結果、メモリコントローラ２１０は、まず要求される行を開放するための起動コマンドを発行し、次いで、読取り／書込みコマンドを発行し、結果として、ｔＲＣＤ＋ｔＣＬの総レイテンシをもたらす必要があり、式中、ｔＲＣＤは起動コマンドに関するレイテンシであり、ｔＣＬは読取り／書込みコマンドに関するレイテンシである。第３の範疇は、行衝突（ｒｏｗ  ｃｏｎｆｌｉｃｔ）であってよく、この場合、要求２２６は、それぞれの行バッファＲＢ内の現在の行とは異なる行に対する可能性があり、その結果、メモリコントローラ２１０は、まずプリチャージ（ｐｒｅｃｈａｒｇｅ）コマンドを発行して、（必要とされる行をアクティブ化することによって）必要とされる行を開放し、必要とされる行内のデータに関して読取り／書込みコマンドを発行する必要がある。これらのアクセスは、ｔＲＰ＋ｔＲＣＤ＋ｔＣＬの最高総レイテンシを負う可能性があり、式中、ｔＲＰは（行を閉鎖するための）行プリチャージに関するレイテンシであり、ｔＲＣＤは起動コマンドに関するレイテンシであり、ｔＣＬは読取り／書込みコマンドに関するレイテンシである。
【００２７】
メモリコントローラ２１０は、メモリ１２０およびマルチプロセッサと通信している形で構成可能であり、マルチプロセッサ内を含めて、システムに沿ってどこに配置されてもよい。メモリコントローラ２１０は、要求２２６がサービス提供されるのを待っている可能性がある間、要求２２６およびデータ２３０にバッファリングするように構成可能なメモリ要求バッファ２１１を含むことが可能である。メモリコントローラ２１０は、サービス提供されることになる次の要求２２６を選択するように構成可能な要求スケジューラ２１２を含むことが可能である。いくつかの実施形態では、要求スケジューラ２１２は２つのレベルを有し得る。サービス提供されることになる次の要求２２６を選択するとき、要求スケジューラ２１２は、メモリバンク１２２ａ〜１２２ｍの状態と、メモリコントローラ２１０をそれぞれのメモリバンク１２２に接続しているメモリバス２１４ａ〜２１４ｍの状態と、要求２２６の状態とを考慮するように構成可能である。要求２２６に関するメモリコマンドは、そのスケジューリングが、メモリバンク１２２ａ〜１２２ｍ、およびアドレス／データ／システムバスなど、いかなるリソース衝突も引き起こさず、いかなるメモリタイミング制約にも違反しない場合、要求スケジューラ２１２によってスケジュールされ得る。いかなる衝突も引き起こさないメモリコマンドは、準備ができていると見なすことができる。
【００２８】
メモリコントローラ２１０は、要求バッチ処理アルゴリズムを有する要求スケジューリングアルゴリズム、およびバッチ内要求スケジューリングアルゴリズムまたはバッチ内要求並列処理認識スケジューリングアルゴリズムを含む要求スケジューラ２１２を含む。あるいは、バッチ内要求スケジューリングアルゴリズムおよびバッチ内要求並列処理認識スケジューリングアルゴリズムの両方が要求スケジューリングアルゴリズムによって用いられることも可能である。
【００２９】
図３Ａは、スレッドバッチアルゴリズム３０２およびバッチ内スレッドスケジューリングアルゴリズムまたはバッチ内スレッド並列処理認識スケジューリングアルゴリズム３５０を含むスレッドスケジューリングアルゴリズム３００の一部を示すオペレーティングシステム１４０の詳細図を含む。アプリケーションプログラムは、スレッドスケジューリングアルゴリズムを含むことが可能である。あるいは、バッチ内スレッドスケジューリングアルゴリズムおよびバッチ内スレッド並列処理認識スケジューリングアルゴリズムの両方がスレッドスケジューリングアルゴリズムによって用いられることも可能である。
【００３０】
図３を再び参照すると、スレッド２２０ａ〜２２０ｎから要求２２６ａ１〜２２６ｎｏをスケジューリングする効率性を改善するために、メモリコントローラ２１０、および特に要求スケジューラ２１２は、スレッド内バンク並列処理を考慮に入れることが可能な要求スケジューリングアルゴリズムを使用することが可能であり、それぞれのスレッド２２０ａ〜２２０ｎにサービスの質（ＱｏＳ）を提供することが可能である。サービスの質は、異なるスレッド２２０ａ〜２２０ｎに異なる優先順位を提供するための能力、および／またはスレッド２２０ａ〜２２０ｎを実行するときに基礎パフォーマンスレベルを提供するための能力と見なすことができる。要求スケジューリングアルゴリズムは、公平性、およびＱｏＳ、ならびに高いＣＭＰシステムスループットに関して構成可能な基板を提供するように設計可能である。要求バッチ処理アルゴリズムは、いくつかの未解決のメモリ要求２２６ａ１〜２２６ｎｏをバッチにグループ化するように構成可能である。要求スケジューリングアルゴリズムは、次のバッチが形成される前に、現在のバッチに属するすべての要求２２６ａ１〜２２６ｎｏがサービス提供されることを確実にするように構成されることも可能である。要求バッチ処理アルゴリズムは、複数のバッチをすべて同時に形成するように適合可能であり、この場合、それぞれのバッチは、本明細書で説明される一定の基準を使用して形成され得る。
【００３１】
要求バッチ処理アルゴリズムは、メモリ要求バッファ内の未解決の要求を要求バッチと呼ばれる要求のセットにグループ化するように構成可能である。メモリスケジューラは、現在の要求バッチに属している要求をその他の要求に勝って優先順位付けすることによって、要求バッチの全域で要求を再順序付けすることを回避できる。要求バッチのすべての要求がサービス提供されると、例えば、その要求バッチが仕上がったとき、最後の要求バッチ内に含まれていなかった、メモリ要求バッファ内の未解決の要求を含み得る次の要求バッチが次いでサービス提供され得る。複数の要求バッチを同時に形成することは、要求バッチ内の要求を再順序付けすることを可能にできる。
【００３２】
要求バッチ処理アルゴリズムは、以下のように作用することが可能である。メモリ要求バッファ内のそれぞれの要求は、その要求が現在の要求バッチ内のどの要求バッチに属すかを表示する関連するビットを有し得る。要求が第１の要求バッチに属する場合、例えば、関連するビットは、その要求が第１の要求バッチに属すことを表示するように設定可能であり、その要求はマーキングされたと見なすことができる。複数の要求バッチを形成することが可能であり、その場合、それらの要求のそれぞれは、本明細書で説明される一定の基準に基づいて、それらの要求がそれらの複数の要求バッチのうちのどの中に配置されることになるか、またはそれらの要求がそれらの複数の要求バッチのうちのどの一部であるかを表示するためにマーキングされる。メモリ要求バッファ内にマーキングされた要求が残されていないとき、例えば、これまでの要求バッチからのすべての要求が完全にサービス提供されているとき、新しい要求バッチを形成することが可能である。
【００３３】
いくつかの実施形態では、要求バッチを形成するとき、要求バッチ処理アルゴリズムは、それぞれのスレッドに関するメモリバンクごとに未解決の要求のセット番号、すなわち、マーキングキャップ（ｍａｒｋｉｎｇ−ｃａｐ）をマークアップすることが可能であり、これらの要求は要求バッチを形成することができる。このマーキングキャップは、あるバンクに関してスレッドによって発行されたいくつの要求が要求バッチの一部であってよいかを制限できるシステムパラメータとして利用可能である。例えば、このマーキングキャップが５であり、スレッドがメモリバンクに関して７個の未解決の要求を有する場合、要求バッチ処理アルゴリズムは、５個の（または、５個に満たない要求が存在する場合、より少ない）最も古い要求をマーキングすることが可能である。例は、２、３、５、７、１０、２０、５０、またはより大きなマーキングキャップすら含む。さらに、本明細書で説明されるように、これらのマーキングキャップは、異なるタイプのバッチによって異なってよい。いくつかの例では、マーキングキャップが設定されていない場合、１つまたは複数のバッチが形成されるとき、すべての未解決の要求をマーキングすることが可能である。
【００３４】
要求バッチ処理アルゴリズムは、マーキングされた要求（バッチの形の要求）を所与のメモリバンク内のマーキングされていない要求に勝って優先順位付けするように構成可能である。所与のバンクに対してマーキングされた要求が存在しない場合、未解決のマーキングされていない要求をそのバンクに対してスケジューリングすることができる。２つのマーキングされた要求または２つのマーキングされていない要求の間で選択するために、ＦＲ−ＦＣＦＳなど、任意の既存のメモリスケジューリングアルゴリズムまたは新しいメモリスケジューリングアルゴリズムを用いることが可能である。
【００３５】
それぞれの要求バッチが１つまたは複数の要求を含む、スレッド要求の１つまたは複数のバッチを形成するための要求スケジューリング方法を開始することが可能である。この方法を開始した後で、スレッドを、次いで、スレッドタイプ、例えば、第１のスレッドタイプおよび第２のスレッドタイプ、または、第１のスレッドタイプ、第２のスレッドタイプ、および第３のスレッドタイプに分離（それらのスレッドタイプとして識別）することが可能である。それぞれが１つもしくは複数の類似のまたは同じスレッドタイプの１つもしくは複数のスレッドから発行された要求を含み得る、１つもしくは複数の要求バッチを形成することが可能である。それぞれが１つまたは複数の要求を含む、１つまたは複数の要求バッチを形成した後で、その１つまたは複数の要求バッチは、次いで、メモリコントローラによって実行可能である。その１つもしくは複数の要求バッチは一度に１回実行可能であり、またはコンピュータシステムに能力がある場合、その１つもしくは複数の要求バッチは一度に２回以上実行可能である。
【００３６】
スレッドの分離（識別）、したがって、異なるスレッドタイプからの要求のバッチ処理は、いくつかの異なる基準のうちのいずれかに基づいてよい。例えば、スレッドは以下に分離可能である。すなわち、（１）それらのスレッドが、並列メモリと共に使用するために、どのくらい良好に設計されているかに基づいて、良好な設計スレッドおよび不良な設計スレッド、（２）それらのスレッドがそれらのスレッドがその他のスレッドとどのくらい効果的に共働するかに基づいて、協調スレッドおよび非協調スレッド、（３）そのスレッドが発生したアプリケーションプログラムに基づいて、第１のアプリケーションスレッド、第２のアプリケーションスレッド、および第３のアプリケーションスレッド、（４）それらのスレッドが行う要求の相対数に基づいて、大規模要求スレッド、任意選択で、中規模要求スレッドおよび小規模要求スレッド、例えば、大規模要求スレッドは、平均数以上の要求を行うことが可能であり、小規模要求スレッドは、平均数未満のいくつかの要求を行うことが可能であること、である。多くのその他の改変形態が可能である。したがって、選択される基準に応じて、第１のスレッドタイプ、第２のスレッドタイプ、任意選択の第３のスレッドタイプ、任意選択の第４のスレッドタイプなどが存在し得る。
【００３７】
以下は、結果として、２つのスレッドタイプをもたらし得る、ある基準を使用した一例であり、上述のように、選択される基準に応じて、３つ以上のスレッドタイプも可能である。これらのスレッドは、第１のスレッドタイプおよび第２のスレッドタイプに分離可能である。それぞれのスレッドタイプによって発行された要求、例えば、第１のスレッドタイプから発行された第１の要求、および第２のスレッドタイプから発行された第２の要求は、次いで、スレッド要求の１つまたは複数のバッチに形成され得る。それぞれの要求バッチは、１つのスレッドタイプの要求を含むことが可能であり、例えば、第１の要求バッチは、第１の要求だけを含むことが可能であり、最後の要求バッチは、第２の要求を含むことが可能である。もう１つの例では、それぞれの要求バッチは、第１のスレッドタイプからの第１の要求を主に含むことが可能であるか、または第２のスレッドタイプからの第２の要求を主に含むことが可能である。このように、形成された要求バッチは、それぞれのスレッドタイプからの要求に関して均一であってよく、または主に均一であってもよい。この１つもしくは複数の要求バッチは一度に１回実行可能であり、またはコンピュータシステムに能力がある場合、その１つもしくは複数の要求バッチは一度に２回以上実行可能である。本明細書で使用される場合、主にという用語は、約５０％超、および約８０％超、約９５％超であってよく、または約９９％超であってもよい。
【００３８】
１つまたは複数の要求バッチが形成されると、要求スケジューリングアルゴリズムは、要求バッチ内の要求のサービスをスケジューリングするために、バッチ内要求スケジューリングアルゴリズムまたはバッチ内要求並列処理認識スケジューリングアルゴリズムを用いるように構成可能である。ＦＲ−ＦＣＦＳなど、任意のバッチ内要求スケジューリングアルゴリズムを使用することが可能である。
【００３９】
要求バッチ内で、バッチ内要求並列処理認識スケジューリングアルゴリズムは、第１に行ヒット要求を優先順位付けするように構成可能である。第２に、本明細書に詳しく説明されるように、バンクレベルの並列処理を高めるために、より高いランクを有するスレッドからの要求をより低いランクを有するスレッドからの要求に勝って優先順位付けすることが可能である。最終的に、他に特別な条件がない限り、より古い要求をより新しい要求に勝って優先順位付けすることが可能である。
【００４０】
バッチ内要求並列処理認識スケジューリングアルゴリズムは、要求バッチ内のランクベースのスレッド優先順位付け方式を使用することが可能である。新しい要求バッチが形成されるとき、メモリスケジューラは、新しい要求バッチ内に要求を有するすべてのスレッド間のランキングを計算するように構成可能である。新しい要求バッチが処理される間、計算されたランキングは同じ状態にとどまることが可能であり、より高くランク付けされたスレッドからの要求をより低くランク付けされたスレッドからの要求に勝って優先順位付けすることが可能である。ランキングベースのスケジューリングの効果は、すべてのメモリバンクの全域で異なるスレッドを同じ順序で優先順位付けすることが可能であり、したがって、それぞれのスレッドの要求がすべてのバンクによって並列してサービス提供される可能性がより高いことである。
【００４１】
任意のランキングベースの方式が使用可能であるが、特定のランキング手順は、ＣＭＰスループットおよび公平性に対してかなりの影響を有する場合がある。良好なランキング方式は、メモリ集約型スレッドとメモリ非集約型スレッド（および、高いバンク並列処理を伴うスレッド）とを効果的に区別することが可能である。いくつかの実装形態では、最短ジョブ優先原理に適合するランキング方式を用いることが可能であり、この方式は、非集約型スレッドを集約型スレッドより高くランキングできる。
【００４２】
図３および図３Ａを再び参照すると、アプリケーションプログラム１５０またはオペレーティングシステム１４０からスレッド２２０ａ〜２２０ｎをスケジューリングする効率性を改善するために、アプリケーションプログラム１５０またはオペレーティングシステム１４０は、スレッドをスレッドバッチにグループ化するように構成可能である。スレッドバッチ処理アルゴリズム３０２は、いくつかの未解決のスレッド２２０ａ〜２２０ｎをグループ化してスレッドバッチにするように構成可能である。スレッドスケジューリングアルゴリズム３００は、次のスレッドバッチが形成される前に、現在のスレッドバッチに属しているスレッド２２０ａ〜２２０ｎがサービス提供され得ることを確実にするように構成されることも可能である。スレッドバッチ処理アルゴリズム３０２は、複数のスレッドバッチを同時に形成するように構成可能であり、この場合、それぞれのスレッドバッチは、本明細書で説明されるように、一定の基準を使用して形成可能である。
【００４３】
スレッドバッチ処理アルゴリズムは、未解決のスレッドをバッチと呼ばれるスレッドのセットにグループ化するように構成可能である。アプリケーションプログラムまたはオペレーティングシステムは、現在のスレッドバッチに属しているスレッドをその他のスレッドに勝って優先順位付けすることによって、スレッドバッチの全域でスレッドを再順序付けすることを回避できる。スレッドバッチのスレッドがサービス提供されると、例えば、スレッドバッチが仕上がったとき、最後のスレッドバッチ内に含まれていなかった未解決のスレッドを含み得る次のスレッドバッチが次いでサービス提供され得る。複数のスレッドバッチを同時に形成することは、スレッドバッチ内でスレッドを再順序付けすることを可能にし得る。
【００４４】
１つの例示的なスレッドバッチ処理アルゴリズムは以下のように作用することが可能である。それぞれのスレッドは、そのスレッドが現在のスレッドバッチ内のどのスレッドバッチに属すかを表示する関連するビットを有し得る。スレッドが第１のスレッドバッチに属する場合、例えば、関連するビットは、そのスレッドが第１のスレッドバッチに属すことを表示するように設定可能であり、そのスレッドはマーキングされたと見なすことができる。複数のスレッドバッチを形成することが可能であり、この場合、それらのスレッドのそれぞれは、本明細書で説明される一定の準に基づいて、それらのスレッドがそれらの複数のスレッドバッチのうちのどのスレッドバッチ内に配置されることになるか、またはそれらのスレッドがそれらの複数のスレッドバッチのうちのどのスレッドバッチの一部であるかを表示するためにマーキング可能である。マーキングされたスレッドが残されていないとき、例えば、これまでのスレッドバッチからのすべてのスレッドが完全にサービス提供されているとき、新しいスレッドバッチを形成することが可能である。
【００４５】
いくつかの実施形態では、スレッドバッチを形成するとき、スレッドバッチ処理アルゴリズムは、それぞれのアプリケーションプログラムに関するコアごとに未解決のスレッドのセット番号、すなわち、マーキングキャップをマークアップするように構成可能であり、これらのスレッドは、スレッドバッチを形成することができる。このマーキングキャップは、一定のコアに関してアプリケーションプログラムによって発行されたいくつのスレッドがスレッドバッチの一部であってよいかを制限できるシステムパラメータとして利用可能である。例えば、このマーキングキャップが５であり、アプリケーションプログラムが７個の未解決のスレッドを有する場合、スレッドバッチ処理アルゴリズムは、５個の（または、５個に満たないスレッドが存在する場合、より少ない）最も古いスレッドをマーキングすることができる。例は、２、３、５、７、１０、２０、５０、またはより大きなマーキングキャップすら含む。さらに、本明細書で説明されるように、これらのマーキングキャップは、異なるタイプのバッチによって異なってよい。マーキングキャップが設定されていない場合、１つまたは複数のスレッドバッチが形成されるとき、未解決のスレッドをマーキングすることが可能である。
【００４６】
スレッドバッチ処理アルゴリズムは、マーキングされたスレッド（バッチの形のスレッド）をマーキングされていないスレッドに勝って優先順位付けするように構成可能である。マーキングされたスレッドが存在しない場合、未解決のマーキングされていないスレッドをスケジューリングすることができる。２つのマーキングされたスレッドまたは２つのマーキングされていないスレッドの間で選択するために、任意の既存のスレッドスケジューリングアルゴリズムまたは新しいスレッドスケジューリングアルゴリズムを用いることが可能である。
【００４７】
図４は、本開示の少なくともいくつかの実施形態に従って構成された方法、装置（システム）、およびコンピュータプログラム製品の流れ図である。図４の流れ図のそれぞれのブロック、および図４の流れ図のブロックの組合せは、コンピュータプログラム命令によって実装可能である点を理解されよう。これらのコンピュータプログラム命令は、コンピュータ上、もしくはプロセッサ上、または他のプログラマブルデータ処理装置上で実行する命令が流れ図の１つまたは複数のブロック内で指定される機能を実装するための手段を作成するように、コンピュータ上、もしくはプロセッサ上、または他のプログラマブルデータ処理装置上にロード可能である。これらのコンピュータプログラム命令は、記憶デバイス内に格納された命令が、流れ図の１つもしくは複数のブロック内で指定された機能および／または動作を実装できる命令手段を含む製品を作成するように、コンピュータ、もしくはプロセッサ、または他のプログラマブルデータ処理装置が特定の様式で機能あるいは動作するように指令できる記憶デバイス内に格納されることも可能である。これらのコンピュータプログラム命令は、コンピュータ上で、もしくはプロセッサ上で、または他のプログラマブル装置上で実行する命令が流れ図の１つもしくは複数のブロック内で指定された機能および／または動作を実装するためのステップを提供するようにコンピュータ実装プロセスを作成するように、コンピュータ上で、もしくはプロセッサ上で、または他のプログラマブルデータ処理装置上で一連の動作ステップを実行させるために、コンピュータ上、もしくはプロセッサ上、または他のプログラマブルデータ処理装置上にロードされることも可能である。
【００４８】
したがって、図４の流れ図のブロックは、指定された機能を実行するための手段の組合せ、指定された機能を実行するためのステップの組合せ、ならびに指定された機能および／または動作を実行するためのプログラム命令手段をサポートする。図４の流れ図のそれぞれのブロック、および図４の流れ図内のブロックの組合せは、指定された機能／動作／活動もしくはステップ、または専用ハードウェアおよびコンピュータ命令の組合せを実行する専用ハードウェアベースのコンピュータシステムによって実装可能である点も理解されよう。
【００４９】
かかるコンピュータ命令は、コンピュータ可読媒体（例えば、ディスケット、ＣＤ−ＲＯＭ、ＲＯＭ、もしくは固定ディスク）などの有形媒体上に固定されてよく、またはモデム、もしくは媒体上でネットワークに接続された通信アダプタなど、その他のインターフェースデバイスを経由して、コンピュータシステムに転送可能であってもよい。この媒体は、有形媒体（例えば、光通信線もしくはアナログ通信線）または無線技術（例えば、マイクロ波、赤外線伝送技術もしくはその他の伝送技術）を用いて実装された媒体であってよい。一連のコンピュータ命令は、このシステムに関して本明細書でこれまで説明された機能性のすべてまたは一部を実施する。
【００５０】
当業者は、かかるコンピュータ命令は、多くのコンピュータアーキテクチャまたはオペレーティングシステムと共に使用するために、いくつかのプログラミング言語で書込み可能である点を理解されたい。さらに、かかる命令は、半導体、磁気メモリデバイス、光メモリデバイス、またはその他のメモリデバイスなど、任意のメモリデバイス内に格納可能であり、光伝送技術、赤外線伝送技術、マイクロ波伝送技術、またはその他の伝送技術など、任意の通信技術を使用して送信可能である。かかるコンピュータプログラム製品は、コンピュータシステムを用いて（例えば、システムＲＯＭ上もしくは固定ディスク上に）事前にロードされた、印刷文書もしくは電子文書を伴う取出し可能媒体（例えば、シュリンクラップソフトウェア）として供給可能であるか、あるいはネットワーク上でサーバまたは電子掲示板（例えば、インターネットもしくはワールドワイドウェブ）から供給可能であることが予想される。
【００５１】
図４に示されるように、それぞれのスレッドバッチが１つまたは複数のスレッドを含む、スレッドの１つまたは複数のバッチを形成するための方法６００を、ブロック６０１で開始することが可能である。方法６００を開始した後で、次いで、ブロック６０２において、スレッドを、スレッドタイプ、例えば、第１のスレッドタイプおよび第２のスレッドタイプ、または第１のスレッドタイプ、第２のスレッドタイプ、および第３のスレッドタイプに分離（それらのスレッドタイプとして識別）することが可能である。ブロック６０４において、それぞれのスレッドバッチは、類似または同じ１つもしくは複数のタイプのスレッドを有する、アプリケーションプログラムまたはオペレーティングシステムから発行されたスレッドを含み得る、１つまたは複数のスレッドバッチを形成することが可能である。それぞれのスレッドバッチが１つまたは複数のスレッドを含む状態で、１つまたは複数のスレッドバッチを形成した後で、次いで、ブロック６０６において、１つまたは複数のスレッドバッチをコアによって実行することが可能である。１つもしくは複数のスレッドバッチは一度に１回実行可能であり、またはコンピュータシステムに能力がある場合、その１つもしくは複数の要求バッチは一度に２回以上実行可能である。
【００５２】
スレッドの分離（識別）、および、したがって、異なるスレッドタイプのスレッドのバッチ処理は、いくつかの異なる基準のうちのいずれかに基づいてよい。例えば、スレッドは、以下に分離可能である。（１）それらのスレッドが、並列メモリと共に使用するために、どのくらい良好に設計されているかに基づいて、良好な設計スレッドおよび不良な設計スレッド、（２）それらのスレッドがその他のスレッドとどのくらい効果的に共働するかに基づいて、協調スレッドおよび非協調スレッド、（３）そのスレッドが発生したアプリケーションプログラムに基づいて、第１のアプリケーションスレッド、第２のアプリケーションスレッド、および第３のアプリケーションスレッド、（４）それらのスレッドが行う要求の相対数に基づいて、大規模要求スレッド、任意選択で、中規模要求スレッドおよび小規模要求スレッド、例えば、大規模要求スレッドは、平均数以上の要求を行うことが可能であり、小規模要求スレッドは、平均数未満のいくつかの要求を行うことが可能であること、である。スレッドをバッチにグループ化するためのその他の基準は、それぞれのスレッドに重要度、例えば、高い重要度もしくは低い重要度を割り当てること、または重要度値を割り当てて、類似の重要度値もしくは同じ重要度値を有するスレッドを共にバッチ処理することを含むことが可能である。スレッドをバッチにグループ化するためのさらにその他の基準は、それぞれのスレッドに関連するゴーストページ内に格納されたデータを用いて、これまでそれらのスレッドを実行したときに収集された過去の互換性データに基づいてグループ化することを含むことが可能であり、または当該データは、そこからそのスレッドが発行されたアプリケーションプログラムの一部として提供されたフリーズドライゴーストページ内に格納可能であり、このフリーズドライゴーストページは、そのアプリケーションプログラムを用いて提供されたスレッドの互換性データを含む。多くの他の改変形態が可能である。したがって、選択される基準に応じて、第１のスレッドタイプ、第２のスレッドタイプ、任意選択の第３のスレッドタイプ、任意選択の第４のスレッドタイプなどが存在し得る。
【００５３】
図５は、本開示の少なくともいくつかの実施形態に従ってスレッドバッチの形で構成されているスレッドの概略図を示す。例示されるのは、結果として、２つのスレッドタイプをもたらす基準を使用した一例であり、上述のように、選択される基準に応じて、３つ以上のスレッドタイプも可能である。スレッド２２０ａ〜２２０ｎは、第１のスレッドタイプ２５０および第２のスレッドタイプ２５１に分離可能である。それぞれのアプリケーションプログラムまたはオペレーティングシステムによって発行されたスレッド、例えば、第１のスレッドタイプ２５０の第１のスレッド、および第２のスレッドタイプ２５１の第２のスレッドを、次いで、スレッドの１つまたは複数のスレッドバッチ３３２ａ〜３３２ｘに形成することが可能である。それぞれのスレッドバッチは、１つだけのスレッドタイプのスレッドを含むことが可能であり、例えば、例示されるように、第１のスレッドバッチ３３２ａは、第１のスレッドタイプ２５０の第１のスレッドだけを含むことが可能であり、最後のスレッドバッチ３３２ｘは、第２のスレッドタイプ２５１の第２のスレッドだけを含むことが可能である。もう１つの例では、それぞれのスレッドバッチ３３２ａ〜３３２ｘは、第１のスレッドタイプ２５０の第１のスレッドを主に含むことが可能であり、または第２のスレッドタイプ２５１の第２のスレッドを主に含むことが可能である。このように、形成されたスレッドバッチ３３２ａ〜３３２ｘは、それぞれのスレッドタイプのスレッドに関して、均一であるか、または主に均一である。１つもしくは複数のスレッドバッチは一度に１回実行可能であり、またはコンピュータシステムに能力がある場合、その１つもしくは複数の要求バッチは一度に２回以上実行可能である。本明細書で使用される場合、主にという用語は、約５０％超、および約８０％超、約９５％超であってよく、または約９９％超であってもよい。
【００５４】
１つまたは複数のスレッドバッチが形成されると、スレッドスケジューリングアルゴリズムは、スレッドバッチ内のスレッドのサービスをスケジューリングするために、バッチ内スレッドスケジューリングアルゴリズムまたはバッチ内スレッド並列処理認識スケジューリングアルゴリズムを用いることが可能である。
【００５５】
バッチ内スレッド並列処理認識スケジューリングアルゴリズムは、スレッドバッチ内でランクベースのスレッド優先順位付け方式を使用することが可能である。新しいスレッドバッチが形成されるとき、メモリスケジューラは、新しいバッチ内のすべてのスレッド間のランキングを計算するように構成可能である。新しいバッチが処理される間、計算されたランキングは同じ状態にとどまることが可能であり、より高くランク付けされたスレッドをより低くランク付けされたスレッドに勝って優先順位付けすることが可能である。
【００５６】
任意のランキングベースの方式が使用可能であるが、特定のランキング手順は、かなりの影響を有する場合がある。良好なランキング方式は、計算集約型スレッドと非計算集約型スレッド（および、高いバンク並列処理を伴うスレッド）を効果的に区別することが可能である。いくつかの実装形態では、ランキング方式は、最短ジョブ優先原理に適合するランキング方式を用いることが可能であり、この方式は、より迅速に実行するスレッドを、より遅く実行するスレッドよりもより高くランキングすることが可能である。
【００５７】
特許請求される主題は、範囲の点で、本明細書で説明される特定の実装形態に限定されない。例えば、いくつかの実装形態は、あるデバイス上またはデバイスの組合せ上で動作するために用いられるようなハードウェアの形であってよく、例えば、一方、その他の実装形態は、ソフトウェアおよび／またはファームウェアの形であってよい。同様に、特許請求される主題は、この点において範囲の点で限定されないが、いくつかの実装形態は、１つまたは複数の記憶媒体など、１つまたは複数の物品を含むことが可能である。ＣＤ−ＲＯＭ、コンピュータディスク、フラッシュメモリなど、この記憶媒体は、例えば、コンピュータシステム、コンピューティングプラットフォーム、またはその他のシステムなど、システムによって実行されるとき、結果として、例えば、これまで説明された実装形態のうちの１つなど、特許請求される主題に従ってプロセッサの実行をもたらし得る命令を格納していることが可能である。１つの可能性として、コンピューティングプラットフォームは、１つもしくは複数の処理ユニットまたはプロセッサと、ディスプレイ、キーボードおよび／またはマウスなど、１つもしくは複数の入出力デバイスと、静的ランダムアクセスメモリ、動的ランダムアクセスメモリ、フラッシュメモリ、および／またはハードドライブなど、１つもしくは複数のメモリとを含むことが可能である。
【００５８】
明細書における「ある実装形態」、「一実装形態」、「いくつかの実装形態」、または「その他の実装形態」の参照は、１つもしくは複数の実装形態に関して説明される特定の特徴、構造、または特性は少なくともいくつかの実装形態内に含まれ得るが、すべての実装形態内に含まれるとは限らないことを意味する場合がある。先の説明における「ある実装形態」、「一実装形態」、「いくつかの実装形態」の様々な出現は、すべて同じ実装形態を参照するとは限らない。さらに、「結合された」または「反応する」もしくは「に反応して」、あるいは「と通信している」などの用語または句が、本明細書または続く特許請求の範囲において使用される場合、これらの用語は広く解釈されるべきである。例えば、「に結合された」という句は、その句が使用される文脈に応じて適切に、通信可能に、電気的に、および／または動作可能に結合されていることを指す場合がある。
【００５９】
先の説明において、特許請求される主題の様々な態様が説明されている。説明のために、特定の番号、システム、および／または構成は、特許請求される主題の十分な理解をもたらすために記載された。しかし、当業者および本開示の利益を有する者は、特許請求される主題は、それらの特定の詳細なしに実行可能である点を理解されたい。その他の事例では、特許請求される主題をあいまいにしないように、よく知られている特徴は省略および／または簡素化された。本明細書において、いくつかの特徴が例示および／または説明されているが、当業者は、ここでまたは今後、多くの修正形態、代替形態、変更形態、および／または均等物を思いつくであろう。したがって、添付の特許請求の範囲は、特許請求される主題の真の趣旨に該当するすべてのかかる修正形態および／または変更形態をカバーすることが意図されることを理解されたい。
【００６０】
システムの態様のハードウェア実装形態とソフトウェア実装形態の間に差異はほとんどなく、ハードウェアの使用またはソフトウェアの使用は、一般に、費用対効果の兼ね合いを表す設計の選択である（しかし、ハードウェアとソフトウェアとの間の選択が重要になる可能性がある一定の状況では、常にそうであるとは限らない）。それによって本明細書で説明されるプロセス、および／もしくはシステム、ならびに／またはその他の技術が実現可能な様々な手段（例えば、ハードウェア、ソフトウェア、および／またはファームウェア）が存在し、好ましい手段は、それらのプロセス、および／もしくはシステム、ならびに／またはその他の技術が展開される状況によって異なることになる。例えば、実装者が、速度および精度が最重要であると決定した場合、その実装者は、ハードウェア手段および／またはファームウェア手段を主に選択することができ、柔軟性が最重要である場合、その実装者は、ソフトウェア実装形態を主に選択することができ、またはさらにこの場合も代替として、その実装者は、ハードウェア、ソフトウェア、および／またはファームウェアのいくつかの組合せを選択することができる。
【００６１】
前述の詳細な説明は、ブロック図、流れ図、および／もしくは例の使用を介したデバイスならびに／またはプロセスの様々な実施形態を記載している。かかるブロック図、流れ図、ならびに／あるいは例が１つもしくは複数の機能および／または動作を含む限り、かかるブロック図、流れ図、もしくは例の中のそれぞれの機能および／または動作は、幅広い範囲のハードウェア、ソフトウェア、ファームウェア、または実質的にそれらの任意の組合せによって、個々におよび／もしくは集合的に実装可能である点を当業者は理解されよう。一実装形態では、本明細書で説明された主題のいくつかの部分は、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、デジタル信号プロセッサ（ＤＳＰ）、またはその他の統合形式を介して実装可能である。しかし、当業者は、本明細書で開示された実施形態のうちのいくつかの態様は、全体としてまたは一部において、１つもしくは複数のコンピュータ上で実行している１つもしくは複数のコンピュータプログラム（例えば、１つもしくは複数のコンピュータシステム上で実行している１つもしくは複数プログラム）として、１つもしくは複数のプロセッサ上で実行している１つもしくは複数のプログラム（例えば、１つもしくは複数のマイクロプロセッサ上で実行している１つもしくは複数のプログラム）として、ファームウェアとして、または実質的にそれらの任意の組合せとして、集積回路内で等しく実行可能であり、回路の設計ならびに／またはソフトウェアおよび／もしくはファームウェアに関するコードの書込みは、本開示に照らして、十分当業者の能力範囲内にあることになる点を理解されよう。加えて、当業者は、本明細書で説明された主題の機構は、様々な形態のプログラム製品として供給されることが可能であり、本明細書で説明された主題の例示的な実施形態は、その供給を実際に実行するために使用される信号担持媒体の特定のタイプにかかわらず適用される点を理解されよう。信号担持媒体の例は、以下を含むが、これらに限定されない。すなわち、フロッピー（登録商標）ディスク、ハードディスクドライブ、コンパクトディスク（ＣＤ）、デジタルビデオディスク（ＤＶＤ）、デジタルテープ、コンピュータメモリなど、記録可能なタイプの媒体、ならびにデジタル通信媒体および／またはアナログ通信媒体（例えば、光ファイバーケーブル、導波管、有線通信リンク、無線通信リンクなど）など、伝送タイプの媒体である。
【００６２】
当業者は、本明細書に記載された形でデバイスおよび／またはプロセスを説明し、その後、かかる説明されたデバイスおよび／またはプロセスをデータ処理システムに統合するために技術的な手法を使用することは当技術分野において一般的である点を理解されよう。すなわち、十分な量の実験を介して、本明細書で説明されたデバイスおよび／またはプロセスの少なくとも一部をデータ処理システムに統合することが可能である。当業者は、典型的なデータ処理システムは、一般に、システムユニット筐体、ビデオディスプレイデバイス、揮発性メモリおよび不揮発性メモリなどのメモリ、マイクロプロセッサおよびデジタル信号プロセッサなどのプロセッサ、オペレーティングシステム、ドライバ、グラフィカルユーザインターフェース、およびアプリケーションプログラムなどの計算エンティティ、タッチパッドまたはスクリーンなどの１つもしくは複数の対話デバイス、ならびに／あるいはフィードバックループおよび制御モーター（例えば、位置および／または速度を感知するためのフィードバック、構成要素および／もしくは数量を移動ならびに／または調整するための制御モーター）を含む制御システムのうちの１つまたは複数を含む点を理解されよう。典型的なデータ処理システムは、一般に、データコンピューティングシステム／データ通信システムおよび／またはネットワークコンピューティングシステム／ネットワーク通信システムの内に見出される構成要素など、任意の適切な市販の構成要素を利用して実装可能である。
【００６３】
本明細書で説明される主題は、時には、異なる他の構成要素内に含まれた異なる構成要素、または異なる他の構成要素に接続された異なる構成要素を例示する。そのような示されたアーキテクチャは単なる例示であり、実際には、同じ機能性を達成する、多くのその他のアーキテクチャが実装可能である点を理解されよう。概念的な意味で、同じ機能性を達成するための構成要素のいずれの構成も、所望される機能性が達成されるように、有効に「関連付けられる」。したがって、特定の機能性を達成するために組み合わされる、本明細書のいずれの２つの構成要素も、アーキテクチャまたは中間構成要素にかかわらず、所望される機能性が達成されるように互いに「関連付けられる」と見なすことができる。同様に、そのように関連付けられたいずれの２つの構成要素も、所望される機能性を達成するために、互いに「動作可能に接続されている」または「動作可能に結合されている」と見なすこともでき、そのように関連付けられているいずれの２つの構成要素も、所望される機能性を達成するために、互いに「動作可能に結合続可能である」と見なすこともできる。動作可能に結合可能な特定の例は、物理的に噛み合わせ可能な（ｍａｔｅａｂｌｅ）構成要素および／もしくは物理的に相互作用する構成要素、ならびに／または無線で相互作用可能な構成要素および／もしくは無線で相互作用する構成要素、ならびに／または論理的に相互作用する構成要素および／もしくは論理的に相互作用可能な構成要素を含むが、これらに限定されない。
【００６４】
本明細書における実質的に任意の複数用語および／または単数用語の使用に関して、当業者は、文脈および／もしくは応用例に応じて、複数から単数にかつ／または単数から複数に変換することが可能である。分かりやすくするために、本明細書において、様々な単数／複数の置換が明示的に記載される場合がある。
【００６５】
概して、本明細書、および、特に添付の特許請求の範囲（例えば、添付の特許請求の範囲の本文）において使用される用語は、一般に、「開放的な」用語として意図される（例えば、「含んでいる」という用語は、「含むが、それに限定されない」と解釈されるべきであり、「有する」という用語は、「少なくとも含む」と解釈されるべきであり、「含む」という用語は、「含むが、それに限定されない」と解釈されるべきである、など）ことを理解されよう。当業者は、特定の数の導入される請求項の列挙が意図される場合、かかる意図は、特許請求の範囲内で明示的に列挙されることになり、かかる列挙がない場合、かかる意図は存在しない点をさらに理解されよう。例えば、理解の支援として、以下の特許請求の範囲は、請求項の列挙を導入するために、「少なくとも１つの」および「１つまたは複数の」という導入句の使用を含む場合がある。しかし、かかる句の使用は、同じ請求項が、導入句「１つもしくは複数の」または「少なくとも１つの」、ならびに「ａ」または「ａｎ」などの不定冠詞を含むときですら、不定冠詞「ａ」または「ａｎ」による請求項の列挙の導入が、そのように導入された請求項の列挙を含む任意の特定の請求項を１つのかかる列挙だけを含む発明に限定することを意味すると解釈されるべきではなく（例えば、「ａ」および／または「ａｎ」は、典型的には、「少なくとも１つの」または「１つもしくは複数の」を意味すると解釈されるべきである）、同じことは、請求項の列挙を導入するために使用される定冠詞の使用に関しても当てはまる。加えて、特定の数の導入された請求項の列挙が明示的に列挙されているときですら、当業者は、かかる列挙は、一般に、少なくとも列挙された数を意味する（例えば、修飾語句を伴わない「２つの列挙」の単なる列挙は、一般に、少なくとも２つの列挙、または２つ以上の列挙を意味する）と解釈されるべきである点を理解されよう。
【００６６】
さらに、「Ａ、Ｂ、およびＣのうちの少なくとも１つの、など」に類似する表現方法が使用される場合、一般に、そのような構造は、当業者がその表現を理解するであろう意味が意図される（例えば、「Ａ、Ｂ、およびＣのうちの少なくとも１つを有するシステム」は、Ａだけを有するシステム、Ｂだけを有するシステム、Ｃだけを有するシステム、ＡとＢとを共に有するシステム、ＡとＣとを共に有するシステム、ＢとＣとを共に有するシステム、および／またはＡと、Ｂと、Ｃとを共に有するシステムなどを含むことになるが、これらに限定されない）。「Ａ、Ｂ、またはＣのうちの少なくとも１つ、など」に類似する表現方法が使用される場合、一般に、そのような構造は、当業者がその表現を理解するであろう意味が意図される（例えば、「Ａ、Ｂ、またはＣのうちの少なくとも１つを有するシステム」は、Ａだけを有するシステム、Ｂだけを有するシステム、Ｃだけを有するシステム、ＡとＢとを共に有するシステム、ＡとＣとを共に有するシステム、ＢとＣとを共に有するシステム、および／またはＡと、ＢとＣとを共に有するシステムなどを含むことになるが、これらに限定されない）。当業者は、明細書内であれ、特許請求の範囲内であれ、または図面内であれ、２つ以上の代替用語を提示する実質的にいかなる離接語および／または離接句も、それらの用語のうちの１つ、それらの用語のどちらか、またはそれらの用語の両方を含む可能性を企図すると理解されるべきである点をさらに理解されよう。例えば、「ＡまたはＢ」という成句は、「Ａ」、もしくは「Ｂ」、または「ＡおよびＢ」の可能性を含むと理解されることになる。
【図１】
0005444467.tif 000002
【図２】
0005444467.tif 000003
【図３】
0005444467.tif 000004
【図３Ａ】
0005444467.tif 000005
【図４】
0005444467.tif 000006
【図５】
0005444467.tif 000007