ЗНАЙ ИНТУИТ, Лекция, Паралелни методи върху графики
10.3. Оптимален проблем за разделяне на графики
Проблемът за оптималното разделяне на графове е един от често срещаните проблеми в различни научни изследвания, използващи паралелни изчисления. Пример за това са проблеми с обработката на данни, при които изчислителните домейни се апроксимират от двуизмерни или триизмерни изчислителни мрежи. Получаването на резултати в такива задачи се свежда, като правило, до изпълнението на определени процедури за обработка за всеки елемент (възел) на мрежата. В този случай в хода на изчисленията между съседни мрежови елементи, прехвърлянето на резултатите от обработката и т.н. Ефективното решение на такива проблеми на мултипроцесорни системи с разпределена памет предполага разделянето на мрежата между процесорите по такъв начин, че приблизително еднакъв брой мрежови елементи да бъдат разпределени за всеки от процесорите и междупроцесорните комуникации, необходими за осъществяване на обмен на информация между съседните елементи са минимални. На фиг. 10.9 показва пример за неправилна мрежа, разделена на 4 части (различните части на подразделението на мрежата са маркирани в тъмен цвят с различна интензивност).
Очевидно подобни проблеми на мрежовото разделяне между процесорите могат да бъдат сведени до проблема с оптималното разделяне на графи. Този подход е целесъобразен, тъй като представянето на изчислителния модел под формата на графика улеснява решаването на проблемите със съхранението на обработваните данни и предоставя възможност за използване на стандартни алгоритми за обработка на графики .
За да се представи мрежата под формата на графика, всеки мрежов елемент може да бъде свързан с връх на графика, а дъгите на графиката могат да се използват, за да отразят свойството близост на мрежовите елементи (например, дефинирайте дъги между върховете на графика, ако и само ако съответните елементи на оригиналната мрежа са съседни). При този подход, например, за мрежата на фиг. 10.9, графиката, показана на фиг. 10.10.
Допълнителна информация по проблема с разделянето на графики може да бъде получена, например, в [[67]].
Проблемът за оптималното разделяне на графовете сам по себе си може да бъде обект на паралелизиране. Това е необходимо в случаите, когато изчислителната мощност и количеството памет с произволен достъп на конвенционалните компютри не са достатъчни за ефективно решаване на проблема. Паралелни алгоритми за разделяне на графики са разгледани в много научни трудове: [[20], [38], [44], [48], [49], [65], [74]].
10.3.1. Поставяне на проблема за оптималното разделяне на графика
Нека бъде дадена претеглена неориентирана графика G = (V, E), на всеки връх и на всеки ръб на която е присвоена тежест. Проблемът за оптималното разделяне на графове се състои в разделяне на върховете му на несъединени подмножества с най-близките общи тегла на върховете и минималното общо тегло на ребрата, преминаващи между получените подмножества на върховете.
Трябва да се отбележи, че посочените критерии за разделяне на графика може да са несъвместими - равновесието на подмножествата на върховете може да не съответства на минималните тегла на граничните ръбове и обратно. В повечето случаи е необходимо да се избере едно или друго компромисно решение. Така че, в случай на нисък дял на комуникациите, може да бъде ефективно да се оптимизира теглото на ръбовете само сред решенията, които осигуряват оптимално разделяне на множеството върхове по тегло.