Changeset f621e43f

Timestamp:

Mar 30, 2021, 2:44:56 PM (3 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

22b7579

Parents:

976bc68 (diff), a41e87b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:

• doc/theses/mubeen_zulfiqar_MMath/AllocDS1.fig (added)
• doc/theses/mubeen_zulfiqar_MMath/AllocDS2.fig (added)
• doc/theses/mubeen_zulfiqar_MMath/Makefile (modified) (2 diffs)
• doc/theses/mubeen_zulfiqar_MMath/allocator.tex (modified) (1 diff)
• doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex (modified) (2 diffs)
• tests/include/includes.cfa (modified) (5 diffs)

doc/theses/mubeen_zulfiqar_MMath/Makefile

@@ -1 @@
-### Makefile from Andrew Beach's Masters Thesis
+DOC = uw-ethesis.pdf
+BASE = ${DOC:%.pdf=%} # remove suffix
+# directory for latex clutter files
+BUILD = build
+TEXSRC = $(wildcard *.tex)
+FIGSRC = $(wildcard *.fig)
+BIBSRC = $(wildcard *.bib)
+TEXLIB = .:../../LaTeXmacros:${BUILD}: # common latex macros
+BIBLIB = .:../../bibliography # common citation repository
 
-DOC=uw-ethesis.pdf
-BUILD=out
-TEXSRC=$(wildcard *.tex)
-BIBSRC=$(wildcard *.bib)
-STYSRC=$(wildcard *.sty)
-CLSSRC=$(wildcard *.cls)
-TEXLIB= .:../../LaTeXmacros:${BUILD}:
-BIBLIB= .:../../bibliography
-
-# Since tex programs like to add their own file extensions:
-BASE= ${DOC:%.pdf=%}
+MAKEFLAGS = --no-print-directory # --silent
+VPATH = ${BUILD}
 
 ### Special Rules:
 
-.PHONY: all clean deepclean
+.PHONY: all clean
 
 ### Commands:
-LATEX=TEXINPUTS=${TEXLIB} pdflatex -halt-on-error -output-directory=${BUILD}
-BIBTEX=BIBINPUTS=${BIBLIB} bibtex
+LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD}
+BIBTEX = BIBINPUTS=${BIBLIB} bibtex
 #GLOSSARY=INDEXSTYLE=${BUILD} makeglossaries-lite
 
-### Rules and Recipies:
+### Rules and Recipes:
 
 all: ${DOC}
 
-${BUILD}/${DOC}: ${TEXSRC} ${BIBSRC} ${STYSRC} ${CLSSRC} Makefile | ${BUILD}
+${BUILD}/%.dvi: ${TEXSRC} ${FIGSRC:.fig=.tex} ${BIBSRC} Makefile | ${BUILD}
         ${LATEX} ${BASE}
         ${BIBTEX} ${BUILD}/${BASE}
@@ -33 +32 @@
 #       ${LATEX} ${BASE}
 
-${DOC}: ${BUILD}/${DOC}
-        cp $< $@
-
 ${BUILD}:
         mkdir $@
 
+%.pdf : ${BUILD}/%.ps | ${BUILD}
+        ps2pdf $<
+
+%.ps : %.dvi | ${BUILD}
+        dvips $< -o $@
+
+%.tex : %.fig | ${BUILD}
+        fig2dev -L eepic $< > ${BUILD}/$@
+
+%.ps : %.fig | ${BUILD}
+        fig2dev -L ps $< > ${BUILD}/$@
+
+%.pstex : %.fig | ${BUILD}
+        fig2dev -L pstex $< > ${BUILD}/$@
+        fig2dev -L pstex_t -p ${BUILD}/$@ $< > ${BUILD}/$@_t
+
 clean:
-        -@rm -rv ${BUILD}
-
-deepclean: clean
-        -@rm -v ${DOC}
+        @rm -frv ${DOC} ${BUILD} *.fig.bak

doc/theses/mubeen_zulfiqar_MMath/allocator.tex

@@ +1 @@
+
 \chapter{Allocator}
+
+\newpage
+\paragraph{Design 1: Decentralized}
+Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the sbrk area.
+Kernel threads (KT) are assigned to the N heaps.
+When KTs $\le$ N, the heaps are uncontented.
+When KTs $>$ N, the heaps are contented.
+By adjusting N, this approach reduces storage at the cost of speed due to contention.
+In all cases, a thread acquires/releases a lock, contented or uncontented.
+\begin{cquote}
+\centering
+\input{AllocDS1}
+\end{cquote}
+Problems: need to know when a KT is created and destroyed to know when to create/delete the KT's heap.
+On KT deletion, its heap freed-storage needs to be distributed somewhere.
+
+\paragraph{Design 2: Centralized}
+
+One heap, but lower bucket sizes are N-shared across KTs.
+This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
+When KTs $\le$ N, the important bucket sizes are uncontented.
+When KTs $>$ N, the free buckets are contented.
+Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
+\begin{cquote}
+\centering
+\input{AllocDS2}
+\end{cquote}
+Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
+When no thread is assigned a bucket number, its free storage is unavailable.
+It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.

doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex

@@ -81 +81 @@
 \usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments
 \usepackage{xcolor}
-\usepackage[pdftex]{graphicx}
+\usepackage{epic,eepic}
+\usepackage{graphicx}
 \usepackage{comment} % Removes large sections of the document.
 \usepackage{todonotes} % Adds todos (Must be included after comment.)
@@ -89 +90 @@
 % Use the "hyperref" package
 % N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE
-\usepackage[pdftex,pagebackref=true]{hyperref} % with basic options
+\usepackage[pagebackref=true]{hyperref} % with basic options
 %\usepackage[pdftex,pagebackref=true]{hyperref}
 % N.B. pagebackref=true provides links back from the References to the body text. This can cause trouble for printing.

tests/include/includes.cfa

@@ -40 +40 @@
 #include <errno.h>
 #include <error.h>
-//#include <eti.h>                                                                              // may not be installed
+//#include <eti.h>                                                                              // may not be installed, comes with ncurses
 #include <execinfo.h>
 #include <expat.h>
@@ -49 +49 @@
 #include <fmtmsg.h>
 #include <fnmatch.h>
-#include <form.h>
+//#include <form.h>                                                                             // may not be installed, comes with ncurses
 #include <fstab.h>
 #include <fts.h>
@@ -77 +77 @@
 #include <mcheck.h>
 #include <memory.h>
-#include <menu.h>
+//#include <menu.h>                                                                             // may not be installed, comes with ncurses
 #include <mntent.h>
 #include <monetary.h>
 #include <mqueue.h>
-#include <ncurses_dll.h>
+//#include <ncurses_dll.h>                                                                      // may not be installed, comes with ncurses
 #include <netdb.h>
 #include <nl_types.h>
 #include <nss.h>
 #include <obstack.h>
-#include <panel.h>
+//#include <panel.h>                                                                            // may not be installed, comes with ncurses
 #include <paths.h>
 #include <poll.h>
@@ -117 +117 @@
 #include <syslog.h>
 #include <tar.h>
-#include <term.h>
-#include <termcap.h>
+//#include <term.h>                                                                             // may not be installed, comes with ncurses
+//#include <termcap.h>                                                                          // may not be installed, comes with ncurses
 #include <termio.h>
 #include <termios.h>
@@ -130 +130 @@
 #include <ucontext.h>
 #include <ulimit.h>
-#include <unctrl.h>
+//#include <unctrl.h>                                                                           // may not be installed, comes with ncurses
 #include <unistd.h>
 #include <utime.h>