FlashInformatique.epfl.ch

p/a EPFL - Domaine IT - Station 8 - CH 1015 Lausanne - tél. +41 21 69 322 11

20.12.201110

tout public public averti expert

Prochaines parutions

No Délai de rédaction Parution

1 12.01.12 31.01.12

2 09.02.12 28.02.12

3 08.03.12 27.03.12

Actualités

Voeux de la rédactionLa rédaction du Flash informatique vous souhaite de joyeuses fêtes de fin d’année

et une année 2012 informatique avec, sans, sur ou dans le nuage !

ActualitésDIT-info 2

Jacques vole vers d'autres destinations – Le DIT vous forme – Le prix de l'AFCA – iPhone et Wi-Fi Swisscom

La disparition programmée de l’ordinateur

Marielle Stamm & Yves Bolognini 22

Savoir et savoir-faire en algorithmique

Christian Kauth & Jonas Wagner 24

Echos du ForumIT d’automne

Jean-Claude Berney 27

AnalyseiPad, une révolution dans la salle de classe ?

Bettina Büchel & Iain Cooke 20

Brève

routeRANK 8

Comment faire ?La téléphonie VoIP privée en pratique

Jacques Menu 16

Logiciel libre

Quantum GIS Nicolas Lachance-Bernard &

Timothée Produit 3

Le logiciel libre dans le HPC

Vittoria Rezzonico 10

Vers une informatique pédagogique libre

au DIP genevois ? Marco Gregori 14

page 3

2 20 DÉCEMBRE 2011 - N° 10flash informatique

ImpressumRevue consacrée aux technologies de l’information, éditée par le Domaine IT de l’EPFL (DIT). Les articles n’engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d’autres entités). Toute reproduction, même par-tielle, n’est autorisée qu’avec l’accord de la rédaction et des auteurs.

Rédacteur en chef:Jacqueline Dousson, fi@epfl.chMise en page & graphisme: Appoline Raposo de BarbosaComité de rédaction:Jean-Daniel Bonjour, Patrice Fumasoli, Florence Hagen, Laurent Kling, Julia Paolini, François Roulet, Christophe Salzmann, Richard Timsit & Predrag Viceic

Impression: Atelier de Reprographie EPFLTirage: 4000 exemplairesAdresse Web: flashInformatique.epfl.chAdresse: Domaine IT EPFLStation 8, CH-1015 LausanneTéléphone: +41 21 69 32246 & 32247Abonnement au FI par e-mail à: fi-subscribe@listes.epfl.ch

DIT-info

Actualités

Jacques vole vers d'autres destinations

Après plus de 25 ans de collabora-tion dans le groupe DIT-TI, Jacques Virchaux a pris une retraite bien méritée fin novembre 2011. Il a bien voulu résumer lui-même sa carrière à l’EPFL. Je vous laisse la découvrir:«Le 1er juin 1979, le Professeur Moser m’engagea au Laboratoire de Physique Appliquée pour tra-vailler dans le domaine naissant du Génie Médical. C’est là que j’établirai un premier réseau DECnet point-à-point entre deux ordinateurs PDP-11/34, l’un étant au LPA à l’avenue Ruchonnet, l’autre dans un local aux soins intensifs du CHUV (le bâtiment Nestlé de l’époque). J’ai fait aussi mes premiers pas sur le VAX-11/780 du département de Physique (un des tous premiers à l’EPFL). En 1982, j’ai été engagé par Kurt Oesch dans le nouveau Service Informatique Général issu du Centre de Calcul d’alors. Je m’occuperai d’abord de la distribution des systèmes d’exploi-tation pour les PDP-11 (RT-11 et RSX-11M) dans toute l’école. Il faut dire que cela représentait une pile de quatre à six disques dont la capacité variait entre 2,5 et 10 MB ! Avec l’évolution du parc VAX/VMS, j’ai aussi participé au développement du réseau d’interconnexion aussi bien en interne qu’au niveau national (réseau CHADnet). C’est en 1986 que j’ai été appelé à m’occu-per de messagerie avec le réseau BITNET/EARN, sponsorisé par IBM, et que j’ai obtenu ma première adresse e-mail internationale (VIRCHAUX@CLSEPF51.BITNET). De ce fait, je me suis retrouvé dans l’équipe réseau qui gérait cela à cette époque. Je participerai à toute l’évolution avec le nouveau partenaire SWITCH gérant le ré-seau académique suisse et mettrai en route le premier système d’accès distant CARPE, avec des modems et TELEPAC (X.25 pour les initiés), en 1990.

Finalement, je me suis attelé aux différentes versions du site Web network.epfl.ch, vitrine d’interface entre l’équipe réseau et les utili-sateurs des services du groupe. À côté, j’ai géré les évolutions des accès distants jusqu’au VPN actuel.» Avec Jacques, c’est donc une partie de l’Histoire du DIT (alias SIC,alias SIG) qui nous quitte. Tous les membres du groupe DIT-TI lui souhaitent une longue et heureuse retraite.

Yves.Despond@epfl.ch, Domaine IT

.. /.. Suite page 9

NdR: Jacques et le FI: une longue collabora-tion

Le premier article que Jacques a signé dans le Flash informa-tique date de juin 1986, c’était l’annonce de la création d’un groupe d’utilisateurs le TIC, le Team IBM-PC & Compatibles, dont la première séance était suivie d’une présentation du fameux IBM- PC/RT !Depuis l’informatique a un peu changé … et Jacques s’est tout naturellement intéressé à bien d’autres sujets sur lesquels il a écrit dans le journal, le courrier électronique (c’est comme cela qu’on appelait le mail au début), et bien sûr le réseau, mais toujours avec l’intention de faire comprendre le jargon tech-nique aux non-experts.N’oublions pas non plus qu’il a fait partie du comité de rédac-tion du FI depuis plus de 20 ans, c’est donc un compagnon de longue date qui quitte le journal, qu’il continuera peut-être à lire s’il en trouve le temps.

320 DÉCEMBRE 2011 - N° 10

If you are looking for powerful free/open source software that is easy to learn for geodata visualiza-tion and analysis, this article will interest you.

Si vous êtes à la recherche d’un logiciel libre puis-sant et aisé à prendre en main pour visualiser et analyser des géodonnées, alors cet article va vous intéresser.

Fiche descriptive

Quantum GIS

Domaine Système d’information géographique (SIG)

Licence GPL V2 or later

langue multilingue

version 1.7.2

Autres alternatives libres GRASS & GIS gvSIG OpenJump SAGA GIS

Alternatives non libres ESRI ArcGIS Bentley GIS FME Manifold GIS System MapInfo Smallworld

Sites Web Projet et téléchargement: www.qgis.org

Plates-formes

Introduction aux données spatiales

Les Systèmes d’Information Géographiques (SIG & ou GIS & en anglais) sont des outils qui permettent de travailler avec des don-nées géo-référencées (géodonnées). Les géodonnées regroupent l’ensemble des bases de données auxquelles sont reliées des coordonnées spatiales (géographiques). Depuis les années 2000, de nombreux SIG disponibles sur le Web sont devenus des outils indispensables. Google Maps s’est particulièrement démocratisé dans les domaines de la recherche de lieux, d’itinéraires, d’horaires de transports publics et sur la communication de ces informations

Quantum GISNicolas.Lachance-Bernard@epfl.ch & Timothee.Produit@epfl.ch, assistants-doctorants au Laboratoire de systèmes d’information géographique EPFL-ENAC

entre utilisateurs. Cependant, les utilisateurs de données géogra-phiques qui ont besoin de fonctions de cartographie ou de traite-ments plus avancés utilisent des logiciels spécialisés. Les SIG per-mettent d’abord de visualiser les géodonnées. Un usager un peu plus aguerri pourra aussi les éditer et les analyser (on parle alors d’analyse spatiale). Finalement, il pourra encore les cartographier (par exemple par des cartes thématiques). Cet article se divise en deux parties. D’abord, les types de géodon-nées ainsi que les bases nécessaires à une bonne utilisation d’un SIG seront introduits. Plus loin, nous mettrons à disposition dif-férentes données afin d’illustrer les fonctions d’un SIG et l’article prendra la forme d’un tutoriel d’introduction au logiciel QGIS &.

Les principaux types de géodonnéesDeux types de géodonnées sont généralement utilisés. Le premier type est composé des données matricielles ou images (raster data en anglais), le second type est formé de données vectorielles ou vecteurs (vector en anglais). Ces deux types sont habituellement couplés à des métadonnées (metadata en anglais). Ces dernières contiennent les informations explicatives et descriptives de la géodonnée (auteur, licence d’usage, système de coordonnées, système de référence, description des classes présentes, …). Ces géodonnées sont organisées en couches superposables que l’uti-lisateur choisit d’afficher ou non à l’écran lors de leur usage dans un SIG (fig. 1.)

fig. 1 – Quantum GIS affichant des géodonnées vectorielles (routes - Swisstopo Vecteur 25) et matricielles (orthophoto - SwissImage 50cm).

Les données matricielles sauvegardent dans une matrice com-posée de pixels une information liée au territoire. Les données matricielles les plus connues sont les images satellites et les orthophotos générées sur la base d’images aériennes (avion, hélicoptère, UAV &). De plus, il faut citer les MNT &, qui utilisent le format matriciel pour enregistrer l’altitude du territoire sur une grille régulière de résolution prédéfinie (par exemple l’altitude moyenne de chacune des cellules de 25m x 25m).

Logiciel libre

4 flash informatique44 20 DÉCEMBRE 2011 - N° 10flash informatique

Les données vectorielles sauvegardent dans une base de données des objets géographiques. Chacun de ces objets représente un vecteur pour lequel plusieurs données attributaires sont associées. Une donnée attributaire enregistre une information sur l’objet: le nom d’une rue, le nom d’un bâtiment, le type de surface, ou encore la longueur ou l’aire d’un objet. Il existe trois types de pri-mitives géométriques dans un SIG:Le point: permet de représenter des objets ponctuels tels qu’un

arbre, un point d’intérêt, ou encore le centre de gravité (point central) d’un d’objet modélisé par un polygone;

La ligne: permet de représenter des objets linéaires tels qu’une route, une rivière ou encore une voie ferrée;

Le polygone: est utilisé pour des éléments surfaciques tels qu’un bâtiment, une forêt, un terrain.

Les systèmes de projection et de référenceIl reste une étape primordiale lors de l’usage de géodonnées. Cette étape est la configuration du système de projection et du système de référence géodésique (souvent appelé datum) de chacune des couches. Cette étape permet aux couches de diverses sources de se superposer proprement.À ce stade, il est suffisant de comprendre qu’il existe des coordon-nées géodésiques (ou encore géographiques), par exemple Lati-tude et Longitude, permettant de décrire la localisation d’un point sur la surface de la Terre. C’est typiquement dans un tel système de référence géodésique global (WGS84 &) que sont livrées les données utilisées avec les appareils GPS &. Cependant, en Suisse, on utilise principalement le système de coordonnées cartogra-phiques SwissGrid, défini pour un plan et associé à un système de référence géodésique local (CH1903+ &). Ce système permet, par exemple, d’afficher et de mesurer les coordonnées x et y d’un lieu en mètres. La mauvaise configuration des systèmes de coor-données est une source récurrente de problèmes dans l’usage des SIG et des géodonnées.

Les géodonnées à l’EPFLDepuis janvier 2011, l’ensemble des étudiants et des collabora-teurs de l’EPFL ont accès pour l’enseignement et la recherche à la majeure partie des données de l’Office fédéral de la topo-graphie Swisstopo 1. Un premier serveur est disponible pour les membres de la faculté ENAC depuis le début des années 2000. Environ 12TB de géodonnées sont actuellement disponibles par le site Web ENACGEODATA 2 qui est accessible à plus de 50 cor-respondants principalement de l’ENAC, mais aussi d’autres facul-tés de l’EPFL. De plus, depuis l’été 2011, une plate-forme proto-type est en évaluation par l’ensemble de ces correspondants. La plate-forme Web GeoVITe 3, initialement développée à l’ETHZ, est actuellement en test pour la consultation, l’extraction et la préparation des géodonnées pour les écoles EPF. Plus de 15TB de géodonnées y sont entreposées et disponibles d’un simple clic de

votre souris (fig. 2). Si votre laboratoire désire avoir plus de renseignements ou avoir accès à ces géodonnées officielles, veuillez contacter le responsable de la distribution des géo-données à l’EPFL, geodata.lasig@epfl.ch du LASIG 4.

fig. 2 – interface GeoVITe pour la sélection des couches de géodonnées (secteur de l’EPFL avec la couche Swisstopo Vecteur 25).

Les géodonnées de type Volunteered Geographic Information - VGISi l’acronyme VGI & ne vous parle probablement pas, vous connaissez certainement le projet OpenStreetMap (OSM &). OSM est un service de cartographie Web libre basé sur la contribution volontaire de particuliers pour la digitalisation de réseaux rou-tiers, d’activités économiques et autres informations spatiales. Ce type de géodonnées libres est en développement intensif depuis les cinq dernières années. D’autres projets mettent à contribu-tion les volontaires du monde entier. Le projet Geo-Wiki 5, par exemple, vise à valider différents modèles de couverture du sol (land covers) pour l’ensemble de la surface terrestre. Les domaines d’application des VGI sont presque illimités. Les VGI démocratisent de plus en plus l’accès à des données justes et pertinentes, tant pour des usages individuels ou commerciaux que ceux liés à des besoins personnels. Les laboratoires TOPO 6 et LASIG explorent de-puis déjà quelques années l’usage de ces jeux de géodonnées afin d’en tester la qualité et l’utilité. Ces travaux ont démontré que les géodonnées de type VGI permettent de produire des analyses prometteuses et innovatrices de l’espace urbain 7.

Logiciels de systèmes d’information géo-graphique

Jusqu’ici, l’enseignement des SIG aux futurs ingénieurs civils, ingénieurs en environnement et architectes était réalisé princi-palement sur des logiciels non libres. Pour une liste des logiciels disponibles pour les étudiants, veuillez consulter le site ENAC-SOFT GIS Software 8. Dans les années à venir, un changement de cap sera effectué pour utiliser principalement des logiciels libres. Le choix se porte inévitablement sur le projet QGIS. QGIS

Quantum GIS

1 www.swisstopo.admin.ch 2 enacgeodata.epfl.ch3 https://geodata.ethz.ch/geovite4epfl/4 lasig.epfl.ch5 www.geo-wiki.org6 topo.epfl.ch7 www.springerlink.com/content/b711024173111250/ & www.slideshare.net/nlachance/urban-monitoring-using-netkde-and-vgi-96732908 enacsoft.epfl.ch/lasig/

5520 DÉCEMBRE 2011 - N° 10

est le logiciel libre le plus avancé et le plus actif, tant par ses déve-loppements continus que par la dimension de sa communauté internationale active. Il peut rivaliser avec la majorité des logiciels non libres pour les usagers novices à intermédiaires. D’ailleurs plu-sieurs communes de l’arc lémanique utilisent ou mettent en place ce logiciel pour remplacer les variantes onéreuses.

Installation de Quantum GIS

Sous WindowsDepuis la page qgis.org/wiki/DownloadFr, vous pouvez choisir entre une installation basée installateur (type Setup.exe) ou ins-tallateur réseau. Vous devez absolument exécuter le fichier ins-tallateur (QGIS-OSGeo4W-1.7.1-c58071d-Setup.exe) en mode administrateur (fig. 3).

fig. 3 – exécution de l’installateur QGIS en mode administrateur

Si votre ordinateur possède un espace disque dur restreint, vous avez l’option de ne pas installer les fichiers des géodonnées pour les tutoriels, qui occuperaient 360.7MB d’espace disque supplé-mentaire (fig. 4).

fig. 4 – installation de QGIS avec (782.3MB) ou sans (421.6MB) les géodonnées des tutoriels

Sous LinuxQGIS est packagé pour la plupart des distributions Linux. Sous Ubuntu par exemple, il suffit de faire pour l’installer:

sudo apt-get update sudo apt-get install qgis

Sous MacOS XL’installation est un peu plus complexe, car elle nécessite l’instal-lation préalable de dépendances. Voyez la page de téléchargement de QGIS: www.qgis.org/wiki/Download#MacOS_X.

Prise en main

Cette seconde partie de l’article présente un échantillon des géo-données disponibles pour les environs de l’École polytechnique fédérale de Lausanne (EPFL). Organisé sous la forme d’un tuto-riel, l’article présente un projet QGIS pré-paramétré. Les données ainsi que le projet QGIS sont disponibles pour téléchargement aux membres de l’EPFL (collaborateurs et étudiants) avec ce lien: lasig2.epfl.ch/qgis/qgis_data.zip.

Présentation de la fenêtre QGISTrois composants principaux sont visibles à l’ouverture de QGIS. Vous pouvez ouvrir le fichier epfl_4_flash.qgs. Tout d’abord, le composant principal est la fenêtre de visualisation des géodon-nées. Cette dernière permet d’explorer les différentes couches de géodonnées à l’aide, entre autres, des zooms. Aussi, il est possible de sélectionner un ou des objet(s) d’une couche afin d’interroger la base de données d’attributs. Ensuite le gestionnaire de couches, situé habituellement à gauche de la fenêtre de visualisation per-met de choisir l’ordre de superposition des couches (fig. 5).

fig. 5 – gestion des couches avec QGIS

Par un clic droit de la souris sur le nom d’une couche suivi de Pro-perties, l’usager accède aux paramètres d’affichage de la couche tels que palettes de couleurs et options de transparence. Enfin, différentes barres d’outils dynamiques permettent d’accéder aux fonctions SIG de base de QGIS (fig. 6).

fig. 6 – barre d’outils – de haut en bas: navigation, importation de données, inter-rogation et sélection, plugins

Habituellement, ce composant est affiché sous les menus tex-tuels principaux de QGIS. Les fonctionnalités de cette composante s’adaptent/s’active selon le type de géodonnées de la couche sélectionnée.

Quantum GIS

6 flash informatique66 20 DÉCEMBRE 2011 - N° 10flash informatique

Importation de géodonnées vectoriellesIl existe de nombreux formats de géodonnées vectorielles et QGIS permet de lire la plupart d’entre eux. Le format le plus répandu est le format propriétaire ESRI shapefiles possédant une extension de fichier .shp. Contrairement à un document de bureautique, une couche de géodonnées comporte plusieurs fichiers ayant ou non des noms similaires, mais des extensions différentes. Dans le cas d’une géodonnées sous le format ESRI shapefiles, il y a plu-sieurs fichiers (.shp qui contient la géométrie, .dbf qui contient les attributs et est éditable avec un tableur, .prj contient le sys-tème de projection, .shx, …). La perte de l’un de ces fichiers liés occasionne habituellement la perte de l’ensemble des géodon-nées. Dans l’exemple qui suit, un fichier de ce type est utilisé pour importer une couche de bâtiment dans QGIS. Il faut tout d’abord importer la couche de géodonnées bâtiments (./vectors/buildings.shp). Pour ce faire, il faut cliquer sur le bou-ton Add Vector Layer . Les bâtiments apparaissent dans la fenêtre de visualisation du projet. Afin de visualiser ses attributs, l’usager peut sélectionner un bâtiment, représenté par un poly-gone, grâce au bouton Identify Features . Si l’usager sou-haite accéder aux attributs de l’ensemble des objets d’une couche, il faut faire un clic droit sur la couche dans la fenêtre de visuali-sation, puis choisir Open Attribute Table. Depuis cette nouvelle fenêtre, il est possible de modifier la structure de la table d’attri-buts. On peut ainsi ajouter une nouvelle colonne d’attributs, cal-culer automatiquement des valeurs, ou encore éditer les valeurs des attributs à la main. Pour modifier la structure ou le contenu de la table d’attributs, l’usager doit passer en mode édition en cliquant le bouton Toggle Editing . Il est non seulement possible pour l’usager en mode édition de travailler sur la table des attributs, mais également de modifier la géométrie des objets dans la fenêtre de visualisation.Bien souvent, d’autant plus avec l’utilisation intensive des GPS ou téléphones intelligents (smartphones), l’usager désire importer des géodonnées au format texte contenant une coordonnée géo-graphique et des attributs. Il faut tout d’abord activer l’outil Add Delimited Text Layer en cliquant sur son icône par le menu principal Plugins / Manage plugins… / Add Delimited Text Layer . L’outil apparaît alors au bas de l’interface QGIS dans le composant plugins de l’interface. Un fichier (./vector/villas.csv) sous le format comma-separated-values (.csv) est à votre dispo-sition pour tester cette fonctionnalité. Lors de son ouverture, il faut simplement spécifier la structure du fichier et le tour est joué. Enfin, le plugin Spatial Query , également activé par le menu principal Plugins / Manage Plugins… / Spatial Query Plugin, permet de réaliser des requêtes spatiales simples entre couches. Par exemple, cet outil permet de sélectionner les routes croisant des bâtiments.

Visualisation d’un modèle numérique de terrainUne orthophoto est déjà présente dans le projet QGIS afin d’illus-trer une donnée matricielle. En plus de cette première couche, un exemple d’importation d’un modèle numérique de terrain (MNT) d’une résolution de 25m (./raster/124313.asc) est réalisé. Pour ce faire, il faut ouvrir le MNT en utilisant le bouton Add Raster Layer en choisissant le format de géodonnées [GDAL]Arc/Info ASCII Grid. L’information [GDAL &] indique que QGIS appelle

la librairie GDAL pour la transformation de données raster entre les divers formats existants.Dans la fenêtre de visualisation de QGIS, l’image doit apparaître en ton de gris (fig. 7).

fig. 7 – modèle numérique de terrain avec style appliqué

Cette image contient comme information l’altitude de chaque pixel, on peut y accéder avec le bouton Identify Features . Pour visualiser correctement ces informations (passer de l’image grise à celle colorée) il est nécessaire de configurer un jeu de cou-leurs adéquat pour l’affichage par un clic droit sur le nom de la couche, dans le gestionnaire des couches, et cliquer sur Properties suivi de l’onglet Style. Dans l’onglet Style, choisir dans le menu déroulant de Color Map un affichage Pseudocolor et cliquer sur le bouton Apply. Il est possible d’augmenter le contraste avec la méthode de Contrast enhancement en sélectionnant Stretch to MinMax (fig. 8).

fig. 8 – fenêtre de configuration des propriétés d’une couche: Onglet Style

Les outils de traitement de géodonnées matricielles sont relati-vement restreints dans QGIS. Il existe notamment un calculateur raster accessible par le menu Raster / Raster calculator. Cet ou-til permet notamment de soustraire deux MNT afin d’identifier des différences d’altitude entre deux jeux de géodonnées différents. Il existe aussi le plugin Raster based terrain analysis qu’il faut activer via Plugins / Manage Plugins / Raster Terrain Analysis plugin. Cet outil permet de calculer sur un MNT les pentes et leur orientation.

Quantum GIS

7720 DÉCEMBRE 2011 - N° 10

GRASS GIS: Traitements avancés du MNTPour proposer des outils plus puissants d’analyse de géodonnées matricielles, QGIS permet de coupler un autre SIG libre directe-ment dans son interface: GRASS GIS. Par exemple, à l’aide de ce couplage des deux SIG, il est possible de produire un relief ombra-gé dans QGIS à partir d’un MNT (fig. 9).

flg. 9 – modèle numérique de terrain en relief ombragé

Pour calculer cet ombrage, il faut tout d’abord créer un nouveau jeu de cartes (mapset) avec l’outil GRASS New Mapset . En cli-quant ce bouton, une fenêtre requiert la sélection d’un répertoire (EPFL par exemple) pour enregistrer la nouvelle base de données ainsi qu’un nom de lieu. Toujours dans cette même fenêtre, il faut choisir le système de projection SwissGrid avec pour Coordinate Reference System CH1903/LV03, Authority ID EPSG: 21781 et ID 1919. Il est possible pour cette configuration de rechercher diffé-rents systèmes de projection à l’aide d’un outil situé dans la même fenêtre. Ensuite, la fenêtre demande de configurer une Bounding Box (dans le cas de ce tutoriel, il est possible de confirmer celle qui apparaît automatiquement dans les paramètres) et de nommer le jeu de cartes qui sera produit (EPFL par exemple).Une fois le jeu de cartes créé, l’ensemble des outils GRASS intégrés à QGIS deviennent actifs et utilisables. Par exemple, à l’aide du bouton GRASS Tools il est possible de sélectionner sous l’on-glet Modules Tree l’outil Import into GRASS / Import raster into GRASS from QGIS view / Import loaded raster (fig. 10).

fig. 10 – utilisation du Module Tree pour l’importation d’une géodonnées matri-cielles avec le module GRASS

Il suffit alors de spécifier une des couches matricielles actives (la case d’affichage dans le gestionnaire de couche doit être cochée) et un nom de couche en sortie (EPFL_Altitude) et de cliquer sur le bouton Run, suivi d’un clic sur le bouton View Output pour rendre disponible le résultat dans le gestionnaire de couches. Enfin, il est possible avec cette nouvelle couche de produire à par-tir du MNT un relief ombragé. Toujours dans à l’aide du bouton GRASS Tools, on utilise sous l’onglet Modules Tree l’outil Raster / Spatial analysis / Terrain analysis / Create shaded relief (fig. 11).

fig. 11 – utilisation du Module Tree pour la création d’un relief ombragé avec le module GRASS.

Pour ce tutoriel, il est possible d’utiliser les paramètres configurés par défaut pour un résultat adéquat, donc de cliquer une nouvelle fois sur le bouton Run suivi d’un clic sur le bouton View output. On remarque donc que si un outil n’est pas disponible directe-ment dans QGIS, il y a de bonnes chances qu’il soit disponible via GRASS.

Paramétrage des systèmes de projectionsPour tout projet QGIS, il est primordial de bien spécifier le sys-tème de coordonnées du projet et celles des géodonnées lors de leur chargement. Dans le premier cas (un nouveau projet), il faut utiliser le menu Settings / Project Properties suivi de l’onglet Coordinate Reference System (CRS &). Dans le second cas (une nouvelle couche), il faut faire un clic droit sur la couche, puis Set layer CRS. Pour les géodonnées suisses, on sera générale-ment appelé à utiliser CH1903/LV03 (EPFL = 533’020; 152’450) ou WGS84 (EPFL = 46.520825; 6.564825). Il est extrêmement important de préciser ces paramètres, et ce pour que:z la diffusion de vos géodonnées soit documentée;z la superposition de vos géodonnées soit conforme entre les

couches;z les calculs et mesures soient dans les bonnes unités (par

exemple des mètres).Si vous avez à travailler avec des géodonnées extérieures à la Suisse ou historiques, il est utile de se référer au site Web du EPSG &): EPSG Geodetic Parameter Registry 9. L’EPSG, créé en 1985, a mis au point une base de données des systèmes de coor-données actifs et historiques. Un code a été associé à chacun des

Quantum GIS

8 flash informatique88 20 DÉCEMBRE 2011 - N° 10flash informatique

systèmes de coordonnées, code devenu de facto le standard de la nomenclature. Ces codes sont largement utilisés dans les SIG courants, par exemple CH1903/LV03 possède le code EPSG21781 pour code et WGS84 le code EPSG4326. Cependant, au moment de calculer les transformations de coordonnées, QGIS se base sur une librairie appelée PROJ.4 10. En Suisse, Swisstopo documente les systèmes de coordonnées courants.

Connexion à des serveurs de géodonnées externesIl n’est pas toujours nécessaire d’utiliser des géodonnées locales (sur votre ordinateur). En effet, certaines géodonnées sont distri-buées grâce à une connexion avec un serveur par l’intermédiaire des réseaux Internet (public) ou Intranet (privé). Les serveurs Web Map Service (WMS &) distribuent des géodonnées matricielles (images). Les serveurs Web Feature Service (WFS &) distribuent des objets géographiques des géodonnées vectorielles. Pour s’y connecter, il suffit d’utiliser respectivement les boutons Add WMS server et Add WFS server, et de spécifier les paramètres de connexion. Dans le projet QGIS fourni, des connexions vers les WMS de l’Office Fédéral de l’Environnement (OFEV) et de l’Infrastructure

Fédérale de Données Géographiques (IFDG) sont déjà préenregis-trées, les couches disponibles sont décrites sur le site de l’Admi-nistration fédérale.

Références

Pour davantage d’informations sur l’utilisation de QGIS et GRASS, voyez:z Les manuels d’aide de QGIS: www.qgis.org/en/documentation/

manuals.html.z Le forum de questions et réponses Quantum GIS Forum II:

forum.qgis.org.z Les tutoriels QGIS du SIG pour l’Enseignement Agricole: sigea.

educagri.fr/ressources-pedagogiques/utilisation-des-logiciels/tutoriels-de-logiciels-gratuits/tutoriels-qgis.html.

z Le wiki QGIS: www.qgis.org/wiki/Welcome_to_the_QGIS_Wiki.

Article du FI-EPFL 2011 sous licence CC BY-SA 3.0 /

N. Lachance-Bernard & T. Produit

GLOSSAIRE &CH1903+: les deux systèmes de référence

géodésiques CH1903+ et CH1903 sont identiques en ce qui concerne les dimensions de l’ellipsoïde de référence, les orientations des axes de coordon-nées, l’échelle et le système de projec-tion. Pour les définitions et désignations: www.admin.ch/ch/f/rs/510_620_1/a3.html.

CRS (Coordinate Reference System): système de coordonnées permettant de faire correspondre à chaque point d’un espace à N dimensions, un N-uplet de scalaires. fr.wikipedia.org/wiki/Syst%C3%A8me_de_coordonn%C3%A9es.

EPSG: European Petroleum Survey Group. www.epsg.org.

GDAL (Geospatial Data Abstraction Library): bibliothèque d’abstraction des données géo-spatiales.www.gdal.org.

GIS (Geographic Information Systems): voir SIG en français.

GPS (Global Positioning System): système de positionnement mondial. fr.wikipedia.org/wiki/Global_Positioning_System.

GRASS (Geographic Resources Analysis Support System): système de support à l’analyse des ressources géographiques. grass.fbk.eu.

MNT: modèle numérique de terrain.

OSM: projet volontaire de carte OpenStreet-Map. www.openstreetmap.org/; lire aussi FI SP10 flashinformatique.epfl.ch/spip.php?article2106.

QGIS: Quantum GIS, www.qgis.org/.

SIG: systèmes d’information géographique.

UAV (Unmanned Aerial Vehicle): ou en français drone.

VGI (Volunteered Geographic Information): information géographique volontaire.

WFS (Web Feature Service): utilisé aussi pour toutes les autres langues.

WGS84 (World Geodetic System 1984): système géodésique mondial avec la révision de 1984, associé au GPS.

WMS (Web Map Service): utilisé aussi pour toutes les autres langues.

Quantum GIS

9 www.epsg-registry.org10 trac.osgeo.org/proj/ & www.geo.admin.ch/internet/geoportal/fr/home/services/geoservices/display_services/services_wms.html

Dernière nouvelle

routeRANK (www.routerank.com) logiciel de planification de voyage créé par une start-up du PSE (voir flashinformatique.epfl.ch/spip.php?article1980) est dans la liste des douze outils rete-nus pour le concours en faveur d'une mobilité intelligente

Brève

routeRANKde la Commission européenne. Le vote est ouvert au public jusqu'au 13 janvier 2012 (ec.europa.eu/transport/its/multimodal-planners/index_fr.htm) … N'hésitez pas à vous exprimer. n

9920 DÉCEMBRE 2011 - N° 10

../.. suite de la page 2

LE DIT VOUS FORME...

et vous souhaite de Joyeuses Fêtes et une année 2012 riche en formations !Sur notre site Web dit.epfl.ch/formation vous trouverez, semaine après semaine, notre calendrier complet pour le 1er semestre, consultez le régulièrement.Plusieurs cours sont organisés à la demande, faites-nous part de vos désirs et nous ferons notre possible pour vous donner la for-mation correspondant au mieux à vos besoins.Ci-après, voici un aperçu des formations offertes pour bien débu-ter l’année:

Windows 7z 1 -Installation et configuration, semaine 1z 2 -Dépannage et maintenance, semaine 2z 3 -Support des applications et du système d’exploitation,

semaine 5z 4 -Déploiement de Windows 7, semaine 6

LabVIEW ou l’acquisition de donnéesz Vision (in English), semaine 3z Object-Oriented Programming System, semaine 3z Core I, semaines 4 et 8z Core II, semaine 4z Diadem, Basics I, semaine 7z Diadem, advanced, semaine 7

programmationz C++, STL-Standard Template Library (in English), semaine 3z C++, A Comprehensive Hands-On Introduction (in English),

semaine 5z Beginning iPhone and iPad Development (in English),

semaine 6z Python, level II (in English), semaine 6z DIT HPC servers usage (in English), semaine 8z NEW, Développement d’applications Web pour mobile multi

plates-formes, semaine 8

Linuxz Essentials (in English), semaine 7

bureautiquez InDesign CS5, 1-introduction, semaine 2z Excel 2010, 1-introduction, semaine 2z Word 2010, les longs documents, semaine 2z Jahia 6, création de sites Web EPFL, semaine 2z FileMaker Pro 11, semaine 2z Outlook 2010, transition, nouveautés et exercices pratiques

(rapido), semaine 4z Excel 2010, 2-feuilles de calcul, semaine 4.

Ceci n’est qu’un aperçu, tous les détails se trouvent sur notre site.cours.dit@epfl.ch

Le prix de l'AFCA 2011 à une collaboratrice du DIT

L’AFCA (Association Femmes & Carrière dans l’Administration) a, pour la deuxième fois de son histoire, attribué son prix à une femme qui sort des sentiers battus par le choix de sa formation et de son parcours professionnel.Cette année c’est Michela Thiémard qui a été choi-sie pour «être parvenue à se faire une place au sein d’un monde presque exclusivement masculin, celui de l’informatique et des mathématiques». Michela est bien connue des utilisateurs des ressources de calcul du DIT, où elle coordonne la cellule HPC et et administre notam-ment le cluster de GPU et la grille de calcul de l’EPFL. Michela a fait ses études à l’EPFL en mathématiques, elle y a soutenu sa thèse en 2004 et depuis travaille au DIT.

iPhone et Wi-Fi Swisscom

Vous êtes client de Swisscom et propriétaire de l’un de ces appa-reils mis à jour vers iOS5:z iPad, iPad 2z iPhone 3GS, iPhone 4Vous devriez vérifier que, sur le campus, votre appareil ne se connecte pas automatiquement au réseau MOBILE-EAPSIM de Swisscom plutôt qu’à celui de l’EPFL. Cela pourrait avoir un effet néfaste sur votre facture de téléphone mobile.Pour désactiver la connexion automatique, voici la marche à suivre:

1. Cliquez sur l’icône Réglages de votre iPhone.2. Cliquez sur Wi-Fi.3. Activez le Wi-Fi. Les réseaux sans fil disponibles s’affichent.4. Sélectionnez le réseau MOBILE-EAPSIM.5. Désactiver la fonction Connexion auto.

L’équipe DIT-TI

DIT-info

10 flash informatique 20 DÉCEMBRE 2011 - N° 10

Since the Beowulf revolution, High Performance Computing (HPC) has been taken over not only by clusters built from commodity hardware, but also by free software. Starting from the operating system, up to the specific scientific software, supercomput-ers (even the most powerful in the world) sport all kind of free software.

Depuis la révolution Beowulf &, le calcul haute per-formance (High Performance Computing, HPC) a été envahi non seulement par des clusters comportant du matériel courant mais aussi par le logiciel libre. Du système d’exploitation aux applications métier, les supercalculateurs (même les plus puissants au monde) sont un nid à logiciels libres.

La révolution Beowulf

Dans l’été 1994 à la NASA, Thomas Sterling (Professeur en infor-matique) et Donald Becker (développeur de drivers ethernet pour le noyau Linux) construisirent le premier cluster à partir de com-posants librement disponibles sur le marché pour l’informatique domestique, avec une couche logicielle libre. Ils appelèrent leur machine Beowulf. Depuis cette date, tous les clusters construits à partir de matériel grand public et de logiciels libres s’appellent cluster de type Beowulf. En juin 1997, le premier cluster Beowulf pointa son nez dans le classement Top500: un cluster fait maison à UC Berkeley, mais qui n’était pas un vrai cluster Beowulf dans le sens que même fait maison, il se basait sur un OS de type Solaris. Il fallut attendre encore une année pour que Linux apparaisse dans le Top500. On peut remercier Los Alamos. Mais hélas, le matériel n’était pas cou-rant (processeurs alpha). En juin 1999, non seulement on vit appa-raître (en Allemagne) des clusters comme on les connaît de nos jours (processeurs Intel ou compatibles), mais aussi les fabricants de machines spécifiques adopter GNU/Linux comme OS. Pendant quelques années, les clusters de type Beowulf eurent de la peine à s’imposer auprès de la communauté HPC: ils étaient en concurrence avec des machines très chères, dont le matériel était spécialement conçu pour le HPC et avec une couche logi-cielle aussi très spécifique. Les leaders du HPC voyaient d’un très mauvais œil ces nouveaux aspirants supercalculateurs construits à partir de matériel généralement vendu au grand public et instal-lés avec des logiciels librement disponibles sur le net. Malgré cette résistance (que l’on rencontre encore aujourd’hui dans certains cercles), les clusters Beowulf eurent de plus en plus de succès, à tel point que depuis 2004 la moitié des 500 ordina-

teurs les plus puissants au monde étaient des clusters (fig. 1). À l’EPFL, le cluster Beowulf arriva en novembre 2003 avec le projet Pléiades. Le DIT suivit en 2005 avec Mizar.

1994 1996 1998 2000 2002 2004 2006 2008 20100

200

400

year

clus

ters

in T

op 5

00

fig. 1 – clusters Beowulf dans le top500: historique

HPC: qu'est-ce?

On entend cet acronyme bien souvent: HPC pour High Perfor-mance Computing. Mais qu’est-ce que cela signifie? S’agit-il d’un autre buzzword? En partie. Mais on peut définir le HPC comme du supercomputing couplé avec des grandes quantités de données et leur traitement. On parle de supercomputing quand on résout des problèmes de taille importante sur les ordinateurs les plus per-formants au monde. Il existe même une liste des ordinateurs les plus puissants du moment: le Top500. Cette liste est publiée deux fois par an depuis 1993 et est reconnue par l’industrie, le monde académique, les vendeurs et les médias. Quand la machine la plus performante atteint une étape représentée par une performance à un chiffre bien rond, c’est la fête. La performance des machines est mesurée à l’aide d’un benchmark & appelé LINPACK. Le Top500 nous permet d’avoir un historique de ce qui se passe en HPC. Dans la figure 2, nous avons l’historique de la puissance LINPACK de la machine numéro un, la numéro 500 et la somme des puissances de toutes les 500 machines. Nous pouvons remarquer la progression exponentielle qui nous donne envie de tracer des droites et peut-être de transformer cette course à la puissance en une prophétie autoréalisatrice. L’étoile représente l’étape déjà franchie du Peta-FLOPs &. La prochaine étape (ExaFLOPs) est prévue pour 2020. Un laptop aujourd’hui est aussi puissant qu’un supercalculateur dans les années 90. À quand un téléphone mobile de cette puissance?

1995 2000 2005 2010

GigaFLOPs

TeraFLOPs

PetaFLOPs

somme des 5001ère machine500ème machine

Mon laptop

Ma station

fig. 2 – historique de la puissance de calcul des ordinateurs les plus performants au monde

Le logiciel libre dans le HPCVittoria.Rezzonico.@epfl.ch, EPFL - Coordinatrice CSE/HPC

Logiciel libre

111120 DÉCEMBRE 2011 - N° 10

Le logiciel libre dans le HPC

Dans la figure 3, on voit le dernier Top10. Toutes sont des ma-chines basées GNU/Linux, qu’on peut considérer des clusters, avec parfois des GPUs. On remarque l’énorme nombre de cœurs par machine et la consommation électrique qui se rapproche de celle d’une petite ville.

Nom Pays Cores PFLOPs MW MFLOPS/W

1 K computer Japon 705024 10.510 12.66 830

2 Tianhe-1A Chine 186368 2.566 4.04 635 GPUs

3 Jaguar USA 224162 1.579 6.95 253

4 Nebulae Chine 120640 1.271 2.58 493 GPUs

5 TSUBAME 2.0 Japon 73278 1.192 1.4 852 GPUs

6 Cielo USA 142272 1.110 3.98 279

7 Pleiades USA 111104 1.088 4.1 265

8 Hopper USA 153408 1.054 2.91 362

9 Tera-100 France 138368 1.050 4.59 229

10 Roadrunner USA 122400 1.042 2.35 444 Cell

fig. 3 – les dix ordinateurs les plus puissants au monde, état novembre 2011

On voit donc deux problèmes pour le futur: l’énorme consomma-tion électrique qui va à l’encontre de la crise énergétique prévue pour les années à venir, et la quantité de cœurs, qui fait que les pannes sur une partie de la machine sont nombreuses et que le temps entre ces pannes suffit à peine à faire tourner un bench-mark.Si un CPU tombe en panne en moyenne une fois en 40 ans, en un jour il a la probabilité p=1/14600 de défaillir. La probabilité qu’au-cun CPU dans une machine qui en compte 100’000 ne tombe en panne un jour donné est de 0.1%. On est donc assez sûr que notre machine va avoir une panne dans la journée. Ceci est bien sûr une vision simplifiée, mais qui nous donne une bonne idée de la réalité.Mais il faut savoir que ces machines sont au service de la science, et que ce n’est qu’un outil de recherche parmi d’autres. Chaque année des prix sont décernés à des chercheurs qui arrivent à tirer parti des machines les plus performantes pour résoudre des pro-blèmes qui, auparavant, n’étaient pas abordables.

Le logiciel libre s'empare du HPC

Les machines dédiées au HPC aujourd’hui pullulent de logiciels libres. On peut dire que le supercalculateur moyen est: un cluster z basé sur GNU/Linux avec z une suite de compilateurs z des bibliothèques de parallélisation z des outils de mesure de performance z des outils d’ordonnancement de tâches (schedulers) z des systèmes de déploiement z des outils de monitoring z des systèmes de fichiers parallèles … tous libres! Dans la suite de cet article, je vais brièvement survoler quelques logiciels qu’on peut trouver sur nos clusters.

GNU/Linux dans le HPC

Aujourd’hui, lorsque l’on parle de systèmes HPC, on pense automatiquement à GNU/Linux. Mais cela n’a pas toujours été le cas. Au début, les serveurs de calcul étaient des machines spécifiquement conçues pour la performance, et le système d’exploitation était livré avec la machine: pas question d’avoir un OS générique sur une machine aussi spécialisée! Jusqu’aux années 80, les codes n’étaient pas portables entre machines différentes: la compatibilité était sacrifiée au profit des performances (CPU et accès mémoire). Les systèmes d’exploita-tion étaient donc faits sur mesure pour les machines, ainsi que les compilateurs et les bibliothèques de parallélisation. Avec l’arrivée du cluster Beowulf, GNU/Linux s’est imposé dans le paysage HPC, à tel point que même les grands acteurs comme Cray et IBM l’ont adopté, parfois partiellement (les BlueGene sont notamment des machines à OS mixte, une partie Linux et une partie spécifique). Dans la figure 4, nous voyons l’évolution des systèmes d’exploita-tion dans les machines du Top500. Linux, qui dans le Top500 ne concerne pas que les clusters, est bien établi dans le HPC.

1994 1996 1998 2000 2002 2004 2006 2008 2010

200

400

mac

hine

s

unixlinuxmixedother

fig. 4 – répartition des systèmes d’exploitation dans les machines du Top500.: historique

Comment installer un cluster Beowulf

Supposons pour simplifier que votre cluster dispose d’un mas-ter et de N nœuds de calcul (fig. 5). Le nœud master (ou maître) est le cerveau du cluster, les nœuds de calcul n’ont pas d’état et peuvent être considérés comme des consommables. Ils n’ont aucune donnée précieuse. En pratique, lors de l’installation, on passe beaucoup de temps sur le master pour en configurer les services, et ensuite on démarre les nœuds, qui s’installent auto-matiquement en suivant les directives du nœud maître.

Nœud NœudNœudNœud Nœud

Switch

Master

réseau d’entreprise

fig. 5 – structure d’un cluster

12 flash informatique1212 20 DÉCEMBRE 2011 - N° 10flash informatique

Le logiciel libre dans le HPC

L’installation du nœud maître n’est pas évidente, car il faut connaître et maîtriser tous les services nécessaires au déploie-ment et à l’administration d’un cluster. Pour créer un serveur d’installation, il faut configurer un serveur dhcp et un tftp, en plus de nfs ou http ou ftp, en fonction de la méthode pour distribuer les paquetages aux nœuds de calcul. Pour ce qui est du monitoring et reporting, des compétences en serveurs web (pour afficher les données), snmp et ssh sont sou-haitables. Ensuite, il faut configurer un ordonnanceur (scheduler). Le nœud maître fait office de firewall et passerelle, une connais-sance de iptables est donc nécessaire. Les utilisateurs doivent être authentifiés sur le nœud maître. Il faudra un système d’authentification comme nis ou ldap. Enfin, lorsqu’on exporte les données utilisateur sur les nœuds, il faut installer (au minimum) un serveur nfs.

Systèmes de déploiement

Les distributions GNU/Linux disposent déjà de leur propre système de déploiement par directives: KickStart pour RedHat et ses déri-vées, FAI pour Debian et Ubuntu, AutoYaST pour SuSE. Chaque système de déploiement est tout à fait utilisable pour installer les nœuds d’un cluster. Pour les administrateurs système qui n’ai-ment pas les installations par directives, on a aussi une panoplie d’outils libres pour installer les nœuds par image. Parmi ces outils, je citerais partimage et systemImager. Les administrateurs les plus avertis se contentent parfois d’un dd à travers netcat. Pour maintenir les nœuds à jour et synchronisés, des outils tels que cfengine et puppet sont disponibles, ainsi que des shells distri-bués comme dsh et pdsh, le dernier étant accompagné par dhs-bak, qui permet d’afficher la sortie de pdsh d’une façon resumée.

Monitoring

Un outil très diffusé dans le monde HPC est Ganglia, qui nous permet d’avoir en un coup d’œil une bonne vue d’ensemble de l’utilisation du cluster (CPU, mémoire, réseau, disques) ainsi que son historique. Ganglia dispose d’une interface web (PHP) et est basé sur XML et RRDtools pour stocker les données. Quand on a beaucoup de nœuds de calcul et des services critiques qui tournent sur le nœud maître, il est nécessaire d’être avertis quand un nœud est en panne, quand les services du master ne sont plus atteignables, mais aussi dans le cas où un utilisateur lance des programmes sur le master ou quand il y a trop d’uti-lisateurs dans la file d’attente. Pour cela, Nagios nous rend un immense service.

Schedulers

Lorsque l’on travaille à plusieurs sur une machine de calcul, il faut la partager de façon transparente. Pour cela, lorsque l’on souhaite lancer un calcul, on passe par un système de files d’attente qui s’occupe de maximiser l’utilisation de la machine moyennant les contraintes dictées par la politique d’utilisation du cluster. L’utili-sateur n’a alors qu’à écrire un script qui s’occupera du lancement de son application et de l’allocation des ressources moyennant la commande qsub mon_script ou encore sbatch mon_script

en fonction du type d’ordonnanceur utilisé. Dans ce script, l’uti-lisateur spécifie entre autres les ressources nécessaires (proces-seurs, mémoire, temps d’exécution, voir figures 6 et 7). Nombre de gestionnaires de ressources et schedulers sont des logiciels libres. Parmi ceux-ci, je citerais Torque et Maui, Son of Grid Engine et Slurm.

#PBS -l nodes=2:ppn=8#PBS -N hellotorque #PBS -l walltime=00:10:00 #!/bin/bash

cd $PBS_O_WORKDIR mpirun -np 16 ./hello_mpi

fig. 6 – exemple de script pour lancer un job MPI avec Torque

#!/bin/sh #SBATCH -J helloslurm #SBATCH -n 8#SBATCH -N 2#SBATCH -t 00:10:00

mpirun -np 16 ./hello_mpi

fig. 7 – exemple de script pour lancer un job MPI avec SLURM

Tout cela n'est pas simple

Pour se simplifier la vie et sauter cette longue étape de configuration du master, on peut prendre des raccourcis et faire appel à des outils de déploiement. Parmi les plus connus, je cite-rais Rocks Cluster Distribution et xCAT. On trouve de plus en plus d’outils de déploiement dans les distributions GNU/Linux, je peux citer Orchestra d’Ubuntu.

Systèmes de fichiers parallèles

Lorsque plusieurs machines accèdent à des fichiers sur un ser-veur de façon asynchrone, NFS est le système de fichiers réseau préféré du Linuxien. Mais si des centaines de machines y accè-dent en même temps, les performances chutent et les clients se bloquent. Pour éviter cela, il faut avoir des systèmes de fichiers réseau conçus pour ce type de charge. Bien sûr, tout cluster assez grand nécessite un serveur avec un système de fichiers à accès parallèle (parallel filesystem). Un cluster est souvent utilisé pour des applications qui tournent sur un seul nœud, ou bien dont chaque processus écrit un fichier séparé. Dans ce cas, ils nous faut juste une alternative plus confor-table au disque local au nœud. Le système de fichiers parallèle Glusterfs satisfait alors nos exigences. Lorsqu’on exécute un calcul en parallèle, il se peut par contre que tous les processus liés au calcul écrivent dans le même fichier. Alors il faut non seulement un filesystem parallèle, mais en plus il faut qu’il supporte le striping des fichiers. Il faudra alors choi-sir entre PVFS2 et Lustre. PVFS2 est plus simple à installer et configurer et on peut vite avoir un système de fichiers qui ré-pond à nos attentes, mais il n’est pas compatible POSIX et il faut alors compiler un module noyau sur les clients ou bien passer par des commandes telles que pvfs-cd pour avoir accès aux fichiers. Lustre est plus complet, mais son avenir est encore flou et il n’est pas facile d’installation.

131320 DÉCEMBRE 2011 - N° 10

Un système de fichiers parallèle répond à une demande complexe, auquel le monde du libre a su répondre avec plusieurs solutions.

Compilateurs

Tout développeur connaît GCC, la GNU Compiler Collection. Le projet fut démarré par Richard M. Stallmann en 1985, et au début, il s’agissait uniquement d’un compilateur C (GNU C Compiler). Depuis lors, plusieurs compilateurs se sont rajoutés. Ceux qui inté-ressent la communauté HPC sont surtout Fortran et C++.

Parallélisation

Sous GNU/Linux, on peut paralléliser du code avec plusieurs outils. Si l’on reste sur le même nœud de calcul et qu’on se contente donc de la parallélisation multi-core, GCC nous satisfait entière-ment: non seulement il nous permet de faire du POSIX Threads, mais aussi du OpenMP. Si l’on souhaite faire de la programmation parallèle distribuée, le standard aujourd’hui est MPI, qui, malgré les mauvaises lan-gues qui annoncent sa mort depuis des années, va encore être le standard de facto pour la parallélisation sur les clusters pendant quelque temps.

include <stdio.h>int main() printf("Hello, world!\n"); return 0;

fig. 8 – Hello, world! séquentiel

include <stdio.h>#include <omp.h>int main() printf("Master thread says: Hello, world!\n");#pragma omp parallel printf("Hello from thread %d of %d\n", omp_get_thread_num(), omp_get_num_threads()); printf("Master thread says: Hello, world!\n"); return 0;

fig. 9 – Hello, world! parallélisé avec OpenMP

#include <stdio.h>#include <mpi.h>int main (int argc, char *argv[]) int rank, size; MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &rank); MPI_Comm_size (MPI_COMM_WORLD, &size); printf( "Hello from process %d of %d\n", rank, size ); MPI_Finalize(); return 0;

fig. 10 – Hello, world! parallélisé avec MPI

Mesure de performance

Afin de produire des codes rapides, il est nécessaire de mesurer leurs performances dans l’objectif de les améliorer. Quand on connaît bien son algorithme, on peut en prédire le temps d’exé-cution et l’utilisation mémoire, et si les ressources utilisées par l’implémentation ne correspondent pas, il faut trouver où est le problème dans le code. Ou bien, quand on souhaite paralléliser des parties de code, on aimerait savoir dans quelles fonctions on passe le plus de temps. L’utilitaire gprof est, comme son nom le laisse comprendre, un outil de profiling. Après avoir compilé le code avec les options adéquates, on lance une fois le code à blanc et ensuite on le passe à travers gprof. Cette dernière action va générer un fichier texte lisible par l’être humain, mais pour les mordus du GUI, kprof est capable de visualiser. Un des démons du programmeur est le memory leak. Pour le détecter, le programme valgrind est l’idéal. Ce programme a tant de fonctionnalités que je vous renvoie aux réfé-rences pour tout explorer. Un autre outil d’analyse des codes est les performance counters. Intégrés au noyau Linux, ils permettent de lire des valeurs de re-gistres spéciaux comme le nombre d’instructions CPU exécutées, les cache misses.

Benchmarks

Maintenant que notre cluster est opérationnel, il s’agit de le vali-der, et quoi de mieux que des benchmarks couramment utilisés dans le monde du HPC. Les plus connus (à tort ou raison) sont le HPL (High Performance LINPACK), qui est utilisé pour rédiger la liste Top500, et le STREAM. Les deux sont disponibles librement, et les développeurs sont même poussés à les modifier pour les adapter à des nouvelles architectures. Plusieurs applications scientifiques sont publiées sous licence libre, je peux citer z QuantumESPRESSO z CP2K z Palabos z Gadget z LAMMPS z NAMD Les utilisateurs sont aussi incités à faire tourner des cas tests sur leurs machines afin de les comparer. Ces applications se transfor-ment donc en benchmarks.

Logiciels de visualisation

Des gros calculs engendrent de lourdes données, qu’il faut traiter et afficher de façon compréhensible, par exemple avec une image 2D, 3D ou même un film. Plusieurs logiciels spécialisés en visua-lisation scientifique existent. Deux exemples sont Paraview qui, comme son nom le suggère, est capable de faire de la visualisation

Le logiciel libre dans le HPC

fig. 11 - logo de Valgrind

14 flash informatique1414 20 DÉCEMBRE 2011 - N° 10flash informatique

Vers une informatique pédagogique libre au DIP genevois Marco.Gregori@edu.ge.ch, rédacteur multimédias au Département de l’instruction publique genevois

By 2015, most of the Geneva’s public school com-puters will run exclusively free and open source software, based on Open standards.

En 2015, la majorité des ordinateurs pédagogiques du Département de l’instruction publique, de la culture et du sport de Genève pourraient fonctionner exclusivement avec des standards ouverts et logiciels libres.

Il en va des logiciels libres comme de la paix dans le monde. Le consensus théorique en leur faveur est large. Pourtant, une fois le principe admis, la réalité s’avère vite complexe. Certes, chacun peut, à titre individuel, assez aisément faire le choix de passer d’un système d’exploitation informatique propriétaire à un système basé sur les standards ouverts et logiciels libres (SOLL). Mais on ne change pas l’informatique scolaire d’une institution publique, composée de milliers de postes informatiques, en mettant simple-ment en avant un idéal. Reste qu’à Genève, dès 2015, la majorité des ordinateurs pédagogiques (et non administratifs) du Départe-ment de l’instruction publique, de la culture et du sport (DIP) aura migré vers des solutions libres et ouvertes. À ce titre, la Direction des systèmes d’information et service écoles-médias (DSI-SEM), notamment en charge de l’informatique pédagogique dans les écoles, a élaboré un plan de déploiement dont la deuxième version est consultable en ligne et ouverte au débat.D’emblée, il convient d’éviter tout malentendu: l’objectif n’est pas l’installation de standards ouverts et logiciels libres en tant que tels, mais bien l’amélioration de la qualité et la pérennité des outils informatiques mis à la disposition de l’enseignement et de l’apprentissage. Corollaire, lorsqu’il est avéré qu’un logiciel propriétaire n’a pas son équivalent libre, il sera maintenu. Cette remarque vaut particulièrement pour les écoles professionnelles.

Sept établissements pilotes au primaire

Depuis plusieurs années, la DSI-SEM chapeaute et évalue des ex-périences réalisées avec des logiciels libres. Les avantages que l’on peut en tirer sont évidents: pérennité des documents, adaptation des outils facilitée en fonction des besoins, possibilité de fournir aux élèves les applications dont ils bénéficient à l’école pour les utiliser à leur domicile, etc. Sans compter qu’il existe une identité de valeurs entre le monde du libre et une communauté éducative publique (lire l’encart). Ainsi, une transition vers les SOLL implique des actions non seulement sur les postes de travail, mais égale-ment sur l’environnement collaboratif et les ressources pédago-giques numériques.

Logiciel libre > Tribune libre

en parallèle sur plusieurs nœuds de calcul, et VisIt, qui est aussi capable de faire une partie du post-processing en parallèle en plus de la visualisation in situ.

Conclusion

Le HPC ne peut plus se passer du logiciel libre: du système d’ex-ploitation jusqu’aux applications scientifiques. Aujourd’hui, on peut presque assembler un supercalculateur à partir de pièces disponibles dans les magasins d’informatique, en utilisant des logiciels disponibles librement sur l’Internet. On peut même transformer une salle de PC en un cluster de calcul per-formant. Nous ne pouvons que nous réjouir d’une telle évolution vu les enjeux du HPC pour la recherche scientifique.

Références

z Top500: http://www.top500.org J’espère que certains outils décrits dans cet article seront le sujet d’articles plus approfondis dans le Flash informatique. Certains l’ont déjà été, avant même la naissance de la rubrique Logiciel Libre: z Aperçu de quelques méthodes d’installation: flashinformatique.

epfl.ch/spip.php?article1397 z AutoYasT: flashinformatique.epfl.ch/spip.php?article2092 z Valgring: valgrind.org.z VisIt: flashinformatique.epfl.ch/spip.php?article2238.

Article du FI-EPFL 2011 sous licence CC BY-SA 3.0 / V. Rezzonico

Le logiciel libre dans le HPC

GLOSSAIRE &Benchmark: point de référence servant à effectuer une mesure.

Dans notre cas, un benchmark nous permet de mesurer les performances d'un système pour le comparer à d'autres.

Beowulf: le premier cluster de calcul a été nommé d’après le héros d'un poème épique anglo-saxon, qui avait dans le poing la force de trente hommes. fr.wikisource.org/wiki/Beowulf/Bot-kine.

FLOPs (floating-point operations per second): nombre d’opé-rations à virgule flottante par seconde; c’est une unité de mesure pour évaluer la vitesse des calculateurs.

MégaFLOPS = 106 FLOPS GigaFLOPS = 109 FLOPS TéraFLOPS = 1012 FLOPS PétaFLOPS = 1015 FLOPS ExaFLOPS = 1018 FLOPS.

151520 DÉCEMBRE 2011 - N° 10

Vers une informatique pédagogique libre au DIP genevois Marco.Gregori@edu.ge.ch, rédacteur multimédias au Département de l’instruction publique genevois

habitudes acquises lors de la formation d’enseignant, difficultés à récupérer des contenus réalisés avec des logiciels propriétaires, complexité à gérer trois environnements informatiques différents (pédagogique proposé par le DIP, administratif de l’État et privé), ressources insuffisantes: ces risques et préoccupations illustrent à quel point un accompagnement au changement s’avère crucial.

Changer de paradigme

Il s’agit en premier lieu de rendre très lisibles les objectifs du DIP, à travers une information régulière; une campagne de communi-cation auprès des collaboratrices et collaborateurs de l’enseigne-ment est donc d’ores et déjà prévue. Deuxième point, l’assistance fournie aux usagers devra être facilement repérable et rapide. Enfin, concernant l’aide à l’acquisition de nouvelles compétences, des cours existent. Mais l’analyse des besoins a montré que, pour la prise en main des nouveaux outils, une autoformation basée sur des modules en ligne devrait suffire.La date prévue pour la réalisation complète de ce déploiement – 2015 – se base bien évidemment sur une planification interne. Mais elle dépend également d’une réalité exogène. Microsoft a annoncé la fin du support Windows XP pour 2014. Autrement dit, quel que soit le système d’exploitation retenu, libre ou pro-priétaire, une migration aura lieu. Le DIP a simplement choisi de changer de paradigme. Aujourd’hui, le standard est Windows et l’exception MacOS. Demain, le standard sera GNU/Linux, les ex-ceptions MacOS et Windows.

Pour en savoir plus

Consulter le plan de déploiement (icp.ge.ch/sem/projets/spip.php?article619) où l’on trouve également d’autres liens et docu-ments expliquant la politique du DIP genevois en matière de stan-dards ouverts et logiciels libres. Voir également le site du projet GeLibrEdu (icp.ge.ch/sem/gelibredu/).

Article du FI-EPFL 2011 sous licence CC BY-SA 3.0 / M. Gregori

Actuellement, 12’000 ordinateurs constituent le parc informa-tique pédagogique du DIP. Un peu moins d’un quart d’entre eux sont des Macintosh fonctionnant avec MacOS. Les trois quarts sont des PC dotés d’une double configuration: la distribution Ubuntu basée sur GNU/Linux et Windows de Microsoft. Il appar-tient à l’usager de choisir entre les deux systèmes d’exploitation lors du démarrage de son ordinateur. En outre, de nombreux logi-ciels libres, tels que l’application de traitement des images GIMP ou la suite bureautique LibreOffice, sont installés sur Windows.Durant l’année scolaire 2012-2013 un premier changement de taille prévu par le plan de déploiement interviendra, puisque tous les postes pédagogiques de l’enseignement primaire (un par classe) seront exclusivement dotés d’une configuration Ubuntu. À ce jour, sept des quatre-vingt-neuf établissements du primaire genevois font office de pilotes. Cette phase permet de tester la configuration, d’y apporter d’éventuelles modifications en fonc-tion des besoins et de mettre au point la gestion à distance des postes informatiques.

Un système développé à l’UNIL

Parallèlement, l’analyse des besoins pour les salles informatiques des écoles du secondaire I et II a déjà commencé. Elle ne part pas de zéro, puisque dans plusieurs salles des maîtres, les PC tournent déjà sous Ubuntu. Et les salles informatiques PC de trois établis-sements possèdent une informatique entièrement libre. Un des enjeux pour l’enseignement secondaire concerne les tableaux numériques interactifs (TNI) qui, à terme, équiperont l’ensemble des salles de classe. Le choix s’est porté sur Uniboard, un système développé par l’Université de Lausanne, entré dans le monde du libre en 2010 sous l’appellation Open-Sankoré (open-sankore.org).Le fait de distinguer le primaire du secondaire et de procé-der à chaque fois en trois phases – analyse, expérimentation, finalisation – est certes nécessaire, mais ne garantit pas la réussite du programme. La résistance au changement constitue une réalité à prendre en compte, qu’elle soit basée sur des critères objectifs ou des craintes infondées. Effort d’apprentissage et d’adaptation,

Des valeurs convergentes

En cherchant à rendre accessible à la fois les outils informa-tiques et les contenus réalisés grâce à eux, le monde du logi-ciel libre vise un objectif de démocratisation du savoir et des compétences, de partage des connaissances et de coopération dans leur mise en œuvre, d’autonomie et de responsabilité face aux technologies, de développement du sens critique et de l’indépendance envers les pouvoirs de l’information et de la communication. Ces valeurs sont clairement convergentes avec celles d’un système éducatif. À Genève, elles sont même inscrites dans la Loi sur l’instruction publique.En outre, les logiciels libres, par leur grande variété, permettent l’acquisition de compétences transposables à d’autres outils plutôt que l’utilisation répétitive d’un nombre limité de fonc-tions. Cet avantage n’a ainsi pas échappé à de nombreux ensei-gnants qui collaborent à des portails éducatifs en utilisant des logiciels libres.

16 flash informatique 20 DÉCEMBRE 2011 - N° 10

Comment faire ?

La téléphonie VoIP privée en pratiqueJacques.Menu@epfl.ch, téléphoniste du XXIème siècle

This paper presents the practical usage of VoIP to call users through a software application, i.e. a soft-phone and combine regular, analogical telephony on a fixed line and the digital one, over the Internet.

Cet article présente l’emploi concret de VoIP pour téléphoner au moyen d’une application logicielle, soit la softphonie et combiner la téléphonie ana-logique traditionnelle sur ligne fixe et celle, numé-rique, par Internet.

Le problème

L’article Télérama de François Roulet dans le FI5/10 (flashinformatique.epfl.ch/spip.php?article2071) présente le cadre général de VoIP (Voice Over IP) et son expérience dans ce domaine. Ce sujet est de plus en plus d’actualité puisque les centraux télé-phoniques classiques sont progressivement remplacés par des modèles offrant VoIP. Ce sera d’ailleurs le cas de l’EPFL dans le futur.Quand j’ai voulu faire le passage à VoIP moi-même, je me suis ins-piré de l’article de François, ce dont je le remercie ainsi que d'avoir relu cet article. J’ai rencontré quelques difficultés pratiques: en particulier, les différents codes à saisir n’étaient pas toujours clairs pour moi, ni le format à utiliser pour les numéros de téléphone.Le but du présent article est d’éviter ces tâtonnements à d’autres personnes, en montrant les réglages importants pour que ça fonc-tionne. L'obtention d'un numéro VoIP géolocalisé comme 021… n'est pas abordé dans cet article. Comme moi, vous ne connaissez rien à la téléphonie? Suivez le guide!

Pour des raisons de confidentialité, tous les numéros pouvant permettre d’atteindre un correspondant qui figurent dans cet article ont été imaginés: n’essayez pas de les utiliser…

Choix d'un fournisseur d'accès

Comme François, j’ai misé sur la nébuleuse Finarea, qui regroupe un certain nombre de portails offrant le service VoIP, à des conditions variées, listées sur la page progx.ch/home-voip-prix-betamax-3-1-1.html. J’ai choisi Rynga, dont les conditions me conviennent: appels gratuits sur les numéros fixes dans nombre de pays dont la Suisse, et appels sur des numéros de portables à un prix assez bas. Par exemple, les SMS pour la suisse sont facturés 3.2 centimes d’€. Les tarifs détaillés figurent à la page www.rynga.com/en/calling-rates.html. La condition chez Rynga est de pré-payer 10€, les appels payants étant débités sur ce montant; cela

donne droit à quatre mois d’appels gratuits pour les destinations qui s’y prêtent, avec une limite à cinq heures de communication sur sept jours consécutifs. À noter qu'un second appel simultané est lui toujours facturé. Une fois ces quatre mois écoulés, les ap-pels sur les lignes fixes sont débités également. On peut recharger son compte VoIP en tout temps par un versement de 10€ qui nous redonne droit à une période de quatre mois, …

Noms, numéros et codes

C’est la difficulté que j’ai eue pour passer à VoIP, et qui justifie l’écriture du présent article. Il y a dans ce contexte:z le Rynga Name, nom de l’utilisateur sur le site de cette société,

et aussi son identité lorsqu’il fait des appels ou envoie des SMS;z le mot de passe du compte VoIP Rynga, demandé lorsqu’on

s’y connecte pour le gérer. Pour les besoins de cet article, le compte est appelé basbois, et le connection name est donc basbois@rynga;

z le caller ID, soit un numéro international +41217896543 qui indique au correspondant qui est son interlocuteur si son équipement le permet;

z le système PIN du boîtier Siemens, si on en a un, utilisé lorsqu’on s’y connecte pour le paramétrer. C’est un code de quatre chiffres décimaux, 0000 initialement.

Création d'un compte VoIP auprès de Rynga

Elle se fait par la page www.rynga.com/en/index.html. On doit indiquer les numéros de téléphone qui seront utilisés comme étant l’appelant, avec le préfixe international, par exemple +41216934587. On a droit à cinq numéros au maximum.Lors de leur enregistrement depuis la page de profil de l’utilisateur (Personal détails), Rynga appelle le numéro indiqué pour vérifier qu’il est utilisable. Lors de cet appel, on reçoit un code à quatre chiffres *à usage unique*, à saisir dans le dialogue d’enregistre-ment du numéro. On voit dans la page de profil également un numéro d’appel local dans le pays de résidence choisi, comme 031xxxyyzz pour la Suisse, qu’on obtient en choisissant la ville la plus proche dans une liste. Pour appeler un numéro international depuis n’importe quel type de téléphone, on compose ce numéro local puis le numéro inter-national désiré. Ce faisant, on paie la communication au tarif local jusqu’à ce numéro dans le pays, puis l’accès international se fait en VoIP aux conditions décrites plus haut. Une fois le compte VoIP créé et crédité, on peut faire des appels, depuis au choix:z un logiciel dit softphone, qui tourne sur un ordinateur, un

téléphone mobile ou une tablette, et qui permet de faire des appels VoIP;

171720 DÉCEMBRE 2011 - N° 10

z un boîtier de téléphonie hybride analogique/numérique, en dur, comme en propose par exemple Siemens.

Gestion courante du compte VoIP

Elle se fait par la page https://www.rynga.com/myaccount qui, en plus de donner l’accès au profil de l’utilisateur, montre:z les dates et montants des ver-

sements réalisés;z les appels récents avec date

et heure, numéro appelé, du-rée et coût, ou FREE pour les appels gratuits;

z le moyen de créditer son compte VoIP;

z le moyen de télécharger le logiciel softphone Mobile-VOIP pour iPhone/iPod/iPad, Android, Nokia/Symbian et Windows Phone.

On voit ci-contre la colonne de gauche de cette page de gestion.

Où l'on se lance dans la softphonie

Comme softphone, j’ai installé X-Lite 4 et MobileVOIP, fournis par Rynga, sur Mac OS X et iPhone/iPod/iPad respectivement. Il en existe bien sûr quantité d’autres, mais qui ne sont pas spécifiques aux portails de Finarea.

On voit l’apparence de l’application X-Lite 4 ci-contre. Petit détail: si on supprime un contact qui est dans plusieurs catégories à la fois, comme Christian dans cette figure, il dispa-raît intégralement. Pour le supprimer dans une seule catégorie, il faut la simplement la décocher dans la définition du contact.

Le compte VoIP Rynga est enregistré dans les préférences de l’application, comme l’il-lustrent les deux figures ci-après.

Emploi de la base hybride analogique/numérique Gigaset

Suivant les traces de François, j’ai opté pour un boîtier Siemens, appelé base par ce constructeur. Ce modèle Gigaset C610A IP vient avec un combiné noir et son support pour le recharger, mais ce support ne joue pas d’autre rôle. Le A indique qu’un répondeur est intégré à la base (il y en a trois en fait, un par paire de combi-nés, voir l’article de François). J’ai aussi un second combiné avec son support, blanc pour pouvoir les distinguer. Ci-dessous, une vue d’ensemble de l’installation, dans laquelle:z la base avec ses deux connexions RJ 11 (téléphonie) et RJ 45

(réseau informatique) est au centre,;z un combiné est montré en bas à droite sur son support;z le boîtier en haut à gauche fournit l’accès à Internet, par

exemple sous la forme d’un routeur, modem réseau ou ADSL;z l’ordinateur en haut à droite n’est utile que pour accéder au

paramétrage de la base, il n’intervient pas dans les communi-cations téléphoniques.

La base est préconfigurée pour obtenir une adresse IP d’un serveur DHCP, comme souvent pour ce genre d’équipement. À la maison, cela se passe donc très bien avec les équipements réseau actuels. Cet équipement héberge un site Web de gestion et de paramé-

La téléphonie VoIP privée en pratique

18 flash informatique1818 20 DÉCEMBRE 2011 - N° 10flash informatique

trage, qui s’annonce sur le réseau. Il suffit, pour y accéder, de choi-sir l’URL www.gigaset-config.com/myDevice/ dans son butineur préféré: cela recherche une base sur le réseau local, qui s’affiche alors avec son adresse IP, comme 10.0.1.42 ici.

Dans le site intégré à la base, on a accès aux différents paramètres de sa configuration.Dans Settings:z sous l’onglet NetWork, IP Configuration, le réglage de la

configuration réseau IP (DHCP par défaut) et en cliquant sur Show Advanced Settings, le nom de la base. On peut si né-cessaire mettre en place une adresse IP fixe si DHCP ne fait pas l’affaire dans le cas concret.

Dans Telephony, on peut spécifier:z sous l’onglet Connections, l’enregistrement d’au maximum

six combinés en plus de la ligne fixe analogique et leur acti-vation/désactivation. C’est ainsi que les combinés sont raccor-dés à la base: leur support ne joue aucun rôle, il ne sert qu’à charger les batteries. Voir les réglages pour le combiné 1 dans l’écran ci-contre. Le bouton Start Configuration Assistant n’est pas utilisable pour Rynga, qui n’est pas connu pour cette fonctionnalité: il a donc fallu fournir à la main les valeurs indi-quées sur ce portail;

z sous Number Assignment, les réglages des combinés enre-gistrés pour les appels entrants et sortants. Dans la figure ci-contre, tous deux acceptent les appels entrants sur la ligne fixe, mais tous les appels sortants vont sur Internet, en uti-lisant le compte basbois@rynga. De plus, si l’accès à Internet n’est pas possible, les appels sortants passent automatique-ment par la ligne fixe (Automatic Fallback to Fixed Line);

z sous Dialing Plans, l’emploi de la ligne fixe ou d’Internet pour certaines gammes de numéros. Ainsi, on peut forcer l’accès à des numéros payants comme 0800… par la ligne fixe, certains n’acceptant pas de connexion VoIP;

z sous Advanced VoIP settings, on peut choisir des réglages plus fins, que j’ai laissés inchangés.

Dans Directories:z sous Online Directory, on définit si l’on veut que les numé-

ros entrants soient recherchés dans un annuaire sur Internet pour afficher l’identité de l’appelant; c’est tel.search.ch qui est proposé pour la Suisse;

z sous Directory Transfer, on peut importer/exporter le conte-nu du répertoire de numéros pour chaque combiné individuel-lement. L’exportation se fait par Save, ce qui crée un fichier teledir.vcf qu’on peut renommer à volonté. Après modification

La téléphonie VoIP privée en pratique

réglages pour le combiné 1

Number assignment

du fichier texte sur un ordinateur, il suffit d’effacer le réper-toire dans le combiné par Delete puis de le télécharger par Transfer.

191920 DÉCEMBRE 2011 - N° 10

Dans Management:z sous Save & Restore, le plus important peut-être est qu’on

peut sauvegarder les réglages complets de la base sur un fichier d’un ordinateur, et les recharger à volonté;

z enfin, sous Firmware Update, on peut aller chercher la ver-sion la plus récente du logiciel interne de la base chez Siemens sur Internet. Il est conseillé de le faire lors de l’installation du matériel, qui peut avoir été stocké un certain temps avant qu’on le reçoive, et c’est un bon test de la connexion de la base au réseau.

Dans l’onglet Status de la page principale du site intégré à la base, on voit l’état de cette dernière, illustré ci-après, et celui des connexions par la ligne fixe et les deux accès par VoIP configurés, illustré ensuite.

Les autres réglages de la base sont décrits dans la documentation. On peut les laisser tels qu’ils ont été mis en place par le fabricant.Un côté intéressant de la préparation du répertoire des combinés sur un ordinateur est qu’on peut facilement le rendre identique sur tous les combinés en employant le même fichier. Voici un exemple de contenu de ce fichier.

BEGIN:VCARDVERSION:2.1N: Yellow Pages;TEL;HOME:2#91END:VCARD

BEGIN:VCARDVERSION:2.1N: [tel.search.ch];TEL;HOME:1#91END:VCARD

BEGIN:VCARDVERSION:2.1N:Reamey;AmiTEL;HOME:0294631292TEL;CELL:0899875321END:VCARD

Si on est équipé de plusieurs postes reliés à la même base, on peut transférer une communication en cours sur un autre poste. Le petit plus, c’est de pouvoir appeler gratuitement tout client du même fournisseur, avec un identifiant comme 222430994014#9@sip.gigaset.net.

Quels avantages?

Avec la base Siemens illustrée ici, on peut avoir deux appels en cours, entrants comme sortants, ce qui est très pratique !Plus généralement, VoIP offre essentiellement:z des communications bon marché, accessibles depuis divers

endroits et avec divers outils: combiné ou softphone, sur dif-férents matériels pour ce dernier;

z un accès permanent à l’état de son compte, en particulier le nombre de jours de gratuité restant et la listes des appels effectués, par Internet comme depuis les softphones;

z la possibilité d’appeler tout numéro de téléphone, sans qu’il doive être accessible par VoIP lui-même;

z la possibilité d’envoyer des SMS;z la facilité pour planifier les coûts des appels.Pour certains services ou achats sur Internet, on vous demande un numéro de téléphone dans le pays du prestataire de service: il suffit d’avoir un numéro VoIP dans ce pays, et le tour est joué.En prime, si vous avez un accès Wi-Fi mais pas de communication GPRS possible, parce que vous êtes dans une zone non desservie ou parce que ce serait trop cher, vous pouvez toujours communi-quer par VoIP. C’est le cas par exemple en vacances ou en dépla-cement à l’étranger, il n’y a plus de notion de territoire.

Un monde parfait?

VoIP a de très bons côtés, mais il faut être bien conscient que:z la disponibilité d’un accès Internet n’est pas comparable à

celle du réseau téléphonique fixe, alimenté électriquement par les centraux et très fiable;

z au moment où j’écris cet article, le mot de passe de mon compte est stocké en clair par Rynga, une faiblesse.

Quelle est la qualité du son? Cela dépend des codecs utilisés pour compresser puis décompresser les paquets contenant le son qui circulent sur Internet. Il y a donc parfois un son moins bon qu’en analogique.Un autre phénomène, déroutant la première fois, est qu’il peut arriver que les paquets provenant du correspondant soient retar-dés puis arrivent en avalanche: rien ne s’est perdu, mais il faut tout de même demander de répéter.La documentation de la base Siemens utilisée ici est bien faite et disponible en plusieurs langues, y compris en format PDF. Une volée de bois vert toutefois à l’interface utilisateur sur un point: pour changer la langue des répondeurs téléphoniques inté-grés, il faut fouiller la documentation pour trouver l’horreur sui-vante en page 117,

alors qu’il serait si facile de proposer ça dans le site Web de ges-tion intégré… Décidément, personne n’est parfait, même dans le monde d’Internet! n

La téléphonie VoIP privée en pratique

20 flash informatique2020 20 DÉCEMBRE 2011 - N° 10flash informatique

Question: How can business schools save money on printing, contribute to environmental sustainabil-ity, improve networking opportunities among par-ticipants and bring cutting edge knowledge into the classroom ? The answer – the iPad.

Question: comment une école de management peut-elle faire des économies sur les frais d’impression, contribuer au développement durable, augmenter les possibilités de réseautage entre les participants et introduire les dernières innovations technologiques dans une salle de classe ? Réponse : l’iPad.

Une expérience pilote avec l’iPad réalisée dans le cadre d’un pro-gramme privé pour Allianz Global Investors, nous a convaincus que cette tablette, assez fine pour tenir dans une enveloppe en papier kraft et plus légère qu’un notebook, allait révolutionner le monde de l’enseignement.La veille du programme, chaque participant a reçu un iPad. Celui-ci contenait toutes les présentations des cours, les cas à étudier, les informations logistiques relatives au programme, sans oublier les applications standards et la possibilité de se connecter au WiFi. La configuration permettait également au coordinateur de programme de rester en contact avec les participants en perma-nence. Les participants l’ont utilisé tout au long de leur séjour et l’ont rendu à la fin. Ils ont ensuite pu récupérer l’intégralité de leurs documents grâce au portail Web. Les commentaires des évaluations, tant du personnel de l’IMD ou que des participants, ont été très positifs. Certains participants ont même mentionné qu’ils s’achèteraient un iPad dès qu’ils seraient disponibles dans

leur pays d’origine, et de plus en plus de professeurs de l’IMD ont décidé d’intégrer ce nouvel outil dans la conception de leurs pro-grammes.Pour les fournisseurs d’information dans le milieu de l’enseigne-ment, l’iPad est le premier pas vers une solution sans papier. Notre bilan:

Avantages

Une solution plus économiqueLes économies financières peuvent en effet être importantes. Par exemple, il arrivait auparavant que les participants de certains longs programmes de l’IMD recevaient des classeurs pouvant contenir plus de 1000 pages, ce qui est loin d’être négligeable en termes de coûts d’impression. En revanche, dès sa première utili-sation, l’iPad peut déjà être rentable. Sachant qu’il est rendu à la fin du programme, l’investissement n’est fait qu’une seule fois et non plus lors de chaque session.

Respect de l’environnementEn économisant des arbres et l’énergie nécessaire à produire, transporter et imprimer le papier, l’iPad permet aux écoles de management d’apporter une contribution positive au développe-ment durable.

Réseautage et accessibilité permanenteÉchanges de cartes de visite et de coordonnées peuvent à pré-sent être faits de manière virtuelle, ce qui élargit les possibilités de réseautage et de contact entre participants. Du point de vue logistique, cela permet aux coordinateurs de programme d’être constamment en contact avec leurs participants et de les infor-mer de tout changement.

iPad, une révolution dans la salle de classe ?Bettina Büchel, Professeur à l’IMD et Directrice du Programme OWP et Iain Cooke, CTO, IMD – texte traduit de l’anglais

Analyse

212120 DÉCEMBRE 2011 - N° 10

Information en temps réelLes participants ont en tout temps accès aux informations les plus récentes sur les performances des entreprises, les rapports et autres documents utiles, ce qui est aussi un avantage pour les professeurs.

Préparation de la session facilitéeImaginons qu’on professeur veuille donner accès à certaines informations seulement après avoir abordé les points-clés de sa session. Il est possible de trouver un équivalent électronique à la distribution des documents qui soit simple, rapide et fiable. Bien entendu, le succès de cette intégration technologique suppose de faire l’effort d’installer les outils, systèmes et serveurs adéquats. Tout doit fonctionner ensemble, de manière sûre et conviviale, tant du point de vue des collaborateurs de l’IMD que des parti-cipants.

Inconvénients

Potentiel ludiqueL’introduction des iPad dans une salle de classe n’a bien évidem-ment pas pour but de permettre aux participants de surfer sur le Web pour prendre connaissance des derniers résultats sportifs ou de chatter avec leurs amis. Il faut donc dès le début du pro-gramme les y rendre attentifs et limiter aux pauses ce type d’uti-lisation. Cependant, c’est un piège que l’on devrait pouvoir évi-ter, sachant que c’est aujourd’hui un réflexe relativement intégré pour les téléphones portables. L’iPad n’est qu’un nouveau support à prendre en compte et les professeurs peuvent répéter l’avertis-sement si besoin.

Résistance à la lecture sur écranCertains participants préféreront lire les documents sur papier, dans ce cas, l’école doit donner la possibilité d’imprimer certains documents lorsque c’est approprié. Cette tendance est plus ou moins importante selon l’âge des participants.

Prise de note moins aiséeAnnoter des documents de façon électronique est un nouveau défi à relever et le programme pilote en a démontré la nécessité.

L’IMD (www.imd.ch) est l’un des pionniers et leaders mondiaux dans la forma-tion des cadres supérieurs. Son rôle dépasse largement celui d’une business school traditionnelle: nous collaborons avec des individus, des équipes et des organisations pour résoudre des problèmes d’entreprise réels, développer des compé-tences et préparer l’avenir. Nos actions s’appuient sur une approche unique, Real World, Real Learning, née de nos partenariats durables avec des entreprises internationales de premier plan. Sur notre campus au bord du lac Léman en Suisse et dans des endroits clés du monde entier, nous proposons des programmes et des services d’une qualité unique, qui mélangent expé-rience pratique, stratégie d’innovation et vision mon-diale. Les participants à ces programmes choisissent IMD pour son environnement de formation ouvert et stimulant qui leur permet de bousculer leurs a-priori et élargir leurs horizons.

iPad, une révolution dans la salle de classe ?

L’IMD développe actuellement une approche qui permet le mar-quage électronique des documents en lien avec des notes prises sur papier. Nous vivons à une époque où l’écart entre les géné-rations est probablement à son apogée, à savoir entre les plus âgés ayant connu la technologie plus tard dans leur carrière et les jeunes qui ont toujours vécu avec. L’iPad est néanmoins si convi-vial qu’il devrait permettre une transition agréable et amusante pour les managers peu familiers avec la technologie.Les possibilités de ce support dans une salle de classe sont presque illimitées et il est difficile de prévoir ce qui, à terme, aura le plus de valeur ajoutée pour nous. Nous sommes encore dans la phase de découverte et d’analyse des retours de participants. Toutefois, il ne fait pas de doute que les écoles de management se doivent d’être à la pointe de l’innovation et une utilisation intelligente de l’iPad est un moyen d’atteindre cet objectif.n

22 flash informatique 20 DÉCEMBRE 2011 - N° 10

An investigation of a different type at the EPFL: programmed computer disappearance.

Une enquête d’un autre type à l’EPFL: l’ordinateur disparaît au Musée Bolo.

Les archéologues du Musée Bolo ont réuni une brochette de cé-lébrités autour de cet étrange phénomène: la disparition pro-grammée de l’ordinateur. Les pionniers suisses de l’informatique ont apporté leur témoignage au cours de du vernissage de la nouvelle exposition. Une réplique de la première souris au monde a été remise au Musée par le fondateur de Logitech, Da-niel Borel. Un ordinateur dinosaure, datant des an-nées soixante et cent pour cent suisse, a été dévoilé par son concepteur. Au cœur du Musée Bolo, sur un mur de vingt et un mètres de long, les fils d’une enquête d’un autre type s’entrecroisent autour de niches de couleur brillamment éclairées où trônent des objets qu’Yves Bolognini, ingénieur informaticien EPFL et co-fon-dateur du Musée avec Edouard Forler, collectionne depuis plus de quinze ans. Autant d’indices, de preuves et de suspects répartis en cinq chapitres inédits qui jalonnent la disparition programmée de l’ordinateur. Les visiteurs sont invités à répondre aux questions posées par les auteurs de l’enquête sous l’œil impassible ou narquois des photos des principaux témoins.Les exemples foisonnent pour illustrer les cinq pistes autour de cette disparition: réduction, camouflage, oubli, dissolution, humanisation. Première piste, devenue désormais classique, la réduction ou miniaturisation des composants de l’ordinateur n’est en effet pas la seule cause de sa disparition. Car la machine

se cache à l’intérieur d’autres objets et se camoufle derrière un design attractif. Elle se fait oublier derrière la façade ludique des jeux vidéo ou dans les pièges de la réalité virtuelle. Elle se dis-sout dans le grand nuage informatique dont le meilleur exemple est Internet. Elle s’humanise par le biais d’interfaces nouvelles et devient intelligente en imitant l’homme.Les archéologues du Musée Bolo n’ont cependant pas dit leur der-nier mot et poursuivent leur enquête. Car des éléments nouveaux ont surgi tout au long du vernissage de l’exposition qui se tenait au Forum du RLC. Deux pionniers de la première heure, Niklaus

Wirth, auteur du langage de programmation Pascal qui a fait le tour du monde, et Jean-Daniel Nicoud, concepteur des micro-or-dinateurs Smaky sur lequels s’est initiée toute une génération de jeunes Suisses, ont montré la filiation entre les premières avancées de l’informatique et les artefacts de notre monde contemporain.Créant la surprise car il n’était pas annoncé, Daniel Borel, fonda-

teur de Logitech, a rendu hom-mage à l’inventeur de la souris, Douglas Engelbart, et mis à dis-position du Musée sa réplique de la première souris de 1968. Construite en bois, elle est dotée d’un unique bouton et de deux roues en métal.Enfin, un autre pionnier inat-tendu et encore inconnu, Peter Toth, a évoqué avec émotion ses recherches pour concevoir, au milieu des années soixante, la Cora, un gigantesque ordinateur

La disparition programmée de l’ordinateurMarielle.Stamm@memoires-informatiques.org & Yves.Bolognini@memoires-informatiques.org, Mémoires Informatiques

Actualités

Niklaus Wirth, un des principaux témoins de l’enquête sur la disparition de l’ordinateur

Jean-Daniel Nicoud , pionnier de la micro-informatique suisse

232320 DÉCEMBRE 2011 - N° 10

destiné à l’armée suisse, oublié puis redécouvert par Yves Bologni-ni dans les caves de l’EPFL. Les entrailles ouvertes, cette grosse machine exhibe ses composants d’un autre âge face au mur de l’exposition Disparition programmée.

La disparition programmée de l’ordinateur

suisse. À sa suite, François Marthaler, conseiller d’Etat, a évoqué les étapes les plus marquantes de l’évolution de l’informatique à l’Etat de Vaud. Martin Vetterli, doyen de la Faculté I&C, a brossé à grands traits et avec maestria l’histoire de l’ordinateur, d’Ada Lovelace, première programmeuse au monde, au nuage informa-tique. Il incombait à Giovanni Conti, directeur de l’Office fédéral de l’informatique et de la télécommunication (OFIT), d’émettre quelques réserves face à la complexité croissante des systèmes et aux risques qu’elle entraîne. Et d’encourager avec à propos l’EPFL à développer des systèmes capables de s’auto-diagnostiquer et de s’auto-réparer.L’exposition Disparition programmée a été réalisée par la Fonda-tion Mémoires Informatiques, dont la vocation est la sauvegarde du patrimoine informatique, avec l’assistance de l’association des Amis du Musée, l’aBCM. Elle est visible au Musée Bolo dans les bâtiments de la Faculté Informatique et Communications, durant les heures d’ouverture de l’École du lundi au vendredi de 8 heures à 19 heures.

Informations pratiquesz Visites guidées: www.abcm.ch/visites z Des photos et le film du vernissage sont disponibles à l’adresse:

www.bolo.ch/?liens .z Pour tout autre renseignement: Yves Bolognini, 078 748 21 16

NB: les photos illustrant cet article sont avec droits limités: Sébastien Monachon, BSC Association.n

Le public découvre la nouvelle exposition du Musée Bolo

L’Apple Lisa 2 trône de l'autre côté du mur

Daniel Borel, l'invité-surprise, rend hommage à Douglas Engelbart

Parmi les autres intervenants du vernissage, signalons Philippe Gillet, vice-président de l’EPFL pour les affaires académiques, qui a rappelé, dans son message d’accueil, le rôle important joué par l’École dans les premiers développements de l’informatique

24 flash informatique 20 DÉCEMBRE 2011 - N° 10

Problem analysis, conception of a solution approach, followed by an efficient implementation – a job for real engineers. Three EPFL teams, trained by Poly-Prog, recently took up this challenge and proved their skills at a top level.

Décortiquer le problème, chercher une approche conduisant à la solution, implémenter celle-ci de manière efficace – un vrai travail d’ingénieur de A à Z. Ce fut le défi auquel se sont livrées récemment 3 équipes de l’EPFL entraînées par PolyProg, en faisant preuve d’excellente maîtrise.

Ce furent Andrei Giurgiu, Anton Dimitrov et Christian Kauth qui ont su assurer une respectable 18e place parmi 1’500 équipes autour du globe, pendant un marathon de 24 heures de concen-tration absolue dans le cadre du IEEEXteme 5.0 [1]. Juste un mois plus tard, deux équipes d’étudiants de l’EPFL, Johannes Wüthrich, Mihai Moraru, Przemyslaw Pietrzkiewicz, Cheng Zhong, Le Hung Tran et Cristian Talau, ont décroché des médailles de bronze au SWERC [2] à Madrid. Elles y furent préparées par le formateur de PolyProg, Christian Kauth et ses assistants Jonas Wagner et Andrei Giurgiu.Sans pouvoir émuler ici l’atmosphère sérieuse, pleine de suspense et ardente d’un vrai concours, nous vous proposons de suivre le parcours qui mène d’un problème populaire du SWERC à sa solu-tion. Une pensée analytique, l’ingéniosité et une bonne maîtrise d’un langage de programmation (nous choisissons le C++ ici) sont indispensables au succès. En voici l’énoncé:

Ce fut le weekend des élections en Espagne et il s’agissait de distribuer les B (B<2’000’000) boîtes de vote parmi les N (N<500’000) villes du pays, de sorte à ce que la pire densité d’électeurs par boîte soit minimisée. À part N et B, on vous donne aussi le nombre d’électeurs par ville ai , ne dépassant pour aucune ville M (M≤5’000’000). Appelons bi le nombre de boîtes attribuées à la ville i. Un minimum d’une boîte par ville est requis.

Ce problème, extrait de la vraie vie, admet plusieurs approches correctes d’efficacités différentes. Testez jusqu’où vous auriez su pousser la barre !

La force brute en O(BN)

Le problème est facile à résoudre : il faut juste donner les boîtes aux villes qui en ont le plus besoin:

Initialiser le nombre de boîtes: bi 1 pour

chaque villeTant qu’il nous reste des boîtes: trouver la ville avec densité a

i/b

i maximale

ajouter une boîte à cette ville: bi b

i + 1

Cette stratégie est gloutonne. Elle choisit à chaque étape la solu-tion optimale, sans considérer les prochaines étapes. Les boîtes déjà attribuées ne sont jamais redistribuées. Malgré sa simplici-té, elle donne le résultat correct. Pour prouver cela, constatons d’abord que le résultat est correct si B=N, car il faut donner une boite à chaque ville dans ce cas. Si nous ajoutons la boîte suivante à la ville avec le pire rapport habitants/boîtes, nous parlons de densité dans la suite, la solution reste optimale. Par induction, il s’ensuit que la solution est optimale pour chaque B>N.Malheureusement, cette solution est trop lente pour marquer des points dans un concours: pour chaque boîte, il faut parcourir toutes les villes et trouver celle qui recevra la boîte. L’algorithme effectue donc B*N opérations, soit un trillion d’opérations !

Savoir et savoir-faire en algorithmiqueChristian.Kauth@epfl.ch, EPFL - président de PolyProg & Jonas.Wagner@epfl.ch, EPFL- membre du comité de PolyProg

Actualités

g.à.d. Anton Dimitrov, Christian Kauth, Andrei Giurgiu

252520 DÉCEMBRE 2011 - N° 10

Encore brut, mais structuré O(B log(N))

Nous pouvons améliorer notre algorithme, si à chaque distribution de boîte, nous trouvons la ville la plus dense plus rapidement. Il nous faut une structure de données qui permet d’accéder rapide-ment au plus grand élément d’une collection. Une telle structure s’appelle un tas (heap) ou une file de priorité (priority queue) [3].Voilà notre algorithme modifié:

Initialiser le nombre de boîtes: bi 1 pour

chaque villeInsérer chaque ville dans une file de priorité QTant qu’il nous reste des boîtes: extraire la ville avec densité a

i/b

i

maximale de Q ajouter une boîte à cette ville: b

i b

i + 1

réinsérer la ville dans Q

Les opérations d’extraction et d’insertion prennent un temps logarithmique en taille de la file. Du coup, le coût total de cet algorithme est d’ordre O(B log(N)). Ceci est nettement plus rapide, mais s’élève encore à une centaine de millions d’opérations.

Se poser la bonne question O(N log(M))

Faisons tabula rasa. Au lieu de créer la distribution optimale des boîtes pas par pas, nous allons simplement deviner quel est le nombre de personnes par boîte dans une distribution optimale. Cette straté-gie n’est pas juste plus élégante, mais s’avère aussi plus efficace.Appelons X0 notre densité devinée. Se pose ensuite la question si une distribution respectant cette densité existe ou non ! La réponse à cette question est facile à calculer: Connaissant X0 , chaque ville nécessite !! =

!!!! boîtes. Si le nombre total de

boîtes nécessaires ne dépasse pas B, il existe effectivement une telle distribution. Soyons plus ambitieux alors et essayons une nouvelle densité X1 ≤ X0 . Dans le cas contraire, tentons notre chance avec un objectif plus modeste X1 ≥ X0 .Ceci nous donne une séquence des bornes pour lesquelles nous savons si elles sont trop ambitieuses ou faisables. Si nous faisons une recherche binaire sur X , chaque réponse coupe la taille de notre intervalle de recherche en deux et nous convergeons vers la plus petite densité qui admet une distribution faisable! Une fois l’idée trouvée, l’étape suivante consiste à formaliser l’algorithme sous forme de pseudocode.

Initialiser la borne inférieure Xmin 0

Initialiser la borne supérieure Xmax M+1

Tant que Xmax – X

min > 1:

X ceil(avg(Xmin, X

max))

Calculer le nombre de boîtes qu’il faudrait: B

necessaire = sum ceil(a

i/X)

Si Bnecessaire

> B: Xmax X

Sinon Xmin X

Xmin est maintenant la solution recherchée.

Vu qu’à chaque itération, la moitié des solutions possibles peut être écartée et qu’il faut calculer le nombre de boîtes pour chaque ville en chaque itération, la complexité totale de cette approche est O(N log(M)) et elle vous aurait amené des points au SWERC ! Il est vrai que la limite inférieure aurait pu être initialisée à la popu-lation de toute l’Espagne P=∑ai , divisée par B. Est-ce que vous trouvez aussi une meilleure estimation pour la borne supérieure ?

Par hasard O(N log(N))

Terminons notre excursion des approches sur une solution extra-vagante, qui met à profit le hasard et déclasse toutes les approches précédentes ! L’observation de base est la suivante: si P est la population totale de l’Espagne, il faudrait idéalement attribuer 1 boîte par ville (c’est le minimum selon les règles du jeu) et distri-buer les (B-N) boîtes restantes sur les villes, proportionnellement à leur population. Etant donné que les boîtes constituent des ob-jets discrets, cette stratégie n’est pas applicable telle quelle, mais nous en tirons néanmoins le nombre minimal de boîtes entières pour chaque ville, !! =

!! ! − !! + 1 . Après cette distribution, il

nous reste R = (B-∑bi ) boîtes pour améliorer la situation dans R villes au maximum. Il est garanti que R<N, puisqu’autrement, nous pourrions donner une boîte de plus à chaque ville ! Nous en concluons que la ville avec la (R+1)–ième plus grande densité (et toutes les villes avec densité inférieure) ne se verra attribuée plus aucune boîte supplémentaire et nous donne une borne inférieure à la pire densité. Ramassons ensuite de nouveau toutes les boîtes des R villes les plus denses et redistribuons-les, avec les R boîtes restantes, selon ce même schéma ! La fonction solve accomplit ceci de manière récursive. Dans le pire des cas, R=N-1 , et solve est appelé N fois ! En pratique, R suit néanmoins une distribution uniforme, entre 0 et N-1 et l’espérance des appels récursifs de solve vaut O(log(N)). Après le pseudo-code vient l’implémenta-tion en langage de programmation. Une somme ! = !! + !!

!

!

s’écrit en C++ S=accumulate(&x0,&xN,s0) et la partie entière supé-rieure C d’une fraction de deux entiers a et b s’exprime comme C = a/b + (a%b>0).

int64 solve(int64 N, int64 B) P = accumulate(&a[0],&a[N],0ll); for (int i=0; i<N; i++) b[i] = (a[i]*(B-N))/P+1; if (N<=0) return 0; if (N==1) return a[0]/b[0]+(a[0]%b[0]>0); R = B-accumulate(&b[0],&b[N],0ll); N = nth_largest(0,N,R+1); B = accumulate(&b[0],&b[N],R); return max( a[N]/b[N]+(a[N]%b[N]>0), solve(N,B) );

Pour mener à bien cette approche, solve doit trouver de manière efficace la n-ième densité par appel à la fonction nth_largest. L’intuition de trier les villes selon leur densité en O(N log(N)) et d’en choisir la n-ième ensuite nous tend un piège, car cette solu-tion fait plus de travail que nécessaire. La bonne approche fonc-tionne comme suit: sélectionnons un pivot et réarrangeons les villes de sorte à ce que celles avec les densités supérieures à celle du pivot se trouvent à sa gauche et celles inférieures, à sa droite. Maintenant seulement la ville pivot est garantie d’être dans sa po-sition ordonnée, que nous appelons m. Si n=m, nous avons trouvé ce que nous cherchions! Si m est inférieur à n, le n-ième élément est dans la partie de droite et à gauche si m est supérieur à n. Par récursivité sur la partie en question, nous trouvons finalement la n-ième ville la plus dense sans opportunité d’amélioration ! Le code ci-dessous rend les choses claires.

Savoir et savoir-faire en algorithmique

26 flash informatique2626 20 DÉCEMBRE 2011 - N° 10flash informatique

int64 partition(int64 left, int64 right, int64 pivot) int64 swappos(left), i; swap(a[right-1],a[pivot]); swap(b[right-1],b[pivot]); for (i=left; i<right; i++) if (a[i]*b[right-1] > a[right-1]*b[i]) swap(a[i],a[swappos]); swap(b[i],b[swappos]); swappos++; swap(a[right-1],a[swappos]); swap(b[right-1],b[swappos]); return swappos;

int64 nth_largest(int64 left, int64 right, int64 N) int64 pivot, rank; if (left==right-1) return left; pivot = left + rand()%(right-left); pivot = partition( left, right, pivot ); rank = pivot-left+1; if (rank>N) return nth_largest( left, pivot, N); if (rank<N) return nth_largest( pivot+1, right, N-rank ); return pivot;

g.à.d. Cheng Zhong, Cristian Talau, Le Hung Tran

L’utile théorème de Master [4] prédit une complexité O(N) en moyenne et O(N^2) dans le pire des cas pour la fonction nth_largest. D’une part, cinq grandes têtes (Blum, Floyd, Pratt, Rivest et Tarjan) y ont trouvé un remède élégant [5] qui garantit toujours une complexité linéaire, et d’autre part le fait d’inclure le hasard dans l’algorithme, rend l’occurrence du pire cas très improbable (1 chance sur N factorielle). Comme les juges du concours ne peuvent aucunement anticiper notre suite de pivots, il n’y a pas de test [6] pour lequel nth_largest ne serait pas de complexité linéaire, donc solve de complexité O(N log(N)). Dans l’hypothèse des éventualités, notre code dépasse le temps d’exécution limite. Il suffit alors de re-soumettre le même code une seconde fois, avec une initialisation aléatoire différente.Comme vous avez pu constater, il existe souvent des approches très différentes à un même problème, se distinguant par leur faci-lité d’implémentation et efficacité. Dans le cadre d’un concours, le temps est une ressource limitée et les programmeurs sont tou-jours face au dilemme entre l’efficacité de leur approche et sa difficulté d’implémentation. C’est précisément à ce niveau qu’une excellente maîtrise du langage de programmation est un énorme

atout. Les programmeurs expérimentés et rusés savent même tirer avantage des propriétés bénéfiques du hasard.N’hésitez pas à faire vous-mêmes l’exercice de l’implémentation et testez votre solution sur un juge automatique [7]. Si vous avez trouvé du plaisir à stimuler vos neurones avec des problèmes simi-laires, faisant appel à votre créativité et à votre savoir-faire en algorithmique, formez vite votre équipe pour le Helvetic Coding Contest [8] et inscrivez-vous d’ores et déjà sous hc2.ch. PolyProg organisera cette 3e édition avec le soutien de l’EPFL, OpenSys-tems [9] et AdNovum [10]. Une centaine d’étudiants (de l’école secondaire jusqu’au doctorat) afflueront des quatre coins de la Suisse pour vous défier le 17 mars 2012, ici au campus, dans une atmosphère conviviale et chacun trouvera des problèmes de son niveau !

g.à.d. Johannes Wüthrich, Mihai Moraru

Références

[1] IEEEXteme 5.0: concours algorithmique de 24 heures. www.ieee.org/membership_services/membership/students/compe-titions/xtreme/index.html.

[2] SWERC: Finales régionales sud-ouest européennes de l’Inte-national Collegiate Programming Contest. swerc.eu.

[3] File de priorité: fr.wikipedia.org/wiki/File_de_priorité[4] Théorème de Master : Livre de cuisine pour la solution de

relations récursives en termes de complexité.[5] Un algorithme très similaire à celui présenté, qui garantit

une réduction d’au moins 30% de l’espace de recherche à chaque itération en utilisant la médiane des médianes.

[6] Dans les concours, un juge automatique compile le code source et le teste contre différentes entrées. Des points sont ensuite attribués en fonction de l’exactitude de la réponse et la mémoire et temps CPU accaparés.

[7] Il s’agit du problem 12390 sur Uva online judge, uva.online-judge.org.

[8] Le premier concours de programmation suisse depuis 2010. hc2.ch.

[9] OpenSystems, sponsor de l’hc2 2012. open.ch.[10] AdNovum, sponsor de l’hc2 2012. www.adnovum.ch.n

Savoir et savoir-faire en algorithmique

2720 DÉCEMBRE 2011 - N° 10

Twice a year, ForumIT is meeting point for IT Domain and IT-people from the EPFL labs (more than 200 people). If you could not attend the November 24 Forum IT, you will find here abstracts of the tackled subjects. The presentations are available on the site dit.epfl.ch/forumIT.

Le 24 novembre 2011, un peu plus de 30 respon-sables informatique d’unités ont assisté au ForumIT, rencontre bisannuelle avec le DIT. Pour ceux qui n’ont pas pu y assister, voici les sujets qui ont été abordés. Les présentations sont disponibles sur le site dit.epfl.ch/forumIT.

IT@EPFL: survol des 6 derniers mois (J.-C. Berney)

GénéralitésPour aider à la mise en œuvre de la nouvelle politique CSE (Com-putational Science & Engineering) adoptée par la Direction en décembre 2010, Vittoria Rezzonico, bien connue en Faculté SB, a été engagée comme coordinatrice du CSE. Afin de mieux com-muniquer sur le sujet du CSE (ou plus généralement du HPC), une nouvelle revue annuelle spécifique, appelée Zetta, paraîtra début février 2012.Une étude sur les communications unifiées (UC) a été menée durant l’été 2011. Une enquête sur les besoins des utilisateurs a montré qu’un tiers des collaborateurs seraient prêts à renoncer à leur téléphone fixe au profit d’un smartphone & ou d’un soft-phone &. Cette enquête a également montré que l’usage de la vidéoconférence est très important, principalement dans le cadre de collaborations avec des laboratoires externes à l’EPFL. Des solu-tions de remplacement de la téléphonie actuelle basée sur une technologie désuète avec de la VOIP ont été analysées et une éva-luation des coûts sur 10 ans a été présentée.Concernant le problème de la sécurité informatique, 3 types de mesures ont été pris suite à l’exercice de piratage éthique qui a eu lieu fin 2010. Il s’agit de mesures techniques, organisationnelles et sous la forme de cours proposés aux administrateurs système et aux développeurs d’applications.Le CopilSI travaille sur la stratégie IT et développe des axiomes stra-tégiques. La transparence demandée à tous les services IT centraux permettra de développer un catalogue de services et un portefeuille de projets. Cela aidera à définir les priorités et à établir les budgets IT.Un nouveau moyen de communication a été mis en place: l’heure-DIT. Il est destiné en priorité aux nouveaux responsables infor-matique et il se présente sous la forme d’une présentation d’une heure par mois sur un sujet particulier (sécurité IT, réseau, gestion des identités,…).

RéseauLe DIT a participé à la journée mondiale IPv6 le 8 juin 2011. Dès 2012, il y aura la possibilité de raccorder des serveurs en IPv6 dans certaines salles serveur de l’EPFL.La nouvelle technologie FCoE & fait son apparition dans les data-centers.Le nombre des connexions Wifi simultanées a doublé en une an-née, la barre des 4000 connexions a été dépassée cet automne. La fiabilité du réseau est excellente, la redondance des équipements a permis d’éviter plus de 95% des pannes.

Serveurs centrauxDans le cadre de la nouvelle politique CSE, un nouveau cluster de calcul mutualisé sera acquis chaque année. Cette année, il s’agit du cluster Ariès, avec des processeurs AMD (1000 cœurs qui pour-ront être étendus jusqu’à 2000 courant 2012), qui sera mis en production en janvier 2012.Un nouveau datacenter avec une puissance de 1MW est en cours de construction dans le bâtiment INJ. Il sera mis en production en mars 2012. Son efficacité énergétique sera très bonne, car il utilisera des portes réfrigérées grâce à l’eau du lac pour climatiser les racks informatiques.Le groupe DIT-EX a développé de nouveaux outils pour gérer les datacenters (cf.page suivante).

Services de baseL’infrastructure de messagerie MS Exchange 2010 a été renou-velée. Le logiciel de distribution de logiciel Distrilog version 2 est en phase pilote au DIT, il sera mis en production pour toute l’EPFL en janvier 2012. La consommation en volume de la prestation d’impression my-Print pour les étudiants a augmenté de 24% par rapport à 2010. La journée Poséidon du 13 octobre 2011 a été un grand succès : 3038 étudiants inscrits au tirage au sort, dont 2399 de l’EPFL (+20% env.).Dès janvier 2012, les étudiants de l’EPFL pourront installer le logi-ciel Matlab sur leur ordinateur privé.

SupportPlus de 25’000 tickets ont été traités cette dernière année par l’équipe du Call Center. Celui-ci, en plus de deux collaborateurs du DIT, fait appel à plus de 30 assistants-étudiants.

KISMise à jour importante du logiciel Infoscience. Evolution de Jahia avec un relookage des outils d’édition. Interface Web 2010 pour les blogs. Nouvelle plate-forme Web pour les smartphones (cf. ci-après).

Actualités

Echos du ForumIT d’automneJean-Claude.Berney@epfl.ch, EPFL-Domaine IT, directeur du Domaine IT

28 flash informatique2828 20 DÉCEMBRE 2011 - N° 10flash informatique

Pour 2012Renouvellement de plusieurs infrastructures de stockage. Le NAS sera séparé en deux avec d’un côté le stockage individuel et de l’autre le stockage applicatif. Une solution d’authentification forte sera mise en production durant le premier semestre 2012.

Outil de gestion des salles serveur(A. Boisseau)

La décision prise en 2010 de ne considérer les différentes salles serveur de l’EPFL que comme des composantes d’un unique data-center virtuel impliquait la nécessité de disposer d’une application permettant de gérer tous les éléments hébergés dans ces diffé-rentes salles (fm.epfl.ch).Le projet de développement de cet outil de gestion des salles serveur a ainsi débuté en septembre 2010. Il s’agit d’un portail Web utilisant le même framework développé pour les autres sites backup/sanas/mynas du groupe DIT-EX. L’outil dispose des fonc-tionnalités suivantes :z gestion des données et des workflows (ajout/suppression/

modification);z gestion des rôles/droits/délégations;z reporting multi-niveaux (sites/salles/racks/faculté/…).

Avec cet outil, il est déjà possible de connaître la place disponible dans chaque rack de chaque salle serveur, la puissance électrique consommée sur chaque prise électrique, la puissance de refroi-dissement encore à disposition, la charge en kg/m2 et encore bien d’autres informations très utiles.

Les évolutions futures concerneront surtout en l’intégration avec d’autres applications comme NAGIOS, CACTI, l’inventaire EBP, un logiciel de modélisation thermique,…

cn=Open Directory @ EPFL(F. Roulet)

L’annuaire Open Directory est en exploitation depuis l’été 2010. Avec plus de 2000 Mac sur le site de l’EPFL, cet annuaire offre un potentiel important d’optimisation de la gestion de ces derniers.Deux exemples concrets d’utilisation ont été présentés:z la gestion d’un parc hétérogène de 370 Mac en Faculté SV par

Nicolas Michel;z la gestion d’un parc homogène de 50 Mac dans une salle in-

formatique pour étudiants en faculté SB par Yoann Dind.

EPFL Mobile(L. Boatto)

Le KIS a développé un portail de services pour Smartphones dis-ponible à l’adresse m.epfl.ch. Ce portail utilise le framework Jquery Mobile (Open Source). Il est multi-plateforme (iPhone, Android, Windows Phone 7+, BlackBerry 6+, etc.) et bilingue (français – anglais).Le DIT ne peut pas et ne souhaite pas développer tous les services mobiles de l’école. Il met à disposition des webmasters toutes les informations néces-saires pour que ceux-ci puissent créer leur propre site mobile (cf. atelierweb.epfl.ch/mobile). L’opération n’est pas très difficile pour tous ceux qui ont déjà des connaissances en HTML / CSS. Un template HTML / CSS est mis à disposition. n

GLOSSAIRE &FCoE (Fibre Channel over Ethernet): technique de réseau de stoc-

kage consistant à faire passer les trames du protocole Fibre Channel sur un réseau Ethernet. W

smartphone: téléphone intelligent mobile qui fournit aussi les fonctionnalités d'agenda, de consultation d'e-mails de GPS et de navigation Web; les plus courants aujourd'hui sont les iPhones d’Apple et les smartphones équipés du système Android.

softphone: logiciel installé sur un ordinateur personnel ou un smartphone qui permet de faire de la téléphonie par Internet, avec éventuellement un périphérique microphone, casque ou haut-parleur.

W = tiré de Wikipédia

Echos du ForumIT d'automne