JPS6243218B2 - - Google Patents
Info
- Publication number
- JPS6243218B2 JPS6243218B2 JP2282781A JP2282781A JPS6243218B2 JP S6243218 B2 JPS6243218 B2 JP S6243218B2 JP 2282781 A JP2282781 A JP 2282781A JP 2282781 A JP2282781 A JP 2282781A JP S6243218 B2 JPS6243218 B2 JP S6243218B2
- Authority
- JP
- Japan
- Prior art keywords
- basic cell
- data
- input
- bus
- data register
- 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
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)
- Complex Calculations (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Description
【発明の詳細な説明】
本発明は、計算機中でのデータの順序付け、す
なわちソーテイング操作を高速に行なうための回
路に関する。
なわちソーテイング操作を高速に行なうための回
路に関する。
データをその大小関係に基づいて順序付けし並
べ換える操作であるソーテイングは、計算機にお
いて基本的な操作であるが、従来は主にソフトウ
エアによつて行なわれており、その効率の改善が
望まれていた。
べ換える操作であるソーテイングは、計算機にお
いて基本的な操作であるが、従来は主にソフトウ
エアによつて行なわれており、その効率の改善が
望まれていた。
近年、集積回路技術の進歩に伴つて、大規模な
論理回路が構成できるようになり、ハードウエア
によるソーテイング回路の提案がいくつか行なわ
れているが、このような従来の手段では、いずれ
も複数のプロセツサが同時にソーテイングの対象
となるデータにアクセスすることを前提としてお
り、したがつて記憶装置から１つずつデータを読
み出す構造になつている従来の計算機の構成を根
本的に変えなければならなかつたり、記憶装置と
ソーテイング回路との通信量が大きくなつたりす
る等の欠点があつた。
論理回路が構成できるようになり、ハードウエア
によるソーテイング回路の提案がいくつか行なわ
れているが、このような従来の手段では、いずれ
も複数のプロセツサが同時にソーテイングの対象
となるデータにアクセスすることを前提としてお
り、したがつて記憶装置から１つずつデータを読
み出す構造になつている従来の計算機の構成を根
本的に変えなければならなかつたり、記憶装置と
ソーテイング回路との通信量が大きくなつたりす
る等の欠点があつた。
本発明は、これらの問題点を解決しようとする
もので、複数のデータを順次入力しながら、しか
も順次並列的に比較・計数を行なうことにより、
従来の計算機に容易に適用できるとともに、記憶
装置とソーテイング回路との間の通信量を必要最
小限にし、逐次的に記憶装置から取り出されるデ
ータをパイプライン的に処理できるようにした並
列計数ソーテイング回路を提供することを目的と
する。
もので、複数のデータを順次入力しながら、しか
も順次並列的に比較・計数を行なうことにより、
従来の計算機に容易に適用できるとともに、記憶
装置とソーテイング回路との間の通信量を必要最
小限にし、逐次的に記憶装置から取り出されるデ
ータをパイプライン的に処理できるようにした並
列計数ソーテイング回路を提供することを目的と
する。
このため、本発明の並列計数ソーテイング回路
は、複数（ｍ）個のデータの大小関係についてソ
ーテイングを行なうべく、バスデータレジスタお
よびシフトデータレジスタと、これら２つのレジ
スタの内容を比較し大小関係を判定する比較器
と、その比較結果に基づく計数を行なうためのカ
ウンタとを持つ基本セルが複数（ｎ≧ｍ）個設け
られて、これらの基本セルが第１番目の基本セ
ル、第２番目の基本セルのごとく第ｎ番目の基本
セルまで順に並べられることによつて基本セルの
配列が構成され、さらに入力バスおよび出力バス
が設けられて、上記配列中の各基本セルのバスデ
ータレジスタが上記入力バスに接続されるととも
に、各基本セルのカウンタの出力側が上記出力バ
スに接続され、さらに第１番目の基本セルのシフ
トデータレジスタの入力側が上記入力バスに接続
されるとともに各基本セルのシフトデータレジス
タの出力側がその基本セルに続く次の基本セルの
シフトデータレジスタの入力側へ接続され、最初
に入力されたデータを上記配列中の第１番目の基
本セルにおけるバスデータレジスタに、第２番目
に入力されたデータを同配列中の第２番目の基本
セルにおけるバスデータレジスタにというように
逐次的に入力されるデータを上記入力バスを通し
て順次各基本セルのバスデータレジスタに記憶さ
せ、それと同時に入力されたデータを第１番目の
基本セルにおけるシフトデータレジスタに入れ、
新しいデータが入力されるごとに上記配列中の各
基本セルにおけるシフトデータレジスタの内容を
その基本セルに続く次の基本セルにおけるシフト
データレジスタへ移動させ、各基本セルにおいて
その比較器による比較結果に基づいて計数を行な
うことにより、基本セルのバスデータレジスタに
記憶されているデータの入力された全データ中に
おける順位をカウンタ上に作り、最後に入力され
たデータが各基本セルのシフトデータレジスタを
通過した後にその基本セルにおけるカウンタの内
容を上記出力バスを通して出力することにより、
入力されたデータ全体の中における各データの順
位を入力終了後直ちに逐次的に出力することを可
能ならしめるべく構成されたことを特徴としてい
る。
は、複数（ｍ）個のデータの大小関係についてソ
ーテイングを行なうべく、バスデータレジスタお
よびシフトデータレジスタと、これら２つのレジ
スタの内容を比較し大小関係を判定する比較器
と、その比較結果に基づく計数を行なうためのカ
ウンタとを持つ基本セルが複数（ｎ≧ｍ）個設け
られて、これらの基本セルが第１番目の基本セ
ル、第２番目の基本セルのごとく第ｎ番目の基本
セルまで順に並べられることによつて基本セルの
配列が構成され、さらに入力バスおよび出力バス
が設けられて、上記配列中の各基本セルのバスデ
ータレジスタが上記入力バスに接続されるととも
に、各基本セルのカウンタの出力側が上記出力バ
スに接続され、さらに第１番目の基本セルのシフ
トデータレジスタの入力側が上記入力バスに接続
されるとともに各基本セルのシフトデータレジス
タの出力側がその基本セルに続く次の基本セルの
シフトデータレジスタの入力側へ接続され、最初
に入力されたデータを上記配列中の第１番目の基
本セルにおけるバスデータレジスタに、第２番目
に入力されたデータを同配列中の第２番目の基本
セルにおけるバスデータレジスタにというように
逐次的に入力されるデータを上記入力バスを通し
て順次各基本セルのバスデータレジスタに記憶さ
せ、それと同時に入力されたデータを第１番目の
基本セルにおけるシフトデータレジスタに入れ、
新しいデータが入力されるごとに上記配列中の各
基本セルにおけるシフトデータレジスタの内容を
その基本セルに続く次の基本セルにおけるシフト
データレジスタへ移動させ、各基本セルにおいて
その比較器による比較結果に基づいて計数を行な
うことにより、基本セルのバスデータレジスタに
記憶されているデータの入力された全データ中に
おける順位をカウンタ上に作り、最後に入力され
たデータが各基本セルのシフトデータレジスタを
通過した後にその基本セルにおけるカウンタの内
容を上記出力バスを通して出力することにより、
入力されたデータ全体の中における各データの順
位を入力終了後直ちに逐次的に出力することを可
能ならしめるべく構成されたことを特徴としてい
る。
以下、図面による本発明の一実施例としての並
列係数ソーテイング回路について説明すると、第
１図はその全体構成図、第２図はその基本セルの
構成図、第３図ａ〜ｇはいずれもその作用を説明
するための説明図、第４，５図は本回路を集積化
した例を示すもので、第４図はその基本セルのレ
イアウトを示す模式図、第５図はそのチツプのレ
イアウトを示す模式図である。
列係数ソーテイング回路について説明すると、第
１図はその全体構成図、第２図はその基本セルの
構成図、第３図ａ〜ｇはいずれもその作用を説明
するための説明図、第４，５図は本回路を集積化
した例を示すもので、第４図はその基本セルのレ
イアウトを示す模式図、第５図はそのチツプのレ
イアウトを示す模式図である。
第１図に示すように、本回路は複数（ｎ）個の
基本セルを縦続接続し、さらに入力バス１および
出力バス２によつて各セルを結合して構成する。
基本セルを縦続接続し、さらに入力バス１および
出力バス２によつて各セルを結合して構成する。
そして、この回路への入力は、ソーテイングの
キーにあたるデータ列x1，x2，x3，…，ｘnと開
始信号ｓおよび終了信号ｆである。
キーにあたるデータ列x1，x2，x3，…，ｘnと開
始信号ｓおよび終了信号ｆである。
ここに、データ列の長さｍは、回路中の基本セ
ル数ｎを越えないものとする。
ル数ｎを越えないものとする。
ところで、データ列は各時刻ごとにx1から順に
１つずつ連続的に入力される。すなわち、時刻t1
にデータx1が入力されるものとする。
１つずつ連続的に入力される。すなわち、時刻t1
にデータx1が入力されるものとする。
一方、開始信号ｓはデータ列の入力が開始され
る時刻t1に印加され、他方終了信号ｆは最後のデ
ータｘnが入力される次の時刻ｔn+1に加えられ
る。
る時刻t1に印加され、他方終了信号ｆは最後のデ
ータｘnが入力される次の時刻ｔn+1に加えられ
る。
またこの回路は、データ列x1，x2，x3，…，ｘ
nの入力が全て終了した次の時刻ｔn+1から順次出
力列c1，c2，c3，…，ｃnを各時刻ごとに１つず
つ連続的に出力する。
nの入力が全て終了した次の時刻ｔn+1から順次出
力列c1，c2，c3，…，ｃnを各時刻ごとに１つず
つ連続的に出力する。
ここで各出力c1は、入力データx1が入力データ
列x1，x2，x3，…，ｘnの中で何番目に大きいか
を示している。
列x1，x2，x3，…，ｘnの中で何番目に大きいか
を示している。
すなわち、例えば、入力データとして、３，
11，８，９，４という自然数のデータ列が与えら
れたとすると、出力列は５，１，３，２，４とな
る。
11，８，９，４という自然数のデータ列が与えら
れたとすると、出力列は５，１，３，２，４とな
る。
なお、計算機は簡単な付加回路またはプログラ
ムによつて、この出力列c1，c2，c3，…，ｃnを
基に記憶装置上での並び換えを容易に行なうこと
ができる。
ムによつて、この出力列c1，c2，c3，…，ｃnを
基に記憶装置上での並び換えを容易に行なうこと
ができる。
このように、ソーテイングのキーを入力し、各
キーの順位を出力することにより、記憶装置とソ
ーテイング回路との通信量を必要最小限にするこ
とができる。
キーの順位を出力することにより、記憶装置とソ
ーテイング回路との通信量を必要最小限にするこ
とができる。
各基本セルは、第２図に示すように、バスデー
タレジスタ３、シフトデータレジスタ４、比較器
５、カウンタ６および制御信号回路７で構成され
ている。
タレジスタ３、シフトデータレジスタ４、比較器
５、カウンタ６および制御信号回路７で構成され
ている。
バスデータレジスタ３は、制御信号回路７から
の信号ｇにしたがつて入力バス１上のデータを取
り込み記憶するためのレジスタである。
の信号ｇにしたがつて入力バス１上のデータを取
り込み記憶するためのレジスタである。
またシフトデータレジスタ４は、各時刻ごと
に、第１図において左隣の基本セルのシフトデー
タレジスタ４の内容を取り込むためのレジスタで
ある。すなわち、基本セルの配列の上で、シフト
データレジスタ４の内容が各時刻ごとに右へ１基
本セルずつシフトされる。
に、第１図において左隣の基本セルのシフトデー
タレジスタ４の内容を取り込むためのレジスタで
ある。すなわち、基本セルの配列の上で、シフト
データレジスタ４の内容が各時刻ごとに右へ１基
本セルずつシフトされる。
比較器５は、各時刻ごとに、バスデータレジス
タ３の内容と、シフトデータレジスタ４の内容と
を比較し、シフトデータレジスタ４の内容の方が
大きいときにのみ１、その他の場合は０を出力す
るものである。
タ３の内容と、シフトデータレジスタ４の内容と
を比較し、シフトデータレジスタ４の内容の方が
大きいときにのみ１、その他の場合は０を出力す
るものである。
カウンタ６は、各時刻ごとに、比較器５の出力
を現在の計数値に加えてゆき、制御信号回路７か
らの信号ｐで計数値を出力バス２へ出力できるよ
うになつている。
を現在の計数値に加えてゆき、制御信号回路７か
らの信号ｐで計数値を出力バス２へ出力できるよ
うになつている。
ここで、時刻t1で第ｊ番目の基本セルにある開
始信号ｓまたは終了信号ｆは、時刻ｔi+1に第ｊ
＋１番目の基本セルｊ＋１へ移動する。
始信号ｓまたは終了信号ｆは、時刻ｔi+1に第ｊ
＋１番目の基本セルｊ＋１へ移動する。
制御信号回路７は、開始信号ｓがその基本セル
に存在する時刻に、そのセルのバスデータレジス
タ３へ入力取り込みの信号ｇを送るとともに、信
号ｒによつてカウンタ６の内容を初期値１にセツ
トする。また、終了信号ｆがそのセルに存在する
時刻には、制御信号回路７は信号ｐをカウンタ６
で送り、カウンタ６内の計数値を出力バス２へ出
力させる。
に存在する時刻に、そのセルのバスデータレジス
タ３へ入力取り込みの信号ｇを送るとともに、信
号ｒによつてカウンタ６の内容を初期値１にセツ
トする。また、終了信号ｆがそのセルに存在する
時刻には、制御信号回路７は信号ｐをカウンタ６
で送り、カウンタ６内の計数値を出力バス２へ出
力させる。
次に、第３図にしたがつてこの回路の動作を詳
しく説明する。第３図ａ〜ｇは、ｎ個の基本セル
からなる並列計数ソーテイング回路に、基本セル
数と同数の入力データ列x1，x2，x3，…，ｘoが
加えられたときの動作を、各時刻のバスデータレ
ジスタ３、シフトデータレジスタ４およびカウン
タ６の内容によつて表わしたものである。
しく説明する。第３図ａ〜ｇは、ｎ個の基本セル
からなる並列計数ソーテイング回路に、基本セル
数と同数の入力データ列x1，x2，x3，…，ｘoが
加えられたときの動作を、各時刻のバスデータレ
ジスタ３、シフトデータレジスタ４およびカウン
タ６の内容によつて表わしたものである。
まず時刻t1において、入力データとしてx1が入
力されるとともに、開始信号ｓが加えられる。
力されるとともに、開始信号ｓが加えられる。
データx1は、第３図ａに示すごとく、第１番目
の基本セルにおけるバスデータレジスタ３および
シフトデータレジスタ４へ取り込まれ、その比較
の結果が第１番目の基本セルのカウンタ６に計数
される。
の基本セルにおけるバスデータレジスタ３および
シフトデータレジスタ４へ取り込まれ、その比較
の結果が第１番目の基本セルのカウンタ６に計数
される。
また、時刻t2では、第３図ｂに示すごとく、デ
ータx2が入力され、開始信号ｓが第２番目の基本
セルへ移動しているので、データx2は第２番目の
基本セルのバスデータレジスタ３へ取り込まれ
る。これと同時に第２番目の基本セルにおけるシ
フトデータレジスタ４にはデータx1が入り、第１
番目の基本セルにおけるシフトデータレジスタ４
にはデータx2が入つて、これら２つのセルで並列
的に比較と計数とが行なわれる。
ータx2が入力され、開始信号ｓが第２番目の基本
セルへ移動しているので、データx2は第２番目の
基本セルのバスデータレジスタ３へ取り込まれ
る。これと同時に第２番目の基本セルにおけるシ
フトデータレジスタ４にはデータx1が入り、第１
番目の基本セルにおけるシフトデータレジスタ４
にはデータx2が入つて、これら２つのセルで並列
的に比較と計数とが行なわれる。
さらに、時刻t3では、第３図ｃに示すごとく、
データx3が入力され、シフトデータレジスタ４の
内容と開始信号ｓとが次の基本セルへ、すなわち
右へ１基本セルずつシフトされ、入力バス１上の
データx3は第３番目の基本セルにおけるバスデー
タレジスタ３へ取り込まれる。
データx3が入力され、シフトデータレジスタ４の
内容と開始信号ｓとが次の基本セルへ、すなわち
右へ１基本セルずつシフトされ、入力バス１上の
データx3は第３番目の基本セルにおけるバスデー
タレジスタ３へ取り込まれる。
以下同様にして、ｎより大きくないｉに対し
て、時刻ｔiでは、データｘiが入力されるととも
に、シフトデータレジスタ４の内容と開始信号ｓ
とが右へ１基本セルずつシフトされ、第ｉ番目の
基本セルにおけるバスデータレジスタ３へデータ
x1が取り込まれる。したがつて各時刻において、
各基本セルで順次並列的に比較が行なわれ、その
結果が並列的に計数される。
て、時刻ｔiでは、データｘiが入力されるととも
に、シフトデータレジスタ４の内容と開始信号ｓ
とが右へ１基本セルずつシフトされ、第ｉ番目の
基本セルにおけるバスデータレジスタ３へデータ
x1が取り込まれる。したがつて各時刻において、
各基本セルで順次並列的に比較が行なわれ、その
結果が並列的に計数される。
そして時刻ｔoで、第３図ｄに示すごとく、最
後のデータｘoが入力され、時刻ｔo+1で、第３図
ｅに示すごとく、終了信号ｆが入力されて、計数
値の出力が始まる。
後のデータｘoが入力され、時刻ｔo+1で、第３図
ｅに示すごとく、終了信号ｆが入力されて、計数
値の出力が始まる。
さらに終了信号ｆは、ｎより大きくない自然数
ｉについて、時刻ｔo+iにおいて第ｉ番目の基本
セルに存在し、第ｉ番目の基本セルの計数値ｃi
を順次出力バス２上へ出力する。このようにして
出力される計数値ｃiはデータｘiが入力データ列
x1，x2，x3，…，ｘoの中で何番目に大きいかを
示している。
ｉについて、時刻ｔo+iにおいて第ｉ番目の基本
セルに存在し、第ｉ番目の基本セルの計数値ｃi
を順次出力バス２上へ出力する。このようにして
出力される計数値ｃiはデータｘiが入力データ列
x1，x2，x3，…，ｘoの中で何番目に大きいかを
示している。
なお、上述の説明からもわかるように、計数値
ｃiを出力しているときも、第ｉ＋１番目目の基
本セル、第ｉ＋２番目の基本セル、…、第ｎ番目
の基本セルにおいては比較と計数とが順次並列的
に行なわれている。
ｃiを出力しているときも、第ｉ＋１番目目の基
本セル、第ｉ＋２番目の基本セル、…、第ｎ番目
の基本セルにおいては比較と計数とが順次並列的
に行なわれている。
そして時刻ｔ2oで、第３図ｇに示すごとく、最
後の出力ｃoが出力され、本並列計数ソーテイン
グ回路は動作を終了する。
後の出力ｃoが出力され、本並列計数ソーテイン
グ回路は動作を終了する。
また、時刻ｔo+2からは次の入力データ列y1，
y2，y3，…，ｙoのソーテイングを開始すること
もでき、このようにすれば回路の処理効率を高め
ることができる。
y2，y3，…，ｙoのソーテイングを開始すること
もでき、このようにすれば回路の処理効率を高め
ることができる。
なお、本回路をnMOS技術を用いて集積化する
場合について、簡単に説明する。ここで各レジス
タ３，４の長さを32ビツト、カウンタ６の長さを
16ビツトとする。
場合について、簡単に説明する。ここで各レジス
タ３，４の長さを32ビツト、カウンタ６の長さを
16ビツトとする。
まず各基本セルは第４図に示すような構成とす
る。
る。
そして比較器５およびカウンタ６の組合わせ回
路部分には、PLAを用いる。この場合PLAは三
角形構造にして面積を減らす。
路部分には、PLAを用いる。この場合PLAは三
角形構造にして面積を減らす。
また１つの基本セルの大きさはおよそ720λ×
750λとする。
750λとする。
ここでλは設計の基本単位である。
なお、制御信号回路７の部分には、多少余裕が
あるので、基本セルの大きさを変えることなく、
機能を追加して各種の応用ができるようにするこ
とが可能である。
あるので、基本セルの大きさを変えることなく、
機能を追加して各種の応用ができるようにするこ
とが可能である。
さらに入力バス１の幅は約200λ、出力バス２
の幅は約100λにする。
の幅は約100λにする。
次に、この基本セルを第５図に示すように配置
してチツプを構成する。今、現在の技術を適用
し、λ＝２μｍとすると、およそ１cm角のチツプ
に20個のセルを集積できる。
してチツプを構成する。今、現在の技術を適用
し、λ＝２μｍとすると、およそ１cm角のチツプ
に20個のセルを集積できる。
そして同じチツプをいくつか結合して、１つの
ソーテイング回路を構成できるように、チツプに
は、結合用のピンを用意する。ここでピン数は、
レジスタ長を32ビツト、カウンタ長を16ビツトと
して、120ピンになる。
ソーテイング回路を構成できるように、チツプに
は、結合用のピンを用意する。ここでピン数は、
レジスタ長を32ビツト、カウンタ長を16ビツトと
して、120ピンになる。
このようにチツプをいくつか結合して、ソーテ
イング回路を構成する。
イング回路を構成する。
なお、結合するチツプの数は、システムの要求
に合わせて決定すればよい。
に合わせて決定すればよい。
ただし、カウンタ長が16ビツトであるから、基
本セルの数が216＝65536個を越えない範囲でチツ
プを結合する。
本セルの数が216＝65536個を越えない範囲でチツ
プを結合する。
またソーテイング回路は、10MHzくらいのクロ
ツク周波数で動作可能であるため、これにより例
えば６万個のキーを12ms程度で処理できる。
ツク周波数で動作可能であるため、これにより例
えば６万個のキーを12ms程度で処理できる。
なお、第５図中、符号８は入力バス用パツド、
９は出力バス用パツド、１０はシフトデータおよ
び制御信号の入力用パツド、１１はシフトデータ
および制御信号の出力用パツドを示している。
９は出力バス用パツド、１０はシフトデータおよ
び制御信号の入力用パツド、１１はシフトデータ
および制御信号の出力用パツドを示している。
ところで、前述の実施例において、入力データ
として、例えば複数の人の各年令に相当する数を
使用すれば、入力された年令が全キー中で何番目
に小さいかを示す順位の列が出力されるので、出
力バス２に接続された記憶装置で、出力されてく
る順位に基づいて人名を並べ換えれば、複数の人
を年令順に並べることができる。
として、例えば複数の人の各年令に相当する数を
使用すれば、入力された年令が全キー中で何番目
に小さいかを示す順位の列が出力されるので、出
力バス２に接続された記憶装置で、出力されてく
る順位に基づいて人名を並べ換えれば、複数の人
を年令順に並べることができる。
もちろん、その他各種のソーテイング処理を行
なえることはいうまでもない。
なえることはいうまでもない。
なお、順位付けとしては、小さい順に順位を付
けることも、大きい順に順位を付けることも自由
である。
けることも、大きい順に順位を付けることも自由
である。
以上詳述したように、本発明の並列計数ソーテ
イング回路によれば、複数のデータを順次入力し
ながら、しかも順次並列的に比較・計数を行なう
ことにより、入力されたデータ数の約２倍の単位
時間で、高速にしかも通信量を少なくしてソーテ
イングを行なえる利点がある。
イング回路によれば、複数のデータを順次入力し
ながら、しかも順次並列的に比較・計数を行なう
ことにより、入力されたデータ数の約２倍の単位
時間で、高速にしかも通信量を少なくしてソーテ
イングを行なえる利点がある。
図は本発明の一実施例としての並列計数ソーテ
イング回路を示すもので、第１図はその全体構成
図、第２図はその基本セルの構成図、第３図ａ〜
ｇはいずれもその作用を説明するための説明図、
第４，５図は本回路を集積化した例を示すもの
で、第４図はその基本セルのレイアウトを示す模
式図、第５図はそのチツプのレイアウトを示す模
式図である。 １……入力バス、２……出力バス、３……バス
データレジスタ、４……シフトデータレジスタ、
５……比較器、６……カウンタ、７……制御信号
回路、８……入力バス用パツド、９……出力バス
用パツド、１０……シフトデータおよび制御信号
の入力用パツド、１１……シフトデータおよび制
御信号の出力用パツド。
イング回路を示すもので、第１図はその全体構成
図、第２図はその基本セルの構成図、第３図ａ〜
ｇはいずれもその作用を説明するための説明図、
第４，５図は本回路を集積化した例を示すもの
で、第４図はその基本セルのレイアウトを示す模
式図、第５図はそのチツプのレイアウトを示す模
式図である。 １……入力バス、２……出力バス、３……バス
データレジスタ、４……シフトデータレジスタ、
５……比較器、６……カウンタ、７……制御信号
回路、８……入力バス用パツド、９……出力バス
用パツド、１０……シフトデータおよび制御信号
の入力用パツド、１１……シフトデータおよび制
御信号の出力用パツド。
Claims (1)
- １ 複数（ｍ）個のデータの大小関係についてソ
ーテイングを行なうべく、バスデータレジスタお
よびシフトデータレジスタと、これら２つのレジ
スタの内容を比較し大小関係を判定する比較器
と、その比較結果に基づく計数を行なうためのカ
ウンタとを持つ基本セルが複数（ｎ≧ｍ）個設け
られ、これらの基本セルが第１番目の基本セル、
第２番目の基本セルのごとく第ｎ番目の基本セル
まで順に並べられることによつて基本セルの配列
が構成され、さらに入力バスおよび出力バスが設
けられて、上記配列中の各基本セルのバスデータ
レジスタが上記入力バスに接続されるとともに、
各基本セルのカウンタの出力側が上記出力バスに
接続され、さらに第１番目の基本セルのシフトデ
ータレジスタの入力側が上記入力バスに接続され
るとともに各基本セルのシフトデータレジスタの
出力側がその基本セルに続く次の基本セルのシフ
トデータレジスタの入力側へ接続され、最初に入
力されたデータを上記配列中の第１番目の基本セ
ルにおけるバスデータレジスタに、第２番目に入
力されたデータを同配列中の第２番目の基本セル
におけるバスデータレジスタにというように逐次
的に入力されるデータを上記入力バスを通して順
次各基本セルのバスデータレジスタに記憶させ、
それと同時に入力されたデータを第１番目の基本
セルにおけるシフトデータレジスタに入れ、新し
いデータが入力されるごとに上記配列中の各基本
セルにおけるシフトデータレジスタの内容をその
基本セルに続く次の基本セルにおけるシフトデー
タレジスタへ移動させ、各基本セルにおいてその
比較器による比較結果に基づいて計数を行なうこ
とにより、基本セルのバスデータレジスタに記憶
されているデータの入力された全データ中におけ
る順位をカウンタ上に作り、最後に入力されたデ
ータが各基本セルのシフトデータレジスタを通過
した後にその基本セルにおけるカウンタの内容を
上記出力バスを通して出力することにより、入力
されたデータ全体の中における各データの順位を
入力終了後直ちに逐次的に出力することを可能な
らしめるべく構成されたことを特徴とする、並列
計数ソーテイング回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2282781A JPS57137939A (en) | 1981-02-18 | 1981-02-18 | Parallel counting and sorting method and its circuit |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2282781A JPS57137939A (en) | 1981-02-18 | 1981-02-18 | Parallel counting and sorting method and its circuit |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS57137939A JPS57137939A (en) | 1982-08-25 |
| JPS6243218B2 true JPS6243218B2 (ja) | 1987-09-11 |
Family
ID=12093520
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2282781A Granted JPS57137939A (en) | 1981-02-18 | 1981-02-18 | Parallel counting and sorting method and its circuit |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS57137939A (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61117663A (ja) * | 1984-10-26 | 1986-06-05 | Fujitsu Ltd | ソ−ト演算回路 |
| JPH0792763B2 (ja) * | 1988-11-16 | 1995-10-09 | 日本電気株式会社 | 障害処理方式 |
| CN109460210B (zh) * | 2018-10-22 | 2020-11-03 | 重庆中科云从科技有限公司 | 排序系统及数据处理方法 |
-
1981
- 1981-02-18 JP JP2282781A patent/JPS57137939A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS57137939A (en) | 1982-08-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US3800129A (en) | Mos desk calculator | |
| JPH0516054B2 (ja) | ||
| JPS61107596A (ja) | 連想記憶装置 | |
| JPH08504992A (ja) | 動的記憶装置におけるパターン検索およびリフレッシュ論理 | |
| US9933998B2 (en) | Methods and apparatuses for performing multiplication | |
| JPH0776910B2 (ja) | リバウンド分類装置を併合装置として使用する分類加速装置 | |
| US11200029B2 (en) | Extendable multiple-digit base-2n in-memory adder device | |
| JPS6243218B2 (ja) | ||
| Kim et al. | A parallel pipelined relational query processor | |
| JPH0666050B2 (ja) | ソート処理方法 | |
| Blair | Low cost sorting circuit for VLSI | |
| JP2803119B2 (ja) | Ｃｍｏｓゲートアレイ消費電力計算方式 | |
| US4523210A (en) | Fast error checked multibit multiplier | |
| Chazelle et al. | Optimality in VLSI | |
| JP2824482B2 (ja) | ２分決定グラフの変数順決定方式 | |
| EP0112186A2 (en) | Modular high-speed multipliers, and integrated circuit chip modules for such multipliers | |
| JPS595937B2 (ja) | 電子計算装置 | |
| Gajski et al. | A parallel pipelined relational query processor: An architectural overview | |
| JP2608600B2 (ja) | ２つの数の和のパリティビットの計算装置 | |
| US20260111511A1 (en) | Depth-wise convolution with input and output parallelism | |
| Parhami | Architectural tradeoffs in the design of VLSI-based associative memories | |
| RU2153699C1 (ru) | Устройство для перераспределения задач между процессорами | |
| JP2613963B2 (ja) | データ入出力装置 | |
| Zeidler et al. | On the Development of Dedicated Hardware for Searching | |
| JPH05189979A (ja) | プライオリティ・エンコーダ |