平成１４年度第３回KSMAP

日時：１２月１３日（金）　１５：００ 〜 １８：００ 

場所：京都大学工学部8号館 共同5号室

       会場への案内  

  「入力依存専用回路による超高速計算」
    中野 浩嗣 （北陸先端科学技術大学院大学） 講演要旨

  「ある制約式充足問題の解法について」
    渡辺 治 （東京工業大学）講演要旨

回路データをダウンロードすることにより，任意のハードウェアを実現 できるFPGAが大容量・高速・低価格化してきており，ASICの安価な代替 として使われるようになってきた．任意のハードウェアを何度でも書き 換えることができるというFPGAの特徴を利用した超高速計算法について， いくつかの具体例を挙げ説明する．基本的なアイデアは，問題の入力が 与えられたときに，入力の一部に依存した，その問題を解くための入力 依存専用回路を自動生成し，FPGAにダウンロードして，高速に問題を 解くものである．ASICの単なる代替としてではない，FPGAの新たな利用 法である．

制約式充足問題のランダム局所探索アルゴリズムの解析手法の 研究の一例として，線形符号 LDPCC の復号問を取り上げ，その ランダム局所探索アルゴリズムについての我々の解析を報告す る．どのような条件の元に，なぜ，ランダム局所探索アルゴリ ズムがうまく働くのか（あるいは働かないのか）についての 解析結果について述べる．