A cluster-based solution for high performance hmmpfam using EARTH execution model
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: Exploring Financial Applications on Many-Core-on-a-Chip Architecture: A First Experiment
abstract: Computational requirements for solving models of financial derivatives, for example, the option pricing problems, are huge and demand efficient algorithms and high performance computing capabilities. This demand has been rekindled by the recent developments in the mobile technology making wireless trading a possibility. In this paper, we focus on the development of a Monte-Carlo algorithm on a modern multi-core chip architecture, Cyclops-64 (C64) under development at IBM as the experimental platform for our study in pricing options. The timing results on C64 show that various sets of simulations could be done in a real-time fashion while yielding high performance/price improvement over traditional microprocessors for finance applications.

title: Optimization of Dense Matrix Multiplication on IBM Cyclops-64: Challenges and Experiences
abstract: This paper presents a study of performance optimization of dense matrix multiplication on IBM Cyclops-64(C64) chip architecture. Although much has been published on how to optimize dense matrix applications on shared memory architecture with multi-level caches, little has been reported on the applicability of the existing methods to the new generation of multi-core architectures like C64. For such architectures a more economical use of on-chip storage resources appears to discourage the use of caches, while providing tremendous on-chip memory bandwidth per storage area. 
 
This paper presents an in-depth case study of a collection of well known optimization methods and tries to re-engineer them to address the new challenges and opportunities provided by this emerging class of multi-core chip architectures. Our study demonstrates that efficiently exploiting the memory hierarchy is the key to achieving good performance. The main contributions of this paper include: (a) identifying a set of key optimizations for C64-like architectures, and (b) exploring a practical order of the optimizations, which yields good performance for applications like matrix multiplication.

title: Toward a Software Infrastructure for the Cyclops-64 Cellular Architecture
abstract: This paper presents the initial design of the Cyclops-64 (C64) system software infrastructure and tools under development as a joint effort between IBM T.J. Watson Research Center, ETI Inc. and the University of Delaware. The C64 system is the latest version of the Cyclops cellular architecture that consists of a large number of compute nodes each employs a multiprocessor-on-a-chip architecture with 160 hardware thread units. The first version of the C64 system software has been developed and is now under evaluation. The current version of the C64 software infrastructure includes a C64 toolchain (compiler, linker, functionally accurate simulator, runtime thread library, etc.) and other tools for system control (system initialization, diagnostics and recovery, job scheduler, program launching, etc.) This paper focuses on the following aspects of the C64 system software: (1) the C64 software toolchain; (2) the C64 Thread Virtual Machine (C64 TVM) with emphasis on TiNy ThreadsTM, the implementation of the C64 TVM; (3) the system software for host control. In addition, we illustrate, through two case studies, what an application developer can expect from the C64 architecture as well as some advantages of this architecture, in particular, how it provides a cost-effective solution. A C64 chip’s performance varies across different applications from 5 to 35 times faster than common off-the-self microprocessors.

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: 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 Distributed Approach to Estimate Link-Level Loss Rates
abstract: Network tomography aims to obtain link-level characteristics, such as loss rate and average delay of a link, by end-to-end measurement. A number of methods have been proposed to estimate the loss rate of a link by end-to-end measurement, all of them, in principle, are based on parametric statistics to identify unknown parameters. In addition, they all used the traditional centralized data processing techniques to complete the estimation, which is time-consuming and unscaleable. In this paper, we put forward a distributed method to tackle the scalability problem. The proposed method, instead of estimating link-level characteristics directly, estimate path level characteristics first that can be executed in parallel and can be achieved by a distributed system. The path level characteristics obtained can be used to identify link-level ones later. The proposed method has been proved to be an maximum likelihood estimate.

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.

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 structures have been proposed to organize the task queues for shared-memory multiprocessor systems: centralized, distributed, and hierarchical. Centralized structures are not suitable for massively parallel systems since the shared queue becomes a bottleneck for frequent enqueuing and dequeuing operations. Distributed structures have load imbalancing problem because of no support for workload sharing between queues. Hierarchical structures intend to combine the advantage of the previous two structures and eliminate their disadvantages. Unfortunately, we find load imbalancing still exists in the hierarchical structure, and has significant impact on system performance, particularly when the workload is heavy and irregular. After identifying the cause of this problem, we propose the use of a clustered structure in place of the hierarchical one. Analyzes and simulations show the proposed structure can provide better load balancing and less contention than the hierarchical one.

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.