Robust and Tuneable Family\\of Gossiping Algorithms
Vincenzo De Florio and Chris Blondia
University of Antwerp
Department of Mathematics and Computer Science
Performance Analysis of Telecommunication Systems group
Middelheimlaan 1
2020 Antwerp
Belgium \vspace*{3pt
We present a family of gossiping algorithms whose members share the same structure though they vary their performance in function of a combinatorial parameter. We show that such parameter may be considered as a ``knob'' controlling the amount of communication parallelism characterizing the algorithms. After this we introduce procedures to operate the knob and choose parameters matching the amount of communication channels currently provided by the available communication system(s). In so doing we provide a robust mechanism to tune the production of requests for communication after the current operational conditions of the consumers of such requests. This can be used to achieve high performance and programmatic avoidance of undesirable events such as message collisions.
average.tex
% GNUPLOT: LaTeX picture
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\begin{picture}(1500,900)(0,0)
\font\gnuplot=cmr10 at 10pt
\gnuplot
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(171.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,131){\makebox(0,0)[r]{ 0}}
\put(1429.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,235.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,235){\makebox(0,0)[r]{ 5}}
\put(1429.0,235.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,339.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,339){\makebox(0,0)[r]{ 10}}
\put(1429.0,339.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,443.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,443){\makebox(0,0)[r]{ 15}}
\put(1429.0,443.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,547.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,547){\makebox(0,0)[r]{ 20}}
\put(1429.0,547.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,651.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,651){\makebox(0,0)[r]{ 25}}
\put(1429.0,651.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,755.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,755){\makebox(0,0)[r]{ 30}}
\put(1429.0,755.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,859.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,859){\makebox(0,0)[r]{ 35}}
\put(1429.0,859.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(171,90){\makebox(0,0){ 0}}
\put(171.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(299.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(299,90){\makebox(0,0){ 5}}
\put(299.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(427.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(427,90){\makebox(0,0){ 10}}
\put(427.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(554.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(554,90){\makebox(0,0){ 15}}
\put(554.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(682.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(682,90){\makebox(0,0){ 20}}
\put(682.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(810.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(810,90){\makebox(0,0){ 25}}
\put(810.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(938.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(938,90){\makebox(0,0){ 30}}
\put(938.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1066.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1066,90){\makebox(0,0){ 35}}
\put(1066.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1193.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1193,90){\makebox(0,0){ 40}}
\put(1193.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1321.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1321,90){\makebox(0,0){ 45}}
\put(1321.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1449.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1449,90){\makebox(0,0){ 50}}
\put(1449.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(171.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(171.0,131.0){\rule[-0.200pt]{307.870pt}{0.400pt}}
\put(1449.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(171.0,859.0){\rule[-0.200pt]{307.870pt}{0.400pt}}
\put(50,495){\rotatebox{90}{\makebox(0,0){Algorithmic parallelism}}
}\put(810,29){\makebox(0,0){participants}}
\put(571,819){\makebox(0,0)[r]{Identity}}
\put(222,176){\makebox(0,0){$+$}}
\put(248,180){\makebox(0,0){$+$}}
\put(273,180){\makebox(0,0){$+$}}
\put(299,182){\makebox(0,0){$+$}}
\put(324,182){\makebox(0,0){$+$}}
\put(350,183){\makebox(0,0){$+$}}
\put(375,183){\makebox(0,0){$+$}}
\put(401,184){\makebox(0,0){$+$}}
\put(427,184){\makebox(0,0){$+$}}
\put(452,184){\makebox(0,0){$+$}}
\put(478,184){\makebox(0,0){$+$}}
\put(503,184){\makebox(0,0){$+$}}
\put(529,185){\makebox(0,0){$+$}}
\put(554,185){\makebox(0,0){$+$}}
\put(580,185){\makebox(0,0){$+$}}
\put(606,185){\makebox(0,0){$+$}}
\put(631,185){\makebox(0,0){$+$}}
\put(657,185){\makebox(0,0){$+$}}
\put(682,185){\makebox(0,0){$+$}}
\put(708,185){\makebox(0,0){$+$}}
\put(733,185){\makebox(0,0){$+$}}
\put(759,185){\makebox(0,0){$+$}}
\put(784,185){\makebox(0,0){$+$}}
\put(810,185){\makebox(0,0){$+$}}
\put(836,185){\makebox(0,0){$+$}}
\put(861,185){\makebox(0,0){$+$}}
\put(887,185){\makebox(0,0){$+$}}
\put(912,186){\makebox(0,0){$+$}}
\put(938,186){\makebox(0,0){$+$}}
\put(963,186){\makebox(0,0){$+$}}
\put(989,186){\makebox(0,0){$+$}}
\put(1014,186){\makebox(0,0){$+$}}
\put(1040,186){\makebox(0,0){$+$}}
\put(1066,186){\makebox(0,0){$+$}}
\put(1091,186){\makebox(0,0){$+$}}
\put(1117,186){\makebox(0,0){$+$}}
\put(1142,186){\makebox(0,0){$+$}}
\put(1168,186){\makebox(0,0){$+$}}
\put(1193,186){\makebox(0,0){$+$}}
\put(1219,186){\makebox(0,0){$+$}}
\put(1245,186){\makebox(0,0){$+$}}
\put(1270,186){\makebox(0,0){$+$}}
\put(1296,186){\makebox(0,0){$+$}}
\put(1321,186){\makebox(0,0){$+$}}
\put(1347,186){\makebox(0,0){$+$}}
\put(1372,186){\makebox(0,0){$+$}}
\put(1398,186){\makebox(0,0){$+$}}
\put(1423,186){\makebox(0,0){$+$}}
\put(1449,186){\makebox(0,0){$+$}}
\put(641,819){\makebox(0,0){$+$}}
\put(571,778){\makebox(0,0)[r]{Hybrid, 50\%}}
\put(222,176){\makebox(0,0){$\triangledown$}}
\put(248,180){\makebox(0,0){$\triangledown$}}
\put(273,186){\makebox(0,0){$\triangledown$}}
\put(299,188){\makebox(0,0){$\triangledown$}}
\put(324,194){\makebox(0,0){$\triangledown$}}
\put(350,195){\makebox(0,0){$\triangledown$}}
\put(375,200){\makebox(0,0){$\triangledown$}}
\put(401,200){\makebox(0,0){$\triangledown$}}
\put(427,205){\makebox(0,0){$\triangledown$}}
\put(452,205){\makebox(0,0){$\triangledown$}}
\put(478,209){\makebox(0,0){$\triangledown$}}
\put(503,208){\makebox(0,0){$\triangledown$}}
\put(529,212){\makebox(0,0){$\triangledown$}}
\put(554,211){\makebox(0,0){$\triangledown$}}
\put(580,214){\makebox(0,0){$\triangledown$}}
\put(606,213){\makebox(0,0){$\triangledown$}}
\put(631,217){\makebox(0,0){$\triangledown$}}
\put(657,216){\makebox(0,0){$\triangledown$}}
\put(682,218){\makebox(0,0){$\triangledown$}}
\put(708,217){\makebox(0,0){$\triangledown$}}
\put(733,220){\makebox(0,0){$\triangledown$}}
\put(759,219){\makebox(0,0){$\triangledown$}}
\put(784,221){\makebox(0,0){$\triangledown$}}
\put(810,220){\makebox(0,0){$\triangledown$}}
\put(836,223){\makebox(0,0){$\triangledown$}}
\put(861,221){\makebox(0,0){$\triangledown$}}
\put(887,224){\makebox(0,0){$\triangledown$}}
\put(912,223){\makebox(0,0){$\triangledown$}}
\put(938,225){\makebox(0,0){$\triangledown$}}
\put(963,224){\makebox(0,0){$\triangledown$}}
\put(989,226){\makebox(0,0){$\triangledown$}}
\put(1014,224){\makebox(0,0){$\triangledown$}}
\put(1040,226){\makebox(0,0){$\triangledown$}}
\put(1066,225){\makebox(0,0){$\triangledown$}}
\put(1091,227){\makebox(0,0){$\triangledown$}}
\put(1117,226){\makebox(0,0){$\triangledown$}}
\put(1142,228){\makebox(0,0){$\triangledown$}}
\put(1168,227){\makebox(0,0){$\triangledown$}}
\put(1193,228){\makebox(0,0){$\triangledown$}}
\put(1219,227){\makebox(0,0){$\triangledown$}}
\put(1245,229){\makebox(0,0){$\triangledown$}}
\put(1270,228){\makebox(0,0){$\triangledown$}}
\put(1296,229){\makebox(0,0){$\triangledown$}}
\put(1321,228){\makebox(0,0){$\triangledown$}}
\put(1347,230){\makebox(0,0){$\triangledown$}}
\put(1372,229){\makebox(0,0){$\triangledown$}}
\put(1398,230){\makebox(0,0){$\triangledown$}}
\put(1423,229){\makebox(0,0){$\triangledown$}}
\put(1449,231){\makebox(0,0){$\triangledown$}}
\put(641,778){\makebox(0,0){$\triangledown$}}
\sbox{\plotpoint}{\rule[-0.400pt]{0.800pt}{0.800pt}}%
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(571,737){\makebox(0,0)[r]{Hybrid, 75\%}}
\sbox{\plotpoint}{\rule[-0.400pt]{0.800pt}{0.800pt}}%
\put(222,176){\makebox(0,0){$\ast$}}
\put(248,184){\makebox(0,0){$\ast$}}
\put(273,190){\makebox(0,0){$\ast$}}
\put(299,193){\makebox(0,0){$\ast$}}
\put(324,199){\makebox(0,0){$\ast$}}
\put(350,207){\makebox(0,0){$\ast$}}
\put(375,215){\makebox(0,0){$\ast$}}
\put(401,212){\makebox(0,0){$\ast$}}
\put(427,218){\makebox(0,0){$\ast$}}
\put(452,225){\makebox(0,0){$\ast$}}
\put(478,232){\makebox(0,0){$\ast$}}
\put(503,227){\makebox(0,0){$\ast$}}
\put(529,233){\makebox(0,0){$\ast$}}
\put(554,238){\makebox(0,0){$\ast$}}
\put(580,244){\makebox(0,0){$\ast$}}
\put(606,238){\makebox(0,0){$\ast$}}
\put(631,243){\makebox(0,0){$\ast$}}
\put(657,249){\makebox(0,0){$\ast$}}
\put(682,254){\makebox(0,0){$\ast$}}
\put(708,247){\makebox(0,0){$\ast$}}
\put(733,252){\makebox(0,0){$\ast$}}
\put(759,256){\makebox(0,0){$\ast$}}
\put(784,261){\makebox(0,0){$\ast$}}
\put(810,255){\makebox(0,0){$\ast$}}
\put(836,259){\makebox(0,0){$\ast$}}
\put(861,263){\makebox(0,0){$\ast$}}
\put(887,267){\makebox(0,0){$\ast$}}
\put(912,261){\makebox(0,0){$\ast$}}
\put(938,264){\makebox(0,0){$\ast$}}
\put(963,268){\makebox(0,0){$\ast$}}
\put(989,272){\makebox(0,0){$\ast$}}
\put(1014,266){\makebox(0,0){$\ast$}}
\put(1040,269){\makebox(0,0){$\ast$}}
\put(1066,272){\makebox(0,0){$\ast$}}
\put(1091,276){\makebox(0,0){$\ast$}}
\put(1117,270){\makebox(0,0){$\ast$}}
\put(1142,273){\makebox(0,0){$\ast$}}
\put(1168,276){\makebox(0,0){$\ast$}}
\put(1193,279){\makebox(0,0){$\ast$}}
\put(1219,273){\makebox(0,0){$\ast$}}
\put(1245,276){\makebox(0,0){$\ast$}}
\put(1270,279){\makebox(0,0){$\ast$}}
\put(1296,282){\makebox(0,0){$\ast$}}
\put(1321,277){\makebox(0,0){$\ast$}}
\put(1347,279){\makebox(0,0){$\ast$}}
\put(1372,282){\makebox(0,0){$\ast$}}
\put(1398,285){\makebox(0,0){$\ast$}}
\put(1423,279){\makebox(0,0){$\ast$}}
\put(1449,282){\makebox(0,0){$\ast$}}
\put(641,737){\makebox(0,0){$\ast$}}
\sbox{\plotpoint}{\rule[-0.500pt]{1.000pt}{1.000pt}}%
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(571,696){\makebox(0,0)[r]{Hybrid, 87.5\%}}
\sbox{\plotpoint}{\rule[-0.500pt]{1.000pt}{1.000pt}}%
\put(222,176){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(248,184){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(273,190){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(299,200){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(324,210){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(350,220){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(375,230){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(401,223){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(427,231){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(452,239){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(478,248){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(503,256){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(529,264){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(554,272){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(580,281){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(606,266){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(631,273){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(657,280){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(682,287){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(708,294){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(733,301){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(759,307){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(784,314){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(810,297){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(836,303){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(861,309){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(887,315){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(912,321){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(938,327){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(963,333){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(989,339){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1014,321){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1040,326){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1066,331){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1091,336){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1117,341){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1142,346){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1168,352){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1193,357){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1219,339){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1245,343){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1270,348){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1296,353){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1321,357){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1347,362){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1372,366){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1398,371){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1423,353){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(1449,358){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\put(641,696){\raisebox{-.8pt}{\makebox(0,0){$\Box$}}}
\sbox{\plotpoint}{\rule[-0.600pt]{1.200pt}{1.200pt}}%
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(571,655){\makebox(0,0)[r]{Hybrid, 95\%}}
\sbox{\plotpoint}{\rule[-0.600pt]{1.200pt}{1.200pt}}%
\put(222,176){\makebox(0,0){$\blacktriangledown$}}
\put(248,184){\makebox(0,0){$\blacktriangledown$}}
\put(273,190){\makebox(0,0){$\blacktriangledown$}}
\put(299,200){\makebox(0,0){$\blacktriangledown$}}
\put(324,210){\makebox(0,0){$\blacktriangledown$}}
\put(350,220){\makebox(0,0){$\blacktriangledown$}}
\put(375,230){\makebox(0,0){$\blacktriangledown$}}
\put(401,241){\makebox(0,0){$\blacktriangledown$}}
\put(427,251){\makebox(0,0){$\blacktriangledown$}}
\put(452,261){\makebox(0,0){$\blacktriangledown$}}
\put(478,272){\makebox(0,0){$\blacktriangledown$}}
\put(503,282){\makebox(0,0){$\blacktriangledown$}}
\put(529,293){\makebox(0,0){$\blacktriangledown$}}
\put(554,303){\makebox(0,0){$\blacktriangledown$}}
\put(580,313){\makebox(0,0){$\blacktriangledown$}}
\put(606,324){\makebox(0,0){$\blacktriangledown$}}
\put(631,334){\makebox(0,0){$\blacktriangledown$}}
\put(657,344){\makebox(0,0){$\blacktriangledown$}}
\put(682,355){\makebox(0,0){$\blacktriangledown$}}
\put(708,322){\makebox(0,0){$\blacktriangledown$}}
\put(733,330){\makebox(0,0){$\blacktriangledown$}}
\put(759,339){\makebox(0,0){$\blacktriangledown$}}
\put(784,347){\makebox(0,0){$\blacktriangledown$}}
\put(810,355){\makebox(0,0){$\blacktriangledown$}}
\put(836,364){\makebox(0,0){$\blacktriangledown$}}
\put(861,372){\makebox(0,0){$\blacktriangledown$}}
\put(887,380){\makebox(0,0){$\blacktriangledown$}}
\put(912,388){\makebox(0,0){$\blacktriangledown$}}
\put(938,397){\makebox(0,0){$\blacktriangledown$}}
\put(963,405){\makebox(0,0){$\blacktriangledown$}}
\put(989,413){\makebox(0,0){$\blacktriangledown$}}
\put(1014,422){\makebox(0,0){$\blacktriangledown$}}
\put(1040,430){\makebox(0,0){$\blacktriangledown$}}
\put(1066,438){\makebox(0,0){$\blacktriangledown$}}
\put(1091,447){\makebox(0,0){$\blacktriangledown$}}
\put(1117,455){\makebox(0,0){$\blacktriangledown$}}
\put(1142,463){\makebox(0,0){$\blacktriangledown$}}
\put(1168,472){\makebox(0,0){$\blacktriangledown$}}
\put(1193,480){\makebox(0,0){$\blacktriangledown$}}
\put(1219,432){\makebox(0,0){$\blacktriangledown$}}
\put(1245,439){\makebox(0,0){$\blacktriangledown$}}
\put(1270,446){\makebox(0,0){$\blacktriangledown$}}
\put(1296,453){\makebox(0,0){$\blacktriangledown$}}
\put(1321,460){\makebox(0,0){$\blacktriangledown$}}
\put(1347,466){\makebox(0,0){$\blacktriangledown$}}
\put(1372,473){\makebox(0,0){$\blacktriangledown$}}
\put(1398,480){\makebox(0,0){$\blacktriangledown$}}
\put(1423,487){\makebox(0,0){$\blacktriangledown$}}
\put(1449,494){\makebox(0,0){$\blacktriangledown$}}
\put(641,655){\makebox(0,0){$\blacktriangledown$}}
\sbox{\plotpoint}{\rule[-0.500pt]{1.000pt}{1.000pt}}%
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(571,614){\makebox(0,0)[r]{Hybrid, 98.7\%}}
\sbox{\plotpoint}{\rule[-0.500pt]{1.000pt}{1.000pt}}%
\put(222,176){\makebox(0,0){$\circ$}}
\put(248,184){\makebox(0,0){$\circ$}}
\put(273,190){\makebox(0,0){$\circ$}}
\put(299,200){\makebox(0,0){$\circ$}}
\put(324,210){\makebox(0,0){$\circ$}}
\put(350,220){\makebox(0,0){$\circ$}}
\put(375,230){\makebox(0,0){$\circ$}}
\put(401,241){\makebox(0,0){$\circ$}}
\put(427,251){\makebox(0,0){$\circ$}}
\put(452,261){\makebox(0,0){$\circ$}}
\put(478,272){\makebox(0,0){$\circ$}}
\put(503,282){\makebox(0,0){$\circ$}}
\put(529,293){\makebox(0,0){$\circ$}}
\put(554,303){\makebox(0,0){$\circ$}}
\put(580,313){\makebox(0,0){$\circ$}}
\put(606,324){\makebox(0,0){$\circ$}}
\put(631,334){\makebox(0,0){$\circ$}}
\put(657,344){\makebox(0,0){$\circ$}}
\put(682,355){\makebox(0,0){$\circ$}}
\put(708,365){\makebox(0,0){$\circ$}}
\put(733,376){\makebox(0,0){$\circ$}}
\put(759,386){\makebox(0,0){$\circ$}}
\put(784,396){\makebox(0,0){$\circ$}}
\put(810,407){\makebox(0,0){$\circ$}}
\put(836,417){\makebox(0,0){$\circ$}}
\put(861,428){\makebox(0,0){$\circ$}}
\put(887,438){\makebox(0,0){$\circ$}}
\put(912,448){\makebox(0,0){$\circ$}}
\put(938,459){\makebox(0,0){$\circ$}}
\put(963,469){\makebox(0,0){$\circ$}}
\put(989,480){\makebox(0,0){$\circ$}}
\put(1014,490){\makebox(0,0){$\circ$}}
\put(1040,500){\makebox(0,0){$\circ$}}
\put(1066,511){\makebox(0,0){$\circ$}}
\put(1091,521){\makebox(0,0){$\circ$}}
\put(1117,532){\makebox(0,0){$\circ$}}
\put(1142,542){\makebox(0,0){$\circ$}}
\put(1168,552){\makebox(0,0){$\circ$}}
\put(1193,563){\makebox(0,0){$\circ$}}
\put(1219,573){\makebox(0,0){$\circ$}}
\put(1245,584){\makebox(0,0){$\circ$}}
\put(1270,594){\makebox(0,0){$\circ$}}
\put(1296,604){\makebox(0,0){$\circ$}}
\put(1321,615){\makebox(0,0){$\circ$}}
\put(1347,625){\makebox(0,0){$\circ$}}
\put(1372,636){\makebox(0,0){$\circ$}}
\put(1398,646){\makebox(0,0){$\circ$}}
\put(1423,656){\makebox(0,0){$\circ$}}
\put(1449,667){\makebox(0,0){$\circ$}}
\put(641,614){\makebox(0,0){$\circ$}}
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(571,573){\makebox(0,0)[r]{Pipelined}}
\put(222,173){\makebox(0,0){$\bullet$}}
\put(248,186){\makebox(0,0){$\bullet$}}
\put(273,200){\makebox(0,0){$\bullet$}}
\put(299,214){\makebox(0,0){$\bullet$}}
\put(324,228){\makebox(0,0){$\bullet$}}
\put(350,242){\makebox(0,0){$\bullet$}}
\put(375,256){\makebox(0,0){$\bullet$}}
\put(401,270){\makebox(0,0){$\bullet$}}
\put(427,284){\makebox(0,0){$\bullet$}}
\put(452,297){\makebox(0,0){$\bullet$}}
\put(478,311){\makebox(0,0){$\bullet$}}
\put(503,325){\makebox(0,0){$\bullet$}}
\put(529,339){\makebox(0,0){$\bullet$}}
\put(554,353){\makebox(0,0){$\bullet$}}
\put(580,367){\makebox(0,0){$\bullet$}}
\put(606,381){\makebox(0,0){$\bullet$}}
\put(631,394){\makebox(0,0){$\bullet$}}
\put(657,408){\makebox(0,0){$\bullet$}}
\put(682,422){\makebox(0,0){$\bullet$}}
\put(708,436){\makebox(0,0){$\bullet$}}
\put(733,450){\makebox(0,0){$\bullet$}}
\put(759,464){\makebox(0,0){$\bullet$}}
\put(784,478){\makebox(0,0){$\bullet$}}
\put(810,492){\makebox(0,0){$\bullet$}}
\put(836,505){\makebox(0,0){$\bullet$}}
\put(861,519){\makebox(0,0){$\bullet$}}
\put(887,533){\makebox(0,0){$\bullet$}}
\put(912,547){\makebox(0,0){$\bullet$}}
\put(938,561){\makebox(0,0){$\bullet$}}
\put(963,575){\makebox(0,0){$\bullet$}}
\put(989,589){\makebox(0,0){$\bullet$}}
\put(1014,602){\makebox(0,0){$\bullet$}}
\put(1040,616){\makebox(0,0){$\bullet$}}
\put(1066,630){\makebox(0,0){$\bullet$}}
\put(1091,644){\makebox(0,0){$\bullet$}}
\put(1117,658){\makebox(0,0){$\bullet$}}
\put(1142,672){\makebox(0,0){$\bullet$}}
\put(1168,686){\makebox(0,0){$\bullet$}}
\put(1193,700){\makebox(0,0){$\bullet$}}
\put(1219,713){\makebox(0,0){$\bullet$}}
\put(1245,727){\makebox(0,0){$\bullet$}}
\put(1270,741){\makebox(0,0){$\bullet$}}
\put(1296,755){\makebox(0,0){$\bullet$}}
\put(1321,769){\makebox(0,0){$\bullet$}}
\put(1347,783){\makebox(0,0){$\bullet$}}
\put(1372,797){\makebox(0,0){$\bullet$}}
\put(1398,810){\makebox(0,0){$\bullet$}}
\put(1423,824){\makebox(0,0){$\bullet$}}
\put(1449,838){\makebox(0,0){$\bullet$}}
\put(641,573){\makebox(0,0){$\bullet$}}
\put(171.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(171.0,131.0){\rule[-0.200pt]{307.870pt}{0.400pt}}
\put(1449.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(171.0,859.0){\rule[-0.200pt]{307.870pt}{0.400pt}}
\end{picture}

cmp13-average.tex
% GNUPLOT: LaTeX picture
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\begin{picture}(885,590)(0,0)
\font\gnuplot=cmr10 at 10pt
\gnuplot
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(171.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,131){\makebox(0,0)[r]{ 0}}
\put(814.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,191.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,191){\makebox(0,0)[r]{ 10}}
\put(814.0,191.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,250.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,250){\makebox(0,0)[r]{ 20}}
\put(814.0,250.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,310.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,310){\makebox(0,0)[r]{ 30}}
\put(814.0,310.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,370.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,370){\makebox(0,0)[r]{ 40}}
\put(814.0,370.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,430.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,430){\makebox(0,0)[r]{ 50}}
\put(814.0,430.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,489.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,489){\makebox(0,0)[r]{ 60}}
\put(814.0,489.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,549.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(151,549){\makebox(0,0)[r]{ 70}}
\put(814.0,549.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(171,90){\makebox(0,0){ 0}}
\put(171.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(237.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(237,90){\makebox(0,0){ 10}}
\put(237.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(304.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(304,90){\makebox(0,0){ 20}}
\put(304.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(370.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(370,90){\makebox(0,0){ 30}}
\put(370.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(436.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(436,90){\makebox(0,0){ 40}}
\put(436.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(502.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(502,90){\makebox(0,0){ 50}}
\put(502.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(569.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(569,90){\makebox(0,0){ 60}}
\put(569.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(635.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(635,90){\makebox(0,0){ 70}}
\put(635.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(701.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(701,90){\makebox(0,0){ 80}}
\put(701.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(768.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(768,90){\makebox(0,0){ 90}}
\put(768.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(834.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(834,90){\makebox(0,0){ 100}}
\put(834.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(171.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(171.0,131.0){\rule[-0.200pt]{159.717pt}{0.400pt}}
\put(834.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(171.0,549.0){\rule[-0.200pt]{159.717pt}{0.400pt}}
\put(50,340){\makebox(0,0){$\mu$}}
\put(502,29){\makebox(0,0){$N$}}
\put(184,144){\makebox(0,0){$+$}}
\put(191,145){\makebox(0,0){$+$}}
\put(198,145){\makebox(0,0){$+$}}
\put(204,146){\makebox(0,0){$+$}}
\put(211,146){\makebox(0,0){$+$}}
\put(217,146){\makebox(0,0){$+$}}
\put(224,146){\makebox(0,0){$+$}}
\put(231,146){\makebox(0,0){$+$}}
\put(237,146){\makebox(0,0){$+$}}
\put(244,146){\makebox(0,0){$+$}}
\put(251,146){\makebox(0,0){$+$}}
\put(257,146){\makebox(0,0){$+$}}
\put(264,146){\makebox(0,0){$+$}}
\put(270,146){\makebox(0,0){$+$}}
\put(277,146){\makebox(0,0){$+$}}
\put(284,146){\makebox(0,0){$+$}}
\put(290,146){\makebox(0,0){$+$}}
\put(297,147){\makebox(0,0){$+$}}
\put(304,147){\makebox(0,0){$+$}}
\put(310,147){\makebox(0,0){$+$}}
\put(317,147){\makebox(0,0){$+$}}
\put(323,147){\makebox(0,0){$+$}}
\put(330,147){\makebox(0,0){$+$}}
\put(337,147){\makebox(0,0){$+$}}
\put(343,147){\makebox(0,0){$+$}}
\put(350,147){\makebox(0,0){$+$}}
\put(357,147){\makebox(0,0){$+$}}
\put(363,147){\makebox(0,0){$+$}}
\put(370,147){\makebox(0,0){$+$}}
\put(377,147){\makebox(0,0){$+$}}
\put(383,147){\makebox(0,0){$+$}}
\put(390,147){\makebox(0,0){$+$}}
\put(396,147){\makebox(0,0){$+$}}
\put(403,147){\makebox(0,0){$+$}}
\put(410,147){\makebox(0,0){$+$}}
\put(416,147){\makebox(0,0){$+$}}
\put(423,147){\makebox(0,0){$+$}}
\put(430,147){\makebox(0,0){$+$}}
\put(436,147){\makebox(0,0){$+$}}
\put(443,147){\makebox(0,0){$+$}}
\put(449,147){\makebox(0,0){$+$}}
\put(456,147){\makebox(0,0){$+$}}
\put(463,147){\makebox(0,0){$+$}}
\put(469,147){\makebox(0,0){$+$}}
\put(476,147){\makebox(0,0){$+$}}
\put(483,147){\makebox(0,0){$+$}}
\put(489,147){\makebox(0,0){$+$}}
\put(496,147){\makebox(0,0){$+$}}
\put(502,147){\makebox(0,0){$+$}}
\put(509,147){\makebox(0,0){$+$}}
\put(516,147){\makebox(0,0){$+$}}
\put(522,147){\makebox(0,0){$+$}}
\put(529,147){\makebox(0,0){$+$}}
\put(536,147){\makebox(0,0){$+$}}
\put(542,147){\makebox(0,0){$+$}}
\put(549,147){\makebox(0,0){$+$}}
\put(556,147){\makebox(0,0){$+$}}
\put(562,147){\makebox(0,0){$+$}}
\put(569,147){\makebox(0,0){$+$}}
\put(575,147){\makebox(0,0){$+$}}
\put(582,147){\makebox(0,0){$+$}}
\put(589,147){\makebox(0,0){$+$}}
\put(595,147){\makebox(0,0){$+$}}
\put(602,147){\makebox(0,0){$+$}}
\put(609,147){\makebox(0,0){$+$}}
\put(615,147){\makebox(0,0){$+$}}
\put(622,147){\makebox(0,0){$+$}}
\put(628,147){\makebox(0,0){$+$}}
\put(635,147){\makebox(0,0){$+$}}
\put(642,147){\makebox(0,0){$+$}}
\put(648,147){\makebox(0,0){$+$}}
\put(655,147){\makebox(0,0){$+$}}
\put(662,147){\makebox(0,0){$+$}}
\put(668,147){\makebox(0,0){$+$}}
\put(675,147){\makebox(0,0){$+$}}
\put(682,147){\makebox(0,0){$+$}}
\put(688,147){\makebox(0,0){$+$}}
\put(695,147){\makebox(0,0){$+$}}
\put(701,147){\makebox(0,0){$+$}}
\put(708,147){\makebox(0,0){$+$}}
\put(715,147){\makebox(0,0){$+$}}
\put(721,147){\makebox(0,0){$+$}}
\put(728,147){\makebox(0,0){$+$}}
\put(735,147){\makebox(0,0){$+$}}
\put(741,147){\makebox(0,0){$+$}}
\put(748,147){\makebox(0,0){$+$}}
\put(754,147){\makebox(0,0){$+$}}
\put(761,147){\makebox(0,0){$+$}}
\put(768,147){\makebox(0,0){$+$}}
\put(774,147){\makebox(0,0){$+$}}
\put(781,147){\makebox(0,0){$+$}}
\put(788,147){\makebox(0,0){$+$}}
\put(794,147){\makebox(0,0){$+$}}
\put(801,147){\makebox(0,0){$+$}}
\put(807,147){\makebox(0,0){$+$}}
\put(814,147){\makebox(0,0){$+$}}
\put(821,147){\makebox(0,0){$+$}}
\put(827,147){\makebox(0,0){$+$}}
\put(834,147){\makebox(0,0){$+$}}
\put(184,143){\makebox(0,0){$\times$}}
\put(191,147){\makebox(0,0){$\times$}}
\put(198,151){\makebox(0,0){$\times$}}
\put(204,155){\makebox(0,0){$\times$}}
\put(211,159){\makebox(0,0){$\times$}}
\put(217,163){\makebox(0,0){$\times$}}
\put(224,167){\makebox(0,0){$\times$}}
\put(231,171){\makebox(0,0){$\times$}}
\put(237,175){\makebox(0,0){$\times$}}
\put(244,179){\makebox(0,0){$\times$}}
\put(251,183){\makebox(0,0){$\times$}}
\put(257,187){\makebox(0,0){$\times$}}
\put(264,191){\makebox(0,0){$\times$}}
\put(270,195){\makebox(0,0){$\times$}}
\put(277,199){\makebox(0,0){$\times$}}
\put(284,203){\makebox(0,0){$\times$}}
\put(290,207){\makebox(0,0){$\times$}}
\put(297,211){\makebox(0,0){$\times$}}
\put(304,215){\makebox(0,0){$\times$}}
\put(310,219){\makebox(0,0){$\times$}}
\put(317,223){\makebox(0,0){$\times$}}
\put(323,227){\makebox(0,0){$\times$}}
\put(330,231){\makebox(0,0){$\times$}}
\put(337,235){\makebox(0,0){$\times$}}
\put(343,238){\makebox(0,0){$\times$}}
\put(350,242){\makebox(0,0){$\times$}}
\put(357,246){\makebox(0,0){$\times$}}
\put(363,250){\makebox(0,0){$\times$}}
\put(370,254){\makebox(0,0){$\times$}}
\put(377,258){\makebox(0,0){$\times$}}
\put(383,262){\makebox(0,0){$\times$}}
\put(390,266){\makebox(0,0){$\times$}}
\put(396,270){\makebox(0,0){$\times$}}
\put(403,274){\makebox(0,0){$\times$}}
\put(410,278){\makebox(0,0){$\times$}}
\put(416,282){\makebox(0,0){$\times$}}
\put(423,286){\makebox(0,0){$\times$}}
\put(430,290){\makebox(0,0){$\times$}}
\put(436,294){\makebox(0,0){$\times$}}
\put(443,298){\makebox(0,0){$\times$}}
\put(449,302){\makebox(0,0){$\times$}}
\put(456,306){\makebox(0,0){$\times$}}
\put(463,310){\makebox(0,0){$\times$}}
\put(469,314){\makebox(0,0){$\times$}}
\put(476,318){\makebox(0,0){$\times$}}
\put(483,322){\makebox(0,0){$\times$}}
\put(489,326){\makebox(0,0){$\times$}}
\put(496,330){\makebox(0,0){$\times$}}
\put(502,334){\makebox(0,0){$\times$}}
\put(509,338){\makebox(0,0){$\times$}}
\put(516,342){\makebox(0,0){$\times$}}
\put(522,346){\makebox(0,0){$\times$}}
\put(529,350){\makebox(0,0){$\times$}}
\put(536,354){\makebox(0,0){$\times$}}
\put(542,358){\makebox(0,0){$\times$}}
\put(549,362){\makebox(0,0){$\times$}}
\put(556,366){\makebox(0,0){$\times$}}
\put(562,370){\makebox(0,0){$\times$}}
\put(569,374){\makebox(0,0){$\times$}}
\put(575,378){\makebox(0,0){$\times$}}
\put(582,382){\makebox(0,0){$\times$}}
\put(589,386){\makebox(0,0){$\times$}}
\put(595,390){\makebox(0,0){$\times$}}
\put(602,394){\makebox(0,0){$\times$}}
\put(609,398){\makebox(0,0){$\times$}}
\put(615,402){\makebox(0,0){$\times$}}
\put(622,406){\makebox(0,0){$\times$}}
\put(628,410){\makebox(0,0){$\times$}}
\put(635,414){\makebox(0,0){$\times$}}
\put(642,418){\makebox(0,0){$\times$}}
\put(648,422){\makebox(0,0){$\times$}}
\put(655,426){\makebox(0,0){$\times$}}
\put(662,430){\makebox(0,0){$\times$}}
\put(668,434){\makebox(0,0){$\times$}}
\put(675,438){\makebox(0,0){$\times$}}
\put(682,442){\makebox(0,0){$\times$}}
\put(688,445){\makebox(0,0){$\times$}}
\put(695,449){\makebox(0,0){$\times$}}
\put(701,453){\makebox(0,0){$\times$}}
\put(708,457){\makebox(0,0){$\times$}}
\put(715,461){\makebox(0,0){$\times$}}
\put(721,465){\makebox(0,0){$\times$}}
\put(728,469){\makebox(0,0){$\times$}}
\put(735,473){\makebox(0,0){$\times$}}
\put(741,477){\makebox(0,0){$\times$}}
\put(748,481){\makebox(0,0){$\times$}}
\put(754,485){\makebox(0,0){$\times$}}
\put(761,489){\makebox(0,0){$\times$}}
\put(768,493){\makebox(0,0){$\times$}}
\put(774,497){\makebox(0,0){$\times$}}
\put(781,501){\makebox(0,0){$\times$}}
\put(788,505){\makebox(0,0){$\times$}}
\put(794,509){\makebox(0,0){$\times$}}
\put(801,513){\makebox(0,0){$\times$}}
\put(807,517){\makebox(0,0){$\times$}}
\put(814,521){\makebox(0,0){$\times$}}
\put(821,525){\makebox(0,0){$\times$}}
\put(827,529){\makebox(0,0){$\times$}}
\put(834,533){\makebox(0,0){$\times$}}
\put(171.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(171.0,131.0){\rule[-0.200pt]{159.717pt}{0.400pt}}
\put(834.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(171.0,549.0){\rule[-0.200pt]{159.717pt}{0.400pt}}
\end{picture}

cmp13-steps.tex
% GNUPLOT: LaTeX picture
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\begin{picture}(885,590)(0,0)
\font\gnuplot=cmr10 at 10pt
\gnuplot
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(211.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,131){\makebox(0,0)[r]{ 0}}
\put(814.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,183.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,183){\makebox(0,0)[r]{ 1000}}
\put(814.0,183.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,235.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,235){\makebox(0,0)[r]{ 2000}}
\put(814.0,235.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,288.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,288){\makebox(0,0)[r]{ 3000}}
\put(814.0,288.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,340.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,340){\makebox(0,0)[r]{ 4000}}
\put(814.0,340.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,392.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,392){\makebox(0,0)[r]{ 5000}}
\put(814.0,392.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,444.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,444){\makebox(0,0)[r]{ 6000}}
\put(814.0,444.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,497.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,497){\makebox(0,0)[r]{ 7000}}
\put(814.0,497.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,549.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191,549){\makebox(0,0)[r]{ 8000}}
\put(814.0,549.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(211.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(211,90){\makebox(0,0){ 0}}
\put(211.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(273.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(273,90){\makebox(0,0){ 10}}
\put(273.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(336.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(336,90){\makebox(0,0){ 20}}
\put(336.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(398.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(398,90){\makebox(0,0){ 30}}
\put(398.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(460.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(460,90){\makebox(0,0){ 40}}
\put(460.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(523.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(523,90){\makebox(0,0){ 50}}
\put(523.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(585.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(585,90){\makebox(0,0){ 60}}
\put(585.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(647.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(647,90){\makebox(0,0){ 70}}
\put(647.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(709.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(709,90){\makebox(0,0){ 80}}
\put(709.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(772.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(772,90){\makebox(0,0){ 90}}
\put(772.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(834.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(834,90){\makebox(0,0){ 100}}
\put(834.0,529.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(211.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(211.0,131.0){\rule[-0.200pt]{150.081pt}{0.400pt}}
\put(834.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(211.0,549.0){\rule[-0.200pt]{150.081pt}{0.400pt}}
\put(50,340){\makebox(0,0){$\lambda$}}
\put(522,29){\makebox(0,0){$N$}}
\put(223,131){\makebox(0,0){$+$}}
\put(230,132){\makebox(0,0){$+$}}
\put(236,132){\makebox(0,0){$+$}}
\put(242,132){\makebox(0,0){$+$}}
\put(248,133){\makebox(0,0){$+$}}
\put(255,134){\makebox(0,0){$+$}}
\put(261,134){\makebox(0,0){$+$}}
\put(267,135){\makebox(0,0){$+$}}
\put(273,136){\makebox(0,0){$+$}}
\put(280,137){\makebox(0,0){$+$}}
\put(286,138){\makebox(0,0){$+$}}
\put(292,139){\makebox(0,0){$+$}}
\put(298,140){\makebox(0,0){$+$}}
\put(304,141){\makebox(0,0){$+$}}
\put(311,142){\makebox(0,0){$+$}}
\put(317,144){\makebox(0,0){$+$}}
\put(323,145){\makebox(0,0){$+$}}
\put(329,147){\makebox(0,0){$+$}}
\put(336,148){\makebox(0,0){$+$}}
\put(342,150){\makebox(0,0){$+$}}
\put(348,152){\makebox(0,0){$+$}}
\put(354,154){\makebox(0,0){$+$}}
\put(361,156){\makebox(0,0){$+$}}
\put(367,157){\makebox(0,0){$+$}}
\put(373,160){\makebox(0,0){$+$}}
\put(379,162){\makebox(0,0){$+$}}
\put(385,164){\makebox(0,0){$+$}}
\put(392,166){\makebox(0,0){$+$}}
\put(398,169){\makebox(0,0){$+$}}
\put(404,171){\makebox(0,0){$+$}}
\put(410,174){\makebox(0,0){$+$}}
\put(417,176){\makebox(0,0){$+$}}
\put(423,179){\makebox(0,0){$+$}}
\put(429,182){\makebox(0,0){$+$}}
\put(435,185){\makebox(0,0){$+$}}
\put(442,188){\makebox(0,0){$+$}}
\put(448,191){\makebox(0,0){$+$}}
\put(454,194){\makebox(0,0){$+$}}
\put(460,197){\makebox(0,0){$+$}}
\put(466,200){\makebox(0,0){$+$}}
\put(473,203){\makebox(0,0){$+$}}
\put(479,207){\makebox(0,0){$+$}}
\put(485,210){\makebox(0,0){$+$}}
\put(491,214){\makebox(0,0){$+$}}
\put(498,218){\makebox(0,0){$+$}}
\put(504,221){\makebox(0,0){$+$}}
\put(510,225){\makebox(0,0){$+$}}
\put(516,229){\makebox(0,0){$+$}}
\put(523,233){\makebox(0,0){$+$}}
\put(529,237){\makebox(0,0){$+$}}
\put(535,241){\makebox(0,0){$+$}}
\put(541,245){\makebox(0,0){$+$}}
\put(547,250){\makebox(0,0){$+$}}
\put(554,254){\makebox(0,0){$+$}}
\put(560,258){\makebox(0,0){$+$}}
\put(566,263){\makebox(0,0){$+$}}
\put(572,267){\makebox(0,0){$+$}}
\put(579,272){\makebox(0,0){$+$}}
\put(585,277){\makebox(0,0){$+$}}
\put(591,282){\makebox(0,0){$+$}}
\put(597,287){\makebox(0,0){$+$}}
\put(603,292){\makebox(0,0){$+$}}
\put(610,297){\makebox(0,0){$+$}}
\put(616,302){\makebox(0,0){$+$}}
\put(622,307){\makebox(0,0){$+$}}
\put(628,312){\makebox(0,0){$+$}}
\put(635,318){\makebox(0,0){$+$}}
\put(641,323){\makebox(0,0){$+$}}
\put(647,329){\makebox(0,0){$+$}}
\put(653,334){\makebox(0,0){$+$}}
\put(660,340){\makebox(0,0){$+$}}
\put(666,346){\makebox(0,0){$+$}}
\put(672,351){\makebox(0,0){$+$}}
\put(678,357){\makebox(0,0){$+$}}
\put(684,363){\makebox(0,0){$+$}}
\put(691,369){\makebox(0,0){$+$}}
\put(697,376){\makebox(0,0){$+$}}
\put(703,382){\makebox(0,0){$+$}}
\put(709,388){\makebox(0,0){$+$}}
\put(716,394){\makebox(0,0){$+$}}
\put(722,401){\makebox(0,0){$+$}}
\put(728,408){\makebox(0,0){$+$}}
\put(734,414){\makebox(0,0){$+$}}
\put(741,421){\makebox(0,0){$+$}}
\put(747,428){\makebox(0,0){$+$}}
\put(753,434){\makebox(0,0){$+$}}
\put(759,441){\makebox(0,0){$+$}}
\put(765,448){\makebox(0,0){$+$}}
\put(772,456){\makebox(0,0){$+$}}
\put(778,463){\makebox(0,0){$+$}}
\put(784,470){\makebox(0,0){$+$}}
\put(790,477){\makebox(0,0){$+$}}
\put(797,485){\makebox(0,0){$+$}}
\put(803,492){\makebox(0,0){$+$}}
\put(809,500){\makebox(0,0){$+$}}
\put(815,507){\makebox(0,0){$+$}}
\put(822,515){\makebox(0,0){$+$}}
\put(828,523){\makebox(0,0){$+$}}
\put(834,531){\makebox(0,0){$+$}}
\put(223,131){\makebox(0,0){$\times$}}
\put(230,131){\makebox(0,0){$\times$}}
\put(236,132){\makebox(0,0){$\times$}}
\put(242,132){\makebox(0,0){$\times$}}
\put(248,132){\makebox(0,0){$\times$}}
\put(255,132){\makebox(0,0){$\times$}}
\put(261,132){\makebox(0,0){$\times$}}
\put(267,132){\makebox(0,0){$\times$}}
\put(273,133){\makebox(0,0){$\times$}}
\put(280,133){\makebox(0,0){$\times$}}
\put(286,133){\makebox(0,0){$\times$}}
\put(292,133){\makebox(0,0){$\times$}}
\put(298,133){\makebox(0,0){$\times$}}
\put(304,133){\makebox(0,0){$\times$}}
\put(311,134){\makebox(0,0){$\times$}}
\put(317,134){\makebox(0,0){$\times$}}
\put(323,134){\makebox(0,0){$\times$}}
\put(329,134){\makebox(0,0){$\times$}}
\put(336,134){\makebox(0,0){$\times$}}
\put(342,134){\makebox(0,0){$\times$}}
\put(348,134){\makebox(0,0){$\times$}}
\put(354,135){\makebox(0,0){$\times$}}
\put(361,135){\makebox(0,0){$\times$}}
\put(367,135){\makebox(0,0){$\times$}}
\put(373,135){\makebox(0,0){$\times$}}
\put(379,135){\makebox(0,0){$\times$}}
\put(385,135){\makebox(0,0){$\times$}}
\put(392,136){\makebox(0,0){$\times$}}
\put(398,136){\makebox(0,0){$\times$}}
\put(404,136){\makebox(0,0){$\times$}}
\put(410,136){\makebox(0,0){$\times$}}
\put(417,136){\makebox(0,0){$\times$}}
\put(423,136){\makebox(0,0){$\times$}}
\put(429,136){\makebox(0,0){$\times$}}
\put(435,137){\makebox(0,0){$\times$}}
\put(442,137){\makebox(0,0){$\times$}}
\put(448,137){\makebox(0,0){$\times$}}
\put(454,137){\makebox(0,0){$\times$}}
\put(460,137){\makebox(0,0){$\times$}}
\put(466,137){\makebox(0,0){$\times$}}
\put(473,138){\makebox(0,0){$\times$}}
\put(479,138){\makebox(0,0){$\times$}}
\put(485,138){\makebox(0,0){$\times$}}
\put(491,138){\makebox(0,0){$\times$}}
\put(498,138){\makebox(0,0){$\times$}}
\put(504,138){\makebox(0,0){$\times$}}
\put(510,139){\makebox(0,0){$\times$}}
\put(516,139){\makebox(0,0){$\times$}}
\put(523,139){\makebox(0,0){$\times$}}
\put(529,139){\makebox(0,0){$\times$}}
\put(535,139){\makebox(0,0){$\times$}}
\put(541,139){\makebox(0,0){$\times$}}
\put(547,139){\makebox(0,0){$\times$}}
\put(554,140){\makebox(0,0){$\times$}}
\put(560,140){\makebox(0,0){$\times$}}
\put(566,140){\makebox(0,0){$\times$}}
\put(572,140){\makebox(0,0){$\times$}}
\put(579,140){\makebox(0,0){$\times$}}
\put(585,140){\makebox(0,0){$\times$}}
\put(591,141){\makebox(0,0){$\times$}}
\put(597,141){\makebox(0,0){$\times$}}
\put(603,141){\makebox(0,0){$\times$}}
\put(610,141){\makebox(0,0){$\times$}}
\put(616,141){\makebox(0,0){$\times$}}
\put(622,141){\makebox(0,0){$\times$}}
\put(628,142){\makebox(0,0){$\times$}}
\put(635,142){\makebox(0,0){$\times$}}
\put(641,142){\makebox(0,0){$\times$}}
\put(647,142){\makebox(0,0){$\times$}}
\put(653,142){\makebox(0,0){$\times$}}
\put(660,142){\makebox(0,0){$\times$}}
\put(666,142){\makebox(0,0){$\times$}}
\put(672,143){\makebox(0,0){$\times$}}
\put(678,143){\makebox(0,0){$\times$}}
\put(684,143){\makebox(0,0){$\times$}}
\put(691,143){\makebox(0,0){$\times$}}
\put(697,143){\makebox(0,0){$\times$}}
\put(703,143){\makebox(0,0){$\times$}}
\put(709,144){\makebox(0,0){$\times$}}
\put(716,144){\makebox(0,0){$\times$}}
\put(722,144){\makebox(0,0){$\times$}}
\put(728,144){\makebox(0,0){$\times$}}
\put(734,144){\makebox(0,0){$\times$}}
\put(741,144){\makebox(0,0){$\times$}}
\put(747,144){\makebox(0,0){$\times$}}
\put(753,145){\makebox(0,0){$\times$}}
\put(759,145){\makebox(0,0){$\times$}}
\put(765,145){\makebox(0,0){$\times$}}
\put(772,145){\makebox(0,0){$\times$}}
\put(778,145){\makebox(0,0){$\times$}}
\put(784,145){\makebox(0,0){$\times$}}
\put(790,146){\makebox(0,0){$\times$}}
\put(797,146){\makebox(0,0){$\times$}}
\put(803,146){\makebox(0,0){$\times$}}
\put(809,146){\makebox(0,0){$\times$}}
\put(815,146){\makebox(0,0){$\times$}}
\put(822,146){\makebox(0,0){$\times$}}
\put(828,147){\makebox(0,0){$\times$}}
\put(834,147){\makebox(0,0){$\times$}}
\put(211.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(211.0,131.0){\rule[-0.200pt]{150.081pt}{0.400pt}}
\put(834.0,131.0){\rule[-0.200pt]{0.400pt}{100.696pt}}
\put(211.0,549.0){\rule[-0.200pt]{150.081pt}{0.400pt}}
\end{picture}

h200.tex
% GNUPLOT: LaTeX picture
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\begin{picture}(1500,900)(0,0)
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(191.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,131){\makebox(0,0)[r]{ 0}}
\put(1429.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,235.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,235){\makebox(0,0)[r]{ 20}}
\put(1429.0,235.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,339.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,339){\makebox(0,0)[r]{ 40}}
\put(1429.0,339.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,443.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,443){\makebox(0,0)[r]{ 60}}
\put(1429.0,443.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,547.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,547){\makebox(0,0)[r]{ 80}}
\put(1429.0,547.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,651.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,651){\makebox(0,0)[r]{ 100}}
\put(1429.0,651.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,755.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,755){\makebox(0,0)[r]{ 120}}
\put(1429.0,755.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,859.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(171,859){\makebox(0,0)[r]{ 140}}
\put(1429.0,859.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(191.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(191,90){\makebox(0,0){ 0}}
\put(191.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(317.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(317,90){\makebox(0,0){ 20}}
\put(317.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(443.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(443,90){\makebox(0,0){ 40}}
\put(443.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(568.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(568,90){\makebox(0,0){ 60}}
\put(568.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(694.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(694,90){\makebox(0,0){ 80}}
\put(694.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(820.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(820,90){\makebox(0,0){ 100}}
\put(820.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(946.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(946,90){\makebox(0,0){ 120}}
\put(946.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1072.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1072,90){\makebox(0,0){ 140}}
\put(1072.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1197.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1197,90){\makebox(0,0){ 160}}
\put(1197.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1323.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1323,90){\makebox(0,0){ 180}}
\put(1323.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1449.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1449,90){\makebox(0,0){ 200}}
\put(1449.0,839.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(191.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(191.0,131.0){\rule[-0.200pt]{303.052pt}{0.400pt}}
\put(1449.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(191.0,859.0){\rule[-0.200pt]{303.052pt}{0.400pt}}
\put(50,495){\rotatebox{90}{\makebox(0,0){Algorithmic parallelism}}
}\put(820,29){\makebox(0,0){$\mathcal H_{200}\times2$}}
\put(197,145){\makebox(0,0){$\times$}}
\put(204,145){\makebox(0,0){$\times$}}
\put(210,145){\makebox(0,0){$\times$}}
\put(216,145){\makebox(0,0){$\times$}}
\put(222,145){\makebox(0,0){$\times$}}
\put(229,145){\makebox(0,0){$\times$}}
\put(235,145){\makebox(0,0){$\times$}}
\put(241,145){\makebox(0,0){$\times$}}
\put(248,146){\makebox(0,0){$\times$}}
\put(254,146){\makebox(0,0){$\times$}}
\put(260,146){\makebox(0,0){$\times$}}
\put(266,146){\makebox(0,0){$\times$}}
\put(273,146){\makebox(0,0){$\times$}}
\put(279,146){\makebox(0,0){$\times$}}
\put(285,146){\makebox(0,0){$\times$}}
\put(292,146){\makebox(0,0){$\times$}}
\put(298,146){\makebox(0,0){$\times$}}
\put(304,146){\makebox(0,0){$\times$}}
\put(311,147){\makebox(0,0){$\times$}}
\put(317,147){\makebox(0,0){$\times$}}
\put(323,147){\makebox(0,0){$\times$}}
\put(329,147){\makebox(0,0){$\times$}}
\put(336,147){\makebox(0,0){$\times$}}
\put(342,147){\makebox(0,0){$\times$}}
\put(348,147){\makebox(0,0){$\times$}}
\put(355,147){\makebox(0,0){$\times$}}
\put(361,147){\makebox(0,0){$\times$}}
\put(367,148){\makebox(0,0){$\times$}}
\put(373,148){\makebox(0,0){$\times$}}
\put(380,148){\makebox(0,0){$\times$}}
\put(386,148){\makebox(0,0){$\times$}}
\put(392,148){\makebox(0,0){$\times$}}
\put(399,148){\makebox(0,0){$\times$}}
\put(405,148){\makebox(0,0){$\times$}}
\put(411,148){\makebox(0,0){$\times$}}
\put(417,148){\makebox(0,0){$\times$}}
\put(424,149){\makebox(0,0){$\times$}}
\put(430,149){\makebox(0,0){$\times$}}
\put(436,149){\makebox(0,0){$\times$}}
\put(443,149){\makebox(0,0){$\times$}}
\put(449,149){\makebox(0,0){$\times$}}
\put(455,149){\makebox(0,0){$\times$}}
\put(461,149){\makebox(0,0){$\times$}}
\put(468,149){\makebox(0,0){$\times$}}
\put(474,150){\makebox(0,0){$\times$}}
\put(480,150){\makebox(0,0){$\times$}}
\put(487,150){\makebox(0,0){$\times$}}
\put(493,150){\makebox(0,0){$\times$}}
\put(499,150){\makebox(0,0){$\times$}}
\put(506,150){\makebox(0,0){$\times$}}
\put(512,150){\makebox(0,0){$\times$}}
\put(518,150){\makebox(0,0){$\times$}}
\put(524,151){\makebox(0,0){$\times$}}
\put(531,151){\makebox(0,0){$\times$}}
\put(537,151){\makebox(0,0){$\times$}}
\put(543,151){\makebox(0,0){$\times$}}
\put(550,151){\makebox(0,0){$\times$}}
\put(556,151){\makebox(0,0){$\times$}}
\put(562,151){\makebox(0,0){$\times$}}
\put(568,152){\makebox(0,0){$\times$}}
\put(575,152){\makebox(0,0){$\times$}}
\put(581,152){\makebox(0,0){$\times$}}
\put(587,152){\makebox(0,0){$\times$}}
\put(594,152){\makebox(0,0){$\times$}}
\put(600,152){\makebox(0,0){$\times$}}
\put(606,152){\makebox(0,0){$\times$}}
\put(612,153){\makebox(0,0){$\times$}}
\put(619,153){\makebox(0,0){$\times$}}
\put(625,153){\makebox(0,0){$\times$}}
\put(631,153){\makebox(0,0){$\times$}}
\put(638,153){\makebox(0,0){$\times$}}
\put(644,153){\makebox(0,0){$\times$}}
\put(650,153){\makebox(0,0){$\times$}}
\put(656,154){\makebox(0,0){$\times$}}
\put(663,154){\makebox(0,0){$\times$}}
\put(669,154){\makebox(0,0){$\times$}}
\put(675,154){\makebox(0,0){$\times$}}
\put(682,154){\makebox(0,0){$\times$}}
\put(688,154){\makebox(0,0){$\times$}}
\put(694,155){\makebox(0,0){$\times$}}
\put(700,155){\makebox(0,0){$\times$}}
\put(707,155){\makebox(0,0){$\times$}}
\put(713,155){\makebox(0,0){$\times$}}
\put(719,155){\makebox(0,0){$\times$}}
\put(726,155){\makebox(0,0){$\times$}}
\put(732,156){\makebox(0,0){$\times$}}
\put(738,156){\makebox(0,0){$\times$}}
\put(745,156){\makebox(0,0){$\times$}}
\put(751,156){\makebox(0,0){$\times$}}
\put(757,156){\makebox(0,0){$\times$}}
\put(763,156){\makebox(0,0){$\times$}}
\put(770,157){\makebox(0,0){$\times$}}
\put(776,157){\makebox(0,0){$\times$}}
\put(782,157){\makebox(0,0){$\times$}}
\put(789,157){\makebox(0,0){$\times$}}
\put(795,157){\makebox(0,0){$\times$}}
\put(801,157){\makebox(0,0){$\times$}}
\put(807,158){\makebox(0,0){$\times$}}
\put(814,158){\makebox(0,0){$\times$}}
\put(820,158){\makebox(0,0){$\times$}}
\put(826,158){\makebox(0,0){$\times$}}
\put(833,158){\makebox(0,0){$\times$}}
\put(839,158){\makebox(0,0){$\times$}}
\put(845,159){\makebox(0,0){$\times$}}
\put(851,159){\makebox(0,0){$\times$}}
\put(858,159){\makebox(0,0){$\times$}}
\put(864,159){\makebox(0,0){$\times$}}
\put(870,159){\makebox(0,0){$\times$}}
\put(877,160){\makebox(0,0){$\times$}}
\put(883,160){\makebox(0,0){$\times$}}
\put(889,160){\makebox(0,0){$\times$}}
\put(895,160){\makebox(0,0){$\times$}}
\put(902,161){\makebox(0,0){$\times$}}
\put(908,161){\makebox(0,0){$\times$}}
\put(914,161){\makebox(0,0){$\times$}}
\put(921,161){\makebox(0,0){$\times$}}
\put(927,161){\makebox(0,0){$\times$}}
\put(933,162){\makebox(0,0){$\times$}}
\put(940,162){\makebox(0,0){$\times$}}
\put(946,162){\makebox(0,0){$\times$}}
\put(952,163){\makebox(0,0){$\times$}}
\put(958,163){\makebox(0,0){$\times$}}
\put(965,163){\makebox(0,0){$\times$}}
\put(971,163){\makebox(0,0){$\times$}}
\put(977,164){\makebox(0,0){$\times$}}
\put(984,164){\makebox(0,0){$\times$}}
\put(990,164){\makebox(0,0){$\times$}}
\put(996,165){\makebox(0,0){$\times$}}
\put(1002,165){\makebox(0,0){$\times$}}
\put(1009,166){\makebox(0,0){$\times$}}
\put(1015,166){\makebox(0,0){$\times$}}
\put(1021,166){\makebox(0,0){$\times$}}
\put(1028,167){\makebox(0,0){$\times$}}
\put(1034,167){\makebox(0,0){$\times$}}
\put(1040,167){\makebox(0,0){$\times$}}
\put(1046,168){\makebox(0,0){$\times$}}
\put(1053,168){\makebox(0,0){$\times$}}
\put(1059,169){\makebox(0,0){$\times$}}
\put(1065,169){\makebox(0,0){$\times$}}
\put(1072,170){\makebox(0,0){$\times$}}
\put(1078,170){\makebox(0,0){$\times$}}
\put(1084,171){\makebox(0,0){$\times$}}
\put(1090,171){\makebox(0,0){$\times$}}
\put(1097,172){\makebox(0,0){$\times$}}
\put(1103,173){\makebox(0,0){$\times$}}
\put(1109,173){\makebox(0,0){$\times$}}
\put(1116,174){\makebox(0,0){$\times$}}
\put(1122,174){\makebox(0,0){$\times$}}
\put(1128,175){\makebox(0,0){$\times$}}
\put(1135,176){\makebox(0,0){$\times$}}
\put(1141,177){\makebox(0,0){$\times$}}
\put(1147,177){\makebox(0,0){$\times$}}
\put(1153,178){\makebox(0,0){$\times$}}
\put(1160,179){\makebox(0,0){$\times$}}
\put(1166,180){\makebox(0,0){$\times$}}
\put(1172,181){\makebox(0,0){$\times$}}
\put(1179,182){\makebox(0,0){$\times$}}
\put(1185,183){\makebox(0,0){$\times$}}
\put(1191,184){\makebox(0,0){$\times$}}
\put(1197,185){\makebox(0,0){$\times$}}
\put(1204,186){\makebox(0,0){$\times$}}
\put(1210,187){\makebox(0,0){$\times$}}
\put(1216,188){\makebox(0,0){$\times$}}
\put(1223,190){\makebox(0,0){$\times$}}
\put(1229,191){\makebox(0,0){$\times$}}
\put(1235,192){\makebox(0,0){$\times$}}
\put(1241,194){\makebox(0,0){$\times$}}
\put(1248,196){\makebox(0,0){$\times$}}
\put(1254,197){\makebox(0,0){$\times$}}
\put(1260,199){\makebox(0,0){$\times$}}
\put(1267,201){\makebox(0,0){$\times$}}
\put(1273,203){\makebox(0,0){$\times$}}
\put(1279,205){\makebox(0,0){$\times$}}
\put(1285,208){\makebox(0,0){$\times$}}
\put(1292,210){\makebox(0,0){$\times$}}
\put(1298,213){\makebox(0,0){$\times$}}
\put(1304,216){\makebox(0,0){$\times$}}
\put(1311,219){\makebox(0,0){$\times$}}
\put(1317,223){\makebox(0,0){$\times$}}
\put(1323,226){\makebox(0,0){$\times$}}
\put(1329,230){\makebox(0,0){$\times$}}
\put(1336,235){\makebox(0,0){$\times$}}
\put(1342,240){\makebox(0,0){$\times$}}
\put(1348,245){\makebox(0,0){$\times$}}
\put(1355,251){\makebox(0,0){$\times$}}
\put(1361,258){\makebox(0,0){$\times$}}
\put(1367,265){\makebox(0,0){$\times$}}
\put(1374,274){\makebox(0,0){$\times$}}
\put(1380,284){\makebox(0,0){$\times$}}
\put(1386,295){\makebox(0,0){$\times$}}
\put(1392,309){\makebox(0,0){$\times$}}
\put(1399,324){\makebox(0,0){$\times$}}
\put(1405,343){\makebox(0,0){$\times$}}
\put(1411,366){\makebox(0,0){$\times$}}
\put(1418,395){\makebox(0,0){$\times$}}
\put(1424,432){\makebox(0,0){$\times$}}
\put(1430,481){\makebox(0,0){$\times$}}
\put(1436,550){\makebox(0,0){$\times$}}
\put(1443,654){\makebox(0,0){$\times$}}
\put(1449,828){\makebox(0,0){$\times$}}
\put(191.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(191.0,131.0){\rule[-0.200pt]{303.052pt}{0.400pt}}
\put(1449.0,131.0){\rule[-0.200pt]{0.400pt}{175.375pt}}
\put(191.0,859.0){\rule[-0.200pt]{303.052pt}{0.400pt}}
\end{picture}

s11.tex
% Beginning of file s11.tex
\documentclass[10pt,twocolumn]{article}
\usepackage{latex8}
\usepackage{times}

\usepackage{rotating}
\usepackage{balance}


\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{subfigure}
\usepackage{amsbsy,amsmath}

\def\P{\hbox{$\mathcal{P}$}}
\def\Q{\hbox{$\mathcal{Q}$}}
\def\H{\hbox{$\mathcal{H}$}}
\def\M{\hbox{$\mathcal{M}$}}
\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\PP}{\bs{\mathcal{P}}}
\newcommand{\QQ}{\bs{\mathcal{Q}}}

%\newtheorem{assumption}{Assumption}{\bf}{\rm}
\newcommand{\keyw}[1]{\hbox{\bf #1}}
\newcommand{\floor}[1]{{\lfloor{#1}\rfloor}}

\DeclareMathAlphabet{\mathscr}{OT1}{pzc}%
                                 {m}{it}

%\ifx\pdfoutput\undefined
\usepackage{graphicx}
\usepackage[dvips]{epsfig}
%\else
%\usepackage[pdftex]{graphicx}
%\fi


\usepackage{listings}
%\usepackage{float}
%\usepackage{alltt}

%%%\ifx\pdfoutput\undefined
%\usepackage[hypertex]{hyperref}
%%%\else
%%%\usepackage[pdftex,colorlinks=true,hyperindex,backref,hypertexnames=false]{hyperref}
%%%\fi
%%%
%%%\hypersetup{%
  %pdftitle={Language-oriented Programming Approach towards User-context Monitoring and Analysis}
  %%%pdfauthor={Vincenzo De Florio},
  %pdfsubject={Language-oriented architectures for EUD}
  %pdfkeywords={Architectures for EUD, language-oriented programming, human-computer interaction, software engineering},
  %%%bookmarksopen=true,
  %%%bookmarksnumbered=true,
  %%%pdfstartview={FitH},
  %%%urlcolor=blue,
%%%}%

\begin{document}
%LNCS%\frontmatter          % for the preliminaries
%
%LNCS%\pagestyle{headings}  % switches on printing of running heads
\pagestyle{empty}
%

%LNCS%\mainmatter

\title{Robust and Tuneable Family\\of Gossiping Algorithms}

\author{Vincenzo De Florio and Chris Blondia\\
University of Antwerp\\
Department of Mathematics and Computer Science\\
Performance Analysis of Telecommunication Systems group\\
Middelheimlaan 1, 2020 Antwerp, Belgium \vspace*{3pt} \\
%\emph{and}\\
Interdisciplinary Institute for Broadband Technology (IBBT)\\
Gaston Crommenlaan 8, 9050 Ghent-Ledeberg, Belgium}

%
\maketitle

\begin{abstract}
	We present a family of gossiping algorithms whose members share the same
structure though they vary their performance in function of a combinatorial parameter.
We show that such parameter may be considered as a ``knob'' controlling
the amount of communication parallelism characterizing the algorithms.
After this we introduce procedures to operate the knob and choose parameters
matching the amount of communication channels currently
provided by the available communication system(s). In so doing we
provide a robust mechanism to tune the production of requests for communication
after the current operational conditions of the consumers of such
requests. This can be used to achieve high performance
and programmatic avoidance of undesirable events such as message collisions.
\end{abstract}

\section{Introduction}
The main character in this text is a family
of algorithms for distributed gossiping whose members differ in
the strategy adopted to discipline the right to transmit. That strategy
can be expressed as a permutation of the indices of the participants.
In~\cite{DeFl06b} a formal model for this family
of algorithms was introduced and the performance of some of its members
was analyzed.
In the cited paper in particular it was shown how the choice of the structure of the permutations controlling
these algorithms
translates in different requirements on the underlying communication system---namely,
different amounts of concurrent send and receive requests.

The focus of this paper is not on the functional properties of the gossiping algorithms but rather
on the non-functional characteristics exhibited by them with the change of the adopted permutations.
Building on top of our past research, here we first show that by assigning different classes of
permutations to the participants
it is possible to scale dynamically the amount of communication requests triggered by the execution
of our algorithm. In other words, this enables the expression of a spectrum of codes each characterized by
a different algorithmic parallelism.

Secondly, we show here how this can be used to reach
an optimal match with the contextual (that is, physical) parallelism
provided by the deployment platform and networks.
Such an optimal tuning allows the avoidance of 
shortcoming and excess of algorithmic parallelism. While in the former case
one would under-utilize the available resources, in the latter case one would
issue a number of requests higher than the available communication resources,
which could lead to undesirable conditions such as 
overloading of request queues and packet collisions.

In what follows we first define our family of algorithms and concisely recall
its characteristics in Sect.~\ref{s:algo}.
Next, in Sect.~\ref{s:knob}, we introduce hybrid gossiping---a strategy to tune the
algorithmic parallelism 
in function of the physical parallelism characterizing the current context.
Section~\ref{s:mape} explains how that strategy can be used to design
autonomic evolution engines exploiting hybrid gossiping.
State of the art is then briefly summarized in Sect.~\ref{s:sota}.
Our conclusions follow in Sect.~\ref{s:conc}.

\section{A Family of Gossiping Algorithms}\label{s:algo}

In this section we recall the main features of a family of gossiping algorithms
firstly introduced in~\cite{DeFl06b}.
We refer the reader to the cited paper for a thorough discussion of the features of those algorithms. 
Introductions to gossiping,
which may be concisely defined as all-to-all pairwise inter-process communication,
may be found e.g. in~\cite{Goss,BGRV98,Gon03}.

In what follows we define a formal model for such family of
algorithms and we highlight the characteristics of two of its members.

\subsection{Formal Model}
Let $t$ represent time and $N>0$ be an integer.
We shall consider a set of $N+1$ communicating processes.
We assume that such processes may be uniquely identified via 
integers in $\{0,\dots,N\}$. Processes are deployed in
processing nodes linked together via one or more communication networks.
We shall refer to the set of nodes and networks as to ``the system''.
Nodes are equipped with a limited
number of communication ports. Likewise, networks provide a limited number
of independent full-duplex point-to-point communication lines.
At any time $t$ a new communication can only be initiated if a free port and a free
line are available in the system. If that is not the case, the requesting process is put in a wait state.
Due to resource competition, the number of ports and that of lines vary dynamically.
Depending on the available ports and lines, at any time $t$ 
at most $\mathcal{N}(t)$ send and at most $\mathcal{N}(t)$ receive requests
may be allowed to execute.
Communication is synchronous and blocking.

%In what follows we characterize the processes' intended task and elementary actions.

Processes own some local data they need to share
(for instance, to execute a voting algorithm as in~\cite{DeDL98e} or~\cite{BDB11a}).
In order to do so, each process broadcasts its local data
to all the others through multiple consecutive send requests,
and receives the $N$ data items owned by its fellows via
multiple consecutive receive requests.
A discrete time model is assumed---events occur at discrete time
steps, and during any time step any process can be involved in only
one such event.
More specifically, on a given time step $t$ process $i$ may be:
  \begin{enumerate}
    \item sending a message to process $j, j\neq i$; 
    this is represented as $i\, S^t j$;
    \item receiving a message from process $j, j\neq i$; 
    this is shown as $i\, R^t j$;
    \item blocked, waiting for messages to be received from any process;
    symbol ``$\curvearrowleft$'' will be used to mean this case;
    \item blocked, waiting for a message to be sent, i.e. for an addressee
    to enter the receiving state.
    Symbol ``$\curvearrowright$'' will be used for this.
\end{enumerate}

A \emph{slot\/} is defined as a process' temporal ``window'' one time step long.
On each given time step $t$, $N+1$ slots are available within the system.
Process $i$ \emph{makes use\/} of slot $t$
if and only if \( \exists \, j \, (i\, S^t j \vee i\, R^t j) \);
on the contrary, process $i$ is said to \emph{waste\/} slot $t$.

By the term ``run'' we shall refer in what follows to the
the collection of slots required to execute the above algorithm on a
given system, as well as to the values of the events corresponding to
those slots.

Let us define the following four state templates:

\begin{description}
\item[$W\!R$ state.]
A process is in state $W\!R_j$ if it is waiting for the arrival of a message
from process $j$. Where the subscript is not important it will be omitted.
Once in $W\!R$, a process stays there for one or more time steps, corresponding to the same number
of ``$\curvearrowleft$'' actions.

\item[$S$ state.]
A process $i$ is in state $S_j$ when it is sending a message to process $j$.
After one time step $i$ leaves state $S_j$.
This corresponds to one $i\, S^t j$ action.

\item[$W\!S$ state.]
A process $i$ waiting to send process $j$ its message is said to be in
state $W\!S_j$. Where the subscript is not important it will be omitted.
Once in $W\!S_j$, process $i$ stays there for one or more time steps, corresponding to the same number
of ``$\curvearrowright$'' actions.

\item[$R$ state.]
When process $i$ is receiving a message from process $j$, it is said to be in
state $R_j$. This state transition also lasts one time step and corresponds to action
$i\, R^t j$.
\end{description}

Let
${\P}_1,\dots,{\P}_N$ represent a permutation of
integers $0,\dots,i-1,i+1,\dots,N$.
Then the above state templates can be used to compose $N+1$
finite state automata as described in Algorithm~1.

\begin{algorithm*}
%\begin{small}
\begin{center}\parbox{0cm}{\begin{tabbing}
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xxxxx \= xx \kill
       %%\> \> \textbf{Algorithm~1: \hskip1pt Compose the FSA solving gossiping}\\
	 \> \> \textbf{Algorithm~1: Compose the FSA solving gossiping}\\
	 \> \> \> \> \> \> \> \textbf{for process $i\in\{0,\dots,N\}$}\\
         \> \> \emph{Input:\/} $A \equiv (i, N, \P)$\\
         \> \> \emph{Output:\/} $\mathrm{FSA}(A)$\\
{\bf  1} \> \> \keyw{begin}\\
         \> \> \> /* emit the initial state */ \\
{\bf  2} \> \> \> $\mathrm{FSA}(A) := \mathrm{START}$\\
{\bf  3} \> \> \> \keyw{for} $j := 0$ \keyw{to} $i-1$ \keyw{do} \\
         \> \> \> \> /* operator ``$\leftarrow$'' appends a new state to the FSA */ \\
{\bf  4} \> \> \> \> $\mathrm{FSA}(A) \leftarrow W\!R$ \\
{\bf  5} \> \> \> \> $\mathrm{FSA}(A) \leftarrow R$ \\
{\bf  6} \> \> \> \keyw{enddo}\\
{\bf  7} \> \> \> \keyw{for} $j := 1$ \keyw{to} $N$ \keyw{do} \\
{\bf  8} \> \> \> \> $\mathrm{FSA}(A) \leftarrow W\!S_{{\P}_j}$\\
{\bf  9} \> \> \> \> $\mathrm{FSA}(A) \leftarrow S_{{\P}_j}$\\
{\bf 10} \> \> \> \keyw{enddo}\\
{\bf 11} \> \> \> \keyw{for} $j := i+1$ \keyw{to} $N$ \keyw{do}\\
{\bf 12} \> \> \> \> $\mathrm{FSA}(A) \leftarrow W\!R$\\
{\bf 13} \> \> \> \> $\mathrm{FSA}(A) \leftarrow R$\\
{\bf 14} \> \> \> \keyw{enddo}\\
         \> \> \> /* emit the final state */ \\
{\bf 15} \> \> \> $\mathrm{FSA}(A) \leftarrow \mathrm{STOP}$\\
{\bf 16} \> \> \keyw{end}.
\end{tabbing}}
\end{center}
%\end{small}
%\caption{Procedure to compose the finite state automaton of process $i$.}\label{a:goss}
\end{algorithm*}

Figure~\ref{fsa} shows the finite state automaton that solves distributed
gossiping for process $i$, which we obtained by executing Alg.~1.
The first row is the condition that has to be reached before
process $i$ is allowed to begin its broadcast: a series
of $i$ \( (W\!R, R) \) couples.

\begin{figure*}[t]
%\centerline{\psfig{figure=fsa2.eps,width=13cm}}
\centerline{\psfig{figure=okdraw1.eps,width=0.86\textwidth}}
\caption{The state diagram of the FSA run by process $i$. The first
row consists of $i$ \( (W\!R, R) \) couples.
$({\P}_1,\dots,{\P}_N)$ represents a permutation of the $N$ integers
$0,\dots,i-1,i+1,\dots,N$.
The last row contains $N-i$ \( (W\!R, R) \) couples.}
\label{fsa}
\end{figure*}

Once process $i$ has successfully received $i$ messages, it acquires
the right to broadcast. Broadcasting is performed according to the rule expressed in
the second row of Fig.~\ref{fsa}: process $i$ orderly sends its message to
its fellows, the $j$-th message being sent to process ${\P}_j$.

The third row of Fig.~\ref{fsa} instructs the reception of the remaining $N-i$ messages,
which is coded as a sequence of $N-i$ \( (W\!R, R) \) couples.

In~\cite{DeFl06b} it was shown how, irrespective of the value of $\P$, such FSA's
implement a distributed deadlock-free gossiping algorithm.
As intuition may suggest, the choice of which permutation to use has
indeed a deep impact
on the overall performance of the algorithm---together
with the physical characteristics of the system. In fact,
different permutations translate in different amounts of
communication parallelism; when such algorithmic parallelism is
backed up by contextual parallelism---that is, by
a sufficiently large number of
independent communication ports and lines in the system,
modeled as dynamic system $\mathcal{N}(t)$---then there is
an optimal match between the algorithm and the deployment
platform.


In order to evaluate the above impact
we shall make use of the following ``quality metrics'':
\begin{description}
\item[Average slot utilization.]
This is the average number of used slots per time step in a given run.
It will be indicated as $\mu_N$, or simply as $\mu$.
$\mu$ can be interpreted as
the average degree of parallelism expressed by the algorithm---hence it will
be referred to also as the ``algorithmic parallelism''.
$\mu$ can take any real value in $[0, N+1]$.

%\item[Efficiency]
%is defined as the percentage of used slots over the total number of slots
%available during a run. $\varepsilon_{N}$, or more simply $\varepsilon$, will
%be used to represent efficiency.

\item[Length.]
This is the number of time steps in a run. It represents a measure
of the time needed for the distributed algorithm to complete.
$\lambda_N$, or more simply $\lambda$, will be used for lengths.
\end{description}



%%\begin{definition}[number of slots]
%%$\sigma(N(t)) = (N(t)+1)\lambda_{N(t)}$ represents the number of slots
%%available within a run of $N(t)+1$ process.\label{sigma}
%%\end{definition}

For any time step $t$, we shall call $\nu_t$ as the number of slots that
were used during $t$.
The $\lambda$-tuple
\( \vec{\nu} = [ \nu_1, \nu_2, \dots, \nu_\lambda ],\)
orderly encoding the number of used slots for
each time step in a run, shall be called ``utilization string.''

In~\cite{DeFl06b} several cases of $\P$ were introduced and discussed.
In particular in the above cited reference it was shown how varying the structure of $\P$
produces quite different values of $\mu$ %
%, $\varepsilon$,
and $\lambda$.
This fact, coupled with physical constraints of the system
as modeled by $\mathcal{N}(t)$,
determine the overall performance of our algorithm.

In what follows we focus on two particular cases representing 
the minimal and maximal algorithmic parallelism.

\subsection{Identity Permutation}

As a first case, 
let $\P$ be the identity permutation:
\begin{equation}\label{zeroperm}
\binom{0,\dots,i-1,i+1,\dots,N}{0,\dots,i-1,i+1,\dots,N},
\end{equation}
i.e., in cycle notation~\cite{Knu73a},
\(
\P = (0)\dots(i-1)(i+1)\dots(N).
\)

This means that, once process $i$ acquires the right to broadcast,
it first sends its message to process 0
(possibly having to wait for it to become available),
then it will do the same with process 1, and so
forth up to process $N$, obviously skipping itself. This is
shown in Table~\ref{run4} for $N=5$. In what follows we shall refer to tables
such as Table~\ref{run4} as to ``run-tables.''

\begin{table*}[t]
%\begin{tiny}
\begin{center}
\begin{tabular}{l@{}|@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}}
$\stackrel{\hbox{\sffamily\scriptsize id}}{\downarrow}\stackrel{\begin{sideways}\hbox{\sffamily\scriptsize step}\end{sideways}}{\rightarrow}$&\tiny1&\tiny2&\tiny3&\tiny4&\tiny5&\tiny6&\tiny7&\tiny8&\tiny9&\tiny10&\tiny11&\tiny12&\tiny13&\tiny14&\tiny15&\tiny16&\tiny17&\tiny18&\tiny19&\tiny20&\tiny21&\tiny22&\tiny23&\tiny24&\tiny25&\tiny26\\\hline
\sf 0&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{5}$&$R_{1}$&$\curvearrowleft$&$R_{2}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{3}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{4}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{5}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 1&$R_{0}$&$\curvearrowright$&$\curvearrowright$&$\curvearrowright$&$\curvearrowright$&$S_{0}$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{5}$&$R_{2}$&$\curvearrowleft$&$\curvearrowleft$&$R_{3}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{4}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{5}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 2&$\curvearrowleft$&$R_{0}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{1}$&$S_{0}$&$\curvearrowright$&$\curvearrowright$&$S_{1}$&$S_{3}$&$S_{4}$&$S_{5}$&$R_{3}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{4}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{5}$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 3&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{1}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{2}$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{4}$&$S_{5}$&$\curvearrowleft$&$\curvearrowleft$&$R_{4}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{5}$&$\curvearrowleft$\\
\sf 4&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{1}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{2}$&$\curvearrowleft$&$\curvearrowleft$&$R_{3}$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{3}$&$S_{5}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{5}$\\
\sf 5&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{1}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{2}$&$\curvearrowleft$&$\curvearrowleft$&$R_{3}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{4}$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$\\
\hline
$\stackrel{\hbox{\sffamily\scriptsize used}}{\rightarrow}$&2&2&2&2&2&2&2&4&2&2&2&2&4&4&2&2&4&2&2&2&2&2&2&2&2&2
\end{tabular}
\end{center}
%\end{tiny}
\caption{Run ($N=5$) for $\P$ equal to the identity permutation.
The {\sf step} row represents time steps. {\sf Id}'s identify
processes. $\vec\nu$ is the utilization string.
In this case
$\mu$ (that is, algorithmic parallelism) is about 2.3077 slots,
%while efficiency $\varepsilon\approx 38.46\%$
and length $\lambda=26$.
Note that, if the slot is a used one, then entry $(i,t)={\mathcal R}_j$ of this matrix
is action $i\, {\mathcal R}^t j$.}\label{run4}
\end{table*}

In~\cite{DeFl06b} it was shown how
it is possible to characterize some properties of the
quality metrics of the member corresponding to the
identity permutation. Among such properties particularly useful here are
the following two ones:
\begin{itemize}
\item The algorithm makes use of $\hbox{O}(N^2)$ time---more precisely,
\(
	\lambda_N = \frac34N^2 + \frac54N + \frac12 \floor{N/2}.
\)
\item The asymptotic value of algorithmic parallelism, that is
\(
	\lim_{k\rightarrow\infty}\mu_k,
\)
equals $\frac83$.
%\item The asymptotic value of efficiency, that is
%\(
	%\lim_{k\rightarrow\infty}\varepsilon_k=0.
%\)
%is 0.
\end{itemize}


%\begin{figure}[t]
%\centerline{\hbox{\psfig{figure=z25.eps,width=0.7\textwidth}}}
%\caption{A graphical representation for run-table 25 when $\P$ is
%the identity permutation. Light gray pixels represent wasted slots,
%gray pixels represent $R$ actions, black slots are sending actions.}
%\label{z25}
%\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Pipelined Permutation}\label{tao-pb}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We now consider a second case---the one corresponding to
permutation

\begin{equation}\label{pipe}
\binom{0,\dots,i-1,i+1,\dots,N}%
      {i+1,\dots,N,0,\dots,i-1}.
\end{equation}

Note how permutation~(\ref{pipe}) is equivalent to $i$ 
cyclic logical left shifts of the identity permutation.

When $\P$ is as in (\ref{pipe}), then
process $i$ first sends its message to process $i+1$,
then to process $i+2$, and so
on until it reaches process $N$. After that, $i$ wraps around
and sends from process 0 to process $i-1$.
This is shown in Table~\ref{run9} for $N=8$.
As can be seen from that table, (\ref{pipe}) maximally overlaps the processes'
broadcast sessions
the same way as machine instructions are being overlapped in
pipelined microprocessors~\cite{He06}. This similarity brought
to the name of ``pipelined permutation'' for (\ref{pipe})~\cite{DeFl06b}. 

%A second similarity between these two seemingly unrelated cases is worth highlighting here.
%In pipelined microprocessors, several limiting factors exist to a true exploitation of the
%parallelism intrinsically available through pipelines. In particular, as a pipeline
%is a series of data-paths from the memory system to the processor, we observe how
%the amount of ``effective'' parallelism that may be derived from the
%potentially unbound ``algorithmic parallelism'' 
%of an instruction pipeline is limited by the physical amount of memory ports available.
%Thus the number of stages in such a pipeline becomes an important design choice
%that must trade off technological
%and economical constraints. In practice, that \emph{immutable\/} number
%will limit both contextual parallelism and costs.
%A similar consideration applies to our family of algorithms and is at the foundations of the
%strategy discussed in Sect.~\ref{s:knob} and used
%to select a member in the family of gossiping algorithms in function of the current context.

\begin{table*}[t]
%\begin{tiny}
\begin{center}
\begin{tabular}{l@{}|@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}}
$\stackrel{\hbox{\sffamily\scriptsize id}}{\downarrow}$ $\stackrel{\begin{sideways}\hbox{\sffamily\scriptsize step}\end{sideways}}{\rightarrow}$&\tiny1&\tiny2&\tiny3&\tiny4&\tiny5&\tiny6&\tiny7&\tiny8&\tiny9&\tiny10&\tiny11&\tiny12&\tiny13&\tiny14&\tiny15&\tiny16&\tiny17&\tiny18&\tiny19&\tiny20&\tiny21&\tiny22&\tiny23&\tiny24\\ \hline
\sf 0&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{5}$&$S_{6}$&$S_{7}$&$S_{8}$&$\curvearrowleft$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$&$R_{5}$&$R_{6}$&$R_{7}$&$R_{8}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 1&$R_{0}$&$\curvearrowright$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{5}$&$S_{6}$&$S_{7}$&$S_{8}$&$S_{0}$&$\curvearrowleft$&$R_{2}$&$R_{3}$&$R_{4}$&$R_{5}$&$R_{6}$&$R_{7}$&$R_{8}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 2&$\curvearrowleft$&$R_{0}$&$R_{1}$&$\curvearrowright$&$S_{3}$&$S_{4}$&$S_{5}$&$S_{6}$&$S_{7}$&$S_{8}$&$S_{0}$&$S_{1}$&$\curvearrowleft$&$R_{3}$&$R_{4}$&$R_{5}$&$R_{6}$&$R_{7}$&$R_{8}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 3&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$R_{1}$&$R_{2}$&$\curvearrowright$&$S_{4}$&$S_{5}$&$S_{6}$&$S_{7}$&$S_{8}$&$S_{0}$&$S_{1}$&$S_{2}$&$\curvearrowleft$&$R_{4}$&$R_{5}$&$R_{6}$&$R_{7}$&$R_{8}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 4&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$\curvearrowright$&$S_{5}$&$S_{6}$&$S_{7}$&$S_{8}$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{3}$&$\curvearrowleft$&$R_{5}$&$R_{6}$&$R_{7}$&$R_{8}$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 5&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$&$\curvearrowright$&$S_{6}$&$S_{7}$&$S_{8}$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$&$\curvearrowleft$&$R_{6}$&$R_{7}$&$R_{8}$&$\curvearrowleft$&$\curvearrowleft$\\
\sf 6&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$&$R_{5}$&$\curvearrowright$&$S_{7}$&$S_{8}$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{5}$&$\curvearrowleft$&$R_{7}$&$R_{8}$&$\curvearrowleft$\\
\sf 7&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$&$R_{5}$&$R_{6}$&$\curvearrowright$&$S_{8}$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{5}$&$S_{6}$&$\curvearrowleft$&$R_{8}$\\
\sf 8&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$\curvearrowleft$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$&$R_{5}$&$R_{6}$&$R_{7}$&$\curvearrowright$&$S_{0}$&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{5}$&$S_{6}$&$S_{7}$\\
\hline
$\stackrel{\hbox{\scriptsize $\vec{\nu}$}}{\rightarrow}$&2&2&4&4&6&6&8&8&8&8&8&8&8&8&8&8&8&8&6&6&4&4&2&2
\end{tabular}
\end{center}
%\end{tiny}
\caption{Run-table for $N=8$ and the pipelined permutation.
In this case algorithmic parallelism is 6
%Efficiency $\varepsilon\approx 66.67\%$ 
and length is 24. Efficiency (channel exploitation) is of 6 slots out of 9, that is 66.67\%.}
%Note that when the permutation is pipelined $\vec\nu$ is a palindrome.}
\label{run9}
\end{table*}


In~\cite{DeFl06b} 
some of the quality metrics of the member corresponding to the
pipelined permutation were also characterized. In particular it was shown that:
\begin{itemize}
\item The algorithm makes use of $\hbox{O}(N)$ time, and more precisely
\(
	\lambda_N = 3N.
\)
\item Algorithmic parallelism linearly depends on the amount of involved processes:
\( \forall k>0: \mu_k = \frac23 (k+1).\)
%\item 
%The efficiency of the algorithm is constant, whatever the amount
%of involved processes:
%\( \forall k>0: \varepsilon_k = 2/3.\)
\end{itemize}


\section{Tuning Algorithmic Parallelism through Hybrid Gossiping}\label{s:knob}
The two cases introduced in the previous section represent
two ``extremes'' in the spectrum of possible permutation structures:
the identity permutation and the pipelined permutation
respectively translate in very low and very high
algorithmic parallelism.
These emerging behaviors characterize \emph{homogeneous\/} gossiping---gossiping
that is in which all processes make use of the same permutation.
A useful property of our family of algorithms is that it also supports
\emph{hybrid\/} gossiping: in this case the gossiping processes make use
of a permutation selected (with some predefined logic) from two or more classes,
as depicted in Fig.~\ref{fsa2}. 
A noteworthy assignment logic is the one that schedules the pipelined permutation
to a certain percentage of the processes and the identity permutation to the
rest. By doing so we experimentally found that the ensuing algorithmic parallelism
grows after the percentage of pipelined permutations assigned to the processes.
In what follows we shall use symbol ``$\H_N$'' 
(or where possible without ambiguity, ``$\H$'') to refer to such percentage.
Figure~\ref{f:avg} shows values of $\mu$ (algorithmic parallelism)
for up to 50 participating processes when various percentages
are used. 

\begin{figure*}[t]
\centerline{\psfig{figure=okdraw2.eps,width=1.0\textwidth}}
\caption{Hybrid gossiping: processes operate using a permutation selected from two or more classes.}
\label{fsa2}
\end{figure*}


\begin{figure*}[t]
\centerline{\input average
}
\caption{Hybrid gossiping produces different amounts
of algorithmic parallelism depending on the scheduling distribution
of the pipelined and identity permutations.}
\label{f:avg}
\end{figure*}




\section{Autonomic System Evolution}\label{s:mape}
The ability to tune algorithmic parallelism paves the way to the definition
of autonomic procedures to evolve the system. In general such evolutions take the
form of a so-called ``MAPE'' adaptation loop~\cite{KeCh:2003}, where MAPE
stands for ``Monitor-Analyze-Plan-Execute''. In the case at hand,
\begin{description}
  \item[Monitor]
      signifies being able to estimate $\mathcal{N}(t)$, 
  \item[Analyze] means
      checking whether $\mu_N$ matches the estimated value of $\mathcal{N}(t)$,
  \item[Plan] is a ``meta-algorithm'' (also known as ``evolution engine''~\cite{DeF11a})
	  responsible for choosing how to evolve the system,
\item[Execute] is the execution of the meta-algorithm and the corresponding
      evolution of the managed system.
\end{description}

In what follows we assume the availability of a monitoring function called
\keyw{sense}. A reflective system such as the one introduced
in~\cite{De10} or~\cite{DB07d} could be used to provide transparent access
to the number of currently available ports and lines---that is, $\mathcal{N}(t)$.
%
The ``Analyze'' step is merely the assessment of
how close the current value of
$\H_N$ is to the estimated value of $\mathcal{N}(t)$. The system would evolve
only in case of two conditions: \emph{overshooting}, that is
a value of $\H_N$ overabundant with respect to that of $\mathcal{N}(t)$, and
\emph{undershooting}---namely, a value of $\H_N$ that would translate
in a sub-optimal exploitation of the available contextual parallelism.
%
In case the system would indeed require adaptation, several
meta-algorithms may be selected for the Planning step depending on e.g. the characteristic
of the mission and the system assumptions: in fact complex planning is likely
to call for non-negligible amounts of system resources, which could
interfere e.g. with real-time requirements. A possible cost-effective
solution for the meta-algorithm could then be to make use of
look-up tables providing for several values of $N$
the algorithmic parallelism corresponding to some sampling of $\H_N$.
Figure~\ref{f:h200} shows 200 samples of $\H_{200}$, which could be
computed off-line and stored in one such look-up table.
%
Algorithm~2 could then be used for the ``Execute'' step.
Alternatively, should performance penalties be deemed preferable
to the memory penalty to store the look-up table,
one could compute the curve best fitting the sampling of $\H_N$ at run-time.

\begin{algorithm*}
\begin{center}\parbox{0cm}{\begin{tabbing}%
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xxxxx \= xx \kill
%%\> \> \textbf{Algorithm~2: \hskip1pt Tune algorithmic parallelism}\\
\> \> \textbf{Algorithm~2: Tune algorithmic parallelism}\\
\> \> \> \> \> \> \> \textbf{after contextual parallelism}\\
\> \> \emph{Input:\/} $\mathcal{N}(t), N$, look-up table $\M_N$; \emph{Output:\/} $\H_{\hbox{best}}$\\
{\bf  1} \> \> \keyw{begin}\\
         \> \> \> /* $cp$ holds the current contextual parallelism */\\
         \> \> \> /* Function \keyw{now} returns current time */\\
{\bf  2} \> \> \> $cp \leftarrow \keyw{sense}(\mathcal{N}(\keyw{now}()))$\\
{\bf  3} \> \> \> $\H_{\hbox{best}} \leftarrow \min \{ h : \M_N(h) \ge cp \}$\\
{\bf  4} \> \> \> \keyw{return} $\H_{\hbox{best}}$ \\
{\bf  5} \> \> \keyw{end}.
\end{tabbing}}
\end{center}
\end{algorithm*}


Another possibility is for instance the one described in
Algorithm~3.
In this case we define $\M_N$ as an associative map, that is,
a growing set of domain-to-value associations
that link known values of $\H_N$ to corresponding known values of $\mu_N$.
A system such as the one described in~\cite{Dev27} could implement such a map.
The specific difference with respect to a look-up table lies in the
dynamic nature of $\M_N$,
as it is possible to add new associations
to it at all times. It is assumed that $\M_N$ is initialized at least
with the associations corresponding
to the identity and the pipelined permutations.
%$\M_N$ would return $\bot$ if no association exists with the specified domain value.

The strategy followed in this case is to return a best match with
the entries currently available in $\M_N$, and
to add new entries to refine dichotomically the list.
The current linear strategy may be replaced by a more efficient one
designed after the non-linear nature of $\mu$.
Figure~\ref{f:2batw} graphically depicts the working of
Algorithm~3 under the following conditions: $N=200$; $\M_{200}$ initially includes only
the identity and pipelined permutations; $\mathcal{N}(t)=13$ for all values of $t$.
At the eighth iteration $|\M_{200}|=9$ and the selected
best value for $\mu$ is 13.11.

\begin{figure*}[t]
	%\begin{tiny}
\centerline{\input h200
}
	%\end{tiny}
\caption{Algorithmic parallelism when $\H_{200}$ varies from 0.5\% to 100\% with step 0.5\%.}
\label{f:h200}
\end{figure*}

\begin{algorithm*}[t]
%\begin{small}
\begin{center}\parbox{0cm}{\begin{tabbing}
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xxxxx \= xx \kill
%%\> \> \textbf{Algorithm~3: \hskip1pt Tune algorithmic parallelism}\\
\> \> \textbf{Algorithm~3: Tune algorithmic parallelism}\\
\> \> \> \> \> \> \> \textbf{after contextual parallelism}\\
         \> \> \emph{Input:\/} $\mathcal{N}(t), N$, associative map $\M_N$;
	 \emph{Output:\/} $\H_{\hbox{best}}$\\
{\bf  1} \> \> \keyw{begin}\\
{\bf  2} \> \> \> $cp \leftarrow \keyw{sense}(\mathcal{N}(\keyw{now}()))$\\
{\bf  3} \> \> \> $\H_{\hbox{best}} \leftarrow \min \{ h : \M_N(h) \ge cp \}$\\
{\bf  4} \> \> \> \keyw{if} $\M_N( \H_{\hbox{best}} ) = cp$ \keyw{then} \keyw{return} $\H_{\hbox{best}}$ \keyw{fi} \\
         \> \> \> /* $\M_N( \H_{\hbox{best}} ) > cp$ */ \\
{\bf  5} \> \> \> $sb \leftarrow 
			\max \{ h : \M_N(h) < \M_N(\H_{\hbox{best}}) \}$\\
{\bf  6} \> \> \> $\H_{\hbox{best}} \leftarrow (\M_N(\H_{\hbox{best}}) - \M_N(sb))/2$\\
\> \> \> /* $\keyw{compute}_\mu$ simulates a run */\\
\> \> \> /* and computes the corresponding $\mu$ */\\
{\bf  7} \> \> \> $\mu \leftarrow \keyw{compute}_\mu(\H_{\hbox{best}})$\\
{\bf  8} \> \> \> $\M_N \leftarrow \M_N \cup \{ \H_{\hbox{best}} \to \mu \}$\\
{\bf  9} \> \> \> \keyw{return} $\H_{\hbox{best}}$\\
{\bf 10} \> \> \keyw{end}.
\end{tabbing}}
\end{center}
%\end{small}
\end{algorithm*}




\begin{figure*}[t]
%\hspace*{-20pt}\psfig{figure=iteration.eps,width=1.1\textwidth}
\centerline{\psfig{figure=s11.eps,width=0.950\textwidth}}
\caption{A graphical representation of Algorithm~3 when $N=200$ and
$\forall t: \mathcal{N}(t)=13$. Logarithmic scales are used.}
\label{f:2batw}
\end{figure*}



\section{State of the Art}\label{s:sota}
In this section we briefly report on methods and strategies to tune
the characteristics of a software system so as to achieve
high performance e.g. through the expression and exploitation of
algorithmic parallelism. 

Concerns such as this
normally are not localized in a single physical module (e.g. a function) or
logical component (e.g., a formal parameter, as it is the case for our gossiping
algorithms);
on the contrary, they often span through several modules and require the
joint evolution of multiple correlated variables. In other words,
the expression of parallelism is a typical \emph{cross-cutting concern}.
A typical way to tackle such concerns is through the usage of
Aspect Oriented Programming (AOP)~\cite{KLM97}.
In AOP the source core consists of two separate ``blocks'':
the functional code dealing with the business logic and the aspect code
to express one or more cross-cutting concerns. The actual source code
is the result of a merging process called weaving where the functional code
is rearranged, instrumented, and patched, according to what
prescribed in the aspect code. This allows software systems to be
effectively evolved so as to maximize one or more target
concerns---including e.g. the expression of algorithmic parallelism~\cite{Sub:2005}.
Widely used in industry and academia, AOP
proved in many cases to be able to manage effectively the complexity of software
evolution.


The general problem of guaranteeing the emergence of certain expected features
or behaviors in a system---software or otherwise---was termed by Jen~\cite{Jen04:Jen}
as ``robust evolvability''. In the cited paper the author defines
evolvability as an entity's ability to
``alter their structure or function so as to adapt to
changing circumstances'' and discusses
a system's capability to retain certain characteristics of interests
(e.g. maximizing algorithmic parallelism)
despite changes in its composition and deployment environment.
Such capability is called by Jen as robustness:
feature persistence under specified and unforeseen perturbations, obtained by
switching among multiple stra\-te\-gic options such that
those changes are dynamically tolerated or even exploited.
Interestingly enough, Jen distinguishes two classes of evolvable systems.
\begin{itemize}
\item Phenotypically plastic systems. Such systems retain their
structure and organization throughout adaptations
and only achieve evolution by switching
among a few, preordained, structurally equivalent configurations that depend on
some internal parameter. Obviously this is the case for our gossiping algorithms.
\item Phenotypically dynamic systems programming system,
which are able to assume
different structures and organizations by mutating the topology,
the role, and the number of their components. An example of this is given
by AOP systems.
%This roughly corresponds
%to compositionally adaptive systems, an example of which is given by
%the above mentioned AOP systems.
\end{itemize}
A deeper discussion and some examples of systems matching the above classes may be found
e.g. in~\cite{DeF11a}.

We believe as worth mentioning here the case of FFTW, an evolvable software system that tunes its
logics so as to maximize performance on a given target platform. FFTW (whose name stands for
``Fastest Fourier Transform in the West'')
is a code generator for Fast Fourier Transforms that defines and assembles
blocks of C code that optimally solve FFT sub-problems
on a given machine~\cite{Fri04}.

Finally we observe how nowadays it is common practice designing software for \emph{families\/} of
target platforms, which selectively enable or disable target-specific
optimizations. One such software is the mplayer video
player~\cite{Mplayer}, which explicitly states such
optimizations with messages such as
``Using optimized IMDCT transform'' or ``Using MMX optimized resampler.''
The same software also permits to instruct the use of a number of threads that matches
optimally the amount of parallelism available on a multi-core target machine.

\section{Conclusions}\label{s:conc}
We presented
the properties of a family of algorithms 
which retain their structural characteristics though vary their operation depending on a
combinatorial parameter. We showed how such
``phenotypically plastic'' system~\cite{Jen04:Jen,DeF11a} may be used
to meet various changing requirements by tuning dynamically the
amount of algorithmic parallelism manifested by the software.
This paves the way to enabling robust control
on the emergence of several properties and behaviors, e.g.
collision avoidance, deterministic upper bounds on energy consumption,
and optimal use of the available communication resources.
Finally we showed how several evolution engines may be adopted to
achieve autonomic context-aware selection of members
that best match the current contextual conditions.


\bibliographystyle{latex8}
%\bibliography{/refs/thesis}
\input s11.bbl

\end{document}

behaviors that 
Each of the corresponding
Here we report on a method to produce permutations 

that three member
whose grade of parallelism is 

Tuning PostgreSQL for performance

Shridhar Daithankar, Josh Berkus

July 3, 2003 Copyright 2003 Shridhar Daithankar and Josh Berkus. 
http://www.varlena.com/GeneralBits/Tidbits/perf.html
``each FSM page uses 6 bytes of RAM for administrative overhead, so increasing
FSM substantially on systems low on RAM may be counter-productive.''



http://www.techrepublic.com/blog/programming-and-development/some-notes-on-aspnets-caching-system/442
As a result, caching a lot of large objects or pages in cache
can end up being counterproductive; 


Content-Aware Caching and Trafc Management in
Content Distribution Networks
Meghana M Amble , Parimal Parag , Srinivas Shakkottai , and Lei Ying
Infocom2011
http://www.ece.tamu.edu/~parimal/Papers/Infocom2011.pdf
However, placing a large demand for a popular piece of content
on the nearest cache might be counterproductive, as the link
capacity between each cache and the end-users is finite


Fastest Fourier Transform in the West approach :)
% End of file s11.tex


The algorithm is a context-aware generalization of the gossiping algorithm 
in~\cite{DeFl06b},
for which we assumed an infinite amount of communication ports and communication channels.
Such unrealistic assumption is not necessary in the algorithm reported here, which dynamically
evolves so as to make the best use of the available channels and ports.

Together with the new formulation of the gossiping algorithm we also describe here its ``evolution engine'', that is
the ``meta''-algorithm responsible for the dynamic tuning of the input permutation of the ``managed'' algorithm.

In what follows we introduce the algorithm through a formal model derived from~\cite{DeFl06b}.

Then in Sect. XXX we introduce the evolution engine 





General idea: 

family of gossiping algorithm depending on a parameter (permutation of participant ids)
solutions exist for particular cases: random, zero, smart\dots and correspond to
certain exploitations / requirements of the parallel channels system

$\mu$ average slot utilization
$\lambda$ duration of one cycle
$\sigma$ total  number of ``slots'' (parallelism)

Identity Permutation: $\lambda = 3/4 n^2 + \dots$

Pseudo-random: $\mu$ approx 3 slots

Pipelined: $\lambda = 3N$
$\varepsilon = 2/3$
$\mu = 2/3 (k+1)$

for a given n, certain 


In the conclusions:

The reported family of algorithms is ``phenotypically plastic''~\cite{Jen04:Jen} in that it retains its general structure
though it evolves its features based on an input parameter. Such parameter is a permutation
of the process identifiers, which is used to represent a total order among the processes.
In turn, this total order determines at any time which among the processes has acquired
the right to transmit.

%LNCS%\bibliographystyle{splncs}
\bibliographystyle{latex8}
\bibliography{/refs/thesis}

\end{document}

behaviors that 
Each of the corresponding
Here we report on a method to produce permutations 

that three member
whose grade of parallelism is 

Tuning PostgreSQL for performance

Shridhar Daithankar, Josh Berkus

July 3, 2003 Copyright 2003 Shridhar Daithankar and Josh Berkus. 
http://www.varlena.com/GeneralBits/Tidbits/perf.html
``each FSM page uses 6 bytes of RAM for administrative overhead, so increasing
FSM substantially on systems low on RAM may be counter-productive.''



http://www.techrepublic.com/blog/programming-and-development/some-notes-on-aspnets-caching-system/442
As a result, caching a lot of large objects or pages in cache
can end up being counterproductive; 


Content-Aware Caching and Trafc Management in
Content Distribution Networks
Meghana M Amble , Parimal Parag , Srinivas Shakkottai , and Lei Ying
Infocom2011
http://www.ece.tamu.edu/~parimal/Papers/Infocom2011.pdf
However, placing a large demand for a popular piece of content
on the nearest cache might be counterproductive, as the link
capacity between each cache and the end-users is finite


Fastest Fourier Transform in the West approach :)
% End of file s11.tex


The algorithm is a context-aware generalization of the gossiping algorithm 
in~\cite{DeFl06b},
for which we assumed an infinite amount of communication ports and communication channels.
Such unrealistic assumption is not necessary in the algorithm reported here, which dynamically
evolves so as to make the best use of the available channels and ports.

Together with the new formulation of the gossiping algorithm we also describe here its ``evolution engine'', that is
the ``meta''-algorithm responsible for the dynamic tuning of the input permutation of the ``managed'' algorithm.

In what follows we introduce the algorithm through a formal model derived from~\cite{DeFl06b}.

Then in Sect. XXX we introduce the evolution engine 





General idea: 

family of gossiping algorithm depending on a parameter (permutation of participant ids)
solutions exist for particular cases: random, zero, smart\dots and correspond to
certain exploitations / requirements of the parallel channels system

$\mu$ average slot utilization
$\lambda$ duration of one cycle
$\sigma$ total  number of ``slots'' (parallelism)

Identity Permutation: $\lambda = 3/4 n^2 + \dots$

Pseudo-random: $\mu$ approx 3 slots

Pipelined: $\lambda = 3N$
$\varepsilon = 2/3$
$\mu = 2/3 (k+1)$

for a given n, certain 



We present a 

Un algoritmo di gossiping context-aware. . .


Quando si scrive un algoritmo, normalmente si cerca di esplicitare quanto piu'
possibile parallelismo; questo perche' quanto piu' intrinseco parallelismo
esiste, tanto maggiore sara' lo speed-up teorico raggiungibile. In altre parole,
disponendo di una macchina (platform) con un parallelismo fisico almeno pari
allo speed-up teorico, l'algoritmo in questione sara' caratterizzato da 
prestazioni migliori (un match migliore con l'architettura della deployment machine).

In realta', la quantita' di parallelismo da esplicitare dovrebbe idealmente
essere pari alla frazione di parallelismo fisico che la deployment machine
ed il deployment environment possono garantire in ogni istante di tempo:
- Generare meno parallelismo di quanto disponibile significa sottoutilizzare
  la macchina e l'ambiente;
- Generarne di piu', puo' nel migliore dei casi creare delle code di richieste
  e nel peggiore dei casi, quando le risorse sono limitate e condivise, puo'
  essere controproducente ed i taluni casi persino portare a delle failures.

Sarebbe vantaggioso isolare in un dato algoritmo l'agente che esprime il
parallelismo cosi' da renderlo un ``knob'' pilotabile da un agente esterno.
This would allow to embed the algorithm into a MAPE-K adaptive loop, able
to dynamically optimize the match between the resources
available at time $t$ (contextual parallelism) and the resources required
at the same time $t$ (algorithmic parallelism).






As an example, in the
case of a bus, or in ALOHA networks (see e.g.~\cite{Tan96}),
two or more overlapping attempts to transmit would result in
a collision i.e., a penalty that wastes the current slot. When
deployed in such a communication environment, our FSA
should be ``tuned'' so as to make use of at most one send per slot.
Using a different environment, e.g.
              transputers~\cite{Gra90}, each of which has
              four independent full-duplex communication channels,
an optimal permutation for our FSA would be one allowing
an average of 4 parallel reads and 4 parallel writes to be executed in each time step.








Clearly using a pipelined permutation leads to higher degrees of parallelism. Should this
parallelism be backed up by the system this would lead to high performance. In particular,
after a start-up phase, sustained performance reaches a maximum as on the
average there will be only one wasted slot 
per time step.

\begin{figure*}[t]
	\hspace*{-40pt}%
	\subfigure[][]{\input cmp13-steps
	}%
	\subfigure[][]{\input cmp13-average
	}%
\caption{Run lengths (a) and algorithmic parallelism (b) for the identity 
and the pipelined permutations, $1\leq N\leq100$.}
\label{cmp13-steps}
\end{figure*}







Table~\ref{pipeline} shows how a run-table looks like when multiple
gossiping sessions take place one after the other.
As a result, the central area corresponding to the best observable
performance is prolonged. In such an area, $\varepsilon$ has been
experimentally found to be equal to $N/(N+1)$ and the throughput,
or the number of fully completed gossipings per time step, has been
found to be equal to $t/2$, $t$ being the duration of a time step.
In other words, within that area a gossiping is fully completed every
two time steps on the average. A number of algorithms which are based
on multiple gossipings may greatly benefit from this approach, e.g.,
those implemented in the distributed voting algorithm described 
in~\cite{DeDL98e}.

\begin{table}[t]
%\begin{small}
\hspace{-30pt}
\begin{tabular}{l|c@{}%
c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}%
    c@{}c@{}c@{}c@{}c@{}%
    c@{}c@{}c@{}c@{}c@{}%
%
    c@{}%
    %%%c@{}c@{}c@{}%
%
    c@{}c@{}c@{}c@{}c@{}%
    c@{}c@{}c@{}c@{}c@{}%
c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}}
&\tiny1&\tiny2&\tiny3&%
\tiny4&\tiny5&\tiny6&\tiny7&\tiny8&\tiny9&\tiny10&\tiny11&\tiny12&\tiny13&\tiny14&\tiny15&\tiny16%
&\tiny17&\tiny18&\tiny19%
%%%&\multicolumn{3}{c}{$\dots$}%
&$\dots$%
\\ \hline
\sf 0&$S_{1}$&$S_{2}$&$S_{3}$&$S_{4}$&$-$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$%
       &$\curvearrowright$&$S_1$&$S_2$&$S_{3}$&$S_{4}$&$-$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$%
       %%%&\multicolumn{3}{c}{$\dots$}%
	&$\dots$%
       &$\curvearrowright$&$S_1$&$S_2$&$S_{3}$&$S_{4}$&$-$&$R_{1}$&$R_{2}$&$R_{3}$&$R_{4}$%
&$-$&$-$&$-$\\
\sf 1&$R_{0}$&$\curvearrowright$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{0}$&$-$&$R_{2}$&$R_{3}$%
       &$R_{4}$&$R_0$&$\curvearrowright$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{0}$&$-$&$R_{2}$&$R_{3}$%
       %&\multicolumn{3}{c}{$\dots$}%
	&$\dots$%
       &$R_{4}$&$R_0$&$\curvearrowright$&$S_{2}$&$S_{3}$&$S_{4}$&$S_{0}$&$-$&$R_{2}$&$R_{3}$%
&$R_{4}$&$-$&$-$\\
\sf 2&$-$&$R_{0}$&$R_{1}$&$\curvearrowright$&$S_{3}$&$S_{4}$&$S_{0}$&$S_{1}$&$-$%
       &$R_{3}$&$R_{4}$&$R_0$&$R_{1}$&$\curvearrowright$&$S_{3}$&$S_{4}$&$S_{0}$&$S_{1}$&$-$%
       %&\multicolumn{3}{c}{$\dots$}%
	&$\dots$%
       &$R_{3}$&$R_{4}$&$R_0$&$R_{1}$&$\curvearrowright$&$S_{3}$&$S_{4}$&$S_{0}$&$S_{1}$&$-$%
&$R_{3}$&$R_{4}$&$-$\\
\sf 3&$-$&$-$&$R_{0}$&$R_{1}$&$R_{2}$&$\curvearrowright$&$S_{4}$&$S_{0}$&$S_{1}$%
       &$S_{2}$&$-$&$R_{4}$&$R_{0}$&$R_{1}$&$R_{2}$&$\curvearrowright$&$S_{4}$&$S_{0}$&$S_{1}$%
       %&\multicolumn{3}{c}{$\dots$}%
	&$\dots$%
       &$S_{2}$&$-$&$R_{4}$&$R_{0}$&$R_{1}$&$R_{2}$&$\curvearrowright$&$S_{4}$&$S_{0}$&$S_{1}$%
&$S_{2}$&$-$&$R_{4}$\\
\sf 4&$-$&$-$&$-$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$\curvearrowright$&$S_{0}$%
       &$S_{1}$&$S_{2}$&$S_{3}$&$-$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$\curvearrowright$&$S_{0}$%
       %&\multicolumn{3}{c}{$\dots$}%
	&$\dots$%
       &$S_{1}$&$S_{2}$&$S_{3}$&$-$&$R_{0}$&$R_{1}$&$R_{2}$&$R_{3}$&$\curvearrowright$&$S_{0}$%
&$S_{1}$&$S_{2}$&$S_{3}$\\
\hline
&2&2&4&4&4&4&4&4&4&4&4&4&4&4&4&4&4&4&4%
%%%&\multicolumn{3}{c}{$\dots$}%
	&$\dots$%
&4&4&4&4&4&4&4&4&4&4&4&2&2
\end{tabular}
%\end{small}
\caption{The algorithm is modified so that multiple gossiping sessions take place.
The central, best performing area is consequently prolonged. Therein $\varepsilon$ is 
equal to $N/(N+1)$. 
Note how within that area there are consecutive ``zones'' of ten columns each,
within whom five gossiping sessions reach their conclusion. For instance,
such a zone is the region between columns 7 and 16: therein, at entries $(4,7)$,
$(0,9)$, $(1,10)$, $(2,11)$, and $(3,12)$, a process gets the last value
of a broadcast and can perform some work on a full set of values. This
brings to a throughput of $t/2$, where $t$ is the duration of a slot.}
\label{pipeline}
\end{table}


Obviously our model reaches such a performance only if the system
calls for exactly one time step to communicate between any two processes,
like e.g. in a crossbar system. This is similar to the constraint
of hardware pipelined processors which call for a number of
memory ports equal to $n$, $n$ being the number of pipeline 
stages supported by that machine---in this way
the system is able to overlap any two of its stages. This of course
turns into requiring to have a memory system 
capable of delivering $n$ times the original bandwidth
of a corresponding, unpipelined machine~\cite{He06}.






\begin{figure*}[t]
\centerline{\psfig{figure=s30.ps,height=0.95\textwidth,angle=-90}}
\caption{A graphical representation for run-table 30 when $\P$ is
permutation~(\ref{pipe}).}\label{s30}
\end{figure*}

Figure~\ref{s30} represents gossiping when $\P$ is pipelined and $N=30$.
Note how the specularity of graphs like the one of Fig.~\ref{s30} translates
into a palindrome $\vec\nu$ string.% This brought us to the following conjecture:

%\begin{conj}\label{pal}
%Whenever the order of reception of Alg.~\ref{alg1} can be further characterized
%by adding subscript ``$j$'' to states $W\!R$ and $R$ in lines 4, 5, 12, and 13,
%so that reception occurs according to increasing values of process labels,
%the corresponding $\vec\nu$ is a palindrome.
%\end{conj}





Here we show that, by ``morphing'' one structure into the other, it is
possible to derive a monotonic ``scale'' of algorithmic parallelism.




$\mu$ (returning the algorithmic parallelism of a certain permutation policy;




	Esperimento: calcola una tavola; esegui continuamente gossiping; 
	ad ogni fine run (round),
	controlla come evolve N(t). Quindi scegli la permutazione piu' vicina
	(ovvero, calcola tale permutazione e aggiorna la tavola);

	$\PP$ = set of known permutations, initially consisting of at least the identity and
	pipelined permutations, possibly . . .

s11.bbl
\begin{thebibliography}{10}\setlength{\itemsep}{-1ex}\small

\bibitem{Mplayer}
Anonymous.
\newblock Mplayer---the movie player.
\newblock Retrieved on August 7, 2011 from
  www.mplayerhq.hu/design7/info.html.

\bibitem{BGRV98}
J.-C. Bermond et al.
\newblock Fast gossiping by short messages.
\newblock {\em SIAM J. Comput.}, 27:917--941, 1998.

\bibitem{BDB11a}
J.~Buys, V.~{De Florio}, and C.~Blondia.
\newblock Towards context-aware adaptive fault tolerance in SOA applications.
\newblock In {\em Proc. of the 5th ACM International Conference on
  Distributed Event-Based Systems (DEBS)}, pages 63--74. 
  ACM, 2011.

\bibitem{Dev27}
V.~De~Florio.
\newblock Array associativi, linguaggio {C} e programmazione {CGI}.
\newblock {\em DEV.}, (27), February 1996.
\newblock (In Italian).

\bibitem{De10}
V.~De~Florio.
\newblock Software assumptions failure tolerance: Role, strategies, and
  visions.
\newblock In A.~Casimiro, R.~de~Lemos, and C.~Gacek, eds.:
\newblock {\em Architecting
  Dependable Systems VII}, volume 6420 of LNCS.
  Springer, 2010.

\bibitem{DeF11a}
V.~De~Florio.
\newblock Robust-and-evolvable resilient software systems --- open problems and
  lessons learned.
\newblock In {\em Proc. of the ESEC/FSE 2011 Workshop on Assurances for
  Self-Adaptive Systems (ASAS 2011)}, Szeged, Hungary, Sept. 2011.

\bibitem{DeFl06b}
V.~De~Florio and C.~Blondia.
\newblock The algorithm of pipelined gossiping.
\newblock {\em Journal of Systems Architecture}, 52(4):235--256, 2006.

\bibitem{DB07d}
V.~De~Florio and C.~Blondia.
\newblock Reflective and refractive variables: A model for effective and
  maintainable adaptive-and-dependable software.
\newblock In {\em Proc. of the 33rd Euromicro Conf. on Software
  Engineering and Advanced Applications (SEEA 2007)}, 
  L{\"u}beck, Germany, August 2007. IEEE.

\bibitem{DeDL98e}
V.~De~Florio, G. Deconinck and R. Lauwereins.
\newblock Software tool combining fault masking with user-defined recovery
  strategies.
\newblock {\em IEE Proceedings -- Software}, 145(6):203--211, Dec. 1998.
\newblock IEE in association with the British Computer Society.

  %\balance 

\bibitem{Fri04}
M.~Frigo.
\newblock A fast fourier transform compiler.
\newblock {\em SIGPLAN Not.}, 39(4):642--655, 2004.

\bibitem{Gon03}
T.~F. Gonzales.
\newblock An efficient algorithm for gossiping in the multicasting
  communication environment.
\newblock {\em IEEE Transactions on Parallel and Distributed Systems}, 14(7),
  July 2003.

\bibitem{Goss}
S.~Hedetniemi, S.~Hedetniemi, and A.~Leistman.
\newblock A survey of gossiping and broadcasting in communication networks.
\newblock {\em Networks}, 18:419--435, 1988.

\bibitem{He06}
J.~L. Hennessy and D.~A. Patterson.
\newblock {\em Computer Architecture, Fourth Edition: A Quantitative Approach}.
\newblock Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2006.

\bibitem{Jen04:Jen}
E.~Jen.
\newblock Stable or robust? what's the difference?
\newblock In E.~Jen, editor, {\em Robust Design: a repertoire of biological,
  ecological, and engineering case studies}, SFI Studies in the Sciences of
  Complexity, pages 7--20. Oxford University Press, 2004.

\bibitem{KeCh:2003}
J.~O. Kephart and D.~M. Chess.
\newblock The vision of autonomic computing.
\newblock {\em Computer}, 36:41--50, January 2003.

\bibitem{KLM97}
G.~Kiczales,
J.~Lamping, A.~Mendhekar, C.~Maeda, C.~Videira~Lopes,
  J.M.~Loingtier and J.~Irwin.
\newblock Aspect-oriented programming.
\newblock In {\em Proc. of the European Conf. on Object-Oriented
  Programming (ECOOP)}, volume 1241 of LNCS,
  Finland, June 1997.

\bibitem{Knu73a}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming, Volume 1 (Fundamental
  Algorithms)}.
\newblock Addison-Wesley, Reading MA, 2nd edition, 1973.

\bibitem{Sub:2005}
S.~Subotic and J.~Bishop.
\newblock Emergent behaviour of aspects in high performance and distributed
  computing.
\newblock In {\em Proc. of the 2005 annual conf.
  on IT research in developing countries}, SAICSIT '05, pages 11--19, Republic
  of South Africa, 2005.

\end{thebibliography}
