Hypergraph +: یک الگوریتم برنامه‌ریزی وظایف مبتنی بر هایپرگراف بهبودیافته برای پردازش داده‌های فضایی عظیم در پلت‌فرم‌های Master-Slave

خلاصه

پردازش داده‌های مکانی اغلب به مجموعه‌های داده عظیم نیاز دارد و کارایی زمان‌بندی کار/داده این برنامه‌ها بر عملکرد کلی پردازش تأثیر می‌گذارد. در میان استراتژی‌های زمان‌بندی موجود، الگوریتم‌های مبتنی بر هایپرگراف الگوی اشتراک‌گذاری داده‌ها را به‌صورت جهانی ثبت می‌کنند و حجم کل ارتباطات را به میزان قابل توجهی کاهش می‌دهند. با این حال، به دلیل بسترهای پردازش ناهمگن، پارتیشن بندی تک هایپرگراف برای زمان بندی بعدی ممکن است بهینه نباشد. علاوه بر این، این الگوریتم‌های زمان‌بندی همپوشانی بین اجرای کار و انتقال داده را نادیده می‌گیرند که می‌تواند زمان اجرا را بیشتر کاهش دهد. به منظور پرداختن به این مشکلات، یک الگوریتم برنامه ریزی کار مبتنی بر هایپرگراف توسعه یافته، به نام Hypergraph +، برای پردازش داده های فضایی عظیم پیشنهاد شده است. هایپرگراف+ الگوریتم‌های زمان‌بندی هایپرگراف فعلی را از دو طریق بهبود می‌بخشد: (1) ناهمگونی پلتفرم را در نظر می‌گیرد تا یک تابع متریک برای ارزیابی کیفیت پارتیشن‌بندی به منظور استخراج بهترین برنامه کار/فایل ارائه دهد. و (2) می تواند همپوشانی بین ارتباطات و محاسبات را به حداکثر برساند. جعبه ابزار GridSim برای ارزیابی Hypergraph + در یک برنامه درون یابی فضایی IDW بر روی پلتفرم های master-slave ناهمگن استفاده شد. آزمایش‌ها نشان می‌دهند که الگوریتم Hypergraph + پیشنهادی به طور متوسط 43٪ کمتر از الگوریتم زمان‌بندی هایپرگراف اصلی به دست می‌آورد، اما همچنان کارایی زمان‌بندی بالایی را حفظ می‌کند.

کلید واژه ها:

برنامه ریزی وظایف ؛ هایپرگراف + ; پردازش داده های مکانی ؛ پلت فرم های ارباب برده

1. معرفی

در سال‌های اخیر، با توسعه سریع فن‌آوری‌های نقشه برداری و سنجش از دور، حجم داده‌های مکانی به طور چشمگیری افزایش یافته است [ 1 ، 2 ، 3 ]. پردازش داده های مکانی یک نوع معمولی از برنامه های کاربردی داده فشرده است که در آن کاربران باید به داده های مکانی عظیم دسترسی داشته باشند و آنها را پردازش کنند. شکل 1یک سناریوی محاسباتی معمولی فشرده داده را نشان می دهد که از مجموعه ای از گره های ذخیره سازی و محاسباتی تشکیل شده است که در یک شبکه با هم همکاری می کنند. هر کار به زیر مجموعه ای از فایل های ورودی از گره های ذخیره سازی نیاز دارد. یک کار ممکن است تعدادی فایل را با وظایف دیگر به اشتراک بگذارد، در حالی که یک کار جداگانه برای اجرا به یک گره محاسباتی ارسال می شود. خود گره های محاسباتی برای انتقال داده از طریق شبکه به گره های ذخیره سازی متصل می شوند. این همکاری با استراتژی زمان‌بندی کار/داده هماهنگ می‌شود. بنابراین، کارایی استراتژی زمان‌بندی تأثیر مهمی بر عملکرد همکاری دارد.

برای چنین برنامه های کاربردی داده فشرده، تعدادی از استراتژی های زمان بندی پیشنهاد شده است، از جمله الگوریتم های وظیفه گرا، داده آگاه و مبتنی بر هایپرگراف. در میان این الگوریتم‌های زمان‌بندی، تنها نوع الگوریتم‌های مبتنی بر هایپرگراف می‌توانند به‌طور کامل اشتراک‌گذاری داده‌ها را در میان وظایف ثبت کنند و در نتیجه انتقال کلی داده را به حداقل برسانند و در عین حال توزیع متعادل بارهای محاسباتی را در گره‌ها حفظ کنند. با این حال، پلتفرم‌های پردازش ناهمگن، مشکلات بیشتری را در این استراتژی‌های زمان‌بندی مبتنی بر هایپرگراف ایجاد می‌کنند. مدل هایپرگراف فرموله شده می تواند به طور کامل رابطه بین وظایف، فایل های داده و بسترهای محاسباتی را نشان دهد، اما از آنجایی که گره اجرای کار و مقصد انتقال فایل قبل از زمان بندی ناشناخته هستند، این نوع الگوریتم هایپرگراف بهبودیافته نمی توانند پردازنده ها یا ناهمگونی شبکه را در نظر بگیرند. بدون در نظر گرفتن ناهمگونی پلت فرم، زمان‌بندی با پارتیشن‌بندی تک هایپرگراف بهینه نیست. علاوه بر این، الگوریتم‌های زمان‌بندی موجود از جمله رویکردهای هایپرگراف به طور کلی از همپوشانی بین اجرای وظایف و انتقال داده غفلت می‌کنند. این همپوشانی‌های نادیده گرفته شده ممکن است برای کاهش بیشتر زمان کل اجرای کار مورد سوء استفاده قرار گیرند.

برای رسیدگی به این مشکلات، ما یک الگوریتم برنامه‌ریزی کار مبتنی بر هایپرگراف توسعه یافته به نام Hypergraph + پیشنهاد می‌کنیم. Hypergraph + در ابتدا یک پلت فرم master-slave، برنامه های کاربردی پردازش داده های فضایی و یک هدف زمان بندی را در یک مدل هایپرگراف عمومی کپسوله می کند. Hypergraph + زمان‌بندی بعدی شامل دو مرحله متوالی است: تطبیق و ترتیب. در مرحله تطبیق، یک تابع Fitness ناهمگونی پلت فرم را نشان می دهد، کیفیت پارتیشن بندی هایپرگراف را ارزیابی می کند و پارتیشن بهینه را انتخاب می کند. در مرحله سفارش، یک متریک Sharing-Files اجرای کار را تعیین می کند تا همپوشانی بین ارتباطات و محاسبات را به حداکثر برساند.

ما آزمایش‌هایی را برای مقایسه الگوریتم Hypergraph + پیشنهادی خود با سه الگوریتم زمان‌بندی کلاسیک بر روی یک پلت‌فرم مجازی ناهمگن master-slave با استفاده از جعبه ابزار شبیه‌سازی GridSim [ 4 ] انجام دادیم. این الگوریتم‌های زمان‌بندی کلاسیک شامل MinMin [ 5 ]، XSufferage [ 6 ] و الگوریتم زمان‌بندی مبتنی بر هایپرگراف خالص [ 7 ] است که در این مقاله به خاطر سادگی آن را Hypergraph می‌نامیم. برنامه هدف یک درونیابی IDW واقعی از یک ابر نقطه عظیم است. نتایج شبیه‌سازی نشان می‌دهد که در مقایسه با Hypergraph ، Hypergraph پیشنهادی ما+ الگوریتم می تواند زمان اجرای کار را بیش از 43 درصد در زمان برنامه ریزی برنامه های کاربردی پردازش داده های مکانی عظیم کاهش دهد.

بقیه این مقاله به شرح زیر سازماندهی شده است. استراتژی های پارتیشن بندی و زمان بندی هایپرگراف برای برنامه های کاربردی داده فشرده در بخش 2 معرفی شده است . مدل فراگراف کلی فرموله شده برای زمانبندی کار در بخش 3 ارائه شده است . بخش 4 الگوریتم Hypergraph + پیشنهادی را تشریح می کند و به دنبال آن جزئیات نتیجه شبیه سازی در بخش 5 آمده است . بخش 6 مقاله را به پایان می رساند.

2. پیشینه و کارهای مرتبط

2.1. Hypergraph و Hypergraph Partitioning

هایپرگراف H = ( V , N ) به عنوان مجموعه ای از رئوس V و مجموعه ای از لبه های N که آن راس ها را به هم متصل می کند تعریف می شود [ 8 ]. هر لبه nj∈نیک زیر مجموعه غیر خالی از رئوس V است ، به عنوان مثال، nj⊆V. شکل 2 یک ابرگراف را نشان می دهد. در این شکل، منحنی بسته نشان دهنده یک لبه بیش از حد و نقاط در منحنی بسته نشان دهنده رئوس روی این لبه است. یک گراف را می توان به عنوان نوع خاصی از هایپرگراف در نظر گرفت که در آن هر لبه تنها می تواند دو راس را به هم متصل کند. مشابه یک نمودار، وزن w _i و هزینه c _{j را} می توان به رئوس ( vمن∈V) و لبه های زیاد ( nj∈ن) از هایپرگراف، به ترتیب.

یک پارتیشن Π = { V ₁ , V ₂ , … , V _K } پارتیشن K-way H نامیده می شود اگر (1) هر قسمت V _k زیر مجموعه ای غیر خالی از H باشد . (2) همه قطعات به صورت جفتی از هم جدا می شوند و (3) اتحاد همه قطعات برابر با V است . در یک پارتیشن Π ، اگر یک لبه دارای حداقل یک راس در یک قسمت باشد، آنگاه به این قسمت متصل می شود. مجموعه اتصال Λ _j یک لبه فوق العاده n _j نشان دهنده تمام قطعات متصل شده توسط n _{j است.}و مقدار اتصال λ _j = | Λ _j | از n _j به عنوان تعداد قطعات متصل شده توسط n _j تعریف می شود . اگر یک لبه بیش از یک قسمت را به هم متصل کند، بریده می شود (یعنی λ _j > 1) و اگر در غیر این صورت، بریده نشده در نظر گرفته می شود (یعنی λ _j = 1). اندازه برش یک پارتیشن Π مانند رابطه (1) محاسبه می شود:

برش اندازه(Π)=∑nj∈نجتوتیجj(λj–1)

(1)

که در آن N _برش مجموعه ای از تمام لبه های برش خورده است و هر لبه برش n _j هزینه ای را متحمل می شود جj(λj–1). این اندازه پارتیشن به عنوان معیار اتصال 1 نیز شناخته می شود .

برای حل مشکل پارتیشن هایپرگراف، باید پارتیشنی پیدا شود که اندازه برش به حداقل برسد و تعادل نسبی بین تمام قطعات حفظ شود. یک پارتیشن Π از H متعادل است اگر حجم کار W _k هر قسمت V _k معیار تعادل نشان داده شده در رابطه (2) را برآورده کند:

دبلیوک=دبلیوآvg(1+ε)، برای 1≤ک≤ک

(2)

جایی که دبلیوک=∑vمن∈Vکwمننشان دهنده مجموع اوزان رأس یک قسمت V _k است . دبلیوآvg=∑Vمن∈Vwمنکمیانگین وزن است؛ و ε یک مقدار نامتعادل از پیش تعیین شده است.

اگرچه پارتیشن بندی هایپرگراف یک مشکل سخت NP است، اما هنوز برخی از الگوریتم های پارتیشن هایپرگراف عالی وجود دارد. علاوه بر این، ابزارهای منبع باز، مانند hMETIS [ 9 ]، PaToH [ 10 ] و Parkway [ 11 ]، برای اجرای پارتیشن بندی هایپرگراف با کیفیت بالا در دسترس هستند. پارتیشن بندی هایپرگراف به طور گسترده در بسیاری از زمینه ها استفاده می شود، از جمله طراحی یکپارچه سازی در مقیاس بسیار بزرگ (VLSI) [ 12 ، 13 ]، داده کاوی [ 14 ، 15 ]، محاسبات علمی موازی [ 16 ، 17 ]، و زمان بندی کار برای برنامه های کاربردی داده فشرده [ 7 ، 18 ].

علاوه بر این، یک هایپرگراف را می توان به عنوان یک گراف دوبخشی نیز نشان داد، به عنوان مثال، گراف مفهومی [ 19 ، 20 ]. یک نمودار مفهومی شامل دو رأس غیرمتناسب و روابط معنایی به عنوان یال های جهت دار است که رئوس ناپیوسته را به هم متصل می کنند. نمودارهای مفهومی می توانند فرآیندهای حل مسئله و تصمیم گیری، از جمله هوش مصنوعی، داده کاوی و استدلال مبتنی بر مورد را پشتیبانی کنند [ 21 ]. با این حال، یک هایپرگراف بسیار کلی تر و واضح تر از یک گراف مفهومی است و در اینجا برای مدل سازی پردازش داده های مکانی عظیم انتخاب شده است.

2.2. اکتشافی زمانبندی برای برنامه های کاربردی داده فشرده

زمان‌بندی برنامه‌های کاربردی داده فشرده به طور گسترده مورد مطالعه قرار گرفته است و تعدادی الگوریتم زمان‌بندی پیشنهاد شده است. با توجه به اینکه آیا و چگونه آنها انتقال داده را در نظر می گیرند، این الگوریتم ها را می توان به سه دسته تقسیم کرد: وظیفه گرا، داده آگاه و مبتنی بر هایپرگراف.

الگوریتم‌های زمان‌بندی وظیفه‌محور معمولاً به اطلاعات دقیق در مورد وظایف و ماشین‌ها برای تخمین دقیق زمان‌های اجرای کار در هر ماشین نیاز دارند. ماهسواران و همکاران چندین اکتشافی نگاشت معمولی از جمله MinMin ، MaxMin و Sufferage [ 5 ] را پیشنهاد کرد. از بین وظایف برنامه ریزی نشده، MinMin وظیفه ای را انتخاب می کند که کمترین زمان تکمیل را داشته باشد و این کار را به ماشین مربوطه اختصاص می دهد که می تواند آن را سریع ترین محاسبه کند. بر خلاف MinMin ، MaxMin کار را با حداکثر زودترین زمان تکمیل به سریعترین گره در حال اجرا اختصاص می دهد. Sufferage وظیفه ای را با بالاترین میزان انتخاب می کندمقدار رنج ، که به عنوان تفاوت بین زودترین زمان تکمیل و دومین زمان تکمیل اولیه آن تعریف می شود. با این حال، هیچ یک از این اکتشافی‌ها، مسائل داده را هنگام تصمیم‌گیری زمان‌بندی در برنامه‌های کاربردی فشرده داده در نظر نمی‌گیرند و بنابراین، ناکارآمد هستند.

متفاوت از الگوریتم‌های وظیفه‌محور، الگوریتم‌های زمان‌بندی آگاه از داده می‌توانند بهبود عملکرد قابل توجهی ایجاد کنند زیرا هم انتقال داده و هم زمان‌بندی کار را در نظر می‌گیرند [ 2 ، 22 ، 23 ]. کازانووا و همکاران پسوندی از Sufferage به نام XSufferage را پیشنهاد کرد که از موقعیت فایل سوء استفاده می کند و مقدار رنج سطح خوشه را برای دستیابی به عملکرد بهتر محاسبه می کند [ 6 ]. الگوریتم Close-to-Files [ 24] کارها را با تکرار فایل بر روی پردازنده کم بارگذاری شده نزدیک به سایت هایی که فایل های ورودی در آن ذخیره می شوند، زمان بندی می کند. ژانگ و همکاران استراتژی‌های پیش‌زمان‌بندی داده‌های فراابتکاری و زمان‌بندی کار پویا برای حل مشکلات مقایسه همه جانبه در سیستم‌های توزیع ناهمگن [ 25 ] ارائه شده است. Szmajduch و Kołodziej نسخه جدیدی از مدل زمان مورد انتظار برای محاسبه ماتریس (ETC Matrix) را ارائه کردند که در آن انتقال داده و محاسبه کار درگیر است [ 26 ]. با این حال، این الگوریتم‌های زمان‌بندی آگاه از داده، الگوهای اشتراک‌گذاری فایل را به‌صورت جهانی در نظر نمی‌گیرند و بنابراین نمی‌توانند به طور کامل از درجات بالایی از I/O مشترک بهره‌برداری کنند.

الگوریتم های زمان بندی مبتنی بر هایپرگراف به صورت جهانی انتقال داده ها را در طول زمان بندی کار بهینه می کنند. خانا و همکاران یک استراتژی مبتنی بر پارتیشن بندی هایپرگراف برای برنامه ریزی دسته ای از وظایف مستقل برای به حداقل رساندن حجم انتقال داده از راه دور و اختلاف بر روی گره های ذخیره سازی و در عین حال حفظ توزیع بار محاسباتی متعادل در سراسر گره های محاسباتی پیشنهاد کرد [7 ] . کایا و آیکانات یک رویکرد زمان‌بندی تکراری را پیشنهاد کردند که عملکرد زمان‌بندی را با اتخاذ پارتیشن‌بندی هایپرگراف بهبود می‌بخشد [ 18 ]. آنها از اشتراک گذاری داده ها به روشی جهانی برای دستیابی به عملکرد بهتری نسبت به دو نوع الگوریتم دیگر بهره برداری می کنند.

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

3. مدل زمانبندی کار مبتنی بر هایپرگراف

در این بخش، ما یک مدل زمان‌بندی کار مبتنی بر هایپرگراف کلی متشکل از یک پلت فرم اصلی، برنامه‌های پردازش داده‌های مکانی و هدف زمان‌بندی را فرموله می‌کنیم.

3.1. مدل پلت فرم

_پلتفرم هدف با یک الگوی معمولی ناهمگن master-slave مطابقت دارد و شامل یک Master P ₀ و مجموعه‌ای از پردازنده‌های p برده، _P = { P1 ، P2 ، …، P _p } است که در شکل 3 نشان داده شده است . Master P ₀ از طریق یک شبکه محلی به بردگان متصل است. بردها به عنوان گره های محاسباتی به کار می روند و هر کدام دارای یک قابلیت پردازش نسبی ρ برای اجرای وظایف هستند. ما فرض می کنیم که تمام فایل های داده در ابتدا در Master P _{0 ذخیره می شوند}، بنابراین اگر یک فایل ورودی مورد نیاز یک کار در پردازشگر slave جایی که وظیفه اجرا می شود نباشد، باید از Master P ₀ درخواست شود .

پهنای باند پیوند بین اصلی P ₀ و پردازشگر برده P _k با b _k ( k = 1 , 2 , …, p ) نشان داده می شود، در حالی که حداکثر پهنای باند خروجی P ₀ با b _m نشان داده می شود . به منظور کاهش زمان انتظار برای کارها، اجرای وظایف و انتقال فایل ها می توانند بر روی بردها همپوشانی داشته باشند، به عنوان مثال، یک پردازنده برده می تواند یک کار را اجرا کند در حالی که فایل های لازم را برای اجرای کار بعدی می پذیرد.

مدل اتصال چندگانه [ 27 ] که ارتباطات بین Masters و Slave را امکان‌پذیر می‌سازد استفاده می‌شود: (1) به چندین Slave اجازه می‌دهد تا فایل‌ها را از Master P ₀ به طور همزمان دانلود کنند. (2) دو برده نمی توانند یک فایل را همزمان درخواست کنند. و (3) یک پردازنده برده می تواند پس از ذخیره فایل دریافتی قبلی در دیسک محلی خود، فایل دیگری را دریافت کند.

3.2. مدل کاربردی

برنامه پردازش داده های مکانی A = ( T , F ) شامل مجموعه ای از وظایف مستقل T = { t ₁ , t ₂_, …, t _n } و m فایل ها F = { f ₁ , f ₂_, …, f _m } . اجرای هر کار t _i به زیر مجموعه ای از فایل ها بستگی دارد که با F _i = { f ₁ , f ₂ , …, f نشان داده می شود._k }; یک فایل داده شده ممکن است توسط چندین کار به اشتراک گذاشته شود. برنامه هدف A را می توان به عنوان یک مدل هایپرگراف H = ( V , N ) نشان داد تا این الگوی اشتراک گذاری داده را به تصویر بکشد. در مدل H فرموله‌شده ما، وظایف با رئوس و فایل‌ها با لبه‌ها مطابقت دارند. لبه هایپر n _j که برخی از رئوس را به هم متصل می کند به این معنی است که این فایل f _j به عنوان ورودی مورد نیاز است و توسط مجموعه ای از وظایف به اشتراک گذاشته می شود. وزن رأس w _i زمان تخمینی تکمیل کار مربوطه T _ct ( t _i ) و وزن بیش از حد لبه است.c _j برابر با اندازه فایل ( f _j ) است.

زمان تخمینی تکمیل یک کار T _ct ( t _i ) مجموع کل زمان انتقال فایل ورودی از Master P ₀ و زمان واقعی محاسبه کار است. قبل از نقشه برداری کار، مقصد انتقال فایل ناشناخته است، اما زمان واقعی انتقال فایل را می توان از اندازه فایل f _j تقسیم بر حداکثر پهنای باند خروجی b _m P ₀ تخمین زد . برای برنامه‌های پردازش داده‌های مکانی، می‌توان زمان محاسبه واقعی یک کار را متناسب با اندازه فایل‌های ورودی F _i_وC فرض کرد.هزینه محاسباتی از پیش تعریف شده یک بایت داده است. بنابراین، کل زمان تخمینی تکمیل کار t _i در رابطه (3) تعریف می شود:

تیجتی(تیمن)=∑fj∈افمن(اسمنzه(fj))*1بمتر+∑fj∈افمن(اسمنzه(fj))*سی=∑fj∈افمن(اسمنzه(fj))*(1بمتر+سی)

(3)

محاسبات همسایگی معمولاً در برنامه های کاربردی پردازش داده های مکانی مورد نیاز است. شکل 4 برخی از پیکربندی های محله معمولی، از جمله فون نویمان، مور، و محله های توسعه یافته مور را نشان می دهد [ 28 ]. در پردازش همسایگی، یک سلول به طور کلی با یک بلوک از پیکسل ها مطابقت دارد که مقادیر مشخصه آن در یک فایل ذخیره می شود. وقتی از الگوریتم همسایگی استفاده می‌شود، برای مثال، برای محاسبه شیب‌ها و جنبه‌ها از ارتفاعات، کار محاسباتی برای یک سلول معین به مقادیر سلول‌های همسایگی آن (از جمله خود سلول)، یعنی مجموعه‌ای از فایل‌های مربوطه نیاز دارد.

یک مثال محله مور نیز در اینجا برای نشان دادن نحوه ساخت چنین مدل هایپرگراف ارائه شده است: در شکل 5 ، وظایف T = { 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 ، 9 } و فایل های F = { A , B , C , D , E , F , G , H , I }. فایل B ، فایل D و فایلE توسط کار T ₁ برای محاسبه اولین خانه مورد نیاز است، سپس F ₁ = { A , B , D , E }. به طور مشابه، F ₂ = { A , B , C , D , E , F }, F ₃ = { B , C , E , F }, F ₄ = { A , B , D , E , G, H }, F ₅ = { A , B , C , D , E , F , G , H , I }, F ₆ = { B , C , E , F , H , I }, F ₇ = { D , E , G , H }, F ₈ = { D , E , F, G , H , I } و F ₉ = { E , F , H , I }.

شکل 6 مدل هایپرگراف فرمول بندی شده را نشان می دهد: هایپرگراف H = ( V , N ), V = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , N = { A = { 1 , 2 , 4 , 5 }, B = { 1 , 2 , 3 , 4 , 5 , 6 },C = { 2 , 3 , 5 , 6 }, D = { 1 , 2 , 4 , 5 , 7 , 8 }, E = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ، F = { 2 ، 3 ، 5 ، 6 ، 8 ، 9 }،G = { 4 , 5 , 7 , 8 }, H = { 4 , 5 , 6 , 7 , 8 , 9 } و I = { 5 , 6 , 8 , 9 }; Master P ₀ در ابتدا همه فایل ها را نگه می دارد و Slaves P = { P ₁ , P ₂ , P ₃ } این وظایف را اجرا می کنند.

3.3. هدف برنامه ریزی

هدف زمان‌بندی به حداقل رساندن زمان اجرای کلی است که به عنوان makepan شناخته می‌شود، که از اولین انتقال فایل شروع می‌شود و با تکمیل آخرین اجرای کار به پایان می‌رسد [ 18 ]. از آنجایی که زمان تکمیل تخمینی یک کار، مجموع کل زمان انتقال داده و زمان واقعی محاسبه کار است، هدف زمان‌بندی کوتاه کردن مقدار انتقال داده و متعادل کردن بار محاسباتی در میان بردها است به گونه‌ای که اجرای کلی زمان به حداقل می رسد. با کمک مدل هایپرگراف فرموله شده، این هدف بیشتر تعمیم می یابد و به عنوان هدف تقسیم بندی هایپرگراف در نظر گرفته می شود.

به حداقل رساندن انتقال داده توسط هدف پارتیشن بندی هایپرگراف به دست می آید.

پس از ساخت هایپرگراف H ، هدف یک مسئله پارتیشن بندی هایپرگراف معمولی یافتن یک پارتیشن Π = { V ₁ ، V ₂ ، …، VK } است که در آن _اندازه برش به حداقل می رسد. برای یک پارتیشن معین Π ، یک لبه برش n _j با اتصال λ _j به این معنی است که فایل f _j باید منتقل شود. λj–1بارها بیشتر اما متحمل اضافی می شود (λj–1)*اندازه(fj)بایت های انتقال داده بنابراین، کل هزینه ارتباطات را می توان به صورت معادله (4) محاسبه کرد:

کام(Π)=∑fj∈افλj*اسمنzه(fj)=∑nj∈نλj*جj=∑nj∈نجتوتی(λj–1)*جj+∑nj∈نجj

(4)

جایی که ∑nj∈نجjبرابر با حجم کل فایل ورودی است و می تواند ثابت در نظر گرفته شود، بنابراین کام(Π)بستگی دارد به برش اندازه(Π). بنابراین، به حداقل رساندن اندازه برش معادل به حداقل رساندن انتقال کل داده است.

زمان بندی تعادل بار توسط محدودیت پارتیشن بندی هایپرگراف تضمین می شود.

معادله (2) نشان می دهد که پارتیشن Π از H متعادل است اگر هر قسمت V _k محدودیت تعادل را برآورده کند. از آنجایی که زمان تکمیل تخمین زده شده یک کار، وزن راس مربوطه است، پس بار کاری یک پردازشگر برده P _k برابر است با زمان انباشته اجرای همه وظایف محول شده:

دبلیوک(Π)=∑Vمن∈Vکwمن=∑تیمن∈پکتیجتی(تیمن)=∑تیمن∈پک∑fj∈افمن(1بمتر+سی)*اسمنzه(fj)

(5)

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

4. الگوریتم Hypergraph + Scheduling

الگوریتم زمانبندی Hypergraph + پیشنهادی دارای دو مرحله متوالی است: تطبیق و ترتیب. بخش 4.1 پارتیشن بندی هایپرگراف را برای نگاشت وظایف به پردازنده های برده معرفی می کند. بخش 4.2 یک الگوریتم سفارشی را توضیح می دهد که به طور موثر وظایف را برای اجرا سفارش می دهد و بر این اساس فایل های مورد نیاز را منتقل می کند.

4.1. پارتیشن بندی هایپرگراف برای تطبیق وظایف

پارتیشن بندی هایپرگراف یک طرح اولیه برای تخصیص وظایف به پردازنده های برده ارائه می دهد تا انتقال داده ها به حداقل برسد و بارهای کاری محاسباتی متعادل شود. پارتیشن بندی تک هایپرگراف ممکن است بهینه نباشد، با این حال، تحت شرایط ناهمگونی پلت فرم. بنابراین، هنگام ارزیابی کیفیت نتایج پارتیشن بندی برای بهینه سازی، هم ناهمگنی شبکه و هم ناهمگنی پردازنده را در نظر می گیریم. کل جریان تطبیق وظایف به بردگان در شکل 7 نشان داده شده است . ابتدا، مدل هایپرگراف ورودی به سرعت با ابزار PaToH [ 10 ] پارتیشن بندی می شود تا پارتیشن Π = { V ₁ , V ₂ , … , V _K } بدست آید. بعد،ارزیابی تناسب اندام بر روی پارتیشن Π با تابع تناسب انجام می شود : تناسب اندام ( Π ). در نهایت، پارتیشن بهینه برای نگاشت وظایف به بردگان انتخاب می شود.

ارزیابی تناسب اندام ( Π ) به شرح زیر است:

(الف) معادله (4) فقط برای موارد شبکه همگن معتبر است و λj روی ثابت تنظیم می شود _.1بمتر. پس از به دست آوردن یک پارتیشن بندی هایپرگراف، حجم واقعی ارتباط کام“(Π)با رابطه (6) محاسبه می شود. شبکه ناهمگن، λ _j به اصلاح می شود ∑پک∈Λj1بک، جایی که Λ _j مجموعه ای از پردازنده های برده مورد نیاز برای انتقال فایل f j را نشان می دهد _و b _k پهنای باند _بین Pk و P 0 _است .

کام“(Π)=∑fj∈اف∑پک∈Λjاسمنzه(fj)بک

(6)

(ب) سپس، حجم کار واقعی هر پردازنده برده دبلیو“ک(Π)محاسبه می شود که مجموع بار محاسباتی و هزینه ارتباط است. بر خلاف معادله (5)، قابلیت پردازش نسبی ρ _k برای نمایش بار محاسباتی واقعی اضافه می شود و b _k جایگزین b _m می شود تا بار ارتباطی واقعی در رابطه (7) بدست آید.

دبلیو“ک(Π)=∑تیمن∈پک∑fj∈افمن(1بک+سیρک)*اسمنzه(fj)

(7)

(ج) میانگین حجم کار دبلیو“آvg(Π)و میانگین انحراف مربع حجم کار سد“دبلیو“ک(Π)مطابق معادلات (8) و (9) محاسبه می شوند.

دبلیو“آvg(Π)=∑ک=1کدبلیو“ک(Π)ک

(8)

سد“دبلیو“ک(Π)=∑ک=1ک(دبلیوک‘(Π)–دبلیوآvg‘(Π))ک

(9)

(د) مقدار تناسب در (10) تعریف شده است: یک مقدار تناسب کوچکتر نشان می دهد که پارتیشن دارای سربار ارتباط کمتر و بار محاسباتی به همان اندازه متعادل است.

تناسب اندام(Π)=کام“(Π)*سد“دبلیو“ک(Π)

(10)

از معادله (10)، مقدار تناسب کمتر به معنای کیفیت پارتیشن بهتر است. به طور کلی، کمترین مقدار تناسب با عدد تکرار n نسبت معکوس دارد، اما تعداد تکرار بیشتر، کل هزینه زمان ارزیابی را افزایش می دهد. برای دستیابی به تعادل هزینه/کیفیت، عدد تکرار n به صورت زیر انتخاب می شود. در ابتدا، n به یک عدد معین (مثلاً 10) تنظیم می شود. سپس، n هر بار دو برابر می شود تا زمانی که درصد کاهش در کمترین مقدار تناسب اندام کوچکتر از یک آستانه معین (مثلاً 5٪) شود. به این ترتیب، ارزیابی کیفیت پارتیشن رضایت بخشی را بدون صرف زمان زیاد ایجاد می کند.

4.2. سفارش وظایف و انتقال فایل

پس از اینکه همه وظایف به پردازنده‌های مقصدشان اختصاص داده شد، Hypergraph + ترتیب اجرای کار و انتقال فایل ورودی را تعیین می‌کند تا همپوشانی بین محاسبات و ارتباطات را به حداکثر برساند و در عین حال اختلاف نقطه پایانی را در میان بردگان کاهش دهد.

به منظور دستیابی به بیشینه سازی همپوشانی، یک معیار اشتراک گذاری فایل ها ( SF ) معرفی شده است تا اجرای وظیفه را در هر پردازنده ترتیب دهد. این متریک شباهت یک کار به وظایف دیگر را محاسبه می کند. مقدار SF یک وظیفه به عنوان تعداد بایت هایی تعریف می شود که فایل های ورودی وظیفه با سایر وظایف روی پردازنده اختصاص داده شده به اشتراک می گذارد. می توان آن را مانند رابطه (11) محاسبه کرد:

SF(تیمن)=∑تیj∈پک∑fایکس∈افمن⋂راافjاسمنzه(fایکس)،من≠j

(11)

Task t _i با مقدار SF ( t _i ) بالاتر به این معنی است که فایل های ورودی آن با وظایف بیشتری به اشتراک گذاشته می شود. وظیفه t _i که دارای بالاترین مقدار SF ( t _i ) است ابتدا اجرا می شود. سپس فایل های مورد نیاز از قبل منتقل می شوند. بنابراین سایر وظایف متکی بر این فایل ها متعاقباً اجرا می شوند. در این مورد، ارتباطات و محاسبات می توانند برای کاهش زمان انتظار وظایف، همپوشانی داشته باشند. الگوریتم 1 اکتشافی ترتیب کار پیشنهادی را تشریح می کند.

الگوریتم 1 ترتیب وظایف برای اجرا

(1): برای هر پردازنده برده P _k در P
(2): برای هر کار t را به P _{k نگاشت}_کردم
(3): ارزیابی تابع SF ( t _i );
(4): لیست L ( P _k ) از وظایف مرتب شده به ترتیب کاهش SF ( t _i ) را بسازید.
(5): پایان برای
(6): پایان برای
(7): این کار را تا زمانی انجام دهید که همه وظایف در T برنامه ریزی شوند
(8): پردازنده برده P _{k را} با حداکثر بار کاری پیدا کنید.
(9): اگر (فایل های ورودی وظیفه t _i از قبل روی پردازنده P _k هستند )
(10): وظیفه t _{i را} برای اجرا انتخاب کنید.
(11): دیگر
(12): اولین کار t _i در L ( P _k ) را برای اجرا انتخاب کنید.
(13): زمانبندی انتقال فایل وظیفه t _i ; ( الگوریتم 2 )
(14): وظیفه t _{i را} از L ( P _k )، T حذف کنید .
(15): به روز رسانی حجم کار P _k ;
(16): پایان دادن

انتقال فایل fj∈افمنبر اساس زودترین زمان تکمیل آن برنامه ریزی شده است. دو کار در پردازنده های برده مختلف ممکن است به یک فایل ورودی یکسان بستگی داشته باشد و باعث اختلاف نقطه پایانی بین پردازنده های برده شود. به منظور کاهش اختلاف نقطه پایانی، زمان تکمیل تخمینی شامل زمان انتقال واقعی و زمان انتظار است. زمان انتقال واقعی به اندازه فایل f _j تقسیم بر پهنای باند است. Tw ( f _j ) نشان دهنده زمان صرف شده برای انتقال در صف است زیرا سایر پردازنده های برده قبلاً درخواست هایی برای فایل _f j _به اصلی P ₀ ارسال کرده اند . زمان تخمینی تکمیل برای انتقال فایل f _jمانند رابطه (12) محاسبه می شود:

تیجتی(fj)=اسمنzه(fj)بک+تیw(fj)

(12)

الگوریتم 2 ساختار کلی اکتشافی انتقال فایل را در هر پردازنده توصیف می کند. اکتشافی با محاسبه زمان تکمیل تخمینی هر فایل در F _i شروع می شود ، که مجموعه ای از فایل های درخواست شده توسط کار t _i است (خط 2 تا خط 4). انتقال فایل f _j را با اولین زمان تکمیل برنامه ریزی می کند (خط 5). سپس فایل f _j از F _i (خط 6) حذف می شود و T _w (f _j ) بر این اساس به روز می شود (خط 7). این اکتشافی تکرار بعدی حلقه do را انجام می دهد تا زمانی که همه فایل ها منتقل شوند.

الگوریتم 2 اکتشافی انتقال فایل در هر پردازنده

(1): این کار را تا زمانی انجام دهید که تمام فایل های موجود در F _i منتقل شوند
(2): برای هر فایل f _j در F _i
(3): محاسبه T _ct ( f _j );
(4): پایان برای
(5): انتقال فایل f _j با اولین زمان تکمیل از P ₀ به P _k .
(6): حذف فایل f _j از F _i ;
(7): به روز رسانی T _w ( f _j );
(8): پایان دادن

5. آزمایش و بحث

5.1. منابع شبیه سازی شده

شبیه‌سازی‌ها یک محیط ارزیابی قابل تکرار و کنترل را فراهم می‌کنند و برای انجام ارزیابی الگوریتم Hypergraph + پیشنهادی ما استفاده می‌شوند . ما جعبه ابزار GridSim [ 4 ] را برای انجام شبیه‌سازی‌ها انتخاب کردیم، زیرا به ما امکان مدل‌سازی منابع پردازشگر ناهمگن و اتصال شبکه با پهنای باند مختلف را می‌دهد. GridSim همچنین از شبیه سازی زمان بندی استاتیک و پویا پشتیبانی می کند.

در این شبیه سازی، شش پردازنده برده مانند جدول 1 برای اجرای وظایف ورودی تعریف شد . هر پردازنده slave دارای دو ویژگی متمایز است، سرعت CPU و پهنای باند شبکه. از آنجایی که زمان اجرای کار را می توان بر حسب میلیون دستورالعمل (MI) تعریف کرد، سرعت منبع CPU به عنوان میلیون دستورالعمل در ثانیه (MIPS) مدل شد. پهنای باند شبکه، پهنای باند پیوند بین master و slave است. MIPS و پهنای باند به طور تصادفی برای این آزمایش ارزیابی تولید شد [ 29 ].

5.2. برنامه تجربی و مجموعه داده ها

ما درون یابی فضایی را به عنوان برنامه هدف برای ارزیابی الگوریتم زمان‌بندی Hypergraph+ انتخاب کردیم. برای سادگی، درون یابی با وزن معکوس فاصله (IDW) در آزمایش ها استفاده شد. IDW این اصل را منعکس می کند که ارزش تخمینی یک سلول به احتمال زیاد با نقاط نزدیک نسبت به نقاط دور مرتبط است [ 30 ]. معادله درونیابی IDW به صورت زیر تعریف می شود:

زپ=∑من=1ک(زمندمنβ)∑من=1ک(1دمنβ)

(13)

که در آن Z _p مقدار درونیابی شده در نقطه هدف p است . Z _i مقدار مشاهده شده در نقطه پراکندگی یکم p _i در همسایگی p است . k تعداد نقاط پراکندگی گرفته شده در درونیابی در همسایگی از پیش تعریف شده p است . d _i فاصله اقلیدسی از من نقطه پراکندگی p _i تا p است . و β یک عدد مثبت دلخواه به نام توان وزنی است.

یک مجموعه داده ابر نقطه LiDAR به عنوان ورودی واقعی در آزمایش‌ها استفاده شد. این داده های ابر نقطه LiDAR در شهرستان گیلمر، ویرجینیای غربی، ایالات متحده آمریکا به دست آمده و برای بارگیری در اینترنت رایگان بودند ( http://www.wvview.org/data/lidar/Gilmer/ ). مجموعه داده شامل 0.883 میلیارد نقطه است، و فاصله نقاط حدود 1.4 متر است که در شکل 8 نشان داده شده است . این مجموعه داده در فرمت فایل ASPRS LAS ذخیره می شود. حجم کل داده ها تقریباً 16.4 گیگابایت است.

مجموعه داده تجربی LiDAR بعداً به بلوک های چند نقطه ای تقسیم شد. درونیابی IDW مستلزم استفاده از همسایگی مور به عنوان ورودی بلوک‌های همسایه است و مدل کاربردی Hypergraph فرمول‌بندی‌شده همان مدل نمونه تعریف‌شده در بخش 3.2 است . در این مدل کاربردی، وزن فوق لبه cj به _اندازه هر بلوک نقطه تنظیم شد. وزن راس w _i روی زمان درونیابی بلوک نقطه متناظر T _ct تنظیم شد .

در رابطه (3)، ما به دست آوردیم که زمان محاسبه واقعی یک کار متناسب با اندازه فایل های ورودی آن است. بنابراین، ابتدا یک آزمایش اضافی برای بررسی رابطه کمی بین زمان درونیابی IDW و اندازه نقاط ورودی انجام شد. همانطور که در شکل 9 نشان داده شده ^است ، رابطه بین اندازه داده نقاط و زمان اجرای درون یابی IDW تقریبا خطی است ( R2 > 0.99). از تابع برازش منحنی، C به 0.0002 برای معادله (3) حل شد.

5.3. نتایج ارزیابی و بحث

با پلتفرم فرموله‌شده و مدل‌های کاربردی در بخش 5.1 و بخش 5.2 ، آزمایش‌هایی برای ارزیابی عملکرد و کارایی Hypergraph +، مقایسه آن با MinMin [ 5 ]، XSufferage [ 6 ] و Hypergraph ، که پارتیشن‌بندی هایپرگراف اصلی است، انجام شد. رویکرد مبتنی بر [ 7 ]. این سه اکتشافی، الگوریتم‌های برنامه‌ریزی مبتنی بر وظیفه‌محور، داده‌آگاه و مبتنی بر ابرگراف هستند که در بخش 2.2 شرح داده شده‌اند .

معیارهای مورد استفاده برای ارزیابی الگوریتم‌های زمان‌بندی عبارتند از زمان، درصد کاهش ورودی/خروجی و زمان اجرا. Makepan، به عنوان مثال، زمان اجرای کلی، رایج ترین معیار عملکرد برای یک الگوریتم زمان بندی است. فاصله زمانی کمتر به معنای عملکرد بهتر الگوریتم زمان بندی است. درصد کاهش ورودی/خروجی به‌عنوان نسبت مقدار مجموعه‌های داده‌ای که از فضای ذخیره‌سازی دیسک محلی به مقدار کل مجموعه داده‌های مورد نیاز وظایف مورد نیاز است، محاسبه شد. درصد کاهش ورودی/خروجی بالاتر به معنای کاهش بیشتر در انتقال داده است. زمان اجرا، زمان صرف شده برای زمان‌بندی وظایف پردازشگرهای محاسباتی است و پیچیدگی زمانی الگوریتم‌های زمان‌بندی را نشان می‌دهد. یک الگوریتم زمانبندی با زمان اجرای کمتر کارآمدتر خواهد بود. هر سه معیار یک ارزیابی کامل برای هر الگوریتم زمان‌بندی ارائه می‌دهند.

در آزمایش‌های ما، برنامه هدف یک مدل ارتفاع دیجیتالی از شهرستان گیلمر را از مجموعه داده LiDAR محاسبه کرد. ابر نقطه اصلی به اندازه بلوک‌های مختلف تقسیم می‌شود و این می‌تواند منجر به دانه‌بندی‌های مختلف کار و درجات مختلف همپوشانی ورودی/خروجی شود، به‌عنوان مثال، اندازه بلوک‌های کوچک‌تر همپوشانی ورودی/خروجی بیشتری ایجاد می‌کند. که از شکل 5 و مثال در بخش 3.2 نشان داده شده است ، تعداد وظایف درونیابی IDW برابر با تعداد بلوک های نقطه بود. نتایج تجربی در شکل 10 و شکل 11 نشان داده شده است .

همانطور که در شکل 10 نشان داده شده است ، زمانی که تعداد وظایف افزایش یافت، طول ساخت MinMin به سرعت افزایش یافت. XSufferage و Hypergraph از همین الگو پیروی کردند، اما طول ساخت Hypergraph + بسیار کندتر رشد کرد. در طول کل فرآیند اجرای کار، الگوریتم Hypergraph + پیشنهادی ما زمان کل اجرای MinMin ، XSufferage و Hypergraph را به ترتیب 70، 62، و 43 درصد کاهش داد. این نتایج نشان می دهد که Hypergraph + از سایر استراتژی های زمان بندی بهتر عمل می کند.

شکل 10 ب نشان می دهد که درصد کاهش I/O در این اکتشافی ها با تعداد کارها متفاوت است. وقتی تعداد کارها افزایش یافت، درصد کاهش ورودی/خروجی در MinMin حدود 40 درصد، XSufferage نزدیک به 55 درصد و Hypergraph بالای 80 درصد بود، اما Hypergraph + کاهش 2٪ تا 5٪ بیشتر از Hypergraph به دست آورد . از نظر متریک کاهش ورودی/خروجی، Hypergraph + برتر از MinMin ، XSufferage و Hypergraph بود .

همانطور که در شکل 10 a,b نشان داده شده است، MinMin و XSufferage با کاهش ورودی/خروجی کمتر نسبت به Hypergraph + و Hypergraph کندتر عمل می کنند . این به این دلیل است که MinMin به هیچ وجه اشتراک داده را در نظر نمی گیرد و XSufferage نمی تواند از الگوهای اشتراک گذاری داده در سطح جهانی بهره برداری کند. Hypergraph + و Hypergraph اشتراک گذاری داده ها را در سطح جهانی در نظر می گیرند به طوری که وظایف با ورودی مشترک تا حد امکان به همان پردازنده اختصاص داده می شود. علاوه بر این، Hypergraph+ می تواند نتیجه پارتیشن هایپرگراف بهینه را به دست آورد و احتمال همپوشانی بین ارتباطات و محاسبات را به حداکثر می رساند تا زمان انتظار برای کارها کاهش یابد. بنابراین، Hypergraph + عملکرد بهتری نسبت به Hypergraph از نظر میزان ساخت و درصد کاهش ورودی/خروجی دارد.

همانطور که در شکل 11 نشان داده شده است ، زمانی که تعداد کارها افزایش یافت، بر خلاف Hypergraph + و Hypergraph ، زمان اجرا با نرخ بسیار سریعتری برای MinMin و XSufferage افزایش یافت . MinMin و XSufferage باید زمان تکمیل مورد انتظار را برای هر کار در هر گره محاسباتی محاسبه کنند تا یک کار را تا زمانی که همه وظایف اجرا شوند انتخاب کنند. در نتیجه، پیچیدگی زمانی O(n2 ⁾ بود . از سوی دیگر، Hypergraph + و Hypergraph از پارتیشن بندی هایپرگراف برای نگاشت سریع همه وظایف به پردازنده ها استفاده می کنند، زیرا پیچیدگی زمانی پارتیشن بندی هایپرگراف O(n) + O(logn) بود [31 ]. Hypergraph + به طور متوسط تنها حدود 3 ثانیه کندتر از Hypergraph بود . همانطور که در شکل 10 الف مشاهده می شود، Hypergraph+ بیش از 2400 ثانیه در مقایسه با Hypergraph حفظ شده است . این سربار کوچک می تواند ناچیز باشد. بنابراین، Hypergraph + می تواند عملکرد بهتری نسبت به سه الگوریتم دیگر داشته باشد و همچنان کارایی بالایی را حفظ می کند.

6. نتیجه گیری

این مقاله یک الگوریتم زمان‌بندی Hypergraph + ارائه می‌کند که الگوریتم زمان‌بندی مبتنی بر هایپرگراف موجود را برای پردازش داده‌های فضایی گسترده برای به دست آوردن عملکرد بهتر گسترش می‌دهد. ابتدا یک مدل هایپرگراف کلی برای نمایش وظایف، مجموعه داده های فضایی و پلت فرم پردازش فرموله می کند. سپس، کیفیت نتایج پارتیشن بندی هایپرگراف توسط یک تابع Fitness برای نگاشت وظایف به پردازنده ها ارزیابی می شود، به طوری که حجم کل ارتباطات در حین متعادل کردن بارهای کاری محاسباتی به حداقل می رسد. علاوه بر این، Hypergraph + وظایف و انتقال فایل را برای به حداکثر رساندن احتمال همپوشانی بین ارتباطات و محاسبات با کاهش اختلاف نقطه پایانی بین پردازنده‌ها زمان‌بندی می‌کند. شبیه سازی برای مقایسه انجام شدHypergraph + با MinMin ، XSufferage ، و Hypergraph با استفاده از برنامه های درون یابی فضایی در پلت فرم های ناهمگن master-slave. نتایج شبیه سازی نشان می دهد که Hypergraph + به طور متوسط 43٪ بهتر از Hypergraph از نظر ساخت و ساز است، در حالی که کارایی Hypergraph را حفظ می کند .

در آینده، ما الگوریتم Hypergraph + را به مراکز ذخیره سازی سیستم فایل توزیع شده گسترش خواهیم داد. در حال حاضر، سیستم فایل توزیع شده، به عنوان مثال، Hadoop HDFS، برای ذخیره و پردازش مجموعه داده های فضایی گسترده استفاده می شود. تکرار داده ها اغلب در Hadoop HDFS برای بهبود در دسترس بودن و توان عملیاتی استفاده می شود. بنابراین، الگوریتم زمان‌بندی Hypergraph + ما را می‌توان برای رسیدگی به مشکل تکثیر داده‌ها و بهره‌برداری از درجه بالاتری از اشتراک‌گذاری داده‌ها در یک محیط Hadoop بررسی کرد.

منابع

لیو، ی. چن، بی. یو، اچ. ژائو، ی. هوانگ، ز. Fang, Y. استفاده از فناوری‌های GPU و رشته POSIX در پردازش داده‌های تصویر سنجش از راه دور. در مجموعه مقالات نوزدهمین کنفرانس بین المللی ژئوانفورماتیک 2011، شانگهای، چین، 24-26 ژوئن 2011; صص 1-6.
آهنگ، دبلیو. یو، اس. وانگ، ال. ژانگ، دبلیو. لیو، دی. زمان‌بندی وظایف پردازش گسترده داده‌های مکانی در مراکز داده توزیع‌شده: چه چیزی جدید است؟ در مجموعه مقالات 2011 IEEE هفدهمین کنفرانس بین المللی سیستم های موازی و توزیع شده، تاینان، تایوان، 7-9 دسامبر 2011. ص 976-981.
زینگ، جی. سیبر، آر. Kalacska، M. چالش‌های تقسیم‌بندی تصویر در داده‌های تصویری سنجش از راه دور بزرگ. ان GIS 2014 ، 20 ، 233-244. [ Google Scholar ] [ CrossRef ]
بویا، ر. Murshed، M. Gridsim: ابزاری برای مدل‌سازی و شبیه‌سازی مدیریت منابع توزیع‌شده و زمان‌بندی برای محاسبات شبکه. CCPE 2002 ، 14 ، 1175-1220. [ Google Scholar ] [ CrossRef ]
ماهسواران، م. علی، س. Siegal، HJ; هنسگن، دی. فروند، تطبیق دینامیک RF و زمان‌بندی یک کلاس از وظایف مستقل بر روی سیستم‌های محاسباتی ناهمگن. در مجموعه مقالات هشتمین کارگاه محاسباتی ناهمگن (HCW’99)، سان خوان، پورتوریکو، 12 آوریل 1999; صص 30-44.
کازانووا، اچ. لگراند، ا. زاگورودنوف، دی. برمن، اف. اکتشافی برای برنامه‌ریزی برنامه‌های جابجایی پارامترها در محیط‌های شبکه. در مجموعه مقالات نهمین کارگاه محاسباتی ناهمگن (HCW’00)، کانکون، مکزیک، 1 مه 2000; صص 349-363.
خانا، جی. ویدیاناتان، ن. کورک، تی. کاتالیورک، یو. ویکوف، پی. سالتز، جی. Sadayappan، P. یک رویکرد مبتنی بر پارتیشن بندی هایپرگراف برای زمان بندی وظایف با I/O به اشتراک گذاشته شده دسته ای. در مجموعه مقالات پنجمین سمپوزیوم بین المللی در محاسبات خوشه ای و شبکه (CCGrid 2005)، کاردیف، انگلستان، 9 تا 12 مه 2005. صص 792-799.
Berge, C. نمودارها و هایپرگرافها ; North-Holland Publishing Company: آمستردام، هلند، 1973. [ Google Scholar ]
کاریپیس، جی. کومار، V. پارتیشن بندی هایپرگراف چندسطحی k-way. VLSI Des. 2000 ، 11 ، 285-300. [ Google Scholar ] [ CrossRef ]
Catalyürek، UV; Aykanat، C. PaToH (ابزار پارتیشن بندی برای هایپرگراف ها). در دایره المعارف محاسبات موازی 2011 ; Springer Science & Business Media: برلین، آلمان، 2011; ص 1479-1487. [ Google Scholar ]
تریفونوویچ، آ. Knottenbelt، WJ Parkway 2.0: ابزار پارتیشن بندی هایپرگراف چند سطحی موازی. در مجموعه مقالات نوزدهمین سمپوزیوم بین المللی علوم کامپیوتر و اطلاعات (ISCIS 2004)، کمر-آنتالیا، ترکیه، 27-29 اکتبر 2004; صص 789-800.
آلپرت، سی جی; Kahng، AB جهت‌های اخیر در پارتیشن‌بندی فهرست شبکه: یک نظرسنجی. یکپارچه سازی VLSI J. 1995 ، 19 ، 1-81. [ Google Scholar ] [ CrossRef ]
کاریپیس، جی. آگاروال، آر. کومار، وی. Shekhar, S. پارتیشن بندی هایپرگراف چندسطحی: کاربردها در حوزه VLSI. IEEE Trans. ادغام در مقیاس بسیار بزرگ. (VLSI) سیستم 1999 ، 7 ، 69-79. [ Google Scholar ] [ CrossRef ]
مبشر، ب. جین، ن. هان، ای اچ. Srivastava, J. Web Mining: Pattern Discovery from the World Wide Web Transactions . گزارش فنی TR96-050; گروه علوم کامپیوتر، دانشگاه مینه‌سوتا: مینیاپولیس، MN، ایالات متحده آمریکا، 1996. [ Google Scholar ]
دمیر، ای. ایکانات، سی. کامبازوغلو، BB خوشه‌بندی شبکه‌های فضایی برای پردازش پرس و جوی کل: یک رویکرد ابرگراف. Inf. سیستم 2008 ، 33 ، 1-17. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
Catalyürek، UV; Aykanat، C. تجزیه مبتنی بر پارتیشن بندی هایپرگراف برای ضرب بردار ماتریس پراکنده موازی. IEEE Trans. توزیع موازی سیستم 1999 ، 10 ، 673-693. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
کامبازاوغلو، بی بی. Aykanat، C. مدل‌های نگاشت مجدد مبتنی بر پارتیشن‌بندی هایپرگراف برای رندر حجم مستقیم تصویر-فضا-موازی شبکه‌های بدون ساختار. IEEE Trans. توزیع موازی سیستم 2007 ، 18 ، 3-16. [ Google Scholar ] [ CrossRef ]
کایا، ک. Aykanat، C. اکتشافی مبتنی بر بهبود تکراری برای زمان‌بندی تطبیقی وظایف اشتراک‌گذاری فایل‌ها در محیط‌های ناهمگن master-slave. IEEE Trans. توزیع موازی سیستم 2006 ، 17 ، 883-896. [ Google Scholar ] [ CrossRef ]
دومبویا، مگابایت؛ کامسو فوگم، بی. کنفک، اچ. معناشناسی استدلال و ویژگی های نمودار. Inf. روند. مدیریت 2016 ، 52 ، 319-325. [ Google Scholar ] [ CrossRef ]
کامسو فوگم، بی. Tchuenté-Foguem، G. فوگم، سی. عملیات گراف مفهومی برای استدلال بصری رسمی در حوزه پزشکی. IRBM 2014 ، 35 ، 262-270. [ Google Scholar ] [ CrossRef ]
Kamsu-Foguem، B. پشتیبانی مبتنی بر دانش در آزمایش های غیر مخرب برای نظارت بر سلامت سازه های هواپیما. Adv. مهندس Inf. 2012 ، 26 ، 859-869. [ Google Scholar ] [ CrossRef ]
کوثر، ت. بالمن، ام. پارادایم جدید: زمان‌بندی آگاهانه از داده در محاسبات شبکه. آینده. ژنر. محاسبه کنید. سیستم 2009 ، 25 ، 406-413. [ Google Scholar ] [ CrossRef ]
Caíno-Lores، S. Carretero، J. نظرسنجی در مورد تکنیک های داده محور و آگاه از داده برای زیرساخت های مقیاس بزرگ. آکادمی جهانی علمی مهندس تکنولوژی بین المللی جی. کامپیوتر. برق خودکار. ادامه Inf. مهندس 2016 ، 10 ، 459-465. [ Google Scholar ]
محمد، HH; Epema، DH ارزیابی پردازشگر نزدیک به فایل و سیاست تخصیص مشترک داده در چند خوشه. در مجموعه مقالات کنفرانس بین المللی IEEE در مورد محاسبات خوشه ای 2004، لس آلامیتوس، کالیفرنیا، ایالات متحده آمریکا، 20-23 سپتامبر 2004.
ژانگ، YF; تیان، YC; فیج، سی. کلی، دبلیو. زمان‌بندی کار آگاه از داده برای مشکلات مقایسه همه به همه در سیستم‌های توزیع ناهمگن. J. توزیع موازی. محاسبه کنید. 2016 ، 93 ، 87-101. [ Google Scholar ] [ CrossRef ]
Szmajduch، M. Kołodziej، J. برنامه ریزی آگاهانه از داده در سیستم های ناهمگن عظیم. در مجموعه مقالات بیست و نهمین کنفرانس اروپایی مدلسازی و شبیه سازی ECMS 2015، وارنا، بلغارستان، 26-29 مه 2015. صص 608-614.
دا سیلوا، FA; Senger, H. محدودیت‌های مقیاس‌پذیری برنامه‌های Bag-of-Tasks که بر روی پلتفرم‌های سلسله مراتبی اجرا می‌شوند. J. توزیع موازی. محاسبه کنید. 2011 ، 71 ، 788-801. [ Google Scholar ] [ CrossRef ]
گوان، کیو. Clarke، KC یک برنامه آزمایشی کتابخانه برنامه نویسی برنامه نویسی پردازش شطرنجی موازی همه منظوره با استفاده از یک مدل اتوماتای سلولی جغرافیایی. بین المللی جی. جئوگر. Inf. علمی 2010 ، 24 ، 695-722. [ Google Scholar ] [ CrossRef ]
موتوولو، ن. لیو، جی. Soe, NL; ونوگوپال، اس. سولیستو، ا. Buyya, R. یک زمان‌بندی مبتنی بر گروه‌بندی مشاغل پویا برای استقرار برنامه‌های کاربردی با وظایف دقیق در شبکه‌های جهانی. در مجموعه مقالات سومین کارگاه استرالیایی در محاسبات شبکه و تحقیقات الکترونیکی (AusGrid 2005)، نیوکاسل، استرالیا، 30 ژانویه تا 4 فوریه 2005. ص 41-48.
گوان، ایکس. وو، اچ. استفاده از قدرت پلتفرم‌های چند هسته‌ای برای پردازش داده‌های مکانی در مقیاس بزرگ: نمونه‌ای از تولید DEM از ابرهای عظیم نقطه LiDAR است. محاسبه کنید. Geosci. 2010 ، 36 ، 1276-1282. [ Google Scholar ] [ CrossRef ]
تریفونوویچ، آ. Knottenbelt، WJ الگوریتم های چند سطحی موازی برای پارتیشن بندی هایپرگراف. J. توزیع موازی. محاسبه کنید. 2008 ، 68 ، 563-581. [ Google Scholar ] [ CrossRef ]

شکل 1. یک سناریوی محاسباتی معمولی با داده فشرده.

شکل 2. تصویری از یک هایپرگراف: نقاط نشان دهنده رئوس هستند، و منحنی های بسته نشان دهنده لبه های بیش از حد هستند.

شکل 3. پلت فرم ناهمگن هدف.

شکل 4. تنظیمات محله معمولی و منظم: ( الف ) محله فون نویمان، ( ب ) محله مور، و ( ج ) محله مور گسترده.

شکل 5. وظایف و فایل ها در الگوریتم همسایگی مور.

شکل 6. مدل زمانبندی کار مبتنی بر هایپرگراف.

شکل 7. نمودار جریان پارتیشن بندی هایپرگراف برای تطبیق وظایف.

شکل 8. مجموعه داده LiDAR شهرستان گیلمر.

شکل 9. رابطه کمی بین اندازه نقاط ورودی و زمان درونیابی IDW.

شکل 10. ارزیابی عملکرد با تعداد وظایف مختلف. ( الف ) Makespan; ( ب ) درصد کاهش ورودی/خروجی.

شکل 11. ارزیابی کارایی با تعداد کارهای مختلف.

جدول 1. تنظیم Slave برای شبیه سازی.

© 2016 توسط نویسندگان؛ دارنده مجوز MDPI، بازل، سوئیس. این مقاله یک مقاله با دسترسی آزاد است که تحت شرایط و ضوابط مجوز Creative Commons Attribution (CC-BY) (http://creativecommons.org/licenses/by/4.0/) توزیع شده است.

;کاربردهای GIS مقالات

درخواست مشاوره

09120049370

8 صبح تا 12 شب