ビンの容量を制限したキューブパッキング問題のNP完全性について

  • Izumi Tomonori
    Department of Electrical and Electronic Engineering,Tokyo Institute of Technology
  • Yokomaru Toshihiko
    Department of Electrical and Electronic Engineering,Tokyo Institute of Technology
  • Takahashi Atsushi
    Department of Electrical and Electronic Engineering,Tokyo Institute of Technology
  • Kajitani Yoji
    School of Science,Japan Advanced Institute of Science and Technology

Bibliographic Information

Other Title
  • Cube-Packing Problem with Fixed Bin-Capacity(≧3)is NP-complete

Search this article

Description

Look Up Table(LUT)ベースのFPGAのテクノロジーマッピングにおいて,2段部分回路のLUTへの割り当てはキャーブパッキング問題として定式化できる.共通信号線の効果を考慮しない場合にはビンパッキング問題として定式化でき,LUTの入力線数を現実的な値に限ると高速に最適解を求めることができる.本論文ではLUTの入力線数を固定した場合のキューブパッキング問題の計算複雑度を考察し,NP完全であることを証明する.
In technology mapping of Look Up Table(LUT)based FPGA,the problem of mapping a two-level subcircuit into LUTs is formulated as the Cube-Packing problem.Without taking account of the advantage of a signal to multiple gates,it is formulated as the Bin-Packing problem.If the number of inputs of LUTs is limited to a practical value,the Bin-Packing problem can be solved optimally very fast.In this paper,we consider the computational complexity of the Cube-Packing in the case that the number of inputs of LUTs is fixed,and prove the problem to be NP-complete.

Journal

  • Technical report of IEICE. FTS

    Technical report of IEICE. FTS 94 (313), 1-6, 1994-10-27

    The Institute of Electronics, Information and Communication Engineers

Keywords

Details 詳細情報について

  • CRID
    1572543027237806592
  • NII Article ID
    110003194271
  • NII Book ID
    AN10012998
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top