Software development technology with automatic configuration to classes of image processing problems

A scheme is proposed to develop image processing and analysis software based on the generation of thesaurus tables in the interpreter’s kernel. The scheme is based on the combined features of dynamic libraries and an interpreter with a set of functions for image processing. As a result, the program can be divided into two parts: the first is aimed at professional software developers, and the second at users. The interpreter is able to use extra functions of dynamic libraries. It makes it possible to change the properties of the software without compilation. On the other hand, users can change the graphical interface to improve the convenience of the workplace.     

A mechanically verified language implementation

This paper briefly describes a programming language, its implementation on a microprocessor via a compiler and link-assembler, and the mechanically checked proof of the correctness of the implementation. The programming language, called Piton, is a high-level assembly language designed for verified applications and as the target language for high-level language compilers. It provides executeonly programs, recursive subroutine call and return, stack based parameter passing, local variables, global variables and arrays, a user-visible stack for intermediate results, and seven abstract data types including integers, data addresses, program addresses and subroutine names. Piton is formally specified by an interpreter written for it in the computational logic of Boyer and Moore. Piton has been implemented on the FM8502, a general purpose microprocessor whose gate-level design has been mechanically proved to implement its machine code interpreter. The FM8502 implementation of Piton is via a function in the Boyer-Moore logic which maps a Piton initial state into an FM8502 binary core image. The compiler and link-assembler are both defined as functions in the logic. The implementation requires approximately 36K bytes and 1400 lines of prettyprinted source code in the Pure Lisp-like syntax of the logic. The implementation has been mechanically proved correct. In particular, if a Piton state can be run to completion without error, then the final values of all the global data structures can be ascertained from an inspection of an FM8502 core image obtained by running the core image produced by the compiler and link-assembler. Thus, verified Piton programs running on FM8502 can be thought of as having been verified down to the gate level.This work was supported in part by the Defense Advanced Research Projects Agency under DARPA Orders 6082 and 9151, contract MDA904-87-C-H009.     

嵌入式组态软件脚本解释虚拟机的设计

为了增强嵌入式组态软件的功能,引入一种类似于C语言的脚本.设计一个编译器把该脚本编译成中间代码,采用中间代码的优点是可提高程序运行的速度,也减小了脚本解释程序的设计难度.提出一种仿微处理器结构的脚本虚拟机设计方案,在运行时对中间代码进行解释.虚拟机主要由程序存储器、指令译码器、运算器、程序计数器、控制器以及动态容器组成,其中动态容器的设计是关键,它具有可动态分配内存、自动释放内存等优点,适合于嵌入式操作系统下运行.实验与测试结果表明,该脚本解释虚拟机可满足嵌入式组态软件设计的要求.     

A chosen-plaintext attack on the microsoft BASIC protection

The Microsoft BASIC (MBASIC) interpreter provides a command which protects the program currently in memory by saving it, on disk, in an encrypted format. A user can RUN such a protected program, but cannot access the source program. A chosen-plaintext attack was used to break the encoding; the encryption method could be derived easily from the enciphering of carefully chosen plaintext programs. As a result, a pair of MBASIC programs able to decrypt a protected program for any interpreter was developed. Further, it is shown that a secure system can never be realized, whichever encryption method is used.     

基于子字并行的串行图像处理算法表示方法

多媒体应用程序的一个最突出的特点就是其内在的并行性,要求同时对多个数据单元进行相同的规则操作,这种并行性被称为子字并行。如何让编译器产生有效的并行代码,如何从普通的串行C程序中识别出子字并行指令,是一个前沿性的研究课题。提出了一种用于实现对串行源代码进行显式表示的方法,该方法对数字信号处理领域常用的同步数据流图方法进行改进,结合模式匹配技术,着眼于内层循环,通过扩展规范的模式库,对带模式识别的数据流、控制流进行分析,能够从串行应用程序中自动地提取其固有的子字并行,得到显式的并行化中间表示,基于这种数据流图表示,采用改进的树模式匹配实现子字并行指令选择和代码生成。实验测试表明了该方法的有效性。     

Compilation techniques for a reconfigurable LIW architecture

Matching an application to an architecture in structure and size is a way of achieving higher computation speed. This paper presents a combination of a compiler and a reconfigurable long instruction word (RLIW) architecture as an approach to the matching problem. Configurations suitable for the execution of different parts of a program are determined by a compiler, and code is generated for both reconfiguring the hardware and performing the computation. The RLIW machine, consisting of multiple processing and global data memory modules, effectively utilizes the fine-grained parallelism detected in programs by a compiler. The long word instructions control the operation of processing and memory modules in the system. To reduce the data transfer between processing modules and data memory modules, we provide reconfigurable interconnections among the processing modules which permit direct communication. The compiler uses new techniques, including region scheduling, generation of code for reconfiguration of the system, and memory allocation techniques, to achieve improved performance. Algorithms for packing operations into long word instructions and techniques for effectively assigning memory modules to the operands required by an instruction are developed. Results of the experiments to evaluate the system indicate that speedups of 60–300% can be obtained for both scientific and nonscientific programs. The reconfigurable architecture is responsible for much of the speedup. Also, the results indicate that the major problem of memory bottleneck faced in designing parallel systems is successfully attacked.This paper represents work done while the author was at the University of Pittsburgh     

The Implementation of a High Performance GPGPU Compiler

In this paper we present our experience in developing an optimizing compiler for general purpose computation on graphics processing units (GPGPU) based on the Cetus compiler framework. The input to our compiler is a naïve GPU kernel procedure, which is functionally correct but without any consideration for performance optimization. Our compiler applies a set of optimization techniques to the naive kernel and generates the optimized GPU kernel. Our compiler supports optimizations for GPU kernels using either global memory or texture memory. The implementation of our compiler is facilitated with a source-to-source compiler infrastructure, Cetus. The code transformation in the Cetus compiler framework is called a pass. We classify all the passes used in our work into two categories: functional passes and optimization passes. The functional passes translate input kernels into desired intermediate representation, which clearly represents memory access patterns and thread configurations. A series of optimization passes improve the performance of the kernels by adapting them to the target GPGPU architecture. Our experiments show that the optimized code achieves very high performance, either superior or very close to highly fine-tuned libraries.     

Efficient Sequential Consistency Using Conditional Fences

Among the various memory consistency models, the sequential consistency (SC) model is the most intuitive and enables programmers to reason about their parallel programs the best. Nevertheless, processor designers often choose to support relaxed memory consistency models because the weaker ordering constraints imposed by such models allow for more instructions to be reordered and enable higher performance. Programs running on machines supporting weaker consistency models can be transformed into ones in which SC is enforced. The compiler does this by computing a minimal set of memory access pairs whose ordering automatically guarantees SC. To ensure that these memory access pairs are not reordered, memory fences are inserted. Unfortunately, insertion of such memory fences can significantly slowdown the program. We observe that the ordering of the minimal set of memory accesses that the compiler strives to enforce, is typically already enforced in the normal course of program execution. A study we conducted on programs with compiler inserted memory fences shows that only 8% of the executed instances of the memory fences are really necessary to ensure SC. Motivated by this study we propose the conditional fence mechanism, known as C-Fence that utilizes compiler information to decide dynamically if there is a need to stall at each fence, only stalling when necessary. Our experiments with SPLASH-2 benchmarks show that, with C-Fences and a centralized active table, programs can be transformed to enforce SC incurring only 12% slowdown, as opposed to 43% slowdown using normal fence instructions. Our approach requires very little hardware support (<350 bytes of on-chip-storage) and it avoids the use of speculation and its associated costs. Furthermore, to ameliorate the contention in the centralized active table arising from the increasing number of processors, we also design a distributed active table, which further improves the performance of C-Fence for a larger number of processors.     

基于Harmony的提前编译技术

在开源Java平台Harmony上,设计并实现一种提前(AOT)编译技术.将可执行代码以文件形式存入本地磁盘或远程服务器,在编译时将文件读入虚拟机,对代码做重定位处理,实现异常信息注册及常量区构造,以确保代码的正确运行.运行结果表明,与解释编译技术和即时编译技术相比,该AOT技术能提高Java程序的响应能力,具有较高的编译效率.     

Compilation of Constraint Programs with Noncyclic and Cyclic Dependencies to Procedural Parallel Programs

This paper reports on a compiler for translation of constraint specifications into procedural parallel programs. A constraint program in our system consists of a set of constraints and an input set containing a subset of the variables appearing in the constraints. The compiler described in this paper successfully compiles a substantially larger class of constraint specifications to efficient programs than did its predecessors. In particular the compiler has been extended to generate processor and memory efficient programs for cyclic constraints which can be resolved by computational relaxation methods. The paper first details the basic compilation process for noncyclic constraints. It then describes the additional steps in the compilation process which enable resolution of cyclic constraints to iterative computational processes and illustrates the process using derivation of a parallel program for solution of the Laplace equation as the example.     

Dynamic compilation in the unix environment

A system for dynamic compilation under the Unix operating system is described. The basis of the system is an incremental assembler that can be used statically or during program execution to insert or replace a module in an executable image. All cross-module references are via offets into a run-time symbol table. All generated code is independent of its location or the location of the symbol table. The symbol table and all modules reside in memory segments compatible with the memory allocator malloc() . The symbol table origin is maintained in a processor register. Library procedures allow the assembler (or C compiler) to be called to alter the currently executing program, or to place a stub function which acts as a trap, so that when the stub is invoked it caues a file to be dynamically compiled into the executing program to replace the stub with a bona fide procedure. This facilitates the construction of advanced interactive environments using native code. Some example applications, to Prolog and to incremental compilation, are considered.     

A hybrid implementation of a process-oriented programming language for system simulation

The implementation of a hierarchical, process-oriented programming language for simulation (HSL) is described. It features a hybrid approach, involving the front end of a compiler and the back end of an interpreter. An HSL program is dichotomous in structure. Source statements from each part are translated into three-address code for an abstract machine, and the resulting code is then interpreted. The algorithms and the supportive data structures that effect the translation and interpretation of HSL are detailed. The host language for HSL is C++. HSL is machine independent and can be ported to any machine on which the host language is available. Its initial implementation was carried out on an NCR Tower. More recently, it was transferred to an NCR PC916.     

A portable lisp compiler

The programming language LISP is usually implemented via an interpreter, and a compiler is added later as a LISP program. However, all such production compilers known to the authors produce explicit instructions for the given computer being used. This paper describes the development of a portable LISP compiler in the sense that only Standard LISP functions are used in its definition and the output is a sequence of abstract machine codes, easily mapped to instruction sequences on current computers. The resulting code is quite efficient, demonstrating once again the maxim that most compiler optimization is largely machine independent.     

A Comparison of Co-Array Fortran and OpenMP Fortran for SPMD Programming

Co-Array Fortran, formally called F^––, is a small set of extensions to Fortran 90/95 for Single-Program-Multiple-Data (SPMD) parallel processing. OpenMP Fortran is a set of compiler directives that provide a high level interface to threads in Fortran, with both thread-local and thread-shared memory. OpenMP is primarily designed for loop-level directive-based parallelization, but it can also be used for SPMD programs by spawning multiple threads as soon as the program starts and having each thread then execute the same code independently for the duration of the run. The similarities and differences between these two SPMD programming models are described.Co-Array Fortran can be implemented using either threads or processes, and is therefore applicable to a wider range of machine types than OpenMP Fortran. It has also been designed from the ground up to support the SPMD programming style. To simplify the implementation of Co-Array Fortran, a formal Subset is introduced that allows the mapping of co-arrays onto standard Fortran arrays of higher rank. An OpenMP Fortran compiler can be extended to support Subset Co-Array Fortran with relatively little effort.     

A distributed Prolog system with AND parallelism

Design details and benchmark results are given for a Prolog interpreter that can be executed across a network by using message passing to implement AND-parallelism. The system is simple and easy to use, yet significantly speeds up existing programs. The system hardware is a group of Sun 3/50 workstations connected to a 10-Mb/s Ethernet. The number of machines actually used by the system is determined when it is initialized. The benchmark programs to test the system are a Prolog compiler, a recursive Fibonacci program, an implementation of the standard quicksort algorithm, and a simple chess program     

申威众核处理器访存与通信融合编译优化

申威众核片上多级存储层次是缓解众核“访存墙”的重要结构.完全由软件管理的SPM结构和片上RMA通信机制给应用性能提升带来很多机会,但也给应用程序开发优化与移植提出了很大挑战.为充分挖掘片上存储层次特点提升应用程序性能,同时减轻用户编程优化负担,本文提出了一种多级存储层次访存与通信融合的编译优化方法.该方法首先设计了融合编译指示,将程序高层信息传递给编译器.其次构建了编译优化收益模型并设计了启发式循环优化方案迭代求解框架,并由编译器完成循环优化方案的求解和优化代码的变换.通过编译生成的DMA和RMA批量数据传输操作,将较低存储层次空间中高访问延迟的核心数据批量缓冲进低访问延迟的更高存储层次空间中.在三个典型测试用例上进行了优化实验测试与分析,结果表明本文所提出的优化在性能上与手工优化相当,较未优化版程序性能有显著提升.     

Static and Dynamic Program Compilation by Interpreter Specialization

Interpretation and run-time compilation techniques are increasingly important because they can support heterogeneous architectures, evolving programming languages, and dynamically-loaded code. Interpretation is simple to implement, but yields poor performance. Run-time compilation yields better performance, but is costly to implement. One way to preserve simplicity but obtain good performance is to apply program specialization to an interpreter in order to generate an efficient implementation of the program automatically. Such specialization can be carried out at both compile time and run time.Recent advances in program-specialization technology have significantly improved the performance of specialized interpreters. This paper presents and assesses experiments applying program specialization to both bytecode and structured-language interpreters. The results show that for some general-purpose bytecode languages, specialization of an interpreter can yield speedups of up to a factor of four, while specializing certain structured-language interpreters can yield performance comparable to that of an implementation in a general-purpose language, compiled using an optimizing compiler.     

Compiler support for effective XSL transformation

XML is a markup language used to describe data or documents. The main goal of XML is to facilitate the sharing of data across diverse information systems, especially via the Internet. XML Stylesheet Transformations (XSLT) is a standard approach to describing how to transform an XML document into another data format. The ever‐increasing number of Web technologies being used in our everyday lives commonly employs XSLT to support data exchange among heterogeneous environments, and the associated increasing burdens on XSLT processors have increased the demand for high‐performance XSLT processors. In this paper, we present an XSLT compiler, named Zebu, which can transform an XSLT stylesheet into the corresponding C program. The compiled program can be used to transform documents without the processing of XSLT stylesheets. The results of experimental testing using standard benchmarks show that the proposed XSLT compiler performs well in processing XML transformations. Copyright © 2011 John Wiley & Sons, Ltd.     

Extending type systems in a library: Type-safe XML processing in C++

Type systems built directly into the compiler or interpreter of a programming language cannot be easily extended to keep track of run-time invariants of new abstractions. Yet, programming with domain-specific abstractions could benefit from additional static checking. This paper presents library techniques for extending the type system of C++ to support domain-specific abstractions. The main contribution is a programmable “subtype” relation. As a demonstration of the techniques, we implement a type system for defining type qualifiers in C++, as well as a type system for the XML processing language, capable of, e.g., statically guaranteeing that a program only produces valid XML documents according to a given XML schema.