JPS627578B2 - - Google Patents
Info
- Publication number
- JPS627578B2 JPS627578B2 JP1274780A JP1274780A JPS627578B2 JP S627578 B2 JPS627578 B2 JP S627578B2 JP 1274780 A JP1274780 A JP 1274780A JP 1274780 A JP1274780 A JP 1274780A JP S627578 B2 JPS627578 B2 JP S627578B2
- Authority
- JP
- Japan
- Prior art keywords
- classification
- cell
- cells
- input
- numerical values
- 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.)
- Expired
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
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/22—Indexing scheme relating to groups G06F7/22 - G06F7/36
- G06F2207/228—Sorting or merging network
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)
- Image Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Description
【発明の詳細な説明】
本発明は複数個の数値を値の大きさの順に並べ
替えて出力する並列分類処理装置に関するもので
ある。
替えて出力する並列分類処理装置に関するもので
ある。
大量の情報を分類処理することは、デイジタル
コンピユータの最も得意とし、取分けフアイル操
作等には欠かせない重要な処理の一つである。な
かでも、複数個の数値を大きさの順（大きい順ま
たは小さい順）に並べ替える操作は、最も単純で
基本的な分類処理の一例であり、簡単な数値比較
を繰返すことによつて実施される。
コンピユータの最も得意とし、取分けフアイル操
作等には欠かせない重要な処理の一つである。な
かでも、複数個の数値を大きさの順（大きい順ま
たは小さい順）に並べ替える操作は、最も単純で
基本的な分類処理の一例であり、簡単な数値比較
を繰返すことによつて実施される。
ここで問題とされるのは、分類処理に費される
時間である。特に分類処理すべき情報が多量であ
る場合、上述の如き単純な繰返し操作が適用され
れば、データ量に比例した膨大な処理時間を要す
こととなる。このため種々に工夫された分類アル
ゴリズムを適用することによつて処理時間の短縮
が図られている。
時間である。特に分類処理すべき情報が多量であ
る場合、上述の如き単純な繰返し操作が適用され
れば、データ量に比例した膨大な処理時間を要す
こととなる。このため種々に工夫された分類アル
ゴリズムを適用することによつて処理時間の短縮
が図られている。
さらに斯かる問題を解決する方法の一例とし
て、富永、平山による「フアイルメモリーにおけ
るコンテントアドレスの一手法」電子通信学会電
子計算機研究会資料1972年１月21日資料番号
EC71−61（1972−01）（以下資料１とする）に並
列分類処理の方法が提案されている。この方法に
よれば、二つの二進数値をビツト毎に比較し大小
の順位を判定し出力する分類回路を基本のセルと
し、これらの分類セルを配列状に並べ、相互に規
則的な組合せにより結合して並列分類処理装置を
構成し、処理の高速化を達成している。この場合
には、装置を構成する個々の分類セルの構造が簡
単であることが利点とされるが、多量の情報を同
時に分類処理するためにはデータ量に応じた個数
の分類セルを設置する必要があり、装置が大型化
するとともに処理時間が増大することが最大の欠
点である。
て、富永、平山による「フアイルメモリーにおけ
るコンテントアドレスの一手法」電子通信学会電
子計算機研究会資料1972年１月21日資料番号
EC71−61（1972−01）（以下資料１とする）に並
列分類処理の方法が提案されている。この方法に
よれば、二つの二進数値をビツト毎に比較し大小
の順位を判定し出力する分類回路を基本のセルと
し、これらの分類セルを配列状に並べ、相互に規
則的な組合せにより結合して並列分類処理装置を
構成し、処理の高速化を達成している。この場合
には、装置を構成する個々の分類セルの構造が簡
単であることが利点とされるが、多量の情報を同
時に分類処理するためにはデータ量に応じた個数
の分類セルを設置する必要があり、装置が大型化
するとともに処理時間が増大することが最大の欠
点である。
一方、集積化技術の進歩によりLSI等のチツプ
上に複雑大規模な回路を収容することが可能とな
つた。この事実と、上記並列分類処理装置の構成
法とを合せて考えれば、基本セルの機能を適度に
増すことが、装置構成を簡単にする手段と成り得
るが処理時間の増大は避けることが出来ない。
上に複雑大規模な回路を収容することが可能とな
つた。この事実と、上記並列分類処理装置の構成
法とを合せて考えれば、基本セルの機能を適度に
増すことが、装置構成を簡単にする手段と成り得
るが処理時間の増大は避けることが出来ない。
本発明の目的は、上記事情に鑑み、より少ない
基本セルで構成され、回路量を軽減すると共に高
速な分類処理が可能な並列分類処理装置を提供す
ることにある。
基本セルで構成され、回路量を軽減すると共に高
速な分類処理が可能な並列分類処理装置を提供す
ることにある。
本発明によれば、二つの数値を入力し、大きさ
の順に並べ替えて出力する第一の分類セルと、大
きさの順に並べられた二つの数値が二組から成る
四つの数値を入力し、大きさの順に並べ替えて出
力する第二の分類セルとをそれぞれ複数個備え、
前記第一の分類セルは第一列目に、また前記第二
の分類セルは第二列目以後の複数の列に配列状に
並べられ、かつ前記第二列目以後の分類セルのそ
れぞれへは、予め決められた規則に従つて、前列
の分類セルのうち相隣り合うものからそれぞれ二
つずつの出力信号が供給されるように、前記二種
類の分類セルが規則的に相互結合されて構成さ
れ、入力される複数個の数値が並列的に分類処理
を施され、大きさの順に並べ替えられて出力され
る並列分類処理装置が得られる。
の順に並べ替えて出力する第一の分類セルと、大
きさの順に並べられた二つの数値が二組から成る
四つの数値を入力し、大きさの順に並べ替えて出
力する第二の分類セルとをそれぞれ複数個備え、
前記第一の分類セルは第一列目に、また前記第二
の分類セルは第二列目以後の複数の列に配列状に
並べられ、かつ前記第二列目以後の分類セルのそ
れぞれへは、予め決められた規則に従つて、前列
の分類セルのうち相隣り合うものからそれぞれ二
つずつの出力信号が供給されるように、前記二種
類の分類セルが規則的に相互結合されて構成さ
れ、入力される複数個の数値が並列的に分類処理
を施され、大きさの順に並べ替えられて出力され
る並列分類処理装置が得られる。
次に図面を参照して本発明を詳細に説明する。
第１図は本発明の一実施例を示すブロツク図で
あり、一例として、12個の数値の並列分類処理を
行なう装置の構成を示すものである。１１，１２
……，１６は第一の分類セルであり、それぞれ二
本ずつの入出力信号線を有する。２１，２２，…
…，２15は第二の分類セルであり、それぞれ四本
ずつの入出力信号線を有する。１００１，１００
２，……，１００12は本装置の外部入力信号線で
あり、12個の分類すべき数値が並列に供給され
る。２００１，２００２，……，２００12は本装
置の外部出力信号線であり、前記12個の数値が大
きさの順の並べ替えられて並列に出力される。ま
た外部入力信号線１００１，１００２は分類セル
１１の入力信号線、外部入力信号線１００３，１
００４は分類セル１２の入力信号線、同様に外部
入力信号線１００11，１００12は分類セル１６の
入力信号線でもある。１０１１，１０１２は分類
セル１１の出力信号線、１０１３，１０１４は分
類セル１２の出力信号線であり、これらは共に分
類セル２１の入力信号線でもある。２０１１，２
０１２，２０１３，２０１４は分類セル２１の出
力信号線であり、また出力信号線２０１１，２０
１２は分類セル２６の一部の入力信号線、出力信
号線２０１３，２０１４は分類セル２４の一部の
入力信号線でもある。２０１５，２０１６，２０
２１，２０２２等も各分類セルの出力信号線であ
り、次列の分類セルの入力信号線でもある。外部
出力信号線２００１，２００２，……，２００12
は最終列にある分類セルの出力信号線でもあり、
例えば外部出力信号線２００１，２００２は分類
セル２11の一部の出力信号線、外部出力信号線２
００３，２００４は分類セル２14の一部出力信号
線等である。
あり、一例として、12個の数値の並列分類処理を
行なう装置の構成を示すものである。１１，１２
……，１６は第一の分類セルであり、それぞれ二
本ずつの入出力信号線を有する。２１，２２，…
…，２15は第二の分類セルであり、それぞれ四本
ずつの入出力信号線を有する。１００１，１００
２，……，１００12は本装置の外部入力信号線で
あり、12個の分類すべき数値が並列に供給され
る。２００１，２００２，……，２００12は本装
置の外部出力信号線であり、前記12個の数値が大
きさの順の並べ替えられて並列に出力される。ま
た外部入力信号線１００１，１００２は分類セル
１１の入力信号線、外部入力信号線１００３，１
００４は分類セル１２の入力信号線、同様に外部
入力信号線１００11，１００12は分類セル１６の
入力信号線でもある。１０１１，１０１２は分類
セル１１の出力信号線、１０１３，１０１４は分
類セル１２の出力信号線であり、これらは共に分
類セル２１の入力信号線でもある。２０１１，２
０１２，２０１３，２０１４は分類セル２１の出
力信号線であり、また出力信号線２０１１，２０
１２は分類セル２６の一部の入力信号線、出力信
号線２０１３，２０１４は分類セル２４の一部の
入力信号線でもある。２０１５，２０１６，２０
２１，２０２２等も各分類セルの出力信号線であ
り、次列の分類セルの入力信号線でもある。外部
出力信号線２００１，２００２，……，２００12
は最終列にある分類セルの出力信号線でもあり、
例えば外部出力信号線２００１，２００２は分類
セル２11の一部の出力信号線、外部出力信号線２
００３，２００４は分類セル２14の一部出力信号
線等である。
第一の分類セル１１，１２……，１６は入力さ
れる二つの数値を順序付けして出力するものであ
る。一例として分類セル１１は入力信号線１００
１，１００２より入力される二つの数値を比較
し、その小さい方を出力信号線１０１１へ、その
大きい方を出力信号線１０１２へ出力する。
れる二つの数値を順序付けして出力するものであ
る。一例として分類セル１１は入力信号線１００
１，１００２より入力される二つの数値を比較
し、その小さい方を出力信号線１０１１へ、その
大きい方を出力信号線１０１２へ出力する。
第二の分類セル２１，２２，……，２15は順序
付けされた二つの数値を二組入力して、これら四
つの数値を順序付けして出力するものである。一
例として、分類セル２１は、一方に分類セル１１
にて順序付けられた二つの数値を入力信号線１０
１１，１０１２より、また他方に分類セル１２に
て順序付けられた二つの数値を入力信号線１０１
３，１０１４よりそれぞれ入力し、これら四つの
数値を比較して値の小さいものから順に出力信号
線２０１１，２０１２，２０１３，２０１４に対
応させて出力する。さらに一例を示せば分類セル
２４は、一方に分類セル２１の出力する数値のう
ち大きいもの二つを入力信号線２０１３，２０１
４より、他方に分類セル２２の出力する数値のう
ち小さいもの二つを入力信号線２０１５，２０１
６よりそれぞれ入力し、これら四つの数値の値の
小さいものから順に出力信号線２０２１，２０２
２，２０２３、２０２４に対応させて出力する。
他の分類セルにおいてもその出力する数値の順位
とそれらの出力信号線との対応付けは全く同じで
ある。
付けされた二つの数値を二組入力して、これら四
つの数値を順序付けして出力するものである。一
例として、分類セル２１は、一方に分類セル１１
にて順序付けられた二つの数値を入力信号線１０
１１，１０１２より、また他方に分類セル１２に
て順序付けられた二つの数値を入力信号線１０１
３，１０１４よりそれぞれ入力し、これら四つの
数値を比較して値の小さいものから順に出力信号
線２０１１，２０１２，２０１３，２０１４に対
応させて出力する。さらに一例を示せば分類セル
２４は、一方に分類セル２１の出力する数値のう
ち大きいもの二つを入力信号線２０１３，２０１
４より、他方に分類セル２２の出力する数値のう
ち小さいもの二つを入力信号線２０１５，２０１
６よりそれぞれ入力し、これら四つの数値の値の
小さいものから順に出力信号線２０２１，２０２
２，２０２３、２０２４に対応させて出力する。
他の分類セルにおいてもその出力する数値の順位
とそれらの出力信号線との対応付けは全く同じで
ある。
なお、上記説明で各信号線の本数は一本あるい
は複数本であり、これについては後述される。
は複数本であり、これについては後述される。
以上で、各分類セルの配置および相互結線の規
則性が説明されたが、この規則に従つて任意の個
数の数値に対する本発明の並列分類処理装置は構
成することは容易に推察される。
則性が説明されたが、この規則に従つて任意の個
数の数値に対する本発明の並列分類処理装置は構
成することは容易に推察される。
次に各分類セルの詳細について説明する。
第２図は第一の分類セルの第一の実施例による
具体的構成を示す回路図である。１１は比較回路
である。１２，１３は選択回路である。入力され
る二つの数値X1、X2はそれぞれ入力信号線１０
０１，１００２を通じて比較回路１１、選択回路
１２，１３へ供給される。１１０は比較回路１１
の出力信号線であり、比較回路１１で判定された
二つの数値X1とX2の大小関係を示す１ビツトの
信号を選択回路１２，１３へ供給する。選択回路
１２は比較回路１１の出力信号により制御され
て、二つの数値X1、X2に対しX1X2ならばX1
を、X1＞X2ならばX2をいずれか一方を選択して
出力する。選択回路１３は二つの数値X1、X2に
対し上記と逆の選択によりいずれか一方を出力す
る。即ち入力される二つの数値の小さい方が出力
信号線１０１１へ、大きい方が出力信号線１０１
２へ得られる。
具体的構成を示す回路図である。１１は比較回路
である。１２，１３は選択回路である。入力され
る二つの数値X1、X2はそれぞれ入力信号線１０
０１，１００２を通じて比較回路１１、選択回路
１２，１３へ供給される。１１０は比較回路１１
の出力信号線であり、比較回路１１で判定された
二つの数値X1とX2の大小関係を示す１ビツトの
信号を選択回路１２，１３へ供給する。選択回路
１２は比較回路１１の出力信号により制御され
て、二つの数値X1、X2に対しX1X2ならばX1
を、X1＞X2ならばX2をいずれか一方を選択して
出力する。選択回路１３は二つの数値X1、X2に
対し上記と逆の選択によりいずれか一方を出力す
る。即ち入力される二つの数値の小さい方が出力
信号線１０１１へ、大きい方が出力信号線１０１
２へ得られる。
なお、入出力信号線１００１，１００２，１０
１１，１０１２は入力される数値を表わすビツト
数と同一本数を含むものである。
１１，１０１２は入力される数値を表わすビツト
数と同一本数を含むものである。
第３図は第一の分類セルの第二の実施例による
具体的構成を示す回路図である。この回路は資料
１に記載の判定回路に相当するものであるので、
説明は簡略にする。５１，５２はインバータであ
る。５３，５４，……，６５はNAND回路であ
る。この回路は順序回路であり、NAND回路５
５，５６および５７，５８によりフリツプフロツ
プを形成し内部状態を記憶する。NAND回路５
９，６０，……，６５は入力信号と内部状態によ
つて決まる出力信号を生成する。１１１はリセツ
ト信号線であり、内部状態を初期状態へ設定する
リセツト信号を供給する。入力される二つの数値
X1，X2はそれらの上位ビツトにより順に１ビツ
トずつそれぞれ入力信号線１００１，１００２を
通じて供給される。インバータ５１とNAND回路
５３およびインバータ５２とNAND回路５４とは
それぞれ二つの数値X1、X2をビツト毎に大小を
判定する。一旦X1、X2の大小関係が決まれば、
内部状態は初期状態よりその関係を示す別の状態
へ移り、以後リセツト信号が印加されるまでその
状態を維持する。斯かる回路動作によつて入力さ
れる二つの数値X1、X2の小さい方は出力信号線
１０１１へ、大きい方は出力信号線１０１２へそ
れぞれ上位ビツトから順に出力される。
具体的構成を示す回路図である。この回路は資料
１に記載の判定回路に相当するものであるので、
説明は簡略にする。５１，５２はインバータであ
る。５３，５４，……，６５はNAND回路であ
る。この回路は順序回路であり、NAND回路５
５，５６および５７，５８によりフリツプフロツ
プを形成し内部状態を記憶する。NAND回路５
９，６０，……，６５は入力信号と内部状態によ
つて決まる出力信号を生成する。１１１はリセツ
ト信号線であり、内部状態を初期状態へ設定する
リセツト信号を供給する。入力される二つの数値
X1，X2はそれらの上位ビツトにより順に１ビツ
トずつそれぞれ入力信号線１００１，１００２を
通じて供給される。インバータ５１とNAND回路
５３およびインバータ５２とNAND回路５４とは
それぞれ二つの数値X1、X2をビツト毎に大小を
判定する。一旦X1、X2の大小関係が決まれば、
内部状態は初期状態よりその関係を示す別の状態
へ移り、以後リセツト信号が印加されるまでその
状態を維持する。斯かる回路動作によつて入力さ
れる二つの数値X1、X2の小さい方は出力信号線
１０１１へ、大きい方は出力信号線１０１２へそ
れぞれ上位ビツトから順に出力される。
以上説明で明らかなように、入出力信号線１０
０１，１００２，１０１１，１０１２はそれぞれ
一本の信号線である。
０１，１００２，１０１１，１０１２はそれぞれ
一本の信号線である。
第４図は第二の分類セルの具体的構成を示す回
路図である。
路図である。
２１，２２，２３は第一の分類セルであり、上
記説明の第一あるいは第二の実施例による第一の
分類セルのいずれであつても良い。入力される四
つの数値A1、A2、B1、B2にはそれぞれA1A2お
よびB1B2なる関係にあり、それぞれ入力信号
線１０１１，１０１２，１０１３，１０１４へ供
給される。A1とB1は第一の分類セル２１にて順
序付けられて小さい方が出力信号線２０１１へ、
大きい方が出力信号線２１１へ出力される。A2
とB2は第一の分類セル２２にて順序付けられて
小さい方が出力信号線２１２へ、大きい方が出力
信号線２０１４へ出力される。このとき出力信号
線２０１１へは最も小さい数値が、出力信号線２
０１４へは最も大きな数値が出力されている。出
力信号線２１１，２１２上の残りの二つの数値は
さらに第一の分類セル２３にて順序付けられ、そ
の小さい方が出力信号線２０１２へ、大きい方が
出力信号線２０１３へ出力される。斯くして四つ
の数値A1、A2、B1、B2の全ての順序付けが行な
われる。
記説明の第一あるいは第二の実施例による第一の
分類セルのいずれであつても良い。入力される四
つの数値A1、A2、B1、B2にはそれぞれA1A2お
よびB1B2なる関係にあり、それぞれ入力信号
線１０１１，１０１２，１０１３，１０１４へ供
給される。A1とB1は第一の分類セル２１にて順
序付けられて小さい方が出力信号線２０１１へ、
大きい方が出力信号線２１１へ出力される。A2
とB2は第一の分類セル２２にて順序付けられて
小さい方が出力信号線２１２へ、大きい方が出力
信号線２０１４へ出力される。このとき出力信号
線２０１１へは最も小さい数値が、出力信号線２
０１４へは最も大きな数値が出力されている。出
力信号線２１１，２１２上の残りの二つの数値は
さらに第一の分類セル２３にて順序付けられ、そ
の小さい方が出力信号線２０１２へ、大きい方が
出力信号線２０１３へ出力される。斯くして四つ
の数値A1、A2、B1、B2の全ての順序付けが行な
われる。
以上で本発明による並列分類処理装置の具体的
な構成が説明された。またこの説明から明らかな
ように、本装置では全て第一の分類セルの組合せ
によつて構成されるものと做すこともできる。
な構成が説明された。またこの説明から明らかな
ように、本装置では全て第一の分類セルの組合せ
によつて構成されるものと做すこともできる。
また、第１図を参照して、第一の分類セル１
１，１２と第二の分類セル２１とを合せて一つの
セルとすれば、四つの数値を入力してそれらの値
の大きさの順に並べ替える第三の分類セルと見做
すこともできる。
１，１２と第二の分類セル２１とを合せて一つの
セルとすれば、四つの数値を入力してそれらの値
の大きさの順に並べ替える第三の分類セルと見做
すこともできる。
なお、第１図の全ての信号線は、第一の実施例
による第一の分類セルが使用されるときは複数本
の信号線により成り、第二の実施例による第一の
分類セルが使用されるときは一本の信号線であ
る。
による第一の分類セルが使用されるときは複数本
の信号線により成り、第二の実施例による第一の
分類セルが使用されるときは一本の信号線であ
る。
第一の実施例による第一の分類セルを使用すれ
ば、信号線が増えるが、分類処理が高速に実施で
きる。
ば、信号線が増えるが、分類処理が高速に実施で
きる。
第二の実施例による第一の分類セルを使用すれ
ば、入力される数値のビツト数分だけ処理時間が
かかるが、信号線の数が少なく回路が簡単とな
る。
ば、入力される数値のビツト数分だけ処理時間が
かかるが、信号線の数が少なく回路が簡単とな
る。
ところでこの場合、順序式論理回路構成である
ために動作タイミングについては若干の注意が必
要となる。それは各信号の各分類セルを通過する
ときの遅延についての配慮であり、各分類セルで
はそれぞれの２乃至４つの入力信号がそろつたタ
イミングで入力されて動作できるようにしなけれ
ばならない。一例として分類セル２６への４つの
入力信号をみれば、第２列目の分類セル２１と第
３列目の分類セル２４とからそれぞれ入力される
もので分類セル１段分の遅延時間の相違がある。
これには、信号線２０１１および２０１２上に前
記遅延時間に相当する遅延を挿入することによつ
て容易に動作タイミングの調整を図ることができ
る。あるいは各列毎に適当なタイミングに調整さ
れた同期信号を供給してもよく、いずれにしても
通常のデイジタル装置の設計技術にて容易に実施
されるものである。
ために動作タイミングについては若干の注意が必
要となる。それは各信号の各分類セルを通過する
ときの遅延についての配慮であり、各分類セルで
はそれぞれの２乃至４つの入力信号がそろつたタ
イミングで入力されて動作できるようにしなけれ
ばならない。一例として分類セル２６への４つの
入力信号をみれば、第２列目の分類セル２１と第
３列目の分類セル２４とからそれぞれ入力される
もので分類セル１段分の遅延時間の相違がある。
これには、信号線２０１１および２０１２上に前
記遅延時間に相当する遅延を挿入することによつ
て容易に動作タイミングの調整を図ることができ
る。あるいは各列毎に適当なタイミングに調整さ
れた同期信号を供給してもよく、いずれにしても
通常のデイジタル装置の設計技術にて容易に実施
されるものである。
最後に本発明の原理を具体的に説明する。
第５図は複数個の数値が並列的に分類される様
子を示すためのデータの流れ図である。
子を示すためのデータの流れ図である。
１１，……，１６等は第一の分類セルであり、
２１，……，２３，２14，……，２15等は第二の
分類セルであり、これら各分類セルの配置は第４
図に対応する。３は記憶装置であり、一例として
分類すべき数値が12個“10”、“４”、“12”、……
の順で記憶されている。各分類セル内に示された
数値は、前記12個の数値が各分類セルを伝達され
る順序と、各分類セルでの順序付けの様子を表わ
すものである。４は最後の列の分類セルの出力を
受ける記憶装置であり、前記12個の数値が
“１”、“２”、“３”……の順に並べ替えられて得
られたことを示している。
２１，……，２３，２14，……，２15等は第二の
分類セルであり、これら各分類セルの配置は第４
図に対応する。３は記憶装置であり、一例として
分類すべき数値が12個“10”、“４”、“12”、……
の順で記憶されている。各分類セル内に示された
数値は、前記12個の数値が各分類セルを伝達され
る順序と、各分類セルでの順序付けの様子を表わ
すものである。４は最後の列の分類セルの出力を
受ける記憶装置であり、前記12個の数値が
“１”、“２”、“３”……の順に並べ替えられて得
られたことを示している。
以上の説明により、本発明の原理の特徴は前記
資料１に記載の並列分類処理装置に較べ、各々の
分類セルが前列の分類セルの出力する順序付けの
情報を有効に活用することにある。
資料１に記載の並列分類処理装置に較べ、各々の
分類セルが前列の分類セルの出力する順序付けの
情報を有効に活用することにある。
従つて本発明によれば、回路規模を軽減できか
つ集積化に好適ならしめる高速並列分類処理装置
が得られその効果は大なるものがある。
つ集積化に好適ならしめる高速並列分類処理装置
が得られその効果は大なるものがある。
第１図は本発明による並列分類処理装置の構成
を示すブロツク図、第２図は第一の分類セルの第
一の実施例を示す回路図、第３図は第一の分類セ
ルの第二の実施例を示す回路図、第４図は第二の
分類セルの具体的構成を示す回路図、第５図はデ
ータ流れの一例を説明するための図である。図に
おいて、１１，１２，……，１６…第一の分類セ
ル、２１，２２，……，２15…第二の分類セル、
１１…比較回路、１２，１３…選択回路、２１，
２２，２３…第一の分類セル、５１，５２…イン
バータ、５３，５４…，６５…NAND回路、３，
４…記憶装置である。
を示すブロツク図、第２図は第一の分類セルの第
一の実施例を示す回路図、第３図は第一の分類セ
ルの第二の実施例を示す回路図、第４図は第二の
分類セルの具体的構成を示す回路図、第５図はデ
ータ流れの一例を説明するための図である。図に
おいて、１１，１２，……，１６…第一の分類セ
ル、２１，２２，……，２15…第二の分類セル、
１１…比較回路、１２，１３…選択回路、２１，
２２，２３…第一の分類セル、５１，５２…イン
バータ、５３，５４…，６５…NAND回路、３，
４…記憶装置である。
Claims (1)
- １ 二つの数値を入力し、大きさの順に並べ替え
て出力する第一の分類セルと、前記第一の分類セ
ルを３個組合せて構成し大きさの順に並べられた
二つの数値が二組から成る四つの数値を入力して
大きさの順に並べ替えて出力する第二の分類セル
とをそれぞれ複数個備え、前記第一の分類セルは
第一列目に、前記第二の分類セルは第二列目以後
の複数の列に配列状に並べられ、かつ前記第二列
目以後の分類セルのそれぞれへは、予じめ決めら
れた規則に従つて、前列の分類セルのうち相隣合
うものからそれぞれ二つずつの出力信号が供給さ
れるように、前記二種類の分類セルが規則的に相
互結合されて構成され、入力される複数個の数値
が並列的に分類処理されて、大きさの順に並べ替
えられ出力されることを特徴とする並列分類処理
装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1274780A JPS56110149A (en) | 1980-02-05 | 1980-02-05 | Parallel classification processing device |
| US06/232,052 US4410960A (en) | 1980-02-05 | 1981-02-05 | Sorting circuit for three or more inputs |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1274780A JPS56110149A (en) | 1980-02-05 | 1980-02-05 | Parallel classification processing device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS56110149A JPS56110149A (en) | 1981-09-01 |
| JPS627578B2 true JPS627578B2 (ja) | 1987-02-18 |
Family
ID=11814007
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1274780A Granted JPS56110149A (en) | 1980-02-05 | 1980-02-05 | Parallel classification processing device |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS56110149A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6170U (ja) * | 1984-06-05 | 1986-01-06 | 横河電機株式会社 | 信号選択回路 |
-
1980
- 1980-02-05 JP JP1274780A patent/JPS56110149A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS56110149A (en) | 1981-09-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8190943B2 (en) | Systolic merge sorter | |
| EP0066061A2 (en) | Relational algebra engine | |
| US12154034B2 (en) | Pruning method based on crossbar architecture and system thereof | |
| JPH065513B2 (ja) | メモリ・システム | |
| CN115905233A (zh) | 归并树形数据排序系统和排序方法 | |
| US5122979A (en) | Method and a digital electronic device for the evaluation of an extremum of a set of binary encoded data words | |
| US20230176999A1 (en) | Devices for time division multiplexing of state machine engine signals | |
| WO1993025975A2 (en) | A programmable logic device | |
| Lipu et al. | Exploiting parallelism for faster implementation of Bubble sort algorithm using FPGA | |
| JP3703518B2 (ja) | 連想メモリシステム | |
| US3514760A (en) | Sorting array ii | |
| US3336580A (en) | Sorting system for multi-bit binary digital records | |
| US5903780A (en) | Data sorting device having multi-input comparator comparing data input from latch register and key value storage devices | |
| JPH0666050B2 (ja) | ソート処理方法 | |
| US4336600A (en) | Binary word processing method using a high-speed sequential adder | |
| CN118642680B (zh) | 一种基于fpga的堆排序系统及方法 | |
| JPS627578B2 (ja) | ||
| JP2002229772A (ja) | ソート処理方法およびソート処理装置 | |
| US5274589A (en) | Method and apparatus for writing and reading data to/from a memory | |
| JPS627579B2 (ja) | ||
| Lin et al. | Two-dimensional rank-order filter by using max-min sorting network | |
| US5838335A (en) | Graphic data processing method and device | |
| JPH0797310B2 (ja) | ソ−ト処理装置 | |
| JP2587447B2 (ja) | ソート処理装置 | |
| JPH07120264B2 (ja) | ソート処理装置 |