ارايه الگوريتم جديد توماس شطرنجي براي حل دستگاه معادلات سه‌قطري روي پردازنده‌گرافيكي

Developing new Checkerboard Thomas algorithm for solving tridiagonal set of equations on GPU

پردازنده گرافيكي همه منظوره كاربر را قادر مي‌سازد تا از پردازنده گرافيكي براي مقاصد محاسباتي عمومي بهره بگيرد. استفاده از اين نوع پردازنده‌ها موجب افزايش قابل توجهي در سرعت محاسبات عددي مي‌شود. تحقيقات متعددي جهت بررسي مزيت استفاده از پردازنده گرافيكي در محاسبات از جمله بكار‌گيري آن براي حل دستگاه معادلات سه‌قطري صورت گرفته است. تمركز اصلي تحقيقات مذكور، روي ارتقا شيوه‌هاي بهره گيري از الگوريتم‌هاي موازي، نظير كاهش متناوب و كاهش متناوب موازي بوده است. اين الگوريتم‌ها با معماري پردازنده گرافيكي سازگارند، با اين وجود پيچيدگي محاسباتي بالايي نسبت به الگوريتم توماس سري دارند و داراي محدوديت‌هايي در خصوص ابعاد دستگاه معادلات مي‌باشند. بنابراين در تحقيق حاضر با توجه به مزاياي الگوريتم توماس نسبت به الگوريتم‌هاي موازي، شيوه‌اي نوين با عنوان توماس شطرنجي جهت سازگار كردن الگوريتم توماس براي اجرا روي پردازنده گرافيكي ارايه شده است. اين روش براي حل مسيله هدايت پاياي دو‌بعدي استفاده شده و نتايج نشان‌دهنده افزايش دقت پاسخ نسبت به دو الگوريتم توماس و كاهش متناوب موازي مي‌باشد. همچنين نتايج حاكي از آن است كه روش جديد مي تواند نسبت به الگوريتم توماس، بين 5.7 تا 22.2 افزايش سرعت محاسباتي را در پي داشته باشد. بعلاوه نتايج نشان‌مي‌دهد كه سرعت اين روش به طور ميانگين در حدود 2 برابر الگوريتم كاهش متناوب موازي مي‌باشد. همچنين مشاهده شد كه دسترسي غير‌هم‌مكان به حافظه سراسري موجب حداقل و حداكثر كاهش سرعت 42.7 و 81.9 درصد به ترتيب براي اندازه شبكه 128×128 و 1024×1024 مي‌شود.

General Purpose Graphics Processing Unite (GPGPU) allows the user to utilize GPU for general computing purposes. Using these processors can cause a great speedup in numerical calculations. Several studies have been performed to investigate the advantages of using the GPGPU in numerical calculations including solving tridiagonal set of equations. The main focus of the mentioned studies was on improving parallel methods, for example, CR and PCR algorithms. Although these algorithms are consistent with GPU architecture, they have higher arithmetic complexity compared with serial Thomas algorithm, they also have limitations in dimensions of the equations’ set. Therefore, in the present study, according to the advantages of Thomas algorithm compared with the parallel algorithms, a novel method entitled checkerboard Thomas has been developed to accommodate Thomas algorithm for running on GPU. This method has been used for solving 2D steady heat conduction problem and the results show an increase in the solution precision compared to Thomas and PCR algorithms. Also, the results indicate that the new algorithm can cause computing to increase in speedup between 5.7 to 22.2x, compared with Thomas algorithm. Furthermore, results show that the new method is about 2x faster than PCR algorithm. It has also been seen that speed decrement for uncoalesced access to global memory is 42.7% minimum and 81.9% maximum for 128×128 and 1024×1024 grid size, respectively.