Auteur Sujet: Sous-projet CSG ( SubsetSum@Home )  (Lu 13106 fois)

0 Membres et 1 Invité sur ce sujet

Jaehaerys Targaryen

  • CàA
  • Messages: 10388
  • Boinc'eur devant l'éternel
  • *****
  •   
Sous-projet CSG ( SubsetSum@Home )
« le: 22 mars 2012 à 13:31 »
 
 
Infos Utiles :





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

Citer
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.

Citer
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 28 septembre 2012 par cedricdd.
« Modifié: 25 février 2015 à 19:41 par ousermaatre »


Twitter : devweborne // Chaine Youtube : https://www.youtube.com/channel/UCXcoCd-1UlHpYIYzNER0n1Q

cedricdd

  • Messages: 1389
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #1 le: 22 mars 2012 à 16:20 »
Citer
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 :p
« Modifié: 22 mars 2012 à 17:09 par cedricdd »
Kill all my demons, and my angels might die too.

toTOW

  • Messages: 3544
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #2 le: 22 mars 2012 à 20:06 »
Encore un projet qui va pas servir à grand chose si ce n'est produire de la chaleur ...
FAH-Addict, première source d'information francophone sur le projet Folding@Home.

JeromeC

  • CàA
  • Messages: 22011
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #3 le: 22 mars 2012 à 21:56 »
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.
Parce que c'était lui, parce que c'était moi.

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : Re : SubsetSum@Home
« Réponse #4 le: 22 mars 2012 à 23:10 »
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.
:warf:

Utilisateur GNU-LINUX. fzs600@jappix.com

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #5 le: 14 avril 2012 à 10:37 »

Utilisateur GNU-LINUX. fzs600@jappix.com

Infomat

  • Animateur fanatique
  • Messages: 5319
  • Boinc'eur devant l'éternel
  • *****
  •   
    • Site de Claude
Re : SubsetSum@Home
« Réponse #6 le: 15 avril 2012 à 02:43 »
Tous les serveurs sont ok mais pas de wu...


[6c/ 12t] Intel i7-980X @3.7  2xNVidia GTX 760  AMD 6970    Windows 7 Pro x64 ou Windows 10 Pro x64 ou Linux 
ELAF= Electrons Libres de l'AF http://forum.electronslibres.boinc-af.org/

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #7 le: 17 avril 2012 à 10:29 »
 :hello:

Quest-ce que c'est que cette application ?Quelqu'un a une idée ?
Citer
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.

Utilisateur GNU-LINUX. fzs600@jappix.com

toTOW

  • Messages: 3544
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #8 le: 17 avril 2012 à 20:54 »
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.
FAH-Addict, première source d'information francophone sur le projet Folding@Home.

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : Re : SubsetSum@Home
« Réponse #9 le: 18 avril 2012 à 07:01 »
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   :kookoo:

Merci pour l'explication.

Utilisateur GNU-LINUX. fzs600@jappix.com

modesti

  • CàA
  • Messages: 15333
  • Boinc'eur devant l'éternel
  • *****
  •   
    • Brocantes en Bourbonnais
Re : SubsetSum@Home
« Réponse #10 le: 18 avril 2012 à 19:58 »
Des nouvelles de Travis !
Citer
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)

Viendez chez nous, cause qu'on est les meilleur(e)s :D


In memoriam Jip

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #11 le: 23 avril 2012 à 18:22 »
Le premier lot de workunits pour MAc et Gnu-linux .
http://volunteer.cs.und.edu/subset_sum/forum_thread.php?id=11

 :jap:

Utilisateur GNU-LINUX. fzs600@jappix.com

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #12 le: 24 avril 2012 à 21:45 »
 :hyperbon: :hyperbon:

Utilisateur GNU-LINUX. fzs600@jappix.com

kasur

  • Messages: 2998
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #13 le: 24 avril 2012 à 22:04 »
Merci  :love:

edit:  :hyperbon: :hyperbon:

et 194 SETI@home classic workunits (4 764 hours) :p Toutes les Minivilles AF

Jaehaerys Targaryen

  • CàA
  • Messages: 10388
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #14 le: 24 avril 2012 à 23:33 »
même pour windows  :hyperbon: :hyperbon:


Twitter : devweborne // Chaine Youtube : https://www.youtube.com/channel/UCXcoCd-1UlHpYIYzNER0n1Q

kasur

  • Messages: 2998
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #15 le: 24 avril 2012 à 23:41 »
5 erreurs sur 6... et elles étaient allées au bout

et 194 SETI@home classic workunits (4 764 hours) :p Toutes les Minivilles AF

Jaehaerys Targaryen

  • CàA
  • Messages: 10388
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #16 le: 25 avril 2012 à 12:23 »
Moi aussi, la seule pour l'instant que j'ai renvoyé est en erreur...


Twitter : devweborne // Chaine Youtube : https://www.youtube.com/channel/UCXcoCd-1UlHpYIYzNER0n1Q

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #17 le: 26 avril 2012 à 17:27 »

Utilisateur GNU-LINUX. fzs600@jappix.com

Hildor

  • DROITS - Journalistes
  • Messages: 6046
  • Boinc'eur devant l'éternel
  • *
  •   
Re : SubsetSum@Home
« Réponse #18 le: 26 avril 2012 à 19:53 »
 :rhaa:

fzs600

  • Animateur fanatique
  • Messages: 5706
  • Boinc'eur devant l'éternel
  • *****
  •   

Utilisateur GNU-LINUX. fzs600@jappix.com

Hildor

  • DROITS - Journalistes
  • Messages: 6046
  • Boinc'eur devant l'éternel
  • *
  •   
Re : SubsetSum@Home
« Réponse #20 le: 27 avril 2012 à 20:58 »

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

cedricdd

  • Messages: 1389
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #21 le: 02 mai 2012 à 00:00 »
 :hyperbon:

Citer
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.

Citer
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.
« Modifié: 02 mai 2012 à 00:08 par cedricdd »
Kill all my demons, and my angels might die too.

kasur

  • Messages: 2998
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #22 le: 02 mai 2012 à 00:03 »
 :jap:

et 194 SETI@home classic workunits (4 764 hours) :p Toutes les Minivilles AF

cedricdd

  • Messages: 1389
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #23 le: 02 mai 2012 à 21:43 »
Citer
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.

Citer
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.
Kill all my demons, and my angels might die too.

cedricdd

  • Messages: 1389
  • Boinc'eur devant l'éternel
  • *****
  •   
Re : SubsetSum@Home
« Réponse #24 le: 03 mai 2012 à 02:37 »
Citer
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.

Citer
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.
Kill all my demons, and my angels might die too.