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



Дата17.11.2017
Размер72.42 Kb.
Размер72.42 Kb.

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

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


I ГЛАВА. ПАРАЛЕЛНИ ЗАДАЧИ И ИЗЧИСЛЕНИЯ
Проектирането на алгоритъм за паралелна реализация на дадена задача преминава през следните основни етапи [39]:

  • Разделяне на задачата на подзадачи (Partitioning) декомпозиране на общата за решаване задача на подзадачи с възможност за паралелна реализация;

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

  • Намиране на съответствие (Mapping)назначаване на процесор (или процесори) за изпълнение на задача (или задачи);

За разглеждания клас задачи е характерно, че всяка задача може да бъде разделена на напълно независими части, всяка от които може да бъде изпълнена от отделен процесор и всички части могат да бъдат изпълнявани едновременно. В англоезичната литература за такива задачи е въведен терминът „embarrassingly parallel” [104, стр. 82-106]. Разделянето на такива задачи не изисква специални техники или алгоритми за паралелно решаване. Между отделните изчислителни подзадачи (процеси) няма необходимост от комуникация по време на изпълнение, поради което такива паралелни задачи се представят чрез напълно несвързан граф (фиг. 1.1). Всички подзадачи (процеси) се изпълняват с различни (или еднакви) входни данни и за получаването на резултат не е необходимо никоя подзадача да използва резултати от други подзaдачи.

1. Стратегии за формиране на паралелни задачи

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


1.1. Разделяне (partitioning)

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


1.2. Стратегия „Разделяй и владей”

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

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

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


2.2. Алгоритми за планиране на задачи при ограничени ресурси

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

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

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


2.2.2. Евристични методи

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


2.3. Приложение на генетични алгоритми в планирането

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


3. Технологии за управление на паралелни изчисления в разпределена среда

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


3.1. Клъстерен модел за реализация на паралелни задачи

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

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

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


3.2.2. Инструментално средство GLOBUS Toolkit за управление на GRID среда

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


II ГЛАВА. ДЕКОМПОЗИРАНЕ НА ЗАДАЧИ НА НЕЗАВИСИМИ ПОДЗАДАЧИ, АЛГОРИТМИ ЗА ПЛАНИРАНЕ НА ИЗПЪЛНЕНИЕТО В РАЗПРЕДЕЛЕНА СРЕДА
1. Декомпозиране на задача на независими подзадачи
1.1. Разделяне на задачата по данни (паралелизъм на ниво данни)

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


1.2. Разделяне на задача на функции (паралелизъм на ниво функции – функционална декомпозиция)

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



2. Планиране на изпълнението на паралелни задачи при ограничени ресурси
2.1. Подход с отместване на задачи по оста на времето

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


2.2. Формално описание на задачата за планиране при ограничени ресурси

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

Планира се изпълнение на 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.


Сподели с приятели:


©zdrasti.info 2017
отнасят до администрацията

    Начална страница