CSE 378 Homework 1 - Part 3
You're going to write a MIPS simulator, that is, a program that can simulate the execution of MIPS instructions. More precisely, your simulator handles exactly six instructions: , , , , , and . (The last is not an actual MIPS instruction, but is useful for obvious reasons. It's part of the Cebollita instruction set.)
Your program takes as input a program written using only those six instructions. You execute each of the instructions, in order, halting when you encounter a instruction. As you execute each instruction, you update values stored in the simulator's registers. That's pretty much all there is to it.
Your simulator happens to be written in MIPS assembler as well (or, actually, the subset of MIPS assembler that Cebollita implements).
Input to your program is a list of instructions, encoded as decimal integer representations of the 32-bit machine instructions. For example: 5 537395212 554237972 554303505 19552293 1073741848 The first integer indicates how many instructions follow. The integers that come next are instructions, written in decimal (because the only routine available to read an integer from assembler requires decimal input). They correspond to the assembler program, and the hex encoded machine instructions, shown in the following output: 00000000 0x2008000c: addi $t0, $0, 12 00000004 0x21090014: addi $t1, $t0, 20 00000008 0x210a0011: addi $t2, $t0, 17 0000000c 0x012a5825: or $t3, $t1, $t2 00000010 0x40000018: halt
None. We'll run your program in Cebollita and examine the contents of the simulated registers when it halts.
Having a look at skeleton code will probably make things somewhat less confusing. At the top, it allocates space to hold the program to be simulated and to keep the values in the simulated registers. In the section, the code begins by reading in the input: first the number of instructions in the input and then the instructions themselves. It then initializes the simulated PC, as a pointer into the memory holding the program to be simulated, and goes into a loop fetching instructions and updating the simulated PC to mimic sequential flow control. The skeleton doesn't actually simulate the effect of each instruction it fetches, though - that's what you'll implement. Instead, it simply checks whether or not the instruction just fetched is a . If not, it fetches the next instruction. Otherwise, the skeleton program itself halts.
Building Your Application
There are two steps:
You can now execute in the Cebollita simulator: $ java dbg.UI a.exe
- Assemble: $ java asm.parser mipsSim.s That produces file .
- Link: $ java asm.Linker prologue-standalone.o mipsSim.o (The order of the operands is significant.) That produces .
Preparing Test Input
It's a bit clunky to prepare the input to your simulator. The basic process is
- Create a small assembler program () that uses only the instructions your simulator supports.
- Assemble it to produce a file.
- Use to dump the instructions in hex.
- Convert the hex to decimal.
- Run your simulator and type in the input.
That's so painful that we're providing some automation to help. The distribution (see below) comes with a simple - it should be intelligible from what you've seen in CSE 303. The has four useful targets:
You can (and should) use the even if you're not currently 100% comfortable with - it's easy, just try it. Your system must have installed, though, to use all the facilities provided.
will assemble and link your simulator ().
will assemble , run on it to get the hex coding of the instructions, then run a program () to extract the hex instructions and turn them into decimal, and finally create a file () that is suitable for feeding as input to your simulator.
will build your simulator, build the input file, and then invoke the Cebollita simulator to run your simulator, providing it with input from . (The switch to causes it to read input from the named file, rather than from the keyboard.)
deletes all intermediate files.
The Cebollita assembler doesn't implement everything described in the text. In particular, it doesn't implement pseudo-instructions - instructions that are not actually supported by the hardware, but for which the assembler inserts one or two instructions that achieve the same effect. Examples are things like , , and . It also doesn't implement the full MIPS instructio set. It's very unlikely, though, that you'll want to use an instruction that isn't available.
I would guess that the vast majority of you won't come across any distinctions between what the book describes and what Cebollita implements. If something won't assemble, though, the Cebollita documentation is the place to look for exactly what it supports.
You can (and should!) assume in your code that the input is always error free - there are 10 or fewer instructions, and each is one of the six your simulator supports.
This is terrible programming practice, but makes life a lot easier, especially when hand coding assembler. (Never, ever, make this assumption again, though. I hang my head in shame that we need it to make this assignment reasonable.)
Downloading Starter Files
Download hw1programming.tar.gz, and save it in the directory you want to work in. Expand it like this: $ tar xzf hw1programming.tar.gz That will produce files , , , , and .
How To Turn In
CS 254 - Computer organization and assembly language programming
Spring/2002Classes: TR 05:15-06:30 p.m., Maria Sanford 221
Instructor: Dr. Zdravko Markov, MS 203, (860)-832-2711, http://www.cs.ccsu.edu/~markov/, e-mail: email@example.com
Office hours: TR 8:00pm-9:00pm., MW 6:30pm-8:00pm, or by appointment
Catalog data: Prereq.: CS 151 or MATH 471. Concepts of assembler language, machine language, macro-instructions, subroutines, program checkout, interrupt structure of assemblers and use of operating system. No credit given to students with credit for MATH 472. [c]
Prerequisites: CS 151 or MATH 471.
Description: This course is an introduction to computer architecture at the assembly language level. The course is based on the MIPS processor, a simple clean RISC processor whose architecture is easy to learn and understand. The course covers binary representation, elements of machine organization, machine language, MIPS assembly language programming, subroutines, interrupts, and basics of operating systems.
Class Participation: Active participation in class is expected of all students. Regular attendance is also expected. If you must miss a test, try to inform the instructor of this in advance.
Honesty policy: It is expected that all students will conduct themselves in an honest manner (see the CCSU Student handbook), and NEVER claim work which is not their own. Violating this policy will result in a substantial grade penalty, and may lead to expulsion from the University. However, students are allowed to discuss projects with others and receive debugging help from others.
Programming: This course teaches assembly programming on a simulator (called SPIM). This is a MIPS machine simulator available as a free software for Unix, DOS, and Windows. There will be 5 programming assignments requiring the use of the SPIM simulator.
Tests: There will be two midterm exams and a final. They will include questions from the textbook, questions from the lectures, and questions from the assignments.
Required textbook: John Waldron, Introduction to RISC Assembly Language Programming, Addison-Wesley, 1999, ISBN 0-201-39828-1.
Required software:SPIM simulator: A free software simulator for running MIPS R2000 assembly language programs available for Unix, DOS, and Windows.
Author's web page of Introduction to RISC Assembly Language Programming: Example programs, lecture slides and other resources Publisher's Web page of Introduction to RISC Assembly Language Programming, Addison-Wesley. SPIM simulator: A free software simulator for running MIPS R2000 assembly language programs available for Unix, DOS, and Windows. Documentation for the Windows interface to SPIM: postscript or Adobe PDF file. Assemblers, Linkers, and the SPIM Simulator (Adobe PDF file): Appendix A of Hennessy & Patterson, Computer Organization and Design: The Hardware/Software Interface, Second Edition, Morgan Kaufmann Publishers, Inc., 1997. VAX instruction set (Adobe PDF file) MIPS Web Site Ghostscript, Ghostview and GSview Postscript to PDF Converter
Grading will be based on three tests (two midterms and a final), 2 assignments and 4 programming projects (see the schedule below for the corresponding point grades). The letter grades will be calculated according to the following table:
Tentative schedule of classes, assignments and tests:
- Computer architecture = Instruction set architecture + Machine organization. Read Ch. 1.
- Representing information in computers: number systems, bits, bytes, binary numbers, characters. Read Ch. 2.
- Representing numbers in computers: integers and floating point numbers. Computer arithmetic.
- MIPS computer organization and the SPIM simulator. Read Ch. 3.
- Assignment 1 due (5 pts.). MIPS assembly language programming: syntax and semantics. Read Sections 4.1 - 4.3.
- Executing an assembly language program in SPIM: edit, assemble and test cycle. Read Section 4.4.
- I/O - read and print numbers: overflow, underflow and range of the numbers in MIPS.
- Load, store, move. Read Section 4.5.
- Pseudo-instructions. Integer arithmetic. Read Sections 4.6 - 4.9.
- Assignment 2 due (5 pts.). More integer arithmetic: convert string to integer and random number generator.
- Test 1 (15 pts.): Load, store, move, integer arithmetic, floating point representation (IEEE 754 floating point format).
- Control flow structures - branches: leap year example. Read Sections 5.1 - 5.3.
- Control flow structures - loops: Euclid's algorithm and string length. Read Sections 5.4 - 5.5.
- Using random numbers: Monte Carlo estimation of PI.
- Project 1 due (10 pts.). Addressing modes. Implementing arrays. Read Ch. 6.1 - 6.6.
- Minimal and maximal element of an array. Read Section 6.7.
- Sorting arrays (bubble sort).
- Indexed addressing: string manipulation. Read Ch. 6.8 - 6.10.
- Project 2 due (10pts.). Logical, shift and rotate instructions: convert integer to bin and hex by using a mask. Read Ch. 7.
- Implementing sets by logical instructions.
- Using sets: Prime numbers - the sieve of Eratosthenes.
- Test 2 (15pts.): Loops and arrays.
- Project 3 due (10pts.). Stacks: reversing a character string and reverse polish calculator. Read Sections 8.1 - 8.2
- Procedure calls and parameter passing. Read Section 8.1 - 8.5.
- Stack frames. Factorial function. Sorting strings by selection sort. Read Section 8.6 - 8.7, Assemblers, Linkers, and the SPIM Simulator.
- Linked lists.
- Recursive programming: binary trees.
- Project 4 due (10pts.). Exceptions and interrupts.
- Test 3 (20 pts.): Procedures, and linked lists.
CS 254 - Class #1Computer architecture = Instruction set architecture + Machine organization
- Levels of abstraction in describing computers
- Computer architecture = Instruction set architecture + Machine organization
- Instruction set the software hardware interface
- Levels of computer architecture in more depth
- Operating system
- Machine language
- Assembly language
- Higher level languages
- Instruction set architecture:
- Data type and structures: encodings and machine representation
- Instruction set
- Instruction formats
- Addressing modes and accessing data and instructions
- Exception handling
- Instruction set processing
- I/O System
- Digital design
- Circuit design
- Processor: datapath and control
- I/O system
CS 254 - Class #2Representing information in computers
- Bits, bytes, words and memory organization
- Number systems
- Binary and hexadecimal numbers, conversions
- Representing textual information - character encoding, lexicographic order.
CS 254 - Class #3Representing numbers in computers
- Unsigned integers
- Signed numbers, two's complement representation, range of integers
- Integer arithmetic
- Floating point numbers
- We need a way to represent:
- numbers with fractions, e.g., 3.1416
- very small numbers, e.g., .000000001
- very large numbers, e.g., 3.15576 × 10 9
- sign, exponent, significand: (-1)^sign × significand × 2^exponent
- more bits for significand gives more accuracy
- more bits for exponent increases range
- IEEE 754 floating point standard:
- single precision: 8 bit exponent, 23 bit significand
- double precision: 11 bit exponent, 52 bit significand
- normalized representation
- implicit leading 1
- exponent is biased: exponent in [0..0 (most negative), 1..1 (most positive)]
- bits of the significand represent the fraction between 0 and 1.
- (-1)^S * (1 + s1*2^-1 + s2*2^-2 + ...) * 2^(exponent-bias)
- all 0's is smallest exponent all 1s is largest
- bias of 127 for single precision and 1023 for double precision
- summary: (-1) sign × (1+significand) × 2^(exponent - bias)
- decimal: .75 = 3/4 = 3*2^(- 2)
- binary: 11*2^(-2) = 1.1* 2^(1)
- sign = 1
- significand = 10000000000000000000000
- exponent = -1 + 127 = 126 = 01111110
- IEEE single precision: 10111111010000000000000000000000
- Comparing floating point numbers
CS 254 - Class #4MIPS computer organization and the SPIM simulator
- MIPS processor:
- Registers 0-31
- Coprocessor 0 (traps and memory)
- Coprocessor 1 (FPU)
- Register + immediate
- PC relative (branches)
- Simulation of a virtual machine
- User interface
- Operating system services
CS 254 - Class #5MIPS assembly language programming
- Structure of the program (data segment, text segment)
- MIPS assembler syntax (Assemblers, Linkers, and the SPIM Simulator, pages 49-53):
- Instructions: format and pseudo instructions
CS 254 - Class #6Executing an assembly language program in SPIM
- Starting PCSpim: settings
- Loading and executing a program
- Edit, assemble and test cycle:
- Syntax errors
- Run-time errors
- single stepping control
Lecture slides (Postscript)
CS 254 - Class #7I/O - read and print numbers: overflow, underflow and range of the numbers in MIPS
1. Read and print integers: overflow and range of the integers1.1. The program (slides in Postscript)
1.1. Example run (explain the results)
2. Read and print floating point numbers: overflow and underflow2.1. The program
2.2. Example run (explain the results)
CS 254 - Class #8Load and Store: 256-numbering system
1. Converting a decimal into 256-numbering system1.1. The Program
1.2. Example run
2. Converting to decimal a number in 256 numbering system2.1. The Program
2.2. Example run
CS 254 - Class #9Integer arithmetic: convert Celsius to Fahrenheit
# We use here two pseudo-instructions - mul and div
CS 254 - Class #10Convert String to integer
Random number generator
CS 254 - Class #11Control flow structures - branches: leap year example (draw a flowchart)
CS 254 - Class #12Control flow structures - loops
1. Euclid's algorithm. See an applet implementation of Euclid here. More about Euclid can be found here.
2. Calculating string length
CS 254 - Class #14Monte Carlo estimation of PI
CS 254 - Class #15Implementing arrays
CS 254 - Class #16Using arrays: minimal and maximal element
CS 254 - Class #17Sorting arrays
CS 254 - Class #18Indexed addressing: using a pseudo-insturction with base addressing
1. Counting occurrences of a character in a string
2. Reading and copying strings
CS 254 - Class #19Logical, shift and rotate instructions
1. Convert integer to binary
2. Convert integer to hexadecimal
CS 254 - Class #20Implementing sets by logical instructions