KR100321013B1 - 동기식디지탈전자회로와그설계및작동방법 - Google Patents

Abstract

네트에 의해 상호 접속되고 소정의 클럭 주기에서 동작하는 클럭킹된 플립플롭 및 셀을 포함하는 동기식 디지탈 전자 회로를 설계하는 방법은 다음과 같이 실행된다. 먼저, 셀로부터 나오는 임의의 서브경로에 대한 임의의 셀로부터 시작하여 똑같은 방향으로 연관된 지연이 축적된다. 다음에, 상기 서브경로에 대해서, 축적 결과가 소정의 수의 클럭 주기를 초과하면, 문제의 서브경로에 상기 소정의 수의 플립플롭들의 후속 제공을 위한 신호를 보냄으로써 축적이 종료된다. 마지막으로, 상기 신호 전송에 따라 모든 기본 셀-대-셀 접속부에 최소의 플립플롭들이 제공된다. 본 발명은 특히 디지탈 비디오 프로세서에 사용되는 것과 같은 큰 회로및 작은 클럭 주기에 유리하다.

Description

동기식 디지탈 전자 회로와 그 설계 및 작동 방법

발명의 배경

본 발명은 네트에 의해 상호 접속되고 소정의 클럭 주기에서 동작하는 클릭킹된 플립플롭들과 셀들을 포함하는 동기식 디지탈 전자 회로를 상기 플립플롭의 선택적인 위치화(selective positioning)를 통해서 설계하는 방법에 관한 것으로서, 회로의 임의의 셀은 각각의 신호 지연을 셀의 입/출력 쌍 사이의 경로에 부여하며, 적어도 하나의 플립플롭이 상기 클럭 주기 이상의 전체 지연을 부여하는 회로내 경로에 제공된다. 회로 설계시 고려된 정밀도가 양호하다면, 셀 또는 노드가 본질적으로 클럭킹되지 않은 결합성 소자(combinatorial element)일 수도 있다. 정밀도가 낮은 경우, 노드는 하나 이상의 클럭킹된 소자들을 포함할 수 있으며, 보다 넓게는 순차적으로 작동하는 소자들을 포함할 수 있다. 또한, 클럭킹된 소자의 관련성은 이하 기술되는 바와 같이 고려된 노드를 통해 실제 신호 경로에 의존할수 있다. 전제부에 따른 방법은 알고리즈미카(Algorithmica) '91의 5-35페이지에 기술된 Ch.E. Leiserson 및 J.B. Saxe의 논문 'Retiming Synchronous Circuitry'에 기술되어 있다. 특히, 비디오 신호들에 대한 디지탈 신호 처리(Digital Signal Processing; DSP)의 도입은 삽입된 셀들의 수의 면에서 신호 처리능력에 대한 요구를 증가시키며, 이는 사실상 플립플롭들을 서로간에 근접하게 한다. 상기 문헌의 특정 기술은 특히 보다 높은 주파수들을 허용하는 성능을 증가시키기 위한 플립플롭들의 재위치화(repositioning) 또는 "리타이밍"이다. 리타이밍의 서브셋 또는 특정 경우는 파이프라이닝이다. 상기 두 기술은 이하 기술될 것이다. 상기 참조 문헌에 따르면, 회로 대기(circuit latency)는 증가되지 않는다. 상기 참조 문헌의 기술은 셀간 신호 지연의 매트릭스를 셋업하고, 하나의 클럭 주기보다 긴 지연 시간을 나타내는 모든 셀간 경로에 플립플롭을 제공함으로써 동작한다. 그 다음에, 플립플롭들은 리타이밍 또는 시프팅(shifting)된다. 그러나, 많은 조건들의 해결책이 무엇보다도 임의의 쌍의 셀들을 상호 접속할 수 있는 긴 경로 및 다수의 셀들을 고려한 다수의 상기 조건들로 인해, 특히, 큰 회로에 대해서는 효과적이지 않다.

발명의 요약

따라서, 본 발명의 주요 목적은 짧은 처리 시간내에 최적의 해결책을 이끄는 플핍플롭들의 배치를 효과적으로 행하기 위한 방법을 제공하는 것이다. 본 발명에 의해 제공된 통찰은 비교적 높은 클럭 주파수로 인해, 연속적인 플립플롭들간의 셀들의 수가 많지 않으므로 문제의 보다 국지화된 해결책이 전체적인 해결책보다 빠르다는 것이다. 많은 경우에, 둘 이상의 조건들 간의 논리 관계는 없거나 기본적이다. 결과적으로, 본 발명의 일 양상에 따르면, 본 발명은 셀로부터 나오는 임의의 서브경로를 위해 임의의 셀로부터 시작함으로써 똑같은 방향으로 관련 지연이 축적되고, 상기 지연에 의해 소정의 수의 상기 클럭 주기를 초과할 때 서브경로에 상기 소정의 수의 플립플롭들의 후속 제공을 위한 신호를 보내어 그 축적이 종료되며, 이어서 상기 신호 전송에 따라 모든 기본적인 셀-대-셀 접속에 최소의 플립플롭이 제공된다. 이제, 소정 수의 클럭 펄스 주기들이 1, 2 또는 그 이상으로 고정될 수 있다. 특히, "1"로 고정된 임계치는 최소량의 처리 메모리를 필요로 한다. 보다 큰 임계치를 갖는 해결책은 종종 회로에 삽입된 보다 적은 플립플롭들을 필요로 한다. 고정된 임계치에 대한 대안으로, 정수는 경로방식(pathwise)으로 범위내에서 할당될 수 있다. 각각의 경로가 존재하는 한, 또는 지연 결정이 관련되는 한보다 큰 값들에 대해 수행될 수 있다. (지연 집합화의 수행이 무의미한 결과로 되기 때문에)회로 루프에 도달할 때 집적 회로의 종단에서 또는 다른 경우에는 기능모듈의 종단에서 종료될 수 있다. 종종, 특정 노드쌍간의 집합화는 여러 번 실행되어 높은 메모리 요구를 발생시킨다.

따라서, 상기 소정의 수가 다수를 포함하는 범위 내에서 경로방식으로 할당되고, 두 특정 셀 중 수렴(converging) 셀에 도달할 때의 최고 축적 결과를 갖는 서브 경로의 추가 축적을 위하여 임의의 상기 서브경로의 추가 축적을 종료하는 두 특정 셀들간에 다중 서브경로 패턴이 존재하는 경우에 할당될 때, 상기 축적은 경로 고유의 가중치로 감소된 클럭 주기에 비해 표준화된 지연이다. 상기 집합화는 최대수의 추가 플립플롭들을 필요로 하는 경로에 대해서만 수행되고, 경로의 가중치는 이미 기능적인 이유로 인해 도입된 플립플롭의 수이다. 즉, 기능화 자체를 실현하기 위해 요구된다. 소정의 수를 1로 균일하게 유지하는 것보다 나은 결과를 궁극적으로 실현하더라도, 상기 방법은 가능한 한 각각에서 고수하는 것보다 적은 컴퓨터 시간/저장을 필요로 함을 알 수 있다.

본 발명은 또한 상기 방법을 실행하기 위한 장치를 제공한다. 본 발명은 또한 본 발명에 따른 상기 방법을 실행함으로써 발생된 전자 회로 구성에 관련된다. 본 발명의 장점들은 청구항에 따라 기술될 것이다.

양호한 실시예의 설명

제 1a 도 및 제 1b 도는 파이프라이닝(pipelining) 전후의 간단한 회로를 도시한다. 제 1a 도에 도시된 것과 같이, 상기 회로에는 신호 입력(I), 신호 출력(0), 2개의 플립플롭들(20, 24) 및 EXOR로서 도시된 2개의 결합 소자들(26,28)이 있지만, 기본적으로 클럭킹된 지연이 없는 임의의 실행 가능한 논리 기능 또는 연산 기능을 포함할 수 있다. 상기 설명한 것과 같이, 상기 후자의 제한조차도 필수적이지는 않다. 간략히 하기 위해, 플립플롭들의 클럭 입력은 도시하지 않았다. 2개의 플립플롭들을 통해서, 회로는 세가지의 연속된 상태들을 저장할 수 있다. 낮은 클럭 주파수에서, 직렬인 2개의 연산 소자들에 의해 발생된 지연은 클럭 펄스주기보다 작다. 보다 높은 주파수에서는 이것이 더 이상 보장되지 않음으로써, 제 Ib '도는 소자들(26, 28) 사이에 삽입된 추가 플립플롭(30)을 가진다. 여분의 플립플롭(32)은 플립플롭(24)과 결합 소자(26)의 출력들 간의 타이밍 조정을 위해 필요하다.

제 2a 도 및 제 2b 도는 리타이밍 전후의 간단한 회로를 도시한다. 일반적으로, 제 1a 도 및 제 1b 도에서와 같은 유사한 회로 소자들이 제시된다. 리타이밍시에, 플립플롭들은 상호 접속부를 따라 시프트된다. 만일 그렇게 동작한다면, 상호 접속부는 둘 이상의 다른 라인으로 분기되고, 상기 플립플롭은 모든 라인에 대해 하나씩 많은 경우로서 분할된다. 이와 유사하게, 만일 둘 이상의 플립플롭들이 단일 라인으로 합쳐지는 병렬 라인들을 따라 이동하면, 상기 플립플롭들은 단일라인을 따라 이동하는 단일 플립플롭으로 수렴한다. 따라서, 제 2a 도에서 제 2b도로의 전환은 두 단계로 행해진다. 즉, 먼저 플립플롭(34)은 전방으로 이동하여 2개의 플립플롭들로 분리되는데, 한 플립플롭은 플립플롭(36)과 직렬이 되고, 다른 한 플립플롭은 상호 접속부(46) 상으로 이동된다. 다음에, 후자의 플립플롭과 플립플롭(36)은 전방으로 이동하여 플립플롭(42)으로서 결합 소자들(38, 40) 사이에 연결된다. 플립플롭(44)은 더 이상의 수정없이 시프트 되었다. 언급된 것과 같이, 파이프라이닝 동작의 설명은 사실상 리타이밍 동작의 서브셋이다. 제 1b 도는 결합 소자(28)에 암시적으로 나타나는 접합부를 통과한 후 그 분기와 연합하여 출력(0)에서의 플립플롭의 후방 이동을 통한 라타이밍 동작의 결과로서 설명될 수 있다. 그러나, 제 2b 도의 구성이 최선이라는 것을 쉽게 알 수 있는데, 왜냐하면 제 2b 도에서 타이밍 제한이 존재하며(두 결합 소자들(38, 40) 사이의 플립플롭), 플립플롭들의 수가 최소(2 대 제 1b 도의 4)이기 때문이다.

제 3 도는 본 발명에 따른 방법을 예시하는 셀들 및 상호 접속 시스템을 도시한다. 전자 기술은 무관하지만, 일반적으로 전체 회로는 단일 집적 칩이나 그 부분으로서 실행된다. 상기 회로는 직사각형으로서 도시된 셀들(50, 70 ...84)을 가진다. 또한, 상기 도면은 다수의 셀-대-셀의 상호 접속부들(51, 52, 53, 55, 56, 57, 59, 61, 62, 64, 66)과 출력 상호 접속부(68)를 도시한다. 셀들의 세트는 회로의 의도된 모든 기능에 따라 임의의 결합 논리 기능을 실현할 수 있고, 각 셀은 그의 적당한 부분을 실현한다. 셀들은 내부 접근 가능성이 없는 것으로 도시되었으나, 이러한 제한이 필수적인 것은 아니다. 각 셀은 컴퓨터-보조 설계 환경(computer-aided design environment)에 대한 적당한 표현에 따라 연관된 라이브러리 소자로서 실현될 수 있다. 데이타는 일반적으로 좌에서 우로 전달된다. 상호 접속부들은 두 셀들 사이에서 각각 나타난다. 실제로, 임의의 물리적 상호 접속부는 3개 이상의 셀들을 상호 접속할 수 있으나, 도시된 바와 같은 도면은 축적된 지연들의 할당을 위해서만 의도된 것이다. 각 셀은 하나 이상의 물리적 입력 상호접속부들과 하나 이상의 출력 상호 접속부들을 가질 수 있다. 실제로, 회로는 더확대된다. 셀(78)의 출력에서 다시 동일 셀의 입력으로의 원형 경로들, 또는 더 복잡한 배열에 따른 원형 경로들이 있을 수 있다. 또한, 제 1 도와 제 2 도를 비교하면, 본 발명의 응용에 앞서 레지스터형 또는 플립플롭형 소자들이 제공될 수도있다.

간략화를 위해, 사실상 상기 제한이 필요하지 않더라도, 신호 지연은 셀들에서 총괄된다. 각 셀은 70A와 같은 작은 네모로서 도시된다. 이것은 적당한 셀의 신호 지연을 나타낸다. 또한, 각 셀에는 상호 접속부(52)의 지연을 나타내는 블록 70B와 같은 다음의 연속적인 상호 접속부의 지연도 고려되었다. 둘 이상의 상호 접속부들이 특정 셀에서 나오는 경우, 문제의 셀의 우측 블록은 출력 상호 접속부들이 있는 것처럼 많은 지연 시간을 나타낸다. 특정 셀로부터의 개개의 출력 지연은 동일할 수도 있고 그렇지 않을 수도 있다. 셀들 개개의 입력들에 대한 상호 접속 지연들을 총괄하는 것이 적당할 것이다. 이 경우, 상호 접속 지연들은 블록 70A로 나타낸 바와 같은 기능 지연들의 다른 측면에 위치해야 한다.

이제, 본 발명에 따른, 회로에 존재하는 셀들로부터 처리가 시작한다. 처리방향은 데이타 흐름과 똑같은 방향으로, 즉, 좌에서 우로 향한다고 가정한다. 반대 방향도 같은 결과를 제공할 것이다. 특정 셀들에서 나오는 상호 접속부는 다음과 같다. 셀(50)에서, 먼저 각각 셀(70)과 셀(72)로 이어지는 두개의 상호 접속부들(51, 53)이 있다. 각각의 이와 같은 셀은 개개의 지연을 나타낸다. 이제, 셀들(50, 70)의 지연이 한쪽에 축적되고, 셀들(50, 72)의 지연이 다른쪽에 축적된다. 다음으로, 축적 결과들은 의도된 클럭 펄스 주기와 비교된다. 모든 셀들 및 결합된 후속 기본 상호 접속부들이 클럭 펄스 주기보다 작은 지연을 가진다는 것을 알수 있다. 이제 분석동안, 축적된 합은 클럭 펄스 주기와 동일하거나 더 크게 되고, 문제의 서브경로는 일반적으로 D형 플립플롭인 클럭 구동 플립플롭의 삽입을 위해 마크된다. 상기 마킹은 축적 결과에 기여한 전체 서브경로에 관련된다. 설명된 것과 같은 축적 처리는 오른쪽으로 더 나아간다. 셀들(70, 78)에서와 같이, 부가적 분기가 발생한다. 이제, 셀(74) 뒤에서 셀들(50, 70, 74)의 시퀀스로 구성된 서브경로에서의 삽입을 위해 플립플롭이 신호를 보내는 점에서 축적 결과가 클럭 펄스 주기를 넘고, 그 축적은 정지된다고 가정한다. 그것만으로, 상기 축적은 약간 높은 클럭 펄스 주기들의 수가 얻어질 때까지 지속될 수 있지만, 이것은 판단을 복잡하게 하고, 더 양호한 결과를 발생하지 않는다. 그러나, 이것은 특정 소정의 축적값을 얻음으로써 제어되어 축적이 정지된다는 점에서, 본 발명의 기본적 생각과 상응한다. 상기에 언급한 것과 같은 방식으로, 제 3 도에 도시된 다른 셀들로부터 축적이 시작된다. 이 기본 회로에 대해, 열가지 축적 결과들이 발생될 수 있는데, 어떤 축적들은 회로의 출력 단자에 도달할 때 정지될 수 있기 때문에 클럭펄스 주기를 넘는 축적 결과를 모두 제공할 필요는 없다.

제 7 도는 해결책에 대한 다양한 개선책들의 실현을 예시한다. 이 도면은 단일 셀(100)에서 시작하는 두개의 상호 접속부들을 도시한다. 제 3 도에서와 같은 방식으로 나타낸 상기 셀은 사실상 제 3 도의 셀들(50, 72, 78)의 시퀀스와 같은 집합된 셀을 나타낼 수 있다. 이제, 두개의 상호 접속부들(102, 104)이 직접 또는간접적으로 같은 셀(106)로 재수렴한다면, 축적 결과들은 클럭 펄스 주기와 비교된다. 만일 이들 중 어떠한 것도 클럭 펄스 주기를 넘지 않으면, 다음 처리는 보다 높은 축적 결과에 대해서만 추가적 축적이 유효하다는 점에서 간단해질 수 있다. 이는 또한 셀(106) 뒤에서 추가의 분기가 발생할 경우에도 적용한다. 이것은 소정의 수가 1과 같다는 것을 의미한다. 그러나, 적어도 하나의 플립플롭에 위치해야 하는 신호가 전송되는 상호 접속부(104)를 포함하는 서브-경로로 뿐한 아니라 일부분을 형성하는 상호 접속부(102)의 서브경로로 분리되어 인가된다.

상기 재수렴 문제는 회로가 복잡할 때 더 중요하다. 지연의 축적이 클럭 펄스 주기의 달성을 지나서 계속 지속된다면, 상황은 약간 더 복잡해지고 다양한 접근 방법들이 뒤따를 수 있다. 경로의 지연(D)은 상기 경로의 비-플림플롭 소자들에 의해서만 발생된다는 것을 명심해야 한다, 또한, 경로의 기본 회로 기능은 그 자체로 플립플롭의 위치화를 지시할 수 있다. 경로에서의 상기 연속된 플립플롭들의 수는 문제의 경로(P)의 가중치(W)이다. 경로의 라벨은 문제의 경로의 입력과 출력간의, 재수렴 경로들 중 하나의 경로를 나타내는 가중치 및 지연으로 구성된다. 관련된 경로 라벨링은 다음과 같다. 함께 재수렴하는 모든 경로들에 대해서, 리타이밍 후에 동일한 수의 레지스터 플립플롭들이 나타나야 한다. 두 셀들 또는 두 동작들간의 관련 경로는 레지스터들의 최대수가 더해져야만 하른 경로이다. 상기 수는 {D/C-W}이며, 여기서 C는 클럭 펄스 주기이고, W는 앞서 나타낸 레지스터들의 수인 가중치이다. 재수렴 셀에 도달할 때, 상기 수의 최대값을 갖는 경로는 추가로 축적되고, 반면에 다른 재수렴 경로들에 대한 축적은 종료될 것이다. 이는 필요한 컴퓨터 용량을 상당히 경감시킨다.

이러한 방법으로, 플립플롭의 세트는 제 3 도의 회로에 위치하기 위해 신호를 보낼 것이며, 임의의 두개의 연속 플립플롭들간의 최고 지연이 클럭 펄스 주기보다 높아야 할 필요는 없다. 우측에서 시작하고 시간이 지남에 따라 부분적 지연들을 축적할 때, 유사한 처리가 실행될 수 있다. 다음으로, 먼저, 발견된 조건들의 세트가 실제로 위치된 플립플롭들의 세트를 얻기 위해 구해진다. 마지막으로, 그렇게 신호가 보내진 플립플롭 위치들은 제 1a 도, 제 1b 도, 제 2a 도, 제 2b 도에 대해서 설명된 것과 같이 리타이밍 및 파이프라이닝 처리가 수행된다. 그러나, 리타이밍은 필수적인 로컬 처리이며, 따라서 약간의 시간이 소비된다.

제 4 도는 회로와 그 타이밍 모델의 예를 도시한다. 상기 회로는 하나의 반가산기(ha)와 두개의 전가산후(fa)를 포함하는 3비트 가산기이다. 각각의 가산기들은 두 입력 비트들(a, b)을 수신하고, 합 비트(s)와 다음의 유효 고레벨로 캐리를 출력하며, 유효 고레벨은 출력 캐리를 발생하는 조합 회로이다. 또한, 종래의 표시에서의 플립플롭은 두개의 최상위 스테이지들간의 캐리 경로에 삽입되었다. 예로써, 모든 가산기들은 똑같은 5(임의의 단위)의 지연을 가진다고 가정된다. 제 5 도에서 최상위 행은 다양한 입력들(N)을 열거한다. 제 2 행은 회로의 최상위 레벨 가산기인 기준 위치에 대한 가중치(플립플롭들의 수)를 열거한다. 제 3 행은 문제의 입력과 플립플롭간의 지연을 열거한다. 이와 비슷하게, 최좌측 열은 출력들을, 그 다음 열은 최상위 레벨 가산기에 대한 가중치들을, 그 다음 열은 플립플롭과 문제의 출력간의 지연을 열거한다. 상기 표의 나머지 부분은 입력-출력 쌍(5, 10 또는un(미결정)일 수 있다)간의 지연을 열거한다. 미결정 상태는 a0과 s2사이와 같은 삽입 플립플롭에서 전개되거나, b1 과 s0 사이와 같은 둘 사이의 관계의 무관련성으로 인해 전개될 수 있다. 그 자체로, 문제의 회로가 A. van der Werf 등의 Hierarchical Retiming Including Pipelining, Proceedings VLSI 1991에 공개되어 있으며, 상기 참고 문헌은 본 발명에 따른 이와 같은 리타이밍보다 우월한 동작에 접근하지 않았다. 회로는 특히, 순차 동작 셀들을 가진 경우와 가지지않은 경우 모두 본 발명의 가능성을 보여주기 위해 본원에 포함되어 있다.

분해의 설명

제 6 도는 본 발명을 실행하는 순서도이다. 블록 80은 종래의 초기화로 방법 실행의 시작을 기호화한다. 블록 82에서, 제 4 도와 제 5 도에 대해 예시된 것과 관련된 파라미터들에 따라 회로의 설명(description)이 로드된다. 셀들은, 예를 들어, 번호가 붙여진 리스트와 같이 시퀀스됨으로써, 각 셀 엔트리(entry)는 선행 셀 또는 셀들 및 회로의 상호 접속 패턴의 후속 셀 또는 셀들에 대한 포인터들을 가진다. 블록 84에서, 제 1 리스트 셀이 액세스된다. 블록 86에서, 문제의 셀들에 저장된 포인터들에 의해(이 특정 셀에 대해 독립적으로 순차 리스트로서 표현된다) 그 다음 셀이 액세스되고 이 특정 경로에 대한 지연이 축적된다. 블록 88에서, 축적이 클럭 주기를 초과하는지의 여부가 검출된다. 만일 초과한다면, 문제의 서브경로가 플립플롭을 얻기 위해 마크되고 그 처리는 종료된다. 만일 초과하지 않는다면, 상기 시스템은 다음 셀을 액세스하기 위해 블록 86으로 되돌아간다. 탐색 블록 86은 트리에 따라 구성되며, 서브경로의 종료는 탐색되지 않은 서브경로가 아직 시작되지 않은 가장 최근 셀로 점프 백하는 것을 제어한다. 트리 탐색은 공지되어 있으며, 더 이상의 설명은 필요하지 않을 것이다. 만일 모든 서브경로들이 종료되었다면, 블록 90에서 처리는 셀들의 리스트가 완전히 다루어졌는지의 여부를 검출한다. 검출 결과가 '아니오'인 한, 시스템은 시퀀스의 다음 셀을 액세스하기 위해 블록 84으로 되돌아간다. 이는 각 셀이 한 무리의 서브경로들의 시작으로서 한번만 계산됨을 의미하지만, 다른 셀들에서 시작하는 것을 통해 몇 번씩 방문될수 있다. 셀들의 시퀸스가 다 소모되면, 시스템은 탐색 처리를 통해 플립플롭들을 위치화시키기 위해 블록 92로 가며, 논리 기능들은 다양한 서브경로들의 셀간 신장에 관해 실시된다. 예를 들어, 만일 서브경로 I가 신장(a, b, c)으로 구성되고 서브경로 II가 신장(c, d, e)으로 구성된다면, 양 서브경로들에 플립플롭들을 제공하는 가장 쉬운 길은 신장 c이다. 왜냐하면 서브경로들은 비교적 짧기 때문이다. 즉, 두개의 클럭 펄스 주기의 진행보다 짧기 때문에, 이렇게 발생된 논리 기능들의 성질은 간단하다. 그 자체로, 배치 알고리즘은 참고 문헌 Leiserson 등에 설명되어 있다. 플립플롭들이 배치되면, 블록 94에서 플립플롭들은 제 2a 도, 제 2b 도와 관련하여 설명된 것과 같이 독립적으로 표준화 방식으로 리타이밍된다. 마지막으로, 블록 96에서, 예를 들어, 리타이밍 후에 플립플롭들의 리스트와 그 위치들을 출력하면서 상기 처리가 종료된다.

이 시점에서 다시 제 7 도로 돌아가서, 앞서 상기 두 상호 접속부들은 오직 하나의 지연을 나타내는 것으로 고려되었다. 이것의 가장 간단한 실현 방법은 기술적으로 가능한 실시 중 한 실시에서의 와이어로서 실시하는 것이다. 또한, 저항과같은 임의의 수동 소자들을 포함할 수 있다. 독립적으로, 기본 논리 소자들은 상호 접속부의 부분을 구성할 수도 있다. 제 7 도는 하나 또는 두 상호 접속부들이 상기 축적 처리에서 카운트되지 않는 하나 이상의 플립플롭들을 포함할 수 있다는 점에서 한 단계 더 나아간다. 이와 같은 플립플롭이 이미 기본 설계에서 나타났다면, 그 존재는 축적 및 플립플롭이 어디에 삽입되어야 하는가를 나타내는 조건들을 해결한 후에 고려된다. 이미 나타난 임의의 플립플롭은 여기서 고려된다. 이제, 축적 기간동안, 제 7 도의 상항, 즉, 둘 또는 그 이상의 경로들(제 3 도에서 셀(50)에서 셀(80)로와 같은)의 브랜치 오프되고 수렴하면, 다음 상황이 발생한다. 먼저, 상호 접속부들의 플립플롭들의 수를 카운트한다. 만일 그 수가 다르다면, 최저 가중치 또는 최저 플립플롭들의 수를 갖는 서브경로에 대한 축적만이 계속된다. 수들이 모두 같을 때에만(제로 포함), 최고 결과에 대한 축적이 지속된다. 다양한 절차상의 빠른 길들이 제 6 도의 기본 예로 실시될 수 있다. 만일 축적이 수렴 셀에 도달하면, 상기 축적은 계속 진행할지의 여부를 결정하기 전에 상기 특정 노드에 수렴하는 모든 다른 서브경로들이 뒤따를 때까지 정지될 수 있다.

상기 언급한 것과 같이, 관련 경로 접근에 따라, 플립플롭의 삽입을 위한 서브경로의 마킹 후에, D/C-W의 축적이 계속되고, 축적이 다음 정수값을 넘어설 때마다, 다음 플립플롭 삽입이 신호화된다. 수렴 셀에서, 축적 결과들이 비교되고, 최고값만이 추가의 축적을 위한 기초로서 취해진다.

이제, 장치, 바람직하게는 프로그램된 디지탈 컴퓨터에서 상기한 바의 실시는 간단해진다. 먼저 회로의 설명이 메모리에서 로드된다. 다음으로, 각 경로 또는서브경로에 대해 상기 설명한 것과 같이, 가중치를 고려하거나 또는 고려하지 않으면서 지연들이 축적된다. 간단한 가산이 거기에서 이루어진다. 다음으로, 프리셋 임계치와 대비하여 식별이 실행된다. 만일 식별이 포지티브이면, 플립플롭이 삽입된다. 마지막으로, 그렇게 얻어진 결과가 출력된다.

부록(APPENDIX)은 라벨링으로 제한된 효율적인 클럭 주기에 대한 요약 프로그램이다. 여기서 0는 출력 단자들(o)의 세트이고, I는 입력 단자들(i)의 세트이며, E는 에지들(e)의 세트; w는 특정 신호 에지에서 신호가 지연되는 클럭 사이클들의 수인 가중치 함수; del은 입력과 출력간의 지연; dat는 입력에서 내부 레지스터나 대응 동작의 출력으로의 내부 경로의 최대 지연; drt는 내부 레지스터나 대응동작의 입력에서 출력으로의 내부 경로의 최대 지연; D는 경로 p의 지연; W는 경로의 가중치이다.

부록

제 1a 도 및 제 1b 도는 파이프라이닝(pipelining) 전후의 회로에 대한 도면.

제 2a 도 및 기 2b 도는 리타이밍(retiming) 전후의 회로에 대한 도면.

제 3 도는 네트(net) 및 상호 접속 시스템의 도면.

제 4 도는 회로와 그 회로의 타이밍 모델의 예시도.

제 5 도는 제 4 도와 연관된 다양한 지연의 도면.

제 6 도는 본 발명을 구현하는 순서도.

제 7 도는 해결책에 대한 다양한 실현예를 예시한 도면.

* 도면의 주요 부분에 대한 부호의 설명 *

I : 신호 입력 O : 신호 출력

20, 24, 30 : 플립플롭 26, 28 : 결합 소자

Claims (7)

1. 네트들(nets)에 의해 상호 접속되고 소정의 클럭 주기로 동작하는 셀들과 클럭킹된 플립플롭들을 포함하는 동기식 디지탈 전자 회로를 상기 플립플롭들의 선택적인 위치화를 통해 설계하는 방법으로서, 상기 회로의 임의의 셀은 상기 셀의 입/출력 쌍 사이의 경로에 각각의 신호 지연을 부여하고, 상기 클럭 주기 이상의 전체 지연을 부여하는 회로내 경로들에는 적어도 하나의 플립플롭이 제공되는, 상기 동기식 디지탈 전자 회로 설계 방법에 있어서,

   임의의 셀로부터 나오는 임의의 서브 경로에 대한 임의의 셀로부터 시작하여 똑같은 방향으로 관련 지연이 축적되고, 상기 지연에 의해 소정의 정수의 상기 클럭 주기들을 초과할 때 상기 서브 경로에 상기 소정의 수의 플립플롭들의 후속 제공을 위한 신호를 보내어 그 축적이 종료되며, 이어서 상기 신호 전송에 따라 최소의 플립플롭들이 모든 기본 셀-대-셀 접속들에 제공되는 것을 특징으로 하는, 동기식 디지탈 전자 회로 설계 방법.
2. 제 1 항에 있어서,

   상기 소정의 수는 1인, 동기식 디지탈 전자 회로 설계 방법.
3. 제 1 항 또는 제 2 항에 있어서,

   두 특정 셀들 간에 다중 서브 경로 패턴이 존재할 때 상기 두 셀들 중수렴(converging) 셀에 도달할 때 서브 경로가 최저 가중치를 갖도록 하기 위해 임의의 상기 서브 경로의 추가 축적을 종료하는, 동기식 디지탈 전자 회로 설계 방법.
4. 제 1 항에 있어서,

   상기 소정의 수는 다수를 포함하는 범위 내에서 경로 방식으로 할당되며, 두특정 셀들 간에 다중 서브 경로 패턴이 존재하는 경우 상기 두 셀들 중 상기 수렴 셀에 도달할 때 하나의 셀이 최고 축적 결과를 갖도록 하기 위해 임의의 상기 서브경로 추가 축적을 종로하며, 상기 축적은 정규화된 상기 지연 대 상기 경로의 고유가중치 부여로 감소된 상기 클럭 주기인, 동기식 디지탈 전자 회로 설계 방법.
5. 제 1 항 또는 제 2항 또는 제 4항 중 어느 한 항에 있어서,

   상기 신호 전송에 의해 나타난 타이밍 제한 조건을 유지하면서 존재하는 하나 이상의 선택적인 플립플롭들에서 후속 노드-방식 탐색 동작을 포함하는, 동기식 디지탈 전자 회로 설계 방법.
6. 제 1 항 또는 제 2 항 또는 제 4 항 중 어느 한 항에 청구된 바와 같은 방법을 실현하기 위한 장치에 있어서,

   회로 설명을 수신하기 위한 입력 수단, 신호 지연들을 경로 방식으로 축적하기 위해 상기 입력 수단에 의해 공급되는 지연 합산 수단, 상기 지연을 임계 정수로 식별하기 위해 상기 합산 수단에 의해 공급되는 식별 수단, 및 상기 임계 정수를 초과함에 따라 최소로 상기 회로 설명에 플립플롭들을 삽입하기 위해 상기 식별 수단에 의해 공급되는 플립플롭 삽입 수단을 포함하는, 장치.
7. 제 1 항, 제 2 항 또는 제 4 항 중 어느 한 항의 방법에 따라 설계되며, 플립플롭들을 선택적으로 위치시킴으로써 네트들에 의해 상호 접속되고 소정의 클럭 주기로 동작하는 셀들 및 클럭킹된 플립플롭들을 포함하는 동기식 디지탈 전자 회로로서, 상기 동기식 디지탈 전자 회로의 임의의 셀이 상기 셀의 입/출력 쌍사이의 경로에 각각의 신호 지연을 부여하고, 상기 클럭 주기 이상의 전체 지연을 부여하는 회로내의 경로들에는 적어도 하나의 플립플롭이 제공되는, 상기 동기식디지탈 전자 회로에 있어서,

   임의의 셀로부터 나오는 임의의 서브 경로에 대한 임의의 셀로부터 시작하여 똑같은 방향으로 관련 지연이 축적되고, 상기 지연에 의해 소정의 수의 상기 클럭 주기들을 초과할 때 상기 서브 경로에 상기 소정의 수의 플립플롭들의 후속 제공을 위한 신호를 보내어 그 축적이 종료되며, 이어서 상기 신호 전송에 따라 최소의 플립플롭들이 모든 기본 셀-대-셀 접속들에 제공되는 것을 특징으로 하는, 동기식 디지탈 전자 회로.