MIT 6.035

HKN Underground Guide evaluations

2006-12-12T17:35:00.000-05:00

The Underground Guide student evaluations are now open. Visit them here for 6.035.

Please complete your evaluation before 11:59P December 22.

Quiz 3 Graded

2006-12-12T17:32:00.000-05:00

Quiz 3 has been graded. You will get your quiz back tomorrow after class. The average (and median) was 68. The standard deviation was 14.

Small bug in data parallelization library (libderby.a)

2006-12-12T14:20:00.000-05:00

I fixed a small bug in the data-parallelization library that prevented one group's code from working. Since no other groups emailed me, I'm assuming the problem was contained to this one group. The fix is installed in the same location as the old file, so you don't have to do anything. Let me know if you experience problems.

Parallelization differences across machines

2006-12-11T18:37:00.000-05:00

First off, with the new benchmarking library, you can benchmark on chocura.

I have noticed big differences between the parallelization speedups of silver, chocura, and tyner. For a small 4-thread test program, silver gets about a 2.9x speedup over sequential code (executed on silver). Tyner gets a 1.8x speedup over sequential code (executed on tyner). Chocura gets a 3.7x speedup for the same code over sequential execution on chocura.

Based on my experiences over the last couple of days, I'm going to use chocura for the derby. It seems to be the most stable.

New benchmarking library for the derby!

2006-12-08T03:04:00.000-05:00

After noticing that the current benchmarking infrastructure produces some inconsistencies when executing multi-threaded benchmarks, I have implemented a new benchmarking library for the derby. You can use this library now for benchmarking.

Don't worry, the implementation decisions that you arrived at using the current (old) benchmarking infrastructure are still valid. I have only noticed inconsistencies when running multiple threads in the current system.

You can continue to use the current (old) library (lib6035.a) but note that it has problems with multi-threaded benchmarks.

The new library is named libderby.a and is located in /u/mgordon/6035/lib64. The new library interface is similar to the old interface. There are two calls: start_caliper()and end_caliper(). Wrap these around the code you would like to benchmark. The only difference from the old library is that the code will not be benchmarked without a caliper defined. As before you can place them in a callout in your decaf source code.

Using the new library, the assemble command is simpler, for example:

gcc4 emboss.s -pthread -lderby -L/u/mgordon/6035/lib64 -o emboss

No need for that papi library from before. When you execute your code (assuming that you have added a call to start_caliper() and end_caliper()), a brief message will print out, for example:

$ emboss
Timer: 276864 usecs
$

This tells you how many usecs (microseconds) it took for the code wrapped in the timer to execute. We will use this library during the derby to determine the ranking. The calls to start_caliper and end_caliper will be in the derby program when it is distributed on Monday.

Sorry about this change so late in the game, but it should not be too much of a hassle to switch to the new library if your are harnessing data parallelism. I just want to make sure that the derby results are as accurate as possible.

Advice for Optimizer final write-up

2006-12-05T23:14:00.000-05:00

Here are some points to think about:

Use the provided programs to substantiate your implementation decisions. Benchmark the provided programs on the target architecture. Hand-implement the transformation first. The target architecture is complex to say the least. Don't waste time with ineffectual transformations.
Cover all of the transformations discussed in class, at the very least qualitatively, given the benchmark programs and the target architecture.
I would like to see an analysis of each implemented optimization (you can group optimizations if you feel they are symbiotic).
Discuss the reasons for you benchmarking results given your knowledge of the target architecture (look at my last recitation).
Describe your full optimizations option and the ideas/experiments behind the implementation.
Analyze your generated assembly. Look for non-traditional peephole optimizations.

Appendix to Optimizer Project Handout

2006-11-27T21:14:00.000-05:00

The documentation for the data-parallelization library are posted on the website. Link

The evil enter instruction

2006-11-27T20:35:00.000-05:00

From your classmate Zev:

After some experimentation, we found that the enter instruction seems to be broken (using the push, mov, sub equivalent works fine). Some googling turned up the following discussion group thread:

http://groups.google.co.nz/group/comp.os.linux.development.system/browse_thread/thread/a057249198598933/a4f5251c9ef1e7a2?#a4f5251c9ef1e7a2.

Everything is pretty much summed up with Linus' reply at the end. Bottom line: enter can cause segfaults on Linux and is a lot slower than its equivalent.

72 + 16 = 96 (Explanation for the curious)

2006-11-16T12:26:00.000-05:00

Yeah, um, that was me trying to hid some stuff from you and forgetting what I was glossing over. If you are interested:

Some x86-64 instructions are very complex. They are translated into simpler operations in hardware. In recitation we saw that a mov that references memory is translated into multiple simple operations in the underlying hardware, the mov and the memory reference. The mov is dependent upon the memory reference. These smaller instructions are called micro-operations.

There are 16 architectural registers and 72 re-order buffer entries. That is 88 registers. But there are also 8 hidden registers that are used for shuffling values between micro-operations. These are not part of architectural state (the state the asm programmer sees) but they are needed to shuffle values between micro-ops when a dependent micro-op is evicted from the re-order buffer.

Running without benchmarking

2006-11-16T12:14:00.000-05:00

The new lib6035.a and the new assemble require that you use the 'benchmark' script to run your code. If don't you want to benchmark, maybe you are just debugging, use the original lib6035.a in /mit/6.035/provided/optimizer/lib and compile with the old command:

gcc4 example.s -L. -l6035 -pthread -o example
cc example.s -L. -l6035 -pthread -o example

New benchmarking infrastructure!

2006-11-15T23:48:00.000-05:00

With help from our sys-admin (thanks Mike!), I have completed the new, much much more accurate benchmarking infrastructure. You have to make some changes to use it.

First, set your LD_LIBRARY_PATH environment variable to include /u/mgordon/6035/lib64

For bash:
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/u/mgordon/6035/lib64

For csh:
setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/u/mgordon/6035/lib64

I have placed a new version of the 6035 library in /u/mgordon/6035/lib64, you don't need
to copy it from there.

Now you have to compile things a bit differently, new compile:

gcc4 program.s -pthread -lpapiex -l6035 -L/u/mgordon/6035/lib64

Just in case your are curious, papiex is the library on which I built our benchmarking infrastructure. It allows us to get access to performance counters on the CPU! Very accurate.

----

You can use /u/mgordon/6035/bin/benchmark to get the cycle count information for your program after you have compiled it.

Use 'benchmark program' to get the cycle count for program.

Here is some sample output:

loop
libmonitor debug: (P20071,T0x0) monitor_fini_process()
PapiEx Version: 0.99rc2
Executable: /u/mgordon/6.035/example/loop
Processor: AMD K8 Revision C
Clockrate: 1993.465942
Parent Process ID: 20064
Process ID: 20071
Hostname: tyner
Options: PAPI_TOT_CYC,NO_WRITE
Domain: User
Real usecs: 125
Real cycles: 241852
Proc usecs: 122
Proc cycles: 239896
PAPI_TOT_CYC: 135670

Event descriptions:
Event: PAPI_TOT_CYC
Derived: No
Short Description: Total cycles
Long Description: Total cycles
Developer's Notes:

Start: Wed Nov 15 23:44:20 2006
Finish: Wed Nov 15 23:44:20 2006
libmonitor debug: (P20071,T0x0) monitor_fini_library()

------

What to notice:
*First line give the program you ran (in this case "loop").
*The line your are interested in: PAPI_TOT_CYC: 135670
this is the number of user cycles that your program took to run.

----

You can also define a single "caliper" in the code. This is a section in your code that you would like detailed information about. Use start_caliper() to define the beginning of a section and end_caliper() to define the end of a section. These functions are defined in lib6035.a. So you can use a callout for each in decaf code or just place it in your assembly code (adhering to calling convention of course).

With a caliper defined, the output would look like:
loop
libmonitor debug: (P20167,T0x0) monitor_fini_process()
PapiEx Version: 0.99rc2
Executable: /u/mgordon/6.035/example/loop
Processor: AMD K8 Revision C
Clockrate: 1993.465942
Parent Process ID: 20156
Process ID: 20167
Hostname: tyner
Options: PAPI_TOT_CYC,NO_WRITE
Domain: User
Real usecs: 435
Real cycles: 860899
Proc usecs: 127
Proc cycles: 249792
PAPI_TOT_CYC: 150002

Caliper 1:
Executions: 1
Real usecs: 16
Real cycles: 32333
Proc usecs: 16
Proc cycles: 32328
PAPI_TOT_CYC: 32226 ***This is the cycle count
for your caliper

Event descriptions:
Event: PAPI_TOT_CYC
Derived: No
Short Description: Total cycles
Long Description: Total cycles
Developer's Notes:

Start: Wed Nov 15 23:51:48 2006
Finish: Wed Nov 15 23:51:48 2006
libmonitor debug: (P20167,T0x0) monitor_fini_library()

Let me know if there are any problems. Actually, let me know if it works for you! It is somewhat untested for anyone but me.

Mike

New option needed when assembling!

2006-11-13T15:02:00.000-05:00

Although it has not been discussed, the new 6035 static library (lib6035.a) includes the data parallelization library. Even if you are not data parallelizing, you have to compile the library with the -pthread option:

gcc4 example.s -L. -l6035 -pthread -o example
cc example.s -L. -l6035 -pthread -o example

Quiz 2

2006-11-12T18:40:00.000-05:00

Quiz 2 has been graded. You will get your quiz back during Monday's Lecture (Nov. 13). The class average is 77 and the standard deviation is 13.

Quiz 2 Review Notes

2006-11-06T14:48:00.000-05:00

I hope the quiz review helped. You can find my typed notes here. They are a bit rough (I hate Word, should have used latex) but they should help you to understand dataflow analysis. If you have any questions, you can email me.

Quiz 2 Information

2006-11-04T16:00:00.000-05:00

The second quiz is schedule for Tuesday during class time.

Remember, it is open book/notes!

I have posted a practice exam and solutions on the web site. You can also look at last year's practice quiz, but be careful with problem 4, there are bugs in it.

I am going to give a quiz review during class on Monday (11am, normal room). I will answer any questions and go over the material (mostly dataflow analysis).

The material:

Assembly Language
Low-level intermediate representation (3-address code, etc.)
Translation from high-level representation to low-level (example, for-loop->assembly)
Control Flow Analysis and Basic Blocks
Intra-basic-block optimizations (value numbering, etc.)
Dataflow Analysis including transfer functions, confluence, Global CSE, copy-prop, dce, liveness, and the theoretical framework (lattices, transfer functions, etc.)

Static Single-Assignment (SSA) Readings

2006-11-03T15:25:00.000-05:00

For those interested in SSA form for their compiler, I recommend you first look at Chapter 19 of the Tiger Book (2nd ed.). This is good introduction to SSA. After this chapter you should be able to decide if you want to use SSA.

The Arc Book contains the most thorough coverage of SSA. Chapter 9.3 focuses on conversion to SSA and Chapter 10 discusses transformations in an SSA framework.

The Whale Book and Optimizing Compilers for Modern Architectures include brief descriptions of SSA also, but they are very limited.

Extension for Dataflow Optimization Project

2006-11-01T14:49:00.000-05:00

Design Document: Friday 11/3 @ 5pm (either email me the doc or place in class inbox)

Implementation and Design: Sunday 11/12 @ 11:59pm

Dataflow optimization test cases are posted

2006-10-30T22:35:00.000-05:00

I have posted the test cases for global CSE. I have not provided the output because you should check the output against your unoptimized compiler flow in your regression infrastructure.

16-qsort.dcf

2006-10-26T00:46:00.000-05:00

This test originally contained a semantic error. The partition method did not contain a return statement on all paths of control. It is now fixed.

Assembler command-line

2006-10-18T13:53:00.000-05:00

Like I mentioned previously, it looks like the order of arguments matters when assembling. The following commands work for me on all the machines for compiling the example program given in the x86-64 architecture guide:

cc example.s -L. -l6035 -o example
gcc4 example.s -L. -l6035 -o example

This assumes that lib6035.a is in the current directory.

Let me know if you have any problems.

Update on machines

2006-10-18T13:51:00.000-05:00

gcc4 and java5 should now be on all the test machines.

/usr/java/jre1.5.0_06

$ gcc4 -v
Using built-in specs.
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --with-gxx-include-dir=/usr

/include/c++/3.4.3 --enable-libgcj-multifile --enable-languages=c,c++,java,f95 --enable-java-awt=gtk --disable-dssi --with-java-home=/usr/lib/jvm/java-1.4.2-gcj-1.4.2.0/jre --with-cpu=generic --host=x86_64-redhat-linux
Thread model: posix
gcc version 4.1.0 20060515 (Red Hat 4.1.0-18)

silver/tyner/chocura

2006-10-17T19:05:00.000-05:00

Some notes on the machines:

* You should try to use silver, tyner, or chocura. Urth is a desktop machine that is not too powerful, but if it is free, use it. It is not a multicore.

* As of right now use 'cc' to assemble and link. Note that cc is picky about the order of arguments, i.e. you must issue something like "cc decaf.s lib6035.a -o decaf". The library must come after the assembly file. I'm going to install gcc4 soon. This is the only version of gcc that has 64-bit support as far as I know.

* These machines do not have java5 installed on them. You can grab a copy yourself or wait for me to install one. Hopefully tomorrow, but I cannot make any promises. If you want to use eclipse, there is at least one group that got the 64-bit version to work.

Project Checkpoint Clarification

2006-10-17T19:04:00.000-05:00

At 5pm on Thursday I am going to grab the tarball from your group locker. Please name it according to the project specifications. I would like you to write a brief document describing your low-level IR design, namely, the structures that are represented, how it is organized (tree or flat, 2 or 3 address code, etc). I would like you to describe your compiler flow, i.e. how your are going to translate your HIR to your LIR and your LIR to asm.

This should not be a rigorous document. One page should suffice. I just want to make sure that you understand the concepts and are not doing anything crazy. Unless i find a problem with your design, you will not get any feedback on the document.

Semantic Hidden Test legal-09.dcf

2006-10-16T00:25:00.000-05:00

For the semantic phase, the hidden test case legal-09.dcf was incorrect. It contained an error where control reached the end of a non-void method. If I marked the test case incorrect for your group, please see me to get 1.7 points back for the hidden test grade.

I have since corrected the test case. Thanks to Jeff for pointing this out.

Line Numbers in the Parser

2006-09-17T23:36:00.000-05:00

I received a question regarding how one can get line number (and
column) information for tokens in the parser. Note that this is not
required for this phase of the project.

This is not straightforward because the parser extracts the "value"
field from the Symbol class when you label a terminal or non-terminal
in the RHS of a production. The other fields of ComplexSymbol are not
available in the action code of the parser.

The JFlex manual gives a solution to this problem. I find it a bit
distasteful but it works. I will detail it below:

In addition to the value field, the parser also extracts the left and
right fields from the Symbol in the RHS of a production. For example
if you have:

id ::= IDENTIFIER:Val

You can use Valleft and Valright in the action code. For example:

id ::= IDENTIFIER:Val {: System.out.println(Valleft + " " + Valright); :} ;

The default constructor for ComplexSymbol does not set the left and
right fields of its superclass, Symbol. We can use left and right to
store the line and column of the token. Our symbol(...) factory
method in the scanner can explicitly set symbol.left and symbol.right
(assuming symbol is the newly created ComplexSymbol is named symbol).
The implementation should be straightforward.

After the line number is available, we can use it while error reporting.

(This is distasteful because this is not the intended use for the left
and right fields.)

Scanner Output Inconsistency

2006-09-16T13:46:00.000-05:00

Your classmate Zev found an inconsistency in the scanner output.
There is an inconsistency between the output for char3 and char5
regarding the line number the scanner records in the ComplexSymbol for
an illegal character.

The desired behavior is for the line number in the symbol for
character literals to take the value of the *beginning* line of the
char literal. This only makes a difference for illegal char literals
that are unterminated (meaning a newline is encountered before a
closing ' ). char3 is an example of this behavior.

But char5 uses the ending line in the line field of the symbol.

I have changed the provided output of char5 to reflect the beginning line.

Since this is short notice and the difference is unimportant, I will
accept either option from your scanner (ending line or beginning
line).

Let me know if there are any further problems. Sorry for the confusion
and thank you Zev.

.05 is an Identifier!

2006-09-15T14:30:00.000-05:00

You should note that .05 (and any other "floating point number" of the form .digit*) is an identifier. Somewhat weird, and it confused me for a bit, but since the language does not include floating point numbers, it is fine.

So we can have an statement like

.5 = .7 + 6;

Where, .5 and .7 are variables.

Tabs in Char/Sring literals

2006-09-15T12:29:00.000-05:00

Your scanner should not allow tabs (depressing the "tab" key, not '\t') in char literals and string literals. Look at scanner test char9.

Scanner Output

2006-09-14T20:52:00.000-05:00

Question:

Do you have a comprehensive list somewhere of all the token strings and
error strings that you expect? Or can you at least guarantee that the
public tests contain all of them? It would suck if one of my error messages
didn't match yours because I didn't know what it should look like.

Answer:

Only the token strings that are listed in the sample scanner output
are specified. The names for any others you recognize are not
specified and I don't know if the provided tests for the scanner are
complete. There is no list of the token strings.

Don't worry about the exact format of any error messages that are not
given in the sample output. Just worry about catching as many errors
in the scanner as you can, and try to match the output of the given
tests. I will look closely at the scanner/parser output for the hidden
tests and I will not simply diff the output against my scanner/parser.
And also, if you really cannot match the output of the scanner
perfectly, don't try too hard, I'll examine any tests that fail to
match the output exactly.

LALR(1) Conflict Resolution

2006-09-13T14:43:00.001-05:00

After class a question was raised regarding how the parser can recognize a field declaration versus a method declaration because they both start out with a type declaration and an identifier.

I think I understand the confusion. You should remember that an LALR(1) parser has one lookahead symbol to decide which *state* it should transition into, but a state can include more than one of the original productions.

So during a parse:

class Program {
int f . (

The parser should be in a state that "includes" both method declaration (if there are no field decls) and field declaration and upon seeing the "(" will move into a state for a method declaration.

The trick is to delay the decision as to which rule should be
matched as long as possible. If you have the following rules:

program -> CLASS id LBRACE field_decl method_decl RBRACE;

field_decl -> type id ... | ;

method_decl -> type id LPAREN ... | ;

You will get a conflict upon seeing a type.

The parser will have to decide upon seeing a type whether it is a
field_decl or a method_decl. But it cannot tell yet and you did not give it the option of delaying the decision until later and continuting in a state that includes both.

You do not want to limit the decisions that the parser must make early in the parse. You need the early states to contain each option (i.e., whether there is a field_decl or not).

How can you re-write the grammar above to be conflict-free?

I hope this helps. Let me know if there are still any problems. I can write more on this subject.

Setting Up CVS

2006-09-12T21:57:00.000-05:00

You can follow the steps below on Athena to create a cvs repository and import the skeleton to begin working on the project. Lines beginning with # are comments.

cd /mit/6.035/groups/leXX
mkdir cvsroot

#set your CVSROOT, should be added to your startup script
#bash
export CVSROOT=/mit/6.035/groups/leXX/cvsroot
# or csh
setenv CVSROOT /mit/6.035/groups/leXX/cvsroot

#create the repository
cvs -d $CVSROOT init

#import the skeleton
cd /mit/6.035/provided/skeleton
#the option compilier is the parent directory for the project
#leXX is a vendor tag and start is a release tag
cvs import -m "Importing Skeleton" compiler leXX start

Now you can run 'cvs checkout project' to check out the skeleton where you want to begin working.

If you would like to work on non-athena computer that has linux and CVS, you can use remote CVS by setting the environment variable CVS_RSH to "ssh" and setting your CVSROOT to:

:ext:username@ant.mit.edu:/mit/6.035/groups/leXX/cvsroot

Then you can run cvs checkout from your linux box.

Introduction

2006-09-12T21:34:00.000-05:00

Welcome to the blog for MIT 6.035. Here the I will post answers to questions that I receive. Students can also post comments, corrections, and updates via the comments.