محتوای CD ، از جمله نسخه ی نمایشی و محتوا ، در وب و برای بارگیری در دسترس است.

همچنین می توانید برای دریافت اعلان های مطالب جدید در سایت ، در فید اخبار توسعه دهنده ما مشترک شوید.

فصل 39. پیشوند موازی (اسکن) با CUDA

شرکت مارک هریس نویدیا

دانشگاه Shubhabrata Sengupta در کالیفرنیا ، دیویس

جان دی اوونز دانشگاه کالیفرنیا ، دیویس

39. 1 مقدمه

یک بلوک ساختمان الگوریتم موازی ساده و متداول ، عملکرد All-Prefix-Sums است. در این فصل ، ما عملیات را تعریف و نشان می دهیم ، و به طور مفصل اجرای کارآمد آن با استفاده از Nvidia cuda را مورد بحث قرار می دهیم. بللوچ (1990) همه پیش فرض را به عنوان نمونه خوبی از محاسباتی توصیف می کند که به نظر می رسد ذاتاً پی در پی است ، اما یک الگوریتم موازی کارآمد وجود دارد. او عملکرد All-Prefix-Sums را به شرح زیر تعریف می کند:

عملیات All-Prefix یک اپراتور انجمنی باینری با هویت I و مجموعه ای از عناصر N می گیرد

[ آ0، آ1بشرآn 1],

و آرایه را برمی گرداند

[من ، الف0، ( آ0آ1).( آ0آ1بشرآn 2)]

به عنوان مثال ، اگر علاوه بر

[3 1 7 0 4 1 6 3]

[0 3 4 11 11 15 16 22].

عملکرد All-Prefix در مجموعه ای از داده ها معمولاً به عنوان اسکن شناخته می شود. ما از این اصطلاحات ساده تر (که از زبان برنامه نویسی APL [Iverson 1962]) برای باقیمانده این فصل استفاده می کنیم. اسکن فقط تعریف شده یک اسکن اختصاصی است ، زیرا هر عنصر j از نتیجه جمع همه عناصر تا اما از جمله J در آرایه ورودی است. در یک اسکن فراگیر ، تمام عناصر از جمله J خلاصه می شوند. با تغییر آرایه حاصل درست توسط یک عنصر و درج هویت ، می توان یک اسکن منحصر به فرد از یک اسکن فراگیر ایجاد کرد. به همین ترتیب ، اسکن فراگیر با تغییر آرایه حاصل از سمت چپ و درج در انتها جمع آخرین عنصر اسکن و آخرین عنصر آرایه ورودی می تواند از یک اسکن منحصر به فرد ایجاد شود (بللوچ 1990). برای باقیمانده این فصل ، ما بر اجرای اسکن اختصاصی تمرکز می کنیم و از آن به عنوان "اسکن" یاد می کنیم ، مگر اینکه به طور دیگری مشخص شده باشد.

کاربردهای زیادی برای اسکن وجود دارد ، از جمله ، اما محدود به مرتب سازی ، تجزیه و تحلیل واژگانی ، مقایسه رشته ، ارزیابی چند جمله ای ، تراکم جریان و ساخت و سازه های ساختمان و ساختار داده (نمودارها ، درختان و غیره) به طور موازی. به عنوان مثال برنامه های کاربردی ، ما خواننده را به نظرسنجی توسط Blelloch (1990) ارجاع می دهیم. در این فصل ، ما جداول منطقه خلاصه (برای فیلتر تصویر با عرض متغیر) ، تراکم جریان و مرتب سازی رادیکس را پوشش می دهیم.

به طور کلی ، All-Prefix-Sums می تواند برای تبدیل برخی از محاسبات پی در پی به محاسبات معادل اما موازی ، همانطور که در شکل 39-1 نشان داده شده است ، استفاده شود.

جدول 39-1. یک محاسبه متوالی و معادل موازی آن

39. 1. 1 اسکن متوالی و کارآیی کار

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

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

39. 2 اجرای

الگوریتم اسکن پی در پی برای GPU مناسب است زیرا از موازی بودن داده های GPU استفاده نمی کند. ما می خواهیم یک نسخه موازی از اسکن پیدا کنیم که می تواند از پردازنده های موازی یک GPU برای سرعت بخشیدن به محاسبه آن استفاده کند. در این بخش ما از طریق اجرای CUDA یک الگوریتم اسکن موازی کار می کنیم. ما با معرفی یک اجرای ساده اما ناکارآمد شروع می کنیم و سپس پیشرفت هایی را در الگوریتم و اجرای در CUDA ارائه می دهیم.

39. 2. 1 اسکن موازی ساده لوح

شبه کد در الگوریتم 1 اولین تلاش برای اسکن موازی را نشان می دهد. این الگوریتم بر اساس الگوریتم اسکن ارائه شده توسط هلیس و استیل (1986) ساخته شده و برای GPU ها توسط هورن (2005) نشان داده شده است. شکل 39-2 عملکرد را نشان می دهد. اگر پیچیدگی کار آن را بررسی کنیم ، مشکل الگوریتم 1 آشکار است. این الگوریتم O (N log را انجام می دهد₂n) عملیات اضافی. به یاد داشته باشید که یک اسکن متوالی O (n) را اضافه می کند. بنابراین ، این اجرای ساده لوحانه کارآمد نیست. عامل ورود به سیستم₂n می تواند تأثیر زیادی در عملکرد داشته باشد.

شکل 39-2 اسکن ساده لوح

مثال 1. یک الگوریتم اسکن جمع که کارآمد نیست

1: برای ورود به d = 1₂n انجام 2: برای همه k به صورت موازی 3: اگر k 2 d پس از آن 4: x [k] = x [ k-2 d-1] + x [k]

الگوریتم 1 فرض می کند که به اندازه عناصر داده پردازنده های زیادی وجود دارد. برای آرایه های بزرگ روی یک GPU که در حال اجرا است ، معمولاً اینگونه نیست. در عوض ، برنامه نویس باید محاسبات را بین تعدادی از بلوک های نخ که هر یک بخشی از آرایه را بر روی یک چند پردازنده واحد GPU اسکن می کند ، تقسیم کند. حتی هنوز هم ، تعداد پردازنده ها در یک چند پردازنده به طور معمول بسیار کوچکتر از تعداد موضوعات در هر بلوک است ، بنابراین سخت افزار به طور خودکار عبارت "برای همه" را به دسته های موازی کوچک (به نام Warps) تقسیم می کند که به طور متوالی روی چند تولید کننده اجرا می شوند. یک پردازنده گرافیکی سری NVIDIA 8 به صورت موازی 32 موضوع را اجرا می کند. از آنجا که همه موضوعات به طور همزمان برای آرایه های بزرگتر از اندازه Warp اجرا نمی شوند ، الگوریتم 1 کار نخواهد کرد ، زیرا اسکن را در محل انجام می دهد. نتایج یک پیچ و تاب توسط موضوعات موجود در Warp دیگر بازنویسی می شود.

برای حل این مشکل ، ما باید آرایه ای را که با استفاده از دو آرایه موقت اسکن می کنیم ، دو بار بافک کنیم. شبه کد برای این در الگوریتم 2 آورده شده است و کد CUDA C برای اسکن ساده لوح در لیست 39-1 آورده شده است. توجه داشته باشید که این کد فقط روی یک بلوک نخ واحد از GPU اجرا می شود ، بنابراین اندازه آرایه هایی که می تواند پردازش کند محدود است (به 512 عنصر در GPU های سری NVIDIA 8). گسترش اسکن به آرایه های بزرگ در بخش 39. 2. 4 بحث شده است.

مثال 2. یک نسخه دو بافر از اسکن جمع از الگوریتم 1

1: برای ورود به d = 1₂n انجام 2: برای همه k به صورت موازی 3: اگر k 2 d پس از آن 4: x [out] [k] = x [in] [ k-2 d-1] + x [in] [k] 5: other6: x [out] [k] = x [in] [k]

مثال 39-1. کد CUDA C برای الگوریتم اسکن ساده لوح

این نسخه می تواند آرایه هایی را به همان اندازه که می تواند توسط یک بلوک نخ واحد که روی یک چند پردازنده یک GPU اجرا می شود ، کنترل کند.

39. 2. 2 اسکن موازی کارآمد

اجرای اسکن ما از بخش 39. 2. 1 به دلیل عدم کارآیی آن ، احتمالاً در آرایه های بزرگ بسیار بد عمل می کند. ما می خواهیم یک الگوریتم پیدا کنیم که به کارآیی الگوریتم پی در پی نزدیک شود ، در حالی که هنوز از موازی بودن در GPU استفاده می کند. هدف ما در این بخش تهیه یک الگوریتم اسکن کارآمد برای CUDA است که از عامل اضافی ورود به سیستم جلوگیری می کند₂n کار انجام شده توسط الگوریتم ساده لوح. این الگوریتم براساس نمونه ارائه شده توسط بللوچ (1990) است. برای انجام این کار از الگوی الگوریتمی استفاده خواهیم کرد که اغلب در محاسبات موازی بوجود می آید: درختان متعادل. ایده این است که یک درخت باینری متعادل را روی داده های ورودی بسازید و آن را از ریشه و از ریشه برای محاسبه مبلغ پیشوند استفاده کنید. یک درخت باینری با برگ n دارای d = log است₂سطح N و هر سطح D دارای 2 گره D است. اگر در هر گره یک اضافه کنیم ، سپس O (n) را بر روی یک گذرگاه واحد از درخت اضافه می کنیم.

درختی که ما می سازیم یک ساختار داده واقعی نیست ، بلکه مفهومی است که ما از آن استفاده می کنیم تا آنچه را که هر موضوع در هر مرحله از مسیر انجام می دهد ، تعیین کنیم. در این الگوریتم اسکن کارآمد کار ، ما عملیات را در یک آرایه در حافظه مشترک انجام می دهیم. این الگوریتم از دو مرحله تشکیل شده است: فاز کاهش (همچنین به عنوان فاز-سوپ نیز شناخته می شود) و مرحله پایین سوپ. در مرحله کاهش ، ما درخت را از برگها به محاسبات ریشه در گره های داخلی درخت عبور می کنیم ، همانطور که در شکل 39-3 نشان داده شده است. این همچنین به عنوان یک کاهش موازی شناخته می شود ، زیرا پس از این مرحله ، گره ریشه (آخرین گره در آرایه) جمع همه گره ها را در آرایه نگه می دارد. شبه کد برای مرحله کاهش در الگوریتم 3 آورده شده است.

شکل 39-3 نمونه ای از الگوریتم اسکن جمع کار با کارآیی بالا یا کاهش

مثال 3. مرحله Up-Sweep (کاهش) یک الگوریتم اسکن SUM با کارآیی کار (After Blelloch 1990)

1: برای ورود به d = 0₂n - 1 do 2: برای همه k = 0 تا n - 1 توسط 2 d +1 به صورت موازی 3: x [k + 2 d +1 - 1] = x [k + 2 d - 1] + x [k+ 2 D +1 - 1]

در مرحله پایین ، ما با استفاده از مبالغ جزئی از مرحله کاهش برای ساخت اسکن در آرایه ، از ریشه از ریشه عبور می کنیم. ما با قرار دادن صفر در ریشه درخت شروع می کنیم و در هر مرحله ، هر گره در سطح فعلی ارزش خود را به فرزند چپ خود منتقل می کند ، و مجموع ارزش آن و ارزش قبلی فرزند چپ خود را به فرزند راست خود می رساندبشردر شکل 39-4 نشان داده شده است و شبه کد در الگوریتم 4 آورده شده است. کد CUDA C برای الگوریتم کامل در لیست 39-2 آورده شده است. مانند کد اسکن ساده لوح در بخش 39. 2. 1 ، کد موجود در لیست 39-2 فقط روی یک بلوک موضوع واحد اجرا می شود. از آنجا که این دو عنصر را در هر موضوع پردازش می کند ، حداکثر اندازه آرایه این کد می تواند 1،024 عنصر در پردازنده گرافیکی سری NVIDIA 8 باشد. اسکن آرایه های بزرگتر در بخش 39. 2. 4 مورد بحث قرار گرفته است.

شکل 39-4 نمونه ای از مرحله پایین سوپت از الگوریتم اسکن موازی کارآمد کار-کارآمد

مثال 4. مرحله پایین یک الگوریتم اسکن موازی با کارآیی کارآمد (پس از بللوچ 1990)

الگوریتم اسکن در الگوریتم 4 عملیات O (N) را انجام می دهد (2 x (n - 1) را اضافه می کند و مبادلات n - 1 را اضافه می کند). بنابراین کارآمد کار است و برای آرایه های بزرگ ، باید بسیار بهتر از الگوریتم ساده لوح از بخش قبلی عمل کند. راندمان الگوریتمی کافی نیست. ما همچنین باید از سخت افزار کارآمد استفاده کنیم. اگر عملکرد این اسکن را در یک GPU در حال اجرا CUDA بررسی کنیم ، خواهیم فهمید که از بسیاری از درگیری های مشترک بانک حافظه رنج می برد. اینها به عملکرد هر دسترسی به حافظه مشترک آسیب می رساند و به طور قابل توجهی بر عملکرد کلی تأثیر می گذارد. در بخش بعدی ، ما به برخی از اصلاحات ساده می پردازیم که می توانیم در محاسبات آدرس حافظه ایجاد کنیم تا بخش اعظم آن عملکرد از دست رفته را بازیابی کنیم.

مثال 39-2. کد CUDA C برای اسکن کل کارآیی الگوریتم های 3 و 4.

بلوک های برجسته در بخش 39. 2. 3 بحث شده است.

آ

شرح

جف

د

اشمیه

39. 2. 3 اجتناب از درگیری های بانکی

الگوریتم اسکن بخش قبلی تقریباً به اندازه یک الگوریتم متوالی بهینه انجام می شود. با وجود این کارآیی کار ، به دلیل الگوهای دسترسی به حافظه ، در سخت افزار GPU NVIDIA هنوز کارآمد نیست. همانطور که در راهنمای برنامه نویسی NVIDIA CUDA (NVIDIA 2007) توضیح داده شده است ، حافظه مشترک مورد بهره برداری توسط این الگوریتم اسکن از چندین بانک تشکیل شده است. هنگامی که چندین موضوع در همان WARP به همان بانک دسترسی پیدا می کنند ، یک درگیری بانکی رخ می دهد مگر اینکه همه موضوعات WARP به همان آدرس 32 بیتی دسترسی پیدا کنند. تعداد موضوعاتی که به یک بانک واحد دسترسی پیدا می کنند ، درجه درگیری بانکی نامیده می شود. درگیری های بانکی باعث سریال سازی دسترسی های متعدد به بانک حافظه می شود ، به طوری که دسترسی مشترک به حافظه با یک درگیری بانکی مدرک N نیاز به تعداد بسیاری از چرخه ها برای پردازش به عنوان دسترسی بدون درگیری دارد. در GPU های سری NVIDIA 8 ، که 16 موضوع را به صورت موازی در نیمه تمامپ اجرا می کنند ، بدترین حالت درگیری با درجه 16 است.

الگوریتم های درختی باینری مانند اسکن کارآمد کار ما دو برابر بین دسترسی حافظه در هر سطح از درخت ، همزمان تعداد موضوعاتی را که به همان بانک دسترسی دارند دو برابر می کند. برای درختان عمیق ، با نزدیک شدن به سطح میانی درخت ، میزان درگیری های بانکی افزایش می یابد و سپس دوباره در نزدیکی ریشه کاهش می یابد ، جایی که تعداد نخ های فعال کاهش می یابد (به دلیلifبیانیه در لیست 39-2). به عنوان مثال ، اگر ما در حال اسکن یک آرایه 512 عنصر هستیم ، حافظه مشترک در حلقه های داخلی لیست 39-2 تجربه حداکثر درگیری های بانکی 16 طرفه می خواند و می نویسد. این تأثیر قابل توجهی در عملکرد دارد.

در صورت مراقبت در هنگام دسترسی ، در بیشتر محاسبات CUDA درگیری های بانکی قابل اجتناب است__shared__آرایه های حافظهما می توانیم با اضافه کردن مقدار متغیر بالشتک به هر شاخص آرایه حافظه مشترک که محاسبه می کنیم ، از بیشتر درگیری های بانکی در اسکن جلوگیری کنیم. به طور خاص ، ما مقدار شاخص تقسیم شده بر تعداد بانکهای حافظه مشترک را به شاخص اضافه می کنیم. این در شکل 39-5 نشان داده شده است. ما از کد اسکن کارآمد کار در لیست 39-2 شروع می کنیم و فقط بلوک های برجسته A از طریق E. را اصلاح می کنیم تا تغییرات کد را ساده کنیم ، ما یک کلان را تعریف می کنیمCONTAIL_FREE_OFFSET، در لیست 39-3 نشان داده شده است.

شکل 39-5 بالشتک ساده اعمال شده برای آدرسهای حافظه مشترک می تواند درگیری های بانکی درجه بالا را در طول الگوریتم های مبتنی بر درخت مانند اسکن از بین ببرد

مثال 39-3. کلان مورد استفاده برای محاسبات شاخص های آرایه حافظه مشترک بدون درگیری بانکی

بلوک های A از طریق E در لیست 39-2 برای جلوگیری از درگیری های بانکی باید با استفاده از این کلان اصلاح شوند. برای مسدود کردن A. باید دو تغییر ایجاد شود__ global__آرایهg_idataبه درون__shared__آرایهدمابشردر کد اصلی ، هر موضوع دو عنصر مجاور را بارگیری می کند ، و در نتیجه نمایه سازی بین آرایه حافظه مشترک ، درگیری های بانکی دو طرفه ایجاد می شود. در عوض بارگیری دو عنصر از نیمه های جداگانه آرایه ، ما از این درگیری های بانکی جلوگیری می کنیم. همچنین ، برای جلوگیری از درگیری های بانکی در هنگام عبور از درخت ، ما باید هر یک از آنها را به آرایه حافظه مشترک اضافه کنیمnum_banks(16) عناصر. ما این کار را با استفاده از ماکرو در لیست 39-3 همانطور که در لیست 39-4 نشان داده شده است انجام می دهیم. توجه داشته باشید که ما جبران خسارات را در شاخص های حافظه مشترک ذخیره می کنیم تا بتوانیم در انتهای اسکن دوباره از آنها استفاده کنیم ، هنگام نوشتن نتایج به آرایه خروجیg_odataدر بلوک E.

مثال 39-4. برای جلوگیری از درگیری های مشترک بانک حافظه ، اصلاح در کد اسکن کارآمد

بلوک A:

بلوک های B و D یکسان هستند:

بلوک C:

بلوک E:

39. 2. 4 آرایه ای از اندازه دلخواه

الگوریتم های داده شده در بخش های قبلی یک آرایه را در داخل یک بلوک نخ واحد اسکن می کنند. این برای آرایه های کوچک خوب است ، تا حداکثر حداکثر تعداد نخ در یک بلوک (از آنجا که هر نخ دو عنصر را بارگیری می کند و پردازش می کند). در GPU های سری NVIDIA 8 ، این ما را به حداکثر 1،024 عنصر محدود می کند. همچنین ، اندازه آرایه باید قدرت دو باشد. در این بخش ، ما توضیح می دهیم که چگونه الگوریتم را برای اسکن آرایه های بزرگ ابعاد دلخواه (غیر قدرت دو) گسترش دهیم. این الگوریتم براساس توضیحات ارائه شده توسط Blelloch (1990) است.

ایده اصلی ساده است. ما آرایه های بزرگ را به بلوک هایی تقسیم می کنیم که هرکدام را می توان با یک بلوک نخ واحد اسکن کرد ، و سپس بلوک ها را اسکن می کنیم و کل کل هر بلوک را به یک مجموعه دیگر از بلوک می نویسیم. سپس مبلغ بلوک را اسکن می کنیم و مجموعه ای از افزایش بلوک را ایجاد می کنیم که به همه عناصر موجود در بلوک های مربوطه اضافه می شوند. با جزئیات بیشتر ، بگذارید n تعداد عناصر موجود در آرایه ورودی باشد و B تعداد عناصر پردازش شده در یک بلوک باشد. ما بلوک های نخ N / B را از نخ های B / 2 اختصاص می دهیم.(در اینجا فرض می کنیم که N چند از B است و ما در پاراگراف بعدی به ابعاد دلخواه گسترش می یابیم.) یک انتخاب معمولی برای B در GPU های سری NVIDIA 8 128 است. ما از الگوریتم اسکن بخش های قبلی استفاده می کنیم تا هر بلوک را اسکن کنیممن به طور مستقل ، اسکن های حاصل را در مکان های متوالی آرایه خروجی ذخیره می کنم. ما یک تغییر جزئی در الگوریتم اسکن انجام می دهیم. قبل از صفر آخرین عنصر بلوک I (بلوک کد با برچسب B در لیست 39-2) ، مقدار (مجموع بلوک I) را در یک آرایه کمکی ذخیره می کنیممبالغبشرسپس اسکن می کنیممبالغبه همین روش ، نوشتن نتیجه را به یک آرایه می نویسدinshبشرسپس اضافه می کنیمinc [i]به همه عناصر بلوکiبا استفاده از یک یکنواخت ساده ، هسته ای را که در بلوک های نخ N / B از نخ های B / 2 فراخوانی شده است ، اضافه کنید. این در شکل 39-6 نشان داده شده است. برای جزئیات بیشتر در مورد اجرای ، لطفاً به کد منبع موجود در http://www. gpgpu.org/scan-gpugems3/ مراجعه کنید.

شکل 39-6 الگوریتم برای انجام یک اسکن جمع بر روی یک مجموعه بزرگ از مقادیر

استفاده از ابعاد غیر قدرت دو از دو آسان است. ما به سادگی آرایه را به چند بعدی از اندازه بلوک b می اندازیم. الگوریتم اسکن به عناصر گذشته از انتهای آرایه بستگی ندارد ، بنابراین لازم نیست از یک مورد خاص برای آخرین بلوک استفاده کنیم.

39. 2. 5 نتایج بهینه سازی و عملکرد بیشتر

پس از بهینه سازی دسترسی به حافظه مشترک ، تنگناهای اصلی باقی مانده در کد اسکن ، تأخیر حافظه جهانی و دستورالعمل سربار به دلیل حلقه های حلقه و آدرس محاسبه هستند. برای پوشش بهتر تأخیر در دسترسی به حافظه جهانی و بهبود کارایی کلی ، باید در هر موضوع محاسبات بیشتری انجام دهیم. ما از تکنیکی که توسط دیوید لیچترن پیشنهاد شده است ، استفاده می کنیم ، که به جای دو بار با بارگیری دو ، هشت عنصر در هر موضوع را پردازش می کندfloat4عناصر در هر موضوع به جای دوشناورعناصر (Lichterman 2007). هر نخ یک اسکن متوالی از هر یک را انجام می دهدfloat4، سه عنصر اول هر اسکن را در رجیسترها ذخیره می کند و مبلغ کل را در آرایه حافظه مشترک وارد می کند. با مبالغ جزئی از همه موضوعات موجود در حافظه مشترک ، ما یک اسکن مبتنی بر درخت یکسان را با نمونه ای که در لیست 39-2 ذکر شده است ، انجام می دهیم. سپس هر نخ دو را ساخت می کندfloat4مقادیر با افزودن عنصر اسکن شده مربوطه از حافظه مشترک به هر یک از مبالغ جزئی ذخیره شده در رجیسترها. بالاخره ،float4مقادیر برای حافظه جهانی نوشته شده اند. این رویکرد ، که بیش از دو برابر سریعتر از کد قبلی است ، نتیجه ای از قضیه برنت است و یک روش متداول برای بهبود کارآیی الگوریتم های موازی است (کوین 1994).

برای کاهش حسابداری و آموزش حلقه سربار ، حلقه ها را در الگوریتم های 3 و 4 حل می کنیم. از آنجا که اندازه بلوک ما ثابت است ، می توانیم این حلقه ها را کاملاً از بین ببریم ، و دستورالعمل های اضافی مورد نیاز برای عبور از درخت را در یک حلقه کاهش می دهیم.

تلاش های ما برای ایجاد یک اجرای کارآمد اسکن در CUDA پرداخت شده است. عملکرد تا 20 برابر سریعتر از نسخه پی در پی اسکن که روی یک پردازنده سریع اجرا می شود ، همانطور که در نمودار در شکل 39-7 نشان داده شده است. همچنین ، به لطف مزایای ارائه شده توسط CUDA ، ما از اجرای OpenGL بهینه شده که در همان GPU در همان GPU انجام می شود ، از یک عامل هفت استفاده می کنیم. نمودار همچنین عملکردی را که ما هنگام استفاده از اجرای اسکن ساده لوح از بخش 39. 2. 1 برای هر بلوک به دست می آوریم ، نشان می دهد. از آنجا که هم اسکن ساده لوح و هم اسکن کارآمد کار باید در بلوک های همان تعداد موضوعات تقسیم شود ، عملکرد اسکن ساده لوحانه توسط یک عامل O کندتر است (ورود به سیستم₂ب) ، جایی که b اندازه بلوک است ، نه یک عامل O (log₂n). شکل 39-8 عملکرد بهترین اجرای CUDA ما را با نسخه هایی که فاقد جلوگیری از بانکی و حلقه حلقه هستند مقایسه می کند.

شکل 39-7 عملکرد کارآیی کارآمد ، بدون درگیری بانکی که در CUDA در مقایسه با یک اسکن متوالی اجرا شده در C ++ اجرا شده است ، و اجرای کارآمد کار در OpenGL

شکل 39-8 مقایسه عملکرد اسکن کارآمد کار در CUDA با بهینه سازی برای جلوگیری از درگیری های بانکی و حلقه های حل نشده

اجرای اسکن مورد بحث در این فصل ، همراه با برنامه های مثال ، بصورت آنلاین در http://www. gpgpu.org/scan-gpugems3/ در دسترس است.

39. 2. 6 مزایای CUDA نسبت به اجرای OpenGL

قبل از معرفی CUDA ، چندین محقق با استفاده از API های گرافیکی مانند OpenGL و Direct3D اسکن را انجام دادند (برای اطلاعات بیشتر به بخش 39. 3. 4 مراجعه کنید). برای نشان دادن مزایای CUDA نسبت به این API ها برای محاسبات مانند اسکن ، در این بخش به طور خلاصه اجرای اسکن فراگیر کار با کارآیی OpenGL را از Sengupta و همکاران شرح می دهیم.(2006). اجرای آنها یک الگوریتم ترکیبی است که تعداد قابل توجهی از مراحل کاهش را همانطور که در الگوریتم 5 نشان داده شده است ، انجام می دهد. سپس نسخه دو بافر الگوریتم اسکن جمع را که قبلاً در الگوریتم 2 در نتیجه مرحله کاهش نشان داده شده است ، اجرا می کند. سرانجام همانطور که در الگوریتم 6 نشان داده شده است ، عملکرد پایین را انجام می دهد.

مثال 5. مرحله کاهش الگوریتم اسکن OpenGL

1: برای ورود به d = 1₂n انجام 2: برای همه k = 1 تا n /2 d - 1 به طور موازی انجام 3: a [d] [k] = a [d - 1] [2 k] + a [d - 1] [2 k +1]]

مثال 6. مرحله پایین الگوریتم اسکن OpenGL

1: برای d = log₂ n 1 down to 0 do 2: for all k = 0 to n /2 d 1 in parallel do 3: if i>0 سپس 4: اگر k mod 2 0 سپس 5: a [d] [k] = a [d + 1] [k /2] 6: other 7: a [d] [i] = a [d + 1][k /2 - 1]

محاسبات اسکن OpenGL با استفاده از سایه بان پیکسل و هر یک اجرا می شودآگهی]Array یک بافت دو بعدی در GPU است. نوشتن به این آرایه ها با استفاده از رندر به متن در OpenGL انجام می شود. بنابراین ، هر تکرار حلقه در الگوریتم 5 و الگوریتم 2 نیاز به خواندن از یک بافت و نوشتن به دیگری دارد.

مهمترین مزایای Cuda نسبت به OpenGL حافظه مشترک روی تراشه آن ، عملکرد همگام سازی موضوع و پراکندگی به حافظه است که در معرض سایه های پیکسل OpenGL قرار نمی گیرند. CUDA کار یک اسکن بزرگ را به بسیاری از بلوک ها تقسیم می کند ، و هر بلوک قبل از ارسال هرگونه داده برای حافظه خارج از تراشه ، توسط یک چند پردازنده واحد کاملاً روی تراشه پردازش می شود. در OpenGL ، تمام به روزرسانی های حافظه به روزرسانی های حافظه تراشه هستند. بنابراین ، پهنای باند مورد استفاده در اجرای OpenGL بسیار بیشتر است و بنابراین عملکرد پایین تر است ، همانطور که قبلاً در شکل 39-7 نشان داده شده است.

39. 3 برنامه اسکن

همانطور که در مقدمه توضیح دادیم ، اسکن کاربردهای متنوعی دارد. در این بخش ، ما سه برنامه SCAN را پوشش می دهیم: تراکم جریان ، جداول خلاصه منطقه و مرتب سازی Radix.

39. 3. 1 تراکم جریان

تراکم جریان در انواع برنامه های عمومی با هدف اصلی ، از جمله تشخیص برخورد و فشرده سازی ماتریس پراکنده ، یک ابتدایی مهم است. در حقیقت ، تراکم جریان تمرکز بسیاری از کارهای GPU قبلی در اسکن بود (به بخش 39. 3. 4 مراجعه کنید). تراکم جریان روش اصلی برای تبدیل یک بردار ناهمگن ، با عناصر بسیاری از انواع ، به بردارهای همگن است که در آن هر عنصر دارای یک نوع یکسان است. این امر به ویژه در مورد بردارهایی که برخی از عناصر جالب هستند و عناصر بسیاری جالب نیستند ، مفید است. تراکم جریان یک بردار کوچکتر با تنها عناصر جالب تولید می کند. با استفاده از این بردار کوچکتر ، محاسبات کارآمدتر است ، زیرا ما فقط بر روی عناصر جالب محاسبه می کنیم و بنابراین هزینه های انتقال ، به ویژه بین GPU و CPU ، به طور بالقوه کاهش می یابد.

به طور غیررسمی ، تراکم جریان یک عمل فیلتر است: از یک بردار ورودی ، زیر مجموعه ای از این بردار را انتخاب می کند و بسته بندی می کند که زیر مجموعه را در یک بردار خروجی متراکم قرار می دهد. شکل 39-9 نمونه ای را نشان می دهد. به طور رسمی ، تراکم جریان یک بردار ورودی V می گیرد_iو یک محمول P ، و فقط آن عناصر را در V تولید می کند_iبرای آن P (v_i) درست است ، حفظ سفارش عناصر ورودی. هورن (2005) این عملیات را با جزئیات توصیف می کند.

شکل 39-9 مثال تراکم جریان

تراکم جریان به دو مرحله ، اسکن و پراکندگی نیاز دارد.

1. مرحله اول یک بردار موقت ایجاد می کند که در آن عناصر عبور از محمول روی 1 تنظیم شده و سایر عناصر روی 0 تنظیم می شوند. ما سپس این بردار موقت را اسکن می کنیم. برای هر عنصری که از محمول عبور می کند ، نتیجه اسکن اکنون حاوی آدرس مقصد برای آن عنصر در بردار خروجی است.
2. مرحله دوم عناصر ورودی را با استفاده از آدرس های تولید شده توسط اسکن ، به بردار خروجی پراکنده می کند.

شکل 39-10 این روند را با جزئیات نشان می دهد.

شکل 39-10 اسکن و پراکندگی

GPU هایی که در آن شاخ در سال 2005 تراکم جریان را اجرا کرد ، توانایی پراکندگی ندارد ، بنابراین در عوض شاخ دنباله ای از مراحل جمع آوری را برای تقلید پراکندگی جایگزین کرد. برای جمع و جور کردن عناصر N نیاز به ورود به سیستم مراحل جمع آوری مراحل ، و در حالی که این مراحل می تواند در یک برنامه قطعه اجرا شود ، این عملیات "جستجوی جمع" بسیار گران بود و به عملیات حافظه بیشتری نیاز داشت. علاوه بر این از پراکندگی بومی در GPU های اخیر ، تراکم جریان را به میزان قابل توجهی کارآمدتر می کند. عملکرد آزمون تراکم جریان ما در شکل 39-11 نشان داده شده است.

شکل 39-11 عملکرد تراکم جریان که در CUDA در یک GPU NVIDIA GEFORCE 8800 GTX اجرا شده است

39. 3. 2 جداول منطقه خلاصه

یک جدول خلاصه (SAT) یک جدول دو بعدی است که از یک تصویر ورودی تولید می شود که در آن هر ورودی در جدول جمع کلیه پیکسل ها را بین محل ورود و گوشه سمت چپ پایین تصویر ورودی ذخیره می کند. جداول منطقه خلاصه توسط Crow (1984) معرفی شد ، که نشان داد چگونه می توان از آنها برای انجام فیلترهای جعبه با عرض دلخواه در تصویر ورودی استفاده کرد. قدرت جدول منطقه خلاصه از این واقعیت ناشی می شود که می توان از آن برای انجام فیلترهای عرض های مختلف در هر پیکسل موجود در تصویر در زمان ثابت در هر پیکسل استفاده کرد. هنسلی و همکاران.(2005) استفاده از میزهای خلاصه شده با GPU را برای ارائه تعاملی از بازتاب محیط براق و انکسار نشان داد. اجرای آنها در GPU از یک عملیات اسکن معادل اجرای ساده لوح در بخش 39. 2. 1 استفاده کرد. اجرای کارآمد کار در CUDA به ما امکان می دهد تا عملکرد بالاتری کسب کنیم. در این بخش ما توضیح می دهیم که چگونه جداول منطقه خلاصه می تواند با استفاده از اسکن در CUDA محاسبه شود ، و ما استفاده از آنها را در ارائه عمق تقریبی میدان نشان می دهیم.

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

تولید یک پیکسل فیلتر شده با استفاده از یک میز خلاصه ای ، نیاز به نمونه برداری از جدول منطقه خلاصه در چهار گوشه یک منطقه فیلتر مستطیل شکل ، S_ur , s_ul , s_ll , s_lrبشرنتیجه فیلتر شده پس از آن است

جایی که W و H عرض و ارتفاع هسته فیلتر و S است_urنمونه گوشه سمت راست ، s است_llنمونه گوشه سمت چپ پایین و غیره است (کلاغ 1977). ما می توانیم با تغییر مکان چهار نمونه ای که برای محاسبه هر پیکسل خروجی فیلتر شده استفاده می کنیم ، از این تکنیک برای فیلتر با عرض متغیر استفاده کنیم.

شکل 39-12 صحنه ساده ای را نشان می دهد که با عمق تقریبی میدان ارائه شده است ، به طوری که اشیاء به دور از فاصله کانونی مبهم هستند ، در حالی که اشیاء در فاصله کانونی در حال تمرکز هستند. در پاس اول ، ما قوری ها را ارائه می دهیم و با استفاده از تکنیکی که فقط توضیح داده شده است ، یک جدول منطقه خلاصه در Cuda از تصویر ارائه شده تولید می کنیم. در پاس دوم ، ما یک چهار صفحه تمام صفحه را با یک سایه بان ارائه می دهیم که بافر عمق را از پاس اول نمونه می گیرد و از عمق برای محاسبه یک فاکتور تاری که عرضه هسته فیلتر را تعدیل می کند ، استفاده می کند. این مکان مکانهای چهار نمونه گرفته شده از جدول منطقه خلاصه در هر پیکسل را تعیین می کند.

شکل 39-12 عمق تقریبی میدان ارائه شده با استفاده از یک جدول منطقه خلاصه شده برای استفاده از یک مبهم با اندازه متغیر بر اساس عمق هر پیکسل

به جای نوشتن یک الگوریتم اسکن سفارشی برای پردازش تصاویر RGB ، تصمیم گرفتیم از کد موجود خود به همراه چند هسته ساده اضافی استفاده کنیم. محاسبه SAT تصویر ورودی RGB8 به چهار مرحله نیاز دارد. ابتدا تصویر RGB8 را در سه آرایه نقطه شناور جداگانه (یکی برای هر کانال رنگی) قرار می دهیم. بعد همه ردیف های هر آرایه را به صورت موازی اسکن می کنیم. سپس آرایه ها باید منتقل شوند و تمام ردیف ها دوباره اسکن شوند (برای اسکن ستون ها). این در مجموع شش اسکن از عناصر ارتفاع x عرض x است. سرانجام ، سه جداول منطقه خلاصه شده در کانال های RGB از یک تصویر 32 بیتی شناور RGBA در هم آمیخته می شوند. توجه داشته باشید که ما نیازی به انتقال دوباره تصویر نداریم ، زیرا می توانیم مختصات مورد استفاده خود را برای جستجوی آن منتقل کنیم. جدول 39-1 زمان صرف شده برای هر یک از این محاسبات را برای دو اندازه تصویر نشان می دهد.