Изпечатай

[gat3way]

Имам една такава странна ситуация, multithreaded приложение, имам няколко нишки (да ги наречем worker-и), които нямат проблем да изпълняват една критична секция паралелно, както и една нишка (да я наречем monitor), която периодично се събужда и върши някаква кратка работа. Термините "worker" и "monitor" са си напълно условни и са лишени от съдържанието, което се влага в тях от академична гледна точка, т.е worker-ите наистина вършат някаква работа, а monitor-а взема някакви хардуерни показатели и на базата на тях влияе на работата на worker-ите.

Докато monitor-а върши тази работа с вземането на хардуерните показатели, останалите няколко нишки не трябва да са в критичната секция. Най-простото решение с мутекс е малоумно, защото не искам да заключвам worker-ите помежду им, това убива производителността най-малкото.

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

Първите идеи които ми се въртяха в главата бяха комбинации от мутекс и семафор или мутекс и condvar-и. После открих съществуването на rwlock-овете в pthreads и бях просто потресен, цялата концепция идеално ми се вписва и е много проста за ползване.

Оообаче проблем - rwlock имплементацията в линукс е крива и е изключително лесно да докараш monitor-а до starvation, защото се дава приоритет на reader-ите (worker-ите). Worker-ите съответно заключват rwlock-а стотици пъти в секунда и горкия "monitor", който се буди през минута да види състоянието на хардуера, просто не може да вземе ръка Съвсем буквално, не може да се изпълни изобщо. Не че закъснява, на практика просто не се изпълнява.

Та това поведение може да се промени ако се ползват едни non-portable _np функции, които обръщат поведението и дават приоритет на writer-а (monitor-а). Обаче те са линукс-специфични, което означава че не мога да портна свинщината дори на FBSD.

Та това което ми хрумна е да си поиграя малко с scheduling policy-то на нишките и да вдигна приоритета на monitor нишката. Обаче доколкото чета разни хора дебело предупреждават, че това не е добра идея и може да доведе до доста грозни проблеми, примерно priority inversion такива и така нататък.

Та ако може да си спестя няколко вечери главоблъскане, чудно ми е някой занимавал ли се е точно с този проблем. Дали си струва да се пробвам да променям приоритети и sched policy-та или просто да отеба идеята и да се пробвам да го реализирам с подръчни средства (мутекси и семафори). От една страна тези rwlocks пасват просто тоооооолкова добре на цялата идея и са толкова прости за ползване и така добре лишават от съмнителното щастие да се осереш някъде. От друга страна, portability-то в бъдеще ми е важно. Ебати дилемата...

[n00b]

Понеже имам подобно главоболие в момента и аз винаги се сещам за крилатата фраза:
"Добрия план днес е по-добре отколкото отличен утре"

Така, че действай смело... FBSD - когато, тогава.

[ieti]

Преди време се борих с приложение с мноооого нишки. Схемата беше следната. Монитора(overlord) взимаше задачи и ги раздаваше на работниците. Следеше само дали работниците са свободни и ако са даваше нова задача. Това би трябвало да те освободи от всякаква синхронизация.

Замисли се обаче трябват ли ти толкова много нишки. Практически ако се ползват за сметки повече от 2-3 на ядро си е безмислено и загубата от контекст суичове става гадна.

Ако обаче бачкаш с някоя латентна среда масовата многонишковост си е доста полезна.

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

[netgraph]

От "man pthread_rwlock_wrlock" на FreeBSD:

Код:

IMPLEMENTATION NOTES
     To prevent writer starvation, writers are favored over readers.

Това важи и за другите BSD-та (поне OpenBSD и NetBSD със сигурност).

От "man pthread_rwlock_wrlock" на Solaris:

Код:

Writers are favored over readers of  the  same  priority  to
     avoid writer starvation. See pthread_rwlock_rdlock(3C).

Интересното в ман страницата на Линукс е следното:

Код:

...
Implementations [b]may[/b] favor writers over readers to avoid writer starvation.
...
APPLICATION USAGE
       Applications using these functions may be subject to priority inversion, as discussed in the Base Definitions volume  of  IEEE Std 1003.1-2001,  Section  3.285,  Priority
       Inversion.
...

Бих казал, че по пътя на логиката, а и на книгите за ОС, би трябвало writer-а да е с по висок приоритет от reader-ите и да не може нови reader-и да я вземат когато writer се опитва да я заключи (което е и по важно), иначе при много нишки ще има write-starvation със сигурност.

Поздрави 

[gat3way]

Пише, но на практика не става така, а точно обратното. rwlock имплементацията в линукс е ужасно сбъркана. Понеже при мен writer-а никога не успяваше да локне, известно време живях с илюзията че съм се осрал при reader-ите, там обичайните проблеми да не го освобождавам поради някаква причина или да го заключвам два пъти или нещо от сорта. Но не беше това проблема, затова google-нах и открих това:

http://stackoverflow.com/questions/2190090/how-to-prevent-writer-starvation-in-a-read-write-lock-in-pthreads


По-специално това:

This does indeed depend on the implementation - so since you have asked about Linux specifically, my comments are refer to the current NPTL implementation of pthreads, which is used in modern glibc.

There are two related, but separate, issues here. Firstly, there is this situation:

    There are read locks currently held, and writers waiting. A new thread tries to take a read lock.

The default action here is to allow the reader to proceed - effectively "jumping the queue" over the writer. You can, however, override this. If you use the pthread_rwlockattr_setkind_np() function to set the PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP flag on the attr that you pass to pthread_rwlock_init(), then your rwlock will block the reader in the above situation.

The second situation is:

    The last holder releases the lock, and there are both readers and writers waiting.

In this situation, NPTL will always wake up a writer in preference to a reader.

Taken together, the above means that if you use the PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP flag, your writers shouldn't be starved (of course, now a continuous stream of writers can starve the readers. C'est la vie). You can confirm all this by checking the sources (it's all very readable) in pthread_rwlock_rdlock.c and pthread_rwlock_unlock.c.

Note that there is also a PTHREAD_RWLOCK_PREFER_WRITER_NP, but it appears not to have the right effect - quite possibly a bug

С други думи - при равни условия и ако не се появи нов reader който да се опита да го заключи - има афинитет към writer-а. Обаче при мен проблемът е точно такъв - имам няколко reader-и които много често заключват rwlock-а и само един writer който спорадично се опитва да го заключи. Крайният резултат беше че не успява. След горепосочения съвет обаче всичко си дойде на мястото.

[e_stealth]

Определено ще имаш проблем с портваемоста.
http://www.gnu.org/software/gnulib/manual/html_node/pthread_005frwlockattr_005fsetkind_005fnp.html

Аз бих заложил по скоро на механизъм който включва семафор.
Но ако търсиш по бързо и по просто решение само за линукс то това няма да е проблем за теб.

[gat3way]

Ммм в крайна сметка ще си остане с rwlock. От суеверни причини, винаги съм мразил и съм се чувствал неудобно когато използвам повече от един синхронизационен механизъм, за да защитавам общ споделен ресурс (condvar-ите са изключение, защото там по презюмпция се ползва и мутекс).

Добре разбирам че ще имам проблеми с други операционни системи. Честно казано, *BSD не ме интересува особено, но идеята ми беше някой ден да го портна за macosx и/или windows. За windows така или иначе ще имам големи драми само задето ползвам pthreads, докато за macosx...не мисля че ще стане освен ако не си купя някой ден такова желязце. Така че майната му на portability-то за момента.

П.П

Замисли се обаче трябват ли ти толкова много нишки. Практически ако се ползват за сметки повече от 2-3 на ядро си е безмислено и загубата от контекст суичове става гадна.

Наистина се ползват за сметки, но сметките не се извършват върху процесора, а от GPU-та. Всяко GPU се обслужва от една или повече нишки (принципно 2-3 е оптималния вариант, защото така най-добре се утилизира GPU-то, докато едната нишка обслужва върнатите резултати, другата може да enqueue-не работа върху GPU-то така че да му "уплътнява" по-добре изчислителното време). При наличие на 2 двучипни видеокарти на системата съответно можеш да имаш спокойно 10 или повече worker нишки. Обаче в моя случай дори само едно GPU е достатъчно, само с 2 worker-а, за да създаде writer starvation проблема. Причината е че worker-ите влизат прекалено често в критичната секция. И....решението е линукс-специфично, забавно...

[ieti]

Хммм а защо трябва да синхронизираш толкова много. Не можеш ли да сложиш работниците в пуул. Шефчето на определено време ще обхожда пуула и ще пуска свободните от задачи да пасат.  Направи обаче работниците така че да не се налага да се синхронизират помежду си. Работните тредове ще са тред с безкраен цикъл. Когато имат задача си се въртят вътре ако не си стоят така и спят.

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

Помня че с мойта боза имах 250 треда. Опита всеки тред да чете и пише в MySQL база докара админа ни до отчаяние след като му сринах сървъра многократно. След като направих прост конекшън пуул се оказа че 250 треда без проблем се обслужват от пуул с 10 конекции.

[gat3way]

worker-ите не трябва да се синхронизират помежду си, няма нужда след като задачата е embarassingly parallel. Обаче с въпросният монитор (нишка, която ходи и взема температурата и suspend-ва worker-ите работещи върху прегряващата карта) нещата са забавни. Това изисква синхронизация между монитора и всеки работник, което става с мутекси. Но това не е проблемът. Проблемът се оказа при NVidia картите, там ако вземането на температурите случайно съвпадне с някой PCIe трансфер, става много голямо мазало. Та оттам тръгна всичко - трябва да съм сигурен че събирането на данните за температура не става докато някой от работниците трансферира данни от/до GPU-то.

[arda_kj]

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

ПС: Преди няколко месеца портвах една моя C програмка към Windows и се оказа, че някви пичове са портнали pthreads (поне по-голямата част) за Windows, и нямах проблеми с портването, не съм пипал никакъв код. Мисля, че даже си идваше с Cygwin.

ПС2: Вчера ровейки се в Интернет попаднах на това

http://en.wikipedia.org/wiki/Intel_Cilk_Plus
http://software.intel.com/en-us/articles/intel-cilk-plus/

Метод за "лесно" паралелно програмиране с разширение към C/C++ нар. Intel Click Plus.
Някой знае ли нещо, пробвал ли го е, дали си струва да се ползва?

[gat3way]

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

Не. Това на теория звучи добре, но на практика ще стане следното (особено ако имаш повече от едно GPU и се различават като скорост на работа): "бързите" worker-и ще си направят итерациите и ще дремят докато по-бавните ги направят. Чак тогава ще може монитора да мине да си вземе нещата. Това е разхищение на изчислително време и не е приемливо. Дори при само едно GPU с две нишки отгоре, едната нишка неминуемо има малко по-добър "късмет" и съумява да си изпълни итерациите върху GPU-то по-бързо (GPU-тата не са preemptive, та няма как едновременно две задачи да се изпълнят, без значение колко CPU нишки са ги засилили, те се сериализират).


За cilk съм чувал, идеята е сходна с OpenMP, въпреки че в OpenMP нещата се реализират малко по-различно, с препроцесорни директиви. OpenCL върху CPU-та е друг модел, гонещ същите цели. Тези неща ти спестяват доста усилия и евентуални проблеми, но никога не могат да докарат производителността, която можеш да изцедиш с внимателно написан C/pthreads код без излишни синхронизации и избягвайки проблеми като false sharing, cache-unfriendly обхождане на структури от данни и т.н.

Дори OpenCL за CPU, което специално е дизайннато да се възползва максимално от хардуера (примерно мапвайки неговите си вектори към хардуерните SSE2/AVX регистри) не се справя добре. Правил съм си експерименти, ръчно оптимизиран SSE2 код (на C ползвайки intrinsics, не на асемблер) върви 2-3 пъти по-бързо от това което генерира OpenCL, колкото и да се старая да оптимизирам OpenCL kernel-а.

[lkr]

Всъщност има голяма вероятност Cilk да извади по-добри резултати от твоя ръчно написан код с pthreads. Cilk дава гаранции за брой cache misses при n на брой процесори и m на брой задачи за изпълнение. Проблемът с false sharing обикновено се получава при ръчно ползване на threads, а не на неща като Cilk. Дори да стане, може да се използва sheriff за отстраняването му. Cilk е модел за nested data parallelism разработван повече от 10 години, наистина ли мислиш, че твоя scheduler ще е по-добър от неговия? И последно да спомена, че всички модерни frameworks като .NET TPL, Java fork/join, Intel TBB са базирани на Cilk.

[gat3way]

Наблюденията ми са свързани с OpenMP, не със Cilk. Така че възможно е и Cilk наистина да е нещо много прекрасно. Обаче не мога да разбера как точно дава гаранция за брой cache misses след като това зависи силно от начина по който е реализиран алгоритъма. Много простия пример е обхождането на голям двумерен масив (примерно 10000x10000) и умножаването на всеки елемент с някаква константа - дали cilk ще види че го обхождам по колони, вместо по редове и ще промени съответно изпълнимия код?

False sharing-а също е проблем, който човек лесно сам си introduce-не без значение какво прави framework-а. С OpenMP това е изключително лесно - караш да ти се паралелизира един цикъл, който чете и пише в някакви глобални променливи и при добър късмет, нещата се осират относително лесно. OpenMP не е достатъчно "умен" за да може да се справя с такива случаи. Но пак казвам, Cilk-а може и да е, знам ли го...

[lkr]

Cilk дава гаранции само за програми, които не използват locks. Най-често се използват divide-and-conqueror алгоритми за разпределянето на задачите. Типичен пример са quick & merge sort, на които може да получиш линеен speedup с добавянето на още ядра. Тъй като Cilk е базирано на рандомизиран work-stealing scheduler имаш гаранции за пълното използване на всички ядра независимо от размера на различните задачи. Ето една статия по темата за изчисляването броя на cache misses при multithreaded програми използващи Cilk http://strumpen.net/tocs08.pdf

[remotex]

Имам следната идея която отново е с 2 примитива обаче...
тъй като имаме ситуация 1!:N то на 1! не му трябва да заключва нищо а само да запише нейде в 1 (2,3,4 колкото е необходимо клетка/и) из паметта че се е активирал и очаква включване на rwlock-а - тогава останалите N просто ще четат (без да заключват) тази клетка и ще чакат или бачкат според зависи дали има какво още да правят без да чакат на rwlock...
идеята ми е за леко модифициран spin lock
т.е. вместо

Код

GeSHi (C):
while(true){ if(!monitor_waiting) break; }
lock(rwlock);
 

да е нещо подобно

Код

GeSHi (C):
while(true){ 
if(monitor_waiting)
 sleep(0) // yield or do work if any...
else
 break;
}
lock(rwlock);

или още по-добре ако N и без това имат какво да правят да си го правят и периодично да проверяват тази клетка от паметта и само ако няма monitor_waiting тогава да се редят на опашката на rwlock за още работа. По този начин най-много 1 закл. вътре плюс m от N нишки ще са наредени на rwlock-а и като се изредят ще чакат... тъй като 1! е единствен той няма нужда да си заключва там където пише булевата ст-т дали е активен и очаква вкл. или не и като заключи той rwlock-а да сменя статус променливата/те на 0 т.е. че не чака вече и другите да почват пак да се редят на опашката.
Така хем е само с 1 "заключващ" примитив - хем е по-портабъл. Ако си мислиш че е по-различно не е: дали ще чакат всички на rwlock ако няма какво да правят междувременно или на обикновена променлива в стил модифициран spin-lock е все-тая все чакат, а ако не блокират на rwlock, а имат какво да правят тогава моят вариант звучи по-добре.