6.173 Lab #4: barrier

Deadlines

Useful links

Goal

The goal of this lab is to implement a barrier. A barrier allows cores to synchronize globally: a core blocks at a barrier until all cores reached the barrier, and then all cores proceed. You may have wished that you had this primitive in previous labs, for example, to coordinate termination of your software across cores. For example, one of the staff solutions for lab 3 has the following use of barriers: 

  ... do some initialization
  barrier();
  if (corenum() == MASTER) {
    master(&idle);
  } else {
    slave(&myjobs, &mytime);
  }
  barrier();
  ... print results
The two barriers in this code fragment cause all cores to wait until initialization is finished, and again to wait until all cores have finished the computation before printing results.

In general, each core calls barrier() multiple times. A core's j'th call to barrier() should only return after every other core has entered its j'th call to barrier().

Your task is to build two implementations of a barrier: one in software using your hardware broadcast messages, and one in hardware using Verilog. Only cores 2 and up should participate in barriers. The challenge in both implementations is dealing with the case that one core comes out of a barrier quickly and hits the next barrier (or the same barrier again in a loop) before the other cores have come out of the first barrier. The presence of the slower cores in the first barrier should not trick the fast core into thinking that they have reached the second barrier.

Task 1: Update your git repo

You must pull the lab 4 code into your git repository. As with the previous labs, you should first commit your changes and then pull the new lab 4 files: 

you@eelab01$ git status
the current state of your git repo
you@eelab01$ git add files that you want to commit
you@eelab01$ git commit -a
you@eelab01$ git pull

You should now see a sw/lab4 directory with a beehive_main.c. You will also see skeleton code in lib/barrier.c. The pull also will update software and hardware makefiles to build lab 4 (e.g., barrier.img).

Task 2: barrier using broadcast

Complete the implementation of bcast_barrier() in lib/barrier.c. Make will build barrier.img. Your code should pass the test in lab4/beehive_main.c on risc_13.bit.

At a high level, your bcast_barrier() should call hw_bcast_send() to announce that the current core has reached a barrier, and then call message_recv() to find out when all the other cores have reached the same barrier.

You may find it convenient to maintain per-core state across successive calls to bcast_barrier. Because the Beehive lacks cache coherence, you need to make sure that each core's state is on a separate cache line. Here's a way to do that by padding each core's data to the size of a cache line: 

struct {
  int x;
  char padding[32 - sizeof(int)];
} state[16] CACHELINE;
Each core would then get at its state with state[corenum()].x.

Hint: you do not need to keep state.

Hint: it's worth simplifying your design as much as you can, since you may be able to use ideas from your software solution in your hardware implementation.

Please use only messages for interaction between cores. Please do not use shared memory.

Task 3: hardware barrier

Your job is to implement a hardware barrier unit. Your hardware should implement the interface used by hw_barrier in shared/intercore.as.

When you're done you should be able to pass the test in lab4/beehive_main.c on risc_13.bit. To test your hardware, un-comment the line in mc_main that calls hw_barrier.

Debugging your Verilog using the FPGA board can be difficult since it's difficult to tell what your modules are doing, what's happening on the ring each cycle, etc. See the Simulation HOW-TO for how to use the Modelsim Verilog simulator for Verilog debugging.

If you look at hw_barrier in intercore.as, you will see that the instruction

aqw_ld vb,barrierControl

triggers a new I/O device, namely number 6. That I/O device will be your barrier unit. Your task is to implement a Verilog module that implements the barrier unit by filling in the appropriate logic inside Barrier.v. The desired semantics is to have the Barrier module respond by asserting its done signal only after all other modules have entered the barrier.

To help you along, we have defined the input and outputs of the Barrier unit in the file Barrier.v. Your job is to complete the implementation of the Barrier module. Make sure to think about the following:

Before you start implementing, please discuss your design with one of the course staff, perhaps at office hours. Your barrier hardware will be complex enough that it's worth getting the design right before implementing.

Here are a few other implementation suggestions:

Task 4: submit lab

Submit your versions of Barrier.v and barrier.c.

End of Lab #4!