This is going to be a gentle introduction, which is good for me, who doesn't know a lot about chips and integrated circuits, to place and root algorithms for digitally integrated circuits.
The focus is going to be algorithms for global placement, and also globally used rooting algorithms for how to place circuits in the integrated circuits.
Thomas got his interest in the subject from the electronics corner of the local recycling center, where he was trying to find out how to build digitally integrated circuits, and understanding how proprietary software used to create the chips and circuits.
And since there was not any lectures on this at his university, he tried to figure it out himself.
So please come in, find a seat.
If you see somebody looking for a seat, put up your hand to indicate where the seats are.
And then, most importantly, for the next 30 seconds or so, give a warm round of applause for Thomas.
Thank you for the introduction. Good morning, everyone.
As I said, I will talk about place and route algorithms that are used for digital integrated circuits on silicon.
So what is that? I'm sure you've seen those. And maybe some of you have wondered what's inside.
I've wondered very often.
And when you don't really have much of special equipment, you can still have a look at what's inside.
And there's a really brutal method how to do it.
You take your blowtorch, you heat this epoxy case, and eventually the epoxy thing will crumble away and make some ugly fumes that don't do it inside.
And if you have a cheap microscope, you can see something like this.
That's actually the silicon chip. It's much smaller than the package.
It's only a couple of millimeters. And what you see on this is...
There's lots of different circuits.
And the thing marked in green is what is supposed to be a digital circuit.
I don't really know for sure for this one.
And this is exactly the thing that I want to talk about today, or how to create it.
So I'm going to focus on place and route algorithms.
That's somehow part of what I would call a digital circuit.
I would call it a type of compiler for silicon circuits.
And I will focus on how this compiler works, and I will not tell you today how to use it.
That's somehow another topic. Most of these chips are proprietary. There's no big news.
I heard people saying that we know that there's Intel inside, but what is inside Intel?
We don't know. Sorry. We don't know so well. There's lots of obscurity in proprietary chips.
There's sometimes missing documentation, incomplete documentation.
We rely on proprietary firmware because we don't have the full documentation.
Then we can ask ourselves, do we have, for instance, this for free DOMs that we use for free software?
Do we have this for chips? Can we use chips for whatever we want? Can we study them?
Probably not so well. Can we share them? To some limited extent. Can we improve them?
Probably not. It's really difficult because we don't know how they work in there.
So can we create open source chips which are completely open, down to the layout, down to this geometrical representation that tells the factory how to produce them?
The answer is yes, we can do it. But there's certain stones in our way.
People who do digital circuits usually cannot really get around certain types of software, the ETA software, Electronic Design Automation, and there's roughly three vendors worldwide which have some sort of monopoly on this software, and they set rules.
When you want to use this software, you have to sometimes sign NDAs, there's restrictive license agreements.
They basically don't allow you to publish the output. They don't allow you to publish the output.
It's a bit like you would write a text in Microsoft Word, and you would not be allowed to publish the text because it could somehow leak information about how grammar correction works.
Then there's another difficulty that's related to the factories, to the fabs who create the chips.
There's usually NDAs involved because you need to get access to information what they can produce.
How you have to design your chips. That they can correctly produce it.
This blocks you from publishing, for instance, the layout of your chip.
Now, it would be great to have some free and open source tool chain to create those chips.
It would help a lot.
It would also help us, for instance, to try new ideas because we could modify and extend this tool chain.
We cannot do this with commercial software. It's also much more accessible. It's much easier.
Because the software of these major three vendors, it's hard to get.
So if you're a small entity, it's probably difficult to even get access.
And free and open source tool chain would also be really helpful for education because it could actually show students how things work inside.
So why do we care now about this? Recently, there were many things happening in the field.
For example, it started with the U.S. foundries called SkyGuarder.
They opened their process design kit.
So they published this information that you need to create a chip with them.
They published it open source. And that's one of the first foundries that did that.
That attracted lots of interest. There was soon Google and DARPA on the project.
Then there is a project in the U.S. called the Open Drought Project.
It's basically a free software place and drought tool chain.
Then recently there was a German fab doing something similar.
They started opening their process design kit.
So this allows basically everybody to have a look at it and create chips for this foundry.
Then the European Union is drafting a new project.
I think the Chips Act, that's another big topic, probably would be worth a full talk itself.
That's not my personal opinion, but I have the feeling that tech ventures get more and more restrictive.
It's harder to understand the technology. So I think it would be time to have alternatives.
Let's have a look at how people usually do digital circuits.
You often start from a high-level description and a harder description.
That's kind of your source code, and you want to turn this into a chip in the end.
For that, you need a foundry who produces the chip.
The foundry wants from you a layout, that's basically a vector graphic representation of your circuit.
They also want money.
They give to you the design rules, so basically to tell you what kind of structures they can fabricate.
For instance, how tiny the transistors are. How thick the wires need to be.
When you have these design rules, you can create standard cells, so-called cell libraries.
That's a collection of logic gates that you can use in your digital circuit.
Then based from that, you can compile your source code into a circuit.
That's called logic synthesis. You get a netlist. That's basically like a text representation.
Okay. That's the representation of a circuit, and now there's a big piece missing.
That's the place and drought toolchains, which basically take this netlist, they take the information from the foundry, the design rules, they take standard cells, and they assemble it into a circuit representation that can actually be sent to the factory for fabrication.
A quick recap of digital circuits. They're built from logic gates.
They implement small Boolean functions.
That's for instance inverters, AND gates, OR gates, NAND, XOR, and many more.
Here is a picture of how such a gate looks inside schematically. It's built from transistors.
Here on the right, for instance, is an inverter.
Now, it's not so important for this talk to understand in detail how this works.
It's just more general.
As a reminder, if you've seen it already before, then we need storage elements that can be, for example, flip flops.
Flip flops, they sample the input signal when the clock edge arrives, and they transfer it to the output and then hold it there.
And once we have those logic gates, we can assemble them to big circuits, like CPUs or whatever.
And in practice, this can be really many, like up to millions.
And when you do this place-and-drought step, you get vector graphic representation.
And when you look at this, it's very hard to understand what it should be.
For instance, the picture on the right is maybe 6,000 cells together with wires.
When you zoom in, you start seeing a bit more structure. You recognize that. Yeah.
arranged on rows you see some patterns that seem to be repeating and that's this logic
cells and two dimensions is kind of hard to understand at first glance what it means so
if you look at it in three dimensions it's a bit more intuitive here you can see again
see this row based structure so those gates are really placed in rows and in between there's
those lines that's the power stripes that's part of the power distribution network then on top you
would add the the wires which connect to the gates and are not displayed that you can actually see
them so maybe you already know silicon chips they're constructed layer by layer you start
on the lower side with the silicon that's very good
you can see that you can create the transistors by adding doping and polysilicon for the gates
that's not so important for place and drought you can try to abstract that or this much more
important as the layers above that's the metal layers which you use for electrical connectivity
so that's usually multiple metal layers and there's via layers in between where you can connect
between two metal layers now what you see here is such a logic gate
it's done cell it's actually invert it as one of the simplest cells you can build is made of two
transistors here under left you see the schematic representation and the middle you see the 2d
representation that's usually what chip designers have on their screen but i find it kind of hard to
understand from first glance how it what it actually presents therefore here on the right
see more or less a one-to-one mapping between the schematic and the layout. For instance,
you can see both transistors, you can see the wires, the pins, and the pins is where
you connect to the gate in the end. Standard cells can be much larger and more complicated.
This, for example, is a flip-flop, one-bit storage. For Place and Route, we like to simplify
this a bit. We don't care so much about transistors below. What is important for us is the metal
layers and the pins because we need to know where to connect the wires.
Let's get to Place and Route. What we need to do first is we have thousands or millions
of components. We need to decide where to connect them.
Where to place them on the chip. Then we need to distribute the clock to, for instance,
the flip-flops. We will not talk about this today. I will talk about how we can connect
displaced cells. Afterwards, usually people try to verify the timing or try to fix the
circuit when timing requirements are not met. I will not talk about this today either.
They will also
and talk about verification which is actually really important because you want to make
sure that what you just built is what you wanted. So placement.
You need to find good positions for all the components on the chip. What does it mean good?
Usually we want to optimise certain things, for instance the wire length because the wire
length will be important for how your circuit performs, how fast you can run the clock,
but it's also important for routing.
The shorter the wires are, the easier it is to route the circuit. There's certain constraints.
For example, the obvious one, the components cannot overlap, and you also want to make
sure that the routing is feasible.
So you don't want to create situations where you would need to pass too many wires somewhere
which is not possible. It's really useful to break the problem down into multiple steps.
Usually what people do is they start with so-called global placement.
This is all about finding approximate locations for the cells.
You can relax the design rules, for example, you can say it's fine if some components overlap.
As long as the overall density is nicely distributed.
And then once you have this, you can go into something that people call legalisation.
So you try to snap the cells to legal positions.
Usually a grid, for instance, those are given by the structure of the power grid.
You need to snap the cells there.
And then you can also do some smaller optimisations like flipping or rotating the cells.
In a way that simplifies, for instance, the routing or shortens the wire links.
Here's an example of such an algorithm for global placement.
And the basic idea is we want to place connected components close together.
So we imagine that we connect them with springs. Mechanical springs.
And the springs, they would pull together components which are electrically connected.
Now we simulate how those connected cells will move and where they would go.
And while we do this, we for now completely ignore overlaps.
That's fine if those cells, they somehow lie on top of each other. And what this method does.
Is it minimises the squared wire links. This is where the name quadratic placement comes from.
And this type of algorithm is so-called analytic placement.
It's mathematically nice because you basically minimise a cost function.
And you compute for each of the components how a tiny shift in position will have an
effect on the cost function. And you move all the components in a way.
To decrease the cost function. And that's called gradient descent.
The problem with this approach is that it leads to really high overlap.
So many cells will lie on top of each other.
If you look at an example of a couple thousand cells, you see that there's this black cloud
where you have tons of cells on top of each other. And we can't use that.
So we need to somehow spread the cells. To move away from each other.
And the idea is to add another force which repulses the cells.
And what you can do is we can actually simulate charged particles which are connected with
springs. Because electrical charges, they repulse each other.
The cells will try to not be on top of each other but go away from each other.
And this way we can effectively reduce the overlap.
This is an approach used by an algorithm called ePlace, which is widely used in, for
instance, this open road tool chain.
I think it's also used in industrial tool chains, but we don't really know for sure.
So let's have a look at what is the effect of adding this repulsion.
Here on the very left, there's a circuit placed with a quadratic placement.
You see lots of overlap. It's very dense.
Then when we add the repulsive force, you see in the middle how the cells start spreading
until on the right, they actually reach the density constraints and there's almost no
overlap anymore. Once we have this, we can continue connecting the components.
And this is done in the routing step. Okay.
So the goal of routing is to do electrical connections, and we have to do them correctly so we don't want short circuits, we don't want missing connections, and there are certain constraints.
The constraints are basically given from the fabrication process, we have certain types of metal layers that you can use, there are design rules.
The design rules, for instance, tell us how close wires can be together, or how thick they need to be in order to be properly fabricated.
There's some other funny design rules, like antenna rules, but I'll not talk about those.
Often it's good to route special nets separately, so there's certain nets that go to many, many cells, for instance, ground and the supply network.
They basically go to all the cells, that's why we need to make a regular grid.
Then another net which goes to many cells is the clock net, it goes to all the flip-flops.
It's also good to do this in a separate step, and that's called clock tree synthesis, I'll also talk about this.
Speaking of images, what we have before we need to route the circuit is a couple of steps.
We have cells which are placed on a chip, we know how they're connected, but we don't yet know where the wires exactly go, as shown here are these orange lines, and on the right is what we want.
We want nice drawn wires which adhere to the design rules.
There's an important concept for routing, it's called MACE routing, if you know Dijkstra's algorithm for shortest path search.
It's called MACE. If you remember the Bellman-Ford algorithm, you know the concept.
And the concept is that we move on the graph, we have a source node, destination node, we want to go from the source node here marked as green to the destination, we maybe have some obstacles where we cannot go through, like this grey box.
And the idea is that we propagate a wavefront from the source, and with each step we remember where we need to go back to the source, and as soon as we reach the destination, we can trace back and find the shortest path to the source.
Now also the routing problem is good to break it down into multiple steps, and often what people do is they do first global routing, where you find approximate routes, and during this step you can relax the data.
You can design rules, you can kind of forget about them, and what you try is also to solve congestion, so you try to push signals away from regions which are heavily used.
And this way you can then simplify the so-called detail routing, where we draw the final wires, and in this way we find the global routes to actual wires.
And in detail routing, we have the following.
We have to respect the design rules, so we need to be aware of this minimum distance that we have to keep not to create short circuits.
Now let's look at global routing.
So you start with a circuit which is placed on the chip, you know the positions of the cells, you want to find approximate routes, and a good approach is to slice this area into tiles.
And now you have to find approximate routes.
And now you say that you basically try to find routes that cover the whole tile.
So for example here, you want to find, or you want to connect a cell which is located somewhere here, I have my MOS pointer to a cell which is somewhere here, and you find out that it goes somehow through those tiles.
But you don't know, and you don't care so much how exactly it will go there.
So let's do an example.
We want to connect those colorful shapes with each other, and what we know is that between those tiles there is a certain capacity, for example you can pass at most two wires.
Then some tiles might be blocked by an obstacle, so we cannot pass any wires, and we have to go around them.
One algorithm that's called Pathfinder algorithm, it's also used in FPGAs, has the approach that we just try to route all the nets, then we try to see if there's problems.
For example, if you route those three nets, we might end up passing three nets through this tile, and the problem is we can only pass two.
And what you can do is we can increase the cost through this tile, so if you're lucky, eventually.
Eventually one signal will decide to go somewhere else, and in this way resolves the congestion.
Once we have these global routes, we can use them to steer the path search for the detail routing.
So they basically mark a region where the final wires can go through. Okay.
What you can do once you have the global routes is that you do another refinement step.
So for example, you can convert to the global routes into thin lines, like skeleton lines, and try to arrange these lines that there's minimal amount of overlap, and these lines they're already quite close to the actual routes.
But there might be gaps, maybe there's still some conflicts.
Once you have those lines, you can use them to steer maze routing.
So they really narrow down the path search, and you can fill the gaps using maze routing.
And if you do this, you end up with final wires.
Maybe you have to check for design rule violations, maybe you somewhere got too close to other wires, and you may have to fix it.
If you apply this to a bigger circuit, that's how it looks like, you've already seen it.
It's hard to somehow really see through what happens there, but that's how it looks.
So once this is done, you might still want to make use, for instance, of empty space.
What people usually do is... They fix it.
They fill empty space with capacitors, and this helps, for instance, to stabilize the power supply.
So if you want to know more about this topic, there's a good book.
There's also a conference which is devoted to this topic. It's usually in Paris.
In summer, I don't know the date yet, but I will be involved in organizing it.
It's the Free Silicon Conference, so if you're interested, maybe check it out.
As already mentioned, there's the Open Road Project, which is a collection of open source tools for placing drought, and also some tools for verification of the timing.
There is a quite old open source project for placing drought. It's called Coriolis.
It's developed in Paris at Sorbonne University.
I just recently discovered another placing drought project. It's called Luna PNR.
Sounds really interesting.
I don't know much about it, but if you want to have a look at some code and how this is done, it might be a good start.
Personally, I also work on a project that's called Libre EDA.
It's very similar, basically trying to implement placing drought algorithms.
If you like Rust, that's maybe also fun. Thank you. Good. Thank you very much for listening.
If you have questions, that's the time now. You can also send me a mail later as you want.
But before you start sending emails and reading books and going to conferences, you should line up behind the microphones in the room if you have questions to Thomas.
And also, on the internet, there is also possibilities of asking questions, and we will read them out, one of the speaker heralds.
We already have three volunteers for questions over here on the left side for me, the front mic.
So, could we have the mic put on, and you can ask a question. Hello. Okay.
So, with this brilliant picture that you have here, and as an example from the previous slides.
So, it has this couple of island regions. Why they are there? How they are? Yeah.
So, how this looks, it really depends on the algorithm used to decide where to place the cells.
And usually, you recognize some sort of blobs, and sometimes you can also see it in this big blob.
And sometimes there's a spot like tinier blobs, and this is usually circuits or kind of sub-circuits, which are those cells under each other, they're much more connected among themselves than to the rest.
So, are they, is it a result of some external constraint for the algorithm, or is it something that the algorithm does by itself?
No, it's kind of something that just happens if you, like I said, you simulate this network of springs.
So, springs and electric repulsion, and that's something that just pops out, and seems to be some optimum.
Fascinating. Thank you. Thank you very much for the question.
Next question in the room, and then we also have a question from the internet. Yeah.
My question is, you said that when doing global routing, you can ignore the design rules.
Can you elaborate on that? Because I actually didn't get that at all. Yeah.
So, I mean, you can somewhat relax the design rules.
The design rules, they tell you, for instance, what needs to be the minimum distance between two metal shapes, and if you want to respect that, it's actually, you need to do lots of checks.
So, it's computationally really hard to always make sure that everything works out, and now, the way you relax it is you say, I know how big the wires should be, I know how much distance they should have, and I kind of summarise it in this capacity between two tiles.
So, from the size of the wire, you can say that, okay, between two tiles, I can have ten wires at most.
And basically, that's how you simplify it. Does it answer your question? Yeah.
In this sense, you don't completely ignore it, but you try to kind of abstract it, and you don't want to make checks for actual design rule violations during global routing.
Yeah. Probably got it wrong, because maybe you said relax and not ignore. Yeah. Good.
We have a question from the internet, possibly more, and if you have questions, please line up behind one of the mics.
So, Signal Angel, could you please read out the question from the internet? Yeah.
The internet wants to know if parts of PNR are done for the FPGAs by the next PNR project, if they are applicable for ASICs or the other way around.
I didn't completely understand the question.
The question is, there is PNR work done with next PNR for FPGAs.
If parts of it are applicable also for ASICs or the other way around, so ASIC software being useful for FPGA.
Okay. I'm not so much into FPGA toolchains, but there's really some differences.
For instance, on the FPGA, basically all the components are already placed, and what you can change is the routing.
For instance, then I imagine that the placement algorithms, they're somewhat different.
I know that for the routing, FPGA toolchains use a similar way to the results.
They solve congestion, like this path finder algorithm, but there's some similarity here.
If you look at the steps before placing routing, the logic synthesis, I think that there's more overlaps, and I think people already use tools for FPGA design also for ASICs, like for synthesis.
Good.
And if any of you sitting down have questions, please don't hesitate to get up and stand behind a mic.
We have one more question. Yeah.
So, again, this comes from the background of FPGA, from YOSIS and Next PNR, this is what I have used.
So these open source alternatives to, let's say, Vivado and all, are YOSIS and Next PNR, right?
I just want to understand in that context, maybe it also applies to ASIC, is that now I see one of the connected circuit in that green island, and one of the other electrical connection is in the main.
Okay. So, what is the consequence of that? So, what is ultimately the consequence of that?
Will I have some timing latency in my circuit in that logical path?
What is the, let's say, how do I make sure that if it's not there, it's in part of this main island, how is my circuit better?
Will I have reduced timing latency? Will they will be good?
How does I make sure as a layman, how do I understand, okay, placing and routing happened?
What happened is a better... Placement, or let's say it was not that efficient.
So how can I make sure that you don't have time latency?
So timing, intuitively, you see that long wires might have more like delay. That's correct.
But often what you try to minimize is, for instance, the...
The quadratic wire lengths, or like the half perimeter wire lengths, and now it can be that...
So there's also...
For instance, there's other things on the left that we now don't see, like the pins or paths, and now it could be that actually shifting this whole blob towards there, even though we make those lines a bit longer, still minimizes the wire lengths because there's more wires going to the other side.
But ultimately, we are trying to minimize the wire length to reduce timing latency.
That is what we are trying to do. Yes and no. Because for timing, it gets more complicated.
So tendentially, it's better to have short wires for timing, but not all wires matter the same.
So a wire might be on a path where you have lots of time available. And this wire...
It will not matter much, so you can make it much longer without a problem.
And then there's other wires which are kind of a critical path where timing is tight and you need to make them much shorter.
So you can also make those trade-offs. Thank you. Good.
It seems like we have our final question, but if any of you want to ask a question, we still have time to answer at least two more questions.
So please go ahead from the microphone.
Coming from the circuit board designs, they, I think, in layers for a ground plane, all these planes on.
Is there some kind of notion when routing here? So the planes? Yeah.
You don't really have planes, but what you do is this grid.
So the grid is in some sort your plane, but you make holes in between.
Because you cannot do a plane because, well, maybe you could do it, but people don't do it.
I think there's other things that limit yourself.
Because there's some restrictions on density and you actually want to use also the space for signals.
So it's better to have the grid where you can also between pass wires for signals. Excellent.
And we have one more question, at least in the room, and the signal angels will have to let me know if we have any more questions from the internet.
So please go ahead from the microphone.
So how common or doable is it to do manual optimizations to the placement or even routing?
Manual optimizations? I think it's not common at all for digital circuits.
I think for analog circuits, it's very different. There are people who do it usually manually.
But if you have so many cells, I think it's really hard.
Sometimes what I've seen is manual optimizations when you have design rule violations.
So maybe your tool chain does something which ends up with some wires getting a bit too close to each other or some corners of wires being too close to each other, and basically you can fix this manually.
Okay, thank you.
So I think this is all of the questions that we've had both in the room and from the internet.
Thomas, is there anything that people haven't asked you that you want to say, give an answer to?
At the moment, no. At the moment, no? Good.
Well, then everybody please give Thomas a warm round of applause. Thank you. Thank you. Thank you.
Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you.