بخشی از مقاله
چکیده
یکی از روشهاي افزایش سرعت اجراي برنامهها موازي سازي حلقههاي برنامه می باشد، که معمولا توسط کامپایلر انجام میشود. اگر بین تکرارهاي مختلف وابستگی داده وجود داشته باشد، کامپایلر نمیتواند موازي سازي حلقه را انجام دهد. در این نوع حلقهها یک روش موازي سازي استفاده از روش چند نخی حدسی می باشد. چند نخی حدسی شروع به اجراي موازي تکرارهاي حلقه می کند و در صورتی که وابستگی داده وجود داشته باشد اجراي بعضی از نخ ها مجددا از ابتدا تکرار می شود. به این عملیات درهم کوبیدگی نخ گفته می شود. دراین مقاله روشی براي اجراي موازي نخ ها به روش چند نخی حدسی ارائه شده است که از در هم کوبیدگی نخ ها جلوگیري می کند. بدین صورت که قبل از عملیات چند نخی حدسی ابتدا میزان وابستگی یک نخ به نخ هاي قبلی اش مشخص میشود و در هنگام اجراي عملیات چند نخی حدسی بسته به نتایج مرحله پیش پردازش نخ ها به گونه اي اجرا می شوند که نیازي به در هم کوبیدگی نخها نباشد. نتایج پیاده سازي نشان می دهد که بهبود قابل توجهی در روش چند نخی حدسی بوجود آمده است، مخصوصا زمانیکه تکرار هاي حلقه وابستگی زیادي به هم داشته باشند.
کلمات کلیدي:چند نخی حدسی، جلوگیري از در هم کوبیدگی، ساختار داده دسترسی ، موازي سازي حلقه.
-1 مقدمه
در زمان کامپایل بهینه سازي هاي فراوانی برروي برنامه،قبل از تبدیل به زبان ماشین انجام می شود، یکی از این بهینه سازي ها موازي سازي حلقه ها می باشد. در صورتی که تکرار١ هاي مختلف حلقه به هم وابستگی داده٢ داشته باشند امکان موازي سازي در زمان کامپایل وجود ندارد، هر چند تکرارهاي این حلقه را نیز می توان به صورت موازي اجرا کرد ولی ممکن است در هنگام اجراي موازي تکرارهاي این نوع از حلقه ها به علت وابستگی داده ، تخلف٣ نیز بوجود بیاید. به عبارت دیگرممکن است در اجراي موازي نتایج بعضی از تکرارهاي حلقه اشتباه باشند.عملیات اجراي موازي تکرارهاي مختلف حلقه در نخ٤ هاي مختلف و بررسی درستی عملکرد نخ ها را چند نخی حدسی٥ می گویند.
علت اصلی اینکه این نوع اجرا حدسی نامیده می شود اینست که نتایج حاصل از اجراي نخ ممکن است اشتباه باشند و به ناچار باید نخ را دوباره از ابتدا اجرا کنیم و نتایج اجراي نخ را بلااثر کنیم. بنابراین با استفاده از چند نخی حدسی می توان یک برنامه سریال را مثل یک برنامه موازي اجرا کرد. البته ممکن است در زمان اجراي موازي حلقه هاي برنامه مشکلاتی در زمان اجرا بوجود بیاید که باید برطرف شوند.بعضی از مفاهیمی که در چند نخی حدسی استفاده می شوند به شرح ذیل می باشند. نخ واحد اجرایی است که می تواند به صورت مستقل تعدادي از تکرارهاي حلقه را اجرا کند. تکه٦دسته اي از تکرارهاي حلقه که با هم در یک نخ اجرا می شود، می باشد.
تزاحم٧هنگامی رخ می دهد که دو یا چند نخ به صورتی به یک محل از حافظه دسترسی پیدا می کنند که وابستگی داده بین آنها اتفاق می افتد. در هر زمان اولین نخ فعال غیر حدسی ٨ و سایر نخ ها حدسی٩ می گویند. براي مشخص شدن ترتیب اجراي نخ ها ، هر نخ داراي شماره می باشد و بر اساس شماره نخ ها ، نخ قبل و بعد شان را شناسایی می کنند. عملیات در هم کوبیدگی١٠ براي یک نخ زمانی اتفاق می افتد که نتایج اجراي نخ اشتباه می باشند و در این صورت تمامی تغییرات انجام شده توسط نخ در حافظه برگردانده شود و نخ دوباره از ابتدا شروع به اجرا شود. در صورت بروز واب ستگی داده بین نخ ها ، نخ متخلف ١١ وتمامی نخ هاي بعدي اش باید در هم کوبیده شوند.در زمان اجراي دستورات در هر برنامه سریال ممکن است وابستگی هاي زیر بین دستورات برنامه وجود داشته باشد.
1 خواندن بعد از نوشتن : Read After Write - RAW - این وابستگی وقتی که دستوري به نتیجه دستور قبلی اش وابسته باشد. به عنوان نمونه در شکل 1 ، دستور 2 به نتیجه دستور 1 وابسته می باشد و نیز دستور 3 به نتیجه دستور 2 وابسته می باشد. اگر ترتیب اجراي این دو دستور با هم عوض شود نتیجه نهایی برنامه تغییر می کند.
2. نوشتن بعد از خواندن : Write After Read - WAR - این واب ستگی زمانی اتفاق می افتد که د ستوري مقدار متغییري را می خواند که بعدا بروزرسانی می شود. به عنوان مثال در شکل1دستور 3 به دستور 2 این نوع وابستگی را دارد.
3.نوشتن بعد از نوشتن : Write After Write - WAW - در حالتی که دو دستور برروي یک متغییر عملیات نوشتن را انجام می دهند. به عنوان مثال در شکل 1 دستور 3 به دستور 1 این نوع وابستگی را دارد.
همه این سه نوع وابستگی در چند نخی حدسی مورد بررسی قرار می گیرند و در صورتی بین نخ ها هر یک از این انواع وابستگی داده وجود داشته باشد ممکن است باعث در هم کوبیدن نخ وابسته شود.عملیات هاي اصلی که براي موازي سازي با چند نخی حدسی لازم است عبارتند از
1. تشخیص داده هایی که می توانند به صورت غیر امن - توسط چندین نخ - مورد دسترسی قرار بگیرند. به این داده ها ، داده هاي حدسی می گوییم.
2.نگهداري اطلاعات دسترسی به داده ها
3.زمانبندي نخ هاي حدسی
4.ذخیره سازي داده هاي حدسی براي هر نخ و اعمال این داده ها به حافظه اصلی در زمان مناسب
5.تشخیص وابستگی داده ها و انجام عملیات در هم کوبیدن در صورت نیاز
تمامی داده هایی که بصورت بالقوه توسط یک نخ قبل از تغییر توسط همان نخ می تواند استفاده شود، به عنوان داده هاي حدسی علامت گذاري می شوند. براي داده هاي حدسی نیاز به نگهداري چندین نسخه از داده - براي هر نخ یک نسخه - و استفاده از قفل براي دسترسی به داده - به منظور جلوگیري از - RAW می باشد. بعد از شناسایی داده هاي حدسی کامپایلر باید تمامی عملیات هاي ذخیره و بازیابی آنها را شناسایی کرده و با عملیات مخصوصی١٢ به منظور ذخیره سازي اطلاعات دسترسی١٣ جایگزین کند.براي نگهداري نسخه هاي داده هاي حدسی و نیز دنبال کردن وابستگی داده ها ، ساختار داده مخصوصی براي هر داده نیاز می باشد.
ساختار داده براي هر نخ تکرار می شودکه به آنها version copy گفته می شود. در هنگامی که نخ ها در حال اجراي دستورات هستند، نسخه هاي متفاوتی از داده ها ایجاد می شود و در version copy ذخیره می شود.براي دنبال کردن دسترسی به داده هاي حدسی ساختار دادهاي به نام ساختار دسترسی١٤ وجود دارد که این ساختار نیز براي هر نخ تکرار می شود. در این ساختار براي هر داده و هر نخ یکی از حالت هاي زیر وجود دارد:
بدون دسترسی : - not accessed - نخ به داده دسترسی نداشته است.
تغییریافته : - modified - نخ داده را تغییر داده است.
بارگذاري شده : - exposed load - نخ داده را خوانده است و قبلا بر روي این داده ذخیره سازي نداشته است. این بارگذاري می تواند مثل RAW را ایجاد کند.
بارگذاري شده و تغییر یافته - exposed load and later : - modified اگر بعد از حالت بارگذاري شده، ذخیره سازي داشته باشیم.بخشی از ساختار داده پیشنهادي در[1] براي ذخیره سازي وضعیت دستریسی در شکل 2 آورده است. در این ساختار داده ماتریسی بنام AM براي نگهداري و ضعیت د ستر سی وجود دارد که ماتریس MxW می باشد. M مشخص کننده تعداد داده هاي حدسی که در حلقه وجود دارد و W تعداد نخ ها می باشد. در هر خانه از این ماتریس وضعیت دسترسی یک نخ به یکی از داده ها ذخیره می باشد که می تواند یکی از 4 حالت توضیح داده شده در پاراگراف قبل باشد.
-2 کارهاي مرتبط
با توجه به اینکه مسئله بهینه سازي و افزایش سرعت اجراي برنامه در زمان کامپایل، یک مسئله قدیمی است روشهاي مختلفی در این زمینه ارائه شده اند.3]،[2در خصوص چند نخی حدسی نیز تحقیقات فراوانی انجام شده اند. 10]،9،6، 5،[4 این تحقیقات در دو شاخه پیاده سازي سخت افزاري و نرم افزاي انجام شده اند. در سال 2005 سینترا و همکارانش [1] یک روش جامع براي پیاده سازي نرم افزاري چند نخی حدسی با جزئیات نسبتا کاملی ارائه داده اند و این مقاله به شدت توسط پژوهشگران مورد استقبال قرار گرفته است و ارجاعات زیادي به مقاله آنها داده شده است و نیز توسعه هاي مختلفی بر روش آنها بوجود آمده است.
در این مقاله نیز از روش و ساختار داده ارائه شده در مقاله سینتر استفاده شده است که توضیحات کاملتر در بخش قبلی آورده شده است.در [7] دو روش مدیریت نسخه هاي eager و lazy را با هم مقای سه کرده ا ست و نیز یک ساختار داده ب سیار مخت صر براي ذخیره سازي دسترسی ها به حافظه ارائه شده است. در [8] روشهاي مختلف جایگزین در هم کوبیدگی نخ ها بررسی شده است و روشهاي در هم کوبیدگی نخ ها را به دو دسته inclusive و exclusive تقسیم کرده اند و راه حلی براي پیاده سازي در هم کوبیده exclusive پیشنهاد شده است و ضمنا در این مقاله ساختار داده پیشنهادي سینترا استفاده شده است و در آن تغییراتی ایجاد شده است.
-3 روش پیشنهادي
با توجه به نحوه اجراي تکرارهاي حلقه در روش چند نخی حد سی امکان در هم کوبیدگی هر یک از نخ ها وجود دارد که این مسئله باعث کاهش سرعت زیادي می شود. براي جلوگیري از در هم کوبیدگی نخ می توان، بهنحوي نخ ها را اجرا کرد که همواره از درهم کوبیدگی نخ ها اجتناب کرد. براي این منظور یک نقشه ترتیب اجراي نخ ها ایجاد می شود، به این صورت که وابستگی هاي داده یک نخ با نخ هاي قبلی اش، قبل از اجراي نخ شناسایی می شوند ودریک ساختار داده ذخیره می شود. با استفاده از این ساختار داده نحوه وابستگی نخ ها به یکدیگر مشخص و بر همین اساس نخ ها بنحوي اجرا می شوند که قبل از اجرا تمامی داده هاي مورد نیازشان آماده باشد و در نتیجه هیچ گاه نیاز به در هم کوبیدن نخ نخواهد بود.
