الگوریتم فوق موازی برای مثلث بندی درون هسته و برون هسته داده بزرگ در E2 و E3

اختصاصی از فی دوو الگوریتم فوق موازی برای مثلث بندی درون هسته و برون هسته داده بزرگ در E2 و E3 دانلود با لینک مستقیم و پر سرعت .

Volume 51, 2015, Pages 2613–2622
ICCS 2015 International Conference On Computational Science

Highly Parallel Algorithm for Large Data

In–Core and Out–Core Triangulation in E² and E³

Abstract

A triangulation of points in E², or a tetrahedronization of points in E³, is used in many applications. It is not necessary to fulfill the Delaunay criteria in all cases. For large data (more then 5 · 10⁷ points),parallel methods are used for the purpose of decreasingrun–time. A new approach for fast, effective and highly parallel CPU and GPU triangulation, or tetrahedronization, of large data sets in E² or E³ suitable for in–core and out–core memory processing, is proposed. Experimental results proved that the resulting triangulation/tetrahedralization is close to the Delaunay triangulation/tetrahedralization. It also demonstrates the applicability of the methodproposed in applications.

---

Keywords

• Triangulation;
• tetrahedronization;
• parallel computing;
• GPU & CPU;
• large data processing

Procedia Computer Science

الگوریتم فوق موازی برای مثلث بندی درون هسته و برون هسته داده بزرگ در E2 و E3

چکیده

یک مثلث بندی از نقاط در E2، یا یک مستطیل بندی از نقاط در E3 در بسیاری از برنامه ها استفاده می شود. لازم نیست در همه موارد معیار دولونه تحقق یابد. برای داده های بزرگ (بیش از 107×5 نقطه)، به منظور کاهش زمان اجرا روشهای موازی استفاده می شود. رویکردی جدید برای مثلث بندی یا مستطیل بندی CPU و GPU سریع، موثر و فوق موازی از داده بزرگ تنظیم شده در E2 یا E3 برای فرآیند حافظه درون هسته یا برون هسته، پیشنهاد شده است. نتایج عملی ثابت کرده است که مثلث بندی یا مستطیل بندی حاصل نزدیک به مثلث بندی یا مستطیل بندی دولونه است. همچنین قابلیت روش پیشنهادی در برنامه ها را نشان می دهد.

واژگان کلیدی: مثلث بندی، مستطیل بندی ، پردازش موازی، GPU و CPU، پردازش داده­های بزرگ

• مقدمه

برنامه های امروزی نیاز دارند که مجموعه داده های بزرگ را با استفاده از پردازنده های مختلف با حافظه اشتراکی یعنی پردازش موازی، و یا روی سیستم ها با استفاده از پردازش توزیعی، پردازش کنند. در این مقاله ما رویکرد جدید قابل اجرایی برای مثلث بندی سریع و کارآمد در E2 و E3 (مستطیل بندی) با استفاده از سیستم موازی یا توزیعی واحد پردازش مرکزی (CPU) و یا واحد پردازش تصویر (GPU)، یعنی روی خوشه های محاسباتی، برای مجموعه داده های بزرگ را توصیف می کنیم.

الگوریتمهای زیادی برای مثلث بندی در E2 و E3 توسعه یافته اند و با معیارهای مختلف توصیف شده اند [1]، [2]، [5]، [8]؛ اغلب به سبب همزادی با دیاگرامهای وورونوی و خصوصیات ریاضیاتی، مثلث بندی دولونه در E2 استفاده می شود. مثلث بندی دولونه زاویه حداقل را حداکثر می کند؛ در سمت دیگر، زاویه حداکثر را حداقل نمی کند، که در بعضی زمینه ها لازم است، مثل سیستم های CAD و غیره. به علاوه، اگر نقاط یک مش مربع تشکیل دهند، الگوریتمها به دقت عددی محاسبات حساس هستند. به خوبی مشخص شده است که مثلث بندی دولونه (DT) شامل ساده سازی های  است که در آن d بعد دار است. پیچیدگی محاسباتی DT  است یعنی برای 2=d،  است و برای 3=d  می باشد.