Return-oriented programming (ROP) is a technique for hijacking the control-flow of a program and forcing it to perform computations that were never originally intended. ROP is achieved by modifying the values of return addresses saved to memory, causing a failure of control-flow integrity. In the POWER10 processor, we have adopted a cryptographic mechanism for ROP protection. Return addresses are cryptographically hashed when control-flow enters a function and the hash is saved in memory. The hash is recomputed and compared to the saved value just before a return from the function. Any mismatch is flagged as a violation and generates an exception to the supervisor. POWER10 was augmented with instructions to generate and verify those hashes. We minimize performance impact on running programs by implementing the cryptographic hash with dedicated functional units.

Large-scale graph processing is an increasingly important workload in modern systems. Conventional systems are usually optimized for locality of memory references, using caches and parallelization techniques to cover long memory latencies. However since graphs are distributed over memory in unpredictable manner, their processing does not exhibit great locality. While graph algorithms have plenty of parallelism, they are not easily amenable for effective vectorization, as the memory references are scattered all over. What is needed is a paradigm to specify a number of parallel tasks, each of which performs a short computation near the memory and a mechanism to efficiently execute them. In this paper, we propose a novel computational model that is memory-centric: the computation is organized as a collection of functions, each of which operates on a specific piece of data and is executed close to the memory where it resides. Basic primitives are provided to orchestrate the flow, synchronization and execution of the functions at their respective data points to accomplish a global task. We propose a scalable architecture to execute this computational model. We simulate an implementation of this architecture to compare the performance of running some graph algorithms on it with observed performance when the same algorithms were run on conventional systems. Preliminary results for a few graph algorithms show our approach is very promising in improving the performance of graph algorithms.

The capability of the Random Access Machine (RAM) to execute any instruction in constant time is not realizable, due to fundamental physical constraints on the minimum size of devices and on the maximum speed of signals. This work explores how well the ideal RAM performance can be approximated, for significant classes of computations, by machines whose building blocks have constant size and are connected at a constant distance. A novel memory structure is proposed, which is pipelined (can accept a new request at each cycle) and hierarchical , exhibiting optimal latency a ( x ) = O ( x 1/ d ) to address x , in d -dimensional realizations. In spite of block-transfer or other memory-pipeline capabilities, a number of previous machine models do not achieve a full overlap of memory accesses. These are examples of machines with explicit data movement . It is shown that there are direct-flow computations (without branches and indirect accesses) that require time superlinear in the number of instructions, on all such machines. To circumvent the explicit-data-movement constraints, the Speculative Prefetcher (SP) and the Speculative Prefetcher and Evaluator (SPE) processors are developed. Both processors can execute any direct-flow program in linear time. The SPE also executes in linear time a class of loop programs that includes many significant algorithms. Even quicksort, a somewhat irregular, recursive algorithm admits a linear-time SPE implementation. A relation between instructions called address dependence is introduced, which limits memory-access overlap and can lead to superlinear time, as illustrated with the classical merging algorithm.

Detailed cache simulation can be useful to both system developers and application writers to understand an application’s performance. However, measuring long running programs can be extremely slow. In this paper we present a technique to use dynamic sampling of trace snippets throughout an application’s execution. We demonstrate that our approach improves accuracy compared to sampling a few timesteps at the beginning of execution by judiciously choosing the frequency, as well as the points in the control flow, at which samples are collected. Our approach is validated using the SIGMA tracing and simulation framework for the IBM Power family of processors.

In this paper we present SIGMA (Simulation Infrastructure to Guide Memory Analysis), a new data collection framework and family of cache analysis tools. The SIGMA environment provides detailed cache information by gathering memory reference data using software-based instrumentation. This infrastructure can facilitate quick probing into the factors that influence the performance of an application by highlighting bottleneck scenarios including: excessive cache/TLB misses and inefficient data layouts. The tool can also assist in perturbation analysis to determine performance variations caused by changes to architecture or program. Our validation tests using the SPEC Swim benchmark show that most of the performance metrics obtained with SIGMA are within 1% of the metrics obtained with hardware performance counters, with the advantage that SIGMA provides performance data on a data structure level, as specified by the programmer.

In a recent paper (SPAA'01), we have established that the Pipelined Hierarchical Random Access Machine (PH-RAM) is a powerful model of computation, where most of the memory latency can be hidden by concurrency of accesses. In the present work, we explore the physical feasibility of PH-RAMs.A pipelined hierarchical memory of size $S$ is characterized by two metrics: the access function α(χ), denoting the time required by an access to location $x$, and the pipeline period $p(S)$, denoting the minimum time between subsequent accesses that can be sustained. Physical constraints on minimum device size and maximum signal speed imply that, for a memory laid out in $d$ dimensions, a(χ)= Ω(χ1/d)$. We propose a novel memory organization scheme that can be specialized to yield optimal performance α(χ)=O(χ^1/d)$ and $p(S)=O(1)$, for any $d \geq 1$.Managing a large number of concurrent load and store instructions would pose a significant burden on a traditional RISC processor, requiring both a large register file and complex logic to properly synchronize instructions. We show how these obstacles can be circumvented by introducing the Scalable transPORT (SPORT) computer where a simple processor drives a version of our pipelined hierarchical memory capable of servicing memory-to-memory instructions. We show that SPORT provides a feasible, scalable implementation of the PH-RAM model.

We define a model of computation, called the Pipelined Hierarchical Random Access Machine with access function a (x), denoted the a(x)-PH-RAM. In this model, a processor interacts with a memory which can accept requests at a constant rate and satisfy each of the requests to the location x within a(x) units of time.We investigate memory management strategies that lead to time efficient implementations of arbitrary computations on a PH-RAM. We begin by developing the so called pipeline d decomposition-treememory management strategy, which can be tuned to the memory access function. Specifically, for a linear or sublinear access function a(x), w e define the concept of latency-hiding depth da(x) and show ho w an y computation of N operations can be implemented on an a(x)-PH-RAM in time T(N) = O(Nda(N)). In particular, T(N) = O(N log N) if a(x) = O(x), T(N) = O(N log log N) if a(x) = O(xΒ) with 0 Β T(N) = O(N log* N) if a(x) = O(log x).We develop lower bound techniques that allow to establish existential lower bounds on PH-RAMs. In particular, we exhibit computations for which T(N) = O(Nlog N/ log log N) when a(x) = O(x), T(N) = O(Nlog logN) when a(x) = O(xΒ) with 0 Β T(N) = O(N log* N) when a(x) = O(log x).The stated lower bounds show that the pipelined decomposition-tree strategy is existentially optimal for the latter case but indicates the potential for a modest, O(log log N) improvement for linear access functions. To realize this potential, a superpipelined decomposition-tree memory manager is proposed, which achieves T(N) = O(N log N/log log N).The pipelined decomposition-tree strategy can also be tuned to the computation, in order to exploit its temporal locality as characterized by the width parameters [9]. When the latter are suitably bounded, then T(N) = O(N) on any PH-RAM with linear or sublinear access function. Finally, we discuss how performance could benefit from parallelism in the data-dependence dag of the computation or from architectural enhancements, such as block-transfer primitives, and formulate various questions that deserve further investigation.

This paper describes PRISM, a distributed shared memory architecture that relies on a tightly integrated hardware and operating system design for scalable and reliable performance. PRISM's hardware provides mechanisms for flexible management and dynamic configuration of shared memory pages with different behaviors. As an example, PRISM can configure individual shared memory pages in both CC-NUMA and Simple-COMA styles, maintaining the advantages of both without incorporating any of their disadvantages. PRISM's operating system is structured as multiple independent kernels, where each kernel manages the resources on its local node. PRISM's system structure minimizes the amount of global coordination when managing shared memory. Page faults do not involve global TLB invalidates, and pages can be replicated and migrated without requiring global coordination. The structure also provides natural fault containment boundaries around each node because physical addresses do not address remote memory directly. We simulate PRISM's hardware, cache coherence protocol and memory management algorithms. Results from SPLASH applications on the simulated machine demonstrate a tradeoff between CC-NUMA and Simple-COMA styles of memory management. Adaptive, run-time policies that take advantage of PRISM's ability to dynamically configure shared memory pages with different behaviors significantly outperform pure CC-NUMA or Simple-COMA configurations and are usually within 10% of optimal performance.

In a distributed shared memory system, each memory page is associated with a home node that maintains the directory state for cache lines within that page. Memory access patterns and home node locations have a strong influence on performance, especially if remote communication is costly. Since access patterns are difficult to predict and may change dynamically, it is useful to dynamically migrate home nodes to reduce the amount of remote communication. The paper presents a new and efficient algorithm for migrating home nodes in distributed shared memory systems. Unlike previous page migration algorithms, our algorithm avoids global coordination. Allowing the system to be more responsive to changing workloads. We verify the algorithm's correctness with the Mur/spl sigma/ protocol verification tool. We explore several policies for deciding when and where to migrate home nodes. Trace driven simulations of several SPLASH-2 benchmarks show that our home migration algorithm and policies can reduce the amount of remote communication by 50%. The results also emphasize the importance of minimizing the cost of migration.

Much attention has been focused by the declarative languages community on combining the functional and logic programming paradigms. In particular, there are many efforts to incorporate logic variables into functional languages. We propose a generalization of of logic variables called accumulators which are eminently suited for incorporation into functional languages. We demonstrate the utility of accumulators by presenting examples which show that accumulators can be used profitably in many scientific applications to enhance storage efficiency and parallelism.

The issues of memory latency, synchronization, and distribution costs in multiprocessors are reviewed. The approaches taken by conventional and data flow architectures are contrasted in relation to these issues. It is pointed out that each approach fits well for a certain situation and that it is possible to have a common framework in which the two execution models can be mixed to suit the situation. An architecture is sketched by describing a few extensions to a conventional processor. While existing programs run without much change, it is shown that improvements could be made by using the new features to tolerate memory latency and to exploit more parallelism. It is shown that data flow graphs can be executed on this to exploit as much parallelism as a data flow architecture could. It is argued that such a testbed will provide for a selective translation of program segments into the appropriate execution model. A fast context switching hardware is presumed for this architecture.

This paper presents an implementation of Hoare's Input/Output commands on a 2-dimensional network of microcomputers. The implementation is defined so that message transfer delays are bounded by a constant. The communication kernel is small and is embedded in each process. Dedicated processors are used for message handling.

Protection in capability-based operating systems is comsidered. The concept of a conditional capability, which is a generalization of a conventional capability, is proposed. The conditional capability can only be exercised when certain conditions relating to the context of its use are satisfied. It is shown that such capabilities form a basis upon which features such as domains of protection, revocation, and type extension can be built. The implementation of these features can be isolated into sepuate modules thus leaving the basic protection module uncluttered and simplifying the overall structure of the system.