조기 완료
Early completion | 이 기사는 대부분의 독자들이 이해하기에는 너무 전문적일 수 있다.세부사항을 이해할 수 . (2021년 ( 템플릿메시지 및 시기 ) |
조기완성은 비동기회선의 일부 클래스의 속성입니다.즉, 회로의 출력을 판별할 수 있는 충분한 입력이 도착하는 즉시 사용할 수 있습니다.예를 들어 mux에 대한 모든 입력이 도착하고 모두 동일하지만 선택 라인이 아직 도착하지 않은 경우에도 회로는 출력을 생성할 수 있습니다.모든 입력이 동일하기 때문에 선택 행은 관련이 없습니다.
예: 비동기 리플 반송 가산기
리플 반송 가산기는 단순한 가산기 회로이지만 가산기의 각 스테이지에 반송 신호가 전파되어야 하므로 속도가 느립니다.
이 다이어그램은 5비트 리플 반송 가산기가 작동하는 모습을 보여 줍니다.5 스테이지의 긴 반송 경로가 있기 때문에 이 가산기에 2개의 숫자를 추가할 때마다 반송이 5 스테이지 전체에 전파될 때까지 기다려야 합니다.
반송 비트용 듀얼 레일 신호로 전환함으로써 각 스테이지 신호를 아는 즉시 실행할 수 있다.스테이지에 대한 두 입력이 모두 1이면 캐리 인이 무엇이든 간에 수행은 1이 됩니다.두 입력이 모두 0이면 수행이 0이 됩니다.이러한 조기 완성은 대부분의 경우 캐리 체인의 최대 길이를 줄여줍니다.
반출 비트 중 2개는 입력이 도착하는 대로 그림에 표시된 입력에 대해 알 수 있습니다.즉, 최대 캐리어 체인 길이는 5가 아니라 3입니다.입력 및 출력에 이중 레일 신호를 사용하는 경우, 모든 캐리어 체인이 완료되는 즉시 완료를 나타낼 수 있습니다.
평균적으로 n비트 비동기 리플 캐리 가산기는 O(log n) 시간 내에 종료됩니다.이 방법을 사전 검색 추가자를 전송하도록 확장하면 O(log log n) 시간을 추가할 수 있습니다.
외부 링크
