Flux Capacitors might help prevent pipeline hazards

First off, this is not serious at all. Okay, you've been warned.

Ever wondered about alternative approaches to overcome Pipeline Hazards?

Well, looking at this xkcd schematic I started to wonder about the Flux Capacitor's potential in an actual circuit. I'll tell you what made sense in my head, but first, let me explain the basics. If you already know the basics, you may skip to "Flux Capacitors in Computers".

About Pipelining
It's a way of speeding up code execution by dividing it into several stages that perform sub-tasks simultaneously by means of dedicated hardware for each stage. Four consecutive stages are typically used: Fetching the instruction from memory, Decoding it (identifying the operation), Executing the instruction, and Writing Back the result. This ultimately speeds execution up (ideally in a rate equal to the number of stages in the pipeline). Read more.

Pipelined execution. Numbers shown in the graph are the instructions at the left.

About The Hazards
Hazards are problems related to the use of a pipeline in an instruction execution unit. Two Hazards are considered here:

• Data Hazards: It happens when an instruction needs data that's produced by another instruction that previously entered the pipeline, but hasn't finished yet. For example let's say instruction i writes data into register A, and instruction i+1 (the next one) uses register A as an operand to calculate something else. What happens when instruction i+1 is in the Execute stage and i is in the Write Back stage? The value of register A used by i+1 as an operand will be the original value prior to the execution of instruction i because it's not done yet. This is called a Read After Write (RAW) or true data dependency. This is a problem because the data used by instruction i+1 is outdated. 

Data Hazard between Execute and WriteBack (may happen between other stages)

• Control Hazards: This concerns branches, calls, interrupts, exceptions, resets, etc. When sequential execution must change due to a branch or whenever the next instruction to fetch is not the next stored instruction, the Fetch stage must be aware of the address of the next instruction (branch target, interrupt vector, etc). Furthermore, most branches are conditional, and it's not until the Execute stage that the processor knows whether or not the branch should be taken. This is a problem because when the processor becomes aware of a branch, all of the instructions previously loaded into the pipeline might have to be aborted (execution may have to jump elsewhere). This abort depends on the condition of the branch, which will be known after Decode. If the branch must be taken, the pipeline must be flushed or bubbled (instructions previously entered replaced by NOPs [no operations]). If not, no problem. Flushing/bubbling the pipeline is a problem because it's a waste of time, and the pipeline is supposed to speed things up. 
  
  Control Hazard with bubble

There are many approaches to overcome these hazards, mainly divided in two kinds of strategies: Static and Dynamic. Static approaches are performed by the compiler, conditioning the resulting code (rearranging instructions, loop unrolling, and so on). Dynamic approaches are performed by additional hardware (storing data in temporary registers or keeping a record of previous hazards for prediction).

Read more about pipeline hazards.

About the Flux Capacitor
"The flux capacitor is what makes time travel possible", Doc. Brown.

The Flux capacitor is the Y-shaped device inside the DeLorean Time Machine in the Back to the Future films.
Read more.

Flux Capacitors in Computers
So! Let's consider the unlikely event of an actual Flux Capacitor being invented, tested, manufactured, and even miniaturized to a VLSI level. Not happening, bear with me.

My intention is to get useful data from the pipeline and send it back in time in order to correct the hazards.

In the video above, Doc Brown said that the Flux Capacitor from the DeLorean requires 1.21GW to operate. It was capable of reaching ±30 years of time travel for anything inside the whole DeLorean. So, taken to a very small size, hopefully a MEMS Flux Capacitor requiring a couple of watts to achieve a time travel of no more than ±1 second for a cage of a cubic micron wouldn't be so much to ask (would it?).
Even if the proof of concept for time travel at this level is only able to achieve microseconds for cubic nanometers, this would be good enough because going some clock cycles back in time is all that's needed.

As described in the films, the time machine is only capable of taking objects back (or forth) in time, when they are somehow attached to the flux capacitor inside a stainless steel body. So our little (tiny) time machine would be a stainless steel cage containing a miniaturized Flux Capacitor, a time-traveling register, some status and control registers and a charge pump to initiate time travel by providing the required power for the Flux Capacitor to start "Fluxing" (lol).

Time Traveling Register Module (TTRM) Block Diagram

The amount of time to go back must be written to the TTRMSC register (SC=Status and Control). Some clock cycles must be allowed for the charge pump to operate. The amount of clock cycles required is irrelevant as the register will leave this timeline anyway. The future of this timeline is of no interest anymore.

So, Data Hazards won't be a problem anymore with something like the following arrangement, which is some kind of actual Register Forwarding:

Register LookAhead (RLA) Block Diagram

Thus, when a RAW data dependency is detected, the "GO!" signal stores the present WriteBack data into the Time Traveling Register, and activates the Charge Pump to start Time Travel a few (previously configured) clock cycles back in time. In the past, the "Incoming" signal replaces one operand of the ALU with the future data, eliminating the dependency setbacks.


On the other hand, Control Hazards could be taken care of nicely with a similar technique:

Branch LookAhead (BLA) Block Diagram

If a branch should be taken, the "GO!" signal loads the target address into the TTRM. In the past, the "Incoming" signal sets the Program Counter to the Target Address so the correct instruction fetch is made.

After the target address is sent back in time, actually loading the target to the program counter in this timeline wouldn't be completely necessary, as time travel would take care of that, correcting the events in the universe of interest (the one in the past). Watch a cool video about time travel here.

This brings up some questions that must have lots of discussion already: What happens to all the split universes generated by each time travel? Is there such thing as Universe Leaking? Is a free(Universe) function reasonable?

Considering all the split universes generated by this technique, it's important to point out that it will only be always useful for one and only one universe. All other universes will experience the hazards. (?) Oh well. 


That's all. I hope I'm not losing my mind.

Make It Challenge at FTF 2011

I got an invitation to attend the Freescale Technology Forum 2011 at San Antonio, as an educator from Galileo University in Guatemala.
Freescale has lots of cool stuff at FTF every year, such as technical sessions, workshops and very nice receptions with demos at their technology lab.

One of the activities I never miss at FTF is their on-site Design Challenge. I got the first place on the "Can Your Badge Do This?" Design Challenge at FTF2008, and later the third place on a second online version of the same challenge.


The Challenge
So FTF2011's design challenge was called the "Make It" Challenge, and it had two tracks: The Tower System Track and the Robot Track. I decided to go for the Robot approach.

We got this very cool FSLBOT kit, which is a biped robot with gooddies such as 12 touch sensor contacts (placed in the shape of a cartoon head), a freaky face made of LEDs on the touch-sensing head, 8 servo-ready connectors, an Xtrinsic sensor port, etc. Plus, Freescale provided lots of stuff to help us get our designs up and running: A dedicated lab with soldering irons and tools, geek snacks, a HUGE box full of batteries, and two very important elements: A large supply of VEX parts, and an Xtrinsic sensor kit with an accelerometer and a magnetometer.

FSLBOT

The challenge was simple: Make a cool robot to impress the judges with the provided tools and any extra hardware you have in Two Days. The only requirement was to use the FSLBOT's controller, the Tower System Mechatronics Board.

The judges were:   

1. Joe Grand (host), president of Grand Idea Studio, Inc. He was one of the inventors on Discovery Channel's "Prototype This" show. He's a Hacker-RockStar: he's Kingpin from the l0pht!!!!!!!!! :OOOOOO w00t!!!!
2. Heather Knight, Social Robotocist and founder of Marilyn Monrobot Labs. She was one of the kenote speakers at FTF2011, a true geek (meant as a compliment). She was part of the team of engineers behind the "This too shall pass" video, by OK Go.
3. Anton Olsen, Master Geek at Innovation First, Inc. ( VEX Robotics ), Contributor at GeekDad.com, and Blogger at AntonOlsen.com

We had two programming language choices: C and RobotSee. Working in C ultimately meant an autonomous, powerful, but time-consuming robot for me (given the short deadline), while RobotSee meant a PC-dependent, basic, but fast-development robot. That's why I chose RobotSee (My heart still belongs to C).

The RobotSee IDE was made by Eric Gregori for the FSLBOT's controller, the Tower System Mechatronics Board. RobotSee looks a lot like a mix of BASIC and C. I found it very easy to learn and definitely suitable for my situation.

My Entry
I didn't want to make a biped as the suggested FSLBOT, because I couldn't come up with something unique for such robot (I imagined lots of dancing robots at the judging). I wanted to make a wheeled rover so much, but when I got to grab VEX parts from the stack, all the DC motors were gone! Then I started to panic, but considering alternatives for DC motor locomotion, I decided to think outside the box and use something I once told my students to do, with no clue on the implementation.

My general idea was to make a Servo-Only rover. So I came up with this robot that paddles his way fordward using four non-driven wheels, a rubber paddle and two servos: one for paddling and one for lifting the paddle so it can move back.

My paddling robot

So how does it turn left or right? I came up with a cool suspension system that most likely already has a name and evolution. Anyway, my robot has two servos acting together to achieve two states:

1. The servos lift most of the structure at one end, causing the four non-driven wheels to make contact with the floor, supporting the robot. By the way, did I mention this is a carpet robot? It had to be, since I didn't get rubber wheels at the giveaway either, so I used actual shameless gears as wheels.
2. The servos lift the wheels at their other end. This causes a horizontal stand  (made from a large gear) to make contact with the floor (carpet). This gear is very special because it's driven by a fifth servo. This allows the robot to turn exactly the angle it's supposed to (provided you have a rubber band around it for friction).

Take a look at this suspension system:

The ServoBot's Suspension System

At the last minute I decided to make the demo using the touch-sensing face. So I made the robot take a step forward when you touch his eyes (yes, his eyes), turn left when you touch his left ear, and turn right when you touch his right ear. I did this in order to use as much hardware as possible. Judges like that.

Since I expected the robot to look like a paddling boatman, I intended to name it Charon.
The robot's movement ended up looking quite funny. After lots of coffee, it looked to me like the robot was proud to manage without DC motors. That's why I called it DC-Motor-Less, Yet Proud ServoBot.

So here's a video of my experience at the Make It Challenge:

I had a lot of fun participating in this challenge and I encourage everyone to put yourselves to the test on similar events. Chances are, you'll have fun too.

Although I didn't expect to win anything, I finally got the second prize. I know the judges liked my project despite being useless, because it was geeky and for most of it's features I had to wing it. Here's my robot with my prizes back home :)

My Robot and Prizes (Note the juicy debit card with the name "Especially for you")

Difficulties
I did have a lot of setbacks while making this robot such as availability of the right parts, time, etc (I had to attend several sessions and workshops during the conference, plus I had to eat and sleep!). My wife was very supportive, though :)

I also received tough news about 2 hours before judging: RobotSee wasn't yet ready to drive more than 4 servos, although the board has 8 servo connectors. I asked Eric Gregori if there was an easy way of driving more servos through RobotSee, but the answer was no. I intended to quit using one of the servos, the one that lifts the paddle, and came up with a mechanical one-way rubber wheel at the end of the paddle.
Once the panic was gone, a much simpler solution came to me: The two servos that lift the robot can be driven by the same signal, seen as one big logical servo in my code. So I got to use both servos. The attempt for a one-way wheel mechanism is still visible in the paddle. I left this rubber wheel static in the end.

The slippery gears I misused to support the robot were also a lot of trouble. That's why I limited my robot to the realm of carpets. I used a rubber band that came with a Freescale T-Shirt to wrap around the turning gear for friction. Take a look:

Rubber band and one-way wheel 

I must admit that during the thinking part of the challenge, I was facing the biggest obstacle of all: Myself. Since I don't have as much experience in mechanics as I do in electronics, I felt very challenged and didn't believe in myself, but then I said "Shame on you, Robotics Teacher!", and then I got to work.

If you're interested in the code, you can download it from here. The mechanics might get tricky :/ Contact me if you're interested.