멀티코어 시스템 설계를 위한 트레이싱 기반 태스크 그래프 추출

한소담 포항공과대학교 일반대학원 2017 국내석사

The task graph is a graphical representation of the dependencies among the tasks running on the system. The task graph consists of tasks (nodes) and dependencies (edges). A task is a unit of execution and a task dependency shows which task can be executed before and after execution of a given task. Typically, task graphs are used for evaluating CPU scheduling algorithms. There are several requirements which task graphs have to satisfy to be used for evaluating CPU scheduling algorithms. First of all, task granularity needs to be determined by considering CPU scheduling behavior of the real multicore system. Also, task parallelism needs to be accurately modelled to precisely describe CPU allocation of tasks which are in parallel relations. Furthermore, because up-to-date mobile devices generally contain multiple cores, CPU scheduling algorithms are required to be suitable for daily scenarios, which are frequently running on the mobile devices. Therefore, task graphs of daily scenarios are necessary. This thesis proposes a new method to extract task graphs using kernel tracing. The proposed method extracts task graphs of scenarios running on the Android-based multicore systems. It is the first approach which extracts task graphs which are suitable to be applied to the systems that mainly manage dynamic workloads. The task graph extracted by the proposed method contains dependence relations among tasks, information on thread-level system behavior triggered by interrupts, and resource usage of tasks. To provide task graphs which are suitable for evaluating CPU scheduling algorithms, the proposed method extracts the task graph by analyzing CPU scheduling behavior monitored by kernel tracing, without source code. The proposed method extracts a task graph of a target scenario through four functional blocks: kernel tracing, task dependency extraction, interrupt modeling, and resource calculation. At first, the kernel tracing block monitors CPU scheduling-related kernel events during execution of the target scenario. Secondly, the task dependency extraction block extracts dependence relations among tasks and task parallelism. Thirdly, the interrupt modeling block models thread-level system behavior triggered by interrupts, which occur during execution of the whole target scenario. Finally, the resource calculation block calculates CPU workload and I/O waiting time to describe resource usage of each task. In the proposed method, analysis of wake up events is a main idea to extract task graphs. Wake up event is one of kernel events, which wakes up a sleeping thread. Generally, wake up event for a certain thread is requested by another thread or an interrupt which causes the target thread to be allocated to a CPU. By analyzing wake up events, the proposed method identifies relations among tasks and performs interrupt modeling. Also, in this thesis, the concept preceding workload is introduced to describe task parallelism precisely. When two tasks have a dependency, the preceding workload is defined as the amount of CPU workloads the source task must complete before the destination task becomes runnable. The proposed method extracts task graphs of a wide range of scenarios which can be performed on the Android-based multicore system, including daily scenarios. Also, the proposed method reflects the real CPU scheduling behavior to extract task graphs. Using the proposed method, the practical and accurate evaluation of the CPU scheduling algorithms would be possible. This method would also help to develop system management policies which need to actively communicate with the CPU scheduler in the system. In this point of view, the proposed method would contribute to the improvement of efficiency of the multicore system design. Task graph란 시스템 상에서 수행되는 task 간의 dependency를 그래프로 나타낸 것이다. Task graph는 task를 나타내는 node와 task 간의 dependency를 나타내는 edge로 구성되어 있다. Task는 시스템 내 실행 단위를 의미하고, task dependency는 임의의 task의 실행 전후에 어떤 task가 수행되어야 하는가를 보여준다. 일반적으로 task graph는 CPU scheduling 알고리즘들을 평가하는데 사용된다. Task graph가 CPU scheduling 알고리즘들을 평가하는데 사용되기 위해서는 충족시켜야 하는 몇 가지 요구사항이 있다. 먼저, task의 granularity가 실제 multicore system 상에서의 CPU scheduling 동작을 고려하여 결정되어야 한다. 또한, 병렬 관계에 있는 task들의 CPU 할당을 보다 상세하게 묘사하기 위해 task의 병렬성이 정확하게 모델링되어야 한다. 더 나아가, 최신 mobile device들은 일반적으로 다수의 코어들을 포함하고 있기 때문에, CPU scheduling 알고리즘들은 mobile device 상에서 빈번하게 수행되는 일상 시나리오들에 적합해야 한다. 따라서 이러한 일상 시나리오들에 대한 task graph가 필요하다. 본 논문에서는 kernel tracing을 사용하여 task graph를 추출하는 새로운 방법은 제안한다. 제안하는 방법은 안드로이드 기반의 multicore system 상에서 수행되는 시나리오들의 task graph를 추출한다. 본 논문은 최초로 dynamic workload를 주로 다루는 시스템을 위한 task graph를 추출하는 방법을 제안한다. 제안하는 방법을 통해 추출된 task graph는 task간의 dependency, 인터럽트에 의해 발생한 thread 레벨에서의 시스템 동작 관련 정보, 그리고 task들의 resource usage 정보를 포함한다. Dynamic workload를 다루는 multicore system에 적용하기에 보다 적합한 task graph를 제공하기 위해, 제안하는 방법은 소스 코드를 사용하지 않고, kernel tracing을 통해 run-time CPU scheduling 동작을 모니터링 한 후 이를 분석하여 task graph를 추출한다. 제안하는 방법은 kernel tracing, task dependency extraction, interrupt modeling, 그리고 resource calculation의 네 개의 블록으로 구성되어 있다. 먼저 kernel tracing 블록은 타겟 시나리오가 수행되는 도중 발생하는 CPU scheduling 관련 kernel 이벤트들을 모니터링한다. 두 번째로 task dependency extraction 블록은 task간의 dependency를 추출하고 task의 병렬성을 모델링한다. 세 번째로 interrupt modeling 블록은 타겟 시나리오가 수행되는 동안 발생한 인터럽트들로 인한 시스템 동작들을 thread 레벨로 모델링한다. 마지막으로 resource calculation 블록은 각 task의 CPU workload 및 I/O waiting time을 계산한다. 제안하는 방법은 wake up 이벤트에 대한 분석을 기반으로 task graph를 추출한다. wake up 이벤트는 커널 이벤트 중 하나로써 자고 있는 thread를 깨운다. 일반적으로 임의의 thread에 대한 wake up 이벤트는 타겟 thread가 CPU에 할당되는 조건을 방생시킨 또 다른 thread나 인터럽트에 의해 요청된다. 제안하는 방법은 wake up 이벤트들을 분석함으로써 task 간의 관계를 파악하고 interrupt modeling을 수행한다. 또한 본 논문에서는 task간의 병렬성을 좀 더 상세하게 묘사하기 위해 preceding workload라는 개념을 정의하였다. Preceding workload란 두 개의 task 사이에 dependency가 존재할 때, destination task가 runnable해지기 전에 source task가 처리해야 하는 CPU workload의 양을 의미한다. 제안하는 방법은 안드로이드 기반의 multicore system 상에서 수행되는 다양한 시나리오들의 task graph들을 추출한다. 또한 제안하는 방법은 타겟 시나리오가 수행될 때 발생하는 실제 CPU scheduling 동작을 반영하여 task graph를 추출한다. 제안하는 방법은 좀 더 실용적이고 보다 정확한 CPU scheduling 알고리즘 성능 평가를 가능하게 하고, 더 나아가 시스템 내 CPU scheduler와의 활발한 교류를 필요로 하는 system management 정책들을 개발하는 데 도움을 준다. 따라서 제안하는 방법은 멀티코어 시스템 설계의 효율을 향상시킨다.

System-level Power/Performance Analysis and Management on Multicore-based Mobile Systems

한소담 포항공과대학교 일반대학원 2020 국내박사

The usage of modern mobile devices (e.g., smartphones and tablets) is not limited to communication, the traditional usage of mobile phones. Recently, mobile devices have been widely used to perform various user-interactive scenarios, such as web browsing, social networking, multimedia streaming, and gaming. In this context, modern mobile devices have been designed by adopting high-performance processing units (e.g., asymmetric multicore CPU, GPU, and AI accelerator) to meet end-users’ requirements. The integration of the high-performance processing units in a single chip increases the quality-of-service (QoS). However, it also increases power density and therefore causes various power and thermal problems such as reduction of battery life, thermal hot spots, and overheating problems. PCs and server computers are not battery-powered, and their thermal problems can be solved by using a fan or liquid. However, these solutions are not suitable for modern mobile devices. Thus, analysis and management of execution behavior, which causes the degradation of power efficiency and performance, are essential to solving power and thermal problems occurring on modern mobile devices. However, system-level analysis and management of the execution become challenging due to the increasing complexity of mobile devices and the diversity of the user scenarios running on mobile devices. This dissertation presents two research topics that have been conducted to enable effective execution-behavior-analysis and power management of multicore-based modern mobile devices. The first topic is system-level application modeling for analysis of the dynamic execution behavior of multicore-based mobile systems. In this research, a generalized application model, as a task graph representation, is suggested with essential elements that must be included in nodes and edges. Then, an application modeling method is proposed to generate the generalized application model for Android-based mobile systems. To be used for the analysis of the thread-level execution behavior of modern mobile devices, the proposed method provides an adequate task unit to guarantee thread-level granularity. Besides, the proposed method uses kernel events occurring during the execution of the target application, instead of its source code; this enables modeling the entire dynamic-execution-behavior of various user scenarios running on modern mobile devices. Experimental results demonstrated that the proposed policy extracts reliable and realistic Android application models. In terms of CPU utilization, the average mean-absolute-error (MAE) of the proposed method was 2.58 %. Also, it was demonstrated that the proposed method extracts the application models with high consistency for various system configurations. Thus, the proposed method can be used for the analysis of the dynamic execution behavior of modern and future mobile systems. The second topic is user scenario-adaptive power management. In this research, a scenario-adaptive dynamic-voltage/frequency-scaling (DVFS) policy is proposed to balance the trade-off between energy consumption and QoS for various user scenarios. The proposed policy is adaptive to a wide range of user scenarios by using scenario characteristics that are not constrained to specific types of user scenarios. Furthermore, by not requiring the preliminary knowledge of the target scenario, the proposed policy is appropriate to online power management, which is essential for modern mobile devices. The proposed policy predicts the upcoming scenario characteristics (in this research, thread-level parallelism and the requested amount of work) during runtime. Then, it calculates ‘just enough’ processing speed to process the requested work at the given parallelism degree. In the experimental study, the proposed policy achieved a maximum of 25.5 % energy saving on the mobile system that uses the asymmetric multicore processor, and a maximum of 30.7 % energy saving on the mobile system that uses the symmetric multicore processor, without any QoS violation which degrades user experiences.