| 題名 | 自律負荷分散方式におけるノード情報の制限と局所的タスク投入による影響 |
| 著者 | *合田 卓矢, 樋上 喜信, 小林 真也 (愛媛大学大学院理工学研究科) |
| Page | pp. 811 - 817 |
| Keyword | 負荷分散, マルチコンピューティング |
| Abstract | ワークステーションなどの低価格な計算機の出現と、ネットワーク技術の進歩によりホストコンピュータによる集中型のシステムに変わり、計算機がネットワークで相互に接続された分散型のシステムが普及している。分散型のシステムは計算機資源の完全な共有化は不可能であるが、低価格でコストパフォーマンスに優れ、耐故障性・拡張性を持つという利点がある。OSとして、マルチユーザ、マルチタスク型のUNIXが使われるケースが多く、同一計算機上で複数のユーザが複数のタスクを処理したり、あるユーザが複数の計算機を同時利用することが可能である。 UNIXのようなマルチユーザ、マルチタスク型のOSを用いた分散型のシステムでは、ある計算機に複数のタスクが投入されたり、シミュレーションやコンパイルなどのような処理時間の大きいタスクが実行された場合、特定の計算機に負荷が集中しタスクの応答時間が遅くなるといった問題がある。この様な負荷の不均衡な状況では計算機資源の有効利用が行われず、システムの運用上好ましくない。そこで高負荷な計算機から低負荷な計算機へタスクを転送し、実行することによってタスクの応答時間を短縮させる必要がある。しかし、ユーザが各計算機の負荷が動的に変化する状況を把握して、適宜にタスクを分散させることは困難である。従って、各計算機が自律的に負荷を分散させ、資源の有効利用や応答時間の短縮を行う負荷分散方式が求められる。 このような背景のもと、我々の研究室では負荷分散方式の一つとして、自律負荷分散方式（Autonomous Load Distributing Algorithm）を提案している。自律負荷分散方式とは、タスクを投入された計算機が他の計算機と１対１通信を用いてタスクの実行依頼とその諾否からなる交渉を行い、受諾した計算機がさらに交渉を行うといった動作の繰り返しで実行計算機を決定する方式である。これまでの研究により自律負荷分散方式はマルチコンピュータ環境において有効な負荷分散方式であることが示されている。 自律負荷分散方式では、ノード間で交渉を行う際に互いの持つ情報を交換し合うことで新たな情報を獲得する。このため、各ノードがシステム全体の情報を持つ必要がないという特徴を持つが、大規模な環境では交渉を繰り返すことで、情報量が単調に増加してしまう。そこで、各ノードが所持できるノード情報量を制限し、それを越えるような場合、ノード情報を削除する方法を提案している。また、ノード情報は獲得してから時間がたつと情報の信頼度が低下するため、ノード情報には信頼性有効期限を設定し、期限内情報のノードと優先的に交渉することで適切な依頼判断が行えると考えられる。 ノード情報を削除することは、情報量が単調に増加することを抑えることができるが、ノード間のつながりが解消されることになる。システムに均一にタスクが投入される場合には、ノード情報の制限が負荷分散動作に支障を起こさないが、局所的にタスクが投入される状況においては、タスク投入ノードから非投入ノードへの単方向の関係を途切れさせる傾向となり、タスク投入ノードから非投入ノードへ依頼を行うことが不可能な状況に陥る。このとき、低負荷な非投入ノードが存在するにもかかわらず、タスク投入ノード間でのみ負荷分散が行われてしまう。これは以下の理由であると考えられる。タスクが投入されたノードは自ら交渉を行うことができるが、非投入ノードは依頼が来て初めて交渉に参加することができるため、投入ノードの方が交渉回数が多いといえる。そのため、投入ノード同士が頻繁に交渉し合ってしまう傾向となり、非投入ノードの存在を知る機会が少なくなってしまい、信頼性有効期限が過ぎた非投入ノードの情報が優先的に削除されてしまう。このことを理由として、投入ノードから非投入ノードへのつながり関係が途切れ、適切に負荷が分散されない状態になると考えられる。そこで、この問題に対する対処法として、信頼性有効期限が過ぎたノード情報は削除対象とはせずに、負荷の高いノード情報のみを削除する方法を提案した。 従来法と提案法との比較を行った結果、時間経過とともに投入ノードから非投入ノードへのつながり関係が途切れることはなく、非投入ノードにも負荷が分散し、適切に負荷分散が行われることが確認できた。提案法は若干の平均交渉回数の増加と、平均交渉成功率の低下が見られたが、大幅に平均応答時間が改善されたため、提案法は有効な方法であることが明らかとなった。 |
| 題名 | 自律負荷分散方式におけるノード情報とその信頼性 |
| 著者 | *工藤 路比古, 樋上 喜信, 小林 真也 (愛媛大学大学院理工学研究科) |
| Page | pp. 818 - 821 |
| Keyword | マルチコンピュータ環境, 負荷分散, ノード情報, 信頼性 |
| 題名 | 野菜類の産地判別システムにおける効率的な産地判別対象の絞込み |
| 著者 | *佐藤 永欣 (岩手県立大学ソフトウェア情報学部), 上原 稔 (東洋大学情報工学科), 下村 講一郎, 山本 浩文, 上條 賢一 (東洋大学植物機能研究センター) |
| Page | pp. 822 - 828 |
| Keyword | 微量元素含有量による産地判別, 類似密ベクトルの効率的な検索 |
| Abstract | 近年、日本では農産地のブランド化が進み、産地により農産物に価格差がでている。 このため、農産物の産地偽装事件が多発した。この問題を解決するため食品 トレーサビリティシステムが導入され、一部で運用されている。 しかし、食品トレーサビリティシステムはバーコードやRFIDなどの形で 人工的に付加したIDを追跡しているため、ID偽造、パッケージ偽造、 中身のすり替えなどの可能性があり、実際に事件が起きている。 そこで我々は、育った土地の違いによる野菜類の微量元素含有量の違いを 利用した産地判別システムの開発を進めている。 本システムは農家からの出荷時に野菜類の微量元素含有量を測定、 データベースに蓄積し、産地偽装が疑われる野菜類が発見された場合、 微量元素含有量を比較し、真の産地を推定する。本システムは、 産地が一致するかどうかを相関係数が適当な閾値を超えるかを基準として判断する。 データベース中の全データとの相関係数の計算が必要であるが、 データ数に対してスケーラビリティが不足している。本論文では、 相関係数の計算対象となるデータをあらかじめ限定し、スケーラビリティを 確保する手法を提案する。 以前われわれが用いていたSimilarity Preserve Hash (SPH)による絞込みは、 SPHの値を一つ計算するために、浮動小数点演算をSPHのビット幅だけ繰り返す 必要があり、高速化には限界があった。絞込みの計算を高速化するためには、 整数演算のみ、データ1件に対して1回の演算で絞込みができるとよい。 一般的に、疎なベクトルにおいては、データ投入、取り出し、空間の利用効率、 データ取出し時の再現率の各点において効率的な手法が知られているが、 密なベクトルの検索・絞込みではこれらを全て同時に満たす手法は 知られていない。以下では、空間の利用効率と再現率を犠牲にすることにより、 データ取り出し時と格納時の所要時間を短縮する手法を述べる。 まず、微量元素含有量そのものについて検討する。各産地を総合した微量元素 含有量は、ある元素について、正規分布か、その変種の分布を持つと考えられる。 負の含有量は考えられないため、左側のすそが切れているかもしれない。 各産地、または農家での、特定の微量元素の含有量も正規分布かその変種に従い、 なおかつ比較的類似した値を持つと考えられる。これらの模式図をFig. 2に示す。 これらの特徴から、産地dのh番目の野菜類のサンプルの元素Aの測定値x_{Adh}が、 A全体の分布のどのあたりの位置を示すかを用いて分類する手法が考えられる。 x_{Adh}全体の平均を、標準偏差をS_Aとする。x_{Adh}は以下のように基準化できる。 基準化したy_{Adh}はx_{Adh}が正規分布に従う場合、標準正規分布に従う。 y_{Adh} = (x_{Adh} - average(x_A)) / s_A y_{Adh}の範囲-∞<=y_{Adh}<=∞を、y_{Adh}が区間gに分類 される確率は全て等しくなるようにb個の区間に分割する。それらを下から順に g (g = 1, 2, 3, …, b)と名前をつける。標準正規分布をg等分する パーセント点を計算し、yAdhとの大小を比較するだけでよい。 同じ圃場で収穫された野菜類のある元素の含有量が、二つまたは それ以上の区間に跨って分類される可能性がある。 すなわち、クエリQの元素Aの含有量Q_Aが与えられたとき、その分類g_{QA}の前後lの 区間g_{QA}±lにも、高い相関係数を持つ微量元素含有量データが存在する 可能性があり、これらが産地判別の対象からもれると、正しい結果が得られない。 次に、分類区間を効率的にコード化する手法を述べる。この手法は浮動小数点 演算命令を使わずに、1回の演算でデータベース中の一つの微量元素含有量 データが、相関係数の計算対象になるかどうか、すなわち、1に近い相関係数を 持つかどうかを判定する。まず、元素Aのためのコード空間をbビット幅取る。 ビット列b_b…b_2b_1で元素Aの分類区間を表現し、全ての元素のためのコードを 連結して特定のサンプルの微量元素含有量のおおよその値を表現する。 元素Aの含有量が区間gに分類されたとき、該当するビットbgを１にし、 それ以外を0にする。g_{QA}±lの範囲に分類されている微量元素含有量全てを 検索する場合、該当するビットを全て1にして検索すればよい。 産地判別にe種類の元素を使い、それぞれがｂ区間に分類されるとき、 微量元素含有量全体はe×bビットあれば表現可能である。これがこの演算を行う 計算機の主要なレジスタのビット幅以下であれば、データベース中の1件の 微量元素含有量データを、相関係数の計算対象とするかどうか判断するのに 1回の整数演算のみで済む。 SPHの評価に用いたのと全く同じ、シミュレーションにより生成した10万件の 微量元素含有量データに対して、微量元素含有量の区間への分割と その結果のコード化、結果のデータベースへの格納を行ったときの実行時間を 評価したところ、8分程度であり、10万件に対する実行時間としては十分であった。 産地判別を行うために、相関係数の計算対象を提案手法により絞り込むための 所要時間を測定したところ、ほぼ1秒弱であった。隣接区間からも絞り込んだ 場合のほうが若干長い。これは対象となるデータ数が多いためと考えられる。 以前用いていたSPHによる絞込みでは概ね3秒強であったので、十分な高速化を 実現できた。 |
| 題名 | アプリケーションレベル分散セキュアグループのためのChinese-Wall型プロセス隔離手法 |
| 著者 | *勝野 恭治, 渡邊 裕治, 古市 実裕, 工藤 道治 (日本アイ・ビー・エム（株）東京基礎研究所) |
| Page | pp. 829 - 839 |
| Keyword | Chinese-Wallポリシー, プログラムリファレンスモニター, プロセス隔離, 強制アクセス制御, 情報フロー制御 |
| Abstract | 分散セキュアグループは、分散したノード上のコンポーネント間で構築したグループに対してセキュリティポリシーを強制適応できる分散コンピューティングプラットフォームである。現在提案されているプロトタイプの主流はコンポーネント間の強固な隔離を実現するために仮想マシンモニタが用いられているため、アプリケーションの運用や管理が複雑になり、利便性が低下する恐れがある。そこで、プログラムリファレンスモニタを用いて利便性への影響を軽減するアプリケーションレベル分散セキュアグループが期待されている。さらに既存環境への影響を最小限に抑えるために、既存OSやアプリケーションのコードを変更しない実現方法が望ましい。 本論文では、既存環境への影響を最小限に抑えたアプリケーションレベル分散セキュアグループを実現する、Chinese-Wallポリシーの概念を利用したプロセス隔離手法CWPC（Chinese-Wall Process Confinement）を提案する。CWPCは既存OSやアプリケーションのコードを変更しないで実現するため既存環境への影響を最小限に抑えることができる。さらに本論文では、既存環境に対する変更を最小限に抑えられることを示すために、幅広く用いられているMicrosoft Windows環境、及びその上で頻繁に利用されるオフィスアプリケーションを検証対象として、ドキュメントの安全な取り扱いを実現するプロトタイプシステムを実装し、性能評価を通して、本論文のアプローチが実用的であることを示す。 |