(57)【特許請求の範囲】
【請求項１】
複数のセルを配列し、前記セルにその近傍のセルの状態を表す信号を入力信号として入力できるようにセル間を相互結合したセルラオートマトンであって、
前記セルラオートマトンにおける状態を表す信号を伝播する信号伝播路と、
前記信号伝播路と連結される演算手段と、
前記演算手段を演算手段として機能させるための演算規則を前記セルラオートマトンに参照させる状態導出手段を有し、
前記演算規則により、
前記演算手段を、２つの入力信号伝播路と１ つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に２つの出力信号を出力するように機能させる第１ の演算手段と、
前記演算手段を、３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２ の演算手段と、
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段と、
前記演算手段を、２つの入出力信号伝播路に連結された演算手段であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算手段を１の状態とし、残りの入出力信号伝播路の状態を出力せずに１から０に戻し、演算手段が１の状態のときにひとつの入出力信号伝播路から演算手段に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算手段が０の状態のときにひとつの入出力信号伝播路から演算手段に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算手段へ入力されたときは、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段と、前記演算手段を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５の演算手段と、
からなる演算手段群のいずれかとして機能させるセルラオートマトン。
【請求項２】
前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、
初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算手段を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算手段が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算手段の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる請求項１に記載のセルラオートマトン。
【請求項３】
複数のセルを配列し、前記セルにその近傍のセルの状態を表す信号を入力信号として入力できるようにセル間を相互結合したセルラオートマトンであって、
前記セルラオートマトンにおける状態を表す信号が伝播するセル列が信号伝播路として形成され、
前記信号伝播路同士の衝突するセルが演算部として形成され、
前記演算部を演算部として機能させるための演算規則を前記セルラオートマトンに参照させる状態導出手段を有し、
前記演算規則が、
前記演算部を、２つの入力信号伝播路と１ つ出力信号伝播路とに接続された演算部であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算部に入力信号が同時に入力された場合に、前記出力信号伝播路に２つの出力信号を出力するように機能させる第１ のモジュールと、
前記演算部を、３つの入出力信号伝播路とに接続された演算部であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算部に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２のモジュールと、
前記演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算部であって、前記入力信号伝播路から入力信号が演算部に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算部に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３のモジュールと、
前記演算部を、２つの入出力信号伝播路に連結された演算部であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算部を１の状態とし、残りの入出力信号伝播路の状態を出力せずに１から０に戻し、演算部が１の状態のときにひとつの入出力信号伝播路から演算部に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算部が０の状態のときにひとつの入出力信号伝播路から演算部に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算部へ入力されたときは、どちらかの入力信号が演算部に先に入力され、残りの入力信号が送れて演算部に入力されたように調整するように機能させる第４のモジュールと、
前記演算部を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算部であって、前記入力信号伝播路から演算部に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５のモジュールと、
からなるモジュール群のいずれかとして機能させるセルラオートマトン。
【請求項４】
前記第４のモジュールの代りに、又は前記第４のモジュールとともに
前記演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、
初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算部を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算部が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算部が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算部の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算部へ入力された場合は、どちらかの入力信号が演算部に先に入力され、残りの入力信号が遅れて演算部に入力されたように調整するように機能させるモジュールを用いる請求項３に記載のセルラオートマトン。
【請求項５】
請求項１〜４のいずれかに記載のセルラオートマトンを用いた非同期回路の設計方法。
【請求項６】
請求項１〜４のいずれかに記載のセルラオートマトンを用いた非同期回路を含むコンピュータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、新規な基本モジュールを利用したセルラオートマトン、そのオートマトンを利用した非同期回路の製造方法、およびコンピュータなどに関する。
【０００２】
【従来の技術】
オートマトンは、例えば、コンピュータなどの基本回路を設計する際などに用いられる。例えば、オートマトンを用いた情報検索回路が知られている（例えば、特許文献１参照。）。
【０００３】
また特セルオートマトンを用いたデータ記録システム及び伝送システムが知られている（例えば、特許文献２参照。）。また、ニューロセルラオートマトンおよび最適化装置が知られている（例えば、特許文献３参照。）。このように、オートマトン、およびセルラオートマトンは、コンピュータシステムの設計などに利用されてきた。
【０００４】
セルラオートマトンは、von Neumann（ノイマン）がその概念を提唱したものである。１９８６年にWolframが物理的考察を行い、物理系への応用がなされるようになった。セルラオートマトンの具体的な手続は、以下の通りである。
すなわち、「解析対象をセルと呼ばれる領域で定義する。各々のセルの状態を物理的な意味をもっている離散量で定義する。状態を時間発展させてそれぞれの時間における状態量を順じ求める。」というものである。
【０００５】
なお、Ｋｅｌｌｅｒ（ケラー）は、ケラー氏の条件のもとで、全ての耐遅延回路（非同期回路）を設計することができる基本モジュールの群を提案した。後にＰａｔｒａ（パトラ）は、基本モジュール群[ＭＥＲＧＥ、ＦＯＲＫ、ＴＲＩＡ、ＳＥＱＵＥＮＣＥＲ]を提案した。この基本モジュール群を用いれば、演算回路などに必要とされる全ての非同期回路を設計することができる。また、この基本モジュール群は、ケラー氏が提案した全ての条件を満足する。以下、モジュールＭＥＲＧＥ、ＦＯＲＫ、ＴＲＩＡ、ＳＥＱＵＥＮＣＥＲの作用を説明する。
【０００６】
図２に、ＭＥＲＧＥを示す。
ＭＥＲＧＥによれば、入力ラインＩ1（Ｉ2）からの信号は、同期されてＯとして出力される。ただし、Ｉ1とＩ2が、同時に入力されることは禁止される。
【０００７】
図３に、ＦＯＲＫを示す。
ＦＯＲＫは、演算部を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算部であって、前記入力信号伝播路から演算部に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させるモジュールであり、演算手段を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる演算手段として機能する。（本発明のセルラオートマトンにおいては、第５の演算手段として機能する。）
【０００８】
ＦＯＲＫによれば、入力ラインＩからの信号は、同期されて、出力ラインＯ1とＯ2からの出力信号として出力される。
【０００９】
図４に、ＴＲＩＡを示す。
ＴＲＩＡによれば、入力ラインＩ1（Ｉ2）＜Ｉ3＞とＩ2（Ｉ3）＜Ｉ1＞からの信号は、同期されてＯ3（Ｏ1）＜Ｏ2＞として出力される。Ｉ1、Ｉ2、Ｉ3が、同時に入力されることは禁止される。入力ラインのひとつが受領状態（信号を受け取った状態）になるまで、他の入力ラインは待ち状態に維持される。
【００１０】
図５に、ＳＥＱＵＥＮＣＥＲを示す。
ＳＥＱＵＥＮＣＥＲは以下のように作用する。信号ｃと、入力ラインａi（ｂi）からの信号が入力されて、信号ａo（ｂo）として出力される。入力ラインａi（ｂi）に、同時に信号が入力された場合は、任意に選ばれた信号ａo（ｂo）が、信号ｃとともに出力ラインに出力され、残ったラインｂo（ａo）上の信号は、次の信号が入力されるまで待ちつづける。
【００１１】
【特許文献１】
特許第２６９６８３２号公報
【特許文献２】
特許第３１４６３５５号公報
【特許文献３】
特許第３０６９０５８号公報
【００１２】
【発明が解決しようとする課題】
パトラ氏による基本モジュール群のそれぞれのモジュールは、入力、出力、入出力の信号伝播路を数多く（例えば、５〜６個）必要とするものであり、より簡便な基本モジュール群を用いたセルオートマトンが望まれている。
【００１３】
【課題を解決するための手段】
本発明では、入力ライン、出力ライン、入・出力ラインからなるライン（信号伝播路ともいう。）のうち多くても３つのを有する新規基本モジュール群を用いたセルオートマトンを提供する。本発明は、公知の基本モジュールＦＯＲＫに、新たな基本モジュールを加えた新たな基本モジュール群[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]を加えたセルオートマトンを提供するものである。そして、これら基本モジュールの組は、耐遅延（Delay Insensitive）回路において汎用性がある。すなわち、これらの基本モジュール群を用いることで、全ての非同期回路を設計することができる（例えば、図１参照）。
【００１４】
すなわち、上記の課題は以下の発明によって解決される。
(1)複数のセルを配列し、前記セルにその近傍のセルの状態を表す信号を入力信号として入力できるようにセル間を相互結合したセルラオートマトンであって、前記セルラオートマトンにおける状態を表す信号が伝播するセル列が信号伝播路として形成され、
前記信号伝播路同士の衝突するセルが演算部として形成され、
前記演算部を演算部として機能させるための演算規則を前記セルラオートマトンに参照させる状態導出手段を有し、
前記演算部が、入力信号伝播路、出力信号伝播路、入出力信号伝播路から選ばれる３本以下の信号伝播路と連結されているセルラオートマトン。
(2)複数のセルを配列し、前記セルにその近傍のセルの状態を表す信号を入力信号として入力できるようにセル間を相互結合したセルラオートマトンであって、
前記セルラオートマトンにおける状態を表す信号を伝播する信号伝播路と、
前記信号伝播路と連結される演算手段と、
前記演算手段を演算手段として機能させるための演算規則を前記セルラオートマトンに参照させる状態導出手段を有し、
前記演算規則により、
前記演算手段を、２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に２つの出力信号を出力するように機能させる第１の演算手段と、
前記演算手段を、３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２の演算手段と、
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段と、
前記演算手段を、２つの入出力信号伝播路に連結された演算手段であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算手段を１の状態とし、残りの入出力信号伝播路の状態を出力せずに１から０に戻し、演算手段が１の状態のときにひとつの入出力信号伝播路から演算手段に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算手段が０の状態のときにひとつの入出力信号伝播路から演算手段に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算手段へ入力されたときは、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段と、
前記演算手段を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５の演算手段と、
からなる演算手段群のいずれかとして機能させるセルラオートマトン。
(3)前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、
初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算手段を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算手段が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算手段の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる上記(2)に記載のセルラオートマトン。
(4)複数のセルを配列し、前記セルにその近傍のセルの状態を表す信号を入力信号として入力できるようにセル間を相互結合したセルラオートマトンであって、前記セルラオートマトンにおける状態を表す信号が伝播するセル列が信号伝播路として形成され、
前記信号伝播路同士の衝突するセルが演算部として形成され、
前記演算部を演算部として機能させるための演算規則を前記セルラオートマトンに参照させる状態導出手段を有し、
前記演算規則が、
前記演算部を、２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算部であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算部に入力信号が同時に入力された場合に、前記出力信号伝播路に２つの出力信号を出力するように機能させる第１のモジュールと、
前記演算部を、３つの入出力信号伝播路とに接続された演算部であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算部に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２のモジュールと、
前記演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算部であって、前記入力信号伝播路から入力信号が演算部に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算部に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３のモジュールと、
前記演算部を、２つの入出力信号伝播路に連結された演算部であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算部を１の状態とし、残りの入出力信号伝播路の状態を出力せずに１から０に戻し、演算部が１の状態のときにひとつの入出力信号伝播路から演算部に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算部が０の状態のときにひとつの入出力信号伝播路から演算部に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算部へ入力されたときは、どちらかの入力信号が演算部に先に入力され、残りの入力信号が送れて演算部に入力されたように調整するように機能させる第４のモジュールと、
前記演算部を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算部であって、前記入力信号伝播路から演算部に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５のモジュールと、
からなるモジュール群のいずれかとして機能させるセルラオートマトン。
(5)前記第４のモジュールの代りに、又は前記第４のモジュールとともに
前記演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、
初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算部を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算部が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算部が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算部の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算部へ入力された場合は、どちらかの入力信号が演算部に先に入力され、残りの入力信号が遅れて演算部に入力されたように調整するように機能させるモジュールを用いる請求項４に記載のセルラオートマトン。
(6)上記(1)〜(5)のいずれかに記載のセルラオートマトンを用いた非同期回路の設計方法。
(7)上記(1)〜(5)のいずれかに記載のセルラオートマトンを用いた非同期回路を含むコンピュータ。
【００１５】
パトラ氏とケラーによる基本モジュール群と異なり、ラインは、双方向（ｂｉ−ｄｉｒｅｃｔｉｏｎａｌ）であってもよく、ラインは、バッファーとして機能しても良い。ここで、双方向とは、ひとつのラインがモジュールへの入力ラインとして機能しても、出力ラインとして機能しても良いことを意味する。すなわち、セルラオートマトン上では、信号伝播路が、入力信号伝播路または出力信号伝播路だけではなく、入出力信号伝播路として機能しても良い。
【００１６】
【発明の実施の形態】
本発明は、少なくとも[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]を演算規則とする演算部を有するセルラオートマトンなどに関する。セルラオ−トマンの概念はJ.von Neumann（ノイマン） によって提案され（J.von Neumann:"Thery of self-reproducing automata",Univ.of Illinoise Press,1996.）、その後多くの研究者により詳細に研究された（例えば、S.Wolfram:Physica 10D,pp.1-35,1984、相沢洋二、永井喜則：物性研究 48 No.4,pp.316-320,1987など）。セルラオ−トマン法を使用することにより、単純な条件を用いて、例えば、カオス状態などの複雑な事象、生物や生体に類似する複雑なパターン等を導くことが可能である。
【００１７】
なお、オートマトンに関する一般的な用語については、例えば、飯島泰蔵編集森北出版株式会社発行  基礎情報工学シリーズ５  オートマトン・言語理論などに記載されている。
【００１８】
本発明におけるセルとしては、例えば、状態を保持する状態記憶手段を持つセルであって、セルが多数個格子状に配列され、各々のセルは状態記憶手段に保持されている現在の自己のセルの状態と、その近傍のセルの状態をもとに次の状態を更新しかつすべてのセルの状態を同期して更新させる状態更新手段を備えているものが挙げられる。特に、演算部（演算手段・モジュール）を演算部として機能させるための演算規則を参照させ、信号伝播路（ライン・パス）からの入力信号とあわせて信号の状態を導出する状態導出手段を有するものが挙げられる。
本発明におけるセルラオートマトンの基本概念としては、例えば、特許第３１４６３５５号、特許第３０６９０５８号公報に記載されているものが挙げられる。セルは、例えば、ライン（信号伝播路）とモジュール（演算部）を含み、これらが、ネットワークとして構成されてもよい。
【００１９】
本明細書において、信号は、ラインにおける値または状態の変化である。そして、信号はモジュールの出力ラインから、他のモジュールの入力ラインへと移動する。ある値の信号である際は、図６（ａ）のトークンのように表される。そして、あるモジュールに入力されたが、他の信号が到着するまで出力されない信号である待ち信号は、図６（ｂ）のように表される。
【００２０】
信号は、モジュール間の情報伝達に用いることができる。モジュールは、そのモジュールに連結された他のモジュールからの入力信号を受け取り、その後、その信号を処理して、時にはそのモジュールの状態を変化させて、出力ラインから出力信号を出す。モジュールの動作は、入力信号により開始されるため、セントラルクロック信号は必要とされないことが好ましい。モジュールは、記録情報と新たな入力情報との組み合わせによって次の動作が決まるような順序機械（Sequential Machine）であってもよく、その記録される情報は、有限であることが好ましい。順序機械は、Ｎ＝（Ｑ、ｑ0、Σ、Δ、ｆ、ｇ）で定義される。ここで、Ｑは、状態の有限な組み合わせであり、ｑ0は初期状態であり、Σは入力記号であり、Δは、出力記号であり、ｆは、例えばｆ：Ｑ×Σ→Ｑのような状態遷移関数であり、ｇは、ｇ：Ｑ×Σ→Δのような出力関数である。
【００２１】
以下本明細書における定義等を説明する。
定義１．耐遅延（DI）回路
耐遅延回路は特殊なクラスの非同期回路であり、その動作の正確性は、モジュールまたは相互接続ラインにおける不定遅延の影響を受けない。DI回路の動作は信号で駆動される。信号がモジュールに到達すると、そのモジュールはそれに対して働きかける。その結果、通常、その相互接続ライン上に１つ以上の出力信号を出され、その後、そのモジュールは、その次の入力信号を受信するまで待ち状態になる。
【００２２】
ＤＩ回路は、モジュール間の入出力のタイミング関係に無関係であるため、（１）低消費電力と低熱損失、（２）クロック信号分配用の配線不要、（３）高速な平均速度、（４）物理条件と実装の依存度が小さいこと、そして（５）モジュール設計技術によく適していることなど、同期タイプに比べて非同期回路の完全な利点を有している（詳細についてはHauck, S. Asynchronous design methodologies: an overview. Proc. IEEE 83(1), 69-93 (1995)、Patra, P. Approaches to design of circuits for low-power computation, Ph.D. thesis. (The university of Texas at Austin, 1995). を参照）。但し、中央クロックが無いため、ANDゲートとNOTゲートなど、論理ゲートだけを使用したDI回路の設計を不可能にする。これは、これらのゲートが論理機能だけを提供し、タイミング機能[Martin, A.J. The limitations to delay-insensitivity in asynchronous circuits. Proc. 6th MIT Conf. on Advanced Research in VLSI (MIT Press, MA: Cambridge) 263-278 (1990)、Brzozowski, J.A., Ebergen, C. On the delay-sensitivity of gate networks. IEEE Tr. Comp. 41(11), 1349-1360 (1992).
]を提供しないためである。この結果、ハードウェア（我々の場合はセルオートマトンとして構成されたハードウェア）にDI回路を実装するためには、任意のDI回路の構築に使用する基関数モジュールの集合を定義することが必要となる。
【００２３】
双方向およびバッファリングラインの使用を可能にする基関数モジュールのユニバーサル集合が提示されている（Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002).）。この集合内の基関数は、一定の時刻に、１つのラインから、それを入力ラインとして使用して入力信号を受信してもよいが、別の時刻に同一のライン上の出力信号を、それを出力ラインとして使用して生成することができる。更に、モジュール間のラインは複数の信号を含むことができ、この結果、その送付先の方へ送信される信号のバッファとして働く。明らかに、ラインを双方向にするのを許可すれば、モジュール当たりのライン数は少なくてすむ。しかも、ライン内にバッファを使用すると、信号のスループットが高まり、DI回路[Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002).の演算効率を高める。
【００２４】
定義２．１  「順序機械」は、N=(Q, q0,Σ,Δ,h,g)として定義される。但し、Qは状態の有限集合、q0は初期状態、ΣとΔはそれぞれ入力および出力記号の集合である。h:Q×Σ→Ｑは静的遷移機能、そしてg:Q×Σ→Δは出力機能である。
【００２５】
定義２．２  「モジュール」は、（I,O,T(O), N）として定義される。但し、Iは入力ラインの有限集合、Oが出力ラインの有限集合、T(O)=[[ ]M]∪[a1,・・・,an]M[a1,・・・,an ∈0,1＜ｎ＜∞]は、O1上の有限サイズ多集合の優先集合であり、そこでは、｛・・・｝Mが多集合（Bag）を示し、また、N=(Q,q0,Σ,Δ,f,g)は、ΣがIと1対1の対応関係にあり、ΔがT(O)と1対１の対応関係にある順序機械である。
【００２６】
定義２．３  モジュールM＝（I,O,T(O),N）であり、ラインa∈I∪Oであると想定する。ラインaは、a∈I∩Oの場合に限って「双方向ライン」と呼ばれ、またこれは⇔によって示される。また、ラインaは、それが一時に複数の信号をバッファリングし、バッファリングした信号をすべて、a∈Iのときには確実にMの方向へ、あるいはa∈OのときにはMに接続されたモジュールの方へ送信することができる場合のみ「バッファリングライン」と呼ばれる。ラインのバッファは、通常、有限容量を有する。
【００２７】
定義２．４  「信号」とは、ラインの状態または値の変化であり、モジュールの出力から他のモジュールの入力へライン上を転送される。１つの値である信号は、図６（a）に示すようにライン上のトークンによって示される。「待ち状態の信号」は、モジュールのラインから到着した入力信号であるが、他の入力信号が異なるラインから到着しない限り、モジュールの出力を生じない。待ち状態の信号は、図６（ｂ）のように示される。
【００２８】
定義２．５  「ネットワーク」は、相互接続されたいくつかのラインを有するモジュールが集まったものである。未接続の端部を有するラインは、ネットワークの入力または出力ラインである。
【００２９】
本明細書で使用される耐遅延（ＤＩ）モジュールのクラスは、［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002)、 Keller, R.M. Towards a theory of universal speed-independent modules. IEEE Tr. Comp. C-23(1), 21-33 (1974).］に基づいた以下の動作条件を満足するすべてのモジュールで構成されることが好ましい。
【００３０】
−条件１：  ラインは、その端部に多くて２台のモジュールを接続することが許可されるのみである。また、ラインとは、モジュール１台だけへの入力であり、所定時刻におけるモジュール１台だけへの出力である。
【００３１】
−条件２：  モジュールが一旦信号を出力すると、そのラインからその信号を引き込めることは不可能である。
【００３２】
−条件３：  ライン上の信号は最終的にはその仕向先のモジュールによって吸収される必要がある。それにより、信号は到着前に不定遅延を被る場合がある。
【００３３】
−条件４：  ２つの入力信号がモジュールの異なるラインに同時に到着すると、あたかも１つの信号のように、動作がモジュールによって任意に選択され、次に他の動作がモジュールが指定した順序で現れる場合がある。これは、「アービトレーション」条件と呼ばれる。
【００３４】
−条件５：  モジュールは、入力信号の同化と対応出力信号の生成との間の不定（しかし有限の）遅延を受ける場合がある。
【００３５】
−条件６：  ラインへの信号の出力は、対応バッファが満杯の場合には遅延を生じる。
【００３６】
−条件７：  いかなるモジュールも、同一ライン上の全入力信号を吸収してからでなければ双方向ライン上に信号を出力できない。
【００３７】
−条件８：  所定時刻にライン上に存在するすべての信号は、同一方向に動く。
【００３８】
定義２．６  モジュールのネットワークは、モジュールまたは相互接続ラインの不定の（しかし有限の）遅延にかかわらず、その外部論理機能が変更を受けない場合に「耐遅延」（DI）である。
【００３９】
定義２．７  モジュールは、そのいずれかの入力ライン上のすべての信号の後にそのいずれかの出力ライン上のきっかり１つの信号が続いていなければ次の入力信号がモジュールに吸収されない場合には、「シリアル」である。
【００４０】
定義２．８  モジュールは、入力信号が必ずしも１つの出力信号によって区切られることなく複数の入力信号を許可するか、あるいは出力信号が必ずしも１つの入力信号で区切られることなく複数の信号を出力できる場合には、「パラレル」である。
【００４１】
定義２．９  モジュールのネットワークは、十分長い間ネットワークへの全入力ライン上に信号がないことが、最終的にネットワーク内に信号が残っていないかまたはネットワーク内に残っているすべての信号が待ち状態になるか、そのいずれかを意味する場合は常に、ウイズアウトビジーウエイティング（without busy waiting）である。
【００４２】
without busy waitingであることの実際的な重要性は、この条件が、入力信号がないときにネットワークがいつまでも交換に係わる必要はなく、その結果ネットワークの電力消費を最小限にすることを保証することである。
【００４３】
定義２．１０  基関数モジュールの集合は、ＤＩモジュールクラス用の「without-busy-waitingユニバーサル」（または「ユニバーサル」と略す）と呼ばれる。但し、これは当該クラス内の各モジュールがこの集合の基関数のwithout-busy-waitingネットワークによって実現可能な場合である。
【００４４】
定理２．１  ［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002).］｛ＭＥＲＧＥ，  ＦＯＲＫ，  ＩＯＭ，  Ｓ−ＪＯＩＮ，  ＡＴＳ｝は、ＤＩモジュールクラス用のwithout-busy-waitingユニバーサルである。
【００４５】
定理２．２  ［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002).］  ｛ＭＥＲＧＥ，  ＦＯＲＫ，  ＩＯＭ，  Ｓ−ＪＯＩＮ｝は計算が万能である。
【００４６】
図７に、セルオートマトンにその初期構成を埋め込んだ基関数耐遅延モジュールを示す。［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002).］内のＰａｒａｌｌｅｌ  ＭＥＲＧＥモジュールはここでは簡潔にするためＭＥＲＧＥと呼ぶ。
【００４７】
図７において、ＭＥＲＧＥでは、入力ラインＩ1またはＩ2上の信号が出力ラインＯに転送される。
【００４８】
図７において、ＦＯＲＫでは、入力ラインＩ上の信号は出力ラインＯ1およびＯ2上に示される。
【００４９】
図７において、ＩＯＭ（入力／出力マルチプレクサ）では、入力ラインａ上の信号がｂに出力される。ラインｂからモジュールへの信号がｃに出力される。
【００５０】
図７において、Ｓ−ＪＯＩＮ  （Ｓｙｍｍｅｔｒｉｃ  ＪＯＩＮ）では、２本のラインａ（ｂ）［ｃ］とｂ（ｃ）［ａ］からモジュールへの入力信号が同化されて、１つの信号が残りのラインｃ（ａ）［ｂ］へ出力される。モジュールへのラインのうちの１本からの信号が、他のいずれかのラインから信号が到着するまで待ち状態となる。
【００５１】
図７において、ＡＴＳ  （Ａｒｂｉｔｒａｔｉｎｇ  Ｔｅｓｔ  ＆  Ｓｅｔ）について、ＡＴＳには０と１の２つの状態がある。入力ラインＴ上の信号は常に状態を１に設定し、入力ラインＲ上の信号は状態を常に０にリセットするが信号を出力しない。Ｔ上の信号は、モジュールが状態１（０）のときに出力ラインＴ1（Ｔ0）に転送される。ＴとＲ両方の２つの同時信号は、１つの信号が最初に入力され、次にもう１つというように、アービトレーションされる。なお、各演算手段（モジュール）をセルラオートマトン上で表現した例が図７の右欄である。図７の右欄においては、信号が伝播する様子をセルの色や数字を用いて表現している。
【００５２】
（非同期セルオートマトン）
均一に配置・接続されたセルのｄ次元配列（ｄ＞１）からセルオートマトン（ＣＡ）が構成される。有限数のセルの近隣に接続され、また有限状態集合の中のいずれかの状態を有する各セルは、遷移則に基づく状態遷移を受ける。これは、その隣接する各セルの状態があるときに、セルの状態が遷移によりどのように変化するのかを決定する部分関数である。通常は、休止状態と呼ばれる特殊な状態がある。セルは、そのすべての隣接セルが休止状態にあるかぎりこの状態にある。
【００５３】
最も一般的なＣＡでは、すべてのセルが中央クロックに従って、同時に状態遷移を受けるので、これらは同期ＣＡと呼ばれる。所定の時刻における全セルの状態は遷移関数によりそれら自身の状態と、直前の時刻におけるその近隣のセルの状態から決定されるため、セル空間全体がその構成を確定的に進化させる。非同期セルオートマトン（ＡＣＡ）では、すべてのセルが、他のセルの遷移のタイミングからは独立して任意の時間に状態遷移を受けることができ、その結果、セル空間全体に中央クロック信号を分配する必要がない。但し、中央クロック信号がないことから、ＡＣＡ内の演算は非確定的になる場合がある。つまり、一定の構成から複数のグローバル構成が進化する場合がある。
【００５４】
本明細書は、二次元配列のセルで構成されたＣＡモデルをも想定しており、この場合各セルはそれ自身に沿って４個の直交隣接セルで構成された隣接（いわゆるフォンノイマン近傍）を有する。図８（ａ）に示されているフォンノイマン近傍を有するＣＡは以下に正式に定義される。
【００５５】
定義３．１  「フォンノイマン・近隣を有する確定的な二次元セルオートマトン（CA）」は、Ａ＝（Ｚ2，Ｖ，ｆ，ｖ0）と定義される。但し、Ｚはすべての整数の集合であり、Ｖはセル当たりの状態の有限集合（Ｖ≠φ）である。マッピングｆ：Ｖ5→Ｖは「局所関数」と呼ばれ、これは５個の隣接セル（つまり、中央、上方、右側、下方、および左側のセル）の現在の状態によって、セルの状態遷移を決定する。このため、遷移則ｆ（ｃ，ｕ，ｒ，ｄ，ｌ）＝ｃ’は図８（ｂ）（フォンノイマン・近隣を有する二次元セル空間を示す。）のように描写できる。
【００５６】
状態v0（∈Ｖ）は、f(v0,v0,v0,v0,v0)= v0。V上の構成はマッピングc: Z2→Vであり、これはA内の各セルにVからの一定の状態を割り当てる。
【００５７】
定義３．２  Ａ＝(Ｚ2,V,f,ｖ0)を、フォンノイマン・近隣を有するCAであるとする。
【００５８】
（i）Ａにおける遷移則は以下の場合にかぎり「回転対称」である。
∀(c,u,r,d,l)∈Ｖ1 f(c,u,r,d,l)=f(c,l,u,r,d)
【００５９】
（ii）Ａにおける遷移則は以下の場合にかぎり「反射対称」である。
∀(c,u,r,d,l)∈V1 f(c,u,r,d,l)=f(c,u,l,d,r)∧f(c,u,r,d,l)=f(c,d,r,u,l)
【００６０】
明らかに、回転対称条件および反射対称条件は、等方性セル空間を指定する。ACA[1 K. Nakamura, “Asynchronous cellular automata and their computational ability”,Systems, Computers, Controls, vol. 5, no. 5, pp. 58〜66, 1974.]の各構成の遷移に関する以下の定義に従って、ACA内の各セルは他のセルとは無関係に無作為の時刻にその状態を更新することができる。
【００６１】
定義３．３  Ａ＝(Ｚ2,Ｖ,f,ｖ0)をフォンノイマン・近隣を有するＣＡであるとする。Conf(V)はV上のすべての構成の集合、つまりConf(V)=[c|c:Z2→V]を示す。
【００６２】
（i）Ａが同期ＣＡである場合には、次のように定義される関数F:Conf(V)→Conf(V)はＡのグローバル関数と呼ばれる。
∀（x,y）∈Z2,F(c)(x,y)=f(c(x,y),c(x,y+1),c(x+1,y),c(x,y-1),c(x-1,y))
（ii）Aが非同期CAの場合には、どのci,cj∈Conf(V)についても、
∀(x,y)∈Z2,ci(x,y)=cj(x,y)∨
cj(x,y)=f(ci(x,y),ci(x,y+1),ci(x+1,y), ci(x,y-1),ci(x-1,y))
となるよう、ci→cjと書かれるciからcjへの遷移が存在する。いかなるca,ct∈Conf(V)についても、我々はcs+/→Ct iff cs→ciまたは∋c's∈Conf(V),cs→c'n+/→ctと示す。
【００６３】
次の定理は、いかなる同期ＣＡも、セル当たりの状態数の増加を犠牲にして、等価のＡＣＡによってシミュレーションできることを述べている。
【００６４】
定理３．１  セル当たりｍ状態を有するｄ次元の同期セルオートマトンと対称近傍（例：フォンノイマン・近隣）の場合には、同一近隣およびＡと等価のセル当たり３ｍ2状態を有するｄ次元の非同期セルオートマトンが存在する［K. Nakamura, “Asynchronous cellular automata and their computational ability”,Systems, Computers, Controls, vol. 5, no. 5, pp. 58〜66, 1974.］。
【００６５】
（非同期セルオートマトン上での信号および回路基関数の実装）
以下、セル間の相互作用を説明するために回転および反射対称の遷移則を使用して、フォンノイマン・近隣を有する新奇な５状態ＡＣＡを提示し、ＡＣＡにＤＩ回路を埋め込んで演算の万能性を達成する。Ａ５（Ａ5）と呼ばれるこのＡＣＡモデルは、Ａ５＝（Ｚ2，｛０，１，２，３，４｝，ｆ５，０）と定義される。便宜上、状態０，１，２，３または４でセルを表すような構成で使用する。遷移則が表現されていない状態の組合せは、些細な遷移、つまりセルの状態を変化させない遷移を生じると考えられる。以下０、１、２、３、４をセル中の濃さで表現することもある。
【００６６】
図９に１つの信号を示す。これは、この信号のコアである状態２のセル１個で構成され、状態１のセル３個によって取り囲まれている。この状態１のセル３個は、休止セルがコア・セルに隣接する方向へこの信号を導くためにシールドとして機能する。
【００６７】
（信号を表現する構成）
Ａ5では、ラインが、セル２個以上の長さを有する、モジュール間の休止セルの直線経路として実装される。図３の構成を採用して休止セルの経路上に信号を表現する（[J. Lee, F. Peper, S. Adachi and K. Morita, “Crossing signals in asynchronous cellularautomata”, Proc. LA Symp. ’01 Winter, Kyoto, pp. 31.1〜31.4, 2002. (in Japanese)]も参照）。
【００６８】
Ａ5内の信号送信のための遷移則は表１に示され、その回転対称および反射対称等価物は除外されている。Ａ5に埋め込まれた回路は、信号交差上での衝突が絶対に起こらないよう設計できるため、我々はより少ない数の状態と遷移則で［J. Lee, F. Peper, S. Adachi and K. Morita, “Crossing signals in asynchronous cellularautomata”, Proc. LA Symp. ’01 Winter, Kyoto, pp. 31.1〜31.4, 2002. (in Japanese)］内の信号を送信できる。表１に信号の送信に必要な遷移則を示す。
【００６９】
【表１】
0003718716.tif 000002
【００７０】
Ａ5内の経路に信号を送信するプロセスは、次のように要約できる。
（確認段階）
状態２のセルに隣接する休止セルは、遷移則１に従って、図１０（ｉｉ）に示すように状態３に更新され、このため信号のコアをセル１個分延長するのが安全であることを確認する。
【００７１】
（遮蔽段階）
休止セルは、条件２に従って、図１０（ｉｉｉ）に示すように状態１に更新され、その結果、次の段階で所定方向に信号のコアを強制する。ＣＡは非同期であるため、この条件が適用される２つのセルは、必ずしも同時に更新されない。
【００７２】
図１０に経路上への信号の送信を示す。各矢印の上の整数は、構成内のセルの状態を変更するのに使用される表2の遷移則（またはその回転対称および反射対称等価物）を示す。
【００７３】
（拡張段階）
状態３のセルが、条件１２に従って、図１０（iv）のように状態2に更新され、その結果信号のコアを1セル延長する。
【００７４】
（離脱段階）
状態2のセルが、条件9〜11に従って、図１０（v）のように状態1に更新され、その結果、その信号の後に離脱を引き起こす。
【００７５】
（クリーニング段階）
状態1のセルは、条件3〜7に従って、図１０（vi）のように休止にされ、その結果、その信号の背後にあるごみをクリーニングする。
【００７６】
Ａ5の経路を転送される信号は次の特性を保持する。
特性１
−自律的である。経路上での信号の送信は、その局所構成内のセル間の相互作用にのみ依存する。送信プロセス中にセルを同期化するのに必要なタイミング機構がない。セルの状態遷移のタイミングが無作為に取られるため、経路上をモジュール間で転送される信号が不定（であるが有限の）遅延を受けるかもしれない。
【００７７】
特性２
−構成の形状が柔軟である。セルの状態遷移のタイミングが無作為に取られるため、信号は、特に、最終的に洗浄されるたくさんのごみがそれらに付着していることが多いそのテールにおいて、様々な形状を取ることができる（図１１を参照）。この種類の多さは、離脱またはクリーニング段階が他の段階と同時に起こる可能性があるためである。また、信号のヘッドは、確認、遮蔽、および拡張の各段階の順序が厳格であるため常に明確に区別できるが、信号のヘッドの形状に関してはある程度の多様性がある（がそれほど多くはない）。その豊富な多様性にもかかわらず、すべての信号形状は、図９の基本構成に由来する。
【００７８】
特性３
−信頼性がある。信号は消滅することも、進路を変えることも、経路上を送信時にそれ自身で複数の信号を生成することも、あるいは複数の信号に分かれることもない。モジュールによって経路上で生成されたら、最終的にその出力先に到達する。
【００７９】
図１２に、ＦＩＦＯバッファリングラインを表す信号で満たされたセルの経路を示す。図１３に、ごみを含むテールを有する信号は、そのごみが除去されるまで後続の信号を妨げるが、その継承者が最終的にその目的地に到達するのを阻止できないことを示す。
双方向およびバッファ経路は、上記の構成によって直線的に実装される。経路の双方向性はＡ5の遷移則の対称性から得られる。各経路のバッファリングは遷移則の設計から得られ、これは、複数の信号が、FIFO式の（図１２参照）経路に沿った同時送信を可能にする。信号の状態2のコアセルのすぐ前の休止セルが、他の信号に隣接していない場合に遷移則に従って非休止セルにのみ変化できるため、経路上の２つの後続信号は、第一の信号がごみを含む長いテールを有するときでも常に区切られた状態を維持する（図１３参照）。信号は同じ経路上を後続する信号に対して不定遅延を引き起こす可能性があるが、これは後者が最終的にその宛先に到達することを阻止できない。
【００８０】
（基関数モジュールを表現する構成）
次に、基関数モジュールの基本構成と入力信号に対するその働きを検討する。信号はＡ5で不定遅延を受ける可能性があるため、セル空間に構築される各基関数は、セクション２のＤＩモジュール上での動作条件を満足する必要がある。これらの基関数は、次の原理に従うなどのために構築される。
【００８１】
（１）Ａ5の各基関数モジュールの初期構成。十分長い間入力信号のないと、すべてのモジュールは最終的にその初期構成へ立ち戻る。
【００８２】
（２）基関数が信号を表す様々な構成を処理できるようにするため、信号ヘッドがそれらの信号を受け入れる前に標準形態になるのを待つ。換言すれば、信号のヘッドは、信号が状態２の正規コアを持った後にのみモジュールを入れることができる。信号のテールは、モジュールの対応ポートのちょうど外側で、状態１のセル１個に減り、その信号が当該モジュールによって処理されるまでそこに残る。
【００８３】
（３）経路上に待ち状態の信号を持つ基関数モジュールの構成は、その他の経路から到着する入力信号がないと、最終的には静的になる。
【００８４】
（４）１つの基関数は、まだ待ち状態の信号以外の先行入力信号を処理した後の残骸がすべてモジュールから除去されると、処理対象の入力信号を１つ受け入れるだけである。
【００８５】
（５）基関数モジュールは、対応する結果を出力する出力経路上に十分な空間を有するかぎり信号の処理を継続する。十分な領域がないと、処理が一時的に中断される。この状況は、直前に出力された信号がモジュールから離れず、その後続信号の出力を阻止するときに発生できる。
【００８６】
基関数モジュールとその信号の処理については、以下により詳細に説明される。
【００８７】
ＭＥＲＧＥ
ＭＥＲＧＥモジュールは、その２つの入力経路のいずれかから到着した信号をその出力経路の方へリダイレクトする。Ａ5でＭｅｒｇｅモジュールに指定された遷移則は表２に示されている。これらの条件のうちのいくつかは、他の基関数の動作にも必要である。表２に、ＭＥＲＧＥモジュールに必要な遷移則を示す。
【００８８】
【表２】
0003718716.tif 000003
【００８９】
図１４に、１つの入力信号に対して働きかけるＭＥＲＧＥを示す。入力信号を処理するＭＥＲＧＥモジュールの代表的な例は図１４に示されている。ＣＡの非同期性により、この処理が発生する形態は数多くある。
【００９０】
図１５に（ａ）左入力経路の２つの連続する信号に対して働きかけるＭＥＲＧＥを示す。図１５（ａ）は、２つの入力経路のうちの１つから到着する２つの連続信号に対して働きかけるＭＥＲＧＥを示している。これら両方の入力経路に信号が到着すると、ＭＥＲＧＥは、図１５（ｂ）に示すように、その出力経路上に２つの後続信号を生成する。２番目の図は、後続信号が吸収されず、直前の信号が出力経路に転送されてモジュール内に残されたごみを含むすべてのセルが第三の図に示すように休止状態に戻るまで、入力経路上で待機しなければならない状況を示している。（ｂ）左右の入力経路から到着する２つ信号。ＣＡの非同期生によって、各構成の複数の様々な順序が可能である。相次いでＭＥＲＧＥに入る２つの信号については、順序（ｉ），（ｉｉ）’，…，（ｖ）’が一般的であり、同時に入る信号については順序（ｉ），（ｉｉ），（ｉｉｉ），…（ｘｉｉｉ）が一般的である。但し、１つの順序は、一定の中間の時刻に他の順序に切り替わる場合がある。構成（ｉｉ）’はそのようなスプリット点である。
【００９１】
ＦＯＲＫ
図１６に、入力信号に作用するＦＯＲＫを示す。ＦＯＲＫモジュールは、その入力経路上の各信号を、図１６の２つの各出力経路上の信号へと複製する。上記の遷移則のうちのいくつかに加えて、表３の遷移則はＦＯＲＫについて要求される。表３に、ＦＯＲＫモジュールに要求される遷移則を示す。
【００９２】
【表３】
0003718716.tif 000004
【００９３】
ＩＯＭ
図１７に、（ａ）その入力経路と（ｂ）その双方向経路からの入力信号に作用するＩＯＭを示す。（ｃ）その入力経路からの直前の信号によって残されたごみがその双方向経路からの新規信号の処理に遅延を生じるが、この新規信号の吸収を阻止することはできない。ＩＯＭモジュールは、その入力経路から到着する信号を、図１７（ａ）に示すその双方向経路にリダイレクトするか、あるいは図１７（ｂ）に示すその出力経路にリダイレクトする。上記の遷移則のいくつかに加えて、ＩＯＭには表４の５つの遷移則が要求される。表４に、ＩＯＭモジュールに必要な遷移則を示す。
【００９４】
【表４】
0003718716.tif 000005
【００９５】
Ｓ−ＪＯＩＮ
図１８に（ａ）隣接経路と（ｂ）反対側の経路からの２つの入力信号に対して働きかけるＳ−ＪＯＩＮ及び（ｃ）待ち状態の入力信号を示す。Ｓ−ＪＯＩＮモジュールは、その３つの双方向経路のどの対であれ、その対から到着する２つの入力信号を結合し、その結果得られる信号を、図１８（ａ，ｂ）に示す残りの経路上に出力する。１つの経路から１つの信号だけが到着すると、その信号は、他の信号が図１８（ｃ）に示す他の２つの経路のうちの１つから到着するまで待ち状態になる。上記の遷移則のうちのいくつかに加えて、Ｓ−ＪＯＩＮには表５の３つの遷移則が必要とされる。表５に、Ｓ−ＪＯＩＮモジュールに必要な遷移則を示す。
【００９６】
【表５】
0003718716.tif 000006
【００９７】
ＡＴＳ
ＡＴＳモジュールは、受信入力信号へのその動作を決定する２つの状態０と１を有する。状態１にあることを示すのにＡＴＳモジュールの初期構成を使用する。上記の遷移則のいくつかに加えて、ＡＴＳに表６内の１６の遷移則が必要とされる。表６に、ＡＴＳモジュールに必要な遷移則を示す。
【００９８】
【表６】
0003718716.tif 000007
【００９９】
図１９は、（ａ）Ｔまたは（ｂ）Ｒ上の入力信号に、それが状態１（初期構成）のときに働きかけるＡＴＳモジュールを示す。図１９（ｃ）は、ＡＴＳモジュールが、Ｒにおける信号が待ち状態にある間に入力信号がＴから到着した後で状態０に設定され、Ｔ1上の出力信号となることを示す。図１９（ｄ）は、経路Ｔ上の入力信号に、それが状態０のときに作用するＡＴＳモジュールを示す。ＡＴＳモジュールが状態１にあるとき、入力経路Ｔから到着する信号は、図１９（ａ）に示すように、出力経路Ｔ1に向かう。入力経路Ｒから到着した信号は、図１９（ｂ）に示すように、Ｔ上の後続入力信号が到着して、Ｔ1への信号出力となり、そして状態０のモジュールをリセットするまで、待ち状態を維持する（図１９（ｃ）を参照）。入力経路Ｔ上のさらにもうひとつの信号は、経路Ｔ0上の出力信号となり、ＡＴＳモジュールを図１９（ｄ）に示す初期構成にリセットする。入力経路ＴとＲから２つの信号が同時に到着すると、ＡＴＳによりそれらの信号の間でアービトレーションが行われ、まずＴからの信号を出力経路Ｔ１に向かわせるか、まずＲからの信号をその経路上で待ち状態にするなどする。
【０１００】
厳密に言えば、Ａ5に埋め込まれたＡＴＳモジュールは、表１のその定義に比べて異なる方法で入力信号に対して働きかけるように見えるが、実際には、その挙動は、耐遅延性によって、外側から見る元のＡＴＳと区別することはできない。ＡＴＳの入力ラインＲ上の信号はいかなる出力にもならないことから、それに不定遅延を課して、ＡＴＳの状態を０にリセットせずに入力ラインＲで待ち状態にさせ（図１９（ｂ））、信号が入力ラインＴから到着するまでまるでそれが無限数の遅延によって入力ラインＲ上で「ハングアップ」しているかのようにすることができる。その信号がまだＲ上で待ち状態であるとき最後に信号が入力ラインＴから到着すると、ＡＴＳはＴのその入力信号を、最初に到着したものとして扱い、その直後にモジュールは状態０にリセットされる。図２０に、入力経路ＴとＲ上の２つの同時信号をアービトレーションするＡＴＳを示す。
【０１０１】
（非同期セルオートマトンへの回路の埋め込み）
定理２．１が意味するように、図７の基関数モジュールのネットワークによって任意のＤＩ回路を構築でき、それぞれの基関数モジュールは、セルの局所構成によって非同期セルオートマトンＡ5の中で実現され、その入力と出力は、信号の送信に使用される休止セルの経路によって互いに接続される。ＤＩ回路が形成されると、その回路の適切な経路に信号を入力して、適切な経路上で出力信号を発生させることで演算作業が実行できる。
【０１０２】
ＤＩ回路の例は、いわゆるＳ（Ｓｅｌｅｃｔモジュール）［R.M. Keller, “Towards a theory of universal speed-independent modules”, IEEETrans. Computers, vol. C-23, no. 1, pp. 21〜33, 1974.］である。図２１に、Sモジュールの例を示す。これは０と１の２つの状態を有するシリアルモジュールであり、後者が初期状態である（図２１を参照）。入力ラインＳ（Ｒ）上の信号は常に状態を１（０）に設定して、Ｓ’（Ｒ’）に転送される。入力ラインＴ（テスト信号）上の信号は内部状態を変えず、モジュールが状態１のときにはＴ１に、状態０のときにはＴ０に転送される。
【０１０３】
図２２に、Ｓモジュール用のＤＩ回路図とＡ5上のその構成を示す。Ｓモジュールの状態は、Ｓ−ＪＯＩＮモジュールＪ0とＪ1上の２つの待ち状態信号によって保存される。左の双方向経路Ｊ0とＪ1上の２つの信号は初期状態１を、両方の右の経路上の信号は状態０を示す。
【０１０４】
図２２は、基関数のネットワークによって実現されるＳモジュールのＤＩ回路図［F. Peper, J. Lee, S. Adachi and S. Mashiko, “Laying out circuits on asynchronous cellular arrays: towards feasible nanocomputers”, submitted for publication.］とＡ5上でのそのインプリメンテーションを示す。信号の方向をセルオートマトン内で左または右へ変更するのにＭＥＲＧＥとＩＯＭの両方を使用できるが、ＩＯＭの方が小型であることから、我々としてはこれにＩＯＭを使用する。信号がその入力経路のいずれかから到着するときはいつでも、この回路がＳモジュールとして機能していることを確認するのは容易である。
【０１０５】
ＤＩ回路の別の例は、図２３（ａ）に示す１つの入力ラインと１つの出力ラインを有するＭｏｄ−２カウンタである。図２３に、（ａ）Ｍｏｄ−２カウンタと、（ｂ）Ａ５上でのその構成を示す。
入力ラインＩ上の連続信号の各組は、出力ラインＯ上で１つの信号となり、第一の入力に対してこのモジュールから信号は何も出力されない。セルオートマトンへのＭｏｄ−２カウンタの実装は、図２３（ｂ）に示されている。図２３（ａ）の実現の正確性と図２３（ｂ）の構成は簡単に確認できる。
【０１０６】
上記のＳモジュールとＭｏｄ−２カウンタという２回路は、交差経路上での信号の同時発信を避けるなどのためにＡ5上に配置された。交差点上で互いに出逢う２つの信号ヘッドは、Ａ5がそのような状況に対処するための遷移則を持たず、また交差が行うための第三次元を欠いていることから、信号［S. Adachi, F. Peper and J. Lee, “Simulator of asynchronous cellular automata”, Proc.SICE Japan ’01 Kansai Chapter Symp., Osaka, pp. 198〜201, 2001. (in Japanese)，J. Lee, F. Peper, S. Adachi and K. Morita, “Crossing signals in asynchronous cellular automata”, Proc. LA Symp. ’01 Winter, Kyoto, pp. 31.1〜31.4, 2002. (in Japanese)］の両方のデッドロックを引き起こす。同時信号の交差は回路設計で回避できることが多いが、簡単にそうできない場合もある。幸いにも、図７の基関数だけを使用する、信号の交差に特化したモジュールを構築することが可能である。このモジュール内のすべての経路交差には信号衝突がないと保証されているので、このモジュールはあらゆる環境下で使用することができる。信号がその入力経路に到着する順序は、機能が正しく実行されるかどうかには無関係である。交差ＳＥＱＵＥＮＣＥＲの呼ばれるこのモジュールは、ＳＥＱＵＥＮＣＥＲモジュール［P. Patra, Approaches to Design of Circuits for Low-Power Computation, Ph.D. thesis,University of Texas at Austin, 1995.］に基づいている。図２４（ａ）にＳＥＱＵＥＮＣＥＲの基本設計を示す。図２４（ｂ）に交差ＳＥＱＵＥＮＣＥＲの基本設計を示す。その機能は次の通りである。図２４（ａ）の入力ラインａi（bi）上の信号は、ｂi（ａi）上の信号ではなくｃ上の信号とともに吸収され、ａo（ｂo）への信号出力となる。同時にａiとｂi上に信号があると、ａiとｂiのうちの（おそらく任意に選択された）１つだけがｃ上の信号と一緒に吸収され、対応するａoまたはｂoラインで出力される。吸収されなかったａiまたはｂi上の信号は同じ入力ライン上で待ち状態を維持する。
【０１０７】
図２４（ｂ）は、交差ＳＥＱＵＥＮＣＥＲの基本設計を示している。最初からラインｃ上に待ち状態の信号があるとの想定の下で、ＳＥＱＵＥＮＣＥＲの出力ラインａo（ｂo）上で生成された信号がＦＯＲＫによって複製され、１つの信号が出力ラインａ’o（ｂ’o）上に、そして他方の信号がラインｃにフィードバックされる。図７の基関数の面でＳＥＱＵＥＮＣＥＲのwithout-busy-waitingの実現［J. Lee, F. Peper, S. Adachi and K. Morita, “Compact designs of universal delayinsensitive circuits with bi-directional and bu.ering lines”, submitted for publication.］に続いて、その設計は詳細に練られ、図１９に示すセル空間上に配置される。
【０１０８】
交差ＳＥＱＵＥＮＣＥＲの使用によって回路のサイズが大きくなる場合でも、回路の正しい機能は耐遅延性があるために影響を受けない。交差ＳＥＱＵＥＮＣＥＲの構造は、表１の基関数を利用した任意のＤＩ回路が、Ａ5の二次元セル空間内に構築できることを示している。換言すると、以下の定理５．１となる。
【０１０９】
定理５．１  Ａ5はＤＩモジュールのクラスに万能であり、つまり、クラス内の各モジュールは、その非同期セル空間上のセルの有限構成によって実現できる。
【０１１０】
Ａ5上の無限数の基関数モジュールのネットワークをレイアウトすることによって万能チューリング機械をシミュレートすることは可能であると考えられる（J. Lee, F. Peper, S. Adachi and K. Morita, “Compact designs of universal delayinsensitive circuits with bi-directional and bu.ering lines”, submitted for publication.もちろん、この場合にはＡ5が無限数のセルから構成されることを想定している）。その結果、次の定理が成立する。
【０１１１】
定理５．２  Ａ5は計算が万能である。
【０１１２】
図２５に、交差ＳＥＱＵＥＮＣＥＲのＤＩ回路図とＡ5上でのその構成を示す。Ｓ−ＪＯＩＮ  Ｊcの右の（おそらく上側の）経路上で待ち状態の信号は、図２４（ｂ）のＳＥＱＵＥＮＣＥＲの入力ラインｃ上の信号として機能する。また、その上側（右側）の経路上に最初に配置された待ち状態の信号を有するＳ−ＪＯＩＮ  Ｊa（Ｊb）は、この回路が経路ａi（ｂi）で直前の入力信号をまだ処理している間、新規の入力信号がその回路の中に入るのを阻止するためのスイッチとして機能する。同時に、信号がループとなって走り始めてこれらのモジュールを二者択一式にスキャンして、ＡＴＳが状態０にある場合は、対応経路で出力を生成する。ループ内の信号は、次の入力信号がａiまたはｂiに到着することによって再度そこに配置されるまで、消失する。
【０１１３】
以上の例は、回転対称および反射対称の遷移則を使用してセル間の相互作用を記述するフォンノイマン・近隣を有する、新規な５状態非同期セルオートマトンである。セル空間に万能な耐遅延回路を埋め込むことによって万能計算を行えるＡＣＡモデルが証明された。本発明のＣＡは、非同期計算が同期ＣＡのシミュレーションに頼らずに直接それらの上で実行される点で、ＡＣＡ上で計算タスクを実行する通常の手法とは異なる。この純粋に非同期なこの計算方法は、すべての信号を一定時間に一定場所に到着させる必要性をなくし、その結果、基関数モジュールの局所構成とＡＣＡへのそれらの埋め込みの実現を簡素化した。
【０１１４】
本発明の５状態ＡＣＡ内のすべてのセルは、互いに独立して、任意の時間にその状態遷移を受け、そのためそれらの上に埋め込まれたＤＩ回路の動作の正確性は、それらのセルがその状態を更新する順序による影響を受けない。セルが更新される順序は、単に遷移則に依存するのみであり、非同期方法に関する想定内容に依存しない（［T.E. Ingerson and R.L. Buvel, “Structures in asynchronous cellular automata”, PhysicaD, vol. 10, pp. 59〜68, 1984.］などを参照）。実際、提案するＡＣＡは、タイミングのモードに関する前提条件をほとんど念頭に置くことなく設計されており、そのため、純粋な同期モードでも正しく実行される。
【０１１５】
関連した作業では、ムーア・近隣を有するモデルや、各セルの状態が隣接セルと１対１の対応関係にある複数の小状態に分けられる一種の分割化セルオートマトンであるいわゆる自己タイミングセルオートマトン（ＳＴＣＡ）［F. Peper, T. Isokawa, N. Kouda and N. Matsui, “Self-timed cellular automata and their computational ability”, to be published in Future Generation Computer Systems,2002.31］に基づいたモデルなど、他のＡＣＡモデル内でのＤＩ回路のインプリメンテーションも既に調査されている。これらのモデルは非同期であるが、２つの隣接セルが絶対にその状態を同時に変更しないとの制約を受ける。その結果、これらの代替モデルは同期モードでは動作せず、そのためＡ5よりも一般的ではない。
【０１１６】
本発明の結果は、大規模並列非同期コンピュータを実現する現実的な方法を約束するものである。提案中の５状態ＡＣＡ上に配置されたＤＩ回路の動作は並行して実行され、回路への入力信号がないことで回路全体が最終的に静的になるため、ほとんど電力を必要とせず、その結果ほとんど熱を放散しないという効果がある。
【０１１７】
以下、本発明の第２の実施の態様について説明する。本発明のセルラオートマトンの演算手段を構成する基本モジュール群である[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]はいかなる非同期回路をも構成することができる。非同期回路は、同期回路と異なりセントラルクロック信号を必要としない。このため、非同期回路を用いて論理回路を構成することには様々な利点がある。
【０１１８】
[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]が、いかなる非同期回路をも構成することができることを説明する。
以下、基本モジュール群[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]を構成するそれぞれモジュールの作用を説明する。
【０１１９】
図２６に、Ｐ−ＭＥＲＧＥ（Parallel−ＭＥＲＧＥ）を示す。
Ｐ−ＭＥＲＧＥは、演算部を、２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算部であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算部に入力信号が同時に入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させるモジュールであり、演算手段を、２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に２つの出力信号を出力するように機能させる第１の演算手段として機能する。
【０１２０】
Ｐ−ＭＥＲＧＥによれば、入力ラインの信号ａまたはｂは、出力ラインに出力される。ＭＥＲＧＥと異なり、ａとｂとが、同時に入力されることも可能である。したがって、Ｐ−ＭＥＲＧＥは、ＭＥＲＧＥの機能を真に含むものである。
【０１２１】
図２７に、Ｓ−ＪＯＩＮ（Ｓｙｍｍｅｔｒｉｃ−ＪＯＩＮ）を示す。
Ｓ−ＪＯＩＮは、演算部を、３つの入出力信号伝播路とに接続された演算部であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算部に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させるモジュールであり、演算手段を、３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２の演算手段として機能する。
【０１２２】
Ｓ−ＪＯＩＮによれば、入力ラインａ（ｂ）＜ｃ＞とｂ（ｃ）＜ａ＞からの信号は、同期されてｃ（ａ）＜ｂ＞からの出力信号となる。ａ、ｂ、ｃが、同時に入力されることは禁止される。ひとつの入力ラインが受領状態（信号を受け取った状態）にあるときは、他の入力ラインからの信号を受領するまで待ち状態に維持される。
【０１２３】
図２８に、ＩＯＭ（Ｉｎｐｕｔ−Ｏｕｔｐｕｔ  Ｍｕｌｔｉｐｌｅｘｅｒ）を示す。
ＩＯＭは、演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算部であって、前記入力信号伝播路から入力信号が演算部に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算部に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させるモジュールであり、演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段として機能する。
【０１２４】
ＩＯＭによれば、入力ラインａからの信号は、同期されてｂからの出力信号となる。また、ＩＯＭによれば、入力ラインｂからの信号は、同期されてａからの出力信号となる。
【０１２５】
図２９に、Ｒ−ＡＴＳ（Ｒｅｆｌｅｘｉｖｅ−ＡＴＳ）を示す。
Ｒ−ＡＴＳは、演算部を、２つの入出力信号伝播路に連結された演算部であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算部を１の状態とし、残りの入出力信号伝播路の状態を出力せずに１から０に戻し、演算部が１の状態のときにひとつの入出力信号伝播路から演算部に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算部が０の状態のときにひとつの入出力信号伝播路から演算部に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算部へ入力されたときは、どちらかの入力信号が演算部に先に入力され、残りの入力信号が遅れて演算部に入力されたように調整するように機能させるモジュールである。
【０１２６】
Ｒ−ＡＴＳは、演算手段を、２つの入出力信号伝播路に連結された演算手段であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算手段を１の状態とし、残りの入出力信号伝播路の状態を出力せずに１から０に戻し、演算手段が１の状態のときにひとつの入出力信号伝播路から演算手段に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算手段が０の状態のときにひとつの入出力信号伝播路から演算手段に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算手段へ入力されたときは、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段として機能する。
【０１２７】
なお、前記第４のモジュール（Ｒ−ＡＴＳ）の代りに、又は前記第４のモジュールとともに前記演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算部を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算部が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算部が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算部の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算部へ入力された場合は、どちらかの入力信号が演算部に先に入力され、残りの入力信号が遅れて演算部に入力されたように調整するように機能させるモジュールを用いてもよく、このモジュールは、前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算手段を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算手段が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算手段の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段として機能する。
【０１２８】
また、ケラー氏によればＡＴＳおよびＳと呼ばれる２つの有用なモジュールも提案されている。図３０に、モジュールＡＴＳ（Ａｒｂｉｔｒａｔｉｎｇ  Ｔｅｓｔ−ａｎｄ−Ｓｅｔ）を表す。
ＡＴＳは、０と１の状態がある。入力ラインＴからの信号は、常にＡＴＳを１の状態とし、入力ラインＲからの信号は、信号を出力せずに、常にＡＴＳの１の状態を０の状態に返す。ＡＴＳモジュールの状態が１の場合は、ラインＴからの信号は、ラインＴ1から出力される。また、ＡＴＳモジュールの状態が０の場合は、ラインＴからの信号は、ラインＴ0から出力される。もしも、ラインＴとラインＲから同時に信号がＡＴＳに入力された場合、いずれかが先で、いずれかが後に入力されたと同様にして信号が出力される。
【０１２９】
図３１は、ＡＴＳが、基本モジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現できることを表す図である。
【０１３０】
入力ラインｃ1とｃ2に待ち信号があり、それらをそれぞれJ1とJ2とする。なお、ここで、ｃ1とｃ2をJ1とJ2と記載したのは、その方向が決まっているからである。入力ラインＴから信号が伝達されたとすると、入力ラインｃ1の信号とあわさって、ラインＴ'からＲ−ＡＴＳに転送される。こののちに、ラインｃ1には待ち信号が残らないから、ラインＴ上の別の信号は、新しい信号がラインｃ1に伝達されるまでラインJ1の外で待つことになる。入力ラインＲの場合も同様である。このように、J1（J2）とは、入力ラインＴ（Ｒ）からの信号がライン（ｃ1）（ｃ2）上の制御信号を用いるときに入力した場合にのみスイッチの役割を果たす。
もしもＲ−ＡＴＳが１の状態であれば、Ｔ’からの出力信号は、ＦＯＲＫモジュールによって分枝される。分枝された信号のひとつは、ラインＴ1に、もうひとつはラインｃ1に戻り、次の入力のための制御（待ち）信号となる。もしもＲ−ＡＴＳが０の状態であれば、Ｒ’からの出力信号は、ＦＯＲＫモジュールによって分枝される。分枝された信号のひとつは、ラインＴ0に、もうひとつはラインｃ2に戻る。したがって、このネットワークは、先に説明したＡＴＳを実現しているといえる。
【０１３１】
先に説明したとおり、ＭＥＲＧＥは、Ｐ−ＭＥＲＧＥによって表現できる。
【０１３２】
ＴＲＩＡを本発明の基本モジュール群の[Ｓ−ＪＯＩＮ，ＩＯＭ]を用いて表現できることを図３２を用いて説明する。図３２から、入力ライン[Ｉ1，Ｉ2，Ｉ3]と、出力ライン[Ｏ1，Ｏ2，Ｏ3]は、ＴＲＩＡと等価であることが明らかである。
ＳＥＱＵＥＮＣＥＲをモジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現すると図３３のようになる。
【０１３３】
Ｓ−ＪＯＩＮモジュールＪ3，Ｊ5，Ｊ6は、それぞれ入力ラインｃ，ai，ｂi上にある信号のスイッチとして使用される。ＡＴＳモジュールにおいて説明したように、Ｊ1とＪ2は、ＴとＲにスイッチされる。ＳＥＱＵＥＮCＥＲの機能は、２つのＡＴＳと、ひとつのＰ−ＭＥＲＧＥを含む回路によって実現できる。入力ラインｃ上の信号は、Ｓ−ＪＯＩＮモジュールＪ4のために回路に直接入ることができない。十分長い時間にわたりラインｃ，ai，ｂiに信号がない場合、ラインｃに到達した新しいシグナルは、モジュールＪ4の入力ラインｃ4上に待ち状態となる。Ｓ−ＪＯＩＮモジュールＪ4は、入力信号ｂ4がある状態で、入力ラインｃ（ｃ4）からの入力信号を出力するスイッチとして機能する。ラインｂ4に到達する信号の数は、Ｐ−ＭＥＲＧＥ（Ｍ）のために、ＲaまたはＲbに到達する信号の数と同じである。このようにして、ＲaまたはＲb上のシグナルの結果、回路上の信号は、最終的にはラインａ0またはｂ0に送られる。
【０１３４】
以上より、ウイズアウトビジーウエイティング（without busy waiting）ＳＥＱＵＥＮＣＥＲを本発明の基本モジュール群を用いて表現できる。
【０１３５】
パトラ氏によれば、以下のセルラオートマトンの基本モジュール群[ＭＥＲＧＥ、ＦＯＲＫ、ＴＲＩＡ、ＳＥＱＵＥＮＣＥＲ]を用いれば、全ての非同期回路を設計することができる。そして、本発明の基本モジュール群を用いて、これら全てのモジュールを表現することができる。したがって、本発明の基本モジュール群は、全ての非同期回路を設計することができる。
【０１３６】
[ＮＡＮＤ回路]
本発明の基本モジュール群を用いた耐遅延ＮＡＮＤ回路（ゲート）を図３４に示す。
ＮＡＮＤゲートは、２つの入力がともに１のときにのみ出力を０とし、それ以外の場合は、出力を１とするゲートである。ＮＡＮＤゲートを用いれば、全ての論理回路を組み立てることができる。
ＮＡＮＤゲートによれば、入力ライン（a0，ｂ0）、（a1，ｂ0）、（a0，ｂ1）からの信号のペアが入力された場合は、出力ラインｃ1から信号が出力される。一方、入力ライン（a1，ｂ1からの信号のペアが入力された場合は、出力ラインｃ0から信号が出力される。したがって、本発明の基本モジュール群を用いれば、ＮＡＮＤゲートを組み立てることができることがわかる。ＮＡＮＤゲート（回路）を、用いれば、論理積（ＡＮＤ）、論理和（ＯＲ）、論理否定（ＮＯＴ）などの基本論理回路を設計することができる、また、ＮＡＮＤ回路を用いれば、双安定回路（ＦＦ回路）や、加算器なども設計できる。したがって、本発明の基本モジュール群を用いて、全ての論理回路（非同期回路）を設計することができる。さらに、非同期回路を設計し、コンピュータを設計することもできる。
【０１３７】
また、本発明のオートマトンを用いて演算装置を設計し、公知の入力装置、制御装置、記憶装置、出力装置と組み合わせたコンピュータを得ることができる。
【０１３８】
以下、本明細書の第３の実施の態様である非同期セルオートマトン（ＡＣＡ）について説明する。
【０１３９】
以下の非同期セルオートマトンは、いずれも１６状態のいずれかになることのできる同一セルの二次元配列である。セルの状態は、セル側面に沿って配置された４個のビットで符号化され（図３５参照）、塗りつぶした丸は値が１のビットを、そして塗りつぶしのない丸は値が０のビットを示す。
【０１４０】
各セルは、セルの４個のビットと、その４個の各隣接セルの最も近くのビットに対して働く「遷移則」に従って発生するいわゆる「遷移」を受ける。セルの遷移のタイミングは互いに独立しており、任意の時間に発生する。２つの隣接セルは、それらに共通の２つのビットを同時に異なる値に設定しようとしないよう、同時に遷移を受けない。図３６（ａ）は、１ビット１個と０ビット７個のパターンに働きかけて、この１ビットをセル１個分北に移動させる遷移則の例を示している。この条件は、図３６（ａ）の矢印の左の８個のビットのパターンに正確に一致する４個のビットと４個の隣接ビットを有するセルにのみ適用される。
【０１４１】
この遷移則は、２度適用されると、信号送信に使用される連続領域であるいわゆるセルの経路に沿って１ビットが北の方向へ移動する、図３６（ｂ）の構成の順序を生む。
【０１４２】
遷移則の回転対称および反射対称等価物も遷移則として使用してもよい。これによって、上記の遷移則を使用して信号を北、東、あるいは西の方向へ送信できるようになる。
【０１４３】
（耐遅延回路の基本的演算子）
同期システムでは、ＡＮＤゲートやＮＯＴゲートなど、数種類の基本演算子だけを使用して任意のブール回路を構築できる。残念ながら、このようなブールゲートは、論理機能だけを提供し、タイミング機能を提供しないので、耐遅延回路用の基関数としては適当でない。我々は、耐遅延回路により適し、かつ非同期セルオートマトン（図３７を参照）と特によく適合する基関数の集合を使用する。
【０１４４】
本発明によれば、従来提案された耐遅延回路用の基関数とは異なり、本実施例における基関数は、双方向接続ライン、つまり、同時でないにせよ入力と出力両用に使用可能なラインを有することができる。さらに、１本のラインには、すべて同一方向に動くのであれば複数の信号を同時に含んでいてもよい。これらの条件の下では、入出力に多くて３本のラインが必要とされ、これは非同期セルオートマトン上での基関数のシミュレーションを実質的に簡素化する。
【０１４５】
非同期セルオートマトン上での耐遅延回路のシミュレーション
図３７の右のセルの構成を使用して対応基関数をシミュレートし、それらをセルの経路によって互いに接続することによって、提案するセルオートマトン内に任意の耐遅延回路を実現できる。基関数のシミュレーションに必要な遷移則は、図３８に示されている。
【０１４６】
図３６（ａ）の遷移則とともに、これらは、セル間の発生し得る相互作用を記述する７つの条件から成る集合を形成する。図３７に示される構成は、入力信号が与えられた場合のみ遷移を受ける。これは、遷移則がそれ以外の場合ではそれらと一致しないからである。この結果、これらの構成は入力信号がない状態で安定している。
【０１４７】
隣接１ビット２個から成る構成で表されるＭｅｒｇｅ基関数は、図３９（ａ）に示すように、図３８に示される条件１に従って単一信号を処理し、また図３９（ｂ）に示すように２個の同時信号を条件２に従って処理する。この基関数はまた信号の左右のターンにも使用できる。
【０１４８】
入力／出力マルチプレクサは、１ビット３対から成る構成で表される。信号は、図４０（ａ）のように、左側のその双方向経路に入力されると、この構成の中を通過して、条件３と４に従って、その右側にそれを残す。図４０（ｂ）のように、その入力経路からの信号では、この構成はＭｅｒｇｅ基関数として働き、条件１により、双方向経路上の信号を左の方へ出力する。
【０１４９】
Ｓｙｍｍｅｔｒｉｃ  Ｊｏｉｎ基関数は、セルの反対外側の１ビット２個から成る構成によって表現される。１つの信号だけがこの基関数に入力される場合、それは、第二の信号が入るまで待ち状態に保持され、その後両方の信号が同化されて１つの出力信号を生成する。条件５は、入力信号が反対の経路から発したときに適用されるのに対して（図４１（ａ）参照）、条件６は、入力信号が隣接経路から発したときに適用される（図４１（ｂ）参照）。
【０１５０】
Ｆｏｒｋ構成では、条件７を条件４と併用してその入力経路から信号を処理する。図４２の連続構成の順序を通過して、これは、右側で１つの信号を、上側で１つの信号を生成する。但し、セルオートマトンの非同期計算によって必ずしもこれらが同時に行われるとは限らない。
【０１５１】
最後に、条件８は、基本的には入力／出力マルチプレクサであるが追加機能を有する、（図４３の塗りつぶし部分として表示される）コアの周囲に構築された構成として表現されるArbitrating Test & Set基関数に使用される。
【０１５２】
このコア（図４３（ａ）参照）は、その標準状態において、その入力経路から到着する信号をその出力経路の方へとリダイレクトする。双方向経路からの信号が到着すると、コアからの中間１ビット対が０（図４３（ｂ）参照）にリセットされ、双方向経路から出力されてコアをその元の状態に復元する入力経路からの次の信号の道を解放する。
【０１５３】
セルオートマトン上に基関数を配置してそれらを経路によって互いに接続することによって耐遅延回路を実現する場合は、セルオートマトンが交差を行うための第三次元を欠いているため、互いに交差する経路には特別な注意が必要である。信号の交差に特化した構成は、その対応回路図とともに、図４４の中に示されている。
【０１５４】
図４４に示される構成は、図３７に示されるような基関数以外は必要とせず、信号がその入力に到着する順序がどうであれ、衝突のない交差を保証する。
【０１５５】
１ビットメモリとその制御回路
ここまで構築された基関数は耐遅延回路の構築に使用できる。これは、２進数を記憶するメモリレジスタ、計算を実行する回路等々を含む。ここで、読み取り/書き込み動作に必要な制御回路（図４５(a)）を有するSモジュールとも呼ばれる１ビットメモリと、提案するセルオートマトン内のインプリメンテーションを示す（図４５(ｂ)）。このメモリ内のすべての経路交差は衝突がなく、またそのため図４４内に交差構成を必要としない。
【０１５６】
メモリの状態は、２つのＳｙｍｍｅｔｒｉｃ  Ｊｏｉｎ基関数への左または右の入力経路上の２つの待ち状態の信号（図４５（ａ）の回路図内の黒点で示されている）によって記憶される。左の入力経路上で待ち状態になっている信号は０、つまり初期状態を意味し、右の信号は状態１を意味する。
【０１５７】
このメモリへの０ビットまたは１ビットの書き込みは、それぞれ入力経路Ｗ0またはＷ1上の信号を送ることによって行われる。このため、メモリの状態を記憶する２つの待ち状態の信号は除去され、その後、回路の一番上の他のＳｙｍｍｅｔｒｉｃ  Ｊｏｉｎ基関数内に一時的に保持される実際の書き込み信号が、２つのＳｙｍｍｅｔｒｉｃ  Ｊｏｉｎ基関数の各々にロードされる。これは、メモリが新しい入力信号を受信する準備ができていることを確認するため、書き込み信号がＷ0またはＷ1のいずれであるかによって、ぞれぞれＡ0またはＡ1上の出力信号を伴う。
【０１５８】
メモリの読み取りは、Ｒで示した入力経路に信号を送ることによって行われる。これは下側のＳｙｍｍｅｔｒｉｃ  Ｊｏｉｎ基関数だけの読み出しを要求し、メモリの状態によって、Ｒ0またはＲ1上に信号を生成する。
【０１５９】
ナノテクノロジーとの関連
提案する非同期セルオートマトンモデルは、その規則正しい構造、その非同期タイミングモード、およびその簡略性により、ナノテクノロジーで構築されるコンピュータの基本アーキテクチャとしての利用に大きな期待を集めている。
【０１６０】
多数の単純なセルの規則正しい構造は、１つの設計の中で何度も再利用できるいくつかの部品へと設計努力を減らせるだけでなく、費用効果の高い製造の可能性をも開くものである。ナノメータ規模のセルオートマトンを大量生産することは極めて困難であるが、この仕事は、フォンノイマン・コンピュータに中にある不規則な構造体を製造するよりもずっと容易である。この点で有望なのが、構成部品を大量に生産してそれらを管理された自己組立によって二次元配列でそれらをつなぎ合わせる技術である。このような技術は、およそ１０20個の簡単な同一セルを有するコンピュータを可能にする。セルが約１ＧＨｚの周波数と並行して実行できる場合、性能は現行コンピュータの性能よりも１０桁のオーダー高く、その演算能力は、物理学では粒子系のシミュレーション、神経細胞網のシミュレーション、および遺伝子アルゴリズムなど、大規模な並列処理を必要とするアプリケーションで特に有用である。ナノコンピュータに期待される類似の性能の向上が他の分野での暗示されている。
【０１６１】
非同期のタイミングモードは中央クロックを不要にし、またその結果ハードウェアの複雑性を軽減する。分子は非同期の挙動を示す傾向にあるがその非同期性に対してより適合性を有することから、非同期セルオートマトンの物理的実装が同期セルオートマトンの物理的実装よりも直裁的である。さらに、過剰な電力消費、熱損失、配線要件、設計の非モジュラー性、信号のレーシング条件、および若干異なる時間（クロックスキュー）にクロック信号を受信する回路部分の相違など、同期コンピュータで遭遇する問題点は、非同期設計では存在しないかあるいはそれほど深刻ではない。マイナスの部分は、非同期性に付随する不確実性によって、非同期システムでの演算が同期システム上よりも困難であることである。これは、これまで考えられてきたほど深刻な問題ではないことが判明した。
【０１６２】
提案する非同期セルオートマトンの単純性の重要な鍵は、それ上での耐遅延回路のシミュレーションである。これは、セル状態と遷移則の必要数を制限するだけでなく、セルオートマトンの大規模並列処理の効率的活用を可能にする。モデルは単純性であるが、従来のコンピュータと同一クラスの演算を実行することができる。
【０１６３】
この実施の態様では、非同期セルオートマトン上で耐遅延回路を効率的にシミュレートする方法を示すが、本質的に同質のセルラーハードウェアを特定の耐遅延回路９、３０へと構成する問題は未解決のままである。この問題は、要するに、一定の情報パターン（回路レイアウトを表す適切な常態のセルの構成）をセル間の局所的相互作用だけを利用することによってセルオートマトン内の一定の場所に移動することに帰着する。概念的には自己複製に近いこの作業は、同期セルオートマトンでは研究が進んでおり、その非同期セルオートマトンでも実行可能である。
【発明の効果】
本発明の基本モジュール群は、最大でも３つの入力ライン、出力ライン、入出力ラインから選ばれるラインのみを有する。そして、本発明の基本モジュール群は、汎用性がある。
本発明のセルラオートマトンによれば、コンピュータをより簡便に設計することができる。
【図面の簡単な説明】（後日調整予定）
【図１】図１は、本発明の基本モジュール群と、ケラー氏の基本モジュール群との対応を表す図である。
【図２】ＭＥＲＧＥを表す。
【図３】ＦＯＲＫを表す。
【図４】ＴＲＩＡを表す。
【図５】ＳＥＱＵＥＮＣＥＲを表す。
【図６】信号を表す。ある値の信号は、図６（ａ）のトークンのように表される。待ち信号は、図６（ｂ）のように表される。
【図７】図７に、セルオートマトンにその初期構成を埋め込んだ基関数耐遅延モジュールを示す。
【図８】フォンノイマン近傍を有するＣＡを表す。
【図９】図９に１つの信号を示す。
【図１０】図１０に経路上への信号の送信を示す。
【図１１】Ａ5の経路を転送される信号を表す。
【図１２】図１２は、ＦＩＦＯバッファリングラインを表す信号で満たされたセルの経路を示す。
【図１３】図１３は、ごみを含むテールを有する信号は、そのごみが除去されるまで後続の信号を妨げるが、その継承者が最終的にその目的地に到達するのを阻止できないことを示す図である。
【図１４】１つの入力信号に対して働きかけるＭＥＲＧＥを示す。
【図１５】本発明の基本モジュール群を用いたＮＡＮＤＯゲートを表す。
【図１６】図１６は、入力信号に作用するＦＯＲＫを示す。
【図１７】図１７は、（ａ）その入力経路と（ｂ）その双方向経路からの入力信号に作用するＩＯＭを示す。
【図１８】図１８は、（ａ）隣接経路と（ｂ）反対側の経路からの２つの入力信号に対して働きかけるＳ−ＪＯＩＮ及び（ｃ）待ち状態の入力信号を示す。
【図１９】図１９は、（ａ）Ｔまたは（ｂ）Ｒ上の入力信号に、それが状態１（初期構成）のときに働きかけるＡＴＳモジュールを示す。
【図２０】図２０は、入力経路ＴとＲ上の２つの同時信号をアービトレーションするＡＴＳを示す。
【図２１】図２１は、Sモジュールの例を示す。
【図２２】図２２は、Ｓモジュール用のＤＩ回路図とＡ5上のその構成を示す。
【図２３】図２３は、ＤＩ回路の別の例を示す。
【図２４】図２４（ａ）は、ＳＥＱＵＥＮＣＥＲの基本設計を示す。図２４（ｂ）は、交差ＳＥＱＵＥＮＣＥＲの基本設計を示す。
【図２５】図２５は、交差ＳＥＱＵＥＮＣＥＲのＤＩ回路図とＡ5上でのその構成を示す。
【図２６】図２６は、Ｐ−ＭＥＲＧＥ（Parallel−ＭＥＲＧＥ）を示す。
【図２７】図２７は、Ｓ−ＪＯＩＮ（Ｓｙｍｍｅｔｒｉｃ−ＪＯＩＮ）を示す。
【図２８】図２８は、ＩＯＭ（Ｉｎｐｕｔ−Ｏｕｔｐｕｔ  Ｍｕｌｔｉｐｌｅｘｅｒ）を示す。
【図２９】  図２９は、Ｒ−ＡＴＳ（Ｒｅｆｌｅｘｉｖｅ−ＡＴＳ）を示す。
【図３０】図３０は、モジュールＡＴＳ（Ａｒｂｉｔｒａｔｉｎｇ  Ｔｅｓｔ−ａｎｄ−Ｓｅｔ）を表す。
【図３１】図３１は、ＡＴＳが、基本モジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現できることを表す図である。
【図３２】図３２は、ＴＲＩＡを本発明の基本モジュール群の[Ｓ−ＪＯＩＮ，ＩＯＭ]を用いて表現できることを示す図である。
【図３３】図３３は、ＳＥＱＵＥＮＣＥＲをモジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現した図である。
【図３４】図３４は、本発明の基本モジュール群を用いたＮＡＮＤ回路を表す。
【図３５】図３５は、本発明のセルオートマトンの一例である。各セルが4個のビットを含むセルオートマトンである。塗りつぶした丸は1ビットを、塗りつぶしのない丸は0ビットを示す。
【図３６】図３６は、遷移則の例を示す。（a）の遷移則を(b)の構成に二度適用すると、信号が北へ2セル分移動する。
【図３７】図３７は、本発明の非同期セルオートマトンの一例を示す。
【図３８】図３８は、遷移則を示す。（a）１つの信号には条件１を使用して、そして（b）2つの同時信号には条件２を使用して働きかけるMerge
【図３９】図３９は、処理条件を示す図である。
【図４０】図４０は、非同期セルオートマトン上での耐遅延回路のシミュレーションの説明図である。（a）その双方向経路への信号入力には条件３と４を使用して、そして（b）その入力経路への信号入力には条件１を使用して働きかける入力出力マルチプレクサである。
【図４１】図４１は、Ｓｙｍｍｅｔｒｉｃ  Ｊｏｉｎ（S-JOIN）基関数（モジュール）の説明図である。（a）両方の経路からの2つの信号に対しては条件５を使用して、（b）隣接経路からの2つの信号に対しては条件６を使用して働きかける。
【図４２】図４２は、Ｆｏｒｋ構成（モジュール）を説明する図である。条件７と４を使用して１つの信号を２つの信号に分岐させる。出力信号がこの分岐を右側と上側に残す。但し、これは必ずしも同時である必要はない。
【図４３】図４３は、Arbitrating Test & Setに使用される構成を表す。（a）の構成は、入力経路から出力経路へ信号を条件１、３、および４を使用して経路設定する。双方向経路からの入力信号は、条件８に従って（a）の構成を（b）の構成に変形させる。この後、次に入力経路からの信号が到着すると、条件１を使用して経路設定され、その後、構成は条件４によって（a）の1へ戻され、信号が双方向経路に出力される。
【図４４】図４４は、信号の交差に特化した構成を示す図である。
【図４５】図４５(a)は、読み取り/書き込み動作に必要な制御回路を示す。図４５（ｂ）は、セルオートマトン内のインプリメンテーションを示す。
【図１】
0003718716.tif 000008
【図２】
0003718716.tif 000009
【図３】
0003718716.tif 000010
【図４】
0003718716.tif 000011
【図５】
0003718716.tif 000012
【図６】
0003718716.tif 000013
【図７】
0003718716.tif 000014
【図８】
0003718716.tif 000015
【図９】
0003718716.tif 000016
【図１０】
0003718716.tif 000017
【図１１】
0003718716.tif 000018
【図１２】
0003718716.tif 000019
【図１３】
0003718716.tif 000020
【図１４】
0003718716.tif 000021
【図１５】
0003718716.tif 000022
【図１６】
0003718716.tif 000023
【図１７】
0003718716.tif 000024
【図１８】
0003718716.tif 000025
【図１９】
0003718716.tif 000026
【図２０】
0003718716.tif 000027
【図２１】
0003718716.tif 000028
【図２２】
0003718716.tif 000029
【図２３】
0003718716.tif 000030
【図２４】
0003718716.tif 000031
【図２５】
0003718716.tif 000032
【図２６】
0003718716.tif 000033
【図２７】
0003718716.tif 000034
【図２８】
0003718716.tif 000035
【図２９】
0003718716.tif 000036
【図３０】
0003718716.tif 000037
【図３１】
0003718716.tif 000038
【図３２】
0003718716.tif 000039
【図３３】
0003718716.tif 000040
【図３４】
0003718716.tif 000041
【図３５】
0003718716.tif 000042
【図３６】
0003718716.tif 000043
【図３７】
0003718716.tif 000044
【図３８】
0003718716.tif 000045
【図３９】
0003718716.tif 000046
【図４０】
0003718716.tif 000047
【図４１】
0003718716.tif 000048
【図４２】
0003718716.tif 000049
【図４３】
0003718716.tif 000050
【図４４】
0003718716.tif 000051
【図４５】
0003718716.tif 000052