Knowledge about active radio transmitters is critical for multiple applications: spectrum regulators can use this information to assign spectrum, licensees can identify spectrum usage patterns and provision their future needs, and dynamic spectrum access applications can efficiently pick operating frequency. To achieve these goals, we need a system that continuously senses and characterizes the radio spectrum. Current measurement systems, however, do not scale over time, frequency and space and cannot perform transmitter detection. We address these challenges with theSpectrum Observatory, an end-to-end system for spectrum measurement and characterization. This paper details the design and integration of the Spectrum Observatory, and describes and evaluates the first unsupervised method for detailed characterization of arbitrary transmitters calledTxMiner. We evaluate TxMiner on real-world spectrum measurements collected by the Spectrum Observatory between 30 MHz and 6 GHz and show that it identifies transmitters robustly. Furthermore, we demonstrate the Spectrum Observatory’s capabilities to map the number of active transmitters and their frequency and temporal characteristics, to detect rogue transmitters, and identify opportunities for dynamic spectrum access.

While pen computing has become increasingly more popular, device responsiveness, or latency, still plagues such interaction. Although there have been advances in digitizer technology over the last few years, commercial end-to-end latencies are unfortunately similar to those found with touchscreens, i.e., 65 - 120 milliseconds. We report on a prototype stylus-enabled device, the High Performance Stylus System (HPSS), designed to display latencies as low as one millisecond while users ink or perform dragging tasks.

The user experience on tablets that support both touch and styli is less than ideal, due in large part to the problem of unintended touch or palm rejection . Devices are often unable to distinguish between intended touch (i.e., interaction on the screen intended for action) and unintended touch (i.e., incidental interaction from the palm, forearm, or fingers). This often results in stray ink strokes and accidental navigation, frustrating users. We present a data collection experiment where participants performed inking tasks, and where natural tablet and stylus behaviors were observed and analyzed from both digitizer and behavioral perspectives. An analysis and comparison of novel and existing unintended touch algorithms revealed that the use of stylus information can greatly reduce unintended touch. Our analysis also revealed many natural stylus behaviors that influence unintended touch, underscoring the importance of application and ecosystem demands, and providing many avenues for future research and technological advancement.

Task and reference spaces are important communication channels for remote collaboration. However, all existing systems for sharing these spaces have an inherent weakness: they cannot share arbitrary physical and digital objects on arbitrary surfaces. We present IllumiShare, a new cost-effective, light-weight device that solves this issue. It both shares physical and digital objects on arbitrary surfaces and provides rich referential awareness. To evaluate IllumiShare, we studied pairs of children playing remotely. They used IllumiShare to share the task-reference space and Skype Video to share the person space. The study results show that IllumiShare shared the play space in a natural and seamless way. We also found that children preferred having both spaces compared to having only one. Moreover, we found that removing the task-reference space caused stronger negative disruptions to the play task and engagement level than removing the person space. Similarly, we found that adding the task-reference space resulted in stronger positive disruptions.

Industry trends suggest that the PC and telephone user experiences will converge over the next several years. This convergence raises important questions for the HCI community: how should the PC-phone user experience be designed, and how does PC-phone technology affect work practices? This paper focuses on the first question and provides some initial data on the second question. We describe a PC-phone prototype we built called Enhanced Telephony, and we report data from an eight month field deployment of Enhanced Telephony within our company where over 7,000 people installed the prototype. Results indicate that PC-phone software is a promising technology for the workplace and that the most valuable features may be those that help people manage their incoming calls.

Our goal is to help automate the capture and broadcast of lectures to remote audiences. There are two inter-related components to the design of such systems. The technology component includes the hardware (e.g., video cameras) and associated software (e.g., speaker-tracking). The aesthetic component embodies the rules and idioms that human videographers follow to make a video visually engaging. We present a lecture room automation system and a substantial number of new video-production rules obtained from professional videographers who critiqued it. We also describe rules for a variety of lecture room environments differing in the numbers and types of cameras. We further discuss gaps between what professional videographers do and what is technologically feasible today.

Notification and shared annotations go hand-in-hand. Notification of activity in a shared document system is known to support awareness and improve asynchronous collaboration, but few studies have examined user needs and explored design tradeoffs. We examined large-scale use of notifications in a commercial system and found it lacking. We designed and deployed enhancements to the system, then conducted a field study to gauge their effect. We found that providing more information in notification messages, supporting multiple communication channels through which notifications can be received, and allowing customization of notification messages are particularly important. Overall awareness of annotation activity on software specifications increased with our enhancements

The concept of awareness has received increasing attention over the past several CSCW conferences. Although many awareness interfaces have been designed and studied, most have been limited deployments of research prototypes. In this paper we describe Sideshow, a peripheral awareness interface that was rapidly adopted by thousands of people in our company. Sideshow provides regularly updated peripheral awareness of a broad range of information from virtually any accessible web site or database. We discuss Sideshow's design and the experience of refining and redesigning the interface based on feedback from a rapidly expanding user community.

We conducted two experiments comparing communication behaviors of co-located users in collaborative augmented reality (AR) interfaces. In the first experiment, we compared optical, stereo- and mono-video, and immersive head mounted displays (HMDs) using a target identification task. It was found that differences in the real world visibility severely affect communication behaviors. The optical see-through case produced the best results with the least extra communication needed. Generally, the more difficult it was to use non-verbal communication cues, the more people resorted to speech cues to compensate. In the second experiment, we compared three different combinations of task and communication spaces using a 2D icon design task with optical see-through HMDs. It was found that the spatial relationship between the task and communication spaces also severely affected communication behaviors. Placing the task space between the subjects produced the most active behaviors in terms of initiatory body languages and utterances with least miscommunications.

The common meeting is an integral part of everyday life for most workgroups. However, due to travel, time, or other constraints, people are often not able to attend all the meetings they need to. Teleconferencing and recording of meetings can address this problem. In this paper we describe a system that provides these features, as well as a user study evaluation of the system. The system uses a variety of capture devices (a novel 360° camera, a whiteboard camera, an overview camera, and a microphone array) to provide a rich experience for people who want to participate in a meeting from a distance. The system is also combined with speaker clustering, spatial indexing, and time compression to provide a rich experience for people who miss a meeting and want to watch it afterward.

Increasingly, documents exist primarily in digital form. System designers have recently focused on making it easier to read digital documents, with annotation as an important new feature. But supporting annotation well is difficult because digital documents are frequently modified, making it challenging to correctly reposition annotations in modified versions. Few systems have addressed this issue, and even fewer have approached the problem from the users' point of view. This paper reports the results of two studies examining user expectations for robust annotation positioning in modified documents. We explore how users react to lost annotations, the relationship between types of document modifications and user expectations, and whether users pay attention to text surrounding their annotations. Our results could contribute substantially to effective digital document annotation systems.

Three public spaces frequency used by members of a single organization who are distributed across different floors of two buildings were linked by constantly-running video and audio connections. We discuss the design of the system, including issues in providing low-latency, full-duplex audio-video connectivity, ways to increase possibilities for interaction while addressing privacy concerns, and the introduction of the system to the community. We report on responses to the system and lessions learned, including unexpected issues, such as creative decorations of the spaces and assertions by a vocal minority of employees about the private nature of “public space.”

Given rapid improvements in network infrastructure and streaming-media technologies, a large number of corporations and universities are recording lectures and making them available online for anytime, anywhere access. However, producing high-quality lecture videos is still labor intensive and expensive. Fortunately, recent technology advances are making it feasible to build automated camera management systems to capture lectures. In this paper we report on our design, implementation and study of such a system. Compared to previous work-which has tended to be technology centric-we started with interviews with professional video producers and used their knowledge and expertise to create video production rules. We then targeted technology components that allowed us to implement a substantial portion of these rules, including the design of a virtual video director. The system's performance was compared to that of a human operator via a user study. Results suggest that our system's quality in close to that of a human-controlled system. In fact most remote audience members could not tell if the video was produced by a computer or a person.

One vision of future technology is the ability to easily and inexpensively capture any group meeting that occurs, store it, and make it available for people to view anytime and anywhere on the network. One barrier to achieving this vision has been the design of low-cost camera systems that can capture important aspects of the meeting without needing a human camera operator. A promising solution that has emerged recently is omni-directional cameras that can capture a 360-degree video of the entire meeting.

In comparison to text, audio-video content is much more challenging to browse. Time-compression has been suggested as a key technology that can support browsing-time compression speeds up the playback of audio-video content without causing the pitch to change. Simple forms of time-compression are starting to appear in commercial streaming-media products from Microsoft and Real Networks.In this paper we explore the potential benefits of more recent and advanced types of time compression, called non-linear time compression. The most advanced of these algorithms exploit fine-grain structure of human speech (e.g., phonemes) to differentially speedup segments of speech, so that the overall speedup can be higher. In this paper we explore what are the actual gains achieved by end-users from these advanced algorithms. Our results indicate that the gains are actually quite small in common cases and come with significant system complexity and some audio/video synchronization issues.

Given rapid improvements in storage devices, network infrastructure and streaming-media technologies, a large number of corporations and universities are recording lectures and making them available online for anytime, anywhere access. However, producing high-quality lecture videos is still labor intensive and expensive. Fortunately, recent technology advances are making it feasible to build automated camera management systems to capture lectures. In this paper we report our design of such a system, including system configuration, audio-visual tracking techniques, software architecture, and user study. Motivated by different roles in a professional video production team, we have developed a multi-cinematographer single-director camera management system. The system performs lecturer tracking, audience tracking, and video editing all fully automatically, and offers quality close to that of human-operated systems.

As more audio and video technical presentations go online, it becomes imperative to give users effective summarization and skimming tools so that they can find the presentation they want and browse through it quickly. In a previous study, we reported three automated methods for generating audio-video summaries and a user evaluation of those methods. An open question remained about how well various text/image only techniques will compare to the audio-video summarizations. This study attempts to fill that gap.

The current generation of desktop computers and networks are bringing streaming audio and video into widespread use. A small investment allows presentations or lectures to be multicast, enabling passive viewing from offices or rooms. We surveyed experienced viewers of multicast presentations and designed a lightweight system that creates greater awareness in the presentation room of remote viewers and allows remote viewers to interact with each other and the speaker. We report on the design, use, and modification of the system, and discuss design tradeoffs.

Video in digital format played on programmable devices presents opportunities for significantly enhancing the user's viewing experience. For example, time compression and pause removal can shorten the viewing time for a video, textual and visual indices can allow personalized navigation through the content, and random-access digital storage allows instantaneous seeks into the content. To understand user behavior when such capabilities are available, we built a software video browsing application that combines many such features. We present results from a user study where users browsed video in six different categories: classroom lectures, conference presentations, entertainment shows, news, sports, and travel. Our results show that the most frequently used features were time compression, pause removal, and navigation using shot boundaries. Also, the behavior was different depending on the content type, and we present a classification. Finally, the users found the browser to be very useful. Two main reasons were: i) the ability to save time and ii) the feeling of control over what content they watched.

Previous research on Tutored Video Instruction (TVI) shows that learning is enhanced when small groups of students watch and discuss lecture videos together. Using specialized, high-end videoconferencing systems, these improved results have been shown to apply even when the students are in different locations (Distributed TVI, or DTVI). In this paper, we explore two issues in making DTVI-like scenarios widely supported at low cost. First, we explore design of a system that allows distributed individuals to collectively watch video using shared VCR controls such as play, pause, seek, stop. We show how such a system can be built on top of existing commercial technologies. Second, we explore the impact of four alternative discussion channels on student learning and interaction behavior. The four channels-text chat, audioconferencing, videoconferencing, and face-to-face-have differing infrastructure requirements and costs. Our lab studies show that while text chat does not work, there is no significant difference in discussion behavior and learning between audioconferencing and videoconferencing. While lab studies have their limitations and long-term field studies need to be done, the preliminary results point to a low-cost way for a DTVI-like model to be deployed widely in the very near future.

Digital web-accessible annotations are a compelling medium for personal comments and shared discussions around documents. Only recently supported by widely used products, "in-context" digital annotation is a relatively unexamined phenomenon. This paper presents a case study of annotations created by members of a large development team using Microsoft Office 2000-approximately 450 people created 9,000 shared annotations on about 1,250 documents over 10 months. We present quantitative data on use, supported by interviews with users, identifying strengths and weaknesses of the existing capabilities and possibilities for improvement.

Increasingly often, presentations are given before a live audience, while simultaneously being viewed remotely and recorded for subsequent viewing on-demand over the Web. How should video presentations be designed for web access? How is video accessed and used online? Does optimal design for live and on-demand audiences conflict? We examined detailed behavior patterns of more than 9000 on-demand users of a large corpus of professionally prepared presentations. We find that as many people access these talks on-demand as attend live. Online access patterns differ markedly from live attendance. People watch less overall and skip to different parts of a talk. Speakers designing presentations for viewing on-demand should emphasize key points early in the talk and early within each slide, use slide titles that reveal the talk structure and are meaningful outside the flow of the talk. In some cases the recommendations conflict with optimal design for live audiences. The results also provide guidance in developing tools for on-demand multimedia authoring and use.

In today's fast-paced world, while the number of channels of television programming available is increasing rapidly, the time available to watch them remains the same or is decreasing. Users desire the capability to watch the programs time-shifted (on-demand) and/or to watch just the highlights to save time. In this paper we explore how to provide for the latter capability, that is the ability to extract highlights automatically, so that viewing time can be reduced.

With the proliferation of online multimedia content and the popularity of multimedia streaming systems, it is increasingly useful to be able to skim and browse multimedia quickly. A key technique that enables quick browsing of multimedia is time-compression. Prior research has described how speech can be time-compressed (shortened in duration) while preserving the pitch of the audio. However, client-server systems providing this functionality have not been available.

As streaming audio-video technology becomes widespread, there is a dramatic increase in the amount of multimedia content available on the net. Users face a new challenge: How to examine large amounts of multimedia content quickly. One technique that can enable quick overview of multimedia is video summaries; that is, a shorter version assembled by picking important segments from the original.

Distributed shared memory is an architectural approach that allows multiprocessors to support a single shared address space that is implemented with physically distributed memories. Hardware-supported distributed shared memory is becoming the dominant approach for building multiprocessors with moderate to large numbers of processors. Cache coherence allows such architectures to use caching to take advantage of locality in applications without changing the programmer's model of memory. We review the key developments that led to the creation of cache-coherent distributed shared memory and describe the Stanford DASH multiprocessor, the first working implementation of hardware-supported scalable cache coherence. We then provide a perspective on such architectures and discuss important remaining technical challenges.

Scalable cache coherence protocols have become the key technology for creating moderate to large-scale shared-memory multiprocessors. Although the performance of such multiprocessors depends critically on the performance of the cache coherence protocol, little comparative performance data is available. Existing commercial implementations use a variety of different protocols, including bit-vector/coarse-vector protocols, SCI-based protocols, and COMA protocols. Using the programmable protocol processor of the Stanford FLASH multiprocessor, we provide a detailed, implementation-oriented evaluation of four popular cache coherence protocols. In addition to measurements of the characteristics of protocol execution (e.g., memory overhead, protocol execution time, and message count) and of overall performance, we examine the effects of scaling the processor count from 1 to 128 processors. Surprisingly, the optimal protocol changes for different applications and can change with processor count even within the same application. These results help identify the strengths of specific protocols and illustrate the benefits of providing flexibility in the choice of cache coherence protocol.

Shared-memory multiprocessors (SMPs) are being extensively used as general-purpose servers. The tight coupling of multiple processors, memory, and I/O provides enormous computing power in a single system, and enables the efficient sharing of these resources.The operating systems for these machines (UNIX or Windows NT) provide very few controls for sharing the resources of the system among the active tasks or users. This unconstrained sharing model is a serious limitation for a server because the load placed by one user can adversely affect other users' performance in an unpredictable manner. We show that this lack of isolation is caused by the resource allocation scheme (or lack thereof) carried over from singleuser workstations. Multi-user multiprocessor systems require more sophisticated resource management, and we show how the proposed "performance isolation" scheme can address the current weaknesses of these systems. We have implemented performance isolation in the Silicon Graphics IRIX operating system for three important system resources: CPU time, memory, and disk bandwidth. Running a number of workloads we show that our proposed scheme is successful at providing workstation-like isolation under heavy load, SMP-like latency under light load, and SMP-like throughput in all cases.

Given the limitations of bus-based multiprocessors, CC-NUMA is the scalable architecture of choice for shared-memory machines. The most important characteristic of the CC-NUMA architecture is that the latency to access data on a remote node is considerably larger than the latency to access local memory. On such machines, good data locality can reduce memory stall time and is therefore a critical factor in application performance. In this paper we study the various options available to system designers to transparently decrease the fraction of data misses serviced remotely. This work is done in the context of the Stanford FLASH multiprocessor. FLASH is unique in that each node has a single pool of DRAM that can be used in a variety of ways by the programmable memory controller. We use the programmability of FLASH to explore different options for cache-coherence and data-locality in compute-server workloads. First, we consider two protocols for providing base cache-coherence, one with centralized directory information (dynamic pointer allocation) and another with distributed directory information (SCI). While several commercial systems are based on SCI, we find that a centralized scheme has superior performance. Next, we consider different hardware and software techniques that use some or all of the local memory in a node to improve data locality. Finally, we propose a hybrid scheme that combines hardware and software techniques. These schemes work on the same base platform with both user and kernel references from the workloads. The paper thus offers a realistic and fair comparison of replication/migration techniques that has not previously been feasible.

The effectiveness of texture mapping in enhancing the realism of computer generated imagery has made support for real-time texture mapping a critical part of graphics pipelines. Despite a recent surge in interest in three-dimensional graphics from computer architects, high-quality high-speed texture mapping has so far been confined to costly hardware systems that use brute-force techniques to achieve high performance. One obstacle faced by designers of texture mapping systems is the requirement of extremely high bandwidth to texture memory. High bandwidth is necessary since there are typically tens to hundreds of millions of accesses to texture memory per second. In addition, to achieve the high clock rates required in graphics pipelines, low-latency access to texture memory is needed. In this paper, we propose the use of texture image caches to alleviate the above bottlenecks, and evaluate various tradeoffs that arise in such designs.We find that the factors important to cache behavior are (i) the representation of texture images in memory, (ii) the rasterization order on screen and (iii) the cache organization. Through a detailed investigation of these issues, we explore the best way to exploit locality of reference and determine whether this technique is robust with respect to different scenes and different amounts of texture. Overall, we observe that there is a significant amount of temporal and spatial locality and that the working set sizes are relatively small (at most 16KB) across all cases that we studied. Consequently, the memory bandwidth requirements of a texture cache system are substantially lower (at least three times and as much as fifteen times) than the memory bandwidth requirements of a system which achieves equivalent performance but does not utilize a cache. These results are very encouraging and indicate that caching is a promising approach to designing memory systems for texture mapping.

The dominant architecture for the next generation of shared-memory multiprocessors is CC-NUMA (cache-coherent non-uniform memory architecture). These machines are attractive as compute servers because they provide transparent access to local and remote memory. However, the access latency to remote memory is 3 to 5 times the latency to local memory. CC-NOW machines provide the benefits of cache coherence to networks of workstations, at the cost of even higher remote access latency. Given the large remote access latencies of these architectures, data locality is potentially the most important performance issue. Using realistic workloads, we study the performance improvements provided by OS supported dynamic page migration and replication. Analyzing our kernel-based implementation, we provide a detailed breakdown of the costs. We show that sampling of cache misses can be used to reduce cost without compromising performance, and that TLB misses may not be a consistent approximation for cache misses. Finally, our experiments show that dynamic page migration and replication can substantially increase application performance, as much as 30%, and reduce contention for resources in the NUMA memory system.

This paper presents a frame-work for live multicast of video streams over the Internet. The overall system combines a scalable video compression algorithm, a cheap software only real-time video encoder and decoder, and a network unit. The scalable compression algorithm produces an embedded bit-stream to support decoders with various spatial and temporal resolutions. Bandwidth scalability with a dynamic range from a few Kbps to several Mbps is provided. The subjective quality of compressed frames improves significantly by the use of perceptual distortion measures. For cheap software only encoding and decoding we use hierarchical table-lookup vector quantization. Multiple multicast groups are used for the delivery of the scalable streams over the Internet.

Many well-known video coding schemes use block-matching based motion estimation with a fixed block size, and motion vectors are coded using lossless entropy coding. The disadvantages of this method are that: 1) the predetermined block size is independent of the scene and may not be optimal; 2) the rate for encoding the motion vectors is fixed but may not be the optimal rate allocation between motion vectors and motion compensated prediction error. We propose a scene adaptive motion estimation and coding scheme based on the quadtree structure with entropy-constrained vector quantization (ECVQ). For each block size, an entropy-constrained vector quantizer is built to provide good motion vectors over many rates. A quadtree structure is then constructed that finds the best block size to perform adaptive motion estimation for each area of the frame, and thus optimally allocates rates among the quantizers. Our simulation results have shown that this coding algorithm has superior rate-distortion performance over the fixed-block-size ECVQ method and the traditional full-search method with lossless coding.

The SPLASH-2 suite of parallel applications has recently been released to facilitate the study of centralized and distributed shared-address-space multiprocessors. In this context, this paper has two goals. One is to quantitatively characterize the SPLASH-2 programs in terms of fundamental properties and architectural interactions that are important to understand them well. The properties we study include the computational load balance, communication to computation ratio and traffic needs, important working set sizes, and issues related to spatial locality, as well as how these properties scale with problem size and the number of processors. The other, related goal is methodological: to assist people who will use the programs in architectural evaluations to prune the space of application and machine parameters in an informed and meaningful way. For example, by characterizing the working sets of the applications, we describe which operating points in terms of cache size and problem size are representative of realistic situations, which are not, and which re redundant. Using SPLASH-2 as an example, we hope to convey the importance of understanding the interplay of problem size, number of processors, and working sets in designing experiments and interpreting their results.

Reliabilityand scalability are major concerns when designing operating systems for large-scale shared-memory multiprocessors.In this paper we describe Hive, an operating system with a novel kernel architecture that addresses these issues Hive is structured as an internal distributed system of independent kernels called cells.This improves reliabihty because a hardwme or software fault damages only one cell rather than the whole system, and improves scalability because few kernel resources are shared by processes running on different cells.The Hive prototype is a complete implementation of UNIX SVR4 and is targeted to run on the Stanford FLASH multiprocessor.This paper focuses on Hive's solutlon to the following key challenges: ( 1) fault containment, i.e. confining the effects of hardware or software faults to the cell where they occur, and (2) memory sharing among cells, which is requmed to achieve

Computer systems are rapidly changing.Over the next few years, we will see wide-scale deployment of dynamically-scheduled processors that can issue multiple instructions every clock cycle, execute instructions out of order, and overlap computation and cache misses.We also expect clock-rates to increase, caches to grow, and multiprocessors to replace uniprocessors.Using SimOS, a complete machine simulation environment, this paper explores the impact of the above architectural trends on operating system performance.We present results based on the execution of large and realistic workloads (program development, transaction processing, and engineering compute-server) running on the IRIX 5.3 operating system from Silicon Graphics Inc.Looking at uniprocessor trends, we find that disk 1/0 is the first-order bottleneck for workloads such as program development and transaction processing.Its importance continues to grow over time.Ignoring 1/0, we find that the memory system is the key bottleneck, stalling the CPU for over 50% of the execution time.Surprisingly, however, our results show that this stall fraction is unlikely to increase on future machines due to increased cache sizes and new latency hiding techniques in processors.We also find that the benefits of these architectural trends spread broadly across a majority of the important services provided by the operating system.We find the situation to be much worse for multiprocessors.Most operating systems services consume 3f)-i'0~0 more time than their uniprocessor counterparts.A large fraction of the stalls are due to coherence misses caused by communication between processors.Because larger caches do not reduce coherence misses, the performance gap between uniprocessor and multiprocessor performance will increase unless operating system developers focus on kernel restructuring to reduce unnecessary communication.The paper presents a detailed decomposition of execution time (e.g., instruction execution time, memory stall time separately for instructions and data, synchronization time) for important kernel services in the three workloads.

To design effective large-scale multiprocessors, designers need to understand the characteristics of the applications that will use the machines. Application characteristics of particular interest include the amount of communication relative to computation, the structure of the communication, and the local cache and memory requirements, as well as how these characteristics scale with larger problems and machines. One important class of applications is based on hierarchical N-body methods, which are used to solve a wide range of scientific and engineering problems efficiently. Important characteristics of these methods include the nonuniform and dynamically changing nature of the domains to which they are applied, and their use of long-range, irregular communication. This article examines the key architectural implications of representative applications that use the two dominant hierarchical N-body methods: the Barnes-Hut Method and the Fast Multipole Method. We first show that exploiting temporal locality on accesses to communicated data is critical to obtaining good performance on these applications and then argue that coherent caches on shared-address-space machines exploit this locality both automatically and very effectively. Next, we examine the implications of scaling the applications to run on larger machines. We use scaling methods that reflect the concerns of the application scientist and find that this leads to different conclusions about how communication traffic and local cache and memory usage scale than scaling based only on data set size. In particular, we show that under the most realistic form of scaling, both the communication-to-computation ratio as well as the working-set size (and hence the ideal cache size per processor) grow slowly as larger problems are run on larger machines. Finally, we examine the effects of using the two dominant abstractions for interprocessor communication: a shared address space and explicit message passing between private address spaces. We show that the lack of an efficiently supported shared address space will substantially increase the programming complexity and performance overheads for these applications.

Several cache-coherent shared-memory multiprocessors have been developed that are scalable and offer a very tight coupling between the processing resources. They are therefore quite attractive for use as compute servers for multiprogramming and parallel application workloads. Process scheduling and memory management, however, remain challenging due to the distributed main memory found on such machines. This paper examines the effects of OS scheduling and page migration policies on the performance of such compute servers. Our experiments are done on the Stanford DASH, a distributed-memory cache-coherent multiprocessor. We show that for our multiprogramming workloads consisting of sequential jobs, the traditional Unix scheduling policy does very poorly. In contrast, a policy incorporating cluster and cache affinity along with a simple page-migration algorithm offers up to two-fold performance improvement. For our workloads consisting of multiple parallel applications, we compare space-sharing policies that divide the processors among the applications to time-slicing policies such as standard Unix or gang scheduling. We show that space-sharing policies can achieve better processor utilization due to the operating point effect, but time-slicing policies benefit strongly from user-level data distribution. Our initial experience with automatic page migration suggests that policies based only on TLB miss information can be quite effective, and useful for addressing the data distribution problems of space-sharing schedulers.

The advantages of using message passing over shared memory for certain types of communication and synchronization have provided an incentive to integrate both models within a single architecture. A key goal of the FLASH (FLexible Architecture for SHared memory) project at Stanford is to achieve this integration while maintaining a simple and efficient design. This paper presents the hardware and software mechanisms in FLASH to support various message passing protocols. We achieve low overhead message passing by delegating protocol functionality to the programmable node controllers in FLASH and by providing direct user-level access to this messaging subsystem. In contrast to most earlier work, we provide an integrated solution that handles the interaction of the messaging protocols with virtual memory, protected multiprogramming, and cache coherence. Detailed simulation studies indicate that this system can sustain message-transfers rates of several hundred megabytes per second, effectively utilizing projected network bandwidths for next generation multiprocessors.

A flexible communication mechanism is a desirable feature in multiprocessors because it allows support for multiple communication protocols, expands performance monitoring capabilities, and leads to a simpler design and debug process. In the Stanford FLASH multiprocessor, flexibility is obtained by requiring all transactions in a node to pass through a programmable node controller, called MAGIC. In this paper, we evaluate the performance costs of flexibility by comparing the performance of FLASH to that of an idealized hardwired machine on representative parallel applications and a multiprogramming workload. To measure the performance of FLASH, we use a detailed simulator of the FLASH and MAGIC designs, together with the code sequences that implement the cache-coherence protocol. We find that for a range of optimized parallel applications the performance differences between the idealized machine and FLASH are small. For these programs, either the miss rates are small or the latency of the programmable protocol can be hidden behind the memory access time. For applications that incur a large number of remote misses or exhibit substantial hot-spotting, performance is poor for both machines, though the increased remote access latencies or the occupancy of MAGIC lead to lower performance for the flexible design. In most cases, however, FLASH is only 2%–12% slower than the idealized machine.

There is an increasing trend to use commodity microprocessors as the compute engines in large-scale multiprocessors. However, given that the majority of the microprocessors are sold in the workstation market, not in the multiprocessor market, it is only natural that architectural features that benefit only multiprocessors are less likely to be adopted in commodity microprocessors. In this paper, we explore multiple-context processors, an architectural technique proposed to hide the large memory latency in multiprocessors. We show that while current multiple-context designs work reasonably well for multiprocessors, they are ineffective in hiding the much shorter uniprocessor latencies using the limited parallelism found in workstation environments. We propose an alternative design that combines the best features of two existing approaches, and present simulation results that show it yields better performance for both multiprogrammed workloads on a workstation and parallel applications on a multiprocessor. By addressing the needs of the workstation environment, our proposal makes multiple contexts more attractive for commodity microprocessors.

Hardware distributed shared memory (DSM) systems efficiently support fine grain sharing of data by maintaining coherence at the level of individual cache lines and providing automatic replication in processor caches. Software DSM systems, on the other hand, amortize high communication costs by maintaining coherence at coarser granularities and replicating data at the level of local main memories. Even though software DSM systems have traditionally been targeted towards loosely coupled environments, some of the techniques are potentially useful in the context of tightly coupled multiprocessors. In particular, communicating data at a coarse grain can sometimes be more efficient than transferring the data as individual cache lines. Furthermore, replication in local memories can accommodate applications with larger working sets as compared to replication in processor caches only. Therefore, combining the two techniques in a hybrid protocol can potentially exploit the benefits of each approach.

The FLASH multiprocessor efficiently integrates support for cache-coherent shared memory and high-performance message passing, while minimizing both hardware and software overhead. Each node in FLASH contains a microprocessor, a portion of the machine's global memory, a port to the interconnection network, The MAGIC chip handles all communication both within the node and among nodes, using hardwired data paths for efficient data movement and a programmable processor optimized for executing protocol operations. The use of the protocol processor makes FLASH very flexible/spl minus/it can support a variety of different communication mechanisms/spl minus/and simplifies the design and implementation. This paper presents the architecture of FLASH and MAGIC, and discusses the base cache-coherence and message-passing protocols. Latency and occupancy numbers, which are derived from our system-level simulator and our Verilog code, are given for several common protocol operations. The paper also describes our software strategy and FLASH's current status.>

Recently, several theoretical models of parallel architectures have been proposed to replace the PRAM as the model that is presented to an algorithm designer. A primary focus of the new models is to include the cost of interprocessor communication, which is increasingly important in modern parallel architectures. We argue that modeling the communication costs in the architecture or system is only one part of the problem. The other, and usually much more difficult, part is modeling the communication properties of the algorithm itself, which provides necessary inputs into the architectural model to determine overall complexity. In this context, we make three main points in this paper: (i) It is incomplete to describe communication without regard to its relationship with replication. We propose a description of the communication-replication relationship in terms of the working set hierarchy of an algorithm. (ii) Both inherent communication and the communication-replication relationship can be very difficult to model in irregular, dynamic computations that are crucial in many real-world applications. We present some examples that demonstrate this difficulty. (iii) We believe that substantial leverage can be obtained in this effort from the computer systems community, which can provide a hierarchy of simulation and profiling tools—from abstract to detailed—tailored to the needs of the algorithm designers. We propose an initial set of simulation tools, and we discuss possible future refinements to this set.

The distribution of resources among processors, memory and caches is a crucial question faced by designers of large-scale parallel machines. If a machine is to solve problems with a certain data set size, should it be built with a large number of processors each with a small amount of memory, or a smaller number of processors each with a large amount of memory? How much cache memory should be provided per processor for cost-effectiveness? And how do these decisions change as larger problems are run on larger machines?

Large-scale shared memory multiprocessors typically support a multilevel memory hierarchy consisting of per-processor caches, a local portion of shared memory, and remote shared memory. On such machines, the performance of parallel programs is often limited by the high latency of remote memory references. In this paper we explore how knowledge of the underlying memory hierarchy can be used to schedule computation and distribute data structures, and thereby improve data locality. Our study is done in the context of COOL, a concurrent object-oriented language developed at Stanford. We develop abstractions for the programmer to supply optional information about the data reference patterns of the program. This information is used by the runtime system to distribute tasks and objects so that the tasks execute close (in the memory hierarchy) to the objects they reference.

No abstract available.

We present parallel versions of a representative N-body application that uses Greengard and Rokhlin's adaptive Fast Multipole Method (FMMJ While parallel implementations of the umform FMM are straightforward and have been developed on alfferent architectures, the aalzptive version complicates the task of obtaining eflective parallel peflormance owing to the nonunz~onn and dynamically changing nature of the problem &mains to which it is applied.We propose and evaluate two techniques for providing load balancing and data locality, both of which take advantageof key insights into the method and its typical applications.Using the better of these techm"ques, we demonstrate 45-fold speedups on galactic sinudations on a 48-processor Stanford DASH machine, a state-of-the-art shared address space multiprocessor even for relatively small problems.We also show good speedups on a 2-ring Kendall Square Research KSR-I.Finally we summarize some key architectural implications of this important computational method.Permission to copy without fee aft or pan of Ibis material is Sranted, provided that the copies am not made or distrit!uted for direct ccmtmerciaf advantage, the ACM copyright ndice and the tiUe of the ~bficstion and 54 its date appear, and notice is given that copyins is by permis$icm of the Association for Com@ing Machinery.To copy dheww, m to repubfish, requires 8 fee andh specific pxmission.

Two interesting variants of large-scale shared-addressspace parallel architectures are cache-coherent non-uru~ormmemory-access machines (CC-NUMA) and cache-only memory architectures (COMA).Both have distributed main memory and use directory-based cache coherence.While both architectures m-grate and replicate data at the cache level automatically under hardware control, COIUA machines do this at the main memory level as well.Previous work had discussed the general advantages and disadvantages of the two opes of architectures, and presented results comparing the performance of small problems on simulated architectures of the two types.In this piper, we compare the parallel performance of a recent realizatwn of each type of architecturuhe Stanford DASH multiprocessor (CC-NUMA) and the Kendall Square Research KSR-1 (COMA).Using a suite of important computatwrtai kernels and complete scientific applicatwns, we examt"ne performance dl~erences resulting both from the CC-NUMAICOMA nature of the machines as well as from spectfii dt~erences in system implementation.

Recently there has been a surge of interest in developing performance debugging tools to help programmers tune their applications for better memory performance [2, 4, 10]. These tools vary both in the detail of feedback provided to the user, and in the run-time overbead of using them. MemSpy [10] is a simulation-based tool which gives programmers detailed statistics on the memory system behavior of applications. It provides information on the frequency and causes of cache misses, and presents it in terms of source-level data and code objects with which the programmer is familiar. However, using MemSpy increases a program's execution time by roughly 10 to 40 fold. This overhead is generally acceptable for applications with execution times of several minutes or less, but it can be inconvenient when tuning applications with very long execution times.This paper examines the use of trace sampling techniques to reduce the execution time overhead of tools like MemSpy. When simulating one tenth of the references, we find that MemSpy's execution time overhead is improved by a factor of 4 to 6. That is, the execution time when using MemSpy is generally within a factor of 3 to 8 times the normal exwution time. With this improved performance, we observe only small errors in the performance statistics reported by MemSpy. On moderate sized caches of 16KB to 128KB, simulating as few as one tenth of the references (in samples of 0.5M references each) allows us to estimate the program's actual cache miss rate with an absolute error no greater than 0.3% on our five benchmarks. These errors are quite tolerable within the context of performance bugging. With larger caches we can also obtain good accuracy by using longer sample lengths. We conclude that, used with care, trace sampling is a powerful technique that makes possible performance debugging tools which provide both detailed memory statistics and low execution time overheads.

An interesting and common class of workloads for shared-memory multiprocessors is multiprogrammed workloads. Because these workloads generally contain more processes than there are processors in the machine, there are two factors that increase the number of cache misses. First, several processes are forced to time-share the same cache, resulting in one process displacing the cache state previously built up by a second one. Consequently, when the second process runs again, it generates a stream of misses as it rebuilds ita cache state. Second since an idle processor simply selects the highest priority runnable process, a given process often moves from one CPU to another. This frequent migration results in the process having to continuously reload its state into new caches, producing streams of cache misses. To reduce the number of misses in these workloads, processes should reuse their cached state more. One way to encourage this is to schedule each process based on its affinity to individual caches, that is, based on the amount of state that the process has accumulated in an individual cache. This technique is called cache affinity scheduling.

The fundamental premise behind the DASH project is that it is feasible to build large-scale shared-memory multiprocessors with hardware cache coherence. The hardware overhead of directory-based cache coherence in a 48-processor is examined. The data show that the overhead is only about 10-15%, which appears to be a small cost for the ease of programming offered by coherent caches and the potential for higher performance. The performance of the system is discussed, and the speedups obtained by a variety of parallel applications running on the prototype are shown. Using a sophisticated hardware performance monitor, the effectiveness of coherent caches and the relationship between an application's reference behavior and its speedup are characterized. The optimizations incorporated in the DASH protocol are evaluated in terms of their effectiveness on parallel applications and on atomic tests that stress the memory system.>

Software-controlled data prefetching is a promising technique for improving the performance of the memory subsystem to match today's high-performance processors.While prefctching is useful in hiding the latency, issuing prefetches incurs an instruction overhead and can increase the load on the memory subsystem.As a resu 1~ care must be taken to ensure that such overheads do not exceed the benefits.This paper proposes a compiler algorithm to insert prefetch instructions into code that operates on dense matrices.Our algorithm identiEes those references that are likely to be cache misses, and issues prefetches only for them.We have implemented our algorithm in the SUfF (Stanford University Intermediate Form) optimizing compiler.By generating fully functional code, we have been able to measure not only the improvements in cache miss rates, but also the oversdl performance of a simulated system.We show that our algorithm significantly improves the execution speed of our benchmark programs-some of the programs improve by as much as a factor of two.When compared to an algorithm that indiscriminately prefetches alf array accesses, our algorithm can eliminate many of the unnecessary prefetches without any significant decrease in the coverage of the cache misses.

Good cache memory performance is essential to achieving high CPU utilization in shared-memory multiprocessors.While the performance of caches is determined by both application end operating system (OS ) references, most research has focused on the cache performance of applications afone.This is partiafly due to the difficulty of measuring OS activity and as a resrtl~the cache performance of the OS is largely unknown.In this paper, we characterize the cache performance of a commercial System V UNIX rtrttrtittg on a four-CPU multiprocessor.The related issue of the performance impact of the OS synchronization activity is tdso stttdicd.For our study, we use a hardware monitor that records the cache misses in the machine without perturbing it.We study three multiprocessor workloads: a parallel Compilq a multiprogrsmmed load and a commercial database.Our results show that OS misses occur frequently enough to stall CPUS for 17-21 'Yoof their non-idle time.Further, if we include application misses induced by OS interference in the cache, then the SQU time reaches 25%.A detailed analysis reveals three major sources of OS misses: instruction fetehea, process migratiom and data accesses in block operations.As for synchronization behavior, we find that OS syncfrrordzation has low overhead if supported correctly end that OS locks show good locality and low contention.

The large latency of memory accesses is a major impediment to achieving high performance in large scale shared-memory multi-processsors. Relaxing the memory consistency model is an attractive technique for hiding this latency by allowing the overlap of memory accesses with other computation and memory accesses. Previous studies on relaxed models have shown that the latency of write accesses can be hidden by buffering writes and allowing reads to bypass pending writes. Hiding the latency of reads by exploiting the overlap allowed by relaxed models is inherently more difficult, however, simply because the processor depends on the return value for its future computation.

We examine two multiple-context schemes in the context of scalable shared-memory multiprocessors. The blocked scheme switches between contexts at cache misses. The proposed interleaved scheme switches between available contexts on a cycle-by-cycle basis, while providing full pipeline interlocks for good single-context performance. We show the interleaved scheme to have a performance advantage over the blocked scheme due to its ability to hide pipeline dependencies and reduce the context switch cost. We also show that, while the implementation of the interleaved scheme is more complex, this complexity is not overwhelming.

The fundamental premise behind the DASH project is that it is feasible to build large-scale shared-memory multiprocessors with hardware cache coherence. While paper studies and software simulators are useful for understanding many high-level design trade-offs, prototypes are essential to ensure that no critical details are overlooked. A prototype provides convincing evidence of the feasibility of the design allows one to accurately estimate both the hardware and the complexity cost of various features, and provides a platform for studying real workloads. A 16-processor prototype of the DASH multiprocessor has been operational for the last six months. In this paper, the hardware overhead of directory-based cache coherence in the prototype is examined. We also discuss the performance of the system, and the speedups obtained by parallel applications running on the prototype. Using a sophisticated hardware performance monitor, we characterize the effectiveness of coherent caches and the relationship between an application's reference behavior and its speedup.

Two interesting variations of large-scale shared-memory machines that have recently emerged are cache-coherent non-uniform-memory-access machines (CC-NUMA) and cache-only memory architectures (COMA). They both have distributed main memory and use directory-based cache coherence. Unlike CC-NUMA, however, COMA machines automatically migrate and replicate data at the main-memory level in cache-line sized chunks. This paper compares the performance of these two classes of machines. We first present a qualitative model that shows that the relative performance is primarily determined by two factors: the relative magnitude of capacity misses versus coherence misses, and the granularity of data partitions in the application. We then present quantitative results using simulation studies for eight parallel applications (including all six applications from the SPLASH benchmark suite). We show that COMA's potential for performance improvement is limited to applications where data accesses by different processors are finely interleaved in memory space and, in addition, where capacity misses dominate over coherence misses. In other situations, for example where coherence misses dominate, COMA can actually perform worse than CC-NUMA due to increased miss latencies caused by its hierarchical directories. Finally, we propose a new architectural alternative, called COMA-F, that combines the advantages of both CC-NUMA and COMA.

To cope with the increasing difference between processor and main memory speeds, modern computer systems use deep memory hierarchies. In the presence of such hierarchies, the performance attained by an application is largely determined by its memory reference behavior—if most references hit in the cache, the performance is significantly higher than if most references have to go to main memory. Frequently, it is possible for the programmer to restructure the data or code to achieve better memory reference behavior. Unfortunately, most existing performance debugging tools do not assist the programmer in this component of the overall performance tuning task.

The memory consistency model, or memory model, supported by a shared-memory multiprocessor directly affects its performance. The most commonly assumed memory model is sequential consistency (SC). While SC provides a simple model for the programmer, it imposes rigid constraints on the ordering of memory accesses and restricts the use of common hardware and compiler optimizations. To remedy the shortcomings of SC, several relaxed memory models have been proposed in the literature. These include processor consistency (PC), weak ordering (WO), release consistency (RCsc/RCpc), total store ordering (TSO), and partial store ordering (PSO). While the relaxed models provide the potential for higher performance, they present a more complex model for programmers when compared to SC. Our previous research has addressed this tradeoff by taking a programmer-centric approach. We have proposed memory models (DRF0, DRF1, PL) that allow the programmer to reason with SC, but require certain information about the memory accesses. This information is used by the system to relax the ordering among memory accesses while still maintaining SC for the programmer. Our previous models formalized the information that allowed optimizations associated with WO and RCsc to be used. This paper extends the above approach by defining a new model, PLpc, that allows optimizations of the TSO, PSO, PC, and RCpc models as well. Thus, PLpc provides a unified programming model that maintains the ease of reasoning with SC while providing for efficiency and portability across a wide range of proposed system designs.

The cache invalidation patterns of several parallel applications are analyzed. The results are based on multiprocessor simulations with 8, 16, and 32 processors. To provide deeper insight into the observed invalidation behavior the invalidations observed in the simulations are linked to the high-level objects causing them in the programs. To predict what the invalidation patterns would look like beyond 32 processors, a classification scheme for data objects found in parallel programs is proposed. The classification scheme provides a powerful conceptual tool to reason about the invalidation patterns of parallel applications. Results indicate that it should be possible to scale well-written parallel programs to a large number of processors without an explosion in invalidation traffic. At the same time, the invalidation patterns are such that directory-based schemes with just a few pointers per entry can be very effective. The variations in invalidation behavior with different cache line sizes are discussed. The results indicate that cache line sizes in the 32-byte range yield the lowest data and invalidation traffic.>

The authors examine the suitability of message-passing computers for parallel implementations of production systems. Two mappings for production systems on these computers, one targeted toward fine-grained message-passing machines and the other targeted toward medium-grained machines, are presented. Simulation results for the medium-grained mapping are presented, and it is shown that it is possible to exploit the available parallelism and to obtain reasonable speedups. The authors perform a detailed analysis of the results and suggest solutions for some of the problems.>

The memory consistency model supported by a multiprocessor architecture determines the amount of buffering and pipelining

Techniques that can cope with the large latency of memory accesses are essential for achieving high processor utilization in large-scale shared-memory multiprocessors. In this paper, we consider four architectural techniques that address the latency problem: (i) hardware coherent caches, (ii) relaxed memory consistency, (iii) softwarecontrolled prefetching, and (iv) multiple-context support. While some studies of benefits of the individual techniques have been done, no study evaluates all of the techniques within a consistent framework. This paper attempts to remedy this by providing a comprehensive evaluation of the benefits of the four techniques, both individually and in combinations, using a consistent set of architectural assumptions. The results in this paper have been obtained using detailed simulations of a large-scale shared-memory multiprocessor. Our results show that caches and relaxed consistency uniformly improve performance. The improvements due to prefetching and multiple contexts are sizeable, but are much more applicationdependent. Combinations of the various techniques generally attain better performance than each one on its own. Overall, we show that using suitable combinations of the techniques, performance can be improved by 4 to 7 times.

Shared-memory multiprocessors are frequently used as compute servers with multiple parallel applications executing at the same time. In such environments, the efficiency of a parallel application can be significantly affected by the operating system scheduling policy. In this paper, we use detailed simulation studies to evaluate the performance of several different scheduling strategies, These include regular priority scheduling, coscheduling or gang scheduling, process control with processor partitioning, handoff scheduling, and affinity-based scheduling. We also explore tradeoffs between the use of busy-waiting and blocking synchronization primitives and their interactions with the scheduling strategies. Since effective use of caches is essential to achieving high performance, a key focus is on the impact of the scheduling strategies on the caching behavior of the applications.Our results show that in situations where the number of processes exceeds the number of processors, regular priority-based scheduling in conjunction with busy-waiting synchronization primitives results in extremely poor processor utilization. In such situations, use of blocking synchronization primitives can significantly improve performance. Process control and gang scheduling strategies are shown to offer the highest performance, and their performance is relatively independent of the synchronization method used. However, for applications that have sizable working sets that fit into the cache, process control performs better than gang scheduling. For the applications considered, the performance gains due to handoff scheduling and processor affinity are shown to be small.

The large latency of memory accesses is a major obstacle in obtaining high processor utilization in large-scale shared-memory multiprocessors. Although the provision of coherent caches in many recent machines has alleviated the problem somewhat, cache misses still occur frequently enough that they significantly lower performance. In this paper we evaluate the effectiveness of nonbinding software-controlled prefetching, as proposed in the Stanford DASH multiprocessor, to address this problem. The prefetches are nonbinding in the sense that the prefetched data is brought to a cache close to the processor, but is still available to the cache-coherence protocol to keep it consistent. Prefetching is software-controlled since the program must explicitly issue prefetch instructions. The paper presents results from detailed simulation studies done in the context of the Stanford DASH multiprocessor. Our results show that for applications with regular data access patterns—we evaluate a particle-based simulator used in aeronautics and an LU-decomposition application—prefetching can be very effective. It was easy to augment the applications to do prefetching and their performance was increased by 100–150% when we prefetched directly into the processor's cache. However, for applications with complex data usage patterns, prefetching was less successful. After much effort, the performance of a distributed-time logic simulation application that made extensive use of pointers and linked lists could be increased by only 30%. The paper also evaluates the effects of various hardware optimizations such as separate prefetch issue buffers, prefetching with exclusive ownership, lockup-free caches, and weaker memory consistency models on the performance of prefetching.

The performance of workstation-class machines has increased dramatically in the recent past.Relatively inexpensive machines offering 10-20 MIPS and 1-5 MFLOPS performance are now available, and machines with even higher performance are not far off.One important.characteristic of these machines is that they rely on a emall amount of high-speed cache memory for their increased performance.In this paper, we consider the problem of Cholesky factorization of a large sparse positive definite system of equations on a high-performance workstation.We find that the major factor limiting performance is the cost of moving data between memory and the processor.We use two techniques to address this limitation; we decrease the number of memory references and we improve cache behavior to decrease the cost of each reference.Using benchmarks from the Harwell-Boeing Sparse Matrix Collection, experimente on a DECstation 3100 show that the resulting factorization code is almost three times as fast as SPARSPAK.We believe that the issues brought up in this paper will play an important role in the effective uee of high-performance workstations on large numerical problems.

Scalable shared-memory multiprocessors distribute memory among the processors and use scalable interconnection networks to provide high bandwidth and low latency communication. In addition, memory accesses are cached, buffered, and pipelined to bridge the gap between the slow shared memory and the fast processors. Unless carefully controlled, such architectural optimizations can cause memory accesses to be executed in an order different from what the programmer expects. The set of allowable memory access orderings forms the memory consistency model or event ordering model for an architecture.

DASH is a scalable shared-memory multiprocessor currently being developed at Stanford's Computer Systems Laboratory. The architecture consists of powerful processing nodes, each with a portion of the shared-memory, connected to a scalable interconnection network. A key feature of DASH is its distributed directory-based cache coherence protocol. Unlike traditional snoopy coherence protocols, the DASH protocol does not rely on broadcast; instead it uses point-to-point messages sent between the processors and memories to keep caches consistent. Furthermore, the DASH system does not contain any single serialization or control point. While these features provide the basis for scalability, they also force a reevaluation of many fundamental issues involved in the design of a protocol. These include the issues of correctness, performance and protocol complexity. In this paper, we present the design of the DASH coherence protocol and discuss how it addresses the above issues. We also discuss our strategy for verifying the correctness of the protocol and briefly compare our protocol to the IEEE Scalable Coherent Interface protocol.

The problem of factoring large sparse systems of equations on high-performance multiprocessor workstations is investigated. A parallel factorization code is described which utilizes the supernodal structure of the matrix to substantially reduce the number of memory references. The authors also propose enhancements that significantly reduce the overall cache miss rate, resulting in greatly increased factorization performance. Experimental results from executions on the Silicon Graphics 4D/380 multiprocessor are presented. Using eight processors, the parallel supernodal code achieves a computation rate of approximately 40 MFLOPS when factoring a range of benchmark matrices. This is more than twice as fast as previously used parallel nodal approaches.>

To make shared-memory multiprocessors scalable, researchers are now exploring cache coherence protocols that do not rely on broadcast, but instead send invalidation messages to individual caches that contain stale data. The feasibility of such directory-based protocols is highly sensitive to the cache invalidation patterns that parallel programs exhibit. In this paper, we analyze the cache invalidation patterns caused by several parallel applications and investigate the effect of these patterns on a directory-based protocol. Our results are based on multiprocessor traces with 4, 8 and 16 processors. To gain insight into what the invalidation patterns would look like beyond 16 processors, we propose a classification scheme for data objects found in parallel applications and link the invalidation traffic patterns observed in the traces back to these high-level objects. Our results show that synchronization objects have very different invalidation patterns from those of other data objects. A write reference to a synchronization object usually causes invalidations in many more caches. We point out situations where restructuring the application seems appropriate to reduce the invalidation traffic, and others where hardware support is more appropriate. Our results also show that it should be possible to scale “well-written” parallel programs to a large number of processors without an explosion in invalidation traffic.

This paper explores the suitability of the Chandy-Misra algorithm for digital logic simulation. We use four realistic circuits as benchmarks for our analysis, with one of them being the vector-unit controller for the Titan supercomputer from Ardent. Our results show that the average number of logic elements available for concurrent execution ranges from 10 to 111 for the four circuits, with an overall average of 68. Although this is twice as much parallelism as that obtained by traditional event-driven algorithms for these circuits, we feel it is still too low. One major factor limiting concurrency is the large number of global synchronization points — “deadlocks” in the Chandy-Misra terminology — that occur during execution. Towards the goal of reducing the number of deadlocks, the paper presents a classification of the types of deadlocks that occur during digital logic simulation. Four different types are identified and described intuitively in terms of circuit structure. Using domain specific knowledge, the paper proposes methods for reducing these deadlock occurrences. For one of the benchmark circuits, the use of the proposed techniques eliminated all deadlocks and increased the average parallelism from 40 to 160. We believe that the use of such domain knowledge will make the Chandy-Misra algorithm significantly more effective than it would be in its generic form.

A fundamental problem that any scalable multiprocessor must address is the ability to tolerate high latency memory operations. This paper explores the extent to which multiple hardware contexts per processor can help to mitigate the negative effects of high latency. In particular, we evaluate the performance of a directory-based cache coherent multiprocessor using memory reference traces obtained from three parallel applications. We explore the case where there are a small fixed number (2-4) of hardware contexts per processor and the context switch overhead is low. In contrast to previously proposed approaches, we also use a very simple context switch criterion, namely a cache miss or a write-hit to shared data. Our results show that the effectiveness of multiple contexts depends on the nature of the applications, the context switch overhead, and the inherent latency of the machine architecture. Given reasonably low overhead hardware context switches, we show that two or four contexts can achieve substantial performance gains over a single context. For one application, the processor utilization increased by about 46% with two contexts and by about 80% with four contexts.

Shared-memory multiprocessors are frequently used in a time-sharing style with multiple parallel applications executing at the same time. In such an environment, where the machine load is continuously varying, the question arises of how an application should maximize its performance while being fair to other users of the system. In this paper, we address this issue. We first show that if the number of runnable processes belonging to a parallel application significantly exceeds the effective number of physical processors executing it, its performance can be significantly degraded. We then propose a way of controlling the number of runnable processes associated with an application dynamically, to ensure good performance. The optimal number of runnable processes for each application is determined by a centralized server, and applications dynamically suspend or resume processes in order to match that number. A preliminary implementation of the proposed scheme is now running on the Encore Multimax and we show how it helps improve the performance of several applications. In some cases the improvement is more than a factor of two. We also discuss implications of the proposed scheme for multiprocessor schedulers, and how the scheme should interface with parallel programming languages.

This paper presents measurements made on several large OPS5 production systems (rule-based systems). The complete set of measurements is divided into three parts. The first part consists of measurements on the textual structure of the production system programs. The second part consists of measurements on the compiled form of the productions, and the third part consists of run-time measurements on the production system programs. The measurements are essential to the design of high-performance interpreters for production systems. The measurements are also designed to help explore the role of parallelism in execution of production system programs.

Rule-based systems are widely used in artificial intelligence for modeling intelligent behavior and building expert systems. Most rule-based programs, however, are extremely computation intensive and run quite slowly. The slow speed of execution has prohibited the use of rule-based systems in domains requiring high performance and real-time response. In this paper we explore various methods for speeding up the execution of rule-based systems. In particular, we examine the role of parallelism in the high-speed execution of rule-based systems and study the architectural issues in the design of computers for rule-based systems. Our results show that contrary to initial expectations, the speed-up that can be obtained from parallelism is quite limited, only about tenfold. The reasons for the small speed-up are: (1) the small number of rules relevant to each change to data memory; (2) the large variation in the processing requirements of relevant rules; and (3) the small number of changes made to data memory between synchronization steps. Furthermore, we observe that to obtain this limited factor of tenfold speed-up, it is necessary to exploit parallelism at a very fine granularity. We propose that a suitable architecture to exploit such fine-grain parallelism is a shared-memory multiprocessor with 32-64 processors. Using such a multiprocessor, it is possible to obtain execution speeds of about 3800 rule-firings/set. This speed is significantly higher than that obtained by other proposed parallel implementations of rule-based systems.

VMP is an experimental multiprocessor being developed at Stanford University, suitable for high-performance workstations and server machines. Its primary novelty lies in the use of software management of the per-processor caches and the design decisions in the cache and bus that make this approach feasible. The design and some uniprocessor trace-driven simulations indicating its performance have been reported previously. Initial experience with the VMP design, based on a running prototype as well as various refinements to the design, is presented. Performance evaluation is based both on measurement of actual execution as well as trace-driven simulation of multiprocessor executions from the Mach operating system.>

Shared-memory multiprocessors have received wide attention in recent times as a means of achieving high-performance cost-effectively. Their viability requires a thorough understanding of the memory access patterns of parallel processing applications and operating systems. This paper reports on the memory reference behavior of several parallel applications running under the MACH operating system on a shared-memory multiprocessor. The data used for this study is derived from multiprocessor address traces obtained from an extended ATUM address tracing scheme implemented on a 4-CPU DEC VAX 8350. The applications include parallel OPS5, logic simulation, and a VSLI wire routing program. Among the important issues addressed in this paper are the amount of sharing in user programs and in the operating system, comparing the characteristics of user and system reference patterns, sharing related to process migration, and the temporal, spatial, and processor locality of shared blocks. We also analyze the impact of shared references on cache coherence in shared-memory multiprocessors.

Rule-based systems, on the surface, appear to be capable of exploiting large amounts of parallelism—it is possible to match each rule to the data memory in parallel. In practice, however, we show that the speed-up from parallelism is quite limited, less than 10-fold. The reasons for the small speed-up are: (1) the small number of rules relevant to each change to data memory; (2) the large variation in the processing required by the relevant rules; and (3) the small number of changes made to data memory between synchronization steps. Furthermore, we observe that to obtain this limited factor of 10-fold speed-up, it is necessary to exploit parallelism at a very fine granularity. We propose that a suitable architecture to exploit such fine-grain parallelism is a bus-based shared-memory multiprocessor with 32-64 processors. Using such a multiprocessor (with individual processors working at 2 MIPS), it is possible to obtain execution speeds of about 3800 rule-firings/sec. This speed is significantly higher than that obtained by other proposed parallel implementations of rule-based systems.