図面 (/)

技術 要素利用のための状態のグループ化

出願人 マイクロン・テクノロジー・インコーポレーテッド
発明者 シュー,ジュンジュエングレンデニング,ポール
出願日 2012年1月24日 (9年0ヶ月経過) 出願番号 2013-550672
公開日 2014年4月10日 (6年10ヶ月経過) 公開番号 2014-508996
状態 特許登録済
技術分野 特別なプログラム実行装置 CAD
主要キーワード 専用要素 入力制約 一般入力 ツリーグラフ ネットワークルーター 出力制約 物理的設計 入力構造
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2014年4月10日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (12)

課題・解決手段

ソースコードから並列マシンプログラムするように構成されたイメージを生成するためのシステムおよび方法の実施形態が開示される。1つのかかる並列マシンは、ペアになった状態機械要素SME)が共通の出力をもつように、ペアにグループ化された複数のSMEを含む。1つのかかる方法は、ソースコードを、複数の相互接続された状態を含むオートマトンに変換すること、および、そのオートマトンを、オートマトン内の状態に対応するインスタンスを含むネットリストに変換することであって、その変換することが、ペアになったSMEが共通の出力をもつという事実に基づいて、SMEのペアに対応する状態をペア形成することを含む、ネットリストに変換することを含む。そのネットリストはイメージに変換され、公開できる。

概要

背景

並列マシン用のコンパイラは、並列マシンを構成する(例えば、プログラミングする)ために、ソースコード機械コード(例えば、イメージ)に変換する。機械コードは、並列マシン上に有限状態機械実装できる。ソースコードを機械コードに変換するプロセスのうちの1つの段階は、ネットリストの形成を含む。ネットリストは、並列マシンのハードウェア要素インスタンス間の接続性記述する。ネットリストは、ハードウェア要素がソースコードの機能を実装できるように、ハードウェア要素間の接続性を記述できる。

概要

ソースコードから並列マシンをプログラムするように構成されたイメージを生成するためのシステムおよび方法の実施形態が開示される。1つのかかる並列マシンは、ペアになった状態機械要素SME)が共通の出力をもつように、ペアにグループ化された複数のSMEを含む。1つのかかる方法は、ソースコードを、複数の相互接続された状態を含むオートマトンに変換すること、および、そのオートマトンを、オートマトン内の状態に対応するインスタンスを含むネットリストに変換することであって、その変換することが、ペアになったSMEが共通の出力をもつという事実に基づいて、SMEのペアに対応する状態をペア形成することを含む、ネットリストに変換することを含む。そのネットリストはイメージに変換され、公開できる。

目的

並列マシン100は、入力データを受信するためのデータ入力ポート110および出力を別の装置に提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

ソースコードから並列マシンプログラムするように構成されたイメージを生成するためのコンピュータ実装方法であって、ソースコードを、複数の相互接続された状態を含むオートマトンに変換することと、前記オートマトンを、前記オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、前記インスタンスが前記並列マシンのハードウェア要素に対応し、前記オートマトンをネットリストに変換することが、前記並列マシンの物理的設計に基づいて状態を共にグループ化することを含む、前記オートマトンをネットリストに変換することと、前記ネットリストを前記イメージに変換することとを含む方法。

請求項2

前記インスタンスが、状態機械要素SME)ハードウェア要素に対応するSMEインスタンスおよび、SMEのグループを含むハードウェア要素に対応するSMEグループインスタンスを含み、かつ、グループ化することが、状態をSMEグループインスタンスにグループ化することを含む、請求項1に記載の方法。

請求項3

前記物理的設計が、SMEのグループを含む前記ハードウェア要素の物理的設計を含む、請求項2に記載の方法。

請求項4

前記物理的設計が、SMEのグループを含む前記ハードウェア要素内の前記SMEに関する入力制約または出力制約のうちの1つを含む、請求項3に記載の方法。

請求項5

前記物理的設計が、SMEのグループを含む前記ハードウェア要素内の前記SMEが出力を共有するという制限を含む、請求項4に記載の方法。

請求項6

SMEグループインスタンスが、2つのSMEインスタンスを含む2つのグループ(GOT)インスタンスを含み、かつ、前記物理的設計が、各GOT内の前記SMEが共通の出力に結合されていることを含む、請求項2に記載の方法。

請求項7

前記オートマトンをネットリストに変換することが、どの前記状態がGOTインスタンス内で共にグループ化できるかを判断することと、前記判断に基づいて前記状態をペア形成することとを含む、請求項6に記載の方法。

請求項8

第1の状態または第2の状態のどちらも前記オートマトンの最終状態ではなく、かつ、前記第1の状態および前記第2の状態の一方が、前記第1の状態または前記第2の状態以外のどの状態も駆動しない場合に、前記第1の状態および前記第2の状態が、GOTインスタンス内で共にペア形成できる、請求項7に記載の方法。

請求項9

第1の状態または第2の状態のどちらも前記オートマトンの最終状態ではなく、かつ、前記第1の状態および前記第2の状態の両方が、同じ外部状態を駆動する場合に、前記第1の状態および前記第2の状態が、GOTインスタンス内で共にペア形成できる、請求項7に記載の方法。

請求項10

第1の状態および第2の状態の一方が前記オートマトンの最終状態であり、かつ、前記第1の状態および前記第2の状態の他方が、どの外部状態も駆動しない場合に、前記第1の状態および前記第2の状態が、GOTインスタンス内で共にペア形成できる、請求項7に記載の方法。

請求項11

第1の状態および第2の状態の両方が前記オートマトンの最終状態であり、かつ、前記第1の状態および前記第2の状態の両方が、同じ外部状態を駆動する場合に、前記第1の状態および前記第2の状態が、GOTインスタンス内で共にペア形成できる、請求項7に記載の方法。

請求項12

どの前記状態がGOTインスタンス内で共にグループ化できるかを判断することが、グラフ理論を使用して、どの前記状態がGOTインスタンス内で共にグループ化できるかを判断することを含む、請求項7に記載の方法。

請求項13

グラフ理論を使用して、どの前記状態がGOTインスタンス内で共にグループ化できるかを判断することが、最大マッチング識別するために、グラフ理論を使用して、どの前記状態がGOTインスタンス内で共にグループ化できるかを判断することを含む、請求項12に記載の方法。

請求項14

前記イメージを公開することをさらに含む、請求項1に記載の方法。

請求項15

前記インスタンスが、汎用インスタンスおよび専用インスタンスを含み、前記汎用インスタンスが前記オートマトンの汎用状態に対応し、また、前記専用インスタンスが前記オートマトンの専用状態に対応する、請求項1に記載の方法。

請求項16

前記汎用インスタンスに対応する前記ハードウェア要素が、状態機械要素(SME)および2つのグループ(GOT)を含み、かつ、前記専用インスタンスに対応する前記ハードウェア要素がカウンタおよび論理要素を含む、請求項15に記載の方法。

請求項17

命令を含むコンピュータ可読媒体であって、前記コンピュータによって実行されるときに、前記コンピュータに、ソースコードを、複数の相互接続された状態を含むオートマトンに変換することと、前記オートマトンを、前記オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、前記インスタンスが前記並列マシンのハードウェア要素に対応し、前記オートマトンをネットリストに変換することが、前記並列マシンの物理的設計に基づいて状態を共にグループ化することを含む、前記オートマトンをネットリストに変換することと、前記ネットリストを前記イメージに変換することとを含む動作を実行させる、コンピュータ可読媒体。

請求項18

前記オートマトンが均質なオートマトンである、請求項17に記載のコンピュータ可読媒体。

請求項19

前記オートマトンをネットリストに変換することが、前記オートマトンの前記状態の各々を、前記ハードウェア要素に対応するインスタンスにマッピングすることと、前記インスタンス間の接続性を決定することとを含む、請求項17に記載のコンピュータ可読媒体。

請求項20

前記ネットリストが、前記ハードウェア要素間の導体を表す前記インスタンス間の複数の接続をさらに含む、請求項17に記載のコンピュータ可読媒体。

請求項21

前記オートマトンをネットリストに変換することが、前記オートマトンを、開始状態を除いて、前記オートマトンの状態に対応するインスタンスを含むネットリストに変換することを含む、請求項17に記載のコンピュータ可読媒体。

請求項22

前記命令が、前記コンピュータに、前記ネットリストの前記インスタンスに対応する前記ハードウェア要素の前記並列マシン内の位置を決定することを含む動作を実行させる、請求項17に記載のコンピュータ可読媒体。

請求項23

状態を共にグループ化することが、汎用要素のグループを含むハードウェア要素の物理的設計に基づいて、状態を共にグループ化することを含む、請求項22に記載のコンピュータ可読媒体。

請求項24

前記命令が、前記コンピュータに、前記並列マシンのどの導体が前記ハードウェア要素を接続するために使用されるかを決定することと、前記並列マシンのプログラム可能スイッチに対する設定を決定することであって、前記プログラム可能スイッチが、前記ハードウェア要素を選択的に共に結合するように構成されている、プログラム可能スイッチに対する設定を決定することとを含む動作を実行させる、請求項22に記載のコンピュータ可読媒体。

請求項25

ソフトウェアがその上に格納されたメモリと、前記メモリに通信的に結合されたプロセッサであって、前記ソフトウェアが、前記プロセッサによって実行されるとき、前記プロセッサに、ソースコードを、複数の相互接続された状態を含むオートマトンに変換することと、前記オートマトンを、前記オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、前記インスタンスが前記並列マシンのハードウェア要素に対応し、前記インスタンスが、複数の第1のインスタンスおよび2つ以上の第1のインスタンスを含むグループインスタンスを含み、前記オートマトンをネットリストに変換することが、未使用の第1のインスタンスの数に基づいて、状態をグループインスタンス内に共にグループ化することを含む、前記オートマトンをネットリストに変換することと、前記ネットリストを前記イメージに変換することとをさせるプロセッサとを含むコンピュータ。

請求項26

前記グループインスタンスが2つのグループ(GOT)インスタンスを含み、かつ、状態をグループ化することが、前記ペア形成された状態がどの状態を駆動するかに応じて、状態をペア形成することを含む、請求項25に記載のコンピュータ。

請求項27

未使用の第1のインスタンスの数に基づいて状態をグループインスタンス内にグループ化することが、以下の条件:第1の状態または第2の状態のどちらも前記オートマトン内の最終状態ではなく、かつ前記第1の状態および第2の状態の一方が、前記第1の状態または第2の状態以外のどの状態も駆動しないことと;前記第1の状態または第2の状態のどちらも前記オートマトン内の最終状態ではなく、かつ前記第1の状態および前記第2の状態の両方が、同じ外部状態を駆動することと;前記第1の状態または前記第2の状態のどちらかが最終状態であり、かつ最終状態ではない前記第1の状態または第2の状態が、前記第1の状態または第2の状態以外のどの状態も駆動しないことと;前記第1の状態および前記第2の状態の両方が最終状態であり、かつ前記第1の状態および前記第2の状態の両方が、同じ外部状態を駆動することとに基づいて、前記第1の状態および前記第2の状態がペア形成できるかどうかを判断することを含む、請求項26に記載のコンピュータ。

請求項28

前記オートマトンをネットリストに変換することが、前記状態をグラフとしてモデル化することであって、前記グラフのバーテックスが状態に対応し、かつ前記グラフのエッジが前記状態の可能なペア形成に対応する、前記状態をグラフとしてモデル化することと、前記グラフに対して一致するバーテックスを決定することと、前記一致するバーテックスに対応する状態をペア形成することとを含む、請求項25に記載のコンピュータ。

請求項29

前記オートマトンをネットリストに変換することが、前記グラフに対して最大マッチングを決定することを含む、請求項28に記載のコンピュータ。

請求項30

前記オートマトンをネットリストに変換することが、一致するバーテックスに対応する状態の各セットをペア形成することと、一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることであって、前記GOTインスタンス内の1つのSMEインスタンスが使用されない、一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることとを含む、請求項29に記載のコンピュータ。

請求項31

ステムであって、前記システムが、コンピュータであって、ソースコードを、複数の相互接続された状態を含むオートマトンに変換することと、前記オートマトンを、前記オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、前記インスタンスが前記並列マシンのハードウェア要素に対応し、前記インスタンスが、複数の第1のインスタンスおよび2つ以上の第1のインスタンスを含むグループインスタンスを含み、前記オートマトンをネットリストに変換することが、未使用の第1のインスタンスの数に基づいて、状態をグループインスタンス内に共にグループ化することを含む、前記オートマトンをネットリストに変換することと、前記ネットリストを前記イメージに変換することとを行うように構成された、コンピュータと、前記イメージを並列マシン上にロードするように構成された装置とを含む、システム。

請求項32

状態を共にグループ化することが、前記ペア形成された状態がどの状態を駆動するかに応じて、状態をペア形成することを含む、請求項31に記載のシステム。

請求項33

未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが、以下の条件:第1の状態または第2の状態のどちらも前記オートマトン内の最終状態ではなく、かつ前記第1の状態および第2の状態の一方が、前記第1の状態または第2の状態以外のどの状態も駆動しないことと;前記第1の状態または第2の状態のどちらも前記オートマトン内の最終状態ではなく、かつ前記第1の状態および前記第2の状態の両方が、同じ外部状態を駆動することと;前記第1の状態または前記第2の状態のどちらかが最終状態であり、かつ最終状態ではない前記第1の状態または第2の状態が、前記第1の状態または第2の状態以外のどの状態も駆動しないことと;前記第1の状態および前記第2の状態の両方が最終状態であり、かつ前記第1の状態および前記第2の状態の両方が、同じ外部状態を駆動することとに基づいて、前記第1の状態および前記第2の状態がペア形成できるかどうかを判断することを含む、請求項31に記載のシステム。

請求項34

未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが、前記状態をグラフとしてモデル化することであって、前記グラフのバーテックスが状態に対応し、かつ前記グラフのエッジが前記状態の可能なペア形成に対応する、前記状態をグラフとしてモデル化することと、前記グラフに対して一致するバーテックスを決定することと、前記一致するバーテックスに対応する状態をペア形成することとを含む、請求項31に記載のシステム。

請求項35

未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが、前記グラフに対して最大マッチングを決定することを含む、請求項34に記載のシステム。

請求項36

未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが、一致するバーテックスに対応する状態の各セットをペア形成することと、一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることであって、前記GOTインスタンス内の1つのSMEインスタンスが使用されない、一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることとを含む、請求項35に記載のシステム。

請求項37

前記装置が、状態の各ペアを、前記並列マシン内の2つのハードウェア要素のグループとして実装するように構成されている、請求項31に記載のシステム。

請求項38

請求項1の前記プロセスによって生成されたイメージによってプログラム化された並列マシン。

技術分野

0001

優先権主張〕
本特許出願は、2011年1月25日に出願された、「STATE GROUPING FOR ELEMENTUTILIZATION」という名称の米国仮特許出願整理番号61/436,075に対する優先権の利益を主張し、これによって、参照によりその全体として本明細書に組み込まれる。

背景技術

0002

並列マシン用のコンパイラは、並列マシンを構成する(例えば、プログラミングする)ために、ソースコード機械コード(例えば、イメージ)に変換する。機械コードは、並列マシン上に有限状態機械実装できる。ソースコードを機械コードに変換するプロセスのうちの1つの段階は、ネットリストの形成を含む。ネットリストは、並列マシンのハードウェア要素インスタンス間の接続性記述する。ネットリストは、ハードウェア要素がソースコードの機能を実装できるように、ハードウェア要素間の接続性を記述できる。

図面の簡単な説明

0003

本発明の様々な実施形態に従った、並列マシンの一例を示す。
本発明の様々な実施形態に従って、有限状態機械エンジンとして実装された図1の並列マシンの一例を示す。
本発明の様々な実施形態に従って、図2の有限状態機械エンジンのブロックの一例を示す。
本発明の様々な実施形態に従って、図3のブロックの行(row)の一例を示す。
本発明の様々な実施形態に従って、図4の行の2つのグループの一例を示す。
本発明の様々な実施形態に従って、コンパイラがソースコードを、図1の並列マシンをプログラムするように構成されたイメージに変換するための方法の一例を示す。
本発明の様々な実施形態に従った、オートマトン(automaton)の例を示す。
本発明の様々な実施形態に従った、オートマトンの例を示す。
本発明の様々な実施形態に従った、ネットリストの例を示す。
本発明の様々な実施形態に従った、ネットリストの例を示す。
本発明の様々な実施形態に従って、図6のコンパイラを実行するためのコンピュータの例を示す。

実施例

0004

以下の説明および図は、特定の実施形態を当業者が実施できるように十分に説明する。他の実施形態は、構造的論理的、電気的、プロセス、および他の変更を包含し得る。いくつかの実施形態の部分および特徴は、他の実施形態に含まれ得るか、または他の実施形態のそれらと置き換えられ得る。請求項に規定される実施形態は、それらの請求項の全ての利用可能な均等物を包含する。

0005

文書は、とりわけ、並列マシンの物理的設計に基づいてネットリストを生成するコンパイラを説明する。一例では、並列マシンの物理的設計は、並列マシンの状態機械要素間における接続性の制限を含み得る。例えば、並列マシン内の状態機械要素は、共通の出力を共有するペアグループ化できる。その結果、コンパイラは、SMEのペアが共通の出力を共有する物理的設計に基づいて、ネットリストを生成できる。

0006

図1は、並列マシン100の例を示す。並列マシン100は、入力データを受信し、その入力データに基づいて出力を提供できる。並列マシン100は、入力データを受信するためのデータ入力ポート110および出力を別の装置に提供するための出力ポート114を含むことができる。データ入力ポート110は、並列マシン100に入力されるデータ用のインタフェースを提供する。

0007

並列マシン100は、汎用要素102および専用要素112を含む、複数のプログラム可能要素を含む。汎用要素102は、1つまたは複数の入力104および1つまたは複数の出力106を含み得る。汎用要素102は、複数の状態のうちの1つにプログラムされ得る。汎用要素102の状態は、汎用要素102が、所与の入力に基づいて、何の出力を提供するかを決定する。すなわち、汎用要素102の状態は、プログラム可能要素が所与の入力に基づいてどのように反応するかを決定する。データ入力ポート110に対するデータ入力は、汎用要素102にそれに対する処置を取らせるため、複数の汎用要素102に提供され得る。汎用要素102の例には、以下で詳細に説明する状態機械要素(SME)、および構成可能論理ブロックを含むことができる。一例では、SMEは、所与の入力がデータ入力ポート110で受信される場合に、特定の出力(例えば、高信号つまり「1」信号)を提供するため、所与の状態に設定され得る。所与の入力以外の入力がデータ入力ポート110で受信される場合、SMEは異なる出力(例えば、低信号つまり「0」信号)を提供し得る。一例では、構成可能論理ブロックは、データ入力ポート110で受信された入力に基づいて、ブール論理関数(例えば、AND、OR、NORなど)を実行するように設定できる。

0008

並列マシン100は、プログラム(例えば、イメージ)を並列マシン100上にロードするためのプログラミングインタフェース111も含むことができる。イメージは、汎用要素102の状態をプログラム(例えば、設定)できる。すなわち、イメージは、所与の入力に対して特定の方法で反応するように汎用要素102を構成できる。例えば、汎用要素102は、文字「a」がデータ入力ポート110で受信される場合、高信号を出力するように設定できる。いくつかの例では、並列マシン100は、汎用要素102の動作のタイミングを制御するためのクロック信号を使用できる。ある例では、並列マシン100は、汎用要素102とやりとりするため、および専用機能を実行するために、専用要素112(例えば、RAM、論理ゲートカウンタルックアップテーブルなど)を含むことができる。いくつかの実施形態では、データ入力ポート110で受信されるデータは、長い時間をかけて、もしくは一度にそろって受信されたデータの一定のセット、または長い時間をかけて受信されたデータのストリームを含むことができる。データは、並列マシン100に結合された、データベースセンサーネットワークなどの任意のソースから受信され得るか、または生成され得る。

0009

並列マシン100は、並列マシン100の異なる要素(例えば、汎用要素102、データ入力ポート110、出力ポート114、プログラミングインタフェース111、および専用要素112)を選択的に共に結合するための複数のプログラム可能スイッチ108も含む。その結果、並列マシン100は、要素間で形成されたプログラム可能マトリックス(programmable matrix)を含む。一例では、汎用要素102の入力104、データ入力ポート110、プログラミングインタフェース111、または専用要素112が、1つまたは複数のプログラム可能スイッチ108を通して、汎用要素102の出力106、出力ポート114、プログラミングインタフェース111、または専用要素112に結合できるように、プログラム可能スイッチ108が、2つ以上の要素を選択的に互いに結合できる。従って、要素間の信号のルーティングが、プログラム可能スイッチ108を設定することによって制御できる。図1は、所与の要素とプログラム可能スイッチ108との間の特定数導体(例えば、ワイヤー)を示しているが、他の例では、異なる数の導体が使用できることが理解されるはずである。また、図1は、個別にプログラム可能スイッチ108に結合された各汎用要素102を示しているが、他の例では、複数の汎用要素102がグループ(例えば、図8に示すような、ブロック802)としてプログラム可能スイッチ108に結合できる。一例では、データ入力ポート110、データ出力ポート114、および/またはプログラミングインタフェース111はレジスタとして実装でき、レジスタへの書込みが、それぞれの要素へデータを提供するか、またはそれぞれの要素からデータを提供するようにする。

0010

一例では、単一の並列マシン100が物理デバイス上に実装されるが、他の例では、2つ以上の並列マシン100が単一の物理デバイス(例えば、物理チップ)上に実装できる。一例では、複数の並列マシン100の各々が、別個のデータ入力ポート110、別個の出力ポート114、別個のプログラミングインタフェース111、および汎用要素102の別個のセットを含むことができる。さらに、汎用要素102の各セットは、それらの対応する入力データポート110でデータに反応(例えば、高信号または低信号を出力)できる。例えば、第1の並列マシン100に対応する汎用要素102の第1のセットは、第1の並列マシン100に対応する第1のデータ入力ポート110でデータに反応できる。第2の並列マシン100に対応する汎用要素102の第2のセットは、第2の並列マシン100に対応する第2のデータ入力ポート110に反応できる。その結果、各並列マシン100は、1セットの汎用要素102を含み、異なるセットの汎用要素102は、異なる入力データに反応できる。同様に、各並列マシン100、および汎用要素102の各対応するセットは、別個の出力を提供できる。いくつかの例では、第2の並列マシン100に対する入力データが、第1の並列マシン100からの出力データを含むことができるように、第1の並列マシン100からの出力ポート114が、第2の並列マシン100の入力ポート110に結合できる。

0011

一例では、並列マシン100上にロードするためのイメージは、汎用要素102の状態を設定するため、プログラム可能スイッチ108をプログラミングするため、および並列マシン100内で専用要素112を構成するための複数のビットの情報を含む。一例では、ある入力に基づいて所望の出力を提供するように並列マシン100をプログラムするために、イメージが並列マシン100上にロードできる。出力ポート114は、データ入力ポート110での汎用要素102のデータに対する反応に基づいて、並列マシン100からの出力を提供できる。出力ポート114からの出力は、所与のパターンの一致を示す単一ビット、複数のパターンに対する一致および不一致を示す複数のビットを含むワード(word)、ならびに所与の時に全てまたは特定の汎用要素102の状態に対応する状態ベクトルを含むことができる。

0012

並列マシン100に関する使用例には、パターン認識(例えば、音声認識画像認識など)、信号処理画像処理コンピュータビジョン、暗号化、およびその他を含む。ある例では、並列マシン100は、有限状態機械(FSM)エンジン、フィールドプログラマブルゲートアレイFPGA)、およびそれらの変形を含むことができる。さらに、並列マシン100は、コンピュータ、ポケットベル携帯電話電子手帳携帯音楽プレーヤネットワーク装置(例えば、ルータファイアウォール、スイッチ、またはそれらの任意の組合せ)、制御回路カメラなどの、大きな装置内のコンポーネントであり得る。

0013

図2図5は、有限状態機械(FSM)エンジン200として実装された別の並列マシンを示す。一例では、FSMエンジン200は、有限状態機械のハードウェア実装を含む。その結果、FSMエンジン200は、FSM内の複数の状態に対応する、複数の選択的に結合可能なハードウェア要素(例えば、プログラム可能要素)を実装する。FSM内の状態と同様に、ハードウェア要素は、入力ストリーム分析し、その入力ストリームに基づいて下流のハードウェア要素をアクティブにできる。

0014

FSMエンジン200は、汎用要素および専用要素を含む、複数のプログラム可能要素を含む。汎用要素は、多数の異なる機能を実装するようにプログラムされ得る。これらの汎用要素は、行(row)206(図3および図4に示す)およびブロック202(図2および図3に示す)に階層的に編成されているSME 204、205(図5に示す)を含む。階層的に編成されたSME 204、205間で信号をルーティングするために、ブロック間スイッチ203(図2および図3に示す)、ブロック内スイッチ208(図3および図4に示す)、ならびに行内(intra−row)スイッチ212(図4に示す)を含む、プログラム可能スイッチの階層が使用される。SME 204、205は、FSMエンジン200によって実装されたFSMの状態に対応できる。SME 204、205は、以下で説明するように、プログラム可能スイッチの使用によって共に結合できる。その結果、FSMは、状態の機能に対応するようにSME 204、205をプログラミングすることにより、また、FSM内の状態間の遷移に対応するため、SME 204、205を選択的に共に結合することにより、FSMエンジン200上に実装できる。

0015

図2は、FSMエンジン例200の全体図を示す。FSMエンジン200は、プログラム可能ブロック間スイッチ203と選択的に共に結合できる複数のブロック202を含む。さらに、ブロック202は、信号(例えば、データ)を受信するため、およびデータをブロック202に提供するために、入力ブロック209(例えば、データ入力ポート)に選択的に結合できる。ブロック202は、ブロック202から外部デバイス(例えば、別のFSMエンジン200)に信号を提供するために、出力ブロック213(例えば、出力ポート)にも選択的に結合できる。FSMエンジン200は、プログラム(例えば、イメージ)をFSMエンジン200上にロードするために、プログラミングインタフェース211も含み得る。イメージは、SME 204、205の状態をプログラム(設定)できる。すなわち、イメージは、入力ブロック209で所与の入力に対して特定の方法で反応するように、SME 204、205を構成できる。例えば、SME 204は、入力ブロック209で文字「a」が受信される場合、高信号を出力するように設定できる。

0016

一例では、入力ブロック209、出力ブロック213、および/またはプログラミングインタフェース211はレジスタとして実装でき、そのレジスタへの書込みがそれぞれの要素に対して、またはそれぞれの要素から、データを提供できるようにする。その結果、プログラミングインタフェース211に対応するレジスタ内に格納されているイメージからのビットが、SME 204、205上にロードできる。図2は、ブロック202、入力ブロック209、出力ブロック213、およびブロック間スイッチ203の間に特定数の導体(例えば、ワイヤ、線)を示しているが、他の例では、もっと少ないかまたは多い導体が使用できることが理解されるはずである。

0017

図3は、ブロック202の一例を示す。ブロック202は、プログラム可能ブロック内スイッチ208と選択的に共に結合できる複数の行206を含むことができる。その結果、行206は、ブロック間スイッチ203で、別のブロック202内の別の行206と選択的に結合できる。一例では、バッファ201は、ブロック間スイッチ203への/ブロック間スイッチ203からの信号のタイミングを制御するために含まれる。行206は、本明細書で2つのグループ(GOT:group of tow)210として参照される要素のペアに編成された複数のSME 204、205を含む。一例では、ブロック202は、16個の行206を含む。

0018

図4は、行206の一例を示す。GOT210は、プログラム可能行内スイッチ212によって、行206内の他のGOT 210および任意の他の要素224と選択的に結合できる。また、GOT 210は、ブロック内スイッチ208で他の行206内の他のGOT 210と、またはブロック間スイッチ203で他のブロック202内の他のGOT 210とも結合できる。一例では、GOT 210は、第1および第2の入力214、216ならびに出力218を有する。第1の入力214は、GOT 210の第1のSME 204と結合され、第2の入力214は、GOT 210の第2のSME 204と結合される。

0019

一例では、行206は、第1および第2の複数の行相互接続導体220、222を含む。一例では、GOT210の入力214、216は、1つまたは複数の行相互接続導体220、222に結合でき、出力218は、1つの行相互接続導体220、222に結合できる。一例では、第1の複数の行相互接続導体220は、行206内の各GOT 210の各SME 204に結合できる。第2の複数の行相互接続導体222は、行206内の各GOT 210の1つのSME 204に結合できるが、そのGOT 210の他のSME 204には結合できない。一例では、第2の複数の行相互接続導体222の半分の第1の方が、行206内のSME 204の半分の第1の方(各GOT 210からの1つのSME 204)と結合でき、第2の複数の行相互接続導体222の半分の第2の方が、行206内のSME 204の半分の第2の方(各GOT 210からのその他のSME 204)と結合できる。第2の複数の行相互接続導体222とSME 204、205との間の制限された接続性は、本明細書では「パリティ」と呼ばれる。

0020

一例では、行206は、カウンタ、プログラム可能ブール論理要素、フィールドプログラマブルゲートアレイ(FPGA)、特定用途向け集積回路ASIC)、プログラム可能プロセッサ(例えば、マイクロプロセッサ)、および他の要素などの、専用要素224も含むことができる。追加として、一例では、専用要素224は、異なる行206内では異なる。例えば、ブロック202内の4つの行206が、専用要素224としてブール論理を含むことができ、ブロック202内の他の8つの行206が、専用要素224としてカウンタを含むことができる。

0021

一例では、専用要素224は、カウンタ(本明細書ではカウンタ224とも呼ばれる)を含む。一例では、カウンタ224は、12ビットのプログラマブル減算カウンタを含む。12ビットのプログラマブルカウンタ224は、カウント入力、リセット入力、およびゼロカウント出力を有する。カウント入力は、アサート時に、カウンタ224の値を1だけ減算する。リセット入力は、アサート時に、カウンタ224に、関連したレジスタから初期値をロードさせる。12ビットのカウンタ224に対して、最大で12ビット数が初期値としてロードできる。カウンタ224の値がゼロ(0)に減算されると、ゼロカウント出力がアサートされる。カウンタ224は、少なくとも2つのモード、パルスおよび保留(hold)を有する。カウンタ224がパルスモードに設定されている場合、カウンタ224がゼロに減算されると、第1のクロック周期中にゼロカウント出力がアサートされ、また、次のクロック周期では、たとえカウント入力がアサートされても、ゼロカウント出力はもはやアサートされない。この状態は、カウンタ224が、アサートされているリセット入力によってリセットされるまで、継続する。カウンタ224が保留モードに設定されている場合、カウンタ224がゼロに減算されると、第1のクロック周期中にゼロカウント出力がアサートされ、また、カウント入力がアサートされる場合、カウンタ224が、アサートされているリセット入力によってリセットされるまで、アサートされたままである。

0022

図5は、GOT210の一例を示す。GOT 210は、入力214、216を有し、かつORゲート230および3入力マルチプレクサ242に結合されたそれらの出力226、228を有する、第1のSME 204および第2のSME 205を含む。3入力マルチプレクサ242は、GOT 210の出力218を、第1のSME 204、第2のSME 205、またはORゲート230のいずれかに結合するように設定できる。ORゲート230は、GOT 210の共通の出力218を形成するため、出力226、228の両方を共に結合するために使用できる。一例では、前述したように、第1および第2のSME 204、205はパリティを示し、そこで、第1のSME 204の入力214は、行相互接続導体222のいくつかに結合でき、第2のSME 205の入力216は、他の行相互接続導体222に結合できる。一例では、GOT 210内の2つのSME 204、205は、スイッチ240の一方または両方を設定することにより、カスケード接続できるか、かつ/またはそれら自身にループバックできる。SME 204、205は、SME 204、205の出力226、228を他のSME 204、205の入力214、216に結合することにより、カスケード接続できる。SME 204、205は、出力226、228をそれら自身の入力214、216に結合することにより、自身にループバックできる。その結果、第1のSME 204の出力226は、第1のSME 204の入力214および第2のSME 205の入力216のどちらとも結合できないか、一方または両方と結合できる。

0023

一例では、状態機械要素204、205は、検出線234と平行に結合された、ダイナミックランダムアクセスメモリDRAM)でしばしば使用されるような、複数のメモリセル232を含む。1つのかかるメモリセル232は、高値または低値(例えば、1または0)のいずれかに対応するものなどの、データ状態に設定できるメモリセルを含む。メモリセル232の出力は、検出線234に結合され、メモリセル232への入力は、データストリーム線236上のデータに基づいて、信号を受信する。一例では、データストリーム線236上の入力が、メモリセル232の1つを選択するために復号される。選択されたメモリセル232は、その格納されたデータ状態を出力として検出線234上に提供する。例えば、データ入力ポート209で受信されたデータがデコーダ(図示せず)に提供でき、デコーダは、データストリーム線236のうちの1本を選択できる。一例では、デコーダは、ASCII文字を256ビットのうちの1つに変換できる。

0024

メモリセル232は、それ故、メモリセル232が高値に設定され、かつ、データストリーム線236上のデータがメモリセル232に対応する場合、高信号を検出線234に出力する。データストリーム線236上のデータがメモリセル232に対応し、メモリセル232が低値に設定されている場合、メモリセル232は、低信号を検出線234に出力する。メモリセル232からの検出線234上への出力は、検出回路238によって検知される。一例では、入力線214、216上の信号は、それぞれの検出回路238をアクティブ状態または非アクティブ状態のいずれかに設定する。非アクティブ状態に設定されると、検出回路238は、それぞれの検出線234上の信号にかかわらず、低信号をそれぞれの出力226、228上に出力する。アクティブ状態に設定されると、高信号がそれぞれのSME 204、205のメモリセル232の1つから検出される場合、検出回路238は、高信号をそれぞれの出力線226、228上に出力する。アクティブ状態にある場合、それぞれのSME 204、205のメモリセル232の全てからの信号が低ければ、検出回路238は、低信号をそれぞれの出力線226、228上に出力する。

0025

一例では、SME 204、205は、メモリセル232を含み、各メモリセル232は、異なるデータストリーム線236に結合される。それ故、SME 204、205は、選択された1つまたは複数のデータストリーム線236がその上に高信号を有する場合、高信号を出力するようにプログラムされ得る。例えば、SME 204は、第1のメモリセル232(例えば、ビット0)を高に設定し、他の全てのメモリセル232(例えば、ビット1〜255)を低に設定できる。それぞれの検出回路238がアクティブ状態にあるとき、SME 204は、ビット0に対応するデータストリーム線236がその上に高信号を有する場合、高信号を出力226上に出力する。他の例では、複数のデータストリーム線236のうちの1本が、適切なメモリセル232を高値に設定することにより、その上に高信号を有する場合、SME 204は、高信号を出力するように設定できる。

0026

一例では、メモリセル232は、関連したレジスタからビットを読み取ることにより、高値または低値に設定できる。その結果、SME 204は、コンパイラによって作成されたイメージをレジスタ内に格納し、レジスタ内のビットを関連したメモリセル232にロードすることにより、プログラムされ得る。一例では、コンパイラによって作成されたイメージは、高および低(例えば、1および0)ビットのバイナリイメージを含む。イメージは、SME 204、205をカスケード接続することにより、FSMエンジン200をFSMとして動作するようにプログラムできる。例えば、第1のSME 204は、検出回路238をアクティブ状態に設定することにより、アクティブ状態に設定できる。第1のSME 204は、ビット0に対応するデータストリーム線236がその上に高信号を有する場合、高信号を出力するように設定できる。第2のSME 205は、最初は非アクティブ状態に設定できるが、アクティブなとき、ビット1に対応するデータストリーム線236がその上に高信号を有する場合、高信号を出力するように設定できる。第1のSME 204および第2のSME 205は、第1のSME 204の出力226を第2のSME 205の入力216に結合するように設定することにより、カスケード接続できる。従って、高信号が、ビット0に対応するデータストリーム線236上で検知される場合、第1のSME 204は、高信号を出力226上に出力し、第2のSME 205の検出回路238をアクティブ状態に設定する。高信号が、ビット1に対応するデータストリーム線236上で検知される場合、第2のSME 205は、別のSME 205をアクティブにするため、またはFSMエンジン200からの出力のため、高信号を出力228上に出力する。

0027

図6は、コンパイラがソースコードを、並列マシンをプログラムするように構成されたイメージに変換するための方法600の一例を示す。方法600は、ソースコードを構文木解析すること(ブロック602)、構文木をオートマトンに変換すること(ブロック604)、オートマトンを最適化すること(ブロック606)、オートマトンをネットリストに変換すること(ブロック608)、ネットリストをハードウェア上に配置すること(ブロック610)、ネットリストをルーティングすること(ブロック612)、および結果として生じるイメージを公開すること(ブロック614)を含む。

0028

一例では、コンパイラは、ソフトウェア開発者がFSMエンジン600上でFSMを実装するために、イメージを作成できるようにする、アプリケーションプログラミングインタフェースAPI)を含む。コンパイラは、ソースコード内の正規表現入力セットを、FSMエンジン600をプログラムするように構成されているイメージに変換するための方法を提供する。コンパイラは、フォンノイマンアーキテクチャを有するコンピュータ用の命令によって実装できる。これらの命令は、コンピュータ上のプロセッサにコンパイラの機能を実装させることができる。例えば、命令は、プロセッサによって実行される場合、プロセッサがアクセス可能なソースコード上のブロック602、604、606、608、610、612、および614に記載する動作をプロセッサに実行させることができる。フォンノイマン型アーキテクチャを有するコンピュータ例が図9に示され、以下で説明される。

0029

一例では、ソースコードは、シンボルグループ内のシンボルのパターンを識別するための検索文字列を記述する。検索文字列を記述するため、ソースコードは、複数の正規表現(regex)を含むことができる。正規表現は、シンボル検索パターンを記述するための文字列であり得る。正規表現は、プログラミング言語テキストエディタネットワークセキュリティ、およびその他などの、様々なコンピュータドメイン幅広く使用されている。一例では、コンパイラによってサポートされる正規表現は、非構造化データ検索するための検索基準を含む。非構造化データは、自由形式のデータを含み得、データ内のワード(word)に適用された指標付けがない。ワードは、データ内に、印刷可能および印字不能な、バイトの任意の組合せを含み得る。一例では、コンパイラは、Perl(例えば、Perl互換正規表現(PCRE))、PHP、Java(登録商標)、および.NET言語を含む、正規表現を実装するための、複数の異なるソースコード言語をサポートできる。

0030

図6を再度参照すると、ブロック602で、コンパイラは、ソースコードを解析して、関係的に結合された演算子の配置を形成でき、そこでは、異なるタイプの演算子は、ソースコードによって実装された異なる機能(例えば、ソースコード内の正規表現によって実装された異なる機能)に対応する。ソースコードの解析により、ソースコードの一般的表現を作成できる。一例では、一般的表現は、ソースコード内の正規表現の、構文木として知られているツリーグラフの形でコード化された表現を含む。本明細書で説明する例は、そのアレンジメントを構文木(「抽象構文木」としても知られている)と呼ぶ。しかし、他の例では、具象構文木または他のアレンジメントも使用できる。

0031

前述したように、コンパイラは、複数言語のソースコードをサポートできるので、解析は、その言語にかかわらず、ソースコードを、例えば、構文木などの、言語固有でない表現に変換する。従って、コンパイラによるさらなる処理(ブロック604、606、608、610)は、ソースコードの言語にかかわらず、共通の入力構造から動作できる。

0032

前述したように、構文木は、関係的に結合されている複数の演算子を含む。構文木は、複数の異なるタイプの演算子を含むことができる。すなわち、異なる演算子は、ソースコード内の正規表現によって実装された異なる機能に対応できる。

0033

ブロック604で、構文木はオートマトンに変換される。オートマトン(有限状態オートマトン、有限状態機械(FSM)、または単に状態機械とも呼ばれる)は、状態、状態間の遷移、および動作の表現であり、決定性または非決定性として分類できる。決定性オートマトンは、一時に、単一経路の実行を有するが、他方、非決定性オートマトンは、複数の並列経路の実行を有する。オートマトンは、複数の状態を含む。構文木をオートマトンに変換するために、構文木内の演算子および演算子間の関係は、状態間の遷移をもつ状態に変換される。一例では、オートマトンは、FSMエンジン200のハードウェアに一部基づいて変換され得る。

0034

一例では、オートマトンに対する入力シンボルは、アルファベット、0〜9の数字、および他の印刷可能な文字のシンボルを含む。一例では、入力シンボルは、バイト値0〜255で表される。一例では、オートマトンは、グラフノードが状態の集合に対応する有向グラフとして表され得る。一例では、入力シンボルαを受けての状態pから状態qへの遷移、すなわち、δ(p,α)は、ノードpからノードqへの有向接続によって示される。一例では、オートマトンによって受け入れられた(例えば、一致した)言語は、オートマトンに連続して入力される場合に、最終状態に達し得る全ての可能な文字列の集合である。オートマトンによって受け入れられた言語内の各文字列は、開始状態から1つまたは複数の最終状態への経路を辿る。

0035

一例では、入力シンボル範囲外の特別な遷移シンボルが、オートマトン内で使用され得る。これらの特別な遷移シンボルは、例えば、専用要素224の使用を可能にするために使用できる。さらに、特別な遷移シンボルは、入力シンボル以外の何かを受けて起こる遷移を提供するために使用できる。例えば、特別な遷移シンボルは、第2の状態および第3の状態の両方が有効な場合に、第1の状態が有効にされる(例えば、遷移される)ことを示し得る。その結果、第1の状態は、第2の状態および第3の状態の両方がアクティブにされる場合にアクティブにされ、また、第1の状態への遷移は、入力シンボルに直接依存しない。特に、第2の状態および第3の状態の両方が有効な場合に、第1の状態が有効にされることを示す特別な遷移シンボルは、例えば、専用要素224としてのブール論理によって実行されるブールAND関数を表すために使用できる。一例では、特別な遷移シンボルは、カウンタ状態がゼロに達したこと、従って下流の状態への遷移を示すために使用できる。

0036

一例では、オートマトンは、汎用状態ならびに専用状態を含む。汎用状態および専用状態は、コンパイラがそれに対して機械コードを生成している対象デバイスによってサポートされる汎用要素および専用要素に対応する。異なるタイプの対象デバイスは、異なるタイプの汎用要素ならびに1つまたは複数の異なるタイプの専用要素をサポートできる。汎用要素は、通常、幅広い範囲の機能を実装するために使用でき、他方、専用要素は、通常、もっと狭い範囲の機能を実装するために使用できる。しかし、一例では、専用要素は、例えば、その狭い範囲の機能内でより大きな効果を得ることができる。その結果、専用要素は、例えば、対象デバイスにおいて特定の機能を実装するために必要なマシンサイクルまたはマシンリソースを削減するために使用できる。いくつかの例では、対象デバイスは、単に専用要素をサポートし、そこで、複数の異なるタイプの専用要素がサポートされる。

0037

コンパイラがFSMエンジン200に対して機械コードを生成している例では、汎用状態はSME 204、205に対応でき、汎用状態はそれに応じて本明細書では「SME状態」と呼ばれる。さらに、コンパイラがFSMエンジン200に対して機械コードを生成している場合、専用状態の一例は、カウンタ224に対応でき、それに応じて本明細書では「カウンタ状態」と呼ばれる。専用状態の別の例は、論理要素(例えば、プログラム可能論理、ブール論理)に対応でき、それに応じて本明細書では「論理状態」と呼ばれる。一例では、オートマトン内のSME状態は、SMEにマッピングしないオートマトンの開始状態を除いて、FSMエンジン200内のSME(例えば、SME 204、205)に1:1でマッピングする。専用要素224は、専用状態に1:1でマッピングすることもあれば、しないこともある。

0038

一例では、オートマトンは、グルコフの方法などの、標準的な方法の1つを使用して構築できる。一例では、オートマトンは、εのない(ε−free)均質な(homogenous)オートマトンであり得る。均質なオートマトンは、一般的なオートマトン定義に関する制限である。その制限は、1つの状態に入る全ての遷移が同じ入力シンボルを受けて起こらなければならないことを必要とする。均質なオートマトンは、以下の条件を満足する:任意の2つの状態、q1およびq2に対して、r∈δ(q1)∩δ(q2)であれば、S1={a|a∈Σ,r∈δ(q1,a)}、S2={a|a∈Σ,r∈δ(q2,a)}を示す。S1は、q1がrに遷移できるようにするシンボルの集合であり、S2は、q2がrに遷移できるようにするシンボルの集合である。ここで、S1=S2、すなわち、状態q1および状態q2が両方とも状態rに遷移する場合、均質な制限は、遷移が同じシンボルを受けて起こらなければならないことである。

0039

図7Aおよび図7Bは、構文木から作られたオートマトンの例を示す。図7Aは、均質なオートマトン700を示し、図7Bは非均質なオートマトン702を示す。

0040

均質なオートマトン700は、入力シンボル「a」を受けて状態706に遷移する開始状態704から始まる。状態706は、入力シンボル「b」を受けて状態708に遷移し、状態708は、入力シンボル「b」を受けて状態710に遷移する。状態710は、入力シンボル「c」を受けて状態712に遷移する。状態712は、入力シンボル「b」を受けて状態710に遷移し、入力シンボル「d」を受けて状態714に遷移する。状態714は、最終状態であり、二重丸によってそのようなものとして識別される。一例では、最終状態のアクティブ化はオートマトンに対応する正規表現の一致を示すので、最終状態は、重要であり得る。所与の状態に対する全ての入側の遷移(in−transition)(例えば、状態への遷移)は同じシンボルを受けて起こるので、オートマトン700は、均質なオートマトンである。特に、状態710は、(状態708および状態712からの)2つの入側の遷移を有し、両方の入側の遷移が同じシンボル「b」を受けて起こる。

0041

非均質なオートマトン702は、均質なオートマトン700と同じ状態704、706、708、710、712、および714を含むが、状態712は、入力シンボル「e」を受けて状態710に遷移する。その結果、状態710は2つの異なるシンボル、すなわち、状態708からのシンボル「b」および状態712からのシンボル「e」、を受けての入側の遷移を有するので、オートマトン702は非均質である。

0042

ブロック606で、オートマトンが構築された後、オートマトンが、とりわけ、その複雑性およびサイズを縮小するように最適化される。オートマトンは、重複する状態を結合することにより最適化できる。

0043

ブロック608で、オートマトンがネットリストに変換される。オートマトンのネットリストへの変換は、オートマトンの状態をFSMエンジン200のハードウェア要素(例えば、SME 204、205、GOT210、専用要素224)のインスタンスにマッピングし、インスタンス間の関係を決定する。一例では、ネットリストは、複数のインスタンスを含み、各インスタンスは、FSMエンジン200のハードウェア要素に対応する(例えば、表す)。各インスタンスは、別のインスタンスへの接続のための1つまたは複数の接続点(本明細書では「ポート」とも呼ばれる)を持つことができる。ネットリストは、インスタンスに対応するハードウェア要素を結合する導体に対応する(例えば、表す)インスタンスのポート間の複数の接続も含む。一例では、ネットリストは、異なるタイプのハードウェア要素に対応する異なるタイプのインスタンスを含む。例えば、ネットリストは、汎用ハードウェア要素に対応する汎用インスタンスおよび専用ハードウェア要素に対応する専用インスタンスを含むことができる。一例として、汎用状態は汎用インスタンスに変換することができ、専用状態は、専用インスタンスに変換することができる。一例では、汎用インスタンスは、SME 204、205に対するSMEインスタンス、およびSMEのグループを含むハードウェア要素に対するSMEグループインスタンスを含むことができる。一例では、SMEグループインスタンスは、GOT 210に対応するGOTインスタンスを含むが、他の例では、SMEグループインスタンスは、3つ以上のSMEのグループを含むハードウェア要素に対応できる。専用インスタンスは、カウンタ224に対するカウンタインスタンス、および論理要素224に対する論理インスタンスを含み得る。GOT 210は2つのSME 204、205を含むので、GOTインスタンスは、2つのSMEインスタンスを含む。

0044

ネットリストを作成するために、オートマトン内の状態が、ネットリスト内のインスタンスに変換されるが、開始状態が対応するインスタンスを持たないことを除く。SME状態は、GOTインスタンスに変換され、カウンタ状態はカウンタインスタンスに変換される。その上、第1のインスタンスから第2のインスタンスへの対応する接続が、第1のインスタンスに対応する状態から第2のインスタンスに対応する状態への遷移に対して作成される。FSMエンジン200内のSME 204、205が、GOT 210と呼ばれるペアにグループ化されるので、コンパイラは、SME状態を、GOTインスタンス内のペアにグループ化できる。GOT 210の物理的設計に起因して、SMEインスタンスの全てがGOT 210を形成するために共にペア形成できるわけではない。その結果、コンパイラは、どのSME状態がGOT 210内で共にマッピングできるかを判断し、次いで、その判断に基づいてSME状態をGOTインスタンスにペア形成する。

0045

図5に示すように、GOT210は、SME 204、205に関する出力制約を有する。特に、GOT 210は、2つのSME 204、205によって共有される単一の出力218を有する。その結果、GOT 210内の各SME 204、205は、出力218を独立して駆動できない。この出力制約は、どのSME状態がGOTインスタンス内で共にペア形成できるかを制限する。特に、外部のSME状態(例えば、GOTインスタンスの外部のSMEに対応するSME状態)の異なる集合を駆動する(例えば、遷移する、アクティブにする)2つのSME状態は、GOTインスタンス内で共にペア形成できない。しかし、GOT 210は、この機能をスイッチ240で内部で提供できるので、この制約は、2つのSME状態が互いに駆動するか、または自己ループを駆動するかを制限しない。FSMエンジン200は、SME 204、205に対応する特定の物理的設計を有するとして説明されているが、他の例では、SME 204、205は、他の物理的設計を有し得る。例えば、SME 204、205は、SME 204、205の3つ以上のセットに共にグループ化され得る。さらに、いくつかの例では、SME 204、205からの出力226、228に関する制限の有無にかかわらず、SME 204、205に対する入力214、216に関する制限があり得る。

0046

しかし、いずれにせよ、コンパイラは、FSMエンジン200の物理的設計に基づいてどのSME状態が共にグループ化できるかを判断する。その結果、GOTインスタンスに対して、コンパイラは、GOT 210内のSME 204、205に対する出力制約に基づいて、どのSME状態が共にペア形成できるかを判断する。一例では、GOT 210の物理的設計に基づいて、GOT 210を形成するために、2つのSME状態が共にペア形成できる5つの状況がある。

0047

第1および第2のSME状態がGOT210内に共にペア形成できる第1の状況は、第1または第2のSME状態のどちらも最終状態でなく、かつ、第1および第2のSME状態の一方が、第1または第2のSME状態以外のどの状態も駆動しない場合に起こる。一例として、第1の状態が第2の状態に遷移する場合、第1の状態が第2の状態を駆動すると考えられる。この第1の状況が起こる場合、最大で、第1および第2のSME状態のうちの1つが外部の状態を駆動している。その結果、第1および第2のSME状態が、GOT 210の出力制約によって影響を受けることなく、共にペア形成できる。しかし、SME 204、205を内部で互いに結合するGOT 210の能力に起因して、第1および第2のSME状態は、互いに駆動するか、または自身を駆動するために自己ループすることが可能にされる。オートマトンの用語では、第1のSME状態(状態q1に対応する)および第2のSME状態(状態q2に対応する)は、q1およびq2のどちらも最終状態ではなく、かつδ(q1)−{q1,q2}が空であるか、またはδ(q2)−{q1,q2}が空である場合、共にペア形成できる。

0048

第1および第2のSME状態がGOT210内に共にペア形成できる第2の状況は、第1または第2のSME状態のどちらもオートマトン内の最終状態でない場合、ならびに、第1および第2のSME状態の両方が同じ外部状態を駆動する場合に起こる。本明細書では、外部状態は、例えば、GOT 210インスタンス内の第1および第2のSME状態が互いに駆動するか、または自己ループするかに関わらず、GOTインスタンスの外部の状態に対応する。ここで再度、第1および第2のSME状態が同じ外部状態を駆動するので、GOT 210の出力制約は、第1および第2のSME状態に影響を及ぼさない。また、SME 204、205を内部で互いに結合するGOT 210の能力に起因して、同じ状態の駆動に関する制限が、第1の状態および第2の状態が互いに駆動するか、または自己ループするかを含まない。オートマトンの用語を使用すると、第1のSME状態(状態q1に対応する)および第2のSME状態(状態q2に対応する)は、q1およびq2のどちらも最終状態ではなく、かつδ(q1)−{q1,q2}=δ(q2)−{q1,q2}である場合に、共にペア形成できる。

0049

第1および第2のSME状態がGOT210内に共にペア形成できる第3および第4の状況は、第1および第2のSME状態の一方が最終状態であり、かつ、第1および第2のSME状態の他方がどの外部状態も駆動しない場合に起こる。すなわち、第1のSME状態(状態q1に対応する)および第2のSME状態(状態q2に対応する)は、q1が最終状態であり、かつδ(q2)−{q1,q2}が空であるか、またはq2が最終状態に対応し、かつδ(q1)−{q1,q2}が空である場合、共にペア形成できる。最終状態は正規表現との一致の表示を出力するので、最終状態に対応するSME状態は、一致を示すためにGOT 210の出力218を独立して使用すべきである。その結果、GOT 210内の他のSME状態は、出力218の使用を許可されない。

0050

第1および第2のSME状態がGOT210内に共にペア形成できる第5の状況は、第1および第2のSME状態の両方がオートマトン内の最終状態に対応し、かつ、第1および第2のSME状態の両方が同じ外部状態を駆動する場合に起こる。オートマトンの用語を使用すると、第1の状態(状態q1に対応する)および第2のSME状態(状態q2に対応する)は、q1およびq2の両方が最終状態であり、かつδ(q1)−{q1,q2}=δ(q2)−{q1,q2}である場合に、共にペア形成できる。

0051

1つまたは複数のSME状態が共にペア形成できるかどうかをコンパイラが判断すると、コンパイラは、そのSME状態をGOTインスタンスにペア形成する。一例では、コンパイラは、SME状態が、GOTインスタンスを形成するためにペア形成することができると判断される順に、SME状態をGOTインスタンスにペア形成する。すなわち、2つの特定のSME状態が共にペア形成することができると判断されると、これら2つのSME状態がGOTインスタンスにペア形成できる。2つのSME状態がペア形成されてGOTインスタンスを形成すると、これらペア形成されたSME状態は、他のSME状態とペア形成するために利用できない。このプロセスは、ペア形成するSME状態がもうなくなるまで継続され得る。

0052

一例では、コンパイラは、どのSMEをGOTインスタンスに共にペア形成できるかを判断するためにグラフ理論を使用する。特定のSMEのみが共にペア形成できるので、あるSMEのペア形成は、結果として、他のSMEがそれら自身のGOTインスタンス内で実装される必要があり、GOTインスタンス内の他のSME位置が未使用で、従って無駄になり得る。グラフ理論は、ネットリストのGOTインスタンス内の未使用のSMEインスタンスの数を減らすことにより、GOT 210内でのSME利用(例えば、未使用のSMEの数を減らす)を最適化するために使用できる。グラフ理論を使用するため、コンパイラは、まず、前述したFSMエンジン200の物理的設計に従って、SME状態間で全ての可能なペア形成を判断する。コンパイラは、次いで、グラフのバーテックス(vertex)がSME状態に対応し、グラフのエッジがSME状態の可能なペア形成に対応するグラフを作成する。すなわち、2つのSME状態がGOTインスタンス内で共にペア形成することができると判断されると、その2つの対応するバーテックスがエッジと結合される。従って、グラフは、SME状態の全ての可能なペア形成を含む。

0053

コンパイラは、次いで、どのSME状態をGOT210内で共にペア形成するかを識別するため、グラフに対して、一致するバーテックスを見つけることができる。すなわち、グラフの一致するバーテックス間のどの2つのエッジも共通のバーテックスを共有しないように、コンパイラがエッジ(および従ってバーテックスのペア)を識別する。一例では、コンパイラは、グラフに対して最大限マッチング(maximal matching)を見つけることができる。別の例では、コンパイラは、グラフに対して最大マッチング(maximum matching)を見つけることができる。最大マッチングは、できる限り多くのエッジを含むマッチングである。多数の最大マッチングがあり得る。一般グラフの最大マッチングを見つける問題は、多項式時間で解決できる。

0054

全ての一致するバーテックスが(例えば、最大マッチングとして)識別されると、一致するバーテックスに対応するSME状態の各ペアが、GOTインスタンスにマッピングされる。一致しないバーテックスに対応するSME状態は、それら自身のGOTインスタンスにマッピングされる。すなわち、一致しないバーテックスに対応するSME状態は、GOTインスタンス内のSME位置の1つにマッピングされ、GOTインスタンス内の他方のSME位置は未使用となる。その結果、ネットリストNおよびその一致するバーテックスの対応する集合Mを前提として、使用されたNのGOTインスタンスの数が|Q|−1−|M|に等しく、式中Qはオートマトンの状態の集合であり、「−1」は、この例では、オートマトンの開始状態がSME状態に対応しないからである。

0055

一例では、Gの最大マッチングMから構築されているネットリストNは、最小数のGOTインスタンスを使用する。これは、以下によって示され得る:さらに少ない数のGOTインスタンスを使用する別のネットリストN´が存在する場合、対応する一致はM´として示される。N´のGOTインスタンスの数が|Q|−1−|M´|に等しいので、|M|<|M´|となる。これは、Mが最大マッチングであるという事実と矛盾する。従って、ネットリストNは、GOTインスタンスの最小数を使用する。

0056

SME状態がGOTインスタンスにペア形成されると、GOTインスタンス、カウンタインスタンス、および論理インスタンスが、オートマトン内の状態間の遷移に従って、結合される。各GOT 210は、単一の出力を有するので、ネットリスト内の各GOTインスタンスは、他のインスタンスに結合するための単一の出力ポートを有する。その結果、第1のGOTインスタンス内のどちらか一方のSME状態が第2のGOTインスタンス内のSME状態を駆動する場合、第1のGOTインスタンスの出力ポートが第2のGOTインスタンスの入力に結合される。

0057

図8Aおよび図8Bは、図7Aの均質なオートマトン700から作成されたネットリスト例800、802を示す。SMEインスタンス806、808、810、812、および814は、オートマトン700内の状態706、708、710、712、および714に対応する。オートマトンの開始状態704は、前述したように、インスタンスに対応しない。

0058

ネットリスト800は、非最適のネットリストの例である。ネットリスト800は、4つのGOTインスタンス816を使用するが、3つのSMEインスタンス818を未使用のまま残している。しかし、ネットリスト802は、最大マッチングを識別するために、グラフ理論を使用して作成された最適なネットリストの例である。ネットリスト802は、3つのGOTインスタンス816を使用し、未使用のSMEインスタンス818が1つある。ネットリスト802では、インスタンス810は、GOTインスタンス内部の接続(例えば、スイッチ240を介して)で、インスタンス812に接続できる。

0059

ブロック610で、ネットリストが生成されると、ネットリストの各インスタンスに対して、対象デバイスの特定のハードウェア要素(例えば、SME 204、205、他の要素224)を選択するために、ネットリストが位置付けられる。本発明の一実施形態によれば、位置付けると、そのハードウェア要素に対する一般入力および出力制約に基づいてハードウェア要素を選択する。

0060

ブロック612で、ネットリストによって記述された接続を達成するため、選択されたハードウェア要素を共に結合するために、グローバルに位置付けられたネットリストが、プログラム可能スイッチ(例えば、ブロック間スイッチ203、ブロック内スイッチ208、および行内スイッチ212)に対する設定を決定するようにルーティングされる。一例では、プログラム可能スイッチに対する設定が、選択されたハードウェア要素を接続するために使用されるFSMエンジン200の特定の導体を決定することにより決定される。ルーティングは、FSMエンジン200上の導体および/またはスイッチの物理的設計を前提として、ハードウェア要素を結合するためなど、位置付け中にネットリストインスタンスのいくつかに対して選択された特定のハードウェア要素を調整し得る。

0061

ネットリストが位置付けられルーティングされると、位置付けられルーティングされたネットリストは、FSMエンジン200のプログラミング用に複数のビットに変換できる。複数のビットはここではイメージと呼ばれる。

0062

ブロック614で、イメージがコンパイラによって公開される。イメージは、FSMエンジン200の特定のハードウェア要素および/またはプログラム可能スイッチをプログラミングするための複数のビットを含む。イメージが複数のビット(例えば、0および1)を含む実施形態では、イメージは、バイナリイメージと呼ぶことができる。ビットは、プログラム化されたFSMエンジン200が、ソースコードによって記述された機能を有するFSMを実装するように、SME 204、205の状態、専用要素224、およびプログラム可能スイッチをプログラムするためにFSMエンジン200上にロードできる。位置付け(ブロック610)およびルーティング(ブロック612)は、特定のハードウェア要素をFSMエンジン200内の特定の位置で、オートマトン内の特定の状態にマッピングできる。その結果、イメージ内のビットは、特定のハードウェア要素および/またはプログラム可能スイッチを所望の機能を実装するようにプログラムできる。一例では、イメージは、機械コードをコンピュータ可読媒体に保存することにより公開できる。別の例では、イメージは、イメージをディスプレイ装置上に表示することにより公開できる。さらに別の例では、イメージは、イメージをFSMエンジン200上にロードするためのプログラミング装置などの、別の装置にイメージを送信することにより、公開できる。さらにまた別の例では、イメージは、イメージを並列マシン(例えば、FSMエンジン200)上にロードすることにより、公開できる。

0063

一例では、イメージは、イメージからのビット値をSME 204、205、および他のハードウェア要素224に直接ロードするか、またはイメージを1つまたは複数のレジスタにロードし、次いで、レジスタからのビット値をSME 204、205、および他のハードウェア要素224に書き込むかのいずれかにより、FSMエンジン200上にロードできる。一例では、プログラム可能スイッチ(例えば、ブロック間スイッチ203、ブロック内スイッチ208、および行内スイッチ212)の状態。一例では、FSMエンジン200のハードウェア要素(例えば、SME 204、205、他の要素224、プログラム可能スイッチ203、208、212)が、プログラミング装置および/またはコンピュータが、イメージを1つまたは複数のメモリアドレスに書き込むことにより、イメージをFSMエンジン200上にロードできるように、メモリマップされる。

0064

本明細書で説明する方法例は、少なくとも一部は、機械またはコンピュータ実装できる。いくつかの例は、上の例で説明した方法を実行する電子装置を構成するように動作可能な命令でコード化されたコンピュータ可読媒体または機械可読媒体を含み得る。かかる方法の実装は、マイクロコードアセンブリ言語コード、高水準言語コード、または同様のものなどの、コードを含み得る。かかるコードは、様々な方法を実行するためのコンピュータ可読命令を含み得る。コードは、コンピュータプログラム製品の一部を形成し得る。さらに、コードは、実行中または他の時に、1つもしくは複数の揮発性または不揮発性のコンピュータ可読媒体上に有形的に格納され得る。これらのコンピュータ可読媒体は、ハードディスク、取り外し可能磁気ディスク、取り外し可能光ディスク(例えば、コンパクトディスクおよびデジタルビデオディスク)、磁気カセットメモリカードまたはメモリスティックランダムアクセスメモリ(RAM)、読取り専用メモリ(ROM)、および同様のものを含み得るが、これらに限定されない。

0065

図9は、フォンノイマン型アーキテクチャを有するコンピュータ900の例をおおまかに示す。本開示の内容を読んで理解すると、当業者であれば、ソフトウェアプログラム内に定義された機能を実行するために、ソフトウェアプログラムが、コンピュータベースシステム内のコンピュータ可読媒体から起動できる方法を理解するであろう。当業者は、さらに、本明細書で開示する方法を実装および実行するように設計された1つまたは複数のソフトウェアプログラムを作成するために採用できる様々なプログラム言語を理解するであろう。プログラムは、Java、C++、または1つもしくは複数の他の言語などのオブジェクト指向言語を使用して、オブジェクト指向フォーマット構造化できる。代替として、プログラムは、アセンブリ、C、などの手続き型言語を使用して、手続指向フォーマットで構造化できる。ソフトウェアコンポーネントは、リモートプロシージャコールまたはその他を含む、アプリケーションプログラムインタフェースまたはプロセス間通信技術など、当業者に周知の任意の数の機構を使用して、通信できる。様々な実施形態の技術は、任意の特定のプログラム言語または環境に制限されない。

0066

このようにして、他の実施形態が実現できる。例えば、コンピュータ、メモリシステム、磁気ディスクもしくは光ディスク、何らかの他の記憶装置、または任意のタイプの電子装置もしくはシステムなどの、製品は、その上に格納された命令924(例えば、コンピュータプログラム命令)を有するメモリ(例えば、取り外し可能記憶媒体、ならびに電気導体光導体、または電磁導体を含む任意のメモリ)などの、コンピュータ可読媒体922に結合された1つまたは複数のプロセッサ902を含み得、それは、1つまたは複数のプロセッサ902で実行される場合に、上の方法に関して説明した動作のいずれかを実行する結果となる。

0067

コンピュータ900は、いくつかのコンポーネントに直接、および/またはバス908を使用して、結合されたプロセッサ902を有するコンピュータシステムの形をとることができる。かかるコンポーネントには、メインメモリ904、スタティックまたは不揮発性メモリ906、および大容量記憶916を含み得る。プロセッサ902に結合された他のコンポーネントには、ビデオディスプレイなどの出力装置910、キーボードなどの入力装置912、およびマウスなどのカーソル制御装置914を含み得る。プロセッサ902および他のコンポーネントをネットワーク926に結合するためのネットワークインタフェース装置920は、バス908にも結合できる。命令924は、いくつかの周知の転送プロトコル(例えば、HTTP)のうちの任意の1つを利用するネットワークインタフェース装置920を経由し、ネットワーク926を通して、さらに転送または受信され得る。バス908に結合されたこれら要素のいずれかは、実現される特定の実施形態に応じて、存在しないか、単独で存在し得るか、または複数で存在し得る。

0068

一例では、1つまたは複数のプロセッサ902、メモリ904、906、または記憶装置916は各々、コンピュータ900に、実行時に、本明細書に記載する方法のいずれか1つまたは複数を実行させ得る、命令924を含むことができる。代替実施形態では、コンピュータ900は、スタンドアロン装置として動作するか、または他の装置に接続(例えば、ネットワーク接続)できる。ネットワーク化された環境では、コンピュータ900は、サーバークライアントネットワーク環境内のサーバーもしくはクライアント装置資格で、または、ピアツーピア(もしくは分散)ネットワーク環境内のピア装置として、動作できる。コンピュータ900には、パーソナルコンピュータ(PC)、タブレットPC、セットトップボックス(STB)、携帯情報端末(PDA)、携帯電話、ウェブアプライアンス、ネットワークルーター、スイッチもしくはブリッジ、またはその装置によってとられる動作を指定する命令のセットを(連続して、もしくは他の方法で)実行可能な任意の装置を含み得る。さらに、単一のコンピュータ900のみが示されているが、「コンピュータ」という用語は、本明細書で説明する方法のいずれか1つまたは複数を実行するための命令のセット(または複数のセット)を単独に、または一緒に実行する装置の任意の集合を含むようにも解釈されるものとする。

0069

コンピュータ900は、1つまたは複数の通信プロトコル(例えば、ユニバーサルシリアルバス(USB)、IEEE 1394など)を使用して周辺機器と通信するための出力コントローラ928も含むことができる。出力コントローラ928は、例えば、コンピュータ900に通信的に結合されているプログラミング装置930にイメージを提供できる。プログラミング装置930は、並列マシン(例えば、並列マシン100、FSMエンジン200)をプログラムするように構成できる。他の例では、プログラミング装置930は、コンピュータ900と統合されて、バス908に結合できるか、またはネットワークインタフェース装置920または別の装置を経由してコンピュータ900と通信できる。

0070

コンピュータ可読媒体924は単一の媒体として示されているが、「コンピュータ可読媒体」という用語は、命令924の1つまたは複数のセットを格納する単一の媒体または複数の媒体(例えば、集中型もしくは分散型データベース、または関連するキャッシュおよびサーバー、ならびに/またはプロセッサ902レジスタ、メモリ904、906、および記憶装置916などの様々な記憶媒体)を含むように解釈されるべきである。「コンピュータ可読媒体」という用語は、コンピュータによって実行するための命令のセットを格納、コード化、または運搬可能であり、かつ、コンピュータに本発明の方法のいずれか1つまたは複数を実行させるか、または命令のかかるセットによって利用されるか、またはそれに関連したデータ構造を格納、コード化、または運搬可能である、任意の媒体を含むように解釈されるものとする。「コンピュータ可読媒体」という用語は、その結果、ソリッドステートメモリ光媒体、および磁気媒体などの、有形的媒体を含むように解釈されるものとするが、それらに限定されない。

0071

要約は、読者が技術的開示の本質および要点を確認できるようにする要約を要求する米国特許規則(37 C.F.R)1.72(b)項に準拠するために提供されている。それは、請求項の範囲または意味を制限または解釈するために使用されないという理解で提示されている。以下の請求項は、これによって詳細な説明に組み込まれ、各請求項が別個の実施形態として権利を主張する。

0072

〔実施形態例〕
例1は、ソースコードから並列マシンをプログラムするように構成されたイメージを生成するためのコンピュータ実装方法を含む。本方法は、ソースコードを、複数の相互接続された状態を含むオートマトンに変換すること;そのオートマトンを、オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、そのインスタンスが並列マシンのハードウェア要素に対応し、オートマトンをネットリストに変換することが、並列マシンの物理的設計に基づいて状態を共にグループ化することを含む、オートマトンをネットリストに変換すること;および、そのネットリストをイメージに変換することを含む。

0073

例2は、命令を含むコンピュータ可読媒体を含み、それは、コンピュータによって実行されるときに、そのコンピュータに動作を実行させる。動作は、ソースコードを、複数の相互接続された状態を含むオートマトンに変換すること;そのオートマトンを、オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、そのインスタンスが並列マシンのハードウェア要素に対応し、オートマトンをネットリストに変換することが、並列マシンの物理的設計に基づいて状態を共にグループ化することを含む、オートマトンをネットリストに変換すること;および、そのネットリストをイメージに変換することを含む。

0074

例3は、ソフトウェアがその上に格納されたメモリ;およびそのメモリに通信的に結合されたプロセッサを含むコンピュータを含む。そのソフトウェアは、プロセッサによって実行されるとき、そのプロセッサに:ソースコードを、複数の相互接続された状態を含むオートマトンに変換すること;そのオートマトンを、オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、インスタンスが並列マシンのハードウェア要素に対応し、インスタンスが、複数の第1のインスタンスおよび2つ以上の第1のインスタンスを含むグループインスタンスを含み、オートマトンをネットリストに変換することが、未使用の第1のインスタンスの数に基づいて状態をグループインスタンス内に共にグループ化することを含む、オートマトンをネットリストに変換すること;および、ネットリストをイメージに変換することをさせる。

0075

例4は、ソースコードを、複数の相互接続された状態を含むオートマトンに変換すること;そのオートマトンを、オートマトンの状態に対応するインスタンスを含むネットリストに変換することであって、インスタンスが並列マシンのハードウェア要素に対応し、インスタンスが、複数の第1のインスタンスおよび2つ以上の第1のインスタンスを含むグループインスタンスを含み、オートマトンをネットリストに変換することが、未使用の第1のインスタンスの数に基づいて、状態をグループインスタンス内に共にグループ化することを含む、オートマトンをネットリストに変換すること;および、ネットリストをイメージに変換すること;を行うように構成されたコンピュータを含む、システムを含む。本システムは、イメージを並列マシン上にロードするように構成された装置も含む。

0076

例5では、例1〜4のいずれかの主題が、インスタンスが、状態機械要素(SME)ハードウェア要素に対応するSMEインスタンスおよびSMEのグループを含むハードウェア要素に対応するSMEグループインスタンスを含むこと、ならびに、グループ化することが、状態をSMEグループインスタンスにグループ化することを含むこと、を随意に含み得る。

0077

例6では、例1〜5のいずれかの主題が、物理的設計が、SMEのグループを含むハードウェア要素の物理的設計を含むこと、を随意に含み得る。

0078

例7では、例1〜6のいずれかの主題が、物理的設計が、SMEのグループを含むハードウェア要素内のSMEに関する入力制約または出力制約の1つを含むこと、を随意に含み得る。

0079

例8では、例1〜7のいずれかの主題が、物理的設計が、SMEのグループを含むハードウェア要素内のSMEが出力を共有するという制限を含むこと、を随意に含み得る。

0080

例9では、例1〜8のいずれかの主題が、SMEグループインスタンスが、2つのSMEインスタンスを含む2つのグループ(GOT)インスタンスを含むこと、および、物理的設計が、各GOT内のSMEが共通の出力に結合されていることを含むこと、を随意に含み得る。

0081

例10では、例1〜9のいずれかの主題が、オートマトンをネットリストに変換することが:どの状態がGOTインスタンス内で共にグループ化できるかを判断すること;および、その判断に基づいて状態をペア形成することを含むこと、を随意に含み得る。

0082

例11では、例1〜10のいずれかの主題が、第1の状態または第2の状態のどちらもオートマトンの最終状態ではなく、かつ、第1の状態および第2の状態の一方が、第1の状態または第2の状態以外の任意の状態を駆動しない場合に、第1の状態および第2の状態が、GOTインスタンス内で共にペア形成できること、を随意に含み得る。

0083

例12では、例1〜11のいずれかの主題が、第1の状態または第2の状態のどちらもオートマトンの最終状態ではなく、かつ、第1の状態および第2の状態の両方が、同じ外部状態を駆動する場合に、第1の状態および第2の状態が、GOTインスタンス内で共にペア形成できること、を随意に含み得る。

0084

例13では、例1〜12のいずれかの主題が、第1の状態および第2の状態の一方がオートマトンの最終状態であり、かつ、第1の状態および第2の状態の他方が、どの外部状態も駆動しない場合に、第1の状態および第2の状態が、GOTインスタンス内で共にペア形成できること、を随意に含み得る。

0085

例14では、例1〜13のいずれかの主題が、第1の状態および第2の状態の両方がオートマトンの最終状態であり、かつ、第1の状態および第2の状態の両方が、同じ外部状態を駆動する場合に、第1の状態および第2の状態が、GOTインスタンス内で共にペア形成できること、を随意に含み得る。

0086

例15では、例1〜14のいずれかの主題が、どの状態がGOTインスタンス内で共にグループ化できるかを判断することが、グラフ理論を使用して、どの状態がGOTインスタンス内で共にグループ化できるかを判断することを含むこと、を随意に含み得る。

0087

例16では、例1〜15のいずれかの主題が、グラフ理論を使用して、どの状態がGOTインスタンス内で共にグループ化できるかを判断することが、最大マッチングを識別するために、グラフ理論を使用して、どの状態がGOTインスタンス内で共にグループ化できるかを判断することを含むこと、を随意に含み得る。

0088

例17では、例1〜16のいずれかの主題が、イメージを公開すること、を随意に含み得る。

0089

例18では、例1〜17のいずれかの主題が、インスタンスが汎用インスタンスおよび専用インスタンスを含むこと、汎用インスタンスがオートマトンの汎用状態に対応し、また、専用インスタンスがオートマトンの専用状態に対応すること、を随意に含み得る。

0090

例19では、例1〜18のいずれかの主題が、汎用インスタンスに対応するハードウェア要素が状態機械要素(SME)および2つのグループ(GOT)を含むこと、ならびに専用インスタンスに対応するハードウェア要素がカウンタおよび論理要素を含むこと、を随意に含み得る。

0091

例20では、例1〜19のいずれかの主題が、オートマトンが均質なオートマトンであること、を随意に含み得る。

0092

例21では、例1〜20のいずれかの主題が、オートマトンをネットリストに変換することが、オートマトンの状態の各々を、ハードウェア要素に対応するインスタンスにマッピングすること、およびインスタンス間の接続性を決定することを含むこと、を随意に含み得る。

0093

例22では、例1〜21のいずれかの主題が、ネットリストが、ハードウェア要素間の導体を表すインスタンス間の複数の接続をさらに含むこと、を随意に含み得る。

0094

例23では、例1〜22のいずれかの主題が、オートマトンをネットリストに変換することが、オートマトンを、開始状態を除いて、オートマトンの状態に対応するインスタンスを含むネットリストに変換することを含むこと、を随意に含み得る。

0095

例24では、例1〜23のいずれかの主題が、ネットリストのインスタンスに対応するハードウェア要素の並列マシン内の位置を決定すること、を随意に含み得る。

0096

例25では、例1〜24のいずれかの主題が、状態を共にグループ化することが、汎用要素のグループを含むハードウェア要素の物理的設計に基づいて、状態を共にグループ化することを含むこと、を随意に含み得る。

0097

例26では、例1〜25のいずれかの主題が、並列マシンのどの導体がハードウェア要素を接続するために使用されるかを判断すること;および並列マシンのプログラム可能スイッチに対する設定を決定することであって、プログラム可能スイッチがハードウェア要素を選択的に共に結合するように構成されている、並列マシンのプログラム可能スイッチに対する設定を決定すること、を随意に含み得る。

0098

例27では、例1〜26のいずれかの主題が、グループインスタンスが2つのグループ(GOT)インスタンスを含むこと、および状態をグループ化することが、ペア形成された状態がどの状態を駆動するかに応じて、状態をペア形成すること、を随意に含み得る。

0099

例28では、例1〜27のいずれかの主題が、未使用の第1のインスタンスの数に基づいて状態をグループインスタンス内にグループ化することが:以下の条件:第1の状態または第2の状態のどちらもオートマトン内の最終状態ではなく、かつ第1の状態および第2の状態の一方が、第1の状態または第2の状態以外のどの状態も駆動しないこと;第1の状態または第2の状態のどちらもオートマトン内の最終状態ではなく、かつ第1の状態および第2の状態の両方が、同じ外部状態を駆動すること;第1の状態または第2の状態のどちらかが最終状態であり、かつ最終状態ではない第1の状態または第2の状態が、第1の状態または第2の状態以外のどの状態も駆動しないこと;ならびに、第1の状態および第2の状態の両方が最終状態であり、かつ第1の状態および第2の状態の両方が、同じ外部状態を駆動すること;に基づいて、第1の状態および第2の状態がペア形成できるかどうかを判断することを含むこと、を随意に含み得る。

0100

例29では、例1〜28のいずれかの主題が、オートマトンをネットリストに変換することが:状態をグラフとしてモデル化することであって、グラフのバーテックスが状態に対応し、かつグラフのエッジが状態の可能なペア形成に対応する、状態をグラフとしてモデル化すること;グラフに対して一致するバーテックスを決定すること;および一致するバーテックスに対応する状態をペア形成することを含むこと、を随意に含み得る。

0101

例30では、例1〜29のいずれかの主題が、オートマトンをネットリストに変換することが:グラフに対して最大マッチングを決定することを含むこと、を随意に含み得る。

0102

例31では、例1〜30のいずれかの主題が、オートマトンをネットリストに変換することが:一致するバーテックスに対応する状態の各セットをペア形成すること;および一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることであって、そのGOTインスタンス内の1つのSMEインスタンスが使用されない、一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることを含むこと、を随意に含み得る。

0103

例32では、例1〜31のいずれかの主題が、状態を共にグループ化することが;ペア形成された状態がどの状態を駆動するかに応じて、状態をペア形成することを含むこと、を随意に含み得る。

0104

例33では、例1〜32のいずれかの主題が、未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが:以下の条件:第1の状態または第2の状態のどちらもオートマトン内の最終状態ではなく、かつ第1の状態および第2の状態の一方が、第1の状態または第2の状態以外のどの状態も駆動しないこと;第1の状態または第2の状態のどちらもオートマトン内の最終状態ではなく、かつ第1の状態および第2の状態の両方が、同じ外部状態を駆動すること;第1の状態または第2の状態のどちらかが最終状態であり、かつ最終状態ではない第1の状態または第2の状態が、第1の状態または第2の状態以外のどの状態も駆動しないこと;ならびに、第1の状態および第2の状態の両方が最終状態であり、かつ第1の状態および第2の状態の両方が、同じ外部状態を駆動すること;に基づいて、第1の状態および第2の状態がペア形成できるかどうかを判断することを含むこと、を随意に含み得る。

0105

例34では、例1〜33のいずれかの主題が、未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが:状態をグラフとしてモデル化することであって、グラフのバーテックスが状態に対応し、かつグラフのエッジが状態の可能なペア形成に対応する、状態をグラフとしてモデル化すること;グラフに対して一致するバーテックスを決定すること;および一致するバーテックスに対応する状態をペア形成することを含むこと、を随意に含み得る。

0106

例35では、例1〜34のいずれかの主題が、未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが:グラフに対して最大マッチングを決定することを含むこと、を随意に含み得る。

0107

例36では、例1〜35のいずれかの主題が、未使用の第1のインスタンスの数に基づいて、状態を共にグループインスタンス内にグループ化することが:一致するバーテックスに対応する状態の各セットをペア形成すること;および一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることであって、そのGOTインスタンス内の1つのSMEインスタンスが使用されない、一致しないバーテックスに対応する各状態をGOTインスタンスにマッピングすることを含むこと、を随意に含み得る。

0108

例37では、例1〜36のいずれかの主題が、装置が、状態の各ペアを、並列マシン内の2つのハードウェア要素のグループとして実装するように構成されていること、を随意に含み得る。

0109

例38は、例1〜37のいずれかのプロセスによって生成されたイメージによってプログラム化された並列マシンを含む。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ