Lab Overview:

Since we want to be able to tout the excellent performance of our processors in our upcoming press release, you are going to need to perform a few more benchmarks to gauge your processor's speed. If you are unsatisfied with your results, you may wish to perform various optimizations in order to improve your performance. If you are feeling up to the challenge, you may even join the multi-core revolution and make your processor a dual-, quad-, or even higher core system! Good luck.

Lab Deliverables:

• Demonstration: A live demonstration of your processor will be required for all groups.
• Progress Report: Your progress report will consist mainly of the answers to the questions posed in this lab. Your report should also contain copies of the final datapath for both your front-end (fetch) and back-end (execution). In addition, you will need to include all the the source files for the final version of your project. This includes all your Verilog source files, assembly code files (*.s, *.coe), testbenches, and Megawizard generated files. You should also include an updated copy of your ISA manual (if you didn't implement certain instructions, make sure they do not show up in your manual). Your final grade will ultimately be determined by whether you have a working processor so it goes without saying that the files you submit must be synthesizable and implementable and produce the correct output on all the benchmark programs.

Lab Description:

Performance Benchmarking

1. fib_native: Your native implementation of Fibonacci (i.e. written in your ISA). It must be able to handle arbitrary inputs such as: -1, 2, 9, and 31.
2. fib_sg: The SuperGarbage implementation of Fibonacci (i.e. run through your VirtualMachine). This also must be able to handle arbitrary inputs.
3. sort_sg: The SuperGarbage implementation of Sort (i.e. app2). It is enough to correctly process the given app2.in input data.

Uniqueness of Design

All work beyond this point is optional.

Optimize Your Processor (Optional)

1. Cycle Time
2. CPI
3. (Dynamic) Instruction Count

Cycle Time

There may be other options available in Altra tools (such as "Timing Advisor") to explore. You may want to speak with your classmates to find out about anecdotal experiences with various parameters.

As you reach diminishing returns from tweaking Quartus II synthesis and implementation parameters, the next step is to try to improve the cycle time of your processor by modifying the design itself (i.e. your Verilog implementation). Remember that it is the critical path that ultimately determines the operating frequency. Your efforts should therefore be aimed at reducing the critical path using such techniques as MUX reordering, moving logic across pipeline stages, or introducing more pipelining. By examining the timing reports and other Quartus II outputs, you can determine the parts of your design (e.g., the critical path) that you may want to focus on optimizing. You often can rewrite the code to reduce critical paths (e.g., reordering muxes, or moving logic across pipeline stages, or pipelining more.) Again, before you start changing your design, make sure to save your work!

Cycles Per Instruction (CPI)

Dynamic Instruction Count

Also, you should note that in the course of your optimization, you should not change the basic algorithms being used for the benchmarks. For example, there are much better ways of calculating fibonacci numbers but your algorithm still needs to be recursive and do the same number of comparisons as the original version. Also, you should not try to optimize the SuperGarbage binaries although it is acceptable to optimize VirtualMachine. Finally, don't forget to make sure that your "optimizations" don't change the end result of the algorithm (i.e. they should still be correct ;)).

Multi-core Processor (Optional)

The following figure shows a simple dual-core design.

In this example, there are two slightly modified cores (i.e. execution units). The biggest change in this system is the location of the data memory. In your single-core design, the data memory resided within the execution unit. However, in a multi-core design the data memory is located outside of the backend so that it can be shared among multiple execution units.

Sharing of the data memory can lead to contention on the memory among the cores. Since the memory can only handle a single request at a time, if multiple requests are received simultaneously, there must be some form of arbitration. For the core that loses out on arbitration, the 'refused' signal is asserted. The simplest arbitration scheme is to always give priority to one of the cores. Unfortunately, this is an unfair scheme and can lead to poor performance of the lesser priority core is memory-intensive. To handle this problem, you will likely want to devise a better method of arbitration.

More sophisticated designs may employ banking, where the data memory is actually composed of several smaller memories. The lower bits of the address indicate which bank an address goes to. In this case, the arbitration logic will only assert the refused signal if the two cores try to address the same bank.

Multi-core Performance

Provided below is a parallel version of the fibonacci algorithm:

 
// the following variables are shared between the two processors
int sync = 0;
int val = 0x3DEADBEEF;
 
int fib_core0(int n)
{
  if (n < 5)
    return fib_internal(n);
 
  val = n-2;                       // write value to core 1
  sync = 1;                        // signal to core 1 that value is ready
 
  int temp = fib_internal(n-1);    // compute my part of fib
  while (sync == 1);               // wait for core1 to be ready 
 
  return temp + val; 
}
 
 
int fib_core1(int n)
{
   while (1) { 
       while (sync == 0);          // wait for core0 to send value 
 
       int temp = fib_internal(val);
       val = temp;                 // write value for core0 to receive
 
       sync = 0;                   // signal back to core1 that we are done;   
 
   }
}

In this code, core0 relegates the task of computing fib(n-2) to core1 while it computes fib(n-1). After both results are available, core0 adds them to get the final result. You will note that both 'sync' and 'val' are shared variables so communication between cores occurs through these variables.

The VirtualMachine function is much harder to parallelize but if you can do it effectively, we will give you a gold star for the day!

Multi-core Implementation Details

• Having multiple cores running simultaneously means you will most likely have multiple stacks. These need to be separated in the data memory so that the cores do not interfere with each other. Another other non-shared (i.e. private) data also needs to be separated.
• In order to supply instruction to multi execution units, you will likely need multiple fetch units. (You might think up some ingenious way of getting around this by modifying your fetch unit, so dream big :)). You have two choices of how to initialize the memories for each fetch unit. One way is to write a single program with all the code and have the cores start fetching from different places (depending on which code they need to execute).
• You can avoid having to maintain different Verilog for the different cores by having case statements built-in to determine behavior based on which core it is. To do this, you need to have some state for each core which maintains their identity (is it core0? core1? coreN?). You can then use a special I/O port to initialize the identity after resetting the processor.