【事件の表示】
　平成　７年特許願第　４１５３８号「順序付きマルチスレッド実行方法とその実行装置」拒絶査定に対する審判事件〔平成　８年　９月　３日出願公開、特開平　８−２２７３６４、請求項の数（２３）〕について、次のとおり審決する。
【結　論】
　原査定を取り消す。
　本願の発明は、特許すべきものとする。
【理　由】
１．手続の経緯、本件発明
　本願は、平成７年３月１日（優先権主張平成６年１２月２０日）の出願であって、その特許請求の範囲の請求項１乃至２３に係る発明は、手続補正書により補正された明細書及び図面の記載から見て、特許請求の範囲の請求項１乃至２３に記載された次の事項により特定されるものである。
「【請求項１】複数のプロセッサから構成される並列プロセッサシステムにおいて、複数のスレッドから構成される一つのプログラムをスレッド毎に並列に実行するプログラム実行方法であって、スレッドの状態として少なくとも、実行中状態、実行可能状態、待ち状態の３つの状態を有し、あるプロセッサ上で実行中状態のスレッドからフォーク動作により実行可能状態のスレッドを生成し、実行可能状態のスレッドを他のプロセッサ上で実行し、同期動作によりこれら並列に実行される複数のスレッド間のデータ依存性を保証し、あるプロセッサ上で実行中状態のスレッドが当該実行を中断して待ち状態になる場合に、他の実行可能状態のスレッドを替わりに実行し、待ち状態になった当該スレッドは同一のプロセッサ上で後で再実行されるマルチスレッド実行方法において、前記プログラムに対して一つの逐次実行パスを定め、この逐次実行パスに沿った前記プログラムの逐次的な実行におけるスレッドの終了順序としてスレッドの仮想スレッド番号を定義し、前記プログラム中の全ての同期動作が前記仮想スレッド番号の小さいスレッドから大きいスレッドへ向かってのみ前記同期動作を行なうように前記プログラムを構築し、このようにして構築された前記プログラムを前記スレッド毎に並列に実行することを特徴とする順序付きマルチスレッド実行方法。
【請求項２】全てのフォーク動作を逐次的な関数呼びだし動作に置き換えることによりプログラムに対する逐次実行パスを得ることを特徴とする請求項１記載の順序付きマルチスレッド実行方法。
【請求項３】一つのプロセッサに着目した時に、実行中状態のスレッドの仮想スレッド番号が、当該プロセッサ上で待ち状態にある全てのスレッドの仮想スレッド番号よりも小さくなるように、前記スレッドの前記プロセッサ上での実行順序を制御することを特徴とする請求項１記載の順序付きマルチスレッド実行方法。
【請求項４】スレッドが使用するアクティベーションレコード領域をスタックを用いて管理することを特徴とする請求項１記載の順序付きマルチスレッド実行方法。
【請求項５】請求項１、２、３または４のマルチスレッド実行方法を用い、並列プロセッサシステムを構成する複数のプロセッサ間で共有される順序付きマルチスレッド実行装置であって、スレッド記述子記憶装置を有し、このスレッド記述子記憶装置は複数個のスレッド記述子スロットを一列に並べて構成され、このスレッド記述子スロットはスレッドの実行に必要な情報を保持するスレッド記述子を格納する機能を持つことと、前記スレッド記述子記憶装置において、前記スレッド記述子スロットが実行可能状態のスレッドのスレッド記述子か、もしくは待ち状態のスレッドのスレッド記述子を格納することと、複数のスレッド記述子スロットに格納された複数のスレッド記述子に関して、それぞれのスレッド記述子に対応する仮想スレッド番号の大小関係に応じて、より小さな仮想スレッド番号に対応付けられたスレッド記述子がより下のスレッド記述子スロットに格納されるように、スレッド記述子記憶装置内で各スレッド記述子を一方向順序に並べて保持することと、を特徴とする順序付きマルチスレッド実行装置。
【請求項６】複数のプロセッサに対してそれぞれのスレッド記述子ポインタを記憶し、このスレッド記述子ポインタは、当該プロセッサ上で実行状態にあるスレッドが、仮想スレッド番号による一方向順序において、スレッド記述子記憶装置内のどのスレッド記述子スロット位置に相当するかを示すことを特徴とする請求項５記載の順序付きマルチスレッド実行装置。
【請求項７】あるプロセッサ上で実行中のスレッドがフォーク動作を行なった際に、当該実行可能状態のスレッドに対応するスレッド記述子を、スレッド記述子ポインタの値を用いて指示されるスレッド記述子スロットに挿入することを特徴とする請求項６記載の順序付きマルチスレッド実行装置の制御方法。
【請求項８】あるプロセッサ上で実行中のスレッドが待ち状態になった際に、スレッド記述子記憶装置内で、当該プロセッサに対応するスレッド記述子ポインタを用いて指示されるスレッド記述子スロットより下の位置の複数のスレッド記述子スロットに記憶された複数のスレッド記述子の中で、前記実行可能状態にある複数のスレッド記述子を送出可能と定義し、これら送出可能なスレッド記述子のうちの一つを選択し、当該プロセッサに当該スレッド記述子を送出するとともに、待ち状態になったスレッドのスレッド記述子を、当該プロセッサに対応するスレッド記述子ポインタの値を用いて指示されるスレッド記述子スロットへ挿入することを特徴とする請求項６記載の順序付きマルチスレッド実行装置の制御方法。
【請求項９】あるプロセッサ上で実行中のスレッドが終了した際に、スレッド記述子記憶装置内に記憶された複数のスレッド記述子の中で、当該プロセッサで前記待ち状態にあるスレッド記述子の中で最も下に位置するスレッド記述子と、それより下に位置する複数のスレッド記述子であって、他のプロセッサ上で待ち状態にあるスレッド記述子以外のスレッド記述子とを送出可能と定義し、これら送出可能なスレッド記述子の中から一つのスレッド記述子を選択し、当該スレッド記述子を当該プロセッサに送出することを特徴とする請求項６記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１０】複数のプロセッサに対して、これらのプロセッサ上で実行中状態にある複数のスレッドの間の仮想スレッド番号の相対的な大小関係に基づく順序関係を示すプロセッサ間順序関係情報を記憶し、複数のプロセッサに関するスレッド記述子ポインタが同じ前記スレッド記述子スロットを指示する場合に、前記プロセッサ間順序関係情報を用いて、当該複数のプロセッサ上で前記実行中状態にある複数のスレッド間の仮想スレッド番号に基づく順序関係を判断することを特徴とする請求項６記載の順序付きマルチスレッド実行装置。
【請求項１１】スレッド記述子記憶装置内のスレッド記述子スロットの数を越えるスレッド記述子がフォーク動作により生成された際に、前記フォーク動作を行なったプロセッサに当該スレッド記述子に対応するスレッドを逐次的に実行させることを特徴とする請求項５または６記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１２】あるプロセッサ上で実行中のスレッドが待ち状態になった際もしくは終了した際に、当該プロセッサに次に実行するスレッドを指示するためにスレッド記述子記憶装置からスレッド記述子を送出するにあたって、送出可能な複数のスレッド記述子の内、対応する仮想スレッド番号が最も小さなスレッド記述子を選択することを特徴とする請求項８または９記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１３】あるプロセッサ上で実行中のスレッドが待ち状態になった際もしくは終了した際に、当該プロセッサに次に実行するスレッドを指示するためにスレッド記述子記憶装置からスレッド記述子を送出するにあたって、送出可能な複数のスレッド記述子の内、対応する仮想スレッド番号が最も大きなスレッド記述子を選択することを特徴とする請求項８または９記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１４】あるプロセッサ上で実行中のスレッドが待ち状態になった際もしくは終了した際に、当該プロセッサに次に実行するスレッドを指示するためにスレッド記述子記憶装置からスレッド記述子を送出するにあたって、送出可能な複数のスレッド記述子のなかに前記待ち状態のスレッドのスレッド記述子が含まれている場合は、当該スレッド記述子を選択し、それ以外の場合は対応する仮想スレッド番号が最も小さなスレッド記述子を選択することを特徴とする請求項８または９記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１５】あるプロセッサ上で実行中のスレッドが待ち状態になった際もしくは終了した際に、当該プロセッサに次に実行するスレッドを指示するためにスレッド記述子記憶装置からスレッド記述子を送出するにあたって、送出可能な複数のスレッド記述子のなかに前記待ち状態のスレッドに対するスレッド記述子が含まれている場合は、対応する仮想スレッド番号が最も小さなスレッド記述子を選択し、それ以外の場合は対応する仮想スレッド番号が最も大きなスレッド記述子を選択することを特徴とする請求項８または９記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１６】あるプロセッサ上で実行中の前記スレッドが待ち状態になった際もしくは終了した際に、当該プロセッサに次に実行するスレッドを指示するためにスレッド記述子記憶装置からスレッド記述子を送出するにあたって、スレッド記述子記憶装置内に存在する待ち状態のスレッドに対するスレッド記述子の数と実行可能状態のスレッドに対するスレッド記述子の数を比較し、当該の比較結果により、送出可能な複数のスレッド記述子の内のどのスレッド記述子を選択するかを動的に定めることを特徴とする請求項８または９記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１７】あるプロセッサ上で実行中の前記スレッドが待ち状態になった際もしくは終了した際に、当該プロセッサに次に実行するスレッドを指示するためにスレッド記述子記憶装置からスレッド記述子を送出するにあたって、スレッド記述子記憶装置内に存在する待ち状態のスレッドに対するスレッド記述子の数と実行可能状態のスレッドに対するスレッド記述子の数を比較し、待ち状態スレッドに対するスレッド記述子の方が多い場合は送出可能な複数のスレッド記述子の内、対応する仮想スレッド番号が最も小さなスレッド記述子を選択し、実行可能状態のスレッドに対するスレッド記述子の数が多い場合は、対応する仮想スレッド番号が最も大きなスレッド記述子を選択することを特徴とする請求項１６記載の順序付きマルチスレッド実行装置の制御方法。
【請求項１８】前記スレッド記述子スロットに付随させて送出可能フラグスロットを設け、あるプロセッサ上で実行中のスレッドが待ち状態になった際に、スレッド記述子記憶装置内で、当該プロセッサに対応するスレッド記述子ポインタを用いて指示されるスレッド記述子スロットより下の位置の複数のスレッド記述子スロットに記憶された複数のスレッド記述子の中で、前記実行可能状態にある複数のスレッド記述子を送出可能と判断し、あるいは、あるプロセッサ上で実行中のスレッドが終了した際に、スレッド記述子記憶装置内に記憶された複数のスレッド記述子の中で、当該プロセッサで前記待ち状態にあるスレッド記述子の中で最も下に位置するスレッド記述子と、それより下に位置する複数のスレッド記述子であって、他のプロセッサ上で待ち状態にあるスレッド記述子以外のスレッド記述子と、を送出可能と判断し、送出可能と判断されたスレッド記述子の中で、更にこの送出可能フラグスロットに送出可能フラグがセットされたスレッド記述子スロットに格納されたスレッド記述子のみを送出可能と限定し、これらの限定された送出可能な複数のスレッド記述子の中から一つを選択し、当該プロセッサに当該スレッド記述子を送出することを特徴とする請求項５の順序付きマルチスレッド実行装置。
【請求項１９】実行可能状態スレッド記述子送出可能化装置を有し、この装置は、ある一つのスレッドからフォークされて前記スレッド記述子記憶装置に格納されている実行可能状態のスレッド記述子の中で、最も先にフォークされたスレッド記述子に対して、対応する送出可能フラグスロットに送出可能フラグをセットするように働くことを特徴とする請求項１８記載の順序付きマルチスレッド実行装置。
【請求項２０】複数のプロセッサに対してそれぞれのスレッドスイッチフラグを記憶し、このスレッドスイッチフラグは、当該プロセッサ上で実行中状態にあるスレッドが、その実行開始後にスレッドをフォークしていない場合にのみセットされていることを特徴とする請求項１９記載の実行可能状態スレッド記述子送出可能化装置。
【請求項２１】待ち状態スレッド記述子送出可能化装置を有し、この待ち状態スレッド記述子送出可能化装置は、前記スレッド記述子記憶装置に格納されている待ち状態のスレッド記述子の中で、同期待ちが成立したスレッド記述子に対して、対応する送出可能フラグスロットに送出可能フラグをセットするように働くことを特徴とする請求項１８記載の順序付きマルチスレッド実行装置。
【請求項２２】同期バッファを有し、この同期バッファは同期待ちがまだ成立していない待ち状態スレッド記述子とこれに対応する同期待ちのアドレスの対を一組にして、これらの組を複数個格納し、これらの格納された同期待ちのアドレスを用いて、同期付き書き込み時に、待ち状態のスレッド記述子の同期待ちが成立したかどうかを検査することを特徴とする請求項２１記載の待ち状態スレッド記述子送出可能化装置。
【請求項２３】限定された送出可能なスレッド記述子の内、最も上位または最も下位に位置するスレッド記述子を送出することを特徴とする請求項１８記載の順序付きマルチスレッド実行装置。」
２．原査定の理由
　これに対して、原査定の拒絶の理由は、この出願は、平成８年１２月１９日付け拒絶理由通知書に記載した理由２によって、拒絶するというものであり、その理由２の中で、
「この出願は、明細書及び図面の記載が下記の点で、特許法第３６条第４項、第５項及び第６項に規定する要件を満たしていない。
　　　　　　　　　記
１．発明の詳細な説明には、下記の記載不備がある。
（１）第５１コラムの、「実行状態にある・・・持つことを示している」という記載は、何故そのようになるのか不明である。
（２）第５３コラムの、「ここで、当該の・・・示している」という記載は、何故そのようになるのか不明である。
（３）第５８コラムの末尾の「上を指す・・・１加算される」という記載は、第８図の記載と矛盾している（第８図で、第２のステップの前後でのポインタ２の内容は２から３に変化しており、「上」を指していないポインタの値も１加算されている）。
（４）第６３コラムの「その代わりに最も上に位置する」という記載では、最も大きい仮想スレッド番号を持っているスレッドが選択されることになり、何故そのような選択をしても順序性が崩れないのか不明である。
（５）第７０コラムの「最も大きいもの」、第７１コラムの「最も大きいもの」、第７２コラムの「最も上に位置するもの」、第７３コラムの「最も上に位置する」という記載についても、上記（４）と同様。
２．特許請求の範囲には、下記の記載不備がある。
（１）乃至（３）省略
（４）請求項１３，１４，１７の「最も大きな」という記載と、請求項２３の「最も上位」という記載は、上記１．の（４）と（５）で指摘した事項に対応しており、発明の構成を明確に把握できない。
（５）及び（６）省略」と指摘し、
　また、拒絶査定の備考においては、
「先の拒絶理由通知書において、理由２の１．の（４）及び（５）で指摘した記載不備は、明細書第３９コラムの記載と矛盾しており、したがって、記載不備は依然として解消されていない。出願人は意見書において、「送出可能とは順序性を崩さないということであるから、明らか」と述べているが、１．の（４）及び（５）で指摘した記載箇所について、何故「順序性を崩さないということ」が保証されるのか不明である。
　また、この１．の（４）及び（５）に対応した２．の（４）に係る記載不備も、依然として解消されていない。」との指摘がなされている。
３．当審の判断　　　　　　　　　　　　　　　　　　　　　　　　　
　本発明の特徴は、複数のプロセッサから構成される並列プロセッサシステムにおいて、複数のスレッドから構成される一つのプログラムをスレッド毎に並列に実行する際に、実行するスレッドの順序関係を把握し、ある一つのプロセッサ１１０上で実行中のスレッド２１０が当該のプロセッサ１１０で待ち状態のスレッド２１０よりも小さい仮想スレッド番号２１１を持つようにスレッド２１０の実行を制御する点にあると認められる。
（１）乃至（３）については、平成９年２月１４日付け手続補正により記載不備は解消したと認められる。
（４）について；
　補正されたコラム３９は「--あるプロセッサ１１０上で実行中のスレッド２１０の仮想スレッド番号２１１が、当該プロセッサ１１０上で待ち状態にある全てのスレッド２１０の仮想スレッド２１０の仮想スレッド番号２１１よりも小さくなるように任意のプロセッサ上で、実行可能なスレッド２１０から実行するスレッド２１０を選択することにある。より具体的には、図１および図２の実施例において、----待ち状態に入った場合には、----当該プロセッサで待ち状態にある全てのスレッド２１０の仮想スレッド番号２１１よりも小さな仮想スレッド番号２１１を持つ実行可能状態のスレッド２１０に対応する複数のスレッド記述子１４１の中から一つを選択して送出する----終了した場合には----当該プロセッサで待ち状態にある全てのスレッド２１０の仮想スレッド番号２１１よりも小さな仮想スレッド番号２１１を持つ実行可能状態のスレッド２１０に対応する複数のスレッド記述子１４１の中から一つを選択して送出するか、もしくは----待ち状態にあるスレッド２１０の中で最も小さな--」とある。
　これは、任意の一つのプロセッサ１１０において実行中状態と待ち状態にあるスレッド２１０の順序関係が規定されていると認められる。
（当該プロセッサ上で待ち状態スレッドが全くない場合については以下に記載される。）
　コラム６３は「ここで、当該プロセッサ１１０上で待ち状態にあるスレッド２１０に対するスレッド記述子１４１が見つからない場合は」とあり、更に、「その代わりに最も上に位置するスレッド記述子１４１を格納するスレッド記述子スロッド５４１を探し出し、これを代わりに用いて上に説明した方法で、スレッド記述子１４１の選択を行う。」とある。
　これらは、コラム６２、図９に記載されるような条件〔待ち状態の最も下に位置する「ｅ：３」を捜し、それ以下の一つが選ばれ送出される；たとえばｃ〕で、ある一つのプロセッサ１１０で実行中状態と待ち状態にあるスレッド２１０に関して、その順序関係を変えず保っており、あるプロセッサ１１０上で待ち状態のスレッド２１０がない場合は、そのプロセッサ１１０上では、実行可能なスレッド２１０であればどのスレッドでも実行してよい（最も大きい仮想スレッド番号を持っているスレッドが選択されてもよい＝いずれそれが待ち状態になるとしても）ことと認められる。
（５）について；
　コラム７０、コラム７１、コラム７２、コラム７３は、図１１（ａ）（ｂ）（ｃ）（ｄ）の複数の送出可能なスレッド記述子１４１から一つを選択する４つの実施例を説明している。
（送出可能なスレッド記述子の中で、という限定が記載されている。）
　これらも、コラム６２、図９に記載されるような条件〔待ち状態の最も下に位置する「ｅ：３」を捜し、それ以下の一つが選ばれ送出される；たとえばｃ〕で、ある一つのプロセッサ１１０で実行中状態と待ち状態にあるスレッド２１０に関して、その順序関係を変えず保っており、あるプロセッサ１１０上で待ち状態のスレッド２１０がない場合は、そのプロセッサ１１０上では、送出可能なスレッドであればどのスレッドでも実行してよい（最も大きい仮想スレッド番号を持っているスレッドが選択されてもよい＝いずれそれが待ち状態になるとしても）ことと認められる。
　以上の点を勘案すると、（４）及び（５）、並びに、（４）及び（５）に対応した２．の（４）の点に記載不備があるとすることはできないと認められる。
４．まとめ                     
　したがって、したがって、この出願は、特許法第３６条第４項、第５項及び第６項に規定する要件を満たしていないという原査定の判断は妥当ではない。
　また、他に本願を拒絶すべき理由を発見しない。
  よって、結論のとおり審決する。