図面 (/)

技術 衝突防止メモリ装置及びそれを用いたアドレス計算とデータルーティング方法

出願人 朴宗元
発明者 朴宗元
出願日 2001年8月30日 (19年5ヶ月経過) 出願番号 2001-262291
公開日 2003年3月7日 (17年11ヶ月経過) 公開番号 2003-067361
状態 特許登録済
技術分野 マルチプロセッサ メモリシステム 並列プロセッサ
主要キーワード 製作パラメータ 四角形ブロック メインコンピューター メインメモリ装置 位置制約 割り当て関数 モジュロ計算 修正速度
関連する未来課題
重要な関連分野

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

図面 (15)

課題

アクセス時間を減少させるための衝突防止メモリ装置を提供する。

解決手段

pq個のプロセッシングエレメントを持つSIMD処理器 M×Nアレイ内のデータでの任意の位置で一定の間隔を持つ4方向のブロック(pq)形態と8方向の線分形態であるpq個のデータ要素を同時にアクセスできるように支援して、メモリ装置アクセス時間を減少させるための衝突防止メモリ装置に関するものであり、従来のメモリ装置と比べてデータクセス形態、間隔、データアレイの大きさに制限、及びハードウェア費用、速度、復雑度面で改善された衝突防止メモリ装置及びそれを用いたアドレス計算及びデータルティング方法である。

概要

背景

一般的な制御装置で構成された単一命令多重データ(Single Instruction Multiple Data:SIMD)処理器、SIMDの命令プログラムが記憶されている共有メモリモジュール及び衝突防止メモリ装置が含まれる多くのプロセッシングエレメント応用分野で図1のようにメインメモリ装置があるコンピューターに取り付けられて使用される。

映像処理演算(M. J. B. Duff、Computing structures for image processing、 Academic Press、1983.、J. L. Potter.、IEEE Computer、vol. 16、No. 1、pp. 62-67、Jan. 1983.、K. Preston、Jr.、IEEE Computer、vol. 16.、No. 1、pp. 36-47、Jan. 1983.、T. J. Fountain、K. N. Matthews、and M. J. B. Duff、IEEE Trans. PAMI、vol. 10、No. 3、pp. 310-319、 May 1988.、H. S. Wallace and M. D. Howard、IEEE Trans. PAMI、 vol. 11、 No. 3、pp. 227-232、Mar. 1989.、L. A. Schmitt and S. S. Wilson、IEEE Trans. PAMI、 vol. 10、No. 3、 pp. 320- 330、May 1988.、V. Dixit and D. I. Moldovan、IEEE Trans. PAMI、vol. 9 No. 1、pp. 153-160、 Jan. 1987.、L. Uhr、Parallel computer vision、Academic press、1987.、A. Rosenfeld、 Multiresolution image processing and analysis、 Springer-Verlag、 1984.、G. Y. Kim、Parallel memory architectures for image processing and wavelet-based video coding、Ph.D. thesis、Korea Advanced Institute of Science and Technology、 1999.、 G. A. Baxes、Digital image processing、 Prentice-Hall、1984.、H. E. Burdick、 Digital imaging、McGraw-Hill、1997.)、双方向併合整列(E. Horowitz and S. Sahni、 Data structures in pascal、 Computer Science Press、 1984.)、連続的な二重高速フーリエル変換(J. W. Cooley、 P. A. W. Lewis、 andP. D. Welch、 IEEE Trans. Educ.、vol. E-12、 No.1、pp. 27-34、1969.、D.T. Harper III and D. A. Linebarger、Storage schemes for efficient computation of a radix 2FFTin a machine with parallel memories、in Proc. 1988 Int. Conf. Parallel Processing、1988.)、再帰倍加(Recursive Doubling:RD)(H. S. Stone、High-performance computer architecture、Addison Wesley、1993.)、基本的な行列演算(D. J. Kuck and R. A. Strokes、IEEE Trans. Comput. vol. C-31、 pp.362-376、May 1982.)等の分野に応用される。こうような応用分野のため、衝突防止メモリ装置からデータのアクセス形態基準座標、データ間の間隔を持ってデータを探し、そのデータをプロセッシングエレメントに割り当てる命令をSIMDコンピューターの制御装置に送った後、制御装置によってそれぞれ異なるデータを持って同じ形態の計算を行うようにする。それで、SIMD処理器の効率性のため、メモリ装置の重要な目的は次のようである。

1. 多様なサブアレイのアクセス形態と間隔:メモリ装置は0でない陽数間隔を持っているデータに対して多様な形態の同時アクセス支援しなければならない。

2.位置制約のない同時アクセス:同時アクセスされるデータの位置は与えられたデータアレイ内のどこでも可能でなければならない。

3. 簡単で迅速なアドレス計算ルーティング回路:アドレス計算とルーティングは簡単迅速にしなければならない。

4. 簡単で迅速なデータのルーティング回路:データのルーティングは簡単迅速にしなければならない。

5.負荷のないプロセッシングエレメント:アドレス計算とルーティング、及びデータルティングはプロセッシングエレメントに負荷を与えずに、メモリ装置内で行わなければならない。それで、プロセッシングエレメントとメモリ装置との間にインターフェースデータレジスターがある。

6. 少ない数のメモリモジュール:メモリ装置のモジュール数はプロセッシングエレメント数と同じであるとか大きな範囲でできるだけ少なくしなければならない。

多重メモリモジュールを持つ貯蔵装置の効率性増大がメモリ装置の分野で長い間に研究された。そのうちで一つが連続的なメモリ装置アクセス要求に対するモジュールのメモリ装置アクセス時間を重ねることであるが(D. T. Harper III、IEEE Trans. Parallel Distrib. Syst.、vol. 2.、pp. 43-51、Jan. 1991.、D. T. Harper III、IEEE Trans. Comput.、vol. C-41、pp.227-230、Feb. 1992.)、前記したSIMD処理器には適当ではない。

SIMD処理器のためのメモリ装置の簡単な貯蔵装置は、メモリ装置をインターリビングさせることであり、メモリ装置のメモリモジュール数をmとすると、アドレスaは(a)mod(m)のメモリモジュールに位置する。ここでmodはモジュロ演算子である。インターリビングされた記憶システムのメモリモジュール数はSIMD処理器のプロセッシングエレメント数と同じなので、アドレス計算とデータのルーティングが簡単に具現されるので、このような体制が多くのSIMD処理器に含まれた。しかし、インターリビングされた体制は一定な間隔によって連関した多様なサブアレイアクセス形態データの同時アクセスを支援しないので、メモリモジュールでの衝突によって性能が低下する。(W. Oed and O. Lange、IEEE Trans. Comput.、vol. C-34、 pp. 949-957、 Oct. 1985.、D. Baily、IEEE Trans. Comput.、vol. C-36、 pp. 293-298、 Mar. 1987.)。

他方、インターリビングされたメモリ装置での平均的な性能を改善する提案があったが、それはSIMD処理器のために更に有用ではない。それは同じモジュールを要求するメモリ要求の衝突によってSIMD処理器の全プロセッシングエレメントの計算が全部遅延されるためである。

貯蔵装置体制の他の一つは多くの人々によって研究された非線型分野である。ほとんどの非線型斜線方式はバッチャー(K. Batcher、IEEE Trans. Comput.、vol. 26、 no. 1、 pp. 174-177、 1977.)によって初めて考案されたビっト演算XORに基づいている。フライロングによって一般化されたXOR方式はデータアドレス点のマルチプライ行列の変形によって貯蔵位置を計算する。XOR方式は2の乗数個のメモリモジュールでデータのアドレス計算とルーティングが簡単である。しかし、この方式はデータのサブアレイアクセス形態、データ間の間隔、データの位置が制限的である。

メモリ装置の他の一つ体制は線型的な斜線方式である。

行列の (i、j)に位置したデータは(ai+bj)mod(m)のメモリモジュールに位置する。ここで、aとbは常数であり、mはメモリモジュール数を示す。線型斜線方式はブッドニックとクック(P. Budnik and D. J. Kuck、IEEE Trans. Comput.、vol. C-20、 pp.1566-1569、 Dec. 1971.)によって初めて提案され、この方式の特性はシャピロ(H. Shapiro、IEEE Trans. Comput.、vol. C-27、 no. 5、 pp.421-428、 May 1978.)と、ウィジショーフとバンリーウぇン(H. Wijshoff and J. Van Leeuwen、 IEEE Trans. Comput.、 vol. C-34、 no. 6、 pp. 501-505、June 1985.、 H. Wijshoff and J. Van Leeuwen、 IEEE Trans. Comput.、 vol. C-36、 no. 2、 pp. 233-239、 Feb. 1987.)によって研究された。ブッドニックとクック、シャピロ、ウィジショーフとバンリーウぇンと、ローリ(D. H. Lawrie、 IEEE Trans. Comput.、 vol. C-24、 no. 12、 pp. 1145-1155、 Dec. 1975.)は、もしデータの数より大きな素数個のメモリモジュールがあれば、ブロック、行、列、対角線、逆対角線アクセス形態のサブアレイ内で衝突なく同時にデータをアクセスすることができるメモリ装置に対して証明した。線型斜線方式の短所はアドレス計算、アドレスルーティング及びデータルーティングでm個のメモリモジュールアドレスが一緒に計算されるとき、複雑で速度が鈍いということである。そして、時間が多く掛かるモジュール(m)での計算を避けるため、データの数が2の乗数である場合、メモリモジュール数を同時アクセスされるデータ数の2倍にしなければならないということである。

表1a及び表1bは線型斜線方式での目標(1)~(6)を実現するSIMD処理器に対する貯蔵技術、線型有無、ルーティング方法、サブアレイアクセス形態、間隔、ハードウェアの具現、同時性アクセス位置、プロセッシングエレメントの負荷、そして従来のメモリ装置と本発明で提示するメモリ装置のメモリモジュール数などを示す。

概要

アクセス時間を減少させるための衝突防止メモリ装置を提供する。

pq個のプロセッシングエレメントを持つSIMD処理器 M×Nアレイ内のデータでの任意の位置で一定の間隔を持つ4方向のブロック(pq)形態と8方向の線分形態であるpq個のデータ要素を同時にアクセスできるように支援して、メモリ装置アクセス時間を減少させるための衝突防止メモリ装置に関するものであり、従来のメモリ装置と比べてデータクセス形態、間隔、データアレイの大きさに制限、及びハードウェア費用、速度、復雑度面で改善された衝突防止メモリ装置及びそれを用いたアドレス計算及びデータルーティング方法である。

目的

本発明の目的は簡単で迅速なアドレス計算回路とルーティング回路を持つ衝突防止メモリ装置を提供することにある。

本発明の他の目的はM×Nアレイ内のデータにおける任意の位置で一定の間隔を持つ4方向のブロック(pq)形態と8方向の線分形態であるpq個のデータ要素に同時にアクセスできるよう支援して、メモリ装置のアクセス時間を短縮することができる衝突防止メモリ装置を提供することにある。

更に、本発明の他の目的は従来のメモリ装置と比べてデータへのアクセス形態、間隔、データアレイの大きさ制限及びハードウェア費用と速度等の面で改善されたメモリ装置を提供することにある。

効果

実績

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

この技術が所属する分野

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

請求項1

m(m>pq)個のメモリモジュールと、データに対するm個アドレスを計算しその値を前記m個のメモリモジュールにルーティング(routing)するアドレス計算及びアドレスルーティング回路と、アクセスされるpq個のメモリモジュールを選択するメモリモジュール選択回路と、指定されたアクセス類型基準座標及びアクセス類型で要求される間隔情報貯蔵するデータレジスターと、前記データレジスター内のデータを前記m個のメモリモジュールにルーティングするデータルティング回路を含んでなり、pq個のプロセッシングエレメントを持つ単一命令多重データ(SIMD)処理装置おけるメモリ装置アクセス時間を減少させるための衝突防止メモリ装置において、4方向四角形ブロック陽数の間隔で連関されたデータ要素データアレイ内のどの位置(東側ブロック、南西側ブロック、西側ブロック、北東側ブロック)に置かれていっても、または8方向の線型(東側線型、南東側線型、南側線型、南西側線型、西側線型、北西側線型、北線型、北東側線型)に置かれていってもアクセス形態のpq個データ要素に同時アクセス支援することを特徴とする衝突防止メモリ装置。

請求項2

前記アドレス計算及びアドレスルーティング回路は、基準座標、アクセス形態及び間隔情報が提供される4個の5×1マルチプレクサーと、アドレス間差を予め整列して貯蔵するための第1及び第2 SRAMと、(i/p)s値のための第3 SRAMと、前記マルチプレクサー出力値を前記第1及び第2 SRAMに伝逹する二つの加算器と前記第3 SRAMの出力値が伝逹され加えられる加算器とm個の加算器とからなるm+3個の加算器と、前記m個の加算器の出力をデータルーティング回路の回転信号に応じてm個のメモリモジュールに伝逹するバレル(barrel)シフターからなることを特徴とする第1項に記載の衝突防止メモリ装置。

請求項3

p×m個のアドレス間差とq×m個のアドレス間差を、それぞれのアクセス形態とそれぞれの間隔に対して整列する過程と、整列されたp×m個のアドレス間差とq×m個のアドレス間差を、それぞれのアクセス形態とそれぞれの間隔に対してメモリモジュールAとBに貯蔵する過程と、要求されたアクセス形態、i%p、j%q間隔によってメモリモジュールAとBでm個のアドレス間差を読み込む過程と、読み込むm個のアドレス間差を基準アドレスα(i、j)に加える過程と、m個のアドレスを12種のアクセス形態と間隔全体に対してμ(0)により回転させる過程と、回転され計算されたm個のアドレス値をm個のメモリモジュールにルーティングする過程からなることを特徴とする衝突防止メモリ装置を用いたアドレス計算とデータルーティング方法。

技術分野

0001

本発明はメモリ装置に関し、より詳細にはpq個のプロセッシングエレメント(Processing Element:PE)を持つSIMD処理器におけるM×Nアレイ内のデータで任意位置から一定間隔を持つ4方向のブロック(pq)形態と8方向の線分形態であるpq個のデータ要素を同時にアクセスすることができるよう支援することでメモリ装置アクセス時間を減少させるための衝突防止メモリ装置に関する。

背景技術

0002

一般的な制御装置で構成された単一命令多重データ(Single Instruction Multiple Data:SIMD)処理器、SIMDの命令プログラムが記憶されている共有メモリモジュール及び衝突防止メモリ装置が含まれる多くのプロセッシングエレメントが応用分野で図1のようにメインメモリ装置があるコンピューターに取り付けられて使用される。

0003

映像処理演算(M. J. B. Duff、Computing structures for image processing、 Academic Press、1983.、J. L. Potter.、IEEE Computer、vol. 16、No. 1、pp. 62-67、Jan. 1983.、K. Preston、Jr.、IEEE Computer、vol. 16.、No. 1、pp. 36-47、Jan. 1983.、T. J. Fountain、K. N. Matthews、and M. J. B. Duff、IEEE Trans. PAMI、vol. 10、No. 3、pp. 310-319、 May 1988.、H. S. Wallace and M. D. Howard、IEEE Trans. PAMI、 vol. 11、 No. 3、pp. 227-232、Mar. 1989.、L. A. Schmitt and S. S. Wilson、IEEE Trans. PAMI、 vol. 10、No. 3、 pp. 320- 330、May 1988.、V. Dixit and D. I. Moldovan、IEEE Trans. PAMI、vol. 9 No. 1、pp. 153-160、 Jan. 1987.、L. Uhr、Parallel computer vision、Academic press、1987.、A. Rosenfeld、 Multiresolution image processing and analysis、 Springer-Verlag、 1984.、G. Y. Kim、Parallel memory architectures for image processing and wavelet-based video coding、Ph.D. thesis、Korea Advanced Institute of Science and Technology、 1999.、 G. A. Baxes、Digital image processing、 Prentice-Hall、1984.、H. E. Burdick、 Digital imaging、McGraw-Hill、1997.)、双方向併合整列(E. Horowitz and S. Sahni、 Data structures in pascal、 Computer Science Press、 1984.)、連続的な二重高速フーリエル変換(J. W. Cooley、 P. A. W. Lewis、 andP. D. Welch、 IEEE Trans. Educ.、vol. E-12、 No.1、pp. 27-34、1969.、D.T. Harper III and D. A. Linebarger、Storage schemes for efficient computation of a radix 2FFTin a machine with parallel memories、in Proc. 1988 Int. Conf. Parallel Processing、1988.)、再帰倍加(Recursive Doubling:RD)(H. S. Stone、High-performance computer architecture、Addison Wesley、1993.)、基本的な行列演算(D. J. Kuck and R. A. Strokes、IEEE Trans. Comput. vol. C-31、 pp.362-376、May 1982.)等の分野に応用される。こうような応用分野のため、衝突防止メモリ装置からデータのアクセス形態基準座標、データ間の間隔を持ってデータを探し、そのデータをプロセッシングエレメントに割り当てる命令をSIMDコンピューターの制御装置に送った後、制御装置によってそれぞれ異なるデータを持って同じ形態の計算を行うようにする。それで、SIMD処理器の効率性のため、メモリ装置の重要な目的は次のようである。

0004

1. 多様なサブアレイのアクセス形態と間隔:メモリ装置は0でない陽数間隔を持っているデータに対して多様な形態の同時アクセスを支援しなければならない。

0005

2.位置制約のない同時アクセス:同時アクセスされるデータの位置は与えられたデータアレイ内のどこでも可能でなければならない。

0006

3. 簡単で迅速なアドレス計算ルーティング回路:アドレス計算とルーティングは簡単迅速にしなければならない。

0007

4. 簡単で迅速なデータのルーティング回路:データのルーティングは簡単迅速にしなければならない。

0008

5.負荷のないプロセッシングエレメント:アドレス計算とルーティング、及びデータルティングはプロセッシングエレメントに負荷を与えずに、メモリ装置内で行わなければならない。それで、プロセッシングエレメントとメモリ装置との間にインターフェースデータレジスターがある。

0009

6. 少ない数のメモリモジュール:メモリ装置のモジュール数はプロセッシングエレメント数と同じであるとか大きな範囲でできるだけ少なくしなければならない。

0010

多重メモリモジュールを持つ貯蔵装置の効率性増大がメモリ装置の分野で長い間に研究された。そのうちで一つが連続的なメモリ装置アクセス要求に対するモジュールのメモリ装置アクセス時間を重ねることであるが(D. T. Harper III、IEEE Trans. Parallel Distrib. Syst.、vol. 2.、pp. 43-51、Jan. 1991.、D. T. Harper III、IEEE Trans. Comput.、vol. C-41、pp.227-230、Feb. 1992.)、前記したSIMD処理器には適当ではない。

0011

SIMD処理器のためのメモリ装置の簡単な貯蔵装置は、メモリ装置をインターリビングさせることであり、メモリ装置のメモリモジュール数をmとすると、アドレスaは(a)mod(m)のメモリモジュールに位置する。ここでmodはモジュロ演算子である。インターリビングされた記憶システムのメモリモジュール数はSIMD処理器のプロセッシングエレメント数と同じなので、アドレス計算とデータのルーティングが簡単に具現されるので、このような体制が多くのSIMD処理器に含まれた。しかし、インターリビングされた体制は一定な間隔によって連関した多様なサブアレイアクセス形態データの同時アクセスを支援しないので、メモリモジュールでの衝突によって性能が低下する。(W. Oed and O. Lange、IEEE Trans. Comput.、vol. C-34、 pp. 949-957、 Oct. 1985.、D. Baily、IEEE Trans. Comput.、vol. C-36、 pp. 293-298、 Mar. 1987.)。

0012

他方、インターリビングされたメモリ装置での平均的な性能を改善する提案があったが、それはSIMD処理器のために更に有用ではない。それは同じモジュールを要求するメモリ要求の衝突によってSIMD処理器の全プロセッシングエレメントの計算が全部遅延されるためである。

0013

貯蔵装置体制の他の一つは多くの人々によって研究された非線型分野である。ほとんどの非線型斜線方式はバッチャー(K. Batcher、IEEE Trans. Comput.、vol. 26、 no. 1、 pp. 174-177、 1977.)によって初めて考案されたビっト演算XORに基づいている。フライロングによって一般化されたXOR方式はデータアドレス点のマルチプライ行列の変形によって貯蔵位置を計算する。XOR方式は2の乗数個のメモリモジュールでデータのアドレス計算とルーティングが簡単である。しかし、この方式はデータのサブアレイアクセス形態、データ間の間隔、データの位置が制限的である。

0014

メモリ装置の他の一つ体制は線型的な斜線方式である。

0015

行列の (i、j)に位置したデータは(ai+bj)mod(m)のメモリモジュールに位置する。ここで、aとbは常数であり、mはメモリモジュール数を示す。線型斜線方式はブッドニックとクック(P. Budnik and D. J. Kuck、IEEE Trans. Comput.、vol. C-20、 pp.1566-1569、 Dec. 1971.)によって初めて提案され、この方式の特性はシャピロ(H. Shapiro、IEEE Trans. Comput.、vol. C-27、 no. 5、 pp.421-428、 May 1978.)と、ウィジショーフとバンリーウぇン(H. Wijshoff and J. Van Leeuwen、 IEEE Trans. Comput.、 vol. C-34、 no. 6、 pp. 501-505、June 1985.、 H. Wijshoff and J. Van Leeuwen、 IEEE Trans. Comput.、 vol. C-36、 no. 2、 pp. 233-239、 Feb. 1987.)によって研究された。ブッドニックとクック、シャピロ、ウィジショーフとバンリーウぇンと、ローリ(D. H. Lawrie、 IEEE Trans. Comput.、 vol. C-24、 no. 12、 pp. 1145-1155、 Dec. 1975.)は、もしデータの数より大きな素数個のメモリモジュールがあれば、ブロック、行、列、対角線、逆対角線アクセス形態のサブアレイ内で衝突なく同時にデータをアクセスすることができるメモリ装置に対して証明した。線型斜線方式の短所はアドレス計算、アドレスルーティング及びデータルーティングでm個のメモリモジュールアドレスが一緒に計算されるとき、複雑で速度が鈍いということである。そして、時間が多く掛かるモジュール(m)での計算を避けるため、データの数が2の乗数である場合、メモリモジュール数を同時アクセスされるデータ数の2倍にしなければならないということである。

0016

表1a及び表1bは線型斜線方式での目標(1)~(6)を実現するSIMD処理器に対する貯蔵技術、線型有無、ルーティング方法、サブアレイアクセス形態、間隔、ハードウェアの具現、同時性アクセス位置、プロセッシングエレメントの負荷、そして従来のメモリ装置と本発明で提示するメモリ装置のメモリモジュール数などを示す。

0017

0018

ID=000004HE=170 WI=139 LX=0355 LY=0300
一方、映像処理で全体的なメモリ装置アクセス時間を減少するためにブロック、列、行、対角線、または逆対角線型態の多くの映像点を同時にアクセスすることができるSIMD処理器(G. Y. Kim、 Parallel memory architectures for imageprocessing and wavelet-based video coding、Ph.D. thesis、Korea AdvancedInstitute of Science and Technology、 1999.)が要求される。映像点の算術演算論理演算のため、デジタルイメージプロセッシング(G. A. Baxes、 Digital image processing、Prentice-Hall、1984.)、ブロック、列、行のアクセス形態の映像点が並列的に演算できるように各プロセッシングエレメントに割り当てられなければならない。ウェブレット変換(K. R. Castleman、Digital image processing、 Prentice-Hall、1996.、S. Mallat、IEEE Trans. PAMI、vol. 11、No. 7、 pp. 674-693、 July 1989.)では列と行のアクセス形態の映像点をアクセスするメモリ装置が必要となる。2n2×2n2個のプロセッシングエレメントで2n1×2n1大きさの映像の縁辺探索、コンボリューション低域フィルター(G. A. Baxes、 Digital image processing、 Prentice-Hall、 1984.、 H. E. Burdick、 Digital imaging、 McGraw-Hill、 1997.、 J. R. Parker、 Algorithms forImage Processing and Computer Vision、 John Wiley & Sons、 1997.、 D. H. Ballard and C. M. Brown、 Computer Vision、 Prentice-Hall、 1982.、 J.S. Lim、 Two-dimensional signal and image processing、 Prentice-Hall、1990.)のような近接演算を行うため、各プロセッシングエレメントは一つの3×3ブロックや4×4ブロックが割り当てられなければならず、3や4間隔を持つ大きさが2n2×2n2であるブロックのメモリ装置アクセスが必要となる。2n1×2n1大きさの映像において2n2×2n2個のプロセッシングエレメントが8×8DCT(Discrete Cosine Transform)(K. R. Rao and P. Yip、Discrete Cosine Transform、 Academic Press、 1990.)の処理のため、各プロセッシングエレメントは8×8ブロックの割当を受けなければならず、8間隔を持つ2n2×2n2ブロックのメモリ装置アクセスが必要となる。動き推定(J. S. Lim、Two-dimensional signal and image processing、 Prentice-Hall、1990.)では16×16ブロックの参照映像と16×16ブロックの以前映像の迅速な比較のために1、2、4の間隔であるブロックのメモリ装置アクセスが必要となる。2×2、3×3の部分サンプリング方法を使用する連続的な伝送(W. Y. Kim、P. T. Balsara、D. T. Harper and J. W. Park、IEEE Trans.Circuits and Systems for Video Technology、 vol. 5、 No.1、 pp.1-13、Feb. 1995.)ではメモリ装置アクセス時間を短縮するため、lを整数とする時に間隔が2lや3lであるブロック形態のデータが同時にアクセスできねばならない。

0019

他の例としては圧縮文字分析動き分析などに用いられるガウシアンピラミッド(A. Rosenfeld、 Multi-resolution image processing and analysis、 Springer-Verlag、 1984.、 P. J. Burt、 Comput. Vision、 Graphics、 Image processing 16、 pp.20-51、 1981.、 P. J. Burt、 Comput. Vision、 Graphics、 Image processing 21、 pp.368-382、 1983.)や階層離散相関ウィンドー関数(Hierarchical Discrete Correlation Window Function)を速やかに具現することができる。Kレベルの再帰的かつ直接的な計算のために全レベルの全ノード値や、0レベルの全ての2番目ノード値がSIMD処理器の各プロセッシングエレメントに割り当てられなければならない。それで、衝突防止メモリ装置はガウシアンピラミッドの生成(J. W. Park and D. T. Harper III、IEEE Symp. Parallel andDistributed Processing、 pp.444-451、 Dec. 1992.、 J. W. Park and D. T.Harper III、 IEEE Trans. Parallel Distrib. Syst.、 vol. 7、 No. 8、 pp.855-860、 Aug. 1996.)に対して全体的なメモリ装置アクセス時間の減少のため、任意の位置でl≧0に対して、間隔2lを持つブロックや行形態の映像点を同時にアクセスできるように支援する。一つの列のノード数がプロセッシングエレメント数より少ないレベルである場合には行形態よりもブロック形態で映像点を同時にアクセスする方がより良い。また、一部映像の速やかな90°回転や反射映像のために後に説明する4方向ブロックアクセス形態の映像点をアクセスするメモリ装置が必要となる。45°や5°ずつ(J. W. Park、 Efficient image analysis and processing memory system、 Korean Patent 58542、 1993.、 Efficient image analysis and processing memory system、 Japanese Patent 2884815、 2000.、 J. W. Park、 S. R. Maeng and J. W. Cho、 Int. J. of High Speed Computing、 vol. 2、 No. 4、 pp.375-385、 Dec. 1990.) 一部映像の速やかな回転のためにも8方向の線型映像点をアクセスできるメモリ装置が必要となる。

0020

双方向併合整列アルゴリズム、連続的な増加FFTアルゴリスム、再帰的な増加アルゴリズム、行列、信号処理等のためにブロック、列、行、対角線、逆対角線アクセス形態のデータを同時にアクセスできるメモリ装置が全体的なメモリ装置アクセス時間を短縮するためのSIMD処理器に必要となる。

0021

双方向併合整列は長さが1ずつである整列されたデータファイルn個の入力から始まる。このn個のデータファイルは大きさが2であるn/2個のファイルに併合される。n/2個のファイルが再び併合され、このような方法で1個のデータファイルとなるまで繰り返される。それで、速やかな双方向併合整列アルゴリズムのため、2l(l>0)の間隔の行形態データをアクセスできるメモリ装置がSIMD処理器に有用である。

0022

SIMD処理器で連続的な増加FFTアルゴリズム(J. W. Cooley、 P. A. W. Lewisand P. D. Welch、IEEE Trans. Educ.、 vol. E-12、 No.1、 pp. 27-34、 1969.、 D. T. Harper III and D. A. Linebarger、 in Proc. 1988 Int. Conf. Parallel Processing、 1988.)のために2l(l>0)間隔の行形態のデータをアクセスすることができるメモリ装置がメモリ装置アクセス時間の短縮に有用である。

0023

足し算掛け算、最大、最少、AND、OR、XOR演算等を行う再帰的な増加アルゴリズム(H. S. Stone、 High-performance computer architecture、 Addison Wesley、 1993.)のためにはメモリ装置アクセス時間を短縮するため、2l(l>0)間隔の行アクセス形態データをアクセスできるメモリ装置が有用である。行列での足し算、掛け算、式(57、58) (これは後に出るのを参照)はブロック、列、行、対角線、逆対角線型態のデータに同時にアクセスすれば効果的である。また、SIMD処理器で信号処理(J. S. Lim、Two-dimensional signal and image processing、 Prentice-Hal、 1990.、 D. H. Johnson and D. E. Dudgeon、 Array signalprocessing、 Prentice-Hall、 1993.)をするために多様な行列演算の速度を高めるためのブロック、列、行、対角線、逆対角線型態の同時データクセスを支援する衝突のフリ記憶は全体的なメモリ装置アクセス時間を短縮するのに有用である。

0024

pq個のプロセッシングエレメントで構成されたSIMD処理器とm個のメモリモジュールで構成されたメモリ装置において、pq個のデータが同時にそれぞれ異なるメモリモジュールから要請される。記憶置アクセス時間の後、pq個の要請が終り、全メモリモジュールもその演算を終えることになるが、このとき要請されたデータ内の各データの位置は制限されてはならない。映像処理、双方向併合整列アルゴリズム、連続増加FFTアルゴリズム、再帰的な倍加アルゴリズム、そして行列、信号処理等において、メモリ装置アクセス時間を短縮し演算速度を速めるために、大きさが I(*、*)であるデータで間隔 rを持ってブロック、列、行、対角線、逆対角線アクセス形態でpq個のデータを同時にアクセスできるメモリ装置が必要となる。間隔が陽数や陰数で可能になるためには基準座標(i、j)から間隔が陽数rである12種のアクセス類型(東側ブロック、南西側ブロック、西側ブロック、北東側ブロック、東側ブロック、南東側線型、南側線型、南西側線型、西側線型、北西側線型、北側線型、北東側線型)を考慮しなければならない。

0025

SEB(i、j、r) = {I(i+ar、j+br) | 0 ≦ a < p、0 ≦ b < q}、
0 ≦ i ≦ M-rp、0 ≦ j ≦ N-rq (1)
SWB(i、j、r) = {I(i+ar、j-br) | 0 ≦ a < p、 0 ≦ b < q}、
0 ≦ i ≦ M-rp、rq ≦ j ≦ N (2)
NWB(i、j、r) = {I(i-ar、j-br) | 0 ≦ a < p、 0 ≦ b < q}、
rp ≦ i ≦ M、 rq ≦ j ≦ N (3)
NEB(i、j、r) = {I(i-ar、j+br) | 0 ≦ a < p、0 ≦ b < q}、
rp ≦ i ≦ M、 0 ≦ j ≦ N-rq (4)
EL(i、j、r) = {I(i、j+ar) | 0 ≦ a < pq}、
0 ≦ i ≦ M、 0 ≦ j ≦ N-rpq (5)
SEL(i、j、r) = {I(i+ar、j+ar) | 0 ≦ a < pq}
0 ≦ i ≦ M-rpq、0 ≦ j ≦ N-rpq (6)
SL(i、j、r) = {I(i+ar、j) | 0 ≦ a < pq}、
0 ≦ i ≦ M-rpq、0 ≦ j ≦ N (7)
SWL(i、j、r) = {I(i+ar、j-ar) | 0 ≦ a < pq}、
0 ≦ i ≦ M-rpq、rpq ≦ j ≦ N (8)
WL(i、j、r) = {I(i、j-ar) | 0 ≦ a < pq}、
0 ≦ i ≦ M、rpq ≦ j ≦ N (9)
NWL(i、j、r) = {I(i-ar、j-ar) | 0 ≦ a < pq}、
rpq ≦ i ≦ M、 rpq ≦ j ≦ N (10)
NL(i、j、r) = {I(i-ar、j) | 0 ≦ a < pq}、
rpq ≦ i ≦ M、0 ≦ j ≦ N (11)
NEL(i、j、r) = {I(i-ar、j+ar) | 0 ≦ a < pq}、
rpq ≦ i ≦ M、 0 ≦ j ≦ N-rpq (12)
ここで、間隔 rは陽の正数である。

0026

基準座標(i、j)で間隔rを持つ12種のアクセス類型(1)〜(12)は図2aと図2bに示す。図2aは4方向ブロック(SEB、SWB、NWB、NEB)を、図2bは8方向線型(EL、SEL、SL、SWL、WL、NWL、NL、NEL)を示す。

0027

図3ではSIMD処理器がある衝突防止メモリ装置の一般的な構造をブロックダイアグラム形態で示す。ここでインターフェースはデータレジスターである。処理すべきデータが貯蔵されると、メモリ装置の構成要素はSIMD処理器の要請に従って制御装置の制御下に次のような演算を順次的に行う。

0028

(1) t、r、i、jレジスターにはSIMD処理器によって指定されたアクセス類型、基準座標、アクセス類型(1)~(12)で要求される間隔が入れ込まれ、データは行優先順位に変わってデータレジスターに入れ込まれる。ここで、k=a・q+b、0≦k<pqである。例えば、南側ブロック(SEB)(14、15、2)で行優先順位に変わった4個のデータはI(14、15)、I(14、17)、I(16、15)、I(16、17)である。南西側ブロック(SWB)(14、15、3)で行優先順位に変わった4個のデータはI(14、15)、I(14、12)、I(17、15)、I(17、12)であり、北西側線型(NWL)(14、15、3)の4個のデータはI(11、12)、I(8、9)、I(5、6)、I(2、3)である。

0029

(2)アドレス計算及びアドレスルーティング回路はデータに対するm個のアドレスを計算し、それをm個のメモリモジュールにルーティングする。

0030

(3)メモリモジュール選択回路はアクセスされるpq個のメモリモジュールを選択する。

0031

(4) データルーティング回路はデータレジスター内のデータをm個のメモリモジュールにルーティングする。

0032

(5) 書き信号によってpq個のデータが選択されたpq個のメモリモジュールに貯蔵される。

0033

ここで(2)、(3)、(4)番の演算が並列に行われる。

0034

同様にメモリ装置からデータを取り出す時にもメモリ装置の構成要素は次のような演算を順次的に行う。

0035

(1) t、r、i、jレジスター値を決定する。

0036

(2)アドレス計算及びアドレスルーティング回路はデータに対するm個のアドレスを計算し、それをm個のメモリモジュールにアドレスをルーティングさせる。

0037

(3)メモリモジュール選択回路はアクセスできるpq個のメモリモジュールを選択する。

0038

(4) 読み信号によってpq個の選択されたメモリモジュールからpq個のデータを取ってくる。

0039

(5) データルーティング回路はm個のメモリモジュールからデータレジスターにデータをルーティングし、行優先順位に変形されたデータを(1)~(12)アクセス形態中の一つに配列する。

0040

ここで、(2)、(3)番の演算が並列に行われる。

0041

大きさがM×NであるデータI(*、*)をmメモリモジュールに分散する時、メモリモジュール割り当て関数は同時にアクセスされるデータを他のメモリモジュールに位置させなければならない。また、アドレス割り当て関数は同じメモリモジュールに割り当てられるデータに他のアドレスを割り当てなければならない。

発明が解決しようとする課題

0042

本発明の目的は簡単で迅速なアドレス計算回路とルーティング回路を持つ衝突防止メモリ装置を提供することにある。

0043

本発明の他の目的はM×Nアレイ内のデータにおける任意の位置で一定の間隔を持つ4方向のブロック(pq)形態と8方向の線分形態であるpq個のデータ要素に同時にアクセスできるよう支援して、メモリ装置のアクセス時間を短縮することができる衝突防止メモリ装置を提供することにある。

0044

更に、本発明の他の目的は従来のメモリ装置と比べてデータへのアクセス形態、間隔、データアレイの大きさ制限及びハードウェア費用と速度等の面で改善されたメモリ装置を提供することにある。

課題を解決するための手段

0045

このような目的を達成するための本発明による衝突防止メモリ装置は、(m>pq)個のメモリモジュールと、データに対するm個のアドレスを計算しその値を前記m個のメモリモジュールにルーティングするアドレス計算及びアドレスルーティング回路と、アクセスされるpq個のメモリモジュールを選択するメモリモジュール選択回路と、指定されたアクセス類型と基準座標及びアクセス類型で要求される間隔情報を貯蔵するデータレジスターと、前記データレジスター内のデータを前記m個のメモリモジュールにルーティングするデータルーティング回路を含んでなり、pq個のプロセッシングエレメントを持つ単一命令多重データ処理装置おけるメモリ装置アクセス時間を減少させるための衝突防止メモリ装置において、4方向四角形ブロック陽数の間隔で連関されたデータ要素がデータアレイ内のどの位置(南東側ブロック、南西側ブロック、北西側ブロック、北東側ブロック)に置かれていっても8方向の線型(東側線型、南東側線型、南側線型、南西側線型、西側線型、北西側線型、北線型、北東側線型)アクセス形態のpq個データ要素に同時アクセスを支援する。

0046

本発明による衝突防止メモリ装置の細部的な特徴は、前記アドレス計算及びアドレスルーティング回路が、基準座標、アクセス形態及び間隔情報が提供される4個の5×1マルチプレクサーと、アドレス間差を予め整列して貯蔵するための第1及び第2 SRAMと、(i/p)s値のための第3 SRAMと、前記マルチプレクサー出力値を前記第1及び第2 SRAMに伝逹する二つの加算器と前記第3 SRAMの出力値が伝逹され加えられる加算器とm個の加算器とからなるm+3個の加算器と、前記m個の加算器の出力をデータルーティング回路の回転信号に応じてm個のメモリモジュールに伝逹するバレルシフターからなることにある。

発明を実施するための最良の形態

0047

以下、本発明の衝突防止メモリ装置の構成と、そのメモリ装置を利用したアドレス計算及びデータルーティング方法を添付図面により詳細に説明する。

0048

データのメモリモジュール番号を決定するメモリモジュール割り当て関数は次のとおりである。

0049

(i、j) = (iq+j) % m (13)
メモリモジュール割り当て関数(13)はm=pq+1、2pq、pq2に対してはバンブーリスモリン(D. C. Van Voorhis and T. H. Morrin、IEEE Trans. Comput.、vol. C-27、pp.113-125、Feb. 1978.)によって、m=pq+1に対してはパク(J. W. Park、IEEE Trans. Comput.、vol. C-35、pp. 669-674、July 1986)と、パクとハーパ(J. W. Park and D. T. Harper III、IEEE Symp. Parallel and Distributed Processing、pp. 444-451、Dec. 1992.、J. W. Park and D. T. Harper III、IEEE Trans. Parallel Distrib. Syst..、vol. 7、No. 8、pp. 855-860、Aug. 1996.)により提案された。

0050

次の理論1は12種のアクセス類型(1)~(12)に対して前記の関数(13)によるアクセス可能性を示している。

0051

理論1:mが pqより大きな素数である時、メモリモジュール割り当て関数(i、j)は間隔がr(r%m≠0)である南東側ブロック(SEB)、南西側ブロック(SWB)、北西側ブロック(NWB)、北東側ブロック(NEB)、東側線型(EL)、南東側線型(SEL)、南側線型(SL)、南西側線型(SWL)、西側線型(WL)、北西側線型(NWL)、北側線型 (NL)、北東側線型(NEL)アクセス形態であるpq個のデータはpq個のお互いに異なるメモリモジュール内に位置する。

0052

メモリモジュール内のデータのアドレスを決定する割り当て関数は下記の式(14)のとおりである。

0053

(i、j) = (i/p)s + j/q (14)
ここで、「s」はN/qの整数部分と同じ或いはより大きな整数であり、「/」は整数形の割り算を表す。この関数はバンブーリスとモリン(D. C. Van Voorhis and T. H. Morrin、IEEE Trans. Comput.、vol. C-27、pp. 113-125、Feb. 1978.)、パク(J. W. Park、IEEE Trans. Comput.、 vol. C-35、pp. 669-674、July 1986)、パクとハーパ(J. W. Park and D. T. Harper III、IEEE Symp. Parallel andDistributed Processing、pp. 444-451、Dec. 1992.、J. W. Park and D. T. Harper III、IEEE Trans. Parallel Distrib. Syst.、vol. 7、No. 8、pp. 855-860、Aug. 1996.)によって提案された。

0054

(1)〜(12)アクセス類型において、メモリモジュールの変化とデータのアドレスが変更された行優先順位に配列できれば、k = a・q+b、0≦k<pqである時、メモリモジュール割り当て関数(13)とアドレス割り当て関数(14)は次のように表すことができる。

0055

μ(k) = (μ(0) + μ'(k))%m、 0 ≦ k < pq (15)
ここで、μ(0)は関数(13)の(i、j)によって求められる。

0056

α(k) = α(0) + α'(k)、 0 ≦ k < pq (16)
ここで、α(0)は関数(14)の基準アドレスであるα(i、j)である。

0057

メモリモジュール内で処理されるべきデータのアドレスが計算されるα(μ)(0≦μ< m)は非常に鈍く高価である(D. C. Van Voorhis and T. H. Morrin、IEEETrans. Comput.、vol. C-27、pp. 113-125、Feb. 1978.、D. H. Lawrie and C.R. Vora、 IEEE Trans. Comput.、vol. C-31、 pp.435-442、 May 1982.)。データのアドレス計算はアドレスルーティングから分離されたアドレス計算により複雑性を低減した。パク(J. W. Park、IEEE Trans. Comput.、vol. C-35、pp. 669-674、 July 1986)、パクとハーパ(J. W. Park and D. T. Harper III、IEEE Symp. Parallel and Distributed Processing、pp. 444-451、Dec. 1992.、J. W.Park and D. T. Harper III、IEEE Trans. Parallel Distrib. Syst.、vol. 7、No. 8、pp. 855-860、Aug. 1996.)のメモリ装置でアドレス間差α'(k) (=α(k)-α(0))が優先的に計算され、そのアドレス間差をα(0)に加えて式(16)のα'(k)を計算する。

0058

最後にアドレスα(k)はメモリモジュールにルーティングされる。アドレス計算及びアドレスルーティング方法の短所はルーティング形態がアクセス形態と間隔に依存するため、アドレスルーティング回路はアクセス類型と間隔が増加すると非常に複雑になる。

0059

本発明では新しいアドレス計算とルーティング方法がアドレス間差α'(k)に要求されたデータのうち、第1番目データのμ(0)のメモリモジュール番号からメモリモジュール番号に従って順次的に予め整列されるよう提案された。それで、基準アドレスにアドレス間差を加えた後、全体12アクセス類型と間隔μ(0)による右側回転が必要となる。

0060

μ'(k)とα'(k)を求めるためには前記の式(15-16)が次のように変わる。

0061

μ'(k) = μ((k)-μ(0))%m、 0 ≦ k < pq (17)
α'(k) = α(k)-α(0)、 0 ≦ k < pq (18)
μ'(k) = (λ・ k)%mの場合に、
k = (μ'(k) λ')%m = ((μ(k)-μ(0))λ')%m (19)
ここで、 λ・ λ' = 1%mである。

0062

式(18)におけるkの代りに((μ(k)-μ(0))・λ')%mを用いて、α'(k)を次のようにすることができる。

0063

α'(k)=α'(((μ(k)-μ(0)) ・λ')%m)
=α(((μ(k)-μ(0)) ・λ')%m) - α(0)、 0 ≦ k < pq (20)
α'(k)(0≦k<pq)はメモリ装置内で用いられたpq個のデータのアドレス間差である。ここで、データは (i、j)のデータから変形された行の優先に整列される。メモリモジュール番号に従ってメモリモジュール「0」からアドレス間差(20)の整列によりα'(μ)を次のように求めることができる。

0064

α'(μ)
= α'(((μ- μ(0)) ・λ')%m)
= α(((μ- μ(0)) ・λ')%m) - α(0)、 0 ≦ μ < m (21)
α'(μ)(0≦μ<m)はpq個のデータに対するpq個のアドレス間差とm-pq個の仮アドレス間差であり、それは「0」からメモリモジュール番号μによって整列された。

0065

α'(μ)(0≦μ<m )は基準アドレス(i、j)のデータのメモリモジュール番号μ(0)(=μ(i、j))に依存するため、アドレス間差の個数はメモリモジュール数mに従って増加する。それで、メモリモジュール数mが大きい時、アクセス類型(1)~(12)のデータのアドレス計算に対し、α'(μ)(0≦μ< m)の使用は非常に複雑である。式(21)にμの代りに(μ+μ(0))%mを入れると、下記の式によりメモリモジュールμ(0)からメモリモジュール番号の順次的なアドレス間差を求めることができる。

0066

α'(μ+μ(0)) = α'(μ・λ')%m、 0 ≦ μ < m (22)
式(22)のアドレス間差、α'(μ・λ')%m (0 ≦ μ< m)は (i、j)や (i、j)の項目が含まれていないため、データの位置に対して影響が少ない。

0067

それで、コンパイリング時間にアドレス間差を計算した後、そのアドレス間差を一つのメモリモジュールに貯蔵することができる。式(22)のアドレス間差α'(μ+μ(i、j))がα(i、j)に加えられた後、α(μ)を求めるためにμ(i、j)による右側回転を単一度だけ行う。

0068

12個のアクセス類型(1)~(12)でアドレス間差は次の式で表わされる。
AD_SEB(i、j、r、a、b) = α(i+ar、j+br) - α(i、j)
= s・((i+ar)/p-(i/p)) + (j+br)/q - j/q
= s・((i%p+ar)/p) + (j%q+br)/q、 0 ≦ a < p、 0 ≦ b < q (23)
AD_SWB(i、j、r、a、b) = α(i+ar、j-br) - α(i、j)
= s・((i+ar)/p-(i/p)) + (j-br)/q - j/q
= s・((i%p+ar)/p) + (j%q-br)/q、 0 ≦ a < p、 0 ≦ b < q (24)
AD_NWB(i、j、r、a、b) = α(i-ar、j-br) - α(i、j)
= s・((i-ar)/p - (i/p)) + (j-br)/q - j/q
= s・((i%p-ar)/p) + (j%q-br)/q、 0 ≦ a < p、 0 ≦ b < q (25)
AD_NEB(i、j、r、a、b) = α(i-ar、j+br) - α(i、j)
= s・((i-ar)/p - (i/p)) + (j+br)/q - j/q
= s・ ((i%p-ar)/p) + (j%q+br)/q、 0 ≦ a < p、 0 ≦ b < q (26)
AD_EL(i、j、r、a) = α(i、j+ar) - α(i、j)
= (j%q+ ar)/q、 0 ≦ a < pq (27)
AD_SEL(i、j、r、a) = α(i+ar、j+ar) - α(i、j)
= s・((i%p+ar)/p) + (j%q+ar)/q、 0 ≦ a < pq (28)
AD_SL(i、j、r、a) = α(i+ar、j) - α(i、j)
= s・((i%p+ar)/p)、 0 ≦ a < pq (29)
AD_SWL(i、j、r、a) = α(i+ar、j-ar) - α(i、j)
= s・((i%p+ar)/p) + (j%q-ar)/q、 0 ≦ a < pq (30)
AD_WL(i、j、r、a) = α(i、j-ar) - α(i、j)
= (j%q - ar)/q、 0 ≦ a < pq (31)
AD_NWL(i、j、r、a) = α(i-ar、j-ar) - α(i、j)
= s・((i%p-ar)/p) + (j%q-ar)/q、 0 ≦ a < pq (32)
AD_NL(i、j、r、a) = α(i-ar、j) - α(i、j)
= s・((i%p-a)/p))、 0 ≦ a < pq (33)
AD_NEL(i、j、r、a) = α(i-ar、j+ar) - α(i、j)
= s・((i%p-ar)/p) + (j%q+ar)/q、 0 ≦ a < pq (34)
前記に示したアドレス間差(23)〜(34)は次の式によって変形された行優先順位の基準座標(i、j)から整列される。

0069

AD_SEB(i、j、r、k) = s・((i%p+(k/q)r)/p) + (j%q+(k%q)r)/q、
0 ≦ k < pq (35)
AD_SWB(i、j、r、k) = s・((i%p+(k/q)r)/p) + (j%q-(k%q)r)/q、
0 ≦ k < pq (36)
AD_NWB(i、j、r、k) = s・((i%p-(k/q)r)/p) + (j%q-(k%q)r)/q、
0 ≦ k < pq (37)
AD_NEB(i、j、r、k) = s・((i%p-(k/q)r)/p) + (j%q+(k%q)r)/q、
0 ≦ k < pq (38)
AD_EL(i、j、r、k) = (j%q + kr)/q、 0 ≦ k < pq (39)
AD_SEL(i、j、r、k) = s・((i%p+kr)/p) + (j%q+kr)/q、 0 ≦ k < pq(40)
AD_SL(i、j、r、k) = s・((i%p+kr)/p))、 0 ≦ k < pq (41)
AD_SWL(i、j、r、k) = s・((i%p+kr)/p) + (j%q-kr)/q、 0 ≦ k < pq(42)
AD_WL(i、j、r、k) = (j%q- kr)/q、 0 ≦ k < pq (43)
AD_NWL(i、j、r、k) = s・((i%p-kr)/p) + (j%q-kr)/q、 0 ≦ k < pq(44)
AD_NL(i、j、r、k) = s・((i%p-kr)/p))、 0 ≦ k < pq (45)
AD_NEL(i、j、r、k) = s・((i%p-kr)/p) + (j%q+kr)/q、 0 ≦ k < pq(46)
アドレス間差が二進項目を持つj%qの影響を受けるので、式(35)~(46)のSEB、SWB、NWB、NEB、EL、SEL、SWL、WL、NWL、NELのアドレス間差は加算器の入力CのためにメモリモジュールBに貯蔵された二進値とアドレス間差の大きさ減少の結果である入力BのためのメモリモジュールにAに貯蔵された残り値を分離する。

0070

SEBのアドレス間差は次の式によって分離される。

0071

AD_SEB(i、j、r、k) = s・((i%p+(k/q)r)/p)+((k%q)r)/q、
0 ≦ k < pq(アドレス間差のためのメモリモジュールA)
+ (j%q+(k%q)r)/q - ((k%q)r)/q、
0≦ k < pq(アドレス間差のためのメモリモジュールB) (47)
他の11個でのアクセス類型のアドレス間差は次のとおりである。

0072

AD_SWB(i、j、r、k) = s・((i%p+(k/q)r)/p) - ((k-(k/q)q)r)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q - (k%q)r)/q + ((k%q)r)/q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (48)
AD_NWB(i、j、r、k) = s・((i%p-(k/q)r)/p) - ((k-(k/q)q)r)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q - (k%q)r)/q + ((k%q)r)/q、
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (49)
AD_NEB(i、j、r、k) = s・((i%p-(k/q)r)/p) + ((k-(k/q)q)r)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q + (k%q)r)/q - ((k%q)r)/q
(アドレス間差のてめのメモリモジュールB)、 0 ≦ k < pq (50)
AD_EL(i、j、r、k) = (kr)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q + (k%q)r)/q -((k%q)r)/q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (51)
AD_SEL(i、j、r、k) = s・((i%p+kr)/p) + (kr)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q+kr)/q - (kr)/q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (52)
AD_SL(i、j、r、k) = s・((i%p+kr)/p))
(アドレス間差のためのメモリモジュールA)、 0 ≦ k < pq (53)
AD_SWL(i、j、r、k) = s・ ((i%p+kr)/p) - (kr)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q - (k%q)r)/q + ((k%q)r)/q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (54)
AD_WL(i、j、r、k) = -(kr) / q
(アドレス間差のためのメモリモジュールA)
+ (j%q kr) /q + (kr) / q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (55)
AD_NWL(i、j、r、k) = s・((i%p-kr)/p) - (kr)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q - (k%q)r)/q + ((k%q)r)/q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (56)
AD_NL(i、j、r、k) = s・((i%p-kr)/p))
(アドレス間差のためのメモリモジュールA)、 0 ≦ k < pq (57)
AD_NEL(i、j、r、k) = s・((i%p-kr)/p) + (kr)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q + (k%q)r)/q - ((k%q)r)/q、
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq (58)
前記12種のアドレス間差に対し表2に整理されている。

0073

ID=000005HE=085 WI=132 LX=0390 LY=0850
アドレス計算回路(J. W. Park、IEEE Trans. Comput.、vol. C-35、pp. 669-674、July 1986.、 J. W. Park and D. T. Harper III、IEEE Symp. Parallel and Distributed Processing、 pp. 444-451、Dec. 1992.、 J. W. Park and D. T. Harper III、IEEE Trans. Parallel Distrib. Syst.、vol. 7、No. 8、pp. 855-860、Aug. 1996.)は記憶アドレスの足し算と式 (47)のブロック、式(51)の行、式(53)の行のアクセス類型のアドレス間差によってpqアドレスを計算する。それで、アドレスルーティング方法は12アクセス類型である(1)~(12)のアドレスが限界値p-i%p、または、q-j%qのみならず、陽数間隔の多様性のためで12種のアクセス形態(1)~(12)と間隔のアドレス間差の計算(47)~(58)の具現によってアドレスルーティング方法が更に複雑化する。要請されたデータのメモリモジュール番号が最初のデータのメモリモジュール番号から順次的に予め整理されており、メモリモジュールAとBに貯蔵されていれば、アドレス間差に基準アドレスα(i、j)を加え、全ての12種のアクセス形態(1)~(12)と間隔を1番目データのメモリモジュールと同じ値によってm個のアドレスに直ちにルーティングさせて、アドレスルーティング回路はm個のアドレスを簡単に計算することができる。

0074

理論1においてアクセスされるpq個のメモリモジュール番号は12種のアクセス形態(1)~(12)とr%m≠0である間隔が次のように表される。

0075

IN_SEB(i、j、r) = μ(i+ar、j+br) = (μ(i、j) + qar + br)%m、
0 ≦ a < p、 0 ≦ b < q (59)
IN_SWB(i、j、r) = μ(i+ar、j-br) = (μ(i、j) + qar - br)%m、
0 ≦ a < p、 0 ≦ b < q (60)
IN_NWB(i、j、r) = μ(i-ar、j-br) = (μ(i、j) - qar - br)%m、
0 ≦ a < p、 0 ≦ b < q (61)
IN_NEB(i、j、r) = μ(i+ar、j+br) = (μ(i、j) - qar + br)%m、
0 ≦ a < p、 0 ≦ b < q (62)
IN_EL(i、j、r) = μ(i、j+br) = (μ(i、j) + br)%m、 0 ≦ b < pq(63)
IN_SEL(i、j、r) = μ(i+ar、j+ar) = (μ(i、j) + (q+1)ar)%m、
0 ≦ a < pq (64)
IN_SL(i、j、r) = μ(i+ar、j) = (μ(i、j) + qar)%m、 0 ≦ a < pq
(65)
IN_SWL(i、j、r) = μ(i+ar、j-ar) = (μ(i、j) + (q-1)ar)%m、
0 ≦ a < pq (66)
IN_WL(i、j、r) = μ(i、j-ar) = (μ(i、j) - br)%m、 0 ≦ a < pq
(67)
IN_NWL(i、j、r) = μ(i-ar、j-ar) = (μ(i、j) - (q+1)ar)%m、
0 ≦ a < pq (68)
IN_NL(i、j、r) = μ(i-ar、j) = (μ(i、j) - qar)%m、 0 ≦ a < pq
(69)
IN_NEL(i、j、r) = μ(i-ar、j+ar) = (μ(i、j) - (q-1)ar)%m、
0 ≦ a < pq (70)
前記の式(59)〜(70)の番号は次のことによって基準アドレス(i、j)から変形された行優先順位に整列される。

0076

μSEB(k) = (μ(0) + q・(k/q)・r + (k%q)・r)%m = (μ(0) + kr)%m、
0 ≦ k < pq (71)
μSWB(k) = (μ(0) + q・(k/q)・r - (k%q)・r)%m
= (μ(0) + (q・(k/q) - (k%q)) ・r)%m、 0 ≦ k < pq (72)
μNWB(k) = (μ(0) - q・(k/q)・r - (k%q)・r)%m
= (μ(0) - kr)%m、 0 ≦ k < pq (73)
μNEB(k) = (μ(0) - q・(k/q)・r + (k%q)・r)%m
= (μ(0) - (q・(k/q) - (k%q)) ・r)%m、 0 ≦ k < pq (74)
μEL(k) = (μ(0) + kr)%m、 0 ≦ k < pq (75)
μSEL(k) = (μ(0) + (q+1)kr)%m、 0 ≦ k < pq (76)
μSL(k) = (μ(0) + qkr)%m、 0 ≦ k < pq (77)
μSWL(k) = (μ(0) + (q-1)kr)%m、 0 ≦ k < pq (78)
μWL(k) = (μ(0) - kr)%m、 0 ≦ k < pq (79)
μNWL(k) = (μ(0) - (q+1)kr)%m、 0 ≦ k < pq (80)
μNL(k) = (μ(0) - qkr)%m、 0 ≦ k < pq (81)
μNEL(k) = (μ(0) - (q-1)kr)%m、 0 ≦ k < pq (82)
ここで μ(0)はμ(i、j)である。

0077

南東側ブロック(SEB)のアドレス間差
μ番目モジュールの南東側ブロック(SEB)のアドレス間差、ASEB(μ)は(17)〜(22)過程によって(47)と(71)から得られた。

0078

ASEB(μ) = s・((i%p+((((μ-μ(0))r')%m)/q)r)/p) + (((((μ-μ(0))r')%m
)%q)r)/q、
0 ≦ μ < m (メモリモジュールA)
+ (j%q+((((μ-μ(0))r')%m)%q)r)/q - (((((μ-μ(0))r')%m)%q)r)/q、
0 ≦ μ < m (メモリモジュールB) (83)
ここで、 r・r' = 1%mである。式(83)でμの代りに(μ+μ(0))%mに代置すると、次の式によってμ(0)から上り順に整列されたメモリモジュールのアドレス間差を求めることができる。

0079

ASEB(μ+μ(0)) = s・((i%p+(((μr')%m)/q)r)/p) + ((((μr')%m)%q)r)/q、

0 ≦ μ < m (メモリモジュールA)
+ (j%q+(((μr')%m)%q)r)/q - ((((μr')%m)%q)r)/q、
0 ≦ μ < m (メモリモジュールB) (84)
ここで、r・r' = 1%mである。

0080

南西側ブロック(SWB)のアドレス間差
SWB(i、j、r)の式(72)の番号が式(19)内にないため、SEB(i、j-(q-1)r、r)の番号とアドレス間差は SWB(i、j、r)の代りに考慮される。SEB(i、j-(q-1)r、r)のアドレス間差は、
AD_SEB(i、(j-(q-1)r)、r、k) = s・((i%p+(k/q)r)/p) + ((k%q)r)/q、
0 ≦ k < pq (メモリモジュールA)
+ (j%q-(q-1)r+(k%q)r)/q - ((k%q)r)/q、
0 ≦ k < pq (メモリモジュールB) (85)
SEB(i、j-(q-1)r、k)のメモリモジュールの指数は次のとおりである。

0081

(μ(0) - (q-1)r + kr)%m、 0 ≦ k < pq (86)
それで、μ番目のモジュールの南東側ブロック(SWB)のアドレス間差ASWB(μ)は式(85)と(86)から求めることができる。

0082

ASWB(μ) = s・((i%p+((((μ - μ(0)+(q-1)r)r')%m)/q)r)/p)
+ (((((μ - μ(0)+(q-1)r)r′)%m)%q)r)/q、
0 ≦ μ < m (メモリモジュールA)
+ (j%q-(q-1)r+((((μ-μ(0)+(q-1)r)r')%m)%q)r)/q
- (((((μ - μ(0)+(q-1)r)r')%m)%q)r)/q、
0 ≦ μ < m (メモリモジュールB) (87)
ここで、 r・r' = 1%mである。

0083

式(87)でμの代りに(μ+ μ(0) + (q-1)r)%mを用いて、次の式によってμ(0)から上り順に整列されたメモリモジュールのアドレス間差を求めることができる。

0084

ASWB(μ + μ(0)) = s・((i%p+((((μ+ (q-1)r)r')%m)/q)r)/p)
+ (-(q-1)r + ((((μ+ (q-1)r)r')%m)%q)r)/q、
0 ≦ μ < m (メモリモジュールA)
+ (j%q-(q-1)r+(((( μ+ (q-1)r)r')%m)%q)r)/q
- (-(q-1)r + (((( μ+ (q-1)r)r')%m)%q)r)/q、
0 ≦ μ < m (メモリモジュールB)、 (88)
ここで、 r・r′= 1%mである。

0085

μ(0)から上り順に整列されたメモリモジュールお互いに異なる10種のアクセス形態に対するアドレス間差はSEBやSWBと同じ過程によって求められる。表3にμ(0)から上り順に整列されたメモリモジュールの12種のアクセス形態(1)~(12)と間隔であるアドレス間差を示す。

0086

ID=000006HE=170 WI=106 LX=0520 LY=0300
アドレス間差の大きさ
表3に示したSEB、SWB、NWB、NEB、SEL、SWL、NWL及びNELのアドレス間差は、r、i%p及びj%qの影響を受ける。また、SEB、SWB、NEB、NWB、SEL、SWL、NWL、NELのアドレス間差の大きさは間隔の個数を#rで表すとき、メモリモジュールAに8×p×m×#r×log2(MN/pq)ビットぐらいとメモリモジュールBに8×q×m×#rビットぐらいである。東側線型と西側線型のアドレス間差はk、r、及び j%pの影響を受ける。また、アドレス間差の大きさはメモリモジュールAでは2×q×m×#r×log2(MN/pq)ビットであり、メモリモジュールBでは2×q×m×#rビットである。南側線型と北側線型のアドレス間差はk、r、i%pに影響を受け、アドレス間差の大きさはメモリモジュールBに2×q×m×#r×log2(MN/(pq))ビットである。南側線型と北側線型のアドレス間差はj%qの影響を受けないのでメモリモジュールBにはアドレス間差がない。それで、提案されたメモリ装置のアドレス間差の全体大きさは(12×p×m×log2(MN/pq)+10×q×m)×#rビットである。提案された方法及びメモリ装置の短所は12種のアクセス形態と間隔 (1)~(12)全体に対する表3のアドレス間差を貯蔵するのに、メモリモジュールAとBの大きさが非常に大きくなるということである。それで、要求されたアクセス形態と間隔に対するアドレス間差をコンパイリング時間に計算しメモリモジュールAとBに貯蔵する。

0087

本発明によるアドレス計算回路とアドレスルーティング回路は次のような演算を順次的に行う。

0088

(1) 予め整列されたp×m個のアドレス間差とq×m個の差がそれぞれアクセス形態とそれぞれの間隔に対してメモリモジュールAとBに貯蔵される。

0089

(2)m個のアドレス間差はアクセス形態、i%p、j%qの間隔のみならず、μ(0≦μ<m )などの影響を受けるので、要求されたアクセス形態、i%p、j%q間隔によってメモリモジュールAとBから取ってくる。

0090

(3) 前記で求められたm個のアドレス間差は基準アドレスα(i、j)に加えられる。

0091

(4) 前記のm個のアドレスは12種のアクセス形態と間隔(1)〜(12)全体に対して、μ(0)によって回転される。

0092

(5) 計算されたm個のアドレスはm個のメモリモジュールにルーティングされる。

0093

データレジスターからm個のメモリモジュールにデータをルーティングするデータルーティング回路の役割は適切なメモリモジュールにpq個のデータをルーティングすることにある。pq個のデータに対するメモリモジュール番号は、式(71)〜(82)でのアドレスと同じである。それで、次の数式によってpq個のデータを整列させた後、そのデータのメモリモジュール番号を持ってメモリモジュール番号0から始まる上り順整列のために右側回転がμ(i、j)ぐらい行われる。

0094

SEB: D2((kr)%m) ←D1(k)、 0 ≦ k < pq (89)
SWB: D2(((q・(k/q) - k%q)・r)%m) ←D1(k)、 0 ≦ k < pq (90)
NWB: D2((-kr)%m) ← D1(k)、 0 ≦ k < pq (91)
NEB: D2(((-q・(k/q) + k%q)・r)%m) ←D1(k)、 0 ≦ k < pq (92)
EL: D2((kr)%m) ←D1(k)、 0 ≦ k < pq (93)
SEL: D2(((q+1)kr)%m) ←D1(k)、 0 ≦ k < pq (94)
SL: D2((qkr)%m) ←D1(k)、 0 ≦ k < pq (95)
SWL: D2(((q-1)kr)%m) ←D1(k)、 0 ≦ k < pq (96)
WL: D2((-kr)%m) ← D1(k)、 0 ≦ k < pq (97)
NWL: D2((-(q+1)kr)%m) ←D1(k)、 0 ≦ k < pq (98)
NL: D2((-qkr)%m) ←D1(k)、 0 ≦ k < pq (99)
NEL: D2((-(q-1)kr)%m) ←D1(k)、 0 ≦ k < pq (100)
ここで、D1とD2はデータレジスターと臨時レジスターである。ルーティング形態がアクセス形態と間隔の影響を受けるため、ルーティング形態(89)~(100)を用いるデータルーティング回路の制御は複雑である。このようなデータルーティング形態は次に示すことによって制御の複雑度を減少させることができる。

0095

南東側ブロック(SEB)
式 (89)の南東側ブロック(SEB)のデータルーティング形態に対して、間隔 rのメモリモジュール番号である(kr)%mは(k・m・l1+ k・r1)%mである。 ここで、r1=r%mでありl1は陽数である。それで、式(89)にの間隔rの南東側ブロック(SEB)のデータルーティング形態は下記の式からr1(=r%m)を持つ(m-1)個のお互いに異なるルーティング経路が選択される。

0096

SEB: D2((kr1)%m) ←D1(k)、 0 ≦ k < pq (101)
南西側ブロック(SWB)
式(90)の南西側ブロック(SWB)のデータルーティング形態に対して、間隔rのメモリモジュール番号である((q・(k/q)-k%q)・r)%mは(k・m・l2+(q・(k/q)-k%q)・r1)%mである。ここで、r1=r%mでありl2は陽数である。それで、式(90)の間隔rの南西側ブロック(SWB)のデータルーティング形態は下記の式からr1=r%mを持つ(m-1)個のお互いに異なるルーティング経路が選択される。

0097

SWB: D2(((q・(k/q) - k%q)・r1)%m) ←D1(k)、 0 ≦ k < pq (102)
北西側ブロック(NWB)
式(91)の北西側ブロック(NWB)のデータルーティング形態に対する間隔rのメモリモジュール番号(-kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態(kr)%mの間隔(-r)%mであるメモリモジュール番号と同一である。それで、式(101)の南東側ブロック(SEB)の(m-1)個のお互いに異なるルーティング経路に間隔rの代わりに(-r)%mを代入することで北西側ブロック(NWB)の経路を求めることができる。

0098

北東側ブロック(NEB)
式(92)の北東側ブロック(NEB)のデータルーティング形態に対して、間隔rのメモリモジュール番号である((-q・(k/q)+k%q)・r)%mは、式(90)の南西側ブロック(SWB)のデータルーティング形態で間隔(-r)%mであるメモリモジュール番号の((q・(k/q) - k%q)・r)%mと同一である。それで、式(102)の南西側ブロック(SWB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(-r)%mを代入することで北東側ブロック(NEB)を求めることができる。

0099

東側線型(EL)
式(93)の東側線型(EL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態に対する間隔rのメモリモジュール番号と同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりにr%mを代入して東側線型(EL)の経路を求めることができる。

0100

南東側線型(SEL)
式(94)の南東側線型(SEL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である((q+1)kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態で間隔((q+1)r)%mのメモリモジュール番号である(kr)%mと同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに((q+ 1)r)%mを代入することで南東側線型(SEL)の経路を求めることができる。

0101

南側線型(SL)
式(95)の南側線型(SL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(qkr)%mは、式(89)の南東側ブロック(SEB)のデータ形態で間隔(qr)%mのメモリモジュール番号である(kr)%mと同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(qr)%mを代入することで南側線型(SL)の経路を求めることができる。

0102

南西側線型(SWL)
式(96)の南西側線型(SWL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である((q-1)kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態で間隔((q1) r)%mのメモリモジュール番号である((kr)%m)と同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに((q-1)r)%mを代入することで南西側線型(SWL)の経路を求めることができる。

0103

西側線型(WL)
式(97)の西側線型(WL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(-kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態でメモリモジュール番号である(kr)%mに間隔(-r)%mを入れた(k(-r))%m)と同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(-r)%mを代入することで西側線型(WL)の経路を求めることができる。

0104

北西側線型(NWL)
式(98)の北西側線型(NWL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(-(q+1)kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態でメモリモジュール番号である(kr)%mに間隔(-(q+1)r)%mを入れた(k(-(q+1)r))%mと同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(-(q+1)r)%mを代入することで北西側線型(NWL)の経路を求めることができる。

0105

北線型(NL)
式(99)の北線型(NL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(-qkr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態でメモリモジュール番号である(kr)%mに間隔(-qr)%mを入れた(k(-qr))%mと同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(-qr)%mを代入することで北線型(NL)の経路を求めることができる。

0106

北東側線型(NEL)
式(100)の北東側線型(NEL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(-(q1)kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態でメモリモジュール番号である(kr)%mに間隔(-(q1)r)%mを入れた(k(-(q1)r))%mと同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(-(q1)r)%mを代入することで北東側線型(NEL)の経路を求めることができる。

0107

表4に減少されたルーティング形態が現われている。

0108

ID=000007HE=075 WI=104 LX=0530 LY=2050
12種のアクセス形態に対する全体ルーティング形態は2(m-1)個である。それで、データルーティング回路では間隔(1)~(12)である12種のアクセス形態に対して、式(101)のSEBと式(102)のSWBの二つに対するルーティング形態だけが必要となる。

0109

データルーティング回路は図4に示す。

0110

ここで、ROM、1og2(2(m-1))×2(m-1)検波器及び3相バッファー選択器を用いて、12種のアクセス形態と間隔を持つ2(m-1)ブランチのルーティング形態を作る。12種のアクセス形態と間隔rのためにルーティング形態は、図5a及び図5bに示したようにオメガネットワーク(J. Frailong、W. Jalby、and J. Lenfant、in Proc. Int. Conf. Parallel Processing、1985、pp. 276-283.、 C. S. Raghavendra and R. Boppana、 in Proc. Int. Conf. Parallel Processing 、1990、pp.76-83.、 D. H. Lawrie、IEEE Trans. Comput .、vol. C-24、no. 12、pp. 1145-1155、Dec. 1975.)や、セータ(Theta)ネットワーク(D. Lee、 Scrambled storage for parallel memory systems、 in Proc. Int. Symp. on Comp.Architecture、 pp. 232-239、 1988.)経路の衝突のため具現されることができない。本発明によるデータルーティング回路はクロスバーネットワーク(D. T. Harper III、IEEE Trans. Comput.、vol. C-43、 pp.618-622、 May 1994.、 H.Shapiro、 IEEE Trans. Comput .、 vol. C-27、 no. 5、 pp. 421-428、 May 1978.、 D. H. Lawrie and C. R. Vora、 IEEE Trans. Comput .、 vol. C-31、pp.435-442、 May 1982.)で単純に比較されられた。読み演算のためのルーティング形態は決まっている。

0111

間隔を持つ列、ブロック、行に対するメモリモジュール選択回路はバンブーリスとモリン(D. C. Van Voorhis and T. H. Morrin、IEEE Trans. Comput.、vol.C-27、pp.113-125、Feb. 1978.)、そして、パク(J. W. Park、IEEE Trans. Comput .、vol. C-35、pp.669-674、July 1986)によって提案された。メモリモジュール選択回路は関数(71)〜(82)において出た番号に該当するpq個のメモリモジュールを選択する。一般的に(m-pq) << pqであるので、使われないメモリモジュールを捜すメモリモジュール選択回路の具現が易しい。次の理論2は12種のアクセス形態(1)~(12)に対する(m-pq)個のアクセスされないメモリモジュール番号を見せる。

0112

理論2 : 12種のアクセス形態に対する(m-pq)個のアクセスされないメモリモジュール番号は次のようになる。

0113

SEB(k) = ((0) + kr)%m、 pq ≦ k < m (103)
SWB(k) = (μ(0) + (q・(k/q) - (k%q))・r)%m、 pq ≦ k < m (104)
NWB(k) = (μ(0) - kr)%m、 pq ≦ k < m (105)
NEB(k) = (μ(0) - (q・(k/q) - (k%q))・r)%m、 pq ≦ k < m (106)
EL(k) = (μ(0) + kr)%m、 pq ≦ k < m (107)
SEL(k) = (μ(0) + (q+1)kr)%m、 pq ≦ k < m (108)
SL(k) = (μ(0) + qkr)%m、 pq ≦ k < m (109)
SWL(k) = (μ(0) + (q-1)kr)%m、 pq ≦ k < m (110)
WL(k) = (μ(0) - kr)%m、 pq ≦ k < m (111)
NWL(k) = (μ(0) - (q+1)kr)%m、 pq ≦ k < m (112)
NL(k) = (μ(0) - qkr)%m、 pq ≦ k < m (113)
NEL(k) = (μ(0) - (q-1)kr)%m、 pq ≦ k < m (114)
ここで、μ(0)は(i、j)である。

0114

前記の式(103)〜(114)にある(m-pq)個の番号が(m-pq)個のデコーダーに与えられると、デコーダーの該当の反転結果をOR演算したm個の結果はm個のメモリモジュールのアクセスを制御する。

0115

特に、m=pq+1に対して、式(103)~(114)内のkをpqで代置して得たアクセスされないメモリモジュール番号の一つをデコーダーに提供し、m個の反転されたデコーダーの結果はpq個のアクセスされるメモリモジュールのアクセス信号とアクセスされないメモリモジュールの非アクセス信号で使われる。

0116

アドレス計算、ルーティング及びメモリモジュールの例
図6はp=q=2、M×N=32×32及びm=5である時、メモリモジュール割り当て関数によって割り当てされた各データのメモリモジュール番号を示す。図7はp=q=2、M×N=32×32、及びs=16である時、アドレス割り当て関数によって割り当てされた各データのアドレスを示す。図8はp=q=2、M×N=32×32、s=16、及びm=5に対するアドレス計算回路とアドレスルーティング回路を示す図である。ここで使われた12種のアクセス形態と間隔r=1、2、3、4のメモリモジュールAとBのアドレス間差は図9に示されている。本発明でのアドレス計算及びアドレスルーティング、及びメモリモジュール選択方法が下記の例でわかる。

0117

(例1)間隔1である位置(14、15)の南東側ブロック(SEB)に対して、行優先順位に変更されたI(14、15)、I(14、16)、I(15、15)、I(15、16)のメモリモジュール番号μ(k) =(3、4、0、1)を図7から求めることができ、アドレスα(k)=(119、120、119、120)を図7から求めてメモリモジュール番号に従ってアドレスを整列すると、α(μ)=(119、120、×、119、120)となる。ここでの×はアクセスされないメモリモジュール番号2を意味する。本発明によるアドレス計算、アドレスルーティング及びメモリモジュール選択方法の過程は下記のようである。

0118

i%p = 0、j%q = 1、r = 1に対して次のようにアドレス間差が求められる。

0119

ASEB(μ+μ(0))%m = (0、0、0、0、16)各加算器の入力B+(0、1、0、1、0)各加算器の入力C
= (0、1、0、1、16) (図9から)
求められたアドレス間差に基準アドレスを適用して下記のことを得ることができる。

0120

α(k) =α(0) (=119)+ASEB(μ+μ(0))
= (119、120、119、120、135)
このアドレスをμ(0)(=3)によって右側に回転すると次のように求められる。

0121

α(μ) = (119、120、135、119、120)
式(103)で求められた((i、j)+kr)%m = (3+4)%5 = 2番のモジュールがアクセスされないモジュールなので、前記と同じ結果である(119、120、×、119、120)が求められる。

0122

他の例は表5a及び表5bに現われている。

0123

0124

ID=000009HE=090 WI=132 LX=0390 LY=0300
テキストイメージの速やかで正確な修正ディスプレーに対する多い要請によって高速高解像度グラフィックディスプレー装置に対する需要が増加している。従来のグラフィックディスプレー装置は修正とディスプレーをするために、2次元映像アレイを含むバッファーメモリ装置を用いる。グラフィックディスプレー装置はメインコンピューターの命令に従ってバッファーメモリ装置の映像点を新しく修正する。バッファーメモリ装置から映像点を読んでレスタースキャニングの形態によりディスプレーに映像点を送る。高速の高解像度グラフィックディスプレー装置でバッファーメモリ装置内容の修正時間を減少するための高速のバッファーメモリ装置が要求される。一つの記憶チップに含まれるビット数チップ技術の発展によって増加している。だから、多くのアクセス形態による多くの映像点の並列的なアクセスのために大容量の単一メモリモジュールに対して、アクセス時間を減少することより、相対的に容量は少なくとしても、一つの記憶チップに入れ込まれるメモリモジュール数を増加することが高速のバッファーメモリ装置のために望ましい。それで、バッファーメモリ装置の内容を修正する時間を減少するための映像アクセス形態による多くの映像点を並列的にアクセスするバッファーメモリ装置が必要となる。

0125

以下、グラフィックディスプレー装置のバッファーメモリ装置のために使われるブロック、水平、垂直、対角線、逆対角線アクセス形態を持つメモリ装置に対して、調べながら従来のメモリ装置と比べる。

0126

ブロック、水平、垂直、対角線、逆対角線アクセス形態のためのメモリ装置高速の高解像度グラフィックディスプレー装置のための效率的なバッファーメモリ装置を調べる。このメモリ装置は二次元映像においてブロック(p×q)、水平(1×pq)、垂直(pq×1)、対角線、逆対角線アクセス形態のpq個の映像点に対して並列アクセスを提供する。

0127

ここで、媒介変数pとqは全部2の乗数である。

0128

図10に示すグラフィックディスプレー装置は一般的にメインコンピューター、ディスプレー処理器、バッファーメモリ装置(100)、ビデオ生成器及びディスプレーで構成される。ディスプレー処理器はメインコンピューターの命令によってバッファーメモリ装置内の映像点を新しく修正する。

0129

ビデオ生成器はバッファーメモリ装置から映像点を読み出してレスタースキャニング形態にディスプレーに送る。M×N大きさの映像データで映像点に対するアクセス時間を減少するため、グラフィックディスプレー装置内のM×N映像内でpq個の映像点を並列にアクセスするためのバッファーメモリ装置が必要となる。表6は従来のグラフィックディスプレーにおける表示領域の多様な大きさを示す。バッファーメモリ装置の大きさは少なくとも特定なディスプレー装置における表示領域の大きさと同じでなければならない。

0130

ID=000010HE=065 WI=078 LX=0210 LY=0300
例えば、960(ライン数)×1280(ライン当たりの映像点数)のディスプレーに対して、M×Nの最小値はそれぞれ960と1280である。それで、多くのグラフィック装置N値は2の乗数ではない値を用いる。

0131

バッファーメモリ装置(100)は、水平線型、垂直線型、または一文字に対する書き時間を減少するために、水平、垂直、またはブロック形態の映像点を並列にアクセスしなければならない。追加的に対角線や逆対角線の映像点に対する並列的なアクセスは45°ずつ整数倍の線型形態の映像データに書き時間を減少させるとか、45°ずつ整数倍で回転させるために必要となる。だから、バッファーメモリ装置(100)における修正速度の向上のために、バッファーメモリ装置(100)はM×N映像i(*、*)内の基準座標(i、j)で、ブロック(BL)、水平(HR)、垂直(VR)、対角線(FD)、または逆対角線(BD)アクセス形態に対しての次のようなpq個の映像点に対する並列的なアクセスを提供しなければならない。

0132

BL(i、j) = {I(i+a、j+b) | 0 ≦ a < p、0 ≦ b < q}、0 ≦ i ≦ M-p、0 ≦
j ≦ N-q (115)
HR(i、j) = {I(i、j+a) | 0 ≦ a < pq}、0 ≦ i ≦ M-1、0 ≦ j ≦ N-pq
(116)
VR(i、j) = {I(i+a、j) | 0 ≦ a < pq}、0 ≦ i ≦ M-pq、0 ≦ j ≦ N-1
(117)
FD(i、j) = {I(i+a、j+a) | 0 ≦ a < pq}、0 ≦ i ≦ M-pq、0 ≦ j ≦ N-pq

(118)
BD(i、j) = {I(i+a、j-a) | 0 ≦ a < pq}、0 ≦ i ≦ M-pq、pq - 1 ≦ j ≦
N-1
(119)
図11は基準座標(i、j)を持つ前記のアクセス形態を示す。ここで基準座標は基準映像点I(i、j)の座標を意味する。映像点を修正しようとする時、図11にあるバッファーメモリ装置の構成要素はディスプレー処理器の要請によって制御回路の制御により次の演算を順次的に行う。

0133

1.レジスターt、i、jはディスプレー処理器によるデータのアクセス形態(ブロックは1、水平は2、垂直は3、対角線は4、逆対角線は5である)の選択tとアクセス形態(1)~(5)によって要求された基準座標(i、j)が入れ込まれ、データ自体は行優先順位のデータレジスターに位置する。

0134

2.アドレス計算とルーティング回路(ACRC)はm個の映像点のアドレスを計算し、その値をm個のメモリモジュールにルーティングさせる。

0135

3.メモリモジュール選択回路はアクセスされるpq個のメモリモジュールを選択する。

0136

4. データルーティング回路はデータレジスターにあるpq個の映像点をm個のメモリモジュールにルーティングさせる。

0137

5. 書き信号はpq個の選択されたメモリモジュールに映像点を貯蔵する。

0138

ここで、演算2、3、4が並列的に行われる。

0139

同様にバッファーメモリ装置から映像点を読み取る時、バッファーメモリ装置の構成要素は次のような演算を順次的に行う。

0140

1. t、i、jレジスターに要請された値を入れ込む。

0141

2.アドレス計算とルーティング回路(ACRC)がm個の映像点アドレスを計算し、その値はm個のメモリモジュールにルーティングさせる。

0142

3.メモリモジュール選択回路はアクセスされるpq個のメモリモジュールを選択する。

0143

4. 読み信号によってpq個の選択されたメモリモジュールから映像点を読み取る。

0144

5. データルーティング回路はm個のメモリモジュールからpq個の映像点をデータレジスターにルーティングし、アクセス形態(1)~(5)の選択によって行優先順位となっているpq個の映像点を整列する。

0145

ここで演算2と3が並列に行われる。

0146

図12は本発明によるアドレス計算とルーティング回路を示す。

0147

アドレス計算とルーティング回路はアドレス間差のために2個のSRAM、4個の5×1MUX、(m+3)個の加算器、(i/p)値のためのSRAM、及びバレルシフターで構成されている。

0148

ブロック、水平、対角線、逆対角線アクセス形態におけるアドレス間差の1番目間隔はμ(0≦μ< m)のi%p値によってp個の差の値で示される。水平アクセス形態におけるアドレス間差の1番目間隔はμ(0 ≦μ< m)のi%p値による変化はない。ブロック、水平、対角線、逆対角線アクセス形態におけるアドレス間差の2番目間隔はμ(0≦μ< m)のj%p値によってq個の差が二進数の値で示される。

0149

垂直アクセス形態におけるアドレス間差の2番目間隔はμ(0≦μ< m)のj%q値による変化はない。だから、アドレス間差のために1番目SRAMはアクセス形態とi%p値によってアクセスされてm個の加算器にB入力で提供される。そして、アドレス間差のために2番目SRAMはアクセス形態とj%q値によってアクセスされてm個の加算器にC入力で提供される。ここでアドレス間差のために1番目と2番目SRAMの大きさはそれぞれ(4p+1)×m×log2(MN / pq)ビットと(4q+1)×mビットである。

0150

図12におけるアドレス間差のための1番目SRAMの選択されたアドレスは、ブロックアクセス形態の0番目p×m個のアドレス間差のためのt・p+i%p、水平アクセス形態の1番目1×m個のアドレス間差のためのt・p、そして垂直、対角線、逆対角線アクセス形態の2番目、3番目、4番目p×m個のアドレス間差のための((p-1)の2の補数)+ t・p+i%p)即ち(t・p+i%p-( p-1 )である。

0151

アドレス間差のために2番目SRAMの選択されたアドレスは、ブロックと水平アクセス形態の0番目と1番目q×m個のアドレス間差のための(t・q+j%q)、垂直アクセス形態の2番目である1×m個のアドレス間差のための(t・p)、そして対角線と逆対角線アクセス形態の3番目と4番目アドレス間差のための(t・q+j%q+((q-1)の2の補修))即ち(t・q+j%q - (q-1))である。

0152

(t・p+i%p)と(t・q+j%q)の値はpとqが全部2の乗数である時、掛け算や足し算なしに、それぞれ (t・p)、(i%p)、(t・q)、(j%q)の連結によって簡単に求めることができる。

0153

基準アドレスα(i、j)の計算に必要な一度の掛け算(i/p)s値のためにSRAMアクセスで代理する。もし基本アドレス計算での一度の掛け算を除くためにNが2の乗数ではないのに、sを2の乗数になるよう選択したら、M×N=960×1280の映像でアクセスされる部分の60%であるq (s -(N/qで整数部分と同じ或いはより大きな整数)) Mが使われないメモリ装置領域で追加された容量である。

0154

本発明によるアドレス計算とルーティング回路ではsが2の乗数ではない時、SRAMのアクセスで得られた(i/p)s値に基準アドレスのためにj/q値を加える。sが2の乗数である時は(i/p)sの値にi値の最下位ビットにlog2(s/p)ぐらいの0を追加して求める。i/pとj/q値の合計はm個の加算器にA入力で提供される。

0155

以下、アドレス計算及びアドレスルーティングに対して本発明によるハードウェアルゴリズムをハードウェア価格、制御の複雑性、速度などの事項を従来のメモリ装置(D. C. Van Voorhis and T. H. Morrin、IEEE Trans. Comput.、vol.C-27、 pp.113-125、 Feb. 1978.、 J. W. Park、IEEE Trans. Comput.、vol.C-35、 pp.669-674、 July 1986.、D. H. Lawrie and C. R. Vora、 IEEE Trans. Comput .、 vol. C-31、 pp.435-442、 May 1982.、J. W. Park and D. T. Harper III、IEEE Symp. Parallel and Distributed Processing 、 pp.444-451、 Dec. 1992.、J. W. Park and D. T. Harper III、IEEE Trans. Parallel Distrib. Syst.、vol. 7、No. 8、pp.855-860、Aug. 1996.)と比べる。

0156

この比べではデータ内における任意の位置にある少なくとも3種のアクセス形態データの並列アクセスが支援され、アドレス計算及びアドレスルーティング回路のハードウェア具現が考察される。バンブーリスとモリン(D. C. Van Voorhisand T. H. Morrin、IEEE Trans. Comput .、 vol. C-27、 pp.113-125、 Feb.1978.)、ローリとボラ(D. H. Lawrie and C. R. Vora、 IEEE Trans. Comput .、vol. C-31、pp.435-442、May 1982.)が提案したメモリ装置では各メモリモジュールμ(0 ≦ μ< m)のアドレスα(μ)を直接計算する。アドレス計算とルーティング回路(D. C. Van Voorhis and T. H. Morrin、 IEEE Trans. Comput .、 vol. C-27、 pp.113-125、 Feb. 1978.、 D. H. Lawrie and C. R. Vora、 IEEETrans. Comput .、 vol. C-31、 pp.435-442、 May 1982.)ではアドレス計算がアドレスルーティングでの回転と分離されないので制御が複雑で費用が上昇する。 アドレス計算とルーティング回路(D. H. Lawrie and C. R. Vora、IEEE Trans. Comput .、vol. C-31、pp.435-442、May 1982.)は各メモリモジュールkに対してブロック、水平、垂直アクセス形態それぞれのα(μ)である(i+((k-(i、j))%m)/q、j+((k-(i、j))/m)%q)、(i、j+(k-(i、j))/m)、(i+(p((i、j)-k))%m、j)を計算する。

0157

だから表7に示すように1番目行に現われたハードウェアの構成要素と演算遅延時間がメモリ装置(D. C. Van Voorhis and T. H. Morrin、IEEE Trans. Comput.、vol. C-27、 pp.113-125、 Feb. 1978.)でm個のメモリモジュールに対して、α(μ)が可能だったら速やかに計算されるのに必要となる。

0158

ID=000011HE=165 WI=139 LX=0355 LY=0300
このメモリ装置(D. H. Lawrie and C. R. Vora、IEEE Trans. Comput .、vol.C-31、 pp.435-442、 May 1982.)でのBSDに対して、α(μ)の計算とルーティングのため、メモリモジュールが17個、プロセッサが16個である時、表7の2番目行にあるハードウェアの構成要素と演算遅延時間が必要となる。パク(J. W. Park、 IEEE Trans. Comput .、 vol. C-35、 pp.669-674、 July 1986)、 パクとハーパ(J. W. Park and D. T. Harper III、 IEEE Symp. Parallel and Distributed Processing 、 pp.444-451、 Dec. 1992.、J. W. Park and D. T. Harper III、IEEE Trans. Parallel Distrib. Syst..、vol. 7、No. 8、pp.855-860、Aug.1996.)によって提案されたメモリ装置でのアドレス計算はアドレスルーティングと分離される。パクのメモリ装置(J. W. Park、 IEEE Trans. Comput .、 vol. C-35、 pp.669-674、 July 1986.)のアドレス計算回路(ACC)は、加算器アレイで一度の足し算時間を要求するa(i、j)、(0、s、またはk、k=0、...、(p-1))、及び(0、1)の足し算によってブロックアクセス形態と水平アクセス形態のpq個のアドレスを計算し、2度の足し算時間を要求するα(i、j)、(0またはs)、及び (ks、k=0、...(q-1))の足し算によって垂直アクセス形態のpq個のアドレスを計算する。

0159

アドレスルーティング回路(ARC)は、まず二度のルーティングによって垂直アクセス形態の(iq+j-1)%(pq+1)や垂直アクセス形態の(iq+j-q)%(pq+1)の数によって整列されたアドレスを右側に回転する。

0160

このメモリ装置(J. W. Park、IEEE Trans. Comput .、vol. C-35、pp.669-674、July 1986)ではm個メモリモジュールのためのα(μ)を計算するために表7の3番目行のハードウェア構成要素と演算遅延時間が必要となる。

0161

他のメモリ装置(J. W. Park and D. T. Harper III、IEEE Symp. Parallel and Distributed Processing 、 pp.444-451、 Dec. 1992.、 J. W. Park and D.T. Harper III、 IEEE Trans. Parallel Distrib. Syst ..、 vol. 7、 No. 8、pp.855-860、 Aug. 1996.)のアドレス計算回路(ACC)は1番目SRAMのアドレス間差と2番目SRAMのアドレス間差である(i、j)の足し算で一度の足し算時間内にブロック、水平、または垂直アクセス形態のpq個アドレスが計算される。pq個の加算器に入力される入力Bに対するアドレス間差の大きさは3種のアクセス形態の全部がp×pqである。

0162

M個の加算器の入力Cに対するアドレス計算回路(ACC)のアドレス間差の大きさは、ブロックアクセス形態のアドレス間で差がi%pだけでなく、j%qに従属するからブロックアクセス形態に対してはq×qである。それで、アドレス計算回路の1番目SRAMと2番目SRAMの大きさは5種のアクセス形態(115)~(119)に対して5p×pqと3q×qぐらいになる。アドレスルーティング回路は、まずメモリモジュール番号によってブロック、水平、または垂直アクセス形態のpq個のアドレスを整列した後、ブロック、水平、または垂直アクセス形態に対して(iq+j)%(pq+1)ぐらい右側に回転する。だから、このメモリ装置でα(μ)を計算するため、表7の4番目行のハードウェア構成要素と演算遅延時間が必要となる。アドレス計算とルーティング回路の短所はアクセス形態に従うアドレスの計算の後、メモリモジュール番号に従って複雑に整列しなければならないことである。それはアドレス計算回路で出力されたアドレスがメモリモジュール番号に従って整列されていないからである。それに比べて本発明で提案されたメモリ装置ではα(μ)を計算するにおいて、表7の5番目行のハードウェア構成要素と演算遅延時間が必要となる。その時、出力アドレスはμ(i、j)からメモリモジュール番号によって整列されている。前記の回路(J. W. Park and D. T. Harper III、IEEE Symp.、Parallel andDistributed Processing、 pp.444-451、 Dec. 1992.、 J. W. Park and D. T.Harper III、 IEEE Trans. Parallel Distrib. Syst.、 vol. 7、 No. 8、 pp.855-860、 Aug. 1996.)と比べると、本発明によるアドレス計算及びデータルーティング回路の重要な利点は速度側面で掛け算器の代わりにSRAMに代置したことと、マルチプレクサーを除いて制御の簡便化とゲートの数を減少させ、アドレス間差の大きさを(4p+q)×pq×log2(MN / pq) j+3q×qのビットから(4p+1)×m×log2(MN / pq)+(4q+1)×mに減少させたことである。

0163

一般的な字の大きさが8×8と同じとか大きいとする時、グラフィックディスプレーの良い性能のためには少なくともp=8、q=8でなければならない。また、pqの値はMとN間にある最小値の同じとか小さくなければならない。

0164

アドレス計算とルーティング回路のハードウェア構成要素と演算遅延時間をM×N×b = 960×1280×24である時、p = q = 8、m = 7である場合とp = q = 16、m = 257である場合に対して表8で比べる。

0165

ID=000012HE=145 WI=132 LX=0390 LY=0300
前記のメモリ装置(J. W. Park and D. T. Harper III、IEEE Symp. Paralleland Distributed Processing 、 pp.444-451、 Dec. 1992.、 J. W. Park andD. T. Harper III、 IEEE Trans. Parallel Distrib. Syst.、 vol. 7、 No. 8、 pp.855-860、 Aug. 1996.)の掛け算器回路の演算速度を向上のための本発明によるメモリ装置ではSRAMで代置した。1ビット5×1マルチプレクサー一つのゲート数が12であり、全体加算器一つのゲート数が7だと仮定すると、m×log2(MN/ pq)ビットの5×1マルチプレクサーのゲート数が12であり、一つの全体加算器のゲート数は全体加算器、即ち、1og2(4p+1)ビットの加算器一個+1og2(4q+1)ビットの加算器一個+1og2(MN / pq)ビットの加算器(pq+1)個のゲート数よりずっと多い。

0166

そのような構成要素を持つ従来のメモリ装置と比べて、本発明によるアドレス計算とルーティング回路はアドレス計算の後にメモリモジュール番号に従ってアドレスを整列するための5×1マルチプレクサーが必要とならないので制御が簡単で費用が少なくなる。また、(pq + 1)個の加算器には5×1マルチプレクサーの間に5m×log2(MN / pq)個の線が連結されているのに、p = q = 8である時及びp =q = 16である時、全体的な線の数がそれぞれ5,025個と16,705個なので、(pq+1)個の加算器から5×1マルチプレクサーまでのルーティング回路の具現と制御は非常に複雑である。従来のアドレス計算とルーティング回路にはマルチプレクサーとアドレス間差のためのSRAMにおける加算器の間に2pq×log2(MN / pq)+pq個の線があり、m個のマルチプレッサーとm個のバレルシフターとの間にある。また、従来のアドレス計算とルーティング回路においてm個のバレルシフターで、m個のメモリモジュールの間の線数はm×log2(MN/pq)である。しかし、本発明によるアドレス計算とルーティング回路での全体線の数は4m×log2(MN/pq)で従来の半分より少ない。

0167

表9はアドレス計算とルーティング回路のゲート数を三星電子ASICであるKG76(0.6mゲートアレイライブラリ)のゲート数により比べた例である。

0168

ID=000013HE=090 WI=135 LX=0375 LY=0300
演算遅延時間がM×N×b = 960×1280×24であり、pq > Mである時、媒介変数pとq値双方が32ではない8と32間の2の乗数である値を持つように設計した表10の演算遅延時間の仮定下で比べた。

0169

ID=000014HE=095 WI=088 LX=0610 LY=1350
ゲート数の割合と演算遅延時間の割合は従来のアドレス計算とルーティング回路のゲート数と演算遅延時間に対する本発明によるアドレス計算とルーティング回路それぞれの割合である。平均ゲート数の割合と平均演算遅延時間の割合はそれぞれ1,198と1,295である。 ゲート数の割合と演算遅延時間の割合を掛け平均値は1,549である。本発明によるアドレス計算とルーティング回路に対して標準化されたゲート数はp=q=8に対してゲート数で分けられ、また、pq/64によって分けられたゲート数である。そして、演算遅延時間はp = q = 8である時の演算遅延時間でそれぞれ分けたことである。標準化された結果は標準化されたゲート数と演算遅延時間を掛けることで求めることができる。標準化された結果に従って本発明によるアドレス計算とルーティング回路のための1番良いpとq値はそれぞれ8と8である。その値が標準化された結果がM×N×b = 960×1280×24で一番小さい値であるためである。標準化された結果は要求されたアドレス計算とルーティング回路に対して一番良いpとq値を選択するのに使うことができる。表11は要求された|(p1、q1)|と1番良い|(p2、q2)|を選択して使った構成を示す。この時、|(p1、q1)|は製作パラメーターがp1とq1であるバッファーメモリ装置を示す。

0170

ID=000015HE=080 WI=104 LX=0530 LY=0400
ここで、|(p1、q1)|と|(p2、q2)|はバッファーメモリ装置のpとq値をp1とq1、p2とq2で示す。

0171

例えば、 |(32、8)|のアドレス計算とルーティング回路が要求されると、4個の|(8、8)|のアドレス計算とルーティング回路が要求されたアドレス計算とルーティング回路で組み合わせて使うことができる。もし|(8、16)|、|(16、8)|、|(16、16)|、|(8、32)|、|(32、8)|、|(16、32)|、|(32、16)|のアドレス計算とルーティング回路を|(8、8)|のアドレス計算とルーティング回路を用いて構成すると、1.353の平均演算遅延時間の割合内の結果で演算遅延時間の割合が1.353に増加される。

0172

データルーティング回路は一度のモジュロ計算と一度の回転演算を行って、メモリモジュール選択回路は一度のモジュロ計算と一度のデコーディング演算を行うため、データルーティング回路やメモリモジュール選択回路の演算遅延時間は本発明によるアドレス計算とルーティング回路の演算遅延時間より短い。だから、もしm個のメモリモジュールアクセス時間が本発明によるアドレス計算とルーティング回路の演算遅延時間より小さく、アドレス計算とルーティング回路のm個のメモリモジュールの間にm個のメモリ装置アドレスレジスターがあり、データルーティング回路とm個のメモリモジュールの間にm個のメモリ装置バッファーレジスターがあるとしたら、本発明によるバッファーメモリ装置はアドレス計算とルーティング回路の演算遅延時間の割合単位のパイプライン方式で行うことができる。

0173

また、ディスプレー処理器が本発明によるアドレス計算とルーティング回路の演算遅延時間内のバッファーメモリ装置からpq個の映像点に対して要素演算を行うと、本発明によるフレームバッファーディスプレー装置の全体的な性能は従来のアドレス計算とルーティング回路を使ったフレームバッファーディスプレー装置より平均1.353倍増加することができる。だから、本発明によるアドレス計算とルーティング回路は従来のメモリ装置より費用を少なくし、制御の複雑性を減少し、速やかにする。

0174

以下、少なくともデータアレイ内の任意の位置にある3種のアクセス類型のデータに対して同時アクセスが支援され、アドレス計算回路とアドレスルーティング回路、データルーティング回路のハードウェア具現が考慮されている従来のメモリ装置方式と本発明によるアドレス計算及びアドレスルーティング、データルーティング方式をアクセス類型、間隔、データアレイの大きさの制限とハードウェアの費用、速度、複雑性に対して比べた。

0175

間隔1を持つブロック、列、行、対角線、逆対角線アクセス形態のための本発明によるアドレス計算とルーティング回路は、従来のメモリ装置に比べてより低費用、更に単純化された制御複雑度、及びそして速やかな速度を持つことができる。

0176

pq≦ mdでありmが素数である時に従来のメモリ装置(A. Deb、IEEE Trans. Parallel Distrib. Syst.、 Vol. 7、No. 6. pp. 595-604、Jun. 1996.)はm個のメモリモジュールとpq個のプロセッシングエレメントで構成されている。ローリとボラ(D. H. Lawrie and C. R. Vora、IEEE Trans. Comput .、vol. C-31、 pp.435-442、 May 1982.)は線型pqベクトルV(a、b、c、d)で下記の線型数式によって形成されたアレイ要素のpq要素集合を定義した。

0177

V(a、b、c、e) = {A(i、 j): i = ax+b、 j = cx+e}、 0 ≦ x < pq ≦ m
ローリとボラ( D. H. Lawrie and C. R. Vora、IEEE Trans. Comput .、 vol. C-31、 pp.435-442、 May 1982.)はα(μ)、即ち番目モジュールのアドレスを求めた。

0178

α(μ) = ((a+cM) ((-(b+eM+base))d' %m)+b+eM+base) / pq 、
ここで、(a+cM)・d' = 1%mであり、"base "はデータアレイの基準アドレス(i、j)であり、Mはアレイの行の数である。

0179

(a+cM)・d' =1%mからd'はmの倍数である間隔M、M+1、M-1のどんな場合でも求めることができない。なぜなら、aとcの値が下記のように各アクセス形態に正義されているからである。

0180

行: a = 0でc =陽数間隔
列: c = 0でa =陽数間隔
対角線: a = c =陽数間隔
そして、
逆対角線: a =-c =陽数間隔
だから、このメモリ装置( D. H. Lawrie and C. R. Vora、IEEE Trans. Comput .、 vol. C-31、 pp.435-442、 May 1982.)は間隔とデータアレイの大きさとメモリモジュール数に制約がある。

0181

一方、従来のメモリ装置と異なって、発明によるメモリ装置はデータアレイの大きさに対する制約がない。 ただ、本発明によるメモリ装置の制約は理論1から間隔がメモリモジュール個数の倍数ではなくにしなければならないということである。従来のメモリ装置(J. W. Park、IEEE Trans. Comput.、 vol. C-35、pp.669-674、July 1986.、 J. W. Park and D. T. Harper III、IEEE Symp.Parallel and Distributed Processing、pp.444-451、 Dec. 1992.、 J. W. Park and D. T. Harper III、 IEEE Trans. Parallel Distrib. Syst ..、 vol. 7、 No. 8、 pp.855-860、 Aug. 1996.)にあったμ(i、j)による右側回転の前に、アドレスを整列するための一つのマルチプレクサーとマルチプレクシング演算時間が本発明によるアドレス計算回路とアドレスルーティング回路ではアドレス間差が予め整列されているから必要ではない。もしマルチプレクサーが12種のアクセス形態に対してアドレス計算及びアドレスルーティング方法(J. W. Park、IEEE Trans. Comput .、 vol. C-35、 pp.669-674、 July 1986.、 J. W. Parkand D. T. Harper III、 IEEE Symp. Parallel and Distributed Processing 、pp.444-451、Dec. 1992.、 J. W. Park and D. T. Harper III、 IEEE Trans.Parallel Distrib. Syst.、vol. 7、No. 8、pp.855-860、 Aug. 1996.)に使われと制御が非常に複雑になるはずである。それはアクセス形態と間隔がアドレスの整列に従属するからである。メモリ装置(D. C. Van Voorhis and T. H. Morrin、 IEEE Trans. Comput.、 vol. C-27、 pp.113-125、 Feb. 1978.)でのデータルーティング回路はμ(i、j)によって制御される多様な右側回転変換器が必要となる。パク(J. W. Park、 IEEE Trans. Comput .、 vol. C-35、 pp.669-674、July 1986)、 パクとハーパ(J. W. Park and D. T. Harper III、 IEEE Symp. Parallel and Distributed Processing、 pp.444-451、 Dec. 1992.、 J. W. Park and D. T. Harper III、 IEEE Trans. Parallel Distrib. Syst.、vol. 7、No. 8、pp.855-860、Aug. 1996.)によって本発明によるメモリ装置のデータルーティングはマルチプレクサーとバレルシフターによって行われる。このメモリ装置では従来メモリ装置のデータルーティング回路内の多様な右側回転変換器を複雑で高くて遅いクロースバーネットワークで代置する。本発明ではマルチプレクシングと回転を使うデータルーティング方法が提案された。

0182

ここで、12種のアクセス形態に対して陽の間隔を持つ12種のデータルーティング形態がROMとlog2(2(m-1))×2(m-1)デコーダー、3相バッファーを用いたセレクター、そしてバレルシフターによって具現された間隔r1(=r%m)である2個のルーティング形態に減少される。また、表11によって、本発明によるアドレス計算、アドレスルーティング、及びデータルーティング回路は更に多いアクセス類型と間隔を支援する。

0183

よって、アドレス計算、アドレスルーティング及びデータルーティングにおいて、本発明による方法はアクセス形態、間隔及びデータアレイの大きさに対する制約とハードウェアの費用、速度及び複雑性の側面で従来のメモリ装置の方法より良いということが分かる。

発明の効果

0184

以上で説明したように本発明による衝突のフリのメモリ装置は従来メモリ装置より改善があった。一つのデータアレイ内に任意の位置にある少なくとも3種のアクセス形態のデータ要素に対する同時アクセスが支援される。更に、アクセス形態、間隔およびデータアレイ大きさの制約とハードウェア費用、速度、複雑性の制限内でメモリ装置内のアドレス計算及びアドレスルーティング回路、及びデータルーティング回路のハードウェア具現が考慮された。

0185

多様な行列演算と映像処理演算はpq個のプロセッシングエレメントを持つSIMD処理器とm(mは素数、m>pq)個のメモリモジュールを持つメモリ装置によって速度を向上することができる。

0186

SIMD処理器は間隔、データアレイの大きさ、データ要素の位置に制約がないデータアレイ内の陽数間隔を持つ多様な形態の四角形ブロックと8方向線型アクセス形態のpq個のデータ要素がアクセスされるメモリ装置が必要となる。

0187

本発明による素数個のメモリモジュールを持つ衝突防止メモリ装置は4方向四角形ブロック陽数の間隔に連関されたデータ要素がデータアレイ内のどの位置に置かれるが(南東側ブロック、南西側ブロック、北西側ブロック、北東側ブロック)、または8方向の線型(東側線型、南東側線型、南側線型、南西側線型、西側線型、北西側線型、北線型、北東側線型)アクセス形態のpq個データ要素に同時アクセスを支援することができる。

図面の簡単な説明

0188

図1メインコンピューターと取り付けられた多重SIMDコンピューターの関係を示す例示図である。
図2a 方向ブロックのアクセス形態、間隔及び基準座標の例示図である。
図2b 8方向線型のアクセス形態、間隔及び基準座標の例示図である。
図3衝突防止メモリ装置の一般的な設計の例示図である。
図4データルーティング回路の詳細な回路図である。
図5a 8×8逆オメガネットワークのスイッチング要素の経路衝突の例示図である。
図5b N = 16セータネットワークのスイッチング要素の経路衝突の例示図である。
図6μ(i、j)=(iq+j)%m、p=q=2とM×N = 32×32、m=5に対するメモリモジュール割り当て関数によって割り当てられたメモリモジュール番号の例示図である。
図7p=q=2、M×N = 32×32及びs=16に対するアドレス割り当て関数α(i、j)=(i/p)s+j/qによって割り当てられたアドレスである。
図8p=q=2、M×N = 32×32、s=16及びm=5に対するアドレス計算とルーティング回路の例示図である。
図9p=q=2、M×N = 32×32及びs=16に対するメモリモジュールAとBの例示図である。
図10本発明によるメモリ装置を適用したグラフィックディスプレー装置の構成を概略的に示すブロック図である。
図11アクセス形態と基準座標の例示図である。
図12本発明によるアドレス計算とルーティング回路(ACRC)の詳細な回路図である。

--

0189

100バッファーメモリ装置

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い 技術一覧

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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