本篇論文中，我們主要探討嵌入式系統的排程硬體化。作業系統的排程中主要是實現任務的排序，選擇任務的執行，每當有新的任務進入作業系統中時就會執行排程。作業系統的排程往往都會限制住其效能，所以我們在此探討以ARM平台為基礎做Linux排程硬體化發展，利用硬體化加速提升作業系統效率。在排程硬體化中，我們主要實現紅黑樹的演算法，其中包含插入任務到紅黑樹、從紅黑樹中移除任務、檢查紅黑樹是否符合規定等。之後，加速排程硬體透過軟硬體的溝通傳輸資料，將任務傳輸給硬體做紀錄，建立紅黑樹，並且在紅黑樹中選擇下一個要執行的任務通知軟體端執行。
實驗當中，在插入任務方面大約節省有20%左右的時間，在移除任務方面大概有只有5%左右小幅縮減，所以平均下來至少有12%以上效能的提升，在任務越多的情況下，效能提升的幅度也越大。所以嵌入式系統的排程硬體化與一般嵌入式系統比較，能得到更佳的效能。

In this paper, we focus on the embedded system scheduling in hardware. The scheduling of the operating system achieves the sort of tasks and selects the next execution tasks. When a new task is forked by the operating system, the scheduler will start. Operating system scheduling often limits on its effectiveness, so we explore the Linux scheduling hardware on an ARM platform. We use hardware acceleration to enhance the efficiency of the operating system. In the scheduling hardware, we mainly implement red-black tree algorithm which contains inserting task into the red-black tree, removing the task from the red-black tree, and checking the red-black tree following rules. The scheduling hardware communication between the hardware and software transfer the task to record, build the red-black tree, select the next task which will be implement, and notice software side to receive data from the hardware.
In experiments, inserting the task can save about 20% of the time, and removing the task just can save only about 5%. In average, there is more than 12% time to be saved. When task numbers grow more and more, performance will be critical. Therefore, the hardware scheduling of embedded systems can gain a performance better.

[1] Takumi Nakanot ,Andy Utamaz, Mitsuyoshi Itabashis, Akichika Shiomiz, Masaharu Imai, “Hardware Implementation of a Real-time Operating System”, TRON '95 Proceedings of the The 12th TRON Project International Symposium, 1995 Page 34
[2] Paul Kohout, Brinda Ganesh, and Bruce Jacob. “Hardware support for real-time operating systems.” In Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis (CODES+ISSS '03). P45-51.
[3] Andrew Morton and Wayne M. Loucks. “A hardware/software kernel for system on chip designs.” In Proceedings of the 2004 ACM symposium on Applied computing (SAC '04), 869-875
[4] Jaehwan Lee, Vincent John Mooney, III, Anders Daleby, Karl Ingstrom, Tommy Klevin, and Lennart Lindh. “A comparison of the RTU hardware RTOS with a hardware/software RTOS.” In Proceedings of the 2003 Asia and South Pacific Design Automation Conference (ASP-DAC '03), 683-688
[5] Andr´e C. N´acul, Francesco Regazzoni, and Marcello Lajolo. “Hardware scheduling support in SMP architectures.” In Proceedings of the conference on Design, automation and test in Europe (DATE '07), 642-647.
[6] Sanggyu Park, Do-sun Hong, Soo-Ik Chae, “A hardware operating system kernel for multi-processor systems”, IEICE Electronics Express Vol. 5 (2008) No. 9 P 296-302
[7] Pramote Kuacharoen , Mohamed A. Shalan , Vincent J. Mooney III, “A Configurable Hardware Scheduler for Real-Time Systems”, in Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms, 2003, P96-101
[8] Jeronimo Castrillon, Diandian Zhang, Torsten Kempf, Bart Vanthournout, Rainer Leupers, and Gerd Ascheid. “Task management in MPSoCs: an ASIP approach.” In Proceedings of the 2009 International Conference on Computer-Aided Design (ICCAD '09), 587-594
[9] Weisstein, Eric W. "Red-Black Tree." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Red-BlackTree.html
[10] ARM Staff , "RealView Platform Baseboard for ARM926EJ-S User Guide , " 2003-2007.
[11] ARM Staff , "AMBA™ Specification , " 2000-2003 Rev 2.0 , " 1999
[12] ARM Staff , "RealView LT-XC4VLX100+ Logic Tile User Guide , " 2006-2007.
[13] D.P. Bovet and M. Cesati , "UNDERSTANDING THE LINUX KERNEL,3e " O’REILLY , 2006
[14] J. Corbet , A. Rubini and G.K. Hartman. "LINUX DEVICE DRIVERS,3e " O’REILLY , 2005
[15] ARM , http://www.arm.com/
[16] Xilinx , http://www.xilinx.com/
[17] Linux Source , http://www.kernel.org/