There are numerous methods of formally defining the semantics of computer languages. Each method has been designed to fulfil a different purpose. For example, some have been designed to make reasoning about languages as easy as possible; others ...

Dataflow languages are widely used for programming real-time embedded systems. They offer high level abstraction above hardware, and are amenable to program analysis and optimisation. This paper addresses the challenge of verifying parallel program transformations in the context of dynamic dataflow models, where the scheduling behaviour and the amount of data each actor computes may depend on values only known at runtime. We present a Linear Temporal Logic (LTL) model checking approach to verify a dataflow program transformation, using three LTL properties to identify cyclostatic actors in dynamic dataflow programs. The workflow abstracts dataflow actor code to Fiacre specifications to search for counterexamples of the LTL properties using the Tina model checker. We also present a new refactoring tool for the Orcc dataflow programming environment, which applies the parallelising transformation to cyclostatic actors. Parallel refactoring using verified transformations speedily improves FPGA performance, e.g.15.4 × speedup with 16 actors.

This paper decomposes the algorithmic parameters that affect the accuracy and parallel run times of mean shift segmentation. Following Comaniciu and Meer [1], rather than perform calculations in the feature space of the image, the joint spatial-range domain is represented by the image space, with feature space information associated with each point. We report parallel speedup and segmentation accuracy using a standardised segmentation dataset and the Probabilistic Rand index (PRI) accuracy measure. Changes to the algorithmic parameters are analysed and a sweet spot between PRI and run time is found. Using a range window radius of 20, spatial window radius of 10 and threshold of 50, the PRI is improved by 0.17, an increase of 34% which is comparable to state of the art. Mean shift clustering run time is reduced by 97% with parallelism, a speedup of 32 on a 64-core CPU.

Specialized FPGA implementations can deliver higher performance and greater power efficiency than embedded CPU or GPU implementations for real-time image processing. Programming challenges limit their wider use, because the implementation of FPGA architectures at the register transfer level is time consuming and error prone. Existing software languages supported by high-level synthesis (HLS), although providing a productivity improvement, are too general purpose to generate efficient hardware without the use of hardware-specific code optimizations. Such optimizations leak hardware details into the abstractions that software languages are there to provide, and they require knowledge of FPGAs to generate efficient hardware, such as by using language pragmas to partition data structures across memory blocks. This article presents a thorough account of the Rathlin image processing language (RIPL), a high-level image processing domain-specific language for FPGAs. We motivate its design, based on higher-order algorithmic skeletons, with requirements from the image processing domain. RIPL’s skeletons suffice to elegantly describe image processing stencils, as well as recursive algorithms with nonlocal random access patterns. At its core, RIPL employs a dataflow intermediate representation. We give a formal account of the compilation scheme from RIPL skeletons to static and cyclostatic dataflow models to describe their data rates and static scheduling on FPGAs. RIPL compares favorably to the Vivado HLS OpenCV library and C++ compiled with Vivado HLS. RIPL achieves between 54 and 191 frames per second (FPS) at 100MHz for four synthetic benchmarks, faster than HLS OpenCV in three cases. Two real-world algorithms are implemented in RIPL: visual saliency and mean shift segmentation. For the visual saliency algorithm, RIPL achieves 71 FPS compared to optimized C++ at 28 FPS. RIPL is also concise, being 5x shorter than C++ and 111x shorter than an equivalent direct dataflow implementation. For mean shift segmentation, RIPL achieves 7 FPS compared to optimized C++ on 64 CPU cores at 1.1, and RIPL is 10x shorter than the direct dataflow FPGA implementation.

SUMMARY Predicting the resources that are consumed by a program component is crucial for many parallel or distributed systems. In this context, the main resources of interest are execution time, space and communication/synchronisation costs. There has recently been significant progress in resource analysis technology, notably in type‐based analyses and abstract interpretation. At the same time, parallel and distributed computing are becoming increasingly important. This paper synthesises progress in both areas to survey the state‐of‐the‐art in resource analysis for parallel and distributed computing. We articulate a general model of resource analysis and describe parallel/distributed resource analysis together with the relationship to sequential analysis. We use three parallel or distributed resource analyses as examples and provide a critical evaluation of the analyses. We investigate why the chosen analysis is effective for each application and identify general principles governing why the resource analysis is effective. Copyright © 2011 John Wiley & Sons, Ltd.

The first thing that you will notice about this book is the clunky how-foreigners-speak-English title.And the second is the clunky illustration style.Of course, the word "clunky" demonstrates either my high-mindedness or my pomposity.Either way, these tropes really got in the way of my taking this book as seriously as it deserved."Comic" books on programming languages actually have a long pedigree.Kaufman's A FORTRAN Coloring Book has a Dr Seuss-ish feel.I used Alcock's Illustrating Basic (1977) for many years to teach non-specialists with the BBC Microcomputer.In our own noble discipline, Friedman's The Little LISPer (1974) predates both.In turn, this has spawned Friedman and Felleisen's The Little Schemer (1998) and Little MLer (1998).These older books have a gently whimsical feel.In contrast, I found Learn You a Haskell. . .considerably more abrasive in tone.Weak puns abound, as do geek culture references, for example to Mission Impossible and Star Trek and Terry Pratchett and spaghetti westerns."Stuff" is "cool."The "maximum" function is "awesome."We take a journey to "the top of Monad Mountain."Perhaps, the target readership will warm to this. 1 Luckily, for me at any rate, the author does not maintain this style throughout: most of the book is thoughtful and well-written.I think the illustrations also lack the charm of those in the earlier books.At best, they are mildly cute.At worst, they are offensive, in particular the scantily clad, curvaceous woman on p. 102 accompanying a phone book example, which only contains female names.Indeed, one of the few other representations of women, among a plethora of men and animals, is the "old lady" on p. 95.Really, sexism is not funny.This is 21st century: gender neutrality should be taken for granted in academic computing.Now, there is a generic problem with books about specific programming languages, or perhaps a family of problems.Do they assume that the reader already knows how to program in some other language?If so, which language?If not, then do they seek to teach some pedagogy of programming?If so, then which pedagogy?Learn You a Haskell. . . is aimed at readers with imperative programming experience in, say C++, Java, or Python.At the start, there is a very brief summary of key functional programming concepts from an imperative perspective.Thereafter, the book dives straight into interactive GHCi use and is driven by Haskell constructs.Thus, no clear discipline is offered to marshal an initial myriad of techniques to solve substantial problems.Of course, this is a fault of many functional programming texts, my own included.Overall, though, I think this book might prove hard going for self-study except for experienced programmers.Nonetheless, the book is well suited to accompany a taught course on Haskell, offering a strong and systematic emphasis throughout on the central notions of types and higher order constructs.Topics in functional programming, such as recursion, type polymorphism,

This paper proposes a modelling and verification approach for data transmission over a multichannel wireless local area network (WLAN). The approach uses typed first-order logic as a specification language. We analyse a system which transmits data securely in the presence of the classic Man in The Middle (MitM) attack using Alloy. We develop a methodology for representing secure message exchange on a multi-channel WLAN which uses a changeable array and indices, instead of the message itself so that we can avoid both passive and active MitM attacks. We analyse the model for vulnerabilities and specify assertions for secure data transmission over a multichannel WLAN.

The definitive version can be found at : http://onlinelibrary.wiley.com/ Copyright Wiley [Full text of this article is not available in the UHRA]

Computational GRIDs potentially offer low-cost, readily available, and large-scale high-performance platforms. For the parallel execution of programs, however, computational GRIDs pose serious challenges: they are heterogeneous and have hierarchical and often shared interconnects, with high and variable latencies between clusters. This paper investigates whether a programming language with high-level parallel coordination and a distributed shared memory (DSM) model can deliver good and scalable performance on a range of computational GRID configurations. The high-level language Glasgow parallel Haskell (GpH) abstracts over the architectural complexities of the computational GRID, and we have developed GRID-GUM2, a sophisticated grid-specific implementation of GpH, to produce the first high-level DSM parallel language implementation for computational Grids. We report a systematic performance evaluation of GRID-GUM2 on combinations of high/low and homogeneous/heterogeneous computational GRIDS. We measure the performance of a small set of kernel parallel programs representing a variety of application areas, two parallel paradigms, and ranges of communication degree and parallel irregularity. We investigate GRID-GUM2's performance scalability on medium-scale heterogeneous and high-latency computational GRIDs and analyze the performance with respect to the program characteristics of communication frequency and degree of irregular parallelism.

There is a high demand for correctness for safety critical systems, often requiring the use of formal verification. Simple, well-understood scheduling strategies ease verification but are often very inefficient. In contrast, efficient concurrent schedulers are often complex and hard to reason about. This paper shows how the temporal logic of action (TLA) can be used to formally reason about a well-understood scheduling strategy in the process of implementing a more efficient one. This is achieved by formally verifying that the efficient strategy preserves all properties, in particular the behaviour, of the simpler strategy. The approach is illustrated with the Hume programming language, which is based on concurrent rich automata. We introduce an efficient extension to the Hume scheduler, and prove that it preserves the behaviour of the standard Hume scheduler.

ABSTRACT. Wegner and Eberbach[Weg04b] have argued that there are fundamental lim-itations to Turing Machines as a foundation of computability and that these can be over-come by so-called superTuring models such as interaction machines, the picalculus and the $-calculus. In this paper we contest Weger and Eberbach claims. 1.

Programming" framework, Yampa.If you like little languages, you'll appreciate how useful Haskell is for embedded domain specific languages.It may be even more useful now that Template Haskell is in the works.

Abstract. The close association between higher order functions (HOFs) and algorithmic skeletons is a promising source of automatic parallelisation of programs. A theorem proving approach to discovering HOFs in functional programs is presented. Our starting point is proof planning, an automated theorem proving technique in which high-level proof plans are used to guide proof search. We use proof planning to identify provably correct transformation rules that introduce HOFs. The approach has been implemented in the λ Clam proof planner and tested on a range of examples. The work was conducted within the context of a parallelising compiler for Standard ML.

Algorithmic skeletons are abstractions from common patterns of parallel activity which offer a high degree of reusability for developers of parallel algorithms. Their close association with higher order functions (HOFs) makes functional languages, with their strong transformational properties, excellent vehicles for skeleton-based parallel program development. However, using HOFs in this way raises substantial problems of identification of useful HOFs within a given application and of resource allocation on target architectures. We present the design and implementation of a parallelising compiler for Standard ML which exploits parallelism in the familiar $map$ and $fold$ HOFs through skeletons for processor farms and processor trees, respectively. The compiler extracts parallelism automatically and is target architecture independant. HOF execution within a functional language can be nested in the sense that one HOF may be passed and evaluated during the execution of another HOF. We are able to exploit this by nesting our parallel skeletons in a processor topology which matches the structure of the Standard ML source. However, where HOF arguments result from partially applied functions, free variable bindings must be identified and communicated through the corresponding skeleton hierarchy to where those arguments are actually applied. We describe the analysis leading from input Standard ML through HOF instantiation and backend compilation to an executable parallel program. We also present an overview of the runtime system and the execution model. Finally, we give parallel performance figures for several example programs, of varying computational loads, on the Linux-based Beowulf, IBM SP/2, Fujitsu AP3000 and Sun StarCat 15000 MIMD parallel machines. These demonstrate good cross-platform consistency of parallel code behaviour.

Polymorphic types in programming languages facilitate code reuse, increase reliability and reduce semantic errors in programs. Hindley–Milner type inference forms a strong basis for checking polymorphic types but is less well suited to explaining them, as it introduces intermediate constructs that relate poorly to a programmer's understanding of the program. We report an experiment into expert human type explanation and uncover a simple set of rules for human-like explanations. We present a type explanation system based on these rules rather than Hindley–Milner inference. The system uses a new $H$ inference algorithm to annotate types with explanations and is designed to produce succinct, non-repetitive explanations with minimal reference to artefacts of mechanized type inference.

The close association between higher order functions and algorithmic skeletons is a promising source of automatic parallelisation of programs. An approach to automatically synthesizing higher order functions from functional programs through proof planning is presented Our work has been conducted within the context of a parallelising compiler for SML, with the objective of exploiting parallelism latent in potential higher order function use in programs.

The understanding of polymorphic typechecking and type errors is poorly supported by contemporary functional language implementations. Here, a novel visualisation of functions and their types is presented based on the generation of function specific icons with graphical type representations which change dynamically as functions are applied. This visualisation has been implemented for a Standard ML subset within a graphical environment in which function combinations are constrained by type matching.

We have been developing techniques for deriving parallel implementations of vision algorithms from prototypes written in a functional language (SML). Initially, we analysed simple, well understood algorithms to allow the prototyping methodology to be investigated in a predictable environment. Subsequently, we have extended our approach to more difficult cases such as edge tracking which present problems for parallel system development. Here we demonstrate the power and generality of our approach to parallel algorithm development by a representative set of vision algorithms encoded in SML. 1 Introduction Functional programming is an excellent basis for general system development [6]. In contemporary functional languages, the combination of canonical data structure representations, pattern matching, case structured functions and recursion enables the construction of succinct programs whose structures correspond closely to those of the data they process. In functional languages, function...

Abstract The construction of a parallel vision system from Standard ML prototypes is presented. The system recognises 3D objects from 2D scenes through edge detection, grouping of edges into straight lines and line junction based model matching. Functional prototyping for parallelism is illustrated through the development of the straight line detection component. The assemblage of the whole system from prototyped components is then considered and its performance discussed.