JPH05508725A - 構造演算用演算装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 構造演算用演算装置 本発明は、構造演算用演算装置に関する。以下においては、この演算装置をコア セルと呼ぶ。

発明の背景 コンピュータは、１９４０年代に発明された。その時以来、それは革命的な速度 で発展せしめられた。それにも拘らず、今日のコンピュータは、最初のものとほ とんと同じアーキテクチャを存する。

大部分の改良はハードウェアにおいてなされてきた。

ＶＬＳ　Ｉの導入およびリソグラフ技術の向上は、ワンチップコンピュータの製 造を可能にしたが、それはわずか５年前にはスーパーコンピュータと呼ばれてい たものである。大きさは指数関数的に縮小し、線幅は、今では１μｍより小とな っている。クロック速度およびアクティブトランジスタの数は、多くのオーダー の大きさ増大した。物理的制約により、恐らくは線幅の限界は０．２μｍとなる と思われる。

同じ期間中に、コンピュータのアーキテクチャは、シリコンの使用においては改 善されなかった。逆に、大部分のコンピュータは、速度の増大のために最適のシ リコン量よりも多くを使用してきている。

これら双方の事実は、次の５年間における単一プロセッサの速度の向上を停止せ しめると思われる。並列ブロセッサが導入されたが、複雑性の増大のためにハー ドウェアの経費が増大し、また、たいていの形式のプログラムにおいて、プログ ラミングの経費か非常に増大する。

相互の関連を見ると、ハードウェアの経費は縮小されたが、新システムのプログ ラミングの経費はかなり増大し、間もなく手におえな（なりそうである。

コンピュータは、ソフトウェアおよびハードウェアにおけるさまざまなユニット の複雑な集合体である。発展のさまざまな絶倒および段階が、特別の確立された 標準を作り出し、それらがシステム内において広く用いられている。この非一様 性のために、極めて多くのインタフェースが存在している。

性質および様式の異なる全てのこれらのインタフェースおよび絶倒は、使用者ま たはプログラマ−による機械の使用を困難にした。それは、多くの知識を要求し 、またプログラマ−は、複雑性のために隠れたエラーを導入する可能性がある。

しかし、最近、いわゆるリグクシ３ンブロセツザ（ｒｅｄｕｅｔｉｏｎ　ｐｒｏ ｃｅｓｓｏｒ）が発展しつつある。リダクションプロセッサは、演算式を含むあ る構造を有するプログラムを実行し、この構造はいくつかのりダクションステッ プにおいてリジュース（ｒｅｄｕｃｅ）される。従って、プログラムは、他の種 類のコンピュータにおけるように、与えられたシーケンスによっては実行されな い。

リダクションプロセッサを、ある限度の大きさを超えて発展させるのには、ある 困難が存在する。

プログラム言語の発展 最初の電子コンピュータの開発は、フォートラン、コボル、アルゴル、ベーシッ ク、パスカルなどの、この形式のコンピュータに適するいくつかのプログラム言 語の発展を開始せしめた。これらの言語は、主として、通常のコンピュータ、す なわちジョン・フォノ・ノイマンにより開発された原理に従って設計されたコン ピュータ、により順次実行されるべき指令または命令のシーケンスから成るプロ グラムを通常は与える事実により、命令型言語と呼ばれており、以下においては 通常型語とも呼ばれる。これらの言語の困難か増大するのに伴って、他の一連の 言語、リスプ、イスライム（ＩＳＷ［Ｍ）スキーム（Ｓｃｈｅｍｅ）　（リスプ の方言）、エムエル（ＭＬ）、ホープ（Ｈｏｐｅ）　、　ニスニーニスエル（Ｓ ＡＳＬ）　、などが開発された。これらの言語の開発の背後の原動力は、概念上 の簡単さであり、特定の機械はその設計に影響を及ぼさなかった。関数型言語が 注意を引くまでには、ある時間を要した。その１つの理由は、関数型プログラム の実行が低速度であったためである。その後の発展により、これらの関数型プロ グラムは、通常の形式のコンピュータによって実行されるのを目的とするもので はないが、ある場合には、通常のコンピュータによって実行される通常型（命令 型）言語のプログラムにおけると近い、または同じ、実行速度を示しうるように なった。

ソフトウェアの危機 関数型言語を発展させるための大きい努力を開始させたのは、命令型言語に係る 困難であった。人々は、１９７０年頃にソフトウェアの危機を唱え始めた。プロ グラムは、ますます複雑化し、しばしば多くのエラーを含有し、読むのが困難に なり、理解しにくくなり、特に修正が困難となった。１つの理由は、高レベルの 命令型言語がプログラミングを簡単化するはずであるという期待が高すぎたから である。これらの言語は、想像はど高レベルにはなかったのである。命令型言語 は、なお初期のコンビコータ、すなわちノイマン形コンピュータの基本思想に適 合しており、プログラミングのレベルは、依然として機械レベルにかなり近い。

関数型プログラム言語は、通常型プログラム言語の欠点のうちのあるものを軽減 するいくつかの性質を育する。

さらに進んだ情報および理解のためには、テキストとしてｒＦｕｎｃｔｉｏｎａ ｌ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｕｓｉｎｇ　５ｔａｎｄａｒｄ　ＭＬＪ、Ａｋｅ 　ＷｉｋｓｔｒＯｍ、Ｐｒｅｎｔｉｃｅ　）ｆａｌｌ　１９８７を参照されたい 。

本発明の目的および利点の完全な理解のためには、コンピユーテイングにおける 機能的なアプローチを構成するものの理解、特に、歴史的にもっと一般的な命令 型アプローチとの比較においての理解が、本質的に重要である。

「関数型アプローチＪという表現は、プログラムが関数型言語で書かれ、この言 語に特に適したハードウェアを含むコンピュータにおいて記憶されかつ実行され ることを意味する。同様に、「命令型アプローチ」という表現は、プログラムが 命令型言語で書かれ、命令型言語に適したハードウェアを含むコンピュータにお いて記憶されかつ実行されることを意味する。

しかし、関数型言語で書かれたプログラムを通常のコンピュータにおいて記憶し 、かつ実行することは可能である。その逆もまた可能である。すなわち、命令型 言語で書かれたプログラムは、関数型言語で書かれたプログラムの実行に適した コンピュータにおいて実行されうる。

関数型言語の性質 関数型言語で書かれたプログラムは、オブジェクトの性質の定義の組として、ま た計算規則として見られつる。

定義は宣言部分であり、計算規則、またはりダクションまたは書直し規則は、コ ンピュータが実行中に使用する演算部分である。関数型言語は、コンピュータに 対する高レベルのインタフェースをなし、それは、プログラマ−がコンピュータ のハードウェアに関連した細部を抽出し去ることを可能ならしめる。肯定的側面 効果として、関数型プログラムはしばしば、通常の命令型プログラムよりも短く 、かつ理解しやすい。関数型言語の主たる欠点の１つは、関数型プログラムが通 常のコンピュータにより実行されるためには、それが通常型言語に翻訳されなく てはならないことである。これは、コンパイラすなわち翻訳プログラムによって 行なわれてきた。関数型ブログラムを効果的に記憶しかつ実行するタスクのため の専用ハードウェアが存在していなかった事実により、関数型アプローチのある 利点が阻害されていたことは明ら本発明は、アクティブストレージ内に存在し、 以下においてコアセルと呼ばれる特定のアクティブメモリセルを提供することを 目的としており、このセルは、全ての種類のりダクションを行ないうる。一方、 アクティブストレージはまた、ある形式のりダクションの限定された部分のみを 行ないつる、他の形式のメモリセルをも含有する。数値演算は、コアセルに接続 された数値演算論理装置（数値ＡＬＵ）において行なわれうるが、実際のりダク ション演算はコアセル内において行なわれる。

本発明のもう１つの目的は、以下においてオブジェクトストレージと呼ばれる、 限定的メモリセルを含む好ましくは連想メモリ、と協働するコアセルであって、 情報転送のためにその連想メモリに直接接続されているセルはこのセルのみであ る、該コアセルを提供することである。

本発明のさらにもう１つの目的は、複数のレベルの表現を記憶しつるコアセルを 提供することである。コアセル内に記憶される表現内の基本命令は、コアセル内 において実行されるべきである。

本発明のもう１つの目的は、構造演算、すなわちコンピュータプログラムによっ て与えられた構造をリジュースする演算のためのコアセルを提供することである 。そのセルにおいては、セル内の表現のサイズは、実行に関係する表示グラフの 技に対応している。通常の種類のコンピュータは、構造演算の概念に基づく種類 のプログラム言語、例えばリスプ（リスプコリスト処理言語）または他の任意の 関数型または宣言型コンピュータ言語を用いる時に特に有利な、構造演算のため のコアセルを備えうる。言語リスプは、リストまたはリストから構成された構造 を取扱いかつ処理するのに特に適しており、例えばエキスパートシステムを作り あげるために、人工知能内において使用される。それはまた、記号式数学、ＶＬ ＳＩの設計、ロボット工学、自然言語理解、などにおいても使用される。その場 合、コアセルは、これらのリストを、書直しまたは／かつリジュースすることに より、処理する手段となりうる。

リダクシヨンによる実行 実行されるべきプログラムは、クロジャー（ｃｌｏｓｕｒｅ）　’の方向性グラ フによって表わされ、プログラムのそれぞれの部分はクロジャーによって表わさ れる。実行中に、クロジャーのこの方向性グラフは、使用されている言語のりダ ラシ３ン規則に従って次第にリジュースされる。

実行可能なりロジャーがなくなれば、プログラムの実行は終ったのである。クロ ジャーの方向性グラフは木構造と見なされ、その木の中のそれぞれのノード（ｎ ｏｄｅ）がクロジャーであり、最上部のノードはルーツ（ｒｏｏｔ）と呼ばれる 。この場合、リダクションによる実行は、通常は、本構造の下部を上にしてリジ ュースすることによって行なわれ、ルーツから最も遠い木の部分からリジュース して、ルーツまで進んで行く。この種の実行は、通常は、要求被部動形実行（ｄ ｅｍａｎｄ　ｄｒｉｖｅｎ　ｅｘｅｃｕｔｉｏｎ）と呼ばれる。すなわち、プロ グラムの他部分の実行の結果に依存するプログラム部分の実行は、その結果の得 られるまで延期される。

定義 以下には、本明細書において用いられる表現に関するリストと、それらの予定さ れた意味とをあげる。

エレメント　データ構造内の何か大きい部分リスト　エレメントの順序づけられ たシーケンスで、それぞれのエレメントはリ ストでありうる 挿入されたリスト　全体が１クロジヤー内に記憶されるほど小さいリストの部分 。

任意の長いリストを代表することを 可能にする。

クロジャー　プロセスを定める階層構造をもった全体。全てのクロジャーは、そ のク ロジャーを一意に定めるルーツを有 する。リダクション機械におけるリ ダクション作業は、クロジャーに対 して行なわれる。その機械の全状態 はりダクションにより変形される。

オブジェクトストレージ　オブジェクトを記憶するストレージセルを含むメモリ 。例えば連想メモ リ ストレージセル　オブジェクトストレージ内のセル。

それは、他のストレージセル内に記 憶されている他のセルクロジャーに 関連するセルクロジャーを記憶する。

セルクロジャー　ストレージセル内の内容ストレーノセルフィールド　ストレー ジセル内のフィールドクロツヤ−エレメント　ストレージセルフイールド内に記 憶されたデータエレメント クロジャー識別子　クロジャーを一意に指示するクロジャーセルエレメント 力！ニカルクロノヤー　それ以上リジュースされないクロジャー、すなわち、こ のセルクロジャ ーがさらにリジュースされなくては ならないようにリジュースされつる、 ある他のセルクロジャーを指示する いかなるクロジャー識別子をも含ま ないセルクロジャー 目標　実行されるべき、すなわちリジュースされるべきクロジャー 親（ｆａｔｈｅｒ）　値／ｆｆｒ示フィ一フィールド内くとも１つのクロジャー 識別子を有するク ロジャー 子（ｓｏｎ）　子を指示するクロジャー識別子ニよりもう１つのクロジャーにリ ンクし たクロジャー 子は親でもありうる。親は子でもありうる。子は１つより多くの親を有しうる。

親は１つより多くの子を存しつる。

クロジャー位置　クロジャーがルーツであるか、あるいはノードであるか ルーツ　りロジャーの木の中での最上部のクロジャーセル ノード　クロジャーの木の中でのルーツでないクロジャーセル ホエア（＊ｈｅｒｅ）　クロジャー位置を含有するストレージセルフイールド タイプ　セルクロジャー内のタイプコード、すなわち、オブジェクト、例えば命 令コード、の性質を表わすビットパ ターン レージ−（１ａｚｙ）　セルクロジャー内のエレメントで、それが実行可能であ るか、延期され た評価であるか、非アクティブであ るか、を指示する 識別子　ストレージセル内に記憶されているオブジェクトを示すのに用いられる 特殊な種類のクロジャーエレメント 環境　オブジェクトは、それらに同じ環境を与えることによりグループ化され つる 値／指示　クロジャーエレメントは、簡単な値、（ｖａｌｕｅ／ｄｅｓ、　）　 すなわち直接的表示、無、または他のクロジャーへの指示、すなわち間 接的表示、のいずれかを記憶する コアセル　本発明の構造演算装置。コアセルは、リジュース用クロジャーに係る 構造 演算を行ないつる 数値ＡＬＵ　基本的な数値および論理演算を行ないつる数値演算装置。コアセル は、 数値演算に数値ＡＬＵを用いる フルレジスタ　コアセル内の全平面を通って延長するレジスタ コアワード　コアセル内のフルレジスタの内容限定的レジスタ　値／指示タイプ のクロジャーセルエレメントを含む大きさの限定された 量の平面を通って延長するコアセル 内のレジスタ エレメントワード　限定的なレジスタ、または限定的レジスタと同じ延長を有す るフルレジ スタの部分、の内容 ナム（ｎｕｍ）ワード　値または指示を表わすエレメントワードの部分 タグワード　ナムワードにおける表示の特徴を示すタグを存するエレメントワー ドの 部分 リダクション　使用される特定のプログラム言語の規則に従ったクロジャーの書 直し／ 再構成 発明の要約 本発明の主要目的を達成するための、構造演算処理の方法は、 ａ）い（つかのレジスタ内にデータワードを記憶せしめるステップであって、そ れぞれのデータワードがマーク部分および情報部分を有し、該マーク部分が問題 となっているレジスタが使用されているか否かを示すマークを含む、前記データ ワードを記憶せしめるステップと、 ｂ）前記データワードがリスト内に配置されており、該リストのそれぞれを所定 数の前記レジスタに記憶せしめるステップであって、使用されているとのマーク を有する前記レジスタに記憶されている前記リスト内のそれぞれの前記ワードの 前記マーク部分が、前記リストの１つの少なくとも一部分が実際の前記レジスタ に記憶されていることと、一部分、を該実際のレジスタに記憶されている前記リ ストが、それがどのような種類のリストであるのか、また前記レジスタ内の前記 リストの配列のどこから前記リスト間の関係か明らかになるのか、についてのリ スト命令を含むことと、を示している、前記ステップと、Ｃ）前記レジスタを制 御し、かつ該レジスタに記憶されているリストに属する前記リスト命令を用いる ことにより、該リストを該レジスタ間において再配列し、前記リスト命令に従っ てレジスタ内容を入力／出力するステップと、を含む。

本発明の構造演算処理用の演算装置は、ａ）データリストの入力および出力のた めの少なくとも１つの入力／出力手段と、 ｂ）それぞれがデータワードを記憶するようにされたいくつかのレジスタであっ て、それぞれのデータワードがマーク部分および情報部分を有し、該マーク部分 が問題となっているレジスタが使用されているか否かを示すマークを含み、それ ぞれの前記リストが所定数の前記レジスタに記憶されつるようになっており、使 用されているとのマークを有する前記レジスタのうちのそれぞれの該レジスタの 前記マーク部分が、前リストの１つの少なくとも一部分が実際のレジスタに記憶 されていることと、一部分を該実際のレジスタに記憶されている前記リストが、 それがどのような種類のリストであるのか、また前記レジスタ内の前記リストの 配列のどこから前記リスト間の関係が明らかになるのか、についてのリスト命令 を含むことと、を示す前記いくつかのレジスタと、Ｃ）前記レジスタを制御し、 かつ該レジスタに記憶されているリストに属する前記リスト命令を用いることに より、該リストを該レジスタ間において再配列し、かつ前記リスト命令に従って レジスタ内容を入力／出力する制御装置と、２．前記レジスタ内に記憶されてい る前記リストを、リストの木であってそのリストの１つがルーツリストである該 リストの木として配置する請求項１記載の方法。

を含む。

リストは、好ましくはリストの木として前記レジスタ内に配置され、記憶されて おり、その木のリストの１つはルーツリストである。別個の識別子レジスタ内の 、記憶されたリストの木の識別子は、好ましくは記憶される。

記憶されたリストの木の環境は、別の環境レジスタに記憶されうる。前記水のル ーツリストは、好ましくは、記憶されるべき前記実際の木のレベルに依存して異 なったレジスタ内に配置される。あるレジスタは、１行の主レジスタを含むベー スレジスタのマトリックス内に配置される。ｌレベルのみを含む木は、好ましく は主レジスタ内に記憶される。２レベルを含む木で、そのルーツリストを存する ものは、好ましくは前記主レジスタ内に記憶され、そのブランチリストはベース レジスタ内に記憶される。補助レジスタと呼ばれる、余分のレジスタの組は、前 記マトリックスの外に配置されつる。３レベルを含む木は、好ましくは前記補助 レジスタ内に記憶され、そのエレメントの１つは、前記レジスタのマトリックス 内に記憶される。

リストの木のルーツリストは、エレメントに分割可能であり、とのような種類の りダクションを行なうべきかに関する情報は制御手段によりルーツリストの第１ エレメントから得られ、他のエレメントはリジュースされるべきデータを表わす 。前記ルーツリストの第１エレメント内の情報は、どのような種類の命令を実行 すべきかを推論するために＃御手段により用いられる命令コードを含むか、また は、前記ルーツリストの前記第１エレメント内の情報は、ファンクションの定義 を表わすリストの木のルーツを含み、その情報はルーツリストをリジュースする ために行なうべき動作を推論するために制御手段により用いられる。

前記ルーツリストの第１エレメント内の情報は、ファンクションの定義を表わす リストの木のルーツを含む。

■リスト内の最大ワード数は、好ましくは４である。

前記リストの木の最大深度は、好ましくは３レベルである。もし該深度が３レベ ルであり、もし前記レジスタ内に記憶されている前記ルーツリストのリスト命令 が、該ルーツリストが１つまたはそれ以上のブランチを有することを示していれ ば、制御手段は該ブランチの■つだけをレジスタ内に記憶せしめる。

構造りダクションは、ペースレジスタ内、またはベースおよび補助レジスタ内、 などのレジスタ内に配置されたデータオブジェクトに対して行なわれる。

前記レジスタのデータスタックは、好ましくはスライスされたように配置され、 それによって、それぞれのデータスタック内の同じ位置を有するそれぞれのスタ ックビットエレメントは、全ての前記レジスタに属する全てのスタックエレメン トを含む平面であって該レジスタが問題となっている平面上のスタックビットエ レメントを有している前記平面内において、互いにビット毎に接続されうるよう になっている。あるレジスタは、他のものより長いスタックを有するので、ある 前記平面は、長いレジスタに属するスタックビットエレメントのみを有する。

ペースレジスタと名づけられている少なくともいくつかのレジスタは、Ｎをある 整数として、ＮＸＮレジスタのマトリックスにおける、行および列をなして配列 されている。前記ペースレジスタのスタックエレメントは、ビット毎に相互接続 されている。前記ベースレジスタスタック内のそれぞれのビットにおいて、それ ぞれの列に対しては列ワイヤが備えられ、それぞれの行に対しては行ワイヤか備 えられ、同じ行および列番号を育する前記列ワイヤと前記行ワイヤとの間のそれ ぞれの交点には、制御可能なスイッチが備えられている。それぞれのペースレジ スタは、少なくともその最も近い行ワイヤおよび列ワイヤによる、制御可能なレ ジスタ接続を有する。接続は、前記行に沿ってと、前記列に沿ってとの双方にお ける、相隣るベースレジスタ間に設けられる。制御手段か、＄ＪＩ（ｉｌｌ可能 スイッチおよび制御可能なレジスタ接続を制御し、実行されるべき命令の種類に 依存して、少なくとも３種類の接続、すなわち、 ａ）１つのレジスタからもう１つのレジスタへの簡単な接続と、 ｂ）レジスタ間における、いずれの方向にも１つずつの、２つの別個の接続と、 Ｃ）レジスタ間における時間多重接続であって、２つの相次ぐ位相において、記 憶されているリストエレメントが１方向および他方向へ移送される前記時間多重 接続と、 の１つを行なう。

レジスタスタック内のそれぞれのセルは、好ましくは、ａ）内部１ビツトレジス タと、 ｂ）該１ビツトレジスタに接続可能な、少なくとも１つの内＃１ワイヤバスと、 Ｃ）少なくとも１つの内部的な、制御可能な接続であって、それぞれか、前記少 なくとも１つの１ワイヤバスの１つを、以下の素子、すなわち前記セルの外部の バス、前記レジスタスタックのもう１つのものに属するセルの１つ、の一方に接 続可能ならしめる、前記制御手段によって制御可能なスイッチを含む、前記接続 と、を含む。少なくとも１つの内部１ビツトレジスタは、インバータなどの人力 バッファ手段と、インバータなどの出力バッファ手段と、該バッファ手段間に接 続された制御可能スイッチと、を含む。前記入力バッファ手段および前記出力バ ッファ手段は、制御可能スイッチにより、別個に前記少なくとも１つの内部！ワ イヤバスに接続可能である。

前記レジスタの位置に依存して、レジスタセルのあるものは、前記内部レジスタ に対する前記接続の１つではない、少なくとも１つのその内部接続に固定的に接 続された固定値を育する。

前記部分レジスタ内の内容を比較するために比較器が接続され、比較結果を、ア クセスと呼ばれる外部バス内のワイヤへ供給する。

図面の簡単な説明 本発明のさらに完全な理解のため、また、本発明の他の諸口的および諸利点の理 解のためには、添付図面と共に以下の説明を参照されたい。添付図面において、 第１図は、本発明のコアセルを含むリダクションプロセッサの構造を概略的に示 し、 第２Ａ図は、セルクロジャーを記憶しうるストレージセルの実施例を示し、 第２８ＩＮから第２Ｄ図までは、本発明のコアセルの実施例内に使用されつるコ アレジスタを示し、第２Ｅ図は、コアセルの実施例内のコアレジスタの可能な配 置を示し、 第３Ａ図から第３Ｆ図までは、本発明のコアセル内における異なるデータストレ ージの形式を示し、第４図、第５図、および第６図は、本発明のコアセルの動作 の例を示し、 第７図は、本発明のコアセル内における、第１形式の動作平面の第１実施例のブ ロック図を示し、第８図は、第７図に示されている第１形式の動作平面に対する 、全ての形式の可能な接続を有する完全なレジスタセルの設計の実施例を概略的 に示し、第９ＡＩＮから第９Ｆ図までは、レジスタセル内において使用されるべ き、異なる種類の成分の例を示し、第１θ図および第１１図は、第７図に示され ている第１形式の動作平面内における、異なるレジスタセルの概略的設計を示し 、 第１２図は、本発明のコアセル内における、第２形式の動作平面（属性平面）の 第１実施例のブロック図を示し、 第１３図から第１５図までは、第１２図に示されている第２形式の動作平面内に おける、異なるレジスタセルの概略的設計を示し、 第１６図および第１７図は、レジスタ間の転送の２例を概略的に示し、 第１８図から第２４図までは、コアセル内におけるデータ移送の異なる例を示し 、 第２５図は、本発明のコアセル内における第１形式の動作平面の第２実施例のブ ロック図を示し、第２６図は、動作平面内のレジスタセルの＠２実施例の設計を 概略的に示す。

実施例の説明 第１図において、コアセルは、単一のりダクションプロセッサ、すなわち、もっ と複雑なりダクションプロセッサの一部分として備えられうる比較的に簡単なり ダクションプロセッサ、の実施例内に含まれているように示されている。このリ ダクションプロセッサの概略的構造は、第１図から明らかである。しかし、その 構造は、極めてさまざまなものでありうることに注意すべきである。

例えば、コアセルの異なる平面は、１チツプ上に並べて配置することもでき、ま たは、平行ではあるが異った層内に配置することもでき、この場合には概略的に 図示されているようになる。

第１図の単一のりダクションプロセッサは、いくつかのコアレジスタ３ｐを含む コアセル２ｐと、それぞれがセルクロジャーを記憶することができ且つまた好ま しくはりジュース用演算の限定された組を与えつる、複数のメモリストレージセ ルを含むオブジェクトストレージ４ｐと、もし第１図の単一リダクションプロセ ッサが、いくつかの単一リダクションプロセッサを含むもっと複雑なりダクショ ンプロセッサの一部分ならば、多重プロセッサ間の通信を実現するためのプロセ ッサ回路網のデータ転送手段５ｐと、を含む。データ転送手段５ｐは、セルクロ ジャーを他の単一プロセッサへ転送するために、そのセルクロジャーを一時的に 保持するようになっているいくつかのレジスタを含む。転送手段５ｐは、本発明 の実際のコアセルの一部分ではないので、これ以上それについては説明しない。

制御装置 前記プロセッサはさらに、コアセル２ｐ内のエレメントを制御するための制御装 置６ｐを含む。さらにそれは、数値ＡＬＵ　ｌｐを含む。制御装置６ｐは、論理 ゲートアレイであり、コアセルにより操作されるべきクロジャーの内容により制 御される。制御装置６ｐも数値ＡＬＵｌｐも、本発明の一部分ではない。従って 、これらは詳細には説明せず、これらへの、またこれらからの信号のみを、以下 に実施例と共に説明する。制御装置の設計に関するこれ以上の情報については、 Ｃａｒｖｅｒ　ＭｅａｄおよびＬｙｎｎ　Ｃｏｎｗａｙ著のテキストｒ　Ｉｎｔ ｒｏｄｕｃｔｉｏｎ　ｔｏ　ＶＬＳＩＳｙｓｔｅｍｓＪ　、Ａｄｄｉｓｏｏ　Ｗ ｅｓｌｅｙ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏｍｐａｎｙ、　１９８０を参照された い。

オブジェクトストレージ コアレジスタは、オブジェクトストレージ４ｐから導かれる構造を含む。オブジ ェクトストレージは、■レベル構造、すなわちセルクロジャーのみを記憶しつる 。コアレジスタは、ルベル構造、すなわちセルクロジャー、を転送するのに十分 な広さのバスにより、オブジェクトストレージに接続されている。しかし、コア セルは、３レベルのオブジェクト構造まで内容として含みつる。４つの場合が存 在する。すなわち、０，１．２、または３レベルのオブジェクト構造がコアセル 内に記憶されつる。

以下に説明されるように、もし３レベルのオブジェクト構造が記憶されるとすれ ば、その頂部レベル（ルーツ）およびそのブランチの１つのみが記憶される。そ うでなければ、全てのレベルが記憶される。

コアセル構造 コアセルは全体として、い（っかのコアレジスタ３ｐを含存する構造演算のため の演算装置である。コアレジスタは、リストの木を記憶する。それぞれのリスト は、ワードを含む。レジスタのあるもの、限定的レジスタ、はそれぞれエレメン トワードを記憶し、エレメントワードはナムワードおよびタグワードを含む。タ グワードは、ナムワードの表示の特徴を示す。例えば、もしナムヮードが値を表 わす場合は、タグワードはナムヮードに含まれる値の種類、例えばそれが整数で あるか、または浮動小数点数などであるか、を示す。コアセルは、それが備えて いるレジスタの数による、ある長さのリストを一時に処理しうるのみである。リ ストを記憶するために用いられるレジスタの数は、好ましくは４であり、これは 記憶されるリストが４エレメントまたはそれ以下を有しうろことを意味する。例 えば、レジスタは、３２ビツトを占有するナムワードと、６ビツトのタグワード とを含みうる。この場合には、４エレメントを存するリストは、好ましくは３８ ビツトの４倍を占有する。

しかし、任意の長さのリストも取扱われつる。しかし、その場合はそれぞれのそ のようなリストは、それぞれがコアセル内において処理されるべき最大の長さに 一致するか、またはそれよりも短い長さを有するいくつかのリストに、分割され なくてはならない。コアセルは、ある深度の木を一時に処理しつるのみである。

もっと大きい深度を有する木も処理されうるが、限定された深度を有する木の一 部分のみが、一時にコアセル内に記憶される。

すなわち、木の一部分を一時に処理しつるのみなのである。

固定された数のレジスタが、リストを記憶しつる。使用されないレジスタは特に 不使用としてマークされる。

リストの木は、計算を制御し、また行なうために用いられ、これは、制御装置６ ｐからのｍｓ下において、もし必要ならば数値ＡＬＵ　ｔｐと協働して行なわれ る。計算は、リストの水内の内容を書直すことによって行なわれる。

インタフェース二オブジェクトストレージーコアセル好ましくは連想メモリであ るオブジェクトストレージ４ｐと、コアセルとは、信号適応を行なう変換インタ フェース９ｐと、クロジャーの広さのバス８ｐ、すなわち、レジスタ平面ＮＵＭ に接続された部分的バス０ＢＪｖ（垂直オブジェクトバス）と、レジスタ平面Ｈ ＥＡＤに接続された部分的バスＴＡＧとを含むバス、従ってルベル構造を転送し つるバスと、により相互接続されている。インタフェース９ｐは、クロジャーの 広さのバスＯＢＪ　８ｐを経てのコアレジスタ３ｐからの信号を、オブジェクト ストレージ内のストレージセルに対して適する信号に、増幅して変換する。それ はまた、読取り動作におけるオブジェクトストレージからの信号を、コアセルレ ジスタに対し適合するように、増幅して変換する。

このインタフェースは、オブジェクトストレージ４ｐ内に配置されているように 示されているが、それは代わりにコアセルと共にも配置されつる。しかし、イン タフェース９ｐは、本発明のコアセルの一部分とみなされるべきものではないの で、ここでは説明しない。

コアセル平面 第１図から明らかなように、コアレジスタは、平面ＮＵＭ、ＨＥＡＤ％ＢＯＯＬ ＳＴＹＰＥ、ＬＡＺＹ。

ＣＬＯ３／Ｓ　ＩＭＰＬＥとして図示されているいくつかの部分に分けられてい る。異なる部分は、異なる数の平面を含む。第１図には、読みやすくするために わずがな平面のみを示した。以下においては、ＴＹＰＥ、ＷＨＥＲＥ、ＬＡＺＹ 、およびＣＬＯＳ／Ｓ　ＩＭＰＬＥの諸平面は、属性平面と呼ばれる。

ナムワードはレジスタ平面ＮＵＭ内に記憶され、タグワードはレジスタ平面ＨＥ ＡＤ内に記憶されうる。例えば、３２のＮＵＭ平面と６ＨＥＡＤ平面とが存在し つる。

第１図に示されているプロセッサの実施例においては、例えば、５つのレジスタ 平面ＴＹＰＥと、１つのレジスタ平面ＷＨＥＲＥと、２つのレジスタ平面ＬＡＺ Ｙと、１つのレジスタの平面ＣＬＯ３／Ｓ　ＩＭＰＬＥと、が存在する。これら の平′面内のコアレジスタ部分に与えられるべき情報は、以下の説明において明 らかにされ、そこでは、コアセルの動作も説明され、それは、該情報の実際の説 明の前に行なわれる。

コアセルの動作 コアセルの発展の背景を与えるために、本発明のコアセルの実際の発展以前に発 展せしめられ、我々の同時係属出願第・・・号にさらに説明されている、特定の オブジェクトストレージ４ｐの説明を参照する。しかし、本発明の構造演算用演 算装置はまた、もっと通常の種類の計算およびストレージ装置にも接続されうろ ことに気づくべきである。コアセルは構造演算のみを行なう装置であること、お よびそれは数値演算を行なうためには数値演算装置（数値ＡＬＵ）を利用するこ と、に注意すべきである。通常は、プロセッサは、数値演算と構造演算部分との 双方を行なう演算論理装置（Ａ　Ｌ　Ｕ）を備えており、この従来技術のＡＬＵ は、構造および数値演算のためにどのようにも相異なる機能部分に分割されてい ない。

従来のＡＬＵを使用する時に、コアセル内において行なわれる構造演算と同等の 演算を行なうためには、小さいプログラムが必要である。

オブジェクトストレージの能力 オブジェクトストレージ４ｐは、通常のＲＡＮ形メモリよりも実質的に多くの知 能を存する。それは連想的であり、通常のＲＡＮ形メモリによって提供される［ 読取りＪおよびｒ書込みＪよりも多くのサービスを提供することができる。

オブジェクトストレージはストレージセルに分割されており、そのそれぞれはい くつかのストレージエレメントを含む。提供されるサービスは高レベルのもので ある。

例えば、それは、ただ１つのメモリ命令を用いることによって、特定のデータエ レメントの全ての存在を、個々のストレージセル内のいかなる場所にあったとし ても発見し、その発見された特定のデータエレメントを広域的に、すなわちオブ ジェクトストレージ全体の中で、新しい値に書直すことができる。オブジェクト ストレージは連想的なものであるから、この書直しの動作は、影響を受けるスト レージセルの数に関係なく、物理的メモリサイクルの２サイクルによって行なわ れつる。

ストレージセル ストレージセルの実施例は、第２Ａ図に示されている。

それは、２種類のクロジャーエレメントを記憶することができ、記憶されるべき エレメントに特に適するストレージフィールドを含む。第２Ａ図においては、こ れらのフィールドは、それらの中に記憶されるべきエレメントと同じ名称を与え られている。

第１種のクロジャーエレメント 第り種のエレメントは、ストレージセルの相異なる状態を記述する。この種類の １つのエレメントはＬＡＺＹであり、これは、そのセルが、セルの残余の内容が 受動的情報であるｅｘｅｃ　ｔであるとみなされる、すなわち、実行可能な状態 にある場合の、アイドルにあるか、またはウェイトにある、すなわちセルの評価 が延期されていて、それが実行されうる前に結果を待ちつつある、かを示す。も う１つの第１種のエレメントはＴＹＰＥであり、これは形式コード（ｐａｒ、ｓ ｅｑ、ａｐｐｌｙ。

１ｉｓｔＳｕｎｉｆなど）を含む。これらの第１種のエレメントは、平面ＬＡＺ Ｙ、ＷＨＥＲＥ、およびＴＹＰＥ内に備えられたコアレジスタの部分内に記憶さ れるようになっている。しかし、コアセルには、ＣＬＯ３／ＳＩＭＰＬＥと呼ば れる余分の平面も備えられ、そこには、レジスタ内の情報がクロジャーであるの か、または単純な値であるのかが示される。応用によっては、他の平面も備えら れつる。

第２種のクロジャーエレメント 第２種のエレメントは、識別、環境、または値を記述する。これらは、ＩＤＥＮ Ｔ　ＩＦ　ＩＥＲ。

ＥＮＶ　ＩＲＯＮＭＥＮＴＳＶＡＬＵＥ／ＤＥＳであ６゜これら第２種のエレメ ントは、平面ＨＥＡＤおよびＮＵＭ内に備えられたコアレジスタの部分内に記憶 されるようになっている。これらのエレメントはそれぞれエレメントワードを含 み、エレメントワードは、コアセル内に平面ＮＵＭ内に記憶されるべきナムワー ドと、コアセル内の平面ＨＥ　Ａ　Ｄ内に記憶されるべきタグワードとに分割さ れる。応用によっては、他の平面も備えられうる。

タグワード 第２種のクロジャーエレメントはそれぞれ、ナムワードの特徴を示すタグワード を有する。タグには２種類、間接タグ、すなわち識別子および環境に用いられる タグと、直接タグ、すなわち単純な値などに用いられるタグと、が存在する。間 接タグの例は、ｅｌｓ、ｃａｎｏｎ。

およびｏｐｅｎである。もしタグワードがｃｌｓであれば、それは、ナムワード がリジュース可能なりロジャーを表わしていることを意味する。もしタグワード がｃａｎｏｎであれば、それは、ナムワードか、それ以上リジュースされえない クロジャーを表わしていることを意味する。もしタグワードがｏｐｅｎであれば 、それは、ナムワードが、クロジャーが挿入されたリストであることを表わして いることを意味する。直接タグの例は、ｄｉｓｃｒＳｃｏｎｔＳｕｎｕｓｅｄ、 およびｎｏｔｈｉｎｇである。もしタグワードがｄｉｓｃｒであれば、それは、 ナムワードが整数であることを意味する。もしタグワードがｃｏｎｔであれば、 それは、ナムワードが浮動小数点値であることを意味する。もしタグワードがｕ ｎｕｓｅｄであれば、それは、ナムワードが意味を欠いていることを意味する。

もしタグワードがｎｏｔｈｉｎｇであれば、それは、ナムワードが何も表わして いないこと、すなわち、何もマークされていないフィールドを含むクロジャーの 統合は、何も生じないことを意味する。応用によっては、他の間接的または直接 的タグワードも用いられうる。

識別子 もしストレージセル内の識別子フィールドが識別子エレメントを含んでいれば、 そのストレージセル内のセルクロジャーは、コアセルへ転送されつる。ストレー ジセルフイールドＶＡＬＵＥ／ＤＥＳは、それぞれ他のセルクロジャーを示す識 別子を含むことができ、それによって、この他のセルクロジャーへのリンクを与 える。記憶されているクロジャーの集められたものは、方向性グラフ、または識 別子によって結合されたセルクロジャーの木とみられうる。

環境フィールドは、回路網部分、すなわち、クロジャーの環境を与えるクロジャ ーの木、におけるルーツクロジャーを示す識別子を含みつる。しかし、環境フィ ールドは、他の用途をも有しつる。環境は、構造のクリエータ（ｃｒｅａｔｏｒ ）のトラックを、クリエートされた全てのセルクロジャーの環境内にそのクリエ ータの識別子を記憶することにより、保存するために使用されうる。例えば、内 部の同じ名称を有する全ての記号が同じものを表わすベき部分木（５ｕｂｔｒｅ ｅ）内の全てのクロジャーセルは、同じ環境を有することによりグループを形成 しうる。このようにして、構造全体は、１回の動作のみにより、木の中の１クロ ジヤーから、ルーツを経て、アクセスされうる。環境は、コアセル内において行 なわれる動作に影響を与えず、本発明の一部をなすものではないので、これ以上 それについては説明しない。

このようにして、もしクロジャーの環境が与えられれば、この環境内のルーツク ロジャーが見出される。環境のルーツクロジャーは、そのストレージセル内のフ ィールドＷＨＥＲＥ内に特定のマーク（例えば「ＩＪ）を備えている。環境のノ ードクロジャーは、フィールドＷＨＥＲＥ内に、他のマーク（例えば「ＯＪ）を 備えてコアセルの実施例内において使用されつるレジスタは、第２Ｂ図から第２ Ｄ図までに示され、コアセルの実施例内において使用されうるレジスタの配置は 、第２Ｅ図に示されている。

第２Ｂ図には、レジスタが示されている。この図は、レジスタがレジスタセルか ら構成されていることを示しており、それぞれのセルは１ビツトの情報を記憶す ることかできる。レジスタの描き方は、レジスタがコアセル内の相異なる平面を 貫いて延長し、それぞれのレジスタセルが１平面内にあることを示している。

第２Ｃ図は、コアセル内の全平面を貫いて延長するレジスタ、すなわちフルレジ スタを示す。この種類のレジスタは、ＮＵＭおよびＨＥＡＤ平面内に位置するレ ジスタセル内に識別子または値を保持しつる。それはまた、ＢＯＯＬＳＴＹＰＥ 、ＷＨＥＲＥ、ＬＡＺＹ、およびＣＬＯ３／Ｓ　ＩＭＰＬＥの諸子面内に位置す るレジスタセル内に、前述の状態を保持する。

第２Ｄ図は、コアセルのＮＵＭおよびＨＥＡＤ平面のみを貫いて延長するレジス タ、すなわち限定的レジスタを示す。

第２Ｅ図は、コアセルの実施例内におけるレジスタの可能な配置を示す。このコ アセルは、好ましくはペースレジスタマトリックスと呼ばれる、正方形をなして 配列されたペースレジスタを有する。これらのレジスタは、その辺の一方に沿っ た、主レジスタと呼ばれる主要行を有する。ペースレジスタの列は、副レジスタ と呼ばれ、それぞれ底部に１つの主レジスタを有する。コアセルにはさらに、識 別子レジスタおよび環境レジスタが備えられつる。ペースレジスタマトリックス の側部には、１列の補助レジスタが配置されている。

コアセルの実施例において、主レジスタ以外の全てのペースレジスタは、第２Ｄ 図に示されている種類のもの、すなわち限定的レジスタでありえ、第２Ｅ図の残 余のレジスタは、第２Ｃ図に示されている種類のもの、すなわちフルレジスタで ありうる。

コアセルのハードウェア構造のさらに詳細な説明の前に、第３Ａ図から第３Ｆ図 までを参照しつつ、さまざまなデータのストレージ形式の簡単な説明を行ない、 また、第４Ａ図から第４Ｈ図まで、第５Ａ図から第５Ｇ図まで、および第６Ａ図 から第６Ｇ１ｇまでを参照しつつその動作のいくつかの例を与える。

単純な値 第３Ａ図に示されているように、リダクションの結果である単純な値２５は、主 レジスタのうちの特定レジスタ内に置かれる。

ルベル構造 目標とは、リジュースされるためにコアセル内にロードされるもののことである 。第３Ｂ図に示されているように、通常は他のセルクロジャーに対する関連のな いクロジャーである、ルベルのみを含む目標は主レジスタ内に記憶される。例は 、簡単な数値演算、すなわち値１．２、および３の加算を示す。数値命令（＋） は第１主レジスタ内に記憶され、処理されるべきエレメントは他の主レジスタ内 に記憶される。

２レベル構造 第３Ｃ図に示されているように、２レベル構造を含む木は、主レジスタ内に水平 に記憶された、親であるルーツリストと、ペースレジスタ内に垂直に記憶された 、子であるリストと、を有する。この例においては、リスト表示（（１２）　（ ３４））を有する構造は、ペースレジスタマトリックス内に記憶されている。ル ーツリスト、すなわちサブリスト内の第１エレメントであるｌおよび３は、主レ ジスタ内に記憶され、子リスト、すなわち（１２）および（３４）は副レジスタ 内に垂直に記憶されている。この種類のストレージのその他の例は、以下に、例 えば第４図に関連して与えられる。

３レベル構造 第３Ｅ図に示されているように、３レベル構造を含む目標の木のルーツは、補助 レジスタの１つに記憶され、またその単一の子は、主レジスタ内に記憶される。

第３Ｄ図において、目標の木の、命令のトランスポーズ（Ｔｒ）であるルーツは 、補助レジスタの１つに記憶され、リスト（ｘｄ＋、ｔｄｔ、１ｄｔ）であるそ の子は、主レジスタ内に記憶されている。このリスト内のそれぞれのエレメント は、子を示す識別子である。第３Ｅ図において、これらの子はペースレジスタ内 に垂直にロードされており、そこではｉｄ＋は、それが示すリスト、すなわち（ １２３）と交換されており、またそこではｉｄ２は、それが示すリスト、すなわ ち（１１１２１３）と交換されており、またそこではｉｄｙは、それが示すリス ト、すなわち（２１２２２３）と交換さ第３Ｆ図に示されているように、バイブ ラインモードで記憶される木は、主レジスタ内に目標リストをロードされ、また 補助レジスタ内に目標の親をロードされ、その処理されるべき命令およびエレメ ントは、双方の種類のレジスタ内に記憶される。バイブラインモードの動作は、 好ましくは、数値表現をリジュースする時に用いられる。１つの利点は、中間結 果が、オブジェクトストレージの代わりにコアセル内に一時的に記憶されうるこ と第４Ａ図から第４Ｈ図までに示されている第１例は、リジュース可能なりロジ ャー ｕｎｉｆｙ（ｐａｒ（Ｉ　ｐａｒ　（１）　３）ｐａｒ　（Ｉ　ｐａｒ（１）　 ２）　）として与えられた並列値の単一化である。このリジュース可能なりロジ ャーは、単一化の並列構造として書き直されるべきものである。

第４Ａ図は、最初のりジュース可能なりロジャーを示す。第４Ｂ図は、このリジ ュース可能なりロジャーが、とのようにオブジェクトストレージ内に記憶される かを示す、ＦＪＡ図には、リジュース可能なりロジャーの異なる部分が記憶され るストレージセルが区画されている。

第４Ｂ図には、エレメントクロジャーと、セルクロジャーとの間のリンクが区画 されている。識別子ｉｄ＋を有するセルクロジャーは、タグｃｌｓを有し、かつ タイプフィールド内にタイプコードｕｎｉｆｙを存しており、識別子ｉｄｚ、ｓ 　ｄ　２　、およびｉｃＬを有するセルクロジャーは、それらのタイプフィール ド内にタイプコードｐａｒを有している。識別子ｉｄ＋を育するセルクロジャー は、その最初の２つの値／指示クロジャーエレメントとして、識別子ｉｄ、およ びｉｄ４を有するセルクロジャーへの指示を含む。これらのセルクロジャーのタ グはキャノンとなっている。識別子ｉｄｚを育するセルクロジャーの、第１およ び第３の値／指示クロジャーエレメントは、タグｄｉｓｃｒをもった離散値を有 し、また、その第２値／指示クロジヤーエレメントは、識別子ｔｄｚを有するセ ルクロジャーを指示し、従ってタグｃａｎｏｎを存する。識別子ｉｄｓを有する セルクロジャーの第１値／指示クロジヤーエレメントは、整数を与えられている ので、タグｄｉｓｃｒを有する。識別子ｉｄ４を有するセルクロジャーの、第１ および第３の値／指示クロジャーエレメントは、タグｄｉｓｃｒを有する離散値 を与えられ、また、その第２値／指示クロジヤーエレメントは、識別子ｘｄｘを 有するセルクロジャーを指示し、従ってタグｃａｎｏｎを有する。

第４Ｃ図に示されているように、識別子ｉｄ＋を存するセルクロジャーをもつス トレージセルの内容が、まずコアセル内にロードされて、その識別子がクロジャ ーのタイプコードｕｎｉｆｙを含めｉｄ、として識別子レジスタ内に配置され、 また、第１動作ステップにおいて、目標としての値／指示エレメントが主レジス タ内にロードされる。これが実際にどのように行なわれるかは第１８図に示され ており、さらに以下に説明される。

第４Ｄ［に示されているように、識別子ｉｄ２およびｉｄｔを存する子は、それ らの第１値／指示エレメントの内容か、その識別子によりマークされている主レ ジスタ内に配置されるように、ペースレジスタ内に垂直にロードされ、また、そ の値／指示エレメントの残余のものは、その上の垂直列内のレジスタ内にロード される。これらの子のそれぞれの、タイプコードｐａｒもまた主レジスタ内にロ ードされる。タイプコードは、ＴＹＰＥ平面内に位置するレジスタセル内にロー ドされる。

第４Ｅ図に示されているように、ペースレジスタの第１垂直列内の内容が主レジ スタ内に配置され、第２垂直列が主レジスタに平行なペースレジスタの行内に配 置されるように、ペースレジスタの内容は９０°トランスボーズされる。トラン スポーズ動作は第２３図に示されており、以下においてさらに説明される。識別 子レジスタと、主レジスタとに与えられているタイプコードのｐａｒとｕｎｔｆ ｙとは交換され、これは制御装置によって自動的に行なわれる。ここで、ペース レジスタは、諸列内に配置された３つの子を有する親を含む。それぞれの子は、 ここで、命令ｍａｋｅを用いて目的ストレージ内ヘロードし返される。オブジェ クトストレージからの応答として、記憶された子に対する識別子が、主レジスタ へ供給されて記憶される。一種のゲートアレイである制御装置６ｐが、特に諸レ ジスタの平面ＣＬＯ３／Ｓ　ＩＭＰＬＥからＴＹＰＥまでの中の内容を検出して 命令を行なう、すなわち、そこに見出されたｆＩｌ？に従ってスイッチおよびゲ ートを制御することを知るべきである。

子は、ｉｄ＋以後のシーケンスの順に命名され、既に６存されている名称は用い られない。しかし、名称の順序は重要ではなく、従って任意でありうる。

第４Ｆ図に示されているように、第１子は識別子ｉｄｚを得、識別子ｆｄｔを６ 育しているエレメントクロジャーを含存する第２子は、識別子ｉｄ４を得、第３ 子は識別子ｉｄｓを得る。識別子ｉｄｚ、ｉｄａ、ｉｄｓを有するセルクロジャ ーにリンクしたエレメントクロジャーを有する親は、その識別子ｉｄ＋を保持し 、次にオブジェクトストレージ内に記憶される。

第４Ｇ図は、リジュース可能なりロジャーｐａｒ（ｕｎｉｆｙ（１１）ｕｎｉｆ ｙ（ｐａｒ（１）　ｐａｒ（１））ｕｎｉｆｙ（２３））を記憶しているストレ ージセルを示す。このリジュース可能なりロジャー自体は、第４Ｈ図に示されて いる。第４Ｇ図および第４Ｈ図は、第４Ａ図および第４Ｂ図と同様に示されてお り、従って自己説明的になっている。

第４Ｇ図にはまた、タイプコードｕｎｉｆｙを有するセルクロジャーが記号ｅｘ ｅｃをＬＡＺＹフィールド内に与えられ、識別子ｉｄ＋を有するセルクロジャー が記号ｗａ　ｉ　ｔを与えられていることが示されていて、これはｅｘｅｃとマ ークされたセルクロジャーが、それらの内容を値にリジュースするために、識別 子ｘｄ＋により示されているセルクロジャー以前に実行されるべきことを意味す る。第４ＨｒＭのクロジャーは、さらに処理を受けるために、後の時点に、コア セル内ヘロードし返されつる。例えば、識別子ｉｄ２を有するセルクロジャーは 、その値／指示エレメント内の値ｌおよびｌが同じであるために、値ｌを有する ことになり、識別子１ｄ、を育するセルクロジャーは、その値／指示エレメント 内の値２および３が同じでないために、無（ｎｏｔｈｉｎｇ）を与える。

それぞれの単一化は、数値ＡＬＵにおいて行なわれ、数値ＡＬＵは前記値を比較 器において比較し、その比較の結果を制御装置６ｐへ供給する。制御装置はそこ で論理ゲートアレイをセットして、それによりコアセルの第１主レジスタ内の情 報を供給する。リダクションの結果、カノニカルな指示または単純な値が得られ るか、または何も得られなければ、それは、リジュースされたクロジャーへのそ れぞれの間接的指示が、値の直接的指示に変えられるように、第２種のエレメン トクロジャーを記憶するよう動作しうるオブジェクトストレージ内の全てのスト レージフィールドに対し全体的に分配される。これは、第２１図に関連して以下 にさらに説明されるｕｎｉｆｙ−ｉｄ動作によって行なわれる。

例２ この例は、セルクロジャーが挿入されたリストを含むことを意味する、ハードウ ェア命令１ｉｓｔ　ｅｘｐａｎｓｉｏｎである。この種の命令は、他のりダクシ ョンの補助ステップである。ハードウェア命令の１ｉｓｔ　ｅＸｐａｎｓｉｏｎ は第２４図に示されており、第２４図に関連してさらに説明される。

機械は、ｅｘ、ｔｙｐｅと呼ばれる例示的命令のりダクションを行ない、該命令 は、 ｅｘ、ｔｙｐｅ（１１ｉｓｔ（２３１ｉｓｔ（４５６））？）の形式を有する値 およびリストを含む任意の種類の命令でありうる。この形式は第５Ａ図に示され 、そのセルクロジャーは第５Ｂ図に示されている。第５Ａ図および第５Ｂ図は、 第４Ａ図および第４Ｂ図と同様に区画されており、従って自己説明的になってい る。

第５Ｃ図に示されているように、識別子ｔｄ＋を存するセルクロジャーは、識別 子およびタイプコードを識別子レジスタ内に有するコアセルの主レジスタ内ヘロ ードされる。第２主レジスタの内容は間接的エレメントｏｐｅｎによりマークさ れているので、それがリンクされているセルクロジャーは、第５Ｄ１１から明ら かなように、ペースレジスタ内に垂直に子としてロードされる。

第２４図にさらに詳細に示されているハードウェア命令１ｉｓｔ　ｅｘｐａｎｄ は、次に第３主レジスタ内の離散値７を、第３ベース列内のｉｄａの隣りの位置 へ移動せしめ、第２主レジスタの上の第２列内のリストの部分を第３列へ移動せ しめてその最下部エレメント（値３）を第３主レジスタ内に配置し、それにタイ プコード１ｉｓｔを与える。

次に、新しいリスト展開が行なわれ、主レジスタの上の第３列内の内容が第４列 内に配置されて、タイプ１ｉｓｔを与えられる。離散値である第３主レジスタの 内容は、第５Ｆ図から明らかなようにタグｄｉｓｃｒを与えられる。

次に、命令ｍａｋｅを用いて、第４列内のリストがオブジェクトストレージ内に 記憶される。それは、識別子ｉｄ２を有するストレージセル内に記憶される。そ のわけは、それはアイドルになっており、第５Ｇ図から明らかなように、識別子 ｉｄｔの供給は、第４主レジスタ内に記憶されるべきコアセルへ送り返されるか らである。

この後、リダクションの結果がオブジェクトストレージ内ヘロードし返される前 に、いくらかの他の種類のりダクションがｅｘ、ｔｙｐｅについて行なわれる。

例３ 数値命令が実行される。数値命令は、＋、−、ネ、／、ｍｏｄ、などでありうる 。命令の後には引数が続く。この例においては、リスト内の数の間の加算が行な われる。

機械は、ファンジョン ａｐｐｔｙ　（＋　１ｉｓｔ　（１２））を有するａｐｐｌｙ（ａｐｐｌｉｃａ ｔｉｏｎ）のりダクションを行なう。

ａｐｐ　ｌ　ｉｃａ　ｔ　ｉ　ｏｎは第６Ａ図に示され、そのセルクロジャーは 第６Ｂ図に示されている。第６Ａ図および第６Ｂ図は、第４Ａ図および第４Ｂ図 と同様に区画されているので、自己説明的になっている。

よびタイプコードを存するコアセルの主レジスタ内ヘロードされる。数値命令（ ＋）は命令としてマークされている。第２主レジスタ内の内容は間接的エレメン トｏｐｅｎとしてタグされているので、それがリンクされているセルクロジャー は、第６Ｄ図から明らかなように、子としてペースレジスタ内に垂直にロードさ れる。

次に、リスト展開が行なわれ、第２主レジスタ内の離散値にｄｉｓｃｒのタグが 与えられ、リスト展開された値２に対しタイプコードフィールド内に１ｉｓｔの マークが与えられる。これが行なわれるわけは、識別子ｉｃＬを有するリストが 、２．３、または４エレメントのいずれを存していたとしても機械は同じ動作を するからである。新しいリスト内にはｌエレメントしか存在していないので、第 ６Ｆ図から明らかなように、機械は、マーク１ｉｓｔを、主レジスタがｄｉｓｃ ｒである値を含有する旨の表示で置換する。

その時、主レジスタは、命令マーク（＋）と２つの離散値とを含み、これは制御 装置をして、直接的に、または例えば、命令が記憶されるオブジェクトストレー ジの非書込み可能部分に記憶されている命令に関する情報によって、数値ＡＬＵ を＃御して命令（加算）を行なわしめ、その数値演算の結果をカノニカル値とし て、第６Ｇ図に示されているように第１主レジスタへ送らしめる。

タイプコードフィールド内の記号ａｐｐｉｙは、ファンクションａｐｐｌｉｃａ ｔｉｏｎが行なわれるべきことのマークである。この場合は単純な値３である結 果の値は、識別子ｉｄ＋の全での存在をこの値に交換するために、広域的に分配 される。

コアセルのハードウェア構造 平面ＮＵＭおよびＨＥＡＤのレジスタセルは、平面２ｐとインタフェース９ｐと の間において、バス０ＢＪｖ。

ｉｄババスなわち識別子バス、およびｅｎｖバスすなわち環境バス、内のワイヤ に接続されている。ＯＢ　Ｊ　ｖ　／＜スは、バス部分ｖＯ１ｖｌ、ｖ２、およ びＦ３を含む。

他の諸平面の目的および接続は、以下に後述される。

このようにして、コアレジスタセルのアレイは、諸レジスタに垂直に諸平面内へ ｒスライスＪされ、同じＮＵＭまたはＨＥＡＤ平面に属するが、異なるコアレジ スタに属するレジスタセルは、第７図に示されているように互いに接続されてい る。

第７図に示されている少なくともＮＵＭ平面およびＨＥＡＤ平面の構造内には、 ＮＸＮ個のレジスタＳ　ｏ、　。

から５Ｎ−１＋Ｎ−１までのマトリックスをなして、レジスタセルの正方形か配 置されている。、二のマトリックス内のレジスタはペースレジスタと呼ばれ、レ ジスタセルはペースレジスタセルと呼ばれる。

ペースレジスタは多くの応用において、一時記憶クロジャーエレメントとして用 いられる。レジスタの表示は、ペース、主、および補助レジスタのような表示の １つの種類か、説明がレジスタの実際の位置に関する時に使用され、子、目標、 および親レジスタのような表示のもう１つの種類が、説明がレジスタの機能に関 する時に使用されるという意味において、厳密に区別されている。

図示されている実施例においてはＮ＝４であり、これは好ましいものではあるが 、マトリックスの、他の大きさも選択可能である（図示はされていない）。第７ 図に示されているように、最下行のペースレジスタセルＳ０゜、Ｓ、。、Ｓｌ。

、およびＳ３゜は、平面に特有のバスｈｏ内の線に接続されており、これらは主 レジスタセルである。主レジスタセルＳ、。、Ｓｌ。、Ｓ、。、およびＳ　ｚ、 　ｏは、目標ルーツレジスタとして最も頻繁に使用され、導体ＮＵＯないしＮＵ ３から成るバスＮＵを経て、数値ＡＬＵ　ｉｐに接続されている。

しかし、本発明の教示する所によれば、数値演算を必要としない簡単なプロセッ サを用いることも可能である。

そのような場合には、数値ＡＬＵ　ｔｐを省略することができる（第１図参照） 。

識別子レジスタセルＩＤは線ｉｄに接続され、環境レジスタセルＥＮＶは線ｅｎ ｖに接続されている。

バス線ｈｉは、ｉを０と３との間の数として、スイッチＳＷ、、によりバス線ｖ ｉに接続されつる。バス線ｈｏ、ｈｌ、ｈ２、ｈ３を含むバスは、０ＢＪｈ、す なわち水平オブジェクトバスと名づけられる。バス０ＢＪｈは、なかんずく、デ ータをコアセル内において垂直に、すなわちレジスタの列内にロードするのに用 いられ、そのデータは、オブジェクトストレージによりバス０ＢＪｖを供給され る。これは、第２０図に関連してさらに以下に説明される。

バス線ｉｄ、ｅｎｖ、ｖＯ，ｖｌ、Ｆ２、Ｆ３は、それぞれスイッチＳＷ、、、 、。ｓ　Ｓ　Ｗ　ｓ　＊　ｗ、　ｋ。、ＳＷｌ。、Ｓ　Ｗｖｌ、ｂＯ，５Ｗｖｔ 、ｈｏ　％およびＳＷ＊ｓ、ｂｏにより、バス線ｈＯに接続されつる。バス線Ｃ ，，，Ｃ，，Ｃ，、およびＣｖを含むバスｒｅｓは、制御装置６ｐに接続されて おり、レジスタに０などの定数をセットするのに用いられつる。バス線Ｃ＋ｎは 識別子レジスタセルに接続され、バス線ＣＩはレジスタセルＦＯ１Ｆｌ、Ｆ２、 およびＦ３に接続されており、バス線Ｃ１はスイッチＳ　Ｗ　ｃ　ｂ　、　ｈ　 。

によりバス線ｈＯに接続可能であり、バス線Ｃｖは、ｉを０と３との間の数とし て、スイッチＳＷ、、ｃ、によりバス線ｖｉに接続可能である。バスｒｅｓはそ のスイッチと共に、ある応用においては省略されつる（図示されデータの水内に は、親と呼ばれる頂部レベルがある。

親は時々、第７図内に左方に配置されている補助レジスタセルＦＯ１Ｆ１、Ｆ２ 、Ｆ３内に記憶される。図示されている実施例においては、全ての補助レジスタ は、コアワードを記憶しうる。それぞれの補助レジスタセルは、バス線ｉｄと、 バス線ｉｄに対して垂直に走るバス０ＢＪｈ内の線ｈＯ１ｈｌ、ｈ２、ｈ３の１ つにそれぞれ接続されている。補助レジスタセルは、コアセルが行ないつる動作 の少数のものにおいて使用される。従って、補助レジスタは、本発明のコアセル のある応用においては省略されうる（図示されていない）。また、１列より多く の補助レジスタを有するコアセルを用いることも可能である（図示されていない ）。

以上から明らかなように、それぞれのレジスタは、諸平面２ｐ内において同じ位 置を育する、いくつかの諸平面２ｐ内のレジスタセルにより構成される。従って 、第７図はそれぞれのレジスタの１セル、すなわち１ビツト、しか示していない が、全レジスタは第７図に用いられている符号を名称として与えられる。第７図 がら明らかなように、レジスタは行および列をなして配列されている。

補助レジスタ領域ＦＯ，Ｆｌ、Ｆ２、Ｆ３は列であり、Ｎ個のペースレジスタ領 域Ｓ０．。ないしＳｏ、ｓ、Ｓ＋、ｓないしＳ　１．ｓ　、Ｓｔ、ｏないしＳｏ 、ｓ　、　オＪ：ヒｓｓ、ｏ　ナイしＳ　ｓ、　ｓは、それぞれ列であって子を 記憶しつる。

レジスタセル間の接続 接続は、それぞれの平面内の隣接するペースレジスタセル間に、垂直方向および 水平方向の双方において行なわれる。図示されている実施例においては偽ｆであ る固定的なプログラムされた値を有する接続もまた、オブジェクトストレージを 利用する水平行上の最外部のペースレジスタセルのそれぞれに対してなされる。

それは、レジスタセル内のＮ端子（北）（第８図参照）に接続され、北−南方向 におけるシフトが行なわれる時に用いられる。

トランスポーズ可能な位置が接続されるように、ペースレジスタセル間の対角線 方向における接続も設定可能である。これは、ｉがｊと異なるものとして、セル Ｓ１．１がセルＳ　ｒ、　＋に接続可能であることを意味する。それぞれのペー スレジスタセルは、最も近い右下方に位置するペースレジスタセルに接続されて いる。ただし、その位置にペースレジスタセルが存在しているものとする。それ ぞれの補助、識別子、環境、およびペースレジスタセルは、Ｘおよびｙを０と３ との間の数として、それぞれ出力ＡＣＣ，，，ＡＣＣ，，，ＡＣＣ，、、、およ びＡ　ＣＣ、、、アにより、平面ＢＯＯＬの１つに接続されている。

以下においては、平面ＮＵＭおよびＨＥＡＤ内に存在すべき総称レジスタセルを 説明する（第８図）。この総称レジスタセル内に用いられるスイッチおよびゲー トの実施例は、第９Ａ図から第９Ｆ図までに示されている。

この総称レジスタセルから、補助レジスタセル（第１θ図）および識別子レジス タセル（第１１図）の実施例が得られる。

さらに以下においては、ＡＴＴＲＩ　ＢＵＴＥ平面内に存在すべきレジスタセル の実施例を説明する。第１３図には、識別子レジスタセルが表示されている。第 １４図には補助レジスタセルが示され、第１５図には主レジスタセルが示されて いる。

平面ＮＵＭおよびＨＥＡＤ内の総称レジスタセル第８図においで、レジスタセル の実施例は、２つの内部バスａ１およびす、と、中央レジスタｒつとを含む。

バスａ６およびす、ｌは、レジスタセルの外部のいくつかの接続に接続されてい る。第８図の実施例は、外部への全ての可能な接続を備えた総称レジスタセルを 示している。通常は、特定のレジスタセルは、第８図に示されている全ての接続 を備えてはいない。レジスタセルの配置により、１つまたはそれ以上を欠いてい る。接続された端子間の全てのワイヤは、第７図に示されている配線から明らか である。全てのレジスタセルが、第８図に示されている全ての外部接続を有する とは限らないことも、第７図から明らかである。従って、全てのレジスタセルお よびそれらの接続についての詳細な説明は行なわない。

バスａ１ バスａｍ′は、スイッチＳＷ、、および端子Ｖを経て垂直バス線ＶＸに接続され ている。ただし、Ｘは０と３との間の数である。さらに、それは、スイッチＳＷ 、Ｉｌおよび端子Ｈを経て、ｙを０と３との間の数として水平バス線ｈｙに接続 され、また隣りのレジスタセル内のスイッチＳＷ□　（東）に接続されている端 子Ｗ（西）を経て左方のレジスタセルにも接続され、さらにもしレジスタセルが 主レジスタセルならば、端子ＮＵにより直接、数値演算袋（ｔｉｐにも接続され ている。バスａｍはまた、右下方のレジスタセルに、そのレジスタセル内に備え られたスイッチ５ＷＤｂへの端子り、を経て接続され、さらに、下方のレジスタ セルにも、そのレジスタセル内に備えられたスイッチＳＷ、（北）への端子Ｓ（ 南）を経て接続されている。本レジスタセルは、バスａＸに接続されている端子 ＣおよびＳＷＣを経て、セットまたはリセットされうる。バスａ、はさらに、ス イッチＳＷ、を経て中央内部レジスタｒ８の入力に接続され、またこスイッチＳ Ｗ、。を経て同レジスタｒＩｌの出力に接続されている。

バスｂ、ｌ バスｂ、は、スイッチＳＷｔおよび端子Ｅを経て右方のレジスタセルに接続され 、また、スイッチ５Ｗｌｌｌｂおよび端子Ｄ１を経て諸レジスタセルの対角線に も接続され、さらにまた、スイッチＳＷＮおよび端子Ｎを経て上方のレジスタセ ルにも接続されている。バスｂ１１はまた、ＳＷ、、を経て中央内部レジスタｒ １の入力に接続され、さらにスイッチＳＷ、。を経て同レジスタｒ、の出力に接 続されている。

中央内部レジスタ 中央内部レジスタセルは、好ましくはＣＭＯＳインバータである２つのインバー タＱｌおよびＧ２と、それらの間の制御可能スイッチＳＷ０とを含む。完全なレ ジスタセルはさらに、バスａｌｌおよびｂえと、スイッチＳＷ、、、ＳＷｌ。、 ＳＷ、、、ＳＷ、、と、このセルを外部に接続する諸スイッチと、を含む。中央 内部レジスタｒえの出力は、スイッチＳＷ、、および端子Ｈを経、またスイッチ Ｓ　Ｗ　ｖｏおよび端子Ｖを経て、それぞれ水平バスと、垂直バスとに接続され つる。中央内部レジスタｒｔは（以下に説明される）動的状態を記憶する。

スイッチの動作 コア内の全てのレジスタセル内にある全ての制御可能スイッチは、例えばＰＡＬ 　（プログラマブルアレイロジック）などのゲートアレイを含む、制御装置６ｐ に接続されたワイヤを経て制御される。このゲートアレイは、コアセル内に記憶 されている情報を用いて、いずれのスイッチを開放し、次にいずれのスイッチを 閉成すべきかを決定する。ゲートアレイの動作は、クロックにより同期せしめら れる。スイッチは２方向性のものであるが、あるもの、例えば入力および出力ス イッチＳＷ□１および５ＷＨＯは、１方向においてのみ使用される。

比較装置ＣＯＭＰ 比較装置ＣＯＭＰは、第１ＮＡＮＤゲートＧｌを含む。

■入力はインバータＱ１の非反転入力に接続され、他人力はインバータＱ２の入 力に接続されている。装置ＣＯＭＰはさらに、第２ＮＡＮＤゲートＧ２をも含む 。１入力はインバータＱｌの出力に接続され、他人力はインバータＱ２の出力に 接続されている。ゲートＧｌおよびＧ２の出力は、平面ＢＯＯＬの１つに至る１ ワイヤバスＡＣＣに接続されている。双方のＮＡＮＤゲートは、２つの直列接続 されたＭＯＳ−ＦＥＴ）ランジスタによって構成され、それらの直列接続された ソース／ドレイン路は接地とＢＯＯＬ平面との間に接続され、それらのゲートは ＮＡＮＤゲートの入力であり、最上部のＭＯＳ−ＦＥＴ）ランジスタのドレイン は出力である（第９Ｄ図参照）。この比較装置ＣＯＭＰは、連想探索中、すなわ ちセルコア内のエレメントが、オブジェクトストレージ内または該セルコアの他 部分内のエレメントと比較されるべき時に、用いられる。その時、比較されるべ きエレメントは、さらに以下に説明されるように、比較すべきエレメントを含存 するレジスタセルの入力に印加される。

インバータおよびスイッチ インバータＱ１およびＧ２は、エンハンスメント形の２つのＭＯＳ−ＦＥＴトラ ンジスタ（第９Ａ図）によって、または第９８ＩＮに示されているように接続さ れた１つのエンハンスメント形および１つのデプレション形のＭＯＳ−ＦＥＴト ランジスタによって、または２つの相補形ＭＯ３−ＦＥＴ）ランジスタ（第９Ｃ 図）によって、構成される。レジスタセル内の制御可能スイッチは、ＭＯＳ−Ｆ ＥＴ）ランジスタ（第９Ｅ図）によって、または第９Ｆ図に示されているように 接続された（エンハンスメント形（ＥＥ　ＭＯＳ）の）２つの相補形ＭＯＳ−Ｆ ＥＴトランジスタによって、構成されうる。制御装置ｔ６ｐは、制御信号Ｃによ りスイッチを制御する。第９Ｆ図かられかるように、スイッチは、より速い状態 遷移を実現するためには、制御信号とその補数信号との双方によってυＩｍされ うる。

第８図の総称レジスタセルは、コアセル内の全てのレジスタセルの基本と見るこ とができる。すなわち、それらは同様に設計されうる。総称レジスタセルから得 られるレジスタセルは、端子および付随する出力および入力スイッチの数によっ てのみ異なる。これらの得られたセルは、第８図に示されているセルと同じ参照 番号を与えられている。

ＮＵＭおよびＨＥＡＤ平面内のベースレジスタセルベースレジスタセルＳ、、。

、ＳＯ，ｌ　、Ｓ、１、およびＳ８．、はスイッチＳＷ、、および端子Ｄｂをも たず、ペースレジスタセルＳ　ａ、ｏ　、Ｓ＋、ｏ　ｓ　Ｓｚ、ｔ　、Ｓｓ、ｓ はＤａＣ端子もたず、主レジスタセル（Ｓ　、、、からＳｓ、。まで）はＳ端子 をもたず、残余のペースレジスタセル（Ｓ＝、＋からＳ　ｓ、　ｓまで）はＮＵ 端子をもたない。いずれのペースレジスタセルもＣ端子をもたずまたＳＷｃスイ ッチももたず−その代わりに、垂直および水平バスと、端子ＶおよびＨとが、バ ス線ＣｙまたはＣ２により供給される一定値によってレジスタセルをセットまた はリセットするのに用いられる。

ＮＵＭおよびＨＥＡＤ平面内の補助レジスタセル第１Ｏ図に示されている補助レ ジスタセルは、ｙを０と３との間の数として、端子Ｈｙ、Ｖ、Ｃ１およびＡＣＣ のみを有し、■端子はバス線ＩＤに接続され、Ｃ端子はバス線Ｃ１に接続されて いる。

ＮＵＭおよびＨＥＡＤ平面内の識別子／環境レジスタセ第１１図に示されている 識別子レジスタセルは、端子Ｖ、Ｃ１およびＡＣＣのみを育し、■端子はバス線 ＩＤに接続され、Ｃ端子はバス線ＣＩｍに接続されている。環境レジスタセル（ 図示されていない）は、第１Ｉ図の識別子レジスタセルと同様のものであるが、 この実施例においては、Ｃ端子およびＳＷ２スイッチがない。他の実施例におい ては、環境レジスタセルは、Ｃ端子およびＳＷｃスイッチを含みつる。

連想探索およびＢＯＯＬ平面 連想探索中においては、比較は、平面ＢＯＯＬに至るアクセス配線およびバスに 対して行なわれる。２つのＡＮＤゲートＧ１およびＧ２は、キー値、すなわちＱ ｌの入力上の比較されるべき記憶値である値と、Ｇ２の入力上の記憶値を比較す る。この比較中に、キー値は、内部バスａ、またはｂつを経てＱｌへ転送される 。スイッチＳＷｏはその時オフ状態にある、すなわち開放されている必要がある 。もし供給された値、すなわちキー値が、記憶値と一致しなければ、充電された ＢＯＯＬ平面はＮＡＮＤゲー１−ＧｌおよびＧ２を経て放電せしめられる。

もし一致すれば、ＢＯＯＬ平面は充電された状態に留まる。

レジスタセル毎に１バス線ＡＣＣが存在する、レジスタ内の全てのバス線ＡＣＣ は、並列に接続されて、平面ＢＯＯＬ内の同じバス線に接続されつる。あるいは 、平面ＮＵＭおよびＨＥＡＤ内に備えられている全てのレジスタセルのバス線Ａ ＣＣは、これらの平面のためのＢＯＯＬ平面内のバス線に接続可能であり、ＡＴ ＴＲＩＢＵＴＥ平面内に備えられている全てのレジスタセルは、同じＢＯＯＬ平 面内、またはＡＴＴＲＩ　ＢＵＴＥ平面のための第２ＢＯＯＬ平面内に備えられ た別個のバス線に接続可能である。ＢＯＯＬ平面か１つ備えられるのか、２つ備 えられるのか、およびバス線が■つ備えられるのか、２つ備えられるのかは、選 択の問題であり、＃纒装置６ｐに記憶される制御命令の形式による。２つより多 （のＢＯＯＬ平面の設置も、本発明の範囲内にある。備えられるＢＯＯＬ平面の 数は、連想探索の細分性、すなわち、行なわれつる異なる連想探索の数およびそ れらが行なわれる程度、すなわち、関連しうるレジスタの諸部分、を指示する。

このようにして、比較は、ＢＯＯＬ平面内の同じバス線に接続されているレジス タの部分に対し同時に行なわれる。もし全てのＮＡＮＤゲー）ＧｌおよびＧ２が 同じ出力（高レベル）を有すれば、比較の結果は「一致」となり、そうでない場 合は、その結果は不「一致」となる。ただし、「一致」は、双方の情報片が同一 であることを意味する。このようにして、平面ＢＯＯＬはバス線に対する平面で あり、仮想的な、すなわち「想像上の」平面とみなされつる。すなわち、バス線 は、必ずしも平面内に備えられる必要はなく、直接制御装置６ｐに接続されつる 。

ＡＴＴＲＩ　ＢＵＴＥ平面の構成 ＡＴＴＲＩ　ＢＵＴＥ平面は、平面ＮＵＭおよびＨＥＡＤとは異なる構成を有し 、その構成は第１２図に示されている。第７図におけると同じ参照符号が、同じ 構成を育するエレメントに対しては用いられている。この種類の平面は、スイッ チＳＷ、。、ＳＷ、ｌ、ＳＷ、、、およびＳＷ、と、１つの識別子レジスタセル ＩＤｔと、４つの補助レジスタセルＦ　Ｏｔ　、　Ｆ　１　？　ＳＦ　２　ｒ　 、　Ｆ　３　ｔと、主レジスタセルＳ０゜、Ｓ、、、　、Ｓ、、。、およびＳｌ 、。のみを含むペースレジスタユニットと、を含む。

このように、ペースレジスタマトリックスは、第７図に示されているレジスタ平 面における同様に、スイッチＳＷ、、、Ｓ　Ｗｖ＋、ｗ　ｓ　５Ｗｖｚ、ｂ＊　 ｓ　ＳＷｗｓ、ｈｏのそれぞれにより、それぞれのバス線ｖＯ１ＭＩＳＶ２、ｖ ３に、またバス線ｈＯに接続された主レジスタセルの行Ｓ０．。

からＳ８．。までのみにリジュースされている。ｉを０と３との間の数とすると き、バス線ｈｉは、スイッチＳＷ、、によりバス線ｖｉに接続可能である。しか し、ｌ（ス線■０、ｖｌ、ｖ２、ｖ３は、平面ＮＵＭおよびＨＥＡＤ内の同じ名 称のバス線ではなく、インタフェース９ｐの他の入力に接続可能であり、従って 、オブジェクトストレージ４ｐの他部分、好ましくはレージ−、ホエア、および タイプの諸部分（第１図参照）に接続可能である。

別の方式においては、バス線ｖＯ１ｖ１、ｖ２、およびｖ３は、全くオブジェク トストレージ４ｐに接続される必要がなく、その代わりにバス線ｉｄを、オブジ ェクトストレージからの状態転送に使用することができ（第１図参照）、すなわ ちオブジェクトストレージ内のレージ−、ホエア、およびタイプが、コアセル内 の対応平面内のバス線ｉｄに結合せしめられる。また、主レジスタセルの行Ｓ６ ９．からＳｓ、。までと、識別子レジスタセルＩＤＴと、補助レジスタセルＦ０ ７からＦ３．までとは、第７図に示されているレジスタ平面内におけると同様に 、バス線ＣＩ４．Ｃｆ　ｓ　Ｃｋ　、およびＣｖを含むバスｒｅｓに接続されて いる。

そのほか、識別子レジスタセルＩＤ、の垂直列と、４つの補助レジスタセルＦ３ ア、Ｆ２ｔ、、Ｆｌｙ、およびＦＯＴとが、バス線ｉｄに接続されており、バス 線ｉｄはさらに、制御装置６ｐに至る第２バス線ｃｏｎｔ　（第１図には示され ていない）に接続されている。制御装置６ｐは、このバス上を転送されうる情報 を用いて、行なわれるべきリダクションの種類を決定することができる。

第１２図に示されている種類のレジスタ平面内のそれぞれのレジスタセルは、そ のアクセスワイヤおよびバス線ＡＣＣのほかに、ｉを０と３との間の数または記 号ＩＤ、ＦＯからＦ３までとして、出力線ＳＤ、を有し、これは、問題となって いる出力線に接続されているレジスタセルの状態を直接検査するのに用いられる 。

ＡＴＴＲＩ　ＢＵＴＥ平面内の識別子レジスタセル第１３図は、ＡＴＴＲＩ　Ｂ ＵＴＥ平面内に存在する識別子レジスタセルＴＤ、の実施例を示す。それは、４ 端子ｖ、Ｃ０ＮＴ、ｓ［）、　およびＡｃｃｔ−１ｒする。端子Ｖに接続されう る。端子Ｃ０ＮＴは、スイッチＳ　Ｗｃａｓｔを経て内部レジスタｒえの出力に 接続されている。端子ＳＤは、内部レジスタｒＲの出力、すなわちインバータＱ 、の出力に接続されている。端子Ｃはバス線Ｃ１ｄに接続される。

ＡＴＴＲＴ　ＢＵＴＥ平面内の補助レジスタセル第１４図は、ｙを０と３との間 の数として、ＡＴＴＲＩ　Ｂ　Ｕ　Ｔ　Ｅ平面内に存在する補助レジスタセルＦ ｙｔの実施例を示す。識別子レジスタセルＩＤ、と比較すると、このレジスタは １つ余分な端子、すなわち端子Ｈを有する。端子Ｈは、ｙをＯと３との間の数と して、バス線ｈｙに接続されつる。他の諸端子は、識別子レジスタセルＩ　Ｄ　 ｔの対応する諸端子における接続と同様に接続される。端子Ｃはバス線ＣＩに接 続される。

ＡＴＴＲＴ　ＢＵＴＥ平面内の主レジスタセル第１５図は、Ｘを０と３との間の 数として、ＡＴＴＲＩＢＵＴＥ平面内に存在する主レジスタセルＳ８１．の実施 例を示す。それは、６端子Ｖ、Ｅ、Ｈ，Ｗ、ＳＤ、およびＡＣＣを有する。端子 ＳＤは、内部レジスタｒ、の出力、すなわちインバータＱ、の出力に接続されて いる。

他の諸端子は、ＮＵＭおよびＨＥＡＤ平面内のレジスタセルの対応する諸端子に おける接続と同様に接続される。

いずれの主レジスタセルもＣ端子をもたず、またＳＷｅスイッチももたない一代 りに、垂直および水平バスと、端子ＶおよびＨとが、バス線Ｃ７またはＣｋによ り供給される一定値によってレジスタセルをセットまたはリセットするのに使用 される。

スタンバイストレージモード スタンバイストレージモードループは、セル内に備えられたループの一方または 双方により形成される。１つのループは、スイッチＳＷ、。と、バスｂ、と、ス イッチＳ　Ｗ　ｂ＋と、インバータＱｌと、スイッチＳＷ０と、インバータＱ２ と、により形成される。もう１つのループは、スイッチＳＷ、。と、バスａｍと 、スイッチＳＷ、、と、インバータＱｌと、スイッチＳＷ９と、インバータＱ２ と、により形成される。一方または双方のループ内のスイッチが閉成されると、 信号は２つのインバータＱｌおよびＱ２を経て伝搬することができ、インバータ Ｑ１の入力における、またインバータＱ２に出力における信号レベルは、安定す る−これがセル内へのデータの記憶され方である。セルは動的状態を記憶する。

出力モード 出力モードにおいては、Ｑ２の出力は一方のバスａ１１またはｂｌへ転送される ことができ、そこから、適切なスイッチが制御されて、その出力を１つまたはそ れ以上の出力端子（Ｎ、Ｓ、Ｅ、Ｗ、など）へ転送することができる。他方のバ スｂ、またはａ８は、任意のモードで使用されつる。もしＳＷｏがオフ、すなわ ち開放、されていれば、インバータＱ２の出力は安定している。すなわち、それ はスイッチＳＷ０が閉成されるまで変化しえない。インバータのこの出力は、閉 成された時のスイッチＳＷ、、を経てバスｂ１１へ、閉成された時のスイッチＳ Ｗ、。を経てバスａｍへ、閉成された時のスイッチＳ　Ｗ　ｅ　ＩＩ　ｍ　ｌを 経て出力ｃｏｎｔへ、さらに直接端子ＳＤへ、転送されうる。バスｂ、およびａ ｋ上の情報は、さらに以下において例によって示されるように、レジスタセルと 問題にされる外部バスとの間に接続されたスイッチを制御することによってその レジスタセルが接続されるそれぞれの外部バスへ転送されつる。

入力モード 入力モードにおいては、１つのスイッチＳＷ、、またはＳＷｌがオン、すなわち 閉成されている。従って、１端子（Ｎ、Ｓ、Ｅ、Ｗ、など）の状態が、局部バス ａ、またはｂＲへ転送され、さらにそこから中央内部レジスタｒ、ｌへ転送され る。

転送 コアセル内の任意のレジスタセルからコアセル内の他のレジスタセルへ、端子接 続を経て、２位相サイクル中にデータを転送することができる。垂直、水平、ま たは対角線方向における２つのペースレジスタセルのスワップは、３位相サイク ル中に可能である。

スイッチＳＷ０は、インバータＱｌおよび０２間の転送が全コアセル内において 同時に行なわれるように、主クロックにより直接に、かつレジスタ内の全てのセ ルにおいて同時にクロックされる。他の諸スイッチは、主クロックから得られる 信号によって制御されるが、主クロックの同期内において異なった、適切な位相 間隔に置かれる。主クロックは、コアセルの全ての動作に対する基準信号として 用いられる。

クロックサイクルは、クロック位相０、ａ、および／またはｂに分割される。位 相０は、第１の拡張可能な位相、すなわち中央内部レジスタｒ、がスタンバイス トレージモードにある時−データが安定している時、である。

位相ａはバスａ８からの移送中に用いられ、位相すはバスｂ、からの移送中に用 いられる。

１方向転送、すなわちレジスタセルから、またはレジスタセルへ、のみの転送は 、２位相クロックサイクル中に行なわれる。第１位相０は安定している。２位相 クロックサイクルにおいては、位相ａまたは位相すは、移送のために用いられる 。

２方向転送、すなわちそれぞれの内容を交換するための２レジスタセル間での移 送は、３位相クロックサイクル中に行なわれる。位相０は安定している。位相ａ およびｂ中には、移送は異なる方向において行なわれる。

例えば２つの５位相を有する、３位相より多いクロックサイクルも本発明の範囲 内にあることに注意すべきである。

スイッチＳ　Ｗ、、およびＳ　Ｗ、、は常態においては閉成されている。その時 、双方の局部バスａ１１およびす、は、レジスタセルの記憶状態を保持している 。内部バスａ。

またはす、が、記憶されるべき新しい値の入力のために使用されるべき時には、 適切なスイッチＳＷ、、またはＳ　Ｗ、、がそれぞれ開放されるべく１ｌｉＩＪ ＩＩＩＪされる。垂直または水平バスなどの外部バスの１つへのスイッチは、そ のバス上の情報が内部バスへ転送されるためには十分に長い、短い間隔の開閉成 される。

シフト回路網、すなわち諸端子に接続されたスイッチを含む、異なるレジスタセ ル間の回路網を用いて、レジスタセル内の内容を、北Ｎまたは南Ｓまたは西Ｗま たは東Ｅへ転送することも可能である。

■方向転送動作の例 第１６Ａ図は、２つの相隣るベースレジスタセルを示し、データは、送信セルで ある左方のセルから、受信セルである右方のセルへ転送されるべきものとする。

制御装置６ｐからの制御信号が、諸スイッチを制御する。第１６Ｂ図は、異なる 位相中における転送により影響される全スイッチの状態を示し、低レベル値は開 放されたスイッチを表わし、高レベル値は閉成されたスイッチを表わす。実際の 転送は、位相すにおいて起こる。転送は、以下のように行なわれるＣ以下の諸ス テップには、第１６Ａ図および第１６Ｂ図におけると同じ番号が付せられている ）： ０、送信セルおよび受信セルの双方において、回路が安定しており、ｓｗ、、ｓ ｗ、。、ＳＷ、Ｉ、ＳＷ、。、５ＷｂＩは閉成されており、他のスイッチは全て 開放されている（このステップは、全てのスイッチに関連しているので、第１６ Ａ図にはマークされていない）。この安定モードは、第１６Ｂ図における位相Ｏ に対応している。

１、第１位相（位相ｂ）のクロック間隔中に、送信セルおよび受信セルの双方に おけるスイッチＳＷｏが開放された時、 ２、送信セルおよび受信セルの双方において、スイ・ツチＳＷ、。が開放され、 スイッチＳＷ、。が閉成され、３、送信セルと受信セルとの間のスイッチＳＷよ が閉成され、 ４、送信セルおよび受信セルの双方において、スイッチＳＷ、、が開放され、 ５、送信セル内のスイッチＳＷ−１が開放され、受信セル内のスイッチＳ　Ｗ　 、　＋が閉成される。これにより、送信セルの内部レジスタから受信セルの内部 レジスタへのデータの伝搬が可能ならしめられる。

６、第２位相（位相Ｏ）のクロック間隔中に、送信セルおよび受信セルの双方に おけるスイッチＳＷ０が閉成された時、 ７、送信セルと受信セルとの間のスイッチＳＷ８が開放され、 ８、受信セルおよび送信セルの双方において、まずスイッチＳＷ、。およびＳＷ 、。か閉成され、その後スイッチＳＷ１およびＳＷ、、が閉成される。これによ り、上記ステップＯで説明された安定モード、すなわち位相０に復帰する。

２方向転送動作の例 第１７Ａ図は相隣るベースレジスタセルを示しており、２つの別のペースレジス タセル内のデータが２方向転送動作によって交換される。制置装置６ｐからの制 御信号が、諸スイッチを制御する。第１７Ｂ図は、異なる位相中における転送に よって影響される全てのスイッチの状態を示しており、低レベル値は開放された スイッチを、高レベル値は閉成されたスイッチを表わす。双方のレジスタセルが 送信セルおよび受信セルとして働くので、それらを以下においては「セル１」お よび「セル２」と呼ぶ。セル２からセルｌへの、一方の転送は位相ａにおいて行 なわれ、セルｌからセル２への他方向への転送は位相すにおいて行なわれる。以 下の諸ステップには、第１７Ａ図および第１７Ｂ図におけると同じ番号が付せら れている。転送は以下のように行なわれる：０、双方のセルにおいて、回路は安 定しており、ＳＷｏ、ＳＷ、。、ＳＷ、、、ＳＷ、。、Ｓ　Ｗ、、は閉成されて おり、他のスイッチは全て開放されている（このステップは、全てのスイッチに 関連しているので、第１．７Ａ図にはマークされていない）。この安定モードは 、第１７Ｂ図における位相０に対応している。

１、第１位相（位相ａ）のクロック間隔中に、セルｌおよび２内のスイッチＳＷ ｏが開放された時、２、セルｌおよび２内のスイッチＳＷ、。が閉成され、セル ｌおよび２内のスイッチＳＷ、。が開放され、３、セル間のスイッチＳＷｔが閉 成され、４、セルｌおよび２内のスイッチＳ　Ｗ、、が開放され、５、セルｌ内 のスイッチＳ　Ｗ、、が閉成され、セル２内のスイッチ５Ｗｂｌが開放される。

これにより、セル２からセルｌへのデータの伝搬が可能ならしめられる。

第２位相（位相ｂ）のクロック間隔中の、スイッチＳＷ０がなお開放されている 時に、 ６、セルｌおよび２内のスイッチＳＷ、。が開放され、セル１および２内のスイ ッチＳＷ、。が閉成され、７、セルｌおよび２内のスイッチＳＷ、、が開放され 、８、セルｌ内のスイッチＳＷ、Ｉが開放され、セル２内のスイッチＳＷ、、が 閉成される。これにより、セルｌからセル２へのデータの伝搬が可能ならしめら れる。

９、第３位相（位相０）のクロック間隔中に、セルｌおよび２の双方におけるス イッチＳＷ０が閉成された時、 １０、セル間のスイッチＳＷｚが開放され、１１、双方のセル内において、まず スイッチＳＷ、。およびＳＷ、。が閉成され、その後スイッチＳＷ、、およびＳ Ｗ、　ｌが閉成される。これにより、上記ステップ０で説明された安定モード、 すなわち位相０に復帰する。

スイッチＳＷ、。およびＳＷ、。に対する制御信号位相０中の省略解釈により、 諸信号はオンに、すなわち諸ゲートは閉成、される。その時、全ての局部バスは 、記憶状態を保持している。入力のために用いられるノくスは、Ｘをａまたはｂ として、スイッチＳＷＱおよびスイッチＳＷ０゜に対する制御信号をオフ、すな わち開放、にセットすることにより制御される。入力動作中に、いくつかのバス が、ある端子（Ｅ、Ｖ、Ｄ、Ｈｌなど）により短時間の間短絡されうる。

スイッチＳＷ０への制御信号の下降部分から、スイッチＳ　Ｗ　ｘ。（Ｘはａま たはｂ）への制御信号の下降部分までには、遅延時間が存在する。もしそれが短 かければ、問題は起こらない。しかし、もしその時間がｍｓの領域まで長くなる と、バスＸ＊　（Ｘはａまたはｂ）は、その動的状態を失いうる。

スイッチＳＷ０への制御信号の上昇部分から、スイッチＳＷ、ｌ（Ｘはａまたは ｂ）への制御信号の上昇部分までには、遅延時間が存在する。もしそれが負にな ると、インバータＱ２からインバータＱｌまでの局部バスＸ。

へは、誤った値が伝搬しうる。従って、正の該遅延時間が用いられる。

スイッチＳＷＩ　、ｓｗ、、ＳＷＤ　、ＳＷ、等に対する制これらのスイッチは 常態においてはオフ、すなわち開放されている。その時全ての局部バスは分離さ れている。

入力または出力のために用いられるバスは、それに接続されている端子スイッチ への制御信号を、該スイッチをオン、すなわち閉成、するようにセットすること により制御される。この動作中に、いくつかのバスがあるスイッチ（ＳＷ、、Ｓ Ｗｖ、５Ｗｌ）、ＳＷ、、など）により、短時間の間短絡されうる。その後、諸 バスは正しい値を得る。

スイッチＳＷ９への制御信号の下降部分から、スイッチＳＷ、（Ｚは、Ｈ，Ｄ、 Ｎ、Ｖ％Ｅなど、すなわちスイッチを備えた内部バスａつおよびす、に接続され ている任意の端子）への制御信号の上昇部分までには、遅延時間が存在する。も しそれが負になると、局部バスｘＩＩ（Ｘはａまたはｂ）の値が変化せしめられ つる。その時は、レジスタの値がセットされつる。従って、この遅延時間は、正 であるべきである。

スイッチｓｗｘ　（Ｚは、Ｈ，Ｄ、Ｎ、Ｖ、ＥｆＬど、すなわちスイッチを備え た内部バスａｍおよびｂ麓に接続されている任意の端子）への制御信号の上昇部 分から、スイッチＳＷｘ□への制御信号の下降部分までには、遅延時間が存在す る。もしそれが負になると、値は入力まで伝搬しえない。従って、正の該遅延時 間が用いられる。

スイッチＳ　Ｗ、、への制御信号の上昇部分から、スイッチＳＷ工への制御信号 の下降部分までには、遅延時間が存在する。もしそれが負になると、局部バスが 変更され、レジスタが誤った値にセットされる可能性がある。従って、正の該遅 延時間が用いられる。

スイッチＳ　Ｗ　、　＋および５ＷｂＩに対する制御信号路信号は、位相０中に 省略時解釈によりオンされる。

しかし、スイッチＳＷ０への制御信号の上昇部分から、スイッチＳＷ、、および ＳＷ、、に対する制御信号の上昇部分までには、わずかな遅延がな（ではならな い。

もしこの遅延が負になると、インバータＱ２の入力上の値は、バスＸｔ　（ｘは ａまたはｂ）へ伝搬しえない可能性がある。従って、正の該遅延が用いられる。

コアセルの計算 代表的なリスト命令は、■機械サイクル中に行なわれる。

前述のように、コアセルは構造演算を行なう。全てのステップは、コアレジスタ により、それが含有するリスト内の語命令を用いて行なわれる。命令の例は以下 の通りである。

ｌｅｎｇｔｈ　目標の長さが計算される、ｍａｐ　リストのエレメントに対しフ ァンクションが適用される。もしリストが挿入されたリストを含有すれば、命令 はこれらの挿入されたリストのエレメントにも適用される。

（命令ｍａｐは、以下においてさらに説明される） ｆｉｌｔｅｒ　ファンクションが適用され、リストのエレメントをフィルタする 。ｆｉｌｔｅｒは、挿入されたリストがあればそれに対しても適用される。

ｊｏｉｎ　全でのエレメントが、挿入されたリストのエレメント内に再書込みさ れる。この命令は、挿入されたリストがあればそれに対しても適用される。

ｔｒａｎｓｐｏｓｅ　小さいマトリックスがトランスポーズされる。もしそれが リストのエレメントを含有すれば、それらは交換される。挿入されたリストは処 理される。（命令ｔｒａｎｓｐｏｓｅは、以下においてさらに説明される）。

コアセルは、 ★いくつかのレジスタ、好ましくはペースレジスタ内のリジュースされるべき目 標を、また、 ★ある場合、例えば３レベル構造がリジュースされる時には、好ましくは補助レ ジスタ内の目標のルーツおよびペースレジスタマトリックス内の残余の構造を、 記憶する。

コアセル内の一時ストレージにおいては、４つの場合、すなわち、０，１，２、 または３レベルのオブジェクトを記憶する場合がある。

簡単な木、すなわち単一の値（０レベルのオブジェクト）は、第１主レジスタ内 に記憶される。

ルベルのみを含む木は、主レジスタ内に記憶される。

２レベルを含む木は、主レジスタに水平に記憶された、親であるルーツリストと 、ペースレジスタに垂直に記憶された子であるリストと、を有しつる。あるいは その代わりとして、ルーツは補助レジスタに、またその子の１つは主レジスタに 記憶されることもできる。制御装置６ｐは、行なわれるべき実際の演算に基づい て、これらの異なる方式の一方または他方を選択しうる。

３レベルを含む木は、そのルーツリストを補助レジスタの１つに記憶され、また その２レベルの子の１つをペースマトリックスに記憶される。

このように、目標の木のルーツリストは、好ましくは、木の構造のレベルと、行 なわれるべき演算とに基づいて、コアセル内の諸レジスタの異なる場所に記憶さ れる。

目標の木のルーツは、ｕｎｉｆｙなどのりジュース可能な種類のクロジャーであ る。ファンクションの適用（ａｐｐｌｙ　・・・）においては、第１エレメント は、ファンクションの定義として用いられるクロジャー構造を間接的に指示する 命令または識別子であり、他の諸エレメントは、命令／ファンクションの定義に 対する引数である。

コアセルストレージの制御 コアレジスタ内に記憶される情報は、オブジェクトストレージ４ｐ内の情報から 得られる。コアレジスタ内の情報は、以下のようにして記憶される。

ＡＴＴＲＩＢＵＴＥ平面内におけるストレージ制御ＡＴＴＲＩ　ＢＵＴＥ平面内 のコアレジスタは、オブジェクトストレージバスＯＢＪに接続されている。記憶 された状態は、識別子レジスタＴＤ、、補助レジスタＦｏＴからＦ３ｔまで、お よびペースレジスタＳ、。からＳ２゜まで、に記憶された状態から成る。

ＡＴＴＲＩ　ＢＵＴＥ平面内のコアレジスタセルへの制御ワードは、スイッチＳ Ｗ□、ＳＷ、、、。、（ただしｉは０と３との間の数）、ｓｗ、、、、ｏ　、ｓ ｗｃ、、、。、Ｓ　ｗＷｌ、　ｂｏ、ＳＷ、、、、、　、および５Ｗｖｉ、ｈｏ と、識別子レジスタＩＤ、と、補助レジスタＦｏＴからＦ３ｔまでと、主レジス タＳ０．。からＳ３．。までと、へのより小さい制御ワードを含む。

制御ワードは、制御装置６ｐに接続されたいくつかの制御ワイヤを経て転送され る。制御ワイヤは、使用されるスイッチの種類により、２相制御対ワイヤまたは 単相制御車ワイヤでありうる（第９Ｅ図および第９Ｆ図参照）。

主レジスタＳｏ、。からＳｘ、ｏまでの中のそれぞれのセルへの制御ワードは、 それぞれのペースレジスタに対する１つの共通部分および個別的諸部分を経て転 送される。

共通部分は、コアセルのスイッチＳＷ、。、ＳＷ、。、およびＳＷ、（第１５図 参照）を制御する。しかし、ここでの説明内容は単に例として見られるべきもの であること、またいくつか他の実施例が考えられうることに注意すべきである。

ＨＥＡＤおよびＮＵＭ平面内におけるストレージ制御平面ＨＥＡＤおよびＮＵＭ 内のコアレジスタは、オブジェクトストレージバスＯＢＪと、アクセスバスＡＣ Ｃと、ｒｅｓバスと、数値ＡＬＵバスＮＵと、に接続されている。記憶された状 態は、２つの単一レジスタＪＤおよびＥＮＶと、補助レジスタＦＯからＦ３まで と、ペースレジスタＳ１．６からＳ５．、までと、の記憶された状態から成る。

コアレジスタへの制御ワードは、スイッチＳＷ□、ＳＷ、、、、、（ただしｉは ０と３との間の数）、Ｓ　Ｗ　ｌｄ、　ｈａ　、Ｓ　Ｗｅｂ、　ｋｍ　、Ｓ　Ｗ ＠＋１１１．　ｂｅｓ　Ｓ　Ｗｖ　ｒ、　ｂｅ、Ｓ　Ｗｒｙ、　ｋｍ　、および ５ｗｔ１．。、ＳＷ□。、ＳＷ、、、５Ｗｖｔ１およびＳＷ、ｓと、単一レジス タＩＤおよびＥＮＶと、補助レジスタＦＯからＦ３までと、ペースレジスタＳ、 。からＳ３．までと、への制御ワードから成る。

制御ワードは、副部装置６ｐに接続されたいくつかの制御ワイヤを経て転送され る。制御ワイヤは、使用されるスイッチの種類により、２相制御対ワイヤまたは 単相制御車ワイヤでありうる（第９Ｅ図および第９Ｆ図）。

それぞれのペースレジスタセルへの制御ワードは、それぞれのペースレジスタに 対する１つの共通部分および個別的諸部分を含む。共通部分は、コアセルのスイ ッチＳＷ、。、ＳＷｌ。、およびＳＷｏ　（第８図参照）を制御する。しかし、 ここでの説明内容は単に例として見られるべきものであること、またいくつか他 の実施例が考えられうることに注意すべきである。

コアレジスタの動作の例 第１８図から第２４図までは、第７図から得られる。

第７図に用いられている参照符号は、第１８図から第２４図までに対しても適用 される。しかし、多くの参照番号は、読みやすくするために省略されている。ま た、第１８図から第２４図までの説明においては、レジスタセルの表示は諸子面 ２ｐを貫通して延長する全レジスタを意味するものとする。

１、オブジェクトストレージ４ｐに対するアクセスｍｐｘ−ｍｖ命令： オブジェクトストレージの動作ｍｐｘ−ｍｖにより、オブジェクトストレージが 読取られ、主レジスタがセットされる。アクセスされたオブジェクトは、第１８ 図に、移送が行なわれる先のレジスタセルに向かう矢印を有する太線によって示 されているように、バスｖＯ１ｖｌ、ｖ２、ｖ３を経て主レジスタＳｏ、ｏ　、 Ｓ＋、＊　、Ｓｔ、＋＋、Ｓ３゜へ、バスｉｄを経てレジスタＩＤへ、またバス ｅｎｖを経てレジスタＥＮＶへ、移送される。同時に、主レジスタ内の古い内容 は、オブジェクトストレージ４ｐ内にクロジャーとして記憶される。このように して、ｍｐｘ−ｒｌｖ命令は、現在のコアセルクロジャーを、オブジェクトスト レージ内に記憶せしめ、また実行されるべき次のすプジェクトストレージクロジ ャーを、コアセル内ヘロードする。

ｆｅｔｃｈ命令： 第１９図および第２０１Ｎは、主レジスタの１つの中に記憶された識別子が存在 しており、その識別子がその示す情報のために交換されるべき状況を示す。例え ばＳｔ、。内に記憶されている識別子（第１９図参照）がオブジェクトストレー ジ４ｐへ供給され、そのオブジェクトストレージはその識別子とそれが示す内容 とを見出し、その内容はバス線ＶＯからｖ３までの上に供給されて、最終的には ペースレジスタの垂直列、例えばｓｔ、からＳ　ｔ、　、までにロードされる（ 第２０図参照）。

この動作は、ペースレジスタＳ２９．内の識別子を、バスｈＯおよびスイッチｉ ｄ＋ａ、ｈ。を経て垂直バスｉｄへ転送することによって開始される（第１９図 ）。記憶されている値は、任意の他のレジスタからも同様にして転送されつる。

動作は（第２０１Ｎ参照）、オブジェクトストレージ４ｐからバス線ｖＯ１ｖｌ 、ｖ２、ｖ３上へ供給された値を、本例においてはレジスタＳｔ、・、Ｓｔ、＋ 　ｓ　Ｓｔ、ｘ、Ｓ、１である適切なレジスタ内へ、それらの値をスイッチＳＷ 、、、ｓｗ、、、ｓｗ、、、ＳＷｏおよびバスｈｏ。

ｈｌ、ｈ２、ｈ３を経て転送して、ロードすることにより続けられる。

オブジェクトストレージの演算であるｍａｋｅおよびｕｎｉｆｙ−ｉｄは、コア セル内の内容がオブジェクトストレージ内に記憶されるべき時に、使用されうる 。

ｍａｋｅ　命令： 動作ｍａｋｅの第１ステツＩブにおいては、第２０図におけると同様ではあるが 逆の方向に、問題となっているレジスタの内容が転送される。この動作はまた、 環境レジスタの内容をも転送する。コアセルから供給された情報として記憶され たものと同じ情報を存するオブジェクトを発見するために、連想探索がオブジェ クトストレージ内において行なわれる。もしオブジェクトが発見されれば、その オブジェクトを示す識別子が戻され、もしオブジェクトが発見されなければ、使 用されていない識別子が戻される。双方の場合において、識別子は、オブジェク トストレージから、バス線ｉｄを使用してコアセル内の識別子レジスタへ転送さ れる。別の方法として、識別子は、影響を受けたレジスタ列内の主レジスタへ転 送されることも可能である。このようにして、コアセルの内容と識別子との間の 連想が作り出された。

ｕｎｉｆｙ−ｉｄ　命令： 動作ｕｎｉｆｙ−ｉｄは第２１図に示されており、レジスタの１つ、例えばＳｌ 、。からの識別子を、問題となっているレジスタセルを水平バスｈＯに接続し、 また全ＳＷ、、、ＳＷ□１．などを経て水平バスｈＯに接続することによって、 全ての垂直バスｉｄ％ｅｎｖ、ｖｏ、ｖｌ、ｖ２、ｖ３へ分配する。これは、例 えば、ある識別子の存在を探索し、発見されたこの識別子の存在を新しい、リジ ュースされた簡単な値によって置換することを含む、連想探索および置換、を行 なう時に使用されうる動作である。

ｕｎｆｆｙ−ｉｄに類似した動作が、第１ステツプにおいてｍａｋｅを用いてコ アセルの内容に対する一意の識別子を得、第２ステツプにおいてそのコアセルの 内容をオブジェクトストレージに接続されたバス線上に供給せしめることによっ て、オブジェクトストレージをしてその識別子と、それが示す内容とを記憶せし めることも可能である。

２、数値リダクション 数値リダクションにおいては、リジュースすべきオブジェクト、すなわち目標は 、主レジスタ内に置かれる。

一般に、目標全体がリダクションに参加する。通常、主レジスタＳ０．。は、異 なる命令に対しては異なるビットパターンをなす命令コードを保持する。レジス タＳ１゜、およびＳｔ、。は、２項演算、すなわち２つのオペランドを存する演 算のために使用され、レジスタＳ１．。は単項演算、すなわち１つのオペランド を有する演算のために使用される。一般に、後続のレジスタはリスト形式で使用 され、従ってそれらの内容はりダクション後には左方へ移動せしめられる。

本質的な数値演算は、その後目標のレジスタＳ１゜、およびＳ、。の間において 行なわれる。数値ＡＬＵの主加算器は、これらの２レジスタに接続されている。

他の諸レジスタは、ｍｕｌ、ｄ　ｉ　ｖ、およびｍｏｄのような命令において、 補足的目的のために用いられつる。

以下の命令形式が用いられうる。

単項命令 レジスタＳ０１．が命令を保持し、レジスタＳ１．。がオペランドを保持する。

レジスタＳ３．。およびＳｌ、。は使用されない。数値ＡＬＵの結果は、全ての 主レジスタへ戻される。非バイブラインの場合には、それはレジスタＳ１．。内 ヘセーブされる。バイブラインの場合には、それは直ちに、補助レジスタ内また はペースレジスタ内ヘセーブされる。

２項命令 レジスタＳ０．。が命令を保持し、レジスタＳ１．。、Ｓｌ、。がオペランドを 保持する。レジスタＳｓ、。は使用されない。結果は、全ての主レジスタへ戻さ れる。バイブラインの場合には、それは直ちに、補助レジスタ内またはペースレ ジスタ内ヘセーブされる。

ｍｕｍ　ｄｉｖＳｍｏｄ命令 レジスタＳ０．。が命令を保持し、レジスタＳｔ、。およびＳ２８．がオペラン ドを保持する。レジスタＳ８．。は、中間結果を一時記憶するのに用いられうる 。最終結果は、レジスタＳ１゜内ヘセーブされる。

ｕｎｉｆ）’リダクション ｕｎｉｔｙリダクションは、数値ＡＬＵを用いて、レジスタＳ０゜内の内容を、 レジスタＳ３．。内の内容と比較する。他の主レジスタも、単一化を行なう時に 使用されつる。次の動作を評価するために、諸レジスタのＨＥＡＤ平面内に記憶 されているタグワードが、比較の結果と共に用いられる。

命令ｍｕｌ、ｄｉｖ、およびｍｏｄは、完全に数値演算装置内において、それら のインナループ（１ｎｎｅｒｌｏｏｐ）を行なう。計算された中間値は、数値演 算装置と、コアセル内の主レジスタとの間のワイヤ上、すなわちＮＵババス上、 動的に記憶されつる。

３、構造のりダクション 構造のりダクションに際しては、リジュースすべきオブジェクト、すなわち目標 は、主レジスタ内に置かれる。

一般に、いくらかの、または全てのペースレジスタがリダクションに参加する。

通常は、主レジスタＳ０．。が、異なる命令に対しては異なるビットパターンを なす命令コードを保持する。

ｍ　ａ　ｐ命令は、ファンクシジンｆと、引数としてのリスト（ｅ＋　、・・・ 、ｅ、）とを有し、そのファンクションをそのリストの全エレメントに適用する 。この命令は、全てのファンクション適用の結果であるリスト（ｆｅｌ、・・・ 、ｆｅ、）を戻す。ただし、ｆｅ＋はｆをｅｌに適用した結果を表わす。

マツピング命令 フォーマット：（ｍａｐ　ｆ　１ｉｓｔ）命令ｍａｐは、補助レジスタセル内に ロードされる。

使用すべきファンクションは、補助レジスタセル内にロードされる。リストは、 主レジスタＳ、９．からＳｌ、。までにロードされる。第２２ａ図に示されてい るように、主レジスタ内に記憶されたエレメントは、ペースレジスタマトリック スにおいて２段階アップして転送される。

すなわち、ＸをＯと３との間の数として、レジスタＳ８．。内の内容は、レジス タＳ□、、へ転送される。この転送は、垂直バス線ｖＯからｖ３までを用いて行 なわれる。次に、第２２ｂ図に示されているように、補助レジスタＦＯからＦｌ までの内容が、水平にペースレジスタへ同報通信される。すなわち、ＦＯの内容 はＳ６．。からＳ５，０までへコピーされ、ＰＩの内容はＳｓ、ＩからＳｓ　Ｉ までへコピーされる。もしエレメントが（リストでない）単純な値であれば、そ れが置かれているレジスタセル、例えばＳｌ、ｔの内容と、その下のレジスタセ ル、例えばＳｌ、＋の内容とは、１段階下方ヘシフトされる。

ここで、適用されるべきファンクションは主レジスタセル、例えばＳｌ、。内に 存在しており、そのファンクションを適用されるべきエレメントは、いまこの主 レジスタセルの上のレジスタセル、例えば８１．１内に存在している。もしエレ メントがリストであれば、レジスタのその列においてシフトは行なわれない。第 ２２ｃ図においては、ｅ＋、ｅｂ、およびｅ、は単純な値を表わし、またｅ４は 挿入されたリストを表わしているものと仮定されている。その場合、ペースレジ スタマトリックス内のそれぞれの列は、オブジェクトストレージ内にクロジャー として記憶される。その後、これらの記憶されたクロジャーは、続いての処理の ために、コアセル内ヘコードされる。もし記憶されたクロジャーが単純な値を含 有していたとすれば、それはコアセル内に通常のようにコードされる。すなわち 、第２２ｄ図に示されているように、ｆはＳｏ、。内に記憶され、ｅｉはＳ、。

内に記憶される。

一方、もし記憶されたクロジャーが挿入されたリストを含有していたとすれば、 それは、前述のように、第２２ａ図に示されているようにロードされるが、その 際、ｅｌはｅ４によって表わされるリスト内の第１エレメントとなり、ｅ、はｅ 、内の第２エレメントとなり、等となる。これは、ｍａｐ命令が、挿入された諸 リストに対して再帰的に作用することを可能ならしめる。

このようにして、２レベル構造を有する命令ｍａｐ（ｍａｐ、　ｆ、　（＠！Ｉ Ｆ　−−ｔ　”Ｈ））は、 （（ｆ−＠！１）、　、・ｐ　（’、％））に書面され、これは実行後にはルベ ル構造（ｆｅｄ、　＋、、　ｆｅｎ） に書面される。ただし、ｆｅＩは、ｆをｅ、に対して適用した時の結果を表わす 。

３（またはそれ以上）レベル構造を有する命令ｍａｐ（”Ｐ＃　ｆｔ　Ｐａｒ（ ”ｌＩ”ｚ　（”ｋｙ　−・ｚ’ｘ）ｔ　”ｚ　ｔＨ））（ただし、（ｅｋ、・ ・・、ｅ、）は挿入されたリスト）は、中間ステップとして Ｐａｒ（（ｆｒ　”ｌ）＃　０．、（”Ｐｙ　Ｌ　（”）Ｃ＃　”ｔ％Ｈ）ｂ　 ”ｔ　ＣＬ　＠Ｈ））に書面され、さらにその後 ｐａｒ（（Ｌ　＠１１）、−ｔ　（（Ｌ　”ｋ）ｙ−ｙ＜ｆｔ　％））＃−ｔ　 （ｆｔ　ａｎ））に書面されて、これは実行後、２レベル構造ｐａｒ（ｆｅｄ、 　−、ｔ　（ｆｅｋ、　、、、　ｆ〜）、　、−ｔ　ｆ＠ｎ）に書面される。、 ただし、ｆｅＩは、ｆをｅｌに対して適用した時の結果を表わし、（ｆ　ｅｂ　 、・・・、ｆｅ、）は挿入されたリストである。

このようにして、ファンクションｆは、引数リスト内の全エレメントに対し、再 帰的に適用される。

コアセルがどのようにｍａｐ命令を再構成し、かつ実行するかの例を以下に説明 する。記述を短縮するために、「レジスタ」の代わりに省略形ｒｅｇを、「識別 子」の代わりに１ｄｅｎｔを、「オブジェクトストレージ」のであり、ただしｆ は、ｆ　（ｘ）＝ａｂｓ　（ｘ）＋１として定義される。機械識別子を用いた機 械表示は、ｉｄｌ　：　（！ａａｐ　ｆ　１ｄ２）ｉｄ２　Ｋ　（−１−２１ｄ ３） ｉｄ３　ｇ　（−７−８） でありうる。ただし、１ｄｅｎｔ　ｉｄｌは、（ｍａｐｆ　１ｄ２）構造などを 示す。

以下において、ｉは０と３との間の数である。以下の諸ステップが行なわれる。

ステップ１：ｍａｐがｒｅｇ　ＦＯ内に、ｆがｒｅｇＦｌ内に、また１ｄｅｎｔ 　ｉｄ２がｒｅｇ　ＳｌＩ内に記憶される。

ステップ２：１ｄｅｎｔ　ｉｄ２が展開される。すなわち、ｒｅｇ　ｓＯ，＠が −１を含有し、ｒｅｇ　Ｓ、、。

が−２を含有し、またｒｅｇ　ｓ２．Ｇが１ｄｅｎｔｉｄ３を含有する。

ステップ３：ｒｅｇ　Ｓ＋、ｏの内容がｒｅｇ　Ｓ＋、ｔへ転送される。不使用 とマークされたレジスタは影響を受けない。

ステップ４：ｍａｐおよびｆが水平に同報通信される。

すなわち、ｒｅｇ　Ｓ＋、＋がｆを含有し、ｒｅｇＳ６．。がｍａｐを含有する 。不使用とマークされたレジスタは影響を受けない。

ステップＳ：Ｓ、、を内に単純な値を有する列は１段階下方へ圧縮される。すな わち、ｒｅｇ　Ｓｏ、＋が−１を含有し、ｒｅｇ　Ｓｏ、ｓがｆを含有し、ｒｅ ｇ　ｓｌ、１が−２を含有し、ｒｅｇ　Ｓ＋、。がｆを含有し、第３列はタッチ されない。

ステップ６：ベースレジスタマトリックス内の全ての列がストレージ内に、 ｉｄｌ　＝　（ｉｄ６　ｉｄ７１ｄ８）ｉｄ６　：　（ｆ　−１） ｉｄｌ　：　（ｆ　−２） ｉｄｌ　：　（ｍａｐ　ｆ　１ｄ３） として（再）記憶される。

ステップ７：１ｄｅｎｔ　ｉｄ８によって示されてしするクロジャーが、ｆはｒ ｅｇ　ｓ・、。内に、−１はｒｅｇ　Ｓｒ、。内に、というように主レジスタ内 にロードされる。

ステップ８：前記ファンクション、すなわちｆ　（ｘ）＝ａｂｓ　（Ｘ）＋１が 、引数に適用されて結果２を生じこれがｒｅｇ　Ｓｒ、ｓ内に記憶される。

ステップ９：１ｄｅｎｔ　ｉｄ６に対する連想探索がストレージ内において行な われ、１ｄｅｎｔ　ｉｄ６の全ての存在が２によって置換される： ｉｄｌ　：　（２ｉｄ）　１ｄ８） ｉｄ７　！　（ｆ　−２） ｉｄ８　！　（鮎ｐ　ｆ　１ｄ３） ステップ１０：１ｄｅｎｔ　ｉｄ７に対してステップ７からステップ９までが行 なわれ、結果３を生じる。ストレージは： ｉｄｌ　：　（２３１ｄ８） ｉｄ８　：　（貼ｐ　ｆ　１ｄ３） となる。

ステップ１１：１ｄｅｎｔ　ｉｄ８に対してステップＩからステップ６までが行 なわれ、その結果ペースマトリックス列の２つがストレージ内に記憶される：ｉ ａｌ　ｔ　（２３１ｄ８） ｉｄ８　Ｓ　（ｉｄ９１ｄｌｏ） ｉｄ９　：　（ｆ　−７） ｉｄｌｏ　ｚ　（ｆ　−８） ステップ１２：１ｄｅｎｔ　ｉｄ９および１ｄｌＯに３　対してステップ７から ステップ９までが行なわれ、それ１　ぞれ結果８および９を生じる。ストレージ は：ｉｄｌ　：　（２３１ｄ８） Ｌｄａ　ｔ　（８９） となる。これは、（２３（８９））と読取られ、ファンクションｆが引数リスト 内の全エレメントに適用されたことになる。

上述の諸ステップは、コアセルにより、異なったさらに効率的な方法で行なわれ うろことに注意すべきである。

例えば、オブジェクトストレージ内に中間結果を記憶せしめる代りに、適切な場 合には、コアセル内においてさらにリダクシタン／実行を行なうことができる。

ｔｒａｎｓｐｏｓｅ フォーマット：（ｔｒａｎｓｐｏｓｅ　１ｉｓｔ）ｔｒａｎｓｐｏｓｅ命令は、 補助レジスタの１つ、例えばＦＯにロードされ、リスト引数、例えば諸リストの リストは、ベーズレジスタマトリックスにロードされる（第２３図参照）。ペー スレジスタマトリックスの内容はトランスポーズされる。このようにして、３レ ベル構造 （ｔｒａｒｕｉｐｏｓｅ。

を有する命令ｔｒａｎｓｐｏｓｅは、その結果が２レベル構造 に書き直されるように実行される。

説明用の例： リスト構造 （（１２３４）。

（５６７８）。

（９１０１１１２）。

において、第１リスト、すなわち（１２３４）は、第１Ｍのペースレジスタ、す なわちペースレジスタＳ、、。からＳ　ｏ、　ｚまでに記憶され、第２リスト、 すゎなち（５６７８）は、第２列のペースレジスタ、すなわちペースレジスタＳ ＋、。からＳ１４までに記憶されており、等、の前記リスト構造は、 （（１５９１３）。

（２６１０１４）。

（３）１１１５）。

にトランスポーズされる。ただし、第１リスト、すなわち（１５９１３）は、第 １列のペースレジスタ、すわなちペースレジスタＳ０．。からＳ０１までに記憶 され、等となる。

ｓ　ｗ　ａ　ｐ フォーマット：　（ｓｗａｐ　ｍ　１１ｓｔ）ｓ　ｗ　ａ　ｐ命令は、３レベル 構造 （ｓｗａｐｍ　（（”１．ｌ＃　０．）’において、ｉおよびｊがペースレジス タマトリックス内におけるエレメントの位置を示すものとしてエレメントｅ＋、 □を育する諸リストのリストを含む、前記３レベル構造を有する命令ｓｗａｐが 、エレメント（ｅ＋ｓ、Ｉ、・・・）がエレメント（ｅａ＊１．ｌ、・・・）と 場所を代えた２重構造 に書画されるよう、実行される。

ｓｋｉｐ フォーマット：　（ｓｋｉｐ　ｍ　１ｉｓｔ）ｓｋｉｐ命令は、３レベル構造 （ｓｓｋｉｐ！１１　（（８１，Ｉ、−）ｔにおいて、ｉおよびｊがペースレジ スタ内におけるエレメントの位置を示すものとしてエレメントｅ１．ｊを有する 諸リストのリストを含む、前記３レベル構造を有する命令５ｋｉｐが、エレメン ト（ｅ　ｗａ、　ｒ　、・・・）の削除された２重構造 に書画されるよう、実行される。

４、リストの抽出 リストを含有する目標は、主レジスタ内に置かれる。

もしリストが、挿入されたリストであるエレメントを含有すれば、これらの挿入 されたリストは、補助レジスタに垂直に記憶される。

ｅｘｐａｎｄ−１ｉｓｔ動作は、１サイクル中に行なわれつる。ペースレジスタ の内容は、主レジスタの内容を除外して、対角線的に右下方へ１段階シフトされ 、主レジスタの内容は垂直バスへ転送されて、その列内の最上部のペースレジス タに挿入される（第２４図参照）。

ｅｘｐａｎｄ−１ｉ　ｓ　ｔを繰返して用いれば、主レジスタセルをデータによ って「満たす」ことができる。

ここに説明されたコアセルおよびレジスタセルの設計は、本発明の実施例を構成 するのであるが、本発明はそれらの正確な設計に制限されるものではないこと、 および本発明の範囲から逸脱することなく、そこには変更が行なわれうること、 を理解すべきである。

コアセルの他の実施例 第２５図は、コアセルのもう１つの実施例を示す。第７図におけると同じ参照符 号が、同じコアセルエレメントに対して用いられている。ｔｓ７図におけると異 なる接続を有するコアセルエレメントには′のマークが付けられている。好まし い実施例である第７図の実施例と、第２５図に示されている実施例との閏の主な 相違は、ペースレジスタセルＳ　’　Ｌｌ　、Ｓ’　＋、ｅ　、Ｓ’　＊。、お よびＳ′、１が、スイッチをもたないワイヤｒｅｓ’に接続可能であることであ る。さらに、バスＪＩＩＣ，，およびｃｒが省略されている。さらに、ｙを０と ３との間の数とするとき、ペースレジスタセルｓ０．２のＷ（西）端子は、ペー スレジスタセルＳ８．アのＥ（東）端子に接続されておらず、その代りに、これ らの端子は、ｆ（偽）信号を供給される。コアセル内部の接続は、ある命令に対 してはいくぶん異なるように行なわれうるが、それはファンクション的な相違で はなく、コアレジスタ内のどのスイッチが制御されるべきかの相違に過ぎない。

レジスタセル間の接続もまた、わずかに異なっていることが示されるが、これも またそれぞれのレジスタセルの内部のどの内部スイッチがｌｉＩＩｍされるべき かの問題である。

第２６図は、セル内において制御されるべきスイッチは、異なる方法で配置され うること、しかし、セルはなお同じファンクションを有しうること、の事実の例 を与えるための、コアレジスタセルの第２実施例を示す。第８図におけると同じ 参照符号が、同じセルエレメントに対しては用いられている。第８図におけると 異なる接続を育するエレメントには、′のマークが付けられている。

第８図および第２６図に示されている両実施例間の主な相違は、第２６図におい ては端子ＣおよびスイッチＳＷｃが省略され、かつ端子ＶおよびＨがそれぞれ１ つのスイッチしかもっていないことと、スイッチをもっている端子り、Ｌ＝、お よびＤが、スイッチをもっている端子ＤａおよびＤｂの代わりに用いられている ことと、である。

以上においては、本発明を特定の実施例に関して説明してきたが、本技術分野に 習熟している者ならば、本発明の真の精神および範囲から逸脱することなく、さ まざまな変更が可能であり、またその諸エレメントに対し等価のものを代用しう ることを理解しつるはずである。さらに、本発明の本質的教示から逸脱すること なく改変を行なうことも可能である。

ＦＩＧ、４Ｂ Ｆ旧、４ＣＦＩＧ、／＋Ｄ Ｆ旧、４Ｅ　ＦＩＧ、４Ｆ ＦＩ３．４Ｇ ＦＩＧ、５ＣＦＩＧ、５Ｄ ＦＩＧ、６Ａ ＦＩＧ、６Ｂ Ｄｂ　Ｎ 総称レジスタセルか１Ｍおよび（メＤ平面）ＦＩＧ、９Ａ　ＦＩＧ、９８　ＦＩ Ｇ、９Ｃ送１セル　受信セル ベースレジスタセル１　ベースレジスタセル２送信セ、、　受信セル ＦＩＧ、１８　ＦＩＧ、１９ 要　約　書 構造演算処理の方法および演算装置が説明される。データワードがいくつかのレ ジスタに記憶され、それぞれのデータワードはマーク部分および情報部分を有す る。

マーク部分は、問題となっているレジスタが使用されているか否かを示すマーク を含む。データワードは、リスト内に配置される。それぞれのリストは、所定数 のレジスタに記憶される。レジスタに記憶されているリスト内のそれぞれのワー ドのマーク部分は、使用されているマークを有するとき、リストの１つの少な（ とも一部分が実際のレジスタに記憶されていることを示す。一部を該実際のレジ スタに記憶されているリストは、それがとのような種類のリストであるか、また レジスタ内のリストの配列のどこからリスト間の関係が明らかになるのか、につ いてのリスト命令を含む。レジスタは、レジスタに記憶されているリストに属す るリスト命令を用い、リストをレジスタ間において再配列し、かつリスト命令に 従ってレジスタの内容を入力／出力する、制御装置により制御される。

国際調査報告 ＋＋１１ｅｒ＋＋＋＋＋ｌｅ＋ｕ１＾−１１１，，１，−１１−ＰＣＴ／ＳＥ　 ９１１００５１４国際調査報告 ＰＣＴ／ＳＥ　９１１００５１４

Claims (57)

【特許請求の範囲】
1. １．ａ）いくつかのレジスタ内にデータワードを記憶せしめるステップであって 、それぞれのデータワードがマーク部分および情報部分を有し、該マーク部分が 問題となっているレジスタが使用されているか否かを示すマークを含む、前記デ ータワードを記憶せしめるステップと、 ｂ）前記データワードがリスト内に配置されており、該リストのそれぞれを所定 数の前記レジスタに記憶せしめるステップであって、使用されているとのマーク を有する前記レジスタに記憶されている前記リスト内のそれぞれの前記ワードの 前記マーク部分が、前記リストの１つの少なくとも一部分が実際の前記レジスタ に記憶されていることと、一部分を該実際のレジスタに記憶されている前記リス トが、それがどのような種類のリストであるか、また前記レジスタ内の前記リス トの配列のどこから前記リスト間の関係が明らかになるのか、についてのリスト 命令を含むことと、を示している、前記ステップと、ｃ）前記レジスタを制御し 、かつ該レジスタに記憶されているリストに属する前記リスト命令を用いること により、該リストを該レジスタ間において再配列し、前記リスト命令に従ってレ ジスタ内容を入力／出力するステップと、 を含む、構造演算処理の方法。
2. ２．前記レジスタに記憶される前記リストを、該リストの１つをルーツリストと して有するリストの木として配列することを特徴とする、請求項１記載の方法。
3. ３．前記記憶されているリストの木の識別子を、分離された識別子レジスタに記 憶せしめることを特徴とする、請求項２記載の方法。
4. ４．前記記憶されているリストの木の環境を、分離された環境レジスタに記憶せ しめることを特徴とする、請求項２または請求項３記載の方法。
5. ５．前記リストの木のルーツリストを、記憶されるべき該実際の木のレベルによ って異なるレジスタ内に置くことを特徴とする、請求項２から請求項４までのい ずれかに記載の方法。
6. ６．前記レジスタのあるものを主レジスタの行を含むベースレジスタのマトリッ クス内に配置することを特徴とする、請求項５記載の方法。
7. ７．１レベルのみを含む木を主レジスタ内に記憶せしめることを特徴とする、請 求項５記載の方法。
8. ８．２レベルを含む木を、そのルーツリストは前記主レジスタ内に、そのブラン チリストは前記ベースレジスタ内に配置するようにして記憶せしめることを特徴 とする、請求項５記載の方法。
9. ９．前記マトリックスの外部に、補助レジスタと呼ばれる余分のレジスタの組を 配置することを特徴とする、請求項５記載の方法。
10. １０．３レベルを含む木を、そのルーツリストは前記補助レジスタ内に記憶され 、またそのエレメントの１つは前記レジスタのマトリックス内に記憶されるよう にして、記憶せしめることを特徴とする、請求項９記載の方法。
11. １１．どのような種類のリダクションが行なわれるべきかに関する情報が前記ル ーツリストのタイプから導かれうることを特徴とする、請求項２から請求項１０ までのいずれかに記載の方法。
12. １２．前記ルーツリストの前記タイプ内の前記情報が、実行されるべき命令を表 わす命令コードを含むことを特徴とする、請求項１１記載の方法。
13. １３．もし前記タイプがファンクションの適用ならば、前記ルーツリストの第１ エレメントが、ファンクションの定義を表わす命令コードまたはリストの木のル ーツを含むことを特徴とする、請求項１１記載の方法。
14. １４．１リスト内の最大ワード数が４であることを特徴とする、請求項１から請 求項１３までのいずれかに記載の方法。
15. １５．前記リストの木の最大深度が３レベルであることを特徴とする、請求項２ から請求項１４までのいずれかに記載の方法。
16. １６．前記深度が３レベルであり、かつ前記レジスタに記憶されている前記ルー ツリストの前記リスト命令が、前記ルーツリストが１つより多くのブランチを有 することを示していれば、該ブランチの１つのみが前記レジスタに記憶されるこ とを特徴とする、請求項１４記載の方法。
17. １７．構造リダクションが、前記ベースレジスタ内または前記ベースレジスタお よび補助レジスタ内などの、前記レジスタ内に置かれたデータオブジェクトに対 して行なわれることを特徴とする、請求項６から請求項１６までのいずれかに記 載の方法。
18. １８．２レベル構造 （ｍａｐ，ｆ，（ｅ１，・・ｅｎ）） において、命令ｍａｐは１つの補助レジスタ内に書込まれており、マッピングす るためのファンクションは第２の該補助レジスタ内に書込まれており、命令エレ メントｅ１のリストは前記ベースレジスタ内に書込まれている前記２レベル構造 を有する命令ｍａｐが、前記ベースレジスタのそれぞれの死において、前記ファ ンクションが該列内の最下部のベースレジスタ内に配置され、前記命令エレメン トの１つが該列内の第２最下部ベースレジスタ内に配置されるように、前記ファ ンクションが同報通信され且つ前記命令エレメントが再配置された（（ｆ，ｅ１ ），・・・（ｆ，ｅｎ））に、制御装置からの制御によって書直されるように、 マッピング命令が実行されることを特徴とする、請求項１７記載の方法。
19. １９．３レベル構造 （ｔｒａｎｓｐｏｓｅ， （（ｅ１，１，・・ｅ１，ｍ）， ・・・ （ｅｎ，１，・・ｅｎ，ｍ））） において、命令ｔｒａｎｓｐｏｓｅは補助レジスタ内に書込まれており、命令エ レメントｅ１．ｊ（ｉおよびｊは、前記マトリックス内における該命令エレメン トの位置の表示である）の諸リストのリストは、ベースレジスタ複合体がエレメ ントの正方形を含むように、ベースレジスタの前記マトリックス内に書込まれて いる前記３レベル構造を有する命令ｔｒａｎｓｐｏｓｅが、２レベル構造（（ｅ １，１，・・ｅｎ，１） ・・ （（ｅ１，ｍ，・・ｅｎ，ｍ）） において、補助レジスタの値は空にされており・ベースレジスタの前記マトリッ クス内の前記情報エレメントは、該マトリックスの対角線に関し鏡映位置に配置 されるようにトランスポーズされている前記２レベル構造に、制御装置からの制 御によって書直されるように、ｔｒａｎｓｐｏｓｅ命令が実行されることを特徴 とする、請求項１７記載の方法。
20. ２０．３レベル構造 （ｓｗａｐ　ｍ（（ｅ１，１，・・），・・ （ｅｍ，１，・・）， （ｅｍ＋１，１，・・）， ・・・ （ｅｎ，１，・・））） において、命令エレメントｅｉ．ｊ（ｉおよびｊは、ベースレジスタの前記マト リックス内における該命令エレメントの位置の表示である）の諸リストのリスト は、ベースレジスタ複合体がエレメントの正方形を含むようにされている、前記 ３レベル構造を有する命令ｓｗａｐが、エレメント（ｅｍ．１、・・・）とエレ メント（ｅｍ＋１．１、・・・）との位置の入れ換った２レベル構造（（ｅ１， １，・・）， ・・ （ｅｍ＋１，・・）， （ｅｍ，１，・・）， ・・・ （ｅｎ，１，・・）） に、制御装置からの制御によって書直されるように、ｓｗａｐ命令が実行される ことを特徴とする、請求項１７記載の方法。
21. ２１．３レベル構造 （ｓｋｉｐ　ｍ（（ｅ１，１，・・），・・ （ｅｍ−１，１，・・）， （ｅｍ，１，１・・）， （ｅｍ＋１，１，・・）， ・・ （ｅｎ，１，・・）） において、命令エレメントｅｉ，ｊ（ｉおよびｊは、ベースレジスタの前記マト リックス内における該命令エレメントの位置の表示である）の諸リストのリスト を含む前記３レベル構造を有する命令ｓｋｉｐが、エレメント（ｅｍ．１、・・ ・）の削除された ・・ （（ｅ１，１，・・）， （ｅｍ−１，１，・・）， （ｅｍ＋１，１，・・）， ・・・ （ｅｎ，１，・・）） に、制御装置からの制御によって書直されるように、ｓｋｉｐ命令が実行される ことを特徴とする、請求項１７記載の方法。
22. ２２．ａ）データリストの入力および出力のための少なくとも１つの入力／出力 手段（ｖ０、ｖ１、ｖ２、ｖ３、ｉｄ、ｅｎｖ）と、 ｂ）それぞれがデータワードを記憶するようにされた、いくつかのレジスタ（Ｓ ｏ，ｏ、からＳ３．３まで、Ｆ０からＦ３まで、ＩＤ、ＥＮＶ）であって、それ ぞれのデータワードがマーク部分および情報部分を有し、 該マーク部分が問題となっている前記レジスタが使用されているか否かを示すマ ークを含み、それぞれの前記リストが所定数の前記レジスタに記憶可能であり、 使用されているとのマークを有する前記レジスタのうちのそれぞれの該レジスタ の前記マーク部分が、前記リストの１つの少なくとも一部分が実際の前記レジス タに記憶されていることと、一部分を該実際のレジスタに記憶されている前記リ ストが、それがどのような種類のリストであるのか、また前記レジスタ内の前記 リストの配列のどこから前記リスト間の関係が明らかになるのか、についてのリ スト命令を含むことと、を示している、前記いくつかのレジスタと、 ｃ）前記レジスタを制御し、かつ該レジスタに記憶されているリストに属する前 記リスト命令を用いることにより、該リストを該レジスタ間において再配列し、 かつ前記リスト命令に従ってレジスタ内容を入力／出力する制御手段（６ｐ）と 、 を含む、構造演算処理用の演算装置。
23. ２３．前記レジスタに記憶されている前記リストが、該リストの１つをルーツリ ストとして有するリストの木として配列されていることを特徴とする、請求項２ ２記載の演算装置。
24. ２４．リストを記憶するレジスタの前記所定数の最大値が４であることを特徴と する、請求項２２または請求項２３記載の演算装置。
25. ２５．前記リストの木の最大深度が３レベルであることを特徴とする、請求項２ ３または請求項２４記載の演算装置。
26. ２６．前記深度が３レベルであり、かつ前記レジスタに記憶されている前記ルー ツリストの前記リスト命令が、前記ルーツリストが１つまたは１つより多くのブ ランチを有することを示していれば、前記制御手段が該ブランチの１つのみを前 記レジスタに記憶せしめるようになっていることを特徴とする、請求項２５記載 の演算装置。
27. ２７．少なくとも１つの余分のレジスタ（ＩＤ）が備えられており、その中に前 記記憶されているリストの木の識別子が記憶されうることを特徴とする、請求項 ２２から請求項２６までのいずれかに記載の演算装置。
28. ２８．少なくとも１つの余分のレジスタ（ＥＮＶ）が備えられており、その中に 前記記憶されているリストの木の環境が記憶されうることを特徴とする、請求項 ２２から請求項２７までのいずれかに記載の演算装置。
29. ２９．主レジスタをなす周辺行（Ｓ０．０、からＳ３．０まで）を有するレジス タのマトリックス（Ｓ０．０からＳ３．３まで）を含み、該マトリックスの諸列 がベースレジスタをなす、請求項２２から請求項２８までのいずれかに記載の演 算装置。
30. ３０．前記マトリックスの外部に配設されたいくつかの補助レジスタ（Ｆ０から Ｆ３まで）を含むことを特徴とする、請求項２９記載の演算装置。
31. ３１．前記リストの木の前記ルーツリストが、記憶されるべき該実際の木のレベ ルによって異なるレジスタ内に置かれるようになっていることを特徴とする、請 求項２３から請求項３０までのいずれかに記載の演算装置。
32. ３２．１レベルのみを含む木が前記主レジスタ（Ｓ０．０、からＳ２．０まで） に記憶されるようになっていることを特徴とする、請求項２９記載の演算装置。
33. ３３．２レベルのみを含む木が、そのルーツリストは前記主レジスタ（Ｓ０．０ 、からＳ３．０まで）内に、そのブランチリストは前記ベースレジスタ（Ｓ０． ０からＳ０．３まで、Ｓ１．０からＳ１．２まで、Ｓ２．０からＳ２．３まで、 Ｓ２．０からＳ２．２まで）内に記憶されるようになっていることを特徴とする 、請求項２９記載の演算装置。
34. ３４．３レベルを含む木が、そのルーツリストを前記補助レジスタ（Ｆ０からＦ ３まで）内に記憶され、またそのエレメントの１つを前記レジスタのマトリック ス内に記憶されるようになっていることを特徴とする、請求項３０記載の演算装 置。
35. ３５．どのような種類のリダクションが行なわれるべきかに関する情報が、前記 制御手段（６ｐ）により前記ルーツリストのタイプから導かれうることを特徴と する、請求項２３から請求項３４までのいずれかに記載の演算装置。
36. ３６．前記ルーツリストの前記タイプ内の前記情報が、どのような種類の命令を 実行すべきかを推論するために前記制御手段（６ｐ）により使用される命令コー ドを含むことを特徴とする、請求項３５記載の方法。
37. ３７．もし前記タイプがファンクションの適用ならば、前記ルーツリストの第１ エレメントが、ファンクションの定義を表わす命令コードまたはリストの木のル ーツを含み、それが、前記ルーツリストをリジュースするために行なうべき動作 を推論するのに前記制御手段（６ｐ）により用いられることを特徴とする、請求 項３５記載の方法。
38. ３８．前記レジスタがコアセル内の諸平面内に、それぞれの平面がそれぞれのレ ジスタから多くとも１つのレジスタセルを含むようスライス状に、論理的に配置 されていて、それぞれのレジスタセルが１ビットの情報を記憶可能であり、かつ １平面内のレジスタセルが互いに接続可能であることを特徴とする、請求項２２ から請求項３７までのいずれかに記載の演算装置。
39. ３９．前記レジスタのあるものが他のレジスタより長いために、前記平面のある ものは、該長いレジスタに属するレジスタセルのみを有する（第１２図）ことを 特徴とする、請求項３８記載の演算装置。
40. ４０．ベースレジスタと名づけられている少なくともいくつかの前記レジスタが 、Ｎをある整数として、Ｎ×Ｎレジスタのマトリックスにおける、行および列を なして配列されていることと、前記ベースレジスタの前記レジスタセルが、ビッ ト毎に相互接続されていることと、前記ベースレジスタ内のそれぞれのビットに おいて、それぞれの列に対しては列ワイヤ（ｖ０、ｖ１、ｖ２、ｖ３）が備えら れ、それぞれの行に対しては行ワイヤ（ｈ０、ｈ１、ｈ２、ｈ３）が備えられ、 同じ行および列番号を有する前記列ワイヤと前記行ワイヤとの間のそれぞれの交 点には、制御可能なスイッチ（ＳＷｖ０、ＳＷｖ１、ＳＷｖ２、ＳＷｖ３）が備 えられていて、それぞれのベースレジスタが、少なくともその最も近い行ワイヤ および列ワイヤによる、制御可能なレジスタ接続を有することと、接続が、前記 行に沿ってと、前記列に沿ってとの双方における、相隣るベースレジスタ間に設 けられていることと、を特徴とする、請求項３８記載の演算装置。
41. ４１．前記制御手段（６ｐ）が、前記制御可能スイッチおよび前記制御可能なレ ジスタ接続を制御し、実行されるべき命令の種類に依存して、少なくとも３種類 の接続、すなわち ａ）１つのレジスタからもう１つのレジスタヘの簡単な接続と、 ｂ）レジスタ間における、いずれの方向にも１つずつの、２つの別個の接続と、 ｃ）レジスタ間における時間多重接続であって、２つの相次ぐ位相において、記 憶されているリストエレメントが１方向および他方向へ移送される前記時間多重 接続と、の１つを行なうようになっていることを特徴とする、請求項４０記載の 演算装置。
42. ４２．レジスタ内のそれぞれのレジスタセルが、ａ）内部１ビットレジスタ（ｒ Ｒ）と、ｂ）該１ビットレジスタに接続可能な、少なくとも１つの内部１ワイヤ バス（ａＲ、ｂＲ）と、ｃ）少なくとも１つの内部的な、制御可能な接続であっ て、それぞれが、前記少なくとも１つの１ワイヤバスの１つを以下の素子、すな わち前記セルの外部のバス、前記レジスタのもう１つのものに属するセルの１つ 、の一方に接続可能ならしめる、前記制御手段（６ｐ）によって制御可能なスイ ッチ（ＳＷＮ、ＳＷｇ、ＳＷｖ１、ＳＷｖｏ、ＳＷＨｉ、ＳＷＨｏ、ＳＷＤｂ、 ＳＷａｏ、ＳＷａｌ、ＳＷｂ０、ＳＷｂ１）を含む、前記接続と、を含むことを 特徴とする、請求項２２記載の演算装置。
43. ４３．前記少なくとも１つの内部１ビットレジスタ（ｒＲ）が、インバータなど の入力バッファ手段（Ｑ１）と、インバータなどの出力バッファ手段（Ｑ２）と 、該バッファ手段間に接続された制御可能スイッチ（ＳＷＱ）と、を含むことを 特徴とする請求項４２記載の演算装置。
44. ４４．前記入力バッファ手段および前記出力バッファ手段が、制御可能スイッチ により、別個に前記少なくとも１つの内部１ワイヤバス（ａＲ、ｂＲ）に接続可 能であることを特徴とする、請求項４３記載の演算装置。
45. ４５．それぞれのレジスタセルが、 ａ）第１（ａＲ）および／または第２（ｂＲ）内部１ワイヤバスと、 ｂ）内部１ビットレジスタ（ｒＲ）と、ｃ）前記第１バスを、該内部レジスタの 第１入力に対し、また他のレジスタセルに結合せしめられている第１組のいくつ かの外部バスに対し、接続可能ならしめる前記制御手段により制御可能なスイッ チを含む、第１組の内部的な、制御可能な接続と、 ｄ）前記第２バスを、前記内部レジスタの第２入力に対し、また他のレジスタセ ルに結合せしめられている第２組のいくつかの外部バスに対し、接続可能ならし める前記制御手段により制御可能なスイッチを含む、第２組の内部的な、制御可 能な接続と、 ｅ）前記内部１ビットレジスタの出力を、第３組のいくつかの外部バスに対して 接続可能ならしめる前記制御手段により制御可能なスイッチを含む、第３組の内 部的な、制御可能な接続と、 を含むことを特徴とする、請求項４０記載の演算装置。
46. ４６．前記レジスタの位置に依存して、前記レジスタセルのあるものが、前記内 部レジスタに対する前記接続の１つではない、少なくとも１つのその内部接続に 固定的に接続された固定値を有することを特徴とする、請求項４５記載の演算装 置。
47. ４７．それぞれの前記制御可能な接続が、以下の構成、すわなち、１つのＭＯＳ −ＦＥＴ（第９Ｅ図）、２つの相補形ＭＯＳ−ＦＥＴ（第９Ｆ図）、の一方を含 む少なくとも１つの制御可能スイッチであることを特徴とする、請求項４５記載 の演算装置。
48. ４８．それぞれのインバータが、以下の構成、すなわち、２つの相補形ＭＯＳ− ＦＥＴ（第９Ｃ図）、２つのエンハンスメント形ＭＯＳ−ＦＥＴ（第９Ａ図）、 １つのエンハンスメント形ＭＯＳ−ＦＥＴおよび１つのデプレション形ＭＯＳ− ＦＥＴ（第９Ｂ図）、の１つを含むことを特徴とする、請求項４３記載の演算装 置。
49. ４９．比較器（Ｇ１、Ｇ２）が、前記部分レジスタの内容を比較して、その比較 結果をアクセスと呼ばれる外部バス内のワイヤに供給するように、接続されてい ることを特徴とする、請求項４３記載の演算装置。
50. ５０．前記比較器が、 ａ）第１ＮＡＮＤゲートであって、その第１入力が前記第１バッファ手段（Ｑ１ ）の前記内部レジスタスイッチと反対の側に接続され、第２入力が該内部レジス タスイッチと前記第２バッファ手段（Ｑ２）との間の接続点に接続されている前 記第１ＮＡＮＤゲートと、ｂ）第２ＮＡＮＤゲートであって、その第１入力が前 記第２バッファ手段（Ｑ２）の前記内部レジスタスイッチと反対の側に接続され 、第２入力が該内部レジスタスイッチと前記第１バッファ手段（Ｑ１）との間の 接続点に接続されている前記第２ＮＡＮＤゲートと、を含み、前記両ＮＡＮＤゲ ートの出力が相互接続され、かつ前記アクセスと呼ばれるバス内の前記外部バス ワイヤに接続されていることを特徴とする、請求項４９記載の演算装置。
51. ５１．それぞれの前記ＮＡＮＤゲートが、直列接続されたソース／ドレイン路を 有する２つの直列接続されたＭＯＳ−ＦＥＴトランジスタを含み、それらのゲー トが前記ＮＡＮＤゲートの入力であり、最上部の該ＭＯＳ−ＦＥＴトランジスタ のドレインが前記外部バスのワイヤヘの出力であることを特徴とする、請求項５ ０記載の演算装置。
52. ５２．前記レジスタのマトリックスが、前記ベースレジスタ内に置かれたデータ オブジェクトの構造リダクションを行なうために、前記制御手段により自動的に 制御されるように配設されていることを特徴とする、請求項３０記載の演算装置 。
53. ５３．２レベル構造 （ｍａｐ，ｆ，（ｅ１，・・ｅｎ）） において、命令ｍａｐは前記補助レジスタ（Ｆ０からＦ３まで）の１つに書込ま れており、マッピングするためのファンクションは第２の該補助レジスタに書込 まれており、命令エレメントｅ１のリストは前記ベースレジスタ（Ｓ０．０から Ｓ２．２まで）に書込まれている前記２レベル構造を有する命令ｍａｐが、前記 ベースレジスタのそれぞれの列において、前記ファンクションが該列内の最下部 のベースレジスタ内に配置され、前記命令エレメントの１つが該列内の第２最下 部ベースレジスタ内に配置されるように、前記ファンクションが同報通信され且 つ前記命令エレメントが再配置された （（ｆ，ｅ１），・・・（ｆ，ｅｎ））に、前記制御手段からの制御によって書 直されるように、マッピング命令が実行されることを特徴とする、請求項５２記 載の演算装置。
54. ５４．３レベル構造 （ｔｒａｎｓｐｏｓｅ， （（ｅ１，１，・・ｅ１，ｍ）， ・・・ （ｅｎ，１，・・ｅｎ，ｍ））） において、命令ｔｒａｎｓｐｏｓｅは前記補助レジスタ内に書込まれており、命 令エレメントｅｉ，ｊ（ｉおよびｊは、前記マトリックス内における該命令エレ メントの位置の表示である）の諸リストのリストは、ベースレジスタ複合体がエ レメントの正方形を含むように、ベースレジスタの前記マトリックス内に書込ま れている前記３レベル構造を有する命令ｔｒａｎｓｐｏｓｅが、前記補助レジス タの値は空にされており、ベースレジスタの前記マトリックス内の前記情報エレ メントは、該マトリックスの対角線に関し鏡映位置に配置されるようにトランス ポーズ▽されている （（ｅ１，１，・・ｅｎ，１）， ・・ （ｅ１，ｍ，・・ｅｎ，ｍ））） に、前記制御手段からの制御によって書直されるように、ｔｒａｎｓｐｏｓｅ命 令が実行されることを特徴とする、請求項５３記載の演算装置。
55. ５５．３レベル構造 （ｓｗａｐ　ｍ（（ｅ１，１，・・），・・ （ｅｍ，１，・・）， （ｅｍ＋１，１，・・）， ・・・ （ｅｎ，１，・・））） において、命令エレメントｅｉ，ｊ（ｉおよびｊは、ベースレジスタの前記マト リックス内における該命令エレメントの位置の表示である）の諸リストのリスト は、ベースレジスタ複合体がエレメントの正方形を含むようにされている、前記 ３レベル構造を有する命令ｓｗａｐが、エレメント（ｅｍ．１、・・・）とエレ メント（ｅｍ＋１．ｊ、）との位置の入れ換った （（ｅ１，１，・・）， ・・ （ｅｍ＋１，・・）， （ｅｍ，１，・・）， ・・・ （ｅｎ，１，・・）） に、前記制御手段からの制御よにって書直されるように、ｓｗａｐ命令が実行さ れることを特徴とする、請求項５２記載の演算装置。
56. ５６．３レベル構造 （ｓｋｉｐ　ｍ（（ｅ１，１，・・），・・ （ｅｍ−１，１，・・）， （ｅｍ，１，１・・）， （ｅｍ＋１，１，・・）， ・・・ （ｅｎ，１，・・）） において、命令エレメントｅｉ，ｊ（ｉおよびｊは、ベースレジスタの前記マト リックス内における該命令エレメントの位置の表示である）の諸リストのリスト は、ベースレジスタ複合体がエレメントの正方形を含むようにされている、前記 ３レベル構造を有する命令ｓｋｉｐが、エレメント（ｅｍ．１、・・・）の削除 された（（ｅ１，１，・・）， ・・ （ｅｍ−１，・・）， （ｅｍ＋１，・・）， ・・・ （ｅｎ，１，・・）） に、前記制御手段からの制御によって書直されるように、ｓｋｉｐ命令が実行さ れることを特徴とする、請求項５２記載の演算装置。
57. ５７．中央処理装置の一部分であることを特徴とする、請求項２２記載の演算装 置。