Posted: May 28th, 2015

Practical Exercises

Practical Exercises

The Von Neumann Architecture

1004ICT— Foundations of Computing Systems
School of ICT
Griffith University
Semester 1, 2015
Problem Solving Assignment – Computer Systems

Due by 5pm Friday 29th May 2015 (end of week 12)

Assignment Description
The assignment will test your understanding of the operation of a computer system at a low level via some practical problem solving exercises and a written report describing the solutions.
You will need to write a report describing the von Neumann architecture and other low level concepts like compilers and instruction sets. You will also need to solve some practical problems by writing programs using a provided instruction set. These programs will be demonstrable in a provided emulator and you must also write a document detailing:
•    How they work, with diagrams or pseudo-code and examples of how partial results are obtained, or how iterations (loops) are controlled.

•    How to use them, including a description of where input should be placed and what format it should be in.
As well as submitting the documentation and the source code, you must also submit a design spreadsheet for each question (template provided). This spreadsheet should follow a similar style to the 2 examples provided, where each row in the template corresponds to a row of memory (16 bits / 2 bytes) in the emulator.
It is important to note that submission of this assignment is a requirement for passing the course.

Submission Requirements
Your assignment must be submitted online via L@G under the assessment page. Your submission should include a word document containing your written responses to the theory questions as well as your technical explanation of your practical solutions. For each practical problem, you should also submit a VEM file that has been saved from the emulator and contains the program bytecode for each practical problem. For each question, leave the appropriate bits for input set to blank and make sure you provide instructions as to how to provide input for your program. Make sure you follow the question guidelines that specify how the input should be set up. Your files should be named as shown below:

s1234567_VonNeumann_Report.docx
s1234567_MultipleAdd.vem
s1234567_MultipleAdd-Design.xls
s1234567_Average.vem
s1234567_Average-Design.xls

Theory – The Von Neumann Architecture (50 marks)
Question 1: What is the von Neumann architecture? (25 marks, ~300 words)
Provide an overall explanation of the von Neumann architecture, the Fetch-Execute Cycle and the stored program concept. Explain how it functions. Focus on what it does, and how it does it.

Question 2: Explain the von Neumann bottleneck (worth 10 marks, ~200 words)
Explain the expression “the von Neumann bottleneck.” Investigate and mention if there are any solutions for this.

Question 3: What do compilers do? (worth 15 marks, ~250 words)
Investigate and describe the role of compilers in enabling programming in high-level programming languages rather than the Instruction Set of a particular CPU.

Practical Exercises (150 marks)

All your programs must start with an unconditional BRANCH that is placed at memory position 0 and moves the program counter to a later memory address so the inputs of the program can be placed from memory position 2 onwards. Each question will specify how much room is needed for the input data.
It is highly recommended that you start with a design spreadsheet as this can often make solving the problem easier as you don’t have to worry about binary op codes and numbers. You must submit a design spreadsheet for every question.

Question 1: Multiple Add (50 marks)
Revisiting our multiple add program, you must write a program that adds multiple numbers together. As memory is finite, it is assumed that the number of numbers will be less than 20, each number taking up 8 bits. The numbers can be positive or negative, but it is the responsibility of the person supplying numbers that if one value is negative, the person must convert it to two’s complement when placing it in memory (which is how the emulator represents negative numbers).
The Branch instruction will be at 0, and the input numbers will be between positions 2 and 20. The size of the input data should be stored in memory position 22, and the calculated sum of the numbers stored at position 24. Note, there may be more numbers than there are registers, so you will not necessarily be able to load all the numbers into registers. Instead, you will need to keep a running tally, and iterate through memory addresses. The resulting sum should be stored in memory at some location (possibly after the program code) and this location should be specified in your documentation.

Question 2: Average (50 marks)
Your task for this problem is to build a program that computes the average of a set of numbers. The valid sizes for the set of numbers are 2, 4, 8, 16 and 32. The numbers can be positive or negative, but it is the responsibility of the person supplying numbers that if one value is negative, the person must convert it to two’s complement (which is how the emulator represents negative numbers).
The Branch instruction will be at 0, and the input numbers will be between positions 2 and 32. The size of the input data should be stored in memory position 34. The resulting output should be stored in memory at location 36.
It may be worth starting by writing a program that works just for 2 numbers, and then modify it to work just for 4 numbers. Then see if you can write one that can work for 2 or 4 depending on the input number. Once this is done, changing it to work for 8, 16 or 32 should be trivial.

Question 3: Multiply (50 marks)
The final problem involves building a program that can multiply two numbers in binary, each no larger than 4 bits. The program must use one of the registers as the running total, and use the SHIFT and ADD instructions of the Instruction Set of the textbook and the emulator for the corresponding shift and add operations of the Egyptian method for multiplication.
After the branch at address 0, the 2 input numbers should be stored at address 2 and 3, the output of the program stored at address 4 and your program code can start at address 6. As the result of 15(1111) * 15(1111) is 225(11100001), you will not have to worry about buffer overflow.

Bonus question: Signed Multiplication (20 marks)
Modify your Multiply program to check the signs of the inputs and store the signs separately, convert everything to positive numbers, multiply the positive numbers and adjust the sign at the end (if needed). For this program, the input numbers will be 5 bits big, with the left-most bit being the sign bit. This gives your output a possible range of -225 to +225 which cannot be stored in an 8 bit register. For this problem, you do not have to deal with overflow. You may assume the input multiplication will total in the range of -127 -> +127.
This question is worth 20 BONUS marks. If you lose marks in other areas, the marks from this question can be used to earn them back. You cannot earn over 250 marks.

Technical Report (50 marks)
In addition to providing solutions to the practical questions, you should write a report that details how each problem functions. Begin with a formal specification of what the program does that could be expressed as enumerated steps in sequence or as pseudo-code in a structured way similar to Java (i.e. using appropriate indenting). This should be followed by a description of how the solution is intended to solve the problem (how your solution approaches the problem from a technical standpoint). You should also provide user instructions that describe how and where input should be placed in your program and what format it should take (so that someone who did not have access to this assignment sheet would know how to use your program. You should also specify where the output will be located.
Regardless of whether or not you submit .VEM files for the questions, you MUST submit a description of these problems and a potential solution. You only need to submit documentation for the bonus question if you attempt it.