Модифициране на цикли за подобряване на паралелната производителност на данни, софтуер Intel®
Циклите обикновено представляват по-голямата част от изчисленията в приложенията за паралелна обработка на данни, така че оптимизирането на цикъла има пряко въздействие върху цялостната производителност на приложението. В случай на вложени цикли, производителността е пряко зависима от степента на разделяне (подробност) на изчисленията по нишки. Трансформации като разлагане на вложен цикъл и обединение могат значително да опростят паралелизирането и да повишат неговата ефективност.
Описание на проблема
Оптимизирането на цикъла е важен фактор за подобряване на производителността на приложенията за паралелна обработка. Оптимизации като обединение, пермутация и разгръщане на цикъл обикновено се използват за подобряване на разделянето, балансирането на натоварването и ефективната локализация на данните, като същевременно налагат малко синхронизиране и други разходи за едновременност. Основното правило е, че циклите с голям брой итерации са най-подходящи за паралелизиране. Големият брой итерации подобрява баланса на натоварването, като има повече задачи за разпределяне между нишките. Трябва също така да имате предвид количеството работа, извършена в една итерация. Освен ако не е посочено друго в статията, ние приемаме, че обемът на изчисленията във всяка итерация на цикъла е (приблизително) еднакъв за всички итерации на дадения цикъл.
Помислете за пример за оптимизация на цикъл с помощта на директивата OpenMP* for, използвана за разпределяне на работа, както е показано в примера по-долу. В този случай малък брой итерации води до дисбаланс на натоварването, ако итерациите на цикъла са разпределени между четири нишки.Ако една итерация отнема само няколко милисекунди, такава неравномерност няма да доведе до сериозни последствия. Въпреки това, ако всяка итерация отнема около час, тогава три нишки ще бъдат неактивни за 60 минути, докато чакат четвъртата да завърши. Сравнете това със ситуацията, при която подобен цикъл включва 1003 едночасови итерации, изпълнявани на четири нишки. В този случай стоенето без работа за един час след десет дни екзекуция не е от значение.
Препоръки
В случай на много вложени цикли, при паралелизиране е най-добре да изберете най-външния и в същото време безопасен за паралелизиране цикъл. Този подход в повечето случаи ви позволява да получите най-високата степен на разделяне. Ако равномерното разделяне не е възможно (външният цикъл има твърде малко итерации), по-подходящ кандидат за паралелизиране може да бъде по-голям вътрешен цикъл с голям брой итерации. Като пример, разгледайте следния код с четири вложени цикъла:
Ако броят на нишките не е равен на пет, тогава успоредяването на външния цикъл ще доведе до неравномерно натоварване и празни нишки. Наказанието за производителност може да бъде още по-лошо, ако размерите на масивите imx, jmx и kmx са много големи. В този случай предпочитаният вариант би бил паралелизиране на един от вътрешните цикли. Използването на имплицитни бариери в края на конструкцията за разпределение на работата трябва да бъде изоставено, освен ако не е трудно. Всички директиви на OpenMP за разпределяне на работа (за, секции, единични) имат имплицитна бариера в края на структурирания блок. В този момент всички нишки трябва да се срещнат за синхронизиране, преди изпълнението на кода да може да продължи. В някои случаи такива бариери не са необходими и могатвлияят негативно на производителността. Можете да използвате опцията OpenMP сега, за да деактивирате бариерите, както в примера по-долу:
Тъй като изчисленията в най-вътрешния цикъл са независими едно от друго, няма причина нишките да чакат за синхронизиране при имплицитна бариера, преди да преминат към следващата итерация k. Ако количеството работа варира между итерациите, опцията nowait ще позволи на нишките да продължат да вършат полезна работа, без да спират на неявна бариерна точка.
Ако даден цикъл има зависимост, пренасяна от цикъла, която не позволява на цикъла да работи паралелно, можете да разделите тялото на цикъла на отделни по-малки цикли, които ще работят паралелно. Това разделяне на цикъл на две или повече се нарича "разлагане на цикъл". В примера по-долу използваме декомпозиция на цикъл на зависимост, за да създадем множество цикли, които могат да работят паралелно:
Присвояването на стойности на елементите на масива a се извършва независимо, независимо от знака на съответните елементи на масива b. Всяко присвояване на елемент от масив b е независимо от другите, но зависи от това дали присвояването на необходимия елемент от масив a е завършено. Когато използвате тази версия на кода, цикълът, обсъден по-горе, не може да бъде паралелизиран.
Като разделим цикъла на две независими операции, можем да изпълним тези операции паралелно. Например, можете да приложите алгоритъма parallel_for от Intel® Threading Building Blocks Library (Intel® TBB) към всеки от тях, както е показано по-долу:
Връщането на първото извикване на parallel_for преди изпълнение на второто гарантира, че всички актуализации на масив a са завършени, преди да започнат актуализациите на масив b.
Разлагането на цикъла може да се използва и за локализиране на данни. Помислете за следния пример на код, който работи като сито:
Външният цикъл избира началния индекс на елемента и стъпката на вътрешния цикъл от основния масив. След това вътрешният цикъл преминава през цялата дължина на маркирания масив, поставяйки стойността "1" в избраните елементи. Ако маркираният масив е достатъчно голям, изпълнението на вътрешния цикъл може да доведе до изваждане на редовете на кеша от редовете на кеша на първите елементи на маркирания масив, които са необходими за следващата итерация на външния цикъл. Това ще доведе до ниска честота на попадение в кеша както в серийната, така и в паралелната версия на цикъла.
Чрез използване на разлагане на цикъл, итерациите на вътрешния цикъл могат да бъдат разделени на части, които се вписват по-добре в кеша и да използват отново редовете на кеша, след като са били запълнени. За да приложим декомпозиция в този случай, нека добавим друг цикъл, който контролира обхвата, покрит от най-вътрешния цикъл:
За всяка итерация на най-външния цикъл в горния пример ще бъде изпълнен пълен набор от итерации на i-цикъла. Въз основа на избрания елемент от основния масив намираме началния и крайния индекс в блока на маркирания масив (контролиран от външния цикъл). Тези изчисления са включени в подпрограмите f() и g(). Така същият блок в маркирания масив ще бъде обработен, преди да се извърши преходът към следващия. Като се има предвид, че обработката на всеки блок се извършва независимо от останалите, итерациите на външния цикъл могат да бъдат превключени в паралелен режим.
Друга техника за оптимизация, която помага за ефективно паралелизиране на итерациите, е комбинирането на вложени цикли за увеличаване на броя на итерациите. INКато пример, разгледайте кодовия фрагмент отляво с два вложени цикъла, които имат съответно 23 и 1000 итерации. Тъй като 23 е просто число, повторенията на външния цикъл не могат да бъдат ефективно разделени; в допълнение, количеството работа в 1000 итерации може да не е достатъчно, за да намали значително разходите за паралелизиране само на вътрешния цикъл. От друга страна, можете да обедините тези цикли в един цикъл с 23 000 итерации (вижте примера вдясно), което ще смекчи трудностите, които възникват при паралелизиране на първоначалния код.
В същото време, ако всяка от итерационните променливи се използва вътре в тялото на цикъла (например за индексиране на масиви), новият брояч на цикъл трябва да бъде преведен обратно към съответните стойности на параметри, което води до допълнителни допълнителни разходи, които не присъстват в оригиналния алгоритъм.
Обединенията на цикли с подобни индекси могат да се използват за подобряване на разделянето и ефективно локализиране на данни, като същевременно се намаляват разходите за паралелизиране. Първите два цикъла в примера вляво могат лесно да се комбинират:
Комбинирането на тези цикли увеличава количеството работа на итерация (т.е. степента на разделяне) и намалява разходите, свързани с цикъла. Обединяването на третия цикъл вече не е толкова лесно, защото има различен брой повторения. По-важното е, че има зависимост на данните между третия цикъл и предходните два цикъла.
Използвайте опцията OpenMP if, за да изберете сериен или паралелен режим в зависимост от информацията за времето на изпълнение. В някои случаи броят на итерациите на цикъла не може да бъде зададен до момента на изпълнение. Ако изпълнениеПаралелният регион на OpenMP в множество нишки има отрицателно въздействие върху производителността (например малък брой итерации), за да постигнете стабилна производителност, трябва да зададете минимален праг (праг), както в примера по-долу:
В този пример цикълът се изпълнява паралелно само ако броят на итерациите надвишава минималния праг, зададен от програмиста.
Като се има предвид, че в Intel TBB няма подобен механизъм, за да определите кой режим на изпълнение на кода да използвате (сериен или паралелен), можете да въведете изрична проверка на условието. От друга страна, можете да извикате паралелен алгоритъм и да оставите програмата за планиране на задачи на Intel TBB да използва една нишка за малки стойности на N. Трябва да се отбележи, че последната опция има някои допълнителни разходи.