7778914
Implementation of process migration in Amoeba
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>>
44553256
A Distributed Approach to Estimate Link-Level Loss Rates
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.
2727213
Queue structures for shared-memory multiprocessor systems
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.
25408259
Cluster Queue Structure for Shared-Memory Multiprocessor Systems
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.
11598674
Landing openMP on cyclops-64: an efficient mapping of openMP to a many-core system-on-a-chip
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.
7159642
Hierarchical multithreading: programming model and system software
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
8019938
Optimization of Dense Matrix Multiplication on IBM Cyclops-64: Challenges and Experiences
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.
6376339
Exploring Financial Applications on Many-Core-on-a-Chip Architecture: A First Experiment
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.