Toward a Software Infrastructure for the Cyclops-64 Cellular Architecture
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: 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: 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: Performance Portability on EARTH: A Case Study across Several Parallel Architectures
abstract: 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: 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: Landing openMP on cyclops-64: an efficient mapping of openMP to a many-core system-on-a-chip
abstract: This paper presents our experience mapping OpenMP parallel programming model to the IBM Cyclops-64 (C64) architecture. The C64 employs a many-core-on-a-chip design that integrates processing logic (160 thread units), embedded memory (5MB) and communication hardware on the same die. Such a unique architecture presents new opportunities for optimization. Specifically, we consider the following three areas: (1) a memory aware runtime library that places frequently used data structures in scratchpad memory; (2) a unique spin lock algorithm for shared memory synchronization based on in-memory atomic instructions and native support for thread level execution; (3) a fast barrier that directly uses C64 hardware support for collective synchronization. All three optimizations together, result in an 80% overhead reduction for language constructs in OpenMP. We believe that such a drastic reduction in the cost of managing parallelism makes OpenMP more amenable for writing parallel programs on the C64 platform.

title: A bottom-up inference of loss rate
abstract: Loss tomography, as a key component of network tomography, aims to obtain the loss rate of each link in a network by end-to-end measurements. If knowing the loss model of a link, we, in fact, deal with a parametric estimate problem with incomplete data. Maximum likelihood estimates are often used in this situation to identify the unknown parameters in the loss model. Almost all methods proposed so far rely on the iterative approximation to identify the parameters that requires a long execution time. In addition, the parameters identified by those methods may not be the true values of those parameters since the iterative procedure may trap into a local maximum. In this paper, we propose an estimate that is based on the correlation between a link and its sibling brothers to identify the loss rate of the link. The proposed method, instead of using an iterative approach to approximate the maximum, employs a bottom-up approach to identify the loss rates of the links of a network. Comparing to the previous methods, the proposed method is simple and fast because it is an analytical solution.

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: Implementation of process migration in Amoeba
abstract: The design of a process migration mechanism for the Amoeba distributed operating system is described. The primary motivation for this implementation is to carry out experimental and realistic studies of load balancing algorithms for a distributed operating system. Our aim has been the implementation of a mechanism which is general, efficient and fully transparent and which is reliable in the presence of network and processor failures.<<ETX>>

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.