(57)【特許請求の範囲】
【請求項１】
ｐｑ個のデータ要素を同時処理するｐｑ個の処理要素を有するＳＩＭＤ（Ｓｉｎｇｌｅ−Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ−Ｄａｔａ）ストリームプロセッサのメモリシステムとして利用可能であり、前記メモリシステムへのアクセス時間を低減することが可能なコンフリクトフリーメモリシステムであって、
ｍ個のメモリモジュール（ただし、ｍ＞ｐｑ）と、
ｍ個のデータ要素のｍ個のアドレスを計算し、その値をｍ個のメモリモジュールにルーティングし、ベース座標（ｉ，ｊ）のメモリモジュールのインデックス番号であるμ（ｉ，ｊ）を計算する回路と、ベース座標（ｉ，ｊ）のアドレスであるベースアドレスα（ｉ，ｊ）を計算するベースアドレス計算回路と、各サブアレイタイプに対し、予め整列されたｐ×ｍ個のアドレス間差とｑ×ｍ個のアドレス間差をそれぞれ格納するメモリモジュールＡ及びＢと（ただし、ｍ個のアドレス間差は、ｍ個のアドレスからベースアドレスを差し引くことにより計算され、μ（ｉ，ｊ）から始まりメモリモジュールのインデックス番号の昇順に予め整列される）、ｍ個のアドレスをμ（ｉ，ｊ）から始まりメモリモジュールのインデックス番号の昇順により生成するｍ個の加算器と、前記ｍ個のアドレスを０から始まりメモリモジュールのインデックス番号の昇順となるよう前記ｍ個のアドレスを生成するため、前記ｍ個の加算器の出力をμ（ｉ，ｊ）回だけ回転させ、前記ｍ個の加算器の出力をｍ個のメモリモジュールに供給するバレルシフタとから構成されるアドレス計算ルーティング回路と、
ｍ個のメモリモジュールからアクセスされるｐｑ個のメモリモジュールを選択するメモリモジュール選択回路と、
前記ｐｑ個の処理要素により処理される前記ｐｑ個のデータ要素をデータアレイの一部であるサブアレイに格納するデータレジスタと、
ライト処理に対しては、前記ｐｑ個のデータ要素の前記メモリモジュールのｐｑ個のインデックス番号を０から始まり前記メモリモジュールのインデックス番号の昇順となるよう整列した後、前記データレジスタのｐｑ個のデータ要素を前記ｍ個のメモリモジュールにルーティングし、リード処理に対しては、前記ｐｑ個のデータ要素のメモリモジュールのｐｑ個のインデックス番号をμ（ｉ＋ａ，ｊ＋ｂ）となるよう整列した後（ただし、ａとｂは、サブアレイ内の相対位置を表す）、前記ｐｑ個のデータ要素を前記ｍ個のメモリモジュールから前記データレジスタにルーティングするデータルーティング回路と、
から構成され、
当該コンフリクトフリーメモリシステムは、各々がデータアレイ内部の何れかに位置するサブアレイである、南東ブロック、南西ブロック、北西ブロック及び北東ブロックの４方向矩形ブロックと、東ライン、南東ライン、南ライン、南西ライン、西ライン、北西ライン、北ライン及び北東ラインの８方向ラインとからなる１２のサブアレイタイプの１つの内部のｐｑ個のデータ要素への同時アクセスをサポートし、
サブアレイ内の任意の連続する２つのデータ要素の間の距離は、ｍの倍数に等しくない正の整数であるインターバル情報により表され、
前記１２のサブアレイタイプの１つの内部のｐｑ個のデータ要素のメモリモジュールのｐｑ個のインデックス番号は、関数μ（ｉ＋ａ，ｊ＋ｂ）により異なって割当てられ（ただし、ａとｂは、サブアレイ内の相対位置を表す）、
前記１２のサブアレイタイプの１つの内部のｐｑ個のデータ要素のｐｑ個のメモリモジュール内のｐｑ個のアドレスは、関数α（ｉ＋ａ，ｊ＋ｂ）により割当てられる（ただし、ａとｂは、サブアレイ内の相対位置を表す）、
ことを特徴とするシステム。
【請求項２】
請求項１記載のコンフリクトフリーメモリシステムであって、
サブアレイ内の任意の連続する２つのデータ要素間の距離が１であり、各々がデータアレイの内部の何れかに位置するサブアレイである、前記南東ブロックと同一であるＢｌｏｃｋ（ｐ×ｑ）、前記東ラインと同一であるＨｏｒｉｚｏｎｔａｌ（１×ｐｑ）、前記南ラインと同一であるＶｅｒｔｉｃａｌ（ｐｑ×１）、前記南東ブロックと同一である順方向対角サブアレイ、及び前記南西ラインと同一である逆方向対角サブアレイの５つのサブアレイタイプの１つのｐｑ個のデータ要素への同時アクセスをサポートする当該コンフリクトフリーメモリシステムの前記アドレス計算ルーティング回路は、
ベース座標（ｉ，ｊ）とサブアレイタイプを受け取る４つの５×１マルチプレクサと、
アドレス間差を予め整列し、格納する第１ＳＲＡＭ及び第２ＳＲＡＭと、
ベースアドレスα（ｉ，ｊ）＝（ｉ／ｐ）ｓ＋ｊ／ｑの一項である（ｉ／ｐ）ｓの値を格納する（ｉ／ｐ）ｓの値に対する第３ＳＲＡＭと（ただし、ｓは、Ｎ／ｑ以上の整数であり、Ｎは前記データアレイの列の総数である）、
前記４つの５×１マルチプレクサの出力値を受け取り、前記第１及び第２ＳＲＡＭに対する選択アドレスを計算する２つの加算器、前記ベースアドレスの他方の項であるｊ／ｑの値と前記第３ＳＲＡＭからの出力値とを加算する１つの加算器、及び前記ベースアドレスと前記第１及び第２ＳＲＡＭからの出力値とを加算するｍ個の加算器から構成される（ｍ＋３）個の加算器と、
前記ｍ個の加算器の出力をμ（ｉ，ｊ）回だけ回転させ、前記ｍ個の加算器の出力をｍ個のメモリモジュールに供給するバレルシフタと、
から構成されることを特徴とするシステム。
【請求項３】
請求項１記載のコンフリクトフリーメモリシステムのアドレス計算及びデータルーティングを行う方法であって、
すべての必要とされるサブアレイタイプとインターバルに対し、ｐ×ｍ個のアドレス間差とｑ×ｍ個のアドレス間差とを予め整列するステップと、
すべての必要とされるサブアレイタイプとインターバルに対し、予め整列されたｐ×ｍ個のアドレス間差とｑ×ｍ個のアドレス間差とをそれぞれメモリモジュールＡとＢに格納するステップと、
μ（ｉ，ｊ）を計算するステップと、
ベースアドレスα（ｉ，ｊ）を計算するステップと、
前記必要とされるサブアレイタイプｉ％ｐ（ｉ％ｐは、ベース座標の一方であるｉをｐで除したときの剰余である）とｊ％ｑ（ｊ％ｑは、ベース座標の他方であるｊをｑで除したときの剰余である）によりメモリモジュールＡとＢからｍ個のアドレス間差を読み出すステップと、
ｍ個のアドレス間差を生成するため、前記ｍ個の加算器を利用して、ｍ個のアドレス間差と前記ベースアドレスα（ｉ，ｊ）とを加算するステップと、
前記バレルシフタを利用することにより、ｍ個のアドレスをμ（ｉ，ｊ）だけ回転するステップと、
ｍ個のアドレスをｍ個のメモリモジュールにルーティングするステップと、
から構成されることを特徴とする方法。
【請求項４】
請求項３記載の方法であって、
μ（ｉ，ｊ）を計算するステップと、
前記４つの５×１マルチプレクサと２つの加算器を利用することにより、前記アドレス間差に対する前記第１及び第２ＳＲＡＭへの選択アドレスを計算するステップと、
前記（ｉ／ｐ）ｓのための第３ＳＲＡＭから（ｉ／ｐ）ｓの値を読み出すステップと、
１つの加算器を利用することにより前記ベースアドレスα（ｉ，ｊ）を生成するため、前記（ｉ／ｐ）ｓの値とｊ／ｑの値とを加算するステップと、
前記選択アドレスを利用することにより、前記第１及び第２ＳＲＡＭからｍ個のアドレス間差を読み出すステップと、
ｍ個のアドレスを生成するため前記ｍ個の加算器を利用することにより、ｍ個のアドレス間差と前記ベースアドレスα（ｉ，ｊ）とを加算するステップと、
前記バレルシフタを利用することにより、ｍ個のアドレスをμ（ｉ，ｊ）により回転するステップと、
ｍ個のアドレスをｍ個のメモリモジュールにルーティングするステップと、
から構成されることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はメモリ装置に関し、より詳細にはpq個のプロセッシングエレメント(Processing Element:PE)を持つ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、 and P. 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 2 FFT in 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.  多様なサブアレイのアクセス形態と間隔：メモリ装置は０でない陽数間隔を持っているデータに対して多様な形態の同時アクセスを支援しなければならない。
【０００５】
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処理器に対する貯蔵技術、線型有無、ルーティング方法、サブアレイアクセス形態、間隔、ハードウェアの具現、同時性、アクセス位置、プロセッシングエレメントの負荷、そして従来のメモリ装置と本発明で提示するメモリ装置のメモリモジュール数などを示す。
【００１７】
【表１ａ】
0003802783.tif 000002
【００１８】
【表１ｂ】
0003802783.tif 000003
一方、映像処理で全体的なメモリ装置アクセス時間を減少するためにブロック、列、行、対角線、または逆対角線型態の多くの映像点を同時にアクセスすることができるSIMD処理器(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.)、ブロック、列、行のアクセス形態の映像点が並列的に演算できるように各プロセッシングエレメントに割り当てられなければならない。ウェブレット変換(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 for Image 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であるブロック形態のデータが同時にアクセスできねばならない。
【００１９】
他の例としては圧縮、文字分析、動き分析などに用いられるガウシアンピラミッド(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 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.)に対して全体的なメモリ装置アクセス時間の減少のため、任意の位置で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方向の線型映像点をアクセスできるメモリ装置が必要となる。
【００２０】
双方向併合整列アルゴリズム、連続的な増加FFTアルゴリスム、再帰的な増加アルゴリズム、行列、信号処理等のためにブロック、列、行、対角線、逆対角線アクセス形態のデータを同時にアクセスできるメモリ装置が全体的なメモリ装置アクセス時間を短縮するためのSIMD処理器に必要となる。
【００２１】
双方向併合整列は長さが1ずつである整列されたデータファイルn個の入力から始まる。このn個のデータファイルは大きさが2であるn/2個のファイルに併合される。n/2個のファイルが再び併合され、このような方法で1個のデータファイルとなるまで繰り返される。それで、速やかな双方向併合整列アルゴリズムのため、2l(l>0)の間隔の行形態データをアクセスできるメモリ装置がSIMD処理器に有用である。
【００２２】
SIMD処理器で連続的な増加FFTアルゴリズム(J. W. Cooley、 P. A. W. Lewis and 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)間隔の行形態のデータをアクセスすることができるメモリ装置がメモリ装置アクセス時間の短縮に有用である。
【００２３】
足し算、掛け算、最大、最少、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 signal processing、 Prentice-Hall、 1993.)をするために多様な行列演算の速度を高めるためのブロック、列、行、対角線、逆対角線型態の同時データクセスを支援する衝突のフリ記憶は全体的なメモリ装置アクセス時間を短縮するのに有用である。
【００２４】
pq個のプロセッシングエレメントで構成されたSIMD処理器とm個のメモリモジュールで構成されたメモリ装置において、pq個のデータが同時にそれぞれ異なるメモリモジュールから要請される。記憶置アクセス時間の後、pq個の要請が終り、全メモリモジュールもその演算を終えることになるが、このとき要請されたデータ内の各データの位置は制限されてはならない。映像処理、双方向併合整列アルゴリズム、連続増加FFTアルゴリズム、再帰的な倍加アルゴリズム、そして行列、信号処理等において、メモリ装置アクセス時間を短縮し演算速度を速めるために、大きさが I(＊、＊)であるデータで間隔 rを持ってブロック、列、行、対角線、逆対角線アクセス形態でpq個のデータを同時にアクセスできるメモリ装置が必要となる。間隔が陽数や陰数で可能になるためには基準座標(i、j)から間隔が陽数rである12種のアクセス類型(南東側ブロック、南西側ブロック、北西側ブロック、北東側ブロック、東側ブロック、南東側線型、南側線型、南西側線型、西側線型、北西側線型、北側線型、北東側線型)を考慮しなければならない。
【００２５】
SEB(i、j、r)  =  {I(i+ar、j+br) | 0 ≦ a < p、0 ≦ b < q}、
0 ≦ i ≦ M-rp、0 ≦ j ≦ N-rq                              （１）
SWB(i、j、r) = {I(i+ar、j-br) | 0 ≦ a < p、 0 ≦ b < q}、
0 ≦ i ≦ M-rp、rq ≦ j ≦ N                                （２）
NWB(i、j、r) = {I(i-ar、j-br) | 0 ≦ a < p、 0 ≦ b < q}、
rp ≦ i ≦ M、 rq ≦ j ≦ N                                （３）
NEB(i、j、r) = {I(i-ar、j+br) | 0 ≦ a < p、0 ≦ b < q}、
rp ≦ i ≦ M、 0 ≦ j ≦ N-rq                              （４）
EL(i、j、r) = {I(i、j+ar) | 0 ≦ a < pq}、
0 ≦ i ≦ M、 0 ≦ j ≦ N-rpq                               （５）
SEL(i、j、r) = {I(i+ar、j+ar) | 0 ≦ a < pq}、
0 ≦ i ≦ M-rpq、0 ≦ j ≦ N-rpq                            （６）
SL(i、j、r) = {I(i+ar、j) | 0 ≦ a < pq}、
0 ≦ i ≦ M-rpq、0 ≦ j ≦ N                               （７）
SWL(i、j、r) = {I(i+ar、j-ar) | 0 ≦ a < pq}、
0 ≦ i ≦ M-rpq、rpq ≦ j ≦ N                              （８）
WL(i、j、r) = {I(i、j-ar) | 0 ≦ a < pq}、
0 ≦ i ≦ M、rpq ≦ j ≦ N                                  （９）
NWL(i、j、r) = {I(i-ar、j-ar) | 0 ≦ a < pq}、
rpq ≦ i ≦ M、 rpq ≦ j ≦ N                              （１０）
NL(i、j、r) = {I(i-ar、j) | 0 ≦ a < pq}、
rpq ≦ i ≦ M、0 ≦ j ≦ N                                （１１）
NEL(i、j、r) = {I(i-ar、j+ar) | 0 ≦ a < pq}、
rpq ≦ i ≦ M、 0 ≦   j ≦ N-rpq                          （１２）
ここで、間隔 rは正の整数である。
【００２６】
基準座標(i、j)で間隔rを持つ12種のアクセス類型(1)〜(12)は図2aと図2bに示す。図2aは4方向ブロック(SEB、SWB、NWB、NEB)を、図2bは8方向線型(EL、SEL、SL、SWL、WL、NWL、NL、NEL)を示す。
【００２７】
図3ではSIMD処理器がある衝突防止メモリ装置の一般的な構造をブロックダイアグラム形態で示す。ここでインターフェースはデータレジスターである。処理すべきデータが貯蔵されると、メモリ装置の構成要素はSIMD処理器の要請に従って制御装置の制御下に次のような演算を順次的に行う。
【００２８】
(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)である。
【００２９】
(2)  アドレス計算及びアドレスルーティング回路はデータに対するm個のアドレスを計算し、それをm個のメモリモジュールにルーティングする。
【００３０】
(3)  メモリモジュール選択回路はアクセスされるpq個のメモリモジュールを選択する。
【００３１】
(4)  データルーティング回路はデータレジスター内のデータをm個のメモリモジュールにルーティングする。
【００３２】
(5)  書き信号によってpq個のデータが選択されたpq個のメモリモジュールに貯蔵される。
【００３３】
ここで(2)、(3)、(4)番の演算が並列に行われる。
【００３４】
同様にメモリ装置からデータを取り出す時にもメモリ装置の構成要素は次のような演算を順次的に行う。
【００３５】
(１)  t、r、i、jレジスター値を決定する。
【００３６】
(２)  アドレス計算及びアドレスルーティング回路はデータに対するm個のアドレスを計算し、それをm個のメモリモジュールにアドレスをルーティングさせる。
【００３７】
(３)  メモリモジュール選択回路はアクセスできるpq個のメモリモジュールを選択する。
【００３８】
(４)  読み信号によってpq個の選択されたメモリモジュールからpq個のデータを取ってくる。
【００３９】
(５)  データルーティング回路はm個のメモリモジュールからデータレジスターにデータをルーティングし、行優先順位に変形されたデータを(1)~(12)アクセス形態中の一つに配列する。
【００４０】
ここで、(2)、(3)番の演算が並列に行われる。
【００４１】
大きさがM×NであるデータI(＊、＊)をmメモリモジュールに分散する時、メモリモジュール割り当て関数は同時にアクセスされるデータを他のメモリモジュールに位置させなければならない。また、アドレス割り当て関数は同じメモリモジュールに割り当てられるデータに他のアドレスを割り当てなければならない。
【００４２】
【発明が解決しようとする課題】
本発明の目的は簡単で迅速なアドレス計算回路とルーティング回路を持つ衝突防止メモリ装置を提供することにある。
【００４３】
本発明の他の目的はM×Nアレイ内のデータにおける任意の位置で一定の間隔を持つ4方向のブロック(pq)形態と8方向の線分形態であるpq個のデータ要素に同時にアクセスできるよう支援して、メモリ装置のアクセス時間を短縮することができる衝突防止メモリ装置を提供することにある。
【００４４】
更に、本発明の他の目的は従来のメモリ装置と比べてデータへのアクセス形態、間隔、データアレイの大きさ制限及びハードウェア費用と速度等の面で改善されたメモリ装置を提供することにある。
【００４５】
【課題を解決するための手段】
このような目的を達成するための本発明による衝突防止メモリ装置は、(m>pq)個のメモリモジュールと、データに対するm個のアドレスを計算しその値を前記m個のメモリモジュールにルーティングするアドレス計算及びアドレスルーティング回路と、アクセスされるpq個のメモリモジュールを選択するメモリモジュール選択回路と、指定されたアクセス類型と基準座標及びアクセス類型で要求される間隔情報を貯蔵するデータレジスターと、前記データレジスター内のデータを前記m個のメモリモジュールにルーティングするデータルーティング回路を含んでなり、pq個のプロセッシングエレメントを持つ単一命令多重データ処理装置おけるメモリ装置アクセス時間を減少させるための衝突防止メモリ装置において、4方向四角形ブロック陽数の間隔で連関されたデータ要素がデータアレイ内のどの位置(南東側ブロック、南西側ブロック、北西側ブロック、北東側ブロック)に置かれていっても8方向の線型(東側線型、南東側線型、南側線型、南西側線型、西側線型、北西側線型、北線型、北東側線型)アクセス形態のpq個データ要素に同時アクセスを支援する。
【００４６】
本発明による衝突防止メモリ装置の細部的な特徴は、前記アドレス計算及びアドレスルーティング回路が、基準座標、アクセス形態及び間隔情報が提供される4個の5×1マルチプレクサーと、アドレス間差を予め整列して貯蔵するための第1及び第2 SRAMと、(i/p)s値のための第3 SRAMと、前記マルチプレクサー出力値を前記第1及び第2 SRAMに伝逹する二つの加算器と前記第3 SRAMの出力値が伝逹され加えられる加算器とm個の加算器とからなるm+3個の加算器と、前記m個の加算器の出力をデータルーティング回路の回転信号に応じてm個のメモリモジュールに伝逹するバレルシフターからなることにある。
【００４７】
【発明の実施の形態】
以下、本発明の衝突防止メモリ装置の構成と、そのメモリ装置を利用したアドレス計算及びデータルーティング方法を添付図面により詳細に説明する。
【００４８】
データのメモリモジュール番号を決定するメモリモジュール割り当て関数は次のとおりである。
【００４９】
μ(i、j) = (iq+j) % m                                （１３）
メモリモジュール割り当て関数(13)はm=pq+1、2pq、pq２に対してはバンブーリスとモリン(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.)により提案された。
【００５０】
次の理論1は12種のアクセス類型(1)~(12)に対して前記の関数(13)によるアクセス可能性を示している。
【００５１】
理論１：mが pqより大きな素数である時、メモリモジュール割り当て関数μ(i、j)は間隔がr(r%m≠0)である南東側ブロック(SEB)、南西側ブロック(SWB)、北西側ブロック(NWB)、北東側ブロック(NEB)、東側線型 (EL)、南東側線型(SEL)、南側線型(SL)、南西側線型(SWL)、西側線型(WL)、北西側線型(NWL)、北側線型 (NL)、北東側線型(NEL)アクセス形態であるpq個のデータはpq個のお互いに異なるメモリモジュール内に位置する。
【００５２】
メモリモジュール内のデータのアドレスを決定する割り当て関数は下記の式(14)のとおりである。
【００５３】
α(i、j) = (i/p)s + j/q                                  （１４）
ここで、sは
【外１】
0003802783.tif 000004
の整数部分と同じ或いはより大きな整数であり、「/」は整数形の割り算を表す。この関数はバンブーリスとモリン(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 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.)によって提案された。
【００５４】
(1)〜(12)アクセス類型において、メモリモジュールの変化とデータのアドレスが変更された行優先順位に配列できれば、k = a・q+b、0≦k<pqである時、メモリモジュール割り当て関数(13)とアドレス割り当て関数(14)は次のように表すことができる。
【００５５】
μ(k) = (μ(0) + μ'(k))%m、 0 ≦ k < pq            （１５）
ここで、μ(0)は関数(13)のμ(i、j)によって求められる。
【００５６】
α(k) = α(0) + α'(k)、 0 ≦ k < pq                （１６）
ここで、α(0)は関数(14)の基準アドレスであるα(i、j)である。
【００５７】
メモリモジュール内で処理されるべきデータのアドレスが計算されるα(μ)(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、 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)を計算する。
【００５８】
最後にアドレスα(k)はメモリモジュールにルーティングされる。アドレス計算及びアドレスルーティング方法の短所はルーティング形態がアクセス形態と間隔に依存するため、アドレスルーティング回路はアクセス類型と間隔が増加すると非常に複雑になる。
【００５９】
本発明では新しいアドレス計算とルーティング方法がアドレス間差α'(k)に要求されたデータのうち、第１番目データのμ(0)のメモリモジュール番号からメモリモジュール番号に従って順次的に予め整列されるよう提案された。それで、基準アドレスにアドレス間差を加えた後、全体12アクセス類型と間隔μ(0)による右側回転が必要となる。
【００６０】
μ'(k)とα'(k)を求めるためには前記の式(15-16)が次のように変わる。
【００６１】
μ'(k) = μ((k)-μ(0))%m、 0 ≦  k < pq            （１７）
α'(k) = α(k)-α(0)、 0 ≦  k < pq                （１８）
μ'(k) = (λ・ k)%mの場合に、
k = (μ'(k) λ')%m = ((μ(k)-μ(0))λ')%m            （１９）
ここで、 λ・ λ' = 1%mである。
【００６２】
式(18)におけるkの代りに((μ(k)-μ(0))・λ')%mを用いて、α'(k)を次のようにすることができる。
【００６３】
α'(k)=α'(((μ(k)-μ(0)) ・λ')%m)
=α(((μ(k)-μ(0)) ・λ')%m) - α(0)、 0 ≦  k < pq    （２０）
α'(k)(0≦k<pq)はメモリ装置内で用いられたpq個のデータのアドレス間差である。ここで、データは (i、j)のデータから変形された行の優先に整列される。メモリモジュール番号に従ってメモリモジュール「0」からアドレス間差(20)の整列によりα'(μ)を次のように求めることができる。
【００６４】
α'(μ)
= α'(((μ- μ(0)) ・λ')%m)
= α(((μ- μ(0)) ・λ')%m) - α(0)、 0 ≦ μ < m        （２１）
α'(μ)(0≦μ<m)はpq個のデータに対するpq個のアドレス間差とm-pq個の仮アドレス間差であり、それは「0」からメモリモジュール番号「μ」によって整列された。
【００６５】
α'(μ)(0≦μ<m )は基準アドレス (i、j)のデータのメモリモジュール番号μ(0)(=μ(i、j))に依存するため、アドレス間差の個数はメモリモジュール数mに従って増加する。それで、メモリモジュール数mが大きい時、アクセス類型(1)~(12)のデータのアドレス計算に対し、α'(μ)(0≦μ< m)の使用は非常に複雑である。式(21)にμの代りに(μ+μ(0))%mを入れると、下記の式によりメモリモジュールμ(0)からメモリモジュール番号の順次的なアドレス間差を求めることができる。
【００６６】
α'(μ+μ(0)) = α'(μ・λ')%m、 0 ≦ μ < m         （２２）
式(22)のアドレス間差、α'(μ・λ')%m (0 ≦ μ< m)はμ(i、j)や α(i、j)の項目が含まれていないため、データの位置に対して影響が少ない。
【００６７】
それで、コンパイリング時間にアドレス間差を計算した後、そのアドレス間差を一つのメモリモジュールに貯蔵することができる。式(22)のアドレス間差α'(μ+μ(i、j))がα(i、j)に加えられた後、α(μ)を求めるためにμ(i、j)による右側回転を単一度だけ行う。
【００６８】
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    （２３）
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    （２４）
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    （２５）
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    （２６）
AD_EL(i、j、r、a) = α(i、j+ar) - α(i、j)
= (j%q+ ar)/q、 0 ≦ a < pq                            （２７）
AD_SEL(i、j、r、a) = α(i+ar、j+ar) - α(i、j)
= s・((i%p+ar)/p) + (j%q+ar)/q、 0 ≦ a < pq              （２８）
AD_SL(i、j、r、a) = α(i+ar、j) - α(i、j)
= s・((i%p+ar)/p)、 0 ≦ a < pq                          （２９）
AD_SWL(i、j、r、a) = α(i+ar、j-ar) - α(i、j)
= s・((i%p+ar)/p) + (j%q-ar)/q、 0 ≦ a < pq              （３０）
AD_WL(i、j、r、a) = α(i、j-ar) - α(i、j)
= (j%q - ar)/q、 0 ≦ a < pq                            （３１）
AD_NWL(i、j、r、a) = α(i-ar、j-ar) - α(i、j)
= s・((i%p-ar)/p) + (j%q-ar)/q、  0 ≦ a < pq            （３２）
AD_NL(i、j、r、a) = α(i-ar、j) - α(i、j)
= s・((i%p-a)/p))、  0 ≦ a < pq                        （３３）
AD_NEL(i、j、r、a) = α(i-ar、j+ar) - α(i、j)
= s・((i%p-ar)/p) + (j%q+ar)/q、 0 ≦ a < pq            （３４）
前記に示したアドレス間差(23)〜(34)は次の式によって変形された行優先順位の基準座標(i、j)から整列される。
【００６９】
AD_SEB(i、j、r、k) = s・((i%p+(k/q)r)/p) + (j%q+(k%q)r)/q、
0 ≦ k < pq                                      （３５）
AD_SWB(i、j、r、k) = s・((i%p+(k/q)r)/p) + (j%q-(k%q)r)/q、
0 ≦ k < pq                                      （３６）
AD_NWB(i、j、r、k) = s・((i%p-(k/q)r)/p) + (j%q-(k%q)r)/q、
0 ≦ k < pq                                      （３７）
AD_NEB(i、j、r、k) = s・((i%p-(k/q)r)/p) + (j%q+(k%q)r)/q、
0 ≦ k < pq                                      （３８）
AD_EL(i、j、r、k) = (j%q + kr)/q、 0 ≦ k < pq      （３９）
AD_SEL(i、j、r、k) = s・((i%p+kr)/p) + (j%q+kr)/q、 0 ≦ k < pq（４０）
AD_SL(i、j、r、k) = s・((i%p+kr)/p))、 0 ≦ k < pq            （４１）
AD_SWL(i、j、r、k) = s・((i%p+kr)/p) + (j%q-kr)/q、 0 ≦ k < pq（４２）
AD_WL(i、j、r、k) = (j%q- kr)/q、 0 ≦ k < pq              （４３）
AD_NWL(i、j、r、k) = s・((i%p-kr)/p) + (j%q-kr)/q、 0 ≦ k < pq（４４）
AD_NL(i、j、r、k) = s・((i%p-kr)/p))、 0 ≦ k < pq            （４５）
AD_NEL(i、j、r、k) = s・((i%p-kr)/p) + (j%q+kr)/q、 0 ≦ k < pq（４６）
アドレス間差が二進項目を持つj%qの影響を受けるので、式(35)~(46)のSEB、SWB、NWB、NEB、EL、SEL、SWL、WL、NWL、NELのアドレス間差は加算器の入力CのためにメモリモジュールBに貯蔵された二進値とアドレス間差の大きさ減少の結果である入力BのためのメモリモジュールにAに貯蔵された残り値を分離する。
【００７０】
SEBのアドレス間差は次の式によって分離される。
【００７１】
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)        （４７）
他の11個でのアクセス類型のアドレス間差は次のとおりである。
【００７２】
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     （４８）
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     （４９）
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     （５０）
AD_EL(i、j、r、k) = (kr)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q + (k%q)r)/q -((k%q)r)/q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq    （５１）
AD_SEL(i、j、r、k) = s・((i%p+kr)/p) + (kr)/q、
(アドレス間差のためのメモリモジュールA)
+ (j%q+kr)/q - (kr)/q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq    （５２）
AD_SL(i、j、r、k) = s・((i%p+kr)/p))
(アドレス間差のためのメモリモジュールA)、 0 ≦ k < pq    （５３）
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    （５４）
AD_WL(i、j、r、k) = -(kr) / q
(アドレス間差のためのメモリモジュールA)
+ (j%q - kr) /q + (kr) / q
(アドレス間差のためのメモリモジュールB)、 0 ≦ k < pq    （５５）
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    （５６）
AD_NL(i、j、r、k) = s・((i%p-kr)/p))
(アドレス間差のためのメモリモジュールA)、 0 ≦ k < pq    （５７）
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    （５８）
前記12種のアドレス間差に対し表2に整理されている。
【００７３】
【表２】
0003802783.tif 000005
アドレス計算回路(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個のアドレスを簡単に計算することができる。
【００７４】
理論1においてアクセスされるpq個のメモリモジュール番号は12種のアクセス形態(1)~(12)とr%m≠0である間隔が次のように表される。
【００７５】
0003802783.tif 000006
前記の式(59)〜(70)の番号は次のことによって基準アドレス (i、j)から変形された行優先順位に整列される。
【００７６】
μSEB(k) = (μ(0) + q・(k/q)・r + (k%q)・r)%m = (μ(0) + kr)%m、
0 ≦ k < pq                                        （７１）
μSWB(k) = (μ(0) + q・(k/q)・r - (k%q)・r)%m
= (μ(0) + (q・(k/q) - (k%q)) ・r)%m、   0 ≦ k < pq    （７２）
μNWB(k) = (μ(0) - q・(k/q)・r - (k%q)・r)%m
= (μ(0) - kr)%m、 0 ≦ k < pq                      （７３）
μNEB(k) = (μ(0) - q・(k/q)・r + (k%q)・r)%m
= (μ(0) - (q・(k/q) - (k%q)) ・r)%m、 0 ≦ k < pq      （７４）
μEL(k) = (μ(0) + kr)%m、 0 ≦ k < pq              （７５）
μSEL(k) = (μ(0) + (q+1)kr)%m、 0 ≦ k < pq        （７６）
μSL(k) = (μ(0) + qkr)%m、 0 ≦ k < pq            （７７）
μSWL(k) = (μ(0) + (q-1)kr)%m、 0 ≦ k < pq        （７８）
μWL(k) = (μ(0) - kr)%m、 0 ≦ k < pq              （７９）
μNWL(k) = (μ(0) - (q+1)kr)%m、 0 ≦ k < pq        （８０）
μNL(k) = (μ(0) - qkr)%m、 0 ≦ k < pq              （８１）
μNEL(k) = (μ(0) - (q-1)kr)%m、 0 ≦ k < pq          （８２）
ここで μ(0)はμ(i、j)である。
【００７７】
南東側ブロック(SEB)のアドレス間差
μ番目モジュールの南東側ブロック(SEB)のアドレス間差、ASEB(μ)は(17)〜(22)過程によって(47)と(71)から得られた。
【００７８】
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)                  （８３）
ここで、 r・r' = 1%mである。
式(83)でμの代りに(μ+μ(0))%mに代置すると、次の式によってμ(0)から上り順に整列されたメモリモジュールのアドレス間差を求めることができる。
【００７９】
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)                 （８４）
ここで、r・r' = 1%mである。
【００８０】
南西側ブロック(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)                    （８５）
SEB(i、j-(q-1)r、k)のメモリモジュールの指数は次のとおりである。
【００８１】
(μ(0) - (q-1)r + kr)%m、 0 ≦ k < pq                （８６）
それで、μ番目のモジュールの南東側ブロック(SWB)のアドレス間差ASWB(μ)は式(85)と(86)から求めることができる。
【００８２】
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)                      （８７）
ここで、 r・r' = 1%mである。
【００８３】
式(87)でμの代りに(μ+ μ(0) + (q-1)r)%mを用いて、次の式によってμ(0)から上り順に整列されたメモリモジュールのアドレス間差を求めることができる。
【００８４】
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)、                  （８８）
ここで、 r・r′= 1%mである。
【００８５】
μ(0)から上り順に整列されたメモリモジュールお互いに異なる10種のアクセス形態に対するアドレス間差はSEBやSWBと同じ過程によって求められる。表3にμ(0)から上り順に整列されたメモリモジュールの12種のアクセス形態(1)~(12)と間隔であるアドレス間差を示す。
【００８６】
【表３】
0003802783.tif 000007
アドレス間差の大きさ
表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に貯蔵する。
【００８７】
本発明によるアドレス計算回路とアドレスルーティング回路は次のような演算を順次的に行う。
【００８８】
(1)  予め整列されたp×m個のアドレス間差とq×m個の差がそれぞれアクセス形態とそれぞれの間隔に対してメモリモジュールAとBに貯蔵される。
【００８９】
(2)  m個のアドレス間差はアクセス形態、i%p、j%qの間隔のみならず、μ(0≦μ<m )などの影響を受けるので、要求されたアクセス形態、i%p、j%q間隔によってメモリモジュールAとBから取ってくる。
【００９０】
(3)  前記で求められたm個のアドレス間差は基準アドレスα(i、j)に加えられる。
【００９１】
(4)  前記のm個のアドレスは12種のアクセス形態と間隔(1)〜(12)全体に対して、μ(0)によって回転される。
【００９２】
(5)  計算されたm個のアドレスはm個のメモリモジュールにルーティングされる。
【００９３】
データレジスターからm個のメモリモジュールにデータをルーティングするデータルーティング回路の役割は適切なメモリモジュールにpq個のデータをルーティングすることにある。pq個のデータに対するメモリモジュール番号は、式(71)〜(82)でのアドレスと同じである。それで、次の数式によってpq個のデータを整列させた後、そのデータのメモリモジュール番号を持ってメモリモジュール番号0から始まる上り順整列のために右側回転がμ(i、j)ぐらい行われる。
【００９４】
SEB: D2((kr)%m) ←D1(k)、 0 ≦ k < pq                  （８９）
SWB: D2(((q・(k/q) - k%q)・r)%m) ←D1(k)、 0 ≦ k < pq    （９０）
NWB: D2((-kr)%m) ← D1(k)、 0 ≦ k < pq                （９１）
NEB: D2(((-q・(k/q) + k%q)・r)%m) ←D1(k)、 0 ≦ k < pq    （９２）
EL: D2((kr)%m) ←D1(k)、 0 ≦ k < pq                    （９３）
SEL: D2(((q+1)kr)%m) ←D1(k)、 0 ≦ k < pq              （９４）
SL: D2((qkr)%m) ←D1(k)、 0 ≦ k < pq                  （９５）
SWL: D2(((q-1)kr)%m) ←D1(k)、 0 ≦ k < pq              （９６）
WL: D2((-kr)%m) ← D1(k)、 0 ≦ k < pq                  （９７）
NWL: D2((-(q+1)kr)%m) ←D1(k)、 0 ≦  k < pq            （９８）
NL: D2((-qkr)%m) ←D1(k)、 0 ≦ k < pq                  （９９）
NEL: D2((-(q-1)kr)%m) ←D1(k)、 0 ≦ k < pq            （１００）
ここで、D1とD2はデータレジスターと臨時レジスターである。ルーティング形態がアクセス形態と間隔の影響を受けるため、ルーティング形態(89)~(100)を用いるデータルーティング回路の制御は複雑である。このようなデータルーティング形態は次に示すことによって制御の複雑度を減少させることができる。
【００９５】
南東側ブロック(SEB)
式 (89)の南東側ブロック(SEB)のデータルーティング形態に対して、間隔 rのメモリモジュール番号である(kr)%mは(k・m・l1+ k・r1)%mである。 ここで、r1=r%mでありl1は陽数である。それで、式(89)にの間隔rの南東側ブロック(SEB)のデータルーティング形態は下記の式からr1(=r%m)を持つ(m-1)個のお互いに異なるルーティング経路が選択される。
【００９６】
SEB: D2((kr1)%m) ←D1(k)、  0 ≦ k < pq                （１０１）
南西側ブロック(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)個のお互いに異なるルーティング経路が選択される。
【００９７】
SWB: D2(((q・(k/q) - k%q)・r1)%m) ←D1(k)、 0 ≦ k < pq    （１０２）
北西側ブロック(NWB)
式(91)の北西側ブロック(NWB)のデータルーティング形態に対する間隔rのメモリモジュール番号(-kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態(kr)%mの間隔(-r)%mであるメモリモジュール番号と同一である。それで、式(101)の南東側ブロック(SEB)の(m-1)個のお互いに異なるルーティング経路に間隔rの代わりに(-r)%mを代入することで北西側ブロック(NWB)の経路を求めることができる。
【００９８】
北東側ブロック(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)を求めることができる。
【００９９】
東側線型(EL)
式(93)の東側線型(EL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態に対する間隔rのメモリモジュール番号と同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりにr%mを代入して東側線型(EL)の経路を求めることができる。
【０１００】
南東側線型(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)の経路を求めることができる。
【０１０１】
南側線型(SL)
式(95)の南側線型(SL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(qkr)%mは、式(89)の南東側ブロック(SEB)のデータ形態で間隔(qr)%mのメモリモジュール番号である(kr)%mと同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(qr)%mを代入することで南側線型(SL)の経路を求めることができる。
【０１０２】
南西側線型(SWL)
式(96)の南西側線型(SWL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である((q-1)kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態で間隔((q-1) r)%mのメモリモジュール番号である((kr)%m)と同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに((q-1)r)%mを代入することで南西側線型(SWL)の経路を求めることができる。
【０１０３】
西側線型(WL)
式(97)の西側線型(WL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(-kr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態でメモリモジュール番号である(kr)%mに間隔(-r)%mを入れた(k(-r))%m)と同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(-r)%mを代入することで西側線型(WL)の経路を求めることができる。
【０１０４】
北西側線型(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)の経路を求めることができる。
【０１０５】
北線型(NL)
式(99)の北線型(NL)のデータルーティング形態に対して、間隔rのメモリモジュール番号である(-qkr)%mは、式(89)の南東側ブロック(SEB)のデータルーティング形態でメモリモジュール番号である(kr)%mに間隔(-qr)%mを入れた(k(-qr))%mと同一である。それで、式(101)の南東側ブロック(SEB)での(m-1)個のお互いに異なるルーティング経路を用いて、間隔rの代わりに(-qr)%mを代入することで北線型(NL)の経路を求めることができる。
【０１０６】
北東側線型(NEL)
式(100)の北東側線型(NEL)のデータルーティング形態に対して、間隔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を代入することで北東側線型(NEL)の経路を求めることができる。
【０１０７】
表4に減少されたルーティング形態が現われている。
【０１０８】
【表４】
0003802783.tif 000008
12種のアクセス形態に対する全体ルーティング形態は2(m-1)個である。それで、データルーティング回路では間隔(1)~(12)である12種のアクセス形態に対して、式(101)のSEBと式(102)のSWBの二つに対するルーティング形態だけが必要となる。
【０１０９】
データルーティング回路は図4に示す。
【０１１０】
ここで、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.)で単純に比較されられた。読み演算のためのルーティング形態は決まっている。
【０１１１】
間隔を持つ列、ブロック、行に対するメモリモジュール選択回路はバンブーリスとモリン(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)個のアクセスされないメモリモジュール番号を見せる。
【０１１２】
理論2 : 12種のアクセス形態に対する(m-pq)個のアクセスされないメモリモジュール番号は次のようになる。
【０１１３】
μSEB(k) = (μ(0) + kr)%m、    pq ≦ k < m                  （１０３）
μSWB(k) = (μ(0) + (q・(k/q) - (k%q))・r)%m、    pq ≦ k < m  （１０４）
μNWB(k) = (μ(0) - kr)%m、        pq ≦ k < m          （１０５）
μNEB(k) = (μ(0) - (q・(k/q) - (k%q))・r)%m、    pq ≦ k < m  （１０６）
μEL(k) = (μ(0) + kr)%m、      pq ≦ k < m              （１０７）
μSEL(k) = (μ(0) + (q+1)kr)%m、        pq ≦ k < m      （１０８）
μSL(k) = (μ(0) + qkr)%m、          pq ≦ k < m          （１０９）
μSWL(k) = (μ(0) + (q-1)kr)%m、          pq ≦ k < m    （１１０）
μWL(k) = (μ(0) - kr)%m、    pq ≦ k < m                （１１１）
μNWL(k) = (μ(0) - (q+1)kr)%m、      pq ≦ k < m        （１１２）
μNL(k) = (μ(0) - qkr)%m、          pq ≦ k < m          （１１３）
μNEL(k) = (μ(0) - (q-1)kr)%m、    pq ≦ k < m            （１１４）
ここで、μ(0)はμ(i、j)である。
【０１１４】
前記の式(103)〜(114)にある(m-pq)個の番号が(m-pq)個のデコーダーに与えられると、デコーダーの該当の反転結果をOR演算したm個の結果はm個のメモリモジュールのアクセスを制御する。
【０１１５】
特に、m=pq+1に対して、式(103)~(114)内のkをpqで代置して得たアクセスされないメモリモジュール番号の一つをデコーダーに提供し、m個の反転されたデコーダーの結果はpq個のアクセスされるメモリモジュールのアクセス信号とアクセスされないメモリモジュールの非アクセス信号で使われる。
【０１１６】
アドレス計算、ルーティング及びメモリモジュールの例
図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に示されている。本発明でのアドレス計算及びアドレスルーティング、及びメモリモジュール選択方法が下記の例でわかる。
【０１１７】
(例１)
間隔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を意味する。本発明によるアドレス計算、アドレスルーティング及びメモリモジュール選択方法の過程は下記のようである。
【０１１８】
i%p = 0、j%q = 1、r = 1に対して次のようにアドレス間差が求められる。
【０１１９】
ASEB(μ+μ(0))%m = (0、0、0、0、16)各加算器の入力B
+(0、1、0、1、0)各加算器の入力C
= (0、1、0、1、16) (図9から)
求められたアドレス間差に基準アドレスを適用して下記のことを得ることができる。
【０１２０】
α(k) =α(0) (=119)+ASEB(μ+μ(0))
= (119、120、119、120、135)
このアドレスをμ(0)(=3)によって右側に回転すると次のように求められる。
【０１２１】
α(μ) = (119、120、135、119、120)
式(103)で求められた(μ(i、j)+kr)%m = (3+4)%5 = 2番のモジュールがアクセスされないモジュールなので、前記と同じ結果である(119、120、×、119、120)が求められる。
【０１２２】
他の例は表5a及び表5bに現われている。
【０１２３】
【表５ａ】
0003802783.tif 000009
【０１２４】
【表５ｂ】
0003802783.tif 000010
テキストとイメージの速やかで正確な修正とディスプレーに対する多い要請によって高速の高解像度グラフィックディスプレー装置に対する需要が増加している。従来のグラフィックディスプレー装置は修正とディスプレーをするために、2次元映像アレイを含むバッファーメモリ装置を用いる。グラフィックディスプレー装置はメインコンピューターの命令に従ってバッファーメモリ装置の映像点を新しく修正する。バッファーメモリ装置から映像点を読んでレスタースキャニングの形態によりディスプレーに映像点を送る。高速の高解像度グラフィックディスプレー装置でバッファーメモリ装置内容の修正時間を減少するための高速のバッファーメモリ装置が要求される。一つの記憶チップに含まれるビット数がチップ技術の発展によって増加している。だから、多くのアクセス形態による多くの映像点の並列的なアクセスのために大容量の単一メモリモジュールに対して、アクセス時間を減少することより、相対的に容量は少なくとしても、一つの記憶チップに入れ込まれるメモリモジュール数を増加することが高速のバッファーメモリ装置のために望ましい。それで、バッファーメモリ装置の内容を修正する時間を減少するための映像アクセス形態による多くの映像点を並列的にアクセスするバッファーメモリ装置が必要となる。
【０１２５】
以下、グラフィックディスプレー装置のバッファーメモリ装置のために使われるブロック、水平、垂直、対角線、逆対角線アクセス形態を持つメモリ装置に対して、調べながら従来のメモリ装置と比べる。
【０１２６】
ブロック、水平、垂直、対角線、逆対角線アクセス形態のためのメモリ装置
高速の高解像度グラフィックディスプレー装置のための效率的なバッファーメモリ装置を調べる。このメモリ装置は二次元映像においてブロック(p×q)、水平(1×pq)、垂直(pq×1)、対角線、逆対角線アクセス形態のpq個の映像点に対して並列アクセスを提供する。
【０１２７】
ここで、媒介変数pとqは全部2の乗数である。
【０１２８】
図10に示すグラフィックディスプレー装置は一般的にメインコンピューター、ディスプレー処理器、バッファーメモリ装置(100)、ビデオ生成器及びディスプレーで構成される。ディスプレー処理器はメインコンピューターの命令によってバッファーメモリ装置内の映像点を新しく修正する。
【０１２９】
ビデオ生成器はバッファーメモリ装置から映像点を読み出してレスタースキャニング形態にディスプレーに送る。M×N大きさの映像データで映像点に対するアクセス時間を減少するため、グラフィックディスプレー装置内のM×N映像内でpq個の映像点を並列にアクセスするためのバッファーメモリ装置が必要となる。表6は従来のグラフィックディスプレーにおける表示領域の多様な大きさを示す。バッファーメモリ装置の大きさは少なくとも特定なディスプレー装置における表示領域の大きさと同じでなければならない。
【０１３０】
【表６】
0003802783.tif 000011
例えば、960(ライン数)×1280(ライン当たりの映像点数)のディスプレーに対して、M×Nの最小値はそれぞれ960と1280である。それで、多くのグラフィック装置のN値は2の乗数ではない値を用いる。
【０１３１】
バッファーメモリ装置(100)は、水平線型、垂直線型、または一文字に対する書き時間を減少するために、水平、垂直、またはブロック形態の映像点を並列にアクセスしなければならない。追加的に対角線や逆対角線の映像点に対する並列的なアクセスは45°ずつ整数倍の線型形態の映像データに書き時間を減少させるとか、45°ずつ整数倍で回転させるために必要となる。だから、バッファーメモリ装置(100)における修正速度の向上のために、バッファーメモリ装置(100)はM×N映像i(＊、＊)内の基準座標(i、j)で、ブロック(BL)、水平(HR)、垂直(VR)、対角線(FD)、または逆対角線(BD)アクセス形態に対しての次のようなpq個の映像点に対する並列的なアクセスを提供しなければならない。
【０１３２】
0003802783.tif 000012
図11は基準座標(i、j)を持つ前記のアクセス形態を示す。ここで基準座標は基準映像点I(i、j)の座標を意味する。映像点を修正しようとする時、図11にあるバッファーメモリ装置の構成要素はディスプレー処理器の要請によって制御回路の制御により次の演算を順次的に行う。
【０１３３】
１．  レジスターt、i、jはディスプレー処理器によるデータのアクセス形態(ブロックは1、水平は2、垂直は3、対角線は4、逆対角線は5である)の選択tとアクセス形態(1)~(5)によって要求された基準座標(i、j)が入れ込まれ、データ自体は行優先順位のデータレジスターに位置する。
【０１３４】
２．  アドレス計算とルーティング回路(ACRC)はm個の映像点のアドレスを計算し、その値をm個のメモリモジュールにルーティングさせる。
【０１３５】
３．  メモリモジュール選択回路はアクセスされるpq個のメモリモジュールを選択する。
【０１３６】
４．  データルーティング回路はデータレジスターにあるpq個の映像点をm個のメモリモジュールにルーティングさせる。
【０１３７】
５．  書き信号はpq個の選択されたメモリモジュールに映像点を貯蔵する。
【０１３８】
ここで、演算2、3、4が並列的に行われる。
【０１３９】
同様にバッファーメモリ装置から映像点を読み取る時、バッファーメモリ装置の構成要素は次のような演算を順次的に行う。
【０１４０】
１．  t、i、jレジスターに要請された値を入れ込む。
【０１４１】
２．  アドレス計算とルーティング回路(ACRC)がm個の映像点アドレスを計算し、その値はm個のメモリモジュールにルーティングさせる。
【０１４２】
３．  メモリモジュール選択回路はアクセスされるpq個のメモリモジュールを選択する。
【０１４３】
４．  読み信号によってpq個の選択されたメモリモジュールから映像点を読み取る。
【０１４４】
５．  データルーティング回路はm個のメモリモジュールからpq個の映像点をデータレジスターにルーティングし、アクセス形態(1)~(5)の選択によって行優先順位となっているpq個の映像点を整列する。
【０１４５】
ここで演算2と3が並列に行われる。
【０１４６】
図12は本発明によるアドレス計算とルーティング回路を示す。
【０１４７】
アドレス計算とルーティング回路はアドレス間差のために2個のSRAM、4個の5×1MUX、(m+3)個の加算器、(i/p)値のためのSRAM、及びバレルシフターで構成されている。
【０１４８】
ブロック、水平、対角線、逆対角線アクセス形態におけるアドレス間差の1番目間隔はμ(0≦μ< m)のi%p値によってp個の差の値で示される。水平アクセス形態におけるアドレス間差の1番目間隔はμ(0 ≦μ< m)のi%p値による変化はない。ブロック、水平、対角線、逆対角線アクセス形態におけるアドレス間差の2番目間隔はμ(0≦μ< m)のj%p値によってq個の差が二進数の値で示される。
【０１４９】
垂直アクセス形態におけるアドレス間差の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ビットである。
【０１５０】
図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 )である。
【０１５１】
アドレス間差のために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))である。
【０１５２】
(t・p+i%p)と(t・q+j%q)の値はpとqが全部2の乗数である時、掛け算や足し算なしに、それぞれ (t・p)、(i%p)、(t・q)、(j%q)の連結によって簡単に求めることができる。
【０１５３】
基準アドレスα(i、j)の計算に必要な一度の掛け算(i/p)s値のためにSRAMアクセスで代理する。もし基本アドレス計算での一度の掛け算を除くためにNが2の乗数ではないのに、sを2の乗数になるよう選択したら、M×N=960×1280の映像でアクセスされる部分の60%であるq (s -(N/qで整数部分と同じ或いはより大きな整数)) Mが使われないメモリ装置領域で追加された容量である。
【０１５４】
本発明によるアドレス計算とルーティング回路ではsが2の乗数ではない時、SRAMのアクセスで得られた(i/p)s値に基準アドレスのためにj/q値を加える。sが2の乗数である時は(i/p)sの値にi値の最下位ビットにlog2(s/p)ぐらいの0を追加して求める。i/pとj/q値の合計はm個の加算器にA入力で提供される。
【０１５５】
以下、アドレス計算及びアドレスルーティングに対して本発明によるハードウェアルゴリズムをハードウェア価格、制御の複雑性、速度などの事項を従来のメモリ装置(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.)と比べる。
【０１５６】
この比べではデータ内における任意の位置にある少なくとも3種のアクセス形態データの並列アクセスが支援され、アドレス計算及びアドレスルーティング回路のハードウェア具現が考察される。バンブーリスとモリン(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、 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、 IEEE Trans. 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)を計算する。
【０１５７】
だから表7に示すように1番目行に現われたハードウェアの構成要素と演算遅延時間がメモリ装置(D. C. Van Voorhis and T. H. Morrin、 IEEE Trans. Comput .、vol. C-27、 pp.113-125、 Feb. 1978.)でm個のメモリモジュールに対して、α(μ)が可能だったら速やかに計算されるのに必要となる。
【０１５８】
【表７】
0003802783.tif 000013
このメモリ装置(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個のアドレスを計算する。
【０１５９】
アドレスルーティング回路(ARC)は、まず二度のルーティングによって垂直アクセス形態の(iq+j-1)%(pq+1)や垂直アクセス形態の(iq+j-q)%(pq+1)の数によって整列されたアドレスを右側に回転する。
【０１６０】
このメモリ装置(J. W. Park、IEEE Trans. Comput .、vol. C-35、pp.669-674、July 1986)ではm個メモリモジュールのためのα(μ)を計算するために表7の3番目行のハードウェア構成要素と演算遅延時間が必要となる。
【０１６１】
他のメモリ装置(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である。
【０１６２】
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 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.)と比べると、本発明によるアドレス計算及びデータルーティング回路の重要な利点は速度側面で掛け算器の代わりにSRAMに代置したことと、マルチプレクサーを除いて制御の簡便化とゲートの数を減少させ、アドレス間差の大きさを(4p+q)×pq×log2(MN / pq) j+3q×qのビットから(4p+1)×m×log2(MN / pq)+(4q+1)×mに減少させたことである。
【０１６３】
一般的な字の大きさが8×8と同じとか大きいとする時、グラフィックディスプレーの良い性能のためには少なくともp=8、q=8でなければならない。また、pqの値はMとN間にある最小値の同じとか小さくなければならない。
【０１６４】
アドレス計算とルーティング回路のハードウェア構成要素と演算遅延時間をM×N×b = 960×1280×24である時、p = q = 8、m = 7である場合とp = q = 16、m = 257である場合に対して表8で比べる。
【０１６５】
【表８】
0003802783.tif 000014
前記のメモリ装置(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.)の掛け算器回路の演算速度を向上のための本発明によるメモリ装置ではSRAMで代置した。1ビット5×1マルチプレクサー一つのゲート数が12であり、全体加算器一つのゲート数が7だと仮定すると、m×log2(MN / pq)ビットの5×1マルチプレクサーのゲート数が12であり、一つの全体加算器のゲート数は全体加算器、即ち、1og2(4p+1)ビットの加算器一個+1og2(4q+1)ビットの加算器一個+1og2(MN / pq)ビットの加算器(pq+1)個のゲート数よりずっと多い。
【０１６６】
そのような構成要素を持つ従来のメモリ装置と比べて、本発明によるアドレス計算とルーティング回路はアドレス計算の後にメモリモジュール番号に従ってアドレスを整列するための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個のメモリモジュールの間の線数は9m×log2(MN/pq)である。しかし、本発明によるアドレス計算とルーティング回路での全体線の数は4m×log2(MN/pq)で従来の半分より少ない。
【０１６７】
表9はアドレス計算とルーティング回路のゲート数を三星電子のASICであるKG76(0.6μmゲートアレイライブラリ)のゲート数により比べた例である。
【０１６８】
【表９】
0003802783.tif 000015
演算遅延時間がM×N×b = 960×1280×24であり、pq > Mである時、媒介変数pとq値双方が32ではない8と32間の2の乗数である値を持つように設計した表10の演算遅延時間の仮定下で比べた。
【０１６９】
【表１０】
0003802783.tif 000016
ゲート数の割合と演算遅延時間の割合は従来のアドレス計算とルーティング回路のゲート数と演算遅延時間に対する本発明によるアドレス計算とルーティング回路それぞれの割合である。平均ゲート数の割合と平均演算遅延時間の割合はそれぞれ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であるバッファーメモリ装置を示す。
【０１７０】
【表１１】
0003802783.tif 000017
ここで、|(p1、q1)|と|(p2、q2)|はバッファーメモリ装置のpとq値をp1とq1、 p2とq2で示す。
【０１７１】
例えば、 |(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に増加される。
【０１７２】
データルーティング回路は一度のモジュロ計算と一度の回転演算を行って、メモリモジュール選択回路は一度のモジュロ計算と一度のデコーディング演算を行うため、データルーティング回路やメモリモジュール選択回路の演算遅延時間は本発明によるアドレス計算とルーティング回路の演算遅延時間より短い。だから、もしm個のメモリモジュールアクセス時間が本発明によるアドレス計算とルーティング回路の演算遅延時間より小さく、アドレス計算とルーティング回路のm個のメモリモジュールの間にm個のメモリ装置アドレスレジスターがあり、データルーティング回路とm個のメモリモジュールの間にm個のメモリ装置バッファーレジスターがあるとしたら、本発明によるバッファーメモリ装置はアドレス計算とルーティング回路の演算遅延時間の割合単位のパイプライン方式で行うことができる。
【０１７３】
また、ディスプレー処理器が本発明によるアドレス計算とルーティング回路の演算遅延時間内のバッファーメモリ装置からpq個の映像点に対して要素演算を行うと、本発明によるフレームバッファーディスプレー装置の全体的な性能は従来のアドレス計算とルーティング回路を使ったフレームバッファーディスプレー装置より平均1.353倍増加することができる。だから、本発明によるアドレス計算とルーティング回路は従来のメモリ装置より費用を少なくし、制御の複雑性を減少し、速やかにする。
【０１７４】
以下、少なくともデータアレイ内の任意の位置にある3種のアクセス類型のデータに対して同時アクセスが支援され、アドレス計算回路とアドレスルーティング回路、データルーティング回路のハードウェア具現が考慮されている従来のメモリ装置方式と本発明によるアドレス計算及びアドレスルーティング、データルーティング方式をアクセス類型、間隔、データアレイの大きさの制限とハードウェアの費用、速度、複雑性に対して比べた。
【０１７５】
間隔1を持つブロック、列、行、対角線、逆対角線アクセス形態のための本発明によるアドレス計算とルーティング回路は、従来のメモリ装置に比べてより低費用、更に単純化された制御複雑度、及びそして速やかな速度を持つことができる。
【０１７６】
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要素集合を定義した。
【０１７７】
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.)はα(μ)、即ち番目モジュールのアドレスを求めた。
【０１７８】
α(μ) = ((a+cM) (μ(-(b+eM+base))d' %m)+b+eM+base) / pq 、
ここで、(a+cM)・d' = 1%mであり、"base "はデータアレイの基準アドレス(i、j)であり、Mはアレイの行の数である。
【０１７９】
(a+cM)・d' =1%mからd'はmの倍数である間隔M、M+1、M-1のどんな場合でも求めることができない。なぜなら、aとcの値が下記のように各アクセス形態に正義されているからである。
【０１８０】
行: 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.)は間隔とデータアレイの大きさとメモリモジュール数に制約がある。
【０１８１】
一方、従来のメモリ装置と異なって、発明によるメモリ装置はデータアレイの大きさに対する制約がない。 ただ、本発明によるメモリ装置の制約は理論１から間隔がメモリモジュール個数の倍数ではなくにしなければならないということである。従来のメモリ装置(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. 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.)に使われと制御が非常に複雑になるはずである。それはアクセス形態と間隔がアドレスの整列に従属するからである。メモリ装置(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.)によって本発明によるメモリ装置のデータルーティングはマルチプレクサーとバレルシフターによって行われる。このメモリ装置では従来メモリ装置のデータルーティング回路内の多様な右側回転変換器を複雑で高くて遅いクロースバーネットワークで代置する。本発明ではマルチプレクシングと回転を使うデータルーティング方法が提案された。
【０１８２】
ここで、12種のアクセス形態に対して陽の間隔を持つ12種のデータルーティング形態がROMとlog2(2(m-1))×2(m-1)デコーダー、3相バッファーを用いたセレクター、そしてバレルシフターによって具現された間隔r1(=r%m)である2個のルーティング形態に減少される。また、表11によって、本発明によるアドレス計算、アドレスルーティング、及びデータルーティング回路は更に多いアクセス類型と間隔を支援する。
【０１８３】
よって、アドレス計算、アドレスルーティング及びデータルーティングにおいて、本発明による方法はアクセス形態、間隔及びデータアレイの大きさに対する制約とハードウェアの費用、速度及び複雑性の側面で従来のメモリ装置の方法より良いということが分かる。
【０１８４】
【発明の効果】
以上で説明したように本発明による衝突のフリのメモリ装置は従来メモリ装置より改善があった。一つのデータアレイ内に任意の位置にある少なくとも3種のアクセス形態のデータ要素に対する同時アクセスが支援される。更に、アクセス形態、間隔およびデータアレイ大きさの制約とハードウェア費用、速度、複雑性の制限内でメモリ装置内のアドレス計算及びアドレスルーティング回路、及びデータルーティング回路のハードウェア具現が考慮された。
【０１８５】
多様な行列演算と映像処理演算はpq個のプロセッシングエレメントを持つSIMD処理器とm(mは素数、m>pq)個のメモリモジュールを持つメモリ装置によって速度を向上することができる。
【０１８６】
SIMD処理器は間隔、データアレイの大きさ、データ要素の位置に制約がないデータアレイ内の陽数間隔を持つ多様な形態の四角形ブロックと8方向線型アクセス形態のpq個のデータ要素がアクセスされるメモリ装置が必要となる。
【０１８７】
本発明による素数個のメモリモジュールを持つ衝突防止メモリ装置は4方向四角形ブロック陽数の間隔に連関されたデータ要素がデータアレイ内のどの位置に置かれるが(南東側ブロック、南西側ブロック、北西側ブロック、北東側ブロック)、または8方向の線型(東側線型、南東側線型、南側線型、南西側線型、西側線型、北西側線型、北線型、北東側線型)アクセス形態のpq個データ要素に同時アクセスを支援することができる。
【図面の簡単な説明】
【図１】  メインコンピューターと取り付けられた多重SIMDコンピューターの関係を示す例示図である。
【図２ａ】  方向ブロックのアクセス形態、間隔及び基準座標の例示図である。
【図２ｂ】  8方向線型のアクセス形態、間隔及び基準座標の例示図である。
【図３】  衝突防止メモリ装置の一般的な設計の例示図である。
【図４】  データルーティング回路の詳細な回路図である。
【図５ａ】  8×8逆オメガネットワークのスイッチング要素の経路衝突の例示図である。
【図５ｂ】  N = 16セータネットワークのスイッチング要素の経路衝突の例示図である。
【図６】  μ(i、j)=(iq+j)%m、p=q=2とM×N = 32×32、m=5に対するメモリモジュール割り当て関数によって割り当てられたメモリモジュール番号の例示図である。
【図７】  p=q=2、M×N = 32×32及びs=16に対するアドレス割り当て関数α(i、j)=(i/p)s+j/qによって割り当てられたアドレスである。
【図８】  p=q=2、M×N = 32×32、s=16及びm=5に対するアドレス計算とルーティング回路の例示図である。
【図９】  p=q=2、M×N = 32×32及びs=16に対するメモリモジュールAとBの例示図である。
【図１０】  本発明によるメモリ装置を適用したグラフィックディスプレー装置の構成を概略的に示すブロック図である。
【図１１】  アクセス形態と基準座標の例示図である。
【図１２】  本発明によるアドレス計算とルーティング回路(ACRC)の詳細な回路図である。
【符号の説明】
１００  バッファーメモリ装置
【図１】
0003802783.tif 000018
【図２ａ】
0003802783.tif 000019
【図２ｂ】
0003802783.tif 000020
【図３】
0003802783.tif 000021
【図４】
0003802783.tif 000022
【図５ａ】
0003802783.tif 000023
【図５ｂ】
0003802783.tif 000024
【図６】
0003802783.tif 000025
【図７】
0003802783.tif 000026
【図８】
0003802783.tif 000027
【図９】
0003802783.tif 000028
【図１０】
0003802783.tif 000029
【図１１】
0003802783.tif 000030
【図１２】
0003802783.tif 000031