(57)【要約】異種アレイは処理要素のクラスタを備えている。クラスタは、直接接続及び様々な汎用ルーティングネットワークによって接続されているＡＬＵ及びマルチプレクサの組み合わせを備えている。マルチプレクサは、同じクラスタ内のＡＬＵによって、あるいは他のクラスタ内のＡＬＵによって、専用のマルチプレクサ制御ネットワークを介して制御されている。アレイに構成されるアプリケーションのコンポーネントは、一方のタイプまたは他方のタイプの処理要素内にコンポーネントを実装することの相対的効率と、処理要素タイプの相対的利用可能性とによる決定に基づいて、マルチプレクサまたはＡＬＵのいずれかの中に選択的に実装される。マルチプレクサ制御信号は、ＡＬＵステータス信号の組み合わせから生成され、任意選択で、他のクラスタ内のマルチプレクサを制御するために送られる。
2005531952.tif 000002
【特許請求の範囲】
【請求項１】
汎用ルーティングネットワークと、
その汎用ルーティングネットワークに接続されている複数のクラスタを備え、
各クラスタは複数の処理要素を備えており、
複数の処理要素のそれぞれは第１処理要素と第２処理要素を備えており、
第１処理要素は第１のタイプであり、第２処理要素は第２のタイプであり、
第１処理要素は第１入力と第２入力と第１出力と第２出力を備えており、
第１入力と第１出力は、処理要素を通過せずに、汎用ルーティングネットワークに接続されており、
第２出力は、汎用ルーティングネットワークに接続せずに、第２処理要素に接続されており、
第２処理要素は第３入力と第４入力と第３出力を備えており、
第３入力と第３出力は、処理要素を通過せずに、汎用ルーティングネットワークに接続されている異種再構成可能アレイ。
【請求項２】
前記第１処理要素は、前記第２処理要素と組み合わせて使用するように、または前記第２処理要素と独立して使用するように構成されており、
前記第２処理要素は、前記第１処理要素と組み合わせて使用するように、または前記第１処理要素と独立して使用するように構成されていることを特徴とする請求項１の異種再構成可能アレイ。
【請求項３】
前記第１処理要素では、
前記汎用ルーティングネットワークと前記第１入力との間に、処理要素を通過せずに、第１接続が形成されており、
前記汎用ルーティングネットワークと前記第１出力との間に、処理要素を通過せずに、第２接続が形成されており、
前記第２出力と前記第２処理要素の入力との間に、第３の接続が形成されており、
その第３接続は前記汎用ルーティングネットワークから独立して構成されていることを特徴とする請求項１の異種再構成可能アレイ。
【請求項４】
前記第２処理要素では、
前記汎用ルーティングネットワークと前記第３入力との間に、処理要素を通過せずに、第４接続が形成されており、
前記汎用ルーティングネットワークと前記第３出力との間に、処理要素を通過せずに、第５接続が形成されており、
前記第４入力と前記第１処理要素の出力との間に、第６接続が形成されており、
その第６接続は前記汎用ルーティングネットワークから独立して構成されていることを特徴とする請求項１の異種再構成可能アレイ。
【請求項５】
前記汎用ルーティングネットワークは、第１ビット幅を有する複数の第１バスを備えており、
その第１ビット幅は１よりも大きく、
前記第２出力は、第２ビット幅を有する第２バスを備えており、
その第２ビット幅は、前記第１ビット幅と等しくないことを特徴とする請求項１の異種再構成可能アレイ。
【請求項６】
前記第２ビット幅が１であることを特徴とする請求項５の異種再構成可能アレイ。
【請求項７】
前記汎用ルーティングネットワークは、第１ビット幅を有する複数の第１バスを備えており、
その第１ビット幅は１よりも大きく、
前記第４入力は、第２ビット幅を有する第２バスを備えており、
前記第２ビット幅は、前記第１ビット幅と等しくないことを特徴とする請求項１の異種再構成可能アレイ。
【請求項８】
前記第２ビット幅が１であることを特徴とする請求項７の異種再構成可能アレイ。
【請求項９】
前記第１処理要素は、論理演算装置（「ＡＬＵ」）を備えていることを特徴とする請求項１の異種再構成可能アレイ。
【請求項１０】
前記ＡＬＵは、第１ビット幅のデータワードを処理することを特徴とする請求項９の異種再構成可能アレイ。
【請求項１１】
前記第１入力はＡＬＵデータ入力を備えており、
前記第２入力はＡＬＵインストラクション入力を備えており、
前記第２出力はＡＬＵ出力を備えており、
そのＡＬＵ出力は、前記ＡＬＵデータ入力またはＡＬＵインストラクション入力のうちの１つまたは複数で受け取られた１つまたは複数の入力信号から導かれた出力信号を伝送することを特徴とする請求項９の異種再構成可能アレイ。
【請求項１２】
前記出力信号は、前記ＡＬＵデータ入力で受け取られた入力信号から導かれることを特徴とする請求項１１の異種再構成可能アレイ。
【請求項１３】
前記出力信号は、前記ＡＬＵインストラクション入力で受け取られた入力信号から導かれることを特徴とする請求項１１の異種再構成可能アレイ。
【請求項１４】
前記出力信号は、前記ＡＬＵデータ入力とＡＬＵインストラクション入力で受け取られた入力信号の論理結合から導かれることを特徴とする請求項１１の異種再構成可能アレイ。
【請求項１５】
前記出力信号は、ＡＬＵキャリーアウト信号を備えていることを特徴とする請求項１１の異種再構成可能アレイ。
【請求項１６】
前記出力信号は、前記ＡＬＵによって生成された符号ビットを備えており、
その符号ビットは、符号付き算術演算の正しい符号に等しいことを特徴とする請求項１１の異種再構成可能アレイ。
【請求項１７】
前記出力信号は、第１ＡＬＵデータ値と第２ＡＬＵデータ値が等しいことを示す一致信号を備えていることを特徴とする請求項１１の異種再構成可能アレイ。
【請求項１８】
前記出力信号は、第１ＡＬＵデータ値と第２ＡＬＵデータ値が異なることを示す一致信号を備えていることを特徴とする請求項１１の異種再構成可能アレイ。
【請求項１９】
前記出力信号は、前記ＡＬＵインストラクション入力で受け取られたＡＬＵインストラクションビットを備えていることを特徴とする請求項１１の異種再構成可能アレイ。
【請求項２０】
前記第２処理要素はマルチプレクサを備えており、
前記第３入力はマルチプレクサ入力を備えており、
前記第４入力はセレクト入力を備えており、
前記第３出力はマルチプレクサ出力を備えていることを特徴とする請求項１の異種再構成可能アレイ。
【請求項２１】
前記セレクト入力は、前記汎用ルーティングネットワークを利用せずに、前記第１処理要素に接続されていることを特徴とする請求項２０の異種再構成可能アレイ。
【請求項２２】
前記マルチプレクサ出力は、インバータに接続されていることを特徴とする請求項２０の異種再構成可能アレイ。
【請求項２３】
前記マルチプレクサは、第１ビット幅のデータワードを処理可能であり、
その第１ビット幅は１よりも大きいことを特徴とする請求項２０の異種再構成可能アレイ。
【請求項２４】
複数の前記処理要素のうち少なくとも１つは、レジスタを備えていることを特徴とする請求項１の異種再構成可能アレイ。
【請求項２５】
複数の前記処理要素のそれぞれが、レジスタを備えていることを特徴とする請求項２４の異種再構成可能アレイ。
【請求項２６】
前記マルチプレクサ入力は、一定値信号を受け取ることを特徴とする請求項２０の異種再構成可能アレイ。
【請求項２７】
前記第２処理要素は、レジスタを備えていることを特徴とする請求項２０の異種再構成可能アレイ。
【請求項２８】
前記マルチプレクサ入力は、前記レジスタからフィードバック信号を受け取ることを特徴とする請求項２７の異種再構成可能アレイ。
【請求項２９】
汎用ルーティングネットワークと、
複数のクラスタを備え、
各クラスタは、論理演算装置（「ＡＬＵ」）とマルチプレクサを備えており、
そのマルチプレクサは、マルチプレクサ出力と複数のマルチプレクサ入力を備えており、
そのマルチプレクサ入力は、マルチプレクサセレクト入力と第１マルチプレクサ入力を備えており、
ＡＬＵは、ＡＬＵ出力と複数のＡＬＵ入力を備えており、
そのＡＬＵ入力は、第１ＡＬＵデータ入力と第２ＡＬＵデータ入力とＡＬＵインストラクション入力を備えており、
マルチプレクサセレクト入力は、ＡＬＵによって生成されたマルチプレクサセレクト信号を受け取るように適合されており、
マルチプレクサとＡＬＵは、汎用ルーティングネットワークに接続されている異種再構成可能アレイ。
【請求項３０】
前記マルチプレクサセレクト信号は、インストラクション入力信号ビットを備えていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項３１】
前記マルチプレクサセレクト信号は、組み合わせ関数を備えていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項３２】
マルチプレクサセレクト信号は、前記第１ＡＬＵデータ入力と第２ＡＬＵデータ入力とＡＬＵインストラクション入力のうちの少なくとも１つで受け取られる１つまたは複数の入力信号を利用して生成されることを特徴とする請求項３１の異種再構成可能アレイ。
【請求項３３】
前記入力信号のうちの少なくとも１つは、１ビットよりも大きいことを特徴とする請求項３２の異種再構成可能アレイ。
【請求項３４】
前記第１ＡＬＵ入力とＡＬＵ出力と第１マルチプレクサ入力とマルチプレクサ出力は、前記汎用ルーティングネットワークに接続されていることを特徴とする請求項３０の異種再構成可能アレイ。
【請求項３５】
前記ＡＬＵ入力のうちの１つまたは複数は、ワード幅の入力を備えており、
前記ＡＬＵ出力は、ワード幅の出力を備えており、
前記第１マルチプレクサ入力は、ワード幅の入力を備えており、
前記マルチプレクサ出力は、ワード幅の出力を備えており、
前記ワード幅の入力および出力は、前記汎用ルーティングネットワークに接続されていることを特徴とする請求項３０の異種再構成可能アレイ。
【請求項３６】
前記マルチプレクサセレクト信号は、キャリーアウト信号を備えていること特徴とする請求項３１の異種再構成可能アレイ。
【請求項３７】
前記マルチプレクサセレクト信号は、符号信号を備えていることを特徴とする請求項３１の異種再構成可能アレイ。
【請求項３８】
前記マルチプレクサセレクト信号は、オーバーフロー信号を備えていることを特徴とする請求項３１の異種再構成可能アレイ。
【請求項３９】
前記クラスタは、データ選択回路に構成されていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項４０】
前記クラスタは、条件処理回路に構成されていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項４１】
前記クラスタは、データ経路制御回路に構成されていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項４２】
前記マルチプレクサセレクト信号入力は、前記汎用ルーティングネットワークをバイパスすることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項４３】
前記ＡＬＵによって生成されるとともに前記ＡＬＵ出力を通して送られる出力信号は、前記汎用ルーティングネットワークに伝えられており、
そのＡＬＵ出力は前記汎用ルーティングネットワークに直接接続されていないことを特徴とする請求項２９の異種再構成可能アレイ。
【請求項４４】
前記汎用ルーティングネットワークは第１ビット幅を有しており、
その第１ビット幅は２つ以上のビットを備えており、
前記出力信号は第２ビット幅を有しており、
その第２ビット幅は１つまたは複数のビットを備えており、
前記第１ビット幅は、前記第２ビット幅よりも大きいことを特徴とする請求項４３の異種再構成可能アレイ。
【請求項４５】
前記出力信号は、前記第２ビット幅から前記第１ビット幅に変換されることを特徴とする請求項４４の異種再構成可能アレイ。
【請求項４６】
前記出力信号は、前記マルチプレクサを通して送られることによって、前記汎用ルーティングネットワークに伝えられることを特徴とする請求項４３の異種再構成可能アレイ。
【請求項４７】
前記マルチプレクサ出力に接続されている出力レジスタを備えていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項４８】
前記マルチプレクサ出力は、前記レジスタを通して送られることを特徴とする請求項４７の異種再構成可能アレイ。
【請求項４９】
前記マルチプレクサおよび前記出力レジスタは、イネーブル付きレジスタ回路に構成されていることを特徴とする請求項４７の異種再構成可能アレイ。
【請求項５０】
前記マルチプレクサおよび前記出力レジスタは、リセット付きレジスタ回路に構成されていることを特徴とする請求項４７の異種再構成可能アレイ。
【請求項５１】
前記複数のマルチプレクサ入力のうちの１つに接続されている入力選択論理を備えていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項５２】
前記入力選択論理は、一定値を受け取る少なくとも１つの入力を有する第２のマルチプレクサを備えていることを特徴とする請求項５１の異種再構成可能アレイ。
【請求項５３】
前記異種再構成可能アレイに構成されているアプリケーションを備えており、
前記入力選択論理は、前記アプリケーションによって動的に制御されないことを特徴とする請求項５１の異種再構成可能アレイ。
【請求項５４】
前記入力選択論理は、前記マルチプレクサ出力から複数の前記マルチプレクサ入力のうちの１つに向けてフィードバック経路を形成していることを特徴とする請求項５１の異種再構成可能アレイ。
【請求項５５】
前記入力選択論理は、前記ＡＬＵから前記マルチプレクサに向けてキャリーアウト信号を提供していることを特徴とする請求項５１の異種再構成可能アレイ。
【請求項５６】
前記アレイは、前記マルチプレクサ出力から前記複数のＡＬＵ入力のうちの１つに向けてフィードバック経路を提供していることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項５７】
前記フィードバック経路は、前記マルチプレクサ出力に接続されている出力選択スイッチの下流に提供されていることを特徴とする請求項５６の異種再構成可能アレイ。
【請求項５８】
前記フィードバック経路は、非同期ラッチを形成していることを特徴とする請求項５７の異種再構成可能アレイ。
【請求項５９】
前記マルチプレクサ出力に接続されているインバータを備えていることを特徴とする請求項２９の異種再構成可能アレイ。
【請求項６０】
前記マルチプレクサ出力は、前記インバータを通して送られることを特徴とする請求項５４の異種再構成可能アレイ。
【請求項６１】
第１の処理要素と第２の処理要素を有するクラスタを複数備えている異種再構成可能アレイを構成するための方法であって、
アプリケーションを受け取る工程と、
アプリケーションの第１部分を選択する工程と、
アプリケーションの第２部分を選択する工程と、
アプリケーションの第３部分を選択する工程と、
第１部分を、複数の第１処理要素に実装する工程と、
第２部分を、複数の第２処理要素に実装する工程と、
第３部分を、利用可能性基準に基づいて、複数の第１処理要素、複数の第２処理要素、又はその組み合わせのいずれかに選択的に実装する工程と、
を備えている構成方法。
【請求項６２】
前記第１部分は、第１処理要素を利用して実装されるアプリケーション要素を備えていることを特徴とする請求項６１の構成方法。
【請求項６３】
前記第２部分は、第２処理要素を利用して実装されるアプリケーション要素を備えていることを特徴とする請求項６１の構成方法。
【請求項６４】
前記第３部分は、第１処理要素または第２処理要素のいずれかを利用して実装されるアプリケーション要素を備えていることを特徴とする請求項６１の構成方法。
【請求項６５】
前記利用可能性基準は、前記第３部分が、より豊富に利用可能な処理要素内に実装されることを規定することを特徴とする請求項６１の構成方法。
【請求項６６】
前記第３部分は、複数のアプリケーション要素を備えており、
前記利用可能性基準が、各アプリケーション要素について、一度評価されることを特徴とする請求項６５の構成方法。
【請求項６７】
前記複数の第１処理要素は、論理演算装置を備えていることを特徴とする請求項６１の構成方法。
【請求項６８】
前記複数の第２処理要素は、マルチプレクサを備えていることを特徴とする請求項６１の構成方法。
【請求項６９】
それぞれがＡＬＵ出力と複数のＡＬＵ入力を有する複数の論理演算装置（「ＡＬＵ」）と、
それぞれがマルチプレクサ制御入力を有する複数のマルチプレクサと、
ＡＬＵ群とマルチプレクサ群のうち、選択されたものの間の接続を形成する汎用ルーティングネットワークと、
複数のＡＬＵ出力のうちの１つと、複数のマルチプレクサ制御入力のうちの１つを接続するマルチプレクサ制御回路を備え、
マルチプレクサ制御回路は、１つまたは複数のＡＬＵ出力信号からマルチプレクサ制御信号を導くことを特徴とする異種再構成可能アレイ。
【請求項７０】
前記ＡＬＵ出力信号は、１つまたは複数のＡＬＵ入力信号に基づく信号を備えていることを特徴とする請求項６９の異種再構成可能アレイ。
【請求項７１】
前記ＡＬＵ出力信号は、ＡＬＵキャリーアウト信号を備えていることを特徴とする請求項７０の異種再構成可能アレイ。
【請求項７２】
前記ＡＬＵ出力信号は、正しい符号信号を備えていることを特徴とする請求項７０の異種再構成可能アレイ。
【請求項７３】
前記ＡＬＵ出力信号は、オーバーフロー信号を備えていることを特徴とする請求項７０の異種再構成可能アレイ。
【請求項７４】
前記ＡＬＵ出力信号は、ＡＬＵデータ入力信号を備えていることを特徴とする請求項７０の異種再構成可能アレイ。
【請求項７５】
前記ＡＬＵ出力信号は、ＡＬＵインストラクション入力信号を備えていることを特徴とする請求項７０の異種再構成可能アレイ。
【請求項７６】
前記ＡＬＵ出力信号は、ＡＬＵデータ信号とＡＬＵインストラクション信号の論理結合を備えていることを特徴とする請求項７０の異種再構成可能アレイ。
【請求項７７】
１つまたは複数の前記ＡＬＵ出力信号は、コード化ＡＬＵ出力にコード化されていることを特徴とする請求項６９の異種再構成可能アレイ。
【請求項７８】
前記マルチプレクサ制御回路は、１つまたは複数のＡＬＵ出力信号と１つまたは複数のマスク値から、前記マルチプレクサ制御信号を導くことを特徴とする請求項６９の異種再構成可能アレイ。
【請求項７９】
前記マルチプレクサ制御回路に接続されている外部入力を備えており、
１つまたは複数の前記マスク値は、前記マルチプレクサ制御信号を生成するために、前記外部入力を選択するために利用されることを特徴とする請求項７８の異種再構成可能アレイ。
【請求項８０】
前記マルチプレクサ制御回路は、複数のマルチプレクサ制御回路のうちの１つであるとともに、専用の高ファンアウトネットワークを備えており、
その専用の高ファンアウトネットワークは、複数の前記マルチプレクサ制御回路のみに接続されていることを特徴とする請求項７９の異種再構成可能アレイ。
【請求項８１】
前記外部入力は、前記専用の高ファンアウトネットワークから前記マルチプレクサ制御回路に接続されていることを特徴とする請求項８０の異種再構成可能アレイ。
【請求項８２】
前記マルチプレクサ制御回路から前記専用の高ファンアウトネットワークに接続されている専用の高ファンアウトネットワーク出力を備えていることを特徴とする請求項８０の異種再構成可能アレイ。
【請求項８３】
前記マルチプレクサ制御回路は、複数のマルチプレクサ制御回路のうちの１つであるとともに、第２汎用ルーティングネットワークを備えており、
その第２汎用ルーティングネットワークは、複数の前記マルチプレクサ制御回路のみに接続されていることを特徴とする請求項６９の異種再構成可能アレイ。
【請求項８４】
前記外部入力は、前記第２汎用ルーティングネットワークから前記マルチプレクサ制御回路に接続されていることを特徴とする請求項８３の異種再構成可能アレイ。
【請求項８５】
前記マルチプレクサ制御回路と前記第２汎用ルーティングネットワークを接続する出力接続を備えていることを特徴とする請求項８３の異種再構成可能アレイ。
【請求項８６】
第１の複数の入力端子と第１の複数の出力端子を備えている第１汎用ルーティングネットワークと、
第２の複数の入力端子と第２の複数の出力端子を備えている第２汎用ルーティングネットワークと、
複数の処理要素を備え、
それぞれの処理要素は、第１の複数の入力端子、第１の複数の出力端子、第２の複数の入力端子、第２の複数の出力端子のいずれかに属する少なくとも１つの端子に接続されている複数の処理要素を備えている再構成可能アレイ。
【請求項８７】
前記第１汎用ルーティングネットワークは、複数の前記処理要素のうちの１つまたは複数のみによって、前記第２汎用ルーティングネットワークに接続されていることを特徴とする請求項８６の再構成可能アレイ。
【請求項８８】
前記第１汎用ルーティングネットワークは第１ビット幅を有し、前記第２汎用ルーティングネットワークは第２ビット幅を有しており、
前記第１ビット幅は前記第２ビット幅と異なっていることを特徴とする請求項８６の再構成可能アレイ。
【請求項８９】
前記第１汎用ルーティングネットワークは、前記第１の複数の入力端子のいずれかと前記第１の複数の出力端子のいずれかとの間の接続をなすように構成可能であることを特徴とする請求項８６の再構成可能アレイ。
【請求項９０】
前記第２汎用ルーティングネットワークは、前記第２の複数の入力端子のいずれかと前記第２の複数の出力端子のいずれかとの間の接続をなすように構成可能であることを特徴とする請求項８６の再構成可能アレイ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、再構成可能なコンピューティングデバイスに関する。より詳細には、本発明は、アプリケーションの複数の態様の実装を可能とするアレイ要素タイプを有する異種アレイに関する。
【背景技術】
【０００２】
フィールドプログラマブルゲートアレイ（「ＦＰＧＡ」）、プロセッサアレイ、および再構成可能算術演算アレイ（「ＲＡＡ」）などの再構成可能デバイスは、通常、多数の処理要素とそれらを接続するための相互接続方式を備えている。相互接続は、通常は汎用ルーティングネットワークの形態を取る。その他のより限定的な相互接続の形態も利用され得る。処理要素は、１つまたは複数のデータ入力を有しており、１つまたは複数のデータ出力を計算する。データ出力のそれぞれは、２つ以上の入力値に基づいた関数である。２つ以上の入力値とは、２つ以上の入力で受け取られるもの、又は場合によっては同じ入力で別々の時間に受け取られたものである。処理要素の例としては、加算器、乗算器、ＦＰＧＡ様のルックアップテーブル（ＬＵＴ）、およびデータ入力に接続可能なセレクト信号を有するマルチプレクサがある。出力が以前の時間における入力の一部またはすべての値の関数であることができるように、処理要素はレジスタを備えていてもよい。
【０００３】
汎用ルーティングネットワークは、複数の入力端子と複数の出力端子（さらに、場合によっては、入力端子または出力端子のいずれかとして構成可能ないくつかの双方向端子）を備え、任意の入力端子と任意の出力端子との間の接続をなすように構成可能である。すべての端子は、同じワード長のデータ値を運ぶ。構成された場合、汎用ルーティングネットワークは、複数の独立した接続をなす。各接続は、１つのネットワーク入力を１つまたは複数のネットワーク出力に接続するが、各ネットワーク出力は多くても１つのネットワーク入力にしか接続されない。これらの接続は、レジスタを通過していてもよい（それにより、ネットワーク入力とネットワーク出力との間にいくらかの時間的オフセットが存在してもよい）。ただし、ルーティングネットワーク内ではデータ処理は行われないので、出力端子でのデータ値と、関連する時間における関連する入力端子での同等の値との間には、直接的な対応関係がある。そのようなネットワークは、一般に、パストランジスタ、および／または、トライステートバッファ、および／または、静的に構成されたマルチプレクサ（つまり、アレイの構成によって制御されるセレクト入力を有するマルチプレクサ）から構築されている。しかしながら、ネットワークの構造に関係なく、その機能（ネットワーク入力からネットワーク出力にデータを伝えるということ）は同じである。
【０００４】
再構成可能デバイスの設計は、処理要素および相互接続の特性を指定するプロセスである。これら両者の要素においては、このプロセスは以下で説明する一連の妥協を備えている。
【０００５】
処理要素の選択は、機能と、物理的サイズ、動作速度、または電力損などのさまざまなパラメータとの間の妥協点を見つけることである。例えば、機能を追加することにより、各要素のサイズは増加するが、アプリケーションを実装するために必要とされる要素の合計数は減少する可能性がある。機能を追加する価値があるのは、要素数の減少が、個々の要素のサイズの増加よりも影響力があり、したがって、アプリケーション領域が最終的に増加しない場合のみである。機能の増加は、他のパラメータにも同様に影響を及ぼす。
【０００６】
上述のように、再構成可能デバイスにはさまざまなタイプがある。また、再構成可能デバイスのためのさまざまなタイプのアプリケーションも存在する。さまざまなタイプの再構成可能デバイスのそれぞれは、一般に、あるタイプのアプリケーションを、他のタイプのアプリケーションよりも適切に実行する。再構成デバイス内で使用される特定の処理要素の適合性の評価は、したがって、そのデバイスの用途として意図されているアプリケーションのタイプにより異なる。
【０００７】
サイズ／機能の空間内には、いくつかの「スイートスポット」があり、それは部分的には、アプリケーション空間の区割りよるものである（例えば、さまざまなタイプのアプリケーションにおいては、通常、ＦＰＧＡではなく、プロセッサアレイが利用される）。また部分的には、機能を一緒に組み合わせる方が、それらのうちの任意のものを単独で使用するよりも良い可能性があるためである（例えば、プロセッサに乗算器または除算器を追加することは価値がない可能性があるが、両方を追加すること−それらの間でハードウェアがいくらか共有されるように−は最終的に利益となる）。
【０００８】
相互接続の選択もまた、機能と、物理的サイズ、動作速度、又は電力損などのさまざまなパラメータとの間の妥協点を見つけることである。理想的な相互接続は、伝播遅延が０で、１つの経路が別の経路を妨害する危険がなく、物理的な面積は無視できるほど小さいものである。この理想は、実際には存在しない。適切な妥協に達するために、次のようなさまざまな要素の特性を考慮できる。
【０００９】
処理要素：
高速な処理要素には、高速な相互接続が好ましい。
処理要素によってデータが処理される幅と同じ幅で、データを送ることは有益である。
【００１０】
アレイ：
可能な接続の数は、処理要素の数の２乗で増加する。接続間の妨害がないことを保証する相互接続の「要素あたりのコスト」は、したがって、処理要素の数に直線的に比例して増加する。これは、小さなアレイでは手頃な可能性があるが、大きなアレイでは手頃ではない。
伝播遅延は、アレイのサイズとともに増加する傾向がある。
【００１１】
アプリケーション：
再構成可能デバイスを利用するために書かれたアプリケーションが、最近接接続のみを有するデバイスを利用してそのアプリケーションを実装できるように書かれている場合は、相互接続を大幅に単純化できる。そのような単純化が可能でない場合は、（上述のような）汎用ルーティングネットワークが、相互接続の基礎として一般に利用される。ネットワークの端子が処理要素の端子となる。
【００１２】
性能を向上するために、再構成可能デバイスは、さらに、異種処理要素、階層型ルーティングネットワーク、および／または、異種インターコネクト等の追加要素を備え得る。異種処理要素は、２つ以上の異なるタイプの処理要素を１つのデバイス上で組み合わせたものであり、例えば次のようなものがある。
ルックアップテーブルベースの要素と、専用乗算器ブロックとの両方を有するＦＰＧＡ
ルックアップテーブルベースの要素と、積項ベースの論理との両方を有するＦＰＧＡ
整数および浮動小数点の両方のプロセッサを含むプロセッサアレイ
【発明の開示】
【発明が解決しようとする課題】
【００１３】
処理要素の組み合わせは、さまざまな理由で行われてよい。例えば、「機能対コスト」のトレードオフの問題を減らそうとして行われてもよい（デバイス上の代替タイプのブロックとして機能が追加される場合、すべての処理要素のコストが追加されるのではなく、追加される機能を含む処理要素のコストのみが追加される）。このアプローチは、表面的には魅力的ではあるが、さまざまなタイプの処理要素の割合はどれだけであるべきか、およびそれらがお互いに対してどのように配置されるべきかを決定するという、１つの大きな問題がある。例えば、アレイの行または列内などに、要素タイプの、きめの細かい混合（ＡＢＡＢＡＢ．．．）が存在すべきか、または、よりきめの粗い混合（ＡＡＡＢＢＢＡＡＡＢＢＢ）が存在すべきか、を決定しなければならない。よりさまざまなタイプの処理要素が再構成可能デバイス内に組み込まれるにつれて、混合の解析はより重要になる。
【００１４】
階層型ルーティングネットワーク方式は、通常、処理要素をグループ内に割り当て、グループ内の要素を強力に接続し、さらに、グループ間を（および、グループ群の間などを）接続する。このモデルの拡張では、グループが重なる場合がある（つまり、境界は、グループ間接続以外の接続が存在しないという不透明な壁ではない）。例えば、グループの境界にある処理要素は、両方のグループのメンバーであり得る。
【００１５】
異種相互接続方式を利用すると、２つ以上のタイプの接続が利用可能となる。例えば、高速ではあるが限定されている追加の相互接続が、より低速ではあるがより高機能な汎用ルーティングネットワークに追加される。
【００１６】
一般的な接続パターン（例えば、多くのＦＰＧＡ内の「キャリーワイヤ」）をサポートするために、専用の配線が追加される場合がある。
【００１７】
汎用ルーティングネットワークに加えて、専用の最近接接続が存在する場合もある。
【００１８】
「異種」相互接続と「階層型」相互接続との間には、大きな違いがある。階層型ルーティングネットワークは、階層のすべてのレベルについて同じタイプの接続を利用し、レベルによって接続の到達範囲が異なるのに対して、異種相互接続は、さまざまなネットワークのための異なるタイプの接続を利用する。アレイは、異種相互接続および階層型相互接続の両方を含むことに留意されたい。
【００１９】
プロセッサは、一般に、条件分岐と無条件分岐とジャンプの混合、及び／又は命令の予測実行を利用して、アプリケーション内の制御の流れを管理している。「再構成可能コンピューティング」とは、再構成可能デバイスを利用して計算を実行するために、アプリケーション固有のデータ経路を構築するコンピューティングのことをいう。「再構成可能コンピューティング」は、通常、制御の流れの管理にはあまり優れていない。
【００２０】
プロセッサアレイ内では、個々のプロセッサは、各自の命令の流れの管理に優れているが、アレイ内の他のプロセッサへの影響をほとんど又は全く有していない。
【００２１】
ＦＰＧＡベースの再構成可能コンピューティングでは、プログラムを通した各経路が、あまり頻繁に利用されないものでさえも、ハードウェア内に実装されていなければならない。プロセッサの実行時動作の最大９０％が、コードのうちの１０％のみで指定されてもよいとすると、ＦＰＧＡのシリコン領域のほとんどが、まれにしか使用されない動作のために割り当てられているということになる。上記の例では、９０％の領域が１０％の時間で利用されるのに対して、残りの１０％の領域は、９０％の時間で使用される。
【００２２】
再構成可能コンピューティング用に設計されたその他のデバイス（ＲＡＡなど）では、ＦＰＧＡの状況を改善する試みがなされている。ＲＡＡは、インストラクション入力を備えた論理演算装置（「ＡＬＵ」）を有しているので、ＡＬＵに提供されるインストラクションを変更することにより、データ経路の機能を動的に変更することが可能である。しかし、これは完全な解決策ではない。
【００２３】
ビットではなく、マルチビットワード（例えば、４ビットニブル）を処理する。また、ＲＡＡ ＡＬＵは、入力ワードによって実行する操作を選択するための、（やはり、４ビット内への）コンパクトなインストラクション符号化を備えている。しかし、制御条件は、決定の真／偽の性質を表現する単一ビットとなる傾向がある。
ＡおよびＢ入力は等しいか
入力Ａは入力Ｂよりも大きいか
入力のビット３は１にセットされているか
【００２４】
ｎビットＡＬＵを利用して、（「もし条件１または条件２ならば  ．．．」のような文内で）そのような単一ビット条件を処理すると、ＡＬＵのデータ経路は十分に使用されず、（ｎ−１）ビットは未使用となる。
【００２５】
その結果として、次のような状況になる。ＦＰＧＡは、その１ビット性により、条件処理に優れているが、条件の結果に基づく分岐には劣っている。それに対して、マルチビットのＲＡＡ様のデバイスは、分岐には優れているが、条件の処理には非効率的である。
【００２６】
再構成可能コンピューティングアプリケーションのための有用な実装技術は、データを、ビット（またはニブル、またはワードのその他の何らかの小部分、またはその他の全幅のデータ項目）シリアル形式で処理することである。なぜなら、単一の処理要素が、ワードの連続部分を処理するために、連続するクロックサイクル内で利用されるからである。この技術により、領域とスループットが相互にトレードオフされることが可能になる。なぜなら、シリアル化された処理は、より長時間がかかるが、使用される処理要素の数はより少ないからである。
【００２７】
シリアルフォーマットとパラレルフォーマットの間でデータを変換する機能は、シリアル化された処理の中で有用である。この変換を実行する１つの方法は、マルチプレクサおよびレジスタから構築された回路を利用することである。
【００２８】
マルチプレクサもまた、多数の一般的な１入力および２入力論理関数を実装するために、再構成可能デバイス内で有用である。これらの例は、Ｃ／ｊａｖａの「条件選択」演算子：「ａ＝（ｂ？ｃ：ｄ）；」によって書かれている（この演算子は、「ｉｆ（ｂ）ｔｈｅｎ｛ａ＝ｃ；｝ｅｌｓｅ｛ａ＝ｄ；｝」の省略表現である）。
Ａ＆Ｂ    ＝Ａ？Ｂ：０
Ａ｜Ｂ    ＝Ａ？１：Ｂ
ＮＯＴ Ａ ＝Ａ？０：１
Ａ∧Ｂ    ＝Ａ？（ＮＯＴ Ｂ）：Ｂ
【課題を解決するための手段】
【００２９】
上述のように、異種アレイは、さまざまなワード長を処理するように最適化された、処理要素の混合を提供する。ただし、従来の異種アレイには、上述の割合決定問題がある。これらの問題の有用な解決策は、第１のタイプの処理要素をマルチビット処理に偏重させるとともに１ビット処理も可能に設計し、そして、第２のタイプの処理要素を、１ビット処理に偏重させるとともにマルチビット処理も可能に設計することである。
【００３０】
添付の図面は、本発明の実施形態のさらなる理解を提供するためのものであり、以下の説明とともに、開示されている実施形態の原理を説明するために有用である。
【発明を実施するための最良の形態】
【００３１】
本発明の実施形態を以下に開示する。本実施形態で説明するアレイは、第１および第２のタイプの処理要素として、ＡＬＵおよびマルチプレクサを利用して構成されている。ただし、ＡＬＵ、マルチプレクサ、又はその両者に代えて、その他の処理要素が使用され得ることは当業者であれば理解する。例えば、アレイは、ルックアップテーブルベースの要素、積項ベースの要素、ハードワイヤード要素（専用乗算器ブロック、浮動小数点プロセッサ、整数プロセッサなど）、又は組み合わせ論理関数を実装することが可能なその他の要素を利用して構成されてもよい。
【００３２】
本実施形態のアレイは、処理要素の複数の「クラスタ」という用語によって表される。クラスタは、少なくとも１つの第１のタイプの処理要素と１つの第２のタイプの処理要素を有する処理要素の集まりを備えている。クラスタ内の第１のタイプと第２のタイプの処理要素は、直接クラスタ内接続を用いて相互に接続されている。直接クラスタ内接続は、導線、バス、またはその他の形態の電気的接続であり得る。クラスタ内接続は、アレイ上に存在するいかなる汎用ルーティングネットワークの一部ではない。ただし、クラスタ境界において、汎用ルーティングネットワークとの接続が存在し得る。クラスタは、同一でない要素に直接接続する接続の組によって、直接的または間接的に接続されている処理要素の組として定義される。２つのタイプの処理要素を有する実施形態では、信号がクラスタ内接続を介して実際に伝わる方向と無関係に、第１のタイプから第２のタイプの処理要素への、又はその逆のクラスタ内接続をたどることによって、クラスタ内の任意の処理要素に、クラスタ内のその他の任意の処理要素から到達することが可能である。３つのタイプの処理要素を有する実施形態では、同一でないタイプの処理要素を接続するクラスタ内接続の任意の経路が、クラスタを定義する。
【００３３】
例えば、第１のタイプの処理要素がＡＬＵで、第２のタイプの処理要素がマルチプレクサである場合、経路ＡＬＵ−ＭＵＸ−ＡＬＵ−ＭＵＸはクラスタを表すが、経路ＡＬＵ−ＭＵＸ−ＭＵＸは、経路内に同じタイプの２つの処理要素間の接続があるので、クラスタを表さない。同様に、３つの処理要素タイプＡ、Ｂ、Ｃについては、経路Ａ−Ｂ−Ｃ−Ａはクラスタを表すが、Ａ−Ｂ−Ｂ−Ｃ−Ａは、Ｂ−Ｂ接続があるので、クラスタを表さない。
【００３４】
クラスタは、また、上述のようにクラスタ内に処理要素の各ペア間の経路が存在していれば、同じタイプの処理要素間の接続を備えていてもよい。
【００３５】
図１９は、クラスタの例を示す。処理要素は、「ＡＬＵ」および「ＭＵＸ」要素により示され、接続は、要素を接続する線によって示されている。第１のクラスタ１９１０は、点線の左側にあるすべての処理要素１９１０（ａ）〜（ｆ）を備えている。第２のクラスタ１９２０は、点線の右側にあるすべての処理要素１９２０（ａ）〜（ｇ）を備えている。各処理要素１９１０（ａ）〜（ｆ）には、その他の各処理要素１９１０（ａ）〜（ｆ）から、ＡＬＵ−ＭＵＸまたはＭＵＸ−ＡＬＵ接続をたどることにより到達可能である。同様に、各処理要素１９２０（ａ）〜（ｇ）には、その他の各処理要素１９２０（ａ）〜（ｇ）から、ＡＬＵ−ＭＵＸまたはＭＵＸ−ＡＬＵ接続をたどることにより到達可能である。処理要素１９２０（ａ）〜（ｇ）から、ＡＬＵ−ＭＵＸまたはＭＵＸ−ＡＬＵ接続をたどることによって、処理要素１９１０（ａ）〜（ｆ）のいずれにも到達することはできない。少なくとも１つのＡＬＵ−ＡＬＵまたはＭＵＸ−ＭＵＸ接続をたどる必要がある。したがって、処理要素１９１０（ａ）〜（ｆ）は第２のクラスタ１９２０のメンバーでない。処理要素１９２０（ａ）〜（ｇ）もまた第１のクラスタ１９１０のメンバーでない。
【００３６】
「ＡＬＵ」は、インストラクション値によって、さまざまな数学および論理関数を実装するように構成可能な処理要素である。ＡＬＵは、１つまたは複数のデータ入力を受け取り、インストラクション値によって選択された関数をデータ入力に適用して、データ出力を生成する。ＡＬＵは、また、別の処理要素からキャリーイン値を受け取ってもよく、そして、受け取ったデータおよびインストラクション値に基づいて、別の処理要素にキャリーアウト出力値を提供してもよい。
【００３７】
「マルチプレクサ」は、２つ以上のデータ入力値を受け取り、セレクト入力値に基づいて、データ入力値のうちの１つをデータ出力に提供する。
【００３８】
図１に示すように、再構成可能アレイ内で利用されるＡＬＵ１００は、第１のデータ入力１１０、第２のデータ入力１２０、およびインストラクション入力１３０を備えている。データおよびインストラクション入力は、アレイ内の他の要素又はアレイに接続されている要素から入力値を受け取る。データおよびインストラクション入力は、第１ビット幅の入力値を受け取る。
【００３９】
ＡＬＵ１００は、さらに、第２ビット幅のキャリーイン入力１４０（「ＣＩＮ」）を備えている。この入力は、アレイ内の別のＡＬＵ１００からキャリー入力を受け取るために利用される。
【００４０】
ＡＬＵ１００は、さらに、第２ビット幅のキャリーアウト出力１５０（「ＣＯＵＴ」）を備えている。キャリーアウト出力１５０は、アレイ内の他の要素又はアレイに接続された他の要素にキャリー出力を提供する。ＡＬＵ１００の構成によっては、キャリーイン入力１４０およびキャリーアウト出力１５０は、設計者による要求に基づいて、キャリー値以外の値を提供することも可能である。
【００４１】
ＡＬＵ１００は、さらに、第１ビット幅のデータ出力１６０を備えている。データ出力１６０は、ＡＬＵにより実行された数学または論理関数の結果を、アレイ内の他の要素又はアレイに接続された他の要素に提供する。
【００４２】
ＡＬＵ１００は、さらに、第２ビット幅のセレクト信号出力１７０を備えている。セレクト信号出力１７０は、アレイ内の他の要素又はアレイに接続された他の要素にセレクト信号を提供する。セレクト信号は、アレイ内又はアレイに接続されている別の要素の機能を制御するために有用な、多種多様な信号であり得る。例えば、セレクト信号は、以下のデータ依存信号のうちの１つまたは複数であってもよい。
ＣＯＵＴ：ＡＬＵ演算からのキャリーアウト
符号：ＡＬＵ演算の正しい符号（算術オーバーフローが発生した場合でも）
オーバーフロー：算術オーバーフローが発生したことを示す信号
【００４３】
あるいは、セレクト信号は、インストラクション入力１３０の１つまたは複数のビットであり得る。これにより、データ依存およびインストラクション依存の両方の信号の提供が可能になる。いくつかの実施形態では、ＡＬＵ１００は、インストラクション入力１３０とは無関係に、内部インストラクションを記憶するように適合されている。これにより、インストラクション入力１３０を、専用のセレクト信号入力として使用することが可能になり、そのためには、インストラクション入力１３０の一部またはすべてをセレクト信号出力１７０に直接提供し、記憶されたインストラクション値をＡＬＵ１００を制御するために使用する。以下で詳しく説明するように、セレクト信号出力１７０は、さらに、ＡＬＵ１００から送られるさまざまな信号を選択するための、追加の回路も備え得る。
【００４４】
図２に示すように、再構成可能アレイ内で利用されるマルチプレクサ２００は、第１の入力２１０と第２の入力２２０（いずれも第１ビット幅）を備えている。入力２１０、２２０は、アレイ内の他の要素又はアレイに接続された要素から入力値を受け取る。
【００４５】
マルチプレクサ２００は、さらに、第１ビット幅の出力２３０を備えている。出力２３０は、マルチプレクサ２００により実行された入力選択の結果を、アレイ内の他の要素又はアレイに接続された要素に提供する。
【００４６】
マルチプレクサ２００は、さらに、セレクト入力２４０を備えている。セレクト入力２４０は、入力２１０、２２０のうちのどちらが出力２３０に送られるべきかを指示するセレクト値を受け取る。セレクト入力２４０は、第２ビット幅である。本実施形態では、セレクト値が「１」の場合は、第１の入力２１０が出力２３０に送られ、セレクト値が「０」の場合は、第２の入力２２０が出力２３０に送られる。
【００４７】
本実施形態では、第１ビット幅はワード幅（４ビット幅）であり、第２ビット幅は１ビット幅である。他の実施形態では、第１ビット幅および第２ビット幅は、設計者により企図された特定の実装により要求される任意のサイズであり得る。第１ビット幅の入力および出力は、好ましくは、アレイのさまざまな要素にわたって信号を送るために有用な、第１汎用ルーティングネットワークに接続される。第２ビット幅の入力および出力は、好ましくは、別の処理要素に直接接続されるか、または、さもなければ、第２ビット幅の信号を運ぶように適合された第２汎用ルーティングネットワークに接続される。いずれのケースでも、第２ビット幅の信号は、第１汎用ルーティングネットワークをバイパスする。あるいは、第２ビット幅の信号は、第１ビット幅の信号とともに、第１汎用ルーティングネットワークを横切って送られる。さまざまな入力および出力が、さまざまな導線、バス、あるいはその他の導電性デバイスまたは電流経路を使用して接続されてもよい。
【００４８】
図３に示すように、クラスタ３００は、ＡＬＵ１００およびマルチプレクサ２００を備えている。ＡＬＵ１００のセレクト出力１７０は、セレクト信号をマルチプレクサ２００のセレクト入力２４０に提供する。上述のように、マルチプレクサ２００は、データ依存またはインストラクション依存のいずれかの信号により制御されることが可能となる。アプリケーション内での有用性という点では、これらの２つのケースは、大まかには、プロセッサ内の条件分岐および無条件分岐と同等である。
【００４９】
設計者の要求に基づいて、追加のマルチプレクサをクラスタ３００に追加することも可能である。これらの追加のマルチプレクサは、マルチプレクサ２００を制御するのと同じセレクト信号により制御されてもよく、または、異なるセレクト信号により制御されてもよい。クラスタ３００は、さらに、クラスタ３００内の要素のさまざまな入力および出力に接続される、追加のＡＬＵ、レジスタ、ゲート、その他の、他の要素の追加により拡張されてもよい。クラスタ３００は、さらに、より複雑な回路を実装するために、他のクラスタに接続されてもよい。そのような拡張のさまざまな例について、以下で詳しく説明する。
【００５０】
クラスタ３００は、単独で使用することも、あるいは、さまざまな回路を実装するために、他のクラスタ３００と組み合わせて使用することも可能であり、その例を図４〜６に示す。図４Ａに示すように、クラスタ３００は、データ選択回路を実装するために利用される。データ選択回路は、セレクト信号出力１７０上で提供される条件の結果によって、「ＩＮ１」または「ＩＮ２」のいずれかを選択する。例えば、セレクト信号出力１７０がオーバーフロー信号を提供するように構成されている場合、データ選択回路はオーバーフローがあれば（Ｓ＝１）、「ＩＮ１」を選択し、オーバーフローがなければ（Ｓ＝０）、「ＩＮ２」を選択する。
【００５１】
この回路は、例えばワード長が変更された場合に符号拡張を実行することによって、データをフォーマッティングする際に有用である。第１の入力１１０は、８ビット値に変換されるべき、符号付き４ビット値を運んでいる。マルチプレクサ入力２１０、２２０は、それぞれ、値「１１１１」および「００００」を運んでいる。ＡＬＵ１００は、関数Ａ＜０を評価して、適切な符号信号をセレクト出力１７０に生成するとともに、入力値ＡをＡＬＵ出力１６０に伝える。符号出力信号は、「１１１１」または「００００」のいずれかを選択するようにマルチプレクサ２００を切り換えるために利用される。８ビットの結果は、ＡＬＵ出力１６０の値、およびマルチプレクサ出力２３０の値から構築される。
【００５２】
図４Ｂに示すように、クラスタ３００は、また、ＡＬＵ１００により生成された第２ビット幅の信号を、第１ビット幅の汎用ルーティングネットワークに伝えるように構成することも可能である。ＡＬＵ１００のセレクト出力１７０で生成された第２ビット幅のセレクト信号は、マルチプレクサ２００のセレクト入力２４０に送られる。第１の入力２１０には、第２ビット幅の値「１」を表現する第１ビット幅の値「０００１」が提供される。第２の入力２２０には、第２ビット幅の値「０」を表現する第１ビット幅の値「００００」が提供される。セレクト信号が「１」の場合、マルチプレクサ２００は、第１の入力値２１０の「０００１」を出力２３０に送るとともに、その先にある汎用ルーティングネットワークにも送る。同様に、セレクト信号が「０」の場合、マルチプレクサ２００は、第２の入力値２２０の「００００」を出力２３０に送るとともに、その先にある汎用ルーティングネットワークにも送る。このようにして、符号、オーバーフロー、キャリーアウト、その他のセレクト信号は、第２ビット幅から第１ビット幅に効率的に変換されるとともに、第１汎用ルーティングネットワークに置かれ、その先にある他の処理要素に送られることが可能となる。これにより、上述の専用接続および第２汎用ルーティングネットワークに加えて、これらの信号のための代替経路が提供される。
【００５３】
図５に示すように、第１のクラスタ５１０および第２のクラスタ５５０は、条件処理回路を実装するために使用される。条件処理回路は、ＡＬＵのセレクト出力値として提供された１つまたは複数の条件に基づいて、論理演算を実行する。第１のクラスタ５１０は第１のＡＬＵ５２０を備えている。ＡＬＵ５２０は、第１の条件（例えば、出力値Ｆ１の「符号」）を生成し、前記第１の条件を第１のマルチプレクサ５３０に渡す。第１のマルチプレクサ５３０は、定数値「０００１」を第１の入力５３３で受け取り、定数値「００００」を第２の入力５３５で受け取る。第１の条件が「１」の場合、第１のマルチプレクサ５３０は、第１の入力５３３を選択して出力５３７に提供し、それ以外の場合、第１のマルチプレクサ５３０は、第２の入力５３５を選択して出力５３７に提供する。
【００５４】
第２のクラスタ５５０は、第２のＡＬＵ５６０を備えている。第２のＡＬＵ５６０は、第２の条件（例えば、出力値Ｆ２の「符号」）を生成し、前記第２の条件を第２のマルチプレクサ５７０に渡す。第２のマルチプレクサは、出力５３７からの値を第１の入力５７３で受け取り、定数値「００００」を第２の入力５７５で受け取る。第２の条件が「１」の場合、第２のマルチプレクサ５７０は、第１の入力５７３を選択して出力５７７に提供し、それ以外の場合、第２のマルチプレクサ５７０は、第２の入力５７５を選択して出力５７７に提供する。
【００５５】
第１の条件および第２の条件の関数として表されたこの回路の出力を、次の表１に示す。
【００５６】
【表１】
2005531952.tif 000003
【００５７】
表１からわかるように、図５の条件処理回路は、２つの条件Ｓ１およびＳ２の論理ＡＮＤを出力として生成する。その他の論理関数も、同様に生成することが可能である。
【００５８】
図６に示すように、第１のクラスタ５１０および第２のクラスタ５５０は、データ経路制御回路を実装するように構成されている。第１のＡＬＵ５２０は、上述のセレクト信号を生成して、第１のマルチプレクサ５３０に送る。第１のマルチプレクサ５３０は、加算（「ＡＤＤ」）インストラクション値に対応するデータ入力信号を第１の入力５３３で受け取り、減算（「ＳＵＢ」）インストラクション値に対応するデータ入力信号を第２の入力５３５で受け取る。これらのデータ入力は、上述のように、通常は複数ビットの信号である。セレクト信号の値に基づいて、第１のマルチプレクサ５３０は、ＡＤＤまたはＳＵＢインストラクション値のいずれかを、第２のＡＬＵ５６０のインストラクション入力５６２に送る。第２のＡＬＵ５６０の出力は、したがって、第１のＡＬＵ５２０により生成された条件によって、Ａ２＋Ｂ２またはＡ２−Ｂ２のいずれかになる。このように、第１および第２のクラスタ５１０、５５０を含むアレイ内のデータ経路は、第２のＡＬＵ５６０により実行される関数を変更することにより制御される。第１のＡＬＵ５２０および第１のマルチプレクサ５３０への、データおよびインストラクション入力を変えることにより、所望される任意のデータ経路制御関数を実装することが可能である。
【００５９】
図７〜８に示すように、クラスタ３００に出力レジスタを追加して、追加の有用な回路を作製することが可能である。これらの回路は、データのシリアル−パラレルおよびパラレル−シリアル変換のためのデータフォーマッティングを実行するために有用である。図７の回路は、上述のＡＬＵ１００およびマルチプレクサ２００を備えている。さらに、レジスタ７００が、マルチプレクサ２００の出力２３０に接続されている。レジスタ７００は、マルチプレクサ２００の出力２３０から読み込まれた値を記憶する。スイッチ７１０は、マルチプレクサの出力２３０またはレジスタの出力７２０のいずれかを、その先にある他の要素に送るように適合されている。スイッチ７１０は、アレイ上へのアプリケーションの構成の一部として設定される。代替の実施形態では、ＡＬＵ１００の出力１６０に第２のレジスタが対応するスイッチとともに、または対応するスイッチなしで接続される。
【００６０】
図８Ａおよび８Ｂは、クラスタ３００を利用して実装可能な有用なレジスタ回路の実装を示す。図８Ａは、「イネーブル付きレジスタ（ｒｅｇｉｓｔｅｒ  ｗｉｔｈ  ｅｎａｂｌｅ）」回路の実装であり、図８Ｂは、「リセット付きレジスタ（ｒｅｇｉｓｔｅｒ  ｗｉｔｈ  ｒｅｓｅｔ）」回路の実装である。図８Ａの「イネーブル付きレジスタ」回路により提供されるレジスタでは、クロックエッジでイネーブル（ＥＮＡＢＬＥ）がアクティブの場合にのみ、レジスタ内容が（「入力（ＩＮＰＵＴ）」の値で）更新され、それ以外の場合は、記憶された値がリサイクルされ、出力は変更されない。図８Ｂの「リセット付きレジスタ」回路は、リセット信号（ＲＥＳＥＴ）が非アクティブである限り、「入力（ＩＮＰＵＴ）」の値をレジスタに提供する。リセット信号がアクティブになると、次のクロックエッジで、値０がレジスタに読み込まれる。これらのレジスタオプションは、いずれも、アプリケーション内で一般に使用される。したがって、これらの回路は、再構成可能アレイを用いてアプリケーションを実装するときに有用である。そして、図７の「マルチプレクサおよびレジスタ」配置を利用して容易に構築可能である。
【００６１】
例えば次に示すような、マルチプレクサの可能な用途の多くは、マルチプレクサへの入力の１つまたは両方が定数値となっているものを備えている。
ＡＮＤ、ＯＲ、またはＮＯＴゲートの実装
第１汎用ルーティングネットワークへのキャリーアウト値の伝達、または
リセット可能レジスタの実装
【００６２】
これらの用途は、マルチプレクサ２００の入力に入力選択論理を追加することにより簡単になる。入力選択論理は、マルチプレクサのサイズは増加するが、ルーティングネットワークを通して伝えられる信号の数は減少するというトレードオフの関係である。図９に示すマルチプレクサ２００は、第１の入力２１０および第２の入力２２０にそれぞれ接続された、第１の入力マルチプレクサ９１０および第２の入力マルチプレクサ９２０を有する。第１の入力マルチプレクサ９１０は、第１の入力値９１３（ＩＮＰＵＴ）又は第１の定数値９１７（ここでは値「０００１」）を第１の入力２１０に提供するように適合されている。第２の入力マルチプレクサ９２０は、第２の入力値９２３（ＩＮＰＵＴ）又は第２の定数値９２７（ここでは値「００００」）を第２の入力２２０に提供するように適合されている。入力マルチプレクサ９１０、９２０は、アプリケーションにより動的に制御されることは意図されていない。入力マルチプレクサ９１０、９２０の制御信号は、アプリケーションがアレイ内に読み込まれる際に設定され、その後は変化しない。アレイに対するより高いレベルの制御が所望される代替の実施形態では、入力マルチプレクサ９１０、９２０は動的に制御可能である。
【００６３】
入力マルチプレクサ９１０、９２０は、その他の信号（定数または変数）を含むように拡張されてもよい。例えば、図１０に示すように、第２の入力マルチプレクサ９２０への入力としてフィードバック信号を追加することにより、第２の入力マルチプレクサ９２０は拡張される。したがって、第２の入力マルチプレクサ９２０は、図８Ａの「イネーブル付きレジスタ」回路を実装するために、第２の入力２２０へのフィードバック経路１０１０を形成するように構成することが可能である。同様に、図１１に示すように、ＡＬＵ１００のキャリーアウト出力１５０からのキャリーアウト信号（ＣＡＲＲＹ  ＯＵＴ）を第１の入力マルチプレクサ９１０に提供することにより、第１の入力マルチプレクサ９１０は拡張される。第１の入力マルチプレクサ９１０への入力の幅が、キャリーアウト出力１５０の幅よりも広い場合、キャリーアウト信号にゼロが補足される。したがって、例えばキャリーアウト信号「１」は、第１の入力マルチプレクサ９１０に提供される場合、ゼロで補足されて「０００１」となる。したがって、適切に構成されている場合、第１の入力マルチプレクサ９１０は、キャリーアウト出力１５０を、第１の入力２１０を介して、マルチプレクサ２００に提供する。これにより、キャリーアウト信号を第１汎用ルーティングネットワークに提供するための、別の経路が提供される。キャリーアウト信号は、セレクト入力１７０を介してマルチプレクサ２００ですでに利用可能であり、したがって、それにより第１汎用ルーティングネットワークに伝えられることが可能であるが、この変更により、イネーブル付き（または、図８Ｂの回路を変更することにより、リセット付き）キャリーレジスタを、１つのマルチプレクサ２００および１つのレジスタ７００（存在する可能性のある入力マルチプレクサは考慮に入れない）の中で作製することが可能になる。リセット可能キャリー出力レジスタは、シリアル算術演算アプリケーションに有用である。
【００６４】
図１２に示すように、図１１の回路のさらなる有用な変更は、レジスタ７００またはマルチプレクサ２００の出力のうちの１ビットが、ＡＬＵへの専用キャリー入力として利用されることを可能にすることである。マルチプレクサ２００の４ビット出力２３０からの１ビットが、ＡＬＵ１００のキャリーイン入力１４０に接続された入力マルチプレクサ１２１０に送られる。これにより、キャリーアウト出力１７０からキャリーイン入力１４０へのレジスタ付き経路が作製される。そのような経路は、シリアル化された算術演算回路（特に、上述のようなレジスタ７００をリセットする機能と組み合わされている場合）を作製する際に有用である。
【００６５】
図１０〜１２は、スイッチ７１０の出力に接続された、第２の入力マルチプレクサ９２０へのフィードバック経路を示す。あるいは、フィードバック経路は、スイッチ７１０の前の、レジスタ７００の出力に接続されていてもよい。ただし、スイッチ７１０の後に前記接続をなすことにより、レジスタなしの経路を選択し、それにより非同期ラッチを構築することが可能になる。
【００６６】
図１３は、クラスタ３００の基本回路のさらに別の拡張を示す。マルチプレクサ２００の出力２３０にインバータ１３１０を追加することにより、マルチプレクサ２００により生成可能な関数の範囲が増加する。マルチプレクサ２００は、ＮＡＮＤおよびＮＯＲゲートを提供することが可能である。
ＮＡＮＤ（Ａ,Ｂ）＝ＮＯＴ（Ａ？Ｂ：０）
ＮＯＲ（Ａ,Ｂ）＝ＮＯＴ（Ａ？１：Ｂ）
【００６７】
さらに、これにより、出力反転を実装するための代替の方法が提供される。
ＮＯＴ Ａ＝Ａ？０：１            −この形態はインバータを使用しない
ＮＯＴ Ａ＝ＮＯＴ（１？Ａ：０）  −この形態はインバータを使用する
【００６８】
後者のオプションでは、Ａ信号を、セレクト入力２４０ではなく、マルチプレクサ２００のデータ入力２１０、２２０に接続する。これは、データ入力２１０、２２０とセレクト入力２４０に対して異なるルーティング遅延がある場合に、好ましい可能性がある。
【００６９】
さらに、１つの入力が反転された関数を実行するための、代替の方法が提供される。
Ａ＆（ＮＯＴ Ｂ）＝Ｂ？０：Ａ    −この形態はインバータを使用しない
Ａ＆（ＮＯＴ Ｂ）＝ＮＯＴ（（ＮＯＴ Ａ）ＯＲ Ｂ）
＝ＮＯＴ（Ａ？Ｂ：１）
【００７０】
これによっても、関数を実装するためにどちらのマルチプレクサ入力を使用するかについての柔軟性が増加する。
【００７１】
上述の回路は、本発明の実施形態のクラスタ３００を使用して実装可能な、広範な回路の例にすぎない。
【００７２】
上で説明したクラスタ３００を含む異種アレイは、ＡＬＵのみによる同種アレイよりも小さく、かつ、より高速な、多くの回路を実装することができる。マルチプレクサは、ＡＬＵよりもかなり小さく、かつ、高速であるため、マルチプレクサを利用できる回路は、ＡＬＵのみにより構成されている同等の回路よりも小さく、かつ、高速である。条件処理、データフォーマッティング、およびインストラクション選択などの動作はすべて、ＡＬＵのみを使用するよりも、マルチプレクサとＡＬＵを混合して使用した方が、より効率的に実装される。
【００７３】
異種相互接続を備えたアレイを使用することにより、速度は向上する。第１汎用ルーティングネットワークは、アレイ内の要素間でのデータおよびインストラクションのルーティングのために提供される。さらに、追加の相互接続は、ＡＬＵとマルチプレクサとの間でセレクト信号をルーティングするためのマルチプレクサ制御ネットワークを提供する。このマルチプレクサ制御ネットワークは、クラスタ内のＡＬＵと１つまたは複数の関連するマルチプレクサとの間の単純な直接接続であってもよく、あるいは、ＡＬＵのセレクト出力を、同じクラスタ内のマルチプレクサ、他のクラスタ内のマルチプレクサ、または両方に接続するように適合された、より複雑な制御ネットワークであってもよい。この制御ネットワークは、第１汎用ルーティングネットワークとは分離した、第２汎用ルーティングネットワークの形態を取っていてもよく、そして、データおよびインストラクションではなく、マルチプレクサ制御信号を運ぶために最適化されていてもよい。
【００７４】
一実施形態の異種アレイは、要素タイプの適切な混合を決定する際の問題を大幅に減少させる。マルチプレクサは、ビットレベル論理、データの再フォーマッティング、および動的なインストラクション選択などの、広範なアプリケーション論理コンポーネントの実装に有用である。したがって、設計者が異種アレイ上に実装を希望する可能性があるほとんどのアプリケーションには、マルチプレクサを利用することはある程度可能である。
【００７５】
ただし、マルチプレクサは、それが有用な関数を実装するための唯一の手段ではない。マルチプレクサで実装できる任意の関数は、ＡＬＵを利用して実装することも可能である。マルチプレクサは、通常、より効率的な実装であるにすぎない。したがって、アプリケーションは、３つのタイプの論理コンポーネントに分けることができる。
１．ＡＬＵに実装することが好ましい論理
２．マルチプレクサに実装することが好ましい論理
３．実装の選択肢がある論理
【００７６】
これらのカテゴリのいずれか、またはすべては、カテゴリ内の相対的な優先レベルを示すサブカテゴリを備えていてもよい。これらのサブカテゴリは、アレイ内で提供される処理要素の特定の混合比と各カテゴリ内の論理コンポーネントのさまざまな量に基づいて、処理要素への論理コンポーネントの割り当てを微調整するために利用される。
【００７７】
第３のカテゴリの存在は、すべてのアプリケーションのための十分なマルチプレクサ（またはＡＬＵ）が常にあることを保証する、ＡＬＵ対マルチプレクサの「完全な」比率を見いだす必要はないということを意味している。その代わりに、処理要素内への論理コンポーネントの割り当て方法を決定する際には、図１４の方法が利用される。ステップ１４１０において、第１の処理要素タイプ内に実装されることが好ましい論理コンポーネントが識別され、第１のタイプの処理要素に割り当てられる。カテゴリ内の相対優先度を示すサブカテゴリがある場合は、最も優先度の高いコンポーネントが最初に割り当てられる。
【００７８】
ステップ１４２０において、第２の処理要素タイプ内に実装されることが好ましいコンポーネントが識別され、第２のタイプの処理要素に割り当てられる。カテゴリ内の相対優先度を示すサブカテゴリがある場合は、最も優先度の高いコンポーネントが最初に割り当てられる。
【００７９】
ステップ１４３０において、残りの論理コンポーネントが、ヒューリスティックに従って、第１および第２のタイプの残りの処理要素間に割り当てられる。例えば、残りの論理コンポーネントは、残っている第２のタイプの要素がなくなるまで、第２のタイプの要素に割り当てられ、次に、第１のタイプの要素に割り当てられる。あるいは、残っている要素は、サブカテゴリにより分割され、第２のタイプのための相対優先度を有する論理コンポーネントは第２のタイプに、第１のタイプのための相対優先度を有する論理コンポーネントは第１のタイプ割り当てられる。
【００８０】
（セレクト信号出力）
上述のように、ＡＬＵ１００（図１に示す）のセレクト信号出力１７０は、さまざまな異なる信号のうちの任意のものを含むことが可能である。図１５に示す、マルチプレクサ２００を制御するために使用される制御信号を生成および選択するための、選択回路の例１５００について、以下で詳しく説明する。選択回路１５００は、ＡＬＵ１００からのステータスビット（まとめて、ＡＬＵステータスワード（ALU STATUS WORD:ASW）と呼ばれる）を受け取るように適合された、複数のステータス入力１５１０を備えている。ステータス入力１５１０のそれぞれは、符号、オーバーフロー、キャリーアウトなどの特定のステータス信号を示すビット、またはインストラクション入力１３０からのビット、またはマルチプレクサ２００の制御に役立つその他の任意のデータを運ぶ。
【００８１】
選択回路１５００は、さらに、複数のマスク入力１５２０（まとめて、マスクワードと呼ばれる）を備えている。マスク入力１５２０は、マスク値を受け取るように適合されている。マスク値は、ＡＬＵステータスワードのステータスビットのうちの１つまたは複数をマスキングするために利用される。マスク入力１５２０は、それらのマスク値を、広範なソースから受け取ってもよい。例えば、マスク入力１５２０は、第１汎用ルーティングネットワークに接続されていてもよく、それにより、アレイ内の他の処理要素から動的にマスク値を受け取ってもよい。あるいは、マスク入力１５２０は、特定のアプリケーション用にアレイが構成されている場合にアレイ内に読み込まれるマスク値などの、マスク値を記憶するローカルメモリセルに接続されていてもよい。
【００８２】
ステータス入力１５１０とマスク入力１５２０は、入力１５１０、１５２０に対してビットごとのＡＮＤを実行するように適合された、複数のＡＮＤゲート１５３０に接続されている。ＡＮＤゲート１５３０は、ＯＲゲート１５４０に全て接続されている。ＯＲゲート１５４０は、ＡＮＤ演算が実行された値を一緒にして単一ビットの出力を形成し、マルチプレクサ２００を制御するために、マルチプレクサ２００のセレクト入力２４０に提供する。
【００８３】
マスクワードをすべて０に設定するということは、セレクト入力２４０に送られるマルチプレクサ制御信号が０になるということ、つまり、マルチプレクサ２００は第２の入力２２０の値を出力２３０に常に供給するように固定されるということを意味している。ＡＳＷのビットのうちの１つが常に１の場合、マスクワードでこのビットを選択するということは、制御信号が１になるということ、つまり、マルチプレクサ２００は第１の入力２１０の値を出力２３０に常に供給するように固定されるということを意味している。すべて０の場合と組み合わせて、これは、マルチプレクサ制御信号を常に０または常に１に設定する機能を提供する。
【００８４】
常に０および常に１の両方を可能にする代替の方法は、図１６に示すように選択回路１５００を拡張することである。ＯＲゲート１５４０の出力を反転できるように、ＯＲゲート１５４０の出力にＸＯＲゲート１６１０を配置することにより、選択回路１５００は拡張される。ＸＯＲゲート１６１０への他方の入力は、アレイの構成中に値が読み込まれるデータソース１６２０に接続されている。データソースから読み込まれる値が「１」の場合、ＸＯＲゲート１６１０はインバータとして動作し、ＯＲゲート１５４０からの出力値を反転する。データソースから読み込まれる値が「０」の場合、ＸＯＲゲート１６１０は、ＯＲゲート１５４０の出力を伝える。したがって、ＸＯＲゲート１６１０は、「イネーブル付きインバータ」として機能する。この動作を表２に示す。
【００８５】
【表２】
2005531952.tif 000004
【００８６】
したがって、セレクト入力２４０に、常に０が送られることを所望する場合は、マスクワードはすべて０に設定され、データソース値は０に設定される。セレクト入力２４０に、常に１が送られることを所望する場合は、マスクワードはすべて０に設定され、データソース値は１に設定される。この代替方法は、また、マスクワードのすべての値に対して、ＯＲゲート１５４０の出力が反転されることを可能にする。
【００８７】
これは、マルチプレクサ２００への制御の極性を変更することが可能であることを意味している。インバータがアクティブになっている場合、ＯＲゲート１５４０からの「１」出力によって、第１の入力２１０の代わりに第２の入力２２０が選択され、そして、ＯＲゲート１５４０からの「０」出力によって、第２の入力２２０の代わりに第１の入力２１０が選択される。これは、マルチプレクサ２００が、マルチプレクサ２００の入力２１０、２２０への非対称な接続を有している場合に有用である。このような例は、レジスタ出力からのフィードバック経路が、入力２１０、２２０のうちの１つのみに接続されている場合、又は入力２１０、２２０のうちの１つのみで専用の一定入力が得られる場合である。
【００８８】
（ＡＬＵステータスワードの可能な内容）
ＡＳＷは、例えば、以下の値のいずれか、またはすべてを表すビットを備えることが可能である。
ＡＬＵのキャリーイン
ＡＬＵのキャリーアウト
ＡＬＵの「オーバーフロー」（オーバーフローの２の補数定義を使用）
ＡＬＵの「正しい符号」（再び、２の補数定義に従う）
ＡＬＵのデータ入力１１０、１２０から直接取られた１つまたは複数のビット
ＡＬＵのインストラクション入力１３０から直接取られた１つまたは複数のビット
【００８９】
ＲＡＡ設計の１つの例では、ＡＬＵのインストラクション値は、ＡＬＵ内のレジスタに記憶されることが可能であり、その場合、インストラクション入力１３０は、専用のマルチプレクサ制御入力として使用することが可能である。これは、インストラクション入力１３０が、上のリスト内の「インストラクション入力からのビット」および「データ入力からのビット」の両方をカバーするために使用できるということを意味している。したがって、このリストの有用なサブセットは、キャリーアウト、正しい符号、およびＡＬＵインストラクション入力１３０からの２ビットを備えている。
【００９０】
このサブセットは、マルチプレクサ制御信号が、例えば、次のいずれかであってもよいことを意味している。
符号なし比較（より小さい、より大きい）の結果、キャリーアウト経由
符号付き比較（より小さい、より大きい）の結果、符合信号経由
符号拡張に使用される、符号付き算術演算の符号（再び、符号信号経由）
符号なし算術演算からのオーバーフロー（再び、キャリーアウト経由）
等値テストの結果（キャリーアウト経由で等値テストの結果を報告するＡＬＵ設計用）
インストラクション入力１３０から導かれたビット、２インストラクションビットの選択肢を有する（やはり、「データ入力からのビット」オプションをカバー）
【００９１】
したがって、このサブセットは、アプリケーション内でよくテストされる条件のいくつかをカバーする。以下で詳しく説明するように、ＲＡＡは一般に、ワード長管理のために異なるアプローチを使用するので、ＲＡＡアプリケーション内では一般的ではない符号付き算術オーバーフローは、算術演算結果の正しい符合およびＭＳＢから合成されることが可能である。
【００９２】
（インストラクションビットの可能な選択肢）
インストラクション入力１３０のいずれのビットがＡＳＷ内で得られるようにすべきかの選択肢としては、以下の例がある。
【００９３】
１．インストラクションのＬＳＢおよびＭＳＢ
ＬＳＢは、キャリー値が正しい数値を有していることを意味するので（キャリーがある場合は１、ない場合は０）、ルーティングネットワークでキャリーを伝えるために使用されるビットである。インストラクション入力１３０を介してキャリーを接続できるということは、マルチプレクサ２００が、ローカルのＡＬＵ１００からのキャリーによって、そしてさらに、アレイ内の他の任意のＡＬＵ１００からのキャリーによって（間接的に）、制御されることが可能であることを意味している。
【００９４】
ＭＳＢは、同様の理由により選択される。ＭＳＢは、ワード内の符号ビットなので、これを選択できることにより、符号データの選択に関する柔軟性が得られる。
【００９５】
２．インストラクションのＬＳＢ、およびインストラクションのビットｎ／２（つまり、４ビットワードではビット２、６ビットワードでは３、．．．）
ＬＳＢは、上の選択肢＃１と同じ理由で選択される。
【００９６】
ワードの中央のビットを選択することにより、（複数のＡＬＵ１００のインストラクション入力１３０を、一連のシフトまたはローテートとともに使用して）ワードからすべてのビットを個別に抽出することが容易になる。
ビット０およびｎ／２を抽出
１桁左にローテート
ビット０およびｎ／２を抽出（ビットｎ−１およびｎ／２−１と同等）
１桁左にローテート
ビット０およびｎ／２を抽出（ビットｎ−２およびｎ／２−２と同等）
１桁左にローテート
以下同様
という反復シーケンスにより、ｎ／２のローテートで、ｎビットすべてを抽出するための、効率的な、定型の方法が得られる。これが機能するためには、使用されるビットがインストラクションワード内で均一の間隔を空けられていなければならず、また、ビット０は他の理由のために有用なので、その他のビットは、ビット０から半ワード上になる。
【００９７】
ＡＳＷの、代替の有用なサブセットは、インストラクション入力１３０の４ビットとＡＬＵのキャリー出力１５０を備えた５ビットワードである。このサブセットには、次の利点がある。
１．キャリーアウトは、上述のように、符号なし比較とオーバーフローを提供する。
２．インストラクション入力１３０のすべてのビットを利用可能にすることにより、ワードから取られた任意のビットを使用してマルチプレクサ２００を制御することが可能になる。これにより、ワード内のビットの任意関数の構築が比較的簡単になる（特に、上述のように、マルチプレクサ２００の使用と組み合わせて論理ゲートを構築する場合）。
【００９８】
ワードから任意のビットを抽出する機能により、符号拡張の実行が容易になり、したがって、符号付きオーバーフローが発生しないことを保証することが容易になる。
【００９９】
（状態符号化）
ＡＬＵステータスワードのいずれのビットがセレクト入力２４０に接続されるべきかを選択するために、ｎビットのマスクを使用することは、使用されてもよい可能な組み合わせが２ｎあることを意味している。実際には、いくつかの組み合わせは、他の組み合わせよりもはるかに一般的ではなく、また、いくつかの組み合わせは決して使用されない。
【０１００】
上で概説した４ビットＡＳＷの例を使用すると、以下の表３に示すように、１６の可能な組み合わせがある。最初の４列はマスク値を示し、５番目の列は、セレクト入力２４０に送られる結果的な出力関数を示す。
【０１０１】
【表３】
2005531952.tif 000005
【０１０２】
両方のインストラクションビットが使用される行は、非常にまれであり、キャリーおよび符号の両方が使用される行は、実際には決して発生しない。「キャリー  ＯＲ  符号」は、通常のアプリケーションで発生する制御関数ではない（その理由は、符号は、キャリーとのＸＯＲをすでに備えているからである）。さらに、２つのインストラクションビットは、使用される可能性が同等ではなく、ＬＳＢの方が、ＭＳＢよりもよく使用される（インストラクションと、キャリーまたは符号との組み合わせの場合は特にそうである）。
【０１０３】
したがって、より少ないビットで符号化できる、この表の「よく使用される」サブセットを識別することは、マスクおよびＡＳＷを組み合わせるためのより複雑な論理回路を利用することによって可能である。例えば、表内の、８つのより一般的な状態は、３ビットで符号化できる。ただし、必要とされる復号化は、はるかに複雑なものとなる。代替の方法は、一般的な状態の復号化を容易にするために、４ビットの符号化を維持し、一般的でない状態は、代替の便利な機能を符号化するために使用することである。この例について、以下で説明する。
【０１０４】
（高ファンアウト制御信号）
多くのアプリケーションは、アプリケーション全体にわたって広く使用される、少数の制御信号を含んでいる。例えば、次のようなものがある。
「グローバルリセット」
「グローバルイネーブル」
パイプライン機能停止／イネーブル
【０１０５】
これらの信号は、一般に、レジスタの、リセットまたはイネーブル入力のいずれかに接続される。したがって、これらの信号は、ＲＡＡ内のマルチプレクサ２００のマルチプレクサセレクト入力２４０に接続されることが期待される種類の信号である。
【０１０６】
これらの信号は、また、従来の再構成可能デバイス内の汎用ルーティングネットワークによって十分にサポートされていない。これらのネットワークは、一般に、アプリケーション内のデータフローに特有のルーティングパターンを処理するように最適化されており、通常は、これらのグローバル制御信号のファンアウトよりもはるかに低いファンアウトを有する。「ファンアウト」は、特定の出力により駆動される、他の処理要素の入力の数である。ｎ入力処理要素から構築される再構成可能デバイス内の平均ファンアウトは、≦ｎである（すべての入力は、出力または一定の信号により駆動されるため）。ＦＰＧＡおよびＲＡＡでは、通常、ｎ≦４であり、それに対して、高ファンアウト信号は、その何倍ものファンアウトを容易に有することが可能である。一部のデバイスは、いくつかの高ファンアウト信号をアレイ上で長距離にわたって迅速にブロードキャストするために、それらのルーティングネットワークに専用の高ファンアウト接続を追加する。ただし、これらの専用接続は、やはり、効果的な方法でクラスタ３００に接続される必要がある。これらの高ファンアウト信号をサポートするための代替の方法は、マルチプレクサセレクト入力２４０に効率的に接続することが可能な、第２汎用ルーティングネットワークを追加することである。この代替の方法について、以下でさらに説明する。
【０１０７】
上述の回路１５００は、（上記の第２汎用ルーティングネットワークなどの）さまざまなネットワークへの効率的な接続を含むように拡張可能であり、その拡張は、上で説明したＡＳＷ符号化方式の一般的でない部分を利用することによって可能である。
【０１０８】
図１７に示すように、「全マスクビットセット」状態は、マルチプレクサ制御経路への代替入力を選択するために利用可能である。拡張された回路１５００は、マスク入力１５２０から入力を引き込む４入力ＡＮＤゲート１７１０を備えている。４入力ＡＮＤゲート１７１０の出力は、マルチプレクサ１７２０のセレクト入力に接続されている。マルチプレクサ１７２０は、第１の入力１７３０を、高ファンアウトネットワークから受け取り、第２の入力１７４０を、回路１５００から受け取る。上述のように、マルチプレクサ２００のセレクト入力２４０にセレクト信号を伝達するために、マルチプレクサ１７２０は、ＸＯＲゲート１６１０への出力を提供する。
【０１０９】
マスク入力１５２０が、すべて１に設定されている場合（表３の最終行）、４入力ＡＮＤゲート１７１０の出力はハイ（１）になり、それにより、マルチプレクサ１７２０は、高ファンアウトネットワークからの第１の入力１７３０を選択して、ＸＯＲゲート１６１０を介して、マルチプレクサ２００にセレクト信号を提供する。したがって、マルチプレクサ２００は、高ファンアウトネットワークで送られる信号によって制御される。
【０１１０】
マスク入力１５２０が、他の任意の値に設定されている場合、４入力ＡＮＤゲート１７１０の出力はロー（０）のままになり、それにより、マルチプレクサ１７２０は、回路１５００からの第２の入力１７４０を選択して、ＸＯＲゲート１６１０を介して、マルチプレクサ２００にセレクト信号を提供する。したがって、マルチプレクサ２００は、上述のようにＡＬＵ１００により制御される。
【０１１１】
任意選択で上述のように拡張される回路１５００などのＡＳＷ処理論理は、また、高ファンアウト制御ネットワークに提供される高ファンアウト制御信号の有用なソースでもある。「グローバル」制御信号は、通常、「ローカル」制御信号と同様の方法で導かれて、単に、アレイのより大きな部分に提供される。したがって、回路１５００の出力も、高ファンアウト制御ネットワークに送られる。前記出力は、図１７に示すように、高ファンアウト制御ネットワークに直接送られてもよく、あるいは、前記出力は、最初にマルチプレクサ１７２０を通して、マルチプレクサ１７２０の出力に作製された高ファンアウトネットワークへの接続に送られてもよい。この代替の接続により、高ファンアウト出力が、代わりに高ファンアウト入力から導かれることが可能になる。
【０１１２】
ＡＳＷ選択表（表３）からの複数の「一般的でない」状態を復号して、高ファンアウトネットワークからの複数の入力の間で選択する、この回路の変形が可能である。あるいは、これらの複数の一般的でない状態は、高ファンアウト出力を駆動するための状態を選択するために使用されてもよい。
【０１１３】
高ファンアウト出力が高ファンアウトネットワークに接続されることが可能な、いくつかの方法がある。有用な方法は、デバイスの構成状態の一部（例えば、専用の構成ビット）によって駆動されるトライステートイネーブルを備えたトライステートバッファを介して接続を形成することである。この接続形態は、複数のソースが高ファンアウト導線を駆動できるという利点を有する。しかし、タイミングはどれが実際に使用されているかとは無関係である。これは、高ファンアウトネットワークのタイミングをルーティングソフトウェアが解析するのを容易にする。
【０１１４】
（高ファンアウト制御ネットワーク）
上の項では、高ファンアウト制御信号の有用性、およびマルチプレクサ制御回路１５００にそれらの信号を接続する方法の例について説明した。本項では、汎用ルーティングネットワークを作製するために、高ファンアウト接続導線が使用するための有用な接続パターンの例を示す。
【０１１５】
再構成可能アレイ内の処理要素は、完全に実装されているか、または部分的に実装されているＸ−Ｙグリッド上の、行および列内に配置されている（例えば、チェッカー盤またはチェス盤状配置）と仮定する。そのようなアレイ上では、一般的なマルチプレクサ制御信号を共有する要素は、次のように配置できる可能性がある。
行内、または、
列内、または、
ほぼ四角形の区画内
（高ファンアウト制御信号は、ビットスライス（またはサブワードスライス）スタイルのレイアウトを有するデータ経路を制御するために使用されているという仮定に基づく）
【０１１６】
これらのパターンは、すべて、基本的に四角形の構造の変形である。したがって、高ファンアウト導線がこれらのパターンを効率的に構築できるということは有用である。そのようなパターンを構築する高ファンアウトネットワークの例を、以下に示す。
【０１１７】
１．アレイは、水平および垂直の両方の方向の高ファンアウト導線を含む。
【０１１８】
２．独立したそれぞれの高ファンアウト導線は、水平または垂直のいずれかに（つまり、行または列に沿って）伸び、交差するすべてのＡＬＵ１００に接続される。導線は、行（列）全体に沿って伸びていてもよく、またはその一部のみに沿って伸びていてもよい。
【０１１９】
３．高ファンアウト導線は、上で示したように、マルチプレクサ制御回路１５００に接続され、以下の追加の制約条件を有する。
【０１２０】
ＡＬＵ１００ごとにマルチプレクサ２００が１つ以上ある場合、各回路１５００は、直行する導線に接続された高ファンアウト導線からの入力、および直行する導線に接続された高ファンアウト導線への出力を有する（つまり、入力は垂直から、出力は水平へ、またはその逆）。
【０１２１】
ＡＬＵ１００ごとにマルチプレクサ２００が１つだけある場合、回路１５００は、高ファンアウトネットワークから、又は高ファンアウトネットワークへの入力および出力を、垂直および水平の両方の高ファンアウト導線に接続できなければならない。
【０１２２】
導線は自然に水平または垂直方向に伸びるので、上述のように行および列接続を形成するのは容易である。さらに、水平の導線から入力し、垂直の導線に出力すること（またはその逆）ができることによって、２次元の区画を作製することが可能になる−水平の導線を、交差する複数の垂直の導線に接続することができる。
【０１２３】
導線がアレイ全体にわたって伸びていない状況では、それらの端はずらされていなければならない−つまり、隣接する列（および行）の平行な導線の端は、一致していてはならず、相互に食い違っていなければならない。４つのＡＬＵ１００にまたがる制御導線（通常のＲＡＡ用語では「レングス４（Ｌｅｎｇｔｈ  ４）」導線）の場合を考慮する。列０では、これらの導線は、ＡＬＵ０からＡＬＵ３まで、ＡＬＵ４からＡＬＵ７まで、などのように伸びることが可能であり、そして、列１内では、これらの導線は、ＡＬＵ２からＡＬＵ５まで、ＡＬＵ６からＡＬＵ９まで、などのように伸びることが可能である。これらの導線の範囲は部分的に重なるので、それらは水平の制御導線によって接続されることが可能であり、それにより、２本の導線による合計の垂直到達距離は、１本の導線のみによる距離よりも大きくなる。
【０１２４】
図２０に示すようなチェッカー盤状配置は、奇数列を除き、偶数行にＡＬＵがない（またはその逆）という特性を有する−それらの位置は、ＡＬＵの間の空間により、あるいは、より一般的には、ルーティングネットワークをサポートするハードウェアにより占められている。上述の接続パターンにより、結果として、２つの独立した制御ネットワーク２０１０ａおよび２０１０ｂが作製される（１つは、奇数番の行および列のＡＬＵ２０００を結び、もう１つは、偶数番の行および列のＡＬＵ２０００を結ぶ）。図２０で、ＡＬＵ２０００の間の線は、制御ネットワークの接続を表す。ＡＬＵ２０００内で交差する線は、制御ネットワーク２０１０ａ、２０１０ｂを形成するために相互に接続可能である。ＡＬＵ２０００の外部で交差する線は、制御ネットワーク２０１０ａ、２０１０ｂを形成するために相互に接続可能ではない。２つの独立した制御信号を配送するために、２つのネットワークが使用される場合、これは許容できる状況であり得る。あるいは、これらの２つのネットワーク２０１０ａ、２０１０ｂの間の接続を提供するのが有用であることが見いだされる可能性もある。それらが交差する点は、チェッカー盤のルーティング領域の上にあるため、必要に応じてこの接続をサポートするのは容易である。
【０１２５】
汎用ルーティングネットワーク２０１０ａ、２０１０ｂは、上述の第１汎用ルーティングネットワークからは分離している。２０１０ａ、２０１０ｂから第１汎用ルーティングネットワークへの信号の伝達は、図４Ｂに関連して上で説明した方法で、マルチプレクサを制御することによってのみ可能である。
【０１２６】
（制御信号としての「符号」および「オーバーフロー」の有用性）
「符号」は、ＦＰＧＡ（またはＲＡＡ）ベースの再構成可能アレイのための制御信号として、特に有用である。これは、そのようなアレイと、オーバーフローを使用する傾向のある従来のプロセッサとの間の違いである。この理由については、以下に記載する。
【０１２７】
（オーバーフロー）
プロセッサは、ワード長に対しては、非常に限定された制御しか有しておらず、通常は、小さな範囲のワード長（例えば、８、１６、および３２ビット−２のべき乗の範囲が一般的）のみをサポートする。ＦＰＧＡおよびＲＡＡデバイスは、アレイを構成する処理要素の粒度のみによって制限される広範なワード長をサポートできる（つまり、アレイが４ビットの処理要素を有している場合、そのアレイは、４ｎ（ｎは正の整数）に等しいワード長を直接処理できる）。
【０１２８】
多くの算術演算アプリケーションは、「一般的な」データセットを使用して実行される場合、アプリケーション内で計算されるすべての中間データは特定のワード長に適合するという特性を有する。しかし、中間結果が適合しない、一般的でないデータセットも存在する。一般的なケースではサポートされているワード長のうちの１つに適合するが、一般的でないケースでは適合しない場合、これはプロセッサにとって重大な問題である。単純なプロセッサベースの実装では、そのため、次の望ましくない選択肢に直面する。
まれなケースに対処するのに十分大きなワード長を常に使用し、これを行うための効率の犠牲は受け入れること。
小さなワード長を使用し、ときには結果が間違っている可能性があることを受け入れること。
【０１２９】
効率の犠牲は、非常に大きい可能性がある。例えば、１６ビットから３２ビット実装に変更する場合、中間結果のために必要なメモリの量は２倍になり、主要なデータ経路のスループットは半減する可能性がある。しかし、たまにエラーが発生する可能性は、受け入れられない場合がある。
【０１３０】
幸いにも、この選択の必要を回避するために使用可能な次の第３の選択肢がある。
通常の状況では、小さなワード長を使用して実行するが、これにより間違った答えが与えられる状況を検出して、必要に応じて是正措置を取ることができるようにする（例えば、より広いワード長を使用して、計算の全部または一部を再実行する）。
【０１３１】
これにより、アプリケーションは、ほとんどの時間は小さなワード長の利点（メモリサイズ、データ経路のスループット）を得て、まれに必要となった場合にのみ、長いワード長バージョンの犠牲を払うようにすることができる。
【０１３２】
ほとんどのプロセッサは、したがって、計算の結果が書き込み先のワード長に適合しない場合を識別するオーバーフロー検出機構を有し、オーバーフローが発生した場合は、プログラムの別の部分に分岐することができる。「オーバーフロー」は、したがって、プロセッサにとって重要な概念である。
【０１３３】
ＦＰＧＡおよびＲＡＡベースの処理では、状況は大幅に異なる−よりきめの細かいワード長制御により、ワード長を拡張するコストははるかに低く、そして、分岐のコストははるかに高い。アプリケーションが、通常は１６ビットワードに適合し、ときには１８ビットを必要とすると仮定する。プロセッサは、これらのケースに対処するために、３２ビットワードを使用しなければならないが、４ビット処理要素を有するＲＡＡは、２０ビットのデータ経路を使用できる。したがって、最悪ケースの状況をサポートするための犠牲は、１００％ではなく、２５％の領域増加となる。
【０１３４】
上述のように、ＦＰＧＡおよびＲＡＡは、一般に、プログラム全体を通して可能なすべての経路についてのデータ経路を構築することによって分岐を実装する。次に、マルチプレクサを使用して、特定のデータセットのための正しい経路を選択する。１６ビットの主要データ経路を有し、一部の区間は２０ビットを使用して繰り返されており、さらに、それらの間で選択するための多重化を有する場合は、より広いデータ経路を単に全体にわたって使用する場合よりも、実装は大規模になるという結果がただちに得られる可能性がある。
【０１３５】
要約すると、プロセッサは、きめの細かいワード長制御には適していないが、分岐には適しているのに対して、ＦＰＧＡおよびＲＡＡは、ワード長制御はより優れており、分岐はより劣っている。オーバーフローの検出は、ワード長の問題を分岐に変換する方法であり、したがって、プロセッサにとって適切であり、ＦＰＧＡまたはＲＡＡにとっては適切ではない。
【０１３６】
（符号）
結果の符合を知ることは、アプリケーション内の２つの特定の演算で重要となる。
【０１３７】
比較：
Ａ＞Ｂは、ＢからＡを減算して、結果の符合を確認することにより実装できる（完全な値ではなく、結果の符合のみが重要である）。同様の方法が、他の比較（＜、≦、≧）にも有用である。
【０１３８】
符号拡張：
２の補数符号付き数のワード長を増加する場合、符号ビットがすべての追加されるビットにコピーされなければならない。これは、符号ビットが判明した後は、通常、単純な操作である。
【０１３９】
符号付きおよび符号なしの両方の数について、正しい結果が得られなければならない。「符号なし」のケースは、符号付き演算の特殊なケース（ｎ＋１ビットの符号付きの値の中に、ｎビットの符号なしの値が埋め込まれている）と見ることができる。２の補数表記法では、値−Ｘは（ＮＯＴ  Ｘ）＋１と表現され、最上位ビット（「ＭＳＢ」）の１が符号ビットを表す。したがって、次のようになる。
−２１０進＝ＮＯＴ（０１０２進）＋１２進＝１０１２進＋１２進＝１１０２進
【０１４０】
符号なし比較は、計算の最上位ビットからのキャリーアウトによって、常に正しく表現される。
【０１４１】
減算と、ＭＳＢからのキャリーアウトのテストによる符号付き比較は、算術オーバーフローが発生した場合は間違った結果を与える。これは、「キャリーアウト」および「オーバーフロー」信号の組み合わせを使用して、または、符号信号を直接生成することによって修正することができる。
【０１４２】
符号なし「符号拡張」は、問題とはならない−追加されるビットはすべて０である。
【０１４３】
符号付き符号拡張は、上述のとおりである−符号が、追加されるすべてのビットにコピーされる。
【０１４４】
上述の、プロセッサ、ＦＰＧＡおよびＲＡＡ内の、ワード長制御および分岐の異なる実装は、符号の計算方法および使用方法にも影響する。
【０１４５】
（プロセッサ）
プロセッサは、主な制御機構として分岐を使用し、そして、分岐を制御するために比較を使用する。これは、「比較および分岐」が組み合わされた命令を使用するか、または、「比較してフラグをセット」する命令および「フラグがセットされていれば分岐」する命令という独立した命令を使用するかの、いずれかにより実行される。したがって、比較演算と、上述のオーバーフロー処理の説明との間には、いくらかの類似性がある−両方とも、「演算を実行する」段階と、それに続く、「ある条件が発生した場合（つまり、オーバーフローがある場合、または、比較が真の場合）は分岐する」段階を有する。この類似性は、関心のある条件の組のうちのいずれが発生したか（算術オーバーフロー、計算が負の結果（つまり、「符号」）を生成した、最新のキャリーアウト値、など）を示す一組の「条件フラグ」と、前記フラグの特定のサブセットのうちの１つまたは複数がセットされている場合にジャンプする汎用分岐命令とを有するプロセッサを使用する場合、しばしば明白にされる。
【０１４６】
符号拡張は、通常、メモリからプロセッサにデータが読み込まれる際に行われる−読み込み先よりも小さなフォーマットでメモリに記憶されている場合は、読み込み操作において符号拡張を任意に選択して、記憶されている表現のＭＳＢを、プロセッサ内バージョンの追加ビット内に複製することができる。
【０１４７】
（ＦＰＧＡ）
分岐は、ＦＰＧＡ内では、非効率的な操作である。比較操作は、ＦＰＧＡ内では、マルチプレクサへの制御入力として、または、複数の条件を組み合わせるための論理ブロックとして使用される可能性がより大きい。ルーティングネットワークの１ビット性により、以下で与えられる正しい符号のための表現を直接実装することが容易になるので、符号の計算は簡単な操作である。
【０１４８】
ＦＰＧＡ内での符号拡張は、ルーティング操作であってもよい−ＦＰＧＡルーティングの１ビット性により、符号ビットを複数の宛先に容易に接続することが可能である。ただし、ｎビット入力とｎ＋１ビット出力とを有する演算子を実装することは容易なので、算術演算への入力を拡張する必要はないことが多い。
【０１４９】
（ＲＡＡ）
ＲＡＡは、プロセッサとＦＰＧＡとの間の中間のケースである−汎用の分岐はやはり非効率的（ただし、一部の制限された形態は、インストラクションの多重化により実装可能）であるが、ルーティングネットワークはビットベースではなくワードベースなので、符号およびオーバーフローのための式の直接実装はより複雑であり、ワード内のビット位置を調節するためにシフトが必要になる。したがって、符号および／またはオーバーフローを直接生成するために、ＲＡＡ ＡＬＵにさらに論理を追加することは、考慮する価値がある。例えば、符号は有用であり、実装するためにはＸＯＲゲートが１つ必要なだけである。
【０１５０】
符号拡張は、ワード内のビットを再編成する必要があるので、単純なルーティングオプションではありえない。ただし、（上のＦＰＧＡのケースで説明した）算術演算出力の符号拡張は、ＲＡＡとともに使用することもでき、そして、符号信号を利用できることにより直接的な利点がもたらされる。図１８の回路（加算（または減算）操作１８２０の符号出力１８１０がマルチプレクサ１８３０を制御）は、図３に示すクラスタ３００のＡＬＵ１００およびマルチプレクサ２００に直接対応付けられる。これは、図４Ａに示す、符号付き比較に続くデータ選択に使用される回路構成と同一である。この回路は、入力として、加算または減算されるべき２つの数を受け取り、出力として、演算の結果と、符合値を拡張することによって、所望される長さまで出力を補足したさらなる数のビットとを生成する。
【０１５１】
図１８の回路で、符号出力１８１０が、負の数を示す値「１」を運ぶ場合、マルチプレクサ１８３０は、すべて１という第１の入力値を、結果を補足するために選択する。符号出力１８１０が、正の数を示す値「０」を運ぶ場合、マルチプレクサ１８３０は、すべて０という第２の入力値を、結果を補足するために選択する。
【０１５２】
要約すると、ＦＰＧＡは必要とされる論理を直接実装できるので、専用の符号論理は、ＦＰＧＡにとってほとんど利点はない。専用の符号論理は、プロセッサにとって（分岐のための制御フラグとして）およびＲＡＡにとって（マルチプレクサ２００で条件制御および符号拡張の両方のために使用されることが可能な、マルチプレクサ２００の制御信号として）、より大きな利点がある。
【０１５３】
（符号およびオーバーフローのための式の導出）
加算の中の個々のビットについては、和およびキャリーアウトは、入力（Ａ、Ｂ、キャリーイン）に、次のように関連している（ＢをＮＯＴ Ｂに置き換えれば、同じ式が減算にも当てはまる）。
Σｉ＝Ａｉ∧Ｂｉ∧Ｃｉ−１
Ｃｉ＝ｉｆ（Ａｉ∧Ｂｉ）ｔｈｅｎ（Ｃｉ−１）ｅｌｓｅ（Ａｉ）
ここで、Ｃｉ−１はキャリーイン、Ｃｉはキャリーアウトであり、∧はＸＯＲ演算を表す。
【０１５４】
ｎビットを使用した計算の結果が、より高い精度で計算が実行されたと仮定した場合（例えば、入力および出力がｎ＋１ビットに拡張された場合）に得られたであろう結果と異なっていれば、オーバーフローが発生している。符号付きおよび符号なしのケースは、別々に取り扱われなければならない。
【０１５５】
（符号なしのケース）
入力拡張は、先行する０を追加することにより実現される。
Σｎ−１＝Ａｎ−１∧Ｂｎ−１∧Ｃｎ−２
Ｃｎ−１＝ｉｆ（Ａｎ−１∧Ｂｎ−１）ｔｈｅｎ（Ｃｎ−２）ｅｌｓｅ（Ａｎ−１）
Σｎ＝Ａｎ∧Ｂｎ∧Ｃｎ−１
Ａｎ＝０
Ｂｎ＝０
Σｎ＝Ｃｎ−１
【０１５６】
符号なし加算では、結果の中の追加ビットは０でなければならず、したがって、ｎビット計算からのキャリーアウトが０でない場合は、オーバーフローがある。減算のケース（つまり、Ｂをｎｏｔ Ｂに置き換えたケース）では、下記の数１が得られ、期待される値は、やはり０となる。オーバーフローは、したがって、加算についてはキャリーアウト、減算についてはＮＯＴ（キャリーアウト）である。
【数１】
2005531952.tif 000006
【０１５７】
正しい符号は、符号なし加算については、常に正である。減算については、負の結果がオーバーフローを発生させる。したがって、減算については次のようになる。正しい符号＝オーバーフロー＝ＮＯＴキャリーアウト
【０１５８】
(符号付きのケース)
入力拡張は、ＭＳＢを繰り返すことにより実現される。
Σｎ−１＝Ａｎ−１∧Ｂｎ−１∧Ｃｎ−２
Ｃｎ−１＝ｉｆ（Ａｎ−１∧Ｂｎ−１）ｔｈｅｎ（Ｃｎ−２）ｅｌｓｅ（Ａｎ−１）
Σｎ＝Ａｎ∧Ｂｎ∧Ｃｎ−１
Ａｎ＝Ａｎ−１
Ｂｎ＝Ｂｎ−１
Σｎ＝Ａｎ−１∧Ｂｎ−１∧Ｃｎ−１
【０１５９】
追加出力ビットの期待される値は、やはり、元の計算のＭＳＢを繰り返さなければならないものである。したがって、オーバーフローＶは、これらの２つのビットのＸＯＲに等しい。
Ｖ＝Σｎ∧Σｎ−１
＝（Ａｎ−１∧Ｂｎ−１∧Ｃｎ−１）∧（Ａｎ−１∧Ｂｎ−１∧Ｃｎ−２）
＝（Ａｎ−１∧Ａｎ−１）∧（Ｂｎ−１∧Ｂｎ−１）∧（Ｃｎ−１∧Ｃｎ−２）
＝０∧０∧（Ｃｎ−１∧Ｃｎ−２）
＝Ｃｎ−１∧Ｃｎ−２
【０１６０】
したがって、オーバーフロー信号は、ｎビット計算の最終段階のキャリーインおよびキャリーアウトを組み合わせる単一のＸＯＲゲートを使用して生成できる。
【０１６１】
正しい符号（しばしば、ネガティブフラグＮと呼ばれる）は、追加出力ビットに等しい。
Ｎ＝Σｎ
＝Ａｎ−１∧Ｂｎ−１∧Ｃｎ−１
【０１６２】
ただし、Ａｎ−１∧Ｂｎ−１の項は、ｎビット値のＭＳＢの計算の一部としてすでに計算されているので、符号もまた、評価のためには、追加のＸＯＲゲートが１つ必要となるだけである。
【０１６３】
要約すると、符号なしのケースについては、正しい符号とオーバーフローは、キャリー出力との直接の関係を有する。符号付きのケースについては、これはもはや正しくなく、符号とオーバーフローの両方が、それらを正しく生成するために、それぞれ、１つの追加のＸＯＲゲートのみを必要とする。
【０１６４】
上記の明細の中では、本発明を、その特定の実施形態を参照して説明した。ただし、その実施形態に対するさまざまな変形および変更が、本発明のより広い本質と範囲から逸脱することなく行われてもよいことは明らかである。例えば、ここで説明した処理フロー図に示された、処理動作の特定の順序および組み合わせは、あくまでも説明するためのものにすぎず、本発明は、異なるまたは追加の処理動作、あるいは処理動作の異なる組み合わせまたは順序を使用して実施されることが可能であることを、読者は理解すべきである。したがって、明細書および図面は、限定するというよりもむしろ、説明する意味があるものと見なされるべきであり、本発明は、特許請求の範囲およびそれらの法的均等物に従うことを除き、制限または限定されるべきではない。
【図面の簡単な説明】
【０１６５】
【図１】本発明の実施形態で使用する論理演算装置を示す。
【図２】本発明の実施形態で使用するマルチプレクサを示す。
【図３】本発明の実施形態による、クラスタ内に組み合わされたＡＬＵおよびマルチプレクサの例を示す。
【図４Ａ】データ選択回路として構成されたクラスタを示す。
【図４Ｂ】データ伝達回路として構成されたクラスタを示す。
【図５】条件処理回路として構成された２つのクラスタを示す。
【図６】データ経路制御回路として構成された２つのクラスタを示す。
【図７】マルチプレクサに接続された出力レジスタを有するクラスタを示す。
【図８Ａ】レジスタを有するマルチプレクサのための、イネーブル付きレジスタ構成を示す。
【図８Ｂ】レジスタを有するマルチプレクサのための、リセット付きレジスタ構成を示す。
【図９】追加の入力選択論理を有するマルチプレクサを示す。
【図１０】フィードバック回路として構成された入力選択論理を有するマルチプレクサを示す。
【図１１】キャリーアウト信号のための代替経路を提供するように構成されたマルチプレクサを示す。
【図１２】ＡＬＵのキャリーアウト出力からキャリーイン入力へのレジスタ付き経路を実装するための追加要素を有するクラスタを示す。
【図１３】マルチプレクサ出力に接続されたインバータを有するクラスタを示す。
【図１４】アプリケーションの論理コンポーネントを処理要素に割り当てるための方法のフローチャートである。
【図１５】マルチプレクサ制御信号を生成および選択するための回路を示す。
【図１６】マルチプレクサ制御信号を選択的に反転させるための回路を示す。
【図１７】拡張された回路を制御するために、値が迂回されることを可能にする、図１５の回路の拡張を示す。
【図１８】図３のクラスタに対応付けられることが可能な、符号拡張を実装するための回路を示す。
【図１９】クラスタ内に配置された、ＡＬＵおよびマルチプレクサの集まりを示す。
【図２０】制御信号のための２つの汎用ルーティングネットワークを含む、再構成可能アレイを示す。
【図１】
2005531952.tif 000007
【図２】
2005531952.tif 000008
【図３】
2005531952.tif 000009
【図４Ａ】
2005531952.tif 000010
【図４Ｂ】
2005531952.tif 000011
【図５】
2005531952.tif 000012
【図６】
2005531952.tif 000013
【図７】
2005531952.tif 000014
【図８Ａ】
2005531952.tif 000015
【図８Ｂ】
2005531952.tif 000016
【図９】
2005531952.tif 000017
【図１０】
2005531952.tif 000018
【図１１】
2005531952.tif 000019
【図１２】
2005531952.tif 000020
【図１３】
2005531952.tif 000021
【図１４】
2005531952.tif 000022
【図１５】
2005531952.tif 000023
【図１６】
2005531952.tif 000024
【図１７】
2005531952.tif 000025
【図１８】
2005531952.tif 000026
【図１９】
2005531952.tif 000027
【図２０】
2005531952.tif 000028
【国際調査報告】
2005531952.tif 000029
2005531952.tif 000030
2005531952.tif 000031
2005531952.tif 000032
2005531952.tif 000033