Introduction to VLSI CAD and Discrete-Event Simulation at Tufts University
Comp150/EE194 Joel Grodstein
Comp 150/EE194: Introduction
to VLSI CAD
Spring 2017Tufts University
Instructor: Joel Grodstein
joelg@eecs.tufts.edu
Discrete-event simulation
What we'll cover today
•
Event-oriented simulation
•
What is simulation?
–
Build a virtual model of something.
–
Run the model with some inputs (this is the simulation
part!)
–
See if the model's outputs match what you expect
•
Simulation is a big part of
validation
– testing
whether your design works or not.
Comp150/EE194 Joel Grodstein
Why do we care
•
How many of you have ever written a non-trivial
computer program?
•
How many of you always have your programs
work perfectly the first time?
•
Designing things is easy.
–
Designing things that work is not so easy!
•
We all agree that validating stuff we design is
important. But why build virtual models of it?
–
Why not just build the real thing, try it out and iterate?
Comp150/EE194 Joel Grodstein
What are some things to
simulate?
•
A virtual world (a.k.a. a video game)
–
Why? Because it's fun.
•
An airplane
–
Flight simulation: e.g., to train pilots
•
A pacemaker
–
Because trying out your first version in a real human is not really a
good idea
•
A VLSI chip
–
Because building the first one costs several $M
•
A bacteria
–
Because they can be dangerous and expensive
Comp150/EE194 Joel Grodstein
A few more things to sim
•
A few published papers:
–
Simulate the effect of various air-traffic control policies on
congestion and safety (Conway 2006)
–
Crime Analysis. A realistic virtual urban environment, populated
with virtual burglar agents (Malleson 2010)
–
Simulating the smart power grid. GECO: Global Event-Driven Co-
Simulation Framework for Interconnected Power System and
Communication Network, 2013.
Comp150/EE194 Joel Grodstein
What will we cover today?
•
Discrete-event simulation: how it works
•
Discrete-event simulation as a way to use multi-
core processors
•
Example: simulating a VLSI network
•
Example: simulating a cure for cancer
Comp150/EE194 Joel Grodstein
Continuous vs. discrete
•
Models can be continuous or discrete. Who
remembers the difference?
–
Continuous: mostly differential equations. Accurate but
slow.
–
Discrete: interesting events happen at distinct times,
and nothing noteworthy happens in between. Big
speedup – if you can live with this model.
•
George Box: all models are wrong; some are still
useful.
•
We will focus on discrete-event models.
Comp150/EE194 Joel Grodstein
Simplest of gates: a buffer
•
Input=0 → output=0. Input=1 → output=1.
Comp150/EE194 Joel Grodstein
A
B
•
Now let's add some delay to it.
Buffer with delay
•
The output is simply a
delayed copy of the input.
Period.
•
The
Δ
t might be different
for different buffers.
–
Similar to a parameterized
object.
Comp150/EE194 Joel Grodstein
A
B
time delay
of 3 seconds
3
Next simple gate: an inverter
•
Input=1 → output=0. Input=0 → output=1. Delay
= (e.g., 3).
Comp150/EE194 Joel Grodstein
A
B
3
A
B
AND gate
•
Input=1 → output=0. Input=0 → output=1. Delay
= (e.g., 3).
Comp150/EE194 Joel Grodstein
A
B
3
A
B
C'
C
What if we have a big network?
Comp150/EE194 Joel Grodstein
Events
•
For big networks, we cannot deal with pictures of
waveforms. Why?
–
Computers don't store pictures real efficiently
–
We want to deal with objects and algorithms
•
Three types of objects:
–
A
gate
(each instance of AND, OR, INV, etc).
–
A
node
(what we've called A, B, C, etc). It has a value
at the current time
–
An
event.
I.e., a given node rising or falling at a given
time.
Comp150/EE194 Joel Grodstein
AND gate with events
•
Input=1 → output=0. Input=0 → output=1. Delay
= (e.g., 3).
Comp150/EE194 Joel Grodstein
A
B
3
A
B
C'
C
A=1@3
A=0@5
B=1@4
B=0@8
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
A=1@3
A=0@5
B=1@4
B=0@8
Current time
0
Pending events
C
0
0
0
3
1
1 & 0 → 0
C=0@3
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
C=0@3
A=0@5
B=1@4
B=0@8
Current time
0
Pending events
C
1
0
0
3
C is already 0, so this
event does nothing!
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
B=1@4
B=0@8
A=0@5
Current time
3
Pending events
C
1
0
0
4
1
1 & 1 → 1
C=1@7
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
A=0@5
B=0@8
C=1@7
Current time
4
Pending events
C
1
1
0
5
0
0 & 1 → 0
C=0@8
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
C=1@7
C=0@8
B=0@8
Current time
5
Pending events
C
1
1
0
7
0
This change on C
does not have any
fanout
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
B=0@8
C=0@8
Current time
7
Pending events
C
1
0
1
8
0
0 & 0 → 0
C=0@11
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
C=0@8
C=0@11
Current time
8
Pending events
C
1
0
0
8
0
This change on C
does not have any
fanout
Simulating our AND gate
•
Let's do a simulation.
Comp150/EE194 Joel Grodstein
A
B
3
C=0@11
Current time
8
Pending events
C
0
0
11
0
The value on C
does not change
DONE!
More practical consequences
•
Trends in functional validation: an industry study
,
2014
–
Large survey (1886 good responses) by Mentor
graphics
•
Conclusions:
–
Average 57% of time spent on verification
–
Most projects spend 60-70% of their time.
–
Average 11 val engineers, 10.1 design eng per project.
–
2007-2014 CAGR for DE=4%, VE=12% (and DE
spending 50% of their time on val).
Comp150/EE194 Joel Grodstein
SWARM
•
SWARM (Prof. Daniel Sanchez, MIT).
–
Seminar in Halligan last December
•
What problem did SWARM solve?
–
Intel keeps selling us multi-core CPUs; 64 processors with 2B
instruc/second, rather than one CPU with 100B instruct/second.
–
Why is this a problem?
–
Because parallel programming is really hard. Breaking one big
problem into 64 little problems that are mostly independent is not
the way our brains work.
EE194/Comp150 Joel Grodstein
SWARM
•
SWARM part 1:
–
Designed a chip that would run parallel DES really well
–
Mostly just a standard multi-core CPU with some secret sauce
•
SWARM part 2:
–
Showed you can turn various graph and database algorithms into
DES
–
I.e., DES is used for more than just DES!
Comp150/EE194 Joel Grodstein
Curing cancer
•
Well, perhaps not today.
•
One interesting strategy: re-purposing bacterial
chemotaxis.
•
Why are we talking about curing cancer?
–
Well, because most people would agree it's an
important problem
–
More to the point, because we can easily simulate our
strategy
Comp150/EE194 Joel Grodstein
What is bacterial chemotaxis?
•
Bacteria, like every living thing, need to find food
•
E.coli has sensors that can sense the presence of
sugar.
–
Based on these sensors, it steers itself towards the sugar
•
Big picture, no problem – but…
–
E.coli is too small to swim in a straight line; it keeps
getting hit by particles big enough to knock it off
course (i.e., it needs frequent course correction).
–
E.coli is too small to sense a spatial gradient (the
difference in concentration between its front & back is
often less than 1 molecule)
Comp150/EE194 Joel Grodstein
So what's an E.coli to do?
•
while (1)
–
note the sugar concentration level & remember it
–
pick a random direction
–
swim for a bit
–
if (current concentration < old concentration)
•
pick a new random direction
•
That's it:
–
Substantial oversimplification compared to real E.coli,
but it captures the main idea
–
The real one uses the difference between a fast reaction
(phosphorylation) and a slower reaction (methylation)
to "remember" the old concentration.
Comp150/EE194 Joel Grodstein
But how does that cure cancer?
•
Tumor cells are typically more acid and more
dense than surrounding tissue
–
Sensors can recognize this
–
We can use recombinant DNA techniques to graft new
sensors into E.coli, so that it hunts down tumor cells.
•
Reprogram it again to release lethal chemicals
when it finds the cancer cell.
•
Result: we have a tumor-hunting bacteria that
reproduces like crazy kills on contact.
•
References:
–
Environmentally-Controlled Invasion of Cancer Cells
by Engineered Bacteria
, JMB 2006.
–
Synchronized cycles of bacterial lysis for in vivo
delivery
, Nature 2016.
Comp150/EE194 Joel Grodstein
Our model
Comp150/EE194 Joel Grodstein
tumbler
tumbler
accumulator
accumulator
sensor
delay
line
decider
Δ
x
Δ
y
x
y
sugar_level
old_sugar_level
do_tumble
Simulation runs fine
•
The E.coli uses our algorithm.
•
The algorithm works perfectly
–
Admission: I did not get it right the first time!
•
So why should we not expect the Nobel Prize
anytime soon?
•
Class exercise:
–
Break into small groups
–
Play the game: how many things did the professor do
wrong?
Comp150/EE194 Joel Grodstein
What's wrong with our sim?
•
Our model does not match the actual E.coli
chemotaxis. We've proved that our model can find
a target, but not that the real organism can.
•
We've not even tried to model what happens when
the bacteria hits the tumor.
•
Even if the bacteria destroys the tumor: who will
destroy the bacteria?
•
Conclusion of the 2006 paper: ??
Comp150/EE194 Joel Grodstein
This course introduces students to event-oriented simulation, building virtual models, and validating designs through simulation. It covers the importance of simulation in testing and refining designs before implementation. Examples include simulating VLSI networks and exploring the use of discrete-event simulation on multi-core processors.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Comp 150/EE194: Introduction to VLSI CAD Spring 2017Tufts University Instructor: Joel Grodstein joelg@eecs.tufts.edu Discrete-event simulation Comp150/EE194 Joel Grodstein 1
What we'll cover today Event-oriented simulation What is simulation? Build a virtual model of something. Run the model with some inputs (this is the simulation part!) See if the model's outputs match what you expect Simulation is a big part of validation testing whether your design works or not. Comp150/EE194 Joel Grodstein 2
Why do we care How many of you have ever written a non-trivial computer program? How many of you always have your programs work perfectly the first time? Designing things is easy. Designing things that work is not so easy! We all agree that validating stuff we design is important. But why build virtual models of it? Why not just build the real thing, try it out and iterate? Comp150/EE194 Joel Grodstein 3
What are some things to simulate? A virtual world (a.k.a. a video game) Why? Because it's fun. An airplane Flight simulation: e.g., to train pilots A pacemaker Because trying out your first version in a real human is not really a good idea A VLSI chip Because building the first one costs several $M A bacteria Because they can be dangerous and expensive Comp150/EE194 Joel Grodstein 4
A few more things to sim A few published papers: Simulate the effect of various air-traffic control policies on congestion and safety (Conway 2006) Crime Analysis. A realistic virtual urban environment, populated with virtual burglar agents (Malleson 2010) Simulating the smart power grid. GECO: Global Event-Driven Co- Simulation Framework for Interconnected Power System and Communication Network, 2013. Comp150/EE194 Joel Grodstein 5
What will we cover today? Discrete-event simulation: how it works Discrete-event simulation as a way to use multi- core processors Example: simulating a VLSI network Example: simulating a cure for cancer Comp150/EE194 Joel Grodstein 6
Continuous vs. discrete Models can be continuous or discrete. Who remembers the difference? Continuous: mostly differential equations. Accurate but slow. Discrete: interesting events happen at distinct times, and nothing noteworthy happens in between. Big speedup if you can live with this model. George Box: all models are wrong; some are still useful. We will focus on discrete-event models. Comp150/EE194 Joel Grodstein 7
Simplest of gates: a buffer Input=0 output=0. Input=1 output=1. B A Now let's add some delay to it. Comp150/EE194 Joel Grodstein 8
Buffer with delay The output is simply a delayed copy of the input. Period. The t might be different for different buffers. Similar to a parameterized object. 3 A B time delay of 3 seconds Comp150/EE194 Joel Grodstein 9
Next simple gate: an inverter Input=1 output=0. Input=0 output=1. Delay = (e.g., 3). A 3 B A B Comp150/EE194 Joel Grodstein 10
AND gate Input=1 output=0. Input=0 output=1. Delay = (e.g., 3). A 3 B A B C' C Comp150/EE194 Joel Grodstein 11
What if we have a big network? Comp150/EE194 Joel Grodstein 12
Events For big networks, we cannot deal with pictures of waveforms. Why? Computers don't store pictures real efficiently We want to deal with objects and algorithms Three types of objects: A gate (each instance of AND, OR, INV, etc). A node (what we've called A, B, C, etc). It has a value at the current time An event. I.e., a given node rising or falling at a given time. Comp150/EE194 Joel Grodstein 13
AND gate with events Input=1 output=0. Input=0 output=1. Delay = (e.g., 3). A 3 B A A=1@3 A=0@5 B B=1@4 B=0@8 C' C Comp150/EE194 Joel Grodstein 14
Simulating our AND gate Let's do a simulation. Current time 3 0 0 1 A 0 C 3 B 0 Pending events A=1@3 B=1@4 1 & 0 0 C=0@3 A=0@5 B=0@8 Comp150/EE194 Joel Grodstein 15
Simulating our AND gate Let's do a simulation. Current time 3 0 A 1 0 C 3 B 0 Pending events C=0@3 B=1@4 C is already 0, so this event does nothing! A=0@5 B=0@8 Comp150/EE194 Joel Grodstein 16
Simulating our AND gate Let's do a simulation. Current time 3 4 A 1 0 C 3 B 0 1 Pending events B=1@4 A=0@5 1 & 1 1 C=1@7 B=0@8 Comp150/EE194 Joel Grodstein 17
Simulating our AND gate Let's do a simulation. Current time 4 5 A 1 0 0 C 3 B 1 Pending events A=0@5 C=1@7 0 & 1 0 C=0@8 B=0@8 Comp150/EE194 Joel Grodstein 18
Simulating our AND gate Let's do a simulation. Current time 5 7 A C 1 0 0 3 B 1 Pending events This change on C does not have any fanout C=1@7 B=0@8 C=0@8 Comp150/EE194 Joel Grodstein 19
Simulating our AND gate Let's do a simulation. Current time 7 8 A C 1 0 3 B 0 1 Pending events B=0@8 C=0@8 0 & 0 0 C=0@11 Comp150/EE194 Joel Grodstein 20
Simulating our AND gate Let's do a simulation. Current time 8 8 A C 1 0 0 3 B 0 This change on C does not have any fanout Pending events C=0@8 C=0@11 Comp150/EE194 Joel Grodstein 21
Simulating our AND gate Let's do a simulation. Current time 8 11 A 0 C 0 3 B 0 The value on C does not change Pending events C=0@11 DONE! Comp150/EE194 Joel Grodstein 22
More practical consequences Trends in functional validation: an industry study, 2014 Large survey (1886 good responses) by Mentor graphics Conclusions: Average 57% of time spent on verification Most projects spend 60-70% of their time. Average 11 val engineers, 10.1 design eng per project. 2007-2014 CAGR for DE=4%, VE=12% (and DE spending 50% of their time on val). Comp150/EE194 Joel Grodstein 23
SWARM SWARM (Prof. Daniel Sanchez, MIT). Seminar in Halligan last December What problem did SWARM solve? Intel keeps selling us multi-core CPUs; 64 processors with 2B instruc/second, rather than one CPU with 100B instruct/second. Why is this a problem? Because parallel programming is really hard. Breaking one big problem into 64 little problems that are mostly independent is not the way our brains work. EE194/Comp150 Joel Grodstein 24
SWARM SWARM part 1: Designed a chip that would run parallel DES really well Mostly just a standard multi-core CPU with some secret sauce SWARM part 2: Showed you can turn various graph and database algorithms into DES I.e., DES is used for more than just DES! Comp150/EE194 Joel Grodstein 25
Curing cancer Well, perhaps not today. One interesting strategy: re-purposing bacterial chemotaxis. Why are we talking about curing cancer? Well, because most people would agree it's an important problem More to the point, because we can easily simulate our strategy Comp150/EE194 Joel Grodstein 26
What is bacterial chemotaxis? Bacteria, like every living thing, need to find food E.coli has sensors that can sense the presence of sugar. Based on these sensors, it steers itself towards the sugar Big picture, no problem but E.coli is too small to swim in a straight line; it keeps getting hit by particles big enough to knock it off course (i.e., it needs frequent course correction). E.coli is too small to sense a spatial gradient (the difference in concentration between its front & back is often less than 1 molecule) Comp150/EE194 Joel Grodstein 27
So what's an E.coli to do? while (1) note the sugar concentration level & remember it pick a random direction swim for a bit if (current concentration < old concentration) pick a new random direction That's it: Substantial oversimplification compared to real E.coli, but it captures the main idea The real one uses the difference between a fast reaction (phosphorylation) and a slower reaction (methylation) to "remember" the old concentration. Comp150/EE194 Joel Grodstein 28
But how does that cure cancer? Tumor cells are typically more acid and more dense than surrounding tissue Sensors can recognize this We can use recombinant DNA techniques to graft new sensors into E.coli, so that it hunts down tumor cells. Reprogram it again to release lethal chemicals when it finds the cancer cell. Result: we have a tumor-hunting bacteria that reproduces like crazy kills on contact. References: Environmentally-Controlled Invasion of Cancer Cells by Engineered Bacteria, JMB 2006. Comp150/EE194 Joel Grodstein 29
Our model x x tumbler accumulator y y tumbler accumulator sensor sugar_level do_tumble decider delay line old_sugar_level Comp150/EE194 Joel Grodstein 30
Simulation runs fine The E.coli uses our algorithm. The algorithm works perfectly Admission: I did not get it right the first time! So why should we not expect the Nobel Prize anytime soon? Class exercise: Break into small groups Play the game: how many things did the professor do wrong? Comp150/EE194 Joel Grodstein 31
What's wrong with our sim? Our model does not match the actual E.coli chemotaxis. We've proved that our model can find a target, but not that the real organism can. We've not even tried to model what happens when the bacteria hits the tumor. Even if the bacteria destroys the tumor: who will destroy the bacteria? Conclusion of the 2006 paper: ?? Comp150/EE194 Joel Grodstein 32
