تبدیل مدار semi-systolic به systolic

اگر مداری چیزی را همزمان برای همه ی پردازنده ها بفرستد یا همزمان مقدار تعدادی پردازنده را جمع کند و ... . (خلاصه همزمان یک سری کار روی همه انجام بدهد) دیگر مدار ما systolic نیست. اگر بتوان چنین مداری را به systolic تبدیل کرد به این مدار semi-systolic می گویند و در ادامه شرایط آن و نحوه ی تبدیل آن را نشان می دهیم.

مدار بالا در مدل میلی است (یعنی مقدار خروجی علاوه بر رجیسترها از مدار هم می آید. (خط چین ها از مدار می آیند.)

گراف متناظر آن به صورت زیر است: (همان طور که زیر شکل نوشته شده تعداد بافرها را وزن یالها می گیریم و پردازنده ها راسها هستند.)

اگر گرافی که به دست می آید دور صفر نداشته باشد (دوری که همه ی یالهای آن وزن صفر داشته باشند) می توانیم آن را به systolic تبدیل کنیم.

مرحله اول: همه ی بافرها را چند برابر کنیم، با این کار عملکرد مدار تغییر نمی کند و فقط تاخیر ایجاد می شود. در گراف همه ی یالها در یک عدد ضرب می شوند. عددی را برای این کار انتخاب می کنیم که همه ی دورها وزنشان از تعداد یالهایشان بیشتر یا مساوی باشد؛ که بعدا بتوانیم با ایجاد تاخیر در گره ها یالهای با وزن صفر را از بین ببریم. (چون کلا مشکل ما این است که یک سری کار همزمان با هم دارند انجام می شوند.)

مرحله دوم: با عمل lagging در گره ها تاخیر ایجاد کنیم. (شکل زیر)

می خواهیم ثابت کنیم که هر مداری که این شرط (نبود دور صفر) را داشته باشد (semi-systolic باشد)، می توانیم با یک دنباله از عملیات قبل به یک مدار systolic تبدیل کنیم.

اثبات: اینکه با انجام عملیات lagging شرط semi-systolic بودن به هم نمی خورد تقریبا بدیهی است. می خواهیم ثابت کنیم که حتما با دنباله ای از عملیات lagging می توانیم از S به S' برسیم.

استقرا: پایه استقرا همان حالت اولیه است که با 0 عمل lagging به یک مدار semi-systolic می رسیم (خود S!)

فرض استقرا: برای تعداد توابع lagging کمتر از L مدار semi-systolic بماند.

حکم استقرا: برای L تابع lag مدار semi-systolic است.

اگر گره ای باشد که lag آن مثبت باشد و درجه ی همه ی یالهای خروجی آن ناصفر باشد می توان روی آن یک عمل lag انجام داد. با این کار یکی از تعداد عملیات lag لازم کم می شود و L-1 عمل lag طبق فرض استقرا مدار را semi-systolic می کند.

اگر چنین گره ای نباشد، یعنی همه ی راسهای با lag مثبت یال خروجی صفر دارند. می دانیم با طی هر یال با وزن صفر از یک راس با lag مثبت به راس دیگری با lag مثبت می رسیم، چون اگر یک سر آن وزن یال را کم می کند دیگری باید آن را اضافه کند وگرنه به یال با وزن منفی می رسیم. پس اگر یک راس مثبت یال صفر داشته باشد آن یال به یک راس مثبت دیگر می رود، با دنبال کردن یالهای به وزن صفر خروجی راسهای با lag مثبت یک دور به وجود می آید که وزن آن صفر است که با فرض semi-systolic بودن S (نه S') در تناقض است. (چون ثابت کردیم وزن دورهای S' و S برابرند.)

برای lag منفی هم مشابه همین استدلال را می توانیم انجام بدهیم.

(پایان اثبات)

باید مقادیر رجیسترهایی که جا به جا می کنیم را هم اصلاح کنیم.

حالا می خواهیم تابع lag را به دست بیاوریم.

اثبات:

تابع بالایعنی کوتاهترین مسیر از هر گره تا host در گراف G-1 تابع lag مورد نظر است. ثابت می کنیم این تابع مدار را systolic می کند.

مثال: برای سوال palindrome که در ابتدای متن گفته شد، باید وزن یالهای گراف را در 2 ضرب کنیم شرایط semi-systolic را پیدا می کند و با استفاده از قضیه قبل مدار زیر به دست می آید.

راهنمایی حل سوالات آخر فصل با این روش!