[논문]해밍거리가 3인 큐브를 활용한 공통식 추출

권오형

해밍거리가 3인 큐브를 활용한 공통식 추출
Common Logic Extraction Using Hamming Distance 3 Cubes 원문보기

컴퓨터교육학회논문지 = The Journal of Korean Association of Computer Education, v.20 no.4, 2017년, pp.77 - 84

초록
AI-Helper

논리회로 심화학습에 사용할 수 있는 논리식 간략화 도구로 활용하고 더 나아가 반도체 부품 최적화를 위한 설계자동화 도구로 활용할 수 있는 도구를 제안한 것이다. 본 논문에서 제시하는 논리식 간략화 방법은 여러 논리식에 존재하는 공통부분을 찾아 반복 사용을 줄이는 것이다. 최종적으로 전체 논리식에 사용된 리터럴 개수를 최소화하는 것을 목표로 한다. 이 전의 연구들이 나눗셈 원리를 이용해서 공통식을 찾았기 때문에 논리식에 내재한 공통식을 산출하는 데는 실패하였다. 본 논문에서 제안하는 방법은 논리식들 사이에 내재된 공통식을 찾도록 해밍거리가 3인 큐브들을 이용하였다. 벤치마크 회로를 이용한 실험을 통해 타 방법들과 간략화 정도를 비교했을 때, 제안한 방법으로 최대 47% 정도의 리터럴 개수를 줄이는 효과를 보였다.

Abstract ▼ AI-Helper

This paper proposes a tool that can be used as a logical expression simplification tool that can be used for deepening learning of logic circuits and further utilized as a design automation tool for optimizing semiconductor parts. The simplification method of logical expressions proposed in this paper is to find common subexpressions existing in various logical expressions and reduce the repetitive use. Finally, the goal is to minimize the number of literals used in all logical expressions. These previous studies failed to produce a common subexpression embedded in the logical expressions because they only use division principle. The proposed method uses cubes with a Hamming distance of 3 to find the common subexpression embedded between logical expressions. Experiments using benchmark circuits show that the proposed method reduces the number of literals by as much as 47% when comparing simplifications with other methods.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 선험 방법(heuristic method)으로 공통식을 찾아 논리식을 간략화 하는 방법을 제안한 것이다. 논리식 또는 출력 별로 해밍거리가 3인 큐브들을 선택해서 공통식이 될 수 있는 후보군을 늘리는 것이 본 논문의 핵심이다. 각 논리식 별로 후보군이 많으면 공통식을 찾을 가능성이 높기 때문이다.
본 논문에서 제안하는 논리식 간략화의 목표는 AND, OR, NOT 연산자만을 사용 하고 전체 논리식에 사용된 리터럴 개수를 최소화하는 것이다. 논리식을 CMOS 트랜지스터 회로로 전환했을 때 트랜지스터의 개수는 논리식에 사용된 리터럴 개수의 2배가 되기 때문에 리터럴 개수를 줄이는데 목표를 둔다.
논리회로 심화학습을 위한 설계자동화 도구를 제안한 것으로 여러 논리식에 존재하는 공통부분을 찾고, 공통부분이 반복 사용되지 않도록 하여 전체 논리식을 간략화 하는 방법을 보인 것이다. 간략화 결과는 전체 논리식에 사용된 리터럴 개수를 최소화하도록 고안하였다.
산출된 논리식이 최종회로나 칩의 크기에 많은 영향을 미친다. 따라서 많은 연구자들이 최적 논리식 또는 논리회로를 산출하기 위한 논리합성 도구를 만들기 위해 연구를 진행하고 있다. 특히 여러 개의 출력들이 있는 논리회로를 설계하고자 할 경우, 여러 출력에서 공통으로 사용된 논리식을 한 번만 사용해서 전체 논리식을 간략화 하는 것은 회로 간략화에 매우 중요한 과정이다.
반면에 임의의 해밍거리 n의 큐브들로부터 후보식들을 찾고, 다시 해밍거리 n-1의 큐브들로부터 후보식을 찾는 방법으로 해밍거리를 줄여가면서 후보식들을 찾는 경우에는 수행시간이 늘어나게 된다. 따라서 본 논문은 큐브들 사이에 해밍거리가 3인 경우로 한정하고 공통식을 산출하는 방법을 제안한다.
각 논리식 별로 후보군이 많으면 공통식을 찾을 가능성이 높기 때문이다. 본 논문에서 제안하는 논리식 간략화의 목표는 AND, OR, NOT 연산자만을 사용 하고 전체 논리식에 사용된 리터럴 개수를 최소화하는 것이다. 논리식을 CMOS 트랜지스터 회로로 전환했을 때 트랜지스터의 개수는 논리식에 사용된 리터럴 개수의 2배가 되기 때문에 리터럴 개수를 줄이는데 목표를 둔다.
그러나 카르노맵을 이용한 방법은 입력 변수가 6개 이하인 경우 진리표를 입력으로 2단의 단순식을 수작업에 의해 산출하게 고안된 것이다. 본 논문은 논리회로 심화학습 과정에서 논리회로 간략화를 자동화하는 도구로 활용하고, 더 나아가 반도체 부품 개발 도구로 활용하기 위한 실용적 방법을 제안한 것이다.
본 논문은 선험 방법(heuristic method)으로 공통식을 찾아 논리식을 간략화 하는 방법을 제안한 것이다. 논리식 또는 출력 별로 해밍거리가 3인 큐브들을 선택해서 공통식이 될 수 있는 후보군을 늘리는 것이 본 논문의 핵심이다.
본 논문을 서술하는데 필요한 용어들과 관련 연구들에 대하여 기술한다. 관련 연구 중에서 대수 나눗셈 방법과 커널 방법에 의한 공통식 추출 방법은 본 연구 결과와 비교를 할 것이기 때문에 보다 별도의 절로 구분해서 자세히 서술한다.
이들 중에서 전체 논리식의 리터럴 개수를 가장 많이 줄일 수 있는 공통식을 선택하는 것이 중요하다. 본 절에서는 3개 이상 큐브로 구성된 후보식 산출 방법, 후보식들에서 공통식을 추출하는 방법, 그리고, 여러 공 통식 중에서 리터럴 개수를 가장 많이 줄일 수 있는 공통식을 선택하는 방법에 대하여 기술한다.
대수 나눗셈을 이용한 공통식 산출 방법 중의 하나가 커널을 이용한 것이다. 커널을 이용한 방법이 널리 알려져 있고, 본 논문에서 제안하는 방법과 비교할 것이 때문에 본 절에서 자세히 소개한다.

가설 설정

정의 3: 서포트 집합이 동일한 2개의 C_i 와 C_j 큐브 사이에 해밍거리(Hamming Distance)는 2개의 큐브에서 차이가 나는 리터럴의 개수가 된다. 큐브 C_i 와 C_j에 대한 해밍거리는 HD(C_I, C_j)로 표현한다.

제안 방법

2장에서는 본 논문 서술에 필요한 배경 지식인 정의와 관련 연구를 소개하고, 또한 커널을 이용한 공통식 추출 방법에 대하여 서술한다. 3장에서 본 논문에서 제시하는 해밍거리 3인 큐브들을 이용해서 공통식 추출 방안을 제시한다. 4장에서 실험결과를 보이고, 5장에서 결론을 제시한다.
논리회로 심화학습을 위한 설계자동화 도구를 제안한 것으로 여러 논리식에 존재하는 공통부분을 찾고, 공통부분이 반복 사용되지 않도록 하여 전체 논리식을 간략화 하는 방법을 보인 것이다. 간략화 결과는 전체 논리식에 사용된 리터럴 개수를 최소화하도록 고안하였다. 출력수가 2개 이상의 논리회로에서 공통식을 산출해서 각 출력에 서 공통으로 사용된 부분을 새로운 변수로 대치하여 논리식을 간략화하는 공통식 추출방법을 제안하였다.
본 논문에서 해밍거리가 3인 큐브들을 공통식 산출에 선정한 이유에 대해 먼저 설명하고 다음 해밍거리가 3인 큐브로부터 공통식을 산출하는 방법에 대하여 서술한다.
{ {α, b′}, {b,c} }는 단순식이다. 본 논문에서는 큐브와 단순식을 표현하는 경우 집합 표기와 보편적으로 사용되는 논리식 표기를 모두 사용한다. 따라서 큐브 {α, b}는 ab와 동일한 표현이며, { {α, b′}, {b,c} }는 αb′+bc와 동일한 표현이다.
3GHz i3 CPU가 장착된 PC에서 제안한 방법을 C언어로 작성하였다. 실험 은 Microelectronics Center of North Carolina(MCNC) 벤치마크 회로[12] 일부를 대상으로 제안한 방법과 타 방법들의 수행 결과인 리터럴 개수와 수행시간을 기준으로 비교하였다. 이유는 본 논문에서 제안한 방법이 선험 알고리즘이기 때문에 시간 복잡도 산출대신 벤치마크 회로를 대상으로 알고리즘 수행결과를 비교한 것이 다.
출력수가 2개 이상의 논리회로에서 공통식을 산출해서 각 출력에 서 공통으로 사용된 부분을 새로운 변수로 대치하여 논리식을 간략화하는 공통식 추출방법을 제안하였다. 제안한 방법은 각 논리식 또는 출력별로 해밍거리가 3인 큐브들을 이용해서 주어진 논리식 변형을 통해 보다 많은 공통식이 될 수 있는 후보식을 산출하는 것이다. 실험 결과 수행시간은 타 방법들에 비해 상대적으로 늘어났지만, 리터럴 개수를 줄이는 데 효과적임을 보였다.
간략화 결과는 전체 논리식에 사용된 리터럴 개수를 최소화하도록 고안하였다. 출력수가 2개 이상의 논리회로에서 공통식을 산출해서 각 출력에 서 공통으로 사용된 부분을 새로운 변수로 대치하여 논리식을 간략화하는 공통식 추출방법을 제안하였다. 제안한 방법은 각 논리식 또는 출력별로 해밍거리가 3인 큐브들을 이용해서 주어진 논리식 변형을 통해 보다 많은 공통식이 될 수 있는 후보식을 산출하는 것이다.
해밍거리 3인 큐브들로부터 여러 출력에서 사용되는 공통식이 될 수 있는 후보식들을 찾는 방법과 이를 이용해서 간략화된 논리식을 산출하는 알고리즘에 대하여 제시한다.

이론/모형

알고리즘 1은 후보식 집합 L에 대응하는 새로운 식 IF(L)를 만들고, IF(L)에서 제수들을 찾으면 바로 이것이 후보식들의 교집합이다. 교집합 산출 방법은 MIS에서 제안한 방법을 그대로 사용 한다. IF(L)를 만들 때, 후보식들을 구성하는 큐브들을 새로운 변수로 치환하고, 후보식을 새로운 변수들의 곱으로 나타낸 것이 단계 1이다.
간략화된 다단 논리식을 산출하기 위해 Brayton과 McMullen은 커널(kernel)을 이용한 공통 다항 큐브 제수를 찾는 방법[1]을 제시하였다. 그 후, 커널을 이용한 논리합성 도구인 MIS[2]가 Brayton, Rudell, Sangiovanni-Vincentelli, Wang 에 의해 발표되었다. MIS 도구에 순차회로 합성 기능을 추가한 SIS[3]가 Sentovich 등에 의해 발표되었다.
다음 IF(L)로 표현된 한 개의 식에 대해서 코커널 집합을 산출하는 것이 단계 2로 예2에서 보인 바와 같이 결과를 산출한다. 본 연구에서는 코커널을 산출하는데 Brayton 등이 제시한 알고리즘[2]을 사용하였다. Brayton 등이 제시한 방법을 간단히 소개하면 논리식에서 사용한 서포트 변수의 조합을 만들어 가면서 2개 이상의 항을 동시에 나누는 제수(divisor)를 찾는데, 이 때 산출된 제수가 바로 코커널이 된다.

성능/효과

<표 2>는 제안한 방법과 타 방법이 산출한 후보식과 공통식 개수를 비교한 것이다. 대체로 제안한 방법이 후보식의 개수가 가장 많이 산출되었고, 그 결과 공통식의 산출 개수도 상대적으로 많음을 보이고 있다. 제안 방법의 경우 C7552 의 경우 <표 2>에서 후보식에 비해 산출된 공통식 개수가 적다.
따라서 에서 C7552가 타 방법에 비해 장시간의 수행 시간 소요에 비해 리터럴 개수를 줄이는 효과가 상대적으로 적음을 보이고 있다.
<표 1>의 마지막 행은 표에 리터럴 개수의 합을 표시한 것이다. 실험 결과 리터럴 개수를 비교하면, 모든 벤치마크 회로에 대하여 리터럴 개수를 줄이는 효과를 발휘하였다. 제안한 방법은 SIS보다 16%, FBDD보다 47%, 2-cube 보다 3% 정도의 리터럴 개수를 줄이는 효과를 얻었다.
제안한 방법은 각 논리식 또는 출력별로 해밍거리가 3인 큐브들을 이용해서 주어진 논리식 변형을 통해 보다 많은 공통식이 될 수 있는 후보식을 산출하는 것이다. 실험 결과 수행시간은 타 방법들에 비해 상대적으로 늘어났지만, 리터럴 개수를 줄이는 데 효과적임을 보였다. 보통 설계자동화 도구는 2~3일 정도의 수행시간을 허용할 정도로 수행시간 보다는 간략화 정도를 더 중요시 한다.
실험 결과 리터럴 개수를 비교하면, 모든 벤치마크 회로에 대하여 리터럴 개수를 줄이는 효과를 발휘하였다. 제안한 방법은 SIS보다 16%, FBDD보다 47%, 2-cube 보다 3% 정도의 리터럴 개수를 줄이는 효과를 얻었다. 반면에 해밍거리가 3인 큐브들 산출에 소요되는 시간이 요구되고, 또 타 방법보다 공통식을 추출하는데 사용되는 후보식들이 많아 상대적으로 긴 수행시간이 요구되었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	산출된 논리식의 역할은?	간략화 된 논리식을 산출하는 단계가 회로설계 자동화 분야의 핵심 중의 하나로, 하드웨어 표현 언어(Hardware Description Language)로 작성된 동작 행위(behavior level)를 실제 회로로 변환하기 위한 중간 역할을 한다. 산출된 논리식이 최종회로나 칩의 크기에 많은 영향을 미친다.
	카르노맵을 이용한 방법의 제한점은?	대학에서 논리회로에 대한 기초 학습은 카르노맵(Karnaugh Map)을 이용한 논리식 간략화에 초점을 맞추고 있다. 그러나 카르노맵을 이용한 방법은 입력 변수가 6개 이하인 경우 진리표를 입력으로 2단의 단순식을 수작업에 의해 산출하게 고안된 것이다. 본 논문은 논리회로 심화학습 과정에서 논리회로 간략화를 자동화하는 도구로 활용하고, 더 나아가 반도체 부품 개발 도구로 활용하기 위한 실용적 방법을 제안한 것이다.
	대학에서 논리회로에 대한 기초 학습은 무엇에 초점을 두고 있는가?	대학에서 논리회로에 대한 기초 학습은 카르노맵(Karnaugh Map)을 이용한 논리식 간략화에 초점을 맞추고 있다. 그러나 카르노맵을 이용한 방법은 입력 변수가 6개 이하인 경우 진리표를 입력으로 2단의 단순식을 수작업에 의해 산출하게 고안된 것이다.

참고문헌 (12)

R. K. Brayton, C. McMullen. (1982). The Decomposition and Factorization of Boolean Epressions. Proc. ISCAS, 49-54.
R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, A. R. Wang.(1987) MIS: A Multiple-Level Logic Optimization System. IEEE Trans. CAD, 6(6). 1062-1081.

상세보기
E. M. Sentovich, K. J. Singh, C. Moon, H. Savoj, R. K. Brayton, R. K., A. Sangiovanni-Vincentelli. (1992). Sequential Circuit Design Using Synthesis and Optimization. Proc. ICCD, 328-333.
J. Rajski, J. Vasudevamurthy. (1992). The Testability-Preserving Concurrent Decomposition and Factorization of Boolean Expressions. IEEE Trans. CAD, 11(6), 778-79.

상세보기
C. Yang, M. Ciesielski. (2002). BDS: A Boolean BDD-Based Logic Optimization System. IEEE Trans. CAD, 21(7), 866-876.

상세보기
D. Wu, J. Zhu. (2005). FBDD: A Folded Logic Synthesis System. Technical Report TR-07-01-05, University of Toronto.
권오형, 오임걸 (2008). 2-큐브 제수와 보수에 의한 공통 논리식 산출. 정보처리학회 논문지 A, 15(1), 9-16.
권오형 (2012). 논리식 인수분해를 위한 코스웨어. 컴퓨터교육학회논문지, 15(1), 65-72.

원문보기 상세보기
J. Cong, K. Minkovich. (2007) Optimality Study of Logic Synthesis for LUT-Based FPGAs. IEEE Trans. CAD, 26(2). 230-239.

상세보기
L Amaru, P.-E. Gaillardon, G. De Micheli. (2016). Majority-Inverter Graph: A New Paradigm for Logic Optimization. IEEE Trans. CAD, 35(5), 806-819.

상세보기
D. Kagaris. (2016). MOTO-X: A Multiple-Output Transistor-Level Synthesis CAD Tool. IEEE Trans. CAD, 35(1), 114-127.

상세보기
S. Yang. (1991). Logic Synthesis and Optimization Benchmarks User Guide Version 3.0. Technical Report, Microelectronics Center of North Carolina.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증