Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Розбиття графа



Приклад розбиття паралельної граф-схеми алгоритму логічного управління. У складі блоків, позначених різними кольорами, немає паралельних вершин

Розбиття графа на подграф ( англ. Graph partition ) (Іноді в літературі також вживається термін розрізання графа [1]) - представлення вихідного графа G = \ left \ langle A, V \ right \ rangle у вигляді безлічі підмножин вершин \ Mathrm {Sep} ~ A = \ left \ {A_1, A_2, ..., A_n \ right \}, A_i \ subseteq V за певними правилами. Зазвичай за умовами задачі потрібно, щоб \ Bigcup_ {i = 1} ^ {n} A_i = A , Тобто всі вершини вихідного графа повинні бути розподілені по підмножини, причому A_i \ neq \ varnothing . Зазвичай також додатково вводиться вимога ортогональності розбиття: \ Forall i \ neq j ~ A_i \ cap A_j = \ varnothing , Тобто одна і та ж вершина не може входити до складу різних підмножин. Іноді з безлічі можливих розбиттів потрібно вибрати одне, яке задовольняє обмеженням і є оптимальним (або субоптимальних) по позначеному умовою, або довести, що шукане розбиття не існує (обмеження суперечливі). Завдання розбиття графа відноситься до класу NP-повних, верхня оцінка числа розбиття визначається числом Белла, однак при цьому зазвичай не всі можливі розбиття є коректними (не порушують обмежень), тобто оцінка є завищеною. При значеннях числа вершин графа N = \ left | A \ right | більше 15-20 отримання оптимальних розбиття як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальних рішеннями, отриманими з використанням евристичних алгоритмів.

Необхідність отримання розбиття виникає при вирішенні ряду завдань:

  1. Завдання розмальовки графа - кожне безліч вершин V i складається з вершин одного кольору, причому вершини одного кольору не мають спільних інцидентних ребер. Зазвичай цікавить пошук мінімальної розмальовки, що в загальному випадку є завданням класу NP (критерій оптимальності - n \ rightarrow \ min ).
  2. Завдання визначення числа і складу компонент зв'язності графа.
  3. При проектуванні топології локальної мережі її розбиття на широкомовні домени визначається вимогами продуктивності (критерій оптимальності - обсяг переданого міждоменної трафіку при використанні різних серверів і мережевих служб (доступ до файловим серварам, службам DHCP, WINS, DNS і т. д.), обмеження - число портів і пропускна здатність комутаторів, маршрутизаторів та каналів зв'язку, а також вартість).
  4. У задачі трасування міжз'єднань друкованих плат або мікросхем необхідно розбиття вихідної схеми на шари (кожен з яких представляє собою планарний граф). Критерії оптимальності - мінімальне число шарів і міжз'єднань (фактично, собівартість виробництва), обмеження - габаритні розміри і вимоги термічної та електромагнітної сумісності електронних компонентів. [2]
  5. У задачі розбиття граф-схеми алгоритму на блоки з метою реалізації на багатопроцесорні системи або логічному мультіконтроллером. Критерії оптимальності - мінімальне число блоків, мінімальні ступеня дублювання сигналів мікрооперацій і логічних умов, мінімальне число міжмодульних передач управління, мінімальний трафік міжмодульних передач управління і даних; обмеження диктуються використовуваної елементної бази. [3] [4] [5] [6]
  6. Подання графа у вигляді ярусно-паралельної форми або граф-схеми алгоритму у вигляді безлічі перетинів (безлічі вершин у складі перетинів можуть бути неортогональних).
  7. Розбиття графа алгоритму на непересічні подграф з подальшим їх розміщенням у процесорних елементах або елементах у складі ПЛІС при реалізації конвеєрної обробки даних (балансування навантаження). [7] [8]

Методи розбиття графа [9]

  • Покоординатного розбиття
  • Рекурсивний інерційний метод поділу навпіл
  • Розподіл мережі з використанням кривих Пеано
  • Ділення з урахуванням зв'язності (по суті, пошук в ширину)
  • Алгоритм Керніган - Ліна (англ.)

Примітки

  1. Євстигнєєв В. А. Застосування теорії графів в програмуванні. М.: Наука, 1985. 352 с.
  2. Курейчик В. М., Глушань В. М., Щербаков Л. І. Комбінаторні апаратні моделі та алгоритми в САПР. М.: Радіо і зв'язок, 1990. 216 с.
  3. Баранов С. І., Журавіна Л. Н., Піщанський В. А. Метод подання паралельних граф-схем алгоритмів сукупностями послідовних граф-схем / / Автоматика і обчислювальна техніка. 1984. № 5. С. 74-81.
  4. Зотов І. В., Титов В. С., Колосков В. А. [и др.] Організація і синтез мікропрограмних мультімікроконтроллеров. Курськ: вид-во "Курськ", 1999. 368 с. ISBN 5-7277-0253-4
  5. Ватутін Е. І., Зотов І. В., Титов В. С. [и др.] Комбінаторно-логічні задачі синтезу розбиття паралельних алгоритмів логічного управлени при проектуванні логічних мультіконтроллером. Курськ, вид-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
  6. Ватутін Е.І. Проектування логічних мультіконтроллером. Синтез розбиття паралельних граф-схем алгоритмів. Saarbrucken: Lambert Academic Publishing, 2011 р. 292 с. ISBN 978-3-8433-1728-3
  7. Каляєв І. А., Левін І. І., Семерніков Е. А., Шмойлов В. І. реформуються мультіконвейерние обчислювальні структури: 2-е видання. Ростов н / Д: вид-во ЮНЦ РАН, 2009. 344 с. ISBN 978-5-902982-61-6
  8. Каляєв І. А., Левін І. І. реформуються мультіконвейерние обчислювальні системи для вирішення потокових задач обробки інформації та управління / / Пленарні доповіді 5-ій міжнародній конференції "Паралельні обчислення і завдання управління" (PACO'10). М.: ІПУ РАН, 2010 р. С. 23-37.
  9. INTUIT.ru: Курс: Теорія і практика ..: Лекція № 10: Паралельні методи на графах - www.intuit.ru/department/calculate/paralltp/class/free/10/5.html

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Розбиття
Розбиття числа
Розбиття множини
Розбиття одиниці
Інваріант графа
Доповнення графа
Розгортка графа
Компонента зв'язності графа
Притчі графа дифузора
© Усі права захищені
написати до нас
Рейтинг@Mail.ru