JPH0259929A - マージソート回路 - Google Patents
マージソート回路Info
- Publication number
- JPH0259929A JPH0259929A JP21195188A JP21195188A JPH0259929A JP H0259929 A JPH0259929 A JP H0259929A JP 21195188 A JP21195188 A JP 21195188A JP 21195188 A JP21195188 A JP 21195188A JP H0259929 A JPH0259929 A JP H0259929A
- Authority
- JP
- Japan
- Prior art keywords
- data
- rams
- merge
- processing
- ram
- 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
- 230000009977 dual effect Effects 0.000 abstract description 7
- 230000001174 ascending effect Effects 0.000 description 3
- 238000010586 diagram Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000000034 method Methods 0.000 description 2
- 239000003795 chemical substances by application Substances 0.000 description 1
Landscapes
- Dram (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明はマージソート回路に関し、特にシリアルポート
付きＤ−ＲＡＭを使用したマージソート回路に関する。
付きＤ−ＲＡＭを使用したマージソート回路に関する。
〔従来の技術］
画像データの各画素構成要素のベクトルデータ等は種々
のデータ処理を必要とするが、初期処理としてソーティ
ングは重要な位置を占め、これを高速に処理することは
画像データ処理を高速化することにつながる。
のデータ処理を必要とするが、初期処理としてソーティ
ングは重要な位置を占め、これを高速に処理することは
画像データ処理を高速化することにつながる。
これらのソートあるいはマージソート処理は一般にソフ
トウェアで処理されている。
トウェアで処理されている。
しかし、ソフトウェア処理では処理時間がかかり、画像
データ等を高速処理する上での問題点となっている。ま
た、ハードウェアで処理する場合も、メモリへのアクセ
スがランダムポートを使用しているので、個々のデータ
毎にアドレスを制御する必要があり、高速化に一定の限
度がある。
データ等を高速処理する上での問題点となっている。ま
た、ハードウェアで処理する場合も、メモリへのアクセ
スがランダムポートを使用しているので、個々のデータ
毎にアドレスを制御する必要があり、高速化に一定の限
度がある。
本発明はこのような点に鑑みてなされたものであり、シ
リアルポート付きＤ−ＲＡＭを使用し、簡易な構成で、
高速処理可能なマージソート回路を提供することを目的
とする。
リアルポート付きＤ−ＲＡＭを使用し、簡易な構成で、
高速処理可能なマージソート回路を提供することを目的
とする。
本発明では上記課題を解決するために、画像のベクトル
データ等のデータをマージソートするマージソート回路
において、 マージソートすべきデータを格納する第１及び第２のシ
リアルポート付きＤ−ＲＡＭと、マージソートした結果
を格納する第３のシリアルポート付きＤ−ＲＡＭと、 前記第１及び第２のシリアルポート付きＤ−ＲＡＭの出
力データを比較する比較器と、前記比較器の出力によっ
て前記２個のシリアルポート付きＤ−ＲＡＭの出力を選
択して、前記第３のＤ−ＲＡＭに入力するセレクタと、
前記３個のＤ−ＲＡＭの人出力を制御するシーケンサと
、 を有することを特徴とするマージソート回路が、提供さ
れる。
データ等のデータをマージソートするマージソート回路
において、 マージソートすべきデータを格納する第１及び第２のシ
リアルポート付きＤ−ＲＡＭと、マージソートした結果
を格納する第３のシリアルポート付きＤ−ＲＡＭと、 前記第１及び第２のシリアルポート付きＤ−ＲＡＭの出
力データを比較する比較器と、前記比較器の出力によっ
て前記２個のシリアルポート付きＤ−ＲＡＭの出力を選
択して、前記第３のＤ−ＲＡＭに入力するセレクタと、
前記３個のＤ−ＲＡＭの人出力を制御するシーケンサと
、 を有することを特徴とするマージソート回路が、提供さ
れる。
マージソート処理されるデータは２個のシリアルポート
付きＤ−ＲＡＭに格納される。このシリアルポート出力
を比較器で比較し、マージソート処理を実行する。その
結果もシリアルポート付きのＤ−ＲＡＭのシリアルボー
トに入力される。
付きＤ−ＲＡＭに格納される。このシリアルポート出力
を比較器で比較し、マージソート処理を実行する。その
結果もシリアルポート付きのＤ−ＲＡＭのシリアルボー
トに入力される。
従って、データがシリアルボートからシリアルボートに
転送されるので、高速に転送が可能になり、処理速度が
向上する。これらのデータの転送処理はシーケンサによ
って制御される。
転送されるので、高速に転送が可能になり、処理速度が
向上する。これらのデータの転送処理はシーケンサによ
って制御される。
以下、本発明の一実施例を図面に基づいて説明する。
第１図に本発明の一実施例であるマージソート回路のブ
ロック図を示す。図において、■はシリアルボートとラ
ンダムポートのデュアルポートＤＲＡＭであり、一般の
市場で簡単に入手できる。
ロック図を示す。図において、■はシリアルボートとラ
ンダムポートのデュアルポートＤＲＡＭであり、一般の
市場で簡単に入手できる。
このＤ−ＲＡＭＩにはマージソートされたデータが格納
される。
される。
２はセレクタであり、Ｄ−ＲＡＭＩへの転送データの選
択を行う。３は比較器であり、マージソートすべき２個
のデータを比較し、°それによってセレクタ２の制御を
行う。
択を行う。３は比較器であり、マージソートすべき２個
のデータを比較し、°それによってセレクタ２の制御を
行う。
４及び５はマージソート処理を行うデータを格納するＤ
−ＲＡＭであり、Ｄ−ＲＡＭＩと同しデュアルボー）Ｒ
ＡＭである。６は要素カウンタであり、Ｄ−ＲＡＭ４及
び５のシリアルボートのシフト量をカウントする。７は
クロック発生器である。８はシーケンサであり、クロッ
ク発生器７のクロンク及び要素カウンタ６のカウント数
を受け、Ｄ−ＲＡＭＩ、４及び５のデータの転送を制御
する。尚、回ではデュアルポートＤ−ＲＡＭＩ、４及び
５のランダムポートは省略しである。
−ＲＡＭであり、Ｄ−ＲＡＭＩと同しデュアルボー）Ｒ
ＡＭである。６は要素カウンタであり、Ｄ−ＲＡＭ４及
び５のシリアルボートのシフト量をカウントする。７は
クロック発生器である。８はシーケンサであり、クロッ
ク発生器７のクロンク及び要素カウンタ６のカウント数
を受け、Ｄ−ＲＡＭＩ、４及び５のデータの転送を制御
する。尚、回ではデュアルポートＤ−ＲＡＭＩ、４及び
５のランダムポートは省略しである。
次に第１図のマージソート回路の動作を説明する。例と
して、２５６個のデータをデータの小さな順番にマージ
ソートする場合を説明する。
して、２５６個のデータをデータの小さな順番にマージ
ソートする場合を説明する。
（１） ２ ｉ−１番目と２１番目（ｉ＝１〜１２８）
の比較を行い、小さい方を先に並べる。これは第１図の
回路を使用せずにソフトウェアで処理する。このマージ
ソート処理したデータをＤ−ＲＡＭＩに格納する。
の比較を行い、小さい方を先に並べる。これは第１図の
回路を使用せずにソフトウェアで処理する。このマージ
ソート処理したデータをＤ−ＲＡＭＩに格納する。
（２）Ｄ−ＲＡＭＩの出力（シリアルポート出力）から
、４１−３．４１−２番目のデータをＤＲＡＭ４へ、４
１−１．４１番目のデータをＤ−ＲＡＭ５へ転送する。
、４１−３．４１−２番目のデータをＤＲＡＭ４へ、４
１−１．４１番目のデータをＤ−ＲＡＭ５へ転送する。
勿論これらのデータはＤ−ＲＡＭＩのシリアルボートか
ら出力され、ＤＲＡＭ４及び５のシリアルボートに入力
される。
ら出力され、ＤＲＡＭ４及び５のシリアルボートに入力
される。
シリアルレジスタ部がオーバフローしたら、新たなシリ
アルレジスタに転送される。
アルレジスタに転送される。
（３）Ｄ−ＲＡＭ４及び５に格納されたデータをシリア
ルボートから出力し、比較器で両者の２個づつの出力を
比較し、その値の小さい方をセレクタ２で選択して、Ｄ
−ＲＡＭＩに格納していく。
ルボートから出力し、比較器で両者の２個づつの出力を
比較し、その値の小さい方をセレクタ２で選択して、Ｄ
−ＲＡＭＩに格納していく。
この結果、４個のデータが小さい順序にマージソートさ
れた６４Ｍ１のデータがＤ−ＲＡＭＩに格納される。
れた６４Ｍ１のデータがＤ−ＲＡＭＩに格納される。
〔４〕さらに同様の処理を行い、８個のデータが小さい
順序にマージソートされた３２のデータがＤ−−ＲＡＭ
Ｉに格納される。
順序にマージソートされた３２のデータがＤ−−ＲＡＭ
Ｉに格納される。
〔５〕このような処理を８回繰り返せば、２５６個のデ
ータを完全に小さい順序にマージソートすることができ
る。
ータを完全に小さい順序にマージソートすることができ
る。
この結果、現在のＤ−ＲＡＭのシリアルポートの入出力
速度は、ｌサイクル３０ｎｓであり、ＤＲＡＭ４或いは
５へのセット回数が２５６回、Ｄ−ＲＡＭＩへのセット
回数が２５６回、マージソート処理が８回であるので、 （２５６＋２５６）ｘ８＝４０９６ ４０９６Ｘ３０＝１２２８８０ （ｎｓ）従って、約１
２３．ｉｓ程度で２５６個のデータがマージソートでき
ることになり、ソフトウェア等で処理している処理速度
に比べ相当高速化できることが分かる。
速度は、ｌサイクル３０ｎｓであり、ＤＲＡＭ４或いは
５へのセット回数が２５６回、Ｄ−ＲＡＭＩへのセット
回数が２５６回、マージソート処理が８回であるので、 （２５６＋２５６）ｘ８＝４０９６ ４０９６Ｘ３０＝１２２８８０ （ｎｓ）従って、約１
２３．ｉｓ程度で２５６個のデータがマージソートでき
ることになり、ソフトウェア等で処理している処理速度
に比べ相当高速化できることが分かる。
勿論上記のデータの数等は単なる例示であり、任意のデ
ータを処理することができる。また、ＤＲＡＭの個数も
処理すべきデータ量に応じて増やすことができる。
ータを処理することができる。また、ＤＲＡＭの個数も
処理すべきデータ量に応じて増やすことができる。
以上説明したように本発明では、シリアルポート付きの
Ｄ−ＲＡＭを使用して、データをマージソート処理する
ように構成したので、簡単な構成で、高速にマージソー
ト処理が可能になる。
Ｄ−ＲＡＭを使用して、データをマージソート処理する
ように構成したので、簡単な構成で、高速にマージソー
ト処理が可能になる。
第１図は本発明の一実施例であるマージソート回路のブ
ロック図である。 ト デュアルポートＲＡＭ セレクタ 比較器 ・・−デュアルポートＲＡＭ デュアルポートＲＡＭ −・−・−−−−−−一要素カウンタ クロンク発生器 シーケンサ 特許出願人 ファナック株式会社 代理人 弁理士 服部毅巖
ロック図である。 ト デュアルポートＲＡＭ セレクタ 比較器 ・・−デュアルポートＲＡＭ デュアルポートＲＡＭ −・−・−−−−−−一要素カウンタ クロンク発生器 シーケンサ 特許出願人 ファナック株式会社 代理人 弁理士 服部毅巖
Claims (2)
- （１）画像のベクトルデータ等のデータをマージソート
するマージソート回路において、マージソートすべきデ
ータを格納する第１及び第２のシリアルポート付きＤ−
ＲＡＭと、マージソートした結果を格納する第３のシリ
アルポート付きＤ−ＲＡＭと、 前記第１及び第２のシリアルポート付きＤ−ＲＡＭの出
力データを比較する比較器と、 前記比較器の出力によって前記２個のシリアルポート付
きＤ−ＲＡＭの出力を選択して、前記第３のＤ−ＲＡＭ
に入力するセレクタと、 前記３個のＤ−ＲＡＭの入出力を制御するシーケンサと
、 を有することを特徴とするマージソート回路。 - （２）前記第１、第２及び第３のＤ−ＲＡＭはランダム
ポートを有するデュアルポート付きＤ−ＲＡＭであるこ
とを特徴とする特許請求の範囲第１項記載のマージソー
ト回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP21195188A JPH0259929A (ja) | 1988-08-26 | 1988-08-26 | マージソート回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP21195188A JPH0259929A (ja) | 1988-08-26 | 1988-08-26 | マージソート回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0259929A true JPH0259929A (ja) | 1990-02-28 |
Family
ID=16614397
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP21195188A Pending JPH0259929A (ja) | 1988-08-26 | 1988-08-26 | マージソート回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0259929A (ja) |
-
1988
- 1988-08-26 JP JP21195188A patent/JPH0259929A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5504919A (en) | Sorter structure based on shiftable content memory | |
| US4068214A (en) | Asynchronous logic array | |
| USRE31287E (en) | Asynchronous logic array | |
| US4734877A (en) | Vector processing system | |
| JPH0259929A (ja) | マージソート回路 | |
| US4651301A (en) | Circuit arrangement for performing rapid sortation or selection according to rank | |
| JPH09128241A (ja) | ファジーロジックプロセッサの言語入力値の所属関数値に対する配列方法および装置 | |
| KR20000059423A (ko) | 다단 인터럽트 제어 장치 | |
| KR100218522B1 (ko) | 파이프 라이닝을 이용한 퍼지 제어기의 최소-최대처리회로 | |
| JP2976418B2 (ja) | パターンマッチング処理装置 | |
| JPH01273132A (ja) | マイクロプロセッサ | |
| JPS6187425A (ja) | インクリメンタル型エンコ−ダ用時分割カウント回路 | |
| JPS6346554A (ja) | メモリアクセス制御装置 | |
| KR0183347B1 (ko) | 에이티엠교환기의 출력포트 충돌 검출 회로 | |
| JP3331682B2 (ja) | 演算装置 | |
| JPH0580089A (ja) | タイマ装置 | |
| JPH04184535A (ja) | 並列演算装置 | |
| KR100257502B1 (ko) | 클럭없이동작하는쉬프트연산장치 | |
| JPH04330519A (ja) | 乗算回路 | |
| JPH03246651A (ja) | メモリコントロール回路 | |
| JPS63181030A (ja) | 特定デ−タパタ−ンにおける演算高速化システム | |
| JPS63303424A (ja) | 演算回路 | |
| JPH01280918A (ja) | インターバルタイマ | |
| JPH03203891A (ja) | メモリ制御装置 | |
| JPS623371A (ja) | ベクトルデ−タ処理装置 |