No abstract available.

Abstract This paper describes the issues involved in sharing data among processes executing co‐operatively in a heterogeneous computing environment. In a heterogeneous environment, the physical representation of a data object may need to be transformed when the object is moved from one type of processor to another. As a part of a larger project to build a heterogeneous distributed shared memory system we developed an automated tool for generating the conversion routines that are used to implement representation conversion for data objects. We developed a novel method for processing source programs that allowed us to extract detailed information about the physical representation of data objects without access to the source code of the compilers that were generating those representations. A performance comparison with the more general XDR heterogeneous data conversion package shows that the customized conversion routines that we generate are 4 to 8 times faster.

The effective management of caches is critical to the performance of applications on shared-memory multiprocessors. In this paper, we discuss a technique for software cache coherence tht is based upon the integration of a program-level abstraction for shared data with software cache management . The program-level abstraction, called Shared Regions, explicitly relates synchronization objects with the data they protect. Cache coherence algorithms are presented which use the information provided by shared region primitives, and ensure that shared regions are always cacheable by the processors accessing them. Measurements and experiments of the Shared Region approach on a shared-memory multiprocessors accessing them. Measurements and experiments of the Shared Region approach on a shared-memory multiprocessor are shown. Comparisons with other software based coherence strategies, including a user-controlled strategy and an operating system-based strategy, show that this approach is able to deliver better performance, with relatively low corresponding overhead and only a small increase in the programming effort. Compared to a compiler-based coherence strategy, the Shared Regions approach still performs better than a compiler that can achieve 90% accuracy in allowing cacheing, as long as the regions are a few hundred bytes or larger, or they are re-used a few times in the cache.

Abstract Load sharing in large, heterogeneous distributed systems allows users to access vast amounts of computing resources scattered around the system and may provide substantial performance improvements to applications. We discuss the design and implementation issues in Utopia, a load sharing facility specifically built for large and heterogeneous systems. The system has no restriction on the types of tasks that can be remotely executed, involves few application changes and no operating system change, supports a high degree of transparency for remote task execution, and incurs low overhead. The algorithms for managing resource load information and task placement take advantage of the clustering nature of large‐scale distributed systems; centralized algorithms are used within host clusters, and directed graph algorithms are used among the clusters to make Utopia scalable to thousands of hosts. Task placements in Utopia exploit the heterogeneous hosts and consider varying resource demands of the tasks. A range of mechanisms for remote execution is available in Utopia that provides varying degrees of transparency and efficiency. A number of applications have been developed for Utopia, ranging from a load sharing command interpreter, to parallel and distributed applications, to a distributed batch facility. For example, an enhanced Unix command interpreter allows arbitrary commands and user jobs to be executed remotely, and a parallel make facility achieves speed‐ups of 15 or more by processing a collection of tasks in parallel on a number of hosts.

The increasing need for data sharing in large-scale distributed systems may place a heavy burden on critical resources such as file servers and networks. Our examination of the workload in one large commercial engineering environment shows that wide-spread sharing of unstable files among tens to hundreds of users is common. Traditional client-based file cacheing techniques are not scalable in such environments.

The design, implementation, and performance of heterogeneous distributed shared memory (HDSM) are studied. A prototype HDSM system that integrates very different types of hosts has been developed, and a number of applications of this system are reported. Experience shows that despite a number of difficulties in data conversion, HDSM is implementable with minimal loss in functional and performance transparency when compared to homogeneous DSM systems.>

Large-scale Non-Uniform Memory Access (NUMA) multiprocessors are gaining increased attention due to their potential for achieving high performance through the replication of relatively simple components. Because of the complexity of such systems, scheduling algorithms for parallel applications are crucial in realizing the performance potential of these systems. In particular, scheduling methods must consider the scale of the system, with the increased likelihood of creating bottlenecks, along with the NUMA characteristics of the system, and the benefits to be gained by placing threads close to their code and data.We propose a class of scheduling algorithms based on processor pools. A processor pool is a software construct for organizing and managing a large number of processors by dividing them into groups called pools. The parallel threads of a job are run in a single processor pool, unless there are performance advantages for a job to span multiple pools. Several jobs may share one pool. Our simulation experiments show that processor pool-based scheduling may effectively reduce the average job response time. The performance improvements attained by using processor pools increase with the average parallelism of the jobs, the load level of the system, the differentials in memory access costs, and the likelihood of having system bottlenecks. As the system size increasesr, while maintaining the workload composition and intensity, we observed that processor pools can be used to provide significant performance improvements. We therefore conclude that processor pool-based scheduling may be an effective and efficient technique for scalable systems.

The problems of building a distributed shared memory system on a network of heterogeneous machines are discussed. An existing algorithm (due to K. Li, 1986) that implements distributed shared memory is extended to a heterogeneous environment. An implementation that runs on Sun and DEC Firefly multiprocessor workstations connected by Ethernet is described. Related implementation and performance issues are discussed. On the basis of measurements of the applications ported to the system, it is concluded that heterogeneous distributed shared memory is not only feasible but can also be compared in performance to its homogeneous counterpart.>

A trace-driven simulation study of dynamic load balancing in homogeneous distributed systems supporting broadcasting is presented. Information about job CPU and input/output (I/O) demands collected from production systems is used as input to a simulation model that includes a representative CPU scheduling policy and considers the message exchange and job transfer cost explicitly. Seven load-balancing algorithms are simulated and their performances compared. Load balancing is capable of significantly reducing the mean and standard deviation of job response times, especially under heavy load, and for jobs with high resource demands. Algorithms based on periodic or nonperiodic load information exchange provide similar performance, and, among the periodic policies, the algorithms that use a distinguished agent to collect and distribute load information cut down the overhead and scale better. With initial job placements only, source initiative algorithms were found to perform better than server initiative algorithms. The performances of all hosts, even those originally with light loads, are generally improved by load balancing.>