Skip to contentSkip to author details

Solving the Stable Marriage problem on an FPGA (Part 1)

Written by Michael Earls
 Mathematics  FPGA  programming

At my last client, there was an issue that came up that required matching between two groups. It had to be a fair matching based on preferences of both sides. I first started by writing my own algorithm, but I quickly realized that someone has to have come up with something to do this already. I was right. Not only had someone(s) figured the problem out, they received a Nobel Prize for their work (good thing I didn't try to tackle it on my own).

Note: Blog title image used without permission (pending) from numberphile.com

Series entries:

The algorithm is named after the two mathematicians who discovered it: the Gale–Shapley algorithm, or commonly called the Stable Marriage Problem (or stable matching problem - SMP). I'll let you read about it on Wikipedia as I don't just want to repeat what's already there. Basically, it's also used in the National Resident Matching Program to help match medical students to residency programs, so it has real-world applications beyond the classroom.

Here is a great video describing the algorithm in layman's terms:

And for some deeper math, here is the follow-up to that video:

I became obsessed with this algorithm while working with the client because they had some unique ways of determining preferences beyond just saying "I like guy 2". There had to be more to it. "I like guy 2 because...".

My work obsession happened to coincide with my home obsession of learning how to utilize and develop on FPGAs. Again, I'll let you read the details, but the best way to describe an FPGA (compared to a microcontroller like the Arduino or Raspberry Pi) is as follows (I read this somewhere on the Internet and it stuck in my head):

  • You tell a microcontroller what to do.
  • You tell an FPGA what to be

There's a nuance there that has enormous implications on the differences between the two. FPGAs are much faster than microcontrollers because all of the logic runs in parallel, whereas a microcontroller has to run a program in a tight loop and constantly check and update the status of its IO pins. Every time you add a new task to a microcontroller's program, you slow it down.

Here is a video from Microsoft's Channel 9 discussing research they are doing on using FPGAs in the data center (Bing specifically) to increase performance and save energy:

Since the SMB algorithm can be so processor-intensive, I thought it might be cool to implement it on FPGA hardware to see if I can pull it off.

To keep things simpler for me, my initial approach is only going to deal with 8 total people: 4 women, and 4 suitors. I will take the "women propose" approach as discussed in the video above.

Next: Establishing the preferences...