\documentclass[10pt,a4paper]{article} % Packages \usepackage{fancyhdr} % For header and footer \usepackage{multicol} % Allows multicols in tables \usepackage{tabularx} % Intelligent column widths \usepackage{tabulary} % Used in header and footer \usepackage{hhline} % Border under tables \usepackage{graphicx} % For images \usepackage{xcolor} % For hex colours %\usepackage[utf8x]{inputenc} % For unicode character support \usepackage[T1]{fontenc} % Without this we get weird character replacements \usepackage{colortbl} % For coloured tables \usepackage{setspace} % For line height \usepackage{lastpage} % Needed for total page number \usepackage{seqsplit} % Splits long words. %\usepackage{opensans} % Can't make this work so far. Shame. Would be lovely. \usepackage[normalem]{ulem} % For underlining links % Most of the following are not required for the majority % of cheat sheets but are needed for some symbol support. \usepackage{amsmath} % Symbols \usepackage{MnSymbol} % Symbols \usepackage{wasysym} % Symbols %\usepackage[english,german,french,spanish,italian]{babel} % Languages % Document Info \author{jackiechenjx} \pdfinfo{ /Title (cs2100-midterms.pdf) /Creator (Cheatography) /Author (jackiechenjx) /Subject (cs2100 midterms Cheat Sheet) } % Lengths and widths \addtolength{\textwidth}{6cm} \addtolength{\textheight}{-1cm} \addtolength{\hoffset}{-3cm} \addtolength{\voffset}{-2cm} \setlength{\tabcolsep}{0.2cm} % Space between columns \setlength{\headsep}{-12pt} % Reduce space between header and content \setlength{\headheight}{85pt} % If less, LaTeX automatically increases it \renewcommand{\footrulewidth}{0pt} % Remove footer line \renewcommand{\headrulewidth}{0pt} % Remove header line \renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit % This two commands together give roughly % the right line height in the tables \renewcommand{\arraystretch}{1.3} \onehalfspacing % Commands \newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour \newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols \newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns \newcommand{\tn}{\tabularnewline} % Required as custom column type in use % Font and Colours \definecolor{HeadBackground}{HTML}{333333} \definecolor{FootBackground}{HTML}{666666} \definecolor{TextColor}{HTML}{333333} \definecolor{DarkBackground}{HTML}{66CCFF} \definecolor{LightBackground}{HTML}{EBF8FF} \renewcommand{\familydefault}{\sfdefault} \color{TextColor} % Header and Footer \pagestyle{fancy} \fancyhead{} % Set header to blank \fancyfoot{} % Set footer to blank \fancyhead[L]{ \noindent \begin{multicols}{3} \begin{tabulary}{5.8cm}{C} \SetRowColor{DarkBackground} \vspace{-7pt} {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}} } \end{tabulary} \columnbreak \begin{tabulary}{11cm}{L} \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{cs2100 midterms Cheat Sheet}}}} \\ \normalsize{by \textcolor{DarkBackground}{jackiechenjx} via \textcolor{DarkBackground}{\uline{cheatography.com/194887/cs/40724/}}} \end{tabulary} \end{multicols}} \fancyfoot[L]{ \footnotesize \noindent \begin{multicols}{3} \begin{tabulary}{5.8cm}{LL} \SetRowColor{FootBackground} \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}} \\ \vspace{-2pt}jackiechenjx \\ \uline{cheatography.com/jackiechenjx} \\ \end{tabulary} \vfill \columnbreak \begin{tabulary}{5.8cm}{L} \SetRowColor{FootBackground} \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}} \\ \vspace{-2pt}Not Yet Published.\\ Updated 9th October, 2023.\\ Page {\thepage} of \pageref{LastPage}. \end{tabulary} \vfill \columnbreak \begin{tabulary}{5.8cm}{L} \SetRowColor{FootBackground} \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}} \\ \SetRowColor{white} \vspace{-5pt} %\includegraphics[width=48px,height=48px]{dave.jpeg} Measure your website readability!\\ www.readability-score.com \end{tabulary} \end{multicols}} \begin{document} \raggedright \raggedcolumns % Set font size to small. Switch to any value % from this page to resize cheat sheet text: % www.emerson.emory.edu/services/latex/latex_169.html \footnotesize % Small font. \begin{multicols*}{3} \begin{tabularx}{5.377cm}{x{0.82386 cm} x{2.24273 cm} x{1.51041 cm} } \SetRowColor{DarkBackground} \mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{Number System}} \tn % Row 0 \SetRowColor{LightBackground} & 1s-complement & \seqsplit{2s-complement} \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} Min & -(2\textasciicircum{}n-1\textasciicircum{}-1) & -(2\textasciicircum{}n-1\textasciicircum{}) \tn % Row Count 2 (+ 1) % Row 2 \SetRowColor{LightBackground} Max & 2\textasciicircum{}n-1\textasciicircum{}-1 & 2\textasciicircum{}n-1\textasciicircum{}-1 \tn % Row Count 3 (+ 1) % Row 3 \SetRowColor{white} \seqsplit{Zero(s)} & 0, 2\textasciicircum{}n\textasciicircum{}-1 & 0 \tn % Row Count 4 (+ 1) % Row 4 \SetRowColor{LightBackground} \seqsplit{Negation} & 2\textasciicircum{}n\textasciicircum{} - X -1 & 2\textasciicircum{}n\textasciicircum{}-X \tn % Row Count 6 (+ 2) % Row 5 \SetRowColor{white} Addition\textasciicircum{}{[}1{]}\textasciicircum{} & Add carry out to result & Ignore carry out \tn % Row Count 8 (+ 2) % Row 6 \SetRowColor{LightBackground} & Sign-Magnitude & Excess \tn % Row Count 9 (+ 1) % Row 7 \SetRowColor{white} Min & -(2\textasciicircum{}n-1\textasciicircum{}-1) & -excess \tn % Row Count 10 (+ 1) % Row 8 \SetRowColor{LightBackground} Max & 2\textasciicircum{}n-1\textasciicircum{}-1 & 2\textasciicircum{}n\textasciicircum{}-excess-1 \tn % Row Count 11 (+ 1) % Row 9 \SetRowColor{white} \seqsplit{Zero(s)} & 0, 2\textasciicircum{}n-1\textasciicircum{} & excess \tn % Row Count 12 (+ 1) % Row 10 \SetRowColor{LightBackground} & Diminished radix \{\{nl\}\} (r-1)'s complement & Radix \{\{nl\}\} r's complement \tn % Row Count 15 (+ 3) % Row 11 \SetRowColor{white} Definition\textasciicircum{}{[}2{]}\textasciicircum{} & (r\textasciicircum{}n - 1) - X & r\textasciicircum{}n\textasciicircum{} - X \tn % Row Count 18 (+ 3) \hhline{>{\arrayrulecolor{DarkBackground}}---} \SetRowColor{LightBackground} \mymulticolumn{3}{x{5.377cm}}{ASCII: 1bit parity + 7bit content \newline C string: Should end with '\textbackslash{}0' \newline \textasciicircum{}{[}1{]}\textasciicircum{} overflow if the result is opposite sign of A and B \newline \textasciicircum{}{[}2{]}\textasciicircum{} radix -\textgreater{} base (e.g. 999...99 - X for base-9)} \tn \hhline{>{\arrayrulecolor{DarkBackground}}---} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{x{1.64241 cm} x{3.33459 cm} } \SetRowColor{DarkBackground} \mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{MIPS - Assembly}} \tn % Row 0 \SetRowColor{LightBackground} branch/jump labels & Does not count as instn. \tn % Row Count 2 (+ 2) % Row 1 \SetRowColor{white} lw \& sw & Should use offset in multiple of 4 \tn % Row Count 4 (+ 2) % Row 2 \SetRowColor{LightBackground} Instruction Executed & Initial instn.\{\{nl\}\}+num of loops\{\{nl\}\}~~* loop instn.\{\{nl\}\}+ exit loop instn.\{\{nl\}\}+ end instn. \tn % Row Count 9 (+ 5) \hhline{>{\arrayrulecolor{DarkBackground}}--} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{X} \SetRowColor{DarkBackground} \mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{MIPS - Memory}} \tn % Row 0 \SetRowColor{LightBackground} \mymulticolumn{1}{x{5.377cm}}{32 registers, each 32-bit (4-byte) long} \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} \mymulticolumn{1}{x{5.377cm}}{Each word contains 32 bits (4 bytes)} \tn % Row Count 2 (+ 1) % Row 2 \SetRowColor{LightBackground} \mymulticolumn{1}{x{5.377cm}}{Memory addresses are 32-bit long} \tn % Row Count 3 (+ 1) % Row 3 \SetRowColor{white} \mymulticolumn{1}{x{5.377cm}}{2\textasciicircum{}30\textasciicircum{} memory words\textasciicircum{}{[}1{]}\textasciicircum{}} \tn % Row Count 4 (+ 1) \hhline{>{\arrayrulecolor{DarkBackground}}-} \SetRowColor{LightBackground} \mymulticolumn{1}{x{5.377cm}}{\textasciicircum{}{[}1{]}\textasciicircum{} Consecutive words differ by 4 bytes} \tn \hhline{>{\arrayrulecolor{DarkBackground}}-} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{x{1.24425 cm} x{3.73275 cm} } \SetRowColor{DarkBackground} \mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{MIPS - Encoding}} \tn % Row 0 \SetRowColor{LightBackground} branch & If the branch is {\bf{not taken}}:\{\{nl\}\}~~PC=PC+4\{\{nl\}\}If the branch is {\bf{taken}}:\{\{nl\}\}~~PC=(PC+4)+immd*4 \tn % Row Count 5 (+ 5) % Row 1 \SetRowColor{white} I-format\textasciicircum{}{[}1{]}\textasciicircum{} & 16-bit immd only! \tn % Row Count 7 (+ 2) % Row 2 \SetRowColor{LightBackground} J-format\textasciicircum{}{[}2{]}\textasciicircum{} & 26-bit target address \tn % Row Count 9 (+ 2) % Row 3 \SetRowColor{white} & Max Jump: 256MB \tn % Row Count 10 (+ 1) \hhline{>{\arrayrulecolor{DarkBackground}}--} \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{\textasciicircum{}{[}1{]}\textasciicircum{} `li` = `lui` upper 16-bit + `ori` lower 16-bit \newline \textasciicircum{}{[}2{]}\textasciicircum{} Actual address: 4-bit PC MSB + 26-bits + 2-bit word-aligned(00)} \tn \hhline{>{\arrayrulecolor{DarkBackground}}--} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{x{2.4885 cm} x{2.4885 cm} } \SetRowColor{DarkBackground} \mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{ISA - Design Philosophy}} \tn % Row 0 \SetRowColor{LightBackground} RISC & CISC \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} E.g. x86-32 & E.g. MIPS, ARM \tn % Row Count 2 (+ 1) % Row 2 \SetRowColor{LightBackground} Single instruction performs complex operation & Small and simple instruction set \tn % Row Count 5 (+ 3) % Row 3 \SetRowColor{white} Smaller program size as memory was premium & Complex implementation, no room for hardware optimizatio \tn % Row Count 8 (+ 3) % Row 4 \SetRowColor{LightBackground} Complex implementation, no room for hardware optimizatio & Burden on software to combine simpler operations to implement high-level language statements \tn % Row Count 13 (+ 5) \hhline{>{\arrayrulecolor{DarkBackground}}--} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{p{0.45947 cm} x{0.8354 cm} x{1.92142 cm} x{0.96071 cm} } \SetRowColor{DarkBackground} \mymulticolumn{4}{x{5.377cm}}{\bf\textcolor{white}{ISA - Data Storage}} \tn % Row 0 \SetRowColor{LightBackground} \mymulticolumn{4}{x{5.377cm}}{{\bf{Example for C = A+B}}} \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} Stack & \seqsplit{Accumulator} & Register\{\{nl\}\}(load-store) & \seqsplit{Memory-Memory} \tn % Row Count 3 (+ 2) % Row 2 \SetRowColor{LightBackground} Push A & Load A & Load R1, A & Add C, A, B \tn % Row Count 5 (+ 2) % Row 3 \SetRowColor{white} Push B & Add B & Load R2, B & \tn % Row Count 7 (+ 2) % Row 4 \SetRowColor{LightBackground} Add & Store C & Add R3, R1, R2 & \tn % Row Count 8 (+ 1) % Row 5 \SetRowColor{white} Pop C & & Store R3, C & \tn % Row Count 10 (+ 2) \hhline{>{\arrayrulecolor{DarkBackground}}----} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{x{2.4885 cm} x{2.4885 cm} } \SetRowColor{DarkBackground} \mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{ISA - Memory Addressing Mode}} \tn % Row 0 \SetRowColor{LightBackground} Big-Endian & Little-Endian \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} MSB stored in lowest address & LSB stored in lowest address \tn % Row Count 3 (+ 2) \hhline{>{\arrayrulecolor{DarkBackground}}--} \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{{\emph{MIPS is Big-Endian}}} \tn \hhline{>{\arrayrulecolor{DarkBackground}}--} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{p{0.59501 cm} x{2.65466 cm} x{1.32733 cm} } \SetRowColor{DarkBackground} \mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{ISA - Operations in Instructions Set}} \tn % Row 0 \SetRowColor{LightBackground} \mymulticolumn{3}{x{5.377cm}}{{\bf{Frequently Used Instructions}}} \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} Rank & Instruction & Average \% \tn % Row Count 2 (+ 1) % Row 2 \SetRowColor{LightBackground} 1 & Load & 22\% \tn % Row Count 3 (+ 1) % Row 3 \SetRowColor{white} 2 & Conditional Branch & 20\% \tn % Row Count 4 (+ 1) % Row 4 \SetRowColor{LightBackground} 3 & Compare & 16\% \tn % Row Count 5 (+ 1) % Row 5 \SetRowColor{white} 4 & Store & 12\% \tn % Row Count 6 (+ 1) \hhline{>{\arrayrulecolor{DarkBackground}}---} \SetRowColor{LightBackground} \mymulticolumn{3}{x{5.377cm}}{Amdahl's law – make the common cases fast! \newline If the total time originally: \newline T = (0.7 * t) + (0.3 * t) \newline Decrease common by 50\%, uncommon by 50\% \newline T = (0.7 * 0.5 * t) + (0.3 * 1.5 * t) \newline T = (0.80 * t) -\textgreater{} Faster} \tn \hhline{>{\arrayrulecolor{DarkBackground}}---} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{x{1.04517 cm} x{3.93183 cm} } \SetRowColor{DarkBackground} \mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Datapath}} \tn % Row 0 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{{\bf{Instruction Execution Cycle}}} \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} \mymulticolumn{2}{x{5.377cm}}{1. Fetch} \tn % Row Count 2 (+ 1) % Row 2 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{Use the PC to fetch instn from memory} \tn % Row Count 3 (+ 1) % Row 3 \SetRowColor{white} \mymulticolumn{2}{x{5.377cm}}{Increment PC by 4} \tn % Row Count 4 (+ 1) % Row 4 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{2. Decode} \tn % Row Count 5 (+ 1) % Row 5 \SetRowColor{white} \mymulticolumn{2}{x{5.377cm}}{Read the `opcode` to determine instruction type} \tn % Row Count 6 (+ 1) % Row 6 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{Read from all necessary registers} \tn % Row Count 7 (+ 1) % Row 7 \SetRowColor{white} \mymulticolumn{2}{x{5.377cm}}{3. Execute} \tn % Row Count 8 (+ 1) % Row 8 \SetRowColor{LightBackground} \seqsplit{Performs} & - Arithmetic, shifting, logical \tn % Row Count 9 (+ 1) % Row 9 \SetRowColor{white} & - Address calculation \tn % Row Count 10 (+ 1) % Row 10 \SetRowColor{LightBackground} & - Register comparison \tn % Row Count 11 (+ 1) % Row 11 \SetRowColor{white} & - Target address calculation \tn % Row Count 12 (+ 1) % Row 12 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{4. Memory} \tn % Row Count 13 (+ 1) % Row 13 \SetRowColor{white} \mymulticolumn{2}{x{5.377cm}}{Use memory address calculated by ALU Stage} \tn % Row Count 14 (+ 1) % Row 14 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{Read from or write to data memory} \tn % Row Count 15 (+ 1) % Row 15 \SetRowColor{white} \mymulticolumn{2}{x{5.377cm}}{5. Register Write} \tn % Row Count 16 (+ 1) % Row 16 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{Write into registers} \tn % Row Count 17 (+ 1) \hhline{>{\arrayrulecolor{DarkBackground}}--} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{x{1.28156 cm} x{1.32733 cm} x{1.96811 cm} } \SetRowColor{DarkBackground} \mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{Control Path}} \tn % Row 0 \SetRowColor{LightBackground} {\bf{Control Signal}} & {\bf{Execution}} & {\bf{Purpose}} \tn % Row Count 2 (+ 2) % Row 1 \SetRowColor{white} `RegDst` & \seqsplit{Decode/Fetch} & 0: Inst{[}20:16{]}\{\{nl\}\}1: Inst{[}15:11{]} \tn % Row Count 4 (+ 2) % Row 2 \SetRowColor{LightBackground} `RegWrite` & Decode/Fetch\{\{nl\}\}/RegWrite & 0: Idle\{\{nl\}\}1: Register write \tn % Row Count 7 (+ 3) % Row 3 \SetRowColor{white} `ALUSrc` & ALU & 0: Register RD 2\{\{nl\}\}1: SignExt(Inst{[}15:0{]}) \tn % Row Count 10 (+ 3) % Row 4 \SetRowColor{LightBackground} \seqsplit{`ALUcontrol`} & ALU & Select the operation to be performed \tn % Row Count 13 (+ 3) % Row 5 \SetRowColor{white} `MemRead`\{\{nl\}\}/`MemWrite` & Memory & 0: Idle\{\{nl\}\}1: Performs \tn % Row Count 16 (+ 3) % Row 6 \SetRowColor{LightBackground} `MemToReg` & RegWrite & 1: Memory RD\{\{nl\}\}0: ALU result \tn % Row Count 18 (+ 2) % Row 7 \SetRowColor{white} `PCSrc` & Memory\{\{nl\}\}/RegWrite & 0: PC + 4\{\{nl\}\}1: SignExt(Inst{[}15:0{]}) \textless{}\textless{} 2 + (PC + 4) \tn % Row Count 22 (+ 4) \hhline{>{\arrayrulecolor{DarkBackground}}---} \end{tabularx} \par\addvspace{1.3em} \begin{tabularx}{5.377cm}{x{1.24425 cm} x{3.73275 cm} } \SetRowColor{DarkBackground} \mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{ISA - Instruction}} \tn % Row 0 \SetRowColor{LightBackground} \mymulticolumn{2}{x{5.377cm}}{{\bf{Fixed Length Instruction Encoding}}} \tn % Row Count 1 (+ 1) % Row 1 \SetRowColor{white} Type-A & 2 * 5-bit operands \tn % Row Count 2 (+ 1) % Row 2 \SetRowColor{LightBackground} Type-B & 1 * 5-bit operand \tn % Row Count 3 (+ 1) % Row 3 \SetRowColor{white} Maximum & Maximise Type-B \tn % Row Count 4 (+ 1) % Row 4 \SetRowColor{LightBackground} & 1 + (2\textasciicircum{}6\textasciicircum{} - 1) * 2\textasciicircum{}5\textasciicircum{} \tn % Row Count 5 (+ 1) % Row 5 \SetRowColor{white} Minimum & Maximise Type-A \tn % Row Count 6 (+ 1) % Row 6 \SetRowColor{LightBackground} & 2\textasciicircum{}6\textasciicircum{} - 1 + 2\textasciicircum{}5\textasciicircum{} \tn % Row Count 7 (+ 1) \hhline{>{\arrayrulecolor{DarkBackground}}--} \end{tabularx} \par\addvspace{1.3em} % That's all folks \end{multicols*} \end{document}