\documentclass[a4paper]{article} \usepackage{hangul,a4} %\setstretch{1.0} %\textwidth 105mm %\hyphenation{non-faul-ty cl-ock for-malism } \begin{document} \tableofcontents % ---- Title ---- \section{序論} 다중 프로세서로 構成된 실시간 시스템에서의 故障허용성은 날로 그 重要性이 더해지고 있다. 이러한 시스템의 高信賴性을 위하여 시스템에서 유지하는 클럭 역시 信賴度가 높아야 한다. 일반적으로 시스템을 이루는 각각의 프로세서들은 자신의 클럭을 지니고 있으며 이들의 클럭을 動機시켜서 전체 시스템을 動機 시킨다. 이러한 클럭 動機 方法은 비잔틴 故障(Byzantine Fault)이라는 최악의 故障에도 動機를 이룰수 있어야 한다. 한 클럭이 비잔틴 故障이라는 것은, 다른 클럭에게 각각 다른 信號를 보내주어서 信號를 받는 클럭마다 그 정보가 다르게 認識되도록 할 수 있는 故障을 의미한다. 이러한 故障허용 클럭 動機에 대한 問題는 크게 두가지의 다른 方式으로 解決하려는 연구가 진행되어 왔다. 프로세서들이 유지하는 클럭을 메시지 交換 方法으로 서로 交換하여 전체클럭(global clock)을 추정하여 動機를 이루는 方式인 소프트웨어方式은, 클럭 動機 알고리즘의 수행과 메세지 交換으로 인해 發生하는 시간지연의 크기등으로 인해 稠密한(tight)動機를 이룰 수 없는 단점을 지니고 있다. 반면 부가적인 하드웨어에 의해 動機를 이루는 하드웨어 方式은 時間 오버헤드를 유발하지 않으면서 매우 稠密한 動機를 이룰 수 있기 때문에 시간의 정확성이 요구되는 실시간 시스템에 적합한 方法이다. 현재까지 제안된 하드웨어 方式의 클럭 動機 方法은 위상고정 클럭(phase-locked clock) 알고리즘을 使用한 方式이다. 이러한 方式을 使用한 기존의 연구는 주로 참조 클럭의 선택에서 비잔틴 故障의 영향을 배제하기 위한 방향으로 연구되어 왔다. Chrishna등은 자신의 클럭 빠르기 순서에 따라서 가변적으로 참조 클럭을 결정하는 알고리즘을 제안 하였다. ([Chri85]) 그러나, 이 알고리즘을 使用하여 클럭 시스템을 구현하면([Shin87], [Choi90]) 클럭 접수 회로가 매우 복잡하게 되며, 복잡성으로 인해 발생한 회로지연(circuit delay)의 영향으로 안정된 클럭 動機를 이루기 어렵게 된다. 즉, 입력된 클럭의 순서화(ordering)을 바탕으로한 참조클럭 선택이라는 복잡한 기능을 수행하고 나서 선택된 참조 클럭을 위상고정클럭에 입력되는 형태에서 벗어 나지 않고 있는데, 참조 클럭을 선택하는 회로의 복잡성은 회로지연을 야기시키고 그로인해 전체클럭이 불안정한 動作을 하게 되는 문제점을 지니고 있다. 또다른 문제점으로는 디지탈 회로(클럭접수회로)와 아날로그회로(위상고정클럭)의 혼합된 형태를 띄고 있으므로 전체 회로의 動作을 分析하기가 어려워서 최대 편차에 대한 分析이 이루어지지 못한 점을 들 수 있다. 여기서, 최대 편차란 정상의 클럭들간에 가질 수 있는 최대의 클럭 편차를 말한다. 최대 편차를 알지 못한다면 전체 클럭動機가 얼마나 잘 이루어지고 있는지 알 수 없는 것이므로 최대 편차를 分析하는 것은 매우 중요한 일이다. 본 論文에서는 기존의 위상 고정 클럭을 使用하지않고 디지틀 회로를 기본 클럭으로 使用하는 하드웨어 클럭動機 方法을 제안한다. 이 方式은 소프트웨어 方式에서 使用하는 CNV알고리즘([Lamp85])을 하드웨어 方式에 적합하도록 변형하여 적용한 것이다. CNV알고리즘은, 입력된 다른 클럭들과 자신의 클럭과의 편차를 측정하여 편차를 평균하고 그 결과를 使用하여 자신의 클럭을 조정하는 方式의 알고리즘이다. 본 論文에서는 PXO(Programmable Crystal Oscillator)라고 명명된 순수 디지탈 회로를 기본클럭으로 使用 편차측정기와 편차평균기라는 간단한 회로를 使用하여 클럭動機를 이룰 수 있음을 보일 것이다. 이 方式은 기존의 하드웨어 方式의 장점인 稠密한 動機가 가능하며 아울러 시간오버헤드가 없다. 또한, 구성하고 있는 회로가 간단할 뿐 아니라 회로 지연으로 인한 영향이 거의 없으므로 動作이 안정하다. 본 論文에서는 기존의 하드웨어 方式과는 달리 최대 편차를 分析하였으므로 動機가 이루어지는 정도를 파악할 수 있게 되었다. 본 論文의 구성은 다음과 같다. 2장에서는 이론적 배경을 다루고, 3 장에서는 제안하는 方式에 대하여 자세한 설명을 기술할 것이다. 4장에서는 수치의 예를들며 제안하는 方式에 대한 논의를 다룰 것이며 5장에서는 결론을 기술한다. \section{이론적 배경 } 이장에서는 명확한 문제 정의를 위한 표기법(notation)과 정의(defi\-ni\-tion) 들을 기술할 것이다. 이것은 [Lamp85]의 형식(formalism)을 주로 이용하였다. \noindent {\bf\gr[ 정의 1]}\rm 어떤 클럭에 의해 유지되며 직접 관측 가능한 시간을 {\bf\gr클럭시간(clock time)}이라고 한다. 또한, Newtonian time frame에 의해 측정되는 것으로 가정하는 시간으로서 직접 관측이 불가능한 시간을 {\bf\gr 실제시간(real time)}이라고 한다. \noindent {\bf\gr[정의 2]}\rm $c$를 클럭시간에서 실제시간으로의 사상(mapping)이라고 정의한다. 이때 $c(T)=t$는 클럭시간 $T$일때 실제시간은 $t$임을 나타낸다. 여기서 대문자는 클럭시간과 관계있는 것이고, 소문자는 실제시간과 관계 있는 것으로 표기하기로 하자. 따라서 $C(t)=T$는 실제시간 $t$일때 클럭시간 $T$라는 것을 의미한다. 두개의 클럭 $c_1,c_2$이 {\bf\gr$\delta$-動機($\delta$-synchronized)}되었다는 의미는 \[ \left| c_1(T) - c_2(T) \right| \leq \delta \] 라는 의미이다. 여기서 $\delta$는 두 클럭 간에 발생할 수 있는 {\bf\gr 최대 편차(maximum skew)}를 나타낸다. \noindent {\bf\gr[정의 3]}\rm 클럭 $c$가 실제 시간 구간 $[t_1,t_2]$에서 {\bf\gr 유효클럭(good clock)} 또는 {\bf\gr 정상 클럭(non\-faul\-ty clock)}이려면, $c$가 구간 $[T_1,T_2]$ (단,$c(T_i)=t_i$,\penalty-5000 $i=1,2$)에서 단조(monotonic), 미분가능함수(differentiable function)이고 $[T_1$,$T_2]$에 속한 모든 T에 대해 \[ \left| \frac{dc(T)}{dT} - 1 \right| < \frac{ \rho }{2} \] 이 성립해야 한다. ( 단, $\rho$는 유효 클럭의 표류율(drift rate)을 나타내는 상수) $N$개의 클럭을 가진 시스템에서 최대 $m$개의 클럭이 故障일 수 있는 경우를 생각하자. 이때, 매 $R$초다 클럭들이 재動機(resynchronized)되고, $T^{(i)}=T^{(0)}+iR$이고, $R^{(i)}$는 $[T^{(i)},T^{(i+1)}]$의 구간을 나타낸다고 표기하자. 여기서 $R$초 마다 클럭을 {\gr 재動機} 한다는 것은 다음과 같은 논리적인 클럭 $c_p^{(i)}$를 구간 $R^{(i)}$동안 유지하는 것을 의미한다. \[ c_p^{(i)}(T) = c_p(T + C_p^{(i)}) \hspace{5em} (C_p^{(i)} \mbox{는 상수이고} ~~ C_p^{(0)} = 0 ) \] \noindent {\bf\gr[정의 4]}\rm 만약 클럭 $c_p$와 클럭 $c_q$가 실시간 구간$[c_p^{(0)}(T^{(0)}), c_p^{(i)}(T^{(i+1)})]$동안 정상이라면 클럭 $c_p$가 $T^{(i+1)}$시간까지 정상이라고 생각한다. (이시간 구간은 클럭 $c_p$의 시작시간 부터 $i$번째 재動機 끝가지의 시간을 의미한다.) 이러한 정의를 使用하여 두가지의 {\bf\gr클럭動機 조건 (clock synchronization condi\-tion)}을 기술하면 다음과 같다. \noindent {\bf\gr[조건 S1]} 만약 클럭 $c_p$와 클럭 $c_q$가 $T^{(i+1)}$시간까지 정상이라면, 어떤 상수 $\delta$에 대해 다음 식이 성립한다. \begin{eqnarray*} \left| c_p^{(i)}(T) - c_q^{(i)}(T) \right| < \delta ~~~~~~~~~~\forall T \in R^{(i)} \end{eqnarray*} \noindent {\bf\gr[조건 S2]} 만약 클럭 $c_p$가 $T^{(i+1)}$시간까지 정상이라면, 어떤 상수 $\Sigma$에 대해 다음 식이 성립한다. \begin{eqnarray*} \left| C_p^{(i+1)} - C_p^{(i)} \right| < \Sigma \end{eqnarray*} 이러한 두가지 조건 S1,S2를 만족하는 알고리즘과 그 구현 方法에 대하여 다음장에서 논의 할 것이다. \section{제안하는 方式} 이 절에서는 제안하는 方式에 대한 설명을 기술한다. 제안하는 方式은 CNV알고리즘을 기본으로하는 것이다. 여기서는 이 CNV 알고리즘을 수정한 MCNV 알고리즘을 설명하고 이를 하드웨어로 구성한 회로에 대한 설명과 分析을 기술할 것이다. \subsection{Modified CNV 알고리즘} 먼저 CNV알고리즘의 動作을 기술하면 다음과 같다. 다른 클럭을 입력받아 자신의 클럭과의 편차를 측정한 후, 이 편차가 일정한 문턱치(threshold) 를 넘으면 편차를 0으로 한다. 이렇게 조정된 편차들을 평균하면 추정된 편차(estimated skew)가 계산된다. 이 추정된 편차를 使用하여 자신의 클럭을 조정한다. 다음은 MCNV알고리즘이다. \noindent \fbox{\bf\gr 알고리즘 MCNV} :~ 모든 $p$에 대해 \paragraph{알고리즘 MCNV} \[ \begin{array}{l} C_p^{(i+1)} = C_p^{(i)} + \alpha \Delta_p \\ \mbox{~~~where~} \begin{array}[t]{l} \Delta_p \equiv \left( \frac{1}{n} \right) {\displaystyle \sum_{r=1}^{n} \bar{\Delta}_{rp} }\\ \bar{\Delta}_{rp} \equiv \mbox{\bf~if~} r \not= p \mbox{\bf~and~} \left| \Delta_{rp} \right| < \Delta \begin{array}[t]{l} \mbox{\bf~then~} \Delta_{rp} \\ \mbox{\bf~else~} \beta \\ \end{array} \\ ~~{\displaystyle \alpha \equiv \frac{n}{2^{ \lceil {\log}_2 {n} \rceil }} \mbox{\bf~or~} \frac{n}{2^{ \lceil {\log}_2 {(n-1)} \rceil + 1}}}\\ ~~~~~~\mbox{($\alpha$는 두가지 중, 1에 더 가까운 수로 결정)} \\ ~~\Delta \approx \delta + \varepsilon \\ ~~\beta < |\Delta| \end{array} \end{array} \] 이 알고리즘은 CNV알고리즘과 다음 두가지 면에서 다르다. \begin{itemize} \item 클럭 편차를 측정할 때 故障에 견디도록 문턱치를 초과하면 0으로 계산하게 하는 점을 완화하여 문턱치보다 작은 절대값을 갖는 임의의 값을 취할 수 있도록 하였다. 따라서, 이것은 하드웨어 설계를 간단하게 한다. 왜냐하면 단지 업다운(Up/Down) 카운터를 使用하면 되기 때문이다. 즉, 카운터가 셀 수 있는 수보다 절대값이 큰 수를 셀때는 오버플로우(overflow)나 언더플로우(underflow)현상이 발생되어 일정한 절대값보다 작은 수를 센 것이 되기 때문이다. \item 측정된 편차를 평균하여 추정 편차를 구하고,이 추정 편차를 자신의 클럭을 조정하는데 직접 使用하지 않고 $\alpha$라는 因數를 곱한 값을 클럭 조정에 使用하게 하였다. 이 $\alpha$는 정의한 바와 같은데 이것은 평균을 구할때 $n$으로 나눗셈을 계산하지 않고 $n / \alpha $ 즉, $2^{ \lceil {\log}_2 {n}\rceil }$ 또는 $ 2^{ \lceil {\log}_2 {(n-1)} \rceil +1}$으로 나눌수 있도록 한 것이다. 이 부분은 쉬프터(shifter)를 使用하여 간단히 구현 가능하다. \end{itemize} 즉, MCNV알고리즘은 CNV알고리즘을 하드웨어로 간단히 구현하기 위하여 수정한 형태이다. \subsection{MCNV 알고리즘의 하드웨어 具現} 이 절에서는 3.1절에서 설명한 MCNV알고리즘을 하드웨어로 구현하는 것에 대해 설명한다. 그림 1 에서 보는 바와 같이 하드웨어 블럭은 3개로 나누어져 있다. 편차측정회로,편차평균기는 MCNV알고리즘에서 추정 편차인 $\alpha \Delta$를 구하는 블럭이고, 추정 편차를 使用하여 자신의 클럭을 조정하는 기능을 가진 블럭은 PXO이다. \noindent {$\bullet$ \bf\gr 편차측정회로(Skew Measuring Circuitry):} 이 블럭은 외부에서 입력받은 클럭 信號와 자신의 클럭과의 편차를 측정하는 부분이다. 이 블럭은$n-1$개의 동일한 작은 소블럭으로 이루어 진다. 입력 클럭 信號는 각각의 소블럭에 입력된다. 이 소블럭은 그림 2에 나타나있는 바와 같이 1개의 업다운 카운터(up/down counter)와 약간의 논리 소자(logic gate)를 使用하여 간단히 설계 가능하다. 이것은 $C_{hf}$를 이용하여 편차를 측정하게 된다. 이 소블럭의 動作은 그림 3의 시간 도표(timing diagram)에 나타나 있다. 여기에서 $C_i$는 이 소블럭으로 입력되는 외부 클럭 信號이며 $C_s$는 자신의 클럭이다. 클럭 측정은 매 클럭 마다 이루어 진다. 카운터 입력인 Enable이 '1'이 되어 카운트가 시작될 때는 $C_i$와 $C_s$중 어느 한가지 클럭 信號의 입력이 '1'이 된 경우이다. 카운터의 증감의 방향은 자신의 클럭 $C_s$이 $C_i$보다 먼저 '1'이 된 경우 증가하는 방향이 된다. 반대로 $C_i$가 먼저 $C_s$보다 먼저 '1'이 된 경우 감소하는 방향이 된다. 이것은 단지 $C_s$를 Up/Down에 연결하면 된다. 따라서 출력되는 측정된 편차는 2의 보수로 표현 된다. 이와 같은 方式으로 편차를 측정할때 故障 상태의 클럭이 입력된 경우를 생각해보자. 이때는, 입력된 클럭과의 편차의 절대값이 카운터의 한계인 $2^{k-1}$보다 큰 경우이다. 그러나 이 소블럭의 출력은 절대값이 $2^{k-1}$보다 작은 값이 된다. 위에서 기술한 바와 같이 MCNV알고리즘은 이경우 입력된 편차의 절대값이 일정한 문턱 값보다 작으면 되므로 이 소블럭의 출력을 그대로 使用하면 된다. 이렇게 측정된 편차는 다음 단계인 편차 평균기로 전달된다. \noindent {$\bullet$ \bf\gr편차 평균기(Skew Averager):} 이 블럭은 측정된 편차를 평균하는 기능을 수행한다. 이 블럭은 편차를 합하는 합산기 부분과 나눗셈을 하는 쉬프터로 나누어진다. 합산기 부분에서는 입력된 측정 편차들을 모두 더하여 전체 합을 구하는 기능을 담당한다. 이것은 이진 트리를 형성하는 이진 덧셈기를 使用하여 간단히 구현된다.(그림 4) 이와 같이 이진 트리로 합산기를 구성한다면 2의 멱수 개의 입력단자가 존재하므로 잉여의 입력 단자가 발생하기 쉬운데 이 단자들은 0이 입력되도록 하면 된다. 이와 같이 합산된 편차는 쉬프터를 통해 나누어진다. 이진 쉬프터는 2의 멱수로 나눗셈하는데 적합하다. 쉬프터로 나눗셈을 수행할때 젯수는 $2^{ \lceil {\log}_2 {n}\rceil }$ 또는 $2^{ \lceil {\log}_2 {(n-1)} \rceil +1} $이다. 이점은 MCNV알고리즘의 使用으로 정당화 된다. 이와 같이 편차 평균기는 간단히 구현 가능하다. 편차 평균기의 출력은 추정 편차(Estimated Skew)이다. 이 추정 편차는 PXO에 입력되어 클럭을 조절하게 한다. \noindent {$\bullet$ \bf\gr PXO(Programmable Crystal Oscillator):} 이 블럭은 클럭 信號를 공급하는 부분이다. ( 그림 5 ) 여기서 출력하는 클럭 信號는 고 주파수 클럭(high freqency clock) $C_{hf}$를 일정한 비율로 분주하여 발생 된다. 이 블럭에서는 입력으로 추정 편차를 받아서, 클럭의 위상에 가감하여 클럭 信號를 조정하는 기능을 수행한다. 이 블럭은 한개의 카운터와 여러개의 논리 소자로 구성된 간단한 형태를 이루고 있다. 카운터는 $C_{hf}$의 고주파 클럭을 일정한 비율로 분주하여 자신의 클럭을 생성하는 역할을 한다. 즉, 고주파 클럭이 64MHz이고 분주비율이 16이라면 4MHz의 클럭을 생성하게 되는 것이다. 즉, 카운터는 $C_{hf}$를 일정한 수로 분주하되 필요에 따라 분주되는 수를 변화 시켜 클럭의 빠르기를 조정하게 한다. 클럭의 빠르기가 조정되는 것은 일시적으로 한 주기에서만 이루어진다. 즉, 빠르기는 필요가 생길때만 조정되고 조정이 되는 주기가 끝나면 원래대로 정해진 비율로 분주를 행한다. 빠르기의 조정은 추정 편차의 값에 의존하여 이루어진다. 즉, 추정 편차의 값이 양수이면, 편차 곱하기$C_{hf}$의 주기의 시간 만큼 자신의 클럭을 앞당기고, 음수이면 그 절대값 만큼 클럭을 늦춘다. 이러한 기능을 갖는 PXO의 回路가 그림 5에 나와 있다. 動作을 좀 더 자세히 설명하면 다음과 같다. 이 블럭에서 추정 편차는 클럭 信號가 '1'에서 '0'으로 전이 할때 카운터의 입력단자에 로드(load) 된다. 또한, 클럭 信號가 '0'인 동안에는 로드된 이 추정편차를 써서 클럭의 주기를 조정함으로서 클럭의 빠르기를 변화 시킨다. 추정 편차가 카운터의 입력 데이터로 로드된다. 이렇게 로드가 이루어진후 카운터는 계속 動作한다. 따라서, 클럭 信號의 '0' 부분에서 추정 편차의 크기 만큼 줄어들게 된다. 추정 편차가 음수 인경우는 약간 다르게 作動한다. 이 경우는 클럭信號의 길이를 줄여야한다. 먼저 로드는 양수와 같이 이루어 진다. 음수가 로드되었으므로 '0' 이어야하는 클럭 출력이 '1'이 되므로 이것을 방지하는 부분이 AND 素子의 役割이다. 즉, 음수의 입력이 된 상태에서는 출력을 {'0'} 되도록 하는 것이다. \section{알고리즘의 증명및 分析} \input a \section{수치적인 예} 위의 scheme들을 실제 구현할때의 예를 들어 수식들의 의미를 살펴보면 다음과 같다. 즉, $n=7$인 시스템에서 다른 因數(parameter)들을 정하는 것을 살펴보자. $\alpha$의 선택은 전술한 바와 같이 1에 가까운 값으로 정하도록 한다. 먼저 $\alpha = { 7 \over 4 }$또는 ${ 7 \over 8 }$에서 ${7 \over 8}$을 선택한다. 또한 m은 $m<{10\over 3}7$ 이므로 $m=2$이다. 실제 시스템에서 $\rho$는 $10^{-6}$정도 이고, $\varepsilon$은 대략 10 ns 정도이다. 이때 재動機를 매 클럭 주기마다 수행하는 경우를 생각하므로, $\rho R$은 무시할 정도로 작다. 따라서 \begin{eqnarray*} \delta & > &\mbox{max} \left\{ {(4-2\alpha)n +(4\alpha-4)m \over (2\alpha-1)n-(4\alpha-1)m} \varepsilon, \delta_0 \right\} \end{eqnarray*} 을 使用하여 $\delta$를 계산할 수 있다. 따라서 $\delta > 59 \varepsilon$이므로 $\delta > 590$ns 이다. 따라서 이와 같은 因數들을 使用할때 대략 한 주기가 840kHz정도 이하이면 作動하게 된다. 여기에서 수식을 살펴본 바와 같이, $\alpha$의 크기가 작을수록 $\delta$가 커지므로 가급적 $\alpha$가 1에 가까와 지도록하는 설계하는 것이 필요하다. 즉, $\alpha$가 1인 경우인 $n=4$이면 $\delta$는 80 ns 정도로 작아진다. 여기에서 또한 고려해야 할 점은 $n$을 크게 설계하면 나쁘다는 것이다. $n$을 크게 하면 먼저 fan-in, fan-out이 커야하는 문제점을 일으키며, 위의 方法에서 $\delta$가 $n$에 비례하여 커지므로 稠密한 動機를 이루는데 지장이 생긴다. \section{結 論} 본 論文에서는 소프트웨어 方式의 알고리즘에 기반을 둔 새로운 하드웨어 方式에 대하여 다루었다. 하드웨어로 구현이 용이하도록 기존의 소프트웨어 方式의 알고리즘을 수정하였으며 이 方式이 쉽게 구현됨을 알 수 있도록 구체적인 설계를 보였다. 이 方式은 기존의 하드웨어 方式의 장점들을 계속 지니면서, 문제점으로 제기된 클럭접수회로의 회로지연 문제도 解決하는 특징을 지니고 있다. 또한, 최대 편차를 分析하여 클럭動機가 얼마나 잘 이루어 지고 있는지 분명히 알 수 있게 되었는데 이것은 기존의 하드웨어 方式에서는 알려지지 않았던 것이다. \newpage \input p \end{document}