| 1. |
- Darulova, Eva, et al.
(författare)
-
Welcome from the chairs
- 2019
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)
|
|
| 2. |
- Aronsson, Markus, 1990, et al.
(författare)
-
Hardware software co-design in Haskell
- 2017
-
Ingår i: Haskell 2017 - Proceedings of the 10th ACM SIGPLAN International Symposium on Haskell, co-located with ICFP 2017. - New York, NY, USA : ACM. ; 52:10, s. 162-173
-
Konferensbidrag (refereegranskat)abstract
- We present a library in Haskell for programming Field Programmable Gate Arrays (FPGAs), including hardware software co-design. Code for software (in C) and hardware (in VHDL) is generated from a single program, along with the code to support communication between hardware and software. We present type-based techniques for the simultaneous implementation of more than one embedded domain specific language (EDSL). We build upon a generic representation of imperative programs that is loosely coupled to instruction and expression types, allowing the individual parts to be developed and improved separately. Code generation is implemented as a series of translations between progressively smaller, typed EDSLs, safeguarding against errors that arise in untyped translations. Initial case studies show promising performance.
|
|
| 3. |
- Aronsson, Markus, 1990, et al.
(författare)
-
Safety at speed: in-place array algorithms from pure functional programs by safely re-using storage
- 2019
-
Ingår i: FHPNC 2019 Proceedings of the 8th ACM SIGPLAN International Workshop on Functional. - New York, NY, USA : ACM. - 9781450368148 ; , s. 34-46
-
Konferensbidrag (refereegranskat)abstract
- We present a purely functional array programming language that offers safe, purely functional and crash-free in-place array transformations. The language supports high-level abstractions for pure and efficient array computations that fully support equational reasoning. We show how to execute selected parts of these computations safely in-place, with the compiler guaranteeing that in-place execution does not change the computation’s result. Correctness is ensured by using an off-the-shelf-theorem prover to discharge safety conditions. Our main contribution is the idea of virtual copies for expressing re-use of arrays, and techniques for verifying their safety, which allow a pure language to include in-place transformations without weakening its transparency or rea- soning power.
|
|
| 4. |
- Aronsson, Markus, 1990, et al.
(författare)
-
Stream Processing for Embedded Domain Specific Languages
- 2014
-
Ingår i: Proceedings of the 26nd 2014 International Symposium on Implementation and Application of Functional Languages. - New York, NY, USA : ACM. - 9781450332842 ; 01, s. 1-12
-
Konferensbidrag (refereegranskat)abstract
- We present a library for expressing digital signal processing (DSP) algorithms using a deeply embedded domain-specific language (EDSL) in Haskell. The library supports definitions in functional programming style, reducing the gap between the mathematical description of streaming algorithms and their implementation. The deep embedding makes it possible to generate efficient C code without any overhead associated with the high-level programming model. The signal processing library is intended to be an extension of the Feldspar EDSL which, until now, has had a rather low-level interface for dealing with synchronous streams. However, the presented library is independent of the underlying expression language, and can be used to extend any pure EDSL for which a C code generator exists with efficient stream processing capabilities. The library is evaluated using example implementations of common DSP algorithms and the generated code is compared to its handwritten counterpart.
|
|
| 5. |
|
|
| 6. |
- Axelsson, Emil, 1978, et al.
(författare)
-
Feldspar: A Domain Specific Language for Digital Signal Processing algorithms
- 2010
-
Ingår i: Eighth ACM/IEEE International Conference on Formal Methods and Models for Codesign. - 9781424478859 ; , s. 169-178
-
Konferensbidrag (refereegranskat)abstract
- A new language, Feldspar, is presented, enabling high-level and platform-independent description of digital signal processing (DSP) algorithms. Feldspar is a pure functional language embedded in Haskell. It offers a high-level dataflow style of programming, as well as a more mathematical style based on vector indices. The key to generating efficient code from such descriptions is a high-level optimization technique called vector fusion. Feldspar is based on a low-level, functional core language which has a relatively small semantic gap to machine-oriented languages like C. The core language serves as the interface to the back-end code generator, which produces C. For very small examples, the generated code performs comparably to hand-written C code when run on a DSP target. While initial results are promising, to achieve good performance on larger examples, issues related to memory access patterns and array copying will have to be addressed.
|
|
| 7. |
- Axelsson, Emil, 1978, et al.
(författare)
-
Feldspar: Application and Implementation
- 2012
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 7241, s. 402-439
-
Konferensbidrag (refereegranskat)abstract
- The Feldspar project aims to develop a domain specific language for Digital Signal Processing algorithm design. From functional descriptions, imperative code (currently C) is generated. The project partners are Ericsson, Chalmers and ELTE, Budapest. The background and motivation for the project have been documented elsewhere [3]. We aim to raise the level of abstraction at which algorithm developers and implementors work, and to generate, from Feldspar descriptions, the kind of code that is currently written by hand. These lecture notes first give a brief introduction to Feldspar and the style of programming that it encourages. Next, we document the implementation of Feldspar as a domain specific language (DSL), embedded in Haskell. The implementation is built using a library called Syntactic that was built for this purpose, but also designed to be of use to other implementors of embedded domain specific languages. We show the implementation of Feldspar in sufficient detail to give the reader an understanding of how the use of the Syntactic library enables the modular construction of an embedded DSL. For those readers who would like to apply these techniques to their own DSL embedded in Haskell, further instructions are given in section 5. The programming examples are available in the CEFP directory of the Feldspar package, version 0.5.0.1: http://hackage.haskell.org/package/ feldspar-language-0.5.0.1 The code can be fetched by running: > cabal unpack feldspar-language-0.5.0.1 All code is written in Haskell, and has been tested using the Glasgow Haskell Compiler (GHC), version 7.0.2, and the packages syntactic-0.8 feldspar-language-0.5.0.1 feldspar-compiler-0.5.0.1
|
|
| 8. |
- Axelsson, Emil, 1978, et al.
(författare)
-
Teaching Hardware Description and Verification
- 2005
-
Ingår i: 2005 International Conference on Microelectronic Systems Education. - 0769523749 ; , s. 119-120
-
Konferensbidrag (refereegranskat)abstract
- We outline the course "Hardware Description and Verification", taught at the department of computing science, and how the course and our research benefit from each other.
|
|
| 9. |
- Axelsson, Emil, 1978, et al.
(författare)
-
The Design and Implementation of Feldspar: An Embedded Language for Digital Signal Processing
- 2011
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783642242755 ; 6647, s. 121-136
-
Konferensbidrag (refereegranskat)abstract
- Feldspar is a domain specific language, embedded in Haskell, for programming digital signal processing algorithms. The final aim of a Feldspar program is to generate low level code with good performance. Still, we chose to provide the user with a purely functional DSL. The language is implemented as a minimal, deeply embedded core language, with shallow extensions built upon it. This paper presents full details of the essential parts of the implementation. Our initial conclusion is that this approach works well in our domain, although much work remains.
|
|
| 10. |
- Axelsson, Emil, 1978, et al.
(författare)
-
The Design and Implementation of Feldspar: an Embedded Language for Digital Signal Processing
- 2010
-
Ingår i: IFL 2010, the 22nd Symposium on Implementation and Application of Functional Languages.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Feldspar is a Domain Specific Language, embedded in Haskell, for programming Digital Signal Processing algorithms. The final aim of a Feldspar program is to generate low level code with good performance. Still, we chose to provide the user with a purely functional DSL. The language is implemented as a minimal, deeply embedded core language, with shallow extensions built upon it. This paper presents full details of the essential parts of the implementation. Our initial conclusion is that this approach works well in our domain, although much work remains.
|
|
| 11. |
- Axelsson, Emil, 1978, et al.
(författare)
-
Using Lava and Wired for Design Exploration
- 2006
-
Ingår i: Proceedings of the sixth international workshop on designing correct circuits, March, Vienna, Mary Sheeran and Tom Melham (editors).
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Lava has been used successfully in structural circuit description and layout generation for FPGAs. It has been demonstrated that Lava is suitable for describing so-called "clever" or adaptive circuits -- circuits whose structure adapts to various properties of their contexts. This can be incorporated quite naturally into the descriptions due to the fact that Lava is embedded in the powerful functional programming language Haskell.The rising problems associated with chip design in the deep sub-micron (DSM) era calls for new methods that are able to account for low-level effects already in higher-level descriptions. In particular, interconnect wires need to be modeled in order to get reliable estimates of non-functional properties, such as delay and power consumption.We are working on a system -- Wired -- which aims to bring the ideas from Lava down to lower levels. What distinguishes Wired from other layout-aware languages is the fact that we are modeling Wires explicitly, and that we can have adaptive descriptions whose structure adapts to accurate estimates of, for example, signal delays in their context.Here we demonstrate a flow for design exploration using parallel prefix circuits \cite{PP} as example. The descriptions start of in Lava, and are then transformed, surprisingly smoothly, into corresponding Wired descriptions. We demonstrate several classic parallel prefix structures as well as a family of new ones.Wired has the capability of performing a number of different signal analyses on the descriptions. We can, for example, analyse for signal flow direction and delay. Our most advanced delay model uses Elmore approximation to appropriately take account of fanout and load capacitance. We will use the available analysis methods to compare the different parallel prefix structures. Hopefully, we will also be able to demonstrate examples of delay-adaptive circuits in time for the DCC workshop.
|
|
| 12. |
- Axelsson, Emil, 1978, et al.
(författare)
-
Wired - a Language for Describing Non-Functional Properties of Digital Circuits
- 2004
-
Ingår i: Proceedings of International Workshop on Designing Correct Circuits. Barcelona, Spain, March 2004.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Increasingly, designers need to estimate non-functional properties such as area, power consumption and timing, even when working at a high level of abstraction, early in the design. In deep sub-micron processes, it is the routing wires that account for most of the power consumption and signal delays. So, information about the wires is vital for controlling non-functional properties. To deal with more and more complex constructions, current design methods and languages strive towards higher and higher levels of abstraction, and provide only very limited possibilities for low-level control. Often, detailed information about wire properties is only available in the very last design stages - after placement and routing. We propose a language, Wired, that aims to bridge this gap in abstraction levels. The main idea is construction with combinators and higher-order connection patterns. The key to the usefulness of this style is that the combinators have both functional and geometric interpretations. This allows us to construct circuits at high-level, without loosing control over lower levels. Wired goes further than previous methods in that it offers more precise and flexible control over the geometry.
|
|
| 13. |
- Axelsson, Emil, 1978, et al.
(författare)
-
Wired: Wire-Aware Circuit Design
- 2005
-
Ingår i: Correct Hardware Design and Verification Methods. - 3540291059 ; 3725, s. 5-19
-
Konferensbidrag (refereegranskat)
|
|
| 14. |
- Björk, Magnus, 1977, et al.
(författare)
-
Exposed Datapath for Efficient Computing
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We introduce FlexCore, which is the first exemplar of a processor based on the FlexSoC processor paradigm. TheFlexCore utilizes an exposed datapath for increased performance. Microbenchmarks yield a performance boost of a factor of two over a traditional five-stage pipeline with the same functional units as the FlexCore.We describe our approach to compiling for the FlexCore.A flexible interconnect allows the FlexCore datapath to bedynamically reconfigured as a consequence of code generation. Additionally, specialized functional units may be introduced and utilized within the same architecture and compilation framework. The exposed datapath requires a wide control word. The conducted evaluation of two micro benchmarks confirms that this increases the instruction bandwidth and memory footprint. This calls for an efficient instruction decoding as proposed in the FlexSoC paradigm.
|
|
| 15. |
|
|
| 16. |
- Bouverot-Dupuis, Mathis, et al.
(författare)
-
Efficient GPU Implementation of Affine Index Permutations on Arrays
- 2023
-
Ingår i: FHPNC 2023 - Proceedings of the 11th ACM SIGPLAN International Workshop on Functional High-Performance and Numerical Computing, Co-located with ICFP 2023. ; , s. 15-28
-
Konferensbidrag (refereegranskat)abstract
- Optimal usage of the memory system is a key element of fast GPU algorithms. Unfortunately many common algorithms fail in this regard despite exhibiting great regularity in memory access patterns. In this paper we propose efficient kernels to permute the elements of an array. We handle a class of permutations known as Bit Matrix Multiply Complement (BMMC) permutations, for which we design kernels of speed comparable to that of a simple array copy. This is a first step towards implementing a set of array combinators based on these permutations.
|
|
| 17. |
- Claessen, Koen, 1975, et al.
(författare)
-
SAT-Solving in Practice
- 2008
-
Ingår i: 9th International Workshop on Discrete Event Systems.
-
Konferensbidrag (refereegranskat)
|
|
| 18. |
- Dévai, Gergely, et al.
(författare)
-
Efficient Code Generation from the High-level Domain-specific Language Feldspar for DSPs
- 2010
-
Ingår i: ODES-8: 8th Workshop on Optimizations for DSP and Embedded Systems, workshop associated with IEEE/ACM International Symposium on Code Generation and Optimization (CGO).
-
Konferensbidrag (refereegranskat)abstract
- Software for digital signal processors (DSPs) is traditionally highly hardware-dependent and hence porting it to new processors usually requires significant design effort. In this paper we present Feldspar (Functional Embedded Language for DSP and Parallelism), an embedded, high-level, domain-specific language for DSP algorithm design and the compilation techniques we developed for generating C code from specifications written in Feldspar. While Feldspar allows description of algorithms on specification level, we show that with the right set of abstractions and transformations this high level, functional specification can be transformed into C code that is comparable or better than reference, hand-crafted C language implementations. The Feldspar compiler is highly modular and plugin-based, hence future hardware-specific plugins will enable automatic generation of efficient, hardware-specific code. This approach enables the encapsulation of knowledge of hardware completely in the compiler and thus allows description of algorithms in completely hardware-independent, portable manner.
|
|
| 19. |
- Dreyer, D., et al.
(författare)
-
Special issue dedicated to ICFP 2014: Editorial
- 2016
-
Ingår i: Journal of Functional Programming. - : Cambridge University Press (CUP). - 1469-7653 .- 0956-7968. ; 26
-
Tidskriftsartikel (refereegranskat)abstract
- The 19th ACM SIGPLAN International Conference on Functional Programming (ICFP) took place on September 1–3, 2014 in Gothenburg, Sweden. After the conference, the programme committee, chaired by Manuel Chakravarty, selected several outstanding papers and invited their authors to submit to this special issue of JFP. We acted as editors for these submissions. This issue includes the six accepted papers, each of which provides substantial new material beyond the original conference version. The selected papers demonstrate both the quality and the breadth of the conference, with a strong emphasis on types and their applications, and ranging from compilation methods through contract verification to homotopy type theory.
|
|
| 20. |
- Dybdal, Martin, 1987, et al.
(författare)
-
Low-Level Functional GPU Programming for Parallel Algorithms
- 2016
-
Ingår i: FHPC 2016- Proceedings of the 5th International Workshop on Functional High-Performance Computing. - New York, NY, USA : ACM. - 9781450344333 ; , s. 31-37
-
Konferensbidrag (refereegranskat)abstract
- We present a Functional Compute Language (FCL) for low-levelGPU programming. FCL is functional in style, which allows foreasy composition of program fragments and thus easy prototypingand a high degree of code reuse. In contrast with projects such asFuthark, Accelerate, Harlan, Nessie and Delite, the intention is notto develop a language providing fully automatic optimizations, butinstead to provide a platform that supports absolute control of theGPU computation and memory hierarchies. The developer is thusrequired to have an intimate knowledge of the target platform, as isalso required when using CUDA/OpenCL directly.FCL is heavily inspired by Obsidian. However, instead of relyingon a multi-staged meta-programming approach for kernel generationusing Haskell as meta-language, FCL is completely selfcontained,and we intend it to be suitable as an intermediate languagefor data-parallel languages, including data-parallel parts ofhigh-level array languages, such as R, Matlab, and APL.We present a type-system and a dynamic semantics suitablefor understanding the performance characteristics of both FCL andObsidian-style programs. Our aim is that FCL will be useful as aplatform for developing new parallel algorithms, as well as a target languagefor various code-generators targeting GPU hardware.
|
|
| 21. |
|
|
| 22. |
|
|
| 23. |
- Hughes, John, 1958, et al.
(författare)
-
FlexSoC: Combining Flexibility and Efficiency in SoC Designs
- 2003
-
Ingår i: Proceedings of 21st Norchip Conference. ; Riga, Latvia, s. 52-55
-
Konferensbidrag (refereegranskat)abstract
- The FlexSoC project aims at developing a designframework that makes it possible to combine the computational speed and energy-efficiency of specialized hardware accelerators with the flexibility of programmable processors. FlexSoC approaches this problem by defining auniform programming interface across the heterogeneousstructure of processing resources. This paper justifies ourapproach and also discusses the central research issueswe will focus on in the areas of VLSI design, computerarchitecture, and programming and verification.
|
|
| 24. |
- Lindström Claessen, Koen, 1975, et al.
(författare)
-
Expressive array constructs in an embedded GPU kernel programming language
- 2012
-
Ingår i: Conference Record of the Annual ACM Symposium on Principles of Programming Languages. - New York, NY, USA : ACM. - 0730-8566. - 9781450311175 ; , s. 21-30
-
Konferensbidrag (refereegranskat)abstract
- Graphics Processing Units (GPUs) are powerful computing devices that with the advent of CUDA/OpenCL are becomming useful for general purpose computations. Obsidian is an embedded domain specific language that generates CUDA kernels from functional descriptions. A symbolic array construction allows us to guarantee that intermediate arrays are fused away. However, the current array construction has some drawbacks; in particular, arrays cannot be combined efficiently. We add a new type of push arrays to the existing Obsidian system in order to solve this problem. The two array types complement each other, and enable the definition of combinators that both take apart and combine arrays, and that result in efficient generated code. This extension to Obsidian is demonstrated on a sequence of sorting kernels, with good results. The case study also illustrates the use of combinators for expressing the structure of parallel algorithms. The work presented is preliminary, and the combinators presented must be generalised. However, the raw speed of the generated kernels bodes well.
|
|
| 25. |
- Lindström Claessen, Koen, 1975, et al.
(författare)
-
Functional Hardware Description in Lava
- 2003
-
Ingår i: The fun of programming - edited by Jeremy Gibbons and Oege de Moor. - 1403907722
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
| 26. |
|
|
| 27. |
- Lindström Claessen, Koen, 1975, et al.
(författare)
-
SAT-Solving in Practice
- 2008
-
Ingår i: 9th International Workshop on Discrete Event Systems, WODES' 08; Goteborg; Sweden; 28 May 2008 through 30 May 2008. - 9781424425921 ; , s. 61-67
-
Konferensbidrag (refereegranskat)abstract
- Satisfiability solving, the problem of deciding whether the variables of a propositional formula can be assigned in such a way that the formula evaluates to true, is one of the classic problems in computer science. It is of theoretical interest because it is the canonical NP-complete problem. It is of practical interest because modern SAT-solvers can be used to solve many important and practical problems. In this tutorial paper, we show briefly how such SAT-solvers are implemented, and point to some typical applications of them. Our aim is to provide sufficient information (much of it through the reference list) to kick-start researchers from new fields wishing to apply SAT-solvers to their problems.
|
|
| 28. |
- Lindström Claessen, Koen, 1975, et al.
(författare)
-
SAT-Solving in Practice, with a Tutorial Example from Supervisory Control
- 2009
-
Ingår i: Discrete Event Dynamic Systems. - : Springer Science and Business Media LLC. - 0924-6703 .- 1573-7594. ; 19:4, s. 495-524
-
Tidskriftsartikel (refereegranskat)abstract
- Satisfiability solving, the problem of deciding whether the variables of a propositional formula can be assigned in such a way that the formula evaluates to true, is one of the classic problems in computer science. It is of theoretical interest because it is the canonical NP-complete problem. It is of practical interest because modern SAT-solvers can be used to solve many important and practical problems. In this tutorial paper, we show briefly how such SAT-solvers are implemented, and point to some typical applications of them. Our aim is to provide sufficient information (much of it through the reference list) to kick-start researchers from new fields wishing to apply SAT-solvers to their problems. Supervisory control theory originated within the control community and is a framework for reasoning about a plant to be controlled and a specification that the closed-loop system must fulfil. This paper aims to bridge the gap between the computer science community and the control community by illustrating how SAT-based techniques can be used to solve some supervisory control related problems.
|
|
| 29. |
|
|
| 30. |
- Saline, Maria, 1979, et al.
(författare)
-
A large ‘discovery’ experiment: Gender Initiative for Excellence (Genie) at Chalmers University of Technology
- 2021
-
Ingår i: QRB Discovery. - : Cambridge University Press (CUP). - 2633-2892. ; 2
-
Forskningsöversikt (refereegranskat)abstract
- Sweden tops gender equality rankings, but Swedish academia is still lacking women in top positions. To address gender inequality in its faculty, Chalmers University of Technology has invested 300 million SEK (30 million Euros) over 10 years in Gender initiative for Excellence (Genie). Genie aims to increase the university’s success and excellence via gender equality efforts. In this editorial, we want to share insights on explicit efforts during Genie’s first 2.5 years with the goal to inspire and advise other universities and researchers.
|
|
| 31. |
- Sarkar, Abhiroop, 1991, et al.
(författare)
-
Hailstorm : A Statically-Typed, Purely Functional Language for IoT Applications
- 2020
-
Ingår i: ACM International Conference Proceeding Series. - New York, NY, USA : ACM.
-
Konferensbidrag (refereegranskat)abstract
- With the growing ubiquity of Internet of Things (IoT), more complex logic is being programmed on resource-constrained IoT devices, almost exclusively using the C programming language. While C provides low-level control over memory, it lacks a number of high-level programming abstractions such as higher-order functions, polymorphism, strong static typing, memory safety, and automatic memory management. We present Hailstorm, a statically-typed, purely functional programming language that attempts to address the above problem. It is a high-level programming language with a strict typing discipline. It supports features like higher-order functions, tail-recursion and automatic memory management, to program IoT devices in a declarative manner. Applications running on these devices tend to be heavily dominated by I/O. Hailstorm tracks side effects like I/O in its type system using resource types. This choice allowed us to explore the design of a purely functional standalone language, in an area where it is more common to embed a functional core in an imperative shell. The language borrows the combinators of arrowized FRP, but has discrete-time semantics. The design of the full set of combinators is work in progress, driven by examples. So far, we have evaluated Hailstorm by writing standard examples from the literature (earthquake detection, a railway crossing system and various other clocked systems), and also running examples on the GRiSP embedded systems board, through generation of Erlang.
|
|
| 32. |
- Sarkar, Abhiroop, 1991, et al.
(författare)
-
Higher-Order Concurrency for Microcontrollers
- 2021
-
Ingår i: MPLR 2021 - Proceedings of the 18th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes. - New York, NY, USA : ACM. - 9781450386753 ; , s. 26-36
-
Konferensbidrag (refereegranskat)abstract
- Programming microcontrollers involves low-level interfacing with hardware and peripherals that are concurrent and reactive. Such programs are typically written in a mixture of C and assembly using concurrent language extensions (like FreeRTOS tasks and semaphores), resulting in unsafe, callback-driven, error-prone and difficult-to-maintain code. We address this challenge by introducing SenseVM - a bytecode-interpreted virtual machine that provides a message-passing based higher-order concurrency model, originally introduced by Reppy, for microcontroller programming. This model treats synchronous operations as first-class values (called Events) akin to the treatment of first-class functions in functional languages. This primarily allows the programmer to compose and tailor their own concurrency abstractions and additionally, abstracts away unsafe memory operations, common in shared-memory concurrency models, thereby making microcontroller programs safer, composable and easier-to-maintain. Our VM is made portable via a low-level bridge interface, built atop the embedded OS - Zephyr. The bridge is implemented by all drivers and designed such that programming in response to a software message or a hardware interrupt remains uniform and indistinguishable. In this paper we demonstrate the features of our VM through an example, written in a Caml-like functional language, running on the nRF52840 and STM32F4 microcontrollers.
|
|
| 33. |
- Sarkar, Abhiroop, 1991, et al.
(författare)
-
Synchron - An API and Runtime for Embedded Systems
- 2022
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - 1868-8969. - 9783959772259 ; 222, s. 17:1-17:28
-
Konferensbidrag (refereegranskat)abstract
- Programming embedded systems applications involve writing concurrent, event-driven and timing-aware programs. Traditionally, such programs are written in low-level machine-oriented programming languages like C or Assembly. We present an alternative by introducing Synchron, an API that offers high-level abstractions to the programmer while supporting the low-level infrastructure in an associated runtime system and one-time-effort drivers. Embedded systems applications exhibit the general characteristics of being (i) concurrent, (ii) I/O–bound and (iii) timing-aware. To address each of these concerns, the Synchron API consists of three components - (1) a Concurrent ML (CML) inspired message-passing concurrency model, (2) a message-passing–based I/O interface that translates between low-level interrupt based and memory-mapped peripherals, and (3) a timing operator, syncT , that marries CML’s sync operator with timing windows inspired from the TinyTimber kernel. We implement the Synchron API as the bytecode instructions of a virtual machine called SynchronVM. SynchronVM hosts a Caml-inspired functional language as its frontend language, and the backend of the VM supports the STM32F4 and NRF52 microcontrollers, with RAM in the order of hundreds of kilobytes. We illustrate the expressiveness of the Synchron API by showing examples of expressing state machines commonly found in embedded systems. The timing functionality is demonstrated through a music programming exercise. Finally, we provide benchmarks on the response time, jitter rates, memory, and power usage of the SynchronVM.
|
|
| 34. |
- Sheeran, Mary, 1959, et al.
(författare)
-
A new approach to the design of optimal parallel prefix circuits
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Parallel prefix is one of the fundamental algorithms in computer science. Parallel prefix networks are used to compute carries in fast addition circuits, and have a number of other applications, including the computation of linear recurrences and loop parallelization. A new construction, called Slices, for fan-out-constrained depth size optimal (DSO) parallel prefix circuits is presented. The construction encompasses the largest possible number of inputs for given depth and fan-out. It improves on previous approaches that produce DSO networks with constrained fan-out by encompassing more inputs for a given depth. Even when compared with parallel prefix circuits with unbounded fan-out, the construction provides a new family of circuits that are both small and reasonably shallow. We present the construction, which is composed of recursively defined blocks, and derive a recurrence for the maximum number of inputs that can be processed for a given fan-out and depth.We also show how a DSO network built according to our construction can be cropped, to produce a new DSO network with the same depth and fan-out, but fewer inputs. Thus, we can produce a DSO network for given depth, fan-out and number of inputs, provided such a network exists. We believe that we are the first to be able to do this. The resulting networks are compared to others with both bounded and unbounded fan-out.
|
|
| 35. |
- Sheeran, Mary, 1959
(författare)
-
Describing and reasoning about circuits that are almost regular
- 2003
-
Ingår i: Correct hardware design and verification methods : 12th IFIP WG 10.5 Advanced Research Working Conference, CHARME 2003, L'Aquila, Italy, October 21-24, 2003 : proceedings / Daniel Geist, Enrico Tronci, (Eds.).. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783540203636 ; , s. 4-18
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
| 36. |
|
|
| 37. |
|
|
| 38. |
- Sheeran, Mary, 1959
(författare)
-
Functional and dynamic programming in the design of parallel prefix networks
- 2010
-
Ingår i: Journal of Functional Programming. - 1469-7653 .- 0956-7968. ; 21:1, s. 59-114
-
Tidskriftsartikel (refereegranskat)abstract
- A parallel prefix network of width n takes n inputs, a1, a2, . . ., an, and computes each yi = a1 ○ a2 ○ ⋅ ⋅ ⋅ ○ ai for 1 ≤ i ≤ n, for an associative operator ○. This is one of the fundamental problems in computer science, because it gives insight into how parallel computation can be used to solve an apparently sequential problem. As parallel programming becomes the dominant programming paradigm, parallel prefix or scan is proving to be a very important building block of parallel algorithms and applications. There are many different parallel prefix networks, with different properties such as number of operators, depth and allowed fanout from the operators. In this paper, ideas from functional programming are combined with search to enable a deep exploration of parallel prefix network design. Networks that improve on the best known previous results are generated. It is argued that precise modelling in a functional programming language, together with simple visualization of the networks, gives a new, more experimental, approach to parallel prefix network design, improving on the manual techniques typically employed in the literature. The programming idiom that marries search with higher order functions may well have wider application than the network generation described here.
|
|
| 39. |
- Sheeran, Mary, 1959
(författare)
-
Functional Programming and Hardware Design: Still Interesting after All These Years
- 2015
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - New York, NY, USA : ACM. - 0730-8566. ; 50:9, s. 165-165
-
Konferensbidrag (refereegranskat)abstract
- Higher order functions provide an elegant way to express algorithms designed for implementation in hardware [1, 6-9]. By showing examples of both classic and new algorithms, I will explain why higher order functions deserve to be studied. Next, I will consider the extent to which ideas from functional programming, and associated formal verification methods, have influenced hardware design in practice [3-5, 10]. What can we learn from looking back? You might ask "Why are methods of hardware design still important to our community?". Maybe we should just give up? One reason for not giving up is that hardware design is really a form of parallel programming. And here there is still a lot to do! Inspired by Blelloch's wonderful invited talk at ICFP 2010 [2], I still believe that functional programming has much to offer in the central question of how to program the parallel machines of today, and, more particularly, of the future. I will briefly present some of the areas where I think that we are poised to make great contributions. But maybe we need to work harder on getting our act together?
|
|
| 40. |
- Sheeran, Mary, 1959
(författare)
-
Generating Fast Multipliers Using Clever Circuits
- 2004
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 3540237380 ; 3312, s. 6-20
-
Tidskriftsartikel (refereegranskat)abstract
- New insights into the general structure of partial product reduction trees are combined with the notion of clever circuits to give a novel method of writing simple but flexible and highly-parameterised data-path generators.
|
|
| 41. |
|
|
| 42. |
|
|
| 43. |
|
|
| 44. |
|
|
| 45. |
- Svenningsson, Josef, 1976, et al.
(författare)
-
Counting and Occurrence Sort for GPUs using an Embedded Language
- 2013
-
Ingår i: The 2nd ACM SIGPLAN Workshop on Functional High-Performance Computing, FHPC'13. - New York, NY, USA : ACM. - 9781450323819 ; 48:12, s. 37-45
-
Konferensbidrag (refereegranskat)abstract
- This paper investigates two sorting algorithms: counting sort and avariation, occurrence sort, which also removes duplicate elements,and examines their suitability for running on the GPU. The dupli-cate removing variation turns out to have a natural functional, data-parallel implementation which makes it particularly interesting forGPUs.The algorithms are implemented in Obsidian, a high-level do-main specific language for GPU programming.Measurements show that our implementations in many casesoutperform the sorting algorithm provided by the library Thrust.Furthermore, occurrence sort is another factor of two faster thanordinary counting sort. We conclude that counting sort is an impor-tant contender when considering sorting algorithms for the GPU,and that occurrence sort is highly preferable when applicable. Wealso show that Obsidian can produce very competitive code.
|
|
| 46. |
- Svensson, Joel Bo, 1979, et al.
(författare)
-
A language for hierarchical data parallel design-space exploration on GPUs
- 2016
-
Ingår i: Journal of Functional Programming. - 1469-7653 .- 0956-7968. ; 26
-
Tidskriftsartikel (refereegranskat)abstract
- Graphics Processing Units (GPUs) offer potential for very high performance; they are also rapidly evolving. Obsidian is an embedded language (in Haskell) for implementing high performance kernels to be run on GPUs. We would like to have our cake and eat it too; we want to raise the level of abstraction beyond CUDA code and still give the programmer control over the details relevant to kernel performance. To that end, Obsidian provides array representations that guarantee elimination of intermediate arrays while also using the type system to model the hierarchy of the GPU. Operations are compiled very differently depending on what level of the GPU they target, and as a result, the user is gently constrained to write code that matches the capabilities of the GPU. Thus, we implement not Nested Data Parallelism, but a more limited form that we call Hierarchical Data Parallelism. We walk through case-studies that demonstrate how to use Obsidian for rapid design exploration or auto-tuning, resulting in performance that compares well to the hand-tuned kernels used in Accelerate and NVIDIA Thrust.
|
|
| 47. |
- Svensson, Joel Bo, 1979, et al.
(författare)
-
Design Exploration through Code-Generating DSLs
- 2014
-
Ingår i: Communications of the ACM. - : Association for Computing Machinery (ACM). - 0001-0782 .- 1557-7317. ; 57:6, s. 56-63
-
Tidskriftsartikel (refereegranskat)abstract
- DOMAIN-SPECIFIC LANGUAGES (DSLS) make programs shorter and easier to write. They can be stand-alone- for example, LaTeX, Makefiles, and SQL-or they can be embedded in a host language. You might think that DSLs embedded in high-level languages would be abstract or mathematically oriented, far from the nittygritty of low-level programming. This is not the case. This article demonstrates how high-level embedded DSLs (EDSLs) really can ease low-level programming. There is no contradiction. A gentle introduction to EDSLs can be found in the previous article in this series: "Domain-specific.
|
|
| 48. |
- Svensson, Joel Bo, 1979, et al.
(författare)
-
Design exploration through code-generating DSLs
- 2014
-
Ingår i: Queue. - : Association for Computing Machinery (ACM). - 1542-7749 .- 1542-7730. ; 12:4, s. 40-52
-
Tidskriftsartikel (refereegranskat)abstract
- DSLs (domain-specific languages) make programs shorter and easier to write. They can be stand-alone - for example, LaTeX, Makefiles, and SQL - or they can be embedded in a host language. You might think that DSLs embedded in high-level languages would be abstract or mathematically oriented, far from the nitty-gritty of low-level programming. This is not the case. This article demonstrates how high-level EDSLs (embedded DSLs) really can ease low-level programming. There is no contradiction.
|
|
| 49. |
- Svensson, Joel Bo, 1979, et al.
(författare)
-
GPGPU Kernel Implementation and Refinement using Obsidian
- 2010
-
Ingår i: ICCS 2010 conference proceedings; Amsterdam, NETHERLANDS, MAY 31-JUN 02, 2010. - : Elsevier BV. - 1877-0509. ; 1:1, s. 2059-2068
-
Konferensbidrag (refereegranskat)abstract
- Obsidian is a domain specific language for data-parallel programming on graphics processors (GPUs). It is em-bedded in the functional programming language Haskell. The user writes code using constructs familiar from Haskell(like map and reduce), recursion and some specially designed combinators for combining GPU programs. NVIDIACUDA code is generated from these high level descriptions, and passed to the nvcc compiler [1]. Currently, weconsider only the generation of single kernels, and not their coordination.This paper is focussed on how the user should work with Obsidian, starting with an obviously correct (or well-tested) description of the required function, and refining it by the introduction of constructs to give finer control of thecomputation on the GPU. For some combinators, this approach results in CUDA code with satisfactory performance,promising increased productivity, as the high level descriptions are short and uncluttered. But for other combinators,the performance of generated code is not yet satisfactory. Ways to tackle this problem and plans to integrate Obsidianwith another higher-level embedded language for GPU programming in Haskell are briefly discussed.
|
|
| 50. |
- Svensson, Joel Bo, 1979, et al.
(författare)
-
GPGPU Kernel Implementation using an Embedded Language: a Status Report
- 2010
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Obsidian is a domain specific language for general purpose computations on graphics processing units (GPUs) embedded Haskell. This report present examples of GPU kernels written in Obsidian as well as parts of the current implementation of Obsidian. The goal with Obsidian is to raise the level of abstraction for the programmer while not scarifying performance. The kind of decisionsand tradeoffs considered by a GPU kernel implementer should be easy to make and change in Obsidian.
|
|
