멀티코어 시스템 상의 Global FP를 위한 조건적 최적 병렬화 기법

학위논문 (석사) -- 서울대학교 대학원 : 공과대학 컴퓨터공학부, 2020. 8. 이창건.Throughout the last decade, the importance of parallel computing has risen greatly to match the ever-increasing computational demand. Frameworks such as OpenMP and OpenCL allow easy parallelization of computing tasks into desirable number of threads, opening up a chance to greatly utilize the parallel computing resources. We call this parallelization freedom. However, this does not come for free, as parallelization overhead increase with parallelization option (i.e. the number of thread each task is parallelized). Thus parallelization option must be carefully decided to better utilize a given computing resource. This paper addresses the problem of assigning parallelization option to each task for global FP scheduler. For this, we extend the approaches made by Cho, which is limited to the global EDF scheduler case. We prove that a conditionally optimal parallelization assignment of parallelization option also exists for the global FP case. Through extensive simulations and autonomous driving module task sets, we show a significant improvement of schedulability.지난 몇 십년 간, 컴퓨테이션 요구의 증가와 함께 병렬 컴퓨팅의 중요성이 크게 증대되고 있다. OpemMP나 OpenCL과 같은 프레임워크들은 컴퓨팅 테스크를 원하는 수의 쓰레드로 쉽게 병렬화 할 수 있도록 한다. 이를 본 논문에서는 병렬화 자유도라고 명명했다. 그러나 병렬화는 댓가를 필요로 하며 병렬화 옵션(각 태스크를 병렬화 하는 쓰레드의 갯수)에 따른 병렬화 오버헤드를 발생시킨다. 이에 주어진 컴퓨팅 리소스의 보다 나은 활용을 위해 병렬화 옵션은 신중하게 정해질 필요가 있다. 본 논문은 global FP 스케쥴러 상에서 각 테스크에 병렬화 옵션을 할당하는 문제를 다룬다. 이를 위해 기존에 global EDF 상으로 한정되어 있는 조의 접근방법을 확장한다. global FP 상에서도 병렬화 옵션의 조건적 최적 할당이 존재함을 증명하였다. 또한 광범 위한 시뮬레이션과 자율주행 태스크셋을 통해 스케쥴러빌리티의 확실한 향상을 보였다1 Introduction 1 2 Problem Description 3 3 Global FP Extension of BCL Schedulability Analysis for Tasks with Parallelization Freedom 5 3.1 Overview of BCL Schedulability Analysis for Global FP 6 3.2 Extension of BCL Schedulability Analysis for Tasks with Parallelization Freedom 9 4 A Trade-Off of Parallelization: Tolerance VS. Interference 11 4.1 Monotonic Increasing Property of Tolerance 11 4.2 Monotonic Increasing Property of Interference 13 5 Optimal Parallelization Options Assignment Algorithm 23 6 Experiment 29 6.1 Simulation Results 29 6.2 Implementation Results 32 7 Conclusion 33 References 34Maste