انجمن کامپیوتر ایران

مساله کوتاه‌ترین مسیر از مسائل بنیادی و پرکاربرد در علم کامپیوتر است. انواع و حالات مختلفی از این مساله وجود دارد که بسیاری از آن‌ها با توجه به کوتاه‌ترین مسیر در گراف‌ها قابل حل هستند. سطوح نامنظم مثلث‌بندی‌شده‌ی (تین) وزن‌دار , در نمایش سرزمین‌ها در سیستم‌های اطلاعات جغرافیایی کاربرد دارند و یافتن کوتاه‌ترین مسیر میان دو نقطه از این سطح به طوری که مسیر از روی تین عبور کند و هزینه آن کمینه شود مورد بررسی ماست. به علت حجم زیاد داده‌ها در تین در کاربردهای واقعی, یافتن کوتاه‌ترین مسیر در زمان قابل‌قبول چندان ساده نیست. در این مقاله با استفاده از پردازش چندهسته‌ای, روشی برای پاسخ‌گویی سریع به پرس‌وجوهای کوتاه‌ترین مسیر میان دو نقطه از تین ارائه می‌دهیم. پردازش چندهسته‌ای حیطه‌ای نوین در پردازش موازی است که پیاده‌سازی برنامه‌های کارا با استفاده از آن متفاوت از سیستم‌های پردازش موازی پیشین است. مقایسه عملکرد روش پیشنهادی با معیارهای موجود برای ارزیابی این مساله و با داده‌های واقعی, کارایی روش را نشان می‌دهد.