[Review] Introduction of deep neural network in hybrid WCET analysis(2018) 논문 요약 정리

T. Huybrechts, T. Cassimon, S. Mercelis, and P. Hellinckx, “Introduction of deep neural network in hybrid WCET analysis,” in Proc. Int. Conf. P2P Parallel Grid Cloud Internet Comput., 2018

1. 연구의 필요성

하드 리얼타임 사이버-물리 시스템(CPS)에서는 각 태스크의 WCET(최악 시나리오 실행 시간)을 파악해야 해당 태스크가 예측 가능한지를 판단할 수 있다. WCET 분석을 위한 방법에는 static, measurement-based, hybrid approach가 있다. 이 중 hybrid 방법론은 계산 complexity(static의 장점)과 accuracy(measurement의 장점) 사이의 균형을 맞추는 데 도움을 준다. 현재 대부분의 WCET 분석은 특정 하드웨어에서 컴파일된 실행 파일을 기반으로 이루어진다. 이 연구에서는 하이브리드 방식을 기계 학습으로 확장하여, 실제 하드웨어에서 측정 없이 WCET를 추정하는 새로운 접근법을 제시한다. 저자가 초기 단계에서의 WCET 분석을 강조하는 이유는 소프트웨어와 하드웨어의 고수준 특성을 바탕으로 WCET를 미리 예측함으로써, 시스템의 최종 설계 과정을 효과적으로 최적화할 수 있기 때문이다.

2. Method

저자는 소스코드를 'hybrid blocks'로 분할하여 WCET를 분석한다. 이 'hybrid blocks'는 인풋과 아웃풋이 있는 코드블록으로 일반적인 'basic blocks'와 유사하지만 , 우리가 추구하는 complexity와 accuracy에 따라 작은 instruction부터 프로그램 전체 사이즈가 될 수 있다. 저자의 접근법은 두 단계로 이루어진다: 첫째, hybrid blocks의 WCET 측정, 둘째, 이 측정 결과를 합쳐 계층을 고려한 WCET를 추정한다. 여기서 ML은 시스템의 각 속성 값 기반으로 모델을 학습시켜 WCET를 추정하기 위해 사용된다.

이 논문에서는 소프트웨어 관련 속성을 기반으로 Feed-Forward Neural Networks(FFNN)와 Tree Recursive Neural Networks(TRNN)를 학습시킨다. TRNN은 계층적 정보를 네트워크에 포함시키기 위해 채택됐다. 먼저 FFNN 네트워크 방식으로 블록의 WCET를 예측한 후, 트리 구조의 합성 네트워크로 각 블록들의 계층적 정보를 고려하여 WCET 결과를 예측한다.

• TRNN 부가설명

• Analysis-network: 기본적인 FFNN과 같은 역할을 합니다. 개별 코드 블록을 분석하여 해당 블록의 WCET를 예측합니다.
• Synthesis-network: 트리 구조의 상위 노드에서 여러 하위 노드 (또는 "자식 블록")의 WCET 값을 결합하여 해당 상위 노드의 최종 WCET 값을 예측합니다. 그러나 이 네트워크는 단순히 값을 합치는 것 외에도 해당 블록들이 어떻게 함께 작동하는지의 계층적 정보를 고려하여 WCET를 예측해야 합니다.

• Tree Recursive Neural Networks (TRNN)는 CFG (Control Flow Graph)의 트리 구조를 모델링하는 데 사용되며, 이 구조는 소프트웨어 프로그램의 여러 블록들이 어떻게 실행되는지의 순서를 표현합니다. TRNN은 기본적으로 두 가지 네트워크, 즉 analysis-network와 synthesis-network로 구성됩니다.

3. Evaluation

데이터셋: TACLeBench benchmark suite로부터 다양한 플랫폼에서의 WCET가 결정된 selected test applications를 얻었고, 시간 측정은 Silicon Labs의 EZR32 Leopard Gecko 보드의 ARM Cortex-M3 CPU에서 수행됐다. 각 블록의 WCET는 원래의 하이브리드 분석으로 얻었다. COBRA framework를 활용하여 hybrid block의 code에서 feature를 추출하여 속성 세트를 생성했다.

실험방법: 데이터 전처리와 신경망 모델의 구현은 TensorFlow를 사용했고 모델의 성능은 RMSE로 평가했다. 실험은 두 가지 hybrid block 크기 (추상화 없는 작은 블록 Set A와 큰 추상 블록 Set B)를 사용하여 수행되었고, 이를 5-fold cross-validation으로 훈련 및 검증했다. 최적의 신경망 구성을 찾기 위해 다양한 디자인을 실험했다.

결과: 예상보다 저조한 결과. (1) Set A가 validation set에서 smallest RMS error(40%)를 보였고, 여기서 scaling factor를 추가로 고려하면 clock cycle 수에 대한 오차는 약 20배. 따라서 유의한 WCET의 상한을 얻기에는 너무 큰 편차를 보임. (2) 모델은 epoch 40에서 수렴을 했고 이는 global optimum이 아닌 것으로 보임. (3) Set A와 Set B의 최적의 네트워크가 항상 동일하지 않았기 때문에 데이터셋 별로 다른 네트워크로 실험 진행.

실패원인: (1) Set A와 Set B의 추상화 레벨이 달라 training set의 갯수에 차이가 났다(98 blocks), 그래서 Set의 결과가 훨씬 나빴다. (2) Dataset의 feature의 분포가 충분하지 않아 일부 feature는 dataset에서 나타나지 않았다. (3) Benchmark 프로그램의 블록 사이즈 제한 때문에 적은 WCET를 가진 block들이 dataset의 대부분을 차지했다.

4. Limitation, Future Work

TRNN 중 synthesis network는 수렴도 안됐고 모델이 거의 학습되지 않았다. TRNN은 CFG(Control Flow Graph)의 계층적 정보 부족 때문에, 하위 노드의 WCET 값을 받아도 이 값을 어떻게 최종적인 상한값으로 결합해야 할지 알지 못했다. TRNN 방식이 실행 가능해지려면 최적의 모델 구성 및 파라미터 모델링에 대한 추가적인 탐구가 필요하고, loop, recursion 등 코드플로우와 블록 유형 정보(block type information)를 모델에 통합해야 할 것이다.

향후 연구에서는 (1) 데이터셋을 1000+개 이상으로 늘려서 모델이 충분히 블록의 attribute 관계를 학습할 수 있도록 해야 하고, (2) 네트워크에 대해 최적의 attribute와 하이퍼파라미터를 선택해야 하며, (3) CNN, LSTM 등의 다른 딥러닝 모델을 채택하는 방법도 있다.