WO2004104819A1 - 並列処理装置及び並列処理方法 - Google Patents

並列処理装置及び並列処理方法 Download PDF

Info

Publication number
WO2004104819A1
WO2004104819A1 PCT/JP2004/001526 JP2004001526W WO2004104819A1 WO 2004104819 A1 WO2004104819 A1 WO 2004104819A1 JP 2004001526 W JP2004001526 W JP 2004001526W WO 2004104819 A1 WO2004104819 A1 WO 2004104819A1
Authority
WO
WIPO (PCT)
Prior art keywords
signal
output
circuit
column
row
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.)
Ceased
Application number
PCT/JP2004/001526
Other languages
English (en)
French (fr)
Inventor
Toshishige Shimamura
Koji Fujii
Satoshi Shigematsu
Katsuyuki Machida
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to JP2004567189A priority Critical patent/JP3788804B2/ja
Priority to US10/505,718 priority patent/US7480785B2/en
Priority to DE602004024995T priority patent/DE602004024995D1/de
Priority to EP04711019A priority patent/EP1643356B1/en
Publication of WO2004104819A1 publication Critical patent/WO2004104819A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

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/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/50—Adding; Subtracting
    • G06F7/505—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination
    • G06F7/509—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination for multiple operands, e.g. digital integrators
    • G06F7/5095—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination for multiple operands, e.g. digital integrators word-serial, i.e. with an accumulator-register
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/10—Image acquisition
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/20—Image preprocessing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
    • G06V10/75—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
    • G06V10/751—Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/94—Hardware or software architectures specially adapted for image or video understanding
    • G06V10/955—Hardware or software architectures specially adapted for image or video understanding using specific electronic processors
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V40/00—Recognition of biometric, human-related or animal-related patterns in image or video data
    • G06V40/10—Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
    • G06V40/12—Fingerprints or palmprints
    • 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/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/607—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers number-of-ones counters, i.e. devices for counting the number of input lines set to ONE among a plurality of input lines, also called bit counters or parallel counters

Definitions

  • the processing circuit 2302 outputs the above-described true when the reference irregularities recorded in advance match the detected irregularities, the cell shown in FIG.
  • the shape of the surface (fingerprint) detected in the area where 2301 is arranged can be collated.
  • the number of cells where true is output exceeds 80% of all cells, it is determined that the detected fingerprint shape matches the fingerprint data recorded in advance (authentication) it can.
  • the sum of the reference irregularities of all cells is the fingerprint data.
  • FIG. 16 is a configuration diagram showing a configuration example of the accumulation adder.
  • the accumulation adder 110 adds the row addition results output in synchronization with the clock signal (CK) and the row adder 106 in synchronization with the clock signal (CK).
  • the accumulation adder 110 outputs a signal within the set range (m 'row Xn' column). The total result (final result) of the processing results output from the processing circuit 102 of the cell 101 is output.
  • the start address and the row range m by the row address signal generation circuit 1733 may be set in the row range setting section 172, and the end address and the row range m ′ may be set. It may be set.
  • the row range setting unit 172 can be configured by a register circuit or the like that holds the set value indicating the above-described range.
  • a row address signal generation circuit 173 can be configured by a logic circuit, a counter circuit, and the like.
  • the polarity of the signal is determined in advance, the potential corresponding to “0” or “1”, that is, the ground potential or the power supply You may make it short-circuit to an electric potential.
  • the polarity of the signal is not limited.
  • the row adder 106 and the accumulation adder 110 of the parallel processing device shown in FIG. A row adder 106b, a carry adder 1601, a register 1602, and a CS adder 1603 may be used.
  • the ll type adder 1101, the CS type adder 1401, and the carry type adder 1601 are the same as those shown in Figs. 12, 15, and 17.

Landscapes

  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computing Systems (AREA)
  • Software Systems (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Human Computer Interaction (AREA)
  • General Engineering & Computer Science (AREA)
  • Health & Medical Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Databases & Information Systems (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Medical Informatics (AREA)
  • Mathematical Optimization (AREA)
  • Image Processing (AREA)

Abstract

行範囲設定部(１７２)に設定されている行に対応し、行デコード回路(１７１)よりセレクト信号が出力されていずれかのセレクト信号線(１０３)を選択し、この行の処理回路(１０２)の処理結果をデータ出力線(１０４)に出力させ、列範囲選択部(１０５)に設定されている列のデータ出力線(１０４)に出力された処理結果を行加算器(１０６)で加算する。

Description

明 細 書 並列処理装置及ぴ並列処理方法 技術分野
本発明は、 マトリクス状に配列された複数のセルに備えられた処理部による複 数の処理結果を集計することで並列処理を行う並列処理装置に関わり、 特に、 高 速にかつ正確に集計結果を集計する並列処理装置及び並列処理方法に関する。 背景技術
高速な情報処理を行うために、 個別の処理を単純化して並列に処理する並列処 理装置が開発されている。 並列処理装置の一例として、 単体で簡易な処理を行う セルをマトリタス状に配置したセルアレイとし、 このセルアレイ内の各セルを並 列に動作させるものがある。 このような並列処理装置の応用例として、 各セル内 に指紋センサと指紋認証回路を持ち、 全セルの並列動作により指紋センサで採取 した指紋が登録されている指紋と同一であるかを判定する処理装置 （特開 2 0 0 1 - 2 4 2 7 7 1号公報参照） がある。 また、 各セルが画像処理回路を持ち、 全 セルの並列動作で、 光学センサ等により取得した画像に対する各種画像処理を行 つ装 li (J. C. Gealow ら "System Design for Pixel-Parallel Image Processing " , IEEE Transaction on very large scale integration systems, vol. 4, no. 1, 1996参照） などがある。
上記のセルァレイで構成された並列処理装置に関して簡単に説明する。 この並 列処理装置は図 2 1に示すように、 処理回路を備えたセルがマトリタス状に複数 配置され、 各セルは制御回路から与えられたデータと命令を元に並列に処理を行 う。 各セルの並列処理が終了すると、 制御回路は各セルの処理回路が出力した処 理結果を集計し、 全体の処理結果を生成して出力する。
セルを大量に備えている場合、 各セル内の処理回路は簡略化され、 各セル内の 処理回路の処理結果は、 真 ·偽もしくは数ビット程度のデータとなる。 セルアレイ構成の並列処理装置がよく用いられる応用例としては、 画像処理が ある。 画像処理に並列処理を適用する場合、 各セルが処理対象の画像を構成して いる数ドットに対して所定の処理を行う。 例えば、 パタンマッチングなどの画像 処理を行う場合、 各セルは、 各セルに割り当てられた画像内のドットに対して画 像処理を行い、 照合結果として真 ·偽などを出力する。 各処理の並列処理が終了 した後、 制御回路は、 真の出力数を計数して集計し、 集計した真の数により画像 の一致率などを計算し、 パタンマツチング処理結果を生成する。
このように、 大量の処理回路が独立 ·分散している並列処理装置では、 各処理 回路が処理した結果を収集する必要がある。 このため、 並列処理では、 真 ·偽の 集計などの収集を行う処理が高速でない場合、 並列処理による演算高速化の効果 が失われてしまう。
処理したデータを収集する並列処理装置の集計処理には、 まず、 D R AM (Dy namic Random Access Memory) などと同様にし、 各セルから処理結果を読み出し て集計する第 1の方式がある。 また、 可変遅延時間回路を搭載したセルを直列に 接続し、 処理結果が出力される可変遅延回路の遅延時間をまとめて計測すること で、 処理結果の集計処理を高速に行う第 2の方式 （特開 2 0 0 1— 1 6 6 9 1 7 号公報参照） も提案されている。
まず、 D R AMなどと同様にして各セルから処理結果を読み出して集計する第 1の方式について説明する。 この方式では、 図 2 2に示すように、 n行 m歹 IJに配 列された複数のセル 2 2 0 1を備えている。 各セル 2 2 0 1の処理回路 2 2 0 2 の入力が、 セレクト信号線 2 2 0 3に接続され、 出力がデータパス 2 2 0 4に接 続されている。 セレクト信号線 2 2 0 3は、 配列された処理回路 2 2 0 2の行^ に共通に接続され、 データバス 2 2 0 4は、 配列された処理回路 2 2 0 2の列毎 に共通に接続されている。
行選択制御部 2 2 0 5内のアドレス信号発生回路 2 2 0 6では、 ク口ック発生 回路 2 2 1 0が出力するクロック信号に合わせ、 1行ずつ異なる行を逐次指定す るアドレス信号を生成する。 このようにして生成されるアドレス信号が、 デコー ド回路 2 2 0 7を介して所定セレクト信号線 2 2 0 3に送出されることで、 ァド レス信号が送出されたセレクト信号線 2 2 0 3のある行のセルが選択される。 選 択された行においては、 各々の処理回路 2 2 0 2より、 処理回路 2 2 0 2の処理 結果 （真 OR偽） が出力され、 データバス 2 2 0 4を介してセレクタ回路 2 2 0 8 に入力される。 従って、 上記行クロック信号に合わせ、 一行毎に複数の処理回路 2 2 0 2から処理結果が出力される。
以上のように各処理回路 2 2 0 2より出力された処理結果は、 データバス 2 2 0 4によりセレクタ回路 2 2 0 8に送出される。 セレクタ回路 2 2 0 8では、 デ ータバス 2 2 0 4より 1行毎に複数の処理結果を受け付け、 受け付けた複数の処 理結果を、 1行毎にカウンタ 2 2 0 9に送出する。 このようにして送出された各 処理回路 2 2 0 2の処理結果は、 カウンタ 2 2 0 9にカウントされる。 カウンタ 2 2 0 9では、 各処理回路 2 2 0 2の処理結果 （例えば真） を全て集計し、 処理 結果の加算結果を出力する。
これらのことにより、 カウンタ 2 2 0 9より、 各処理回路 2 2 0 2より出力さ れた処理結果 （例えば真の数） の合計が得られる。
例えば、 予め記録されている基準凹凸と検出した凹凸とがー致した場合、 処理 回路 2 2 0 2が上述した真を出力するようにすれば、 図 2 2に示す構成により、 セル 2 2 0 1を配列した領域で検出される表面 （指紋） 形状を照合することがで きる。 この場合、 真が出力されたセルの数が、 全セルの 8 0 %を超えていれば、 検出された指紋形状と、 予め記録されている指紋データとが一致したものと判断 (認証） できる。 なお、 全てのセルの基準凹凸を合わせたものが、 指紋データで ある。
次に、 前述した第 2の方式について説明する。 この方式では、 図 2 3に示すよ うに、 各セル 2 3 0 1は、 処理回路 2 3 0 2とこの処理結果により進行の通過時 間を変化させる可変遅延回路 2 3 0 3とを備えている。 複数のセル 2 3 0 1は、 可変遅延回路 2 3 0 3を介して直列に接続されている。 可変遅延回路 2 3 0 3は、 例えば、 駆動力の異なるインバータ回路で構成され、 各セル 2 3 0 1の処理回路 2 3 0 2の出力結果 （真 OR偽） は、 各遅延回路 2 3 0 3の信号伝播時間に反映さ れる。
このように直接に接続された複数のセル 2 3 0 1に対し、 制御回路 2 3 0 4よ り測定入力信号が送出されると、 送出された測定入力信号は、 まず、 先頭のセル 2 3 0 1の可変遅延回路 2 3 0 3に入力され、 各セル 2 3 0 1の可変遅延回路 2
3 0 3を通過し、 最後のセル 2 3 0 1の可変遅延回路 2 3 0 3を通過し、 測定出 力信号として遅延カウンタ 2 3 0 5に入力する。
ここで、 可変遅延回路 2 3 0 3は、 処理回路 2 3 0 2の処理結果が真のとき、 通過する信号の基本遅延に、 所定の追加遅延を与えるものとする。 すると、 全て のセル 2 3 0 1を通過した測定出力信号は、 上記基本遅延時間に全てのセルの数 を乗じた基本遅延時間に、 上記追加遅延に 「処理回路 2 3 0 2が真を出力したセ ル 2 3 0 1の数 （真のセル数） 」 を乗じた追加遅延時間だけ遅れて、 遅延カウン タ 2 3 0 5に入力されることになる。 一方、 制御回路 2 3 0 4より出力される測 定入力信号は、 セル 2 3 0 1を通過せずに、 遅延力ゥンタ 2 3 0 5にも出力され る。
遅延カウンタ 2 3 0 5では、 直接入力される測定入力信号の入力時刻と、 最後 のセル 2 3 0 1を通過した測定出力信号と入力時刻との差を取り、 この時間差に より真となったセル 2 3 0 1の数を計数する。
測定出力信号が遅延カウンタ 2 3 0 5に入力する時刻は、 測定入力信号が出力 されてから、 基本遅延 Xセル数 +追加遅延 X真のセル数だけ遅れることになり、 この遅れが計測されることになる。 基本遅延， 追加遅延， セルの数は予め既知で あるので、 計測された遅れから基本遅延 Xセル数を減じ、 この値を追加遅延で除 すれば、 真のセル数が算出できる。
例えば、 処理回路 2 3 0 2が、 予め記録されている基準凹凸と、 検出した凹凸 とが一致した場合、 上述した真を出力するようにすれば、 図 2 3に示す構成によ り、 セル 2 3 0 1を配列した領域で検出される表面 （指紋） 形状を照合すること ができる。 この場合、 真が出力されたセルの数が、 全セルの 8 0 %を超えていれ ば、 検出された指紋形状と、 予め記録されている指紋データとがー致したものと 判断 （認証） できる。 なお、 全てのセルの基準凹凸を合わせたものが指紋データ である。
しかしながら、 前述した従来の第 1の方式では、 各行毎にセルの処理結果を力 ゥンタに転送しているが、 カウンタではセル毎に処理結果を集計していることに なる。 このため、 従来の第 1の方式では、 配列の数が増えてセルの数が増加すれ ば、 これに連動して集計のためにより多くの時間が必要になる。 例えば、 第 1の 方式を、 前述したように指紋の認証を行う装置に適用した場合、 精度を上げるた めにセル数を増加させると、 真となったセルの集計に要する時間が増大して認証 処理に多くの時間を要し、 利便性が低下するという問題があった。
また、 上記の第 2の方式では、 可変遅延回路に駆動力の異なるインパータ回路 の信号伝播の違いを利用しているため、 精度を確保するのが困難であり、 集計結 果に誤差が生じていた。 例えば、 図 2 3に示した第 2の方式を指紋認証を行う装 置に適用した場合、 真となったセルの数により認証を行っているため、 集計結果 に誤差が生じると、 認証率を低下させ、 高いセキュリティーを保てなくなるとい う問題があった。
さらに、 上述したいずれの方式においても、 配列された複数のセルの任意のセ ルを対象として集計を行うことができない。 従って、 上述した従来の技術では、 例えば指紋認証に適用させた場合、 検出した指紋の一部の範囲を比較照合するこ とができない。
本発明は、 以上のような問題点を解消するためになされたものであり、 並列処 理される複数のセルの処理結果を、 従来より高速にかつ正確に集計できるように し、 また、 任意のセルを対象とした処理の集計を可能とすることを目的とする。 発明の開示
本発明に係る並列処理装置は、 マトリクス状に配列された複数のセルと、 配列 の行毎に設けられた複数のセレクト信号線と、 設定されている行範囲に従ってい ずれかのセレクト信号線を選択する行範囲設定手段と、 この行範囲設定手段によ つて選択されたセレクト信号線を選択するためのァドレス信号を所定の間隔で出 力する行ァドレス信号発生手段と、 この行ァドレス信号発生手段が出力したァド レス信号により指定されるセレクト信号線に対してセレクト信号を出力する行デ コード手段と、 セル毎に設けられ、 配列の行毎にセレクト信号線に接続し、 所定 の処理を行ってセレクト信号線を介したセレクト信号の入力により処理の結果を 出力する処理部と、 配列の列毎に設けられて各列の処理部に共通に接続し、 処理 部より出力される処理の結果を伝搬するデータ出力線と、 設定されている列範囲 に従っていずれかのデータ出力線を選択する列範囲選択手段と、 この列範囲選択 手段によって選択されたデータ出力線に出力された処理結果を配列の行毎に加算 して行加算結果を出力する行加算手段と、 この行加算手段が出力した各行の行加 算結果を、 所定の間隔に同期して加算し、 この加算結果を集計結果として出力す る蓄積加算手段とを少なくとも備えるようにしたものである。
この装置によれば、 マトリクス状に配列されたセルが備える処理部の処理結果 力 所定の間隔で各セル毎に加算されるのではなく、 所定の間隔で配列の行毎に —度加算され、 これら行加算結果が上記所定の間隔に同期して加算されることで、 処理部の処理結果が集計される。 加えて、 配列されたセルの中で、 設定されてい る行範囲及び列範囲の中の処理部の処理結果が、 集計される。
また、 本発明に係る並列処理方法は、 マトリクス状に配列された複数のセルに 設,けられた処理部が所定の処理を行う第 1ステップと、 上記配列の行毎に設けら れた複数のセレクト信号線の中より設定されている行範囲に従つていずれかのセ レクト信号線を選択する第 2ステップと、 選択されたセレクト信号線を選択する ためのァドレス信号を生成する第 3ステップと、 生成されたァドレス信号によ 指定されるセレクト信号線に対してセレクト信号を出力する第 4ステップと、 セ レクト信号が出力されたセレクト信号線に接続する複数の処理部より、 配列の列 毎に設けられた複数のデータ出力線に処理の結果を出力する第 5ステップと、 設 定されている列範囲に従つていずれかのデータ出力線を選択し、 選択したデータ 出力線に出力された処理結果を加算して行加算結果を出力する第 6ステップとを 少なくとも備え、 第 2〜第 6ステップを配列の行毎に繰り返し、 行毎に得られた 行加算結果を加算するようにしてものである。
この方法によれば、 マトリクス状に配列されたセルが備える処理部の処理結果 力 所定の間隔で各セル毎に加算されるのではなく、 所定の間隔で配列の行毎に 一度加算され、 これら行加算結果が所定の間隔に同期して加算されることで、 全 ての処理部の処理結果が集計されるようになる。 加えて、 配列されたセルの中で、 設定されている行範囲及び列範囲の中の処理部の処理結果が、 集計される。 図面の簡単な説明 図 1は、 本発明の実施例における並列処理装置の構成例を示す構成図である。 図 2は、 図 1の処理回路 1 0 2の構成例を示す構成図である。
図 3は、 図 1の並列処理装置の動作例を示すタイミングチャートである。 図 4は、 図 1の列範囲選択部 1 0 5の構成例を示す構成図である。
図 5 Aは、 図 4の出力許可回路 1 5 3の構成例を示す回路図である。
図 5 Bは、 図 4の出力許可回路 1 5 3の構成例を示す回路図である。
図 6は、 図 4の出力許可信号生成回路 1 5 1の構成例を示す構成図である。 図 7は、 図 6の記憶回路 5 0 4の構成例を示す回路図である。
図 8は、 出力許可信号生成回路の他の構成例を示す構成図である。
図 9は、 反転回路 7 0 1の構成例を示す回路図である。
図 1 0は、 出力許可信号生成回路の一部構成例を示す回路図である。
図 1 1は、 図 1の行加算器 1 0 6の構成例を示す構成図である。
図 1 2は、 ツリー型加算器の構成例を示す構成図である。
図 1 3は、 桁上げ加算器の構成例を示す構成図である。
図 1 4は、 行加算器の構成例を示す構成図である。
図 1 5は、 C S型加算器の構成例を示す構成図である
図 1 6は、 蓄積加算器の構成例を示す構成図である。
図 1 7は、 桁上げ加算器の構成例を示す構成図である。
図 1 8は、 行加算器と蓄積加算器の構成例を示す構成図である。
図 1 9は、 蓄積加算器のより詳細な構成例を示す構成図である
図 2◦は、 蓄積加算器のより詳細な構成例を示す構成図である
図 2 1は、 一般的な並列処理装置の構成を簡単に示す構成図である。
図 2 2は、 マトリクスに配列されたセルから構成された従来よりある並列処理 装置の構成を示す構成図である。
図 2 3は、 従来よりある並列処理装置の構成を示す構成図である。 発明を実施するための最良の形態
以下、 本発明の実施例について図を参照して説明する
[実施例 1 ] 図 1は、 本発明の第 1の実施例における並列処理装置の構成例を示す構成図で ある。 この並列処理装置は、 まず、 m行 n列配列されたセル 1 0 1， 列範囲選択 部 1 0 5， 行加算器 1 0 6 , 行選択制御部 1 0 7 , 及び蓄積加算器 1 1 0から構 成されている。 各セル 1 0 1は、 所定の処理を行う処理回路 1 0 2を備えている。 行選択制御部 1 0 7は、 各セレクト信号線 1 0 3に接続する行デコード回路 1 7 1と、 行範囲設定部 1 7 2と行アドレス信号発生回路 1 7 3とを備えている。 ま た、 各処理回路 1 0 2の入力が、 セレクト信号線 1 0 3に接続され、 出力がデー タパス （データ出力線） 1 0 4に接続されている。
行毎に設けられたセレクト信号線 1 0 3は、 行選択制御部 1 0 7が備える行デ コード回路 1 7 1に接続し、 列ごとに設けられたデータバス 1 0 4は、 列範囲選 択部 1 0 5を介して行加算器 1 0 6に接続している。
処理回路 1 0 2の例を示す。 処理回路 1 0 2は、 図 2に示すように、 静電容量 を検出するセンサ素子 2 0 1と、 センサ素子 2 0 1で検出された容量を電気信号 に変換してデジタルデータを出力するセンサ回路 2 0 2と、 登録形状 （画像） の 1セル （画素） 分のデータを記憶するフリップ ·フロップ 2 0 4と、 センサ回路 2 0 2の出力おょぴフリップ'フロップの出力を比較して同一である場合 「真」 ， 異なる場合 「偽」 を出力する比較回路 2 0 3とから構成されている。 センサ素子 2 0 1が検出した部分と、 フリップ ·フロップ 2 0 4に記憶されている登録部分 データとは、 各セル毎に並列に比較され、 この比較結果が、 セレクト信号により 制御されるスィツチ素子 2 0 5を介してデータバス 1 0 4に出力される。 各セル 1 0 1より得られる上述した処理結果を集計することで、 例えば、 指紋形状の一 致度を求めることができる。
図 1に示すように、 複数のセル 1 0 1は、 マトリクス状に配列されており、 セ ンサ素子 2 0 1も、 マトリクス状に配列されることになる。 したがって、 これら で、 2次元のセンサとなる。 センサ素子 2 0 1は、 例えば、 5 0 μ πι角程度の寸 法の静電容量型のセンサ素子であり、 図 1に示す並列処理装置は、 複数のセンサ 素子 2 0 1がマトリクス状に配列された検出面を備えた指紋認証装置である。 マトリクス状に配列された複数の静電容量型のセンサ素子から検出面が構成さ れた表面形状認識用センサによれば、 検出面に接触している指の表面 （指紋） の 各部分と、 各センサ素子との間には各々容量が形成され、 形成された容量がセン サ素子に検出される。 各センサ素子に検出される容量は、 指紋の凹凸に対応して 変化し、 センサ素子の配列に対応して凹凸による容量が検出される。 従って、 各 センサ素子の箇所で検出されて各々の容量に対応して濃淡データを設ければ、 指 紋形状が再現できることになる。
ここで、 センサ素子が配置されている各セル毎に、 センサ素子が検出した値と 登録されている値とを比較し、 これら比較結果を集計することで、 検出面により 検出した指紋 （形状） の認証を行うことが可能となる。
従って、 図 1， 2に示す装置によれば、 1チップで指紋認証装置が構成できる。 また、 本装置によれば、 加算機能を各セル毎に設ける必要がないので、 セルサイ ズの増大を抑制でき、 一定面積内により多くのセル （センサ素子） を配置させる ことが可能となる。
以下、 m行 n列配列された複数のセルの中で、 m， 行 n ' 列の範囲 （図中点線 で示す矩形の領域） で集計する場合について説明する。
セレクト信号線 1 0 3に送出されるセレクト信号は、 行選択制御部 1 0 7内の 行アドレス信号発生回路 1 7 3から出力される行アドレス信号 （R A) により 行アドレス信号発生回路 1 7 3は、 図 3に示すように、 クロック発生回路 1 0 9より出力されるクロック信号 （C K) に同期し、 配列されているセル 1 0 1の 行を選択するための行アドレス信号 （R A) を、 行範囲設定部 1 7 2に設定され ている範囲内で、 逐次選択して生成して出力する。 出力された行アドレス信号
(R A) は、 行デコード回路 1 7 1に入力する。 行アドレス信号 （R A) を入力 した行デコード回路 1 7 1は、 行アドレス信号により指定される行に対してセレ クト信号を出力する。
従って、 行範囲設定部 1 7 2に設定されている範囲外のセレクト信号線 1 0 3 は、 選択対象外となる。 ここでは、 点線で示す集計範囲以外のセレク ト信号線 1 0 3力 選択対象外となる。
以上のようにしてセレクト信号が出力されたセレクト信号線 1 0 3の行では、 各セル 1 0 1の処理回路 1 0 2力 ら、 接続しているデータパス 1 0 4に処理結果 が出力される。 この処理結果は、 例えば真 ·偽のいずれかに対応する信号である。 以上のことにより、 1行目の各処理回路 102の処理結果， 2行目の各処理回 路 102の処理結果， · · ·力 S、 クロック信号 （CK) に同期して行毎に、 列範 囲選択部 105を介して行加算器 106に出力される。 列範囲選択部 105は、 予め設定されている、 選択された列だけのデータバスの値を出力する。 各データ パス 104が接続している行加算器 106は、 同じ行の中の列範囲選択部 105 に選択された列にあるセル 1 01の処理結果を、 データバス 104を介して受け 付けて加算し、 加算した結果を蓄積加算器 1 10に出力する。 従って、 行加算器 106は、 図 3に示すように、 クロック信号 （CK) に同期し、 行毎の加算結果 (行加算結果： C S O) を出力する。
また、 蓄積加算器 1 10は、 図 3に示すように、 クロック信号 （CK) に同期 し、 行加算器 106よりクロック信号 （CK) に同期して出力される行加算結果 を加算する。 行アドレス信号発生回路 1 73から、 最後の行を選択するための行 アドレス信号 (RA) が出力されると、 蓄積加算器 1 10より、 設定された範囲 内 （m' 行 Xn' 列） のセル 101の処理回路 1 02より出力された処理結果の 集計結果 （最終結果） が出力される。
以下、 図 3に従って動作例を説明する。 以下では、 行範囲設定部 1 72には、 アドレス aの行から m' 行選択することが設定されているものとし、 列範囲選択 部 105には、 アドレス bの列から n' 列選択することが設定されているものと する クロック発生回路 109より出力されるクロック信号に同期し、 行ァドレ ス信号 （RA) が変更され、 行アドレス aから、 セレク ト信号線 103 (行） が 選択されていく。
行アドレスが変更された後、 行加算器 1 06の処理時間の経過後に、 行加算結 果 （CSO) が確定する。 ここで、 列範囲選択部 105は、 アドレス bの列から n' 列選択し、 選択した列の出力のみを行加算器 106に出力する。 従って、 行 加算器 106は、 アドレス bの列から n' 列の範囲のみの加算結果を出力する。 蓄積加算器 1 10は、 行アドレス変更前までの加算結果 （SO) に、 行ァドレ スが変更されたときの行加算結果 （CSO) を加算する。 以上のことを、 行アド レス a+m' _1まで行うことで、 m， 行 Xn' 列の範囲の集計結果が確定され る。 なお、 例えば、 行範囲設定部 1 7 2には、 行ァドレス信号発生回路 1 7 3によ るスタートアドレスと行範囲 m， とが設定されていても良く、 終了アドレスと行 範囲 m ' とが設定されていても良い。 行範囲設定部 1 7 2は、 上述した範囲を示 す設定値を保持するレジスタ回路などで構成できる。 また、 論理回路とカウンタ 回路などにより、 行ァドレス信号発生回路 1 7 3を構成することが可能である。 以上に説明したように、 本実施例によれば、 配列された各セル 1 0 1の処理回 路 1 0 2より出力される処理結果を、 クロック信号に同期して行毎に加算し、 行 毎の加算結果をさらに加算するようにした。 この結果、 従来のように、 クロック 信号に同期してセル毎に加算する場合に比較し、 処理時間を 1 （1行のセル 数） すなわち 1 Z列数に低減することができる。 また、 ディジタル信号のみで処 理することで、 集計結果の誤差を生じることなく、 集計処理を行うことができる。 また、 任意の （所定の） 範囲のセルを選択して集計することが可能である。 な お、 上述では、 m ' 行 X n ' 行の範囲で集計する場合を例に説明したが、 これに 限るものではない。 行範囲設定部 1 7 2及び列範囲選択部 1 0 5への設定により、 分割された複数の範囲を集計することも可能である。
[実施例 2 ]
次に、 列範囲選択部 1 0 5についてより詳細に説明する。 図 4は、 図 1に示し た並列処理回路における列選範囲択部 1 0 5の構成例を示す構成図である。 図 4 に示す列範囲選択部 1 0 5は、 出力許可信号生成回路 1 5 1と、 列範囲設定部 1 5 2と、 各データバス 1 0 4毎に対応して設けられた出力許可回路 1 5 3とから 構成されていることが特徴である。
出力許可回路 1 5 3は、 出力許可信号生成回路 1 5 1から出力される出力許可 信号に従い、 データバス 1 0 4からの信号の出力を制御する。 出力許可信号が
「許可」 のときは、 データパス 1 0 4からの信号をこのまま出力し、 出力許可信 号が 「不許可」 の場合は、 「0」 （零） を出力する。 これらのことにより、 行カロ 算器 1 0 6の構成を変更することなく、 指定された集計範囲 （列範囲） のセル 1 0 1の処理回路 1 0 2の処理結果だけを加算することができる。
出力許可信号生成回路 1 5 1は、 列範囲設定部 1 5 2に設定されている集計範 囲に対応し、 「許可」 もしくは 「不許可」 のいずれかの出力許可信号を出力許可 回路 1 5 3に出力する。 図 5 A, 図 5 Bに、 出力許可回路 1 5 3の回路例を示す。 図 5 A， 図 5 Bに示すように出力許可回路 1 5 3は、 AN Dゲートを用いて実現 できる。 図 5 Aは、 出力が許可される場合の状態を示し、 図 5 Bは、 出力が許可 されない場合を示している。 図 5 Aに示すように、 出力許可信号が 「1」 のとき は、 データパスからの信号 「a」 が出力され、 図 5 Bに示すように、 出力許可信 号が 「0」 のときは、 信号 「0」 が出力されてデータバスからの信号 「a」 は出 力されない。
なお、 列範囲設定部 1 5 2は、 上述した列範囲の設定値を保持するレジスタ回 路などで構成できる。 また、 出力許可信号生成回路 1 5 1は、 列範囲設定部 1 5 2に設定されている設定値に対応した列の出力許可回路 1 5 3のみが、 「1」 を 出力するような回路を構成すればよい。
図 4に示す列範囲選択部 1 0 5により、 列範囲設定部 1 5 2に設定された列範 囲のデータバス 1 0 4のみの値だけを行加算器 1 0 6に出力し、 これら以外の列 は 「0」 を出力するようにしたので、 行加算器 1 0 6の構成を変更することなく、 指定された列のセルのデータだけを加算することができる。
[実施例 3 ]
次に、 出力許可信号生成回路について、 より詳細に説明する。 図 6は、 図 4に 示した列範囲選択部 1 0 5における出力許可信号生成回路 1 5 1の構成例を示す 構成図である。 図 6に示す出力許可信号生成回路 1 5 1は、 列デコード回路 5 0 1と列ァドレス信号発生回路 5 0 2と初期化回路 5 0 3と、 各々の出力許可回路 1 5 3に対応する複数の記憶回路 5 0 4とから構成されていることが特徴である。 各記憶回路 5 0 4は、 出力許可回路 1 5 3への出力許可信号を保持する。 記憶 回路 5 0 4への出力許可信号の設定は、 次に示すことにより行うことができる。 まず記憶回路 5 0 4を初期化回路 5 0 3で初期化する。 この後、 出力を許可する 列を列デコード回路 5 0 1により選択することで、 対応する記憶回路 5 0 4へ各 々の出力許可信号を設定する。 出力を許可する列は、 列範囲設定部 1 5 2に設定 されており、 この設定値に対応した列アドレスが、 列アドレス信号発生回路 5 0 2から出力される。 この出力される列アドレスに対応し、 列デコード回路 5 0 1 は、 例えば、 出力を許可する制御の出力許可信号を記憶回路 5 0 4に設定する。 図 7に、 記憶回路 5 0 4の構成例を示す。 図 7に示すように、 記憶回路 5 0 4 は、 S Rフリップフロップから構成することが可能である。 S Rフリップフロッ プは、 リセット端子 （R) に 「1」 が入力されると 「0」 が書き込まれ、 出力
(Q) からは 「0」 が出力される。 また、 セット端子 （S ) に 「1」 が入力され ると、 「1」 が書き込まれて出力 （Q) からは 「1」 が出力される。
このような記憶回路 5 0 4を用いれば、 列デコード回路 5 0 1により選択され た記憶回路 5 0 4に、 「1」 を書き込むことで、 対応する出力許可回路 1 5 3に 所定の出力許可信号を設定することができる。
なお、 上述では、 出力を許可する列の出力許可回路 1 5 3に対し、 列を特定す るための信号として、 出力許可信号 「1」 を設定する例を示したが、 これらに限 るものではない。 例えば、 初期化をするときに、 全ての列が出力が許可された状 態とし、 出力を許可しない列に対応する出力許可回路だけに、 所定の出力許可信 号を設定するようにしてもよい。 列範囲設定部 1 5 2に設定されている状態に従 い、 選択された列に対応する記憶回路 5 0 4と、 他の記憶回路 5 0 4とに設定す る出力許可信号の状態が異なっていればよい。
以上に説明した本実施例の並列処理装置によれば、 規則的なレイァゥトが可能 な列デコード回路を用い、 また各列毎に記憶回路を配設するようにしたので、 規 則的なレイァゥトが可能になり、 小面積かつ簡略に出力許可信号生成回路を実現 することができる。
[実施例 4 ]
次に、 他の形態の出力許可信号生成回路について、 図 8を用いて説明する。 図 8に示す出力許可信号生成回路 1 5 1 aは、 図 6の出力許可信号生成回路 1 5 1 に、 反転回路 7 0 1と初期値設定回路 7 0 3を加えたものである。 反転回路 7 0 1は、 記憶回路 5 0 4より出力された反転許可信号が 「許可」 すなわち 「1」 の とき、 入力した信号を反転して出力する。 また、 反転回路 7 0 1は、 記憶回路 5 0 4より出力された反転許可信号が 「不許可」 すなわち 「0」 のとき、 入力した 信号と同じ信号を出力する。
反転回路 7 0 1は、 例えば、 図 9に示すように、 排他的論理和 （E O R) ゲー トにより実現できる。 図 9に示すように各記憶回路より反転許可信号が出力され る場合、 出力許可信号が連続する列で比較した場合に変化する列に対応する反転 回路 7 0 1に、 「許可」 すなわち 「1」 の反転許可信号を設定すればよい。 これ ら以外の列に対応する反転回路 7 0 1には、 「不許可」 すなわち 「0」 の反転許 可信号を設定する。
このようにすることで、 出力許可をする全ての列の記憶回路に対して 「1」 を 設定する必要が無くなる。
従って、 例えば、 n ' 列の範囲を選択する場合、 この範囲の境界領域の列に対 応する 2つの記憶回路にのみ 「1」 を設定すれば良く、 図 6に示した例に比較し て、 設定回数が 2 Ζ η ' に低減できる。 このように、 本実施例によれば、 列範囲 設定部 1 5 2に設定されている状態に従い、 選択された列に対応する記憶回路 5 0 4と、 他の記憶回路 5 0 4とに設定する反転許可信号の状態が異なるようにす ることで、 反転回路 7 0 1を制御するようにしたので、 出力許可信号生成回路の 選択範囲の設定手順を、 簡略化することが可能となる。 ' ところで、 初期値設定回路 7 0 3は、 フリップフロップなどで実現することが でき、 信号の極性が予め決定されていれば、 「0」 又は 「1」 に対応する電位、 すなわち接地電位や電源電位に短絡しておくようにしてもよい。 なお、 上述した 実施例では、 信号の極性が限定されるものではない。
また、 図 1 0に示すように、 反転回路 8 0 1に加えて論理回路 8 0 2を設け、 論理回路 8 0 2により、 反転許可信号と反転信号とを論理演算した結果を、 出力 許可回路に出力許可信号として出力してもよい。 このようにすることで、 列アド レスの設定範囲と列デコード回路の指定範囲とを同一とすることができ、 利便性 が向上する。 論理回路 8 0 2は、 O Rゲートに限らず他の回路構成としてもよい。 次に、 行加算器についてより詳細に説明する。 図 1 1は、 図 1に示した並列処 理回路における行加算器の構成例を示す構成図である。 図 1 1に示す行加算器 1 0 6は、 ツリー型加算器 1 1 0 1と桁上げ型加算器 1 1 0 2とから構成されてい ることが特徴である。 行加算器 1 0 6は、 配列された各セル 1 0 1が接続する各 データパス 1 0 4に出力される 1ビット信号を加算する。
配列されたセル 1 0 1の列数を n列とすると、 行加算器 1 0 6には、 nビット の 2進数の各ビットを加算して、 + 1 (= 1 o g 2 ( n ) + 1 ) ビットの結果を 出力する機能が必要とされる。
ツリー型加算器 1 1 0 1は、 この機能を満たすものである。 図 1 2は、 n = l 6とした場合のツリー型加算器 1 1◦ 1の構成例を示す構成図である。 ツリー型 加算器 1 1 0 1は、 入力側の 1段目に 8個の全加算器 1 1 1 1を備え、 2段目に 4個の全加算器 1 1 1 2を備え、 3段目に 2個の全加算器 1 1 1 3を備え、 4段 目に 1個の全加算器 1 1 1 4を備える。
ツリー型加算器 1 1 0 1において、 入力側より入力される 1 6ビットの入力信 号の各ビットは、 8個の全加算器 1 1 1 1の各々の入力端子 （X、 Y、 C iのい ずれか） に入力される。 この中の 7個の全加算器 1 1 1 1より出力される和信号 ( S ) は、 隣の全加算器 1 1 1 1の入力端子に入力し、 残りの 1個の全加算器 1 1 1 1より出力される和信号 （S ) は、 ツリー型加算器 1 1 0 1より出力される 信号の最下位ビット （s o ) となる。
1段目の 8個の全加算器 1 1 1 1より出力される点線で示す桁上げ信号 （C。） は、 2段目の 4個の全加算器 1 1 1 2の入力端子に入力される。 これらは、 前述 した 1段目の全加算器 1 1 1 1と同様に接続され、 2段目の中の 3個の全加算器 1 1 1 2より出力される和信号 （S ) は、 隣 （3段目） の全加算器 1 1 1 3の入 力端子に入力し、 残りの 1個の全加算器 1 1 1 2より出力される和信号 （S ) は、 ツリー型加算器 1 1 0 1より出力される信号の 2ビット目の出力 （S 1) となる。 ツリー型加算器 1 1 0 1は、 このように桁上げ信号を加算するために、 3段目 は 2個の全加算器 1 1 1 3、 4段目は 1個の全加算器 1 1 1 4で構成する。 n = 1 6とする場合のッリ一型加算器 1 1 0 1は、 合計 1 5個の全加算器で構成すれ ばよく、 1 6ビットの入力に対し、 5ビット （= 1 o g 2 ( 1 6 ) + 1 ) を出力す る。
ところで、 ツリー型加算器は、 全加算器の接続に規則性がないため、 設計者が 全ての配線を結線しなければならない。 上述では、 n = 1 6の場合について例示 したが、 画像処理等に用いられる並列処理装置では、 nが数百から数千となるた め、 これに対応するツリー型加算器の回路は複雑となり、 設計時間が膨大となる だけでなく、 設計者のミスが入りやすくなるという問題がある。
この問題を解決するために、 図 1 1に示すように、 n列のデータバスを、 a列 を 1組として b組に分割し、 1組毎に、 aビット入力， ab+ l (= 1 o g2 (a) +1) ビット出力のツリー型加算器 1 101と、 nb+ l (= 1 o g2 (n) + 1) ビットの桁上げ型加算器 1 1 02とを設けるようにした。 図 1 3は、 + 1ビッ トの桁上げ型加算器 1 102の構成例を示す構成図である。 桁上げ型加算器 1 1 02は、 nb+ 1個の全加算器 1 121から構成されている。 各々の全加算器 1 1 21の和信号 （実線） は、 このまま各ビットの出力信号となり、 各々の全加算器 1 1 21の桁上げ信号 （点線） は、 下位ビットの全加算器 1 121から順に上位 ビットの全加算器 1 1 21に伝播する。 また、 ツリー型加算器 1 101の出力は、 最下位ビットから ビットまでの全加算器 1 1 21に入力される。
図 1 1に示す行加算器 106では、 a列のデータパスの組からの各信号を、 各 々ッリ一型加算器 1 101で a b+ 1ビットの信号にまとめ、 これらの各信号を n b+1ビットの桁上げ型加算器 1 1 02により、 図 1 1の右側から順に加算するこ とで、 m行 n列に配列されたセル 101の処理結果を加算している。 なお、 全加 算器の入力端子が 1つあまる場合は、 半加算器から構成するようにしても良い。 また、 全ての桁上げ型加算器 1 1 02が、 nb+ 1ビットである必要はなく、 例え ば、 図 1 1において、 最も右側の桁上げ型加算器 1 102は a b+ 1ビットととし、 右から 2組目の桁上げ型加算器 1 102を （ 1 o g2 ( 2 X a ) + 1 ) ビットとし、 b組目の桁上げ型加算器 1 102を （1 o g2 (b X a) + 1) ビット、 すなわち、 n„+ 1ビットとしても良い。
次に、 他の行加算器の構成例について説明する。 図 14は、 図 1に示した並列 処理装置を構成する行加算器の他の構成例を示す構成図である。 図 14に示す行 加算器 106 aは、 複数のツリー型加算器 1 10 1と、 CS型 （キャリーセーブ 型） 加算器 1401と、 桁上げ型加算器 1 1 02とから構成したものである。 ッ リ一型加算器 1 1 01及び桁上げ型加算器 1 102は、 図 1 1, 12, 13と同 様であり、 ここでは説明を省略する。
以下、 CS型加算器 1401について説明する。 CS型加算器 1401は、 図 1 5に示すように、 1つのツリー型加算器 1 101の出力に対して、 n b+1個の 全加算器 141 1を備えるようにしたものである。 また、 1つのツリー型加算器 1 101の出力に対応する各全加算器 141 1より出力される和信号 （実線） は、 同じビットとなる左隣の全加算器 1 4 1 1に入力される。 また、 1つのツリー型 加算器 1 1 0 1の出力に対応する各全加算器 1 4 1 1より出力される桁上げ信号 (点線） は、 1ビット上位となる左隣の全加算器 1 4 1 1に入力される。 各ッリ 一型加算器 1 1 0 1の出力は、 最下位ビットから ab+ 1ビットまでの全加算器 1 4 1 1に入力される。
図 1 4に示すように、 桁上げ型加算器 1 1 0 2は、 C S型加算器 1 40 1の出 力の和信号 （ ビット） と， 桁上げ信号 （ ビット） とを入力し、 nb+ lビット の行加算結果を出力する。 図 1 4に示す行加算器 1 0 6 aは、 C S型加算器 1 4 0 1を用いる。 このため、 図 1 1に示した行加算器 1 06のように、 桁上げ型加 算器 1 1 0 2の桁上げ信号を下位ビットから上位ビットまで伝播させることがな い。 この結果、 C S型加算器 1 40 1では、 クリティカルパスを大幅に短くする ことができ、 図 1 1に示す行加算器 1 06に比べて高速化を図ることができる。 また、 C S型加算器 1 40 1は、 結線に規則性があるため、 図 1 1に示した行 加算器 1 06のように構成する場合に比べて、 設計作業が行いやすいという特徴 も有する。 なお、 全加算器 1 4 1 1の入力端子が 1つあまる場合は、 これらを半 加算器にしても良い。 また、 C S型加算器 1 40 1の全ての段を nb+ 1ビットと する必要はなく、 例えば、 図 1 5の最も右側の段の全加算器 1 4 1 1の列を ab+ 1ビットとし、 右から 2番目の段の全加算器 1 4 1 1の列を （1 o g2 (2 X a) + 1 ) ビットとし、 b番目の段の全加算器 1 4 1 1の列を （ 1 o g 2 ( b X a ) + 1) ビット、 すなわち、 nb+ 1ビットとしても良い。
ところで、 上述した各構成において、 蓄積加算器 1 1 0は、 図 1 6に示すよう に、 桁上げ型加算器 1 6 0 1とレジスタ 1 6 0 2とから構成すればよい。 配列さ れたセル 1 0 1のセル数を Pとすると、 桁上げ型加算器 1 6 0 1は、 Pb+ 1 (= 1 o g2 (P) + 1) ビットの桁上げ型加算器であり、 レジスタ 1 6 02は、 Pb+ 1ビットのレジスタである。
行加算器 1 06 (行加算器 1 06 a) より出力された行加算結果は、 桁上げ型 加算器 1 6 0 1により、 レジスタ 1 6 02の出力とクロック発生回路出力 （C K) に同期し、 逐次加算される。 CKをレジスタ 1 6 0 2に入力し、 CKに同期 して行加算結果が変化する毎に、 レジスタ 1 6 0 2に一時的に保存されるデータ を更新することで、 各行の行加算結果を加算していき、 複数のセル 101の処理 結果を加算する。
桁上げ型加算器 1 601は、 例えば図 1 7に示すように、 Pb+ 1個の全加算器 161 1から構成すればよい。 桁上げ型加算器 1 601において、 まず、 行加算 器 106 (行加算器 106 a) より出力された行加算結果は、 最下位ビットから nb+ 1ビットまでの全加算器 161 1に入力される。 各々の全加算器 161 1の 和信号 （実線） は、 このまま各ビットの出力信号となり、 各々の全加算器 161 1の桁上げ信号 （点線） は、 下位ビットの全加算器 16 1 1から順に上位ビ: ト の全加算器 161 1に伝播する。 また、 レジスタ 1 602より出力された Pb+ 1 ビットの信号が、 Pb+ 1個の全加算器 16 1 1に入力される。
また、 図 1に示した並列処理装置の行加算器 106と蓄積加算器 1 10とを、 図 18に示すように、 複数のッリ一型加算器 1 10 1及ぴ C S型加算器 1401 から構成された行加算器 1 06 bと、 桁上げ型加算器 1 601とレジスタ 1 60 2と C S型加算器 1603とから構成された蓄積加算器 1 10 aから構成しても よい。 ッリ一型加算器 1 101， C S型加算器 1401, 桁上げ型加算器 1 60 1は、 図 1 2， 図 1 5， 図 1 7に示した構成と同様である。
図 1 8に示すように、 蓄積加算器 1 10 aは、 図 16に示した蓄積加算器 1 1 0に CS型加算器 1 603を加えたものである。 蓄積加算器 1 1 0 aでは、 まず、 行加算器 1 06 aにおける CS型加算器 1401から出力された和信号と桁上げ 信号、 及ぴ、 レジスタ 1 602より出力された信号の 3つのデータを C S型加算 器 1603で処理する。
CS型加算器 1 603は、 図 1 9に示すように、 Pb+ 1個の全加算器 1 631 から構成されたものである。
まず、 行加算器 106 bの CS型加算器 1401より出力された各々 ビット の和信号 （実線） と桁上げ信号 （点線） とが、 CS型加算器 1603の最下位ビ ットから nb+ 1ビットまでの全加算器 1631に入力される。 また、 レジスタ 1 602より出力された Pb+ 1ビットの信号が、 全ての全加算器 1 63 1に入力さ れる。
全加算器 1631から出力される和信号 （実線） と桁上げ信号 （点線） とは、 桁上げ型加算器 1 6 0 1の P b+ 1個の全加算器 1 6 1 1に入力する。 なお、 最下 位ビットの和信号は、 このまま出力されてレジスタ 1 6 0 2に入力される。
全加算器 1 6 3 1からの信号を入力した全加算器 1 6 1 1では、 各々の全加算 器 1 6 1 1の桁上げ信号 （点線） 力 下位ビットの全加算器 1 6 1 1から順に上 位ビットの全加算器 1 6 1 1に伝播し、 各々の全加算器 1 6 1 1の和信号 （実 線） ヽ 各ビットの信号としてレジスタ 1 6 0 2に出力される。
図 1 8に示す行加算器 1 0 6 bと蓄積加算器 1 1 0 aとの構成では、 蓄積加算 器 1 1 0 aが C S型加算器 1 6 0 3を備えているため、 図 1 4に示した行加算器 1 0 6 aに比較し、 桁上げ型加算器 1 1 0 2が不要となる。 このように、 図 1 8 に示す構成によれば、 桁上げ型加算器を c S型加算器で置き換えることができる ため、 クリティカルパスを短くすることができ、 より加算処理を高速化できるよ うになる。
なお、 図 1 9に示す蓄積加算器 1 1 0 aにおいて、 全加算器の入力端子が 1つ あまる場合は、 半加算器から構成しても良い。 また、 図 2 0示すように、 n b個の 全加算器 1 6 3 1から構成された C S型加算器 1 6 0 3 aを用いるようにしても 良い。 図 1 9に示すように、 C S型加算器 1 6 0 3の n b+ 1個目から Pb+ 1個目 までの全加算器 1 6 3 1は加算処理をしていないため、 これらを除く図 2 0に示 すような構成としても良い。
以上に説明したように、 本発明では、 設定されている行のセレクト信号線を選 択してこの行の処理部の処理結果をデータ出力線に出力させ、 設定されている列 のデータ出力線に出力された処理結果を加算するようにした。 この結果、 本発明 によれば、 並列処理される複数のセルの処理結果を、 従来より高速にかつ正確に 集計でき、 任意のセルを対象とした処理の集計ができるという優れた効果が得ら れる。
以上に説明した本発明に係る並列処理装置は、 例えば、 指紋の形状を検出して 検出した形状と登録されている形状とを比較する指紋認証装置に適用できる。

Claims

請 求 の 範 囲
1 . マトリタス状に配列された複数のセルと、
前記配列の行毎に設けられた複数のセレクト信号線と、
設定されている行範囲に従っていずれかの前記セレクト信号線を選択する行範 囲設定手段と、
この行範囲設定手段によって選択されたセレクト信号線を選択するためのァド レス信号を所定の間隔で出力する行ァドレス信号発生手段と、
この行ァドレス信号発生手段が出力したァドレス信号により指定されるセレク ト信号線に対してセレクト信号を出力する行デコード手段と、
前記セル毎に設けられ、 前記配列の行毎に前記セレク ト信号線に接続し、 所定 の処理を行って前記セレクト信号線を介した前記セレクト信号の入力により前記 処理の結果を出力する処理部と、
前記配列の列毎に設けられて各列の前記処理部に共通に接続し、 前記処理部よ り出力される前記処理の結果を伝搬するデータ出力線と、
設定されている列範囲に従っていずれかの前記データ出力線を選択する列範囲 選択手段と、
この列範囲選択手段によつて選択されたデータ出力線に出力された処理結果を 前記配列の行毎に加算して行加算結果を出力する行加算手段と、
この行加算手段が出力した各行の行加算結果を、 前記所定の間隔に同期して加 算し、 この加算結果を集計結果として出力する蓄積加算手段と
を少なくとも備えることを特徴とする並列処理装置。
2 . 請求の範囲第 1項に記載の並列処理装置において、
前記列範囲選択手段は、
前記配列の列毎に配置され、 前記データ出力線から前記行加算手段への信号出 力を制御する出力許可回路と、
前記列範囲が設定されている列範囲設定手段と、
この列範囲設定手段に設定されている列範囲に従って、 前記出力許可回路の出 力を制御する出力許可信号を生成して出力する出力許可信号生成回路と を備え、
前記出力許可回路は、
前記出力許可信号により、 前記データ出力線からの信号の前記行加算手段への 出力を制御する
ことを特徴とする並列処理装置。
3 . 請求の範囲第 2項に記載の並列処理装置において、
前記出力許可信号生成回路は、
前記配列の列毎に設けられて設定されている出力許可信号を同一列の前記出力 許可回路に出力する記憶回路と、
この記憶回路を初期化する初期化回路と、
前記記憶回路に出力許可信号を設定する列デコード回路と、
前記列範囲設定手段に設定されている前記列範囲に従って列ァドレスを指定す る列ァドレス信号を発生する列ァドレス信号発生回路と
を備 、
前記列デコード回路は、 前記列ァドレス信号発生回路が発生した列ァドレス信 号に対応する前記記憶回路に対して設定する出力許可信号と、 他の前記記憶回路 に対して設定する出力許可信号と異なる状態とする
ことを特徴とする並列処理装置。
4 . 請求の範囲第 2項に記載の並列処理装置において、
前記出力許可信号生成回路は、
前記配列の列毎に設けられて設定されている反転許可信号を出力する記憶回路 と、
この記憶回路を初期'化する初期化回路と、
前記記憶回路に反転許可信号を設定する列デコード回路と、
前記配列毎に設けられ、 同一の列の前記記憶回路より出力された反転許可信号 を一方の入力信号とした 2つの入力信号を入力し、 前記一方の入力信号として入 力した前記反転許可信号をもとに他方の入力を反転して前記出力許可回路に前記 出力許可信号として出力する反転回路と、 O 2004/104819
22 前記配列の一端の前記反転回路の他方の入力信号として初期値を出力する初期 値設定回路と、
前記列範囲設定手段に設定されている前記列範囲に従って列ァドレスを指定す る列ァドレス信号を発生する列ァドレス信号発生回路と
を備え、
前記列デコード回路は、 前記列ァドレス信号発生回路が発生した列ァドレス信 号に対応する前記記憶回路に対応して設定する反転許可信号と、 他の前記記憶回 路に対して設定する反転許可信号とを異なる状態とし、
前記反転回路は、 出力する信号を前記配列の他端側の次の列の反転回路の他方 の入力信号とし、 前記配列の一端側の前の列の反転回路より出力された出力許可 信号を前記他方の入力信号として入力する
ことを特徴とする並列処理装置。
5 . 請求の範囲第 2項に記載の並列処理装置において、
前記出力許可信号生成回路は、
反転許可信号を出力する記憶回路と、 ， この記憶回路を初期化する初期化回路と、
前記記録回路に前記反転許可信号を設定する列デコード回路と、
同一の列の前記記憶回路より出力された反転許可信号を一方の入力信号とした 2つの入力信号を入力し、 前記一方の入力信号として入力した前記反転許可信号 をもとに他方の入力を反転した反転信号を出力する反転回路と、
前記反転許可信号と前記反転信号とを論理演算した結果を前記出力許可回路に 出力許可信号として出力する論理回路と、
前記配列の一端の前記反転回路の他方の入力信号として初期値を出力する初期 値設定回路と、
前記列範囲設定手段に設定されている前記列範囲に従って列ァドレスを指定す る列ァドレス信号を発生する列ァドレス信号発生回路と
を備え、
前記列デコード回路は、 前記列ァドレス信号発生回路が発生した列ァドレス信 号に対応する前記記憶回路に対応して設定する反転許可信号と、 他の前記記憶回 路に対して設定する反転許可信号とを異なる状態とし、
前記反転回路は、 出力する信号を前記配列の他端側の次の列の反転回路の他方 の入力信号とし、 前記配列の一端側の前の列の反転回路より出力された反転信号 を前記他方の入力信号として入力する
ことを特徴とする並列処理装置。
6 . 請求の範囲第 1項に記載の並列処理装置において、
前記行加算手段は、 複数の前記データ出力線より入力した処理結果を集計する 複数のツリー型加算器と、 このツリー型加算器毎に設けられ、 前記ツリー型加算 器より出力される複数の集計結果を加算する桁上げ型加算器とから構成されるも のであることを特徴とする並列処理装置。
7 . 請求の範囲第 1項に記載の並列処理装置において、
前記行加算手段は、 複数の前記データ出力線より入力した処理結果を集計する 複数のッリ一型加算器と、 この複数のッリ一型加算器より出力される複数の集計 結果を加算するキャリーセーブ型加算器と、 このキャリーセーブ型加算器より出 力される和信号及び桁上げ信号を加算する桁上げ型加算器とから構成されるもの であることを特徴とする並列処理装置。
8 . 請求の範囲第 1項に記載の並列処理装置において、
前記行加算手段は、 複数の前記データ出力線より入力した処理結果を集計する 複数のッリ一型加算器と、 この複数のッリ一型加算器より出力される複数の集計 結果を加算する第 1キヤリ一セーブ型加算器とから構成され、
前記蓄積加算手段は、 加算結果が格納されるレジスタと、 このレジスタから出 力させる信号， 第 1キャリーセーブ型加算器より出力された和信号， 及び桁上げ 信号を加算する第 2キヤリ一セーブ型加算器と、 この第 2キヤリ一セーブ型加算 器が出力する和信号及び桁上げ信号を加算する桁上げ型加算器とから構成され、 前記桁上げ型加算器による加算結果は、 前記レジスタに出力されることを特徴 とする並列処理装置。
9 . マトリクス状に配列された複数のセルに設けられた処理部が所定の処理を 行う第 1ステップと、
前記配列の行毎に設けられた複数のセレクト信号線の中より設定されている行 範囲に従っていずれかのセレクト信号線を選択する第 2ステップと、
選択されたセレクト信号線を選択するためのァドレス信号を生成する第 3ステ ップと、
生成されたアドレス信号により指定されるセレクト信号線に対してセレクト信 号を出力する第 4ステップと、
前記セレクト信号が出力された前記セレクト信号線に接続する複数の前記処理 部より、 前記配列の列毎に設けられた複数のデータ出力線に前記処理の結果を出 力する第 5ステップと、
設定されている列範囲に従っていずれかの前記データ出力線を選択し、 選択し たデータ出力線に出力された処理結果を加算して行加算結果を出力する第 6ステ ップと
を少なくとも備え、
前記第 2〜第 6ステップを前記配列の行毎に繰り返し、 前記行毎に得られた前 記行加算結果を加算する
ことを特徴とする並列処理方法。 ' 1 0 . 請求の範囲第 1項に記載の並列処理装置において、
前記処理部は、
静電容量を検出するセンサ素子と、
このセンサ素子で検出された容量を電気信号に変換してデジタルデータを出力 するセンサ回路と、
登録形状が記録された記録部と、
前記センサ回路の出力と前記記録部に記録された登録形状とを比較して比較結 果を出力する比較回路と
から構成されたものであることを特徴とする並列処理装置。
PCT/JP2004/001526 2003-05-23 2004-02-13 並列処理装置及び並列処理方法 Ceased WO2004104819A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP2004567189A JP3788804B2 (ja) 2003-05-23 2004-02-13 並列処理装置及び並列処理方法
US10/505,718 US7480785B2 (en) 2003-05-23 2004-02-13 Parallel processing device and parallel processing method
DE602004024995T DE602004024995D1 (de) 2003-05-23 2004-02-13 Parallelverarbeitungseinrichtung und parallelverarbeitungsverfahren
EP04711019A EP1643356B1 (en) 2003-05-23 2004-02-13 Parallel processing device and parallel processing method

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2003-146723 2003-05-23
JP2003146723 2003-05-23
JP2003271037 2003-07-04
JP2003-271037 2003-07-04

Publications (1)

Publication Number Publication Date
WO2004104819A1 true WO2004104819A1 (ja) 2004-12-02

Family

ID=33478989

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2004/001526 Ceased WO2004104819A1 (ja) 2003-05-23 2004-02-13 並列処理装置及び並列処理方法

Country Status (5)

Country Link
US (1) US7480785B2 (ja)
EP (1) EP1643356B1 (ja)
JP (1) JP3788804B2 (ja)
DE (1) DE602004024995D1 (ja)
WO (1) WO2004104819A1 (ja)

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9384004B2 (en) 2012-06-15 2016-07-05 International Business Machines Corporation Randomized testing within transactional execution
US9348642B2 (en) 2012-06-15 2016-05-24 International Business Machines Corporation Transaction begin/end instructions
US9436477B2 (en) 2012-06-15 2016-09-06 International Business Machines Corporation Transaction abort instruction
US10437602B2 (en) 2012-06-15 2019-10-08 International Business Machines Corporation Program interruption filtering in transactional execution
US9740549B2 (en) 2012-06-15 2017-08-22 International Business Machines Corporation Facilitating transaction completion subsequent to repeated aborts of the transaction
US9448796B2 (en) 2012-06-15 2016-09-20 International Business Machines Corporation Restricted instructions in transactional execution
US20130339680A1 (en) 2012-06-15 2013-12-19 International Business Machines Corporation Nontransactional store instruction
CN108427932B (zh) * 2015-10-19 2021-07-02 Oppo广东移动通信有限公司 指纹图像的识别方法及装置
US11424621B2 (en) 2020-01-28 2022-08-23 Qualcomm Incorporated Configurable redundant systems for safety critical applications

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH06187405A (ja) * 1993-08-01 1994-07-08 Hitachi Ltd 画像データ処理装置及びそれを用いたシステム
US6075876A (en) * 1997-05-07 2000-06-13 Draganoff; Georgi Hristoff Sliding yardsticks fingerprint enrollment and verification system and method
JP2001084370A (ja) * 1999-09-13 2001-03-30 Nippon Telegr & Teleph Corp <Ntt> 指紋認識装置およびデータ処理方法

Family Cites Families (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4399517A (en) * 1981-03-19 1983-08-16 Texas Instruments Incorporated Multiple-input binary adder
US4660165A (en) * 1984-04-03 1987-04-21 Trw Inc. Pyramid carry adder circuit
EP0257362A1 (de) * 1986-08-27 1988-03-02 Siemens Aktiengesellschaft Addierer
CA2021192A1 (en) * 1989-07-28 1991-01-29 Malcolm A. Mumme Simplified synchronous mesh processor
US5054090A (en) * 1990-07-20 1991-10-01 Knight Arnold W Fingerprint correlation system with parallel FIFO processor
US5148388A (en) * 1991-05-17 1992-09-15 Advanced Micro Devices, Inc. 7 to 3 counter circuit
US5187679A (en) * 1991-06-05 1993-02-16 International Business Machines Corporation Generalized 7/3 counters
US5291443A (en) * 1991-06-26 1994-03-01 Micron Technology, Inc. Simultaneous read and refresh of different rows in a dram
JP3724014B2 (ja) * 1994-08-25 2005-12-07 ソニー株式会社 画像認識装置および画像認識方法
US5963679A (en) * 1996-01-26 1999-10-05 Harris Corporation Electric field fingerprint sensor apparatus and related methods
KR100198662B1 (ko) * 1996-05-16 1999-06-15 구본준 디램 셀, 디램 및 그의 제조 방법
US6442286B1 (en) * 1998-12-22 2002-08-27 Stmicroelectronics, Inc. High security flash memory and method
EP1085426B1 (en) * 1999-09-13 2006-01-11 Nippon Telegraph and Telephone Corporation Parallel-processing apparatus and method
JP2001242771A (ja) 2000-02-29 2001-09-07 Canon Inc 画像読取装置及び画像形成装置
US6728862B1 (en) * 2000-05-22 2004-04-27 Gazelle Technology Corporation Processor array and parallel data processing methods
US7085796B1 (en) * 2000-06-08 2006-08-01 International Business Machines Corporation Dynamic adder with reduced logic
US7199897B2 (en) * 2002-02-22 2007-04-03 Ricoh Company, Ltd. Image data processing apparatus for and image data processing method of pattern matching

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH06187405A (ja) * 1993-08-01 1994-07-08 Hitachi Ltd 画像データ処理装置及びそれを用いたシステム
US6075876A (en) * 1997-05-07 2000-06-13 Draganoff; Georgi Hristoff Sliding yardsticks fingerprint enrollment and verification system and method
JP2001084370A (ja) * 1999-09-13 2001-03-30 Nippon Telegr & Teleph Corp <Ntt> 指紋認識装置およびデータ処理方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP1643356A4 *

Also Published As

Publication number Publication date
EP1643356B1 (en) 2010-01-06
JP3788804B2 (ja) 2006-06-21
EP1643356A4 (en) 2009-04-01
EP1643356A1 (en) 2006-04-05
US7480785B2 (en) 2009-01-20
JPWO2004104819A1 (ja) 2006-07-20
DE602004024995D1 (de) 2010-02-25
US20050259502A1 (en) 2005-11-24

Similar Documents

Publication Publication Date Title
JP4440603B2 (ja) 容量検出回路及び検出方法並びにそれを用いた指紋センサ
KR20180110080A (ko) 아날로그 코-프로세서
JP3788804B2 (ja) 並列処理装置及び並列処理方法
Alam et al. Exact stochastic computing multiplication in memristive memory
JP2976932B2 (ja) 画像照合回路および画像照合集積回路
CN113924621B (zh) 用于存储器内矩阵乘法的基于温度的调整
JP4883251B1 (ja) 半導体集積回路及び指数算出方法
JPS5948421B2 (ja) パリティ予測回路
CN113127911B (zh) 电力数据加密方法、装置及终端
CN113031915B (zh) 乘法器、数据处理方法、装置及芯片
CN114187944B (zh) 一种基于ReRAM的权值矩阵处理方法及装置
US5084834A (en) Digit-serial linear combining apparatus
JP2009070226A (ja) マッチング装置
CN100419668C (zh) 并行处理设备和并行处理方法
JP2007066258A (ja) 演算装置
CN111243640B (zh) 用于存储器操作的电路和方法
CN120546853B (zh) 侧信道的分析方法、装置、设备、存储介质及程序产品
JPH04218829A (ja) パリティビットジェネレータを備えるバレルシフタ
JP2001166917A (ja) 並列処理装置および並列処理方法
Tate et al. Fast template matching system using VHDL
US20240094988A1 (en) Method and apparatus with multi-bit accumulation
CN119731636A (zh) 多位累加器和具有多位累加器的存储器内计算处理器
JP4568987B2 (ja) ニューロン、及び当該ニューロンを用いて構成された階層型ニューラルネットワーク
Madireddy Approximation multiplier using three-operand binary adder
RU2029358C1 (ru) Ассоциативный вычислитель смещения центра текущего изображения от центра эталонного

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 2004567189

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 2004711019

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 10505718

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 20048000400

Country of ref document: CN

AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): BW GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWP Wipo information: published in national office

Ref document number: 2004711019

Country of ref document: EP