Dear viewer, these subtitles were generated by a machine via the service YouTube and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/2723 Thanks!
[Music]
this is going to be a gent 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 roting
algorithms for how to place circuits on
um in the integrated
circuits Thomas uh 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
work and since there was not any uh
lectures on this at his university he
tried try 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 I said I will talk about place
and drout 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 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 blow torch you heat
this epoxy case and eventually the epoxy
thing will crumble away make some ugly
fumes so don't do it
inside and if you have a jeap microscope
you can see something like this so
that's actually the Silicon chip is much
smaller than the the package
sorry couple
millimet and what you see on this
is there's divers lots of different
circuit and the the thing marked in
green is what I 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
drought algorithms
that's somehow part of what I would call
a type of compiler for silicon
cirqus 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 chips are proprietary this
no big
news I heard people saying that we know
that there's Intel Insight but what is
inside
Intel we don't know so well there's lots
of obscurity in propriety chips there's
sometimes missing documentation
incomplete
documentation um we rely on proprietary
firmer because we don't have the full
documentation then we can ask ourselves
do we have for instance this free for
freedoms that we use from free software
do we have this for chips can we use the
chips for whatever you want can we study
them probably not so well can we share
them to some limited extent can we
improve them probably not that it's
really difficult because we don't know
how how they work in there
so can we create open source chips which
are completely open like down to the
layout down to this geometrical
representation who tells the factory how
to produce
them answer is yes we can do it um but
there's certain stones in our
way people who do digital circuits
usually cannot really get around certain
types of software ETA software
electronic design automation and there's
roughly three vendors worldwide which
have some sort of Monopoly on on this
software and they set
rules when you want to use this software
you have to sometimes sign ndas there's
restricted license agreements and they
basically don't allow you to publish the
output of of the software it's a bit
like you would write a text in Microsoft
Word and you would not be allowed to
publish the text because 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 ND involved because you need to
get access to information what they can
produce how you have to design your chip
that um they can correctly produce
it and this blocks you from from
publishing the for instance the the
layout of your
chip now it would be great to have some
free and open source tool chain to
create those chips with 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 because the software of this
major three
vendors it's hard to get so if you're
small small entity is probably difficult
to even get
access and free and open source tool CH
would also be really helpful for
Education because you could actually
show students how how things work
inside so why do we care now about this
so recently there were many things
happening in the
field for example started with a US
foundaries called skyer they opened
their process design 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
foundies that did that that attracted
lots of interest there was soon Google
and DARPA on the
project then there is a project in US
called the open road project is
basically a free free software plac in
drout 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 and create chips for for
this
Foundry then the European Union is
drafting the gips ACT that's another big
toping topic probably would be worth a
full Talk itself then that's somewhat my
personal opinion but I have the feeling
that Tech vendors get more more
restrictive is
harder to to understand the technology
so I think it would be time to have
Alternatives so let's have a look at how
people usually do digital
circuits you often start from a high
level description and a harder
description language that's kind of your
source code and you want to turn this
into a chip in the end and 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 and they give to you the design
rules so basically they tell you what
kind of structures they can
fabricate for instance how tiny the
transistors can be how thick the wires
need to
be and when you have this design rules
you can create standard cells soal cell
library that's a collection of logic
gates that 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 an nlist that's
basically a like a text representation
of a
circuit and now there's a big piece
missing that's the place in drout tool
chains which basically take this net
list they take the
information from the phone sign rules
they take standard cells and they
assemble it into a circuit
representation that can actually be sent
to the factory for
fabrication so quick recap of digital
circuits they're built from logic gates
they Implement small Boolean functions
that's for for instance inverters andt
Gates or Gates n xor and many more here
is a picture of
how such a gate looks inside
schematically this built from
transistors here on the right for
instance is a inverter now it's not so
important for this talk to understand in
detail how how thises work just more a
reminder if you have seen it already
before then we need storage elements
that can be for example
flipflops 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
Route step you get uh Vector graphic
representation and when you look at this
it it's very hard to understand what it
should be for instance the picture on 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 things are
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 to understand at first glance what
means so if you look at it in three
dimensions it's bit more
intuitive here you can see again see
this row based structures so this 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 the wires which connect to the gates
and not displayed that you can actually
see it
on so maybe you already know silicon
chips there
constructed layer by
layer you you start on the lower side
with the Silicon that's where you create
the
transistors by adding doping and
polysilicon fortigates
that's not so important for place in
drought we can of tried to obstruct that
what is more much more important is the
layers above that's the metal layers
which use for electrical connectivity so
that's usually multiple metal layers and
there's V layers in between where you
can connect between two metal
layers now what you see here is such a
logic gate a standard cell it's actually
inverted that's one of the simplest
cells you can build it's made of two
transistors here under the left you see
the schematic
representation in the middle you see the
2D
representation that's usually what what
chip designers have on on their screen
but I find it kind of hard to understand
from first clance how it what it
actually presents therefore here on the
right there's also a 3D repres
representation and you see more or less
a oneto one mapping
between the schematic and the layout for
instance you can see the both
transistors you can see the the
vires the 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 and for plac and rout we like to
simplify this a
bit so we don't care so much about
transistors below what's important for
us is the metal layers and the pins
because we need to know where to connect
the
virus so let's get to place and
drout what we need to do first is we
have this thousands or millions of
components we need to decide where to
place them on the
chip then we need to distribute the
clock to for instance to the flip-flops
we will not talk about this today I will
talk about how we then connect displaced
cells then afterwards usually people try
to verify thep timing or try to fix the
circuit when timing requirement are not
met I will not talk about this today
either and I will also talk about
verification which is actually really
important because you want to make sure
that what you just buildt is what you
wanted so
placement you need to find good
positions for all the components on the
Chip And what does mean good usually
want to optimize certain things for
instance the wire length because the the
wire length will be important on for how
you C with performs how fast you can run
the clock but it's also important for
routing the shorter deves are the the
easier it is to rout 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 need to pass too
many wires somewhere which is not
possible it's really useful to break the
problem down into multiple steps and
usually what people do is they start
with so-called Global
placement and this is all about finding
approximate locations for for the cells
so you can
relax the design for example you say
it's fine if some components overlap as
long as the overall density is is nicely
distributed and then once you have this
you
can go
into something people call legalization
so you try to snap to cells to Legal
positions usually have a grid for
instance those are given by by the
structure of the power grid you need to
snap the cells there and then you can
also do some smaller optimizations like
flipping or rotating the cells in a way
that simplifies forance the routing or
or shorten the
wirelength now 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 if the cells
they somehow lie on top of each other
and what what this method does is it
minimizes the squared wirelength this
where the the name quadratic placement
comes from and this type of algorithm is
so-called analytic placement um it's
mathematically nice because you have
basically minimize a cost function and
you compute for each of the
components how a tiny shift in position
will effect have an effect on the cost
function and you move the components in
a way to decrease the the cost function
and that's called gradient descent the
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 is 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 um 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 you can
actually simulate charged particles
which are connected with with springs
because electrical charges they repulse
each other the those 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 e 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 this very dense then when we
add the repulsive Force we 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 so the
goal of routing is to do electrical
connections and we have to do them
correctly so you don't want short
circuits you don't want missing
connections and there's certain
constraints the constraints are
basically given from the fabrication
process um we have certain types of
metal layers that you can use there's
design rules the design rules for
instance tell
us how um close wires can be together or
how thick the need to be in in order to
be properly fabricated there's some
other funny design rules like antenna
rules but I know not talk about
those
often it's good to to Route special Nets
separately so there's certain Nets that
go to many many cells for instance
ground and and the supply network they
basically go to all the cells that's why
we need to make a regular crit then
another Network and another net which
goes to many cells is the clock nut 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 also talk
about
this speaking in images what we have
before we need to Route the circuit is a
couple cells which are placed on the
chip we know how they're connected but
we don't yet know where the the virus
exactly go that's here shown is this
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 maze routing if you
know taust algorithm for shortest path
sech or um Belmont Ford algorithm you
know the
concept and the concept is that we we
move on a graph we have uh Source node
destination Noe we want to go from The
Source node here Mark the screen to the
destination we maybe have some obstacles
where you cannot go through with this
gray
box and the idea is that
we propagate away from wfront from the
source and with each step we remember
where we would need to to go back to the
source and as soon as we reach the
destination we can trace back and find
the shortest PA 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 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 in this way refine the the grow
Global routes to actual wires and in
detail routing 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 Globe broken
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 in into tiles and
now you say that you
basically try to find routes that cover
the whole tiles so for example here you
you want to find or you want to connect
a cell which is located somewhere here I
have my M 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 which each
other and what we know is that between
those tiles there's 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 pathf
alth is also used in fbj 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 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 one signal will decide to go
somewhere else and in this way resolves
the
congestion once we have this Global
routes we can use them to to steer the
pass search for the detail
routing so they basically Mark a region
where the final wires can go
through 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 in Into
Thin lines like skeleton lines and try
to arrange this lines that there there's
minimal amount of
overlap and these lines they're already
quite close to the 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 pass search
and you can fill the gaps using maze
[Music]
roing
and if you do this you end up with final
wires maybe you have to check for design
rule violations maybe you some somewhere
got too close to other VAR and you might
have may have to fix
it if you apply this to a bigger circuit
that's how it looks like you already
seen it um it's hard to somehow really
see through what what happens there but
that's how it
looks
so once this is
done you may still want to make use for
instance of empty space what people
usually do
is they fill empty space with
capacitors and this helps for instance
to to stabilize the 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 in Paris in summer
I don't know the the date yet but I've
been involved in in organizing it it's a
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 place and drout and also some tools
for a verification of the
timing there is a quite old open source
project for place and drought it's
called coriolis it's developed in in
Paris at sbon
University I just recently discovered
another place in drout 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
some code and how how this is done might
be a good start personally I also work
on a project is called Libra Eda it's
very similar basically trying to
implement place and drout algorithms if
you like rust that's maybe also
fun good so 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 uh
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 uh the front mic so could we have the
mic put on and you can ask a question
okay so uh with This brilliant picture
that you have here uh 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 on the
algorithm you use to decide where to
where to place the cells and usually you
recognize some sort of
blops
and sometimes you can also see
it
and and like in this big bloing and
sometimes those spot like tinier
blobs and this is usually circuits or
kind of subcircuits 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 algorithm does
about itself no kind of something that
just happens if you like I said you you
simulate this network of of of Springs
and electric
repulsion and that's something that just
pops out and seems to be some some
Optimum yeah 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 uh yeah um my question is you
said that when doing Global routing um
you can ignore the design rules can you
elaborate on that because I actually
didn't get that at all yeah so
I you can somewhat relax the design
rules so the design rules they tell you
for instance um what what needs to be
the minimal 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
to always make sure that everything
works
out and now the way you relax it is you
say I know how the how big the wire
should be I know how how much distance
they should have and I kind of summarize
it in this capacity between two
tiles so from from the size of the wire
you can say that okay between two tiles
I can have 10 wires at
most and basically that's how you
simplify it
does it answer your
question in this sense you don't
completely ignore it but you try to kind
of abstract it and you you don't want to
to make checks for for actual design
rule violations during Global rout 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 so signal Angel could you
please read out the question from the
internet yeah the internet wants to know
if parts of PNR Dawn for the fpgs by the
next PNR project if they are applicable
for A6 or the other way around I didn't
completely understand the the question
question is there is PNR work done with
um next PNR for fpj if parts of it are
applicable for also for as6 or the other
way around so as6 software being useful
for fpga okay yeah um
I'm not so much into fpga tool CHS but
there's some there's really some diff
differences
um for inst on the fpj basically all the
components are already placed and what
what you can change is is the
routing for instance then I imagine that
the placement algorithms there somewhat
different I know that for for the
routing fpta tool chains use a similar
way to to resolve congestion like this
Pathfinder algorithm so there's some
similarity
here um if you look at the steps before
place and rout like the logic
synthesis I think it there's more
overlaps and I think people already use
tools for fpga design also for as6 like
yosis for for
synthesis good and if any of you sitting
down have questions please don't
hesitate to get up and stand behind a
mic uh we have one more question yeah so
again this comes from the background of
fpga from yis and X PNR this is what I
have used so these open source
alternatives to let's say vivado and all
are youres and next PNR right I just
want to understand in that context maybe
it also applies to as 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 uh
overl region 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 uh how
is my circuit better will I have reduced
timing latency will they will be good
how does I make sure as a lay man how do
I understand okay placing and routing
happened what happened is a better uh uh
placement or let's say it was not that
efficient um so how can you make sure
that you don't have time Laten
so
timing intuitively you see the long
wires might have more like
Delight uh that's that's correct but
um often what you try to to minimize
is for instance the the quadratic wire
length or um like the the half parameter
wire length and now it can be that so
there's also for other things on the
left that we now don't see like like the
the the pins or pads and now it could be
that actually shifting this whole block
towards
there even though we make those lines a
bit longer still minimizes the wire
length because there's more wires go
going to the other
side but ultimately we are trying Trying
to minimize the wi L to reduce timing
latency that is what we are trying yes
and no
um because for for timing it gets more
gets more complicated so tendentially
it's better to have short wires for for
timing but not all wires matter the same
so a wire might be on on a path where
you have like lots of time available and
this wire will not matter much so you
can make it much longer without 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
tradeoff good it seems like we have our
final question but if any of you want to
ask a question you we still have time to
answer at least uh 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 voltage plane and so on is there
some kind of notion when routing
here so the the the planes
yeah um 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
there's other things that limit yourself
because there's some restrictions on
density and you actually want to use
also the the space for 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
optimization I think it's not common at
all for digital circuits
I think for for analog circuits it's
very different there people do it
usually manually but if you have so many
cells I think it's really hard sometimes
what I've seen is um 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 this
manually okay thank
you so if 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 one
[Applause]
warm
[Music]
la