Abstract
Recently, multi-core processors have become mainstream in processor design. To take full advantage of multi-core processing, computation-intensive real-time systems must exploit intra-task parallelism. In this paper, we address the problem of realtime scheduling for a general model of deterministic parallel tasks, where each task is represented as a directed acyclic graph (DAG) with nodes having arbitrary execution requirements. We prove processor-speed augmentation bounds for both preemptive and nonpreemptive real-time scheduling for general DAG tasks on multi-core processors. We first decompose each DAG into sequential tasks with their own release times and deadlines. Then we prove that these decomposed tasks can be scheduled using preemptive global EDF with a resource augmentation bound of 4. This bound is as good as the best known bound for more restrictive models, and is the first for a general DAG model. We also prove that the decomposition has a resource augmentation bound of 4 plus a constant non-preemption overhead for non-preemptive global EDF scheduling. To our knowledge, this is the first resource augmentation bound for non-preemptive scheduling of parallel tasks. Finally, we evaluate our analytical results through simulations that demonstrate that the derived resource augmentation bounds are safe in practice
چکیده
اخیراٌ پردازنده‌های چندهسته‌ای به یک جریان و رویکرد اصلی در طراحی پردازنده مبدل شده‌اند. به‌منظور بهره بردن کامل از فناوری پردازش چندهسته‌ای، سیستم‌های بلادرنگ با قابلیت محاسباتی بالا، از اصل موازات درون وظیفه‌ای بهره می‌برند. در این مقاله قصد داریم به بررسی و پاسخ به مسئله‌ی زمان‌بندی بلادرنگ برای یک مدل کلی از وظایف موازی قطعی بپردازیم که در این مدل، هر وظیفه به‌صورت یک گراف جهت‌دار غیر مدور (DAG) و با گره‌هایی که دارای نیازمندی‌های اجرای دلخواهانه هستند نشان داده می‌شود. محدودیت سرعت پردازنده را برای زمان‌بندی‌های بلادرنگ انحصاری و غیر انحصاری در وظایف DAG بر روی پردازنده‌های چندهسته‌ای اثبات می‌کنیم. در ابتدا هر DAG را به وظایف پشت سر هم تقسیم کرده که هرکدام از این وظایف، دارای زمان اجرا و مهلت زمانی مختص به خود می‌باشند. در ادامه، اثبات خواهیم کرد که این وظایفی که تقسیم‌شده‌اند را می‌تواند با استفاده از EDF جهانی انحصاری و با تعداد 4 منبع محدود زمان‌بندی کرد. این تعداد محدود را می‌تواند به‌عنوان بهترین تعداد منابع محدود در مدل‌های بازدارنده در نظر گرفت و می‌تواند آن را اولین مدل رایج DAG دانست. همچنین اثبات می‌کنیم که پروسه‌ی تقسیم وظایف دارای محدودیت منابع به تعداد 4 و یک سربار پیش‌دستی ثابت برای زمان‌بندی edf غیر انحصاری می‌باشد. با توجه به دانشی که در اختیارداریم، این مدل می‌تواند اولین مدل تقویت منابع محدود برای زمان‌بندی غیر انحصاری در وظایف موازی دانست. درنهایت، نتایج تحلیلی خود را از طریق شبیه‌سازی‌هایی که به ایمن بودن تقویت منابع محدود در عمل می‌پردازند اثبات خواهیم کرد.