Read Me

Project manager's email address (send questions and comments to):

* kevin.baas -at- milwaukee.gov


Tsunami on sourceforge.com:

* [http://sourceforge.net/projects/tsunamiprogramm/ http://sourceforge.net/projects/tsunamiprogramm/]


PLEASE SEE THE SVN FOR THE LATEST CODE REVISION

* [http://sourceforge.net/projects/tsunamiprogramm/develop]


==========================

    * 1 What is Tsunami?
          o 1.1 Influenced by
          o 1.2 The Tsunami language
                + 1.1.1 The basic building blocks: Channels, Operators, Networks, and Connections
                + 1.1.2 Three ways to write expressions
                + 1.1.3 Handling dimension lists ("< , , >") in expressions
                + 1.1.4 EBNF notation
    * 2 What is it used for?
    * 3 How does it work?
          o 3.1 The front end
          o 3.2 The middle end
          o 3.3 The back end
    * 4 The Roadmap
          o 4.1 Where to find the code?
                + 3.1.1 Front end - parser package
                + 3.1.2 Middle end - graphs package
                + 3.1.3 Back end - codeGenerator package
          o 4.2 Major revisions
          o 4.3 Minor revisions

=============================

=What is Tsunami?=

Tsunami is three things:

# a programming language
# an interpreter for that language
# a (cross-)compiler for that language

Essentially, it is a concise parallel-programming language along with a (cross-)compiler for that language that produces the equivalent optimized OpenCL code.

==Influenced by==

*Joy
*APL
*Java
*Brook

==The Tsunami language==

As a programming language, Tsunami is very concise and powerful.
To give an example right away, the code for a matrix multiplication is as follows:

  C<a,c> = A<a,d> * B<d,c>.

You were expecting pages of code, weren't you?  Nope.
'''Compare this to [[the code for matrix multiplication in OpenCL]].'''

So how do you do an outer product or an inner product?  Just as easily:

  outer<a,e,c,d> = A<a,e> * B<c,d>.
  inner = vector1<a> * vector2<a>.

Now for the function syntax.  Let's do a matrix multiply function:

  matrix_multiply( A<a,d>, B<d,c> | C<a,c>) {
    C<a,c> = A<a,d> * B<d,c>.
  }

Notice a function has two sets of parameters, separated by a "|".
The first set are the inputs, and the second set are the outputs.


===The basic building blocks: Channels, Operators, Networks, and Connections===

Now for some nomenclature.  In Tsunami, a function is called a "network", and a variable is called a "channel".
Why?  Well, because Tsunami is a stream processing language.  That means it doesn't just process single pieces of data,
it processes continuous streams of data.

* A "channel" is something that data flows through.
* And a "network" is just another name for a function that uses "channels" in place of "variables".
* And finally we have the familiar "operator"s, such as *, /, +, and -.  Only difference being that in Tsunami, operators process a continuous stream of data.  That is, they act on "channels" of data and produce a "channel" of results.

To summarize, from the most basic to the most complex:

* channel -  1 input,          1 output,         does nothing, i.e. output = input.
* operator - 1 or more inputs, 1 output,         might do something to the data from input to output.
* network -  1 or more inputs, 1 or more ouputs, might do something to the data from input to output.

Thus, a channel is a special type of operator, and an operator is in turn a special type of network.
Ultimately, an entire Tsunami program is simply one big "network".


And we actually have a name for the "|" symbol.  In unix it's called a "pipe", and in Tsunami it shares much the same purpose.
In Tsunami we call it a "connector", but I suppose you can call it a "pipe" for short, if you like.
As in Unix, it connects the output(s) of one channel (or operator or network) to the input(s) of another.

To use our matrix multiply function -- that is, "network" -- we "connect" it to the input and output channels of our choosing:

  matrix1, matrix2 | matrix_multiply | result.

And viola!  We call this a "stream".

For brevity, the connectors ("|") can be left out, leaving just:

  matrix1, matrix2 matrix_multiply result.
  

===Three ways to write expressions===

In Tsunami, the programmer has three different ways of writing an expression to choose from:

* infix
* postfix
* "streamfix"


1. The familiar "infix" expressions:

   x = y<a,b> * z<b,c>.

the parser converts these expressions to postfix expressions.  Which brings us to:

2. "postfix" expressions:

  postfix y<a,b>, z<b,c> | * | x.
  
This is a little different from what you're used to seeing as "postfix" (for those of you who are familiar with it).
Namely, the "," and "|" are new.  In Tsunami, there is no real difference between an operator and a variable.  Everything has inputs and outputs.
So that means everything would pop the stack to fill its inputs, then push its outputs.  but that's not how we want it to work.
Enter the separator (,) and connector (|).
*the separator (,) says "don't pop the stack to fill the inputs of the next identifier/operation.  push only."
*the connector (|) says "pop to fill the inputs, then push the outputs".
thus, to differentiate between "operands" and "operators", one separates operands by a "," and puts a "|" before operators.
the parser can be told that either commas or connects are implied.  then you can leave them out and it will automatically fill them in for you.
for instance, the same expression with implied commas would be:
 
  postfix y<a,b> z<b,c> | * | x.

and with implied connects, would be:
  
  postfix y<a,b>, z<b,c> * x.
  
  
operators are anonymous networks are assumed to be connected.  Thus, when using implied commas (the default), the postfix can be written simply as: 

  postfix y<a,b> z<b,c> * x.


3. "streamfix" expressions:

  streamfix y<a,b>, z<b,c> | * | x.
  
This is like postfix, except instead of a stack, it uses a queue.  So the connector (|) separates "stages", so to speak.
all the outputs of the first stage are connected to the inputs of the next stage, sequentially.
and all that stage's outputs are in turn connected to the inputs of the following stage.
notice often small expressions will express the same in postfix or streamfix.  By default, connectors are implied:

  streamfix y<a,b>, z<b,c> * x.

====Specifying a default "fix"====

You can always write infix just by using an assignment operator (=), but since postfix and streamfix expressions have the same syntax,
you have to tell the compiler which type it is by prepended the keyword "postfix" or "streamfix", respectively.  But you can also specify a "default"
expression notation, either postfix or streamfix.  the compiler will then assume that any expression without an assignment operator and without a keyword
"postfix" or "streamfix" in front of it, is that fix.   by default, streamfix is the default.


===Handling dimension lists ("< , , >") in expressions===

the dimension list < , > in an expression defines what output dimensions of that identifier (the source) are connected to the input dimensions of the connecting identifier (the sink).
*if the source's output contains dimensions not in the dimension list, those dimensions are "reduced".
*if the dimension list contains dimensions not in the source's output, the data is "repeated" to extend in those dimensions.

*if the sink's input contains dimensions not in the dimension list, the source data is "repeated" to extend in those dimensions
*if the dimension list contains dimensions not in the sink's input, the sink is "repeated" to extend in those dimensions.

*however, if the dimension list contains dimensions in neither the source nor the sink, they are forwarded to the output of the sink, delaying the repetition until then.

(repetition amounts to adding the dimension, but with a stride of zero.)

For example, the infix expression:
  x<a,c> = y<a> * z<c>.
  
causes y to repeat across the c dimension, and z to repeat across the a dimension, before their elements are multiplied together.  this results in an outer product.

Likewise, the infix expression:
  x<a,c> = y<a,b> * z<b,c>.
  
causes an outer product on a,b,c, which is then reduced along b, resulting in a matrix product.
note, however, that "x" and "x<a,b,c>" refer to the non-reduced product.
that is, unless x is explicitly defined:
  channel x<a,c>.
  
in which case the expression can be written as:
  x = y<a,b> * z<b,c>.
  
and "x" refers to x<a,c>, while x<a,b,c> refers to x<a,c> repeated along b.


oh, and operators input dimensions are always the union of all the dimensions of their sources.

===EBNF notation===

 alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
                     | "H" | "I" | "J" | "K" | "L" | "M" | "N"
                     | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
                     | "V" | "W" | "X" | "Y" | "Z"
                     | "a" | "b" | "c" | "d" | "e" | "f" | "g"
                     | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                     | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                     | "v" | "w" | "x" | "y" | "z" | "_";
 digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

 constant = [ "-" ], digit, { digit }, [ ".", digit, { digit } ] ; 
 var = alphabetic character , { alphabetic character | digit } ;
 name = var { ".", var } ;
 dimension list = "<", [ var, { ",", var } ] , ">" ;
 identifier = name, [ dimension list ] ;

 proto identifier = "channel" | identifier ;
 definition = proto identifier, identifier ;
 param = identifier | definition ;

 declaration = "net", proto_identifier, "(", param,  { ",", param }  "|" , param,  { ",", param }  ")", "{", { sentence, "." | declaration } , "}" ;

 sentence = definition | postfix | streamfix | identifier, "=", infix ;

 operator = "*" | "+" | "-" | "/" ;
 punctuation = "," | "|" | "(" | ")" ;
 function = "recipr" | "sqrt" | "reciprsqrt" | "ln" | "exp" | "neg" ;

 expression = { punctuation | identifier | proto_identifier | constant | dimension list | operator | function } ;
 postfix = [ "postfix" ], expression ;
 streamfix = [ "streamfix" ], expression ;

 infix =  infix_unit { operator, infix_unit } ;
 infix_unit = identifier | constant | ( [ function | identifier  | proto identifier ], "(", infix, ")" ) ;
 
 file contents = { declaration } ;
 
 
=What is it used for?=

Tsunami is designed to maximize automatic parallelization of data-parallel algorithms for high performance computing on heterogenous architectures, while minimizing the hassle.


Some applications where Tsunami is ideal include:

*physics
*modeling & simulation
*medical imaging
*finance
*fluid dynamics
*CAD/CAM/CAE
*video rendering
*video compression / encoding
*data mining
*statistics
*artificial intelligence
*signal processing
*linear algebra

=How does it work?=

==The front end==

The front end reads in human-written code and converts it into an annotated graph of data flow, which it then writes in a use-specifiable file
in javascript object notation (.json), a standard data interchange format.

It is invoked by passing the main function a .json "make" file that tells it where the source code is and where to store the result.

The makefile is formated like so:

 {
    working_directory: "this is optional.  if ommited it will use the root directory of the filesystem", 
    entry_network: "this is the network whose inputs and outputs connect to the outside world (usually the filesystem)",
    errors: "optional.  if specified it will write any compilation errors here.",
    output: "this is where it will write the .json file of the data flow graph.",
    code: [
       "here you list the files and directories where your source code is located",
       "it uses the working directory and loads all directories recursively, so usually it's just",
       "src",
    ],
    
 }

The front end produces the data flow graph from the source code in 6 passes:  

#parse
#*tokenize
#*check syntax and convert infix to postfix
#*collect network prototypes
#collect explicitly defined members of networks
#collect implied members. (anonymous and unnamed)
#instantiate networks and their members, recursively, from their prototypes, starting with the entry network.
#construct a data flow graph from the instantiated networks
#write that data flow graph to a .json file, along with the inputs and outputs of the entry network.

The classes used by the front end are (in roughly the order that they are used): 

*parser.Package
*parser.Parser
*parser.prototype.ProtoNetwork
*parser.Network
*graphs.DAG

==The middle end==

(Isn't that an oxymoron?)

The middle end optimizes the graph produced by the front end.

*read in graphs.json file
*convert to canonical form.  this includes:
**algebraic simplification
**dead code elimination
*fuse (i.e. common subexpression elimination)
*write new graphs.json file

==The back end (the interesting i.e. difficult part) ==

The back end takes the graph generated by the middle end and from it creates code for a particular architecture.

* It will analyze the graph to determine reference locality and compute intensity at different points,
* then it will use these metrics to chunk the graph into kernels targeted for different processors on the machine,
* and calculate an execution schedule as well as optimal buffer sizes for transferring data between the kernels.
* it will probably try a couple different combinations (ways to chunk the code into kernels and schedule them) before choosing the one with the highest estimated overall throughput. 
* Then it will generate the code (C++ and/or OpenCL) for the kernels, along with their schedule of data transfers and execution.

If the proper compilers are available on the computer, and specified in a configuration file, it may also use them to compile and link the generated code
into (a) binary executable(s).

=The Roadmap=

==Where to find the code?==

===Front end - parser package===

The classes used by the front end are (in roughly the order that they are used): 

*Main
*parser.Package
*parser.Parser
*parser.prototype.ProtoNetwork
*parser.Network
*graphs.DAG

It is recommended that you start with the Main class. 

===Middle end - graphs package===
The middle-end is all in the "''graphs''" package.  It's all "''graphs.DAG''" and "''graphs.DAGNode''".  These are the data structures that the back-end will use.

===Back end - codeGenerator package===
There is no back-end yet.  The back-end will be in the "''codeGenerator''" package.  The codeGenerator package will produce OpenCL code from a graph of "''graphs.DAGNode''"s. 


==Major revisions==
*v0.0 - nothing
*v0.1 - ''current''
*v0.2 - complete interpreter(first alpha release)
*...
*v1.0 - compiler to OpenCL


==Minor revisions (subject to change)==
*v0.11 - ''current''

*v0.12
**finish parser
**test interpretator on 0-dimensional streams


*v0.13
**create instantiator (multi-dim streams)
**test interpretation
**create source file reader
**create command line interpreter