 |
 |
|
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 :
Op elk van deze vlakken werden belangrijke resultaten geboekt, die internationaal gepubliceerd werden. Het uitgevoerde werk gaf tevens aanleiding tot drie doctoraatsthesissen
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".
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.
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.
|
|
|