Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การจัดตารางงานโดยคำนึงถึงพลังงานสำหรับการคำนวณภารกิจเคลื่อนที่แบบวิวิธพันธุ์
Year (A.D.)
2017
Document Type
Thesis
First Advisor
Chidchanok Lursinsap
Second Advisor
Peraphon Sophatsathit
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Computer Science and Information Technology
DOI
10.58837/CHULA.THE.2017.179
Abstract
The problem of scheduling a set of dependent tasks from a user mobile device to several servers in communication cells while the user is moving along these cell in various speed is studied in this thesis. The challenging issue is the execution speed of each server and the speed of user's movement are not compatible. This leads to the difficulty of assigning and finishing the subset of scheduled dependent tasks to each server within the limitation of execution time during passing a cell. Another concern involved this study is the constraints on the length of makespan in terms of minimum communication time among servers in the same cell and the energy consumed by the servers as well as the energy spent by user's mobile device. This study proposed a new algorithm to schedule a set of dependent tasks under the constraints from these issues. Three new concepts of (1) selecting cells for executing scheduled tasks proposed algorithm, (2) partitioning and scheduling tasks to be assigned to the servers in the selected cell, and (3) shuffling the tentatively assigned tasks of all servers to minimize the makespan and energy consumption were proposed in this study. The experimental results were compared with the current practically used algorithms, i.e. HEFT, PEFT, HETS based on several complex synthetic task flow graphs. The obtained results showed that the most of makespan lengths found by our algorithm are shorter than those found by the other algorithms. But in terms of energy consumption, all results scheduled by our algorithm significantly consume less energy than those from the other algorithms.
Other Abstract (Other language abstract of ETD)
ปัญหาของการจัดลำดับการส่งชุดของงานที่มีความสัมพันธ์กันจากโทรศัพท์มือถือของผู้ใช้ไปยังเครื่องที่ให้บริการหลายตัวที่เชื่อมต่อกับเซลล์เครือข่ายขณะที่ผู้ใช้กำลังเคลื่อนที่ไปตามเซลล์เหล่านี้ด้วยความเร็วต่าง ๆ ได้รับการศึกษาในวิทยานิพนธ์ฉบับนี้ ปัญหาที่ท้าทายคือความเร็วในการทำงานของแต่ละเครื่องที่ให้บริการและความเร็วในการเคลื่อนที่ของผู้ใช้ทำให้ไม่สามารถทำงานร่วมกันได้อย่างลงตัวซึ่งจะนำไปสู่ความยากในการกำหนดกำหนดกลุ่มงานที่มีความสัมพันธ์กันให้กับแต่ละเครื่องที่ให้บริการ โดยต้องใช้เวลาในการประมวลผลกลุ่มงานพร้อมกันกับการใช้พลังงานในการสื่อสารระหว่างเครื่องที่ให้บริการภายในเซลล์เดียวกันและพลังงานที่ใช้ในอุปกรณ์ของผู้ใช้ให้น้อยที่สุด การศึกษาครั้งนี้นำเสนอขั้นตอนวิธีใหม่ในการจัดตารางงานที่มีความสัมพันธ์กันภายใต้ข้อ จำกัด จากปัญหาเหล่านี้ สามแนวคิดใหม่เกี่ยวกับ (1) การเลือกเซลล์เพื่อดำเนินการตามขั้นตอนที่กำหนดให้กับอัลกอริทึม (2) การแบ่งและกำหนดลำดับงานให้กับเครื่องที่ให้บริการในเซลล์ที่เลือกและ (3) สลับลำดับงานที่กำหนดไว้เบื้องต้นเพื่อให้ความยาวของการประมวลผลสั้นที่สุดและใช้พลังงานน้อยที่สุด ได้ถูกนำเสนอในการศึกษานี้ จากผลการทดลองเปรียบเทียบกับขั้นตอนวิธีที่ใช้ในปัจจุบันเช่น HEFT, PEFT, HETS จากกราฟการทำงานของงานสังเคราะห์ที่ซับซ้อนหลายแบบ ผลลัพธ์ที่ได้แสดงให้เห็นว่าส่วนใหญ่ของความยาวของการประมวลผลที่พบโดยขั้นตอนวิธีที่นำเสนอจะสั้นกว่าที่พบในขั้นตอนวิธีอื่น ๆ แต่ในแง่ของการใช้พลังงานผลลัพธ์ทั้งหมดที่กำหนดโดยขั้นตอนวิธีที่นำเสนอจะใช้พลังงานน้อยกว่าที่ได้จากขั้นตอนวิธีอื่น ๆ อย่างมีนัยสำคัญ
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Rujivorakul, Vittayasak, "Energy aware scheduling for heterogeneous mobile task computing" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 669.
https://digital.car.chula.ac.th/chulaetd/669