Задача на подзадачи с възможност за паралелна реализация; Анализ на необходимостта от предаване на съобщения (комуникация) между задачите

Такива изчисления са характерни за приложението на числените методи, които са доказали своята ефективност при решаване на широк диапазон от задачи. С помощта на компютри се моделират и симулират сложни и трудоемки научни и инженерни задачи, диагностицират се заболявания, контролира се техническо оборудване, прогнозира се времето, управляват се капитали.

• 
  Разделяне на задачата на подзадачи (Partitioning) – декомпозиране на общата за решаване задача на подзадачи с възможност за паралелна реализация;
  
• 
  Анализ на необходимостта от предаване на съобщения (комуникация) между задачите (Communication Analysis) – анализ на съществуващи зависимости по данни между задачите;
  
• 
  Намиране на съответствие (Mapping) – назначаване на процесор (или процесори) за изпълнение на задача (или задачи);
  

Две фундаментални стратегии, които се използват за декомпозиране на задачи при проектиране на паралелни алгоритми са разделяне (partitioning) и “разделяй и владей” (divide and conquer) [104, стр. 107-138].

Тази стратегия стои в основата на всяка паралелна реализация. При нея задачата се разделя на части. Всяка част се изчислява независимо от останалите. В повечето случаи се налага обединяване на резултатите, получени от отделните части за получаване на краен резултат. Разделянето може да бъде приложено върху данните на програмата (паралелизъм на ниво данни). Данните се разделят на части, които се обработват конкурентно от процесорите. Това разделяне се нарича разделяне по данни (data partitioning) или декомпозиция на домейн (domain decomposition). Разделянето на задачата може да бъде извършено и с функциите на програмата (паралелизъм на ниво задача). При него програмата се разделя на независими функции, които се изпълняват конкурентно. Това разделяне се нарича функционална декомпозиция (functional decomposition).

При този подход задачата се разделя на подзадачи, които са от същия вид както основната задача. Разделянето на подзадачи обикновено се реализира чрез рекурсия, която се прилага докато всяка подзадача не може да се раздели на по-малки подзадачи. Получените малки подзадачи се изпълняват, а резултатите от тяхното изпълнение се комбинират.

При рекурсивното разделяне на задача на подзадачи се формира двоично дърво. Това дърво се обхожда отгоре надолу при рекурсивните извиквания и отдолу нагоре при рекурсивните връщания. Фиг. 1.6 показва пълно двоично дърво, в което крайните подзадачи са разположени в листата на дървото, а главната (началната) задача е разположена във върха (корена) на дървото. Процесът в корена на дървото разделя задачата първоначално на две подзадачи. Всяка от тези подзадачи се разделя на още две и т.н. до достигане на листата на дървото. Там се изпълняват основните операции на задачата.
2. Планиране на изпълнението на паралелни задачи
2.1. Основни понятия в теорията на планиране

В зависимост от това дали задачите могат да бъдат дефинирани предварително се различават два подхода за формиране на паралелни задачи [35].

Най-общо задачата за планиране на задачи при ограничени ресурси се описва по следния начин [101]:

Дадени са множество от задачи за изпълнение, ресурси, необходими за изпълнението на задачите, ограничителни условия, които трябва да бъдат удовлетворени при изпълнението и функции (критерии), чрез които се оценява качеството на планирането (т.е. на всеки получен план за изпълнение). Задачата се свежда до намиране на времеви момент за стартиране на всяка от задачите върху съответен ресурс, така че дефинираните ограничителни условия да бъдат удовлетворени и да бъде постигната минимална (или максимална стойност) на целевата функция.
2.2.1. Методи и алгоритми за намиране на точно решение

Тези алгоритми гарантирано намират точно (оптимално) решение на задачата за планиране, но са практически неприложими при нарастване на броя на задачите за планиране или на поставените ограничителни условия.

Докато методите за получаване на точно решение гарантирано намират точно (оптимално) решение (ако такова съществува), евристичните методи намират оптимално решение понякога, а най-често намират просто „добро” решение. В повечето случаи евристичните методи изискват много по-малко време и/или пространство за намиране на решение в сравнение с точните методи. Тези методи използват правила, които показват какво решение трябва да бъде взето в определена ситуация.

Едно от най-ранно предложените приложения на генетични алгоритми в задачите за планиране е публикувано от Lawrence Davis, където се отбелязва, че стохастичните методи за търсене са подходящи за използване в голямо пространство от решения [28]. Oграниченията в много задачи за планиране често са твърде трудни (или дори невъзможни) за представяне чрез други традиционни техники. Освен това генетичните алгоритми имат възможност за избягване на попадането в локален екстремум на целевата функция, което е характерно за детерминираните методи, използвани например в системите, базирани на знания.

Според търсения ефект от използването на паралелни изчисления технологиите за управление на паралелни изчисления най-общо се разделят на два класа.

Клъстерът представлява система с разпределена памет, съставена от свързани работни станции, които работят върху обща задача и изглеждат за потребителите като единствен компютър [16].

Клъстерните системи предлагат добра алтернатива на скъпите суперкомпютри и специализирани паралелни компютърни системи. Те имат следните основни предимства.
3.2. Възможности на GRID технологии за реализация на паралелни изчисления
3.2.1. Кратко определение за GRID

GRID е изчислителна инфраструктура, която осигурява достъп до изчислителни ресурси и данни, разпределени по цял свят в т.нар. виртуални организации. Тя използва Интернет като среда за пренос и се явява надстройка над нея с по-тясно специализирана цел. Наименованието GRID (мрежа – в т.ч. електическа, решетка) е избрано по аналогия с електрическата мрежа.

Както клъстерната система, организирана в локална компютърна мрежа, така и GRID средата работи под управление на специализирана програмна система (middleware). Тази система се грижи за управление на задачи, данни и ресурси, предоставяне на услуги, планиране на изпълнението. Особено важна функционалност на системите за управление на GRID средата е осигуряване на високо ниво на сигурност при използването на услуги в GRID.

Разделяне на типична изчислителна задача на независими подзадачи и реализация на паралелизъм на ниво данни са демонстрирани чрез базов пример за оценяване на риска на финансов инструмент по Монте Карло метод.

Паралелизъм на функционално ниво може да бъде демонстриран чрез декомпозиция на задача на независими подзадачи при управление и оценяване на финансови фондове.

Идеята на предлагания подход е отлагане на стартирането на изчислителните задачи с цел предотвратяване на конкурентен достъп до източника на данни. Симулират се сценарии с отместване на задачите една спрямо друга. Целта е да се намери такъв сценарий (план) на изпълнение, при който във всеки времеви интервал само една задача да има достъп до общия източник на данни.

За синтезиране и анализ на алгоритъм за планиране е необходимо формално описание на решаваната задача.

Планира се изпълнение на n задачи в среда от m свързани еднакви компютри.
3. Доказателство за NP-трудност чрез свеждане до минимално оцветяване на граф

Формулираната в т.2.2. задача може да се сведе до задача за минимално оцветяване на върховете на граф, с което да се докаже нейната NP-трудност.

1. 
   Aarts, E., Laarhoven, al. Job Shop Scheduling by Simulated Annealing. Technical Report OS-R8809, Center for mathematics and computer science, Amsterdam, 1988.
   
2. 
   Abdelkhalek, A., A. Bilas. Parallelization, optimization, and performance analysis of portfolio choice models. in Proceedings of the 30th International Conference on Parallel Processing, Valencia, Spain, September 3–7, 2001.
   
3. 
   Adams, J., E. Balas, D. Zawack. The shifting bottleneck procedure for job shop scheduling. Management Science 34, 1988, pp. 391-401.
   
4. 
   Alba, E. (ed.). Parallel Metaheuristics. Parallel and Distributed Computing. Computing. Wiley, Hoboken, New Jersey, USA, 2005.
   
5. 
   Anderson, T. E., D. E. Culler, D. Patterson. A Case for NOW (Networks of Workstations). IEEE Micro, Vol. 15, No. 1 (Feb.), 1995, pp. 54-64.
   
6. 
   Applegate, D., W. Cook. A computational study of the job-shop scheduling instance. ORSA Journal on Computing 3, 149-156, 1991.
   
7. 
   Bagchi, S., S. Uckum, al. Exploring Problem-Specific Recombination Operators for Job shop Scheduling. Proceedings of the Fifth International Conference on Genetic Algorithms, 1991.
   
8. 
   Barnes, J. E., P. Hut. A Hierarchical O(NlogN) Force Calculation Algorithm. Nature, vol. 324, No. 4 (December), 1986, pp. 446 – 449.
   
9. 
   Basney, J., M. Livny. Deploying a high throughput computing cluster. In High Performance Cluster Computing: Architectures and Systems, Vol. 1, Prentice Hall PTR, 1999.
   
10. 
    Benkner, S., L. Halada, M. Lucka. Parallelization strategies of three-stage stochastic program based on the BQ method. In Parallel Numerics’02, Theory and Applications, 2002, pp. 77–86.