(57)【要約】少なくともｎ個の並列処理要素を備えているマイクロプロセッサにて、算術又は論理演算の、少なくとも第１及び第２ツリーを計算する方法。この方法は、：ａ）ｎ個の処理要素を用いて、第１ツリーの第１イテレーションの算術又は論理演算をｎ回並列に実行し（４８において）、次いで、ｂ）第１イテレーションの計算に用いたｎ個の処理要素から選定したｍ個の処理要素を用い、他のｎ−ｍ個の処理要素は第２イテレーションの計算には使用しないで、第１イテレーションの結果間でｍ回の算術又は論理演算を並列に実行する（６６において）ステップを含む。本発明による方法は、第１ツリーの第２イテレーションの計算と並列に、第２ツリーのｋ算術又は論理演算を、第１ツリーの第２イテレーションの計算には使用されなかったｎ−ｍ個の処理要素から選定したｋ個の処理要素を用いて、並列に実行する（６６において）ステップを含む。
2008524691.tif 000002
【特許請求の範囲】
【請求項１】
ｎ回の算術又は論理演算を並列に実行する、少なくともｎ個の並列処理要素を備えていいるマイクロプロセッサにて、算術又は論理演算の、少なくとも第１及び第２ツリーを計算する方法であって、各ツリーの計算が複数の連続イテレーションを必要とし、各イテレーションの結果を、次のイテレーションの計算中に使用し、ここに、ｎは４よりも大きな正の整数とし、当該方法が：
ａ）前記ｎ個の処理要素を用いて、前記第１ツリーの第１イテレーションの算術又は論理演算を（４８にて）ｎ回並列に実行し、次いで、
ｂ）前記第１イテレーションの計算に使用したｎ個の処理要素から選定したｍ個の処理要素を用い、他のｎ−ｍ個の処理要素は、第２イテレーションの計算には使用しないで、ここに、ｍはｎよりも確実に小さい整数として、第１イテレーションの結果間で算術又は論理演算を（６６にて）ｍ回並列に実行する、
ステップを含む、算術／論理演算ツリーの計算方法において、
ｋはｎ−ｍよりも小さいか、又はそれに等しい整数として、第１ツリーの第２イテレーションの計算と並列に、第１ツリーの第２イテレーションの計算には使用されなかったｎ−ｍ個の処理要素から選定したｋ個の処理要素を用いて、第２ツリーの算術又は論理演算をｋ回並列に実行するステップを含むようにする、ことを特徴とする算術／論理演算ツリーの計算方法。
【請求項２】
前記第１ツリーの第２イテレーションの計算に先立つ処理要素間のデータ転送と、前記第２ツリーのｋ回の算術又は論理演算の実行に先立つ処理要素間のデータ転送とを、並列に実行する、請求項１に記載の方法。
【請求項３】
前記第２ツリーの計算に用いる各処理要素を、前記第１ツリーの第２イテレーションの計算に用いる２つの処理要素間にインターリーブさせる、請求項１又は２に記載の方法。
【請求項４】
前記マイクロプロセッサは、ｐ回の同じ算術又は論理演算を並列に実行するｐ個の同一処理要素を備え、これら処理要素は共通のダイ上に製造され、ｐはｎより大きいか若しくは等しい整数とする、ＳＩＭＤマイクロプロセッサとする、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
少なくとも第１及び第２のバイナリーツリーの和を計算するステップを有している、通信デバイスにおける逆拡散法であって、前記請求項１〜４のいずれか一項に記載の計算方法を用いて、ｎ回の算術又は論理演算を並列に計算する、少なくともｎ個の並列処理要素を備えているマイクロプロセッサにて、前記少なくとも第１及び第２のバイナリーツリーの和を計算する、電気通信デバイスにおける逆拡散法。
【請求項６】
請求項１〜４のいずれか一項に記載の算術又は論理演算の、第１及び第２ツリーを計算する方法を実行するための命令を含むメモリであって、これらの命令を、少なくともｎ個の並列処理要素を備えているマイクロプロセッサにて実行させる際に、ｎは４よりも大きな正の整数とする、メモリ。
【請求項７】
請求項１〜４のいずれか一項に記載の算術又は論理演算の、少なくとも第１及び第２ツリーを計算する方法を実行するための命令を含む、マイクロプロセッサのプログラムであって、これらの命令を、少なくともｎ個の並列処理要素を備えているマイクロプロセッサにて実行させる際に、ｎは４よりも大きな正の整数とする、マイクロプロセッサのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算術又は論理演算ツリーの計算方法に関する。
【背景技術】
【０００２】
算術又は論理演算のツリーは、ツリー構造に従って編成した算術又は論理演算から成る。このツリー構造は複数のノードを含み、各ノードは少なくとも２つの入力端と１つの出力端とを有する。各ノードは、その入力端で受け取ったデータ間の算術又は論理演算に対応し、算術又は論理演算の結果をその出力端に出力する。
【０００３】
ツリー構造は、リーフノードから成る第１レベルと、各々が先行する同じレベルのノードの出力端に直接接続された入力端を有している複数のノードから成る幾つかの中間レベルと、ルートノードを有するルートレベルとの、連続レベルに分けることができる。
【０００４】
このような演算ツリーの計算は、複数回のイテレーションを必要とする。イテレーションの間に、同じレベルのノードに対応する全ての演算が実行される。
【０００５】
典型的に、少なくともｎ個の並列処理要素を備えているマイクロプロセッサにて、算術又は論理演算の少なくとも第１及び第２ツリーを計算する方法は、
ａ）ｎ個の処理要素を用いて、第１ツリーの第１イテレーションの算術又は論理演算をｎ回並列に実行し、次いで、
ｂ）第１イテレーションの計算に使用したｎ個の処理要素から選定したｍ個の処理要素を用い、他のｎ−ｍ個の処理要素は第２イテレーションの計算には使用しないで、ここに、ｍはｎよりも確実に小さい整数として、第１イテレーションの結果間で算術又は論理演算をｍ回並列に実行する、
ステップを備えている。
【０００６】
第１の演算ツリーを一旦計算したら、第２演算ツリーを同じように処理すべく、処理要素は構成されている。
【０００７】
並列処理要素を有するマイクロプロセッサを用いるこのようなやり方は、第１演算ツリーの第２イテレーションの計算中に、一部の処理要素が使用されないままとなるから、非効率的である。
【０００８】
ｎ個の並列処理要素を備えているマイクロプロセッサの例は、Ａｎｄｒｅｗ  ＰａｕｌＷａｌｌａｃｅによるＵＳ２００３／００８８６０３に開示されている。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従って、本発明の目的は、複数の並列処理要素を有しているマイクロプロセッサをもっと有効的に用いて、少なくとも第１及び第２の演算ツリーを計算する方法を提供することにある。
【課題を解決するための手段】
【００１０】
本発明は、斯様なマイクロプロセッサで少なくとも第１及び第２の演算ツリーを計算する方法において、当該方法が、ｋはｎ−ｍよりも小さいか、又はそれに等しい整数として、第１ツリーの第２イテレーションの計算と並列に、第１ツリーの第２イテレーションの計算には使用されなかったｎ−ｍ個の処理要素から選定したｋ個の処理要素を用いて、第２ツリーの算術又は論理演算をｋ回並列に実行するステップを含むようにする、演算ツリーの計算方法を提供する。
【００１１】
上記方法においては、第１演算ツリーの或るイテレーションに対して使用されないｎ−ｍ個の処理要素を使用して、第２演算ツリーの算術又は論理演算を並列に計算する。従って、並列に使用される処理要素の数と、並列に実行される演算の回数が増えるために、複数の並列処理要素を備えているマイクロプロセッサの使用効率が向上する。
【００１２】
請求項２の特徴事項は、ｍ個の処理要素間にデータを転送するのに必要な時間中に、ｋ個の処理要素間にもデータを並列に転送するために、処理時間量を低減させることにある。
【００１３】
請求項３の特徴事項は、処理要素間のデータ転送時間を低減させることにある。
【００１４】
本発明はまた、上記方法を実行するための命令を有する、メモリ及びマイクロプロセッサのプログラムにも関する。
【００１５】
本発明はまた、同一の算術又は論理演算の少なくとも第１及び第２ツリーを計算するために上記方法を使用する、通信デバイスにおける逆拡散法（ｄｅ−ｓｐｒｅａｄｉｎｇ  ｍｅｔｈｏｄ）にも関する。
【発明を実施するための最良の形態】
【００１６】
図１は、演算ツリー２の一例を示す。例えば、図１において、それぞれのノードは、各列が演算ツリーのレベルに対応する平行な垂直方向の列にて編成されている。図１の最も左の列は、全てのリーフノードＬＦｉを含み、図１の最も右の列は、ルートノードＲＮだけを含んでいる。
【００１７】
各リーフノードＬＦｉは、処理すべきデータを受け取る２つの入力端を有している。２つのリーフノードＬＦｉの出力端は、次列のノードの入力端に接続されている。この次列のノードの出力端は、同様に、その次列の入力端に接続されている。一つの列のノードを次の列のノードに接続するというこの方法は、ルートノードＲＮを有するルート列に達するまで、繰り返される。
【００１８】
ここで、演算ツリー２はバイナリーツリー（二分木）の和であり、各ノードは、入力された２つのデータの加算に対応する。例えば、演算ツリー２は、ＣＤＭＡ（符号分割多重アクセス）通信システムにおける拡散信号の、各チップのチップ値のような、極めて多数のデータ加算を計算するのに用いられる。
【００１９】
演算ツリー２の計算には、複数のイテレーションＩＴｉが必要である。第１イテレーションＩＴ１中には、リーフノードＬＦｉの算術又は論理演算を実行する。そして、次のイテレーションＩＴ２中には、左から第２列のノードに対応する演算を実行する。このような演算処理は、ルートノードＲＮに対応する演算が実行されるまで、繰り返す。
【００２０】
例えば、演算ツリー２に入力されるデータの数ｎが２５６に等しい場合に、演算ツリー２は、８回のイテレーションで計算される。ＩＴ１からＩＴ８までのイテレーション中に実行される加算回数は、それぞれ、１２８、６４、３２、１６、８、４、２及び１回である。
【００２１】
図２は、演算ツリー２を計算するのに用いる、ＳＩＭＤ（Single Instructions Multiple Data）マイクロプロセッサ２０を示している。ＳＩＭＤマイクロプロセッサは特に、多数のデータに同じ処理を同時に実行するのに適している。
【００２２】
簡単化のために、図２には、本発明を理解するのに必要な細部のみを示してある。
【００２３】
マイクロプロセッサ２０は、ｐ個の多数の並列処理要素ＰＥｉを備えている。例えば、ｐは４０８６に等しく、インデックスｉは１から４０８６までの範囲の整数とする。全ての並列処理要素ＰＥｉは、異なるデータ組を、同じプログラムで並列に実行するように設計されている。従って、各処理要素は、算術又は論理演算を実行するためのＡＬＵ（算術兼論理ユニット）と、このＡＬＵによって処理すべきデータ及びこの処理結果を格納するためのデータレジスタＤＲｉとを有している。例えばデータレジスタＤＲｉは、１９２ビットまで格納することができる。
【００２４】
図２には、ＰＥ１、ＰＥ２、ＰＥｉ、ＰＥｐ−ｉ、ＰＥｐの５つの処理要素のみを示してある。
【００２５】
マイクロプロセッサ２０の処理要素は、相互接続ネットワーク２４によって互いに接続されて、１つのデータレジスタＤＲｉに格納されているデータを、他の処理要素ＰＥｊにおける他のデータレジスタＤＲｊへ転送し得るようになっている。各データレジスタＤＲｉは、データの転送中に使用されるネットワーク２４上のアドレスを有している。
【００２６】
それぞれの処理要素ＰＥｉは、同じシリコンのダイまたは基板上に製造される。
【００２７】
マイクロプロセッサ２０は、全ての処理要素に同じプログラムが適用され、また、全ての処理要素が同時に同じ命令を実行するので、使いやすい。そのプログラムは、マイクロプロセッサ２０に接続したメモリ２６に格納されている。
【００２８】
メモリ２６は、マイクロプロセッサ２０が図２の方法を実行するための命令を実行する際に、これらの命令を含んでいる。
【００２９】
マイクロプロセッサ２０で演算ツリー２のような少なくとも２つの演算ツリーを計算する方法を、図３〜図６を参照して、８つの同一のバイナリーツリーの和Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈを並列に処理するという特別な場合につき説明する。例えば、以下に述べる方法は、通信デバイスにおいて実施される逆拡散法の一部である。
【００３０】
各バイナリーツリーの和Ａ〜Ｈは２５６のデータ入力を有し、各データは、論理０か論理１を表す２進数である。
【００３１】
さらに、図３の方法を、マイクロプロセッサ２０における最初の２５６個の処理要素ＰＥｉだけを用いて、Ａ〜Ｈの、８つのバイナリーツリーの和を計算する、特定の場合について説明する。
【００３２】
先ず、ステップ４０では、各バイナリーツリーの和の各入力データを、マイクロプロセッサ２０のデータレジスタＤＲｉの１つに格納する。例えば、バイナリーツリーの和Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈの、入力データＡｉ、Ｂｉ、Ｃｉ、Ｄｉ、Ｅｉ、Ｆｉ、Ｇｉ及びＨｉは、それぞれ、データレジスタＤＲｉに格納する。その結果、データＡ１、Ｂ１、Ｃ１、Ｄ１、Ｅ１、Ｆ１、Ｇ１及びＨ１が、第１の処理要素ＰＥ１のデータレジスタＤＲ１に格納され、また、データＡ２５６、Ｂ２５６、…及びＨ２５６が、バイナリーツリーの和Ａ〜Ｈを計算するのに使用される、最後の処理要素ＰＥ２５６のデータレジスタＤＲ２５６に格納される。
【００３３】
その後、フェーズ４２において、各バイナリーツリーの和の第１イテレーションを計算する。
【００３４】
より正確に云えば、ステップ４４では、プロセッサ２０が、処理要素ＰＥ１〜ＰＥ２５６を用いて、バイナリーツリーの和Ａ及びＢの第１イテレーションを並列に計算する。
【００３５】
ステップ４４の間に、マイクロプロセッサ２０は、データＡ２ｊをデータレジスタＤＲ２（ｊ−１）＋１へ、また、データＢ２（ｊ−１）＋１をデータレジスタＤＲ２ｊへ転送し、ここに、インデックスｊは、１〜１２８までの範囲の整数である。これらの転送動作は、僅か２つの命令、即ち、全てのデータＡ２ｊを移すための命令と、全てのデータＢ２（ｊ−１）＋１を移すための命令、との２つの命令のみを用いて実行される。
【００３６】
データＡｉとＢｉは、両方ともデータレジスタＤＲｉに記録されるために、僅か２つの転送命令を必要とするだけである。
【００３７】
図４Ａは、データレジスタＤＲ１〜ＤＲ８間で行われるデータ転送を図解している。図４Ａ並びに図４Ｂ−４Ｄ及び図５Ａ−５Ｄと図６では、マイクロプロセッサ２０の要素に、図２におけるのと同じ参照符号を付してある。
【００３８】
実行すべき算術又は論理演算、即ち、加算を各記号ＡＬＵｉ内に示してある。ＡＬＵｉに対応するデータレジスタＤＲｉに格納される関連データを、ＡＬＵｉの左及び右側に示してある。データレジスタＤＲｉのデータからＡＬＵｋへの垂直部分を有する矢印は、ＡＬＵｋを用いて算術又は論理演算を実行する前に、このデータをどのように移動させるべきかを示している。例えば図４Ａにおいて、データＢ１は、垂直部分を有する矢印によってＡＬＵ２に結ばれている。このことは、ＡＬＵ２を用いる加算を実行する前に、データＢ１を、データレジスタＤＲ２へ転送しなければならないことを意味している。図４Ａにおいて、データＡ１からＡＬＵ１への水平方向の矢印は、データＡ１がデータレジスタＤＲ１に既に格納されていることを示している。
【００３９】
演算４８の間に、ひとたびデータが転送されると、処理要素ＰＥ２（ｊ−１）＋１は、データＡ２（ｊ−１）＋１とＡ２ｊとの加算を実行して、その結果ＡＡ２（ｊ−１）＋１をデータレジスタＤＲ２（ｊ−１）＋１に格納する。
【００４０】
演算４８の間には、これと並列に、処理要素ＰＥ２ｊが、データＢ２ｊとＢ２（ｊ−１）＋１の加算を実行し、その結果ＢＢ２ｊを、データレジスタＤＲ２ｊに格納する。
【００４１】
従って、演算４８の間に、２５６個の処理要素ＰＥｉの全てが、同時に使用される。
【００４２】
次に、ステップ５０、５２、５４において、バイナリーツリーの和ＣとＤ、バイナリーツリーの和ＥとＦ、バイナリーツリーの和ＧとＨ、の第１イテレーションを、それぞれ計算する。各ステップ５０、５２及び５４の各ステップは、ＡとＢの文字を、それぞれ、
−ステップ５０ではＣとＤに、
−ステップ５２ではＥとＦに、
−ステップ５４ではＧとＨに、
置き換える以外は、ステップ４４と同じである。
【００４３】
その後、フェーズ６０において、各バイナリーツリーの和Ａ〜Ｈの、第２イテレーションを計算する。
【００４４】
ステップ６２では、バイナリーツリーの和Ａ〜Ｄの第２イテレーションを並列に計算する。より正確に云えば、演算６４の間に、次のデータを転送する。即ち、
−結果ＡＡ２ｊ＋１をデータレジスタＤＲ２（ｊ−１）＋１に転送し、
−結果ＢＢ２（ｊ＋１）をデータレジスタＤＲ２ｊに転送し、
−結果ＣＣ２（ｊ−１）＋１をデータレジスタＤＲ２ｊ＋１に転送し、且つ
−結果ＤＤ２ｊをデータレジスタＤＲ２（ｊ＋１）に転送する。
【００４５】
これらのデータ転送を、図５Ａに下向きの矢印によって示してある。
【００４６】
そして、演算６６の間に、各処理要素ＰＥｉにて次の加算を並列に実行する。即ち、
−処理要素ＰＥ２（ｊ−１）＋１は、結果ＡＡ２（ｊ−１）＋１を結果ＡＡ２ｊ＋１に加えて、その結果ＡＡＡ２（ｊ−１）＋１をデータレジスタＤＲ２（ｊ−１）＋１に格納し、
−処理要素ＰＥ２ｊは、結果ＢＢ２（ｊ＋１）を結果ＢＢ２ｊに加えて、その結果ＢＢＢ２ｊをデータレジスタＤＲ２ｊに格納し、
−処理要素ＰＥ２ｊ＋１は、結果ＣＣ２（ｊ−１）＋１を結果ＣＣ２ｊ＋１に加えて、その結果ＣＣＣ２ｊ＋１をデータレジスタＤＲ２（ｊ＋１）に格納し、
−処理要素ＰＥ２（ｊ＋１）は、結果ＤＤ２ｊを結果ＤＤ２（ｊ＋１）に加えて、その結果ＤＤＤ２（ｊ＋１）をデータレジスタＤＲ２（ｊ＋１）に格納する。
【００４７】
その後ステップ６８において、バイナリーツリーの和Ｅ、Ｆ、Ｇ及びＨの第２イテレーションを並列に計算する。ステップ６８は、Ａ、Ｂ、Ｃ、Ｄの文字を、それぞれ、Ｅ、Ｆ、Ｇ、Ｈに置き換えること以外は、ステップ６２と同じである。ステップ６８で行うデータ転送を、図５Ｂに下向きの矢印によって示してある。
【００４８】
ステップ６２及びステップ６８では、２５６個の処理要素ＰＥｉが並列に使用される。
【００４９】
次に、ステップ７０で、バイナリーツリーの和Ａ〜Ｈの第３イテレーションを並列に計算する。先ず、演算７２の間に、第２イテレーションの結果のデータ転送を行い、次いで、演算７４の間に、バイナリーツリーの和の第３イテレーションの加算を実行する。
【００５０】
演算７２の間に、第２イテレーションの結果は、次のように転送される。即ち、
−結果ＡＡＡ２（ｊ＋１）＋１はデータレジスタＤＲ２（ｊ−１）＋１に転送され、
−結果ＢＢＢ２（ｊ＋２）はデータレジスタＤＲ２ｊに転送され、
−結果ＣＣＣ２（ｊ＋２）＋１はデータレジスタＤＲ２ｊ＋１に転送され、
−結果ＤＤＤ２（ｊ＋３）はデータレジスタＤＲ２（ｊ＋１）に転送され、
−結果ＥＥＥ２（ｊ−１）＋１はデータレジスタＤＲ２（ｊ＋１）＋１に転送され、
−結果ＦＦＦ２ｊはデータレジスタＤＲ２（ｊ＋２）に転送され、
−結果ＧＧＧ２ｊ＋１はデータレジスタＤＲ２（ｊ＋２）＋１に転送され、
−結果ＨＨＨ２（ｊ＋１）はデータレジスタＤＲ２（ｊ＋３）に転送される。
【００５１】
演算７４の間には、以下の加算を並列に実行する。即ち、
−処理要素ＰＥ２（ｊ−１）＋１が、結果ＡＡＡ２（ｊ＋１）＋１を結果ＡＡＡ２（ｊ−１）＋１に加え、その結果ＡＡＡＡ２（ｊ−１）＋１をデータレジスタＤＲ２（ｊ−１）＋１に格納し、
−処理要素ＰＥ２ｊが、結果ＢＢＢ２（ｊ＋２）を結果ＢＢＢ２ｊに加え、その結果ＢＢＢＢ２ｊをデータレジスタＤＲ２ｊに格納し、
−処理要素ＰＥ２ｊ＋１が、結果ＣＣＣ２（ｊ＋２）＋１を結果ＣＣＣ２ｊ＋１に加え、その結果ＣＣＣＣ２ｊ＋１をデータレジスタＤＲ２ｊ＋１に格納し、
−処理要素ＰＥ２（ｊ＋１）が、結果ＤＤＤ２（ｊ＋３）を結果ＤＤＤ２（ｊ＋１）に加え、その結果ＤＤＤＤ２（ｊ＋１）をデータレジスタＤＲ２（ｊ＋１）に格納し、
−処理要素ＰＥ２（ｊ＋１）＋１が、結果ＥＥＥ２（ｊ−１）＋１を結果ＥＥＥ２（ｊ＋１）＋１に加え、その結果ＥＥＥＥ２（ｊ＋１）＋１をデータレジスタＤＲ２（ｊ＋１）＋１に格納し、
−処理要素ＰＥ２（ｊ＋２）が、結果ＦＦＦ２ｊを結果ＦＦＦ２（ｊ＋２）に加え、その結果ＦＦＦＦ２（ｊ＋２）をデータレジスタＤＲ２（ｊ＋２）に格納し、
−処理要素ＰＥ２（ｊ＋２）＋１が、結果ＧＧＧ２ｊ＋１を結果ＧＧＧ２（ｊ＋２）＋１に加え、その結果ＧＧＧＧ２（ｊ＋２）＋１をデータレジスタＤＲ２（ｊ＋２）＋１に格納し、
−処理要素ＰＥ２（ｊ＋３）が、結果ＨＨＨ２（ｊ＋１）を結果ＨＨＨ２（ｊ＋３）に加え、その結果ＨＨＨＨ２（ｊ＋３）をデータレジスタＤＲ２（ｊ＋３）に格納する。
【００５２】
従って、演算７４の間には、２５６の全ての処理要素ＰＥｉが同時に使用される。
【００５３】
演算７２の間に行うこれらのデータ転送を、図６に下向きの矢印によって示してある。
【００５４】
ステップ８０では、各バイナリーツリーの和Ａ〜Ｈの次のイテレーションを、並列に計算する。この段階における処理要素の数２５６は、実行するべき並列加算の数よりも大きい。従って、各バイナリーツリーの和の第４〜第８イテレーションの計算については、詳細に述べる必要はないものと思料する。実際上、８つのバイナリーツリーの和Ａ〜Ｈの第４イテレーションを並列に計算するためには、８つのバイナリーツリーの和を計算するために最初に割り当てられた２５６個の処理要素よりも少ない、１２８個の処理要素ＰＥｉを必要とするだけである。
【００５５】
図３の方法では、バイナリーツリーの和Ａの第１イテレーションを計算するために最初に割り当てられた幾つかの処理要素ＰＥｉは、バイナリーツリーの和の第２及び第３イテレーションを計算している間に、別のバイナリーツリーの和のイテレーションを並列に計算するために使用される。例えば、処理要素ＰＥ３は、バイナリーツリーの和Ａの第１イテレーションを計算するために使用され、そして、バイナリーツリーの和Ａの第２イテレーションを計算している間に、バイナリーツリーの和Ｃの第２イテレーションを計算するために使用される。処理要素ＰＥ３はまた、バイナリーツリーの和Ａの第３イテレーションを計算している間に、バイナリーツリーの和Ｃの第３イテレーションを計算するためにも使用される。
【００５６】
従って、ここで述べた特定の実施態様では、処理要素ＰＥ１〜ＰＥ２５６の全てが、フェーズ４２、フェーズ６０、そしてステップ７０の間に完全に使用される。従って、８つのバイナリーツリーの和の計算は、異なる演算ツリーからの演算を混合又はインターリーブするために、高速になる。
【００５７】
第１及び第２演算ツリー、例えばバイナリーツリーの和Ａ及びＢを計算するために使用する処理要素は、インターリーブされる。これは、最初の処理要素ＰＥ１と最後の処理要素ＰＥ２５６を除いて、第１ツリーの計算のために使用する各々の処理要素が、第２ツリーの計算のために使用する２つの処理要素の間に位置付けられることを意味する。このような機構により、データ転送の振幅が低減し、処理速度が速くなる。
【００５８】
多くの追加の実施態様が可能である。例えば、本発明による方法は複数のバイナリーツリーの和を並列に計算することに限定されず、各ノードを、１つの命令に答えてＡＬＵによって実行させることのできる算術又は論理演算とする、もっと一般的な演算ツリーにも適用することができる。例えば、各ノードは、Ｘ−ＯＲ（排他的論理和演算）または減算を計算するように設計することもできる。
【００５９】
ＳＩＭＤマイクロプロセッサは、１つの命令で複数のデータを並列に実行するためにだけ設計されている。従って上記の方法は、ＳＩＭＤマイクロプロセッサで実行させる際に、複数の同一演算ツリーを並列に計算するためだけに用いることができる。しかしながら、このような制約は、本発明による方法をＭＩＭＤ（Multiple Instruction Multiple Data）マイクロプロセッサで実施する場合には存在しない。従って、ＭＩＭＤマイクロプロセッサで実施する場合には、本発明による方法は、異なる演算ツリーを並列に計算するために用いることができる。例えば、バイナリーツリーの和及びバイナリーツリーの減算は、同時に計算することができる。
【００６０】
上記の方法は、２つの入力端を有するノードを備えたバイナリーツリーに限定されるものでなく、例えば、２つ以上の入力端を有するノードを備えた演算ツリーにも適用することができる。
【図面の簡単な説明】
【００６１】
【図１】模範的な演算ツリーの概略図である。
【図２】図１の演算ツリーを計算するのに用いられるＳＩＭＤ(単一命令／複数データ)マイクロプロセッサの概略図である。
【図３】図２のマイクロプロセッサを用いて、図１の演算ツリーのような８つの演算ツリーを並列に計算する方法のフローチャートである。
【図４】図３の方法の計算ステップの説明図である。
【図５】図３の方法の他の計算ステップの説明図である。
【図６】図３の方法のさらに他の計算ステップの説明図である。
【図１】
2008524691.tif 000003
【図２】
2008524691.tif 000004
【図３】
2008524691.tif 000005
【図４Ａ】
2008524691.tif 000006
【図４Ｂ】
2008524691.tif 000007
【図４Ｃ】
2008524691.tif 000008
【図４Ｄ】
2008524691.tif 000009
【図５Ａ】
2008524691.tif 000010
【図５Ｂ】
2008524691.tif 000011
【図６】
2008524691.tif 000012
【国際調査報告】
2008524691.tif 000013
2008524691.tif 000014
2008524691.tif 000015