臺灣博碩士論文加值系統

依據摩爾定律以及節能的考量，在一個晶片中放置多個處理器已是一種趨勢。人們在設計系統時，因為成本因素，捨棄使用裡面只有一個處理器，但是速度快卻高耗電性的晶片，改用具有多處理器但每個處理器卻是設計較簡單且速度較低的晶片。單一處理器的晶片雖然可以很快的把工作做完，但是成本與電耗都較高，在使用多處理器晶片時，作業系統對於原先的任務需要做調整，才能以多處理器完成原任務。本論文中所要探討的是多處理器系統中的可平行化任務處理機制，任務為可平行化與不可平行化片段所組成，我們首先透過將週期分配給可平行化任務的不同片段的子任務，讓執行順序限制轉換成執行區間限制，達到每個子任務間的獨立性。再藉由不同片段的子任務的執行區間完全不重疊，在將子任務分配至處理器時，盡量能將不同片段的子任務分配給同一處理器，減少處理器保留過多能力給多個同一任務之不同片段的子任務，因為在執行階段當某個子任務執行時，同一任務之其他子任務是不會執行的，因此一個時間點只會使用保留給同一個任務之子任務的部份能力，因此我們希望能在分配子任務時，將同一個任務之不同片段的子任務的能力合併計算。最後，我們建置模擬程式，驗證我們所提的子任務使用密度合併機制，並且結合不同的截限時間分配機制，以及(子)任務分配機制，由於Equal Flexibility (EQF) 讓同一個任務的每個子任務之使用密度一樣，合併時，額外增加的使用密度最少，而Best Fit (BF) 則是在分配(子)任務時，先將(子)任務分配至可用之使用能力最低的處理器，因此EQF 結合Best Fit 有最佳的可排程率。

According to Moore's Law and energy-saving considerations, placing multiple processors in a single chip is a trend. Because of the cost factor, people almost adopt multi-processor platforms to design the system, instead of the chips only having one high-speed and high-power consumption processor . A single complex processor chip can quickly finish the work, but the cost and energy consumption are higher. When a multi-processor platform is used, the operating system must adjust the original task execution to fit the execution on the multi-processor platform. In this paper, we will propose a mechanism to deal with parallel tasks on multiprocessor systems. A parallel task is composed of parallel and sequential segments. For each parallel task, we allocate its period to the subtasks of its segments. Then, the execution order of the subtasks will be transformed into the timing constraints. If each subtask can meet its timing constraint, the original parallel task will achieve its real-time requirements. Besides, due to that the execution interval of subtasks for different segments of a parallel task do not have any overlap. If the subtasks for different segments can be assigned to the same processor, the capacity of the processor can be used for more tasks. When a subtask is executed, the other subtask of the same task is not executed. We want to combine the densities of the subtasks of the different subtasks of the same parallel task when allocating subtasks. Finally, we build the simulation program to verify our proposed mechanism. We combine the different deadline allocation mechanisms, such as Equal Flexibility (EQF), Equal Slack (EQS), and Boundary, and the (sub)task allocation mechanisms, such as Best Fit Decreasing (BFD), First Fit Decreasing (FFD), and Worst Fit Decreasing (WFD). Since EQF makes all the subtasks of a parallel task have the same densities, the additional density is the smallest, i.e., 0, when the subtasks are combined. BFD assigning a (sub)task to the processor with the lowest available capacity. Therefore, The Best-Fit Decreasing with the EQF has the highest schedulability ratio.

圖目錄
1 導論1
1.1 前言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 全文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 系統模式與問題定義5
3 多處理器上具可平行化任務之任務集合分配機制8
3.1 任務分配機制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 執行順序限制(execution order) 轉成時間約束限制(timing constraint) 10
3.3 子任務使用密度合併. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 例子. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4 效能評估23
4.1 實驗環境設置. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 實驗結果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 結論35
Bibliography 37

[1] Opencl, 2017. https://www.khronos.org/opencl/.

[2] Openmp, 2017. http://www.openmp.org/.

[3] H. Aydin and Q. Yang. Energy-aware partitioning for multiprocessor real-time systems. In International Parallel and Distributed Processing Symposium (IPDPS),
2003.

[4] E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: a survey in approximation algorithms for np-hard problems. PWS, Boston,1997.

[5] Ricardo Garibay-Martínez, Geoffrey Nelissen, Luis Lino Ferreira, and Luís Miguel Pinho. On the scheduling of fork-join parallel/distributed real-time tasks. In the 9th IEEE International Symposium on Industrial Embedded Systems (SIES), 2014.

[6] Chin-Fu Kuo, Yung-Feng Lu, and Tzu-Chieh Chen. Scheduling algorithm for parallel real-time tasks on multiprocessor systems. In 2016 ACM Research in Adaptive and Convergent Systems (ACM RACS 2016), 2016.

[7] Chin-Fu Kuo, Yung-Feng Lu, Shu-Ping Lu, and Ya-Ju Yu. Subdeadline assignment for real-time tasks with multiple parallelization options on multiprocessor systems.2017 IEEE International Conference on Applied System Innovation (ICASI 2017),May. 2017.

[8] F J. Kwon, K.-W. Kim, S. Paik, J. Lee, and C.-G. Lee. Multicore scheduling of parallel real-time tasks with multiple parallelization options. In IEEE 21st Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 232–244, April 2015.

[9] Karthik Lakshmanan, Shinpei Kato, and Pittsburgh. Scheduling parallel real-time tasks on multi-coreprocessors. In IEEE Real-Time Systems Symposium (RTSS),2010.

[10] Tobias Langer, Lukas Osinski, and J¨urgen Mottok. A survey of parallel hard-real time scheduling on task models and scheduling approaches. In the 30th InternationalConference on Architecture of Computing Systems (ARCS), April 2017.

[11] J. W. Layland. Real-Time System. Prentice Hall, 2000.

[12] Dawei Li and Jie Wu. Utility-based scheduling for periodic tasks with multiple parallelization options. In 2016 IEEE International Conference on Cloud Computing Technology and Science (CloudCom), 2016.

[13] Abusayeed Saifullah, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill.Multi-core real-time scheduling for generalized parallel task models. In IEEE Real-Time Systems Symposium (RTSS), 2011.