- 12 Apr 2012: Reminder: as discussed in class Tuesday, I will be answering
questions on material relating to preparing for the final on Friday from 2:30
to 4:30 in UC 286. The final itself is then on Sunday the 15th at 10AM
UCC54A.
- 5 Apr 2012: As mentioned in class today, I will be in my office 1:30 - 4:30pm on
Monday 10 Apr 2012 if there are questions on Monday. We will have Tuesday's class
as usual (first up looking at associative cache behavior of program we talked about
at end of Thursday's class). Should know Monday whether room will be available Friday
for a study session as discussed in Thursday's class.
- 5 Apr 2012: CSv4.120405.tar.gz is now available. The description of H3 on 24 Mar 2012
says that your circuit should have performance twice as good as the provided marieMemory.csd
on a provided `reasonable program' positioned anywhere in memory. This software distribution
provides the mechanism for this. In CSDExamples, there is a new awk program, marieAsm.awk, which
is a simple assembler for the Marie assembly language. There are also two sample programs,
marieAsm5, which is input that would produced something comparable to marieData5's output
and marieAsm7. marieAsm7 is a program that traverses a zero-terminated sequences of 2's
complement 16-bit integers in memory and finds the largest value stored. The full usage sequence
would be:
awk -f $h/marieAsm.awk < $h/marieAsm7 > $h/marieData7
$h/marieTrace < $h/marieData7 > $h/marieTrace7
(cat $h/h3.nl ; $h/marieTrace7) | java -jar SequentialTester.jar > $h/marieTrace7.result
(cat $h/h3Orig.nl ; $h/marieTrace7) | java -jar SequentialTester.jar > $h/marieTrace7.orig
diff $h/marieTrace7.orig $h/marieTrace7.result
should show the two circuits produce the same output although the peformance of your h3.csd should
be at least twice as good (half the value of) the performance of the original h3.csd (which you
probably want to move to h3Orig.csd so you don't lose track of it).
marieAsm7 produces a 580 so it shouldn't take more than 6 minutes to run on the original circuit
on gaul. The thing that is of most interest about it is that if you look at the file, you will see
there is a JUMP at line 0 that transfers control to an area of memory where the program is stored
(starting with the label program: and preceded by the metacommand BASE x10) which can be repositioned
in memory easily by changing the hex value of BASE. It uses temporary variables in a section
of memory preceeded by BASE x700 which can be similarly repositioned. And finally, the array
is stored at label data: preceeded by BASE x800. So, you know this program will be run, but you
don't know what values I will set BASE to for the three indicated memory sections (except that they
won't cause the sections to overlap). As usual, circuits that fail on any setting of BASE in this
program would get a 0. Circuits that work on this program but fail on other test data would get a 1,
and working programs would otherwise be marked on the range 2 to 5. To be considered `working' on the
test data, the performance requirements must be met. To be considered working on alternative data,
it is sufficient that the right answers are produced but performance needn't be quarenteed.
- 2 Apr 2012: Only one group had a working solution to h2. Its performance was: 26876 transistors,
95 depth, 4.28 clock cycles per task, for a performance figure of: 10927781.6
- 29 Mar 2012: CSv4.120329.tar.gz has been uploaded to gaul in ~webber/CS350 as usual. It
contains the version of marieNew.csd that we discussed in class today as well as the marieTrace6 file
that we looked at.
- 24 Mar 2012: Regarding H3. A new software distribution CSv4.120324.tar.gz has been put on
gaul. To speed up test runs for homework 3, rather than run the actual Marie implementation,
the input data for h3.csd will be a memory trace from the updated marie simulator marieNew.c .
The memory trace is actually created by a modified version of marieNew.c called marieTrace.c .
As an example, marieTrace5 contains about 400 memory read and write requests. If one runs:
(cat $h/marieMemory.nl $h/marieTrace5) | java -jar SequentialTester.jar > x
diff $h/marieTrace5.result x
One finds that the version of the marieNew.csd that handles only read and write memory requests,
named marieMemory.csd takes 6834 clock cycles to process the 402 memory requests (averaging 17 clock
cycles per request). The number of transistors in the marieMemory.csd circuit is 1,705,148 and
the circuit depth is 51. The compiler in this distribution has been modified so that uses ram that takes
550 circuit depths worth of time to respond to a request. It takes just over 4 minutes to run this simulation
on gaul and just under 1 minute to run it on a 2.26 GHz Quad-Core Intel Xeon. [Note: the test cases
named marieTrace1 through marieTrace4 all contain more than 4000 memory requests and so take 10 times
longer to run which is probably too long for gaul, which is why marieTrace5 was created and I am still
working on determining the final memoryTrace for timing the project.]
The file marieMemory.nl was compiled from marieMemory.csd which is pretty much the marieNew.csd from
the last software distribution. The program that produced the memory trace can be found in marieData5 .
It runs the right shift program from last year's final and dumps the first 32 words of memory.
./marieNew marieData5 > marieData5.result
./marieTrace marieData5 > marieTrace5
./marieNew marieTrace5 > marieTrace5.result
If one then compares marieData5.result and marieTrace5.result, we find that the last 32 entries are
the same (so that when they dump the last 32 words of memory, they both have put the same information
in memory). The file marieData5 is 44 lines long (including comments showing the hand assembling of
the program into configuration file format) while marieTrace5 is 404 lines long showing just the sequence
of memory accesses needed to simulate the system described in marieData5.
So, if one was working on h3.csd, it would make sense to rebuild your current version of h3.csd
using the new compiler and then run the marieTrace5 data over it to see how its performance
compares with the above sited performance of marieMemory.csd . As with any sequential circuit,
performance is number of transistors time circuit depth times number of tasks time average number of
clock cycles per task. In order to qualify as a working solution to homework 3, it must get exactly
the same resuls as marieMemory.csd and have a performance value of no more than half that of
marieMemory.csd . As mentioned in class, the most obvious place to focus is the memory subsystem
and implementing some sort of caching system should be able to easily cut performance in half.
The exact memory trace to be used for measuring h3.csd has not yet been determined, but it is
intended to be one that results from running a `reasonable' marie assembly program through marieTrace.
Your solution should be able to do well regardless of where in memory that program is placed. Also,
your program needs to perform properly on any arbitrary sequence of memory requests whether they
come from marieTrace or not (although performance value for arbitrary memory request sequences need
not be as good as marieMemory.csd's performance value).
- 22 Mar 2012: Following up on discussion of finding information about companies on the net,
Morningstar provides basic financial information about any publically traded company on Canadian and
U.S. stock exchanges. The largest Information Technology companies in Canada are tracked by iShares
under the symbol
XIT. According to them, the largest tech companies in canada are:
RIM,
CGI Group,
Open Text,
Celestica,
MacDonald Detwiller, and
WI-LAN.
Of course, biggest isn't always best. There is a company called Deloitte that each year produces a
list
of the fastest growing Canadian tech companies (based on the last 5 years of revenues).
The members of this list, in order, from Ontario are:
RTI Cryogenics Inc (Cambridge),
NexJ Systems Inc (Toronto),
Real Matters (Markham),
ARISE Technologies Corporation (Waterloo),
Dominion Voting Systems Corporation (Toronto),
GuestLogix Inc. (Toronto),
Wi_LAN Inc. (Ottawa),
Vital Insights Inc. (Missassauga),
Varicent Software Incorporated (Toronto),
Cyberplex Inc (Toronto),
Tantalus Systems Corp (Burnaby),
Carproof (London),
Solace Systems Inc (Kanata),
Route1 Inc (Toronto),
Research In Motion (Waterloo),
ViXS Systems (Toronto),
RuggedCom Inc. (Concord) [note: being bought out by Siemens],
Impact Mobile Inc. (Toronto),
Doxim Inc. (Markham),
BTI Systems Inc (Kanata),
Complete Innovations Inc. (Markham),
QuickPlay Media Inc. (Toronto),
The Code Project Inc. (Toronto),
BlueCat Networks (Toronto),
Nulogx (Mississauga), and
Nightingale Informatix Corporation (Markham). Links to their websites are included with on the
list. And, of course there are a number of tech companies
that are neither the largest nor the fastest growing.
- 22 Mar 2012: New version of course software in ~webber/CS350 on gaul under name CSv4.120322.tar.gz .
This version includes:
- marieNew.c and marieNew.csd in CSDExamples/_2012_Winter subdirectory. these are to be discussed
in class today (after fieldtrip) and form the basis for homework 3.
- update to Simulator subdirectory to fix input over 32 lines long problem in Sequential circuit testers.
- update to CSD_Manual to mention begin_sequential_with_ram_chip keyword.
- copy of last semester's final exam in CSDExamples/_2011_Fall subdirectory.
- 20 Mar 2012: Reminder: Field trip Thursday 22 March 2012 at 3:45pm Room SEB 3097 to
see FPGA lab and hear about how they do circuit design projects with FPGAs.
- 17 Mar 2012: Marks so far with midterm commentary emailed out at 5pm today. Midterms will
be handed back at Tuesday's class.
- 16 Mar 2012: Midterm exam marks are: 89.72, 87.5, 80.83, 76.94, 75, 69.44, 65.69, 65.55, 61.94,
61.66, 60.83, 50.83, and 50.00. Remember the exam was a combination of concept questions and
skill questions with a 1:2 weighting on the categories. Specifically, the concept marks (out of
40) were: 37, 37, 34, 33.5, 33, 33, 31, 30, 29, 29, 28, 28, and 22. The skill marks (out of 30)
were: 27, 26.5, 25.5, 23, 22, 20, 19, 17, 17, 15, 15, 12, and 12.
Hope to be mailing these out either tonight or tommorrow. Remember, the final exam is cumulative,
so you will be expected to be able to answer midterm-like questions on the final as well.
In particular, I would expect 3 of the skill questions on the final to echo the 3 skill question
types on the midterm.
- 15 Mar 2012: By the way, a hint that came up after class today is if you have a wire
that is output 0 and you don't think it should, try negating it. If both x and NOT(x) are
0, then that means that the is an undefined value involved in the calculation of x, which
needs to be tracked down and fixed. Recall the discussion of `frozen' wires at the end
of part 2 of the manual.
- 15 Mar 2012: Coming out of today's class, there is a new release of the course software
CSv4.120315.tar.gz in ~webber/CS350 . The changes aren't required to get homework 2 done,
but they should help if you are testing subcomponents with input size greater than 32.
- In converting test points to values to a list of wire values to be read by the
circuit in the simulator, I was masking the long value against 1 << i. When i got bigger
than 31, this didn't work. So, it has been changed to 1L << i. This was done in a bunch
of testers.
- A request was made for /* */ comments. The Java tokenizer supports this as well as //,
and so a flag was changed in the initialization of the tokenizer so that both types of comments
are allowed.
- Copy of midterm and notes on midterm are now in CSDExamples/_2012_Winter .
- Edited gcdnew.csd so that the component called MUX was renamed ITE (as noted a few times
in class, this was a problem where the name didn't match the boolean equation and so the
name has been changed sot that the component does what you would expect it to).
- 9 Mar 2012: notes on solution to midterm available.
- 6 Mar 2012: A full writeup of H2 including handin instructions
is now available. Remember the due date is Thursday 15 March 2012.
- 6 Mar 2012: As mentioned in class, will have special office hours Wednesday 7 Mar 2012 from
3pm to 5pm for last minute questions before midterm Thursday 8 Mar 2012.
- 6 Mar 2012: A new copy CSv4.120306.tar.gz of the course software is up on gaul. Changes are:
- h2new.c is fixed . The problem, as mentioned in class, was that ~word was working differently
under Solaris than on my machine. I created a new define notword which fixed the problem.
- A new jar file, SequentialDebugger.jar, now exists. It is SequentialTester.jar except the
prints mentioned in the note on debugging infinite loops have been uncommented so that you can
watch what your circuit is doing every clock cycle instead of just seeing the result when done is
raised (which is what SequentialTester.jar does).
- MP3.pdf has been added to _2012_Winter for people looking for a copy of the problem worked
last Thursday.
- Reminder: past exams can be found in _2011_Fall (which is under CSDExamples like _2012_Winter).
In particular, you have:
- Midterm.pdf and MidtermNotes (from Oct 2011). using same textbook
- PracticeMidterm.pdf and PracticeMidtermNotes (from Oct 2011). using same textbook
- PracticeFinal.pdf and PracticeFinalNotes (from Oct 2011). using same textbook -- not relevant to our midterm
- justQuestionsMidtermFeb11 and notesMidtermFeb11 (from Feb 11). different textbook, used CSD though, so
first few questions are of interest.
- 5 Mar 2012: A problem with h2new.c 's handling of negative inputs has been reported.
This seems to be a portablility problem with the C code in that it worked fine on the
machine I developed it on but doesn't seem to work on the Sparc under Solaris. I expect
to sort it out Tuesday.
- 5 Mar 2012: It has been noticed that it is possible for a sequential circuit to
go into an infinite loop, much like any other kind of program. A discussion of how
to debug sequential circuits that are in infinite loops can be found in
DebuggingInfiniteLoopsInSquentialCircuits.html.
- 1 Mar 2012: As agreed at the end of class today, the due date for H2 has moved from
end of day Monday 12 March to end of day Thursday 15 March 2012.
- 28 Feb 2012: Two sample questions to help prepare for the concepts part of the Midterm
are available. Don't look at them until
you are ready to write down their answers. Give yourself 20 minutes to do so
as that is the amount of time you will have on the midterm for questions like
this. Bring your written answers to class 30 Feb 2012 (with you name and
gaul account name on them) and I will read them over and give feedback on them.
- 25 Feb 2012: The email mentioned below was then followed by another regarding
the practice concept questions, chapter reading order, etc.
- 25 Feb 2012: Marks emailed out to people with registered encryption keys who
authorized encrypted marks to be sent out. Others should have recieved email
reminding them of their status vis a vis the encryption form.
- 16 Feb 2012: As mentioned in class today, the homework 2 problem has now been
announced. Specifically, on gaul you will find a new distribution of the course
software CSv4.120216.tar.gz . In it, you will find the following:
The performance metric for h2 is number of transistors times circuit depth times average number
of clock cycles per task. This information will be reported by SequentialTester.jar when h2timing
is used to specify the test data to be timed. Your solution should work with other test data as
well.
- 15 Feb 2012: Notes toward the midterm:
- As mentioned before, the midterm will be held in our regular classroom
rather than the one mentioned in the course outline.
- As mentioned before, the midterm will have two parts: part 1 counting a
third of the exam will be concept questions and cover chapters 1 through 6
(the Tuesday part of the course)
and part 2 will be skill questions (the Thursday part of the course) counting
two thirds of the exam. The concept questions will generally be gauged at 10 minute
answers so expect either 3 or 4 of them. The skill questions will be gauged at 20
minute answers so expect either 3 or 4 of them.
- Example skill questions include measuring performance parameters of a presented
circuit and from a C code specification, generating a combinational circuit. When being
asked to generate a combinational circuit one might be asked to design from primitive
components (and perhaps to minimize either depth or number of transitors in answer)
or design from StandardComponents -- either way, the answer will be expected to
be presented in proper CSD code. Being able to properly apply deMorgan's Law to
a circuit may figure into the requirements as well.
- Although H2 will involve implementing a sequential circuit, the midterm will
not have sequential circuit tasks in its skill part (they may appear in the concept
part to the extent that Chapter 3 covers them).
- Sample past exams can be found under _2011_Fall. They tend to be only skill
type questions. Sample concept questions have been posted to this web site as well
as being scattered among the questions the author presents at the end of the chapters.
- 14 Feb 2012: Performance for solutions handed in on homework 1 were:
- 1992 * 60 = 119,520
- 2184 * 64 = 139,776
- 3264 * 79 = 357,856
- 4608 * 80 = 368,640
- 2988 * 170 = 507,960
- 14 Feb 2012: Two sample questions to help prepare for the concepts part of the Midterm
are available. Don't look at them until
you are ready to write down their answers. Give yourself 20 minutes to do so
as that is the amount of time you will have on the midterm for questions like
this. Bring your written answers to class 16 Feb 2012 (with you name and
gaul account name on them) and I will read them over and give feedback on them.
- 9 Feb 2012: As mentioned in class, I have now downloaded to gaul:~webber/CS350
CSv4.120208.tar.gz which in the _Fall_2012 subdirectory has the gcdnew.c and gcdnew.csd
files we talked about in class as well as the new SequentialTester.jar file . Since
gaul is back up, I also downloaded the version that was previously emailed out which
people hopefully used for their h1, i.e., CSv4.120202b.tar.gz , which included CombinationalTester.jar
which could read the test data specification files talked about in class today (explanation was
also in the email messages and course announcement page, hope to soon update CSD_Manual to reflect
the new simulation/testing structure).
- 9 Feb 2012: Congradulations, everyone got something handed in on time
(and by now hopefully have received email from me to that effect).
- 7 Feb 2012: As we discussed in class today:
- As mentioned in email last week, your homework 1s are due the end of the
day Wednesday 8 Feb 2012. As mentioned in class:
- The H1 spec has you handing in two files, one called README and the other
called h1.csd . Both of which are supposed to be plain ascii text files.
You are to hand them in by emailing them to me (webber@csd.uwo.ca) with
the subject line:
CS3350 H1 handin
as MIME attachments. When I see them in my email stream I will unpack them
and send you return email indicating if there was a problem or not.
- As with the usual submit process, you are allowed to hand in more than
once. The mark goes with the last handin recieved.
- With the due date moved to 8 Feb 2012, than makes 9 Feb 2012 1 day late,
10 Feb 2012 2 days late, and 11 Feb 2012 3 days late (the maximum allowed lateness) --
see course outline for penalties.
- Unlike the usual submit process, email doesn't automatically encrypt your
handin. For H1 you are not required to encrypt your handin. If you want to
encrypt your handin, this is allowed. Basically what you would do is
go to http://ccrypt.sourceforge.net/ and download ccrypt and them encrypt your
files (creating README.cpt and h1.csd.cpt) which you would them MIME attach
to your email to me. I would then decrypt them using the key you provided
on your encryption key form. Note that it is relatively easy for someone to
forge email to me claiming to be from you, but much harder for them to send
me a file encrypted by your encryption key (assuming you have chosen a reasonably
secure key and kept it private) so people sometimes view encryption as playing
a role similar to signing something.
- Remember that each member of a group is responsible for individually
handing in their assignment (expect for the one group that handed me the
signed form for establishing an alternative approach last Thursday).
- Two sample questions to help prepare for the concepts part of the Midterm
are available. Don't look at them until
you are ready to write down their answers. Give yourself 20 minutes to do so
as that is the amount of time you will have on the midterm for questions like
this. Bring your written answers to class 9 Feb 2012 (with you name and
gaul account name on them) and I will read them over and give feedback on them.
- 2 Feb 2012: Due date for H1 has moved from the end of Monday to the end of
Wednesday 8 Feb 2012. Email was sent with more details. 7:50pm today.
- 2 Feb 2012: CSv4.120202b.tar.gz was emailed out 7:25pm today. It
contains the h1new.c file that wasn't in the earlier mailing of CSv4.120202.tar.gz.
Enjoy.
- 2 Feb 2012: Instead of
./h1 sample > h1s.out
cat h1.csd sample | java -jar CombinationalTester.jar h1s.result
diff h1s.out h1s.result
the C program that reads the sample files for h1 has been put in h1new.c, so
./h1new sample > h1s.out
cat h1.csd sample | java -jar CombinationalTester.jar h1s.result
diff h1s.out h1s.result
Note: this doesn't change the homework spec, but it does make it easier to do
testing as before you would have to recompile changes to both h1.c and PartialTester.java
in order to test other than the default data points. Now you can specify the testing
you want to do in the sample file as discussed below.
- 2 Feb 2012: Right now the network connection to gaul is slow,
but after class I will be downloading a new version of the course
software. In it, I have created a new tester called CombinationalTester.jar
that can be run:
cat h1.csd sample | java -jar CombinationalTester.jar
where sample is a file like:
begin_config
sample xFF
sample xEF
sample x8FF011
random x2 x36987
sequence x3 x7
random x2 x367
sequence xF x17
end_config
where hex numbers are the only number form supported currently and all
hex numbers begin with the letter x. sample xFF asks the tester to
run the circuit on the test point extracted from the long value 0xFF .
random x2 x36987 asks the tester to generate two (0x2) random test
points starting with the seed 0x36987 . sequence x3 x7 asks the tester
to test all data points from 0x3 to 0x7 (inclusive). I am still working
on convering h1.c so that it reads the same file and produces comparable
output. it should work like:
./h1 sample > h1s.out
cat h1.csd sample | java -jar CombinationalTester.jar h1s.result
diff h1s.out h1s.result
where diff shows which lines, if any, the circuit disagrees with the
C program (as well as showing resources used by the circuit).
- 2 Feb 2012: Last night had some time to try out h1. My first
solution was 4728 transistors with a depth of 81 for a performance of
382,968. After reworking it a bit, got it down to 3424 transistors
with a depth of 43 for a performance of 147,232. To illustrate the
kinds of tradeoffs one makes, I was able to get the transistor count
down to 3124, but with a depth of 81 and was able to get the depth
down to 38, but with a transistor count of 4422, so 3424 transistors
at a depth of 43 turned out to be the best of the solutions I tried out.
There are, of course, other ideas I didn't try out that have the potential
to be even better. The above work was done with incremental modifications,
rather than radical redesigns.
- 31 Jan 2012: Following up on today's class, there are two professional
societies of interest to computer scientists, both of whom's publications
are available to students at UWO through the library's institutional
subscription (and both of whom offer student memberships at lower pricing).
These are ACM (The Association for Computing Machinery) and IEEE Computer
Society. URLS for key points of both organizations are listed below.
Communications of the ACM and IEEE's journal Computer are aimed at a
general IT audience and should be readable by CS undergraduate students
(particularly articles on areas of interest to said student). ACM also
makes available the Linux Journal which will be of interest to some.
For the general IT computer architecture audience (people in this class),
IEEE Micro is worth looking at.
- 27 Jan 2012: Computers in the news:
- 26 Jan 2012: Reminder: the skills needed to do the homework 1 count for 5% of your mark on homework 1,
but they count for nearly 50% of your course mark as they are two thirds of what is tested on the exams
which in turn count 75% of your mark. So if you don't understand how your group's solution was built to
the degree that you could do it by your self, then you didn't get the benefits you should from working on
homework 1 and it will show up in the exam marking. Remember you can see sample past exams in the
subdirectory of the course softare handout called _2011_Fall . Most of the questions on these exams are
of the type the homeworks are trying to prepare you for.
- 26 Jan 2012: The spec for H1 is available. A few things of note:
- You need the latest version of the course software CSv4.120126.tar.gz for this to work as it includes both
the h1.c file we looked at in class but also a new version of PartialTester .
- Your assignment must work on any input. If it works on the default inputs of PartialTester, but not other
inputs, then it gets 1 out of 5. To try other inputs, you need to recompile both h1.c and PartialTester.java.
h1.c can be rebuilt by typing:
make h1
PartialTester is rebuilt by typing ./build in the subdirectory Simulator. I am hoping to soon have a new version
of PartialTester and h1.c that take a configuration file so alternative inputs can be tested without recompiling
either program. When this has been done, it will be announced here. It will be completely backward compatible
with the current h1.c and PartialTester in that with no configuration file it will do the same thing as they do.
- In addition to marking the `working' circuit on a scale from 2 to 5, I also mention that a circuit whose performance
is no worse than twice that of the best circuit will not get a mark lower than 4. Similarly a circuit whose performance
is no worse than four times that of the best circuit will not get a mark lower than 3.
- As mentioned in class, by default each member of the group is responsible for separately handing in their copy
of the group project and will be separately evaluated (if there is any difference in the copy or in the lateness of the
handin). Alternatives to the default that groups might choose are mentioned in the spec along with a deadline for
deciding.
- Don't forget to handin the encryption key form and show me your id at the time you do.
- 24 Jan 2012: Office hours announced (see top of this page).
- 24 Jan 2012: Forms for establishing an encryption code for online
handins will be/were handed out in class today. In case you need to change
your encryption code or lose your form, copies of the form are also
available online:
- 24 Sept 2011: As mentioned in class last week, the software and documentation
we will be using for the homeworks/ projects is in:
gaul:~webber/CS350/CSv4.120119.tar.gz
In the root directory is a copy of CSD_Manual which tells you how
to run the compiler and simulator.
- 24 Jan 2012: Random note re Chpt 1:
Regarding history, there is, of course, a
wikipedia entry that gives a good start.
- 1 Jan 2012: Course outline
is available.