(57)【特許請求の範囲】
【請求項１】
ｍ２個のＰＥ及びｍ３個のＢＭを含むＨＸＮｅｔと、
ｍ２（ｎ−１）個の追加ＢＭを実装し、
前記ｍ及びｎは２以上の整数であることを特徴とする、ＶＬＳＩ回路。
【請求項２】
ｍ２個のＰＥ及びｍ３個のＢＭを含むＨＸＮｅｔとｍ２（ｎ−１）個の追加ＢＭを実装したＶＬＳＩ回路をｎ個含み、
前記ｍ及びｎは２以上の整数であり、
各ＶＬＳＩ回路において、前記追加ＢＭは、前記ＨＸＮｅｔ中のｍ２個のＰＥの各々から書込可能な（ｎ−１）個の追加ＢＭをｍ２組備え、
前記追加ＢＭのｍ２組は順序付けされ、ｉ組目の追加ＢＭに書込可能なＰＥをｉ番目のＰＥ（ｉは１以上ｍ２以下の整数）と表すものとし、
前記（ｎ−１）個の追加ＢＭ（１組の追加ＢＭ）は順序付けされ、
ｊ番目の順序のＶＬＳＩ回路のｉ組目の追加ＢＭの組のｋ番目の順序の追加ＢＭがｋ番目の順序（ｋ＜ｊの場合）又は（ｋ＋１）番目の順序（ｋ≧ｊの場合）のＶＬＳＩ回路のｉ番目のＰＥによって読取可能であることを特徴とする、並列コンピューティングシステム。
【請求項３】
ｋ番目の順序のＶＬＳＩ回路のｉ番目のＰＥをＰＥ（ｋ，ｉ）と表すとき、ＰＥ（ｋ１，ｉ１）からＰＥ（ｋ２，ｉ２）へのデータ転送が、
（１）ｋ１＝ｋ２であればｋ１番目のＶＬＳＩ回路内のＨＸＮｅｔによって実行され、
（２）ｋ１≠ｋ２かつｉ１＝ｉ２であればＰＥ（ｋ１，ｉ１）が所定の追加ＢＭにデータを書き込み、該データをＰＥ（ｋ２，ｉ１）が読取ることによって実行され、
（３）ｋ１≠ｋ２かつｉ１≠ｉ２であればＰＥ（ｋ１，ｉ１）が所定の追加ＢＭにデータを書き込み、該データをＰＥ（ｋ２，ｉ１）が読取り、ｋ２番目のＶＬＳＩ回路内のＨＸＮｅｔによりＰＥ（ｋ２，ｉ２）に転送されることによって実行されることを特徴とする、請求項２に記載の並列コンピューティングシステム。
【請求項４】
本体ＣＰＵと、請求項３に記載の並列コンピューティングシステムと、前記本体ＣＰＵと前記並列コンピューティングシステムとのインタフェース回路とを備えることを特徴とする、コンピュータシステム。
【請求項５】
前記並列コンピューティングシステムを用いてラジオシティの計算を行うことを特徴とする、請求項４に記載のコンピュータシステム。
【請求項６】
携帯端末装置上で動作し、
ゲームのアプリケーションにおける画像表示にラジオシティの計算を行うことを特徴とする、請求項５に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列コンピューティングのためのＶＬＳＩ回路、該ＶＬＳＩ回路を活用する並列コンピューティングシステム及び該並列コンピューティングシステムを活用するコンピュータシステムに関する。
【背景技術】
【０００２】
計算を並列化して計算を高速化することを目的とする並列コンピューティングシステムは、数十年に及ぶ研究開発がなされてきた。
並列コンピューティングシステムにおいては、ＰＥと呼ばれる計算エレメント（ＣＰＵに相当）が複数用いられて、各々のＰＥが独立に計算を行い、他のＰＥに計算結果のデータを転送する。ここで、データ転送には転送用のバスが必要となるため、多くのデータ転送を必要とする計算においてはハードウェアの構築が容易でなかった。
【０００３】
例えば、物質の拡散を表す微分方程式の数値解を求める（ラプラシアン演算を行う）場合であれば各ＰＥに空間の１座標における計算をさせ、近接する座標における計算をするＰＥ（２次元であれば４つ、３次元であれば６つ）のみにデータ転送をすればよいので、バスの数を増やさない構成が可能であった。しかし、昨今携帯端末装置においても行われる画像処理におけるラジオシティ計算においては、各ＰＥに１つの小平面における計算をさせると、全てのＰＥ間でデータ転送が必要となる可能性がある。このため、従来の並列コンピューティングシステムでは、十分な高速演算が実現されなかった。
【０００４】
ＰＥ間のデータ転送の問題を解決する方法として、例えば特許文献１には、データ転送を専門に実行する通信ネットワークを有する並列コンピューティングシステムが開示されている。しかし、かかる通信ネットワークの構築には多大なコストを要する。
【０００５】
また、特許文献２には、２次元的に配列された各々のＰＥに対応するメモリを、３ポート以上のバスに対応させ、２つの次元を超えた第３のポートを介して幅広いデータ転送を実行する並列コンピューティングシステムが開示されている。しかし、第３のポートにかかるデータ転送の具体的な実現は、個々に設計しなければならない。
【０００６】
ＰＥを２次元的に配列し任意のＰＥ間のデータ転送を可能とした並列コンピューティングシステムとしては、ＨＸＮｅｔ（非特許文献１）によるものが知られていた。ｍ２個のＰＥ（ｉ，ｊ）（１≦ｉ≦ｍ、１≦ｊ≦ｍ）として、ＰＥ（ｉ，ｊ）→ＰＥ（ｊ，ｋ）→ＰＥ（ｋ，ｌ）の順にデータ転送を行うことで、任意のＰＥ間のデータ転送を可能としたものである。ＨＸＮｅｔは、実装が保証された有用なものである。
【０００７】
一方ＨＸＮｅｔは、ＰＥの数がｍ２個に限定され、複数のＨＸＮｅｔを結合して大きなＨＸＮｅｔを構成することができない。小規模のものを後に大規模化するスケーラビリティがなかった。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平０６−０５２１２５号公報
【特許文献２】特開平０６−０７５９３０号公報
【非特許文献】
【０００９】
【非特許文献１】超並列ＶＬＳＩコンピュータ  廉田浩著  工業調査会
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明は、任意のＰＥ間のデータ転送が可能であり、スケーラビリティを持った並列コンピューティングシステムを提供することを課題とする。
また、かかる並列コンピューティングシステムを活用するコンピュータシステムを提供し、小型の携帯端末装置上でラジオシティの計算を可能とすることを課題とする。
【課題を解決するための手段】
【００１１】
小規模のＨＸＮｅｔをＶＬＳＩ回路によって実現する。ＶＬＳＩ回路は、ＨＸＮｅｔに使用するＢＭ（ＢＭは「バッファメモリ」を表す。）に加え、他のＶＬＳＩ回路にデータを転送するための追加ＢＭを備える。これにより、任意の数のＶＬＳＩを結合して並列コンピューティングシステムを構成することができ、任意のＰＥ間でのデータ転送が可能となる。
【００１２】
本発明のＶＬＳＩ回路は、
ｍ２個のＰＥ及びｍ３個のＢＭを含むＨＸＮｅｔと、
ｍ２（ｎ−１）個の追加ＢＭを実装したことを特徴とする。
【００１３】
ＨＸＮｅｔをＶＬＳＩに実装し、他のＶＬＳＩとのデータ転送のための追加ＢＭを更に実装する。ここで、ｍ及びｎは２以上の整数である。
【００１４】
本発明の並列コンピューティングシステムは、
ｍ２個のＰＥ及びｍ３個のＢＭを含むＨＸＮｅｔとｍ２（ｎ−１）個の追加ＢＭを実装したＶＬＳＩ回路をｎ個含み、
前記ｍ及びｎは２以上の整数であり、
各ＶＬＳＩ回路において、  前記追加ＢＭは、前記ＨＸＮｅｔ中のｍ２個のＰＥの各々から書込可能な（ｎ−１）個の追加ＢＭをｍ２組備え、
前記追加ＢＭのｍ２組は順序付けされ、ｉ組目の追加ＢＭに書込可能なＰＥをｉ番目のＰＥ（ｉは１以上ｍ２以下の整数）と表すものとし、
前記（ｎ−１）個の追加ＢＭ（１組の追加ＢＭ）は順序付けされ、
ｊ番目の順序のＶＬＳＩ回路のｉ組目の追加ＢＭの組のｋ番目の順序の追加ＢＭがｋ番目の順序（ｋ＜ｊの場合）又は（ｋ＋１）番目の順序（ｋ≧ｊの場合）のＶＬＳＩ回路のｉ番目のＰＥによって読取可能であることを特徴とする。
【００１５】
各々の追加ＢＭからのデータ転送先のバスを確定し、ＶＬＳＩ間のバスを少なくする。
【００１６】
本発明の並列コンピューティングシステムは、
ｋ番目の順序のＶＬＳＩ回路のｉ番目のＰＥをＰＥ（ｋ，ｉ）と表すとき、ＰＥ（ｋ１，ｉ１）からＰＥ（ｋ２，ｉ２）へのデータ転送が、
（１）ｋ１＝ｋ２であればｋ１番目のＶＬＳＩ回路内のＨＸＮｅｔによって実行され、
（２）ｋ１≠ｋ２かつｉ１＝ｉ２であればＰＥ（ｋ１，ｉ１）が所定の追加ＢＭにデータを書き込み、該データをＰＥ（ｋ２，ｉ１）が読取ることによって実行され、
（３）ｋ１≠ｋ２かつｉ１≠ｉ２であればＰＥ（ｋ１，ｉ１）が所定の追加ＢＭにデータを書き込み、該データをＰＥ（ｋ２，ｉ１）が読取り、ｋ２番目のＶＬＳＩ回路内のＨＸＮｅｔによりＰＥ（ｋ２，ｉ２）に転送されることによって実行される
ことを特徴とする。
【００１７】
具体的なデータ転送手順を与える。
【００１８】
本発明のコンピュータシステムは、
本体ＣＰＵと、上記の並列コンピューティングシステムと、前記本体ＣＰＵと前記並列コンピューティングシステムとのインタフェース回路とを備えることを特徴とする。
【００１９】
ＶＬＳＩによる並列コンピューティングシステムを、本体ＣＰＵから見て１つのデバイスとして取り扱うことを可能とする。
【００２０】
本発明のコンピュータシステムは、
前記並列コンピューティングシステムを用いてラジオシティの計算を行うことを特徴とする。
【００２１】
ラジオシティの計算においては、ＰＥ間のデータ転送が多い。本発明のコンピュータシステムが有効に活用される。
【００２２】
本発明のコンピュータシステムは、
携帯端末装置上で動作し、
ゲームのアプリケーションのおける画像表示にラジオシティの計算を行うことを特徴とする。
【００２３】
スケーラビリティを持った並列コンピューティングシステムであり、携帯端末装置での活用、特にゲームにおける活用が考えられる。
【発明の効果】
【００２４】
本発明によれば、任意のＰＥ間のデータ転送が可能でありスケーラビリティを持った並列コンピューティングシステム、及びかかる並列コンピューティングシステムを活用するコンピュータシステムが提供される。
【図面の簡単な説明】
【００２５】
【図１】図１は、ＶＬＳＩ回路を示す図である。
【図２】図２は、複数のＶＬＳＩ回路による並列コンピューティングシステムを示す図である。
【図３】図３は、コンピュータの構成を示す図である。
【図４】図４は、ラジオシティの計算手順を示す図である。
【発明を実施するための形態】
【００２６】
以下、本発明の実施例を、ｍ＝２、ｎ＝３の例で説明する。ｍ、ｎが他の値であっても同様に動作する。
【００２７】
図１は、ＶＬＳＩ回路を示す図である。ＶＬＳＩ回路１には、ＨＸＮｅｔ２及び８つの追加ＢＭ（ＡＢＭ）４が実装されている。ＨＸＮｅｔ２は、４つ（＝２２）のＰＥ３と８つ（＝２３）のＢＭを有している。ＶＬＳＩ回路１は、この他に８つのＡＢＭを含む。８つのＡＢＭは、４つのＰＥ（ｉ）のそれぞれから読み書き可能な２つずつのＡＢＭ（ｉ，ｊ）である（ｉ＝１，．．．４、ｊ＝１，２）。
【００２８】
８つのＡＢＭは、ｊ毎に（読み書きされるＰＲ毎（ｉ毎）でなく各ＰＭに係る順序毎（ｊ毎）に）、グループ化されてバスを有している。むろん、各々のＡＢＭ毎に別々のバスを有するのであるが、グループ毎に略同一方向へのバス（ＶＬＳＩ回路外への経路）を有している。
【００２９】
１つのＶＬＳＩ回路は、４ＰＥからなるＨＸＮｅｔを構成しており、それ自体が並列コンピューティングシステムとして動作する。本実施例では４ＰＥとしたが、９ＰＥ、１６ＰＥ、２５ＰＥ、その他任意の数のＰＥ（ただし、ｍを２以上の整数としてｍ２個のＰＥとする）であってよい。
【００３０】
図２は、複数のＶＬＳＩ回路による並列コンピューティングシステムを示す図である。本実施例では３つのＶＬＳＩ回路１による１２ＰＥ（４ＰＥ×３）の並列コンピューティングシステムを示すが、４以上のＶＬＳＩ回路１による並列コンピューティングシステムも同様に構築可能である。
【００３１】
３つのＶＬＳＩ回路１ａ、１ｂ及び１ｃがあり、ＶＬＳＩ回路１ａと１ｂとを結ぶバス５ａｂ、ＶＬＳＩ回路１ｂと１ｃとを結ぶバス５ｂｃ及びＶＬＳＩ回路１ｃと１ａとを結ぶバス５ｃａが備えられている。
【００３２】
バス５ａｂ、５ｂｃ及び５ｃａは、それぞれ４つのＡＢＭに係る４本のバスをまとめて示している。１本１本のバスは、以下のように接続されている。例えば、バス５ａｂのうち、ＶＬＳＩ回路１ａのＡＢＭ（１，２）からのバスは、ＶＬＳＩ回路１ｂのＡＢＭ（１，１）及び／又はＰＥ１に接続される。一方のＶＬＳＩ回路のＡＢＭ（ｉ１，ｊ１）から他方のＶＬＳＩ回路のＡＢＭ（ｉ２，ｊ２）又はＰＥｉ２を接続するにあたって、ｉ１＝ｉ２の関係を保つ。このようにして、同じ番号のＰＥ若しくはそれに係るＡＢＭを接続している。
【００３３】
ここで、バスで接続されたＡＢＭ間でデータを複写する（ＡＢＭ間でミラーリングする）か、接続先のＡＢＭを書き換えずにＰＥにデータを転送するかは、いずれでもよい。ＰＥにデータを転送することが目的であり、ＡＢＭを介するか否かは本質でない。
【００３４】
ここで、ｉ１＝ｉ２の関係を保つことが重要である。ＨＸＮｅｔにおいては、ＰＥの数がｍ２個であり、共に１〜ｍの値をとるｉ及びｊによってＰＥが番号付けされているため、ＰＥ（ｉ，ｊ）からＰＥ（ｊ、ｋ）に転送する際に、ｊの値にかかわらずＰＥ（ｊ、ｋ）が存在する。しかし、本発明においては、ＶＬＳＩ回路の数ｎがｍよりも小さい場合には、ｉ番目のＶＬＳＩのｊ番目のＰＥに対して、「ｊ番目のＶＬＳＩ」が存在しない可能性がある。ＰＥ（ｉ，ｊ）からＰＥ（ｊ、ｋ）への転送が保証されない。このため、ｉを各々のＶＬＳＩにおけるＰＥの順序として、転送先のＰＥが存在することを保証するものである。
【００３５】
以上により、ｍ２（ｎ−１）個の追加ＢＭを実装したＶＬＳＩ回路１を、最大ｎ個まで、スケーラビリティを持って任意の数を接続することができ、任意のＰＥ間のデータ転送を実現することができる。以下、任意のＰＥ間のデータ転送を説明する。ｋ番目の順序のＶＬＳＩ回路のｉ番目のＰＥをＰＥ（ｋ，ｉ）と表すとき、ＰＥ（ｋ１，ｉ１）からＰＥ（ｋ２，ｉ２）へのデータ転送は、以下の手順で行われる。
【００３６】
ｋ１＝ｋ２であればｋ１番目のＶＬＳＩ回路内のＨＸＮｅｔによって実行される。すなわち、同一のＶＬＳＩ内におけるＨＸＮｅｔによるデータ転送である。
【００３７】
ｋ１≠ｋ２かつｉ１＝ｉ２であればＰＥ（ｋ１，ｉ１）が所定の追加ＢＭにデータを書き込み、該データをＰＥ（ｋ２，ｉ１）が読取ることによって実行される。すなわち、ＶＬＳＩ内の順序が同一のＰＥ間は、ＡＢＭ及びバスを介したデータ転送が可能である。
【００３８】
ｋ１≠ｋ２かつｉ１≠ｉ２であればＰＥ（ｋ１，ｉ１）が所定の追加ＢＭにデータを書き込み、該データをＰＥ（ｋ２，ｉ１）が読取り、ｋ２番目のＶＬＳＩ回路内のＨＸＮｅｔによりＰＥ（ｋ２，ｉ２）に転送されることによって実行される。すなわち、ＡＢＭ及びバスを介したデータ転送を行った後に、転送先のＶＬＳＩ内のＨＸＮｅｔによるデータ転送を行う。
【００３９】
以上、ＶＬＳＩ回路及びその接続を説明した。次いで、並列コンピューティングシステムを実現するためのインタフェース回路について説明する。ただし、インタフェース回路は非特許文献１に開示されたものと同様であってよく、特段の説明をせずとも本発明の属する技術分野における通常の知識によって開発可能である。
【００４０】
図３は、コンピュータの構成を示す図である。コンピュータにはメインＣＰＵ６及び並列コンピューティング用のＶＬＳＩ回路１が備えられ、これらはインタフェース回路７によって結ばれている。ここで、ＶＬＳＩ回路１は、１つのＶＬＳＩであっても、上述のように複数のＶＬＳＩを結合したものであってもよい。
【００４１】
インタフェース回路７は、データストレージと同様に、メインＣＰＵ６にとっては１つの入出力デバイスとして取り扱うことができる。何らかのデータを与え、何らかのデータを受け取るものだからである。
【００４２】
インタフェース回路７は、メインＣＰＵ６からデータ（プログラムの指示を含む）を受け取り、ＶＬＳＩ回路１に並列コンピューティングを行わせ、その計算結果をメインＣＰＵ６に返す。このためには、データをストアするＩＦ−メモリと、ＶＬＳＩ回路１の動作を制御するＩＦ−ＣＰＵとを備えている。メインＣＰＵ６から受け取るプログラムの指示に従って、ＶＬＳＩ回路１の各々のＰＥにデータを与え、計算を指示する。
【００４３】
以上、並列コンピューティングを行うことのできるコンピュータを説明した。次いで、かかるコンピュータによって実行させるラジオシティの計算について説明する。
【００４４】
ラジオシティの計算は、画像を求める計算であり、従来のレイトレーシング（光路追跡）と異なり、個々の光線を追跡せずに物体の表面を表す小平面における反射を他の小平面との関係で計算することが特徴である。
【００４５】
ｘ番目の小平面の反射率をＲｘ、ｘ番目の小平面とｙ番目の小平面との角関係（ｘ番目の小平面で反射された光がｙ番目の小平面に到達する割合）をＦｘｙ、ｘ番目の小平面から放射される光エネルギーをＢｘ、初期の放射光エネルギーをＥｘとするとき、以下の式が成立する。なお、Ｒｘ及びＦｘｙが色相によって相違するとして色相ごとに計算してもよい。
【数１】
0005610603.tif 000002
ここで、Ｒｘは物体表面の材質によって定まる定数であり、Ｅｘは初期の放射光（光源）によって定まる定数である。Ｆｘｙ及びＢｘを計算することがラジオシティの計算の中心となる。
【００４６】
図４は、ラジオシティの計算手順を示す図である。先にＦｘｙを求め、その後にＢｘを求める。ここで、Ｆｘｙを求めるステップ８ａ及びＢｘ求めるステップ８ｂに、並列化計算が有効である。
【００４７】
Ｆｘｙは、ｘ番目の小平面とｙ番目の小平面との角関係によるので、ｘ番目の小平面とｙ番目の小平面に関する情報のみに基づいて計算できる。すなわち、小平面の数をｐとするときｐ（ｐ−１）／２個のＦｘｙの値を計算するが、それぞれを独立に並列計算できる。ｍ２ｎ個のＰＥを備えた並列コンピューティングシステムによれば、計算時間が（１／ｍ２ｎ）になることが期待される。
【００４８】
Ｂｘの計算は、上記数１に基づいて（右辺の計算結果を左辺に代入して）逐次計算する方法と、上記数１を線形連立方程式として逆行列計算によって解く方法とがある。
【００４９】
逐次計算の場合には、各々のｘに対するＢｘを他のｘに対するものとは独立に計算できる。並列化計算が有効である。
【００５０】
逆行列計算の場合には、非特許文献１に記載された方法によって、並列化計算を有効に活用できる。ここで、Ｆｘｙの値は多くが非ゼロであり、逆行列計算の対象となる行列が密であるため、並列化計算の効果が大きい。
【００５１】
以上のとおり、ｍ２個のＰＥを持つＨＸＮｅｔのＶＬＳＩ回路１を任意の数だけ用いることのできる、スケーラビリティを持った並列コンピューティングシステムが実現された。また、この並列コンピューティングシステムを活用したコンピュータシステム及びそのコンピュータシステムにおいて実行されるラジオシティの計算を示した。携帯端末等における並列コンピューティングシステムの活用を実現したものである。
【００５２】
本発明の並列コンピューティングシステムは、スケーラビリティを有するので、小型の携帯端末装置に用いることも（この場合にはｍの小さなＶＬＳＩ回路を用いる。）、大型の計算機に用いることも（この場合にはｍ、ｎの大きなＶＬＳＩ回路を用いる。）、ゲーム機その他の機器に用いることもできるものである。
【産業上の利用可能性】
【００５３】
任意のＰＥ間のデータ転送が可能でありスケーラビリティを持った並列コンピューティングシステム、及びかかる並列コンピューティングシステムを活用するコンピュータシステムである。多くの携帯端末製造業者、コンピュータメーカによる利用が期待される。
【００５４】
また、ラジオシティの計算を携帯端末等においても実現するものであり、多くのソフトウェア開発業者による利用も期待される。
【符号の説明】
【００５５】
１…ＶＬＳＩ回路
２…ＨＸＮｅｔ
３…ＰＥ
４…追加ＢＭ
５…バス
６…メインＣＰＵ
７…インタフェース回路
８…並列化ステップ 
【要約】
【課題】任意のＰＥ間のデータ転送が可能であり、スケーラビリティを持った並列コンピューティングシステムを提供すること。また、かかる並列コンピューティングシステムを活用するコンピュータシステムを提供し、小型の携帯端末装置上でラジオシティの計算を可能とすること。
【解決手段】ＨＸＮｅｔをＶＬＳＩに実装し、追加ＢＭによってＶＬＳＩ間のデータ転送を可能とする。ＶＬＳＩ数を任意に選択できるスケーラビリティが実現され、小型の携帯端末装置上でラジオシティの計算が可能となる。
【選択図】図２【図１】
0005610603.tif 000003
【図２】
0005610603.tif 000004
【図３】
0005610603.tif 000005
【図４】
0005610603.tif 000006