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




ИмеНеобходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат
Дата на преобразуване12.06.2013
Размер72.42 Kb.
ТипАнализ
източникhttp://www.tu-varna.bg/tu-varnaknt/images/tutorials/pik/word_styles.doc
УВОД


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

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


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.

Свързани:

Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconПатенти за изобретения
Под изобретение най-често се разбира някаква новост, създадена в областта на науката и техниката. Но – не всички интелектуални продукти...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconИ к о номическиунверситет варн а
Финанси на предприятието, Теория на счетоводството и Счетоводство на предприятието, Висша математика и др. Дисциплината дава на студентите...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconИ к о номическиунверситет варн а
Финанси на предприятието, Теория на счетоводството и Счетоводство на предприятието, Висша математика и др. Дисциплината дава на студентите...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconИ к о номическиунверситет варн а
Финанси на предприятието, Теория на счетоводството и Счетоводство на предприятието, Висша математика и др. Дисциплината дава на студентите...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconИ к о номическиунверситет варн а
Финанси на предприятието, Теория на счетоводството и Счетоводство на предприятието, Висша математика и др. Дисциплината дава на студентите...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconИнтерактивни методи за формиране на екологична култура
Днес степента на промяна, но не в положителен аспект, е огромна. Науката разви свой свят чрез сложни изчисления и монументални абстракции,...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconХърбърт еделсбрунен и Ернст П. Муке Често, данните в начнуте изчисления са в абстрактния си вид крайно точково множество в пространството и понякога е полезно
Представен е алгоритъм, който конструира цялата фамилия от форми за едно дадено множество с размерност n със сложност O(n2), в най-лошия...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconВ. "Дневен труд" Бандит без маска ограби „Токуда" | 25. 01. 2012 02: 12 | Труд | стр. 10
Апаш ограби част от дневния оборот на столичната частна болница „Токуда" малко преди 20 ч в понеделник. Първоначално се появи информацията,...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconВръща поредния номер на текущата дата. Поредното число е обединяващ дата и астрономическото време код, използван за изчисления с дати и часове. Можете да
Датите се съхраняват като поредни числа, така че да може да се използват в изчисления. По подразбиране 31 декември 1899 има пореден...
Необходимостта от паралелни изчисления възниква във всички области на науката и техниката. Настоящият труд е насочен към изчисления, които могат да бъдат iconВ. "Дневен труд" Държавата отряза трима болни от помощ
Представяте ли си на нас, инвалидите, да вземат данък!? С хора с моята съдба сме правили изчисления, че от инвалидите държавата е...
Поставете бутон на вашия сайт:
Документация


Базата данни е защитена от авторски права ©bgconv.com 2012
прилага по отношение на администрацията
Документация
Дом