cse240a: Assignments

Homework Policy

Integrity Policy


Assignment 1: Log into and use the class discussion board

This assignment should be completed on your own.

Part 1: Log into the discussion board

Due: October 2

There is a link to the coures discussion board on the course homepage. Your login is your official UCSD user name (i.e., your @ucsd.edu email address without the "@ucsd.edu" part). Password is your PID.

Take some time to explore the discussion boards features. If you like, you can configure it to send everything to you by email, so you don't have to visit the website regularly.

Need an account? If you are enrolled through concurrent enrollment or, for some other reason, you need to take proof enrollment to the ACS help desk (AP&M 1313) to get an account. If you have trouble, send me mail.

Deliverable Post a reply under the "Welcome" message in the administrative forum. You don't neet to hand anything in. Due: October 2

Part 2: Participate in discussion on the web-board during the course

Due: Throughout the quarter

Participation in the discussion board is mandatory. It forms a significant fraction of your class participation grade.

If you have questions about the material in the class, post them to the general discussion forum. Sat and I will hold off on answering the questions for a while to give other student an opportunity to reply.

Posting Guidelines

Deliverable You should be posting to the discussion board about architecture-related topics at least once or twice a week throughout the quarter. The more you post, the more useful the forum will be. You don't need to hand anything else in. Due: Throughout the quarter

Assignment 2: Caching

You are encouraged to work on this assignment in groups of two. If you do work in a group of 2, submit only 1 report (but make sure both names are on it). While you may have your partner do all the work, this will only hurt you when the midterm and final come around so don't do it.

Book Problems

Due: October 16

The following problems are required. They are taken from the 3rd edition of the book (since all the 4th edition solutions are available on the textbook website.

  1. You are building a system around a processor with in-order execution that runs at 1.1GHz and has a CPI of 0.7 excluding memory accesses. The only instructions that read or write data from memory are loads (20% of all instructions) stores (5% of all instructions).
    The memory system for this computer is composed of a split L1 cache that imposes no penalty on hits. Both the I-cache and D-cache are direct mapped and hold 32KB each. The I-cache has 2% miss rate and 32-byte blocks, and the D-cache is write through with a 5% miss rate and 16-byte blocks. There is a write buffer on the D-cache that eliminates stalls for 95% of all writes.
    The 512KB write-back, unified L2 cache has 64-byte blocks and an access time of 15ns. It is connected to the L1 cache by a 128-bit data bus that runs at 266 MHz and can transfer one 128-bit word per bus cycle. Of all memory references sent to the L2 cache in this system, 80% are satisfied without going to main memory. Also 50% of all blocks replaced are dirty.
    The 128-bit-wide main memory has an access latency of 60ns, after which any number of bus words may be transferred at the rate of one per cycles on the 128-bit-wide 133 MHz main memory bus.
  2. A cache may use a write buffer to reduce write latency and a victim cache to hold recently evicted (nondirty) blocks. Would there be any advantage to combining the two intoo a single piece of hardware? Would there be any disadvantages?
  3. Smith and Goodman found that for a given small size, a direct-mapped instruction cache consistently outperformed a fully associative instruction cache using LRU replacement.
  4. Way prediction allows an associative cache to provide the hit time of a direct-mapped cache. The MIPS R10K processor uses way prediction to achieve a different goal: reduce the cost of a chip package.
    The R10K hardware includes an on-chip L1 cache, an on-chip L2 tag comparison circuitry, and an on-chip L2 way prediction table. L2 tag information is brought on chip to detect an L2 hit or miss. The way prediction tables contains 8K 1-bit entries, each corresponding to two L2 cache blocks. L2 cache storage is built externally to the processor package, must be two-way associative, and may have one of several block sizes.
Deliverable The solutions to the above problems either typed-up (highly recommended) or nicely hand-written. Include your name (or names, if working in a group), on all pages. Due: October 16

Assignment 3: Virtual Memory and Basic Pipelining

While this homework is not due until after the midterm, you should attempt to complete it before then as some of these topics (namely, virtual memory) will be covered on that exam.

Problems 2 - 4 come from the 3rd edition of our class textbook.


Due: November 13

  1. You are interested in calculating the access time of a 128KB, 4-way set associative write-back cache with 32 byte blocks. As you learned in class, there are various ways to index and tag your cache in relation to your virtual memory system. Consider that you have the following information about your system:

    Assume that all other parts are insignificant to the access time of the cache.

    For the following configurations, calculate the amount of time it takes to get data from the cache on a load hit. Assume that your page size is 4KB. Be sure to explain your answers; just writing down numbers won't get you credit even if they end up being correct.

    1. A physically-indexed, physically-tagged cache
    2. A virtually-indexed, virtually-tagged cache
    3. A virtually-indexed, physically-tagged cache
    4. A physically-indexed, virtually-tagged cache

  2. Use the following code fragment:
    Loop: LD R1,0(R2)
      DADDI R1,R1,#1
      SD 0(R2),R1
      DADDI R2,R2,#4
      DSUB R4,R3,R2
      BNEZ R4,Loop

    Assume that the initial value of R3 is R2 + 196.

    Throughout this exercise use the classic RISC five-stage integer pipeline and assume all memory accesses take 1 cycle.

  3. For these problems, we will explore a pipeline for a register-memory architecture. This architecture has two instruction formats: a register-register format and a register-memory format. There is a single memory addressing mode (offset + base register).

    There is a set of ALU operations with the format:

        ALUop Rdest, Rsrc1, Rsrc2


        ALUop Rdest, Rsrc1, MEM

    where the ALUop is one of the following: Add, Subtract, And, Or, Load (Rsrc1 ignored), Store. Rsrc and Rdest are registers. MEM is a base register and offset pair.

    Branches use a full compare of two register and are PC-relative. Assume that this machine is pipelined so that a new instruction is started every clock cycle. The following pipeline (used in the VAX 8700) is:


    The first ALU stage is used for effective address calculation for memory references and branches. The second ALU cycle is used for operations and branch comparison. RF is both a decode and register-fetch cycle. Assume that when a register read and a register write occur in the same clock, the write data is forwarded.

  4. We will now add support for register-memory ALU operations to the classic five-stage RISC pipeline. To offset this increase in complexity, all memory addressing will be restricted to register indirect (i.e. all addresses are simply a value held in a register; no offset or displacement may be added to the register value). For example, the register- memory instruction ADD R4,R5,(R1) means add the contents of register R5 to the contents of the memory location with address equal to the value in register R1 and put the sum in register R4. Register-register ALU operations are unchanged. Answer the following for the integer RISC pipeline:
Deliverable The solutions to the above problems either typed-up (highly recommended) or nicely hand-written. Include your name (or names, if working in a group), on all pages. Due: November 13

Assignment 4: End of the Term Pseudo-Assignment

This assignment is a pseudo-assignment: you should do it but you do not have to turn it in. The answers will be available for you to look at but you should attempt the problems first as this will be a better aid in studying for the exam.

Part 1 is up first and contains problems from the 4th edition of the book. Part 2 will be available in a couple days and will include questions from other sources.

Part 1: Problems from the 4th edition

Due: December 14

The following problems come from the 4th edition of the textbook (the official edition for the class). Solutions are available on the textbook companion website, available here.

Deliverable As this is only a pseudo-assignment, you do not have to turn anything in. Due: December 14

Part 2: Misc. Problems

Due: December 14

coming soon...

Deliverable As this is only a pseudo-assignment, you do not have to turn anything in. Due: December 14