JPH03262076A - 並列データ処理装置 - Google Patents
並列データ処理装置Info
- Publication number
- JPH03262076A JPH03262076A JP2061636A JP6163690A JPH03262076A JP H03262076 A JPH03262076 A JP H03262076A JP 2061636 A JP2061636 A JP 2061636A JP 6163690 A JP6163690 A JP 6163690A JP H03262076 A JPH03262076 A JP H03262076A
- Authority
- JP
- Japan
- Prior art keywords
- data
- arithmetic
- calculation
- fourier transform
- fast fourier
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Multi Processors (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
［産業上の利用分野］
この発明は高速フーリエ変換を高速に実行するために、
該変換のバタフライ演算後のピットリバース処理を行う
を行う並列データ処理装置に関するものである。
該変換のバタフライ演算後のピットリバース処理を行う
を行う並列データ処理装置に関するものである。
［従来の技術］
高速フーリエ変換とは次式で示す離散的フーリエ変換式
を高速に演算するもので、サンプル値ｆ （ｋｌ と回
転子Ｗ″′の乗算、およびΣに対する加減算回数を大幅
に減少させたものである。
転子Ｗ″′の乗算、およびΣに対する加減算回数を大幅
に減少させたものである。
第１５図は２ポイントの高速フーリエ変換におけるバタ
フライ演算を図示したものである。図において・ （３
４）はｘ＋ｙ 、 Ｏ（３５１は（ｘ−ｙ） Ｗ’を演
算するものとする。全ての高速フーリエ変換はこの２ポ
イントのバタフライ演算に帰着できる。
フライ演算を図示したものである。図において・ （３
４）はｘ＋ｙ 、 Ｏ（３５１は（ｘ−ｙ） Ｗ’を演
算するものとする。全ての高速フーリエ変換はこの２ポ
イントのバタフライ演算に帰着できる。
以下１６ポイントの高速フーリエ変換の場合を例として
述べる。
述べる。
第１６図は第１５図の記述法にしたがって１６ポイント
の高速フーリエ変換のバタフライ演算を記述したもので
ある。
の高速フーリエ変換のバタフライ演算を記述したもので
ある。
１６ポイント高速フーリエ変換の場合、各要素に付いて
βＯｇＪ・４回のバタフライ演算を行えば良く、同図に
おいて演算順序を第１段（３６） 、第２段（３７１、
第３段（３８） 、第４段（３９）とする。
βＯｇＪ・４回のバタフライ演算を行えば良く、同図に
おいて演算順序を第１段（３６） 、第２段（３７１、
第３段（３８） 、第４段（３９）とする。
第１７図は従来の並列データ処理装置における第１図の
バタフライ演算を示したものであり、 （４０）は演算
要素を示す。
バタフライ演算を示したものであり、 （４０）は演算
要素を示す。
従来の並列データ処理装置は上記のように構成され、第
１６図のように第１段から第４段まで加減。
１６図のように第１段から第４段まで加減。
算および乗算を繰り返すことによりバタフライ演算を並
列に行う。
列に行う。
マタ、ハタフラーｒ演算の結果ｆ（ｎ） （ｎ４ｘａ
Ｘ２ ＸＩｘｏｌ、［］は２進数表現）は［Ｘｏ Ｘ＋
Ｘｚ Ｘｓ］の順に格納され、演算要素平面上では第
１８図のように格納される。これを元の位置に並びかえ
る処理をビットリバースと呼ぶが、従来の並列データ処
理装置では同図のように演算要素平面のアドレスが左右
対称でない行、または列についてその単位毎に入れ換え
を行うため、これだけでは１行・列が逆に格納される。
Ｘ２ ＸＩｘｏｌ、［］は２進数表現）は［Ｘｏ Ｘ＋
Ｘｚ Ｘｓ］の順に格納され、演算要素平面上では第
１８図のように格納される。これを元の位置に並びかえ
る処理をビットリバースと呼ぶが、従来の並列データ処
理装置では同図のように演算要素平面のアドレスが左右
対称でない行、または列についてその単位毎に入れ換え
を行うため、これだけでは１行・列が逆に格納される。
そこで、転置行列を求めることにより高速フーリエ変換
を並列に処理する。
を並列に処理する。
［発明が解決しようとする課題］
上記のような従来の並列データ処理装置では。
次に示す点から必ずしも高速な処理が可能ではない。
■）処理した結果が行方向のデータと列方向のデータが
逆に格納されてしまうため９本来不必要な転置行列を求
める処理を施さないとフーリエ変換の結果が得られない
。
逆に格納されてしまうため９本来不必要な転置行列を求
める処理を施さないとフーリエ変換の結果が得られない
。
２）サンプル数が正方行列にならないと転置行列を求め
るのが困難である。
るのが困難である。
３）除算機能がないため離散的フーリエ変換式の１７Ｎ
に相当する演算が困難である。
に相当する演算が困難である。
従来の並列データ処理装置では上記の欠点が存在するた
め、必ずしも高速な処理ができないという問題点があっ
た。
め、必ずしも高速な処理ができないという問題点があっ
た。
この発明はかかる課題を解決するためになされたもので
、高速に高速フーリエ変換を実行することができる並列
データ処理装置を得ることを目的とする。
、高速に高速フーリエ変換を実行することができる並列
データ処理装置を得ることを目的とする。
［課題を解決するための手段］
この発明に係るデータ処理装置は、四則演算機能を有す
る演算手段と記憶手段と与えられた命令を実行する実行
制御手段とを有する複数の演算要素が、互いに隣接する
要素間でデータ転送するためのデータ転送ラインにより
２次元状に相互接続された演算アレイにおいて、各演算
要素に１つまたは２つ以上のデータを対応させこれらの
データに対し行単位及び列単位に２のべき乗だけ離れた
要素間でデータを転送するとともに、各々の演算要素内
での加減乗算を制御して高速フーリエ変換のバタフライ
演算を行い、上記演算の終了後に各要素内のデータを所
定の行・列に入れ換えることによりピットレバース処理
を行う手段を備えたものである。
る演算手段と記憶手段と与えられた命令を実行する実行
制御手段とを有する複数の演算要素が、互いに隣接する
要素間でデータ転送するためのデータ転送ラインにより
２次元状に相互接続された演算アレイにおいて、各演算
要素に１つまたは２つ以上のデータを対応させこれらの
データに対し行単位及び列単位に２のべき乗だけ離れた
要素間でデータを転送するとともに、各々の演算要素内
での加減乗算を制御して高速フーリエ変換のバタフライ
演算を行い、上記演算の終了後に各要素内のデータを所
定の行・列に入れ換えることによりピットレバース処理
を行う手段を備えたものである。
［作用］
この発明においては各演算要素においてバタフライ演算
を並列して同時に行い、上記演算後のデータを所定の行
・列に入れ換えているから、転置行列を求める処理が不
要になり、高速フーリエ変換が実行できる。
を並列して同時に行い、上記演算後のデータを所定の行
・列に入れ換えているから、転置行列を求める処理が不
要になり、高速フーリエ変換が実行できる。
［実施例］
第１図はこの発明の位置実施例を示す構成図であり、（
１）は演算要素、（２）は演算要素固有のデータを格納
するメモリ、（３）は四則演算を行うＡＬＵ、（４１は
演算命令を制御する制御装置、 ｆ５１ 。
１）は演算要素、（２）は演算要素固有のデータを格納
するメモリ、（３）は四則演算を行うＡＬＵ、（４１は
演算命令を制御する制御装置、 ｆ５１ 。
（６１、ｆ７１ 、 ｆ８）は各々の演算要素から見て
上。
上。
下、左、右の方向の演算要素にデータ転送するデータ転
送ラインである。
送ラインである。
上記のように構成された並列データ処理装置においては
、 １６ポイントの高速フーリエ変換を例にとると、従
来通りバタフライ演算を行った結果第２図のように各演
算要素上にデータが並ぶ。
、 １６ポイントの高速フーリエ変換を例にとると、従
来通りバタフライ演算を行った結果第２図のように各演
算要素上にデータが並ぶ。
まず、同図で（９）と （ｌＯ）及び（ｉｌｌと（１２
）の部分を入れ換え第３図のように配置する。図中の数
時はｆ （ｎｌの値を示す。この手段は、第４図のよう
に左半分（１３）の演算要素上のデータだけを１行上方
向に転送し、第５図のように（１４）及び（１５）の部
分、すなわち１行おきに２列右方向に転送し、第６図の
ように左半分（１６）を１行下方向に転送する。
）の部分を入れ換え第３図のように配置する。図中の数
時はｆ （ｎｌの値を示す。この手段は、第４図のよう
に左半分（１３）の演算要素上のデータだけを１行上方
向に転送し、第５図のように（１４）及び（１５）の部
分、すなわち１行おきに２列右方向に転送し、第６図の
ように左半分（１６）を１行下方向に転送する。
次に、この結果すなわち第７図で（１７）と（１８）及
び （１９）と （２０）の部分を入れ換えることによ
りビットリバース処理が完了する。この手順は。
び （１９）と （２０）の部分を入れ換えることによ
りビットリバース処理が完了する。この手順は。
第９図のように１列おきの演算要素（２１）及び（２２
）だけを２行分上方向にデータ転送し、第１Ｏ図のよう
に上半分（２３）を１列右方向に転送子、第１１図のよ
うに （２４）及び（２５）の部分、すなわち１列おき
に２行下方向に転送する。以上の手順で第８図のように
ビットリバース処理が完了する。
）だけを２行分上方向にデータ転送し、第１Ｏ図のよう
に上半分（２３）を１列右方向に転送子、第１１図のよ
うに （２４）及び（２５）の部分、すなわち１列おき
に２行下方向に転送する。以上の手順で第８図のように
ビットリバース処理が完了する。
以上は正方行列の場合を考えたが、一般に高速フーリエ
変換で扱うサンプル数は２のべき乗である。すなわち ２″・２′″・２１ （ｎは偶数） ２″・２１・２１・２ （ｎは奇数）であり、正方行
列でない場合は必ず２対１の長方行列であることがわか
る。この例を３２ポイントの高速フーリエ変換の場合に
ついて述べる。
変換で扱うサンプル数は２のべき乗である。すなわち ２″・２′″・２１ （ｎは偶数） ２″・２１・２１・２ （ｎは奇数）であり、正方行
列でない場合は必ず２対１の長方行列であることがわか
る。この例を３２ポイントの高速フーリエ変換の場合に
ついて述べる。
バタフライ演算の結果は第１２図のように格納される。
（２６）と（２７）及び（２８）と （２９）の部分
を入れ換え第１３図のように配置し、 （３０）と（
３１）及び（３２）と（３３）の部分を入れ換えて第１
４図のようになりビットリバース処理が完了する。
を入れ換え第１３図のように配置し、 （３０）と（
３１）及び（３２）と（３３）の部分を入れ換えて第１
４図のようになりビットリバース処理が完了する。
この手順は１６ポイントの場合と同様であり、以下のよ
うになる。
うになる。
ｌ）第１２図において１列数の２分の１を境にその左側
、すなわち左半分の演算要素上のデータを１行上に転送
する。
、すなわち左半分の演算要素上のデータを１行上に転送
する。
２）１行おきの演算要素について列数の２分の１を境に
左右のデータを入れ換える。
左右のデータを入れ換える。
３）列数の２分の１を境にその左側の演算要素上のデー
タを１行下に転送する。この結果第１３図のように配置
される。
タを１行下に転送する。この結果第１３図のように配置
される。
４）第１３図において９列数の４分の１おきの演算要素
について２行だけ上方向に転送する。
について２行だけ上方向に転送する。
５）２行おきの演算要素について９列数の２分の１ごと
の組をさらに２分の１に切り、これを中心としてその各
々左右のデータを入れ換える。
の組をさらに２分の１に切り、これを中心としてその各
々左右のデータを入れ換える。
６）列数の４分の１おきの演算要素について２行だけ下
方向に転送する。
方向に転送する。
ところで上記説明では、この発明の並列データ処理装置
を１６ポイント及び３２ポイントの高速フーリエ変換す
る場合について述べたが、２のべき乗の一般的にサンプ
ル数の高速フーリエ変換でも。
を１６ポイント及び３２ポイントの高速フーリエ変換す
る場合について述べたが、２のべき乗の一般的にサンプ
ル数の高速フーリエ変換でも。
列数の２・分の１おきの演算要素について２・−１行だ
け上方向に転送し、２”行おきの演算要素について列数
の２″−１のｌ毎の各組の２分の１に切りこれを中心と
して左右のデータを入れ換え９列数の２゜分の１おきの
演算要素について２′−１行だけ下方向に転送し、 ｉ
＝１からｉ＝βＯｇｚｎまで繰り返すことにより利用で
きる。
け上方向に転送し、２”行おきの演算要素について列数
の２″−１のｌ毎の各組の２分の１に切りこれを中心と
して左右のデータを入れ換え９列数の２゜分の１おきの
演算要素について２′−１行だけ下方向に転送し、 ｉ
＝１からｉ＝βＯｇｚｎまで繰り返すことにより利用で
きる。
［発明の効果］
この発明は以上説明したとおり、複数個の演算要素を２
次元状に相互接続し同時に動作させ９行単位及び列単位
に転送、演算を行うといった簡単な方法により、高速フ
ーリエ変換が高速に実行できる並列データ処理装置が得
られるといった効果がある。
次元状に相互接続し同時に動作させ９行単位及び列単位
に転送、演算を行うといった簡単な方法により、高速フ
ーリエ変換が高速に実行できる並列データ処理装置が得
られるといった効果がある。
第１図はこの発明の一実施例を示す並列データ処理装置
の構成図、第２図は上記発明の一実施例による１６ポイ
ント高速フーリエ変換のバタフライ演算後のデータ配置
及び入れ変えるデータの組を示す図、第３図は第２図の
結果を示す図、第４図は第２図から第３図に導くための
１番目の手順を示す図、第５図は同じく２番目の手順を
示す図。 第６図は同じく３番目の手順を示す図、第７図は第３図
の状態からビットリバース処理を完了するために入れ換
えるべきデータの組を示す図、第８図は上記処理が完了
した状態を示す図、第９図は第７図から第８図に導くた
めの１番目の手順を示す図、第１０は同じく２番目の手
順を示す図、第１１図は同じく３番目の手順を示す図、
第１２図は上記発明の一実施例による３２ポイント高速
フーリエ変換の場合のバタフライ演算後のデータ配置及
び入れ換えるべきデータの組を示す図、第１３図は第１
２図で示したデータの組を入れ換えた結果及び最終的に
入れ換えるべきデータの組を示す図、 第１４図は１６
ポイント高速フーリエ変換のバタフライ演算アルゴリズ
ムを示す図、第１７図は従来の並列データ処理装置にお
ける第１段目のバタフライ演算の手順を示す図、第１８
図は上記従来の並列データ処理装置に置けるビットリバ
ース処理の手順を示す図である。 図においては）は演算要素、（２）はメモリ（記憶手段
） 、 １３）はＡＬＵ （四則演算手段）、（４）
は制御装置（実行制御手段） 、 ｆ５１ 、 （６１
、（７１。 （８）はデータ転送ライン、 （９１，ｆｌＯ） 、
ｆｉｌｌ。 （１２）は入れ換えるデータの組、 （１３） 、
（１４） 。 （１５） 、 ＋１６１は移動する部分、 ｆ１７
） 、 ｆ１８）。 （１９１、（２０）は入れ換えるデータの組、 （２１
）。 （２２１、＋２３１． ＋２４１ 、＋２５１は移動す
る部分、 （２６１゜（２７］、 （２８１，（２９１
、＋３０１． （３１１，（３２）、 ＋３３１は入れ
換えるデータの組、 （３４１は）（＋ｙの演算を示
す符号、 （３５）はｆｘ−ｙ） １１’の演算を示
す符号。 （３６） 、 ｆ３７）、 （３８１、＋３９１は１
６ポイント高速フーリエ変換のバタフライ演算の第１段
目、第２段目、第３段目、第４段目、 （４０１は演算
アレイ。 （４１）、 ＋４２＋は演算アレイのアドレスである
。 なお、各図中同一符号は同一または相当部分を示す。
の構成図、第２図は上記発明の一実施例による１６ポイ
ント高速フーリエ変換のバタフライ演算後のデータ配置
及び入れ変えるデータの組を示す図、第３図は第２図の
結果を示す図、第４図は第２図から第３図に導くための
１番目の手順を示す図、第５図は同じく２番目の手順を
示す図。 第６図は同じく３番目の手順を示す図、第７図は第３図
の状態からビットリバース処理を完了するために入れ換
えるべきデータの組を示す図、第８図は上記処理が完了
した状態を示す図、第９図は第７図から第８図に導くた
めの１番目の手順を示す図、第１０は同じく２番目の手
順を示す図、第１１図は同じく３番目の手順を示す図、
第１２図は上記発明の一実施例による３２ポイント高速
フーリエ変換の場合のバタフライ演算後のデータ配置及
び入れ換えるべきデータの組を示す図、第１３図は第１
２図で示したデータの組を入れ換えた結果及び最終的に
入れ換えるべきデータの組を示す図、 第１４図は１６
ポイント高速フーリエ変換のバタフライ演算アルゴリズ
ムを示す図、第１７図は従来の並列データ処理装置にお
ける第１段目のバタフライ演算の手順を示す図、第１８
図は上記従来の並列データ処理装置に置けるビットリバ
ース処理の手順を示す図である。 図においては）は演算要素、（２）はメモリ（記憶手段
） 、 １３）はＡＬＵ （四則演算手段）、（４）
は制御装置（実行制御手段） 、 ｆ５１ 、 （６１
、（７１。 （８）はデータ転送ライン、 （９１，ｆｌＯ） 、
ｆｉｌｌ。 （１２）は入れ換えるデータの組、 （１３） 、
（１４） 。 （１５） 、 ＋１６１は移動する部分、 ｆ１７
） 、 ｆ１８）。 （１９１、（２０）は入れ換えるデータの組、 （２１
）。 （２２１、＋２３１． ＋２４１ 、＋２５１は移動す
る部分、 （２６１゜（２７］、 （２８１，（２９１
、＋３０１． （３１１，（３２）、 ＋３３１は入れ
換えるデータの組、 （３４１は）（＋ｙの演算を示
す符号、 （３５）はｆｘ−ｙ） １１’の演算を示
す符号。 （３６） 、 ｆ３７）、 （３８１、＋３９１は１
６ポイント高速フーリエ変換のバタフライ演算の第１段
目、第２段目、第３段目、第４段目、 （４０１は演算
アレイ。 （４１）、 ＋４２＋は演算アレイのアドレスである
。 なお、各図中同一符号は同一または相当部分を示す。
Claims (1)
- 四則演算を行う演算素子と、上記演算素子にデータを供
給するメモリ素子と、与えられた命令を実行する手段を
有する複数の演算素子が二次元平面上に互いに接続され
た演算アレイより構成されている並列データ処理装置に
おいて、行単位及び列単位に２のべき乗だけ離れた演算
素子間でデータ転送するとともに各々の演算要素内で四
則演算を繰り返す事により、高速フーリエ変換のバタフ
ライ演算を行い、行方向・列方向に２のべき乗だけ離れ
た演算要素間でデータ転送することによりビットリバー
ス処理を行うことを特徴とする並列データ処理装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2061636A JPH03262076A (ja) | 1990-03-13 | 1990-03-13 | 並列データ処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2061636A JPH03262076A (ja) | 1990-03-13 | 1990-03-13 | 並列データ処理装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH03262076A true JPH03262076A (ja) | 1991-11-21 |
Family
ID=13176885
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2061636A Pending JPH03262076A (ja) | 1990-03-13 | 1990-03-13 | 並列データ処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH03262076A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5751616A (en) * | 1995-11-29 | 1998-05-12 | Fujitsu Limited | Memory-distributed parallel computer and method for fast fourier transformation |
| US7441106B2 (en) | 2004-07-02 | 2008-10-21 | Seagate Technology Llc | Distributed processing in a multiple processing unit environment |
| JP2012123561A (ja) * | 2010-12-07 | 2012-06-28 | Internatl Business Mach Corp <Ibm> | ルートｉ（√ｉ）演算の保持を特徴とする基数８固定小数点ＦＦＴ論理回路 |
-
1990
- 1990-03-13 JP JP2061636A patent/JPH03262076A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5751616A (en) * | 1995-11-29 | 1998-05-12 | Fujitsu Limited | Memory-distributed parallel computer and method for fast fourier transformation |
| US7441106B2 (en) | 2004-07-02 | 2008-10-21 | Seagate Technology Llc | Distributed processing in a multiple processing unit environment |
| JP2012123561A (ja) * | 2010-12-07 | 2012-06-28 | Internatl Business Mach Corp <Ibm> | ルートｉ（√ｉ）演算の保持を特徴とする基数８固定小数点ＦＦＴ論理回路 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0122048B1 (en) | Data processing cells and parallel data processors incorporating such cells | |
| EP0497586A2 (en) | Motion detection circuit | |
| CA2130336A1 (en) | Method and apparatus for rapidly processing data sequences | |
| JPS6211960A (ja) | プロセツサアレイ | |
| KR880011681A (ko) | 메모리연결형 파면어레이 프로세서 | |
| CN108205700A (zh) | 神经网络运算装置和方法 | |
| Qiao et al. | Cycle time analysis of dual-arm cluster tools for wafer fabrication processes with multiple wafer revisiting times | |
| JPH0233191B2 (ja) | ||
| JPH09153029A (ja) | 高速フーリエ変換を行うメモリ分散型並列計算機およびその方法 | |
| JPH03262076A (ja) | 並列データ処理装置 | |
| JP2580501B2 (ja) | 並列デ−タ処理装置 | |
| JPH05233795A (ja) | 画像拡大縮小装置 | |
| JPH06175986A (ja) | 行列演算の並列処理方法 | |
| EP0073116A2 (en) | Integrated data processing circuits | |
| JP2600591B2 (ja) | 乗算器 | |
| JPS60175174A (ja) | 並列デ−タ転送方式 | |
| JP3860545B2 (ja) | 画像処理装置及び画像処理方法 | |
| JPH03116271A (ja) | ２次元画像の高速フーリエ変換解析方法 | |
| WO1999053417A1 (en) | Device for converting series of data elements | |
| JPH0648485B2 (ja) | 並列データ処理方式 | |
| JP2835366B2 (ja) | 高速フーリエ変換用アドレス情報発生装置 | |
| JP3839504B2 (ja) | フーリエ変換装置 | |
| JP2605792B2 (ja) | 演算処理装置 | |
| JPS5839336B2 (ja) | 自動制御系のデイジタル処理方式 | |
| KR950009773B1 (ko) | 메쉬형 병렬 컴퓨터의 단위기판 배열방법 |