著者

横丸 敏彦 泉 知論 高橋 篤司 梶谷 洋司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM)

巻号頁・発行日

vol.1995, no.72, pp.1-8, 1995-07-20

---

LUTをベースとしたFPGAのテクノロジーマッピングに登場する,2段部分論理回路を最小数のLUTに割り当てる問題は,共通信号線を考慮しない場合,整数ビンパッキング問題となる.整数ビンパッキング問題ではビンの容量を固定した場合,全探索アルゴリズムにより多項式時間で最適解が求まることがよく知られているが,実用性に欠ける.本文では,整数ビンパッキング問題の高速近似アルゴリズムであるFFD法が容量を6以下に固定した時に最適解を求めることを示す.また,入力を制限することにより,容量を7および8に固定した時にFFD法が最適解を与えることを示し,容量を8以下に固定した場合に高速に最適解を求める多項式時間アルゴリズムを提案する.In technology mapping of Look Up Table (LUT) based FPGA, the problem of mapping a two-level subcircuit into LUTs is formulated as the Integer Bin Packing Problem without taking account of the advantage of input signals connected to more than one gate. It is known that Integer Bin Packig Problem can be solved in polynomial time by exhaustive search when the size of bins is fixed, however, which is not practical. In this paper, we show that First Fit Decreasing (FFD) which is a fast approximation algorithm solves Integer Bin Packing Problem when the size of bins is fixed to less than or equal to 6. We show that FFD gives optimal solutions for some class of instances when the size of bins is fixed to 7 or 8, and suggest a polynomial time algorithm which solves fast when the size of bins is fixed to less than or equal to 8.