JPS62171076A - 多値画像ヒストグラム処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、データフロー処理装置を用いて、入力された
多値画像のレベルごとのヒストグラムを得る多値画像ヒ
ストグラム処理方式に関する。

〔従来の技術〕

データフロー処理装置（待開昭５８−７０３６０号公報
記載）等を用いて多値画像のヒストグラムをとる場合、
これまで計数した値を内部メモリから読み出し、インク
リメントし、同じ場所に書き込むという一連の処理が１
つのプロセッサで行なわれ一ケ所に記憶された内部状態
に依存していたため、この動作の間は次の入力データに
よる読み出し動作を禁止する必要があり、全ての入カド
ークンに対して待ち合わせ機能を用いて上で述べた動作
の開始を遅らせるように制御しなければならなかった。

このときの処理のフローを第７図に示し、データフロー
処理装置の構成を示す第３図を用いて処理の手順を説明
する。

１つ目のデータがバスインタフェース２１から入力され
ると、それはトランスファーテーブルメモリ２２、パラ
メータテーブルメモリ２３を通り、データメモリ２４で
あらかじめそこに書き込まれていた処理許可トークン６
１ｂがあるときに限って先に進み、これがない場合には
、そこでデータメモリ２４に書き込まれることにより、
処理許可トークン６１ｂの到着するのを待つ。処理許可
トークン６１ｂがあった場合及び初めになくて後から到
着した場合には、入力データ値を持った１−−クンはリ
ングバスを１周し、再びデータメモリ２４に到着したと
き、入力されたデータ値をアドレスとして参照される過
去の出現回数値を読み出し、そこで得た値をプロセッサ
ユニット２６でインクリメントする。ここでプロセッサ
ユニット２６からトランスファーテーブルメモリ２２に
対し、インクリメントされた値をもつトークン６１ａと
、さらに次のクロ・ツクで２つ目の入力Ｉ・−クンと待
ち合わせるための処理許可トークン６１ｂが出力される
。これらの２つのトークンは連続したままトランスファ
ーテーブルメモリ２２、パラメータテーブルメモリ２３
を通り、インクリメントされた値を持つトークン６１ａ
はデータメモリ２４でそのデータフィールドの値■を前
回参照したときのアドレスに書き込み、また処理許可ト
ークン６１ｂは同じくデータメモリ２４で次の入カドー
クンと持ち合わせ、これが既に到着していれば、さらに
１回りした後にデータメモリ２４で過去の出現回数値を
参照するという動作を繰り返す。

このように２つの入カドークンがプロセッサ外から入力
されたとき、それらがデータメモリ２４を参照し、処理
されるための最短の時間間隔は、トークンが内部リング
を２周する時間と、データメモリ読み出し後プロセ・・
Ｉサユニットで２つの１・−クンを出力するために２つ
めが遅れることによる１クロ・・Ｉりの和となり、■・
−クンが装置の内部リングを一周するのにかかる時間を
Ｌパイプラインステップとするとき、処理できる最大性
能として一つのデータあたり２Ｌ＋１パイプラインステ
・ツブ等の処理す、イクルが必要となる。このときのタ
イムチャートを第８図に示す、ここでは各入力１−一ク
ン１〜４について、待ち合わせ動作Ａ１〜Ａ４、データ
メモリ参照・インクリメント動作８１〜Ｂ４、データメ
モリ書き込み動作０１〜Ｃ４を行ない、処理速度は、ト
ークンが装置の内部リングを一周するのにかかる時間を
Ｌパイプラインステップとするとき、１トークンあなり
２Ｌ＋１パイプラインサイクルになっている。

〔発明が解決しようとする問題点〕

パイプライン化によって処理の高速化を図るデータフロ
ー処理装置においては、一般に内部のバッファがオーバ
フローしない範囲で装置内に存在するデータトークン数
をなるべく多くして、１０セ・ソサユニットが空くこと
なく連続的に処理することが高速処理のために望ましい
。

しかし従来の方式では、上で述べたように一つの画素に
対して計数値の更新を行なってから次の画素に対して行
なうまでには、どんな場合でもトークンが装置の内部リ
ングを一周するのにかかる時間をＬパイプラインステ・
ツブとして最低２Ｌ＋１パイプラインステツプの処理サ
イクルが必要であることになり、このような２Ｌ＋１サ
イクルに１データという平均処理速度をこれ以上上げる
ことはできないという欠点があった。

本発明は、これを高速化することを目的とする。

〔問題点を解決するための手段：］ 本発明の多値画像ヒストグラム処理方式は、すングバス
と、該リングバスによってリング状に接続された複数の
プロセッサと、前記リングバスに接続されたメモリとか
ら成るデータフロー処理装置において、前記メモリから
そのデータ部に画素データを含むトークンを、前記プロ
セッサの１つが前記リングバスを介して入力し、前記画
素データをその数値によって階層化して分割し、この分
割された画素データの夫々の階層に応じて前記画素デー
タを処理するプロセッサを割当て、この割当てたプロセ
ッサのプロセッサナンバを前記トークンに付加したデー
タトークンを、前記リングバスに送出するプロセッサ選
択入力手段と、該プロセッサ選択入力手段により前記リ
ングバスに送出されたプロセッサナンバ及び画素データ
を含むデータトークンを、該データトークンのプロセッ
サナンバと同一のプロセッサナンバを有するプロセッサ
に入力し、この入力されたデータトークンの画素データ
の数値に対応する参照アドレスのデータメモリの内容を
読出し、この内容をインクリメントしてこれを前記参照
アドレスのデータメモリに書き込む更新動作を実行する
更新手段と、該更新手段が更新動作を実行する際、更新
手段に入力されるデータトークンの数を制御する待合せ
手段とを備えている。

〔実施例〕

次に、本発明の実施例について図面を参照して説明する
。

、　第１図は本発明の一実施例の構成を示す図、第２図
は本発明の一実施例を示すプロ・ツク図である。

第１図及び第２図において本発明の一実施例は、リン′
グバス１２と、このリングバス１２によってリング状に
接続された複数のプロセッサ１１ａ。

１１ｂ・・・ｌｌｎと、前記リングバス１２に接続され
たメモリ１３とから構成されている。メモリ１３はその
データ部に画素データを含むトークンをリングバス１２
を介して前記プロセッサの１つに入力し、このプロセッ
サが前記画素データをその数値によって階層化して分割
し、その分割された画素データの夫々の階層に応じて前
記画素データを処理するプロセッサを割当て、このプロ
セッサのプロセッサナンバを前記トークンに付加したデ
ータトークンをリングバス１２に送出するプロセッサ選
択入力手段１６として動作するように構成されている。

このプロセッサ選択入力手段１６は、プロセッサナンバ
及び画素データを含むデータトークンをリングバス１２
に送出する。このデータトークンのプロセッサナンバと
同一のプロセッサナンバを有するプロセッサは、このデ
ータトークンを入力し、この入力されたデータトークン
の画素データの数値に対応する参照アドレスのデータメ
モリの内容を読み出し、この内容をインクリメントして
これを前記参照アドレスのデータメモリに書き込むとい
う更新動作を実行する更新手段２２と、この更新手段１
７が更新動作を実行する際この更新手段１７に入力され
るデータトークンの数を制御する待合せ手段１８とを備
えており、各プロセッサは夫々の更新手段１７を並列に
実行し得るように構成されている、 更に各プロセラは第３図で示されるような構成で、パイ
プライン方式の内部バス２０ｂ〜２０ｆでトランスファ
ーテーブルメモリ２２、パラメータテーブルメモリ２３
、データメモリ２４、キューメモリ２５およびプロセッ
サユニット２６を結合し、さらに外部リングバス１２と
接続されトランスファテーブルメモリ２２及びキューメ
モリ２５との間で夫々内部バス２０ａ、及び２０ｇを介
して外部とのデータの入出力をコントロールするバスイ
ンタフェース２１を持つ。

また、データの単位であるトークンは、プロセッサ内部
バス２０ａ〜２Ｏｆの各点で異なったフォーマツ■・を
持つが、特にプロセッサの内部バス２０ａ及び２Ｏｆに
おいては、内部バス２０ｂ〜・２０ｒを回りトランスフ
ァーメモリ２２に到着した時にそれを参照すべきアドレ
スとなるＩＤと、データの値Ｖとを持ち、一方リングバ
ス１２上においては、データの値■とそのトークンが次
にどのプロセッサに入力されるかをしめすプロセッサナ
ンバと、プロセッサに入力された時にトランスファーメ
モリ２２の参照を行なうためのＩＤとを持つ。

リングバス１２を流れるトークンは各プロセッサのバス
インタフェース２１でトークンのプロセッサ→”ンバと
そのプロセッサ固有のナンバとが一致するかどうかが判
定され、一致すればそのブロモ・ソサの内部バス２０ａ
へ送られ、そうでなければリングバス１２を通って次の
ブロモ・ソサへ送られる。これによりリングバス１２を
流れる１・−クンか入力されるべきブロモ・ソサはそれ
の持つプロセッサナンバによって決定されることになる
。バスインタフェース２１から内部バス２０ａに入力さ
れたトークンはそのｔＤによってトランスファーテーブ
ルメモリ２２を参照し、次に持つべきＩＤと、そのトー
クンがパラメータテーブルメモリ２３の一時メモリエリ
アに対して書込みを行なうべきときにＯ，参照を行なう
べきとにき１であるような読出し書込轟フラグ（以下Ｔ
と呼ぶ。）と、プロセッサユニット２６で実行すべき命
令をパラメータテーブルメモリ２３で参照するためのア
ドレスとなるＦＩＤとが決められる。パラメータテーブ
ルメモリ２３はこのＦＩＤでアクセスされるメモリで、
ブロモ・ソサユニツト２６で実行すべき命令を格納して
おり、また同じＦＩＤでアクセスされる一時メモリエリ
アを持つ。

プログラムは予めバスインタフェース２１を通じてトラ
ンスファーテーブルメモリ２２、パラメータテーブルメ
モリ２３にロードされ、データメモリ２４、キューメモ
リ２５も初期化される２以下、本実施例によって画素の
ヒストグラムを求める方法を説明する。

第４図は本実施例における処理フローを示す図、第５図
はそのうちＩＤ変更部４２の詳細な構成を示す図である
。本実施例では入力されたトークンを用いて更新動作を
行なうプロセッサの数Ｎを８としてあり、また入力され
たデータ値■の下３ビットによって８つのプロセッサに
分流するようにしている。

外部メモリからリングバス１２を通ってブロモ・ソサ選
択を行なうプロセッサに入力されたデータトークンは、
第５図に示すようにコピー命令３１によって連続した２
つのトークン（書込みトークン及び参照トークン）に複
製される。書込みトークンはアンドマスク命令３２によ
って下３ビットをデータ■とし、ＩＤ変更命令３３をＴ
＝Ｏで用いることにより８つの枝への分流のための書込
み動作を行なう。ＩＤ変更命令３３は、Ｔ＝Ｏのときに
データ■をパラメータテーブルメモリ２３の一時メモリ
エリアに書き込み、次回Ｔ＝１で参照されたときにその
トークンのＩＤのフィールドに、一時メモリエリアにあ
る最後に書き込まれた値を゛代入するという機能を持つ
９分流後のＩＤはここでは０から７までとしている。参
照トークンは右へシフト命令３４で３ビツトシフトされ
更新を行なうプロセッサに渡されるデータＶを得た後Ｉ
Ｄ変更命令３５にＴ＝１で入力され、先にＴ＝Ｏで書き
込まれた値に従ってＩＤを受は取り分流する。

ここで前記のコピー命令３１によって複製された書込み
ｌ・−クン及び参照トークンは内部バスを連続して流れ
るので他のトークンによる追い越しは起こらない。

分流後、その変更されたＩＤに従ってプロセッサナンバ
をトークンに付加しバスインタフェース２１からリング
バス１２へ出力するという出力命令が実行され、前記で
選択されたプロセッサに入力される。

各プロセッサで入力データ値に対してその累積加算値を
求めるのはリードライト命令という命令で行なう。それ
はＴ＝Ｏのときに、そのトークンのデータ■をパラメー
タテーブルメモリ２３内の対応する一時メモリエリアに
格納し、同時にト−クンの持つデータＶをアドレスとし
てデータメモリ２４を参照し、得た値をトークンのデー
タのフィールド■に代入しく以下データメモリ９照命令
４６と呼ぶ）、またＴ＝１のときに、その対応する一時
メモリエリアに記憶されている最後に参照されたデータ
メモリ２４のアドレスにデータ■を書き込む（以下デー
タメモリ書込み命令４８と呼ぶ）という機能を持ってい
る。

よって第１図に示すように、分流後の各データ値に対し
て、データメモリ参照命令４６によってそのデータＶを
アドレスとしてこれまでの入力デ−タごとの計数積算値
を格納するデータ、メモリ２４のデータの参照を行ない
、読み出したデータをプロセッサユニット２６でひとつ
インクリメント４７したのちに、データメモリ書込み命
令４８によって、そのデータを最後に読み出したのと同
じアドレスのデータメモリ２４へ書き込むという処理を
行なう。

しかしデータメモリへの書込みが直前の参照アドレスに
対してのみ行なわれるという命令を用いることにより、
上で述べたような方法だけでは、前のデータによるデー
タメモリ２４の参照から、その書込みまでの間は次の入
力データによってデータメモリ２４の参照を行なうこと
を禁止する必要がある。

そのためにデータメモリ参照命令４６の前に待合わせ命
令４５を入れて、データメモリへの書込み後に次の参照
が行なわれるように保証する。この待合わせ命令４５は
、上に用いられるとのは別の部分のデータメモリ上に実
現されたＦＩＦＯで、入力の１−−クン４５ａと４５ｂ
の２つのうち早く実行可能状態になったものが他方が到
着するのを待ち、両方揃った時点でトークンを次の命令
実行へ進ませるもので！）る。この場合、初期値として
４５ｂ側に１つの１・−クンか待っており、装置への入
力データ４５ａが来ると１つに限って、次のデータメモ
リ参照命令４６の実行へ進み、連続して入力された２個
目以降の１・−クンは上述のＦＩＦＯ”待たされ、先に
実行されたデータメモリ参照命令４６及びインクリメン
ｌ−命令４７でプロセッサユニ・ｔトがコピーして出す
２つの出力の一方がデータメモリ書込み命令４８を実行
した後に、もう一方が、ＦＩＦＯに到着することにより
次の入カドークンがデータメモリ参照命令４６を実行す
る。ことを許すことになる。

以上のような方法によって、入力された８ビツトのデー
タの２５６レベルの各累積値が８つのプロセッサに分割
された夫々３２ワードずつのエリアに作られることによ
りヒストグラムを得る処理を行なうことができる。

なお上の例では入力データの下３ビットを用いてプロセ
ッサ選択を行なったが、これをデータの池の部分、例え
ば上位３ビツトを用いて行なうことらできる。これはＩ
Ｄ変更部の中のアンドマスク、右シフトなどのパラメー
タをかえることにより実現できる。

、：発明の効果〕 分流、プロセッサ選択後の各々のプロセッサでの更新用
の命令は、他のプロセッサの命令とは異なるデータメモ
リに作用するため、他とは非同期に平行して命令実行を
行なうことになり効率的な処理を行なうことができる。

。 即ち入力されるデータトークン列のデータ値■が隣接し
たＩ・−クンにおいて上で述べの異なる範囲に属する場
合、その２つは従来のようにトークンが装置の内部リン
グを一周するのにかかる時間をしパイプラインステップ
とするとき、２Ｌ＋１パイプラインサイクル待つことな
しに、入力されたのちＩＤ変更命令の結果が出るとの同
じ速度で更新動作を行なうことができる。例えば最も効
率的に処理を行なえるのは、分割処理するブロセ・ソサ
の数をＮとして、同じプロセッサに入力されるのがＮ個
ごとのトークンとなるときで、この場合、平均処理速度
は分流動作の速度と同じ２パイプラインサイクルとなる
。この場合のタイムチャートを第６図に示す。ここでは
各入カドークン１〜４について、識別子変更動作Ｄ１〜
Ｄ４、待ち合わせ動作Ａ１〜Ａ４、データメモリ参照・
インクリメント動作Ｂ１〜Ｂ４、データメモリ書き込み
動作Ｃ１〜・Ｃ４を行ない、処理速度は２パイプライン
サイクルあたり１１−−クンになっている。ここではＬ
＝７である。

また処理効率が最悪なのは、全てのトークンか同じ枝に
分流されるときであるが、この時でら処理速度は従来と
変わらず、更新動作に必要な２Ｌ十１パイブラインステ
ップ

【図面の簡単な説明】

第１図は本発明の一実施例の構成を示す図、第２図は本
発明の一実施例を示すブロック図、第３図は本発明の一
実施例に用いるプロセッサを示す図、第４図は本実施例
における処理フローを示す図、第５図は第４図の一部の
詳細を示す図、第６図は本実施例における処理のタイム
チャートを示す図、第７図は従来の処理方式における処
理フローを示す図、第８図は従来の処理方式における処
理のタイムチャートを示す図である。 １１ａ〜ｌｌｎ・・・プロセッサ、１２・・・リングバ
ス、１３・・・メモリ、１６・・・ブロモ・ソサ選択入
力手段、１７・・・更新手段、１８・・・待合せ手段。 峯２回 ）３個 チ４−回 躯　＼　　　　　Ｎ　　　　　箇　　　　　勢ダハ ベ１ト

Claims (1)

【特許請求の範囲】
1. リングバスと、該リングバスによってリング状に接続さ
   れた複数のプロセッサと、前記リングバスに接続された
   メモリとから成るデータフロー処理装置において、前記
   メモリからそのデータ部に画素データを含むトークンを
   、前記プロセッサの１つが前記リングバスを介して入力
   し、前記画素データをその数値によって階層化して分割
   し、この分割された画素データの夫々の階層に応じて前
   記画素データを処理するプロセッサを割当て、この割当
   てたプロセッサのプロセッサナンバを前記トークンに付
   加したデータトークンを、前記リングバスに送出するプ
   ロセッサ選択入力手段と、該プロセッサ選択入力手段に
   より前記リングバスに送出されたプロセッサナンバ及び
   画素データを含むデータトークンを、該データトークン
   のプロセッサナンバと同一のプロセッサナンバを有する
   プロセッサに入力し、この入力されたデータトークンの
   画素データの数値に対応する参照アドレスのデータメモ
   リの内容を読出し、この内容をインクリメントしてこれ
   を前記参照アドレスのデータメモリに書き込む更新動作
   を実行する更新手段と、該更新手段が更新動作を実行す
   る際、更新手段に入力されるデータトークンの数を制御
   する待合せ手段とを備え、各プロセッサが夫々前記更新
   動作を並列に実行し得るように構成したことを特徴とす
   る多値画像ヒストグラム処理方式。