A Hybrid Real-Time Scheduling Approach for Large-Scale Multicore Platforms

ABSTRACT

We propose a hybrid approach for scheduling real-time tasks on large-scale multicore platforms with hierarchical shared caches. In this approach, a multicore platform is partitioned into clusters. Tasks are statically assigned to these clusters, and scheduled within each cluster using the preemptive global EDF scheduling algorithm. We show that this hybrid of partitioning and global scheduling performs better on large-scale platforms than either approach alone. We also determine the appropriate cluster size to achieve the best performance possible, given the characteristics of the task set to be supported.

INTRODUCTION

Multicore architectures, which include several processors on a single chip, are being widely touted as a solution to the “thermal roadblock” imposed by single-core designs. Most chip makers have released dual- core chips, and afew designs with more than two cores have been released as well. For instance, both Intel and AMD have released four-core chips, Sun recently released its eight-core Niagara chip, and Intel is expected to release chips with 80 cores within five years [6]. Azul, a company that builds Java appliances, has created 48-core chips that are used in systems with up to 768 total cores . These appliances are used to process large numbers of transactions with soft real-time requirements. To summarize, largescale multicore platforms with tens or even hundreds of cores per chip may become a reality fairly soon and applications with (soft) real-time constraints will likely be deployed on them. In this paper, we consider the issue of how to efficiently schedule soft real-time workloads on such large platforms. In most proposed multicore platforms, different cores share on-chip caches. For example, by the end of 2007, both Intel and AMD plan to have chips with a cache shared by four cores, and the aforementioned Azul chip has a shared cache for each group of eight cores. To effectively exploit the available parallelism in these systems, such caches must not become performance bottlenecks .In fact, the issue of efficient cache usage on multicore platforms is one of the most important problems with which chip makers are currently grappling. This will become an even more pressing issue as the number of cores on a chip increases. For example, Intel envisions a 32- core platform where all cores share a cache.

چکیده

ما پیشنهاد یک روش ترکیبی برای برنامه ریزی وظایف در زمان واقعی در سیستم های چند منظوره در مقیاس بزرگ با مخازن ذخیره سلسله مراتبی. در این رویکرد، یک پلت فرم چند هسته ای به خوشه ها تقسیم می شود. وظایف به طور ایستا به این خوشه ها اختصاص داده می شوند و در هر خوشه ای برنامه ریزی شده با استفاده از الگوریتم پیشنهادی الگوریتم پیشنهادی EDF برنامه ریزی شده. ما نشان می دهیم که این هیبرید پارتیشن بندی و برنامه ریزی جهانی در سیستم های بزرگ در مقیاس بزرگ بهتر از هر دو روش است. ما همچنین اندازه خوشه مناسب را برای رسیدن به بهترین عملکرد ممکن تعیین می کنیم، با توجه به ویژگی های وظیفه ای که برای حمایت وجود دارد.

مقدمه

معماریهای چندگانه که شامل چندین پردازنده در یک تراشه هستند، به طور گسترده به عنوان یک راه حل برای “موانع حرارتی” تحمیل شده توسط طرح تک هسته ای مورد استفاده قرار می گیرد. اکثر تراشه سازندگان تراشه های دو هسته ای را منتشر کرده اند و طرح هایی با بیش از دو هسته نیز وجود دارد. به عنوان مثال، هر دو اینتل و AMD تراشه های چهار هسته ای را منتشر کرده اند، خورشید به تازگی هشت هسته ای از تراشه نایگارا خود را منتشر کرده است، و انتظار می رود که اینتل ظرف پنج سال، تراشه های 80 هسته را منتشر کند [6]. Azul، شرکتی که دستگاههای Java را تولید می کند، تراشه های 48 هسته ای را که در سیستم های با 768 هسته کامل استفاده می شود، ایجاد کرده است. این دستگاه ها برای پردازش تعداد زیادی از معاملات با نیازهای زمان واقعی نرم افزار مورد استفاده قرار می گیرند. به طور خلاصه، سیستم عامل های چند هسته ای بزرگتر با ده ها یا حتی صدها هسته در هر تراشه ممکن است به زودی تبدیل به یک واقعیت شود و برنامه های کاربردی با محدودیت های (نرم) زمان واقعی بر روی آنها اعمال شود. در این مقاله، ما در مورد چگونگی برنامه ریزی کارهای نرم افزاری بارگیری زمان واقعی در چنین سیستم عامل های بزرگ را در نظر می گیریم. در اکثر پلت فرم های متعدد چند هسته ای، هسته های مختلف در حافظه های مبتنی بر تراشه به اشتراک می گذارند. به عنوان مثال، تا پایان سال 2007، هر دو اینتل و AMD قصد دارند تراشه هایی با یک حافظه پنهان که توسط چهار هسته مشترک به اشتراک گذاشته شود، و تراشه Azul مذکور دارای مخزن مشترک برای هر گروه از هشت هسته باشد. به طور موثر بهره برداری از موازی در دسترس در این سیستم ها، این نوع حافظه ها نباید دچار تنگناهای عملکردی شوند. در واقع، مسئله استفاده از کشف کارآمد در سیستم عامل های چندرسانه ای یکی از مهم ترین مشکلات موجود در حال حاضر است که سازندگان تراشه در حال تسخیر هستند. این مسئله حتی بیشتر به عنوان تعداد هسته ها در تراشه افزایش می یابد. به عنوان مثال، اینتل یک پلت فرم 32 هسته ای را معرفی می کند که تمام هسته ها یک حافظه پنهان دارند.

Year: 2007

Publisher : IEEE

By : John M. Calandrino , James H. Anderson , and Dan P. Baumberger