| 摘要: | MapReduce是由Google所提出用於處理大量密集式資料的分散式平行運算架構。使用MapReduce的使用者只要撰寫Map以及Reduce這兩個Function，並輸入待處理的資料，即可以自動的完成需要大量運算資源的工作，如網頁搜尋、數值統計等。但是較少使用者將2D to 3D這種高複雜度且運算時間較長的影像處理應用放置於MapReduce處理，然而這種高複雜度以及高運算量的應用若是透過使用MapReduce來進行運算則可以用來增加其處理效能。
此外，在較早的文獻中，有許多的研究以及應用都被拿來建置在MapReduce上，但是這些研究以及應用所存在的環境需要擁有完整的運算資訊才能被正確地運行。而本論文的運作環境為一即時性的影像處理環境，所以如果沒有一個較佳的排程機制負責處理影像即時地被儲存在系統裡，將無法有效地將即時性的應用程序移植到MapReduce系統上。
本論文實作一個運作在MapReduce上的多使用者(Multi-user)的2D to 3D系統，並讓Map負責處理高複雜度以及高運算量的影像處理程序，而Reduce負責收集Map處理後的Intermediate Data並輸出。當多個使用者同時競爭MapReduce的資料來處理2D to 3D的應用時，就會造成等待Map處理的資料被正在處理的使用者所延誤，而Reduce必需等待所有Map處理完成後才能產生輸出結果的情形，。因此，本論文提出了一個新的排程機制，讓MapReduce能夠自動依照任務的處理進度自動切換下一個任務執行，並減少Reduce的閒置時間，我們稱之為Dynamic Switch of Reduce Function (DSRF) Algorithm。
MapReduce, a programming model proposed by Google, is designed for distributed parallel computing to process vast amounts of data. MapReduce users write the Map and Reduce functions, input the data to be processed and the task will be finished automatically. Hadoop, a distributed file system designed for implementing Google MapReduce, is adopted by many enterprises for daily data-intensive applications. Most users process short tasks using MapReduce; in other words, most tasks handled by the Map and Reduce functions require low response time. Currently, quite few users use MapReduce for 2D to 3D image processing, which is highly complicated and requires long execution time. However, in our opinion, MapReduce is exactly suitable for processing applications of high complexity and high computation.
The other researches use MapReduce to build their applications. In the above researches, they will store the complete data into their file system. In our paper, our system is a real-time image processing system and the file system will get the real-time image continually. By the way, the system doesn’t have a schedule algorithm to solve the real-time application problem.
This paper implements MapReduce on an integrated 2D to 3D multi-user system, in which Map is responsible for image processing procedures of high complexity and high computation, and Reduce is responsible for integrating the intermediate data processed by Map for the final output. Different from short tasks, when several users compete simultaneously to acquire data from MapReduce for 2D to 3D applications, data that waits to be processed by Map will be delayed by the current user and Reduce has to wait until the completion of all Map tasks to generate the final result. Therefore, a novel scheduling scheme, Dynamic Switch of Reduce Function (DSRF) Algorithm. |
