Le langage C Map/Reduce (C M/R) est un langage pour l'écriture de codes parallèles sur une machine multicoeurs, utilisant 2 constructeurs pour le parallélisme: les fonctions map et reduce.
Le langage est basé sur le C. En cas
d'ambiguité sur la façon d'interpréter le langage, on se basera
sur C.
1. Les variables
Les variables peuvent manipuler des entiers, des
flottants, des fonctions et des tableaux:
- Les tableaux sont déclarés soit avec un nombre d'éléments constant, comme le tableau A, soit sans élément, comme le tableau B.
int A[100],B[]
A est un pointeur sur une zone de 100 entiers, B est un pointeur, sans être associé à une zone mémoire. Les tableaux peuvent être retournés par des fonctions. On peut affecter un tableau à un autre tableau, le nombre d'élément de chaque tableau doit être compatible (voir après pour les règles de typage).
- Les fonctions doivent être déclarées avec un bloc de code. Une fonction
main
doit être déclarée.
Les variables ne peuvent avoir le même nom que les mots clés du langage. En particulier, 2 fonctions sont réservées, map et reduce.
Une discussion plus approfondie sur ce système de typage est
faite dans la suite.
Opérateurs
On définit à présent les opérations qui sont réalisables entre ces types.
-
Les entiers et floats ont les 4 opérateurs de base (+,-,*,/). Les
règles de conversion de type standard s'appliquent: si l'un des
opérandes est un entier et l'autre est un float, alors le résultat est
un float.
Les opérations de comparaison (<,<=,>,>=,==,!=) s'appliquent également
entre entiers et floats, avec les mêmes règles de conversion
implicite. Le résultat d'une comparaison est un entier (0 pour faux, 1 pour vrai).
Les opérateurs && et || s'appliquent sur des entiers.
- Les pointeurs de fonctions n'ont qu'une opération: l'affectation. Il n'est pas possible de faire une autre opération entre pointeurs de fonctions.
- Les tableaux n'ont qu'une opération: l'affectation. Le nombre d'élément d'un tableau est défini soit lors de sa déclaration, soit par affectation. Aucun changement de type (cast) des éléments n'est autorisé lors de l'affectation de tableaux.
2. Map, reduce et autres fonctions
Le langage implémente les fonctions suivantes. Les fonctions map et reduce font partie de la grammaire, les autres fonctions peuvent être définies comme des variables extern
.
- La fonction map a un type générique, dont le prototype est:
TYPE2 (map(TYPE2 fct(TYPE1),TYPE1 array[N]))[N]
avec TYPE1 et TYPE2 n'importe quel type valide, sauf VOID. La fonction map prend en paramètre un tableau array de N
éléments de type TYPE1
et une fonction fct
qui transforme un élément de type TYPE1
en TYPE2
. Le type de retour de map est un tableau d'éléments de TYPE2
.
La fonction map peut être appliquée en parallèle à tous les éléments du tableau d'entrée.
-
La fonction reduce est également générique et aurait pour type:
TYPE reduce(TYPE fct(TYPE a, TYPE b), TYPE array[])
avec TYPE n'importe quel type valide, sauf VOID. La fonction applique
la fonction fct sur tous les éléments du tableau array. C'est une
réduction, comme lorsque l'on fait une somme entre tous les éléments
d'un tableau. La fonction fct est supposée être associative: le
parenthésage n'a pas d'importance pour le calcul du résultat.
int A[1000];
int f(int x) {
return x+5;
}
int g(int x,int y) {
return x+y;
}
int main() {
int B[];
int x;
B = map(f,A); // B a 1000 elements
x = reduce(g,B); // x est ∑i=1..1000 (A[i] + 5)
return x;
}
-
D'autres fonctions peuvent être déclarées comme
étant
extern
. Cela permet d'utiliser des fonctions de
bibliothèques externes. On rajoutera les fonctions:
extern void printint(int x);
extern void printfloat(float x);
qui affichera les entiers et les flottants. Le code de ces
fonctions sera mis dans un code C, à compiler avec le code produit par
LLVM.
3. Les instructions
Les instructions sont l'affectation, la boucle for, la boucle while et la conditionnelle.
- L'affectation: on ne considère que des affectations du type var=expr. L'affectation est également une expression, renvoyant la valeur de expr.
- Les boucles for et while: même sens qu'en C.
- La conditionnelle, avec une partie else optionnelle
4. Tableaux
Allocation
Les tableaux peuvent être soit déclarés statiquement avec une
taille, soit sans. Dans le premier cas, les éléments du tableau sont
alloués. La fonction map permet également de créer un tableau. La
fonction map retourne un tableau dont la taille est la même que celle
passée en entrée. Il s'agit d'un nouveau tableau, qui devra donc être
alloué dynamiquement. La fonction map permet d'écrire un code comme
celui qui suit:
int B[];
int A[1000];
B = map(g,map(f,A));
Le tableau B sera un tableau de 1000 éléments.
Typage
Un tableau non alloué correspond juste à un pointeur. Il est recommandé de typer les tableaux en incluant également leur taille dans leur type. Les affectations autorisées entre tableaux doivent vérifier la propriété suivante: un tableau ne peut prendre que la valeur d'un tableau plus grand.
int A[100];
int B[];
int C[200];
int D[50];
int E[];
int F[];
B = A; // valide. Le tableau B a maintenant 100 elements
C = A; // non valide
D = A; // valide. Le tableau D a maintenant 100 elements
D = B; // valide si l'affectation B=A est faite avant. D a 100 elements
E = F; // valide, 0 elements
La fonction map créé un tableau de même longueur que celui passé en paramètre. On définira un comportement lors qu'on passe un tableau à 0 éléments à map et reduce.
Libération de la mémoire
On devra spécifier comment la mémoire est allouée (sur la pile, sur le tas, statiquement) et comment elle est désallouée, si elle l'est.