A library implementation of the nano-threads programming model

A Lib a y Implemen a ion o he Nano-Th eads P og amming Model Xa ie Ma o ell, Jesus Laba a, Nacho Na a o, Edua d Ayguade Depa amen d'A qui ec u a de Compu ado s (DAC) Uni e si a Poli ecnica de Ca alunya (UPC) G an Capi a s/n, Campus No d, Modul D6, 08071, Ba celona, Spain {xa im, jesus, nacho, edua d}@ac.upc.es Abs ac . In his pape we desc ibe he design and implemen a ion o a use -le el h ead package based on he nano- h eads p og amming model, whose goal is o e icien ly manage he applica ion pa allelism a use -le el. Nano- h ead applica ions wo k close o he ope a ing sys em o quickly adap o esou ce a ailabili y. The goal is o ob ain an e icien pa allel execu ion o he nano- h eads by app op ia ely balancing he wo k assigned o each h ead and he h ead managemen o e head. Ea ly expe imen s le us de e mine ha he app op ia e numbe o ope a ions sp ead ou among he h eads o ensu e less han 10% o o e head is a ound 800. Recen expe imen s show ha his nano- h ead g anula i y is ine enough o adap easily o he sys em condi ions, g an ing a educed esponse ime. 1. In oduc ion T adi ional use -le el h ead packages a e used by p og amme s o pa allelize by hand hei applica ions. Those packages a e mos ly o ien ed o coa se-g ain s uc u ed pa allelism [7][12]. Nowadays, new h ead packages e ol e o gi e suppo o compile gene a ed pa allel code. Compile s mainly manage one-le el o s uc u ed pa allelism (do-loops) and also coa se-g ain pa allelism. Resea ch on new p og amming models is a opic o g ea in e es o he success o gene al pu pose pa allel compu ing. The goal is ha new h ead packages could o e e icien execu ion o se e al le el pa allelism, less s uc u ed, mo e ine-g ained and lexible han cu en ones. In his pape we a e going o desc ibe he design and implemen a ion o a use -le el h ead package based on he nano- h eads model [10]. Ou en i onmen assumes ha applica ions (e.g., C o FORTRAN p og ams) a e au oma ically decomposed by a pa allelizing compile . The compile iden i ies he maximum pa allelism o he applica ion h ough da a and con ol dependence analysis and gene a es an in e media e ep esen a ion o he pa allel applica ion in he o m o a hie a chical ask g aph This wo k has been suppo ed by he Minis y o Educa ion o Spain (CICYT) unde con ac s TIC95-0492 and TIC94-0439. Ma o ell, X. [e al.]. A lib a y implemen a ion o he nano- h eads p og amming model. A: In e na ional Eu opean Con e ence on Pa allel and Dis ibu ed Compu ing. "Eu o-Pa '96, Pa allel P ocessing: Second In e na ional Eu o-Pa Con e ence: Lyon, F ance, Augus 26–29, 1996: p oceedings, olume II". Be lín: Sp inge , 1996, p. 644-649. ISBN 978-3-540-70636-6. The inal au hen ica ed e sion is a ailable online a h ps://doi.o g/10.1007/BFb0024761 (HTG)[2][6]. We plan o use he Pa a ase-2 compile [9] o gene a e execu able code om he HTG in e media e ep esen a ion. 2. Objec i es Objec i es o his pape a e o s udy he iabili y o he nano- h eads pa allel p og amming model demons a ing ha +I is possible o build an e icien implemen a ion o a nano- h ead package o manage he applica ion pa allelism a use le el. +The un- ime o e head ela ed o he c ea ion and managemen o pa allel h eads can be kep e y low, so ha e iciency o pa allel p ocessing a ine-g anula i y le els does no depend on lib a y managemen . +The suppo ed g anula i y is ine-g ained enough o ensu e a good adap a ion o he esou ce a ailabili y. Sec ion 3 ou lines he design o he nano- h eads package. Sec ion 4 p esen s i s e alua ion. Finally, sec ion 5 ou lines some u u e wo k. 3. The Nano- h eads Lib a y The execu ion o a nano- h eaded applica ion consis s in he execu ion, in some o de and p ese ing dependencies, o he unc ions gene a ed om he HTG. An app oach is o build a use -le el lib a y o ou ines g ouping he se ices needed by hese unc ions: he nano- h eads lib a y. In he lib a y, he equi ed simplici y in h ead managemen is ob ained by managing only one ixed size s uc u e ( he nano- h ead s uc u e). I con ains all he nano- h ead in o ma ion including i s desc ip o and i s s ack. Among o he a ibu es, he nano- h ead desc ip o con ains a coun e o un esol ed dependencies o he nano- h ead and a e e ence o a successo nano- h ead. The nano- h ead c ea ion p imi i e alloca es (o ecycles) and ini ializes he nano- h ead s uc u e. The lib a y also o e s simple p imi i es o con ol he (al eady) un esol ed dependencies, o manage he use -le el eady queue, and o help in he implemen a ion o pa allel loops. The co e o he lib a y con ains he nano- h ead scheduling loop ha sea ches o wo k in he eady queue. This loop is execu ed by as many ke nel h eads as p ocesso s a e alloca ed o he applica ion. Also, he lib a y is able o adap o a ia ions in he numbe o p ocesso s alloca ed o i . Mo e in o ma ion abou he cu en implemen a ion o he nano- h eads lib a y can be ound in [5]. 4. E alua ion We ha e implemen ed he nano- h eads lib a y on op o he Mach 3.0 mic oke nel [1]. We use a 4 i486 (33 Mhz) mul ip ocesso a chi ec u e (DEC433MP) wi h 32 Mb. o main memo y and 256 Kb. o cohe en cache a each p ocesso . Ou implemen a ion o he nano- h eads lib a y is based on he Quick Th eads package [3]. Execu ion imes o he basic nano- h ead lib a y p imi i es emain below 15 us. S a ing a nano- h ead cos s 25 us. in he gi en a chi ec u e. This can be compa ed wi h he ime equi ed o pe o m a loa ing poin addi ion (0.15 us) and a loa ing poin mul iplica ion (0.27 us). 4.1. G anula i y Expe imen s A i s e alua ion o he nano- h eads package was done using a ma ix by ec o p oduc applica ion. Figu e 1 shows he applica ion execu ion imes and speed-up on 2, 3 and 4 p ocesso s. The main goals o he expe imen s we e he s udy o he nano- h ead g anula i y and i s e ec on he execu ion ime and speedup o he applica ion. Figu e 1: Execu ion ime and speed-up o he ma ix by ec o p oduc . The applica ion we used wo ked wi h a big ma ix and a small ec o (9 elemen s). The chunk size assigned o each nano- h ead le s he applica ion o span a wide ange o g anula i y le els. I can use chunks con aining om 1 o 11250 ma ix ows (wi h 18 p-ops o each ow). In e ms o ope a ions execu ed by each nano- h ead, he esul s indica e ha he minimum numbe o loa ing poin ope a ions o be pe o med by a nano- h ead should be g ea e han 800 (43 i e a ions * 18 p-ops/i e a ion = 774 p-ops) o ensu e an o e head lowe han 10% o he sequen ial execu ion ime. Applica ion speedups e lec he cache in luence. Fou p ocesso s p o ide ou imes mo e cache han a single one. This educes he numbe o cache misses in he o e all execu ion, hus p oducing a supe -linea speedup in some expe imen s. 16 26 32 43 65 1406 11250 chunk size 0 1000 2000 3000 4000 5000 6000 7000 8000 execu ion ime (ms.) 1 p ocesso 2 p ocesso s 3 p ocesso s 4 p ocesso s sequen ial e sion on 1 p ocesso 1 cpu 2 cpus 3 cpus 4 cpus p ocesso s 0.75 1.00 1.25 1.50 1.75 2.00 2.25 2.50 2.75 3.00 3.25 3.50 3.75 4.00 4.25 4.50 4.75 5.00 speed-up chunk size = 16 chunk size = 43 chunk size = 65 chunk size = 87 chunk size = 1406 chunk size = 11250 4.2. Adap abili y Expe imen s The nano- h eads p og amming model is de ined o adap o he unde lying numbe o p ocesso s. This means ha he ope a ing sys em can add and emo e p ocesso s o/ om applica ions. The s eps ollowed by he ke nel p eemp ion mechanism a e: +The ope a ing sys em decides o eassign a p ocesso om an applica ion o ano he . I eques s a p ocesso o he sou ce applica ion and wai s o he esponse ( he eac ion ime). +The applica ion de ec s he eques and i eleases a p ocesso a a sa e poin (a he end o a nano- h ead), a oiding he p eemp ion o wo k, which may be in he c i ical pa h. +The ope a ing sys em ans e s he p ocesso o he des ina ion applica ion. +In case he sou ce applica ion does no espond in he gi en eac ion ime, he ope a ing sys em s eals a p ocesso om i , independen ly o he wo k i is doing. Two di e en echniques o elease and e u n p ocesso s ha e been implemen ed: i s , using he h ead suspend/ esume p imi i es; and second, modi ying he p io i y o he ke nel h eads associa ed o he applica ion. The measu emen s p esen ed he e a e aken using he i s echnique. We ha e used a Jacobi i e a ion based on a ma ix o 480 ows. The esolu ion spends 250 i e a ions. Two wo k gene a ion schemes a e es ed: i s , a ixed chunk size (2 and 24 ows); and second, a ying he chunk size in a guided sel -scheduling s yle. Elapsed execu ion imes a e gi en in igu e 2. Obse e he o e head in oduced by he ixed small chunk size (2) compa ed wi h he gss gene a ion s yle, using 1, 2 and 3 p ocesso s. We ha e implemen ed a high-p io i y use -le el p ocess which simula es he ope a ing sys em scheduling, s ealing and e u ning p ocesso s om/ o he applica ion. Sha ed memo y is used o communica ion be ween he ke nel simula o and he applica ion. In he expe imen s, one p ocesso is p eemp ed om he applica ion and assigned o i pe iodically o he same amoun o ime ( -ncpuchange). A wide ange in -ncpuchange is explo ed o co e om quick mo emen o p ocesso s (40 ms.), o la ge pe iods used in o he scheduling wo ks (4 s.) [12]. The sys em simula o is con igu ed o se no eac ion ime o a eac ion ime o 3 ms. In gene al, applica ions ha eac in ime always pe o m be e han applica ions ha do no . A small chunk size (2 ows ) is a good wa an y o esponse. Gss applica ions do no espond because hey gene a e some oo la ge chunks o each i e a ion. When he -ncpuchange is small, ixed chunk size (2 o 24) pe o ms be e han gss because he la e gene a es bigge chunks. Gene ally, p eemp ion can occu in he middle o he execu ion o he chunk, and no only he applica ion looses one p ocesso , bu a g ea amoun o wo k blocks un il he p ocesso e u ns. Also, his is he eason why applica ions wi h big chunk sizes pe o m wo se when he -ncpuchange is la ge . Figu e 2: E ec o he p ocesso assignmen in he execu ion ime. 5. Fu u e Wo k Mo e expe imen s, measu emen s and beha iou al s udies a e needed. We plan o ace he execu ion o applica ions based on he lib a y o de e mine whe e and when he p ocesso s become idle o he managemen done by he lib a y does no i he applica ion equi emen s. We a e implemen ing an ins umen ed e sion o he lib a y ha in e aces o a isualiza ion ool (PARAVER [8]). This ool will enable us o see he ac ual un- ime beha iou . I will also be in e es ing he s udy o he in luence o he ope a ing sys em i ual memo y managemen mechanism in he pe o mance o he applica ions. 40 400 4000 -ncpuchanges (ms.) 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 105 107 109 111 execu ion ime (secs.) nano- h eads, chunk size 2, 2.5 cpus, no eac ion ime nano- h eads, gss s yle, 2.5 cpus, no eac ion ime nano- h eads, chunk size 2, 2.5 cpus, 3 ms. eac ion ime nano- h eads, gss s yle, 2.5 cpus, 3 ms. eac ion ime nano- h eads, chunk size 24, 2.5 cpus, 3 ms. eac ion ime pu e sequen ial e sion nano- h eads, chunk size 2, 1 cpu nano- h eads, gss s yle, 1 cpu nano- h eads, chunk size 2, 2 cpus nano- h eads, gss s yle, 2 cpus nano- h eads, chunk size 2, 3 cpus nano- h eads, gss s yle, 3 cpus We wan o es new use -le el scheduling policies; o example, dynamic chunk sizes based on apezoid sel -scheduling, a ini y scheduling, e c. [4], and o de e mine he quali y o adap abili y o he lib a y o la ge a ia ions in he numbe o p ocesso s. The esul s will be e y use ul o apply o a mul i-use en i onmen . The nano- h eads lib a y is now being po ed o o he a chi ec u es: in pa icula he SGI Powe Challenge and he DEC Alpha AXP. We also plan o po he lib a y on op o he Cho us mic oke nel [11]. 6. Acknowledgemen s We would like o hank Cons an ine D. Polych onopoulos o he ini ial discussions abou nano- h eads and he possibili ies o implemen a ion. 7. Re e ences 1. Acce a, M., Ba on, R., Golub, D., Rashid, R., Te anian, A., Young, M.: Mach: A New Ke nel Founda ion o UNIX De elopmen . P oc. o he Summe 1986 USENIX Con e ence, July 1986. 2. Gi ka , M., Polych onopoulos, C. D.: Au oma ic Ex ac ion o Func ional Pa allelism om O dina y P og ams. IEEE T ans. on Pa allel and Dis . Sys ems, Vol. 3, No. 2, Ma ch 1992. 3. Keppel, D.: Tools and Techniques o Building Fas Po able Th eads Packages. Technical Repo UWCSE 93-05-06, Uni e si y o Washing on, 1993. 4. Ma ka os, E. P., LeBlanc, T. J.: Using P ocesso A ini y in Loop Scheduling on Sha ed- Memo y Mul ip ocesso s. P oc. o he Supe compu ing-92, 1992, pp. 104-113. 5. Ma o ell, X., Laba a, J., Na a o, N., Ayguadé, E.: Nano-Th eads Lib a y Design, Implemen a ion and E alua ion. Dep . d’A qui ec u a de Compu ado s - Uni e si a Poli ècnica de Ca alunya. Technical Repo : UPC-DAC-1995-33, Sep embe 1995. 6. Mo ei a, J. E.: On he Implemen a ion and E ec i eness o Au oscheduling o Sha ed- Memo y Mul ip ocesso s. PhD. hesis, Depa men o Elec ical and Compu e Enginee ing, Uni . o Illinois a U bana-Champaign, 1995. 7. Muelle , F.: A Lib a y Implemen a ion o POSIX Th eads unde UNIX. 1993 Win e USENIX, Janua y 25-29, 1993, San Diego, CA. 8. Pille , V., Laba a, J., Co és, T., Gi ona, S.: PARAVER: A Tool o Visualize and Analyse Pa allel Code, WoTUG-18, pp 17-31, Manches e , Ap il 95. 9. Polych onopoulos, C. D., Gi ka , M., Haghigha , M. R., Chia Ling Lee, Leung, B., and Schou en, D.: Pa a ase-2: An En i onmen o Pa allelizing, Pa i ioning, Synch onizing, and Scheduling P og ams on Mul ip ocesso s. In e na ional Jou nal o High Speed Compu ing, Vo. 1, No. 1, 1989. 10. Polych onopoulos, C. D.: nano-Th eads: Compile -D i en Mul i h eading. CSRD Technical Repo , 1993. 11. Rozie , M., Ab ossimo , V., A mand, F., Boule, I., Gien, M., Guillemon , M., He man, F., Kaise , C., e al.: O e iew o he Cho us Dis ibu ed Ope a ing Sys em. P oc. o he USENIX Wo kshop on Mic o-ke nels and O he Ke nel A chi ec u es, Ap il 1992. 12. Tucke , A., Gup a, A.: P ocess Con ol and Scheduling Issues o Mul ip og ammed Sha ed-Memo y Mul ip ocesso s. ACM Ope a ing Sys ems Re ., Vol 23 Num 5, Dec. 1989.