autorouting-dataset

view online · blog · discord · tscircuit

A dataset of autorouting problems for benchmarking 🥇, plus a ton of utilities 🔨 including a viewer and testing server for developing new autorouting algorithms.

Autorouting is the process of drawing traces (wires) to connect chips on a PCB. It is a decades-old largely unsolved problem.

• autorouting-dataset
  • What is autorouting?
  • Problems
    • Example Problems
      • simple-multi-point-trace
  • Benchmarks
  • Usage
  • Writing a Solver
    • Typescript Solvers
    • Non-Typescript Solvers
  • Visualizing Problems/Solutions
    • Running a Dev Server with Typescript
  • Running a Benchmark
    • Running Benchmarks with Typescript
    • Running Benchmarks without Typescript
  • CLI Usage
    • Installation
    • Starting Dev Servers
    • Running Benchmarks
      • Customizing Benchmarks
    • Generating Datasets
    • Generating Single Problems
  • Community Solvers
  • References

What is autorouting?

Autorouting is the drawing of traces (wires) across a 2d surface to connect copper pads together. Traces can go underneath pads using a copper-plated hole called a "via". Traces must also avoid "obstacles" which are other pads or blocked areas where a trace cannot pass such as a hole or region designated for an antenna.

Problems

There are different classifications of problems, each problem applies to a different autorouting scenario. A perfect autorouter can solve all of these problems, but partial autorouting is very useful for human-assisted routing.

Problem	Ready Status	Description	Difficulty
single-trace	🟢 view	Route a single trace through obstacles	Easy
traces	🟢 view	Route multiple traces to pairs of points, without crossing traces	Medium
distant-single-trace	🟢 view	Long (200mm+) single trace	Easy
single-trace-group	🔴 TBA	Route a single trace through multiple points	Easy
layers-traces	🔴 TBA	Route a trace through multiple layers to connect two points	Easy
traces-groups	🔴 TBA	Route multiple traces to groups of points, without crossing traces	Medium
layers-traces	🔴 TBA	Route multiple traces to pairs of points, without crossing traces across layers	Hard
layers-traces-groups	🔴 TBA	Route multiple traces, through multiple places, to groups of points, without crossing traces	Hard
width-constraints-*	🔴 TBA	Maintain the optimal trace widths, given target ranges for each trace	Hard
hyperdense-*	🔴 TBA	Super dense BGA routing	Hard+
incremental-*	🔴 TBA	The same dataset but a component is moved or a trace is changed. Tests cache efficiency	Hard+

Example Problems

simple-multi-point-trace

Benchmarks

There are several criteria we use for running benchmarks:

• Speed (machine specs TBD)
• Percent of Boards fully routed inside category
• Quality (as compared to "ideal routing")
  • How much longer are the traces? Shorter traces are usually better
  • How good is the trace width relative to the ideal routing
• Problem Type
• Incremental Speed (speed if a single component is moved or a trace is changed)
• Memory Usage

Over time, we'd like to have a simple 2d chart showing Speed and Quality.

Usage

This dataset is composed of thousands of files in the tscircuit soup format. You can find a dataset for each problem tscircuit in the datasets directory. You can download a zip file containing the datasets from the releases page. If your solver is in typescript, you can generate the datasets on the fly by importing autorouting-dataset

soup can be easily visualized and contains a lot of metadata that can be used for constraints. However, you may want to use the getSimpleRouteJson utility function from autorouting-dataset to convert it into a simple object with the following interface:

interface SimpleRouteJson {
  layerCount: number
  obstacles: Array<{
    type: "rect"
    center: { x: number; y: number }
    width: number
    height: number
  }>
  connections: Array<{
    name: string
    pointsToConnect: Array<{ x: number; y: number }>
  }>
  bounds: { minX: number; maxX: number; minY: number; maxY: number }
}

Each directory in the datasets directory contains a dataset for each problem. The code directory contains the code to generate datasets.

Writing a Solver

You can write a solver in any language you want, but currently most of the examples are in Typescript. You can read about building a "hello world" autorouter in this blog post.

Hate Javascript? Skip to building a non-typescript solver

Note

There are tons of examples of solvers inside the algos directory!

Typescript Solvers

Typescript solvers can accept either tscircuit soup or SimpleRouteJson. To develop your Typescript solver, just create a file like this:

import { startAutoroutingDevServer, getSimpleRouteJson } from "autorouting-dataset"

const mySolver = (soup: AnySoupElement[]) => {
  const routeJson = getSimpleRouteJson(soup)

  // ...

  // ...return one or more pcb_trace objects with our solution!
  return [
    {
      "type": "pcb_trace",
      "route": [
        {
          "route_type": "wire",
          "x": 3,
          "y": 1,
          "width": 5,
          "layer": "top"
        },
        {
          "route_type": "via",
          "x": 3,
          "y": 1,
          "from_layer": "top",
          "to_layer": "bottom"
        }
      ]
    }
  ]

startAutoroutingDevServer({
  solver: mySolver,
  port: 3080
})

You can then run this file with bun --hot ./solver-server.ts

Tip

Try it out with bun ./algos/tscircuit-builtin/server.ts

Note

We recommend putting the solver in a separate file then importing it inside your server file, this way you can easily export your solver as a library!

Non-Typescript Solvers

Tip

Check out a simple python autorouter

• Host a server with your algorithm (see the simple flask server below)
• Run npx autorouting-dataset server start --solver-url http://localhost:1234 (replace localhost:1234 with your solver server url
• To benchmark your solver, run npx autorouting-dataset benchmark --solver-url http://localhost:1234 see running benchmarks without typescript

from flask import Flask, request, jsonify
from autoroute import autoroute

app = Flask(__name__)

@app.route('/solve', methods=['POST'])
def solve():
    simple_route_json = request.json['simple_route_json']

    solution = autoroute(simple_route_json)

    return jsonify({
        "solution_soup": solution
    })

if __name__ == '__main__':
    app.run(host='0.0.0.0', port=1234)

The autorouting-dataset dev server will send a POST request to the provided url with the a JSON payload containing the following fields:

interface Payload {
  problem_soup: Array<AnySoupElement>
  simple_route_json: SimpleRouteJson
}

You must return a JSON array containing pcb_trace elements in the following format:

interface Response {
  solution_soup: Array<{
    type: "pcb_trace"
    route: Array<{
      route_type: "wire" | "via"
      x: number
      y: number
      width: number
      layer: string
    }>
  }>
}

Visualizing Problems/Solutions

You can visualization your algorithm against a sample using the dev server. To start the dev server, just run npx autorouting-dataset server start --solver-url <solver-url> and run your solver server.

When you're debugging your solver, you may want to insert additional elements into your solution_soup to help debug visually. To do this, just return elements in addition to or instead of the pcb_trace element. A full list of elements can be found in the tscircuit json format (soup).

One easy element you can add is a fabrication_note_path, which is shown in gray on the PCB viewer. Here's an example:

{
  "type": "pcb_fabrication_note_path",
  "layer": "top",
  "route": [
    {
      "x": "3mm",
      "y": "1mm"
    },
    {
      "x": "3mm",
      "y": "1mm"
    }
  ],
  "stroke_width": "0.1mm"
}

You could also add a pcb_fabrication_note_text to add helpful text annotations:

{
  "type": "pcb_fabrication_note_text",
  "font": "tscircuit2024",
  "font_size": "1mm",
  "text": "Hello, World!",
  "layer": "top",
  "anchor_position": {
    "x": "3mm",
    "y": "1mm"
  },
  "anchor_alignment": "top_left"
}

Running a Dev Server with Typescript

If you're using Typescript, you can run a dev server with the code below:

import { startDevServer } from "autorouting-dataset"
import { autoroute } from "./my-autorouter"

await startDevServer({
  solver: autoroute,
  solverName: "my-autorouter",
  port: 3080,
})

[!TIP] > export DEBUG=autorouting-dataset* will give you all the debug output including additional dropdown debug information

Tip

Check out this directory for a typical Typescript autorouter configuration

Running a Benchmark

Running Benchmarks with Typescript

If you have a Typescript solver, you can run a benchmark programmatically using:

import { runBenchmark } from "autorouting-dataset"
import mySolver from "./my-solver"

const result = await runBenchmark({
  solver: mySolver,
  verbose: true,
})

You can then just run your file with bun ./benchmark.ts

Tip

Try it out with bun ./algos/tscircuit-builtin/benchmark.ts

Running Benchmarks without Typescript

autorouting-dataset benchmark --solver-url http://localhost:1234

See the section on customizing benchmarks for more details on how to change the sample count, customize the problem type etc.

CLI Usage

You can use the CLI to generate datasets, run benchmarks, and start a dev server.

Installation

npm install -g autorouting-dataset

Starting Dev Servers

The dev server helps you visualize a dataset and will automatically send data to your solver to test it.

The dev server will start on port 3080 by default, after you start the dev server you can visit http://localhost:3080 to view the dev server.

# Start the dev server with the default grid-based solver
autorouting-dataset server start

# Start the dev server with a custom solver url
autorouting-dataset server start --solver-url http://localhost:1234

# You can send specify
autorouting-dataset server start --port 3080

Running Benchmarks

Runs a benchmark against a solver server. See running benchmarks without typescript for more details.

autorouting-dataset benchmark --solver-url http://localhost:1234

Customizing Benchmarks

Option	Flag	Description
sampleCount	--sample-count	Number of samples to run for each problem type
problemType	--problem-type	Problem type to run benchmarks for (default: all)
verbose	--verbose	Prints out more information
solverUrl	--solver-url	URL of the solver to benchmark
sampleSeed	--sample-seed	Seed to randomize sampling (default: 0)
noSkipping	--no-skipping	Disables skipping of problem types

By default, running a benchmark will run for 100 samples against all problem types.

If no problemType is provided and the solver fails on the first 10 samples, it will not run the remaining samples of the problem type. You can disable this behavior by setting noSkipping to true

The sample count can be changed with the --sample-count flag. For public evaluations the sample count should be set to at least 1,000.

Generating Datasets

autorouting-dataset generate-dataset --problem-type single-trace --output ./single-trace-problem-XXX.json

This command will generate a dataset of 100 problems (by default) for the specified problem type, saving each problem as a separate JSON file.

Generating Single Problems

To generate a single problem:

autorouting-dataset generate-problem --problem-type single-trace --seed 0 --output ./single-trace-problem-0.json

This command generates a single problem of the specified type with the given seed and saves it to the specified output file.

Community Solvers

Coming soon! Please create an issue to add your solver to this repo, we will be listing benchmarks etc.!

We are working on a dedicated test machine for measuring performance.

References

• Pathfinding Architecture Optimizations