Expertiza_Wiki - User contributions [en]

CSC 456 Spring 2012/10b CP

2012-04-23T17:03:29Z

Pzwong:

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/ch4b

2012-03-26T18:09:07Z

Pzwong: the source is copyright me, pzwong, 2012

==Gustafson's Law==

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times.<ref name="karp" /> "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold <ref name="published speedup" />, and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program.<ref name="IBM" /> He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). Gustafson referred to this as [http://en.wikipedia.org/wiki/Gustafson%27s_law scaled speedup]. This provided the basis of what became known as "Gustafson's Law".

===Derivation from Amdahl's Law===
Amdahl's law assumes that the problem size is constant. A different expression, Gustafson's law, can be derived if the total time used to execute a workload is kept constant instead.<ref name="derivation" /> This source contains the derivation.

==Superlinear Speedup==

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as [http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup superlinear speedup]. This controversy is the product of differences in interpretations of the basis of what constitutes speedup, making this an ideological disagreement.<ref name = "controversy" />

Superlinear speedup can most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.<ref name="SS" />

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

===Lack of a Serial Equivalent===
However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm. While it is possible for one processor to have a cache size large enough to encompass a problem's working set, the usage of cache manipulation in achieving superlinear speedup relies on parallel execution, which a single processor is incapable of doing. Also, the monetary cost of such a cache would be so high as to make this implementation practically unfeasible.

Additionally, a serial algorithm could be constructed that would reduce the total problem size, but it would be much slower than its parallel counterpart. E.g., you could take this serial algorithm and parallelize it and both instances would do the same amount of work (less than the original problem size), but the parallel version would still do it much faster, achieving the superlinear speedup.

==References==
<references>
<ref name="karp">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false</ref>
<ref name="IBM">http://techresearch.intel.com/ResearcherDetails.aspx?Id=182</ref>
<ref name="published speedup">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D</ref>
<ref name="SS">http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup</ref>
<ref name="derivation">http://expertiza.csc.ncsu.edu/wiki/images/5/5f/Ohai.png</ref>
<ref name = "controversy">http://www.sciencedirect.com/science/article/pii/0167819187900536</ref>
</references>

CSC 456 Spring 2012/ch4b

2012-03-26T18:07:16Z

Pzwong: /* Derivation from Amdahl's Law */

==Gustafson's Law==

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times.<ref name="karp" /> "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold <ref name="published speedup" />, and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program.<ref name="IBM" /> He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). Gustafson referred to this as [http://en.wikipedia.org/wiki/Gustafson%27s_law scaled speedup]. This provided the basis of what became known as "Gustafson's Law".

===Derivation from Amdahl's Law===
Amdahl's law assumes that the problem size is constant. A different expression, Gustafson's law, can be derived if the total time used to execute a workload is kept constant instead.<ref name="derivation" />

==Superlinear Speedup==

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as [http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup superlinear speedup]. This controversy is the product of differences in interpretations of the basis of what constitutes speedup, making this an ideological disagreement.<ref name = "controversy" />

Superlinear speedup can most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.<ref name="SS" />

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

===Lack of a Serial Equivalent===
However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm. While it is possible for one processor to have a cache size large enough to encompass a problem's working set, the usage of cache manipulation in achieving superlinear speedup relies on parallel execution, which a single processor is incapable of doing. Also, the monetary cost of such a cache would be so high as to make this implementation practically unfeasible.

Additionally, a serial algorithm could be constructed that would reduce the total problem size, but it would be much slower than its parallel counterpart. E.g., you could take this serial algorithm and parallelize it and both instances would do the same amount of work (less than the original problem size), but the parallel version would still do it much faster, achieving the superlinear speedup.

==References==
<references>
<ref name="karp">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false</ref>
<ref name="IBM">http://techresearch.intel.com/ResearcherDetails.aspx?Id=182</ref>
<ref name="published speedup">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D</ref>
<ref name="SS">http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup</ref>
<ref name="derivation">http://expertiza.csc.ncsu.edu/wiki/images/5/5f/Ohai.png</ref>
<ref name = "controversy">http://www.sciencedirect.com/science/article/pii/0167819187900536</ref>
</references>

CSC 456 Spring 2012/ch4b

2012-03-26T18:01:52Z

Pzwong: /* Gustafson's Law */

==Gustafson's Law==

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times.<ref name="karp" /> "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold <ref name="published speedup" />, and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program.<ref name="IBM" /> He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). Gustafson referred to this as [http://en.wikipedia.org/wiki/Gustafson%27s_law scaled speedup]. This provided the basis of what became known as "Gustafson's Law".

===Derivation from Amdahl's Law===
It is possible to derive Gustafson's Law from Amdahl's Law, by not holding to the assumption that Amdahl's law makes (that problem size is constant).<ref name="derivation" />

==Superlinear Speedup==

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as [http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup superlinear speedup]. This controversy is the product of differences in interpretations of the basis of what constitutes speedup, making this an ideological disagreement.<ref name = "controversy" />

Superlinear speedup can most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.<ref name="SS" />

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

===Lack of a Serial Equivalent===
However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm. While it is possible for one processor to have a cache size large enough to encompass a problem's working set, the usage of cache manipulation in achieving superlinear speedup relies on parallel execution, which a single processor is incapable of doing. Also, the monetary cost of such a cache would be so high as to make this implementation practically unfeasible.

Additionally, a serial algorithm could be constructed that would reduce the total problem size, but it would be much slower than its parallel counterpart. E.g., you could take this serial algorithm and parallelize it and both instances would do the same amount of work (less than the original problem size), but the parallel version would still do it much faster, achieving the superlinear speedup.

==References==
<references>
<ref name="karp">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false</ref>
<ref name="IBM">http://techresearch.intel.com/ResearcherDetails.aspx?Id=182</ref>
<ref name="published speedup">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D</ref>
<ref name="SS">http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup</ref>
<ref name="derivation">http://expertiza.csc.ncsu.edu/wiki/images/5/5f/Ohai.png</ref>
<ref name = "controversy">http://www.sciencedirect.com/science/article/pii/0167819187900536</ref>
</references>

CSC 456 Spring 2012/ch4b

2012-03-26T17:59:14Z

Pzwong:

==Gustafson's Law==

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times.<ref name="karp" /> "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [<ref name="published speedup" />, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program.<ref name="IBM" /> He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). Gustafson referred to this as [http://en.wikipedia.org/wiki/Gustafson%27s_law scaled speedup]. This provided the basis of what became known as "Gustafson's Law".

===Derivation from Amdahl's Law===
It is possible to derive Gustafson's Law from Amdahl's Law, by not holding to the assumption that Amdahl's law makes (that problem size is constant).<ref name="derivation" />

==Superlinear Speedup==

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as [http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup superlinear speedup]. This controversy is the product of differences in interpretations of the basis of what constitutes speedup, making this an ideological disagreement.<ref name = "controversy" />

Superlinear speedup can most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.<ref name="SS" />

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

===Lack of a Serial Equivalent===
However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm. While it is possible for one processor to have a cache size large enough to encompass a problem's working set, the usage of cache manipulation in achieving superlinear speedup relies on parallel execution, which a single processor is incapable of doing. Also, the monetary cost of such a cache would be so high as to make this implementation practically unfeasible.

Additionally, a serial algorithm could be constructed that would reduce the total problem size, but it would be much slower than its parallel counterpart. E.g., you could take this serial algorithm and parallelize it and both instances would do the same amount of work (less than the original problem size), but the parallel version would still do it much faster, achieving the superlinear speedup.

==References==
<references>
<ref name="karp">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false</ref>
<ref name="IBM">http://techresearch.intel.com/ResearcherDetails.aspx?Id=182</ref>
<ref name="published speedup">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D</ref>
<ref name="SS">http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup</ref>
<ref name="derivation">http://expertiza.csc.ncsu.edu/wiki/images/5/5f/Ohai.png</ref>
<ref name = "controversy">http://www.sciencedirect.com/science/article/pii/0167819187900536</ref>
</references>

CSC 456 Spring 2012/ch4b

2012-03-26T17:55:24Z

Pzwong:

==Gustafson's Law==

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times.<ref name="karp" /> "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [<ref name="published speedup" />, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program.<ref name="IBM" /> He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). Gustafson referred to this as [http://en.wikipedia.org/wiki/Gustafson%27s_law scaled speedup]. This provided the basis of what became known as "Gustafson's Law".

===Derivation from Amdahl's Law===
It is possible to derive Gustafson's Law from Amdahl's Law, by not holding to the assumption that Amdahl's law makes (that problem size is constant).<ref name="derivation" />

==Superlinear Speedup==

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial<ref name = "controversy" /> topic known as [http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup superlinear speedup].

Superlinear speedup can most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.<ref name="SS" />

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

===Lack of a Serial Equivalent===
However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm. While it is possible for one processor to have a cache size large enough to encompass a problem's working set, the usage of cache manipulation in achieving superlinear speedup relies on parallel execution, which a single processor is incapable of doing. Also, the monetary cost of such a cache would be so high as to make this implementation practically unfeasible.

Additionally, a serial algorithm could be constructed that would reduce the total problem size, but it would be much slower than its parallel counterpart. E.g., you could take this serial algorithm and parallelize it and both instances would do the same amount of work (less than the original problem size), but the parallel version would still do it much faster, achieving the superlinear speedup.

==References==
<references>
<ref name="karp">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false</ref>
<ref name="IBM">http://techresearch.intel.com/ResearcherDetails.aspx?Id=182</ref>
<ref name="published speedup">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D</ref>
<ref name="SS">http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup</ref>
<ref name="derivation">http://expertiza.csc.ncsu.edu/wiki/images/5/5f/Ohai.png</ref>
<ref name = "controversy">http://www.sciencedirect.com/science/article/pii/0167819187900536</ref>
</references>

CSC 456 Spring 2012/ch4b

2012-03-26T17:33:02Z

Pzwong:

==Gustafson's Law==

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times.<ref name="karp" /> "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [<ref name="published speedup" />, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program.<ref name="IBM" /> He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). Gustafson referred to this as [http://en.wikipedia.org/wiki/Gustafson%27s_law scaled speedup]. This provided the basis of what became known as "Gustafson's Law".

===Derivation from Amdahl's Law===
It is possible to derive Gustafson's Law from Amdahl's Law, by not holding to the assumption that Amdahl's law makes (that problem size is constant).<ref name="derivation" />

==Superlinear Speedup==

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as [http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup superlinear speedup].

Superlinear speedup can most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.<ref name="SS" />

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

===Lack of a Serial Equivalent===
However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm. While it is possible for one processor to have a cache size large enough to encompass a problem's working set, the usage of cache manipulation in achieving superlinear speedup relies on parallel execution, which a single processor is incapable of doing. Also, the monetary cost of such a cache would be so high as to make this implementation practically unfeasible.

Additionally, a serial algorithm could be constructed that would reduce the total problem size, but it would be much slower than its parallel counterpart. E.g., you could take this serial algorithm and parallelize it and both instances would do the same amount of work (less than the original problem size), but the parallel version would still do it much faster, achieving the superlinear speedup.

==References==
<references>
<ref name="karp">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false</ref>
<ref name="IBM">http://techresearch.intel.com/ResearcherDetails.aspx?Id=182</ref>
<ref name="published speedup">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D</ref>
<ref name="SS">http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup</ref>
<ref name="derivation">http://expertiza.csc.ncsu.edu/wiki/images/5/5f/Ohai.png</ref></references>

CSC 456 Spring 2012/ch4b

2012-03-22T01:08:20Z

Pzwong: /* Derivation from Amdahl's Law */

==Gustafson's Law==

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times.<ref name="karp" /> "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [<ref name="published speedup" />, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program.<ref name="IBM" /> He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). This provided the basis of what became known as "Gustafson's Law".

===Derivation from Amdahl's Law===
[[File:Ohai.png|left|Derivation of Gustafson Scaled Speedup]]

==Superlinear Speedup==

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as "superlinear speedup".

Superlinear speedup can most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.<ref name="SS" />

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

===Lack of a Serial Equivalent===
However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm. While it is possible for one processor to have a cache size large enough to encompass a problem's working set, the usage of cache manipulation in achieving superlinear speedup relies on parallel execution, which a single processor is incapable of doing. Also, the monetary cost of such a cache would be so high as to make this implementation practically unfeasible.

Additionally, a serial algorithm could be constructed that would reduce the total problem size, but it would be much slower than its parallel counterpart. E.g., you could take this serial algorithm and parallelize it and both instances would do the same amount of work (less than the original problem size), but the parallel version would still do it much faster, achieving the superlinear speedup.

==References==
<references>
<ref name="karp">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false</ref>
<ref name="IBM">http://techresearch.intel.com/ResearcherDetails.aspx?Id=182</ref>
<ref name="published speedup">http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D</ref>
<ref name="SS">http://en.wikipedia.org/wiki/Speedup#Super_linear_speedup</ref>
</references>

File:Ohai.png

2012-03-22T01:07:48Z

Pzwong:

CSC 456 Spring 2012/ch4b

2012-03-19T18:07:20Z

Pzwong:

Gustafson's Law

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times. "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [1, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program. He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). This provided the basis of what became known as "Gustafson's Law".

SOURCE http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false
SOURCE http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

<pre>
Regular speedup(p) = T1 / Tparallel = 1/(s+(1-s)/p) -> Assumes a fixed problem size (T1 = 1)
Gustafson's speedup(p) = T1 / Tparallel = (T1)/(s+(1-s)) = (T1) -> Assumes a fixed execution time (Tparallel = 1)
How to calculate T1?

Examine the work graph:
Tparallel =
[s][1-s ]
[1-s ]
...
[1-s ]
Total execution time: s+(1-s) = 1 = Tparallel
Serial fraction: s = 0.3 (3 of 10 units)

T1 =
[s][1-s ][1-s ] ... [1-s ]
By inspection, the execution time is a single serial portion + p parallel portions.
Total execution time: s (serial) + p*(1-s) (parallel) = 0.3 + p*(1-0.3) = 0.3+0.7p

Gustafson's speedup(p) = s + p*(1-s) / (s+(1-s)) = p + s - p*s
</pre>
Superlinear Speedup

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as "superlinear speedup".

Superlinear speedup most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

However, it is not possible to serialize the parallel algorithm used in achieving superlinear speedup in order to get a better serial algorithm.

Sources: 
[1] http://books.google.com/books? id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D 
[2] http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

CSC 456 Spring 2012/ch4b

2012-03-19T18:03:14Z

Pzwong:

Gustafson's Law

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times. "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [1, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program. He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). This provided the basis of what became known as "Gustafson's Law".

SOURCE http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false
SOURCE http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

<pre>
Regular speedup(p) = T1 / Tparallel = 1/(s+(1-s)/p) -> Assumes a fixed problem size (T1 = 1)
Gustafson's speedup(p) = T1 / Tparallel = (T1)/(s+(1-s)) = (T1) -> Assumes a fixed execution time (Tparallel = 1)
How to calculate T1?

Examine the work graph:
Tparallel =
[s][1-s ]
[1-s ]
...
[1-s ]
Total execution time: s+(1-s) = 1 = Tparallel
Serial fraction: s = 0.3 (3 of 10 units)

T1 =
[s][1-s ][1-s ] ... [1-s ]
By inspection, the execution time is a single serial portion + p parallel portions.
Total execution time: s (serial) + p*(1-s) (parallel) = 0.3 + p*(1-0.3) = 0.3+0.7p

Gustafson's speedup(p) = s + p*(1-s) / (s+(1-s)) = p + s - p*s
</pre>
Superlinear Speedup

If a problem were 100% parallelizable, then under ideal circumstances one would expect the speedup for a 4-processor system running the same problem to be 4. However, there are cases where such a system might achieve a speedup of, say, 4.3, or 5. This seems counter intuitive, and is a controversial topic known as "superlinear speedup".

Superlinear speedup most easily be attained by taking advantage of the combined cache size of all the processors. If the total cache size is greater than the problem's total working set, the problem can be placed inside the cache and executed much more quickly, allowing faster execution while doing the same amount of work.

Another explanation for superlinear speedup is that the parallel execution of the problem does less total work than a uniprocessor system. This can be done by clever usage of algorithms such that the problem size is reduced, resulted in less total work.

Sources: 
[1] http://books.google.com/books? id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D 
[2] http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

CSC 456 Spring 2012/ch4b

2012-03-19T17:43:14Z

Pzwong:

Gustafson's Law

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times. "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [1, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program. He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). This provided the basis of what became known as "Gustafson's Law".

SOURCE http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false
SOURCE http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

<pre>
Regular speedup(p) = T1 / Tparallel = 1/(s+(1-s)/p) -> Assumes a fixed problem size (T1 = 1)
Gustafson's speedup(p) = T1 / Tparallel = (T1)/(s+(1-s)) = (T1) -> Assumes a fixed execution time (Tparallel = 1)
How to calculate T1?

Examine the work graph:
Tparallel =
[s][1-s ]
[1-s ]
...
[1-s ]
Total execution time: s+(1-s) = 1 = Tparallel
Serial fraction: s = 0.3 (3 of 10 units)

T1 =
[s][1-s ][1-s ] ... [1-s ]
By inspection, the execution time is a single serial portion + p parallel portions.
Total execution time: s (serial) + p*(1-s) (parallel) = 0.3 + p*(1-0.3) = 0.3+0.7p

Gustafson's speedup(p) = s + p*(1-s) / (s+(1-s)) = p + s - p*s
</pre>
Superlinear Speedup

Sources: 
[1] http://books.google.com/books? id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D 
[2] http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

CSC 456 Spring 2012/ch4b

2012-03-19T17:42:22Z

Pzwong:

Gustafson's Law

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times. "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold [1, first paragraph, second column, first page], and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program. He noticed a limitation in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases (i.e., big machines do big problems, bigger problems means smaller portions of serial code, which means that there is more room for processors to parallelize). This provided the basis of what became known as "Gustafson's Law".

SOURCE http://books.google.com/books?id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9CKarp+Challenge%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9CKarp%20Challenge%E2%80%9D&f=false
SOURCE http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

Regular speedup(p) = T1 / Tparallel = 1/(s+(1-s)/p) -> Assumes a fixed problem size (T1 = 1)
Gustafson's speedup(p) = T1 / Tparallel = (T1)/(s+(1-s)) = (T1) -> Assumes a fixed execution time (Tparallel = 1)
How to calculate T1?

Examine the work graph:
Tparallel =
[s][1-s ]
[1-s ]
...
[1-s ]
Total execution time: s+(1-s) = 1 = Tparallel
Serial fraction: s = 0.3 (3 of 10 units)

T1 =
[s][1-s ][1-s ] ... [1-s ]
By inspection, the execution time is a single serial portion + p parallel portions.
Total execution time: s (serial) + p*(1-s) (parallel) = 0.3 + p*(1-0.3) = 0.3+0.7p

Gustafson's speedup(p) = s + p*(1-s) / (s+(1-s)) = p + s - p*s

Superlinear Speedup

Sources: 
[1] http://books.google.com/books? id=Hm6LaufVKFEC&pg=PA55&lpg=PA55&dq=%E2%80%9Cpublished+speedups%E2%80%9D&source=bl&ots=uCAOgSzfmR&sig=KpvmL85rJHqoFuBZlXNL_e_thbs&hl=en&sa=X&ei=ZNRgT4HxL4KatweYz5y7BQ&ved=0CFAQ6AEwBw#v=onepage&q=%E2%80%9Cpublished%20speedups%E2%80%9D 
[2] http://techresearch.intel.com/ResearcherDetails.aspx?Id=182

CSC 456 Spring 2012/ch4b

2012-03-19T16:59:54Z

Pzwong: sources

CSC 456 Spring 2012/ch4b

2012-03-19T16:59:15Z

Pzwong: sources

CSC 456 Spring 2012/ch4b

2012-03-19T16:56:53Z

Pzwong:

CSC 456 Spring 2012/ch4b

2012-03-14T18:04:59Z

Pzwong:

CSC 456 Spring 2012/ch4b

2012-03-14T18:00:44Z

Pzwong: Created page with "Gustafson's Law In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times. "Karp's Challenge", as it became known, highlighted ..."

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-21T03:17:09Z

Pzwong: /* Implementations */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared. In the 1990's there was a resurgence of in sectored caches. This is because sector caches have the feature that large numbers of bytes can be tagged using relatively small numbers of tag bits, while still only transferring small blocks when a miss occurs. This suggests the use of sector caches for multilevel cache designs. In such a design, the cache tags can be placed at a higher level (e.g., on the processor chip) and the cache data array can be placed at a lower level (e.g., off-chip).

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png|tumb|100px|980px|This is taken from reference 1]]
Image taken from reference 1.

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses which use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic (ie. run slower) than direct mapped caches; direct mapped caches are faster but less efficient. One solution is to use a more associative cache, giving each line higher associativity, but this is expensive in cache logic. In actual workloads, it was discovered that high associativity is only really needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache. Traditional victim caches are usually between 4 and 16 entries and run a little slower than the parent cache due to the fully associative feature of a victim cache.

[[File:ch6_pzwong.png|tumb|100px|768px|A graphical representation of how a Victim Cache works]]

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small: 8 entries (512 bytes at 64 bytes per line).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache, which was no longer fully associative. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.
[[File:Yarr.png|tumb|100px|800px|A diagram of old and new victim cache structure]]

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-21T03:15:19Z

Pzwong: /* Implementations */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared. In the 1990's there was a resurgence of in sectored caches. This is because sector caches have the feature that large numbers of bytes can be tagged using relatively small numbers of tag bits, while still only transferring small blocks when a miss occurs. This suggests the use of sector caches for multilevel cache designs. In such a design, the cache tags can be placed at a higher level (e.g., on the processor chip) and the cache data array can be placed at a lower level (e.g., off-chip).

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png|tumb|100px|980px|This is taken from reference 1]]
Image taken from reference 1.

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses which use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic (ie. run slower) than direct mapped caches; direct mapped caches are faster but less efficient. One solution is to use a more associative cache, giving each line higher associativity, but this is expensive in cache logic. In actual workloads, it was discovered that high associativity is only really needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache. Traditional victim caches are usually between 4 and 16 entries and run a little slower than the parent cache due to the fully associative feature of a victim cache.

[[File:ch6_pzwong.png|tumb|100px|768px|A graphical representation of how a Victim Cache works]]

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small: 8 entries (512 bytes at 64 bytes per line).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.
[[File:Yarr.png|tumb|100px|800px|A diagram of old and new victim cache structure]]

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

File:Yarr.png

2012-02-21T03:14:38Z

Pzwong:

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-21T03:00:57Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared. In the 1990's there was a resurgence of in sectored caches. This is because sector caches have the feature that large numbers of bytes can be tagged using relatively small numbers of tag bits, while still only transferring small blocks when a miss occurs. This suggests the use of sector caches for multilevel cache designs. In such a design, the cache tags can be placed at a higher level (e.g., on the processor chip) and the cache data array can be placed at a lower level (e.g., off-chip).

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png|tumb|100px|980px|This is taken from reference 1]]
Image taken from reference 1.

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses which use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic (ie. run slower) than direct mapped caches; direct mapped caches are faster but less efficient. One solution is to use a more associative cache, giving each line higher associativity, but this is expensive in cache logic. In actual workloads, it was discovered that high associativity is only really needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache. Traditional victim caches are usually between 4 and 16 entries and run a little slower than the parent cache due to the fully associative feature of a victim cache.

[[File:ch6_pzwong.png|tumb|100px|768px|A graphical representation of how a Victim Cache works]]

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small: 8 entries (512 bytes at 64 bytes per line).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-21T03:00:26Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared. In the 1990's there was a resurgence of in sectored caches. This is because sector caches have the feature that large numbers of bytes can be tagged using relatively small numbers of tag bits, while still only transferring small blocks when a miss occurs. This suggests the use of sector caches for multilevel cache designs. In such a design, the cache tags can be placed at a higher level (e.g., on the processor chip) and the cache data array can be placed at a lower level (e.g., off-chip).

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png|tumb|100px|980px|This is taken from reference 1]]
Image taken from reference 1.

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses which use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic (ie. run slower) than direct mapped caches; direct mapped caches are faster but less efficient. One solution is to use a more associative cache, giving each line higher associativity, but this is expensive in cache logic. In actual workloads, it was discovered that high associativity is only really needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache. Traditional victim caches are usually between 4 and 16 entries and run a little slower than the parent cache due to the fully associative feature of a victim cache.

[[File:ch6_pzwong.png|tumb|100px|980px|A graphical representation of how a Victim Cache works]]

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small: 8 entries (512 bytes at 64 bytes per line).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

File:Ch6 pzwong.png

2012-02-21T02:59:08Z

Pzwong:

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T19:03:21Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared. In the 1990's there was a resurgence of in sectored caches. aches. This is because sector caches have the feature that large numbers of bytes can be tagged using relatively small numbers of tag bits, while still only transferring small blocks when a miss occurs. This suggests the use of sector caches for multilevel cache designs. In such a design, the cache tags can be placed at a higher level (e.g., on the processor chip) and the cache data array can be placed at a lower level (e.g., off-chip).

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png|tumb|100px|980px|This is taken from reference 1]]

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses which use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic (ie. run slower) than direct mapped caches; direct mapped caches are faster but less efficient. One solution is to use a more associative cache, giving each line higher associativity, but this is expensive in cache logic. In actual workloads, it was discovered that high associativity is only really needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache. Traditional victim caches are usually between 4 and 16 entries and run a little slower than the parent cache due to the fully associative feature of a victim cache.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small: 8 entries (512 bytes at 64 bytes per line).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T18:56:12Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png]]

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses which use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic (ie. run slower) than direct mapped caches; direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache. Traditional victim caches are usually between 4 and 16 entries and run a little slower than the parent cache due to the fully associative feature of a victim cache.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small: 8 entries (512 bytes at 64 bytes per line).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T18:51:27Z

Pzwong: /* Implementations */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png]]

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small: 8 entries (512 bytes at 64 bytes per line).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T18:45:16Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png]]

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series. The AMD and Intel implementations will be examined in the next section.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small, usually no more than 16 entries (1024 bytes).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T18:44:44Z

Pzwong: /* Implementations */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png]]

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

===Implementations===
AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small, usually no more than 16 entries (1024 bytes).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T18:44:11Z

Pzwong: /* Implementations */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===
[[File:examples_of_sectored_cache.png]]

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

===Implementations===
Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache as a buffer between levels of cache.

Traditional Victim Caches are implemented in AMD's older architectures, such as the K7 and K8. In K7, the cache was located on a very slow external bus, and the victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache. In K8 and later iterations of K7, the L2 cache was fast because it was integrated on-chip, but transferring data between the L1 and L2 cache was still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core. The victim caches on these CPUs was very small, usually no more than 16 entries (1024 bytes).

With the increasing focus on multiprocessing, AMD used the "victim cache" idea and evolved it into a large "victim cache" capable of serving more than two CPUs. In AMD's K10 architecture, a three-level cache hierarchy was used, with the new victim cache at the third level. A smaller, faster, and more associative L1 and L2 cache was dedicated to each CPU, coupled to a large, slow L3 victim cache. This victim cache was shared between all of the CPUs on the package and was 2-6 MB, an order of magnitude larger than earlier victim caches. The higher associativities of lower level caches reduces the effectiveness of the traditional victim cache. Thus, the evolution of the victim cache to fulfill the demands of multiprocessing is natural.

Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system (the cache line is just re-fetched from the lower level cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T18:19:05Z

Pzwong: /* Implementations */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
===Examples===

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

===Implementations===
Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

However, the motivation behind the victim cache between the architectures could not be more different.

In K7, the cache was located on a very slow external bus. The victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache.

In K8, and later iterations of K7, the L2 cache was integrated on-chip, but transferring data between the L1 and L2 cache is still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core.

K10 adopted a three-level cache hierarchy, using smaller but faster L1 and L2 caches coupled to a large, slow L3 "victim cache". The "victim cache" is 2-6 MB, an order of magnitude larger than most victim cache implementations, which are usually no more than 16 entries (1024 bytes).

With the increasing focus on multiprocessing, the creation of K10's large L3 "victim cache" served to make it possible to design a large and relatively fast cache capable of serving more than two CPUs. Similarly, Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches to improve cache performance for multiple CPUs. Intel's cache hierarchy is inclusive, so no prior Intel CPU has implemented this feature, as there is no good reason to use a victim cache for a inclusive cache on a uniprocessor system. It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-20T18:05:30Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section, sectored caches were all but abandoned due to the inferiority to other designs; this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.
==Examples==

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

===Implementations===
Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

However, the motivation behind the victim cache between the architectures could not be more different.

In K7, the cache was located on a very slow external bus. The victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache.

In K8, and later iterations of K7, the L2 cache was integrated on-chip, but transferring data between the L1 and L2 cache is still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core.

K10 adopted a three-level cache hierarchy, using smaller but faster L1 and L2 caches coupled to a large, slow L3 "victim cache". The "victim cache" is 2-6 MB, an order of magnitude larger than most victim cache implementations, which are usually no more than 16 entries (1024 bytes).

With the increasing focus on multiprocessing, the creation of K10's large L3 "victim cache" served to make it possible to design a large and relatively fast cache capable of serving more than two CPUs. Similarly, Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches, although the cache hierarchy is inclusive (for which there is no good reason to use a victim cache if only considering uniprocessing). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-06T19:07:03Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section sectored caches were all but abandoned due to the inferiority to other designs, this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

However, the motivation behind the victim cache between the architectures could not be more different.

In K7, the cache was located on a very slow external bus. The victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache.

In K8, and later iterations of K7, the L2 cache was integrated on-chip, but transferring data between the L1 and L2 cache is still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core.

K10 adopted a three-level cache hierarchy, using smaller but faster L1 and L2 caches coupled to a large, slow L3 "victim cache". The "victim cache" is 2-6 MB, an order of magnitude larger than most victim cache implementations, which are usually no more than 16 entries (1024 bytes).

With the increasing focus on multiprocessing, the creation of K10's large L3 "victim cache" served to make it possible to design a large and relatively fast cache capable of serving more than two CPUs. Similarly, Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches, although the cache hierarchy is inclusive (for which there is no good reason to use a victim cache). It marks the first time that an Intel chip has implemented a victim cache.

==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf 
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-02-06T19:05:10Z

Pzwong: /* Victim Cache */

== Sectored Cache ==

===History===
One of the first commercially available PCs that used a cache, IBM 360/85, used a sectored cache. The primary reason for a sectored cache is that during the time of the IBM 360/85 it was easier to build than current non-sectored designs. However, the sectored design proved to be much less efficient then the non-sectored designs (of the time) and thus largely disappeared.

===How they work===
A sectored cache is broken up into sectors (hence the name) each of which has an address tag associated with it. Each sector is further broken down into subsectors, each of which has a "valid" bit allowing for some subsectors to remain empty while others are full. [[File:sectored_diagram.png|thumb|alt=This is a picture of a sectored cache|This is a diagram of a sectored cache taken from Jeffry B. Rotham1.]]When there is a miss to a sector, a resident sector is evicted, an address tag is set to point to the missed sector and a single subsector is fetched. When a subsector is missing but the sector "containing" it is present then only the subsector needs to be fetched. As mentioned in the history section sectored caches were all but abandoned due to the inferiority to other designs, this inferiority came mainly to the design flaw that a sector would often be evicted before all subsectors had been loaded thus at any given time much of the cache was not utilized.Sector caches do have, however, one important advantage. In a normal, (non-sectored) cache, the only way to have a very large cache capacity with a relatively small numb er of tag bits is to make the cache blocks (lines) very large; the problem in that case is that every miss requires that a large block be fetched in its entirety. With a sector cache, it is possible to fetch only a portion of a block (or sector), and thus the time to handle a miss, and the bus traffic, can both be significantly reduced. Thus, although it is likely that sector caches will have higher miss ratios than normal caches, there is the possibility that when timing is considered, the sector cache will be found to have better performance.

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern where a cache line conflict occurs. These types of memory patterns cause conflict misses, a cache miss caused by subsequent accesses use and evict the same cache line.

In general, the solution to conflict misses is a cache of higher associativity. However, associative caches require more logic than direct mapped caches, implying that direct mapped caches are faster but less efficient.
In actual workloads, it was discovered that high associativity is only needed for very few cache lines. The victim cache's effect is to extend the associativity of cache lines which need them. The associativity of that particular direct mapped cache line increases by the number of entries in the victim cache.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, AMD K10, and the Intel Core i7 series.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data by ensuring that data is only available at one cache level. When a line of cache is evicted from a lower level cache, it is added to a higher level cache. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

However, the motivation behind the victim cache between the architectures could not be more different.

In K7, the cache was located on a very slow external bus. The victim cache acted as a buffer between evicted lines from L1 cache and slow L2 cache.

In K8, and later iterations of K7, the L2 cache was integrated on-chip, but transferring data between the L1 and L2 cache is still an expensive (powerwise) operation that the victim cache helped mitigate. In addition, the hardware is already there from the K7 core.

K10 adopted a three-level cache hierarchy, using smaller but faster L1 and L2 caches coupled to a large, slow L3 "victim cache". The "victim cache" is 2-6 MB, an order of magnitude larger than most victim cache implementations, which are usually no more than 16 entries (1024 bytes).

With the increasing focus on multiprocessing, the creation of K10's large L3 "victim cache" served to make it possible to design a large and relatively fast cache capable of serving more than two CPUs. Similarly, Intel's Core i7 uses the L3 "victim cache" with non-shared L2 caches, although the cache hierarchy is inclusive. It marks the first time that an Intel chip has implemented a victim cache.

Look into:
non-x86 victim caches, herp

Actual *implications* of victim caches for inclusive vs. exclusive cache hierarchies... yep
==Notes==
{{Reflist}}

== References ==
1. http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1034.pdf
2. http://delivery.acm.org/10.1145/200000/192072/p384-seznec.pdf?ip=152.14.244.199&acc=ACTIVE%20SERVICE&CFID=83457235&CFTOKEN=35168855&__acm__=1328554043_50f74be9f1a9f6d72939aa9190e069e7

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:59:29Z

Pzwong: /* Victim Cache */

== Sectored Cache ==
Hard section

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern (of which a cache line conflict occurs). In effect, this extends the associativity of would-be conflict misses by the number of entries in the victim cache for very low cost.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, and finally the AMD K10.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

In K7, the cache is on a very slow external bus. The victim cache acted as a buffer between evicted lines from L1 cache, and slow L2 cache.

The K10's "victim cache" deserves some more inspection, as it is 2-6 MB, an order of magnitude larger than most victim cache implementations. It is more of a buffer for efficient implementation of AMD's exclusive cache hierarchy. It is possible that AMD decided that the L3 cache was fast enough to act as a victim cache.

Look into:
non-x86 victim caches, herp

Actual *implications* of victim caches for inclusive vs. exclusive cache hierarchies... yep

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:53:41Z

Pzwong: /* Victim Cache */

== Sectored Cache ==
Hard section

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. This cache is usually highly associative and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern (of which a cache line conflict occurs). In effect, this extends the associativity of would-be conflict misses by the number of entries in the victim cache for very low cost.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, and finally the AMD K10.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

The K10's "victim cache" deserves some more inspection, as it is at least 2MB big and 32-way set associative; at this point, it is no longer a traditional victim cache and more of a buffer for efficient implementation of AMD's exclusive cache hierarchy. It is possible that AMD decided a traditional, fast victim cache was not beneficial on the K10 architecture and elected to directly use L3 cache as a victim cache.

Look into:
non-x86 victim caches, herp

Actual *implications* of victim caches for inclusive vs. exclusive cache hierarchies... yep

actual cache organization of victim cache (my source said direct mapped but some are fully/especially-highly- associative)

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:51:42Z

Pzwong: /* Victim Cache */

== Sectored Cache ==
Hard section

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. For speed reasons, this cache is usually direct-mapped and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern (of which a cache line conflict occurs). In effect, this extends the associativity of would-be conflict misses by an extra way for very low cost.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, and finally the AMD K10.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

The K10's "victim cache" deserves some more inspection, as it is at least 2MB big and 32-way set associative; at this point, it is no longer a traditional victim cache and more of a buffer for efficient implementation of AMD's exclusive cache hierarchy. It is possible that AMD decided a traditional, fast victim cache was not beneficial on the K10 architecture and elected to directly use L3 cache as a victim cache.

Look into:
non-x86 victim caches, herp

Actual *implications* of victim caches for inclusive vs. exclusive cache hierarchies... yep

actual cache organization of victim cache (my source said direct mapped but some are fully/especially-highly- associative)

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:49:49Z

Pzwong: /* Victim Cache */

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:44:31Z

Pzwong: /* Victim Cache */

== Sectored Cache ==
Hard section

== Victim Cache ==
The Victim Cache, in architectures with them, stores just-evicted lines from another level of cache. For speed reasons, this cache is usually direct-mapped and has very few entries, but solves one of the pathological cases for direct-mapped caches, the alternating memory access pattern (of which a cache line conflict occurs). In effect, this extends the associativity of would-be conflict misses by an extra way for very low cost.

Architectures implementing victim cache for x86 include the Transmeta Efficeon, AMD K7, AMD K8, and finally the AMD K10.

AMD has traditionally implemented an exclusive cache hierarchy, a form of cache that avoids duplication of data. Therefore, a victim cache is a natural development from implementation of an exclusive cache.

The K10's victim cache deserves some more inspection, as it is at least 2MB big and 32-way set associative; at this point, it is no longer a traditional victim cache and more of a buffer for efficient implementation of AMD's exclusive cache hierarchy.

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:38:58Z

Pzwong: /* Victim Cache */

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:37:55Z

Pzwong: /* Cache */

Chapter 6: Joshua Mohundro, Patrick Wong

2012-01-30T18:26:30Z

Pzwong: herp