동기식 설계

디지털 집적 회로(IC)를 설계하는 사람은 설계의 정확성에 매우 민감하다. 소프트웨어와 달리 IC는 손쉽게 테스트할 수 없기 때문이다. 실제 테스트는 설계가 확정되고 칩이 제조된 뒤에야 가능하다.

디지털 IC의 동작을 시뮬레이션하고 완성된 칩이 제대로 동작하리라는 것을 어느 정도 보장하기 위해, 오늘날의 디지털 IC는 거의 모두 동기식 설계(synchronous design) 를 따른다.

동기식 설계에서는 외부 클럭 신호가 IC를 잘 정의된 안정 상태에서 다음 안정 상태로 전이시킨다. 클럭의 활성 에지(active edge)에서 모든 입력, 출력, 내부 노드는 high 또는 low 중 하나로 안정되어 있다. 연속된 두 클럭 에지 사이에서는 신호와 노드가 값을 바꿀 수 있으며 임의의 중간 상태를 거칠 수 있다. 동기식 네트워크의 동작은 예측 가능하며, 실제 회로의 불완전성에서 비롯되는 해저드나 글리치 때문에 오작동하지 않는다.

IC가 올바른 동기식 설계인지 판단하기 위해 노드를 동기(synchronous) 노드와 비동기(asynchronous) 노드로 구분한다.

• 플립플롭은 동기 노드다. 클럭의 활성 에지에서 플립플롭의 출력은 입력 상태를 취하고, 그 상태를 다음 클럭 주기 동안 유지한다. 동기 노드는 클럭 신호에 연결되어 있다.
• AND, OR 같은 단순 게이트는 비동기 노드다. 이 노드의 출력은 입력 중 하나라도 바뀌면 짧은 지연 후에 바뀌며, 그 전이 구간 동안 출력은 잠시 정의되지 않은 중간 상태가 될 수 있다.

단순화를 위해, 회로의 모든 입력은 회로 밖 동기 노드의 출력에 직접 연결되고, 회로의 모든 출력은 회로 밖 동기 노드의 입력에 직접 연결된다고 가정한다.

IC가 올바른 동기식 설계가 되려면 다음 두 조건을 모두 만족해야 한다.

1. 클럭 주기. 두 동기 노드 사이의 모든 경로에서 발생하는 신호 지연은 클럭 주기 이하여야 한다. 그래야 모든 노드가 안정될 시간이 충분하다. 예를 들어 누적 지연이 43ns인 경로는 클럭 주기 30ns를 위반한다.
2. 비동기 사이클 없음. 오직 비동기 노드로만 이루어진 사이클이 존재해서는 안 된다. 실제 회로에서 그런 사이클은 발진할 수 있다.

다음을 가정해도 좋다.

• 같은 노드의 임의의 입력과 임의의 출력 사이의 지연은 모두 같으며, 그 노드에 주어진 지연과 같다.
• 동기 노드는 지연이 전혀 없다.
• 모든 연결은 한 노드의 출력을 다른 노드의 입력에 잇는다.

주어진 동기·비동기 노드 네트워크(각 노드의 지연 포함), 입력과 출력, 그리고 클럭 주기에 대해, 그 회로가 올바른 동기식 설계인지 판정하는 프로그램을 작성하라.

입력은 여러 개의 회로로 이루어진다. 첫 번째 줄에는 회로의 개수가 주어진다.

각 회로에 대해:

• 첫 번째 줄에는 클럭 주기가 나노초 단위 정수로 주어진다.
• 두 번째 줄에는 노드의 개수가 주어진다.
• 이어지는 각 줄은 하나의 노드를 문자 하나와 정수 하나로 나타낸다. 문자는 입력이면 i, 출력이면 o, 비동기 노드면 a, 동기 노드면 s다. 정수는 그 노드가 유발하는 지연으로 나노초 단위이며, 비동기 노드에서만 의미가 있다. 노드에는 0부터 시작하는 번호가 순서대로 암묵적으로 붙는다.
• 그다음 줄에는 연결의 개수가 주어진다.
• 이어지는 각 줄에는 두 정수 u v가 주어지며, 노드 u의 출력에서 노드 v의 입력으로 이어지는 연결을 뜻한다.

클럭 신호 자체는 입력에 주어지지 않는다. 모든 동기 노드는 클럭 신호에 올바르게 연결되어 있다고 가정한다.

각 회로에 대해 다음 중 하나의 문장을 한 줄로 출력한다.

• 회로가 올바른 동기식 설계이면 Synchronous design. Maximum delay: <ss>. 를 출력한다. 여기서 <ss>는 두 동기 노드 사이의 어떤 경로에서든 나타나는 가장 큰 지연으로 바꾼다.
• 오직 비동기 노드로만 이루어진 사이클이 있으면 Circuit contains cycle. 를 출력한다.
• 비동기 노드만으로 이루어진 사이클이 없고, 두 동기 노드 사이에 클럭 주기보다 긴 경로가 있으면 Clock period exceeded. 를 출력한다.

여러 조건이 동시에 해당할 수 있을 때에는 비동기 사이클을 가장 먼저 보고한다.