[논문]가역 임베딩 없는 직접적 비가역-가역회로 매핑 방법의 게이트비용 절감 방안

박동영; 정연만

doi:10.13067/jkiecs.2014.9.11.1233

초록
AI-Helper

1980년 Toffoli 가역게이트 출현 이후 지난 30년 간 적당한 함수 상에 가역 임베딩을 하는 많은 가역회로 합성법들이 발표되어 오는 동안 소수의 논문만이 가역 임베딩 없이 직접적인 비가역-가역 회로 매핑 방법을 채택해 왔다. 본 논문에서는 가역 임베딩 없는 직접적 가역 매핑에 대한 효과적인 게이트비용 절감 정책을 개발하였다. 새로운 비용절감 정책을 개발하기 위해 고전회로에서 NOT 게이트 배치에 따른 Toffoli 모듈 비용의 영향을 고찰하고, 이것을 기초로 하여 고전적 AND(OR)게이트에 대한 반전입력 추가가 가역 Toffoli 모듈의 비용을 증가(감소)시킨다-라는 고전 게이트 반전입력 수와 가역 Toffoli 모듈 비용 사이의 반비례적 성질을 이끌어내었다. 직접적 가역 매핑에 선행한 반전입력 재배치 정책은 현존하는 팬-아웃 및 슈퍼셀 정책들과 병행할 경우에 가역 Toffoli 모듈의 비용과 복잡성을 개선할 수 있는 효과적인 방법이다.

Abstract ▼ AI-Helper

For the last three decades after the advent of the Toffoli gate in 1980, while many reversible circuit syntheses have been presented reversible embedding methods onto suitable reversible functions, only a few proposed direct irreversible-to-reversible mapping methods without reversible embedding. In...

For the last three decades after the advent of the Toffoli gate in 1980, while many reversible circuit syntheses have been presented reversible embedding methods onto suitable reversible functions, only a few proposed direct irreversible-to-reversible mapping methods without reversible embedding. In this paper we present two effective policies to reduce the gate cost and complexity for the existing direct reversible mapping methods without reversible embedding. In order to develop new cost reduction policies we consider the cost influence of Toffoli module according to NOT gate arrangement in classical circuits. From this we deduced an inverse proportional property between inverting input numbers of classical AND/OR gates and reversible Toffoli module cost based on a fact - the inverting inputs of classical AND(OR) gates increase(decrease) the Toffoli module cost. We confirm the applications of the inverting input rearrangement and maximum fan-out policies preceding direct reversible mapping will be effective method to improve the reversible Toffoli module cost and complexity with the parallel using of the fan-out and supercell ones.

주제어

AI 본문요약
AI-Helper

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

문제 정의

Sultana는 Zilic의 방법을 개선하여 모든 고전 게이트들을 등가 Toffoli 모듈로 표현했는데 Zilic의 가역 셀과 유사한 슈퍼셀 (supercell)을 사용할 경우에 선(line) 수와 비용(gate cost)이 감소될 수 있음을 보였다. 본 논문은 Zilic의 방법을 Toffoli 모듈로 확장한 Sultana 방법에 대해 비용과 선의 수를 줄일 수 있는 방안을 연구하였다. 본 논문의 구성은 Ⅱ장에서 기초적 배경 이론을 논한후 Ⅲ장에서 직접적 가역 매핑의 게이트비용 절감을 위해 본 논문이 새롭게 제안하는 NOT 게이트 재배치 정책을 제시하였다.
5배로 증가했음을 알 수 있다. 이와 같은 결과는 NOT 게이트가 함수 전체에 미치는 영향을 간과한 단순 배치의 결과로서 복잡성과 비용에 대한 전형적인 교환 문제를 보여주는 사례이다. 그림 8은 본 논문의 비용 절감 정책을 그림 7(b)과 그림 7(c)에 적용한 결과이다.

제안 방법

이 NOT 게이트들은 상대적 비용이 1로써 전체 비용에 미치는 영향은 작지만 회로 연결선과 단수를 증가시켜 복잡성을 유발하고 있다. 따라서 이 문제를 해결하기 위해 Sultana[7] 은 그림 7(c) 실현에서 NOT 게이트를 단순하게 슈퍼셀에 포함시키는 해법을 제안하였다. 본 논문의 Ⅲ장 연구 결과와 비교하면 Sultana[7]이 사용한 OR-AND 2단 셀의 (b+c)# 함수는 표 1의 비용 비교에서 가장 불리한 선택이었으며, 그 결과 NOT 문제는 해결했지만 비용은 77이 되어 그림 6(b)의 약 2.
비가역 회로소자들을 가역 소자들로 치환하는 아이디어는 1980년에 최초로 Toffoli 에 의해 제안되었으나 가역 임베딩을 생성하지 않는 직접적 소자 변환방법은 2007년 Zilic[6] 등에 의해 실현되었고, 2011년 Sultana[7]에 의해 Toffoli 모듈로 확장되었다. Zilic은 고전적 게이트들을 사용하여 가역 회로를 실현하였으며, 팬-아웃(fan-out) 제한 극복을 위해 관계없는 신호들을 효과적으로 재사용하는 방안과 범용 AND/OR게이트를 포함한 다양한 가역 셀 (cell) 구현 방법을 제안하였다. Sultana는 Zilic의 방법을 개선하여 모든 고전 게이트들을 등가 Toffoli 모듈로 표현했는데 Zilic의 가역 셀과 유사한 슈퍼셀 (supercell)을 사용할 경우에 선(line) 수와 비용(gate cost)이 감소될 수 있음을 보였다.
본 논문은 Zilic의 방법을 Toffoli 모듈로 확장한 Sultana 방법에 대해 비용과 선의 수를 줄일 수 있는 방안을 연구하였다. 본 논문의 구성은 Ⅱ장에서 기초적 배경 이론을 논한후 Ⅲ장에서 직접적 가역 매핑의 게이트비용 절감을 위해 본 논문이 새롭게 제안하는 NOT 게이트 재배치 정책을 제시하였다. Ⅳ장은 Ⅲ장의 제안 정책을 타 논문 방법에 적용한 결과의 상세 비교이며, Ⅴ장은 본 논문의 결론이다.
본 장에서는 고전 게이트의 반전입력과 Toffoli 모듈의 게이트 비용의 상관관계 도출을 위해 단일 게이트와 2단 게이트의 가역매핑 실현 특성을 고찰한다. 이를 토대로 가역임베딩 없는 직접적 가역매핑법의 일반적 게이트비용 절감 정책을 도출하였다.
본 장에서는 고전 게이트의 반전입력과 Toffoli 모듈의 게이트 비용의 상관관계 도출을 위해 단일 게이트와 2단 게이트의 가역매핑 실현 특성을 고찰한다. 이를 토대로 가역임베딩 없는 직접적 가역매핑법의 일반적 게이트비용 절감 정책을 도출하였다.

성능/효과

그림 2에서 기본적으로 3x3 Toffoli 게이트인 무반전(non-inverting) 입력 AND 게이트는 Toffoli 모듈의 비용이 5로써 AND 게이트에 추가되는 반전입력 당 Toffoli 모듈의 CNOT 게이트도 한 개씩 추가되어 비용이 1씩 선형적으로 증가함을 알 수 있다. 반면 무반전 입력 OR 게이트는 기본적으로 3x3 Toffoli 게이트에 2개의 CNOT 게이트들이 종속 곱(cascade multiplication)되어 실행되므로 기본적 비용이 7이며, 고전적 OR 게이트에 추가되는 반전입력 당 Toffoli 모듈의 CNOT 게이트들이 한 개씩 제거되어 비용이 1씩 감소함을 알 수 있다. 그림 3은 AND/OR 게이트의 반전입력 수와 비용의 상관관계 그래프이다.
1번/2번 및 5번/6번의 팬-아웃 함수들은 각각 NAND/OR 연산을 실행해야 하므로 P2 적용 시에 표 3의 Ⅰ형에서 AND 출력에 NOT를 추가한 비용 6으로 실현될 수 있어 그림 8(b)과 같이 총비용 27로 실현 가능하였다. 본 논문은 기존의 복잡성 원인이었던 4개 NOT 게이트를 팬-아웃과 OR 게이트로 분산 배치함으로써 복잡성과 비용 절감이란 교환 문제를 동시에 해결할 수 있었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	비가역 회로를 가역 회로로 실현하는 방법 중 일반적인 방법으로 무엇이 있는가?	비가역 회로를 가역 회로로 실현하는 방법은 가역 임베딩(reversible embedding)이란 매핑(mapping)의 적용 유무에 따라 구분할 수 있다. 일반적 방법은 적당한 함수 상에 가역임베딩을 먼저 만든 후에 간략화 과정을 통해 가역회로로 합성하는 방법들로서 대표적인 BDD(Binary Decision Diagram) 방법[2]를 비롯해 다양한 방법들이 발표되었다[1],[3-5]. 비가역 회로소자들을 가역 소자들로 치환하는 아이디어는 1980년에 최초로 Toffoli 에 의해 제안되었으나 가역 임베딩을 생성하지 않는 직접적 소자 변환방법은 2007년 Zilic[6] 등에 의해 실현되었고, 2011년 Sultana[7]에 의해 Toffoli 모듈로 확장되었다.
	비가역 회로의 정보손실에 따른 에너지 손실을 막기 위한 대안은 무엇인가?	비가역 회로는 전송 종단점에서 정보손실에 따른 에너지 손실이 발생한다. 비가역 회로의 정보손실에 따른 에너지 손실을 막기 위한 대안은 비가역 회로를 가역 회로로 설계하는 것이다[1]. 비가역 회로를 가역 회로로 실현하는 방법은 가역 임베딩(reversible embedding)이란 매핑(mapping)의 적용 유무에 따라 구분할 수 있다.
	비가역 회로는 전송 종단점에서 어떠한 손실이 발생하는가?	비가역 회로는 전송 종단점에서 정보손실에 따른 에너지 손실이 발생한다. 비가역 회로의 정보손실에 따른 에너지 손실을 막기 위한 대안은 비가역 회로를 가역 회로로 설계하는 것이다[1].

참고문헌 (7)

D. Maslov and G. W. Dueck, "Reversible Cascades with Minimal Garbage," IEEE Trans. CAD, vol. 23, no. 11, 2004, pp. 1497-1509.

상세보기
R. Wille and R. Dreschler, "BDD-based Synthesis of Reversible Logic Circuits for Larger Functions," Proc. DAC, San Francisco, CA, July 26-31, 2009, pp. 270-275.
V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, "Synthesis of Reversible Logic Circuits," IEEE Trans. CAD, vol. 22, no. 6, 2003, pp. 710-722.

상세보기
D. Michael Miller, Robert Wille, and Gerhard W. Dueck, "Synthesizing Reversible Circuits for Irreversible Functions," 12th Euromicro Conf. on Digital System Design/Architectures, Methods and Tools, Patras, Greece, Aug. 2009, pp. 749-756.
D.-Y. Park and Y.-M. Jeong, "A New Functional Synthesis Method for Macro Quantum Circuits Realized in Affine-Controlled NCV-Gates," J. of the Korea Institute of Electronic Communication Science, vol. 9, no. 4, 2014, pp. 447-454.

원문보기 상세보기
Z. Zilic, K. Radecka, and A. Khazamiphur, "Reversible circuit technology mapping from non-reversible specifications," Proc. Design Automation and Test in Europe, Nice, France, Apr. 2007, pp. 558-563.
S. Sultana and K. Radecka, "Rev-Map: A Direct Gateway from Classical Irreversible Network to Reversible Network," IEEE 42th Int. Symp. on Multiple-Valued Logic, Victoria, Canada, May 2011. pp. 147-152.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

가역 임베딩 없는 직접적 비가역-가역회로 매핑 방법의 게이트비용 절감 방안
Gate Cost Reduction Policy for Direct Irreversible-to-Reversible Mapping Method without Reversible Embedding 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

질의응답

참고문헌 (7)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

가역 임베딩 없는 직접적 비가역-가역회로 매핑 방법의 게이트비용 절감 방안 Gate Cost Reduction Policy for Direct Irreversible-to-Reversible Mapping Method without Reversible Embedding 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

성능/효과

질의응답

참고문헌 (7)

이 논문을 인용한 문헌

저자의 다른 논문 :

박동영 (12) 정연만 (7)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

가역 임베딩 없는 직접적 비가역-가역회로 매핑 방법의 게이트비용 절감 방안
Gate Cost Reduction Policy for Direct Irreversible-to-Reversible Mapping Method without Reversible Embedding 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper