Retour d'exprience sur le premier sujet

Retour d'exprience sur le premier sujet

Le premier concours touche sa fin. Et mme si certains continuent se battre pour obtenir les meilleurs performances, le temps est venu de prendre du recul sur ces dernires semaines.

J'aimerais profit d'un retour d'exprience de la part des vos quipes. Notamment sur votre organisation, la rpartition du (temps de) travail, ce que vous changeriez si vous deviez recommencer ou tout autres anecdotes sur lesquelles vous souhaiteriez attirer l'attention.

Pour lancer ce sujet qui je l''espre sera suivit je vous fait part du miens :
En terme de temps de travail j'ai pass environ environ 60h sur mon code et 20h pour la recherche d'information en parallle (sic) de mes cours. Je n'ai pas vraiment eu la chance de travailler en binmes.
J'ai pass normment de temps implmenter des mthodes qui au final ne m'auront servi rien. Je sais maintenant fois je passerai moins de temps coder et plus de temps rflchir sur la meilleur rponse possible et sur les problmes qu'elle pourrait rencontre. J'ai aussi t choqu pour le nombre de solutions envisageables en rponse un problme alors qu'au final seule deux ou trois donnent un rsultat optimale. Une dernire chose qui m'a surpris est l'utilisation intensive des mathmatiques pour l'optimisation. Mais peut-tre tait-ce d au sujet ?

Merci d'avance pour vos retours.

28 posts / 0 nouveau(x)
Dernière contribution
Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.

Tu n'as pas dormi? ^^ Parce que j'ai du y passer 3 fois moins de temps que toi au total.
Mine de rien c'est un "petit" problme. Aussi, d'aprs mon exprience c'est difficile de se rpartir les tches plusieurs lorsqu'il y aussi peu de code produire. C'est plus simple sur des gros projets ou tu peux discerner plusieurs parties bien distinctes. Par exemple une partie interface, et une partie backend. Par contre pour rflchir, tre deux, c'est bien.

Soyons constructifs, tout le monde n'a pas les mmes comptences ... mes conclusions?1. il ne faut pas choisir le C++ pour faire de l'ILP ... icpc ne: unroll, vectorise pas les boucles, et ne prefetche pas les variables globales. icc le fait trs bien... je savais que les compilos C++ sont merdiques pour l'ILP, mais pas ce point... un gros choc.2. J'ai opt pour une approche rcursive pour expertiser Cilk+, un gros bide ... version parallle 20 fois moins rapide que la version squentielle.3. OpenMP ne paralllise pas correctement les boucles de petites tailles (la mienne fait 10itrations), mme s'il y a un gros travaille derrire ... Il ne cre que 2Threads alors que j'en demandais 9. On peut faire un unroll complet puis crer des sections, mais cela n'tant pas mon objectif, et ne comptais pas sur moi pour faire le travail du compilo4. TBB::TASK EST ENORME (mme si un peu moins flexible que Cilk++) ... une maitrise de pointe du grain de paralllisme, des acclrations de fous ... dommage qu'un bug trainait quelques parts, et que mes rsultats taient un peu tronqus.Ma premire motivation n'tant pas d'tre fond dans le jeu, mais d'expertiser un max de parallel tools ...Sinon, j'ai fini par participer, j'espre que je vais gagner un petit truc, mon anniversaire est dans 1 semaine ... et mon Hp compaq m'a lch y a une dizaine aprs 5ans de loyaux services.voil,

Je ne sais pas combien de temps j'y ai pass en tout mais ... beaucoup.

Pendant une premire phase j'ai normment rflchi l'algorithme optimal sans rien programmer. Et apparemment je l'ai trouv puisque une fois implment et lanc sur 1 thread je met un tout petit peu plus d'1 seconde. A partir de ce moment l, je savais donc que j'avais quelque chose de vraiment pas mal entre les mains.

Ensuite au niveau de la paralllisation, l a a t trs trs galre pour gagner du temps. Un premier jet m'a permis d'atteindre 600 millisecondes sans trop de problme. Mais pour descendre en dessous a a t du grand n'importe quoi avec des fonctions pour "slicer" mes tches qui ne ressemblent pas grand chose avec des logarithmes et des exponentielles partout. A mon avis j'aurai mieux fait de changer d'option (ici OpenMP), parce que je suis convaincu qu'un bon tiers du programme est pass faire de l'attente/synchro par OpenMP. Mais bon, maintenant je le saurai ;-)

Et puis dernire ligne droite aujourd'hui, le temps final est assez variable mais en gros a s'tale entre 80ms (j'ai un screen 74ms) et 180ms.

Enfin voil quoi, trs bonne exprience, et je suis dans les starting blocks pour le prochain ;-)

Pareil pour moi, j'ai 50% d'overhead. Soit un tiers du temps de mon programme qui est totalement inutile.

Dj j'ai eu beaucoup de plaisirs participer et rflchir sur ce problme.

Rimaxime et moi avons travaill en binome malgr la distance qui nous sparait les 3/4 de la semaine (la partie o nous tions en entreprise).

Ca a ncessit quelques amnagements (mise en place d'un serveur subversion, collaboration au travers de google documents, ect ...) ainsi que de la mthode.
Nous tions forc de tester unitairement toutes nos contributions pour s'assurer que chaque fonction rpondait au besoin pour lequel elle avait t cod. Notre collaboration est rcente et c'est pourquoi nous ne pouvions pas nous permettre d'diter trop souvent nos fonctions respectives, trop de risques de mauvaises comprhension du code existant ou d'oubli. Sur la fin, c'etait plus facile. Nous commencions connaitre nos habitudes respectives.

Cot technique, nous avons utilis le C. Nous avions peu de connaissances en programmation systme. Ca a t l'occasion d'explorer cette dimension.

Pour le paralllisme, nous tions parti sur une approche pThread base de ThreadPool mais nous avons renonc en cours de route en constatant que il tait possible de subdiviser le problme en tache de temps relativement constant. Nous avons termin par une simple implmentation partir d'OpenMP. Un regret de ne pas avoir eu le temps d'utiliser les outils d'Intel, notamment pour profiler (nous avions trop de choses apprendre cote).
Nous divisons par 7 le temps d'execution du programme en utilisant 40 processeurs. Nous sommes dus de notre rsultat ce niveau. C'est l'un des axes sur lequel nous devrons travailler.

Nous sommes partis ds le dpart sur la bonne solution. Cependant, nous nous sommes arrts un cran trop tot en terme d'optimisation mathmatique. Ce n'est qu'en dcouvrant vos rsultats que nous avons constat notre erreur. Malgr nos efforts le dernier jour, nous ne sommes pas parvenu terminer l'implmentation d'une approche plus optimis n'utilisant plus du tout de numrique, exclusivement des combinaisons.

Je prends note de 2 points pour la seconde tape :
- la concurrence est la fois saine et rude. Un vrai plaisir
- tre sur tous les fronts et ne rien lacher. Penser le problme de faon globale.

Fabien

Pour ma part, mon binome et moi n'avions que trs peu de temps car beaucoup d'autres choses faire en parallle. Le temps total de travail doit avoisiner la dizaine d'heure.
Dveloppeurs de formation et non pas mathmaticiens, nous nous somme plus accs sur l'optimisation du code et la paralllisation que sur la recherche d'un algorithme optimal au sens mathmatique du terme.

Le point fort de notre programme tiens dans l'utilisation massive de la mtaprogrammation (merci C++ contrairement ce que certain disent) afin de rsoudre un maximum de choses la compilation et une paralllisation trs simple du code avec trs peu d'overhead du aux synchronizations (merci TBB :P).
On s'en est sorti au final avec 400 lignes de codes (commentaires compris), on aura surement pas la solution la plus rapide mais on la trouve trs sexy en tous cas.

Quoi qu'il en soit le concours est trs agrable et j'ai hte de voir le prochain sujet !

Je ne voudrais pas cracher dans la soupe mais si vous vous en tes tenus l'algorithme "trivial", il est tout fait normal que la paralllisation se fasse bien, avec quasiment aucun overhead. TBB ou pas d'ailleurs.

Il me semble que la mta programmation tait interdite.

Rien n'empchait d'crire un programme qui venait effectuer tous les calculs au moment de la compilation et venait juste restituer les rsultats la demande ...

Ne l'ayant jamais utilis, j'ai toute de mme hate de voir comment vous l'avez mis en oeuvre.

Fabien

Ce n'est pas qu'lle est interdite,la mtaprogrammation, mais presque inutile pour cette comptition ... l'nonc tait clair ... des entiers de 64bits. Pas un autre type supporter (pour ceux qui ont pens gmplib) !!

La meta-programmation c'est la programmation gnrative. Ce qui veut dire qu'ils font des calculs "implicitement" en gnrant du code la compilation (dans le cas de C++). Ca me parait effectivement limite comme dmarche dans le cadre d'un concours d'optimisation.

Moi aussi j'avais pens la mta-programmation au dbut, mais j'ai vite chang d'ide parce que tout l'intrt du truc c'tait justement de ne rien prcalculer du tout et que tout soit calcul l'excution... Si quelqu'un arrivait premier du concours en ayant utilis la mtaprogrammation haute dose, je pense qu'une analyse prcise par le jury serait ncessaire...

Je ne comprends pas ta rponse VinceRev,on peut trs bien faire de la mtaprogrammation (les C++ templates), sans pour autant prcalculer quoique ce soit. Nouce dont Achilles parlait, c'est le fait d'utiliser des types gnriques pour implmenter des fonctions ou classes gnriques ... et de faire le versionning au moment des dclarations des fonctions ou des objets grce l'oprateur c++ <>.Sinon, je pense que la mtaprogrammation n'altre en rien l'optimisation,les templates seront versionns par une passe suprieure qui prcdera les passes d'optimisation (qui elles personnaliseront les opt en fonction du type).l'ambrouille est plutt pour le lecteur du code (le dveloppeur par l'occasion) ... je viens de faire un petit test qui consolide mon intuition:

[cpp]#include 
using namespace std;

template< typename T>   T       SOMME(T t1[],T t2[]){
T       res[10];
T       result=0;
for(int i=0;i<10;i++)
        res[i]=t1[i]+t2[i];
for(int i=0;i<10;i++)
        result+=res[i];
return result;
}


int main(void){
int t[10],t2[10],res1;
short t3[10],t4[10], res2;

res1=SOMME(t,t2);
res2=SOMME(t3,t4);

cout< les warnings de compil
 test]$ icpc -fast -axSSE3,SSE4   -vec-report3  test.cc  -S
test.cc(19): (col. 6) remark: LOOP WAS VECTORIZED.
test.cc(19): (col. 6) remark: LOOP WAS VECTORIZED.
test.cc(19): (col. 6) remark: loop was not vectorized: existence of vector dependence.
test.cc(20): (col. 6) remark: vector dependence: assumed ANTI dependence between result line 20 and result line 20.
test.cc(20): (col. 6) remark: vector dependence: assumed FLOW dependence between result line 20 and result line 20.
test.cc(20): (col. 6) remark: vector dependence: assumed FLOW dependence between result line 20 and result line 20.
test.cc(20): (col. 6) remark: vector dependence: assumed ANTI dependence between result line 20 and result line 20.

Je ne parlais en l'occurence pas de la gnricit, qui ne pose videmment aucun problme vis vis des rgles du concours. Je sais seulement qu'avec la mtaprogrammation on peut faire des trucs assez tordus. On peut par exemple imaginer un code qui calculerait les SmallBrain ... la compilation. Cette liste ne serait pas prsente dans le code source, mais figurerait bien dans le code assembleur de l'excutable d'o le caractre trs tendancieux d'une telle pratique.

Je ne parlais en l'occurence pas de la gnricit, qui ne pose videmment aucun problme vis vis des rgles du concours. Je sais seulement qu'avec la mtaprogrammation on peut faire des trucs assez tordus. On peut par exemple imaginer un code qui calculerait les SmallBrain ... la compilation. Cette liste ne serait pas prsente dans le code source, mais figurerait bien dans le code assembleur de l'excutable d'o le caractre trs tendancieux d'une telle pratique.Je serai preneur, si tu as un pointeur qui parle de a!

Voici le lien d'un article que j'avais trouv extrmement original. L'auteur propose de faire rsoudre le problme du sac dos par le compilateur grce la mta programmation.

http://j-jorge.developpez.com/cpp/meta-kp/

Effectivement, ce genre de code dporte le calcul de l'excution vers la compilation. Il faut donc dans le cas o c'est utilis prendre la somme du temps de compilation et du temps d'excution pour que ce soit valide. Anthony avait prcis dans un poste forum que les prcalculs n'taient pas autoriss. Je crois que nous y avons tous plus ou moins pens en premier lieu.

Retrouv : http://software.intel.com/fr-fr/forums/showthread.php?t=82065&o=a&s=lr

3) Ne vous inquitez pas pour ce genre de chose, nos ingnieurs
veillent au grain. Tout pr calcul est videmment interdit. Nous
nous en assurerons lors de la phase de correction.

Les templates pour crer des conteneurs et viter d'crire une liste chaine pour chaque classe (par exemple), c'est effectivement de la mta programmation mais l'objectif est diffrent. Aucun calcul n'est effectu par le compilateur, c'est un confort et une scurit (plus que bienvenue).

Cependant j'ai envi de voir comment ils ont utilis la mta programmation.

Ola mon post cre de l'engoument ce que je vois.

J'ai essay de rsoudre le problme entier en mtaprog mais a n'est pas possible mon sens, cela ncessiterait de gnrer bien trop de code et le binaire ferait plusieurs Gigaoctets... et la compilation prendrait des heures.

Nous l'avons utiliser pour prcalculer les puissances, l'ide est que l'on allait devoir calculer des puissances entires de 0^0 9^20 (en gros, du au limitations des entiers 64bits).
Comme le calcul de puissance est couteux (O(log(n)) pour les meilleurs algos) on a pr-gnr les 200 rsultats de calculs de puissance pour avoir une rsolution de n^p en O(1).
Je trouve qu'il s'agit d'une optimisation, on a pas pr-gnr les rsultats de l'algorithme, on s'est juste dot d'un outil nous permettant d'acclrer le calcul (et a a pas t vident).

On vient tous d'horizons diffrents il faut composer avec ce que l'on sait faire... j'spre que le deuxime sujet nous permettra d'utiliser ce genre de choses parce que c'est carment fun programmer !

PS : au final on ne gnre qu'un tableau, on aurait pu l'crire directement dans le code... mais un tableau de 200 cases o toutes les valeurs sont crites en dur dans le code c'est une perte de temps et une source d'erreur norme quand on a la chance de pouvoir le faire faire par le compilo ;)

Pour moi, ce genre de choses, c'est un peu de la "premature optimization". Mon algo pour ce problme, travaillait nombre de digit N fix. Du coup la premire chose que je faisais pour chaque N, c'est de remplir un tableau des puissances pour viter d'avoir les calculer. Ca fait parti des choses dont je n'ai mme pas regard le temps d'excution parce que a ne doit mme pas mettre 10us sur toute l'excution du code.

Je rejoins @VinceRev sur ce point. Pour ma part je fais tout en mme temps, du plus petit au plus grand nombre de digits plus les puissances de 10. Et je ne me suis mme pas embt parallliser cette partie.
(Si tu ne fais pas gaffe tu prends plus de temps spawner tes threads qu' faire le calcul sur 1 thread, c'est pour dire)Bien sr, dans une bonne implmentation, les threads ne sont spawns qu'une seule fois.
Par contre, je serais curieux de voir votre code de gnration des puissances. Si vous pouviez poster un lien vers pastebin, a serait sympa... ;-)
Et flicitations, c'est trs bien de penser trs vite la complexit de votre algo. Je signale quand mme que calculer des puissances de nombres c'est forcmment en O(n) (et donc pas en O(1)), mme en multipliant navement... C.a.d que si vous calculez (i^p)_{i in [1,n]} alors le rapport de complexit de vos algos tend, au mieux du mieux vers p, qui est une constante!

Oui l'algo de calcul des puissance appliqu au compilo est en O(n) mais une fois que les rsultats sont gnrs l'opration de calcul de n^p au runtime est en O(1), c'est une simple indexation dans un tableau ;)

Je vais en discuter avec mon binome, on postera surement le code d'ici quelques jours.

Laisser moi faires quelques remarques:1. GCC a du mal avec les constantes qui tiennent sur plus de 32bits.2. La mtaprogrammation ne fait que dans les constantes, et gnre des constantes qui dbordentComment est il possible que, pour gcc titre d'exemple, de grer correctement ce genre de calcul?!

C'est faux. Tu values une complexit sur n lments. Donc mme si tu mets un cycle d'horloge calculer une puissance, tu mets (1 * n) cycles d'horloges calculer n puissances. Tu es donc en O(n). O(1), a voudrait dire que quel que soit le nombre de calculs que tu fais tu mets toujours un temps born. Ce qui est clairement faux.

O(calcul(X^Y)) = O(Y)mais une fois stocks dans une matrice ... y a que l'accs qui est payantO(ACCES(M[X][Y])= O(1)la complexit pire cas se calcule en nombre d'itrations (cycles machines turing qui rsoud le meme problme) ... pas en nombre de cycle!

Un accs c'est une opration. C'est pas gratuit.

Je suis entirement d'accord avec toi, pour lever N nombres une puissance quelconque l'algo est en O(n) (comment faire autrement... )

Je voulais parler de la complexiter d'un algo pour calculer n^p (un entier n la puissance p). Dans ce cas l on peut obtenir un complexit en O(1) au lieu de O(log(n)) pour un algo appliqu au runtime... (on peut toujours chipoter et dire que la lib math est ultra optimise etc... on se mange quand mme l'appel fonction, donc a reste plus long que de faire faire le calcul au compilo et d'inliner la fonction qui fait l'indexation dans le tableau gnr).
O(1) ne veut pas dire gratuit, mais dans les tests que j'ai fait le temps de calcul d'une puissance devenait quivalant celui d'une addition (en mme temps c'est normal au niveau instruction cela revient au mme, une indexation dans un tableau c'est une addition sur la valeur d'un pointeur !)

On s'tait mal compri je crois.

Quoting goog_iceandmagic
Laisser moi faires quelques remarques:1. GCC a du mal avec les constantes qui tiennent sur plus de 32bits.2. La mtaprogrammation ne fait que dans les constantes, et gnre des constantes qui dbordentComment est il possible que, pour gcc titre d'exemple, de grer correctement ce genre de calcul?!

Il faut croire qu'ils ont amlior le compilo, je n'ai eu aucun problme utiliser des entiers 64bits dans le paramtres des templates (il y avait des dbordements avec les types int 32bits).

Selon moi, un des principales optimisation voir tait l'utilisation du backtracking. En effet, si on parcourait tout l'ensemble des entiers de 64 bits, on mettait un temps vraiment trop grand, alors qu'en utilisant le backtracking, on vitait de recalculer plusieurs fois les mmes sommes !

Juste par curiosit, vous mettiez peu prs combien de temps pour faire la recherche sur tout l'intervalle avec les 40 processeurs du MTL (comme vous n'aviez pas post sur le topic performances) ?

Laisser un commentaire

Veuillez ouvrir une session pour ajouter un commentaire. Pas encore membre ? Rejoignez-nous dès aujourd’hui