\subsubsection{Cache}
\label{cache}

The \cache is specified by the following definitions 
\cite{smith1982cache} \cite{sebek2001state} \cite{mellor2001improving} 
\cite{zahran2007cache} \cite{jaleel2010high} \cite{Srilatha12}:\\

(1) It is a small high speed memory usually Static RAM (SRAM) 
that contains the most recently accessed pieces of main memory. \\

(2) Cache memories are small, high-speed buffer memories used 
in modern computer systems to hold temporarily those portions of 
the contents of main memory which are (believed to be) currently in use.\\

(3) In Cheddar ADL, the \cache is named $Generic_{-}Cache$ in the xml schema.\\

\begin{center}
Standard attributes
\end{center}

$Name$ : the unique name of a $Cache$.\\

$Cache_{-}Size$: the size of a cache - the number of bytes that a cache can contain.\\

$Line_{-}Size$: the number of contiguous bytes that are transferred from main memory on a cache miss. When the cache does not contain the memory block requested, the transaction is said to be a cache miss.\\

$Associativity$: the number of cache locations where a particular memory block may reside. \\	

$Block_{-}Reload_{-}Time$: the time to access a memory block that is not in the cache. \\

$Replacement_{-}Policy$:a policy which decides which cache block should be replaced 
when a new memory block needs to be stored in the cache. \\

$Coherence_{-}Protocol$: a protocol which maintains the consistency between all the 
	caches in a system of distributed shared memory.\\
	
$Cache_{-}Category$: specifies a cache as instruction cache,
 data cache or a combined one.\\

$Cache_{-}Blocks$: TO BE COMPLETED \\

$Write_{-}Policy$: TO BE COMPLETED \\

 
\begin{center}
Legality rules
\end{center}

(L1) The cache name must not be empty.\\

(L2) The cache name must be valid identifier.\\

(L3) $Cache_{-}size > 0 $.\\

(L4) $Block_{-}size > 0 $.\\

(L5) $Cache_{-}Size \: MOD \: Block_{-}Size = 0 $.\\

(L6) $Hit_{-}Time > Miss_{-}Time > 0 $.\\

(L7) The $Coherence_{-}Protocol$ of $Instruction_{-}Cache$ can only be $Shared_{-}Cache_{-}Protocol$ or  $Private_{-}Cache_{-}Protocol$. \\

\begin{center}
Annexes
\end{center}

(A1) The kinds of $Associativity$ :\\

\indent \indent (A11) $Fully_{-}Associative_{-}Cache$: when a memory block can reside in any locations 
in the cache ($Associativity = Cache_{-}Size{/}Block_{-}Size$).\\

\indent \indent (A12) $Direct_{-}Mapped_{-}Cache$: when a memory block can reside in exactly one location 
in the cache ($Associtivity = 1$).\\

\indent \indent (A13) A way set associative cache: when a memory block can reside in exactly $A$ location 
in the cache ($Associativity = A$).

In this case, we have 
		$$Number_{-}of_{-}set_{-}of_{-}the_{-}cache = \frac{Number_{-}of_{-}block}{A}$$.\\
		
(A2) The replacement policies :\\

\indent \indent (A21) $Random$: this policy randomly replace a selected block 
among all blocks currently in cache.\\

\indent \indent (A22) $Least_{-}Recently_{-}Used (LRU)$: it replaces the block in 
cache that has not been used for the longest time.\\

\indent \indent (A23) $Least_{-}Recently_{-}Replaced (LRR)$: it replaces the 
block in cache that has not been replaced for the longest time.\\
		
\indent \indent (A24) $First_{-}in, First_{-}out (FiFo)$: it evicts the block 
that has been in the cache the longest.\\

(A3) The types of coherence protocols.\\

\indent \indent (A31) $Shared_{-}Cache_{-}Protocol$: cache is shared between cores.\\

\indent \indent (A32) $Private_{-}Cache_{-}Protocol$: each core has its private cache.\\

\indent \indent (A33) $Private_{-}Invalid_{-}Cache_{-}Protocol$: when a core writes into a memory block in the
cache,all copies of this memory block in other cores' cache are invalidated.\\

\indent \indent (A34) $Private_{-}MSI_{-}Cache_{-}Protocol$: M,S,I stand for 
Modified, Shared and Invalid. 

They are three possibles states that a block inside the cache can have. 
This protocol is used in the 4D machine \cite{baskett19984d}.\\

\indent \indent (A35) $Private_{-}MESI_{-}Cache_{-}Protocol$: MESI stand 
for Modified, Exclusive, Shared and Invalid. This cache coherence protocol 
is derived from MSI protocol. More information about the MESI protocol can be 
found in \cite{papamarcos1984low}\\

(A4) The $Cache_{-}Category$:\\

\indent \indent (A41) $Data_{-}Cache$: cache which is used in order to 
speed up data fetch and store. \\

\indent \indent (A42) $Instruction_{-}Cache$: cache which is used in order 
to speed up executable instruction fetch. $Instruction_{-}Cache$ is in fact a 
cache where coherence protocol is $Private_{-}Cache_{-}Protocol$ or $Shared_{-}Cache_{-}Protocol$.\\

\indent \indent (A43) $Data_{-}Instruction_{-}Cache$: both data and instructions are stored in cache.\\

(A5) Type of write policies.\\

\indent \indent (A51) $Write{-}Back$ (called also $Copy{-}Back$, $Write_{-}Behind$): 
the information is written only to the block in the \cache. 

The modified block is written in the memory only when the cache is replaced.\\

\indent \indent (A52) $Write_{-}Through$: the information is written both in 
the block to cache and the block in the main-memory.\\

\indent \indent \indent \indent (A521) $Write_{-}Through_{-}With_{-}Allocation$: memory 
block at the missed-write location is loaded to cache then followed by a 
write operation in the \cache. \\

\indent \indent \indent \indent (A522) $Write_{-}Through_{-}Without_{-}Allocation$:  
memory block at the missed-write location is not loaded to the cache and 
written directly in the higher level memory. \\

\begin{figure}[H]{}
\begin{lstlisting}{}

<!ELEMENT caches (generic_cache | data_cache | 
	instruction_cache | data_instruction_cache | 
	cache_system)+>
	
<!ELEMENT generic_cache (object_type | name | 
	cache_size | line_size | associativity | 
	replacement_policy | block_reload_time | 
	coherence_protocol | cache_category)*>
<!ATTLIST generic_cache id ID #REQUIRED>

<!ELEMENT data_cache (object_type | name | cache_size | 
	line_size | associativity | cache_replacement | 
	block_reload_time | coherence_protocol | 
	cache_category | write_policy)*>
<!ATTLIST data_cache id ID #REQUIRED>

<!ELEMENT instruction_cache (object_type | name | 
	cache_size | line_size | associativity | 
	replacement_policy | block_reload_time | 
	coherence_protocol | cache_category)*>
<!ATTLIST instruction_cache id ID #REQUIRED>

<!ELEMENT data_instruction_cache (object_type | name | 
	cache_size | line_size | associativity | 
	replacement_policy | block_reload_time | 
	coherence_protocol | cache_category | 
	write_policy)*>
<!ATTLIST data_instruction_cache id ID #REQUIRED>

<!ELEMENT cache_system (object_type | name | caches)*>
<!ATTLIST cache_system id ID #REQUIRED>

\end{lstlisting}
	\caption{The DTD of entity $Cache$}
	\label{dtd_cache}
\end{figure}

\begin{center}
Implementation
\end{center}

The figure \ref{dtd_cache} gives the DTD of entity \cache.

\begin{figure}[H]{}
\begin{lstlisting}{}

<instruction_cache id=" 1" >
	<object_type>CACHE_OBJECT_TYPE</object_type>
	<name>Cache_01</name>
	<cache_size>2048</cache_size>
	<line_size>8</line_size>
	<associativity>2</associativity>
	<replacement_policy>LRU</replacement_policy>
	<block_reload_time>10.00000</block_reload_time>
	<coherence_protocol>
		PRIVATE_CACHE_PROTOCOL
	</coherence_protocol>
	<cache_category>
		INSTRUCTION_CACHE_TYPE
	</cache_category>
</instruction_cache>

\end{lstlisting}
\caption{An Example of entity \cache}
\label{cache_example}
\end{figure}

\begin{center}
Example
\end{center}

The figure \ref{cache_example} gives an example of entity \cache 
described using Cheddar ADL. It describes an 2-ways set associative 
($Associativity = 2$) instruction cache with cache size 2048 bytes 
(2 KB) and block size 8 bytes. The replacement policy is Least Recently Used.