Coping with Java threads

A thread is a basic unit of program execution that can share a single address space with other threads - that is, they can read and write the same variables and data structures. Originally, only assembly programmers used threads. A few older programming languages such as PL/I supported thread concurrency, but newer languages such as C and C++ use libraries instead. Only recently have programming languages again begun to build in direct support for threads. Java and Ada are examples of industry-strength languages for multithreading. The Java thread model has its roots in traditional concurrent programming. As the "real-time specification for Java" sidebar describes, RTSJ attempts to remove some of the limitations relative to real-time applications - primarily by circumventing garbage collection. But RTSJ does not make the language safer. It retains standard Java's threading pitfalls and is a risky candidate for critical concurrent applications.     

On Migrating Threads

Based on the notion of persistent threads in Tycoon (Matthes and Schmidt, 1994), we investigate thread migration as a programming construct for building activity-oriented distributed applications. We first show how a straight-forward extension of a higher-order persistent language can be used to define activities that span multiple (semi-) autonomous nodes in heterogeneous networks. In particular, we discuss the intricate binding issues that arise in systems where threads are first-class language citizens that may access local and remote, mobile and immobile resources.We also describe how our system model can be understood as a promising generalization of the more static architecture of first-order and higher-order distributed object systems. Finally, we give some insight into the implementation of persistent and migrating threads and we explain how to represent bindings to ubiquitous resources present at each node visited by a migrating thread on the network to avoid excessive communication or storage costs.     

Continuation-Passing C, compiling threads to events through continuations

In this paper, we introduce Continuation Passing C (CPC), a programming language for concurrent systems in which native and cooperative threads are unified and presented to the programmer as a single abstraction. The CPC compiler uses a compilation technique, based on the CPS transform, that yields efficient code and an extremely lightweight representation for contexts. We provide a proof of the correctness of our compilation scheme. We show in particular that lambda-lifting, a common compilation technique for functional languages, is also correct in an imperative language like C, under some conditions enforced by the CPC compiler. The current CPC compiler is mature enough to write substantial programs such as Hekate, a highly concurrent BitTorrent seeder. Our benchmark results show that CPC is as efficient, while using significantly less space, as the most efficient thread libraries available.     

Migrant threads on process farms: parallel programming with Ariadne

We present a novel and portable threads-based system for concurrent applications on shared- and distributed-memory environments. The Ariadne system provides stateful user-space threads that can be very effective in medium to coarse grained applications. The interface is the same for uniprocessors and multiprocessors. Sequential programs are readily converted into parallel programs for shared or distributed memory, with low development effort. Ariadne supports the development of customized schedulers, and offers a thread migration capability in distributed environments. Scheduling of computations at the threads level enables both task- and data-driven executions. Thread migration is a useful feature which turns remote memory accesses into local accesses, enables load-balancing and simplifies program development. Ariadne employs a unique runtime stack rewriting mechanism to migrate threads between homogeneous processors. Ariadne currently runs on the SPARC (SunOS 4.x, SunOS 5.x), Sequent Symmetry, Intel Paragon, Silicon Graphics IRIX and IBM RS/6000 environments. We present some examples of Ariadne programs, along with performance measurements. © 1998 John Wiley & Sons, Ltd.     

VCluster: a thread‐based Java middleware for SMP and heterogeneous clusters with thread migration support

Clusters, composed of symmetric multiprocessor (SMP) machines and heterogeneous machines, have become increasingly popular for high‐performance computing. Message‐passing libraries, such as message‐passing interface (MPI) and parallel virtual machine (PVM), are de facto parallel programming libraries for clusters that usually consist of homogeneous and uni‐processor machines. For SMP machines, MPI is combined with multithreading libraries like POSIX Thread and OpenMP to take advantage of the architecture. In addition to existing parallel programming libraries that are in C/C++ and FORTRAN programming languages, the Java programming language presents itself as another alternative with its object‐oriented framework, platform neutral byte code, and ever‐increasing performance. This paper presents a new parallel programming model and a library, VCluster, which implements this model. VCluster is based on migrating virtual threads instead of processes to support clusters of SMP machines more efficiently. The implementation uses thread migration, which can be used in dynamic load balancing. VCluster was developed in pure Java, utilizing the portability of Java to support clusters of heterogeneous machines. Several applications are developed to illustrate the use of this library and compare the usability and performance of VCluster with other approaches. Copyright © 2007 John Wiley & Sons, Ltd.     

An implementation of the SANE Virtual Processor using POSIX threads

The SANE Virtual Processor (SVP) is an abstract concurrent programming model that is both deadlock free and supports efficient implementation. It is captured by the μTC programming language. The work presented in this paper covers a portable implementation of this model as a C++ library on top of POSIX threads. Programs in μTC can be translated to the standard C++ syntax and linked with this library to run on conventional systems. The motivation for this work was to provide an early implementation on conventional processors as well as supporting work from programming FPGA chips to Grids.     

A moving threads processor architecture MTPA

Moving threads is a new kind of approach for multicore processor architectures. Traditionally, each thread stays in the core where it is created, and data is moved from the main memory via caches to each core and thread. In the moving threads approach, each core can access only a certain portion of the main memory via its local memory block, and thus extremely lightweight threads are moved between the cores. As a consequence, all kinds of cache coherence problems and need for read reply messages are eliminated. Also Lamport’s sequential consistency of shared memory multiprocessor systems is achieved for free. In this paper, we propose a processor architecture (MTPA) for the moving threads paradigm. We describe the overall structure, operation, instruction set, and thread management mechanism as well as evaluate the proposed architecture with different functional unit settings with simulations and give early silicon area and power consumption estimates.     

Mobile JikesRVM: A framework to support transparent Java thread migration

Today’s complex applications must face the distribution of data and code among different network nodes. Computation in distributed contexts is demanding increasingly powerful languages and execution environments, able to provide programmers with appropriate abstractions and tools. Java is a wide-spread language that allows developers to build complex software, even distributed, but it cannot handle the migration of computations (i.e. threads), due to intrinsic limitations of many traditional JVMs. After analyzing the approaches in the literature, this paper presents our thread migration framework (called Mobile JikesRVM), implemented on top of the IBM Jikes Research Virtual Machine (RVM): exploiting some of the innovative techniques in the JikesRVM, we implemented an extension of its scheduler that allows applications to easily capture the state of a running thread and makes it possible to restore it elsewhere (i.e. on a different hardware architecture or operating system), but still with a version of the framework installed). Our thread serialization mechanism provides support for both proactive and reactive migration, available also for multi-threaded Java applications, and tools to deal with the problems of resource relocation management. With respect to previous approaches, we implemented Mobile JikesRVM without recompiling its JVM (Java Virtual Machine) source code, but simply extending JikesRVM functionalities with a full Java package to be imported when thread migration is needed.     

Scheduling and admission testing for jitter-constrained periodic threads

We present new admission tests for periodic real-time threads with explicitly stated deadlines scheduled according to the earliest deadline first (EDF) algorithm. In traditional real-time periodic scheduling, the deadline of a periodic thread is conventionally the end of the current period. In contrast, our tests support periodic threads in which the deadline may be earlier than the end of the current period. In the extreme case, the deadline may be specified as identical to the per period execution time, which results in perfectly isochronous periodic threads. The provision of such threads, which we refer to as jitter-constrained threads, helps end-systems to honour jitter as well as throughput-related QoS parameters in distributed multimedia systems. In addition, such threads can reduce end-to-end delay and buffer memory requirements as less buffering is needed to smooth excessive delay jitter.     

Java线程迁移机制的研究

从计算机集群系统实际应用出发,首先对Java线程的状态进行了分析,介绍了目前Java线程迁移机制的几种实现方法：处理源代码、处理字节码和扩展Java虚拟机的实现机制.从3个不同的方面进行了性能分析和比较,得出一个初步的评估.最后提出了一种扩展Java虚拟机方法的改进以及该迁移技术在集群系统中的应用.     

一种基于国产异构众核处理器的C++智能源码转换框架

国产异构众核处理器是我国打破国际技术壁垒,在高性能计算领域取得突破的关键环节.围绕国产超算的软件生态环境建设,采用智能源码转换的方法盘活海量多核架构的遗产代码是加速软件研发效率,推动领域发展的重要途径.针对国产运算核心不支持C++编译的现状,基于开源的ANTLR语言翻译工具,提出了一种面向异构众核处理器的智能化C++语言向C语言转换的辅助框架.该框架聚焦面向对象语言的关键特征,基于抽象语法树,实现了基类和继承类、函数定义、基于标签法的模板实例化以及部分STL库的C语言转换,建立了待转换代码的自动化标注体系,极大地提高了C++代码的转换和移植效率.通过对可衡量的并行计算基准应用BableStream进行自动转换和移植测试,证实了该转换框架的有效性.     

Generation, Optimization, and Evaluation of Multithreaded Code

The recent advent of multithreaded architectures holds many promises: the exploitation of intrathread locality and the latency tolerance of multithreaded synchronization can result in a more efficient processor utilization and higher scalability. The challenge for a code generation scheme is to make effective use of the underlying hardware by generating large threads with a large degree of internal locality without limiting the program level parallelism or increasing latency. Top-down code generation, where threads are created directly from the compiler's intermediate form, is effective at creating a relatively large thread. However, having only a limited view of the code at any one time limits the quality of threads generated. These top-down generated threads can therefore be optimized by global, bottom-up optimization techniques. In this paper, we introduce the Pebbles multithreaded model of computation and analyze a code generation scheme whereby top-down code generation is combined with bottom-up optimizations. We evaluate the effectiveness of this scheme in terms of overall performance and specific thread characteristics such as size, length, instruction level parallelism, number of inputs, and synchronization costs.     

Memory-aware kernel mechanism and policies for improving internode load balancing on NUMA systems

Although nonuniform memory access architecture provides better scalability for multicore systems, cores accessing memory on remote nodes take longer than those accessing on local nodes. Remote memory access accompanied by contention for internode interconnection degrades performance. Properly mapping threads to cores and data accessed to their nodes can substantially improve performance and energy efficiency. However, an operating system kernel's load-balancing activity may migrate threads across nodes, which thus messes up the thread mapping. Besides, subsequent data mapping behavior pays for the cost of page migration to reduce remote memory access. Once unsuitable threads are migrated, it is detrimental to system performance. This paper focuses on improving the kernel's internode load balancing on nonuniform memory access systems. We develop a memory-aware kernel mechanism and policies to reduce remote memory access incurred by internode thread migration. The Linux kernel's load balancing mechanism is modified to incorporate selection policies in the internode thread migration, and the kernel is modified to track the amount of memory used by each thread on each node. With this information, well-designed policies can then choose suitable threads for internode migration. The purpose is to avoid migrating a thread that might incur relatively more remote memory access and page migration. The experimental results show that with our mechanism and the proposed selection policies, the system performance is substantially increased when compared with the unmodified Linux kernel that does not consider memory usage and always migrates the first-fit thread in the runqueue that can be migrated to the target central processing unit.     

CUDA到异构众核架构的线程映射模型

统一计算设备架构(CUDA)程序移植到其他异构众核架构时的线程数不匹配。为此,提出一种层次化的线程映射模型。在第1个映射层次上,将CUDA主机端线程和设备端线程分别映射到目标平台的主核和从核阵列上,在第2个映射层次上,采用线程循环的方法消除协作线程阵列(CTA)中线程间同步操作,将整个CTA映射到从核阵列的一个从核上。实验结果表明,该模型能使CUDA程序在其他异构众核系统上得到有效运行。     

P#: a concurrent Prolog for the .NET framework

We discuss P#, our implementation of a tool that allows interoperation between a concurrent superset of the Prolog programming language and C#. This enables Prolog to be used as a native implementation language for Microsoft's .NET platform. P# compiles a linear logic extension of Prolog to C# source code. We can thus create C# objects from Prolog and use C#'s graphical, networking and other libraries. We add language constructs on the Prolog side that allow concurrent Prolog code to be written. A primitive predicate is provided that evaluates a Prolog structure on a newly forked thread. Communication between threads is based on the unification of variables contained in such a structure. It is also possible for threads to communicate through a globally accessible table. All of the new features are available to the programmer through new built-in Prolog predicates. We discuss two software engineering tools implemented using P#. Copyright © 2004 John Wiley & Sons, Ltd.     

Helper threads via virtual multithreading

Memory latency dominates the performance of many applications on modern processors, despite advances in caches and prefetching techniques. Numerous prefetching techniques, both in hardware and software, try to alleviate the memory bottleneck. One such technique, known as helper threading improves single-thread performance on a simultaneous multithreaded architecture (SMT), which shares processor resources, including caches, among logical threads. It uses otherwise idle hardware thread contexts to execute speculative threads on behalf of the main thread. Helper threading accelerates a program by exploiting a processor's multithreading capability to run assist threads. Based on the helper threading usage model, virtual multithreading (VMT), a form of switch-on-event user-level multithreading, can improve performance for real-world workloads with a wall-clock speedup of 5.0 to 38.5 percent     

基于粒子群算法的多核处理器线程调度研究

为有效解决多核处理器的线程调度问题,提出了一种基于粒子群算法框架上的线程调度算法.该算法依据设计的调度模型,在线程DAG图上通过复制不在同一处理器上且存在相关性的线程,生成相互独立的子DAG图,并采用改进的粒子群优化算法对其进行合理调度,由此提高线程调度效率.仿真实现了该算法,并通过实验数据验证了该算法的优越性.     

A Smooth Concurrency Revolution with Free Objects

In this paper, the author propose viewing a program as a collection of "free" objects, each of which has its own thread of control and executes its operations within atomic transactions. Such objects would communicate by asynchronous message passing with futures - objects that encapsulate the results of server invocations and let clients retrieve them while hiding the actual state of readiness from the client. Except for the unleashing of newly created free objects, there's no need for specific language constructs other than those already available in 00 languages. After all, C++ has been successful in part because it looked like C, Java has been successful in part because it looked like C++, and C# looks like both. With free objects, the program looks exactly like a traditional OO program, with one exception: certain object creations fork new activity threads and must be distinguished as such. This column discusses how to do that.     

Separation of highly viscous fluid threads in branching microchannels

We experimentally study the transport properties of threads made of high-viscosity fluids flowing in a sheath of miscible, low-viscosity fluids in bifurcating microchannels. A viscous filament is generated using a square hydrodynamic focusing section by injecting a ‘thick’ fluid into the central channel and a ‘thin’ fluid from the side channels. This method allows us to produce miscible fluid threads of various sizes and lateral positions in a straight channel and enables the systematic study of the downstream thread’s response to flow partitioning in branching microfluidic networks at low Reynolds numbers. A phase diagram detailing the various flow patterns observed at the first bifurcation, including thread folding, transport, and fouling, is presented along with transition lines. We also examine the role of viscous buckling instabilities on thread behavior and the formation of complex viscous mixtures and stratifications at the small scale. This work shows the possibility to finely control thread trajectory and stability as well as manipulate the structural arrangement of high-viscosity multiphase flows in complex microfluidic systems.