Discussion :

[patoche.05]

Bonjour,

Je travaille actuellement sur le développement d'un logiciel de calcul. Je modélise une structure (composée de nœuds et de liaisons entre ces nœuds), une fois celle-ci terminée, je lance un calcul pour déterminer des déplacements (vecteur X).
Pour déterminer ces déplacements, ma structure est représentée sous forme matricielle (A matrice creuse symétrique définie positive). Des efforts extérieurs sont appliqués sur ma matrice, ces efforts sont représentés sous la forme d'un vecteur F.
L'idée est de résoudre le système linéaire : AF = X

Ce calcul peut-être effectué une centaine de fois.

Je suis confronté à deux problèmes :
- un temps de calcul de plusieurs minutes
- un plantage pour mémoire insuffisante

Les pistes envisagées pour résoudre ce problème :
- parallélisme
- utilisation de la carte graphique pour soulager la mémoire CPU

Est-ce que ces pistes sont pertinentes?
En existe-t-il d'autres?

Environnement utilisé : delphi xe5

Merci d'avance

[tourlourou]

Bonjour,

Utilises-tu une bibliothèque pour les calculs ? Sinon, tu peux regarder du côté de dmath, dont je ne sais si elle peut s'appliquer à ton problème, faute de connaissances en calcul matriciel.

[patoche.05]

Je n'utilise pas de library. L'algorithme qui permet de résoudre ce système est tiré d'un livre.
Je ne connaissais pas cette library, je vais jeter un œil dessus.

[patoche.05]

Les fonctions qu'il a développées sont bien mais ne permettent pas d'exploiter les deux propriétés intéressantes de ma matrice à savoir :
- elle est creuse : 80% de ses termes sont nuls.
- symétrique

[tourlourou]

Pour le souci de mémoire, es-tu sûr de libérer correctement les ressources ? As-tu du code récursif ? Tu peux sûrement tracer l'usage de la mémoire, si nécessaire, après avoir tenté de détecter les fuites mémoire avec les outils de l'EDI.

[patoche.05]

Disons que je stocke beaucoup de données pour effectuer ma résolution de système et ensuite pour exploiter ces résultats. J'ai très peu de fuite de mémoire (j'utilise un outil qui me permet de vérifier si certains lors de la fermeture de mon logiciel, des objets ont été mal désalloués).

[tourlourou]

Comment sont allouées les données ? Voir la possibilité de régler MaxHeapSize dans les données du projet ou options de compilation ?

[patoche.05]

Je n'arrive pas à trouver dans les options de delphi la donnée : MaxHeapSize.

J'utilise un tableau dynamique de pointeurs pour stocker les données

[ALWEBER]

Je n'arrive pas à trouver dans les options de delphi la donnée : MaxHeapSize.
J'utilise un tableau dynamique de pointeurs pour stocker les données

Pourquoi des pointeurs ? Peux tu nous mettre quelques lignes significatives de ton programme pour comprendre.
J'ai travaillé il y a quelques temps sur une traduction d'un programme mathlab en delphi et j'ai résolu un certain nombre des problématiques liées au temps de calcul et à la taille mémoire.

[patoche.05]

Ci-dessous quelques fonctions permettant de créer/détruire la matrice de rigidité (beaucoup d'autres fonctions sont créées sur ce modèle)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
// types utilisés
type cel_type_r=Double;
 
     _tab_r=array [0..0] of cel_type_r;
 
     tab_r=^_tab_r;
 
     cel_r=^cel_type_r;
 
type cel_type_r=Double;
 
     _tab_r=array [0..0] of cel_type_r;
 
     tab_r=^_tab_r;
 
     cel_r=^cel_type_r;
 
r1 : tab_r; // déclaration de la matrice
 
// création de la matrice de taille i
Function alloc_mem_r1(i:integer):boolean;
begin
  try
    getmem(r1,i*sizeof(cel_type_r));
    result:=true;
  except
    result:=false;
  end;
end;
 
// lecture de la valeur se trouvant à l'index i
function r1_l(i:integer):cel_r;
begin
  r1_l:=@r1^[i-1];
end;
 
// écriture de la valeur inf à l'index i
procedure r1_e(i:integer;inf:Double);
begin
  r1^[i-1]:=inf;
end;
 
// désallocation de la matrice de rigidité
procedure lib_mem_r1(i:integer);
begin
  if r1<>nil
    then freemem(r1,i*sizeof(cel_type_r));
  r1 := nil;
end;

Remarques :
- la matrice est mémorisée sous forme d'une seule colonne
- comme la matrice est nécessairement symétrique, je ne mémorise que la partie triangulaire supérieure
- comme elle est en plus creuse, je ne mémorise qu'une partie de ses éléments

J'utilise l’algorithme de Cuthill-Mac Kee pour avoir les termes non nuls le plus proche de la diagonale => allègement mémoire et temps de calcul diminué

https://en.wikipedia.org/wiki/Cuthil...cKee_algorithm

Exemple de matrice que j'obtiens ainsi que quelques informations sur le temps de calcul :

[patoche.05]

Et concernant le choix de l'emploi de pointeurs, c'est un bon outil pour la gestion de la mémoire.

[Paul TOTH]

avec X5 il doit être possible d'utiliser un "TArray<Double>" ou encore un "array of Double" (c'est la même chose) dont on fixe la taille par SetLength(a, size);

après tout dépend de la taille de la matrice évidemment.

il est possible d'allouer une matrice sur disque et d'utiliser un mappage mémoire pour manipuler toute la matrice ... bon ça fait bosser le disque, mais ça n'explose pas la mémoire.

[ALWEBER]

Et concernant le choix de l'emploi de pointeurs, c'est un bon outil pour la gestion de la mémoire.

Est ce que cet exemple réalisé avec XE7 ne convient pas ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
program Project1;
 
{$APPTYPE CONSOLE}
{$R *.res}
 
uses
  System.SysUtils;
 
// types utilisés
type
  TAr1 = array of double ;
var
  ar1: Tar1;
  v1 : double ;
 
// création de la matrice de taille i
procedure alloc_mem_r1(taille: integer) ;
var
  i1 : integer ;
begin
  i1 := length(ar1) ;
  if i1 = 0 then
    setlength (ar1, taille)
  else
    if taille <> i1  then
    begin
      Finalize(ar1); // nettoyage
      // setLength(ar1,0) ; // utile si le tableau est passé en paramètre
      setlength (ar1, taille) ;
    end ;
end ;
 
var
  i1,i2 : integer ;
 
begin
  for i1 := 10 downto 1  do
  begin
    alloc_mem_r1 (100000*i1) ;
    for i2 := low(ar1) to high(ar1) do
      ar1[i2]:= (i1*100000) + (i2/3) ;
    writeln (ar1[(100000*i1)-1]) ;
  end;
  alloc_mem_r1 (100000*10) ;
  for i1 := 1 to 10  do
    writeln (ar1[(100000*i1)-1]) ;
  // désallocation de la matrice de rigidité
  alloc_mem_r1 (0) ;
  readln
end.

[tourlourou]

Bonjour,
As-tu progressé, et dans quelle direction, grâce à des pistes glanées ici ou ailleurs ?

[patoche.05]

Bonjour,

Désolé de la réponse tardive. J'ai été sur un salon où des logiciels que je développe sont présentés. Suite à ce salon, je dois corriger quelques bugs assez urgents?
Je n'ai malheureusement pas eu le temps d'explorer d'autres pistes où d'étudier celles qui m'étaient proposées.

J'espère pouvoir m'y remettre la semaine prochaine.

[SergioMaster]

Bonjour,

C'est la deuxième fois en peu de temps que j'entends parler de matrice creuse (symétrique ou non)
Où pourrais-je glané quelques informations (pour les nuls autre que wiki, bref un bon cours) à ce sujet (mes cours de maths sont très très lointains c.f. mon âge avancé) la dernière fois que je me suis amusé avec des matrices date des années 80 et d'une tentative d'utilisation de matrices inversées)

[Paul TOTH]

Bonjour,

C'est la deuxième fois en peu de temps que j'entends parler de matrice creuse (symétrique ou non)
Où pourrais-je glané quelques informations (pour les nuls autre que wiki, bref un bon cours) à ce sujet (mes cours de maths sont très très lointains c.f. mon âge avancé) la dernière fois que je me suis amusé avec des matrices date des années 80 et d'une tentative d'utilisation de matrices inversées)

ben la définition de WP me semble bien pourtant

Dans la discipline de l'analyse numérique des mathématiques, une matrice creuse est une matrice contenant beaucoup de zéros.

[SergioMaster]

ben la définition de WP me semble bien pourtant

Oui, en fait j'aurais plutôt du demander l'usage de la matrice creuse.

[Paul TOTH]

Oui, en fait j'aurais plutôt du demander l'usage de la matrice creuse.

c'est à dire ? ce n'est pas un outil mathématique, c'est juste une matrice qui de part les données quelle contient est "creuse"...je suppose que ça peut ouvrir des perspectives d'optimisation au niveau de l'implémentation (pourquoi allouer toute la matrice alors que 10% sera utilisé).

[Caribensila]

Stricto sensu, une matrice creuse et une matrice carrée de ce type :

0 . . . .
. 0 . . .
. . 0 . .
. . . 0 .
. . . . 0

Ce qui n'a rien à voir avec le concept informatique qui, comme l'explique Paul, concerne surtout les structures de données.