代写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.