Gamma: Parallelizing Sequential Streaming Applications

updates in red

In this assignment, you will implement the Gamma HJOIN architecture within a single Java program using multiple threads and Java pipes exactly as in the Gamma lecture notes -- no short cuts!  Short cuts will be deducted from your grade.

Warning: this is a substantial assignment.  It will take you many days to finish.  Do not delay in getting started.  This assignment will count 2x times a typical programming assignment, so take it seriously.  Brownie points will be given to those groups who finish early.

---

Gamma Netbeans Project Preliminaries

I am giving you a shell of a Gamma Netbeans Project that uses MDELite to read and write tables.  In the project, I supply 3 directories:

• gammaSupport --  You will build Gamma using its classes and methods.  Study them!
• gamma -- I have shells of all classes (and some completed classes) for you to use.  Classes starting with name "Array" you can skip.
• tests -- I supply 3 runnable regression tests.
  

I have 5 components/boxes (ReadTable, Print, Sort, HSplit, OMerge) for you to use as exemplars and three runnable regression tests:

Study carefully how these examples work.  Only when you understand how each box and each regression test works, should you proceed onto the main assignment.

---

More Studying

A major part of this assignment is for you to read and use existing code.   Read the last sentence again for effect. Not doing so will cost you a lot of time. Study carefully the gammaSupport package. It contains definition of tuples and common operations and other utilities that you will need, such as connectors:

Connector c = new Connector("A_to_B");
ReadEnd re = c.getReadEnd();
WriteEnd we = c.getWriteEnd();

Please note: there is (may still be) a bug in Java Pipes.  If you serialized tuples and pushed them through pipes, your program will fail.  (I have no idea why).  If tuples are serialized as Java Strings, there is no problem.  This level of detail has been hidden from you -- you should only invoke getNextTuple or getNextMap methods on ReadEnds, and putNextTuple or putNextMap on WriteEnds.  Study the boxes whose code I give you.  You'll see the level of abstraction at which you need to program.

Another point on Java pipes.  When a  ReadEnd is finished (meaning there is nothing more to read) -- close it!  When a WriteEnd is finished (meaning there is nothing more to write) -- close it!  Typical coding idioms are:

ReadEnd	WriteEnd
while(true) { Tuple t = re.getNextTuple(); if (t == null) { re.close(); break; } // do something with t }	while(true) { // produce tuple t if (t == null) { wr.close(); break; } wr.putNextTuple(t); }

Study the code of the boxes I give you, and you'll see the use of these idioms.  They are important: if you don't close when your done, your boxes/threads may hang or not perform correctly.  It is a horror to be stuck in this position. So follow my advice!

Another note: Carefully read and understand the BMap class.  It implements tuple hashing and manipulates bitmaps. There are many ways in which MMerge and MSplit can be realized. The simplest is this: M is a n×k bitmap. The join key of an A tuple is hashed twice: once to determine the row of M, the second to determine the column within the selected row. Thus, all tuples of substream A[i] hash to row i of M. MMerge combines M[1]...M[n] into M by boolean disjunction. For each i, MSplit extracts row i from M and zeros out the rest of M[i].

Databases Provided

Implementation Hints

I suggest two main class hierarchies.  Here's the first -- every terminal class is a primitive, whose object is a thread.  

The meaning of these classes is below:

• Bloom-- computes a bloom filter, as in notes.  Observe the icon in the middle of the class: the box has a record stream input (on the left) and a record stream output on the right, and also a bitmap output (red).

• BFilter -- applies bloom filter, as in notes.  The icon in the middle of the class says that this box takes a bitmap (red) and stream (black) as input and produced a record stream as output (on the right).

• BloomSimulator -- to test a Bloom box, I needed to create a box that supplies a bloom filter; that's this box.

• DoNothing  -- relays input messages to output messages.  Initially useful to see if pipelines are working.

• HJoin -- this box encodes the hashjoin algorithm

• Sink -- this box is useful in testing; it simply reads its inputs and does nothing with them.

• ReadRelation -- this box has 2 parameters: name of file to read and the end of a pipe in which to send Tuples of the file.  (I have given this box to you).

• Print -- prints each record that it receives. (I have given this box to you).

• PrintMap -- reads a single bit map and prints it.  Useful for debugging

• HSplit -- reads in a record stream and hash-splits its contents across 4 streams (numbered 0..3).  (I have given this box to you).

• Merge -- reads 4 streams in round-robin order to merge their results into a single output stream.

• SplitM -- splits a bitmap into 4 distinct bitmaps (inverse of MergeM)

• MergeM -- merges 4 distinct bitmaps into a single bitmap.

The following boxes/classes implement pipe-and-filter graphs that implement the functionality of the primitive boxes above (and thus have the same iconic "shape").  They are not part of the Thread hierarchy as only the building blocks above are implemented as threads.

These boxes implement various non-primitive implementations of the HJoin box/primitive.  In  the notes, one implementation map-reduced HJoin, another implementation implemented HJoin using BFilter and Bloom boxes wired together, and finally the entire Gamma graph.  The terminal boxes are subclasses of Gamma.ArrayConnectors, which provides useful ways of creating arrays of pipes in one call.  Not all methods of Gamma.ArrayConnectors may be needed for this project; all are fairly simple.

What To Submit To Canvas

1. Your program needs to run correctly on Linux machines, even though you may have developed them on Macs and Windoze.  The TA will grade your program running on Linux.
   
   
2. Your program's source.
   
   
3. A short description that the Grader needs to know to run your program, other than the above. 
   
   
4. Use JUnit tests that are provided to confirm you are producing the correct output for Gamma joins of:

• join client table with viewing table over key (CLIENTNO)

• join orders table with odetails table over key (ONO)

• join parts table with odetails table over key (PNO)

1. A short writeup explaining any additional tests that you have added to your program to verify that it works.
   
   
2. A PDF file (in the required format) that the Grader should read to provide any information that is not obvious.  The contents of the PDF file can be minimal.

A critical part of any design is clarity and understandability.   Hence, you will be graded on the clarity of your project and its ability to work correctly.  Sloppy code, documentation, or anything that makes grading or understanding your program difficult will cost you points.  Beware, some of these "beauty" points are subjective. 

Remember: No late assignments/submissions will be accepted.