The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
LUT 기반 FPGA의 최신 기술 매퍼는 컷 열거를 사용합니다. 좋은 네트워크를 찾기 위해서는 많은 컷이 필요한 경우가 많지만, 크기가 큰 컷을 모두 열거하려면 런타임이 많이 소모됩니다. 기존 알고리즘은 각 노드에 대한 패닌 컷의 데카르트 곱을 계산하는 상향식 병합을 사용합니다. 컷 수는 대부분의 경우 데카르트 곱의 크기보다 훨씬 작습니다. 따라서 기존 알고리즘은 비효율적입니다. 게다가 컷의 크기에 따라 컷 수가 기하급수적으로 증가하므로 실행 시간이 훨씬 길어집니다. 전체 컷이 아닌 부분 컷을 열거하는 여러 알고리즘이 제시되었지만 네트워크 품질을 방해하는 경향이 있습니다. 이 문서에서는 컷을 열거하는 두 가지 알고리즘을 제시합니다. 철저한 열거와 부분 열거. 둘 다 상향식 병합을 사용하지 않기 때문에 효율적입니다. 부분 열거는 최소 깊이 네트워크를 구성할 수 있도록 보장하면서 열거된 컷 수를 줄입니다. 실험 결과는 철저한 열거가 기존 상향식 알고리즘보다 약 5배, 13배 빠르게 실행되는 것을 보여줍니다. K=8, 9이며 동일한 결과를 유지합니다. 반면 부분 열거형은 기존 알고리즘보다 약 9배, 29배 빠르게 실행됩니다. K = 각각 8, 9. 부분 열거에 의해 열거된 컷 세트에 의해 도출된 네트워크의 평균 면적은 모든 컷을 사용하여 도출된 것보다 단지 4% 더 크고 깊이는 동일합니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Taiga TAKATA, Yusuke MATSUNAGA, "Efficient Cut Enumeration Heuristics for Depth-Optimum Technology Mapping for LUT-Based FPGAs" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 12, pp. 3268-3275, December 2009, doi: 10.1587/transfun.E92.A.3268.
Abstract: Recent technology mappers for LUT based FPGAs employ cut enumeration. Although many cuts are often needed to find a good network, enumerating all the cuts with large size consumes a lot of run-time. Existing algorithms employ the bottom-up merging which calculates Cartesian products of the fanins' cuts for each node. The number of cuts is much smaller than the size of the Cartesian products in most cases. Thus, the existing algorithms are inefficient. Furthermore, the number of cuts exponentially increases with the size of cuts, that makes the run-time much longer. Several algorithms to enumerate not all the cuts but partial cuts have been presented, but they tend to disturb the quality of networks. This paper presents two algorithms to enumerate cuts; an exhaustive enumeration and a partial enumeration. Both of them are efficient because they do not employ the bottom-up merging. The partial enumeration reduces the number of enumerated cuts with a guarantee that a depth-minimum network can be constructed. The experimental results show that the exhaustive enumeration runs about 5 and 13 times faster than the existing bottom-up algorithm for K=8, 9 respectively, while keeping the same results. On the other hand, the partial enumeration runs about 9 and 29 times faster than the existing algorithm for K = 8, 9, respectively. The average area of networks derived by the sets of cuts enumerated by the partial enumeration is only 4% larger than that derived with using all the cuts, and the depth is the same.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.3268/_p
부
@ARTICLE{e92-a_12_3268,
author={Taiga TAKATA, Yusuke MATSUNAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Cut Enumeration Heuristics for Depth-Optimum Technology Mapping for LUT-Based FPGAs},
year={2009},
volume={E92-A},
number={12},
pages={3268-3275},
abstract={Recent technology mappers for LUT based FPGAs employ cut enumeration. Although many cuts are often needed to find a good network, enumerating all the cuts with large size consumes a lot of run-time. Existing algorithms employ the bottom-up merging which calculates Cartesian products of the fanins' cuts for each node. The number of cuts is much smaller than the size of the Cartesian products in most cases. Thus, the existing algorithms are inefficient. Furthermore, the number of cuts exponentially increases with the size of cuts, that makes the run-time much longer. Several algorithms to enumerate not all the cuts but partial cuts have been presented, but they tend to disturb the quality of networks. This paper presents two algorithms to enumerate cuts; an exhaustive enumeration and a partial enumeration. Both of them are efficient because they do not employ the bottom-up merging. The partial enumeration reduces the number of enumerated cuts with a guarantee that a depth-minimum network can be constructed. The experimental results show that the exhaustive enumeration runs about 5 and 13 times faster than the existing bottom-up algorithm for K=8, 9 respectively, while keeping the same results. On the other hand, the partial enumeration runs about 9 and 29 times faster than the existing algorithm for K = 8, 9, respectively. The average area of networks derived by the sets of cuts enumerated by the partial enumeration is only 4% larger than that derived with using all the cuts, and the depth is the same.},
keywords={},
doi={10.1587/transfun.E92.A.3268},
ISSN={1745-1337},
month={December},}
부
TY - JOUR
TI - Efficient Cut Enumeration Heuristics for Depth-Optimum Technology Mapping for LUT-Based FPGAs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3268
EP - 3275
AU - Taiga TAKATA
AU - Yusuke MATSUNAGA
PY - 2009
DO - 10.1587/transfun.E92.A.3268
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2009
AB - Recent technology mappers for LUT based FPGAs employ cut enumeration. Although many cuts are often needed to find a good network, enumerating all the cuts with large size consumes a lot of run-time. Existing algorithms employ the bottom-up merging which calculates Cartesian products of the fanins' cuts for each node. The number of cuts is much smaller than the size of the Cartesian products in most cases. Thus, the existing algorithms are inefficient. Furthermore, the number of cuts exponentially increases with the size of cuts, that makes the run-time much longer. Several algorithms to enumerate not all the cuts but partial cuts have been presented, but they tend to disturb the quality of networks. This paper presents two algorithms to enumerate cuts; an exhaustive enumeration and a partial enumeration. Both of them are efficient because they do not employ the bottom-up merging. The partial enumeration reduces the number of enumerated cuts with a guarantee that a depth-minimum network can be constructed. The experimental results show that the exhaustive enumeration runs about 5 and 13 times faster than the existing bottom-up algorithm for K=8, 9 respectively, while keeping the same results. On the other hand, the partial enumeration runs about 9 and 29 times faster than the existing algorithm for K = 8, 9, respectively. The average area of networks derived by the sets of cuts enumerated by the partial enumeration is only 4% larger than that derived with using all the cuts, and the depth is the same.
ER -