(57)【特許請求の範囲】
【請求項１】
再設定可能なハードウェアプラットフォームを備えるシステムであって、
前記再設定可能なハードウェアプラットフォームは、DNA言語として定義されるプログラミング言語で表現されるプログラムを実施することにより、前記システムの自己組織化および自己維持を実現するためにプログラミングされるように構成されるセルとして定義される、複数のハードウェアユニットを備え、
前記再設定可能なハードウェアプラットフォームは、複数のルータを備え、
各セルは、複数のルータに接続されているとともに、各ルータは、複数のセルに接続されており、各セルは、前記システム内の複数の他のセルとダイナミックに通信するように構成され、
前記システムは、前記DNA言語からのキーワードを、バイナリDNAコードに変換するように構成されるコンバータエンジンをさらに含み、
前記システムの自己組織化を実現するために、前記DNAコードは、前記セルの1つまたは複数に送信されるものであり、前記1つまたは複数のセルのそれぞれは、前記システム内でのその機能を決定するものであり、
第1のセルで欠陥が発生し、前記第1のセルがその機能を実行することを停止するならば、ルータが、前記第1のセルがその機能を実行することを停止したという情報をセルに送信し、その後、第2のセルが前記第1のセルの前記機能を引き受けることを実現するために、前記自己組織化が再び実行されるということにより、自己維持が実行されるシステム。
【請求項２】
前記システム内の1つまたは複数の変数を含む表である、少なくとも1つのデータ回復センタ(DRC)をさらに備え、前記DRCは、少なくとも1つのセルが、前記DRCになるために分化することにより生成される、請求項1に記載のシステム。
【請求項３】
前記セルは、前記システム内の他のセルからの情報を要求するともに、前記システム内の他のセルに情報を送信する、請求項1に記載のシステム。
【請求項４】
前記第2のセルが前記第1のセルの前記機能を引き受けたならば、第3のセルが、前記第2のセルの前記機能を引き受ける、請求項1から3のいずれかに記載のシステム。
【請求項５】
各セルは、成長パターンに従って、前記各セルが前記第1のセルの前に配置されているか、それとも後に配置されているかを推定し、前記セルが前記第1のセルの後に配置されているならば、前記セルは、それが前に有していた番号より1小さいセル番号を有するようにリナンバリングされる、請求項1から4のいずれかに記載のシステム。
【請求項６】
前記セルは、前記システムの独立した部分が並列に実行できるように、並列構文として定義されるDNA構文を使用するために構成される、請求項1から5のいずれかに記載のシステム。
【請求項７】
前記セルは、前記セルが前記独立した部分を並列に成長させるように、並列構文を使用するために構成される、請求項6に記載のシステム。
【請求項８】
セルは、ゲートレベルよりも高いレベルの論理粒度で、機能を実施するように構成される、請求項1から7のいずれかに記載のシステム。
【請求項９】
前記セルは、機能的な方法で前記DNAコードを解釈するように構成され、それによって、前記DNAコードが表現する各機能は、1つのセルに配置される、請求項1から8のいずれかに記載のシステム。
【請求項１０】
ガードセルとして定義される1つのセルが、ガーディアン回路の機能を実行する、請求項1から9のいずれかに記載のシステム。
【請求項１１】
前記DNAコードは、前記DNA言語内のステートメントである、複数のステートメントを備えるように構成される、請求項1から10のいずれかに記載のシステム。
【請求項１２】
再設定可能なハードウェアプラットフォームを備えるシステムの、自己組織化および自己維持を実現する方法であって、
前記再設定可能なハードウェアプラットフォームは、セルとして定義される複数のハードウェアユニットと、複数のルータとを備え、
各セルは、複数のルータに接続されているとともに、各ルータは、複数のセルに接続されており、前記方法は、
-  DNA言語として定義されるプログラミング言語で表現されるプログラムを実施することにより、前記システムの自己組織化および自己維持を実現するために、前記セルの1つまたは複数をプログラミングするステップであって、各セルは、前記システム内の1つまたは複数の他のセルとダイナミックに通信するように構成されるステップと、
-  コンバータエンジンにより、前記DNA言語からのキーワードを、バイナリDNAコードに変換するステップと、
-  前記DNAコードを、前記セルの1つまたは複数に送信するステップであって、前記1つまたは複数のセルのそれぞれは、前記システム内でのその機能を決定するように構成されるステップと、
-  第1のセルで欠陥が発生し、前記第1のセルがその機能を実行することを停止するならば、ルータからの情報を前記セルに送信するステップであって、それによって、自己維持が前記システムにより実行されるステップと、
-  第2のセルが前記第1のセルの前記機能を引き受けることを実現するために、前記自己組織化を再び実行するステップとを含む方法。
【請求項１３】
前記システムに請求項12に記載された方法を実行させるためのプログラム。
【請求項１４】
前記システムに請求項12に記載された方法を実行させるためのプログラムを記
憶したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、一般には、欠陥(fault)が発生する際にそれらを訂正することができる半導体デバイスなどのシステムに関するものである。より詳細には、本発明は、再設定可能な(reconfigurable)ハードウェアプラットフォームと、プログラミング言語で表現されるプログラムを実施することにより、システムの自己組織化および自己維持(self-maintenance)を実現するためにプログラム可能なセル(cell)として定義される、複数のハードウェアユニットとを備えるシステムに関するものである。
【背景技術】
【０００２】
ハードウェアの設計では、より高いフォールトトレランスが、より重要な主題となりつつある。当然ながら、エラーおよび性能損失が許容され得ないシステムであるセーフティクリティカルなシステム、ならびに、エラーがきわめて望ましくなく、アプリケーションが救われ得る限りにおいて性能損失が容認可能であるシステムである弾力的なシステムは、より高いフォールトトレランスを有するために、基礎となるハードウェアプラットフォームを必要とするシステムであるが、より高いフォールトトレランスは、標準のアプリケーションにおいても、ますます重要になりつつある。トランジスタのサイズが小さくなることにより、半導体デバイスを製造することが、ますます困難になりつつある。トランジスタのサイズが小さくなるにつれて、誤った場所に配置される各原子が、トランジスタ全体に対して、より多数を占めるようになり、これにより、トランジスタが変形され、または最良の場合でも、考えられていたよりもわずかに大きくなり、したがって、それに対してわずかに異なる電気特性が与えられ、そのために、デバイスに対して欠陥がもたらされる。これは、所与のデバイスが特定の方法で動作することになるということを保証するのが困難であるということを意味する。したがって、技術は、半導体デバイスを監視し、欠陥が発生する際にそれらを訂正する方法を、非常に必要としている。
【０００３】
Mangeらによる論文: Towards Robust Integrated Circuits - The Embryonic Approach; Proceedings of the IEEE、IEEE、New York、US、第88巻、第4号、2000年4月1日は、自己修復および自己複製が可能な超大規模集積回路の開発に向けた手法を開示する。自己修復は、重大ではない欠陥の場合の部分的な再構成として定義され、自己複製は、重大な欠陥の場合の、元のデバイスの完全な再構成として定義される。この文献は、発生学(embryonics)の4つのレベルの階層、すなわち、集団レベル、組織体レベル、セルレベルおよび分子レベルを利用する。
【０００４】
米国特許第5931959号明細書には、ハードウェアベースの柔軟なフォールトトレランスを提供するための、フォールトトレラントのマルチプロセッサシステムが記載されている。このシステムは、メモリインターフェースを介して、再設定可能な論理兼スイッチングデバイスに接続される、複数の結果メモリに接続される、複数のコンピューティングモジュールを備える。再設定可能な論理兼スイッチングデバイスは、ビット単位での正確性を要求する従来のフォールトトレランス機能と、出力がユーザにより定義される妥当性基準を満たすかどうかをチェックする、より複雑なアルゴリズムを使用する、より精巧なフォールトトレランス機能との両方を供給するようにプログラミングされ得る。
【０００５】
米国特許第6874108号明細書には、フィールドプログラマブルゲートアレイのフォールトトレラントの動作の方法が記載されている。この方法は、信号経路内で欠陥源を識別し、前記欠陥源を除外するために前記信号経路を再設定し、前記信号経路を再設定することにより発生する伝搬遅延を推定し、推定される伝搬遅延がクリティカルパスの伝搬遅延より大きい場合に、システムクロックを調整することにより動作する。
【０００６】
米国特許第7142953号明細書には、宇宙船での使用のためにリモートで設定され得るデジタル処理システムが記載されている。このデジタル処理システムは、処理タスクを実行するためのフィールドプログラマブルゲートアレイと、命令を受信するための前記宇宙船上の受信機と、前記命令に従って、前記フィールドプログラマブルゲートアレイを再設定するために、前記受信機に結合されるフィールドプログラマブルゲートアレイ設定ユニットとを備え、それにより、前記フィールドプログラマブルゲートアレイのリモート設定を可能にする。
【０００７】
米国特許第7343579号明細書には、入力信号が実行時間中に処理される方法を動的に変化させることが可能な、再設定可能な適応コンピューティングシステムが記載されている。このコンピューティングシステムは、検出される環境の状態に基づいて環境信号を生成するための検出器と、環境信号を受信し、その信号に基づいて、複数の処理設定から1つの処理設定を選択するためのコントローラとを備える。
【０００８】
現在、この問題は、システムに静的冗長性を導入することにより解決されるように努力がなされている。冗長性が付加されているという意味での静的は、単に、すでに実施されている機能性の余分なコピーである。システムの複数のコピーは、すべて同じ機能を実行し、比較器またはボータは、コピーの出力を比較する。ボータは、コピーの過半数が出力する出力が、有効な出力として選択されるものであるということを確実にする。これは安定した解決策であるが、それにはマイナス面もある。それらは、例えば、以下のようなものである。
-  性能低下:比較器またはボータの回路は、システムに余分の遅延をもたらす。
-  増加する電力および領域のオーバーヘッド:同じデバイスのx個のコピーを有することは、当然ながら、必要とされる余分な領域および電力をx倍にすることになる。
-  比較器またはボータの故障:欠陥をチェックする回路が故障する場合に、これに対処する方法が存在すべきである。そして、これをチェックすることが可能であるべきである。
【０００９】
さらには、フィールドプログラマブルゲートアレイ(FPGA)のような再設定可能なハードウェアプラットフォームは、その再設定可能性のためにすでに余分なオーバーヘッドをもたらしているので、上述の解決策は、主として、特定用途向け集積回路(ASIC)に適用される。当然ながら、同じ技術が、再設定可能なハードウェアプラットフォームに対して採用され得るが、それは、領域、電力および速度に関して、オーバーヘッドをさらにそれ以上に増加させることになる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許第5931959号明細書
【特許文献２】米国特許第6874108号明細書
【特許文献３】米国特許第7142953号明細書
【特許文献４】米国特許第7343579号明細書
【非特許文献】
【００１１】
【非特許文献１】Mangeら: Towards Robust Integrated Circuits - The Embryonic Approach; Proceedings of the IEEE、IEEE、New York、US、第88巻、第4号、2000年4月1日
【発明の概要】
【発明が解決しようとする課題】
【００１２】
再設定可能な、フォールトトレラントのシステムを改善するという課題が残されている。
【課題を解決するための手段】
【００１３】
-  再設定可能なハードウェアプラットフォームと、
-  DNA言語(DNA language)として定義されるプログラミング言語で表現されるプログラムを実施することにより、システムの自己組織化および自己維持を実現するためにプログラミングされるように構成されるセルとして定義される、複数のハードウェアユニットと
を備え、
各セルは、システム内の1つまたは複数の他のセルと通信するように構成され、
システムは、DNA言語からのキーワードを、バイナリDNAコードに変換するように構成されるコンバータプログラムをさらに含み、
自己組織化は、DNAコードが、セルの1つまたは複数に送信され、1つまたは複数のセルのそれぞれは、システム内でのその機能を決定するように構成されることを含み、
第1のセルで欠陥が発生し、第1のセルがその機能を実行することを停止するならば、システムが、第1のセルがその機能を実行することを停止したという情報をセルに送信し、その後、第2のセルが第1のセルの機能を引き受けることを実現するために、自己組織化が再び実行されるということにより、自己維持が実行されるシステムが開示される。
【００１４】
したがって、システム内のある事象に関する情報が、DNAから、および、いくつのセルが終えんとなったかに関する情報から十分に導出され得るため、それによって、自己修復が、すべてのアクティブなセルに、あるセルが終えんとなったことを通知することにより実行され、次いで、更新されたセル終えんカウンタを用いて自己組織化処理を再実行するということが、1つの利点である。
【００１５】
システム内の情報は、セルに対して、1つまたは複数のルータから送信され得る。
【００１６】
自己組織化は、このシステムでの特徴であり、プラットフォームを再設定し、DNAにより指定される機能を実行する準備ができていることを確実にする。自己組織化は、完全に制御され、セルにより実行され得るとともに、ユーザの介在は、必要とされなくてもよい。さらには、自己組織化は、中央集権的な「賢人」により制御されることとは対照的に、分散処理であってよく、したがって、単一障害点を有するリスクが除去される。
【００１７】
さらには、システムは、それが他の方法でなされた場合よりも堅牢であるということが1つの利点である、というのは、セルに関する情報がDNAから直接解釈され得るためであり、というのは、セルは、他のセルとともに機能を果たすために、他のセルに依存せず、それ自体にのみ依存するためである。このように、ネットワークおよび他のセルの状態は、自己設定に何ら影響を与えない。
【００１８】
さらには、セルは、例えば変数、データなどのすべてのコンテンツを次のセルにコピーすることにはならないので、セルの終えん、すなわちセルがその機能を実行することを停止するときは、非常に簡素に対処され得るということが、1つの利点である。セルの終えんに対処するために、自己組織化アルゴリズムが実行されるだけになり、セルは、必要ならば、それらの機能をシフトすることになる。
【００１９】
例えば、先行技術文献である、Mangeら: Towards Robust Integrated Circuits - The Embryonic Approachは、欠陥セルおよび自己修復を実施するために使用される予備セルを開示し、この文献は、欠陥セルが出現するとき、「欠陥セルが属するカラム全体が欠陥であるとみなされ、非活動化され」、「カラム(〜)の右側のセルのすべての機能(〜)は、1カラムだけ右側にシフトされ」、「明らかに、この処理は、存在する欠陥セルすなわち修復すべきカラムと同じ数の予備カラムを、アレイの右側に必要とする」ということを開示する。
【００２０】
上記とは対照的に、本発明のシステムでは、欠陥セル自体のみが非活動化され、欠陥セルを含むカラム全体ということではなく、したがって、Mangeらの文献でよりも、必要とされる予備セルが少ないということが、1つの利点である。
【００２１】
例えば、プラットフォームが3つのセル×3つのセルの正方形であるならば、全体で9つのセルが存在する。最初の2つのカラムのセル、すなわちセルの6つが機能を有するならば、1つのカラム、すなわち3つのセルが、予備セルとして使用されるべく残されている。機能を有するセルの1つで欠陥が発生するならば、Mangeらのシステムによると、欠陥セルを有するカラム全体が、予備セルを有するカラムで置換されることになる。この後には、予備セルがまったく残されていないことになる。したがって、予備セルを有するカラムがただ1つ存在するときには、欠陥はただ1つだけ発生してもよい。
【００２２】
このように、本発明のシステムでは、欠陥セルのみが予備セルで置換されることになり、存在する予備セルと同じ数の欠陥が発生してもよく、すなわち、予備カラムの数は重要ではないということが、1つの利点である。
【００２３】
レジスタを有することが、大量のデータが存在する場合には、システムが低速で動作するという結果になる可能性があるため、セルがレジスタに分化しないということが、さらなる利点である。レジスタがない場合、各ユニットが後でそこからデータを取り出すべきレジスタにデータを格納する代わりに、データは直接、それが使用される場所に転送されるので、システムはより高速で動作する。
【００２４】
各セルが、それ自体の機能を読み出し、または抽出し、または決定するように、DNAコードがセルに送信され、それによって、DNAコード全体が、あらゆるセルに格納される、またはセルからセルにコピーされる必要がなく、したがって、その結果、1つのセルには1つの機能が存在するということが、さらなる利点である。ただ1つのコピーが存在し、かつ欠陥が発生するならば、DNAコードが失われる可能性があるので、DNAコードの2つ以上のコピーが存在してもよい。このように、DNAコードの2つ以上のコピーが存在してもよいが、セルと同じ数のコピーは、存在しないことが好ましいことになる、というのは、これは効率的にはならない、または空間的な節約にはならないためである。
【００２５】
一方、Mangeらによる先行技術文献: Towards Robust Integrated Circuits - The Embryonic Approachでの自己組織化は、データをコピーするステップを含む、というのは、母セルが、作動ゲノム(operative genome)の唯一のコピーを保持し、次いで、このコピーは、時間t1後に、隣接する、すなわち娘のセルにコピーされるためである。セル分裂のこの処理は、組織体のすべてのセルが完全にプログラミングされるまで継続する。こうして、あらゆるセルが、すべてのセルに関するすべての情報を含む。データのコピーは、長い時間がかかる場合があり、すべてのコピーは、広大な空間を占有する場合がある。
【００２６】
背景技術の項で述べたように、あるシステムには冗長性を使用する欠点が存在するので、このシステムでは、静的冗長性が回避されるということが、さらなる利点である。静的冗長性を回避するということは、システム内の欠陥が、欠陥がどこにあるかにかかわらず、修復され得るということを意味する。本発明のシステムは、動的マッピングを備える。
【００２７】
Mangeらの文献では、いわゆる分子の間で通信が行われる。ネットワークは固定配線であり、通信は隣接のセルまたは分子の間でのみ可能である。通信が行われるのが静的な手段によるため、分子Xに欠陥が発生する場合は、分子Xおよび分子Xを通るワイヤの両方が破壊される場合があり、それによって、システム内の通信が遮断されるようになる場合があり、そのために、システムが故障する場合がある。一方、本発明のシステムでは、ネットワークの動的な性質により、ワイヤの欠陥は、パッケージを経路再指定することにより許容され得る。
【００２８】
上記とは対照的に、本発明のシステムでは、通信はいわゆるノードの間で行われ、そのため、通信はすべてのセルの間で可能であり、したがって、セルXで欠陥が発生する場合は、セルXおよびセルXへのワイヤは破壊される場合があるが、ノードが多数のワイヤを介して相互に接続されているので、通信は、セルXおよびそのワイヤの周囲で、何らかの方法で相応に方向を変更されることになるということが、1つの利点である。プラットフォームには、2つのノード間に多数の経路が存在し得るので、経路の1つが欠陥のセルまたはワイヤにより破壊されたとしても、システム内の2つのノード間には、おそらく常に異なる経路が存在することになる。このように、ノードを接続する多数のワイヤにより、動的な通信を行うことができ、それによって、経路の1つのワイヤが切断されるとしても、通信のフローは、代替の経路を発見することができる。
【００２９】
コンバータが、DNA言語からのキーワードを、バイナリDNAコードに変換するために使用されるということが、さらなる利点である。
【００３０】
先行技術文献である、Mangeら: Towards Robust Integrated Circuits - The Embryonic Approachは、コンパイラを開示しているが、一方で、本発明のシステムでは、コンバータプログラムが開示されており、本出願では後で詳細に説明されるように、それはコンパイラとは異なる。Mangeら: Towards Robust Integrated Circuits - The Embryonic Approachで開示されるシステムは、DNA言語をコンパイルするために、プラットフォームまたはネットワークの構造に関する知識を必要とし、このシステムは、あらゆるセルに対し、その機能が何であるかを通知し、したがって、このシステムは、システムの組織を開示し、そこでは、各セルは他のセルと関連している。このことで、システムが非効率になる。
【００３１】
上記とは対照的に、本発明のシステムは、より高いレベルで、例えば抽象のレベルで動作し、セルの構造および組織の代わりに、セルの機能性と関連するということが、1つの利点である。したがって、本発明のシステムは、DNA言語を変換する前に、ネットワークまたはプラットフォームの構造の知識を利用せず、すなわち必要とせず、それによって、システムは十分に自律的である。
【００３２】
Mangeら: Towards Robust Integrated Circuits - The Embryonic Approachでのシステムは、このシステムが十分に自律的でないために、コンパイルの際には、コンピュータを必要とする。したがって、Mangeら: Towards Robust Integrated Circuits - The Embryonic Approachでは、セルの機能、および、ネットワークもしくはプラットフォームの構造は、コンパイルが実行される前に必要であり、コンパイルの後に得られる結果は、マップおよびセルの機能である。
【００３３】
したがって、変換が実行され得る前に、セルの機能のみが必要とされ、変換の後に得られる結果は動的マップであるということが、本発明のシステムの1つの利点である。
【００３４】
システムが、再設定可能なハードウェアプラットフォームを備えるということが、1つの利点である。一部の先行技術文献は、FPGAシステムを使用することを開示するが、オーバーヘッドが、FPGAシステムにとって対処するには大きすぎる場合があり、したがって、そのようなシステムが、実際には使用されない場合がある。しかしながら、本発明の再設定可能なハードウェアプラットフォームは、大量のデータに対処し、それを管理することができ、したがって、実際に使用され得る。
【００３５】
ハードウェアユニットすなわちセルは、システムの一部であり、セルはプラットフォーム上に物理的に配置され、したがって、セルもまた、プラットフォームの一部であるとして定義され得る、すなわち、システムはセルを備え、または、再設定可能なハードウェアプラットフォームは、セルとして定義される複数のハードウェアユニットを備える。
【００３６】
再設定可能なハードウェアプラットフォームと、セルとして定義される複数のハードウェアユニットと、DNA言語からのキーワードを、バイナリDNAコードに変換するように構成されるコンバータプログラムとを備えるシステムが開示される。
【００３７】
コンバータプログラムは、コンバータプログラムの代わりにコンバータ手段として示されてもよく、明らかに、コンバータ手段は、構造的な特徴であり得る。あるいは、コンバータプログラムの代わりに、システムは、コンバータプログラムがそこに記憶される記憶媒体を備えることができ、または、システムは、コンバータプログラムを実行するように構成される処理手段を備えることができる。
【００３８】
さらには、システムは、プログラムコード手段が処理手段により実行されるときに、DNA言語からのキーワードを、バイナリDNAコードに変換するステップを、処理手段に実行させるように構成される、実行可能なプログラムコード手段を備えるコンピュータプログラムがそこに記憶される記憶媒体を備えることができる。
【００３９】
あるいは、システムは、プログラムコード手段が処理手段により実行されるときに、DNA言語からのキーワードを、バイナリDNAコードに変換するステップを、処理手段に実行させるように構成される、実行可能なプログラムコード手段を備えるコンピュータプログラムを実行するように構成される処理手段を備えることができる。
【００４０】
上述のシステムは、個別セットアップとして定義され得る。
【００４１】
DNA言語として定義されるプログラミング言語は、ユーザにより定義されるアルゴリズムを使用して具体化される。
【００４２】
提供されるシステムは、容易にプログラム可能な、弾力的な、生物学の影響を受けた、動的で、再設定可能な、自己組織化を行う、および自己維持を行うハードウェアプラットフォームである。
【００４３】
容易にプログラム可能な、とは、それを用いることで、実施されるべき挙動を記載し得るアルゴリズム仕様書のみを用いて、再設定可能なプラットフォームを設定することが可能であり得る、DNAすなわち電子DNA(electronic DNA)(eDNA)として定義される方法論を、システムが提供するということとして定義され得る。合成ツールまたはコンパイラは必要とされない場合があり、したがって、再設定可能なプラットフォームを設定する、容易かつきわめて高速な方法を実現する。
【００４４】
DNAおよび電子DNA(eDNA)という表現は、本出願では、同じ要旨を定義するために使用される。
【００４５】
弾力的な、とは、システムが、欠陥を検出することができ、機能性の欠陥部分をプラットフォームの別の場所で再設定することにより、それを訂正することができるため、システムは弾力的であるということとして定義され得る。欠陥は、内蔵のセルフテストまたはデータ完全性テストにより検出され得る。
【００４６】
生物学の影響を受けた、とは、システムが、生物学的なセルの影響を受けているということとして定義され得る。生物学的なセルは、DNAを解釈し、これから、組織内でのそれらの機能は何であるかを決定することができ、すなわち、セルは、自己組織化を行う。さらには、生物学的なセルは、古いセルが終えんとなるときに、新しいセルを再生させることができる。これは、組織体に自己維持を行わせる、というのは、組織体は、失われた機能性を、同じ機能性を生成する新しいセルで置換することにより、欠陥を訂正することができるためである。
【００４７】
動的で、再設定可能な、とは、単に、様々な既定の数学的機能を実行することができる演算論理装置(ALU)であってよい、再設定可能なコアを、セルが含むことができるということとして定義され得る。セルは、選択信号を変化させることにより、ALUの機能を変化させることができる場合があるので、システムは、動的で、再設定可能である。
【００４８】
自己組織化を行う、とは、上述のように、実施されるべき挙動を記載し得る電子DNAを、ハードウェアセルが解釈することができるということとして定義され得る。セルがDNAを解釈することができるという独特の方法のため、それらは、システム全体の中でのそれらの機能は何であるか、他のセルがどのような機能を有するかなどを決定することができる。セルにより必要とされるすべての情報は、DNAから決定され得る。自己組織化により、システムは、それ自体を初期化し、DNAを解釈する。
【００４９】
自己維持を行う、とは、ハードウェアセルは、その内部で欠陥が発生したかどうかを検出することができる場合があるということとして定義され得る。欠陥が発生したことを検出したならば、セルは最期となる場合がある。他のセルは、これを認識する場合があり、それらは、終えんとなったセルが有していた機能性を、ハードウェアプラットフォーム上の別の場所に移動させるために、DNAと同様に、システムに格納される情報を利用することができる。自己維持により、システムは、システム内の欠陥を訂正する。
【００５０】
ここで提供されるシステムのハードウェアプラットフォームは、半導体デバイスのモデルとなり得る。
【００５１】
システム内のセルの機能は、それが実行しなければならない活動であってよい。第2のセルが第1のセルの機能を引き受けるとき、第2のセルは第1のセルの機能を継承する。
【００５２】
一部の実施形態では、各セルは、演算論理装置(ALU)、ランダムアクセスメモリ(RAM)を備え、それによって、セルは複雑なメモリ機能に対処することができ、かつ、各セルは、ネットワークアダプタを備える。
【００５３】
一部の実施形態では、セルは、言語パーサのように動作するように構成され、それによって、DNAコードのみが、システムの自己組織化および自己維持を実行するために使用される。
【００５４】
この実施形態の利点は、DNAコードのみが、システムを初期化かつ修復するために使用され、自己組織化および自己維持は、セル間の通信に依存しないということである。ネットワークの構造およびアルゴリズムは、本説明でより詳細に説明されるように、セルが言語パーサのように動作することができるということを実現する。例えば、セルは、言語であるDNAから直接、機能性に関する情報を導出し、他のセルは、情報を提供するためには使用されず、それによって、各セルはそれ自体が、その機能性およびそれ自体のセットアップを実施する責任を負う。セルはレジスタに分化せず、したがって、セル内のメモリまたは記憶域またはレジスタを除いて、レジスタは使用されない。
【００５５】
一部の実施形態では、システムは、システム内の1つまたは複数の変数を含む表である、少なくとも1つのデータ回復センタ(data recovery centre)(DRC)をさらに備え、DRCは、少なくとも1つのセルが、DRCになるために分化することにより生成される。
【００５６】
この実施形態の利点は、データ回復センタ(DRC)は、システム内のエラーが修復され得ることを可能にするということである。DRCは、追加的な安全対策として機能する。DRCは、システム内の様々な変数は何であるかのトラックを保存する表である。1つのセルは、1つのDRCに分化することができる。システム内に2つ以上のDRCが存在する場合があり、したがって、DRCの数は、DRCになるために分化したセルの数に対応する。DNAでの式が変数の値を変化させるとき、例えば、a=b+cにおいて「a」の値が変化するとき、この値は、関連するセルに、および、例えば2つのDRCに通知され、これらのDRCは、それぞれがコピーを維持する、すなわち、それによって、さしあたり正しい値である値の2つの同様のコピーが維持される。これにより、結果として、第1のセルが終えんとなるならば、第2のセルが第1のセルの機能を引き受ける、または継承するとき、第2のセルは、DRCに、どの値が正しいかを問い合わせることになる。さらには、これは、DRCに、そのデータがRAMセル内に配置されているトラックを保存する機会を提供する。DRCの追加によって、システムはより堅牢であるという結果になる、というのは、RAMセルが終えんとなる場合に、システムは崩壊しないためであり、というのは、値は、DRCを用いて再生され得るためである。
【００５７】
この実施形態のさらなる利点は、DRCを有することにより、レジスタセルはシステムにとって不要になり、さらには、これが、終えんとなったレジスタセルを有するリスクを除去するということである。
【００５８】
先行技術文献である、Mangeら: Towards Robust Integrated Circuits - The Embryonic Approachは、データ回復センタを開示せず、上述のような本発明のシステムでは回避される、論理、コピーなどの複製のみを開示する。
【００５９】
一部の実施形態では、セルは、システム内の他のセルからの、およびこの他のセルに、情報を要求かつ送信する。
【００６０】
この実施形態の利点は、セルが相互に通信することにより、情報がシステム内に分散するということである。
【００６１】
この実施形態によるシステムは、協調型セットアップ(cooperative setup)として定義され得る。
【００６２】
一部の実施形態では、第2のセルが第1のセルの機能を引き受けたならば、第3のセルが、第2のセルの機能を引き受ける。
【００６３】
この実施形態の利点は、アクティブなセルが、終えんとなったセルの機能を確実に実行するので、すべての機能が常に実行されることになるということである。
【００６４】
一部の実施形態では、各セルは、成長パターンに従って、それが第1のセルの前に配置されているか、それとも後に配置されているかを推定し、セルが第1のセルの後に配置されているならば、セルは、それが前に有していた番号より1小さいセル番号を有するようにリナンバリングされる。
【００６５】
この実施形態の利点は、セルは、それらが終えんとなったセルの後に配置されているならば、新しいセル番号を取得し、それにより、特定の機能が特定のセル番号に関連づけられるということである。
【００６６】
一部の実施形態では、1つまたは複数のルータが、2つ以上のセルの間の通信を実現するように構成される。
【００６７】
一部の実施形態では、セルの一部が、例えばクラスタなどのネットワークオンチップ(NoC)トポロジー内に配置され、それによって、セルの一部は、1つのルータを共有するように構成され、ルータを用いてセルの一部は、他のセルと通信することができる。
【００６８】
一部の実施形態では、DNA最適化プログラムが、DNAコード内のどこに、ランダムアクセスメモリ(RAM)機能が配置されるかに関する配置決定を実現する。
【００６９】
この実施形態の利点は、セルは再組織化されてよく、その結果、例えば、RAMはすべてのセルの近くに配置され、それにより、システムはより高速に動作することができるということである。
【００７０】
一部の実施形態では、並列構文として定義されるDNA構文が、システムの独立した部分が並列に実行されることを実現するように構成される。
【００７１】
この実施形態の利点は、並列実行により、アプリケーションがより高速に動作することができるということである。並列実行は、図4に関連してより詳細に説明されるように、開始信号を分割することにより得られ得る。
【００７２】
一部の実施形態では、並列構文は、セルが、独立した並列部分を並列に成長させることを実現するように構成される。DNAプログラムコードの2つ以上の部分が、並列構文により囲まれるならば、それにより、セルが、これらの独立した部分を並列に成長させることが可能になる。
【００７３】
一部の実施形態では、セルは、ゲートレベルよりも高いレベルの論理粒度(logical granularity)で、機能を実施するように構成される。
【００７４】
この実施形態の利点は、これによって、セルがただ1つの、例えば単純な機能を有するということの代わりに、各セルが、複雑な機能を実行するように構成されるということである。これは、トランジスタが、論理構成要素にまとめられることにより実施される。このように、1つのセルは、例えば、1つの論理機能を単に実行する代わりに、ANDおよびORなどのいくつかの論理機能を実行することができる。これによって、複雑なDNAコードを実施することが、より容易に、より高速に、およびより少ない電力で可能になり得る。
【００７５】
一部の実施形態では、リップルキャリー加算器(RCA)が、1つのセルのみを占有する。
【００７６】
この実施形態の利点は、リップルキャリー加算器が、より多数のセルを占有する代わりに、単に1つのセルを占有するときに、システムがより高速に動作することができるということである。
【００７７】
一部の実施形態では、セルは、機能的な方法でDNAコードを解釈するように構成され、それによって、DNAコードが表現する各機能は、1つのセルに配置される。
【００７８】
この実施形態の利点は、構造的な方法ではなく、機能的な方法でDNAコードを解釈するときに、1つの機能を複数のセルに配置する代わりに、2つ以上の機能が、ただ1つのセルに配置され得るということである。
【００７９】
一部の実施形態では、ガードセル(guard cell)として定義される1つのセルが、ガーディアン回路(guardian circuitry)の機能を実行する。
【００８０】
この実施形態の利点は、例えば4つのガードセルを使用する代わりに、ただ1つのセルが、ガードセルとして使用されるということである。
【００８１】
一部の実施形態では、DNAコードは、複数の<statements>を実施するように構成される。
【００８２】
この実施形態の利点は、システムが、例えば<if>および<while>のタイプの複数のステートメントを解することができるとき、システムは、所望のように動作し、さらには、より高速に動作することができる。<statement>という表現、すなわち、イタリック体を用いた山形かっこ内の単語のステートメントは、本説明で後でより詳細に説明されるように、この表現が、DNA言語でのステートメントを示すということを意味する。
【００８３】
本発明は、上述の、および後述のシステム、ならびに対応する方法、デバイス、ならびに/またはプロダクト手段を含む様々な態様に関するものであり、それぞれが、最初に述べられる態様に関連して説明される、1つまたは複数の利益および利点をもたらし、それぞれが、最初に述べられる態様に関連して説明される、および/または添付の特許請求の範囲で開示される実施形態に対応する、1つまたは複数の実施形態を有する。
【００８４】
特に、本明細書で開示されるのは、再設定可能なハードウェアプラットフォームと、セルとして定義される複数のハードウェアユニットとを備えるシステムの、自己組織化および自己維持を実現する方法であって、
この方法は、
-  DNA言語として定義されるプログラミング言語で表現されるプログラムを実施することにより、システムの自己組織化および自己維持を実現するために、セルの1つまたは複数をプログラミングするステップであって、各セルは、システム内の1つまたは複数の他のセルと通信するように構成されるステップと、
-  コンバータプログラムにより、DNA言語からのキーワードを、バイナリDNAコードに変換するステップと、
-  DNAコードを、セルの1つまたは複数に送信するステップであって、1つまたは複数のセルのそれぞれは、システム内でのその機能を決定するように構成されるステップと、
-  第1のセルで欠陥が発生し、第1のセルがその機能を実行することを停止するならば、情報をセルに送信するステップであって、それによって、自己維持がシステムにより実行されるステップと、
-  第2のセルが第1のセルの機能を引き受けることを実現するために、自己組織化を再び実行するステップと
を含む。
【００８５】
上述の、および後述の方法の特徴は、ソフトウェアで実施され、データ処理システム、または、コンピュータが実行可能な命令の実行により発生する他の処理手段で実行され得る。この命令は、RAMなどのメモリに、記憶媒体から、または別のコンピュータから、コンピュータネットワークを介してロードされるプログラムコード手段であってよい。あるいは、説明される特徴は、ソフトウェアの代わりに、またはソフトウェアとともに、ハードウェアに組み込まれた回路により実施されてもよい。
【００８６】
本発明の上述の、および/または追加の目的、特徴および利点は、添付図面を参照して、本発明の実施形態の後述の例示的かつ非限定的な詳細説明により、さらに解明されることになる。
【図面の簡単な説明】
【００８７】
【図１ａ】本発明のシステムによるプラットフォームの例を示す。
【図１ｂ】本発明のシステムによるプラットフォームの例を示す。
【図２】DNAコードがどのようにセルに送信され得るかの例を示す。
【図３】セルがどのように組織化され得るかを示す。
【図４】図４ａ〜図４ｅは、DNAプログラミング言語構造がどのようにハードウェアブロックに翻訳されるかの例を示す。
【図５】図５ａ〜図５ｂは、セルがどのようにガードを実施することができるかを示す。
【図６】図６ａ〜図６ｂは、自己維持がどのように実行され得るかを示す。
【図７】自己組織化がどのように実行され得るかを示すフローチャートである。
【図８】自己維持がどのように実行され得るかを示すフローチャートである。
【図９】DNAプログラミング言語からのキーワードが、どのように対応するバイナリコードに翻訳され得るかを示す表である。
【図１０】図１０ａ〜図１０ｄは、欠陥の際の、本発明のシステムと比較した先行技術による通信の例を示す。
【発明を実施するための形態】
【００８８】
以下の説明では、本発明がどのように実施され得るかを実例として示す、添付図面に対する参照がなされる。
【００８９】
図1は、本発明のシステムによるプラットフォームの例を示す。図1aは、いくつかのセル101が配置されるネットワークオンチップ(NoC)104としてのプラットフォームを示す。
【００９０】
図1bは、いくつかのセル101、いくつかのルータ102、および、セル101とルータ102とを接続するいくつかのリンク103を備えるプラットフォームを示す。セルは処理ユニットであり、それらのそれぞれは、いくつかの数学的演算を実行し、DNAプログラミング言語を、図4に示されるハードウェアブロックに翻訳することができる。セルはさらに、計算ユニット、異種計算ユニットなどとして示され得る。セル101は、再設定可能であってよい。各セル101は、プラットフォーム上のいくつかの他のセル101と通信するように構成される。これは、ルータ102を使用することにより実現されてもよい。各セル101は、1つまたは複数のリンク103により、1つまたは複数のルータに接続される。さらには、各ルータ102は、1つまたは複数のリンク103により、1つまたは複数の別のルータ102に接続され得る。このように、ルータ102およびリンク103は、個別のセル101の間の通信手段を提供する。ルータ102は、データおよび情報の経路指定および転送を実行することができる。リンク103は、ワイヤであってよく、それにより、データおよび情報は、セル101とルータ102との間で、または、ルータ102とルータ102との間で送出され得る。
【００９１】
図1に示されるNoCトポロジーは、2Dメッシュであるが、例えば、クラスタベースの2Dメッシュ、2Dハイパーメッシュ、3-ary 2-cubeプラットフォームなどの、他のデザインの通信媒体も使用され得る。NoCは、ノードの間でデータを搬送するためにルータまたはスイッチを使用するデータ媒体として定義されてよく、ノードは、セルおよび/またはネットワークのルータであってよい。
【００９２】
生物学でのDNAは、すべての組織体の遺伝情報である。同様に、電子DNAは、すべてのハードウェア組織体(hardware organism)の遺伝情報として定義される。ハードウェア組織体は、実施されるべきアプリケーションとして定義される。本発明のシステムでの電子DNAは、プログラマにとって、デバイスをプログラミングすることについて理解するのが容易な方法、および、それを利用する、基礎となるハードウェアプラットフォームを提供する。
【００９３】
DNAは、それが疑似コードのようなプログラミング言語の形式をとるため、プログラマにとっては、理解するのが容易である場合がある。DNA言語のバッカス-ナウア記法(BNF)の記法は、このように示される場合がある。
【００９４】
dna ::= <statement>*| <parallel>*
statement ::= <assignment>| <while>| <if>| return <var>
parallel ::= parallel <statement>* endparallel
assignment ::= <var> = <exp>
while ::= while <bexp> do
<statement>* endwhile
if  ::= if <bexp> then
<statement>* else
<statement>* endif
exp  ::=<var/c> [<op> <exp>]*
bexp ::= <var/c> [<bop> <bexp>]*
op   ::=AND| OR|XOR|NOR|XNOR|NAND| +| -|...
bop  ::=AND|OR|XOR|NOR|XNOR|NAND| <| <=| ==|!=
var  ::= Letters{A-Z}*|RAM <var/c>
var/c ::= Letters{A-Z}*| <const>
const ::= Numbers(0-9)*
【００９５】
すべての論理演算子はビットワイズであり、<bop>での論理演算子は、1ビット入力を想定する。forループは存在しないことに留意されたい。これは、forループはwhileループの特別な場合であり、したがって、それは不要であってよいためである。このDNAを使用することにより、プログラマは、プラットフォーム上で動作するアプリケーションを、手早く容易に作成することができる。
【００９６】
プログラマは、上記のDNA言語を使用してコードを記述するだけでよく、そうすれば、セルが残りを処理することになる。
【００９７】
図2は、「DNA」コードがどのようにセルに送信され得るかの例を示す。
【００９８】
アルゴリズム206は、「DNA」プログラミング言語で記述される。次いで、アルゴリズム206は、コンバータプログラム207により、バイナリ「DNA」コード208に変換され得る。アルゴリズム206のバイナリ「DNA」コード208への変換により、ハードウェアがコードを解釈することができるようになる。次いで、「DNA」コード208が、プラットフォーム上のセル201に送信され得るとともに、個別のセル201が、それらのそれぞれの機能をアルゴリズム206内で発見する。図2では、セル201の7つが、機能「Func1」〜「Func 7」209を、送信された「DNA」コードから取得したことが示され、セルの2つが、「空」210であることが示される。これらの空セルは、欠陥が発生する、例えばセルが終えんとなる場合に、自己維持のために使用され得る、プラットフォーム内のセルである。
【００９９】
DNAは、セルがDNAを解釈するために使用することができる翻訳のモデルによって、基礎となるプラットフォーム、すなわちセルにとっては、理解するのが容易である場合がある。ソフトウェアコードをハードウェアブロックに翻訳する方法の例は、図4で確認され、そこでは、様々なタイプのコード、および、それがどのように翻訳されるかが提示される。
【０１００】
図4は、ソフトウェアコードがどのようにハードウェアブロックに翻訳され得るかの例を示す。
【０１０１】
図4aは、並列処理がどのようにハードウェアで実施され得るかを示す。2つのステートメントS1およびS2は、同じ開始信号「start」により開始され、それにより、並列処理を実行し、それによって、2つの終了信号「finish1」および「finish2」が生成される。
【０１０２】
図4bは、数式がどのように、協調型セットアップに従って実施され得るかの例を示す。開始信号「start」は処理を開始し、式「EXPR」からの結果はレジスタに転送され、終了信号「finish」が生成される。
【０１０３】
図4cは、数式がどのように、個別セットアップに従って実施され得るかの例を示す。開始信号「start」は処理を開始し、式「EXPR」からの結果は、いくつかのデータ出力「data」として転送され、終了信号「finish」が生成される。
【０１０４】
図4dは、ifステートメントがどのように実施され得るかの例を示す。2つのANDゲート402およびNOTゲート403により、S1およびS2での式がどのように評価されるべきかが決定される。ガードは、入力として、開始信号「start」、および、ブール式「BOOL」からの出力を受け取る。終了信号「finish」は、1つのORゲート404により制御される。終了信号は、S1またはS2のいずれかから来る信号となり得る。
【０１０５】
図4eは、whileステートメントがどのように実施され得るかの例を示す。2つのANDゲート402、ORゲート404およびNOTゲート403により、S1での式が評価されるべきかどうか、およびいつ評価されるべきかが決定される。S1からの出力は、開始信号「start」とともに入力信号として使用され、ブール式「BOOL」は出力信号を提供し、終了信号「finish」が出力される。
【０１０６】
開始/終了信号は、実行の順序が維持されることを確実にするシーケンサとして動作することができる。それは、DNAから、これらのハードウェアブロックに対して、以下のステップ、すなわち、
-  ステートメントのタイプ、すなわち、代入、ifまたはwhileを識別するステップ
-  代入のタイプに関連するブロックを配置するステップ
を実行することにより得ることは容易である。
【０１０７】
しかしながら、ブロックがどのように配置されるかは、後の項で説明されることになるような多数の方法でなされ得る。
【０１０８】
したがって、セルは、様々な機能を実施し、それらの、いわゆるセルタイプは、EXPR、BOOL、IF-G(ifガード)、W-G(whileガード)、およびPARであってよい。EXPRおよびBOOLは、図4aでのEXPR、および図4b、4cでのBOOLとしても確認されるように、eDNA言語の<exp>および<bexp>の部分を実施する。IF-GおよびW-Gは、ガードと呼ばれる、塗られた箱により特徴づけられる図4b〜4dでの部分である。最後に、PARは、コードの2つの並列な部分を連結する役割を果たすセルタイプである。BOOLのセルタイプは、セルおよび配線を節約するために、IF-GおよびW-Gに統合される場合がある。
【０１０９】
図3は、セルがどのように組織化され得るかを示す。セル301は、DNAコードにより指示される処理タスクを実行することができる中央処理装置302、DNAコードからの命令、および、協調型もしくは個別のセットアップのいずれかを使用して、セルを制御するアルゴリズムを格納するためのランダムアクセスメモリ(RAM)303、ならびに、例えばルータおよび他のセルなどの、ネットワーク内の他のユニットと通信するために使用されるインターフェースユニットであるネットワークアダプタ304を備えることができる。
【０１１０】
ハードウェアセルは小型のプロセッサであり、それに対して提供されるDNAを解釈すること、および、他のセルにより提供される情報に対処することが可能である。セルの制御は、記憶域内に配置される単純な命令として表現され得るアルゴリズムにより対処される。セルは、それが、何らかの数学的機能を実行することができるALUを含むという意味で、再設定可能である。それがどの機能を実行するかは、選択信号による。この選択信号の値を変化させることにより、セルが、ハードウェアプラットフォームに対して別の機能を実行するように再設定することが可能になり得る。これは、セルが表現することができる数学的機能の数を、限定することができる。DNAにより指定される挙動を実施する責任があるのは、セルである。これは、多数の方法でなされ得る。本発明のシステムによるセルは、それを機能的な方法で実施する。この方法では、セルのALUは、「加算」「論理シフト」「比較器」などのような、より高いレベルの機能を含む。
【０１１１】
プロセッサおよびALUだけでなく、セルはさらに、セルとその環境との間のインターフェースに対処するユニットを含むことができる。
【０１１２】
セルが相互に通信するために、それらは、何らかの種類の媒体により接続される必要がある場合がある。その媒体は、ネットワークオンチップであってよい。
【０１１３】
したがって、インターフェースユニットは、近くのルータとの通信に対処するネットワークアダプタであってよい。そのトポロジーは、例えば単純な2Dメッシュであってよい。
【０１１４】
自己組織化は、このシステムでの特徴であり、プラットフォームを再設定し、DNAにより指定される機能を実行する準備ができていることを確実にする。自己組織化は、完全に制御され、セルにより実行され得るとともに、ユーザの介在は、必要とされなくてもよい。さらには、自己組織化は、中央集権的な「賢人」により制御されることとは対照的に、分散処理であってよく、したがって、単一障害点を有するリスクが除去される。
【０１１５】
自己組織化を実施する多数の方法が存在する。以下では、2つの方法が説明されることになる。自己組織化の一部のステップは、両方の方法に対して共通である。自己組織化に対する以下の基本的なアルゴリズム、すなわち、
-  DNAを受信する
-  それをメモリに保存する
-  2つの方法に対して共通ではない、自己組織化を実行する
-  「自分が最後である」かどうかを判定し、これが事実であるならば、関連する当事者に、自己組織化が終了したということを通知する
-  実行を開始する
は、システム内の単一のセルの観点から説明される。
【０１１６】
自己組織化のステップでは、セルは、以下のもの、すなわち、
-  以下ではfuncと略される、例えばガード、演算子、RAMなどの、セルの機能
-  以下ではoutsと略される、セルがその出力を送出することになるセルの座標
-  以下ではauxと略される、自己維持のために必要とされる補助変数
を決定しなければならない場合がある。
【０１１７】
以下で説明される2つの方法は、次のように定義される。
-  協調型セットアップ:セルは、「私はここにいます。あなたの出力を私に送出してください。」などのような情報である、システムに関する情報を協調的に交換する。
-  個別セットアップ:セルは、セルの終えんの通知を除いて、すべての情報をDNAから導出することができる。セルの終えんは、システム内の欠陥として定義される。
【０１１８】
2つの方法は、以下で詳細に説明される。
【０１１９】
まず、個別セットアップが説明される。
他のセルが情報を提供することを助ける協調型セットアップとは対照的に、個別セットアップでは、必要とされ得るすべての情報は、DNA、すなわち、例えば、本説明で前に開示された言語のBNF記法により記述されるDNAプログラムから直接導出される。個別セットアップの目的は、セルのネットワーク(NoC)および他のセルの機能性をなぜ当てにするのか、各セルがそれ自体で、それ自体のセットアップに責任を負う場合に、同じ機能性がいつ実現され得るのか、ということである場合がある。個別セットアップと協調型セットアップとの間の重要な違いは、個別セットアップはレジスタを使用せず、したがって、実行時間中に、低速のデータプルプロトコルを有する影響を除去するということである。個別セットアップは、以下のアルゴリズムにより特徴づけられ得る。
【０１２０】
Algorithm void selfOrganisation(DNA dna, Coord id){
int MyNr = getCellNr(id);
func = find_gene(MyNr,dna);
setFunc(func);
determine_outputs(func,dna);
determine_GS _source(id,dna,func);
}
Algorithm String find_gene(int nr,DNA dna){
int dnai = 0;
int count = 0;
ignorevars.clear();
ignoreRAM = false;
while (dnai < dna.getTotalGeneNr()){
gene d = dna.getGene(dnai);
String kw = d.getContent(0);
boolean ignore = ignorekw(kw);
if (!ignore && count == nr){
return kw;
} 
else{
if (!ignore){
count++;
} 
else{
ignoreCount++;
} 
dnai++;
} 
} 
return "?";
}
Algorithm void determine_GS_source(Coord id, DNA dna,String funs){
while(dnai < dna.getTotalGeneNr()){
dnai++;
Gene d = dna.gene(dnai);
String t = d.getContent(0);
boolean ignore = ignorekw(t),
if (!ignore){
if (!Constants.convertToString(t). startsWith("var") &&
!t.equals(Constants.RAM) &&dnai==genenr){
//入力環境(IE)からの開始信号を要求する
OutputRegPay toad orpl = null;
if (func.eg oats Constants.lF)‖func.eguals(Constants.WHILE)){
orpl = new OutputRegPayload("GS","p1");
}
else{
orpl = new OutputRegPayload("GS","p3");
}
ID IE = new ID("IE",-1,id.getY());
Packet[] ps = {new Packet(1,new Destination(IE),
new Source(id),orpl)};
sendPackets(ps); 
//入力環境にGSをここで提供するように命じる
StartPayfoad spl = new StartPaytoad()
Packet[] ps2 = {new Packet(2,new Destination (IE),
new Source(id)spl};
sendPackets(ps2);
break;
}
else if (!Constants.cnvertToString(t).startsWith("var") &&
!t.equals(Constants.RAM) & & dnai != genenr){
break;
}
}
}
}
【０１２１】
find_geneアルゴリズムの目的は、セルに割り当てられるセル番号を使用して、このセルが表現することになる遺伝子をDNA内で探し出すことである。これは、DNAを最初から検索することによりなされ得るとともに、各遺伝子に対して、その遺伝子が「表現可能」であるかどうかを判定する。これは、生物学的なタンパク質合成におけるRNAポリメラーゼと類似点がある。遺伝子は、それが、
-  キーワード:while、if、endifの1つ
-  RAMの最初の出現
-  任意の演算子
であるならば、表現可能であり得る。
【０１２２】
表現可能な遺伝子が発見されるたびに、カウンタが1だけインクリメントされ得る。カウンタがセルのセル番号に等しくなるとき、セルが表現することになる遺伝子が発見される。
【０１２３】
determine_GS_sourceのソースの目的は、このセルが、入力環境からの開始信号を取得することになるかどうかを決定することであり、したがって、それは別のセルからのものではない。セルが表現する遺伝子が、DNA内の、すなわち<parallel>ブロック内部の、最初の表現可能な遺伝子であるならば、これは事実となり得る。
【０１２４】
determine_outputs(func)は、他よりも複雑であり、したがって、それは、説明はされるが、疑似コードでは記述されない。その目的は、DNAにより記述されるアルゴリズムを分析し、auxを設定するだけでなく、正しいoutsを導出することであり得る。DNA言語は、4つのステートメントのタイプを含むことができる。DNA言語での<statement>を参照されたい。
-  <while>
-  <if>
-  <assignment>
-  return <var>
【０１２５】
<while>および<if>ステートメントは、非常に類似しているので、<while>のみが説明されることになる。以下では、詳細に関しては図4を参照されたい。
【０１２６】
whileステートメントを読み出す最初のセルは、whileガードである場合がある。このwhileガードは、先行のステートメントが処理する、先行のステートメントからの開始信号を受信し、ブール式が処理する、ブール式の結果を受信することを確実に行うことになり、最後に、whileガードは、その開始信号を、whileステートメントに含まれるステートメント、および、whileステートメントの直後のステートメントに提供することができる。ブール式がいくつのセルを占有するかを計算することにより、whileガードは、その出力を、whileステートメントに含まれるステートメント、および、whileステートメントの直後のステートメントにリンクすることができる場合がある。
【０１２７】
DNA内のwhileキーワードの後のブール式は、それが、その出力を、その関連するガードに提供することを確実にするようにすることができる。これは、関連するガードがブール式の開始部分の直前のセルであるので、非常に容易であり、したがって、計算し、かつoutsに保存することは容易である。
【０１２８】
代入は、もう少し複雑である場合がある。代入を生成するために、各式は、その出力を、それが計算する変数を必要とするすべてのセルに送出してもよい。それは、DNAを読み出し、この式が計算する変数を含む式に対して、出力をリンクするということであり得るので、これらの座標は容易に発見することができるものであり、したがって、それは、言語パーサに類似し得る。さらには、式は、それが計算する変数が、return <var>ステートメントの1つの中にあるならば、それらの出力をシステムから送出することもできる。
【０１２９】
以下では、協調型セットアップが説明される。
【０１３０】
協調型セットアップでは、セルは、システムの組織化を相互に援助する。この方法の目的は、func、outsおよびauxを確立することに関して、より多くのセルが協調して相互に援助するならば、ならびに、導出が誤っているとしたらどうなるかという問題に対処するならば、より多くのセルが正しくなるという可能性が、より高くなり得るということである。協調型セットアップの基本的な考え方は、個別セットアップと同じであり、すなわち、セルはまず、その機能を決定しなければならないということである。これは、2つの方法、すなわち、(i)セル自体による「半」導出処理としてか、(ii)それが別のセルにより命じられるためかのいずれかで起こり得る。前のセルが、セルに対して、それがどこからDNAを読み出すことになるのかをそれに伝えるパケットを送信する場合があるので、(i)の半導出処理は「半」と呼ばれ、したがって、導出処理は、実際には、DNAを分析する複数のセルの結果である。さらには、(ii)によれば、セルはさらに、ある機能に分化するようにそれに命じる命令を受信する場合があり、その機能は、その命令で指定されている。これは、例えば、ifまたはwhileステートメントが、前のセルにより読み出されるときに起こり得るものであり、次いで、前のセルは、受信セルに、パケットに記述されるブール式に分化するように命じるブール式パケットを送出することができる。個別セットアップとは反対に、協調型セットアップでのセルは、他のセルへ/からのパケットの送出/受信と同様に、それら自体の機能の分化に対して、部分的にのみ役割を果たす場合がある。セルのタイプに応じて、セルはさらに、他のセルに対して、受信セルの出力を要求する出力要求パケットを送出することができる。これは、例えば、whileガードからの開始信号を要求する、whileステートメント内部のステートメントである場合がある。whileステートメント内部のセルは、whileガードがどこにあるかを知っている、というのは、この情報は、ステートメントを「生成する」パケットに保存されるからである。したがって、セルは、DNAから多くを導出する必要はなく、むしろ受信したパケットから導出することになる。出力要求の受信に際して、入力通知パケットは、パケットの送信元に返送される場合があり、それにより、出力要求
者はさらに、それがどの入力を取得するかのトラックを保存することができ、したがって、「入出力情報冗長性」を生成し、それが自己維持の際に使用され得ることに留意されたい。このように、他のセルに/から情報を要求かつ送出する役割を果たすのは、他のセルである。
【０１３１】
自己維持の目的は、システムが実施するアプリケーションを維持することである。これは、2つの段階、すなわち、
(1)欠陥を検出する、および
(2)システムの利用可能な部分を再プログラミングすることにより訂正する
を含むことができる。
【０１３２】
第1の段階(1)は、完全にハードウェア依存である場合があり、内蔵のセルフテスト技術およびデータ完全性テストを当てにする場合がある。第2の段階(2)は、セル内に含まれるアルゴリズムにより制御され得るものであり、以下で説明されることになる。
【０１３３】
図6は、自己維持がどのように実行され得るかを示す。ネットワーク内の各セルは、例えば「セル1」のようなセル番号、およびアドレス、位置、場所などでも示され得る座標点を有する。ネットワークは、2Dメッシュとして示される。この2Dメッシュでの座標点は、(行、列)により示される点の形式であり、ここで、「行」は、セルがどの行番号に配置されているかを示し、「列」は、セルがどの列番号に配置されているかを示す。例えば、「セル1」は、プラットフォームの座標点(0、0)に配置されている。他のプラットフォームの形状およびアドレススキームもまた使用され得る。個別のセルは、機能「Func」を実施する場合があり、または、空である場合がある。
【０１３４】
図6aは、セルの終えんの形での欠陥の前に、システムがどのように動作することができるかを示し、図6bは、自己維持が実行された後で、システムがどのように動作することができるかを示す。図6bでは、座標点(0、2)でのセルが終えんとなったことが理解される。セルが終えんとなった前は、このセルは、図6aではセル3であった。セルが終えんとなる後では、図6bで見られるように、それは、もはやセル番号を有しない。その代わりに、終えんとなったセルの直後に配置されているセル、すなわち、次の座標点のセルが、終えんとなったセルが、それが生きていたときに有していたセル番号を取得し、すなわち、図6aでのセル4が、今度は図6bでセル3になる。すべての後続のセル、すなわち、より高い座標点を有するセルもまた、直前のセルが有していたセル番号でリナンバリングされることになる。すなわち、図6aでのセル4が、図6bではセル3であるなどである。セルの機能「Func」は、セル番号の変化とともに変化し、すなわち、図6bでの新しいセル3は、図6aでの古いセル3から、機能「Func 3」もまた継承する。したがって、図6aでのセル7、セル8およびセル9の空セルは、図6aでのセル3が終えんとなる後で、機能を有するセルとなるように形成され得る。図6aでの古い空セル7は、図6bでは、新しいセル6であり、したがって、それは、図6aでの古いセル6の機能「Func 6」を継承する。このように、終えんとなったセルの前に配置されているセルは、それらのセル番号および機能を維持するが、一方で、終えんとなったセルの後に配置されているセルは、それらのセル番号および機能番号が1だけ減少する。
【０１３５】
第2の段階(2)は、個別セットアップおよび協調型セットアップそれぞれに関して、それぞれ以下で説明されることになる。
【０１３６】
まず、それは、個別セットアップに関して説明されることになる。個別セットアップに関する利点の1つは、それは、自己維持を制御するために異なる組のアルゴリズムを使用する協調型セットアップとは対照的に、自己組織化を制御するために使用されるアルゴリズムとまさに同じアルゴリズムを、自己維持を制御するために使用するということである。これは、個別セットアップが、アルゴリズムを保持するために、より小さな記憶域を必要とすることがあるということを意味する。欠陥が発見されるならば、ルータは、これに関して入力環境に警告することができ、次いで、すべてのセルにセル終えん信号を送出して、セルの終えんが発生したことを通知することができる。セルは、成長パターンに従って、それらが終えんとなったセルの前に配置されているか、それとも後に配置されているかを、迅速に推定することができる。成長パターンは、アルゴリズムがどのようにプラットフォーム上に配置されるかを決定する規則として定義され得る。セルが、終えんとなったセルの後に配置されているならば、それは、selfOrganisationアルゴリズム内のgetCellNr(id)関数により使用され得るdeadcellカウンタを増加させることができ、これは、自己組織化アルゴリズムを再開させる。deadcellカウンタを更新することは、終えんとなったセルの後に配置されているセルが、それが前に有していた番号より1小さいセル番号を自動的に取得するという効果を有する。これは、それが、その1セルだけ後側の隣のセルが有していたような機能を取得することになり、したがって、それ自体をきわめて容易な、高速な、かつ楽な方法でコピーするということを意味する。終えんとなったセルは、その位置に残っており、それにより、それが有する座標点は、引き続き終えんとなったセルに属する。その結果、終えんとなったセルの後に配置されているセルは、それらが前に有していた番号より1小さい、新しいセル番号を取得するが、すべてのセルは、それらの座標点に残っている。このように、セル番号、およびそれによって、終えんとなったセルの後に配置されているセルの機能は、1座標点だけ増加される。
【０１３７】
セルが、終えんとなったセルの前に配置されているならば、それは、そのoutsをチェックして、そのoutsに含まれる何らかの座標が、終えんとなったセル自体またはその後を指すかどうかを確認する。終えんとなったセル自体またはその後を指すならば、終えんとなったセルの前に配置されているセルは、そのoutsが指している座標点を1だけ増加させることにより更新し、それによって、終えんとなったセルの後に配置されているセルについて、セル番号に関する座標点の増加が考慮される。その結果、これにより、システムはそれ自体を回復させた。
【０１３８】
セルが、2Dメッシュ内に配置されているならば、それらは、第1の行内には(0、0)、(0、1)、(0、2)〜のような座標、および第2の行内には(1、0)、(1、1)、(1、2)〜のような座標などを有することができ、すなわち、第1の座標は行番号に対応し、第2の座標は列番号に対応し、第1の行番号および第1の列番号は0により示される。図6を参照されたい。
【０１３９】
次に、自己維持が、協調型セットアップに関して説明される。自己維持アルゴリズムの開始は、個別セットアップおよび協調型セットアップに対して同じであってよく、すなわち、終えんとなったセルを囲むルータは、セルが終えんとなっていることを発見し、環境に警告するということである。このアルゴリズムでは、ルータは、セル終えんパケットを、終えんとなったセルの前のすべてのセルに、および、終えんとなったセルの後のセルの1つに送出することができる。終えんとなったセルの前のセルは、個別セットアップに対することとまさに同じことを、しかしながら2つの追加の(a)および(b)とともに行うことができる。つまり、(a)は、前のセルが、終えんとなったセルの座標点である、outsに含まれる座標を見つけたときはいつでも、それは、座標点を1だけ増加させることに加えて、入力通知パケットを、更新された座標点に、すなわち、終えんとなったセルの機能を引き受け、かつ継承したセルに送出することができ、その結果、入出力リスト情報の冗長性が維持され得るということである。そして、(b)では、終えんとなったセルの前のセルはさらに、それがoutsを用いて行うのと同じようにして、その入力通知リストを検索することができ、ただし、前のセルが、そのリストの中に、終えんとなったセルの座標点を発見するならば、前のセルは、更新された座標点に、入力通知の代わりに、出力要求を送出することができる。
【０１４０】
終えんとなったセルの直後のセルは、例えば個別セットアップのものに類似する手法を使用することにより、どの機能を終えんとなったセルが有していたかを推定することができる。機能が推定されると、終えんとなったセルの直後のセルは、この結果を保存し、次いで、例えば、関連する変数を含むコピーパケットを生成かつ送出することにより、成長パターンに従って、その結果自体を次のセルにコピーすることができる。次いで、終えんとなったセルの直後のセルは、最後に、それが今推定した機能に分化することができる。コピーパケットを受信するセルは、それ自体を次のセルにコピーし、それが受信するコピーパケットを読み出すことができる。
【０１４１】
以下では、システムが、どのように、およびどこで使用され得るかが説明されることになる。システムは、FPGAのような再設定可能なプラットフォームであり、ほぼ同じ方法で使用され得る。FPGAは、ハードウェア記述言語(HDL)を、FPGAの設定可能論理ブロック(CLB)にマッピングするために、合成またはコンパイラのツールを必要とする。非常に大きなデザインに関しては、これは、非常に時間がかかる処理である。一方、本発明のシステムは、DNAからキーワードを受け取り、それを対応するバイナリコードに翻訳することができる、小さなコンバータプログラムのみを必要とする。コンバータソフトウェアは、DNAからのキーワードをバイナリコードに変換するために、図9の表を使用する。
【０１４２】
キーワードおよび変数が同じ値を有しないことを確実にするために、変数は、表で最も高い値よりも高い値で符号化される場合がある。さらには、コンバータソフトウェアは、PCとハードウェアプラットフォームとを接続するケーブルと同様に、DNAをPCからセルにコピーすることができるインターフェースをさらに含むことができる。
【０１４３】
プラットフォームを用いて作業する者は、このプラットフォームを使用するために、以下のステップを行うことができる。
-  彼/彼女がプラットフォーム上で実施することを望むアルゴリズムを、DNA言語で記述する
-  DNAをバイナリDNAに変換するために、コンバータソフトウェアを使用する
-  さらにソフトウェアを使用して、DNAをプラットフォームにロードする
【０１４４】
このように、これらのステップは、FPGAを用いて作業することにかなり類似する場合がある設計サイクルであるが、FPGAと本発明のシステムとの間には、いくつかの明確な違いが存在する。
-  詳細なHDLモデルを記述するよりも、アルゴリズムを記述する方がはるかに容易である。
-  変換処理は、合成処理よりも高速である。
-  本発明のシステムによるロード処理は、FPGAよりも低速であるはずがない、というのは、それらは複雑に関連づけられているためである。
【０１４５】
以下では、DNAの構文の異なる特性が説明される。電子DNA構文は、このように指定され得る。
【０１４６】
dna :: = <statement>*|<parallel>*
statement :: = <assignment>| <while> ( <if>| return <var>
parallel ::= parallel <statement>* endparallel
assignment ::= <var> = <exp>
while ::= while <bexp> do
<statement>* endwhile
if  ::= if <bexp> then
<statement>* else
<statement>* endif 
exp   ::= <var/c> [<op> <exp>]*
bexp  ::= <var/c> [<bop> <bexp>]*
op    ::=AND| OR|XOR|NOR|XNOR|NAND| +| -|…
bop   ::=AND| OR|XOR|NOR|XNOR|NAND| <| <=| ==|!=
var   ::= Letters{A-Z}*|RAM <var/c>
var/c  ::=Letters{A-Z}*| <const> 
const  ::= Numbers(0-9)*
【０１４７】
電子DNAは、「while」、「if」、「代入」、「returnステートメント」などのような、従来のプログラミング構成体または標準構造を用いる通常のプログラミング言語に類似する。標準構造は、当業者には周知である。しかしながら、returnステートメントは、電子DNAプログラミング言語では、ソフトウェアプログラミング言語と比較すると、異なって解釈される。システム内のセルは、returnステートメントの「<var>」部分の変数は、システムの出力ピンの1つに送出されるべきであるというような形で、returnステートメントを解釈する。
【０１４８】
2つのタイプの式「exp」および「bexp」が存在し、それらはそれぞれ、式およびブール式である。これらの2つの間の違いは、ブール式は、ブール演算子を利用することができ、式は数値演算子を利用することができるということである。
【０１４９】
新しいプログラミング構造が、電子DNAを伴って導入され、これは、「並列な」ステートメントまたは構文である。
【０１５０】
<parallel>構文が、含まれ得る。これは、アプリケーションの速度を上げるために、アプリケーションの独立した部分を並列に実行することを可能にする。システムは、少なくとも速度に関心がある場合には、並列にすることでより高速になる。この<parallel>構文はさらに、セルが、<parallel>によりマークされる部分を並列に成長させることを可能にし、したがって、自己組織化処理の速度もまた上がる。これは、システムの一般的な挙動を変化させることができる、というのは、今やプラットフォームは、独立したアプリケーションを動作させることができるためである。
【０１５１】
いくつかの演算子は、<op>に含まれ得る。セルは、ゲートレベルの機能よりもはるかに高いレベルの論理粒度で、機能を実施する。これは、システムの領域および電力の使用法に大きな影響を与え得る。このように、ハードウェアプラットフォームは、「現実での」アプリケーションの観点から見ると、非常に興味深い場合がある。
【０１５２】
RAMが含まれ得ることにより、セルは、例えばアレイ演算などの複雑なメモリ機能に対処することができる場合があり、それによって、ハードウェアプラットフォームは、他の多数のアプリケーションを実行することが可能にされる場合がある。これはさらに、セルがDNAを解釈する方法に影響を与える場合がある、というのは、静的な値を有しないレジスタがアドレスとして使用されるアドレッシングであり得る、動的アドレッシングを使用することもまた可能であり得るためである。
【０１５３】
本発明のシステムによれば、セルは、DNAを機能的な方法で解釈する。しかしながら、セルはさらに、DNAを構造的な方法で解釈することができ、それによって、セルは、所与の機能的ユニットのどのビットワイズユニットもすべて、構造的に配置することができる。
【０１５４】
セルが、DNAを機能的な方法で解釈するとき、それらは、機能を1つのセルとして配置することができる。これは、DNAが表現することができる各機能が、複数のセルの代わりに、1つのセルに配置されることを意味する。これは、セルの解釈を制御するアルゴリズムに大きな影響を与える場合がある、というのは、大きな式をビットワイズでアセンブルすることは、きわめて複雑であり、したがって高コストとなり得るためである。
【０１５５】
アルゴリズムは、タイプ<if>および<while>の複数の<statements>を解することができる。
【０１５６】
ガーディアン回路は、1つのガードセルにまとめられる場合があり、それによって、ガードセルに関連するオーバーヘッドが、ガードセルがガーディアン回路全体の1つのゲートを実行する4つのセルから構成された場合と比較して、最小化される。ガードセルとして、4つのセルではなくただ1つのセルを使用することにより、ifおよびwhileのステートメントにつき3つのセルの節約となる。
【０１５７】
図5は、セルがどのようにガードを実施することができるかを示す。図5aでは、1つのセル501が、if上部ガードを実施することができ、1つのセルが、if下部ガードを実施することができる。図5bでは、1つのセルが、whileガードを実施する。
【０１５８】
本発明のシステムでは、より高い、またはより低いレベルの粒度が使用され得ることが理解される。
【０１５９】
以下では、NoCトポロジーが説明される。ネットワークでセルからセルへデータを搬送することに、必要以上に多くの時間が費やされることが研究で示された。ネットワークのトラフィックを最適化する方法は、NoCトポロジーを最適化することである場合がある。図1bは、2Dメッシュトポロジーの例を示す。
【０１６０】
それぞれが1つのルータを有する各セルの代わりに、セルのグループが、同じルータを共有してもよく、それを用いて、セルのグループは他のセルと通信することができ、したがって、セルは、いわゆるクラスタ状に配置される。これは、複数の利益を有する場合がある。
-  クラスタ内に利用可能なセルが存在するならば、セルの終えんは、対処するのが容易であり得る。
-  ネットワークは、より小さくてよく、したがって、領域および電力を節約する。
-  データは、「組織自体を通過する」必要がないので、組織対組織のデータ搬送遅延がより短い。ただし、組織は、セルの組織化として定義され得る。
【０１６１】
以下では、個別セットアップのDNA解釈スキームが説明される。これによれば、セルは、言語パーサのように動作する。これは、DNAのみが、システムを初期化かつ修復するために使用され得ることを意味する。それによって、システム内のある事象に関してセルに通知する情報を、互いの間で送出することにより、セルが協力してシステムを組織化するシステムとは対照的に、責任はNoCからセルに移される。しかし、この情報は、DNA、およびただ1つの他の情報、すなわち、終えんとなったセルの数から十分に導出され得る。したがって、自己修復は、単に、すべてのアクティブなセルに、あるセルが終えんとなったことを通知するという課題である場合があり、次いで、更新されたセル終えんカウンタを用いて自己組織化処理を再実行することができる。このように、セルは、異なるスキーム、例えば協調では、ネットワークの周囲ではパケットで搬送されなければならない情報を、自動的に取得することができる。この個別セットアップの解釈スキームは、例えば、高いレベルの論理粒度によって可能である場合がある。
【０１６２】
複数の要因が、DNAでアルゴリズムを記述するときに、影響を与える場合がある。実施されるべきアルゴリズムの性能に影響を与え得ることの1つは、レジスタおよびRAMがどこに配置されるかであり、これは、協調型セットアップに対して関連がある。配置の決定は、DNAコード内のどの点で、レジスタまたはRAMが導入されるかに関係する場合がある。DNA最適化プログラムは、大きなアルゴリズムを最適化するために実施され得る。
【０１６３】
図7は、自己組織化がどのように実行され得るかを示すフローチャートである。
【０１６４】
ステップ701では、アルゴリズムが、DNAプログラミング言語を使用して記述される。
【０１６５】
ステップ702では、このDNAが、バイナリコードに翻訳される。
【０１６６】
ステップ703では、このコードは、プラットフォーム内の少なくとも1つのセルに送出される。
【０１６７】
ステップ704では、DNAコードが、セルにより受信され、DNAコードは、それぞれのセルが、DNAのどの機能を表現することになるか、および、それが、その出力をどのセルに、セルIDに基づいて提供することになるかを決定するために、セルにより分析される。
【０１６８】
ステップ705では、システムは、DNAが十分な数のセルにより受信されるかどうかを検査する。
【０１６９】
十分な数のセルがDNAを受信したならば、ステップ706で、自己組織化は完了したと判定される。
【０１７０】
十分な数のセルがDNAを受信しなかったならば、ステップ707で、分散パターンに従うことにより、まだDNAを受信していないセルに対してDNAが送出される。
【０１７１】
図8は、自己維持がどのように実行され得るかを示すフローチャートである。
【０１７２】
ステップ801では、セル欠陥が検出されるかどうかが検査される。
【０１７３】
このセルにセル欠陥が存在するならば、ステップ802で、セルは、ルータからのウォッチドッグに確認応答することを停止する。
【０１７４】
ステップ803では、ルータは、セル終えんパケットをすべてのセルに対して中継して伝え、このパケットは、終えんとなったセルのIDを含む。
【０１７５】
ステップ804では、すべてのセルは、終えんとなったセルのIDに基づいて、それら自体のセルIDが、終えんとなったセルIDよりも高いか、それとも低いかを判定する。
【０１７６】
セルIDが終えんとなったセルIDよりも高く、自己組織化が再起動されるならば、ステップ805で、セルIDは1だけ減少される。図7を参照されたい。
【０１７７】
セルIDが終えんとなったセルIDよりも低いならば、ステップ806で、すべての出力IDがチェックされ、この出力IDは、このセルが出力を提供することになるセルである。
【０１７８】
ステップ807では、出力IDが、終えんとなったセルIDよりも高いか、それとも低いかが判定される。
【０１７９】
出力IDが終えんとなったセルIDよりも高いならば、ステップ808で、出力IDは1だけ増加される。
【０１８０】
ステップ809では、さらに多くの出力IDが存在するかどうかがチェックされる。
【０１８１】
さらに多くの出力IDが存在したならば、ステップ810では、次の出力IDもまたステップ807で検査される。
【０１８２】
ステップ809でチェックされるときに、これ以上出力IDが存在しないならば、ステップ811で、自己維持が完了する。
【０１８３】
図9は、DNAプログラミング言語からのキーワードが、どのように対応するバイナリコードに翻訳され得るかを示す表である。第1の列では、様々なキーワードが確認され、第2の列では、キーワードのそれぞれに対しての対応するバイナリコードが確認される。最後の列では、一部のキーワードが何を意味するのかの説明が確認される。
【０１８４】
図10は、欠陥の際の、先行技術のシステムでの、および本発明のシステムでの通信の例を示す。
【０１８５】
図10aおよび図10bは、先行技術のシステムでの通信の例を示し、通信はセルの間で行われる。ネットワークは固定配線であり、通信は隣接のセルの間でのみ可能である。通信が行われるのが静的な手段によるため、図10aを参照されたいが、×印により示される欠陥が、機能F4を有するセルに発生する場合は、×印により示されるように、セルF4およびセルF4を通るワイヤの両方が破壊される場合があり、それによって、システム内の通信が遮断されるようになる場合があり、したがって、システムが故障する場合がある。
【０１８６】
図10bで確認されるように、システムが自己回復を経るならば、最も右側のカラムである予備カラムが、欠陥セルF4を有するカラムを追い越し、予備カラム内のセルは、機能F4、F5およびF6が割り当てられる。しかしながら、古い欠陥F4セルの周囲のワイヤが、セルとともに破壊されたならば、図10bで×印により示されるように、これらのワイヤは断線したままであり、これによって、異常のないセルF4との通信は、×印により示されるように、断線したワイヤにより遮断される。
【０１８７】
図10cおよび図10dは、本発明のシステムでの通信の例を示す。本発明のシステムでのネットワークの動的な性質により、ワイヤの欠陥は、パッケージを経路再指定することにより許容され得る。
【０１８８】
本発明のシステムでは、通信はいわゆるノードの間で行われ、そのため、通信はすべてのセルの間で可能であり、したがって、図10cで確認されるように、機能F4を有するセルで欠陥が発生する場合は、×印により示されるように、セルF4およびセルF4へのワイヤは破壊される場合があるが、ノードは多数のワイヤを介して相互に接続されているので、システムが自己回復を経るときに、通信は、欠陥セルおよびそのワイヤの周囲で、何らかの方法で相応に方向を変更されることになる。図10dで確認されるように、最も右側のカラムである予備カラムからのセルが、欠陥セルF4の機能を割り当てられ、新しいセルF4になる。さらに図10dで確認されるように、欠陥セルでのワイヤもまた破壊されたということは、通信を遮断しない、というのは、システム内のノードにより、プラットフォームには2つのノード間に、したがってセルの間に、多数の経路が存在し、したがって、経路の1つが欠陥のセルまたはワイヤにより破壊されたとしても、システム内の2つのノード間には、おそらく常に異なる経路が存在することになるためである。このように、ノードを接続する多数のワイヤにより、動的な通信を行うことができ、それによって、経路の1つのワイヤが切断されるとしても、通信のフローは、代替の経路を発見することができる。
【０１８９】
実際に動作する、しかし本発明の現実の実施で使用されるには単純すぎるプロトタイプの例が、以下で説明されることになる。ハードウェアプラットフォームは、ネットワークオンチップ相互接続により接続される複数のXilinx PicoBlazeソフトコアからなるMPSoCであってよい。
【０１９０】
ネットワークアダプタは、1対の周辺スイッチからなってよく、それらはハンドシェーキングの後で所望の場所により設定され、データを受信するスイッチは、送信データの受信を確認する。さらには、ネットワークアダプタは、6×8ビットのレジスタ、すなわち、単一のデータグラムを格納することが可能であってよい、セル内のレジスタを含むことができる。状態機械は、シグナリング、パッケージ転送、アルゴリズムを経路指定すること、CPUインタラプトをトリガーすること、およびレジスタアクセスを制御することに対処するために使用され得る。
【０１９１】
アプリケーションを高い抽象レベルでセットアップするために、ネットワークアダプタに加えて、ソフトコアCPUが動作され得る。小さなリソース要求およびその柔軟性により、PicoBlazeは、適切な解決策であり得る。Xilinx PicoBlazeは、FPGAのVirtexおよびSpartanシリーズに対してサイズが最適化されている、8ビットのRISCアーキテクチャに基づいており、FPGAは、ここでは、チップデザインおよびアルゴリズムがハードウェアに入り込んでいることを示すために、高速プロトタイピングのプラットフォームとして使用される。それは、所望のアプリケーションに合わせるために、追加のポートにより拡張することが容易である、合成可能なソースレベルのVHDLファイルとして提供され得る。PicoBlazeに対して利用可能なアセンブラおよびCコンパイラが存在してもよい。例えば、49セルのアレイからなるセットアップは、Digilent XUPV2Pボード上でセットアップされる場合がある。
【０１９２】
データグラムのサイズは、6×8ビットと指定されてよい。この並列アーキテクチャは、セルの間により多くの接続を要求する場合があるが、より高速なパッケージ転送を可能にし、パッケージ転送に対するオーバーヘッドを低く保つ。セットアップでは、データパッケージを隣接するセルに送信し、対応するCPUを起動するのに、14クロックサイクルを必要とする場合がある。関係するPicoBlazeなしでパッケージを経路指定するセルは、パッケージを転送するために、30クロックサイクルの間占有される場合があり、それは、ハンドシェーキングおよびデータを受信すること、宛先方向の計算、ハンドシェーキングおよびデータを送信することを含む。
【０１９３】
データグラムの最初の8ビットは、例えば開始/停止シグナリング、変数読み出し/書込みなどのデータのコンテンツを記述するパッケージ識別子として使用され得る。8つのアドレスビットは、4ビットのX/Y座標に分けられてよく、したがって、0は有効なアドレスではないので、アドレス空間は225セルに制限される場合があり、これは、実施に関して意味を持つ場合がある。残りの4×8ビットは、データを搬送するために使用され得る。
【０１９４】
セルが生きていてビジーでないときにアサートされ得る、ハンドシェーキングおよび「ライフライン」シグナリングは、信頼性の高いパッケージ転送を確実にするために使用され得る。
【０１９５】
分散型の論理電子DNAすなわちeDNAの手法は、セルの間でデータパッケージを送信することにより、かなりのオーバーヘッドを生成する場合がある。データ交換に加えて、開始/停止シグナリングは、純粋なパッケージベースで実施される場合があり、NoCで余分なトラフィックを発生させる場合がある。将来のネットワークは、単純かつ高速な方式で、パッケージを転送することができるべきである、というのは、システム全体の性能は、その特性に非常に依存するためである。
【０１９６】
メッシュ8のネットワークは、使用されるチップ空間とホップの数との間の良好な折衷案であり得る。さらには、それは、単純かつ効率的な経路指定アルゴリズムを実施する可能性を提供することができる。このトポロジーは、現代のチップに関しては接続の数および長さは重大な問題ではないので、製造するのに妥当である場合があり、さらには、NoCの速度をさらに上げるために、パケット転送を並列化することが実行可能である場合がある。
【０１９７】
経路指定は、セルのネットワークアダプタがパッケージを受信するときに、パッケージの宛先アドレスが到達しているかどうかがチェックされるというような方法で動作する場合がある。そうでないならば、ネットワークアダプタは、宛先セルの方向を決定し、対応する場所に出力スイッチを設定する。パッケージの宛先アドレスが到達しているならば、eDNAの機能性を実行するために、CPUのインタラプトがトリガーされる。CPUのレジスタアクセスの後で、ネットワークアダプタは、データグラムの新しい宛先アドレスを、それを送出する前にチェックする。送信する前に、ネットワークアダプタは、宛先セルへの直通の経路上の次のセルが生きていてビジーではないかどうかをチェックする。そうである場合は、ネットワークアダプタは、単純に、隣接するセルの1つにパッケージを送出することを試み、この機構は、宛先への経路上の、終えんとなった、もしくはビジーであるセルが避けられ得ること、およびデッドロックが回避され得ることを確実にし、その結果、システム内でパッケージが失われないことになる。
【０１９８】
一部の実施形態が、詳細に説明され、かつ示されたが、本発明は、それらに制限されるものではなく、以下の特許請求の範囲で定義される発明の要旨の範囲内で、他の方法でさらに実施され得る。特に、他の実施形態が利用され得るとともに、構造的および機能的な修正が、本発明の範囲から逸脱することなくなされ得ることを理解されたい。
【０１９９】
複数の手段を列挙する装置クレームでは、これらの手段のいくつかは、ハードウェアのまったく同一の部品により実施されてもよい。ある手段が、相互に異なる従属クレームに記載されている、または、異なる実施形態で説明されているという単なる事実は、これらの手段の組み合わせが有利に使用され得ないということを示すものではない。
【０２００】
この明細書で使用される場合の、「備える/備えている」という用語は、述べられる特徴、整数、ステップまたは構成要素の存在を指定するために必要とされ、1つもしくは複数の他の特徴、整数、ステップ、構成要素またはそれらのグループの存在あるいは追加を排除しないということは強調されるべきである。
【符号の説明】
【０２０１】
101  セル
102  ルータ
103  リンク
104  ネットワークオンチップ(NoC)
201  セル
206  アルゴリズム
207  コンバータプログラム
208  バイナリ「DNA」コード、「DNA」コード
209  機能
210  「空」
301  セル
302  中央処理装置
303  ランダムアクセスメモリ(RAM)
304  ネットワークアダプタ
402  ANDゲート
403  NOTゲート
404  ORゲート
501  セル
【図１ａ】
0005581326.tif 000002
【図１ｂ】
0005581326.tif 000003
【図３】
0005581326.tif 000004
【図５】
0005581326.tif 000005
【図６】
0005581326.tif 000006
【図７】
0005581326.tif 000007
【図８】
0005581326.tif 000008
【図９】
0005581326.tif 000009
【図１０】
0005581326.tif 000010
【図２】
0005581326.tif 000011
【図４】
0005581326.tif 000012