Winter 2010 CS 3350 by Webber Course Home Page

OFFICE HOURS DURING SEMESTER

Monday: 10:30am to 11:30am MC4a; TA
Tuesday: 4:30pm to 5:30pm classroom heading back to MC384; Prof
Wednesday: 1:30pm to 3:30pm MC4a; TA
Thursday: 5:30pm to 6:30pm classroom heading back to MC384; Prof

Most recent announcements are at top, older ones are further down the page.

9 Apr 2010: After class yesterday, one of the students talked some about his Arduino board (which he had brought in). For roughly $30, one gets a microcontroller packaged up with a USB connector so one can compile programs for it on one's regular computer and download them into the microcontroller. In Computer Science, over the past decade or so, a half dozen students have done 4490E projects based on similar setups. While the department has no electronics lab, the hobbyest market is such that interested students can usually put together a project that is interesting for less than the price of a textbook. As you might expect, for more information on the Arduino, I recommend looking at the wikipedia entry on Arduino (nice overview with pictures and many links). The student currently working with the system recommended the following links:
- URL for the Arduino board
- the manufacturer's main site
- The Make: blog
- Arduino implemented on an FPGA
- Hack A Day also have a pile of Arduino-related articles

8 Apr 2010:

As mentioned in the last class of the semester, I may be out of
my office 1:30 to 1:45 on Tuesday 13 April when you are trying to
hand in your exam.  If this is the case, I will put a message on
my door directing you to hand in to Cheryl McGrath in the Main
Office (MC 355) who will have the forms for recording exam handins.

On a separate note, with regards to question 1, I specified what
the answer should be for 0 0 divided by 0 0, but not the more 
general case of 1 0 divided by 0 0.  Two reasonable interpretations
come to mind.  Either setting it to 0 0 in all cases of division by
0 0 or setting it to don't care in the unspecified cases.  The resulting
circuit could be different based on which choice you make.  Your mark
won't be affected by which choice you make.  It would be best if you
indicate on your paper what interpretation you are using.

A copy of this note can also be found on gaul in the directory where
the final exam is kept as well as on the course announcements page.

--- BOB (webber@csd.uwo.ca)

31 Mar 2010: The file containing the final exam and corresponding encrypted file are now available. The sha1 hash codes for these files were:
```
SHA1(FinalExam)= eee8bbd24e0e65c289a8cab6bfccc712c6a387ee
SHA1(FinalExam.cpt)= c62e28798a82c796bcba4a67d3aa1b828107796d
```
Be sure and read over the exam as soon as you can and be sure you understand the instructions.
30 Mar 2010: As mentioned today in class, for some of you it may be worthwhile establishing a mechanism for send confidential information such as marks via email. My approach to this is to send files encrypted by the open-source program ccrypt. If order for this to work, you need to fill out the following form ( postscript or pdf) and present it to me (verifying your identity with your student id card). On the form there is some basic discussion of security issues relating to password choice -- please be sure and read them. By the way, ccrypt is also installed on gaul in /usr/local/bin .
27 Mar 2010: Homework 11 is now available. Enjoy -- this is the last homework. I expect to be posting the take-home final before the Good Friday holiday.
26 Mar 2010: Still working on Homework 11 -- check back Saturday.
24 Mar 2010: In reference to today's sample I/O code, the typewriter_exceptions code works when you are running java 1.6, but not when you are running java 1.5 . To see it work, type a word followed by a carriage return. It works best when you turn off `update screen', but even then you can type faster than it reads characters, so the program doesn't always see every character you type (some times you have to type a few carriage returns). But if you type slowly with screen update off, like a character a second, and then hit return/enter, what you type will be echoed properly back to you.
20 Mar 2010: Homework 10 is now available. It turned out that both sorting and matrix multiplication were to slow to be able to run reasonable size test cases against the cache configurations available in the simulator. So, Homework 10 is based on a program that is similar to searching for an occurance of one string (the pattern) in another string (the data). Enjoy.
11 Mar 2010: Some interesting articles in Communications of the ACM (which is undergraduate textbook-level reading -- note: these articles can be found either directly in the ACM Digital Library or through Google Scholar):
- The five-minute rule 20 years later (and how flash memory changes the rules) Communications of the ACM, Volume 52, Number 7 (2009), Pages 48-59, by Goetz Graefe
  Presents some `current' tables on costs of flash memory and hard disks. The paper talks about introducing flash memory as an intermediate stage between RAM and disk. The five-minute rule is that RAM should be big enough that all the records that are accessed more frequently than once every 5 minutes should be able to be stored in RAM. The paper claims access latency for Flash disk is .1 ms and access time for SATA disk is 12ms on average (ms milliseconds). On the other hand, transfer bandwidth from Flash is 66MBs API whereas from SATA disk it is 300MB/s API. The price per Gigabyte for NAND Flash is $31.20 whereas for SATA disk it is $0.32. The price to read a 4KB page per second comes to $0.16 for NAND Flash and $0.96 for SATA disk; however, the price to read 256KB per second on NAND Flash is $3.99 while on SATA disk it is $1.03.
- Fighting physics: a tough battle Communications of the ACM, Volume 52, Number 7 (2009), Pages 60-65, by Jonathan M. Smith
  Discusses limits on network performance coming from speed of light. In a round trip from Philadelphia to San Francisco, observes 88ms (milliseconds). 38ms comes from light delays. Cisco CRS-1 routers have average latencies of 100 microseconds -- roughly 30 of them in round trip acounts for another 3 milliseconds, bringing us to 41 milliseconds out of 88 milliseconds acounted for. Various higher-level bottlenecks seem to acount for the rest. Interestingly, IP routing is only twice as slow as light, so networks can't really get delays faster than half current delays (see Amdahl's law for benefits of various amounts of speedup of IP routing).
- Hard-disk drives: the good, the bad, and the ugly Communications of the ACM, Volume 52, Number 6 (2009), Pages 38-45, by Jon Elerath
  Looks at all the ways a hard disk can fail. If you had 67,000 hard drives and ran them hard for 5 months (you would expect a few hundred bytes to not be recorded correctly -- and for this to not be knowable until someone read them and did the wrong thing). Read errors on hard drives seem to range from 1 every 100,000 hours to 1 every 1,000 hours. 1,000 hours is 42 days (just over a month) -- 100,000 hours is 11.4 years. Of course, 100,000 also means that in a class of 100 students each running their computers constantly for 42 days, one of them will see a read error (which may cause all their data to be deleted or it may just cause a single pixel to hold the wrong color for a 60th of a second).
- Network front-end processors, yet again Communications of the ACM, Volume 52, Number 6 (2009), Pages 46-50, Mike O'Dell
  Discussion of the tradeoffs between having a separate network front-end processor (NFE) for offloading TCP processing versus doing TCP processing in the main CPU. As technology has varied since the mid-80s, the advisability of this has changed back and forth.
12 Mar 2010: Homework 09 is now available. Enjoy.
11 Mar 2010: As mentioned in class, in the pipeline example, F0_3 in clock cycles 24, 40, 56, 72, and 88 should be 2060 instead of 2048 (because loop is 2060 and not 2048). Note that PC0 in clock cycle 25 etc is 2060, so I did the jump right, just forgot to fix the fetch operand stage when I noticed that loop wasn't the start of the program. This has been updated in postscript and pdf (and the old version is no longer linked here (although doubtless exists in some Google cache somewhere)).
11 Mar 2010: The completion of Tuesday's pipeline example task in postscript and pdf. Note, we ended up taking 101 clock cycles to execute 41 instructions for a CPI of 2.46 (not quite 1, but way better than the Chapt 5 implementation would have done).
11 Mar 2010: Still in the middle of marking Homework 06. Don't expect to have it ready for Thursday's class. Expect to have it ready for next Tuesday's class.
10 Mar 2010: Correction to Homework 08: The code in part 1 of Homework 08 had the syntax of the load instructions wrong and has been changed to:
```
          ld [m1], %r1
          ld [s65], %r2
          srl %r1, %r2, %r3
          ...
          m1: -1
          s65: 65
```
8 Mar 2010: For recording traces through the pipeline implementation discussed in Section 6.7 of your text, I have prepared the following forms: PipelineTrace including notes on what each column means pdf format and postscript format and PipelineTrace2 (PipelineTrace without the notes) pdf format and postscript format.
5 Mar 2010: Homework 08 is now available. Enjoy.
02 Mar 2010: Clarification on Homework 07: By 32-bit multiplication I mean two 32-bit inputs and a 32-bit output (just like in Java:
```
      int x, y, z;
      z = x * y;
```
works or in C with 32-bit ints).
26 Feb 2010: Homework 07 is now available. Enjoy.
22 Feb 2010: It has been pointed out that where I said `unnormalized' representation in Homework 05, I actually meant `denormalized' representation. It is sad that it takes two weeks for this sort of stuff to come up.
18 Feb 2010: In the continuing saga of Homework 06, the .org directive for the first part has been changed from a base of 4096 to a base of 2096 to deal with the sign extension aspect of the ld instruction. As clarification, the numbers in the second part of the homework (where one is trying to find the max) are 2's complement signed 32-bit values. The Homework has been updated to reflect thse changes as well as those of the 17th.
17 Feb 2010: On Homework 06, ld and st at locations 2048 and 2049 changed to ld and st at locations 2048 and 2052 (recalling it is a byte addressable machine). Also, rather than initialize %r0 to -1, I changed the spec to initialize %r0 to 0 reflecting the actual book microarchitecture better. Also, with respect to %r0, since it is a constant 0, changed the find largest value in memory task to report the result in %r1 rather than %r0.
13 Feb 2010: Note: for the `write microcode' program, I do NOT want 41-bit binary values, instead use the `assembly' notation of 5-15 and more generally Section 5.3.2 (but NOT Figure 5-17).
12 Feb 2010: Homework 06 is now available. Enjoy.
06 Feb 2010: It turns out ARC is byte addressable rather than word addressable, so I updated Homework 05 to refer to addresses 3000, 3004, 3008 instead of 3000, 3001, 3002.
05 Feb 2010: Homework 05 is now available. Enjoy.
02 Feb 2010: Following up on today's class discussion, the student who mentioned the problem with the way C compliers handled volatiles sites the following paper. Interesting. I particularly liked the comment that it is often done wrong because it is difficult to set up a standard test to see if it is done right as the parts of memory where it matters are different on various designs and on the other parts of memory, one wouldn't notice a behavioral difference.
01 Feb 2010: People looking for more examples of finite state controls using D flipflops might look at Figures 5-21 and 5-23 -- note the bubble on input to a gate notation also seen in Figure A-7(b) we haven't introduced (in such cases, a regular NOT gate should be used). Most of the textbook lives at a higher level assuming we know how to build the underlying logic circuits, so there are relatively few examples of completely laid out circuits as opposed to gestures toward the structure of a circuit like you see in Figure 3-11. In the sample problems that are at the same web site as the slides for the text, problems A-8 thru A-15 are relevant to this and come with partial answers.
29 Jan 2010: Homework 04 is now available. Enjoy.
28 Jan 2010: Regarding Timsort (mentioned in class today) created by Tim Peters, there is the wikipedia article An interesting visualization of the Timsort algorithm running on a larger input size can be found at the following blog.
28 Jan 2010: Another clarification to Homework 03: The only flipflop you should be using the the negative edge-triggered D-flipflop Figure A-54. This is also the one the text uses in the discussion of finite state machines.
28 Jan 2010: Marking penalty note: As mentioned in class today, not handing in homework 2 in an envelope will result in a penalty of -1 (making it equal to the penalty of taking a day to find an envelope). Starting with homework 3, the penalty will be raised to -2 to make it worthwhile to take a day to find an envelope (in the case of a 3 day late handin when there just isn't an extra day, the penalty would be only -1 on top of the -3 for being 3 days late). [The above numbers assume the homework is marked out of 10.]
28 Jan 2010: Clarification to Homework 03: The first problem is very specific to the task specified. Pretty much the only thing that can be done with the component connections given is to write a 3 to location 1. When things start up, you can assume the memory unit is not processing anything and that d is 0. When your controller is done, it shouldn't try to do anything else with the memory unit, it should just continually hold the ready signal at 1 (indicating that it is done).
26 Jan 2010: An Improved Algorithm for High-Speed Floating Point Addition is a 1990 Stanford Technical Report. The thing of interest here is that it actually shows truth tables for how the guard, round, and sticky bits are used at various stages of the computation of an addition result -- your text doesn't go into much detail on this point.
26 Jan 2010: Correction to Homework 03: The first problem says that a 1 is on the address lines and a 3 on the data_in lines and you are asked to write 1 at location 3. What you are meant to do is write 3 at location 1. Sigh.
22 Jan 2010: Homework 03 is now available. It is a bit long to read, so try and take a look at it as soon as possible so you can ask questions if it is unclear in spots. The actual answers are not particularly long. The homework is aimed at guiding you to see how a finite state controller could implement some C code (I also talk about how to extend the C code testing approach from the previous homework to circuits involving flipflops).
16 Jan 2010: Clarification on Homework 2, all logic gates in answers are restricted to have a fan-in of at most two (i.e., no 3-input (or more) gates). There is no restriction on the fan-out of the gates.
15 Jan 2010: Homework 02 is now available. It is due by the end of Monday 25 January 2010.
14 Jan 2010: A few questions came up after class regarding the homework:
- relative error was encountered in the text in the discussion of the gap in floating point numbers (page 47). the gap is the difference between a number and its neighbor, the relative error was then the gap divided by the size of the number. by analogy, we think of the relative error between the correct answer and the approximate error as being the gap between the correct answer and the approximate answer. since there is only one correct answer and many approximate answers, it is the correct answer that one is relative to.
- regarding guard bits and the like, we haven't discussed them yet (although they appear on page 50 of the text, it won't be til page 74 in a few weeks that we will get to them at a level that you would need for them to play a role in this problem). if you know all the ends and outs of them and indicate in your answer discussion that you are using them, that is ok. by default, I will assume people are not using them. full credit for the problem does not require using them.
- with regards to what excess value to use for decimal arithmetic, the b, s, M, and m values tell you all you need to know to know what numbers can be represented. knowing what numbers can be represented is all you need to know to answer question 1. the problem never really says how many digits are used to store the exponent. I am assuming that the layout looks much like Figure 2-6, except s = 2 and the exponent field is of whatever size is necessary to accommodate the values of M and m. It is worthwhile paying attention to the location of the decimal point in Figure 2-6 and the definition of s. The answer would be different if the decimal point were in a different location or if s were defined differently. While you can write down that you assumed s meant something other than what the text says it meant, clearly an assumption like that would not be worth full marks. It would seem reasonable to make maximum usage of the values available, so I would expect people to be using normalized representations rather than less accurate unnormalized representations.
- Note: since we are using Figure 2-6 rather than the bottom of page 42, base 16 doesn't figure into this. I.e., there is no need to convert decimal values to other bases when working problem 1.
13 Jan 2010: Been spending some time looking at GUI-based circuit simulators, in particular, two implemented in Java that are distributed as jar files:
- Logisim: seems to be the simpler of the two, but wasn't able to actually test a working circuit in it. ran under Java 1.5
- Digisim: a much more ambitious project. was able to test a working circuit in it, but seemed cumbersome to use. required Java 1.6
In both simulators, placing gates is easy -- it is the handling of wires that is tedious and not intuitive. Both were designed to support courses in computer architecture, so you may (or may not) find them useful.
12 Jan 2010: Following up on having negative and positive zeros, there is a wikipedia entry on signed zeros. It says that positive and negative zero compare as equal in C and Java -- however in Java's Double class, they are different. There are references to algorithms where having signed zeros is useful -- it seems to arise when computing functions on complex numbers although the details are obscure in the references.
12 Jan 2010: TA office hours, starting tomorrow (13 Jan 2010) announced (see top of this page).
11 Jan 2010: There is a wikipedia entry mentioning the patriot missle floating-point problem. It is a bit more complicated than presented in the text as discussed in SIAM News article (SIAM = Society of Industrial and Applied Mathematicians).
8 Jan 2010: (6pm) Homework 1 is now available. Since this is the first homework we have attempted, it is important to read through the procedural information at the front of the assignment to make sure you are doing things the right way. Enjoy.
7 Jan 2010: For a detailed explanation of issues related to 16-bit query id in DNS packet structure, see here. Also related are the wikipedia entries on DNS cache poisoning and Dan Kaminsky.
6 Jan 2010: Chapter 2 is interesting because of the importance of the problems created by computer representation of numbers (both fixed and floating point), particularly in the fields of computer graphics and computer security. For a more extended discussion of the issues involved for the mathematically inclined, the the American Math Monthly article by Forsythe cited at the end of Chapter 2 can be found online. The way I found this one is typical of looking up this kind of material online, i.e., simply visit scholar.google.com and type in the title of the article you are looking for.
6 Jan 2010: There are no online course notes for this class. As mentioned in class, we will be following the textbook closely. The textbook author does keep a set of slides at http://iiusatech.com/murdocca/CAO/.
6 Jan 2010: Created announcements page.

I can be contacted by email at webber@csd.uwo.ca . Be sure and include course number in subject line of your email.