JPH04247554A - マルチプロセッサにおけるデータの再割り付け方法とその制御機構 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 【０００１】 【産業上の利用分野】本発明は複数の処理ユニットから
なるマルチプロセッサにおけるデータの再割り付け方法
とその制御機構に係り、特に処理ユニット間のデータの
授受により各処理ユニットに格納されているデータを再
配置するマルチプロセッサにおけるデータの再割り付け
方法とその制御機構に関する。 【０００２】 【従来の技術】多種類の並列処理を行うマルチプロセッ
サでは、ある処理の処理結果をデータとして用いて他の
処理を実行する場合、各処理ユニットで得られた処理結
果を他の並列処理の実行に適するように各処理ユニット
に割り付け直す必要がある。このようにデータを処理ユ
ニットに割り付け直すことをデータの再配置という。 【０００３】従来、このようなマルチプロセッサにおけ
るデータの再配置処理には主として次に述べる２種類の
方法があった。１つの方法はマルチプロセッサを管理す
るホストプロセッサに各処理ユニットにある全てのデー
タを集める。集められたデータはホストプロセッサ上で
データの並び換えられ、各処理ユニットに再格納される
。 【０００４】もう一つの方法はホストプロセッサを介さ
ずに、処理ユニット間のデータ転送パスを使用し、各処
理ユニットのデータを１つずつ再配置するものである。 【０００５】 【発明が解決しようとする課題】しかるに、上記のホス
トプロセッサ上でデータを並び換えて再格納する方法は
、各処理ユニットとホストプロセッサとの間で大量のデ
ータ授受を必要とし、さらに、ホストプロセッサに対す
るデータの並び換え処理の付加が大きくなるという問題
がある。一方、データ転送パスを使用する方法は再配置
の対象になるデータ量に比例してデータ転送時間がかか
り、マルチプロセッサの処理に対するオーバヘッドが大
きくなるばかりでなく、各処理ユニットに対する再配置
のためのデータ転送処理を個々に管理しなければならな
いために制御が複雑になるという問題がある。 【０００６】本発明は上記の点に鑑みなされたもので、
マルチプロセッサ上でデータの再割り付けの処理を効率
的に高速に実行することができるデータの再割り付け方
法とその制御機構を提供することを目的とする。 【０００７】 【課題を解決するための手段】図１は本発明の原理説明
図である。複数の処理要素を環状に接続したマルチプロ
セッサにおいて、複数の処理要素は各々データ授受を行
うためのデータ転送パスを介して処理要素と接続され、
複数の処理要素は所望の演算を行う演算手段、処理要素
間のデータを転送するデータ転送手段、アドレス及びデ
ータを記憶する記憶手段及び、記憶したデータを読み出
す読み出し手段に対して制御を行う制御手段を有し、複
数の処理要素に対して処理要素がマルチプロセッサに配
列されている順番に番号が付与され、全ての処理要素に
おいて、記憶手段の第１のアドレスから読み出し手段に
よりデータを読み出し（１０）、読み出したデータを処
理要素間で所定の回数転送し（１１）、各処理要素に転
送されてきた記憶手段の第１のアドレスのデータを第２
のアドレスのデータと交換して記憶手段に格納し（１３
）、変換された記憶手段の第２のアドレスのデータは処
理要素間で同時に所定回数転送し（１４）、個々の処理
要素に転送された記憶手段の第２のアドレスのデータを
記憶手段の第１のアドレスに格納する手続きを処理要素
の総数が奇数の場合は処理要素の総数（Ｎ）を２で割っ
た値（Ｎ／２）分実行し、処理要素の総数が偶数の場合
には処理要素の総数（Ｎ）を２で割った値（Ｎ／２）よ
り１を減した値（Ｎ／２−１）分実行し、処理要素の総
数が偶数且つ処理要素の総数を２で割った値（Ｎ／２）
とデータ転送を繰り返すカウント（ｒ）が等しければ全
ての処理要素において同時に記憶手段の第１のアドレス
のデータを取り出し、取り出した第１のアドレスデータ
を処理要素間で同時に所定カウント分転送し、各処理要
素では個々の処理要素に転送された第１のアドレスのデ
ータを記憶手段の第２のアドレスに格納する（１５）。 【０００８】また、第１のアドレス（ｈ＋ｒ）に対する
処理要素間の転送回数を第１のアドレス（ｈ＋ｒ）のデ
ータの交換対象となるデータに対する第２のアドレス（
ｈ＋Ｎ−ｒ）のアドレス値からｈを減じた値（Ｎ−ｒ）
とし、第２のアドレス（ｈ＋Ｎ−ｒ）のデータに対する
処理要素間の転送回数を第２のアドレス（ｈ＋Ｎ−ｒ）
のデータの交換対象となるデータに対する第１のアドレ
ス（ｈ＋ｒ）のアドレス値からｈを減じた値ｒとして、
ｒ＝１，２，・・・，［Ｎ／２］に対して処理要素の記
憶手段から取り出されるデータの処理要素間の同時転送
における転送回数をカウントして、取り出したデータに
対する再配置先の処理要素への転送処理を制御する。 【０００９】また、第１のアドレスを保持する第１のカ
ウンタと、第２のアドレスを保持する第２のカウンタと
、処理要素の記憶手段から取り出されるデータの処理要
素間の同時転送における転送回数をカウントする第３の
カウンタと、第１のカウンタの出力と第２のカウンタの
出力とを切り換えるセレクタと、セレクタの出力は第３
のカウンタの入力に接続され、第３のカウンタの値がｈ
に等しいことを検出して第１のフラグを発生する第１の
フラグ発生手段と、セレクタにより第１のフラグの内容
によって第１のカウンタの出力と第２のカウンタの出力
とを切り換える切り換え手段と、繰り返しの回数の制御
パラメータを保持する第１のレジスタと、全ての処理要
素の個数の偶奇性判定用のパラメータを保持する第２の
レジスタと、第１のレジスタの内容と、第１のカウンタ
の内容との一致を検出して第２のフラグを発生させる第
２のフラグ発生手段と、第２のレジスタの最下位ビット
の内容によりすべての処理要素の個数の偶奇性を判断す
る偶奇性判断手段と、第２のフラグの内容と第２のレジ
スタの最下位ビットの内容によってデータの再配置処理
の終了を検出する終了検出手段とを有する。 【００１０】 【作用】複数（Ｎ個）の処理要素を環状に接続し、その
処理要素にはマルチプロセッサ上での並び順に番号付さ
れている。隣接する処理要素間にデータ転送パスを有す
るマルチプロセッサにおいて処理要素の記憶手段の連続
しているアドレスに第１のデータが格納されている状態
から処理要素の記憶手段の同じ連続するアドレスに第２
のデータが格納されるように第１のデータと第２のデー
タのＮ個の処理要素を一括して再配置する。 【００１１】 【実施例】本発明の理系を簡単にするために以下にハイ
デンマーコブモデル法の学習処理及びフォワード−バッ
クワード・プロセデュアにおける学習処理とバウム−ウ
ェルチ・リエスティメーション・フォーミュラスにおけ
る学習処理について説明する。 【００１２】声や文字等のパターン認識処理に用いられ
るＨＭＭ（Ｈｉｄｄｅｎ　Ｍａｒｋｏｖ　Ｍｏｄｅｌｓ
）　法の学習処理をマルチプロセッサの一つの形態であ
るアレイプロセッサを用いて実行する例について説明す
る。 【００１３】このＨＭＭ法を用いたパターン認識では、
ある状態遷移確率モデルを仮定して音声や文字のパター
ンの生起をそのモデルにおける状態間の遷移によって観
測されるシンボル系列としてパターンをモデル化する。 学習処理とは複数のサンプルパターンのデータから、確
率モデルの確率パラメータを推定することである。ＨＭ
Ｍ法の学習処理では、フォワード−バックワード・プロ
セデュア（Ｆｏｒｗａｒｄ−Ｂａｃｋｗａｒｄ　Ｐｒｏ
ｃｅｄｕｒｅ）　とバウム−ウェルチ・リ−エティメー
ション（Ｂａｕｍ−Ｗｅｌｃｈ　Ｒｅ−ｅｓｔｉｍａｔ
ｉｏｎ　Ｆｏｒｍｕｌａｓ）の２種類のアルゴリズムが
用いられる。 ＨＭＭ法の学習処理はこれらのアルゴリズムにより互い
のアルゴリズムの処理結果を用いて求める確率モデルの
推定が収束するまで各々のアルゴリズムの処理を繰り返
す。これらのアルゴリズムの内容が以下に示される。 【００１４】フォワード−バックワード・プロセデュア
は前向きパス・アルゴリズムと後ろ向きパス・アルゴリ
ズムの２種類のアルゴリズムからなる。 【００１５】 　　（１）　前向きパス・アルゴリズム　　初期設定：
　　１≦ｉ≦Ｎに対して　　　　　　　　　　　　　　
α（ｉ，０）＝π（ｉ）　　　　　　　　　　　　　　
　　　　　　　　・・・（１）　　　　　漸化式：　　
１≦ｉ≦Ｎ，ｔ＝１，２，・・・，Ｔに対して【００１
６】 【数１】上記のアルゴリムにおいて、Ｎは処理要素の個
数である。π（ｉ）は初期状態確率を示す。α（ｉ，ｔ
）は確率パラメータである。 【００１７】（２）　後ろ向きパス・アルゴリズム　　
初期設定：　　１≦ｉ≦Ｎに対して　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
１　　　　　　ｆｏｒ　ｉ∈ＥＴ　　　　　　　　　　
　　　　　β（ｉ，Ｔ）＝　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　・・・（３）　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　０　　　　　　ｏｔｈｅｒｗｉｓｅ　
　　　　漸化式：　　１≦ｉ≦Ｎ，ｔ＝Ｔ−１，Ｔ−２
，・・・，０に対して　　　　　　　　 【００１８】 【数２】ここで、ｃ（ｉ，ｊ；ｔ）≡ａ（ｉ，ｊ）・ｂ
（ｉ，ｊ；Ｏｔ　） 【００１９】 【数３】である。 【００２０】上記のアルゴリズムにおいて、β（ｉ，ｔ
）は確率パラメータであり、ａ（ｉ，ｊ）は状態遷移確
率、ｂ（ｉ，ｊ；ｋ）はシンボル出力確率である。 【００２１】また、バウム−ウェルチ・リエティメーシ
ョン・フォーミュラスの処理は初期状態確率π（ｉ）の
再推定計算、状態遷移確率ａ（ｉ，ｊ）の再推定計算、
シンボル出力確率ｂ（ｉ，ｊ；ｋ）の再推定計算の３種
類の計算からなる。各再推定計算の内容を以下に示す。 尚、以下の表記では、π＋　（ｉ），ａ＋　（ｉ，ｊ）
，ｂ＋　（ｉ，ｊ；ｋ）はそれぞれ、π（ｉ），ａ（ｉ
，ｊ），ｂ（ｉ，ｊ；ｋ）の再推定計算結果を表す。 【００２２】（１）　初期状態確率の再推定計算【００
２３】 【数４】（２）　状態遷移確率ａ＋　（ｉ，ｊ）の再推
定計算【００２４】 【数５】（３）　シンボル出力確率ｂ＋　（ｉ，ｊ；ｋ
）の再推定計算 【００２５】 【数６】ここで、ｃ（ｉ，ｊ；ｔ）≡ａ（ｉ，ｊ）・ｂ
（ｉ，ｊ；Ｏｔ　）， 【００２６】 【数７】 【００２７】 【数８】である。 【００２８】上記のフォワード−バックワード・プロセ
デュアとバウム−ウェルチ・リエティメーション・フォ
ーミュラスの各アルゴリズムに対する処理は所望の機能
を持った処理要素（以下ＰＥと呼ぶ）を環状に接続した
アレイプロセッサ構成（以下リングアレイプロセッサと
呼ぶ）を用いて並列処理が可能である。ここで対象とす
るリングアレイプロセッサについて説明する。図２はＨ
ＨＭ法のパターン認識処理における学習処理を並列処理
により実行する場合のリングアレイプロセッサの構成を
示す。リングアレイプロセッサはＰＥ１００ａ，１００
ｂ，・・・，１００ｃ，１００ｄと各ＰＥ間のデータ転
送パス１０１と、各ＰＥの管理下にあるメモリ１０２ａ
，１０２ｂ，・・・，１０２ｃ，１０２ｄ及びＰＥとデ
ータの入出力を行うデータ入出力パス１０３ａ，１０３
ｂ，・・・，１０３ｃ，１０３ｄにより構成される。 以下に図２のリングアレイプロセッサ構成を用いた上記
の各アルゴリズムに対する並列処理方法について説明す
る。 【００２９】 （ａ）　フォワード−バックワード・プロセデュア［ａ
−１］　　前向きパス・アルゴリズム図３は学習処理に
おけるフォワード−バックワード　　プロセデュアの前
向きパス・アルゴリズムをリングアレイプロセッサ構成
で並列処理する場合のデータフローを示す。同図のリン
グアレイプロセッサの構成はＰＥ２００ａ，２００ｂ，
・・・，２００ｃ，２００ｄと各ＰＥ間のデータ転送パ
ス２０１と、各ＰＥの管理下にあるメモリ２０４とのデ
ータの入出力を行うデータ入出力パス２０２ａ，２０２
ｂ，・・・，２０２ｃ，２０２ｄとＰＥ間で循環転送さ
れるデータ列２０３｛α（１、ｔ−１），α（２，ｔ−
１），・・・，α（ｉ，ｔ−１），・・・，α（Ｎ，ｔ
−１）｝である。また、データ列２０４は各ＰＥにおい
て、上記のデータ列２０３の循環転送と同期してその管
理下にあるメモリ２０４から入力される。 【００３０】例えば、ＰＥｉ　（１≦ｉ≦Ｎ）ではデー
タ列ＣＦ　（ｉ，ｔ）はＣＦ　（ｉ，ｔ）＝｛ｃ（ｉ，
ｉ；ｔ），ｃ（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；ｔ），・・
・，ｃ（ｍｏｄ（ｉ−１｜Ｎ），ｉ；ｔ）｝である。 【００３１】ここで、ｍｏｄ（ｍ｜Ｎ）（ｍは整数）は
ｍがＮの整数倍の時はＮをｍがＮの整数倍でないときに
はｍをＮで割ったときの剰余を表す。上記のデータ列Ｃ
Ｆ　（ｉ，ｔ）（１≦ｉ≦Ｔ）はＰＥｉ　（１≦ｉ≦Ｎ
）の管理下にあるメモリに格納されている。また、この
メモリにはデータα（ｉ，ｔ）の初期値α（ｉ，０）＝
π（ｉ）が格納されているとする。 【００３２】ＰＥｉ　（１≦ｉ≦Ｎ）では先ず、（１）
　式に対応するα（ｉ，ｔ）の初期値α（ｉ，０）＝π
（ｉ）をその管理下にあるメモリから読み出し、データ
入出力パス２０２を介して入力する。次にＰＥｉ　（１
≦ｉ≦Ｎ）はその管理下にあるメモリからデータ列ＣＦ
　（ｉ，ｔ）の第１番目のデータｃ（ｉ，ｉ；１）を入
力し、そのデータと先に入力した初期値α（ｉ，０）と
乗算を行い、乗算結果であるα（ｉ，０）・ｃ（ｉ，ｉ
；１）をＰＥ内の格納領域に一時的に保持する。次に次
段の処理としてＰＥｉ　（１≦ｉ≦Ｎ）は先に入力した
初期値α（ｉ，０）を次段のＰＥに送信すると同時に、
前段のＰＥから初期値α（ｍｏｄ（ｉ＋１｜Ｎ），０）
を受信する。これと同時にＰＥの管理下にあるメモリか
らデータ列ＣＦ　（ｉ，ｔ）の２番目のデータｃ（ｍｏ
ｄ（ｉ＋１｜Ｎ），ｉ；１）を入力する。そして、ＰＥ
間で転送されたデータα（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；
１）とこれと同時にメモリから入力されたデータｃ（ｍ
ｏｄ（ｉ＋１｜Ｎ），ｉ；１）との乗算を行い、その乗
算結果であるα（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；１）・ｃ
（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；１）とＰＥ内の格納領域
に保持されている先の乗算結果α（ｉ，０）・ｃ（ｉ，
ｉ；１）との和を計算（即ち積和計算）する。 α（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；１）・ｃ（ｍｏｄ（ｉ
＋１｜Ｎ），ｉ；１）＋α（ｉ，０）・ｃ（ｉ，ｉ；１
） さらに、上記の加算結果をＰＥ内の格納領域に一時的に
保持する。 【００３３】以後、全てのＰＥ間で転送されるデータα
（ｉ，０）がリングアレイプロセッサの全てのＰＥを一
巡するまで繰り返し行い、その都度、上述したような積
和計算を実行する。積和計算の計算結果はＰＥ内の格納
領域に保持する。このようにＰＥ間で循環転送されるデ
ータα（ｉ，０）がリングアレイプロセッサ上を一巡す
ると、ＰＥｉ　（１≦ｉ≦Ｎ）において時刻ｔ＝１に対
するデータα（ｉ，１）が求められる。以後、ｔ＝２に
対するデータα（ｉ，２）の計算処理はここで求められ
たデータα（ｉ，１）でα（ｉ，０）を置き換えてＰＥ
間で循環転送し、これと同時に時刻ｔ＝２に対するデー
タ列ＣＦ　（ｉ，ｔ）のデータをメモリから入力しなが
ら、ｔ＝１の場合と全く同一の処理過程で実行する。ｔ
＝３，・・・，Ｔに対しても同様である。各時刻ｔ＝１
，２，・・・、Ｔに対するα（ｉ，ｔ）の計算結果はＰ
Ｅｉ　（１≦ｉ≦Ｎ）の管理下にあるメモリに逐次格納
される。 【００３４】［ａ−２］　　後向きアルゴリズム図４は
学習処理におけるフォワード−バックワード　　プロセ
デュアの後ろ向きパス・アルゴリズムをリングアレイプ
ロセッサ構成で並列処理する場合のデータフローを示す
。同図のリングアレイプロセッサはＰＥ３００ａ，３０
０ｂ，・・・，３００ｃ，３００ｄと各ＰＥ間のデータ
転送パス３０１と、各ＰＥの管理下にあるメモリとのデ
ータの入出力を行うデータ入出力パス３０２ａ，３０２
ｂ，・・・，３０２ｃ，３０２ｄとＰＥ間で循環転送さ
れるデータ列３０３｛β（１，ｔ＋１），β（２，ｔ＋
１），・・・，β（ｉ，ｔ＋１），・・・β（Ｎ，ｔ＋
１）｝により構成される。データ列３０４は各ＰＥ３０
０ａ，３００ｂ，・・・，３００ｃ，３００ｄにおいて
上記のデータ列３０３の循環転送と同期にして、その管
理下にあるメモリから入力される。ＰＥｉ　（１≦ｉ≦
Ｎ）ではデータ列ＣＢ　（ｉ，ｔ＋１）（０≦ｔ≦Ｔ−
１）はＣＢ　（ｉ，ｔ＋１）＝｛ｃ（ｉ，ｉ；ｔ＋１）
，ｃ（ｉ，ｍｏｄ（ｉ＋１｜Ｎ）；ｔ＋１），・・・，
ｃ（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ＋１）｝である。こ
のデータ列ＣＢ　（ｉ，ｔ＋１）（０≦ｔ≦Ｔ−１）は
ＰＥｉ　（１≦ｉ≦Ｎ）の管理下にあるメモリに格納さ
れている。また、このメモリにはデータβ（ｉ，ｔ）の
初期値β（ｉ，Ｔ）が格納されているものとする。 【００３５】この後ろ向きパス・アルゴリズムに対する
並列処理はＰＥ間の循環転送データをβ（ｉ，ｔ＋１）
、これと同時にメモリからＰＥｉ　（１≦ｉ≦Ｎ）に入
力されるデータ列をＣＢ　（ｉ，ｔ＋１）として、前向
きパス・アルゴリズムの並列処理と全く同様の処理を実
行する。即ち、ＰＥｉ　（１≦ｉ≦Ｎ）では先ず、（３
）　式に対応するβ（ｉ，ｔ）の初期値β（ｉ，Ｔ）が
その管理下にあるメモリから読み出され、データ入出力
パス３０２を介して入力される。次にＰＥｉ　（１≦ｉ
≦Ｎ）はＰＥｉ　の管理下にあるメモリからデータ列Ｃ
Ｂ　（ｉ，ｔ＋１）の第１番目のデータｃ（ｉ，ｉ；Ｔ
）を入力する。そのデータと先に入力した初期値β（ｉ
，Ｔ）との乗算を行い、その乗算結果であるβ（ｉ，Ｔ
）・ｃ（ｉ，ｉ；Ｔ）をＰＥ内の格納領域に一時的に保
持する。次にＰＥｉ　（１≦ｉ≦Ｎ）は先に入力した初
期値β（ｉ，Ｔ）を次段のＰＥに送信すると同時に、前
段のＰＥから初期値β（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；Ｔ
）受信し、同時にＰＥの管理下にあるメモリからデータ
列ＣＢ　（ｉ，ｔ＋１）の２番目のデータｃ（ｍｏｄ（
ｉ＋１｜Ｎ），ｉ；Ｔ）を入力する。さらに、ＰＥ間で
転送されたデータβ（ｍｏｄ（ｉ＋１｜Ｎ），Ｔ）とこ
れと同時にメモリから入力されたデータｃ（ｍｏｄ（ｉ
＋１｜Ｎ），ｉ；Ｔ）との乗算を行い、その乗算結果で
あるβ（ｍｏｄ（ｉ＋１｜Ｎ），Ｔ）・ｃ（ｍｏｄ（ｉ
＋１｜Ｎ），ｉ；Ｔ）とＰＥ内の格納領域に保持されて
いる先に求められている乗算結果β（ｉ，Ｔ）・ｃ（ｉ
，ｉ；Ｔ）との和を計算（即ち、積和計算）する。 【００３６】β（ｍｏｄ（ｉ＋１｜Ｎ），Ｔ）・ｃ（ｍ
ｏｄ（ｉ＋１｜Ｎ），ｉ；Ｔ）＋　　β（ｉ，Ｔ）・ｃ
（ｉ，ｉ；Ｔ） 上記の加算結果をＰＥ内の格納領域に一時的に保持する
。以後すべてのＰＥはこのようなＰＥ間データ転送とメ
モリからのデータ入力との同時実行をＰＥ間で転送され
るデータβ（ｉ，Ｔ）がリングアレイプロセッサ上の全
てのＰＥを一巡するまで繰り返し行い、その都度、上記
の積和計算を実行する。積和計算の結果はＰＥ内の格納
領域に保持される。ＰＥ間で循環転送されるデータβ（
ｉ，Ｔ）がリングアレイプロセッサ上を一巡すると、Ｐ
Ｅｉ　（１≦ｉ≦Ｎ）において時刻ｔ＝Ｔ−１に対する
データβ（ｉ，Ｔ−１）が求められる。以後ｔ＝Ｔ−２
に対するデータβ（ｉ，Ｔ−２）の計算処理はここで求
められたデータβ（ｉ，Ｔ−１）でデータβ（ｉ，Ｔ）
を置き換えてＰＥ間で循環転送する。これと同時に時刻
ｔ＝Ｔ−２に対するデータ列ＣＢ　（ｉ，ｔ＋１）のデ
ータをメモリから入力しながら、ｔ＝Ｔ−１の場合と全
く同一の処理過程で実行する。ｔ＝Ｔ−３，・・・，０
に対しても同様である。各時刻ｔ＝Ｔ−１，Ｔ−２，・
・・，０に対するβ（ｉ，ｔ）の計算結果はＰＥｉ　（
１≦ｉ≦Ｎ）の管理下にあるメモリに逐次格納される。 【００３７】フォワード−バックワード・プロセデュア
の前向きパス・アルゴリズム、及び後向きパス・アルゴ
リズムに対して、それぞれ、上記のような並列処理を実
行すると、各ＰＥのメモリには次のようなα（ｉ，ｔ）
及びβ（ｉ，ｔ）の計算結果が得られる。 【００３８】ＰＥｉ　（１≦ｉ≦Ｎ）の管理下にあるメ
モリに格納される計算結果： α（ｉ，０），α（ｉ，１），・・・，α（ｉ，ｔ），
・・・，α（ｉ，Ｔ）；β（ｉ，Ｔ），β（ｉ，Ｔ−１
），・・・，β（ｉ，ｔ），・・・β（ｉ，０）尚、上
記の計算結果の並べ方は計算結果が求められる順番に同
じである。 【００３９】（ｂ）　　バウム−ウェルチ・リエティメ
ーション・フォーミュラス ［Ｂ−１］　　初期状態確率の再推定計算の並列処理方
法先ず、バウム−ウェルチ・リエティメーション・フォ
ーミュラスにおける初期状態確率π（ｉ）の再推定計算
に対する並列処理方法について説明する。 【００４０】図５は学習処理におけるバウム−ウェルチ
・リ−エティメーション・フォーミュラスの初期状態確
率の再推定計算をリングアレイプロセッサ構成で並列処
理する場合のデータフローを示す。このリングアレイプ
ロセッサの構成はＰＥ４００ａ，４００ｂ，・・・，４
００ｃ，４００ｄと各ＰＥ間のデータ転送パス４０１と
ＰＥとそのＰＥが管理するメモリ間のデータ入出力パス
４０２とＰＥ間で循環転送されるデータ列４０３｛α（
１，０）・β（１，０），α（２，０）・β（２、０）
，・・・，α（ｉ，０）・β（ｉ，０），・・・，α（
Ｎ，０）・β（Ｎ，０）｝とデータ入出力パス４０２を
介してメモリから入力されるデータ列４０４等により構
成される。データ列４０４はＰＥｉ　（１≦ｉ≦Ｎ）で
はＤ（ｉ，０）＝｛α（ｉ，０），β（ｉ，０）｝が入
力される。このデータ列Ｄ（ｉ，０）はＰＥｉ　（１≦
ｉ≦Ｎ）の管理下にあるメモリに格納されているとする
。 【００４１】この並列処理では先ずＰＥｉ　（１≦ｉ≦
Ｎ）において、（５）　式の分子の計算を実行するため
に必要なデータ列Ｄ（ｉ，０）＝｛α（ｉ，０），β（
ｉ，０）｝がデータ入出力パス４０２を介してメモリか
ら入力される。ＰＥｉ　（１≦ｉ≦Ｎ）は入力されたデ
ータ列Ｄ（ｉ，０）＝｛α（ｉ，０），β（ｉ，０）｝
の２種類のデータα（ｉ，０）及びβ（ｉ，０）を用い
て分子の積計算α（ｉ，０）・β（ｉ，０）を並列に実
行する。分母の計算であるＰ（Ｏ｜λ）はα（ｉ，０）
，β（ｉ，０）を用いた計算式を用いると、各ＰＥで並
列に計算した分子の計算結果の総和に等しい。従って、
分母の計算はＰＥｉ　（１≦ｉ≦Ｎ）の積計算結果α（
ｉ，０）・β（ｉ，０）をリングアレイプロセッサの全
てのＰＥを一巡するまでＰＥ間で循環転送し、全てのＰ
Ｅにおいて、その転送データの累積加算を並列に実行す
ることにより求められる。従って、それぞれのＰＥで求
められた分子の計算結果を分母の計算結果で除算するこ
とにより、初期状態確率π（ｉ）の再推定計算結果π＋
　（ｉ）（１≦ｉ≦Ｎ）がＰＥｉ　（１≦ｉ≦Ｎ）で同
時に求められる。さらに、得られた初期状態確率π（ｉ
）の再推定計算結果π＋　（ｉ）はＰＥｉ　（１≦ｉ≦
Ｎ）が管理するメモリに格納される。 【００４２】［Ｂ−２］　　状態遷移確率の再推定計算
の並列処理方法 次にリングアレイプロセッサ構成を用いた状態遷移確率
ａ（ｉ，ｊ）の再推定計算の並列処理を説明する。図６
は学習処理におけるバウム−ウェルチ・リエスティメー
ション・フォーミュラスの状態遷移確率の再推定計算を
リングアレイプロセッサ構成で並列処理する場合のデー
タフローを示す。データ転送パス５０１は各ＰＥ５００
ａ，５００ｂ，・・・，５００ｃ，５００ｄ間に設けら
れる。データ入出力パス５０２ａ，５０２ｂ，・・・，
５０２ｃ，５０２ｄは各ＰＥ５００ａ，５００ｂ，・・
・，５００ｃ，５００ｄとその管理下にあるメモリとの
間のデータの入出力を行うためのパスである。データ列
５０３はＰＥ５００ａ，５００ｂ，・・・，５００ｃ，
５００ｄ間で循環転送されるデータ列である。図６に示
した例では、データ列５０３はβ（１，ｔ），β（２，
ｔ），・・・，β（ｉ，ｔ），・・・，β（ｉ，ｔ），
・・・，β（Ｎ，ｔ）｝を示している。第１のデータ列
５０４はデータ入出力パス５０２を介してメモリから入
力され、ＰＥｉ　（１≦ｉ≦Ｎ）において、データ列Ｄ
（ｉ，ｔ）＝｛α（ｉ，ｔ），β（ｉ，ｔ）｝（０≦ｔ
≦Ｔ）が入力される。第２のデータ列５０５はデータ入
出力パス５０２を介してメモリから入力され、ＰＥｉ　
（１≦ｉ≦Ｎ）において、データ列ＣＢ　（ｉ，ｔ）＝
｛ｃ（ｉ，ｉ；ｔ），ｃ（ｍｏｄ（ｉ＋１｜Ｎ）；ｔ）
，・・・，ｃ（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ）｝が入
力される。この第１のデータ列５０４、第２のデータ列
５０５はともにＰＥの管理するメモリに格納されている
ものとする。 【００４３】この並列処理では先ず（６）　式の分母の
計算処理を実行するために、データ列Ｄ（ｉ，ｔ）＝｛
α（ｉ，ｔ），β（ｉ，ｔ）｝（０≦ｔ≦Ｔ）がＰＥｉ
　（１≦ｉ≦Ｎ）にメモリから入力される。ＰＥｉ　（
１≦ｉ≦Ｎ）は入力されたデータ列Ｄ（ｉ，ｔ）＝｛α
（ｉ，ｔ），β（ｉ，ｔ）｝（０≦ｔ≦Ｔ）の２種類の
データα（ｉ，ｔ）及びβ（ｉ，ｔ）を用いて、時刻ｔ
に関する積和計算 Σα（ｉ，ｔ）・β（ｉ，ｔ） を実行し、分母の計算結果を求める。この積和計算は全
てのＰＥにおいて並列に実行される。一方、分子の計算
処理ではＰＥｉ　（１≦ｉ≦Ｎ）は先に入力されたデー
タ列Ｄ（ｉ，ｔ）＝｛α（ｉ，ｔ），β（ｉ，ｔ）｝（
０≦ｔ≦Ｔ）のデータβ（ｉ，ｔ）を全てのＰＥを一巡
するまで循環転送しながら、これと同期してＰＥｉ　（
１≦ｉ≦Ｎ）にメモリからデータ列ＣＢ　（ｉ，ｔ）を
入力し、その時々でＰＥｉ　（１≦ｉ≦Ｎ）に入力され
るＰＥ間の循環転送データ、データ列ＣＢ　（ｉ，ｔ）
のデータ、先に入力されたデータ列Ｄ（ｉ，ｔ）のデー
タα（ｉ，ｔ−１）との３項間の乗算を並列に実行する
。この処理により、ＰＥｉ　（１≦ｉ≦Ｎ）にはｊ＝１
，２，・・・，Ｎの（ｉ，ｊ）の組み合わせに対する分
子の時刻ｔの被累積加算項が求められる。従って、時刻
ｔを更新して上記のような３項間の乗算に係わる処理を
実行し、各（ｉ，ｊ）の組み合わせに対して得られた計
算結果を各時刻ｔ毎に累積加算すれば分子の計算結果が
求められる。上記のこれらの処理は全てＰＥで並列に実
行される。上記の処理過程により求められた分母、分子
の計算結果を用いて、並列に分子を分母で除算すること
により、ＰＥｉ　（１≦ｉ≦Ｎ）にはｊ＝１，２，・・
・，Ｎの（ｉ，ｊ）の組み合わせに対する状態遷移確率
ａ（ｉ，ｊ）の再推定値ａ＋　（ｉ，ｊ）が求められる
。 【００４４】また、以上のような並列処理方法からわか
るように、分子の計算の並列処理ではＰＥ間の転送デー
タをα（ｉ，ｔ−１），ＰＥｉ　（１≦ｉ≦Ｎ）にメモ
リから入力される第２のデータ列５０５をＣＦ　（ｉ，
ｔ）＝｛ｃ（ｉ，ｉ；ｔ），ｃ（ｍｏｄ（ｉ＋１｜Ｎ）
，ｉ；ｔ），ｃ（ｍｏｄ（ｉ＋２｜Ｎ），ｉ；ｔ），・
・・，ｃ（ｍｏｄ（ｉ−１｜Ｎ），ｉ；ｔ）｝とし、分
子の３項間の乗算においてはデータ列Ｄ（ｉ，ｔ）＝｛
α（ｉ，ｔ），β（ｉ，ｔ）｝（０≦ｔ≦Ｔ）からのデ
ータとしてβ（ｉ，ｔ）を用いればＰＥｉ　（１≦ｉ≦
Ｎ）にはｊ＝１，２，・・・，Ｎの（ｊ，ｉ）の組み合
わせに対する分子の計算結果が得られる。 【００４５】従ってＰＥｉ　（１≦ｉ≦Ｎ）にはｊ＝１
，２，・・・，Ｎの（ｊ，ｉ）の組み合わせに対する状
態遷移確率ａ（ｊ，ｉ）の再推定値ａ＋　（ｊ，ｉ）は
分母の計算結果をすべてのＰＥに対して一巡するまでＰ
Ｅ間で循環転送し、得られた分子の計算結果をその時々
に転送される分母の計算結果で除算することにより求め
られる。 【００４６】［ｂ−３］　　シンボル出力確率の再推定
計算の並列処理 次にリングアレイプロセッサ構成用いたシンボル出力確
率ｂ（ｉ，ｊ；ｋ）の再推定計算の並列処理について説
明する。図７は学習処理におけるバウム−ウェルチ・リ
エスティメーション・フォーミュラスのシンボル出力確
率の再推定計算をリングアレイプロセッサ構成で並列処
理する場合のデータフローを示す。データ転送パス６０
１は各ＰＥ６００ａ，６００ｂ，・・・，６００ｃ，６
００ｄ間に設けられる。データ入出力パス６０２ａ，６
０２ｂ，・・・，６０２ｃ，６０２ｄは各ＰＥ６００ａ
，６００ｂ，６００ｃ，６００ｄとその管理下にあるメ
モリとの間のデータの入出力を行うためのパスである。 データ列６０３はＰＥ６００ａ，６００ｂ，・・・，６
００ｃ，６００ｄ間で循環転送されるデータ列である。 図７に示した例ではデータ列６０３は｛β（１，ｔ），
β（２，ｔ），・・・，β（ｉ，ｔ），・・・，β（ｉ
，ｔ），・・・，β（Ｎ，ｔ）｝である。第１のデータ
列６０４は各データ入出力パス６０２ａ，６０２ｂ，６
０２ｃ，６０２ｄを介してメモリから入力される。ＰＥ
ｉ（１≦ｉ≦Ｎ）においてはデータ列Ｄ（ｉ，ｔ）は Ｄ（ｉ，ｔ）＝｛α（ｉ，ｔ），β（ｉ，ｔ）｝　　　
　（０≦ｔ≦Ｔ） が入力される。また、第２のデータ列６０５は各データ
入出力パス６０２ａ，６０２ｂ，６０２ｃ，６０２ｄを
介してメモリから入力される。ＰＥｉ（１≦ｉ≦Ｎ）に
おいてはデータ列ＣＢ　（ｉ，ｔ） ＣＢ　（ｉ，ｔ）＝｛ｃ（ｉ，ｉ；ｔ），ｃ（ｉ，ｍｏ
ｄ（ｉ＋１｜Ｎ）；ｔ），・・・，（ｉ，ｍｏｄ（ｉ−
１｜Ｎ）；ｔ）｝とデータ列ＧＢ　 ＧＢ　（ｉ，ｔ）＝｛（ｇ（ｉ，ｉ；ｔ），ｇ（ｉ，ｍ
ｏｄ（ｉ＋１｜Ｎ）；ｔ），・・・，ｇ（ｉ，ｍｏｄ（
ｉ−１｜Ｎ）；ｔ）｝のデータが１つずつ組になって入
力される。即ち、ＰＥｉ（１≦ｉ≦Ｎ）には、｛ｃ（ｉ
，ｉ；ｔ），ｇ（ｉ，ｉ；ｔ）｝，｛ｉ，ｍｏｄ（ｉ＋
１｜Ｎ）；ｔ），ｇ（ｉ，ｍｏｄ（ｉ＋１｜Ｎ）；ｔ）
｝，・・・，｛ｃ（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ），
ｇ（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ）｝の順で入力され
る。これらのデータは第１のデータ列６０４及び第２の
データ列６０５を構成するデータ列ＣＢ　（ｉ，ｔ）、
ＧＢ　（ｉ，ｔ）と共に、ＰＥの管理するメモリに格納
されているものとする。 【００４７】ここで、第２のデータ列ＧＢ　（ｉ，ｔ）
のデータはシンボルＯｔ　と基準シンボルｋとの類似度
を表すパラメータｕ（ｔ；ｋ）を使用して ｇ（ｉ，ｊ；ｔ）＝ｃ（ｉ，ｊ；ｔ）・ｕ（ｔ；ｋ）と
定義する。 【００４８】シンボル出力確率ｂ（ｉ，ｊ；ｋ）の再推
定計算は（７）　式からわかるように、分母、分子の計
算内容は殆ど同一で、分子の計算にシンボルＯｔ　に関
する条件としてシンボルＯｔ　＝ｋが付加されている点
だけが異なる。また、この分母、分子の計算は状態遷移
確率ａ（ｉ，ｊ）の再推定計算の分子の計算と全く同等
である。従って、このシンボル出力確率ｂ（ｉ，ｊ；ｋ
）の再推定計算の分母、分子の計算処理は先に述べた状
態遷移確率ａ（ｉ，ｊ）の再推定計算の分子の並列計算
処理法をそのまま応用して実行できる。 【００４９】次に図７に沿って分母、分子の並列計算処
理法について説明する。先ず、ＰＥｉ（１≦ｉ≦Ｎ）は
データ入出力パス６０２ａ，６０２ｂ，・・・，６０２
ｃ，６０２ｄを介してメモリから第１のデータ列Ｄ（ｉ
，ｔ）＝｛α（ｉ，ｔ），β（ｉ，ｔ）｝　　　　（０
≦ｔ≦Ｔ） を入力する。そして、分母、分子の並列計算処理では、
転送データが一巡するまでＰＥ間でデータβ（ｉ，ｔ）
を循環転送しながら、これと同期してＰＥｉ（１≦ｉ≦
Ｎ）にメモリから第２のデータ列 ｛ｃ（ｉ，ｉ；ｔ），ｇ（ｉ，ｉ；ｔ）｝，｛ｃ（ｉ，
ｍｏｄ（ｉ＋１｜Ｎ）；ｔ），ｇ（ｉ，ｍｏｄ（ｉ＋１
｜Ｎ）；ｔ）｝，｛ｃ（ｉ，ｍｏｄ（ｉ＋２｜Ｎ）；ｔ
），ｇ（ｉ，ｍｏｄ（ｉ＋２｜Ｎ）；ｔ）｝，・・・，
｛ｃ（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ），ｇ（ｉ，ｍｏ
ｄ（ｉ−１｜Ｎ）；ｔ）｝を入力する。ＰＥｉ（１≦ｉ
≦Ｎ）ではその時々で入力されるＰＥ間の循環転送デー
タ、第２のデータ列の２種類のデータ、第１のデータ列
のデータα（ｉ，ｔ−１）を用いて、（７）　式での分
母の計算についてはデータα，ｃ，βの３項間の乗算を
実行し、分子の計算についてはデータα，ｇ，βの３項
間の乗算を実行する。この分母、分子の乗算の処理はす
べてのＰＥにおいて並列に実行される。この処理により
、ＰＥｉ（１≦ｉ≦Ｎ）にはｊ＝１，２，・・・，Ｎの
（ｉ，ｊ）の組み合わせに対する分母・分子の時刻ｔに
対する被累積加算項が求められる。従って、時刻ｔを更
新して上記のよウな３項間の乗算に係わる処理を実行し
、その計算結果を各時刻ｔ毎に累積加算すれば、分母、
分子の計算結果が求められる。これらの処理はＰＥ間で
並列に実行される。上記の処理過程により求められた分
母、分子の計算結果を用いて、並列に分子を分母で除算
することにより、ＰＥｉ（１≦ｉ≦Ｎ）にはｊ＝１，２
，・・・，Ｎの（ｉ，ｊ）の組み合わせに対するシンボ
ル出力確率の再推定値としてｂ＋　（ｉ，ｊ；ｋ）が求
められる。 【００５０】また、以上の並列処理方法からわかるよう
にこの計算の並列処理では複数のＰＥ間の転送データを
α（ｉ，ｔ−１），ＰＥｉ（１≦ｉ≦Ｎ）にメモリから
入力される第２のデータ列を、 データ列ＣＦ　（　ｉ，ｔ）＝｛ｃ（ｉ，ｉ；ｔ），ｃ
（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；ｔ），ｃ（ｍｏｄ（ｉ＋
２｜Ｎ），ｉ；ｔ），・・・，ｃ（ｍｏｄ（ｉ−１｜Ｎ
），ｉ；ｔ）｝と データ列ＧＦ　（ｉ，ｔ）＝｛ｇ（ｉ，ｉ；ｔ），ｇ（
ｍｏｄ（ｉ＋１｜Ｎ），ｉｔ），ｇ（ｍｏｄ（ｉ＋２｜
Ｎ），ｉ；ｔ）｝，・・・，ｇ（ｍｏｄ（ｉ−１｜Ｎ）
，ｉ；ｔ）｝のデータを１つずつ組にしたデータ列｛ｃ
（ｉ，ｉ；ｔ），ｇ（ｉ，ｉ；ｔ）｝，｛ｃ（ｍｏｄ（
ｉ＋１｜Ｎ），ｉ；ｔ），ｇ（ｍｏｄ（ｉ＋１｜Ｎ），
ｉ；ｔ）　｝，｛ｃ（ｍｏｄ（ｉ＋２｜Ｎ），ｉ；ｔ）
，ｇ（ｍｏｄ（ｉ＋２｜Ｎ），ｉ；ｔ）｝，・・・，｛
ｃ（ｍｏｄ（ｉ−１｜Ｎ），ｉ；ｔ），ｇ（ｍｏｄ（ｉ
−１｜Ｎ），ｉ；ｔ）｝とし、３項間の乗算においては
データ列Ｄ（ｉ，ｔ）からのデータとしてデータβ（ｉ
，ｔ）を用いれば、ＰＥｉ（１≦ｉ≦Ｎ）にはｊ＝１，
２，・・・、Ｎの（ｊ，ｉ）の組み合わせに対するシン
ボル出力確率の再推定値ｂ＋　（　ｊ，ｉ；ｋ）が求め
られる。 【００５１】以上、ＰＥｉ（１≦ｉ≦Ｎ）においてｊ＝
１，２，・・・，Ｎの（ｉ，ｊ）（または（ｊ，ｉ））
の組み合わせに対する状態遷移確率の再推定値（ａ＋　
（ｉ，ｊ）（またはａ＋　（ｊ，ｉ））及びシボル出力
確率の再推定値ｂ＋　（ｉ，ｊ；ｋ）（またはｂ＋　（
ｊ，ｉ；ｋ））が求められると、ＰＥｉ（１≦ｉ≦Ｎ）
はシンボルＯｔ　と基準シンボルｋとの類似度を表すパ
ラメータｕ（ｔ；ｋ）を用いてｋに関する以下の積和計
算Σｕ（ｔ；ｋ）・ｂ＋　（ｉ，ｊ；ｋ）または Σｕ（ｔ；ｋ）・ｂ＋　（ｊ，ｉ；ｋ）を実行してシン
ボルＯｔ　に対するシンボル出力確率の再推定値ｂ＋　
（ｉ，ｊ；Ｏｔ　）又は、ｂ＋　（ｊ，ｉ；Ｏｔ　）を
求め、その結果と状態遷移確率の再推定値ａ＋　（ｉ，
ｊ）（またはａ＋　（ｊ，ｉ））との乗算を実行し、デ
ータｃ（ｉ，ｊ；ｔ）（又は、ｃ（ｊ，ｉ；ｔ））の再
推定値ｃ＋　（ｉ，ｊ；ｔ）（又はｃ＋　（ｊ，ｉ；ｔ
））を求める。 【００５２】ここに再推定値を得るための流れを示す。 ｂ＋　（ｉ，ｊ；Ｏｔ　）＝Σｕ（ｔ；ｋ）・ｂ＋　（
ｉ，ｊ；ｋ） 又は、 ｂ＋　（ｉ，ｉ；Ｏｔ　）＝Σｕ（ｔ；ｋ）・ｂ＋　（
ｊ，ｉ；ｋ） 次に ｃ＋　（ｉ，ｊ；ｔ）＝ｂ＋　（ｉ，ｊ；Ｏｔ　）・ａ
＋　（ｉ，ｊ） 又は ｃ＋　（ｊ，ｉ；ｔ）＝ｂ＋　（ｊ，ｉ；Ｏｔ　）・ａ
＋　（ｊ，ｉ） この結果はＰＥの管理下にあるメモリに格納される。 【００５３】また、データｇ（ｉ，ｊ；ｔ）（又はｇ（
ｊ，ｉ；ｔ））の再推定値ｇ＋　（ｉ，ｊ；ｔ）（又は
ｇ＋　（ｊ，ｉ；ｔ））はｕ（ｔ；ｋ）・ｂ＋　（ｉ，
ｊ；Ｏｔ　）（又はｕ（ｔ；ｋ）・ｂ＋　（ｊ，ｉ；Ｏ
ｔ　）の乗算結果と状態遷移確率の再推定値ａ＋　（ｉ
，ｊ）（又はａ＋　（ｊ，ｉ））との乗算を実行するこ
とによって求め、 　　ｇ＋　（ｉ，ｊ；ｔ）＝｛ｕ（ｔ；ｋ）・ｂ＋　（
ｉ，ｊ；Ｏｔ　）｝　　　　　　　　　　　　　　　　
　　　　　　　　・ａ＋　（ｉ，ｊ）　　ｇ＋　（ｊ，
ｉ；ｔ）＝｛ｕ（ｔ；ｋ）・ｂ＋　（ｊ，ｉ；Ｏｔ　）
｝　　　　　　　　　　　　　　　　　　　　　　　　
・ａ＋　（ｊ，ｉ）その結果はＰＥの管理下にあるメモ
リに格納される。 【００５４】以上のようなバウムウェルチ・リエスティ
メーション・フォーミュラスの３種類の再推定計算に対
する並列計算処理を実行することにより、リングアレイ
プロセッサの各ＰＥで求められる計算結果の分布は以下
のようになる。 【００５５】ＰＥｉ（１≦ｉ≦Ｎ）の管理するメモリに
格納される計算結果： （ａ）ＰＥ間の転送データをα（ｉ，ｔ）とした並列処
理法の場合 π＋　（ｉ）； １≦ｔ≦Ｔに対する ｃ＋　（ｉ，ｉ；ｔ），ｃ＋　（ｍｏｄ（ｉ＋１｜Ｎ）
，ｉ；ｔ），・・，ｃ＋　（Ｎ，ｉ；ｔ），ｃ＋　（１
，ｉ；ｔ），ｃ＋　（２，ｉ；ｔ），・・，ｃ＋　（ｍ
ｏｄ（ｉ−１｜Ｎ），ｉ；ｔ）； １≦ｔ≦Ｔに対する ｇ＋　（ｉ，ｉ；ｔ），ｇ＋　（ｍｏｄ（ｉ＋１｜Ｎ）
，ｉ；ｔ），・・，ｇ＋　（Ｎ，ｉ；ｔ），ｇ＋　（１
，ｉ；ｔ），ｇ＋　（２，ｉ；ｔ），・・，ｇ＋　（ｍ
ｏｄ（ｉ−１｜Ｎ），ｉ；ｔ）； （ｂ）ＰＥ間の転送データをβ（ｉ，ｔ）とした並列処
理方法の場合 π＋　（ｉ）； １≦ｔ≦Ｔに対する ｃ＋　（ｉ，ｉ；ｔ），ｃ＋　（ｉ，ｍｏｄ（ｉ＋１｜
Ｎ），ｉ；ｔ），・・，ｃ＋　（ｉ，Ｎ，；ｔ），ｃ＋
　（ｉ，１；ｔ），ｃ＋　（ｉ，２；ｔ），・・，ｃ＋
（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ）；１≦ｔ≦Ｔに対す
る ｇ＋　（ｉ，ｉ；ｔ），ｇ＋　（ｉ，ｍｏｄ（ｉ＋１｜
Ｎ）；ｔ），・・，ｇ＋　（ｉ，Ｎ；ｔ），ｇ＋　（ｉ
，１；ｔ），ｇ＋　（ｉ，２；ｔ），・・，ｇ＋　（ｉ
，ｍｏｄ（ｉ−１｜Ｎ）；ｔ）； 尚、上記の（ａ），（ｂ）の計算結果の並べ方は、計算
結果が得られる順番に同じである。 【００５６】（Ｃ）　　学習処理に必要となるデータの
再配置処理の内容 これまで、説明してきたフォワード−バックワード・プ
ロセデュアとバウムウェルチ・リエスティメーション・
フォーミュラスに対するリングアレイプロセッサ構成を
用いた並列処理法とそれによって各ＰＥのメモリに得ら
れる処理結果の分布から学習処理に必要となるデータの
再配置処理の内容を説明する。 【００５７】互いの処理結果を使ってフォワード−バッ
クワード・プロセデュアとバウムウェルチ・リエスティ
メーション・フォーミュラスの処理を繰り返し実行する
学習処理は、具体的には次のような処理を実行するに他
ならない。。先ず、初期状態確率π（ｉ）、状態遷移確
率ａ（ｉ，ｊ），シンボル出力確率ｂ（ｉ，ｊ；ｋ）の
初期値を適当に設定し、フォワード−バックワード・プ
ロセデュアの処理により確率パラメータα（ｉ，ｔ），
β（ｉ，ｔ）を計算する。そして、上記の３種類の確率
の初期値とフォワード−バックワード・プロセデュアよ
り求められた２種類の確率パラメータα（ｉ，ｔ），β
（ｉ，ｔ）を用いてバウムウェルチ・リエスティメーシ
ョン・フォーミュラスより初期状態確率π（ｉ），状態
遷移確率ａ（ｉ，ｊ），シンボル出力確率ｂ（ｉ，ｊ；
ｋ）の再推定を行い、その結果をそれぞれπ＋　（ｉ）
，ａ＋　（ｉ，ｊ），ｂ＋　（ｉ，ｊ；ｋ）とする。再
推定結果が初期と異なれば、初期値を再推定値に置き換
えて、再度、フォワード−バックワード・プロセデュア
とバウム−ウェルチ・リエスティメーション・フォーミ
ュラスの処理を行う。このような処理をバウム−ウェル
チ・リエスティメーション・フォーミュラスにより求め
られた再推定値がフォワード−バックワード・プロセデ
ュアの計算で用いられた各種の確率の値に一致するまで
実行する。 【００５８】上記の繰り返しの処理の内容から、繰り返
し処理の実行中はフォワード−バックワード・プロセデ
ュアの処理で用いられるデータπ（ｉ），ａ（ｉ，ｊ）
，ｂ（ｉ，ｊ；ｋ）としては、バウムウェルチ・リエス
ティメーション・フォーミュラスの処理で得られるπ＋
　（ｉ），ａ＋　（ｉ，ｊ），ｂ＋　（ｉ，ｊ；ｋ）を
用い、バウムウェルチ・リエスティメーション・フォー
ミュラスで用いるデータはフォワード−バックワード・
プロセデュアの処理で用いられるデータπ（ｉ），ａ（
ｉ，ｊ），ｂ（ｉ，ｊ；ｋ）とフォワード−バックワー
ド・プロセデュアの処理で得られるデータα（ｉ，ｔ）
，β（ｉ，ｔ）である。 【００５９】従って、データの再配置処理の目的はフォ
ワード−バックワード・プロセデュアの並列処理後にＰ
Ｅのメモリに保持されるデータの分布がバウム−ウェル
チ・リエスティメーション・フォーミュラスの並列処理
に対する初期データ分布にバウムウェルチ・リエスティ
メーション・フォーミュラスの並列処理後のＰＥのメモ
リに保持されるデータの分布がフォワード−バックワー
ド・プロセデュアに対する並列処理の初期データ分布に
適するようにすることである。 【００６０】上記の各並列処理法の説明から、それぞれ
の並列処理において必要となるＰＥｉ（１≦ｉ≦Ｎ）の
管理下にあるメモリのデータ分布を整理し、以下に示す
。 【００６１】［Ｃ−１］　　フォワード−バックワード
プロセデュアの前向きパス・アルゴリズムのデータ分布
使用するデータ：α（ｉ，０）＝π（ｉ），ＣＦ　（ｉ
，ｔ）＝｛ｃ（ｉ，ｉ；ｔ），ｃ（ｍｏｄ（ｉ＋１｜Ｎ
），ｉ；ｔ），・・・，ｃ（ｍｏｄ（ｉ−１｜Ｎ），ｉ
；ｔ）｝（１≦ｔ≦Ｔ） 得られるデータ：｛α（ｉ，１），・・・，α（ｉ，ｔ
），・・・，α（ｉ，Ｔ）｝ ［Ｃ−２］　　フォワード−バックワードプロセデュア
の後向きパス・アルゴリズムのデータ分布使用するデー
タ：β（ｉ，Ｔ），ＣＢ　（ｉ，ｔ）＝｛ｃ（ｉ，ｉ；
ｔ），ｃ（ｉ，ｍｏｄ（ｉ＋１｜Ｎ）；ｔ），・・・，
ｃ（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ）｝（１≦ｔ≦Ｔ） 得られるデータ：｛β（ｉ，Ｔ−１），・・・，β（ｉ
，ｔ），・・・，β（ｉ，０）｝ ［Ｃ−３］　　バウム−ウェルチ・リエスティメーショ
ン・フォーミュラスの再推定計算のデータ分布（１）　
ＰＥ間の循環転送データがα（ｉ，ｔ）の場合使用する
データ：｛α（ｉ，０），α（ｉ，１），・・・，α（
ｉ，ｔ），・・・，α（ｉ，Ｔ）｝｛β（ｉ，０），β
（ｉ，１），・・・，β（ｉ，ｔ），・・・，β（ｉ，
Ｔ）｝， ＣＦ　（ｉ，ｔ）＝｛ｃ（ｉ，ｉ；ｔ），ｃ（ｍｏｄ（
ｉ＋１｜Ｎ），ｉ；ｔ），ｃ（ｍｏｄ（ｉ−１｜Ｎ），
ｉ；ｔ）｝（１≦ｔ≦Ｔ） ＣＦ　（ｉ，ｔ）＝｛ｇ（ｉ，ｉ；ｔ），ｇ（ｍｏｄ（
ｉ＋１｜Ｎ），ｉ；ｔ），ｇ（ｍｏｄ（ｉ−１｜Ｎ），
ｉ；ｔ）｝（１≦ｔ≦Ｔ） 得られるデータ：　　π＋　（ｉ），ＣＦ　＋　（ｉ，
ｔ）＝　　｛ｃ＋　（ｉ，ｉ；ｔ），ｃ＋　（ｍｏｄ（
ｉ＋１｜Ｎ），ｉ；ｔ），ｃ＋　（ｍｏｄ（ｉ−１｜Ｎ
），ｉ；ｔ）｝（１≦ｔ≦Ｔ） ＣＦ　＋　（ｉ，ｔ）＝｛ｇ＋　（ｉ，ｉ；ｔ），ｇ＋
　（ｍｏｄ（ｉ＋１｜Ｎ），ｉ；ｔ），ｇ＋　（ｍｏｄ
（ｉ−１｜Ｎ），ｉ；ｔ）｝（１≦ｔ≦Ｔ） （２）　ＰＥ間の循環転送データがβ（ｉ，ｔ）の場合
使用するデータ：｛α（ｉ，０），α（ｉ，１），・・
・，α（ｉ，ｔ），・・・，α（ｉ，Ｔ）｝｛β（ｉ，
０），β（ｉ，１），・・・，β（ｉ，ｔ），・・・，
β（ｉ，Ｔ）｝， ＣＢ　（ｉ，ｔ）＝｛ｃ（ｉ，ｉ；ｔ），ｃ（ｉ，ｍｏ
ｄ（ｉ＋１｜Ｎ）；ｔ），・・・，ｃ（ｉ，ｍｏｄ（ｉ
−１｜Ｎ）；ｔ）｝（１≦ｔ≦Ｔ） ＣＢ　（ｉ，ｔ）＝｛ｇ（ｉ，ｉ；ｔ），ｇ（ｉ，ｍｏ
ｄ（ｉ＋１｜Ｎ）；ｔ），・・・，ｇ（ｉ，ｍｏｄ（ｉ
−１｜Ｎ）；ｔ）｝（１≦ｔ≦Ｔ） 得られるデータ：　　π＋　（ｉ），ＣＢ　＋　（ｉ，
ｔ）＝　　｛ｃ＋　（ｉ，ｉ；ｔ），ｃ＋　（ｍｏｄ（
ｉ＋１｜Ｎ）；ｔ），・・・，ｃ＋　（ｉ，ｍｏｄ（ｉ
−１｜Ｎ）；ｔ）｝（１≦ｔ≦Ｔ） ＣＢ　＋　（ｉ，ｔ）＝｛ｇ＋　（ｉ，ｉ；ｔ），ｇ＋
　（ｉ，ｍｏｄ（ｉ＋１｜Ｎ）；ｔ），・・・，ｇ＋　
（ｉ，ｍｏｄ（ｉ−１｜Ｎ）；ｔ）｝（１≦ｔ≦Ｔ）上
記の各並列処理法に対するデータ分布の整理結果から次
のことがわかる。 【００６２】（１）　フォワード−バックワード・プロ
セデュアの前向きパス・アルゴリズム、後ろ向きパス・
アルゴリスムに対するそれぞれの並列処理により得られ
るデータ分布を合成したものはバウム−ウェルチ・リエ
スティメーション・フォーミュラスの並列処理で使用す
るデータ分布に適している。 【００６３】（２）　フォワード−バックワード・プロ
セデュアの前向きパス・アルゴリズムに対する並列処理
で使用されるデータ列ＣＦ　（ｉ，ｔ）は、ＰＥ間の循
環転送データがα（ｉ，ｔ）の場合のバウムウェルチ・
リエスティメーション・フォーミュラスに対する並列処
理で使用するデータ列ＣＦ　（ｉ，ｔ）に同じである。 【００６４】（３）　フォワード−バックワード・プロ
セデュアの後向きパス・アルゴリズムに対する並列処理
で使用されるデータ列ＣＢ　（ｉ，ｔ）は、ＰＥ間の循
環転送データがβ（ｉ，ｔ）の場合のバウム−ウェルチ
・リエスティメーション・フォーミュラスに対する並列
処理で使用するデータ列ＣＢ　（ｉ，ｔ）に同じである
。 【００６５】（４）　ＰＥ間転送データをα（ｉ，ｔ）
とした場合のバウムウェルチ・リエスティメーション・
フォーミュラスに対する並列処理から得られるデータ列
ＣＦ　＋　（ｉ，ｔ）は、フォワード−バックワード　
　プロセデュアの前向きパス・アルゴリズムの並列処理
に使用されるデータ列ＣＦ　（ｉ，ｔ）と同等であるが
、後ろ向きパス・アルゴリズムの並列処理に使用される
データ列ＣＢ　（ｉ，ｔ）に対しては、これらのデータ
列を構成するデータの（ｘ，ｙ）−インデックスが転置
の関係にある。 【００６６】（５）　ＰＥ間転送データをβ（ｉ，ｔ）
とした場合のバウム−ウェルチ・リエスティメーション
・フォーミュラスに対する並列処理から得られるデータ
列ＣＢ　＋　（ｉ，ｔ）はフォワード−バックワード・
プロセデュアの後ろ向きパス・アルゴリズムの並列処理
に使用されるデータ列ＣＢ　（ｉ，ｔ）と同様であるが
、前向きパス・アルゴリズムの並列処理に使用されるデ
ータ列ＣＦ　（ｉ，ｔ）に対してはこれらのデータ列を
構成するデータの（ｘ，ｙ）−インデックスが転置の関
係にある。 【００６７】上記からバウム−ウェルチ・リエスティメ
ーション・フォーミュラスの並列処理により得られる処
理結果のデータ列はＰＥ間転送データをα（ｉ，ｔ）又
はβ（ｉ，ｔ）のどちらを選択してもフォワード−バッ
クワード・プロセデュアの前向きパス・アルゴリズム又
は、後ろ向きパス・アルゴリズムの処理のどちらか一方
のデータ列と同等になるだけであり、他方の処理を実行
するためには各ＰＥにおいて得られたデータ列のデータ
を再配置する必要がある。その内容は（４）、（５）に
示したように、構成するデータの（ｘ，ｙ）−インデッ
クスが転置関係にあるデータ列ＣＦ　（ｉ，ｔ）（ある
いはＣＦ　＋　（ｉ，ｔ））（１≦ｉ≦Ｎ）とデータＣ
Ｂ　（ｉ，ｔ）（あるいはＣＢ　＋　（ｉ，ｔ））（１
≦ｉ≦Ｎ）との相互変換である。 【００６８】図８は学習処理に必要となるデータの再配
置処理の内容を示す。同図はこの相互変換の内容を示し
ている。同図はすべてのＰＥのメモリに格納されるデー
タ列ＣＦ　（ｉ，ｔ）（あるいはＣＦ　＋　（ｉ，ｔ）
），ＣＢ　（ｉ，ｔ）（あるいはＣＢ　＋　（ｉ，ｔ）
）を構成するデータの（ｘ，ｙ）−インデックスを列挙
する形式で示している。データの時刻ｔに関するインデ
ックスｔはすべてのデータで同一であるので省略してあ
る。データ分布Ｐがデータ列ＣＢ　（ｉ，ｔ）（あるい
はＣＢ　＋　（ｉ，ｔ））を構成するデータから構成さ
れたもので、データ分布Ｑがデータ列ＣＦ　（ｉ，ｔ）
（あるいはＣＦ　＋　（ｉ，ｔ））を構成するデータか
ら構成されたものである。また、ある時刻ｔに対するこ
れらのデータ列のデータは各メモリの連続するアドレス
（図８の例ではアドレスｈ〜アドレス（ｈ＋Ｎ−１）の
範囲）に格納されるものとする。 【００６９】以下図８に沿ってデータの再配置処理法に
ついて説明する。同図に示したデータ分布Ｐ，Ｑをそれ
ぞれ１つの行列と考え、各行列Ｐ，Ｑの同一の要素が保
持されるＰＥ番号と各ＰＥに保持されるデータの順番を
アドレスと考え、この同一の要素のそれぞれのＰＥにお
けるアドレスとの関係について説明する。 【００７０】行列Ｐの要素において、ＰＥｉ（１≦ｉ≦
Ｎ）に保持される要素とそのアドレスとの関係は　　　
　　　アドレス　　　　　　　　　　　　　　　　　　
　　　　　　　　行列Ｐの要素　　　　　　　　ｈ　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　（ｉ，ｉ）　　　　ｈ＋１　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　（
ｉ，ｍｏｄ（ｉ＋１｜Ｎ））　　　　ｈ＋２　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　（ｉ，ｍｏｄ（ｉ＋２｜Ｎ））　　　　　　・　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　・　　　　　　・
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　・　　ｈ＋Ｎ
−１　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　（ｉ，ｍｏｄ（ｉ−１｜Ｎ））である。 【００７１】上記の行列Ｐの要素のインデックスを（ｉ
，ｊ），アドレスをａｄｒ（ＰＥｉ；Ｐ）としてアドレ
スａｄｒ（ＰＥｉ；Ｐ）を要素のｘ−インデックス、ｙ
−インデックスを使って表現することを考える。 ＰＥｉに保持される要素のｙ−インデックスはその値が
Ｎに等しくなるまでは、ｉから順番に１つずつ増加し、
それ以降は１からｉ−１に等しくなるまで１つずつ増加
する。従って、ｉ≦ｊ（≦Ｎ）の場合はこのｙ−インデ
ックス列の何れかに等しい。ｙ−インデックスｉのアド
レスがｈであるので、ｙ−インデックスｊをもつ要素の
アドレスはｊ−ｉ＋ｈと表現できる。一方、ｉ≦ｊ＜ｉ
の場合は、このｙ−インデックスｊは１からｉ−１まで
１つずつ増加するｙ−インデックス列の何れかに等しい
。ｙ−インデックスの値がＮの要素のアドレスは（Ｎ−
ｉ＋ｈ）であるから、ｙ−インデックスの値がＮの要素
のアドレスは（Ｎ−ｉ＋ｈ）であるから、ｙ−インデッ
クスの値が１の要素のアドレスは（Ｎ−ｉ＋ｈ＋１）で
ある。従って、１≦ｊ＜ｉの範囲のｙ−インデックスｊ
を持つ要素のアドレスは（Ｎ−ｉ＋ｈ＋ｊ）で与えられ
る。 【００７２】以上により行列Ｐの要素（ｉ，ｊ）のアド
レスは、 　　　　　　　　　　　　　　　　　　　　ｊ−ｉ＋ｈ
　　　　　　ｆｏｒ　　　　　　　ｉ≦ｊ≦Ｎ　　ａｄ
ｒ（ＰＥｉ；Ｐ）　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　・・・（８）　　　　　　　　　　　　　
　　　　　　　　Ｎ−ｉ＋ｈ＋ｊ　　　　ｆｏｒ　　　
　　　　１≦ｊ＜ｉと表すことができる。 【００７３】次に行列Ｑの要素に対して、上記の行列Ｐ
の要素と同一の要素が保持されるＰＥ番号とそのアドレ
スを求めることにより、行列Ｐ，Ｑの同一要素を保持す
るＰＥ番号の関係及びアドレスの関係を明らかにする。 【００７４】行列Ｑの要素において、ＰＥｉ（１≦ｉ≦
Ｎ）に保持される要素とそのアドレスの関係は　　　　
　　アドレス　　　　　　　　　　　　　　　　　　　
　　　　　　　行列Ｐの要素　　　　　　　　ｈ　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
（ｉ，ｉ）　　　　ｈ＋１　　　　　　　　　　　　　
　　　　　　　　　　　　　　　（ｍｏｄ（ｉ＋１｜Ｎ
），ｉ）　　　　ｈ＋２　　　　　　　　　　　　　　
　　　　　　　　　　　　　　（ｍｏｄ（ｉ＋２｜Ｎ）
，ｉ）　　　　　　・　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　・　　　　　　・　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　・　　ｈ＋Ｎ−１　　　　　　　　　　　
　　　　　　　　　　　　　　　（ｍｏｄ（ｉ−１｜Ｎ
），ｉ）である。 【００７５】上記の関係から、ＰＥ番号はそのＰＥが保
持する要素のｙ−インデックスに等しいので、行列Ｑに
おいて、行列Ｐのｙ−インデックスｊの要素はＰＥｊに
保持されることになる。上記のアドレスと要素との関係
においてｉをｊに置き換えて考えると、このＰＥｊに保
持される要素のｘ−インデックスはｊから始まり、その
値がＮに等しくなるまで、１つずつ増加する。それ以降
は１からｊ−１まで１つずつ増加する。ｊ≦ｉ（≦Ｎ）
の場合は、要素のｘ−インデックスｉはｊからＮまで１
つずつ増加するｘ−インデックス列の何れかに等しいこ
とになるから、ｘ−インデックスｉを持つ要素のアドレ
スはｉ−ｊ＋ｈで与えられる。一方、１≦ｉ＜ｊの場合
は、このインデックスｉは１からｊ−１まで１つずつ増
加するｘ−インデックス列のいずれかに等しい。故に１
≦ｉ＜ｉの範囲のｘ−インデックスｉをもつ要素のアド
レスはＮ−ｊ＋ｈ＋ｉで表される。 【００７６】従って、行列Ｑの要素（ｉ，ｊ）のアドレ
スａｄｒ（ＰＥｊ；Ｑ）は 　　　　　　　　　　　　　　　　　　　　ｉ−ｊ＋ｈ
　　　　　　ｆｏｒ　　　　　　　ｊ≦ｉ≦Ｎ　　ａｄ
ｒ（ＰＥｉ；Ｐ）　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　・・・（８）　　　　　　　　　　　　　
　　　　　　　　Ｎ−ｊ＋ｈ＋ｉ　　　　ｆｏｒ　　　
　　　　１≦ｉ＜ｊと表すことができる。 【００７７】以上の結果を整理すると、（８）　式及び
（９）　式から行列Ｐ，Ｑの同一要素（ｉ，ｊ）に対し
て、この要素を保持するＰＥ番号とそのＰＥにおけるア
ドレスの関係は以下の表１のように整理することができ
る。 【００７８】 【表１】次に、この表１の結果を用いて、行列Ｐ→行列
Ｑ，または、行列Ｑ→行列Ｐの要素の再配置方法を明ら
かにする。 【００７９】表一からわかるように、要素（ｉ，ｊ）が
保持されるＰＥ番号及びアドレスは、その要素のｘ−イ
ンデックス、ｙ−インデックスの大小関係によって分け
て考えなければならない。行列Ｐの要素のインデックス
の大小関係とアドレスとの関係について説明する。図９
は要素のインデックス差と再配置前アドレス、再配置先
アドレスＰＥ間距離との関係を示すグラフである。同図
は要素のｘ，ｙ−インデックス差（ｊ−ｉ）と再配置前
アドレスＫ，再配置先アドレスＫ’，ＰＥ間距離Ｌとの
関係を示している。横軸は要素のインデックスの差（ｊ
−ｉ）であり、縦軸は要素のアドレスである。８１は再
配置前アドレスＫ，８２は再配置先アドレスＫ，８３は
ＰＥ間距離Ｌである。要素のインデックスｉ，ｊの大小
関係から決められる（ｊ−ｉ）の定義域は｛−（Ｎ−１
），−１｝，｛０｝、｛１、（Ｎ−１）｝の３種類に分
けられる。但し、（ｊ−ｉ）は上記の範囲の整数とする
。この３種類の定義域に存在する要素の再配置処理の条
件を以下に示す。 【００８０】（１）ｉ＝ｊの場合； 行列Ｐの要素（ｉ，ｊ）が保持されるＰＥ番号はｉ，そ
のアドレスはｈである。一方、行列Ｑの要素（ｉ，ｊ）
が保持されるＰＥ番号はｉ（ｊ＝ｉより）であり、その
アドレスはｈである。即ち、行列でＰ，Ｑのアドレスｈ
の要素は同一番号のＰＥに保持されるので、再配置処理
の必要はない。 【００８１】（２）　ｉ＜ｊの場合； 行列Ｐの要素（ｉ，ｊ）は、ＰＥｉのアドレス（ｊ−ｉ
＋ｈ）に保持される。一方、行列Ｑの要素（ｉ，ｊ）は
ＰＥｊのアドレス｛Ｎ−（Ｊ−１）＋ｈ｝に保持される
。従って、この定義域の要素に対する行列Ｐ→行列Ｑの
再配置処理では、ＰＥｉのアドレス（ｊ−ｉ＋ｈ）の要
素をＰＥｊのアドレス｛Ｎ−（ｊ−ｉ）＋ｈ｝に再配置
しなければならない。 【００８２】（３）　ｉ＞ｊの場合； 行列Ｐの要素（ｉ，ｊ）はＰＥｉのアドレス｛Ｎ−（ｉ
−ｊ）＋ｈ｝に保持される。一方、行列Ｑの要素（ｉ，
ｊ）はＰＥｊのアドレス（ｉ−ｊ＋ｈ）に保持される。 従って、この定義域の要素に対する行列Ｐ→行列Ｑの再
配置処理では、ＰＥｉのアドレス｛Ｎ−（ｉ−ｊ）＋ｈ
｝の要素をＰＥｊのアドレス（ｉ−ｋ＋ｈ）に再配置し
なければならない。 【００８３】これらの再配置条件から、データの再配置
処理には、ＰＥ番号の変換と各要素が保持されるアドレ
スの変換とが必要である。従って、リングアレイプロセ
ッサ構成では、（再配置前のアドレスから要素を取り出
す）→（この要素を再配置先のＰＥへ転送する）→（転
送された要素を再配置先のアドレスに格納する）の手順
でデータの再配置処理を実行しなければならない。この
手順の中の要素の再配置先のＰＥへの転送は各再配置条
件毎に異なるので、その内容を以下に述べる。ここで、
ｉ＝ｊの場合は上記の結果から再配置処理は必要としな
いため、ｉ≠ｊの場合のみ考える。また、再配置処理の
ＰＥ間データ転送において経由するＰＥの個数をＰＥ間
距離Ｌと定義する。 【００８４】（１）　ｉ＜ｊの場合； リングアレイプロセッサ構成上でのデータ転送方向はＰ
Ｅ番号の大→小であるから、ＰＥｉ→ＰＥｊのデータ転
送は、 ＰＥｉ→　　ＰＥ１→　　ＰＥＮ→　　ＰＥｊの経路で
実行しなければならない。従って、ＰＥ間距離Ｌは、Ｐ
Ｅｉ→　　ＰＥ１が（ｉ−１），ＰＥ１→ＰＥＮが１，
ＰＥＮ→ＰＥｊが（Ｎ−ｊ）であるから、Ｌ＝（ｉ−１
）＋１＋（Ｎ−ｊ）＝Ｎ−（ｊ−ｉ）である。 【００８５】（２）　ｉ＞ｊの場合；データ転送はＰＥ
ｉ→　　ＰＥｊで実行できるので、ＰＥ間距離ＬはＬ＝
ｉ−ｊ である。 【００８６】以上の結果をまとめ、ＰＥ間距離Ｌ，再配
置再アドレスＫ’と要素のインデックス差（ｊ−ｉ）と
の関係を先の図９のグラフにより次のことが分かる。 【００８７】（１）　要素群｛（ｉ，ｊ）｜ｊ−ｉ＝ｋ
｝と要素群｛（ｉ，ｊ）｜ｊ−ｉ＝ｋ−Ｎ｝のアドレス
は同一で、その値はｋ＋ｈ（１≦ｋ≦Ｎ−１）である。 【００８８】このアドレス（ｋ＋ｈ）に保持される要素
群のｘ，ｙ−インデックスの関係について説明する。図
１０はアドレスに保持される要素群のｘ−インデックス
とｙ−インデックスの関係を示す。要素群｛（ｉ，ｊ）
｜ｊ−ｉ＝ｋ｝は同図中、ｊ−切片がｋの直線９０上の
格子点に対応し、要素群｛（ｉ，ｊ）｜ｊ−ｉ＝ｋ−Ｎ
｝はｉ−切片がＮ−ｋの直線９１上の格子点に対応する
。それぞれの直線上の格子点の個数はｉ，ｊの定義域１
≦ｉ，ｊ≦Ｎから、前者は（Ｎ−ｋ）個、後者はｋ個で
ある。従って、同一アドレス（ｋ＋ｈ）に存在する要素
の個数はＮ個である。これはｋのすべての場合に対して
成立し、それぞれのｋに対する要素は互いに排反である
。 【００８９】即ち、要素群｛（ｉ，ｊ）｜ｊ−ｉ＝ｋ，
ｊ−ｉ＝ｋ−Ｎ｝の要素はＮ個存在し、これらは１個ず
つＮ個のＰＥに保持され、そのアドレスは（ｋ＋ｈ）で
ある。 【００９０】（２）　同一アドレス値（ｋ＋ｈ）をもつ
要素群のＰＥ間距離ＬはＮ−ｋである。即ち、同一アド
レスの要素のＰＥ間の転送回数は等しい。従って、各Ｐ
Ｅの同一アドレスの要素はリングアレイプロセッサ構成
上で並列データ転送が可能である。 【００９１】（３）　同一アドレス値（ｋ＋ｈ）をもつ
要素群の再配置先アドレスＫ’はその要素群のＰＥ間距
離Ｌにｈを加算した値、即ち、（Ｎ−ｋ＋ｈ）に等しい
。従って、（２）　に示した並列データ転送の対象とな
る要素群はそのＰＥ間データ転送回数の値にｈを加算し
たアドレス（Ｎ−ｋ＋ｈ）に配置すればよい。 【００９２】上記の内容の（１）　〜（２）　より、デ
ータ再配置処理は次のような並列データ転送処理で実行
できる。 アドレス（ｋ＋ｈ）の要素群に対しては（Ｎ−ｋ）回の
ＰＥ間転送を行い、アドレス（Ｎ−ｋ＋ｈ）に配置する
。また、アドレス（Ｎ−ｋ＋ｈ）の要素群に対してはｋ
回のＰＥ間転送を行い、アドレス（ｋ＋ｈ）に配置する
。即ち、ＰＥ間での並列データ転送を行いながら、アド
レス（ｋ＋ｈ）の要素群とアドレス（Ｎ−ｋ＋ｈ）の要
素群とを交換する処理である。再配置処理の対象となる
要素群のアドレス（ｋ＋ｈ）とＰＥ数Ｎの値によりＰＥ
間転送回数及び再配置先アドレスが決定されるので、各
ＰＥはＰＥ間の転送回数、再配置先アドレスを全く同一
の制御により実現できる。 【００９３】これまでの説明は行列Ｐ→行列Ｑの再配置
処理を例に述べてきたが、行列Ｑ→行列Ｐの再配置処理
の場合についても全く同一である。 【００９４】これまでの説明をまとめ、要素群の再配置
処理の並列処理方法を以下に示す。 （Ｄ）　　再配置処理の並列処理方法 Ｎ個のＰＥからなるリングアレイプロセッサ構成におい
て、（但し、データ転送方向はすべてのＰＥｉ（１≦ｉ
≦Ｎ）に対して ＰＥｉ→ＰＥ（ｍｏｄ（ｉ−１｜Ｎ））である。ここで
、ｍｏｄ（ｍ｜Ｎ）はｍがＮの整数倍であればＮ，ｍが
Ｎの整数倍でなければｍをＮで割ったときの剰余を表す
） ステップ１； ｒ＝１，２，・・・，［Ｎ／２］に対してステップ２〜
ステップ７を実行する。（ｒは繰り返し数）ここで［ｘ
］はｘを越えない最大整数を表す。 ステップ２；全てのＰＥｉ（１≦ｉ≦Ｎ）において、ア
ドレス（ｒ＋ｈ）の要素を取り出す。 ステップ３；全てのＰＥｉ（１≦ｉ≦Ｎ）において、取
り出された要素を次段のＰＥに送信すると同時に、前段
ＰＥから取り出された要素を受信する。このようなデー
タ電送を（Ｎ−ｒ）回繰り返す。 ステップ４；Ｎが偶数、かつｒ＝［Ｎ／２］のとき、す
べてのＰＥｉ（１≦ｉ≦Ｎ）において、転送されてきた
要素をアドレス（Ｎ−ｒ＋ｈ）に格納し、処理を終了す
る。 ステップ５；全てのＰＥｉ（１≦ｉ≦Ｎ）において、ア
ドレス（Ｎ−ｒ＋ｈ）の要素を取り出すと共に、転送さ
れてきた要素をアドレス（Ｎ−ｒ＋ｈ）に格納する。 ステップ６；全てのＰＥｉ（１≦ｉ≦Ｎ）において、ア
ドレス（Ｎ−ｒ＋ｈ）から取り出された要素を次段ＰＥ
へ送信すると同時に、前段ＰＥから取り出された要素を
受信する。このようなデータ転送をｒ回繰り返す。 ステップ７；全てのＰＥｉ（１≦ｉ≦Ｎ）において、転
送されてきた要素をアドレス（ｒ＋ｈ）に格納する。 【００９５】この並列処理方法ではステップ１の繰り返
し処理回数は［Ｎ／２］で規定されることから、Ｎが偶
数の場合に対してステップ４の特殊な処理を設けている
。これは、次の理由からである。 【００９６】Ｎが奇数の場合は［Ｎ／２］は（Ｎ−１）
／２に等しいので、ステップ２で取り出される要素のア
ドレスは｛ｈ＋１，ｈ＋２，・・・，ｈ＋（Ｎ−１）／
２｝である。また、これらのアドレスの要素が格納され
るアドレスは｛ｈ＋（Ｎ−１），ｈ＋（Ｎ−２），・・
・・・，ｈ＋（Ｎ＋１）／２｝である。一方、ステップ
５で取り出される要素のアドレスは｛ｈ＋（Ｎ−１），
ｈ＋（Ｎ−２），・・・・・，ｈ＋（Ｎ＋１）／２｝で
あり、格納されるアドレスは｛ｈ＋１，ｈ＋２，・・・
，ｈ＋（Ｎ−１）／２｝である。従って、ステップ１〜
ステップ７の処理は互いに重複することなく実行できる
。 【００９７】Ｎが偶数の場合は［Ｎ／２］はＮ／２に等
しいので、ステップ２で取り出される要素のアドレスは
｛ｈ＋１，ｈ＋２，・・・，ｈ＋Ｎ／２｝である。また
、これらのアドレスの要素が格納されるアドレスは｛ｈ
＋（Ｎ−１），ｈ＋（Ｎ−２），・・・・・，ｈ＋Ｎ／
２｝である。ステップ４のステップがないとすると、ス
テップ５で取り出される要素のアドレスは｛ｈ＋（Ｎ−
１），ｈ＋（Ｎ−２），・・・・・，ｈ＋Ｎ／２｝であ
り、格納されるアドレスは｛ｈ＋１，ｈ＋２，・・・，
ｈ＋Ｎ／２｝である。このためアドレスＮ／２の要素の
再配置処理に伴うデータ転送処理は重複して実行される
。従って、ステップ４のステップを設けておけば、ステ
ップ２〜ステップ４の処理によってアドレスＮ／２の要
素の再配置が完了し、このアドレスの要素に対する再配
置処理が重複することなく、無駄な処理ステップを削減
することができる。 【００９８】［Ｄ−１］　　Ｎが偶数の場合における再
配置処理の並列処理方法 次にＮが偶数の場合について説明する。Ｎ＝６（偶数）
の場合の再配置処理例に対して、再配置処理前のデータ
分布、データ再配置の並列処理過程及び再配置処理後の
データ分布について説明する。図１１は再配置処理前の
各ＰＥのデータ分布を示す。また、図１２は本発明の一
実施例の再配置処理過程を示す。図１３は本発明の一実
施例の再配置処理後の各ＰＥデータ分布を示す。図１１
の例では、ＰＥに割り付けられた要素のｘ−インデック
スはＰＥ番号に等しい。先に述べた再配置処理の並列処
理方法に従って、図１２に示した並列処理過程を図１３
と共に説明する。 【００９９】図１２におけるステップ１では先ず、アド
レス（ｈ＋１）の要素をすべてのＰＥで取り出す。取り
出された全ての要素に対するＰＥ間転送回数はＮ−１＝
６−１＝５であるから、ステップ２〜ステップ６はこれ
らの要素をＰＥ間で循環転送している過程を示している
。 【０１００】そして、ステップ６はこれらの要素に対す
る再配置先のＰＥへの転送が完了する。 【０１０１】ステップ７では、これらの転送された要素
は、再配置先のアドレスの要素と交換する形式で格納さ
れる。即ち、再配置先のアドレス（ｈ＋５）の要素を取
り出し、このアドレス（ｈ＋５）に転送された要素を格
納する。 【０１０２】ステップ８では、交換する形式で取り出さ
れたアドレス（ｈ＋５）の要素を、転送回数Ｎ−５＝６
−５＝１だけＰＥ間で転送し、再配置先のＰＥへの転送
を完了する。 【０１０３】ステップ９ではこれらの要素は再配置先ア
ドレス（ｈ＋１）に格納される。このとき、アドレス（
ｈ＋１）の要素はすでに再配置されているので、転送さ
れてきた要素をそのままこのアドレス（ｈ＋１）に格納
する。 【０１０４】以上のように、ステップ１〜ステップ９に
おいて、ＰＥ間の循環データ転送を介して、アドレス（
ｈ＋１）の要素とアドレス（ｈ＋５）の要素との交換が
完了する。ステップ９では、さらに、次の交換の処理の
対象となるアドレス（ｈ＋２）の要素が取り出される。 そして、これらの要素はステップ１０〜ステップ１３に
示すように、Ｎ−２＝６−２＝４回のＰＥ間での循環デ
ータ転送を経て、再配置先のＰＥに配置され、アドレス
（ｈ＋４）に格納される。また、このとき、アドレス（
ｈ＋４）に格納されていた要素が取り出される。この様
子を示しているのがステップ１４である。 【０１０５】ステップ１５からステップ１６ではこのア
ドレス（ｈ＋４）の要素はＮ−４＝６−４＝２回のＰＥ
間循環転送を経て、再配置先ＰＥへ配置され、そのＰＥ
のアドレス（ｈ＋２）に格納される。 【０１０６】アドレス（ｈ＋３）の要素に対しては、再
配置先のアドレスが（ｈ＋３）であるので、このアドレ
スから取り出した要素はＮ−３＝６−３＝３回のＰＥ間
循環データ転送を経て、再配置先のＰＥに配置され、取
り出しアドレスと同じアドレス（ｈ＋３）に格納される
。これらの処理過程を示しているのがステップ１８〜ス
テップ２１であり、このステップ２１で全ての再配置処
理が完了する。 【０１０７】図１３のデータ分布は図１２による再配置
処理過程を経て得られた再配置処理後のものである。こ
の分布では各アドレスの要素に対するインデックスに対
して転置の関係になっている。再配置処理が正常に実行
されたことを示している。 【０１０８】［Ｄ−２］　　Ｎが奇数の場合における再
配置処理の並列処理方法 次にＮが奇数の場合について説明する。Ｎ＝５（奇数）
の場合の再配置処理例に対して、再配置処理前のデータ
分布、データ再配置の並列処理過程及び再配置処理後の
データ分布について説明する。図１４は再配置処理前の
各ＰＥのデータ分布を示す。また、図１５は本発明の他
の実施例の再配置処理過程を示す。図１６は本発明の一
実施例の再配置処理後の各ＰＥデータ分布を示す。Ｎが
偶数の場合と全く同様の処理過程で再配置処理が実行で
きる。図１５のステップ１〜ステップ６はＮ−１＝５−
１＝４回のＰＥ間循環データ転送を経て、アドレス（ｈ
＋１）の要素がアドレス（ｈ＋４）に再配置される。 【０１０９】また、ステップ６〜ステップ８ではＮ−１
＝５−４＝１回のＰＥ間循環データ転送を経て、アドレ
ス（ｈ＋４）の要素がアドレス（ｈ＋１）に再配置され
る。これにより、アドレス（ｈ＋１）の要素とアドレス
（ｈ＋４）の要素に関する再配置処理が完了する。以後
、ステップ８以降についても、ＰＥ間循環データ転送を
介したアドレス（ｈ＋２）の要素とアドレス（ｈ＋３）
の要素との交換が行われ、ステップ１５において、全て
の要素に対する再配置処理が完了する。 【０１１０】図１４、図１６から、再配置処理後のデー
タ分布を比較すると、ＰＥの各アドレスの要素に対する
インデックスは互いに転置の関係になっており、再配置
処理が終了したことがわかる。 【０１１１】 （Ｅ）再配置処理の並列処理方法における処理時間［Ｅ
−１］　　　　総処理時間 次に上記の並列処理方法を用いて再配置処理を実行した
場合の処理時間を見積もる。先ず、データ転送に要する
処理時間を、ＰＥ間のデータ転送回数の総和から見積も
る。各ＰＥの同一アドレスの要素は、全て、ＰＥ間のデ
ータ転送回数が同一で、且つ、リングアレイプロセッサ
の構成上のＰＥ間で並列転送が可能である。 【０１１２】上記の並列処理方法では、Ｎの偶数、奇数
のそれぞれの場合に対する問題に対処してあるので、総
転送回数は１つのＰＥの各アドレスの要素の転送回数の
総和をとることにより求められる。 【０１１３】アドレス（ｈ＋ｒ）のＰＥ間データ転送回
数は（Ｎ−ｒ）であるから、転送回数の総和をＴｔｒと
すると、 【０１１４】 【数９】である。 【０１１５】従って、１回当たりのデータ転送時間をＳ
（ｔｒ）　とすると、ＰＥ間データ転送に要する総処理
時間Ｓ（ｔｒ−ａｌｌ）　は（１０）式を用いて、　　
Ｓ（ｔｒ−ａｌｌ）　＝（１／２）・Ｎ・（Ｎ−１）・
Ｓ（ｔｒ）　　　　　　・・・（１１）で表される。 【０１１６】 ［Ｅ−２］　　要素の取り出し及び、再格納処理時間次
に各ＰＥに格納されている要素の取り出し、及び再格納
に要する処理時間を見積もる。１つの要素を取り出すの
に要する時間をＳ（Ｒ），格納するのに要する時間をＳ
（Ｗ）　とする。上記の並列処理方法では、各ＰＥの同
一のアドレスの要素は同時に取り出され、リングアレイ
プロセッサ構成上で並列にＰＥ間データ転送された後、
同時に再配置先のアドレスに格納される。すなわち、要
素の取り出し、または、再格納の回数は１つのＰＥにお
ける回数を考えればよく、その回数は再配置の対象にな
るアドレスの個数に等しいから（Ｎ−１）回（アドレス
０の要素は再配置処理の必要がないので、再配置処理が
必要となる要素は（Ｎ−１）個）である。従って、各Ｐ
Ｅでの要素取り出し、再格納に要する総処理時間Ｓ（Ｒ
／Ｗ）　は、　　 　　Ｓ（Ｒ／Ｗ）　＝（Ｎ−１）・｛Ｓ（Ｒ）　＋Ｓ（
Ｗ）　｝　　　　　　　　　　　　　　　　・・・（１
２）で表される。 【０１１７】（１１）、（１２）式より、再配置処理に
要する総処理時間Ｓ（ａｒｎｇ）は、 　　Ｓ（ａｒｎｇ）　　＝Ｓ（ｔｒ−ａｌｌ）　＋Ｓ（
Ｒ／Ｗ）　　　　　　　　　　　　　＝（１／２）・Ｎ
・（Ｎ−１）・Ｓ（ｔｒ）　＋（Ｎ−１）　　　　　　
　　　　　　　　　　・｛Ｓ（Ｒ）　＋Ｓ　（Ｗ）｝　
　　　　　　　　　　　＝（Ｎ−１）・｛（１／２）・
Ｎ・Ｓ（ｔｒ）＋Ｓ（Ｒ）　＋Ｓ（Ｗ）　｝　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　・・・（１３）となる。 【０１１８】（１３）式の｛　　｝の第２、第３の項は
第１項に比べて無視できるとする（第１項はＮに比例、
第２、第３はＮに関係なく一定）と、総処理時間Ｓ（ａ
ｒｎｇ）は、　　　　Ｓ（ａｒｎｇ）　　≒（１／２）
・Ｎ・（Ｎ−１）・Ｓ（ｔｒ）　　　　　　　　・・・
（１４）と近似できる。すなわち、総処理時間Ｓ（ａｒ
ｎｇ）はＰＥ間データ転送に要する処理時間に支配され
る。従って、Ｎ（ＰＥ数）の偶数、奇数に関係なく、再
配置処理はＯ（Ｎ２　／２）の処理時間で実行できる。 【０１１９】 （Ｆ）　　並列処理方法による再配置処理の制御方法上
記の並列処理方法を用いて再配置処理を実行する場合の
制御方法について説明する。上記の並列処理方法におい
て、並列にＰＥ間データ転送される要素は全て同一アド
レスの要素であり、その転送回数も同一であることから
、あるアドレスから要素を取り出す場合のアドレス設定
、転送回数のカウント、再格納時のアドレスの設定は、
どのＰＥでも全く同じである。従って、この再配置処理
は個々のＰＥで全く同一の制御を行うことによって実現
できる。 【０１２０】図１７は本発明のデータの再配置処理の制
御フローチャートを示す。このフローチャートは上記の
再配置処理の並列処理方法に対応するものである。本発
明の再配置処理の制御方法の特徴は互いに交換の対象と
なる要素のアドレス値をＰＥ間データ転送の転送回数の
カウントに用いる点である。以下図１７に従って先に説
明した再配置処理の並列処理過程との関係を明確にしな
がら説明する。 【０１２１】ステップ１１０；要素取り出しアドレス／
再格納アドレス用のカウンタＣＡ，ＣＢに初期値を設定
する。初期値としては、カウンタＣＡには“ｈ＋１”、
カウンタＣＢには“ｈ＋Ｎ−１”を設定する。この２つ
のカウンタＣＡ，ＣＢに設定されたアドレス値は再配置
処理の並列処理において、互いにその要素を交換する対
象のアドレスである。また、ループ回数を指定するパラ
メータＢＲ１には［Ｎ／２］＋ｈを設定し、Ｎの偶数・
奇数の判定用のパラメータＢＲ２にはＮを設定する。 【０１２２】ステップ１１１；全てのＰＥにおいて、同
時にカウンタＣＡで示されるアドレスの要素を取り出す
と共に、再格納アドレスを示すカウンタＣＢの内容を転
送回数をカウントするカウンタＣＴにロードする。 【０１２３】ステップ１１２；全てのＰＥにおいて、取
り出された要素を次段のＰＥへ送信すると同時に前段Ｐ
Ｅからの要素を受信する。このとき、すべてのＰＥにお
いて、カウンタＣＴをデクリメントする。 【０１２４】ステップ１１３；カウンタＣＴの値が“ｈ
”になるまで、ＰＥ間での要素の転送とカウンタＣＴの
デクリメント（ステップ１１２）を繰り返す。カウンタ
ＣＴの値が“ｈ”になったら、転送された要素は再配置
先のＰＥに存在するから、ＰＥ間データ転送を終了し、
その転送されてきた要素をカウンタＣＢで示されるアド
レスに格納する。 【０１２５】ステップ１１４；カウンタＣＴの値が“ｈ
”のとき、転送された要素は再配置先のＰＥに存在する
から、ＰＥ間のデータ転送を終了し、その転送されてき
は要素をカウンタＣＢで示されるアドレスに格納する。 このとき、カウンタＣＢで示されるアドレスには再配置
処理前の別の要素が格納されているため、転送されてき
た要素をこのカウンタＣＢで示されるアドレスに格納す
る。また、パラメータＢＲ２が偶数であり、且つカウン
タＣＡがパラメータＢＲ１であれば、処理を終了する。 【０１２６】ステップ１１５；カウンタＣＡの内容をカ
ウンタＣＴにロードする。そして、すべてのＰＥにおい
て、カウンタＣＢで示されるアドレスから取り出された
要素を次段のＰＥへ送信すると同時に、前段のＰＥから
の要素を受信する。 【０１２７】ステップ１１６；すべてのＰＥにおいて、
カウンタＣＴをデクリメントする。 【０１２８】ステップ１１７；このような処理をカウン
タＣＴの値が“ｈ”になるまで繰り返す。 【０１２９】ステップ１１８；カウンタＣＴの値が“ｈ
”になったら、転送されてきた要素をカウンタＣＡの示
すアドレスに格納する。カウンタＣＡの示すアドレスの
要素はすでに再配置処理されているから、転送された要
素はそのままカウンタＣＡの示すアドレスに格納する。 このとき、カウンタＣＡがパラメータＢＲ１と等しくな
ったら終了する。 【０１３０】ステップ１１９；このようなある２つのア
ドレスの要素の再配置処理が互いの要素の交換の形式で
終了すると、カウンタＣＡはインクリメント、カウンタ
ＣＢはデクリメントする。そして、上記と同様の過程に
よって、カウンタＣＡ，カウンタＣＢで示されるアドレ
スの要素をＰＥ間データ転送を介して再配置する。 【０１３１】上記のように、２つのアドレスの要素を互
いに交換して再配置する処理を、カウンタＣＡの値が“
［Ｎ／２］＋ｈ”に一致するまで繰り返す（ステップ１
１４、ステップ１１８）。この制御フローチャートでは
カウンタＣＡの値がこの“［Ｎ／２］＋ｈ”に一致した
か否かの判定（ステップ１１４、ステップ１１８）はカ
ウンタＣＡの値とパラメータＢＲ１の内容“［Ｎ／２］
＋ｈ”との一致検出により行う。尚、パラメータＢＲ１
の内容は、再配置処理開始時に設定する（ステップ１１
０）。Ｎが偶数の場合には、アドレス（［Ｎ／２］＋ｈ
）の要素の再配置は２つのアドレスの要素を交換する形
式にはならないので、ＰＥ間データ転送によって再配置
先のＰＥに転送された後、同じアドレスに直接再格納す
る。このＰＥの総個数Ｎが偶数であるか奇数であるかの
判定（ステップ１１４）は、パラメータＢＲ２の内容“
Ｎ”によって判定する。このＢＲ２の内容も再配置処理
開始時に設定する（ステップ１１０）。 【０１３２】これまで説明してきたように、ＰＥ間での
並列データ転送を介した２つのアドレスの要素の交換を
基本とした規則的な処理によって、再配置処理が完了す
る。この制御方法はカウンタＣＡ、カウンタＣＢは要素
の取り出し／再格納アドレスを与える働きをするばかり
でなく、それぞれ、カウンタＣＢの示すアドレスの要素
、カウンタＣＡの示すアドレスの要素に対するＰＥ間デ
ータ転送回数を与える働きもしている。 【０１３３】（Ｇ）　　並列処理方法による再配置処理
の制御ハードウェア構成 （Ｆ）で示したような制御方法を実現する制御ハードウ
ェア構成について説明する。図１８は本発明のデータの
再配置処理の制御ハードウェアの構成図を示す。同図に
おいて、インクリメンタＣＡ１２０　，デクリメンタＣ
Ｂ１２１　，デクリメンタＣＴ１２４　，レジスタＢＲ
１１２２　，レジスタＢＲ２１２３　はそれぞれ、図１
６に示したカウンタＣＡ，カウンタＣＢ，カウンタＣＴ
に対応し、レジスタＢＲ１１２２　は図１７で転送を繰
り返すカウントであるループ回数の制御パラメータを指
定するＢＲ１に対応し、レジスタＢＲ２１２３　はＮの
偶数、奇数の判定用のパラメータを指定するＢＲ２に対
応する。 【０１３４】セレクタ１２７　はインクリメンタＣＡ１
２０，デクリメンタＣＢ１２１　の出力を切り換えてデ
クリメンタＣＴ１２４　にロードするためのものである
。 【０１３５】フラグ生成回路１２５　はＰＥ間の並列デ
ータ転送の終了はデクリメンタＣＴ１２４　の値が“ｈ
”であることを検出してそのフラグ（以後このフラグを
“ｈ”−フラグと呼ぶ）を生成する回路である。また、
この“ｈ”−フラグはデクリメンタＣＴ１２４　へのデ
ータロード元を切り換える制御信号として用いる。即ち
この“ｈ”−フラグがオンになる毎に、セレクタ１２７
　はデータロード元のインクリメンタＣＡ１２０　また
はデクリメンタＣＢ１２１　を切り換える。 【０１３６】レジスタＢＲ２１２３　にはＮを設定する
。Ｎの偶数、奇数についてはこのレジスタＢＲ２１２３
　のＬＳＢ（最下位ビット）の値が“０”又は、“１”
によって判定する。即ち、“０”ならば偶数、“１”な
らば奇数と判定する。また、［Ｎ／２］＋ｈとインクリ
メンタＣＡ１２０　の値との一致によって制御する。こ
れは、上記の制御方法にも示したように、インクリメン
タＣＡ１２０　は、“ｈ＋１”から“［Ｎ／２］＋ｈ”
までインクリメントするので、このインクリメンタＣＡ
１２０　の値とレジスタＢＲ１１２２　の内容との一致
を検出することは実行的に［Ｎ／２］の回数をカウント
するのに等価である。 【０１３７】このため、本制御ハードウェア構成には、
インクリメンタＣＡ１２０　の値とレジスタＢＲ１１２
２　の内容との一致を検出する一致検出回路１２６　を
設けている。 【０１３８】再配置処理の終了はこの一致検出回路１２
６　から出力される一致フラグの内容によって判定する
。なお、再配置処理の終了条件にはＮの偶奇性が関係す
るので、、レジスタＢＲ２１２３　のＬＳＢはこの一致
検出回路１２６　に入力されている。 【０１３９】これにより、インクリメンタＣＡ１２０　
、デクリメンタＣＢ１２１　、デクリメンタＣＴ１２４
　とレジスタＢＲ１１２２　の特定の値を検出すること
により（Ｆ）で示したような制御方法が実現できる。 【０１４０】 【発明の効果】上記のように本発明のデータの再配置処
理方法によれば、複数（Ｎ）個の処理要素を一括して同
時に再配置できるので、要素を１個ずつ再配置する場合
に比べて再配置処理をＮ倍高速化できる。また、本発明
は２つのアドレスの要素を交換する形式で再配置処理を
行う方法であるので、規則的また、効率的な処理が実現
できる。 【０１４１】また、本発明の再配置処理の制御方法によ
れば、要素のアドレス値を単に取り出しアドレス及び再
格納アドレスとして用いるだけでなく、ＰＥ間データ転
送により要素を再配置先のＰＥへ転送する場合の転送回
数のカウントにも用いた二重のＤＯループ処理の構造を
もった制御方法であるので、再配置処理の制御を規則的
、効率的に実現できる。さらに、各ＰＥは全く同一の制
御を実行し、各々のＰＥの制御状態を互いに管理するこ
となく、また、リングアレイプロセッサ構成の各ＰＥを
個別に制御するような複雑な制御構成をとることがない
ので制御が簡単になる。 【０１４２】また、本発明の制御ハードウェアの構成に
よれば、上記の二重のＤＯループ構造の制御を３種類の
カウンタとカウンタの特定の値を検出して、そのフラグ
を生成する２種類の検出回路を用いて実現できるため、
ハードウェア構成が簡素化でき、ハードウェアの規模も
小さくできる。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】パターン認識における学習処理を並列処理によ
り実行する場合のリングアレイプロセッサの構成図であ
る。

【図３】リングアレイプロセッサ構成を用いた前向きパ
ス・アルゴリズムの並列処理を示す図である。（フォワ
ード−バックワード・プロセデュア）

【図４】リングアレイプロセッサ構成を用いた後ろ向き
パス・アルゴリズムの並列処理を示す図である。（フォ
ワード−バックワード・プロセデュア）

【図５】リング
アレイプロセッサ構成を用いた初期状態確率の再推定計
算の並列処理を説明するための図である。（バウム−ウ
ェルチ・リエスティメーション・フォーミュラス）

【図６】バウム−ウェルチ・リエスティメーション・フ
ォーミュラスの状態遷移確率の再推定計算をリングアレ
イプロセッサ構成で並列処理する場合のデータフローで
ある。

【図７】学習処理におけるバウム−ウェルチ・リエステ
ィメーション・フォーミュラスのシンボル出力確率の再
推定計算をリングアレイ構成で並列処理する場合のデー
タフローである。

【図８】学習処理に必要となるデータの再配置処理の内
容を示す図である。

【図９】要素のインデックス差と再配置前アドレス、再
配置先アドレス、ＰＥ間距離との関係を示す図である。

【図１０】アドレスに保持される要素群のｘ−インデッ
クスとｙ−インデックスの関係を示す図である。

【図１１】再配置処理前の各ＰＥのデータ分布を示す図
である。

【図１２】本発明の一実施例の再配置処理過程を示す図
である。

【図１３】本発明の一実施例の再配置処理後の各ＰＥの
データ分布を示す図である。

【図１４】再配置処理前の各ＰＥのデータ分布を示す図
である。

【図１５】本発明の他の実施例の再配置処理過程を示す
図である。

【図１６】本発明の他の実施例の再配置処理後の各ＰＥ
のデータ分布を示す図である。

【図１７】本発明のデータの再配置処理の制御フローチ
ャートである。

【図１８】本発明のデータの再配置処理の制御ハードウ
ェアの構成図である。

【符号の説明】

１２０　　インクリメンタＣＡ １２１　　デクリメンタＣＢ １２２　　レジスタＢＲ１ １２３　　レジスタＢＲ２ １２４　　デクリメンタＣＴ １２５　　フラグ生成回路 １２６　　一致検出回路 １２７　　セレクタ

Claims (3)

【特許請求の範囲】
1. 【請求項１】　　複数の処理要素を環状に接続したマル
   チプロセッサシステムにおいて、複数の前記処理要素は
   各々データ授受を行うためのデータ転送パスを介して前
   記処理要素と接続され、前記複数の処理要素は所望の演
   算を行う演算手段、前記処理要素間のデータを転送する
   データ転送手段、アドレス及びデータを記憶する記憶手
   段及び、記憶したデータを読み出す読み出し手段に対し
   て制御を行う制御手段を有し、前記複数の処理要素に対
   して前記処理要素が前記マルチプロセッサに配列されて
   いる順番に番号が付与され、全ての前記処理要素におい
   て、前記記憶手段の第１のアドレスから前記読み出し手
   段によりデータを読み出し、読み出した前記データを前
   記処理要素間で所定の回数転送し、前記各処理要素に転
   送されてきた前記記憶手段の第１のアドレスのデータを
   前記第２のアドレスのデータと交換して前記記憶手段に
   格納し、交換された前記記憶手段の第２のアドレスのデ
   ータは前記処理要素間で同時に所定回数転送し、個々の
   前記処理要素に転送された前記記憶手段の第２のアドレ
   スのデータを前記記憶手段の第１のアドレスに格納する
   手続きを前記処理要素の総数が奇数の場合は前記処理要
   素の総数（Ｎ）を２で割った値（Ｎ／２）分実行し、前
   記処理要素の総数が偶数の場合には前記処理要素の総数
   （Ｎ）を２で割った値（Ｎ／２）より１を減した値（Ｎ
   ／２−１）分実行し、前記処理要素の総数が偶数且つ前
   記処理要素の総数を２で割った値（Ｎ／２）とデータ転
   送を繰り返すカウント（ｒ）が等しければ全ての前記処
   理要素において同時に前記記憶手段の第１のアドレスの
   データを取り出し、取り出した前記第１のアドレスデー
   タを前記処理要素間で同時に所定カウント分転送し、前
   記各処理要素では個々の前記処理要素に転送された前記
   第１のアドレスのデータを前記記憶手段の第２のアドレ
   スに格納することを特徴とするマルチプロセッサにおけ
   るデータの再割り付け方法。
2. 【請求項２】　　前記第１のアドレス（ｈ＋ｒ）に対す
   る前記処理要素間の転送回数を前記第１のアドレス（ｈ
   ＋ｒ）のデータの交換対象となるデータに対する前記第
   ２のアドレス（ｈ＋Ｎ−ｒ）のアドレス値からｈを減じ
   た値（Ｎ−ｒ）とし、前記第２のアドレス（ｈ＋Ｎ−ｒ
   ）のデータに対する前記処理要素間の転送回数を前記第
   ２のアドレス（ｈ＋Ｎ−ｒ）のデータの交換対象となる
   データに対する前記第１のアドレス（ｈ＋ｒ）のアドレ
   ス値からｈを減じた値ｒとして、ｒ＝１，２，・・・，
   ［Ｎ／２］に対して前記処理要素の前記記憶手段から取
   り出されるデータの前記処理要素間の同時転送における
   転送回数をカウントして、前記取り出したデータに対す
   る再配置先の前記処理要素への転送処理を制御すること
   を特徴とするマルチプロセッサにおけるデータの再割り
   付け方法の制御方法。
3. 【請求項３】　　前記第１のアドレスを保持する第１の
   カウンタと、前記第２のアドレスを保持する第２のカウ
   ンタと、前記処理要素の前記記憶手段から取り出される
   データの前記処理要素間の同時転送における転送回数を
   カウントする第３のカウンタと、前記第１のカウンタの
   出力と前記第２のカウンタの出力とを切り換えるセレク
   タと、前記セレクタの出力は前記第３のカウンタの入力
   に接続され、前記第３のカウンタの値がｈに等しいこと
   を検出して第１のフラグを発生する第１のフラグ発生手
   段と、前記セレクタにより前記第１のフラグの内容によ
   って前記第１のカウンタの出力と前記第２のカウンタの
   出力とを切り換える切り換え手段と、繰り返しの回数の
   制御パラメータを保持する第１のレジスタと、全ての前
   記処理要素の個数の偶奇性判定用のパラメータを保持す
   る第２のレジスタと、前記第１のレジスタの内容と、前
   記第１のカウンタの内容との一致を検出して第２のフラ
   グを発生させる第２のフラグ発生手段と、前記第２のレ
   ジスタの最下位ビットの内容によりすべての前記処理要
   素の個数の偶奇性を判断する偶奇性判断手段と、前記第
   ２のフラグの内容と前記第２のレジスタの最下位ビット
   の内容によってデータの再配置処理の終了を検出する終
   了検出手段とを有することを特徴とするマルチプロセッ
   サにおけるデータの再割り付けの制御機構。