چکيده— چارچوب "کاهش نگاشت" به عنوان راه حلی موثر برای پردازش داده های بزرگ و موازی مورد توجه قرار گرفته است. مضمون این مقاله، گردش کاری پردازش داده های بزرگ را به شکل یک گراف DAG (گراف جهتدار چرخشی) مورد بررسی قرار می دهد که از کارهای کاهش نگاشت تشکیل یافته است. در یک محیط پردازشی ناهمگن، سرعت پردازش حتی ممکن است روی یک اسلات، متفاوت باشد که این مورد به ماهیت کارهای مختلف وابسته می باشد. برای رفع این مساله، در این مقاله یک الگوریتم بهبود یافته زمانبندی گردش کاری کاهش نگاشت، ارائه شده است. این الگوریتم از یک مرحله اولویت بندی کار و یک مرحله‌ی اختصاص وظیفه تشکیل می شود. در ابتدا می توان کار ها را به انواع I/O-intensive (عملیات ورود و خروج حجم انبوهی از داده ها) و computing-intensive (عملیات پردازش حجم انبوهی از داده ها) تقسیم بندی نمود و در ادامه اولویت های تمامی کار ها بر اساس نوع آنها تعیین می شوند. سپس، شکاف‌های مناسب به هر بلوک اختصاص می‌یابد؛ و وظایف کاهش نگاشت در گردش کاری با توجه به ویژگی محلیت یا محلی سازی داده‌ها، زمانبندی می‌شوند. نتایج تجربی نشان می‌دهند که الگوریتم بهبود یافته زمانبندی گردش کاری کاهش نگاشت، می‌تواند کارایی زمانبندی وظیفه و منطقی بودن اختصاص منابع در پردازش ناهمگن را افزایش دهد.
کلمات کليدي- Hadoop، خوشه ناهمگن، کاهش نگاشت، زمانبندی، گردش کاری

Abstract:  The MapReduce framework is considered to be an effective resolution for huge and parallel data processing. This paper treats a massive data processing workflow as a DAG graph consisting of MapReduce jobs. In a heterogeneous computing environment, the computation speed can be different even on the same slot depending on various jobs. For this problem, this paper proposes an optimized MapReduce workflow scheduling algorithm. This algorithm comprises a job prioritizing phase and a task assignment phase. Firstly, the jobs can be classified as I/O-intensive and computing-intensive, and the priorities of all jobs are computed according to their corresponding types. Then, the suitable slots are allocated for each block, and the MapReduce tasks in the workflow are scheduled with respect to data locality. The experimental results show that the optimized MapReduce workflow scheduling algorithm can improve the performance of task scheduling and the rationality of resources allocation in heterogeneous computing.
Keywords -Hadoop - heterogeneous cluster - MapReduce - scheduling - workflow