Sous-projet CSG ( SubsetSum@Home )

[Jaehaerys Targaryen]

 

Infos Utiles :

• Statut : Projet terminé
  
  • Url pour s'y attacher : http://volunteer.cs.und.edu/subset_sum/
  • L'alliance Francophone : http://volunteer.cs.und.edu/subset_sum/team_display.php?teamid=10
  • Articles sur le site de L'AF : pas encore.
  • Classement mondial de L'AF : http://fr.boincstats.com/stats/team_stats.php?pr=subsetsum&st=0
  • Temps de calcul et points de sauvegarde : http://wuprop.boinc-af.org/results.html
  • Avancement des sous-projets : pas d'infos disponibles.
  • État du Serveur : http://volunteer.cs.und.edu/subset_sum/server_status.php
  • Affiliation : Université du Dakota du Nord - États-Unis
  
  
  
  
  Résumé :
  
  
       Le problème de la somme de sous-ensembles (Subset Sum) est décrit ainsi: étant donné un ensemble d'entiers positifs S et une somme cible t, existe-t-il un sous-ensemble de S dont la somme fait t? C'est l'un des problèmes importants en complexité algorithmique. En réalité il s'agit d'un problème très simple, et le programme requis pour le résoudre n'est pas très compliqué. Ce qui représente le plus grand problème est le temps d'exécution -  tous les algorithmes d'approximations ont des durées d'exécutions qui sont proportionnelles à une fonction exponentielle du nombre d'éléments dans l'ensemble (pour le pire des cas). Plus de détails sur le problème de la somme des sous-ensembles ici
  
       Au fil des ans, il a été montré qu'un grand nombre de problèmes combinatoires sont de la même classe que Subset Sum (appelé problème NP-complet). Cependant, en fonction dont la mesure de la taille du problème est réalisée, il existe certains signes laissant penser que Subset Sum est en fait un problème plus simple que la plupart des autres de sa classe. Le but de ce projet est de renforcer les signes indiquant que Subset Sum est en fait un problème complexe "simple".
  
       Supposons que nous avons un ensemble de n nombres positifs S dont le maximum est m. Nous allons définir le ratio n/m comme étant la densité de l'ensemble et prendront ∑S comme étant la somme de tous les éléments de l'ensemble. Si l'on regarde la liste des sommes produites par des sous-ensembles de S, on remarque que très peu de somme sont manquantes si S est suffisamment dense. En fait, il semblerait qu'il existe un palier de densité à partir duquel on aura toutes les sommes entre m et  ∑S / 2. Nos expériences préliminaires nous ont conduit à l'hypothèse suivante: Un ensemble d'entiers positifs ayant pour élément maximum m et dont la taille n est supérieur à floor(m/2) + 1 (floor c'est l'entier directement inférieur; floor(4.5) => 4), possède un sous-ensemble dont la somme est t et cela pour tout t dans l'intervalle m < t < ∑S − m.
  
       Voilà donc ou vous pouvez aider. Pour le moment nous n'avons pas pu démontrer cette hypothèse. Vous seriez d'une énorme aide si vous pouviez nous envoyer une preuve (ou nous montrer où en trouver une dans la littérature de recherche), ainsi le projet serait terminé. Mais si vous voulez apporter un peu moins d'aide et si vous voulez vous amusez, vous pouvez utiliser votre ordinateur afin de voir jusqu'où nous pourrons pousser la preuve empirique. Vous nous aiderez également à trouver de meilleurs moyens d'appliquer le calcul distribué aux problèmes combinatoires.
  
  
  
  Applications CPU :
  
       Disponible pour Windows (32 et 64bits), Linux (32 et 64bits) et Mac (32 et 64bits).
  
  
  
  Applications GPU :
  
       Il est question du développement d'une application GPU pour les cartes Nvidia.
       Le 27/09/12 - il est question des premières applications de test pour dans quelques semaines.
  
  
  
  Dernière Info :
  
  Le 27/09/2012
  
  

  I think I've turned on workunits being sent out by priority -- this means that your WUs won't wait in the queue forever waiting for a wingman since they're added to the end of the workunit queue. Please let me know how they're working.
  
  On another note, a student and I have been working on a CUDA application for SubsetSum@Home, so I'm hoping to get test versions of that out in a couple weeks.

  
  

  Je pense que j'ai activé l'envoi d'unité par priorité -- cela signifie que vos WUs n'attendront plus éternellement un "wingman" dans la file étant donné qu'elles sont ajoutées à la fin. Veuillez me faire savoir comment ça se passe.
  (Il doit probablement parler des cas ou le réplica initial est annulé ou n'est pas renvoyé à temps.)
  
  Je tiens également à annoncer qu'un étudiant et moi même avons travaillé sur une application CUDA pour SubsetSum@Home, j'espère avoir les premières version de test de disponible dans quelques semaines.

  
  
  Remerciement à Damien d'avoir trouver ce projet...
  
  mise à jour par fzs600 le 8 janvier 2021.

[cedricdd]

Le problème de la somme de sous-ensembles (Subset Sum) est décrit ainsi: étant donné un ensemble d'entiers positifs S et une somme cible t, existe-t-il un sous-ensemble de S dont la somme fait t? C'est l'un des problèmes importants en complexité algorithmique. En réalité il s'agit d'un problème très simple, et le programme requis pour le résoudre n'est pas très compliqué. Ce qui représente le plus grand problème est le temps d'exécution -  tous les algorithmes d'approximations ont des durées d'exécutions qui sont proportionnelles à une fonction exponentielle du nombre d'élément dans l'ensemble (pour le pire des cas).

Au fil des ans, il a été montré qu'un grand nombre de problèmes combinatoires sont de la même classe que Subset Sum (appelé problème NP-complet). Cependant, en fonction dont la mesure de la taille du problème est réalisée, il existe certains signes laissant penser que Subset Sum est en fait un problème plus simple que la plupart des autres de sa classe. Le but de ce projet est de renforcer les signes indiquant que Subset Sum est en fait un problème complexe "simple".

Supposons que nous avons un ensemble de n nombres positifs S dont le maximum est m. Nous allons définir le ratio n/m comme étant la densité de l'ensemble et prendront ∑S comment étant la somme de tous les éléments de l'ensemble. Si l'on regarde la liste des sommes produites par des sous-ensembles de S, on remarque que très peu de somme sont manquantes si S est suffisamment dense. En fait, il semblerait qu'il existe un palier de densité à partir duquel on aura toutes les sommes entre m et  ∑S / 2. Nos expériences préliminaires nous ont conduit à l'hypothèse suivante: Un ensemble d'entiers positifs ayant pour élément maximum m et dont la taille n est supérieur à floor(m/2) + 1 (floor c'est l'entier inférieur; floor(4.5) => 4), possède un sous-ensemble dont la somme est t et cela pour tout t dans l'intervalle m < t < ∑S − m.

Voilà donc ou vous pouvez aider. Pour le moment nous n'avons pas pu démontrer cette hypothèse. Vous seriez d'une énorme aide si vous pouviez nous envoyer une preuve (ou nous montrer où en trouver une dans la littérature de recherche), ainsi le projet serait terminé. Mais si vous voulez apporter un peu moins d'aide et si vous voulez vous amusez, vous pouvez utiliser votre ordinateur afin de voir jusque où nous pourrons pousser la preuve empirique. Vous nous aiderez également à trouver de meilleurs moyens d'appliquer le calcul distribué aux problèmes combinatoires.

SubsetSum@Home est basé au Département des Science Informatique à l'Université du Dakota du Nord.   

Faut relire sûrement

[toTOW]

Encore un projet qui va pas servir à grand chose si ce n'est produire de la chaleur ...

[JeromeC]

Si, il me permet dès maintenant et sans m'y inscrire de me rappeler pourquoi j'ai laissé la plus grande distance possible (appelons la Dp) entre moi (appelons moi M) et les mathématiques (appelons les m) après mon bac C (appelons le bC).

Nous avons donc bC < Dp[M,m] < +∞

Ou quelque chose d'approchant. A peu de choses près.

[fzs600]

Si, il me permet dès maintenant et sans m'y inscrire de me rappeler pourquoi j'ai laissé la plus grande distance possible (appelons la Dp) entre moi (appelons moi M) et les mathématiques (appelons les m) après mon bac C (appelons le bC).

Nous avons donc bC < Dp[M,m] < +∞

Ou quelque chose d'approchant. A peu de choses près.

[fzs600]

Status du serveur : http://volunteer.cs.und.edu/subset_sum/server_status

[Infomat]

Tous les serveurs sont ok mais pas de wu...

[fzs600]

 

Quest-ce que c'est que cette application ?Quelqu'un a une idée ?

Linux Beowulf Cluster running MOAB job scheduler and MPICH2 on an AMD x86_64 CPU

http://volunteer.cs.und.edu/subset_sum/apps.php

Merci.

[toTOW]

Voir ici : http://fr.wikipedia.org/wiki/Cluster_Beowulf

Et ici : http://www.mcs.anl.gov/research/projects/mpich2/

P.S : cette technologie (MPI) était utilisée par FAH dans son core Gromacs SMP première génération mais a été remplacée par la gestion par thread, bien plus efficace sur une machine unique.

[fzs600]

Voir ici : http://fr.wikipedia.org/wiki/Cluster_Beowulf

Et ici : http://www.mcs.anl.gov/research/projects/mpich2/

P.S : cette technologie (MPI) était utilisée par FAH dans son core Gromacs SMP première génération mais a été remplacée par la gestion par thread, bien plus efficace sur une machine unique.

toTOW   

Merci pour l'explication.

[modesti]

Des nouvelles de Travis !

some updates
Hi Everyone,

The last couple weeks have been hectic! I was off in NY to give a presentation at IBM T.J. Watson Research center. Now that I'm back I have a few more updates for everyone.

First, I've made a portal on the front page of this volunteer computing server with links to the other projects we'll be running here: http://volunteer.cs.und.edu/index.html

Notably, SubsetSum@Home and Wildlife@Home. We're starting to get video for wildlife@home, which should prove really interesting so it might be worth taking a look at that project over there. I'll also be starting to send out workunits for SubsetSum@Home by the end of the week (as we have a deadline for a conference and would like to have the project running by then). After SubsetSum@Home is up and sending out workunits, I'll be updating the client application here (to fix the checkpointing issue) and sending out some more workunits.

Until then, hopefully the videos we'll be putting up on wildlife@home will keep you interested, and the workunits at subsetsum@home will keep your computers busy.

--Travis 11 Apr 2012 | 18:31:28 UTC

Traduction :
Quelques infos
Salut tout le monde,

Les dernières semaines ont été mouvementées ! J'étais à New York pour une présentation au Centre de recherche T.J. Watson d'IBM. Maintenant que je suis de retour, j'ai quelques informations supplémentaires pour tous.

Tout d'abord, j'ai fait un portail sur la page d'accueil de ce serveur de calcul volontaire avec des liens vers les autres projets que nous ferons tourner ici : http://volunteer.cs.und.edu/index.html

Notamment, SubsetSum@Home et Wildlife@home. Nous commençons à avoir des vidéos pour Wildlife@home qui devraient s'avérer vraiment intéressantes, cela vaudrait le coup de jeter un coup d'oeil à ce projet. Je commencerai aussi à envoyer des UT pour SubsetSum@Hom d'ici la fin de la semaine (car nous avons une date limite pour une conférence et aimerions avoir le projet prêt et en fonctionnement d'ici là). Une fois que SubsetSum@Home sera prêt et enverrai des UT, je mettrai à jour l'application client ici (pour remédier au problème des points de sauvegarde) et enverrai quelques UT supplémentaires.

D'ici là, j'espère que les vidéos que nous mettrons sur Wildlife@home vous maintiendront intéressés et que les UT sur SubsetSum@Home garderont vos ordinateurs occupés.

***
Copie du message publié chez DNA@Home (car trouvé sur le serveur de DNA)

[fzs600]

Le premier lot de workunits pour MAc et Gnu-linux .
http://volunteer.cs.und.edu/subset_sum/forum_thread.php?id=11

[fzs600]

 

[kasur]

Merci 

edit: 

[Jaehaerys Targaryen]

même pour windows 

[kasur]

5 erreurs sur 6... et elles étaient allées au bout

[Jaehaerys Targaryen]

Moi aussi, la seule pour l'instant que j'ai renvoyé est en erreur...

[fzs600]

Je rentre du taf et prem's (bis)   
https://statseb.boinc-af.org/classement_membres.py?projet=163&offset=0#1

[Hildor]

 

[fzs600]

Mais c'est bien aussi deuxieme !   
https://statseb.boinc-af.org/classement_membres.py?projet=129&offset=0#1 

[Hildor]

Oui, je collectionne les deuxièmes places, 7 au total 

[cedricdd]

 

New Workunits, Applications and Validator
Hi Everyone,

Updated the applications to 0.06 (hopefully fixing the checkpointing issue). I think I've also fixed the issue with the validator behaving really weirdly and erroring out valid workunits. Let me know how things are working.

Nouvelles tâches, applications et validateur
Bonjour tout le monde,

J'ai mis à jour les applications vers la version 0.06 (en espérant avoir réparé le problème avec les points de sauvegarde). Je pense que j'ai également réparé le problème avec le validateur qui se comportait étrangement et ne validait pas certaines  des tâches. Veuillez me prévenir si quelque chose ne va pas.

[kasur]

 

[cedricdd]

more updates and new workunits
Applications are now on v0.07. They should be printing more information about the standard int type I'm using; you'd think that stdint would be standard across operating systems/architectures, as that's its name but I guess it isn't.

D'autres mise à jour et de nouvelles tâches
Les applications en sont maintenant à la version 0.07. Elles devraient afficher plus d'informations à propos du nombre entier que j'utilise; on pourrait penser que stdint aurait le même standard sur différentes architectures/systèmes, mais il faut croire que ce n'est pas le cas.

[cedricdd]

validation issue
So it looks like linux and windows are generating different checksums (even if they aren't checkpointed -- which is nice because it looks like checkpointing is working correctly).

I'll be debugging the windows vs linux problem locally, so I won't be sending out more workunits until I've resolved that. I'll also be scaling the credit up in the next batch of workunits -- does anyone have a good suggestion about how much credit each workunit should be worth (as they're fixed size)? I could just calculate the credit manually for each workunit and use that instead of the creditnew system.

Problème de validation
Il semblerait que Linux et Windows génèrent différentes sommes de contrôle (même si elles ne sont pas sauvegardées -- ce qui est bien puisqu'il semblerait que les points de sauvegarde fonctionnent correctement).

Je vais débugger le problème Windows vs Linux localement, je ne vais donc pas envoyer de nouvelles tâches jusqu'à ce que cela soit résolu. Je vais également augmenter les crédits pour le prochain lot de tâches -- est ce que quelqu'un a une suggestion sur le montant que devrait valoir une unité (étant donné qu'elles sont de taille fixe)? Je pourrai juste calculer les crédits manuellement pour chaque tâches et l'utiliser à la place du nouveau système de crédit.