مشخصات مقاله:
عنوان فارسی مقاله:
استراتژی Task stealing مکان شناسی آگاه برای پردازشگرها در تراشه NUMA چند هسته ای
عنوان انگلیسی مقاله:
Topology Aware Task stealing for On-Chip NUMA Multi-Core Processors
کلمات کلیدی مقاله:
چند هسته ای، Task stealing، اشتراک کار، صف کارگر، متعادل بار، در چند هسته ای تراشه NUMA
مناسب برای رشته های دانشگاهی زیر:
مهندسی کامپیوتر
مناسب برای گرایش های دانشگاهی زیر:
معماری سیستم های کامپیوتری، مهندسی الگوریتم ها و محاسبات و سخت افزار
وضعیت مقاله انگلیسی و ترجمه:
مقاله انگلیسی را میتوانید به صورت رایگان با فرمت PDF از باکس زیر دانلود نمایید. ترجمه این مقاله با فرمت WORD – DOC آماده خریداری و دانلود آنی میباشد.
فهرست مطالب:
چکیده
1. مقدمه
1.1. ساختار
2. انگیزه
3. روش سرقت وظیفه موجود: مسائل
4. مکان شناسی سرقت وظیفه اگاه
4.1 توپلوژی معماری
4.2 اجتناب از انتخاب قربانی تصادفی
4.3 الگوریتم ارائه شده
5. آنالیز نتیجه
6. نتیجه گیری ها
قسمتی از مقاله انگلیسی و ترجمه آن:
Abstract
“The On Chip NUMA Architectures (OCNA) introduce a new challenge namely memory-latency to the scheduling methods. The language run-times and libraries try to explore the processing power of these multiple cores by mapping the user-created tasks on to these cores by using suitable scheduling algorithms with load balancing support to improve throughput. The popular load balancing techniques used are work-sharing and work-stealing and many run-time systems such as Cilk, TBB and wool implement task stealing algorithm to schedule the tasks on to the cores by multiplexing the program generated tasks on to the native worker threads supported by the operating system. But the task stealing strategy applied in present run-time systems assumes the sharing the last level cache (LLC) and common shared bus among all cores on Chip Multi Processor. It tries to optimize the utilization without considering the presence of multiple On Die DRAM controllers and their topological arrangements. Current task stealing technique also suffers from problem of randomly choosing the victim worker queue. In this paper we address these issues and propose a solution for these problems by suggesting few optimizations. Our proposed task stealing strategy dynamically analyzes the topology of the underlying hardware connections and models the group of cores and connections as a logical topology tree. This logical tree is translated into multiple worker pools called stealing domains. By restricting the task stealing within these domains, this strategy is implemented and shows an average of 1.24 times better performance on NAS Parallel Benchmark programs compared to popular runtimes Cilk and OpenMP.
چکیده
مشخصات روی تراشه NUMA (OCNA) چالش جدیدی به نام حافظه تاخیری را برای روش های زمانبندی معرفی می کند. زمان تنظیم و کتابخانه ها در تلاشند تا قدرت پردازش این هسته های متعدد را با نقشه برداری وظایف ایجاد شده کاربر در روی این هسته ها با استفاده از الگوریتم های زمانبندی مناسب همراه با پشتیبانی تعادل بار برای بهبود توان عملیاتی کشف کند. روش های محبوب تعادل بار، اشتراک گذاری کار و سرقت کار و بسیاری از سیستم های زمان اجرا همچون Cilk، TBB و الگوریتم دزدی کار پیاده سازی wool را به منظور زمانبندی وظایف بر روی هسته ها بوسیله ضرب کردن برنامه وظایف تولید شده توسط رشته ها بر روی کارگر بومی تغذیه شده توسط سیستم عملیاتی استفاده می کنند. از آنجا که استراتژی سرقت کار در سیستم های زمان اجرا به کار می رود از اینرو به اشتراک گذاری آخرین مخزن (LLC) و باس به اشتراک گذاری شده مشترک در میان تمام هسته ها، در تراشه چند پردازشگری فرض می شوند. این تلاش به منظور بهینه سازی استفاده بدون در نظر گرفتن حضور متعدد در کنترل کننده های Die DRAM و ترتیب های مکان شناسی آنها می باشد. همچنین روش دزدی کنونی از مشکل انتخاب تصادفی صف کارگر قربانی آسیب می بیند. در این مقاله این موضوعات را نشان می دهیم و راه حلی را برای این مسائل با پیشنهاد دادن چندین بهینه سازی ارائه می کنیم. استراتژی دزدی کار ارائه شده ما بطور دینامیکی توپولوژی را با تاکید بر اتصالات سخت افزار و مدل-های گروه هسته ای آنالیز می کند و بعنوان درخت مکان شناسی منطقی اتصال می دهد. این درخت منطقی درون دامنه های کارگر متعدد به نام دامنه های دزدی تعریف می شود. با محدود کردن دزدی وظیفه با این دامنه ها، این استراتژی اجرا می شود و میانگینی برابر با عملکرد بهتر 1.24 برابری در برنامه های معیار موازی NAS را در مقایسه با زمان های اجرای محبوب OpenMP و Cilk نشان می دهد.