∇-Nabla: Numerical Analysis BAsed LAnguage

∇-Nabla: Numerical Analysis BAsed LAnguage

nablaLulesh-512.png pnnnt-512.png nablaSethi-512.png monai-512.png nablaDDFV-512.png nablaMNLDDFV-512.png nablaCoMD-512.png nablaSPH-512.png

∇ specifications pdf file

Introduction

Nabla (∇) is an open-source Domain Specific Language (DSL) introduced in whose purpose is to translate numerical analysis algorithmic sources in order to generate optimized code for different runtimes and architectures. The objectives and the associated roadmap have been motivated since the beginning of the project with the goal to provide a programming model that would allow:

  • Performances. The computer scientist should be able to instantiate efficiently the right programming model for different software and hardware stacks.
  • Portability. The language should provide portable scientific applications across existing and fore-coming architectures.
  • Programmability. The description of a numerical scheme should be simplified and attractive enough for tomorrow's software engineers.
  • Interoperability. The source-to-source process should allow interaction and modularity with existing legacy codes.

As computer scientists are continuously asked for optimizations, flexibility is now mandatory to be able to look for better concurrency, vectorization and data-access efficiency. The ∇ language constitutes a proposition for numerical mesh-based operations, designed to help applications to reach these listed goals. It raises the level of abstraction, following a bottom-up compositional approach that provides a methodology to co-design between applications and underlying software layers for existing middleware or heterogeneous execution models. It introduces an alternative way, to go further than the bulk-synchronous way of programming, by introducing logical time partial-ordering and bringing an additional dimension of parallelism to the high-performance computing community.

This document releases the language specification corresponding to the preliminary version of its implementation. This document is organized as follows. An overview of the ∇ language features is given in chapter No description for this link: data management and program flow are exposed, definitions and vocabulary are specified by the way. Chapter No description for this link presents the ∇ language specification. Finally, a commented ∇ port of LULESH is provided in appendix.

This document applies to ∇ applications developers, and some prerequisites are necessary for full understanding: a good mastery of the C language and its standard, as well as good knowledge of syntactical grammar notations for programming languages.

Language Overview & Definitions

∇ allows the conception of multi-physics applications, according to a logical time-triggered approach. It is a domain specific language which embeds the C language in accordance with its standard. It adds specific syntax to implement further concepts of parallelism and follows a source-to-source approach: from ∇ source files to C, C++ or CUDA output ones. The method is based on different concepts: no central main function, a multi-tasks based parallelism model and a hierarchical logical time-triggered scheduling. It adds specific syntax to implement further concepts of parallelism.

To develop a ∇ application, several source files must be created containing standard functions and specific for-loop function, called jobs. These files are provided to the compiler and will be merged to compose the application. The compilation stages operate the transformations and return source files, containing the whole code and the required data. An additional stage of compilation with standard tools must therefore be done on this output.

A ∇ program lexically consists of white space (ASCII space, horizontal tab, form feed and line terminators), comments, identifiers, keywords, literals, separators and operators, all of them composed of unicode characters in the UTF-8 encoding. The language does not specify any limits for line length, statement length, or program size. A ∇ program grammatically consists of a sequence of statements, declarations, which are connected to the explicit definitions of: items, functions, jobs and ∇ variables. Appendix No description for this link gives illustrative examples of such a listing.

Lexical & Grammatical Elements

To be able to produce an application from ∇ source files, a first explicit declaration part is required. Language libraries have to be listed, options and the data fields -or variables- needed by the application have to be declared. The options keyword allows developers to provide different optional inputs to the application, with their default values, that will be then accessible from the command line or within some data input files. Application data fields must be declared by the developer: these variables live on items, which are some mesh-based numerical elements: the cells, the nodes, the faces or the particles.

nodes{                 cells{
   ℝ³ 𝜕tx;                 p;
   ℝ³ 𝜕t2x;               ℝ³ ε;
   ℝ³ nForce;             ℝ³ cForce[nodes];
    nMass;                delv_xi;
};                     };

Listing 1 shows two declarations of variables living on nodes and cells. Velocity (∂tx), acceleration (∂t2x) and force vector (nForce), as well as the nodal mass (nMass) for nodes. Pressure (p), diagonal terms of deviatoric strain (ε) and some velocity gradient (delv_xi) on cells.

Functions and Jobs Declaration

Two kinds of functions live within a ∇ program. Functions are standard functions (as in C) that have only access to global variables. Jobs are functions that eventually take in input variables, eventually produce output variables and have also access to global variables. Jobs are tied to an item (cells, nodes, faces or particles), they implicitely represent a for-loop on these ones.

For example, listing 2 is a for-loop, iterating on the nodes, set by the developer to be triggered at the logical time '-6.9'. This job uses in its body the '∀' token, which starts another for-loop, for each cell the current node is connected to. Listings 3 and 4 are the C and CUDA generated sources.

nodes void iniNodalMass(void) 
  in (cell calc_volume) 
  out (node nodalMass) @ -6.9{
  nodalMass=0.0;
   cell nodalMass += calc_volume/8.0;
}
static inline void iniNodalMass(){
   dbgFuncIn();
   _Pragma("omp parallel for firstprivate(NABLA_NB_CELLS,NABLA_NB_CELLS_WARP,NABLA_NB_NODES)")
   for(int n=0;n<NABLA_NB_NODES_WARP;n+=1){
      node_nodalMass[n]=0.0 ;
      FOR_EACH_NODE_WARP_CELL(c){
         int nw;
         real gathered_cell_calc_volume;
         nw=(n<<WARP_BIT);
         gatherFromNode_k(node_cell[8*(nw+0)+c],
                  node_cell[8*(nw+1)+c],
                  node_cell[8*(nw+2)+c],
                  node_cell[8*(nw+3)+c],
                  cell_calc_volume,
                  &gathered_cell_calc_volume);
         node_nodalMass[n]+=opDiv(gathered_cell_calc_volume, 8.0);
      }
   }
}
__global__ void iniNodalMass(int *node_cell,
                             real *cell_calc_volume,
                             real *node_nodalMass){
  const register int tnid = blockDim.x*blockIdx.x+threadIdx.x;
  if (tnid>=NABLA_NB_NODES) return;
  node_nodalMass[tnid]=0.0;
  for(int i=0;i<8;i+=1){
    real gathered_cell_calc_volume=real(0.0);
    gatherFromNode_k(node_cell[8*tnid+i],
                     cell_calc_volume,
                     &gathered_cell_calc_volume);
    node_nodalMass[tnid]+=opDiv(gathered_cell_calc_volume,8.0);
  }
}

Both functions and jobs can be triggered with new statements: the '@' statements. As soon as they are coupled to this logical time statement, both functions and jobs do not take standard parameters and return types anymore but are declared to work on variables.

Program Flow

The execution of a ∇ program does not start at the beginning of the program but is driven by the '@' statements. They ensure the declaration of logical time steps that trigger the statement they are related to. The different '@' attributes are gathered and combined hierarchically in order to create the logical time triggered execution graph, used for the scheduling. Different jobs and functions can be declared in multiple files and then be given to the ∇ compiler. Different stages of compilation will take place, one of the most important is the one that gathers all of these '@' statements and produces their execution graph used during code generation.

The introduction of the hierarchical logical time within the high-performance computing scientific community represents an innovation that addresses the major exascale challenges. This new dimension to parallelism is explicitly expressed to go beyond the classical single-program-multiple-data or bulk-synchronous-parallel programming models. The task-based parallelism of the ∇ jobs is explicitly declared via logical-timestamps attributes: each function or job can be tagged with an additional '@' statement. The two types of concurrency models are used: the control-driven one comes from these logical-timestamps, the data-driven model is deduced from the in, out or inout attributes of the variables declaration. These control and data concurrency models are then combined consistently to achieve statically analyzable transformations and efficient code generation.

By gathering all the '@' statements, the ∇ compiler constructs the set of partially ordered jobs and functions. By convention, the negative logical timestamps represent the initialization phase, while the positive ones compose the compute loop. You end up with an execution graph for a single ∇ component. Each ∇ component can be written and tested individually. A nested composition of such logical-timed components becomes a multi-physic application. Such an application still consists in a top initialization phase and a global computational loop, where different levels of ∇ components can be instantiated hierarchically, each of them running there own initialization/compute/until-exit parts.

Language Specification

Syntax Notation

Syntax and semantics are given for terminals and nonterminals that differ with the C language and its standard. In the syntax notation for the grammatical elements used in this document, a colon following a nonterminal introduces its definition.

Lexical Elements

Keywords

Syntax

aligned auto 
break 
char const continue 
do double
else extern
float for
if inline int 
long
register restrict return
short signed sizeof static 
unsigned
void volatile
while
all
Bool backCell 
cell Cell cells coord  
face Face faces forall foreach frontCell
global
in inner inout Integer  
node Node nodes 
options out outer own
particle Particle particles
Real Real3 Real3x3
this
Uid
with
Semantics

The above tokens are case sensitive and are reserved for use as keywords, and shall not be used otherwise.

Literals

Syntax

L                 [a-zA-Z_αβγδεζηθικλμνξοπρςστυφχψωΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩ𝜕]
Semantics

A literal is a sequence of nondigit characters, including the underscore '_'. Lowercase and uppercase letters are distinct. Literals are used to compose an identifier. The additional Greek letters are the following:

  • Lowercase Greek Letters
    Character Letter Unicode Character Letter Unicode
    α alpha 03B1 ν nu 03BD
    β beta 03B2 ξ xi 03BE
    γ gamma 03B3 ο omicron 03BF
    δ delta 03B4 π pi 03C0
    ε epsilon 03F5 ρ rho 03C1
    ζ zeta 03B6 σ sigma 03C3
    η eta 03B7 τ tau 03C4
    θ theta 03B8 υ upsilon 03C5
    ι iota 03B9 φ phi 03D5
    κ kappa 03BA χ chi 03C7
    λ lambda 03BB ψ psi 03C8
    μ mu 03BC ω omega 03C9
  • Uppercase Greek Letters
    Character Letter Unicode Character Letter Unicode
    Α Alpha 0391 Ν Nu 039D
    Β Beta 0392 Ξ Xi 039E
    Γ Gamma 0393 Ο Omicron 039F
    Δ Delta 0394 Π Pi 03A0
    Ε Epsilon 0395 Ρ Rho 03A1
    Ζ Zeta 0396 Σ Sigma 03A3
    Η Eta 0397 Τ Tau 03A4
    Θ Theta 0398 Υ Upsilon 03A5
    Ι Iota 0399 Φ Phi 03A6
    Κ Kappa 039A Χ Chi 03A7
    Λ Lambda 039B Ψ Psi 03A8
    Μ Mu 039C Ω Omega 03A9
  • Other Letters
    Character Letter Unicode
    Partial 2202

Digits

Syntax

D                 [0-9]                         // Digit
H                 [a-fA-F0-9]                   // Hexadecimal
E                 [Ee][+-]?{D}+                 // Exponent
FS                (f|F|l|L)                     // Floating point suffix
IS                (u|U|l|L)*                    // Integer suffix0[x]{H}+{IS}?                 // Hexadecimal digit
                 {D}+{IS}?                     // Integer digit
                 {D}+{E}{FS}?                  // Real digit
                 {D}*"."{D}+({E})?{FS}?        // Real digit
                 {D}+"."{D}*({E})?{FS}?        // Real digit
Semantics

Each digit is associated to a unique type. Digits can also be used to create an identifier. In ∇ the digits are the same as in C.

Identifiers

Syntax

IDENTIFIER        {L}({L}|{D})*
LC                L?'(\\.|[^\'])+'              // Long-wide character
Semantics

An identifier is a sequence of literals and digits. Again, lowercase and uppercase letters are distinct.

Strings

Syntax

STRING_LITERAL    L?\"(\\.|[^\\\"])*\"
Semantics

In ∇ the strings are the same as in C.

Punctuators

Syntax

[ ] ( ) { } . ->
++ -- & * + - ~ !
/ % << >> < > <= >= == != ^ | && ||
? : ; , ...
= *= /= %= += -= <<= >>= &= ^= |=
<?= >?= ?=
# @   ∧ ∨ 
∞ ² ³ √ ∛ ½ ⅓ ¼ ⅛
⋅ ⨯ ⤫ ⊗ ⨂ ⊛
Semantics

Depending on context, punctuators may specify an operation to be performed. The first five lines are the same as in C, the rest is ∇ specific.

Whitespaces

Syntax

[ \t\v\f]                   // ignored terminals
Semantics

ASCII space, horizontal tab, form feed and line terminators constitute whitespaces.

Comments

Syntax

/*                          // ignored comments bloc
//                          // ignored comment line
Semantics

All text included within the ASCII characters '/*' and '*/' is considered as comment and ignored. Nested comments are not allowed. All text from the ASCII characters '//' to the end of line is considered as comment and is also ignored.

Grammatical Elements

∇ Grammar

Syntax

∇_grammar
: with_library                // Library declaration
| declaration                 // Preprocessing, Includes
| ∇_options_definition        // ∇ options definition
| ∇_item_definition           // Cell, Node, Face & Particle variables definition
| function_definition         // C function definition
| ∇_job_definition            // ∇ job definition
| ∇_reduction                 // ∇ reduction job definition
;
Semantics

The input stream can be recursively one of the following: library declaration with the 'with' keyword, standard includes or preprocessing declarations or specific ∇ declarations: options, variables, function or jobs.

Data Types

Syntax

type_specifier
: void 
| char
| short
| int 
| long 
| float
| double 
| signed
| Bool
| ℝ³ | Real3
| Real3x3
|  | Real
|  | unsigned
|  | Integer
| Cell | Face | Node | Particle
| Uid
;
Semantics

All the data types and type definitions existing in C can be used. \(\mathbb{R}\), \(\mathbb{N}\) and \(\mathbb{Z}\) are aliases to float/double, unsigned int and int respectively. Uid is still experimental.

Scopes

Syntax

start_scope: '{' ;          // Common starting scope
end_scope
: '}'                       // Standard ending scope
| '}' @ at_constant         // ∇ ending scope with an '@' statement
;
Semantics

Scopes are opened as in C, ∇ adds a possibility to explicitly declare the logical time-step for it with the '@'.

Operators

In ∇ the operators are evaluated as in C.

New operators coming from new punctuators are still experimental.

Declarations

Library Libraries are introduced by the with token: additional keywords are then accessible, as well as some specific programming interfaces. For example, the aleph (ℵ) library provides the matrix keyword, as well as standard algebra functions to fill linear systems and solve them.

single_library:
| PARTICLES                   // Additionnal 'particle' keyword
| LIB_ALEPH                   // ℵ keywords for implicit schemes
| LIB_SLURM                   // time, limit & remain keywords
| LIB_MATHEMATICA             // Mathematica keywords
;
with_library_list
: single_library
| with_library_list ',' single_library 
;
with_library: with with_library_list ';';

Options

∇_options_definition
: options '{' ∇_option_declaration_list '}' ';' 
;
∇_option_declaration_list
: ∇_option_declaration 
| ∇_option_declaration_list ∇_option_declaration
;
∇_option_declaration
: type_specifier direct_declarator ';' 
| type_specifier direct_declarator '=' expression ';'   
| preproc 
;

Option variables are used as constants in the program. These constants must have a default value and should be changeable from the command line or input config file.

Item

∇_item
: cell
| node
| face
| particle
;

∇_item is used to define the in and out ∇ variables of each job.

Items

∇_items
: cells
| nodes
| faces
| global
| particles
;

∇_items are used to define the implicit data each job will loop on.

Items Scope

∇_scope: own | all;

∇_scope are used to define the scope of the implicit data each job will loop on.

Items Region

∇_region: inner | outer;

∇_region are used to define the region on which each job will loop on.

Family

∇_family
: ∇_items 
| ∇_scope ∇_items 
| ∇_region ∇_items 
| ∇_scope ∇_region ∇_items 
;

The ∇_family allow the different combinations of items, scopes and regions. It is used to declare ∇ jobs by defining on which items they will loop on.

System

∇_system
: uid | this | iteration
| nbNode | nbCell 
| backCell | frontCell 
| nextCell | prevCell 
| nextNode | prevNode 
| time remain limit
| exit | mail 
;

∇_system are additional keywords allowed within ∇ jobs:

  • uid or this used within a job body refers to the item of the current for-loop.
  • nbNode or nbCell returns the number of items for the one considered.
  • next* and prev* are for example accessible after cartesian library declaration.
  • time, remain and limit keywords are usable after the slurm library declaration.
  • exit allows to quit current time-line or the program if no higher hierarchical logical-time level exists.

Variable

∇_item_definition
: ∇_items '{' ∇_item_declaration_list '}' ';' 
;    
∇_item_declaration_list
: ∇_item_declaration 
| ∇_item_declaration_list ∇_item_declaration 
;
∇_item_declaration
: type_name ∇_direct_declarator ';' 
| preproc 
;
∇_direct_declarator
: IDENTIFIER 
| IDENTIFIER '[' ∇_items ']'
| IDENTIFIER '[' primary_expression ']';

Variables must be declared before jobs definition. They are linked to ∇_items. Array of connectivities can be declared, however these arrays should be sized to fit mesh requirements.

Parameters

∇_parameter_list
: ∇_parameter 
| ∇_parameter_declaration
| ∇_parameter_list ∇_parameter
| ∇_parameter_list ',' ∇_parameter_declaration
;
∇_parameter
: ∇_in_parameter_list
| ∇_out_parameter_list 
| ∇_inout_parameter_list 
;
∇_in_parameter_list: in '(' ∇_parameter_list ')';
∇_out_parameter_list: out '(' ∇_parameter_list ')';
∇_inout_parameter_list: inout '(' ∇_parameter_list ')' ;

Parameter lists declare the variables on which the current job is going to work with. in, inout or out variables must be declared in the parameter list before use.

Job

∇_prefix: ∇_family |  ∇_family ;
∇_job_definition
: ∇_prefix decl_specifiers IDENTIFIER '(' param_type_list ')' compound_statement 
| ∇_prefix decl_specifiers IDENTIFIER '(' param_type_list ')' ∇_param_list compound_statement 
| ∇_prefix decl_specifiers IDENTIFIER '(' param_type_list ')' @ at_constant compound_statement 
| ∇_prefix decl_specifiers IDENTIFIER '(' param_type_list ')' @ at_constant if '(' constant_expression ')' compound_statement 
| ∇_prefix decl_specifiers IDENTIFIER '(' param_type_list ')'_param_list @ at_constant compound_statement 
| ∇_prefix decl_specifiers IDENTIFIER '(' param_type_list ')'_param_list @ at_constant if '(' constant_expression ')' compound_statement
;

Each job is tied to the item with which it is declared, via the prefix and the family. A job can or cannot be triggered by an @ statement. If such @ statement is given, an additional if statement is again accessible to allow different treatments from option variables for example. The if condition is for now a constant_expression but this limitation should be removed in future version.

Function

function_definition
: declaration_specifiers declarator declaration_list compound_statement 
| declaration_specifiers declarator declaration_list @ at_constant compound_statement 
| declaration_specifiers declarator compound_statement 
| declaration_specifiers declarator @ at_constant compound_statement 
;

Functions are declared as in C. Similarly to job declaration, a function can be trigged by @ statements. Optionnal if are not yet possible, but should be possible in future version.

Expressions

Primary Expressions

primary_expression
: # 
| ∞ 
| ∇_item
| ∇_system 
| ℍ  |  |  
| ½ | ⅓ | ¼ | ⅛ 
| IDENTIFIER 
| QUOTE_LITERAL 
| STRING_LITERAL 
| '(' expression ')' 
;

Last four lines are as in C: an identifier, a constant, a string literal and a parenthesized expression are primary expressions. The first expressions come with new ∇ ponctuators: ∇_system or ∇_item keywords, few mathematical constants and type declarations. The # terminal allows to retrieve the iteration count within a job body. It is still experimental: there is a possible confusion with nested foreach statements.

Postfix Expression

postfix_expression
: primary_expression
| postfix_expression FORALL_NODE_INDEX 
| postfix_expression FORALL_CELL_INDEX
| postfix_expression FORALL_MTRL_INDEX 
| postfix_expression '[' expression ']'
| REAL '(' ')'
| REAL '(' expression ')'
| REAL3 '(' ')'
| REAL3 '(' expression ')' 
| REAL3x3 '(' ')'
| REAL3x3 '(' expression ')'
| postfix_expression '(' ')'
| FATAL '(' argument_expression_list ')'
| postfix_expression '(' argument_expression_list ')'
| postfix_expression '.' IDENTIFIER 
| postfix_expression '.' ∇_item '('  ')'
| postfix_expression '.' ∇_system 
| postfix_expression PTR_OP primary_expression 
| postfix_expression INC_OP 
| postfix_expression DEC_OP 
| postfix_expression SUPERSCRIPT_DIGIT_TWO
| postfix_expression SUPERSCRIPT_DIGIT_THREE 
| aleph_expression
;

Postfix expressions have been augmented with several types constructors possibilities: this is a work in progress and will evolve soon in a future version. SUPERSCRIPT_DIGIT_* terminals are introduced here but should move to become operators.

Unary Expression

unary_expression
: postfix_expression
| '√'  unary_expression
| '∛'  unary_expression
| '++' unary_expression
| '--' unary_expression
| '&'  unary_expression
| unary_prefix_operator cast_expression
| SIZEOF unary_expression
| SIZEOF '(' type_name ')';

Unary expressions are like in C, with the possibility to add some prefix expressions. Two examples are given here with the additionnal \(\sqrt{}\) and \(\sqrt[3]{}\) ones. Several other operations should arrive with future version.

Multiplicative Expression

multiplicative_expression
: cast_expression
| multiplicative_expression '*' cast_expression
| multiplicative_expression '/' cast_expression 
| multiplicative_expression '%' cast_expression
| multiplicative_expression '⨯' cast_expression // for vectors cross product. 
| multiplicative_expression '⋅' cast_expression // for vectors dot products.
| multiplicative_expression '⊗' cast_expression
| multiplicative_expression '⊛' cast_expression; // for the products matrices, and tensors.

First multiplicative expressions are as in C. Unicode characters and expressions are still to be normalized and will evolve in future versions of the specifications.

Assignment Expression

assignment_expression
: conditional_expression
| unary_expression assignment_operator assignment_expression
| unary_expression assignment_operator logical_or_expression '?' expression
;

Assignment expressions are as in C, with an additional construction: the '?' statement without a ':' has the same semantic as the '?:' but with the last expression ommitted, meaning here 'else unchanged'.

Aleph Expressions

aleph_vector: rhs | lhs ;
aleph_expression
: aleph_vector
|  aleph_vector reset 
|  solve 
|  aleph_vector newValue | addValue | setValue
|  matrix addValue |  matrix setValue 
|  lhs getValue |  rhs getValue 
;

ℵ expressions are usable after the 'with ℵ' declaration. It is a minimal interface proposed to construct implicit schemes.

Statements

Expression Statement

expression_statement
: ';'
| expression ';'
| expression @ at_constant';' 
;

Expressions are as in C. A null statement, consisting of just a semicolon, performs no operations. For each standard expression, an @ statement can be adjoined to declare the logical time at which it must be triggered.

Iteration Statement

iteration_statement
:  ∇_item statement
| _item @ at_constant statement
|  ∇_matenv statement
| _matenv @ at_constant statement
|  IDENTIFIER cell statement
|  IDENTIFIER node statement
|  IDENTIFIER face statement
|  IDENTIFIER particle statement
| while '(' expression ')' statement 
| do statement while '(' expression ')' ';' 
| for '(' expression_statement expression_statement ')' statement 
| for '(' expression_statement expression_statement expression ')' statement 
| for '(' type_specifier expression_statement expression_statement ')' statement 
| for '(' type_specifier expression_statement expression_statement expression ')' statement 
;

The ∀ terminals can be one of: ∀, foreach or forall. Last six lines are the iteration statements of C. First ones are for ∇ jobs, to nest deeper for-loop constructions.

Reduction Statement

∇_reduction
:  ∇_items IDENTIFIER <?= IDENTIFIER  @ at_constant ';'
|  ∇_items IDENTIFIER >?= IDENTIFIER  @ at_constant ';'
;

Logical-Time Elements

@ Definition

at_single_constant
:  |  
| '-'  | '+'  
| '-'  | '+'  
;
at_constant
: at_single_constant
| at_constant ',' at_single_constant

Time-line conventions

Conventionally, the timeline is decomposed as follow:

Time Range     Compute Phase
-∞     First time initialization
]-∞,-0.0[     Standard initialization
0.0     Initialization after a restart
]+0.0, +∞[     Compute loop
+∞     Exit time

∇ Port of the LULESH proxy application

camierjs@nabla-lang.org,