When a compiler synthesizes circuits from high-level descriptions, it duplicates functional units that must be used twice in a single clock to prevent misbehavior caused by conflicts. In imperative synchronous languages, a statement may be executed more than once in a single clock due to the combination of loop constructs and the perfect synchrony hypothesis; which is a schizophrenic statement. To cure schizophrenic statements, a compiler has to duplicate them to avoid multiple executions in a clock. However, if the corresponding circuit of a schizophrenic statement can perform multiple semantic behaviors in a single clock, it is harmless and thus curing is not necessary. A schizophrenic problem has to be cured when imperative synchronous languages are compiled to other computation models (software or propositional logic).
Esterel is an imperative synchronous language. Imperative features and preemption mechanisms of Esterel help to describe control-intensive embedded systems and protocols. When a program in Esterel is translated to hardware circuit, functional units in a loop statement that can be executed more than once in a clock may cause schizophrenic problems: unstable cycle or wrong behavior. Schizophrenic problems have been previously defined by the instantaneous reentrance to local signal declarations and parallel statements. Compilers cure the problems in circuits by breaking combinational cycles with circuit duplication. But, we observe that the reentrance of two block statements are neither necessary nor sufficient conditions for harmful schizophrenic statements. Exact schizophrenia detectors can reduce the number of statements to be cured. If compilers can reduce the number of statements to apply curing techniques, the resultant circuits can be smaller due to avoiding unnecessary logic duplications. The accuracy of schizophrenia detectors is just as important for the synthesis of smaller circuits as the optimization of curing techniques.
All schizophrenic statements do not need to be cured during circuit translation. In this thesis, we identify the conditions in which a schizophrenic statement of the Esterel program must be cured during circuit translation. We also propose an algorithm to detect schizophrenic statements that have to be cured on the control flow graphs (CFGs) of source codes. Our algorithm detects all schizophrenic statements that have to be cured and results in fewer false alarms on the benchmark programs used in the previous work.
In addition, we apply our framework to another imperative synchronous language, Quartz. We extend the detection algorithm for modular analysis. Our detection framework is simple and based on the CFG of a program so that it can be merged into existing compilers easily.
고급언어로 작성된 프로그램을 컴파일하여 회로를 생성할 경우, 고급언어와 회로에서의 의미 차이로 인해 하나의 회로가 한 클록에 중복수행 되는 경우가 종종 발생한다. 회로의 중복수행은 기능적/전기적 문제를 일으킬 수 있기 때문에 컴파일러는 중복수행 되는 회로를 복사하여 중복수행을 피한다. 특히, 절차형(imperative) 동기(synchronous) 언어로부터 회로를 생성할 경우, 루프 구조와 이상적 동기화 가정(perfect synchrony hypothesis)이 서로 맞물려 한 문장이 한 클록에 중복수행 되기도 한다. 이러한 문장을 중복수행 문장(schizophrenic statement)라고 한다. 중복수행 문장이 문제를 일으키지 않게 하기 위해, 이러한 문장들을 컴파일 할 때는 해당 문장을 위한 회로를 중복 생성하여 하나의 회로가 한 클록에 중복수행 되지 않도록 한다. 하지만, 중복수행 문장에 해당하는 회로 부분이 중복수행 되더라도 문제를 일으키지 않으면 우리는 해당 문장을 컴파일할 때 회로 복제를 하지 않아도 된다. 이와 같은 중복수행 문장은 회로 컴파일 때 뿐 아니라 절차형 동기 언어를 소프트웨어나 논리식으로 컴파일 할 때도 문제를 일으킬 수 있으므로 주의를 요한다.
Esterel은 절차형 동기 언어이다. Esterel에서의 절차형 언어의 특성과 선점(preemption) 구조의 조합은 제어 시스템이나 프로토콜(protocol)을 표현할 때 많은 도움을 준다. Esterel로 작성된 프로그램을 회로로 컴파일할 경우, 루프 바디 부분은 한 클록에 두 번 이상 수행될 수 있어서 루프에 해당하는 회로 부분이 전기적으로 불안정하거나 원 기능을 잘못 수행하는 문제를 일으킬 수 있다. 이러한 문제점을 중복수행 문제(schizophrenic problem)이라고 한다. 기존 연구에서 이러한 문제점은 지역변수선언문이나 병렬문이 중복수행될 경우에 일어난다고 하였다. 그리고 이러한 문제점을 해결하기 위해 기존 Esterel 컴파일러들은 중복수행 되는 회로를 하나 더 생성하여 하나의 회로가 중복수행 되지 않게 하는 해결책(cure)을 사용하고 있다. 하지만, 우리는 기존 연구에서 제시한 두 가지 문장들이 중복수행 될 때 항상 문제를 일으키는 것은 아닐 뿐 아니라, 다른 문장도 중복수행 될 경우 문제를 일으킬 수 있다는 것을 알았다. 중복수행 문제를 일으키는 문장을 정확히 알아내면 중복사용 해결책을 적용하는 횟수를 줄일 수 있다. 그렇다면 해결책 적용 시 생기는 불필요한 회로 복사를 줄일 수 있어 컴파일시 생성하는 회로의 크기를 줄일 수 있다. 즉, 해결책의 최적화만큼이나 중복수행 문제를 일으킬 수 있는 문장을 정확히 찾아내는 것이 생성하는 회로의 크기를 줄이는데 있어 중요한 역할을 한다.
한 문장이 중복수행 되더라도 항상 중복수행 문제를 일으키는 것은 아니다. 먼저 우리는 Esterel에서 어떤 문장이 어떤 조건에서 중복수행되 더라도 회로로 변경 시 문제를 일으키지 않는지를 조사하였다. 그리고 이 조건을 바탕으로 중복수행 문제를 일으키는 문장을 검출하는 알고리즘을 제시한다. 본 알고리즘을 적용하기 위해 Esterel 프로그램에 대한 제어흐름 그래프(control flow graph) 생성 방법도 제시한다. 소스코드에서 제어흐름 그래프를 생성하여 적용하는 본 알고리즘은 문제를 일으킬 수 있는 모든 문장을 찾아내면서도, 벤치마크 프로그램 실험에서 기존 검출기들보다 훨씬 적은 허위 경보(false alarm)를 보여 주었다.
추가적으로, 앞에서 소개한 검출 방법을 또 다른 절차형 동기 언어인 Quartz에도 적용하였다. 또한 검출 알고리즘을 모듈 단위 분석법(modular analysis)으로 확장하는 방법을 보인다. 우리의 검출 방법은 제어흐름 그래프를 바탕으로 한 알고리즘을 사용하고 있기 때문에 기존 컴파일러들에도 쉽게 적용할 수 있을 것이다.
