تجزیه و تحلیل جریان داده

تجزیه و تحلیل جریان داده یکی از روش‌هایی است که با استفاده از آن می‌توان اطلاعات مربوط به داده‌هایی که در نقاط مختلف یک برنامهٔ رایانه‌ای محاسبه می‌شوند را فراهم کرد. گراف روند کنترلی برای تعیین قسمت‌های برنامه که به تعریف یک متغیر یا مقداردهی یک متغیر منجر شده‌است، استفاده می‌شود. تحلیل جریان داده اطلاعاتی را تولید می‌کند که معمولاً کامپایلرها از آن برای بهینه‌سازی برنامه استفاده می‌کنند.

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

یک راه ساده برای پیاده‌سازی تجزیه و تحلیل جریان داده این است که معادله جریان داده را برای هر گره از گراف روند کنترلی تنظیم کنیم و سپس به صورت محلی خروجی هر گره را از ورودی‌های آن محاسبه کنیم و این کار را تا زمانی که سیستم به نقطه ثابتی برسد تکرار کنیم.

اصول اساسی

تجزیه و تحلیل جریان داده فرایند تولید اطلاعات دربارهٔ شیوه به کار رفتن متغیرهای تعریف شده در برنامه است و تلاش می‌کند اطلاعات خاصی را در هر نقطه از اجرا به دست بیاورد. معمولاً به دست آوردن این اطلاعات در محدودهٔ بلوک‌های پایه کفایت می‌کند؛ زیرا با استفاده از آن به راحتی می‌توان اطلاعات نقاط مختلف بلوک پایه را به دست آورد. در تحلیل جریان رو به جلو، حالت خروجی یک بلوک تابعی از حالت ورودی آن بلوک است. این تابع ترکیب اثرات عبارات موجود در بلوک می‌باشد. حالت ورودی یک بلوک تابعی از حالت‌های خروجی اجداد آن بلوک می‌باشد. در نتیجه مجموعه ای از معادلات جریان داده به دست می‌آید: برای هر بلاک b:

$out_{b}=trans_{b}(in_{b})$

$in_{b}=join_{p\in pred_{b}}(out_{p})$

در این‌جا $trans_{b}$ تابع انتقال بلوک $b$ می‌باشد. این تابع روی حالت ورودی $in_{b}$ کار می‌کند و حالت خروجی $out_{b}$ را نتیجه می‌دهد و $join$ عملگر پیوند است که حالت‌های خروجی اجداد بلوک $b$ را ترکیب کرده و حالت ورودی $b$ را نتیجه می‌دهد.

بعد از حل این مجموعه از معادلات، می‌توان از حالت‌های ورودی و خروجی بلوک‌ها برای استخراج ویژگی‌های برنامه در محدوده بلوک‌های پایه استفاده کرد. با اعمال کردن تابع انتقال هر عبارت به صورت جداگانه، می‌توان اطلاعات مطلوب را در هر نقطه از بلوک پایه به دست آورد.

هر نوع خاصی از تحلیل جریان داده، تابع انتقال و عملگر پیوند خاص خود را دارد. برخی از مسئله‌های جریان داده، به تحلیل جریان رو به عقب نیاز دارند. این تحلیل به جز تابع انتقال و عملگر پیوند تقریباً مشابه تحلیل رو به جلو می‌باشد؛ تابع انتقال در این تحلیل روی حالت خروجی بلوک اعمال می‌شود و حالت ورودی آن را نتیجه می‌دهد و عملگر پیوند روی حالت‌های ورودی بلوک‌های فرزند اعمال شده و حالت خروجی یک بلوک را نتیجه می‌دهد.

می‌توانید شمایی ساده از گراف کنترل جربان داده را در تصویر زیر مشاهده کنید:

• 
  شمایی از یک گراف کنترل جریان داده

حل مسائل تجزیه و تحلیل جریان داده

رایج‌ترین روش برای حل مسائل تجزیه و تحلیل جریان داده، استفاده از الگوریتم‌های تکراری(به انگلیسی: iterative algorithm) است. محبوبیت این الگوریتم‌ها به خاطر سرعت، قدرت و سادگی پیاده‌سازی آن هاست. این الگوریتم، با یک تقریب از حالت ورودی هر بلوک شروع می‌کند و حالت خروجی را با اعمال کردن تابع انتقال هر بلوک بر روی حالت ورودی آن، به دست می‌آورد. حالت ورودی جدید برای هر بلوک با اعمال عملگر پیوند روی اجداد آن بلوک در گراف روند کنترلی به دست می‌آید. حال الگوریتم روی حالت‌های اولیه جدید تکرار خواهد شد و این تکرار تا زمانی ادامه پیدا می‌کند که سیستم به نقطه ثابتی برسد به این معنا که با تکرار فرایند الگوریتم، حالت ورودی و خروجی جدید برای هر بلوک با حالت ورودی و خروجی قبلی آن تفاوتی نکند.

همگرایی

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

• دامنه مقادیر باید مجموعه جزئاً مرتب و کراندار باشد.
• ترکیب تابع انتقال و پیوند باید یک تابع یکنوا نسبت به ترتیب مقادیر در دامنه باشد.

با وجود این دو شرط نتیجه یک تابع یکنوای کراندار است و یک تابع یکنوای کراندار حتماً همگرا است.

مقداردهی اولیه

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

اهمیت ترتیب پیمایش بلوک‌ها

ترتیب پیمایش بلوک‌ها در فرایند اجرای الگوریتم روی کارایی الگوریتم و زمان اجرای آن، تأثیر مستقیم دارد. عامل مهم دیگری که در این بحث اهمیت دارد، رو به جلو (به انگلیسی: forward) یا رو به عقب (به انگلیسی: backward) بودن تحلیل در گراف روند کنترل می‌باشد. اگر تحلیل ما رو به جلو باشد، بهتر است اجداد هر گره در گراف، قبل از آن شده باشند؛ چرا که حالت هر بلوک وابسته به حالات اجداد آن در گراف خواهد بود و اگر قبل از دیدن هر گره اجداد آن دیده شده باشند، سرعت همگرایی الگوریتم بیشتر خواهد بود. اگر در گراف حلقه نداشته باشیم، می‌توان ترتیبی از بلوک‌ها را پیدا کرد که تنها با یک بار اجرای الگوریتم روی هر بلوک، مقدار نهایی و صحیح هر بلوک به دست آید. برخی از ترتیب‌های ممکن برای پیمایش گراف در اجرای الگوریتم عبارتند از:

• پیمایش تصادفی: در این روش بلوک‌ها به ترتیب تصادفی پیمایش می‌شوند و به رو به جلو یا رو به عقب بودن تحلیل توجهی نمی‌شود به همین دلیل عملکرد این مدل ترتیب پیمایش به نسبت پیمایش‌های دیگر ضعیف است.
• پیمایش پس ترتیب (به انگلیسی: Postorder): این ترتیب پیمایش برای تحلیل رو به عقب مناسب است. در این روش هر گره زمانی دیده می‌شود که همهٔ فرزندان آن در گراف دیده شده باشند. برای پیاده‌سازی این روش پیمایش، از الگوریتم جستجوی اول عمق استفاده می‌شود.
• پیمایش عکس پس ترتیب (به انگلیسی: Reverse postorder): این ترتیب پیمایش برای تحلیل رو به جلو مناسب است. در این روش هر گره قبل از هر یک از فرزندانش دیده خواهد شد؛ مگر اینکه گره فرزند یک یال رو به عقب داشته باشد. (این روش با پیمایش پیشوندی (به انگلیسی: preorder) متفاوت است)

الگوریتم تکرار راند-رابین

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

for i ← 1 to N

initialize node i

while (sets are still changing)

for i ← 1 to N

recompute sets at node i

ترتیب پیمایش گره‌ها در این روش ثابت است.

رویکرد لیست کار

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

Worklist ← ∅

for i ← 1 to N

initialize the sets at node i add i to the Worklist

while (Worklist ≠ ∅)

remove a node i from the Worklist recompute set at node I

if new set ≠ old set for i then

add each successor of i to Worklist, uniquely

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

• تحلیل متغیر زنده
• درهم کردن ثابت
• تفسیر انتزاعی