Степен на разделяне и паралелна производителност, софтуер Intel®
Един от ключовете за постигане на добра паралелна производителност е изборът на правилната степен на разделяне на приложението. Степента на разделяне (степента на детайлност) е количеството работа, извършена в паралелна задача. Ако нивото на детайлност е твърде високо, тогава производителността ще пострада от комуникационните разходи. Ако детайлността е твърде ниска, приложението ще изпита дисбаланс на натоварването. Целта е да се определи правилното ниво на детайлност (обикновено по-високото е по-добро) за паралелни задачи, като се избягва дисбаланс на натоварването и комуникационни разходи, за да се постигне най-добра производителност.
Входни данни
Количеството работа в една паралелна задача в многонишково приложение значително влияе върху ефективността на паралелизма. Когато разлагате приложение на нишки, една опция е логическото разделяне на задачата на възможно най-много паралелни задачи. Освен това в среда на паралелни задачи се определя необходимото ниво на комуникация за работа с разделени данни и определяне на реда на изпълнение. Тъй като операциите по разделяне на задачи, присвояване на задачи на нишки и споделяне на данни между задачи не са безплатни, често е необходимо да се агломерират или комбинират дялове, за да се преодолеят тези режийни разходи и да се получи най-ефективното внедряване. Агломерацията е за определяне на най-доброто ниво на гранулиране за паралелни задачи.
Грануларността често се отнася до това как работата е балансирана между нишките. Въпреки че е по-лесно да се балансира работа, която се състои от много малки задачи, може да има твърде много разходи за комуникация, синхронизация и т.н. Следователно е възможнонамаляване на разходите чрез намаляване на детайлността, комбиниране на малки задачи в една по-голяма. Инструменти като Intel® Parallel Amplifier могат да помогнат за определяне на правилното ниво в приложение.
Следващият пример показва как производителността на паралелна програма може да бъде подобрена чрез намаляване на разходите за обмен и използване на правилното ниво на гранулиране. Примерът, използван в тази статия, е алгоритъм за прости числа, който използва прост пряк тест, при който всяко потенциално просто число се дели на всички възможни делители, докато се намери реален делител или се докаже, че числото е просто. Тъй като положителните нечетни числа се изчисляват като (4k+1) или (4k+3) за k ≥ 0, кодът също така брои прости числа, съответстващи на една от тези форми. Примерът изчислява всички прости числа от 3 до 1 милион.
Първата версия на кода използва OpenMP за паралелизиране:
Този код има високо ниво на комуникационни разходи (под формата на синхронизация), а размерът на отделните задачи е твърде малък за нишки. Вътре в цикъла има критична секция, която се използва за организиране на безопасното увеличаване на променливата на брояча. Критичната секция добавя синхронизиране и блокиране на допълнителни разходи към цикъла, което е отразено в прозореца на Intel Parallel Amplifier на фиг. 1.
Фиг. 1. Анализ на блокиране и изчакване, който казва, че критичният регион на OpenMP причинява увеличени разходи за синхронизиране.
Увеличаването на броя на променливите на брояча въз основа на стойностите на големи масиви от данни е често използван метод, който се нарича намаляване. Разходите за заключване и синхронизиране могат да бъдат елиминирани чрез премахване на критичния регион и добавяне на израз за намаляване на OpenMP:
В зависимост от това колко итерации се изпълняват в цикъла, премахването на критичната секция от тялото на цикъла може да ускори изпълнението с порядък. Горният код обаче все още има някои паралелни разходи. Те са причинени от твърде малък обем на работата във всяка задача. Изявлението schedule(dynamic, 1) означава, че планировчикът динамично разпределя по една итерация (част от работа) на всяка нишка. Всеки работен процес обработва една итерация, след което се синхронизира с планировчика и започва следващата итерация. Чрез увеличаване на размера на парчето, ние увеличаваме размера на работата във всяка задача, която е присвоена на нишки, като по този начин намаляваме броя на извикванията на нишки за синхронизиране към планировчика.
Въпреки че този метод може да подобри производителността, трябва да имате предвид (както беше споменато по-горе), че твърде ниското ниво на детайлност може да причини дисбаланс на натоварването. Например, нека се опитаме да увеличим размера на задачата до 10 000, както е в кода по-долу:
Анализът на този код с помощта на паралелен усилвател разкри дисбаланс в броя на изчисленията, извършени от четири нишки, както е показано на фиг. 2. Основната причина тук е, че всяка част от работата има различен брой изчисления и има твърде малко части, зададени като задачи (десет части за четири нишки), което причинява дисбаланс на натоварването. Тъй като броят на потенциалните прости числа се увеличава (от цикъла for), са необходими повече итерации за тестване на всички възможни фактори (в цикъла while). По този начин общото количество работа във всяка част изисква повече итерации на цикъла while, отколкото в предишния случай.
Фиг. 2. Резултатите от анализа на паралелността, показващи дисбаланс във времето на изпълнениеразлични потоци.
За да изберете правилната детайлност за програмата, трябва да се използва по-подходящ размер на работния блок (100). Освен това, тъй като разликата в количеството работа в последователните задачи ще бъде по-малка, отколкото при предишния размер, можете допълнително да намалите разходите, като използвате статично, а не динамично планиране. Кодът по-долу показва промените в оператора на графика, които премахват режийните разходи от този кодов сегмент и осигуряват най-добра едновременност.
Препоръки
Паралелната производителност на многонишковия код зависи от детайлността: как работата се разделя между нишките и как се осъществява комуникацията между тях. Следват препоръки за подобряване на производителността с правилната настройка на гранулиране:
- Трябва да знаете вашата програма
- Разберете колко работа се извършва в различни части на паралелно приложение.
- Разберете комуникационните изисквания на приложението. Синхронизирането е форма на комуникация, но трябва да се вземат предвид и разходите за изпращане на съобщения и споделяне на данни чрез йерархия на паметта (кеш, основна памет и т.н.).
Ръководство за приложение
Въпреки че горните примери често се отнасят за OpenMP, всички съвети и принципи се отнасят за други модели на нишки, като нишки на Windows и нишки на POSIX*. Всички модели на нишки имат допълнителни разходи, свързани с различни функции, като паралелно изпълнение, заключвания, критични региони, предаване на съобщения и т.н. Препоръките, дадени тук за намаляване на количеството комуникация и увеличаване на размера на работата на нишка без увеличаване на дисбаланса на натоварването, се отнасят за всички модели на нишки. Въпреки това различните нива на режийни разходи в различните модели на поточно предаване диктуват различен избор на ниво на детайлност.