제어 성능을 고려한 오토사 러너블 스케줄링

1. 서 론

자동차 업계는 차량 제어 애플리케이션 개발시 오토사(AUTomotive Open System ARchitecture, AUTOSAR) 차량용 표준 소프트웨어 아키텍처를 이용한다.^1-3) 오토사 기반 제어 애플리케이션은 복수의 소프트웨어 컴포넌트(Software Component, SWC)들이 서로 연결되어 구성되고 각 소프트웨어 컴포넌트는 1개 이상의 러너블(Runnable)로 구성된다. 러너블은 최소 실행 단위인 함수이며 일반적으로 각 러너블은 정해진 주기마다 실행된다.^4,5) 이 때, 한 소프트웨어 컴포넌트에 속한 러너블들은 서로 다른 주기를 가질 수 있다.

러너블 주기는 제어 시스템 동작의 시간 특성을 결정하며 이는 제어 성능에 큰 영향을 미친다. 같은 제어 알고리즘도 제어 빈도와 센서에서 액추에이터까지의 지연시간의 변화에 따라 전혀 다른 제어 성능을 보일 수 있다.^6,7) 일반적으로 러너블 주기를 짧게 할수록 더 좋은 제어 성능을 얻을 수 있지만, 이 경우 CPU 부하가 커지기 때문에 무조건 러너블 주기를 짧게 할 수는 없다. 그렇기 때문에 제한된 CPU 부하 수준에서 최적 제어 성능을 발휘할 수 있는 러너블 주기를 찾을 필요가 있다.

현재 산업계에서는 Ad-hoc 방식으로 러너블 주기를 결정하는 경우가 대부분이다. 애플리케이션 개발자는 각 러너블에 다양한 주기를 부여하면서 제어 성능을 비교하고 경험에 의존해 가장 좋은 결과의 러너블 주기가 결정된다. 이러한 러너블 주기 결정 방법으로는 최적의 러너블 주기를 결정할 수 없다.

이러한 문제를 해결하기 위해 본 논문은 최적 제어 성능을 가지는 러너블 주기를 찾는 오토사 러너블 스케줄링 방법을 제시한다. 이 문제를 해결하기 위한 첫 번째 시도로 우리의 이전 연구는 러너블들이 선형 혹은 체인 형태의 데이터 의존 관계를 가질 경우에 한해서 조합최적화 문제로 정형화하여 해결하였다.^8,9) 하지만 이 방법은 러너블의 수가 많아지면 최적화에 걸리는 시간이 기하급수적으로 증가하고 선형 러너블 구조가 아닌 복잡한 구조에 적용할 수 없는 문제가 있다.

위의 두 한계점, 즉 (1) 계산량의 문제와 (2) 복잡한 러너블 구조에 적용 불가능한 점을 개선할 필요가 있고 이를 위해 본 논문은 계산량의 문제를 해결하기 위해 선형 러너블의 최적화 문제를 라그랑주 승수법¹⁰⁾으로 해결할 수 있음을 보인다. 이 방법을 이용하면 계산량이 많고 그에 따라 시간이 많이 걸리는 문제 공간에 대한 탐색 없이 분석적 방법으로 바로 최적의 해를 구할 수 있다. 선형 러너블 구조에만 적용 가능한 한계를 극복하기 위해 본 논문은 여러 개의 독립적인 선형 러너블 체인으로 구성된 더 복잡한 형태의 러너블 구조에 대한 해결책을 제시한다. 이를 위해 n개 러너블의 각 주기 {p₁,p₂,⋯,p_n}를 결정하는 n개 변수 최적화 문제를 더 단순한 3개 변수 최적화 문제로 변환한 후 이 문제를 다시 라그랑주 승수법을 이용하여 해결한다. 이 방법은 최적해를 구하지는 못하고 근사해를 구하게 되지만 실험 결과 이로 인한 제어 성능 저하는 2 % 이하인 것으로 확인되었다. 또한 분석적 방법을 사용함으로써 기존에 계산량이 많은 최적화 방법과 달리 최적해를 찾는데 걸리는 시간이 1 ms 이하로 매우 짧기 때문에 복잡한 시스템에 대해서도 시간 제약 없이 효과적으로 사용할 수 있음을 보인다.

논문은 다음과 같이 구성된다. 다음 장에서는 본 논문과 관련된 연구들에 관해 서술한다. 3장에서는 문제 해결을 위한 배경 지식 설명 및 본 논문에서 해결할 문제를 정의한다. 4장에서는 선형 시스템과 다층 선형 시스템 형태의 러너블 주기 결정방법에 대해 알아본다. 5장에서는 실험을 통해 본 논문에서 제시한 방법에 대한 평가를 진행한다. 마지막 장에서는 논문의 결론을 맺는다.

2. 관련 연구

제어 성능과 스케줄링을 함께 고려하는 Control-scheduling codesign 연구는 Seto 등¹¹⁾에 의해 처음 시작되었다. 이 연구는 제어 성능의 척도인 제어 비용 함수를 실시간 태스크 주기의 함수로 정의하고 이에 기반을 둔 스케줄링 알고리즘을 제시하였다. 이 연구에서는 동적 우선순위 스케줄링 방법을 이용했다. 후속 논문¹²⁾은 정적 우선순위 스케줄링 방법을 이용해 주기 결정방법을 제시했다. Du 등¹³⁾은 라그랑주 승수법과 온라인 알고리즘을 활용하여 태스크 주기를 결정하는 휴리스틱 알고리즘을 제시했다. 위 연구들은 제어 주기가 제어 성능에 영향이 있음을 증명했다.

다수의 논문을 통해 End-to-end 지연시간과 제어 성능 간의 연관성 또한 연구되었다. 김병국의 연구¹⁴⁾는 시스템의 제어 성능은 제어 주기뿐만 아니라 시스템의 End-to-end 지연시간 또한 영향을 미침을 증명했다. 이 연구에서는 제어 비용 함수를 제어 주기와 시스템의 End-to-end 지연시간에 대해 정의했다. Bini와 Cervin¹⁵⁾은 이전 논문을 확장하여 제어 성능을 제어 주기와 End-to-end 지연시간에 대한 선형 함수로 정의했다. Wu 등¹⁶⁾은 동적 우선순위 스케줄링 방법의 하나인 EDF (Earliest Deadline First) 알고리즘을 이용하여 지연시간과 제어 성능의 관계를 분석해 제어 주기와 마감 시간을 찾아내는 알고리즘을 제시했다. 하지만, 과거의 연구들은 모두 오토사 러너블이 아닌 Real-time 기반 태스크에 대한 연구라는 한계점이 있다.

오토사 러너블 스케줄링에 관한 연구는 비교적 최근에 시작되었다. 특히 초기 연구들은 러너블을 ECU에 배치하는 방법과 스케줄링하는 연구가 주를 이뤘다. Long 등¹⁷⁾은 ECU 내부에서 러너블 간의 데이터 통신을 고려한 러너블 배치 방법을 제시했다. Monot 등¹⁸⁾은 Multi-core ECU의 각 Core 별로 러너블을 배치 및 스케줄링하여 시스템의 성능을 향상시키는 연구를 진행했다. Saidi 등¹⁹⁾은 ILP(Integer Linear Programming) 기법을 사용하여 Multi-core ECU에 최소 비용을 통해 러너블 스케줄링하는 연구를 진행했다. Kehr 등²⁰⁾은 러너블과 태스크들의 병렬 연산을 통한 스케줄링 연구를 했다. 위 연구들은 러너블들의 주기가 결정된 상태에서 오토사 러너블을 ECU에 스케줄링하는 것에 중점을 두었다. 러너블의 주기를 따로 결정하는 방법에 대해서는 제시되지 않았다.

오토사 러너블 주기를 직접 결정하는 방법 연구는 우리의 이전 연구에 의해 처음으로 시작되었다.^8,9) 이 연구들은 시스템을 구성하고 있는 러너블의 주기를 검출하는 방법을 제시하였으며 검출한 러너블 주기를 사용하여 시스템 성능을 향상시킬 수 있음을 보여주었다. 그러나 시스템의 복잡도가 높은 경우 주기를 검출하는데 소요되는 시간이 상당하게 소요되어 복잡한 시스템에서는 적용하기 어렵다는 한계점이 존재한다.

본 논문에서는 이전 연구들과는 다르게 러너블 스케줄링을 통해 제어 성능을 최적화하는 알고리즘을 연구한다. 특히, 복잡한 오토사 기반 애플리케이션의 제어 성능을 고려하여 한정된 자원 하에서 최적의 제어 성능을 발휘할 수 있는 러너블 주기를 결정하는 방법을 연구한다.

3. 배경 지식 및 문제 정의

3.1 시스템 모델

본 논문은 오토사 기반의 서로 연결된 소프트웨어 컴포넌트들로 구성된 차량 제어 애플리케이션을 대상으로 한다. 각 소프트웨어 컴포넌트는 단위 함수인 러너블로 구성된다. 대상 제어 애플리케이션에 총 n개의 러너블이 있다고 가정하면 전체 시스템은 식 (1)과 같은 집합의 형태로 표현할 수 있다.

$\[ \left\{r_1,r_2,\cdots ,r_n\right\} \]$

(1)

Fig. 1은 6개의 러너블로 구성된 예제 시스템이다. 본 논문은 1개의 센서와 1개의 액추에이터를 사용한다고 가정한다. n개의 러너블 중에서 첫 번째 r₁을 센서 러너블, 그리고 마지막 r_n (Fig. 1에서는 r₅)을 액추에이터 러너블로 정의한다. 이후부터 r₁과 r_n은 별도로 언급하지 않아도 각각 센서 러너블과 액추에이터 러너블을 의미한다. r₁은 센서 데이터를 읽어서 그에 대한 처리 결과를 r₂와 r₄에 전달한다. 이때 러너블 사이의 데이터 전달은 Sender-Receiver 방식으로 구현된다. Sender 러너블이 자신의 주기 내에 연산을 마쳐 결과값을 송신하고 Receiver 러너블은 그 결과값을 자신의 주기에 비동기적으로 읽어서 자신의 연산을 수행하고 또 결과를 다른 러너블에 전달한다. 센서 러너블에서 시작된 이러한 데이터 흐름은 그래프 형태를 이루어 최종적으로 액추에이터 러너블까지 전달된다.

Fig. 1

Example AUTOSAR system made of six runnables with one input sensor and one output actuator. Each arrow means flow of data

각각의 러너블 r_i는 파라미터 p_i와 e_i를 가지며 식 (2)와 같이 표현한다.

$\[ r_i=\left(p_i,e_i\right) \]$

(2)

where,
･ p_i: r_i의 주기
･ e_i: r_i의 최악 실행시간

일반적으로 e_i는 러너블에 작성된 소스코드에 의해 결정되는 고유의 상수이며 p_i는 시스템 최적화 단계에서 임의의 값으로 설정할 수 있다. 각 러너블은 결정된 p_i에 맞춰 주기적으로 실행된다.

3.2 제어 성능 모델

제어 성능을 모델링하기 위한 제어 성능 모델은 Bini와 Cervin¹⁵⁾에 의해 정의된 선형 제어 비용 함수를 활용한다. 선형 제어 비용 함수에는 제어 주기 T와 End-to-end 지연시간 Δ가 파라미터로 사용된다. 주기 및 지연시간이 증가할수록 제어 비용이 증가하는 경향을 보여주며 제어 성능과는 반비례 관계이다. 제어 비용 함수 J는 식 (3)과 같이 표현된다. Fig. 2는 T와 Δ에 따른 J의 경향을 시각적으로 표현한 그림이다.

Fig. 2

Trend of control cost with varying control period T and varying end-to-end delay Δ

$\[ J\left(T,\Delta \right)=\alpha T+\beta \Delta \]$

(3)

where,
･ T: 시스템의 제어 주기
･ Δ: 시스템의 end-to-end 지연시간
･ α,β: 양의 실수

4. 오토사 러너블 스케줄링

오토사 러너블을 스케줄링하기 위해 제어 성능 평가 지표인 제어 비용 함수 J를 오토사 러너블 주기 p_i에 대한 식으로 변형시켜야 한다. 본 논문에서는 센서 러너블부터 액추에이터 러너블까지 선형으로 연결 되어 있는 선형 시스템과 센서 러너블부터 액추에이터 러너블까지 복수개의 선형으로 연결된 다층 선형 시스템에 대한 연구를 진행한다. 각 모델에 대한 예시는 Fig. 3과 같다. 두 모델은 서로 다른 형태로 제어 비용 함수가 정의된다. 이로 인해 모델 형태에 따라 해결할 문제 또한 재정의되며 최적 러너블 주기를 결정하는 일반식 또한 다르게 도출된다. 이번 절에서는 선형 시스템과 다중 선형 시스템에 대한 문제를 해결하는 과정을 설명한다.

Fig. 3

Example of linear runnable system and multiple layer linear runnable system

4.1 선형 시스템 모델

4.1.1 선형 시스템 모델 제어 비용 함수

식 (3)의 비용 함수 J를 오토사 러너블 주기 p_i에 대한 함수로 변형시키기 위해 먼저 T와 Δ를 p_i에 대한 식으로 변환한다.

제어 대상인 자동차의 관점에서 시스템 제어 주기 T는 액추에이터에 직접적으로 데이터를 전송하는 액추에이터 러너블 r_n과 연관이 있다. 시스템 제어 주기 T는 연속한 액추에이션 사이의 최악 시간 길이로 정의할 수 있다. 이는 r_n이 특정 주기가 시작할 때 곧바로 실행되고 그 다음에는 주기의 끝에서 실행이 종료되는 경우이다. 이때 두 액추에이션 사이의 간격은 p_n의 2배가 된다. 이를 최악 상황에서의 시스템 제어 주기 T로 정의하며 이는 식 (6)과 같다.

$\[ T=2p_n \]$

(6)

End-to-end 지연시간 Δ는 Sensor-to-actuator 지연시간이다. Fig. 4를 통해 최악 상황에서의 Δ를 설명한다. Fig. 4에는 r₁부터 r_n까지 선형으로 연결된 시스템의 데이터 흐름이 표현되어 있다. 최악의 상황에서 r₁에서의 결과값이 근소한 차이로 r₂가 시작된 직후 전달된다. 이 경우 r₂의 다음 주기에 r₁의 결과값을 전달받아 실행하게 된다. 이 때 r₂가 주기의 끝에서 실행이 종료되는 경우 r₁의 연산 결과는 p₂의 2배만큼 지연된 후 처리된다. 선형 시스템의 연결된 모든 러너블에 대해 연쇄적으로 최악 상황이 발생하면 시스템의 모든 러너블은 자신의 주기의 2배의 시간을 소요해야 정상적으로 데이터를 다음 러너블에 전달할 수 있다. 선형 시스템의 경우 연속적으로 러너블이 연결되어 있으므로 Δ는 시스템을 구성하고 있는 모든 러너블 주기 두 배의 합으로 치환한다. 이에 따라 선형 시스템의 End-to-end 지연시간은 식 (7)과 같이 정의한다.

Fig. 4

Example worst-case runnable scheduling scenario

$\[ \Delta =2p_1+2p_2+\cdots +2p_n=\sum _{i=1}^{n}2p_i \]$

(7)

최종적으로 선형 시스템에서의 선형 비용 함수 J는 식 (3), 식 (6) 그리고 식 (7)에 의해 식 (8)과 같이 나타낼 수 있다.

$\[ J\left(p_1,p_2,\cdots ,p_n\right)=\alpha \times 2p_n+\beta \times \sum _{i=1}^{n}2p_i \]$

(8)

4.1.2 선형 시스템 모델 최적화 방법

본 논문에서는 시스템의 최적화를 위해 라그랑주 승수법을 사용한다. 이를 통해 제어 비용을 최소화하는 최적화 러너블 주기 P={p₁,p₂,⋯,p_n} 를 계산하는 일반식을 도출한다. 라그랑주 승수법을 적용하기 위해 제어 비용 함수 J(P)를 라그랑주 승수법의 목적함수로, 스케줄링 함수 U(P)를 라그랑주 승수법의 제한 조건으로 정의한다. 라그랑주식 L은 식 (9)와 같이 정의할 수 있다.

$\[ \begin{array}{c}L=J\left(P\right)-\lambda \left(U\left(P\right)-1\right)\hfill \\ =\left(2\alpha p_n+2\beta \sum _{i=1}^n{p}_i\right)-\lambda \left(\sum _{i=1}^n\frac{e_i}{p_i}-1\right)\end{array} \]$

(9)

식 (9)를 P={p₁,p₂,⋯,p_n}와 λ에 대해 편미분을 진행하여 식 (10) 방정식을 해결하면 P={p₁,p₂,⋯,p_n}의 일반식이 도출된다.

$\[ \nabla L=\left(\frac{\delta L}{\delta p_1},\frac{\delta L}{\delta p_2},\cdots ,\frac{\delta L}{\delta p_n},\frac{\delta L}{\delta \lambda }\right)=0 \]$

(10)

$\[ \begin{array}{c}{p}_1=\sum _{i=1}^{n-1}\left(e_i\sqrt{\frac{e_1}{e_i}}\right)+e_n\sqrt{\frac{\left(\alpha +\beta \right)e_1}{\beta e_n}}\hfill \\ p_2=\sqrt{\frac{e_2}{e_1}}{p}_1\hfill \\ \cdots \hfill \\ p_{n-1}=\sqrt{\frac{e_{n-1}}{e_1}}{p}_1\hfill \\ p_n=\sqrt{\frac{{\beta e}_n}{{\left(\alpha +\beta \right)e}_1}}{p}_1\hfill \end{array} \]$

(11)

식 (10)을 정리하여 방정식을 해결하면 식 (11)과 같은 최적화 러너블 주기 P={p₁,p₂,⋯,p_n}를 얻을 수 있는 일반식을 도출할 수 있다.

4.2.1 다층 선형 시스템 모델 제어 비용 함수

4.2.1 다층 선형 시스템 모델 제어 비용 함수

다층 선형 시스템 모델에서 제어 주기 T는 선형 시스템 모델과 동일하게 액추에이터 러너블 주기의 두 배인 2p_n이며 이는 식 (6)과 같다.

End-to-end 지연시간 Δ를 정의하기 위해 Fig. 5를 예로 들어 다층 선형 시스템을 설명하고 설명을 돕기 위한 새로운 개념인 집합 ℙ_k를 정의한다. Fig. 5는 센서 러너블부터 액추에이터 러너블 사이의 경로가 m개 존재하는 다층 선형 시스템이다. 각 러너블은 왼쪽에서 오른쪽으로, 그리고 위에서 아래로 러너블 번호가 매겨진다. 센서 러너블과 액추에이터 러너블 사이의 러너블들은 복수 경로에 중복으로 존재하지 않으며 이는 r₂부터 r_n-1에 해당한다. 집합 ℙ_k는 이 중에서 k번째 경로 안에 있는 러너블 인덱스를 원소로 하는 집합이고 식 (12)와 같이 정의된다.

Fig. 5

Example of multiple layer linear runnable system’s paths from sensor runnable to actuator runnable

(12)

where,
･ 1 ≤ k ≤ m
･ |ℙ_k|: ℙ_k원소의갯수

복수의 경로가 있는 다층 선형 러너블 시스템에서는 각 경로마다 r₁부터 r_n까지 데이터가 전달되는 시간이 서로 다를 수 있다. 이 중에서 데이터 전달 시간이 가장 긴 경로가 제어 성능에 직접적인 영향을 미치기 때문에 이를 End-to-end 지연시간 Δ로 결정한다. 이 때 선형 시스템의 경우와 동일한 이유로 최악 스케줄링 시나리오를 가정하여 러너블 주기에 두 배를 곱하여 Δ를 식 (13)과 같이 표현한다.

$\[ \mathit{\Delta }=2p_1+\underset{k\in \left[1,m\right]}{\max }\left(\sum _{i\in {\mathbb{P}}_k}2p_i\right)+2p_n \]$

(13)

다층 선형 시스템의 경우 모든 경로의 러너블 주기의 합이 같을 때 최적의 제어 성능을 나타낸다. 만약 특정 경로의 러너블 주기의 합이 다른 경로들 보다 크다면 다른 경로의 러너블의 주기를 더 크게 하더라도 Δ는 그대로 유지되고 따라서 제어 비용도 변하지 않지만 Utilization이 감소하게 된다. 이때 확보한 Utilization을 활용하면 Δ를 더 줄여서 제어 비용을 더 감소시킬 수 있기 때문에 결과적으로 제어 비용이 최소일 때 모든 경로의 러너블 주기의 합은 같아야 한다. 이를 식 (14)의 p_*라는 변수로 정의한다.

$\[ p_{\mathrm{*}}=\sum _{i\in {\mathbb{P}}_1}{p}_i=\sum _{i\in {\mathbb{P}}_2}{p}_i=\cdots =\sum _{i\in {\mathbb{P}}_m}{p}_i \]$

(14)

식 (13)과 식 (14)을 활용하여 다층 선형 시스템에서의 Δ는 식 (15)와 같이 3개의 변수만을 사용하여 나타낼 수 있다.

$\[ \Delta =2\left(p_1+p_{*}+p_n\right) \]$

(15)

최종적으로 식 (3), 식 (6) 그리고 식 (15)를 사용하여 다층 선형 시스템에서의 제어 비용 함수 J를 선언한다.

$\[ J\left(p_1,p_{*},p_n\right)=\alpha \times 2p_n+\beta \times 2\left(p_1+p_{*}+p_n\right) \]$

(16)

4.2.2 다층 선형 시스템 스케줄 가능성 제약 조건

다층 선형 시스템에서의 스케줄 가능성 제약 조건 또한 제어 비용 함수와 같이 최적화 러너블 주기 3개에 대한 식으로 변형해야 한다. 센서 러너블과 액추에이터 러너블 사이에 존재하는 러너블들의 주기는 각 경로의 러너블 실행시간에 비례한 값으로 결정된다. 이 정책은 식 (17)과 같이 정의된다.

$\[ p_i=\frac{e_i}{\sum _{j\in {\mathbb{P}}_m}{e}_j}{p}_{*} \]$

(17)

where,
･ i∈ ℙ_k

스케줄링 함수 U(p₁,p₂,⋯,p_n)는 U(p₁,p_*,p_n)로 식을 재정의한다. 식 (4), 식 (6), 식 (15), 그리고 식 (17)을 이용하면 다층 선형 시스템의 U(p₁,p_*,p_n)는 식 (18)과 같다.

$\[ \begin{array}{c}U\left(p_1,p_{*},p_n\right)=\frac{e_1}{p_1}+\frac{\sum _{k=1}^m\sum _{i\in {\mathbb{P}}_k}\sum _{j\in {\mathbb{P}}_k}{e}_j}{p_{*}}+\frac{e_n}{p_n}\\ =\frac{e_1}{p_1}+\frac{\sum _{k=1}^m\sum _{i\in {\mathbb{P}}_k}\left|{\mathbb{P}}_k\right|e_i}{p_{*}}+\frac{e_n}{p_n}\end{array} \]$

(18)

4.2.3 다층 선형 시스템 모델 최적화 방법

3.2.1절과 3.2.2절에 의해 다층 선형 시스템에 대해 본문에서 정의한 문제를 다시 정리하면 다음과 같다.

Optimization problem: U(p₁,p_*,p_n)≤1을 만족하는 제한 조건에서 J(p₁,p_*,p_n)를 최소화시키는 최적화 주기 p₁,p_*,p_n 를 찾아 결정한다.

최적화 문제 해결을 위해 선형 시스템과 동일하게 라그랑주 승수법을 사용한다. 식 (16)과 식 (18)을 이용하여 식 (19)와 같이 라그랑주 식을 선언한다.

$\[ \begin{array}{c}L=J\left(p_1,p_{*},p_n\right)-\lambda \left(U\left(p_1,p_{*},p_n\right)-1\right)\\ =\left(2\alpha p_n+2\beta \left(p_1+p_{*}+p_n\right)\right)\\ -\lambda \left(\frac{e_1}{p_1}+\frac{\sum _{k=1}^m\sum _{i\in {\mathbb{P}}_k}\left|{\mathbb{P}}_k\right|e_i}{p_{*}}+\frac{e_n}{p_n}-1\right)\end{array} \]$

(19)

식 (19)를 p₁, p_*, p_n, 그리고 λ에 대하여 식 (20)과 같이 편미분을 진행한 식들이 0이 되는 방정식을 해결하면 식 (21)과 같은 최적화 주기 p₁, p_*, p_n를 찾는 일반식을 도출할 수 있다. 이 값을 이용하면 식 (17)을 통해 P={p₁,p₂,⋯,p_n}을 얻을 수 있다.

$\[ \nabla L=\left(\frac{\delta L}{\delta p_1},\frac{\delta L}{\delta p_{*}},\frac{\delta L}{\delta p_n},\frac{\delta L}{\delta \lambda }\right)=0 \]$

(20)

$\[ \begin{array}{c}{p}_1=e_1+\sqrt{e_1\sum _{k=1}^m\sum _{i\in {\mathbb{P}}_k}\left|{\mathbb{P}}_k\right|e_i}+\sqrt{\frac{\left(\alpha +\beta \right)e_1{e}_n}{\beta }}\hfill \\ p_{*}=p_1\sqrt{\frac{\sum _{k=1}^m\sum _{i\in {\mathbb{P}}_k}\left|{\mathbb{P}}_k\right|}{e_1}}\hfill \\ p_n=p_1\sqrt{\frac{{\beta e}_n}{\left(\alpha +\beta \right)e_1}}\hfill \end{array} \]$

(21)

5. 실험을 통한 최적화 방법 평가

이번 장에서는 4장에서 제시한 선형 시스템 러너블 주기 최적화 방법과 다층 선형 시스템 러너블 주기 최적화 방법을 실험을 통해 평가한다. 실험은 1개의 선형 시스템과 3개의 다층 선형 시스템을 대상으로 한다. Fig. 6은 실험 대상 시스템의 형태와 각 러너블의 실행시간을 표현한다. (a)는 선형 시스템이고 (b), (c), (d)는 다층 선형 시스템이다. 각 대상 시스템에 대해서 세 가지 관점으로 평가한다. 첫 번째는 제어 비용의 최소화 정도, 두 번째는 최적화에 소요되는 시간, 그리고 마지막은 최적화 된 시스템의 정상 작동 여부이다. 이를 위해 아래 세 가지 방법을 서로 비교한다.

Fig. 6

Example of 1 linear model and 3 multiple linear models with varying number of runnables (denoted by nR) and number of paths (denoted by mP) with execution times shown below each runnable

• Ours (real) method: 선형 시스템의 경우 4장 식 (11), 다층 선형 시스템의 경우 4장 식 (17), (21)을 사용한다. 각 주기는 소수점 둘째 자리까지 계산한다.
• Ours (int) method: 위의 방법을 통해 얻은 실수 주기 에 근사한 정수들의 조합 중에서 제어 비용이 최소인 조합을 찾는다.
• Exhaustive search method: 가능한 모든 러너블 주기 조합을 탐색하여 스케줄링이 가능하면서 제어 비용이 최소인 최적 주기 조합을 찾는다. 탐색 범위는 1 ≤ p₁,p₂,⋯,p_n ≤ 1000 인 정수로 제한한다. 이 방법을 통해 얻은 결과값은 러너블의 정수형 주기 중에서 최적의 제어 성능을 낼 수 있는 optimal point이다.

제어 성능 평가를 위한 제어 비용 함수는 식 (22)와 같다.

5.1 실험을 통한 주기 결정 및 제어 성능 평가

Fig. 6(a) 선형 시스템의 경우 제어 비용 함수 파라미터 T와 Δ는 각각 4장의 식 (6), 그리고 식 (7)에 의해 다음과 같이 치환된다.

$$ T=2p_3$$

$$ \Delta =2\sum _{i=1}^3{p}_i=2\left(p_1+p_2+p_3\right)$$

스케줄 가능성 제약 조건은 4장의 식 (5)에 의해 다음과 같이 치환된다.

$$ U\left(p_1,p_2,p_3\right)=\frac{e_1}{p_1}+\frac{e_2}{p_2}+\frac{e_3}{p_3}=\frac{2}{p_1}+\frac{3}{p_2}+\frac{3}{p_3}\le 1$$

4장의 식 (11)을 통해 본 논문에서 정의한 조건을 만족하는 최적 주기를 계산할 수 있다. 결정된 러너블 주기들은 Table 1(a)의 Ours (real) Method와 같고 이를 정수값으로 근사한 최적 주기 결과값은 Ours (int) Method와 같다.

Table 1

Result of our method and exhaustive search method

Fig. 6(b)의 경우 4개의 러너블이 2개의 층을 이루고 있는 형태이다. 제어 비용 함수 파라미터 T와 Δ는 각각 4장 식 (13), (15)에 의해 다음과 같이 치환된다.

$$ T=2p_4$$

$$ \Delta =2p_1+{2p}_{*}+{2p}_4$$

4장 식 (18)을 이용한 스케줄 가능성 제약 함수는 다음과 같다.

$$ \begin{array}{c}U\left(p_1,p_{*},p_n\right)=\frac{e_1}{p_1}+\frac{\sum _{k=1}^2\sum _{i\in {\mathbb{P}}_k}\left|{\mathbb{P}}_k\right|e_i}{p_{*}}+\frac{e_n}{p_n}\\ =\frac{2}{p_1}+\frac{\left(1\times 7\right)+\left(1\times 5\right)}{p_{*}}+\frac{3}{p_4}\le 1\end{array}$$

다층 선형 시스템의 경우 4장의 식 (21)을 통해 주기를 결정할 수 있다. 결과값은 Table 1(b)의 Ours (real) Method와 같고 이를 정수값으로 근사한 최적 주기 결과값은 Ours (int) Method와 같다. 같은 방법으로 Fig. 6(c), (d) 모델에 대해서도 최적 주기를 계산할 수 있고 그 결과는 Table 1(c), (d)와 같다.

Table 1의 Exhaustive Search Method 열에는 Exhaustive 탐색 방법을 Fig. 6의 실험 대상 시스템에 적용해 얻은 Optimal point를 기재했다. Fig. 7은 Table 1과 식 (22)를 사용해 계산한 제어 비용을 그래프로 나타낸 그림이다. 그래프 가로 축에는 Fig. 6의 4개 실험 대상 시스템 번호를 기재했다. 파란색 막대 그래프는 Exhaustive 탐색 방법으로 얻은 최적 제어 비용이다. 본 논문에서 제시한 알고리즘과의 상대적 비교를 위해 이를 100 %로 표시한다. 빨간색 그래프는 Ours (real) 방법으로 얻은 제어 비용이다. Ours (real) 방법은 소수점 둘째 자리까지 계산되어 러너블의 개수가 많지 않은 시스템에서는 정숫값만을 탐색 대상으로 하는 Exhaustive 탐색 방법보다 더 좋은 제어 성능을 보인다. 초록색 막대 그래프는 Ours (int) 방법으로 얻은 제어 비용이다. 본 논문에서 제시한 정수형 최적 주기 검출 알고리즘을 사용하더라도 최적 제어 성능과 큰 차이가 없는 2 % 내외의 차이를 보였다.

Fig. 7

Comparison of normalized control cost

5.2 주기 결정 소요시간 비교

이번 절에서는 본 논문에서 제시한 최적 주기 결정 방법과 Exhaustive 탐색 방법을 통해 얻은 최적 주기에 대해 주기 결정 소요시간을 비교한다. 실험은 Intel i7-8700k, 32gb ram PC와 Matlab 2016b 환경에서 진행했다.

Fig. 8은 Exhaustive 탐색 방법, 본 논문에서 제시한 Ours (real) 방법 그리고 Ours (int) 방법을 Fig. 6의 실험 대상 시스템에 적용할 때 주기 결정 소요시간을 비교한 그래프이다. Ours (real) 방법과 Ours (int) 방법은 주기 결정 소요시간 차이가 없어 Ours로 통일하여 표현한다. 러너블의 개수가 많지 않을 때는 Exhaustive 탐색 방법과 본 논문에서 제시한 알고리즘의 주기 결정 소요시간에 큰 차이가 있지 않다. 그러나 러너블 개수가 증가하여 6개일 때는 본 논문에서 제시한 알고리즘의 경우 소요시간이 3개 일 때와 큰 차이가 없는 방면 Exhaustive 탐색 방법은 최적 주기 검출시간이 6시간이 걸리는 결과를 보였다.

Fig. 8

Comparison of elapsed optimization time

Table 2는 러너블 개수 증가에 따른 주기 결정 소요시간에 대한 실험 결과다. 결과 데이터 중 괄호로 표시된 수치는 타 수치들을 통한 예측 수치를 계산해 기재했다. 이 실험을 통해 Exhaustive 탐색 방법의 경우 러너블 개수가 7개 이상일 때부터 소요시간의 증가로 인해 사용하기 어려운 반면 본 논문에서 제시한 알고리즘의 경우에는 러너블 개수와 상관없이 빠르게 최적 주기를 검출함을 보여주었다.

Table 2

Comparing the elapsed optimization time of Our method and Exhaustive search method

5.3 시스템 안정성 평가

이번 절에서는 본 논문에서 제시한 최적 주기 검출 알고리즘을 통해 얻은 최적 주기를 오토사 기반 애플리케이션에 적용하였을 때 시스템이 정상적으로 작동하는지에 대한 평가를 진행한다. 평가 방법은 아래와 같다.

• 평가방법: 본 논문에서 제시한 Ours (real) method 그리고 Ours (int) method를 사용하여 얻은 최적 주기 결과들을 시스템에 각각 적용했을 때의 스케줄링 함수 U(p₁,p₂,⋯,p_n) 결과값을 통해 시스템 안정성을 평가한다.

3장에서 정의한 바와 같이 본 논문에서는 EDF 알고리즘을 사용하여 스케줄링 하며 시스템 Utilization 합이 1 이하인 양의 실수값을 나타내는 경우 러너블 스케줄이 가능한 것으로 정의한다. 이는 곧 오토사 기반 애플리케이션이 사용하는데 문제가 없음을 의미한다.

이번 실험에서는 5장 1절의 실험을 통해 얻은 최적 주기들이 오토사 기반 애플리케이션에 적용하였을 때 문제가 없는지에 대한 실험을 진행한다. Table 1에 기재된 최적 주기들과 Fig. 6의 시스템 모델들을 활용하여 각 시스템 별 Utilization 합을 계산한다. 그 결과는 Table 3과 같다.

Table 3

System utilization using Ours (real) method and Ours (int) method

Table 3의 1열에는 Fig. 6의 시스템 모델 4개가 기재 되어 있으며 Ours (real) 방법과 Ours (int) 방법을 통해 얻은 최적 러너블 주기를 각 시스템에 적용했을 때의 시스템 Utilization 합은 표 안에 기재되어있다. 모든 시스템의 Utilization 합은 1 이하의 값을 보였으며 이는 본 논문에서 제시한 두 가지 최적 주기 검출 알고리즘 모두 오토사 기반 애플리케이션에 사용하는데 문제가 없음을 보여준다.

6. 결 론

본 논문은 오토사 기반 차량 제어 애플리케이션의 성능 향상 방법에 관한 연구를 진행했다. 특히 러너블 스케줄링과 제어 성능을 같이 고려한 러너블 주기 결정 방법을 제시하여 한정된 CPU 자원으로 제어 성능을 최적화하였다. 이를 위해 일반 선형 시스템과 다층 선형 시스템에 대해 최악 상황에서의 시스템 제어 주기와 End-to-end 지연 시간을 러너블 주기로 나타냈고 이들을 이용해 제어 비용 함수와 시스템의 스케줄링 가능성 체크 함수를 정의했다. 여기에 라그랑주 승수법을 이용해 한정된 하드웨어 자원으로 러너블들의 스케줄링이 가능하면서 시스템이 최적의 성능을 낼 수 있는 최적의 러너블 주기들을 결정하는 알고리즘을 제시했다. 본 논문에서 제시한 알고리즘은 제어 성능 기준으로 실제 Optimal Point에 비해서 2 % 내외의 차이를 보였다. 하지만 Optimal Point를 찾기 위해 사용하는 Exhaustive 탐색 방법은 러너블의 수가 증가할수록 소요 시간이 기하급수적으로 증가하여 실제 자동차 제어 시스템에 적용하는 게 불가능하다. 반면에 본 논문의 분석적인 방법은 Near Optimal Point를 빠르게 찾을 수 있는 장점이 있다.

이후의 연구에서는 본 논문에서 제시한 최적화 알고리즘을 일반적인 DAG 형태의 시스템에 적용하여 일반화하는 방법을 연구한다.

Acknowledgments

이 논문은 부분적으로 2019년도 정부(과학기술정보통신부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임(No. 2017R1C1B5018374). 또한, 이 논문은 부분적으로 2019년도 정부(과학기술정보통신부)의 재원으로 정보통신기술진흥센터의 지원을 받아 수행된 연구임(No.2014-3-00065, 실시간 자율복원 사이버물리 시스템 기초연구).

References

• AUTOSAR, https://www.autosar.org, , 2019.
• S. Kang, B. Kim and J. Jung, “Study on Optimization of CAN Message Processing S/W Structure in Based on AUTOSAR Platform,” KSAE Fall Conference Proceedings, pp.512-516, 2018.
• K. Lee, I. Park, M. Sunwoo and W. Lee, “AUTOSAR-ready Light Software Architecture for Automotive Embedded Control Systems,” Transactions of KSAE, Vol.21, No.1, pp.68-77, 2013. [https://doi.org/10.7467/KSAE.2013.21.1.068]
• E. Wozniak, A. Mehiaoui, C. Mraidha, S. Tucci-Piergiovanni and S. Gerard, “An Optimization Approach for the Synthesis of Architectures,” Proceedings of 18th Conference on Emerging Technologies & Factory Automation, 2013. [https://doi.org/10.1109/ETFA.2013.6647952]
• S. Lee, “IT Fusion Trend to Automobile Technology,” KSAE, Auto Journal, Vol.30, No.4, pp.88-94, 2008.
• H. Cha, S. Park, W. Jeong and J. Kim, “Performance Tradeoff between Control Period and Delay: Lane Keeping Assist System Case Study,” Journal of the Korea Society of Computer and Information, Vol.20, No.11, pp.39-46, 2015. [https://doi.org/10.9708/jksci.2015.20.11.039]
• H. Cha, W. Jeong and J. Kim, “Control-Scheduling Codesign Exploiting Trade-off between Task Periods and Deadlines,” Mobile Information Systems, Vol. 2016, Article ID 3414816, 2016. [https://doi.org/10.1155/2016/3414816]
• G. Lee and J. Kim, “AUTOSAR Runnable Scheduling for Optimal Control Performance,” KSAE Fall Conference Proceedings, pp.786-798, 2017.
• T. Kim, G. Lee and J. Kim, “AUTOSAR Runnable Scheduling for Optimal Tradeoff between Control Performance and CPU Utilization,” Proceedings of 18th International Conference on Control, Automation and Systems, 2018. [https://doi.org/10.1109/MCS.2018.2888718]
• D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Int Edn., Academic Press, New York, 2014.
• D. Seto, J. P. Lehoczky, L. Sha and K. Shin, “On Task Schedulability in Real-time Control Systems,” Proceedings of 17th IEEE Real-Time Systems Symposium, 1996.
• D. Seto, J. P. Lehoczky and L. Sha, “Task Period Selection and Schedulability in Real-time Systems,” Proceedings of 19th IEEE Real-Time Systems Symposium, 1998.
• C. Du, L. Tan and Y. Dong, “Period Selection for Integrated Controller Tasks in Cyber-physical Systems,” Chinese Journal of Aeronautics, Vol.28, No.3, pp.894-902, 2015. [https://doi.org/10.1016/j.cja.2015.04.011]
• B. K. Kim, “Task Scheduling with Feedback Latency for Real-time Control Systems,” Proceedings of the 5th International Conference on Real-Time Computing Systems and Applications, pp.37-41, 1998.
• E. Bini and A. Cervin, “Delay-aware Period Assignment in Control Systems,” Proceedings of 29th IEEE Real-Time Systems Symposium, 2008. [https://doi.org/10.1109/RTSS.2008.45]
• Y. Wu, G. Buttazzo, E. Bini and A. Cervin, “Parameter Selection for Real-time Controllers in Resource-constrained Systems,” IEEE Transactions on Industrial Informatics, Vol.6, No.4, pp.610-620, 2010. [https://doi.org/10.1109/TII.2010.2053378]
• R. Long, H. Li, W. Peng, Y. Zhang and M. Zhao, “An Approach to Optimize Intra-ECU Communication Based on Mapping of AUTOSAR Runnable Entities,” Proceedings of 6th International Conference on Embedded Software and Systems, 2009. [https://doi.org/10.1109/ICESS.2009.63]
• A. Monot, N. Navet, B. Bavoux and F. Simonot-Lion Monot, “Multisource Software on Multicore Automotive ECUs-combining Runnable Sequencing with Task Scheduling,” IEEE Transactions on Industrial Electronics, Vol.59, No.10, pp.3934-3942, 2012. [https://doi.org/10.1109/TIE.2012.2185913]
• S. Saidi, S. Cotard, K. Chaaban and K. Marteil, “An ILP Approach for Mapping AUTOSAR Runnables on Multi-core Architectures,” Proceedings of 7th Workshop in Rapid Simulation and Performance Evaluation: Methods and Tools, 2015. [https://doi.org/10.1145/2693433.2693439]
• S. Kehr, E. Quinones, D. Langen, B. Boddeker and G. Schafer, “Parcus: Energy-aware and Robust Parallelization of AUTOSAR Legacy Applications,” Proceedings of 23th Real-Time and Embedded Technology and Applications Symposium, 2017. [https://doi.org/10.1109/RTAS.2017.4]
• C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” Journal of the ACM, Vol.20, No.1, pp.46-61, 1973. [https://doi.org/10.1145/321738.321743]