(57)【特許請求の範囲】
【請求項１】
ある形式で表現された３次元形状を形状処理システムに読み込む際に、該システムを実行するＣＰＵの数を検出し、形状オブジェクトを前記ＣＰＵ数に合わせて分割し、読み込み処理のためにマルチスレッド技術を利用して、３次元形状の読み込みのためのスレッド実行関数を前記ＣＰＵ数分だけ発生させ、該スレッド実行関数をそれぞれのＣＰＵで並列に実行させて、前記分割された形状オブジェクトをそれぞれ読み込ませることによって、３次元形状の読み込み機能を高速に実現することを特徴とする形状処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、形状処理方法、より詳細には、分散型３次元形状データの変換方法に関し、例えば、３次元ＣＡＤ／ＣＡＭ／ＣＡＥにおける形状データの交換等に応用可能なものである。
【０００２】
【従来の技術】
３次元形状設定において、データ交換は、設計効率を左右する重要な機能の一つである。形状設計は一つのＣＡＤ（Computer Aided Design）／ＣＡＭ（Computer Aided Manufactureing）システムだけで行われるのではなく、設計物に応じて複数のシステムを使い分けるので、システム間で３次元形状を受け渡す必要が生じることが理由の一つである。
【０００３】
一般に、データ交換は、ＩＧＥＳ（Smith,B.,Rinaudot,G.R.,Reed,K.A.,and Wright,T.:INITIAL GRAPHICS EXCHANGE SPECIFICATION(IGES) VERSION 4.0,National Bureau of Standard,Spring field,VA,(1988).）やＳＴＥＰ（岸浪建史：ＳＴＥＰによる技術データ統合の現状と動向，精密工学会誌，第６２巻，第１号，pp.19-23(1996).）などの標準的なデータフォーマットを介して行われるか、システム間で直接データを変換するダイレクトトランスレーターを利用するかのどちらかの手法により実現されている。最近では、ＣＯＭ／ＤＣＯＭ技術を利用した形状データ交換用ＡＰＩによるデータ交換技術も提案されている（http://www.dmac.org/）。
【０００４】
データ交換では、形状データが他のシステムに高速かつ正確に受け渡されることが要求される。しかし、一般には、システム間の形状表現方法や精度の違いが障害となり、表現方法の変換や幾何形状の近似計算を行いながらデータを取り込む。この時、ユーザは、幾何形状の近似精度を変更しながら何度かデータ変換を試み、近似された形状が意図通りになる最適な精度を探索する。このように、データ変換は試行錯誤による計算量が膨大であり、幾何形状の近似計算自体も計算負荷が高いため、短時間で意図するデータを得ることが困難な場合も多い。
【０００５】
データ変換のための実行時間を短縮するための一つの方法として、例えば、同一プロセス内で並列処理を実現する手段として、マルチスレッドプログラミングを利用することが考えられる（Microsoft Developer Studioのヘルプ参照）。マルチスレッドプログラミングでは、スレッドと呼ばれる実行単位（ＯＳによりスケジュールされる最小単位）を複数生成し、それぞれのスレッドに別々の作業を割り当てることができる。従って、複数のＣＰＵを搭載する計算機では、それぞれのＣＰＵにスレッドが割り当てられ並列にスレッドが実行されるため、実行時間の短縮が期待できる。
【０００６】
【発明が解決しようとする課題】
あるシステムで作成した３次元形状を別のシステムへ受け渡すためのデータ変換技術は、形状データの共有化を促進し、データを有効利用する上でも必須の技術である。しかし、データ交換ではシステム間の幾何精度の違いや、表現形式の違いによりデータを変換できない、あるいは、データ量が多い場合や複雑な形状の場合には、変換に多大な時間を必要とするため事実上変換不可能となるなどの問題がある。
【０００７】
本発明は、上述のごとき実情に鑑みてなされたもので、データ変換の機能をマルチスレッドにより並列に実行することによって変換に要する時間を短縮し、時間的制約によりデータ交換が事実上不可能であったケースで、データ交換を可能にする方法を提案することを目的として成されたものである。
【０００８】
【課題を解決するための手段】
請求項１記載の発明は、ある形式で表現された３次元形状を形状処理システムに読み込む際に、該システムを実行するＣＰＵの数を検出し、形状オブジェクトを前記ＣＰＵ数に合わせて分割し、読み込み処理のためにマルチスレッド技術を利用して、３次元形状の読み込みのためのスレッド実行関数を前記ＣＰＵ数分だけ発生させ、該スレッド実行関数をそれぞれのＣＰＵで並列に実行させて、前記分割された形状オブジェクトをそれぞれ読み込ませることによって、３次元形状の読み込み機能を高速に実現することを特徴としたものである。
【００１１】
【発明の実施の形態】
本発明は、前述の目的を達成するために、曲面オブジェクトを形状変換するスレッド関数を作成し、スレッド関数をマルチスレッド技術により複数動作させ、個々のスレッドに異なった曲面オブジェクトを割り当てて並列に動作させるようにしたものである。
【００１２】
図１は、本発明の一実施例を説明するためのフローチャートで、
ＳＴＥＰ１では、
ＣＰＵ数を検出する。ＣＰＵ数はスレッド関数を生成する目安となる。
ＳＴＥＰ２では、
３次元形状のデータから曲面を全て取り出し、メモリに格納する。
ＳＴＥＰ３では、
ＳＴＥＰ２で得られた曲面データをＣＰＵ数で分割し、複数のデータに分ける。
ＳＴＥＰ４では、
ＳＴＥＰ１で得られたＣＰＵ数分だけ曲面オブジェクトを形状変換するスレッド関数を動作させる。
ＳＴＥＰ５では、
ＳＴＥＰ２で得られた曲面データをＣＰＵ数で分割し、それぞれの曲面データ群をＳＴＥＰ３で生成したスレッド関数に割り当てて、データ変換処理を行う。
【００１３】
本出願人は、マルチスレッドプログラム対応の３次元データ交換のためのカーネル上で３次元データを変換する応用プログラムを作成し、データ交換の処理時間が短縮されることを確認し、応用プログラムの有効性を検証した。すなわち、２つ以上のＣＰＵを搭載するパーソナルコンピュータ（ＰＣ）上で、複数のＣＰＵに処理を分散する分散型データ交換プログラムを作成し、従来の逐次処理との速度を比較することで、マルチスレッドを利用した方式が、逐次処理方式と比較して高速化されることを実証した。
【００１４】
（形状処理ツールキットの概要）
最初に、本発明で行う評価のための３次元形状処理ツールキットについて説明する。マルチスレッドを利用して、３次元形状を分散処理するにあたり、ＭＴ−ＳＡＦＥ（湯浅太一，安村通晃，中田登志之：初めての並列プログラミング，共立出版（1998).）な３次元形状処理ツールキットが必要である。そこで、本出願人は、データ交換を主眼に置きＭＴ−ＳＡＦＥなツールキットを開発した。ここでは、３次元形状の分散型データ交換プログラムであるTranslatorを実現するための３次元形状処理ツールキットMiniKernelについて説明する。
【００１５】
一般に、ＣＡＤシステム間では、３次元形状の位相構造や幾何形状の許容誤差などが異なっているため、データの受け側では、位相構造の再構築や形状の近似などを行う。この時、幾何学的に整合する形状をまず構築できないと、位相構造生成のための幾何計算が意図通りなされない。従って、データ交換でまず重要なことは、曲線，曲面といった幾何要素が受け側の許容誤差内で取り込めることである。
【００１６】
境界表現(Braid,I.C. and Lang,C.A.:Computer-aided design of mechanical components with volume building bricks,In Proceedings of PROLAMAT '73,(1973).)を用いた３次元形状は、曲線，曲面といった幾何要素と幾何要素の繋がりを表す位相要素により表現されている。幾何要素には、ＮＵＲＢＳ（Non Uniform Rational B-Spline）表現や平面，２次曲面などの解析表現などが主に用いられる。また、位相要素は、ＣＡＤシステムにより異なるが、立体，シェル，面，ループ，稜線，頂点などで構成される(Mantyla,(¨省略)M.:An Introduction To Solid Modeling,Computer science press,USA(1988)，鳥谷浩志，千代倉弘明：３次元ＣＡＤの基礎と応用，共立出版(1991).）。
【００１７】
面，ループ，稜線，頂点と幾何要素との関係に着目すると、面は曲面を持ち、稜線は曲線を持つ。また、面とループによりトリム曲面を表し、３次元空間における面上線を稜線が持つ曲線で表す。一方、頂点は稜線の端点を表すが、頂点が持つ３次元空間上の座標値と稜線が持つ曲線の端点，頂点の位置に対応する曲面上の点の３点が整合する必要があり、３つの情報を整合させながら維持管理するのは手間がかかる。また、ある演算を行うときに、頂点の位置情報，曲線の端点，面上の点のどれかを利用するかで処理結果が変わる可能性もある。面，ループ，稜線，頂点は、曲面と曲面の境界稜線の関係を表しており、曲面が境界曲線列として直接トリム情報を持てば、位相要素は冗長であるとと考えられる。前述したように、データ交換は幾何形状主導で行われることを考えれば、位相要素は極力排除した方が受け取ったデータの管理方法が単純になる。
【００１８】
以上のような考え方により、MiniKernelでは、モデル，立体，領域，シェルを位相要素として持つ。一方、幾何要素としては、曲面とパラメータ空間曲線，３次元空間曲線の３つを持つ。幾何要素が表現できる曲線，曲面表現形式には次のものがある。
・パラメータ空間曲線（２次元の曲線）
直線（線分），円（円弧），（有理）Ｂ−Ｓｐｌｉｎｅ曲線
・３次元空間曲線
直線（線分），円（円弧），（有理）Ｂ−Ｓｐｌｉｎｅ曲線
・曲面
平面，球面，円柱面，円錐面，トーラス面，（有理）Ｂ−Ｓｐｌｉｎｅ曲線
ここで述べた位相，幾何要素により３次元形状を表現する。また、上記のデータ以外は形式変換する。
【００１９】
MiniKernelは、次のような特徴を持つ。
・ＭＴ−ＳＡＦＥである。
MiniKernelを利用したマルチスレッド対応の応用プログラムを作成することができる。
【００２０】
・ＮＵＲＢＳ表現と解析表現が連携する。
ＮＵＲＢＳ表現と解析表現ではパラメータ化が異なるため、混在して利用するときには、形状変換を行わなければならない。例えば、回転面の境界面線には円弧が含まれるが、回転面を表現しているＮＵＲＢＳ曲面の境界曲線はＮＵＲＢＳ曲線で表現されるため、同一の形状が円弧とＮＵＲＢＳ曲面とで表されることがある。このような場合には、円弧をＮＵＲＢＳ曲線に変換するか、ＮＵＲＢＳ曲線を円弧に変換する必要がある。形状変換にかかるコストを低減するために、ＮＵＲＢＳ表現と主表現，解析的表現を従表現とし、常に両方の表現形式を維持することができる。
【００２１】
・計算結果の寿命を管理することにより、計算コストを低減する。
曲線の端点の座標値や微分ベクトルなど、幾何形状の評価結果を保存し、適宜利用することで形状評価による計算コストを低減する。
【００２２】
・Ｇ1連続およびPeriodicなＮＵＲＢＳ曲線，曲面を扱う。
様々なＣＡＤシステムで生成された幾何形状を取り込むために、ＮＵＲＢＳ表現上の拘束条件を緩めに設定しておく。ただし、Ｃ0連続な形状は折れていることが形状特徴であるという認識により、MiniKernelではＣ0の位置で分割して扱う。
【００２３】
図２は、MiniKernelが持つモデル（Model），立体（Body），領域（Region），シェル（Shell）などのオブジェクト構造を示している。太線で囲まれたものがオブジェクトであり、矢印はオブジェクト間のリンクを表す。また、細線や破線で囲まれるものは、それぞれのオブジェクトが持つメンバーである。更に、破線で囲まれたメンバーはリング上の双方向リストを表し、リストノードには位相または幾何要素が設定される。例えば、モデルはモデルに含まれる立体のリストを持ち、個々の立体はその親のモデルへのリンクを持つ構造である。
【００２４】
図２からも分かるように、MiniKernelでは、モデル，立体，領域，シェルは、境界表現で表される形状モデルの位相要素を意味する。シェルは、そのシェルを構成する曲面（Surf）のリストを持ち、曲面は、曲面の元になる母曲面（Base）と曲面の境界（bound）を表す境界線列からなる。母曲面は、ＮＵＲＢＳ曲面が主表現であり形状に応じて従表現を持つ。境界線列は、母曲面のｕ，ｖ方向のパラメータ区間がそれぞれ［０，１］であると想定したときのパラメータ空間曲線列である。よって、母曲面のパラメータ空間曲線で表された境界線列により、トリム曲面を表現することができる。
図３では、パラメータ空間曲線と３次元空間曲線の関係を示している。これらは、Mantylaが提案する半稜線構造(Mantyla,M.:An Introduction To Solid Modeling,Computer science press,USA(1988)をなしており、隣接する２つの曲面のそれぞれのパラメータ空間曲線が、３次元空間上の共有境界曲線を指し示し、３次元空間曲線が元になるパラメータ空間曲線を指し示す双方向リンクとなっている。
【００２５】
上述のような構造を持つMiniKernel上に３次元形状を構築するときには、次のような手順で行う。
（１）曲面を生成する。
曲面の幾何情報とパラメータ空間曲線を生成し、（トリム）曲面を生成する。
（２）Ｍｏｄｅｌオブジェクトを生成する。
Ｍｏｄｅｌは３次元形状のルートにあたる概念である。立体形状は、すべてＭｏｄｅｌからリンクすることができる。
（３）Ｂｏｄｙを生成する。
（２）で生成したＭｏｄｅｌに属するＢｏｄｙオブジェクトを生成し、適切なリンクをはる。
（４）立体のスケルトンを生成する。
（３）で生成したＢｏｄｙに属するＲｅｇｉｏｎ，Ｓｅｌｌオブジェクトをそれぞれ一つずつ生成し、適切なリンクをはる。これによって、空のＳｈｅｌｌを含む立体が一つずつ生成される。なお、Ｒｅｇｉｏｎは中空シェルを表現するためのオブジェクトである。
（５）（１）で生成した曲面を（４）で生成したＳｈｅｌｌの持つ曲面リストに追加する。これにより、Ｓｈｅｌｌは１枚の曲面を持つサーフェスシェルになる。
【００２６】
複数の曲面を生成するときには、前記（４）から（５）を繰り返すことにより、サーフェスモデルを表す３次元形状をMiniKernel上に構築できる。ソリッドモデルを生成する場合には、個々のＳｈｅｌｌを接合すればよい。以上に述べた方法で、３次元形状データ交換のための形状構築を行う。以下にその詳細について説明する。
【００２７】
本出願人は、以上に説明したMiniKernelを利用し、商用の３次元形状ツールキットＤＥＳＩＧＮＢＡＳＥ（鳥谷浩志，千代倉弘明：３次元ＣＡＤの基礎と応用，共立出版(1991).)から形状データを取り込むデータ交換ツール（Translatorと呼ぶ）を開発した。以下に、Translatorの構成とアルゴリズムについて説明する。また、並列に実行するときの並列化効率についても説明する。
【００２８】
図４は、本出願人が開発したTranslatorの構成を示している。Translatorは、ＤＥＳＩＧＮＢＡＳＥの形状データをMiniKernelの形状データに変換する機能を持つ。図４の黒い矢印は、関数の呼び出し関係を示している。このTranslatorは、ＤＥＳＩＧＮＢＡＳＥの一つのコマンドとして作成したもので、ＤＥＳＩＧＮＢＡＳＥデータをMiniKernelに取り込む場合には、ＤＥＳＩＧＮＢＡＳＥのコマンドインターフェースを利用してコマンド実行関数を呼び出し、コマンド実行関数がTranslator本体を呼び出す方式を取った。
【００２９】
Translator本体では、大きく分けて以下に示す３つの機能を実装した。これら３種類の処理を部品として利用し、後述の手法により並列化したアルゴリズムを提案する。
（１）形状の取得：ＤＥＳＩＧＮＢＡＳＥから３次元形状を取得する。
ＤＥＳＩＧＮＢＡＳＥが持っている、モデル，立体，ループをたどり、（トリム）曲面情報を得る。
（２）曲面の形式変換：ＤＥＳＩＧＮＢＡＳＥの曲面構造をMiniKernelのものに変換する。
（３）形状の生成：MiniKernelの曲面をカーネルに登録する。
（２）で変換したMiniKernelの曲面を、MiniKernelのシェルとして生成する。ここで生成されたシェルは、１つの曲面のみを持つ。
【００３０】
並列処理は、専用の並列計算機や並列コンパイラなどを利用して実装するのが一般的に行われており、大規模な科学技術計算や、専用のハードウエア上での並列化手法（中田秀基，村上聡，荒木拓也，小池汎平，田中秀彦：並列計算機ＰＩＥ６４ににおけるCommitted-choice型言語Flengの負荷分散手法，情報処理学会論文誌，第３８巻，第２号，pp.332-340(1997))などが提案されている。多くのＣＡＤ／ＣＡＭシステムは、逐次処理を前提にしているので、逐次的なプログラムを複数のタスクに分割し、タスク間の並列性を利用して並列処理する考え方を取り入れることが容易である。また、３次元形状モデルは、立体，シェル，面，稜線，頂点などのオブジェクトにより表現されているので、オブジェクトを分散させて同一の処理を行う手法も考えられる。ここでは、タスク間の並列性を利用する手法を並列タスク型並列処理，オブジェクトを分割する手法をオブジェクト分割並列処理と呼ぶことにする。
【００３１】
前述のTranslatorの内部機能（１）〜（３）を並列タスク型，オブジェクト分割型並列処理にあてはめ、次のように実装し並列化評価のためのTranslatorを開発した。なお、並列化評価の基準となる逐次処理についても合わせて説明する。
【００３２】
（逐次処理）
前記（１）から（３）までを逐次的に処理するプログラムであり、マルチスレッドプログラムではない。以下に、プログラム例を示す（エラー処理などは省略する）。
【００３３】
0003847020.tif 000002
【００３４】
（並列タスク型並列処理）
（１）から（３）までの３つの処理を別々のスレッド実行関数としパイプライン処理するようにした（プログラム例参照）。すなわち、スレッド１は、３次元形状モデルの曲面と境界曲線をＤＥＳＩＧＮＢＡＳＥ形式でｄｂｓｆに出力する。スレッド２は、スレッド１が出力したＤＥＳＩＧＮＢＡＳＥ形式の曲面と境界曲線をMiniKernelで扱える形式に変換し、ｍｋｓｆに出力する。スレッド３は、スレッド２で生成した曲面オブジェクトを利用して、位相を含めた３次元形状（シェル）を生成する。
【００３５】
それぞれのスレッドは、自分が処理するべきデータが渡されるまでは、待ち状態にあり、データが渡されたときにだけ処理する。以下に、プログラム例を示す。エラー処理などは省略する。また、関数名はわかりやすいものに変更されている。
【００３６】
0003847020.tif 000003
【００３７】
0003847020.tif 000004
【００３８】
0003847020.tif 000005
【００３９】
0003847020.tif 000006
【００４０】
（オブジェクト分割型並列処理）
データ変換の対象となる曲面を複数のスレッド実行関数で処理する。それぞれのスレッドは、（１）から（３）までの処理を行う。すなわち、それぞれのスレッドは、同一の処理を行うが、扱う形状データが異なっている。オブジェクトを分割するときの目安はＣＰＵ数とする。以下に、プログラム例を示す。エラー処理などは省略する。また、関数名は、わかりやすいものに変更されている。
【００４１】
0003847020.tif 000007
【００４２】
0003847020.tif 000008
【００４３】
次に、以上に述べたTranslatorの実装法について、どの程度並列化による実行時間の短縮が図れるかどうかを説明する。
図５は、逐次処理，並列タスク型並列処理，オブジェクト分割型並列処理の３種類についてTranslatorの動作と時間との関係を示している。逐次処理では、データ交換するすべての曲面オブジェクトに対して、形状取得，形式変換，形状生成が順番に実行されるので、それぞれのフェーズでかかった時間が総実行時間となる。並列タスク型並列処理では、まず、処理の最初で形状取得のためのスレッド（スレッド１），形式変換のためのスレッド（スレッド２），形状生成のためのスレッド（スレッド３）を起動される。スレッド１からスレッド３までは、それぞれの入出力が同期しており、データが到着するかどうかをそれぞれのスレッドが監視している。それぞれのスレッドで扱えるデータが到着すると同時に処理を行う。いわゆる、パイプライン方式で動作する。それぞれのスレッドは、処理すべきデータがなくなったところで自滅する。従って、スレッド１での処理が開始されたときから、スレッド３が自滅するまでが、総実行時間となる。オブジェクト分割型並列処理では、ＣＰＵ数に合わせて、オブジェクトを分割し、スレッド関数をＣＰＵ数だけ立ち上げ、個々のスレッドが割り当てられたオブジェクトを処理する。データ交換の一連の処理を複数のスレッドで並列に実行されるため、総実行時間は、スレッドの立ち上げが開始されたときからスレッドがすべて終了したときまでの時間となる。
【００４４】
曲面変換の総実行時間Ｔは、次式で表現することができる。
Ｔ＝（ｔ×ｎ）×（１−Ｃ）＋ｏ                          …（１）
ただし、ｔは１枚の曲面変換に費やす時間、ｎは処理する曲面数、Ｃ（Ｃ≦１とする）は並列性による寄与率、ｏは同期などの並列オーバーヘッドとする。例えば、逐次処理の場合には、Ｃ＝０、ｏ＝０なので、総実行時間Ｔsは、
Ｔs＝（ｔ×ｎ）                                          …（２）
である。
【００４５】
並列処理方式に対する逐次処理との速度比は、図６のようになると予想できる。図６は、横軸はデータ変換する曲面の数を、縦軸は逐次処理との速度比を示した。比は、１より大きければ、並列処理が逐次処理よりも高速であることを示す。すなわち、逐次処理の総実行時間をＴs、並列処理の総実行時間をＴpとしたときに、
【００４６】
【数１】
0003847020.tif 000009
【００４７】
【数２】
0003847020.tif 000010
【００４８】
で表すことができるので、これを式（３）に代入すると、
ｏ＜Ｔs×Ｃ  並列処理が高速
ｏ＝Ｔs×Ｃ  速度は同一
ｏ＞Ｔs×Ｃ  逐次処理が高速                              …（５）
が得られる。
【００４９】
式（５）より、一定の曲面数をデータ変換するときには、並列化により短縮された時間Ｔs×Ｃが並列オーバーヘッドよりも多いときには、並列処理が高速になることが分かる。逆に、並列化により短縮された時間Ｔs×Ｃが並列オーバーヘッドよりも少ないときには、逐次処理が高速になる。また、処理するべき曲面数が増加したときは、処理時間であるＴsは増大するためＴs×Ｃも増大し、並列オーバーヘッドｏよりも大きくなったところで、並列処理が高速になることが予想できる。つまり、図６の横軸の曲面数ＡからＥまでが単調増加すると仮定すると、ある数以上の曲面を処理すると、並列オーバーヘッドよりも並列化により短縮された時間Ｔs×Ｃが多くなり、並列処理が高速になることが予想できる。
【００５０】
次に、以上に説明したTranslatorを利用し、３次元形状のデータ交換に要する時間を計測，評価した結果について説明する。実行時間を計測する計算機は、ＣＰＵがＰｅｎｔｉｕｍIIプロセッサ（２６６ＭＨｚ）を２個搭載し、メモリ１２８ＭＢのパーソナルコンピュータ（ＰＣ）である。ＯＳは、Ｗｉｎｄｏｗｓ  ＮＴ４.０である。また、ＤＥＳＩＧＮＢＡＳＥはＶ７.０、コンパイラはＶＣ＋＋５.０）を利用した。データ交換に利用したデータは、平面，トーラス面，スイープ面の３種類である（図７，図８，図９参照）。それぞれのデータをＤＥＳＩＧＮＢＡＳＥの形状生成コマンドで生成し、その立体形状をMiniKernelに読み込むＤＥＳＩＧＮＢＡＳＥコマンドを実行し、Translator本体の実行時間を計測する。面数と時間の関係を得るために、図７から図９に示した形状をコピーして面数を増やし、それぞれの面数での読み込み時間を計測した。
【００５１】
表１から表３は、平面，トーラス面，スイープ面を面数が２５６枚から、１６３８４枚までを逐次処理，並列タスク型並列処理，オブジェクト分割並列処理の３種類の方法でMiniKernelへ読み込んだときの実行時間を計測したものである。なお、単位は秒とする。また。図１０は、逐次処理とオブジェクト分割型並列処理，並列タスク型並列処理との速度比を示している。実線が逐次処理とオブジェクト分割型並列処理の速度比を、破線が逐次処理と並列タスク型並列処理の速度比を示している。
【００５２】
図１０では、横軸が面数を表し、縦軸が速度比を表す。速度比が１.０以下では、逐次処理が高速であり、１.０より大きければ並列処理が高速であることを示す。図１０から分かるように、並列タスク型並列処理では、逐次処理との速度を比較しても速度向上は達成されていない。並列タスク型並列処理では、オブジェクト（曲面形状）がスレッドを渡り歩くパイプライン処理になり、各スレッドは、オブジェクトの到着を監視するために頻繁に同期を取る必要がある。すなわち、同期にかかる時間やオブジェクトが到着するまでの待ち時間が並列オーバーヘッドになる。また、処理が並列に行われている時間が長くないときは、並列度が高くないため、速度向上は望めない。すなわち、オーバーヘッドを含めた負荷の均等かがうまくいかないと効率が上がらない、典型的な例になった。
【００５３】
一方、オブジェクト分割型並列処理では、平面，トーラス面，スイープ面のどの場合でも、曲面数が２０４８枚以上で逐次処理よりも高速になることが分かる。このことから、ある一定以上の曲面処理時間が並列オーバーヘッドよりも多くなり、並列処理が高速化されたことが実証できた。以上のことから、逐次処理アルゴリズムを利用したオブジェクト分割型並列処理では、変換形状の元になるモデラが再入可能であれば、並列化効率は高まることが予測できる。また、ＣＰＵ数が２の場合に２つのスレッドに処理を分担させることによって、約２倍の高速化が達成された。ＣＰＵ数がｎの場合には、ｎ個のスレッドに処理を分担すればよいことが予想できる。このように、オブジェクト分割型並列処理はデータ交換に有効であると考えられる。
【００５４】
【表１】
0003847020.tif 000011
【００５５】
【表２】
0003847020.tif 000012
【００５６】
【表３】
0003847020.tif 000013
【００５７】
【発明の効果】
上述のように、本出願人は、再入可能な３次元カーネルMiniKernelを作成し、マルチスレッドプログラミングによる速度評価を行った。MiniKernelを利用したアプリケーションとして３次元形状のデータ変換プログラムを作成し、逐次処理，並列タスク型並列処理，オブジェクト分割並列処理の３種類の方法をインプリメントし、平面，トーラス面，スイープ面の面数を変更して読み込みに要する時間を計測した。アルゴリズムから並列性を見出す並列タスク型並列処理では、高速化されなかった。オブジェクトをＣＰＵ数分だけ分割するオブジェクト分割型並列処理では、並列化により速度が向上された。実験では２ＣＰＵのＰＣを利用し、オブジェクトを２つに分割し処理することで約２倍の速度向上が図れた。３次元形状処理は、対話的な処理が要求されるにもかかわらず、計算量も多い。しかも、逐次処理的なアルゴリズムが主流であり、立体，面，線などのオブジェクトが多数存在する。従って、逐次処理をスレッド関数として、マルチスレッドで並列化することは容易に適用することができる。
【００５８】
以上のように、マルチスレッドプログラミングを利用したオブジェクト分割型並列処理は、３次元形状処理においても有効であることが実証された。
【図面の簡単な説明】
【図１】  本発明の動作説明をするためのフローチャートである。
【図２】  MiniKernelが持つモデル（Model），立体（Body），領域（Region），シェル（Shell）などのオブジェクト構造を示す図である。
【図３】  パラメータ空間曲線と３次元空間曲線の関係を示す図である。
【図４】  本出願人が開発したTranslatorの構成を示す図である。
【図５】  逐次処理，並列タスク型並列処理，オブジェクト分割型並列処理の３種類についてTranslatorの動作と時間との関係を示す図である。
【図６】  横軸にデータ変換する曲面の数を、縦軸に逐次処理との速度比を示す図である。
【図７】  評価用の３次元形状（平面）を示す図である。
【図８】  評価用の３次元形状（トーラス面）を示す図である。
【図９】  評価用の３次元形状（スイープ面）を示す図である。
【図１０】  逐次処理とオブジェクト分割型並列処理，並列タスク型処理との速度比を示す図である。
【図１】
0003847020.tif 000014
【図２】
0003847020.tif 000015
【図３】
0003847020.tif 000016
【図４】
0003847020.tif 000017
【図５】
0003847020.tif 000018
【図６】
0003847020.tif 000019
【図７】
0003847020.tif 000020
【図８】
0003847020.tif 000021
【図９】
0003847020.tif 000022
【図１０】
0003847020.tif 000023