Файлове за подготовка на изпити/Съображения за съвпадение

1.2.2. Характеристики на паралелизма.

На този етап, следвайки [1], ще характеризираме различни характеристики и видове паралелизъм, които са от съществено значение от гледна точка на намирането на адекватни езикови средства за неговото изразяване. Естествено, в крайна сметка понятието паралелизъм се свързва с едновременността на действията или процесите, извършвани в дискретно време. Широко известните концепции за синхронност и асинхронност на протичащите процеси отразяват допустимите схеми и "граници" на взаимодействието на процесите. Търсенето на модели на абсолютно асинхронни или абсолютно паралелни процеси, въпреки че е неразрешим проблем, въпреки това поставя съвсем естествен и важен за паралелни изчисления проблем за сравняване на изразителната сила на различни подходи, модели и езици, свързани с паралелното програмиране.

Една от важните характеристики на паралелността е начинът, по който се уточнява: явен или неявен.

Първият предполага съществуването на език или определен набор от примитиви, чрез които програмистът описва в програмата паралелно интересуващите го действия. Примитивите parbeginparend, fork-join, инструменти за задаване на паралелни процеси в MPI, PVM и много други подобни софтуерни инструменти за определяне на паралелизъм, накрая, различни модели на процеси (мрежи на Петри, модели на взаимодействие между процеси на Milner и Hoare [34] и др.) .) и т.н. ... - примери за изрично уточняване на паралелизъм.

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

Паралелизмът имплицитно присъства във функционалните езици [5, 6], логика от първи ред, Prolog. Поради факта, че тези езици имат строга детонационна семантика и независима паралелна оперативна семантика (във функционалните езици - тази семантика се осъществява чрез процесите на сгъване и разширяване на дървета [5, 6], в логически формализми и езици - чрез изграждането на паралелни алгоритми за извод [7]) ... Освен това всеки опит да се посочи изрично какво трябва да се изпълнява паралелно в този вид програми изглежда неестествено и освен това почти винаги ще доведе до факта, че много възможности за успоредяване просто ще бъдат загубени.

Очевидно имплицитните начини за отразяване на паралелизма без позоваване на процеса на паралелно изпълнение на програмата имат предимството, че разделят аспектите на програмирането и самата организация на паралелното изпълнение на програмата; програмистът не се нуждае, като например при използване на MPI, на от една страна, за програмиране на функция или алгоритъм, който прилага метод за решаване на проблема. От друга страна, за решаване на друг проблем, как да се организират паралелни процеси на неговото изпълнение.

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

В тази връзка се разграничават видовете паралелизъм: функционален, логичен, паралелизъм на последователни програми, паралелизъм на обектно-ориентирани програми, паралелизъм на процеса.

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

Говорейки за паралелизъм на процеса, имаме предвид различни модели на процесите (мрежи на Петри, модели на Хоаре и Милнър, модели на актьори и др. [8]) Говорейки за паралелизъм на процеса, имаме предвид различни модели процеси () на процеса на промяна просто ще бъдат загубени. Естествено ), в която се изясняват основните понятия, свързани с генерирането и взаимодействието на процесите.

Именно на базата на тези модели са внедрени много езици на процесите (например OCCAM), OS инструменти за организиране на процеси с "нишка" и т.н.

Друг важен в практически смисъл аспект при характеризирането на паралелизма са ограниченията върху „зърнистостта“, за да се изясни кои понятия обикновено се използват: едрозърнест, среден и финозърнест паралелизъм (възможна е и по-подробна скала на диференциация).

Дълбочината на паралелизацията, която беше обсъдена в раздел (1.2.1), изяснява тази концепция. Обикновено крупон - гранулираният паралелизъм се свързва с модулното програмиране, с разработването на сложни софтуерни системи с разнообразни приложения, включително тези, фокусирани върху решаването на изчислителни проблеми. Фино паралелизмът е способността на функционалните и логическите програми.

Финозърнестият паралелизъм е характеристика на аритметичните и логически функционални програми, алгоритмите за извод в логиката и др. Показахме (вж. Раздел 1.2.1), че дълбочината на успоредяване, която формално определя „зърнистостта“ на паралелния алгоритъм, значително влияе коефициентът на ускорение и ефективността на прилагането на паралелни изчисления на самолети [1, 2].

Освен това, решаването на проблема за оптимално управление на натоварването на компютрите (процесорите) на самолета изисква въвеждане на механизми за динамично измерване на дълбочината на успоредяване [1].

Например при изпълнението на функционалния език за програмиране FTPL [5] на клъстери е въведен механизъм за контрол на дълбочината на успоредяване по време на изпълнението на програмата чрез присвояване на рекурсивно дефинирани функции на фрагменти от програмата, които са по-сложни от изчислителна точка на изглед от основните функции.

Освен това, за да може програмистът също да варира „зърното“ на паралелизъм в програмата, на езиците на функционалното и логическото програмиране те въвеждат средства за модулна организация на програмата, насочващи кои нейни фрагменти трябва да бъдат изпълнени в паралелно (виж например системата за паралелно програмиране T [9])

Две по-важни свойства на паралелизма са неговата комутативност или некомутативност [1]. Комутативността предполага, че фрагменти от паралелна програма, готова за изпълнение, могат да бъдат назначени за изпълнение в произволен ред, без да се засяга резултатът. Това не важи за некоммутативния паралелизъм.

Ясно е, че аргументите

(вместо които могат да се заменят други функции) могат да се изчисляват паралелно, като се контролира резултатът на всяка от тях и се сравняват с резултатите от изчисляването на други аргументи.

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

са дефинирани и равни, а стойността

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

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

Типичен пример е условен израз: if

тогава

друго

. Ясно е, че стойността

може да се изчисли едновременно, но стойността

винаги е необходимо и необходимостта от ценности

или

определя се от резултата

. Имайте предвид, че паралелизмът на тези фрагменти не е комутативен. Внедряването на едновременна съвпадение е усложнено от необходимостта от прекъсване на изчисленията, без да се изискват резултати.

Всички паралелни програми могат да бъдат класифицирани в два класа: с ограничен и неограничен паралелизъм [1, 2] (вж. Раздел 1.2.1). За програми от първи клас можете предварително да посочите броя (обикновено най-малкия) компютри на самолета, което е достатъчно, за да се реализират всички възможности за паралелизъм в програмата по време на нейното изпълнение за предварително определен набор от първоначални данни. Това условие не е изпълнено за паралелни програми, класифицирани като програми с неограничен паралелизъм. Примерите за паралелно изчисляване на n!, За успоредно умножение на матрица, разгледани в раздел 1.2.1, принадлежат към класа паралелни програми с неограничен паралелизъм, ако не са наложени ограничения върху n.

За програми от този вид, от практическа гледна точка, често е задача да се постигне определено ниво на паралелизация и ефективно последователно прилагане на паралелизъм на ограничени ресурси на самолета.

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

Анализ, който засяга организационните специфики на паралелизма, като система от взаимодействащи процеси, подчертава неговото синхронно и асинхронно изпълнение. Първият, за разлика от втория, предполага строго уточняване на моментите във времето (или събитията), в които могат да възникнат определени действия по време на изпълнението на паралелна програма. Типичен пример, векторният оператор parbeginparend, поемащ контрол върху неговото завършване след завършване на изпълнението на оператора с максимално време за изпълнение (или всички такива оператори, ако има няколко).

Друга характеристика на паралелизма на процеса е тази, която определя схемата на нейното изпълнение като система от процеси, разпределени в пространството (това, което обикновено се нарича разпределена обработка), или чрез организиране на поточна обработка. В първия случай паралелизмът в [1] се нарича още пространствен. Схемата за обработка на потоци има различни „нюанси“. На първо място, това е прехвърляне в сферата на организиране на изчислителни процеси на схемата за обработка на тръбопровода, използвана дълго време в производството. Известно е, че разбиването на сложен процес на отделни последователно изпълнени малки фази и организиране на обработка на тръбопровод (поток) от създаване на независима единица (устройство, машина и т.н.) .p.), в ограничителния случай е възможно да се увеличи производителността на такава схема за извършване на „работа“ с коефициент k, където k е броят на конвейерни етапи. Освен това, тази схема ви позволява да постигнете най-добрия показател при използването на тръбопроводни ресурси. Конвейерът получи истинското си въплъщение на компютърна основа през 60-те години на миналия век в компютрите STRETCH и BESM-6, където едновременно бяха обработени от 7 до 10 програмни команди. Всеки съвременен компютър (персонален или суперкомпютър, например Cray), с изключение на командния, изпълнява скаларни и/или векторни конвейери за извършване на аритметични операции.

Тези тръбопроводи обаче имат свои собствени основни ограничения. Така че, поради настоящите обстоятелства, изпълнението на, например, операцията за добавяне на реални числа се състои само от 5 фази: сравнение на поръчки, смяна на мантиса, самото добавяне, нормализиране и не може да бъде увеличено, за да се увеличи производителността. В допълнение, контурите на конвейерите, използвани в компютрите, обикновено са линейни (трябва да се отбележи, че компютрите Cray използват паралелни конвейери, които могат да си взаимодействат, прехвърляйки данни).

Реалните системи за обработка на информация обикновено са многонишкови, като правило, с опашки на входовете на техните възли и сложни връзки, които определят „посоката“ на движение на данните: един към много, много към един възел и т.н.

Тази схема за обработка на данни се използва все по-често при паралелно програмиране, описание на разпределени системи и процеси [10].

В графично-схематичния език за програмиране на потока, реализиран в работата [11], е възможно да се изграждат всякакви схеми за обработка на поточно предаване (многонишкови схеми с опашки от данни на входовете на модула) и поради факта, че модулите си взаимодействат само на базата на данни, независимите от информация модули се откриват лесно от липсата на връзки между тях.

Нещо повече, често възникват задачи, зависими от нишка, например изчисляване

, където елементи

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

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