(57)【特許請求の範囲】
【請求項１】
ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えており、前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものであり、前記コントローラは、以下のステップを実行することを特徴とする論理回路：
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空であるか、または、前記ＦＡキューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【請求項２】
ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えており、前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものであり、前記コントローラは、以下のステップを実行することを特徴とする論理回路：
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空でなく、かつ、前記ＦＡキューのデータが、それ以前と同じアドレスへのアクセスを行うものであるときは、ＦＡキューを一つ進めて、前記（１）〜（３）の操作を行うステップ；
（５）前記ＦＡキューが空であるか、または、前記キューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【請求項３】
さらにパスセレクタを備え、前記パスセレクタは、前記デルタレジスタ中のデータを前記メモリおよび前記演算器のいずれかに送るかを選択するものであることを特徴とする請求項１または２に記載の論理回路。
【請求項４】
ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えた論理回路を用い、前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものであり、さらに、以下のステップを備えたことを特徴とする演算方法：
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空であるか、または、前記ＦＡキューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【請求項５】
ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えた論理回路を用い、前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものであり、さらに、以下のステップを備えたことを特徴とする演算方法：
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空でなく、かつ、前記ＦＡキューのデータが、それ以前と同じアドレスへのアクセスを行うものであるときは、ＦＡキューを一つ進めて、前記（１）〜（３）の操作を行うステップ；
（５）前記ＦＡキューが空であるか、または、前記ＦＡキューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【請求項６】
請求項４または５記載の演算方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項７】
前記演算器は加算器であることを特徴とする請求項１〜３のいずれか１項記載の論理回路。
【請求項８】
前記演算器は加算器であることを特徴とする請求項４または５記載の演算方法。
【請求項９】
前記演算器は加算器であることを特徴とする請求項６記載のコンピュータプログラム。
【発明の詳細な説明】
【発明の属する技術分野】
本発明は、論理回路および演算方法に関するものである。
【０００１】
【従来の技術】
従来から、共有メモリ型マルチプロセッサが知られている。この共有メモリ型マルチプロセッサは、メモリに格納されたセマフォ（同期変数）に複数のプロセッサがアクセスする方式を採用している。共有メモリ型マルチプロセッサにおいては、プロセッサを増加させて性能を向上させようとすると、同一の同期変数に対するメモリアクセスがボトルネックとなって、性能向上の妨げになる。このことは、プロセッサ数が増えるほど深刻な問題となる。
【０００２】
同一セマフォへのアクセス、すなわち、同一アドレスへのメモリアクセスを減らすことができれば、この問題は解消しうる。そのためには、同一アドレスに対する複数のアクセスを一つにまとめられるという機能を有するＦＡ（Fetch & Add）命令を使うことができる。
【０００３】
このＦＡ命令の動作を簡単に説明する。例えば、ＦＡ（ｘ，ｅ）と、ＦＡ（ｘ，ｆ）という二つの命令が同時に発行されたとする。ここで、ｘは、メモリ中の値である。このとき、メモリには、値ａが格納されているとする。このとき、ＦＡ命令では、結果的に、メモリに、ａ＋ｅ＋ｆの値を書き戻すことができる。
【０００４】
しかしながら、このＦＡ命令は、その実現のために、特殊なハードウェアを必要とする。例えば、ニューヨーク大学のウルトラコンピュータで用いられたハードウェアは、８個のプロセッサからのアクセスを一つにまとめるために、１２個ものスイッチを必要としてしまう。このため、実装が難しいという問題がある。
【０００５】
【発明が解決しようとする課題】
本発明は、前記の事情に鑑みてなされたものである。本発明は、比較的に簡易な構成でＦＡ命令を実行できる論理回路を提供することを目的としている。
【０００６】
【課題を解決するための手段】
請求項１記載の論理回路は、ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えている。前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものである。前記コントローラは、以下のステップを実行するものである。
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空であるか、または、前記ＦＡキューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【０００７】
請求項２記載の論理回路は、ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えている。前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものである。前記コントローラは、以下のステップを実行するものである。
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空でなく、かつ、前記ＦＡキューのデータが、それ以前と同じアドレスへのアクセスを行うものであるときは、ＦＡキューを一つ進めて、前記（１）〜（３）の操作を行うステップ；
（５）前記ＦＡキューが空であるか、または、前記キューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【０００８】
請求項３記載の論理回路は、請求項１または２に記載のものにおいて、さらにパスセレクタを備え、前記パスセレクタは、前記デルタレジスタ中のデータを前記メモリおよび前記演算器のいずれかに送るかを選択するように構成されている。
【０００９】
請求項４記載の演算方法は、ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えた論理回路を用いる。前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものである。さらに、この演算方法は、以下のステップを備えている。
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空であるか、または、前記ＦＡキューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【００１０】
請求項５記載の演算方法は、ＦＡキューと、ＦＡレジスタと、演算器と、デルタレジスタと、メモリと、ＦＡコントローラとを備えた論理回路を用いる。前記ＦＡキューは、複数のデータが書き込まれるものであり、前記デルタレジスタは、前記演算器からの出力を格納するものであり、前記メモリは、同期変数を格納するものである。さらに、この演算方法は、以下のステップを備えている。
（１）ＦＡキューの先頭のデータをＦＡレジスタに送るステップ；
（２）前記同期変数または前記デルタレジスタ中のデータと、前記ＦＡレジスタ中の値とを、前記演算器に送るステップ；
（３）前記演算器の出力を前記デルタレジスタに格納するステップ；
（４）前記ＦＡキューが空でなく、かつ、前記ＦＡキューのデータが、それ以前と同じアドレスへのアクセスを行うものであるときは、ＦＡキューを一つ進めて、前記（１）〜（３）の操作を行うステップ；
（５）前記ＦＡキューが空であるか、または、前記ＦＡキューのデータが、それ以前のものとは異なるアドレスへのアクセスを行うものであるときは、前記デルタレジスタ中のデータを前記メモリに同期変数として書き戻すステップ。
【００１１】
請求項６記載のコンピュータプログラムは、請求項４または５記載の演算方法をコンピュータに実行させるものである。
【００１２】
請求項７記載の論理回路は、請求項１〜３のいずれか１項記載のものにおいて、前記演算器を加算器としている。
【００１３】
請求項８記載の演算方法は、請求項４または５記載のものにおいて、前記演算器を加算器としている。
【００１４】
請求項９記載のコンピュータプログラムは、請求項６記載のものにおいて、前記演算器を加算器としている。
【００１５】
【発明の実施の形態】
本発明の実施形態に係る論理回路を、添付の図面を参照しながら説明する。まず、図１に基づいて、論理回路の構成を説明する。
【００１６】
この論理回路は、ＦＡキュー１と、ＦＡレジスタ２と、演算器の一例としての加算器３と、デルタレジスタ４と、パスセレクタ５と、メモリ６と、ＦＡコントローラ７とを主要な構成として備えている。
【００１７】
ＦＡキュー１は、複数のデータ（値）が、一定の順序で書き込まれるものである。例えば、０番にデータ０１、２番にデータ０３、３番にデータ１Ｆ、というように書き込まれて格納される。
【００１８】
ＦＡレジスタ２は、次の二つの機能を有する。第１は、ＦＡキュー１からデータを取得して、加算器３に送る機能である。第２は、デルタレジスタ４のデータを、パスセレクタ５を介して受け取り、ＦＡキュー１に返す機能である。
【００１９】
加算器３は、入力された値（正でも負でもよい）を加算し、結果をデルタレジスタ４に送るものである。
【００２０】
デルタレジスタ４は、加算器３からの出力を格納するものである。デルタレジスタ４は、加算器３の出力側に接続されている。デルタレジスタ４は、パスセレクタ５を介してメモリ６に接続されている。
【００２１】
パスセレクタ５は、デルタレジスタ４のデータを、メモリ６、加算器３またはＦＡレジスタ２に、選択的に送るものである。パスセレクタ５は、ＦＡコントローラ７からの選択信号に応じて、一つの入力を、二つの出力端子のいずれか一方に出力するものである。このとき、出力されない端子は、回路の誤動作を防ぐため、ハイインピーダンス状態とする。このような構成のパスセレクタ５を構成するための回路の例を、ハードウエア記述言語（ＨＤＬ）を用いて、図５に記載した。
【００２２】
メモリ６は、同期変数（セマフォ）を格納するものである。メモリ６は、加算器３に同期変数を送ることができるようになっている。
【００２３】
ＦＡコントローラ７は、論理回路全体の動作を制御するものである。ＦＡコントローラ７の動作を以下に説明する。
【００２４】
まず、初回の動作を、図２に基づいて説明する。はじめに、ＦＡキュー１に、並列に動作する複数のプロセッサ（図示せず）からのデータをそれぞれ格納する（ステップ２−１）。ついで、ＦＡキュー１の先頭のデータを、ＦＡレジスタ２に送る（ステップ２−２）。
【００２５】
ついで、メモリ６に格納された同期変数（セマフォ）と、ＦＡレジスタ２に格納されたデータとを、加算器３に送る（ステップ２−３）。加算器３は、両者を加算して出力する。ついで、加算器３の出力を、デルタレジスタ４に格納する（ステップ２−４）。
【００２６】
ついで、パスセレクタ５を介して、ＦＡレジスタ２に、デルタレジスタ４のデータを返す（ステップ２−５）。このとき、ＦＡコントローラ７は、パスセレクタ５の出力端として、メモリ６側でなく、ＦＡレジスタ２側を予め選択しておく。
【００２７】
ついで、ＦＡレジスタ２のデータを、ＦＡキュー１に返す（ステップ２−６）。このデータが、最初のデータをＦＡキュー１に格納したプロセッサにおける処理結果となる。ついで、ＦＡキュー１を一つ進める（ステップ２−７）。つまり、次のデータを送ることができるようになる。
【００２８】
つぎに、２回目以降の動作を、図３に基づいて説明する。まず、ＦＡキュー１が空でないかどうかを確認する（ステップ３−１）。空でなければ、ＦＡキュー１の先頭のデータをＦＡレジスタ２に送る（ステップ３−２）。ここで、先頭のデータとは、前記したステップ２−７で一つ進められたものである。したがって、初回から数えれば、これは、２番目のデータである。
【００２９】
ついで、デルタレジスタ４のデータとＦＡレジスタ２のデータとを、加算器３に送る（ステップ３−３）。すなわち、このときは、ＦＡコントローラ７は、パスセレクタ５の出力端として、メモリ６側でなく、加算器３側を予め選択しておく。ついで、加算器３の出力を、デルタレジスタ４に格納する（ステップ３−４）。
【００３０】
ついで、ＦＡレジスタ２に、デルタレジスタ４の値を返す（ステップ３−５）。すなわち、このときは、ＦＡコントローラ７は、パスセレクタ５の出力端として、メモリ６側でなく、ＦＡレジスタ２側を予め選択しておく。ついで、前記したステップ２−６および２−７と同様の動作を行う（ステップ３−６および３−７）。ついで、再び、ステップ３−１に戻る。これにより、各プロセッサからＦＡキュー１に格納されたデータを逐次処理できるとともに、処理した結果を各プロセッサに逐次的に返すことができる。
【００３１】
このように処理を進めた結果、ＦＡキュー１が空（つまり処理すべきデータがなくなった状態）になると、ステップ３−１の判断がＮｏとなる。このときは、デルタレジスタ４のデータをメモリ６に同期変数として書き戻す（ステップ３−８）。また、このときは、ＦＡコントローラ７は、パスセレクタ５の出力端として、メモリ６側を予め選択しておく。
【００３２】
なお、図３には明記していないが、もし、ＦＡキュー１のデータが、それ以前のものとは異なるメモリアドレスへのアクセスを行うものであるときは、ステップ３−１から直ちにステップ３−８に移行することが望ましい。
前記した動作の具体例を、念のために、擬似コード（pseudo code）を用いて図４に記述した。
【００３３】
また、本実施形態の論理回路を用いた演算方法は、前記したＦＡコントローラ７の動作説明から明らかなので、説明を省略する。
【００３４】
本実施形態の論理回路によれば、加算器３の出力側にデルタレジスタ４を接続したため、煩雑なデータパスやハードウエアを用いずに、ＦＡ命令を実行できるという利点がある。
【００３５】
したがって、本実施形態の論理回路によれば、ＦＡ命令実行のためのハードウエアを容易に実装することが可能となる。
【００３６】
また、本実施形態の論理回路によれば、ＦＡ命令実行の最初と最後にのみ、メモリ６にアクセスするので、メモリアクセス回数が少ない。メモリアクセスは、プロセッサの動作に比較して遅いため、メモリアクセス回数を減らすことにより、命令実行速度の向上が期待できる。
【００３７】
なお、前記各実施形態の記載は単なる一例に過ぎず、本発明に必須の構成を示したものではない。各部の構成は、本発明の趣旨を達成できるものであれば、上記に限らない。例えば、前記した実施形態では、演算器の例として加算器を示した。しかしながら、演算器としては、論理演算器であってもよい。
また、本明細書においては、ＦＡ（Fetch and Add）命令を、論理演算処理を含めた概念として用いている。
【００３８】
【発明の効果】
本発明によれば、比較的に簡易な構成でＦＡ命令を実行できる論理回路を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る論理回路の概略的な構成を示すブロック図である。
【図２】本発明の一実施形態に係る論理回路における演算手順を説明するためのフローチャートである。
【図３】本発明の一実施形態に係る論理回路における演算手順を説明するためのフローチャートである。
【図４】本発明の一実施形態に係る論理回路における演算手順の一具体例を擬似コードで記述した説明図である。
【図５】本発明の一実施形態に係る論理回路に用いるパスセレクタの回路構成例をハードウエア記述言語（ＨＤＬ）で記述した説明図である。
【符号の説明】
１  ＦＡキュー
２  ＦＡレジスタ
３  加算器（演算器）
４  デルタレジスタ
５  パスセレクタ
６  メモリ
７  ＦＡコントローラ
【図１】
0003855069.tif 000002
【図２】
0003855069.tif 000003
【図３】
0003855069.tif 000004
【図４】
0003855069.tif 000005
【図５】
0003855069.tif 000006