Månedlige arkiver: mars 2011

Parallelle programmer

Informatikkens verden hadde denne uken foredrag nummer 10 og 11, og først ut var Arne Maus fra forskningsgruppen Objektorientering, Modellering og Språk med foredraget «Den vanskelige datamaskinen – hvordan programmerer vi den?»

Arne Maus

Før 1980 besto kjernen av datamaskinen av en CPU (regneenhet) og hukommelse. Regneenheten var rask, mens det å skrive og lese til hukommelsen var (og er) en tregere prosess. For å bøte på dette ble det utviklet mellomlagre eller såkalte «cache» for mer effektiv lagring av de data man brukte ofte. Det ble videre utviklet to eller flere nivåer med «cache» slik at data kunne graderes ut mot hovedhukommelsen. Slik så prosessoren  i en datamaskin ut i mange år!

CPUer med 2 eller flere «cache» ble stadig kraftigere i den forstand at stadig flere transistorer kunne plasseres på en databrikke (integrert krets). Når strøm kjøres gjennom transistorene i den integrerte kretsen utvikles varme og etter hvert som CPUene ble kraftigere og kraftigere ble de for varme. For å bøte på dette fant man ut at en databrikke kunne inneholde flere CPUer (CPU ble heretter kalt prosessor og hver beregningsenhet ble kalt en kjerne). Hver kjerne hadde da sine egne mellomlagre, men slik at begge kjernene  hadde en felles hukommelse. Vi fikk parallelle maskiner. Dette skjedd omkring år 2005. En annen form for parallelle enheter er grafikkprosessorer (GPUer) drevet fram av spillindustrien. I dag har de fleste datamaskiner en kjerne bestående av minst 2 kjerner, og det blir stadig mer vanlig med både 4, 8 og 16 kjerner i datamaskinens prosessor. Hvordan utnytte denne kraften?

Svaret er å kjøre programmet som flere tråder i parallell og da utføre såkalte parallelle beregninger. Her oppstår imidlertid noen utfordringer som Arne Maus snakket om i sitt foredrag, og det er særlig to forutsetninger som må være oppfylt før man kan utnytte flere kjerner i parallell:

  1. Det må eksistere en naturlig oppdeling av den oppgaven man skal løse slik at hver deloppgave kan løses  for seg. Anta at vi har en prosessor med 8 kjerner og et bilde på 1024 x 1024 punkter (pixler) med gråtoneverdier mellom 0(sort) og 255(hvitt). Finne alle punkter i bildet med gråtoneverdier i intervallet [0-9]. Da kan bildet deles i 8 bilder hver på 512 x 256 punkter og hver av de 8 kjernene kan behandle hvert sitt bilde, dvs finne gråtoneverdier i intervallet [0-9]. Denne type problemstillinger kan parallellisering med tilnærmet full effekt, dvs. at 8 kjerner tilnærmet går 8 ganger så hurtig som én kjerne.
  2. Oppgaven må være stor nok, dvs. at man ikke får effekt av en parallellisering før problemet har en viss størrelse. Et klassisk eksempel er sortering av tall – et eksempel Arne Maus gikk gjennom i detalj. Anta at vi har en prosessor med 8 kjerner og N usorterte tall. Da finnes det en algoritme/metode som heter kvikksort for å sortere disse tallene i stigende rekkefølge. Denne algoritmen kan parallelliseres over 8 kjerner, men den vil ikke være raskere enn en sekvensiell prosessering (dvs. sortering på én kjerne) før N er omkring 1 million. Skal man sortere 10 millioner eller flere tall vil en parallellisering over 8 kjerner gå 3-4 ganger raskere enn på én kjerne. I motsetning til bildeeksemplet over er kvikksort en mer sammensatt problemstilling, og effekten er derfor mindre. Det er til og med slik at effekten er negativ dersom problemet ikke er stort nok.

I tillegg til de to forutsetningen som må være tilstede for at parallellisering gir effekt er det en særlig utfordring å synkronisere prosessene på de ulike kjernene slik at 1) de samarbeider i de tilfeller en kjerne er avhengig av resultater fra andre kjerner for å gjøre en jobb og 2) slik at de ikke arbeider på de samme dataene i hukommelsen samtidig. Dette finnes det mekanismer for i de fleste programmeringsspråk i dag, f.eks. i Java.

Arne Maus snakket mye om “tråder”, som er en betegnelse på én beregningsprosess i et program som gjør en sekvensiell jobb på en kjerne. En tråd kan starte nye tråder og disse vil av operativsystemet bli sendt til andre kjerner. Et klassisk eksempel har vi foran oss når vi spiller dataspill der all tastingen på tastaturet eller signalene fra en “joystick” håndteres i én tråd på én kjerne som igjen gir signaler til figurene som beveger seg og tegnes ut på skjermen ved hjelp en eller flere andre tråder på andre kjerner eller en GPU (som i seg selv er en parallell datamaskin spesiallaget for å tegne bilder på en dataskjerm).

DLD og politisk nedtur

I dag har Arbeiderpartiet og Høyre blitt enige om at datalagringsdirektivet (DLD) skal innføres i Norge. Jeg registrerer at enigheten mellom Arbeidpartiet og Høyre tar høyde for en del av argumentasjonen fra motstandere av DLD, men dette er allikevel en trist dag for Norge! Dette trenger vi ikke, og som jeg og andre har hevdet med store tyngde gjennom lengre tid; dette er et alvorlig angrep på personvernet og det er en radikalt dårlig investering!

Det endelige forslaget fra de to partiene legger opp til strengere rutiner for innsyn og økt sikkerhet. Store byråkratier må bygges opp og tele-/internettleverandørene pålegges kostnadskrevende tiltak. MEN, det er et lyspunkt i dette, noe også IKT-Norge er inne på i dagens TU; Det blir så krevende å innføre DLD med de føringer som nå legges inn at det blir tilnærmet umulig å gjennomføre en rasjonell innføring av direktivet. Dersom det allikevel innføres, blir det kostbart for forbruker som må betale for tele-/internettleverandørenes systemer, og for Staten som både må forsterke Datatilsynet og etablere kontrollsystemer for å overvåke bruken.

Jeg er fortsatt optimist, og håper og tror at ikke bare Norge, men hele Europa, tar til fornuften.

Korrekte programmer

Dette referatet fra forelesningsserien Informatikkens verden er skrevet av Ragnhild Kobro Runde.

Peter Csaba Ölveczky

Samfunnet er avhengig av korrekte og pålitelige datasystemer. Samtidig blir disse datasystemene stadig større og mer kompliserte. Dette gir store utfordringer når programvare skal utvikles, utvides eller endres.  Eksempler på systemer hvor det er kritisk hvis ting går galt inkluderer fly, banksystemer, krigføring styrt via satellitter og vanlige biler hvor små datamaskiner erstatter mer og mer av mekanikken. Peter Csaba Ölveczky fra forskningsgruppen Presis modellering og analyse(PMA) snakker i dette foredraget om hvordan utvikle korrekte datasystemer?

Datasikkerhet

Bruk av nettbank er et eksempel hvor datasikkerhet er viktig. På nettet er det lett, både å avlytte kommunikasjon og sende falske meldinger. Så hvordan kan nettbanken vite at den kommuniserer med den faktiske eieren av kontoen, og hvordan kan brukerne vite at han eller hun kommuniserer med den ekte banken? NSPK er en protokoll for slik gjensidig autentisering. NSPK ble mye brukt fra 1978, men formell analyse viste i 1995 at NSPK ikke var en sikker protokoll. Det tok altså 17 år å finne feilen – på tross av at protokollen essensielt bare består av tre linjer «kode»!

Spørsmålet blir da hvordan man kan sikre at viktige systemer er korrekte? Her finnes det mange teknikker som utfyller hverandre, og formell modellering og analyse av systemdesign er en viktig del av dette.

Modellering

Modellering vil si å lage en plan/beskrivelse av hvordan systemet er tenkt å fungere – tilsvarende hvordan arkitekter lager ulike typer modeller av bygningene før selve byggingen starter. Sammenlignet med å lage et ferdig datasystem, går det raskt å lage en modell av systemet som inkluderer de viktige delene av systemet, med hvor detaljer som ikke har noe med den endelige utformingen å gjøre ikke er tatt med. Modellen kan så brukes til å analysere endelige utformingen med tanke på spørsmål som: Kan flyet styrte? Er det mulig å lure nettbanken? Vil airbagen utløses raskt nok ved en kollisjon? Dersom analysen viser at designet er tilfredsstillende, fungerer modellen som et fundament for implementasjon av systemet.

Formelle modeller og analysemetoder

En formell modell er basert på matematisk logikk, og modellen er et matematisk objekt. Det vil si at modellen er entydig, at matematiske regler kan brukes til å analysere konsekvenser av utformingen og at klare slutningsregler gjør at analysen i stor grad kan automatiseres.

I foredraget skilte Peter mellom tre hovedtyper av analysemetoder:

  • Simulering, hvor man eksekverer en mulig oppførsel av systemet. Dette gir god informasjon om denne ene oppførselen, men fungerer dårlig hvis systemet har mange mulige oppførsler (også for samme inngangsdata), noe som stort sett er tilfellet når det er snakk om nettverk.
  • Modellsjekking, hvor man automatisk analyserer alle mulige oppførsler ut fra en start-tilstand. Dette fungerer bra ikke minst for å finne mer uvanlige feil, men det kan være et problem hvis det blir altfor mange mulige oppførsler (tilstander).
  • Bevise teoremer, hvor man fører et matematisk bevis for at visse egenskaper holder. Dette er ikke-trivielt, og selv om deler kan automatiseres krever det ofte også mye menneskelig hjelp.

Formelle metoder på ifi

For å få systemdesignere til å benytte formelle metoder, er det viktig med enkle og intuitive formalismer og analysemetoder. En mulighet er å definere en formell semantikk til et intuitivt modelleringsspråk som allerede brukes av systemdesignere – for så å automatisk oversette den uformelle modellen til en formell modell for videre analyse. PMA-gruppen ved ifi bygger sin virksomhet på omskrivingslogikk og Maude – et formelt språk og verktøy for simulering og modellsjekking, med mange likhetstrekk med funksjonell programmering. Spesielt har PMA-gruppen utviklet CREOL, et modelleringsspråk basert på Maude, som blant annet har vært brukt til å verifisere en modell av en menge autonome støvsugere.

Velkommen til nye hjemmesider

Endelig er dagen her!

Nye hjemmesider er lagt ut etter mange uker med hardt arbeid fra flere, men særlig av Instituttets web-redaksjon bestående av Sigrun og Kristin. Følg med på nyheter og fakta fra forskningsfronten og hold deg orientert om Instituttets  studieprogrammer og emner/kurs. Første faktasak måtte selvfølgelig bli en liten orientering om det nye informatikkbygget – Ole-Johan Dahls Hus.

Ole-Johan Dahls Hus (Foto: Jørn Hagerup)

En ettermiddag på Imperial

På min spasertur gjennom Kensington Garden og Hyde Park ser jeg kuppelen på Royal Albert Hall. Rett bak ligger Imperial College – et av Londons mest renommerte universitetet. I helgen besøkte jeg det gamle ærverdige Trinety College i Dublin som ble etablert allerede i 1592.  Imperial College er et mye yngre universitet, etablert så sent som i 1907. Gjennom store ombygginger de senere årene fremstår Imperial College som et moderne universitet.

Imperial College har en interessant organisering. Jeg besøkte ”Institute of Biomedical engineering” som er en enhet på tvers av fakultetene på Imperial. De har lagt særlig vekt på tverrfaglighet og de har samlokalisert forskere med ulik fagbakgrunn i en og samme enhet. Medisinere, fysikere, biologer, matematikere og informatikere arbeider sammen for å finne løsninger på biomedisinske utfordringer. Vi gjør dette i mindre skala ved UiO, men skal man virkelig få til nye innovasjoner har jeg stor tro på de ”grepene” de har tatt ved Imperial College.

Imperial College er bygningene farget blått/turkis. Du ser kuppelen på Royal Albert Hall i overste høyre hjørne.

Institutt for informatikk, særlig representert ved Tor Sverre Lande (Bassen), har samarbeidet med Imperial College gjennom mange år. Institutt for informatikk og de forskningsgruppene jeg besøkt er delvis komplementære, men vi har også nødvendig faglig overlapp. Imperial er derfor en interessant samarbeidspartner for Institutt for informatikk. Vi ble enige om å arbeide frem et forslag omkring felles doktorgradsutdanning mellom UiO og Imperial, i første omgang med fokus på skjæringsfeltet mellom informatikk og biomedisin. Det passer meget godt med våre satsinger innen ”IKT i medisin og helse”.

Gjestfrihet og litt historie

Per på en av "gressdynene" ved Brittas Bay

I feiende flott vårvær har jeg hatt gleden av å oppholde meg i Irland noen dager. Tiden har gått med private sysler ved Brittas Bay, en times kjøring sør for Dublin. Her har vi møtt en gjestfrihet som man sjelden opplever. Vi bodde i en hytte tilhørende vertshustet Ballinclea house.

Vertinnen på verthuset sørget for at vi hadde frokosten på bordet oppe i hytta hver morgen.  Hennes egg og bacon ble en super start på dagen for en gjeng med ivrige gutter (godt opp i åra) som skulle ute å flytte og forfølge noen små hvite baller hele dagen. Ballinclea house ligger langs hovedveien mot syd fra Dublin, midt mellom byene Wicklow og Arklow. Stedet kan anbefales for alle som drømmer om en tur til Irland.

Stedet vi besøkte hadde én restaurant (og pub) – Jack Whites – et samlingssted for hele bygda. Når vi skulle spise middag var det bare å ringe sjefen på restauranten og han hentet oss og fraktet oss hjem om kvelden de 2 kilometerne  fra hytta til restauranten. Vi bidro selvfølgelig til omsetningen denne helgen uten at det gjorde et alvorlig innhogg i våre lommebøker, og jeg fikk mitt irske favorittmåltid (“Bangers and mash”).  “Bangers and mash” er pølser med potetstappe, men pølsene er noe helt for seg selv og potetstappe smaker aller best i Irland!

Gamle bøker i Dublin

Etter noen flotte dager vandrende mellom «gressdynene» i godværet i Brittas Bay fikk vi en dag i Dublin. Der tok vi turen innom Trinety College (etablert 1592), leste oss gjennom rommet med “The book of Kells” og tok det fantastiske biblioteket i øyesyn. Jeg har sett det før, men det er like imponerende hver gang.

I utstilingen av «The book of Kells» leste jeg et sted at vikingene kom til Irland i 795 e.kr., men jeg tror ikke det er genene etter mine norske forgjengere som er årsaken til den store gjestfriheten vi møtte på den grønne øye vest i havet! Det er noe entusiastisk positivt med keltisk gjestfrihet!

Robotene kommer

Dette referatet i forelesningserien om Informatikkens verden er skrevet av Ragnhild Kobro Runde.

Mats Høvin

I dette foredraget snakket Mats Høvin fra gruppen Robotikk og intelligente systemer (ROBIN) om mange ulike roboter, fra både industri og forskning. Noen av disse presenteres under. En hovedkonklusjon må være at fremtidens roboter på mange måter er her allerede!

Industriroboter

Industriroboter brukes i stadig større grad for å erstatte mennesker «på gulvet» i tradisjonell industri. Slike roboter ligner gjerne litt på mennesker, slik at de kan overta arbeidsoppgavene uten at det er nødvendig å gjøre om på arbeidsplassene. Samtidig gjør roboter det også mulig å lage helt nye ting, siden de kan være mye mer nøyaktige enn det mennesker klarer.

Et etisk spørsmål er om det er riktig å fjerne arbeidsplasser på denne måter. Utstrakt bruk av industriroboter kan gjøre det mulig for bedrifter å konkurrere mot Asia, men hva skal man med en bedrift som ikke har mennesker? Et mulig svar er at det fortsatt er nødvendig med menneskelig arbeidskraft, men nå ikke direkte i produksjonen men til programmering, vedlikehold osv. av robotene.

Serviceroboter

Serviceroboter er et nytt begrep som er i ferd med å danne seg og betegner roboter som er på vei inn i samfunnet, ikke minst i helsevesenet. For eksempel CareBot fra GeckoSystems. Roboter kan hjelpe eldre med utføring av enkle oppgaver, og de kan overvåke og varsle om uønskede hendelser (som feks fall). CareBot har en skjerm, som kan brukes til økt kontakt med familien, og dermed økt livskvalitet. Samtidig kan økonomi virke i motsatt retning, dersom roboter erstatter den menneskelige kontakten innen for eksempel eldreomsorg.

En variant av dette er terapeutiske roboter som Paro og AIBO, en form for kunstige kjæledyr for selskap og kos til personer som ikke ønsker eller har muligheten til å ha ansvar for et vanlig dyr. AIBO er til og med laget slik at den utvikler seg ut fra hvordan den blir behandlet – ved god omsorg blir den vennlig og kjærlighetsfull, mens den kan bli «trassig» ved mangel på omsorg!

Et annet eksempel innen helse er da Vinci-systemet, som brukes ved små eller vanskelige operasjoner. Kirurgens bevegelser ved kontrollene blir skalert ned, og systemet fjerner også normale skjelvinger i kirurgens hender. Derimot gis det ikke fysisk feedback, slik at kirurgen kun kan basere seg på det han ser på skjermen.

Autonome roboter

For å kunne utføre operasjoner på utilgjengelige steder, er det et ønske om å ha roboter som kan handle autonomt, dvs på egen hånd, under store deler av oppdraget. Dette kan dreie seg om oppdrag som inspeksjon av oljeplattformer i hardt vær, overvåking av oljeledninger på bunnen av havet, eller utforsking av Mars. I slike tilfeller ønsker man at robotene selv skal kunne identifisere og håndtere farlige hindringer på vei mot det definerte målet.

Militære roboter

Crusher er en kjøretøy-robot som danner seg et 3D-bilde av terrenget for så å bestemme seg for den beste måten for å komme seg til det angitte stedet. Crusher veier 10 tonn, og har ingen problemer med å kjøre over en bil eller to på vei mot bestemmelses-stedet. Crusher kan kjøre på batteri, og er da lydløs – se for deg et selvtenkende monster på 10 tonn komme snikende opp bak deg!

BigDog er en robot med fire bein, laget for å frakte militært utstyr i områder med så vanskelig terreng at det ikke er mulig å bruke vanlige kjøretøy. BigDog kan også bevege seg på is, og ligner da ikke så rent lite på Bambi – bortsett fra at BigDog holder seg på beina!

Kunstig evolusjon

Kunstig evolusjon brukes for å betegne roboter som ikke bare kan operere autonomt, men som også kan lære på egen hånd. ROBIN-gruppen har utviklet «kyllingroboten» Henriette som er i stand til å lære seg selv å gå – og å lære det på nytt dersom en del skulle gå i stykker slik at det første innlærte bevegelsesmønsteret ikke lenger passer. Hovedprinsippet er å programmere roboten med små enkeltbevegelser, som den så setter sammen i et tilfeldig mønster og ser hvordan det fungerer. Mønstre som fungerer minst dårlig beholdes og roboten prøver så å sette disse sammen igjen på nye måter for å finne noe som fungerer bedre, inntil målet (feks å lære å gå) er nådd. ROBIN-gruppen ser også på hvordan kunstig evolusjon kan brukes til å gro nye robot-deler ved behov, for eksempel kunstige ledd.

Smarte ting i smarte hjem

Inne i en smart bolig for eldre ved Universitetet i Toulouse (foto: M. Dæhlen)

Datamaskinen er på vei inn i tingene vi bruker i hverdagen. Denne utvikling har for så vidt pågått over flere år, men tingene blir nå mer «intelligente» og de kommuniserer med omverden.

Huset ditt blir litt smartere. Når du skal hjem etter jobben registrerer din mobiltelefon at du er på vei hjem noe som medfører at ditt energisystem, f.eks. en luft-til-luft varmepumpe, sørger for å heve temperaturen til det nivået du ønsker deg. Når siste person i familien forlater boligen om morgen ble temperaturen senken noen grader. Når du låser deg inn ved hjelp av ditt nøkkelkort, som bare kan brukes av deg, går huset ditt ut av dvalen. Lys slås på, en berøringsskjerm gir deg beskjed om at kjøpmannen har levert matvarene i et kjøleskap som kan fóres fra utsiden, og alle nødvendig bekjeder finner du ved et par små berøringer på skjermen som er «bakt» inn i veggen på kjøkkenet.

Det vil stadig bli utviklet nye gjenstander der sensorer og datamaskiner er bygget inn, men for at dette skal virke må det utvikles systemløsninger for håndtering av data og kommunikasjon, både internt i boligen og i forhold til omverden. Disse systemene må være sikre, både i forhold til drift og «innbrudd», og kommunikasjonen må bygges på standarder slik at du som bruker kan velge de produktene som passer deg.

Over store deler av verden utvikles smarte løsninger for hjemmet og det er et særlig fokus på utvikling av teknologi som kan hjelpe eldre i deres hverdag. Oslo Kommune skal i løpet av de neste årene utvikle og bygge nærmere 1000 leiligheter for eldre.  Institutt for informatikk er involvert i dette arbeidet. Vårt mål er å finne smarte løsninger for eldre der teknologien finner sin naturlig plass i hverdagen. Dette er en stor utfordring da behovene varierer sterkt mellom individene som skal bruke de smarte boligene og hvilke (offentlige) tjenester som skal og bør være knyttet til boligene. Videre vil behovene varierer sterkt over tid for hver enkelt bruker.

En rekke bedrifter arbeider med teknologi og løsninger for smarte boliger og vi samarbeider tett med Oslo Medtech i utviklingen av gode prosjekter sammen med Oslo kommune og utvalgte bedrifter i nettverket til Oslo Medtech.

ICT in Medicine and Health (at a glance)

The Department of Informatics at The University of Oslo (UiO) is involved in many projects addressing important challenges in medicine and health. I will here give a short resymé of our research profile to wards medicine and health at the Department of informatics.

Community power and health in rural Bangladesh.

The development of health information systems and ICT support for collaboration in the health sector are major research topics at the Department of Informatics. Researchers in the Department are studying socio-technological issues in the health sector, and during recent years we have created strong interdisciplinary activities combining competence within ICT, sociology and health. This is supported by strong competence in complexity analysis, building of information infrastructures, development of mobile services, human-computer interaction, and design of digital environments.  Moreover, we believe that our competence in building and utilizing open source software is important to cover future needs in the health sector. In particular, we are involved in projects aimed at challenges created by an ageing population and the development of smart houses for elderly people.

ICT in medical research has grown to become a huge area at UiO and we collaborate closely with excellent groups conducting brain, cancer and heart research at the Oslo University hospital and the Faculty of Medicine at UiO. The main areas of research are development of statistical methods and software for studying biomedical data, simulation within systems biology, and the development of image-based methods for cancer diagnostics. An important partner within computational biomedicine (systems biology) is Simula research laboratory.

Tor Sverre Lande (Bassen) and Phillipp Häfligere med nanoelectronics for implants

Medical equipment and intervention is a growing area where we work on issues such as robustness of intervention software, search mechanism dedicated for medical use, image fusion, ultrasound, nanoelectronics for implants and robotics for surgery and support to elderly people. We are also involved in the development of user interfaces for advanced medical equipment.

The Department of informatics is also involved in several projects with partners in industry and public sector, and we are having an increasing portefolio of projects together with members of Oslo Medtech – a network organizing companies, hospitals and research organization developing products and services in the realm of medicine and health.

Uniforum skildrer livet i Gaustadbekkdalen

Kveld i Gaustadbekkdalen. Foto: Ola Sæther

Denne ukas Uniforum dedikerte midtsidene til en vakker skildring av livet i det nye informatikkbygget i Gaustadbekkdalen. Studenter og ansatte synes å være svært fornøyde, og i følge en student vil hun ikke studere andre steder enn i Ole-Johan Dahls Hus. Les videre i Uniforum og takk til Martin Toft og Ola Sæther for en fin reportasje med mange fine bilder fra livet i det nye bygget.

Jeg kan jo legge til at Studentkjelleren – ESCAPE – hadde en såkalt «soft opening» på fredag. Alt synes å være på plass i kjelleren. Jeg slang innom og under finner du en stolt Kjellermester (Magnus) og Cafevert (Eivind), knipset med min mobiltelefon. Vi ser frem til den offisielle åpningen av ESCAPE – en moderne studentkjeller som drives av vår  egen studentforeing Cybernetisk Selskab.

Magnus Johansen (Kjellermester) og Eivind Vedå Gilhuus (Cafévert)