Matchy

Matchy in action

If you have any experience designing the layout of analog integrated circuits, chances are you have spent hours of your life trying to balance devices on a grid. There has to be a better way, right?

I decided to give it a go and spent some hours building Matchy, a Python tool to automate this flow.

First comes a a brief overview of Matchy, its capabilities, and finally some reflections on the process.

If you would like to refresh your knowledge about layout matching, feel free to check out my Introduction to Matching.

Table of Contents

Usage

This section assumes that you have installed matchy. For this, you will need a working installation of Python 3.8 (or newer) with pip enabled and run pip install matchy in your terminal.

Getting started

Matchy comes with sensible defaults and an interactive command line interface.

You can just invoke it in your terminal with matchy and answer its prompts. It will display the results after you have given it enough information and it will offer to save the matrix in CSV format.

$ matchy
Number of devices: 3
Multiplicity for device A: 3
Multiplicity for device B: 3
Multiplicity for device C: 3

Would you like to manually enter matrix dimensions? (defaults to square) [y/N]: 


┌───────┐
│ B C A │
│ C A B │
│ A B C │
└───────┘

┌────────────┬────────────┬────────────┬────────────┐
│      names │ centroid_x │ centroid_y │      error │
├────────────┼────────────┼────────────┼────────────┤
│          A │        0.0 │       -0.0 │        0.0 │
├┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┤
│          B │        0.0 │       -0.0 │        0.0 │
├┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┤
│          C │        0.0 │       -0.0 │        0.0 │
├┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┤
│      total │        nan │        nan │        0.0 │
└────────────┴────────────┴────────────┴────────────┘

Would you like to save the matrix to a .csv file? [y/N]:

Exploring matchy’s potential

The behavior of matchy can be changed with flags and command line arguments, including setting the optimization algorithm, changing the output matrix dimensions, and specifying CSV input and output paths.

You can view all the options by calling matchy with the --help flag.

$ matchy --help
Usage: matchy [OPTIONS]

  Matching for IC devices.

  Usage: `matchy -n 3 -m 2 -m 3 -m 1`

  This will match 3 devices, the first of which has m=2, the second has m=3,
  the third has m=1.

Options:
  -n INTEGER RANGE                Number of different devices to be matched.
  -m INTEGER RANGE                Multiplicity of each device.
  --mat_height INTEGER RANGE      Height for the final matching matrix
  --mat_width INTEGER RANGE       Width for the final matching matrix
  --method [random|hill_climbing|random_hill|do_nothing]
                                  Method to find the optimal matrix.
  --initial PATH                  File to load the initial matrix guess.
  --output PATH                   File to save the resulting matrix.
  --help                          Show this message and exit.

Just for checking

Another common problem in matching is measuring the quality of your design, which is usually done by comparing the centroid of all devices. This is easy for small designs, but it quickly becomes cumbersome and impractical for larger arrays.

Many engineers tackle this problem with spreadsheets, which offer good flexibility, but working with formulas and conditional formatting takes time and is not easy to automate. In addition, spreadsheet editors tend to be large and resource heavy programs that you needn’t be constantly running.

Matchy aims to tackle this problem by leveraging its built in optimization metrics to evaluate existing devices matrices given in CSV format.

For example, if you have an initial guess for your matrix that you have designed, you can store it in an initial.csv file looking like this:

A,A,C
B,C,B
C,A,B

And call matchy with the --initial and --method do_nothing arguments.

matchy --initial initial.csv --method do_nothing


┌───────┐
│ A A C │
│ B C B │
│ C A B │
└───────┘

┌────────────┬────────────┬────────────┬────────────┐
│      names │ centroid_x │ centroid_y │      error │
├────────────┼────────────┼────────────┼────────────┤
│          A │     -0.333 │      0.333 │      0.471 │
├┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┤
│          B │      0.333 │     -0.333 │      0.471 │
├┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┤
│          C │        0.0 │       -0.0 │        0.0 │
├┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┼┈┈┈┈┈┈┈┈┈┈┈┈┤
│      total │        nan │        nan │      0.667 │
└────────────┴────────────┴────────────┴────────────┘

Would you like to save the matrix to a .csv file? [y/N]: 

As you can see, matchy has detected that device A and B are slightly off-center whereas device C has its centroid in the center.

Matching Metric

Matchy calculates the quality of the matching in a device matrix by measuring the difference between each device centroid and the center of the matrix in the rows and columns direction. For each device, it gives a single error metric as the euclidean distance between its centroid and the matrix centroid, and a global error metric as the L2 norm of the error in all devices.

Dummy devices (if needed to fill a matrix) are not included in the error calculation.

Algorithms

My first attempt at solving the problem is what I would call “the naïve approach”: get all the target devices and matrix dimensions as inputs and compute all possible combinations.

The problem is that the computation resources required grow exponentially with the number of devices, so it becomes impractical very quickly.

This led me to the conclusion that it was necessary for Matchy to implement different algorithms that approximate the optimal solution.

After the naïve approach didn’t work, the first iteration was to include random search, a well known and very simple method to deal with non-differentiable problems in a high dimensional space.

The implementation is extremely simple, it involves shuffling the matrix a set number of times and keeping the best results.

Random search algorithm.

The problem, as you may imagine, is that it’s not very optimal. It can take a big number of iterations to find better results, most of which are instantly discarded.

Hill Climbing

Because random search proved to be very slow, I set out to find an algorithm with the ability to converge to an optimal.

Inspired by the hill climbing algorithm, I implemented a matching algorithm that given an initial guess it traverses the matrix, and swaps each element with its adjacent elements. If the resulting swapped matrix is better than the previous one, the change is kept in a greedy fashion.

This algorithm is run until no more changes of adjacent transistors decrease the overall error.

Hill climbing search algorithm.

This method proved to be much more effective than random search, but it had a big shortcoming: local optima.

Depending on its initial conditions, the matrix could be stuck in a local optima and the optimization is stopped early with unsatisfactory results.

Random Hill

Combining the experience from the two previous algorithms, a third algorithm (known as random-restart hill climbing) was implemented to try and get the best of both worlds.

In this algorithm, the matrix is randomly sorted a set number of times and each one of these random starting points are optimized with hill climbing.

This method is more robust to local optima since the different random starting points are less likely to get stuck at the same place.

Random hill algorithm.

This algorithm was chosen as the default for matchy.

Conclusions

Matching is a very complex mathematical problem. CPU and memory requirements scale exponentially with the matrix dimensions, which makes it impractical to completely solve for arbitrary dimensions.

However, most designs in analog integrated circuit are not arbitrarily long, even very complex designs for a human can be resolved by tools like matchy in seconds or minutes with a common laptop, thus making development times shorter.

I introduced matchy to a few of my colleagues who kindly offered to test it. Their feedback was very positive for calculating centroids and metrics, but a recurring complaint was that the optimized results do not take into account easy of routing. This is a challenge to be addressed in future versions of matchy.

Fabián Torres
Fabián Torres
ECE Master’s student

My interests include integrated circuits, machine learning, and hardware acceleration.

Related