(57)【特許請求の範囲】
【請求項１】
複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理装置において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、
画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、
上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、
上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、算出した画像ブロック単位で、上記各プロセッサが上記コーナーターン処理を実行するように上記共有メモリの対象領域を割り付けるメモリ割付手段とを
備えたことを特徴とする並列画像処理装置。
【請求項２】
画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像サイズが上記画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保するメモリ確保手段を
備えたことを特徴とする請求項１記載の並列画像処理装置。
【請求項３】
画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定するアクセス方向指定手段を
備えたことを特徴とする請求項１記載の並列画像処理装置。
【請求項４】
画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段に設定されているプロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定する多重書き込み対応アクセス方向指定手段を
備えたことを特徴とする請求項１記載の並列画像処理装置。
【請求項５】
画像サイズが算出した画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保するメモリ確保手段と、
上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定するアクセス方向指定手段と、
上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段に設定されているプロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定する多重書き込み対応アクセス方向指定手段と、
上記画像サイズが上記画像ブロックの整数倍にならない時に、その修正方法の判定条件を設定しているはみ出し修正方法設定手段とを
備えたことを特徴とする請求項１記載の並列画像処理装置。
【請求項６】
要求仕様として与えられる時間制約と各プロセッサの処理時間等の時間制約条件を設定している処理時間制約設定手段と、
実際に使用する上記プロセッサの個数を画像処理プログラムに指定する実行プロセッサ数指定手段とを
備えたことを特徴とする請求項１記載の並列画像処理装置。
【請求項７】
画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像へのアクセスパターンを算出し、画像処理プログラムに指定する画素アクセス順序指定手段を
備えたことを特徴とする請求項１記載の並列画像処理装置。
【請求項８】
複数の画像サイズを持つ各画像を対象にコーナーターン処理を行う時に、上記各画像に対して、キャッシュのラインサイズが画素サイズの整数倍にならない場合に画素の補間を行うと共に、算出した画像ブロックの整数倍で、かつ、処理対象画像を包含する最小の画像サイズを算出し、算出した各画像の最小の画像サイズの中から最大の画像サイズを選択し、選択した上記最大の画像サイズの領域を共有メモリ上に確保する複数サイズ対応メモリ確保手段を
備えたことを特徴とする請求項１記載の並列画像処理装置。
【請求項９】
複数サイズ対応メモリ確保手段が確保した共有メモリの対象領域を使用し、確保の対象となった画像よりも小さいサイズの画像処理を行う時に、選択された小さいサイズの画像に対する画像ブロック単位で、コーナーターン処理に使用する共有メモリの使用範囲を算出し、算出した使用範囲で上記コーナーターン処理を実行するように、各プロセッサに処理対象の領域やアクセス手順を指定する複数サイズ対応アクセス制御手段を
備えたことを特徴とする請求項８記載の並列画像処理装置。
【請求項１０】
複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理装置において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、
画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、
上記各プロセッサに搭載されている多階層のキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、
上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、１次キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、
上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した１次キャッシュの画像ブロックをもとに、キャッシュの階層ごとに低位キャッシュの複数の画像ブロックを包含し１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、算出した最上位キャッシュの画像ブロック単位でコーナーターン処理を実行し、かつ、上記最上位キャッシュの画像ブロックを実行する個数が上記プロセッサ間で均等になるように、上記各プロセッサへ上記共有メモリの対象領域を割り付けるよう上記画像処理プログラムに指示する多階層キャッシュ対応メモリ割付手段とを
備えたことを特徴とする並列画像処理装置。
【請求項１１】
画像サイズが最上位キャッシュの画像ブロックの整数倍にならない時に、上記画像サイズが上記最上位キャッシュの画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保する多階層キャッシュ対応メモリ確保手段を
備えたことを特徴とする請求項１０記載の並列画像処理装置。
【請求項１２】
上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない時に、上記上位キャッシュのラインサイズが、上記低位キャッシュの画像ブロックの整数倍になるように、上記低位キャッシュの画像ブロックの領域を拡張して共有メモリ上に確保する多階層画像ブロック用メモリ確保手段を
備えたことを特徴とする請求項１０記載の並列画像処理装置。
【請求項１３】
画像サイズが算出した最上位キャッシュの画像ブロックの整数倍にならない時に、上記最上位キャッシュの画像ブロックの行又は列を上記最上位キャッシュの画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段に設定されているプロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定する多階層キャッシュ対応アクセス方向指定手段を
備えたことを特徴とする請求項１０記載の並列画像処理装置。
【請求項１４】
算出した画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像又は低次のキャッシュへのアクセスパターンを指定する多階層キャッシュ対応アクセスパターン指定手段を
備えたことを特徴とする請求項１０記載の並列画像処理装置。
【請求項１５】
複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理装置において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、
画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、
上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、
上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、
上記コーナーターン処理の前に実行する事前実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記事前実行処理と上記コーナーターン処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける前処理対応メモリ割付手段とを
備えたことを特徴とする並列画像処理装置。
【請求項１６】
複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理装置において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、
画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、
上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、
上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、
上記コーナーターン処理の後に実行する事後実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記コーナーターン処理と上記事後実行処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける後処理対応メモリ割付手段とを
備えたことを特徴とする並列画像処理装置。
【請求項１７】
複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理装置において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、
画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、
上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、
上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、
上記コーナーターン処理の前に実行する事前実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記事前実行処理と上記コーナーターン処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける前処理対応メモリ割付手段と、
上記コーナーターン処理の後に実行する事後実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記コーナーターン処理と上記事後実行処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける後処理対応メモリ割付手段と、
上記コーナーターン処理と同時に実行する上記事前実行処理又は上記事後実行処理を選択する前後処理選択手段とを
備えたことを特徴とする並列画像処理装置。
【請求項１８】
複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理方法において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、
画像処理で使用する上記プロセッサの個数情報を入手し、
上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を入手し、
入手した画像情報とキャッシュ情報により、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、
入手した上記プロセッサの個数情報により、算出した上記画像ブロック単位で、上記各プロセッサが上記コーナーターン処理を実行するように上記共有メモリの対象領域を割り付ける
ことを特徴とする並列画像処理方法。
【請求項１９】
画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像サイズが上記画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保することを特徴とする請求項１８記載の並列画像処理方法。
【請求項２０】
画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定することを特徴とする請求項１８記載の並列画像処理方法。
【請求項２１】
画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、プロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定することを特徴とする請求項１８記載の並列画像処理方法。
【請求項２２】
画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像へのアクセスパターンを算出し指定することを特徴とする請求項１８載の並列画像処理方法。
【請求項２３】
複数の画像サイズを持つ各画像を対象にコーナーターン処理を行う時に、上記各画像に対して、キャッシュのラインサイズが画素サイズの整数倍にならない場合に画素の補間を行うと共に、算出した画像ブロックの整数倍で、かつ、処理対象画像を包含する最小の画像サイズを算出し、算出した各画像の最小の画像サイズの中から最大の画像サイズを選択し、選択した上記最大の画像サイズの領域を共有メモリ上に確保することを特徴とする請求項１８記載の並列画像処理方法。
【請求項２４】
確保した共有メモリの対象領域を使用し、確保の対象となった画像よりも小さいサイズの画像処理を行う時に、選択された小さいサイズの画像に対する画像ブロック単位で、コーナーターン処理に使用する共有メモリの使用範囲を算出し、算出した使用範囲で上記コーナーターン処理を実行するように、各プロセッサに処理対象の領域やアクセス手順を指定することを特徴とする請求項２３記載の並列画像処理方法。
【請求項２５】
複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理方法において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、
画像処理で使用する上記プロセッサの個数情報を入手し、
上記各プロセッサに搭載されている多階層のキャッシュの構成やサイズ等のキャッシュ情報を入手し、
入手した上記画像情報と上記キャッシュ情報により、１次キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、
入手した上記画像情報と上記キャッシュ情報により、算出した１次キャッシュの画像ブロックをもとに、キャッシュの階層ごとに低位キャッシュの複数の画像ブロックを包含し１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、
入手した上記プロセッサの個数情報により、算出した最上位キャッシュの画像ブロック単位でコーナーターン処理を実行し、かつ、上記最上位キャッシュの画像ブロックを実行する個数が上記プロセッサ間で均等になるように、上記各プロセッサへ上記共有メモリの対象領域を割り付ける
ことを特徴とする並列画像処理方法。
【請求項２６】
画像サイズが最上位キャッシュの画像ブロックの整数倍にならない時に、上記画像サイズが上記最上位キャッシュの画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保することを特徴とする請求項２５記載の並列画像処理方法。
【請求項２７】
上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない時に、上記上位キャッシュのラインサイズが、上記低位キャッシュの画像ブロックの整数倍になるように、上記低位キャッシュの画像ブロックの領域を拡張して共有メモリ上に確保することを特徴とする請求項２５記載の並列画像処理方法。
【請求項２８】
画像サイズが算出した最上位キャッシュの画像ブロックの整数倍にならない時に、上記最上位キャッシュの画像ブロックの行又は列を上記最上位キャッシュの画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、プロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定することを特徴とする請求項２５記載の並列画像処理方法。
【請求項２９】
算出した画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像又は低次のキャッシュへのアクセスパターンを指定することを特徴とする請求項２５記載の並列画像処理方法。
【請求項３０】
複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理方法において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、
画像処理で使用する上記プロセッサの個数情報を入手し、
上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を入手し、
入手した上記画像情報と上記キャッシュ情報により、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、
上記コーナーターン処理の前に実行する事前実行処理の内容を入手し、
入手した上記画像情報、上記プロセッサの個数情報、上記キャッシュ情報、上記事前実行処理の内容により、算出した上記画像ブロック単位を基準として上記事前実行処理と上記コーナーターン処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける
ことを特徴とする並列画像処理方法。
【請求項３１】
複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示する並列画像処理方法において、
処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、
画像処理で使用する上記プロセッサの個数情報を入手し、
上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を入手し、
入手した上記画像情報と上記キャッシュ情報により、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、
上記コーナーターン処理の後に実行する事後実行処理の内容を入手し、
入手した上記画像情報、上記プロセッサの個数情報、上記キャッシュ情報、上記事後実行処理の内容により、算出した画像ブロック単位を基準として上記コーナーターン処理と上記事後実行処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける
ことを特徴とする並列画像処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、共有メモリ型の並列計算機上で実行する画像処理において、プロセッサへの共有メモリの割り当てと、プロセッサの共有メモリへのアクセス制御に係る並列画像処理装置及び並列画像処理方法に関するものである。
【０００２】
【従来の技術】
画像処理の高速化手法の１つに、複数のプロセッサを使った並列処理がある。並列処理は、画像処理内での依存関係が少なく、画像サイズが大きいケースや処理負荷が高いケースで有効である。このような画像処理の１つに、ＳＡＲ（Ｓｙｎｔｈｅｔｉｃ  Ａｐｅｒｔｕｒｅ  Ｒａｄａｒ：合成開口レーダ）画像の再生処理がある。
【０００３】
ＳＡＲ画像再生処理を並列処理する従来例として、特開昭５８−２２９８２号公報の「合成開口レーダの画像処理システム」がある。図５６は従来システムの構成を示すブロック図である。図において、１０１はＳＡＲ受信画像データを記憶している磁気テープ、１０２は磁気テープ１０１に記憶されているＳＡＲ受信画像データをレンジ方向にライン単位に圧縮処理するレンジ方向圧縮装置、１０３−１，１０３−２は、レンジ方向圧縮済画像データをコーナーターン（縦横転置）処理するための２次元画像メモリ、１０４は、２次元画像メモリ１０３−１，１０３−２をアクセスする２次元画像メモリ制御部である。
【０００４】
また、図５６において、１０５はコーナーターンされたデータをアジマス方向に圧縮するアジマス方向圧縮装置、１０６は圧縮された画像データを記憶する磁気テープ、１０７は全体システムの制御を行うＣＰＵ、１０８はＣＰＵ１０７のメインメモリ、１０９は高速フーリエ変換を行う共通データ用ＦＦＴ（Ｆａｓｔ
Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）装置、１１０はデータバスである。
【０００５】
なお、ＳＡＲ画像再生処理については、特開昭５８−２２９８２号公報に記載されている他、「合成開口レーダ画像ハンドブック」（朝倉書店、飯坂譲二監修、日本写真測量学会編、１９９８年５月２０日  初版第１冊）等の市販の書籍にも記載されているので、説明を省略する。
【０００６】
次に動作について説明する。
ここでは、各処理フェーズを実行する処理装置を設けてパイプラインで実行している。また、レンジ方向圧縮装置１０２とアジマス方向圧縮装置１０５も、パイプラインで実行される。また、レンジ方向圧縮装置１０２とアジマス方向圧縮装置１０５では、内部でＦＦＴやＩＦＦＴ（Ｉｎｖｅｒｓｅ  Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ，高速逆フーリエ変換）を行う装置を複数用意して、並列実行を行うことも可能である。
【０００７】
レンジ方向圧縮済画像データに対しデータ転置を行うコーナーターン処理は、２次元画像メモリ１０３−１，１０３−２を使って高速に実行する。ここでは、パイプラインでの処理速度のギャップを埋めるために、２個の２次元画像メモリ１０３−１，１０３−２を設け、交替で利用するための２次元画像メモリ制御部１０４を備えている。
【０００８】
上記のように、この装置は、各処理フェーズ毎に専用の処理装置を設け、処理フェーズごとに、別々の装置で処理を順次パイプライン実行していく、ＳＡＲ画像再生処理の専用システムである。また、２次元画像メモリ１０３−１，１０３−２や２次元画像メモリ制御部１０４のような専用のメモリ装置を使って、コーナーターンを実行する。また、専用のＨ／Ｗ（Ｈａｒｄｗａｒｅ）を利用したシステムとしては、特開昭５８−１９１９７９号公報にも記載されている。上記のような専用のＨ／Ｗと２次元画像メモリを利用したシステムは、特に、コーナーターン処理を高速に行えるが、一般的に実現コストは高くなる。
【０００９】
一方、並列処理の実現方法の１つに、コスト的に有利な汎用の並列計算機を利用した共有メモリ密結合型のＳＭＰ（Ｓｙｍｔｅｒｉｃ  Ｍｕｌｔｉ  Ｐｒｏｃｅｓｓｏｒ）がある。図５７はＳＭＰの構成の一例を示すブロック図である。図５７において、１２１，１２２，１２３，１２４はプロセッサで、１２５は共有メモリである。ここでは、４個のプロセッサの例であるが、プロセッサは任意の個数で構成することが可能である。なお、ＳＭＰは、共有結合密結合型の並列計算機の中で、各プロセッサが同等の機能を有するものである。
【００１０】
ＳＭＰでは、図５６に示した２次元メモリ１０３−１，１０３−２を使用せずに、共有メモリ１２５を複数のプロセッサ１２１〜１２４で共有するため、これを有効に利用することで、プロセッサ１２１〜１２４間のデータ転送を効率良く行うことができる。また、画像処理の並列化を行う場合でも、この共有メモリ１２５を有効に利用できるか否かが、処理の効率化を考えるうえで、大きなポイントとなる。
【００１１】
上記の従来システムである特開昭５８−２２９８２号公報や特開昭５８−１９１９７９号公報は、専用システムにおいて処理を並列に実行できるが、ＳＭＰ構成をとっておらず、共有メモリを有効に利用するための手段を有していない。また、ＳＡＲ画像再生処理を並列処理する従来例としては、上記のような専用システム等を用いた例はあるが、共有メモリ型のＳＭＰ構成を有した従来例はなく、コーナーターン処理を行うプロセッサのキャッシュメモリの制御方法に関する従来例もない。
【００１２】
次にＳＭＰ構成でのＳＡＲ画像再生処理の並列化方法について説明する。
まず、ＳＡＲ画像再生処理の特徴を示す。
（１）各処理部分単位では、処理結果への依存性が低く、並列実行可能な部分が多い。
（２）処理にレンジ及びアジマスの方向性があり、各方向別に行と列の処理を割り当てる（例：レンジを行、アジマスを列）。例えば、レンジ方向の処理では、レンジを行、アジマスを列として、行（レンジ）方向に処理を進めていく。
（３）処理の途中でコーナーターン処理と呼ぶ行と列の方向を転置する処理を行う。
（４）１つの画像に対して順次処理を行う。すなわち、処理結果を次々に利用して処理を行う。
（５）画像サイズが大きく、処理に時間がかかる。
【００１３】
上記のような特徴を持つＳＡＲ画像再生処理を、図５７に示すＳＭＰで実装する場合には、次のような実装方法を、容易に考えることができる。
（１）共有メモリ１２５上に、処理前と処理後の領域を確保する。
（２）使用可能なプロセッサ１２１〜１２４の数に応じて、任意の個数で画像を分割して並列実行する。
【００１４】
図５８及び図５９はＳＭＰでのＳＡＲ画像再生処理を実行する方法の一例である。共有メモリ１２５の利用方法としては、図５８に示すように、（１）各処理毎に処理前と処理後の共有メモリ１２５を切り替えて使用する方法や、図５９のように、（２）処理毎に共有メモリ１２５を割り当てて順次利用する方法や、（３）両者を組み合わせる方法等を容易に考えることができる。
【００１５】
次に共有メモリ型計算機でのキャッシュ操作について説明する。
ＳＭＰの各プロセッサ１２１〜１２４では、共有メモリ１２５の内容をキャッシュと呼ぶ高速小容量のメモリにコピーして使用（読み書き）する。そして、プロセッサ１２１〜１２４のキャッシュ内に存在しないデータへの読み込みが発生した時には、共有メモリ１２５からキャッシュへデータをコピーする。キャッシュは通常、複数の等量の記憶領域（キャッシュのラインと呼ぶ）に分割されている。データの読み込みは、このライン単位で実行する。
【００１６】
また、データの読み込み時に、キャッシュのラインが全て埋まっている場合には、１つのラインを選択して、新規のデータと入れ換える。この入れ換え対象の選択方法としては、アクセス頻度や最終アクセス時刻等を利用する方法がある。このキャッシュへのデータの読み込みを、キャッシュのリードミス時の処理と呼ぶ。
【００１７】
共有メモリ１２５の同じ場所が、異なったプロセッサでキャッシュ（キャッシュメモリ上にデータとして存在していること）されている時に、データの書き込みが起きると、データの一貫性を保つための処理が行われる。この処理方法としては、書き込みデータをそのまま共有メモリ１２５上に書き込むライトスルー方式と、データの書き込まれたキャッシュのデータを、キャッシュのブロック（ライン）単位で共有メモリ１２５に書き戻すライトバック方式がある。このキャッシュのデータの一貫性を保つための処理時間を、キャッシュのライトミス時の処理と呼ぶ。
【００１８】
上記のキャッシュのリードミス時の処理にかかる時間と、ライトミス時の処理にかかる時間は、並列処理の性能低下の要因となるオーバヘッド時間である。
【００１９】
なお、共有メモリ型計算機でのキャッシュ操作については、「並列処理マシン」（富田  眞治・末吉  敏則著、オーム社、コンピュータアーキテクチャシリーズ・電子情報通信学会編）や、「並列計算機アーキテクチャ」（奥川  峻史著、コロナ社）等の市販の書籍に記載されているので、詳細は省略する。
【００２０】
キャッシュ操作によるオーバヘッド時間では、ライトミス時の時間は、一般にリードミス時の時間よりも大きい。ライトミスが頻発すると、そのオーバヘッド時間により、並列処理の性能を著しく低下させる原因となる。このため、ライトミスを低減することが、並列処理を効率良く動作させる時の大きなポイントになる。
【００２１】
従来のＳＭＰでの実装方法を利用した場合、コーナーターン処理で、キャッシュミスを引き起こし易い問題がある。これを図６０，図６１を使って説明する。図６０は、プロセッサ１２１とプロセッサ１２２が割り付けた画像上の領域を示す図である。図６１は、図６０に対する共有メモリ１２５上の位置を示す図である。図６０及び図６１において、斜線の部分はキャッシュの範囲を示している。キャッシュは、各ライン単位で、共有メモリ１２５の連続した領域を対象にデータを格納している。
【００２２】
図６０に示すように、プロセッサ１２１とプロセッサ１２２では、それぞれ異なったレンジ方向の領域を割り付けて処理を行っている。この割付方法は、レンジ方向に処理を進める場合に、連続した領域を順次アクセスしていくので、キャッシュのリードミスを抑える効果がある。また、コーナーターン処理以外のＳＡＲ画像処理では、書き込みも同じ方向（この場合レンジ方向）に行い、ライトミスも起こりにくい。
【００２３】
【発明が解決しようとする課題】
従来の並列画像処理装置は以上のように構成されているので、コーナーターン処理では、図６０に示すように、書き込み方向（レンジ方向）が読み込み方向（レンジ方向）と異なり、各プロセッサ１２１，１２２がデータを書き込むメモリ領域は、図６１に示すように、読み込みとは異なり、各プロセッサの書き込み領域が同じキャッシュの範囲に重なる可能性が高く、キャッシュのライトミスが起こりやすくなり、オーバーヘッド時間が多くなるという課題があった。
【００２４】
なお、ここでは、ＳＡＲ画像再生処理の例で説明したが、ＳＡＲ画像再生処理と同様に、各処理部分では、処理に方向性があり、処理結果への依存性が低く、途中でコーナーターン処理を実施する画像処理では、同じ課題が発生する。
【００２５】
この発明は上記のような課題を解決するためになされたもので、キャッシュの情報と、画像サイズと、使用可能なプロセッサ数の情報から、各プロセッサがコーナーターン処理を実行する画像の範囲とアクセス方法を制御することで、キャッシュのライトミスを低減し、オーバーヘッド時間を低減することができる並列画像処理装置及び並列画像処理方法を得ることを目的とする。
【００２６】
また、キャッシュのライトミスだけでなく、リードしたデータを全て使用しない時に発生するリードミスについても考慮し、最終的なオーバーヘッド時間を低減することができる並列画像処理装置及び並列画像処理方法を得ることを目的とする。
【００２７】
【課題を解決するための手段】
この発明に係る並列画像処理装置は、複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、算出した画像ブロック単位で、上記各プロセッサが上記コーナーターン処理を実行するように上記共有メモリの対象領域を割り付けるメモリ割付手段とを備えたものである。
【００２８】
この発明に係る並列画像処理装置は、画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像サイズが上記画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保するメモリ確保手段を備えたものである。
【００２９】
この発明に係る並列画像処理装置は、画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定するアクセス方向指定手段を備えたものである。
【００３０】
この発明に係る並列画像処理装置は、画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段に設定されているプロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定する多重書き込み対応アクセス方向指定手段を備えたものである。
【００３１】
この発明に係る並列画像処理装置は、画像サイズが算出した画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保するメモリ確保手段と、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定するアクセス方向指定手段と、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段に設定されているプロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定する多重書き込み対応アクセス方向指定手段と、上記画像サイズが上記画像ブロックの整数倍にならない時に、その修正方法の判定条件を設定しているはみ出し修正方法設定手段とを備えたものである。
【００３２】
この発明に係る並列画像処理装置は、要求仕様として与えられる時間制約と各プロセッサの処理時間等の時間制約条件を設定している処理時間制約設定手段と、実際に使用する上記プロセッサの個数を画像処理プログラムに指定する実行プロセッサ数指定手段とを備えたものである。
【００３３】
この発明に係る並列画像処理装置は、画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像へのアクセスパターンを算出し、画像処理プログラムに指定する画素アクセス順序指定手段を備えたものである。
【００３４】
この発明に係る並列画像処理装置は、複数の画像サイズを持つ各画像を対象にコーナーターン処理を行う時に、上記各画像に対して、キャッシュのラインサイズが画素サイズの整数倍にならない場合に画素の補間を行うと共に、算出した画像ブロックの整数倍で、かつ、処理対象画像を包含する最小の画像サイズを算出し、算出した各画像の最小の画像サイズの中から最大の画像サイズを選択し、選択した上記最大の画像サイズの領域を共有メモリ上に確保する複数サイズ対応メモリ確保手段を備えたものである。
【００３５】
この発明に係る並列画像処理装置は、複数サイズ対応メモリ確保手段が確保した共有メモリの対象領域を使用し、確保の対象となった画像よりも小さいサイズの画像処理を行う時に、選択された小さいサイズの画像に対する画像ブロック単位で、コーナーターン処理に使用する共有メモリの使用範囲を算出し、算出した使用範囲で上記コーナーターン処理を実行するように、各プロセッサに処理対象の領域やアクセス手順を指定する複数サイズ対応アクセス制御手段を備えたものである。
【００３６】
この発明に係る並列画像処理装置は、複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、上記各プロセッサに搭載されている多階層のキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、１次キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した１次キャッシュの画像ブロックをもとに、キャッシュの階層ごとに低位キャッシュの複数の画像ブロックを包含し１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、算出した最上位キャッシュの画像ブロック単位でコーナーターン処理を実行し、かつ、上記最上位キャッシュの画像ブロックを実行する個数が上記プロセッサ間で均等になるように、上記各プロセッサへ上記共有メモリの対象領域を割り付けるよう上記画像処理プログラムに指示する多階層キャッシュ対応メモリ割付手段とを備えたものである。
【００３７】
この発明に係る並列画像処理装置は、画像サイズが最上位キャッシュの画像ブロックの整数倍にならない時に、上記画像サイズが上記最上位キャッシュの画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保する多階層キャッシュ対応メモリ確保手段を備えたものである。
【００３８】
この発明に係る並列画像処理装置は、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない時に、上記上位キャッシュのラインサイズが、上記低位キャッシュの画像ブロックの整数倍になるように、上記低位キャッシュの画像ブロックの領域を拡張して共有メモリ上に確保する多階層画像ブロック用メモリ確保手段を備えたものである。
【００３９】
この発明に係る並列画像処理装置は、画像サイズが算出した最上位キャッシュの画像ブロックの整数倍にならない時に、上記最上位キャッシュの画像ブロックの行又は列を上記最上位キャッシュの画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段に設定されているプロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定する多階層キャッシュ対応アクセス方向指定手段を備えたものである。
【００４０】
この発明に係る並列画像処理装置は、算出した画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像又は低次のキャッシュへのアクセスパターンを指定する多階層キャッシュ対応アクセスパターン指定手段を備えたものである。
【００４１】
この発明に係る並列画像処理装置は、複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、上記コーナーターン処理の前に実行する事前実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記事前実行処理と上記コーナーターン処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける前処理対応メモリ割付手段とを備えたものである。
【００４２】
この発明に係る並列画像処理装置は、複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、上記コーナーターン処理の後に実行する事後実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記コーナーターン処理と上記事後実行処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける後処理対応メモリ割付手段とを備えたものである。
【００４３】
この発明に係る並列画像処理装置は、複数のプロセッサと共有メモリを含むプラットホーム上で動作し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する画像処理プログラムに上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を設定している画像情報設定手段と、画像処理で使用する上記プロセッサの個数情報を設定している使用プロセッサ数設定手段と、上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段と、上記画像情報設定手段に設定されている画像情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出するメモリ割付手段と、上記コーナーターン処理の前に実行する事前実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記事前実行処理と上記コーナーターン処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける前処理対応メモリ割付手段と、上記コーナーターン処理の後に実行する事後実行処理の内容を入手すると共に、上記画像情報設定手段に設定されている画像情報、上記使用プロセッサ数設定手段に設定されている上記プロセッサの個数情報、上記キャッシュ情報設定手段に設定されているキャッシュ情報を入手し、上記メモリ割付手段が算出した画像ブロック単位を基準として上記コーナーターン処理と上記事後実行処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付ける後処理対応メモリ割付手段と、上記コーナーターン処理と同時に実行する上記事前実行処理又は上記事後実行処理を選択する前後処理選択手段とを備えたものである。
【００４４】
この発明に係る並列画像処理方法は、複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、画像処理で使用する上記プロセッサの個数情報を入手し、上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を入手し、入手した画像情報とキャッシュ情報により、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、入手した上記プロセッサの個数情報により、算出した上記画像ブロック単位で、上記各プロセッサが上記コーナーターン処理を実行するように上記共有メモリの対象領域を割り付けるものである。
【００４５】
この発明に係る並列画像処理方法は、画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像サイズが上記画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保するものである。
【００４６】
この発明に係る並列画像処理方法は、画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定するものである。
【００４７】
この発明に係る並列画像処理方法は、画像サイズが算出した画像ブロックの整数倍にならない時に、上記画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、プロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定するものである。
【００４８】
この発明に係る並列画像処理方法は、画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像へのアクセスパターンを算出し指定するものである。
【００４９】
この発明に係る並列画像処理方法は、複数の画像サイズを持つ各画像を対象にコーナーターン処理を行う時に、上記各画像に対して、キャッシュのラインサイズが画素サイズの整数倍にならない場合に画素の補間を行うと共に、算出した画像ブロックの整数倍で、かつ、処理対象画像を包含する最小の画像サイズを算出し、算出した各画像の最小の画像サイズの中から最大の画像サイズを選択し、選択した上記最大の画像サイズの領域を共有メモリ上に確保するものである。
【００５０】
この発明に係る並列画像処理方法は、確保した共有メモリの対象領域を使用し、確保の対象となった画像よりも小さいサイズの画像処理を行う時に、選択された小さいサイズの画像に対する画像ブロック単位で、コーナーターン処理に使用する共有メモリの使用範囲を算出し、算出した使用範囲で上記コーナーターン処理を実行するように、各プロセッサに処理対象の領域やアクセス手順を指定するものである。
【００５１】
この発明に係る並列画像処理方法は、複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、画像処理で使用する上記プロセッサの個数情報を入手し、上記各プロセッサに搭載されている多階層のキャッシュの構成やサイズ等のキャッシュ情報を入手し、入手した上記画像情報と上記キャッシュ情報により、１次キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、入手した上記画像情報と上記キャッシュ情報により、算出した１次キャッシュの画像ブロックをもとに、キャッシュの階層ごとに低位キャッシュの複数の画像ブロックを包含し１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、入手した上記プロセッサの個数情報により、算出した最上位キャッシュの画像ブロック単位でコーナーターン処理を実行し、かつ、上記最上位キャッシュの画像ブロックを実行する個数が上記プロセッサ間で均等になるように、上記各プロセッサへ上記共有メモリの対象領域を割り付けるものである。
【００５２】
この発明に係る並列画像処理方法は、画像サイズが最上位キャッシュの画像ブロックの整数倍にならない時に、上記画像サイズが上記最上位キャッシュの画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保するものである。
【００５３】
この発明に係る並列画像処理方法は、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない時に、上記上位キャッシュのラインサイズが、上記低位キャッシュの画像ブロックの整数倍になるように、上記低位キャッシュの画像ブロックの領域を拡張して共有メモリ上に確保するものである。
【００５４】
この発明に係る並列画像処理方法は、画像サイズが算出した最上位キャッシュの画像ブロックの整数倍にならない時に、上記最上位キャッシュの画像ブロックの行又は列を上記最上位キャッシュの画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、プロセッサの個数の整数倍にならない時に、上記画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定するものである。
【００５５】
この発明に係る並列画像処理方法は、算出した画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像又は低次のキャッシュへのアクセスパターンを指定するものである。
【００５６】
この発明に係る並列画像処理方法は、複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、画像処理で使用する上記プロセッサの個数情報を入手し、上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を入手し、入手した上記画像情報と上記キャッシュ情報により、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、上記コーナーターン処理の前に実行する事前実行処理の内容を入手し、入手した上記画像情報、上記プロセッサの個数情報、上記キャッシュ情報、上記事前実行処理の内容により、算出した上記画像ブロック単位を基準として上記事前実行処理と上記コーナーターン処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付けるものである。
【００５７】
この発明に係る並列画像処理方法は、複数のプロセッサと共有メモリを使用し、画像の行方向と列方向の並びを転置するコーナーターン処理を含む画像の再生処理を実行する際に、上記複数のプロセッサへの上記共有メモリの対象領域の割り付けを指示するものにおいて、処理対象画像のサイズや各画素のデータサイズ等の画像情報を入手し、画像処理で使用する上記プロセッサの個数情報を入手し、上記各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を入手し、入手した上記画像情報と上記キャッシュ情報により、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、上記コーナーターン処理の後に実行する事後実行処理の内容を入手し、入手した上記画像情報、上記プロセッサの個数情報、上記キャッシュ情報、上記事後実行処理の内容により、算出した画像ブロック単位を基準として上記コーナーターン処理と上記事後実行処理を同時に実行し、上記各プロセッサの負荷が均等になるように、上記各プロセッサに上記共有メモリの対象領域を割り付けるものである。
【００５８】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１はこの発明の実施の形態１による並列画像処理装置の構成を示すブロック図である。図において、１はＳＡＲ画像の再生処理を実行する画像処理プログラム、２は、ＳＭＰの並列計算機における、図５７に示す各プロセッサ１２１〜１２４や共有メモリ１２５，キャッシュ等のＨ／Ｗ（Ｈａｒｄｗａｒｅ），ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ），並列化ライブラリ等により構成されたプラットホームで、３は、プラットホーム２上で動作し、コーナーターン処理における各プロセッサ１２１〜１２４への共有メモリ１２５の対象領域の割り付け方法等を画像処理プログラム１に指示する並列画像処理装置である。
【００５９】
また、図１の並列画像処理装置３において、１１は、処理対象画像のサイズ（画素数）、各画素のデータサイズ、コーナーターン処理前後に実行可能な処理情報等の処理対象の画像情報を設定している画像情報設定手段、１２は画像処理で使用するプロセッサの個数情報を設定している使用プロセッサ数設定手段、１３は各プロセッサに搭載されているキャッシュの構成やサイズ等のキャッシュ情報を設定しているキャッシュ情報設定手段、１４は、画像情報設定手段１１，使用プロセッサ数設定手段１２，キャッシュ情報設定手段１３の各情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる処理領域の画像ブロックを算出し、算出した画像ブロック単位で、各プロセッサがコーナータウン処理を実行するように共有メモリの対象領域を割り付けるよう、画像処理プログラム１に指示するメモリ割付手段である。
【００６０】
図２はこの発明の実施の形態１による並列画像処理装置の処理を示すフローチャートで、図３は並列画像処理装置３での基本的なメモリ割り付けの概念を示す図で、図４はこの並列画像処理装置３を利用した時の各プロセッサでのキャッシュアクセスの概念を示す図である。
【００６１】
図５は具体的なメモリ割り付けの実行例を示す図である。ここでは、処理対象画像を、１画素当たり８Ｂｙｔｅで、画像サイズはレンジ方向２０４８画素×アジマス方向１６３８４画素と仮定している。また、プロセッサに搭載されているキャッシュは、データキャッシュ、１ライン当たり３２Ｂｙｔｅ×５１２ライン、１次キャッシュのみを仮定している。
【００６２】
図６は１画像ブロックを複数プロセッサで処理する一例を示す図である。この例では、各プロセッサに割り付けた処理は、途中で退避させないものとする。また、共有メモリ１２５上に処理前と処理後の領域を確保して、レンジ方向の処理（行：レンジ、列：アジマス）からアジマス方向の処理（行：アジマス、列：レンジ）へコーナーターン処理するものとする。
【００６３】
並列画像処理装置３は、プラットホーム２上で動作し、コーナーターン処理でのメモリの割り付け方法等を画像処理プログラム１に指示するが、並列画像処理装置３の実装法としては、並列化支援ライブラリとして独立して提供する方法、プラットホーム２であるＯＳや並列化ライブラリへ組み込む方法、画像処理プログラム１の中へ組み込む方法がある。この実施の形態では、並列化支援ライブラリとして独立して提供する方法で説明する。
【００６４】
次に動作について説明する。
画像情報設定手段１１は、処理対象画像の情報として、画像のサイズ（画素数）、各画素のデータサイズ、コーナーターン処理前後に実行可能な処理情報等を設定している。この例では、１画素当たり８Ｂｙｔｅ，画像サイズはレンジ方向２０４８画素×アジマス方向１６３８４画素という情報を設定している。画像情報設定手段１１への画像情報の設定は、ユーザ入力等により手動で行う他、画像データや画像処理プログラム１から自動的に行うこともできる。
【００６５】
使用プロセッサ数設定手段１２は、画像処理で使用するプロセッサの個数情報を設定している。この個数情報は、最大利用可能なプロセッサの個数であり、基本的に、指定された個数で画像処理を行う。使用プロセッサ数設定手段１２へのプロセッサの個数情報の設定は、画像処理プログラム１の中で指定する方法やユーザ入力等で行う方法が考えられる。
【００６６】
キャッシュ情報設定手段１３は、プロセッサに搭載されているキャッシュの構成（階層型や１次キャッシュのみか等）、各ライン毎のサイズ（容量）、ライン数、一貫性保持方法、データの退避順序、ライトミスとリードミスにかかるオーバーヘッド時間、データをキャッシュへ読み書きするのにかかる時間等のキャッシュ情報を設定している。
【００６７】
この例では、プロセッサに搭載されているキャッシュは、データキャッシュ、１ライン当たり１６Ｂｙｔｅ×５１２ライン、１次キャッシュのみ、一貫性保持方法はライトバック、データの退避順序は最終アクセス時刻順とする。キャッシュ情報設定手段１３へのキャッシュ情報の設定は、ユーザ入力等により手動で行う他、システムが用意するＩ／Ｆ（Ｉｎｔｅｒｆａｃｅ）経由等で自動的に行うこともできる。
【００６８】
次にメモリ割付手段１４の動作について説明する。
メモリ割付手段１４は、図２のステップＳＴ１において、キャッシュ情報設定手段１３からキャッシュ情報を入手し、ステップＳＴ２において、画像情報設定手段１１から画像情報を入手し、ステップＳＴ３において、使用プロセッサ数設定手段１２から使用するプロセッサの個数情報を入手する。
【００６９】
ステップＳＴ４において、メモリ割付手段１４は、ステップＳＴ１で入手したキャッシュ情報と、ステップＳＴ２で入手した画像情報に基づき、処理単位である画像ブロックを算出する。画像ブロックは、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる処理領域であり、ここでは、１辺の長さが１キャッシュラインサイズの正方形の画像上の領域である。
【００７０】
ステップＳＴ４における画像ブロックの算出後に、ステップＳＴ５において、メモリ割付手段１４は、ステップＳＴ３で入手した使用プロセッサ数の情報に基づき、各プロセッサ１２１〜１２４が算出された画像ブロック単位でコーナーターンを行うように共有メモリ１２５の対象領域を割り付けるよう、画像処理プログラム１に指示する。画像処理プログラム１では、外部から指定された共有メモリ１２５の領域毎に、各プロセッサ１２１〜１２４でコーナーターン処理するようにプログラムされている。
【００７１】
処理前画像の画像ブロックには、コーナーターン処理後に対応する処理結果画像の画像ブロックでの書き込みに必要なデータが全て含まれ、また、読み込まれた画像ブロックのデータは、全て処理結果画像の画像ブロックに書き込まれる。
【００７２】
図５７に示す複数プロセッサ１２１〜１２４で、コーナーターン処理を行う時に、各プロセッサ１２１〜１２４が担当する画像領域について、画像ブロックを重ねなければ書き込みによるキャッシュのライトミスは起こらない。このため、算出された画像ブロック単位で、重なりなくコーナーターン処理を行うことで、書き込み側でのキャッシュのライトミスをなくすことができる。また、データの読み込みも、最小限の１回だけで済むので、キャッシュのリードミスによるオーバヘッド時間を最小に抑えることができる。
【００７３】
図３に、画像ブロック単位での、複数プロセッサによるコーナーターン処理の概要を示す。ここでは、プロセッサ１２１とプロセッサ１２２は、それぞれ異なった画像ブロックを担当している。このため、処理前画像と処理結果画像のそれぞれの画像領域で、キャッシュするデータが重ならずに、コーナーターン処理を実行している。
【００７４】
図４に画像ブロック単位でのコーナーターン処理を行っている時の各プロセッサ内部でのキャッシュの使用状況を示す。ここでは、画像ブロック単位でのコーナーターン処理を行うのに十分なライン数のキャッシュがあると仮定している。このため、読み込みと書き込みに、それぞれ別のキャッシュラインを割り当て、画像ブロック単位でのコーナーターン処理を、必要なデータの退避なしに実行している。
【００７５】
図５を使って具体的な実行例を示す。
図５における１，２，３，…の番号は、各画素の番号であり、処理前と処理結果の画像間では、コーナーターン処理前の読み込み位置と、コーナーターン処理後の書き込み位置で対応している。また、画像とメモリ空間の間では、それぞれ対応する位置を示している。
【００７６】
ここでは、キャッシュのラインサイズが３２ｂｙｔｅなので、画像ブロックは３２ｂｙｔｅ×３２ｂｙｔｅ分の領域となる。１画素のデータが８ｂｙｔｅなので、１つのキャッシュラインに４画素分のデータが格納され、画像ブロックは４画素×４画素の画像上の領域となる。全画像データは、レンジ方向２０４８画素×アジマス方向１６３８４画素なので、５１２×４０９６の画像ブロックとなる。
【００７７】
画像ブロックは画像上の領域のため、共有メモリ１２５の空間上は不連続の領域になる。図５に示すように、１キャッシュラインのサイズ（４画素）単位の領域が、共有メモリ１２５の空間上に散在している。
【００７８】
画像ブロック単位でのコーナーターン処理を、図５における画素番号１〜１６で示す。読み込み側では、（１，２，３，４），（５，６，７，８），（９，１０，１１，１２），（１３，１４，１５，１６）の４個のキャッシュラインとして読み込まれる。コーナーターン処理後の書き込みでは、（１，５，９，１３），（２，６，１０，１４），（３，７，１１，１５），（４，８，１２，１６）の４個のキャッシュラインとして書き込まれる。
【００７９】
なお、各画像ブロック内のコーナーターン処理では、処理間で依存関係がなく、全てのデータがプロセッサ１２１〜１２４内のキャッシュにあることを前提としているので、どの画素から処理を実行しても良い。
【００８０】
この操作を、５１２×４０９６の画像ブロックで実行することで、画像全体でのコーナーターン処理を実行する。
【００８１】
図２に示すステップＳＴ５において、各プロセッサ１２１〜１２４へ画像ブロックを割り付ける時には、プロセッサ１２１〜１２４間での処理負荷を均等した方が効率が良い。各画像ブロック間の処理には、依存関係がないので、任意の画像ブロックを、任意のプロセッサ１２１〜１２４へ割り付けて並列実行できる。このため、基本的には、各プロセッサ１２１〜１２４に割り付ける画像ブロックの個数に注目し、処理負荷が等しくなるように割り付ける。
【００８２】
一方で、この並列画像処理装置では、画像サイズとプロセッサ数を任意に設定できるため、画像ブロックを均等に分割できないケースがある。この場合、図６に示すように、１つの画像ブロックを複数のプロセッサ１２１〜１２４で実行することもできる。
【００８３】
図６では、４個のプロセッサ１２１〜１２４が、それぞれ処理前画像側の画像ブロック内のデータを全て読み込む。処理結果画像への書き込みでは、お互いの書き込み先キャッシュが重ならないように、画像ブロック内の指定されたラインにのみデータを書き込む。このため、読み込んだデータの一部を無駄にするリードミスがあるが、書き込みでのライトミスはおこさない。また、各プロセッサ１２１〜１２４での処理間には依存関係がないので、並列に処理を実行できる。
【００８４】
通常、１プロセッサで実行する場合は、４ライン分のデータを読み込み、４ライン分のデータを書き込むが、この処理方法では、各プロセッサ１２１〜１２４で４ライン分のデータを読み込み、１ライン分のデータを書き込んでいる。
【００８５】
このため、１画像ブロックの処理時間としては、１プロセッサで実行する場合より処理時間が短い。ただし、処理対象の画像ブロックの個数が増える。図６の例では、１画像ブロックあたりでは、３ライン分のデータ書き込み時間が短くなる。キャッシュへのデータのリードとライト時間が同等とすると５／８倍時間が短くなる。一方、処理すべき画像ブロックの個数は４倍に増える。
【００８６】
ＳＡＲ画像処理では、一般に画像サイズが大きいために、プロセッサ１２１〜１２４の個数と比較して、処理すべき画像ブロックの個数が大きい。この場合には、まず画像ブロック単位で処理を分割し、割り切れない余りとなった画像ブロックだけを、２個以上のプロセッサ１２１〜１２４で分割して実行することが考えられる。
【００８７】
逆に、画像サイズが小さく、プロセッサ１２１〜１２４の個数と比較して、処理すべき画像ブロックの個数が小さい場合には、画像ブロックを複数のプロセッサ１２１〜１２４で分割して実行することにより、処理時間を短縮することもできる。
【００８８】
この実施の形態では、ＳＡＲ画像再生処理に適用しているが、ＳＡＲ画像再生処理以外でも、コーナーターン処理に相当する処理を実行する並列画像処理に対しても適用できる。
【００８９】
この実施の形態では、画像のサイズやキャッシュのサイズを設定しているが、任意の画像（画素サイズや画像の画素数）、任意のキャッシュ（構成、ライン数、サイズ、一貫性保持方法、データの退避順序等）、任意の個数のプロセッサでも良い。
【００９０】
この実施の形態では、（行：レンジ、列：アジマス）から（行：アジマス、列：レンジ）へのコーナーターン処理を実行しているが、（行：アジマス、列：レンジ）から（行：レンジ、列：アジマス）のコーナーターン処理でも良い。また、レンジ、アジマスが規定されていない画像処理であっても、コーナーターン処理と同等の画像処理内容であれば良い。
【００９１】
この実施の形態では、並列画像処理装置３の実装法として、並列化支援ライブラリとして独立して提供されているが、プラットホーム２であるＯＳや並列化ライブラリへ組み込む方法、又は画像処理プログラム１へ組み込む方法でも良い。
【００９２】
この実施の形態では、画像処理プログラム１に処理領域を指定することで、各プロセッサの処理領域を設定していたが、プラットホーム２の機能等を使って、並列画像処理装置３が直接指定する方法で実装しても良い。
【００９３】
この実施の形態では、各プロセッサに割り付けた処理は、途中で退避させられないことを仮定しているが、１画像ブロック単位の処理が途中で退避させられない限り、タイムシェアリングシステムのようなある周期で退避されるようなシステムであっても良い。また、１画像ブロック単位の処理が退避させられるケースでも、退避されたプロセッサと新たに実行を行うプロセッサ間でしか、キャッシュのライトミスをおこさないため、キャッシュのライトミスの確率は低い。
【００９４】
この実施の形態では、コーナーターン処理単独の例で説明したが、一連の画像処理をＳＭＰ上でパイプライン処理する場合にでも、そのコーナーターン処理部分にこの並列画像処理装置３を適用しても良い。
【００９５】
以上のように、この実施の形態１によれば、画像の縦方向と横方向の並びを転置するコーナーターン処理を実行する時に、画像サイズ（画素数）や各画素のデータサイズ等の処理対象の画像情報と、キャッシュの構成やサイズやキャッシュライン数やキャッシュの一貫性保持方法等のキャッシュ情報から、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる処理領域の画像ブロックを算出し、画像ブロック単位で処理を実行するように、並列に動作する複数のプロセッサ１２１〜１２４へ処理対象位置の共有メモリ１２５の対象領域を、各プロセッサ１２１〜１２４間で重ねないように割り付けることで、書き込みによるキャッシュのライトミスを起こさず、かつ、データの読み込みも、最小限の１回だけで済ませることができ、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【００９６】
また、画像処理に使用するプロセッサ１２１〜１２４の個数の情報から、処理対象の画像を画像ブロック単位で、各プロセッサ１２１〜１２４に均等に割り振ることにより、並列処理において効果的な負荷分散を行い、効率の良いコーナーターン処理を実現できるという効果が得られる。
【００９７】
さらに、負荷分散を行う時に、１画像ブロックの処理を複数のプロセッサ１２１〜１２４により行うことで、より公平な負荷分散が行えると共に、１画像ブロックの処理を高速化できるという効果が得られる。
【００９８】
実施の形態２．
図７はこの発明の実施の形態２による並列画像処理装置の構成を示すブロック図である。図において、１５は、画像サイズが算出した画像ブロックの整数倍にならない時に、画像サイズが画像ブロックの整数倍になるように画像領域を拡張して共有メモリ１２５上に確保するメモリ確保手段であり、その他は実施の形態１の図１に示す構成と同等である。図８はこの実施の形態２による並列画像処理装置の処理を示すフローチャートであり、図９はメモリ確保の実行例を示す図である。この実施の形態では、算出した画像サイズが画像ブロックサイズの整数倍にならない点が、実施の形態１と異なっている。
【００９９】
次に動作について説明する。
図８のステップＳＴ１からＳＴ４の画像ブロックを計算する処理までは、実施の形態１と同じである。ステップＳＴ１１において、メモリ割付手段１４は、画像サイズが、算出した画像ブロックの整数倍になるかをチェックする。チェックの結果、画像サイズが、算出した画像ブロックの整数倍になる場合は、実施の形態１と同様に、ステップＳＴ５において、メモリ割付手段１４は、共有メモリ１２５の領域の各プロセッサ１２１〜１２４への割付を、画像処理プログラム１に指示する。
【０１００】
上記ステップＳＴ１１で、画像サイズが、算出した画像ブロックの整数倍にならない場合には、メモリ確保手段１５は、メモリ割付手段１４の指示により、図９に示すように、画像サイズが画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ１２５上に確保する。
【０１０１】
この例では、メモリ確保手段１５が画像処理プログラム１に画像のサイズを指定することで、画像処理プログラム１により画像領域が拡張される。拡張された画像領域は、コーナーターン処理の際には、他の部分と同様に実行されるが、コーナーターン処理以外の処理では無視される。
【０１０２】
図９（ａ）に、アジマス方向で画像サイズが画像ブロックの整数倍とならない例を示す。ここでは、キャッシュラインに、任意の位置からデータを読み込めると仮定する。整数倍とならないために、このまま処理すると、画像処理後のデータの右端での書き込みが、次の行の左端のキャッシュに影響を与える。例えば、Ａ，Ｅを書き込もうとすると、（Ａ，Ｅ，２，６）という単位でキャッシュに書き込む。一方で、左上端の画像ブロックでは、（２，６，１０，１４）の単位でキャッシュに書き込む。このように、（２，６）を管理するキャッシュが２つあることになり、この２つのキャッシュ間でライトミスが発生する。
【０１０３】
なお、ラインサイズの整数倍のアドレスから読み込む場合でも、キャッシュラインには、（Ａ，Ｅ，２，６）と（１０，１４，・，・，）という単位でしか書き込めなくなり、読み込んだ画像ブロックをそのまま書き込むと、キャッシュのライトミスが発生する。
【０１０４】
ここで、図９（ｂ）のように、画像サイズが画像ブロックの整数倍になるように、処理対象の画像領域を拡張して共有メモリ１２５上に確保する。拡張後の画像全体を対象にコーナーターン処理を行うことで、実施の形態１と同じ方法で実行できる。
【０１０５】
この実施の形態では、アジマス方向の画像サイズが画像ブロックの整数倍にならない場合であるが、レンジ方向の画像サイズが画像ブロックの整数倍にならない場合は、レンジ方向に画像サイズの領域を増やせば良く、また、アジマスとレンジの両方向の画像サイズが画像ブロックの整数倍にならない場合は、両方向に画像サイズの領域を増やせば良い。
【０１０６】
この実施の形態では、画像サイズの領域を増やす量も任意に設定できる。このため、上記実施の形態以外のキャッシュや画像サイズを指定された場合でも、同様の手法で画像サイズの領域を増やせば良い。
【０１０７】
この実施の形態では、画像サイズの領域を拡張して共有メモリ１２５上の確保する方法として、画像処理プログラム１が指定された領域量を確保しているが、メモリ確保手段１５が共有メモリ１２５の領域を確保して、画像処理プログラム１へ使用先を指定しても良い。この場合、共有メモリ１２５の確保サイズを知らせず、画像処理プログラム１では、メモリ割付手段１４が、拡張領域も含めて画像ブロックで指定した範囲をコーナーターン処理するように指示しても良い。
【０１０８】
以上のように、この実施の形態２によれば、コーナーターン処理を行う時に、処理対象の画像サイズが画像ブロックの整数倍にならない時に、画像サイズが画像ブロックの整数倍になるように、処理対象の画像領域を拡張して共有メモリ１２５上に確保することにより、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【０１０９】
実施の形態３．
図１０はこの発明の実施の形態３による並列画像処理装置の構成を示すブロック図である。図において、１６は、画像サイズが算出した画像ブロックの整数倍にならない時に、画像ブロック幅の行又は列を画像ブロックの帯として算出し、算出した画像ブロックの帯で画像のアクセス方向を指定するアクセス方向指定手段で、その他は実施の形態１の図１に示す構成と同等である。この実施の形態では、実施の形態２と同様に、画像サイズが画像ブロックサイズの整数倍にならない点が実施の形態１と異なっている。
【０１１０】
図１１はこの実施の形態３による並列画像処理装置の処理を示すフローチャートで、図１２は、アジマス方向の画像サイズが画像ブロックの整数倍にならない時に、アクセス方向を指定した処理内容を示す図であり、図１３は、レンジ方向の画像サイズが画像ブロックの整数倍にならない時に、アクセス方向を指定した処理内容を示す図である。
【０１１１】
次に動作について説明する。
図１１のステップＳＴ１からＳＴ１１までで、画像サイズが、算出した画像ブロックの整数倍になるかをチェックし、チェックの結果、整数倍になった場合のステップＳＴ５の処理は、実施の形態２と同じである。
【０１１２】
ステップＳＴ１１のチェック結果、整数倍にならない時は、ステップＳＴ１３において、メモリ割付手段１４の指示により、アクセス方向指定手段１６は、画像へのアクセス方向と画像ブロックの帯を算出し、算出した画像ブロックの帯での画像へのアクセス方法を、画像処理プログラム１に指定する。
【０１１３】
画像へのアクセス方向と画像ブロックの帯の算出後、図１１のステップＳＴ５において、メモリ割付手段１４は、算出した画像ブロックの帯を基準に、画像ブロックの帯が重ならず、かつ負荷が均等になるように、共有メモリ１２５の領域の各プロセッサ１２１〜１２４への割り付けを、画像処理プログラム１に指示する。
【０１１４】
なお、この例の画像処理プログラム１では、外部から指定されたアクセス順序で、各プロセッサ１２１〜１２４に指示し、コーナーターン処理できるようにプログラムされている。
【０１１５】
次に上記ステップＳＴ１３で、アクセス方向指定手段１６が画像へのアクセス方向と画像ブロックの帯を算出する方法について説明する。
画像へのアクセス方向は、アジマス方向の画像サイズが画像ブロックの整数倍にならない時に、図１２に示すようにアジマス方向になり、逆に、レンジ方向の画像サイズが画像ブロックの整数倍にならない時に、図１３に示すようにレンジ方向になる。
【０１１６】
画像ブロックの帯は、画像ブロック幅で、各方向の画像の行と列になる。図１２の例では、処理前画像で画像ブロック幅の列になり、処理結果画像で画像ブロック幅の行になる。
【０１１７】
アクセス方向指定手段１６は、書き込みが重ならず、かつ、なるべく読み込みの重複を少なくするようにアクセス方法を指定する。この方法の一例を図１２及び図１３に示す。ただし、アクセス方法は、はみ出す画素数により若干異なるために、図１２及び図１３では代表的な一例を示している。また、ここでは、レンジ方向からアジマス方向へのコーナーターン処理の例で説明するが、アジマス方向からレンジ方向へのコーナーターン処理は、アジマスとレンジを入れ換えたものである。
【０１１８】
図１２は、処理結果画像の行方向（アジマス方向）に、画像ブロックの整数倍から１画素はみ出す例である。図１２（ａ）は、画像イメージ上での各画素の読み込みと書き込みの位置関係を、各画素に対応する番号とアルファベットで示している。図１２（ｂ）は画像イメージ上でのアクセス順序を示している。
【０１１９】
画像の両端では、書き込み側で１画素ずつずれている影響のために、読み込みと書き込みを１回ずつで終えることができない。ここでは、なるべく読み込みの重複を少なくするようにする。図１２では、最初に、＜１＞，＜２＞，＜３＞，＜４＞と、＜Ｎ−２＞，＜Ｎ−１＞，＜Ｎ＞のキャッシュデータを読み込む。これを、書き込み側の［１］（画素Ｋ，Ｇ，Ｃ，４），［２］（画素Ｆ，Ｂ，３，７），［３］（画素Ａ，２，６，１０），［４］（１，５，９，１３）の順で書き込む。この時、＜１＞（画素１，２，３，４）に含まれるデータは、全てコーナーターン処理を完了している。
【０１２０】
次のコーナーターン処理では、＜２＞，＜３＞，＜４＞と、＜５＞のキャッシュデータ（画素８，１２，１６，２０）を、書き込み側の［５］のキャッシュに書き込む。ここでは、＜２＞，＜３＞，＜４＞のデータは読み込み済のため、＜５＞のデータだけが新たに読み込まれる。そして、＜２＞（画素５，６，７，８）のデータについてコーナーターン処理を完了する。
【０１２１】
以下順次、次のコーナーターン処理では、＜３＞，＜４＞，＜５＞と、＜６＞のキャッシュデータ（画素１１，１５，１９，２３）を、書き込み側の［６］のキャッシュに書き込み、さらに、次のコーナーターン処理では、＜４＞，＜５＞，＜６＞と、＜７＞のキャッシュデータ（画素１４，１８，２２，２６）を、書き込み側の［７］のキャッシュに書き込むことで、コーナーターン処理を行う。ここでは、＜６＞，＜７＞のデータだけが順次読み込まれ、＜３＞（画素９，１０，１１，１２），＜４＞（画素１３，１４，１５，１６）に含まれるデータのコーナーターン処理が完了する。
【０１２２】
このように、＜１＞〜＜Ｎ−３＞までのデータについては、キャッシュのデータを最小回数（１回ずつ）の読み込みと書き込みを行うことで、コーナーターン処理が実行できる。
【０１２３】
一方、コーナーターン処理の最終段階では、＜Ｎ−５＞，＜Ｎ−４＞，＜Ｎ−３＞，＜Ｎ−２＞のデータを［Ｎ−２］のキャッシュに、＜Ｎ−４＞，＜Ｎ−３＞，＜Ｎ−２＞，＜Ｎ−１＞のデータを［Ｎ−１］のキャッシュに、＜Ｎ−３＞，＜Ｎ−２＞，＜Ｎ−１＞，＜Ｎ＞のデータを［Ｎ］のキャッシュにコーナーターン処理を行う。ここでは、最初に読み込まれた＜Ｎ−２＞，＜Ｎ−１＞，＜Ｎ＞のデータが再度読み込まれる。
【０１２４】
最終的に、図１２の方法では、＜Ｎ−２＞，＜Ｎ−１＞，＜Ｎ＞の＊印のデータを最大２回読み込む（キャッシュのライン数が十分にあれば、１回の読み込みで済む）。＜Ｎ−２＞〜＜Ｎ＞まで読み込んだデータについては、１回目には、図１２の点線部分のデータを書き込まずに、最終段階で再度読み込んだ時に書き込む。このため、各キャッシュに、重複なく１回の書き込みでコーナーターン処理を実行できる。
【０１２５】
図１３は、処理結果画像の列方向（レンジ方向）に、画像ブロックの整数倍から１画素はみ出す例である。図１３（ａ）は画像イメージ上での各画素の読み込みと書き込みの位置関係を、図１３（ｂ）は画像イメージ上でのアクセス順序を示している。
【０１２６】
図１３では、読み込み側で１画素ずつずれている影響のために、読み込みと書き込みを１回ずつで終えることができない。ここでも、なるべく読み込みの重複を少なくするようにする。図１３では、最初に、＜１＞（画素１，２，３，４）と＜Ｎ−２＞（画素Ａ，５，６，７），＜Ｎ−１＞（画素Ｆ，Ｂ，９，１０），＜Ｎ＞（画素Ｋ，Ｇ，Ｃ，１３）のキャッシュデータを読み込む。これを、書き込み側の［１］（画素１，５，９，１３）に書き込む。
【０１２７】
次のコーナーターン処理では、新たに＜２＞（画素１４，１５，１６，ａ１３）のキャッシュデータを読み込み、書き込み側の［２］（画素２，６，１０，１４）のキャッシュに書き込む。ここでは、読み込み済の＜Ｎ−１＞，＜Ｎ＞，＜１＞のデータを利用する。
【０１２８】
以下順次、次のコーナーターン処理では、新たに＜３＞（画素１１，１２，ａ９，ａ１０）のキャッシュデータを読み込んで、書き込み側の［３］（画素３，７，１１，１５）のキャッシュに書き込み、さらに、次のコーナーターン処理では、新たに＜４＞（画素８，ａ５，ａ６，ａ７）のキャッシュデータを読み込んで、書き込み側の［４］（画素４，８，１２，１６）のキャッシュに書き込むことで、コーナーターン処理を行う。
【０１２９】
このように、＜１＞〜＜Ｎ−３＞までのデータについては、キャッシュのデータを最小回数（１回ずつ）の読み込みと書き込みを行うことで、コーナーターン処理を実行できる。
【０１３０】
一方、コーナーターン処理の最終段階では、＜Ｎ−２＞のデータを再度読み込んで［Ｎ−２］のキャッシュに、＜Ｎ−１＞のデータを再度読み込んで［Ｎ−１］のキャッシュに、＜Ｎ＞のデータを再度読み込んで［Ｎ］のキャッシュに、コーナーターン処理を行う。
【０１３１】
最終的に、図１３の方法では、＜Ｎ−２＞，＜Ｎ−１＞，＜Ｎ＞の＊印のデータを最大２回読み込む（キャッシュのライン数が十分にあれば、１回の読み込みで済む）。＜Ｎ−２＞〜＜Ｎ＞まで読み込んだデータについては、１回目には、図１２の点線部分のデータを書き込まずに、最終段階で再度読み込んだ時に書き込む。このため、各キャッシュに、重複なく１回の書き込みでコーナーターン処理を実行できる。
【０１３２】
この実施の形態では、特定のずれ幅の例で説明を行ったが、任意のずれ幅でも良い。また、この実施の形態では、画像処理プログラム１を介して、各プロセッサ１２１〜１２４にアクセス方法を指示していたが、プラットホーム２の機能等を使って、並列画像処理装置３が直接指定する方法で実装しても良い。
【０１３３】
以上のように、この実施の形態３によれば、コーナーターン処理を行う時に、処理対象の画像サイズが画像ブロックの整数倍にならない時でも、画像へのアクセス方向と画像ブロックの帯を算出し、画像ブロックの帯で指定されたアクセス方向へ、読み込みの重複が少なくかつ書き込みの重複がないアクセス方法でコーナーターン処理を行うように、各プロセッサに指定することにより、実施の形態２のように画像サイズを変更せずに、キャッシュのリードミスとライトミスを抑えて、オーバーヘッド時間を低減できるという効果が得られる。
【０１３４】
実施の形態４．
図１４はこの発明の実施の形態４による並列画像処理装置の構成を示すブロック図である。図において、１７は、画像サイズが画像ブロックの整数倍にならない時に、画像ブロック幅の行又は列を画像ブロックの帯として算出し、算出した画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段１２に設定されているプロセッサの個数の整数倍にならない時に、画像ブロックの帯を分割して、複数のプロセッサ１２１〜１２４で処理するよう指定する多重書き込み対応アクセス方向指定手段で、その他は、実施の形態１の図１に示す構成と同等である。この実施の形態では、画像ブロックの帯を基準に各プロセッサ１２１〜１２４に処理を割り振った時に、均等に割り振ることができず、画像ブロックの帯を分割して実行することが、実施の形態３と異なっている。
【０１３５】
図１５はこの実施の形態４による並列画像処理装置の処理を示すフローチャートで、図１６はアジマス方向に画像サイズが画像ブロックの整数倍にならない時の処理内容を示す図であり、図１７はレンジ方向に画像サイズが画像ブロックの整数倍にならない時の処理内容を示す図である。
【０１３６】
次に動作について説明する。
図１５のステップＳＴ１からＳＴ１１までの画像サイズが画像ブロックの整数倍になるかをチェックするまでの処理は、実施の形態３と同様である。画像サイズが画像ブロックの整数倍にならない時に、ステップＳＴ１３において、多重書き込み対応アクセス方向指定手段１７は、メモリ割付手段１４の指示により、画像へのアクセス方向と画像ブロックの帯を算出して、画像処理プログラム１に指定する。
【０１３７】
ステップＳＴ１４において、多重書き込み対応アクセス方向指定手段１７は、画像ブロックの帯の個数が設定されたプロセッサの個数の整数倍になるかをチェックする。チェックした結果、整数倍になる場合は、メモリ割付手段１４が実施の形態３と同様にステップＳＴ５の処理を行う。
【０１３８】
画像ブロックの帯の個数が設定されたプロセッサの個数の整数倍にならない時には、ステップＳＴ１５において、多重書き込み対応アクセス方向指定手段１７は、まず画像ブロックの帯の重なりを許して、各プロセッサ１２１〜１２４の負荷が均等になるように、画像ブロックの帯を各プロセッサ１２１〜１２４に処理を割り当てる。
【０１３９】
次に、画像ブロックの帯が重ならない部分については、多重書き込み対応アクセス方向指定手段１７は、実施の形態３と同様のアクセス方向を指定する。画像ブロックの帯が重なった部分については、多重書き込み対応アクセス方向指定手段１７は、次に示すアクセス方法を指定する。
【０１４０】
多重書き込み対応アクセス方向指定手段１７では、画像サイズがアジマス方向に画像ブロックの整数倍にならない時は、図１６に示すようにアジマスの方向で読み込みと書き込みの範囲を分割し、画像サイズがレンジ方向に画像ブロックの整数倍にならない時は、図１７に示すようにレンジの方向で、読み込みと書き込みの範囲を分割する。分割した範囲について、データの書き込みが重複せず、かつ、読み込み範囲の重複が小さくなるアクセス方法を指示する。この例を図１６と図１７に示す。
【０１４１】
図１６において、プロセッサ１２１，１２２は、基本的に図示された各領域について処理を行うが、処理前画像の点線部分は、画像ブロックの帯の個数が設定されたプロセッサの個数の整数倍にならないために、プロセッサ１２１，１２２のキャッシュがデータを多重に読み込む部分である。また、処理結果画像におけるプロセッサ１２２の範囲の斜線部分は、プロセッサ１２２が書き込む領域であるが、プロセッサ１２１が書き込みの処理を行うことにより、キャッシュのライトミスを抑えている。
【０１４２】
図１７においても、プロセッサ１２１，１２２は、基本的に図示された各領域について処理を行うが、処理前画像の点線部分は、画像ブロックの帯の個数が、設定されたプロセッサの個数の整数倍にならないために、プロセッサ１２１，１２２のキャッシュがデータを多重に読み込む部分である。また、処理結果画像の点線部分については、各プロセッサ１２１，１２２が、それぞれ書き込みの処理を行うことにより、キャッシュのライトミスを抑えている。
【０１４３】
ステップＳＴ１５の処理を終了後に、メモリ割付手段１４が実施の形態３と同様にステップＳＴ５の処理を行う。
【０１４４】
この実施の形態では、特定のずれ幅の例で説明を行ったが、任意のずれ幅でも良い。
【０１４５】
以上のように、この実施の形態４によれば、コーナーターン処理を行う時に、キャッシュのリードミスを最小限に抑えると共にライトミスを抑えて、オーバーヘッド時間を低減できるという効果が得られる。
【０１４６】
また、画像ブロックの帯での処理を分割して実行するため、画像ブロックの帯の個数が、設定されたプロセッサの個数の整数倍にならない時でも、プロセッサに処理負荷を均等に分割することにより、効率の良いコーナーターン処理を実行できるという効果が得られる。
【０１４７】
実施の形態５．
図１８はこの発明の実施の形態５による並列画像処理装置の構成を示すブロック図である。図において、１５は画像サイズが画像ブロックの整数倍になるように画像領域を拡張してメモリ上に確保するメモリ確保手段、１６は、画像サイズが画像ブロックの整数倍にならない時に、画像ブロック幅の行又は列を画像ブロックの帯として算出し、算出した画像ブロックの帯で画像のアクセス方向を指定するアクセス方向指定手段、１７は、画像サイズが画像ブロックの整数倍にならない時に、画像ブロック幅の行又は列を画像ブロックの帯として算出し、算出した画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段１２に設定されているプロセッサの個数の整数倍にならない時に、画像ブロックの帯を分割して、複数のプロセッサ１２１〜１２４で処理するよう指定する多重書き込み対応アクセス方向指定手段である。
【０１４８】
また、図１８において、１８は、画像サイズが画像ブロックの整数倍にならない時の修正方法の判定条件を設定するはみ出し修正方法設定手段であり、その他は実施の形態１の図１に示す構成と同等である。この実施の形態は、画像サイズが画像ブロックの整数倍にならない時に、その修正方法を選択するものである。図１９はこの実施の形態５による並列画像処理装置の処理を示すフローチャートである。
【０１４９】
次に動作について説明する。
はみ出し修正方法設定手段１８は、画像サイズが画像ブロックの整数倍にならない時に、修正方法を選択するための基準となる判定条件を設定している。このはみ出し修正方法設定手段１８への情報の設定は、ユーザ入力等で行う。メモリ割付手段１４は、はみ出し修正方法設定手段１８が保有している条件式の基準に基づき、画像情報設定手段１１の画像情報や、キャッシュ情報設定手段１３のキャッシュ情報等を使って、修正方法を選択する。
【０１５０】
また、はみ出し修正方法設定手段１８に、メモリの確保にかかる時間や、アクセス方向を指定した処理にかかる時間等を、手動や過去の実行情報の履歴から設定して、メモリ割付手段１４が、各修正法を選択した時のコーナーターン処理を含めた画像処理時間等を計算して、最短となる方法を選択することもできる。
【０１５１】
この他、アクセス方向指定手段１６が選択されたケースで、使用プロセッサ数設定手段１２からのプロセッサの個数により、画像ブロックの帯で処理が均等に分割できない場合には、メモリ割付手段１４が、多重書き込み対応アクセス方向指定手段１７に切り替えて処理を行うといった設定も行うことができる。
【０１５２】
図１９のステップＳＴ１からＳＴ４までの処理は、実施の形態１の処理と同じである。ステップＳＴ１１において、メモリ割付手段１４は、画像サイズが、算出した画像ブロックの整数倍になるかをチェックする。チェックの結果、整数倍になる時は、実施の形態１と同様に、ステップＳＴ５の処理を行う。整数倍にならない時には、ステップＳＴ１６において、メモリ割付手段１４は、はみ出し修正方法設定手段１８に問い合わせて、修正方法を選択する。
【０１５３】
メモリ割付手段１４がメモリ確保手段１５を選択した場合には、実施の形態２と同様に、ステップＳＴ１２及びステップＳＴ５の処理を行い、アクセス方向指定手段１６を選択した場合には、実施の形態３と同様に、ステップＳＴ１３及びステップＳＴ５の処理を行い、多重書き込み対応アクセス方向指定手段１７を選択した場合には、実施の形態４と同様に、ステップＳＴ１３，ＳＴ１４，ＳＴ１５，ＳＴ５の処理を行う。
【０１５４】
以上のように、この実施の形態５によれば、コーナーターン処理を行う時に、処理対象の画像サイズが画像ブロックサイズの整数倍にならない時に、キャッシュのリードミスを最小限に抑えると共にライトミスを抑えて、オーバーヘッド時間を低減できると共に、複数の対処方法から最適の方法を選択することで、効率の良いコーナーターン処理を実行できるという効果が得られる。
【０１５５】
実施の形態６．
図２０はこの発明の実施の形態６による並列画像処理装置の構成を示すブロック図である。図において、１９は要求仕様として与えられる時間制約と各プロセッサ１２１〜１２４の処理時間等の時間制約条件を設定している処理時間制約設定手段、２０は実際に使用するプロセッサ１２１〜１２４の個数を画像処理プログラム１に指定する実行プロセッサ数指定手段であり、その他は実施の形態１の図１に示す構成と同等である。この実施の形態では、画像ブロックをプロセッサ１２１〜１２４に分割する前に、使用するプロセッサ数を調整することが実施の形態１と異なる。
図２１はこの実施の形態６による並列画像処理装置の処理を示すフローチャートである。
【０１５６】
次に動作について説明する。
処理時間制約設定手段１９は、要求仕様として与えられるコーナーターン処理に対する時間制約条件の情報を設定している。ここで設定する時間制約条件には、処理完了までの目標時間、最大許容時間等の時間条件の他、処理時間（速度）とシステム資源（プロセッサ）の利用に関するポリシ（処理時間優先やシステム資源の節約優先）等の処理時間に影響を与える各種情報がある。また、コーナーターン処理にかかった実行時間情報を、画像サイズや使用したプロセッサ数や画像の分割処理方法等のパラメータと一緒に記録しておくこともできる。
【０１５７】
この処理時間制約設定手段１９への情報設定は、ユーザ入力等により手動で行う他に、処理実行時に実行時間情報を、画像サイズや使用したプロセッサ数等のパラメータと一緒に蓄積しておくこともできる。
【０１５８】
実行プロセッサ数指定手段２０は、指定されたプロセッサ数で処理を実行するように指定する手段である。この例では、画像処理プログラム１にプロセッサ数を指定する。なお、この例の画像処理プログラム１では、実行プロセッサ数指定手段２０が指定したプロセッサ数でコーナーターン処理を行う。
【０１５９】
図２１のステップＳＴ１からＳＴ４までの画像ブロックを計算するところまでの処理は、実施の形態１と同じである。ただし、この実施の形態では、ステップＳＴ３で、使用プロセッサ数設定手段１２から入手したプロセッサの個数を、プロセッサ数Ａとして記憶しておく。
【０１６０】
ステップＳＴ４で画像ブロックを計算後、ステップＳＴ２１において、メモリ割付手段１４は、処理時間制約設定手段１９から時間制約条件を入手し、ステップＳＴ２２において、メモリ割付手段１４は、入手した時間制約を満たす最適のプロセッサ数Ｂを計算する。この計算では、過去のコーナーターン処理にかかった実行時間情報と、その時の画像サイズ等の処理パラメータを使って、与えられた条件下でのプロセッサ数と処理時間の関係を予測して算出することも含まれている。
【０１６１】
例えば、システム資源の節約優先の場合には、最大許容時間を満たすのに最低限必要な個数のプロセッサ数を算出する。目標時間〜最大許容時間の範囲で処理時間優先の場合には、目標時間内で終了するのに最低限必要な個数のプロセッサ数を算出する。処理時間最優先の場合には、プロセッサ数を無限大∞とする。
【０１６２】
ステップＳＴ２２でプロセッサ数Ｂを算出した後に、ステップＳＴ２３において、メモリ割付手段１４はプロセッサ数Ａの値とプロセッサ数Ｂの値を比較し、同じであれば、実施の形態１と同様にステップＳＴ５の処理を行い、ステップＳＴ２３でＡの値とＢの値が異なり、ステップＳＴ２４において、Ｂの値がＡの値以上の場合には、メモリ割付手段１４はＡの値を最終的なプロセッサ数として、実施の形態１と同様にステップＳＴ５の処理を実施する。
【０１６３】
ステップＳＴ２４において、Ｂの値がＡの値より小さい場合には、ステップＳＴ２５において、メモリ割付手段１４はＢの値を最終的なプロセッサ数とする。この場合は、プロセッサ数Ｂの値を使用し、ステップＳＴ５において、実施の形態１と同じ手順でプロセッサへの処理領域の割り付けを行うと共に、メモリ割付手段１４は実行プロセッサ数指定手段２０に最終的なプロセッサ数を伝達し、実行プロセッサ数指定手段２０は、伝達されたプロセッサ数で処理を実行するように画像処理プログラム１へ指定する。
【０１６４】
この実施の形態では、使用プロセッサ数設定手段１２が最大利用可能なプロセッサ数を指定する例で説明したが、使用プロセッサ数設定手段１２では、プロセッサ数の設定を行わず、処理時間制約設定手段１９で計算機資源への利用制約の１つとして、最大利用可能プロセッサ数を設定し、プロセッサ数Ａを無限大∞として実行しても良い。
【０１６５】
この実施の形態では、実行プロセッサ数指定手段２０が、画像処理プログラム１にプロセッサ数を指定しているが、実行プロセッサ数指定手段２０が、画像処理プログラム１で使用するプロセッサの個数を、プラットホーム２の機能を使って直接設定するように実装しても良い。
【０１６６】
この実施の形態では、コーナーターン処理について、使用プロセッサ数を実行プロセッサ数指定手段２０で指定しているが、コーナーターン処理以外の画像処理についても、実行プロセッサ数指定手段２０でプロセッサ数を変更できるように実装しても良い。
【０１６７】
この実施の形態では、処理時間制約設定手段１９での処理時間関連の情報は、コーナーターン処理関連の時間を使用しているが、コーナーターン処理を含む画像処理全体についての制約時間情報や実行時間情報を使用して、プロセッサ数Ｂを算出しても良い。
【０１６８】
この実施の形態では、実施の形態１の並列画像処理装置に処理時間制約設定手段１９と実行プロセッサ数指定手段２０を加えているが、実施の形態２〜実施の形態５の並列画像処理装置に対しても、処理時間制約設定手段１９と実行プロセッサ数指定手段２０を加えても良い。また、実施の形態４と実施の形態５に適用した場合には、画像ブロックの帯を複数プロセッサに分割しないという条件を、処理時間制約設定手段１９に加えることで、画像ブロックの帯での重なりを抑制しても良い。
【０１６９】
以上のように、この実施の形態６によれば、キャッシュによるオーバーヘッド時間を低減できると共に、要求仕様として与えられる時間制約条件の情報に基づいて最適のプロセッサ数を算出し、算出したプロセッサ数で効率の良いコーナーターン処理を実行できるという効果が得られる。
【０１７０】
また、最適のプロセッサ数の算出では、過去の実行時間情報等を利用することで、要求仕様として与えられた時間内で、より正確にコーナーターン処理を完了できると共に、利用する資源を節約しながらコーナーターン処理を実行できるという効果が得られる。
【０１７１】
実施の形態７．
図２２はこの発明の実施の形態７による並列画像処理装置の構成を示すブロック図である。図において、２１は、画像ブロックの処理に必要な各プロセッサ１２１〜１２４のキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像へのアクセスパターンを算出し、画像処理プログラム１に指定する画素アクセス順序指定手段であり、その他は実施の形態１の図１に示す構成と同等である。この例では、画像ブロックをプロセッサ１２１〜１２４に分割して実行する時に、１つの画像ブロックをコーナーターン処理するのに、各プロセッサ１２１〜１２４のキャッシュライン数が不足することが、実施の形態１と異なる。
【０１７２】
図２３はこの実施の形態７による並列画像処理装置の処理を示すフローチャートであり、図２４はキャッシュのライン数が不足した時のアクセスパターンを示す図である。
【０１７３】
次に動作について説明する。
図２３のステップＳＴ１からＳＴ４における画像ブロックを計算するところまでの処理は、実施の形態１と同じである。画像ブロックを計算後、ステップＳＴ３１において、メモリ割付手段１４は、まず、画像ブロックの処理に必要なキャッシュのライン数を算出する。このライン数は、コーナーターン処理の処理前画像側と処理結果画像側で、画像ブロックのデータを全てキャッシュに収めるのに必要なライン数となる。
【０１７４】
図２４の例では、１キャッシュライン当たり４画素であり、画像ブロックは４画素×４画素の領域になる。この場合、処理前画像側と処理結果画像側で、画像ブロックのデータを全てキャッシュに収めるのに、それぞれ４ラインづつ必要となるため、ここでの必要なキャッシュのライン数は８ラインとなる。
【０１７５】
必要なキャッシュのライン数を算出した後、ステップＳＴ３１において、メモリ割付手段１４は、キャッシュ情報設定手段１３が設定している各プロセッサ１２１〜１２４が搭載しているキャッシュのライン数と比較する。ここで、キャッシュのライン数が不足しない時（プロセッサ１２１〜１２４が搭載しているキャッシュのライン数≧必要なキャッシュのライン数）には、実施の形態１と同様に、ステップＳＴ５の処理を実行する。
【０１７６】
キャッシュのライン数が不足する時（プロセッサ１２１〜１２４が搭載しているキャッシュのライン数＜必要なキャッシュのライン数）には、ステップＳＴ３２において、メモリ割付手段１４の指示により、画素アクセス順序指定手段２１は、画素へのアクセス順序を計算して、画像処理プログラム１に指定する。その後、ステップＳＴ５において、各プロセッサ１２１〜１２４への画像ブロック割り付けを実施の形態１と同様に実行する。
【０１７７】
ステップＳＴ３２の処理について説明する。
アクセス順序の制御を指示された画素アクセス順序指定手段２１では、キャッシュ情報設定手段１３の情報を利用して、キャッシュデータの退避回数が最小になるアクセスパターンを算出する。ここでは、画素へのアクセス順序を制御することで、キャッシュデータの退避回数が最小になるパターンを算出する。
【０１７８】
図２４に、必要なキャッシュのライン数は「８ライン」の場合に、キャッシュのライン数が８ラインよりも少ない場合のアクセスパターンの例を示す。なお、ここでは、キャッシュデータの退避順序が、最終アクセス順序であることを仮定している。この仮定のもと、図２４のアクセスパターンでは、アクセス順序を図示のように行い、キャッシュデータの退避回数を最小にしている。
【０１７９】
アクセスパターンの算出後、ステップＳＴ３２において、画素アクセス順序指定手段２１が、メモリ割付手段１４と同様に、画像処理プログラム１に画素へのアクセスパターンを指定することで、各プロセッサ１２１〜１２４での実際のアクセス順序を制御する。ここでは、画像処理プログラム１が外部から指定された順序で各プロセッサ１２１〜１２４の各画素へのアクセス順序を変更できることを仮定している。
【０１８０】
この実施の形態では、画像ブロックのサイズが４画素×４画素であるが、任意のサイズの画像ブロックでも良い。また、キャッシュラインの不足数についても任意の数で良い。さらに、この実施の形態では、キャッシュデータの退避順序が、最終アクセス順序である例で説明したが、他のキャッシュ退避方法で実現されたシステムでは、キャッシュデータの退避回数を最小となるアクセスパターンを指定するように実装しても良い。
【０１８１】
この実施の形態では、画素アクセス順序指定手段２１が、画像処理プログラム１にアクセスパターンを指定することにより、アクセスパターンの制御を行っているが、画素アクセス順序指定手段２１がプラットホーム２の機能を使って直接設定するように実装しても良い。
【０１８２】
この実施の形態では、実施の形態１の並列画像処理装置に画素アクセス順序指定手段２１を追加しているが、実施の形態２〜実施の形態６の並列画像処理装置に対しても、画素アクセス順序指定手段２１を追加しても良い。
【０１８３】
以上のように、この実施の形態７によれば、画像ブロックをプロセッサ１２１〜１２４に分割して実行する時に、１つの画像ブロックをコーナーターン処理するのに、各プロセッサ１２１〜１２４のキャッシュのライン数が不足しても、各画素へのアクセスパターンを制御し、キャッシュデータの退避回数を抑えることにより、オーバーヘッド時間を低減できるという効果が得られる。
【０１８４】
実施の形態８．
図２５はこの発明の実施の形態８による並列画像処理装置の構成を示すブロック図である。図において、２２は、各プロセッサ１２１〜１２４のキャッシュが多階層の構成をとる時に、画像情報設定手段に１１に設定されている画像情報、使用プロセッサ数設定手段１２に設定されているプロセッサ１２１〜１２４の個数情報、キャッシュ情報設定手段１３に設定されているキャッシュ情報を入手して、メモリ割付手段１４が算出した１次キャッシュの画像ブロックをもとに、キャッシュの階層ごとに低位キャッシュの画像ブロックを包含するように画像ブロックを算出し、算出した最上位キャッシュの画像ブロック単位でコーナーターン処理を実行し、かつ、最上位キャッシュの画像ブロックを実行する個数がプロセッサ１２１〜１２４間で均等になるように、各プロセッサ１２１〜１２４へ共有メモリ１２５の対象領域を割り付けるよう画像処理プログラム１に指示する多階層キャッシュ対応メモリ割付手段であり、その他は実施の形態１の図１に示す構成と同等である。
図２６はこの実施の形態８による並列画像処理装置の処理を示すフローチャートである。
【０１８５】
図２７はこの実施の形態でのメモリ割り付けの概念を示す図で、図２８は画像ブロックを複数のプロセッサ１２１〜１２４で処理する一例を示す図である。この例では、各プロセッサ１２１〜１２４は、１次キャッシュと２次キャッシュの２階層のキャッシュ構成を取るものと仮定する。１次キャッシュは実施の形態１と同じサイズ（３２Ｂｙｔｅ×５１２ライン）でライトスルー方式、２次キャッシュは１２８Ｂｙｔｅ×１６，３８４ラインのサイズでライトバック方式、２次キャッシュへのライトミスが、他のキャッシュミスのオーバーヘッド時間と比較して特に大きいと仮定する。
【０１８６】
次に動作について説明する。
図２６のステップＳＴ４１において、多階層キャッシュ対応メモリ割付手段２２は、メモリ割付手段１４に、階層の低い１次キャッシュの画像ブロックの算出を指示し、ステップＳＴ４２において、メモリ割付手段１４は、画像情報、使用プロセッサ数、キャッシュ情報を入手して、実施の形態１と同様にして、１次キャッシュの画像ブロックを算出する。
【０１８７】
多階層キャッシュ対応メモリ割付手段２２は、ステップＳＴ４３において、１つ上位の２次キャッシュを選択し、ステップＳＴ４４において、対象の２次キャッシュのキャッシュ情報を入手し、ステップＳＴ４５において、１次キャッシュの画像ブロック（以下、１次画像ブロックとする）を包含するように、２次キャッシュの画像ブロック（以下、２次画像ブロック）を算出する。図２７に示す例では、１次画像ブロック４個で２次キャッシュの幅と一致するため、１次画像ブロック４個×４個のサイズの画像ブロックを２次画像ブロックとする。
【０１８８】
ステップＳＴ４６において、多階層キャッシュ対応メモリ割付手段２２は、さらに上位のキャッシュが存在するかをチェックし、存在する場合には、ステップＳＴ４７において、１つ上位階層のキャッシュを選択し、ステップＳＴ４４に戻り、２次画像ブロックを求めたのと同様の方法で、画像ブロックを求めていく。例えば、３次キャッシュが存在する場合には、２次画像ブロックを基準に、それを包含する３次キャッシュの画像ブロックを算出する。
【０１８９】
ステップＳＴ４６で、上位のキャッシュが存在しない場合には、最上位のキャッシュの画像ブロックを、全体の画像ブロックとして決定し、ステップＳＴ５の処理を行う。この例では、２次キャッシュまでしか存在しないので、２次画像ブロックを全体の画像ブロックとする。
【０１９０】
ステップＳＴ５において、多階層キャッシュ対応メモリ割付手段２２は、決定した全体の画像ブロックを基準に、実施の形態１のメモリ割付手段１４と同様の方法で、各プロセッサ１２１〜１２４へ処理する対象領域を割り付ける。この例では、２次画像ブロックを１つの単位として領域を割り付け、各プロセッサ１２１〜１２４で処理を実行する。
【０１９１】
また、全体の画像ブロック単位では、画像ブロックを均等に割り付けられない時には、実施の形態１と同様に、画像ブロックの処理を複数のプロセッサ１２１〜１２４で実行する。図２８は多階層キャッシュの画像ブロックを複数のプロセッサ１２１〜１２４で処理する一例を示す図である。
【０１９２】
多階層キャッシュの画像ブロックで、このような複数のプロセッサ１２１〜１２４での実行を行った場合、最上位のキャッシュレベル（この例では２次キャッシュ）では、実施の形態１と同様に、全てのプロセッサ１２１〜１２４が画像ブロック全体のデータを読み込む（この例では、２次画像ブロックのデータは全てのプロセッサ１２１〜１２４が読み込む）。
【０１９３】
一方で、低位のキャッシュについては、必ずしも全てのデータを読み込む必要はない。図２８の例では、プロセッサ１２１は１次画像ブロックの＜１＞，＜５＞，＜９＞，＜１３＞だけを、プロセッサ１２２は１次画像ブロックの＜２＞，＜６＞，＜１０＞，＜１４＞だけを読み込めば良い。
書き込みについては、実施の形態１と同様に、全てのキャッシュで重ならないように実行する。
【０１９４】
この実施の形態では、１次キャッシュと２次キャッシュによる構成で説明したが、並列実行する各プロセッサ１２１〜１２４に、３次キャッシュ以上の階層的な構造を取る場合でも適用できる。
【０１９５】
この実施の形態では、１次キャッシュと２次キャッシュについて、上記の所定のサイズと一貫性保持のための方法を割り付けて説明したが、任意のサイズ及び一貫性保持のための方法でも良い。また、処理画像の画素サイズや画像サイズの大きさについても任意で良い。
【０１９６】
この実施の形態では、実施の形態１の並列画像処理装置に多階層キャッシュ対応メモリ割付手段２２を追加したが、実施の形態６の並列画像処理装置に対しても、多階層キャッシュ対応メモリ割付手段２２を追加しても良い。
【０１９７】
以上のように、この実施の形態８によれば、多階層のキャッシュ構成を取る場合に、最上位キャッシュの画像ブロックを算出し、各プロセッサ１２１〜１２４が最上位キャッシュの画像ブロック単位でコーナーターン処理を実行し、かつ、最上位キャッシュの画像ブロックを実行する個数が均等になるように、各プロセッサ１２１〜１２４へ共有メモリ１２５の対象領域を割り付けることにより、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【０１９８】
また、多階層のキャッシュ構成を取る場合でも、１画像ブロックの処理を複数のプロセッサ１２１〜１２４で行うことにより、より公平な負荷分散が行えると共に、１画像ブロックの処理を高速化できるという効果が得られる。
【０１９９】
実施の形態９．
図２９はこの発明の実施の形態９による並列画像処理装置の構成を示すブロック図である。図において、２３は、画像サイズが最上位キャッシュの画像ブロックの整数倍にならない時に、画像サイズが最上位キャッシュの画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ１２５上に確保する多階層キャッシュ対応メモリ確保手段であり、その他は実施の形態８の図２５に示す構成と同等である。この実施の形態では、画像サイズが最上位キャッシュの画像ブロックサイズの整数倍にならない点が、実施の形態８と異なっている。
図３０はこの実施の形態９による並列画像処理装置の処理を示すフローチャートである。
【０２００】
次に動作について説明する。
図３０のステップＳＴ４１からＳＴ４７までの最上位キャッシュの画像ブロックを計算するところまでは、実施の形態８と同じである。
【０２０１】
ステップＳＴ５１において、多階層キャッシュ対応メモリ割付手段２２は、画像サイズが、算出した最上位キャッシュの画像ブロックの整数倍になるかをチェックする。チェックの結果、整数倍になる場合は、実施の形態８と同様にステップＳＴ５の処理を行う。
【０２０２】
整数倍にならない時には、ステップＳＴ５２において、多階層キャッシュ対応メモリ割付手段２２の指示により、多階層キャッシュ対応メモリ確保手段２３が、実施の形態２のメモリ確保手段１５と同様の方法で、画像サイズが最上位キャッシュの画像ブロックの整数倍になるように画像領域を拡張して、共有メモリ１２５上に確保する。そして、多階層キャッシュ対応メモリ割付手段２２は、実施の形態８と同様に、ステップＳＴ５の処理を行う。
【０２０３】
この実施の形態では、実施の形態１の並列画像処理装置に、多階層キャッシュ対応メモリ割付手段２２と多階層キャッシュ対応メモリ確保手段２３を追加しているが、実施の形態６の並列画像処理装置に、多階層キャッシュ対応メモリ割付手段２２と多階層キャッシュ対応メモリ確保手段２３を追加しても良い。
【０２０４】
以上のように、この実施の形態９によれば、多階層のキャッシュ構成を取り、処理対象の画像サイズが最上位キャッシュの画像ブロックサイズの整数倍にならない時に、コーナーターン処理において、画像サイズが最上位キャッシュの画像ブロックの整数倍になるように、処理対象の画像領域を拡張して共有メモリ１２５上に確保するので、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【０２０５】
実施の形態１０．
図３１はこの発明の実施の形態１０による並列画像処理装置の構成を示すブロック図である。図において、２４は、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない時に、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍になるように、低位キャッシュの画像ブロックの領域を拡張して共有メモリ１２５上に確保する多階層画像ブロック用メモリ確保手段であり、その他は実施の形態８の図２５に示す構成と同等である。この実施の形態では、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない点が、実施の形態８と異なっている。
図３２はこの実施の形態１０による並列画像処理装置の処理を示すフローチャートであり、図３３はこの実施の形態での領域拡張方法の概念を示す図である。
【０２０６】
次に動作について説明する。
図３２のステップＳＴ４１からＳＴ４４までの２次キャッシュ以上の各階層で対象キャッシュの情報を入手するところまでは、実施の形態８と同じである。
【０２０７】
ステップＳＴ５１において、多階層キャッシュ対応メモリ割付手段２２は、選択した各階層で、ステップＳＴ４４で入手した対象キャッシュの情報に基づき、選択された階層のキャッシュのラインサイズが、１つ下の低位のキャッシュの画像ブロックサイズの整数倍になるかをチェックする。チェックの結果、整数倍になる時は、実施の形態８と同様に、ステップＳＴ４５以降の処理を行う。
【０２０８】
整数倍にならない時には、ステップＳＴ５２において、多階層キャッシュ対応メモリ割付手段２２の指示に基づき、多階層画像ブロック用メモリ確保手段２４が、整数倍になるように、全ての低位キャッシュの画像ブロックの領域を拡張して、共有メモリ１２５上に確保する。この例を図３３に示す。ここで、領域拡張の指示方法は、実施の形態２や実施の形態９と同様の方法である。ステップＳＴ５２の領域拡張後の処理手順は、実施の形態８と同様に、ステップＳＴ４５以降の処理を行う。
【０２０９】
この領域拡張を行った場合に、画像中にアクセスされない領域ができるため、拡張後も画像処理プログラム１が画像データに正しくアクセスできるようにする必要がある。この方法としては、画像処理プログラム１を多階層画像ブロック用メモリ確保手段２４での領域拡張に対応したプログラムとし、多階層画像ブロック用メモリ確保手段２４から画像処理プログラム１へ領域の拡張を指示することで、画像処理プログラム１が自動的に対応する方法がある。
【０２１０】
また、画像処理プログラム１は、並列画像処理装置３が指定した領域を画像データとして参照しながら実行するプログラムとし、並列画像処理装置３内の多階層画像ブロック用メモリ確保手段２４が、領域の拡張情報と画像データの位置情報を管理し、画像処理プログラム１が正しいデータにアクセスできるように画像データの位置を計算して指定する方法もある。
【０２１１】
この実施の形態では、実施の形態８の並列画像処理装置に多階層画像ブロック用メモリ確保手段２４を追加しているが、実施の形態９の並列画像処理装置に対しても、多階層画像ブロック用メモリ確保手段２４を追加しても良い。また、実施の形態６の並列画像処理装置についても、多階層キャッシュ対応メモリ割付手段２２と多階層画像ブロック用メモリ確保手段２４を追加しても良い。
【０２１２】
以上のように、この実施の形態１０によれば、多階層のキャッシュ構成で、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない時に、コーナーターン処理において、上位キャッシュのラインサイズが低位キャッシュの画像ブロックの整数倍になるように、低位キャッシュの画像ブロックの領域を拡張して共有メモリ１２５上に確保することにより、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【０２１３】
実施の形態１１．
図３４はこの発明の実施の形態１１による並列画像処理装置の構成を示すブック図である。図において、２５は、画像サイズが算出した最上位キャッシュの画像ブロックの整数倍にならない時に、最上位キャッシュの画像ブロックの行又は列を最上位キャッシュの帯として算出し、算出した画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、使用プロセッサ数設定手段１２に設定されているプロセッサ１２１〜１２４の個数の整数倍にならない時に、画像ブロックの帯を分割して、複数のプロセッサ１２１〜１２４で処理するよう指定する多階層キャッシュ対応アクセス方向指定手段であり、その他は実施の形態８の図２５に示す構成と同等である。この実施の形態では、画像サイズが最上位キャッシュの画像ブロックの整数倍にならない点が、実施の形態８と異なっている。
【０２１４】
図３５はこの実施の形態１１による並列画像処理装置の処理を示すフローチャートであり、図３６はこの実施の形態１１でのアクセス方向指定方法の概念を示す図である。
【０２１５】
次に動作について説明する。
図３５のステップＳＴ４１からＳＴ４７までの最上位キャッシュの画像ブロックを計算するところまでは、実施の形態８と同じである。
【０２１６】
ステップＳＴ６１において、多階層キャッシュ対応メモリ割付手段２２は、画像サイズが、算出した最上位キャッシュの画像ブロックの整数倍になるかをチェックする。チェックの結果、整数倍になる時は、実施の形態８と同様にステップＳＴ５の処理を行う。整数倍にならない時には、ステップＳ６２において、多階層キャッシュ対応メモリ割付手段２２の指示により、多階層キャッシュ対応アクセス方向指定手段２５は画像ブロックの帯と画像へのアクセス方向を算出する。
【０２１７】
多階層キャッシュ対応アクセス方向指定手段２５が画像ブロックの帯と画像へのアクセス方向を算出する方法は、基本的に、実施の形態３と同じである。画像ブロックの帯は、最上位キャッシュの画像ブロック幅でアジマス又はレンジ方向になる。図３６の例では、画像ブロックの帯は、処理前画像で画像ブロック幅の列、処理後方向で画像ブロック幅の行になり、画像へのアクセス方向は、アジマス側にはみ出した時にはアジマス方向、レンジ側にはみ出した時にはレンジ方向になる。
【０２１８】
ステップＳＴ６３において、多階層キャッシュ対応メモリ割付手段２２は、画像ブロックの帯の個数が、設定されたプロセッサの個数の整数倍になるかをチェックする。チェックの結果、整数倍になる時は、実施の形態８と同様にステップＳＴ５の処理を行うが、この時、画像ブロックの帯を基準に、画像ブロックの帯が重ならず、かつ負荷が均等になるようにプロセッサ１２１〜１２４に処理を割り付ける。
【０２１９】
ステップＳＴ６３で、画像ブロックの帯の個数が、設定されたプロセッサの個数の整数倍にならない時には、ステップＳ６４において、多階層キャッシュ対応メモリ割付手段２２は、算出した画像ブロックの帯を低位キャッシュでの画像ブロック幅の整数倍に分割する。図３６にその例を示す。
【０２２０】
図３６において、低位キャッシュ（１次キャッシュ）の画像ブロックは、図における（ａ），（ｂ）と同じサイズである。２分割する場合には、（Ａ）と（Ｂ）に分割し、ステップＳＴ５において、２つのプロセッサで実行するよう割り付ける。また、４分割する場合には、さらに（Ａ）の幅の半分、すなわち（ａ），（ｂ）の単位に分割し、ステップＳＴ５において、４つのプロセッサで実行するよう割り付ける。
【０２２１】
この実施の形態では、アジマス方向にはみ出す例を示したが、レンジ方向にはみ出す場合でも適用できる。また、この実施の形態では、実施の形態８の並列画像処理装置に、多階層キャッシュ対応アクセス方向指定手段２５を追加しているが、実施の形態９と実施の形態１０の並列画像処理装置に対しても、多階層キャッシュ対応アクセス方向指定手段２５を追加しても良い。
【０２２２】
以上のように、この実施の形態１１によれば、多階層のキャッシュ構成を取る場合で、処理対象の画像サイズが最上位キャッシュの画像ブロックの整数倍にならない時でも、実施の形態１０のように画像ブロックの領域を拡張せずに、画像ブロックの帯と画像へのアクセス方向を算出し、画像ブロックの帯で指定されたアクセス方向へ、読み込みの重複が少なく、かつ書き込みの重複がないアクセス方法でコーナーターン処理を行うことにより、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【０２２３】
また、画像ブロックの帯を複数のプロセッサ１２１〜１２４で分割実行する場合でも、低位キャッシュでの画像ブロック幅の整数倍に分割することで、キャッシュのリードミスとライトミスを抑えて、効率の良いコーナーターン処理を実行できるという効果が得られる。
【０２２４】
実施の形態１２．
図３７はこの発明の実施の形態１２による並列画像処理装置の構成を示すブロック図である。図において、２６は、算出した画像ブロックの処理に必要な各プロセッサ１２１〜１２４のキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像又は低次のキャッシュへのアクセスパターンを指定する多階層キャッシュ対応アクセスパターン指定手段であり、その他は実施の形態８の図２５に示す構成と同等である。この実施の形態では、画像ブロックをプロセッサに分割して実行する時に、１つの画像ブロックをコーナーターン処理するのに、各プロセッサ１２１〜１２４のキャッシュのライン数が不足していることが、実施の形態８と異なっている。
【０２２５】
図３８はこの実施の形態１２による並列画像処理装置の処理を示すフローチャートであり、図３９はこの実施の形態１２での２次キャッシュのライン数が不足した時のアクセスパターンを示す図である。
【０２２６】
次に動作について説明する。
図３８のステップＳＴ４１からステップＳＴ４７までの最上位キャッシュの画像ブロックを計算するところまでは、実施の形態８と同じである。最上位キャッシュの画像ブロックを計算後、ステップＳＴ７１において、多階層キャッシュ対応メモリ割付手段２２は、まず、画像ブロックの処理に必要なキャッシュのライン数を各キャッシュの階層毎に算出する。このライン数は、各階層のキャッシュで、最上位キャッシュの画像ブロックを対象に、処理前画像側と処理結果画像側で、データを全てキャッシュに収めるのに必要なライン数となる。このライン数の算出方法は、実施の形態７と同じである。
【０２２７】
必要なキャッシュのライン数を算出した後、多階層キャッシュ対応メモリ割付手段２２は、キャッシュ情報設定手段１３が設定している各プロセッサ１２１〜１２４が搭載しているキャッシュのライン数と比較し、キャッシュのライン数が不足するか否かをチェックする。全ての階層でキャッシュのライン数が不足しない時（プロセッサ１２１〜１２４が搭載しているキャッシュのライン数≧必要なキャッシュのライン数）には、実施の形態８と同様に、ステップＳＴ５の処理を実行する。
【０２２８】
いずれかの階層でキャッシュのライン数が不足する時（プロセッサ１２１〜１２４が搭載しているキャッシュのライン数＜必要なキャッシュのライン数）は、ステップＳＴ７２において、多階層キャッシュ対応メモリ割付手段２２の指示により、多階層キャッシュ対応アクセスパターン指定手段２６は、キャッシュ情報設定手段１３の情報を利用して、キャッシュデータの退避回数が最小になるアクセスパターンを算出する。その場合のアクセス順序を図３９に示している。
【０２２９】
この時、最上位キャッシュからチェックし、ライン数が不足した時には、ライン数が不足したキャッシュの階層で、その階層の画像ブロック単位で処理を行うようにする。自身の階層の画像ブロック単位でもライン数が不足する時には、低位キャッシュの画像ブロック単位を選択し、アクセス順序を制御して実行する。ライン数の不足が解消されるまで、より低位キャッシュの画像ブロックを選択していく。
【０２３０】
図３９の例では、１次キャッシュの画像ブロックである＜１＞，＜２＞，＜３＞といった単位で処理を実行するようにする。この例の場合、任意のアクセスパターンで実行するには、１次キャッシュで１２８ライン必要となる。これは、１次キャッシュの１ラインは４画素で、２５６画素では６４ライン、読み込みと書き込みで２倍必要なためである。一方、１次キャッシュの画像ブロック単位で実行すれば８ラインで実行可能になる。
【０２３１】
この画像ブロック単位での処理でライン不足を解消する方法は、コーナーターン処理を任意のアクセスパターンで実行するケースと同じ効率で実行できる利点がある。
【０２３２】
最終的に、１次キャッシュの画像ブロック単位でも、キャッシュラインが不足する場合には、実施の形態７と同様に、画素単位でのアクセスパターンを制御する。この場合、低位キャッシュの画像ブロック単位ごとに実行する場合と比べて処理効率が低下するが、実施の形態７と同様の方法を取ることで、オーバーヘッドを抑えることができる。
【０２３３】
アクセスパターンの算出後、ステップＳＴ７２において、多階層キャッシュ対応アクセスパターン指定手段２６は、実施の形態７の画素アクセス順序指定手段２１と同様の方法で各プロセッサでの実際のアクセス順序を計算し、実施の形態８と同様に、ステップＳＴ５の処理を実行する。
【０２３４】
この実施の形態では、キャッシュの構成が１次と２次のキャッシュとなっているが、任意のキャッシュの構成でも良い。また、画素サイズや画素数といった画像情報に対しても、任意の値でも良い。
【０２３５】
この実施の形態では、実施の形態８の並列画像処理装置に多階層キャッシュ対応アクセスパターン指定手段２６を追加しているが、実施の形態９〜実施の形態１１の並列画像処理装置に対しても、多階層キャッシュ対応アクセスパターン指定手段２６を追加しても良い。
【０２３６】
以上のように、この実施の形態１２によれば、多階層のキャッシュ構成を取る場合に、最上位キャッシュの画像ブロックをプロセッサ１２１〜１２４に分割してコーナーターン処理を行う時に、各プロセッサ１２１〜１２４のキャッシュのライン数が不足しても、各画素またはキャッシュへのアクセスパターンを制御することで、キャッシュデータの退避回数等のオーバーヘッド時間を削減できるという効果が得られる。
【０２３７】
また、画像ブロック単位での処理でライン不足を解消する方法で実行した場合には、任意のパターンで実行するケースと同じ効率で実行でき、キャッシュのライン数が不足した状況でも、ライン数が充足した状況と同じ効率でコーナーターン処理を実行できるという効果が得られる。
【０２３８】
実施の形態１３．
図４０はこの発明の実施の形態１３による並列画像処理装置の構成を示すブロック図である。図において、２７は、複数の画像サイズを持つ各画像を対象にコーナーターン処理を行う時に、各画像に対して、キャッシュのラインサイズが画素サイズの整数倍にならない場合に画素の補間を行うと共に、算出した画像ブロックの整数倍で、かつ、処理対象画像を包含する最小の画像サイズを算出し、算出した各画像の最小の画像サイズの中から最大の画像サイズを選択し、選択した最大の画像サイズの領域を共有メモリ１２５上に確保する複数サイズ対応メモリ確保手段であり、その他は実施の形態１の図１に示す構成と同等である。
【０２３９】
図４１はこの実施の形態１３による並列画像処理装置の処理を示すフローチャートであり、図４２は画素のすきまを補間する方法を示す図である。
【０２４０】
次に動作について説明する。
複数サイズ対応メモリ確保手段２７は、図４１のステップＳＴ８１において、キャッシュ情報設定手段１３からキャッシュの情報を得て、ステップＳＴ８２において、処理対象の画像を１つ選択し、ステップＳＴ８３において、選択した画像の情報を画像情報設定手段１１から得る。
【０２４１】
ステップＳＴ８４において、複数サイズ対応メモリ確保手段２７は、入手したキャッシュ情報と画像の情報から、キャッシュのラインサイズが画素サイズの整数倍になるかをチェックする。ここで、画素サイズがキャッシュのラインサイズよりも大きい場合は、画素を包含する最小のライン数を対象にチェックを行う。キャッシュのラインサイズが画素サイズの整数倍になる場合は、ステップＳＴ８６において、メモリ割付手段１４は、複数サイズ対応メモリ確保手段２７の指示により、この画像データに対する画像ブロックを算出する。
【０２４２】
キャッシュのラインサイズが画素サイズの整数倍にならない場合には、ステップＳＴ８５において、複数サイズ対応メモリ確保手段２７は、図４２に示すように、処理対象画像に一定のマージンを取り、キャッシュのラインサイズが画素サイズの整数倍になるように、処理対象画像を変更する。なお、画素サイズがキャッシュのラインサイズよりも大きい場合には、画素を包含する最小のライン数を対象にこの操作を実行する。
【０２４３】
処理対象画像を変更後、ステップＳＴ８６において、メモリ割付手段１４は、複数サイズ対応メモリ確保手段２７の指示により、変更した処理対象画像の画像ブロックを算出する。ステップＳＴ８７において、複数サイズ対応メモリ確保手段２７は、画像ブロックの整数倍で、かつ、処理対象画像全体を包含する最小の画像サイズを算出する。
【０２４４】
最小の画像サイズを算出後、ステップＳＴ８８において、複数サイズ対応メモリ確保手段２７は、残りの処理対象の画像があるかをチェックする。処理対象の画像がある場合には、ステップＳＴ８２に戻り、その中から１つを選択して、上記のステップＳＴ８３からＳＴ８８までの一連の処理を実行する。ステップＳＴ８８で、処理対象の画像がない場合は、ステップＳＴ８９において、複数サイズ対応メモリ確保手段２７は、算出した全ての最小の画像サイズの中から、最大の画像サイズを選択する。ステップＳＴ９０において、複数サイズ対応メモリ確保手段２７は、選択した画像サイズの領域を、共有メモリ１２５上に確保する。ステップＳＴ９１において、複数サイズ対応メモリ確保手段２７は、処理対象の画像を１つ選択する。その後のステップＳＴ１〜ＳＴ５において、メモリ割付手段１４が、実施の形態１と同様に処理を実行する。
【０２４５】
複数サイズ対応メモリ確保手段２７での共有メモリ１２５上の確保や、補間した画像へのアクセス方法には、上記の実施の形態と同様に、画像処理プログラム１を設定可能なプログラムとして実装し、並列画像処理装置３側から設定値を与えて実現する方法がある。
【０２４６】
また、画像処理プログラム１は、指定された領域に対する操作を行うように実装し、並列画像処理装置３側で共有メモリ１２５上の確保や、補間した画像へのアクセス方法を管理し、画像処理プログラム１が意識せずに正しい領域をアクセスできるように、画像処理プログラム１へ操作領域を指示する方法でも実現できる。
【０２４７】
この他、複数サイズ対応メモリ確保手段２７では、特定のアラインメント、すなわち、キャッシュのラインサイズの整数倍のアドレスからしか、キャッシュにデータが読み込めない場合には、画像の先頭からキャッシュに読み込める位置から共有メモリ１２５上に領域を確保する。
【０２４８】
この実施の形態では、複数画像を対象としているが、単一画像を対象としても良い。また、この実施の形態では、実施の形態１の並列画像処理装置に複数サイズ対応メモリ確保手段２７を追加しているが、実施の形態２〜実施の形態１２の並列画像処理装置に対しても、複数サイズ対応メモリ確保手段２７を追加しても良い。
【０２４９】
この実施の形態では、キャッシュが１次キャッシュのみの構成であったが、多階層キャッシュ構成の時でも、実施の形態８の方法で最上位キャッシュの画像ブロックを算出し、最上位キャッシュの画像ブロックを使用して最小の画像サイズを算出しても良い。
【０２５０】
以上のように、この実施の形態１３によれば、複数の画像サイズを対象にコーナーターン処理を行う時に、算出した画像ブロックの整数倍で、かつ、処理対象画像を包含する最小の画像領域を算出し、算出した各画像の最小の画像サイズの中から最大の画像サイズを選択し、選択した最大の画像サイズの領域を共有メモリ１２５上に確保することにより、複数の異なったサイズの画像を対象に処理する場合でも、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【０２５１】
また、キャッシュのラインサイズが画像の画素サイズの整数倍にならない場合には、画素を補間することにより、各画素データへのアクセスがキャッシュ上にあることを保証することができ、画像処理全体を効率良く実行できるという効果が得られる。
【０２５２】
実施の形態１４．
図４３はこの発明の実施の形態１４による並列画像処理装置の構成を示すブロック図である。図において、２８は、複数サイズ対応メモリ確保手段２７が確保した共有メモリ１２５の領域を使用し、確保の対象となった画像よりも小さいサイズの画像処理を行う時に、選択された小さいサイズの画像に対する画像ブロック単位で、コーナーターン処理に使用する共有メモリ１２５の使用範囲を算出し、算出した使用範囲でコーナーターン処理を実行するように、各プロセッサ１２１〜１２４に処理対象の領域やアクセス手順を指定する複数サイズ対応アクセス制御手段であり、その他は実施の形態１３の図４０に示す構成と同等である。
【０２５３】
図４４はこの実施の形態１４による並列画像処理装置の処理を示すフローチャートであり、図４５は実施の形態１４でのメモリの使用範囲の一例を示す図である。
【０２５４】
次に動作について説明する。
この実施の形態は、実施の形態１３の図４１のフローチャートに示す処理を行った後、図４４のフローチャートに示す処理を行う。複数サイズ対応アクセス制御手段２８は、図４４のステップＳＴ１０１において、複数サイズ対応メモリ確保手段２７が確保した共有メモリ１２５の領域のサイズを入手し、ステップＳＴ１０２において、画像サイズの異なる複数の画像の中から、処理対象の画像を選択する。この選択方法としては、ユーザの入力による指示や、画像処理プログラム１から処理対象として選択した画像の通知を受ける方法等がある。
【０２５５】
選択画像が確定した時点で、ステップＳＴ１０３において、メモリ割付手段１４は、複数サイズ対応アクセス制御手段２８の指示により、実施の形態１と同様の方法で、選択された画像に対する画像ブロックを算出する。
【０２５６】
ステップＳＴ１０４において、複数サイズ対応アクセス制御手段２８は、算出された画像ブロックの値を受け取り、前記の複数サイズ対応メモリ確保手段２７が確保したメモリ領域のサイズの中から、コーナーターン処理を実行する共有メモリ１２５の使用範囲を決定する。この決定方法を図４５の例で示す。確保した共有メモリ１２５の領域の先頭から、単純に利用すると、図４５（ａ）に示した「共有メモリ領域の先頭から使用した場合」のように、画像ブロックからはみ出した領域を利用する可能性がある。
【０２５７】
一方、実施の形態１３で示したように、複数サイズ対応メモリ確保手段２７が確保するメモリ領域は、処理対象画像の全ての画像に対して、処理対象画像を包含し、かつ、画像ブロックの整数倍となる領域も包含することを保証している。このため、複数サイズ対応アクセス制御手段２８では、選択された画像に対する画像ブロックを基準に、処理対象画像を包含し、かつ、画像ブロックの整数倍となる領域を、コーナーターン処理を実行する領域として決定する。
【０２５８】
図４５（ｂ）に示した「本装置での利用例」は、選択したコーナーターン処理を実行する領域の一例である。コーナーターン処理を実行する領域の選択後、複数サイズ対応アクセス制御手段２８は、ステップＳＴ１０５において、使用するプロセッサ数の情報を入手し、ステップＳＴ１０６において、各プロッセに割り振る処理領域とアクセスパターンを計算する。そして、実施の形態１と同様に、ステップＳＴ５の処理を行う。
【０２５９】
この実施の形態では、実施の形態１を基にした実施の形態１３の並列画像処理装置に複数サイズ対応アクセス制御手段２８を追加しているが、実施の形態２〜実施の形態１２の並列画像処理装置に対しても、複数サイズ対応メモリ確保手段２７と複数サイズ対応アクセス制御手段２８を追加しても良い。
【０２６０】
また、実施の形態１３と同様に、多階層キャッシュ構成でも良い。この場合には、実施の形態１０の多階層画像ブロック用メモリ確保手段２４と連動して、下位のキャッシュから順に共有メモリ１２５の領域を設定していくと有効である。
【０２６１】
以上のように、この実施の形態１４によれば、複数の画像を対象に確保した大きいサイズの共有メモリ１２５の領域を使用して、確保の対象となった画像よりも小さいサイズの画像の処理を行う時に、選択された小さいサイズの画像に対する画像ブロック単位で、コーナーターン処理の実行時に使用する共有メモリ１２５の使用範囲を算出し、かつ、算出した使用範囲で効率良くコーナーターン処理を行うように、各プロセッサ１２１〜１２４へ処理対象の領域やアクセス手順を指定することにより、キャッシュによるオーバーヘッド時間を低減できるという効果が得られる。
【０２６２】
また、１度確保した共有メモリ１２５の領域を、複数のサイズの画像で共同して利用しながら、効率良くコーナーターン処理を実行できるという効果が得られる。
【０２６３】
実施の形態１５．
図４６はこの発明の実施の形態１５による並列画像処理装置の構成を示すブロック図である。図において、２９は、コーナーターン処理の前に実行する事前実行処理の内容を入手すると共に、画像情報設定手段１１に設定されている画像情報、使用プロセッサ数設定手段１２に設定されているプロセッサ１２１〜１２４の個数情報、キャッシュ情報設定手段１３に設定されているキャッシュ情報を入手し、メモリ割付手段１４が算出した画像ブロック単位を基準として事前実行処理とコーナーターン処理を同時に実行し、各プロセッサ１２１〜１２４の負荷が均等になるように、各プロセッサ１２１〜１２４に共有メモリ１２５の対象領域を割り付ける前処理対応メモリ割付手段であり、その他は実施の形態１の図１に示す構成と同等である。
【０２６４】
図４７はこの実施の形態１５による並列画像処理装置の処理を示すフローチャートであり、図４８は各プロセッサ１２１〜１２４への処理の割り付けと処理の段数を示す図であり、図４９は各プロセッサ１２１〜１２４での各処理の段で処理を実行する時のアクセスパターンの一例を示す図である。
【０２６５】
次に動作について説明する。
図４７のステップＳＴ１１１において、メモリ割付手段１４は、前処理対応メモリ割付手段２９の指示により、画像ブロックを算出する。ステップＳＴ１１２において、前処理対応メモリ割付手段２９は、コーナーターン処理の前に実行する事前実行処理の内容を入手する。この入手方法としては、ユーザの入力による指示や、画像処理プログラム１から対象の処理について通知を受ける方法等がある。
【０２６６】
ステップＳＴ１１３において、前処理対応メモリ割付手段２９は、入手した事前実行処理が画素単位の処理であるかをチェックし、事前実行処理が、各画素単位の処理である場合は、ステップＳＴ１１４において、前処理対応メモリ割付手段２９は、使用プロセッサ数設定手段１２からプロセッサ１２１〜１２４の個数を入手する。
【０２６７】
ステップＳＴ１１５において、前処理対応メモリ割付手段２９は、処理前の画像に対して、コーナーターン処理と同様に、画像ブロック単位で共有メモリ１２５の領域にアクセスし、アクセスした領域において、各画素の単位で、事前実行処理を実行し、事前実行処理の計算結果を、各画素の単位で処理結果の画像に書き込むことで、結果として、画像ブロック単位を基準として、事前実行処理とコーナーターン処理を同時に実行する、画像処理プログラム１に指示する。
【０２６８】
上記ステップＳＴ１１３において、事前実行処理が画素単位の処理でない場合には、ステップＳＴ１１６において、前処理対応メモリ割付手段２９は、ライン単位の処理パターンを選択する。そして、前処理対応メモリ割付手段２９は、図４８に示すように、画像ブロック幅の、処理前画像の列と処理結果画像の行を、各プロセッサに割り付ける基準にする担当領域として算出する。図４８ではプロセッサ数をＭ個としている。図４８のプロセッサ（１）、プロセッサ（２）、…、プロセッサ（Ｍ）の担当領域は、仮想的なプロセッサ（１）〜（Ｍ）に割り当てた担当領域である。
【０２６９】
また、前処理対応メモリ割付手段２９は、画像ブロック幅の、処理前画像での１行分と対応する処理結果画像の１列を、各段で実行する処理部分とし、第１段〜第Ｎ段の処理部分として算出する。仮想的なプロセッサ（１）〜（Ｍ）では、第１段から順に、第Ｎ段まで、各段ごとに、事前実行処理とコーナーターン処理を実行すると仮定する。
【０２７０】
各段ごとの処理について図４９を使って説明する。
事前実行処理が、レンジ又はアジマス方向のアクセスの場合、ＳＡＲ画像の処理では、１画素分の計算を行うのに、その方向１行分のデータを必要とする。図４９の例では、画素Ａ１分の計算を行うのに、処理前画像の（ａ）の行の全画素のデータを必要とする。このため、各段ごとの処理では、処理前画像の（ａ）の行の全画素のデータを使って、４回事前実行処理を行うことで、Ａ１，Ａ２，Ａ３，Ａ４の結果を得る。これを、（ｂ），（ｃ），（ｄ）の行についても同様に行うことで、仮想的なプロセッサ（１）の第１段の部分の処理結果が得られる。
【０２７１】
前処理対応メモリ割付手段２９は、仮想的なプロセッサ（１）〜（Ｍ）に割り付ける担当領域と第１段〜第Ｎ段の処理部分を算出後、ステップＳＴ１１７において、画像情報設定手段１１から画像情報、使用プロセッサ数設定手段１２からプロセッサ１２１〜１２４の個数、キャッシュ情報設定手段１３からキャッシュ情報を、それぞれ入手する。
【０２７２】
ステップＳＴ１１８において、前処理対応メモリ割付手段２９は、各プロセッサへの処理の割り付け方法を算出する。ここでは、まず、仮想的なプロセッサ（１）〜（Ｍ）に割り当てた担当領域の各段の処理を実行するのに、十分なキャッシュのラインサイズがあるかチェックし、全てのデータをキャッシュに入れて処理できるだけの十分な領域があれば、特にアクセス方法についての指示は行わない。キャッシュのラインサイズが不足し、キャッシュデータの退避が発生する場合には、各段ごとの処理での、データのアクセス方法を指示する。
【０２７３】
ここでは、キャッシュデータの退避方法や、キャッシュのリードミスにかかる時間から、オーバーヘッドが最小となるアクセス方法を算出する。この例としては、図４９のように、（ａ）の行を処理するときに（ａ１），（ａ２）の順で交互にアクセスする方法がある。また、各プロセッサに処理負荷が均等になるように、仮想的なプロセッサ（１）〜（Ｍ）に担当領域を算出する。
【０２７４】
ステップＳＴ１１９において、前処理対応メモリ割付手段２９は、上記で算出した割り付け方法に従って、事前実行処理とコーナーターン処理を実行するよう共有メモリ１２５の領域の割り付けを、画像処理プログラム１に指示する。
【０２７５】
この実施の形態では、画像処理としてＳＡＲ画像の再生処理を行っているが、ＳＡＲ画像の再生処理以外でも、画像の行または列方向の処理と、各画素単位の処理で構成され、途中でコーナーターン処理に相当する処理を実行する画像処理にも適用できる。
【０２７６】
この実施の形態では、実施の形態１の並列画像処理装置に前処理対応メモリ割付手段２９を追加しているが、実施の形態２〜実施の形態１４の並列画像処理装置に対しても、前処理対応メモリ割付手段２９を追加しても良い。
【０２７７】
プロセッサ１２１〜１２４への処理の割り付けでは、使用するプロセッサ１２１〜１２４の個数により、画像ブロックや担当領域の個数が均等に分割できないケースがある。この場合には、他の実施の形態で示した画像ブロックや画像ブロックの帯を、複数のプロセッサ１２１〜１２４で実行する方法を応用して、画像ブロックや担当領域を複数のプロセッサ１２１〜１２４で、容易に並列実行することができる。
【０２７８】
以上のように、この実施の形態１５によれば、コーナーターン処理用に算出した画像ブロック単位を基準として、事前実行処理とコーナーターン処理を同時に実行し、かつ、各プロセッサ１２１〜１２４の処理負荷が均等になるように、各プロセッサ１２１〜１２４に共有メモリ１２５の対象領域を割り付けることにより、コーナーターン処理において、事前実行処理の完了待ちをする必要がなくなり、画像処理全体のオーバーヘッド時間を低減できるという効果が得られる。
【０２７９】
実施の形態１６．
図５０はこの発明の実施の形態１６の並列画像処理装置の構成を示すブロック図である。図において、３０は、コーナーターン処理の後に実行する事後実行処理の内容を入手すると共に、画像情報設定手段１１に設定されている画像情報、使用プロセッサ数設定手段１２に設定されているプロセッサ１２１〜１２４の個数情報、キャッシュ情報設定手段１３に設定されているキャッシュ情報を入手し、メモリ割付手段１４が算出した画像ブロック単位を基準としてコーナーターン処理と事後実行処理を同時に実行し、各プロセッサ１２１〜１２４の負荷が均等になるように、各プロセッサ１２１〜１２４に共有メモリ１２５の対象領域を割り付ける後処理対応メモリ割付手段であり、その他は実施の形態１の図１に示す構成と同等である。
【０２８０】
図５１はこの実施の形態１６による並列画像処理装置の処理を示すフローチャートであり、図５２は、各プロセッサへの処理の割り付けと、各プロセッサでのアクセスパターンの一例を示す図である。図５３はライン単位の処理パターンを示す図である。
【０２８１】
次に動作について説明する。
ステップＳＴ１３１において、メモリ割付手段１４は、後処理対応メモリ割付手段３０の指示により画像ブロックを算出する。ステップＳＴ１３２において、後処理対応メモリ割付手段３０は、コーナーターン処理後に実行する事後実行処理の内容を入手する。入手の方法は、実施の形態１５の前処理対応メモリ割付手段２９と同様である。
【０２８２】
ステップＳＴ１３３において、後処理対応メモリ割付手段３０は、入手した事後実行処理が画素単位の処理であるかをチェックし、事後実行処理が、各画素単位の処理である場合は、ステップＳＴ１３４において、後処理対応メモリ割付手段３０は、使用プロセッサ数設定手段１２からプロセッサ１２１〜１２４の個数を入手する。
【０２８３】
ステップＳＴ１３５において、後処理対応メモリ割付手段３０は、処理前の画像に対して、コーナーターン処理と同様に、画像ブロック単位で共有メモリ１２５の領域にアクセスし、アクセスした領域において、各画素の単位で、事後実行処理を実行し、事後実行処理の計算結果を、各画素の単位で処理結果の画像に書き込むことで、結果として、画像ブロック単位を基準として、コーナーターン処理と事後実行処理を同時に行うよう、画像処理プログラム１に指示する。
【０２８４】
上記ステップＳＴ１３３において、事後実行処理が画素単位の処理でない場合には、ステップＳＴ１３６において、後処理対応メモリ割付手段３０は、ライン単位の処理パターンを選択する。そして、後処理対応メモリ割付手段３０は、図５２に示すように、画像ブロック幅の、処理前画像の列と処理結果画像の行を、各プロセッサ１２１〜１２４に割り付ける基準にする担当領域として算出する。図５２ではプロセッサ数をＭ個としている。図５２のプロセッサ（１）、プロセッサ（２）、…、プロセッサ（Ｍ）の担当領域は、仮想的なプロセッサ（１）〜（Ｍ）に割り付けた担当領域である。
【０２８５】
ただし、各段で実行する処理部分については、コーナーターン処理用に書き込んだデータをそのまま使用できる。事後実行処理は、算出した担当領域を基準に、コーナーターン処理結果の書き込み直後に、処理結果画像の１行単位で処理を実行するものとする。
【０２８６】
ステップＳＴ１３７において、後処理対応メモリ割付手段３０は、画像情報設定手段１１から画像情報、使用プロセッサ数設定手段１２からプロセッサ１２１〜１２４の個数、キャッシュ情報設定手段１３からキャッシュ情報を、それぞれ入手する。
【０２８７】
ステップＳＴ１３８において、後処理対応メモリ割付手段３０は、各プロセッサへの処理の割り付け方法を算出する。ここでは、まず、仮想的なプロセッサ（１）〜（Ｍ）に割り当てた担当領域の各段の処理を実行するのに、十分なキャッシュのラインサイズがあるかチェックし、全てのデータをキャッシュに入れて処理できるだけの十分な領域があれば、特にアクセス方法についての指示は行わない。キャッシュのラインサイズが不足し、キャッシュデータの退避が発生する場合には、データのアクセス方法を指示する。
【０２８８】
ここでは、キャッシュデータの退避方法や、キャッシュのリードミスにかかる時間から、図５３に示すように、オーバーヘッドが最小となるアクセス方法を算出する。また、各プロセッサに処理負荷が均等になるように、仮想的なプロセッサ（１）〜（Ｍ）に担当領域を算出する。
【０２８９】
ステップＳＴ１３９において、後処理対応メモリ割付手段３０は、上記で算出した割り付け方法に従って、コーナーターン処理と事後実行処理を実行するよう共有メモリ１２５の領域の割り付けを、画像処理プログラム１に指示する。
【０２９０】
この実施の形態では、実施の形態１の並列画像処理装置に後処理対応メモリ割付手段３０を追加しているが、実施の形態２〜実施の形態１４の並列画像処理装置に対しても、後処理対応メモリ割付手段３０を追加しても良い。
【０２９１】
また、実施の形態１５と同様に、ＳＡＲ画像の再生処理以外の画像処理でも適用できる。また、画像ブロックや担当領域の複数のプロセッサでの並列実行も、実施の形態１５と同様に容易にできる。
【０２９２】
以上のように、この実施の形態１６によれば、コーナーターン処理用に算出した画像ブロック単位を基準として、コーナーターン処理と事後実行処理を同時に実行し、かつ、各プロセッサ１２１〜１２４の処理負荷が均等になるように、各プロセッサ１２１〜１２４に共有メモリ１２５の対象領域を割り付けることにより、事後実行処理において、コーナーターン処理の完了待ちをする必要がなくなり、画像処理全体のオーバーヘッド時間を低減できるという効果が得られる。
【０２９３】
実施の形態１７．
図５４はこの発明の実施の形態１７による並列画像処理装置の構成を示すブロック図である。図において、２９は実施の形態１５における前処理対応メモリ割付手段、３０は実施の形態１６における後処理対応メモリ割付手段、３１は、コーナーターン処理と同時に実行する事前実行処理又は事後実行処理を選択する前後処理選択手段であり、その他は実施の形態１の図１に示す構成と同等である。図５５はこの実施の形態１７による並列画像処理装置の処理を示すフローチャートである。
【０２９４】
次に動作について説明する。
ＳＡＲ画像の再生処理では、画像サイズに加えて、ＳＡＲ画像を撮像する人工衛星や航空機等のプラットホームの種類等により、再生処理でのプラットホームの動揺補整等、再生方法が異なるケースがある。この場合、ＳＡＲ画像の再生処理処理装置では、複数の再生方法に柔軟に対応することが求められる。
【０２９５】
前後処理選択手段３１は、図５５のステップＳＴ１５１において、複数の種類の事前実行処理と事後実行処理を登録しておく。登録方法は、ユーザの入力による指示や、画像処理プログラム１から通知を受ける方法、画像処理プログラム１を解析して自動的に入手する方法等がある。
【０２９６】
ステップＳＴ１５２において、前後処理選択手段３１は、登録した処理の中から、コーナーターン処理と同時に実行する処理を選択する。この選択方法には、ユーザの入力による指示や、画像処理プログラム１から通知を受ける方法等がある。また、過去の実行時刻と実行方法を記録しておき、その情報から最も時間が短くなると期待されるものを選択する方法もある。
【０２９７】
前後処理選択手段３１は、ステップＳＴ１５３において、選択した処理が事前実行処理か否かをチェックし、事前実行処理の場合には、ステップＳＴ１５４において、前処理対応メモリ割付手段２９に選択した事前実行処理の実行を指示する。その後の処理は、実施の形態１５と同じ処理を行う。
【０２９８】
ステップＳＴ１５３で、事前実行処理でなければ、ステップＳＴ１５５において、前後処理選択手段３１は、後処理対応メモリ割付手段３０に選択した事後実行処理の実行を指示する。その後の処理は、実施の形態１６と同じ処理を行う。
【０２９９】
この実施の形態では、画像処理としてＳＡＲ画像の再生処理を行っているが、ＳＡＲ画像の再生処理以外でも、画像の行または列方向の処理と、各画素単位の処理で構成され、途中でコーナーターン処理に相当する処理を実行する画像処理にも適用できる。
【０３００】
この実施の形態では、実施の形態１の並列画像処理装置に前後処理選択手段３１と前処理対応メモリ割付手段２９と後処理対応メモリ割付手段３０を追加しているが、実施の形態２〜実施の形態１４の並列画像処理装置に対しても、前後処理選択手段３１と前処理対応メモリ割付手段２９と後処理対応メモリ割付手段３０を追加しても良い。
【０３０１】
以上のように、この実施の形態１７によれば、コーナーターン処理と同時に実行する事前実行処理又は事後実行処理を選択できるようにしているので、複数の処理方法から選択して処理を行う必要があるＳＡＲ画像の再生処理でも、任意の処理とコーナーターン処理と同時に実行することができ、完了待ちによるオーバーヘッド時間を低減できるという効果が得られる。
【０３０２】
【発明の効果】
以上のように、この発明によれば、画像情報、プロセッサの個数情報、キャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、算出した画像ブロック単位で、各プロセッサがコーナーターン処理を実行するように共有メモリの対象領域を割り付けることにより、キャッシュのライトミスとリードミスを削減し、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３０３】
この発明によれば、画像サイズが算出した画像ブロックの整数倍にならない時に、画像サイズが画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保することにより、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３０４】
この発明によれば、画像サイズが算出した画像ブロックの整数倍にならない時に、画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した画像ブロックの帯で画像のアクセス方向を指定することにより、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３０５】
この発明によれば、画像サイズが算出した画像ブロックの整数倍にならない時に、画像ブロックの幅の行又は列を画像ブロックの帯として算出し、算出した上記画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、プロセッサの個数の整数倍にならない時に、画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定することにより、キャッシュによるオーバーヘッド時間を低減できると共に、効率の良いコーナーターン処理を実行できるという効果がある。
【０３０６】
この発明によれば、画像サイズが画像ブロックの整数倍にならない時に、複数の修正方法を備え、その修正方法の判定条件を設定していることにより、キャッシュによるオーバーヘッド時間を低減できると共に、複数の対処方法から最適の方法を選択することができ、効率の良いコーナーターン処理を実行できるという効果がある。
【０３０７】
この発明によれば、要求仕様として与えられる時間制約と各プロセッサの処理時間等の時間制約条件を設定し、実際に使用する上記プロセッサの個数を画像処理プログラムに指定することにより、要求仕様として与えられる時間制約条件の情報に基づいて最適のプロセッサ数を算出でき、算出したプロセッサ数で効率の良いコーナーターン処理を実行できるという効果がある。
【０３０８】
この発明によれば、画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像へのアクセスパターンを算出し、画像処理プログラムに指定することにより、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３０９】
この発明によれば、複数の画像サイズを持つ各画像を対象にコーナーターン処理を行う時に、各画像に対して、キャッシュのラインサイズが画素サイズの整数倍にならない場合に画素の補間を行うと共に、算出した画像ブロックの整数倍で、かつ、処理対象画像を包含する最小の画像サイズを算出し、算出した各画像の最小の画像サイズの中から最大の画像サイズを選択し、選択した最大の画像サイズの領域を共有メモリ上に確保することにより、複数の異なったサイズの画像を対象に処理する場合でも、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３１０】
この発明によれば、確保した共有メモリの対象領域を使用し、確保の対象となった画像よりも小さいサイズの画像処理を行う時に、選択された小さいサイズの画像に対する画像ブロック単位で、コーナーターン処理に使用する共有メモリの使用範囲を算出し、算出した使用範囲でコーナーターン処理を実行するように、各プロセッサに処理対象の領域やアクセス手順を指定することにより、キャッシュによるオーバーヘッド時間を低減できると共に、１度確保した共有メモリの領域を、複数のサイズの画像で共同して利用しながら、効率良くコーナーターン処理を実行できるという効果がある。
【０３１１】
この発明によれば、画像情報、キャッシュ情報を入手し、１次キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、画像情報、プロセッサの個数情報、キャッシュ情報を入手し、算出した１次キャッシュの画像ブロックをもとに、キャッシュの階層ごとに低位キャッシュの複数の画像ブロックを包含し１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、算出した最上位キャッシュの画像ブロック単位でコーナーターン処理を実行し、かつ、最上位キャッシュの画像ブロックを実行する個数がプロセッサ間で均等になるように、各プロセッサへ共有メモリの対象領域を割り付けるよう画像処理プログラムに指示することにより、キャッシュによるオーバーヘッド時間を低減できると共に、効率の良いコーナーターン処理を実行できるという効果がある。
【０３１２】
この発明によれば、画像サイズが最上位キャッシュの画像ブロックの整数倍にならない時に、画像サイズが最上位キャッシュの画像ブロックの整数倍になるように、画像領域を拡張して共有メモリ上に確保することにより、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３１３】
この発明によれば、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍にならない時に、上位キャッシュのラインサイズが、低位キャッシュの画像ブロックの整数倍になるように、低位キャッシュの画像ブロックの領域を拡張して共有メモリ上に確保することにより、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３１４】
この発明によれば、画像サイズが算出した最上位キャッシュの画像ブロックの整数倍にならない時に、最上位キャッシュの画像ブロックの行又は列を最上位キャッシュの画像ブロックの帯として算出し、算出した画像ブロックの帯で画像のアクセス方向を指定すると共に、算出した画像ブロックの帯の個数が、プロセッサの個数の整数倍にならない時に、画像ブロックの帯を分割して、複数のプロセッサで処理するよう指定することにより、キャッシュによるオーバーヘッド時間を低減できると共に、効率の良いコーナーターン処理を実行できるという効果がある。
【０３１５】
この発明によれば、算出した画像ブロックの処理に必要なキャッシュのライン数が不足する時に、キャッシュデータの退避回数が最小になる画像又は低次のキャッシュへのアクセスパターンを指定することにより、キャッシュによるオーバーヘッド時間を低減できるという効果がある。
【０３１６】
この発明によれば、画像情報、キャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、コーナーターン処理の前に実行する事前実行処理の内容を入手すると共に、画像情報、プロセッサの個数情報、キャッシュ情報を入手し、算出した画像ブロック単位を基準として事前実行処理とコーナーターン処理を同時に実行し、各プロセッサの負荷が均等になるように、各プロセッサに共有メモリの対象領域を割り付けることにより、コーナーターン処理において、事前実行処理の完了待ちをする必要がなくなり、画像処理全体のオーバーヘッド時間を低減できるという効果がある。
【０３１７】
この発明によれば、画像情報、キャッシュ情報を入手し、キャッシュのライトミスとリードミスにかかるオーバーヘッド時間が最小となる１辺の長さが１キャッシュラインサイズの正方形の処理領域の画像ブロックを算出し、コーナーターン処理の後に実行する事後実行処理の内容を入手すると共に、画像情報、プロセッサの個数情報、キャッシュ情報を入手し、算出した画像ブロック単位を基準としてコーナーターン処理と事後実行処理を同時に実行し、各プロセッサの負荷が均等になるように、各プロセッサに共有メモリの対象領域を割り付けることにより、事後実行処理において、コーナーターン処理の完了待ちをする必要がなくなり、画像処理全体のオーバーヘッド時間を低減できるという効果がある。
【０３１８】
この発明によれば、コーナーターン処理と同時に実行する事前実行処理又は事後実行処理を選択することにより、任意の処理とコーナーターン処理と同時に実行することができ、完了待ちによるオーバーヘッド時間を低減できるという効果がある。
【図面の簡単な説明】
【図１】  この発明の実施の形態１による並列画像処理装置の構成を示すブロック図である。
【図２】  この発明の実施の形態１による並列画像処理装置の処理を示すフローチャートである。
【図３】  この発明の実施の形態１による基本的なメモリ割り付けの概念を示す図である。
【図４】  この発明の実施の形態１によるキャッシュアクセスの概念を示す図である。
【図５】  この発明の実施の形態１による具体的なメモリ割り付けの実行例を示す図である。
【図６】  この発明の実施の形態１による１画像ブロックを複数プロセッサで処理する一例を示す図である。
【図７】  この発明の実施の形態２による並列画像処理装置の構成を示すブロック図である。
【図８】  この発明の実施の形態２による並列画像処理装置の処理を示すフローチャートである。
【図９】  この発明の実施の形態２によるメモリ確保の実行例を示す図である。
【図１０】  この発明の実施の形態３による並列画像処理装置の構成を示すブロック図である。
【図１１】  この発明の実施の形態３による並列画像処理装置の処理を示すフローチャートである。
【図１２】  この発明の実施の形態３による、アジマス方向の画像サイズが画像ブロックの整数倍にならない場合にアクセス方向を指定した処理内容を示す図である。
【図１３】  この発明の実施の形態３による、レンジ方向の画像サイズが画像ブロックの整数倍にならない場合にアクセス方向を指定した処理内容を示す図である。
【図１４】  この発明の実施の形態４による並列画像処理装置の構成を示すブロック図である。
【図１５】  この発明の実施の形態４による並列画像処理装置の処理を示すフローチャートである。
【図１６】  この発明の実施の形態４による、アジマス方向に画像サイズが画像ブロックの帯の整数倍にならない時の処理内容を示す図である。
【図１７】  この発明の実施の形態４による、レンジ方向に画像サイズが画像ブロックの帯の整数倍にならない時の処理内容を示す図である。
【図１８】  この発明の実施の形態５による並列画像処理装置の構成を示すブロック図である。
【図１９】  この発明の実施の形態５による並列画像処理装置の処理を示すフローチャートである。
【図２０】  この発明の実施の形態６による並列画像処理装置の構成を示すブロック図である。
【図２１】  この発明の実施の形態６による並列画像処理装置の処理を示すフローチャートである。
【図２２】  この発明の実施の形態７による並列画像処理装置の構成を示すブロック図である。
【図２３】  この発明の実施の形態７による並列画像処理装置の処理を示すフローチャートである。
【図２４】  この発明の実施の形態７によるキャッシュのライン数が不足した時のアクセスパターンを示す図である。
【図２５】  この発明の実施の形態８による並列画像処理装置の構成を示すブロック図である。
【図２６】  この発明の実施の形態８による並列画像処理装置の処理を示すフローチャートである。
【図２７】  この発明の実施の形態８によるメモリ割り付けの概念を示す図である。
【図２８】  この発明の実施の形態８による画像ブロックを複数のプロセッサで処理する一例を示す図である。
【図２９】  この発明の実施の形態９による並列画像処理装置の構成を示すブロック図である。
【図３０】  この発明の実施の形態９による並列画像処理装置の処理を示すフローチャートである。
【図３１】  この発明の実施の形態１０による並列画像処理装置の構成を示すブロック図である。
【図３２】  この発明の実施の形態１０による並列画像処理装置の処理を示すフローチャートである。
【図３３】  この発明の実施の形態１０による領域拡張方向の概念を示す図である。
【図３４】  この発明の実施の形態１１による並列画像処理装置の構成を示すブロック図である。
【図３５】  この発明の実施の形態１１による並列画像処理装置の処理を示すフローチャートである。
【図３６】  この発明の実施の形態１１によるアクセス方向指定方法の概念を示す図である。
【図３７】  この発明の実施の形態１２による並列画像処理装置の構成を示すブロック図である。
【図３８】  この発明の実施の形態１２による並列画像処理装置の処理を示すフローチャートである。
【図３９】  この発明の実施の形態１２による２次キャッシュのライン数が不足した時のアクセスパターンを示す図である。
【図４０】  この発明の実施の形態１３による並列画像処理装置の構成を示すブロック図である。
【図４１】  この発明の実施の形態１３による並列画像処理装置の処理を示すフローチャートである。
【図４２】  この発明の実施の形態１３による画素のすき間を補間する方法を示す図である。
【図４３】  この発明の実施の形態１４による並列画像処理装置の構成を示すブロック図である。
【図４４】  この発明の実施の形態１４による並列画像処理装置の処理を示すフローチャートである。
【図４５】  この発明の実施の形態１４によるメモリの使用範囲の一例を示す図である。
【図４６】  この発明の実施の形態１５による並列画像処理装置の構成を示すブロック図である。
【図４７】  この発明の実施の形態１５による並列画像処理装置の処理を示すフローチャートである。
【図４８】  この発明の実施の形態１５による各プロセッサへの処理の割り付けと処理の段数を示す図である。
【図４９】  この発明の実施の形態１５による各プロセッサでの処理の段で処理を実行する時のアクセスパターンの一例を示す図である。
【図５０】  この発明の実施の形態１６による並列画像処理装置の構成を示すブロック図である。
【図５１】  この発明の実施の形態１６による並列画像処理装置の処理を示すフローチャートである。
【図５２】  この発明の実施の形態１６による各プロセッサへの処理の割り付けと各プロセッサでのアクセスパターンの一例を示す図である。
【図５３】  この発明の実施の形態１６によるライン単位の処理のパターンを示す図である。
【図５４】  この発明の実施の形態１７による並列画像処理装置の構成を示すブロック図である。
【図５５】  この発明の実施の形態１７による並列画像処理装置の処理を示すフローチャートである。
【図５６】  従来のシステムの構成を示すブロック図である。
【図５７】  従来のＳＭＰの構成の一例を示すブロック図である。
【図５８】  従来のＳＭＰでのＳＡＲ画像再生処理を実行する方法の一例を示す図である。
【図５９】  従来のＳＭＰでのＳＡＲ画像再生処理を実行する方法の一例を示す図である。
【図６０】  従来の複数のプロセッサが割り当てた画像上の領域を示す図である。
【図６１】  従来の複数のプロセッサが割り付けたメモリ上の位置を示す図である。
【符号の説明】
１  画像処理プログラム、２  プラットホーム、３  並列画像処理装置、１１画像情報設定手段、１２  使用プロセッサ数設定手段、１３  キャッシュ情報設定手段、１４  メモリ割付手段、１５  メモリ確保手段、１６  アクセス方向指定手段、１７  多重書き込み対応アクセス方向指定手段、１８  はみ出し修正方法設定手段、１９  処理時間制約設定手段、２０  実行プロセッサ数指定手段、２１  画素アクセス順序指定手段、２２  多階層キャッシュ対応メモリ割付手段、２３  多階層キャッシュ対応メモリ確保手段、２４  多階層画像ブロック用メモリ確保手段、２５  多階層キャッシュ対応アクセス方向指定手段、２６  多階層キャッシュ対応アクセスパターン指定手段、２７  複数サイズ対応メモリ確保手段、２８  複数サイズ対応アクセス制御手段、２９  前処理対応メモリ割付手段、３０  後処理対応メモリ割付手段、３１  前後処理選択手段、１０１  磁気テープ、１０２  レンジ方向圧縮装置、１０３−１  ２次元画像メモリ、１０３−２  ２次元画像メモリ、１０４  ２次元画像メモリ制御部、１０５  アジマス方向圧縮装置、１０６  磁気テープ、１０７  ＣＰＵ、１０８  メインメモリ、１０９  ＦＦＴ装置、１１０  データバス、１２１，１２２，１２３，１２４プロセッサ、１２５  共有メモリ。
【図１】
0003850599.tif 000002
【図２】
0003850599.tif 000003
【図３】
0003850599.tif 000004
【図４】
0003850599.tif 000005
【図５】
0003850599.tif 000006
【図６】
0003850599.tif 000007
【図７】
0003850599.tif 000008
【図８】
0003850599.tif 000009
【図９】
0003850599.tif 000010
【図１０】
0003850599.tif 000011
【図１１】
0003850599.tif 000012
【図１２】
0003850599.tif 000013
【図１３】
0003850599.tif 000014
【図１４】
0003850599.tif 000015
【図１５】
0003850599.tif 000016
【図１６】
0003850599.tif 000017
【図１７】
0003850599.tif 000018
【図１８】
0003850599.tif 000019
【図１９】
0003850599.tif 000020
【図２０】
0003850599.tif 000021
【図２１】
0003850599.tif 000022
【図２２】
0003850599.tif 000023
【図２３】
0003850599.tif 000024
【図２４】
0003850599.tif 000025
【図２５】
0003850599.tif 000026
【図２６】
0003850599.tif 000027
【図２７】
0003850599.tif 000028
【図２８】
0003850599.tif 000029
【図２９】
0003850599.tif 000030
【図３０】
0003850599.tif 000031
【図３１】
0003850599.tif 000032
【図３２】
0003850599.tif 000033
【図３３】
0003850599.tif 000034
【図３４】
0003850599.tif 000035
【図３５】
0003850599.tif 000036
【図３６】
0003850599.tif 000037
【図３７】
0003850599.tif 000038
【図３８】
0003850599.tif 000039
【図３９】
0003850599.tif 000040
【図４０】
0003850599.tif 000041
【図４１】
0003850599.tif 000042
【図４２】
0003850599.tif 000043
【図４３】
0003850599.tif 000044
【図４４】
0003850599.tif 000045
【図４５】
0003850599.tif 000046
【図４６】
0003850599.tif 000047
【図４７】
0003850599.tif 000048
【図４８】
0003850599.tif 000049
【図４９】
0003850599.tif 000050
【図５０】
0003850599.tif 000051
【図５１】
0003850599.tif 000052
【図５２】
0003850599.tif 000053
【図５３】
0003850599.tif 000054
【図５４】
0003850599.tif 000055
【図５５】
0003850599.tif 000056
【図５６】
0003850599.tif 000057
【図５７】
0003850599.tif 000058
【図５８】
0003850599.tif 000059
【図５９】
0003850599.tif 000060
【図６０】
0003850599.tif 000061
【図６１】
0003850599.tif 000062