\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{hziad}
\pdfinfo{
  /Title (computer-architecture.pdf)
  /Creator (Cheatography)
  /Author (hziad)
  /Subject (computer architecture 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}{A3A3A3}
\definecolor{LightBackground}{HTML}{F3F3F3}
\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{computer architecture Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{hziad} via \textcolor{DarkBackground}{\uline{cheatography.com/24934/cs/6357/}}}
\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}hziad \\
  \uline{cheatography.com/hziad} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 11th December, 2015.\\
   Updated 13th May, 2016.\\
   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*}{4}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{The memory access time is \seqsplit{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}. \newline % Row Count 1 (+ 1)
a) The time from initiation to completion of a word or byte transfer from RAM \newline % Row Count 3 (+ 2)
N the cache memory that uses write-through protocol, if a write miss occurs \_\_\_\_\_\_\_\_. \newline % Row Count 5 (+ 2)
b) The data is written directly to the main RAM. \newline % Row Count 6 (+ 1)
In pipelined RISC processors, data dependencies can be handled. \newline % Row Count 8 (+ 2)
d) All of the above. \newline % Row Count 9 (+ 1)
A block-direct-mapped cache consists of a total of 32 blocks. The main memory contains  \newline % Row Count 11 (+ 2)
2K blocks, each consisting of 8 words. Each word is 4 bytes. Assuming a 16-bit byte-addressable \newline % Row Count 13 (+ 2)
 Address space, how many bits are there in each of the Tag, Block, and Word fields? \newline % Row Count 15 (+ 2)
c) Tag= 6 bits. Block=5 bits, Word= 5 bits. \newline % Row Count 16 (+ 1)
A block-associative-mapped cache consists of a total of 32 blocks. The main memory contains  \newline % Row Count 18 (+ 2)
2K blocks, each consisting of 8 words. Each word is 4 bytes. Assuming a 16-bit byte-addressable \newline % Row Count 20 (+ 2)
 Address space, how many bits are there in each of the Tag, Block, and Word fields? \newline % Row Count 22 (+ 2)
A) Tag= 11 bits. Block=0 bits, Word= 5 bits. \newline % Row Count 23 (+ 1)
A block-4-way associative-mapped cache consists of a total of 32 blocks. The main memory \newline % Row Count 25 (+ 2)
 Contains 2K blocks, each consisting of 8 words. Each word is 4 bytes. Assuming a  \newline % Row Count 27 (+ 2)
16-bit byte-addressable address space, how many bits are there in each of the Tag, Set, and Word fields? \newline % Row Count 30 (+ 3)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{B) Tag= 9 bits. Set=2 bits, Word= 5 bits. \newline % Row Count 1 (+ 1)
By using the Booth algorithm recoding technique, the binary multiplier  \newline % Row Count 3 (+ 2)
0 1 0 0 1 1 0 1 1 1 0 will be recoded as: \newline % Row Count 4 (+ 1)
A) +1 -1 0 +1 0 -1 +1 0 0 -1 0 \newline % Row Count 5 (+ 1)
The processor uses the Instruction Register (IR) to: \newline % Row Count 7 (+ 2)
Keep the instruction to be executed until it is finished. \newline % Row Count 9 (+ 2)
 Q1: How many chips you need to build a memory module of size 4M8 bits, if you only have \newline % Row Count 11 (+ 2)
 Chips of size 256K1 bits.  \newline % Row Count 12 (+ 1)
a)	128 \newline % Row Count 13 (+ 1)
 Q2: A block-direct-associative cache consists of a total of 64 blocks. The main memory  \newline % Row Count 15 (+ 2)
Contains 1K blocks, each consisting of 8 words. Each word is 4 bytes. Assuming a  \newline % Row Count 17 (+ 2)
16-bit byte-addressable address space, how many bits are there in each of the Tag, Set,  \newline % Row Count 19 (+ 2)
And Word fields?  \newline % Row Count 20 (+ 1)
a) Tag= 5 bits. Block=6 bits, Word= 5 bits.  \newline % Row Count 21 (+ 1)
 Q3: The memory access time is:  \newline % Row Count 22 (+ 1)
a)	The time from initiation to completion of a word or byte transfer. \newline % Row Count 24 (+ 2)
Q4: Compared to the static RAM, the dynamic RAM is:  \newline % Row Count 26 (+ 2)
a) Slower, Cheaper, Simpler, and always needs refreshing.  \newline % Row Count 28 (+ 2)
 Q5: The Double-Data-Rate (DDR) SDRAM:  \newline % Row Count 29 (+ 1)
a)	Transfers data on the rising and falling edges of its own clock cycle.  \newline % Row Count 31 (+ 2)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{ Q6: The hierarchy of the memory in a computer is (starting from the processor):  \newline % Row Count 2 (+ 2)
a)	Registers, Cache, RAM, and Hard disk.  \newline % Row Count 3 (+ 1)
Q7: The flash memory is made of:  \newline % Row Count 4 (+ 1)
a) EEPROM cells.  \newline % Row Count 5 (+ 1)
 Q1: How many chips you need to build a memory module of size 4M8 bits, if you only  \newline % Row Count 7 (+ 2)
Have chips of size 256K2 bits.  \newline % Row Count 8 (+ 1)
a)	64  \newline % Row Count 9 (+ 1)
 Q2: A block-direct- cache consists of a total of 32 blocks. The main memory \newline % Row Count 11 (+ 2)
 Contains 4K blocks, each consisting of 4 words. Each word is 4 bytes. Assuming  \newline % Row Count 13 (+ 2)
A 16-bit byte-addressable address space, how many bits are there in each of the Tag, \newline % Row Count 15 (+ 2)
 Set, and Word fields?  \newline % Row Count 16 (+ 1)
a) Tag= 6 bits. Block=5 bits, Word= 4 bits.  \newline % Row Count 17 (+ 1)
Q8: To solve the problem of data dependency in pipelining architectures, -{}-{}-{}-{}-{}-{}-{}-{}-{}--: \newline % Row Count 19 (+ 2)
a) Processors use data forwarding.  \newline % Row Count 20 (+ 1)
b) The compiler insert NOP operation between the instructions.  \newline % Row Count 22 (+ 2)
c) The pipeline has to stall until the operands are ready.  \newline % Row Count 24 (+ 2)
d) Any of the other options.  \newline % Row Count 25 (+ 1)
Q9: To solve the problem of branch penalty in pipelining architectures, -{}-{}-{}-{}-{}-{}-{}-{}-{}--: \newline % Row Count 27 (+ 2)
a) Processors use delayed branching technique.  \newline % Row Count 28 (+ 1)
b) Processors use branch prediction technique.  \newline % Row Count 29 (+ 1)
c) Processors use branch target buffer.  \newline % Row Count 30 (+ 1)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{d) All of the other options.  \newline % Row Count 1 (+ 1)
Q10: The pipeline may stall because of: \newline % Row Count 2 (+ 1)
a) Data dependency.  \newline % Row Count 3 (+ 1)
b) Cache miss.  \newline % Row Count 4 (+ 1)
c) Limited hardware resources.  \newline % Row Count 5 (+ 1)
d) All of the other options.  \newline % Row Count 6 (+ 1)
Q11: Although the throughput increases by increasing the number of stages in \newline % Row Count 8 (+ 2)
 The pipeline, the number of \newline % Row Count 9 (+ 1)
a) The probability of data dependency will increase.  \newline % Row Count 11 (+ 2)
b) The branch penalty will increase.  \newline % Row Count 12 (+ 1)
c) The cache misses may increase.  \newline % Row Count 13 (+ 1)
d) All of the other options  \newline % Row Count 14 (+ 1)
Q2: The processor's control signals are generated by: \newline % Row Count 16 (+ 2)
a) Only hardware and called Hardwired approach  \newline % Row Count 17 (+ 1)
b) Only software and called Microprogrammed approach  \newline % Row Count 19 (+ 2)
c) Either (a) or (b)  \newline % Row Count 20 (+ 1)
Q3: In pipelining, to alleviate the problem of branch delayed slot problem:  \newline % Row Count 22 (+ 2)
a)	The compiler tries to find a suitable instruction that precedes the branch and move it after the branch instruction.  \newline % Row Count 25 (+ 3)
 Q5: The Double-Data-Rate (DDR) SDRAM:  \newline % Row Count 26 (+ 1)
a)	Transfers data on the rising and falling edges of its own clock cycle.  \newline % Row Count 28 (+ 2)
 Q1: By using the Booth algorithm recoding technique, the binary multiplier 0 1 0 1 1 1 0 1 0 1 1 will be:  \newline % Row Count 31 (+ 3)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{b)	a) +1 -1 +1 0 0 -1 +1 - 1 +1 0 -1  \newline % Row Count 1 (+ 1)
 Q2: Which statement from the following is true?  \newline % Row Count 2 (+ 1)
a) The ripple-carry adder is slower than the carry-lookahead adder.  \newline % Row Count 4 (+ 2)
 Q3: Which statement from the following is true?  \newline % Row Count 5 (+ 1)
a)	The 2-dimensional combinational array is faster than sequential circuit multiplier.  \newline % Row Count 7 (+ 2)
Q8: How many chips you need to build a memory module of size 1G32 bits, if you only have chips of size 128M64 bits.  \newline % Row Count 10 (+ 3)
a) 4  \newline % Row Count 11 (+ 1)
Q9: A block direct-mapped cache consists of a total of 128 blocks. The main memory contains 64K blocks, each consisting of 16 words. Each word is 4 bytes. Assuming a 16-bit byte-addressable address space, how many bits are there in each of the Tag, Block, and Word fields?  \newline % Row Count 17 (+ 6)
a)	Tag= 3 bits. Block=7 bits, Word= 6 bits.  \newline % Row Count 18 (+ 1)
Q10: A block associative-mapped cache consists of a total of 64 blocks. The main memory contains 64K blocks, each consisting of 8 words. Each word is 4 bytes. Assuming a 16-bit byte-addressable address space, how many bits are there in each of the Tag, Block, and Word fields?  \newline % Row Count 24 (+ 6)
a)	Tag= 11 bits. Block=0 bits, Word= 5 bits.  \newline % Row Count 25 (+ 1)
Q13: The access time for the hard disk is:  \newline % Row Count 26 (+ 1)
a)	The sum of the seek time and rotational delay.  \newline % Row Count 28 (+ 2)
Q14: The Digital Versatile Disk stores up to 17GB because:  \newline % Row Count 30 (+ 2)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{a)	It uses two-layered two-sided disks, and red-light laser.  \newline % Row Count 2 (+ 2)
Q15: The CD-ReWritables (CD-RW) uses:  \newline % Row Count 3 (+ 1)
a)	Three different laser powers with an organic dye and alloy of materials in the recording layer.  \newline % Row Count 5 (+ 2)
Q16: The magnetic hard disk is formatted as:  \newline % Row Count 6 (+ 1)
a)	Tracks and sectors in each platter.  \newline % Row Count 7 (+ 1)
Q17: In virtual memory, a page fault occurs:  \newline % Row Count 8 (+ 1)
a)	When a virtual address has no corresponding physical address.  \newline % Row Count 10 (+ 2)
Q18: Which statement is true?  \newline % Row Count 11 (+ 1)
a)	The processor always issues a virtual address and the MMU translates it to a physical address.  \newline % Row Count 13 (+ 2)
Q19: In the cache memory, the no hit occurs when:  \newline % Row Count 15 (+ 2)
a)	The tag match occurs and the valid bit is 0.  \newline % Row Count 16 (+ 1)
Q20: In the cache memory that uses write-back protocol, if a write miss occurs:  \newline % Row Count 18 (+ 2)
a) First transfer block containing the addressed word into the cache and then overwrite specific word in cached block.  \newline % Row Count 21 (+ 3)
Q21: The cache memory makes the RAM to appear to the processor as much faster because of:  \newline % Row Count 23 (+ 2)
a)	The locality of reference of computer programs.  \newline % Row Count 25 (+ 2)
Q22: The choice of a RAM chip for a given application depends on:  \newline % Row Count 27 (+ 2)
a)	The cost, speed, power dissipation, and size of the chip.  \newline % Row Count 29 (+ 2)
Q23: The main problem in DRAMs is:  \newline % Row Count 30 (+ 1)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{a)	They are slow and need refreshing of their contents.  \newline % Row Count 2 (+ 2)
Q24: The main problem in static RAMs is:  \newline % Row Count 3 (+ 1)
a)	They use six transistors to build each cell.  \newline % Row Count 4 (+ 1)
Q25: Pipelining is used in RISC processors to:  \newline % Row Count 5 (+ 1)
a)	Increase the processor's throughput.  \newline % Row Count 6 (+ 1)
Q26: The 5-satges in the pipelined RISC processors is in the following order:  \newline % Row Count 8 (+ 2)
a)	Fetch, Decode, Compute, Memory, Write.  \newline % Row Count 9 (+ 1)
Q27: In pipelined RISC processors, data dependencies can be handled by:  \newline % Row Count 11 (+ 2)
a)	Any one of the other options.  \newline % Row Count 12 (+ 1)
Q28: In pipelined RISC processors, the ideal time (throuput) needed to execute one instruction is:  \newline % Row Count 14 (+ 2)
a) One clock cycle.  \newline % Row Count 15 (+ 1)
Q29: In pipelined RISC processors, what makes the actual throughput less than the ideal one is:  \newline % Row Count 17 (+ 2)
a) All of the other options.  \newline % Row Count 18 (+ 1)
b) The stall times due to data dependencies.  \newline % Row Count 19 (+ 1)
c) The branch penalties.  \newline % Row Count 20 (+ 1)
d) The caches misses.  \newline % Row Count 21 (+ 1)
Q30: The processor uses the program counter (PC) to:  \newline % Row Count 23 (+ 2)
a)	Keep track of the address of the next instruction to be fetched and executed.  \newline % Row Count 25 (+ 2)
Q31: In pipelined RISC processors, executing the instruction (Add R3, R4, R5) requires the following steps in order:  \newline % Row Count 28 (+ 3)
a)	Fetch, Decode, Compute, No-action, and Write result into register. \newline % Row Count 30 (+ 2)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{multiple choice (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{Q32: The processor's control signals can be generated by using:  \newline % Row Count 2 (+ 2)
a)	Either hardwired or microprogramming control% Row Count 3 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{rate of instruction execution}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{1-GHz clock. Instruction statistics in a large program are as follows: Branch 20\% Load 20\% Store 10\% Computational instructions 50\%} \tn 
% Row Count 3 (+ 3)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{90\% of instruction fetch operations are completed in one clock cycle and 10\% are completed in 4 clock cycles. On average, access to the data operands of a Load or Store, instruction is completed in 3 clock cycles} \tn 
\mymulticolumn{1}{x{3.833cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}On average, instruction fetch takes 0.9+0.1x4 = 1.3 cycles. All instructions, except Load and Store, take four more cycles to complete. Load and Store instructions take two additional cycles, on average. Average completion time = 1.3 + (0.2 + 0.5) x 4 + (0.2 + 0.1) x 6 = 5.9 cycles Instruction rate = 109 /5.9 = 169.5 million instructions per second} \tn 
% Row Count 16 (+ 13)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{a) Access to the memory is always completed in 1 clock cycle.} \tn 
\mymulticolumn{1}{x{3.833cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}Execution rate = 1x109 /5 = 200 million instructions per second} \tn 
% Row Count 20 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{chapter 5 example}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{{\bf{Call\_register R9 }}  \newline • Calls a subroutine whose address is in register R9: \newline 1. Memory address \textless{}- {[}PC{]}, Read memory, IR \textless{}-Memory data, PC \textless{}-{[}PC{]} \textless{}- 4 \newline 2. Decode instruction, RA \textless{}-{[}R9{]} \newline 3. PC-Temp\textless{}-{[}PC{]}, PC \textless{}-{[}RA{]} \newline 4. RY \textless{}- {[}PC-Temp{]} \newline 5. Register LINK \textless{}- {[}RY{]} \newline  \newline {\bf{Q1: Assume that all memory access operations are completed in one clock}} {\bf{cycle in a processor that has a 1-GHz clock. What is the frequency of memory access operations if Load and Store instructions constitute 20 percent of the dynamic instruction count in a program? (The dynamic count is the number of instruction executions, including the effect of program loops, which may cause some instructions to be executed more than once.) Assume that all instructions are executed in 5 clock cycles}} \newline There is one memory access to fetch each instruction. Then, 20 percent of the \newline instructions have a second memory access to read or write a memory \newline operand. On average, each instruction has 1.2 memory accesses in 5 clock cycles. Therefore, the frequency of memory accesses is (1.2/5) × 10\textasciicircum{}9 \newline , or 240 million accesses per second.(1 Ghz= 10\textasciicircum{}9 hz) \newline {\bf{ Give the sequence of actions for a Return-from-subroutine instruction in a RISC processor. Assume that the address LINK of the general-purpose register in which the subroutine return address is stored is given in the instruction field connected to address A of the register file (IR31−27).}} \newline Whenever an instruction is loaded into the IR, the contents of the generalpurpose \newline register whose address is given in bits IR31−27 are read and placed \newline into register RA. Hence, a Return-from-subroutine instruction will cause the contents of register LINK to be read and placed in register RA. \newline Execution proceeds as follows: \newline 1. Memory address←{[}PC{]}, Read memory, Wait for MFC, \newline IR←Memory data, PC←{[}PC{]} + 4 2. Decode instruction, RA←{[}LINK{]} 3. PC←{[}RA{]} 4. No action 5. No action \newline  \newline {\bf{At the time the instruction Load R6, 1000(R9) is fetched, R6 and R9 contain the values 4200 and 85320, respectively. Memory location 86320 contains 75900. }} \newline step 1 and 2: the values are determined by the previous instructions  \newline stept 3: RA = 85320, RB = 4200. Step 4:  RA = 85320, RB = 4200, RZ = 86320, RM= 4200. Step 5:  RA = 85320, RB = 4200, RZ = 86320, RM= 4200 RY = 75900.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{16M × 32 memory using 1M × 4 memory chips}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449843832_a.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{A 16M module can be structured as 16 rows, each containing eight 1M x 4 chips. A 24-bit address is required. Address lines A19-0 should be connected to all chips. Address lines A23-20 should be connected to a 4-bit decoder to select one of the 16 rows.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{A block-set-associative cache}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{{\bf{A block-set-associative cache consists of a total of 64 blocks, divided into 4-block sets. The main memory contains 4096 blocks, each consisting of 32 words. Assuming a 32-bit byte-addressable address space, how many bits are there in each of the Tag, Set, and Word fields?}} \newline Each block contains 128 bytes, thus requiring a 7-bit Word field. There are 16 sets, requiring a 4-bit Set field. The remaining 21 bits of the address constitute the tag field.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{problem set {\bf{Mult}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449849740_example mult.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{A = 010111 and B = 110110 \newline b) A = 110011 and B = 101100 \newline c) A = 001111 and B = 001111}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{Question about the sequential circuit}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{{\bf{how to implement multiplication of 2's-complement n-bit numbers using the Booth algorithm, by clearly specifying inputs and outputs for the Control sequencer and any other changes needed around the adder and register A.}} \newline % Row Count 5 (+ 5)
Both the A and M registers are augmented by one bit to the left to hold a sign extension bit. The adder is changed to an n + 1-bit adder. A bit is added to the right end of the Q register to implement the Booth multiplier recoding operation. It is initially set to zero. The control logic decodes the two bits at the right end of the Q register according to the Booth algorithm. The right shift is an arithmetic right shift as indicated by the repetition of the extended sign bit at the left end of the A register.% Row Count 16 (+ 11)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{R2, R3, R4, R5, R6, and R7}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{Load R2, \#A\_VEC \newline Load R3, \#B\_VEC \newline Load R4, \#3 \newline And R5, R5, R0 \newline  LOOP: Load R6, (R2) \newline Load R7, (R3) \newline Multiply R6, R6, R7 \newline Add R5, R5, R6 \newline Add R2, R2, \#4 \newline Add R3, R3, \#4 \newline Subtract R4, \#1 \newline Branch\textgreater{}0 LOOP \newline Load R7, \# RESULT \newline Store R5. (R7) \newline End \newline ORIGIN 500 \newline A\_VEC: DATAWORD 05, -20, 10 \newline B\_VEC: DATAWORD 09, 04, 07 \newline RESULT: RESERVE 4  \newline R2=512, R3=524, R4=0, R5=25 R6=7 R7=524} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{pipeline provides forwarding paths}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449827414_pipline example.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{The result from theALU is 130 − 12 = 118. This result is available in register RZ during cycle 6. The result of the Or instruction, 130, is in register RY during in cycle 6. In cycle 6, the Subtract instruction is in the Memory stage. The unspecified instruction following the Subtract instruction is generating a result in the Compute stage. In cycle 7, the result of the unspecified instruction is in register RZ, and the result of the Subtract instruction is in register RY.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{Chapter 6 execution time and speed up}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{{\bf{Assume that 20\% of the dynamic count of the instructions executed for a program are branch instructions. There are no pipeline stalls due to data dependencies. • Static branch prediction is used with a not-taken assumption. a) Determine the execution times for two cases: when 30 percent of the branches are taken, and when 70 percent of the branches are taken. b) Determine the speedup for one case relative to the other. Express the speedup as a percentage relative to 1}} \newline In first case, 30\% of branches are taken but we assumed not-taken, so they are mispredicted (one cycle penalty 30\% from 20\% branch instructions): The value of δbranch\_penalty = 0.20 × 0.30 ×1 = 0.06 \newline In second case, 70\% of branches are taken but we assumed not-taken, so they are mispredicted (one cycle penalty 70\% from 20\% branchs): The value of δbranch\_penalty = 0.20 × 0.70 ×1 = 0.14 \newline Using S = 1 + δbranch\_penalty, the execution time: \newline in first case is (1.06 × N)/R and (1.14 × N)/R for the second case. \newline b) Because the execution time for the first case is smaller, the performance improvement as a speedup percentage is:(1.14/1.06 -1)*100=7.5\%} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{Chapter 9}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{Overflow =cn ⊕ cn−1 or xn−1 yn−1( ̅sn−1) +( ̅xn−1)( ̅yn−1) sn−1} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{For the subtraction operation X−Y on 2's-complement numbers X and Y • We form the 2's-complement of Y and add it to X . • Set Add/Sub =0 and c0= 0 for addition. • Set Add/Sub =1 and c0 = 1 for subtraction} \tn 
% Row Count 7 (+ 5)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{4-bit adder has four carry-out signals: c1 = G0 + P0 c0, c2 = G1 + P1G0 + P1P0 c0, c3 = G2 + P2G1 + P2P1G0 + P2P1P0 c0, c4 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0 c0} \tn 
% Row Count 11 (+ 4)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{A sequence of n addition cycles generates a 2n-bit product Delay = n * (adder + control delays)} \tn 
% Row Count 13 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{For n = 32, delay is approximately 32  14 = 448 gate delays} \tn 
% Row Count 15 (+ 2)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{3.833cm}}{Registers A and Q are shift registers, together, they hold partial product PPi while multiplier bit qi generates the signal Add/Noadd.At the end of each cycle, C, A, and Q are shifted right one bit position to allow for growth of the partial product as the multiplier is shifted out of register Q} \tn 
% Row Count 21 (+ 6)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{• Non-Restoring Division:}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449849083_div2.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{{\bf{Stage 1}}: Do the following two steps n times: \newline 1. If the sign of A is 0, shift A and Q left one bit position and subtract M from A; otherwise, shift A and Q left and add M to A. \newline 2. Now, if the sign of A is 0, set q0 to 1; otherwise, set q0 to 0. \newline {\bf{Stage 2}}: If the sign of A is 1, add M to A.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{example}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449850171_mult.png}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{Store R6, X(R8)}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449811279_Capture.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{Memory address {[}PC{]}, \newline Read memory, \newline IR  Memory data, \newline PC  {[}PC{]}  4 \newline 2. Decode instruction, \newline RA {[}R8{]}, RB {[}R6{]} \newline 3. RZ {[}RA{]}  Immediate value X, \newline RM {[}RB{]} \newline 4. Memory address {[}RZ{]}, \newline Memory data {[}RM{]}, \newline Write memory \newline 5. No action}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{Add R5, R6}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449811689_cisc style processors.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{(on Bus B) Memory address ← {[}PC{]}, \newline Read memory, Wait for MFC, (on Bus C) IR ← Memory data, \newline PC ←{[}PC{]} + 4 \newline 2. Decode instruction \newline 3. The contents of R5 and R6 are sent to ALU \newline using buses A and B, \newline R5 ←{[}R5{]} + {[}R6{]}, \newline the sum is written to R5 using bus C}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{sequential mult UNSIGNED}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449848077_seq.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{13*11}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{Booth algorithm}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449848642_bootha.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{booth mult example}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449848765_boothssss.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{3.833cm}}{\bf\textcolor{white}{Restoring Division}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{3.833cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/hziad_1449848965_division.PNG}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{3.833cm}}{• Do the following three steps n times: \newline 1. Shift A and Q left one bit position. \newline 2. Subtract M from A, and place the answer back in A. \newline 3. If the sign of A is 1, set q0 to 0 and add M back to A (that is, restore A); otherwise, set q0 to 1.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}