Assignment 7, due Mar 7

Part of the homework for 22C:122/55:132, Spring 2003
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

  1. Here is a partial table of the opcode frequencies measured by Clark, Bannon and Keller at Digital Equipment Corporation for the VAX architecture.
    Opcode Execution Frequency
    Instruction Percent
    MOVL 23.1
    BEQL 5.9
    CMPL 5.6
    BNEQ 4.9
    CMPB 2.8
    INCL 2.2
    RET 2.1
    MOVB 1.8
    ADDL2 1.2

    For these instructions, the suffix L indicates a long (32-bit) operand while the suffix B indicates a one-byte operand. Numeric suffixes indicate the number of operands.

    How many bits should have been used for the opcodes on these instructions?

  2. Here is a partial table of the addressing mode frequencies measured by Clark, Bannon and Keller at Digital Equipment Corporation for the VAX architecture.
    Operand Specifier Frequency
    Group Percent
    register 42.9
    displacement 18.5
    literal 13.8
    PC-relative 9.4
    register deferred 7.1
    immediate 3.8
    displacement deferred 3.8
    autoincrement 1.2
    autodecrement 0.7
    PC-relative deferred 0.4
    autoincrement deferred 0.4
    absolute 0.3

    Note that literal mode refers to short literals in the instruction, while immediate mode refers to the use of autoincrement PC mode to fetch a literal from the instruction stream. Deferred modes are what everyone else would refer to as indirect addressing.

    For each mode, show how many bits in the VAX instruction set are used to encode that mode, and show how many bits should have been used, in an instructions set that uses an optimal instruction encoding.

  3. Estimate the speed of the elementary shift-and-add multiply algorithm for a 32-bit machine when implemented in software on a machine supporting double-register shift instructions, and supporting register to register add. Assume all operands are initially in memory, assume it takes one memory cycle per instruction fetch, and assume that the shift instruction sets the carry bit to indicate the last bit shifted out of the operand, and assume that there are one-instruction conditional branch instructions that test the carry bit. Please unroll your loops!