COS 111, Fall 2000 - Problem Set 4

Problem 1
Suppose that three values x, y, and z are stored in memory at locations 20, 21, and 22 respectively. Write a program in the machine code of the COS 111 processor that adds up these numbers and puts the sum into memory location 25.

There are several ways to write this program. Here is one (the bracketed text is an explanation of what each instruction does):

20 20     { R0 <== Memory[20] }
21 21     { R1 <== Memory[21] }
22 22     { R2 <== Memory[22] }
63 1      { R3 <== R0+R1 }
63 32     { R3 <== R3+R2 }
33 25     { Memory[25] <== R3 }
0  0      { Halt }

Problem 2
A modern processor can execute 300 million instructions per second. If a person types 100 characters per second, how many instructions on average does the computer execute between two consecutive keystrokes? (In other words, how many instructions can the computer afford to execute in dealing with each keystroke?)

     300,000,000 instructions      1 second    
     ------------------------  X -------------- 
           1 second              100 characters


     = 3,000,000 instructions per character

Problem 3
What does the following program (written in assembly language for the COS 111 processor) do?

start:
	SetPc start
	Halt

This program runs forever without terminating. The first instruction (SetPc start) sets the program counter so that it points back again to the first instruction. The result is that the "SetPc start" instruction is executed over and over again, forever. The program never reaches the "Halt" instruction.

This kind of structure is called an "infinite loop" because the program keep going around and around through the same instruction(s) without stopping.

Problem 4
Can you think of a situation where the program from problem 3 would really be useful? If you can, explain what that situation is and why the program is useful in that situation. If you can't think of a situation where it would be useful, then do you think the assembler (the program that translates the assembly code program into machine code) should try to detect such programs and tell the programmer he/she made a mistake?

There's really no use for a program like this that runs forever without producing any visible effect. It would be nice of the assember detected the fact that the program will get stuck in an infinite loop, and warned the programmer.

Although we didn't expect you to know this, we'll see later in the semester that it is not always possible to detect, just by looking at a program, whether that program will loop forever or will eventually terminate. Nonetheless, would be useful for the assembler to warn the programmer in those cases (like this one) where it can tell for sure that the program will get stuck in an infinite loop.

Problem 5
A well-known rule called "Moore's Law" (named for Gordon Moore, a founder of chip-maker Intel) says that processors double in speed about every eighteen months. (Remarkably, this rule has held true since about 1965, through about 23 doublings, or a speed increase of about ten million times.) If processors double in speed and software stays the same, then all programs should run about twice as fast now as they did in early 1999. But almost everybody says that computers seems to do things at about the same speed as they did in 1999. What reasons might explain why the expected speedup hasn't materialized? (Be creative, and give as many plausible guesses as you can think of. There's no single right answer to this question.)

Many explanations are possible. Here are some examples:

• People aren't buying the new, faster processors, but are using the same computers they used before.
• Processors are getting faster, but software is getting less efficient, requiring more and more instructions to do the same job, so the net effect is no speedup.
• Processors are getting faster, but other parts of the computer are not getting faster.
• People spend most of their time waiting for data to download across the network, and making processors faster doesn't help speed that up.
• Computers have gotten so fast that people can't tell the difference; it's like watching a rocket zoom past you and trying to figure out whether it was going 1,000 miles an hour or 2,000 miles an hour.
• Processors are getting faster, but people are running more programs at the same time, so the amount of horsepower devoted to each program hasn't changed.
• Processors are getting faster, but people are using them to write longer documents, download bigger Web pages, and so on. It's like you doubled the horsepower of your pickup truck but then loaded twice as much stuff in the back. You end up going the same speed.