Date: Mon, 02 Dec 1996 15:10:05 GMT Server: NCSA/1.4.2 Content-type: text/html CSE567 Homework Assignment #4

CSE 567: Principles of Digital Systems Design

Carl Ebeling, Fall 1996


Homework 4

Distributed: Monday Oct. 28 - Due Wed. Nov. 6, in class


You are to work together as teams on Homework 4. Please look at the problems individually first and sketch possible solutions and questions. Then meet together and formulate solutions to each if you can, and assign the writeup to one or more team members. Then meet again to collate and review your solutions before you hand them in. The whole team is responsible for understanding the solution to all problems.

For problems involving Verilog code, hand in your code and your simulation log (or at least part of it if it's really long).

  1. [Leiserson 29.2-1]
  2. [Leiserson 29.2-2]

  3. Let's say we have a set of N clients requesting service at the same time, only one of which we can service. We can use a round-robin approach to decide who next gets serviced. The N clients are put in some order, C_1 to C_N, and two bits are associated with each client. The first bit indicates whether the client is requesting service and the second bit indicates whether this client was the last client to be serviced. When choosing the next client to service, we start at the last client serviced and find the next requesting client.

    Design a circuit based on parallel-prefix to implement the round-robin protocol. Assume that once you get to the end of the list of clients, something happens to restart the operation from the beginning. Define your operator, show that it is associative, and sketch the resulting circuit.

    Extra credit: Can you solve this problem if we place the clients in a circle, with no start or end, instead of a list?

  4. Show that the conditional sum operator defined in class is associative. Design the conditional sum adder for an 8-bit adder. Write a verilog program for this adder and simulate it to show that it works correctly.

  5. Show that the delay of the carry-select adder is O(N^1/2). (root N)

  6. Take your sorting circuit from Homework #3 and turn it into a pipelined sorter by inserting the appropriate registers. Model delay using the unit-delay model and calculate the clock period. Simulate your circuit and show that it works correctly.

  7. Design a fast accumulator circuit which adds up a list of 8-bit numbers presented sequentially, one per clock cycle. Your circuit should have two inputs, Data and Start, and two outputs, Sum and Valid. Start is asserted on the cycle that a new list of numbers starts. Valid is asserted on the cycle that the sum of the last list of numbers is valid. That is, it may take more than one cycle after a list of numbers has been entered to generate the final sum. Implement your circuit using Verilog using the unit-delay model to model the circuit delays. Simulate your circuit, showing how fast it is and that it works.

ebeling@cs.washington.edu