بخشی از مقاله
چکیده: نگاشت کاربرد، یکی از مراحل مهم در جریان طراحی شبکه بر روی تراشه است که در آن وظایف یک کاربرد، بر روی هسته های توپولوژی شبکه بر روی تراشه، نگاشت می شوند. الگوریتم های متفاوتی برای انجام نگاشت معرفی شده اند که هدف در آن ها، معمولا بهینه کردن طراحی، حداقل کردن توان مصرفی و زمان اجرای مربوط به یک کاربرد است. وجود یک دسته بندی ساخت یافته برای این الگوریتم ها، موجب کاهش زمان پژوهشگران در ارائه ی الگوریتم های جدید می گردد. در این پژوهش، ضمن بررسی ویژگی های تعدادی از الگوریتم های معرفی شده در این زمینه، یک دسته بندی ساخت یافته برای این الگوریتم ها ارائه خواهد شد و سپس این تکنیک ها با یکدیگر مورد مقایسه قرار می گیرند تا بتوان با توجه به هدف مسئله، الگوریتم مناسب را انتخاب نمود.
واژگان کلیدی: الگوریتم های نگاشت، شبکه بر روی تراشه، نگاشت پویا، نگاشت ایستا
-1 مقدمه
به مرور و با افزایش بیشتر سرعت، تراشه های سیستم بر روی تراشه1 با معماری گذرگاه مبنا که در آن تمامی بلوک ها از یک گذرگاه مشترک برای ارتباط استفاده می کردند، جوابگوی افزایش حجم انتقال اطلاعات درون تراشه ای نبودند تا اینکه ایده ی استفاده از شبکه بر روی تراشه2 به جای گذرگاه در سیستم های چندپردازنده ای روی تراشه3 در دهه ی اخیر مطرح شده و بکار گرفته شد .[1]
طراحی شبکه بر روی تراشه، دارای چندین مرحله است که نگاشت کاربرد یکی از مراحل مهم در آن بحساب می آید. نگاشت کاربرد در شبکه بر روی تراشه، به عنوان یک مسئله ی NP-hard شناخته شده است .[2] در نگاشت کاربرد، یک کاربرد به وظایف متعددی تقسیم می شود و سپس هر وظیفه به یک هسته ی پردازشی خاص تخصیص داده می شود و در نهایت هسته ها در مکان مناسب خود قرار داده می شوند .[3] الگوریتم
1SoC : System on Chip 2NoC: Network on Chip 3MPSoC: Multi Processor System on Chip
های مختلفی برای این منظور ارائه شده اند که در آن ها اهداف متعددی از قبیل، کاهش تاخیر و تعادل گرمایی شبکه بر روی تراشه، کاهش توان مصرفی و زمان اجرای مربوط به یک کاربرد در نظر گرفته شده اند .[2] تاکنون مقاله ای که دسته بندی تمامی تکنیک های نگاشت را تحت پوشش قرار دهد، ارائه نشده است، لذا هدف این تحقیق، ارائه ی یک دسته بندی ساخت یافته برای الگوریتم های نگاشت در شبکه بر روی تراشه و مقایسه ی آن ها با یکدیگر است.
در ادامه مقاله به این صورت سازماندهی می شود که در بخش 2 انواع تکنیک های نگاشت بررسی خواهند شد، در بخش 3 تکنیک های نگاشت پویا بیان می شوند و در بخش 4 بر روی تکنیک های نگاشت ایستا تمرکز خواهد شد. نتیجه گیری نیز در بخش نهایی انجام خواهد گرفت.
-2 تکنیک های نگاشت
با توجه به این که وظایف در چه زمانی به هسته های پردازشی برای پردازش، تخصیص داده می شوند، تکنیک های نگاشت را می توان به دو دسته ی نگاشت پویا و نگاشت ایستا تقسیم کرد (شکل .(1
در نگاشت پویا یا آنلاین، تخصیص وظایف در زمان اجرای کاربرد انجام می گیرد. در این نوع نگاشت، همیشه سعی می شود تا گلوگاه های عملکرد کشف شوند و بارکاری بین هسته های
1
شکل :1 دسته بندی الگوریتم های نگاشت
پردازشی، توزیع شود. در این نوع نگاشت، سربار محاسباتی الگوریتم نگاشت، ممکن است تاخیر و مصرف انرژی کاربرد را در زمان اجرا افزایش دهد.
در نگاشت ایستا، تخصیص وظایف به هسته های پردازشی، به صورت آفلاین و قبل از اجرای کاربرد انجام می گیرد. برای یک کاربرد داده شده، این نوع نگاشت سعی دارد که همیشه بهترین مکان وظایف را در زمان طراحی مشخص کند. از آنجاییکه نگاشت قبل از اجرای کاربرد انجام می گیرد، الگوریتم نگاشت فقط یکبار اجرا می شود. برای شبکه بر روی تراشه، نگاشت ایستا پیشنهاد می شود، زیرا سربار محاسباتی موجود در نگاشت پویا به صورت چشمگیری بر روی عملکرد سیستم، تاثیر می گذارد و تاخیر کلی سیستم را افزایش می دهد .[4]
-3 تکنیک های نگاشت پویا
نگاشت پویا، یک استراتژی نگاشت آنلاین است. وظایف آماده برای پردازش، با توجه به بارکاری پردازنده ها در زمان اجرا، نگاشت می شوند؛ بنابراین مکان وظایف در شبکه بر روی تراشه می تواند در طول اجرای کاربرد تغییر کند.
در [3] یک تکنیک نگاشت حلزونی پویا برای نگاشت وظایف در زمان اجرا برای توپولوژیمشپیشنهاد شده است. یک کاربرد به تعدادی وظیفه تقسیم می شود و سپس به هرکدام از وظایفیک هسته اختصاص داده می شود و پس از آن، یک لیست از وظایف ایجاد می شود که در آن وظایف براساس اولویت ها در لیست قرار می گیرند. اولویت ها براساس سیاست های خاصی تعریف می شوند. وظایف به ترتیب از ابتدای لیست استخراج شده و مکان آن ها از طریق یک مسیر حلزونی از مرکز به سمت مرزهای معماری شبکه، جستجو می شود. در این نگاشت سعی
شده است تا وظایفی که باهم ارتباط دارند، مجاور یکدیگر نگاشت شوند، پس از انجام نگاشت زمان طراحی، در صورتی که در زمان اجرا، گراف وظایف تغییر کند، دو نوع الگوریتم نگاشت پویا را برای انتخاب خواهیم داشت، یک الگوریتم نگاشت پویا این است که تمامی مراحل مربوط به نگاشت حلزونی، یکبار دیگر انجام گیرند و یک الگوریتم نگاشت پویای دیگر این است کهنگاشت زمان اجرا، از نزدیکترین نقطه به مرکز معماری، که در معرض حذف، اضافه و یا تغییر مکان وظیفه است، آغاز شود. به این ترتیب امکان دارد که بعضی از وظایف در حال اجرا، حذف شوند و یا مکان آنها تغییر کند و یا وظایف جدیدی برای اجرا، اضافه گردند. در این الگوریتم سعی شده است که با کاهش زمان نگاشت پویا و زمان پیکربندی دوباره و نیز زمان انتقال وظیفه، زمان برقراری ارتباط بین وظایف نیز کاهش یابد.
در [5] یک الگوریتم برای نگاشت پویای کاربرد در شبکه بر روی تراشه معرفی شده است که موجب کاهش زمان اجرای کاربرد و کاهش ترافیک شبکه بر روی تراشه می شود. این الگوریتم دارای دو فاز است: در فاز اول یک نگاشت اولیه انجام می گیرد و در فاز دوم، با توجه به درخواست های ارتباطی و بار موجود در اتصالات4 شبکه بر روی تراشه، نگاشت پویا انجام می شود. فاز نگاشت پویا یکی از این تکنیک ها را بکار می برد: FF5، NN6، MMC7، MAC8، .PL9 در تکنیک FF، شبکه بر روی
4Links 5 First Free 6Nearest Nighbor
