In this project-centered course you will build a modern software hierarchy, designed to enable the translation and execution of object-based, high-level languages on a bare-bone computer hardware platform. In particular, you will implement a virtual machine and a compiler for a simple, Java-like programming language, and you will develop a basic operating system that closes gaps between the high-level language and the underlying hardware platform. In the process, you will gain a deep, hands-on understanding of numerous topics in applied computer science, e.g. stack processing, parsing, code generation, and classical algorithms and data structures for memory management, vector graphics, input-output handling, and various other topics that lie at the very core of every modern computer system. This is a self-contained course: all the knowledge necessary to succeed in the course and build the various systems will be given as part of the learning experience. The only prerequisite is knowledge of programming at the level acquired in introduction to computer science courses. All the software tools and materials that are necessary to complete the course will be supplied freely after you enrol in the course. This course is accompanied by the textbook "The Elements of Computing Systems" (Nisan and Schocken, MIT Press). While not required for taking the course, the book provides a convenient coverage of all the course topics. The book is available in either hardcopy or ebook form, and MIT Press is offering a 30% discount off the cover price by using the discount code MNTT30 at https://mitpress.mit.edu/books/elements-computing-systems. The course consists of six modules, each comprising a series of video lectures, and a project. You will need about 2-3 hours to watch each module's lectures, and about 15 hours to complete each one of the six projects. The course can be completed in six weeks, but you are welcome to take it at your own pace. You can watch a TED talk about this course by Googling "nand2tetris TED talk". *About Project-Centered Courses: Project-centered courses are designed to help you complete a personally meaningful real-world project, with your instructor and a community of learners with similar goals providing guidance and suggestions along the way. By actively applying new concepts as you learn, you’ll master the course content more efficiently; you’ll also get a head start on using the skills you gain to make positive changes in your life and career. When you complete the course, you’ll have a finished project that you’ll be proud to use and share.
Unit 6.2: Efficiency Matters
Loading...
From the course by Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
147 оценки
Hebrew University of Jerusalem
147 оценки
From the lesson
Operating System
Meet the Instructors
Shimon SchockenProfessor
Computer Science
As I said in the previous unit, we decided to open the module on
operating systems with a discussion of some efficiency matters.
So, once again, here is the Jack operating system, and
let us focus on the top left class, so to speak, math.
We see that math is a collection, or
a library of several widely used mathematical operations.
And the first thing that I would like to claim is that when it comes to
operating systems, efficiency really matters.
You see, every one of the operations that you see here is
going to be used by numerous application programs,
and perhaps by other classes in the operating system, as well.
So, the lower is the service, so to speak,
in the software hierarchy the more you want it to be efficient,
because it is going to support many more services on top of it.
Now think about things like multiplication, division, square root.
They'd better be efficient.
So, to illustrate, let us focus on the multiplication method,
and to begin with, let's take a look at the client perspective, so to speak.
So, we can write some Jack program, and
at some point, you say x times y.
And if you want, by the way, you can also multiply numbers using this syntax.
In the first example, in the top multiplication,
the compiler is going to be generous enough to understand that
asterisk stands for invoking the method that you see at the bottom,
and the compiler will automatically replace 419 times
5003 by math, multiply these two numbers.
So, you can do either way, right?
It doesn't matter.
So, this is just a syntactical comment that I wanted to put aside,
and someone has to deliver this functionality, and this agent is,
of course, the math class in our Gecko operating system.
So, here is an example of a possible solution to multiplication.
We're going to do what is known as repetitive addition, and basically,
we are adding x to some accumulator y times.
Now, before you continue, I'd like to
say a few words about the syntax that we're going to use in this unit, and
in all subsequent units from now until the end of this module.
We no longer use the Jack syntax of curly brackets, and semi colons and so on.
Instead, we do something which is similar to Python,
we use indentation to stand for blocks of code.
And we do this because we want you to focus strictly on the algorithm, and
ignore all sort of syntax clutters,
which are not terribly important when we discuss the operating system.
So, with that in mind, what is the running time of this algorithm?
Well, I'm not sure what is the exact running time, but
I see from the code here that is really completely dominated by y.
If y is a large number, then we're going to have many iterations in this program,
we're going to have y iterations in this particular algorithm.
And if you ask me what is the running time of this algorithm?
Then in computer science, when we're asked to give such assessments,
we always take a very honest and conservative standpoint.
And we try to give what is known as the worst case answer.
So, let us assume that N is the largest number that we may be asked to multiply.
So N is the largest value of y.
And with that in mind,
we observed that the algorithms runtime is proportional to N, Y proportional to N.
Because we have y iterations, actually, we have N iterations in the worst case.
And in every one of this iterations, let us assume that we have
to make something like ten machine-level operations after compilation and so on.
So, overall, we have to perform ten times N machine operations.
So whatever, whether it's ten or 20 or 40, it doesn't really matter,
because N dominates the picture here.
And therefore, the running time is simply proportional to N.
If N is a huge number, this algorithm would run extremely slowly.
So, let's remember this algorithm,
put it on the side, and consider now another solution.
And this solution is based on what we learned in elementary school.
So, for example, if I ask you to multiply 27 times nine in binary,
then I can do exactly what they learned in grade two or three.
I don't remember.
Basically, I take the first number, also known as the multiplicand.
And this is a big words, so I'll simply use x instead.
So we take x, we write it down, and I'm sorry, we take x,
we multiply it by the right most digit of the multiplier, which happens to be one.
And so we get the same number, the same x.
We write it down.
Then we take the same x, and we multiply it by the next digit up
the significance letter, so to speak, which happens to be zero.
So we get a bunch of zeros.
Then we do the same with the next bit.
Once again, we get a bunch of zeros.
Then we do the same thing with the next bit, which happens to be one.
And finally, we add up all these bits along the rows, or along the columns.
And we get the result, which happens to be 243.
All right,
now let me present to you a more systematic way of doing the same thing.
Well here, I take into consideration the fact
that this number does not exist in a vacuum.
It sits within some word in memory, and the width of this word in Jack is 16 bits.
But in a modern computer, it's typically 64 bits, or maybe even 128 bits.
So, I write down the number, and then I pad with zeroes until the end of the word.
And I do the same with y, and here is the algorithm.
I take x and write it down as is,
then I shift x one position to the left, write it again,
shift it another position to the left, write it again, and so on and so forth.
And in this particular case, I do it four times, why four?
Because the second number, the multiplier, has four significant bits, 1 0 0 0 1, so
it's enough to carry out this shifts four times.
And then I have to add them up.
Now, how do I add them up?
Well, I take the multiplier, and I write it kind of vertically, just for
my own record keeping.
And then I'm going to add up only those rows for which the index,
or the ith bit of, and the multiplier is one.
So, it looks from this example here, that I have to add up only the first and
the last row.
And indeed, if I do it, I will get the same result that I got before.
So, it looks like two very similar procedures, yet,
the second procedure is easier to implementing a computer program,
and indeed, here is the program that's implements it.
We start with some accumulated sum, which is initialized to zero,
and then we use a variable that we call shifted x.
And at the beginning, shifted x is the same as x,
that's the first row below the lines, so to speak.
And then we go through the following group.
For each i, going from zero to the number of
digits that they have in their presentation, w, and
so, w can be 16, or 64, or.
It is a relatively small number.
So, for every one of these digits, if the ice bit of
the multiplier is one, I add shifted x to sum.
And then irrespective of this test, I do another shift,
and I go back to the fore loop and do the same over and
over again, until I exhaust all the bits in the representation.
So, what I described here is just sort of a sequential way to describe
what I did waving my hand, when I gave you this example up there.
You can stop the tape and verify that it's exactly the same thing.
And at the end of this process, I return the sum to which we arrived.
All right, now there are some very nice properties of this algorithm.
Once again,
let us assume that n is the largest number that we may be asked to multiply.
It may be a million, a billion, a trillion.
Whatever is the number that you can represent given w bits.
And yet, irrespective of the magnitude of this number,
the runtime of this algorithm is proportional not to n, but
rather to w, to the number of bits which is fixed, right?
Because we work with a fixed representation with either 1632,
64 bits and so on.
And this constant 16 64 and so on is going
to determine how long this algorithm is going to be, is going to perform.
Now, it also happens that the number of bits that it takes to represent a number
n Is log based two of n,
which is a relatively, not relatively, it's a very small number.
I mean, when n is very large log two of n is still very small.
Now, there's another nice property of this algorithm.
If you look at it, it involves only addition operations and shifts.
Now, shift is a trivial operation in the world of binary numbers,
and also note that shift is simply the same as adding up the same number.
So, shifted x is shifted x plus shifted x.
It's another way to think about shift.
So, anyway you look at it,
what we have here is an algorithm that runs just a few iterations.
And in each iterations, it carries out only addition operations, which is lovely.
It means that we can easily implement this algorithm either in software,
as we did here or in hardware.
We can easily build a logic gate, or a chip that carries out
multiplication using this logic here, all right?
Now, if you're not convinced that logarithmic runtime is good, I'd like to
give you some examples, and in particular, take a look at this table here.
And what I have on the left column is some representative
examples of the magnitude of N, the input.
Now, if I have an algorithm whose runtime is proportional to N,
let's say that the proportion constant or coefficient is ten,
then the running time of this algorithm will be as shown here in red.
And you see that as the input becomes large,
the running time becomes very slow proportionally.
And what about log?
Well, here's the log function applied to the very same inputs.
And you see here that in respective how the input grows,
the log remains very small, and we can see
the dramatic difference between these two functions very vividly if we plot them
one next to the other, so on the x-axis we see the size of the input N.
And here is the linear function, the red one.
And you see that as N goes up,
this function goes through the roof, so to speak.
And yet, at the same time, the log remains asymptotically bounded.
It will also reach infinity at some point, but it will take a lot of time.
It will happen only with astronomically large input sizes.
And so, the attractive thing about log of N,
is that as you double the input,
log of N increases by one unit only.
And in words, as the size of the input doubles, the algorithm that has
logarithmic running time requires one additional iteration.
Now, this statement is quite remarkable,
and it has far-reaching practical implications.
And to illustrate it, let's take an example which is close to home.
All of you guys are searching the Internet, and
you are doing it using search engines.
And every one of these search engines is using all sorts of versions
of an algorithm called binary search.
And binary search has this nice property of having a runtime,
which is logarithmic in the size of the input.
What does this mean?
It means that, for example,
suppose that the size of the Internet is 1 billion items,
and you want to search every one of these items, and find it as fast as you can.
Well, according to this table, if you want to search or
find one item out of a billion using a logarithmic runtime algorithm.
It will take 300 iterations.
So far, so good.
Suppose now, that tomorrow, the size of the Internet is going to double.
It is now going to be 2 billion items.
How long will it take now to find any particular item in this huge
sort of universe of information?
Well, according to the logarithmic rationale,
it will take 310 steps, because the constant here equals.
So, from 300 went up to 310,
and suppose that in a few days later, or a few months later,
the size of the Internet will double again, and it will be 4 billion items.
How long will it take the search engine to find any one item
in this huge pile of information?
It will take the algorithm 320 iterations.
So, you see that as the size of the Internet shoots out of the roof,
the search time is logarithmically bounded, and it never becomes too large.
And this is, I think,
a dramatic example of the incredible power of logarithmic run time.
And that's why in computer science,
whether it's a theoretical computer science, or applied computer science,
we're always delighted when we manage to come up and
conjure logarithmic runtime algorithms.
All right, so, to recap, this has been a unit about efficiency,
but as a side effect of talking about efficiency,
we also talked about fast implementations of multiplication.
And what we'll do in the next unit is continue from this point onward and
discuss the implementation of some other mathematical operations.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
