JPH04112319A - データ格納方法と先入れ先だし装置 - Google Patents
データ格納方法と先入れ先だし装置Info
- Publication number
- JPH04112319A JPH04112319A JP2233539A JP23353990A JPH04112319A JP H04112319 A JPH04112319 A JP H04112319A JP 2233539 A JP2233539 A JP 2233539A JP 23353990 A JP23353990 A JP 23353990A JP H04112319 A JPH04112319 A JP H04112319A
- Authority
- JP
- Japan
- Prior art keywords
- output
- data
- section
- value
- tag
- 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
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multi Processors (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明（よ 電子計算機での数値演算時のデータ格納方
法と、電子計算他 特に並列処理システムでのデータ格
納及び転送時に重要な役割を有する先入れ先だし装置に
関連すム 従来の技術 従来のデータ格納方法としてζよ 例えば数値計算プロ
グラミング（森正久 合波書店） Ｐ９８−１０１に示
されていも 第７図はこの従来のデータ格納方法を示し
たものである。メモリ領域１の中にデータ位置を示す配
列（ａ）とデータ値を示す配列（ｂ）を設ける。これは
特定の値の出現頻度が高い場合のデータ圧縮を目的と
したもので、本例では データ値゛０−に注目する。−
０゛が出現した場合これをデータ値として格納せず、−
〇−以外のデータについて出現順番と共に格納する。デ
ータ列３．８．０．０．０．００、０．１．３．０．０
．０．０．６について述べれは （ａ）に゛０′以外の
データ位置１，２，９，１０．１５． （ｂ）に対応
するデータ値３，８，１，３．６が順次格納される。
法と、電子計算他 特に並列処理システムでのデータ格
納及び転送時に重要な役割を有する先入れ先だし装置に
関連すム 従来の技術 従来のデータ格納方法としてζよ 例えば数値計算プロ
グラミング（森正久 合波書店） Ｐ９８−１０１に示
されていも 第７図はこの従来のデータ格納方法を示し
たものである。メモリ領域１の中にデータ位置を示す配
列（ａ）とデータ値を示す配列（ｂ）を設ける。これは
特定の値の出現頻度が高い場合のデータ圧縮を目的と
したもので、本例では データ値゛０−に注目する。−
０゛が出現した場合これをデータ値として格納せず、−
〇−以外のデータについて出現順番と共に格納する。デ
ータ列３．８．０．０．０．００、０．１．３．０．０
．０．０．６について述べれは （ａ）に゛０′以外の
データ位置１，２，９，１０．１５． （ｂ）に対応
するデータ値３，８，１，３．６が順次格納される。
また従来の先入れ先だし装置として（よ 第８図に示し
たものが一般的である。書き込み要求が発生した場合、
書き込み制御部１５ｃはライトポインタ３７の示すアド
レスに書き込み制御２６を出力してデータ入力１０ｃを
メモリ部３６に書き込へ ライトポインタ３７を進めも
読みだし要求が発生した場合は読みだし制御部１６ｃ
はリードポインタ３８の示すアドレスに読みだし制御２
７を出力してメモリ部３６よりデータ出力１９ｃに読み
だし リードポインタ３８を進める。
たものが一般的である。書き込み要求が発生した場合、
書き込み制御部１５ｃはライトポインタ３７の示すアド
レスに書き込み制御２６を出力してデータ入力１０ｃを
メモリ部３６に書き込へ ライトポインタ３７を進めも
読みだし要求が発生した場合は読みだし制御部１６ｃ
はリードポインタ３８の示すアドレスに読みだし制御２
７を出力してメモリ部３６よりデータ出力１９ｃに読み
だし リードポインタ３８を進める。
発明が解決しようとする課題
しかしながぺ 上記の様なデータ格納方法で（よ次の３
つの課題がある。
つの課題がある。
２２、ニー０−成分が少ない時、データ圧縮効率が低下
する。場合によっては データ位置を示す配列が大きく
なりデータ量が増える場合がある。
する。場合によっては データ位置を示す配列が大きく
なりデータ量が増える場合がある。
第２にデータ位置とデータ値両方のデータ構造を作成す
る必要が有り、これがオーバーヘッドとなる。そして、
このオーバーヘッドを〕λ−ドウエアで実現しようと
した場合、ハード量はかなり大きなものとなる。
る必要が有り、これがオーバーヘッドとなる。そして、
このオーバーヘッドを〕λ−ドウエアで実現しようと
した場合、ハード量はかなり大きなものとなる。
第３に ２種類以上のデータを削減することが出来なｔ
兎 また 上記の様な先入れ先だし装置で（よ 容量以上の
データを格納することは出来ない。当然前記したデータ
圧縮を行なうことも出来なしも本発明はかかる点に鑑へ
常に高いデータ圧縮効率を実現するデータ圧縮方法と
、これを高速にサポートする先入れ先だし装置を提供す
ることを目的とする。
兎 また 上記の様な先入れ先だし装置で（よ 容量以上の
データを格納することは出来ない。当然前記したデータ
圧縮を行なうことも出来なしも本発明はかかる点に鑑へ
常に高いデータ圧縮効率を実現するデータ圧縮方法と
、これを高速にサポートする先入れ先だし装置を提供す
ることを目的とする。
課題を解決するための手段
本発明ζよ 少なくとも２種類以上の値を格納できるタ
グ部と、データ部を有し 前記タグ部が第一の値の隊 前記データ部にデータ値を
格納し 前記タグ部が第一の値以外の時、前記タグ部の値はそれ
ぞれ特定のデータ値を示し 前記データ部にデータの個
数を格納することを特徴とするデータ格納方法である。
グ部と、データ部を有し 前記タグ部が第一の値の隊 前記データ部にデータ値を
格納し 前記タグ部が第一の値以外の時、前記タグ部の値はそれ
ぞれ特定のデータ値を示し 前記データ部にデータの個
数を格納することを特徴とするデータ格納方法である。
また本発明は データ入力と１つまたは複数の特定の値
を格納したレジスタの出力を比較する１つまたは複数の
比較器と、前記比較器が連続して一致を示した時その回
数をカウントするアップカウンタと、前記アップカウン
タ出力と前記データ入力を選択する入力セレクタを備え
た入力変換部と、 メモリ部内の書き込み位置を示すライトポインタをｍえ 書き込み要求が発生した場合、前記比較結果が不一致の
場合に前記入力セレクタを前記データ入力を選択する方
向に定め、 第一の値をタグ値として出力すると共＆ミ
メモリ部への書き込みを指示してライトポインタを進
め、 また前記比較結果が第Ｎ （Ｎは２以上の整数）のレジ
スタ出力と一致の場合に前記入力セレクタを前記アップ
カウンタ出力を選択する方向に定数第Ｎの値をタグ値と
して出力すると共に 一致の連続が途切れた力＼ また
はデータ入力が途切れた時点でメモリ部への書き込みを
指示してライトポインタを進め、 同時に前記アップカ
ウンタをリセットする書き込み制御部と、 前記入力セレクタ出力を格納するデータ部と、前記タグ
値を格納するタグ部を備えたメモリ部と、前記データ部
出力をカウントダウンするダウンカウンタと、前記デー
タ部出力と前記レジスタ出力を選択する出力セレクタを
備えた出力変換部と、常に読みだし位置を示すリードポ
インタを備え読みだし要求が発生した場合へ 前記メモ
リ部のタグ部出力が第一の値の時、前記出力セレクタを
前記データ部出力を選択する方向に定めて、データ出力
を行った後にリードポインタを進め、また前記メモリ部
のタグ部出力が第Ｎの値の時、前記出力セレクタを前記
第Ｎのレジスタ出力を選択する方向に定めて前記第Ｎの
レジスタ出力を出力し続け、また前記データ部出力を前
記ダウンカウンタにロードし その後読みだし要求が発
生する度に前記ダウンカウンタをカウントダウンし前記
ダウンカウンタ出力が０になった時点でリードポインタ
を進める読みだし制御回路を具備する先入れ先だし装置
である。
を格納したレジスタの出力を比較する１つまたは複数の
比較器と、前記比較器が連続して一致を示した時その回
数をカウントするアップカウンタと、前記アップカウン
タ出力と前記データ入力を選択する入力セレクタを備え
た入力変換部と、 メモリ部内の書き込み位置を示すライトポインタをｍえ 書き込み要求が発生した場合、前記比較結果が不一致の
場合に前記入力セレクタを前記データ入力を選択する方
向に定め、 第一の値をタグ値として出力すると共＆ミ
メモリ部への書き込みを指示してライトポインタを進
め、 また前記比較結果が第Ｎ （Ｎは２以上の整数）のレジ
スタ出力と一致の場合に前記入力セレクタを前記アップ
カウンタ出力を選択する方向に定数第Ｎの値をタグ値と
して出力すると共に 一致の連続が途切れた力＼ また
はデータ入力が途切れた時点でメモリ部への書き込みを
指示してライトポインタを進め、 同時に前記アップカ
ウンタをリセットする書き込み制御部と、 前記入力セレクタ出力を格納するデータ部と、前記タグ
値を格納するタグ部を備えたメモリ部と、前記データ部
出力をカウントダウンするダウンカウンタと、前記デー
タ部出力と前記レジスタ出力を選択する出力セレクタを
備えた出力変換部と、常に読みだし位置を示すリードポ
インタを備え読みだし要求が発生した場合へ 前記メモ
リ部のタグ部出力が第一の値の時、前記出力セレクタを
前記データ部出力を選択する方向に定めて、データ出力
を行った後にリードポインタを進め、また前記メモリ部
のタグ部出力が第Ｎの値の時、前記出力セレクタを前記
第Ｎのレジスタ出力を選択する方向に定めて前記第Ｎの
レジスタ出力を出力し続け、また前記データ部出力を前
記ダウンカウンタにロードし その後読みだし要求が発
生する度に前記ダウンカウンタをカウントダウンし前記
ダウンカウンタ出力が０になった時点でリードポインタ
を進める読みだし制御回路を具備する先入れ先だし装置
である。
作用
本発明におけるデータ格納方法（上 前記した構成によ
り、特定のデータ値が連続した場合、タグ部にその旨を
示す値を格納して、データ部に連続する個数を格納する
。このた八 特定の値の出現頻度の高いデータを効率的
に圧縮することが可能となる。
り、特定のデータ値が連続した場合、タグ部にその旨を
示す値を格納して、データ部に連続する個数を格納する
。このた八 特定の値の出現頻度の高いデータを効率的
に圧縮することが可能となる。
また 本発明における先入れ先だし装置は 前記した構
成により、書き込み時、特定のデータ値に関しては デ
ータ値に代えて連続する個数を格納し タグ部にその旨
を示す値を格納する（データ圧縮）。また 読みだし時
、連続する個数が格納された領域を読む場合には タグ
部情報よりデータ値を復元して個数分読みだす（データ
復号）。
成により、書き込み時、特定のデータ値に関しては デ
ータ値に代えて連続する個数を格納し タグ部にその旨
を示す値を格納する（データ圧縮）。また 読みだし時
、連続する個数が格納された領域を読む場合には タグ
部情報よりデータ値を復元して個数分読みだす（データ
復号）。
これにより、容量以上のデータ格納が可能となる。
また 同先入れ先だし装置において、書き込み側はデー
タ圧縮機構を設けたままで、読みだし側をタグ部及びデ
ータ部をそのまま読みだす様にすれば データ圧縮装置
（符号化先入れ先だし装置）となる。
タ圧縮機構を設けたままで、読みだし側をタグ部及びデ
ータ部をそのまま読みだす様にすれば データ圧縮装置
（符号化先入れ先だし装置）となる。
さらく 同先入れ先だし装置において、読みたし側はデ
ータ複合機構を設けたままで、書き込み側をタグ部及び
データ部をそのまま書き込む様にすれば データ複合装
置（復号化先入れ先だし装置）となる。
ータ複合機構を設けたままで、書き込み側をタグ部及び
データ部をそのまま書き込む様にすれば データ複合装
置（復号化先入れ先だし装置）となる。
実施例
第１図は本発明の実施例におけるデータ格納方法の構成
図である。
図である。
同図（ａ）に示す様へ メモリ領域１７１ １ビツトの
タグ部２及びデータ部３で構成されも タグ部２が一〇
−〇時テータ部３にはデータ値力（タグ部２が１の時は
データ部３には個数が格納されも データ列３、８．０
．０．０． Ｏ，Ｏ，０，１，３，０，０，０，０，６
を格納する様子を同図（ｂ）に示す。タグ部／テータ部
と表現すると、トップより０／３． Ｏ／８．１／６．
Ｏ／１．０／３． ｌ／４． Ｏ／６となり、１５ワ
ードのデータが７ワードに圧縮されたことになム 第２図は本発明の実施例における先入れ先だし装置の構
成図である。
タグ部２及びデータ部３で構成されも タグ部２が一〇
−〇時テータ部３にはデータ値力（タグ部２が１の時は
データ部３には個数が格納されも データ列３、８．０
．０．０． Ｏ，Ｏ，０，１，３，０，０，０，０，６
を格納する様子を同図（ｂ）に示す。タグ部／テータ部
と表現すると、トップより０／３． Ｏ／８．１／６．
Ｏ／１．０／３． ｌ／４． Ｏ／６となり、１５ワ
ードのデータが７ワードに圧縮されたことになム 第２図は本発明の実施例における先入れ先だし装置の構
成図である。
先入れ先だし装置（よ レジスタ１２．比較器１１．ア
ップカウンタ１３．入力セレクタ１４で構成される部分
を入力変換部４０と、メモリ部３６と、書き込み制御部
１５ａと、読み出し制御部１６ａと、出力セレクタ１７
、ダウンカウンタ１８で構成される部分を出力変換器４
１とによって構成されも 使用に先だって、 レジスタ
１２に特定の値を設定す４ この値に等しいデータが入
力された隊 個数がメモリ部３６に格納されるので、出
現頻度の高い値を設定する。数値演見 例えば疎行列を
ガウス消去で解く場合等で（よ−０゛の出現頻度が高い
ので′０゛を設定する。またアップカウンタ１３．ダウ
ンカウンタ１＆ ライトポインタ３７、リードポインタ
３８の初期化を行なう。
ップカウンタ１３．入力セレクタ１４で構成される部分
を入力変換部４０と、メモリ部３６と、書き込み制御部
１５ａと、読み出し制御部１６ａと、出力セレクタ１７
、ダウンカウンタ１８で構成される部分を出力変換器４
１とによって構成されも 使用に先だって、 レジスタ
１２に特定の値を設定す４ この値に等しいデータが入
力された隊 個数がメモリ部３６に格納されるので、出
現頻度の高い値を設定する。数値演見 例えば疎行列を
ガウス消去で解く場合等で（よ−０゛の出現頻度が高い
ので′０゛を設定する。またアップカウンタ１３．ダウ
ンカウンタ１＆ ライトポインタ３７、リードポインタ
３８の初期化を行なう。
な耘 以下の実施例で（よ タグ部２が′０゛の時デー
タ部３にはデータ値力（タグ部２が１の時はデータ部３
には個数が格納されるものとする。
タ部３にはデータ値力（タグ部２が１の時はデータ部３
には個数が格納されるものとする。
まず、書き込み動作を説明する。
ライトポインタ３７はメモリ部３６内の書き込み位置を
示す。
示す。
書き込み要求が発生した場合、比較器１１でデータ入力
１０ａとレジスタ出力２０を比較する。
１０ａとレジスタ出力２０を比較する。
比較結果２１が不一致を示す場合、書き込み制御部１５
ａζ瓜 入力セレクタ１４に対して、データ入力１０ａ
を選択する方向に定める様に入力セレクト２４を送出し
タグ値２５として′０′を出力する。また 入力セレ
クタ１４の出力であるデータ部入力２９（この場合はデ
ータ入力）を、メモリ部３６内のライトポインタ３７の
示す位置へ書き込み（書き込み制御２６を送出）、その
後ライトポインタ３７を進める。
ａζ瓜 入力セレクタ１４に対して、データ入力１０ａ
を選択する方向に定める様に入力セレクト２４を送出し
タグ値２５として′０′を出力する。また 入力セレ
クタ１４の出力であるデータ部入力２９（この場合はデ
ータ入力）を、メモリ部３６内のライトポインタ３７の
示す位置へ書き込み（書き込み制御２６を送出）、その
後ライトポインタ３７を進める。
比較結果２１が一致を示す場合、書き込み制御部１５ａ
ｉ＆ 入力セレクタ１４に対して、アップカウンタ出
力３４を選択する方向に定める様に入力セレクト２４を
送出し タグ値２５として一１′を出力する。また書き
込み要求時に比較結果２１が発生する度にカウントアッ
プ２３を送出してアップカウンタ１３を増加し 連続回
数を数える。そして、書き込み要求が途絶えた力＼ 比
較結果２１か不一致を示した時点で、入力セレクタ１４
の出力であるデータ部入力２９（この場合は連続個数）
を、メモリ部３６内のライトポインタ３７の示す位置へ
書き込む（書き込み制御２６を送出）。その後、ライト
ポインタ３７を進数 同時にリセット２２を送出して、
アップカウンタ１３をリセットする。これらにより、デ
ータが圧縮された形でメモリ部３６に格納されも 続いて、読みだし動作を説明する。
ｉ＆ 入力セレクタ１４に対して、アップカウンタ出
力３４を選択する方向に定める様に入力セレクト２４を
送出し タグ値２５として一１′を出力する。また書き
込み要求時に比較結果２１が発生する度にカウントアッ
プ２３を送出してアップカウンタ１３を増加し 連続回
数を数える。そして、書き込み要求が途絶えた力＼ 比
較結果２１か不一致を示した時点で、入力セレクタ１４
の出力であるデータ部入力２９（この場合は連続個数）
を、メモリ部３６内のライトポインタ３７の示す位置へ
書き込む（書き込み制御２６を送出）。その後、ライト
ポインタ３７を進数 同時にリセット２２を送出して、
アップカウンタ１３をリセットする。これらにより、デ
ータが圧縮された形でメモリ部３６に格納されも 続いて、読みだし動作を説明する。
リードポインタ３８はメモリ部３６内の読みだし位置を
示し 常にリードポインタ３８の示すワードがタグ出力
２８及びデータ部出力３ｏとして出力されていも 読みだし要求が発生した場合、読みだし制御２７でタグ
出力２８を調べる。
示し 常にリードポインタ３８の示すワードがタグ出力
２８及びデータ部出力３ｏとして出力されていも 読みだし要求が発生した場合、読みだし制御２７でタグ
出力２８を調べる。
読みだし制御部１６ ａ Ｉｔ タグ出力２８が−０
−の時、出力セレクタ１７に対してデータ部出力３ｏを
選択する方向に定めるように出力セレクト３１を送出し
データ出力１９ａに出力すム その後、 リードポイン
タ３８を進める。
−の時、出力セレクタ１７に対してデータ部出力３ｏを
選択する方向に定めるように出力セレクト３１を送出し
データ出力１９ａに出力すム その後、 リードポイン
タ３８を進める。
また 読みだし制御部１６ ａ ’１１ タグ出力２
８が一１−の昧 即ちタグ部２に′１゛が格納されてい
るワードをリードポインタ３８が指した時点で、出力セ
レクタ１７に対してレジスタ出力２０を選択する方向に
定めるように出力セレクト３１を送出し データ出力１
９ａに出力する。また同時に読み出し制御部１６ａｌ；
＆ロード３５をアサートしてデータ部出力３０をダウン
カウンタ１８にロードする。その後読みだし要求が発生
する度にダウンカウンタ１８をカウントダウン３２によ
りカウントダウンし ダウンカウンタ出力３３が０“に
なった時点でリードポインタ３８を進めもこれらにより
、圧縮されたデータかもとの形に復元してメモリ部３６
より読みだされも 以上により、容量以上のデータが先入れ先だし装置に格
納でき、ハードウェアの削減が実現できも 第３図は本発明の実施例における符号化先入れ先だし装
置の構成医 第５図（ａ）は同実施例におけるタイミン
グ図であム 本実施例（ム 第２図に示した先入れ先だし装置の書き
込み側の入力変換部４０を設けたままて 読みだし側を
タグ部２及びデータ部３をそのまま読みだす様にしたも
のである。書き込み側は第２図の説明と同じなので省略
すも 読みだし要求が発生した場合、読みだし制御部１
６ｂは読みだし制御２７を送出して、 リードポインタ
３８の示すタグ部２及びデータ部３を読みだすと共にリ
ードポインタ３８を進めも 第５図（ａ）に示す様にデータ入力１０ａが３．５．０
．０゜０、１．４．０．０．２．６の場合、データ出力
１９ｂはタグ／データと表記すると、０／３．０１５．
Ｉ／３．０／Ｉ、 ０／４．１／２． Ｏ／２、０／
６となム 第４図は本発明の実施例における復号化先入れ先だし装
置の構成医 第５図（ｂ）は同実施例におけるタイミン
グ図であも 本実施例は 第２図に示した先入れ先だし装置の読みだ
し側の出力変換部４１を設けたままで、書き込み側をタ
グ部２及びデータ部３をそのまま書き込む様にしたもの
であも ただし レジスタ１２は別途膜↓す、出力変換
部４１内の出力セレクタ１７の一方の入力に接続すム
読みだし側は第２図の説明と同じなので省略すも 書き
込み要求が発生した場合 書き込み制御部１５ｂは書き
込み制御２６を送出して、ライトポインタ３７の示すタ
グ部２及びデータ部３にデータ入力１０ｂを書き込むと
共にライトポインタ３７を進めも 第５図（ｂ）に示す様にデータ入力１０ｂがタグ／デー
タと表記しテＯ／３．０１５．１／３． Ｏ／１． Ｏ
／４．１／２． Ｏ／２． Ｏ／６の場合 データ出力
１９ａハ３．５．０． Ｏ，０，１，４，０，０，２゜
６となａ 第６図は 本発明の実施例における先入れ先だし装置を
使用した並列処理システムの構成図であ本実施例は８つ
のデータ入力１０ａ−１〜１０ａ−＆ ８つのデータ
出力１９ａ−１〜１９ａ−８を多段結合網４６（ハイパ
ーキューブ結合）により結合したものであａデータ入力
１０ａ−１からデータ出力１９ａ−１へのデータの流れ
は次のようになム 符号化先入れ先だし装置５０−１に
よりデータ圧縮されたのち交換スイッチ４５ａ、 ４
５ｈ、 ４５ｃを直通し 復号化先入れ先だし装置５
１−１で復元されも ここで同時にデータ入力１０ａ６
からデータ出力１９ａ−１への転送要求かあった場合、
これは交換スイッチ４５ｇで交＆ ４５ｈで直通４５
ｃで交換となも 即板 交換スイッチ４５ｃで衝突が発
生する。一般に並列処理システムでは多量のデータ転送
が発生するので、ここでの衝突は性能低下に大きく関連
すム 本発明で（よ 多段結合網４６内のデータ転送量を圧縮
しており、衝突が発生しても各交換スイッチで処理すべ
きデータ量は少な賎 ここで、 もとの多量のデータは
多くの場合同一要素（通常は０−）を多く含むので、圧
縮効率も高（ｔ 従って、性能低下を大幅に救済可能で
あり、結合網の転送性能を実質的に向上できも また データ圧練 復号は小規模なハードウェアの追加
で実現可能となるので、高速なシステムが構成できも なおここで示したいくつかの実施例で（よ タグ部が１
ビツトの場合について述べた方丈 これは２ビツト以上
でもよＬ％ この場合は例えは第２図で比較器１１と
レジスタ１２を複数組用意し 入力セレクタ１４．Ｉｉ
力セレクタ１７を多入力とすれはよい。
８が一１−の昧 即ちタグ部２に′１゛が格納されてい
るワードをリードポインタ３８が指した時点で、出力セ
レクタ１７に対してレジスタ出力２０を選択する方向に
定めるように出力セレクト３１を送出し データ出力１
９ａに出力する。また同時に読み出し制御部１６ａｌ；
＆ロード３５をアサートしてデータ部出力３０をダウン
カウンタ１８にロードする。その後読みだし要求が発生
する度にダウンカウンタ１８をカウントダウン３２によ
りカウントダウンし ダウンカウンタ出力３３が０“に
なった時点でリードポインタ３８を進めもこれらにより
、圧縮されたデータかもとの形に復元してメモリ部３６
より読みだされも 以上により、容量以上のデータが先入れ先だし装置に格
納でき、ハードウェアの削減が実現できも 第３図は本発明の実施例における符号化先入れ先だし装
置の構成医 第５図（ａ）は同実施例におけるタイミン
グ図であム 本実施例（ム 第２図に示した先入れ先だし装置の書き
込み側の入力変換部４０を設けたままて 読みだし側を
タグ部２及びデータ部３をそのまま読みだす様にしたも
のである。書き込み側は第２図の説明と同じなので省略
すも 読みだし要求が発生した場合、読みだし制御部１
６ｂは読みだし制御２７を送出して、 リードポインタ
３８の示すタグ部２及びデータ部３を読みだすと共にリ
ードポインタ３８を進めも 第５図（ａ）に示す様にデータ入力１０ａが３．５．０
．０゜０、１．４．０．０．２．６の場合、データ出力
１９ｂはタグ／データと表記すると、０／３．０１５．
Ｉ／３．０／Ｉ、 ０／４．１／２． Ｏ／２、０／
６となム 第４図は本発明の実施例における復号化先入れ先だし装
置の構成医 第５図（ｂ）は同実施例におけるタイミン
グ図であも 本実施例は 第２図に示した先入れ先だし装置の読みだ
し側の出力変換部４１を設けたままで、書き込み側をタ
グ部２及びデータ部３をそのまま書き込む様にしたもの
であも ただし レジスタ１２は別途膜↓す、出力変換
部４１内の出力セレクタ１７の一方の入力に接続すム
読みだし側は第２図の説明と同じなので省略すも 書き
込み要求が発生した場合 書き込み制御部１５ｂは書き
込み制御２６を送出して、ライトポインタ３７の示すタ
グ部２及びデータ部３にデータ入力１０ｂを書き込むと
共にライトポインタ３７を進めも 第５図（ｂ）に示す様にデータ入力１０ｂがタグ／デー
タと表記しテＯ／３．０１５．１／３． Ｏ／１． Ｏ
／４．１／２． Ｏ／２． Ｏ／６の場合 データ出力
１９ａハ３．５．０． Ｏ，０，１，４，０，０，２゜
６となａ 第６図は 本発明の実施例における先入れ先だし装置を
使用した並列処理システムの構成図であ本実施例は８つ
のデータ入力１０ａ−１〜１０ａ−＆ ８つのデータ
出力１９ａ−１〜１９ａ−８を多段結合網４６（ハイパ
ーキューブ結合）により結合したものであａデータ入力
１０ａ−１からデータ出力１９ａ−１へのデータの流れ
は次のようになム 符号化先入れ先だし装置５０−１に
よりデータ圧縮されたのち交換スイッチ４５ａ、 ４
５ｈ、 ４５ｃを直通し 復号化先入れ先だし装置５
１−１で復元されも ここで同時にデータ入力１０ａ６
からデータ出力１９ａ−１への転送要求かあった場合、
これは交換スイッチ４５ｇで交＆ ４５ｈで直通４５
ｃで交換となも 即板 交換スイッチ４５ｃで衝突が発
生する。一般に並列処理システムでは多量のデータ転送
が発生するので、ここでの衝突は性能低下に大きく関連
すム 本発明で（よ 多段結合網４６内のデータ転送量を圧縮
しており、衝突が発生しても各交換スイッチで処理すべ
きデータ量は少な賎 ここで、 もとの多量のデータは
多くの場合同一要素（通常は０−）を多く含むので、圧
縮効率も高（ｔ 従って、性能低下を大幅に救済可能で
あり、結合網の転送性能を実質的に向上できも また データ圧練 復号は小規模なハードウェアの追加
で実現可能となるので、高速なシステムが構成できも なおここで示したいくつかの実施例で（よ タグ部が１
ビツトの場合について述べた方丈 これは２ビツト以上
でもよＬ％ この場合は例えは第２図で比較器１１と
レジスタ１２を複数組用意し 入力セレクタ１４．Ｉｉ
力セレクタ１７を多入力とすれはよい。
これにより、圧縮対象が複数種類に対応可能とな発明の
効果 以上述べてきたように 本発明におけるデータ格納方法
先入れ先だし装置はデータ数をデータ領域に格納する
ことで、常に高いデータ圧縮か可能となり、格納領域を
有効に活用できもまた 本発明の符号化及び復号化先入
れ先だし装置を用いて並列処理システムを構成すること
で結合網内のデータ転送効率を実質的に向上できる。
効果 以上述べてきたように 本発明におけるデータ格納方法
先入れ先だし装置はデータ数をデータ領域に格納する
ことで、常に高いデータ圧縮か可能となり、格納領域を
有効に活用できもまた 本発明の符号化及び復号化先入
れ先だし装置を用いて並列処理システムを構成すること
で結合網内のデータ転送効率を実質的に向上できる。
従って今後大きな発展が期待され ますます多量データ
を扱うことになる並列処理システム等で非常に有用なも
のであム
を扱うことになる並列処理システム等で非常に有用なも
のであム
第１図は本発明の実施例におけるデータ格納方法の説明
医 第２図は本発明の実施例における先入れ先だし装置
の構成図 第３図は本発明の実施例における符号化先入
れ先だし装置の構成図 第４図は本発明の実施例におけ
る復号化先入れ先だし装置の構成図 第５図（ａ）は第
３図の実施例におけるタイミングは 第５図（ｂ）は第
４図の実施例におけるタイミング＠ 第６図は本発明の
実施例における先入れ先だし装置を使用した並列処理シ
ステムの構成図 第７図は従来のデータ格納方′法を示
した医 第８図は従来の先入れ先だし装置の構成図であ
も １・・・メモリ領域 ２・・・タグ黴 ３・・・データ
服１０ａ、 １０ｂ、 １０ｃ、 １０ａ−１〜１０ａ
−８−−−データ入九 １１・・・比較器１２・・・レ
ジス久 １３・・・アップカラン久１４・・・入力セレ
クタ １５ａ、 １５ｂ、 １５ｃ・・・書き込み制御
訊１６ａ、１６ｂ、１６ｃ・・・読みだし制御諏１７・
・・出力セレク久 １８・・・ダウンカラン久 １９ａ
、 １９ｂ、 １９ｃ、 １９ａ−１〜１９ａ−８・・
・データ出九４０・・・入力変換数４１・・・出力変換
拡４５ａ〜４５１・・・交換スイッチ、４６・・・多段
結合諷５０，５０−１〜５０−８・・・符号化先入れ先
だし装［５１，５１１〜５１−８・・・復号化先入れ先
だし装代理人の氏名 弁理士 小鍜治 明 ほか２名第 図 第 図 （α） Ｑａ 第 図 第 図 （ＱＪ 第 図 テ タコ８００００００Ｉ３００００６ 第 図
医 第２図は本発明の実施例における先入れ先だし装置
の構成図 第３図は本発明の実施例における符号化先入
れ先だし装置の構成図 第４図は本発明の実施例におけ
る復号化先入れ先だし装置の構成図 第５図（ａ）は第
３図の実施例におけるタイミングは 第５図（ｂ）は第
４図の実施例におけるタイミング＠ 第６図は本発明の
実施例における先入れ先だし装置を使用した並列処理シ
ステムの構成図 第７図は従来のデータ格納方′法を示
した医 第８図は従来の先入れ先だし装置の構成図であ
も １・・・メモリ領域 ２・・・タグ黴 ３・・・データ
服１０ａ、 １０ｂ、 １０ｃ、 １０ａ−１〜１０ａ
−８−−−データ入九 １１・・・比較器１２・・・レ
ジス久 １３・・・アップカラン久１４・・・入力セレ
クタ １５ａ、 １５ｂ、 １５ｃ・・・書き込み制御
訊１６ａ、１６ｂ、１６ｃ・・・読みだし制御諏１７・
・・出力セレク久 １８・・・ダウンカラン久 １９ａ
、 １９ｂ、 １９ｃ、 １９ａ−１〜１９ａ−８・・
・データ出九４０・・・入力変換数４１・・・出力変換
拡４５ａ〜４５１・・・交換スイッチ、４６・・・多段
結合諷５０，５０−１〜５０−８・・・符号化先入れ先
だし装［５１，５１１〜５１−８・・・復号化先入れ先
だし装代理人の氏名 弁理士 小鍜治 明 ほか２名第 図 第 図 （α） Ｑａ 第 図 第 図 （ＱＪ 第 図 テ タコ８００００００Ｉ３００００６ 第 図
Claims (4)
- （１）少なくとも２種類以上の値を格納できるタグ部と
、データ部とを有し、 前記タグ部が第一の値の時、前記データ部にデータ値を
格納し、 前記タグ部が第一の値以外の時、前記タグ部の値はそれ
ぞれ特定のデータ値を示し、前記データ部に前記特定の
データの連続する個数を格納することを特徴とするデー
タ格納方法。 - （２）データ入力と１つまたは複数の特定の値を格納し
たレジスタの出力を比較する１つまたは複数の比較器と
、前記比較器が連続して一致を示した時その回数をカウ
ントするアップカウンタと、前記アップカウンタからの
アップカウンタ出力と前記データ入力を選択する入力セ
レクタを備えた入力変換部と、 メモリ部内の書き込み位置を示すライトポインタを備え
書き込み要求が発生した場合、前記比較結果が不一致の
場合に前記入力セレクタを前記データ入力を選択する方
向に定め、第一の値をタグ値として出力すると共に、メ
モリ部への書き込みを指示してライトポインタを進め、 また前記比較結果が第Ｎ（Ｎは２以上の整数）のレジス
タ出力と一致の場合に前記入力セレクタを前記アップカ
ウンタ出力を選択する方向に定め、第Ｎの値をタグ値と
して出力すると共に、一致の連続が途切れたか、または
データ入力が途切れた時点でメモリ部への書き込みを指
示してライトポインタを進め、同時に前記アップカウン
タをリセットする書き込み制御部と、 前記入力セレクタ出力を格納するデータ部と、前記タグ
値を格納するタグ部を備えたメモリ部と、前記データ部
出力をカウントダウンするダウンカウンタと、前記デー
タ部出力と前記レジスタ出力を選択する出力セレクタを
備えた出力変換部と、常に読みだし位置を示すリードポ
インタを備え、読みだし要求が発生した場合に、前記メ
モリ部のタグ部出力が第一の値の時、前記出力セレクタ
を前記データ部出力を選択する方向に定めて、データ出
力を行った後にリードポインタを進め、また前記メモリ
部のタグ部出力が第Ｎの値の時、前記出力セレクタを前
記第Ｎのレジスタ出力を選択する方向に定めて前記第Ｎ
のレジスタ出力を出力し続け、また前記データ部出力を
前記ダウンカウンタにロードし、その後読みだし要求が
発生する度に前記ダウンカウンタをカウントダウンし、
前記ダウンカウンタ出力が０になった時点でリードポイ
ンタを進める読みだし制御回路を具備する先入れ先だし
装置。 - （３）データ入力と１つまたは複数の特定の値を格納し
たレジスタの出力を比較する１つまたは複数の比較器と
、前記比較器が連続して一致を示した時その回数をカウ
ントするアップカウンタと、前記アップカウンタ出力と
前記データ入力を選択する入力セレクタを備えた入力変
換部と、 メモリ部内の書き込み位置を示すライトポインタを備え
書き込み要求が発生した場合、前記比較結果が不一致の
場合に前記入力セレクタを前記データ入力を選択する方
向に定め、第一の値をタグ値として出力すると共に、メ
モリ部への書き込みを指示してライトポインタを進め、 また前記比較結果が第Ｎ（Ｎは２以上の整数）のレジス
タ出力と一致の場合に前記入力セレクタを前記アップカ
ウンタ出力を選択する方向に定め、第Ｎの値をタグ値と
して出力すると共に、一致の連続が途切れたか、または
データ入力が途切れた時点でメモリ部への書き込みを指
示してライトポインタを進め、同時に前記アップカウン
タをリセットする書き込み制御部と、 前記入力セレクタ出力を格納するデータ部と、前記タグ
値を格納するタグ部を備えたメモリ部と、常に読みだし
位置を示すリードポインタを備え読みだし要求が発生し
た場合に前記タグ部と前記データ部を出力し、その後に
リードポインタを進める読みだし制御回路を具備する符
号化先入れ先だし装置。 - （４）メモリ部内の書き込み位置を示すライトポインタ
を備え、書き込み要求が発生した場合に、外部入力デー
タの一部をメモリ部のタグ部へ、残りをデータ部へ書き
込む様に指示してライトポインタを進める書き込み制御
部と、 前記入力データの一部を格納するタグ部と、残りを格納
するデータ部を備えたメモリ部と、前記データ部出力を
カウントダウンするダウンカウンタと、前記データ部出
力と複数の特定の値を保持するレジスタの出力を選択す
る出力セレクタを備えた出力変換部と、 常に読みだし位置を示すリードポインタを備え、読みだ
し要求が発生した場合に、 前記メモリ部のタグ部出力が第一の値の時、前記出力セ
レクタを前記データ部出力を選択する方向に定めて、デ
ータ出力を行った後にリードポインタを進め、 また前記メモリ部のタグ部出力が第Ｎ（Ｎは２以上の整
数）の値の時、前記出力セレクタを前記第Ｎのレジスタ
出力を選択する方向に定めて前記第Ｎのレジスタ出力を
出力し続け、また前記データ部出力を前記ダウンカウン
タにロードし、その後読みだし要求が発生する度に前記
ダウンカウンタをカウントダウンし、前記ダウンカウン
タ出力が０になった時点でリードポインタを進める読み
だし制御回路を具備する復号化先入れ先だし装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2233539A JPH04112319A (ja) | 1990-09-03 | 1990-09-03 | データ格納方法と先入れ先だし装置 |
| US07/752,788 US5210713A (en) | 1990-09-03 | 1991-08-30 | Data storage method and first-in first-out memory device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2233539A JPH04112319A (ja) | 1990-09-03 | 1990-09-03 | データ格納方法と先入れ先だし装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04112319A true JPH04112319A (ja) | 1992-04-14 |
Family
ID=16956638
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2233539A Pending JPH04112319A (ja) | 1990-09-03 | 1990-09-03 | データ格納方法と先入れ先だし装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5210713A (ja) |
| JP (1) | JPH04112319A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2000079378A1 (fr) * | 1999-06-22 | 2000-12-28 | Seiko Epson Corporation | Dispositif de memoire en liste directe (fifo) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6332152B1 (en) * | 1997-12-02 | 2001-12-18 | Matsushita Electric Industrial Co., Ltd. | Arithmetic unit and data processing unit |
| JP2004151990A (ja) * | 2002-10-30 | 2004-05-27 | Renesas Technology Corp | プログラムカウンタ回路 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01302917A (ja) * | 1988-05-31 | 1989-12-06 | Olympus Optical Co Ltd | データ圧縮方式 |
| JPH02201536A (ja) * | 1989-01-31 | 1990-08-09 | Nec Corp | データ圧縮バッファ |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH07114076B2 (ja) * | 1987-10-20 | 1995-12-06 | シャープ株式会社 | 半導体記憶装置 |
-
1990
- 1990-09-03 JP JP2233539A patent/JPH04112319A/ja active Pending
-
1991
- 1991-08-30 US US07/752,788 patent/US5210713A/en not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01302917A (ja) * | 1988-05-31 | 1989-12-06 | Olympus Optical Co Ltd | データ圧縮方式 |
| JPH02201536A (ja) * | 1989-01-31 | 1990-08-09 | Nec Corp | データ圧縮バッファ |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2000079378A1 (fr) * | 1999-06-22 | 2000-12-28 | Seiko Epson Corporation | Dispositif de memoire en liste directe (fifo) |
| US6772280B1 (en) | 1999-06-22 | 2004-08-03 | Seiko Epson Corporation | First-in first-out storage device |
Also Published As
| Publication number | Publication date |
|---|---|
| US5210713A (en) | 1993-05-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5881302A (en) | Vector processing unit with reconfigurable data buffer | |
| US6275921B1 (en) | Data processing device to compress and decompress VLIW instructions by selectively storing non-branch NOP instructions | |
| US5410727A (en) | Input/output system for a massively parallel, single instruction, multiple data (SIMD) computer providing for the simultaneous transfer of data between a host computer input/output system and all SIMD memory devices | |
| JPS618785A (ja) | 記憶装置アクセス制御方式 | |
| US20010001327A1 (en) | External storage device and memory access control method thereof | |
| US4757440A (en) | Pipelined data stack with access through-checking | |
| US6986029B2 (en) | Micro-controller for reading out compressed instruction code and program memory for compressing instruction code and storing therein | |
| JPH04112319A (ja) | データ格納方法と先入れ先だし装置 | |
| EP0803800B1 (en) | A sort processor and a sort processing device | |
| EP0383342B1 (en) | Microprocessor | |
| JPH0482082A (ja) | 半導体記憶装置 | |
| JP2547219B2 (ja) | ベクトルデータのアクセス制御装置及び方法 | |
| JPH0479422A (ja) | 送信制御回路 | |
| CA2150518C (en) | Vector processing unit with reconfigurable data buffer | |
| US4467413A (en) | Microprocessor apparatus for data exchange | |
| US5826063A (en) | Apparatus and method for programming the setup, command and recovery time periods within a transaction cycle | |
| RU2212715C2 (ru) | Ассоциативное запоминающее устройство | |
| EP1650912B1 (en) | Data queue control circuit for variable length packets | |
| JPS59189442A (ja) | ソ−テイング処理方式 | |
| JPH0253820B2 (ja) | ||
| JPS63231676A (ja) | ベクトルレジスタ制御方式 | |
| JPH04145747A (ja) | 並列信号処理回路 | |
| JPH0210453B2 (ja) | ||
| JPS60215281A (ja) | ベクトルデータ処理装置 | |
| JPS5882336A (ja) | 情報整列装置 |