-
Notifications
You must be signed in to change notification settings - Fork 43
/
example-scribe-notes.tex
175 lines (152 loc) · 7.01 KB
/
example-scribe-notes.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
\documentclass[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
\usepackage{graphicx}
\usepackage{url}
%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
\newcommand{\dnl}{\mbox{}\par}
%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{#1}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf COMPSCI~590S~~~Systems for Data Science
\hfill Fall 2016} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Lecture #1: #2 \hfill} }
\vspace{2mm}
\hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe(s): #4} }
\vspace{2mm}}
}
\end{center}
\markboth{Lecture {#1}: #2}{Lecture {#1}: #2}
\vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}
% \input{epsf}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
\vspace{0.2 in}
\setlength{\epsfxsize}{#2}
\centerline{\epsfbox{#4}}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
\ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\llap{$##$}\tabskip\z@skip\crcr
#1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
#1\crcr}}
\makeatother
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
% Some general latex examples and examples making use of the
% macros follow.
\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{1}{Memory Allocation}{Emery Berger}{Udit Saxena,Freddie Sanchez}
\section{Continuation of discussion on Grappa }
We discussed the concept of 'Work Stealing' and the difference from Work Stealing and Work Sharing.
\begin{enumerate}
\item Work Stealing :
\begin{enumerate}
\item Proactively go and "steal" work from an overloaded fellow worker.
\item It is used for load imbalance correction. There can be different strategies -
\begin{enumerate}
\item Randomly choosing a victim and then decide how much work to take.
\item "Half Stealing" - steal half the work of the chosen victim.
\item "The power of two choices" - between two choices, we pick the victim as the one with more work.
\end{enumerate}
\item Work Stealing is more fine grained when looking at degree of load balancing control.
\item Only the processes with "no work" are doing the load balancing work.
\end{enumerate}
\item Work Sharing :
\begin{enumerate}
\item Another load sharing paradigm where load is "shed" onto other workers. Different strategies include :
\begin{enumerate}
\item Random picking
\item Round Robin
\item Min-first
\end{enumerate}
\item Work Sharing is coarse grained when looking at degree of load balancing control.
\item Everyone needs to be asked for their load.
\item When workers are asking/answering to a query for their load, they aren't doing meaningful work - this situation gets worse when everyone is asking everyone for their work. \\
But to prevent the issue of stopping working when asking/being asked, we the concept of lock-free data structures.
\end{enumerate}
\end{enumerate}
\section{Cooperative Scheduling}
While on a single core, processes go to sleep and are context-switched out on an I/O call. \\
The process scheduling framework can be thought of as a scheduling - descheduling framework. \\ \\
There are two kinds of scheduling:
\begin{enumerate}
\item: Preemptive Scheduling: Every process gets a time quantum (~5ms). On the expiration of this time slice, the process is context-switched out, and another process is allowed to continue computation. \\
This kind of scheduling is good for preventing malicious processes from taking an arbitrarily long computation time. \\
The problem with this kind of scheduling is:
\begin{enumerate}
\item High scheduling overhead with lower granularity
\item Lock Convoying
\item Warm up or collateral damage or frequent cache flushing.
\end{enumerate}
\item: Cooperative Scheduling: In Cooperative scheduling, a process is allowed to continue processing until it explicitly yields the CPU for another process to continue. The onus is on the process to hand over the CPU - if it doesn't, it can keep processing for as long as it wants. This is used in environments which are considered safe and have no malicious processes.
\end{enumerate}
\section{Page based DSM}
Page based DSM refers to the Distributed Shared Memory at the level of a page which is the smallest unit of memory being shared across the distributed system. There are two kinds:
\begin{enumerate}
\item True Sharing : When the same location on the same page needs to be shared across a distributed system. When the page is both logically and physically shared.
\item False Sharing: When different locations on the same page need to be shared. Here the locations are logically unshared, but physically shared.
\end{enumerate}
False sharing is overcome by using diff merges/updates - it is a cheaper mode of communication.
Grappa doesn't do this - it batches updates to amortize update overhead.
\section{Delegation}
This concept of completing work on the local machine rather than remotely doing the work. It is based on the principle that local memory access is way cheaper than remote memory access.
\end{document}