(57)【要約】システム１００および複雑な計算を要する問題を解決する方法において、複数の多目的ワークステーション（Ａ−Ｉ）を備える仮想スーパコンピュータ１０２が用いられる。このスーパコンピュータ１０２と複雑な計算を要する問題を解決するためのアプリケーションソフトウェアは、多目的ワークステーション（Ａ−Ｉ）がプライマリユーザにより他のタスクを実行するために使用される可能性があることを鑑み、それに及ぼす影響を最小限にするために用いられる。複雑な計算を要する問題は、仮想スーパコンピュータ１０２を用いることで、多目的ワークステーション(Ａ−Ｉ)で入手可能なコンピュータリソースを一切余分に使うことなく、解決される。【選択図】図１Ａ
2004530182.tif 000002
【特許請求の範囲】
【請求項１】
複数の多目的コンピュータワークステーションを用いて複雑な計算を要する問題を解決するための方法であって、
（ａ）主コンピュータと、前記複数の多目的コンピュータワークステーションから選択された少なくとも１つの従コンピュータを有する仮想スーパーコンピュータを構築し、
（ｂ）前記主コンピュータで主アプリケーションをスタートさせ、
（ｃ）前記従コンピュータで従アプリケーションをスタートさせ、
（ｄ）前記複雑な計算を要する問題を複数のタスク断片に分割し、
（ｅ）前記複数のタスク断片から選択された少なくとも１つのタスク断片を、前記少なくとも１つの従コンピュータに割り当て、
（ｆ）前記従コンピュータに前記タスク断片を完了させ、
（ｇ）前記従コンピュータが出した結果を前記主コンピュータに受領させ、
（ｈ）前記複雑な計算を要する問題が解決するまで、ステップ（ｅ）−（ｇ）を繰り返す、各ステップを含む方法。
【請求項２】
前記主コンピュータおよび前記少なくとも一つ以上の従コンピュータは、同一のコンピュータである、請求項１に記載の方法。
【請求項３】
前記仮想スーパコンピュータの負荷を調整するステップをさらに含んでいる、請求項１に記載の方法。
【請求項４】
（ａ）前記仮想スーパコンピュータの規模に影響を与える事象を探知し、
（ｂ）前記事象に応じて前記仮想スーパコンピュータ上の負荷を調整する、
各ステップをさらに含む請求項１に記載の方法。
【請求項５】
前記事象は、前記複数のコンピュータワークステーションから選ばれた第２の従コンピュータが利用できることを含む、請求項４に記載の方法。
【請求項６】
前記仮想スーパコンピュータに前記第２の従コンピュータを追加するステップをさらに含む方法であって、負荷を分配するステップは、
（ａ）前記少なくとも一つ以上の従コンピュータに割り当てられた少なくとも一つのタスク断片を回収し、
（ｂ）前記少なくとも一つ以上の従コンピュータおよび前記第２の従コンピュータの処理能力を判断し、
（ｃ）判断された前期処理能力に基づいて、前記少なくとも一つ以上の従コンピュータおよび前記第２の従コンピュータにタスク断片を分配する、各ステップを含んでいる請求項４に記載の方法。
【請求項７】
前記事象は、前記少なくとも一つ以上の従コンピュータにおける前記従アプリケーションの不具合を含んでいる、請求項４に記載の方法。
【請求項８】
（ａ）前記少なくとも一つ以上の従コンピュータ上で前記従アプリケーションを再始動させ、
（ｂ）前記少なくとも一つ以上の従コンピュータ上で再始動した前記従アプリケーションをテストする、各ステップをさらに含んでいる請求項７に記載の方法。
【請求項９】
前記事象は、前記主コンピュータと前記少なくとも一つ以上の従コンピュータ間における通信の切断を含んでいる、請求項４に記載の方法。
【請求項１０】
（ａ）前記仮想スーパコンピュータから前記少なくとも一つ以上の従コンピュータを削除し、
（ｂ）前記複数のタスク断片から選ばれたタスク断片のうちどれが完了していないかを判断し、
（ｃ）前記仮想スーパコンピュータにおける残っている従コンピュータの処理能力を判断し、次のステップをさらに含んでいる、
（ｄ）前記判断された処理能力に応じて前記残っている従コンピュータに少なくとも一つ以上のタスク断片を分配する、各ステップをさらに含んでいる請求項９に記載の方法。
【請求項１１】
（ａ）前記少なくとも一つ以上の従コンピュータの処理能力を判断し、
（ｂ）前記少なくとも一つ以上の従コンピュータに前記複数のタスク断片を分配する、各ステップをさらに含んでいる請求項１に記載の方法。
【請求項１２】
前記少なくとも一つ以上の従コンピュータから、複数の最終実行統計値を主コンピュータに集めるステップをさらに含む、請求項１に記載の方法。
【請求項１３】
前記仮想スーパコンピュータを解体するステップをさらに含む、請求項１に記載の方法。
【請求項１４】
前記仮想スーパコンピュータを分解するステップは、
（ａ）前記少なくとも一つ以上の従コンピュータ上の前記従アプリケーションを終了し、
（ｂ）前記主コンピュータ上の前記主アプリケーションを終了し、
（ｃ）前記少なくとも一つ以上の従コンピュータおよび前記主コンピュータ上の、前記仮想スーパコンピュータデーモンアプリケーションを終了する、各ステップを含んでいる請求項１３に記載の方法。
【請求項１５】
前記複雑な計算を要する問題への解を提供するステップをさらに含む、請求項１に記載の方法。
【請求項１６】
前記仮想スーパコンピュータを構築するステップは、
（ａ）前記主コンピュータ上で第１の仮想スーパコンピュータデーモンを始動させ、
（ｂ）前記複数の多目的ワークステーションから選ばれた潜在従コンピュータを認識し、
（ｃ）前記主コンピュータから前記潜在従コンピュータへ、第２の仮想スーパコンピュータデーモンをダウンロードし、
（ｄ）前記潜在従コンピュータ上で、前記第２の仮想スーパコンピュータデーモンを始動させ、
（ｅ）第１の仮想スーパコンピュータデーモンと第２の仮想スーパコンピュータデーモン間の通信活動を構築する、各ステップを含んでいる請求項１に記載の方法。
【請求項１７】
（ａ）前記従コンピュータから前記潜在従コンピュータへ、従アプリケーションをダウンロードし、
（ｂ）前記潜在従コンピュータ上で前記従アプリケーションを始動させ、
（ｃ）前記潜在従コンピュータ上で前記従アプリケーションをテストし、
（ｄ）前記従アプリケーションテストが成功すれば、前記潜在従コンピュータを、前記仮想スーパコンピュータにおける前記少なくとも一つ以上の従コンピュータとする、各ステップをさらに含んでいる請求項１５に記載の方法。
【請求項１８】
前記少なくとも一つ以上の従コンピュータの実行処理能力を判断するステップをさらに含む、請求項１６に記載の方法。
【請求項１９】
前記複数の多目的ワークステーションにおいて、利用できる潜在従コンピュータが存在しなくなるまで、ステップ１６（ｂ）からステップ１６（ｅ）を繰り返すステップをさらに含む、請求項１６に記載の方法。
【請求項２０】
（ａ）前記主コンピュータから前記潜在従コンピュータへ、従アプリケーションをダウンロードし、
（ｂ）前記潜在従コンピュータ上で、前記従アプリケーションを始動させ、
（ｃ）前記潜在従コンピュータ上で、前記従アプリケーションをテストし、
（ｄ）前記従アプリケーションテストが成功すれば、前記潜在従コンピュータを、前記仮想スーパコンピュータにおける前記少なくとも一つ以上の従コンピュータとし、
（ｅ）前記少なくとも一つ以上の従コンピュータの実行能力を見積もり、
（ｆ）前記複数の多目的ワークステーションにおいて、利用できる潜在従コンピュータが存在しなくなるまで、ステップ（ａ）から（ｅ）を繰り返す、各ステップをさらに含む請求項１９に記載の方法。
【請求項２１】
前記複雑な計算を要する問題は、金融ポートフォリオの最適化をさらに含む、請求項１に記載の方法。
【請求項２２】
前記複雑な計算を要する問題は、サプライチェーン物流をさらに含む、請求項１に記載の方法。
【請求項２３】
品目ごとまたは店舗ごとの最適在庫レベルを、対応する日ごとの積み替え予定に合わせて、決定することをさらに含む、請求項２２に記載の方法。
【請求項２４】
前記複雑な計算を要する問題は、最適化への分岐限界アプローチと連動して用いられる、請求項１に記載の方法。
【請求項２５】
前記複雑な計算を要する問題は、合計実行時間を減少させるために、大規模シミュレーションに関連して用いられる、請求項１に記載の方法。
【請求項２６】
前記複雑な計算を要する問題は、ネットワーク最適化問題を含んでいる、請求項１に記載の方法。
【請求項２７】
前記ネットワーク最適化問題は、搬送手段の経路決定および日程調整システムを含んでいる、請求項２６に記載の方法。
【請求項２８】
前記ネットワーク最適化問題は、搬送手段の経路決定および日程調整システムを含んでいる、請求項２６に記載の方法。
【請求項２９】
前記複雑な計算を要する問題は、データベース構築を含んでいる、請求項１に記載の方法。
【請求項３０】
前記複雑な計算を要する問題は、画像分析プログラムを含んでいる、請求項１に記載の方法。
【請求項３１】
主コンピュータと、複数の多目的ワークステーションから選ばれた少なくとも一つの従コンピュータと、を有する仮想スーパコンピュータを構築する方法であって、
（ａ）前記主コンピュータ上で第１の仮想スーパコンピュータデーモンを始動させ、
（ｂ）前記複数の多目的ワークステーションから選ばれた潜在従コンピュータを認識し、
（ｃ）前記潜在従コンピュータ上で、第２の仮想スーパコンピュータデーモンを始動させ、
（ｄ）前記第１の仮想スーパコンピュータデーモンと前記第２の仮想スーパコンピュータデーモン間の通信活動を構築し、
（ｅ）（ｂ）前記潜在従コンピュータ上で、前記従アプリケーションを始動させ、
（ｆ）前記潜在従コンピュータ上で、前記従アプリケーションをテストし、
（ｇ）前記従アプリケーションテストが成功すれば、前記潜在従コンピュータを、前記仮想スーパコンピュータにおける前記少なくとも一つ以上の従コンピュータとする、各ステップを含む方法。
【請求項３２】
前記少なくとも一つ以上の従コンピュータの実行能力を見積もるステップをさらに含む、請求項３１に記載の方法。
【請求項３３】
前記複数の多目的ワークステーションにおいて、利用できる潜在従コンピュータが存在しなくなるまで、ステップ３１（ｂ）からステップ３１（ｅ）を繰り返すステップをさらに含む、請求項３１に記載の方法。
【請求項３４】
前記主コンピュータから前記潜在従コンピュータに、従仮想スーパコンピュータソフトウェアをダウンロードするステップをさらに含む、請求項３１に記載の方法。
【請求項３５】
前記主コンピュータから前記潜在従コンピュータに、従アプリケーションをダウンロードするステップをさらに含む、請求項３１に記載の方法。
【請求項３６】
仮想スーパコンピュータが複雑な計算を要する問題を解いている間に、
前記仮想スーパコンピュータを動的に再構築する方法であって、
（ａ）前記仮想スーパコンピュータの規模に影響をおよぼす事象を探知し、
（ｂ）前記事象が従コンピュータの不具合であれば、障害の発生した従コンピュータから、前記仮想スーパコンピュータにおける少なくとも一つ以上の従コンピュータに、タスク断片を再分配し、
（ｃ）前記事象が新規に利用可能となった従コンピュータの出現であれば、前記仮想スーパコンピュータにおける少なくとも一つ以上のコンピュータからタスク断片を回収して、前記回収されたタスク断片を新規の従コンピュータに割り当てる、各ステップを含む方法。
【請求項３７】
（ａ）前記事象が従コンピュータの不具合であれば、障害の発生した従コンピュータ上での従アプリケーションを終了させ、
（ｂ）前記事象が従コンピュータの不具合であれば、障害の発生した従コンピュータ上での従アプリケーションを再始動させる、各ステップをさらに含む方法であり、ステップ３６（ｂ）を実行する前にステップ３７（ａ）およびステップ３７（ｂ）を実行する請求項３６に記載の方法。
【請求項３８】
（ａ）前記事象が従コンピュータの不具合であれば、前記再始動した従アプリケーションを初期化し、
（ｂ）前記事象が従コンピュータの不具合であれば、前記従アプリケーションの再始動をテストし、
（ｃ）前記テストステップに失敗した場合、前記従アプリケーションの再始動を終了させる、各ステップをさらに含む方法であり、ステップ３６（ｂ）を実行する前に、ステップ３７（ａ）から３７（ｃ）を実行する請求項３７に記載の方法。
【請求項３９】
前記テストステップに失敗した場合、前記仮想スーパコンピュータから前記障害の発生した従コンピュータを削除するステップをさらに含む、請求項３８に記載の方法。
【請求項４０】
前記複数の多目的ワークステーションから選ばれたワークステーションが新規に利用可能となった場合、前記仮想スーパコンピュータに追加の従コンピュータを加えるステップは、
（ａ）前記利用可能なワークステーション上において仮想スーパコンピュータデーモンを始動させ、
（ｂ）前記新規利用可能ワークステーション上において、従アプリケーションを始動させる、各ステップを含む請求項３６に記載の方法。
【請求項４１】
（ａ）前記新規利用可能ワークステーション上の前記従アプリケーションを初期化し、
（ｂ）前記新規利用可能ワークステーション上の前記従アプリケーションをテストする、各ステップをさらに含む請求項４０に記載の方法。
【請求項４２】
複数の多目的ワークステーションを用いて複雑な計算を要する問題を解く方法であって、
（ａ）主コンピュータと、少なくとも一つ以上の従コンピュータを備えた仮想スーパコンピュータを構築し、前記従コンピュータは、前記複数の多目的コンピュータワークステーションから選択されており、
（ｂ）前記少なくとも一つ以上の従コンピュータに、複数のデータ・セットを分配し、
（ｃ）前記仮想スーパコンピュータ上の初期負荷調整を行い、
（ｄ）前記少なくとも一つ以上の従コンピュータに初期計算タスクを割り当て、
（ｅ）前記少なくとも一つ以上の従コンピュータでの計算を指示し、
（ｆ）前記少なくとも一つ以上の従コンピュータからの計算結果の第１のセットを受領し、
（ｇ）前記複数の多目的ワークステーションから選ばれたワークステーションが、新規に利用可能となれば、前記仮想スーパコンピュータに追加の従コンピュータを加え、
（ｈ）前記従コンピュータが利用不能になった場合に、その従コンピュータを前記仮想スーパコンピュータから削除し、
（ｉ）前記複雑な計算を要する問題が解決されるまで、前記第１の計算結果セットおよび追加のデータセットを、前記少なくとも一つ以上の従コンピュータに分配する、各ステップを含んでいる方法。
【請求項４３】
（ａ）各従コンピュータからの複数の最終実行統計値を集め、
（ｂ）前記仮想スーパコンピュータを分解する、各ステップをさらに含んでいる請求項４２に記載の方法。
【請求項４４】
複雑な計算を要する問題を解く仮想スーパコンピュータに、新規のメンバコンピュータを組み入れる方法であって、
（ａ）前記仮想コンピュータにおいて、前記新規メンバコンピュータから主コンピュータへ、第１のメッセージを送らせ、前記第１のメッセージは、前記新規メンバコンピュータが利用可能な状態にあることを含み、
（ｂ）前記新規メンバコンピュータ上で、仮想スーパコンピュータデーモンを始動させ、
（ｃ）前記新規メンバコンピュータ上で、従アプリケーションを始動させ、
（ｄ）前記新規メンバコンピュータ上で、前記従アプリケーションのセルフテストを実行させ、
（ｅ）前記新規メンバコンピュータから前記主アプリケーションへ、第２のメッセージを送らせ、前記第２のメッセージは，実行統計値報告を含んでおり、
（ｆ）前記新規メンバコンピュータ上でデータ・セットを受領させ、
（ｇ）前記新規メンバコンピュータ上でタスクを受領させ、前記タスクは、複雑な計算を要する問題の一部を解くための計算指示を含んでおり、
（ｈ）前記新規メンバコンピュータ上の前記タスクを完了する、各ステップを含む方法。
【請求項４５】
（ａ）前記新規メンバコンピュータから主コンピュータへ、第３のメッセージを送らせ、前記第３のメッセージは、前記新規メンバコンピュータが前記セルフテストに失敗した場合、障害報告を含んでおり、
（ｂ）前記セルフテストに失敗した場合、前記新規メンバコンピュータ上の前記仮想スーパコンピュータデーモンを終了させ、
（ｃ）前記セルフテストに失敗した場合、前記新規メンバコンピュータ上の前記従アプリケーションを終了させる、各ステップをさらに含んだ請求項４４に記載の方法。
【請求項４６】
（ａ）前記新規従コンピュータの複数の最終実行統計値を集め、
（ｂ）前記新規メンバコンピュータから主コンピュータへ、第３のメッセージを送らせ、前記第３のメッセージは、前記複数の最終実行統計値を含有する、各ステップをさらに含んでいる請求項４４に記載の方法。
【請求項４７】
仮想スーパコンピュータが複雑な計算を要する問題を解いている間に、前記仮想スーパコンピュータを動的に再構築する方法であって、
（ａ）前記新規従コンピュータが利用可能であることを探知し、
（ｂ）前記新規従コンピュータに仮想スーパコンピュータデーモンを提供し、
（ｃ）前記新規従コンピュータに前記仮想スーパコンピュータデーモンを始動させるように指示し、
（ｄ）前記新規従コンピュータに従アプリケーションを提供し、
（ｅ）前記新規従コンピュータに前記従アプリケーションを始動させるように指示し、
（ｆ）前記仮想スーパコンピュータの計算負荷を再分配し、
（ｇ）前記仮想スーパコンピュータの計算タスクを完了する、各ステップを含んだ方法。
【請求項４８】
（ａ）前記新規従コンピュータに初期データ・セットを提供し、
（ｂ）前記初期データ・セットを用いてセルフテストの実行を指示する、各ステップをさらに含んだ請求項４７に記載の方法。
【請求項４９】
（ａ）前記新規従コンピュータからセルフテストの結果を受領し、
（ｂ）前記セルフテストに失敗した場合、前記従アプリケーションを終了するよう指示し、
（ｃ）前記セルフテストに失敗した場合、前記仮想コンピュータから前記新規従コンピュータを除去する、各ステップをさらに含んだ請求項４８に記載の方法。
【請求項５０】
前記仮想スーパコンピュータの計算負荷を再分配するステップは、
（ａ）前記仮想スーパコンピュータにおける各メンバコンピュータから複数のタスク断片を回収し、
（ｂ）前記仮想スーパコンピュータにおける各メンバコンピュータの計算能力を判断し、
（ｃ）前記仮想スーパコンピュータにおける各メンバコンピュータに複数のタスク断片のサブ・セットを割り当てる、各ステップをさらに含む請求項４７に記載の方法。
【請求項５１】
仮想スーパコンピュータが複雑な計算を要する問題を解いている間に、前記仮想スーパコンピュータにおける各メンバコンピュータ上の従アプリケーションの不具合を動的に処理する方法であって、
（ａ）前記従アプリケーションの不具合を探知し、
（ｂ）前記メンバコンピュータに前記従アプリケーションを再始動するよう指示し、
（ｃ）前記メンバコンピュータに初期データ・セットを提供し、
（ｄ）前記メンバコンピュータに、前記初期データ・セットを用いてセルフ・テストを行うよう指示し、
（ｅ）前記メンバコンピュータに、以前に割り当てられたタスク断片についての計算タスクの実行を続けるよう指示する、各ステップを含んでいる方法。
【請求項５２】
（ａ）前記メンバコンピュータからセルフテストの結果を受領し、
（ｂ）前記セルフテストに失敗した場合、前記メンバコンピュータに前記従アプリケーションを終了するよう指示し、
（ｃ）前記仮想スーパコンピュータ上の計算負荷を再分配し、
（ｄ）前記セルフテストに失敗した場合、前記仮想スーパコンピュータから前記メンバコンピュータを除去する、各ステップをさらに含んでいる請求項５１に記載の方法。
【請求項５３】
前記仮想スーパコンピュータ上の計算負荷を分配するステップは、
（ａ）複数のタスク断片のうち、前記メンバコンピュータに以前に割り当てられていたのはどれかを判断し、
（ｂ）前記仮想スーパコンピュータにおける各メンバコンピュータの計算能力を判断し、
（ｃ）前記仮想スーパコンピュータにおける各メンバコンピュータに前記複数のタスク断片の小集合を割り当てる、各ステップを含んでいる請求項５２に記載の方法。
【請求項５４】
仮想スーパコンピュータが複雑な計算を要する問題を解いている間に、前記仮想スーパコンピュータにおけるメンバコンピュータ上の仮想スーパコンピュータデーモンの終了を動的に処理する方法であって、
（ａ）前記仮想スーパコンピュータデーモンの終了を探知し、
（ｂ）前記メンバコンピュータに前記仮想スーパコンピュータデーモンの再始動を指示し、
（ｃ）前記メンバコンピュータに前記従アプリケーションの再始動を指示し、
（ｄ）前記メンバコンピュータに初期データ・セット提供し、
（ｅ）前記メンバコンピュータに前記初期データ・セットを用いてセルフテストを実行するよう指示し、
（ｆ）前記メンバコンピュータに以前に割り当てられたタスク断片の計算タスクの実行を続けるよう指示する、各ステップを含む方法。
【請求項５５】
（ａ）前記メンバコンピュータからセルフテストの結果を受領し、
（ｂ）前記セルフテストに失敗した場合、前記メンバコンピュータに前記従アプリケーションを終了するよう指示し、
（ｃ）前記仮想スーパコンピュータ上の計算負荷を再分配し、
（ｄ）前記セルフテストに失敗した場合、前記仮想スーパコンピュータから前記メンバコンピュータを除去する、各ステップをさらに含んでいる請求項５４に記載の方法。
【請求項５６】
前記仮想スーパコンピュータ上の計算負荷を再分配する方法は、
（ａ）複数のタスク断片のうち、前記メンバコンピュータに以前に割り当てられていたのはどれかを判断し、
（ｂ）前記仮想スーパコンピュータにおける各メンバコンピュータの計算能力を判断し、
（ｃ）前記仮想スーパコンピュータにおける各メンバコンピュータに前記複数のタスク断片の小集合を割り当てる、各ステップを含んでいる請求項５４に記載の方法。
【請求項５７】
仮想スーパコンピュータを用いた、前記複雑な計算を要する問題を解決するシステムであって、
（ａ）少なくとも１つ以上の従コンピュータと連携している主コンピュータを有する仮想スーパコンピュータと、
（ｂ）前記主コンピュータで稼動する主アプリケーションと、
（ｃ）前記少なくとも１つ以上の従コンピュータで稼動する従アプリケーションと、を具備しており、
前記主アプリケーションは、前記複雑な計算を要する問題を複数のタスク断片に分割し、前記少なくとも１つ以上の従コンピュータに前記複数のタスク断片の小集合を割り当てるようになっており、
前記従アプリケーションは、前記主コンピュータに割り当てられた前記タスク断片の小集合を実行するように構成されたシステム。
【請求項５８】
前記主コンピュータと前記少なくとも一つ以上の従コンピュータ間の通信はローカルエリアネットワークを含んでいる、請求項５７に記載のシステム。
【請求項５９】
前記主コンピュータと前記少なくとも一つ以上の従コンピュータ間の通信はワイドエリアネットワークを含んでいる、請求項５７に記載のシステム。
【請求項６０】
前記主コンピュータと前記少なくとも一つ以上の従コンピュータ間の通信はインターネットを含んでいる、請求項５７に記載のシステム。
【請求項６１】
前記主アプリケーションは、前記従アプリケーションから定期的メッセージを受領するようにつくられており、前記定期的メッセージへの応答において、主アプリケーションは前記仮想スーパコンピュータ上で負荷調整処理を行う、請求項５７に記載のシステム。
【請求項６２】
前記主アプリケーションは、新規従コンピュータが利用可能であることを探知して、前記複雑な計算を要する問題を解きながら前記新規従コンピュータを組み入れるために、前記仮想スーパコンピュータを動的に再構成する、請求項５７に記載のシステム。
【請求項６３】
前記複雑な計算を要する問題は、金融ポートフォリオの最適化をさらに含む、請求項５７に記載のシステム。
【請求項６４】
前記複雑な計算を要する問題は、サプライチェーン物流をさらに含む、請求項５７に記載のシステム。
【請求項６５】
品目ごとまたは店舗ごとの最適在庫レベルを、対応する日ごとの積み替え予定に合わせて、決定することをさらに含む、請求項６４に記載のシステム。
【請求項６６】
前記複雑な計算を要する問題は、最適化への分岐限界アプローチのと連動して用いられる、請求項５７に記載のシステム。
【請求項６７】
前記複雑な計算を要する問題は、合計実行時間を減少させるために、大規模シミュレーションに関連して用いられる、請求項５７に記載のシステム。
【請求項６８】
前記複雑な計算を要する問題は、ネットワーク最適化問題を含んでいる、請求項５７に記載のシステム。
【請求項６９】
前記ネットワーク最適化問題は、搬送手段の経路決定および日程調整システムを含んでいる、請求項６８に記載のシステム。
【請求項７０】
前記複雑な計算を要する問題は、データベース検索を含んでいる、請求項５７に記載のシステム。
【請求項７１】
前記複雑な計算を要する問題は、データベース構築を含んでいる、請求項５７に記載のシステム。
【請求項７２】
前記複雑な計算を要する問題は、画像分析プログラムを含んでいる、請求項５７に記載のシステム。
【発明の詳細な説明】
【基礎となる出願】
【０００１】
本出願は、２０００年１２月２８日出願の米国仮出願第６０／２５８，３５４号、および２００１年９月１２日出願の米国出願の利益を享受し、その内容全体が本明細書の一部を構成する。
【０００２】
本発明は、海軍研究所により提供された、米国政府の援助契約第N０００１４−００−D０７００号のもとで行われた。したがって米国政府は、本発明において、何らかの権利を有する。
【発明の技術分野】
【０００３】
本発明は、並行して共同作業を行う複数のコンピュータを用いる仮想スーパコンピュータを構築するためのシステムおよび方法と、その用途に関する。より具体的には、平行して共同作業を行う複数の多目的コンピュータの一群で構成される、要求即応スーパコンピュータシステムに関する。コンピュータは、私設ネットワークを通じて連結されているだけでなく、作業効率とセキュリティの問題に対応がなされている場合は、インターネットを通じても連結される。
【発明の背景】
【０００４】
本発明によれば、平行して共同作業を行う複数の多目的コンピュータの一群で構成される、要求即応スーパコンピュータシステムが提供される。したがって本発明は、“集合体”スーパコンピュータの区分に入る。集合スーパコンピュータは、国立の研究所や主要な大学では、一般的である。他多数の集合スーパコンピュータと同様に、本発明も、個々のコンピュータ間の基礎接続およびデータ交換機構を動かすために、オークリッジ国立研究所（ORNL）（テネシー州、オークリッジ）により提供される無料で入手可能なソフトウェア・パッケージである「並行仮想機械（PVM）」を用いることができる。もし他のソフトウェア・アプリケーションが、仮想スーパコンピュータのすべての作業に不要な干渉をすることなく仮想スーパコンピュータを再構築できるならば、仮想スーパコンピュータの構築に他のソフトウェア・アプリケーションを用いることもできる。本発明はまた、以下に述べるようにPVMにより提供されない様々な機能を得るために、民間のソフトウェアも用いる。
【０００５】
当技術分野で周知の仮想スーパコンピュータは、たとえば、のサン・マイクロシステムズ社（カリフォルニア州、パロ・アルト）提供のサン・グリッド・エンジン・ソフトウェア（GES）のようなジョブ制御言語（JCL）プロセッサを備えている。とくに、GESのようなネットワーク化されたコンピュータに用いるJCLプロセッサ製品の場合、使用者は、JCL主コンピュータにジョブ（実行されるべきタスク）を預ける。そうすると、JCL主コンピュータはタスクを実行するネットワーク上のワークステーションを見出して資源配分を行う高度な規則を用いる。タスクは、1つのプログラムでも、多数のプログラムでもよい。JCLマスターコンピュータは、タスク内のすべてのプログラムを完了するために要する時間の合計が最小になるように、タスクにおけるそれぞれのプログラムを、ネットワーク上の個々のプロセッサに割り当てる。しかしGESは、プログラム間でその計算に影響を与えるプログラム間で共有されている情報のための特別な装置を提供しないという点で、並行処理の援助を行わない。
【０００６】
使用者は、並行処理を行うGESアプリケーションの開発が可能な範囲内で、別々のコンピュータ上で処理中のジョブ間におけるデータ交換方法を見つけなければならない。さらには、GESは個々のコンピュータ上で処理中のジョブが首尾一貫した全体の一部であることを認識できないことがある。したがって、何らかの理由で並行処理中のジョブの1つをやり残してしまった場合、GESはそのジョブを単に“待ち行列に戻す”ことのほかに何かしなければならないということを、認識できないかもしれない。このことによって、GESにおける並行処理アプリケーションに対する耐障害性の向上は、非常に困難になっている。
【発明の概要】
【０００７】
複数の多目的コンピュータワークステーションを用いて複雑な計算を要する問題を解決するための方法は、次のようなステップを備えている。（a）主コンピュータと、複数の多目的コンピュータワークステーションから選択された少なくとも１つの従コンピュータを有する仮想スーパーコンピュータを構築し、（ｂ）複雑な計算を要する問題を複数のタスク断片に分割し、（ｃ）複数のタスク断片から選択された少なくとも１つのタスク断片を、少なくとも１つの従コンピュータに割り当て、（ｄ）従コンピュータにタスク断片を完了させ、（ｅ）従コンピュータが出した結果を主コンピュータに受領させ、複雑な計算を要する問題が解決するまで、ステップ（ｃ）、（ｄ）および（ｅ）を繰り返す。
【０００８】
ＧＥＳのような周知の仮想スーパコンピュータとは対照的に、本発明は、一つのプログラムを、ネットワーク上の複数のプロセッサにまたがって稼動させることを必要とする。本発明の主コンピューターは、ただ単にプロセッサに仕事を割り当てるだけでなく、メンバコンピュータから送られてきた情報を用いて、所与の問題に取り組んでいる全てのプロセッサの作業を指示する。すなわち、タスク内のプログラムは、ただ単にネットワーク上のプロセッサで独立して稼動するために送られるわけではない。
【０００９】
本発明と、従来のコンピュータネットワークと、ＧＥＳにより制御されるネットワーク化されたコンピュータの違いは来客の行列への対応になぞらえて説明できる。たとえば、運転免許試験所（ＤＭＶ）に、免許取得や自動車の登録などの様々な処理を求めて、人がやってきたとする。
【００１０】
従来のコンピュータネットワークは、それぞれの窓口の前に列ができて、個々の係員は一つの業務（たとえば、免許、登録など）に専念するような、運転免許試験所に例えられる。一人の係員の前に長蛇の列ができている一方で他の係員は何もすることがない（たとえば、客はみな免許更新を求めていて、登録の係員は仕事がない）ということが、しばしば起こりうるので、非常に非効率的である。
【００１１】
ＧＥＳは一揃いの係員の前に一つの列ができた運転免許試験所のようなものである。係員は、幅広い業務（すべての業務でなくてもよい）をこなすことができる。列の一番前に来たら、手が空いていて希望の業務を取り扱える係員のところへ行く。このほうが、ずっと効率的であるし、運転免許試験所における資源をより有効に使える。
【００１２】
本発明の仮想スーパコンピュータは、州外から引っ越してきた際、すべての事務手続きを最初の係員に託せば、免許、所有権、登録、住所変更などの手続きをすべての（あるいは必要な人数の）係員に同時に処理してもらえるような運転免許試験所のようなものである。さらには、係員は必要な情報を自動的に交換し合う（たとえば、免許の係員が、社会保障番号を所有権および登録の係員に伝える、所有権の係員が自動車登録番号と権利番号を登録の係員に伝える、など）。免許手続きだけのために待つ時間よりも短い時間で、免許や登録などのすべての更新手続きをもれなくまとめたものを手にすることができる。
【００１３】
ＧＥＳにおけるそれぞれのコンピュータは、(本発明のスーパコンピュータとは違って)様々なタスクを行わねばならないので、ＧＥＳはネットワークに参加するそれぞれのワークステーションに十分なソフトウェアを装備する必要がある。その一方で、ＰＶＭ通信がワークステーションによって構築できるように、レジストリへの変更およびデーモンのインストールを最小限にとどめる必要がある。
【００１４】
本発明は、他のすべてのコンピュータを調整および制御する一つの専用コンピュータ（主コンピュータと呼ぶ）を備えたスーパコンピュータである。スーパコンピュータの形成は、主コンピュータ上でＰＶＭ主ソフトウェアを作動させることから始まる。主コンピュータは、できるだけ多くの（あるいはスーパコンピュータの使用者が明白に示しただけの）他のコンピュータとの接続を構築することにより、スーパコンピュータを形成する。ネットワーク上のそれぞれのコンピュータは、主コンピュータに解決を指示された個別の問題に関係するソフトウェア、データ、タスクをダウンロードする。
【００１５】
ネットワーク上のコンピュータは、好ましくは、ウィンドウズＮＴ／２０００のオペレーティングシステムが設定された一般的な多目的コンピュータである。このオペレーティングシステムは、政府および民間産業を通じて共通である。ウィンドウズＮＴ／２０００のコンピュータが本発明のスーパコンピュータに参加するために必要なことは、ウィンドウズＮＴ／２０００のレジストリにいくつかの簡単な変更を加えることと、遠隔コマンド解釈プログラムのソフトウェア（世界規模のサイトライセンスを５，０００ドルという比較的安価で購入できる）を導入することだけである。しかしながら、本発明は、ウィンドウズＮＴの使用環境に限定されず、もちろん、ＬｉｎｕｘやＵｎｉｘ、そのほかのオペレーティングシステムの使用環境にも適応できる。
【００１６】
本発明のスーパコンピュータは、すべての集合スーパコンピュータの中でも類のないいくつかの特徴を持っている。それらの特徴とは、次のようなものである。
【００１７】
ネットワークに参加しているコンピュータは、物理的にスーパコンピュータに関するタスク専用ではない、一般的な多目的コンピュータである。周知の集合スーパコンピュータはすべて、専用の参加コンピュータ（たとえば、フェルミ国立研究所のＰＣＦＡＲＭＳや、航空宇宙局により開発されたベオウルフ・クラスター）を有している。すなわち、一室に多数のコンピュータが置かれ、それらは互いに配線で繋がれており、その役割はスーパコンピュータの房の一部としての機能を果たすことだけである。その一方で、本発明で用いられる、ネットワーク上のコンピュータは、使用者がいつでも使えるオフィスまたは作業場に設置することができる。本発明は、主コンピュータとして作動するコンピュータが一つあればよい。
【００１８】
ネットワーク上のコンピュータは、一般の多目的な計算と、スーパコンピュータのタスクを同時にこなすことができる。ネットワーク上のコンピュータは、それら自身が物理的に専用でないだけでなく、スーパコンピュータが稼動しているときでさえも、普段の使用者は、個別のコンピュータにアクセスして使用することができる。このようなことが可能な集合スーパコンピュータは、他には知られていない。
【００１９】
ネットワーク上のコンピュータは、計算進行中であっても、スーパコンピュータから離脱できる。集合スーパコンピュータであって、計算中にその形状を変化させることができるものは、ほとんど知られていない。実際、メッセージ・パッシング・インターフェイス（Message Passing Interface、ＭＰＩ、ＰＶＭの変型）に基づく集合スーパコンピュータは、形状を多少なりとも変える場合には、シャット・ダウンして再起動させる必要がある。サンディア国立研究所のＵｎｉｘを用いた集合コンピュータは、ネットワーク上のコンピュータの削除ができることは知られているが、このシステムにおいてネットワーク上のコンピュータが削除できるのは、あくまで参加コンピュータの必要最小数（その数は、問題により変化する）まである。必要最小数のコンピュータのうちのどれかがスーパコンピュータから離脱した場合、計算に失敗してしまう。それとは対照的に、本発明のスーパコンピュータからネットワーク参加中のコンピュータが離脱した場合、その計算負荷を自動的に残りの参加コンピュータに再配分するので、計算の進行は妨げられない。本発明のスーパコンピュータは、すべての参加コンピュータが離脱して主コンピュータだけが残った場合でさえも、問題なく計算タスクを続けることができる。
【００２０】
ネットワーク上のコンピュータは、計算が進行中でもスーパコンピュータに加えることができ、その進行中の計算に利用される。ほとんどのＰＶＭを用いた集合コンピュータは、ネットワーク上のコンピュータをいつでも参加させることができる。しかしながら、加えられたコンピュータは、実際には次の計算が始まるまで使われない。それとは対照的に、本発明のスーパコンピュータは、加えられたコンピュータをすぐに使うことができる。計算負荷は、新しく加えられたコンピュータに自動的に再配分される。
【００２１】
スーパコンピュータに参加する資格のあるコンピュータは、ネットワーク上に現れた時にはいつでも自動的に探知され、スーパコンピュータに加えられる。要するに、本発明のスーパコンピュータは、自動的に適格なコンピュータ資源をネットワーク上で探し、見つけ出し、使用するのである。コンピュータは、（ａ）潜在的な参加者として設定され、かつ（ｂ）スーパコンピュータの使用者が、その特定のコンピュータをスーパコンピュータに加えることを指示した場合に、適格となる。後者の条件は、主コンピュータにスーパコンピュータを構成する個々のコンピュータのリストを提供するか、または、主コンピュータに「利用可能なすべての資源」を使うように指示することにより、満たされる。それとは対照的に、地球外知性探査計画（ＳＥＴＩ）のような分散型インターネット演算においては、個々のコンピュータは、主コンピュータに利用可能であることを知らせる明確な信号を送らなければならない。すなわち、参加は自主的であるのに対し、本発明においては、参加は、主コンピュータにより制御される。
【００２２】
このスーパコンピュータは、耐障害性に非常に優れている。参加コンピュータのいずれかが離脱した場合（例えば、ハードウェアまたはソフトウェアに起因して主コンピュータとの通信が途絶えた、または、コンピュータがシャット・ダウンされた場合）、本発明のスーパコンピュータは、自動的にその参加コンピュータの離脱を探知し、残ったコンピュータ間における計算負荷を再配分する。ネットワーク自体が故障した場合、（たとえいくぶん遅くなっても）ネットワークが回復する（スーパコンピュータが自動的に適格な参加コンピュータを探知し、それらを再接続する）まで、計算は主コンピュータにおいて継続される。主コンピュータが故障した場合のみ、計算も失敗する。この場合、計算は再開され、途中の結果から進行する（したがって、すべての計算結果が失われるわけではない）。さらに、本発明においては、集合スーパコンピュータの耐障害性を、主コンピュータの自動的再起動および処理再始動の実行により、強化することができる。本発明の集合スーパコンピュータと同等の耐障害性を持つ集合コンピュータは、他に知られていない。
【００２３】
本発明のスーパコンピュータはまた、既存のＬｉｎｕｘコンピュータのネットワーク上で並行処理を可能にする製品の中でも類のない、いくつかの特徴を持っている。そのような製品の一つであるEnfuzionと呼ばれる製品は、本発明のスーパコンピュータとは実質的に全く異なる。Enfuzion が解決することを意図された問題は、わずかに異なるデータの組をいくつも処理するために、同じアプリケーションを何度も何度も用いることを必要とする。たとえば、有用な統計結果を得るために、本質的には同じ処理が何度も必要なモンテ・カルロ・モデリングを行う際に、よく見られる問題である。言うまでもなく、これは、単調で時間のかかる処理である。Enfuzionは、ネットワーク上のコンピュータそれぞれに、そのアプリケーションを自動的および同時に稼動させることによって、この特殊なニーズに対応する。したがって、このモデルを１００回連続して稼動させるかわりに、Enfuzionは、１００台にコンピュータを同時に用いて、それを一度に済ませることができる。このことにより、使用者は通常一度モデルを稼動させるのにかかる時間と同じ時間で、１００回のモデルの稼動を行うことができる。
【００２４】
これは、本発明のスーパコンピュータに比べれば、各段に性能が劣るものである。本発明のスーパコンピュータは、些細であるが特殊なケースで要求される計算を実行することができる。Enfuzion により提供される機能に加えて、本発明のスーパコンピュータは、計算進行中でも、異なるコンピュータ間でデータの交換をすることもできる。すなわち、集合コンピュータのうちの一つのコンピュータから得られた計算結果のデータは、直接他のコンピュータに送信され、他の接続点における新しいデータの使用を可能にする。知られているかぎりでは、Enfuzion は、計算の進行に影響を及ぼす可能性のあるデータを交換または共有するというコンピュータ間の通信を構築できない。
【００２５】
さらに、本発明のスーパコンピュータにおいて、参加コンピュータは一つの計算問題を処理するために共同作業を行うことができる。Enfuzion が各コンピュータ上で実行するソフトウェアは、他のコンピュータから基本的には独立している。これはすなわち、使用者がそれぞれのコンピュータに歩いて行き、同じプログラムを（おそらくそれぞれ違うデータを入力して）起動しているようなものである。すべてのEnfuzion ができるのは、この処理を自動化して、使用者がコンピュータからコンピュータへと渡り歩かなくて済むようにすることである。本質的には、それぞれのコンピュータは所与の小さな問題を処理している。あるコンピュータで進行している計算の部分的な結果は、他のどのコンピュータの計算の進行にも、影響を及ぼすことができる。それぞれのコンピュータ上でのEnfuzion プログラムの実行は、均一的であると同時に連続的である（それらは、単に時間の節約のために同時に動いている）。  それとは対照的に、本発明のスーパコンピュータにおいて実行されるプログラムは、時間節約だけでなく計算能力向上のために、集合コンピュータ内のほかのコンピュータとの有益な相互作用を行う。
【発明の詳細説明】
【００２６】
コンピュータネットワーク１００は、図１Ａに示すように、互いに連結された複数のコンピュータシステムを備えている。その通信路は、たとえば、ローカルまたはワイドエリア・ネットワーク、もしくはインターネットのような、ネットワークである。本発明の仮想スーパコンピュータは、コンピュータネットワーク１００から選択されたコンピュータからなる。コンピュータネットワーク１００上の一つのコンピュータは、仮想スーパコンピュータの管理者として機能する、主コンピュータ１０２である。主コンピュータ１０２は、図１Ｂに示すように、オペレーティング・システム１０４、メモリ１０６、中央プロセッサ１０８、並行仮想コンピュータ（ＰＶＭ）デーモン１１０、および主アプリケーションソフトウェア１１２を備えている。ＰＶＭデーモン１１０は、共同作業を行う独立したコンピュータシステムを備えた並行仮想コンピュータを構築するためのソフトウェア・アプリケーションのいずれかである。ＰＶＭデーモン１１０は、仮想スーパコンピュータの主コンピュータ１０２と他のメンバコンピュータとの通信路を制御する。本発明の一実施形態においては、ＰＶＭデーモン１１０は、オークリッジ国立研究所（ORNL）により提供されるＰＶＭソフトウェアである。
【００２７】
主アプリケーション・ソフトウェア１１２は、複雑な計算を要する問題を解く際、仮想スーパコンピュータの作動を制御する。すなわち、主アプリケーション・ソフトウェア１１２は、仮想スーパコンピュータを構築および管理し、スーパコンピュータにおける他のメンバコンピュータにタスクを割り当て、そのメンバコンピュータから報告された計算結果を、保存するという役割を担う。主コンピュータ１０２は、多目的コンピュータシステムであってもよい。好ましくは、主コンピュータ１０２は、仮想スーパコンピュータの管理者として専任でタスクを遂行するコンピュータシステムである。主コンピュータ１０２はまた、主アプリケーション・ソフトウェア１１２から受領したタスクを実行する従アプリケーション・ソフトウェア１１４を備えている。
【００２８】
上述のように、コンピュータ・ネットワーク１００から選択された多目的コンピュータは、本発明の仮想スーパコンピュータを構築するために用いられる。図１Ａの影付きのアイコンは、仮想スーパコンピュータの構成員であるコンピュ−タを示す。すなわち、たとえば、中でもコンピュータ１０２、１１６、１１８および１２０は、仮想スーパコンピュータの構成員である。それに対して、コンピュータ１２２は、図１Ａに示される仮想コンピュータの現在の構成員ではない。なおこの表示方法は、仮想スーパコンピュータの構成員と非構成員を区別するのにすべての図面を通じて用いられる。
【００２９】
図１Ｃに示すように、メンバコンピュータ１２０などのメンバコンピュータは、オペレーティング・システム１２４、メモリ１２６、中央プロセッサ１２８、ＰＶＭデーモン１３０、および従アプリケーション・ソフトウェア１２０を備えている。さらに、コンピュータ１２０は、使用者がコンピュータ１２０上の様々なタスクを実行することができるように、他のアプリケーション・ソフトウェア１３４を備えていてもよい。他のアプリケーション・ソフトウェアとしては、たとえば中でも、ワープロ、表計算、データベースもしくは他の日常的に用いられている事務処理アプリケーションが含まれていてもよい。メンバコンピュータ１２０上のオペレーティング・システム１２４は、主コンピュータ１０２上のオペレーティング・システム１０４と同じでなくてもよい。同様に、メンバコンピュータ１２０上のオペレーティング・システム１２４は、メンバコンピュータ１１６や１１８のような他のメンバコンピュータのオペレーティング・システムと同じでなくてもよい。したがって、本発明の仮想スーパコンピュータは、異種のコンピュータ・システムのネットワークを備えていてもよい。本発明の一実施形態においては、メンバコンピュータ１２０上のＰＶＭデーモン１３０および従アプリケーション・ソフトウェア１３２は、主コンピュータ１０２上で実行されるＰＶＭデーモン１１０および従アプリケーション・ソフトウェア１１３と同一である。
【００３０】
本発明の仮想スーパコンピュータは、一つのメンバコンピュータで障害が発生した場合に、自動的に自身を再設定する仕組みを提供する。同様にして、本発明の仮想スーパコンピュータは、利用可能になったメンバコンピュータを加える仕組みを提供する。このように、本発明の仮想スーパコンピュータは、システム管理者の干渉を最小限にとどめて、複雑な計算を要する問題を解決するための、非常に丈夫なシステムである。さらに、本発明の仮想スーパコンピュータが丈夫であるために、メンバコンピュータは、その計算において果たせる役割があるかどうかに応じて、仮想スーパコンピュータへ自由に参加または離脱できる。したがって、本発明の仮想スーパコンピュータは、メンバコンピュータの使用者に不便をかけることなく、メンバコンピュータの余剰処理能力を最大限に利用できる。
【００３１】
図１Ａおよび図１Ｄの概略図は、メンバコンピュータが仮想コンピュータから離脱した場合の仮想スーパコンピュータの再構築方法を示している。各メンバコンピュータの処理負荷は、図１Ａに示すとおりである。各メンバコンピュータの実際の処理負荷は、主コンピュータ１０２によって各メンバコンピュータに割り当てられたタスクによって決まる。負荷は、単位時間あたりの推定指示量、または割り当てられたタスク断片の推定指示量、もしくは仮想スーパコンピュータの一部として使用中の、もしくは使用されつつあるメンバコンピュータの処理能力を示す他の何らかの単位に基づく推定指示量に基づいている。たとえば、メンバコンピュータ１１６の処理負荷は、符号Ｆで示されており、符号Ｆは複雑な計算を要する問題を解決するために使用される（任意の単位の）容量を示している。同様に、主コンピュータ１２０の処理負荷はＩとされ、それはＦと同一であってもよいし、そうでなくてもよい。コンピュ−タ１２２は仮想スーパコンピュータの現時点の構成員ではないので、その処理負荷は、図１Ａにおいてゼロで示されている。
【００３２】
メンバコンピュータが仮想スーパコンピュータから離脱した場合、その負荷は残っているメンバコンピュータに再分配されねばならない。たとえば、図１Ｄにおいて、コンピュータ１１６および１１８は、その処理負荷がゼロになっていることからもわかるように、仮想スーパコンピュータから離脱している。この場合において、負荷ＦおよびＧは、それぞれもともとコンピュータ１１６および１１８に割り当てられていたもので、残りのコンピュータに再分配されなければならない。図１Ｄに示すように、残りのコンピュータそれぞれの負荷が調整される。別の実施形態においては、残りのコンピュータそれぞれに割り当てられた増加負荷は、たとえば、Ａ1、Ｂ1などであり、均等に分配される。すなわち、Ａ1＝Ｂ1＝Ｃ1など、となる。別の実施形態においては、残りのコンピュータそれぞれに割り当てられた増加負荷は、もともと割り当てられている負荷に比例する。たとえばＩ1は、メンバコンピュータ１２０への増加負荷であり、Ｉ1＝Ｉ／Ｔ×（Ｆ＋Ｇ）で与えられ、Ｉはメンバコンピュータ１２０にもともと分配されていた負荷、Ｆはコンピュータ１１６にもともと分配されていた負荷、Ｇはコンピュータ１１８にもともと分配されていた負荷、Ｔは負荷再分配前に残りのメンバコンピュータに割り当てられていた負荷の合計である。各コンピュータへ負荷を割り当てる別の方法は、それぞれのコンピュータの処理速度に応じて、負荷を分配するやり方である。いずれにせよ、それぞれのシステムへの増加負荷の合計は、離脱したコンピュータにもともと割り当てられていた負荷に等しい。すなわち、Ｆ＋Ｇ＝Ａ1＋Ｂ1＋Ｃ1＋Ｄ1＋Ｅ1＋Ｈ1＋Ｉ1、となる。
【００３３】
本発明のスーパコンピュータは、メンバコンピュータが離脱する際に自身の再構築を行うが、ちょうどそれと同じように、本発明の仮想スーパコンピュータは、ネットワーク上で新しいコンピュータが利用可能であることを探知した場合にも自身の再構築を行う。図２Aおよび２Bは、本発明の仮想スーパコンピュータが、新しいメンバコンピュータを仮想コンピュータに迎え入れる際の再構築方法を示す概略図である。図２Aにおいて、ネットワーク２００は互いに連結された複数の多目的コンピュータを有する。それらのコンピュータのなかで、仮想スーパコンピュータの一員であるものは、図２Aにおいて影付きで表されている。仮想スーパコンピュータに関連するネットワーク２００上のそれぞれのコンピュータの処理負荷は、示されているとおりである。たとえば、メンバコンピュータ２０２は、主コンピュータ２０４により割り当てられた計算に関する処理負荷Bを有している。一方、コンピュータ２０６は、仮想スーパコンピュータの一員でないので、処理負荷はゼロである。図２Bにおいて、コンピュータ２０６は本発明の仮想スーパコンピュータに参加したところである。このとき、主コンピュータ２０４は、図２Bに示すように、メンバコンピュータ間に負荷を再分配する。
【００３４】
各メンバコンピュータへの新しい負荷は、新規のメンバコンピュータの処理能力によって、何％か減少するであろう。たとえば、新規のメンバコンピュータ２０６は初期負荷Fを受領すると、次に図２Bに示すように、それぞれのメンバコンピュータに割り当てられる負荷が減少する。すなわち、F＝Ａ1＋Ｂ1＋Ｃ1＋Ｄ1＋Ｅ1＋Ｇ1＋Ｉ1となる。その減少分は、仮想スーパコンピュータにおける各メンバコンピュータの処理能力に比例するか、または負荷分配の他の計算方法によって決定される。たとえば、Ｂ1は、メンバコンピュータ２０２の減少分であり、Ｂ1＝Ｂ／Ｔ×Ｆで与えられ、Ｂはもともとメンバコンピュータ２０２に割り当てられた負荷、Ｆは新規メンバコンピュータ２０６に割り当てられた負荷、Ｔはメンバコンピュータ１１６に負荷Ｆを割り当てる以前の、メンバコンピュータに割り当てられた負荷の合計である。
【００３５】
残りのメンバコンピュータ間の再分配に用いられる正確な仕組みを備えているにもかかわらず、主コンピュータ１２０は、負荷を再分配する際、次の点を考慮に入れる。主コンピュータ１０２は、負荷のすべての部分が計算に組み込まれていることを保証する。すなわち、たとえ残りの各コンピュータへの増加負荷が、離脱したコンピュータ１１６にもともと割り当てられていた負荷のパーセンテージまたは割合で表現されていたとしても、正確なパーセンテージでそのタスクを分割することはできない。それは、以下の初期負荷調整についての段落で詳しく説明するように、最小限に定義されたタスク断片にまで減少させることしかできず、それ以上分割できないタスクもあるからである。さらに、主コンピュータ１０２は、最新の処理状況の統計を用い、残りのメンバコンピュータについて、現在の処理容量に応じた再分配の計算を行う。
【００３６】
図３に示されたフロー図は、複雑な計算を要する問題を解決するための仮想スーパコンピュータを構築および利用するための、本発明の一実施形態に用いられるステップを示す。通常の当業者にとって明らかであるように、以下に示すステップは、主コンピュータが再起動すればいつでも仮想スーパコンピュータが構築され、所与の問題に必要な計算がメンバコンピュータに割り当てられるように、自動化されている。図３に示すように、そのステップは３段階に分けられる。すなわち、始動段階３００、計算段階３１０および終了段階３２０である。各段階は、以下の段落にて詳述される。
【００３７】
１．始動段階
ステップ３０１において、主コンピュータの電源を入れる。ステップ３０２において、ＰＶＭデーモンのソフトウェアをマスターコンピュータ上で起動させる。主アプリケーション・ソフトウェアとメンバプリケーション・ソフトウェアは、それぞれステップ３０３、３０４で起動させる。ステップ３０４の完了により、メンバコンピュータを一つ有する規模の仮想スーパコンピュータが構築される。本発明によれば、複雑な計算を要する問題を解決するためにこのようなコンピュータを用いることがもちろん可能であるが、より大きな仮想スーパコンピュータが、処理容量が増大するので、好ましい。
【００３８】
ステップ３０５において、（主アプリケーション段階を終えた）主コンピュータが、図４に示すようなステップにより、仮想スーパコンピュータを構築する。一度仮想スーパコンピュータが構築されると、主コンピュータは各従コンピュータにデータ・セットを分配する。ここで用いられているように、“従コンピュータ”、“メンバコンピュータ”、“仮想スーパコンピュータの一員”という語はどれも、仮想スーパコンピュータにおいて前述の従ソフトウェアを稼動させているコンピュータのいずれかを指す。たとえば、図１Ａに示す主コンピュータ１０２と多目的コンピュータ１２０は、どちらも“従コンピュータ”である。ステップ３０６において、主コンピュータは、次の計算に必要なデータ・セットおよび情報をすべて、本発明の仮想スーパコンピュータにおける各従コンピュータに分配する。ある実施形態においては、データ・セットは、データと、それに適用されるべき計算指示を一緒に含んでいる。この実施形態においては、従コンピュータ上で実行される従アプリケーションは、主コンピュータから指示およびデータを受領し、送られた指示を実行するための非常に単純なアプリケーションである。その代わりに、従アプリケーションは、検討中の問題を解決するために必要な計算指示を含むもっと複雑なものであってもよい。別の実施例においては、従アプリケーションは、主コンピュータからの追加の計算指示を受領する容量のほかに、ソフトウェアに含まれる計算指示の組み合わせを備える。
【００３９】
ステップ３０６において、主コンピュータは、各従コンピュータに計算を実行させる準備する。これは、計算に要するデータや、従コンピュータに割り当てられるかもしれないあらゆるタスクを実行するために従コンピュータが要するその他の情報、または、実行試験および負荷調整に必要な計算を行うために従コンピュータが要するその他の情報を提供することを含む。
【００４０】
ステップ３０７において、主コンピュータ１０２は、仮想スーパコンピュータの初期負荷調整を行う。このステップにおいて、主コンピュータは、個々のメンバコンピュータから受領した情報を用いて、個々のコンピュータの処理能力および仮想スーパコンピュータ全体としての集合的な処理能力を見積もる。このような情報を用いて、主コンピュータは本発明の仮想スーパコンピュータに適した負荷配分を決定する。さらに上述のように、主コンピュータは、複雑な計算を要する問題を個別のタスク・セットに分割するようにプログラムされている。ここで、各タスク・セットをタスク断片と定義する。したがって、複雑な計算を要する問題の全体は、タスク断片の合計と考えることができる。タスク断片は個別のタスク・セットなので、主コンピュータはどの従コンピュータがどのタスク断片を割り当てられているかを把握することができる。さらには、後のステップにおいて、従コンピュータは、各タスク断片の計算結果を、同時進行的に提供する。このことにより、主コンピュータは、複雑な計算を要する問題を解決する際の必要に応じて、データ・セットおよびタスク断片を更新することができる。
【００４１】
２．計算段階
各従コンピュータは、従アプリケーションの事前に用意されたプログラムによって、または主コンピュータ１０２の指示に従い、もしくは事前に用意されたプログラムの指示とステップ３１２で割り当てられた主コンピュータから受領した指示との組み合わせにしたがって、計算を始める。
【００４２】
実行されるべきタスクは、主コンピュータおよび従コンピュータ双方の待ち行列に挿入される。ステップ３１３において、主コンピュータ１０２は、仮想スーパコンピュータの計算活動を監視する。割り当てられた計算タスクがすべて完了すれば、主コンピュータ１０２はステップ３２１に移る。そうでなければ、ステップ３１４において、主コンピュータ１０２は、各従コンピュータから送られる計算結果のネットワークを監視する。ステップ３１４において計算結果が受領されると、主コンピュータ１０２は仮想スーパコンピュータ内の一つまたはそれ以上の他の従コンピュータにそれらを配分する。
【００４３】
上述のように、本発明の仮想スーパコンピュータ内の各従コンピュータは、主コンピュータ１０２に定期的に実行報告を行う（ステップ３１５）。定期的実行報告は、従コンピュータに割り当てられた特別な性能測定計算の結果を含んでいてもよいし、従コンピュータ上の負荷を指示するために用いることができる他の実行測定基準を含んでいてもよい。本発明の従コンピュータは、複数の多目的コンピュータシステムを備えているので、主コンピュータが従コンピュータの実行と負荷を監視して、タスク割り当てにおける必要な調整を行い、仮想スーパコンピュータが最大の処理能力を発揮できるようにすることが重要である。
【００４４】
ステップ３１６において、主コンピュータ１０２は、従コンピュータから受領した実行データを用いて、仮想スーパコンピュータの負荷を最良の状態に調整する方法を決定する。ステップ３１７において、主コンピュータ１０２は、ステップ３１６で構築された負荷調整の枠組みに従って、従コンピュータから未完了の計算タスクを取り戻して、再分配する。ステップ３１８において、主コンピュータ１０２は、仮想スーパコンピュータの規模に影響を及ぼす事象を探知して処理する。そのような事象は、従コンピュータ上における従処理の不具合や、従コンピュータ自体の不具合を含み、どちらの場合でも、仮想スーパコンピュータの規模は小さくなる。同様に、その事象には、新しい従コンピュータの追加であってもよく、それにより仮想スーパコンピュータの規模および計算能力は増大する。どちらの場合においても、主コンピュータ１０２は、図５に示すように、その事象を処理できる。
【００４５】
３．終了段階
上述のように、所与の複雑な計算を要する問題のためのタスクがすべて完了するとすぐに、処理は終了段階３２０へ移動する。ステップ３２１において、主コンピュータ１０２は、各従コンピュータからの最終実行統計値を集計する。これらの実行統計値は、たとえば、他の複雑な計算を要する問題を解決するために構築される、次の仮想スーパコンピュータの基準値を設定するために用いられる。とくに、その統計値は、ネットワーク内におけるコンピュータ資源の利用促進のために用いられる。
【００４６】
最終的には、ステップ３２２から３２４において、本発明の仮想スーパコンピュータは解体され、通常のシステム管理プログラムが呼び出される。すなわち、ステップ３２２において、各従コンピュータ上の従アプリケーションが終了され、ステップ３２３において、ＰＶＭデーモンが終了される。ステップ３２４において、仮想スーパコンピュータの計算結果の使用者への報告の準備が行われる。
【００４７】
ＰＶＭの構築
上述のように、主コンピュータがネットワーク上に現れるとすぐに、すなわち、主コンピュータに電源が入り、主および従アプリケーションが始動するとすぐに、主コンピュータはステップ３０５において仮想スーパコンピュータの規模を拡大することを試みる。図４は、仮想スーパコンピュータを構築する本発明の一実施形態において用いられるステップのフロー図である。ステップ４００において、主コンピュータ１０２は、潜在的なホストコンピュータの有無を判断する。このステップは、いくつかの異なるやり方で実行される。たとえば、それは既知の潜在ホストコンピュータに対し、利用可能かどうかを照会するポーリングを含んでいてもよい。他の実施形態では、各潜在ホストコンピュータは、その利用可能性を、ネットワークもしくは主コンピュータ１０２に直接、定期的に発信する。さらに他の実施形態では、主コンピュータによるポーリングと潜在ホストコンピュータによる情報発信を組み合わせることで、潜在ホストコンピュータの認識が可能となっている。
【００４８】
潜在ホストコンピュータが見つかるとすぐに、主コンピュータ１０２は、ステップ４０２において自身とその潜在ホストコンピュータの通信路が仮想スーパコンピュータの支援に適しているか否かを判断する。これは、必要に応じて、ＴＣＰ／ＩＰネットワーク用の「ｐｉｎｇ」のような標準的ネットワークツール、もしくはネットワークの回線容量または安定性を判断する私有のデータ通信ツールを用いて行われる。通信路が適切でない場合は、主コンピュータ１０２はステップ４００に戻り、他の潜在ホストを認識できるかどうかを確かめる。逆に通信路が適切であれば、主コンピュータ１０２は、ステップ４０４に移り、ＰＶＭデーモンソフトウェアを主コンピュータからホストコンピュータにダウンロードする。ステップ４０４（および／または、後述するステップ４１４）は、主コンピュータが、潜在ホストコンピュータに、そのデーモンを始動指示とともに送信する「押出」法により実行される。あるいは、ステップ４０４および／または４１４は、潜在ホストが主コンピュータからソフトウェアを積極的に引き出す「牽引」法により実行される。どちらの場合においても、主および潜在従コンピュータがダウンロードするソフトウェアの存在場所を認識している限り、ソフトウェアは他のコンピュータシステムからダウンロードされてもよいということがわかる。あるいは、各潜在ホストコンピュータは、ローカル記憶装置上にそのソフトウェアのローカルコピーを備えておくこともできる。後者の実施形態は、設定管理のための追加費用、およびソフトウェア変更の際に各システム個別にかかる更新のための追加費用が必要なので、大体の環境において望ましくない。しかしながら、ＰＶＭデーモンおよび／または従アプリケーションのソフトウェア設定は、十分に安定しているので、ローカル配置を行ってもよい。
【００４９】
ステップ４０６において、潜在ホストコンピュータ上でＰＶＭデーモンが開始し、ステップ４０８において、主コンピュータ上でのＰＶＭデーモン処理と潜在ホストコンピュータ上でのＰＶＭデーモン処理との間で、ＰＶＭ間の通信が構築される。ステップ４１０において、ＰＶＭ間の通信がうまく構築できなかった場合、処理はＰＶＭデーモンが潜在ホスト上で終了するステップ４１２へと進行する。次に、主コンピュータ１０２は、追加する潜在ホストコンピュータを探してステップ４００に戻る。逆に、ＰＶＭ間の通信がうまく構築できた場合、処理は従コンピュータに従アプリケーションをダウンロードするステップ４１４に進行する。
【００５０】
ステップ４１６において、従コンピュータ上で従アプリケーションが開始し、ステップ４１８において、正確な計算が行われることを確かめるために、従アプリケーションがテストされる。ステップ４１８におけるテストは、たとえば計算指示および所定のデータ・セットを従コンピュータに送ることにより、行われる。次に従コンピュータは、必要な計算を実行し、結果を主コンピュータに返信する。ステップ４２０において、主コンピュータ１０２は、報告された結果を既知の正しい結果と比べて、潜在ホスト上の従アプリケーションが正しく稼動するか否かを判断する。従アプリケーションが正しく稼働しない場合、処理はステップ４２４へ進行し、潜在ホストコンピュータ上の従アプリケーションは終了する。次に、処理はステップ４１２における後片付けへと続き、ステップ４００に戻って仮想スーパコンピュータに参加する次の潜在ホストを探す。ステップ４２０において、従アプリケーションが妥当な結果を返信した場合、「潜在ホスト」は、仮想スーパコンピュータの「メンバ」になる。処理は、新しいメンバコンピュータの作業能力または負荷容量を見積もるステップ４２６へと進行する。この見積もりは、テスト計算の処理速度や、そのコンピュータの期待作業を測定するための他の測定基準に基づく。見積もられた期待作業は、図３のステップ３０７において検討される初期負荷調整の実行に用いられる。最後に、処理はステップ４００に戻って、追加の潜在ホストを認識できるかどうかを確認する。認識できない場合は、ＰＶＭ構築段階は完了し、すなわち図３のステップ３０７の実行が完了する。
【００５１】
１．動的再構築―主コンピュータ
上述のように、本発明の仮想スーパコンピュータは、従コンピュータが仮想スーパコンピュータに参加できる状態になった場合もしくは従コンピュータが仮想スーパコンピュータから離脱する場合に、自身を動的に再構築する。仮想スーパコンピュータの規模に影響を与えるような事象は、図３のステップ３１８において探知される。図５は、そのような事象に応じて、仮想スーパコンピュータが再構築される際のステップに関する、より詳細なフロー図である。ステップ５００において、ある事象が探知されると、それが新しいコンピュータホストが仮想スーパコンピュータに参加可能になるというものか、それとも現存する従システムのどれかに不具合が発生したというものかが判断される。前者の場合、処理はステップ５０１に進行し、後者の場合は、ステップ５０２に進行する。そのような事象は、適切な探知機構を用いた主コンピュータ１０２上で探知または指摘が可能である。たとえば、主コンピュータ１０２から特定の従コンピュータにメッセージを送信したが、所定時間内に何の返信もない場合に、従コンピュータにおける障害発生が探知される。そのほかの状況としては、所定時間内に定期的実行統計報告や計算結果の報告を受領していない場合に、主コンピュータ１０２は従コンピュータにおける障害発生を探知する。また、従コンピュータが所与の基準データ・セットについて誤った結果を出した場合も、主コンピュータ１０２は従コンピュータにおける障害発生を探知する。同様にして、仮想スーパコンピュータに参加可能な潜在ホストコンピュータがあるかを、いくつかの方法で探知する。たとえば、新規に利用可能となった潜在コンピュータは、利用可能であることをネットワークに知らせてもよいし、主コンピュータに直接通知してもよい。あるいは、主コンピュータが定期的に仮想スーパコンピュータの潜在メンバになるかもしれないシステムのネットワークに対し、定期的にポーリングを行うこともできる。
【００５２】
まず、従システムに障害が発生した場合には、処理は、そのホストがＰＶＭからＰＶＭへの通信を通じて連絡可能であるかを主コンピュータ１０２が判断するステップ５０２に進行する。ホストに連絡可能であれば、すなわち従コンピュータが依然として仮想スーパコンピュータの一部であれば、処理はステップ５０３へ進行する。そうでなく、ＰＶＭデーモンが従コンピュータ上で適切に機能していない場合は、処理はステップ５０４に進行し、主コンピュータ１０２は、そのホストコンピュータにＰＶＭデーモンを再始動するよう指示する。ステップ５０５において、ＰＶＭデーモンがホストコンピュータ上でうまく再始動した場合、処理はステップ５０３へ進行する。そのホストコンピュータ上でデーモンを再始動できなかった場合は、処理はステップ５０６へ進行し、主コンピュータ１０２は仮想スーパコンピュータからその従コンピュータを離脱させる。
【００５３】
図５に示されているステップは、主コンピュータの立場から見たものである。つまり、主コンピュータと従コンピュータ間のネットワーク通信路が途絶えている場合でさえも、主コンピュータ１０２は、依然としてステップ５０４および５０５を実行しようとする。また、従アプリケーションおよび／またはＰＶＭデーモンは、主コンピュータにより仮想スーパコンピュータから離脱させられた後でさえ、障害の発生した従コンピュータ上にて稼動しつづける。この場合、従アプリケーションおよび／またはＰＶＭデーモンは、所定の時間内に主コンピュータからのフィードバックを受領しなかった場合、従コンピュータ上にて終了するようプログラムされていてもよい。
【００５４】
ＰＶＭからＰＶＭへの通信が２つのコンピュータ間で行われている場合、主コンピュータ１０２は、ステップ５０３において、障害の発生したホスト上の従アプリケーションを終了するように指示することができる。ステップ５０７において、主コンピュータ１０２は、障害の発生した従コンピュータに、従アプリケーションを始動（または再始動）するよう指示する。ステップ５０８において、主コンピュータ１０２は、従アプリケーションが従コンピュータ上でうまく始動しているか否かを判断する。従アプリケーションが始動できなかった場合、処理は５０６へと進行し、始動に失敗したホストは仮想スーパコンピュータから離脱させられる。上記のように、従コンピュータが仮想スーパコンピュータとの有効な通信を失った場合、何らかの状態監視プログラムが、従コンピュータ上で自動的にまたは手動にて実行されてもよい。
【００５５】
新規の従アプリケーションがホストコンピュータ上でうまく始動した場合、処理はステップ５１０へと進行し、従アプリケーションはホストコンピュータ上で初期化される。ステップ５１２において、従アプリケーションは、既知の問題もしくはデータ・セットに対する適切な計算結果が得られることを確認するためにテストされる。ステップ５１４において、従アプリケーションが誤った結果を返信した場合、処理はステップ５１６へと進行する。ステップ５１６において、主コンピュータ１０２は、従コンピュータに従処理を終了するように指示する。従処理が終了した後、主コンピュータ１０２は、ステップ５０６において仮想スーパコンピュータから従コンピュータを離脱させる。
【００５６】
ステップ５１４に戻って、従アプリケーションが期待通りの結果を出した場合、処理はステップ５１８へ進行する。ステップ５１８において、主コンピュータは、仮想スーパコンピュータにおける負荷を随時再分配して、効率性を最大にし、使用可能な計算手段を利用する。図５に示すように、ステップ５１８は、従コンピュータが仮想スーパコンピュータから離脱した場合や従コンピュータが仮想スーパコンピュータに参加した場合に、必ず実行される。ステップ５２０において、処理が完了し、仮想スーパコンピュータは提示された問題の解決を続ける。
【００５７】
ステップ５００において、新規のホストコンピュータが利用可能になったことが探知された場合、図５に示すように、上記と同様のステップの多くが実行される。まず、ステップ５０１において、新規のホストコンピュータが仮想スーパコンピュータに加えられる。さらに、このとき、主コンピュータから新規ホストコンピュータへＰＶＭデーモンをダウンロードし、始動させる指示が含まれていてもよい。ステップ５２２において、新規のホストが仮想スーパコンピュータに参加できなかった場合、たとえば、主コンピュータと新規ホスト間で、ＰＶＭからＰＶＭへの通信がうまく構築されなかった場合、処理はステップ５２０へと進行する。ステップ５２０において、仮想スーパコンピュータは、現存する形状にて進行中の計算を続ける。逆に、ＰＶＭからＰＶＭへの通信がうまく構築された場合、処理はステップ５０７へと進行し、新規のホストは前述のように従アプリケーションを始動させる。
【００５８】
２．動的再構築―ホストコンピュータ
図６は、新規ホストコンピュータが、本発明の一実施形態における仮想スーパコンピュータに参加可能な状態になった時に、当該ホスト上で実行されるステップを示す。図６のステップは、新規ホストコンピュータ上で実行されるものとして、示されている。ステップ６００における始動により、ホストコンピュータに電源が入れられる、もしくはそうでなければ、仮想スーパコンピュータを提供するコンピュータネットワークに参加する。ステップ６０２において、新規のホストコンピュータは、仮想スーパコンピュータに参加できることを報告する。前述のように、このステップは新しいホストコンピュータにより開始されてもよいし、主コンピュータ１０２からの問い合わせに応じるという形でもよい。
【００５９】
ステップ６０４において、新規のホストコンピュータは仮想コンピュータに参加する。前述のように、このステップは、主コンピュータもしくはネットワーク上の他の場所からＰＶＭデーモンをダウンロードしたあとに、新規のホストコンピュータにより行われてもよい。あるいは、新規のホストコンピュータは、ハードディスク上に記憶されたコピーから引き出したＰＶＭデーモンソフトウェアを稼動させてもよい。ＰＶＭデーモンが稼動すると、新規のホストコンピュータと仮想スーパコンピュータの主コンピュータの間で、ＰＶＭからＰＶＭへの通信が構築される。
【００６０】
ステップ６０６において、新規のホストコンピュータは従アプリケーション処理を開始し、提示された問題の解決に参加できるようにする。従アプリケーション処理は、主コンピュータまたはネットワーク上の他の場所からダウンロードされてもよいし、新規ホストコンピュータのローカルディスクに記憶されていてもよい。ステップ６０８において、新規ホストコンピュータは従アプリケーション上の一連のセルフテストを行う。セルフテストは、既知のデータ・セットの計算、およびその結果と既知の正しい結果の比較を含む。図６に示されるように、ステップ６１０で、セルフテストに失敗した場合、処理はステップ６１２へと進行して、その失敗は主コンピュータへ報告される。次にステップ６１４において、新規のホストコンピュータ上のＰＶＭデーモンが終了する。最後に、ステップ６１６において、新規のホストコンピュータ上の従アプリケーション処理が終了する。
【００６１】
ステップ６１０において、セルフテストに成功した場合、処理はステップ６１７へ進行し、新規のホストコンピュータは、実行統計値を主コンピュータに送信する。主コンピュータは、これらの実行統計値を用いて新規のホストコンピュータの処理能力を評価する。別の実施形態においては、新規のホストコンピュータは、処理速度、利用率、記憶容量、および処理能力に影響を及ぼすようなその他の統計値を報告してもよい。あるいは、主コンピュータは、その特定の新規ホストコンピュータの過去の履歴を基礎において見積もりを行うこともできる。見積もりは、そのコンピュータの種類や位置などのその他の情報、または、もしわかれば新規ホストコンピュータの主な使用者の身元に基づいていてもよい。
【００６２】
ステップ６１８において、新規のホストコンピュータは、主コンピュータから１つ以上のデータ・セットを受領する。前述のように、新規ホストコンピュータで実行される従アプリケーションの複雑さに応じて、データ・セットは、データおよび／または計算指示を含んでいてもよい。ステップ６２０において、新規のホストコンピュータは、その処理能力の見積もりに応じて、主コンピュータから１つ以上のタスク断片を受領する。ステップ６２２において、新規のホストコンピュータは、受領したタスク断片に処理を終了せよとの指示が含まれているか否かを判断する。含まれている場合は、処理はステップ６１４へと進み、片付け処理の後、終了処理が行われる。終了処理が割り当てられていない場合、新規のホストコンピュータは、ステップ６２４において割り当てられたタスクを実行する。新規のホストコンピュータは、ステップ６２６で実行統計を集計し、ステップ６２８でこれらの統計値を定期的に主コンピュータに送信し、主コンピュータは、その値を負荷調整作業に用いる。新規のホストコンピュータは、終了タスクを受領するまで、もしくは、エラー探知により従アプリケーションが自己終了するまで、割り当てられたタスクの処理と定期的なセルフテストの実行を続ける。
【００６３】
上述の構造およびステップは、一つの主コンピュータと、一つ以上の従コンピュータを有する並行仮想スーパコンピュータを構築および操作するために用いられる。上記のような実施例において、主コンピュータは、全てのタスクを割り当て、従コンピュータ間のデータ分布をすべてを調整する。別の実施例においては、図７に示すように、一つ以上の従コンピュータが、補助主コンピュータの役割を果たすように設定することができる。
【００６４】
図７におけるネットワーク７００は、互いに通信できる複数の多目的コンピュータを有する。主コンピュータ７１０は、図７に示す仮想スーパコンピュータの管理者である。さらに、多目的コンピュータ７２０および７３０は、補助主コンピュータとしての役割を果たす。本実施例においては、主コンピュータ７１０は、依然として前述の仮想スーパコンピュータの構築および作動を監視する。たとえば、主コンピュータ７１０は、仮想スーパコンピュータにおける負荷調整ならびに従コンピュータへのデータ・セットおよびタスクの割り当てを行う。補助主コンピュータ７２０および７３０もまた、他の従コンピュータにデータ・セットおよびタスクを割り当てることができる。複雑な計算を要する問題全体の解決のために、付加的または部分的な副次的問題を解くことが必要な問題は、本実施例により有利に解決することができる。たとえば、分岐限界最適化問題を考える場合、問題は、２つの下位問題に分かれる。各下位問題を検討しても解決できない場合は、各下位問題は２つの下位問題に順次分割される。このように、もとの問題は二進木の根にある。この二進木は、各下位問題が吟味（または理解）されるに伴い、拡大または縮小する。本実施例において、下位問題を割り当てられた従コンピュータは、仮想スーパコンピュータの他の従コンピュータにその下位問題を割り当てることによりその問題を２つに分割する必要がある時に、補助主コンピュータとなる。このように、各下位問題を解くのに必要な作業は、仮想スーパコンピュータの従コンピュータで手分けすることができる。
【００６５】
別の実施例においては、多目的コンピュータによる１つのネットワークが、１つ以上の仮想スーパコンピュータを構築するために用いることができる。この実施例において、複数の主コンピュータは、それぞれが一つ以上の個々の問題を解決するように設定される。図８は、本発明におけるこの実施例に係る多目的仮想スーパコンピュータを提供するネットワークの概略図を示す。ネットワーク８００は、２つの主コンピュータ８０１および８０２と、複数の多目的コンピュータ８１１−８３９を有するネットワークである。各仮想スーパコンピュータは、メンバコンピュータ上の利用可能な計算資源を最大限に使用するように設定されているので、資源の優先配分システムが実行されてもよい。たとえば、システム管理者は、主コンピュータ８０１に対して主コンピュータ８０２よりも高い優先順位を割り当ててもよい。システム管理者はさらに、主コンピュータ８０１が起動して動いている時は常に主コンピュータ８０２に対して完全な優先性を有する、と指示してもよい。この場合、すべての利用可能な多目的コンピュータは、主コンピュータ８０１の仮想スーパコンピュータに参加しようと試みる。主コンピュータ８０１が利用可能でない場合に限り、多目的コンピュータは主コンピュータ８０２の仮想スーパコンピュータに参加する。
【００６６】
あるいは、システム管理者は各主コンピュータの仮想スーパコンピュータに利用可能な多目的コンピュータについて、所定の割合を与えておいてもよい。すなわちたとえば、主コンピュータ８０１の仮想スーパコンピュータは常に利用可能な多目的コンピュータのうち６５％を利用できるのに対し、主コンピュータ８０２の仮想スーパコンピュータは、残りの３５％しか利用できない。ネットワークからメンバコンピュータが離脱する場合、または潜在メンバコンピュータが利用可能になった場合、２つの主コンピュータは、システム管理者の配分枠組をきちんと満たすように、調整される。当該分野では周知のように、２つの主コンピュータ間の通信はＰＶＭ通信から独立した回線を通じて行うことができる。あるいは、ＰＶＭデーモンを改変して、多目的並行仮想コンピュータにおけるＰＶＭからＰＶＭへの通信を円滑にすることもできる。
【００６７】
あるいは、ネットワーク上の各潜在メンバコンピュータは、優先する第１の主コンピュータに割り当てられてもよい。この実施例においては、指定された第１主コンピュータが稼動している時は常に、割り当てられた多目的コンピュータは、まずその主コンピュータのスーパコンピュータに参加を試みる。潜在メンバコンピュータは利用可能な状態となった時に第１主コンピュータが問題を処理していない場合、そのメンバコンピュータは、第２の主コンピュータのどれかに参加を試みて、別の問題の解決に助力することもできる。
【００６８】
本発明のさらに別の実施例においては、複数の仮想スーパコンピュータが、ネットワーク上に共存しており、それらの仮想スーパコンピュータは、いくつかのまたは全ての、同一のメンバコンピュータを共有することができる。すなわち、この実施例においては、一つの多目的コンピュータが、一つ以上の仮想スーパコンピュータのメンバになってもよい。本実施例が実行できるのは、各仮想スーパコンピュータが問題を解決する際に、メンバコンピュータ上の利用可能な資源の全てを常に使用しているわけではないという場合である。すなわち、前述の分岐限界最適化問題のような問題を解決するコンピュータは、データを回収したり結果をメンバコンピュータに転送するため、断続的な処理待機時間がある。その処理待機時間の間、メンバコンピュータは、他の主コンピュータから割り当てられた問題に取り組むことができる。
【００６９】
さらに他の実施例では、複数の仮想スーパコンピュータは、同じネットワーク上にて構築可能であり、各仮想スーパコンピュータの主コンピュータは、ネットワーク上の他の主コンピュータと“交渉”することができる。この実施例では、仮想スーパコンピュータは、たとえば所与の問題を所定時間内に解決するために構築される。主コンピュータは、利用可能な計算資源に基づき、資源が追加されなければその期限を守れないと決定することもある。この場合、主コンピュータは、ネットワーク上の他の主コンピュータに追加の資源を要求する。この要求には、当該仮想スーパコンピュータの優先性、必要な追加処理機械の数、処理機械を用いる時間などの、ネットワーク上の他の仮想スーパコンピュータがその要求を満たすべきか否かを決定するのに必要な他の情報を含んでもいてもよい。
【００７０】
さらに他の実施例においては、潜在メンバコンピュータの中央データベースが、ネットワーク上で保持されることが可能である。主コンピュータは起動して新しい仮想スーパコンピュータの構築を始める時は常に、リストを参考にして潜在メンバコンピュータのブロックを“吟味する”。主コンピュータは、吟味された各メンバコンピュータを仮想コンピュータに迎え入れることを試みる。当該メンバコンピュータのどれかが仮想スーパコンピュータにうまく参加することができない場合、主コンピュータは、その情報を中央データベースに報告し、他の利用可能なメンバコンピュータを探す。メンバコンピュータが割り当てられていた仮想スーパコンピュータから離脱すると常に、中央データベースは更新されてそのコンピュータが利用可能となったことが反映される。また、欠陥を原因とする離脱の場合は、そのコンピュータが利用できないことが示される。中央データベースは、仮想スーパコンピュータに参加可能である新規コンピュータの探知を目的とするネットワークへのポーリングにより、定期的に更新される。また、中央データベースは、多目的ワークステーションにおける状況の変化が探知された場合いつでも更新可能である。
【本発明の一実施形態の具体的な実施例】
【００７１】
本発明の一実施形態の具体的な実施例を示すことにより、個々の複雑な計算を要する問題を解決するための仮想スーパコンピュータならびに主および従アプリケーションを構築する際に、どのような要素がどのように考慮されるのかを示す。本実施例において、解決を要する複雑な計算を要する問題は、（ＭＩＭＥＲＢＳ）システムとして知られており、配置についた航空母艦による航空機操作を支えている小売・卸売部品交換方法(the retail and wholesale sparing policies)を決定する際に生じる膨大な非線形整数最適化問題を解決するためのシステムである。ＭＩＭＥＲＢＳは、利用可能な航空機の期待数を満たす代替部品の組み合わせの最小費用を決定する。規模（が数千の変数であること）と、代替部品と航空機の利用可能性が非線形関係にあることにより、この問題は難しいものとなっている。ＭＩＭＥＲＢＳは、通常のオフィスＬＡＮにより互いに結び付けられた既存のウィンドウズＮＴを用いた仮想スーパコンピュータ上で稼動するように開発された、非線形整数最適化の方法論である。本実施例は、Implementing a Large Non-Linear Integer Optimization on a Distributed Collection of Office Computers（Nickel, R.H., Mikoric-Torreira, I., and Tolle, J. W., 2000）, in Proceedings, 2000 ASME International Mechanical engineering Congress & Expositionにおいてより詳細に説明されており、同文献の内容は本明細書の一部を構成する。
【００７２】
本実施例は、仮想スーパコンピュータの構築、および本実施例の仮想スーパコンピュータの高い通信費用を考慮に入れＭＩＭＥＲＢＳ問題が並行処理によりいかに効率的に解決されるのか、について説明する。また、本実施例は、ＭＩＭＥＲＢＳのソフトウェアが優れた耐障害性と動的構築性を有していることにより、個々のコンピュータの離脱への対処、新規のコンピュータの迅速な自動的追加および動的負荷調整をいかにして行っているのか、を説明する。この具体的な実施例により、数ギガフロップスの作業がオフィスＬＡＮ上のたった数十の通常のコンピュータで処理できることが示される。
【００７３】
ＭＥＭＥＲＢＳ入門
前述のように、ＭＥＭＥＲＢＳは、航空母艦が飛行機を飛行任務に利用可能な状態に保つために運ぶべき代替部品の組み合わせを決定する際に生じる、膨大な非線形整数最適化問題を解決するために用いられる。ＭＩＭＥＲＢＳは、現実の部品交換および修復処理についての正確な数理モデルであるので、モデルは複雑な計算を要する問題を提示する。計算需要量が莫大なので、ＭＩＭＥＲＢＳは、最適な部品交換の方針を相応な時間内に決定するために、スーパコンピュータの能力を必要とする。実際のスーパコンピュータシステムの代わりに、通常のオフィス・コンピュータの集合として構築された本発明に係る仮想スーパコンピュータが、ＭＩＭＥＲＢＳの計算に時宜を得て用いられた。
【００７４】
本実施例に用いる仮想スーパコンピュータの構築
前述のように、仮想スーパコンピュータの構築に適したソフトウェアならばどれでも、本発明に用いることができる。本実施例においては、オークリッジ国立研究所にて開発された仮想並行処理機械（ＰＶＭ）ソフトウェア・パッケージが用いられた。ＰＶＭはもともとＵＮＩＸ環境において作動するように作られたのだが、ウィンドウズ環境へのＰＶＭのポートも備えている。本実施例では、既存のポートが遭遇した問題を解決するため、当該ソフトウェアに新規のポートが導入された。既存のポートが遭遇した２つの主要な問題は、次の通りである．（１）ＥＲＲＮＯがウィンドウズのＡＰＩに含まれる関数により、一致するように設定されていない場合でさえ、エラー状況の判断についてグローバル変数ＥＲＲＮＯに依存している。（２）既存のポートにおける環境変数からレジストリ入力への転換が、不完全であるかまたは一貫していない。本実施例で用いられるソフトウェアにポートされたバージョンにより、両方の問題が修正され、非常に安定した実行が得られた。このような実行においては、仮想スーパコンピュータ上で参加コンピュータが離脱および参加を繰り返し、一連のアプリケーションが実行されている時でさえ、仮想スーパコンピュータは、定期的に起動されて一度に何週間も稼動する。
【００７５】
本実施例では、サービスパック６Ａを搭載したウィンドウズＮＴのヴァージョン４．０を用いたコンピュータが、次の手順で仮想スーパコンピュータに参加するよう構成されている。
１．１つのコンピュータを、ウィンドウズＮＴのサーバとして設定する。このコンピュータは、すべてのＰＶＭと実行可能アプリケーションを含む。これらのアプリケーションを含むディレクトリを、他の参加コンピュータ、例えばメンバコンピュータ、がアクセスできる共有フォルダとして公開する。
２．仮想スーパコンピュータに参加可能な各コンピュータに対応するサーバ上に、独立共有ディレクトリをつくる。これらのディレクトリは作動中に、各参加コンピュータが、それぞれのＰＶＭ関連のファイルを蓄積している場所である。
３．他のウィンドウズＮＴの参加コンピュータを、標準ＰＶＭ用のレジストリ入力で構築する。ただし、ＰＶＭのルートディレクトリ、すなわちＰＶＭ＿ＲＯＯＴ、の環境変数がサーバの共有ＰＶＭルートディレクトリに設定されている場合、および一時ディレクトリ、すなわちＰＶＭ＿ＴＭＰ、の環境変数が個別のコンピュータに対応したサーバの共有ディレクトリに設定されている場合を除く。
４．他のコンピュータには、ＰＶＭもアプリケーションも導入しない。すべての参加コンピュータを、サーバ上に位置する実行可能アプリケーションにアクセスさせる。
５．ＰＶＭのコンピュータからコンピュータへのログインを、遠隔処理プログラムソフトウェアｒｓｈによって支援する。このソフトウェアは、Fischer, M., 1999, RSHD Services for Microsoft WIN32のウェブサイトhttp://www.markus-fischer.de/getservice.htmにて入手可能で、実施許諾されたウィンドウズＮＴの実行プログラムであり、本発明の仮想スーパコンピュータの実施に用いられる全てのコンピュータに導入された。さらに、各コンピュータに、ＰＶＭのコンピュータからコンピュータへのログインのための専用の同一な利用者名とパスワードを設定する。
【００７６】
参加コンピュータは、（１０ＢａｓｅＴと１００ＢａｓｅＴが混合した）通常のオフィスＬＡＮにより接続される。ＬＡＮおよびほとんどのコンピュータは、通常のオフィス・ワーク（Ｅメール、ファイルの共有、ウェブアクセス、文書作成など）に優先的に用いられる。仮想スーパコンピュータへの参加は、副次的なタスクである。この構成は、いくつかの利点を有する。第一に、すべての実行アプリケーションは一つのコンピュータに存在するため、コンピュータ間で実行アプリケーションを分配したり、バージョンを一致させたりする必要がない。第二に、（コンピュータが仮想スーパコンピュータに参加するために必要な）使用されなくなったＰＶＭに関連するファイルの除去が、それらの全てが一つのコンピュータに存在するため、容易である。第三に、エラーの記録、すなわちデフォルトにより、対応するＰＶＭ関連のファイルまたはそのファイルと同一のディレクトリにあるファイルのどちらかに出現するエラーの記録は、計算を指示しデバッグを行うコンピュータ上にすべて存在するので、デバッグが容易である。
【００７７】
本実施例では、４５のコンピュータが仮想スーパコンピュータに参加するように設定されたが、それらのうち多くは、他の処理に取られているので営業時間中は使用できず、多くのコンピュータがＬＡＮに接続されていないことになる。すなわち、本実施例の仮想スーパコンピュータは、通常、営業時間中は２０から３０のコンピュータを有しており、夜間および週末には４０から４５のコンピュータを有する（そして平日の朝には再びいくつかのコンピュータが離脱する）。当業者には明らかであるが、通常のＬＡＮ接続でつながれたオフィスコンピュータ上の仮想スーパコンピュータは、アルゴリズムの効果的実行を制約する通信の遅延を伴う。このような制約は、仮想スーパコンピュータがたとえばインターネットのような比較的通信速度の遅いネットワーク上で作動している場合に、より顕著である。本実施例では、１０ＢａｓｅＴと１００ＢａｓｅＴを組み合わせたイーサネットを使用したため、仮想スーパコンピュータの２地点間通信速度が４．５〜６．５byte/μsecであり、短いメッセージならば、最小通信時間は１５msecであった。
【００７８】
多くの一般的な並行処理技術（たとえば行列積を同時並行的な内積に分解するなど）は、これらの所与の通信遅延を効果的に利用することができなかった。すなわち、本実施例における仮想スーパコンピュータは、処理機械間の大規模かつ迅速な通信を必要とするアプリケーションには向かない（たとえば、偏微分方程式の有限要素解システム）。解くべき問題を分解して、処理機械に割り当てられた計算タスクに要する時間が、そのタスクに要する通信時間に対して長くなるようにすることで、本実施例の仮想スーパコンピュータの効果的な利用が可能となる。モンテカルロ・シミュレーションや、ネットワークの問題や、分解克服アルゴリズム等を含む様々な種類の問題は、そのように分解することができる。
【００７９】
ＭＩＭＥＲＢＳアルゴリズムの実行
ＭＩＭＥＲＢＳ最適化アルゴリズムは、内点アルゴリズムである。内点アルゴリズムの実行は、次の３つのステップを繰り返すことで行う。すなわち、（１）可能領域の中心に向かう中心化ステップ、（２）連続最適解を求めるオブジェクティブステップ（３）整数最適解候補を求める丸めステップ、を繰り返す。第１および第３のステップは、非常に複雑な数値計算を必要とする。これらの二つのステップを、非同期並行パターン検索（ＡＰＰＳ）アルゴリズムを用いて行う。ＡＰＰＳは非同期的であり、またそのサポートに必要なメッセージは比較的短いので、本発明の仮想スーパコンピュータを用いて解くのに非常に適している。元のＡＰＰＳアルゴリズムを著しく変化させることで、本実施例を用いて適切に実行することができた。
【００８０】
元のＡＰＰＳアルゴリズムは、Hough , P. D., Kolda, T. G., and Torczon, V. J., 2000, Asynchronous Parallel Search for Nonlinear Optimization, SAND 2000-8213, Sandia National Laboratoryに記述されており、次に説明する通りである。
【００８１】
＜ＡＰＰＳアルゴリズム１＞  Ｒnに含まれるｘの関数であるｆ（ｘ）を最小にすることが目的である。各プロセッサは、検索方向ｄを割り当てられ、現在最適点ｘbestと、それに対応する最適値ｆbest＝ｆ（ｘbest）と、現在増加分Δと、を維持する。各プロセッサは、次のステップを実行する。
１．他のプロセッサにより報告された潜在好適点を調べて、より適した点が受領された場合は、そこに移動する。具体的には、他のプロセッサから入ってくる各３重項[ｘin，ｆin，Δin]を検討し、ｆin＜ｆbestでああれば、[ｘbest，ｆbest，Δ]←[ｘin，ｆin，Δin]、のように更新する。
２．割り当てられた方向における現在量を図る。具体的にはｘbest←ｘin+ｄを計算し、ｆtrial＝ｆ（ｘtrial）の値を求める。
３．試行点がより適しているならば、そこに移動し、そうでなければそのステップ増加分を減少させる。具体的には、ｆtrial＜ｆbestであれば、[ｘbest，ｆbest]←[ｘtrial，ｆtrial]、のように更新し、新しい最小３重項[ｘbest，ｆbest，Δ]を他のすべてのプロセッサに配信する。そうでなければ、Δ←１／２Δとする。
４．ステップ量が小さすぎない限り、このプロセスを繰り返す。そうでなければ、現在割り当てられている検索が完了したことを報告する。具体的には、Δstop＞Δであれば、ステップ１に向かい、そうでなければ[ｘbest，ｆbest]でのローカル完了を報告する。
５．（ａ）すべてのプロセッサがこの点においてローカル完了する、または（ｂ）他のプロセッサからより好適な点を受領するまで、待機する。（ａ）の場合、停止および退出する。（ｂ）の場合、ステップ１に向かう。
【００８２】
すべての検索方向の組は、Ｒnのためのポジティブスパニングセットを形成せねばならない。そのためには、たとえ、ｅjがｊ番目のユニットベクトルを示すような領域の組｛ｅ1…ｅn，−ｅ1…−ｅn｝である２ｎの方向ベクトルを用いることが通常であるとしても、少なくともｎ＋１の方向ベクトルが必要である。
【００８３】
アルゴリズム１の第１の問題は、少なくとも検索方向と同じ数のプロセッサがあること、もしくは、同時期に独立した検索プロセス（各々は１方向についてのみ検索）が各プロセッサにおいて実行されること、のどちらをも、暗に示していることである。ＭＩＭＥＲＢＳのアプリケーションは、（ｎ＞＞１０００の）数千の変数を含んでいるので、ＡＰＰＳアルゴリズムの実行は、数千のプロセッサもしくは数百の（数千であるかもしれない）同時期プロセスが各プロセッサにおいて必要とされる。どちらを選択しても、本実施例のためには実用的でない。したがって、アルゴリズム１は修正され、各プロセッサは１方向ではなく一組の複数の方向を検索できるようにされた。
【００８４】
アルゴリズム１の第２の問題は、解決への大きな進歩ではない多くの“より適した”解を配信してしまうことが主な原因であるが、仮想スーパコンピュータ上でうまく動かないことである。（約数百以下の変数をもつ）小さいアプリケーションであれば、これは大きな問題ではない。しかし、数百もしくは数千の変数をもつアプリケーション上では、実行時間と計算方法は積み重なった丸め誤差からは無視しうるほどの、驚異的な数の“より適した”解についての転送と計算応答により、支配されることになる。この問題を解決するために、解を“より適している”と決めるためにより厳密な判断基準が適用された。この新しい判断基準を用いることにより、試行解は、それが他のプロセッサに転送される前に、より適しているだけでなくさらに顕著に適していなければならなくなった。この結果、次のアルゴリズムが生まれた。
【００８５】
＜ＡＰＰＳアルゴリズム２＞  Ｒnに含まれるｘの関数であるｆ（ｘ）を最小にすることを目的とする。各プロセッサは、検索方向の組｛ｄ1，…ｄm｝を割り当てられ、現在最適点ｘbestと、それに対応する最適値ｆbest＝ｆ（ｘbest）と、現在増加分Δと、現在方向ｄkを示す指標ｋと、を維持する。各ホストは、次のステップを実行する。
１．他のプロセッサにより報告された潜在好適地点を調べて、より適した地点が受領された場合は、そこに移動する。具体的には、他のプロセッサから入ってくる各３重項[ｘin，ｆin，Δin]を検討し、ｆin＞ｆbest−ε（１＋｜ｆbest｜）であれば、[ｘbest，ｆbest，Δ]←[ｘin，ｆin，Δin]、のように更新する。
２．次に調べる方向を決定する。具体的には、次の方向に対応する指標はｋ←（ｋ  ｍｏｄ  ｍ）＋１である。
３．すべてのｍ方向について検索が失敗した場合、ステップ量を減らしてΔ←１／２Δとする７に向かう。
４．割り当てられた方向における現在量を図る。具体的にはｘtrial←ｘbest+ｄを計算し、ｆtrial＝ｆ（ｘtrial）の値を求める。
５．試行点がより適しているならば、そこに移動する。具体的には、ｆtrial＜ｆbest−ε（１＋｜ｆbest｜）であれば、[ｘbest，ｆbest]←[ｘtrial，ｆtrial]、のように更新し、新しい最小３重項[ｘbest，ｆbest，Δ]を他のすべてのホストに配信する。
６．ステップ１に移動して、プロセスを繰り返す。
７．（ａ）すべてのホストがこの点においてローカル完了する、または（ｂ）他のプロセッサからより好適な点を受領するまで、待機する。（ａ）の場合、停止および退出する。（ｂ）の場合、ステップ１に向かう。
【００８６】
アルゴリズム２は、ＭＩＭＥＲＢＳの内点アルゴリズムにおける２箇所で用いられる。中心化ステップおよび丸めステップである。中心化ステップにおける利用は上記のとおりである。丸めステップにおいてアルゴリズム２を利用するために、Nickel, R. H., Goodwyn, S. C., nunn, W., Tolle, J.W., and Mikolic-Torreira, I., A Multi-Indenture, Muti-Echlon Readiness-Based-Sparing (MIMERBS) Model, Research memorandum 99-19, Center for Naval Analysesに記載されている丸め技術が、各々内点アルゴリズムの繰り返しを行うオブジェクティブステップの結果から整数解を得るために用いられる。そしてこの整数解は、アルゴリズム２の開始点として用いられ、（Δinitial＝4 and Δstep＝１ work well）の整数格子上に残る。すべての場合において、本実施例は、方向ベクトルのための領域の組を用い、オブジェクティブ関数はコスト関数とペナルティ関数の適切な組み合わせに設定されている。
【００８７】
実行アーキテクチャ
本実施例において、ＭＩＭＥＲＢＳは、主―従アーキテクチャを用いて実行される。このアプローチによると、並行して作動する構成コンピュータ間の明確な責任分担が可能となる。またそれにより、ＡＰＰＳアルゴリズム２を実際に実行することにほとんど排他的に集中させられる単なる従コンピュータと、アルゴリズムの全般的な実行を調整する主コンピュータと、を有する非常に単純なプログラミングモデルが実現できる。この段落では、主および従コンピュータが何を実行し、いかにしてその作業調整を行っているのかをより詳細に説明する。従コンピュータは、２者のうちより単純なものを指す。その基本的仕事は，主コンピュータに指示された時に、主コンピュータにより割り当てられた検索方向のセットを用いて、ＡＰＰＳアルゴリズム２を実行することである。それが第一のタスクであるとはいえ、従コンピュータは、主コンピュータからの様々な要求に応えることができなければならない。具体的には、従コンピュータは、
１．データおよび主コンピュータから与えられた情報のセットアップを読みこむ。
２．コンピュータから割り当てられた検索方向（ＡＰＰＳ進行中の変化も含む）を受領する。
３．主コンピュータにより示された初期値および目的関数を用いてＡＰＰＳを始動させる。
４．主コンピュータに新しい“最適”解を報告する。
５．主コンピュータから新しい“最適”解を受領する。
６．主コンピュータに検索のローカル完了を報告する。
７．主コンピュータの指示によりＡＰＰＳを終了する。
８．主コンピュータに実行統計値を報告する。
９．問題があれば、主コンピュータに報告する。
【００８８】
各従コンピュータに送られる情報のセットアップは、任意の点での任意の種類の目的関数の計算に必要なデータを、すべて含んでいる。目的関数は、ＡＰＰＳの始動時に従コンピュータに対して適切な変数およびセレクターを通じて指定される。本実施例においては、従コンピュータが互いに直接通信することは、全くない。従コンピュータは、単に主コンピュータに報告を行い、主コンピュータから更新を受領するだけである。他の従コンピュータの情報を把握しなくてよいので、従コンピュータは非常に単純化されている。実際、従コンピュータは、他の従コンピュータが存在するということさえ認識していない。しかし前述のように、本発明の他の実施例は、従コンピュータ間の通信を含んでいる可能性がある。本実施例においては、ある従コンピュータから受領した解を、他のすべての従コンピュータに知らせることが主コンピュータの役割である。主コンピュータは、従コンピュータよりも複雑な構成を有する。主コンピュータは、データの出入力、内点アルゴリズム実行の全面的指示、従コンピュータの管理を司る。そのため、主コンピュータは、次の機能を果たす。
１．入力データを読む。
２．仮想スーパコンピュータのすべてのホスト上に、従コンピュータをつくる。
３．最適化を構成する。
４．データと情報のセットアップを従コンピュータに送る。
５．内点アルゴリズムの繰り返しを実行する。
（ａ）中心化ステップ：従コンピュータによりＡＰＰＳを始動させ、管理する。
（ｂ）オブジェクティブステップ：主コンピュータのみにより実行される。
（ｃ）丸めステップ：主コンピュータは、連続解を丸めて初期整数解を獲得し、それからこの解を用いて従コンピュータによる整数検索を始動させ、管理する。
６．従コンピュータを終了させる。
７．適切な報告とその他のデータ出力を行う。
【００８９】
実行の観点からいえば、本発明における主コンピュータが行う複雑なタスクのほとんどは、“従コンピュータを用いてＡＰＰＳを始動させ管理する”ことである。このタスクは、並行処理の中心であり、次のサブタスクからなる。１．すべての従コンピュータに初期値および目的関数の適切な選択を送信することのにより、ＡＰＰＳを始動させる。２．個々の従コンピュータから“最適”解を受領する。３．各従コンピュータの検索状態を把握する。４．従コンピュータから提供される実行統計値を収集し、必要に応じて負荷配分を調整する。５．全ての従コンピュータがタスクを完了すれば、検索を終了する。６．従コンピュータにおける問題およびスーパコンピュータにおける変動を処理する。前述のように、主コンピュータは、他の全ての従コンピュータに対して、受領した解を再配信する。これは非効率的に思えるかもしれないが、そのおかげで本実施例におけるＡＰＰＳの集束が著しく加速される。これは、入ってくる解の報告を大きな単位で処理して、個々に入力された解をみな再配信する代りに一括して最適解を再配信することより、達成される。主コンピュータが通常処理を実行している間に、入力された解がメッセージ待ち行列に蓄積されるので、主コンピュータは、待ち状態に陥ることなく、入ってくる解の報告を大きな単位で処理できる。最終的には、再配信により従コンピュータが解を更新するスピードがほとんど落ちることなく、ネットワーク交通量が約二桁ほど減少する。この改良により、ＡＰＰＳの集束に必要な関数評価の回数が１５から３０％ほど減少する。すべての通信は主コンピュータを通過するので、従コンピュータのローカル完了が永続する状態にない場合に起こる問題として周知である、非同期中止問題を処理する効果的手段もまた提供される。すなわち、従コンピュータは、そのローカル検索を完了した後であっても、完了の時点よりも適した解を含む更新を受領した場合は、再始動する。ただ単にすべての従コンピュータが終了しているかどうかをポーリングすることは、そのポーリングの最中に更新メッセージが送信されているかもしれないので、非効率的である。本実施例において、すべての更新は、主コンピュータを通じて配信されるので、発信された更新メッセージはすべて追跡できる。さらに、従コンピュータは、すべての更新メッセージを認識する（通信負荷を最小にするために、ローカル検索完了時にまとめて行う）。これにより、確実な停止規則を実行するために十分な情報を与えられる。主コンピュータは、すべての従コンピュータがローカル完了し、すべての更新を認識した場合に、検索の終了を決定する。
【００９０】
耐障害性および信頼性
本実施例において構築される仮想スーパコンピュータは、耐障害性に優れており、仮想スーパコンピュータを構成する個々のホストが（故障もしくはその所有者の再起動に起因して）離脱することを許容する。仮想スーパコンピュータを構築するのに用いられるＰＶＭソフトウェアが潜在するホストコンピュータのセットが長い時間に変化することを許容するとしても、仮想スーパコンピュータ上にて稼動するアプリケーション、この場合はＭＩＭＥＲＢＳ、はそのような変化が起こった場合にも計算が正しく進行することを保証せねばならない。信頼性に関して、２つの問題がある。第１の問題は、ＰＶＭを実行できるプロセッサがネットワーク上に現れたらいつでもそれを動的に取りこむことである。第２の問題は、プロセッサ上の負荷変化に応じて、動的な負荷調整を行うことである。
【００９１】
本実施例で実行されるＭＩＭＥＲＢＳアプリケーションは、作動中に起こりうる障害を処理するにあたって、非常に頑丈に作られている。ＭＩＭＥＲＢＳが扱わねばならない基本的な障害は、従コンピュータの離脱である。従コンピュータは、様々な事情により離脱することがある。すなわち、従コンピュータを稼動させているプロセッサが仮想スーパコンピュータから離脱した（たとえば、再起動や、シャットダウンなどで）場合や、従プログラムそのものに障害が発生した（たとえばランタイムエラーまたはリソース枯渇などによる）場合や、プロセッサ上のＰＶＭデーモンが致命的なランタイムエラーを起こした場合や、従コンピュータへの通信路が破壊された場合、である。本実施例においては、主アプリケーションによって実行される２つの関数が、耐障害性を支えている。すなわち、従コンピュータが“離脱した”ことを決定する関数と、その状況に対応する関数である。
【００９２】
主コンピュータは、従コンピュータが離脱したことを、いくつかの方法で判断する。第１に、ＰＶＭのｐｖｍ通知サービスが、従プロセスが終了したこと、もしくはプロセッサが仮想スーパコンピュータから離脱したことを（ＰＶＭメッセージを介して）知らせる。第２に、従コンピュータが主コンピュータに何らかのランタイムエラーもしくは潜在的問題（たとえば、メモリ不足や、内部状態の矛盾など）を報告した場合、主コンピュータは、従コンピュータを終了させ、それが離脱したものとして扱う。最後に、主コンピュータがあまりにも長時間従コンピュータから何のメッセージも受領していない場合、従コンピュータが離脱したことを決定し、そのように処理する（すなわち、通信路が壊れていることや従コンピュータが“停止”していることを探知する）。主コンピュータは、従コンピュータの離脱に対して、基本的にはその従コンピュータの作業負荷を他の従コンピュータに割り当てることにより対処する。このため、主コンピュータは、現在どの検索方向がどの従コンピュータに割り当てられているかを常に把握している。従コンピュータが離脱する場合、主コンピュータは、まずその従コンピュータが稼動しているプロセッサがまだ仮想スーパコンピュータの一部であるか否かを調べる。もしそうならば、主コンピュータは、そのプロセッサ上にて新しい従コンピュータを始動させることを試みる。それがうまくいけば、前任の従コンピュータの検索方向は、そのプロセッサ上の新しい従コンピュータに再び割り当てられる。離脱した従コンピュータのプロセッサがすでに仮想スーパコンピュータの一部でなかった場合、もしくは主コンピュータがそのプロセッサ上にて新しい従コンピュータを始動できなかった場合には、主コンピュータは、離脱した従コンピュータの検索方向を、残っている他の従コンピュータに再配分する。このことにより、すべての検索方向が活動中の検索セット中に保持されることが保証され、また従コンピュータが離脱した場合でさえ、ＡＰＰＳの処理は中断されることなく進行可能となる。最終的には、ＭＩＭＥＲＢＳはいかなる従コンピュータ、遠隔ＰＶＭデーモン、もしくは遠隔プロセッサにおける障害によっても、影響されないのである。本実施例において、３種類の障害だけが、ＭＩＭＥＲＢＳに障害を発生させうる。すなわち、
１．主プロセッサの離脱、
２．主コンピュータ上で稼動するＰＶＭデーモンの致命的なランタイムエラー、もしくは、
３．ＭＩＭＥＲＢＳの主プログラムにおける致命的なランタイムエラー、である。
【００９３】
各３つの障害が起これば、手動での再起動により、内点アルゴリズムの最後に完了した繰り返しから計算が再開される。はじめの２つの障害は、ＰＶＭを用いることによる、避けられない結果である。仮想スーパコンピュータは、その構築を開始したプロセッサに障害が発生した場合、もしくはそのプロセッサ上で稼動するＰＶＭデーモン（主ＰＶＭデーモン）にランタイムエラーが生じた場合、崩壊する。より信頼性の高い仮想スーパコンピュータが必要な場合は、仮想スーパコンピュータを構築する別のアプリケーションソフトウェアを用いることにより、この状況を避けることができる。第３の障害は、ＭＩＭＥＲＢＳ主プログラムにおける致命的なランタイムエラーであるが、ＡＰＰＳアルゴリズム１の実行で用いられたアプローチ（Hough et al., 2000）を用いることで避けることができた。その実行では、主コンピュータは必要ない。従コンピュータがみな必要な場合に“主コンピュータ”として機能することができる。あるいは、主コンピュータにおける致命的な障害のリスクは、同一のプロセッサ上で仮想スーパコンピュータの構築開始および主プログラムの稼動を行うことにより、減少させることができる。さらに、このプロセッサは他の使用者から独立している専用のコンピュータであって無停電電源を有する場合、リスクはさらに小さくなる。
【００９４】
ホストコンピュータの動的追加
前述のように、ＰＶＭによりプロセッサが仮想スーパコンピュータにいつでも参加することが可能となったとはいえ、主アプリケーションは、この場合ＭＩＭＥＲＢＳであるが、その新しいプロセッサ上にて計算を始めなければならない。ＭＩＭＥＲＢＳ主アプリケーションプログラムは、新しいプロセッサが仮想スーパコンピュータに追加されるときはいつでも、ＰＶＭのｐｖｍ通知サービスを用いて（ＰＶＭメッセージを介して）通知を受領する。主コンピュータは、この通知に対して次のようにして応答する。
１．新しいホストコンピュータ上にて従コンピュータを始動させる。
２．その従コンピュータにすべての必要なセットアップデータを送信する。
３．新しい従コンピュータとホストの組み合わせが上手く作動することを確かめるために計算テストを指示する。（新規の従コンピュータとホストが上手く作動しない場合、従コンピュータは終了され、ホストは仮想スーパコンピュータから離脱する。）
４．検索方向の再分配を行い、新しい従コンピュータに相応な割当分を分配する。
５．ＡＰＰＳ検索が進行中である場合、適切な変数と現在最適解を送ることにより、新しいホストコンピュータ上のＡＰＰＳを開始する。
【００９５】
主コンピュータは、ＭＩＭＥＲＢＳの通常始動処理の一部として、従コンピュータに配信したすべてのメッセージを照会する整列リストを維持するのに必要とされるセットアップデータを把握している。新しい従コンピュータが始動すると、主コンピュータは、先入れ先出し順でリストの中身を再送する。
【００９６】
上記の説明は、新しいプロセッサが仮想スーパコンピュータに実際に参加する場合に、起こることを単に述べているだけである。問題は依然として、潜在プロセッサがネット上に現れたことを探知し、実際にそれを仮想スーパコンピュータに追加することである。これは、稼動中に利用可能となったあらゆるコンピュータの能力を自動的に活用するために、必要とされる要素である。PVMは、このサービスを直接提供しないので、本実施例は、PVMが設定されたコンピュータがネットワーク上に現れたかどうかを確認するために定期的に調査を行い、それが見つかったら仮想スーパコンピュータに追加するという、主コンピュータ上のルーティンを含む。
【００９７】
負荷調整
仮想スーパコンピュータにおいて、ホストコンピュータが参加および離脱することに加えて、主アプリケーションは、仮想スーパコンピュータを構成するプロセッサ上のいかなる計算負荷の変化に対しても適応しなければならない。本実施例は、日常業務にも同時に使われている通常のオフィスコンピュータを用いるので、プロセッサの負荷はその使用者によって大きく変化せざるをえない。ＭＩＭＥＲＢＳは、効率的な計算を保証するために、このような負荷の変化に応じる必要がある。
【００９８】
ＡＰＰＳは非同期であるため、調整された負荷の定義は、自明ではない。大きく捉えると、すべての検索方向は、“同等にすばやく”検索されるべきである。したがって、本実施例において、負荷均衡は各プロセッサに割り当てられた方向の数により決定される。たとえば、仮想スーパコンピュータ内に２つのプロセッサがあって、一方のプロセッサが他方のプロセッサの二倍の処理速度を有する場合、速いプロセッサは、遅いプロセッサの二倍の方向を割り当てられる。本実施例においては、調整された負荷が決定されるのは、すべてのプロセッサｉについて、Ｎiは割り当てられた検索方向の数を示し、Ｒiはｉ番目のプロセッサにて目的関数の値が求められる際の速度を示す場合において、Ｎi／Ｒiが一定の時である。動的負荷調整をサポートするために、すべての従コンピュータは、実行データを記録し、定期的に主コンピュータに送信する。主コンピュータは、このデータを関数計算速度の変化を探知するために用いて、負荷配分がアンバランスになった場合はいつでも負荷配分を調整する。実際の再調整は、割り当てられた検索方向をある従コンピュータから別の従コンピュータへと移すことにより行われる。
【００９９】
動的負荷調整を行うことに加えて、本実施例はまた、ウィンドウズＮＴのスケジューリング・スキームを用いて、従タスクの相対的優先順位を、使用者のタスク、特に最前面にある使用者のタスクに劣るように調節する。具体的には、従コンピュータは、処理優先クラスをＮＯＲＭＡＬ＿ＰＲＩＯＲＩＴＹ＿ＣＬＡＳＳ（通常優先クラス）に設定し、スレッド優先クラスをＴＨＲＥＡＤ＿ＰＲＩＯＲＩＴＹ＿ＢＥＬＯＷ＿ＮＯＲＭＡＬ（通常以下のスレッド優先）に設定されることにより、バックグラウンド処理として作動する。このことにより、仮想スーパコンピュータに参加しているデスクトップコンピュータは、使用者に対する応答に優れていることがわかる。これは、仮想スーパコンピュータが通常の使用者から見えないようにするために、重要な部分である。当該分野の技術者には明らかであるように、同様の処理優先化スキームは、ＵＮＩＸ、Ｌｉｎｕｘなどを含む別のオペレーティングシステム上においても実行可能である。
【その他の実施例】
【０１００】
本発明は、アプリケーションおよび本発明のシステムと方法の利用に関する。現在の好適な実施例において、本発明は、十分に活用されていないパーソナルコンピュータおよびワークステーションをたくさん有する組織のファイアウォールの背後で用いることができる。多くのオフィス環境は、ワープロやｅメールのようなタスクのために、強力なプロセッサを備えたコンピュータを用いているので、多くの中規模もしくは大規模のオフィスにおいては、通常は十分にその処理能力を活用されていないコンピュータが大量に存在する。したがって、本発明を用いることにより、この十分に活用されていない能力を利用して、スーパコンピュータの能力を手ごろな費用で仮想スーパコンピュータを形成することができる。低コストのスーパコンピューティングを利用できるので、従来は現実的に解決できなかった様々な種類のアプリケーションが、解決可能となる。本発明のアプリケーションには、次のようなものがある。
【０１０１】
一般的応用
＜金融への応用＞  比較的小規模な金融機関は、現代のポートフォリオ理論の手段を用いて貸付金や有価証券を最適化することを必要としている。これらの手段は、スーパコンピュータの力を必要とすることが多い。本発明の仮想スーパコンピュータは、スーパコンピュータの導入に必要な財源の投入を行わずに、その能力を獲得できるという選択肢を与える。
【０１０２】
＜在庫・卸最適化＞  品目ごともしくは店舗ごとの最適な在庫水準を、日付単位の積み替え予定（どこに何で運ぶか）と連動させて決定することは、Ｗａｌ−Ｍａｒｔのような大規模卸業者にとって重要な競走上の優位である。従来、そのような大きな問題を毎日のアップデートに間に合うようにすばやく処理するには、専用の高性能コンピュータハードウェアが必要であった。このような問題は、現存するオフィスコンピュータのネットワーク上の仮想スーパコンピュータにより解決することができ、多くの小規模な企業は、コンピュータハードウェアに追加の投資を行うことなくこの技術の利点を享受することができる。
【０１０３】
＜分岐−限界問題＞  最適解を見つけるために分岐−限界アプローチを用いる、整数プログラム問題などの最適化問題は、仮想スーパコンピュータを用いることができるように構築することができる。
【０１０４】
＜シミュレーション＞  大規模なシミュレーションは、仮想コンピュータ上で行うことができる。ｎ台のコンピュータを有する仮想コンピュータを用いると、稼動時間合計は、ｎ台分ほど減少させることが可能である。
【０１０５】
＜経路決定および日程調整＞  搬送手段の経路決定および日程調整のようなネットワーク最適化問題は、仮想スーパコンピュータ上にて分割して解決できる。
【０１０６】
＜データベース分析＞  データベース検索またはデータベース構築(database mining)は、仮想スーパコンピュータを用いたワークステーションのネットワークを通じて可能である。各ワークステーションは、検索もしくは分析のためにデータベースの一部を割り当てられる。
【０１０７】
＜画像分析＞  戦車（もしくは他の標的）を発見せねばならない場合、現存する画像の自動的な分析を必要とする。これは、ひとつのパーソナルコンピュータが行うと、大変時間がかかるが、コンピュータのネットワークに簡単に分担させることができる。
【０１０８】
軍事的応用
＜超音波探知機予測＞  浅水では、３６０度の超音波探知機予測を行う必要がある。これは、通常一回につき１度分行われる。通常のパーソナルコンピュータ上では、各１度のタスクは約１５秒間であるので、３６０度すべての分析には、９０分かかる。たとえば５０台のパーソナルコンピュータからなる仮想スーパコンピュータ上で同じ計算を行えば、約２分で完了できる。さらに、各接続点は計算結果を共有するために他の接続点と通信できるので、個別のコンピュータからの計算結果は、超音波探知機の映像をより容易に形成するために用いることができる。
【０１０９】
＜任務計画＞  たとえば戦略的飛行任務計画システム（ＴＡＭＰＳ）などの軍事任務計画システムは、空爆やその他の任務の計画に用いられるソフトウェアツールである。しかし、多くの任務計画システムは、任務の成功もしくは失敗の評価を下さない。そのような評価は、業務計画レベルで利用できるコンピュータシステム上では、時間がかかりすぎる（数時間かかる）莫大なモンテカルロ・モデリングを必要とするからである。前述のように、そのようなシミュレーションの実行は、本発明の集合スーパコンピュータによって容易に対応することができる。
【０１１０】
最後に、このシステムは、現在の好適な（ファイアウォールの背後の）セキュリティを持つオフィス環境を想定して記述されているのであるが、本発明はインターネットもしくは他の同様な公共のネットワークに接続されたコンピュータを用いることができる。ある実施例では、集合スーパコンピュータの主コンピュータは、従コンピュータにアクセスして、従コンピュータの計算タスクを開始する。したがって、安全な環境は、ネットワーク上のコンピュータにアクセスする部外者に関連する問題を単に緩和することには、好適である。本発明に係る集合スーパコンピュータは、集合体のメンバが主コンピュータへのアクセスを許可するように構築されていれば、セキュリティで守られていないネットワーク上でも作動できる。また、実用の観点から、インターネット上の集合スーパコンピュータは、接続されているコンピュータ間でのより高速な接続を必要とし、これにより計算に用いられるデータをほぼリアルタイムで接続点間でシェアリングして、本発明の処理能力を最大にすることができる。
【０１１１】
さらに、本発明の代表的な実施例を示すにあたって、本明細書は、本発明の方法および／またはプロセスを、特定のステップの連続として提示している。しかし、当該方法またはプロセスが、本明細書中で述べた特定の順序でなくてもよい、という意味において、当該方法またはプロセスは、示された特定のステップの連続に限定されるべきでない。当業者の都合により、ステップの順序を変えてもよい。したがって、本明細書にて述べた特定のステップの順序は、請求項の通りに限定されると解釈するべきではない。さらに、本発明の方法および／またはプロセスについての請求項は、表記された順番のステップの実行に限定されるべきでなく、また当業者は、都合により簡単に順番を変えることができるが、それも依然として本発明の思想と目的の範囲内である。
【０１１２】
前述の本発明の好適な実施例は、説明および記述を目的として開示された。開示された通りの形に本発明を限定したり、その形を包括的なものとすることは、意図していない。本明細書中に述べられた実施例についての数多くの変形や改良は、上記の開示から当業者とって明白であろう。本発明の範囲は、ここに添付された請求項およびそれに均等するものによってのみ、規定されることになる。
【図面の簡単な説明】
【０１１３】
【図１Ａ】複数の多目的コンピュータを備えた仮想スーパコンピュータを示す概略図である。
【図１Ｂ】本発明の仮想スーパコンピュータの主コンピュータの構成を示す概略線図である。
【図１Ｃ】本発明の仮想スーパコンピュータのメンバコンピュータの構成を示す概略線図である。
【図１Ｄ】仮想スーパコンピュータからメンバホストコンピュータが離脱した場合における、本発明の仮想スーパコンピュータの再構築方法を示す概略図である。
【図２Ａ．２Ｂ】仮想スーパコンピュータに新しいコンピュータが参加する場合における、本発明の仮想スーパコンピュータの再構築方法を示す概略図である。
【図３】複雑な計算を要する問題の迅速な解決のために、仮想スーパコンピュータを構築し使用する、本発明の一実施形態において用いられるステップを示すフロー図である。
【図４】仮想スーパコンピュータ構築のために、本発明の一実施形態において用いられるステップを示すフロー図である。
【図５】メンバホストコンピュータが仮想スーパコンピュータにおいて参加または離脱する際に、仮想スーパコンピュータを自動的に再構築するために、本発明の一実施形態において用いられるステップを示すフロー図である。
【図６】メンバホストコンピュータが仮想スーパコンピュータに参加しようとする際に、本発明の一実施形態において用いられるステップを示すフロー図である。
【図７】複数の多目的コンピュータと複数の補助主コンピュータを備えた仮想スーパコンピュータを示す概略図である。
【図８】多目的コンピュータの共通プールを備えた２つのスーパコンピュータを示す概略図である。
【図１Ａ】
2004530182.tif 000003
【図１Ｂ】
2004530182.tif 000004
【図１Ｃ】
2004530182.tif 000005
【図１Ｄ】
2004530182.tif 000006
【図２Ａ．２Ｂ】
2004530182.tif 000007
【図３】
2004530182.tif 000008
【図４】
2004530182.tif 000009
【図５】
2004530182.tif 000010
【図６】
2004530182.tif 000011
【図７】
2004530182.tif 000012
【図８】
2004530182.tif 000013
【国際公開パンフレット】
2004530182.tif 000014
2004530182.tif 000015
2004530182.tif 000016
2004530182.tif 000017
2004530182.tif 000018
2004530182.tif 000019
2004530182.tif 000020
2004530182.tif 000021
2004530182.tif 000022
2004530182.tif 000023
2004530182.tif 000024
2004530182.tif 000025
2004530182.tif 000026
2004530182.tif 000027
2004530182.tif 000028
2004530182.tif 000029
2004530182.tif 000030
2004530182.tif 000031
2004530182.tif 000032
2004530182.tif 000033
2004530182.tif 000034
2004530182.tif 000035
2004530182.tif 000036
2004530182.tif 000037
2004530182.tif 000038
2004530182.tif 000039
2004530182.tif 000040
2004530182.tif 000041
2004530182.tif 000042
2004530182.tif 000043
2004530182.tif 000044
2004530182.tif 000045
2004530182.tif 000046
2004530182.tif 000047
2004530182.tif 000048
2004530182.tif 000049
2004530182.tif 000050
2004530182.tif 000051
2004530182.tif 000052
2004530182.tif 000053
2004530182.tif 000054
2004530182.tif 000055
2004530182.tif 000056
2004530182.tif 000057
2004530182.tif 000058
2004530182.tif 000059
2004530182.tif 000060
2004530182.tif 000061
2004530182.tif 000062
2004530182.tif 000063
2004530182.tif 000064
2004530182.tif 000065
2004530182.tif 000066
2004530182.tif 000067
2004530182.tif 000068
2004530182.tif 000069
2004530182.tif 000070
2004530182.tif 000071
2004530182.tif 000072
2004530182.tif 000073
2004530182.tif 000074
【国際調査報告】
2004530182.tif 000075