فرمت فایل: فایل Word ورد 2007 یا 2003 (Docx یا Doc) قابل ویرایش
چکیده
در این مقاله ما نشان می دهیم که الگوریتم ها چطور می توانند در الگوریتم های روان مربوط به برخی مشکلات ترکیبی کلاسیک در مدل W-Stream، موثر و کارآمد باشند. در این مدل، در هر مرحله، یک مسیر ورودی خوانده می شود، یک مسیر خروجی نوشته شده و آیتم های داده باید با استفاده از فضای محدود، پردازش شوند؛ جریان ها با شیوه ای مانند شیوه ای که جریان خروجی در مرحله i با آن پردازش شد، به عنوان جریان ورودی در مرحله i+1 مسیردهی (لوله کشی) می شوند. ما ابتدا یک تکنیک شبیه سازی را معرفی می کنیم که امکان تبدیل الگوریتم های موثر PRAM به الگوریتم های بهینه W-Stream به ازای بسیاری از مشکلات ترکیبی کلاسیک بالاخص گراف نمودن مشکلات را فراهم می نماید، به هرحال این تکنیک، الگوریتم های نسبتاً بهینه ای را به همراه دارد. برای فائق آمدن بر این مشکل، ما مدل محاسباتی Relaxed PRAM RPRAM را به عنوان یک مدل میانی بین PRAM و W-Stream مطرح می کنیم. RPRAM به هر پردازنده امکان می دهد تا به یک تعداد غیر ثابتی از خانه های حافظه در هر دور موازی، حتی به همراه برخی محدودیت ها، دسترسی داشته باشد. مدل RPRAM در حالیکه قدرتمند تر از مدل PRAM می باشد، می تواند در W-Stream درون همان کرانه های مجانب، شبیه سازی شود. قدرت فوق العاده ارائه شده توسط RPRAM در بسیاری موارد به ما امکان می دهد تا تعداد پردازنده ها را به صورت اساسی در حالیکه همان تعداد از دورهای موازی را حفظ می کنیم، کاهش دهیم و این موضوع منجر به موثرتر بودن شبیه سازی های الگوریتم های موازی W-Stram می شود. تکنیک RPRAM ما دیدگاه های جدیدی را در مورد توسعه الگوریتم های جاری ارائه داده و الگوریتم های کارآمدی را برای چندین مشکل کلاسیک در این مدل از جمله مرتب سازی، برقراری اتصال، درخت دارای حداقل پوشایی، دو جزء متصل، و مجموعه مستقل بیشینه، فراهم می نماید. علاوه بر فراهم نمودن امکان مبادلات مسیرهای هموار فضایی، الگوریتم های ما با ارائه کران های پایین مبتنی بر پیچیدگی ارتباط نسبتاً شدید در W-Stream به صورت بهینه برای عوامل چند لگاریتمی نشان داده می شوند.