Course Project - Instruction Set Simulator

General Overview   Collaboration   ISS/Assembler Details   Arch Opt/Research Details   Additional links


General Overview

This semester you will be developing an instruction set simulator (ISS) for your own custom assembly language. You ISS will need to be both pipelined (basic 5-stage pipeline) and cycle accurate (including stall cycles due to data and control hazards and any potential pipeline forwarding) and you will implement your ISS in C++. Additionally, you will need to implement an optimization of your choice and finish with a technical research paper.

The layout of this project is very similar to the methodology used by researchers when optimizing system architectures. To test out potential optimizations, the researcher must first obtain an ISS for the architecture tested. Many times, if a researcher is using a standard architecture, a simulator already exists and the researcher may bypass developing the ISS. However, in the case of a custom ISS (as is with this project), the researcher must develop an ISS for the instruction set. After the testing environment is obtained and/or verified, the researcher can then modify the ISS to simulate architectural optimizations to measure the effects on the system. Finally, the researcher will culminate their work with a final paper, describing their work and contributions.

The project will be broken into 2 main parts for grading purposes:
  1. Assembler and ISS - Due Monday, Oct 29.
  2. Architectural Optimization and Research Paper - Interview during finals week.

Collaboration

For this project, you may either work individually or with 1 other partner (absolutely no groups larger than 2 individuals). Both individuals and groups of 2 will be graded the same - I do not expect a better project from a group of 2, nor will I accept less work from an individual. You may choose your own partner, but please choose wisely! After you have formed your group, you may not change/drop partners.

In addition, all academic integrity and collaboration polices discussed on the main page apply to this project.

ISS/Assembler Details

ISA Design:

First you will need to create your own instruction set architecture for a 32-bit processor. This will include, but is not limited to, the following:

Basic Simulator Design:

You will need to create an Instruction Set Simulator (ISS) for your instuction set. Your simulator will read in a program file in intermediate format and execute the program. At program termination, you will need to print out any values that were calculated and stored in registers or memory locations to verify the functionality of your ISS. In addition, you must calculate the CPI and output that value upon program termination.

Your simulator must use a 5 stage pipeline and must be cycle accurate including handling all stall cycles due to data and control hazards, any potential pipeline forwarding to minimize stall cycles, and resource sharing (register file). The implementation details are up to you, however do not implement any optimizations at this point. Your pipeline should resemble the pipeline in Appendix A. I will give you some sample programs and your CPI should match up with my expected CPI for that bit of code. If it doesn't you will need to explain why, siting details in your simulator.

For simplicity, you may assume that all alu operations take 1 cycle to execute

Don't forget, you are implementing a real architectural simulator so make all of your design choices keeping that in mind. For example, you will need to read you binary in to either instruction memory or a ROM and then run the program from that location.

Assembler:

Input to your ISS will be a program represented in intermediate format. As you do not want to have to write a program using opcodes and field values, you will ne to write a separate assembler. This program will take as input a program that you will write in your own custom instruction set and output the program in intermediate format.

Testing:

You will need to write programs to test the functionality of your ISS. I suggest you write these applications first in C/C++ and then manually translate them to your assembly language before running them through your assembler. Here is an example of a simple program to move memory around and associated assembly code for a sample instruction set. NOTE: Your assembly language will not look exactly like mine. The details of those files are dependent on your instruction set, this is just an example (sample output will be provided shortly): Since everyone's instruction sets will be different, I can't provide you with hard testbenches. However, here are the provided test cases that you will have to pass. I am including both C and ASM code, but you may need to slightly modify the assembly code so that the program will work in your instruction set. In fact, I will expect that you will change the ASM code, just make sure that the functionality is the same: For the following test cases, I am supplying you with sample C code and you will need to create the associated assembly code for testing: In addition, you will need to create 2 more benchmarks to test your code.

I will verify the functionality of your ISS using both the CPI and the results that you output at program completion.

CPI Benchmarks:

load_delay_1.asm CPI = 3.5
load_delay_2.asm CPI = 3.5
load_delay_3.asm CPI = 3.5
load_reg_1.asm CPI = 1.8
load_reg_2.asm CPI = 1.8
load_reg_3.asm CPI = 1.8
alu_reg_1.asm CPI = 1.8
alu_reg_2.asm CPI = 1.8
alu_reg_3.asm CPI = 1.8
ex-mem_to_ex_1.asm CPI = 2.33
ex-mem_to_ex_2.asm CPI = 2.33
ex-mem_to_ex_3.asm CPI = 2.33
mem-wb_to_ex_1.asm CPI = 2.33
mem-wb_to_ex_2.asm CPI = 2.33
mem-wb_to_ex_3.asm CPI = 2.33
mem-wb_to_ex_4.asm CPI = 2.33
mem-wb_to_ex_5.asm CPI = 2.33
mem-wb_to_ex_6.asm CPI = 2.33
st_mem-wb_mem.asm CPI = 2.33
st_addr_ex-mem_ex.asm CPI = 2.33
st_addr_mem-wb_ex.asm CPI = 2.33
ld_addr_ex-mem_ex.asm CPI = 2.33
ld_addr_mem-wb_ex.asm CPI = 2.33
ld_st_mem-wb_mem.asm CPI = 2.33
big_test.asm CPI = 1.8
branch_1.asm CPI = 3 (same if branch is evaluated in 2nd or 3rd cycle) - register file must show r1 = 0 and r5 = 6 ONLY
branch_2.asm CPI = 2.5 if branch evaluated in 3rd cycle, CPI = 2.25 if branch evaluated in the 2nd cycle - register file must show r1 = 0 and r5 = 6 ONLY

What to turn in:

You will need to email me a tarred and zipped file (or a Winzipped or RARed file) containing the following:

Grading:

After the due date, you and your partner will need to make an appointment to come to my office to demo your ISS. You will have no more than 30 minutes to give me a demo of the above programs and your own custom benchmarks to verify your ISS. Your grade will be based on the following: NOTE: Both members will not necessarily get the same grade. The purpose of the demo will be to make sure you have implemented the assignment correctly and for me to assess who did the work. You will need to prove to me that both partners shared equal responsibility and that each person knows the internal workings of the code. I will have a set of questions and I will alternate who answers the question. At the end of the interview, I will then assign a percentage weight between the two partners for work done. Your goal is just to convince me that you both participated equally.

During the demo you will be demoing a subset of the provided benchmarks and your custom benchmarks. The subset will be chosen randomly during the demo. You are only given a fixed period of time to demo your code and if we don't get through all of the tests, you will not get points for the ones that you don't get to. Thus, it is imperitive that you follow the directions above on what to turn in (All assembly code must be preassembled so that we can avoid that step during the demo). I will not give you time to modify assembly code nor will I give you time to assemble the code (although I will have you assemble some code to show the funcationality of your assembler). I am not trying to be mean, I just have many groups to get through and it is very important that we finish in the allotted time.

Architectural Optimization and Research Paper Details

After you have developed your simulator testing environment, you will need to modify your ISS to implement an architectural optimization. You will get to choose which optimization you would like to explore. You will first choose the optimization and then do a survey of existing techniques. This survey will be the related work section of your research paper. During your survey, you will think about how an existing method can be modified to improve the technique or combined with another technique to produce improved results. This extension to an existing technique is not necessary, you can just implent the basic optimization if you choose. You will also need to implement your optimization and if you extend an existing technique, you will need to implement the base technique for comparison purposes. NOTE: You will need to get instructor approval of your optimization technique. NOTE: you will need to add additional functionality to your simulator for this part.

Quantifying Your Optimization

You will need to use an appropriate metric to quantify your optimization compared to the system without the optimization and to previous work if you are improving/extending a technique. If your optimization improves CPI, you may simply compare change in CPI. If your optimization reduced power/energy consumption, you may be able to quantify using reduction in switching activity or you can calculate the power/energy consumption. After you read current research papers in the area of your optimzation, this quantification should become obvious.

Sample Optimzation Topics

One of the most difficult parts of becoming a researcher is developing novel solutions to existing problems and/or discovering new areas for exploration. Below is a list of potential areas of optimization. Or course I would encourage you to pick a topic not listed below:

Grading

During finals week, you will need to make an appointment to demo your optimzation. You will have no more than 30 minutes for you demo, and the demo will include the following: NOTE: Since I am allowing you to implement an existing technique, you must show improvement to your system. Your grade will be severly impacted if you do not show improvement. However, if you extend an existing technique with something novel, your grade will not depend on how successful your optimzation is. Your grade will be based on implementing a novel optimization that improves a previous technique. There is no minimum placed on what the improvement has to be but you must show at least some improvement.

Again, as with the first demo, both partners will not necessarily get the same grade.

Presentation

During the last weeks of the course, you will need to give a 10 minute presentation describing your optimization and previous work pertaining to your to the class. Both partners will need to participate in the presentation. This will be worth 10% of your grade. You MUST adhere to the time limit for your presentation. Your grade will suffer if you are over or under your 10 minute limit. This means that you will need to prepare the timing very well. This is exactly the contraints you would have if you were to present your findings at a conference.

Research Paper

Your final task is to write a research paper presenting your optimization technique. To prepare you for writing technical documents in the future, you will write your paper in the standard technical format used by most conference and journal publications. This is the two column, single spaced, 9-pt font, fully justified format (this will become clear as you read papers). A research paper basically contains the following sections. There are variations depending on what needs to be reported:
    Abstact: 100-200 words describing what you did and results
  1. Introduction: Background information and a longer summary of what you did and results you got. You should briefly mention how you technique differs from previous work in this section
  2. Related work: Provide summaries of previous work related to your optimization including references to the papers (include cross-reference to paper listed in your references section). In this section you should clearly distinguish your work from previous work, giving details on how your work is different and how your work improves and/or extends previous methods. Be careful not to trash anyone elses work in this section. For one, it is tacky and two, the authors you are trashing are likely reviewing your paper
  3. Methodology: Describe what you did, how you did it, how it works, etc. Give architectural diagrams, charts and figures where necessary.
  4. Experiment Results: Include a subsection describing your experimental setup followed by (a) subsection(s) presenting your results. Be concise and use graphs to show improvements. Tables may also be used but a graph showing improvements conveys your results much easier than a table that must be read and interpretted.
  5. Conclusions and Future Work: Summarize work and results. Give any future work you may be planning or future work that could be done
  6. Acknowledgments: Acknowledge any person that helped with your research that is not listed as an auther. Also acknowledge any funding sources that funded this work (of course you will not have that for this paper, just future reference).
  7. References: List of papers cited throughout your paper.
Although I don't recommend it, research papers are typically written in MS Word (which is actually what I use). LaTex is also a popular method. You may use any editor that you wish, just make sure your document is formatted correctly.

What to turn in

As with the first part of the project, you email me your project as a single tarred/zipped/rarred file. You will need to turn in the following:

Additional Reading/Resources

Here I have listed some additional resources that may be helpful with your project. I do not know of any pipelined simulators that I can direct you to, the following are simply functional simulators. This means that you should not model your ISS after these simulators, you should just use them as examples of existing simulators.