Numero 18

måndag 8 maj 1995, årgång 25

Veckoblad om forskning, undervisning och administration m.m.
NADA - Institutionen för numerisk analys och datalogi, KTH


Kalendarium

Aktuellt kalendarium (inte kalendariet som hör specifikt till denna Numeroutgåva).

Seminarium: Att välja och bedöma information på Internet

Kjell Jansson, informatiker, KTHB (inledare), håller seminarium under ovanstående rubrik på onsdag (10 maj) kl. 13.00-14.15 i kursrummet, 1 tr., KTHB (Valhallavägen 81).

Upplysningar och föranmälan (senast 9 maj kl. 11): Per Jacobsson, utbildnings- och forskningsenheten, ankn. 7018, fax 7252, <perjac@admin.kth.se>. Numeropärmen 95.051.


KTHB minskar prenumerationslistan

KTH:s bibliotek har inför 1995 års prenumerationer upphört att prenumerera på ett större antal tidskriftsartiklar. En alfabetisk lista över vilka det gäller finns hos Sten.

Datalogiseminarium: Övre gräns för storleken på obstruktioner för stigbredd <= p

Jens Lagergren, NADA, håller seminarium teoretisk datalogi under ovanstående rubrik på torsdag (11 maj) kl. 15.15-16.15 i seminarierum 1537 (Lindstedtsv. 3, plan 5).

Sammanfattning

Man kan använda antalet tillstånd i en ändlig automat för att begränsa storleken på den minsta sträng som automaten accepterar. Detta är mycket enkelt och välkänt. Vi ska med inspiration hämtad från denna metod ge en generell metod att begränsa storleken hos obstruktioner för minorslutna familjer av grafer. Vi ska även tillämpa denna generella metod på familjen av grafer med stigbredd <= p. Resultatet blir en övre gräns som är exponentiell i p^3. Denna övre gräns kan jämföras med storleken på de största kända obstruktioner för stigbredd <= p, vilka har storlek 3^p. Samma metod ger övre gränser för intertwines av planära grafer samt för obstruktioner för trädbredd <= k.
Anders Björner & Johan Håstad

IPLab-seminarier

Det blir dubbla IPLabseminarier både 12 maj och 2 juni, vilket innebär seminarium 9.15-10.15 samt 10.30-11.30. Den 12 maj blir det två exjobbspresentationer med Olle Sundblad resp. Mårten Stenius. Den 2 juni är det Kerstin S. Eklundh resp Kai-Mikael Jää-Aro som står för seminarierna (mera detaljer om detta senare).
Lasse Kj.

Disputation: Performance Issues in Discrete Event Simulation

Robert Rönngren, IT, KTH, disputerar under ovanstående rubrik torsdagen den 18 maj kl. 10.00 i Kollegiesalen, administrationshuset (Valhallavägen 79).

Abstract

The focus of this thesis is on how to increase the execution speed of Discrete Event Simulation (DES). DES has gained wide acceptance and is one of the most commonly used simulation methods today. The thesis consists of a short overview of the subject of sequential and parallel DES and eight articles on issues related to the performance of DES.

To maintain causality correctness, i.e. that cause precedes action, in a sequential discrete event simulation it is sufficient to always select the event with the smallest timestamp first for execution. The set of generated but not yet executed events is referred to as the pending event set. The performance of a sequential DES heavily depends on the data structure used for the implementation of the pending event set. The first two articles in this thesis, A1 and A2, describe a new data structure for efficient implementation of the pending event set and a comprehensive performance study of the most frequently used data structures respectively.

Most simulated systems are inherently parallel by nature. This allows for a single simulation to be executed in parallel using several processors, thus reducing the execution time. Parallel execution of programs is no longer of interest only for the research community. Recent advances in low cost multiprocessor workstations have made parallel processing facilities commonly available. Several protocols for parallel discrete event simulation (PDES) have been proposed during the last decade. PDES includes many problem areas that are of general interest for parallel processing.

In a PDES, LPs are often treated as lightweight processes, which requires efficient process management and synchronization. It also requires efficient resource management, in particular memory management. These are topics closely related issues encountered in operating systems. A simulation model is often characterized by stochastic behavior and irregular communication and computation patterns. This implies that the parallelism available is irregular and hard to predict and the simulation program often shows poor spatial locality. In general such problems are considered hard to efficiently execute in parallel. Solutions that address the problems encountered in PDES could thus be relevant to many other fields of computer science.

In an optimistic protocol, LPs are allowed to proceed with processing events without asserting (optimistically assuming), that the event processing will be causally correct. A detection and recovery protocol is used to undo any effects of causally incorrect processing. Optimistic protocols have a potential of exploiting a large fraction of the available parallelism with a low overhead, eliminating the need to block LPs which cannot yet guarantee that their continued processing will be causally correct. The Time Warp protocol, on which the studies of PDES in this thesis are focused, has proven to be one of the most promising approaches to PDES in a number of independent studies.

The articles A3-A6 address the questions of load balancing, LP scheduling, exploitation of lookahead, implementation of the pending event set and memory management in the context of the optimistic Time Warp protocol for PDES respectively. Article A7 addresses the question of how the underlying computer architecture affects the implementation and the performance of a Time Warp based PDES system. Lastly paper A8 shows an example where the use of global shared variables in a simulation sometimes favours the use of a class of PDES protocols referred to as conservative protocols over optimistic protocols.



Språkhörnet

Språkhörnet - debatt- och käpphästforum

Härmed införs ett språkhörn i Numero. Det är tänkt som ett debatt-, informations- och käpphästventileringsforum för alla som bryr sig lite om hur det svenska språket hanteras och utvecklas - i Sverige i allmänhet och på NADA i synnerhet.

Så, kära läsare, se nu till att skriva av dig det där du så länge funderat på, irriterat dig på eller undrat över. Red. hoppas på livlig debatt!

Red.

Brevinledning med kommatecken - svenskt?

En fenomen jag allt oftare stöter på är att datorbrev inleds med en hälsningsfras eller mottagarens namn, avslutat med ett kommatecken:
Hej,

Hoppas du fick...
Jag var helt övertygad om att detta var ett onödigt, rent av fånigt anammande av det anglosaxiska sättet att inleda brev ("Dear Sir, " och sådant). I skolan fick man ju lära sig att använda utropstecken.

Döm om min förvåning när jag - under skrivandet av detta inlägg - i Språknämndens skrivregler fann att kommatecken "används ibland istället för utropstecken efter inledande hälsningsord i brev". Håller vi med?

För att ändå behålla lite udd i detta första språkhörnsinlägg: språkreglerna påpekar att kommat "bör följas av liten bokstav". I ett exempel finns heller inte någon blank rad mellan fraserna.

Vad ska förresten styra konventionerna i ett brev - inte bara vad gäller inledningsfraser utan också så krångliga aspekter som datumformat? Är det språket i brevet, mottagarens kultur eller avsändarens kultur som ska styra? Hur gör man om det är flera mottagare?

Peter Sv.

^ Upp till Numeros hemsida.


Senast ändrad 1995-05-08 <numero@nada.kth.se>