COMP2300

Semester 1, 2007: Assignment 1

Deadline: 12:00 (noon) on Friday 23 March 2007, extended to 10:00 am Mon 26 March

Clarifications added 16/03: these will appear within (*** ...... ***) below.
Clarification added 21/03 (part 3, step 7): this appears within (*** ...... ***) below.
(Please report any errors, mistakes and ambiguities to the course lecturer)

This assignment is worth 12% of your total course mark. It will be marked out of 48 as indicated below.

The estimated time we expect you to spend on this assignment is around 12 hours in total (1 hour per 4 assignment marks).

Submission

This assignment must be submitted electronically. This can be done using the submit comp2300 ass1 ... command.

You should submit a separate file for each part of the assignment you are required to complete. The file names which you should use (and the only ones that will be accepted by the submit command) are:

fun.txt
transpose.c
transpose2.c

As an example of what you should do

    submit comp2300 ass1 transpose.c

All files submitted must include, at the beginning, a completed preamble. The proforma for this can be found in the files:

/dept/dcs/comp2300/public/standard_preamble.txt

You have to copy the preamble from this files into the top of each file you intend to submit, and then complete your details. By submitting a file containing a completed preamble, you are making a declaration about the work you have submitted (see the text of the declaration in the preamble files. If you need to modify the text, e.g. you did in fact receive substantial assistance from another student, you should modify the text to say so).

Any file submitted without a completed preamble will be rejected without being marked.

Note you can submit any file multiple times, including after the deadline has expired. Note that if you submit any file after the deadline your entire submission will be considered as late and will attract a late penalty.

Extensions

See http://cs.anu.edu.au/student/comp2300/assessment.html.

Late Penalties

Late penalties are as follows

How Late	Penalty from 60 Marks
less than 1 hour	-1
between 1 and 6 hour	-2
between 6 and 24 hours (1 day)	-4
between 24 and 48 hours (2 days)	-8
between 48 and 72 hours (3 days)	-16
between 72 and 96 hours (4 days)	-32
more than 96 hours (4 days)	-64 (forget it!)

Note: late penalties apply even if you submit just one file after the deadline.

Plagiarism

See http://cs.anu.edu.au/student/comp2300/assessment.html.

Part 1 - Fundamental Concepts [18 marks]

Please show enough working to demonstrate how each answer is derived. Failure to do so may result in you being awarded no marks for the question concerned (i.e. writing only the correct answer will give you NO marks). Submit your answers as plain text in a file called fun.txt (make sure you have the completed preamble at the beginning).

Let x be the number whose decimal representation is the first digit of YOUR ANU student number multiplied by the second and third digits and then added to the last four digits. For example: stud_number=u1234567 -> x = 1*23 + 4567 = 4590.
1.A What is the base 10 representation of x? [-2 marks if not given or wrong!!]
1.B What is the base 16 representation of x? [1 mark]
1.C What is the binary representation of -x in a 16-bit word, if the value is encoded as a two's complement number? [2 marks]
1.D What is the bit pattern of x (x.0 (base 10) to be precise) when stored as an IEEE single precision floating point number. Represent the resulting 32-bit pattern as an 8 digit hexadecimal number. [3 marks]
1.E Let x' be the number derived from taking the hexadecimal number from 1.B and padding digits O (base 16) to the right until the result is 8 hex digits long (and the leftmost digit is non-zero). For example, if x = 15f5_16, x' = 15f50000_16. Write x' in hexadecimal and binary. Interpreting the latter as a bit pattern for 32-bit floating point, write the corresponding value in binary (in form +/- 1.m * 2^e, where m is in binary and e is in decimal), and convert this to decimal (in form +/- 1.m' * 10^e', where m' and e' are in decimal). A calculator may be used in the final stage (give your answer correct to 4 decimal places). [4 marks]

Assume you are using a 6-bit computer. What would be the binary AND decimal results obtained from the following 2-complement operations? (show working for decimal to binary conversions and indicate if overflow occurred).

2.A 101 010
+010 010

2.B 001 011
+011 101

2.C 110 011
-011 110

2.D 100 111
-110 110

[6 marks]

given the C code:
```
  int i, n;
  ...
  char c = 0;
  for (i=0; i<n; i++)
    c++; // increment c
  printf("%d\n", c);
```
what number is output when (a) n = 127, (b) n = 128, (c) n = 255 and (d) n = 256. Explain your answers. [2 marks]

Part 2 - Simple C Programming [15 marks]

Over this course, we will develop a test program that will be used to explore memory hierarchy performance on modern Intel x86-based machines. The program will perform a simple but exacting memory operation: transposition of an n by n integer matrix A. The simplest way of representing a 2-dimensional matrix in C is to create an n*n one-dimensional array; the logical matrix element A[i,j] is accessed as A[i*n+j] (this is called row-major storage format).

The program transpose.c will be the first and simplest prototype (indeed, simple enough to translate into PeANUt assembler, which you will do in Assignment 2). It will use basic control structures, a simple function with parameters, simple arrays, and I/O via printf() and scanf(). The program:

statically allocates storage for the int matrix A, sufficient for n<=16.
prints an introductory message, which prompts for n, and inputs the value of n. It can be assumed that a valid non-negative integer can be scanned from the standard input.
checks the storage for A can hold an n by n matrix; if not, it exits with an error message.
initializes each logical element A[i,j] to i*n+j
prints the matrix A with each row printed (in order) on a line of output. Each element is printed with a " %4d" format specifier. This is preceded by a message signifying this is the initial matrix.
transposes the matrix (swaps each logical element A[i,j] with A[j,i]).
(*** i.e. it performs the operation A = A^T, which requires explicit swapping of elements. Your program must not create the tranpose in a different matrix, e.g. perform B = A^T, which is a different operation in terms of its effect on the memory system. ***)
prints the matrix as per step 5, but preceded by a message signifying this is the transposed matrix.

You can compile your program using the command gcc -Wall -o transpose transpose.c.

The printing of a matrix should be performed in a separate function (with the matrix A and n passed as parameters). Otherwise there are no constraints on how you implement the above steps (including whether you use row-major storage), except that your program's output should match exactly that produced by the reference version of the program /dept/dcs/comp2300/public/ass1/transpose. i.e. this program tells you the exact output messages etc that your program should produce. This can be done with the aid of the Unix diff utility:

echo 4 | transpose > out1 echo 4 | /dept/dcs/comp2300/public/ass1/transpose > out2 diff out1 out2

If the above diff command has an exit status of 0 (and produces no output), then the output of your program and the reference version are identical. Note: you should remove any trailing spaces from output messages, and do not use tabs. You can display the exit status of the above diff command by executing the command echo "diff exit status="$? (if your command line shell is bash) or echo "diff exit status="$status (if your command line shell tcsh).

Your program should be written with good programming style (and so should not produce any warnings when compiled with the -Wall option!). I.e. it should be well commented, so as to enable the reader (this includes the tutor/marker!) to understand how it works. Identifiers should be meaningful (e.g. ARRAY_LENGTH rather than L), any constants should be named rather than hard-coded, and you are encouraged to use a coding style similar to that displayed in the examples given in lectures. Your program must compile and run correctly on the default gcc in DCS Linux Labs (use partch.anu.edu.au for remote access).

Note that your program will be automatically compiled and run using various test cases. The ability of your program to reproduce the required behaviour (*** provided it does so in the way specified above***) will contribute about 50% to your marks. The remaining 50% of the marks will be awarded based on inspection of your code (completeness, coding style).

(*** Note you will be translating transpose.c into PeANUt in Assignment 2, so keep it simple! That refers particularly to program structure (especailly functions are hard to implement in assembler) and the use of external library calls - there will only be limited forms of printf() and scanf() available in PeANUt. ***)

Part 3 - More Advanced C Programming [15 marks]

The above test program is just sufficient for performing a simple transpose operation on small matrices and checking (by eye) the result is valid. To make it more useful, the program should get the value of N (and any other parameters from the command line (the standard for C programs), dynamically allocate the matrix, be able to optionally print out matrices (and in octal, decimal or hexadecimal form), implement at least two versions of matrix transposition algorithms, and checks if the result is correct. It will also check coorectness of the command line parameters, and abort with a non-zero exit status if these are incorrect.

Implementing this program will extend your C abilities in manipulating strings (and arrays of strings), command line parameters and exit status, the assert statement, dynamically allocated memory, and more complex control structures.

You should only proceed with this part if your program transpose.c is working satisfactorily. None or very few marks will be allocated for this part if it is not!. You should use your code from transpose.c as a starting point for transpose2.c.

The program:

processes the command line parameters according to the usage: transpose2 [-2] [-p d|x|o] n. This means the program can accept an optional parameter -2 followed by an optional parameter -p (which must be followed by one of the strings d, x or o, followed by an (non-negative) integer n. Valid examples include:
The program should print out a `usage' message and exit with a status of 1 if the parameters are invalid. Invalid examples include:
Note that your program may treat as valid or invalid the cases where the -2 and -p options are repeated or out of order.
dynamically allocates storage for an n by n int matrix A. An assert statement should be used to check the allocation succeeded (it might not if very large values of n are given).
initializes each logical element A[i,j] to i*n+j.
if the -p option was specified, prints the matrix A with each row printed (in order) on a line of output. Each element is printed with a " %4d", " %4x", or " %4o" format specifier, according to whether -p d, -p x, or -p o was given in the command line, respectively. This is preceded by a message signifying this is the initial matrix.
transposes the matrix. If the -2 option was not specified, this should be by a simple nested loop, i.e. one that swaps one element per iteration of the innermost loop. This should be implemented in a separate function which is called from main().
(*** see the clarification for the transpose step in Part 2 ***)
if the -2 option was specified, the transposition should be performed by another function in which the innermost loop swaps four elements, in 2 by 2 blocks, per iteration. This need only work correctly for even n.
optionally prints the matrix as per step 4, but preceded by a message signifying this is the transposed matrix.
counts the number of errors in the transposed matrix (taking advantage of the expected values from step 4). It reports that an n by n matrix transpose was performed, and reports the number of errors.
(*** An `error' in the tranposed matrix is a matrix element with an incorrect value. From step 3, A[i,j] originally had the value i*n+j; after the transposition, it should have the value j*n+i. It is then a simple matter to count the number of errors. Should your program have any errors? Hopefully not in the end, but its unlikely that the code for 2 x 2 swap will work perfectly first time. But if it does have errors, the code here should report them. ***)

Similarly to before, your program's output should match exactly that produced by the reference version of the program /dept/dcs/comp2300/public/ass1/transpose2. Thus, running this program can be used to determine the exact format of output messages etc. The reference version can also be used to resolve any ambiguity (but not inconsistency! - contact the lecturer if you think you find one) in the above specification.

Coding style and marking requirements for this part are as per Part 2.

Hints:

you need to include at the top of your program stdlib.h for the dynamic memory allocation libraries (as well as exit()). You also need to include assert.h.
implementing the function performing the transposition by swapping 2 by 2 blocks is probably the most tricky part, and should be left till last (certainly, you are likely to need the checking code implemented first!). The nested loops should use an increment of 2, rather than one, and the body of the innermost loop should involve the swapping of 4 matrix elements. This technique is called loop unrolling; later in the course we will see that this can have several performance advantages.
(*** To be more explicit, one iteration of the innermost loop should swap each logical element in the list:
A[i,j], A[i,j+1], A[i+1,j], A[i+1,j+1] with the respective element in the list:
A[j,i], A[j+1,i], A[j,i+1], A[j+1,i+1]. A google on "loop unrolling" turns up a Wikipedia entry and a nice example in C. Also see the unroll.c program from lecture P1 ***)

For an optional bonus mark (1 each):

extend step 1 to treat as valid the cases where the -2 and -p options are repeated or out of order. If the -p option is repeated, the format from the last time should be used. (This is the standard convention for processing command-line parameters).
in step 5, extend the 2 by 2 blocks function so that it works for odd n.

Thu Mar 22 15:24:06 EST 2007

2.A	101 010 +010 010
2.B	001 011 +011 101
2.C	110 011 -011 110
2.D	100 111 -110 110