代写Java算法，处理Control Flow Graph，尽可能的优化算法，快速高效。
Instructions
- You may collaborate with (at most) one other student to complete this assignment.
- Each team shall submit a .zip file containing all the source files and documents.
- On top of each file, please clearly indicate your names and student IDs
- You must clearly describe the main methods of your program (i.e., methods that implement main algorithms, etc.)
Marking Guide
The total marks of this assignment is 100. Marks will be allocated based on
the correctness, clarity and originality of your code.
Introduction to Cache Analysis
The purpose of this assignment is to develop algorithms to compute, as
precisely yet as quickly as possible, a safe overestimate of the cache misses
that can happen in a given computer program.
For simplicity, we can assume that we are dealing with a simplistic program
that can be converted into a control flow graph (CFG) as shown in the figure
below.
The CFG shows the program’s control points as its nodes. The nodes in figure
(a) above show which memory blocks are needed at each control point. For
instance, the initial control point denoted as node B1 needs to load memory
blocks m1, m2, m3, and m4.
A program can load memory blocks from a storage device such as a hard disk.
However, loading and storing memory blocks from such devices is very slow.
Hence, most computers contains caches that are used to hold memory blocks and
make them available to the program at a much higher speed. The number of
blocks that can be held in the cache is determined by the number of cache
lines available. Figure (b) above shows that our simplistic program has four
cache lines c0, …, c3.
Memory blocks are loaded into the cache (from the hard disk) based on a given
cache replacement policy. We can assume that we have a direct-mapped cache,
where memory blocks can be loaded only onto specific cache lines. For
instance, figure (b) tells us that blocks m1 and m5 can be loaded only into
cache line c0.
A cache hit happens when a memory block needed by the program is already in
the cache. For instance, if at node B3, the program needs the memory block m1,
and it is already there, there is no need to load it from the hard disk. On
the other hand, a cache miss happens when a required memory block is not in
the cache and needs to be loaded from hard disk onto the cache. For instance,
when the program starts up and the cache is empty, the initial node B1
requires us to load all the four memory blocks it needs, resulting in four
cache hits.
Analytically, the cache analysis problem boils down to statically determining
all possible cache states (and therefore the number of misses in the worst
case) at each node using a suitable algorithm.
The assignment is divided into the following steps.
Question 1
Create a Java package called datastructure containing classes for CFG and
directmapped cache replacement policy. Create a class TestExample1 which
models the sample program and cache provided in the figure on page 1.
This question will be marked on the following aspects:
- Correct and error free implementation.
- Ability to scale and flexibly model other programs. For instance, we should be able to add as many cache lines as needed, as easily as possible, and easily add nodes to a program.
- Quality and organisation of code.
Question 2
Design two algorithms to answer the cache analysis problem.
- Class ExplicitEnumeration enumerates all possible states of the cache at each node in the CFG. Once this exhaustive enumeration is done, it finds the worst number of cache misses for each node in the CFG and returns them.
- Adapt the algorithm above to create a class CacheLineEnumeration containing an algorithm to enumerate whether a miss can happen in each cache line (and not the whole cache) at each node in the CFG. The algorithm returns the worst case number of cache misses as the number of cache lines that can have a miss along each node in the CFG. (This is not strictly a divide and conquer technique, since the answer returned by this adaptation may not be the same as the result of the first algorithm)
Bonus: Using any of the techniques taught in the class or via your own
research, come up with a third algorithm to compute the worst-case number of
cache misses at each node in the CFG. (Bonus marks can not be carried over to
other assessment items)
Question 3
Compare each of the algorithms created in question 2 both experimentally and
theoretically. Experimental evaluation will require creating an algorithm to
randomly create a CFG and direct-mapped cache. The input to this algorithm
will be the numbers of control points, number of cache lines and number of
memory blocks. The algorithm will randomly generate all other details needed
before any of the algorithms in question 2 can be read.
Theoretical analysis will be based on time complexity analysis of the
algorithms in question 2.
Bonus: you may analyse the third, bonus algorithm from question 2 in addition
to the other two algorithms. You may analyse the algorithms for precision or
how close they are to the actual number of cache misses in the program.
