DIENSTEN VAN 
DE EERSTE MINISTER
WETENSCHAPPELIJKE,
TECHNISCHE EN CULTURELE AANGELEGENHEDEN

	Impulsprogramma

	INFORMATICA VAN DE TOEKOMST

	(1990-1995)

	Eindverslag

Deze tekst is een onderzoeksresultaat van het Impulsprogramma "Informatica van de toekomst" , uitgevoerd op initiatief van de Belgische Staat - Diensten van de Eerste Minister - Federale diensten voor wetenschappelijke, technische en culturele aangelegenheden (DWTC). De wetenschappelijke verantwoordelijkheid over de inhoud berust volledig bij de auteurs.

	

	INHOUDSTAFEL

A. Parallelle architecturen

				G.A.  ORBAN   ...............................................................................................................	 1 
							Simulatie van modulaire neurale netwerken op onderling communicerende 
							multiprocessoren

				M. BRUYNOOGHE ............................................................................................................	 3
							Het uitbaten van parallellisme in logisch programmeren

				D. ROOSE  ....................................................................................................................	 5
							Softwarewerktuigen en algoritmen voor toepassingen met geometrisch
							parallellisme

				J.M. VAN CAMPENHOUT .................................................................................................	 7
							Software-engineering en gebruikersinterfaces voor multiprocessoren met
							gemeenschappelijk geheugen

				M. LOBELLE ...................................................................................................................	9
							PARTS : Production de logiciel temps-réel pour système parallèle par
							transformation de spécifications graphiques

				E. MILGROM ...................................................................................................................	11
							OSCAR : Concepts de systèmes d'exploitation pour architectures composées

				P. VERBAETEN ................................................................................................................	15
							XENOOPS : Een omgeving voor de uitvoering van object-georiënteerde parallelle
							programmatuur op parallelle computersystemen

				P. STEYAERT & E. DIRKX  ..................................................................................................... 	17
							Een generisch object-georiënteerd raamwerk voor multiprocessor-computer-
							systemen, toegepast op gedistribueerde programma's met de nadruk op performantie

				R. BEAUWENS ...............................................................................................................	19
							Conception et implantation d'algorithmes numériques parallèles

				P.A. DE MARNEFFE .......................................................................................................	21
							Paradigmes de conception pour algorithmes parallèles

				M. DEVILLE & C. BENOCCI ..........................................................................................................	23
							Solution numérique de haute précision des équations de transport du type
							diffusif et advectif-diffusif dans des domaines complexes par l'utilisation
							de techniques de décomposition du domaine sur des ordinateurs parallèles

B. Objectgeoriënteerde benadering

				J. LEWI  ......................................................................................................................	27
							Een omgeving voor object-gerichte analyse en ontwerp

				A. VAN LAMSWEERDE ....................................................................................................	29
							OASIS : Approche orientée-objet d'architectures avancées d'assistant logiciel

				J. PAREDAENS ................................................................................................................	31
							Een declaratief model voor een visuele interface voor ondervraging en voorstelling
							van informatie in object-georiënteerde informatiesystemen

				W. VAN DE VELDE ..................................................................................................................	33
							ADIOS : Geavanceerde ontwikkelingen in objectsystemen

C. Betrouwbaarheid en veiligheid

				P. WOLPER ...........................................................................................................................	38
							Outils de vérification temporelle

D. Dialoog mens-machine

				R. LESUISSE ..........................................................................................................................	42
							Conception d'interfaces homme-machine pour des applications de gestion hautement
							interactives

				M. RIJCKAERT  .......................................................................................................................	44
							CALLIOPE : Een methodologie voor een gebruiker en situatie aanpasbare multi- 
							media mens-machine-dialoog

				L. BOLLAERT & J.P. BRANS .........................................................................................................	46
							Mens-Machine-Mens dialoog in een groepsbesluitvormingsondersteuningssysteem

		

		

	PARALLELLE ARCHITECTUREN

	Simulatie van modulaire neurale netwerken
	op onderling communicerende multiprocessoren

	Prof. G.A. ORBAN, KUL, Lab. Neuro -en Psychofysiologie
	Campus Gasthuisberg, 3000 Leuven

Bij de start van dit project, en zelfs vandaag niet, konden in de literatuur slechts heel weinig benaderingen gevonden worden inzake de ontwikkeling van generieke simulatiesoftware voor Artificiële Neurale Netwerken (ANN's) op parallelle computers. Doorgaans wordt weinig aandacht geschonken aan de decompositie- en mappingproblemen bij de simulatie van complexe, modulaire ANN's op deze machines. Verder is er zelfs nog minder aandacht voor het verbergen van elk parallellisme en alle decompositie- en mappingproblemen voor de gebruiker, ondanks het feit dat daardoor de drempel voor het gebruik van parallelle machines aanzienlijk verlaagd zou worden.

Het algemeen oogmerk van het project was in deze leemte te voorzien en een parallelle simulatie-omgeving voor onderling communicerende multiprocessors te ontwikkelen ten behoeve van niet-computergespecialiseerde wetenschappers die modulaire ANN's ontwikkelen, bouwen en simuleren. Wij zijn daar om verschillende reden in geslaagd. 

In de eerste plaats is de ontwikkelde simulatiesoftware in staat elke decompositie- en mappingstrategie uit te voeren, wat een belangrijk gegeven is daar er geen passende strategie bestaat voor elk type van simulatieprobleem.

Ten tweede hebben we een machine-onafhankelijk ontwerp gemaakt van een simulatieomgeving voor een bepaald type van modulaire ANN's, de "Entropy Driven Artificial Neural Network" (EDANN's).

De simulatieomgeving bestaat uit drie onderdelen : 

1. een compileerprogramma voor een recentelijk ontwikkelde ANN-specificatietaal, genaamd i;
2. een splitter-programma dat de eigenlijke decompositie en mapping voor zijn rekening neemt;
3. een parallelle simulator.

Er werd aangetoond dat dit ontwerp automatisch leidt tot een generieke simulatieomgeving, d.w.z. een waarin ook andere dan EDANN-modellen geïmplementeerd kunnen worden. Dit impliceert dat de software niet alleen een simulatieomgeving is, maar tevens een programmeeromgeving voor ANN's waarin elk parallellisme transparant is, een kritisch gegeven voor niet-computergespecialiseerde wetenschappers.

Ten derde hebben we nieuwe softwaretechnieken ontwikkeld voor het opslaan van de maten van interconnecties tussen neuronen op basis van zoektabellen. Onze zoektechniek heeft slechts een geringe weerslag op de simulatietijd en helemaal geen op de complexiteit van de simulatietijd. Vandaar dat deze nieuwe techniek het connectiedilemma voorkomt.

Ten vierde hebben we ook een formeel model afgeleid dat "Locally Connected Layered Networks" (LCLN's) en parallelle machines definieert. Uitgaande van de decompositie, leidt het de optimale mappingstrategie af. Het geeft de parallelle efficiëntie en de optimaliteit weer van geometrische decompositie van LCLN's voor toroïdale rastermachines voor al dan niet gebalanceerde decomposities en voor rechthoekige en verspreide jobs op de processors. Het model werd dan gebruikt en vergeleken met geometrische decompositie op een echte machine (transputers).

Tot slot hebben wij aangetoond dat onze simulatiesoftware in staat is tot simulaties van zeer grote EDANN's die nodig zijn voor het verwerken van echte grijze schaalbeelden. Dank zij deze simulatiesoftware konden we het EDANN-concept verder ontwikkelen in veelvuldige EDANN-modules en de EDANN-modellen indelen in twee groepen voor verschillende visuele verwerkingsfuncties. 

Wij konden in het bijzonder aantonen dat :

1.	een gemeenschappelijke filterfase gebruikt kan worden voor zowel line en edge detectie en textuurscheiding; 
2.	dat line en edge detectie onderscheiden kan worden van textuurscheiding ook al ondersteunen de twee verschillende objectscheiding.

Samenvattend is het wetenschappelijk succes van het EDANN-model toe te schrijven aan onze parallelle simulatiesoftware en, omgekeerd, stimuleerde de wil om grote en modulaire EDANN's te ontwikkelen, bouwen en simuleren de ontwikkeling van nieuwe softwareprincipes voor parallelle machines en van formele modellen en instrumenten voor decompositie en mapping.

	Het uitbaten van parallellisme in logisch programmeren

	Prof. M. BRUYNOOGHE, KUL, Dep. Computerwetenschappen
	Celestijnenlaan 200 A, 3001 Heverlee

Het oorspronkelijke projectvoorstel voorzag in 11 manjaar en bevatte twee luiken : 

1. 	de ontwikkeling van abstracte interpretatie voor parallelle logische programmeertalen  
2. 	de implementatie van parallelle uitvoeringsmodellen. 
Uiteindelijk werd slechts 5.5. manjaar toegekend. Dit was onvoldoende om twee nieuwe onderzoeksrichtingen helemaal uit te bouwen.

Dankzij de parallelle financiering via de ESPRIT-projecten PEPMA ('89-'92) en ACCLAIM ('92-'95) en het voorbereidend werk in project RFO/AI/02 ('87- '91) werd een ernstige inspanning geleverd rond het tweede luik : een parallelle versie van AKL werd volledig geïmplementeerd. De samenwerking (en competitie) met SICS (Swedish Institute of Computer Science) was daarbij van groot belang. Het implementatie-ontwerp voor parAKL werd gepubliceerd in PLILP'93 en nieuwe optimalisatie in verband met de reductie van het aantal niet-deterministische promoties en copy operaties, in JICSLP'94. Dit werk werd afgerond met een doctoraat van een van de medewerkers (Remco Moolenaar) in 1995.

Het eerste luik werd grondig bijgestuurd en een beperkt deel van het budget werd gebruikt ter aanvulling van onderzoek rond abstracte interpretatie dat via andere projecten werd gefinancierd : GOA ('93-'97) en ESPRIT project PRINCE ('90-'94). Het onderzoek werd geconcentreerd op de verdere uitbouw van abstracte interpretatie voor gewone logische programma's en voor logische programma's met beperkingen. In dit onderzoek werden opmerkelijk goede resultaten behaald : niet minder dan 3 publikaties vonden hun weg naar het top tijdschrift ACM Transactions on Programming Languages And Systems (TOPLAS) :

	.	een studie rond het hergebruik van gegevensstructuren (het voorkomen van ontoegankelijke structuren die via garbage collectie moeten opgeruimd worden) die gestart werd tijdens project RFO/AI/02 ('87-'91) werd afgerond (TOPLAS, 1994).

	.	in samenwerking met M. Codish (die in ons labo verbleef van 2/1992 tot 9/1993) en met de groep van M. Hermenegildo (UPMadrid) werd een studie gemaakt over het combineren van diverse domeinen en het effect op de analysetijd en de precisie (TOPLAS 1995).

	.	in samenwerking met de groep van M. Hermenegildo werd het door onze groep ontwikkelde raamwerk voor de analyse van logische programma's uitgebreid tot een raamwerk voor logische programma's met beperkingen en werden een aantal toepassingen uitgewerkt (TOPLAS, ter perse).

Daarnaast werden resultaten gepubliceerd in talrijke conferenties en verschenen verschillende artikelen in de Journal of Logic Programming :

	.	in 1991 en 1992 telkens een artikel gebaseerd op werk tijdens RFO/AI/02.
	.	in 1995 werk over bottom-up groundness analyse van logische programma's.
	.	in 1996 (ter perse) over freeness analyse van logische programma's.

	Softwarewerktuigen en algoritmen voor
	toepassingen met geometrisch parallellisme

	Prof. D. ROOSE, KUL, Dep. Computerwetenschappen
	Celestijnenlaan 200A, 3001 Heverlee

Dit project had tot doel algoritmen en software-werktuigen te ontwikkelen voor een aantal technisch-wetenschappelijke toepassingen die zeer rekenintensief zijn en in aanmerking komen om op parallelle computers te worden uitgevoerd. De beschouwde toepassingen, zoals het oplossen van partiële differentiaalvergelijkingen, digitale beeldverwerking en het genereren van foto-realistische beelden met behulp van de computer, zijn zeer verscheiden. Toch hebben deze toepassingen een aantal belangrijke gemeenschappelijke kenmerken :

		.	de gegevens houden verband met een geometrisch domein,
		.	de hoge rekentijden worden veroorzaakt door de grote hoeveelheid gegevens die moet worden verwerkt,
		.	parallellisatie van de algoritmen kan gebeuren via een "geometrische opsplitsing" in deeldomeinen, die elk door een processor van de parallelle machine worden behandeld.

Het project werd opgesplitst in een aantal deelprojecten, waarvan we de resultaten als volgt kunnen samenvatten :

		.	Er werd een software-omgeving ontwikkeld voor de uitvoering van parallelle toepassingsprogramma's gebaseerd op geometrisch parallellisme. Deze omgeving zorgt onder meer voor een gelijkmatige werkverdeling tijdens de uitvoering van de programma's. Ze werd gebruikt voor de parallellisatie van twee oplossingsmethoden voor de Euler differentiaalvergelijkingen uit de stromingsmechanica, gebaseerd op adaptief verfijnde roosters.

		.	Verscheidene algoritmen en technieken voor het opsplitsen van roosters en het toewijzen van deelroosters aan processoren, werden uitgewerkt. Een aantal hiervan zijn ingebouwd in de hierboven vermelde software-omgeving.

		.	Nieuwe, parallelliseerbare methoden voor het oplossen van parabolische partiële differentiaalvergelijkingen, gebaseerd op golfvormrelaxatie en versnellingstechnieken voor algebraïsche stelsels vergelijkingen, werden ontwikkeld, uitgetest en theoretisch geanalyseerd. Deze methoden steunen op het gebruik van ruimte-tijd roosters.

		.	Voor diverse beeldverwerkingstaken werden parallelle algoritmen opgesteld en geanalyseerd. Nieuwe technieken voor ruisverwijdering werden ontwikkeld, gebaseerd op het gebruik van wavelets, gecombineerd met een stochastische aanpak.

		.	Nieuwe wiskundige modellen en algoritmen voor foto-realistische beeldgeneratie m.b.v. ray tracing en de radiositeitsmethode werden bestudeerd. De ray tracing methoden steunen ook op een stochastische aanpak, gebaseerd op Monte Carlo technieken.

Dit project heeft geleid tot een groot aantal publikaties : 21 artikels in internationale tijdschriften, 48 artikels in proceedings van internationale conferenties en hoofdstukken in boeken en 18 rapporten. De onderzoeksresultaten werden voorgesteld tijdens 127 voordrachten op conferenties, workshops en seminaries aan andere universiteiten. Dit onderzoek heeft geleid tot 5 doctoraten (2 nog in voorbereiding) en tot samenwerking met verscheidene buitenlandse onderzoekers en instituten, o.m. met het California Institute of Technology (USA), het SANDIA National Laboratory (USA), het Department of Computer Science van de University of Toronto (Canada), het National Institute of Health (USA) en de Technische Universiteit Wenen (Oostenrijk). Ook heeft één van de medewerkers aan het project een postdoctorale positie bekomen aan Cornell University (USA).

Tenslotte vermelden we nog dat de resultaten i.v.m. het gebruik van wavelets in beeldverwerking gebruikt en verder uitgewerkt zullen worden in een industrieel project in het kader van het Vlaams Actieprogramma Informatietechnologie.

	Software-engineering en gebruikersinterfaces
	voor multiprocessoren met gemeenschappelijk geheugen

	Prof. J.M. VAN CAMPENHOUT, Lab. voor Elektronika & Meettechniek
	Sint-Pietersnieuwstraat, 9000 Gent

Dit rapport geeft een overzicht van het onderzoek en de bereikte resultaten bij het onderzoeksproject Software-engineering en gebruikersinterfaces voor multiprocessoren. De doelstellingen van dit project situeren zich op drie vlakken :

			.	Automatische programmaverdeler : het automatisch parallelliseren van sequentiële programma's voor uitvoering op parallelle en gedistribueerde architecturen.

			.	Parallel debuggen : het ontwikkelen van technieken die het debuggen van parallelle programma's ondersteunen.

			.	Clusteranalyse : het bestuderen en implementeren van een mens-computer interface voor een dynamische grafische benadering van statistische clusteranalyse.

Op elk van deze vlakken werden belangrijke resultaten geboekt, die internationaal gepubliceerd werden. Het uitgevoerde werk gaf tevens aanleiding tot drie doctoraatsthesissen 

Automatische Programmaverdeler

			In dit deel van het onderzoek werd grondig de problematiek onderzocht van het transformeren van traditionele sequentiële FORTRAN-programma's naar een in parallel uitvoerbare vorm, initieel op multiprocessoren met gemeenschappelijk geheugen, en nadien ook op gedistribueerde architecturen.

			In een eerste fase werd de transformatie bestudeerd van FORTRAN naar een geschikte intermediaire vorm, waarin zoveel mogelijk (in principe alle) potentieel parallellisme besloten ligt. Deze vorm, een soort van uitgebreide dataflowgraaf, dient dan als basis voor de generatie van efficiënt uitvoerbare code.

			De methode die gebruikt wordt voor de effectieve codegeneratie is gebaseerd op een intelligente en aangepaste techniek van clustering, waarin de elementaire operaties in een dataflowgraaf optimaal gegroepeerd worden in taken van een voldoend hoge granulariteit. Dit is een statische manier van werkverdeling. Bij de taakgroepering wordt terdege rekening gehouden met de bijkomende kost (b.v. communicatiekost) die het gevolg is van de groepering zelf. Diverse alternatieve groeperingstechnieken werden bestudeerd en geëvalueerd.

			Nadien werd overgegaan tot een dynamische (run time) vorm van taakverdeling, gebaseerd op het meer recente draadgebaseerde uitvoeringsmodel. Er werd een implementatie gemaakt van een lichtgewicht- kern, waarvoor automatisch taken gegeneerd werden vanuit traditionele sequentiële programma's. De prestaties van deze kern werden grondig onderzocht en geoptimaliseerd, zowel experimenteel als op basis van statistische modellen en simulatiemodellen.

			In een latere fase werd ook aandacht besteed aan de rechtstreekse codetransformaties uitgevoerd op bronprogramma's, met de bedoeling de mogelijkheden van de diverse parallelle extensies aan moderne FORTRAN-varianten (DO-ALL,DO-ACROSS enz.) rechstreeks te kunnen gebruiken. Origineel werk werd verricht op diverse codetransformatietechnieken, gebaseerd op unimodulaire transformaties en op het model van "hangmatgrafen".

Parallel Debuggen

			Bij de aanvang van het project werd een studie en implementatie gemaakt van een debugger voor een parallelle implementatie van MODULA-2. Deze implementatie, die op zich een aantal innovatieve concepten bevat, werd verder in het project intensief gebruikt als substraat voor het verder onderzoek. Daarna kwam de nadruk van het onderzoek te liggen op twee domeinen : het verlagen van de intrusiviteit van observaties van programma-uitvoeringen door middel van de techniek van execution replay, en het opsporen van datatraces, een belangrijke klasse van fouten in parallelle programma's.

			Op het gebied van execution replay werd belangrijke vooruitgang geboekt in de efficiëntie van de opnametechnieken. Dankzij een zorgvuldige wiskundige modellering van parallelle uitvoeringen zijn wij erin geslaagd te komen tot een nieuwe, bewijsbaar correcte en bijzonder weinig intrusieve opnametechniek. Deze techniek stelt on in staat de uitvoering van een parallel programma dynamisch te observeren met een bijzonder lage beïnvloeding van de uitvoering zelf, en, op basis van de meetgegevens en de programmatekst, een getrouwe heruitvoering van het programma te realiseren, waarop dan met de traditionele sterk intrusieve debug-technieken verder kan gewerkt worden. 

			Bij de nieuwe techniek moet er typisch een factor 15 minder geregistreerd worden dan bij traditionele registreertechnieken. Bovendien werd aangetoond dat door optimalisatie van de techniek nog bijzonder grote verdere reducties van het registreervolume mogelijk zijn.

			Op het gebied van race detection werd, eveneens door zorgvuldige wiskundige modellering van bepaalde aspecten van parallelle uitvoering, een model van de tijd opgesteld, bruikbaar in parallelle en gedistribueerde omgevingen. Dit tijdsmodel laat ons toe op betrouwbare manier uitspraken te doen over de al dan niet gegarandeerde tijdsordening van relevante gebeurtenissen in een parallelle uitvoering (bijvoorbeeld, de toegangen tot een gemeenschappelijk data-object). Op basis van dit model werd een efficiënte techniek uitgewerkt voor het automatisch opsporen van data-races in programma's met een daartoe geschikte structuur. Ook voor deze implementatie werd innoverend onderzoek uitgevoerd, daar de ruimtelijke efficiënte van de ontwikkelde methode veel groter is dan deze van vergelijkbare, gepubliceerde methoden.

Clusteranalyse

			Bij het onderzoek naar een gebruikersinterface voor statistische clusteranalyse werden zowel hiërarchische als niet-hiërarchische clustertechnieken behandeld. In de eerste fasen van het onderzoek werden de grafische mogelijkheden van de X window-omgeving zeer grondig onderzocht, en werden een aantal data-visualisatietechnieken uitgewerkt als substraat voor het meer fundamenteel onderzoekswerk. In de zelfde periode werden tevens een drietal alternatieven voor fuzzy clustering bestudeerd.

			Deze resultaten werden in opvolgende fasen uitgediept en geconsolideerd. Er werd onderzoek verricht naar manipulaties op ultrametrische en additieve bomen, die de proximiteitsrelaties niet beïnvloeden, maar die de interpreteerbaarheid van de data door verschillende representaties grondig kunnen wijzigen. Voorts werd bestudeerd hoe de representatie van drie-dimensionele data moet aangepakt worden. Er werd o.m. bestudeerd hoe men met een "cross-eyed viewing" de illusie van dieptezicht kan realiseren op een vlak scherm.

			Nieuwere clustertechnieken werden onderzocht, zoals de techniek van "Landscape Clustering", die een belangrijke hulp kan zijn bij goede visualisaties. Ook werd een gewijzigde vorm bestudeerd van "K-means clustering", gericht op representaties met lage dimensionaliteit. Verschillende van deze theorieën werden geïmplementeerd in Andromdeda, een grafisch softwarepakket voor statistische clusteranalyse.

	PARTS : Production de logiciel temps-réel pour système parallèle par transformation
	de spécifications graphiques

	Prof. M. LOBELLE, UCL, Unité d'Informatique
	Place Sainte-Barbe 2, 1348 Louvain-La-Neuve

Le domaine de recherche du projet PARTS était la transformation automatique de la spécification graphique d'un système temps-réel en logiciel pour environnement parallèle.

Le langage de spécification graphique choisi comme point de départ du projet, appelé G++, présente les spécifications sous forme de machines à états parallèles et hiérarchiques. Ce langage ne spécifiait que le comportement du système mais pas comment réaliser des traitements c'est-à-dire comment manipuler des variables et des types. Ces manipulations constituent ce qu'on appelle l'aspect transformationnel de la spécification. Le langage prévoyait uniquement que de telles manipulations étaient encapsulées dans ce qu'il appelle des actions.

Afin de garantir la cohérence des spécifications à transformer, il a d'abord fallu définir formellement une sémantique du langage incluant les actions. La formalisation reste, en effet, la clé pour aboutir à une implémentation correcte et à une production de code cohérente. De plus, le domaine d'utilisation (essentiellement industriel) des systèmes temps-réel d'envergure impose de pouvoir contrôler et garantir tant la qualité du logiciel produit que la qualité et la pertinence de la spécification. Ces objectifs ne pouvaient être atteint sans une définition complète et formelle du langage de spécification utilisé. Cet aspect du projet s'est révélée d'une envergure significativement plus large que prévue.

Plusieurs tentatives ont été nécessaires pour prendre conscience des différentes facettes de la définition formelle de ce genre de langages :

				.	le caractère graphique du langage, et notamment la prise en compte différente de la circularité (auto-référence) au niveau syntaxe que dans les langages graphiques et textuels,
				.	les spécifications liées aux aspects temps-réel,
				.	la hiérarchie avec limitation de visibilité de certains états,
				.	le parallélisme et la concurrence,
				.	le traitement des types, variables et valeurs.

L'objectif de génération de code, et donc l'impératif de respecter une certaine notion d'exécutabilité s'ajoute aux contraintes.

La nécessité d'aboutir à une définition formelle du langage a guidé notre recherche vers les langages formels existants impliquant une ou plusieurs des facettes citées ci-dessus. Une première piste a été de s'inspirer des calculs de processus comme CCS et SCCS. Malheureusement, ce type de raisonnement mathématique mène à l'introduction d'opérateurs très puissants d'un point de vue théorique mais inadéquats en vue d'aboutir à une forme exécutable à partir de la spécification.

La définition formelle d'autres langages graphiques a alors été examinée, notamment celle des Statecharts (présentée dans les travaux de Huizing). Celle-ci nous a semblé prometteuse et plusieurs tentatives ont été menées pour adapter ces travaux au langage G++ et pour y introduire les actions (qui dans les Statecharts sont reportées dans les activity charts et ne font donc pas partie de la syntaxe). L'adaptation à la syntaxe de G++ ne pose que peu de problèmes malgré certaines différences de conventions, mais l'intégration des aspects temps-réel et l'introduction des actions dans le formalisme utilisé pour les Statecharts ne sont pas aisés.

Une exploration de la signification de la circularité exprimée directement au niveau de la syntaxe dans les langages graphiques nous a permis de mieux comprendre cette notion.

En fin de compte, un langage hybride entre Statecharts et G++a été adopté et les actions y ont été introduites dans la syntaxe même du langage. Les aspects temps-réel doivent encore y  être formellement intégrés. Quelques pistes dans cette voie ont été explorées. Le langage résultant de ce travail a été baptisé "First-Order Hierarchical Multi-State Machines". Ce langage introduit la notion d'états paramétrés par des variables.

Les recherches portant sur le langage ont abouti à la définition d'un langage formel alliant la concision des langages graphiques, les possibilités de composition des langages structurés et l'expressivité des langages dynamiques. Le langage est dérivé des Statecharts de Harel et permet des changements dynamiques de la structure hiérarchique des diagrammes.

En parallèle avec les dernières phases de la définition du langage, un prototype d'éditeur/interprète du langage a été réalisé. Celui-ci a permis d'utiliser expérimentalement le langage tout en le définissant et ainsi de s'assurer que les concepts proposés sont bien utilisables en pratique.

	OSCAR : Concepts de systèmes d'exploitation pour architectures composées

	Prof. E. MILGROM, UCL, Cellule de Liaison Recherche et Développement
	Place Sainte-Barbe 2, 1348 Louvain-La-Neuve

Le but du projet OSCAR était d'explorer les concepts et les moyens à mettre en oeuvre en vue d'une exploitation performante des architectures composées supportant simultanément plusieurs types d'applica-
tions : des programmes réguliers ainsi que des applications réparties ou parallèles constituées de plusieurs entités actives (processus). De telles architectures sont composées d'ordinateurs de types distincts et de fonctionnalités différentes connectés au moyen d'un réseau local à haut débit. Sur de telles architectures, tous les processus qui s'exécutent simultanément sont en compétition les uns avec les autres pour accéder aux ressources disponibles. C'est pourquoi l'axe prioritaire qui a été retenu pour le projet OSCAR portait sur les tâches suivantes : explorer et étudier des moyens requis pour permettre une exploitation efficace des architectures composées pour tous les types d'applications, proposer des solutions originales au problèmes mis en évidence, étudier les stratégies de gestion de ressources et de valider les solutions proposées au moyen de prototypes intégrés dans un banc d'essais.

Par souci de généralité, l'hypothèse initiale qui a été retenue pour le projet était que les moyens à mettre en oeuvre pour permettre l'exécution de divers types d'applications sur une architecture composée doivent être fournis par le système d'exploitation lui-même et non, comme c'est le cas dans d'autres approches, au moyen d'un langage de programmation spécifique et de son environnement d'exécution.

La recherche qui a été menée dans le cadre du projet concerne différents domaines scientifiques : l'un d'entre eux est relatif à l'approche orientée objets tandis que les autres aspects concernent les techniques de gestion de charge.

Systèmes d'exploitation orientés objets

			Les premiers travaux de recherche que nous avons effectués nous ont convaincus la conception d'applications en terme d'objets - plutôt qu'en terme de processus, de fichiers, etc. faciliteraient les problèmes de gestion de ressources et ce, grâce aux propriétés inhérentes aux objets. En outre, les objets pourraient contribuer à résoudre efficacement les problèmes d'hétérogénéité présents dans un environnement hétérogène.

			C'est pourquoi nous avons décidé d'explorer les diverses notions d'objets rencontrées dans le domaine des systèmes d'exploitation. De tels objets peuvent être utilisés non seulement pour structurer les applications mais également les systèmes d'exploitation.

			Dans un premier temps, la recherche a consisté à comparer les systèmes répartis orientés objets aux systèmes classiques et à étudier les caractéristiques des objets utilisés dans les systèmes orientés objets. Ensuite, nous nous sommes intéressés à la gestion des ressources dans les systèmes orientés objets : les résultats de la recherche montrent qu'il n'y a pas de différences fondamentales entre les systèmes orientés objets et les systèmes classiques du point de vue de la gestion des ressources mais que, cependant, une gestion efficace des objets entraîne des besoins spécifiques.

			Le départ de plusieurs membres de l'équipe nous a empêché de poursuivre la recherche dans cette direction et d'atteindre les objectifs opérationnels. Par conséquent, les systèmes classiques (c'est-à-dire non orientés objets) ont été retenus comme base de la recherche menée dans les autres tâches du projet.

Gestion de la charge

			Une des principales hypothèses de travail relative à cette partie de la recherche était la suivante : l'efficacité -en terme de performance - d'une application s'exécutant sur un système composé ainsi que la performance globale d'un système réparti peut être améliorée en exécutant l'application, ou des parties de l'application, sur un noeud peu chargé du système, pour autant qu'un tel noeud existe. En d'autres termes, des déséquilibres entre la charge des noeuds peut induire des pertes de performances : dans un système réparti, on tente en général d'éviter de surcharger certains noeuds alors que d'autres sont souschargés, voire même inutilisés. De nombreuses solutions ont été proposées pour pallier le problème de déséquilibre des charges en distribuant ou en redistribuant la charge globale d'un système réparti : nous regroupons ces solutions sous l'appellation collective de sous-systèmes de répartition de charge. De tels systèmes se composent de mécanismes activés au moyens de stratégies. Dans le cadre du projet OSCAR, nous nous sommes intéressés aux stratégies dynamiques de répartition de charge, qui prennent des décisions sur base d'une évaluation de l'état courant de charge du système, et aux stratégies adaptatives, qui adaptent leur comportement en fonction ce l'état courant de charge du système réparti.

			Dans cette partie de la recherche, nous nous sommes penchés sur les problèmes de gestion de la charge et nous avons démontré que des gestionnaires adaptatifs de gestion de la charge peuvent améliorer la performance d'un système réparti plus efficacement que des solutions non-adaptatives lorsque la charge du système varie, ce qui est une caractéristique des systèmes répartis retenus. Peu de travaux de recherche ont été effectués dans ce domaine précis et aucune approche systématique n'est proposée dans la littérature scientifique. Le but de la recherche était de combler ce vide et de proposer une approche systématique au problème de la gestion de la charge.

			Dans une première partie de cette tâche, nous avons jeté les bases qui permettent une compréhension en profondeur du domaine. Nous proposons un cadre général de travail dont le but est de procurer un soutien pour comprendre les stratégies de répartition de la charge, pour analyser les stratégies existantes et pour les comparer selon une approche systématique. Ce cadre de travail permet de se focaliser sur nombre de propriétés, dites qualités internes, de tout sous-systèmes de répartition de charge. Ces qualités internes sont d'un grand intérêt pour le concepteur de stratégies de répartition de charge, car elles ont un impact sur l'efficacité de ces stratégies. En effet, les négliger peut mener à des pertes de performances.

			Grâce au cadre de travail mis au point, nous avons montré qu'il était possible - et utile - de raisonner systématiquement sur la manière dont les propriétés associées à ces qualités internes peuvent être satisfaites dans une stratégie donnée. En outre, nous avons mis en évidence des liens directs entre des critères de qualité et des choix qui doivent être faits lors de la conception d'une nouvelle stratégie de répartition de charge. Nous avons donc défini une nouvelle méthode, intégrée au cadre de travail que nous avons défini, qui s'est révélée être un soutien efficace pour concevoir de nouvelles stratégies de manière méthodique.

			Afin d'évaluer l'intérêt de l'adaptabilité, il nous fallait disposer d'un ensemble de stratégies représentatives du domaine et qui pourraient être exploitées utilement par un système adaptatif de gestion de la charge. Nous avons décidé de ne pas utiliser des stratégies existantes parce que notre recherche et les analyses de stratégies que nous avons faites ont révélé que ces stratégies présentaient trop de particularités, tout en ignorant certaines propriétés internes majeures des stratégies. Nous avons donc conçu et implémenté  - au moyen du cadre de travail et de la méthode associée - un jeu de stratégies intéressantes à utiliser dans le contexte adaptatif et représentatives des principales classes de stratégies dynamiques.

			Dès le début du projet, il avait été décidé de favoriser les approches empiriques. Il nous fallait donc une plate-forme afin de mesurer les performances obtenues au moyen de différentes stratégies de répartition de charge et de les comparer. Nous avons décidé d'étudier à cette fin des plate-formes logicielles basées sur la technique des micro-noyaux, qui étaient à l'époque à la pointe de la recherche dans le domaine : leur flexibilité découlant de leur conception et de leur architecture leur conférait un atout majeur. Les deux hypothèses de base sur lesquelles le reste du travail a reposé étaient : (1) un système d'exploitation réparti de type UNIX procure un environnement adéquat pour construire un banc d'essais; (2) la migration de processus est un mécanisme de base nécessaire pour réaliser l'équilibrage de charge. Après une étude approfondie, nous avons choisi d'utiliser le système d'exploitation MACH, de OSF; ce système d'exploitation a ensuite été modifié pour supporter la migration des processus UNIX et adapté en banc d'essais.

			Dans les dernières tâches relatives à cette partie de la recherche, nous nous sommes intéressés aux problèmes d'efficacités. Au moyen d'une approche empirique basée sur des techniques de prise de mesures ainsi que sur une approche statistique, nous avons construit des modèles polynomiaux qui permettent d'évaluer la performance d'un système réparti soumis à une stratégie donnée de répartition de charge. Ce travail a été fait pour chacune des nouvelles stratégies conçues dans une phase antérieure du projet et intégrées au banc d'essais. La méthode que nous avons utilisée contraste avec les approches, généralement utilisées dans le domaine, qui mènent à des résultats moins généraux et peu fiables.

			Nous avons exploité ces modèles pour prédire les améliorations de performances qui peuvent être obtenues pour les différentes stratégies sur lesquelles l'étude portait et pour déterminer les conditions sous lesquelles la performance d'un système réparti peut être maximisée. De tels modèles fournissent un support adéquat pour évaluer les intérêts respectifs de certaines décisions prises lors de la conception de stratégies de répartition de charge mais également pour déterminer les valeurs qui doivent être affectées aux paramètres de ces stratégies pour obtenir la meilleure amélioration possible de performance. Les résultats que nous avons obtenus nous ont permis de montrer qu'une stratégie qui adapte son comportement en fonction de l'état du système sous-jacent est en effet plus efficace qu'une stratégie non adaptative lorsque la charge du système varie.

	XENOOPS : Een omgeving voor de uitvoering van object-georiënteerde
	parallelle programmatuur op parallelle computersystemen 

	Prof. P. VERBAETEN, KUL, Dep. Computerwetenschappen
	Celestijnenlaan 200A, 3001 Heverlee

XENOOPS staat voor een Execution Environment for Object-Oriented Parallel Software. Het hoofddoel van dit project was de studie van uitvoeringsomgevingen voor parallelle toepassingen op parallelle computers met gespreid geheugen. Dergelijke omgeving werd vervolgens ontworpen, waarna een prototype gerealiseerd werd. In het XENOOPS project hebben we geprobeerd de voordelen van de object-gerichte benadering (die steeds meer bijval geniet) te benutten bij de ontwikkeling van parallelle toepassingen, alsook en vooral bij de ontwikkeling van applicatie-specifieke uitvoeringsomgevingen voor dergelijke toepassingen.

Een uitvoeringsomgeving kan opgebouwd zijn uit diverse subsystemen die elk een specifieke en complementaire rol spelen in de systeemprogrammatuur. Zo kan men bijvoorbeeld subsystemen beschouwen voor geheugenbeheer, voor belastingsspreiding, of subsystemen ter ondersteuning van foutbestendigheid. De centrale studie in het XENOOPS project was gericht op ondersteuning voor belastingsspreiding. We hebben een modulaire architectuur ontwikkeld waarbinnen subsystemen voor belastingsspreiding samengevoegd kunnen worden met toepassingen die in een onafhankelijk ontwikkelingsproces gerealiseerd werden.

De onderzoeksactiviteiten die we uitgevoerd hebben binnen het XENOOPS-project kunnen in vier groepen ondergebracht worden :

		1.			De studie van object-gebaseerde technologie, en de impact van deze technologie op de ontwikkeling van applicaties enerzijds, en van systeemprogrammatuur anderzijds. Deze studie was zeer breed, en raakt aan object-gebaseerde programmeertalen, en object-gebaseerde technologie die gelijktijdigheid (concurrency) en distributie ondersteunt.
		2.			De studie van programmeeromgevingen voor parallelle toepassingen. In dit gedeelte hebben we bestaande omgevingen bestudeerd, zowel produkten die commercieel ondersteund worden, alsook populaire prototypes uit de onderzoekswereld.
		3.			De studie van architecturen voor systeemprogrammatuur. Hierbij ging er aandacht naar besturingssystemen, naar uitvoeringsomgevingen en naar de "run time" van programmeertalen.
		4.			De studie van subsystemen voor belastingsspreiding. Hierbij hebben we zowel aandacht besteed aan algoritmen (de strategie voor belastingsspreiding) als aan mechanismen. Bovendien werd de integratie van mechanismen in een basissysteem voor objectondersteuning uitvoering behandeld.

De vier hogervermelde activiteiten werden gelijktijdig uitgevoerd. De interactie tussen deze vier activiteiten heeft onze kennis en inzichten verbeterd omtrent de interactie en 

		.			samenhang tussen applicatieprogrammatuur (niet enkel parallelle toepassingen);
		.			systeemprogrammatuur (niet enkel parallelle systemen);
		.			omgevingen die applicatie en systeem integreren en applicatie-specifieke subsystemen (niet enkel belastingsspreiders).

Onze onderzoekservaringen uit het XENOOPS-project liggen mee aan de basis van een nieuwe benadering voor de ontwikkeling van systeemprogrammatuur. Wij zullen in de nabije toekomst andere  toepassingsdomeinen bestuderen vanuit een gelijkaardige invalshoek. Uiteindelijk zal dergelijk onderzoek de basis  vormen voor generische technieken en architecturen die het ontwikkelingsproces en de intrinsieke  kwaliteit van systeemprogrammatuur aanzienlijk kunnen verbeteren.

	Een generisch objectgeoriënteerd raamwerk voor multiprocessor computer systemen, toegepast op gedistribueerde programma's met de nadruk op performantie

	De Heer P. STEYAERT, VUB, Dep. Artificiële Intelligentie
	Pleinlaan 2, 1050  Brussel
	De Heer E. DIRKX, VUB, Dep. Info
	Pleinlaan 2, 1050 Brussel

Het doel van de bijdrage van INFO was de experimentele evaluatie van de ontwikkelde programmeeromgeving en methode op een spectrum van parallelle architekturen. Als modelapplikatie werd diskrete simulatie genomen omdat dit een gebied is met reële behoeften op het vlak van rekensnelheid en omdat het de basis is voor een groot aantal toepassingen zoals bv. operationeel onderzoek, de studie van computer- en telekommunikatie netwerken, de simulatie en foutanalyse van (digitale) elektronische schakelingen etc. M.b.t. software engineering is dit probleem uitermate geschikt omdat het representatief is voor de problematiek van de programmatie en het gebruik van parallelle computerarchitekturen in andere toepassingsdomeinen : het hele spectrum van fine grain tot coarse grain algoritmen en machines kan (en werd) onderzocht worden zodat de software en machineparameters en karakteristieken in dit "laboratorium" op een gekontroleerde wijze geanalyseerd (en evt. geoptimizeerd) kunnen worden.

Het resultaat van dit werk is diep inzicht in het run-time gedrag van een gamma parallelle machines gaande van "clusters" tot architekturen met dedicated interkonnektienetwerken. In de context van de studie van zeer fine grain algorithmen werd een custom (weliswaar konfigureerbaar en programmeerbaar door de eindgebruiker) computing node ontwikkeld en geïmplementeerd op basis van "field programmable gate arrays". Alhoewel oorspronkelijk de versnelling van kritische operaties het doel was (en nog is) heeft deze komponent bewezen over veel meer mogelijkheden te beschikken, wat geleid heeft tot a-priori onverwachte mogelijkheden en resultaten.

De brede basis-know-how op het vlak van zowel parallelle computers als parallelle algorithmen leidde (en leidt nog steeds) op zijn beurt tot een behoefte aan software tools voor dit soort machines. Het is duidelijk dat dit de sleutel is tot het efficiënt en effectief gebruik van parallelle computer systemen door niet specialisten.

Er moet opgemerkt worden dat gedurende de loop van dit projekt de hardware en (low-level) systeemprogrammatuur van parallelle computers een opmerkelijke vooruitgang hebben gemaakt. De voornaamste reden hiervoor is de erkenning in industriële en niet-computer science onderzoeksomgevingen dat er een fundamentele (al dan niet economische) beperking zit op de schaalbaarheid van de rekenkracht van klassieke (Von Neumann) computerarchitecturen en dat parallelle computers daar eigenlijk de enige oplossing voor zijn. Daar waar mogelijk werden (en worden) de resultaten van deze evolutie gebruikt. Een belangrijk besluit op dit vlak is echter dat het zeer onwaarschijnlijk is dat de evolutieve strategie die gevolgd wordt door zowel suppliers als consumers van general purpose parallelle machines zal leiden tot abstracties (en hun implementatie in de vorm van software tools) en methoden die toelaten dit nieuw soort machine effectief en efficiënt te gebruiken. General purpose parallelle computers voegen inderdaad een nieuwe dimensie (kommunikatie) toe aan zowel hardware, systeem- als applikatiesoftware waaraan van in het begin (minstens) evenveel aandacht moet besteed worden als aan de meer klassieke dimensies van processing en storage. Dit was (en is meer dan ooit) de justifikatie van de studie (en implementatie) van nieuwe paradigma's voor het ontwerp, de implementatie en optimizatie van parallelle software zoals bewezen werd in het software engineering deel van dit projekt.
Er kan ook gesteld worden dat de implementatie van een voorbeeld (simulatie van een Asychronous Transfer Mode schakelaar) op een dedicated parallelle machine industriële interesse en toepassingen tot gevolg heeft gehad (en nog steeds heeft), aangezien dit prototype nog altijd operationeel is voor de evaluatie van implementatie-alternatieven voor dit type telekommunikatieschakelaar. Het blijkt dat moderne kommerciële parallelle systemen niet in de buurt komen (en zullen komen in de nabije toekomst) van de prijs/prestatieverhouding van onze implementatie.

Het doel van de bijdrage van dienst PROG was de ontwikkeling van een programmeeromgeving en raamwerk voor de programmatuur van parallelle architecturen. Gezien de toegekende middelen en de trage evolutie op internationaal vlak van de beschikbare technologie werden na een grondige evaluatie de initiële ambities tot meer realistische proporties herleid. Alhoewel een belangrijk deel van het onderzoek gewijd werd (en wordt) aan het aspect parallellisme richtte het project zich voornamelijk op de fundamenten van objectgerichte (OO) software ontwerp en technieken en methoden voor de ontwikkeling en toepassingen van herbruikbare of aanpasbare software. 

De verschillende deelaspecten die aan bod kwamen omvatten de formele en semantische grondslagen van objectgerichtheid, de ontwikkeling van nieuwe OO-concepten en methoden, implementatietechnieken voor objectgerichte (parallelle) programmeertalen, objectgerichte ontwikkelingsomgevingen en analyse en typering van objectgerichte programma's. De verschillende karakteristieken van objectgerichtheid zoals encapsulatie, polymorfisme en overerving maken objectgerichte software uitermate geschikt voor "software reuse". We kunnen hier een onderscheid maken in hergebruik van software die niet specifiek ontwikkeld is voor hergebruik en het ontwikkelen van software met het specifieke doel van herbruikbaarheid. We noemen dit laatste aanpasbare of generische software. In elk van de hierboven opgenoemde deeldomeinen werd sterk de nadruk gelegd op methoden en technieken voor het maken van aanpasbare software. Bijvoorbeeld bij de ontwikkeling van nieuwe OO-overervingsconcepten werd een modulaire overervingstechniek onderzocht die toelaat objecten samen te stellen uit voorgedefinieerde modules. Tegelijk werden er richtlijnen (of kwaliteitseisen) onderzocht om te garanderen dat ontwikkelde modules maximaal kunnen herbruikt worden. Of, bij het onderzoek naar OO-ontwikkelingsomgevingen werd nagegaan hoe de ontwikkelingsomgeving kan worden aangepast voor software hergebruik. De voornaamste toepassingsdomeinen van dit alles zijn "open hypertext systemen", aanpasbare "user interface builders", aanpasbare programmeeromgevingen, actieve objectservers en computer ondersteund groepswerk. Vooral in dit laatste toepassingsdomein wordt sterk gebruik gemaakt van de inzichten bekomen uit het bestuderen van objectgericht parallellisme.

Recente resultaten situeren zich in het theoretische domein - met formele, algebraïsche modellen voor objectgerichte talen- die uitmonden in software artefacten waarmee geëxperimenteerd wordt. Langs de andere kant werden fundamentele bijdragen geleverd tot het gebruik van OO-technologie in industriële toepassingen. Zo werden de resultaten van het project in belangrijke mate gebruikt bij de constructie van een geavanceerd programma-planningssysteem bij VTM en in de specificatie van een groepswerk-systeem bij de ARGO. Daarbij staat de software-technologie centraal, maar worden belangrijke bruggen gelegd naar andere disciplines zoals telecommunicatie en multi-media.

	Conception et implantation d'algorithmes numériques parallèles

	Prof. R. BEAUWENS, ULB, Fac. des Sciences Appliquées
	Avenue F.D. Roosevelt 50, 1050 Bruxelles

L'objectif du projet "Algorithmes numériques parallèles" (Contrat IT/IF/14) était la conception, le développement et l'implantation d'algorithmes numériques parallèles d'intérêt général dans les applications industrielles.

La difficulté majeure des grosses applications industrielles, c'est-à-dire celles qui motivent le recours aux architectures parallèles, réside dans la mise au point de solveurs linéaires efficaces et plus spécifiquement de solveurs linéaires itératifs efficaces et les difficultés de parallélisation de ces solveurs sont à localiser au niveau de la parallélisation du préconditionnement.

Il s'agit là de la parallélisation d'un solveur linéaire direct mais approché. Il est souhaitable que cette approximation soit bonne (entraînant un moindre nombre d'itérations) mais d'exécution rapide (entraînant un moindre coût par itération).

C'est principalement à ce problème central que nous nous sommes attaqués, tout en ne négligeant pas les aspects auxiliaires tels que la discrétisation ou les simulations du type Monte Carlo, dont nous ne parlons que peu dans ce rapport parce que ces aspects n'ont pas soulevé de gros problèmes de parallélisation.

La parallélisation repose sur la définition d'un ordre de numérotation des inconnues par niveaux tel que les inconnues d'un même niveau n'aient pas de connexions entre elles et puissent donc être traitées en parallèle.

Mais l'ordre de numérotation choisi peut avoir une influence importante sur la précision (c'est-à-dire l'efficacité) du préconditionneur. Pas toujours cependant : dans le cas des méthodes de Jacobi ou de Schwarz, cet ordre n'a pas d'influence et ces méthodes se prêtent bien à une parallélisation efficace et peuvent dès lors servir de référence. (La méthode de Jacobi est très peu coûteuse mais très peu efficace; la méthode de Schwarz est, moyennant quelques perfectionnements, très efficace mais très coûteuse).

Il est donc important d'étudier l'influence de l'ordre sur le conditionnement (pour des ordres à degré de parallélisme élevé). Nous avons abouti à de nombreux résultats dans ce domaine par la définition d'ordres et de stratégies de conditionnement tels que les ordres consistants avec perturbations non diagonales, les ordres S/P consistants, les ordres de Kutcherov Makarov et les ordres du type rouge-noir récursif. Non seulement ces ordres sont à degré de parallélisme élevé mais ils améliorent en outre l'efficacité du préconditionnement.

Nous n'avons pas eu de succès lors de l'implantation de ces stratégies d'ordonnancement sur Connection Machine. Cependant, nous avons récemment appris que d'autres groupes avaient réussi à en tirer parti sur des architectures à mémoire partagée. La conclusion à en tirer est que, sur les architectures parallèles à mémoire distribuées actuellement disponibles, il ne suffit pas de mettre au point des ordres à degré de parallélisme élevé. Il faut en outre rencontrer le problème de la lenteur des communications sur ces architectures. Il faut donc minimiser les communications.

Ce deuxième problème représente une limitation importante imposée par les architectures actuelles et l'on ne saurait trop insister sur l'importance qu'il y a à progresser dans ce domaine, de façon à pouvoir utiliser des algorithmes plus efficaces.

Nous avons attaqué ce deuxième problème par l'emploi de partitionnements et de recouvrements définis soit géométriquement (décomposition de domaine), soit algébriquement (détermination de séparateurs dans les graphes matriciels) et par le développement d'une implantation parallèle spécifique des méthodes de factorisation approchée utilisant des recouvrements minimaux et n'exigeant que légèrement plus de communications que la méthode de Jacobi moins en général que celle de Schwarz, qui utilise des recouvrements plus importants) .

L'emploi des partitionnements a été développé par S. BOUSRI pour des applications industrielles en théorie des réacteurs nucléaires et par M.M. MAGOLU pour la parallélisation des méthodes de factorisation par blocs . Dans les deux cas, il s'agit d'implantations MIMD sur grappe IBM à l'ULB et sur GCel de Parsytec à l'IC3A. Les gains relevés par BOUSRI sont particulièrement élevés, conduisant typiquement à des "speedups" de l'ordre de 16 pour 36 processeurs. Les gains relevés par MAGOLU sont moins spectaculaires mais restent très intéressants, de l'ordre de 4 pour 32 processeurs.

L'emploi des recouvrements a été développé par Y. NOTAY et Z. OULD AMAR pour la parallélisation des méthodes de factorisation ponctuelles. Y. NOTAY a inventé une technique d'implantation originale, qui, comme nous l'avons déjà mentionné, ne requiert que légèrement plus de communications que la méthode de Jacobi et l'a appliquée aux architectures MIMD. Il a typiquement observé  des speedups de l'ordre de 5 à 200 ou plus pour des grilles de 8 à 512 processeurs (sur GCel) tandis que la comparaison, plus sévère, avec le préconditionnement de Jacobi, montre des gains de temps CPU d'un facteur pouvant atteindre 10 pour les gros problèmes.

Z. OULD AMAR a adapté cette technique d'implantation aux architectures SIMD et a relevé des gains en temps CPU d'un facteur pouvant atteindre 3 par rapport au préconditionnement de Jacobi sur Connection Machine. A notre connaissance, c'est la première implantation qui réussit à faire nettement mieux que le préconditionnement de Jacobi sur Connection Machine sans recourir à la solution de problèmes hautement anisotropes ou fortement discontinus (qui handicapent la méthode de Jacobi).

Au cours de ces recherches, nous avons développé plusieurs logiciels dont une partie est déjà mise en accès public et accessible par ftp anonyme. Nous avons également développé notre collaboration industrielle et nos contacts internationaux. Sur ce dernier plan, notre équipe s'est acquis une position internationale reconnue.

	Paradigmes de conception pour algorithmes parallèles

	Prof. P.A. De MARNEFFE, ULG, Institut d'Electricité Montefiore
	Sart Tilman B28, 4000 Liège

	Le but du projet était de déterminer un ensemble de paradigmes de conception pour les algorithmes parallèles: paradigmes exploitables pour la conception de programmes parallèles dans les domaines d'application de l'ingénierie.  Pour parvenir à déterminer ces paradigmes, une étude des méthodes de conception des algorithmes séquentiels et parallèles a été menée en examinant le domaine de la géométrie algorithmique, la mise en oeuvre de ces méthodes dans le cadre des architectures des machines parallèles a été étudiée, les paradigmes ont été validés avec succès en testant leurs applications dans le développement de programmes de calcul des éléments finis sur machines parallèles.

Les activités de recherche du projet ont associé deux services de la Faculté des Sciences Appliquées de l’Université de Liège : le service d'Informatique (algorithmique), orienté vers l'étude et la définition des méthodes de développement des algorithmes, et le Laboratoire des Techniques Aéronautiques et Spatiales, impliqué régulièrement dans la conception et le développement de méthodes de calcul avancées en ingénierie.

Maîtriser le développement des algorithmes pour l'utilisation la plus efficace des nouveaux équipements parallèles est un défi important pour les sciences appliquées. Pour conserver la possibilité de pratiquer efficacement la conception en ingénierie, l'utilisation d'équipements parallèles s'impose de plus en plus :  les réseaux de stations de travail permettent de regrouper une importante puissance de calcul, les multiprocesseurs à mémoire distribuée permettent d'envisager de s'attaquer à la résolution de problèmes de très grande  taille, trop grande pour un traitement sur un monoprocesseur. La difficulté majeure provient de la conception d’algorithmes parallèles qui peuvent exploiter efficacement une architecture parallèle et justifier l’accroissement de matériel que cette architecture implique.

L’étude des paradigmes de conception des algorithmes séquentiels a mis en évidence la décomposition d’un problème en problèmes plus simples par la recherche de relations de récurrence. En général, les algorithmes séquentiels performants exploitent des structures de données élaborées qui permettent d’appliquer une relation de récurrence résolvant le problème en un nombre réduit d’étapes. Cette forme d’algorithme est plus difficile à paralléliser qu’un algorithme basé sur une récurrence dans la division des données où la solution du problème est obtenue par une phase de regroupement des résultats partiels fournis par le traitement de chaque sous‑ensemble des données. 

La conception d'un algorithme parallèle implique un découpage à la fois des opérations et des données, de manière à déterminer un ensemble de "sous‑algorithmes" qui sont associés aux différentes unités matérielles qui composent l'ordinateur parallèle. Pour répondre au critère d'utilisation effective du matériel, il importe que la décomposition assure une répartition équitable de la charge de travail des différents sous‑algorithmes. L’étude des architectures parallèles a montré l’influence profonde de l’équipement sur la structure des algorithmes développés, et la difficulté de définir des concepts transposables d’un équipement à l’autre. 

L’étude comparative d’algorithmes séquentiels et d’algorithmes parallèles en géométrie algorithmique, menée en tenant compte des contraintes des équipements parallèles disponibles, a permis de rassembler un ensemble de règles de parallélisation qui sont directement exploitables dans le contexte des machines réelles : machines à mémoire partagée, disposant d'un nombre relativement modeste de processeurs, fonctionnant en mode MIMD (flots d'instructions multiples); ces règles sont également exploitables dans le contexte des équipements multiprocesseurs à mémoire distribuée. Ces règles permettent de développer une version parallèle à partir d’une version séquentielle efficace.

 
Les règles de parallélisation ont pu être complétées et affinées en concevant des algorithmes parallèles dans le domaine des éléments finis. Les algorithmes développés traitent de la résolution des systèmes linéaires de très grandes dimensions par les méthodes directes, itératives et semi‑itératives. Des résultats importants et pratiquement applicables ont été obtenus dans ce domaine. La décomposition en sous‑domaines et le problème aux valeurs propres ont été également étudiés.

Une librairie portable fournissant un ensemble minimum de fonctionnalités pour la mise en oeuvre du parallélisme a été définie. Cette librairie implémente des opérations de base de la parallélisation et permet au concepteur de ne pas devoir rentrer dans les détails d’utilisation des librairies propres à chaque constructeur. La librairie permet également de faire exécuter sur un équipement multiprocesseur à mémoire partagée un algorithme conçu pour une architecture à mémoire distribuée.

Les règles de parallélisation forment un ensemble cohérent dont la compréhension permet d'aborder efficacement le développement d'algorithmes parallèles ou la parallélisation d'algorithmes séquentiels. En appliquant ces paradigmes de parallélisation, nous avons pu mener correctement à bien des opérations de parallélisation de codes "industriels", c.‑à‑d. avec toutes les particularités d'un logiciel appliqué industriel, (dans le cadre d’un contrat Esprit Europort/Sammi).

 

	Solution numérique de haute précision des équations de transport du type diffusif et advectif-diffusif dans des domaines complexes par l'utilisation de techniques
	de décomposition du domaine sur des ordinateurs parallèles

	Mr. C. BENOCCI, VKI, Chaussée de Waterloo 72, 1640 Rhode-St-Genèse

D'importantes améliorations ont été apportées au cours des dix dernières années dans l'utilisation des méthodes spectrales pour résoudre des systèmes d'équations aux dérivées partielles dans le cas de géométries complexes. Les méthodes par décomposition de domaines, sont, à l'opposé des méthodes à domaine unique, particulièrement bien adaptées à la résolution de problèmes de dynamique des fluides tels que l'écoulement autour d'obstacles non-profilés. C'est dans ce contexte que ce travail traite de développement d'un algorithme spectral multi-domaines permettant la résolution des équations de Navier-Stokes en régime incompressible. Nous croyons que cette approche permet, non seulement de conserver la précision associée aux méthodes spectrales appliquées à des géométries complexes, mais également de réduire de manière drastique les coûts de calcul. Cette réduction peut être obtenue de deux manières complémentaires. D'une part, une découpe judicieuse du domaine de calcul permet d'affiner au mieux la précision dans les zones où la frontière ou la solution manquent de régularité et d'avoir recours à la "convergence spectrale" dans les régions aux caractéristiques plus régulières, où moins de noeuds sont utilisés. D'autre part, le développement d'un algorithme multi-domaines est particulièrement adapté aux architectures de calculateurs à mémoire distribuée.

Les équations de Navier-Stokes, permettant la modélisation de l'écoulement instationnaire et incompressible d'un fluide visqueux, peuvent être discrétisées par rapport au temps de diverses manières. Un schéma continu de correction de pression a été utilisé dans ce travail. Cette méthode conduit à différents "blocs" linéaires ou linéarisés devant être résolus à chaque pas temporel. De manière plus précise, si la contribution convective est traitée d'une façon explicite, on ne devra résoudre que des problèmes de type Helmholtz tandis qu'un traitement implicite du pas prédicteur linéarisé mène à un système d'équations scalaires de convection-diffusion et à une équation de Poisson pour la pression. De manière à augmenter l'efficacité des procédures itératives utilisées dans chaque bloc, il est important de concevoir les préconditionneurs les mieux adaptés. Une série d'outils performants à été conçue à cet effet au moyen de préconditionneurs basés sur des méthodes de discrétisation d'ordre inférieur. De plus, un nouveau préconditionneur pour des problèmes de convection-diffusion est proposé.
Toutes les méthodes développées ont été validées de manière exhaustive par des comparaisons directes avec des cas-test de référence.

	

	 Prof. M. DEVILLE, UCL, Unité de Mécanique Appliquée
	Bâtiment Simon Stévin, Place du Levant 2, 1348  Louvain-La-Neuve

Cette recherche se donne comme ambition de montrer que la simulation numérique des écoulements de fluides instationnaires et incompressibles, décrits par les équations tridimensionnelles de Navier-Stokes, peut être traitée de manière efficace par un programme de calcul basé sur une discrétisation spatiale de type spectral. Cette efficacité repose largement sur de nombreuses améliorations apportées dans le domaine des méthodes spectrales ces dix dernières années tant au niveau de la théorie que des algorithmes et des  coûts de calcul. Par conséquent, le champ d'applications des méthodes spectrales ne se limite plus aux géométries simples, mais s'étend aux situations complexes. En particulier, la méthode des éléments spectraux est devenue très populaire parce qu'elle combine les avantages de la méthode des éléments finis avec la "capacité spectrale" de réduire le nombre de degrés de liberté pour atteindre une précision fixée. En outre, elle incorpore naturellement l'idée de décomposition en sous-domaines, notion intimement liée au parallélisme et donc à la réduction des coûts de calcul. Ceci est la clé pour une implémentation efficace sur les ordinateurs les plus puissants de notre époque constitués presque sans exception de processeurs parallèles à mémoire répartie.

Les équations continues de Navier-Stokes décrivent l'évolution de la vitesse et de la pression d'un écoulement de fluide dans un domaine matériel; la méthode des éléments spectraux les réduit à un ensemble d'équations discrètes. Cette technique de discrétisation est fiable et bien établie, et constitue le point de départ de ce travail. Cependant, le développement d'algorithmes rapides pour la résolution du système discret est un défi majeur. A cette fin, on étudiera le découplage des composantes de vitesse et de pression en comparant des algorithmes existants et originaux. Les méthodes itératives se sont avérées très appropriées afin de mener à bien la résolution des systèmes discrets découplés. Toutefois, des techniques adéquates de préconditionnement ont été développées afin d'assurer un taux de convergence acceptable des méthodes itératives. Pour ce faire, un nombre de préconditionneurs des opérateurs de vitesse et de pression ont été proposés et validés. Ces techniques ont toutes en commun des solutions rapides et locales à un élément et une stratégie de traitement d'interfaces.
Un autre sujet important abordé dans ce travail est la discrétisation temporelle des équations instationnaires. La manière classique est de choisir un schéma implicite pour les termes linéaires et un schéma explicite pour les termes convectifs. La mise au point de telles méthodes qui doivent être à la fois stables et d'une précision d'ordre élevé n'est pas évidente. En fait, les concepts de stabilité et de précision sont liés: plus le schéma temporel est stable, plus le pas de temps admissible est grand. Du point de vue de la rapidité de calcul, il est souhaitable que l'évolution dans le temps se fasse avec un pas maximal. Un niveau de précision acceptable est alors obtenu uniquement par une méthode d'ordre élevé.

Le développement d'un programme de calcul de haute performance demande non seulement des méthodes numériques parallélisables, mais aussi des algorithmes rapides qui impliquent une communication entre processeurs la plus réduite possible. L'implémentation parallèle est facilitée par l'utilisation de méthodes itératives, notamment en présence de préconditionneurs diagonaux par bloc. On montrera à travers l'analyse et l'optimisation des algorithmes de communication, que les plus performants sont souvent exclusifs pour certains types d'architecture de machine. Cette spécificité doit être mise en regard avec la perte de portabilité du programme de calcul.

	OBJECTGEORIËNTEERDE BENADERING

	Een omgeving voor objectgerichte analyse en ontwerp

	Prof. J. LEWI, KUL, Dep. Computerwetenschappen
	Celestijnenlaan, 200 A - 3001 Heverlee

Het objectgeoriënteerde paradigma heeft in de huidige stand van zaken een dermate rijpheid bereikt dat het de meest populaire en meest effectieve hedendaagse aanpak voor de produktie van software van hoge kwaliteit is geworden. Met hun wortels in programmeertalen zoals Smalltalk, zijn de objectgeoriënteerde principes vooreerst toegepast of het implementatieniveau. Om structurele continuïteit te bekomen, hebben onderzoekers over de hele wereld nagegaan hoe deze objectgeoriënteerde principes ook gedurende de vroegere fasen van de software-levenscyclus toegepast kunnen worden. Dit resulteerde in een groot aantal methoden bepaalde aspecten van de objectgeoriënteerde aanpak meer benadrukken dan andere, kunnen we toch een onderscheid maken tussen structurele methoden enerzijds, waar relaties tussen objecten de drijvende kracht zijn, en methoden waarin het gedrag van klassen, in de vorm van boodschappen tussen objecten, een centrale rol spelen, anderzijds.

In dit onderzoeksproject is de EROOS-methode voor objectgeoriënteerde analyse en ontwerp, die ontwikkeld is aan de KULeuven, toegepast op een aantal gevalstudies. Tegelijkertijd is een prototype van een ontwikkelomgeving gerealiseerd, die deze methode ondersteunt. EROOS is een structurele methode, waarin naast relaties en attributen ook beperkingen, uitgedrukt in een beperkte vorm van eerste-orde- logica, sleutelconcepten zijn. EROOS toepassen op een aantal gevalstudies van kleinere schaal in verschillende toepassingsdomeinen, heeft als resultaat dat de basisconcepten uit de analyse-en ontwerpfasen  tegelijkertijd verfijnd en uitgebreid zijn. Zo zijn de klassen uitgebreid met een archief, waarin alle reeds vernietigde objecten nog steeds beschikbaar zijn, om tegemoet te komen aan verschillende vormen van statistieken welke typisch gevonden worden in informatiesystemen. Gevalstudies in dit domein hebben ook geleid tot een precieze en formele definitie van de generalisatie- en specialisatierelatie tussen klassen. De analyse van kleine gevalstudies in het domein van reële-tijd-systemen, zoals verkeerslichten, luchtverversing- en liftcontrolesystemen, gaven aanleiding tot uitbreiding van de zeggingskracht van de beperkingen om tijdsaspecten uit te drukken. Een belangrijk deel van het project was gewijd aan de toepassing van de principes van objectgeoriënteerde analyse op een echte industriële gevalstudie. Daarvoor werd de werking van een bepaald apparaat in de telecommunicatiewereld, een flexibele multiplexer genoemd, in alle detail geanalyseerd en gespecificeerd. De EROOS-methode bleek op dat moment al voldoende stabiel om alle aspecten van de gegeven multiplexer op een elegante wijze te specificeren. De resulterende specificatie was echter te complex om in zijn geheel begrepen te worden. Samenvattend kunnen we stellen dat de principes van objectgeoriënteerde analyse met succes kunnen toegepast worden op applicaties van kleine schaal. Er zijn echter nog steeds bijkomende concepten nodig om de complexiteit van problemen op grotere schaal te beheersen. Op dit moment zijn enkele, nog onvolwassen concepten voorgesteld in verschillende methoden om toepassingen op verschillende niveaus van abstractie te specificeren.

Zoals voorheen al vermeld, behoorde de ontwikkeling van een prototypeomgeving die de EROOS-methode voor objectgeoriënteerde analyse en ontwerp ondersteunt, ook tot de doelstellingen van dit onderzoeksproject. Naast aspecten van grafische gebruikersinterface, vormen ook de problemen om  documenten met een complexe inwendige structuur te creëren en te manipuleren, een struikelblok in de ontwikkeling van een dergelijke omgeving. Omdat bovendien de methode die ondersteund moest worden, verwacht werd grondig te evolueren gedurende het project, was een flexibele taal van hoog niveau om de inwendige structuur van een document te beschrijven van het hoogste belang. Alhoewel op het moment dat het project aanving verschillende gesofistikeerde werktuigen om grafische gebruikersinterfaces te genereren, beschikbaar waren, werden geen geschikte werktuigen gevonden om de structuur van EROOS-modellen te beschrijven. Om deze reden werd een generisch pakket, dat een uitgebreide verzameling bewerkingen om te navigeren doorheen complexe grafen aanbood, uitgebreid om zulke structuren te editeren, wat resulteerde in de zogenoemde Reusable Graphical Editor. Gedurende dit project heeft dit pakket bewezen uitermate geschikt te zijn om de voortdurende veranderingen en uitbreidingen aan de concepten van onderliggende EROOS-methode op te vangen. Bovendien is de Reusable Graphical Editor ook met succes toegepast in de context van andere projecten, waarin gelijksoortige prototypewerktuigen moesten ontwikkeld worden. In een tweede fase bleek het werktuig, dat initieel geselecteerd was om deze gebruikersinterface te genereren, niet toepasbaar te zijn. Dit verklaart waarom op het einde van het project slechts een eerder primitieve vorm van de gebruikersinterfacing verwezenlijkt kon worden. Op dit moment zijn deze problemen echter opgelost, zodat een werktuig met een professionele gebruikersinterface beschikbaar is voor verdere experimenten met de EROOS-methode.

	

	OASIS : Approche orientée-objet d'architectures avancées d'assistant logiciel

	Prof. A. VAN LAMSWEERDE, UCL, Fac. des Sciences Appliquées
	Place Sainte-Barbe 2, 1348 Louvain-La-Neuve

L'objectif du projet OASIS était de concevoir et de prototype une architecture avancée d'assistant logiciel guidé par les processus, étendant les possibilités et l'architecture de l'environnement ALMA que nous avions conçu auparavant. L'idée était d'y inclure de la connaissance sur les processus de développement de logiciels afin de fournir une guidance active de l'utilisateur pour l'élaboration, la validation et la documentation des objets logiciels gérés dans une base d'objets suivant une méthodologie donnée. L'architecture d'OASIS devait fournir des mécanismes permettant de la particulariser (instancier) aux types d'objets, d'associations, de processus ou d'agents intervenant dans une méthodologie spécifique, existante ou à venir. De plus, nous souhaitions étudier plus précisément une instantiation de cette architecture générique permettant de supporter des processus complexes s'appuyant sur une grande quantité de connaissances variées, à savoir l'acquisition des spécifications de logiciels, domaine dans lequel nous avons acquis une expertise par le développement de la stratégie d'acquisition de spécifications KAOS.

Dans un premier temps, nous avons étudié des modèles et des processus existants ainsi que les paradigmes de modélisation de ces processus, encore appelés méta-modèles. Ensuite, nous avons proposé un schéma extensible pour la définition de modèles et de méta-modèles. Ce schéma est basé sur le paradigme orienté-objet. Tout méta-modèle est défini comme une spécialisation d'un noyau orienté-objet, général et unique. La dynamique d'un méta-modèle est définie par des méthodes attachées à des objets de niveau méta. Les modèles de processus sont alors définis comme des instances de ces objets de niveau méta. Ce schéma extensible fournit un pilote générique dont un prototype a été construit en ML. Une première expérience réaliste de description d'un tel méta-modèle comme spécialisation du pilote a été menée. Marvel, le paradigme de modélisation bien connu, a été choisi pour cette expérience.
En parallèle, nous avons identifié la nécessité de disposer de descriptions plus abstraites des modèles de processus. En effet, la plupart des langages de modélisation de processus existants ne permettent pas de décrire le pourquoi d'un modèle. En l'absence de telles informations, la maintenance de ces programmes est très difficile, voire impossible. Une approche par raffinement est nécessaire si on souhaite modéliser des processus complexes réalistes. Ceux-ci doivent tout d'abord être spécifiés dans un langage abstrait pour être ensuite progressivement raffinés en des programmes exécutables modélisant les processus. L'adéquation du langage KAOS comme langage abstrait de spécification de processus a été étudiée. Les résultats sont encourageants en ce sens qu'il est maintenant possible de raisonner formellement sur les buts et les contraintes apparaissant dans ces modèles.

KAOS a également été étudiée en tant que méthodologie de développement. Comme les études de cas l'ont montré, l'acquisition de spécifications KAOS est une tâche longue et ardue. Seule l'utilisation d'outils basés sur le paradigme de réutilisation peut rendre cette tâche supportable. Le raisonnement par analogie s'avère une piste prometteuse dans cette optique. Des études de cas ont confirmé que cette approche pouvait fournir une assistance efficace dans la réutilisation de composants KAOS. Même si les mécanismes de base du raisonnement par analogie sont bien connus, un travail important fut nécessaire pour adapter ces mécanismes à l'acquisition de processus KAOS. Le résultat est un ensemble d'opérateurs génériques, applicables à tout langage de spécification basé sur un modèle conceptuel orienté-objet, muni de prédicats.

	Een declaratief model voor visuele interface voor ondervraging
	en voorstelling van informatie in object-georiënteerde informatiesystemen

	Prof. J. PAREDAENS, UIA, Dep. Wiskunde en Informatica
	Universiteitsplein 1, 2610 Wilrijk

Het object-georiënteerde programmeer-paradigma en de ermee verband houdende benadering van mens-machine interfaces gebaseerd op rechtstreekse object-manipulatie, bieden vele mogelijkheden tot ontwikkeling van nieuwe, intuïtief aantrekkelijke modellen voor gebruikers-interfaces tot informatiesystemen.

Het doel van het project was deze mogelijkheden te onderzoeken, gericht op het ontwerp van een uitbreidbaar, ergonomisch grafisch model voor interfaces tot informatiesystemen, dat een continu gamma van informatieopvragingsstrategieën ondersteunt, gaande van eenvoudige browsing tot een gesofistikeerde visuele query-taal, evenals krachtige en tegelijkertijd eenvoudig te gebruiken tools voor het definiëren van de gewenste object-representatie.

Zoals voorgesteld bij het begin van het project viel de studie uiteen in een aantal erg gecorreleerde deelaspecten. Eerst werd LOCO, een model om object-georiënteerde gegevens voor te stellen en te beheren op een logische en formeel ondersteunde manier.

Er zijn een aantal nieuw gereedschappen ontwikkeld die de gebruiker helpen in het definiëren van zijn applicaties, en in de definitie van de objectrepresentaties. Waar het vroeger enkel mogelijk was om de voorgedefinieerde objectrepresentaties aan te passen aan de behoeften van de applicatie, kan men nu ook volledig nieuwe representaties definiëren door middel van een eenvoudig te gebruiken interactief programma. Een ander nieuw ontwikkelde applicatie laat de gebruiker toe om op een intuïtieve wijze de structuur van zijn programma te analyseren, en om fouten erin op te zoeken. Deze applicatie is zowel beschikbaar in een textuele als in een grafische uitvoering, en is gebaseerd op geavanceerde foutdetectie technieken zoals in de internationale literatuur beschreven worden. Het verband met PROLOG werd onderzocht. Enkele toepassingen op medische informatica zijn gerealiseerd.

Parallel met LOCO werd G-Log ontwikkeld. De bedoeling hiervan was na te gaan hoe de concepten uit LOCO grafisch en visueel kunnen worden voorgesteld. Eerst werd het gegevensmodel van G-Log ontwikkeld. Een G-Log schema is een gerichte gelabelde graaf en representeert de structuur van de gegevensbank. Een G-Log schema bevat twee soorten knopen : rechthoekige knopen en elliptische knopen. De rechthoekige knopen stellen klassen van complexe objecten voor terwijl de ellipsvorming knopen klassen van atomaire objecten, i.e. waarden, representeren. De bogen van een G-Log schema duiden de relaties aan die tussen de verschillende klassen van het schema kunnen gelden. De uitdrukkingskracht van G-Log werd gemeten, het gebruik van gekleurde grafen werd onderzocht, en beslisbaarheidsproblemen in dit verband werden nagegaan.

Steunend op het vorige werd een volledig databasemodel ontwikkeld. Een prototype hiervan werd geïmplementeerd. GOOD (Graphical Object Oriented Database), is een grafische databank manipulatietaal. de taal werd ontwikkeld om een grafische taal te hebben, die toch bijna alle taken aankan die nodig zijn om vragen te stellen aan een gegevensbank, om schema's te creëren en om gegevens te plaatsen in de databank. De nodige aandacht werd hier besteed aan objectcreatie en de uitbreidingen van GOOD.

Tenslotte hebben we aandacht besteed aan de fundamentele onderbouw van onze modellen, met name aan de genericiteit, de overerving, de categorie theoretische aspecten, en de topologische aspecten wanneer we ons datamodel wensen toe te passen op GIS.

	ADIOS : Geavanceerde ontwikkelingen in objectsystemen

	Prof. W. VAN DE VELDE, VUB, Lab. voor Kunstmatige Intelligentie
	Pleinlaan 2, 1050  Brussel

Het doel van het ADIOS project was de verdere ontwikkeling en profilering van KRS, een bestaande object-gerichte kennisrepresentatietaal. Het was de bedoeling om KRS uit te bouwen tot een volwaardige omgeving voor de ontwikkeling van complexe software systemen. ADIOS gaat dus voornamelijk over kennistechnologische werktuigen.

De technische realisaties van het project zijn de volgende :

					.	critische analyse van systemen en benaderingen,
					.	ontwerp en implementatie van een ontwikkelingsomgeving die conceptuele modellering koppelt met gedeeltelijk geautomatiseerde code-generering, volgens een objectgerichte stijl,
					.	flexibele ondersteuning voor de kennisingenieur door reflectie over het kennisniveau, t.t.z. kennismodellering wordt zelf als probleemoplossen beschouwd en als dusdanig ook gemodelleerd binnen dezelfde omgeving,
					.	integratie van leertechnieken, opnieuw door leertaken op dezelfde manier te benaderen als andere taken.

Binnen een snel evoluerend technologisch landschap werden de aksenten binnen het ADIOS project regelmatig verlegd. Op deze manier werd niet enkel de academische relevantie van de resultaten nagestreefd. Deze moeten ook aansluiten bij de noden van de toekomst.

Twee belangrijke verschuivingen kunnen worden vastgesteld. De eerste verschuiving is van object-gerichtheid naar een component-perspectief. Objectgerichtheid is vooral een implementatietechniek. Hoewel het ook als een conceptualisatiebenadering kan beschouwd worden is de expressieve kracht van de ontologie der objecten te klein om complex probleemoplossend gedrag te kunnen uitdrukken. Eind van de jaren 80 en begin 90 werd daarom de notie van kennis-niveau (knowledge level), tot een praktisch werktuig uitgewerkt. De  "Components of Expertise" van Luc Steels is bijzonder invloedrijk in die context, en werd dan ook gevolgd binnen ADIOS. Objectgerichtheid werd, op het conceptueel niveau, vervangen door componentieel modeleren vanuit de drie perspectieven van taak, methode en domeinmodel. Alle doelen van ADIOS  werden in het licht van deze verschuiving opnieuw geïnterpreteerd. Zo werkt het beheer van de consistentie nu volledig op het kennis-niveau, reflectie is niet langer computationeel maar op het kennis-niveau, enzovoort. Bovendien bleek dat het programmeerprobleem waarop ADIOS oorspronkelijk gericht was, eenvoudiger werd door een goede conceptuele benadering, in die mate zelfs dat we een gedeeltelijk automatische code-generering konden realiseren, nog steeds volgens een objectgerichte stijl.

De tweede verschuiving binnen ADIOS is er een van objectgerichtheid naar agent-gerichtheid. Binnen dit project waren er hiervoor twee motivaties. Ten eerste wilden we het gebruik van Internet exploreren voor het opbouwen en uitwisselen van kennis-modeleringsexpertise (on-line bibliotheken). Al gauw bleek dat de snelle verspreiding van netwerken ook een invloed heeft op het soort van systemen dat men tegenwoordig wil bouwen. Toepassingen in een netwerk-omgeving worden opgevat, als multi-agent systemen : verzamelingen van onafhankelijke en autonome entiteiten, agenten genoemd. Er is een onomkeerbare trend weg van de monolotische alleenstaande invoer-uitvoer systemen, naar gedistribueerde, open en sterk interactieve toepassingen. Het agenten-paradigma is de logische stap in die richting.

Geen van deze verschuivingen - naar conceptueel modeleren en naar agent-gerichtheid - werd in het oorspronkelijke ADIOS voorstel geanticipeerd. Door deze verschuivingen echter vormen de technische resultaten van het ADIOS project een soliede basis voor toekomstig onderzoekswerk.  Het ADIOS team had zichzelf kunnen opsluiten in de veilige maar enge objectgerichte context. In plaats daarvan werd een toekomstgerichte integratie bereikt van kennistechnologie, leertechnieken, en objectgerichtheid, resoluut gericht op het agenten-paradigma. Hierdoor, en in termen van impact is dit ongetwijfeld het belangrijkste resultaat van het project, heeft deze groep zich snel een stevige reputatie kunnen verwerven voor onderzoek naar multi-agenten systemen en toepassingen van agenten. Zonder het ADIOS project was deze (noodzakelijke) transitie moeilijker geweest.

 

BETROUWBAARHEID EN VEILIGHEID

	Outils de vérification temporelle 

	Prof. P. WOLPER, ULG, Institut d'Electricité Montefiore
	Sart Tilman B28, 4000 Liège

Les systèmes réactifs, c'est-à-dire les systèmes programmés en interaction continue avec leur environnement, sont de plus en plus courants, que ce soit comme composants de gros systèmes informatiques et de communication (e.g. les protocoles dans un réseau informatique), ou comme parties de systèmes de contrôle (e.g. l'informatique embarquée en aéronautique). De plus, le rôle de ces systèmes est souvent critique et leur défaillance peut avoir des conséquences économiques ou physiques sérieuses. Un développement de qualité est donc essentiel pour de tels systèmes. Il y a deux voies habituellement reconnues pour obtenir des développements de qualité dans ce contexte. La première, qui est déjà assez largement adoptée, est d'utiliser une méthodologie basée sur un langage de description de systèmes de haut niveau (e.g. SDL, les StateCharts,...) qui aide à systématiser et à documenter le processus de conception. De telles méthodologies sont souvent liées à des outils qui fournissent un support pour la capture et la documentation de la conception de systèmes. La seconde approche pour obtenir des développements de qualité est complémentaire à la première et fournit des outils pour analyser le résultat de la conception et pour vérifier qu'il satisfait les propriétés désirées. Lors du démarrage de ce projet, de nombreuses bonnes idées sur la manière de procéder à cette vérification existaient, mais leur exploitation pratique était encore rare.

La technique principale utilisée pour vérifier la conception de systèmes réactifs est l'exploration de l'espace des états et son extension plus souple, la vérification de modèles. L'avantage additionnel de la vérification de modèles est qu'elle permet l'utilisation de la logique temporelle, un langage expressif et commode pour exprimer les propriétés exigées, tout en préservant la possibilité d'utiliser des algorithmes relativement simples et faciles à implémenter pour vérifier que le système conçu vérifie les exigences imposées. L'inconvénient majeur de cette technique est qu'elle n'est directement applicable qu'à des systèmes dont l'espace des états à une taille limitée bien inférieure à ce que l'on voit habituellement en pratique. Ce projet visait à contribuer, et a contribué, à lever ce handicap. Les contributions issues du projet sont basées sur trois idées directrices.

La première est que simplifier le problème de l'analyse facilite la conception et l'implémentation de meilleurs algorithmes de vérification. La concrétisation de cette idée qui a été exploitée est que la vérification de modèles pour la logique temporelle peut être réduite à une simple exploration de l'espace des états en utilisant la traduction de formules en automates, objets qui peuvent être vus comme des représentations opérationnelles des formules.

La seconde ligne directrice est d'attaquer les causes de la taille souvent excessive de l'espace des états. Le projet a montré que cela était possible en ce qui concerne l'explosion de l'espace des états venant de la modélisation du parallélisme par l'entrelacement. En effet, en analysant soigneusement l'interaction des actions des activités concurrentes, il est possible de se limiter à explorer certains de leurs entrelacements tout en permettant une analyse complète

La dernière idée directrice est que l'usage bien pensé de techniques algorithmiques avancées peut mener à des améliorations substantielles. Ce point de vue a été appliqué au problème de la représentation et de la mémorisation d'espaces d'états. Ce problème a été choisi parce que les données expérimentales montrent que la quantité de mémoire excessive nécessaire à la conservation de l'espace des états est une des causes les plus fréquentes de l'échec des tentatives de vérification. La technique utilisée est une application originale de la technique du "hashing" vue comme méthode de compression.

En plus d'un bon nombre de publications dans des congrès et revues internationaux, le projet a produit des implémentations de ses nouvelles techniques principales. Ces implémentations ont été réalisées dans le contexte de l'outil SPIN et ont été largement évaluées et adoptées. En conclusion, on peut dire que le projet a contribué significativement à l'évolution rapide de l'état de l'art de la vérification des systèmes réactifs. Ses contributions ont été bien reçues dans le milieu international de la recherche. De plus, le projet a contribué à développer une expertise locale qui devrait se révéler de grande valeur lorsque les techniques de vérification, qui maintenant sont devenues plus facilement applicables, seront plus largement adoptées dans le monde industriel.

	DIALOOG MENS-MACHINE

	Conception d'interfaces homme-machine pour des applications
	de gestion hautement interactives

	Prof. R. LESUISSE, FUNDP - Dep. d'Informatique
	Rue Grandgagnage, 21 - 5000 Namur

Le projet TRIDENT (Tools for an Interactive Development Environment) comprend à la fois une méthodologie visant le développement d'applications commerciales hautement interactives et un environnement en support de cette méthodologie. L'objectif principal de ce projet est d'élargir la théorie et la recherche connexe à la conception d'interfaces d'utilisateurs pour tels types d'applications interactives. Des recherches déjà effectuées ont mis en évidence le besoin :

			-	de définir une architecture objet orientée pour ces applications;
			-	de définir l'abstraction pertinente de l'objet de l'interaction physique par des environnements de développement actuels;
			-	d'écrire un langage complet en vue de spécifier à la fois la présentation et la conversation de tout dialogue;
			-	d'implémenter un prototype partiel pour la validation de la faisabilité de l'approche susmentionnée.

Le présent projet IT/IF/1 "A Multimedia Man-Machine Interface Management System for Highly Interactive Business Oriented Application" vise les objectifs suivants :

			1.	formuler des critiques et affiner l'architecture objet orientée, les modèles connexes et les langages de spécification actuels;
			2.	élargir la disponibilité d'objets d'interaction abstraite;
			3.	définir une base de connaissances globales de règles ergonomiques qui permettent de mettre en oeuvre des dialogues;
			4.	spécialiser des éléments actuels au domaine spécialisé du système de support à la décision afin de permettre la génération et la réutilisation;
			5.	définir et implémenter un éditeur graphique pour le langage de spécification;
			6.	définir une méthodologie globale intégrant l'ensemble des aspects susmentionnés;
			7.	implémenter des prototypes d'instruments de logiciel en support de cette méthodologie.

Afin de réaliser les objectifs 1 à 6, une méthodologie complète a été étudiée allant de la recherche jusqu'à la pratique. A cet effet cinq activités fondamentales ont été mises en oeuvre :

			.	élaboration de spécifications d'interfaces d'utilisateurs à partir des résultats de l'analyse des tâches;
			.	dériver des présentations de l'analyse des tâches et des règles ergonomiques;
			.	dériver une architecture de logiciel de l'analyse des tâches et de composantes de présentation;
			.	élaborer des spécifications de dialogue de haut niveau à partir des résultats de l'analyse des tâches;
			.	transformer le cadre de la méthodologie en un cadre de spécifications.

Les objectifs 2, 3, 4, 5 et 7 sont atteints par le développement d'instruments de logiciel supportant la méthodologie susmentionnée : suggestion automatique du style d'interaction, identification automatique de fenêtres, sélection automatique d'objets d'interaction abstraite, placement automatique d'objets d'interaction concrète.

L'ensemble des prototypes d'instruments de logiciel ont été implémentés et testés sur Microsoft Windows V3.11 en version MS-DOS V6.2.

Des concepts qui ont été définis, décrits et délimités antérieurement ont été appliqués à une étude de cas en vue d'une évaluation. Ce rapport est consacré aux cadres pouvant être utilisés en vue du développement de systèmes d'aide à la décision.

Un prototype d'un éditeur graphique supportant différentes étapes de la méthodologie a d'abord été introduit. Un logiciel complet a été développé et supportera par sa génération plusieurs graphiques associés à la méthodologie. La portée de cet éditeur est d'ordre général et comprend l'application, la technique objet orienté à l'édition graphique.

	Calliope : een methodologie voor een gebruiker en situatie aanpasbare
	multi-media-mens-machine-dialoog

	Prof. M. RIJCKAERT, KUL, Afdeling Chemische Procestechniek
	De Croylaan, 46 - 3001 Heverlee

In het kader van het Calliope project (DPWB IT/IF/7) werd een generisch intelligent mens-machine dialoog-systeem ontwikkeld. De voornaamste functie van dit systeem is het begeleiden/coachen van een gebruiker/operator bij het uitvoeren van een taak met een toestel. Dat toestel kan zowel een computer, een koffiezetmachine, als een machine in een fabriekshal zijn.

De kern van het systeem is een planningmodule, gebaseerd op Artificiële Intelligentie technieken. Het systeem maakt het name gebruik van een reeks van drie dialoogacties (die een model zijn van de drie spraakmodi : affirmatief, interrogatief en imperatief) en een bibliotheek bestaande uit dialoogscenario's.

De intelligente dimensie van Calliope blijkt uit de manier waarop het zijn dialogen aanpast zowel aan de gebruiker als aan de situatie. Calliope beheert mathematische modellen van zijn gebruikers en zijn fysische omgeving en gebruikt die modellen om de situatiegevoeligheid van de dialoogacties te verhogen. Gezien de aard van het huidige systeem - het coachen van gebruikers - bevatten de huidige modellen vooral informatie over de kennis en vaardigheden van de gebruikers. De modelleercomponenten behandelen simpele datastructuren die persoonlijke "dossiers" voorstellen, en gebruiken die persoonlijke dossiers om - via een stereotype-techniek- om nieuwe gebruikers te modelleren.

De resultaten die het project kan voorleggen, zijn : 

			1.	een implementatie van een "lege" planning component die op verschillende theoretische problemen getest is; 
			2.	een theoretisch gefundeerd kader voor een generische mens-machine dialoog, gebaseerd op gesitueerde dialoogacties, 
			3.	goed gedefinieerde technieken voor het modelleren en controleren van gebruikers en situaties; 
			4.	een blauwdruk voor een generisch intelligent mens-machine dialoogsysteem.

	Mens-Machine-Mens dialoog in een groepsbesluitvormings-
	ondersteuningssysteem

	Prof. L. Bollaert, VUB, Vrijetijd Toekomst en Beleidsplanning
	Pleinlaan 2, 1050 Brussel
	Prof. J.P. BRANS, ULB, Sciences appliquées
	Bd. du Triomphe, 1050 Bruxelles

Inleiding

GDSS, Group Decision Support Systems. Dit concept ontstond een tiental jaren geleden toen men voor het eerst probeerde om via computerondersteuning systematisch groepen betere beslissingen te helpen maken. Sindsdien kende GDSS een steeds groeiende belangstelling, omwille van verscheidene redenen :

					.	de marktcompetitie noopt voortdurend tot het nemen van betere beslissingen;
					.	de markt en de wereld evolueren sneller en sneller, dus ook beslissingen moeten sneller genomen worden;
					.	de informatie-technologie veroorzaakte en dramatische toename van de beschikbare informatie en kennis voor de beleidsmakers; er is dus behoefte aan een tool om hiervan op een efficiënte manier gebruik te maken;
					.	ondernemingen neigen naar vlakkere organisatievormen, waarbij meer beslissingsmacht aan lagere niveaus gegeven wordt. Een manier om dat te realiseren is het laten deelnemen van mensen aan beslissingsvergaderingen.

Dit leidde tot een groot aantal onderzoeksprojecten in het domein, en tot minstens één commercieel produkt : TeamFocus, van IBM. Tegenwoordig worden TeamFocus en enkele andere systemen gebruikt of geïnstalleerd in meerdere ondernemingen, business schools en organisaties. De resultaten zijn veelbelovend, maar tonen ook aan dat GDSS nog in haar kinderschoenen staat. Er is nog veel te doen.

Het projekt

Daarom beslissen twee onderzoeksteams in 1990 om hun kennis en ervaring samen te brengen : de dienst Vrijetijd, Toekomst- en Beleidsplanning van de Vrije Universiteit Brussel en de Service de Mathématiques de la Gestion van de Université Libre de Bruxelles. Vanuit de overtuiging dat groepsbesluitvorming een complex probleem is dat in zijn globaliteit dient aangepakt te worden, werd op 15 december 1990 een driejarig interdisciplinair projekt opgestart onder de naam Mens-Machine-Mens Dialoog in een Groepsbesluitvormingsondersteuningssysteem. Dit was mogelijk dank zijn de steun van de Dienst voor de Programmatie van het Wetenschapsbeleid die de contracten IT/IF/19 en IT/IF/20 toekende aan dit projekt. Het doel van dit projekt was de kennis over dit terrein te bevorderen, een GDSS te ontwikkelen en te testen.
Drie jaar later kan gesteld worden dat de objectieven bereikt werden.

					.	Uiteraard gaf een grondige literatuurstudie ons een beter inzicht in het probleem. Maar we leerden ook veel uit de samenwerking tussen sociale wetenschappers en operationeel onderzoekers, uit het ontwikkelingsproces en uit de tests met het systeem.
					.	Een GDSS werd ontwikkeld door de samenwerking van de beide teams in het projekten, de dienst Laboratorium voor Programmeerkunde (Vrije Universiteit Brussel Faculteit Wetenschappen - Prof. Th. DHONDT) en Softcore NV, een software-producent. Het vertoont nog enkele tekortkomingen (zowel technologisch als methodologisch) maar is toch reeds operationeel.
					.	Intensieve tests werden uitgevoerd met GDSS en met enkele vroegere prototypes. Deze laatsten stelden ons in staat om het systeem op een constructieve wijze te ontwikkelen. Dit ontwikkelingsproces, dat onlangs beëindigd werd, laat ons toe om onze benadering als waardevol te beschouwen en ons systeem als operationeel.

Het huidige systeem

Een besluitvormingsproces kan ruwweg ingedeeld worden in twee delen : het genereren van ideeën en het evalueren van die ideeën. In onze benadering wordt het eerste deel behandeld met behulp van de MacPolicy software en het tweede deel met behulp van de MacPromethee software.

MacPolicy is gebaseerd op de Delphi methode, een discussietechniek die zoals brainstorming (het vaakst gebruikt in andere systemen) of de nominale groepstechniek kan gebruikt worden om een elektronische discussie te voeren. Het grote voordeel van Delphi dan het gestructureerde elektronische discussie toelaat.

MacPromethee is gebaseerd op de multicriteria besluitvormingsondersteuningsmethode PROMETHEE. Zij maakt het mogelijk dat groepen verschillende alternatieven volgens verschillende criteria kunnen evalueren. Zij kan dus beschouwd worden als een gesofisticeerd instrument voor stemmingsrondes. Het geeft de deelnemers een begrijpbaar overzicht van het probleem en kan bronnen van conflict of wegen naar betere oplossingen aanwijzen.

Beide programma's zijn geschreven in Smalltalk 80 (loopt op Macintosh, Unix, Windows) en functioneren via netwerken. Er is een coördinator nodig voor het gebruik van het systeem, en de deelnemers moeten in dezelfde ruimte aanwezig zijn.

Toekomstig onderzoek

Er kunnen vele verbeteringen aangebracht worden in het huidige systeem. Zo zouden de twee programma's volledig geïntegreerd moeten worden, waarbij van één enkele database gebruik gemaakt wordt. Maar bovenal zou het interessant zijn om het systeem zodanig aan te passen dat het kan functioneren in een asynchrone setting. De deelnemers zouden dan niet meer in dezelfde ruimte aanwezig of tegelijkertijd ingelogd hoeven te zijn. Het toepassingsdomein van dit soort systeem zou dan ook veel ruimer worden dan dat van het huidige.

Het impulsprogramma "Informatica van de toekomst" dat liep van 1990 tot 1995 had betrekking op volgende thema's:

				. Parallelle architecturen
				. Objectgeoriënteerde benadering
				. Betrouwbaarheid en veiligheid
				. Dialoog mens-machine

Het onderzoek op het gebied van de parallelle architecturen heeft als doel instrumenten te ontwikkelen waardoor het gebruik van die architecturen zo doorzichtig mogelijk wordt gemaakt. Dit van nature technisch onderzoek snijdt thema's aan zoals de programmeertalen die aan het parallellisme zijn aangepast, de parallellisering van programma's en de concipiëring van parallelle algoritmen. De beschouwde parallelle architecturen zijn verschillend naargelang van het project, te weten transputernetwerken, PC-netwerken of nog, parallelgeschakelde machines.

De objectgeöriënteerde benadering bestaat erin een programma te concipiëren uitgaande van de verwerkte objecten (gegevens), eerder dan, zoals traditioneel wordt gedaan, voorrang te verlenen aan de op die gegevens toegepaste verwerking. 
In die benadering vormen de objecten het centraal element van het programma, terwijl de verwerkingsmethoden verbonden zijn met de objecten waarop zij betrekking hebben. Die nieuwe programmastructuur maakt de concipiëring ervan gemakkelijker en biedt de mogelijkheid bestaande programma's beter opnieuw aan te wenden, wat leidt tot een aanzienlijke produktiviteitsverhoging.
De objectgeoriënteerde benadering heeft een vrij ruim toepassingsgebied. Sommige projecten bestuderen de toepassing ervan bij de kennisvoorstelling, hetgeen een fundamenteel gebied vormt voor de artificiële intelligentie en de expertsystemen. Er is ook steeds meer belangstelling voor gegevensbanken met een objectgeoriënteerde structuur.

Een programmatuurfout kan rampzalige gevolgen hebben, vandaar de roep om betrouwbaarheid. De betrouwbaarheid van programmatuur kan worden gewaarborgd als gebruik wordt gemaakt van een systematische analysemethode waardoor kan worden vastgesteld of de programmatuur wel voldoet aan een reeks voorwaarden die met behulp van een formele specificatie uitgedrukt worden. 

De dialoog mens-machine speelt een doorslaggevende rol in de verspreiding van informatietechnologie. Hiermee definieert en exploiteert de gebruiker immers het systeem. Een goed uitgedachte "dialoog" is derhalve essentieel voor de toegankelijkheid van de computersystemen en het doeltreffend gebruik ervan.

	Voor verdere inlichtingen over de onderzoeksprojecten
	gelieve contact op te nemen met de auteurs of met de DWTC
	D/1996/1191/37

		DIENSTEN VAN DE EERSTE MINISTER
		WETENSCHAPPELIJKE, TECHNISCHE
		EN CULTURELE AANGELEGENHEDEN
		Wetenschapsstraat 8 - B-1000 Brussel
		tel (02) 238 34 11 × fax (02) 230 59 12
		http://www.belspo.be