(57)【特許請求の範囲】
【請求項１】
集積回路であって、
第１のクロック周波数で動作可能であって、構成データをロードすることによって構成されてパケットから検索キーを抽出するプログラマブル回路と、
第１のメモリブロックとを備え、
前記メモリブロックは、
データポートを有する第１のメモリ要素と、
前記第１のメモリ要素のデータポートおよび前記プログラマブル回路に結合される第１のメモリプロセッサとを含み、
前記第１のメモリプロセッサおよび前記第１のメモリ要素の前記データポートは、前記第１のクロック周波数よりも高い第２のクロック周波数で動作可能であり、
前記第１のメモリプロセッサは、前記第１のメモリ要素に記憶されるデータについてのみ動作し、
集積回路はさらに、第２のメモリブロックを備え、
前記第２のメモリブロックは、
データポートを有する第２のメモリ要素と、
前記第２のメモリ要素の前記データポートに結合され、前記構成データをロードすることなく前記集積回路内で機能するハードウェアによって実現される接続を介して前記第１のメモリプロセッサに直列に接続される第２のメモリプロセッサとを含み、
前記第２のメモリプロセッサおよび前記第２のメモリ要素の前記データポートは、前記第２のクロック周波数で動作し、
前記メモリプロセッサは前記メモリ要素に記憶されるデータについてのみ動作し、
前記第１および第２のメモリブロックの各々は、前記プログラマブル回路から取得した検索キーの一部に対して作用する、集積回路。
【請求項２】
前記第１のメモリ要素はランダムアクセスメモリ（ＲＡＭ）要素であり、前記第１のメモリプロセッサは更新条件に応答して前記第１のＲＡＭ要素内の少なくとも１つの位置を更新するように構成される、請求項１に記載の集積回路。
【請求項３】
前記第１のメモリブロックは、前記検索キーの第１の部分に作用し、前記第２のメ
モリブロックは、同じ検索キーの第２の部分に作用する、請求項１または２に記載の集積回路。
【請求項４】
前記第１のメモリプロセッサまたは前記第２のメモリプロセッサは、検索キーの最上位ビットをチェックするために前記メモリブロックが指定されることを示すように構成される最上位セルを含む、請求項３に記載の集積回路。
【請求項５】
前記第１のメモリプロセッサまたは前記第２のメモリプロセッサは、検索キーの最下位ビットをチェックするために前記メモリブロックが指定されることを示すように構成される最下位セルを含む、請求項３に記載の集積回路。
【請求項６】
前記第１のメモリプロセッサは、二分探索ツリーフォーマットデータとして前記第１のメモリ要素内に記憶されるテーブルの第１の部分について検索操作を行うように構成され、
前記第２のメモリプロセッサは、二分探索ツリーフォーマットデータとして前記第２のメモリ要素内に記憶される前記テーブルの第２の部分について検索操作を行うように構成される、請求項１から５のいずれか１項に記載の集積回路。
【請求項７】
前記第１のメモリ要素および前記第２のメモリ要素は、前記第１のメモリ要素の単一のポートを用いて前記第１のメモリ要素にアクセスする前記第１のメモリプロセッサおよび前記第２のメモリ要素の単一のポートを用いて前記第２のメモリ要素にアクセスする前記第２のメモリプロセッサを有する二値連想メモリとして構成される、請求項６に記載の集積回路。
【請求項８】
前記第１のメモリ要素および前記第２のメモリ要素は、前記第１のメモリ要素のデュアルポートを用いて前記第１のメモリ要素にアクセスする前記第１のメモリプロセッサおよび前記第２のメモリ要素のデュアルポートを用いて前記第２のメモリ要素にアクセスする前記第２のメモリプロセッサを有する三値連想メモリとして構成される、請求項６に記載の集積回路。
【請求項９】
前記第１のメモリプロセッサは、前記第１のメモリ要素内に記憶されるテーブルの第１の部分について検索操作を行うように構成され、
前記第２のメモリプロセッサは、前記第２のメモリ要素内に記憶される前記テーブルの第２の部分について検索操作を行うように構成される、請求項１から５のいずれか１項に記載の集積回路。
【請求項１０】
前記第１のメモリ要素は、前記プログラマブル回路に結合される追加のデータポートを含み、前記第１のクロック周波数で動作可能である、請求項１に記載の集積回路。
【請求項１１】
前記第１のメモリブロックおよび前記第２のメモリブロックは、ツリーデータ構造の同レベルのデータを記憶し、
前記第１または前記第２のメモリブロックのみが動作可能であり、動作不能なメモリブロックはバイパスされる、請求項１に記載の集積回路。
【請求項１２】
探索性能を向上させる方法であって、
集積回路のプログラマブル回路を第１のクロック周波数で動作させるステップを備え、前記プログラマブル回路は構成データをロードすることによって構成され、方法はさらに、
前記構成されたプログラマブル回路を用いて、パケットから検索キーの少なくとも２つの部分を抽出するステップと、
第１のメモリプロセッサと第１のメモリ要素とを含む第１のメモリブロック内において、前記検索キーの第１の部分を受け取るステップと、
前記第１のメモリプロセッサを使用して、前記第１の部分を用いた動作を前記第１のメモリ要素に記憶されるデータについて行うステップと、
第２のメモリプロセッサと第２のメモリ要素とを含む第２のメモリブロック内において、前記検索キーの第２の部分を受け取るステップと、
前記第２のメモリプロセッサを使用して、前記第２の部分を用いた動作を前記第２のメモリ要素に記憶されるデータについて行うステップとを備える、方法。
【請求項１３】
前記検索キーの前記第１の部分と前記第１のメモリ要素内の選択されたエントリとを比較するステップと、
前記検索キーの前記第２の部分と前記第２のメモリ要素内の選択されたエントリとを比較するステップとをさらに備える、請求項１２に記載の方法。
【請求項１４】
二分探索ツリーフォーマットデータとして前記第１のメモリ要素内に記憶されるテーブルの第１の部分について検索操作を行うステップと、
二分探索ツリーフォーマットデータとして前記第２のメモリ要素内に記憶される前記テーブルの第２の部分について検索操作を行うステップとをさらに備える、請求項１２または１３に記載の方法。
【請求項１５】
前記第１のメモリ要素内に記憶されるテーブルの第１の部分について検索操作を行うステップと、
前記第２のメモリ要素内に記憶される前記テーブルの第２の部分について検索操作を行うステップとをさらに備える、請求項１２または１３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本明細書に開示される１つ以上の実施形態は、集積回路（ＩＣ）に関する。より特定的には、１つ以上の実施形態は、ＩＣ内の組み込みメモリおよび専用プロセッサ構造に関する。
【背景技術】
【０００２】
背景
高速ネットワークのアプリケーションにおいて、探索操作を素早く行う能力は非常に重要であり得る。パケットを処理するために、たとえば、通常はパケットの１つ以上の属性を判定し、探索操作を行うために使用しなければならない。探索操作の結果により、パケットに対して実施されるハンドリングが決定され得る。パケットのハンドリングに影響を及ぼし得る属性の一覧には、完全に網羅しているわけではないが、パケットのタイプおよびパケットの所有権などが含まれ得る。パケットに対するハンドリング操作の例としては、限定されるものではないが、パケットの宛先アドレスに基づくパケットのネクストホップアドレスの判定、パケットの転送、パケットのルーティング、およびパケットのスクリーニングが含まれ得る。この種のパケット操作には、パケットごとに１つ以上の探索操作が伴い得る。このため、探索操作を素早く効率的に行うためのネットワークノードの能力にネットワークノードの帯域幅が大きく依存し得る。探索性能が低速であれば、ネットワークノードの帯域幅が小さくなり得る。また、探索性能が低速であれば、探索処理によって引き起こされる時間遅れにより、データのオーバーフロー状態を避けるためにネットワークノードに追加のメモリを含むことが必要となり得ることから、ネットワークノードのコストが増大し得る。
【発明の概要】
【課題を解決するための手段】
【０００３】
概要
本明細書に開示される１つ以上の実施形態は、集積回路（ＩＣ）に関し、より特定的には、ＩＣ内の組み込みメモリおよび専用プロセッサ構造に関する。
【０００４】
実施形態は、ＩＣを含み得る。ＩＣは、第１のクロック周波数で動作可能なプログラマブル回路と、メモリブロック（たとえば、ブロックランダムアクセスメモリ）とを含み得る。メモリブロックは、少なくとも１つのデータポートを有するメモリ要素（たとえば、ランダムアクセスメモリ（ＲＡＭ）要素）と、メモリ要素のデータポートおよびプログラマブル回路に結合されるメモリプロセッサとを含み得る。メモリプロセッサは、第１のクロック周波数よりも高い第２のクロック周波数で動作可能であり得る。さらに、メモリプロセッサは、ハードウェアによって実現され得て、メモリブロックのメモリ要素における動作専用であり得る。
【０００５】
本実施形態において、メモリ要素はランダムアクセスメモリ（ＲＡＭ）要素であり、メモリプロセッサは更新条件に応答してＲＡＭ要素内の少なくとも１つの位置を更新するように構成され得る。
【０００６】
本実施形態において、プログラマブル回路は、検索キーの少なくとも一部をパケットから抽出し、検索キーの少なくとも一部をメモリプロセッサに提供するように構成され、メモリプロセッサは、検索キーの少なくとも一部とメモリ要素内の選択されたエントリとを比較するように構成され得る。
【０００７】
本実施形態において、メモリプロセッサは、メモリブロックが少なくとも１つの追加のメモリブロックに結合された場合に、検索キーの少なくとも一部における最上位ビットをチェックするためにメモリブロックが指定されるか否かを示すように構成される最上位セルを含み得る。
【０００８】
本実施形態において、メモリプロセッサは、メモリブロックが少なくとも１つの追加のメモリブロックに結合された場合に、検索キーの少なくとも一部における最下位ビットをチェックするためにメモリブロックが指定されるか否かを示すように構成される最下位セルを含み得る。
【０００９】
本実施形態において、メモリプロセッサは、二分探索ツリーフォーマットデータとしてメモリ要素内に記憶されるテーブルの一部について検索操作を行うように構成され得る。
【００１０】
本実施形態において、メモリ要素は二値連想メモリとして構成され、メモリプロセッサは二値連想メモリの稼働状態において構成される。
【００１１】
本実施形態において、メモリ要素は三値連想メモリとして構成され、メモリプロセッサは三値連想メモリの稼働状態において構成される。
【００１２】
本実施形態において、メモリプロセッサは、トライフォーマットデータとしてメモリ要素内に記憶されるテーブルの一部について検索操作を行うように構成され得る。
【００１３】
本実施形態において、メモリブロックは、複数のメモリブロックのうちの１つであり、マルチステージパイプライン構造は、複数のメモリブロックを含み得る。複数のメモリブロックにおける各メモリプロセッサは、ハードウェアによって実現される信号経路を介して複数のメモリブロックのうちの他のメモリブロックにおける少なくとも１つの他のメモリプロセッサに結合され得る。複数のメモリブロックにおける少なくとも１つのメモリプロセッサは、プログラマブル回路に結合され、検索キーの少なくとも一部を受け取るように構成され得る。
【００１４】
本実施形態において、複数のメモリブロックの第１のグループは、マルチステージパイプライン構造の第１のステージとして構成され得る。複数のメモリブロックの第２のグループは、マルチステージパイプライン構造の第２のステージとして構成され得る。
【００１５】
探索性能を向上させる方法の実施形態は、集積回路のプログラマブル回路を第１のクロック周波数で動作させるステップと、集積回路のメモリブロック（たとえば、ブロックランダムアクセスメモリ）のメモリプロセッサを第１のクロック周波数より高い第２のクロック周波数で動作させるステップとを含み得る。メモリブロックのメモリ要素は、メモリプロセッサに結合され、メモリプロセッサは、ハードウェアによって実現されるとともに、メモリ要素における動作専用であり得る。
【００１６】
本実施形態において、方法は、検索キーの少なくとも一部をパケットから抽出するステップと、検索キーの少なくとも一部をメモリプロセッサに提供するステップと、検索キーの少なくとも一部とメモリ要素内の選択されたエントリとを比較するステップとをさらに含み得る。
【００１７】
本実施形態において、方法は、二分探索ツリーフォーマットデータとしてメモリ要素内に記憶されるテーブルの一部について検索操作を行うステップをさらに含み得る。
【００１８】
本実施形態において、方法は、トライフォーマットデータとしてメモリ要素内に記憶されるテーブルの一部について検索操作を行うステップをさらに含み得る。
【００１９】
ＩＣの他の実施形態は、プログラマブル回路とマルチステージパイプライン回路構造とを含み得る。マルチステージパイプライン回路構造は、複数のブロックランダムアクセスメモリを含み得る。各ブロックランダムアクセスメモリは、少なくとも１つのデータポートを有するＲＡＭ要素とデータポートに結合される専用メモリプロセッサと含み得る。複数のブロックランダムアクセスメモリにおける各メモリプロセッサは、ハードウェアによって実現される信号経路を介して複数のブロックランダムアクセスメモリのうちの他のブロックランダムアクセスメモリにおける少なくとも１つの他のメモリプロセッサに結合され得る。複数のブロックランダムアクセスメモリにおける少なくとも１つのメモリプロセッサは、プログラマブル回路に結合されるとともに、検索キーの少なくとも一部を受け取るように構成され得る。
【００２０】
本実施形態において、複数のブロックランダムアクセスメモリの第１のグループは、マルチステージパイプライン構造の第１のステージとして構成され得る。複数のブロックランダムアクセスメモリの第２のグループは、マルチステージパイプライン構造の第２のステージとして構成され得る。
【００２１】
本実施形態において、各ステージにおける少なくとも１つのメモリプロセッサは、メモリプロセッサの属するブロックランダムアクセスメモリがグループにおける少なくとも１つの追加のブロックランダムアクセスメモリに結合された場合に、検索キーの少なくとも一部における最上位ビットをチェックするためにブロックランダムアクセスメモリが指定されるか否かを示すように構成される最上位セルを含み得る。
【００２２】
本実施形態において、各ステージにおける少なくとも１つのメモリプロセッサは、ブロックランダムアクセスメモリがグループにおける少なくとも１つの追加のブロックランダムアクセスメモリに結合された場合に、検索キーの少なくとも一部の最下位ビットをチェックするためにブロックランダムアクセスメモリが指定されるか否かを示すように構成される最下位セルを含み得る。
【００２３】
本実施形態において、プログラマブル回路は、第１のクロック周波数で動作可能であり得る。複数のブロックランダムアクセスメモリにおける各メモリプロセッサは、第１のクロック周波数よりも高い第２のクロック周波数で動作可能であり得る。
【００２４】
本実施形態において、プログラマブル回路は、キーデータを少なくとも２つのパケットから抽出し、キーデータをマルチステージパイプライン回路構造に並行して提供するように構成され得る。
【００２５】
本実施形態において、キーデータの第１の部分は、マルチステージパイプライン回路構造の第１のステージに提供され得る。第１の部分以外のキーデータの各部分は、遅延線に提供され、遅延線から第１のステージ以外のマルチステージパイプライン回路構造のステージに出力され得る。
【００２６】
本実施形態において、マルチステージパイプライン回路構造は、直列に結合される複数のブロックランダムアクセスメモリの第１のサブセットを含む第１の列と、直列に結合される複数のブロックランダムアクセスメモリの第２のサブセットを含む第２の列とを含み得る。第１の列は第２の列と直列に結合される。
【００２７】
本実施形態において、マルチステージパイプライン回路構造は、直列に結合される複数のブロックランダムアクセスメモリの第１のサブセットを含む第１の列と、直列に結合される複数のブロックランダムアクセスメモリの第２のサブセットを含む第２の列とを含み得る。第１の列と第２の列とは並列に結合され、各々が同じキーデータを受け取る。
【００２８】
ＩＣの他の実施形態は、第１のクロック周波数で動作可能なプログラマブル回路と、第１のデータポートおよび第２のデータポートを有するＲＡＭ要素を含むブロックランダムアクセスメモリとを含み得る。第１のデータポートは、プログラマブル回路に結合され得る。メモリプロセッサは、第２のデータポートおよびプログラマブル回路に結合され得る。メモリプロセッサは、第１のクロック周波数よりも高い第２のクロック周波数で動作可能であり得る。メモリプロセッサは、ハードウェアによって実現されるとともに、ＲＡＭ要素における動作専用であり得る。
【００２９】
本実施形態において、集積回路にロードされる構成データに基づき、選択的に第１のデータポートまたは第２のデータポートのみが一度に動作可能である。
【図面の簡単な説明】
【００３０】
【図１】本明細書に開示される実施形態に基づく集積回路（ＩＣ）のアーキテクチャを示す第１のブロック図である。
【図２】本明細書に開示される他の実施形態に基づくブロックランダムアクセスメモリ（ＢＲＡＭ）のアーキテクチャを示すブロック図である。
【図３】本明細書に開示される他の実施形態に基づく探索システムのステージへのデータ構造の例示的なマップ化を示す図である。
【図４】本明細書に開示される他の実施形態に基づくＢＲＡＭを使用したマルチステージパイプライン構造を示すブロック図である。
【図５】本明細書に開示される他の実施形態に基づくＢＲＡＭを示すブロック図である。
【図６】本明細書に開示される他の実施形態に基づく図５のＢＲＡＭを示すブロック図である。
【図７】本明細書に開示される他の実施形態に基づくＢＲＡＭを示すブロック図である。
【図８】本明細書に開示される他の実施形態に基づくＩＣのマルチステージパイプライン構造を示すブロック図である。
【図９】本明細書に開示される他の実施形態に基づくＩＣのマルチステージパイプライン構造を示すブロック図である。
【図１０】本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造を示す図である。
【図１１】本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造を示す図である。
【図１２】本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造を示す図である。
【図１３】本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造を示す図である。
【図１４】本明細書に開示される他の実施形態に基づく回路設計を生成するためのシステムを示すブロック図である。
【図１５】本明細書に開示される他の実施形態による回路設計の方法を示すフロー図である。
【発明を実施するための形態】
【００３１】
図面の詳細な説明
本明細書は新規であるとみなされる１つ以上の実施形態の特徴を定義する請求項で締めくくられるが、図面と併せて記載を考慮することによって１つ以上の実施形態についてより良好に理解されると考えられる。適宜、１つ以上の実施形態についての詳細が本明細書に開示される。しかし、当然のことながら、１つ以上の実施形態は単に例示である。このため、本明細書に開示される具体的な構造および機能についての詳細は、限定的なものとして解釈されるのではなく、単に請求項の根拠として、および実質的に任意で適度に詳細な構造を用いて１つ以上の実施形態を様々な形で採用するよう当業者に教示するための代表的な根拠として解釈される。さらに、ここで使用される用語および語句は限定することを意図したものでなく、ここに開示される１つ以上の実施形態について理解可能な記載を提供することを意図している。
【００３２】
本明細書に開示される１つ以上の実施形態は集積回路（ＩＣ）に関し、より特定的にはＩＣ内の組み込みメモリおよび専用プロセッサ構造に関する。本明細書に開示される１つ以上の実施形態に基づき、探索性能は、組み込みメモリに処理要素を含むことによって高められ得る。組み込みメモリブロックを有するＩＣにおいて、処理要素は１つ以上の組み込みメモリブロックに含まれ得る。隣接する処理要素間の信号経路はハード化されており、パイプライン構成で配置された場合に回路の帯域幅を増大させる。一局面において、メモリブロックに含まれる処理要素は、各処理要素が関連付けられる特定のメモリブロック内における検索または探索操作専用であり得る。
【００３３】
図１は、本明細書に開示される実施形態に基づくＩＣのアーキテクチャ１００を示すブロック図である。アーキテクチャ１００は、たとえばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）タイプのＩＣにおいて実施され得る。示されるように、アーキテクチャ１００は、たとえばロジックブロックなどの複数の異なるタイプのプログラマブル回路を含む。たとえば、アーキテクチャ１００は、マルチギガビットトランシーバ（ＭＧＴ）１０１と、構成可能ロジックブロック（ＣＬＢ）１０２と、ランダムアクセスメモリブロック（ＢＲＡＭ）１０３と、入力／出力ブロック（ＩＯＢ）１０４と、構成およびクロッキングロジック（構成／クロック）１０５と、デジタル信号処理ブロック（ＤＳＰ）１０６と、特殊Ｉ／Ｏブロック１０７（たとえば、構成ポートおよびクロックポート）と、デジタルクロックマネージャ、アナログ−デジタルコンバータ、およびシステムモニタリングロジックなどの他のプログラマブルロジック１０８とを含む、多数の異なるプログラマブルタイルを含み得る。
【００３４】
一部のＩＣにおいて、各プログラマブルタイルは、プログラマブル相互接続要素（ＩＮＴ）１１１を含み、ＩＮＴ１１１は、隣接する各タイルの対応するＩＮＴ１１１に対して規格化された接続を有する。このため、ＩＮＴ１１１は、まとめられ、示されるＩＣのためのプログラマブル相互接続構造を実現する。各ＩＮＴ１１１は、図１の上部に含まれる例示されるように、同じタイル内でプログラマブルロジック要素に対する接続も含む。
【００３５】
たとえば、ＣＬＢ１０２は、ユーザーロジックと単一のＩＮＴ１１１とを実現するようにプログラミングされ得る構成可能ロジック要素（ＣＬＥ）１１２を含み得る。ＢＲＡＭ１０３は、１つ以上のＩＮＴ１１１に加えて、ＢＲＡＭロジック要素（ＢＲＬ）１１３を含み得る。通常、タイルに含まれるＩＮＴ１１１の数は、タイルの高さに依存する。描かれる実施形態において、ＢＲＡＭタイルは５つのＣＬＢと同じ高さを有するが、他の数（たとえば、４つ）も使用され得る。ＤＳＰタイル１０６は、適切な数のＩＮＴ１１１に加えてＤＳＰロジック要素（ＤＳＰＬ）１１４を含み得る。ＩＯＢ１０４は、１つのＩＮＴ１１１のインスタンスに加え、たとえば２つのＩ／Ｏロジック要素（ＩＯＬ）１０５のインスタンスを含み得る。当業者にとって明らかなように、たとえばＩＯＬ１１５に接続される実際のＩ／Ｏパッドは、通常はＩＯＬ１１５の領域に制限されない。
【００３６】
図１に描かれる例において、ダイの中心付近の列領域（図１に網掛けで示される）は、構成、クロック、および他の制御ロジックに使用される。この列から延在する水平領域１０９は、プログラマブルＩＣの幅方向にわたってクロックおよび構成信号を分配するために使用される。図１に示されるアーキテクチャを利用する一部のＩＣは、ＩＣの大部分を構成する規則的な列構造を分断させる追加のロジックブロックを含む。追加のロジックブロックは、プログラマブルブロックおよび／または専用回路であり得る。たとえば、ＰＲＯＣ１１０として示されるプロセッサブロックは、ＣＬＢおよびＢＲＡＭの複数列に及ぶ。
【００３７】
ＰＲＯＣ１１０は、ＩＣのプログラマブル回路を実施する型の一部として作られる、ハードウェアによって実現されるプロセッサとして実施され得る。ＰＲＯＣ１１０は、複雑さの範囲が、たとえばプログラムコードを実行可能なシングルコアの個別のプロセッサから、１つ以上のコア、モジュール、コプロセッサ、もしくはインターフェイスなどを有するプロセッサシステム全体にまで及ぶ、様々な異なるタイプのプロセッサおよび／またはシステムのいずれかを示し得る。
【００３８】
「プログラマブル回路」の語句は、たとえば、ここに記載される様々なプログラマブルまたは構成可能回路ブロックもしくはタイルなど、ＩＣ内のプログラマブル回路要素、およびＩＣにロードされる構成データに基づいて様々な回路ブロック、タイル、および／または要素を選択的に結合する相互接続回路を言う。たとえば、ＣＬＢ１０３およびＢＲＡＭ１０３など、図１においてＰＲＯＣ１１０の外に示される部分は、ＩＣのプログラマブル回路として考慮され得る。
【００３９】
概して、プログラマブル回路の機能は、構成データがＩＣにロードされるまでは確立されない。構成ビットのセットまたは複数のセットは、ＦＰＧＡなどのＩＣのプログラマブル回路をプログラミングするために使用され得る。構成データまたはビットは、通常は「構成ビットストリーム」と呼ばれる。概して、プログラマブル回路は、まず構成ビットストリームがＩＣにロードされないと動作または機能しない。構成ビットストリームは、回路設計を効果的に規定する。構成ビットストリームをＩＣにロードすることにより、ビットストリームによって規定された特定の回路設計がプログラマブル回路内において実現される、またはそのインスタンスが生成される。設計回路により、たとえば、プログラマブル回路ブロックの機能的な局面、および様々なプログラマブル回路ブロック間の接続が規定される。
【００４０】
「ハードウェアによって実現される」または「ハード化された」回路、すなわちプログラマブルでない回路は、ＩＣの一部として製造される。プログラマブル回路とは異なり、ハードウェアによって実現される回路または回路ブロックは、ＩＣが製造された後は構成ビットストリームをロードすることによっては実現されない。ハードウェアによって実現される回路は、たとえば最初に構成ビットストリームをＩＣにロードせずとも機能する専用回路ブロックおよび相互接続を有すると通常は考えられる。
【００４１】
一部のインスタンスにおいて、ハードウェアによって実現される回路は、ＩＣ内の１つ以上のメモリ要素に記憶されるレジスタの設定もしくは値に応じて設定または選択され得る１つ以上の動作モードを有し得る。動作モードは、たとえば構成ビットストリームをＩＣにロードすることによって設定され得る。このような能力を有しながらも、ハードウェアによって実現される回路はＩＣの一部として製造されることによって動作可能であって特定の機能を有するので、ハードウェアによって実現される回路はプログラマブル回路として考慮されない。
【００４２】
図１は、たとえばプログラマブルファブリックなどのプログラマブル回路とプロセッサシステムとを含むＩＣを実現するために使用され得る例示的なアーキテクチャを示すことを意図している。たとえば、列におけるロジックブロックの数、列の相対幅、列の数および順序、列に含まれるロジックブロックのタイプ、ロジックブロックの相対サイズ、ならびに図１の上部に含まれる相互接続／ロジックの実行例は、単に例示である。実際のＩＣにおいては、たとえば、ＣＬＢのある場所には通常は２列以上のＣＬＢが含まれ、ユーザ回路設計の効率的な実施が容易となる。しかしながら、隣接するＣＬＢ列の数は、ＩＣの全体的な大きさに伴って異なり得る。さらに、ＩＣ内におけるＰＲＯＣ１１０の大きさおよび／または位置決めは例示のみを目的としており、本明細書に開示される１つ以上の実施形態を限定する意図はない。
【００４３】
本明細書に開示される１つ以上の実施形態は、プログラマブルであるか否かに関わらず、ＩＣ内において実現され得る。プログラマブルＩＣは、規定のロジック機能を実行するようにプログラミングされ得る周知のタイプの集積回路である。概して、プログラマブルＩＣは、少なくともいくつかのプログラマブル回路を含む特定用途向けＩＣを含む任意のＩＣであり得る。プログラマブルＩＣの例としては、限定されないが、ＦＰＧＡ、複合プログラマブルロジックデバイス（ＣＰＬＤ）、およびマスクプログラマブルデバイスが含まれ得る。このため、「プログラマブルＩＣ」の語句は、ここに記載のＩＣおよび一部のみがプログラマブルなＩＣを言う。たとえば、他のタイプのプログラマブルＩＣとしては、ハードコードされたトランジスタロジックとハードコードされたトランジスタロジックをプログラマブルに相互接続するプログラマブルスイッチファブリックとを組み合わせたものが含まれ得る。
【００４４】
図２は、本明細書に開示される他の実施形態に基づくＢＲＡＭ２０５のアーキテクチャを示すブロック図である。図２は、複数のＢＲＡＭ２０５を含む列２００を示す。列２００は、たとえば、図１を参照して示されるアーキテクチャを有するＩＣ内において実現され得る。たとえば、ＢＲＡＭ２０５は、図１を参照して示されるＢＲＡＭ１０３の代わりに、またはこれと組み合わせて使用され得る。示されるように、各ＢＲＡＭ２０５は、ランダムアクセスメモリ（ＲＡＭ）要素２１０とメモリプロセッサ２１５とを含み得る。一局面において、ＲＡＭ要素２１０は、図１を参照して記載されるＢＲＡＭロジック要素（ＢＲＬ）１１３と実質的に同様に、または同じ態様で実現され得る。概して、ＲＡＭ要素２１０は、信号２２０を介してメモリプロセッサ２１５に結合され得る１つ以上のポート２４０を含み得る。メモリプロセッサ２１５は、隣接するＢＲＡＭ２０５における他のメモリプロセッサに信号２２５および２３０を介して直列に結合され得る。ＲＡＭ要素２１０は、メモリプロセッサ２１５に対してポート２４０および信号２２０を介して配線される。
【００４５】
示されるように、ＢＲＡＭ２０５はプログラマブル回路２７０に結合され得る。プログラマブル回路２７０は、概して図１を参照して記載される１つ以上のプログラマブルタイルもしくはブロックおよびプログラマブル相互接続回路を使用して実現され得る。一局面において、ＲＡＭ要素２１０は、信号２４４を介してＩＣのプログラマブル回路２７０に結合され得る１つ以上の追加のポート２４２を含み得る。ポート２４２は、たとえば、メモリプロセッサ２１５をバイパスし得る。
【００４６】
ポート２４０がメモリプロセッサ２１５と同じクロック周波数で動作し得る一方、ポート２４２はＩＣのプログラマブル回路２７０と同じクロック周波数で動作し得る。ＩＣにロードされる構成ビットストリームにより、異なるデータポートが有効となり得る、たとえば、動作可能もしくは動作不能となり得る。たとえば、ＩＣにロードされる構成ビットストリームに基づき、ポート２４０またはポート２４２のいずれかが常に動作可能となる。示されるように、プログラマブル回路２７０は、信号２４６を介してメモリプロセッサ２１５にさらに結合され得る。
【００４７】
本明細書内において、端子、信号線、ワイヤ、およびこれらの対応する信号を参照するために同一の参照符号が付されている。この点について、「信号」、「ワイヤ」、「接続」、「端子」、および「ピン」の用語は、本明細書内において場合に応じて互換的に使用され得る。また、「信号」または「ワイヤ」などの用語は、１つ以上の信号、たとえば、単一のワイヤを介した単一ビットの搬送、または複数の並列なワイヤを介した複数の並列ビットの搬送を示し得る。さらに、各ワイヤまたは信号は、場合によっては信号またはワイヤによって接続される２つ以上の構成部品の間の双方向通信を示してもよい。
【００４８】
一局面において、メモリプロセッサ２１５は、ハードウェアによって実現される回路ブロックとして実現され得る。さらに、信号２２０，２２５，２３０は、ハードウェアによって実現される信号経路であり得る。ハードウェアによって実現される回路の形態でメモリプロセッサ２１５および信号２２０，２２５，２３０を実施することにより、ＢＲＡＭ２０５は、互いに直列的かつ効果的に、およびプログラマブル回路２７０（たとえば、プログラマブル回路ブロックおよびプログラマブル相互接続を含む）を使用する場合と比して速いクロック速度で通信し、２つ以上のＢＲＡＭ２０５を結合し得る。これにより、一実施形態において、列２００のＢＲＡＭ２０５は互いに結合して、プログラマブル回路２７０を利用することなくメモリプロセッサ２１５ならびに信号２２５および２３０を介して列内で直列に１つのＢＲＡＭ２０５から次へとデータが伝播し得るマルチステージパイプラインを形成し得る。
【００４９】
概して、ＢＲＡＭ２０５は、プログラマブル回路２７０の周波数またはメモリプロセッサ２１５の周波数のいずれかで動作するように構成され得る。たとえば、ポート２４０を含むＲＡＭ要素２１０は、プログラマブル回路２７０を動作させるために使用される周波数よりも速い、メモリプロセッサ２１５の周波数で動作するように構成され得る。ポート２４２を含むＲＡＭ要素２１０は、メモリプロセッサ２１５の周波数で動作するようにさらに構成され得る。メモリプロセッサ２１５の周波数は、たとえば、プログラマブル回路２７０の周波数よりも数倍高い、または速い。
【００５０】
ＢＲＡＭ２０５の各メモリプロセッサ２１５は、そのＢＲＡＭ２０５のＲＡＭ要素２１０のみと併せての使用専用であり得る。このようなことから、一局面において、メモリプロセッサ２１５は、ＲＡＭ要素２１０に関する様々なデータ駆動機能を実行するように構成され得る。たとえば、メモリプロセッサ２１５は、ＲＡＭ要素２１０において検索および／または探索機能を実行するように構成され得る。
【００５１】
他の例において、メモリプロセッサ２１５は、特定の条件を検知し、これらの条件または信号に応答し、カウンタ位置として指定されたＲＡＭ要素２１０内の１つ以上の位置内の値を更新するように、たとえば、増加または減少させるように構成され得る。カウンタ機能に関し、メモリプロセッサ２１５は、１つ以上のカウンタの実施をカプセル化し得る。１つ以上のトリガ条件が、システム内の他の場所の回路、たとえばＢＲＡＭ２０５の外にあるプログラマブル回路２７０によって生成され得る。特定の条件が発生したことを示すこのような回路からの信号に応答し、メモリプロセッサ２１５は、ＲＡＭ要素２１０内の１つ以上の異なるメモリ位置を増加または減少させ得る。
【００５２】
この方法により、メモリプロセッサ２１５は、ＲＡＭ要素２１０の１つ以上のセルの内部状態を操作するように構成され得る。変更され得る１つ以上のセルまたはメモリ位置は、たとえば、カウンタであり得る。メモリプロセッサ２１５は、ＲＡＭ要素２１０と固く結合される、または一体化されると考えられ得る。メモリプロセッサ２１５は、抽象化レイヤをメモリの周囲に提供し、記載される特殊な挙動をカプセル化し得る。メモリプロセッサ２１５の機能は、プロセッサとメモリとの結合の制限が小さい、たとえば結合が緩い汎用プロセッサの挙動または動作と対比され得るクローズドシステムの動作も示す。たとえばメモリコントローラなど、メモリと相互作用する他のコントローラは、基本的な読み取り要求および書き込み要求を処理する。メモリコントローラは、たとえば、メモリに記憶されたデータの取得を効果的にスケジューリングし、途中でデータを変更することなく、要求されたデータをメモリからホストへ、またはホストからメモリへ伝達する。
【００５３】
記載したように、ＢＲＡＭ２０５は、探索操作を行うようにも構成され得る。ＢＲＡＭ２０５は、様々な異なるフォーマットのうちのいずれかで編成されたデータに基づいて探索操作を行うように構成され得る。たとえば、データは、二分探索ツリー（ＢＳＴ）の形態で、２つ以上のＢＲＡＭ２０５にわたってフォーマットおよび記憶され得る。他の例において、データは、トライ形式で、２つ以上のＢＲＡＭ２０５にわたってフォーマットおよび記憶され得る。
【００５４】
ＢＳＴは、ノードベースの二値ツリーデータ構造をいう。また、ＢＳＴは順序二分ツリーまたは分類二分ツリーともいう。ＢＳＴの階層構造により、実行しなければならない比較の数を最小化するために、検索の効率化を容易にする。概して、ＢＳＴはノードから構成される。各ノードはテーブルエントリを示す。最長プレフィックスマッチ（ＬＰＭ）の場合、各ノードはエントリの長さも記憶する。
【００５５】
最長プレフィクス合致ともいうＬＰＭは、インターネットプロトコル（ＩＰ）ネットワーキングにおいてルーターによって使用されるアルゴリズムを参照し、ルーティングテーブルからエントリを選択する。ルーティングテーブルにおける各エントリは、ネットワークを特定し得る。これにより、１つの宛先アドレスが２つ以上のルーティングテーブルのエントリに合致し得る。テーブルエントリは宛先アドレスのアドレスのビットに合致する先頭アドレスのビット数が最も大きいため、最も特定的なテーブルエントリはＬＰＭであると言える。
【００５６】
たとえば、プレフィクスは、ルーティングテーブルをコンパクトにするために使用され得る。ＩＰアドレスは、本質的には階層的である。このため、多くのフラットアドレスを記憶するよりも、ＩＰアドレスの範囲を示すために単一のプレフィクスが使用され得る。一方のプレフィクスが大きいアドレスセットを示し、他方のプレフィクスが小さいアドレスセットを示し、２つのプレフィクスが重複し得ることから、最も特定的なプレフィクスの選択が望ましい。最も特定的なプレフィクスは、最も小さいアドレスセットを示す。この例において、最も長い合致プレフィクスは、最も特定的または記述的なプレフィクスであり、ＩＰアドレスの最も小さいセットを示す。
【００５７】
再びＢＳＴを参照すると、各ノードは親として機能し得る。各親ノードは、２つの子を有し得る。ＢＳＴの視覚的表現において、左の子ノードは、親ノードの左にあり、第２の子は親ノードの右にある。左の子および左の子ノードの各子孫は、現ノード、たとえば親ノードに記憶される値よりも小さい値を含まなければならない。同様に、右の子および右の子ノードの各子孫は、現ノードに記憶される値よりも大きい値を含まなければならない。左右の子ノードから延在する左右両方のサブツリーもそれぞれＢＳＴでなければならない。効率的な探索を行うために、ツリーのバランスを保つ必要がある。
【００５８】
各ノードが順序付けおよび探索を目的としてデータ要素を示す一方、ノードは、ノードに関連付けられた記録の一部を使用するのではなく、各ノードのキーに基づいて概して比較される。ＢＳＴに対する操作には、ノード間の比較が必要となる。これらの比較は、１つ以上の異なるＢＲＡＭ２０５内のメモリプロセッサ２１５によって行われ得る。トライは、キーが通常は文字列である連想配列を記憶するために使用される順序ツリーデータ構造をいう。トライは、プレフィクスツリーともいわれる。ＢＳＴとは異なり、トライにおけるノードは、そのノードに関連付けられたキーを記憶しない。むしろ、トライ内におけるノードの位置は、そのノードに関連付けられたキーを規定する。ノードのすべての子孫は、そのノードに関連付けられた文字列の共通のプレフィクスを有する。ルートは、空のの文字列に関連付けられる。値は通常はすべてのノードには関連付けられず、対象となるキーに対応するリーフおよび一部の内部ノードのみに関連付けられる。
【００５９】
ＢＳＴと同様に、トライはＬＰＭを容易にするために使用され得る。トライは、そこに記憶されるビットを区分し、各レベルにおける小さなビット間の比較を可能とする。トライは、レベルにわたってビットを効果的に分類する。このようなことから、ルートノードからプレフィクスノードへの経路によって示されるバイナリ論理値は、プレフィクスの値と合致する。各レベルは関連付けられたストライドを有する。ストライドは、トライの各レベルにおいて検査されるビットの数を指定する。所与のレベルにおける各ノードは、２ストライドの考えられる分枝を有する。
【００６０】
トライを使用した探索または検索操作は、トライのルートで始まり、キーの最上位ビットで開始される。各レベルにおいて分枝の決定／比較が行われ、各分枝は与えられた割り当てられた２進値を有する。分岐の決定では、プレフィクスの上部からビットのストライド数が抽出され、同じ２進値を有する分枝が続く。分枝に続くノードがプレフィクスを含む場合、プレフィクスは検索キーに合致する。手順は、最長の合致プレフィクスが見つかるまで最後のトライレベルおよび最下位ビットに向けて繰り返し継続され得る。トライフォーマットデータの検索に必要な比較は、１つ以上のＢＲＡＭ２０５内においてメモリプロセッサ２１５によって行われ得る。
【００６１】
図３は、本明細書に開示される他の実施形態に基づく探索システム３１０のステージへのデータ構造３０５の例示的なマップ化を示す図である。一局面において、データ構造３０５は、ＢＳＴを示し得る。他の局面において、データ構造３０５はトライを示し得る。いずれの場合においても、図３は、どのようにデータ構造３０５がレベル０、１、２、および３で示されるレベルに分けられ得るかを示す。
【００６２】
データ構造３０５の各レベルは、本明細書においてより詳細に記載される探索システム３１０の特定のステージにマップ化され得る、または割り当てられ得る。概して、探索システム３１０は、図２を参照して記載されるＢＲＡＭ、たとえばＢＲＡＭの列を使用して実現され得る。複数のＢＲＡＭは、直列に結合され、マルチステージパイプライン構造となり得る。複数のＢＲＡＭは、ＢＲＡＭのグループに編成され、各グループは２つ以上の個別のＢＲＡＭを含む。ＢＲＡＭの各グループは、データ構造３０５の各レベルがマップ化される探索システム３１０のステージを実現し得る。
【００６３】
データ構造３０５は、例示のみを目的として提供される。このようなことから、１つ以上のＢＲＡＭにわたって記憶される実際のデータ構造は、より少ない、またはより多いノードを含み得る。さらに、データ構造は、適宜同じ階層または異なる階層を有し得る。
【００６４】
図４は、本明細書に開示される他の実施形態に基づくＢＲＡＭを使用したマルチステージパイプライン構造４００を示すブロック図である。図４は、異なるＢＲＡＭ２０５がステージにグループ化され、場合によってはＢＳＴまたはトライのデータ構造のレベルに各ステージが対応し得ることを示す。例示を目的として、図４に描かれる例は、ＢＳＴの実行例に関する。
【００６５】
示されるように、各ＢＲＡＭ２０５は、ＲＡＭ要素２１０とメモリプロセッサ２１５とを含む。信号経路４０５は、マルチステージパイプライン構造４００においてハードウェアによって実現されるパイプラインを形成する、メモリプロセッサ２１５を介したデータフローを示す。マルチステージパイプライン構造４００は、十分な数の隣接するＢＲＡＭ２０５が各ステージのメモリ要件を満たすように割り当てられる限りＢＲＡＭ２０５の列に対して実現、たとえば、マップ化され得る。図４は、ステージ０およびステージ１として表される２つのステージを示し、パイプラインは下方から上方へ、たとえばステージ０からステージ１へ流れる。図４に描かれる例は、各ステージにおいて重ねられるメモリの量を示し、これはＢＳＴの実行例における深いレベルの特徴である。
【００６６】
簡単に記載すると、「グループ」は「Ｋ」個のＢＲＡＭ２０５を言い、「Ｋ」は１以上の整数値であり得る。各ステージは１つ以上のグループで形成され、各グループはＫ個のＢＲＡＭ２０５を含む。各ステージはＢＲＡＭ２０５の１つ以上のグループを含み得るが、ＢＲＡＭ２０５の１つのグループのみが常に各ステージ内でアクティブである。たとえば、ステージ０は、グループ１と名付けられたＢＲＡＭ２０５の単一のグループを含む。ステージ０が単一のグループのみを含むため、そのグループ、すなわちグループ１がアクティブである。しかしながら、ステージ１は、グループ２およびグループ３として表される２つのグループを含む。ステージ１内においては、グループ２またはグループ３のいずれかが常にアクティブである。非アクティブなグループは、信号経路４０５に対して通過挙動を実施し得る。記載したように、ＢＳＴ実行例について、各ステージの容量は、使用されるＢＲＡＭ２０５の各々についてメモリ容量が同じと仮定して、２倍となり得る。
【００６７】
概して、各メモリプロセッサ２１５は、テーブルエントリの記憶、探索結果の記憶、および選択されたエントリと検索キーとの比較、またはその一部などの機能を実行するように構成され得る。記載したように、メモリプロセッサ２１５および信号経路４０５は、ハードウェアによって実現され得る。
【００６８】
一局面において、ＢＲＡＭ２０５巻の相互接続は最小化され得る。「Ｋ」の大きさ、たとえば各グループにおけるＢＲＡＭ２０５の数は、式Ｋ＝（３２／Ｗ）＋１に基づいて判定することができ、「Ｗ」は各テーブルエントリの幅を示す。グループは、上方の「Ｋ−１」個のＢＲＡＭ２０５にテーブルエントリを記憶し得る。テーブル結果は、下方のＢＲＡＭ２０５に記憶され得る。検索キーおよび探索コンテキストは、信号経路４０５の一部としてのメモリプロセッサ２１５を通過し得る。「探索コンテキスト」は、たとえば、メモリアドレス、結果、および／またはステータス情報であり得る。上方の「Ｋ−１」個のＢＲＡＭ２０５は、記憶されたエントリをアドレスから引き出し、引き出されたエントリを区分的に検索キーと比較し得る。比較により、たとえば次のステージのための新しいアドレスなどのコンテキストおよび結果が判定され得る。そして、コンテキストおよび結果は、パイプラインにおいて次のＢＲＡＭ２０５に渡され得る。
【００６９】
図５は、本明細書に開示される他の実施形態に基づくＢＲＡＭ５００を示すブロック図である。ＢＲＡＭ５００は、ＬＰＭを実現するためのＢＳＴタイプのデータ構造を実施するように構成される。示される例において、ＢＲＡＭ５００は、範囲の比較を実施するように構成される。なお、記載されるＢＲＡＭ５００は、比較操作の１つの３２ビット部分を実現し得る。先に述べたように、１つ以上のＢＲＡＭ５００は、各ステージが比較操作の３２ビット部分を実行することができる複数のステージを形成するようにパイプライン化される。
【００７０】
連想メモリ（ＣＡＭ）は、完全合致ストラテジを実施する場合に使用され得るメモリをいう。一局面において、二値ＣＡＭ（ＢＣＡＭ）メモリが使用され得る。他の局面において、より包括的な合致、たとえばＬＰＭのために、三値ＣＡＭ（ＴＣＡＭ）が使用され得る。ＴＣＡＭの「三値」部分は、各テーブルビットの位置ごとに０、１、または＜＊＞（ワイルドカード）を使用することをいう。図５は、ＬＰＭタイプの探索のためのＴＣＡＭの実施を示す。ＴＣＡＭの実施により、各二値テーブルエントリ、たとえばノードと併せてビットマスクが記憶され得る。ビットマスクは、値のどのビットが探索操作時に合致しなければならないかを示し得る。これにより、２つのビットがテーブルエントリデータビットごとに記憶される。
【００７１】
ＢＲＡＭ５００は、ＲＡＭ要素５０５とメモリプロセッサ５１０とを含み得る。示されるように、ＲＡＭ要素５０５は、データポートＡおよびデータポートＢとして表される２つのデータポートを含み得る。データポートＡおよびＢの各々は、３２ビットデータポートとして構成され得る。ＲＡＭ要素５０５は、１０ビット動作のために構成されるアドレスポートとイネーブルポートとをさらに含み得る。先に述べたように、ＲＡＭ要素５０５は、プログラマブル回路に直接的に結合され得る１つ以上の追加のポート（図示せず）を含み得る。ＢＲＡＭ５００のためのプログラマブル回路に結合されるポートは、メモリプロセッサ５１０が利用される場合に動作不能となり得る。
【００７２】
図５に示される例示的な構成は、検索ワードと記憶された上限値および下限値とを比較するためのＲＡＭ要素５０５のデュアルポート特性を使用する。比較は、次のパイプラインステージのためにアドレスの形態でＢＳＴをどの方向に移動させるかを判定するために使用され得る。メモリプロセッサ５１０は、コンパレータブロック５１５−１および５１５−２とフォームアドレスブロック５２５とを含み得る。
【００７３】
キーは、信号５３０を介して１つのＢＲＡＭから次へと渡され得る。先に述べたように、信号５３０は、１つ以上のデータ線またはワイヤを示し得る。信号５３０は、メモリプロセッサ５１０およびそこで横断する様々な信号と同様に、ハードウェアによって実現される。
【００７４】
探索コンテキストは、図５において信号５３２，５３４，５３６，５３８として表される追加の信号上で渡され得る。信号５３２および５３４は、各々の幅が４ビットである上限下限比較信号であり得る。信号５３６は、１７ビット信号の形態で結果およびステータス情報を搬送し得る。信号５３８は、１４ビット信号の形態でアドレス情報を搬送し得る。
【００７５】
示されるように、メモリプロセッサ５１０は、パイプラインアーキテクチャ内の次のメモリプロセッサ（図示せず）に出力されるそれぞれの信号の更新バージョンを生成し得る。たとえば、信号５３２′，５３４′，５３６′，５３８′が生成され、入力として次のメモリプロセッサに結合され得る。信号５３０は、たとえばＢＲＡＭの列の長さにわたって連続し得る。
【００７６】
稼働時において、メモリプロセッサ５１０は、キーの一部、たとえばスライスの形態の入力（信号５３０）と、以前の比較結果およびステータス（信号５３６）と、読み取られるアドレスおよび後続または次のステージに渡される次のアドレス（信号５３８）とを受け取り得る。記載したように、キーのスライスは３２ビットであり得る。例示を目的として、ＲＡＭ要素５０５は、各々が３６ビットの幅を有する１０２４個のエントリを記憶するように構成され得る。この例において、有効な信号５３０−１がＲＡＭ要素５０５に提供され、選択されたクロックサイクルの読み取りおよび／書き込みのためにＲＡＭ要素５０５が有効となる。一局面において、有効な信号５３０−１は、信号５３０から取得され得る。たとえば、構成ビットストリームをロードすることによって構成可能なレジスタ５６０が含まれ得る。レジスタ５６０は、（構成ビットストリームによって指定される）１つ以上のアドレスビット、たとえば、上方の「Ｍ」個のビットを信号５３８からのＭ個のアドレスビットと合致させ得る。Ｍは整数値である。レジスタ５６０の出力は、信号５３０−１とともに「ＡＮＤ」ゲート５６２に提供され得る。したがって、アドレスの上方のＭ個のビットが合致し、信号５３０−１が「有効」を示す場合のみ、特定のクロックサイクルにおいてＲＡＭ要素５０５が有効化される。有効化された場合、メモリプロセッサ ５１０は、ＲＡＭ要素５０５から読み取り、必要な比較を行い、信号５３６および５３６′に対応する結果およびステータスを適宜変更し得る。
【００７７】
示されるように、信号５３８はマルチプレクサ５４２に提供される。マルチプレクサ５４２に提供される制御信号は、最上位セル（ＭＳＣ）５４０から提供され得る。ＭＳＣ５４０は、構成可能であり得るレジスタとして実施され得る。たとえば、ＭＳＣ５４０に記憶された値は、構成ビットストリームをロードすることによってロードまたは特定され得る。ＭＳＣ５４０は、ＢＲＡＭのグループにおける最上位ビット（ＭＳＢ）、たとえば、特定のステージにおける最上位ビットにＢＲＡＭ５００が対応するか否かを特定する。設定された場合、ＢＲＡＭ５００は、パイプラインの次のＢＲＡＭまたは次のステージに提供されるアドレスを更新し得る。たとえば、ＭＳＣ５４０が設定された場合、マルチプレクサ５４２は、フォームアドレスブロック５２５によって生成または判定される、新しく判定されたアドレスを信号５３８′として渡し得る。ＭＳＣ５４０が設定されていない場合、信号５３８を介して受け取ったアドレスは、信号５３８′として通過および出力され得る。
【００７８】
最下位セル（ＬＳＣ）５４４も提供され得る。ＭＳＣ５４０と同様に、ＬＳＣ５４４は、構成ビットストリームをロードすることによって設定され得るレジスタであり得る。ＬＳＣ５４４が設定された場合、コンパレータブロック５１５−１および５１５−２の各々からの比較出力は、それぞれゼロとされ、パイプラインにおいて信号５３２′および５３４′を通って次のメモリプロセッサに伝播される。ＬＳＣ５４４が設定されていない場合、区分的な比較がコンパレータブロック５１５−１および５１５−２を使用して行われ得る。
【００７９】
ＬＳＣ５４４からの信号の受け取りに加え、コンパレータブロック５１５−１および５１５−２の各々は、動作可能となる有効な信号、たとえば信号５３０−１を所与のクロックサイクルで受信し得る。コンパレータブロック５１５−１は上限の比較を行い、コンパレータブロック５１５−２は下限の比較を行い得る。示されるように、図５は、上限および下限の比較を同時に行い、フォームアドレスブロック５２５によって特定されたＢＳＴ内における移動方向を判定するためにＲＡＭ要素５０５の両方のデータポートＡおよびＢが利用される例を示す。
【００８０】
概して、コンパレータブロック５１５−１および５１５−２によって行われる区分的な比較は、たとえば信号５３２および５３４を介して受信される、ステージにおける他のＢＲＡＭの比較結果と結合され、キーがＲＡＭ要素５０５において信号５３８によって特定されたアドレスから読み取られるテーブルエントリ値以下であるか否かを判定するために使用され得る。
【００８１】
一局面において、次のアドレスは、信号５３８を介して受け取った現アドレスを左方に１つ移動させ、比較結果に下方のアドレスビットを割り当てることにより、フォームアドレスブロック５２５によって形成され得る。マルチプレクサ５４６への制御信号５４８は、信号５３０−１および信号５６４の論理積である。信号５６４は、フォームアドレスブロック５２５から出力され、合致が検知されたか否かを示し得る。制御信号５４８は、ＲＡＭ要素５０５のデータポートＡから取得した結果およびステータス情報を信号５３６′として渡すか否か、または、以前のＢＲＡＭから受け取った結果およびステータス情報を渡すか否か、たとえば信号５３６を信号５３６′として渡すか否かを示す。キーがテーブルエントリ値に合致するか、ステータスが現クロックサイクルに関して有効であるか、たとえば、信号５３０−１および信号５６４の両方が真であって制御信号５４８が真となるかについての判定に応答し、データポートＡから取得された結果およびステータスは、新しい結果およびステータスとしての信号５３６′として出力され得る。そうでなければ、信号５３６で受け取った結果およびステータスが信号５３６′として出力される。
【００８２】
図６は、本明細書に開示される他の実施形態に基づく図５のＢＲＡＭ５００を示すブロック図である。図６において、ＢＲＡＭ５００は、ＬＰＭを実現するためにＢＳＴタイプのデータ構造と併せて実現されるように構成される。図５がＴＣＡＭタイプのメモリと併せて使用される実施形態を示すのに対し、図６はＢＣＡＭタイプのメモリと併せて使用される実施形態を示す。このため、単一のコンパレータブロック５１５のみが利用される。さらに、ＲＡＭ要素５０５の単一のデータポート、すなわちデータポートＡのみがアクセスされる。
【００８３】
メモリプロセッサ５１０はある程度構成可能であることから、ハードウェアによって実現されるブロックとして実現されているが、一局面において、コンパレータブロック５１５−１および信号５３２，５３２′へ、ならびにデータポートＢからコンパレータブロック５１５−１へ、ＬＳＣ５４４および信号５３０−１からコンパレータブロック５１５−１へ、およびコンパレータブロック５１５−１からフォームアドレスブロック５２５への他の内部接続を取り除くのではなく、このような構成部品および／または接続は、適切な構成ビットストリームをロードすることによって無効化することができる。この点に関し、図５のメモリプロセッサ５１０および図６のメモリプロセッサ５１０は、ハードウェアによって実現される２つの異なる回路ブロックとして実現する必要はなく、適切な構成ビットストリームを実施もしくはロードすることによって選択されるＴＣＡＭ稼働状態およびＢＣＡＭ稼働状態を用いてハードウェアによって実現される１つの回路ブロックとして実現される。
【００８４】
図７は、本明細書に開示される他の実施形態に基づくＢＲＡＭ７００を示すブロック図である。ＢＲＡＭ７００は、ＬＰＭを実施するためのトライタイプのデータ構造と併せて実現されるように構成される。示されるように、ＢＲＡＭ７００は、ＲＡＭ要素７０５とメモリプロセッサ７１０とを含み得る。例示を目的として、ＲＡＭ要素７０５は、各エントリが１８ビットの幅を有する２０４８個のエントリを記憶するように構成され得る。メモリプロセッサ７１０への入力は、キースライスまたはその一部を含み得る。メモリプロセッサ７１０へのキースライスの入力は、マルチプレクサ７２０への入力として提供され得て、「キー＜０＞」および「キー＜１：０＞」として表される。たとえば、キーの１つまたは２つのビットは、入力としてメモリプロセッサ７１０に提供され得る。加えて、メモリプロセッサ７１０は、信号７１２を介して次の子ノードのアドレスを受け取るとともに、信号７１４を介して子ノードのアドレスを受け取り得る。
【００８５】
示されるように、子ノードのアドレスは、アライメントブロック７１６に提供され得る。アライメントブロック７１６は、子ノードのアドレスにおける選択された部分をマルチプレクサ７１８および７２０の各々の入力の異なる部分に提供し得る。たとえば、アライメントブロック７１６は、アドレスのビット１０−１２をマルチプレクサ７１８の第１の入力のアドレスに提供し、アドレスのビット９−１１をマルチプレクサ７１８の第２の入力に提供し得る。
【００８６】
上で述べたように、マルチプレクサ７２０は、キーのスライスを受け取ることができる。たとえば、マルチプレクサ７２０は、カンマを用いて図７に示される連結値を受け取るように各々が構成される２つの入力を有し得る。マルチプレクサ７２０の各入力は、たとえば、アドレスの１つ以上の上方ビット、およびキーのスライスである１つ以上または２つのビットを受け取るように構成され得る。例示を目的として、図７に示される実行例は、各ステージまたはＢＲＡＭ７００の外部の２つ以上の異なるスライスにキーがスライスまたは処理されることを想定している。これにより、各ステージは、後により詳細に記載される遅延線を介してスライスを供給した後、キーの一部、たとえば、１ビット、２ビットなどを受け取り得る。
【００８７】
ストライド選択信号７５０が、マルチプレクサ７１８および７２０の各々に設けられ得る。ストライド選択信号７５０は、構成ビットストリームをロードすることによって特定され得るメモリプロセッサ７１０の構成可能な部分であり得る。これにより、ストライド選択信号７５０に応じて、マルチプレクサ７２０は第１の入力または第２の入力を出力し得る。たとえば、マルチプレクサ７２０は、トライにおけるレベルについてのストライドを選択し得る。ストライドは、行われている探索操作の現ステージにおいていくつのキービットが使用されているかを示す。図７に描かれるように、ストライドは１または２である。たとえば、ストライドが１の場合、１つのキービットがステージにおいて、もしくはステージ毎に使用される。ストライドが２の場合、２つのキービットがステージにおいて、もしくはステージ毎に使用される。
【００８８】
マルチプレクサ７２８は、最初のステージまたは後続のステージのアドレスを選択するように構成され得る。最初のステージにおいて、より大きい、たとえば、完全長のストライドが使用される。この例において、ＲＡＭ要素７０５が２０４８個のエントリによって１８ビットで構成される３６ＫのＲＡＭとして実現されることから、完全長のストライドは１１ビットである。全ての後続のステージにおいて、１つまたは２つのビットのストライドはマルチプレクサ７２８からの出力として使用され得る。
【００８９】
また、ストライド選択信号７５０に基づき、マルチプレクサ７１８は信号７１４から抽出されたアドレスのビット１０−１２またはアドレスのビット９−１１を出力し得る。マルチプレクサ７１８からの出力は、回路ブロック７４６に提供され得る。回路ブロック７４６は、所定の値を有する所定数のビットをチェックするように構成され得る。ストライド選択信号７５０の場合において、回路ブロック７４６によってチェックされるビットに関する特定の数および値は、構成ビットストリームをロードすることによって構成可能であり得る。
【００９０】
たとえば、一局面において、回路ブロック７４６は、ＡＮＤゲートとして実現され、構成ビットストリームをロードすることによって判定または特定され、信号７２２として表される１つ以上のビット値とマルチプレクサ７１８の出力とが比較され得る。図７に描かれる例に基づき、信号７２２は、マルチプレクサ７１８から出力される信号と比較され得る３つのビット値を特定し得る。なお、しかしながら、他の回路構成を実現することも可能であり、ＡＮＤゲートの使用は例示のみを目的としていることが理解されるべきである。
【００９１】
マルチプレクサ７２４は、回路ブロック７４６の出力を第１の入力として受け取り、ハードコードされた値、たとえば１つの値を第２の入力として受け取り得る。マルチプレクサ７２４は、回路ブロック７４６からの出力またはハードコードされた値のいずれかを最初のステージ信号７５２に基づいて渡すように構成され得る。最初のステージ信号７５２は、ステージのプログラマブル構成の一部であり得る。このようなことから、最初のステージ信号７５２は、ＢＲＡＭ７００が探索パイプラインの第１のステージを実施しているかどうかを示すように設定され得る。回路ブロック７２６、たとえば、ＡＮＤゲートは、有効な信号７５４およびマルチプレクサ７２４からの出力の各々が所与のクロックサイクルにおいて真である場合に、イネーブル信号７４０をＲＡＭ要素７０５のイネーブルポートに提供し得る。
【００９２】
信号７１２′によって特定される次の子アドレスは、少なくとも一部が更新ステージブロック７３０によって判定され得る。マルチプレクサ７３２は、信号７１４または更新ステージブロック７３０からの出力を制御信号タイプ７５６に基づいて渡し得る。更新ステージブロック７３０は、スキップ距離を１つ減少させるように構成され得る。たとえば、更新ステージブロック７３０は、子ポインタが２Ｄポインタであると想定して実施され得る。制御信号タイプ７５６は、子のタイプが２Ｄポインタまたはリーフであるか否かをチェックする。たとえば、制御信号タイプ７５６は、子の一部、たとえば、子の１ビットとして渡され得る。リーフは既に結果を含んでいることから、リーフは直接的に渡される。２Ｄポインタは、記載したような更新ステージブロック７３０による処理、たとえば減少を必要とする。
【００９３】
マルチプレクサ７３２は、第１の入力としてマルチプレクサ７３４によって受信された出力信号を提供し得る。ＲＡＭ要素７０５のアドレスポートに提供されたアドレスから読み取られたデータ、たとえばコンテキストおよび／または結果は、データポートから出力され、マルチプレクサ７３４の第２の入力に提供され得る。マルチプレクサ７３４は、マルチプレクサ７３２からの出力またはＲＡＭ要素７０５から読み取られたデータを制御信号スキップ７５８に基づいて渡し得る。
【００９４】
制御信号スキップ７５８は、たとえば、入ってくる子信号７１４からの２つのチェックに基づいて生成され得る。２つのチェックは、タイプおよびスキップ距離を含み得る、または示し得る。入ってくる子のタイプが２Ｄポインタである場合、第２のチェックは、スキップ距離がゼロに等しいかについて行なわれ得る。制御信号スキップ７５８の割り当ては、（ａ）タイプがリーフであるか否か、または（ｂ）タイプが２Ｄポインタであるか、およびスキップ距離がゼロでないか否かに基づいて判定され得る。条件（ａ）または（ｂ）のいずれかが真である場合、制御信号スキップ７５８は真として割り当てられる。制御信号スキップ７５８に真の値が割り当てられた場合、マルチプレクサ７３２からの値が使用される、たとえば、マルチプレクサ７３４を介して渡される。その他の場合においては、制御信号スキップ７５８は偽として割り当てられ、メモリからの値が使用される。
【００９５】
アライメントブロック７１６は、信号７１４で受信された子のためのアドレスポインタを左にシフトさせ得て、これによって構成されたストライドに応じてアドレスが適切に整列される。入ってくる子は、２Ｄポインタまたはリーフのいずれかであり得る。２Ｄポインタの場合、スキップ距離がゼロに等しいかについてチェックされ得る。スキップ距離がゼロでない場合、子のアドレスが更新ステージブロック７３０によって減少され、子が次のステージに渡される。スキップ距離がゼロである場合、下方のストライドアドレスを子からのアドレスポインタに設定することにより、新しい子がメモリから読み出され得る。新しい子は、信号７１４′として次のステージに渡される。
【００９６】
マルチプレクサ７３４は、出力をマルチプレクサ７３６に提供し得る。示されるように、マルチプレクサ７３６はマルチプレクサ７３４からの出力を第１の入力として受け取り、信号７１２を第２の入力として受け取り得る。これにより、マルチプレクサ７３６は、マルチプレクサ７３４からの出力または信号７１２をイネーブル信号７４０に基づいて信号７１２′として渡し得る。マルチプレクサ７３６によって生成された出力は、メモリプロセッサ７１０から信号７１２′として出力され得る。したがって、ＢＲＡＭ７００が現クロックサイクルのために有効化された場合、メモリプロセッサ７１０は、特定された次の子のアドレスをメモリから読み取って変更し、信号７１２′で出力する。
【００９７】
信号７１２′は、第１の入力としてマルチプレクサ７３８に提供され得る。子のアドレスを特定する信号７１４は、第２の入力としてマルチプレクサ７３８に提供され得る。マルチプレクサ７３８は、制御信号７４２に基づき、信号７１２′を渡し得る、または信号７１４を信号７１４′として渡し得る。制御信号７４２は、ＢＲＡＭ７００が「ステージエッジ」であるか否かを示す。より特定的には、制御信号７４２は、ＢＲＡＭ７００がパイプライン構造のステージにおける最後のＢＲＡＭであるか否かを示し得る。このようなことから、制御信号７４２は、構成ビットストリームをロードすることによって特定され得る構成可能信号でもあり得る。いずれの場合においても、ＢＲＡＭ７００がステージにおける最後のＢＲＡＭである場合、マルチプレクサ７３８は、制御信号７４２に基づき、信号７１２′上で特定される次の子のアドレスを信号７１４′上の次のステージの子のアドレスに効果的に割り当てる。
【００９８】
図８は、本明細書に開示される他の実施形態に基づくＩＣ内のマルチステージパイプライン構造８００を示すブロック図である。図８は、ＢＳＴタイプのテーブルの実行例と併せて使用され得る例を示す。示されるように、パケット処理回路８１０は、ＩＣのプログラマブル回路の部分において実現され得る。パケット処理回路８１０は、第１のクロック周波数を有する第１のクロックドメインにおいて動作し得る。概して、パケット処理回路８１０は、受け取ったパケット８０５−１，８０５−２，８０５−３，８０５−４の各々からキーを抽出し得る。
【００９９】
ＢＲＡＭ列８２０は、先に述べたように、ＢＲＡＭ列８２０内で通信可能にリンクされたＢＲＡＭの各々において様々なメモリプロセッサを結合するように実現される、ハードウェアによって実現されるデータ経路を含み得る。ＢＲＡＭ列８２０は、クロックドメイン１の第１のクロック周波数とは異なる、たとえば、それよりも高い第２の周波数を有する第２のクロックドメインにおいて動作し得る。１つの例において、第２のクロック周波数は、第１のクロック周波数の数倍であり得る。図８に描かれる例において、第２のクロック周波数は、第１のクロック周波数の４倍であり得る。
【０１００】
これにより、パケットは、プログラマブル回路内、たとえばパケット処理回路８１０内のネットワークインターフェイスに到達し得る。ヘッダー情報、たとえばキーは、パケット処理回路８１０によって抽出され、ＢＲＡＭ列８２０に提供され得る。クロック周波数１の４倍速いクロック周波数２で、４つのキーがＢＲＡＭ列８２０に提供され得る。したがって、クロック周波数１に対するクロック周波数２の倍数に応じて、複数のキーがグループ化され、並列処理のためにＢＲＡＭ列８２０に提供され得る。
【０１０１】
例示において、パケット８０５から抽出された各キーは、１２８ビットであり得る。パケット処理回路８１０は、ＢＲＡＭ列８２０に対して４つのキーを並列に提供し得て、これによって５１２本のビット線が必要となる。ＢＲＡＭ列８２０によって受け取られると、速度の増大により、キー８１５がシリアライズされ、示されるように順にマルチステージパイプラインアーキテクチャを伝播し得る。４つのキー８１５は、４つの連続的なハードウェアサイクルにおいてＢＲＡＭ列８２０に渡され、いつ特定のＢＲＡＭがキーまたはその一部を受け取って動作するかを示す有効表示ビットと併せてハードウェアによって実現されるデータ経路に沿って伝播し得る。この例においては、キーの幅により、データ経路が１２８ビットに有効な信号のための追加のビットを加えたものとなり、たとえば合計で１２９ビットとなり得る。ＢＲＡＭ列８２０の速度の高まりにより、パケット８０５からの４つのキー８１５に対する処理の結果８２５が出力され得る。結果８２５は、並列でＩＣのプログラマブル回路に提供され得る。結果８２５は、実際には４つの１７ビットの結果、たとえば、並列な各パケットまたはキーについて１つの１７ビットの結果を含み得て、これがＢＲＡＭ列８２０の最後のステージから出力され得る。
【０１０２】
図９は、本明細書に開示される他の実施形態に基づくＩＣ内のマルチステージパイプライン構造９００を示すブロック図である。図９は、トライタイプのテーブルの実行例と併せて使用され得る例を示す。例示を容易にするため、パケット処理回路は示されず、抽出されて図９に示される回路に提供されるキーまたはその一部を用いて、図８を参照して記載されるようにパケットが処理され得る。
【０１０３】
示されるように、ＢＲＡＭ列９０５は、「Ｓ」個のステージを含み得て、Ｓは整数であり、キーは最初のストライド＋Ｓ−１の幅を有し得る。４つの連続的なパケットキーは、抽出され、ＢＲＡＭ列９０５に並列に提供され得る。４つのキーの最初のストライドビットは、ステージ０に並列に提供され得る。この例において、ステージ０は４つの１１ビットの最初のストライド、たとえば４４ビットを受け取り得る。残りのキービットは、遅延線９１５−１、９１５−２から９１５−Ｓに供給され、そしてステージ１からＳ−１に供給され得て、対応するコンテキストがステージに到達した場合に各キーが適切なステージに到達する。
【０１０４】
遅延の長さはステージＸについては「Ｘ」個のサイクルであり、たとえば、ステージ１には１つのサイクルであり、ステージ２には２つのサイクルとなる。ＢＲＡＭ列９０５の結果９２０は、ステージＳ−１に並列に４つの結果を含み得る。各個別の結果は、１８ビットであり得る。これにより、結果９２０は、４×１８ビットとなり得る。代替的な実施においては、ＢＲＡＭ列９０５を形成するＢＲＡＭの各々の上の１つ以上の金属層内において実現され得るハード化データ経路を用いて全てのキービットがすべてのステージに搬送され得る。
【０１０５】
図１０は、本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造１０００を示すブロック図である。図１０は、ＩＣ内の２つの異なるＢＲＡＭ列１００５−１および１００５−２が直列に結合され、ＢＳＴタイプのテーブルの実行例と併せて使用されるより大きな構造を実現する場合を示す。示される例において、ステージ０〜７は、ＢＲＡＭ列１００５−１に対してマップ化されている。ステージ８〜１１は、ＢＲＡＭ列１００５−２に対してマップ化されている。
【０１０６】
先に述べたように、複数のキー１０１０が並列に低速の回路から高速のＢＲＡＭ列１００５に提供され得る。信号１０１５は、ＢＲＡＭ列１００５−１とＢＲＡＭ列１０１０−２とを結合し得る。各キーが１２８ビットであって各キーまたはパケットの結果が１７ビットである上記の例について続けると、信号１０１５は５８０ビットの信号経路であり、４つのキー（４×１２８）および４つの結果（４×１７）をＢＲＡＭ列１００５−１からＢＲＡＭ列１００５−２に伝播し得る。結果１０２０は、４つの個別の結果を含み、回収されてステージ１１から出力され得る。結果１０２０は、図８を参照して記載されるように出力され得て、たとえば、ＩＣのプログラマブル回路などの他の回路に並列に提供され得る４つの個別の１７ビットの結果として出力され得る。
【０１０７】
図１１は、本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造１１００を示すブロック図である。図１１は、ＩＣ内の２つの異なるＢＲＡＭ列１１０５−１と１１０５−２とが直列に結合されてトライタイプのテーブルの実行例と併せて使用される大きな構造を実現する場合を示す。示される例において、ステージ０からステージ（Ｓ−１）は、ＢＲＡＭ列１１０５−１に対してマップ化される。ステージＳからステージ（２Ｓ−１）は、ＢＲＡＭ列１１０５−２に対してマップ化される。
【０１０８】
４つのキー１１１０の最初のストライドビットは、並列にステージ０に提供され得る。この例において、ステージ０は、４つの１１ビットの最初のストライド、たとえば４４ビットを受け取り得る。残りのキービットは、遅延線１１１５−１から１１１５−（２Ｓ−１）に供給され、そしてステージ１から２Ｓ−１のそれぞれに供給され得て、対応するコンテキストがステージに到達した場合に各キーが適切なステージに到達する。明らかに、遅延線１１１５−１から１１１５−（２Ｓ−１）の各々は、遅延の量が増大する、たとえば、１つの遅延したクロックサイクルを提供する。信号１１２０は、ＢＲＡＭ列１１０５−１からＢＲＡＭ列１１０５−２によって判定された４つの結果、たとえば、４×１８ビットの結果もしくは７２ビットを提供し得る。ＢＲＡＭ列１１０５−２の結果１１２５は、ステージ２Ｓ−１から出力された後に並列にフォーマットされ得る４つの結果を含み得る。各個別の結果は、１８ビットであり得る。これにより、結果１１２５は、４×１８ビットとなり得る。代替的な実施においては、ＢＲＡＭ列１１０５−１およびＢＲＡＭ列１１０５−１を形成するＢＲＡＭの各々の上の１つ以上の金属層内において実現され得るハード化データ経路を使用して全てのキービットが全てのステージに搬送され得る。
【０１０９】
図１２は、本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造１２００を示すブロック図である。図１２は、マージされた結果と並行してＩＣ内の２つの異なるＢＲＡＭ列１２０５−１および１２０５−２が動作する、ＢＳＴタイプのテーブルと併せて使用される実行例を示す。マルチステージパイプライン構造１２００は、図１０の場合における大きなテーブルを実現し得るが、時間遅れが小さい。実現されるテーブルは、区分され、それぞれＢＲＡＭ列１２０５−１および１２０５−２に対してマップ化された２つの別個のテーブルにマップ化される。直列に結合されたＢＲＡＭ列を用いた原テーブルの実行例と比して得られる構造のステージが少ないため、時間遅れは小さい。示されるように、４つの受け取られたパケットから抽出されたキー１２１０、たとえば、同じ４つのキーは、ＢＲＡＭ列１２０５−１および１２０５−２の各々に提供され得る。ＢＲＡＭ列１２０５−１および１２０５−２の各々によって判定される結果は、マージされ、結果１２２０として出力され得る。結果１２２０は、たとえば、ＬＰＭを選択すること、または合致が無かったと返答することにより判定される。
【０１１０】
図１３は、本明細書に開示される他の実施形態に基づくマルチステージパイプライン構造１３００を示すブロック図である。図１３は、ＩＣ内の２つの異なるＢＲＡＭ列１３０５−１および１３０５−２の各々がトライタイプのテーブルの実行例のためのマルチステージパイプライン構造を実現し、並列に結合される場合を示す。示される例において、ステージ０からステージ（Ｓ−１）は、ＢＲＡＭ列１３０５−１およびＢＲＡＭ列１３０５−２にマップ化される。
【０１１１】
４つのキー１３１０の最初のストライドビットは、並列に各ステージ０に提供され得る。この例において、ステージ０は４つの１１ビットの最初のストライド、たとえば４４ビットを受け取り得る。残りのキービットは、遅延線１３１５−１から１３１５−（Ｓ−１）に供給され、そしてステージに対応するコンテキストが到達した場合に各キーが適切なステージに到達するように、ＢＲＡＭ列１３０５−１および１３０５−２の各々においてステージ１からＳ−１にそれぞれ供給され得る。図１３に示されるように、直列構成が各ステージの遅延線を必要とする一方、１つの遅延線は、２つの並列のステージの各々、たとえばＢＲＡＭ列１３０５−１および１３０５−２の各々における同じステージにデータを提供し得る。ＢＲＡＭ列１３０５−１および１３０５−２の各々からのマージされた結果１３２５は、ステージＳ−１の各々から出力され得る。マルチパイプラインの結果は、全てのパイプラインからの結果を比較し、ＬＰＭを選択するもしくは結果として合致が無かったと返答することにより、マージされ得る。各個別の結果は、１８ビットであり得る。これにより、結果１３２５は４×１８ビットであり得る。
【０１１２】
図１４は、本明細書に開示される他の実施形態に基づく回路設計を生成するためのシステム１４００を示すブロック図である。システム１４００は、システムバス１４１５を介してメモリ要素１４１０に結合された少なくとも１つのプロセッサ１４０５を含み得る。このようなことから、システム１４００はメモリ要素１４１０内にプログラムコードを記憶し得る。プロセッサ１４０５は、システムバス１４１５を介してメモリ要素１４１０からアクセスされるプログラムコードを実行し得る。一局面において、たとえば、システム１４００は、プログラムコードの記憶および／または実行に適したコンピュータとして実現され得る。しかしながら、システム１４００は、本明細書に開示される機能を実行することが可能なプロセッサおよびメモリを含む任意のシステムの形態で実施され得る。
【０１１３】
メモリ要素１４１０は、たとえば、ローカルメモリ１４２０および１つ以上の大容量記憶装置１４２５など、１つ以上の物理メモリ装置を含み得る。ローカルメモリ１４２０は、ランダムアクセスメモリまたはプログラムコードの実際の実行時に一般的に使用される他の非持続性メモリ装置をいう。大容量記憶装置１４２５は、ハードドライブまたは他の持続性データ記憶装置として実現され得る。システム１４００は、実行時に大容量記憶装置からプログラムコードを読み出さなければならない回数を減らすために、少なくとも一部のプログラムコードを一時的に記憶する１つ以上のキャッシュメモリ（図示せず）を含む。
【０１１４】
キーボード１４３０、ディスプレイ１４３５、およびポインティングデバイス（図示せず）などの入力／出力（Ｉ／Ｏ）装置が任意でシステム１４００に結合され得る。Ｉ／Ｏ装置は、直接的に、または介在するＩ／Ｏ制御部を介してシステム１４００に結合され得る。介在するプライベートネットワークもしくはパブリックネットワークを介してシステム１４００が他のシステム、コンピュータシステム、遠隔プリンタ、および／または遠隔記憶装置に結合できるように、ネットワークアダプタもシステム１４００に結合され得る。モデム、ケーブルモデム、およびイーサネット（登録商標）カードは、システム１４００とともに使用され得る異なるタイプのネットワークアダプタの例である。
【０１１５】
図１４に描かれるように、メモリ要素１４１０は、回路設計モジュール１４４０を記憶し得る。実行可能なプログラムコードの形態で実施される回路設計モジュール１４４０は、システム１４００によって実行され得る。回路設計モジュール１４４０は、ＩＣ内でのインスタンス生成またはＩＣとしての実施のための１つ以上の回路設計を生成し得る。生成される回路設計は、ＩＣがプログラマブルＩＣであるか否かに関わらず、ＩＣ内においてインスタンスが生成され得る。さらに、回路設計は、ネットリストもしくは１つ以上のハードウェア記述言語ファイルなどのプログラムの形態で、または構成ビットストリームとして特定され得る。システム１４００を使用して生成された回路設計は、本明細書に開示される様々なマルチステージパイプライン構造を構成するのに適した構成テーブルを含む、または特定する。たとえば、回路設計は、ここに記載されるパイプラインアーキテクチャに配置される場合にＲＡＭ要素およびメモリプロセッサを構成するのに必要なパラメータを特定し得る。
【０１１６】
一局面において、回路設計モジュール１４４０は、標準的な合成、場所、およびルートなどの機能を実行し、回路設計を生成するように構成され得る。回路設計モジュール１４４０はさらに、適切なデータ構造の実施、所与のテーブルエントリ、および様々なユーザパラメータを生成し、特定されるマルチステージパイプライン構造にロードし得る。
【０１１７】
図１５は、本明細書に開示される他の実施形態に基づく回路設計の方法１５００を示すフロー図である。図１５は、図１３を参照して記載されるシステム１４００などのシステムによって実現され得る。
【０１１８】
ブロック１５０５において、システムは、実施されるテーブルのタイプを特定するユーザ入力を受け取り得る。一局面において、たとえば、テーブルがＢＳＴによる実施またはトライによる実施のいずれかについて示すユーザ入力が受け取られ得る。ＢＳＴの実行例の場合、ユーザ入力はさらにＢＳＴ実施がＢＣＡＭの実施またはＴＣＡＭの実施のいずれであるかを示し得る。
【０１１９】
ブロック１５１０において、システムは、テーブルサイズ情報を特定するユーザ入力を受け取り得る。たとえば、テーブルの幅および高さを特定するユーザ入力がシステムによって受け取られ得る。ブロック１５１５において、システムは、出力され得る回路設計、たとえばプログラム回路設計を生成し得る。得られた回路設計は、受け取られたユーザ指定パラメータに適合したマルチステージパイプライン構造を特定し得る、または含み得る。たとえば、システムがユーザから受け取ったパラメータは、１つ以上のＢＲＡＭの適切な設定を生成するように変更され、場合によっては、得られた回路設計に含まれ、この回路設計もまたＩＣのプログラマブル回路内で実現される様々なサブ回路を含み得る。
【０１２０】
ブロック１５２０において、システムは、システムに対してユーザによって提供または識別されるテーブルエントリによって設定されたテーブル実施、たとえばＢＳＴまたはトライをさらに構築し得る。トライ実施の場合においては、たとえば、設定されたテーブルは、リーフにプレフィクスを含み得る。得られたテーブル実施は、ブロック１５１５において生成されたマルチステージパイプラインアーキテクチャにマップ化され得る。なお、マップ化アルゴリズムは、レベルごとにバランスのとられた数のノードを生成し得る。
【０１２１】
１つ以上の実施形態において、テーブル実施およびマップ化は、Ｌｅらによる「Scalable High-Throughput SRAM-Based Architecture for IP-Lookup Using FPGA」 Field Programmable Logic and Applications （2008）、およびＪｉａｎｇらによる「A Memory-Balanced Linear Pipeline Architecture for Trie-Based IP Lookup」High-Performance Interconnects （2007）に記載されるものを含む様々な技術によって行われ得るが、これらに限定されない。これらの文献は、その全体が引用によりここに援用される。
【０１２２】
ブロック１５２５において、システムによって生成された回路設計は、ＩＣにロードされ得る。ブロック１５３０において、システムはブロック１５２０において生成されたテーブルの実施を、回路設計によって特定されてＩＣで実施されるマルチステージパイプライン構造にロードし得る。
【０１２３】
図中のフローチャートは、本明細書に開示される１つ以上の実施形態に係るシステム、方法、およびコンピュータプログラム製品の可能な実施についてのアーキテクチャ、機能、および操作を示す。これに関連し、フローチャートにおける各ブロックは、モジュール、セグメント、またはコードの一部を示し得て、特定の論理的機能を実施する実行可能なプログラムコードの１つ以上の部分を含む。
【０１２４】
なお、一部の代替的な実施において、ブロックに記される機能は、図に示される順序以外で実現されてもよい。たとえば、含まれる機能に応じて、連続する２つのブロックは実際には実質的に同時に行われてもよい、またはブロックは逆の順序で実行される場合もある。また、フローチャートの例示における各ブロックおよびフローチャートの例示におけるブロックの組み合わせは、特定の機能もしくは動作を実行する特定用途向けのハードウェアベースのシステム、または特定目的のハードウェアと実行可能な指令の組み合わせであってもよい。
【０１２５】
１つ以上の実施形態は、ハードウェアまたはハードウェアとソフトウェアの組み合わせによって実現され得る。１つ以上の実施形態は、１つのシステムにおいて集中的に実現されてもよいし、または、異なる要素がいくつかの相互接続されたシステムにわたって分散した状態で実現されてもよい。ここに記載の方法の少なくとも一部を実行するように適合された任意の種類のデータ処理システムまたは他の装置がここでは適している。
【０１２６】
１つ以上の実施形態は、ここに記載の方法の実施を可能とするすべての特徴を含むコンピュータプログラム製品などのように、装置に組み込まれ得る。装置は、メモリおよびプロセッサを含むシステムにロードされて実行された場合に本明細書に開示される機能の少なくとも一部をシステムに実行させるプログラムコードを記憶するデータ記憶媒体、たとえば、非持続性コンピュータ利用可能もしくはコンピュータ読み取り可能媒体を含み得る。データ記憶媒体の例としては、限定されないが、光媒体、磁気媒体、光磁気媒体、ランダムアクセスメモリなどのコンピュータメモリ、大容量記憶装置、たとえばハードディスクなどが含まれ得る。
【０１２７】
本文脈における「コンピュータプログラム」、「ソフトウェア」、「アプリケーション」、「コンピュータ利用可能プログラムコード」、「プログラムコード」、「実行可能なコード」などの用語、変形、および／またはこれらの組み合わせは、ａ）他の言語、コード、または表記への変換、および／またはｂ）異なる材料形態での再現以降に情報処理性能を有するシステムが特定の機能を実行することを意図した指令のセットの表現、言語、コード、または表記を意味する。たとえば、プログラムコードは、限定されないが、サブルーチン、機能、手順、オブジェクト法、オブジェクト実施、実行可能なアプリケーション、アプレット、サーブレット、ソースコード、オブジェクトコード、共有ライブラリ／動的負荷ライブラリ、および／またはコンピュータシステム上での実行用に設計された指令の他のシーケンスを含み得る。
【０１２８】
ここで使用される「ａ」および「ａｎ」の用語は、１つまたは１つ以上として定義される。ここで使用される「複数」の用語は、２つまたは２つ以上として定義される。ここで使用される「他の」の用語は、少なくとも第２またはそれ以降として定義される。ここで使用される「含む」および／または「有する」の用語は、備える（comprising）、すなわちオープン表現として定義される。ここで使用される「結合」の用語は、介在する要素なしに直接的である場合または１つ以上の介在する要素を伴って間接的である場合に関わらず、特に示されない限りにおいては、接続として定義される。２つの要素は、機械的に結合、電気的に結合、または通信チャンネル、パスウェイ、ネットワーク、もしくはシステムを介して通信可能にリンクされ得る。
【０１２９】
本明細書に開示される１つ以上の実施形態は、その精神または本質的な属性から逸脱することのない他の形態で具現化され得る。このため、１つ以上の実施形態の範囲を示すものとしては、上述の明細書ではなく、以下の請求項を参照すべきである。
【図１】
0005878639.tif 000002
【図２】
0005878639.tif 000003
【図３】
0005878639.tif 000004
【図４】
0005878639.tif 000005
【図５】
0005878639.tif 000006
【図６】
0005878639.tif 000007
【図７】
0005878639.tif 000008
【図８】
0005878639.tif 000009
【図９】
0005878639.tif 000010
【図１０】
0005878639.tif 000011
【図１１】
0005878639.tif 000012
【図１２】
0005878639.tif 000013
【図１３】
0005878639.tif 000014
【図１４】
0005878639.tif 000015
【図１５】
0005878639.tif 000016