超並列アルゴリズム設計のためのデータ構造と計算モデルに関する研究

大规模并行算法设计的数据结构和计算模型研究

• 批准号: 04235207
• 负责人: 安浦 寛人
• 金额: $ 1.6万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 1992
• 资助国家: 日本
• 起止时间: 1992 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-04235207/
• 关键词: 超並列アルゴリズム; 並列計算モデル; 局所計算可能な符号化; 機能メモリ型並列処理; レイトレーシング

超並列処理においては,数万から数百個のプロセッサ上で動作する超並列アルゴリズムの設計技法の確立が大きな問題である.逐次処理のアルゴリズム設計においては,データ構造の工夫が効率的なアルゴリズム設計に大きく影響することが良く知られているが,並列アルゴリズム設計においても,データ構造の重要性は当然認識されるべきものである.しかし,これまでに数百万個のプロセッサ上で動作する超並列アルゴリズムを対象としたデータ構造の設計論はほとんど研究されていない.本研究では,超並列処理のアルゴリズム設計に対する設算モデルを確立し,その上でデータ構造の設計原理を明確化することを目指している.特に,プロセッサ間の通信量の制約を考慮して,通信量を限定した処理適した「局所計算可能なデータ構造」の確立を目指す.本年度の研究としては,1)種々の並列計算モデルの整理:並列アルゴリズムや並列計算モデルの理論的な研究と現実の並列計算機アーキテクチャの研究との整合性と隔たりについて整理した.2)局所計算可能な符号化に関する理論的な研究:複数の単項演算が定義された有限集合に対し,すべての単項演算を局所計算可能とするための符号化の符号長について研究し,局所計算可能な関数の数を数え上げ,符号長の下界を与えた.3)機能メモリ型並列処理におけるレイトレーシングの並列処理アルゴリズム開発:コンピュータグラフィックスの画像生成アルゴリズムであるレイトレーシングの交差判定処理を機能メモリ型並列処理で行なう手法として,オブジェクト並列と視線並列とよぶ2種のアルゴリズムを考案し,処理速度および必要なハードウェア量を評価した.以上のように,本年度の研究では,並列計算モデルと並列アルゴリズムの関係を整理し,また,局所的に計算できるデータ構造の構成理論の基礎研究並びに実用的な問題としてレイトレーシングについて研究を行なった.

The design technique of super-parallel processing is established by tens of thousands or hundreds of super-parallel processing operations. The design process of the multi-layer structure is gradually changed, and the time and efficiency of the multi-layer structure design are greatly influenced. The design theory and research of the structure of the image and the action of millions of pieces of paper on the surface of the image are discussed. This study aims to establish the design parameters of the super-parallel processing and clarify the design principles of the super-parallel processing. In particular, traffic constraints between servers are taken into account, traffic constraints are addressed appropriately, and the establishment of "local computing possibilities" is indicated. This year's research includes: 1) Parallel computation, sorting: Parallel computation, theoretical research: Parallel computation, sorting: Parallel computation, sorting: The definition of complex single term calculus is based on finite sets, and the symbolic length of complex single term calculus is studied. The number of possible correlations calculated by complex single term calculus is calculated. The lower bound of the symbol length is equal to.3) The function of the parallel processing: The image generation of the image of The processing speed is too high to be evaluated. This year's research is focused on parallel computation, the relationship between parallel computation and structure, the fundamental research of structure theory and its application.

项目成果

安浦 寛人: "並列計算機と並列計算モデル" 情報処理. 33. 1024-1032 (1992)

Hiroto Yasuura：“并行计算机和并行计算模型”信息处理。33. 1024-1032 (1992)

山田 哲也,安浦 寛人: "FMPPによるレイトレーシングの高速化手法について" 情報処理学会研究報告ARC97-14. 105-112 (1992)

Tetsuya Yamada、Hiroto Yasuura：“关于使用 FMPP 加速光线追踪的方法”日本信息处理协会研究报告 ARC97-14 (1992)。