∇-Nabla: Numerical Analysis BAsed LAnguage
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 suffix ℍ 0[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
orthis
used within a job body refers to the item of the current for-loop.nbNode
ornbCell
returns the number of items for the one considered.next*
andprev*
are for example accessible aftercartesian
library declaration.time
,remain
andlimit
keywords are usable after theslurm
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 |