連想メモリによるメモリ型並列計算モデルの計算能力

• Item type: Journal(1)
• 公開日: 1992-04-15
• タイトル: 連想メモリによるメモリ型並列計算モデルの計算能力
• タイトル / 言語: en
• タイトル: Computational Power of a Memory - Based Parallel Computation Model with Content Addressable Memory
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 情報数学と情報理論
• 著者所属: 京都大学工学部情報工学科
• 著者所属: 京都大学工学部情報工学科
• 著者所属: 京都大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者名: 武永, 康彦; 高木, 直史; 矢島, 脩三
• 著者名(英): Yasuhiko, Takenaga; Naofumi, Takagi; Shuzo, Yajima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 高度の集積化が可能なメモリに簡単な機能を付加することにより 高度な並列処理を実現できる可能性がある本論文では 連想メモリ(CAM)による並列計算の能力を明らかにするため CAMと同様の記憶データに対する並列部分一致検索機能をもつメモリ型並列計算モデルCAFRAMを提案し その能力について考察するメモリ型並列計算モデルは ランダムアクセス機械に 機能メモリを付加したものであるCAFRAMの機能メモリは 各ワードがアドレスを記憶するインデックス部とデータ部からなり 検索データとマスクデータを与えることにより両者に対してワード並列に部分一致検索を実行できるわれわれはこのモデル上で多項式時間で受理できる集合のクラスが NP問題に対する神託をもつ神託付きチューリング機械により多項式時間で受理できるクラス?^p_2に等しいことを証明したこの結果は われわれが以前に提案したFRAMモデルの場合と同じであり すなわち メモリ型並列計算の本質的な磯能が FRAMのもつ複数のワードヘの並列アクセスにあることを示している
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 33, 号 4, p. 415-422, 発行日 1992-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764