Sequential Processor Architecture Solution

Introduction



In this lab, you will learn about the design and implementation of a sequential Y86-64 processor. When you have completed the lab, you will have a keen appreciation for the interactions between code and hardware that affect the performance of your programs.




The lab is organized into two parts. In Part A you will write some simple Y86-64 programs and become familiar with the Y86-64 tools. In Part B, you will extend the SEQ simulator with a new instruction.




Logistics



You will work on this lab alone.




Any clarifications and revisions to the assignment will be posted on the course Web page.







Handout Instructions



Download the archlab-handout.tar file from the Assignment tab on CS 225 LMS page.




Start by copying the file archlab-handout.tar to a (protected) directory in which you plan to do your work.



Then give the command: tar xvf archlab-handout.tar. This will cause the following



files to be unpacked into the directory: README, Makefile, sim.tar, archlab.pdf, and simguide.pdf.







1















Next, give the command tar xvf sim.tar. This will create the directory sim, which contains your personal copy of the Y86-64 tools. You will be doing all of your work inside this directory.



Finally, change to the sim directory and build the Y86-64 tools:



linux cd sim




linux make clean; make







Part A



You will be working in directory sim/misc in this part.




Your task is to write and simulate the following three Y86-64 programs. The required behavior of these programs is defined by the example C functions in examples.c. Be sure to put your name and ID in a comment at the beginning of each program. You can test your programs by first assemblying them with the program YAS and then running them with the instruction set simulator YIS.




In all of your Y86-64 functions, you should follow the x86-64 conventions for passing function arguments, using registers, and using the stack. This includes saving and restoring any callee-save registers that you use.




sum.ys: Iteratively sum linked list elements




Write a Y86-64 program sum.ys that iteratively sums the elements of a linked list. Your program should consist of some code that sets up the stack structure, invokes a function, and then halts. In this case, the function should be Y86-64 code for a function (sum list) that is functionally equivalent to the C sum list function in Figure 1. Test your program using the following three-element list:







Sample linked list



.align 8 ele1:




.quad 0x00a




.quad ele2




ele2:




.quad 0x0b0




.quad ele3




ele3:




.quad 0xc00




.quad 0







rsum.ys: Recursively sum linked list elements




Write a Y86-64 program rsum.ys that recursively sums the elements of a linked list. This code should be similar to the code in sum.ys, except that it should use a function rsum list that recursively sums a list of numbers, as shown with the C function rsum list in Figure 1. Test your program using the same three-element list you used for testing list.ys.







2
























1 /* linked list element */

2 typedef struct ELE {




long val;
struct ELE *next; 5 } *list_ptr;



6

7 /* sum_list - Sum the elements of a linked list */

8 long sum_list(list_ptr ls)




{



long val = 0;



while (ls) {



val += ls-val;



ls = ls-next;



}



return val;



}



17

18 /* rsum_list - Recursive version of sum_list */

19 long rsum_list(list_ptr ls)




{



if (!ls)



return 0;



else {



long val = ls-val;



long rest = rsum_list(ls-next);



return val + rest;



}



}



29

30 /* copy_block - Copy src to dest and return xor checksum of src */

31 long copy_block(long *src, long *dest, long len)

{



long result = 0;



while (len 0) {
long val = *src++;
*dest++ = val;



result ˆ= val;



len--;



}



return result;



}






Figure 1: C versions of the Y86-64 solution functions. See sim/misc/examples.c
















3















copy.ys: Copy a source block to a destination block




Write a program (copy.ys) that copies a block of words from one part of memory to another (non-overlapping area) area of memory, computing the checksum (Xor) of all the words copied.




Your program should consist of code that sets up a stack frame, invokes a function copy block, and then halts. The function should be functionally equivalent to the C function copy block shown in Figure Figure 1. Test your program using the following three-element source and destination blocks:







.align 8




Source block src:



.quad 0x00a




.quad 0x0b0




.quad 0xc00




Destination block dest:



.quad 0x111




.quad 0x222




.quad 0x333







Part B



You will be working in directory sim/seq in this part.




Your task in Part B is to extend the SEQ processor to support the iaddq, described in Homework problems 4.51 and 4.52 at the end of Chapter 4 in the Course text book. To add this instructions, you will modify the file seq-full.hcl, which implements the version of SEQ described in the CS:APP3e textbook. In addition, it contains declarations of some constants that you will need for your solution.




Your HCL file must begin with a header comment containing the following information:




Your name and ID.




A description of the computations required for the iaddq instruction. Use the descriptions of irmovq and OPq in Figure 4.18 in the CS:APP3e text as a guide.




Building and Testing Your Solution




Once you have finished modifying the seq-full.hcl file, then you will need to build a new instance of the SEQ simulator (ssim) based on this HCL file, and then test it:




Building a new simulator. You can use make to build a new SEQ simulator: linux make VERSION=full




4















This builds a version of ssim that uses the control logic you specified in seq-full.hcl. To save typing, you can assign VERSION=full in the Makefile.




Testing your solution on a simple Y86-64 program. For your initial testing, we recommend running simple programs such as asumi.yo (testing iaddq), comparing the results against the ISA simula-tion:




linux ./ssim -t ../y86-code/asumi.yo




Retesting your solution using the benchmark programs. Once your simulator is able to correctly execute small programs, then you can automatically test it on the Y86-64 benchmark programs in

../y86-code:




linux (cd ../y86-code; make testssim)




This will run ssim on the benchmark programs and check for correctness by comparing the resulting processor state with the state from a high-level ISA simulation. Note that none of these programs test the added instructions. You are simply making sure that your solution did not inject errors for the original instructions. See file ../y86-code/README file for more details.




Performing regression tests. Once you can execute the benchmark programs correctly, then you should run the extensive set of regression tests in ../ptest. To test everything except iaddq and leave:




linux (cd ../ptest; make SIM=../seq/ssim)




To test your implementation of iaddq:




linux (cd ../ptest; make SIM=../seq/ssim TFLAGS=-i)




For more information on the SEQ simulator refer to the handout CS:APP3e Guide to Y86-64 Processor Simulators (simguide.pdf).







Evaluation



The lab is worth 90 points: 30 points for Part A and 60 points for Part B.




Part A




Part A is worth 30 points, 10 points for each Y86-64 solution program. Each solution program will be eval-uated for correctness, including proper handling of the stack and registers, as well as functional equivalence with the example C functions in examples.c.




The programs sum.ys and rsum.ys will be considered correct if the graders do not spot any errors in them, and their respective sum list and rsum list functions return the sum 0xcba in register %rax.







The program copy.ys will be considered correct if the graders do not spot any errors in them, and the copy block function returns the sum 0xcba in register %rax, copies the three 64-bit values 0x00a, 0x0b, and 0xc to the 24 bytes beginning at address dest, and does not corrupt other memory locations.







5















Part B




This part of the lab is worth 35 points:




10 points for your description of the computations required for the iaddq instruction.




10 points for passing the benchmark regression tests in y86-code, to verify that your simulator still correctly executes the benchmark suite.




15 points for passing the regression tests in ptest for iaddq.







Submission Instructions



You will submit the files on LMS.




You will be submitting following four files:




– Part A: sum.ys, rsum.ys, and copy.ys.




– Part B: seq-full.hcl.




Make sure you have included your name and ID in a comment at the top of each of your submitted files.




To submit your files, create a new directory called archlab.




Copy all the four files ( sum.ys, rsum.ys, copy.ys, and seq-full.hcl) in the newly created directory archlab.




On the linux prompt go one directory up (i.e., the directory that contains the archlab directory) by typing cd ...




Create a tar file including your submitted files by typing the following at the linux shell prompt: tar -cvf <your registation no.tar lab5




If your registration number is 20100945, type: tar -cvf 20100945.tar lab5.




Submit the <your registation no.tar on LMS.










Hints



The psim and ssim simulators terminate with a segmentation fault if you ask them to execute a file that is not a valid Y86-64 object file.










6