JPH04213722A - データの選別及び格納装置 - Google Patents
データの選別及び格納装置Info
- Publication number
- JPH04213722A JPH04213722A JP3017712A JP1771291A JPH04213722A JP H04213722 A JPH04213722 A JP H04213722A JP 3017712 A JP3017712 A JP 3017712A JP 1771291 A JP1771291 A JP 1771291A JP H04213722 A JPH04213722 A JP H04213722A
- Authority
- JP
- Japan
- Prior art keywords
- data
- stack
- register
- mode
- input
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
- G06F7/24—Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in general
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Time-Division Multiplex Systems (AREA)
- Executing Machine-Instructions (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は一般にコンピュータの記
憶装置および格納装置に関する。更に詳細には、本発明
は入力データ語をより小さいまたはより大きい規模の語
の間にデータを等級順に格納するように自動的に挿入す
る自動選別格納装置を目的とする。
憶装置および格納装置に関する。更に詳細には、本発明
は入力データ語をより小さいまたはより大きい規模の語
の間にデータを等級順に格納するように自動的に挿入す
る自動選別格納装置を目的とする。
【０００２】
【従来の技術】コンピュータシステムの多くは「スタッ
ク」または「プッシュダウンスタック」として知られて
いる記憶に専用される区域を備えており、これはデータ
を迅速に格納し且つ取出すのに特に有用である。データ
は一般に簡単な一語文でスタックに書込まれ、スタック
から読出される。たとえば、「ＰＵＳＨ Ａ」はレジ
スタ「Ａ」の内容をスタックにロードする典型的命令で
ある。同様に、「ＰＯＰＡ」はスタックの最上部にある
データ語をレジスタにロードさせる。スタックデータは
一般に、たとえば、単一クロックサイクルで、記憶装置
の他の区域に格納されているデータより速くアクセスす
ることができる。記憶装置の他の区域とは反対に、スタ
ックにデータを格納することの短所は、データをスタッ
クから先入れ先出し（ＦＩＦＯ）でまたは後入れ先出し
（ＬＩＦＯ）でのみ取出すことができるだけであるとい
うことである。この理由は、スタックレジスタの内容が
新しいデータ語がスタックに書込まれるごとに押下げら
れ（すなわち、各データ語がスタック内の次のレジスタ
に移し下げられ）、スタックの下にあるデータは、下か
ら「押し（ＰＵＳＨ）」出されてから（ＦＩＦＯ）また
は最上部に「はじき（ＰＯＰ）」出されてから（ＬＩＦ
Ｏ）アクセスすることができるだけであるからである。
ク」または「プッシュダウンスタック」として知られて
いる記憶に専用される区域を備えており、これはデータ
を迅速に格納し且つ取出すのに特に有用である。データ
は一般に簡単な一語文でスタックに書込まれ、スタック
から読出される。たとえば、「ＰＵＳＨ Ａ」はレジ
スタ「Ａ」の内容をスタックにロードする典型的命令で
ある。同様に、「ＰＯＰＡ」はスタックの最上部にある
データ語をレジスタにロードさせる。スタックデータは
一般に、たとえば、単一クロックサイクルで、記憶装置
の他の区域に格納されているデータより速くアクセスす
ることができる。記憶装置の他の区域とは反対に、スタ
ックにデータを格納することの短所は、データをスタッ
クから先入れ先出し（ＦＩＦＯ）でまたは後入れ先出し
（ＬＩＦＯ）でのみ取出すことができるだけであるとい
うことである。この理由は、スタックレジスタの内容が
新しいデータ語がスタックに書込まれるごとに押下げら
れ（すなわち、各データ語がスタック内の次のレジスタ
に移し下げられ）、スタックの下にあるデータは、下か
ら「押し（ＰＵＳＨ）」出されてから（ＦＩＦＯ）また
は最上部に「はじき（ＰＯＰ）」出されてから（ＬＩＦ
Ｏ）アクセスすることができるだけであるからである。
【０００３】データを選別する装置は既知である。たと
えば米国特許第３，９３１，６１２号、第４，６５１，
３０１号、第４，５７０，２２１号、および第４，５５
９，６１２号を参照。データ語を選別し、たとえば、そ
の大きさに基くような、特定の順序で格納することが望
ましいときがある。従来技術では、スタックに格納すべ
きデータを、スタックにロードする前に等級分けする、
すなわち選別する、かまたはすべてのデータ語をスタッ
クから取出してから選別する。これら選別動作は、選別
すべき語を一時格納するのに必要な余分の記憶装置の点
で、および選別動作を行うのに必要な時間の点で、費用
が高い。この後者の費用は、最初の設置によりスタック
を利用する一つの目標、すなわち、データを格納したり
取出したりすることに関する時間を極力少くするという
ことを無効にするため、特に望ましくない。
えば米国特許第３，９３１，６１２号、第４，６５１，
３０１号、第４，５７０，２２１号、および第４，５５
９，６１２号を参照。データ語を選別し、たとえば、そ
の大きさに基くような、特定の順序で格納することが望
ましいときがある。従来技術では、スタックに格納すべ
きデータを、スタックにロードする前に等級分けする、
すなわち選別する、かまたはすべてのデータ語をスタッ
クから取出してから選別する。これら選別動作は、選別
すべき語を一時格納するのに必要な余分の記憶装置の点
で、および選別動作を行うのに必要な時間の点で、費用
が高い。この後者の費用は、最初の設置によりスタック
を利用する一つの目標、すなわち、データを格納したり
取出したりすることに関する時間を極力少くするという
ことを無効にするため、特に望ましくない。
【０００４】
【発明が解決しようとする課題】したがって、データ語
を自動的に選別し、レジスタのスタック類似系列に等級
順に格納する装置を設けることが望ましい。望ましくは
新しい語がスタックに追加されるにつれてデータを等級
順に自動的に維持する。またデータを等級順に、スタッ
ク、ＲＡＭ、バブル記憶装置、などであろうと何等かの
形式の格納装置に自動的に格納する装置を設けることも
望ましい。本発明はこれらの目的を達成するものである
。
を自動的に選別し、レジスタのスタック類似系列に等級
順に格納する装置を設けることが望ましい。望ましくは
新しい語がスタックに追加されるにつれてデータを等級
順に自動的に維持する。またデータを等級順に、スタッ
ク、ＲＡＭ、バブル記憶装置、などであろうと何等かの
形式の格納装置に自動的に格納する装置を設けることも
望ましい。本発明はこれらの目的を達成するものである
。
【０００５】
【課題を解決するための手段】本発明によれば、入力デ
ータ語をその大きさに従って（「等級順」に）選別し、
格納する装置は、一連のデータ語を格納する、一連のレ
ジスタのような手段、およびレジスタに結合して入力語
を受取り、これらをその大きさに従って等級順にレジス
タにロードする選別手段、から構成されている。
ータ語をその大きさに従って（「等級順」に）選別し、
格納する装置は、一連のデータ語を格納する、一連のレ
ジスタのような手段、およびレジスタに結合して入力語
を受取り、これらをその大きさに従って等級順にレジス
タにロードする選別手段、から構成されている。
【０００６】本発明の一特定実施例では、格納されたデ
ータ語は小さい値を大きい値より前にして順次の記憶装
置に（またはレジスタのスタックを使用する場合には、
レジスタに）保持される。代りに、格納されたデータ語
を大きい値を小さい値より前にして順次記憶装置に保持
する。
ータ語は小さい値を大きい値より前にして順次の記憶装
置に（またはレジスタのスタックを使用する場合には、
レジスタに）保持される。代りに、格納されたデータ語
を大きい値を小さい値より前にして順次記憶装置に保持
する。
【０００７】最も好ましい実施例では、データ語を格納
する手段は一定数（たとえば、８個）のレジスタのスタ
ックから構成されている。最も好ましくは選別手段を、
少くとも一つの格納データ語の大きさを入力データ語の
大きさと比較し、入力データ語が格納データ語より小さ
いか否かを示す出力信号を発生する手段から構成する。 最も好ましい実施例は更に、比較器および選別手段と結
合し、選別手段に制御信号を供給する制御手段、および
制御信号に応じて入力データ語を系列内に等級順に格納
する（複数のマルチプレクサのような）手段を備えてい
る。制御信号の発生は、比較器出力信号および外部で発
生したモード信号によって変る。
する手段は一定数（たとえば、８個）のレジスタのスタ
ックから構成されている。最も好ましくは選別手段を、
少くとも一つの格納データ語の大きさを入力データ語の
大きさと比較し、入力データ語が格納データ語より小さ
いか否かを示す出力信号を発生する手段から構成する。 最も好ましい実施例は更に、比較器および選別手段と結
合し、選別手段に制御信号を供給する制御手段、および
制御信号に応じて入力データ語を系列内に等級順に格納
する（複数のマルチプレクサのような）手段を備えてい
る。制御信号の発生は、比較器出力信号および外部で発
生したモード信号によって変る。
【０００８】
【実施例】本発明は、入力データ語を受取り、入力語を
その大きさに従って等級順に格納する手段を広く備えて
いる。データを格納する手段は好適にはデータレジスタ
から構成されるが、他の形式の格納装置、たとえば、Ｒ
ＡＭ、バブル記憶装置などを備えることもできる。本発
明の基礎を成すのは、データを自動的に選別する手段お
よび方法である。
その大きさに従って等級順に格納する手段を広く備えて
いる。データを格納する手段は好適にはデータレジスタ
から構成されるが、他の形式の格納装置、たとえば、Ｒ
ＡＭ、バブル記憶装置などを備えることもできる。本発
明の基礎を成すのは、データを自動的に選別する手段お
よび方法である。
【０００９】本発明について今度は図面を参照して説明
することにする。図面では類似数字は類似要素を示して
いる。
することにする。図面では類似数字は類似要素を示して
いる。
【００１０】図１を参照すると、本発明による選別装置
の簡略ブロック図を示してある。図１は本発明を幅広く
表現したものに過ぎない。選別装置は、入力データ語を
線１４で受取り、これらの語を複数の格納装置（たとえ
ば、レジスタ）１２ａ，１２ｂ，１２ｃ，１２ｄなどに
出力する選別手段１０を備えている。格納装置の精密な
数はユーザの要求事項によって決まる。選別手段１０は
、格納装置に並列にアクセスすることができるので、入
力データ語を格納されるデータ語の値、または大きさ、
に応じてどんなレジスタにも格納することができる。こ
のような方法で、格納データを等級順に保持する。（こ
こに採用する語句「等級順」は増加順または減少順を指
すことに注意。）格納装置１２ａ，１２ｂ，１２ｃ，１
２ｄなどからの線１６に載っている出力データは、選別
手段１０の精密な実施例によって、増加順が減少順かに
なる。
の簡略ブロック図を示してある。図１は本発明を幅広く
表現したものに過ぎない。選別装置は、入力データ語を
線１４で受取り、これらの語を複数の格納装置（たとえ
ば、レジスタ）１２ａ，１２ｂ，１２ｃ，１２ｄなどに
出力する選別手段１０を備えている。格納装置の精密な
数はユーザの要求事項によって決まる。選別手段１０は
、格納装置に並列にアクセスすることができるので、入
力データ語を格納されるデータ語の値、または大きさ、
に応じてどんなレジスタにも格納することができる。こ
のような方法で、格納データを等級順に保持する。（こ
こに採用する語句「等級順」は増加順または減少順を指
すことに注意。）格納装置１２ａ，１２ｂ，１２ｃ，１
２ｄなどからの線１６に載っている出力データは、選別
手段１０の精密な実施例によって、増加順が減少順かに
なる。
【００１１】本発明を具体化する特定の回路について今
度は説明することにする。以下に説明する好適実施例で
は、データはデータレジスタの「スタック」に増加順に
保持されているが、わずかな明らかな修正を施してデー
タを減少順に保持することができる。データを選別し、
減少順に格納する選別装置はそれ故、本発明の範囲内に
あると考えられる。
度は説明することにする。以下に説明する好適実施例で
は、データはデータレジスタの「スタック」に増加順に
保持されているが、わずかな明らかな修正を施してデー
タを減少順に保持することができる。データを選別し、
減少順に格納する選別装置はそれ故、本発明の範囲内に
あると考えられる。
【００１２】今度は図２乃至図７を参照すると、本発明
の一実施例による図１の自動選別装置の詳細な実施が示
されている。図２乃至図７に示す自動選別スタックは、
複数の１５ビット幅の４対１マルチプレクサ２４，２８
，３２，３６，４０，４４，４８，５２，複数の１５ビ
ットレジスタ１２ａ’，１２ｂ’，１２ｃ’，１２ｄ’
，１２ｅ’，１２ｆ’，１２ｇ’，１２ｈ’，および複
数の１２ビット比較器２６，３０，３４，３８，４２，
４６，および５０、から構成されている。マルチプレク
サ２４，２８，３２，３６，４０，４４，４８，５２は
、制御器１１０（図２乃至図７は示してない）により制
御される。制御器１１０について以下に図１３に関連し
て説明する。本発明をここでは１５ビットデータ語を選
別することについて説明するが、これは単に本発明の一
実施例を示すものであって、本発明はそのように限定さ
れるものではないことを理解すべきである。
の一実施例による図１の自動選別装置の詳細な実施が示
されている。図２乃至図７に示す自動選別スタックは、
複数の１５ビット幅の４対１マルチプレクサ２４，２８
，３２，３６，４０，４４，４８，５２，複数の１５ビ
ットレジスタ１２ａ’，１２ｂ’，１２ｃ’，１２ｄ’
，１２ｅ’，１２ｆ’，１２ｇ’，１２ｈ’，および複
数の１２ビット比較器２６，３０，３４，３８，４２，
４６，および５０、から構成されている。マルチプレク
サ２４，２８，３２，３６，４０，４４，４８，５２は
、制御器１１０（図２乃至図７は示してない）により制
御される。制御器１１０について以下に図１３に関連し
て説明する。本発明をここでは１５ビットデータ語を選
別することについて説明するが、これは単に本発明の一
実施例を示すものであって、本発明はそのように限定さ
れるものではないことを理解すべきである。
【００１３】入力データ語は線１４’で受取られる。各
データ語は１５ビットのディジタル語から成り、バッフ
ァ２０および２２により受取られる。バッファ２０は線
１４’により入力語の１５ビットすべてを受取り、この
語をマルチプレクサ２４，２８，３２などの「Ｄ３」入
力に伝送する。バッファ２２は線１４’により入力語の
１２ビットを受け、これら１２ビットを比較器２６，３
０，３４，３８，４２，４６，５０の「Ｐ」入力に出力
する。各格納レジスタ１２ａ’，１２ｂ’，１２ｃ’，
１２ｄ’，１２ｅ’，１２ｆ’，１２ｇ’，１２ｈ’に
それぞれ関連する一つのマルチプレクサ２４，２８，３
２，３６，４０，４４，４８，５２があり、各マルチプ
レクサに対して４個の入力端子、それぞれ「Ｄ０」、「
Ｄ１」、「Ｄ２」、および「Ｄ３」がある。Ｄ３入力は
新しいデータをバッファ２０から受取る。Ｄ２入力は、
系列の最後のマルチプレクサ５２のものを除き、直下の
レジスタからデータを受取る（たとえば、マルチプレク
サ２４のＤ２はレジスタ１２ｂ’からデータを受取る）
。各マルチプレクサのＤ０入力は、系列の最初のマルチ
プレクサ２４のものを除き、直上のレジスタからデータ
を受取る（たとえば、マルチプレク２８のＤ０はデータ
を１２ａ’から受取る。マルチプレクサ２４のＤ０入力
およびマルチプレクサ５２のＤ２入力は接地されている
。
データ語は１５ビットのディジタル語から成り、バッフ
ァ２０および２２により受取られる。バッファ２０は線
１４’により入力語の１５ビットすべてを受取り、この
語をマルチプレクサ２４，２８，３２などの「Ｄ３」入
力に伝送する。バッファ２２は線１４’により入力語の
１２ビットを受け、これら１２ビットを比較器２６，３
０，３４，３８，４２，４６，５０の「Ｐ」入力に出力
する。各格納レジスタ１２ａ’，１２ｂ’，１２ｃ’，
１２ｄ’，１２ｅ’，１２ｆ’，１２ｇ’，１２ｈ’に
それぞれ関連する一つのマルチプレクサ２４，２８，３
２，３６，４０，４４，４８，５２があり、各マルチプ
レクサに対して４個の入力端子、それぞれ「Ｄ０」、「
Ｄ１」、「Ｄ２」、および「Ｄ３」がある。Ｄ３入力は
新しいデータをバッファ２０から受取る。Ｄ２入力は、
系列の最後のマルチプレクサ５２のものを除き、直下の
レジスタからデータを受取る（たとえば、マルチプレク
サ２４のＤ２はレジスタ１２ｂ’からデータを受取る）
。各マルチプレクサのＤ０入力は、系列の最初のマルチ
プレクサ２４のものを除き、直上のレジスタからデータ
を受取る（たとえば、マルチプレク２８のＤ０はデータ
を１２ａ’から受取る。マルチプレクサ２４のＤ０入力
およびマルチプレクサ５２のＤ２入力は接地されている
。
【００１４】各マルチプレクサ２４，２８，３２などの
基本機能は、その関連レジスタが（ｉ）新しい、すなわ
ち「入力」データを受取るか、（ｉｉ）それの直上また
は直下のレジスタからデータを受取るか、または（ｉｉ
ｉ）不変のままであるか制御する。マルチプレクサを制
御する制御論理は制御器１１０に入っているが、これに
ついては図１３および図１４を参照して以下に説明する
。各マルチプレクサに対する制御線、すなわちマルチプ
レクサ２４に対して６８，７０と示してあり、マルチプ
レクサ２８に対して７２，７４と示してある等々、は制
御器１１０に結合されている。 制御器１１０は制御信号を各マルチプレクサの「Ａ」入
力および「Ｂ」入力に供給する。制御論理については以
下に図１３および図１４を参照して説明する。
基本機能は、その関連レジスタが（ｉ）新しい、すなわ
ち「入力」データを受取るか、（ｉｉ）それの直上また
は直下のレジスタからデータを受取るか、または（ｉｉ
ｉ）不変のままであるか制御する。マルチプレクサを制
御する制御論理は制御器１１０に入っているが、これに
ついては図１３および図１４を参照して以下に説明する
。各マルチプレクサに対する制御線、すなわちマルチプ
レクサ２４に対して６８，７０と示してあり、マルチプ
レクサ２８に対して７２，７４と示してある等々、は制
御器１１０に結合されている。 制御器１１０は制御信号を各マルチプレクサの「Ａ」入
力および「Ｂ」入力に供給する。制御論理については以
下に図１３および図１４を参照して説明する。
【００１５】各比較器２６，３０，３４などは新しいデ
ータをその「Ｐ」入力（または端子）により受取り、そ
の関連レジスタからのデータをその「Ｑ」入力により受
取る。たとえば、比較器２６を参照すると、そのＰ入力
はバッファ２２により線１０２に押上げられ、そのＱ入
力はその関連レジスタ１２ａ’により線１０４に押上げ
られる。各比較器の出力信号、「ＰＬＴＱ」と記してあ
る、はＰの大きさがＱの大きさより小さいとき真であり
、その他の場合は偽である。各比較器のＰＬＴＱ信号は
線５４，５６，５８，６０などにより制御器１１０（図
１３）に入力される。各ＰＬＴＱ信号は、それぞれ「Ｃ
ＭＰＬＴ０」、「ＣＭＰＬＴ１」、「ＣＭＰＬＴ２」な
どと記してある、制御器１１０の異なる入力端子に伝達
される。各比較器はその関連レジスタに格納されている
データ語のビット０を受ける。「ＲＥＱＶＡＬＩＤ」と
記した入力をも備えている。ビット０は、データの「有
効ビット」であり、０のとき、関連レジスタが空である
ことを示す。レジスタにあるデータ語の有効ビットが０
であるとき、または偽であるときは、その関連比較器の
出力信号が強制的に真にされ、これは制御器１１０に入
力するデータの大きさがレジスタの現在の内容より小さ
いことを示す。このような仕方で比較器を設定すること
により、入力データ語の大きさがその有効ビットが偽で
あるデータ語より小さいと規定され、空レジスタを示す
。空レジスタはこのようにしてスタックの下に維持され
る。
ータをその「Ｐ」入力（または端子）により受取り、そ
の関連レジスタからのデータをその「Ｑ」入力により受
取る。たとえば、比較器２６を参照すると、そのＰ入力
はバッファ２２により線１０２に押上げられ、そのＱ入
力はその関連レジスタ１２ａ’により線１０４に押上げ
られる。各比較器の出力信号、「ＰＬＴＱ」と記してあ
る、はＰの大きさがＱの大きさより小さいとき真であり
、その他の場合は偽である。各比較器のＰＬＴＱ信号は
線５４，５６，５８，６０などにより制御器１１０（図
１３）に入力される。各ＰＬＴＱ信号は、それぞれ「Ｃ
ＭＰＬＴ０」、「ＣＭＰＬＴ１」、「ＣＭＰＬＴ２」な
どと記してある、制御器１１０の異なる入力端子に伝達
される。各比較器はその関連レジスタに格納されている
データ語のビット０を受ける。「ＲＥＱＶＡＬＩＤ」と
記した入力をも備えている。ビット０は、データの「有
効ビット」であり、０のとき、関連レジスタが空である
ことを示す。レジスタにあるデータ語の有効ビットが０
であるとき、または偽であるときは、その関連比較器の
出力信号が強制的に真にされ、これは制御器１１０に入
力するデータの大きさがレジスタの現在の内容より小さ
いことを示す。このような仕方で比較器を設定すること
により、入力データ語の大きさがその有効ビットが偽で
あるデータ語より小さいと規定され、空レジスタを示す
。空レジスタはこのようにしてスタックの下に維持され
る。
【００１６】ここに開示する好適実施例では、１５ビッ
トレジスタのデータの１２ビットだけが大きさの比較に
使用される。残りの３ビットの内、一つは前に説明した
「有効ビット」であり、他の二つは、この特定の実施例
では、大きさを指示しないので、選別には使用されない
。
トレジスタのデータの１２ビットだけが大きさの比較に
使用される。残りの３ビットの内、一つは前に説明した
「有効ビット」であり、他の二つは、この特定の実施例
では、大きさを指示しないので、選別には使用されない
。
【００１７】各マルチプレクサ２４，２８，３２などは
また「ＮＺＥＲＯＶＡＬ」を記した入力を備えている。 特定のマルチプレクサのＮＺＥＲＯＶＡＬが偽であると
きは、そのマルチプレクサの関連レジスタにあるデータ
語の「有効ビット」が強制的に偽にされ、関連レジスタ
が空であることを示す。ＮＺＥＲＯＶＡＬ入力はリセッ
ト回路１００により駆動される。作動されると、リセッ
ト回路１００はそれ故レジスタ１２ａ’，１２ｂ’，１
２ｃ’などのビット０をクリアする。
また「ＮＺＥＲＯＶＡＬ」を記した入力を備えている。 特定のマルチプレクサのＮＺＥＲＯＶＡＬが偽であると
きは、そのマルチプレクサの関連レジスタにあるデータ
語の「有効ビット」が強制的に偽にされ、関連レジスタ
が空であることを示す。ＮＺＥＲＯＶＡＬ入力はリセッ
ト回路１００により駆動される。作動されると、リセッ
ト回路１００はそれ故レジスタ１２ａ’，１２ｂ’，１
２ｃ’などのビット０をクリアする。
【００１８】データはレジスタ１２ａ’，１２ｂ’，１
２ｃ’などから線１６’を経由して取出される。１本の
導線として描いてあるが、線１６’は好適には取出され
るデータ語の各ビットについて１本の導線を備えている
。レジスタがアンロードされるにつれて、データ語は系
列の最初のレジスタ、すなわち１２ａ’から取出され、
後続データ語がスタック内で「押上げ」られる。この動
作は制御器１１０の指導のもとでマルチプレクサ２４，
２８，３２などにより自動的に行われる。好適実施例の
動作を完全に認めるには、制御論理を理解しなければな
らない。制御器および制御論理については図１３および
図１４を参照して下に説明する。 しかし、この説明の前に比較器２６，３０，３４，３８
，４２，４６，および５０を実現する好適回路について
非常に手短かに説明することになる。
２ｃ’などから線１６’を経由して取出される。１本の
導線として描いてあるが、線１６’は好適には取出され
るデータ語の各ビットについて１本の導線を備えている
。レジスタがアンロードされるにつれて、データ語は系
列の最初のレジスタ、すなわち１２ａ’から取出され、
後続データ語がスタック内で「押上げ」られる。この動
作は制御器１１０の指導のもとでマルチプレクサ２４，
２８，３２などにより自動的に行われる。好適実施例の
動作を完全に認めるには、制御論理を理解しなければな
らない。制御器および制御論理については図１３および
図１４を参照して下に説明する。 しかし、この説明の前に比較器２６，３０，３４，３８
，４２，４６，および５０を実現する好適回路について
非常に手短かに説明することになる。
【００１９】今度は図８乃至図１２を参照すると、図２
乃至図７の自動選別スタックに使用する好適比較器回路
が描かれている。明瞭のため、図８乃至図１２の回路に
ついて比較器２６を参照して説明することにするが、事
実上は比較器のすべてに同じ回路が採用されている。
乃至図７の自動選別スタックに使用する好適比較器回路
が描かれている。明瞭のため、図８乃至図１２の回路に
ついて比較器２６を参照して説明することにするが、事
実上は比較器のすべてに同じ回路が採用されている。
【００２０】上に説明したように、比較器２６へのＰ、
Ｑ、およびＲＥＧＶＡＬＩＤの各入力はそれぞれ線１０
２，１０４，および１０６を通って供給される。図示し
た回路は組合せ論理回路であってこれにより比較が並列
に行われる。新しいデータ語は先行のどのレジスタの内
容より小さくなければ、デフォルトによりそれが最後の
レジスタに格納されるので、系列の最後のレジスタ、す
なわちレジスタ１２ｈ’、の内容については比較が行わ
れないことに注目。比較器の機能については図２を参照
して上に説明してあり、且つ図８乃至図１２に示す回路
は基本的ディジタル回路手法を採用しているので、回路
が動作する仕方は当業者には明らかである。それ故図３
に関するこれ以上の説明は不要である。
Ｑ、およびＲＥＧＶＡＬＩＤの各入力はそれぞれ線１０
２，１０４，および１０６を通って供給される。図示し
た回路は組合せ論理回路であってこれにより比較が並列
に行われる。新しいデータ語は先行のどのレジスタの内
容より小さくなければ、デフォルトによりそれが最後の
レジスタに格納されるので、系列の最後のレジスタ、す
なわちレジスタ１２ｈ’、の内容については比較が行わ
れないことに注目。比較器の機能については図２を参照
して上に説明してあり、且つ図８乃至図１２に示す回路
は基本的ディジタル回路手法を採用しているので、回路
が動作する仕方は当業者には明らかである。それ故図３
に関するこれ以上の説明は不要である。
【００２１】今度は図１３を参照すると、図２乃至図７
の自動選別スタックに使用する好適制御器１１０のピン
接続の一実施例の図解が描かれている。制御器への入力
、「ＣＭＰＬＴ０」、「ＣＭＰＬＴ１」、「ＣＭＰＬＴ
２」、「ＣＭＰＬＴ３」、「ＣＭＰＬＴ４」、「ＣＭＰ
ＬＴ５」、および「ＣＭＰＬＴ６」と記してある、は比
較器２６，３０，３４，３８，４２，４６，５０により
それぞれ線５４，５６，５８，６０，６２，６４，およ
び６６を通して供給される。「ＭＯＤＥ」と記してある
入力は外部源により線１１２を通して供給される。外部
源は本発明の一部とは考えられない。好適実施例では、
ＭＯＤＥ信号は２ビットから成り、その機能については
図１４を参照して説明することにする。制御器１１０の
出力は「ＭＵＸ０
の自動選別スタックに使用する好適制御器１１０のピン
接続の一実施例の図解が描かれている。制御器への入力
、「ＣＭＰＬＴ０」、「ＣＭＰＬＴ１」、「ＣＭＰＬＴ
２」、「ＣＭＰＬＴ３」、「ＣＭＰＬＴ４」、「ＣＭＰ
ＬＴ５」、および「ＣＭＰＬＴ６」と記してある、は比
較器２６，３０，３４，３８，４２，４６，５０により
それぞれ線５４，５６，５８，６０，６２，６４，およ
び６６を通して供給される。「ＭＯＤＥ」と記してある
入力は外部源により線１１２を通して供給される。外部
源は本発明の一部とは考えられない。好適実施例では、
ＭＯＤＥ信号は２ビットから成り、その機能については
図１４を参照して説明することにする。制御器１１０の
出力は「ＭＵＸ０
〔０〕」、「ＭＵＸ０〔１〕」、「Ｍ
ＵＸ１
ＵＸ１
〔０〕」、「ＭＵＸ１〔１〕」、「ＭＵＸ２〔０
〕」、「ＭＵＸ２〔１〕」、「ＭＵＸ３
〕」、「ＭＵＸ２〔１〕」、「ＭＵＸ３
〔０〕」、「Ｍ
ＵＸ３〔１〕」、「ＭＵＸ４
ＵＸ３〔１〕」、「ＭＵＸ４
〔０〕」、「ＭＵＸ４〔１
〕」、「ＭＵＸ５
〕」、「ＭＵＸ５
〔０〕」、「ＭＵＸ５〔１〕」「ＭＵ
Ｘ６
Ｘ６
〔０〕」、および「ＭＵＸ６〔１〕」と記してある
。これら出力はマルチプレクサのＡおよびＢ入力を駆動
する。たとえばＭＵＸ０
。これら出力はマルチプレクサのＡおよびＢ入力を駆動
する。たとえばＭＵＸ０
〔０〕は線６８を通ってマルチ
プレクサ２４に入力Ａに伝達される。 同様にＭＵＸ０〔１〕は線７０を通してマルチプレクサ
２４の入力Ｂに伝達される。
プレクサ２４に入力Ａに伝達される。 同様にＭＵＸ０〔１〕は線７０を通してマルチプレクサ
２４の入力Ｂに伝達される。
【００２２】制御器は組合せ回路である。所要データ転
送を生ずるクロック信号ＣＬＫ（図２Ａ）を発する前に
データを適正に加えまたは受取り、対応するＭＯＤＥに
適用するのは本発明を使用する外部源の責任である。
送を生ずるクロック信号ＣＬＫ（図２Ａ）を発する前に
データを適正に加えまたは受取り、対応するＭＯＤＥに
適用するのは本発明を使用する外部源の責任である。
【００２３】今度は図１４を参照すると、図１３の制御
器１１０を動作させる流れ図が示されている。ＭＯＤＥ
入力は２ビットから成るので、ユーザが選択できる可能
な動作モードは四つある。ブロック１２０で示したよう
に、入力モードは次のように復号される。すなわちＩＤ
ＬＥ＝０、ＵＮＵＳＥＤ＝１、ＬＯＡＤ＝２、およびＵ
ＮＬＯＡＤ＝３。
器１１０を動作させる流れ図が示されている。ＭＯＤＥ
入力は２ビットから成るので、ユーザが選択できる可能
な動作モードは四つある。ブロック１２０で示したよう
に、入力モードは次のように復号される。すなわちＩＤ
ＬＥ＝０、ＵＮＵＳＥＤ＝１、ＬＯＡＤ＝２、およびＵ
ＮＬＯＡＤ＝３。
【００２４】ＩＤＬＥかＵＮＵＳＥＤかが選択されれば
、マルチプレクサ２４，２８，３２などのそれら関連レ
ジスタ２６，３０，３４などへの出力はＤ１データから
得られる。すなわち各レジスタはそれ自身のデータを受
取ることになり、したがって不変のままである。ＬＯＡ
Ｄが選択されれば、マルチプレクサ２４，２８，３２な
どの、その関連レジスタ２６，３０，３４などへの出力
はＤ３から得られた新しいデータ、Ｄ２から得られたそ
の下のレジスタからのデータ、またはＤ０から得られた
その上のレジスタからのデータである。正確どれになる
かはＣＭＰＬＴ信号によって決まるが、この信号の機能
については下に説明する。ＵＮＬＯＡＤが選択されれば
、各マルチプレクサはその関連レジスタに、Ｄ２から得
られた、その直下のレジスタからのレジスタデータを供
給する。これらの結果を達成するには、ブロック１２２
で示すように、制御語「ＡＢＯＶＥ」、「ＳＡＭＥ」、
「ＢＥＬＯＷ」、および「ＮＥＷＤＡＴＡ」をそれぞれ
値０、１、２、および３で符号化する。
、マルチプレクサ２４，２８，３２などのそれら関連レ
ジスタ２６，３０，３４などへの出力はＤ１データから
得られる。すなわち各レジスタはそれ自身のデータを受
取ることになり、したがって不変のままである。ＬＯＡ
Ｄが選択されれば、マルチプレクサ２４，２８，３２な
どの、その関連レジスタ２６，３０，３４などへの出力
はＤ３から得られた新しいデータ、Ｄ２から得られたそ
の下のレジスタからのデータ、またはＤ０から得られた
その上のレジスタからのデータである。正確どれになる
かはＣＭＰＬＴ信号によって決まるが、この信号の機能
については下に説明する。ＵＮＬＯＡＤが選択されれば
、各マルチプレクサはその関連レジスタに、Ｄ２から得
られた、その直下のレジスタからのレジスタデータを供
給する。これらの結果を達成するには、ブロック１２２
で示すように、制御語「ＡＢＯＶＥ」、「ＳＡＭＥ」、
「ＢＥＬＯＷ」、および「ＮＥＷＤＡＴＡ」をそれぞれ
値０、１、２、および３で符号化する。
【００２５】ＭＯＤＥ＝ＩＤＬＥ、ＵＮＵＳＥＤ。ブロ
ック１２４でＭＯＤＥ＝ＩＤＬＥまたはＵＮＵＳＥＤで
あるか否かの判定を行う。そうであれば、ＭＵＸ０の二
つのビット（すなわち、ＭＵＸ０
ック１２４でＭＯＤＥ＝ＩＤＬＥまたはＵＮＵＳＥＤで
あるか否かの判定を行う。そうであれば、ＭＵＸ０の二
つのビット（すなわち、ＭＵＸ０
〔０〕およびＭＵＸ０
〔１〕、およびＭＵＸ１、ＭＵＸ２、ＭＵＸ３などＭＵ
Ｘ７までの二つのビットをＳＡＭＥ、すなわち「１」に
設定する（ブロック１２６）。上に説明したように、こ
れら出力はマルチプレクサ２４，２８，３２などのＡお
よびＢ端子を駆動する。たとえば、ＭＵＸ０
〔１〕、およびＭＵＸ１、ＭＵＸ２、ＭＵＸ３などＭＵ
Ｘ７までの二つのビットをＳＡＭＥ、すなわち「１」に
設定する（ブロック１２６）。上に説明したように、こ
れら出力はマルチプレクサ２４，２８，３２などのＡお
よびＢ端子を駆動する。たとえば、ＭＵＸ０
〔０〕およ
びＭＵＸ０〔１〕はマルチプレクサ２４の、それぞれ入
力ＡおよびＢを駆動する。ＭＵＸ１
びＭＵＸ０〔１〕はマルチプレクサ２４の、それぞれ入
力ＡおよびＢを駆動する。ＭＵＸ１
〔０〕およびＭＵＸ
１〔１〕はマルチプレクサ２８のそれぞれ入力Ａおよび
Ｂを駆動する。 ＭＵＸ２
１〔１〕はマルチプレクサ２８のそれぞれ入力Ａおよび
Ｂを駆動する。 ＭＵＸ２
〔０〕およびＭＵＸ２〔１〕はマルチプレクサ
３２のそれぞれ入力ＡおよびＢを駆動する。以下同様。
３２のそれぞれ入力ＡおよびＢを駆動する。以下同様。
【００２６】ＭＯＤＥ＝ＬＯＡＤ。選択されたモードが
ＬＯＡＤであれば、新しいデータが比較器２６，３０，
３４，３８，４２，４６，および５０の各種出力に応じ
てスタックの記憶場所に挿入される。最初に、制御器１
１０のＣＭＰＬＴ０入力を試験して「１」（すなわち真
）であるか判定する。真であれば、これは入力データの
大きさが最初のレジスタ１２ａ’に格納されているデー
タ語の大きさより小さいことを示す。この場合には、ブ
ロック１３０で示すように、ＭＵＸ０の二つのビットが
ＮＥＷＤＡＴＡ（すなわち「３」）に設定され、残りの
出力（ＭＵＸ１、ＭＵＸ２、ＭＵＸ３、ＭＵＸ４、ＭＵ
Ｘ５、ＭＵＸ６、およびＭＵＸ７）がＡＢＯＶＥ（すな
わち「１」）に設定される。これはマルチプレクサ２４
にレジスタ１２ａ’が入力データ語を受取ること、マル
チプレクサ２８，３２，３６，４０，４４，４８，およ
び５２にそのそれぞれのレジスタ（１２ｂ’から１２ｈ
’まで）が直前のレジスタからのデータを受取ること、
を示す。このようにして、スタック内の各データ語がス
タック内で１レジスタだけ押し下げられ、新しいデータ
が最初のレジスタに挿入される。
ＬＯＡＤであれば、新しいデータが比較器２６，３０，
３４，３８，４２，４６，および５０の各種出力に応じ
てスタックの記憶場所に挿入される。最初に、制御器１
１０のＣＭＰＬＴ０入力を試験して「１」（すなわち真
）であるか判定する。真であれば、これは入力データの
大きさが最初のレジスタ１２ａ’に格納されているデー
タ語の大きさより小さいことを示す。この場合には、ブ
ロック１３０で示すように、ＭＵＸ０の二つのビットが
ＮＥＷＤＡＴＡ（すなわち「３」）に設定され、残りの
出力（ＭＵＸ１、ＭＵＸ２、ＭＵＸ３、ＭＵＸ４、ＭＵ
Ｘ５、ＭＵＸ６、およびＭＵＸ７）がＡＢＯＶＥ（すな
わち「１」）に設定される。これはマルチプレクサ２４
にレジスタ１２ａ’が入力データ語を受取ること、マル
チプレクサ２８，３２，３６，４０，４４，４８，およ
び５２にそのそれぞれのレジスタ（１２ｂ’から１２ｈ
’まで）が直前のレジスタからのデータを受取ること、
を示す。このようにして、スタック内の各データ語がス
タック内で１レジスタだけ押し下げられ、新しいデータ
が最初のレジスタに挿入される。
【００２７】ＣＭＰＬＴ０が真でなければ、ＣＭＰＬＴ
１が真であるか否かに関する判定が行われる。ＣＭＰＬ
Ｔ１が真であることは入力データの大きさが第２のレジ
スタ１２ｂ’のデータの大きさより小さいがレジスタ１
２ａ’のデータの大きさより大きいか等しいことを示す
。ＣＭＰＬＴ１が真であれば、ＭＵＸ０の二つのビット
がＳＡＭＥに等しく設定され、ＭＵＸ１の二つのビット
がＮＥＷＤＡＴＡに等しく設定され、残りの出力がＡＢ
ＯＶＥに設定され、これによりマルチプレクサに入力デ
ータ語をレジスタ１２ｂ’に挿入させると共にレジスタ
１２ａ’の内容を不変のままとし、レジスタ１２ｂ’か
ら１２ｈ’までの内容をスタック内で押し下げる。
１が真であるか否かに関する判定が行われる。ＣＭＰＬ
Ｔ１が真であることは入力データの大きさが第２のレジ
スタ１２ｂ’のデータの大きさより小さいがレジスタ１
２ａ’のデータの大きさより大きいか等しいことを示す
。ＣＭＰＬＴ１が真であれば、ＭＵＸ０の二つのビット
がＳＡＭＥに等しく設定され、ＭＵＸ１の二つのビット
がＮＥＷＤＡＴＡに等しく設定され、残りの出力がＡＢ
ＯＶＥに設定され、これによりマルチプレクサに入力デ
ータ語をレジスタ１２ｂ’に挿入させると共にレジスタ
１２ａ’の内容を不変のままとし、レジスタ１２ｂ’か
ら１２ｈ’までの内容をスタック内で押し下げる。
【００２８】ＣＭＰＬＴ１が真でなければ、同様なステ
ップを実行してスタックのどこに入力データを設置すべ
きかを判定する。制御器１１０の入力がいずれも（すな
わち、ＣＭＰＬＴ０〜ＣＭＰＬＴ６）真でなければ、デ
フォルトにより入力データは系列内の最後のレジスタ、
レジスタ１２ｈ’、に送られる。これはブロック１３６
でＭＵＸ０からＭＵＸ６までがすべてＳＡＭＥに設定さ
れ、ＭＵＸ７がＮＥＷＤＡＴＡに設定される場合を示す
。
ップを実行してスタックのどこに入力データを設置すべ
きかを判定する。制御器１１０の入力がいずれも（すな
わち、ＣＭＰＬＴ０〜ＣＭＰＬＴ６）真でなければ、デ
フォルトにより入力データは系列内の最後のレジスタ、
レジスタ１２ｈ’、に送られる。これはブロック１３６
でＭＵＸ０からＭＵＸ６までがすべてＳＡＭＥに設定さ
れ、ＭＵＸ７がＮＥＷＤＡＴＡに設定される場合を示す
。
【００２９】ＭＯＤＥ＝ＵＮＬＯＡＤ。最後に、ＵＮＬ
ＯＡＤ手順をブロック１３８で示す。ＵＮＬＯＡＤ動作
については、レジスタ１２ａ’にあるデータ語を取出し
、後続レジスタ全部（１２ｂ’〜１２ｈ’）の内容を系
列内の直前レジスタまで押し上げる。データがスタック
内で押上げられるにつれて、有効データを所持する系列
内の最後のレジスタがその有効ビットを自動的に設定し
て空レジスタを示す。このようにして、データ語が順次
アンロードされるにつれて、これらレジスタは空と示さ
れ、スタックの使用の間でのリセットを不要にする。
ＯＡＤ手順をブロック１３８で示す。ＵＮＬＯＡＤ動作
については、レジスタ１２ａ’にあるデータ語を取出し
、後続レジスタ全部（１２ｂ’〜１２ｈ’）の内容を系
列内の直前レジスタまで押し上げる。データがスタック
内で押上げられるにつれて、有効データを所持する系列
内の最後のレジスタがその有効ビットを自動的に設定し
て空レジスタを示す。このようにして、データ語が順次
アンロードされるにつれて、これらレジスタは空と示さ
れ、スタックの使用の間でのリセットを不要にする。
【００３０】先に記したように、制御器１１０は組合せ
回路である。下記は制御器１１０の好適実施例を記述し
、図１４の流れ図に対応する論理方程式である。
回路である。下記は制御器１１０の好適実施例を記述し
、図１４の流れ図に対応する論理方程式である。
【００３１】
論理方程式ＭＵＸ０［０］ ＝ ／ＭＯＤＥ［０］ ＋／ＭＯＤＥ［１］； ＭＵＸ０［１］ ＝ ＭＯＤＥ［１］ ＊ ＣＭＰＬＴ０ ＋ＭＯＤ
Ｅ［１］ ＊ ＭＯＤＥ［０］；ＭＵＸ１［０］ ＝ ／ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＋／ＭＯ
ＤＥ［１］； ＭＵＸ１［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ＣＭ
ＰＬＴ１ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤＥ［０］；
ＭＵＸ２［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＋／ＭＯＤＥ［１］； ＭＵＸ２［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ＣＭＰＬＴ２ ＋ ＭＯＤＥ［１］
＊ ＭＯＤＥ［０］；ＭＵＸ３［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＋／ＭＯＤＥ［１］
； ＭＵＸ３［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ＣＭＰＬＴ３
＋ ＭＯＤＥ［１］ ＊ ＭＯＤＥ［０］；ＭＵＸ４［
０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＋／ＭＯＤＥ［１］； ＭＵＸ４［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ＣＭＰＬＴ４ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤ
Ｅ［０］；ＭＵＸ５［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＋／ＭＯＤＥ［１］； ＭＵＸ５［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＊ ＣＭＰＬＴ５ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤＥ［０］；ＭＵＸ６
［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５ ＋／ＭＯＤＥ［１］； ＭＵＸ６［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５
＊ ＣＭＰＬＴ６ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤ
Ｅ［０］；ＭＵＸ７［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５
＊ ／ＣＭＰＬＴ６ ＋／ＭＯＤＥ［１］； ＭＵＸ７［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５
＊ ／ＣＭＰＬＴ６ ＋ ＭＯＤＥ［１］ ＊ ＭＯ
ＤＥ［０］； 今正に説明した自動選別スタックの動作は次のように要
約することができる。スタックの八つのレジスタがクリ
アされ、そのそれぞれのエントリが有効でないことを示
す。新しいデータ語をスタックにロードしようとすると
きは、これを８個のレジスタの各々の内容と同時に比較
する。最後の語が無効であれば、データを最初のレジス
タに挿入する。最初の語が有効であれば、それが入力デ
ータより小さいかに関する判定が行われる。小さければ
、スタック内の現存データを１レジスタ押下げ、新しい
データを最初のレジスタに挿入する。新しいデータが最
初のレジスタにあるデータより小さくなければ、８個の
レジスタすべてを通じて、新しいデータを同じ手順およ
び結果を用いて第２のレジスタにあるデータと比較し、
以下同様。新しいデータ語はそれ故より小さい大きさの
データの後に挿入されるだけである。比較はすべて１ク
ロックサイクルで行われる。
論理方程式ＭＵＸ０［０］ ＝ ／ＭＯＤＥ［０］ ＋／ＭＯＤＥ［１］； ＭＵＸ０［１］ ＝ ＭＯＤＥ［１］ ＊ ＣＭＰＬＴ０ ＋ＭＯＤ
Ｅ［１］ ＊ ＭＯＤＥ［０］；ＭＵＸ１［０］ ＝ ／ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＋／ＭＯ
ＤＥ［１］； ＭＵＸ１［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ＣＭ
ＰＬＴ１ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤＥ［０］；
ＭＵＸ２［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＋／ＭＯＤＥ［１］； ＭＵＸ２［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ＣＭＰＬＴ２ ＋ ＭＯＤＥ［１］
＊ ＭＯＤＥ［０］；ＭＵＸ３［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＋／ＭＯＤＥ［１］
； ＭＵＸ３［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ＣＭＰＬＴ３
＋ ＭＯＤＥ［１］ ＊ ＭＯＤＥ［０］；ＭＵＸ４［
０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＋／ＭＯＤＥ［１］； ＭＵＸ４［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ＣＭＰＬＴ４ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤ
Ｅ［０］；ＭＵＸ５［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＋／ＭＯＤＥ［１］； ＭＵＸ５［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＊ ＣＭＰＬＴ５ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤＥ［０］；ＭＵＸ６
［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５ ＋／ＭＯＤＥ［１］； ＭＵＸ６［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５
＊ ＣＭＰＬＴ６ ＋ ＭＯＤＥ［１］ ＊ ＭＯＤ
Ｅ［０］；ＭＵＸ７［０］ ＝ ＭＯＤＥ［０］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ／ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５
＊ ／ＣＭＰＬＴ６ ＋／ＭＯＤＥ［１］； ＭＵＸ７［１］ ＝ ＭＯＤＥ［１］ ＊ ／ＣＭＰＬＴ０ ＊ ／Ｃ
ＭＰＬＴ１ ＊ ／ＣＭＰＬＴ２ ＊ ／ＣＭＰＬＴ３
＊ ＣＭＰＬＴ４ ＊ ／ＣＭＰＬＴ５
＊ ／ＣＭＰＬＴ６ ＋ ＭＯＤＥ［１］ ＊ ＭＯ
ＤＥ［０］； 今正に説明した自動選別スタックの動作は次のように要
約することができる。スタックの八つのレジスタがクリ
アされ、そのそれぞれのエントリが有効でないことを示
す。新しいデータ語をスタックにロードしようとすると
きは、これを８個のレジスタの各々の内容と同時に比較
する。最後の語が無効であれば、データを最初のレジス
タに挿入する。最初の語が有効であれば、それが入力デ
ータより小さいかに関する判定が行われる。小さければ
、スタック内の現存データを１レジスタ押下げ、新しい
データを最初のレジスタに挿入する。新しいデータが最
初のレジスタにあるデータより小さくなければ、８個の
レジスタすべてを通じて、新しいデータを同じ手順およ
び結果を用いて第２のレジスタにあるデータと比較し、
以下同様。新しいデータ語はそれ故より小さい大きさの
データの後に挿入されるだけである。比較はすべて１ク
ロックサイクルで行われる。
【００３２】好適実施例は、複数のマルチプレクサ、レ
ジスタ、および関連する比較器、およびマルチプレクサ
を制御する一つの制御器を用いて実施される。すべての
要素は既知の集積回路技術を用いて単一装置に集積する
ことができる。
ジスタ、および関連する比較器、およびマルチプレクサ
を制御する一つの制御器を用いて実施される。すべての
要素は既知の集積回路技術を用いて単一装置に集積する
ことができる。
【００３３】
【発明の効果】以上のように本発明によれば、入力デー
タ語をより小さいまたはより大きい規模の語の間にデー
タを等級順に格納するように自動的に挿入する自動選別
格納装置が提供される。
タ語をより小さいまたはより大きい規模の語の間にデー
タを等級順に格納するように自動的に挿入する自動選別
格納装置が提供される。
【００３４】本発明はその精神または不可欠の属性から
逸脱することなくどんな特定のシステムにも具体化する
ことができる。したがって、前述の明細書ではなく、本
発明の精神および範囲を示す特許請求の範囲を参照すべ
きである。
逸脱することなくどんな特定のシステムにも具体化する
ことができる。したがって、前述の明細書ではなく、本
発明の精神および範囲を示す特許請求の範囲を参照すべ
きである。
【図１】本発明に基づく自動選別記憶装置の簡単なブロ
ック図である。
ック図である。
【図２】本発明を組み込んだ自動選別スタックの概略的
なダイヤグラムである。
なダイヤグラムである。
【図３】本発明を組み込んだ自動選別スタックの概略的
なダイヤグラムである。
なダイヤグラムである。
【図４】本発明を組み込んだ自動選別スタックの概略的
なダイヤグラムである。
なダイヤグラムである。
【図５】本発明を組み込んだ自動選別スタックの概略的
なダイヤグラムである。
なダイヤグラムである。
【図６】本発明を組み込んだ自動選別スタックの概略的
なダイヤグラムである。
なダイヤグラムである。
【図７】本発明を組み込んだ自動選別スタックの概略的
なダイヤグラムである。
なダイヤグラムである。
【図８】図２乃至図８の自動選別スタックで用いられる
好適な比較器回路の概略的なダイヤグラムである。
好適な比較器回路の概略的なダイヤグラムである。
【図９】図２乃至図７の自動選別スタックで用いられる
好適な比較器回路の概略的なダイヤグラムである。
好適な比較器回路の概略的なダイヤグラムである。
【図１０】図２乃至図７の自動選別スタックで用いられ
る好適な比較器回路の概略的なダイヤグラムである。
る好適な比較器回路の概略的なダイヤグラムである。
【図１１】図２乃至図７の自動選別スタックで用いられ
る好適な比較器回路の概略的なダイヤグラムである。
る好適な比較器回路の概略的なダイヤグラムである。
【図１２】図２乃至図７の自動選別スタックで用いられ
る好適な比較器回路の概略的なダイヤグラムである。
る好適な比較器回路の概略的なダイヤグラムである。
【図１３】図２乃至図７の自動選別スタックで用いられ
る好適な制御器のピン接続の１つの実施例を示したダイ
ヤグラムである。
る好適な制御器のピン接続の１つの実施例を示したダイ
ヤグラムである。
【図１４】図１３の制御器の好適な動作を示す流れ図で
ある。
ある。
１０…選別手段
１２…格納手段
１１０…制御器
Claims (1)
- 【請求項１】大きさに従って入力データ語を選別して格
納するための装置であって： （ａ） 一連のデータ語を格納するためのレジスタ手段
と；（ｂ） 動作可能に前記レジスタ手段に結合されて
、前記入力データ語を受け取り、前記入力データ語を大
きさに従って等級順に前記レジスタ手段に格納するため
の選別手段と；から成ることを特徴とする装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/478,126 US5222243A (en) | 1990-02-09 | 1990-02-09 | Sorting apparatus having plurality of registers with associated multiplexers and comparators for concurrently sorting and storing incoming data according to magnitude |
| US478126 | 1990-02-09 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04213722A true JPH04213722A (ja) | 1992-08-04 |
Family
ID=23898635
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3017712A Pending JPH04213722A (ja) | 1990-02-09 | 1991-02-08 | データの選別及び格納装置 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5222243A (ja) |
| EP (1) | EP0441533A3 (ja) |
| JP (1) | JPH04213722A (ja) |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5303381A (en) * | 1990-07-19 | 1994-04-12 | Canon Kabushiki Kaisha | Method and apparatus for sorting sequential input signals by concurrently comparing successive input signals among signals in first and second memory sections |
| US5410719A (en) * | 1992-05-27 | 1995-04-25 | Hewlett-Packard Company | Field compositor for merging data and including cells each receiving three control and two data inputs and generating one control and one data output therefrom |
| GB2287557A (en) * | 1994-03-17 | 1995-09-20 | Michael Colin Parsons | Sorting/ranking data elements |
| US7177319B2 (en) * | 2001-12-27 | 2007-02-13 | Interdigital Technology Corporation | Insertion sorter |
| US20040254931A1 (en) * | 2003-05-29 | 2004-12-16 | Marconi Communications, Inc. | Multiple key self-sorting table |
| US20070233868A1 (en) * | 2006-03-31 | 2007-10-04 | Tyrrell John C | System and method for intelligent provisioning of storage across a plurality of storage systems |
| US12210371B2 (en) * | 2023-02-22 | 2025-01-28 | L3Harris Technologies, Inc. | Single-clock insertion sort scheme |
Family Cites Families (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3931612A (en) * | 1974-05-10 | 1976-01-06 | Triad Systems Corporation | Sort apparatus and data processing system |
| NL8006163A (nl) * | 1980-11-12 | 1982-06-01 | Philips Nv | Inrichting voor het sorteren van datawoorden volgens de waarden van telkens daarbij behorende attribuutgetallen. |
| US4628483A (en) * | 1982-06-03 | 1986-12-09 | Nelson Raymond J | One level sorting network |
| NL8203844A (nl) * | 1982-10-04 | 1984-05-01 | Philips Nv | Geintegreerde, als bouwsteen uitgevoerde sorteerinrichting voor datawoorden en geintegreerde, dataverwerkende, processor voorzien van zo een meegeintegreerde sorteerinrichting. |
| US4567572A (en) * | 1983-02-22 | 1986-01-28 | The United States Of America As Represented By The Director Of The National Security Agency | Fast parallel sorting processor |
| JPS59229643A (ja) * | 1983-06-13 | 1984-12-24 | Fujitsu Ltd | ソ−ト演算回路 |
| DE3322706A1 (de) * | 1983-06-24 | 1985-01-10 | Fa. Carl Zeiss, 7920 Heidenheim | Schaltungsanordnung zur schnellen rangordnungsauswahl oder -sortierung |
| US4833655A (en) * | 1985-06-28 | 1989-05-23 | Wang Laboratories, Inc. | FIFO memory with decreased fall-through delay |
| EP0271626B1 (en) * | 1986-12-16 | 1992-03-04 | International Business Machines Corporation | Bypass mechanism for daisy chain connected units |
| US5068822A (en) * | 1988-03-16 | 1991-11-26 | Digital Equipment Corporation | Single-stage extensible sorter for sorting data and efficiently reading out sorted data, incorporating single-bit devices |
| US4991134A (en) * | 1988-03-30 | 1991-02-05 | International Business Machines Corporation | Concurrent sorting apparatus and method using FIFO stacks |
| US4958141A (en) * | 1988-07-15 | 1990-09-18 | Hughes Aircraft Company | Real time rank ordering logic circuit |
-
1990
- 1990-02-09 US US07/478,126 patent/US5222243A/en not_active Expired - Fee Related
-
1991
- 1991-01-31 EP EP19910300775 patent/EP0441533A3/en not_active Withdrawn
- 1991-02-08 JP JP3017712A patent/JPH04213722A/ja active Pending
Also Published As
| Publication number | Publication date |
|---|---|
| EP0441533A3 (en) | 1993-01-07 |
| US5222243A (en) | 1993-06-22 |
| EP0441533A2 (en) | 1991-08-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0054588B1 (en) | Interactive data retrieval apparatus | |
| JPH0330898B2 (ja) | ||
| GB1563482A (en) | Multipass sorter for arranging an input list into numerical order | |
| US5469398A (en) | Selectable width, brustable FIFO | |
| EP0234038A2 (en) | Apparatus for identifying the LRU storage unit in a memory | |
| JPH026765A (ja) | 自動回路テスタ制御システム | |
| US3740728A (en) | Input/output controller | |
| JPH01283625A (ja) | データを分類するための固定布線回路 | |
| US4706079A (en) | Raster scan digital display system with digital comparator means | |
| US5222243A (en) | Sorting apparatus having plurality of registers with associated multiplexers and comparators for concurrently sorting and storing incoming data according to magnitude | |
| EP0589662A2 (en) | Digital signal processing system | |
| GB2244158A (en) | Cache memory with write buffer | |
| US5033066A (en) | Event tagging time delay | |
| US4528648A (en) | Memory management system | |
| Royals et al. | On the design and implementation of a lossless data compression and decompression chip | |
| US4837748A (en) | Counting RAM | |
| EP0205122A2 (en) | Event counting prescaler | |
| EP0227348A2 (en) | Content addressable memory circuit and method | |
| US5161217A (en) | Buffered address stack register with parallel input registers and overflow protection | |
| US4914620A (en) | Capacity extensible data storage for use in electronic apparatus | |
| JPH0520350A (ja) | ベクトル処理装置 | |
| JPH07141290A (ja) | バッファ回路 | |
| AU606617B2 (en) | Buffer address register | |
| JP3087488B2 (ja) | データ復元回路 | |
| JPS5914193A (ja) | メモリ回路 |