Estimation de complexité

[kronanberg]

Bonjour,

J'ai réalisé un algorithme pour un système embarqué et je suis maintenant en train de compter les différentes instructions qu'il faudra réaliser (lecture, écriture, addition, multiplication) de façon à estimer le temps de calcul de mon système. Cela me permettra de sélectionner un processeur adapter à mes besoins.

Mais j'ai des doutes sur différents calculs notamment les cosinus, sinus, atan2... Il me semble qu'il n'y a pas de calcul pour ces fonctions mais juste une lecture dans un tableau déjà prédéfini ? Donc finalement le calcul de cosinus ou sinus peut être définie comme une opération de lecture ?

Si quelqu'un à des réponses à ces questions je suis preneur. Merci.
-----

[invite4492c379]

Hello,

Ça dépend des librairies que tu utilises, en effet si tes fonctions se bornent à faire un look up dans une table tu peux considérer que leur appel prend un temps constant, cependant il y a souvent un tableau de valeurs et une interpolation pour le calcul donc il faudrait que tu te renseignes sur les bibliothèques que tu utilises.

[Jack]

Pour accélérer le calcul, on peut utiliser des lockup tables, mais cette seule solution n'est pas envisageable au delà d'une certaine précision.

Un exemple d'algorithme:
http://fr.wikipedia.org/wiki/CORDIC

Ne me demande pas comment on le met en oeuvre

A+

[kronanberg]

Ok merci pour ces réponses.

Pour info, pour le moment je ne sais pas quelles librairies je vais utiliser puisque je ne sais même pas quel l'OS embarqué je vais utiliser. Le but étant justement d'estimer le nombre d'instructions que j'ai à réalisé pour choisir mon processeur et mon OS.

Par contre je sais qu'il me faudra de la précision dans le calcul des cosinus et sinus puisqu'ils sont utilisés pour linéariser des filtres de Kalman. Donc je vais peut être regardé la méthode de Cordic alors.

En tout cas merci des conseils.

[A voir en vidéo sur Futura]

[Jack]

Je te déconseille d'écrire tes propres routines de calcul. Tu vas y passer un temps fou. Si tu fais de l'embarqué, programme en C, la librairie mathématique ne va prendre que quelques ko. Un petit µcontrôleur à moins d'un euro est donc capable de faire ce genre de calcul.

Si tu veux de la rapidité, monte en gamme au niveau CPU, voire avec coprocesseur mathématique intégré.

A+

[kronanberg]

ok. J'utiliserai donc la librairie mathématiques de mon OS. Le système à réaliser étant assez complexe je risque de me tourner vers un processeur style atom ou ARM avec une Floating Point Unit pour mes calculs. Par contre l'acquisition des capteurs se fera à l'aide de microcontrôleur (au moins un domaine que je connais un peu mieux )

Et encore une dernière question dans le code, les tests ou comparaison (avec un if ou autre) corresponde à quelle instruction ? En faite à la base je pensais décrire mon système en comptant que les additions et multiplications pour avoir une idée. Puis finalement, j'ai rajouté la lecture et l'écriture des variables en mémoire, puis le calcul trigonométrique. Je pense pas non plus détaille tout mon code en assembleur mais j'ai quand même envie une estimation correct.

Il me suffira ensuite d'estimer le temps de cycle de ces instructions dans mon OS pour pouvoir le sélectionner.


A+

[lou_ibmix_xi]

Un autre paramètre important est le format utilisé pour les calculs, si tu peux passer ton algo (ou une partie) en virgule fixe, ça évite d'avoir un système équipé d'une FPU, ni de faire de l'émulation logicielle très coûteuse.

De plus, compter le nombre d'instruction n'est pas forcément suffisant ni pertinant. Si ton système possède des entrées - sorties (convertisseurs analogiques numériques etc), le bus périphériques (qui tourne souvent moins vite que le coeur) peut être un goulet d'étranglement. Enfin, dès que tu commences à taper dans des CPU avec de la mémoire cache et autres joyeuseutées du genre, ça se complique également (temps de vidange des caches etc...)

[kronanberg]

D'accord avec toi. Mais pour le fait de compter les instructions, c'est le seul moyen que j'ai trouvé pour étudier la complexité de mon système.

Je serai à priori sur une architecture distribuée. Plusieurs microcontroleurs effectueront l'acquisition des différents capteurs via un bus CAN, des liaisons séries, des convertisseurs Analogiques Numériques... Les informations seront ensuite transmises au processeur à travers un bus I2c, SPI ou autres. L'acquisition des mesures doit se faire à 10 Hz.

Et moi il va falloir que je m'assure que mon processeur puisse effectuer tous les calcul entre les 100 ms qui sépare deux échantillons.

Donc si tu vois une autre méthode que de détailler toutes les fonctions pour estimer un temps de calcul je suis preneur

A+

[Xoxopixo]

Donc si tu vois une autre méthode que de détailler toutes les fonctions pour estimer un temps de calcul je suis preneur

Tu testes, il n'y aura pas meilleur estimation.

[Jack]

Tu testes, il n'y aura pas meilleur estimation.

Le problème, si j'ai bien compris, est d'estimer le temps de calcul pour calibrer le µContrôleur. Or si tu testes, c'est que tu as déjà fait le choix de ce dernier.

Il faudrait voir si certains outils de développement ne proposent pas de simulateur, ce qui permettrait de faire des mesures de temps d'exécution. Ca existe pour des µC basiques. Pour des ATOM ou ARM de haut de gamme, je ne sais pas.

A+

[lou_ibmix_xi]

C'est toujours compliqué de choisir une architecture à priori... Perso, je choisirai une gamme de CPU, je trouve une carte d'évaluation avec la CPU la plus costaud de sa famille (vitesse _ET_ mémoire), j'implante mon algo et je regarde, alors dans un 2ème temps je revoie à la baisse la CPU. C'est surtout valable lorsqu'il y a une grosse série, car la différence de coût entre une CPU bas de gamme et haut de gamme d'une même famille est en générale négligeable pour des petites quantitées.

Pour choisir une famille, les questions a se poser sont (en vrac et non exhaustif):

-mémoire nécessaire => nécessité de mémoire externe et combien
-16 bits ou 32 bits
-si l'algo est implantable en virgules fixes, évaluer le MIPS, sinon FOPS (attention prendre une sacrée marge)
-compétence perso en informatique très bas-niveau, design électronique etc vs le temps/argent alloué au projet

cette dérnière est, je pense, la considération prédominante, car si tu (ton équipe) n'as jamais fait de design de carte, ni de "board support package", tu n'auras d'autre choix que de t'orienter vers une carte de développement bien supportée par un "OS" comme FreeRTOS et autre eCos.

[kronanberg]

Salut,

Merci pour ces réponses.

Pour information, je réalise actuellement une thèse, le but est maintenant de développer un prototype permettant de tester et valider mes algorithmes. Donc pour le moment la solution envisagée est d'utiliser une carte de développement qui sera destinée uniquement au traitement des données. L'acquisition des capteurs se fera via des microcontroleurs (où la j'ai les connaissances pour réaliser mes cartes d'acquisition).


Mais dans un premier temps, je crois que je vais suivre ton conseil et prendre une carte de développement qui me permettra à coup sur d'implémenter mon algo. Le projet n'est pas pour une grande série donc c'est sur que ce n'est pas la différence de coût entre 2 CPU qui jouera dans mon choix mais plutôt la consommation de mon processeur. Mais cette partie concernera plutôt l'amélioration du prototype.

Par contre comme je vois que vous avez de bonnes connaissances dans le domaine de l'embarqué est ce que vous avez des références sur des livres dans le domaine des OS embarqués temps réel. A priori par rapport aux connaissances de mes collègues de travail, j'envisagerai plutôt de partir sur un RTLinux.

[lou_ibmix_xi]

A priori par rapport aux connaissances de mes collègues de travail, j'envisagerai plutôt de partir sur un RTLinux.

Je n'ai jamais joué avec du linux temps réel dur. Mais ce que je peux en dire c'est que:

-faire du temps réel dur avec linux nécessite d'utiliser ADEOS (ou XENOMAI), donc les parties temps réels ne se font pas "dans" linux, et je ne connais pas les moyens de communications entre l'espace temps réel et linux
-linux c'est du lourdingue, donc ça dimensionne déjà ta plateforme en terme de CPU et de mémoire, et suivant les applications, ces dimensions sont au-delà de ce qui serait nécessaire pour gérer que la partie métier

L'intérêts de linux pour l'embarqué est, à mon avis:
-lorsqu'une majorité du projet peut-être implanté grâce à des bibliothéques / logiciels déjà existants et tournant sur linux
-lorsque le projet nécessite déjà une CPU assez costaud permettant d'utiliser linux

Après, pour une application "simple", utiliser LINUX, FreeRTOS ou eCos, au niveau de la programmation ça ne change pas franchement puisque tu auras accès aux mêmes services (fils d'executions concurents, semaphores, etc), l'avantage des 2 derniers sur le premier est qu'ils sont temps réel dur et nettement plus léger.

Je joue avec eCos, je ne suis pas un grand fan car il propose beaucoup trop de chose et on est très vite perdu dans la masse de ce qui est fourni, sans compter des morceaux en C++ (j'avoue qu'en vieux réac de l'embarqué ça me dresse les cheveux sur la tête). FreeRTOS à l'air pas mal, et à la différence de eCos il ne fait que sont bouleau: installer le runtime C, les vecteurs d'interruptions et te proposer un ordonnaceur de tâche, des méchanismes de synchro etc... Pour le FAT, la pile TCP/IP et autre, si tu en as besoin, a toi de trouver une implémentation qui te convienne et à l'intégrer, et je trouve cette approche nettement plus pertinante pour de l'embarqué.

Jette un oeil sur FreeRTOS et surtout les cartes de dev supportées, tu y trouveras peut-être ton bonheur. Si c'est vraiment du linux que tu veux, ça va se jouer (en gros et en puissance/consommation croissante) entre ARM, ATOM et PENTIUM/CORE/CORE2, l'avantage des deux derniers étants la possibilité d'utiliser une distribution linux classique dans un 1er temps (bien que ça semble de + en + vrai sur les ARM de nos jours). Pour l'ARM, la mode est à la téléphonie et autre tablette, donc tu trouveras énôôôôôôrmément de bouzin sous ANDROID avec des contrôleurs graphiques intégrés, ce qui n'est pas pertinent pour ton besoin (je pense)...

Quelques constructeurs de carte de dev:
bluetechnix, armadeus, embedded artist, toradex, phytec, embedian, gumstix, et aussi les projets de plateformes ouvertes leaopardboard, pandaboard, cranebaord, beagleboard et hawkboard
Attention, de mon expérience, ce ne sont que des revendeur de matériel, le support technique est en général quasi-inexistant sur les problèmes logiciels, mais heureusement il y a des forums particuliers (parfois spécialisés sur une carte) et la communauté des enthousiastes développeurs...

Pour les bouquins, ça va dépendre un peu de la solution que tu vas retenir:
-"ARM System developper's guide" de Sloss, Symes et Wright, si tu veux aller au fond des choses de la plate-forme ARM avec un environement léger (type freeRTOS / eCos)
-"Making Embedded Systems" de Elecia White, je suis en train de le lire, de ce que j'en voie pour l'instant c'est plus pour te donner une méthode de travail pour l'embarqué bas-niveau,

Si c'est pour du linux, linux embarqué ne veux pas dire grand chose (à mon sens), puisque un linux c'est un linux, donc pour tripatouiller le noyau:
-"Linux device drivers 3" de Rubini (accesible gratos sur internet)
-"understanding linux kernel" de Bovet et Cesati
-les sources du noyau

Pour le reste de linux, les bouquins c'est bien mais le mieux c'est de mettre les mains dans le cambouis nottament comprendre l'arborescence, les scripts de démarrage, génération et utilisation de système en RAMDISK, enfin toutes ces choses qui te permettent de faire un système linux minimal complet à la main (c'est franchement pas très compliqué), néanmoins il y a des outils qui existent également (je ne les ai jamais essayer, je ne sais pas ce qu'ils valent): yocto, angstrom, openembedded... Le site eLinux regroupe pas mal d'info sur toute ces choses.

Pas curiosité, quel est le sujet de ta thèse?

[kronanberg]

Mon travail porte sur l'amélioration des performances dans le cadre de la course au large (du point de vu électronique), c'est à dire en grande partie sur la correction des différentes mesures (vent, vitesse ...) perturbées par l'environnement maritime. Pour le moment j'ai surtout travaillé sur matlab pour étudier des algorithmes de corrections et maintenant je vais commencer à réaliser un prototype qui me permettra de valider (ou non) mes solutions proposées.

En tout cas, merci pour tes conseils.