Abstract
Analysis of opportunities and approaches to parallel implementation of the Yen's algorithm is done and the expediency of such implementation using video adapters is argue. A parallel implementation of the Yen's algorithm with realization of developed method of templates and parallelization of basic Dijkstra's algorithm using hardware-software platform CUDA is created. Acceleration of work of parallel algorithm in comparison with serial algorithm is received
چکیده
در این مقاله، فرصت‌ها و روش‌هایی به‌منظور پیاده‌سازی الگوریتم Yen مورد تحلیل قرارگرفته است و همچنین سودمندی چنین پیاده‌سازی‌هایی با استفاده از آداپتورهای ویدئویی موردبررسی قرارگرفته است. با بکار گیری متد توسعه‌یافته‌ای از الگوها و موازی سازی الگوریتم اولیه‌ی دایجسترا به‌وسیله‌ی پلت فرم نرم افزار-سخت‌افزار کودا ، یک شکل موازی از الگوریتم Yen نیز پیاده‌سازی شده است. نتایج حاصله نیز حاکی از برتری سرعت این الگوریتم موازی در مقایسه با الگوریتم سریال بوده است.
1-مقدمه
راه‌حل‌های مرسومی و رایجی که برای مسئله‌ی یافتن کوتاه‌ترین مسیر در نظریه‌ی گراف وجود دارد، به ما اجازه داده تا بتوانیم مسیری را در بین یک جفت از گرافی که به شکل رأس مشخص‌شده است، به دست آوریم[1].یک سری مسائلی وجود داشته که انتخاب‌های واقعی برای آنها می‌تواند روش‌هایی بهینه‌تری را برای وضع معیارها به وسیله ی مجموعه ای از همه ی مسیرهای موجود به همراه داشته باشد…