وابستگی داده

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

به‌طور کلی، اگر اجرای هم‌زمان دو دستور ممکن نباشد و اجرای آن‌ها باید به صورت متوالی انجام شود، آن‌ها را وابسته می‌گوییم.

انواع وابستگی عبارت اند از:

• وابستگی داده
• وابستگی نام
• وابستگی کنترل

در نظریه کامپایلر، برای تشخیص وابستگی از فنون آنالیز وابستگی (به انگلیسی: Dependence Analysis) استفاده می‌شود.

وابستگی داده

دو دستور ${\displaystyle S_{1}}$ و ${\displaystyle S_{2}}$ را در نظر می‌گیریم که دستور ${\displaystyle S_{2}}$در جایی بعد از دستور ${\displaystyle S_{1}}$ قرار دارد. ${\displaystyle I(S_{i})}$ و ${\displaystyle O(S_{i})}$ را به ترتیب مجموعه خانه‌هایی از حافظه که ${\displaystyle S_{i}}$ از آن‌ها می‌خواند و مجموعه خانه‌هایی از حافظه که ${\displaystyle S_{i}}$ در آن‌ها می‌نویسد، تعریف می‌کنیم. در این صورت با برقراری شرط زیر که به شرط Bernstein موسوم است، می‌گوییم ${\displaystyle S_{2}}$ به ${\displaystyle S_{1}}$ وابسته است:

مثالی از انواع وابستگی داده

${\displaystyle [I(S_{1})\ \cap \ O(S_{2})]\ \cup \ [O(S_{1})\ \cap \ I(S_{2})]\ \cup \ [O(S_{1})\ \cap \ O(S_{2})]\ \neq \ \varnothing }$

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

• وابستگی جریان (داده): زمانی که ${\displaystyle [O(S_{1})\ \cap \ I(S_{2})]\ \neq \ \varnothing }$ و ${\displaystyle S_{2}}$ از حافظه مشترک چیزی را پس از نوشتن ${\displaystyle S_{1}}$ می‌خواند.
• پاد وابستگی: زمانی که ${\displaystyle [I(S_{1})\ \cap \ O(S_{2})]\ \neq \ \varnothing }$ و ${\displaystyle S_{2}}$ حافظه مشترک را پس از خواندن ${\displaystyle S_{1}}$ بازنویسی می‌کند.
• وابستگی خروجی: زمانی که ${\displaystyle [O(S_{1})\ \cap \ O(S_{2})]\ \neq \ \varnothing }$ و ${\displaystyle S_{2}}$ و ${\displaystyle S_{1}}$ هر دو بر روی حافظه مشترک می‌نویسند.

در برخی منابع، نوع چهارمی هم به صورت زیر تعریف می‌شود:

• وابستگی ورودی: زمانی که ${\displaystyle [I(S_{1})\ \cap \ I(S_{2})]\ \neq \ \varnothing }$ و ${\displaystyle S_{2}}$ و ${\displaystyle S_{1}}$ هر دو از حافظه مشترک می‌خوانند.

وابستگی جریان

وابستگی جریان (به انگلیسی: Flow Dependency) که به آن وابستگی داده (به انگلیسی: Data Dependency)، وابستگی صحیح (به انگلیسی: True Dependency) و خواندن بعد از نوشتن (به انگلیسی: (RAW) Read-after-write) نیز گفته می‌شود، هنگامی رخ می‌دهد که یک دستور به نتیجه دستوری قبل از خود وابسته باشد. مثال زیر را با فرض اینکه مقدار x و y از قبل محاسبه شده‌است در نظر بگیرید:

a = x + y;
b = 2 * a;

در این مثال، دستور دوم به دستور اول وابستگی جریان دارد؛ چرا که از مقدار تولیدی در دستور اول استفاده می‌کند. به این ترتیب در این مثال نمی‌توان دستورها اول و دوم را به صورت هم زمان اجرا کرد.

پاد وابستگی

پاد وابستگی (به انگلیسی: Anti-dependency) که به آن نوشتن بعد از خواندن (به انگلیسی: Write-after-read (WAR)) نیز گفته می‌شود، هنگامی رخ می‌دهد که یک دستور به داده‌ای نیاز دارد که در دستور بعدی بازنویسی می‌شود. مثال زیر را با فرض اینکه مقدار x و y و z از قبل محاسبه شده‌است در نظر بگیرید:

a = x + y;
b = 2 * a;
a = z + 1;

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

a2 = x + y;
b = 2 * a2;
a = z + 1;

به ابن ترتیب با تغییر نام متغیر a به متغیر جدید a2 در دستورها پیش از بازنویسی آن، پاد وابستگی میان دستورها دوم و سوم از بین رفته‌است و اکنون اجرای هم‌زمان آن‌ها امکان‌پذیر است.

وابستگی خروجی

وابستگی خروجی (به انگلیسی: Output Dependency) که به آن نوشتن بعد از نوشتن (به انگلیسی: Write-after-write (WAW)) نیز گفته می‌شود، هنگامی رخ می‌دهد که یک متغیر در دو دستور نوشته شود. به بیان دیگر ترتیب اجرای دو دستور تعیین‌کننده مقدار نهایی یک متغیر است. مثال زیر را در نظر بگیرید:

b = 7;
a = 2 * b;
b = 11;

در این مثال دستور سوم به دستور اول وابستگی خروجی دارد. توجه داریم که تغییر ترتیب این دستورها موجب تغییر مقدار نهایی متغیرها خواهد شد. وابستگی خروجی هم مثال دیگری از وابستگی نام است. برای مثال در کد زیر با تغییر نام متغیر b به متغیر b2 در دستورها قبل از بازنویسی آن، وابستگی خروجی مثال قبل برطرف شده‌است:

b2 = 7;
a = 2 * b2;
b = 11;

وابستگی ورودی

وابستگی ورودی (به انگلیسی: Input Dependency) که به آن خواندن بعد از خواندن (به انگلیسی: Read-after-read (RAR)) نیز گفته می‌شود، هنگامی رخ می‌دهد که یک متغیر در دو دستور خوانده شود. مثال زیر را در نظر بگیرید:

b = 7;
a = 2 * b;
c = b;

در این مثال دستور سوم به دستور دوم وابستگی ورودی دارد.

توجه داریم که وابستگی ورودی در عمل مشکلی در اجرای هم‌زمان دستورها ایجاد نمی‌کند. همچنین تغییر ترتیب دستورها نیز قابل انجام است.

به وضوح، وابستگی ورودی نیز نوعی از وابستگی نام است.

وابستگی نام

وابستگی نام (به انگلیسی: Name Dependency) هنگامی رخ می‌دهد که دو دستور از محل یکسانی از حافظه استفاده می‌کنند اما هیچ جریان داده‌ای میان آن‌ها برقرار نیست. در نتیجه در بسیاری از موارد می‌توان با تغییر نام برخی از متغیرها این وابستگی را از بین برد.

از مهم‌ترین انواع وابستگی‌های نام، وابستگی خروجی و پاد وابستگی هستند.

وابستگی کنترل

اگر نتیجه دستور ${\displaystyle S_{1}}$ مشخص‌کننده اجرا و یا عدم اجرای دستور ${\displaystyle S_{2}}$ باشد، آنگاه دستور ${\displaystyle S_{2}}$ به دستور ${\displaystyle S_{1}}$ وابستگی کنترل دارد. مثال زیر را در نظر بگیرید:

if (a == b)
{
    c = 2 * a;
    a = a + b;
}
b = a + b;

در این مثال نتیجه دستور اول مشخص می‌کند که دستورها سه و چهار اجرا می‌شوند یا خیر.

گراف جریان کنترل ساختار شرطی

گراف جریان کنترل

برای بیان کردن و نشان دادن دقیق و راحت وابستگی کنترل، معمولاً از مفهوم گراف جریان کنترل (به انگلیسی: Control flow Graph (CFG)) استفاده می‌شود.

گراف جریان کنترل گرافی جهت‌دار است که مسیرهای مختلفی که اجرای برنامه ممکن است بپیماید را نشان می‌دهد. رأس‌های این گراف را تکه‌های مجزای برنامه تشکیل می‌دهند. در صورتی که امکان انتقال مستقیم از تکه برنامه i به تکه برنامه j وجود داشته‌باشد، یالی از راس i به راس j خواهیم داشت.

منابع

• allsyllabus Computer_Science Advance Computer Architecture course
• Wake Forest University CSC346/646 Data Dependency handouts 2015
• Computer Organization and Architecture
• Colorado State University computer science course CS553Fall06 lecture