کدگذاری حالتی برای قدرت کم

کدگذاری حالتی برای قدرت کم (انگلیسی: State encoding for low power) یک الگوی منحصر به فرد از صفر و یک را به هر حالت تعریف شده ازماشین حالات متناهی(FSM) اختصاص می‌دهد. به‌طور سنتی، معیار طراحی برای سنتز FSM سرعت، مساحت یا هر دو بود. با توجه به قانون مور، با پیشرفت تکنولوژی تراکم و سرعت مدارهای مجتمع به‌طور نمایی افزایش یافته‌است. با این کار، ناگزیر اتلاف قدرت در هر ناحیه افزایش می‌یابد، که باعث شده‌است طراحان برای دستگاه‌های رایانه‌ای قابل حمل و پردازنده‌های با سرعت بالا در هنگام طراحی به اتلاف قدرت به عنوان یک پارامتر حیاتی توجه کنند.

پیش‌زمینه

سنتز FSM شامل سه مرحله عمده می‌شود:

1. به حداقل رساندن حالت: همان‌طور که از نامش برمی‌آید، تعداد حالاتی که نیاز به نمایش FSM دارند، به حداقل می‌رسد. این روش شامل تکنیک‌ها و الگوریتم‌های مختلف مانند جداول اشیاء، تطابق ردیف‌ها، الگوریتم پارتیشن‌بندی پیوندی، شناسایی و حذف حالت‌های معادل یا کارهای اضافی می‌شود.
2. تخصیص یا کدگذاری حالت: شامل انتخاب نمایه‌های از نوع بولین از حالت‌های داخلی FSM می‌شود. به عبارت دیگر به هر حالت یک کد باینری منحصر به فرد را اختصاص می‌دهد. انتخاب روش رمزگذاری مناسب بسیار مهم است. تصمیم اشتباه می‌تواند باعث شود FSM از منطق بیش از حد استفاده کند، بسیار کند شود، قدرت بیشتری مصرف کند یا هر ترکیبی از این‌ها را مصرف کند.
3. به حداقل رساندن منطق ترکیبی: از کدهای حالت غیر اختصاصی به منظور کاهش منطق ترکیبی استفاده می‌کند.

تکنیک‌های کدگذاری موجود

برخی از تکنیک‌هایی که به‌طور گسترده برای رمزگذاری حالت استفاده می‌شوند عبارتند از:

• کدگذاری داغ در این روش برای هر حالت تنها یک بیت از متغیر حالت " (داغ) است و تمام بیت‌های دیگر " هستند. فاصله همینگ برای این تکنیک برابر ۲ است. یک داغ برای هر حالت نیاز به یک فلیپ فلاپ در FSM دارد. در نتیجه، ماشین حالت در حال حاضر "رمزگشایی" شده‌است، بنابراین حالت دستگاه به سادگی با تعیین اینکه چه فلیپ فلاپی فعال است تعیین می‌شود. این روش پهنای منطق ترکیبی را کاهش می‌دهد و به همین علت ماشین حالت آن نیاز به سطح پایین‌تر منطق بین ثبات‌ها دارد، پیچیدگی آن کم شده و سرعت آن بیشتر می‌شود.
• کدگذاری باینری

در این روش تعداد بیت‌ها (b) به ازای هرحالت بستگی به تعداد حالت‌ها (n) دارد. این رابطه با معادله زیر تعریف می‌شود:

 b = log2(n)

در این تکنیک، حالت‌ها در توالی باینری اختصاص داده می‌شوند که در آن حالت‌ها با شروع از صفر و شماره‌گذاری می‌شوند. واضح است که تعداد فلیپ فلاپ‌های مورد استفاده برابر با تعداد بیت(b) است. از آنجا که رمزگذاری باینری از حداقل تعداد (flip-flops) برای رمزگذاری یک ماشین استفاده می‌کند، فلیپ فلاپ‌ها به‌طور حداکثر استفاده می‌شوند. در نتیجه در مقایسه با روش گدگذاری داغ منطق ترکیبی بیشتری برای تقسیم هر حالت مورد نیاز است. همچنین در مقایسه با گدگذاری‌داغ تعداد flip-flops کمتری نیاز است اما فاصله همیلتنی به اندازه تعداد بیت‌ها (b) است که رقم بدتری است.

• کدگذاری خاکستری در کد خاکستری که با نام کد باینری منعکس شده نیز شناخته می‌شود، حالت‌ها به گونه‌ای تعریف شده‌اند که کدهای حالت متوالی فقط در یک بیت تفاوت دارند. در این کدگذاری نیز رابطه بین تعداد بیت‌ها و تعداد حالت‌ها برابر است با:

 b = log2(n)

تعداد فلیپ فلاپ‌های مورد استفاده و پیچیدگی منطق رمزگشایی در این روش مشابه رمزگذاری دودویی است. اما فاصله همینگ در کد خاکستری همیشه برابر۱ است. سایر تکنیک‌های رمزگذاری رمزگذاری مبتنی بر خروجی، MUSTANG, NOVA

انگیزه

برای شمارنده‌ها، کد گری دارای حداقل فعالیت سوئیچینگ است و بنابراین برای طراحی با قدرت کم مناسب است. کدگذاری گری زمانی که حالت‌ها به صورت ترتیبی تغییر می‌کنند، مناسب تر است. در تغییر حالت دلخواه، کد FSM Gray برای طراحی‌های کم قدرت ناکام می‌ماند. برای چنین FSMهایی، رمزگذاری داغ تضمین می‌کند برای هر تغییر حالت تنها دو بیت تغییر می‌کنند. اما از آنجا که تعداد متغیرهای حالت مورد نیاز برابر با تعداد حالت‌ها است، با افزایش تعداد حالت‌ها، رمزگذاری داغ به یک راه حل غیرعملی تبدیل می‌شود، عمدتاً به این دلیل که با افزایش تعداد ورودی و خروجی‌های مدار، پیچیدگی و بار خازنی افزایش پیدا می‌کند. برنامه‌نویسی باینری بدترین حالت برای قدرت کم است زیرا حداکثر فاصله همینگ برابر با تعداد متغیرهای حالت است. نیاز به یک راه حل برای تغییر حالت خودسرانه FSM منجر به تکنیک‌های رمزگذاری حالت متعددی شده‌است که تمرکز آن‌ها بر روی کاهش فعالیت سوئیچینگ در هنگام انتقال حالت است.

تکنیک‌ها

رویکرد مبتنی بر ستون برای تخصیص حالت کم قدرت

هدف این رویکرد این است که به وسیله مدارهای ترتیبی و انتخاب حالاتی که باعث کمینه شدن تغییر حالت‌ها شود، اتلاف انرژی را کاهش دهد؛ بنابراین بخش ترکیبی FSM دارای احتمال انتقال ورودی پایین‌تری است و بیشتر شبیه به تخلیه قدرت کم هنگام تولید است. این الگوریتم از ماتریس بولینی با ردیف‌های متناظر با کدهای حالت و ستون‌های متناظر با متغیرهای حالت استفاده می‌کند. یک متغیر حالت تنها در یک زمان در نظر گرفته شده‌است و تلاش می‌کند مقدارش را به حالتی در FSM اختصاص دهد، به‌طوری‌که دوست دارد تعداد سوئیچینگ برای تخصیص کلی را به حداقل برساند. این روش برای متغیر بعدی تکرار می‌شود. از آنجا که روش کمینه‌سازی ستون بر روی ستون‌ها اعمال می‌شود، این روش به عنوان رویکرد مبتنی بر ستون نامگذاری شده‌است.

تخصیص حالت چندمنظوره

تکنیک تخصیص حالت چندمنظوره(multi-code) به وسیله محدود کردن حالت‌های اضافه، به صورت اولویت‌بندی شده کدگذاری می‌کند؛ بنابراین هر حالت می‌تواند توسط تعداد متغیرحالت (بیت) کمتری رمزگذاری شود. علاوه بر این فلیپ-فلاپ‌های مربوط به حالت‌های غایب می‌توانند گیت‌های کلاک باشند.

تخصیص حالت مبتنی بر پروفایلینگ

این روش از اطلاعات حلقه پویا که از داده‌های پروفایل FSM استخراج می‌شوند استفاده کرده و برای کاهش سوئیچینگ استفاده می‌شود. در زیر مراحل استفاده شده در این تکنیک آمده‌است:

1. پروفایل کردن حالت FSM اطلاعات مربوط به رفتار پویای FSM را به عنوان یک مجموعه داده ورودی مرتبط جمع‌آوری می‌کند.
2. تشخیص‌گر حلقه در اثرات حالت‌ها جستجو کرده و هر حلقه را پیدا کرده و دخیره می‌کند و در نهایت فرکانس حلقه‌ها را به دست می‌آورد.
3. انتساب حالت، بر اساس داده‌های جمع‌آوری شده در دو مرحله قبل و به منظور به حداقل رساندن مصرف سوئیچینگ متغیرهای حالت را به هر حالت اختصاص می‌دهد. سه الگوریتم برای انتساب متغیرهای حالت وجود دارد:

• الگوریتم تخصیص حالت DFS پایه‌ای
• الگوریتم تخصیص حالت DFS مبتنی بر حلقه
• الگوریتم تخصیص حالت مبتنی بر حلقه برپایه حالات هیوریستیک

تکنیک‌های دیگر

• بعضی از تکنیک‌ها، گراف انتقال حالت (STG) را برای پیاده‌سازی دو سطحی و چند سطحی هدفمند کم قدرت رمزگذاری می‌کنند.
• رمزگذاری مجدد مدارهای ترتیبی موجود برای بهینه‌سازی قدرت مورد توجه قرار گرفته‌است.
• روش Depth_First، روش حداقل، روش 1_Level، روش 1_level_tree، که در آن تمرکز بر روی اختصاص متغیرهای حالت به حالت‌های دیگر است به‌طوری‌که سوئیچینگ کاهش یابد.
• به‌علاوه فقط کدگذاری حالتهای کم مصرف، بعضی از تکنیک‌ها شامل تجزیه FSM به دو یا چند ماشین زیرزمینی می‌شود که تنها یکی از آن‌ها اکثر زمان‌ها فعال است. با استفاده از این، دیگر ماشین‌ها می‌توانند به‌طور هم‌زمان یا به‌طور مداوم یا برق متصل شوند.

جستارهای وابسته

• مینیم‌سازی دی‌اف‌ای

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «State encoding for low power». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳ ژانویه ۲۰۱۸.