JPH083801B2 - 度数を含まない関数型言語コ−ドを用いる２進有向グラフとしてストアされたプログラムを評価する縮小プロセッサのためのシステムアロケ−タ - Google Patents

Description

【発明の詳細な説明】 関連した米国特許出願 掲題の出願に直接的または間接的に関連した米国特許
出願は以下のとおりである。

Gary E. Logsdon 等によって1984年６月５日出願さ
れた「変数を含まない関数型言語コードを用いる２分有
向グラフとしてストアされたプログラムを評価する縮小
プロセッサのためのグラフマネージャ（Graph Manager
for a Reduction Processor Evaluating Programs Stor
ed as Binary Directed Graphs Employing Variable−F
ree Applicative Language Codes）」と題される、連続
番号第617,526号。

Gary E. Logsdon 等によって1984年６月５日に出願
された「変数を含まない関数型言語コードを用いる２分
有向グラフとしてストアされたプログラムを評価する縮
小プロセッサのための並列レジスタ転送機構（Parallel
Register Transfer Mechanism for a Reduction Proce
ssor Evaluating Programs Stored as Binary Directed
Graphs Employing Variable−Free Applicative Langu
age Codes）」と題される、連続番号第617,531号。

Gary E. Logsdon 等によって1984年６月５日に出願
された「変数を含まない関数型言語コードを用いる２分
有向グラフとしてストアされたプログラムを評価する縮
小プロセッサのための条件コンセントレータおよび中央
記憶（Condition Concentrator Central Store for a R
eduction Processor Evaluating Programs Stored as B
inary Directed Graphs Employing Variable Free Appl
icative Language Codes）」と題される、連続番号第61
7,532号。

Gary E. Logsdon 等によって1985年１月11日に出願
された「変数を含まない関数型言語コードを用いる２分
有向グラフとしてストアされたプログラムを評価する縮
小プロセッサのためのアロケータ（Allocator for a Re
duction Processor Evaluating Programs Stored as Bi
nary Directed Graphs Employing Variable−Free Appl
icative Language Codes）」と題される、連続番号第69
0,846号。

発明の背景 発明の分野 この発明は２分有向グラフとして表わされたプログラ
ムを評価するようにされたデジタルプロセッサのための
システムメモリおよびアロケータに関するものであっ
て、特にグラフを等価なグラフに順次置換えることによ
ってそのようなグラフを評価するプロセッサに関するも
のである。

先行技術の説明 今日、市場におけるほとんどのデジタルコンピュータ
は未だにJohn Von Neumannによって最初に仮定された型
であり、指令をシーケンシャルに実行する。フォートラ
ンおよびコボルのようなコンピュータをプログラムする
ための高レベル言語の初期のものは、この編成を反映し
てコンピュータによって実行されるアルゴリズムの設計
と同様、記憶管理および制御フローの管理の責任をプロ
グラマに任せた。Pure LISP のような純粋な関数型言
語は、命令言語とは異なり、プログラマからこれらの管
理責任を取り除く。

Pure LISP に代わるものはセイントアンドリュース
スタティック言語（Saint Andrews Static Languag
e）、すなわちSASLで、これはDavid A. Turner によっ
て開発された（SASL言語マニュアル（SASL Language Ma
nual)、1976年、セイント アンドリュース大学）。
「結合子（combinator）」と呼ばれる多数の定数を導入
することによって、この言語は変数を含まない表示に変
換できる（D.A.Turner、「関数型言語のための新実現化
例技術（A New Implementation Technique for Applica
tive Languages）」ソフトウェアー実践および経験（So
ftware-Practice and Experience）第９巻、31−49頁、
1979年）。この表示は（引数として関数を、結果として
リターン関数をとることができる）より高次の関数およ
び（仮に１個または２個以上の引数が規定されていなく
ても結果を返してもよい）非厳密関数（non−strict fu
nctions）を取扱うのに特に有利である。

Turnerによって開発された実現化例技術は、プラス、
マイナスなどのような１組の原始的関数（primitive fu
nctions）およびより高次の非厳密関数である１組の結
合子を採用する。これらのオペレータは置換規則によっ
て正式に規定され、それらのいくつかの具体例は以下の
通りである。

Ｓ ｆ ｇ ｘ＝ｆ ｘ （ｇ ｘ） Ｋ Ｘ ｙ＝ｘ Ｉ ｘ＝ｘ Ｙ ｈ＝ｈ （Ｙ ｈ） Ｃ ｆ ｘ ｙ＝ｆ ｙ ｘ Ｂ ｆ ｇ ｘ＝ｆ （ｇ ｘ） cond ｐ ｘ ｙ＝x, ただしｐが真の場合 y, ただしｐが偽の場合 plus ｍ ｎ＝r, ただしｍとｎとは既に数にまで還
元され（reduced）ていなくてはならず、ｒはｍとｎの
合計である。

他の結合子およびそれらの定義は上に引用されたTurn
erの著書の中に見られるはずである。

この結合子表示は便宜上２分有向グラフとして表わす
ことができる。その場合、各ノードは関数を引数に作用
させることを表わす。（これらのグラフは最初の２つの
結合子の名前からSK−グラフとして知られる。）置換規
則はそのためグラフ変換規則として解釈することもで
き、これらのグラフ（およびそれゆえ、それらが表わす
プログラム）は縮小として知られる処理中にかなり単純
な性質のプロセッサによって評価することができる。そ
のような縮小プロセッサは「変数を含まない関数型言語
コードを用いる樹形のグラフとしてストアされたプログ
ラムを実行するための縮小プロセッサ（Reduction Proc
essor for Executing Programs Stored as Treelike Gr
aphs Employing Variable−Free Applicative Language
Codes）」と題されるBolton等のアメリカ特許番号第4,
447,875号で開示される。

縮小処理の詳細はTurnerの書類で見られるが、簡単に
具体例をあげておくことも有用である。第1A図ないし第
1D図はSASLプログラムを表わすグラフの縮小を例示す
る。

（successor x ＝ 1＋ｘである場合） successor 2 このプログラムは第1A図のグラフで表わされる結合子
の表現 CI2（plus 1） に解釈（コンパイル）される。このグラフをさらに変換
することで以下が得られる。

I （plus 1）2 C規則を用いる（第1B図） plus 1 2 Ｉ規則を用いる（第1C図） ３ plus規則を用いる（第1D図） グラフを縮小させるために行なわれる置換は、ポイン
タおよび結合子コードのような多数の異なるデータの操
作を必要とし、これらのデータはレジスタファイル内の
１つのロケーションからさらに別のロケーションにシフ
トされる。上に引用されたBolton等の出願で開示された
実施例では、各グラフ縮小段階はレジスタファイル転送
のシーケンスを必要とした。しかし多くの場合、レジス
タ間の必要な転送は同時に行なうことができ、その結果
速度を増大できるであろう。

これらの変形の１つを行なった後、プロセッサは次の
変換位置（「リデックス（redex）」と呼ばれる）を求
めてグラフ上を探索しなければならない。この探索の
間、ノードの検査が行われ、ノードの左側がポインタを
示すかまたは結合子を示すかを判定するといった様々な
検査が行なわれる。再び、Bolton等の出願で説明された
機械では、これらの検査はシーケンシャルに行なわれな
くてはならないが、多くの場合これらの検査は同時に行
なわれ得るであろう。

そこでこの発明の目的は、一連の置換を通して２分有
向グラフを評価するための、改良された処理システムを
提供することである。

この発明の別の目的は、レジスタ転送を同時に多数行
うことによって、各置換をより速く達成することができ
るプロセッサを提供することである。

この発明のさらに別の目的は、アロケータが、それぞ
れのグラフを評価する際に用いられる縮小プロセッサへ
転送するための新しいノードのアドレスを選択するよう
な、縮小プロセッサのためのアロケータおよびシステム
メモリを提供することである。

発明の要約 上で確認された目的を達成するために、この発明は関
数型言語縮小（reduction）プロセッサに用いるための
アロケータおよびシステムメモリにある。アロケータは
システムメモリに結合され、関数の置換に必要なシステ
ムメモリ上の新しいノードのアドレスを選択する。

この発明の特徴は２分有向グラフで表わされた関数型
言語プログラムを評価するように意図された縮小プロセ
ッサのためのアロケータおよびシステムメモリにある。

図面の簡単な説明 この発明の上記およびその他の目的、利点および特徴
は図面に関連して以下の明細書を検討することで容易に
明らかとなるであろう。

第1A、Ｂ、ＣおよびＤ図はこの発明が意図される型の
２分有向グラフを示す。

第２図はこの発明を採用するシステムを例示する。

第３図はこの発明のグラフマネージャセクションの図
である。

第４図はこの発明のデータセクションの図である。

第５図はこの発明の条件コンセントレータの図であ
る。

第６図はグラフが形成されるような型のノードのフォ
ーマットの図である。

第7A図ないし第7C図はこの発明のアロケータを詳細に
示す図である。

第8A図ないし第8B図はこの発明のシステムメモリの図
である。

発明の概略説明 この発明を用いるシステムを第２図に例示する。主た
る要素はグラフマネージャ10である。グラフマネージャ
10はデータセクションを含む。データセクションは、縮
小すべきグラフのいくつかのノードをキャッシュし、グ
ラフ縮小に必要な一連の置換を行なうためにそれらのノ
ードを操作することを可能にする。システムはグラフの
ノードのすべてに対する記憶領域を提供するシステムメ
モリ11と、使用されていないワードを求めてシステムメ
モリを走査し、グラフマネージャに使用可能なようにそ
れらのアドレスを待行列につなぐためのアロケータ12と
を含む。アロケータはまた、待行列につながれたアドレ
スの数のカウントを維持する。サービスプロセッサ13は
ホストプロセッサ（図示されていない）への非常に様々
なデータ転送を提供し、また、浮動小数点演算設備も備
える。

先行技術のシステムのグラフ縮小技術に関して何が特
に問題となるかは、第1A図ないし第1D図を再び参照すれ
ばよりよく説明出来るだろう。第1A図のグラフから第1B
図への変換において、ノードｂの右のセルの内容物をノ
ートａの右のセルに転送しなければならず、ノードｃの
右のセルをノードｆの左のセルに転送しなければなら
ず、ノードａの右のセルはノードｆの右のセルに転送し
なければならない。先行技術の縮小プロセッサでは、こ
の一連の転送はシーケンシャルに行なわれ、第1B図のグ
ラフを第1C図のそれに縮小し、また同様にさらにグラフ
を縮小していくために、同様の一連の転送が行なわれ
た。この発明の目的は並列レジスタ転送機構を提供し、
それによってレジスタ転送の各シーケンスを同時に行な
うようにし、そのようにして縮小処理の速度を上げるこ
とである。

先行技術のシステムに関するさらに別の問題は、縮小
処理の道筋を定める条件（condition）の検査に関す
る。第1A図のリデックスが変換され得る前には、プロセ
ッサは、いくつかの条件が成立するか否かを判定しなく
てはならない。先行技術のプロセッサでは、これらの条
件はシーケンシャルに検査され、各検査の結果は２方向
の分岐のうちの１つの経路を選択するのに用いられる。
この発明のさらに別の目的は、多方向の分岐の中から１
つの経路を選択するためにいくつかの条件を同時に検査
できるような条件検査機構を提供することである。

発明の詳細な説明 第２図のグラフマネージャ10を、そのアロケータ12と
の交信を含めて、第３図にわずかであるがより詳しく示
す。このグラフマネージャはデータセクション20、条件
コンセントレータ21および制御セクション22を含む。

データセクション20は縮小されるグラフの一部分をス
トアし、その内部の種々のレジスタの間をフィールドが
同時に転送されることを可能にする。これらのフィール
ドのいくつかの値は下に説明される理由で条件はコンセ
ントレータ21に送られる。このデータセクションは第４
図により詳細に示される。

制御セクション22は書込可能制御記憶22bを有する簡
単な状態機械であり、状態機械のためのマイクロプログ
ラムをストアする。マイクロ命令アドレスは、条件コン
セントレータ21から受取られた置換フィールドを制御レ
ジスタ22aの次アドレスフィールドとつなぎ合わせるこ
とによって発生される。その制御レジスタ22aは、選択
されたマイクロ命令を受取る。

第４図に例示される第３図のデータセクション20の機
構は、グラフの置換を行なうためにレジスタ間を並列転
送するための主要な機構であるレジスタファイル30を含
む。経路バッファ50もまた第４図に示され、これはレジ
スタファイル30にストアされたノードの「先祖」をスト
アするために用いられるスタックメモリである。第４図
の演算論理装置32は簡単な算術演算子を実行し、バスイ
ンターフェースユニット31はシステムメモリおよびシス
テムの他のユニットと交信する。

第３図の条件コンセントレータ21を、第５図により詳
細に説明する。条件コンセントレータ21は演算論理装置
32、アロケータ12およびサービスプロセッサ13から入力
を受け、さらにレジスタファイル30からの入力を受取
る。これらの入力は13個の「条件グループ」に分類され
る。各ガード発生器40aないし40mは、１組のガードに条
件グループを写像する。これは以下により詳細に説明さ
れる。検査サイクルの間、各ガート発生器はそのガード
のサブセットをガードバス41に向ける。このバスは優先
順位エンコーダ42への入力である16線のオープンコレク
タバスである。優先順位エンコーダの出力は４ビット幅
で、最高位の「真」の優先順位のガードを特定する。こ
の場合ライン０のガードが最高位の優先順位を有し、ラ
イン15のガードが最低位の優先順位を有するものとす
る。この出力は変位値として用いられ、これは第３図の
制御レジスタ22aからのベースアドレスとつなぎ合わさ
れて、制御記憶22b内の次のマイクロ命令のアドレスを
発生する。

ノードのフォーマット 上に示されるように、第６図はシステムメモリ11、レ
ジスタファイル30の種々のレジスタおよび経路バッファ
50内にあるSK−グラフのノードのフォーマットを例示す
る。各ノードは４ビットのノード型フィールド（NT）、
マークビットおよび各々が30ビットの左と右のセルのフ
ィールド（LCおよびRC）を含む。左および右のセルフィ
ールドはさらに、２ビットのセル型フィールド（CT）、
４ビットのサブ型フィールド（ST）および24ビットの内
容物フィールド（Ｃ）に細分される。種々のSK演算子お
よび値が、これらのフィールドの特別な値の組合わせで
コード化される。

アロケータおよびシステムメモリ 第２図のシステムメモリ11はノードのイメージおよび
それらに関連したマークビットをストアするために特に
設計されている。SK縮小の間、グラフにはノードが加え
られ、捨てられる。グラフに加えられるノードは新しい
ノードと呼ばれ、グラフから捨てられるノードはガーベ
ッジノードと呼ばれる。ガーベッジコレクションとは、
ガーベッジノードを集めて新しいノードとして再利用可
能とする処理である。この発明は２つの明確な段階、す
なわちマーク段階とその後の走査段階とからなるマーク
走査（Mark−Scan）アルゴリズムを用いる。

メモリの各ノードは上述したように、関連付けされた
マークビットを有する。マーク段階の間、アクティブな
グラフ全体が探索され、各ノードが検査されるたびに各
ノードのマークビットがセットされる。それゆえ、マー
ク段階の終了時には、そのグラフのノードと関連付けら
れたマークビットはセットされ、その他のマークビット
はリセットされていることになる。走査段階の間、メモ
リ内の全てのノードに対するマークビットがシーケンシ
ャルに走査される。各マークビットが一度検査される
と、以下の２つのうち１つの処置がとられる。

（１）もしマークビットがセットされているなら、関連
したノードはそのグラフ内にあり、再使用することはで
きない。マークビットは次のマーキング段階の準備とし
てリセットする。

（２）もしマークビットがセットされているなら、関連
したノードは縮小器（reducer）によって再使用でき
る。この場合このノードのアドレスを「セーブ」してお
き、将来縮小器が新しいノードを要求した場合にすぐ発
行できるようにしておかなければならない。これらの
「セーブされた」アドレスを新ノードアドレス（NNA）
と名付ける。

従来例では、縮小はすべてのマークビットが調べられ
た後に再び始められる。

この発明では、マーク段階は縮小を行なうのと同じプ
ロセッサ、すなわち第２図のグラフマネージャ10によっ
て行なわれる。しかし、走査段階は専用プロセッサのア
ロケータ12によって行なわれる。走査機能を果たすため
にはグラフマネージャ10が必要ではないので、グラフマ
ネージャ10は、マーク段階を完了するとすぐに縮小を再
び始めることができる。同時に、アロケータ12はマーク
されていないノードを捜してメモリを走査し始め、そう
したノードをグラフマネージャ10が使用できるように待
行列につなぐ。

走査段階が縮小と同時に行なわれるので、この実施例
におけるガーベッジコレクションの中断の実際の長さは
単にマーク段階で費される時間のみであり、従来例にお
けるよりも大いに短く、しかも（メモリのサイズではな
く）グラフのサイズのみに依存する。

上で述べたように、アロケータ12の目的は、縮小の間
に、再使用可能なノードのアドスレをグラフマネージャ
10に供給することのみである。アロケータ12は、メモリ
を走査して、関連付けされたマークビットがリセットさ
れたノードを求めることによりこれらのノードの位置を
特定する。これらのノードのアドレスは、グラフマネー
ジャに新ノードアドレスを供給するための待行列（ノー
ドキュー）に置かれる。

縮小の間は、アロケータ12およびグラフマネージャ10
の双方ともシステムメモリ11にアクセスする。アロケー
タ12はマークビットを読出しそしてリセットするためで
あり、グラフマネージャ10はノードにアクセスするため
である。メモリ競合を 減じるため、メモリ動作の特別
なセットがアロケータ12に利用可能である。これらの動
作は、アロケータ12がマークビットのみに関連があり、
ノードの内容物には関連がないので可能なのであるが、
マークベクトルへのアクセスを可能にする。マークベク
トルは８個のシーケンシャルなアドレスに存在するノー
ドのマークビットを含むビットベクトルである。マーク
ベクトルは通常のメモリアクセスにおける２クロック期
間ではなく、１クロック期間でアクセスできる。したが
って、この特別な動作を用いれば、アロケータは、８個
のマークビットに、16クロック期間ではなく１クロック
期間でアクセスすることができる。

第２図のアロケータ12は第7A図に、より詳細に例示さ
れる。アロケータ12は３つの機能ユニット、すなわち、
ベクトルフェッチャ70と、ベクトル検査器71と、ノード
キュー72とからなる。ベクトルフェッチャ70は第7B図
に、より詳細に例示される。

ベクトルフェッチャ70は、ベクトル検査器71に処理の
ためのマークベクトルを供給する。ベクトル検査器71が
ベクトルを要求するときはいつでも、ベクトルフェッチ
ャ70は第２図のシステムメモリ11からベクトルを読出
し、ベクトル検査器71に転送する。次にベクトルフェッ
チャは、システムメモリ11の、読出されたばかりのマー
クベクトルに対するマークビットをリセットするメモリ
動作を開始する。これにより、走査段階が終わると、走
査されたすべてのマークビットが確実にリセットされて
いることになる。ベクトルフェッチャ70は第7B図に、よ
り詳細に例示される。

マーク段階の間、第２図のサービスプロセッサ13は、
一旦走査段階が始まった場合に走査されるべきマークベ
クトルの数を第7B図の走査カウントレジスタ73にロード
する。マークベクトルが処理されるたびに、走査カウン
トレジスタ73はデクリメントされる。レジスタの値が０
に等しくなると、マークベクトルのフェッチングは終了
し、走査完了信号がアサートされる。このレジスタは21
ビット長である。また、マーク段階の間、第２図のサー
ビスプロセッサ13は、一旦走査段階が始まった場合に走
査されるべき第１のマークベクトルのアドレスをMVアド
レスレジスタ74にロードする。このレジスタはアドレス
の最上位の21ビットを含み（最下位の３ビットは常に零
に等しい。）、新しい各マークベルトがメモリから読出
される前にインクリメントされる。

ベクトルフェッチャ状態機械75はベクトルフェッチャ
の動作を制御する。上に述べたように、走査段階が始ま
る前に、MVアドレスレジスタ74および走査カウントレジ
スタ73にはそれらの初期値がロードされる。走査段階が
一旦始まると、ベクトルフェッチャ状態機械はMVアドレ
スレジスタ74によってアドレスされたマークベクトルを
読出す。ベクトルフェッチャ状態機械75はメモリのイン
ターフェース信号を操作することによってこの読出しを
行う。マークベクトルがデータバスDB（7:0）上に存在
するとき、状態機械75はBEGIN CHECK 信号をアサートし
て第7A図のベクトル検査器71に知らせる。

一旦マークベクトルがベクトル検査器71によって受取
られると、状態機械75はメモリインターフェース信号を
用いて、MVアドレスレジスタ74によってアドレスされた
マークベクトル内のマークビットをリセットするとい
う、さらに別のメモリ動作を実行する。リセット動作が
完了すると、状態機械75はベクトル検査器71からのCHEC
K OVER信号がアサートされて、ベクトル検査器71がさら
に別のマークベクトルを必要としていることを示すま
で、アイドルのままである。リセット動作と同時に、状
態機械75はMVアドレスレジスタ74をインクリメントし、
走査カウントレジスタ73をデクリメントする。もし走査
カウントレジスタ73が零でないなら、さらに別のマーク
ベクトルが以前に説明されたようにフェッチされる。も
し走査カウントレジスタ73が零なら、走査完了信号がグ
ラフマネージャにアサートされる。もし走査完了信号が
アサートされ、ENOUGH NODES信号がアサートされないな
ら、グラフマネージャはガーベッジコレクションを開始
する。

ベクトル検査器71は受取られた各ベクトルから８個ま
でのノードアドレスを発生する。これらのアドレスは発
生されると第7A図のノードキューに加えられる。ベクト
ル検査器71はもしノードキュー72からのFULL信号がアサ
ートされないなら、ベクトルフェッチャ70からマークベ
ルトを要求する。第7A図のベクトル検査器71は第7C図に
より詳細に例示される。

第7C図において、アドレスカウンタ76は新ノードアド
レス（NNA）の最上位の21ビットを格納する、単なるア
ップカウンタである。走査段階が始まる前に、アドレス
カウンタ76には第7B図のMVアドレスレジスタ74より１つ
少ない値に等しい値がロードされる。一旦走査段階が始
まると、第7A図のベクトルフェッチャがBEGIN CHECK
信号をアサートするごとに、アドレスカウンタ76はイン
クリメントされ、新しいマークベクトルがベクトルレジ
スタ77にロードされる。ベクトルレジスタ77は８ビット
幅のレジスタである。セット論理80の出力がこのレジス
タへの入力で、出力はエンコーダ78に行く。エンコーダ
78はベクトルレジスタ77の値に基づいた３ビット変位を
発生する。変位はベクトルのマークされていないビット
のうち最下位のものの順番位置に対応する。たとえば、
ベクトル 10010111 は３の変位を発生する。ベクトルに少なくとも１つのマ
ークされていないビットがある限り、新ノードアドレス
VALID信号がアサートされ、ベクトル検査器71からの新
ノードアドレスが有効で、かつキュー72にロードされる
べきことを第7A図のノードキュー72に示す。もしベクト
ルレジスタ77の出力がすべて１なら、エンコーダ78はCH
ECK OVER信号をアサートし、新しいマークベクトルがベ
クトルレジスタ77にロードされてもよいことをベクトル
フェッチャに示す。

変位レジスタ79は新ノードアドレスの最下位の３ビッ
トを格納するレジスタである。変位レジスタ79は、エン
コーダ78が新しい変位を発生するごとにロードされる。
24ビットの新ノードアドレスは３ビット変位レジスタと
21ビットアドレスカウンタ76とを単に連結したものであ
る。

セット論理80はBEGIN CHECK 信号の状態に依存して
２つのうちの１つの方法で動作する。もしBEGIN CHECK
信号がアサートされていれば、ベクトルレジスタ77に
ロードされるべきマークベクトルがデータバスDB（7:
0）上に存在する。ゆえに、セット論理80はベクトルレ
ジスタ77にロードするべく、マークベクトルを変化させ
ず単に通過させる。

もしBEGIN CHECK 信号がアサートされていないな
ら、セット論理80はベクトルレジスタ77の出力を選択
し、最下位の０のビットを１にセットし、新しい値をベ
クトルレジスタの入力に供給する。たとえば、ベクトル
レジスタ77が値 10010111 を含むなら、次のクロック信号によりベクトルレジスタ
77にロードされるべきセット論理80の出力は 10011111 となる。要するに、ベクトルレジスタ77の値は、レジス
タ内に少なくとも１つのマークされていないビット
（０）がある限り、各クロックごとにセット論理80によ
って変化させられる。ベクトルレジスタ77の値の各々に
対して、エンコーダ78は変位レジスタ79にロードされる
新しい変位を発生する。

第7A図のノードキュー72は第２図のグラフマネージャ
10により将来使用できるようにするために、新ノードア
ドレスをストアするために用いられる。ノードキュー72
は幅が24ビットで、深さが256エントリである。新ノー
ドアドレスが発生されると、それらはベクトル検査器71
によってキューにロードされ、必要となるごとに、グラ
フマネージャによってキューから取り除かれる。

ノードキュー72と関連したカウンタが、キューの中の
ノード数を監視し、また、２つの信号を発生するために
用いられる。FULL信号はキューがそれ以上いかなる新ノ
ードアドレスをも受取ることができないときにアサート
される。ベクトルフェッチャ70はFULL信号がアサートさ
れるまでマークベクトルをフェッチし続け、FULL信号が
アサートされるとメモリからマークベクトルを要求する
ことを停止する。その場合アロケータ12は一時的にアイ
ドルになり、再開するために十分な余裕がノードキュー
に生じるまで待機する。

ENOUGH NODES信号はキュー72に９個以上のノードがあ
るときにアサートされる。グラフマネージャ10が結合子
を実行する前には、この結合子の実行を完了するのに十
分な新ノードアドレスが存在するか否かを確かめるため
に、この信号を検査する。

第２図のシステムメモリ11は、要求を発生する３つの
回路要素、すなわちグラフマネージャ10、アロケータ1
2、および第8A図のリフレッシュ論理、のための様々な
演算をサポートする。各メモリアクセスに必要とされる
クロック数は、行なわれる動作の型により異なる。利用
可能なメモリ動作は以下のとおりである。すなわち、ノ
ードおよびマークビットを読出す（Read Node and Mark
Bit）。ノードおよびマークビットを読出し、次にマー
クビットをセットする（Read Node and Mark Bit, then
Set Mark Bit）。ノードおよびマークビットを読出
し、次にマークビットをリセットする（Read Node and
Mark Bit, then Set Mark Bit）。ノードを書込む（Wri
te Node）。マークベクトルを読出す（Read Mark Vecto
r）。マークベクトルをリセットする（Reset Mark Vect
or）。リフレッシュする（Refresh）。要求なし（No Re
quest）。

バスアービタ86の目的はシステムバスへのアクセスを
制御することである。バスは実際にはデータバスとアド
レスバスの２つのバスからなる。このバスは第２図の４
つの主要機能ユニットの間でデータを転送するために用
いられる。バス上の転送の大部分にシステムメモリ11が
関係する。それゆえ、単純にするために、バスへのアク
セスはシステムメモリ11が次の動作を実行する準備がで
きているとき（すなわちそれがアイドルであるとき）の
みに可能とされている。バスアービタはバス利用可能
（BUSAVL）信号をアサートすることによってバスが利用
可能であることを示す。

メモリタイミングおよび制御81は以下に説明される２
個の記憶アレイに制御情報およびタイミング信号を提供
する。タイミングおよび制御信号の発生は選択された動
作に依存する。

ノードのためのマークビットは、マークメモリ83にス
トアされる。これらのマークビットは行なわれている動
作の型に基づいて、２つの方法の内の１つによってアク
セスされ得る。マークメモリ83のマークメモリアレイ90
を第8Bにより詳細に示す。マークメモリアレイ90は、16
K×１の複数のスタティックRAMから形成される。各スタ
ティックRAMは、14のアドレス入力と、チップ可能化入
力と、書込可能化入力と、データ入力と、データ出力と
を有する。もしチップが選択され（すなわちチップ可能
化信号がアサートされ）、書込可能化信号がアサートさ
れると、データ入力の値が、アドレスされたロケーショ
ンにストアされる。チップが選択され、書込可能化がア
サートされないなら、アドレスロケーションにストアさ
れた値がデータ出力に出力される。チップが可能化され
ないなら、データ出力はトライステート素子により高イ
ンピーダンス状態とされ、RAMの内容物は変化しないま
まである。

第8B図は、ボード分割の様な付随的な複雑さを無視し
て、マークメモリがどのように構成されているかを機能
的に例示している。アドレスバスAB（17:3）からの14ビ
ットおよびMARK BIT IN 信号がメモリアレイのすべての
RAMに送られる。８個のRAMの各行は独自のチップ可能化
信号を有する。RAMの８列の各々は独自の書込可能化信
号を有し、かつデータ出力ラインを共有する。

デコーダ91は２進の重みが付けられた７つの入力AB
（23:17）を受取り、可能化されると、128個の相互に排
他的なアクティブロー出力（０−127）を与える。デコ
ーダ91はMARK MEMORY ENABLE信号がアサートされると可
能化される。デコーダ91が不能化されると、すべての出
力がアサートされない。たとえば、もしデコーダ91への
AB（23:17）入力が 0000010 と等しく、MARK MEMORY ENABLEがアサートされると、デ
コーダの３番目に下位の出力（２）がアサート（LOW）
され、その他すべてはアサートされない。

書込可能化発生器92は５つの入力信号の関数である８
個のアクティブローの書込可能化信号を与える。発生器
はMARK VECTOR OPERATION 信号の状態に依存して、２
つの方法のうち１つで動作する。MARK VECTOR OPERATIO
N 信号がアサートされている場合、書込可能化発生器7
2はAB（2:0）入力を無視し、MARK MOMORY WRITE 信号
がアサートされたときに、すべての８個の書込可能をア
サートする。MARK VECTOR OPERATION 信号がアサート
されていない場合、書込可能化発生器92はMARK MOMORY
WRITE 信号がアサートされたときには、８個の書込可
能化のうち１つだけをアサートする。AB（2:0）ライン
をデコードすることで、８個の書込可能化のどれがアサ
ートされるかが決定される。

マルチプレクサ93はデータ出力ラインの１つからMARK
BIT OUTPUT 信号の値を選択する。AB（2:0）ラインは
８個の出力ラインのどれが選択されるかを決定するため
に用いられる。

駆動ブロック94はMARK VECTOR READ信号によって制御
される８個のトライステードドライバを含む。MARK VEC
TOR READ信号がアサートされている場合、トライステー
トドライバが可能化され、８個のデータ出力ラインの値
をデータバスDB（7:0）に出力する。MARK VECTOR READ
信号がアサートされていない場合、ドライバは高インピ
ーダンス状態とされる。

第8A図のシステムメモリをアクセスするとき、グラフ
マネージャ10は、各マークビットが、その関連したノー
ドとともに（概念的にはそのノードの65番目のビットと
して）直接にストアされているものとみなす。マークメ
モリ83へのグラフマネージャのアクセスを可能にする２
つのシステムメモリ動作がある。両方ともマークビット
をまず最初に読出し、そして次にマークビットをセット
するか、リセットする。これらは単一のシステムメモリ
動作であると考えられるが、実際には２つのマークメモ
リ動作が行なわれる。マークビットは動作の第１のクロ
ックの間に読出されてストアされ、次に第２のクロック
の間にセットまたはリセットされる。マークメモリ83に
よって行なわれる、１つのマークビットのみにアクセス
する動作を単一ビット動作と呼ぶ。すべての単一ビット
動作に対して、MARK VECTOR OPERATION 信号はアサー
トされない。

マークメモリアドレスAB（23:17）の最上位の７ビッ
トは、メモリアレイ90のRAMの１行を選択するために第8
B図のデコーダ91によって用いられる。アドレスAB（16:
3）の次の下位14ビットは、選択された各RAM内の単一ビ
ットをアドレスするのに用いられる。MARK MOMORY WRIT
E 信号はアサートされず、メモリアレイ90の、アドレ
スされた８ビットをデータ出力ラインに転送することを
可能にする。メモリアドレスAB（2:0）の最下位３ビッ
トは、MARK BIT OUTPUT 信号のソースとしての８個の
出力ラインのうちの１つを選択するためにマルチプレク
サによって用いられる。MARK BIT OUTPUT 信号はグラ
フマネージャに与えられ、ストアされる。

単一ビット書込みは、マークメモリの単一ビットのセ
ットおよびリセット動作を実行するのに用いられる。メ
モリアドレスAB（23:17）の最上位の７ビットは、メモ
リアレイ90のRAMの１行を選択するためにデコーダ91に
よって用いられる。アドレスAB（16:3）の次の下位14ビ
ットは、選択された８個のRAMの各々の単一ビットをア
ドレスするために用いられる。MARK BIT IN 信号はセ
ット動作に対しては１、リセット動作に対しては０であ
る。MARK MOMORY WRITE 信号がアサートされると、８
個の書込可能化信号のうちの１つが強制的にアサートさ
れ、アドレスされたビットのうちの１つのみにMARK BIT
IN 信号の値が書込まれる。アドレスAB（2:0）の最下
位の３ビットが、書込可能化信号のどれがアサートされ
ているかを決定する。

第２図のシステムメモリ11にアクセスするとき、アロ
ケータ12は、各マークビットが８ビットマークベクトル
のメモリにストアされているものとみなす。アロケータ
12はこれらのマークベクトルを読出しまたはリセットす
る事ができる。アロケータ12によって与えられるアドレ
スは、最下位の３ビットが常に０であるので、８の倍数
である。第8A図のマークメモリ83によって行なわれる、
マークベクトルにアクセスする動作をマークベクトル動
作と呼ぶ。MARK VECTOR OPERATION 信号はすべてのマ
ークベクトル動作に対してアサートされる。

メモリアドレスAB（23:17）の最上位７ビットは、メ
モリアレイ90のRAMの１行を選択するためにデコーダ91
によって用いられる。アドレスAB（16:3）の次の下位14
ビットは、選択された各RAM内の単一ビットをアドレス
するために用いられる。MARK MOMORY WRITE 信号はア
サートされず、アドレスされた８ビットをメモリアレイ
90のデータ出力ラインへ転送可能にする。MARK VECTOR
READ信号はアサートされ、８個のデータ出力ラインの値
を、ドライバ94を介してデータバスDB（7:0）の最下位
の８個のライン上に出力する。アロケータは第7A図のベ
クトル検査器71内で、データバス上のデータをラッチす
る。

マークベクトル書込は、マークメモリリセット動作を
行なうのに用いられる。メモリアドレスAB（23:16）の
最上位の７ビットは、メモリアレイ90のRAMの１行を選
択するためにデコーダ91によって用いられる。アドレス
AB（16:3）の次の下位14ビットは、選択された８個の各
RAM内の単一のビットをアドレスするのに用いられる。M
ARK BIT IN 信号はリセット動作に対しては０である。
MARK MOMORY WRITE 信号がアサートされ、８個の書込
可能化信号のすべてが強制的にアサートされるように
し、アドレスされた８ビットのすべてにMARK BIT IN
信号の値か書込まれる様にする。これによりアドレスさ
れたマークベクトルがリセットされる。

第8A図のノードメモリ84は従来のメモリで、１ノード
幅である。ノードメモリ84はまた、エラー修正のために
１個のノードにつき８個の検査ビットを含む。エラー検
出および訂正器（EDC）85はノードメモリ84で発生する
可能性のあるいかなるエラーも検出し訂正するためのも
のである。これは64ビットワード毎に８個の検査ビット
をストアすることによって行なわれる。これらの検査ビ
ットを用いて、すべての単一ビットエラーを訂正でき、
すべての２ビットエラーおよびいくつかの多数ビットの
エラーを検出することもできる。

エラー訂正は性能を最大とするために「脇で（on the
side）」なされる。これは、修正前のデータが直接に
要求を発生した回路に戻され、それと同時にEDCによっ
て検査されることを意味する。エラーが検出された場
合、データ修正ができるようにメモリサイクルが延ばさ
れる。エラーの起こる可能性はわずかであるので、サイ
クルが延ばされることはほとんどなく、メモリは、訂正
機能を持たないメモリと同じ速度で働く。

結語 以上、変数を含まない関数型言語コードを用いる２進
のグラフとしてストアされるプログラムを評価する縮小
プロセッサのためのアロケータおよびシステムメモリを
説明してきた。これらのグラフはノードからなる。ノー
ドは物理的にはシステムメモリ内の記憶ロケーションで
ある。縮小処理の間、縮小プロセッサは新しいノードを
要求し、ノードまたは記録ロケーションを捨てる。メモ
リ内に存在する時、各ノードはその最上位ビットとして
マークビットを含む。マークビットは、セットされてい
ると、そのノードがグラフに用いられていることを示
し、リセットされていると、そのノードまたは記憶ロケ
ーションがグラフマネージャにより将来使用することが
可能であることを示す。

グラフマネージャおよびアロケータは連携して動作す
る。グラフマネージャは、縮小処理において使用するた
めに、メモリにストアされる種々のノードをマークし、
一方アロケータは、未使用の記憶ロケーションがあるか
どうかを見るために記憶ロケーションの選択されたグル
ープを走査し、次にこれらがグラフマネージャに使用で
きるように、キュー内にそれらの未使用記憶ロケーショ
ンのアドレスを置く。多数の記憶ロケーションを並列に
走査できるようにするために、システムメモリはノード
メモリおよびマークビットメモリに分割される。これに
より、どのノードロケーションがグラフマネージャによ
り使用可能かを決定するために、一連の記憶ロケーショ
ンのマークビットが並列に検査される。

この発明の１つの実施例だけを開示したが、特許請求
の範囲に記載の発明の精神および範囲から逸脱すること
なしに種々の変形および修正ができることは当業者にと
って明らかであろう。

フロントページの続き (72)発明者 ウイリアムズ，フランク・エイ，ジユニア アメリカ合衆国、78750 テキサス州、オ ーステイン ビツク・コート・コーヴ、 6310

Claims (10)

【特許請求の範囲】
1. 【請求項１】複数個の記憶ロケーションを持ったメモリ
   を有する処理システムにおける割当て装置であって、 各記憶ロケーションは、セットされている場合にはその
   記憶ロケーションが使用のために割当て済であることを
   示し、リセットされている場合にはその記憶ロケーショ
   ンが使用可能であることを示すマークビット位置を有
   し、 前記割当て装置は、 前記メモリに結合され、シーケンシャルな複数個の記憶
   ロケーションからマークビットを並行してフェッチする
   マークビットアドレス手段を含み、前記フェッチされた
   マークビットはマークビットベクトルを形成し、 前記マークビットアドレス手段に結合され、リセットに
   マークされたビットを探索するために前記マークビット
   ベクトルを検査するための検査手段と、 前記マークビットベクトル内のリセットにマークされた
   ビットによって示される記憶ロケーションのためのアド
   レスを形成するためのアドスレ形成手段とを含む、割当
   て装置。
2. 【請求項２】前記アドレス発生手段に結合され、前記発
   生された記憶ロケーションアドレスを受取るための待行
   列手段をさらに含む、請求の範囲第１項に記載の割当て
   装置。
3. 【請求項３】前記マークビットアドレス手段が、前記記
   憶ロケーションの前記マークビット位置に結合され、並
   列にフェッチされたマークビットをリセットするリセッ
   ト手段を含む、請求の範囲第１項に記載の割当て装置。
4. 【請求項４】前記マークビットアドレス手段が、前記記
   憶ロケーションからフェッチされるべきマークビットベ
   クトルの数のカウントを受取る走査カウント手段を含
   む、請求の範囲第３項に記載の割当て装置。
5. 【請求項５】マークビットベクトルを形成する複数個の
   マークビットの各々のフェッチの後に、前記マークビッ
   トアドレス手段をインクリメントし、そして前記走査カ
   ウント手段をデクリメントする手段をさらに含む、請求
   の範囲第４項に記載の割当て装置。
6. 【請求項６】複数個の記憶ロケーションを有するメモリ
   を有する処理システムにおいて、各記憶ロケーション
   は、セットされている場合にはその記憶ロケーションが
   割当て済であることを示し、リセットされている場合に
   はその記憶ロケーションが使用可能であることを示すマ
   ーグビット位置を有し、 前記記憶ロケーションに結合され、それらの記憶ロケー
   ションを割当てるように選択されたマークビットをセッ
   トするマークビットセッティング手段と、 複数個のシーケンシャルな記憶ロケーションからマーク
   ビットを並列にフェッチするマークビットアドレス手段
   と、選択されたマークビットはマークビットベクトルを
   形成し、 前記マークビットアドレス手段に結合され、リセットさ
   れたマークビットを探索して前記マークビットベクトル
   を検査する検査手段と、 前記リセットされたマークビットによって示される記憶
   ロケーションのためのアドレスを発生するアドレス発生
   手段とを含む、割当て装置。
7. 【請求項７】前記アドレス発生手段に結合され、前記発
   生された記憶ロケーションアドレスを受取るための待行
   列手段をさらに含む、請求の範囲第６項に記載の割当て
   装置。
8. 【請求項８】前記マークビットアドレス手段が、前記記
   憶ロケーションの前記マークビット位置に結合され、並
   列にフェッチされたマークビットをリセットするリセッ
   ト手段を含む、請求の範囲第６項に記載の割当て装置。
9. 【請求項９】前記マークビットアドレス手段が、前記記
   憶ロケーションからフェッチされるべきマークビットベ
   クトルの数のカウントを受取る走査カウント手段を含
   む、請求の範囲第８項に記載の割当て装置。
10. 【請求項１０】マークビットベクトルを形成する複数個
    のマークビットの各々のフェッチ後、前記マークビット
    アドレス手段をインクリメントし、そして前記走査カウ
    ント手段をデクリメントする手段をさらに含む、請求の
    範囲第９項に記載の割当て装置。