Werner Kluge Professor (retired since 31 03 2003) wk@informatik.uni-kiel.de ++49-(0)2238) 81-792 (private)

The SAC project Top priority over the last couple of years was given to the implementation of a no-frills functional array processing language SAC (for Single Assignment C). This language supports an APL-like programming style which allows to specify array operations in a dimensionality and shape independent form, using a C-like syntax. SAC programs are compiled to C target code using sophisticated code optimization techniques which, whenever possible, eliminate the generation of intermediate arrays and also include measures to enhance cache utilization. We were able to demonstrate that for a set of benchmark programs the SAC implementation clearly outperforms equivalent HPF-programs both in terms of memory utilization and runtime efficiencys - a message that was well received by the functional community. We have also been able to successfully implement SAC on a shared multiprocessor systems, using sophisticated workload distribution and balancing schemes which require almost no overhead for thread synchronization. Performance figures again were clearly superior to those of equivalent HPF program runs on the same hardware plattform. Interestingly enough, a grant application for this subproject was turned down by DFG (the German Science Foundation) some years ago on the grounds that there was no way that with only two research staff we could achieve what in the FORTRAN world took a small army of people. Actually, we had only one scientific staff and two graduate students doing the job - so much for the peer `experts' who review project proposals. More about SAC can be found under the SAC home page. The pi-RED system Work on our standard reduction system pi-RED has for all practical purposes been completed some time ago. This applicative order graph reducer realizes the reduction semantics of a full-fledged applied Lambda- calculus. The system is fully normalizing, meaning that it does substitutions and reductions under Lambda-binders. Both programming and program execution are realized as fully interactive processes: program construction is aided by a syntax-oriented editor, and syntactically complete programs may be reduced in a step-by-step mode, with intermediate programs being displayed to the user in high-level notation. pi-RED is therefore an excellent tool for program validation, symbolic computations (theorem proving), and also for teaching basic language concepts and their interpretation. It comes with a versatile pattern matching facility that allows to implement rule based computations as well. There are two versions of the system available, the more reliable one interprets abstract machine code and should therefore preferably be used for interactive programming, the other one compiles abstract machine code to C in order to achieve competitive performance for production runs, but contains a few bugs. Links to both versions may be found under pi-RED. Actually, we have been using this system a number of times to teach basic programming techniques in undergraduate courses but also in graduate courses on computer organization to have students prototype, as sets of state transition rules, various abstract machines. Concurrent systems We have also been working on various ways of organizing the concurrent execution of functional | function-based programs on multi-processor machinery. They include the conventional divide-and-conquer approach of exploiting program-inherent concurrency based on a simple but effective dynamic workload distribution and balancing scheme; the concurrent execution of alternative program parts on a speculative basis which involves fairly sophisticated fairness regulation schemes among speculative processes; Our model train system Having taught several times a course on system modelling with Petri nets, it occurred to me that there was an urgent need for students to get some hands-one experience as to what systems with several concurrent activities are all about and how such systems need to be controlled to enforce an orderly overall behavior which meets essential safety and liveness properties. The best possible choice for an experimental system appeared to be a model train system with a sufficiently complex track layout that would allow several trains to be moved about in patterns that need to be carefully coordinated. We have actually built such a system consisting of three circular tracks, each partitioned into several sections (or blocks) that are equipped with several sidings, with interconnecting tracks in between which permit trains to change between any of these circular tracks. Two of the circular tracks are operated unidirectionally, one clockwise, the other counterclockwise, the third track permits trains to move about in both directions. Train traffic is controlled very conventionally by a single workstation connected through a field bussystem to the tracks. It receives in cycles of about 70 msecs data about actual train positions from the tracks, evaluates them, and sends out control codes which apply to the track sections actual voltage levels that drive the locomotives, set switches and signal lights. The idea is to have each of up to eight trains assigned individual schedules which prescribe which tracks they must pass through in which sequence. Particularly the train traffic through the bidirectional track creates all the phenomena that must be dealt with in concurrent systems. The nice part about this system is that actual train positions and train movements are directly visible and that everything happens sufficiently slowly so that a human observer can follow up on what is going on and how critical situations develop and how they can be resolved.. In the lab courses students are typically asked to first develop a coloured Petri net model of the system and then to transform this model into a working control program. More details about the system can be found under system description. wk@informatik.uni-kiel.de Last modified: June 19, 2007