CS 207
Final exam
Ondich
Due 5:00 PM, Friday, November 22, 1996
HAND IN ON PAPER


You may use your textbook, your notes, the library, our computers, your computer, and the Internet for this exam. Do not consult with people other than Jeff Ondich, who would be pleased to speak with you about the exam, and who would also be pleased to have you present him with clear and carefully considered exposition as well as neatly typed explanations and neatly drawn diagrams. Have a good time.

Java

As you are doubtless aware by now, Java is a programming language devised by researchers at Sun Microsystems. This language was originally designed to facilitate programming for embedded systems--the ubiquitous microprocessors found in our cars, our appliances, our thermostats, our toys, etc. Some of the features that made Java appropriate for embedded systems programming--security, good exception handling, automatic garbage collection (that is, the prevention of memory leaks due to allocation of memory that is never later freed), etc.--have also made it appropriate for transmitting programs over the World-Wide Web. That's why Java became famous overnight, and why its independent existence as a general-purpose programming language has been hard to see through all the hype about "applets" and little dancing men on Web pages.

One of the most interesting features of Java is the means by which its designers intended it to be translated into machine language. Part of the specification of Java is the specification of the Java Virtual Machine. The JVM has a simple instruction set that has many features in common with most assembly languages, including the MIPS and PDP8/E assembly languages. The JVM instructions are called bytecodes, for reasons that will be clear in a moment.

When you compile a Java program, you don't compile it directly into the machine language of a particular processor. Instead, you compile it into the JVM instruction set. The resulting bytecode "executable" doesn't run on any real machines directly. But since the bytecodes are like instructions found in most machine languages, the translation from JVM bytecodes to any particular machine language is very simple (especially if you don't sweat performance). When Java programs (applets) are shipped from Web server to Web browser, they are sent as bytecodes, which the browser translates to the machine language of the real machine on which the browser is running.

Question 1

Discuss the costs and benefits of using bytecodes as an intermediate step between Java and machine languages. What parts of the computing system (considered broadly to include the various levels of hardware and software, as well as the users, hardware designers, compiler writers, applications programmers, etc.) pay the costs, and what parts reap the benefits? One or two pages of discussion will be sufficient for the purposes of this exam (though this question has undoubtly occupied thousands of hours at Sun and elsewhere).

You might find it interesting in this context to know that one of the earliest implementations of Pascal--UCSD Pascal--used a scheme almost identical to Java's. Its intermediate language was called "p-code," which survived for a while until Turbo Pascal came along (this is an over-simplification of the events, but it is true that Borland, in a sense, exploited a weakness in the p-code idea). Turbo did not use p-code.

More about JVM

The JVM architecture is stack-based, in the sense that almost all of its instructions make reference to a stack. The addition instruction iadd, for example, pops the top two words from the stack, adds them together, and then pushes the result back on the stack.

The location of the stack is not addressed in the specification of the JVM. Just as the description of the PDP8/E architecture might say "the PDP8/E has a 12-bit Accumulator, a 1-bit Link, and a Memory consisting of 4096 12-bit Words," so does the JVM description say, simply, that the JVM has a Stack. Bytecodes manipulate the Stack.

All JVM instructions consist of a one-byte op-code, followed by zero or more operands. Some operands are longer than one byte. Such operands are stored after the op-code in network byte order, also known as big-endian byte order. That is, the highest-order byte of operand comes first.

I have down-loaded the complete JVM specification, which is available in HTML form off our course Web page at www.mathcs.carleton.edu/faculty/jondich/Courses/cs207_f96/Documents/JavaVM/vmspec-1.html . Go take a look. [Actually, don't go take a look. I kept this document locally during the exam in case of network failure, but for copyright reasons I have deleted it. The final version of the JVM specification is now in print--see http://www.javasoft.com/doc/language_vm_specification.html and http://www.aw.com/cp/lindholm-yellin.html for details.]

Java chips

As you answer Question 1, you will undoubtedly mention performance issues. The performance costs of having an intermediate language between Java and machine language are not unknown to the people at Sun, which is why they will soon release a collection of Java chips. These chips are microprocessors, all of whose native instruction sets are identical to the JVM bytecode instruction set. Like the IBM 360 series (and many other processor families since), the Java chips will offer a range of prices and a corresponding range of performances. But Sun claims at this early date that they will all execute bytecodes faster than, say, a bytecode emulator running on a Pentium.

The cover story in the November 1996 issue of Byte magazine is entitled "Inside Sun's Java Chips: How will they transform computing?" This story is a very interesting read. For reasons that remain somewhat mysterious to me, Carleton's library does not carry Byte, but our departmental library does. There is an issue of the November Byte in the Math/CS lounge. If you read it, please do not remove the magazine from the lounge.

All of this leads us to the heart of this exam.

Question 2

Design a datapath to implement a subset of the JVM instruction set. In particular, your datapath should implement the following instructions: sipush, swap, isub, iadd, ineg, ifeq, ifne, if_icmpeq, and if_icmpne.

You should include in your datapath an instruction memory, and a memory unit for the Stack. You do not need to show the circuitry required for your ALU--just describe what it does in response to its control.

Please hand in a diagram of your datapath (like Figure 5.39 on page 323 of Patterson and Hennessy), a finite-state machine describing your datapath's control (like Figure 5.47 on page 332), and a brief discussion of your design and how it works.

One thing you'll have to do to handle this question in a reasonable amount of time is to cut through the interesting but unimportant (for us) clutter in the JVM documentation. The structure you'll need to deal with for this small subset of the JVM instruction set is quite simple, so don't get bogged down in all the extra goodies in JVM. It's important to be able to read a document starting in the middle.

If your design is better than Sun's, can I have a cut?

Rounding things out

There are so many more things I want to ask you to do! Learn Booth's algorithm, study buses, talk about how to include multiplication in the sample datapaths of Chapter 5, learn about parallel architectures,....

But I'll forbear. Let's finish out the exam with:

Question 3

Do problem 6.3 on page 445 of P and H, and

Question 4

Do problems 7.1 and 7.2 on page 527 of H and P.

Have a good break

You have been a marvellous class. Thanks for going on this ride with me. If you have nothing better to do during break (and I can't imagine a better thing to do), read Chapter 9. See you later.


Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057
(507) 646-4364, jondich@carleton.edu