JPH0559453B2 - - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、多次元配列のブロツク化アドレツシ
ング装置に関し、特にページング方式により仮想
化された階層記憶システムを備える計算機システ
ムにおける多次元配列データの写像法、及び参照
法に関する。

〔従来の技術〕

従来のこの種の多次元配列のブロツク化アドレ
ツシング装置は多次元配列の一次元記憶への写像
法及び参照法として比較的単純な算出法で一次元
アドレスに変換できるため、多くのプログラミン
グ言語で採用されている。配列の添字から一次元
アドレスの算出は、通常の計算機が備えている加
減算器、乗算器を用いて計算される。

配列要素Ａ（I₁，I₂，……，In）への参照法とし
ては下記に示す計算式により与えられる。

（l₁−I₁＋｜d₁｜×（l₂−I₂＋｜d₂｜×（……｜d_o-1
｜×（l_o−I_o）……）））×ｓ＋ｂ なお、配列の宣言をａ（d₁，d₂，……，d_o）：：
ｓとする（ｎ＞＝１）。ａは配列名、d₁〜d_oは寸
法宣言子であり、寸法宣言子d_iはl_i：h_iのペアで記
述される。l_iは下限値を、h_iは上限値を示す。｜d_i
｜を寸法宣言子d_iの寸法と呼び、h_i−l_i＋１に等し
い。配列要素が占める記憶単位はｓバイトとす
る。さらにプログラミング言語上で宣言された配
列に対して言語処理系（コンバイラ、インタプリ
タ等）が決定する、配列データ記憶領域の起点ア
ドレスをｂとする。この起点アドレスｂは、配列
要素ａ（l₁，l₂，……，l_o）を指すアドレスと等価
である。

たとえば、二次元配列における多次元配列の写
像法は第４図ａに示すように従来の写像法は縦割
り的で、配列要素Ａ（１：４，１：４）の場合に、
Ａ（ｉ，ｊ）に対する参照は計算式（ｉ−１＋３
×（ｊ−１））×ｓ＋ｂにより求められる。これに
より、一次元空間上での配列要素の並びは第４図
ｂのようになる。配列データを用いてプログラミ
ングを行なう場合の典型的な配列要素への参照パ
ターンは、Ａ（ｉ，ｊ）に対してｉやｊを変化さ
せて参照するループを構成する場合であるが、第
４図ｂからわかるように、添字ｉを＋１もしくは
−１ずらして配列Ａに参照することは一次元記憶
上では連続した記憶領域への参照になるのに対し
て、添字ｊを＋１もしくは−１ずらして配列Ａに
参照することは、一次元記憶上では不連続な記憶
領域への参照となる。

また、第４図ｂにおいて、配列要素Ａ（１：４，
１：４）がページング方式による仮想記憶空間上
に展開されている様子を示すと、ページ・サイズ
は配列Ａの要素４個分に等しい。計算機の処理装
置がある時間間隔γ中に配列要素４個を参照した
とする。この参照がＡ（ｉ，１）ｉ＝１，４であ
るならばこの間に参照される記憶ページは１ペー
ジであるが、この参照がＡ（１，ｊ）ｊ＝１，４
であるならばこの間に参照される記憶ページは４
ページに渡る。明かに後者の参照は局所性に欠
き、主記憶に配列Ａ全体が入りきらない場合、主
記憶−二次記憶装置間で転送されるページ数が増
大する。平均的にみても必要となる主記憶ページ
数は2.5であり、Ａ（１，ｊ）ｊ＝１，４のような
参照になつて必要となる主記憶ページ数は増大す
る。このような現象によるプログラムの実行時間
増大、性能低下は、大規模な配列を用いる科学技
術計算プログラムにしばしばあらわれ、ワーキン
グ・セツト異常の一つとされている。この現象を
避けるためには、従来プログラムのコーデイング
法やアルゴリズムの設計階段において記憶参照の
局所性が保たれるように注意深く設計をすすめる
方法が一般的であり、プログラム作成を困難なも
のにしている。

そこで、比較的どのような参照パターンに対し
ても記憶参照の局所性の高い写像法が必要とな
る。これに関しては、サブマトリツクス法もしく
はブロツク化法と呼ばれる方式がある。ブロツク
化法により多次元配列を一次元記憶空間に写像す
る例として、二次元配列を一次元化する方式では
元の二次元配列の部分配列を一つのブロツクとし
て扱い、ブロツクに関する写像と、ブロツク内の
写像とを独立に行なう。例として配列要素Ａ
（１：４，１：４）を部分配列２×２で写像した
場合の一次元記憶空間上での様子は第２図ｂに示
すようにページ・サイズが配列Ａの要素４個分に
等しい場合を示している。計算機の処理装置があ
る時間間隔γ中に配列要素４個を参照したとす
る。この参照がＡ（ｉ，１）ｉ＝１，４であるな
らばこの間に参照される記憶ページは２ページで
あり、この参照がＡ（１，ｊ）ｊ＝１，４である
場合もこの間に参照される記憶ページは２ページ
である。前者の写像法と比べるとＡ（ｉ，１）ｉ
＝１，４の場合の必要主記憶ページ数が１から２
に増加したかわりに、Ａ（１，ｊ）ｊ＝１，４の
場合の必要主記憶ページ数が４から２に減少して
いる。平均的には２ページの主記憶ページが必要
であり、前者の写像法よりも低く押さえられてい
る。

〔発明が解決しようとする問題点〕

上述したように従来の多次元配列の一次元記憶
空間への写像法及び参照法は、展開された一次元
記憶空間がページング方式による仮想記憶空間で
実現されている場合に問題を生ずる。すなわち、
仮想記憶システムは参照の局所性を利用し、定義
された記憶空間は二次記憶装置に確保し、実際に
現在参照されている記憶ページのみを主記憶に配
置することで主記憶の有効利用を計つている。仮
想記憶システムが有効に作用するためには前提条
件である参照の局所性が成り立たなければならな
い。多次元配列を従来の方法で一次元記憶空間に
写像及び参照することは、この局所性に反する場
合がある。

また、ブロツク化写像法の有効性を示したが、
ブロツク化法は従来法式と比べ多次元空間から一
次元空間への写像コストが高く、その変換にはビ
ツトフイールドの切出し等が含まれ、従来のよう
にソフトウエアにより変換を行うことには問題が
あり、また、主記憶バンク上での衝突等の問題も
ある。本発明の目的はこれらの問題点を計算機の
アドレツシング・ハードウエアにより解決する多
次元配列のブロツク化アドレツシング装置を提供
することにある。

〔問題点を解決するための手段〕

本発明によれば、多次元配列データを一次元ア
ドレス空間に写像／参照するブロツク化アドレツ
シング装置において、 配列要素Ａ（I₁，I₂，……I_o）を示す各次元の添
字値I_i（０≦I_i≦d_i−１：１≦ｉ≦ｎ）を保持する
ｎ個の添字値レジスタと、各次元の添字寸法d_i
（１≦ｉ≦ｎ−１）を2^Nで割算を行い商が２のべ
き数となるように切上げたブロツク添字寸法RM_i
（１≦ｉ≦（ｎ−１））を保持するｎ−１個の添字
寸法レジスタと、 前記添字値レジスタの上位Ｎ−１ビツトのブロ
ツクアドレス部RB_i（１≦ｉ≦ｎ）と、前記添字
寸法レジスタのブロツク添字寸法値RM_iから一次
元記憶空間のブロツクアドレスとして RB₁＋RM₁×（RB₂＋RM₂×（……（RM_o-1×
RB_o）……）を演算するブロツクアドレス演算手
段と、 前記添字値レジスタ下位Ｎビツト列のブロツク
内アドレス部RI_i（１≦ｉ≦ｎ）のｎ個のビツト列
からRI_o、（RI_o＋RI_o-1）、（RIn＋RI_o-1＋RI_o-2）、
……（RI_o＋……RI₁）のｎ個の演算値を求め、
演算結果の下位ビツト列を並べて一次元記憶空間
のブロツク内アドレスを生成するブロツク内アド
レス生成手段と、 前記ブロツクアドレス演算手段と前記ブロツク
内アドレス生成手段とに接続される一次元アドレ
スを保持する出力レジスタとから構成されること
を特徴とする多次元配列のブロツク化しアドレツ
シング装置が得られる。

〔実施例〕

次に本発明の実施例について図面を参照して説
明する。

第１図は本発明の一実施例を示す。第１図にお
いて、本実施例は多次元配列の一次元化アドレツ
シング方式により、三次元の添字アドレスから一
次元添字アドレスを生成する装置で、配列要素Ａ
（ｉ，ｊ，ｋ）を参照する場合配列添字ｋ、配列
添字ｊおよび配列添字ｉをそれぞれ保持するレジ
スタ１１，１２および１３と、添字ｉの添字寸法
を２のＮ乗で割つた商を切上げた値を保持する入
力レジスタ１４と、添字ｊの添字寸法を２のＮ乗
で割つた商を切上げた値を保持する入力レジスタ
１５と添字レベルでの一次元アドレスを出力する
出力レジスタ２２とを含む。

レジスタ１１，１２および１３は下位からＮビ
ツト目とＮ＋１ビツト目を境にして２つのフイー
ルドから成つている。Ｎの値は対象とする計算機
のページ・サイズ等をもとに定める必要があるが
ページ・サイズが4Kバイトの単精度実数を配列
要素の基準と考えるとＮ＝４程度となる。すなわ
ち16×16×16の部分配列がひとつのブロツクとな
り、この部分配列が占める記憶サイズは単精度実
数配列の場合、４ページに相当する。配列要素が
８バイトの倍精度実数配列の場合には16×16×16
の部分配列８ページを占めることになる。

更にこの実施例においてはレジスタ１１と入力
レジスタ１５とに接続される掛け算器１６と、レ
ジスタ１２と掛け算器１６とに接続される全加算
器１８と、入力レジスタ１４と全加算器１８とに
接続される掛け算器１７と、レジスタ１３と掛け
算器１７に接続されている全加算器１９と、レジ
スタ１１とレジスタ１２とに接続されている全加
算器２０と、全加算器２０とレジスタ１３とに接
続されている全加算器２１とを含み、全加算器１
９〜２１とレジスタ１１とが出力レジスタ２２に
接続されるように構成されている。

本実施例においてはブロツク内の一次元アドレ
ス計算において添字ｉ，ｊ，ｋのいずれかを連続
的に変化させて参照に対してバンク衝突を避ける
ようにしている。この過程は添字入力ｉ，ｊの下
位Ｎビツトをそのまま出力に導かず、添字ｋとｊ
の下位Ｎビツトの和（あふれは捨てる）、添字ｋ，
ｊ，ｉの下位Ｎビツトの和（あふれは捨てる）を
用いる。第２図は複数バンクからなる主記憶装置
にブロツク化写像した場合を示す。第２図におい
て、８バイト並列、16バンクから構成される主記
憶装置にＡ（１：16，１：16，１：16）：：８の配
列が写像された状態を示す。ここではＮ＝４とし
ている。Ａ（ｉ，１，１）ｊ＝１，16A（１，１，
ｋ）ｋ＝１，16等添字のいずれかを連続的にスラ
イドさせてのアクセスに対してバンク衝突を起こ
さない。ただし、添字ｉ，ｊ，ｋの和が一定にな
るような形で添字を変化させると同一バンクへの
参照となるので、そのような形での参照を含むプ
ログラムに対しては添字ｉ，ｊ，ｋの下位Ｎビツ
トをそのまま出力に導く。

このように本実施例はバンク衝突を回避するた
めの機構を備えている。計算機の主記憶装置は演
算処理装置等との間高速データ転送を行なうため
に複数バンクに分割されている場合があり、異な
るバンクに対するアクセスは高速に処理すること
が可能である。配列Ａ（ｉ，ｊ，ｋ）に対するｉ
もしくはｊ，ｋを変化させての連続参照も主記憶
中で同一バンクへのアクセスとならなければ高速
に処理可能である。

また、この実施例は三次元配列のブロツク化を
基本動作として行なうものであるのであるが、二
次元配列及び四次元以上の配列を一次元化するた
めにも使用可能である。第５図に本発明を多次元
の配列に対して構成した一実施例を示す。

第５図において、配列要素Ａ（I₁，I₂，……I_o）
を参照する場合に各次元の添字値I₁，I₂，……I_o
を保持するｎ個の添字値レジスタ５０₁〜５０_o
と、I₁，I₂，……I_oの添字寸法d₁，d₂，……d_o-1を
2^Nで割算を行い商が２のべき数となるように切り
上げたブロツク添字寸法RM_i（１≦ｉ≦（ｎ−１））
を保持するｎ−１個の添字寸法レジスタ５１₁〜
５１_o-1と、添字値レジスタ５０₁〜５０_oと添字
寸法レジスタ５１₁〜５１_o-1に接続される掛け算
器５２₁〜５２_o-1及び全加算器５３₁〜５３_o-1，
５４₁〜５４_o-1と一次元アドレスを保持する出力
レジスタ５５とを含む。

添字値レジスタ５０₁〜５０_oは第１図のレジス
タ１１，１２と同様に下位ビツト目とＮ−１ビツ
ト目を境にして、下位Ｎビツトはブロツク内アド
レス部RIi（１≦ｉ≦ｎ）、上位Ｎ−１ビツトはブ
ロツクアドレス部RBi（１≦ｉ≦ｎ）とから成つ
ている。

添字値レジスタ５０_oのブロツク内アドレス部
RI_oは、出力レジスタ５５及び全加算器５４_o-1に
送られ、添字値レジスタ５０₁〜５０_o-1のブロツ
ク内アドレス部RI_i（１≦ｉ≦ｎ）は、全加算器５
４₁〜５４_o-1に送られ、RI_o、（RI_o＋R1_o-1）、
（RI_o＋RI_o-1＋RI_o-2）、……（RI_o＋……RI₁）の
ｎ個の演算値を求め、ブロツク内アドレスとして
出力レジスタ５５に送られる。

また、ブロツクアドレス生成のために添字レジ
スタ５０₁から５１_oのブロツクアドレス部RB_i（１
≦ｉ≦ｎ）は、掛け算器５２_o-1及び全加算器５
３₁〜５３_o-1に送られ、添字寸法レジスタ５１₁
〜５１_o-1に保持されているブロツク添字寸法
RM₁，RM₂，……RM_o-1は掛け算器５２₁〜５２
_ｏに送られ、一次元記憶空間のブロツクアドレス
として次式の演算を行い出力レジスタ５４に送出
する。

RB₁＋RM₁×（RB₂＋RM₂×（……（RM_o-1×
RB_o）……）出力レジスタ５５の出力は一次元ア
ドレスとして送出される。

第３図はブロツク化写像法により二次元配列を
一次元記憶空間に写像する方式を示す。第３図に
おいて、まず二次元配列を一次元化する場合に
は、入力レジスタ１３に値０をセツトする。ま
た、入力レジスタ１４は値１をセツトする。すな
わち、配列要素Ａ（ｉ，ｊ）の参照に対して、入
力レジスタ１１に配列添字ｊ、入力レジスタ１２
に配列添字ｉの値をセツトし、入力レジスタ１５
に添字ｉの添字寸法を２のＮ乗で割つた商を切上
げた値をセツトして使用する。この場合出力レジ
スタ２２の下位Ｎビツトは意味を持たないので、
添字レベルの一次元アドレスから求めるべき一次
元アドレスを計算するまえに右にＮビツトシフト
する必要がある。配列Ａ（１：128，１：128）：：
４に対して32×32でブロツク化されている状態で
Ａ（ｉ，ｊ）に参照すると、各次元の添字値を保
持するレジスタ１２，１１に添字ｉ，ｊの下限値
からの増分ｉ−１，ｊ−１をセツトする。各次元
の添字値を保持するレジスタ１２，１１はブロツ
ク化する単位が32×32であるので下位５ビツトが
ブロツク内アドレス部であり、下位５ビツトを除
いた上位がブロツクアドレス部である。添字寸法
を保持するレジスタ１４には添字ｉの寸法１２８
を32で割つた商を切上げた値４をセツトする。二
次元配列の場合、添字寸法ｊは必要ない。

次に、装置を動作させることにより出力レジス
タ２２に結果が得られる。出力レジスタ２２のブ
ロツクアドレス部は、添字寸法ｉを保持するレジ
スタ１２の値に添字値ｊの値を保持するレジスタ
１１のブロツクアドレス部を掛けた値に、添字値
ｉの値を保持するレジスタのブロツクアドレスを
加算したものである。他方、出力レジスタ２２の
ブロツク内アドレス部は、添字値ｊの値を保持す
るレジスタ１１のブロツク内アドレス部と、この
値に添字値ｉの値を保持するレジスタ１２のブロ
ツク内アドレス部を加算した値（あふれは捨て
る）を直列に並べたものである。

最後に出力レジスタ２２に得られた値は添字レ
ベルの一次元アドレスであるので、さらに演算処
理装置により、配列要素の占める記憶サイズ４と
出力レジスタ２２の値を掛け、さらに配列Ａの起
点アドレスｂを加算することにより求める一次元
アドレスが生成される。

また、四次元以上の配列を写像する場合である
が、この場合は配列添字を三次元単位に区切りブ
ロツク化し、その合成には従来の方法を用いるこ
ともできる。すなわち、配列Ａ（ｉ，ｊ，ｋ，１）
に対してはこれをＡ（ijk，１）とみなし、添字
ijkの算出に本装置を用い、添字ijkと１の合成に
は従来方法でこれを行なう。

〔発明の効果〕

以上述べたように、本発明は多次元配列の一次
元記憶空間への写像／参照をブロツク化写像法式
により行なうことで、ページング方式による仮想
記憶システムの主記憶−二次記憶装置間のページ
転送回数を低減することができる。ブロツク化写
像方式は、参照する配列要素を指す各次元の添字
値を保持するレジスタと各次元の添字寸法を保持
するレジスタを有し、添字値を保持するレジスタ
のブロツクアドレス部と添字寸法を示すレジスタ
の積和から一次元記憶空間のブロツクアドレスを
生成し、添字値を保持するレジスタのブロツク内
アドレス部の加算結果から一次元記憶空間のブロ
ツク内アドレスを生成する。多次元配列のブロツ
ク化アドレツシング装置を計算機の演算処理装置
内に設けることにより、バンク衝突を避けるとと
もに、従来の写像方式と同程度の時間コストによ
り写像することが可能である。

【図面の簡単な説明】

第１図は本発明の一実施例により三次元配列を
一次元記憶空間にブロツク化写像する装置を示す
図、第２図は複数バンクからなる主記憶装置にブ
ロツク化写像した場合を示す図、第３図はブロツ
ク化写像法により二次元配列を一次元記憶空間に
写像する方式を示す図、第４図は従来の方式によ
り二元配列を一次元記憶空間に写像する方式を示
す図、第５図は本発明の一実施例による多次元配
列を一次元記憶空間にブロツク化写像する装置を
示す図である。 １１，１２，１３……配列添字を保持するレジ
スタ、１４，１５……入力レジスタ、１６，１７
……掛け算器、１８，１９……全加算器、２０，
２１……加算器、２２……出力レジスタ。

Claims (1)

1. 【特許請求の範囲】 １ 多次元配列データを一次元アドレス空間に写
   像／参照するブロツク化アドレツシング装置にお
   いて、 配列要素Ａ（I₁，I₂，……I_o）を指す各次元の添
   字値I_i（Ｏ≦I_i≦d_i−１：１≦ｉ≦ｎ）を保持する
   ｎ個の添字値レジスタと、各次元の添字寸法d_i
   （１≦ｉ≦ｎ−１）を2^Nで割算を行い商が２のべ
   き数となるように切上げたブロツク添字寸方法
   RM_i（１≦ｉ≦（ｎ−１）を保持するｎ−１個の添
   字寸法レジスタと、 前記添字値レジスタの上位Ｎ−１ビツトのブロ
   ツクアドレス部RB_i（１≦ｉ≦ｎ）と、前記添字
   寸法レジスタのブロツク添字寸法値RM_iから一次
   元記憶空間のブロツクアドレスとしてRB₁＋
   RM₁×（RB₂＋RM₂×（……（RM_o-1×RB_o）…
   …）を演算するブロツクアドレス演算手段と 前記添字値レジスタの下位Ｎビツト列のブロツ
   ク内アドレス部RI_i（１≦ｉ≦ｎ）のｎ個のビツト
   列からRI_o、（RI_o＋RI_o-1）、（RIn＋RI_o-1＋RI_o-2）
   ……（RIn＋……＋RI₁）のｎ個の演算値を求め、
   演算結果の下位Ｎビツト列を並べて一次元記憶空
   間のブロツク内アドレスを生成するブロツク内ア
   ドレス生成手段と、 前記ブロツクアドレス演算手段と前記ブロツク
   内アドレス生成手段とに接続される一次元アドレ
   スを保持する出力レジスタとから構成されること
   を特徴とする多次元配列のブロツク化アドレツシ
   ング装置。