JPH0612325A - プロセス親和スケジュール法およびその装置 - Google Patents

プロセス親和スケジュール法およびその装置

Info

Publication number
JPH0612325A
JPH0612325A JP5046163A JP4616393A JPH0612325A JP H0612325 A JPH0612325 A JP H0612325A JP 5046163 A JP5046163 A JP 5046163A JP 4616393 A JP4616393 A JP 4616393A JP H0612325 A JPH0612325 A JP H0612325A
Authority
JP
Japan
Prior art keywords
cache
affinity
processor
bit
bus
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP5046163A
Other languages
English (en)
Inventor
Jr Arthur F Cochcroft
エフ．コウチクローフト， ジュニア アーサー
Jimmy D Pike
ディー．パイク ジミー
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NCR International Inc
Original Assignee
NCR International Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NCR International Inc filed Critical NCR International Inc
Publication of JPH0612325A publication Critical patent/JPH0612325A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5061—Partitioning or combining of resources
    • G06F9/5066—Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
    • G06F12/0842—Multiuser, multiprocessor or multiprocessing cache systems for multiprocessing or multitasking

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Abstract

(57)【要約】 【目的】主メモリ１６のデータでキャッシュ線を無用に
置換することを低減することができるプロセス親和スケ
ジュール手段を与える。 【構成】多重プロセッサシステム１０におけるプロセス
の移動は、ラン待ち行列上の上位Ｎ個のエントリについ
て利用可能なプロセッサが何らかの親和性を有するか否
かを見るための迅速な見取り表を与えることにより、制
御される。もしもプロセッサＰ1-Ｐpのうち現在利用可
能なものが或親和性を有する（すなわち当該プロセスに
関係するそのローカルキャッシュＣ1-ＣP内に格納され
ているオペランドおよび／またはインストラクションの
うちの一行以上を有する）と、その親和性を有するプロ
セッサはそのラン待ち行列上の上位Ｎ個のプロセスの中
から当該プロセスを選択する。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は多重プロセッサを有する
コンピューターシステムに関し、特に当該プロセスを効
率よく実行できるプロセッサによって処理できるように
各プロセスをスケジュール化する方法および装置に関す
る。
【０００２】
【従来の技術】共通システムメモリ内に情報を格納する
多重プロセッサコンピューターシステムにおいては、あ
る与えられたプロセスはいろいろの時期にアクティブと
なりいろいろのプロセッサ上で実行される可能性があ
る。一つのプロセッサから別のプロセッサへのこのよう
なプロセスの移動（migration）は多数の理由で生じ
る。プロセスは、ある入力／出力オペレーションが完了
するのを待機する期間中、多重プロセッサ上でのラン
（実行に移されること）を保留される。この入力／出力
オペレーションが完了すると、待機中のプロセスはラン
準備完了のマークを付けられ、ラン待ち行列上に置かれ
る。このプロセスは多重プロセッサのうち次に利用可能
となったプロセッサによってそのラン待ち行列から選択
される。この利用可能なプロセッサは必ずしも保留前に
先にプロセスを実行したプロセッサであるとは限らな
い。プロセスはまたそれに割り当てられた時間が時間切
れとなったためにランを保留されることもあり得る。一
旦プロセスの割当て時間が切れると、通常、プロセスは
低い優先度を指定されてラン待ち行列上に置かれ、別の
プロセッサにより選択され、すなわちプロセスは移動さ
れ、実行される。
【０００３】多重プロセッサ間におけるプロセスの移動
はかなり最近話題となった問題である。その理由は、各
々に大容量キャッシュメモリを有するプロセッサを多重
に有するシステムアーキテクチャはかなり最近に出現し
たことであるからである。しかしながらこのようなシス
テムアーキテクチャは進歩的なコンピューターシステム
にとって普遍的なアーキテクチャである。キャッシュメ
モリを持たせるのは、必要とされるシステムバスデータ
帯域およびメモリデータ帯域を低減するためである。キ
ャッシュメモリは、インストラクションを取り寄せるた
めに又はオペランドを読み取り若しくは書き込むために
行われる共通システムメモリへのアクセス数を低減する
ことにより、必要データ帯域を低減する。キャッシュメ
モリはまた平均的なオペレーションのサイクル時間を低
減することができる。なぜならばよく知られているよう
に、プロセッサとそのローカルキャッシュメモリとの間
のデータ転送は、そのプロセッサともっと遠い共通シス
テムメモリとの間の転送よりも高速であるからである。
【０００４】
【発明が解決しようとする課題】しかしながらプロセス
移動は通常、キャッシュマッチ（cache match）の代わ
りにキャッシュミス（cache miss）を来たし、キャッシ
ュミスはシステムメモリからの冗長な負荷オペレーショ
ンを来たす。プロセスが新たなプロセッサに移動する度
にこのような移動がキャッシュミスを起こし、そうなる
と続いてシステムメモリから当該プロセスのすべてある
いは一部を負荷しなければならない。従ってシステムメ
モリからの長い負荷を伴う頻繁なキャッシュミスは、シ
ステムバスおよびメモリデータ帯域に負の効果を与え
る。これは多重プロセッサを有するシステムアーキテク
チャに大きなローカルキャッシュを与えることにより所
望されている結果と正しく反対の結果を与える。
【０００５】キャッシュ負荷に伴うプロセッサ時間（処
理時間）の損失に加えて、当該プロセスのインストラク
ションおよびオペランドはプロセスが移動する度に複製
されて別のキャッシュメモリに格納される。言うまでも
なく同一プロセスのコピーの複製化は有限のキャッシュ
メモリ空間を浪費する。さらにかかる移動は、不必要に
も、まもなく実行されるプロセスのためのキャッシュラ
インの置換を起こす。
【０００６】制御されないままにプロセス移動が生ずる
ことを防止するため、コンピューター設計者によっては
或型のプロセス親和スケジュール化（process affinity
scheduling）をシステムソフトウェアの一部として含
めている。残念ながら、完全にソフトウェアに基づく解
決法は著しい量のプロセッサ時間およびシステムデータ
帯域とを使用し、あるいは少なからず理解しにくく、そ
れゆえ実質的な性能上の利得が得られない。
【０００７】本発明は多重プロセッサを有するコンピュ
ーターシステムにおけるプロセス移動を低減するため
の、ハードウェアに基づく親和スケジュール装置を与え
ることを課題とする。
【０００８】本発明の別の課題は多重プロセッサを有す
るコンピューターシステムにおけるプロセス移動を低減
するため、ハードウェアに基づく親和スケジュール装置
を作動させる方法を与えることを課題とする。
【０００９】
【課題を解決するための手段】本発明は上記課題を解決
するためその一局面として、各々にローカル外部キャッ
シュメモリを有するプロセッサを複数有するコンピュー
ターシステムに使用する装置を与える。本装置は最も近
時に実行されたユーザープロセスを同定する同定コード
を複数キャッシュデータ線に格納する親和キャッシュデ
バイス（affinity cache device）を含む。各キャッシ
ュデータ線は、ローカル外部キャッシュ内でそれぞれの
ユーザープロセスにより占領されているデータ線の数を
示すデータを収容する。さらに本装置は利用可能なプロ
セッサを利用するための親和性（affinity）をユーザー
プロセスが有するか否かを決定するため、コンピュータ
ーシステムのラン待ち行列内にリストされているラン準
備完了プロセスの同定コードを親和キャッシュデバイス
内の各同定コードと比較するためのデバイスを有する。
【００１０】本発明の別の局面では、各プロセッサがキ
ャッシュメモリを具えるようにされた多重プロセッサを
有するコンピューターシステムにおいて、プロセッサに
より実行されるプロセスをラン待ち行列から選択する方
法を与えることにより上記課題が達成できる。この方法
は、各アクティブプロセスに対し固有の親和性同定コー
ドを指定するステップと、各プロセッサにより最近時実
行されたＮ個プロセス（N most recent processes exec
uted）の親和性同定コードを格納するステップと、各プ
ロセッサの該Ｎ個の最近時プロセス毎に、各該キャッシ
ュ内で占領されているキャッシュ線の数を示すカウント
を当該プロセスに割り当てられた親和性同定コードに関
連づけると共に、各該カウントをその関連の親和性同定
コードと共に格納するステップと、各該プロセッサが、
最近時実行済みＮ個のプロセスの一つに対応する親和性
同定コードを持つ次のプロセスが該ラン待ち行列上にあ
れば該ラン待ち行列からこれを選択するが該当するもの
がなければ該ラン待ち行列上で最高度優先性を有するプ
ロセスを選択するステップとを含む。
【００１１】前記特許請求の範囲に記載した本発明は添
付の図面と以下の説明からより良く理解されよう。
【００１２】
【実施例】図１を参照すると、多重プロセッサＰ1-Ｐp
を有するコンピューターシステム１０が示されている。
プロセッサＰ1-Ｐpは各々それに装着されたそれぞれの
キャッシュメモリＣ1-Ｃpを有する。各プロセッサＰ1-
ＰpはそれぞれのプロセッサバスＰＢ1-ＰＢpを介して並
列システムバスのようなシステム中間接続ネットワーク
（system interconnection network）１２に接続する。
システム中間接続ネットワーク１２はまたメモリバス１
４を介して共通のシステムメモリ１６に接続される。共
通のシステムメモリ１６はシステム中間接続ネットワー
ク１２を経由して任意のプロセッサＰ1-Ｐpにアクセス
できる。コンピューターシステム１０は禁止的方策がと
られない限り、ランダムなプロセス移動を避けられな
い。
【００１３】図２を参照すると、本コンピューターシス
テムのＰ重プロセッサのうちのＰ1プロセッサの詳細な
説明が示されている。すべてのプロセッサは実質上同一
なので、当業者は残りのプロセッサの構造および動作、
並びにそれらのキャッシュ構成がプロセッサＰ1および
そのキャッシュ構成の説明から理解できよう。従って簡
単のため、プロセッサＰ1およびそのキャッシュ構成の
みを説明する。
【００１４】プロセッサＰ1はキャッシュインターフェ
ース２０に接続されており、キャッシュインターフェー
ス２０はキャッシュメモリシステムＣ1が多数の標準的
キャッシュプロトコルの任意の一つを使ってプロセッサ
Ｐ1および共通システムメモリ（図１）と対話すること
を許可する。キャッシュインターフェース２０はキャッ
シュメモリシステムＣ1およびプロセッサバスＰＢ1に接
続される。プロセッサバスＰＢ1は３２ビット並列アド
レスバス、６４ビット並列データバス、およびｎビット
並列制御バスを有する。プロセッサバスＰＢ1はさらに
システム中間接続インターフェース２２1を介してシス
テム中間接続ネットワーク１２にも接続する。
【００１５】本キャッシュメモリシステムはキャッシュ
コントローラおよびキャッシュタグメモリ（以下、キャ
ッシュコントローラという）３０1並びにキャッシュメ
モリ格納部３２1を含む。キャッシュメモリ格納部３２1
は各線が２５６ビットの線を容量８Ｋ分有する。キャッ
シュコントローラ３０1はインテルコーポレーションで
製造されている形式８２４８５のような周知のものでよ
く、これは一つ以上の標準的な静的ＲＡＭアレイと共同
してキャッシュメモリ格納部３２1として動作すること
ができる。当業者は設計例として他のサイズのキャッシ
ュ格納部および線サイズも使用可能であり、そのような
設計変更は本発明も範囲内であることを了解されたい。
【００１６】親和スケジュールシステム４０1はプロセ
ッサバスＰＢ1とキャッシュコントローラ３０1とに接続
される。親和スケジュールシステム４０1はキャッシュ
ステータスＲＡＭ４２1を含むが、これは図２の実施例
では８Ｋ×１０ビットのＲＡＭである。キャッシュステ
ータスＲＡＭ４２1に対するアドレス入力線はキャッシ
ュメモリ格納部３２1へのアドレス入力線と同一の線Ａ
１６-Ａ５である。この構成により、キャッシュステー
タスＲＡＭ４２1内の各エントリはキャッシュメモリ格
納部３２1内の２５６ビット線に関連される。各エント
リは各２５６ビット線に１０ビットを付加した論理拡張
体である。
【００１７】図２および図３を参照すると、キャッシュ
ステータスＲＡＭ４２1の構成および使用法が説明され
ている。上述したようにキャッシュメモリ格納部３２1
およびキャッシュステータスＲＡＭ４２1は共にアドレ
ス線Ａ１６-Ａ５に接続されている。この接続が４Ｋア
ドレスへのアクセスを可能にする。キャッシュコントロ
ーラ３０1は、キャッシュタグアドレスを転送するため
ＰＢ1のアドレス線Ａ３１-Ａ１７に接続され、キャッシ
ュインデックスアドレスを転送するためＰＢ1のアドレ
ス線Ａ１６-Ａ５に接続され、制御信号をプロセッサＰ1
で送信するためＰＢ1のｎ本の制御バス線に接続され
る。キャッシュコントローラ３０1はアドレスＡ３１-Ａ
１７からの情報を使用してキャッシュメモリ格納部３２
1の二つの４Ｋアレイ間の選択を行い、キャッシュステ
ータスＲＡＭ４２1の８Ｋアレイから一組のアドレスを
選択する。キャッシュステータスＲＡＭ４２1から得ら
れる各アドレスはそれぞれのキャッシュメモリ格納部３
２1と関連付けられる。線３６はキャッシュコントロー
ラ３０1をキャッシュメモリ格納部３２1に接続する。線
３６を介してアレイ選択信号が与えられる。線３８はキ
ャッシュコントローラ３０1をキャッシュステータスＲ
ＡＭ４２1に接続して組選択信号（a set selection sig
nal）を与える。このようにしてキャッシュコントロー
ラ３０1は標準的キャッシュプロトコルに従ってキャッ
シュメモリ格納部３２1を動作させるために使用される
のみならず、キャッシュメモリ格納部３２1内の２５６
ビットキャッシュデータ線各々をキャッシュステータス
ＲＡＭ４２1の各１０ビット線と関連付ける組織化にも
使用される。
【００１８】キャッシュメモリ格納部３２1は、データ
バス４７1を介してプロセッサバスＰＢ1の線Ｄ３１-Ｄ
０に接続された６４ビット幅のデータ入力を有する。デ
ータバス４７1を介して、キャッシュコントローラ３０1
およびアドレス線アドレス線Ａ３１-Ａ５の周知制御の
下に、これら２５６ビットキャッシュデータ線の６４ビ
ットが送信される。キャッシュステータスＲＡＭ４２1
の１０ビット線内に格納されたデータビットは以下に述
べるようにＰ1および親和性制御装置４６1により制御さ
れる。
【００１９】親和性制御装置４６1はキャッシュ制御バ
ス４８1を介してプロセッサバスＰＢ1の制御バスの制御
線に接続される。このキャッシュ制御バス４８1は、キ
ャッシュメモリ格納部３２1内の各２５６ビットキャッ
シュ線に関連する親和性情報を格納／呼び出しするた
め、プロセッサＰ1およびキャッシュコントローラ３０1
から来る制御信号を親和性制御装置４６1に与える。親
和性情報の格納および呼び出しは、プロセッサＰ1のオ
ペレーティングシステムの制御の下に、キャッシュシス
テムＣ1のオペレーションと類似の方法で達成される。
キャッシュ制御バス４８1に加えて、親和性制御装置４
６1はバス５０1によりプロセッサバスＰＢ1のアドレス
バスのアドレス線Ａ６-Ａ３に接続され、またデータバ
ス５２1によりプロセッサバスＰＢ1のデータバス部分の
線Ｄ３１-Ｄ０に接続される。
【００２０】プロセッサＰ1は他のプロセッサと関連し
ながらオペレーティングシステムソフトウェアを実行
し、各プロセスがアクティブになる際にそのプロセスに
プロセス同定番号（process identification number,
ＰＩＤ）を割り当てる。図４に示す実施例は８ビットを
有するので、０と２５５の間のＰＩＤは最初の２５６個
アクティブプロセスに割り当てられ、本コンピューター
システム１０（図１）上で走るプロセスすべてに予め割
り当てられている固有の３２ビットプロセス同定番号の
別名として使われる。８プロセッサシステムの場合、全
部で２５６個の同定コードは３２個の現アクティブ（cu
rrently active）プロセス／プロセッサに対応する。こ
れはシステムの使用上十分すぎるものであると考えられ
る。もしもアクティブプロセスの数が２５６を超える
と、最も旧くに使用されたキャッシュを置換する戦略
（least recently used chache replacement strateg
y）に類似した置換プロセスを設けて別名の再割当てを
することができる。２５６アクティブプロセスを超える
大きなシステムではＰＩＤ内のビット数は必要に応じて
拡張することができる。
【００２１】本発明の一実施例では各プロセッサＰ1-Ｐ
pはオンチップ８Ｋバイトの直接マップキャッシュメモ
リ格納部（on-chip 8K byte directly mapped cache me
morystore）を有する。本親和性スケジュールシステム
を最適に動作させるため、オンチップキャッシュメモリ
格納部とオフチップキャッシュメモリ格納部３２1との
間のデータの包含（data inclusion）はキャッシュコン
トローラ３０1のプロトコルにより与えられる。その場
合、オンチップキャッシュメモリ格納部内のすべての情
報がキャッシュメモリ格納部３２1内にも格納されるよ
うにする。さらに、そのような実施例ではオペレーティ
ングシステムは、当該プロセスにサービスしているオペ
レーティングシステムカーネル（operating system ker
nel）に当該プロセスに属する３２ビットプロセス同定
番号を割り当てる。これを説明すると、ユーザープロセ
スとそのユーザープロセスにサービスを行っているオペ
レーティングシステムカーネルとを親和スケジュールシ
ステムが区別できるようにするため、各ＰＩＤにカーネ
ル／ユーザー ビットと名付けられる９番目のビットが
追加される。前者（ユーザープロセス）は親和スケジュ
ールシステムに含まれるが、後者カーネルは含まれな
い。
【００２２】キャッシュステータスＲＡＭ４２1の各１
０ビット線に示されている第１０番目のビットは有効／
無効ビットである。キャッシュステータスＲＡＭ４２1
内の線が格納される当初、それに有効の印が付けられる
が、もしも或オペレーションでＰＩＤが再度当該ローカ
ルプロセッサその他のプロセッサを用いて書き込まれる
と、そのキャッシュ線のステータスは無効である場合が
あり、従ってそのときはこのビットを変更することによ
り無効の印が付けられる。
【００２３】ここで図４および図５を参照して本親和ス
ケジュールシステムをさらに詳細に説明する。データバ
ス５２1は親和性制御装置４６1への接続と同様、ＰＩＤ
レジスタ６０1およびプロセス親和性キャッシュ（proce
ss affinity cache, ＰＡＣ）５４1に接続される。ＰＩ
Ｄレジスタ６０1からの９ビット出力はバス６２1により
マルチプレクサ５８1に接続されると共に、バス６４1に
より制御されるバスドライバ６６1に接続される。バス
ドライバ６６1の出力はキャッシュステータスＲＡＭ４
２1に接続されると共に、バス６８1によりマルチプレク
サ５８1の別の入力に接続される。親和性制御装置４６1
は線７０1を介してバスドライバ６６1に接続され、バス
６８1を経由して送信された信号を使ってこの線経由の
データ信号の送信を制御する。マルチプレクサ５８1は
バス７２1を介して親和性制御装置４６1からの８ビット
出力に接続される第三入力を有する。マルチプレクサ５
８1の８ビット出力はバス７４1を介してＰＡＣ５４1に
接続される。
【００２４】親和スケジュールシステム４０1にはそれ
自身のアドレス空間が割当られる。親和性制御装置４６
1はこのアドレス空間を入力／出力アドレス空間として
使用する。この入力／出力アドレス空間のアドレスオフ
セット０には第一制御レジスタ（ＣＲＧ０）が配置され
る。図５に示す好ましい実施例ではこのレジスタは３２
ビット幅である。但しそのうちの２０ビットは未使用で
ある。親和スケジュールシステム４０1のオペレーショ
ンは、ＣＲＧ０のビット３１を論理１に設定することに
よりイネーブル化される。一旦イネーブル化が行われる
と、ＰＩＤまたはカーネル／ユーザー ビットを親和性
制御装置４６1中に負荷するため、プロセッサＰ1による
制御レジスタＣＲＧ０への書き込みを行うことができ
る。ＰＩＤまたはカーネル／ユーザー ビットを用いて
プロセッサＰ1はまたＣＲＧ０と一プロセス親和キャッ
シュ（ＰＡＣ）５４1との間でいかなるアクションがと
られべきかを親和性制御装置４６1に指令する２進ビッ
トオペレーションコードを書き込む。制御レジスタ０Ｃ
ＲＧ０およびＰＡＣ５４1が関与する四つのオペレーシ
ョンを表１に示す。
【表１】 Ｄ３０ Ｄ２９ オペレーション ０ ０ ＰＡＣ内のカーネル／ユーザー ビットのトグル。 ＰＩＤの変化はなし。 ０ １ 新規ＰＩＤの負荷。 必要があればＰＡＣへの割当てを行う。 １ ０ 新規ＰＩＤを負荷するが、異なるプロセスのＰＩＤ を再使用する。必要があればＰＡＣへの割当てを行い 、ＰＡＣ内にカウントがあれば解除する。 １ １ すべてのＰＡＣエントリを無効化し、ＰＡＣ内の各カ ウントを解除する。
【００２５】ＰＡＣ５４1は全部的に関連するキャッシ
ュである。好ましい本実施例ではＰＡＣ５４1は８×３
２ビットキャッシュである。ＰＡＣ５４1内の各線のフ
ォーマットは図４に示されている。８個のＲＰＩＤフィ
ールドはプロセッサＰ1により最も近時に使用された８
個のユーザーＰＩＤに対するロケーションである。８個
の各ＲＰＩＤフィールドは、これに関連づけられた四ビ
ットのＰＡＣアドレス-アンド-イネーブル信号（ＡＤＥ
３：０）と一つの１６ビットカウントフィールドとを
有する。このカウントフィールドは各ＰＡＣ５４1に対
応するプロセスにより占領されているキャッシュステー
タスＲＡＭ４２1内キャッシュ線の数を表す。
【００２６】当該ＰＡＣ内に既にＰＩＤが格納されてい
るのでないならば、表１に示す負荷オペレーション（０
１）または（１０）のいずれも、一つ以上の線をユーザ
ーＰＩＤ（すなわちカーネル／ユーザー ビット＝０の
ＰＩＤで、ＰＡＣ５４1内の一ロケーションである）に
割り当てる。異なるプロセスオペレーションからのＰＩ
Ｄの負荷および再使用を行う場合（１０）は、もしも当
該ＰＩＤがＰＡＣ５４1内に発見されると、そのＰＩＤ
に対するキャッシュ線カウントフィールドが解除され
る。
【００２７】負荷オペレーション（０１または１０）の
いずれかの期間中はマルチプレクサ５８1はバス７４1を
介して現プロセスのＰＩＤをＰＩＤレジスタ６０1から
ＰＡＣ５４1に切り替える。ＰＡＣ５４1は全部的にキャ
ッシュメモリに関連するので、すべてのＲＰＩＤが現プ
ロセスＰＩＤと並列に比較される。但し有効／無効ビッ
トにより無効とマークされたものはこの比較から除かれ
る。もしも現プロセスＰＩＤがＲＰＩＤの一つに一致す
ると、イネーブルと三ビットアドレスとを含むマッチ信
号がＰＡＣ５４1から親和性制御装置４６1へ向けて四導
体バス７６1上に送り出される。バス７６1上のこの三ビ
ットアドレスは一致するＲＰＩＤ（以下、マッチングＲ
ＩＰＤという）の論理線アドレスである。プロセッサＰ
1は次いで当該親和性データを使ってＰＡＣ５４1中への
負荷プロセスを完了する。
【００２８】形式（１０）の負荷オペレーションが開始
されると、親和性制御装置４６1は論理演算の結果とし
て、マッチングＲＩＰＤのカウントフィールドをリセッ
トするリセット信号を与える。もしもマッチングＲＩＰ
Ｄが発見されないと、ＰＡＣ５４1から親和性制御装置
４６1へ、バス７６1を介してミス信号が送られる。ミス
が生じたときは、ＰＡＣ５４1はバス７６1を介して最低
のカウントフィールド値を持つＲＰＩＤの論理アドレス
を親和性制御装置４６1へ送る。親和性制御装置４６1は
その後、ミスの生じた８ビットＰＩＤを、前記ミス信号
と共に送られた論理アドレスに対応するＰＡＣ５４1の
中の当該キャッシュ線中に書き込み、その線の有効ビッ
トを設定し、その線のカウントフィールドを０にリセッ
トする。この代わりとして別の実施例はそのようなミス
が生じたときは、置換の必要条件たる無効のマークを付
けられた有効／無効ビットを有する第一キャッシュ線の
論理アドレスを、ＰＡＣ５４1が送信する。
【００２９】オペレーションに関して図２を再び参照す
ると、表１の四つのオペレーションの一つを行なうた
め、プロセッサＰ1は書き込みインストラクションとデ
ータをＣＲＧ０へ送る。現オペレーションが完了する
と、親和性制御装置４６1は、当該スケジュールオペレ
ーションが完了したことと、当該プロセッサがプロセス
を実行をできることとを示すため、プロセッサＰ1に信
号を送る。この完了信号が送られた後、マルチプレクサ
５８1はバス７４1を介して１０ビット出力の指向先を４
システム中間接続ネットワーク１２からＰＡＣ５４1の
入力に切り替える。バスキャッシュ制御バス４８1内の
マッチ／ミス制御線を監視することにより検出されるよ
うに、もしもアクセスの結果がキャッシュミスである
と、キャッシュステータスＲＡＭ４２1からの１０ビッ
ト出力はバス８２1を介して親和性制御装置４６1により
検査される。もしも有効／無効ビットが設定されてお
り、カーネル／ユーザー ビットがリセットされている
と、ＰＡＣ５４1内で見取りオペレーションが行われ
る。もしもマッチングＲＩＰＤエントリがＰＡＣ５４1
内に発見されると、関連のカウントが親和性制御装置４
６1により減少される。なぜならば当該プロセスに属す
るキャッシュ線はキャッシュメモリ格納部Ｃ1内で置換
されているからである。このオペレーションが起きるの
は、共通のシステムメモリ１６（図１）からキャッシュ
線を充満させるオペレーションを行うためキャッシュコ
ントローラ３０1がシステム中間接続ネットワーク１２
を要求しており、且つ獲得している間である。
【００３０】次にマルチプレクサ５８1は８ビットＰＩ
Ｄの指向先を、バス６２1および７４1を介してＰＩＤレ
ジスタ６０1からＰＡＣ５４1の入力に切り替える。同時
に、親和性制御装置４６1はバスドライバ６６1を制御
し、バス６２1および６８1を介してカーネル／ユーザー
ビットおよび８ビットＰＩＤをＰＩＤレジスタ６０1か
らキャッシュステータスＲＡＭ４２1の入力／出力ポー
トに送信する。キャッシュ線は共通メモリからアクセス
できるが、ＰＡＣ５４1内で見取りオペレーションが行
われる。但しカーネル／ユーザー ビットがリセットさ
れているときはＰＡＣ５４1中にはカーネルＰＩＤが全
く格納されないのでこのときは見取りオペレーションは
行われない。当該キャッシュメモリ格納部３２1内にキ
ャッシュ線が格納されると、ＰＩＤレジスタ６０1から
キャッシュステータスＲＡＭ４２1にカーネル／ユーザ
ー ビットおよび８ビットの現ＰＩＤが書き込まれ、有
効／無効ビットが設定される。もしもＰＩＤレジスタ６
０1から書き込まれた現ＰＩＤが論理０にリセットされ
ているカーネル／ユーザー ビットを有するなら、ＰＡ
Ｃ５４1内のマッチングエントリのカウントフィールド
が増量される。なぜならばこの時点で当該関連のユーザ
ープロセスはキャッシュメモリ格納部３２1および／ま
たはプロセッサＰ1（図示してなし）のオン−チップキ
ャッシュ内に追加線を有するからである。
【００３１】プロセッサＰ1により起こされたキャッシ
ュアクションに加えて、親和性制御装置４６1は、コン
ピューターシステム１０（図１）の別のプロセッサによ
り開始された無効化スヌープサイクル（invalidating s
noop cycle、無効化のための覗き見サイクル）がキャッ
シュメモリ格納部３２1に影響しているか否かを決定す
るため、制御バス４８1の制御も行う。もしもキャッシ
ュメモリ格納部３２1の少なくとも一つのキャッシュ線
を無効化するスヌープサイクルが親和性制御装置４６1
により検出されると、無効化されるキャッシュ線の８ビ
ットＰＩＤがＰＩＤレジスタ６０1中に入れられ、ＲＰ
ＩＤ一致検査のためこの８ビットＰＩＤがＰＡＣ５４1
に送信される。もしもマッチングが起きていると、マッ
チングＲＰＩＤのキャッシュ線内のカウントフィールド
が決定される。従って、プロセッサＰ1のローカルキャ
ッシュ内に格納されている線に収容されているアドレス
をコンピューターシステム１０内の別のプロセッサが書
き込みもしくは書き込みの意図を以て読み取りを行うと
き（すなわち所有権を求めて読み取りを行うとき）は、
親和スケジュールシステム４０1はコヒーレントに留ま
る。
【００３２】このようにして各親和スケジュールシステ
ムは関連プロセッサのキャッシュメモリ格納部に現在存
在している最近時に実行された最大８個までのユーザー
プロセスに関連する全キャッシュ線数のカウントを維持
する。もしも例えばシステムＩ／Ｏとか時間スライスの
時間切れとかのためにプロセスが保留されると、ローカ
ルプロセッサはオペレーティングシステムのカーネルを
再入力し、当該プロセスのＰＩＤに関連したカーネル／
ユーザー ビットを設定する。さらに、このプロセッサ
は親和性制御装置４６1の制御レジスタＣＲＧ０に表１
に示すトグルオペレーション（００）を書き込む。この
ように設定されたカーネル／ユーザービットは親和スケ
ジュールシステム４０1に、このプロセスがラン準備完
了していないことおよびそれが最近時に実行された８個
のプログラムの一つとしてＰＡＣ５４1内に収容される
ことを示す。従ってＰＡＣ５４1はラン準備の整った高
い親和性のプロセスのＲＰＩＤのみを収容する。これは
親和スケジュールを立てるための最善の判定条件を与え
る。
【００３３】あるプロセッサＰ1-Ｐpが次のプロセスに
利用可能となると、そのプロセッサはＰＡＣの出力ポー
トから３２ビットワードを読むことにより、当該プロセ
ッサに帰属するＰＡＣ1-ＰＡＣp内エントリを８個まで
読み取ることができる。３２ビットワードのデータフォ
ーマットを図６に示す。当該ＰＡＣ内の８線エントリを
読み取った後、利用可能なプロセッサは、当該プロセッ
サにとって最大の親和性を有する８プロセスを記述する
データを、有する。もしもこれら８個のプロセッサのう
ちの一つ以上が、ＬＡＮ準備完了しているＬＡＮ待ち行
列にあると、プロセッサはそれぞれのキャッシュメモリ
システムＣ1-Ｃp内で最大数の線を占領するプロセスを
スケジュール化する。ＬＡＮ待ち行列上のこのプロセス
は早晩実行されなければならないので、それを実行する
ためにキャッシュ中に最少限度数の線を負荷すればよい
プロセッサで実行すれば一層効率的である。利用可能な
プロセッサに対するプロセス親和性に基づいてシステム
ラン待ち行列からラン準備完了したユーザープロセスを
選択する方法は図９および図１０に示されている。
【００３４】ここで図７および図８を参照する。親和ス
ケジュールを得るためのもう一つのプロセスは、親和ス
ケジュールシステム４０1内にプローブ能力を含めるこ
とである。そのようなプロセスは第二の制御レジスタＣ
ＲＧ１を使用するが、かかる第二制御レジスタＣＲＧ１
は図７に示すデータフォーマットと図８に示すデータフ
ォーマットを有する結果レジスタ（result register）
とを有する。これらのプロセスは、ラン待ち行列内にあ
るプロセスのラン準備完了プロセス同定番号からＰＩＤ
が抽出されることを可能にする。これは８ビットプロー
ブＰＩＤをＣＲＧ１中に書き込むことにより達成され
る。この書き込みによって親和性制御装置４６1がトリ
ガー作動され、プローブＰＩＤがＰＡＣ５４1内のＲＰ
ＩＤと比較される。もしも一致するエントリが全く発見
されないと、結果レジスタにはプローブＰＩＤ（すべて
が０のカウントフィールド）が負荷され、「発見されな
い」フラッグが立てられる。もしもマッチングＲＩＰＤ
エントリが発見されると、結果レジスタにはプローブＰ
ＩＤ（マッチングＲＩＰＤエントリに関連したカウント
フィールド）が負荷され、「発見された」フラッグが立
てられる。このプロセッサは結果レジスタを読み取り、
当該発見されたプロセスを実行することができる。
【００３５】
【効果】以上の説明から、新規なキャッシュ親和スケジ
ュール装置を開示したことが了解されよう。すなわち本
発明は多重プロセッサを有するコンピューターシステム
においてプロセス移動を低減するための、ハードウェア
に基づく親和スケジュールの方法およびそのための装置
を与える。この親和スケジュールは主メモリのデータで
キャッシュ線を無用に置換することを低減する。
【００３６】尚、好ましい実施例を参照して本発明を特
定的に例示し説明したが、当業者であれば形態、詳細お
よび用途に関していろいろの変更が可能であることを理
解されたい。例えば一層大きなＰＩＤ数を使うため、長
いＰＩＤ数を使うことができる。またプロセス親和性キ
ャッシュを８エントリ以上に拡張して最近時に実行され
たプロセスをさらに多数含めることができる。
【図面の簡単な説明】
【図１】Ｐ個のプロセッサを有するコンピューターシス
テムの簡単なブロック線図である。
【図２】Ｐ個のプロセッサの一つのブロック線図で、そ
のキャッシュメモリおよびその関連の親和スケジュール
回路を示す。
【図３】図２に示すキャッシュメモリおよび親和スケジ
ュール回路内のデータフィールドの構成を示す図であ
る。
【図４】本発明に基づく親和スケジュール回路のブロッ
ク線図である。
【図５】本発明に基づく制御レジスタ０のブロック線図
である。
【図６】本発明に基づくプロセス親和キャッシュ読み取
り入力レジスタのブロック線図である。
【図７】本発明に基づく制御レジスタ１のブロック線図
である。
【図８】本発明に基づく結果レジスタのブロック線図で
ある。
【図９】本発明に基づく親和スケジュール装置を作動さ
せる一方法を示す流れ図である。
【図１０】本発明に基づく親和スケジュール装置を作動
させる別の方法を示す流れ図である。
【符号の説明】
１０ コンピューターシステム １４ メモリバス ＰＢ1 プロセッサバス
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジミー ディー．パイク アメリカ合衆国 29607 サウス カロラ イナ、グリーンヴィル、クロス ヤード 28

Claims (2)

    【特許請求の範囲】
  1. 【請求項１】各々にローカル外部キャッシュメモリを有
    するプロセッサを複数含むコンピューターシステムに使
    用する装置であって、 最近時に実行されたユーザープロセスを同定する同定コ
    ードを複数のキャッシュデータ線に格納するための親和
    キャッシュ手段にして、該ローカル外部キャッシュにお
    いてそれぞれのユーザープロセスにより占領されている
    データ線の数を示すデータを各該キャッシュデータ線が
    収容するようにされた親和キャッシュ手段と、 該コンピューターシステムのラン待ち行列内にリストさ
    れたラン準備完了プロセスの同定コードを該親和キャッ
    シュ手段内の各該同定コードと比較して、利用可能なプ
    ロセッサを利用するための親和性をユーザープロセスが
    有するか否かを決定する比較手段とを含むことを特徴と
    する装置。
  2. 【請求項２】各々にキャッシュメモリを有するプロセッ
    サを多重に具えるコンピューターシステムにおいて実行
    を待つラン待ち行列からあるプロセスを選択する方法で
    あって、 各アクティブプロセスに対し固有の親和性同定コードを
    指定するステップと、 各プロセッサにより最近時実行されたＮ個プロセスの親
    和性同定コードを格納するステップと、 各プロセッサの該Ｎ個の最近時プロセス毎に、各該キャ
    ッシュ内で占領されているキャッシュ線の数を示すカウ
    ントを当該プロセスに割り当てられた親和性同定コード
    に関連づけると共に、各該カウントをその関連の親和性
    同定コードと共に格納するステップと、 各該プロセッサが、最近時実行済みＮ個のプロセスの一
    つに対応する親和性同定コードを持つ次のプロセスが該
    ラン待ち行列上にあれば該ラン待ち行列からこれを選択
    するが該当するものがなければ該ラン待ち行列上で最高
    度優先性を有するプロセスを選択するステップとを含む
    ことを特徴とするプロセス選択方法。
JP5046163A 1992-02-18 1993-02-12 プロセス親和スケジュール法およびその装置 Pending JPH0612325A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US836487 1992-02-18
US07/836,487 US5317738A (en) 1992-02-18 1992-02-18 Process affinity scheduling method and apparatus

Publications (1)

Publication Number Publication Date
JPH0612325A true JPH0612325A (ja) 1994-01-21

Family

ID=25272052

Family Applications (1)

Application Number Title Priority Date Filing Date
JP5046163A Pending JPH0612325A (ja) 1992-02-18 1993-02-12 プロセス親和スケジュール法およびその装置

Country Status (4)

Country Link
US (1) US5317738A (ja)
EP (1) EP0557050B1 (ja)
JP (1) JPH0612325A (ja)
DE (1) DE69320847T2 (ja)

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5890221A (en) * 1994-10-05 1999-03-30 International Business Machines Corporation Method and system for offset miss sequence handling in a data cache array having multiple content addressable field per cache line utilizing an MRU bit
JP3612105B2 (ja) * 1995-03-13 2005-01-19 株式会社東芝 Ａｔｍ通信システムとａｔｍ通信システムにおけるプロセスマイグレーション方法
US6105053A (en) * 1995-06-23 2000-08-15 Emc Corporation Operating system for a non-uniform memory access multiprocessor system
US6633897B1 (en) * 1995-06-30 2003-10-14 International Business Machines Corporation Method and system for scheduling threads within a multiprocessor data processing system using an affinity scheduler
US5784614A (en) * 1995-07-27 1998-07-21 Ncr Corporation Cache affinity scheduling method for multi-processor nodes in a split transaction bus architecture
KR100384213B1 (ko) * 1995-10-06 2003-08-19 어드밴스트 마이크로 디바이시즈 인코퍼레이티드 순차리스트내의선택된타입의제1또는제2대상을인식하는처리시스템,선택회로및방법
JPH09101916A (ja) * 1995-10-06 1997-04-15 Fujitsu Ltd マルチプロセス処理装置
US5825788A (en) 1996-05-20 1998-10-20 Micron Technology Inc. Data ordering for cache data transfer
US5872972A (en) * 1996-07-05 1999-02-16 Ncr Corporation Method for load balancing a per processor affinity scheduler wherein processes are strictly affinitized to processors and the migration of a process from an affinitized processor to another available processor is limited
US5761506A (en) * 1996-09-20 1998-06-02 Bay Networks, Inc. Method and apparatus for handling cache misses in a computer system
US6591414B2 (en) * 1996-10-28 2003-07-08 Fujitsu Limited Binary program conversion apparatus, binary program conversion method and program recording medium
US5752261A (en) * 1996-11-07 1998-05-12 Ncr Corporation Method and apparatus for detecting thrashing in a cache memory
US6714960B1 (en) * 1996-11-20 2004-03-30 Silicon Graphics, Inc. Earnings-based time-share scheduling
US6269390B1 (en) * 1996-12-17 2001-07-31 Ncr Corporation Affinity scheduling of data within multi-processor computer systems
US5974438A (en) * 1996-12-31 1999-10-26 Compaq Computer Corporation Scoreboard for cached multi-thread processes
DE19833221C2 (de) * 1997-07-31 2000-11-23 Siemens Nixdorf Inf Syst Verfahren zur Erhöhung der Nutzleistung von Multiprozessorsystemen
US6360303B1 (en) * 1997-09-30 2002-03-19 Compaq Computer Corporation Partitioning memory shared by multiple processors of a distributed processing system
US6907605B1 (en) * 1998-05-18 2005-06-14 International Business Machines Corporation Method and apparatus for providing for notification of task termination
US6243788B1 (en) * 1998-06-17 2001-06-05 International Business Machines Corporation Cache architecture to enable accurate cache sensitivity
US6782410B1 (en) 2000-08-28 2004-08-24 Ncr Corporation Method for managing user and server applications in a multiprocessor computer system
US6640289B2 (en) * 2000-11-15 2003-10-28 Unisys Corporation Software controlled cache line ownership affinity enhancements in a multiprocessor environment
US20020087828A1 (en) * 2000-12-28 2002-07-04 International Business Machines Corporation Symmetric multiprocessing (SMP) system with fully-interconnected heterogenous microprocessors
US6745299B2 (en) * 2001-11-19 2004-06-01 Hewlett-Packard Development Company, L.P. Method for evaluation of scalable symmetric multiple processor cache coherency protocols and algorithms
JP3864251B2 (ja) * 2002-12-06 2006-12-27 インターナショナル・ビジネス・マシーンズ・コーポレーション メッセージ処理装置、メッセージ処理方法、及びメッセージ処理プログラム
US8156496B2 (en) 2007-01-31 2012-04-10 Hewlett-Packard Development Company, L.P. Data processing system and method
US8621470B2 (en) * 2008-01-24 2013-12-31 Hewlett-Packard Development Company, L.P. Wakeup-attribute-based allocation of threads to processors
US8108867B2 (en) * 2008-06-24 2012-01-31 Intel Corporation Preserving hardware thread cache affinity via procrastination
JP2011059777A (ja) * 2009-09-07 2011-03-24 Toshiba Corp タスクスケジューリング方法及びマルチコアシステム
US8719500B2 (en) * 2009-12-07 2014-05-06 Intel Corporation Technique for tracking shared data in a multi-core processor or multi-processor system
AU2011213795A1 (en) 2011-08-19 2013-03-07 Canon Kabushiki Kaisha Efficient cache reuse through application determined scheduling
JP6459784B2 (ja) 2015-06-03 2019-01-30 富士通株式会社 並列計算機、マイグレーションプログラム、及び、マイグレーション方法
US10223282B2 (en) * 2017-05-23 2019-03-05 International Business Machines Corporation Memory affinity management
EP3753229B1 (en) * 2018-03-02 2023-08-02 Huawei Technologies Co., Ltd. Devices and methods for coded caching
US11182205B2 (en) * 2019-01-02 2021-11-23 Mellanox Technologies, Ltd. Multi-processor queuing model

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2253423A5 (ja) * 1973-11-30 1975-06-27 Honeywell Bull Soc Ind
US4809157A (en) * 1985-09-30 1989-02-28 International Business Machines Corp. Dynamic assignment of affinity for vector tasks
US4775955A (en) * 1985-10-30 1988-10-04 International Business Machines Corporation Cache coherence mechanism based on locking
US5006982A (en) * 1988-10-21 1991-04-09 Siemens Ak. Method of increasing the bandwidth of a packet bus by reordering reply packets
DE68924755D1 (de) * 1988-10-31 1995-12-14 Ibm Mehrfachverarbeitungssystem und Verfahren für gemeinsame Speichernutzung.
US5148533A (en) * 1989-01-05 1992-09-15 Bull Hn Information Systems Inc. Apparatus and method for data group coherency in a tightly coupled data processing system with plural execution and data cache units
JP3155537B2 (ja) * 1989-01-23 2001-04-09 株式会社日立製作所 実記憶管理方法
US5155831A (en) * 1989-04-24 1992-10-13 International Business Machines Corporation Data processing system with fast queue store interposed between store-through caches and a main memory
US5197139A (en) * 1990-04-05 1993-03-23 International Business Machines Corporation Cache management for multi-processor systems utilizing bulk cross-invalidate
US5109512A (en) * 1990-05-31 1992-04-28 International Business Machines Corporation Process for dispatching tasks among multiple information processors
US5185861A (en) * 1991-08-19 1993-02-09 Sequent Computer Systems, Inc. Cache affinity scheduler

Also Published As

Publication number Publication date
US5317738A (en) 1994-05-31
DE69320847D1 (de) 1998-10-15
EP0557050A1 (en) 1993-08-25
EP0557050B1 (en) 1998-09-09
DE69320847T2 (de) 1999-05-27

Similar Documents

Publication Publication Date Title
JPH0612325A (ja) プロセス親和スケジュール法およびその装置
US5490261A (en) Interlock for controlling processor ownership of pipelined data for a store in cache
JP4106016B2 (ja) 入出力（ｉ／ｏ）通信のハードウェア・アクセラレーションを実現するデータ処理システム
US5465342A (en) Dynamically adaptive set associativity for cache memories
US5966734A (en) Resizable and relocatable memory scratch pad as a cache slice
US5941981A (en) System for using a data history table to select among multiple data prefetch algorithms
US5119485A (en) Method for data bus snooping in a data processing system by selective concurrent read and invalidate cache operation
US5950225A (en) Fly-by XOR for generating parity for data gleaned from a bus
US20040139305A1 (en) Hardware-enabled instruction tracing
US5450564A (en) Method and apparatus for cache memory access with separate fetch and store queues
US20040139304A1 (en) High speed virtual instruction execution mechanism
JP4006436B2 (ja) 種々のキャッシュ・レベルにおける連想セットの重畳一致グループを有するマルチレベル・キャッシュ
US6976148B2 (en) Acceleration of input/output (I/O) communication through improved address translation
JPH0272452A (ja) 無効要求を選別する方法及び装置
WO1990003002A1 (en) Coherent cache structures and methods
JPS6150342B2 (ja)
JPS6149709B2 (ja)
US6662216B1 (en) Fixed bus tags for SMP buses
US5214766A (en) Data prefetching based on store information in multi-processor caches
EP0380842A2 (en) Method and apparatus for interfacing a system control unit for a multiprocessor system with the central processing units
KR100373576B1 (ko) 변환 장치의 엔트리를 무효로 하는 시스템 및 방법
US6976128B1 (en) Cache flush system and method
US20080301324A1 (en) Processor device and instruction processing method
US7783842B2 (en) Cache coherent I/O communication
EP0159712A2 (en) Control means in a digital computer

Legal Events

Date Code Title Description
A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20040907