Cost (4 points)

P+H problems (4 points each): 1.51

Performance (32 points)

P+H problems (4 points each): 4.1, 4.2, 4.3, 4.8, 4.12, 4.21 (on the CD), 4.22 (on the CD), 4.25 (on the CD)

Instruction Set Architecture (24 points)

P+H problems (4 points each): 2.30, 2.31, 2.38, 2.47, 2.52 (on the CD), 2.53 (on the CD)

R372 Assembly Programming (40 points)

In CSE372 this semester, you will design and test a simple microprocessor for a simple MIPS-like ISA, R372. Before building this processor, you will write some programs using this ISA. This will help you understand how the ISA works and give you some programs on which to test your processor design. The link above also contains descriptions of tools (assembler, simulator) you can use to help write these programs. For this assignment, you are to write two programs.

search: stringsearch. The input data memory image consists of two NULL terminated string. The first string begins at address (hex)8000. The second string begins after the first string ends. You are to write two procedures.

• STRLEN takes a pointer to a string in R0, and returns the length of the string in R4.
• SEARCH takes a pointer to the first string in R0, and the length of the string in R2, and returns the index of the first string within the second in R4.

btree: binary tree. The input data memory image consists of an array of N+1 words. The first word is at address (hex)8000 and contains the number N. The next N words (8001 to 8000+N) are the array elements. Your job is to write three procedures.

• BTREE_BUILD takes no arguments. It iterates over the array and out of it constructs a sorted binary tree whose root is at the address (hex) C000. Each binary tree node is 4 memory words long. The first element is the value. The second element is a pointer to the left subtree which contains all elements smaller than the value. The third element is a pointer to the right subtree which contains all the elements larger than the value. The fourth element is 0. Notice, the easiest way to do this is to lay out the tree in memory in the same way the original array is layed out. That is, the tree node corresponding to array element N starts at C000+(N*4). This way you don't have to worry about building an explicit malloc routine and the only thing you have to do is figure out the pointer linkage.
• BTREE_PREORDER takes no arguments. It sets a global index to the 8001 in register R2 and initializes a pointer to the root of the tree in register R3. It then calls BTREE_PREORDER_REC.
• BTREE_PREORDER_REC is a recursive function that takes a pointer to a subtree as an argument in register R3. It performs a pre-order traversal (effectively, a sorted traversal) of the tree. At each node, it stores the value at the address R2, and increments R2.

To help you, I put sample implementations of some programs in the directory ~amir/cse371/r372/mbench/. Here you can find the programs fib (recursive fibonacci), matrix (matrix multiplication), and bubble (bubblesort).

For this part of the assignment, you must turn in a printout of your assembly code, but also an electronic copy of your .a files. The TAs will announce to the newsgroup how they want this part turned in. Your grade for this part of the assignment will consist of your program producing the correct output for a test case of our choosing. We will not debug your programs for you.

Hint: write pseudo-code in C or Java first. Then translate it to R372 using the control idioms we covered in class.

Don't procrastinate: It took me about 30 minutes to write the SEARCH routines and about an hour and a half to write the BTREE routines. You shouldn't be surprised if it takes your 5 times as long.