JPS6134631A - 整理編集プロセツサ - Google Patents
整理編集プロセツサInfo
- Publication number
- JPS6134631A JPS6134631A JP11964485A JP11964485A JPS6134631A JP S6134631 A JPS6134631 A JP S6134631A JP 11964485 A JP11964485 A JP 11964485A JP 11964485 A JP11964485 A JP 11964485A JP S6134631 A JPS6134631 A JP S6134631A
- Authority
- JP
- Japan
- Prior art keywords
- processor
- coupled
- cell
- registers
- signal line
- 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.)
- Granted
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/22—Microcontrol or microprogram arrangements
- G06F9/26—Address formation of the next micro-instruction ; Microprogram storage or retrieval arrangements
- G06F9/262—Arrangements for next microinstruction selection
- G06F9/264—Microinstruction selection based on results of processing
-
- 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/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/30003—Arrangements for executing specific machine instructions
- G06F9/30072—Arrangements for executing specific machine instructions to perform conditional operations, e.g. using predicates or guards
-
- 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/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/30094—Condition code generation, e.g. Carry, Zero flag
-
- 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/44—Arrangements for executing specific programs
- G06F9/448—Execution paradigms, e.g. implementations of programming paradigms
- G06F9/4494—Execution paradigms, e.g. implementations of programming paradigms data driven
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Devices For Executing Special Programs (AREA)
- Multi Processors (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
゛する 許出願
本願に直接的にまたは間接的に関連する米国特許出願は
以下のとおりである： ｆ ジ ） −／
ｑ 争 −−Ｇａｒｙ Ｅ、 Ｌｏａｓ
ｄｏｎ、 ｅｔ ａｔ、によって１９８４年６月５日に
出願され、かつ゛変数を含まない適応可能な言語コード
を用いる２進的に方向付けられたグラフとして記憶され
た整理編集プロセッナ評価プログラムに対する並列レジ
スタ転送機構（ｐａｒａｌｌｅｌ Ｒｅｇｉｓｔｅｒ
Ｔ ｒａｎｓｆｅｒ Ｍｅｃｈａｎｉｓｍｆｏｒ ａ
ＲｅｄｕｃＮｏｎ Ｐ ｒｏｃｅｓｓｏｒ Ｅ
ｖａｌｕａｔｉｒｉａＰ ｒｏｇｒａｍｓ Ｓ ｔｏ
ｒｅｄ ａｓ ３１ｎａｒｙ Ｄ １ｒｅｃｔｃｄＧ
ｒａｐｈｓ Ｅｍｆｌｌｏｙｉｒ＋ｇＶａｒｉａｂｌｅ
−ＦｒｅｅＡｐｐｌｉｃａｔｉｖｅ ｌ−ａｎａｕ
ａｇｅ Ｃｏｄｅｓ） ”と題された特許出願連続番号
第６１７，５３１号；およびＧａｒｙ Ｅ 、 Ｌｏ
ｇｓｄｏｎ、 ｅｔ ａｔ、によって１９８１年６月５
日に出願され、かつ゛変数を含まない適応可能な言語コ
ードを用いる２進的に方向付けられたグラフとして記憶
されたプログラムを評価する整理編集プロセッサに対す
るグラフマネジャー（Ｑ ｒａｐ！１Ｍ ａｎａｇｅｒ
ｆｏｒ ａ ＲｅｄｕｃｔｉｏｎＰ ｒｏｃｅｓ
ｓｏｒ Ｅ ｖａｌｕａｔｉｎｇ Ｐ ｒｏｇｒａ
ｍｓ ５ｔｏｒｅｄａｓ Ｂ １ｎａｒｙ ｏ １ｒ
ｅｃｔｅｄ Ｑｒａｐｈｓ Ｅｍｐｌｏｙｔｎ。
以下のとおりである： ｆ ジ ） −／
ｑ 争 −−Ｇａｒｙ Ｅ、 Ｌｏａｓ
ｄｏｎ、 ｅｔ ａｔ、によって１９８４年６月５日に
出願され、かつ゛変数を含まない適応可能な言語コード
を用いる２進的に方向付けられたグラフとして記憶され
た整理編集プロセッナ評価プログラムに対する並列レジ
スタ転送機構（ｐａｒａｌｌｅｌ Ｒｅｇｉｓｔｅｒ
Ｔ ｒａｎｓｆｅｒ Ｍｅｃｈａｎｉｓｍｆｏｒ ａ
ＲｅｄｕｃＮｏｎ Ｐ ｒｏｃｅｓｓｏｒ Ｅ
ｖａｌｕａｔｉｒｉａＰ ｒｏｇｒａｍｓ Ｓ ｔｏ
ｒｅｄ ａｓ ３１ｎａｒｙ Ｄ １ｒｅｃｔｃｄＧ
ｒａｐｈｓ Ｅｍｆｌｌｏｙｉｒ＋ｇＶａｒｉａｂｌｅ
−ＦｒｅｅＡｐｐｌｉｃａｔｉｖｅ ｌ−ａｎａｕ
ａｇｅ Ｃｏｄｅｓ） ”と題された特許出願連続番号
第６１７，５３１号；およびＧａｒｙ Ｅ 、 Ｌｏ
ｇｓｄｏｎ、 ｅｔ ａｔ、によって１９８１年６月５
日に出願され、かつ゛変数を含まない適応可能な言語コ
ードを用いる２進的に方向付けられたグラフとして記憶
されたプログラムを評価する整理編集プロセッサに対す
るグラフマネジャー（Ｑ ｒａｐ！１Ｍ ａｎａｇｅｒ
ｆｏｒ ａ ＲｅｄｕｃｔｉｏｎＰ ｒｏｃｅｓ
ｓｏｒ Ｅ ｖａｌｕａｔｉｎｇ Ｐ ｒｏｇｒａ
ｍｓ ５ｔｏｒｅｄａｓ Ｂ １ｎａｒｙ ｏ １ｒ
ｅｃｔｅｄ Ｑｒａｐｈｓ Ｅｍｐｌｏｙｔｎ。
Ｖａｒｉａｂｌｅ−ＦｒｅｅＡｌ）ｐｌｉｃａｔｔｖｅ
ＬａｎｇｕａｇｅＣＯｄｅＳ） ”と題された特許
出願連続番号筒６１７゜５２６号。
ＬａｎｇｕａｇｅＣＯｄｅＳ） ”と題された特許
出願連続番号筒６１７゜５２６号。
発明の背景
発明の分野
この発明は、２進的に方向付けられたグラフとして表わ
されたプログラムを評価するようにされたディジタルプ
ロセッサに対する並列レジスタ転送機構に関し、より特
定的には、同等のグラフの漸進的な置換によってそのよ
うなグラフを評価するプロセッサに関する。
されたプログラムを評価するようにされたディジタルプ
ロセッサに対する並列レジスタ転送機構に関し、より特
定的には、同等のグラフの漸進的な置換によってそのよ
うなグラフを評価するプロセッサに関する。
烈＃ｉ Ｍ ＊ （７） ｆＪ口止
今日の市場におけるほとんどのディジタルコンピュータ
は、Ｊ ｏｈｎ Ｖ ｏｎ Ｎ ｅｕｍａｎｎによっ
て最初に仮定されたタイプのものであり、それらはコマ
ンドの実行を逐次的に行なっている。ＦＯＲＴＲＡＮお
よびＣＯＢ ０１のような、コンピュータをプログラム
するための第１の高水準言語はこの構成を反映しており
、コンピュータによって実行されるべきアルゴリズムの
設計とともに記憶の管理および制御の流れの管理の責任
をプログラマに負わせていた。純ＬＩＳＰのような純粋
に適応可能な言語は、プログラマをこれらの管理の責任
から解放することだけ、無条件言語とは異なっている。
は、Ｊ ｏｈｎ Ｖ ｏｎ Ｎ ｅｕｍａｎｎによっ
て最初に仮定されたタイプのものであり、それらはコマ
ンドの実行を逐次的に行なっている。ＦＯＲＴＲＡＮお
よびＣＯＢ ０１のような、コンピュータをプログラム
するための第１の高水準言語はこの構成を反映しており
、コンピュータによって実行されるべきアルゴリズムの
設計とともに記憶の管理および制御の流れの管理の責任
をプログラマに負わせていた。純ＬＩＳＰのような純粋
に適応可能な言語は、プログラマをこれらの管理の責任
から解放することだけ、無条件言語とは異なっている。
純ＬＩＳＰに代わるものは、［） ａｖｉｄ Ａ 。
Ｔ ｕｒｎｅｒによって開発されたセイントアンドリニ
ーススタティックランゲツジ（３ａｉｎｔ Ａ ｎｄ
ｒｅｗｓＳｔａｔｉｃ Ｌａｎｏｕａｇｅ ）すなわち
Ｓ Ａ Ｓ ｌ−である（ Ｌ Ｌａｎ ｕａ
ｏｅ Ｍａｎｕａｌ、 ＬＪｎｔｖｅｒｓｉｔｙｏｒ
３ｔ、 Ａｎｄｒｅｗｓ、 １９７６ ）。゛コ
ンビネータ″と呼ばれるいくつかの定数を導入すること
によって、この言語は、変数を含まない表記法に変換さ
れる（Ｄ、 Ａ、 Ｔｕｒｎｅｒ、 ”Ａ Ｎｅｗ
Ｉ ｍｐｌｅｍｅｎｔａｔｉｏｎ Ｔｅｃｈｎｉｑｕ
ｅ ｆｏｒ ＡｐｐｌｉｃａＮｖｅＬ ａｎｇｕａ
ｇｅｓ”、 Ｓｏｆｔｗａｒｅ −Ｐｒａｃｔｉｃ
ｅ ａｎｄｘ ｅｒｉｅｎｃｅ Ｖｏｌ、 ９．
Ｄｒｌ、 ３１−４９． １９７９）。この表記法
は、（引数として関数を使用しかつ結果としてその関数
を戻す）高次関数および（１つまたはそれ以上の引数が
規定されていないときでさえ結果を戻す）厳密ではない
関数を取扱うのに特に有利である。
ーススタティックランゲツジ（３ａｉｎｔ Ａ ｎｄ
ｒｅｗｓＳｔａｔｉｃ Ｌａｎｏｕａｇｅ ）すなわち
Ｓ Ａ Ｓ ｌ−である（ Ｌ Ｌａｎ ｕａ
ｏｅ Ｍａｎｕａｌ、 ＬＪｎｔｖｅｒｓｉｔｙｏｒ
３ｔ、 Ａｎｄｒｅｗｓ、 １９７６ ）。゛コ
ンビネータ″と呼ばれるいくつかの定数を導入すること
によって、この言語は、変数を含まない表記法に変換さ
れる（Ｄ、 Ａ、 Ｔｕｒｎｅｒ、 ”Ａ Ｎｅｗ
Ｉ ｍｐｌｅｍｅｎｔａｔｉｏｎ Ｔｅｃｈｎｉｑｕ
ｅ ｆｏｒ ＡｐｐｌｉｃａＮｖｅＬ ａｎｇｕａ
ｇｅｓ”、 Ｓｏｆｔｗａｒｅ −Ｐｒａｃｔｉｃ
ｅ ａｎｄｘ ｅｒｉｅｎｃｅ Ｖｏｌ、 ９．
Ｄｒｌ、 ３１−４９． １９７９）。この表記法
は、（引数として関数を使用しかつ結果としてその関数
を戻す）高次関数および（１つまたはそれ以上の引数が
規定されていないときでさえ結果を戻す）厳密ではない
関数を取扱うのに特に有利である。
Ｔｕｒｎｅｒによって開発された実行手法は、プラス、
マイナスなどのような１組の原始関数と、高次の、厳密
ではない関数である１組のコンビネータとを用いる。こ
れらの演算子は、置換の規則によって形式的に定義され
、そのいくつかの例は以下のとおりである。
マイナスなどのような１組の原始関数と、高次の、厳密
ではない関数である１組のコンビネータとを用いる。こ
れらの演算子は、置換の規則によって形式的に定義され
、そのいくつかの例は以下のとおりである。
Ｓｆ ａ ｘ＋ｆ ｘ （（ｌ Ｘ）Ｋｘ
ｙ→Ｘ ■ ×→× Ｙ ｈ−＞ｈ（Ｙ ｈ） ｃｒ ｘ ｙ→ｒｙｘ Ｂｒ ｇ ｘ 今ｆ（ａｘ） ｃｏｎｄ ｐ Ｘ Ｖ＋Ｘ、Ｉ）が真の場合ｙ、
ｐが偽の場合 プラス ｍｎ→ｒ、ここで、ｍおよびｎは、すでにある
数まで減少さ れておらなければならず、 ｒはｍとｎとの合計であ る。
ｙ→Ｘ ■ ×→× Ｙ ｈ−＞ｈ（Ｙ ｈ） ｃｒ ｘ ｙ→ｒｙｘ Ｂｒ ｇ ｘ 今ｆ（ａｘ） ｃｏｎｄ ｐ Ｘ Ｖ＋Ｘ、Ｉ）が真の場合ｙ、
ｐが偽の場合 プラス ｍｎ→ｒ、ここで、ｍおよびｎは、すでにある
数まで減少さ れておらなければならず、 ｒはｍとｎとの合計であ る。
他のコンビネータおよびそれらの定義は、上述のＴ ｕ
ｒｎｅｒの刊行物において見出される。
ｒｎｅｒの刊行物において見出される。
このコンビネータの表記法は、２進的に方向付けられた
グラフとして都合良く表わされており、このグラフにお
いて、各ノードは、引数への関数の適用を表わしている
（これらのグラフは、最初の２つのコンビネータの名称
からＳＫ−グラフとして知られている）。この置換の法
則はその後、グラフ変換ルールとして理解されており、
これらのグラフ（それゆえに、それらが表わすプログラ
ム）は、非常に簡単な特性のプロセッサによって、整理
編集とて知られている処理において評価される。そのよ
うな整理編集プロセッサは、″′変数を含まない適応可
能な言語コードを用いるツリー状のグラフとして記憶さ
れたプログラムを実行するための整理編集プロセッサ（
ＲｅｄｕｃｔｉｏｎＰ ｒｏｃｅｓｓｏｒ ｆｏｒ
Ｅ ｘｅｃｕｔｔｎ（］ Ｐ ｒｏｏｒａｍｓＳｔｏ
ｒｅｄ ａｓ Ｔｒｅｅｌｉｋｅ Ｇｒａｐｈｓ Ｅ
ｍ１１１０１／１ｎｃｌＶａｒｉａｂｌｅ −Ｆ ｒｅ
ｅΔｐｐ＋＋ｃａｔ＋ｖｅ ＬａｎａｕａｇｅＣｏｄ
ｅｓ） ”と題された３ｏｌｔｏｎ ｅｔ ａｔ、によ
る米国特許第４．４／Ｉ７．８７５号において開示され
ている。
グラフとして都合良く表わされており、このグラフにお
いて、各ノードは、引数への関数の適用を表わしている
（これらのグラフは、最初の２つのコンビネータの名称
からＳＫ−グラフとして知られている）。この置換の法
則はその後、グラフ変換ルールとして理解されており、
これらのグラフ（それゆえに、それらが表わすプログラ
ム）は、非常に簡単な特性のプロセッサによって、整理
編集とて知られている処理において評価される。そのよ
うな整理編集プロセッサは、″′変数を含まない適応可
能な言語コードを用いるツリー状のグラフとして記憶さ
れたプログラムを実行するための整理編集プロセッサ（
ＲｅｄｕｃｔｉｏｎＰ ｒｏｃｅｓｓｏｒ ｆｏｒ
Ｅ ｘｅｃｕｔｔｎ（］ Ｐ ｒｏｏｒａｍｓＳｔｏ
ｒｅｄ ａｓ Ｔｒｅｅｌｉｋｅ Ｇｒａｐｈｓ Ｅ
ｍ１１１０１／１ｎｃｌＶａｒｉａｂｌｅ −Ｆ ｒｅ
ｅΔｐｐ＋＋ｃａｔ＋ｖｅ ＬａｎａｕａｇｅＣｏｄ
ｅｓ） ”と題された３ｏｌｔｏｎ ｅｔ ａｔ、によ
る米国特許第４．４／Ｉ７．８７５号において開示され
ている。
整理編集処理の詳細は、Ｔ ｕｒｎｅｒの論文において
見出されるが、簡単な例が有用である。第１八図ないし
第１Ｄ図は、５ＡＳＬプログラムを表わすグラフの整理
編集を描いている。
見出されるが、簡単な例が有用である。第１八図ないし
第１Ｄ図は、５ＡＳＬプログラムを表わすグラフの整理
編集を描いている。
サクセザ（５ｕｃｃｅｓｓｏｒ ） ２ここで、
サクセサＸ＝１＋Ｘ
このプログラムは、コンビネータの表現Ｃｌ２（プラス
１） に翻訳（コンパイル）され、この表現は、第１Ａ図のグ
ラフによって表わされている。このグラフの連続的な変
換は、次のものを生じる。
１） に翻訳（コンパイル）され、この表現は、第１Ａ図のグ
ラフによって表わされている。このグラフの連続的な変
換は、次のものを生じる。
Ｃルール（第１Ｂ図）を用いる、■（プラス１）■ルー
ル（第１Ｃ図）を用いる、プラス１２プラスルール（第
１Ｄ図）を用いる、３グラフを減少させるために実行さ
れる置換は、レジスタファイルにおける一方のロケーシ
ョンから他方のロケーションにシフトされる、ポインタ
およびコンビネータコードのような、いくつかの異なる
データの操作を要求する。上述の３０１ｔＯｎｅｔ ａ
ｔ、の出願において開示された実施例において、各グラ
フー整理編集ステップは、レジスターファイルの転送の
シーケンスを要求する。しかしながら、多くの場合、レ
ジスタ間で要求された転送は、結果として速度の増大を
もたらしながら、同時に実行され得る。
ル（第１Ｃ図）を用いる、プラス１２プラスルール（第
１Ｄ図）を用いる、３グラフを減少させるために実行さ
れる置換は、レジスタファイルにおける一方のロケーシ
ョンから他方のロケーションにシフトされる、ポインタ
およびコンビネータコードのような、いくつかの異なる
データの操作を要求する。上述の３０１ｔＯｎｅｔ ａ
ｔ、の出願において開示された実施例において、各グラ
フー整理編集ステップは、レジスターファイルの転送の
シーケンスを要求する。しかしながら、多くの場合、レ
ジスタ間で要求された転送は、結果として速度の増大を
もたらしながら、同時に実行され得る。
これらの変換のうちの１つを実行した後に、プロセッサ
は、次の変換の位置（“リデツクス（ｒｅｄｅＸ ）
”と呼ばれる）を求めてグラフを横切らなければならな
い。このサーチ期間中に、ノードは試験されかつノード
の左側がポインタまたはコンビネータを表わすかどうか
を判断するなどの、種々のテストが実行される。再度、
Ｂｏｌｔｏｎ ｅｔ ａｌ、の出願において開示された
装置において、これらのテストは逐次的に行なわれなけ
ればならないが：多くの場合、これらのテストは同時に
実行され得る。
は、次の変換の位置（“リデツクス（ｒｅｄｅＸ ）
”と呼ばれる）を求めてグラフを横切らなければならな
い。このサーチ期間中に、ノードは試験されかつノード
の左側がポインタまたはコンビネータを表わすかどうか
を判断するなどの、種々のテストが実行される。再度、
Ｂｏｌｔｏｎ ｅｔ ａｌ、の出願において開示された
装置において、これらのテストは逐次的に行なわれなけ
ればならないが：多くの場合、これらのテストは同時に
実行され得る。
この発明の目的は、一連の置換を介して２進的に方法付
けられたグラフの評価のための改善された処理システム
を提供することである。
けられたグラフの評価のための改善された処理システム
を提供することである。
この発明の他の目的は、いくつかの同時的なレジスタの
転送によって各置換が実行されるようなプロセッサを提
供することである。
転送によって各置換が実行されるようなプロセッサを提
供することである。
さらに、この発明の他の目的は、制御セクションがファ
イルを構成する各レジスタ間のレジスタ内容の特定の同
時転送を選択するような整理編集プロセッサに対する改
善されたレジスタファイルおよび制御セクションを提供
することである。
イルを構成する各レジスタ間のレジスタ内容の特定の同
時転送を選択するような整理編集プロセッサに対する改
善されたレジスタファイルおよび制御セクションを提供
することである。
１１匹」Ｌ
上述の目的を達成するために、この発明は、適応可能な
言語の整理編集プロセッサに用いるためのレジスタファ
イルおよび制御セクションに存する。この制御セクショ
ンは、レジスタファイルにおける種々のレジスタに結合
されて条件を検出しかつ関数の置換に必要とされる種々
のレジスタ転送を選択する。
言語の整理編集プロセッサに用いるためのレジスタファ
イルおよび制御セクションに存する。この制御セクショ
ンは、レジスタファイルにおける種々のレジスタに結合
されて条件を検出しかつ関数の置換に必要とされる種々
のレジスタ転送を選択する。
この発明の特徴は、２進的に方向付けられたグラフとし
て表わされる適応可能な言語のプログラムを評価するつ
もりである整理編集プロセッサに対する並列レジスタ転
送機構および制御セクションにある。
て表わされる適応可能な言語のプログラムを評価するつ
もりである整理編集プロセッサに対する並列レジスタ転
送機構および制御セクションにある。
この発明の上述のおよび他の目的、利点および特徴は、
図面に関連して以下の明細書を調べることによって容易
に明白となるであろう。
図面に関連して以下の明細書を調べることによって容易
に明白となるであろう。
日の 的な 明
この発明を利用するシステムは第２図に描かれている。
主要なエレメントはグラフマネジャー１０であり、これ
は減少されるべきグラフのいくつかのノードを蓄えかつ
これらのノードを操作さぜてグラフの整理編集に必要な
一連の置換を実行させるデータセクションを含んでいる
。このシステムは、グラフのノードのすべてに対する記
憶をもたらすシステムメモリ１１と、それが待機してい
るそのアドレスがグラフマネジャーによって用いられる
未使用のワードに対するシステムメモリをスキャンする
アロケータ１２とを含んでいる。このアロケータはまた
、待機されているアドレス数の計数値を維持する。サー
ビスプロセッサ１３は、ホストプロセッサ（図示せず）
への広範囲のデータ転送を支持し；それはまた浮動少数
点演算能力を提供している。
は減少されるべきグラフのいくつかのノードを蓄えかつ
これらのノードを操作さぜてグラフの整理編集に必要な
一連の置換を実行させるデータセクションを含んでいる
。このシステムは、グラフのノードのすべてに対する記
憶をもたらすシステムメモリ１１と、それが待機してい
るそのアドレスがグラフマネジャーによって用いられる
未使用のワードに対するシステムメモリをスキャンする
アロケータ１２とを含んでいる。このアロケータはまた
、待機されているアドレス数の計数値を維持する。サー
ビスプロセッサ１３は、ホストプロセッサ（図示せず）
への広範囲のデータ転送を支持し；それはまた浮動少数
点演算能力を提供している。
先行技術のシステムのグラフ整理編集手法に関する特定
の問題は、再度第１八図ないし第１Ｄ図を参照してより
良好に描かれている。第１Δ図におけるグラフの第１Ｂ
図におけるグラフへの変換において、ノードｂの右側の
セルの内容は、ノードａの右側のセルに転送されなけれ
ばならず、ノードＣの右側のセルは、ノードｆの左側の
セルに転送されなければならず、さらにノードａの右側
のセルはノードｆの右側のセルに転送されなければなら
ないということが評価されるであろう。先行技術の整理
編集プロセッサにおいて、この一連の転送は、逐次的に
実行され、同様の一連の転送が実行されて第１Ｂ図のグ
ラフを第１Ｃ図のグラフに減少させる。この発明の目的
は、レジスタ転送の各シーケンスがそれによって同時に
実行され整理編集処理の効率を高める並列レジスター転
送機構を提供することである。
の問題は、再度第１八図ないし第１Ｄ図を参照してより
良好に描かれている。第１Δ図におけるグラフの第１Ｂ
図におけるグラフへの変換において、ノードｂの右側の
セルの内容は、ノードａの右側のセルに転送されなけれ
ばならず、ノードＣの右側のセルは、ノードｆの左側の
セルに転送されなければならず、さらにノードａの右側
のセルはノードｆの右側のセルに転送されなければなら
ないということが評価されるであろう。先行技術の整理
編集プロセッサにおいて、この一連の転送は、逐次的に
実行され、同様の一連の転送が実行されて第１Ｂ図のグ
ラフを第１Ｃ図のグラフに減少させる。この発明の目的
は、レジスタ転送の各シーケンスがそれによって同時に
実行され整理編集処理の効率を高める並列レジスター転
送機構を提供することである。
先行技術のシステムに関する他の問題は、整理編集処理
を導く状態のテストに関している。第１Ａ図のリデック
スが転送され得る前に、プロセッサは、いくつかの条件
がホールドすることを判断しなければならない。先行技
術のプロセッサにおいて、これらの条件は逐次的にテス
１〜され、各テストの結果は、２−ウニイブランデの一
方の経路を選択するために用いられる。この発明の他の
目的は、いくつかの条件がそれによって同時にテストさ
れてマルチウェイブランチの単一経路を選択する条件テ
スト機構を提供することである。
を導く状態のテストに関している。第１Ａ図のリデック
スが転送され得る前に、プロセッサは、いくつかの条件
がホールドすることを判断しなければならない。先行技
術のプロセッサにおいて、これらの条件は逐次的にテス
１〜され、各テストの結果は、２−ウニイブランデの一
方の経路を選択するために用いられる。この発明の他の
目的は、いくつかの条件がそれによって同時にテストさ
れてマルチウェイブランチの単一経路を選択する条件テ
スト機構を提供することである。
、０のｉ−な１明
第２図のグラフマネジャー１０は、第３図においてより
詳細に示されており、アロケータ１２との通信を含んで
いる。このグラフマネジャーは、データセクション２０
と、条件コンセントレータ２１と、制御セクション２２
とを含んでいる。
詳細に示されており、アロケータ１２との通信を含んで
いる。このグラフマネジャーは、データセクション２０
と、条件コンセントレータ２１と、制御セクション２２
とを含んでいる。
データセクション２０は、減少されているグラフの一部
分をストアし、かつその中の種々のレジスタ間でフィー
ルドを同時に転送させる。これらのフィールドのうちの
いくつかの値は、以下に説明される理由で条件コンセン
トレータ２１に送られる。このデータセクションは、第
４図により詳細に示されており、さらにそのレジスタフ
ァイルは第７八図ないし第７Ｆ図において詳細に示され
ている。
分をストアし、かつその中の種々のレジスタ間でフィー
ルドを同時に転送させる。これらのフィールドのうちの
いくつかの値は、以下に説明される理由で条件コンセン
トレータ２１に送られる。このデータセクションは、第
４図により詳細に示されており、さらにそのレジスタフ
ァイルは第７八図ないし第７Ｆ図において詳細に示され
ている。
制御セクション２２は、ステー１〜マシンのためのマイ
クロプログラムがその中にストアされる書込可能な制御
ストローブ２２ｂを伴なった簡単なステートマシンであ
る。マイクロ命令アドレスは、条件コンセントレータ２
１から受取られた変位フイールドをつなぐことによって
発生し、制御レジスタ２２ａにおける次のアドレスフィ
ールドはさらに選択されたマイクロ命令を受取る。
クロプログラムがその中にストアされる書込可能な制御
ストローブ２２ｂを伴なった簡単なステートマシンであ
る。マイクロ命令アドレスは、条件コンセントレータ２
１から受取られた変位フイールドをつなぐことによって
発生し、制御レジスタ２２ａにおける次のアドレスフィ
ールドはさらに選択されたマイクロ命令を受取る。
第４図に描かれている、第３図のデータセクション２０
の構成は、レジスタファイル３０を含み、このレジスタ
ファイル３０は、グラフの置換を実行するレジスタ間の
並列転送に対する基本的な機構である。また、第４図に
示されているのは経路バッファ５０であり、これはレジ
スタフ、アイル３０にストアされたノードの前身をスト
アするために用いられるスタックメモリである。レジス
タファイルおよび経路バッファの双方は、第７八図ない
し第７Ｆ図に関連して以下により完全に説、明されてい
る。第４図の演算ロジックユニット３２は、簡単な演算
子を実行するが、バスインターフェイスユニット３１は
、システムメモリおよびシステムの他のユニットと通信
する。
の構成は、レジスタファイル３０を含み、このレジスタ
ファイル３０は、グラフの置換を実行するレジスタ間の
並列転送に対する基本的な機構である。また、第４図に
示されているのは経路バッファ５０であり、これはレジ
スタフ、アイル３０にストアされたノードの前身をスト
アするために用いられるスタックメモリである。レジス
タファイルおよび経路バッファの双方は、第７八図ない
し第７Ｆ図に関連して以下により完全に説、明されてい
る。第４図の演算ロジックユニット３２は、簡単な演算
子を実行するが、バスインターフェイスユニット３１は
、システムメモリおよびシステムの他のユニットと通信
する。
第３図の条件コンセントレータ２１は、第５図において
より詳細に説明されている。それは、演算ロジックユニ
ット３２、アロケータ１２およびサービスプロセッサ１
３から入力を受取るとともに、正規のファイル３０から
も入力を受取る。これらの入力は１３の゛条件グループ
″に分類される。各ガード（ｇｕａｒｄ ）ジェネレー
タ４０ａないし４０ｍは、条件グループを１組のガード
にマツピングする。これは、以下により詳細に説明され
る。テストサイクル期間中に、各ガードジェネレータは
、そのガードのサブセットをガードパス４１に向け、こ
のガードパス４１は、優先順位エンコーダ４２への入力
である１６−ラインのオープンコレクタバスである。優
先順位エンコーダの出力は４ビツト幅であり、最も高い
優先順位の真のガードを特定し、ここでライン０上のガ
ードは最も高い優先順位を有しており、ライン１５上の
ガードは最も低い優先順位を有している。この出力は、
第３図の制御レジスタ２２ａからのベースアドレスとつ
ながって制御記憶装置２２ｂにおいて次のマイクロ命令
のアドレスを発生する変位値として用いられる。
より詳細に説明されている。それは、演算ロジックユニ
ット３２、アロケータ１２およびサービスプロセッサ１
３から入力を受取るとともに、正規のファイル３０から
も入力を受取る。これらの入力は１３の゛条件グループ
″に分類される。各ガード（ｇｕａｒｄ ）ジェネレー
タ４０ａないし４０ｍは、条件グループを１組のガード
にマツピングする。これは、以下により詳細に説明され
る。テストサイクル期間中に、各ガードジェネレータは
、そのガードのサブセットをガードパス４１に向け、こ
のガードパス４１は、優先順位エンコーダ４２への入力
である１６−ラインのオープンコレクタバスである。優
先順位エンコーダの出力は４ビツト幅であり、最も高い
優先順位の真のガードを特定し、ここでライン０上のガ
ードは最も高い優先順位を有しており、ライン１５上の
ガードは最も低い優先順位を有している。この出力は、
第３図の制御レジスタ２２ａからのベースアドレスとつ
ながって制御記憶装置２２ｂにおいて次のマイクロ命令
のアドレスを発生する変位値として用いられる。
ノードフォーマット
上述のように、第６図は、ＳＫ−グラフのノードが、シ
ステムメモリ１１と、レジスタファイル３０の種々のレ
ジスタと、経路バッファ５０との中に存在するフォーマ
ットを描いている。各ノードは、４ビツトのノード−タ
イプのフィールド（ＮＴ）と、各３０ビツトの左および
右側のセルのフィールド（Ｌ ＣおよびＲＣ）とを含ん
でいる。
ステムメモリ１１と、レジスタファイル３０の種々のレ
ジスタと、経路バッファ５０との中に存在するフォーマ
ットを描いている。各ノードは、４ビツトのノード−タ
イプのフィールド（ＮＴ）と、各３０ビツトの左および
右側のセルのフィールド（Ｌ ＣおよびＲＣ）とを含ん
でいる。
左側および右側のセルのフィールドはさらに、２ビツト
のセル−タイプのフィールド（ＣＴ）と、４ビツトのサ
ブタイプフィールド（ＳＴ）と、２４ビツトの内容フィ
ールド（Ｃ）とに細別される。
のセル−タイプのフィールド（ＣＴ）と、４ビツトのサ
ブタイプフィールド（ＳＴ）と、２４ビツトの内容フィ
ールド（Ｃ）とに細別される。
種々のＳＫ演算子および値は、これらのフィールドの特
定の値の組合わせとしてコード化される。
定の値の組合わせとしてコード化される。
並列レジスター転送機Ｊ
第４図に描かれたデータセクションのレジスタファイル
３１は、相互接続ネットワーク５９の要約された表現と
ともに第７Δ図に詳細に示されている。総合的な相互接
続ネットワークを形成するようにその上に張られた実際
には４つのクロスバ−ネットワークであるネットワーク
５９の複雑さのために、この表現は要約されている。第
７Ｃ図ないし第７Ｆ図は、別々のクロスバ−ネットワー
クの各々に対する現実の出所および行先を示すテーブル
であり、第７Ｂ図は、以下により完全に示されるように
、これらのネットワークの複合物を表わすテーブルであ
る。
３１は、相互接続ネットワーク５９の要約された表現と
ともに第７Δ図に詳細に示されている。総合的な相互接
続ネットワークを形成するようにその上に張られた実際
には４つのクロスバ−ネットワークであるネットワーク
５９の複雑さのために、この表現は要約されている。第
７Ｃ図ないし第７Ｆ図は、別々のクロスバ−ネットワー
クの各々に対する現実の出所および行先を示すテーブル
であり、第７Ｂ図は、以下により完全に示されるように
、これらのネットワークの複合物を表わすテーブルであ
る。
レジスタＲ，ＦおよびＮＮＡを除いて、第７Ａ図のレジ
スタは、第６図に示されたタイプのノードを保持するよ
うに設計されている。バッファレジスタＢＯ−８３＜レ
ジスタ５１ａ −ｃ 、５２ａ−ｃ 、 ５３ａ −ｃ
、 ５４ａ −ｃ ）は、各々１つのノードをストア
し、さらに、通常は、減少されているグラフのリデック
スを含んでいる。レジスタＴ （５５ａ −Ｃ）はまた
、１つのノードをストアし、さらに複雑な変換期間中に
一時的な記憶手段として用いられる。前述のように、経
路バッフ１（５０ａ −ｃ ）は、データセクションに
おけるノードの前身であるノードを保持するために用い
られるスタックメモリである。この経路バッファは、最
大で２０４８のノードを保持することができる。
スタは、第６図に示されたタイプのノードを保持するよ
うに設計されている。バッファレジスタＢＯ−８３＜レ
ジスタ５１ａ −ｃ 、５２ａ−ｃ 、 ５３ａ −ｃ
、 ５４ａ −ｃ ）は、各々１つのノードをストア
し、さらに、通常は、減少されているグラフのリデック
スを含んでいる。レジスタＴ （５５ａ −Ｃ）はまた
、１つのノードをストアし、さらに複雑な変換期間中に
一時的な記憶手段として用いられる。前述のように、経
路バッフ１（５０ａ −ｃ ）は、データセクションに
おけるノードの前身であるノードを保持するために用い
られるスタックメモリである。この経路バッファは、最
大で２０４８のノードを保持することができる。
ＦおよびＲ（レジスタ５６および５７）は、各々１つの
セルをストアし、さらにグラフの通過期間中に主に用い
られ、ＮＮＡ（レジスタ５８）は、未使用のノードのア
ドレスをストアし、さらに２４ビツト幅である。
セルをストアし、さらにグラフの通過期間中に主に用い
られ、ＮＮＡ（レジスタ５８）は、未使用のノードのア
ドレスをストアし、さらに２４ビツト幅である。
これらのレジスタに加えて、レジスタファイル 。
の中へのおよびレジスタファイルから外へのいくつかの
バスが存在し、さらにこれらは第７Ｂ図ないし第７Ｆ図
において説明されている。バッファボート（ＢＰババス
０）は、バッファレジスタＢ３から経路バッファヘノー
ドを転送するのに用いられる双方向ボートである。ＢＰ
ババス０はまた、経路バッファからＢ３またはＴレジス
タファイルを転送するのに用いられる。どのサイ・クル
の期間中にも、ＢＰババス０は、データセクションの中
へまたはデータセクションの外へデータを転送すること
ができるが、双方を実行することはできない。
バスが存在し、さらにこれらは第７Ｂ図ないし第７Ｆ図
において説明されている。バッファボート（ＢＰババス
０）は、バッファレジスタＢ３から経路バッファヘノー
ドを転送するのに用いられる双方向ボートである。ＢＰ
ババス０はまた、経路バッファからＢ３またはＴレジス
タファイルを転送するのに用いられる。どのサイ・クル
の期間中にも、ＢＰババス０は、データセクションの中
へまたはデータセクションの外へデータを転送すること
ができるが、双方を実行することはできない。
データボート（ＤＰババス１）は、外部データバスとレ
ジスタファイルとの間でノードを転送するために用いら
れる双方向ボートである。このボートを含むデータ転送
は、データボートが出所および行先に同時になることが
できないということを除いて、レジスタとの転送と同じ
である。中でも、データボート６１は、システムメモリ
へのボートとして機能する。
ジスタファイルとの間でノードを転送するために用いら
れる双方向ボートである。このボートを含むデータ転送
は、データボートが出所および行先に同時になることが
できないということを除いて、レジスタとの転送と同じ
である。中でも、データボート６１は、システムメモリ
へのボートとして機能する。
アドレスポー１− （ＡＢババス２）は、内容フィール
ドをアドレスバスに転送するのに用いられる単方向ボー
トである。このボートにおけるデータは、システムメモ
リをアドレスするために用いられる。このボートを含む
データ転送は、アドレスボー１へが行先にしかなり得な
いということを除いて、レジスタとの転送ど同一である
。
ドをアドレスバスに転送するのに用いられる単方向ボー
トである。このボートにおけるデータは、システムメモ
リをアドレスするために用いられる。このボートを含む
データ転送は、アドレスボー１へが行先にしかなり得な
いということを除いて、レジスタとの転送ど同一である
。
新しいノードボート（ＮＮＰバス６４）は、ＮＮ△レジ
スタ５８を、その前身によってもたらされたアドレスで
満すために用いられる単方向ボートである。このボート
は、データセクションにおける他のどのレジタによって
もアクセスすることはできない。
スタ５８を、その前身によってもたらされたアドレスで
満すために用いられる単方向ボートである。このボート
は、データセクションにおける他のどのレジタによって
もアクセスすることはできない。
相互接続ネットワーク５９の機能は、もちろん、データ
セクションのレジスタおよびボートを相互接続すること
である。上述のように、第７Ａ図は、ネットワーク５９
が４つのクロスバ−ネットワークで現実に構成され、そ
の各々それ自身の出所、行先および制御の組を有してい
るというように要約されている。これらのクロスバ−の
１つにおける各行先は、その入力においてｎ−人力マル
チプレクサを有しており、ここでｎは、その行先□に対
する可能な出所の数に等しい。各マルチプレクサに対す
る別々の制御情報は、制御レジスタ２２ａによって与え
られる。この態様で、それぞれの行先は、その内容を同
時に受取り、さらにどのレジスタも１つ以上の行先に対
する出所となり得る。
セクションのレジスタおよびボートを相互接続すること
である。上述のように、第７Ａ図は、ネットワーク５９
が４つのクロスバ−ネットワークで現実に構成され、そ
の各々それ自身の出所、行先および制御の組を有してい
るというように要約されている。これらのクロスバ−の
１つにおける各行先は、その入力においてｎ−人力マル
チプレクサを有しており、ここでｎは、その行先□に対
する可能な出所の数に等しい。各マルチプレクサに対す
る別々の制御情報は、制御レジスタ２２ａによって与え
られる。この態様で、それぞれの行先は、その内容を同
時に受取り、さらにどのレジスタも１つ以上の行先に対
する出所となり得る。
相互接続ネットワークを構成する４つのクロスバ−ネッ
トワークは、ノードタイプ（第７Ｃ図）、セルタイプ（
第７Ｄ図）、サブタイプ（第７Ｅ図）および内容（第７
Ｆ図）ネットワークである。第７Ｂ図は、これらの４つ
のネットワークの複合物である。これらの図は、各ネッ
トワークの接続パターンを示している。行先は、テーブ
ルの最上部に表示された列である。出所はテーブルの行
を形成し、さらに左側に表示されている。Ｘは、出所と
行先との間の接続を示している。たとえば、第７Ｂ図に
おいて、ＮＮＡ列を下方に読んでいくと、第７Ａ図のＮ
ＮＡレジスタ５８が１つの出所、すなわちＮＮＰバス６
４のみを有しているということが判断され得る。逆に、
行を横切って読むことによって、いずれかの特定の出所
に対して許された行先が判断され得る。
トワークは、ノードタイプ（第７Ｃ図）、セルタイプ（
第７Ｄ図）、サブタイプ（第７Ｅ図）および内容（第７
Ｆ図）ネットワークである。第７Ｂ図は、これらの４つ
のネットワークの複合物である。これらの図は、各ネッ
トワークの接続パターンを示している。行先は、テーブ
ルの最上部に表示された列である。出所はテーブルの行
を形成し、さらに左側に表示されている。Ｘは、出所と
行先との間の接続を示している。たとえば、第７Ｂ図に
おいて、ＮＮＡ列を下方に読んでいくと、第７Ａ図のＮ
ＮＡレジスタ５８が１つの出所、すなわちＮＮＰバス６
４のみを有しているということが判断され得る。逆に、
行を横切って読むことによって、いずれかの特定の出所
に対して許された行先が判断され得る。
条件コンセントレータ
第５図に示された条件コンセントレータは、１６に達す
るガードを同時にテストし、このテストの結果に従って
マルチウェイブランチのうちから１つの経路を選択する
。マシンの他の部分からの信号は、１３の条件グループ
に分類され、これはガードジェネレータ４Ｑａ−ｍへの
入力として機能する。これらの信号の例は、データセク
ションレジスタＢＯ−８３（第７Ａ図にお（プるレジス
タ５１ａ −５４ａ ）からのノードタイプフィールド
、レジスタ８０．ＲＣ−Ｂ３．ＲＣ（レジスタ５１Ｃ−
５４，０）からのセル−タイプおよびサブタイプフィー
ルド、およびＡ Ｌ Ｕからの条件コードを含んでいる
。
るガードを同時にテストし、このテストの結果に従って
マルチウェイブランチのうちから１つの経路を選択する
。マシンの他の部分からの信号は、１３の条件グループ
に分類され、これはガードジェネレータ４Ｑａ−ｍへの
入力として機能する。これらの信号の例は、データセク
ションレジスタＢＯ−８３（第７Ａ図にお（プるレジス
タ５１ａ −５４ａ ）からのノードタイプフィールド
、レジスタ８０．ＲＣ−Ｂ３．ＲＣ（レジスタ５１Ｃ−
５４，０）からのセル−タイプおよびサブタイプフィー
ルド、およびＡ Ｌ Ｕからの条件コードを含んでいる
。
各ガードジェネレータは、その入力から１組のガードを
発生する。このガードは単に、選択された項の積のブー
ル代数の和である。たとえば、そのメンバーとして項Ａ
、ＢおよびＣを有する条件グループを考える。このグル
ープから発生し得るガードは、次のものを含む。
発生する。このガードは単に、選択された項の積のブー
ル代数の和である。たとえば、そのメンバーとして項Ａ
、ＢおよびＣを有する条件グループを考える。このグル
ープから発生し得るガードは、次のものを含む。
Ａ ＡＮＤ Ｂ ＡＮＤ Ｃ
Ａ ＯＲＢ ＯＲＣ
（Ａ ＡＮＤ Ｂ） ＯＲ（△ ＡＮＤ Ｃ＞（
／Ａ ＡＮＤ ／Ｂ） ＯＲ／Ｃ各ガードジェネ
レータ出力は、ガードパス４１における１６のラインの
うちの１つに接続されている。制御レジスタ２２ａから
の各ガードジェネレータへの制御入力は、能動化される
べき出力を選択する。ガードパス４１はオープンコレク
タバスであるので、いくつかのガードジェネレータは、
同一ライン上のガードを同時に能動化することができ、
これによって個別的な条件グループからの個々のガード
の総和であるガードを許容する。各ジェネレータにおけ
るガードに対する組合わせの方程式は、用いられる特定
のマイクロプログラムの関数であり、さらにマイクロプ
ログラムがコンパイルされるときに決定される。
／Ａ ＡＮＤ ／Ｂ） ＯＲ／Ｃ各ガードジェネ
レータ出力は、ガードパス４１における１６のラインの
うちの１つに接続されている。制御レジスタ２２ａから
の各ガードジェネレータへの制御入力は、能動化される
べき出力を選択する。ガードパス４１はオープンコレク
タバスであるので、いくつかのガードジェネレータは、
同一ライン上のガードを同時に能動化することができ、
これによって個別的な条件グループからの個々のガード
の総和であるガードを許容する。各ジェネレータにおけ
るガードに対する組合わせの方程式は、用いられる特定
のマイクロプログラムの関数であり、さらにマイクロプ
ログラムがコンパイルされるときに決定される。
ガードバス４１は、優先順位エンコーダ４２への入力で
ある。このエンコードの出力は、バス４１上の最も高い
優先順位の真のガードを特定する４ビット変位４４であ
り、ここでラインＯは最も高い優先順位を有しておりか
つライン１５は最も低い優先順位を有している。この変
位は、制御レジスタ２２ａからのベースアドレスに結合
されて次のマイクロ命令のアドレスを得る。この方法で
、１６−ウェイに達するブランチが１つの命令サイクル
で実行され得る。
ある。このエンコードの出力は、バス４１上の最も高い
優先順位の真のガードを特定する４ビット変位４４であ
り、ここでラインＯは最も高い優先順位を有しておりか
つライン１５は最も低い優先順位を有している。この変
位は、制御レジスタ２２ａからのベースアドレスに結合
されて次のマイクロ命令のアドレスを得る。この方法で
、１６−ウェイに達するブランチが１つの命令サイクル
で実行され得る。
艶１
２進的に方向付けられたグラフとしてストアされた変数
を含まない適応可能な言語の表現を評価するのに用いら
れる並列レジスター転送機構および制御セクションが以
上のように開示された。この表現は、その結果が得られ
るまで一連の変換を介して減少される。整理編集処理期
間中に、プロセッサはメモリへおよびメモリからノード
を転送し、これらのノード上で種々のオペレーションを
実行する。このプロセッサはまた、メモリに新しいノー
ドを作り出しかつ未使用のものを削除することができる
。この発明ににると、各整理編集は、先行技術のシステ
ムよりもはるかに速いスデップで実行され得る。
を含まない適応可能な言語の表現を評価するのに用いら
れる並列レジスター転送機構および制御セクションが以
上のように開示された。この表現は、その結果が得られ
るまで一連の変換を介して減少される。整理編集処理期
間中に、プロセッサはメモリへおよびメモリからノード
を転送し、これらのノード上で種々のオペレーションを
実行する。このプロセッサはまた、メモリに新しいノー
ドを作り出しかつ未使用のものを削除することができる
。この発明ににると、各整理編集は、先行技術のシステ
ムよりもはるかに速いスデップで実行され得る。
この発明の一実施例が開示されたが、この発明の精神お
よび範囲から離れることなく、その中で変更および修正
がなされるということは当業者にとって明白であろう。
よび範囲から離れることなく、その中で変更および修正
がなされるということは当業者にとって明白であろう。
第１Ａ図、第１Ｂ図、第１Ｃ図および第１Ｄ図は、この
発明が向けられるタイプの２進的に方向付けられたグラ
フを表わす図である。 第２図は、この発明を用いるシステムを示す図である。 第３図は、この発明のグラフマネジャーセクションの図
である。 第４図は、この発明のデータセクションの図である。 第５図は、この発明の条件コンセントレータの図である
。 第６図は、グラフがそこから形成されるタイプのノード
のフォーマットを示す図である。 第７八図ないし第７Ｆ図は、この発明のレジスター転送
機構を詳細に示す図である。 図において、１０はグラフマネジャー、１１はシステム
メモリ、１２はアロケータ、１３はサービスプロセッサ
、２０はデータセクション、２１は条件コンセントレー
タ、２２は制御セクション、３０はレジスタファイル、
３１はバスインターフェイスユニット、３２は演算ロジ
ックユニット、４０ａ−ｍはガードジェネレータ、４１
はガードパス、４２は優先順位エンコーダ、５０は経路
バッファ、５９は相互接続ネッ１〜ワーク、６０はＢＰ
ババス６１はＤＰババス６２はＡＰババス６４はＮＮＰ
バスを示す。 特許出願人 バロース・コーポレーション昭和６０年８
月ｇ日 ２０発明の名称 整理編集プロセッサ ３、補正をする者 事件との関係 特許出願人 住所 アメリカ合衆国、ミシガン州、デトロイトバロ
ース・ブレイス （番地なし） 名称 バロース・コーポレーション 代表者 ポペット・ジョーンズ ４、代理人 住 所 大阪市北区天神橋２丁目３番９号 八千代第一
ビル６、補正の対象 図面全回 ７、補正の内容 淵墨を用いて描いた図面全回を別層のどＪ３す。 以上
発明が向けられるタイプの２進的に方向付けられたグラ
フを表わす図である。 第２図は、この発明を用いるシステムを示す図である。 第３図は、この発明のグラフマネジャーセクションの図
である。 第４図は、この発明のデータセクションの図である。 第５図は、この発明の条件コンセントレータの図である
。 第６図は、グラフがそこから形成されるタイプのノード
のフォーマットを示す図である。 第７八図ないし第７Ｆ図は、この発明のレジスター転送
機構を詳細に示す図である。 図において、１０はグラフマネジャー、１１はシステム
メモリ、１２はアロケータ、１３はサービスプロセッサ
、２０はデータセクション、２１は条件コンセントレー
タ、２２は制御セクション、３０はレジスタファイル、
３１はバスインターフェイスユニット、３２は演算ロジ
ックユニット、４０ａ−ｍはガードジェネレータ、４１
はガードパス、４２は優先順位エンコーダ、５０は経路
バッファ、５９は相互接続ネッ１〜ワーク、６０はＢＰ
ババス６１はＤＰババス６２はＡＰババス６４はＮＮＰ
バスを示す。 特許出願人 バロース・コーポレーション昭和６０年８
月ｇ日 ２０発明の名称 整理編集プロセッサ ３、補正をする者 事件との関係 特許出願人 住所 アメリカ合衆国、ミシガン州、デトロイトバロ
ース・ブレイス （番地なし） 名称 バロース・コーポレーション 代表者 ポペット・ジョーンズ ４、代理人 住 所 大阪市北区天神橋２丁目３番９号 八千代第一
ビル６、補正の対象 図面全回 ７、補正の内容 淵墨を用いて描いた図面全回を別層のどＪ３す。 以上
Claims (10)
- （１）変数を含まない適応可能な言語コードを用いる２
進的に方向付けられたグラフを表わす２−セルのノード
を受取る記憶手段を有し、各ノードのいくつかにおける
そのようなセルの１つは他方のノードの記憶アドレスを
含み、各ノードのいくつかにおける前記セルの他方は関
数の変数を表わすコードを含みかつ各ノードのいくつか
における前記セルの他方は関数の置換を特定する変数を
含まない演算子コードを含む整理編集処理システムにお
けるプロセッサであって、 前記記憶手段に結合されて関数の置換による整理編集の
ために前記複数のノードを受取る複数のレジスタと、 前記ノードを含む前記レジスタの種々のフィールドに結
合されてどの関数の置換が実行されるべきかを検出しか
つそこから変位アドレスを発生する条件テスト手段と、 前記条件検出手段に結合されて前記変位アドレスを受取
り１組の制御信号を検索して前記レジスタ間の転送を能
動化し前記関数の置換を完了する制御記憶手段とを備え
た、プロセッサ。 - （２）前記条件テスト手段は、それぞれ前記レジスタの
うちの選択されたものに結合されて複数の情報信号のう
ちの異なるものを受信しかつ前記制御記憶手段から受信
した制御信号に応答して前記情報信号の異なるブール組
合わせを発生する１組のブールロジック回路を含む、特
許請求の範囲第１項記載のプロセッサ。 - （３）前記条件検出手段は、最も高い優先順位の信号ラ
インから最も低い優先順位の信号ラインへの順序で配列
された１組の信号ラインを含み、前記信号ラインの各々
は前記ブールロジック回路の組のうちの選択されたもの
に結合される、特許請求の範囲第２項記載のプロセッサ
。 - （４）前記条件テスト手段は、前記信号ラインに結合さ
れて、前記ブールロジック回路の１つまたはそれ以上か
ら１組の信号を受取る最も高い優先順位の信号ラインを
検出しかつ前記ブールロジック回路の１つまたはそれ以
上によって能動化されている最も高い優先順位の信号ラ
インのランクの形で変位アドレスを発生する優先順位コ
ード化手段を含む、特許請求の範囲第３項記載のプロセ
ッサ。 - （５）各セルは、セルが、変数を含まない演算子コード
を有するかどうかを特定するセル−タイプのフィールド
を有し、 前記条件テスト手段は前記セル−タイプのフィールドに
結合されて変数を含まない演算子コードを検出する、特
許請求の範囲第４項記載のプロセッサ。 - （６）各セルは内容フィールドを含み、 前記条件テスト手段は前記フィールドに結合されて前記
内容フィールドの１つにおける演算子の特性を検出する
、特許請求の範囲第５項記載のプロセッサ。 - （７）変数を含まない適応可能な言語コードを用いる２
進的に方向付けられたグラフを表わす２−セルのノード
を受取る記憶手段を有し、各ノードのいくつかにおける
そのようなセルの１つは他方のノードの記憶アドレスを
含み、各ノードのいくつかにおける前記セルの他方は関
数の変数を表わすコードを含みかつ各ノードのいくつか
における前記セルの他方は関数の置換を特定する変数を
含まない演算子コードを含み、各セルはセル−タイプの
フィールドおよび内容フィールドを含む整理編集処理シ
ステムにおけるプロセッサであって、 前記記憶手段に結合されて関数の置換による整理編集の
ために前記複数のノードを受取る複数のレジスタと、 前記ノードを含む前記レジスタの種々の内容フィールド
に結合されて演算子コードの特性を検出しかつそこから
変位アドレスを発生する条件テスト手段と、 前記条件検出手段に結合されて前記変位アドレスを受取
り１組の制御信号を検索して前記レジスタ間の転送を能
動化し前記関数の置換を完了する制御記憶手段とを備え
た、プロセッサ。 - （８）前記条件テスト手段は、それぞれ前記レジスタの
うちの選択されたものに結合されて複数の情報信号のう
ちの異なるものを受信しかつ前記制御記憶手段から受信
した制御信号に応答して前記情報信号の異なるブール組
合わせを発生する１組のブールロジック回路を含む、特
許請求の範囲第７項記載のプロセッサ。 - （９）前記条件検出手段は、最も高い優先順位の信号ラ
インから最も低い優先順位の信号ラインへの順序で配列
された１組の信号ラインを含み、前記信号ラインの各々
は前記ブールロジック回路の組のうちの選択されたもの
に結合される、特許請求の範囲第８項記載のプロセッサ
。 - （１０）前記条件テスト手段は、前記信号ラインに結合
されて、前記ブールロジック回路の１つまたはそれ以上
から１組の信号を受取る最も高い優先順位の信号ライン
を検出しかつ前記ブールロジック回路の１つまたはその
以上によって能動化されている最も高い優先順位の信号
ラインのランクの形で変位アドレスを発生する優先順位
コード化手段を含む、特許請求の範囲第９項記載のプロ
セッサ。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US617532 | 1984-06-05 | ||
| US06/617,532 US4615003A (en) | 1984-06-05 | 1984-06-05 | Condition concentrator and control store for a reduction processor evaluating programs stored as binary directed graphs employing variable-free applicative language codes |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6134631A true JPS6134631A (ja) | 1986-02-18 |
| JPH073655B2 JPH073655B2 (ja) | 1995-01-18 |
Family
ID=24474018
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60119644A Expired - Lifetime JPH073655B2 (ja) | 1984-06-05 | 1985-05-31 | 整理編集プロセツサ |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US4615003A (ja) |
| EP (1) | EP0164997A3 (ja) |
| JP (1) | JPH073655B2 (ja) |
| CA (1) | CA1229174A (ja) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4644464A (en) * | 1984-06-05 | 1987-02-17 | Burroughs Corporation | Graph manager for a reduction processor evaluating programs stored as binary directed graphs employing variable-free applicative language codes |
| US4654780A (en) * | 1984-06-05 | 1987-03-31 | Burroughs Corporation | Parallel register transfer mechanism for a reduction processor evaluating programs stored as binary directed graphs employing variable-free applicative language codes |
| US4734848A (en) * | 1984-07-17 | 1988-03-29 | Hitachi, Ltd. | Combination reduction processing method and apparatus |
| US5053952A (en) * | 1987-06-05 | 1991-10-01 | Wisc Technologies, Inc. | Stack-memory-based writable instruction set computer having a single data bus |
| SE9002558D0 (sv) * | 1990-08-02 | 1990-08-02 | Carlstedt Elektronik Ab | Processor |
| DE4430195B4 (de) * | 1993-12-13 | 2004-09-23 | Hewlett-Packard Co. (N.D.Ges.D.Staates Delaware), Palo Alto | Verfahren zur Auswertung von Booleschen Ausdrücken |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS588358A (ja) * | 1981-07-07 | 1983-01-18 | バロース コーポレーション | 還元処理システムおよびその方法 |
| JPS60119642A (ja) * | 1983-11-30 | 1985-06-27 | Ricoh Co Ltd | 光情報記録再生装置 |
| JPS6134629A (ja) * | 1984-06-05 | 1986-02-18 | バロ−ス・コ−ポレ−シヨン | グラフマネジャー |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB1540299A (en) * | 1975-02-15 | 1979-02-07 | Mathematik Datenverarbeitung G | Computer employing reduction language |
| SU613401A1 (ru) * | 1976-07-07 | 1978-06-30 | Предприятие П/Я В-2892 | Запоминающее устройство |
| IT1134780B (it) * | 1980-12-18 | 1986-08-13 | Honeywell Inf Systems | Unita' di controllo microprogrammata con rete di salti multipli |
| US4459660A (en) * | 1981-04-13 | 1984-07-10 | Texas Instruments Incorporated | Microcomputer with automatic refresh of on-chip dynamic RAM transparent to CPU |
-
1984
- 1984-06-05 US US06/617,532 patent/US4615003A/en not_active Expired - Lifetime
-
1985
- 1985-05-31 JP JP60119644A patent/JPH073655B2/ja not_active Expired - Lifetime
- 1985-06-04 EP EP85303932A patent/EP0164997A3/en not_active Withdrawn
- 1985-06-04 CA CA000483113A patent/CA1229174A/en not_active Expired
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS588358A (ja) * | 1981-07-07 | 1983-01-18 | バロース コーポレーション | 還元処理システムおよびその方法 |
| JPS60119642A (ja) * | 1983-11-30 | 1985-06-27 | Ricoh Co Ltd | 光情報記録再生装置 |
| JPS6134629A (ja) * | 1984-06-05 | 1986-02-18 | バロ−ス・コ−ポレ−シヨン | グラフマネジャー |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH073655B2 (ja) | 1995-01-18 |
| EP0164997A3 (en) | 1989-08-30 |
| EP0164997A2 (en) | 1985-12-18 |
| CA1229174A (en) | 1987-11-10 |
| US4615003A (en) | 1986-09-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0010934B1 (en) | An information handling system | |
| US5999725A (en) | Method and apparatus tracing any node of an emulation | |
| US3978452A (en) | System and method for concurrent and pipeline processing employing a data driven network | |
| US5720006A (en) | Expert system inference circuit | |
| EP0237013A2 (en) | Adaptive instruction processing by array processor having processor identification and data dependent status registers in each processing element | |
| US4833619A (en) | Automatic logic design system | |
| JP2006509306A (ja) | 関係アプリケーションへのデータ処理システム相互参照用セルエンジン | |
| Kathail et al. | A multiple processor dataflow machine that supports generalized procedures | |
| JPH04127275A (ja) | Ｌｓｉ論理回路自動合成における組合せ回路のテクノロジーマッピング方式 | |
| JPH06342371A (ja) | 複数の命令を発行する装置および方法 | |
| US4654780A (en) | Parallel register transfer mechanism for a reduction processor evaluating programs stored as binary directed graphs employing variable-free applicative language codes | |
| Lindon et al. | An optimal implementation of broadcasting with selective reduction | |
| JPS6134631A (ja) | 整理編集プロセツサ | |
| US4644464A (en) | Graph manager for a reduction processor evaluating programs stored as binary directed graphs employing variable-free applicative language codes | |
| JPS6081641A (ja) | レジスタトレース方法 | |
| FI91107C (fi) | Tietojenkäsittely-yksikkö | |
| CA1182579A (en) | Bus sourcing and shifter control of a central processing unit | |
| Treleaven et al. | A recursive computer architecture for VLSI | |
| US5896526A (en) | Programmable instruction trap system and method | |
| Tavangarian | Flag-oriented parallel associative architectures and applications | |
| Dugan et al. | A study of the utility of associative memory processors | |
| Jørgensen et al. | Computer aided verification of lamport's fast mutual exclusion algorithm using colored petri nets and occurrence graphs with symmetries | |
| JP3737573B2 (ja) | Ｖｌｉｗプロセッサ | |
| CN101556627B (zh) | 用于验证电路的模型检测中的模型抽象方法及其系统 | |
| Jones | A formal semantics for a DataFlow Machine—Using VDM |