Categories
Explore project

Ergonomic & Practical Effect Systems

Project type: Explore Project

Ergonomic & Practical Effect Systems

Summary

Effect systems are currently a hot research subject in type theory. Yet many effect systems, whilst powerful, are very complicated to use, particularly by programmers that are not experts at type theory. Effect systems with inference can provide useful guarantees to programming languages, while being simple enough to be used in practice by everyday programmers.

Building on the Boolean unification-based polymorphic effect system in the Flix programming language, we want to pursue two practical short-term objectives: to (a) improve the quality of effect error messages, and to (b) develop techniques to improve the performance of Boolean unification and effect inference. Thus laying the foundation for a more ambitious objective: The Futhark programming language supports a form of referentially transparent in-place updates, controlled by a system of uniqueness types inspired by Clean, but which is too limited in the presence of polymorphic higher-order functions. Recasting the type system in terms of effects, based on the one in Flix, might provide a more intuitive system.

A unique aspect of this project is that it brings together two programming language researchers, one from Aarhus and one from Copenhagen, who are both working on full-blown programming language implementations.

Value Creation

We address value creation following the three outlined categories:

Scientific Value: We see two clear publishable scientific contributions: (a) new techniques to improve the performance of Boolean unification and (b) new applications of type and effect systems based on Boolean unification.

Capacity Building: Flix and Futhark are the two the major academic efforts towards building new programming languages in Denmark. Bringing the two research groups together will facilitate knowledge sharing and technology transfer; enabling both projects to thrive and grow even further. This unique opportunity exists because both languages are based on similar technology and because they do not compete in the same space. Success for one is not at the expense of the other, and they can rise together.

Business and Societal Value: A significant amount of research effort has been expended on designing effect systems. Despite widespread belief that such systems can lead to safer programs, few systems have been implemented in real-world programming languages. By focusing on improving the ergonomics, we want to make these technologies more accessible. Being the designers of Flix and Futhark, we are in great position to conduct such work. We can show the way for other mainstream programming languages by having real, full-blown implementations.

After decades of relative stagnation, programming languages are now rapidly absorbing features previously only seen in obscure or academic programming languages. Java and C# and prominent examples of originally very orthodox object-oriented languages that have been augmented with concepts from functional programming. We believe that effect systems and other fancy type system features are a logical next step, but before they can be added to mainstream languages, it must be shown that they can be designed and implemented in a form that will be palatable to industrial users. Thus, while Flix and Futhark may or may not be the languages of the future, we believe that our research can help impact the direction of future programming languages by providing solid formal foundations and real-world implementations that others can build on directly or indirectly.

Participants

Project Manager

Magnus Madsen

Associate Professor

Aarhus University
Department of Computer Science

E: magnusm@cs.au.dk

Troels Henriksen

Assistant Professor

University of Copenhagen
Department of Computer Science

Categories
Explore project

Hardware/software Trade-off for the Reduction of Energy Consumption

Project type: Explore Project

Hardware/software Trade-off for the Reduction of Energy Consumption

Summary

Computing devices consume a considerable amount of energy. Within data centers this has an impact on climate change and in small embedded systems, i.e., battery powered devices, energy consumption influences battery life. Implementing an algorithm in hardware (in a chip) is more energy efficient than executing it in software in a processor. Up until recently processor performance and energy efficiency have been good enough to just use software on a standard processor or on a graphic processing unit. However, this performance increase comes to an end and energy-efficient computing systems need domain specific hardware accelerators.

However, the cost of producing a chip is very high. Between fixed hardware and software there is the technology of field-programmable gate arrays (FPGAs). FPGAs are programmable hardware, the algorithm can be changed at runtime. However, FPGAs are less energy efficient than chips. We expect that for some algorithms an FPGA will be more energy efficient than the implementation in software. The research question is whether and how it is possible to reduce energy consumption of IT systems by moving algorithms from software into hardware (FPGAs). We will do this by investigating classic sorting and path-finding algorithms and compare their energy-efficiency and, in addition, their performance. Such results are essential to both data centers as well as embedded systems. However, the hardware design of these accelerators is often complex, and their development is time-consuming and error-prone. Therefore, we need a tool and methodology that enables software engineers to design efficient hardware implementation of their algorithms. We will explore a modern hardware construction language, Chisel. Chisel is a Scala-embedded hardware construction language that allows to describe hardware in a more software-like high-level language. Chisel is the enabling technology to simplify the translation of a program from software into hardware. This project will furthermore investigate the efficiency of using the functional and object-oriented hardware description language Chisel to express algorithms efficiently for execution in FPGAs.

Programs running on a general-purpose computer consume a considerable amount of energy. Some programs can be translated into hardware and executed on an FPGA. This project will explore the trade-offs between executing a program in hardware and executing it in software relative to energy consumption.

Value Creation

Scientific Value
The FPGA and software implementations of path-finding algorithms have recently been evaluated in the lense of performance, e.g., [?], whereas sorting algorithms have also been evaluated on energy consumption, e.g., [2]. Here FPGAs performed better than CPU in many cases and with similar or reduced energy consumption. The language used for implementation is Verilog and C which is then translated to Verilog using Vivado HLS. In this project, we will implement the algorithms in hardware using Chiesl and evaluate their performance and energy consumption. DTU and RUC will advance the research in the design and testing of digital systems for energy saving. Our proposed approach provides a general software engineering procedure that we plan to validate with standard algorithms used in cloud applications. This research will drive the adaption of hardware design methods to the education curriculum towards modern tools and agile methods. 

Capacity Building
The project establish a new collaboration between two Danish Universities and is a first step towards building a more energy-aware profile of the Computer Science laboratory FlexLab, RUC. In return FlexLab make FPGAs available to the research assistants at RUC. Thus, this project will improve visibility of energy-aware design IT systems nationally and international. This project with the cooperation between researchers as DTU and RUC will allow Denmark to take the lead in digital research nd development for reduced energy consumption. The upcoming research positions at RUC will contribute to building RUC’s research capacity, and the project will also recruit new junior researchers directly and in future subsequent projects.

Business Value
The changes in the hardware industry indicates that the use of FPGAs will increase: A few years ago Intel bought Altera -one of the two largest FPGA production companies- to include FPGAs in future versions of their processors. Similar, AMD is aiming to buy Xilinx, the other big FPGA vendor. In addition, one can already rent a server in the cloud from Amazon that includes an FPGA. These changes all points towards that FPGAs are entering mainstream computing. Many mainstream programming languages like C# or Java already include functional features such as lambda expressions or higher-order functions. The more common languages for encoding FPGAs are Verilog, a C inspired language, and VHDL, a Pascal inspired language, Therefore, it may be efficient for mainstream software developers to use a functional language to efficiently implement algorithms in FPGAs and thus both increase performance and reduce the energy consumption. 

Societal Value
Currently ICT consumes approximately 10% of the global electricity and this is estimated to increase to 20% in 2030. Thus, reducing energy consumption of ICT is critical. If successful, this project has the potential to reduce the energy consumption via rephrasing the essential software programs in FPGA units.

Participants

Project Manager

Maja Hanne Kirkeby

Assistant Professor

Roskilde University
Department of People and Technology

E: majaht@ruc.dk

Martin Schoerberl

Associate Professor

Technical University of Denmark
DTU Compute

Mads Rosendahl

Associate Professor

Roskilde Universlty
Department of People and Technology

Thomas Krabben

FlexLab Manager

Roskilde University
Department of People and Technology

Categories
News

Meet Tijs Slaats, who just won a prize for best process mining algorithm

Meet Tijs Slaats, who just won a prize for best process mining algorithm

Tijs is Associate Professor at the Department of Computer Science at the University of Copenhagen and Head of the Business Process Modeling and Intelligence research group. In DIREC, he works on the Bridge project AI and Blockchains for Complex Business Processes.

Tijs’ research interests include declarative and hybrid process technologies, blockchain technologies, process mining, and information systems development.  

He co-invented the flagship declarative Dynamic Condition Response (DCR) Graphs process notation and was a primary driver in its early commercial adoption. In addition, he led the invention and development of the DisCoveR process miner, which was recognized as the best process discovery algorithm in 2021. 

Can you tell us briefly about your research and what value you expect to get from it?
We try to describe processes. It can be basic things that we do as human beings. It could be assembling a car at a factory, but it could also be treating patients at a hospital. If a patient is admitted to a hospital, they need help and treatment.

What it has in common for these examples is that you need to go through a number of steps and activities to reach your goal, and those activities are related to each other. It may be medication that needs to be taken in a certain order.

In our research, we have developed a mathematical method for describing these processes. The reason for doing this is because it gives you the tools to ensure that the process goes the way you want it to.

In the new DIREC project, we take one step further. We have observed that many companies and organizations have large amounts of data on how they have performed their jobs. And we can look at these data and analyze them to see how they actually perform their jobs, because the way many people do their jobs does not necessarily match the way they expect to do it. Maybe they take shortcuts unintentionally.

Our idea is to find these data and analyze them and on that basis we get a model.

It is important that such a model also is understandable to the users so that they can understand how they perform their work. We call this process mining, and it is a reasonably large academic area. Two years ago, I developed an algorithm, and it was in a contest, where you compare which algorithm is most accurate to describe these “logs of behaviour”, and we won the contest.

Read more

What results do you expect from your research?
Our cooperation with industry is particularly important. In the project, we collaborate with the company Gekkobrain https://gekkobrain.com, which works with DevOps, and they are interested in analyzing large ERP systems and in finding tools that can optimize a system and find abnormalities. These systems are quite complex, so it is important to be able to identify where things are going wrong.

Gekkobrain has a lot of data because they work with large companies that have huge amounts of log data, and these systems are so complex that it adds some extra challenges for our algorithms. To get access to such complex data is an important perspective.

How can your research make a difference to companies and society?
The biggest impact of our work and models is that you can gain insight into how you perform your work. It gives you an objective picture of what has been done.

Companies can use it to find out if there are places where work processes are performed in an inappropriate way and thus avoid the extra costs.

Can you tell us about your background and how you ended up working with this research area?
I initially got a Bachelor degree in Information & Communication Technology from Fontys University of Professional Education, then worked in industry where I led the webshop development team of a Dutch e-commerce provider and acted as project leader on the implementation of our product for two major customers; Ferrari and Hewlett Packard.

I decided to move to Denmark after meeting my (Danish) wife, at the time I was already considering pursuing further education, while my wife was fairly settled in Denmark, so it made sense for me to be the one to move.

I got my MSc and PhD degrees at the IT University of Copenhagen. There I became interested in the field of business process modeling because it allows me to combine foundational theoretical research with very concrete industrial applications. Process mining in particular provides really interesting challenges because it requires learned models to be understandable for business users, something that has only recently come into focus in the more general field of AI. 

After a short postdoc at ITU I accepted a tenure-track assistant professorship at DIKU, which was a very good opportunity because it offers a (near) permanent position for relatively junior researchers. At the time this was uncommon in Denmark.