Експеримент Сітка на дієті; Fraunhofer IAO - БЛОГ
Після того, як Всесвітня павутина здійснила революцію в Інтернеті в 90-х роках, ми вже кілька років стикаємось з іншим революційним розвитком: обчислювальні мережі (de.wikipedia.org/wiki/Grid-Computing). У сіткових обчисленнях децентралізовані комп’ютери та обчислювальні кластери об’єднуються у „віртуальний суперкомп’ютер” через Інтернет. Це забезпечує прямий доступ до ресурсів мережі, таких як комп’ютери, пам’яті, наукові прилади та експерименти, програми, дані та датчики.
Починаючи з 2001 року, IAO експлуатує Fraunhofer Resource Grid (www.fhrg.fraunhofer.de) разом із кількома іншими інститутами Fraunhofer. З моменту ініціативи D-Grid (www.d-grid.de/), започаткованої в 2005 році, компанія Fraunhofer IAO також бере участь у різних сферах обчислювальних мереж. Основна увага приділяється покращенню зручності використання послуг, вдосконаленню архітектури безпеки та розробці бізнес-моделей для постачальників ресурсів та послуг.
У цьому контексті ми хотіли б представити вам експериментальний підхід до сітки: LiDiC - полегшені розподілені обчислення. При такому підході створюється "полегшене" сіткове середовище з використанням звичайних браузерів з підтримкою JavaScript. Будь-яка кількість цих браузерів спрямовується на певну URL-адресу, а робочі пакети передаються до браузера за допомогою технологій JavaScript та AJAX. Робочі пакети обробляються браузерами, а результати потім надсилаються назад на сервер.
Великою перевагою цього підходу є те, що він не вимагає встановлення клієнта, так що, на відміну від інших мережевих проектів, таких як SETI @ home або World Community Grid, кожен користувач Інтернету може негайно брати участь у розрахунках. Завдяки легкому підходу можна сказати: LiDiC - це сітчасте середовище на дієті!
На рисунку 1 показана основна структура: майстер завдань створює робочі пакети, які HTTP-сервер розповсюджує серед доступних веб-браузерів. Результати працівників надсилаються назад на сервер, який потім робить їх доступними майстру завдань.
Як можна таку сітку успішно використовувати у повсякденному цифровому житті компаніями та приватними особами? Однією з можливостей було б використовувати його вдома, оскільки в наш час на багатьох комп’ютерах працюють багатоядерні процесори, які не використовуються повною мірою повсякденними офісними програмами. Сучасні браузери підтримують ефективний розподіл відкритих вікон між різними ядрами процесора, а це означає, що кожен співробітник може мати внутрішню сітку компанії, розраховану в одному або декількох вікнах браузера, не впливаючи на продуктивність решти додатків або серфінг в Інтернеті.
Рис. 1
Результатом буде оптимальне використання власних комп’ютерних ресурсів компанії, а через легкий підхід немає необхідності встановлювати клієнтську програму на всіх комп’ютерах співробітників.
Крім того, були поодинокі спроби комерційного використання такої сітки. Прикладом цього є компанія PluralProcessing, яка пропонує операторам веб-сайтів гроші, якщо вони інтегрують аплет Java на свій веб-сайт. Потім за допомогою цього аплету розподілені обчислення виконуються у веб-браузерах відвідувачів сайту.
Підхід, представлений у цій статті, слід розглядати як експеримент. Під час продуктивної експлуатації необхідно обробляти великі навантаження, а також враховувати аспекти синхронізації та безпеки. Крім того, обраний протокол HTTP та обчислення в JavaScript призводять до великих накладних витрат, саме тому підхід може швидко стати неефективним, якщо його застосувати до неправильного домену проблеми. Тим не менше, мережева інфраструктура, що базується на браузері, пропонує спокусливу можливість того, що потенційно кожен комп'ютер з підключенням до Інтернету може внести обчислювальний час у сітку.
Детально про експеримент
Ми вирішили розрахувати найкоротший шлях як завдання для експерименту
між початковим вузлом та будь-яким вузлом у спрямованому графіку (de.wikipedia.org/wiki/Graphentheorie). Як правило, алгоритм Дейкстри [Dijkstra59] використовується для пошуку мінімальної відстані в спрямованому графіку, але його неможливо достатньо розпаралелювати. Ось чому ми здійснили пошук із широтою, запропонований у розмові Google (nl.youtube.com/watch?v=BT-piFBP4fE), в якому паралельність вводиться за допомогою шаблону MapReduce [Dean04].
Рис.2
За допомогою цього алгоритму майстер завдань проходить кілька ітерацій пошуку по ширині, і таким чином визначає загальний оптимум найкоротших шляхів на графіку. Як набір даних ми використовуємо синтезований графік «Малий світ» згідно [Wenzel02] зі 100 000 вузлами та 400 218 спрямованими ребрами (див. Рисунок 2).
[Дейкстра59] Е. В. Дейкстра. Примітка щодо двох задач у зв’язку з графіками. Чисельна математика 1. С. 269–271. 1959 рік.
[Венцель02] Л. Венцель. Наскільки маленький світ. Набір інструментів. 2002 рік.
[Dean04] J. Dean, S. Ghemawat. MapReduce: спрощена обробка даних на великих кластерах. OSDI. 2004 рік.