عملگرهای جبری خطی برای اجرای الگوریتم های عددی توسط GPU
چکیده
در این کار، تاکید بر توسعه استراتژی‌هایی جهت درک تکنیک‌های مربوط به محاسبات عددی تراشه گرافیک است. به طور ویژه، تمرکز ما در شتاب بخشی به تکنیک‌های حل معادلات جبری حاکم بر شبیه‌سازی‌های عددی است. ما یک چارچوب و طرح کلی جهت اجرای عملگرهای جبری خطی بر پردازنده‌های گرافیکی قابل برنامه‌نویسی (یا GPU ها) معرفی می‌کنیم، لذا پایه‌ی طراحی الگوریتم‌های عددی پیچیده‌تر فراهم خواهد شد. به خصوص، ما یک مدل دنباله‌ای (stream) برای عملیات حسابی بردارها و ماتریس‌هایی که در GPUهای مدرن از موازی‌سازی درونی و ارتباطات کارآمد استفاده می‌کنند، پیشنهاد خواهیم داد. بعلاوه، به خاطر محاسبات عددیِ بهبود یافته، کارایی خوبی به دست می‌آید و الگوریتم‌های گرافیک از این مدل سود می‌برند چرا که از انتقال نتایج محاسباتی به پردازنده گرافیکی نمایش، پرهیز می‌گردد. ما کارایی و اثربخشی روش خود را با به کارگیری حلگرهای مستقیم برای ماتریس‌های اسپارس، و نیز با اعمال این حلگرها در معادلات تفاضل محدود چند بعدی (معادله موج دوبعدی و معادلات ناویر-استوکس تراکم‌ناپذیر)، نشان خواهیم داد. سا
1. مقدمه
توسعه تکنیک های عددی برای حل معادلات دیفرانسیل با مشتقات جزئی، یکی از موضوعات قدیمی در ریاضیات کاربردی است. این تکنیک‌ها دارای کاربردهای وسیعی در شبیه‌سازی‌ها و مدلسازی‌های فیزیکی هستند و به دفعات در گرافیک کامپیوتر مورد استفاده قرار گرفته اند به طوری که بتوان پدیده‌های طبیعی را به صورت دقیقی شبیه سازی نمود [کاس و میلر 1990؛ چن و دا ویتوریا لوبو 1995؛ فاستر و متاکزاس 1996؛ استام 1999؛ فاستر و فدکیو 2001؛ فدکیو و همکاران 2001]. این تکنیک‌ها با وجود کاربردشان در شبیه سازی عددی، در موارد بسیاری از محیط‌های گرافیک کامپیوتری، اعمال شده‌اند؛ مثلا برای ذکر چند مورد از کارهای انجام شده در این زمینه می‌توان به این موارد اشاره کرد: شبیه سازی ترسیم‌های رنگین کمانی [دسبرون و همکاران 1999]، یا متحرک سازی مدل‌های تغییرشکل پذیر [باراف و ویتکین 1998؛ دبان و همکاران 2001].
Abstract
In this work, the emphasis is on the development of strategies to realize techniques of numerical computing on the graphics chip. In particular, the focus is on the acceleration of techniques for solving sets of algebraic equations as they occur in numerical simulation. We introduce a framework for the implementation of linear algebra operators on programmable graphics processors (GPUs), thus providing the building blocks for the design of more complex numerical algorithms. In particular, we propose a stream model for arithmetic operations on vectors and matrices that exploits the intrinsic parallelism and efficient communication on modern GPUs. Besides performance gains due to improved numerical computations, graphics algorithms benefit from this model in that the transfer of computation results to the graphics processor for display is avoided. We demonstrate the effectiveness of our approach by implementing direct solvers for sparse matrices, and by applying these solvers to multi-dimensional finite difference equations, i.e. the 2D wave equation and the incompressible Navier-Stokes equations.
1 Introduction
The development of numerical techniques for solving partial differential equations is one of the traditional subjects in applied mathe- matics. These techniques have a variety of applications in physics based simulation and modelling, and they have been frequently employed in computer graphics to provide realistic simulation of real-world phenomena [Kaas and Miller 1990; Chen and da Vitoria Lobo 1995; Foster and Metaxas 1996; Stam 1999; Foster and Fedkiw 2001; Fedkiw et al. 2001]. Despite their use in numerical simulation, these techniques have also been applied in a variety of computer graphics settings, e.g. the simulation of watercolor drawings [Curtis et al. 1997], the processing of polygonal meshes [Desbrun et al. 1999], or the animation of deformable models [Baraff and Witkin 1998; Debunne et al. 2001], to mention just a few.
چکیده
1. مقدمه
2. معرفی ماتریس به GPU ها
3. چهار عمل اصلی
3.1. عملیات حسابی بردار
3.2. حاصلضرب ماتریس-بردار
3.3. کاهش بردار
4. ماتریس‌های اسپارس
4.1. ماتریس‌های نواری
4.2. ماتریس‌های اسپارس با توزیع تصادفی
5. مثال‌ها
5.1. روش گرادیان همیوغ
5.2. حلگر گاوس-سایدل
6. بحث و ارزیابی عملکرد
7. جمع‌بندی
Abstract
1 Introduction
2 Matrix Representation on GPUs
3 Basic Operations
3.1 Vector Arithmetic
3.2 Matrix-Vector Product
3.3 Vector Reduce
4 Sparse Matrices
4.1 Banded Matrices
4.2 Sparse Random Matrices
5 Examples
5.1 Conjugate Gradient Method
5.2 Gauss-Seidel Solver
6 Discussion and Performance Evaluation
7 Conclusion
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه