Performance Portability on EARTH: A Case Study across Several Parallel Architectures
With the rapidly increasing diversity of parallel architectures and the increasing time and labor for developing parallel applications, the performance portability of parallel programs is becoming increasingly important and should be considered when designing parallel execution models, APIs, and runtime system software. This paper analyzes both code portability and performance portability of parallel programs based on the EARTH model $an event-driven fine-grain multi-threaded execution and architecture model. We discuss several design considerations of the EARTH system that contribute to the performance portability of parallel applications. Experiments of four representative benchmarks are conducted on several different parallel architectures, including two clusters listed in the 23rd supercomputer TOP500 list. The results demonstrate that EARTH based programs can achieve robust performance portability across the selected hardware platforms without any code modification or tuning.

title: Sequential Consistency Revisit: The Sufficient Condition and Method to Reason the Consistency Model of a Multiprocessor-on-a-Chip Architecture
abstract: In his seminal paper in 1979  on memory consistency, Lamport proposed two requirements for a multiprocessor system to be sequentially consistent. The second condition stated that memory “requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue”. Recently, the authors have the opportunity to revisit Lamport’s conditions in the context of a design study of the IBM Cyclops multiprocessoron-a-chip architecture (known as BG/C) from the system software angle. We find that when a multiprocessor system employs a network to communicate with its shared memory modules – such as in the BG/C architecture we need to carefully elaborate Lamport’s requirements to cover the network. Thus we have refined the Lamport’s second requirement along this line and demonstrated that the revised conditions are sufficient for ensuring the sequentially consistent behaviors for a class of BG/C-like architectures.

title: A cluster-based solution for high performance hmmpfam using EARTH execution model
abstract: Hmmpfam is a widely used computation-intensive bioinformatics software for sequence classification. The contribution of this paper is the first largely scalable and robust cluster-based solution of parallel hmmpfam based on EARTH (Efficient Architecture for Running Threads), which is an event-driven fine-grain multi-threaded programming execution model. Compared with the original PVM implementation, our implementation shows notable improvements on absolute speed-up and better scalability. Experiments on two advanced supercomputing clusters at Argonne National Laboratory (ANL) achieve an absolute speedup of 222.8 on 128 dual-CPU nodes for a representative data set, which means that the total execution time is reduced from 15.9 hours (serial program) to only 4.3 minutes.

title: Implementing parallel hmm-pfam on the EARTH multithreaded architecture
abstract: Hmmpfam is a widely used computation-intensive bioinformatics software for sequence classification. This poster describes a new parallel implementation of hmmpfam on EARTH, which is an event-driven fine-grain multithreaded programming execution model. The comparison results of the original PVM implementation and our implementation shows notable improvements on absolute speedup and scalability. On a cluster of 128 dual-CPU nodes, the execution time of a representative testbench is reduced from 15.9 hours to 4.3 minutes.

title: Hierarchical multithreading: programming model and system software
abstract: This paper addresses the underlying sources of performance degradation (e.g. latency, overhead, and starvation) and the difficulties of programmer productivity (e.g. explicit locality management and scheduling, performance tuning, fragmented memory, and synchronous global barriers) to dramatically enhance the broad effectiveness of parallel processing for high end computing. We are developing a hierarchical threaded virtual machine (HTVM) that defines a dynamic, multithreaded execution model and programming model, providing an architecture abstraction for HEC system software and tools development. We are working on a prototype language, LITL-X (pronounced "little-X") for latency intrinsic-tolerant language, which provides the application programmers with a powerful set of semantic constructs to organize parallel computations in a way that hides/manages latency and limits the effects of overhead. This is quite different from locality management, although the intent of both strategies is to minimize the effect of latency on the efficiency of computation. We work on a dynamic compilation and runtime model to achieve efficient LITL-X program execution. Several adaptive optimizations were studied. A methodology of incorporating domain-specific knowledge in program optimization was studied. Finally, we plan to implement our method in an experimental testbed for a HEC architecture and perform a qualitative and quantitative evaluation on selected applications

title: TiNy threads: a thread virtual machine for the Cyclops64 cellular architecture
abstract: This paper presents the design and implementation of a thread virtual machine, called TNT (or TiNy-Threads) for the IBM Cyclops64 architecture (the latest Cyclops architecture that employs a unique multiprocessor-on-a-chip design with a very large number of hardware thread units and embedded memory) - as the cornerstone of the C64 system software. We highlight how to achieve high efficiency by mapping (and matching) the TNT thread model directly to the Cyclops ISA features assisted by a native TNT thread runtime library. Major results of our experimental study demonstrate good efficiency, scalability and usability of our TNT model/implementation.

title: A Hopfield neural network based task mapping method
abstract: With a prior knowledge of a program, static mapping aims to identify an optimal clustering strategy that can produce the best performance. In this paper we present a static method that uses Hopfield neural network to cluster the tasks of a parallel program for a given system. This method takes into account both load balancing and communication minimization. The method has been tested on a distributed shared memory system against other three clustering methods. Four programs, SOR, N-body, Gaussian Elimination and VQ, are used in the test. The result shows that our method is superior to the other three.

title: Cluster queue structure for shared-memory multiprocessor systems
abstract: Three basic organizations have been proposed to construct the task queues for a shared memory multiprocessor system: centralized, distributed, and hierarchical structures. The centralized structure is not suitable for massively parallel systems since the centralized queue is a bottleneck. The distributed structure, on the other hand, will end up with load imbalancing due to the random execution time of tasks. The hierarchical structure tends to combine the advantages of the previous two structures and reduces the impact of bottleneck and load imbalancing. However, we found out that the load imbalancing still exists in the hierarchical structure. It also affects system performance, in particular, when the workload becomes heavier. We further identified the cause of this problem. We propose the use of a forest structure to provide load balancing and contention minimization.

title: Queue structures for shared-memory multiprocessor systems
abstract: Three basic structures have been proposed to organize the task queues for shared-memory multiprocessor systems: centralized, distributed, and hierarchical structures. The hierarchical structure intends to combine the advantage of the other two structures and eliminate their disadvantages. Unfortunately, we find it still has serious load imbalancing, in particular when the workload is heavy and irregular. We propose the use of a forest structure in place of a hierarchical one. Simulation shows the proposed structure can provide better load balancing and less contention than the hierarchical one.

title: Fast handover in clustered wireless ATM
abstract: ATM networks can be extended to wireless networks by attaching wireless base stations to ATM networks, which allows mobile users to roam with little restriction. Due to the physical limitation, handovers become unavoidable when mobiles move from one area to another. As ATM networks are connection-oriented, connections have to be rerouted if a mobile device is moving out of its current cell. To have seamless communication, the handover process must be performed with small delay, minimal cell loss and no change in cell sequence. The authors propose an architecture to link ATM network to wireless networks. The proposed architecture is built on a hierarchical structure that groups cells into clusters. Different handover protocols are used, depending on whether a handover is in the same cluster or between clusters. In addition, the protocols take appropriate actions based on the type of communication. The performance of this protocol is superior to existing solutions in terms of speed and resource consumption.

title: Bottom Up Algorithm to Identify Link-Level Transition Probability
abstract: Network tomography aims to obtain network characteristics by end-to-end measurements. Most works carried out in the past focused on the methods and methodologies to identify some of the characteristics, such as loss rate, delay distribution, etc. which are typical static statistical variables showing long-term network behaviors. In contrast to the previous works, we in this paper turn our attention to dynamic characteristics, e.g. transition probability of each link, which unveil the temporal correlation of traffic flows. Those dynamic characteristics could be more important than those static ones since the temporal information can be used in prediction. Apart from that, those characteristics are essential to many other issues, including the models used in network tomography. To identify transition probabilities by end-to-end measurements and in a real-time manner is a challenging task although the problem can be formulated by a hidden Markov model (HMM). Instead of using Baum-Welch algorithm to identify the transition probabilities because it needs a long execution time, we propose a new method that consider the correlations observed by receivers to obtain the transition probabilities in a simple and real-time manner. The proposed method is equal to a closed form solution that makes it a candidate for real-time network control.