C# Threading for a pipeline

Question

I'm currently creating a pipeline for my asm simulator. I'm to do this with multithreading. Currently I have four threads which correspond to each Fetch, Decode, Execute, and Write Back. I'm confused about how to code a correct pipeline. Here is some of my code:

private void Fetch()
{
    while(_continue)
    {
        fetchEvent.WaitOne();
        if (!_continue) break;
        lock (irLock)
        {
            try
            {
                // Do stuff to fetch instruction...

                catch (IndexOutOfRangeException e) { Err = "Segmentation Fault at Line " + _pc.ToString(); }
                catch (Exception e) { Err = e.Message + "Line " + _pc.ToString(); }
                _pc++;

                GiveTurnTo(2); // used these 2 lines to handle mutual exclusion
                WaitTurn(1);
            }
        }
    }

    private void Decode()
    {
        while (_continue)
        {
            decodeEvent.WaitOne();
            if (!_continue) break;

            lock (irLock)
            {
                WaitTurn(2);
                Console.WriteLine("decode works");
                GiveTurnTo(1);
            }


        }
    }

    private void Execute()
    {
        while (_continue)
        {
            exeEvent.WaitOne();
            if (!_continue) break;

            lock (irLock)
            {
                //WaitTurn(3);
                Console.WriteLine("Am I, execute, getting a turn?");
                // GiveTurnTo(4);
            }

        }

    }

    private void WriteBack()
    {
        while (_continue)
        {
            wbEvent.WaitOne();
            if (!_continue) break;

            lock (irLock)
            {
                Console.WriteLine("Am I, Write Back, getting a turn?");
                //GiveTurnTo(1);
                // WaitTurn(4);
            }

        }

    }
}

I use this method to run a cycle with a button click:

public void nextInstruction()
{
    fetchEvent.Set();
    decodeEvent.Set();
    exeEvent.Set();
    wbEvent.Set();
}
I was thinking of changing nextInstruction() to this:

public void nextInstruction()
{
    fetchEvent.Set();
}

Where each button click will always start with Fetch. After that I thought maybe I could place a set event within the Fetch method to call the next part in the cycle (Decode) and do the same for the following methods. I would end up with something like this:

private void Fetch()
{
    while(_continue)
    {
        // Do stuff....
        decodeEvent.Set();
    }
}

private void Decode()
{
    while (_continue)
    {
        // Do stuff...
        exeEvent.Set();
    }
}

private void Execute()
{
    while (_continue)
    {
        // Do stuff...
        wbEvent.Set();
    }
}
private void WriteBack()
{
    while (_continue)
    {
        // Do stuff...
    }
}

Instead of leaving those set events out in the open, I think they should be activated by some sort of logic, but I don't know what kind of logic. Maybe they could be activated by a button click. That would allow me to control when an instruction is passed down the cycle. In theory, I think this could give me the structure of a pipeline. Can anyone provide any input on this? Can this be accomplished with just Auto Reset Events?

If you look at the first block of code I gave, you can see I tried using a lock, but that made it so only one thread could run at a time. I want to make it so that it follows the format of Fetch0, {Decode0, Fetch1}, {Execute0, Decode1, Fetch3},... and so on. Are locks a necessity in this case?

Answer 1

A pipeline is a process that raises events sync or async. Observers are registerrd with the pipeline to be notified for these events. The pipeline stores the state to allow observers to work with the state. In the case of async events, you will have to ensure synchronization takes place around the state, as well as callbacks to know when the thread has completed or ready for work. Here is a rough high level example of using a pipeline:

public class OnFetchEvent : AsyncEvent {}
public class OnDecodeEvent : AsyncEvent {}
public class OnExecuteEvent : AsyncEvent {}
public class OnWritebackEvent : AsyncEvent {}

public class FetchObserver : Observer,
   IObserve<OnFetchEvent>
{
   public void OnEvent(OnFetchEvent @event)
   {
      ....do some stuff

      // raise the next event
      RaiseEvent<OnDecodeEvent>(); 
   }
}

public class Pipeline
{
   public void RaiseEvent<TEvent>()
   {
      if (typeof(TEvent) is AsyncEvent)
        ...create thread and raise the event which will notify the appropriate 
           observers of the event in the newly created thread
   }

  }

Usage:

pipeline.RegisterObserver<FetchObserver>()
  .AndObserver<DecodeObserver>()
  .AndObserver<ExecuteObserver>()
  .AndObserver<WriteBackObserver>();

pipeline.RaiseEvent<OnFetchEvent>();

This will handle one cycle. Events are raised async (which means the observers will be executed per thread). To have multiple cycles, you need to start the pipeline async (its own thread). And call the pipeline RaiseEvent as required. I hope this provides some high level approach of making use of a pipeline using threads.

Answer 2

Threads are not appropriate for this. You are doing too little work per step before you put the thread to sleep. A better way to simulate it would be just have a single thread doing each of the steps in reverse order, this will ripple the work down the system just like the real system.

public void nextInstruction()
{
    WriteBack();
    Execute();
    Decode();
    Fetch();
}

---

To help understand why I process them in reverse order take a look at how my system works as we call it repeatedly.

• Call 1
  1. WriteBack() does nothing, its input buffer is empty.
  2. Execute() does nothing, its input buffer is empty.
  3. Decode() does nothing, its input buffer is empty.
  4. Fetech() Grabs the 1st instruction and puts it in to Decode()'s input buffer.
• Call 2
  1. WriteBack() does nothing, its input buffer is empty.
  2. Execute() does nothing, its input buffer is empty.
  3. Decode() Grabs the fetched 1st instruction from it's input buffer, places the decoded instruction in to Execute()'s input buffer.
  4. Fetech() Grabs the 2nd instruction and puts it in to Decode()'s input buffer.
• Call 3
  1. WriteBack() does nothing, its input buffer is empty.
  2. Execute() Grabs the decoded 1st instruction from its input buffer, processes it, then places the result in to WriteBack()'s input buffer.
  3. Decode() Grabs the fetched 2nd instruction from its input buffer, processes it, then places the decoded instruction in to Execute()'s input buffer.
  4. Fetech() Grabs the 3rd instruction and puts it in to Decode()'s input buffer.
• Call 4
  1. WriteBack() Grabs the processed 1st value from its input buffer and writes it back to the memory store.
  2. Execute() Grabs the decoded 2nd instruction from its input buffer, processes it, then places the result in to WriteBack()'s input buffer.
  3. Decode() Grabs the fetched 3rd instruction from itss input buffer, processes it, then places the decoded instruction in to Execute()'s input buffer.
  4. Fetech() Grabs the 4th instruction and puts it in to Decode()'s input buffer.
• Call 5
  1. WriteBack() Grabs the processed 2nd value from its input buffer and writes it back to the memory store.
  2. Execute() Grabs the decoded 3rd instruction from its input buffer, processes it, then places the result in to WriteBack()'s input buffer.
  3. Decode() Grabs the fetched 4th instruction from itss input buffer, processes it, then places the decoded instruction in to Execute()'s input buffer.
  4. Fetech() Grabs the 5th instruction and puts it in to Decode()'s input buffer.
• Call 6
  1. WriteBack() Grabs the processed 3rd value from its input buffer and writes it back to the memory store.
  2. Execute() Grabs the decoded 4th instruction from its input buffer, processes it, then places the result in to WriteBack()'s input buffer.
  3. Decode() Grabs the fetched 5th instruction from itss input buffer, processes it, then places the decoded instruction in to Execute()'s input buffer.
  4. Fetech() Grabs the 6th instruction and puts it in to Decode()'s input buffer.
• ect.

See it takes 4 calls before the pipeline is full, this is what happens in real life, it takes more cycles to get the first instruction from Fetch to WriteBack however the time period between instructions coming out of the pipeline is a lot shorter in comparision.

Now looking at your old system you can see you actually don't ever fill your pipeline, a single instruction can go right through all of the stages in a single simulation step.

• Call 1
  1. Fetech() Grabs the 1st instruction and puts it in to Decode()'s input buffer.
  2. Decode() Grabs the fetched 1st instruction from its input buffer, processes it, then places the decoded instruction in to Execute()'s input buffer.
  3. Execute() Grabs the decoded 1st instruction from its input buffer, processes it, then places the result in to WriteBack()'s input buffer.
  4. WriteBack() Grabs the processed 1st value from its input buffer and writes it back to the memory store.
• Call 2
  1. Fetech() Grabs the 2nd instruction and puts it in to Decode()'s input buffer.
  2. Decode() Grabs the fetched 2nd instruction from its input buffer, processes it, then places the decoded instruction in to Execute()'s input buffer.
  3. Execute() Grabs the decoded 2nd instruction from its input buffer, processes it, then places the result in to WriteBack()'s input buffer.
  4. WriteBack() Grabs the processed 2nd value from its input buffer and writes it back to the memory store.

In a single call our instruction went from fetched to written back before we even could fetch the 2nd instruction