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

通过并行余数计算加速无差错图形处理

• 批准号: 13750062
• 负责人: 今井 敏行
• 金额: $ 1.34万
• 依托单位: Wakayama University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13750062/
• 关键词: 計算幾何学; 並列処理; 無誤差計算; 剰余計算

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

This study focuses on the theoretical possibility and engineering realization possibility. The calculation error is processed by the environment and the surplus calculation is realized by the PC server and the parallel installation. The development and implementation of the key element technology in detail are as follows:(1) theory of parallelism in residual calculation,(2) theory of symbol determination and parallelism in residual calculation,(3) implementation of PC classification,(4) implementation of PC classification on parallelism theory. (1) The difficulty of opposing theory is not achieved. (2)integer calculation, calculation speed, calculation speed (3)OS, Linux, MPI and combination, the original PC is easy to implement, high-speed communication performance enhancement is difficult to navigate, performance is difficult to achieve. (4)In the end, the shape of the processing is realized, and it is expected that the processing will be completed in one unit. The main reason is that the communication performance is predetermined. All of these theoretical studies have been carried out at different stages, and the results have been realized. The high speed of the computer is expected to be far away. In practice, the computer is installed at the top of the computer, and the geometric error is handled at different stages. The research results were presented at the annual meetings of the Society for Applied Mathematics and the Society for Information Processing. In theory, symbol determination is speeded up, but in practice, communication is speeded up. Symbol decision compensation is the error reduction of the calculation of the number of layers of high speed, the realization of the OS setting adjustment is the soft surface of high speed (several times) is planned. This is the first time I've ever wanted to get close to speed. In addition, it is expected that there will be no delay in the calculation of the manual, and the introduction of high-speed communication will be speeded up (dozens of times).

项目成果

今井敏行: "並列剰余計算を利用した高精度図形処理の実現"日本応用数理学会年会講演予稿集(電子ジャーナル). (2002)

今井俊行：“利用并行余数计算实现高精度图形处理”日本应用数学学会年会论文集（电子期刊）（2002）。

今井敏行: "剰余計算の並列化による誤差なし図形処理とその実装"情報処理学会アルゴリズム研究会研究報告. 2003-AL-89. 41-48 (2003)

Toshiyuki Imai：“无错误图形处理及其通过并行余数计算的实现”日本信息处理学会算法研究小组研究报告 2003-AL-89 (2003)。

今井 敏行: "高精度図形処理を指向した剰余計算の利用法"日本応用数理学会2001年度年会講演予稿集. 104-105 (2001)

Toshiyuki Imai：“利用余数计算进行高精度图形处理”日本应用数学学会2001年年会记录104-105（2001）。