Nuts! - ran out of time.

Nuts! - ran out of time.

I am sorry to say that I ran out of time in preparing my entry for the Parallelized Parser Formula Interpreter.
I have nobody to blame except for myself in starting this project late.

I did make some good headway. I may finish it in any event and make my own test runs on the MTL system. My results will not count towards the contest. :(...

The strategy I am using is somewhat peculiar, perhaps someone else thought of this too.

I use a dual channel parallel_pipeline that has dual input and dual output data paths.

Path 1 - source code to compiled intermediary code with basic syntax checking and as precompilation of known variables and expressions to values. Residual incalculable expressions and output statements are written into an intermediary "compiled" interpreter code. Note, the output statements may be complete or the expressions are incalculable (but code inserted to attempt recalculation on later pass).

Path 2 - intermediary "compiled" code of one Path 1 output and an adjacent Path 1 output (either immediately preceding or following), this merges the two intermediary "compiled"buffers and in the process reduces nowcalculable expressions to valuesproduces a new "compiled" output code buffer, plus in the event that the two (or one remaining) compiled code buffers represents the front of the file, then the output statements are committed to the output buffer and stripped from the "compiled" code output buffer.

Each merge phase (of two adjacent buffers) is a reduction operation, the process continues (MUNGs along) until there is one compiled code output buffer, then that is finally passed through the compiled code interpreter, which if no syntax errors, will produce the remaining output (and report if there are any un-free'd variables).

Most of this is working. Currently tracking down a problem where a string(expression)that cannot currently be calculated (missing var's from earlier code not merged), is not producing the proper code to regenerate the missing parts of the statement for the next merge phase. (so close but so far from completion)

There is some redundancy involved with unresolvable expressions but presumably as merging progresses more and more expressions get resolved. This is somewhat like the "Snake eating its tail" type of process.

Will let you know how this goes.

It's been fun.

Jim Dempsey

(lame) Excuses:

1) New system (Core i7-2600K) came in, wasted a day installing softwareand migrating code.
2) Working on house remodling (new shower).
3) Found bug in Parallel Studio Composer (variable& from prior closed scope getting mixed up with later same named variable reference in outer scope). This had me chasing my tail for a few hours. The function being called worked properly, but the results got placed into the wrong variable. Don't know if I can make a simple reproducer. If my "completed" project still exhibits the bug (conditional compile with/without work around) then that will be a reproducer.
4) Usual case of debugging taking much longer than anticipated.
5) Had to fix leak in plumming (3 times!).

5 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

jim i am sorry tob see you bail out, it sounds like you had some good ideas. and plumbing always sucks. i will post my write up when i am back to a real computer and we can compare notes. will you be in the second phase?john

it sounds like we have similar ideas. i made a pipeline with five stages:1) serial: read input and chunk into sections by looking for ;2) parallel: parse input chunks, create expression trees, perform constant evaluation, perform chunk local eval where values are known.3) serial: perform global eval for things that have inter-chunk dependencies4) parallel: form output statements to chunk-local buffers5) serial: write buffers to output

Thanks for the sympathy.

FWIW I am not bailing out on the project. I will (may have already) finish it and run it on the MTL system. If I am satisfied that it is working, I will ask the contest manager if he/she will make a run using the same test data. This run will be unofficial since I did not make the deadline. The purpose of the run is should the technique prove superior, then I will write-up a multi-part paper for the ISN. Outline the strategy and show how it is done.

My technique is a bit different. Let's see if I can diagram it.

The parallel pipeline is setup with three stages: Input (serial), Process (parallel), Output (serial)

The input and output pipes are not your standard: Input until EOF and Output while more data.

Instead the input pipe does the following:

Pair obj merge buffers (adjacent chunks, or select last remaining)
If source file remaining read into source input buffer

As with standard parallel pipeline input pipe as little work is done as possible

The output pipe does the following:

if processsource produces obj, send to merge pending pool
if merge A+B produces obj, send to merge pending pool
if merge A+B (or A alone) produces output, send to output file

The merge pending pool is Single Producer (Output Pipe), Single Consumer (Input Pipe). Therefor it can run without interlocked.

The input pipe does NOT shutdown on EOF. Instead it shut downs when the merge phase fails to produce further object code.

The source to obj process checks syntax and converts the expressions into in-line code with known expression/sub-component(s) of expression converted to values (double or text), or and expression with undefined components. The process pipe will determine if the (to be written) obj code represents chunk 0 or some other chunk.

chunk 0

When the expression yields a result, no obj code is generated, instead the symbol table is updated.
If the expression is not resolvable this is a error

chunk x not 0

When the expression yields a result the target variable is examined to see if it previously was loaded with a valid result (excepting for first time on buffer), and if it did, the output obj buffer at the location that stores the data is overwritten with a "skip this code". Then the target variable is updated, the current obj output position is recorded into the variable's property and object code is generated to set the variable to known value.
When the expression is unknown, the current obj output reflects the remaining computation to be performed at future merge state, then the obj code receives store some future value into variable xxx.

The process pipemerge phase works on prior obj code The A buffer is processed to squish out the "skip this code". Then the symbol table from B is merged with symbol table from A and the B buffer obj code is re-processed using the known values from the A buffer (A buffer immediately precedes B buffer). The result of this (generally) computes more values for expressions from former knowns in expressions thus condensing the obj code (or eliminating it). When the merge A buffer represents chunk 0 the output statements fill into the output buffer.

This process keeps running until no more merge data (or error is detected).


Close enough description to give you an idea. Will correct errors and omissions for the article.

Not given in the preceeding information is the layout of the symbol table, how it is indexed, what properties are in the variables. Symbol names are a-z, A-Z, 0-9 (62 characters) to this I added character '.' making 63 symbol characters plus a null character to indicate end of variable name. IOW 64 characrers (6-bits). The primary table has 4096 entries (two 6-bit characters). The secondary tables have 64 entries (for each successive symbol character).

Note, a number in an expression

a = 150;

generates a symbol name in 6-bit for "150". Resulting in an index of "15" in the primary table and "0" in the secondary table.Should the symbol entry for symbol "150" be defined then its value has previously been computed and is used witout a conversion from ascii to double. If the value is undefined, then the conversion from text takes place and the value is inserted into the symbol table.

There is a potential drawback here in that literals are (currently) never deleted.

BTW, "150" and "150.00" are two different symbols.



marks the variable a undefined, but leaves its entry in the symbol table for future use. Finding an undefined variable is quicker than deleting and adding an entry.

Jim Dempsey

Leave a Comment

Please sign in to add a comment. Not a member? Join today