The purpose of this assignment is to help you learn about computer architecture and assembly language programming. It also will give you the opportunity to learn more about the GNU/Unix programming tools, especially bash, emacs, gcc217, gprof, and gdb for assembly language programs.
The assignment consists of two parts. We encourage you to complete Part 1 during the first week of the assignment period.
Part 2f, as defined below, is the "on your own" part of this assignment. That part is worth 12% of this assignment.
The Unix operating system has a command named wc (word count). In its simplest form, wc reads characters from the standard input stream until end-of-file, and prints to the standard output stream a count of how many lines, words, and characters it has read. A word is a sequence of characters that is delimited by one or more white space characters.
Consider some examples. In the following, a space is shown as s and a newline character as n.
If the file named proverb contains these characters:
Learningsissan treasureswhichn accompaniessitsn ownerseverywhere.n --sChinesesproverbn
then the command:
$ wc < proverb
prints this line to the standard output stream:
5 12 82
If the file proverb2 contains these characters:
Learningsissan treasureswhichn accompaniessitsn ownerseverywhere.n --sssChinesesproverb
(note that the last "line" does not end with a newline character) then the command:
$ wc < proverb2
prints this line to standard output:
4 12 83
The file mywc.c in the /u/cos217/Assignment5 directory contains a C program that implements the subset of the wc command described above. Translate that program into assembly language, thus creating a file named mywc.s. It is acceptable to use global (i.e. bss section or data section) variables in mywc.s, but we encourage you to use local (i.e. stack) variables instead. Your assembly language program should have exactly the same behavior (i.e. should write exactly the same characters to the standard output stream) as the given C program.
Make sure you test your assembly language program thoroughly. To do that, you should create multiple data files, run the given C program on those files, run your assembly language program on those files, and compare the output generated by the two programs. Remember to do statement testing, boundary condition testing, and stress testing, as described in the "Testing" lecture and in our Kernighan and Pike textbook.
We recommend that you create Bash shell scripts to automate your testing. A Bash shell script is simply a text file that contains commands, and that has been made executable via the chmod command, for example, chmod 700 testmywc. Your script might build a mywcc program from the given C code, build a mywcs program from your assembly language code, execute both programs, capture the output in files, and compare the files by calling the diff command. Feel free to use the testdecomment and testdecommentdiff Bash shell scripts from Assignment 1 as models.
Many programming environments contain modules to handle high-precision integer arithmetic. For example, the Java Development Kit (JDK) contains the BigDecimal and BigInteger classes. Of course you created such a module for the previous assignment.
The Fibonacci numbers are used often in computer science. See http://en.wikipedia.org/wiki/Fibonacci_numbers for some background information. Note in particular that Fibonacci numbers can be very large integers.
This part of the assignment asks you to use write a minimal but fast high-precision integer arithmetic module in assembly language, and use it to compute large Fibonacci numbers.
BigInt Objects Using C CodeSuppose you must compute Fibonacci number 500000, that is, fib(500000)...
The /u/cos217/Assignment5 directory contains a C program that computes Fibonacci numbers. It consists of two modules: a client module and a BigInt ADT.
The client consists of the file fib.c. The client accepts an integer n as a command-line argument, validates it, and computes and prints fib(n) to stdout as a hexadecimal number. It prints to stderr the amount of CPU time consumed while performing the computation. The client module delegates most of the work to BigInt objects.
The BigInt ADT performs high precision integer arithmetic. It is a minimal ADT; essentially it implements only an "add" operation. The BigInt ADT consists of four files:
bigint.h is the interface. Note that the ADT makes five functions available to clients: BigInt_new, BigInt_free, BigInt_random, BigInt_writeHex, and BigInt_add.
bigint.c contains implementations of the BigInt_new, BigInt_free, BigInt_random, and BigInt_writeHex functions.
bigintadd.c contains an implementation of the BigInt_add function.
bigintprivate.h is a "private header file" -- private in the sense that clients never use it. It allows code sharing between the two implementation files, bigint.c and bigintadd.c.
The /u/cos217/Assignment5 directory also contains a file named testadd.c. You can use testadd.c to build programs that test the code that you write in subsequent parts of this assignment.
Study the given code. Then use testadd.c, bigint.c, and bigintadd.c to build a testadd program. Run the testadd program.
Build a fib program consisting of the files fib.c, bigint.c, and bigintadd.c, with no optimizations. Run the program to compute fib(500000). In your readme file note the amount of CPU time consumed.
BigInt Objects Using C Code Built with Compiler OptimizationSuppose you decide that the amount of CPU time consumed is too large. You decide to command the compiler to optimize the code that it produces...
Build the fib program using optimization. Specifically, specify the -D NDEBUG option so the preprocessor disables the assert macro, and the -O3 option so the compiler generates optimized code. Run the resulting program to compute fib(500000). In your readme file note the amount of CPU time consumed.
Suppose you decide that the amount of CPU time consumed still is too large. You decide to investigate by doing a gprof analysis to determine which functions are consuming the most time...
Perform a gprof analysis of the code from Part 2b. Store the textual report in a file named gprofreport. Save the file; as described later in this document, you should submit that file.
BigInt Objects Using Assembly Language CodeSuppose, not surprisingly, your gprof analysis shows that most CPU time is spent executing the BigInt_add function. In an attempt to gain speed, you decide to code the BigInt_add function manually in assembly language..
Manually translate the C code in the bigintadd.c file into assembly language, thus creating the file bigintadd.s. You should not translate the code in other files into assembly language.
Your assembly language code should store all of the BigInt_add function's local variables in memory. It also should store the BigInt_larger function's local variable in memory.
Note that assert is a parameterized macro, not a function. (See Section 14.3 of the King book for a description of parameterized macros.) So assembly language code cannot call assert. When translating bigintadd.c to assembly language, simply pretend that the calls of assert are not in the C code.
Build a testadd program consisting of the files testadd.c, bigint.c, and bigintadd.s. Run the program, and compare its output to the output of the testadd program from Part 2a. Thereby make sure that the code in your bigintadd.s file is correct.
Build a fib program consisting of the files fib.c, bigint.c, and bigintadd.s using the -D NDEBUG and -O3 options. Run the program to compute fib(x) for various values of x, and make sure it writes the same output as the program built from C code does. Finally, run the program to compute fib(500000). In your readme file note the amount of CPU time consumed.
BigInt Objects Using Optimized Assembly Language CodeSuppose, to your horror, you discover that you have taken a step backward: the CPU time consumed by your assembly language code is approximately the same as that of the non-optimized compiler-generated code! So you decide to optimize your assembly language code...
Manually optimize your assembly language code in bigintadd.s, thus creating the file bigintaddopt.s. Specifically, perform these optimizations:
Store all local variables (but not parameters) in registers instead of in memory. Remember that assembly language functions must handle the EBX, ESI, and EDI registers with special care.
"Inline" the call of the BigInt_larger function. That is, eliminate the BigInt_larger function, placing its code within the BigInt_add function.
Build a testadd program consisting of the files testadd.c, bigint.c, and bigintaddopt.s. Run the program, and compare its output to the output of the testadd program from Part 2a. Thereby make sure that the code in your bigintaddopt.s file is correct.
Build a fib program consisting of the files fib.c, bigint.c, and bigintaddopt.s using the -D NDEBUG and -O3 options. Run the program to compute fib(x) for various values of x, and make sure it writes the same output as the program built from C code does. Finally, run the program to compute fib(500000). In your readme file note the amount of CPU time consumed.
Can you write assembly language code that is approximately as fast as the optimized code that the compiler generates? That is, can you approximately tie the compiler?
BigInt Objects Using Highly Optimized Assembly Language CodeFinally, suppose you decide to optimize your assembly language code even further, moving away from a statement-by-statement translation of C code into assembly language...
Further optimize your assembly language code in bigintaddopt.s, thus creating the file bigintaddoptopt.s. Specifically, perform these optimizations:
Factor as much code as possible out of the loop.
Use the assembly language loop patterns described in Section 3.6.5 of the Bryant & O'Hallaron book instead of the simpler but less efficient patterns described in precepts.
Instead of using a uiCarry variable (stored in memory or in a register) to keep track of carries during addition, use the "carry" bit in the EFLAGS register. The carry bit is examined and set by the adcl ("add with carry long") instruction.
Feel free to implement any additional optimizations you want. However, your BigInt_add function must be a general-purpose function for adding two given BigInt objects; the function cannot be specific to the task of adding two Fibonacci numbers to generate a third Fibonacci number. In other words, your function must work with the given testadd.c client.
This part is difficult; we will not think unkindly of you if you decide not to do it. To do it properly you will need to learn about the adcl instruction, and about which instructions affect and do not affect the C ("carry") flag in the EFLAGS register.
Hint: When writing bigintaddoptopt.s, the problem is this: How can you preserve the value of the C flag between executions of the adcl instruction? One solution is to save and then restore the value of the EFLAGS register. Another solution is to express the logic such that only instructions that do not affect the C flag are executed between each execution of the adcl instruction.
Build a testadd program consisting of the files testadd.c, bigint.c, and bigintaddoptopt.s. Run the program, and compare its output to the output of the testadd program from Part 2a. Thereby make sure that the code in your bigintaddoptopt.s file is correct.
Build a fib program consisting of the files fib.c, bigint.c, and bigintaddoptopt.s using the -D NDEBUG and -O3 options. Run the program to compute fib(x) for various values of x, and make sure it writes the same output as the program built from C code does. Finally, run the program to compute fib(500000). In your readme file note the amount of CPU time consumed.
Can you beat the compiler?
Develop on hats. Use emacs to create source code. Use gdb to debug.
Do not use a C compiler to produce any of your assembly language code. Doing so would be considered an instance of academic dishonesty. Instead write your assembly language code manually.
We encourage you to develop "flattened" C code (as described in precepts) to bridge the gap between the given "normal" C code and your assembly language code. Using flattened C code as a bridge can eliminate logic errors from your assembly language code, leaving only the possibility of translation errors.
We also encourage you to use your flattened C code as comments in your assembly language code. Such comments can clarify your assembly language code substantially.
You should submit:
Your mywc.s file.
Your gprofreport file.
Your bigintadd.s, bigintaddopt.s and bigintaddoptopt.s files.
A readme file.
Your readme file should contain:
Your name.
A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policies" Web page.
The times consumed by the fib programs, as specified above.
(Optionally) An indication of how much time you spent doing the assignment.
(Optionally) Your assessment of the assignment.
(Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.
Submit your work electronically using the commands:
submit 5 mywc.s submit 5 gprofreport submit 5 bigintadd.s submit 5 bigintaddopt.s submit 5 bigintaddoptopt.s submit 5 readme
We will grade your code on quality from the user's and programmer's points of view. From the user's point of view, your code has quality if it behaves as it should. The correct behavior of your code is defined by the previous sections of this assignment specification.
From the programmer's point of view, your code has quality if it is well-styled and thereby easy to maintain. Comments in your assembly language code are especially important. Each assembly language function -- especially the main function -- should have a comment that describes what the function does. Local comments within your assembly language functions are equally important. Comments copied from corresponding "flattened" C code are particularly helpful.
Your assembly language code should use .equ directives to avoid "magic numbers." In particular, you should use .equ directives to give meaningful names to:
Enumerated constants, for example: .equ TRUE, 1.
Parameter stack offsets, for example: .equ OADDEND1, 8.
Local variable stack offsets, for example: .equ UICARRY, -4.
Structure field offsets, for example: .equ ILENGTH, 0.
Stack offsets at which callee-save registers are stored, for example: .equ EBXOFFSET, -4.
(In bigintaddopt.s and bigintaddoptopt.s) Registers which are devoted to local variables, for example: .equ ISUMLENGTH, %esi.
To encourage good coding practices, we will deduct points if gcc217 generates warning messages.
Your grade for the "on your own" part will be based upon raw performance (How quickly does your code compute fib(500000)?) and style (Does your code contain optimizations that logically should improve performance?).
This assignment was written by Robert M. Dondero, Jr.,
based in part upon suggestions from Andrew Appel,
and with contributions by other faculty members.