دستگاه به رایانه شخصی امکان پردازش نمودارهای عظیم را می دهد

در تفسیر علم داده ، نمودارها ساختارهای گرهها و خطوط اتصال هستند که برای ترسیم نمرات روابط پیچیده داده استفاده می شوند. تجزیه و تحلیل نمودارها برای طیف گسترده ای از برنامه ها ، مانند رتبه بندی صفحات وب ، تجزیه و تحلیل شبکه های اجتماعی برای بینش سیاسی یا ترسیم ساختارهای عصبی در مغز مفید است.

با وجود میلیاردها گره و خط ، با این حال ، نمودارهای بزرگ می توانند به اندازه ترابایت برسند. نمودار داده ها به طور معمول در حافظه گران پویا با دسترسی تصادفی (DRAM) در سراسر سرور تشنه قدرت چند پردازش شده است.

محققان آزمایشگاه علوم کامپیوتر و هوش مصنوعی MIT (CSAIL) اکنون وسیله ای را طراحی کرده اند که از حافظه فلش ارزان قیمت - از نوع مورد استفاده در تلفن های هوشمند - برای پردازش نمودارهای گسترده با استفاده از یک رایانه شخصی منفرد استفاده می کند.

حافظه فلش معمولاً به مراتب کندتر از DRAM در پردازش داده های نمودار است. اما محققان وسیله ای متشکل از یک تراشه فلش تراشه و محاسبه "شتاب دهنده" را طراحی کردند که به دستیابی فلش به عملکرد شبیه به DRAM کمک می کند.

تغذیه دستگاه الگوریتم جدیدی است که کلیه درخواست های دسترسی به داده های گراف را به ترتیب متوالی مرتب می کند که فلش می تواند به سرعت و به راحتی به آن دسترسی پیدا کند. همچنین برخی از درخواست ها را برای کاهش سربار - زمان محاسبات ترکیبی ، حافظه ، پهنای باند و سایر منابع محاسباتی - برای مرتب سازی ادغام می کند.

محققان این دستگاه را در برابر چندین سیستم با کارایی بالا سنتی که چندین نمودار بزرگ را پردازش می کردند ، از جمله عظیم Web Data Commons Hyperlink Graph ، که دارای 3.5 میلیارد گره و 128 میلیارد خط اتصال است ، اداره کردند. برای پردازش این نمودار ، سیستم های سنتی همه به سرور نیاز داشتند که هزاران دلار قیمت دارد و شامل 128 گیگابایت DRAM بود. محققان با وصل کردن دو دستگاه از جمله 1 گیگابایت DRAM و 1 ترابایت فلش به یک رایانه رومیزی ، عملکرد مشابهی را بدست آوردند. علاوه بر این ، با ترکیب چندین دستگاه ، آنها می توانند نمودارهای گسترده ای را انجام دهند - تا 4 میلیارد گره و 128 میلیارد خط اتصال - که هیچ سیستم دیگری نمی تواند روی سرور 128 گیگابایتی آن را اداره کند.

سانگ وو جون ، دانشجوی فارغ التحصیل CSAIL و نویسنده اول در مقاله ای که دستگاه را توصیف می کند ، می گوید: "نکته اصلی این است که ما می توانیم عملکرد را با دستگاه های بسیار کوچکتر ، کمتر و خنک تر - مانند دما و مصرف برق" حفظ کنیم. در سمپوزیوم بین المللی معماری رایانه (ISCA) ارائه می شود.

این دستگاه می تواند برای کاهش هزینه ها و انرژی مرتبط با آنالیز نمودار و حتی بهبود عملکرد در طیف گسترده ای از برنامه ها استفاده شود. به عنوان مثال محققان در حال حاضر برنامه ای را تولید می کنند که می تواند ژن های ایجاد کننده سرطان را شناسایی کند. شرکت های بزرگ فنی مانند Google همچنین می توانند با استفاده از ماشین های بسیار کمتری برای اجرای تجزیه و تحلیل ، دستگاهها را برای کاهش ردپای انرژی خود به کار گیرند.

Arvind ، استاد جانسون ، مهندس علوم کامپیوتر ، می گوید: "پردازش نمودار چنین ایده کلی است." "رده بندی صفحه با تشخیص ژن چه ارتباطی دارد؟ برای ما ، این مشکل محاسبه یکسان است - فقط نمودارهای مختلف با معانی مختلف. نوع برنامه شخصی که توسعه می دهد تأثیر آن بر جامعه را تعیین می کند."

نویسندگان مقاله عبارتند از Shuotao Xu ، دانش آموخته CSAIL ، و Andy Wright و Sizhuo Zhang ، دو دانشجوی فارغ التحصیل CSAIL و گروه مهندسی برق و علوم کامپیوتر.

محققان توانستند با وصل كردن دو دستگاه از آنها ، در مجموع 1 گیگابایت DRAM و 1 ترابایت فلاش ، به چندین نمودار بزرگ - با حداكثر 3.5 میلیارد گره و 128 میلیارد خط اتصال - در رایانه رومیزی پردازش كنند. برای پردازش نمودارها همه سیستمهای سنتی به یک سرور نیاز داشتند که هزاران دلار هزینه دارد و شامل 128 گیگابایت DRAM بود. اعتبار: موسسه فناوری ماساچوست
مرتب سازی و کاهش

در تجزیه و تحلیل نمودار ، یک سیستم اساساً مقدار گره را بر اساس اتصالات خود با گره های دیگر ، از جمله سایر معیارها ، جستجو و به روز می کند. به عنوان مثال ، در رتبه بندی صفحه وب ، هر گره یک صفحه وب را نشان می دهد. اگر گره A از مقدار بالایی برخوردار باشد و به گره B متصل شود ، مقدار گره B نیز افزایش می یابد.

سیستم های سنتی تمام داده های نمودار را در DRAM ذخیره می کنند ، که باعث می شود آنها سریع در پردازش داده ها بلکه گرسنه و گرسنه باشند. برخی از سیستم ها برخی از ذخیره سازی داده ها را برای فلش کردن بارگذاری می کنند ، که ارزان تر اما کندتر و کارآمدتر هستند ، بنابراین هنوز به مقدار قابل توجهی از DRAM نیاز دارند.

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

سیستم های تجزیه و تحلیل نمودار نیاز به دسترسی به گره هایی دارند که ممکن است از ساختار بسیار گسترده و پراکنده گرافیکی بسیار دور از یکدیگر باشند. سیستم ها معمولاً برای به روزرسانی مقدار گره ، دسترسی مستقیمی به مثلاً 4 تا 8 بایت داده دارند. DRAM دسترسی مستقیم را خیلی سریع فراهم می کند. با این حال ، فلش ، فقط به داده های 4- تا 8 کیلو بیتی دسترسی پیدا می کند ، اما هنوز هم چند بایت را به روز می کند. با پرش به پهنای باند ، نمودارهای دستیابی به هر درخواست را تکرار کنید. جون می گوید: "اگر شما نیاز دارید که به کل 8 کیلوبایت دسترسی پیدا کنید ، و فقط 8 بایت استفاده کنید و مابقی را پرتاب کنید ، در نهایت 1000 بار عملکرد را دور می اندازید."

در عوض ، الگوریتم مرتب سازی مرتب سازی ، کلیه درخواستهای دسترسی مستقیم را انجام می دهد و آنها را به ترتیب پی در پی توسط شناسه ها مرتب می کند ، که مقصد درخواست را نشان می دهد - مانند جمع آوری تمام به روز رسانی ها برای گره A ، همه برای گره B و غیره. سپس فلش می تواند به هزاران درخواست به اندازه هزار کیلوبایت دسترسی پیدا کند و آن را بسیار کارآمدتر کند.

برای صرفه جویی بیشتر در توان محاسباتی و پهنای باند ، الگوریتم همزمان داده ها را به کوچکترین گروه بندی ممکن ادغام می کند. هر زمان که الگوریتم شناسه های تطبیق را یادداشت می کند ، آن ها را در یک بسته داده واحد قرار می دهد - مانند A1 و A2 A3. این کار با انجام این کار ، ایجاد بسته های بطور فزاینده ای از داده ها با شناسه های تطبیق ، تا زمانی که کوچکترین بسته ممکن برای مرتب سازی تولید کند ، ادامه دارد. این به طور چشمگیری میزان درخواست های تکراری برای دسترسی را کاهش می دهد.

محققان با استفاده از الگوریتم مرتب سازی بر روی دو نمودار بزرگ ، کل داده های مورد نیاز برای به روزرسانی در فلش را حدود 90 درصد کاهش دادند.