الگوریتم جاروب موازی برای سیستم های چندهسته ای

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

Keywords:

الگوریتم جاروب , الگوریتم جاروب موازی , جستجو تقاطع , تشخیص تقاطع