(57)【特許請求の範囲】
【請求項１】
変換されたＭ（Ｍは正の整数）ビットのデータアドレスを使用して、サイズＳ（Ｓは正の整数かつ２の累乗）の複数のＮ（Ｎは正の整数）個のメモリブロックをインターリーブする方法であって、該メモリブロックのラインのサイズがＬ（Ｌは正の整数かつ２の累乗）であり、
（ａ）Ａ＝log2(S)、Ｂ＝Ｍ−Ａ、及びＩ＝切り捨て（log2(N)）の値を計算するステップと、
（ｂ）第１のビット群（Ｂ＿bits）を、変換されるアドレスの前記Ｂ個の最上位ビット（ＭＳＢ）として定義するステップと、
（ｃ）第２のビット群（Ａ＿bits）を、変換されるアドレスの前記Ａ個の最下位ビット（ＬＳＢ）として定義するステップと、
（ｄ）第３のビット群（Ｉ＿bits）を、Ａ＿bitsのlog2（Ｌ）個のＬＳＢを最初に取り除いた後のＡ＿bitsの前記Ｉ個のＬＳＢとして定義するステップと、
（ｅ）調整されない和（ＳＵＭ）と調整された和（ＡＤＪ＿ＳＵＭ）を、以下の定義、すなわち、
ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits、及び
ＡＤＪ＿ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−Ｎ
に従って計算するステップと、
（ｆ）変換されるアドレスに対応するブロック番号を定義するステップであって、ＳＵＭの値又はＡＤＪ＿ＳＵＭの値を前記ブロック番号として選択することからなる、ステップと、
（ｇ）前記ブロック番号に従ってメモリをアドレスするステップ
を含む、方法。
【請求項２】
ブロック番号を定義する前記ステップが、ＡＤＪ＿ＳＵＭがゼロ未満である場合にはＳＵＭの値をブロック番号として選択し、ＡＤＪ＿ＳＵＭがゼロ以上である場合には、ＡＤＪ＿ＳＵＭの値をブロック番号として選択することからなる請求項１の方法。
【請求項３】
インターリーブされた複数の群が存在する場合に、前記ステップ（ａ）〜（ｄ）を、インターリーブされた各々の群について実施するステップをさらに含む、請求項１または２の方法。
【請求項４】
各群が番号ＧＳによって特定される複数の群に、前記メモリブロックを割り当てるステップと、
調整されない和を計算する前記ステップで計算された和から、前記番号ＧＳを減算するステップであって、これによって、これらの和が、ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−ＧＳ、及びＡＤＪ＿ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−（Ｎ＋ＧＳ）としてさらに定義される、ステップと、
ブロック番号を定義する前記ステップで定義された前記ブロック番号によって表されるブロック内のメモリ位置に対応するオフセットアドレスを定義するステップであって、該オフセットがＡ＿bitsの値によって定義される、ステップと、
前記ブロック番号に従ってメモリをアドレスするステップ
とからさらになる請求項１または３の方法であって、
ブロック番号を定義する前記ステップが、ＡＤＪ＿ＳＵＭがゼロ未満である場合には、ＳＵＭの値をブロック番号として選択し、ＡＤＪ＿ＳＵＭがゼロ以上である場合には、ＡＤＪ＿ＳＵＭの値をブロック番号として選択することからなる、方法。
【請求項５】
変換されたＭ（Ｍは正の整数）ビットのデータアドレスを使用して、サイズＳ（Ｓは正の整数かつ２の累乗）の複数のＮ（Ｎは正の整数）個のメモリブロックをインターリーブする方法であって、該メモリブロックのラインのサイズがＬ（Ｌは正の整数かつ２の累乗）であり、
Ａ＝log2(S)、Ｂ＝Ｍ−Ａ、及びＩ＝切り捨て（log2(N)）の値を計算するステップと、
変換されるアドレスの第１のビット群（Ｂ＿bits）を特定するステップであって、Ｂ＿bitsは、変換されるアドレスの前記Ｂ個の最上位ビット（ＭＳＢ）である、ステップと、
変換されるアドレスの第２のビット群（Ａ＿bits）を特定するステップであって、Ａ＿bitsは、変換されるアドレスの前記Ａ個の最下位ビット（ＬＳＢ）である、ステップと、
変換されるアドレスに対応するインターリーブインデックスを定義する第３のビット群（Ｉ＿bits）を特定するステップであって、Ｉ＿bitsは、第２のビット群（Ａ＿bits）のlog2(Ｌ)個の最下位ビットを最初に取り除いた後の前記Ａ＿bitsの前記Ｉ個の最下位ビットである、ステップと、
各群が番号ＧＳによって特定される複数の群に、前記メモリブロックを割り当てるステップと、
調整されない和（ＳＵＭ）と調整された和（ＡＤＪ＿ＳＵＭ）を、以下の定義、すなわち、
ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−ＧＳ、及び
ＡＤＪ＿ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−（Ｎ＋ＧＳ）
に従って計算するステップと、
変換されるアドレスに対応するブロック番号を定義するステップであって、ＳＵＭの値又はＡＤＪ＿ＳＵＭの値を前記ブロック番号として選択することからなる、ステップと、
前記ブロック番号に従ってメモリをアドレスするステップ
を含む、方法。
【請求項６】
（ａ）コンピュータと、
（ｂ）前記コンピュータに結合され、及びサイズＳのＮ個のメモリブロックからなるメモリ手段であって（Ｓは正の整数かつ２の累乗であり、Ｎは正の整数）、各記憶位置が関連するＭ（Ｍは正の整数）ビットのアドレスによって特定可能である、関連する記憶位置内のデータ値のリストを記憶するためのメモリ手段と、
（ｃ）インターリーブ方式で、前記データ値を前記メモリ手段から読み出し、また、前記データ値を前記メモリ手段に書き込むためのアドレス手段であって、
(i)Ａ＝log2(S)、Ｂ＝Ｍ−Ａ、及びＩ＝切り捨て（log2(N)）の値を計算するための手段と、
(ii)変換されるアドレスの第１のビット群（Ｂ＿bits）を特定するための手段であって、Ｂ＿bitsは、変換されるアドレスの前記Ｂ個の最上位ビット（ＭＳＢ）である、手段と、
(iii)変換されるアドレスの第２のビット群（Ａ＿bits）を特定する手段であって、Ａ＿bitsは、変換されるアドレスの前記Ａ個の最下位ビット（ＬＳＢ）である、手段と、
(iv)変換されるアドレスに対応するインターリーブインデックスを定義する第３のビット群（Ｉ＿bits）を特定するための手段であって、Ｉ＿bitsは、第２のビット群（Ａ＿bits）のlog2(Ｌ)個の最下位ビットを最初に取り除いた後の前記Ａ＿bitsの前記Ｉ個の最下位ビットである、手段と、
(v)調整されない和（ＳＵＭ）と調整された和（ＡＤＪ＿ＳＵＭ）を、以下の定義、すなわち、
ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits、及び
ＡＤＪ＿ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−Ｎ
に従って計算するための手段と、
(vi)変換されるアドレスに対応するブロック番号を定義するための手段であって、ＡＤＪ＿ＳＵＭがゼロ未満である場合には、ＳＵＭの値をブロック番号として選択し、ＡＤＪ＿ＳＵＭがゼロ以上である場合には、ＡＤＪ＿ＳＵＭの値をブロック番号として選択するための手段とから構成される手段
とからなるアドレス手段と、
（ｄ）前記メモリ手段を、各群が番号ＧＳによって特定される複数の群に分割するための手段と、
（ｅ）調整されない和と調整された和を計算するための前記手段によって計算された和から、各群を特定する前記番号ＧＳを減算するための手段
とからなるディジタルシステム。
【請求項７】
前記第２のビット群（Ａ＿bits）によって、変換されるアドレスに対応する特定のメモリブロック内のオフセットが定義される、請求項６のディジタルシステム。
【請求項８】
コンピュータと、
前記コンピュータに結合され、及びサイズＳのＮ個のメモリブロックからなるメモリ手段であって（Ｓは正の整数かつ２の累乗であり、Ｎは正の整数）、各記憶位置が関連するＭ（Ｍは正の整数）ビットのアドレスによって特定可能である、関連する記憶位置内のデータ値のリストを記憶するためのメモリ手段と、
インターリーブ方式で、前記データ値を前記メモリ手段から読み出し、また、前記データ値を前記メモリ手段に書き込むためのアドレス手段であって、
変換されるアドレスの第１のビット群（Ｂ＿bits）を特定するための手段
と、
変換されるアドレスに対応するインターリーブインデックスを定義する第２のビット群（Ｉ＿bits）を特定するための手段と、
調整されない和（ＳＵＭ）と調整された和（ＡＤＪ＿ＳＵＭ）を、以下の定義、すなわち、
ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits、及び
ＡＤＪ＿ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−Ｎ
に従って計算するための手段
とからなるアドレス手段と、
変換されるアドレスに対応するブロック番号を定義するための手段であって、ＳＵＭの値又はＡＤＪ＿ＳＵＭの値を前記ブロック番号として選択することからなる、手段と、
Ａ＝log2(S)、Ｂ＝Ｍ−Ａ、及びＩ＝切り捨て（log2(N)）の値を計算するための手段と、
Ｂ＿bitsを、変換されるアドレスの前記Ｂ個の最上位ビット（ＭＳＢ）として定義するための手段と、
Ａ＿bitsを、変換されるアドレスの前記Ａ個の最下位ビット（ＬＳＢ）として定義するための手段と、
Ｉ＿bitsを、Ａ＿bitsのlog2（Ｌ）個のＬＳＢを最初に取り除いた後のＡ＿bitsの前記Ｉ個のＬＳＢとして定義するための手段であって、Ｌは、前記メモリブロック内のラインの数であって、正の整数かつ２の累乗である、手段
とからなるディジタルシステム。
【請求項９】
（ａ）コンピュータと、
（ｂ）前記コンピュータに結合され、及びサイズＳのＮ個のメモリブロックからなるメモリ手段であって（Ｓは正の整数かつ２の累乗であり、Ｎは正の整数）、各記憶位置が関連するＭ（Ｍは正の整数）ビットのアドレスによって特定可能である、関連する記憶位置内のデータ値のリストを記憶するためのメモリ手段と、
（ｃ）インターリーブ方式で、前記データ値を前記メモリ手段から読み出し、また、前記データ値を前記メモリ手段に書き込むためのアドレス手段であって、
(i)第１のビット群（Ｂ＿bits）を特定するための手段であって、Ａ＝log2(S)、Ｂ＝Ｍ−Ａ、及びＩ＝切り捨て（log2(N)）の値を計算するための手段、及び変換されるアドレスの前記Ｂ個の最上位ビット（ＭＳＢ）としてＢ＿bitsを定義するための手段とからなる手段と、
(ii)変換されるアドレスに対応するインターリーブインデックスを定義する第２のビット群（Ｉ＿bits）を特定するための手段であって、変換されるアドレスの前記Ａ個のＬＳＢ（Ａ＿bits）を特定するための手段、及び、Ｌが前記メモリブロック内のラインの数であって、正の整数かつ２の累乗である場合において、Ｉ＿bitsを、Ａ＿bitsのlog2（Ｌ）個の最下位ビット（ＬＳＢ）を最初に取り除いた後のＡ＿bitsの前記Ｉ個の最下位ビットとして定義するための手段とからなる手段と、
(iii)前記メモリ手段を、各群が番号ＧＳによって特定される複数の群に分割するための手段と
(iv)調整されない和（ＳＵＭ）と調整された和（ＡＤＪ＿ＳＵＭ）を、以下の定義、すなわち、
ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−ＧＳ、及び
ＡＤＪ＿ＳＵＭ＝Ｂ＿bits＋Ｉ＿bits−（ＧＳ＋Ｎ）
に従って計算するための和手段と、
(v)変換されるアドレスに対応するブロック番号を定義するための手段であって、ＡＤＪ＿ＳＵＭがゼロ未満である場合には、ＳＵＭの値をブロック番号として選択し、ＡＤＪ＿ＳＵＭがゼロ以上である場合には、ＡＤＪ＿ＳＵＭの値をブロック番号として選択することからなる手段
とから構成されるアドレス手段とからなるディジタルシステム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は概括的にはメモリのアドレス指定に関し、特に、種々のブロックサイズのブロックメモリのアドレス指定をインターリーブ方式で実行する方法と装置に関する。
【０００２】
【従来の技術】
コンピュータ及びコンピュータシステムは、代表的には２つのバス、すなわちアドレスバスとデータバスとを有している。アドレス指定及び制御のために用いられるアドレスバスは、その幅は通常は固定しており、またコンピュータの内部メモリと周辺装置との間のトランザクションの実行を開始するのに必要な信号を搬送する。データは、代表的には、データバスを経て転送される。場合によっては、アドレスバスとデータバスはアドレスとデータを転送するために多重化される。
【０００３】
コンピュータの記憶領域をインターリーブされたメモリブロックもしくはメモリカードに構成する必要がある場合が多い。インターリーブされたメモリは、サイクルを小部分に分割して２つ又はそれ以上のメモリブロックにアクセスすることを許容し、それによってサイクル時間を大幅に短縮し、メモリの速度を高めることができる。最も簡単なインターリーブ手順では、一群のアドレス内又はリスト内のアドレスの連続するラインアドレスを順次番号付けされたメモリブロックへと割り当てる。しかし、この方法は、一般に、所定のアドレスのブロック番号を決定するために大規模な「モジュロ演算」の操作が必要である。
【０００４】
モジュロ演算は剰余関数として理解することが最も簡単である。例えば、２１÷４は５プラス剰余の１である。従って、２１のモジュロ５は１である。よく知られているように、除算は実装するのにコストがかかるので、モジュロ演算を反復的な減算方式で実行することができ、そこで結果がモジュラス（前記の例では５）より小さくなるまで該モジュラスを最初の数（前記の例では２１）から反復的に減算する。例えば、２１のモジュロ５は次のように計算される。
【０００５】
２１−５＝１６（＞＝５、継続）
１６−５＝１１（＞＝５、継続）
１１−５＝６（＞＝５、継続）
６−５＝１（＜５、停止、結果は１）
各々が、２５６Ｋバイトの３ブロックとして構成されたメモリを有するシステムでは、２５６Ｋモジュロ３のアドレスの計算を必要とし、これは任意数のＮ個のブロック用に設計されたハードウェアでは困難であろう。最も容易な簡略化は、２の累乗であるＮ（モジュラス）の値だけを許容して、モジュロＮ演算がビットフィールドの抽出だけを含むようにすることである。しかし、この方法は、特に増分的にメモリを追加する場合にはフレキシビリティがなさすぎる。
【０００６】
前述の「ビットシフト」インターリーブ方式とは別の方法は、２の累乗のメモリカードをインターリーブするために、アドレスビットを用いて該カードを起動させる。例えば、代表的な、非インターリーブ方式のバイトアドレスシステムを考えてみよう。各メモリカードがアクセス毎に３２ビット（４バイト）を供給するものと想定する。更に、アドレス空間が２０ビットであり、メモリカードが各々６４Ｋバイトであるものと想定する。この場合にはアドレス空間は次のように配置することができる。
【０００７】
【表１】
0003599352.tif 000002
【０００８】
２つのメモリカードをインターリーブすることができるようにこの構成を修正するために、オフセットビットが１ビットだけ左にシフトされ、最初のオフセットビットのＬＳＢ（最下位のビット、ビット１７）が、４番目のカード選択ビット、又はインターリーブビットとして用いられる。
【０００９】
【表２】
0003599352.tif 000003
【００１０】
この方法とその変化形は広範に利用されている。これは２の累乗のメモリブロックを有するシステムに容易に拡張することができる。しかし、この方法も、前述のビットシフト方式と同様に、増分的にメモリを加える場合にフレキシビリティがなさすぎる。
【００１１】
前述の論議は、インターリーブ回路の複雑さを解消するために、既知のインターリーブシステムでは２の累乗、例えば２、４、８等の形でメモリブロックを提供する必要があるという事実を反映したものである。このようなシステムでは、例えば６バンクのメモリは、２バンク及び４バンクとして、又は２つのインターリーブメモリシステムの３個のバンクとして構成されなければならないであろう。インターリービングを実行するための回路が比較的複雑であるため、任意の数のバンクは従来の技術では実用的ではなかった。しかしながら、例えばシステムにメモリを追加する場合には、２の累乗ではない任意の数のメモリバンクをインターリーブできることは利点となる。
【００１２】
【発明が解決しようとする課題】
従って、本発明の目的は、任意数のメモリブロックでメモリのインターリービングを実行するための実用的なシステムを提供することである。本発明の更に別の目的は、メモリブロックをアドレスバスに接続でき、それぞれのブロックが自己選択するために利用できるブロック識別番号をつけることができる方法と、該方法に対応する装置を提供することである。本発明はこれらの課題を達成するものである。
【００１３】
【課題を解決するための手段】
本発明の一実施例は、Ｎ個のブロックの各々がサイズＳ（バイト）である複数のＮ個のメモリブロックをインターリーブする方法を提供する。本発明に従えば、Ｍ−ビットのデータアドレスは、各々のブロックがサイズＬ（バイト）のラインに群として分類されたＳバイトを有するインターリーブされたメモリブロックの対応するアドレスに変換される。
【００１４】
この方法は、最初に、変換されるアドレスの第１群のビット（Ｂ＿ｂｉｔｓ）を特定し、次に、その変換されるアドレスに対応するインターリーブインデックスを定める第２群のビット（Ｉ＿ｂｉｔｓ）を特定するステップを含んでいる。好ましい実施例では、次の値を計算することによってＢ＿ｂｉｔｓ及びＩ＿ｂｉｔｓが決定される。すなわち、Ａ＝ｌｏｇ２（Ｓ）、Ｂ＝Ｍ−Ａ及びＩ＝切捨て（ｌｏｇ２（Ｎ））。次にＢ＿ｂｉｔｓが、変換されるアドレスのＢ個の最上位ビットとして定義される。次に、変換されるアドレスの最下位のビット（“Ａ＿ｂｉｔｓ”）が特定される。次に、Ａ＿ｂｉｔｓのｌｏｇ２（Ｌ）個の最下位ビットを最初に切り捨てた後にＡ＿ｂｉｔｓのうちのＩ個の最下位ビットとしてＩ＿ｂｉｔｓが定義される。これに従って、Ａ＿ｂｉｔｓはＢ＿ｂｉｔｓにより定義されたブロック内のオフセットを定義する。
【００１５】
次に、“調整されない和”（“ＳＵＭ”）と調整された和（“ＡＤＪ＿ＳＵＭ”）が次の定義に従って計算される。すなわち、ＳＵＭ＝Ｂ＿ｂｉｔｓ＋Ｉ＿ｂｉｔｓ、及び、ＡＤＪ＿ＳＵＭ＝Ｂ＿ｂｉｔｓ＋Ｉ＿ｂｉｔｓ−Ｎである。
【００１６】
最後に、変換されるアドレスに対応するブロック番号が定義されるが、このブロック番号はＳＵＭ又はＡＤＪ＿ＳＵＭの少なくとも一つの値の関数である。好ましい実施例では、選択されたブロック番号は、ＡＤＪ＿ＳＵＭがゼロ未満である場合はＳＵＭの値であり、ＡＤＪ＿ＳＵＭがゼロ以上である場合はＡＤＪ＿ＳＵＭの値である。
【００１７】
本発明の別の実施例は、第１及び第２の入力値の和をとり、且つ０からＮ−１の範囲内で結果を計算するための限定された範囲のモジュロ−Ｎ加算器を提供するものであり、上記において、入力値の実際の和は０から２Ｎ−１の範囲内にある。本発明による限定された範囲のモジュロ−Ｎ加算器は、第１及び第２の入力値の第１の和を計算するための手段と、第１及び第２の入力値の第２の和を計算し、且つＮに対応する第３の入力値を減算するための手段と、第２の和が負であるかどうかを判定し、且つ第１及び第２の和の一つから結果を選択するための手段とから成っている。その場合、第２の和がゼロ未満である場合は第１の和が選択され、第２の和がゼロ以上である場合は第２の和が選択される。
【００１８】
本発明の別の実施例は、コンピュータと、該コンピュータと連結されたＮ個のメモリブロックと、インターリーブされた方式でメモリからデータ値を読出し、且つ／又はメモリへとデータを書き込むためのアドレス手段（以下では、アドレス指定手段）とを備えたディジタルシステムを提供する。アドレス指定手段は、限定された範囲のモジュロ−Ｎ加算器を含む前述の方法を実行するための手段を備えている。
【００１９】
【実施例】
本発明の好ましい実施例は、記憶位置のそれぞれのアドレスを、対応するインターリーブされたブロック・アドレス及び各ブロック内のオフセットへと変換するための方法と、それに対応する装置、及びインターリーブされたメモリブロックを備えたコンピュータシステムを含んでいる。これらの実施例は、以下に図面を参照して説明するが、同一の参照符号は同一の構成要素又はステップを示している。本実施例を概観するため、好ましい方法では、本明細書で“Ｂ＿ｂｉｔｓ”と呼ぶメモリブロックでは使用されない上位アドレスビットを、本明細書で“Ｉ＿ｂｉｔｓ”と呼ぶＩ個の最下位ラインアドレスビットに加算するために、（後述する）限定された範囲のモジュロ−Ｎ加算器を使用することを指摘しておく。この場合、Ｉ及びＢは整数を表し、“Ｂ＿ｂｉｔｓ”及び“Ｉ＿ｂｉｔｓ”は隣接するアドレスビットの特定の群又はサブセットを表す。更に、“ライン”は各メモリアクセスにより転送されるバイト群（キャッシュ準拠システムでは代表的には１６又は３２）を意味する。“ラインアドレス”は特定のライン内の最初のバイトのアドレスである。本発明によれば、Ｂ＿ｂｉｔｓとＩ＿ｂｉｔｓの和（“調整されない和”と呼ぶ）が、Ｂ＿ｂｉｔｓとＩ＿ｂｉｔｓ−Ｎの和と並行して計算される。ここにＮはインターリーブされているブロック数である。幾つかの群のインターリーブされたブロックを許容するため、該群の開始アドレス（ここでは群開始の意味で“ＧＳ”と称する）もＢ＿ｂｉｔｓから減算される。ブロックが群に構成されていない場合は、ＧＳをゼロにセットする。このようにして、Ｂ＿ｂｉｔｓとＩ＿ｂｉｔｓ−（ＧＳ＋Ｎ）の“調整された和”が計算される。これらの和は３入力加算器によって計算でき、そのうちの１入力はシステムの構成中に決定される予め定義された定数である（この予め定義された定数は、それぞれの加算器毎に−ＧＳ及び−（ＧＳ＋Ｎ）である）。３入力加算器の設計と実装は当該技術分野では周知である。
【００２０】
本発明によると、変換されるアドレスに対応する特定のメモリブロックを識別するブロック番号を定義するために、調整された和又は調整されない和のいずれかが用いられる。調整された和又は調整されない和のいずれを用いるかは、調整された和が負であるか、ゼロであるか又は正であるかによる。これらの和は、対応するメモリブロックを選択するためにそのうちのどれを用いるかの選択と同様に、本発明に基づく限定された範囲のモジュロ−Ｎ加算器によって実行される。
【００２１】
次に図１を参照してこの方法を説明する。その後で図２を参照して限定された範囲のモジュロ−Ｎ加算器を説明する。最後に、図３を参照して本発明を組み入れたコンピュータ・システムを説明する。
【００２２】
さて、図１を参照すると、最初の処理、すなわちステップ１０は、パラメータ“Ｓ”、“Ｌ”、“Ｎ”及び“ＧＳ”を定義するステップである。Ｓは特定の群のメモリブロックのサイズをバイトで示すものである。（一の群内では全てのブロックが同じサイズであることが必要である）。Ｌはブロック内のラインのサイズをバイトで示すものである。前述のとおり、Ｎ及びＧＳは、特定の群内のブロック数及び特定の群の開始アドレス番号をそれぞれ示す。
【００２３】
次のステップは、変数“Ａ”、“Ｂ”及び“Ｉ”の値を計算するためのステップ１２である。これらの変数は次のように定義される。
【００２４】
Ａ＝ｌｏｇ２（Ｓ）、
Ｂ＝Ｍ−Ａ、
Ｉ＝ｔｒｕｎｃａｔｅ（ｌｏｇ２（Ｎ））
ここで、“Ｍ”は予め定数として定められた、システムのアドレスバスの幅（すなわちビット数）に等しい。尚、以下では、ｔｒｕｎｃａｔｅ（ｌｏｇ２（Ｎ））は、切り捨て（ｌｏｇ２（Ｎ））と記載。
【００２５】
ステップ１４、１６及び１８は“Ｂ＿ｂｉｔｓ”、“Ａ＿ｂｉｔｓ”及び“Ｉ＿ｂｉｔｓ”をそれぞれ特定することに関連するステップである。“Ｂ＿ｂｉｔｓ”は、変換されるアドレスのＢ個の最上位ビット（ＭＳＢｓ）により定義される。“Ａ＿ｂｉｔｓ”は、アドレスのＡ個の残りの最下位ビット（ＬＳＢｓ）により定義される。又、“Ｉ＿ｂｉｔｓ”はラインアドレスのＩ個の最下位ビットにより定義される。この場合、ラインアドレスは、ライン内の特定のバイトを識別するのに必要なビットを取り除いた後のＡ＿ｂｉｔｓの残りのビットにより定義される。従って、ラインサイズがＬである場合、Ｉ＿ｂｉｔｓは、Ａ＿ｂｉｔｓのｌｏｇ２（Ｌ）個の最下位ビットを取り除いた後のＡ＿ｂｉｔｓの残りのＩ個の最下位ビットにより定義される。
【００２６】
例えば、ラインのサイズが１６バイト（Ｌ＝１６）で１６ビットのアドレスバス（Ｍ＝１６）を有する１０２４バイトのメモリ（Ｓ＝１０２４）の５つのブロック（Ｎ＝５）を考えてみる。更に、群開始アドレス（ＧＳ）がゼロであるものと想定する。メモリブロック内の全ての記憶位置をアドレス指定するのに必要なビット数Ａは、Ａ＝ｌｏｇ２（１０２４）＝１０である。従ってＢは１６−１０＝６であり、Ｉは切り捨て（ｌｏｇ２（５））＝２である。インターリーブビット（Ｉ＿ｂｉｔｓ）はビット１０及び１１であり、ビット０はアドレスの最も左側のビットである。この場合、アドレスは次のように分解される。
【００２７】
【表３】
0003599352.tif 000004
【００２８】
添文字（例えばｋ０、ｋ１、ｋ２等）は特定のアドレス及びビット数を表すことに留意されたい。例えばアドレスのリスト中のｋ番目のアドレスのビット０はｂｋ０として表される。このようにこの例では特定のアドレスに対応するＩ＿ｂｉｔｓ、Ａ＿ｂｉｔｓ及びＢ＿ｂｉｔｓは（添文字ｋを省略して）次のように定義される。
【００２９】
Ｉ＿ｂｉｔｓ＝（ｂ１０、ｂ１１）、
Ａ＿ｂｉｔｓ＝（ｂ６  ，ｂ７  ・・・ｂ１５）、
Ｂ＿ｂｉｔｓ＝（ｂ０  ，ｂ１  ・・・ｂ５  ）。
【００３０】
上記のステップ１０−１８は、システムの構成（始動）中に一度しか実施する必要がないことに留意されたい。次のステップ２０−２４は、各メモリアクセスと共に実行される。
【００３１】
図１に戻ると、次にステップ２０で、調整されない和（“ＳＵＭ”）と調整された和（“ＡＤＪ＿ＳＵＭ”）が好ましくは同時に、（各アクセスごとに）計算される。これらの和は次のように計算される。
【００３２】
ＳＵＭ＝Ｂ＿ｂｉｔｓ＋Ｉ＿ｂｉｔｓ−ＧＳ
ＡＤＪ＿ＳＵＭ＝Ｂ＿ｂｉｔｓ＋Ｉ＿ｂｉｔｓ−（ＧＳ＋Ｎ）。
【００３３】
次にステップ２２で、調整された和（ＡＤＪ＿ＳＵＭ）がゼロ以上である場合は、（ＡＤＪ＿ＳＵＭ）が正しい結果（ＲＥＳＵＬＴ）として選択される。そうではない場合は、調整されない和（ＳＵＭ）が正しい結果として選択される。
【００３４】
最後のステップ、すなわちステップ２４は、変換されるアドレスに対応するブロック番号及びオフセットを定義するステップである。ブロック番号は単にＲＥＳＵＬＴにセットされ、オフセットアドレスはＡ＿ｂｉｔｓによって定義される。
【００３５】
前述の方法のさらなる例として、以下の表は内部アドレス及びそれに対応する変換された外部バスアドレスのリストを示している。ここで、バスアドレスはブロック番号（表では“ｂｌｋ”）とオフセット・アドレス（表では“ｏｆｆｓｅｔ”）から構成されている。この例ではＳ＝３２、Ｎ＝７、Ｉ＝２、Ｍ＝７、Ａ＝４、Ｂ＝３及びＧＳ＝０である。
【００３６】
【表４】
0003599352.tif 000005
【００３７】
【表５】
0003599352.tif 000006
【００３８】
【表６】
0003599352.tif 000007
【００３９】
【表７】
0003599352.tif 000008
【００４０】
前述のように、各“インターリーブ群”が同一サイズのブロックから成っており、群の開始Ｂ＿ｂｉｔｓ値を示す群開始番号（ＧＳ）がＢ＿ｂｉｔｓから減算される場合は、サイズが異なるブロックを使用することができる。バスを経て転送されるブロック番号の結果値には、ＧＳを再度加算することが必要なことがある。ブロック番号は連続している必要がないので、インターリーブ群を特定するためにＢ＿ｂｉｔｓのいくつかのビットを使用できることに留意されたい。
【００４１】
例えば、システムが４つのサイズのＤＲＡＭカードをサポートするものと想定する。更に、ハードウェアがシステム内で１６−ウェイまでのインターリービング（Ｉ＝４であることが必要）と、１６個までのメモリカードを許容するものと想定する。サイズＡの全てのカードに０×０？（ここに“？”は０からｆまでの範囲であり得る）の１６進数のブロック番号を割当て、サイズＢのカードに０×１？のブロック番号を割当て、サイズＣのカードに０×２？のブロック番号を割当て、且つサイズＤのカードに０×３？のブロック番号を割り当てることによって、サイズが異なるメモリ・カードの任意の組み合わせを同時にサポートすることが可能である。構成ソフトウェアがシステム内にそのサイズのカードがいくつあるかに基づいて？の値を決定し、０から群内のカード数の数字までをそれらに順次番号付けをする。次に最大のサイズのカードのアドレス範囲が決定される。次に、そのＧＳ番号がゼロにセットされる。その後、先行する群の終わりから始まる、その次に大きい群に対して同じ動作が実行されて、以下同様に実行される。
【００４２】
さて図２を参照すると、本発明に基づく限定された範囲のモジュロ−Ｎ加算器（好ましくは各群のカード毎に一つ備えてある）は、一対の３入力加算器２０ａ’、２０ｂ’と、０とＮ−１の間にある正しい結果、すなわちＳＵＭ又はＡＤＪ＿ＳＵＭを選択する手段とから成っている。正しい結果を選択するための手段は、それぞれの加算器２０ａ’、２０ｂ’に選択信号“ＳＥＬ１”、“ＳＥＬ２”を供給する論理回路である選択回路４８を備えている。図示するように、ＳＵＭとＡＤＪ＿ＳＵＭの計算は並行して行われる。ＡＤＪ＿ＳＵＭがゼロ未満である場合は、ＳＵＭを選択し、ＡＤＪ＿ＳＵＭがゼロ以上である場合は、ＡＤＪ＿ＳＵＭを選択する選択回路４８によって、図面では“ＮＥＧ”と称する符号ビットが用いられる。群記述ビット（例えばＢ＿ｂｉｔｓの上位２ビット）を決定するため、各群毎に一対の範囲比較器４０、４２を使用することができる。比較器４０、４２の出力は、選択回路４８にイネーブル信号（“ＥＮＡＢＬＥ”）を供給する整合回路４４によって利用される。群番号入力を選択回路４８に供給するため、所定の群番号レジスタ４６も備えることができる。多くの群について、低範囲比較器４２は先行する群の高範囲比較器として先行する群によって共用され、高範囲比較器４０は後続の群の低範囲比較器として後続の群によって共用されることができる。
【００４３】
所与の群用の所定の定数（始動時に決定される）である値−ＧＳ及び−（ＧＳ＋Ｎ）はそれぞれの加算器２０ａ’、２０ｂ’の第３の入力である。更に、アドレスＡ１  ，Ａ２  ・・・Ａｋ  、・・・からなるリスト８は、ブロック番号（“ＢＬＯＣＫ＿ＮＯ”）及びブロック内のオフセットアドレス（“ＯＦＦＳＥＴ”）の対応するリストに変換されることも留意されたい。
【００４４】
さて図３を参照すると、本発明に基づくコンピュータ・システムはブロックメモリ３４Ａ，３４Ｂ・・・３４Ｎと、該ブロックメモリをインターリーブするためのアドレス指定手段３２とを備えている。好ましい実施例では、アドレスＡ１  ，Ａ２  ，Ａ３  ・・・からなる内部リスト８を有するコンピュータ３０は、アドレス指定手段３２を介してメモリブロックもしくはカード３４Ａ〜３４Ｎに結合されている。アドレス指定手段３２及び／又はカード３４Ａ−３４Ｎは別個の装置である必要はなく、コンピュータ３０に統合可能である。アドレス指定手段３２は、それぞれのブロックをインターリーブ方式でアドレス指定するための前述のコードと回路とを備えている。
【００４５】
最後に、本明細書で説明した好ましい実施例は、多くの態様で変更可能であることが当業者には明らかであろう。例えば、図１に示したステップを実行する順序は変更可能であり、前述の方法を実施するための手段（ハードウェアでもソフトウェアでも）は、実際に多様な装置で実現することができ、それも本発明の範囲内にある。更に、Ａ及びＩを計算するために好ましい実施例で用いられる式はｌｏｇ２関数を使用する必要はない。その代わりに、Ｂ＿ｂｉｔｓ、Ｉ＿ｂｉｔｓ及びＡ＿ｂｉｔｓ用に用いられる特定のビットを適当なビット選択論理によってマスクしてもよい。従って、例えばＩ＿ｂｉｔｓ、Ｂ＿ｂｉｔｓ等を３入力加算器へと経路指定するための図２のブロック１４、１６及び１８は多重型論理回路として実施することもできよう。更に、システムが一つのサイズのメモリだけをサポートする場合は、これらの経路を直結することもできよう。従って、本発明の範囲は前述の特定の実施例に限定されるものではない。
【００４６】
【発明の効果】
本発明のフレキシブルなＮ−ウェイ・メモリ・インターリーブ方式は、任意数のメモリブロックでインターリービングを実行するのに極めて実用的であり、該メモリブロックをアドレスバスに接続して各メモリブロックが自己選択できるブロック識別番号を付けることができる。
【図面の簡単な説明】
【図１】本発明に基づく、メモリアドレスを対応するインターリーブされたブロックアドレスに変換する方法の簡略化したフローチャートである。
【図２】本発明に基づく、限定された範囲のモジュロ−Ｎ加算器のブロック図である。
【図３】本発明に基づく、インターリーブされたブロックメモリを組み込んだコンピュータシステムのブロック図である。
【符号の説明】
２０ａ’，２０ｂ’  ３入力加算器
３０    コンピュータ
３２    アドレス指定手段
３４Ａ，３４Ｂ…３４Ｎ  ブロックメモリ
４０，４２  比較器
４４  整合回路
４６    群番号レジスタ
４８    選択回路
【図１】
0003599352.tif 000009
【図２】
0003599352.tif 000010
【図３】
0003599352.tif 000011