---
Video Title: Cost of  Computing
Description: Theory of Computation
https://uvatoc.github.io/week5

11.6: Cost of Computing
- How should we measure the cost of computing?
- Counting NAND gates

David Evans and Nathan Brunelle
University of Virginia
---

How does this relate to what we actually
care about?

This is a theorem that says there are some
functions that seem expensive,

but expensive here is the size of the
circuit.

And what we really should care about is
cost.

How do you measure cost?

Well, we've measured cost so far today.

Number of lines in a NAND CERC program.

It's a really precise definition.

In other classes, you've probably measured
cost as some notion of running time.

Maybe you counted steps.

Maybe you had some notion of what you can
do in the future.

In each step.

Is either of those the right way to
measure cost?

Definitely not.

When we're talking about cost,
we should be talking about money.

Any other cost, if we can convert between,
say, time and space, then if the cost is

high in time but low in space,
well, we don't care.

We can convert.

We don't know.

Unless we can say this is
the fundamental cost in some

important way, we don't know if
we're measuring the right thing.

And the cost of computing, well,
that's really easy to convert to money.

These days.

You can go on Amazon's web page or
Microsoft's or your favorite cloud

computing server and find out exactly what
it costs to compute.

And that changes every hour.

These prices are based on demand.

You can buy a certain amount of computing
for .0084 dollars per hour.

That's probably not very much.

But the most expensive nodes, you're
paying a few dollars an hour.

So if you wanted to
measure costs like that, these

kinds of asymptotic costs
might not help us very much.

And you can see the costs vary a lot.

They vary whether
you're running Linux or.

Windows, like the cheaper
ones are running Linux.

And they vary where you are.

If you are in Korea or you want your
computing in Korea, compared to wanting it

in Virginia, you're paying about five
times as much.

Why would anyone pay five
times as much to have their

computing done in Korea
than to have it done in Ashland?

Yeah.

It could be.

There could be
jurisdictional reasons you

don't want to have your
data exposed to the US.

There's people that do think about that.

They probably don't want to use Amazon
then, if you don't trust the US very well.

Yeah, what else?

Yeah, so space is time.

Depending on where you compute it,
if you are serving customers in Korea and

you want low latency, you want your
computing done close to them.

If you're serving humans,
you want low latency

and trip time around
the world matters.

By plane, it's a lot.

But by data, it only travels about a third
the speed of light.

Really slow.

It takes time to travel.

Speed of light should be about 53
milliseconds.

That's about the best you can do if you had
direct fiber between your two endpoints.

Latency matters.

The other thing is bandwidth.

Bandwidth is actually really expensive.

The main cost of most computing today is
not computing.

It's bandwidth.

So if you have a lot of data
that you need to move across the

country, you should buy a
truck and fill it up with hard drives.

That's still the cheapest way to move a
lot of data.

These are not what we're measuring.

We're not measuring the cloud computing
cost of computing these functions.

What's the closest real cost?

If we're talking about sizes of circuits
as the thing we're measuring, what's the

closest sort of dollar cost that that
corresponds to?

So it doesn't have anything
to do with bandwidth

or whether we're computing
in Korea or Virginia.

The size of the circuit does have
something to do with the amount of energy

that we need to use to execute the
circuit.

That is related to the number of gates
that we have to flip.

So the size of the circuit is going to
have a direct connection to energy.

So in that sense, it's actually maybe a
pretty good proxy for some things.

That assumes that we've actually got a
custom circuit.

If we're actually running it as code or
we're running it on a processor,

then the cost to execute
that as code is not going to

be that closely related
to the size of the circuit.

If we care about time, how good a proxy is
the size of the circuit for time?

What property of the circuit
tells us how long it takes

to execute the circuit if we
only have one execution?

Yeah.

Yeah, so the depth of the circuit.

We can execute each layer in parallel, but
the time it's going to take is the depth.

But in terms of energy,
size of the circuit, if we

were thinking of YAB, we
were actually doing a circuit.

Now, we're counting NAND gates.

Is that the right thing to be counting if
we care about the number of operations?

If we're actually making it in Silicon,
it's a pretty good thing to count.

Most of you in your pocket have a few
billion NAND gates.

They're cheap.

The processor on your front, if you've got
a laptop, you have more than a few billion.

NAND gates are cheap and we can make lots
of them.

But if we're computing a function,
so this is where if it's a universal

circuit, then we can compute any circuit
with that.

So you could say that makes sense,
but it's a pretty expensive way to compute.

If you look at processors, they don't just
have NAND gates.

At least that's not the instruction that
you're running.

If we didn't care about cost, Intel only
needs to give us one instruction.

But they built thousands
of instructions into

the processor to support
more efficient programs.