Efficient Abstractions for GPGPU Programming

General purpose (GP)GPU programming demands to couple highly parallel computing units with classic CPUs to obtain a high performance. Heterogenous systems lead to complex designs combining multiple paradigms and programming languages to manage each hardware architecture. In this paper, we present tools to harness GPGPU programming through the high-level OCaml programming language. We describe the SPOC library that allows to handle GPGPU subprograms (kernels) and data transfers between devices. We then present how SPOC expresses GPGPU kernel: through interoperability with common low-level extensions (from Cuda and OpenCL frameworks) but also via an embedded DSL for OCaml. Using simple benchmarks as well as a real world HPC software, we show that SPOC can offer a high performance while efficiently easing development. To allow better abstractions over tasks and data, we introduce some parallel skeletons built upon SPOC as well as composition constructs over those skeletons.     

Efficient virtual machine support of runtime structural reflection

Increasing trends towards adaptive, distributed, generative and pervasive software have made object-oriented dynamically typed languages become increasingly popular. These languages offer dynamic software evolution by means of reflection, facilitating the development of dynamic systems. Unfortunately, this dynamism commonly imposes a runtime performance penalty. In this paper, we describe how to extend a production JIT-compiler virtual machine to support runtime object-oriented structural reflection offered by many dynamic languages. Our approach improves runtime performance of dynamic languages running on statically typed virtual machines. At the same time, existing statically typed languages are still supported by the virtual machine.We have extended the .Net platform with runtime structural reflection adding prototype-based object-oriented semantics to the statically typed class-based model of .Net, supporting both kinds of programming languages. The assessment of runtime performance and memory consumption has revealed that a direct support of structural reflection in a production JIT-based virtual machine designed for statically typed languages provides a significant performance improvement for dynamically typed languages.     

Static type information to improve the IDE features of hybrid dynamically and statically typed languages

The flexibility offered by dynamically typed programming languages has been appropriately used to develop specific scenarios where dynamic adaptability is an important issue. This has made some existing statically typed languages gradually incorporate more dynamic features to their implementations. As a result, there are some programming languages considered hybrid dynamically and statically typed. However, these languages do not perform static type inference on a dynamically typed code, lacking those common features provided when a statically typed code is used. This lack is also present in the corresponding IDEs that, when a dynamically typed code is used, do not provide the services offered for static typing. We have customized an IDE for a hybrid language that statically infers type information of dynamically typed code. By using this type information, we show how the IDE can provide a set of appealing services that the existing approaches do not support, such as compile-time type error detection, code completion, transition from dynamically to statically typed code (and vice versa), and significant runtime performance optimizations. We have evaluated the programmer׳s performance improvement obtained with our IDE, and compared it with similar approaches.     

A Para-Functional Programming Interface for a Parallel Computer Algebra Package

We describe the application of pD, a small para-functional language that we developed as a high-level programming interface for the parallel computer algebra package PACLIB. pD provides several facilities to express parallel algorithms in a flexible way on different levels of abstraction. The compiler translates a pD module into statically typed parallel C code with explicit task creation and synchronization constructs. This target code can be linked with the PACLIB kernel, the multi-processor runtime system of the computer algebra library SACLIB. The parallelization of several computer algebra algorithms on a shared memory multi-processor demonstrates the elegance and efficiency of this approach.     

ParaC:面向GPU平台的图像处理领域的编程框架

GPGPU加速器是当前提高图像处理算法性能的主流加速平台,但是,在GPGPU平台上,同一个程序充分利用硬件体系结构特征和软件特征的优化版本与简单实现版本在性能上会有数量级的差异。GPGPU加速器具有多维多层的大量执行线程和层次化存储体系结构,后者的不同层次具有不同的容量、带宽、延迟和访问权限。同时,图像处理应用程序具有复杂的计算操作、边界处理规则和数据访问特性。因此,任务的并发执行模式、线程的组织方式和并发任务到设备的映射不仅影响到程序的并发度、调度、通信和同步等特性,而且也会影响到访存的带宽、延迟等。因此,GPGPU平台上的程序优化是一个困难、复杂且效率较低的过程。本文提出基于语言扩展的领域编程模型：ParaC。ParaC编程环境利用高层语言扩展描述的程序语义信息,自动分析获取应用程序的操作信息、并发任务间的数据重用信息和访存信息等程序特征,同时结合硬件平台特征,利用基于领域先验知识驱动的编译优化模型自动生成GPGPU平台上的优化代码,最后,利用源源变换编译器生成标准OpenCL程序。本文在测试用例上的实验结果表明,ParaC在GPGPU平台上自动生成的优化版本相对于手工优化版本的加速比最高达到3.22倍,但代码行数只是后者的1.2%到39.68%。     

Design and implementation of an efficient hybrid dynamic and static typing language

Dynamic languages are suitable for developing specific applications where runtime adaptability is an important issue. On the contrary, statically typed languages commonly provide better compile‐time type error detection and more opportunities for compiler optimizations. Because both approaches offer different benefits, there exist programming languages that support hybrid dynamic and static typing. However, the existing hybrid typing languages commonly do not gather type information of dynamic references at compile time, missing opportunities for improving compile‐time error detection and runtime performance. Therefore, we propose some design principles to implement hybrid typing languages that continue gathering type information of dynamically typed references. This type information is used to perform compile‐time type checking of the dynamically typed code and improve its runtime performance. As an example, we have implemented a hybrid typing language following the proposed design principles. We have evaluated the runtime performance and memory consumption of the generated code. The average performance of the dynamic and hybrid typing code is at least 2.53× and 4.51× better than the related approaches for the same platform, consuming less memory resources. Copyright © 2014 John Wiley & Sons, Ltd.     

A practical comparison of two object-oriented languages

The author compares two very different object-oriented programming languages, Flavors and C++, with respect to their merits and how design decisions in each language influence various aspects of programming. The fundamental difference between the two languages is that C++ is strongly typed while Flavors is weakly typed. The comparison follows the completion of two very similar programming projects, one using Flavors and the other C++, allowing direct comparison of software implementation methods in these languages. The projects involved the design of two systems for describing and generating electronic hardware. Differences in implementing all three object-oriented language mechanisms-data abstraction, inheritance, and runtime method determination-are discussed. Typing, memory management, syntax aids and the programming environment are examined. It is concluded that the choice of a language can have a profound influence on program design.<>     

基于Java平台的多语言混合编程

Java领域混合语言编程时代已经到来。本文首先回顾静态类型语言和动态类型语言、命令式语言和声明式语言的基本概念和各自的优缺点,然后介绍Java语言的发展趋势和基于Java Virture Machine的代表性语言Jython、JRuby、Groovy、Scala和Clojure,最后指出软件项目的未来在于混合语言编程,Java仍将是JVM生态系统中的重要组成部分。     

Performance modeling of pipelined linear algebra architectures on FPGAs

The potential design space of FPGA accelerators is very large. The factors that define performance of a particular implementation include the architecture design, number of pipelines, and memory bandwidth. In this paper we present a mathematical model that, based on these factors, calculates the computation time of pipelined FPGA accelerators and allows for quick exploration of the design space without any implementation or simulation. We evaluate the model and its ability to identify design bottlenecks and improve performance. Being the core of many compute-intensive applications, linear algebra computations are the main contributors to their total execution time. Hence, five relevant linear algebra computations are selected, analyzed, and the accuracy of the model is validated against implemented designs.     

Union and intersection types to support both dynamic and static typing

Although static typing provides undeniable benefits for the development of applications, dynamically typed languages have become increasingly popular for specific scenarios. Since each approach offers different benefits, the StaDyn programming language has been designed to support both dynamic and static typing. This paper describes the minimal core of the StaDyn programming language. Its type system performs type reconstruction over both dynamic and static implicitly typed references. A new interpretation of union and intersection types allows statically gathering the type information of dynamic references, which improves runtime performance and robustness. The evaluation of the generated code has shown how our approach offers an important runtime performance benefit.     

一个经过证明的类型化汇编语言的类型检查器

编程语言类型系统的类型安全性可以保证程序运行时满足基本安全属性,包括控制流安全, 内存安全等.类型化编程语言都需要一个类型检查器来检查程序的良类型性,因此编程语言的具体实现是否能保证类型安全性,还依赖类型检查器的可靠性.本文给出一种类型化汇编语言,然后给出相应的类型检查器,并证明了此类型检查器的可靠性,从而保证经过类型检查的汇编程序的安全性.文本的所有工作,包括类型化汇编语言、类型检查器以及相关定理证明,均已在证明辅助工具Coq中实现.本文方法也可用于证明类型化高级语言的类型检查器的可靠性.     

Polymorphic programming I. Another language designed on semantic principles

We wish to illustrate the potential of a thus far little explored avenue of programming language design–-namely the employment of types and routines as values in their own right within the framework of an Algol. In this first paper we pay particular attention to the development of highly orthogonal self-initializing data structures, and to the advantageous expressive power of polymorphism when combined with routine values so as to provide abstract data structures. The emphasis is on the design phase, rather than on the implementation details or precise syntactic structure of the envisaged language. A second, companion paper? discusses the design of a high-level orthogonal abstract architecture intended to support polymorphic languages in which routines are ‘first class’ values. The relationship of the abstract machine architecture to the programming language vis-a-vis the ‘semantic gap’ is then discussed from the viewpoint of compiling programs which are strongly typed while exploiting polymorphism. We feel that polymorphism is essential if truly general purpose programs, software tools, are to be written easily. The research reported herein is an effort towards realizing this goal.     

Performance based design of high-level language-directed computerarchitectures

This paper is concerned with the analytical modeling of computer architectures to aid in the design of high-level language-directed computer architectures. High-level language-directed computers are computers that execute programs in a high-level language directly. The design procedure of these computers are at best described as being ad hoc. In order to systematize the design procedure, we introduce analytical models of computers that predict the performance of parallel computations on concurrent computers. We model computers as queueing networks and parallel computations as precedence graphs. The models that we propose are simple and lead to computationally efficient procedures of predicting the performance of parallel computations on concurrent computers. We demonstrate the use of these models in the design of high-level language-directed computer architectures.     

一种用于Java虚拟机的类型化低级语言

为了能够减小运算系统的需信任计算基础、描述较小粒度的安全策略，目前的研究倾向于从程序设计语言和编译器入手来提高软件的安全性．基于以上研究背景设计了一种类型化的低级语言TLL,TLL是一种为Java虚拟机即时编译器设计的类型安全中间语言，以构造一个具有更小需信任计算基础的Java虚拟机系统为目的．TLL的类型系统基于多态的类型化λ演算，它具有丰富的表现力且能够编码各种高级语言的抽象．基于TLL的一个虚拟机原型系统已经实现，它可以作为实现一个高安全且面向多种源语言的运行时系统的起点．     

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 complete and efficient CUDA-sharing solution for HPC clusters

In this paper we detail the key features, architectural design, and implementation of rCUDA, an advanced framework to enable remote and transparent GPGPU acceleration in HPC clusters. rCUDA allows decoupling GPUs from nodes, forming pools of shared accelerators, which brings enhanced flexibility to cluster configurations. This opens the door to configurations with fewer accelerators than nodes, as well as permits a single node to exploit the whole set of GPUs installed in the cluster. In our proposal, CUDA applications can seamlessly interact with any GPU in the cluster, independently of its physical location. Thus, GPUs can be either distributed among compute nodes or concentrated in dedicated GPGPU servers, depending on the cluster administrator’s policy. This proposal leads to savings not only in space but also in energy, acquisition, and maintenance costs. The performance evaluation in this paper with a series of benchmarks and a production application clearly demonstrates the viability of this proposal. Concretely, experiments with the matrix–matrix product reveal excellent performance compared with regular executions on the local GPU; on a much more complex application, the GPU-accelerated LAMMPS, we attain up to 11x speedup employing 8 remote accelerators from a single node with respect to a 12-core CPU-only execution. GPGPU service interaction in compute nodes, remote acceleration in dedicated GPGPU servers, and data transfer performance of similar GPU virtualization frameworks are also evaluated.     

A language and system for the construction and tuning of parallel programs

The programming of efficient parallel software typically requires extensive experimentation with program prototypes. To facilitate such experimentation, any programming system that supports rapid prototyping of parallel programs should provide high-level language primitives with which programs can be explicitly, statically, or dynamically tuned with respect to performance and reliability. Such language primitives should be able to refer conveniently to the information about the executing program and the parallel hardware required for tuning. Such information may include monitoring data about the current or previous program or even hints regarding appropriate tuning decisions. Language primitives and an associated programming system for program tuning are presented. The primitives and system have been implemented, and have been tested with several parallel applications on a network of Unix workstations.<>     

Memory management of safety-critical hard real-time systems designed in SystemJ

SystemJ is a programming language based on the Globally Asynchronous Locally Synchronous (GALS) Model of Computation (MoC) used to design safety critical hard real-time systems. SystemJ uses the Java programming language as the “host” language, for carrying out data computations, because Java provides clearly defined operational semantics, type and memory safety in the form of the Garbage Collector(GC), which help with formal functional verification. The same GC, which helps in functional verification, makes Worst Case Reaction Time (WCRT)¹ analysis challenging. Any WCRT analysis framework for GALS programs needs to consider the operations performed by the host language. It has been shown that the worst case time estimates for garbage collection cycles are in seconds, whereas the program’s WCRT itself is in micro-seconds. These pessimistic estimates render the WCRT analysis framework ineffective. In order to overcome this problem, we develop a compiler assisted memory management technique for applications written in SystemJ. The SystemJ MoC plays the central role in the proposed technique. The SystemJ MoC allows clearly demarcating the state boundaries of the program, which in turn allows us to partition the heap, at compile time, into two distinct areas: (1) the memory area called the permanent heap, which holds objects that are alive throughout the life time of the application, and (2) the memory area used to hold all other objects, called the transient heap. The size of these memory areas are bounded statically. Furthermore, the memory allocation and reclaim procedures are simple load and pointer reset operations, respectively, which are guaranteed to complete within a bounded number of clock-cycles, thereby alleviating the need for large pessimistic WCRT bounds obtained due to the GC. Experimental results also show that the proposed approach is approximately three times faster, in terms of memory allocation times as compared to standard real-time GC approaches.     

The Green language type system

A programming language that considers basic values and classes as objects brings more opportunities of code reuse and it is easier to use than a language that does not support this feature. However, popular statically typed object-oriented languages do not consider classes as first-class objects because this concept is difficult to integrate with static type checking. They also do not consider basic values as objects for sake of efficiency. This article presents the Green language type system which supports classes as classless objects and offers a mechanism to treat basic values as objects. The result is a reasonably simple type system which is statically typed and easy to implement. It simplifies several other language mechanisms and prevents any infinite regression of metaclasses.     

OCCAM 2: an overview from a software engineering perspective

The programming language OCCAM has been developed for the design and implementation of systems of concurrent processes communicating over channels. It is primarily intended for use as a programming language for the Inmos transputer. This paper has two aims: to review the major features of OCCAM, and to show how the language relates to various stages of the software development process. It also reviews some of the decisions in the design of the language in the light of the criteria outlined in the introductory paper to this series on high-level languages.