メモリ型並列計算モデルとその計算能カ　－スーパコンピュータへの第3のアブローチ－

情報処理学会 被引用文献3件

書誌事項

タイトル別名
  • A Memory - Type Parallel Computation Model and Its Computation Power -Yet Another Approach to Supercomputing-
  • 基礎理論

この論文をさがす

抄録

高い集積度の得られるメモリに若干の機能を付加した並列計算機構を考え これを並列計算モデルとして形式化し その計算能力を明らかにすることは 実用的にも 理論的にも興味深くかつ重要であると考えられる.本論文では スーパコンピュータヘの新しいアプローチとして メモリ型並列計算モデルFRAMを提案し その計算能力について考察する.FRAMは 通常の逐次計算機のモデルであるランダムアクセス機械に アドレスの部分一致による複数のメモリセへの並列アクセスが可能な機能メモリを付加したものである.FRAMにおいて多項式時間で解くことのできる問題のクラスは NP問題に対する神託(オラクル)を持つ神託付きチューリング機械により多項式時間で解くことのできる問題のクラスに等しい.したがって 工学の種々の分野においてしばしば現れ 逐次計算機で多項式時間で解くことは不可能であろうと考えられている組合せ問題や組合せ最適化問題の多くを FRAM によって多項式時間で解くことができる.FRAMは実現性が高く 実用的に興味深いばかりでなく 新しい並列計算モデルとして 理論的にも興味深い.

収録刊行物

被引用文献 (3)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1050845762819193856
  • NII論文ID
    110002724673
  • NII書誌ID
    AN00116647
  • ISSN
    18827764
  • Web Site
    http://id.nii.ac.jp/1001/00014940/
  • 本文言語コード
    ja
  • 資料種別
    journal article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ