Type Systems for Optimizing Stack-based Code

We give a uniform type-systematic account of a number of optimizations and the underlying analyses for a bytecode-like stack-based low-level language, including analysis soundness proofs and strongest analysis (principal type inference) algorithms. Specifically, we treat dead store instructions, load-pop pairs, duplicating load instructions, store-load pairs. The load-pop pairs and store-load pairs elimination optimizations are built on top of bidirectional analyses, facilitating correct elimination of instruction pairs spanning across basic block boundaries. As a result, no assumptions are needed about input code (it need not be the compiled form of a high-level source program, the stack need not be empty at basic block boundaries and not even need it be checked for safety before the analysis). The soundness proofs and strongest analysis algorithms are simple and uniform.     

AutoGen: Easing model management through two levels of abstraction

Due to its extensive potential applications, model management has attracted many research interests and gained great progress. To provide easy-to-use interfaces, we have proposed a graph transformation-based model management approach that provides intuitive interfaces for manipulation of graphical data models. The approach consists of two levels of graphical operators: low-level customizable operators and high-level generic operators, both of which consist of a set of graph transformation rules. Users need to program or tune the low-level operators for desirable results. To further improve the ease-of-use of the graphical model management, automatic generation of low level of operators is highly desirable. The paper formalizes specifications of low- and high-level operators and proposes a generator to automatically transform high-level operators into low-level operators upon specific input data models. Based on graph transformation theoretical foundation, we design an algorithm for the generator to automatically produce low-level operators from input data models and mappings according to a high-level operator. The generator, called AutoGen, therefore eliminates many tedious specifications and thus eases the use of the graphical model management system.     

Complete worst-case execution time analysis of straight-line hard real-time programs

In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a hard real-time program is addressed. The analysis is focused on straight-line code (without loops and recursive function calls) which is quite commonly found in synthesised code for embedded systems. A comprehensive timing analysis system covering both low-level (assembler instruction level) as well as high-level aspects (programming language level) is presented. The low-level analysis covers all speed-up mechanisms used for modern superscalar processors: pipelining, instruction-level parallelism and caching. The high-level analysis uses the results from the low-level to compute the final estimate on the WCET. This is done by a heuristic for searching the longest really executable path in the control flow, based on the functional dependencies between various program parts.     

A feature binding computational model for multi-class object categorization and recognition

We propose a feature binding computational model based on the cognitive research findings. Feature integration theory is widely approved on the principles of the binding problem, which supplies the roadmap for our computational model. We construct the learning procedure to acquire necessary pre-knowledge for the recognition network on reasonable hypothesis–maximum entropy. With the recognition network, we bind the low-level image features with the high-level knowledge. Fundamental concepts and principles of conditional random fields are employed to model the feature binding process. We apply our model to current challenging problems, multi-label image classification and object recognition, and evaluate it on the benchmark image databases to demonstrate that our model is competitive to the state-of-the-art method.     

Using information obtained in the course of program execution for improving the quality of data type reconstruction in decompilation

Methods of improving the decompilation quality, that is, the reconstruction of a program in a high-level language from a given program in a low-level language, are considered. Decompilation is considered as a reverse engineering problem; problems of decompilation quality are examined, and metrics for assessing this quality are proposed.     

利用逻辑编程方法进行形式化的网络安全策略验证

高级安全策略又称为安全需求,低级策略配置是高级策略的实现,正确的低级策略配置必须能够满足安全需求。网络安全取决于低级策略配置的正确性,由于策略配置异常复杂,并且缺乏准确描述安全需求的方法,这为策略的正确性分析提出了巨大的挑战。采用逻辑编程方法来分析网络安全策略,通过将低级策略配置、高级策略、漏洞信息等元素转化为逻辑程序,将网络中所有可能存在的访问与安全需求进行对比,判定策略配置是否满足安全需求,并给出所有不满足安全需求的策略配置。     

Efficient parallel execution of irregular recursive programs

Programs whose parallelism stems from multiple recursion form an interesting subclass of parallel programs with many practical applications. The highly irregular shape of many recursion trees makes it difficult to obtain good load balancing with small overhead. We present a system, called REAPAR, that executes recursive C programs in parallel on SMP machines. Based on data from a single profiling run of the program, REAPAR selects a load-balancing strategy that is both effective and efficient and it generates parallel code implementing that strategy. The performance obtained by REAPAR on a diverse set of benchmarks matches that published for much more complex systems requiring high-level problem-oriented explicitly parallel constructs. A case study even found REAPAR to be competitive to handwritten (low-level, machine-oriented) thread-parallel code     

Compiling scientific code using partial evaluation

The partial evaluation approach, which transforms a high-level program into a low-level program that is specialized for a particular application, exposing the parallelism inherent in the underlying numerical computation, is discussed. A prototype compiler that uses partial evaluation is described. Experiments with the compiler have shown that for an important class of numerical programs, partial evaluation can provide marked performance improvements: speedups over conventionally compiled code that range from seven times faster to 91 times faster have been measured. By coupling partial evaluation with parallel scheduling techniques, the low-level parallelism inherent in a computation can be exploited on heavily pipelined or parallel architectures. The approach has been demonstrated by applying a parallel scheduler to a partially evaluated program that simulates the motion of a nine-body solar system     

The role of memory and concepts in learning

The extent to which concepts, memory, and planning are necessary to the simulation of intelligent behavior is a fundamental philosophical issue in Artificial Intelligence. An active and productive segement of the AI community has taken the position that multiple low-level agents, properly organized, can account for high-level behavior. Empirical research on these questions with fully operational systems has been restricted to mobile robots that do simple tasks. This paper recounts experiments with Hoyle, a system in a cerebral, rather than a physical, domain. The program learns to perform well and quickly, often outpacing its human creators at two-person, perfect information board games. Hoyle demonstrates that a surprising amount of intelligent behavior can be treated as if it were situation-determined, that often planning is unnecessary, and that the memory required to support this learning is minimal. Concepts, however, are crucial to this reactive program's ability to learn and perform.     

Annotations for Portable Intermediate Languages

This paper identifies high-level program properties that can be discovered by static analysis in a compiler front end, and that are useful for classical low-level optimizations. We suggest how intermediate language code could be annotated to convey these properties to the code generator.I wish to thank David Watt and Andrew Kennedy for their detailed comments and suggestions. Simon Peyton Jones and Norman Ramsey commented on an early draft of this paper. The anonymous reviewers made suggestions that improved the contents and the presentation of the paper.     

Dynamical consistency in hierarchical supervisory control

A hierarchical control theory is presented founded upon the trace-dynamical consistency property, which is an extension of the notion of dynamical consistency (DC) to the supervisory case of automata with disablable transitions. Partitions of a system state space are considered for which both the trace-DC and the (non-blocking) in-block controllability (IBC) conditions hold; it is shown that low-level non-blocking controllable languages project up to such languages in the high-level system, and that, when the (non-blocking) IBC condition also holds, high-level non-blocking controllable languages map down to such languages in the low-level system. It is demonstrated that the resulting pairs of low-level and high-level languages satisfy a version of the hierarchical consistency condition found in the existing language-based hierarchical supervisory control theory. The structures produced in the formulation of hierarchical control in this paper permit efficient regulator design (and, in particular, repeated re-design) for hierarchy-compatible language specifications; such specifications consist of low-level languages whose maximal controllable sublanguages are realizable by a combination of a high-level (possibly history-dependent) regulator and a set of (state-dependent) low-level regulators (specified block-wise). An algorithm is proposed which facilitates the construction of (non-blocking) IBC partitions of systems with vocalized states. Examples are presented, including a material transfer line with re-entrant flow and a double queue     

A compositional natural semantics and Hoare logic for low-level languages

The advent of proof-carrying code has generated significant interest in reasoning about low-level languages. It is widely believed that low-level languages with jumps must be difficult to reason about because of being inherently non-modular. We argue that this is untrue. We take it seriously that, unlike statements of a high-level language, pieces of low-level code are multiple-entry and multiple-exit. And we define a piece of code as consisting of either a single labelled instruction or a finite union of pieces of code. Thus we obtain a compositional natural semantics and a matching Hoare logic for a basic low-level language with jumps. By their simplicity and intuitiveness, these are comparable to the standard natural semantics and Hoare logic of While. The Hoare logic is sound and complete wrt the semantics and allows for compilation of proofs of the Hoare logic of While.     

Intelligent Control for Robotic Rehabilitation after Stroke

The paper presents a new control approach to robot-assisted rehabilitation for stroke patients. The control architecture is represented in terms of a hybrid system model combining a high-level and a low-level assistive controller. The high-level controller is designed to monitor the progress and safety of the rehabilitation task. The high-level controller also makes decisions on the modification of the task that might be needed for the therapy. A design of a low-level assistive controller that provides robotic assistance for an upper arm rehabilitation task and works in coordination with the proposed high-level controller is discussed. Experimental results on unimpaired participants are presented to demonstrate the efficacy of both the high-level and low-level assistive controllers.     

High-Level Computer Architecture

Associated with each programming language is a computer architecture that executes programs in that language. If the language is a low-level instruction set, the associated computer architecture is a low-level von Neumann architecture; if the language is high-level, the associated architecture is high-level. The internal structure of a high-level architecture reflects the constructs of the high-level language. The articles in this special issue deal with high-level computer architecture.     

Behavior and Instantiation of High–Level Net Processes

Processes for high-level nets N are often defined as processes of the low-level net Flat(N) which is obtained from N via the well-known flattening construction. This low-level notion of processes for high-level nets, however, is not really adequate, because the high-level structure is completely lost. For this reason we have introduced in a previous paper a new notion of high-level net processes for high-level nets which captures the high-level structure. The key notion is a high-level occurrence net K, which generalizes the well-known notion of occurrence nets from low-level to high-level nets. In contrast to the low-level case we consider high-level occurrence nets together with a set of initial markings of the input places. In this paper we show under which conditions the behavior of low-level occurrence nets and processes can be generalized to the high-level case. A key notion is the instantiation L of a high-level occurrence net K, where L is a low-level subnet of the flattening Flat(K) with isomorphic net structures of L and K. One of our main results characterizes under which conditions a high-level occurrence net - and hence a high-level net process - has unique and nonoverlapping instantiations and can be represented by the union of all its instantiations.     

SafeGPU: Contract- and library-based GPGPU for object-oriented languages

Using GPUs as general-purpose processors has revolutionized parallel computing by providing, for a large and growing set of algorithms, massive data-parallelization on desktop machines. An obstacle to their widespread adoption, however, is the difficulty of programming them and the low-level control of the hardware required to achieve good performance. This paper proposes a programming approach, SafeGPU, that aims to make GPU data-parallel operations accessible through high-level libraries for object-oriented languages, while maintaining the performance benefits of lower-level code. The approach provides data-parallel operations for collections that can be chained and combined to express compound computations, with data synchronization and device management all handled automatically. It also integrates the design-by-contract methodology, which increases confidence in functional program correctness by embedding executable specifications into the program text. We present a prototype of SafeGPU for Eiffel, and show that it leads to modular and concise code that is accessible for GPGPU non-experts, while still providing performance comparable with that of hand-written CUDA code. We also describe our first steps towards porting it to C#, highlighting some challenges, solutions, and insights for implementing the approach in different managed languages. Finally, we show that runtime contract-checking becomes feasible in SafeGPU, as the contracts can be executed on the GPU.     

A Compositional Natural Semantics and Hoare Logic for Low-Level Languages

The advent of proof-carrying code has generated significant interest in reasoning about low-level languages. It is widely believed that low-level languages with jumps must be difficult to reason about by being inherently non-modular. We argue that this is untrue. We take it seriously that, differently from statements of a high-level language, pieces of low-level code are multiple-entry and multiple-exit. And we define a piece of code to consist of either a single labelled instruction or a finite union of pieces of code. Thus we obtain a compositional natural semantics and a matching Hoare logic for a basic low-level language with jumps. By their simplicity and intuitiveness, these are comparable to the standard natural semantics and Hoare logic of While. The Hoare logic is sound and complete wrt. the semantics and allows for compilation of proofs of the Hoare logic of While.     

Heap-Bounded Assembly Language

We present a first-order linearly typed assembly language, HBAL, that allows the safe reuse of heap space for elements of different types. Linear typing ensures the single pointer property, disallowing aliasing but allowing safe, in-place-update compilation of programming languages. We prove that HBAL is sound for a low-level untyped model of the machine, using a satisfiability relation that captures when a location correctly models a value of some type. This interpretation is closer to the machine than previous abstract machines used for typed assembly language models, and we separate typing of the store from an untyped operational semantics of programs, as would be required for proof-carrying code. Our ultimate aim is to design a family of assembly languages that have high-level typing features for expressing resource-bound constraints. We want to link the assembly-level with high-level languages expressing similar constraints, to provide end-to-end guarantees and a viable framework for proof-carrying code. HBAL is a first exemplifying step in this direction. It is designed as a target low-level language for Hofmann's LFPL language. Programs written in LFPL run in a bounded amount of heap space, and this property carries over when they are compiled to HBAL: the resulting program does not allocate store or assume an external garbage collector. Following LFPL, we include a special diamond resource type that stands for a unit of heap space of uncommitted type.