無誤差図形処理の並列剰余計算による高速化

点击翻译按钮获取中文摘要

本研究は理論的に正しい幾何的アルゴリズムをプログラムにしても従来のような暴走を起こすことのないようにする処理を「理論的に可能」から「工学的に実現可能」にすることを目的としていた.そのため,計算誤差なく図形処理できる環境を剰余計算の利用とPCクラスタへの並列実装で実現することが,具体策であった.詳細は次の要素技術の開発と実現である:(1)剰余計算とその並列化の理論,(2)剰余計算下での符号判定と並列化の理論,(3)PCクラスタの実現,(4)並列化の理論のPCクラスタ上への実装.それぞれについて成果をみる:(1)は理論的困難もなく達成できた.(2)は整数計算を行うところで実数計算をして高速化する予定が,予想外に誤差に敏感なため,ある程度の高速化に留まった.(3)はOSにLinux,ライブラリにMPIという組合せで,当初PCクラスタの実現は容易だったが,高速化のための通信性能強化で難航し予想性能がまだ出ていない.(4)は実装し,実験で図形処理を実現できたが,予想に反し1台で処理するのに較べて相当に遅くなった.主因が通信性能が予定の数分の一しかないことを突き止めたところである.全体をまとめると,理論研究は実装できる段階に達し,実現も,予想する高速性からは遠いものの,実際にPCクラスタ上に実装し,幾何的アルゴリズムを誤差なし図形処理として実現できた.研究成果は応用数理学会の年会と情報処理学会のアルゴリズム研究会で発表し,一定の評価を得た.残された問題として,理論では符号判定の高速化,実現では通信の高速化があげられる.符号判定は補償アルゴリズムにより実数計算の誤差を減らし一層の高速化を図り,実現ではOSの設定調整によるソフト面で高速化(数倍)を企画している.これらにより,当初予想に近い高速性を確保できると考える.また,予算の手当がつけば,より高速な通信ハードの導入による高速化(数十倍)もしたい.