Index: .gitignore =================================================================== --- .gitignore (revision 08f3ad3fbb7f014c910d4d066d7c81832e707b6c) +++ .gitignore (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -79,2 +79,5 @@ doc/user/pointer2.tex doc/user/EHMHierarchy.tex + +# generated by npm +package-lock.json Index: doc/LaTeXmacros/common.tex =================================================================== --- doc/LaTeXmacros/common.tex (revision 08f3ad3fbb7f014c910d4d066d7c81832e707b6c) +++ doc/LaTeXmacros/common.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -62,5 +62,5 @@ \newlength{\gcolumnposn} % temporary hack because lstlisting does not handle tabs correctly \newlength{\columnposn} -\setlength{\gcolumnposn}{2.75in} +\setlength{\gcolumnposn}{2.5in} \setlength{\columnposn}{\gcolumnposn} \newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}} @@ -265,5 +265,5 @@ {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex\textgreater}2, -moredelim=**[is][\color{red}]{®}{®}, % red highlighting ®...® (registered trademark symbol) emacs: C-q M-. +moredelim=**[is][\color{red}]{?}{?}, % red highlighting ?...? (registered trademark symbol) emacs: C-q M-. moredelim=**[is][\color{blue}]{ß}{ß}, % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ moredelim=**[is][\color{OliveGreen}]{¢}{¢}, % green highlighting ¢...¢ (cent symbol) emacs: C-q M-" Index: doc/theses/thierry_delisle_PhD/.gitignore =================================================================== --- doc/theses/thierry_delisle_PhD/.gitignore (revision 08f3ad3fbb7f014c910d4d066d7c81832e707b6c) +++ doc/theses/thierry_delisle_PhD/.gitignore (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -11,4 +11,10 @@ comp_II/comp_II.pdf comp_II/comp_II.ps +comp_II/presentation.pdf + +thesis/build/ +thesis/fig/*.fig.bak +thesis/thesis.pdf +thesis/thesis.ps !Makefile Index: doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision 08f3ad3fbb7f014c910d4d066d7c81832e707b6c) +++ doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -133,5 +133,5 @@ As a hard requirement, the \CFA scheduler must guarantee eventual progress, otherwise the above-mentioned illusion of simultaneous execution is broken and the scheduler becomes much more complex to reason about. \newterm{Predictability} and \newterm{reliability} mean similar workloads achieve similar performance so programmer execution intuition is respected. -For example, a thread that yields aggressively should not run more often than other tasks. +For example, a thread that yields aggressively should not run more often than other threads. While this is intuitive, it does not hold true for many work-stealing or feedback based schedulers. The \CFA scheduler must guarantee eventual progress, should be predictable, and offer reliable performance. @@ -219,5 +219,5 @@ Popping is done by selecting two queues at random and popping from the queue with the oldest timestamp. A higher number of underlying queues leads to less contention on each queue and therefore better performance. -In a loaded system, it is highly likely the queues are non-empty, \ie several tasks are on each of the underlying queues. +In a loaded system, it is highly likely the queues are non-empty, \ie several threads are on each of the underlying queues. For this case, selecting a queue at random to pop from is highly likely to yield a queue with available items. In Figure~\ref{fig:base}, ignoring the ellipsis, the chances of getting an empty queue is 2/7 per pick, meaning two random picks yield an item approximately 9 times out of 10. Index: doc/theses/thierry_delisle_PhD/comp_II/img/system.fig =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/img/system.fig (revision 08f3ad3fbb7f014c910d4d066d7c81832e707b6c) +++ doc/theses/thierry_delisle_PhD/comp_II/img/system.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -1,3 +1,3 @@ -#FIG 3.2 Produced by xfig version 3.2.5c +#FIG 3.2 Produced by xfig version 3.2.7b Landscape Center @@ -36,21 +36,4 @@ 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 3600 15 15 4500 3600 4515 3615 -6 -6 3225 4125 4650 4425 -6 4350 4200 4650 4350 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4425 4275 15 15 4425 4275 4440 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 4275 15 15 4500 4275 4515 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4575 4275 15 15 4575 4275 4590 4290 --6 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3450 4275 225 150 3450 4275 3675 4425 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4050 4275 225 150 4050 4275 4275 4425 --6 -6 6675 4125 7500 4425 -6 7200 4200 7500 4350 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7275 4275 15 15 7275 4275 7290 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7350 4275 15 15 7350 4275 7365 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7425 4275 15 15 7425 4275 7440 4290 --6 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 4275 225 150 6900 4275 7125 4425 --6 6 6675 3525 8025 3975 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 @@ -79,9 +62,8 @@ 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3975 2850 150 150 3975 2850 4125 2850 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 7200 2775 150 150 7200 2775 7350 2775 -1 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4860 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4830 1 3 0 1 0 0 0 0 0 0.000 1 0.0000 7200 2775 30 30 7200 2775 7230 2805 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3525 3600 150 150 3525 3600 3675 3600 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3875 4800 100 100 3875 4800 3975 4800 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4650 4800 150 75 4650 4800 4800 4875 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4625 4838 100 100 4625 4838 4725 4838 2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 2400 4200 2400 3750 1950 3750 1950 4200 2400 4200 @@ -153,19 +135,18 @@ 1 1 1.00 45.00 90.00 7875 3750 7875 2325 7200 2325 7200 2550 +2 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5 + 6975 4950 6750 4950 6750 4725 6975 4725 6975 4950 2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 5850 4950 5850 4725 5625 4725 5625 4950 5850 4950 -2 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5 - 6975 4950 6750 4950 6750 4725 6975 4725 6975 4950 -4 1 -1 0 0 0 10 0.0000 2 105 720 5550 4425 Processors\001 -4 1 -1 0 0 0 10 0.0000 2 120 1005 4200 3225 Blocked Tasks\001 -4 1 -1 0 0 0 10 0.0000 2 150 870 4200 3975 Ready Tasks\001 -4 1 -1 0 0 0 10 0.0000 2 135 1095 7350 1725 Other Cluster(s)\001 -4 1 -1 0 0 0 10 0.0000 2 105 840 4650 1725 User Cluster\001 -4 1 -1 0 0 0 10 0.0000 2 150 615 2175 3675 Manager\001 -4 1 -1 0 0 0 10 0.0000 2 105 990 2175 3525 Discrete-event\001 -4 1 -1 0 0 0 10 0.0000 2 135 795 2175 4350 preemption\001 -4 0 -1 0 0 0 10 0.0000 2 150 1290 2325 4875 generator/coroutine\001 -4 0 -1 0 0 0 10 0.0000 2 120 270 4050 4875 task\001 -4 0 -1 0 0 0 10 0.0000 2 105 450 7050 4875 cluster\001 -4 0 -1 0 0 0 10 0.0000 2 105 660 5925 4875 processor\001 -4 0 -1 0 0 0 10 0.0000 2 105 555 4875 4875 monitor\001 +4 1 -1 0 0 0 10 0.0000 2 135 900 5550 4425 Processors\001 +4 1 -1 0 0 0 10 0.0000 2 165 1170 4200 3975 Ready Threads\001 +4 1 -1 0 0 0 10 0.0000 2 165 1440 7350 1725 Other Cluster(s)\001 +4 1 -1 0 0 0 10 0.0000 2 135 1080 4650 1725 User Cluster\001 +4 1 -1 0 0 0 10 0.0000 2 165 630 2175 3675 Manager\001 +4 1 -1 0 0 0 10 0.0000 2 135 1260 2175 3525 Discrete-event\001 +4 1 -1 0 0 0 10 0.0000 2 150 900 2175 4350 preemption\001 +4 0 -1 0 0 0 10 0.0000 2 135 630 7050 4875 cluster\001 +4 1 -1 0 0 0 10 0.0000 2 135 1350 4200 3225 Blocked Threads\001 +4 0 -1 0 0 0 10 0.0000 2 135 540 4800 4875 thread\001 +4 0 -1 0 0 0 10 0.0000 2 120 810 5925 4875 processor\001 +4 0 -1 0 0 0 10 0.0000 2 165 1710 2325 4875 generator/coroutine\001 Index: doc/theses/thierry_delisle_PhD/thesis/Makefile =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/Makefile (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/Makefile (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,98 @@ +## Define the configuration variables. + +Build = build +Figures = img +Macros = ../../../LaTeXmacros +TeXLIB = .:${Macros}:${Build}:../../../bibliography: +LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} +BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex + +MAKEFLAGS = --no-print-directory --silent # +VPATH = ${Build} ${Figures} + +## Define the text source files. +TEXTS = ${addprefix text/, ${addsuffix .tex, \ + front \ + intro \ + runtime \ + core \ + practice \ + io \ +}} + +FIGURES = ${addsuffix .tex, \ +} + +PICTURES = ${addsuffix .pstex, \ + base \ + empty \ +} + +PROGRAMS = ${addsuffix .tex, \ +} + +GRAPHS = ${addsuffix .tex, \ +} + +## Define the documents that need to be made. +all: thesis.pdf +thesis.pdf: ${TEXTS} ${FIGURES} ${PICTURES} glossary.tex + +DOCUMENT = thesis.pdf +BASE = ${basename ${DOCUMENT}} + +# Directives # + +.PHONY : all clean # not file names + +all : ${DOCUMENT} + +clean : + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} + +# File Dependencies # + +%.pdf : build/%.ps | ${Build} + ps2pdf $< + +build/%.ps : build/%.dvi | ${Build} + dvips $< -o $@ + +build/%.dvi : %.tex Makefile | ${Build} + # Must have *.aux file containing citations for bibtex + if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} $< ; fi + -${BibTeX} ${basename $@} + # Some citations reference others so run again to resolve these citations + ${LaTeX} $< + -${BibTeX} ${basename $@} + # Make index from *.aux entries and input index at end of document + -makeglossaries -q -s ${basename $@}.ist ${basename $@} + # Run again to finish citations + ${LaTeX} $< + +## Define the default recipes. + +${Build}: + mkdir -p ${Build} + +%.tex : fig/%.fig | ${Build} + fig2dev -L eepic $< > ${Build}/$@ + +%.ps : fig/%.fig | ${Build} + fig2dev -L ps $< > ${Build}/$@ + +%.pstex : fig/%.fig | ${Build} + fig2dev -L pstex $< > ${Build}/$@ + fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t + +## pstex with inverted colors +%.dark.pstex : fig/%.fig Makefile | ${Build} + fig2dev -L pstex $< > ${Build}/$@ + sed -i 's/\/col-1 {0 setgray} bind def/\/col-1 {1 setgray} bind def/g' ${Build}/$@ + sed -i 's/\/col0 {0.000 0.000 0.000 srgb} bind def/\/col0 {1.000 1.000 1.000 srgb} bind def/g' ${Build}/$@ + sed -i 's/\/col7 {1.000 1.000 1.000 srgb} bind def/\/col7 {0.000 0.000 0.000 srgb} bind def/g' ${Build}/$@ + fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t + +# Local Variables: # +# compile-command: "make" # +# End: # Index: doc/theses/thierry_delisle_PhD/thesis/fig/base.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/base.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/fig/base.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,83 @@ +#FIG 3.2 Produced by xfig version 3.2.7b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 +-6 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 2400 300 300 3900 2400 4200 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 3300 300 300 3900 3300 4200 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 1500 300 300 5100 1500 5400 1500 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 2400 300 300 5100 2400 5400 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 3300 300 300 5100 3300 5400 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6300 2400 300 300 6300 2400 6600 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6300 3300 300 300 6300 3300 6600 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4509 3302 300 300 4509 3302 4809 3302 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 3300 300 300 2700 3300 3000 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 2400 300 300 2700 2400 3000 2400 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3300 2700 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 3300 3900 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 4200 3900 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 2475 5100 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 3300 5100 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 3300 6300 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 4200 6300 3600 +2 1 0 1 -1 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 2400 4275 3000 4275 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4500 4200 4500 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 2400 3375 3000 3375 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 2400 2475 3000 2475 +4 2 -1 50 -1 0 12 0.0000 2 135 630 2100 3075 Threads\001 +4 2 -1 50 -1 0 12 0.0000 2 165 450 2100 2850 Ready\001 +4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 4450 TS\001 +4 2 -1 50 -1 0 12 0.0000 2 165 720 2100 4200 Array of\001 +4 2 -1 50 -1 0 12 0.0000 2 150 540 2100 4425 Queues\001 +4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 3550 TS\001 +4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 2650 TS\001 Index: doc/theses/thierry_delisle_PhD/thesis/fig/empty.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/empty.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/fig/empty.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,41 @@ +#FIG 3.2 Produced by xfig version 3.2.7b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 3300 300 300 5100 3300 5400 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 2400 300 300 2700 2400 3000 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 3300 300 300 2700 3300 3000 3300 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3300 2700 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 +4 2 -1 50 -1 0 12 0.0000 2 165 720 2100 4200 Array of\001 +4 2 -1 50 -1 0 12 0.0000 2 150 540 2100 4425 Queues\001 +4 2 -1 50 -1 0 12 0.0000 2 135 630 2100 3075 Threads\001 +4 2 -1 50 -1 0 12 0.0000 2 165 450 2100 2850 Ready\001 Index: doc/theses/thierry_delisle_PhD/thesis/fig/emptybit.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/emptybit.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/fig/emptybit.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,47 @@ +#FIG 3.2 Produced by xfig version 3.2.5c +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 +-6 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 3300 300 300 5100 3300 5400 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 2400 300 300 2700 2400 3000 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 3300 300 300 2700 3300 3000 3300 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3300 2700 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 +4 0 0 50 -1 5 14 0.0000 2 180 1800 3750 4800 [1000100...]\001 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 Index: doc/theses/thierry_delisle_PhD/thesis/fig/emptytls.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/emptytls.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/fig/emptytls.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,51 @@ +#FIG 3.2 Produced by xfig version 3.2.5c +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 +-6 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 3300 300 300 5100 3300 5400 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 2400 300 300 2700 2400 3000 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 3300 300 300 2700 3300 3000 3300 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3300 2700 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 +4 0 0 50 -1 5 14 0.0000 2 180 1800 2400 5100 [1000100...]\001 +4 0 0 50 -1 5 14 0.0000 2 180 1800 4425 5100 [1000100...]\001 +4 0 0 50 -1 5 14 0.0000 2 180 1800 6450 5100 [1000100...]\001 +4 0 0 50 -1 0 13 0.0000 2 135 690 1500 5175 Bitmask\001 +4 0 0 50 -1 0 13 0.0000 2 150 1155 1050 4950 Thread-Local\001 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 Index: doc/theses/thierry_delisle_PhD/thesis/fig/emptytree.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/emptytree.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/fig/emptytree.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,80 @@ +#FIG 3.2 Produced by xfig version 3.2.5c +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 +-6 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 3300 300 300 5100 3300 5400 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 2400 300 300 2700 2400 3000 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 3300 300 300 2700 3300 3000 3300 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4500 5700 3450 5400 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4500 5700 5850 5400 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 5100 2700 4575 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 5100 3300 4800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3450 5400 3000 5100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3450 5400 3900 5100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5400 5100 5100 4575 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5400 5100 5700 4800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5850 5400 5400 5100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5850 5400 6300 5100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3300 2700 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 +4 1 0 50 -1 0 12 0.0000 2 135 135 3300 4725 X\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 3900 5025 X\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 5700 4725 X\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 6300 5025 X\001 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 Index: doc/theses/thierry_delisle_PhD/thesis/fig/resize.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/resize.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/fig/resize.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,90 @@ +#FIG 3.2 Produced by xfig version 3.2.5c +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 7500 3675 8475 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 + 1 1 1.00 45.00 90.00 + 1 1 1.00 45.00 90.00 + 7500 4200 7950 4200 +4 0 0 50 -1 0 12 0.0000 2 135 915 7500 3825 Grows with\001 +4 0 0 50 -1 0 12 0.0000 2 135 840 7500 4050 additional\001 +4 0 0 50 -1 0 12 0.0000 2 135 840 7500 4425 processors\001 +-6 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 +-6 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 2400 300 300 3900 2400 4200 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 3300 300 300 3900 3300 4200 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 1500 300 300 5100 1500 5400 1500 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 2400 300 300 5100 2400 5400 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5100 3300 300 300 5100 3300 5400 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6300 2400 300 300 6300 2400 6600 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6300 3300 300 300 6300 3300 6600 3300 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4509 3302 300 300 4509 3302 4809 3302 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 2400 300 300 2700 2400 3000 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2700 3300 300 300 2700 3300 3000 3300 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3 + 1 1 1.00 60.00 120.00 + 3750 5550 2400 5550 2400 4500 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 3600 5100 4500 5100 4500 6000 3600 6000 3600 5100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3300 2700 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 3300 3900 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 4200 3900 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 2475 5100 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 3300 5100 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 3300 6300 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 4200 6300 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4500 4200 4500 3600 +4 0 0 50 -1 0 13 0.0000 2 180 1170 2400 5775 Array Pointer\001 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 +4 1 0 50 -1 0 13 0.0000 2 150 1890 4050 5025 Cluster Data Structure\001 Index: doc/theses/thierry_delisle_PhD/thesis/fig/system.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/system.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/fig/system.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,171 @@ +#FIG 3.2 Produced by xfig version 3.2.5c +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 3855 2775 4155 2925 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 3930 2850 30 30 3930 2850 3960 2880 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 4035 2850 30 30 4035 2850 4065 2880 +-6 +6 4755 3525 5055 3675 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 4830 3600 30 30 4830 3600 4860 3630 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 4935 3600 30 30 4935 3600 4965 3630 +-6 +6 4650 2775 4950 2925 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4725 2850 15 15 4725 2850 4740 2865 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4800 2850 15 15 4800 2850 4815 2865 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4875 2850 15 15 4875 2850 4890 2865 +-6 +6 3225 2400 3525 2550 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3300 2475 15 15 3300 2475 3315 2490 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3375 2475 15 15 3375 2475 3390 2490 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3450 2475 15 15 3450 2475 3465 2490 +-6 +6 5475 3450 5625 3750 +1 3 0 1 -1 -1 0 0 20 0.000 1 4.7120 5550 3525 15 15 5550 3525 5535 3540 +1 3 0 1 -1 -1 0 0 20 0.000 1 4.7120 5550 3600 15 15 5550 3600 5535 3615 +1 3 0 1 -1 -1 0 0 20 0.000 1 4.7120 5550 3675 15 15 5550 3675 5535 3690 +-6 +6 4275 3525 4575 3675 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4350 3600 15 15 4350 3600 4365 3615 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4425 3600 15 15 4425 3600 4440 3615 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 3600 15 15 4500 3600 4515 3615 +-6 +6 3225 4125 4650 4425 +6 4350 4200 4650 4350 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4425 4275 15 15 4425 4275 4440 4290 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 4275 15 15 4500 4275 4515 4290 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4575 4275 15 15 4575 4275 4590 4290 +-6 +1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3450 4275 225 150 3450 4275 3675 4425 +1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4050 4275 225 150 4050 4275 4275 4425 +-6 +6 6675 4125 7500 4425 +6 7200 4200 7500 4350 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7275 4275 15 15 7275 4275 7290 4290 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7350 4275 15 15 7350 4275 7365 4290 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7425 4275 15 15 7425 4275 7440 4290 +-6 +1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 4275 225 150 6900 4275 7125 4425 +-6 +6 6675 3525 8025 3975 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6675 3750 6975 3750 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 7125 3750 7350 3750 +2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 + 7800 3975 7800 3525 7350 3525 7350 3975 7800 3975 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 7800 3750 8025 3750 +-6 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5550 2625 150 150 5550 2625 5700 2625 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5550 3225 150 150 5550 3225 5700 3225 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5550 3975 150 150 5550 3975 5700 3975 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3525 2850 150 150 3525 2850 3675 2850 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4200 2475 150 150 4200 2475 4350 2475 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2850 150 150 4425 2850 4575 2850 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4650 2475 150 150 4650 2475 4800 2475 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3975 3600 150 150 3975 3600 4125 3600 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 3525 3600 30 30 3525 3600 3555 3630 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3750 2475 150 150 3750 2475 3900 2625 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4875 3600 150 150 4875 3600 5025 3750 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3975 2850 150 150 3975 2850 4125 2850 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 7200 2775 150 150 7200 2775 7350 2775 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4860 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 7200 2775 30 30 7200 2775 7230 2805 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3525 3600 150 150 3525 3600 3675 3600 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3875 4800 100 100 3875 4800 3975 4800 +1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4650 4800 150 75 4650 4800 4800 4875 +2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 + 2400 4200 2400 3750 1950 3750 1950 4200 2400 4200 +2 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5 + 6300 4500 6300 1800 3000 1800 3000 4500 6300 4500 +2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 + 5775 2850 5775 2400 5325 2400 5325 2850 5775 2850 +2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 + 5775 4200 5775 3750 5325 3750 5325 4200 5775 4200 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5175 3975 5325 3975 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5175 3225 5325 3225 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5175 2625 5325 2625 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5775 3975 5925 3975 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5775 3225 5925 3225 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5775 2625 5925 2625 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2 + 5175 3975 5175 2625 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5925 3975 5925 2025 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5925 3750 6225 3750 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3450 2625 3225 2625 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 3 + 1 1 1.00 45.00 90.00 + 5925 2025 4200 2025 4200 2250 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2 + 3225 2625 3225 3600 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3075 3600 3375 3600 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3675 3600 3825 3600 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4125 3600 4275 3600 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4575 3600 4725 3600 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5025 3600 5175 3600 +2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 + 5775 3450 5775 3000 5325 3000 5325 3450 5775 3450 +2 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5 + 8100 4500 8100 1800 6600 1800 6600 4500 8100 4500 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 7050 2775 6825 2775 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2 + 6825 2775 6825 3750 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 4 + 1 1 1.00 45.00 90.00 + 7875 3750 7875 2325 7200 2325 7200 2550 +2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 + 5850 4950 5850 4725 5625 4725 5625 4950 5850 4950 +2 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5 + 6975 4950 6750 4950 6750 4725 6975 4725 6975 4950 +4 1 -1 0 0 0 10 0.0000 2 105 720 5550 4425 Processors\001 +4 1 -1 0 0 0 10 0.0000 2 120 1005 4200 3225 Blocked Tasks\001 +4 1 -1 0 0 0 10 0.0000 2 150 870 4200 3975 Ready Tasks\001 +4 1 -1 0 0 0 10 0.0000 2 135 1095 7350 1725 Other Cluster(s)\001 +4 1 -1 0 0 0 10 0.0000 2 105 840 4650 1725 User Cluster\001 +4 1 -1 0 0 0 10 0.0000 2 150 615 2175 3675 Manager\001 +4 1 -1 0 0 0 10 0.0000 2 105 990 2175 3525 Discrete-event\001 +4 1 -1 0 0 0 10 0.0000 2 135 795 2175 4350 preemption\001 +4 0 -1 0 0 0 10 0.0000 2 150 1290 2325 4875 generator/coroutine\001 +4 0 -1 0 0 0 10 0.0000 2 120 270 4050 4875 task\001 +4 0 -1 0 0 0 10 0.0000 2 105 450 7050 4875 cluster\001 +4 0 -1 0 0 0 10 0.0000 2 105 660 5925 4875 processor\001 +4 0 -1 0 0 0 10 0.0000 2 105 555 4875 4875 monitor\001 Index: doc/theses/thierry_delisle_PhD/thesis/glossary.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/glossary.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/glossary.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,137 @@ +\makeglossaries + +\longnewglossaryentry{hthrd} +{name={hardware thread}} +{ +Threads representing the underlying hardware directly. + +\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.} +} + +\longnewglossaryentry{thrd} +{name={threads}} +{ +Threads created and managed inside user-space. Each thread has its own stack and its own thread of execution. User-level threads are invisible to the underlying operating system. + +\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.} +} + +\longnewglossaryentry{kthrd} +{name={kernel-level thread}} +{ +Threads created and managed inside kernel-space. Each thread has its own stack and its own thread of execution. Kernel-level threads are owned, managed and scheduled by the underlying operating system. + +\textit{Synonyms : OS threads, Hardware threads, Physical threads.} +} + +\longnewglossaryentry{fiber} +{name={fiber}} +{ +Fibers are non-preemptive user-level threads. They share most of the caracteristics of user-level threads except that they cannot be preempted by another fiber. + +\textit{Synonyms : Tasks.} +} + +\longnewglossaryentry{job} +{name={job}} +{ +Unit of work, often sent to a thread pool or worker pool to be executed. Has neither its own stack nor its own thread of execution. + +\textit{Synonyms : Tasks.} +} + +\longnewglossaryentry{pool} +{name={thread-pool}} +{ +Group of homogeneuous threads that loop executing units of works after another. + +\textit{Synonyms : } +} + +\longnewglossaryentry{preemption} +{name={preemption}} +{ +Involuntary context switch imposed on threads at a given rate. + +\textit{Synonyms : None.} +} + +\longnewglossaryentry{proc} +{name={virtual processor}} +{ + +} + +\longnewglossaryentry{Q} +{name={work-queue}} +{ + +} + +\longnewglossaryentry{at} +{name={fred}} +{ +Abstract object representing an unit of work. Systems will offer one or more concrete implementations of this concept (\eg \gls{kthrd}, \gls{job}), however, most of the concept of schedulings are independent of the particular implementations of the work representation. For this reason, this document use the term \Gls{at} to mean any representation and not one in particular. +} + +\longnewglossaryentry{atsched} +{name={Scheduling a \gls{at}}} +{ +Scheduling an \gls{at} refers to the act of notifying the scheduler that a task is ready to be ran. When representing the scheduler as a queue of tasks, scheduling is the act of pushing a task onto the end of the queue. This doesn't necesserily means the task will ever be allocated CPU time (\gls{atrun}), for example, if the system terminates abruptly, scheduled \glspl{at} will probably never run. + +\textit{Synonyms : None.} +} + +\longnewglossaryentry{atrun} +{name={Running a \gls{at}}} +{ +Running an \gls{at} refers to the act of allocating CPU time to a task that is ready to run. When representing the scheduler as a queue of tasks, running is the act of poping a task from the front of the queue and putting it onto a \gls{proc}. The \gls{at} can than accomplish some or all of the work it is programmed to do. + +\textit{Synonyms : None.} +} + +\longnewglossaryentry{atmig} +{name={migration of \gls{at}}} +{ +Migration refers to the idea of an \gls{at} running on a different worker/processor than the last time it was run. It is generally preferable to minimise migration as it incurs cost but any load balancing among workers requires some amount of migration. + +\textit{Synonyms : None.} +} + +\longnewglossaryentry{atpass} +{name={overtaking \gls{at}}} +{ +When representing the scheduler as a queue of \glspl{at}, overtaking is the act breaking the FIFO-ness of the queue by moving a \gls{at} in front of some other \gls{at} when it arrived after. This remains true for schedulers that do not use a FIFO queue, when the order in which the \glspl{at} are \glslink{atsched}{scheduled} and \glslink{atrun}{run} in a different order. A \gls{at} is said to \emph{overtake} another if it is run \emph{before} but was \emph{scheduled} after the other \gls{at}. + +\textit{Synonyms : None.} +} + +\longnewglossaryentry{atblock} +{name={Blocking an \gls{at}}} +{ +Blocking an abstract task refers to the act of taking a task that us running on a CPU off the CPU. Unless no other task is ready, this action is generally immediately followed by running an other task. + +\textit{Synonyms : None.} +} + +\longnewglossaryentry{atcomplet} +{name={Running to completion}} +{ +Running to completion refers to the entire sequence of : being scheduled, running and blocking, for a given task. + +See also \gls{atsched}, \gls{atrun}, \gls{atblock} + +\textit{Synonyms : None.} +} + +\longnewglossaryentry{load} +{name={System Load}} +{ +The load is refers to the rate at which \glspl{at} are \glslink{atsched}{scheduled} versus the rate at which they are \glslink{atrun}{run}. When \glspl{at} are being scheduled faster than they are run, the system is considered \emph{overloaded}. When \glspl{at} are being run faster than they are scheduled, the system is considered \emph{underloaded}. Conrrespondingly, if both rates are equal, the system is considered \emph{loaded}. Note that the system is considered loaded only of the rate at which \glspl{at} are scheduled/run is non-zero, otherwise the system is empty, it has no load. +} + + +\newacronym{tls}{TLS}{Thread Local Storage} +\newacronym{api}{API}{Application Program Interface} +\newacronym{raii}{RAII}{Resource Acquisition Is Initialization} +\newacronym{numa}{NUMA}{Non-Uniform Memory Access} Index: doc/theses/thierry_delisle_PhD/thesis/text/core.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/core.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/text/core.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,46 @@ +\chapter{Scheduling Core}\label{core} + +This chapter addresses the need of scheduling on a somewhat ideal scenario + +\section{Existing Schedulers} +\subsection{Feedback Scheduling} + +\subsection{Priority Scheduling}\label{priority} + +\subsection{Work Stealing} + +\section{Design} +While avoiding the pitfalls of Feedback Scheduling is fairly easy, scheduling does not innately require feedback, avoiding prioritization of \glspl{thrd} is more difficult because of implicitly priorities, see Subsection~\ref{priority}. + +\subsection{Sharding} + +\begin{figure} + \begin{center} + \input{base.pstex_t} + \end{center} + \caption{Relaxed FIFO list at the base of the scheduler: an array of strictly FIFO lists. + The timestamp is in all nodes and cell arrays.} + \label{fig:base} +\end{figure} + +\subsection{Finding threads} +Once threads have been distributed onto multiple queues, indentifying which queues are empty and which aren't can become a problem. +Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of these queues are empty. +Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time. +This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses. + +Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme. + +\paragraph{Dense Information} + + + + + +\begin{figure} + \begin{center} + \input{empty.pstex_t} + \end{center} + \caption{``More empty'' state of the queue: the array contains many empty cells.} + \label{fig:empty} +\end{figure} Index: doc/theses/thierry_delisle_PhD/thesis/text/front.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/front.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/text/front.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,192 @@ +% T I T L E P A G E +% ------------------- +% Last updated June 14, 2017, by Stephen Carr, IST-Client Services +% The title page is counted as page `i' but we need to suppress the +% page number. Also, we don't want any headers or footers. +\pagestyle{empty} +\pagenumbering{roman} + +% The contents of the title page are specified in the "titlepage" +% environment. +\begin{titlepage} + \begin{center} + \vspace*{1.0cm} + + \Huge + {\bf The \CFA Scheduler} + + \vspace*{1.0cm} + + \normalsize + by \\ + + \vspace*{1.0cm} + + \Large + Thierry Delisle \\ + + \vspace*{3.0cm} + + \normalsize + A thesis \\ + presented to the University of Waterloo \\ + in fulfillment of the \\ + thesis requirement for the degree of \\ + Doctor of Philosophy \\ + in \\ + Computer Science \\ + + \vspace*{2.0cm} + + Waterloo, Ontario, Canada, 2021 \\ + + \vspace*{1.0cm} + + \copyright\ Thierry Delisle 2021 \\ + \end{center} +\end{titlepage} + +% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii' +\pagestyle{plain} +\setcounter{page}{2} + +\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed. +% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary. + + +% E X A M I N I N G C O M M I T T E E (Required for Ph.D. theses only) +% Remove or comment out the lines below to remove this page +\begin{center}\textbf{Examining Committee Membership}\end{center} +\noindent + The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote. + \todo{External Examiners} +\bigskip + +\noindent +\begin{tabbing} + Internal-External Member: \= \kill % using longest text to define tab length + External Examiner: \> TBD \\ + \> TBD \\ +\end{tabbing} +\bigskip + +\noindent +\begin{tabbing} + Internal-External Member: \= \kill % using longest text to define tab length + Supervisor(s): \> Peter Buhr \\ + \> Associate Professor, School of Computer Science \\ + \> University of Waterloo \\ +\end{tabbing} +\bigskip + +\noindent +\begin{tabbing} + Internal-External Member: \= \kill % using longest text to define tab length + Internal Member: \> Trevor Brown \\ + \> Assistant Professor, School of Computer Science \\ + \> University of Waterloo \\ + \\ + Internal Member: \> Martin Karsten \\ + \> Associate Professor, School of Computer Science \\ + \> University of Waterloo \\ +\end{tabbing} +\bigskip + +\noindent +\begin{tabbing} + Internal-External Member: \= \kill % using longest text to define tab length + Internal-External Member: \> TBD \\ + \> TBD \\ + \> University of Waterloo \\ +\end{tabbing} +\bigskip + +\cleardoublepage + +% D E C L A R A T I O N P A G E +% ------------------------------- +% The following is a sample Delaration Page as provided by the GSO +% December 13th, 2006. It is designed for an electronic thesis. +\noindent +I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. + +\bigskip + +\noindent +I understand that my thesis may be made electronically available to the public. + +\cleardoublepage + +% A B S T R A C T +% --------------- + +\begin{center}\textbf{Abstract}\end{center} + +This is the abstract. + +Vulputate minim vel consequat praesent at vel iusto et, ex delenit, esse euismod luptatum augue ut sit et eu vel augue autem feugiat, quis ad dolore. Nulla vel, laoreet lobortis te commodo elit qui aliquam enim ex iriure ea ullamcorper nostrud lorem, lorem laoreet eu ex ut vel in zzril wisi quis. Nisl in autem praesent dignissim, sit vel aliquam at te, vero dolor molestie consequat. + +Tation iriure sed wisi feugait odio dolore illum duis in accumsan velit illum consequat consequat ipsum molestie duis duis ut ullamcorper. Duis exerci odio blandit vero dolore eros odio amet et nisl in nostrud consequat iusto eum suscipit autem vero. Iusto dolore exerci, ut erat ex, magna in facilisis duis amet feugait augue accumsan zzril delenit aliquip dignissim at. Nisl molestie nibh, vulputate feugait nibh luptatum ea delenit nostrud dolore minim veniam odio volutpat delenit nulla accumsan eum vero ullamcorper eum. Augue velit veniam, dolor, exerci ea feugiat nulla molestie, veniam nonummy nulla dolore tincidunt, consectetuer dolore nulla ipsum commodo. + +At nostrud lorem, lorem laoreet eu ex ut vel in zzril wisi. Suscipit consequat in autem praesent dignissim, sit vel aliquam at te, vero dolor molestie consequat eros tation facilisi diam dolor. Odio luptatum dolor in facilisis et facilisi et adipiscing suscipit eu iusto praesent enim, euismod consectetuer feugait duis. Odio veniam et iriure ad qui nonummy aliquip at qui augue quis vel diam, nulla. Autem exerci tation iusto, hendrerit et, tation esse consequat ut velit te dignissim eu esse eros facilisis lobortis, lobortis hendrerit esse dignissim nisl. Nibh nulla minim vel consequat praesent at vel iusto et, ex delenit, esse euismod luptatum. + +Ut eum vero ullamcorper eum ad velit veniam, dolor, exerci ea feugiat nulla molestie, veniam nonummy nulla. Elit tincidunt, consectetuer dolore nulla ipsum commodo, ut, at qui blandit suscipit accumsan feugiat vel praesent. In dolor, ea elit suscipit nisl blandit hendrerit zzril. Sit enim, et dolore blandit illum enim duis feugiat velit consequat iriure sed wisi feugait odio dolore illum duis. Et accumsan velit illum consequat consequat ipsum molestie duis duis ut ullamcorper nulla exerci odio blandit vero dolore eros odio amet et. + +In augue quis vel diam, nulla dolore exerci tation iusto, hendrerit et, tation esse consequat ut velit. Duis dignissim eu esse eros facilisis lobortis, lobortis hendrerit esse dignissim nisl illum nulla minim vel consequat praesent at vel iusto et, ex delenit, esse euismod. Nulla augue ut sit et eu vel augue autem feugiat, quis ad dolore te vel, laoreet lobortis te commodo elit qui aliquam enim ex iriure. Ut ullamcorper nostrud lorem, lorem laoreet eu ex ut vel in zzril wisi quis consequat in autem praesent dignissim, sit vel. Dolore at te, vero dolor molestie consequat eros tation facilisi diam. Feugait augue luptatum dolor in facilisis et facilisi et adipiscing suscipit eu iusto praesent enim, euismod consectetuer feugait duis vulputate veniam et. + +Ad eros odio amet et nisl in nostrud consequat iusto eum suscipit autem vero enim dolore exerci, ut. Esse ex, magna in facilisis duis amet feugait augue accumsan zzril. Lobortis aliquip dignissim at, in molestie nibh, vulputate feugait nibh luptatum ea delenit nostrud dolore minim veniam odio. Euismod delenit nulla accumsan eum vero ullamcorper eum ad velit veniam. Quis, exerci ea feugiat nulla molestie, veniam nonummy nulla. Elit tincidunt, consectetuer dolore nulla ipsum commodo, ut, at qui blandit suscipit accumsan feugiat vel praesent. + +Dolor zzril wisi quis consequat in autem praesent dignissim, sit vel aliquam at te, vero. Duis molestie consequat eros tation facilisi diam dolor augue. Dolore dolor in facilisis et facilisi et adipiscing suscipit eu iusto praesent enim, euismod consectetuer feugait duis vulputate. + +\cleardoublepage + +% A C K N O W L E D G E M E N T S +% ------------------------------- + +\begin{center}\textbf{Acknowledgements}\end{center} + +\todo{Acknowledgements} +\cleardoublepage + +% D E D I C A T I O N +% ------------------- + +% \begin{center}\textbf{Dedication}\end{center} + +% This is dedicated to the one I love. +% \cleardoublepage + +% T A B L E O F C O N T E N T S +% --------------------------------- +\renewcommand\contentsname{Table of Contents} +\tableofcontents +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% L I S T O F T A B L E S +% --------------------------- +\addcontentsline{toc}{chapter}{List of Tables} +\listoftables +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% L I S T O F F I G U R E S +% ----------------------------- +\addcontentsline{toc}{chapter}{List of Figures} +\listoffigures +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) +% ----------------------------- +\printglossary[type=\acronymtype] +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +\listofcits +\listoftodos + + +% Change page numbering back to Arabic numerals +\pagenumbering{arabic} + Index: doc/theses/thierry_delisle_PhD/thesis/text/intro.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/intro.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/text/intro.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,1 @@ +\chapter{Introduction} Index: doc/theses/thierry_delisle_PhD/thesis/text/io.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/io.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/text/io.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,19 @@ +\chapter{I/O} + +\section{Existing options} + +\subsection{\texttt{epoll}, \texttt{poll} and \texttt{select}} + +\subsection{Linux's AIO} + +\subsection{\texttt{io\_uring}} + +\subsection{Extra Kernel Threads} + +\subsection{Discussion} + + +\section{Event-Engine} + + +\section{Interface} Index: doc/theses/thierry_delisle_PhD/thesis/text/practice.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/practice.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/text/practice.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,13 @@ +\chapter{Scheduling in practice}\label{practice} +The scheduling algorithm discribed in Chapter~\ref{core} addresses scheduling in a stable state. +However, it does not address problems that occur when the system changes state. +Indeed the \CFA runtime, supports expanding and shrinking + +the number of KTHREAD\_place + +, both manually and, to some extent automatically. +This entails that the scheduling algorithm must support these transitions. + +\section{Resizing} + +\section{Idle-Sleep} Index: doc/theses/thierry_delisle_PhD/thesis/text/runtime.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/runtime.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/text/runtime.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,7 @@ +\chapter{\CFA Runtime} + +\section{M:N Threading} + +\section{Clusters} + +\section{Interoperating with \texttt{C}} Index: doc/theses/thierry_delisle_PhD/thesis/thesis.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/thesis.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ doc/theses/thierry_delisle_PhD/thesis/thesis.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,294 @@ +% uWaterloo Thesis Template for LaTeX +% Last Updated June 14, 2017 by Stephen Carr, IST Client Services +% FOR ASSISTANCE, please send mail to rt-IST-CSmathsci@ist.uwaterloo.ca + +% Effective October 2006, the University of Waterloo +% requires electronic thesis submission. See the uWaterloo thesis regulations at +% https://uwaterloo.ca/graduate-studies/thesis. + +% DON'T FORGET TO ADD YOUR OWN NAME AND TITLE in the "hyperref" package +% configuration below. THIS INFORMATION GETS EMBEDDED IN THE PDF FINAL PDF DOCUMENT. +% You can view the information if you view Properties of the PDF document. + +% Many faculties/departments also require one or more printed +% copies. This template attempts to satisfy both types of output. +% It is based on the standard "book" document class which provides all necessary +% sectioning structures and allows multi-part theses. + +% DISCLAIMER +% To the best of our knowledge, this template satisfies the current uWaterloo requirements. +% However, it is your responsibility to assure that you have met all +% requirements of the University and your particular department. +% Many thanks for the feedback from many graduates that assisted the development of this template. + +% ----------------------------------------------------------------------- + +% By default, output is produced that is geared toward generating a PDF +% version optimized for viewing on an electronic display, including +% hyperlinks within the PDF. + +% E.g. to process a thesis called "mythesis.tex" based on this template, run: + +% pdflatex mythesis -- first pass of the pdflatex processor +% bibtex mythesis -- generates bibliography from .bib data file(s) +% makeindex -- should be run only if an index is used +% pdflatex mythesis -- fixes numbering in cross-references, bibliographic references, glossaries, index, etc. +% pdflatex mythesis -- fixes numbering in cross-references, bibliographic references, glossaries, index, etc. + +% If you use the recommended LaTeX editor, Texmaker, you would open the mythesis.tex +% file, then click the PDFLaTeX button. Then run BibTeX (under the Tools menu). +% Then click the PDFLaTeX button two more times. If you have an index as well, +% you'll need to run MakeIndex from the Tools menu as well, before running pdflatex +% the last two times. + +% N.B. The "pdftex" program allows graphics in the following formats to be +% included with the "\includegraphics" command: PNG, PDF, JPEG, TIFF +% Tip 1: Generate your figures and photos in the size you want them to appear +% in your thesis, rather than scaling them with \includegraphics options. +% Tip 2: Any drawings you do should be in scalable vector graphic formats: +% SVG, PNG, WMF, EPS and then converted to PNG or PDF, so they are scalable in +% the final PDF as well. +% Tip 3: Photographs should be cropped and compressed so as not to be too large. + +% To create a PDF output that is optimized for double-sided printing: +% +% 1) comment-out the \documentclass statement in the preamble below, and +% un-comment the second \documentclass line. +% +% 2) change the value assigned below to the boolean variable +% "PrintVersion" from "false" to "true". + +% --------------------- Start of Document Preamble ----------------------- + +% Specify the document class, default style attributes, and page dimensions +% For hyperlinked PDF, suitable for viewing on a computer, use this: +\documentclass[letterpaper,12pt,titlepage,oneside,final]{book} + +% For PDF, suitable for double-sided printing, change the PrintVersion variable below +% to "true" and use this \documentclass line instead of the one above: +%\documentclass[letterpaper,12pt,titlepage,openright,twoside,final]{book} + +\newcommand{\href}[1]{#1} % does nothing, but defines the command so the + % print-optimized version will ignore \href tags (redefined by hyperref pkg). + +% This package allows if-then-else control structures. +\usepackage{ifthen} +\newboolean{PrintVersion} +\setboolean{PrintVersion}{false} +% CHANGE THIS VALUE TO "true" as necessary, to improve printed results for hard copies +% by overriding some options of the hyperref package below. + +%\usepackage{nomencl} % For a nomenclature (optional; available from ctan.org) +\usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments +\usepackage{graphicx} % For including graphics + +% Hyperlinks make it very easy to navigate an electronic document. +% In addition, this is where you should specify the thesis title +% and author as they appear in the properties of the PDF document. +% Use the "hyperref" package +% N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE +\usepackage[pagebackref=false]{hyperref} % with basic options + % N.B. pagebackref=true provides links back from the References to the body text. This can cause trouble for printing. +\hypersetup{ + plainpages=false, % needed if Roman numbers in frontpages + unicode=false, % non-Latin characters in Acrobat’s bookmarks + pdftoolbar=true, % show Acrobat’s toolbar? + pdfmenubar=true, % show Acrobat’s menu? + pdffitwindow=false, % window fit to page when opened + pdfstartview={FitH}, % fits the width of the page to the window + pdftitle={The Cforall Scheduler}, % title + pdfauthor={Thierry Delisle}, % author + pdfsubject={Cforall}, % subject + pdfkeywords={Cforall} {concurrency} {scheduling}, % list of keywords + pdfnewwindow=true, % links in new window + colorlinks=true, % false: boxed links; true: colored links + linkcolor=blue, % color of internal links + citecolor=green, % color of links to bibliography + filecolor=magenta, % color of file links + urlcolor=cyan % color of external links +} +\ifthenelse{\boolean{PrintVersion}}{ % for improved print quality, change some hyperref options +\hypersetup{ % override some previously defined hyperref options + citecolor=black, + filecolor=black, + linkcolor=black, + urlcolor=black +}}{} % end of ifthenelse (no else) + +\usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package +% If glossaries-extra is not in your LaTeX distribution, get it from CTAN (http://ctan.org/pkg/glossaries-extra), +% although it's supposed to be in both the TeX Live and MikTeX distributions. There are also documentation and +% installation instructions there. + +% Setting up the page margins... +% uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the +% top, bottom, and outside page edges and a 1.125 in. (81pt) gutter +% margin (on binding side). While this is not an issue for electronic +% viewing, a PDF may be printed, and so we have the same page layout for +% both printed and electronic versions, we leave the gutter margin in. +% Set margins to minimum permitted by uWaterloo thesis regulations: +\setlength{\marginparwidth}{0pt} % width of margin notes +% N.B. If margin notes are used, you must adjust \textwidth, \marginparwidth +% and \marginparsep so that the space left between the margin notes and page +% edge is less than 15 mm (0.6 in.) +\setlength{\marginparsep}{0pt} % width of space between body text and margin notes +\setlength{\evensidemargin}{0.125in} % Adds 1/8 in. to binding side of all +% even-numbered pages when the "twoside" printing option is selected +\setlength{\oddsidemargin}{0.125in} % Adds 1/8 in. to the left of all pages +% when "oneside" printing is selected, and to the left of all odd-numbered +% pages when "twoside" printing is selected +\setlength{\textwidth}{6.375in} % assuming US letter paper (8.5 in. x 11 in.) and +% side margins as above +\raggedbottom + +% The following statement specifies the amount of space between +% paragraphs. Other reasonable specifications are \bigskipamount and \smallskipamount. +\setlength{\parskip}{\medskipamount} + +% The following statement controls the line spacing. The default +% spacing corresponds to good typographic conventions and only slight +% changes (e.g., perhaps "1.2"), if any, should be made. +\renewcommand{\baselinestretch}{1} % this is the default line space setting + +% By default, each chapter will start on a recto (right-hand side) +% page. We also force each section of the front pages to start on +% a recto page by inserting \cleardoublepage commands. +% In many cases, this will require that the verso page be +% blank and, while it should be counted, a page number should not be +% printed. The following statements ensure a page number is not +% printed on an otherwise blank verso page. +\let\origdoublepage\cleardoublepage +\newcommand{\clearemptydoublepage}{% + \clearpage{\pagestyle{empty}\origdoublepage}} +\let\cleardoublepage\clearemptydoublepage + +\newcounter{cit} +\newcounter{todo} + +% \newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace} +% \newcommand{\TODO}{{\large\bf\color{red} TODO: }\xspace} + +\newcommand\cit[1]{\refstepcounter{cit}\textsuperscript{[Citation Needed]}\xspace\addcontentsline{cit}{subsection}{\thecit~#1}}% +\newcommand\todo[1]{\refstepcounter{todo}{{\large\bf\color{red} TODO: }\xspace\color{red}{#1}}\addcontentsline{todo}{subsection}{\thetodo~#1}}% + +\makeatletter +\newcommand\citname{cit} +\newcommand\listcitname{List of missing citations} +\newcommand\listofcits{% + \section*{\listcitname}\@starttoc{cit}} +\makeatother + +\makeatletter +\newcommand\todoname{todo} +\newcommand\listtodoname{List of todos} +\newcommand\listoftodos{% + \section*{\listtodoname}\@starttoc{todo}} +\makeatother + +% cfa macros used in the document +\input{common} + +% glossary of terms to use +\input{glossary} + +%====================================================================== +% L O G I C A L D O C U M E N T -- the content of your thesis +%====================================================================== +\begin{document} + +% For a large document, it is a good idea to divide your thesis +% into several files, each one containing one chapter. +% To illustrate this idea, the "front pages" (i.e., title page, +% declaration, borrowers' page, abstract, acknowledgements, +% dedication, table of contents, list of tables, list of figures, +% nomenclature) are contained within the file "uw-ethesis-frontpgs.tex" which is +% included into the document by the following statement. +%---------------------------------------------------------------------- +% FRONT MATERIAL +%---------------------------------------------------------------------- +\input{text/front.tex} + + +%---------------------------------------------------------------------- +% MAIN BODY +%---------------------------------------------------------------------- +% Because this is a short document, and to reduce the number of files +% needed for this template, the chapters are not separate +% documents as suggested above, but you get the idea. If they were +% separate documents, they would each start with the \chapter command, i.e, +% do not contain \documentclass or \begin{document} and \end{document} commands. +\input{text/intro.tex} +\input{text/runtime.tex} +\input{text/core.tex} +\input{text/practice.tex} +\input{text/io.tex} + +%---------------------------------------------------------------------- +% END MATERIAL +%---------------------------------------------------------------------- + +% B I B L I O G R A P H Y +% ----------------------- + +% The following statement selects the style to use for references. It controls the sort order of the entries in the bibliography and also the formatting for the in-text labels. +\bibliographystyle{plain} +% This specifies the location of the file containing the bibliographic information. +% It assumes you're using BibTeX (if not, why not?). +\cleardoublepage % This is needed if the book class is used, to place the anchor in the correct page, + % because the bibliography will start on its own page. + % Use \clearpage instead if the document class uses the "oneside" argument +\phantomsection % With hyperref package, enables hyperlinking from the table of contents to bibliography +% The following statement causes the title "References" to be used for the bibliography section: +\renewcommand*{\bibname}{References} + +% Add the References to the Table of Contents +\addcontentsline{toc}{chapter}{\textbf{References}} + +\bibliography{uw-ethesis} +% Tip 5: You can create multiple .bib files to organize your references. +% Just list them all in the \bibliogaphy command, separated by commas (no spaces). + +% The following statement causes the specified references to be added to the bibliography% even if they were not +% cited in the text. The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional). +\nocite{*} + +% The \appendix statement indicates the beginning of the appendices. +\appendix +% Add a title page before the appendices and a line in the Table of Contents +\chapter*{APPENDICES} +\addcontentsline{toc}{chapter}{APPENDICES} +%====================================================================== +\chapter[PDF Plots From Matlab]{Matlab Code for Making a PDF Plot} +\label{AppendixA} +% Tip 4: Example of how to get a shorter chapter title for the Table of Contents +%====================================================================== +\section{Using the GUI} +Properties of Matab plots can be adjusted from the plot window via a graphical interface. Under the Desktop menu in the Figure window, select the Property Editor. You may also want to check the Plot Browser and Figure Palette for more tools. To adjust properties of the axes, look under the Edit menu and select Axes Properties. + +To set the figure size and to save as PDF or other file formats, click the Export Setup button in the figure Property Editor. + +\section{From the Command Line} +All figure properties can also be manipulated from the command line. Here's an example: +\begin{verbatim} +x=[0:0.1:pi]; +hold on % Plot multiple traces on one figure +plot(x,sin(x)) +plot(x,cos(x),'--r') +plot(x,tan(x),'.-g') +title('Some Trig Functions Over 0 to \pi') % Note LaTeX markup! +legend('{\it sin}(x)','{\it cos}(x)','{\it tan}(x)') +hold off +set(gca,'Ylim',[-3 3]) % Adjust Y limits of "current axes" +set(gcf,'Units','inches') % Set figure size units of "current figure" +set(gcf,'Position',[0,0,6,4]) % Set figure width (6 in.) and height (4 in.) +cd n:\thesis\plots % Select where to save +print -dpdf plot.pdf % Save as PDF +\end{verbatim} + +% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) +% ----------------------------- +\printglossary +\cleardoublepage +\phantomsection + +\end{document} Index: tools/vscode/uwaterloo.cforall-0.1.0/.gitignore =================================================================== --- tools/vscode/uwaterloo.cforall-0.1.0/.gitignore (revision 7a8011331cd3137af75be1b83777c648932350ce) +++ tools/vscode/uwaterloo.cforall-0.1.0/.gitignore (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -0,0 +1,2 @@ +node_modules/ +cfa-ls