Expertiza_Wiki - User contributions [en]

CSC 456 Spring 2012/10b CP

2012-04-23T17:37:09Z

Crbarile: /* Performance */ added markup for sections

Romanescu, Lebeck, and Sorin make a great point that "The most important feature of a computer is correct execution." Computers are expected to produce correct output consistently. Memory consistency -- the intentional ordering of all reads and writes to memory addresses (Solihin) -- plays a crucial role in guaranteeing that the results of running a program are the results intended by the programmer. Maintaining memory consistency is a problem on all multiprocessor machines (Solihin).

== Models in Use ==
===Strict Consistency===
===Sequential Consistency===
===Weak Consistency===

== Performance ==
===Weak Consistency===
===Sequential Consistency===
===Strict Consistency===

CSC 456 Spring 2012/10b CP

2012-04-23T17:36:38Z

Crbarile: /* Models in Use */ Added markup for sections

Romanescu, Lebeck, and Sorin make a great point that "The most important feature of a computer is correct execution." Computers are expected to produce correct output consistently. Memory consistency -- the intentional ordering of all reads and writes to memory addresses (Solihin) -- plays a crucial role in guaranteeing that the results of running a program are the results intended by the programmer. Maintaining memory consistency is a problem on all multiprocessor machines (Solihin).

== Models in Use ==
===Strict Consistency===
===Sequential Consistency===
===Weak Consistency===

== Performance ==
From best to worst:
Weak Consistency
Sequential Consistency
Strict Consistency

CSC 456 Spring 2012/10b CP

2012-04-17T05:22:12Z

Crbarile: pass 1 at introduction

CSC 456 Spring 2011

2012-04-17T05:16:22Z

Crbarile: Adding our page link

[[Chapter 1: Nick Nicholls, Albert Chu]] 
[[Chapter 4a: Brandon Chisholm, Chris Barile]] 
[[Chapter 6: Joshua Mohundro, Patrick Wong]] 
[[Chapter 6: Allison Hamann, Chris Barile]] 
[[CSC 456 Spring 2012/ch1 BC]] 
[[CSC 456 Spring 2012/ch7 MN]] 
[[CSC 456 Spring 2012/ch7 AA]] 
[[CSC 456 Spring 2012/ch4b]] 
[[CSC 456 Spring 2012/10a AJ]] 
[[CSC 456 Spring 2012/10b CP]] 
[[CSC 456 Spring 2012/11b AB]] 
[[CSC 456 Spring 2012/11a NC]]

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-26T17:21:37Z

Crbarile: /* Polyhedral Transformation */ added references

Automatic Parallelism is the process of automatically converting sequential code into code that will make use of multiple processors. One main reason for implementing automatic parallelism is to save time and energy compared to converting the code manually.<ref name="wiki" /> There are several techniques that have been created for parallelizing code, but each has limitations.

== Techniques ==
===Profile-Driven Parallelism===
This technique involves running the program while recording each memory access in detail. The memory accesses are then looked at to determine what code can be parallelized. This technique is simple, but does not cover all the possible input combinations. These may lead to false positives in which code segments can be labelled as parallelizeable when they actually aren't.<ref name="chia" />
===Polyhedral Transformation===
Polyhedral transformation involves representing loop iterations from the source code as lattice points in something called a polytope. This polytope is then transformed into a more optimized form. This approach is limited when pointers are found inside loops. The following pictures represent a polytope before and after the transformation.<ref name="chia" />
[[File:polytope_model.png|thumb|center|200px|Polytope model, unskewed<ref name="polytope"/>]]
[[File:polytope_model_skewed.png|thumb|center|200px|Polytope model, skewed<ref name="polytope"/>]]

===Automatic Program Exploration===
Also known as "concolic execution", "mixed concrete and symbolic execution", or "symbolic execution", automatic program exploration is originally a bug finding technique that provides full coverage of the program. The first step in this approach is to symbolically represent the inputs to the program. Then, each statement that has a symbolic variable is executed by symbolic manipulation. If a branch condition is found with a symbolic variable, then both paths are conceptually taken. The last step is using the path constraints to find the concrete values that allow the program to go down both paths. This is done until there are no more possible inputs. <ref name="chia" />

===Scalar and Array Analysis===
Scalar and Array Analysis are actually two different forms of analysis that are often used together. Scalar Analysis checks for dependencies between scalar variables in code. A dependency can be defined as "when a memory location written on one iteration of a loop is accessed (read or write) on a different iteration."<ref name="dipa" />

Array Analysis is then used on code that could not be parallelized using Scalar Analysis. Array Analysis looks for arrays that can be privatized.<ref name="dipa" /> Privatization means to allow each thread its own private copy of the array in question, in whole or in part. This is only possible if there are no dependencies in the array.<ref name="dipa" />

===Commutativity Analysis===
One problem in parallelizing code is that synchronization may be required in some programs to prevent errors in computation. Commutativity Analysis is used to determine which operations can be performed out of order without affecting the results of the code. It is based on the mathematical concept of commutativity, where if the result of running two operations is the same, regardless of which order they are performed in.<ref name="dipa" />

===Low Level Virtual Machine===
LLVM works by taking C/C++ code and compiling it into LLVM IR bytecode. Optimizations are done at the IR level and then a code generator brings it back into native code to be executed.

== Limitations ==
One of the major limitations of automatic parallelization is that a computer lacks the insight into the overall intention of a program that a human would have. The programmer understands what the program must do, and can use that to determine if there are alternate approaches or algorithms for parallelizing the code. Even when parallelizing manually, a programmer may not have enough insight into parallel programming, and will need the assistance of an expert to improve code performance.<ref name="ncsa" />

== References ==
<references>
<ref name="chia">http://www.eecs.berkeley.edu/%7Echiayuan/cs262a/cs262a_parallel.pdf</ref>
<ref name="dipa">http://www.csc.villanova.edu/%7Etway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>
<ref name="wiki">http://en.wikipedia.org/wiki/Automatic_parallelization</ref>
<ref name="ncsa">http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization</ref>
<ref name="polytope">http://en.wikipedia.org/wiki/Polytope_model</ref>
</references>

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-26T17:20:20Z

Crbarile: /* References */ added polytope ref

Automatic Parallelism is the process of automatically converting sequential code into code that will make use of multiple processors. One main reason for implementing automatic parallelism is to save time and energy compared to converting the code manually.<ref name="wiki" /> There are several techniques that have been created for parallelizing code, but each has limitations.

== Techniques ==
===Profile-Driven Parallelism===
This technique involves running the program while recording each memory access in detail. The memory accesses are then looked at to determine what code can be parallelized. This technique is simple, but does not cover all the possible input combinations. These may lead to false positives in which code segments can be labelled as parallelizeable when they actually aren't.<ref name="chia" />
===Polyhedral Transformation===
Polyhedral transformation involves representing loop iterations from the source code as lattice points in something called a polytope. This polytope is then transformed into a more optimized form. This approach is limited when pointers are found inside loops. The following pictures represent a polytope before and after the transformation.<ref name="chia" />
[[File:polytope_model.png|thumb|center|200px|Polytope model, unskewed]]
[[File:polytope_model_skewed.png|thumb|center|200px|Polytope model, skewed]]

===Automatic Program Exploration===
Also known as "concolic execution", "mixed concrete and symbolic execution", or "symbolic execution", automatic program exploration is originally a bug finding technique that provides full coverage of the program. The first step in this approach is to symbolically represent the inputs to the program. Then, each statement that has a symbolic variable is executed by symbolic manipulation. If a branch condition is found with a symbolic variable, then both paths are conceptually taken. The last step is using the path constraints to find the concrete values that allow the program to go down both paths. This is done until there are no more possible inputs. <ref name="chia" />

===Scalar and Array Analysis===
Scalar and Array Analysis are actually two different forms of analysis that are often used together. Scalar Analysis checks for dependencies between scalar variables in code. A dependency can be defined as "when a memory location written on one iteration of a loop is accessed (read or write) on a different iteration."<ref name="dipa" />

Array Analysis is then used on code that could not be parallelized using Scalar Analysis. Array Analysis looks for arrays that can be privatized.<ref name="dipa" /> Privatization means to allow each thread its own private copy of the array in question, in whole or in part. This is only possible if there are no dependencies in the array.<ref name="dipa" />

===Commutativity Analysis===
One problem in parallelizing code is that synchronization may be required in some programs to prevent errors in computation. Commutativity Analysis is used to determine which operations can be performed out of order without affecting the results of the code. It is based on the mathematical concept of commutativity, where if the result of running two operations is the same, regardless of which order they are performed in.<ref name="dipa" />

===Low Level Virtual Machine===
LLVM works by taking C/C++ code and compiling it into LLVM IR bytecode. Optimizations are done at the IR level and then a code generator brings it back into native code to be executed.

== Limitations ==
One of the major limitations of automatic parallelization is that a computer lacks the insight into the overall intention of a program that a human would have. The programmer understands what the program must do, and can use that to determine if there are alternate approaches or algorithms for parallelizing the code. Even when parallelizing manually, a programmer may not have enough insight into parallel programming, and will need the assistance of an expert to improve code performance.<ref name="ncsa" />

== References ==
<references>
<ref name="chia">http://www.eecs.berkeley.edu/%7Echiayuan/cs262a/cs262a_parallel.pdf</ref>
<ref name="dipa">http://www.csc.villanova.edu/%7Etway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>
<ref name="wiki">http://en.wikipedia.org/wiki/Automatic_parallelization</ref>
<ref name="ncsa">http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization</ref>
<ref name="polytope">http://en.wikipedia.org/wiki/Polytope_model</ref>
</references>

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-26T17:09:23Z

Crbarile: /* Automatic Program Exploration */ Fixed spelling error.

Automatic Parallelism is the process of automatically converting sequential code into code that will make use of multiple processors. One main reason for implementing automatic parallelism is to save time and energy compared to converting the code manually.<ref name="wiki" /> There are several techniques that have been created for parallelizing code, but each has limitations.

== Techniques ==
===Profile-Driven Parallelism===
This technique involves running the program while recording each memory access in detail. The memory accesses are then looked at to determine what code can be parallelized. This technique is simple, but does not cover all the possible input combinations. These may lead to false positives in which code segments can be labelled as parallelizeable when they actually aren't.<ref name="chia" />
===Polyhedral Transformation===
Polyhedral transformation involves representing loop iterations from the source code as lattice points in something called a polytope. This polytope is then transformed into a more optimized form. This approach is limited when pointers are found inside loops. The following pictures represent a polytope before and after the transformation.<ref name="chia" />
[[File:polytope_model.png|thumb|center|200px|Polytope model, unskewed]]
[[File:polytope_model_skewed.png|thumb|center|200px|Polytope model, skewed]]

===Automatic Program Exploration===
Also known as "concolic execution", "mixed concrete and symbolic execution", or "symbolic execution", automatic program exploration is originally a bug finding technique that provides full coverage of the program. The first step in this approach is to symbolically represent the inputs to the program. Then, each statement that has a symbolic variable is executed by symbolic manipulation. If a branch condition is found with a symbolic variable, then both paths are conceptually taken. The last step is using the path constraints to find the concrete values that allow the program to go down both paths. This is done until there are no more possible inputs. <ref name="chia" />

===Scalar and Array Analysis===
Scalar and Array Analysis are actually two different forms of analysis that are often used together. Scalar Analysis checks for dependencies between scalar variables in code. A dependency can be defined as "when a memory location written on one iteration of a loop is accessed (read or write) on a different iteration."<ref name="dipa" />

Array Analysis is then used on code that could not be parallelized using Scalar Analysis. Array Analysis looks for arrays that can be privatized.<ref name="dipa" /> Privatization means to allow each thread its own private copy of the array in question, in whole or in part. This is only possible if there are no dependencies in the array.<ref name="dipa" />

===Commutativity Analysis===
One problem in parallelizing code is that synchronization may be required in some programs to prevent errors in computation. Commutativity Analysis is used to determine which operations can be performed out of order without affecting the results of the code. It is based on the mathematical concept of commutativity, where if the result of running two operations is the same, regardless of which order they are performed in.<ref name="dipa" />

===Low Level Virtual Machine===
LLVM works by taking C/C++ code and compiling it into LLVM IR bytecode. Optimizations are done at the IR level and then a code generator brings it back into native code to be executed.

== Limitations ==
One of the major limitations of automatic parallelization is that a computer lacks the insight into the overall intention of a program that a human would have. The programmer understands what the program must do, and can use that to determine if there are alternate approaches or algorithms for parallelizing the code. Even when parallelizing manually, a programmer may not have enough insight into parallel programming, and will need the assistance of an expert to improve code performance.<ref name="ncsa" />

== References ==
<references>
<ref name="chia">http://www.eecs.berkeley.edu/%7Echiayuan/cs262a/cs262a_parallel.pdf</ref>
<ref name="dipa">http://www.csc.villanova.edu/%7Etway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>
<ref name="wiki">http://en.wikipedia.org/wiki/Automatic_parallelization</ref>
<ref name="ncsa">http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization</ref>
</references>

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-22T06:45:48Z

Crbarile: /* Scalar and Array Analysis */ Added section on Scalar and Array analysis.

Automatic Parallelism is the process of automatically converting sequential code into code that will make use of multiple processors. One main reason for implementing automatic parallelism is to save time and energy compared to converting the code manually.<ref name="wiki" /> There are several techniques that have been created for parallelizing code, but each has limitations.

== Techniques ==
===Profile-Driven Parallelism===
This technique involves running the program while recording each memory access in detail. The memory accesses are then looked at to determine what code can be parallelized. This technique is simple, but does not cover all the possible input combinations. These may lead to false positives in which code segments can be labelled as parallelizeable when they actually aren't.<ref name="chia" />
===Polyhedral Transformation===
Polyhedral transformation involves representing loop iterations from the source code as lattice points in something called a polytope. This polytope is then transformed into a more optimized form. This approach is limited when pointers are found inside loops. The following pictures represent a polytope before and after the transformation.<ref name="chia" />
[[File:polytope_model.png|thumb|center|200px|Polytope model, unskewed]]
[[File:polytope_model_skewed.png|thumb|center|200px|Polytope model, skewed]]

===Automatic Program Exploration===
Also known as "concolic execution", "mixed concrete and symbolic execution", or "symbolic execution", automatic program exploration is originally a bug finding technique that provides full coverage of the program. The firs0 tstep in this approach is to symbolically represent the inputs to the program. Then, each statement that has a symbolic variable is executed by symbolic manipulation. If a branch condition is found with a symbolic variable, then both paths are conceptually taken. The last step is using the path constraints to find the concrete values that allow the program to go down both paths. This is done until there are no more possible inputs. <ref name="chia" />
===Scalar and Array Analysis===
Scalar and Array Analysis are actually two different forms of analysis that are often used together. Scalar Analysis checks for dependencies between scalar variables in code. A dependency can be defined as "when a memory location written on one iteration of a loop is accessed (read or write) on a different iteration."<ref name="dipa" />

Array Analysis is then used on code that could not be parallelized using Scalar Analysis. Array Analysis looks for arrays that can be privatized.<ref name="dipa" /> Privatization means to allow each thread its own private copy of the array in question, in whole or in part. This is only possible if there are no dependencies in the array.<ref name="dipa" />

===Commutativity Analysis===
One problem in parallelizing code is that synchronization may be required in some programs to prevent errors in computation. Commutativity Analysis is used to determine which operations can be performed out of order without affecting the results of the code. It is based on the mathematical concept of commutativity, where if the result of running two operations is the same, regardless of which order they are performed in.<ref name="dipa" />

===Low Level Virtual Machine===
LLVM works by taking C/C++ code and compiling it into LLVM IR bytecode. Optimizations are done at the IR level and then a code generator brings it back into native code to be executed.

== Limitations ==
One of the major limitations of automatic parallelization is that a computer lacks the insight into the overall intention of a program that a human would have. The programmer understands what the program must do, and can use that to determine if there are alternate approaches or algorithms for parallelizing the code. Even when parallelizing manually, a programmer may not have enough insight into parallel programming, and will need the assistance of an expert to improve code performance.<ref name="ncsa" />

== References ==
<references>
<ref name="chia">http://www.eecs.berkeley.edu/%7Echiayuan/cs262a/cs262a_parallel.pdf</ref>
<ref name="dipa">http://www.csc.villanova.edu/%7Etway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>
<ref name="wiki">http://en.wikipedia.org/wiki/Automatic_parallelization</ref>
<ref name="ncsa">http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization</ref>
</references>

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-22T06:19:49Z

Crbarile: /* Commutativity Analysis */ Added section on commutativity analysis.

Automatic Parallelism is the process of automatically converting sequential code into code that will make use of multiple processors. One main reason for implementing automatic parallelism is to save time and energy compared to converting the code manually.<ref name="wiki" /> There are several techniques that have been created for parallelizing code, but each has limitations.

== Techniques ==
===Profile-Driven Parallelism===
This technique involves running the program while recording each memory access in detail. The memory accesses are then looked at to determine what code can be parallelized. This technique is simple, but does not cover all the possible input combinations. These may lead to false positives in which code segments can be labelled as parallelizeable when they actually aren't.<ref name="chia" />
===Polyhedral Transformation===
Polyhedral transformation involves representing loop iterations from the source code as lattice points in something called a polytope. This polytope is then transformed into a more optimized form. This approach is limited when pointers are found inside loops. The following pictures represent a polytope before and after the transformation.<ref name="chia" />
[[File:polytope_model.png|thumb|center|200px|Polytope model, unskewed]]
[[File:polytope_model_skewed.png|thumb|center|200px|Polytope model, skewed]]

===Automatic Program Exploration===
Also known as "concolic execution", "mixed concrete and symbolic execution", or "symbolic execution", automatic program exploration is originally a bug finding technique that provides full coverage of the program. The firs0 tstep in this approach is to symbolically represent the inputs to the program. Then, each statement that has a symbolic variable is executed by symbolic manipulation. If a branch condition is found with a symbolic variable, then both paths are conceptually taken. The last step is using the path constraints to find the concrete values that allow the program to go down both paths. This is done until there are no more possible inputs. <ref name="chia" />
===Scalar and Array Analysis===
===Commutativity Analysis===
One problem in parallelizing code is that synchronization may be required in some programs to prevent errors in computation. Commutativity Analysis is used to determine which operations can be performed out of order without affecting the results of the code. It is based on the mathematical concept of commutativity, where if the result of running two operations is the same, regardless of which order they are performed in.<ref name="dipa" />

===Low Level Virtual Machine===
LLVM works by taking C/C++ code and compiling it into LLVM IR bytecode. Optimizations are done at the IR level and then a code generator brings it back into native code to be executed.

== Limitations ==
One of the major limitations of automatic parallelization is that a computer lacks the insight into the overall intention of a program that a human would have. The programmer understands what the program must do, and can use that to determine if there are alternate approaches or algorithms for parallelizing the code. Even when parallelizing manually, a programmer may not have enough insight into parallel programming, and will need the assistance of an expert to improve code performance.<ref name="ncsa" />

== References ==
<references>
<ref name="chia">http://www.eecs.berkeley.edu/%7Echiayuan/cs262a/cs262a_parallel.pdf</ref>
<ref name="dipa">http://www.csc.villanova.edu/%7Etway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>
<ref name="wiki">http://en.wikipedia.org/wiki/Automatic_parallelization</ref>
<ref name="ncsa">http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization</ref>
</references>

File:Polytope model skewed.png

2012-03-19T18:06:04Z

Crbarile:

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T18:05:53Z

Crbarile: /* Polyhedral Transformation */ add skewed img

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T18:01:02Z

Crbarile: /* Polyhedral Transformation */ resized polytope image

File:Polytope model.png

2012-03-19T17:58:03Z

Crbarile:

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T17:57:43Z

Crbarile: add polytope image

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T17:49:44Z

Crbarile: removed notes section

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T17:48:52Z

Crbarile: added reference for ncsa blog and fixed ref tag in limitations.

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T17:47:41Z

Crbarile: /* Limitations */ Started limitations section

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T17:34:07Z

Crbarile: Added wiki ref for introduction

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-19T17:31:56Z

Crbarile: Added Introduction

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-14T17:46:01Z

Crbarile: /* References */ Added wiki page to reflist

== Techniques ==

===Profile-Driven Parallelism===
===Polyhedral Transformation===
===Automatic Program Exploration===
===Scalar and Array Analysis===
===Commutativity Analysis===
===Low Level Virtual Machine===

== Limitations ==

== Notes ==
{{reflist}}

== References ==
<references>
<ref name="chia">http://www.eecs.berkeley.edu/%7Echiayuan/cs262a/cs262a_parallel.pdf</ref>
<ref name="dipa">http://www.csc.villanova.edu/%7Etway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>
<ref name="wiki">http://en.wikipedia.org/wiki/Automatic_parallelization</ref>
</references>

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-14T17:45:08Z

Crbarile: /* References */ added dipasquale and yaun cho papers to reflist

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-14T17:39:46Z

Crbarile: /* References */ add sample reference

Chapter 4a: Brandon Chisholm, Chris Barile

2012-03-14T17:38:05Z

Crbarile: Added Page structure

CSC 456 Spring 2011

2012-03-14T17:32:31Z

Crbarile: Added Link to our page for chapter 4a

Chapter 6: Allison Hamann, Chris Barile

2012-02-22T05:51:49Z

Crbarile: /* Organization */ Added image of cache to section

==Victim Cache==
Victim caches were first proposed by Norman P. Jouppi in 1990. Victim caching implements a small, fully-associative cache between direct-mapped L1 memory and the next level of memory. The cache allows lines evicted from the L1 cache a “second-chance” by loading them into the victim cache. Victim caches decrease the overall conflict miss rate (Jouppi).

Direct-mapped caches can especially benefit from victim caching due to their large miss rates. Victim caching allows direct-mapped caches to still be used in order to take advantage of their speed while decreasing the miss rate to an even lower rate than the miss rate found in set-associative caches (Jouppi).

===Handling Misses===
[[File:Jouppi_victimcaching_fig7.jpg|thumb|Jouppi's illustration of victim caching.]]
The proposed victim cache is fully-associative and lies between the L1 memory and the next level of memory. While Jouppi proposed a victim cache with 1 to 5 entries, Naz et al. proposed that the victim caches should be 4 to 16 cache lines.<ref>http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=134547</ref><ref>http://dl.acm.org/citation.cfm?id=1101876</ref> Regardless of the size, when a miss occurs in the L1 cache, the victim cache is then scanned for the wanted line. If a miss occurs in both the L1 and victim cache, the needed line is then pulled from the next level, and the line evicted from the L1 cache is then placed in the victim cache. If a miss occurs in the L1 cache but hits in the victim cache, the two lines are swapped between the two caches. Thus, this eliminates the majority of conflict misses that occur due to temporal locality.

===Implementation===
Victim caching can be found in AMD's Opteron processor series produced specifically for servers and workstations. <ref>http://en.wikipedia.org/wiki/Opteron</ref> Opteron processors use a victim cache that is capable of holding eight victim blocks. <ref> Hennessy, John L., and David A. Patterson. ''Computer Architecture: A Quantitative Approach''. Elsevier, Inc., 2012, p. B-14.</ref>

==Sector Cache==
One early cache organization technique was sector cache. It was used on the IBM 360/85, which was one of the earliest commercial CPUs<ref name="rot99">Rothman, Jeffrey B. and Alan Jay Smith. Sector Cache Design and Performance</ref>. Sector cache allowed for smaller tag sizes, which made searching in cache easier and quicker, without requiring cache lines to be excessively long.<ref name="rot99"/> It was also easier to build with the circuit technology of the time.<ref name="rot99"/> In testing during the design of the IBM 360/85, it was found to run at 81% of the maximum ideal efficiency calculated by IBM's designers.<ref name="lip68">Liptay, J. S. Structural Aspects of the System/360 Model 85, Part II: The Cache.</ref> Sector caches were later replaced by set associative caches, which were found to be more efficient.<ref name="rot99"/>

===Organization===
[[Image:Sectorcache.png|200px|thumb|right|Sectors in cache are made of subsectors. Each subsector has a validity bit indicating whether or not it has been loaded with data.]]The cache is divided into sectors, which correspond to logical sectors on the main storage device.<ref name="lip68"/> When sectors are needed, they are not loaded into cache all at once, but in smaller pieces known as subsectors.<ref name="lip68"/> Subsectors are similar to the lines in a direct mapped cache, and are only loaded into cache when needed. This prevents large amounts of data from having to be transferred for every memory reference. Subsectors have a validity bit that indicates whether they are loaded with data or not.<ref name="lip68"/>

===Miss Handling===
When a process requests data from a disk sector that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored.<ref name="lip68"/> Then the subsector where the data is located is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage.<ref name="lip68"/> When data from other subsectors within a loaded sector are requested, the system loads those subsectors into the cache sector and sets their validity bits.<ref name="lip68"/> Sectors are not removed from the cache until the system needs to reclaim the space to process another request.<ref name="lip68"/>

==References==
<references />

File:Sectorcache.png

2012-02-22T05:44:18Z

Crbarile: Depiction of sector cache with 3 subsectors. For each subsector, there is a validity bit (V) that tells if the subsector has been loaded with the correct data from disk.

Depiction of sector cache with 3 subsectors. For each subsector, there is a validity bit (V) that tells if the subsector has been loaded with the correct data from disk.

Chapter 6: Allison Hamann, Chris Barile

2012-02-22T05:23:10Z

Crbarile: /* Sector Cache */ Fixed missing text for Liptay reference

==Victim Cache==
Victim caches were first proposed by Norman P. Jouppi in 1990. Victim caching implements a small, fully-associative cache between direct-mapped L1 memory and the next level of memory. The cache allows lines evicted from the L1 cache a “second-chance” by loading them into the victim cache. Victim caches decrease the overall conflict miss rate (Jouppi).

Direct-mapped caches can especially benefit from victim caching due to their large miss rates. Victim caching allows direct-mapped caches to still be used in order to take advantage of their speed while decreasing the miss rate to an even lower rate than the miss rate found in set-associative caches (Jouppi).

===Handling Misses===
[[File:Jouppi_victimcaching_fig7.jpg|thumb|Jouppi's illustration of victim caching.]]
The proposed victim cache is fully-associative and lies between the L1 memory and the next level of memory. While Jouppi proposed a victim cache with 1 to 5 entries, Naz et al. proposed that the victim caches should be 4 to 16 cache lines.<ref>http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=134547</ref><ref>http://dl.acm.org/citation.cfm?id=1101876</ref> Regardless of the size, when a miss occurs in the L1 cache, the victim cache is then scanned for the wanted line. If a miss occurs in both the L1 and victim cache, the needed line is then pulled from the next level, and the line evicted from the L1 cache is then placed in the victim cache. If a miss occurs in the L1 cache but hits in the victim cache, the two lines are swapped between the two caches. Thus, this eliminates the majority of conflict misses that occur due to temporal locality.

===Implementation===
Victim caching can be found in AMD's Opteron processor series produced specifically for servers and workstations. <ref>http://en.wikipedia.org/wiki/Opteron</ref> Opteron processors use a victim cache that is capable of holding eight victim blocks. <ref> Hennessy, John L., and David A. Patterson. ''Computer Architecture: A Quantitative Approach''. Elsevier, Inc., 2012, p. B-14.</ref>

==Sector Cache==
One early cache organization technique was sector cache. It was used on the IBM 360/85, which was one of the earliest commercial CPUs<ref name="rot99">Rothman, Jeffrey B. and Alan Jay Smith. Sector Cache Design and Performance</ref>. Sector cache allowed for smaller tag sizes, which made searching in cache easier and quicker, without requiring cache lines to be excessively long.<ref name="rot99"/> It was also easier to build with the circuit technology of the time.<ref name="rot99"/> In testing during the design of the IBM 360/85, it was found to run at 81% of the maximum ideal efficiency calculated by IBM's designers.<ref name="lip68">Liptay, J. S. Structural Aspects of the System/360 Model 85, Part II: The Cache.</ref> Sector caches were later replaced by set associative caches, which were found to be more efficient.<ref name="rot99"/>

===Organization===
The cache is divided into sectors, which correspond to logical sectors on the main storage device.<ref name="lip68"/> When sectors are needed, they are not loaded into cache all at once, but in smaller pieces known as subsectors.<ref name="lip68"/> Subsectors are similar to the lines in a direct mapped cache, and are only loaded into cache when needed. This prevents large amounts of data from having to be transferred for every memory reference. Subsectors have a validity bit that indicates whether they are loaded with data or not.<ref name="lip68"/>

===Miss Handling===
When a process requests data from a disk sector that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored.<ref name="lip68"/> Then the subsector where the data is located is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage.<ref name="lip68"/> When data from other subsectors within a loaded sector are requested, the system loads those subsectors into the cache sector and sets their validity bits.<ref name="lip68"/> Sectors are not removed from the cache until the system needs to reclaim the space to process another request.<ref name="lip68"/>

==References==
<references />

Chapter 6: Allison Hamann, Chris Barile

2012-02-22T05:21:42Z

Crbarile: /* Sector Cache */ Added references

==Victim Cache==
Victim caches were first proposed by Norman P. Jouppi in 1990. Victim caching implements a small, fully-associative cache between direct-mapped L1 memory and the next level of memory. The cache allows lines evicted from the L1 cache a “second-chance” by loading them into the victim cache. Victim caches decrease the overall conflict miss rate (Jouppi).

Direct-mapped caches can especially benefit from victim caching due to their large miss rates. Victim caching allows direct-mapped caches to still be used in order to take advantage of their speed while decreasing the miss rate to an even lower rate than the miss rate found in set-associative caches (Jouppi).

===Handling Misses===
[[File:Jouppi_victimcaching_fig7.jpg|thumb|Jouppi's illustration of victim caching.]]
The proposed victim cache is fully-associative and lies between the L1 memory and the next level of memory. While Jouppi proposed a victim cache with 1 to 5 entries, Naz et al. proposed that the victim caches should be 4 to 16 cache lines.<ref>http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=134547</ref><ref>http://dl.acm.org/citation.cfm?id=1101876</ref> Regardless of the size, when a miss occurs in the L1 cache, the victim cache is then scanned for the wanted line. If a miss occurs in both the L1 and victim cache, the needed line is then pulled from the next level, and the line evicted from the L1 cache is then placed in the victim cache. If a miss occurs in the L1 cache but hits in the victim cache, the two lines are swapped between the two caches. Thus, this eliminates the majority of conflict misses that occur due to temporal locality.

===Implementation===
Victim caching can be found in AMD's Opteron processor series produced specifically for servers and workstations. <ref>http://en.wikipedia.org/wiki/Opteron</ref> Opteron processors use a victim cache that is capable of holding eight victim blocks. <ref> Hennessy, John L., and David A. Patterson. ''Computer Architecture: A Quantitative Approach''. Elsevier, Inc., 2012, p. B-14.</ref>

==Sector Cache==
One early cache organization technique was sector cache. It was used on the IBM 360/85, which was one of the earliest commercial CPUs<ref name="rot99">Rothman, Jeffrey B. and Alan Jay Smith. Sector Cache Design and Performance</ref>. Sector cache allowed for smaller tag sizes, which made searching in cache easier and quicker, without requiring cache lines to be excessively long.<ref name="rot99"/> It was also easier to build with the circuit technology of the time.<ref name="rot99"/> In testing during the design of the IBM 360/85, it was found to run at 81% of the maximum ideal efficiency calculated by IBM's designers.<ref name="lip68"/>Liptay, J. S. Structural Aspects of the System/360 Model 85, Part II: The Cache.</ref> Sector caches were later replaced by set associative caches, which were found to be more efficient.<ref name="rot99"/>

===Organization===
The cache is divided into sectors, which correspond to logical sectors on the main storage device.<ref name="lip68"/> When sectors are needed, they are not loaded into cache all at once, but in smaller pieces known as subsectors.<ref name="lip68"/> Subsectors are similar to the lines in a direct mapped cache, and are only loaded into cache when needed. This prevents large amounts of data from having to be transferred for every memory reference. Subsectors have a validity bit that indicates whether they are loaded with data or not.<ref name="lip68"/>

===Miss Handling===
When a process requests data from a disk sector that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored.<ref name="lip68"/> Then the subsector where the data is located is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage.<ref name="lip68"/> When data from other subsectors within a loaded sector are requested, the system loads those subsectors into the cache sector and sets their validity bits.<ref name="lip68"/> Sectors are not removed from the cache until the system needs to reclaim the space to process another request.<ref name="lip68"/>

==References==
<references />

Chapter 6: Allison Hamann, Chris Barile

2012-02-22T05:15:16Z

Crbarile: /* Sector Cache */ Added background information on sector cache.

==Victim Cache==
Victim caches were first proposed by Norman P. Jouppi in 1990. Victim caching implements a small, fully-associative cache between direct-mapped L1 memory and the next level of memory. The cache allows lines evicted from the L1 cache a “second-chance” by loading them into the victim cache. Victim caches decrease the overall conflict miss rate (Jouppi).

Direct-mapped caches can especially benefit from victim caching due to their large miss rates. Victim caching allows direct-mapped caches to still be used in order to take advantage of their speed while decreasing the miss rate to an even lower rate than the miss rate found in set-associative caches (Jouppi).

===Handling Misses===
[[File:Jouppi_victimcaching_fig7.jpg|thumb|Jouppi's illustration of victim caching.]]
The proposed victim cache is fully-associative and lies between the L1 memory and the next level of memory. While Jouppi proposed a victim cache with 1 to 5 entries, Naz et al. proposed that the victim caches should be 4 to 16 cache lines.<ref>http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=134547</ref><ref>http://dl.acm.org/citation.cfm?id=1101876</ref> Regardless of the size, when a miss occurs in the L1 cache, the victim cache is then scanned for the wanted line. If a miss occurs in both the L1 and victim cache, the needed line is then pulled from the next level, and the line evicted from the L1 cache is then placed in the victim cache. If a miss occurs in the L1 cache but hits in the victim cache, the two lines are swapped between the two caches. Thus, this eliminates the majority of conflict misses that occur due to temporal locality.

===Implementation===
Victim caching can be found in AMD's Opteron processor series produced specifically for servers and workstations. <ref>http://en.wikipedia.org/wiki/Opteron</ref> Opteron processors use a victim cache that is capable of holding eight victim blocks. <ref> Hennessy, John L., and David A. Patterson. ''Computer Architecture: A Quantitative Approach''. Elsevier, Inc., 2012, p. B-14.</ref>

==Sector Cache==
One early cache organization technique was sector cache. It was used on the IBM 360/85, which was one of the earliest commercial CPUs. Sector cache allowed for smaller tag sizes, which made searching in cache easier and quicker, without requiring cache lines to be excessively long. It was also easier to build with the circuit technology of the time. In testing during the design of the IBM 360/85, it was found to run at 81% of the maximum ideal efficiency calculated by IBM's designers. Sector caches were later replaced by set associative caches, which were found to be more efficient.

===Organization===
The cache is divided into sectors, which correspond to logical sectors on the main storage device. When sectors are needed, they are not loaded into cache all at once, but in smaller pieces known as subsectors. Subsectors are similar to the lines in a direct mapped cache, and are only loaded into cache when needed. This prevents large amounts of data from having to be transferred for every memory reference. Subsectors have a validity bit that indicates whether they are loaded with data or not.

===Miss Handling===
When a process requests data from a disk sector that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored. Then the subsector where the data is located is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage. When data from other subsectors within a loaded sector are requested, the system loads those subsectors into the cache sector and sets their validity bits. Sectors are not removed from the cache until the system needs to reclaim the space to process another request.

==References==
<references />

Chapter 6: Allison Hamann, Chris Barile

2012-02-20T18:16:43Z

Crbarile: /* Sector Cache */ Added sub headers that will have the content expanded on.

Chapter 6: Allison Hamann, Chris Barile

2012-02-20T18:07:13Z

Crbarile: Added References list at the bottom of the page.

=Victim Cache=
Victim caches were first proposed by Norman P. Jouppi in 1990. Victim caching implements a small, fully-associative cache between direct-mapped L1 memory and the next level of memory. The cache allows lines evicted from the L1 cache a “second-chance” by loading them into the victim cache. Victim caches decrease the overall conflict miss rate (Jouppi).

Direct-mapped caches can especially benefit from victim caching due to their large miss rates. Victim caching allows direct-mapped caches to still be used in order to take advantage of their speed while decreasing the miss rate to an even lower rate than the miss rate found in set-associative caches (Jouppi).

==Handling Misses==
The proposed victim cache is fully-associative and lies between the L1 memory and the next level of memory. While Jouppi proposed a victim cache with 1 to 5 entries, Naz et al. proposed that the victim caches should be 4 to 16 cache lines.<ref>http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=134547</ref><ref>http://dl.acm.org/citation.cfm?id=1101876</ref> Regardless of the size, when a miss occurs in the L1 cache, the victim cache is then scanned for the wanted line. If a miss occurs in both the L1 and victim cache, the needed line is then pulled from the next level, and the line evicted from the L1 cache is then placed in the victim cache. If a miss occurs in the L1 cache but hits in the victim cache, the two lines are swapped between the two caches. Thus, this eliminates the majority of conflict misses that occur due to temporal locality.

=Sector Cache=
Sector cache is where the cache is divided into sectors. These sectors correspond to a logical sector on the main storage device. When sectors are needed, they are not loaded into cache all at once, but in smaller pieces known as subsectors. Subsectors are similar to the lines in a direct mapped cache.

When a process requests data from a disk sector that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored. Then the subsector where the data is located is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage. When data from other subsectors within a loaded sector are requested, the system loads those subsectors into the cache sector and sets their validity bits. Sectors are not removed from the cache until the system needs to reclaim the space to process another request.

One reason for this approach is that programs are generally organized in contiguous blocks on disk, . Another is that data is first looked up by sector, and then by subsector, which means that it can be found much quicker, and the hardware to do the simultaneous comparison of tags is less expensive.

==References==
<references />

Chapter 6: Allison Hamann, Chris Barile

2012-02-15T07:03:13Z

Crbarile: /* Sector Cache */ Revising content. Editing for clarity.

=Victim Cache=
Victim caches were first proposed by Norman P. Jouppi in 1990. Victim caching implements a small, fully-associative cache between direct-mapped L1 memory and the next level of memory. The cache allows lines evicted from the L1 cache a “second-chance” by loading them into the victim cache. Victim caches decrease the overall conflict miss rate (Jouppi).

Direct-mapped caches can especially benefit from victim caching due to their large miss rates. Victim caching allows direct-mapped caches to still be used in order to take advantage of their speed while decreasing the miss rate to an even lower rate than the miss rate found in set-associative caches (Jouppi).

==Handling Misses==
The proposed victim cache is fully-associative and lies between the L1 memory and the next level of memory. While Jouppi proposed a victim cache with 1 to 5 entries, Naz et al. proposed that the victim caches should be 4 to 16 cache lines.[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=134547][http://dl.acm.org/citation.cfm?id=1101876] Regardless of the size, when a miss occurs in the L1 cache, the victim cache is then scanned for the wanted line. If a miss occurs in both the L1 and victim cache, the needed line is then pulled from the next level, and the line evicted from the L1 cache is then placed in the victim cache. If a miss occurs in the L1 cache but hits in the victim cache, the two lines are swapped between the two caches. Thus, this eliminates the majority of conflict misses that occur due to temporal locality.

Sector cache is where the cache is divided into sectors. These sectors correspond to a logical sector on the main storage device. When sectors are needed, they are not loaded into cache all at once, but in smaller pieces known as subsectors. Subsectors are similar to the lines in a direct mapped cache.

When a process requests data from a disk sector that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored. Then the subsector where the data is located is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage. When data from other subsectors within a loaded sector are requested, the system loads those subsectors into the cache sector and sets their validity bits. Sectors are not removed from the cache until the system needs to reclaim the space to process another request.

One reason for this approach is that programs are generally organized in contiguous blocks on disk, . Another is that data is first looked up by sector, and then by subsector, which means that it can be found much quicker, and the hardware to do the simultaneous comparison of tags is less expensive.

Chapter 6: Allison Hamann, Chris Barile

2012-02-06T18:53:41Z

Crbarile: /* Sector Cache */ drafting content

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=876437

=Victim Cache=

=Sector Cache=
A. Organziation
1) Sectors
2) Subsectors
3) Validity Bit
B. Load Procedure
1) Sector miss
2) Subsector miss
C. Advantages

Sector cache is where the cache is divided into sectors. These sectors correspond to a logical sector on the main storage device. Sectors are not loaded into the cache all at once, but in smaller pieces known as subsectors, which are similar to the cache lines in direct mapped cache.

When a process requests data from a disk sector that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored. Then a portion of that sector, otherwise known as the subsector, is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage. When data from other subsectors are requested, the system loads those subsectors into the cache sector and sets their validity bits. The sector is not removed from the cache until it is needed for another program.

One reason for this approach is that programs are generally organized in contiguous blocks on disk. Another is that data is first looked up by sector, and then by subsector, which means that it can be found much quicker, and the hardware to do the simultaneous comparison of tags is less expensive.

Chapter 6: Allison Hamann, Chris Barile

2012-02-06T18:39:51Z

Crbarile: Change to Sector Cache, accidentally edited whole page

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=876437

=Victim Cache=

=Sector Cache=
A. Organziation
1) Sectors
2) Subsectors
3) Validity Bit
B. Load Procedure
1) Sector miss
2) Subsector miss
C. Advantages

Sector Caches are organized into sectors, which correspond to sectors of the main storage. Sectors are then organized into subsectors, which are similar to cache lines. Each subsector has a "validity bit" which tells whether or not that subsector has been loaded into cache from the main storage.

When a process requests data that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored. Then a portion of that sector, known as the subsector, is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage.

One reason for this approach is that programs are generally organized in contiguous blocks on disk. Another is that data is first looked up by sector, and then by subsector, which means that it can be found much quicker, and the hardware to do the simultaneous comparison of tags is less expensive.

Chapter 6: Allison Hamann, Chris Barile

2012-02-06T18:27:45Z

Crbarile: /* Sector Cache */ Adding paragraph about cache loading

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=876437

=Victim Cache=

=Sector Cache=
A. Organziation
1) Sectors
2) Subsectors
3) Validity Bit
B. Load Procedure
1) Sector miss
2) Subsector miss
C. Advantages

Sector Caches are organized into sectors and subsectors. A sector is a collection of smaller subsectors. Subsectors are similar to lines in a direct-mapped cache. Each subsector has a "validity bit" which tells whether or not that subsector has been loaded into cache from the main storage.

When a process requests data that is not in the cache, a cache sector is assigned to the sector on the main storage device where the requested data is stored. Then a portion of that sector, known as the subsector, is loaded into the cache. The subsector's validity bit is then set to reflect that it has been loaded from the main storage. When a process requests data from the loaded sector that is not already in the cache, the subsector it is in becomes loaded into memory.

Chapter 6: Allison Hamann, Chris Barile

2012-01-30T19:08:20Z

Crbarile: /* Sector Cache */ Started drafting content. Need to add reference section to page and possibly archive papers.

Chapter 6: Allison Hamann, Chris Barile

2012-01-30T19:00:01Z

Crbarile: /*Sector Cache*/ Starting to outline content for this page. Will replace with content.

Chapter 6: Allison Hamann, Chris Barile

2012-01-23T18:54:57Z

Crbarile: Adding reference to ieee paper

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=876437

CSC 456 Spring 2011

2012-01-23T18:48:00Z

Crbarile: Added missing line break

[[Chapter 6: Joshua Mohundro, Patrick Wong]] 
[[Chapter 6: Allison Hamann, Chris Barile]]

CSC 456 Spring 2011

2012-01-23T18:47:23Z

Crbarile: Adding Page for Chapter 6

[[Chapter 6: Joshua Mohundro, Patrick Wong]]
[[Chapter 6: Allison Hamann, Chris Barile]]