(57)【特許請求の範囲】
【請求項１】
第１処理手順が定められた第１単体処理ユニットと、第２処理手順が定められた第２単体処理ユニットと、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する第１処理選択手段とから構成される、第１複合処理ユニットを備えた第１ＣＰＵと、
前記第１処理手順が定められた前記第１単体処理ユニットと、前記第２処理手順が定められた前記第２単体処理ユニットと、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する第２処理選択手段とから構成される、第２複合処理ユニットを備えた第２ＣＰＵと、
前記第１ＣＰＵの第１複合処理ユニットと前記第２ＣＰＵの第２複合処理ユニットを並列的に実行する並列処理制御手段と、
を備え、
前記第１処理選択手段は、予め定義された優先順位である第１処理選択順序に従って、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択し、
前記第２処理選択手段は、前記第１処理選択順序とは異なる予め定義された優先順位である第２処理選択順序に従って、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する
ことを特徴とする並列処理方式。
【請求項２】
前記第１処理選択手段は、前記第１処理選択順序に従って選択された前記単体処理ユニットが実行可能であるか否かを判定する第１判定手段と、実行可能な前記単体処理ユニットが選択されるまで単位処理ユニットの選択動作を行うように前記第１選択手段を制御する第１選択制御手段とを備え、
前記第２処理選択手段は、前記第２処理選択順序に従って選択された前記単体処理ユニットが実行可能であるか否かを判定する第２判定手段と、実行可能な前記単体処理ユニットが選択されるまで単位処理ユニットの選択動作を行うように前記第２選択手段を制御する第２選択制御手段とを備えることを特徴とする請求項１に記載の並列処理方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のプロセッサにより並列処理を実行する並列処理方式に関するものである。
【０００２】
【従来の技術】
従来、並列処理によって実行時間を短縮しようとする方法は多数提案されてきた。
【０００３】
例えば、ベクトル演算処理に於ける並列処理がある。
【０００４】
ベクトル演算処理に於いて、例えば、下記のような制御ループがあった場合を考える。
【０００５】
【数１】
ｆｏｒ（ｉ＝１；ｉ＜ｎ；ｉ＋＋）｛
ａ［ｉ］＝ａ［ｉ］＋ａ［ｉ−１］；
ｂ［ｉ］＝ｂ［ｉ］＋ｂ［ｉ−１］；
｝
【０００６】
この場合に、これを並列処理が可能なように、下記のように分割する。
【０００７】
【数２】
ｆｏｒ（ｉ＝１；ｉ＜ｎ；ｉ＋＋）｛
ａ［ｉ］＝ａ［ｉ］＋ａ［ｉ−１］；
｝
ｆｏｒ（ｉ＝１；ｉ＜ｎ；ｉ＋＋）｛
ｂ［ｉ］＝ｂ［ｉ］＋ｂ［ｉ−１］；
｝
【０００８】
分割された前記の各制御ループに対して別々のプロセッサを割り当て、並列処理を実行することによって、実行時間の短縮を実現していた。
【０００９】
前記のベクトル演算処理に限らず、並列処理を行う場合は、並列処理を行う対象となる処理を、互いの処理結果に依存しない複数の処理ユニットに分割し、分割後の各処理ユニットを別々のプロセッサで並列処理することで、実行時間の短縮を実現する方法が提示されていた。
【００１０】
しかしながら、前記の並列処理方式に於いては、分割された処理ユニットが互いの処理結果に依存しないことが前提となっているため、前の処理の結果を受けて行う処理に於いては、並列処理の効果が得られない問題があった。
【００１１】
この問題に対し、並列処理に於いてスケジューリングを行うことによって、前の処理の結果を受けて行う処理についても並列処理の効果が得られる構成の並列処理方式が従来より提案されている。
【００１２】
図１１は、その一例として、２つの処理Ａ、Ｂをスケジューリングし、並列処理を実行した場合のタイムチャートを示した図である。
【００１３】
ここで、処理Ｂ（ｉ）（ｉ＝１、２、３…）は、処理Ａ（ｉ）（ｉ＝１、２、３…）の結果に依存した処理であり、処理Ａ（ｉ）は処理Ｂ（ｉ）の結果に依存しない処理であるとする（以下同様）。
【００１４】
この場合、処理Ｂ（１）は処理Ａ（１）より先に開始することができないが、処理Ａ（２）は処理Ｂ（１）の処理終了を待つ必要はないため、処理Ａ（１）の処理終了直後に処理を開始することが可能である。このように、処理Ｂの開始時間について矛盾が生じないようにスケジューリングすることにより、並列処理による実行時間の短縮が可能となる。
【００１５】
図１１（ａ）は、処理Ａの実行時間が処理Ｂの実行時間よりも長い場合のタイムチャートであり、図１１（ｂ）は、処理Ｂの実行時間が処理Ａの実行時間よりも長い場合のタイムチャートを示している。いずれの場合も、並列処理を行わない場合よりも全体の実行時間は明らかに短縮される。
【００１６】
【発明が解決しようとする課題】
しかしながら、上述の例のようにスケジューリングを行って並列処理を実行する場合、図１１（ａ）に示す如く、プロセッサ２に、次の処理が開始可能となる条件が満たされるまで何もできずに停止する（ストールする）時間（以下、ストール時間と称する）が発生してしまう問題があった。このストール及びストール時間は、プロセッサ資源の一部を遊ばせ、プロセッサの有する処理能力を十分に発揮させることができない問題を生じさせていた。
【００１７】
尚、図１１の処理Ａ、Ｂが、オペレーティングシステム（以下、ＯＳと記述する）の上で動作するアプリケーションプログラムである場合、図１１（ａ）のストール時間中にＯＳの処理を挿入することも可能ではある。この場合、プロセッサ２のストール時間は減少し、２個のプロセッサは休みなく動作していることにはなるが、アプリケーションプログラム自体の実行時間が短縮されるものではない。
【００１８】
また、図１１（ｂ）の場合は、プロセッサ１、プロセッサ２が休みなく動作しており、これ以上のストール時間は発生しないように見える。しかし、図示のように、処理Ｂの実行時間が処理Ａの実行時間より長い場合には、先に行われた処理Ａ（ｉ）の結果を記憶領域に格納し、その記憶領域に格納された処理Ａ（ｉ）の結果を読み出して処理Ｂ（ｉ）を実行することになるため、処理Ｂの処理が遅いと、処理Ａの実行結果を格納する記憶領域がいっぱいになり、処理Ｂの実行が処理Ａに追いつくまで（記憶領域に空き領域ができるまで）処理Ａを実行することが不可能となる。したがって、結果的に、プロセッサ１にストール時間が生じる問題があった。
【００１９】
本発明は、上述した問題を解決するためになされたものであり、ストール時間を生じること無く、柔軟なスケジューリングを可能とすることによって高速に動作することが可能な並列処理方式を提供することを目的としている。
【００２０】
【課題を解決するための手段】
この目的を達成するために、本発明の請求項１に記載の並列処理方式は、
第１処理手順が定められた第１単体処理ユニットと、第２処理手順が定められた第２単体処理ユニットと、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する第１処理選択手段とから構成される、第１複合処理ユニットを備えた第１ＣＰＵと、
前記第１処理手順が定められた前記第１単体処理ユニットと、前記第２処理手順が定められた前記第２単体処理ユニットと、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する第２処理選択手段とから構成される、第２複合処理ユニットを備えた第２ＣＰＵと、
前記第１ＣＰＵの第１複合処理ユニットと前記第２ＣＰＵの第２複合処理ユニットを並列的に実行する並列処理制御手段と、
を備え、前記第１処理選択手段は、予め定義された優先順位である第１処理選択順序に従って、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択し、前記第２処理選択手段は、前記第１処理選択順序とは異なる予め定義された優先順位である第２処理選択順序に従って、前記第１単体処理ユニット及び前記第２単体処理ユニットの中から実行すべき単体処理ユニットを選択することを特徴としている。
【００２１】
前記並列処理制御手段が第１ＣＰＵの第１複合処理ユニットと第２ＣＰＵの第２複合処理ユニットを並列的に実行する際、第１複合処理ユニットに於いて、第１処理選択手段は、第１複合処理ユニットを構成する第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択し、第２複合処理ユニットに於いて、第２処理選択手段は、第２複合処理ユニットを構成する第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する。
【００２２】
したがって、各複合処理ユニットに於いて、第１処理選択手段により選択された単体処理ユニットと第２処理選択手段により選択された単体処理ユニットが常に稼動していることになり、プロセッサのストール時間が発生せず、柔軟なスケジューリングが可能な並列処理方式を実現することができる。
【００２３】
また、第１処理選択手段は、第１処理選択順序に定義された優先順位に従って第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択し、第２処理選択手段は、第２処理選択順序に定義された優先順位に従って第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する。したがって、処理の目的に合った並列処理のスケジューリングが可能となる。
【００２４】
請求項２に記載の並列処理方式に於いて、
前記第１処理選択手段は、前記第１処理選択順序に従って選択された前記単体処理ユニットが実行可能であるか否かを判定する第１判定手段と、実行可能な前記単体処理ユニットが選択されるまで単位処理ユニットの選択動作を行うように前記第１選択手段を制御する第１選択制御手段とを備え、
前記第２処理選択手段は、前記第２処理選択順序に従って選択された前記単体処理ユニットが実行可能であるか否かを判定する第２判定手段と、実行可能な前記単体処理ユニットが選択されるまで単位処理ユニットの選択動作を行うように前記第２選択手段を制御する第２選択制御手段とを備えることを特徴としている。
【００２５】
すなわち、第１処理選択手段が、第１処理選択順序に定義された優先順位に従って単体処理ユニットを選択し、さらに、第１判定手段が、選択された単体処理ユニットが実行可能であるか否かを判定し、第１選択制御手段が、第１判定手段が実行可能であると判定するまで、第１処理選択順序に従って、順次単体処理ユニットの選択動作を繰り返し、第２処理選択手段が、第２処理選択順序に定義された優先順位に従って単体処理ユニットを選択し、さらに、第２判定手段が、選択された単体処理ユニットが実行可能であるか否かを判定し、第２選択制御手段が、第２判定手段が実行可能であると判定するまで、第２処理選択順序に従って、順次単体処理ユニットの選択動作を繰り返す。
【００２６】
【発明の実施の形態】
以下、本発明を具現化した一つの実施の形態について、図面を参照しながら説明する。
【００２７】
図１は、本実施の形態の並列制御手段である並列処理装置１００の回路構成の概略を示すブロック図である。尚、本並列処理装置１００は、２個のＣＰＵによって並列処理を実行する、いわゆる２ＣＰＵマルチプロセッサシステムとして構成されている。
【００２８】
前記並列処理装置１００は、第１複合処理ユニット１０を備えた第１ＣＰＵ１と、第２複合処理ユニット２０を備えた第２ＣＰＵ２とから構成される。
【００２９】
前記第１複合処理ユニット１０は、予め処理手順が定められた第１単体処理ユニットとしての第１処理手順１１と、予め処理手順が定められた第２単体処理ユニットとしての第２処理手順１２と、第１処理選択手段としての第１処理選択手段１３とから構成される。
【００３０】
前記第２複合処理ユニット２０も同様に、予め処理手順が定められた第１単体処理ユニットとしての第１処理手順１１と、予め処理手順が定められた第２単体処理ユニットとしての第２処理手順１２と、第２処理選択手段としての第２処理選択手段１４とから構成される。
【００３１】
前記並列処理装置１００が起動されると、前記第１ＣＰＵ１は、割り当てられた第１複合処理ユニット１０の実行を開始する。これと並行して、第２ＣＰＵ２は、割り当てられた第２複合処理ユニット２０の実行を開始する。
【００３２】
前記第１ＣＰＵ１に於いては、第１処理選択手段１３によって第１処理手順１１または第２処理手順１２の何れかが選択され、選択された処理手順に沿って処理が実行される。第２ＣＰＵ２に於いても、第２処理選択手段１４によって第１処理手順１１または第２処理手順１２の何れかが選択され、選択された処理手順に沿って処理が実行される。
【００３３】
次に、図２及び図３を参照して、第１処理選択手段１３及び第２処理選択手段１４について詳細に説明する。
【００３４】
まず、図２を参照して、第１処理選択手段１３について説明する。
【００３５】
その第１処理選択手段１３には、第１処理選択順序として、第１処理手順１１を優先して選択する単体処理ユニットの選択順序が定められている。
【００３６】
前記第１処理選択手段１３は、前記第１処理選択順序に従って、まず第１処理手順１１を選択してその実行可能性を判定し、第１処理手順１１が実行可能でない場合に第２処理手順１２を選択してその実行可能性を判定する。したがって、前記第１処理選択手段１３は、本発明の第１判定手段をも兼ねる。
【００３７】
前記第１処理選択手段１３は、最初に、第１処理手順１１の実行可能性の判定を行う（Ｓ１０）。
【００３８】
例えば、第２処理手順１２が第１処理手順１１の処理結果を利用して実行される場合、第２処理手順１２の実行可能性の判定は、第１処理手順１１の処理が終了しているか否かを判定することによって行われる。また、第１処理手順１１が第２処理手順１２の処理結果を利用して実行される場合、第１処理手順１１の実行可能性の判定は、第２処理手順１２の処理が終了しているか否かを判定することによって行われる。
【００３９】
尚、実行可能性の判定は、上述したような、処理結果の相互利用以外の要素、例えば、空きの記憶領域の存在等を考慮して行うこともできる。
【００４０】
具体例としては、例えば、第１処理手順１１が前記処理Ｂ専用である場合、第１処理手順１１の実行可能性は、処理しようとしている処理Ｂ（ｉ）に利用されるべき前記処理Ａ（ｉ）の処理結果が何れかの記憶領域内にあるか否かにより判定される。また、第１処理手順１１が前記処理Ａ専用である場合、第１処理手順１１の実行可能性は、処理しようとしている処理Ａ（ｊ）の処理結果を格納すべき空きの記憶領域が存在するか否かにより判定される。
【００４１】
上述のような実行可能性判定により、第１処理手順１１の実行が可能であると判定された場合（Ｓ１０：Ｙｅｓ）、第１処理手順１１が選択され（Ｓ１２）、処理が終了する（Ｓ２０）。
【００４２】
Ｓ１０に於いて、第１処理手順１１の実行が不可能であると判定された場合、（Ｓ１０：Ｎｏ）、第２処理手順１２の実行が可能か否かの判定が行われる（Ｓ１４）。ここで、第２処理手順１２の実行が可能であると判定された場合（Ｓ１４：Ｙｅｓ）、第２処理手順１２が選択されて（Ｓ１６）、この処理が終了する（Ｓ２０）。
【００４３】
Ｓ１４に於いて、第２処理手順１２の実行が不可能であると判定された場合には（Ｓ１４：Ｎｏ）、第１ＣＰＵ１で実行可能な処理手順が存在しないので、何も選択しないで（Ｓ１８）、この処理を終了する（Ｓ２０）。
【００４４】
第１処理選択手段１３で何も選択されなかった場合は、第１ＣＰＵ１は停止状態（ストール）となる。
【００４５】
同様に、図３を参照して、第２処理選択手段１４について説明する。
【００４６】
その第２処理選択手段１４には、第２処理選択順序として、第２処理手順１２を優先して選択する単体処理ユニットの選択順序が定められている。したがって、前記第２処理選択手段１４は、前記第２処理選択順序に従って、まず第２処理手順１２を選択してその実行可能性を判定し、第２処理手順１２の実行が可能でない場合に第１処理手順１１を選択してその実行可能性を判定する。したがって、前記第２処理選択手段１４は、本発明の第２判定手段をも兼ねる。
【００４７】
前記第２処理選択手段１４は、最初に、第２処理手順１２が実行可能か否かの判定を行う（Ｓ２２）。
【００４８】
Ｓ２２に於いて第２処理手順１２の実行が可能であると判定された場合（Ｓ２２：Ｙｅｓ）、第２処理手順１２が選択され（Ｓ２４）、処理が終了する（Ｓ３２）。
【００４９】
Ｓ２２に於いて第２処理手順１２の実行が不可能であると判定された場合には（Ｓ２２：Ｎｏ）、第１処理手順１１の実行が可能か否かの判定が行われる（Ｓ２６）。第１処理手順１１の実行が可能であると判定された場合（Ｓ２６：Ｙｅｓ）、第１処理手順１１を選択して（Ｓ２８）、この処理を終了する（Ｓ３２）。
【００５０】
Ｓ２６に於いて、第１処理手順１１の実行が不可能であると判定された場合には（Ｓ２６：Ｎｏ）、第２ＣＰＵ２で実行可能な処理手順が存在しないので、何も選択しないで（Ｓ３０）、この処理が終了する（Ｓ３２）。
【００５１】
第２処理選択手段１４で何も選択されなかった場合は、第２ＣＰＵ２は停止状態（ストール）となる。
【００５２】
次に、上述した構成を有する、本実施の形態の並列処理方式１００の動作の様子を示す具体例について説明する。
【００５３】
図４は、図１の回路ブロック図と、図２及び図３のフローチャートを複合することにより、本並列処理装置１００の動作の様子を説明するための図である。
【００５４】
ここで、本並列制御装置１００を繰り返し起動し、処理Ｂの処理結果が１０個得られた時点で処理を終了するものと設定する。
【００５５】
第１処理手順１１は、図５のタイムチャートに示すように、１０ｔの処理時間を要する処理Ａを実行し、第２処理手順１２は、５ｔの処理時間を要する処理Ｂを実行するものとする。また、前記第２処理手順１２は、前記第１処理手順１１の処理結果を使用して処理を実行するものとし、前記第１処理手順１１の処理結果が得られたことを条件として実行可能となるものとする。
【００５６】
すなわち、前記第２処理手順１２に於いて処理されるｉ番目の処理Ｂである処理Ｂ（ｉ）は、前記第１処理手順１１による処理Ａ（ｉ）の結果を利用するものである。したがって、処理Ｂ（ｉ）は処理Ａ（ｉ＋１）の前に行うことはできるが処理Ａ（ｉ）の前に行うことはできない。また、処理Ａ（ｉ）は、記憶領域に格納できる限り、いずれの処理Ｂにも先だって行うことができる。
【００５７】
また、単体処理ユニットの選択順序は、第１複合処理ユニット１０に於いては第１処理手順１１が優先する第１処理選択順序となり、第２複合処理ユニット２０に於いては第２処理手順１２が優先する第２処理選択順序となる。さらに、処理Ａの処理結果は、３個まで記憶領域に格納できるとする。
【００５８】
はじめに、第１ＣＰＵ１は第１処理手順１１を選択して処理Ａ（１）を実行する。一方、第２ＣＰＵ２では、処理Ｂ（１）を実行することが不可能なため、第２処理選択手段１４によって第２処理手順１２が選択され、処理Ａ（２）を実行する。前記処理Ａ（１）及びＡ（２）が終了する時点は、本並列制御装置１００の作動開始より１０ｔ経過後である。
【００５９】
次に、第１ＣＰＵ１は処理Ａ３を実行する。これと並行して、第２ＣＰＵ２では、処理Ｂ（１）からＢ（２）までが実行可能となったため、処理Ｂを実行し、処理Ｂ（１）及びＢ（２）の処理結果を得る。以降、同様の手順で処理を続行する。
【００６０】
以上の動作を行った結果のタイムチャートが図５である。全体の処理時間は７５ｔであり、第１ＣＰＵ１を処理Ａ、第２ＣＰＵ２を処理Ｂに固定して並列処理した場合（１０５ｔ）よりも約３０％の処理時間短縮となる。しかも、柔軟なスケジューリングにより、両ＣＰＵに於けるストール時間の発生はない。
【００６１】
さらに、上述の実施の形態の変形として、単体処理ユニットを３個備えたＣＰＵを２個用いた場合の動作について説明する。
【００６２】
基本的な全体構成は図４と同じであるが、第１複合処理ユニット１０及び第２複合処理ユニット２０を構成する単体処理ユニットの数が各々３個になる部分が異なる。
【００６３】
上述の具体例と同様に、並列処理装置１００を繰り返し起動し、処理Ｃの処理結果が５個得られた時点で処理を終了するものと設定する。
【００６４】
また、処理Ａは１０ｔ、処理Ｂは５ｔ、処理Ｃは１５ｔの処理時間を要し、処理Ｂは処理Ａの処理結果を使用し、処理Ｃは処理Ｂの処理結果を使用するものと仮定する。
【００６５】
さらに、単位処理ユニットの選択順序は、第１複合処理ユニット１０に於いては処理Ａ、処理Ｂ、処理Ｃの順序となり、第２複合処理ユニット２０に於いては処理Ｃ、処理Ｂ、処理Ａの順序となるように設定するものとし、処理Ａ、処理Ｂの処理結果は、各３個まで記憶領域に格納できるものとする。
【００６６】
以上の条件の下で動作を行った結果のタイムチャートを図６に示す。全体の処理時間は８０ｔとなる。処理後半（４５ｔ以降）では、処理Ａを全て終了した第１ＣＰＵ１が、優先順位に従って処理対象となる処理手順を選択し、第２ＣＰＵ２と共に、残りの実行可能な処理を行っていることが確認できる。このように、本実施の形態の並列処理方式によれば、各ＣＰＵで柔軟に処理手順の割り当てを行うことが可能であるため、全体の処理時間が短縮できる。
【００６７】
次に、本実施の形態の具体的な適用例として、ビットマップイメージの描画処理に適用した場合の構成と動作について図面を参照して説明する。
【００６８】
図７は、ビットマップイメージの描画処理の概略手順を示す図である。
【００６９】
ビットマップイメージデータ４０が入力されると、画素データ取得処理（ＰＸＬ）５０によって１画素のデータを取得する。続いて、色変換処理（ＣＬＲ）５１によって所望の色変換が施された後、塗りつぶし領域決定処理（ＲＧＮ）５２によって色変換された画素データを塗りつぶす領域が決定され、ハーフトーン描画処理（ＤＲＷ）５３によって、色変換された画素データをハーフトーン処理によって２値化し、先に決定された塗りつぶし領域に描画し、プリントデバイス５５に出力する。
【００７０】
以上の処理を、入力されたビットマップイメージデータ４０の全ての画素データについて繰り返すことによって、ビットマップイメージの描画処理が実行される。尚、ハーフトーン描画処理５３の部分は、出力先のプリントデバイス５５に応じてフルカラー描画処理や誤差拡散描画処理等に入れ替えが可能である。
【００７１】
図８は、図７に示すビットマップイメージ描画処理を、各処理過程での処理結果を格納する記憶領域（バッファ）を使用することにより並列処理可能に構成した処理手順を示す図である。
【００７２】
画素データ取得処理５０によって取得された画素データは、画素データバッファ６０に格納される。色変換処理５１は、画素データバッファ６０から画素データを読み出し、色変換処理を行って結果を色変換バッファ６１に格納する。塗りつぶし領域決定処理５２は、画素データの取得とは独立して実行可能である。塗りつぶし領域決定処理５２で決定された領域データは、領域データバッファ６２に格納される。ハーフトーン描画処理５３は、色変換バッファ６１から色変換された画素データを読み出してハーフトーン処理によって２値化し、領域データバッファ６２から塗りつぶし領域データを読み出して、塗りつぶし領域に描画し、プリントデバイス５５に出力する。
【００７３】
図９は、図８の構成を上述の実施の形態の並列処理方式に適用した場合の動作の詳細を説明するための図であり、図４と同様に、回路ブロック図とフローチャートとを組み合わせたものである。
【００７４】
第１ＣＰＵ１に割り当てられた第１複合処理ユニット８０は、画素データ取得処理５０、色変換処理５１、塗りつぶし領域決定処理５２、ハーフトーン描画処理５３の各単体処理ユニット、及び第１処理選択手段７０より構成される。
【００７５】
前記第１処理選択手段７０に於ける単体処理ユニットの選択順序は、ＤＲＷ、ＣＬＲ、ＰＸＬ、ＲＧＮの順に設定されている。
【００７６】
同様に、第２ＣＰＵ２に割り当てられた第２複合処理ユニット８１は、画素データ取得処理５０、色変換処理５１、塗りつぶし領域決定処理５２、ハーフトーン描画処理５３の各単体処理ユニット、及び第２処理選択手段７１より構成される。
【００７７】
前記第２処理選択手段７１に於ける単体処理ユニットの選択順序は、ＤＲＷ、ＲＧＮ、ＣＬＲ、ＰＸＬの順に設定されている。
【００７８】
したがって、第１ＣＰＵ１では主として画素データの取得、色変換の処理を行い、第２ＣＰＵ２では主として塗りつぶし領域決定処理とハーフトーン描画を行うような優先順位が設定されている。
【００７９】
ここで、ＤＲＷ、ＣＬＲ、ＰＸＬ、ＲＧＮの各処理時間が同じであると仮定した場合の実行結果のタイムチャートを図１０に示す。
【００８０】
最初、第２ＣＰＵ２に於いては、ＲＧＮが、領域データバッファ６２の記憶領域が無くなるまで連続的に実行される。これと並行して、第１ＣＰＵ１ではＰＸＬ、ＣＬＲ、ＤＲＷが順に繰り返し実行される。領域データバッファ６２の記憶領域が無くなった時点で、第１ＣＰＵ１、第２ＣＰＵ２は、記憶領域に格納されたデータを消費すべく、ＰＸＬ、ＣＬＲ、ＤＲＷの処理を実行する。
【００８１】
すなわち、先に処理できるものは、記憶領域の許容範囲で先に処理を済ませておき、ある時点で足りないデータが生じた場合は、全てのＣＰＵパワーを投入して不足データの作成に対応する。これらのサイクルを繰り返すことで、ＣＰＵを休みなく動作させることが可能となり、高速な並列処理によるビットマップイメージ描画処理が実現されることになる。
【００８２】
尚、本発明は以上に説明した実施の形態に限定されるものではなく、本発明の要旨を変更しない範囲内に於いて、種々の変形が可能である。
【００８３】
例えば、前記実施の形態に於いては、各複合処理ユニットを構成する単体処理ユニットは２つ若しくは３つずつであり、その処理内容も各複合処理ユニットで共通であったが、複合処理ユニットを構成する単体処理ユニットの数は２個以上であれば特に制限がなく、また、各複合処理ユニットに備えられる単体処理ユニットの処理内容が互いに異なっていてもよい。
【００８４】
また、単体処理ユニットの選択順序は、前記実施の形態の如く処理順序を予め定義したものに限定されず、処理順序を動的に決定する方法を予め定義たものでもよい。後者のものによれば、単体処理ユニットの処理負荷や処理内容が何らかの原因で変動することがあっても、単体処理ユニットの選択順序に定められた優先順位を柔軟に変更することが可能となる。
【００８５】
【発明の効果】
以上に説明したことから明かなように、本発明の請求項１に記載の並列処理方式によれば、並列処理制御手段が第１ＣＰＵの第１複合処理ユニットと第２ＣＰＵの第２複合処理ユニットを並列的に実行する際、第１複合処理ユニットに於いて、第１処理選択手段は、第１複合処理ユニットを構成する第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択し、第２複合処理ユニットに於いて、第２処理選択手段は、第２複合処理ユニットを構成する第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する。
【００８６】
したがって、各複合処理ユニットに於いて、第１処理選択手段により選択された単体処理ユニットと第２処理選択手段により選択された単体処理ユニットが常に稼動していることになり、プロセッサのストール時間が発生せず、柔軟なスケジューリングが可能な並列処理方式を実現することができる。
【００８７】
また、請求項１に記載の並列処理方式によれば、第１処理選択手段は、第１処理選択順序に定義された優先順位に従って第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択し、第２処理選択手段は、第２処理選択順序に定義された優先順位に従って第１単体処理ユニット及び第２単体処理ユニットの中から実行すべき単体処理ユニットを選択する。したがって、処理の目的に合った並列処理のスケジューリングが可能となる。
【００８８】
さらに、請求項２に記載の並列処理方式によれば、前の処理結果を利用した後の処理を実行する場合、後の処理が実行可能ならばその処理を実行し、前の処理が終了していないために後の処理が不可能な場合は、前の処理を選択して実行することが可能となる。すなわち、前の処理が遅れた場合には、処理の遅い前処理を複数の複合処理ユニットで処理し、複合処理ユニットのストールを防ぐことができる。
【００８９】
したがって、ストール時間を生じること無く、柔軟なスケジューリングを可能とすることによって高速に動作することが可能な並列処理方式を提供することができる。
【図面の簡単な説明】
【図１】  本発明を具現化した一つの実施の形態の並列処理方式の回路ブロック図である。
【図２】  前記並列処理方式に備えられる第１処理選択手段に於ける処理を説明するためのフローチャートである。
【図３】  前記並列処理方式に備えられる第２処理選択手段に於ける処理を説明するためのフローチャートである。
【図４】  前記並列処理装置の動作を説明するための図である。
【図５】  前記並列処理装置による動作結果を示すタイムチャートである。
【図６】  前記並列処理装置を変形した並列処理方式の動作結果を示すタイムチャートである。
【図７】  ビットマップイメージ描画処理の手順の概略を説明するための図である。
【図８】  前記ビットマップイメージ描画処理の手順の詳細を説明するための図である。
【図９】  前記ビットマップイメージ描画処理に前記実施の形態の並列処理方式を応用した場合の回路ブロック図である。
【図１０】  前記並列処理方式によるビットマップイメージ描画処理の動作結果を示すタイムチャートである。
【図１１】  従来の並列処理方式の動作結果を示すタイムチャートである。
【符号の説明】
１１  第１処理手順
１２  第２処理手順
１０  第１複合処理ユニット
２０  第２複合処理ユニット
１３  第１処理選択手段
１４  第２処理選択手段
１００  並列処理装置
【図１】
0003733678.tif 000002
【図２】
0003733678.tif 000003
【図３】
0003733678.tif 000004
【図４】
0003733678.tif 000005
【図５】
0003733678.tif 000006
【図６】
0003733678.tif 000007
【図７】
0003733678.tif 000008
【図８】
0003733678.tif 000009
【図９】
0003733678.tif 000010
【図１０】
0003733678.tif 000011
【図１１】
0003733678.tif 000012