Computational Complexity Map of the Set Bin-Packing Problem

概要

論文の詳細を見る
One approach to the technology mapping problem of LUT-based FPGAs is to extract a two-level subcircuit and map it into as few LUTs, traversing from primary inputs to primary outputs. See Fig. 1. The mapping problem of a two-level circuit into LUTs can be formulated as the Set Bin-Packing(which has been called as the Cube-Packing in,).[figure]Set Bin-Packing(SBP)Instance:A finite set S, a set G of subsets of S, and positive integers k and K.Question:Is there any partition II of G such that|II|≤ K and|∪_<g∈π>g|≤k for each π∈II? Note that S,G,k,and K correspond to a set of input signals, a set of gates, the number of inputs of an LUT, and the number of LUTs in an FPGA, respectively.The LUT capacity is the number of inputs of an LUT.The gate size is the number of inputs of a gate. The fanout of an input signal is the number of gates to which the signal connects. SBP is a variant of the well-known Bin-Packing (BP) in which an object to be packed is an item with scalar size instead of a set. To the authors' knowledge, there have been few results for SBP except concerning about BP. This paper is a brief introduction of our results most of which have not been published so far.
社団法人電子情報通信学会の論文
1995-03-27