Page MenuHomec4science
Files F94103920

exo3_raffaele_ancarola.tex
No OneTemporary
Actions

File Metadata

Created
Tue, Dec 3, 22:50

exo3_raffaele_ancarola.tex
View Options

\documentclass{article}
% Change "article" to "report" to get rid of page number on title page
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{setspace}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{extramarks}
\usepackage{chngpage}
\usepackage{soul}
\usepackage[usenames,dvipsnames]{color}
\usepackage{graphicx,float,wrapfig}
\usepackage{ifthen}
\usepackage{listings}
\usepackage{courier}
\usepackage{makecell}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{wrapfig}
\usepackage{multicol}
\usepackage{float}
\usepackage{verbatim}
\usepackage[T1]{fontenc}
\usepackage{comment}
\usepackage{systeme}
\usepackage[table,xcdraw]{xcolor}
\usepackage{array}
\usepackage{physics}
% !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
%
% Here put your info (name, due date, title etc).
% the rest should be left unchanged.
%
%
%
% !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
% Homework Specific Information
\newcommand{\hmwkTitle}{Exercise 3}
\newcommand{\hmwkSubTitle}{}
\newcommand{\hmwkDueDate}{\today}
\newcommand{\hmwkClass}{Introduction to multiprocessor architecture}
\newcommand{\hmwkClassTime}{}
%\newcommand{\hmwkClassInstructor}{Prof. Oleg Yazyev}
\newcommand{\hmwkAuthorName}{Raffaele Ancarola}
%
%
% In case you need to adjust margins:
\topmargin=-0.45in %
\evensidemargin=0in %
\oddsidemargin=0in %
\textwidth=6.5in %
\textheight=9.5in %
\headsep=0.25in %
% This is the color used for comments below
\definecolor{MyDarkGreen}{rgb}{0.0,0.4,0.0}
% units of mesure
\usepackage{siunitx}
% comments
\usepackage{comment}
% pgfplots environment
%package setup for graphs
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{pgfplotstable}
\usetikzlibrary{patterns}
\usepgfplotslibrary{external}
\pgfplotsset{compat=newest}
%pgfplot setup
\makeatletter
\pgfplotsset{
/pgfplots/flexible xticklabels from table/.code n args={3}{%
\pgfplotstableread[#3]{#1}\coordinate@table
\pgfplotstablegetcolumn{#2}\of{\coordinate@table}\to\pgfplots@xticklabels
\let\pgfplots@xticklabel=\pgfplots@user@ticklabel@list@x
},
% layer definition
layers/my layer set/.define layer set={
background,
main,
foreground
}{
% you could state styles here which should be moved to
% corresponding layers, but that is not necessary here.
% That is why we don't state anything here
},
% activate the newly created layer set
set layers=my layer set
}
\makeatother
\IfFileExists{./tikzext.perm}{\tikzexternalize[prefix=tikzext/]}{\tikzexternalize}
% pfgplots add graphics
\makeatletter
\newcommand\addplotgraphicsnatural[2][]{%
\begingroup
% set options in this local group (will be lost afterwards):
\pgfqkeys{/pgfplots/plot graphics}{#1}%
% measure the natural size of the graphics:
\setbox0=\hbox{\includegraphics{#2}}%
%
% compute the required unit vector ratio:
\pgfmathparse{\wd0/(\pgfkeysvalueof{/pgfplots/plot graphics/xmax} - \pgfkeysvalueof{/pgfplots/plot graphics/xmin})}%
\let\xunit=\pgfmathresult
\pgfmathparse{\ht0/(\pgfkeysvalueof{/pgfplots/plot graphics/ymax} - \pgfkeysvalueof{/pgfplots/plot graphics/ymin})}%
\let\yunit=\pgfmathresult
%
% configure pgfplots to use it.
% The \xdef expands all macros except those prefixed by '\noexpand'
% and assigns the result to a global macro named '\marshal'.
\xdef\marshal{%
\noexpand\pgfplotsset{unit vector ratio={\xunit\space \yunit}}%
}%
\endgroup
%
% use our macro here:
\marshal
%
\addplot graphics[#1] {#2};
}
\makeatother
% For faster processing, load Matlab syntax for listings
\lstloadlanguages{Matlab}%
\lstset{language=Matlab, % Use MATLAB
frame=single, % Single frame around code
basicstyle=\small\ttfamily, % Use small true type font
keywordstyle=[1]\color{Blue}\bf, % MATLAB functions bold and blue
keywordstyle=[2]\color{Purple}, % MATLAB function arguments purple
keywordstyle=[3]\color{Blue}\underbar, % User functions underlined and blue
identifierstyle=, % Nothing special about identifiers
% Comments small dark green courier
commentstyle=\usefont{T1}{pcr}{m}{sl}\color{MyDarkGreen}\small,
stringstyle=\color{Purple}, % Strings are purple
showstringspaces=false, % Don't put marks in string spaces
tabsize=3, % 5 spaces per tab
breaklines=True,
%
%%% Put standard MATLAB functions not included in the default
%%% language here
morekeywords={xlim,ylim,var,alpha,factorial,poissrnd,normpdf,normcdf},
%
%%% Put MATLAB function parameters here
morekeywords=[2]{on, off, interp},
%
%%% Put user defined functions here
morekeywords=[3]{FindESS, homework_example},
%
morecomment=[l][\color{Blue}]{...}, % Line continuation (...) like blue comment
numbers=left, % Line numbers on left
firstnumber=1, % Line numbers start with line 1
numberstyle=\tiny\color{Blue}, % Line numbers are blue
stepnumber=1 % Line numbers go in steps of 5
}
% Setup the header and footer
\pagestyle{fancy} %
\lhead{\hmwkAuthorName} %
%\chead{\hmwkClass\ (\hmwkClassInstructor\ \hmwkClassTime): \hmwkTitle} %
\rhead{\hmwkClass\ : \hmwkTitle} %
%\rhead{\firstxmark} %
\lfoot{\lastxmark} %
\cfoot{} %
\rfoot{Page\ \thepage\ of\ \protect\pageref{LastPage}} %
\renewcommand\headrulewidth{0.4pt} %
\renewcommand\footrulewidth{0.4pt} %
% This is used to trace down (pin point) problems
% in latexing a document:
%\tracingall
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Some tools
\newcommand{\enterProblemHeader}[1]{\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak}%
\newcommand{\exitProblemHeader}[1]{\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1}{}\nobreak}%
\newlength{\labelLength}
\newcommand{\labelAnswer}[2]
{\settowidth{\labelLength}{#1}%
\addtolength{\labelLength}{0.25in}%
\changetext{}{-\labelLength}{}{}{}%
\noindent\fbox{\begin{minipage}[c]{\columnwidth}#2\end{minipage}}%
\marginpar{\fbox{#1}}%
% We put the blank space above in order to make sure this
% \marginpar gets correctly placed.
\changetext{}{+\labelLength}{}{}{}}%
\setcounter{secnumdepth}{0}
\newcommand{\homeworkProblemName}{}%
\newcounter{homeworkProblemCounter}%
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]%
{\stepcounter{homeworkProblemCounter}%
\renewcommand{\homeworkProblemName}{#1}%
\section{\homeworkProblemName}%
\enterProblemHeader{\homeworkProblemName}}%
{\exitProblemHeader{\homeworkProblemName}}%
\newcommand{\problemAnswer}[1]
{\noindent\fbox{\begin{minipage}[c]{\columnwidth}#1\end{minipage}}}%
\newcommand{\problemLAnswer}[1]
{\labelAnswer{\homeworkProblemName}{#1}}
\newcommand{\homeworkSectionName}{}%
\newlength{\homeworkSectionLabelLength}{}%
\newenvironment{homeworkSection}[1]%
{% We put this space here to make sure we're not connected to the above.
% Otherwise the changetext can do funny things to the other margin
\renewcommand{\homeworkSectionName}{#1}%
\settowidth{\homeworkSectionLabelLength}{\homeworkSectionName}%
\addtolength{\homeworkSectionLabelLength}{0.25in}%
\changetext{}{-\homeworkSectionLabelLength}{}{}{}%
\subsection{\homeworkSectionName}%
\enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]}}%
{\enterProblemHeader{\homeworkProblemName}%
% We put the blank space above in order to make sure this margin
% change doesn't happen too soon (otherwise \sectionAnswer's can
% get ugly about their \marginpar placement.
\changetext{}{+\homeworkSectionLabelLength}{}{}{}}%
\newcommand{\sectionAnswer}[1]
{% We put this space here to make sure we're disconnected from the previous
% passage
\noindent\fbox{\begin{minipage}[c]{\columnwidth}#1\end{minipage}}%
\enterProblemHeader{\homeworkProblemName}\exitProblemHeader{\homeworkProblemName}%
\marginpar{\fbox{\homeworkSectionName}}%
% We put the blank space above in order to make sure this
% \marginpar gets correctly placed.
}%
%%% I think \captionwidth (commented out below) can go away
%%%
%% Edits the caption width
%\newcommand{\captionwidth}[1]{%
% \dimen0=\columnwidth \advance\dimen0 by-#1\relax
% \divide\dimen0 by2
% \advance\leftskip by\dimen0
% \advance\rightskip by\dimen0
%}
% Includes a figure
% The first parameter is the label, which is also the name of the figure
% with or without the extension (e.g., .eps, .fig, .png, .gif, etc.)
% IF NO EXTENSION IS GIVEN, LaTeX will look for the most appropriate one.
% This means that if a DVI (or PS) is being produced, it will look for
% an eps. If a PDF is being produced, it will look for nearly anything
% else (gif, jpg, png, et cetera). Because of this, when I generate figures
% I typically generate an eps and a png to allow me the most flexibility
% when rendering my document.
% The second parameter is the width of the figure normalized to column width
% (e.g. 0.5 for half a column, 0.75 for 75% of the column)
% The third parameter is the caption.
\newcommand{\scalefig}[3]{
\begin{figure}[ht!]
% Requires \usepackage{graphicx}
\centering
\includegraphics[width=#2\columnwidth]{#1}
%%% I think \captionwidth (see above) can go away as long as
%%% \centering is above
%\captionwidth{#2\columnwidth}%
\caption{#3}
\label{#1}
\end{figure}}
% Includes a MATLAB script.
% The first parameter is the label, which also is the name of the script
% without the .m.
% The second parameter is the optional caption.
\newcommand{\matlabscript}[2]
{\begin{itemize}\item[]\lstinputlisting[caption=#2,label=#1]{#1.m}\end{itemize}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Make title
%\title{\vspace{2in}\textmd{\textbf{\hmwkClass:\ \hmwkTitle\ifthenelse{\equal{\hmwkSubTitle}{}}{}{\\\hmwkSubTitle}}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \hmwkClassTime}}\vspace{3in}}
%\title{\vspace{2in}\textmd{\textbf{\hmwkClass:\ \hmwkTitle\ifthenelse{\equal{\hmwkSubTitle}{}}{}{\\\hmwkSubTitle}}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\\vspace{0.1in}\large{\textit{ \hmwkClassTime}}\vspace{3in}}
\title{\textmd{\textbf{\hmwkClass:\ \hmwkTitle\ifthenelse{\equal{\hmwkSubTitle}{}}{}{\\\hmwkSubTitle}}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\\vspace{0.1in}\large{\textit{ \hmwkClassTime}}}
\date{\today}
\author{\textbf{\hmwkAuthorName}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\begin{spacing}{1.1}
\maketitle
% Uncomment the \tableofcontents and \newpage lines to get a Contents page
% Uncomment the \setcounter line as well if you do NOT want subsections
% listed in Contents
%\setcounter{tocdepth}{1}
%\newpage
%\tableofcontents
%\newpage
% When problems are long, it may be desirable to put a \newpage or a
% \clearpage before each homeworkProblem environment
%\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{homeworkProblem}
\begin{homeworkSection}{(1)}
\paragraph{SWMR}: Single Writer, Multiple Reader. For each memory block,
and for a fixed time, many units can read the stocked value but only one is allowed
to write it. Principle: the last writer and any other reader has a valid copy of the stocked value.
\end{homeworkSection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{homeworkSection}{(2)}
The first difference is that cores don't have the authority to write onto it's own cache in the default case \texttt{S},
implying more security in data coherence (can write in $1/3$ of the cases instead of $1/2$).
A \texttt{PWr} operation doesn't forcely imply a \texttt{DataWB}, precisely a new written value
is broadcasted only if it's needed again.
\end{homeworkSection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{homeworkSection}{(3)}
Performance improvement: if a value is managed by only one cache, then
\texttt{BusInv} (invalidate all other caches), which is an expensive operation, can be omitted.
\end{homeworkSection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{homeworkSection}{(4)}
The primary purpose of a directory is to restrict an action which is sent from a core to the smallest group of caches which
are involved with that action. In this sense, a directory-based system allows to manage coherence by many
small regroupements of caches instead of the bus, which acts on the global scope.
\end{homeworkSection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{homeworkSection}{(5)}
Sparse directories buffers in principle have the same size of non-sparse directories, but
it organizes the cache way blocks together as function of the last bits in the \texttt{tag} field.
When no tags bits are used, the associativity is maximal.
Supposing each cache has a $A_{cache} = 4$-way associativity level, then for a fixed cache index
a directory managing $4$ cores (then $4$ caches) has to emplace in total $16$-way blocks.
Imagine now that the directory organizes those blocks in a $A_{dir} = 8$-way associativity level using
the last three bits of the \texttt{tag} field as identifier ($3 = \log_2(8)$), then it's enough
that $3$ blocks share the same value of these three bits to have a conflict. Such a conflict is raised
because the directory supports at maximum $2 = \frac{16}{8}$ values to be equal in those last three bits.
More generally:
\begin{equation}
\#bit_{max} = \frac{\#cores \; \cdot \; A_{cache}}{A_{dir}}
\end{equation}
\end{homeworkSection}
\begin{homeworkSection}{(6)}
False sharing is a coherence cache miss and occures when two cores write different values on the same cache block.
It's bad because in this case the MSI protocol would generate an excess of invalidations and
memory updates, in sense that in order to maintain coherence, addictional \texttt{BusInv} and \texttt{DataBW} are necessary operation.
\end{homeworkSection}
\begin{homeworkSection}{(7)}
\paragraph{Loop fusion}: when more independent loops have the same iteration pattern on the header \texttt{for(int i=0; i < N; ++i)},
then loops overhead and consequent cache misses can be reduced putting all them together in a single loop block.
\begin{lstlisting}
/* Before optimization */
float a = 3.0;
float b = 2.0;
for (int i = 0; i < N; ++i) {
a += 0.5 * i;
}
for (int i = 0; i < N; ++i) {
b += 0.2 * i;
}
/* After optimization */
float a = 3.0;
float b = 2.0;
for (int i = 0; i < N; ++i) {
a += 0.5 * i;
b += 0.2 * i;
}
\end{lstlisting}
\end{homeworkSection}
\begin{homeworkSection}{(8)}
True sharing can be reduced by minimizing the data dependence between threads.
Parallelizing only independent tasks totally avoids true sharing.
\end{homeworkSection}
\end{homeworkProblem}
%\end{spacing}
\end{document}

Event Timeline

c4science · Help