بخشی از مقاله
خلاصه
حجم زیادی از دادهها در بسیاری از برنامههای کاربردی نیاز به راهحلهای دادهکاوی مؤثری دارد. خوشبختانه، ظهور فنّاوریهایی مانند محاسبات توری، محاسبات ابری، پردازندههای چندهستهای با عملکرد بالا و واحد پردازش گرافیکی پتانسیل لازم را برای همگام شدن با انفجار دادهها و باز کردن فرصتهای جدیدی برای طراحی الگوریتمهای کارآمد و مؤثر فراهم میکند. اکثر روشهای دادهکاوی فرض میکنند که دادهها میتوانند توسط یک منبع مهیا شوند. اگر دادهها از بسیاری از مکانهای توزیعشده فیزیکی مانند Wal-Mart تولید شده باشند، این روشها نیاز به یک مرکز داده برای جمعآوری دادهها از مکانها توزیعشده نیاز دارند. بعضی مواقع انتقال حجم زیادی داده به یک مرکز داده دارای هزینههای بسیار بالا و حتی غیرعملی است. بنابراین الگوریتمهای دادهکاوی توزیعشده و موازی برای حل این مشکل توسعه داده شدهاند. در این مقاله ما الگوریتمها و برنامههای کاربردی در دادهکاوی توزیعشده با GPU را بررسی میکنیم.
کلمات کلیدی: دادهکاوی، دادهکاوی توزیعشده، سیستمهای توزیعشده، واحد پردازش گرافیکی
.1 مقدمه
مقدار دادههای علمیهر سال تقریباً دو برابر میشود .[1] همگام با این انفجار دادهها به صورت نمایی، یک تلاش بسیار وسیع در بسیاری از جوامع تحقیقاتی مانند علوم زیستی 2] ، [3 شبیهسازی مکانیکی [4] و یا یادگیری ماشین [5] به استفاده از قابلیتهای محاسباتی GPUها حتی برای اهدافی که به گرافیک کامپیوتری ارتباطی ندارد، وجود دارد. حوزه این تحقیقات، پردازش عمومی – واحدهای پردازش گرافیکی نامیده میشود. در این مقاله، ما در بهرهبرداری از قدرت محاسباتی GPUها برای دادهکاوی تمرکز میکنیم. دادهکاوی شامل استفاده از الگوریتمهای تجزیه و تحلیل داده میباشد، که تحت محدودیتهای بهرهوری قابل قبول، تعداد خاصی از الگوها بر روی دادهها را ایجاد کند .[6]
افزایش تصاعدی در دادهها لزوماً باافزایش نسبتاً بزرگ در تولید دانش همراه نیست. حوزه تحقیقاتی در حال تحول دادهکاوی روشهایی پیشنهاد میدهد که انتقال دادههای خام به دانش مقید و ارزشمند را پشتیبانی میکند. دادهکاوی در طیف گستردهای از برنامههای علمی و تجاری نیز کاربرد دارد. به عنوان مثال در علوم اعصاب، نجوم، زیستشناسی، بازاریابی و کشف تقلبمورد استفاده قرار میگیرد. وظایف اساسی دادهکاوی شامل کلاسهبندی، رگرسیون، خوشهبندی، شناسایی دادههای پرت و همچنین اقلام پرتکرار و استخراج قوانین وابستگی میباشد.کل الگوریتمهای دادهکاوی با استفاده از زبان برنامهنویسی CUDA قابل پیادهسازی هستند. فروشندگان سخت-افزارهای گرافیکی روند محاسبات همهمنظوره کلی بر روی GPU و توسعه کتابخانهها، پیش کامپایلرها و واسطهای برنامهنویسی کاربردی را برای پشتیبانی از برنامههای GP-GPU پیشبینی کردهاند.
CUDA یک واسط برنامهنویسی برای زبان برنامهنویسی C ارائه میدهد، که در آن هر دو برنامه میزبان و همچنین عملیات هسته در یک برنامه واحد یکپارچه میشوند. برنامه میزبان، برنامه اصلی است که بر روی CPU اجرا میشود. در مقابل، توابع هسته در یک سبک موازی سنگین بر روی - صدها - پردازنده در GPU اجرا میشوند یک روش مشابه توسط ATI با نامهای تجاری Close-to-Metal، Stream SDK و Brook-GP ارائه شده است. برخی از مقالات روشهایی برای سرعت بخشیدن به عملیات پایگاه داده رابطهای بر روی GPU پیشنهاد دادهاند. در برخی الگوریتمها برای پیوند رابطهای بر روی یک NVIDIA G80 GPU با استفاده از CUDA ارائه شده است. روشهای اخیر در رابطه با دادهکاوی از GPU و زبان برنامهنویسی CUDA استفاده میکند.
.2 معماری GPU
واحد پردازش گرافیکی جدیدترین نسل از کمک پردازندههای قدرتمند میباشد، که نه تنها برای بازیها و دیگر برنامههای با گرافیک بسیار بالا طراحی شده است، بلکه هماکنون برای محاسبات همهمنظوره استفاده میشود. از دیدگاه سختافزاری، یک GPU شامل تعدادی چندپردازنده* میباشد که هرکدام شامل مجموعهای از پردازندههای ساده که در مد SIMD عمل میکنند، میباشد. یعنی تمام پردازندههای یک چندپردازنده در یک مسیر هماهنگ، عملیات ریاضی و منطقی مشابه را در یک زمان بر روی دادههای متفاوت اجرا میکنند.
.1,2 مدل حافظه GPU
به غیر از برخی واحدهای حافظه که با اهداف خاص در زمینه پردازش گرافیکی - برای مثال حافظه الگو - وجود دارد، ما دارای سه نوع مهم حافظه هستیم، همانطوری که در شکل 1 مشاهده میکنید. حافظه مشترک یک واحد حافظه با سرعت دسترسی بالا میباشد - سرعت دسترسی به ثباتها زیاد و بدون تأخیر است - . SM بین تمام پردازندههای یک چندپردازنده به صورت اشتراکی میباشد. SM میتواند برای متغیرهای محلی مورد استفاده قرار گیرد و همچنین برای مبادله اطلاعات بین نخهای پردازندههای متفاوت بر روی یک چندپردازنده استفاده شود؛ و نمیتواند برای اطلاعاتی که در حافظه اشتراکی بین نخها بر روی چندپردازندههای متفاوت هستند، مورد استفاده قرار گیرد.
SM حافظهای سریع اما دارای ظرفیت محدودی است 16 - کیلوبایت در هر چندپردازنده - نوع. دوم حافظه را که اصطلاحاً حافظه ابزار مینامند که در واقع رم ویدئوهای کارت گرافیک هستند - همچنین برای بافرهای فریم استفاده میشوند - . DM از نظر فیزیکی بر روی کارت گرافیک قرار دارد - در داخل GPU قرار ندارد - همچنین دارای ظرفیت بیشتری نسبت به SMها هستند - معمولاً تا چند صد مگابایت - همچنین سرعت پایینتری هم دارند. پهنای باند برای انتقال داده بین DM و GPU در مقایسه با انتقال داده بین CPU و حافظه اصلی بیشتر است. DM میتواند برای به اشتراکگذاری اطلاعات بین نخها روی چندپردازندههای متفاوت مورد استفاده قرار گیرد.
یک الگوی همکاری برای DM و SM کپی کردن اطلاعات مورد نیاز از DM به SM به طور همزمان از نخهای متفاوت است. نوع سوم حافظه که منظور همان حافظه اصلی است بخشی از کارت گرافیک نیست. GPU دسترسی به فضای آدرس CPU ندارد. CPU تنها میتواند با استفاده از توابع API خاص از DM بخواند یا بنویسد. بستههای داده باید از طریق Front Side Bus و PCI-Express Bus منتقل شوند. پهنای باند سیستمهای باس به شدت محدود است، بنابراین این عملیات انتقال خاص بسیار گرانتر از دسترسی مستقیم از GPU به DM و یا دسترسی مستقیم از CPU به حافظه اصلی است.
.2,2 عملیات اتمیک
به منظور همگامسازی و اطمینان از صحت الگوریتمهای موازی، CUDA عملیات اتمیک از قبیل افزایش، کاهش و یا مبادله را پیشنهاد میکند. اکثر عملیات اتمیک بر روی انواع دادههای صحیح در DM کار میکنند. با این حال جدیدترین نسخه CUDA اجازه عملیات اتمیک در SM را نیز فراهم کرده است. بسیاری از عملیات اتمیک بعد از اجرایشان نتایجی را برمیگردانند. برای نمونه عملیات atomicInc دارای دو پارامتر هست، آدرس یک شمارنده که افزایش پیدا میکند و یک مقدار آستانه که عملیات نباید از آن مقدار بیشتر شود. اگر دو یا چندین نخ - از گروه نخهای یکسان یا متفاوت - چندین عملیات اتمیک را به صورت همزمان فراخوانی کنند، نتایج این عملیات یک ترتیب دلخواه از عملیات همزمان هستند. عملیات atomicDec مشابه atomicInc کار میکند. عملیات atomicCAS یک مقایسه و تعویض عملیات را انجام میدهد، دارای سه پارامتر آدرس، مقدار مقایسه و مقدار مبادله است. اگر مقدار در آدرس برابر مقدار مقایسه باشد، مقدار در آدرس جایگزین با مقدار مبادله میشود. در بسیاری موارد، مقدار قدیمی در آدرس قبل از مبادله به روش هسته برگشت داده میشود.
.3 معرفی دادهکاوی توزیعشده
دادهکاوی توزیعشده با این فرض که هم دادهها و هم محاسبات توزیعشده هستند، ایجاد میشود. دادهکاوی توزیع-شده تحت شرایط مختلف، محدودیت ارتباطات، مشکلات حفظ حریم خصوصی و محدودیت منابع از قبیل قدرت محاسباتی دارد. علاوهبراین، دادهکاوی توزیعشده با برنامههایی که دارای الگوریتمهای پیچیده هستند، سروکار دارد.
