1
00:00:08,160 --> 00:00:12,550
So here we are in lecture twelve. 
And we're going to talk about timing. 

2
00:00:12,550 --> 00:00:18,642
So where are we in the, the CAD flow? 
You synthesized it, you got 10 million 

3
00:00:18,642 --> 00:00:23,144
gates, you mapped it. 
You got 10 million or so gates from the 

4
00:00:23,144 --> 00:00:27,443
available technology library. 
You placed it, so you know where they are 

5
00:00:27,443 --> 00:00:30,108
on the surface of a piece of silicon 
that's maybe you know, a centimeter on a 

6
00:00:30,108 --> 00:00:33,030
side. 
You routed it. 

7
00:00:33,030 --> 00:00:37,950
So you got 10 or 20 million wires across 
10 layers of metal connecting everything. 

8
00:00:37,950 --> 00:00:39,690
What's the next question you might 
want to ask? 

9
00:00:39,690 --> 00:00:43,170
And the question is, how fast does it go? 
Right, doesn't meet the timing 

10
00:00:43,170 --> 00:00:46,802
requirements when I started the design. 
Let's assume, for example, that I want it 

11
00:00:46,802 --> 00:00:50,286
to run with a 1 gigahertz clock. 
Then, I've got 1 nanosecond in which to 

12
00:00:50,286 --> 00:00:53,270
get all the work done. 
So, everything that comes out of a 

13
00:00:53,270 --> 00:00:55,750
storage element and goes through a big 
blob of logic, and goes into another 

14
00:00:55,750 --> 00:00:58,832
storage element. 
All that stuff's gotta happen in 1 

15
00:00:58,832 --> 00:01:02,930
nanosecond, in 1,000 pecoseconds. 
How do I tell if that's possible? 

16
00:01:02,930 --> 00:01:05,750
How do I look at the logic and see if I'm 
doing it right? 

17
00:01:05,750 --> 00:01:09,532
How do I model the physical delay, the 
electrical delay of the wires that we 

18
00:01:09,532 --> 00:01:13,558
spent all that time learning how to route 
that connect all the logic elements so 

19
00:01:13,558 --> 00:01:17,340
that I know that all those paths through 
the gates and through the wires are 

20
00:01:17,340 --> 00:01:24,558
actually meeting all of my timing goals. 
And even beyond that, if I'm not meeting 

21
00:01:24,558 --> 00:01:28,820
my timing goals where do I look to figure 
out what went wrong? 

22
00:01:28,820 --> 00:01:32,934
What are the most problematic things that 
I might be able to go back and fix? 

23
00:01:32,934 --> 00:01:36,233
This is the universe of timing. 
And so, in this introductory lecture 

24
00:01:36,233 --> 00:01:39,201
we're going to talk about what we're 
going to do on the logic side and what 

25
00:01:39,201 --> 00:01:42,540
we're going to do on the layout side as 
we go forth to explore timing, so let's 

26
00:01:42,540 --> 00:01:49,815
go take a look. 
So, our new problem is to talk about 

27
00:01:49,815 --> 00:01:53,232
timing. 
to date, in all of the material we've 

28
00:01:53,232 --> 00:01:57,820
done in the class, we've basically 
focused pretty much on function, logic 

29
00:01:57,820 --> 00:02:02,780
side function. 
You know, getting the right logical 

30
00:02:02,780 --> 00:02:05,457
function. 
Being able to verify that it does the 

31
00:02:05,457 --> 00:02:09,955
right thing as a, as a boolean equation 
or a, or a network of gates. 

32
00:02:09,955 --> 00:02:13,790
Optimizing it, you know, reducing the 
complexity on the physical side, on the 

33
00:02:13,790 --> 00:02:18,056
geometry side, making sure we put all the 
gates some place. 

34
00:02:18,056 --> 00:02:21,190
That we optimize things like the length 
of the wires. 

35
00:02:21,190 --> 00:02:23,560
That we correctly do things like route 
the wires. 

36
00:02:23,560 --> 00:02:26,826
you know, it's clear that there are some 
really deep interactions between say the 

37
00:02:26,826 --> 00:02:30,400
logic synthesis and the layout. 
So, I mean if you just think about the 

38
00:02:30,400 --> 00:02:32,830
diagram on this slide. 
You know, we start with some kind of a 

39
00:02:32,830 --> 00:02:35,266
high-level description. 
And clearly there's something about 

40
00:02:35,266 --> 00:02:38,255
timing going on in there. 
We have not had time in the course to 

41
00:02:38,255 --> 00:02:42,710
actually talk about how one deals with 
time in the earlier stages. 

42
00:02:42,710 --> 00:02:46,208
Logic synthesis gives us connected cells 
with delay constraints on the signal 

43
00:02:46,208 --> 00:02:49,070
paths. 
The physical design, after the very 

44
00:02:49,070 --> 00:02:54,130
least, it places the cells in a way that 
makes them routeable later on. 

45
00:02:54,130 --> 00:02:56,970
And then it actually routes them, you 
know, with connecting wires. 

46
00:02:56,970 --> 00:03:00,750
what we're going to focus on here is how 
one asks questions about the timing 

47
00:03:00,750 --> 00:03:04,220
behavior. 
You know, how fast can this thing go? 

48
00:03:04,220 --> 00:03:08,400
And there's some important facts. 
the logic-side tools have to be able to 

49
00:03:08,400 --> 00:03:12,990
estimate the delays through unplaced and 
unrouted logic. 

50
00:03:12,990 --> 00:03:16,528
So it's often the case that they're 
going to be using very crude models of 

51
00:03:16,528 --> 00:03:21,609
what's happening with respect to the 
geometry aspects of the design. 

52
00:03:21,609 --> 00:03:25,739
but once you actually have layout or even 
rough or approximate layout you can 

53
00:03:25,739 --> 00:03:29,928
actually estimate the delays through not 
only the logic but also some models of of 

54
00:03:29,928 --> 00:03:35,818
the wires that that connect them. 
And so for both the logic-side and the, 

55
00:03:35,818 --> 00:03:39,210
and the physical-side, being able to ask 
questions of timing is really a very 

56
00:03:39,210 --> 00:03:44,330
important thing. 
So our topics for talking about ASIC 

57
00:03:44,330 --> 00:03:46,656
timing. 
Well, we're going to talk about the logic 

58
00:03:46,656 --> 00:03:49,632
side of this and so we're going to do 
some thing that's very important which is 

59
00:03:49,632 --> 00:03:53,834
called static timing analysis. 
And we're going to explain in a while why 

60
00:03:53,834 --> 00:03:57,184
it's called static. 
but for now, the question is sort of 

61
00:03:57,184 --> 00:04:00,021
simple. 
How do we estimate the worst case timing 

62
00:04:00,021 --> 00:04:03,609
through a logic network? 
So we have a bunch of gates and we have a 

63
00:04:03,609 --> 00:04:07,019
bunch of wires and, you know, maybe we 
don't have yet good models of what the 

64
00:04:07,019 --> 00:04:12,262
wires are doing in terms of delay. 
Maybe we have only rough models. 

65
00:04:12,262 --> 00:04:15,245
Nevertheless, I've got millions and 
millions of gates. 

66
00:04:15,245 --> 00:04:18,314
I need to be able to ask questions like 
how fast can it go? 

67
00:04:18,314 --> 00:04:22,661
And on the layout side we're going to be 
primarily focusing on interconnect delay 

68
00:04:22,661 --> 00:04:26,714
analysis. 
So we place the gates, we route the wires 

69
00:04:26,714 --> 00:04:30,970
that connect the gates. 
How do you estimate the delays on the 

70
00:04:30,970 --> 00:04:33,478
wires? 
Because in a, in a modern nano-scale 

71
00:04:33,478 --> 00:04:37,062
technology with a chip that's, you know, 
a centimeter or two centimeters on a 

72
00:04:37,062 --> 00:04:40,702
side, millions and millions and millions 
of gates, you can have an awful lot of 

73
00:04:40,702 --> 00:04:44,286
the delay of the logic circuit itself 
just in the signal propagation through 

74
00:04:44,286 --> 00:04:50,957
the physical electric circuits that are 
the, represented by the wires. 

75
00:04:50,957 --> 00:04:54,491
So we've gotta actually be able to ask 
and answer both the logic side timing 

76
00:04:54,491 --> 00:04:57,950
question and the layout side timing 
question. 

77
00:04:59,650 --> 00:05:02,846
So on the logic side, what's interesting 
is that all the problems look like either 

78
00:05:02,846 --> 00:05:06,089
longest or shortest paths through a graph 
that properly models the gates and if you 

79
00:05:06,089 --> 00:05:09,780
do it correctly you can also model the 
wires. 

80
00:05:09,780 --> 00:05:12,900
When we start we won't be modeling the 
wires but we'll, we'll, we'll close that 

81
00:05:12,900 --> 00:05:15,492
loop when we get to the end of the 
lecture and we'll show you how the 

82
00:05:15,492 --> 00:05:18,708
understanding of what the wires do can be 
incorporated back into the logic-side 

83
00:05:18,708 --> 00:05:22,829
analysis. 
What's kind of surprising here is that 

84
00:05:22,829 --> 00:05:26,810
the maze routing idea reappears in a very 
nice, in a very organic way. 

85
00:05:26,810 --> 00:05:28,591
We're going to be talking about wave 
fronts. 

86
00:05:28,591 --> 00:05:30,300
We're going to be talking about 
expanding. 

87
00:05:30,300 --> 00:05:33,610
We're going to be talking about reaching. 
We're going to be talking about heat. 

88
00:05:33,610 --> 00:05:37,333
The very pretty, nice classical kind of a 
connection from something on the physical 

89
00:05:37,333 --> 00:05:41,345
side to something on the, on the logical 
and the timing side. 

90
00:05:41,345 --> 00:05:45,889
And, when we talk about the layout-side 
and we talk about interconnect delay 

91
00:05:45,889 --> 00:05:50,646
analysis, there is no way around the fact 
that the problem has to be modelled as an 

92
00:05:50,646 --> 00:05:55,875
electrical circuit. 
Now if everybody in the class had an 

93
00:05:55,875 --> 00:05:59,698
electrical engineering background we 
could actually do some cool circuits. 

94
00:05:59,698 --> 00:06:02,514
But since I don't think everybody in the 
class has an electrical engineering 

95
00:06:02,514 --> 00:06:05,390
background, I'm simply not going to do 
the circuit. 

96
00:06:05,390 --> 00:06:08,800
So I'm going to talk a little bit about 
circuit elements at the level of the 

97
00:06:08,800 --> 00:06:12,210
basic sort of physics class that I'm 
assuming everybody has taken, but you 

98
00:06:12,210 --> 00:06:16,460
don't really need to know any detailed 
circuits. 

99
00:06:16,460 --> 00:06:19,652
We're going to surprisingly turn all of 
this stuff into just another 

100
00:06:19,652 --> 00:06:23,025
computational task. 
And I know you're tired of me saying 

101
00:06:23,025 --> 00:06:26,441
this, but amazingly enough it's going to 
be another attractive, simple 

102
00:06:26,441 --> 00:06:30,890
computational walk on another special 
tree data structure. 

103
00:06:30,890 --> 00:06:34,250
And by starting from the physical 
geometry of the wire, turning it into a 

104
00:06:34,250 --> 00:06:38,114
special tree data structure, doing a very 
simple computation that walks the tree, 

105
00:06:38,114 --> 00:06:41,250
I'm going to be able to get a 
surprisingly accurate electrical kind of 

106
00:06:41,250 --> 00:06:48,270
a model of the delay of a form that I can 
actually use for the logic-site timing. 

107
00:06:48,270 --> 00:06:52,365
So, it's a very nice way to, sort of, 
close things in the class with something 

108
00:06:52,365 --> 00:06:56,850
that's linking the physical side, the 
geometry side in a very important and key 

109
00:06:56,850 --> 00:07:03,065
way back into the logical side of things. 
So, with that let's go start talking 

110
00:07:03,065 --> 00:07:05,900
about timing, and we're going to start by 
talking about the logical side of the 

111
00:07:05,900 --> 00:07:07,222
world. 

112
00:07:07,222 --> 00:07:13,346
[SOUND]