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.